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

  • Item types

    • Nesting length

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

    • Maximum weight allowed after an item of a given type

  • Bin types

    • Maximum weight

  • Item type / bin type eligibility

Basic 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

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

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

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

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

Item type / bin type eligibility