one-dimensional solver

The one-dimensional solver solves problems with one-dimensional items and bins.

_images/onedimensional.png

These problems occur for example when cutting paper rolls, pipes, cables, steel bars; or when stacking parcels.

This dimension is called length here.

Features:

  • Objectives:

    • Knapsack

    • Bin packing

    • Bin packing with leftovers

    • Variable-sized bin packing

  • Nesting length between consecutive items

  • Maximum number of items in a bin containing an item of a given type

  • Maximum weight allowed after an item of a given type

  • Maximum weight in bins

Basic usage

The one-dimensional solver takes as input:

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

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

  • a parameter CSV file; option: --parameters parameters.csv

It outputs:

  • a solution CSV file; option: --certificate solution.csv

The item file contains:

  • The dimension of the item type (mandatory)

    • column X

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

The bin file contains:

  • The dimension of the bin type (mandatory)

    • column X

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

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

    • variable-sized-bin-packing

The output certificate file is a CSV file as well. Each line corresponds to either a bin - if the value in the TYPE column is BIN - or to an item of the solution - if the value in the TYPE column is ITEM.

A line corresponding to a bin contains:

  • The id of the bin type

    • Column ID

  • The number of copies of this bin in the solution

    • Column COPIES

  • The length of the bin (input)

    • Column X

A line corresponding to an item contains:

  • The id of the item type

    • Column ID

  • The starting length of the item

    • Column X

  • The length of the item (input)

    • Column LX

Inputs:

items.csv
X
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
bins.csv
X,COPIES
1000,100
parameters.csv
NAME,VALUE
objective,bin-packing

Solve:

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

=================================
          PackingSolver          
=================================

Problem type
------------
OneDimensional

Instance
--------
Objective:             BinPacking
Number of item types:  52
Number of items:       52
Number of bin types:   1
Number of bins:        100
Total item length:     17898
Total item profit:     17898
Largest item profit:   499
Largest item copies:   1
Largest bin cost:      1000

        Time    Bins  Full waste (%)                         Comment
        ----    ----  --------------                         -------
       0.001      20           10.51                      TS g 0 q 1
       0.001      19            5.80                        SVC it 0
       0.066      18            0.57                         CG n 17

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

Solution
--------
Number of items:  52 / 52 (100%)
Item length:      17898 / 17898 (100%)
Item profit:      17898 / 17898 (100%)
Number of bins:   18 / 100 (18%)
Bin length:       18000 / 100000 (18%)
Bin cost:         18000
Waste:            83
Waste (%):        0.461598
Full waste:       102
Full waste (%):   0.566667
solution.csv
TYPE,ID,COPIES,BIN,X,LX
BIN,0,1,0,0,1000
ITEM,50,1,0,0,491
ITEM,51,1,0,491,499
BIN,0,1,1,0,1000
ITEM,48,1,1,0,479
ITEM,49,1,1,479,487
BIN,0,1,2,0,1000
ITEM,15,1,2,0,277
ITEM,17,1,2,277,283
ITEM,41,1,2,560,439
BIN,0,1,3,0,1000
ITEM,0,1,3,0,193
ITEM,30,1,3,193,373
ITEM,40,1,3,566,433
BIN,0,1,4,0,1000
ITEM,2,1,4,0,199
ITEM,24,1,4,199,337
ITEM,46,1,4,536,463
BIN,0,1,5,0,1000
ITEM,9,1,5,0,241
ITEM,26,1,5,241,349
ITEM,36,1,5,590,409
BIN,0,1,6,0,1000
ITEM,7,1,6,0,233
ITEM,25,1,6,233,347
ITEM,37,1,6,580,419
BIN,0,1,7,0,1000
ITEM,4,1,7,0,223
ITEM,31,1,7,223,379
ITEM,34,1,7,602,397
BIN,0,1,8,0,1000
ITEM,14,1,8,0,271
ITEM,19,1,8,271,307
ITEM,38,1,8,578,421
BIN,0,1,9,0,1000
ITEM,3,1,9,0,211
ITEM,23,1,9,211,331
ITEM,44,1,9,542,457
BIN,0,1,10,0,1000
ITEM,6,1,10,0,229
ITEM,29,1,10,229,367
ITEM,35,1,10,596,401
BIN,0,1,11,0,1000
ITEM,10,1,11,0,251
ITEM,21,1,11,251,313
ITEM,39,1,11,564,431
BIN,0,1,12,0,1000
ITEM,12,1,12,0,263
ITEM,13,1,12,263,269
ITEM,47,1,12,532,467
BIN,0,1,13,0,1000
ITEM,1,1,13,0,197
ITEM,28,1,13,197,359
ITEM,42,1,13,556,443
BIN,0,1,14,0,1000
ITEM,5,1,14,0,227
ITEM,32,1,14,227,383
ITEM,33,1,14,610,389
BIN,0,1,15,0,1000
ITEM,11,1,15,0,257
ITEM,16,1,15,257,281
ITEM,45,1,15,538,461
BIN,0,1,16,0,1000
ITEM,20,1,16,0,311
ITEM,22,1,16,311,317
ITEM,27,1,16,628,353
BIN,0,1,17,0,1000
ITEM,8,1,17,0,239
ITEM,18,1,17,239,293
ITEM,43,1,17,532,449

Visualize:

python3 scripts/visualize_onedimensional.py solution.csv
_images/onedimensional_solution.png

Nesting length

In some cases, when two items are placed consecutively in a bin, the second item might nests with the first one, reducing the effective space it occupies. This length difference is called the nesting length.

The nesting length is specified via the NESTING_LENGTH column in the item CSV file.

_images/onedimensional_nesting_length.jpeg

The stackable crate above illustrates the idea: two of them nested (left) take up less length than twice the length of one alone (right), since the legs of the second crate sink into the one before it.

In the following example, thanks to nesting, all items might fit in a single bin.

Without nesting length

With nesting length
items.csv
X,COPIES
70,8
items.csv
X,COPIES,NESTING_LENGTH
70,8,10
bins.csv
X,COPIES
500,10
bins.csv
X,COPIES
500,10
parameters.csv
NAME,VALUE
objective,bin-packing
parameters.csv
NAME,VALUE
objective,bin-packing

oned_nesting_length_no

oned_nesting_length_yes

Maximum number of items in a bin containing an item of a given type

For each item type, it is possible to define a limit on the number of items in a bin that contains an item of this type. This value is called the maximum stackability of the item type.

The maximum stackability of an item type is specified via the MAXIMUM_STACKABILITY column in the item CSV file.

In the following example, without the maximum stackability constraint, all items fit in 2 bins. In the second case, the first item type has a maximum stackability of 3. Therefore, the first bin of the first case is not valid in the second case; and there is no way to fit all items in 2 bins only.

Without maximum stackability

With maximum stackability
items.csv
X,COPIES
200,3
100,4
items.csv
X,COPIES,MAXIMUM_STACKABILITY
200,3,3
100,4,100
bins.csv
X,COPIES
500,10
bins.csv
X,COPIES
500,10
parameters.csv
NAME,VALUE
objective,bin-packing
parameters.csv
NAME,VALUE
objective,bin-packing

oned_maximum_stackability_no

oned_maximum_stackability_yes

Maximum total weight in a bin

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

In the following example, all items fit in a single bin without the maximum weight limit. In the second case, placing all items in a single bin violates the maximum weight limit. Therefore, 2 bins are necessary to pack all items.

Without maximum weight

With maximum weight
items.csv
X,COPIES,WEIGHT
200,4,100
items.csv
X,COPIES,WEIGHT
200,4,100
bins.csv
X,COPIES
800,10
bins.csv
X,COPIES,MAXIMUM_WEIGHT
800,10,200
parameters.csv
NAME,VALUE
objective,bin-packing
parameters.csv
NAME,VALUE
objective,bin-packing

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

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

oned_maximum_weight_no

oned_maximum_weight_yes

Maximum weight allowed after an item of a given type

Each item type may a have maximum weight allowed for the items packed after it in its bin. This corresponds to the maximum weight that an item can support when they are stacked on each other.

The maximum weight after of an item type is specified via the MAXIMUM_WEIGHT_AFTER column in the item CSV file.

The following example packs 2 copies of a 240-length item (weight 200) and 3 copies of a 160-length item (weight 100) into 500-length bins (bin-packing-with-leftovers objective). Without a limit, the optimal solution uses 2 bins: one with both copies of the 240-length item (480), the other with all 3 copies of the 160-length item (480). Setting MAXIMUM_WEIGHT_AFTER to 150 on the 240-length item only means no more than 150 of weight may follow it in its bin: since another copy of that same item weighs 200, two of them can no longer share a bin, while a 160-length item (weight 100) still can. The optimal solution now uses each of the 2 copies of the 240-length item in its own bin, each paired with one of the 160-length items, and a third bin for the last, unpaired 160-length item.

Without maximum weight after

With maximum weight after
items.csv
X,COPIES,WEIGHT
240,2,200
160,3,100
items.csv
X,COPIES,WEIGHT,MAXIMUM_WEIGHT_AFTER
240,2,200,150
160,3,100,10000
bins.csv
X,COPIES
500,10
bins.csv
X,COPIES
500,10
parameters.csv
NAME,VALUE
objective,bin-packing-with-leftovers
parameters.csv
NAME,VALUE
objective,bin-packing-with-leftovers

oned_maximum_weight_after_no

oned_maximum_weight_after_yes