[PYTHON] [2nd] Learning typical problems-Study materials for learning mathematical optimization

: straight_ruler: Introduction

This is the second study material for learning mathematical optimization for the first time. Please see the first time from the following.

[Part 1] What is optimization? --Study materials for learning mathematical optimization https://qiita.com/ttlabo/private/e6970c6e85cce9ff4e34

: straight_ruler: What is a typical problem?

Various problems can be considered as mathematical optimization problems, but in mathematical optimization, problems such as so-called textbooks or typical problems, which are generally called typical problems (or standard problems), are classified and summarized. there is. These are called typical problems (or standard problems).

The reference text is divided into 7 classes and 24 questions.

: one: Graph network problem class ・ Minimum spanning tree problem ・ Maximum stable set problem ・ Maximum cut problem ・ Shortest path problem ・ Maximum flow problem ・ Minimum cost flow problem

: two: Path problem class ・ Transportation route (delivery optimization) problem ・ Traveling salesman problem ・ Chinese postal delivery problem

: three: Set cover / partition problem class ・ Set cover problem ・ Partition problem ・ Combination auction problem

: four: Scheduling problem class ・ Job shop problem ・ Work scheduling problem

: five: Cutout / stuffing problem class ・ Knapsack problem ・ Pin packing problem ・ N-dimensional packing problem

: six: Placement problem class ・ Facility placement problem ・ Facility layout problem without capacity restrictions

: seven: Assignment / matching problem class ・ Secondary allocation problem ・ Generalization allocation problem ・ Maximum matching problem ・ Weight matching problem ・ Stable matching problem

I will explain some of the above classifications in detail.

** Logistics network design problem ** Problems that determine the placement / reduction of bases such as factories and warehouses, production line capacity, production volume, inventory volume, transportation volume, etc. The most cost-effective of the logistics optimization problems. Focusing only on the transportation volume becomes a transportation optimization problem.

** Delivery optimization (transportation route) problem ** The problem of delivering multiple orders using multiple vehicles. An order is an operation that carries a fixed package from the delivery source to the delivery destination. The order may be subject to constraints such as the shipping time zone of the delivery source and the warehousing time zone of the delivery destination. Because it is a difficult problem, it is often solved by an approximate solution.

** Ship Scheduling Problem ** Delivery optimization problem using ships instead of vehicles. Although there are restrictions peculiar to the sea such as port entry restrictions, the structure is the same as the delivery optimization problem.

** Crew Scheduling Problem (Work Scheduling Problem) ** Problems that require the schedule of crew members such as trucks, railroads, and aircraft, part-time workers, and shifts of nurses.

** Minimum cost flow problem ** The problem of using ships and vehicles to transport supplies from surplus to shortage at the lowest cost to meet the demand at each time of day. Problems such as returning used rental cars and empty pallets to the demand area.

** Safety stock issue ** The problem of balancing inventory costs and out-of-stock risk in case of variability in demand. There is also a model that considers disasters by using multiple suppliers.

** Lot size decision problem ** The problem of deciding how much to make together with inventory cost when it is efficient to make products together, such as when setup costs are incurred.

** Job shop problem (flow shop problem) ** The problem of assigning jobs to machines. When the processing order is fixed, it is called a flow shop problem.

** Packing problem ** The problem of efficiently packing luggage in containers and other containers. Cutting (cutting = dividing resources) and packing problem (packing = packing luggage in a container) are two sides of the same coin, and the problems are the same.

** Revenue management issues ** The problem of maximizing profits by manipulating (raising) prices for products that become obsolete over time. Airfare, hotel accommodation, etc.

To tackle an optimization problem, you can solve the problem at hand more accurately by knowing these typical problems and applying their characteristics and solutions.

: straight_ruler: At the end

Next time, in Part 3, we will finally solve an example of an optimization problem in Python. I hope you continue reading.

For this article, the author is also a beginner in optimization. I think there are misunderstandings and typographical errors, so please feel free to send us your opinions and suggestions.

: straight_ruler: Source

This article is based on the reference text "Problem-solving series using Python: How to create an optimization model using a data analysis library" for mathematical optimization models. The details of the text are below.

■ Reference text "Problem-solving series using Python: How to create an optimization model using a data analysis library" Tsutomu Saito [Author] / Modern Science Co., Ltd. [Publishing]