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).

_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

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

  • 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 profit of an item of this type (for a knapsack objective)

    • column PROFIT

    • default value: item area (WIDTH * HEIGHT)

  • The group of the item (for unloading constraints)

    • column GROUP_ID

    • default value: 0

  • The weight of the item

    • column WEIGHT

    • default value: 0

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 maximum total weight that can be placed in a bin of this type

    • column MAXIMUM_WEIGHT

    • default value: no limit

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 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

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

    • none (default)

    • only-x-movements

    • only-y-movements

    • increasing-x

    • increasing-y

Basic example

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.007           3      275000                  TS g 0 d X q 1
       0.008           3      462500                  TS g 0 d X q 2
       0.009           2           0                  TS g 0 d X q 9

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

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:       -9.22337e+18 / inf (-0%)
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

Rotation

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

By default, item rotation is allowed.

Fixed orientation is specified via the ORIENTED column in the item CSV file. Value 1 specifies fixed orientation (no rotation alllowed), and value 1 rotation 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
1000,500,1
bins.csv
WIDTH,HEIGHT,COPIES
1000,500,1
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 (see above).

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
1000,500,1
bins.csv
WIDTH,HEIGHT,COPIES
1000,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 weight

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

The weight of an item type is specified vie the WEIGHT column in the item CSV file. The maximum weight of a bin type is specified via the MAXIMUM_WEIGHT column in the bin CSV file. Items are assigned a weight via the WEIGHT column in the item CSV file.

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 an item type is specified via the GROUP_ID column in the item CSV file. Unloading constraints are specified via the unloading_constraint key in the parameters CSV file.

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
800,400,1
bins.csv
WIDTH,HEIGHT,COPIES
800,400,1
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