rectangle solver

The rectangle solver solves problems where items are two-dimensional rectangles that must be packed into rectangular bins without overlapping. Unlike the rectangle-guillotine solver, items can be placed in any position (guillotine cuts are not required).

_images/rectangle.png

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

    • Variable-sized bin packing

  • With or without item rotations

  • Bins may contain defects

  • Maximum weight in bins

  • Unloading constraints: only horizontal/vertical movements, increasing x/y

Basic usage

The rectangle solver takes as input:

  • an item CSV file; option: --items items.csv

  • a bin CSV file; option: --bins bins.csv

  • optionally a defect CSV file; option: --defects defects.csv

  • optionally 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 WIDTH

    • Integer value

  • The height of the item type (mandatory)

    • column HEIGHT

    • Integer value

  • The number of copies of the item type

    • column COPIES

    • default value: 1

  • The profit of an item of this type (for a knapsack objective)

    • column PROFIT

    • default value: item area (WIDTH * HEIGHT)

The bin file contains:

  • The width of the bin type (mandatory)

    • column WIDTH

    • Integer value

  • The height of the bin type (mandatory)

    • column HEIGHT

    • Integer value

  • The number of copies of the bin type

    • column COPIES

    • default value: 1

  • The minimum number of copies of the bin type that must be used

    • column COPIES_MIN

    • default value: 0

  • The cost of a bin of this type (for a variable-sized bin packing objective)

    • column COST

    • default value: bin area (WIDTH * HEIGHT)

The parameter file has two columns: NAME and VALUE. The possible entries are:

  • The objective; name: objective; possible values:

    • knapsack

    • bin-packing

    • bin-packing-with-leftovers

    • open-dimension-x

    • open-dimension-y

    • open-dimension-xy

    • variable-sized-bin-packing

Inputs:

items.csv
WIDTH,HEIGHT,COPIES
300,200,10
250,150,10
bins.csv
WIDTH,HEIGHT,COPIES
1000,500,10
parameters.csv
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:      inf
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.001           3      275000                  TS g 0 d X q 1
       0.001           3      462500                  TS g 0 d X q 2
       0.002           2           0                  TS g 0 d X q 9

Final statistics
----------------
Time (s):  5.00498

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:       inf / inf (-nan%)
Bin cost:         1e+06
Waste:            25000
Waste (%):        2.5
Full waste:       25000
Full waste (%):   2.5
Area load:        0.195
Weight load:      0
X max:            1000
Y max:            500
Leftover value:   0

Visualize:

python3 scripts/visualize_rectangle.py solution.csv
_images/rectangle_example_solution.png

Item rotations

Each item may individually be allowed to be rotated by 90° or have a fixed orientation.

By default, item rotation is allowed.

  • Whether the item is fixed in its original orientation (cannot be rotated 90°)

    • column ORIENTED

    • 0: rotation allowed (default)

    • 1: item is oriented; rotation not allowed

The following example packs 3 items of size 400×200 into a 1000×500 bin. Without rotation, the items occupy an 800×400 region and leave a narrow leftover. With rotation, one item is placed at 200×400, allowing all three to pack into a compact 600×400 region and leaving a larger leftover.

Without rotation

With rotation
items.csv
WIDTH,HEIGHT,COPIES,ORIENTED
400,200,3,1
items.csv
WIDTH,HEIGHT,COPIES,ORIENTED
400,200,3,0
bins.csv
WIDTH,HEIGHT,COPIES
700,500,2
bins.csv
WIDTH,HEIGHT,COPIES
700,500,2
parameters.csv
NAME,VALUE
objective,bin-packing-with-leftovers
parameters.csv
NAME,VALUE
objective,bin-packing-with-leftovers

packingsolver_rectangle \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv

packingsolver_rectangle \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv

rect_rotation_no

rect_rotation_yes

Defects

Defects are rectangular regions inside a bin where items cannot be placed.

Defects are specified in the defects CSV file; option: --defects defects.csv. The defect file contains:

  • The bin type that contains the defect (mandatory)

    • column BIN

    • It refers to the bin type by its position (0-indexed) in the bins file

  • The X coordinate of the bottom-left corner of the defect (mandatory)

    • column X

    • Integer value

  • The Y coordinate of the bottom-left corner of the defect (mandatory)

    • column Y

    • Integer value

  • The width of the defect (mandatory)

    • column WIDTH

    • Integer value

  • The height of the defect (mandatory)

    • column HEIGHT

    • Integer value

The following example packs 3 items of size 400×200 into a 1000×500 bin. Without defects, the items fill a compact L-shaped region. With a 200×300 defect at position (450, 150), the item that would naturally sit there is pushed further right, reducing the leftover.

Without defects

With defects
items.csv
WIDTH,HEIGHT,COPIES,ORIENTED
400,200,3,1
items.csv
WIDTH,HEIGHT,COPIES,ORIENTED
400,200,3,1
bins.csv
WIDTH,HEIGHT,COPIES
800,500,1
800,500,1
bins.csv
WIDTH,HEIGHT,COPIES
800,500,1
800,500,1
parameters.csv
NAME,VALUE
objective,bin-packing-with-leftovers
parameters.csv
NAME,VALUE
objective,bin-packing-with-leftovers
defects.csv
BIN,X,Y,WIDTH,HEIGHT
0,450,150,50,200

packingsolver_rectangle \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv

packingsolver_rectangle \
        --items items.csv \
        --bins bins.csv \
        --defects defects.csv \
        --parameters parameters.csv \
        --certificate solution.csv

rect_defects_no

rect_defects_yes

Maximum total weight in a bin

Each bin type may have a maximum weight limit: the total weight of items placed in any bin must not exceed its maximum weight.

  • The weight of the item

    • column WEIGHT

    • default value: 0

  • The maximum total weight that can be placed in a bin of this type

    • column MAXIMUM_WEIGHT

    • default value: no limit

The following example packs 4 items of size 300×200 with weight 100 each into 600×400 bins. Without a weight limit, all 4 items (total weight 400) fit in a single bin. With MAXIMUM_WEIGHT=200, at most 2 items can share a bin, so 2 bins are required.

Without maximum weight

With maximum weight
items.csv
WIDTH,HEIGHT,COPIES,WEIGHT
300,200,4,100
items.csv
WIDTH,HEIGHT,COPIES,WEIGHT
300,200,4,100
bins.csv
WIDTH,HEIGHT,COPIES
600,400,10
bins.csv
WIDTH,HEIGHT,COPIES,MAXIMUM_WEIGHT
600,400,10,200
parameters.csv
NAME,VALUE
objective,bin-packing
parameters.csv
NAME,VALUE
objective,bin-packing

packingsolver_rectangle \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv

packingsolver_rectangle \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv

rect_maximum_weight_no

rect_maximum_weight_yes

Unloading constraints

When loading a truck that visits multiple loading/unloading locations, it might be necessary to be able to load/unload the items at a location without having to move the items which are already in the truck. This is modeled in the solver with unloading constraints. Items are assigned to groups: items in group 0 are placed last (nearest the door) and unloaded first, items in group 1 are placed next, etc.

  • The group of the item (for unloading constraints)

    • column GROUP_ID

    • default value: 0

  • The unloading constraint; name: unloading_constraint; possible values:

    • none (default)

    • only-x-movements

    • only-y-movements

    • increasing-x

    • increasing-y

In the following examples, without unloading constraints, all items fit using a width of 600. But with unloading constraints, a width of 750 is necessary.

No constraint

With unloading constraints
items.csv
WIDTH,HEIGHT,GROUP_ID
200,200,0
400,400,1
150,150,2
items.csv
WIDTH,HEIGHT,GROUP_ID
200,200,0
400,400,1
150,150,2
bins.csv
WIDTH,HEIGHT,COPIES
700,400,2
bins.csv
WIDTH,HEIGHT,COPIES
700,400,2
parameters.csv
NAME,VALUE
objective,bin-packing-with-leftovers
parameters.csv
NAME,VALUE
objective,bin-packing-with-leftovers
unloading_constraint,only-x-movements

packingsolver_rectangle \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv

packingsolver_rectangle \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv

rect_unloading_no

rect_unloading_yes

4 types of unloading constraints are available:

  • only-x-movements: items can only be moved out along the X axis; therefore, within each horizontal row, no item from a later group may be positioned to the right of an item from an earlier group

  • only-y-movements: same along the Y axis

  • increasing-x: all items from group 0 have a greater X coordinate than all items from group 1, which in turn have a greater X coordinate than all items from group 2, etc.

  • increasing-y: same along the Y axis

In the following examples, two different solutions are obtained depending of the type of unloading constraint.

only-x-movements

increasing-x
items.csv
WIDTH,HEIGHT,GROUP_ID
500,200,0
200,200,1
150,150,1
items.csv
WIDTH,HEIGHT,GROUP_ID
500,200,0
200,200,1
150,150,1
bins.csv
WIDTH,HEIGHT,COPIES
800,400,1
bins.csv
WIDTH,HEIGHT,COPIES
800,400,1
parameters.csv
NAME,VALUE
objective,open-dimension-x
unloading_constraint,only-x-movements
parameters.csv
NAME,VALUE
objective,open-dimension-x
unloading_constraint,increasing-x

packingsolver_rectangle \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv

packingsolver_rectangle \
        --items items.csv \
        --bins bins.csv \
        --parameters parameters.csv \
        --certificate solution.csv

rect_unloading_x_movements

rect_unloading_increasing_x