The Combinatorial Optimization (http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721) problem has its own set of difficulties. There are multiple modeling methods for the same problem, and each model has its own advantages and disadvantages. How to model is important. Here, we will explain how to devise it by taking the bin packing problem as an example.
| A box with a capacity of $ c (\ gt 0) $ and $ n $ luggage $ N = \ {1, \ dots, n \} $ are given. Let the capacity of the luggage $ i \ in N $ be $ w_i (\ gt 0) $. Find an assortment that minimizes the number of boxes needed to pack all your luggage. |
For example, when carrying some heavy objects on a 10t truck, it is a problem to ask for as few trucks as possible.
reference [Bin packing problem-Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%93%E3%83%B3%E3%83%91%E3%83%83%E3%82%AD % E3% 83% B3% E3% 82% B0% E5% 95% 8F% E9% A1% 8C)
Let's formulate it as it is.
| One-step formulation | ||
| $ \ mbox {objective} $ | $ \ sum_i {y_i} $ | Number of boxes |
| $ \ mbox {variables} $ | $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ | Whether to put the box $ j $ in the luggage $ i $ |
| $ y_j \ in \ {0, 1 \} ~ \ forall j $ | Whether to use box $ j $ | |
| $ \ mbox {subject to} $ | $ \ sum_j {x_ {ij}} = 1 ~ \ forall i $ | Luggage Put $ i $ in one of the boxes |
| $ \ sum_i {w_i x_ {ij}} \ le c ~ \ forall j $ | Fill the capacity of the box $ j $ | |
| $ x_ {ij} \ le y_j ~ \ forall i, j $ | Constraints on $ y $ | |
In fact, this formulation is difficult for the solver to solve and is very time consuming to calculate.
As a result, it is faster to fix the number of boxes, check if there is a solution, and change the number of boxes in the outer loop.
The formulas A and B when the number of boxes is fixed are shown below.
| Two-step formulation A | ||
| $ \ mbox {objective} $ | None | |
| $ \ mbox {variables} $ | $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ | Luggage $ Whether to put the box $ j $ in i $ |
| $ \ mbox {subject to} $ | $ \ sum_j {x_ {ij}} = 1 ~ \ forall i $ | Luggage Put $ i $ in one of the boxes |
| $ \ sum_i {w_i x_ {ij}} \ le c ~ \ forall j $ | Fill the capacity of the box $ j $ | |
| Two-step formulation B | ||
| $ \ mbox {objective} $ | $ y $ | Exceeding capacity |
| $ \ mbox {variables} $ | $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ | Whether to put the box $ j $ in the luggage $ i $ |
| $ y \ ge 0 $ | Exceeding capacity | |
| $ \ mbox {subject to} $ | $ \ sum_j {x_ {ij}} = 1 ~ \ forall i $ | Luggage Put $ i $ in one of the boxes |
| $ \ sum_i {w_i x_ {ij}} \ le c + y ~ \ forall j $ | Fill the capacity of the box $ j $ | |
It has the following features.
| Formulation | When a solution exists | When there is no solution |
|---|---|---|
| Two-step formulation A | Very time consuming | Ends soon |
| Two-step formulation B | Ends soon | Very time consuming |
From this, if you run A and B in parallel, you can quickly see if a solution exists. The number of boxes can be found efficiently by searching for 2 minutes.
Is there a quick way to avoid parallelizing?
The exact solution formulation is inefficient due to the symmetry of the solution (box X and box Y may be exchanged). Therefore, in practice, you will often use the approximate solution method. There is a column generation method as an approximate solution method for solving a bin-packing problem. Although it is an approximate solution, accuracy can be expected. However, since it is a complicated method, the explanation is omitted. If you are interested, please read the relatively easy-to-understand paper (First column generation method). In Python, column generation method is performed by ortoolpy.binpacking which can be installed by "pip install or toolpy".
Greedy and local search methods are commonly used as other approximate solutions, but they are omitted here.
Combinatorial optimization problems are often on the exponential order. From this, if the problem can be divided, it will be an approximate solution, but it can be speeded up. In general, Divide and Conquer (https://ja.wikipedia.org/wiki/%E5%88%86%E5%89%B2%E7%B5%B1%E6%B2%BB%E6% It is called B3% 95).
that's all