OneDimensional solver

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

  • Item type / bin type eligibility

Usage

The OneDimensional 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 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:

    • knapsasck

    • 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

Basic example

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.071      18            0.57                         CG n 18

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

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:            65
Waste (%):        0.361855
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,8,1,2,0,239
ITEM,28,1,2,239,359
ITEM,35,1,2,598,401
BIN,0,1,3,0,1000
ITEM,5,1,3,0,227
ITEM,20,1,3,227,311
ITEM,45,1,3,538,461
BIN,0,1,4,0,1000
ITEM,11,1,4,0,257
ITEM,27,1,4,257,353
ITEM,33,1,4,610,389
BIN,0,1,5,0,1000
ITEM,12,1,5,0,263
ITEM,18,1,5,263,293
ITEM,42,1,5,556,443
BIN,0,1,6,0,1000
ITEM,15,1,6,0,277
ITEM,17,1,6,277,283
ITEM,41,1,6,560,439
BIN,0,1,7,0,1000
ITEM,3,1,7,0,211
ITEM,23,1,7,211,331
ITEM,44,1,7,542,457
BIN,0,1,8,0,1000
ITEM,4,1,8,0,223
ITEM,21,1,8,223,313
ITEM,46,1,8,536,463
BIN,0,1,9,0,1000
ITEM,2,1,9,0,199
ITEM,29,1,9,199,367
ITEM,40,1,9,566,433
BIN,0,1,10,0,1000
ITEM,6,1,10,0,229
ITEM,30,1,10,229,373
ITEM,34,1,10,602,397
BIN,0,1,11,0,1000
ITEM,0,1,11,0,193
ITEM,24,1,11,193,337
ITEM,47,1,11,530,467
BIN,0,1,12,0,1000
ITEM,10,1,12,0,251
ITEM,22,1,12,251,317
ITEM,39,1,12,568,431
BIN,0,1,13,0,1000
ITEM,13,1,13,0,269
ITEM,16,1,13,269,281
ITEM,43,1,13,550,449
BIN,0,1,14,0,1000
ITEM,9,1,14,0,241
ITEM,26,1,14,241,349
ITEM,36,1,14,590,409
BIN,0,1,15,0,1000
ITEM,14,1,15,0,271
ITEM,19,1,15,271,307
ITEM,38,1,15,578,421
BIN,0,1,16,0,1000
ITEM,7,1,16,0,233
ITEM,31,1,16,233,379
ITEM,32,1,16,612,383
BIN,0,1,17,0,1000
ITEM,1,1,17,0,197
ITEM,25,1,17,197,347
ITEM,37,1,17,544,419

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.

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 second 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
100,4
200,3
items.csv
X,COPIES,MAXIMUM_STACKABILITY
100,4,100
200,3,3
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 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 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.

In the following examples, in the first, the first item type has a tight maximum weight after value; while in the second case, it’s the second item type that has a tight maximum weight after value. Therefore in the first case, the first item type is placed first; while in the second case, it’s the second item type that is placed first.

Without maximum weight after

With maximum weight after
items.csv
X,WEIGHT,MAXIMUM_WEIGHT_AFTER
200,400,100
100,200,10000
items.csv
X,WEIGHT,MAXIMUM_WEIGHT_AFTER
200,400,10000
100,200,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_weight_after_no

oned_maximum_weight_after_yes

Item type / bin type eligibility