Rectangle solver¶
The Rectangle solver solves problems where items are two-dimensional rectangles that must be packed into rectangular bins without overlapping. Unlike the RectangleGuillotine solver, items can be placed in any position (guillotine cuts are not required).
These problems occur for example in logistics (palletizing), sheet-metal cutting, and warehousing.
Features:
Objectives:
Knapsack
Bin packing
Bin packing with leftovers
Open dimension X
Open dimension Y
Open dimension XY
Variable-sized bin packing
Item types
Item rotation (90°)
Groups (for unloading constraints)
Weight
Bin types
Rectangular defects
Maximum weight
Unloading constraints
only-x-movementsonly-y-movementsincreasing-xincreasing-y
Basic usage¶
The Rectangle solver takes as input:
an item CSV file; option:
--items items.csva bin CSV file; option:
--bins bins.csvoptionally a defect CSV file; option:
--defects defects.csvoptionally a parameter CSV file; option:
--parameters parameters.csv
It outputs:
a solution CSV file; option:
--certificate solution.csv
The item file contains:
The width of the item type (mandatory)
column
WIDTHInteger value
The height of the item type (mandatory)
column
HEIGHTInteger value
The number of copies of the item type
column
COPIESdefault value:
1
Whether the item is fixed in its original orientation (cannot be rotated 90°)
column
ORIENTED0: rotation allowed (default)1: item is oriented; rotation not allowed
The profit of an item of this type (for a knapsack objective)
column
PROFITdefault value: item area (
WIDTH * HEIGHT)
The group of the item (for unloading constraints)
column
GROUP_IDdefault value:
0
The weight of the item
column
WEIGHTdefault value:
0
The bin file contains:
The width of the bin type (mandatory)
column
WIDTHInteger value
The height of the bin type (mandatory)
column
HEIGHTInteger value
The number of copies of the bin type
column
COPIESdefault value:
1
The minimum number of copies of the bin type that must be used
column
COPIES_MINdefault value:
0
The cost of a bin of this type (for a variable-sized bin packing objective)
column
COSTdefault value: bin area (
WIDTH * HEIGHT)
The maximum total weight that can be placed in a bin of this type
column
MAXIMUM_WEIGHTdefault value: no limit
The defect file contains:
The bin type that contains the defect (mandatory)
column
BIN
The X coordinate of the bottom-left corner of the defect (mandatory)
column
X
The Y coordinate of the bottom-left corner of the defect (mandatory)
column
Y
The width of the defect (mandatory)
column
WIDTH
The height of the defect (mandatory)
column
HEIGHT
The parameter file has two columns: NAME and VALUE. The possible entries are:
The objective; name:
objective; possible values:knapsackbin-packingbin-packing-with-leftoversopen-dimension-xopen-dimension-yopen-dimension-xyvariable-sized-bin-packing
The unloading constraint; name:
unloading_constraint; possible values:none(default)only-x-movementsonly-y-movementsincreasing-xincreasing-y
Example
Inputs:
WIDTH,HEIGHT,COPIES
300,200,10
250,150,10
WIDTH,HEIGHT,COPIES
1000,500,10
NAME,VALUE
objective,bin-packing-with-leftovers
Solve:
packingsolver_rectangle \
--items items.csv \
--bins bins.csv \
--parameters parameters.csv \
--certificate solution.csv
=================================
PackingSolver
=================================
Problem type
------------
Rectangle
Instance
--------
Objective: BinPackingWithLeftovers
Number of item types: 2
Number of items: 20
Number of bin types: 1
Number of bins: 10
Number of groups: 1
Number of defects: 0
Unloading constraint: None
Total item area: 975000
Total item width: 5500
Total item height: 3500
Smallest item width: 150
Smallest item height: 150
Total item profit: 975000
Largest item profit: 60000
Total item weight: 0
Largest item copies: 10
Total bin area: 5000000
Total bin weight: 0
Largest bin cost: 500000
Time # bins Leftover Comment
---- ------ -------- -------
0.000 3 162500 TS g 0 d X q 1
0.001 3 207500 TS g 0 d X q 1
0.008 3 275000 TS g 0 d X q 1
0.009 3 350000 TS g 0 d Y q 2
0.009 3 462500 TS g 0 d X q 2
0.010 2 0 TS g 0 d X q 9
Final statistics
----------------
Time (s): 30.024
Solution
--------
Number of items: 20 / 20 (100%)
Item area: 975000 / 975000 (100%)
Item weight: 0 / 0 (-nan%)
Item profit: 975000 / 975000 (100%)
Number of bins: 2 / 10 (20%)
Bin area: 1000000 / 5000000 (20%)
Bin weight: 0 / 0 (-nan%)
Bin cost: 1e+06
Waste: 25000
Waste (%): 2.5
Full waste: 25000
Full waste (%): 2.5
Area load: 0.195
Weight load: -nan
X max: 1000
Y max: 500
Leftover value: 0
Visualize:
python3 scripts/visualize_rectangle.py solution.csv
Command-line options¶
packingsolver_rectangle --items items.csv [options]
Mandatory option:
--items, -i: path to the items CSV file (or path prefix when files follow the<prefix>items.csvnaming convention)
Other input options:
--bins, -b: path to the bins CSV file--defects, -d: path to the defects CSV file--parameters: path to the parameters CSV file
Instance modifier options:
--objective, -f: objective (overrides the parameters file)--no-item-rotation: fix all items in their original orientation--bin-infinite-x: make all bins infinite in the X direction (for open-dimension-x)--bin-infinite-y: make all bins infinite in the Y direction (for open-dimension-y)--bin-infinite-copies: make all bin types available in unlimited copies--unweighted: set all item profits to 1--bin-unweighted: set all bin costs to 1
Output options:
--certificate, -c: path for the solution CSV file--output, -o: path for a JSON file with detailed statistics--time-limit, -t: time limit in seconds--verbosity-level, -v: verbosity level (0–3)
Rotation¶
By default, items may be rotated 90°. Set ORIENTED = 1 in the items file to fix an item in its original orientation, or use --no-item-rotation on the command line to disable rotation for all items.
Defects¶
Defects are rectangular regions inside a bin where items cannot be placed. They are specified in the defects CSV file. The BIN column refers to the bin type by its position (0-indexed) in the bins file.
Unloading constraints¶
Unloading constraints model situations where items placed later in the bin must be reachable without moving items placed earlier (e.g., truck loading). The available constraints are:
only-x-movements: items can only be moved out along the X axis; therefore no item is blocked in the X direction by a later itemonly-y-movements: same along the Y axisincreasing-x: items must be packed in non-decreasing order of their X coordinate; later items are always at a higher X positionincreasing-y: same along the Y axis
Groups¶
Items can be assigned to groups via the GROUP_ID column. Groups are used together with unloading constraints to model deliveries: items in group 0 must be placed last (nearest the door) and unloaded first, items in group 1 are placed next, etc.