Combinatorial optimization-typical problem-n-dimensional packing problem

Typical problem and execution method

n-dimensional packing problem

Pack as many n-dimensional rectangular parallelepipeds as possible into the n-dimensional rectangular parallelepiped. Find the way. n corresponds to 1 to 3. When n is 1, the capacity and value are the same in the knapsack problem.

Execution method (two-dimensional packing problem by guillotine cut)

usage


Init signature: TwoDimPackingClass(self, width, height, items=None)
Docstring:
2D packing problem
Cut out items from the original plate with a guillotine cut(Approximate solution)
input
    width, height:The size of the original plate
    items:Of the item(side,Vertical)List of
output
Floor area ratio and items included(side,Vertical,x,y)List of

python


from ortoolpy import TwoDimPackingClass
TwoDimPackingClass(500, 300, [(240, 150), (260, 100), \
    (100, 200), (240, 150), (160, 200)]).solve()

result


(1.0,
 [(240, 150, 0, 0),
  (260, 100, 240, 0),
  (160, 200, 240, 100),
  (100, 200, 400, 100),
  (240, 150, 0, 150)])

python


# pandas.DataFrame
from ortoolpy.optimization import TwoDimPacking
TwoDimPacking('data/tdpacking.csv', 500, 300)[1]
width height x y
0 240 150 0 0
1 260 100 240 0
4 160 200 240 100
2 100 200 400 100
3 240 150 0 150

data

Recommended Posts

Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-typical problem-bin 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