Combinatorial optimization-typical problem-bin packing problem

Typical problem and execution method

Bin packing problem

A box with a capacity of $ c (\ gt 0) $ and $ n = $ 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.

Execution method

usage


Signature: binpacking(c, w)
Docstring:
Bin packing problem
Solve with column generation(Approximate solution)
input
    c:Bin size
    w:List of luggage sizes
output
Luggage size list for each bottle

python


from ortoolpy import binpacking
binpacking(10, [4, 5, 3, 8, 7, 6, 2, 3])

result


[[8], [7, 3], [5, 3, 2], [4, 6]]

python


# pandas.DataFrame
from ortoolpy.optimization import BinPacking
BinPacking('data/binpacking.csv', 10)
id size
0 0 8.0
1 1 7.0
2 1 3.0
3 2 5.0
4 2 3.0
5 2 2.0
6 3 4.0
7 3 6.0

data

Recommended Posts

Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-minimum cost flow problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-minimum cut problem
Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints
Combinatorial optimization-typical problems and execution methods