Optimization modes¶
PackingSolver provides 5 optimization modes:
Anytime
Not-anytime
Not-anytime deterministic
Not-anytime sequential
Exact
Anytime mode¶
In anytime mode, PackingSolver tries to quickly get a solution and looks for improving ones as long as a stopping criterion is not met. This mode is typically meant to be used with a time limit.
The anytime mode uses multiple threads, in general about 8 threads.
In anytime mode, PackingSolver may still stop before any stopping criterion is met if it proved it would not be able to improve the current solution further.
Note
Anytime mode: let the solver find the best possible solution within X seconds.
The optimization mode is a parameter of the solver:
In the Parameters section, choose the Optimization mode, and the Time limit.
With the command-line solver: --optimization-mode anytime --time-limit 15.
parameters.optimization_mode = psr.OptimizationMode.Anytime, with parameters = psr.OptimizeParameters().
parameters.optimization_mode = OptimizationMode::Anytime;, with OptimizeParameters parameters;.
Example
Open the example in the online solver: Optimization modes: 40 items.
{
"objective": "bin-packing-with-leftovers",
"bin_types": [
{"x": 1000, "y": 500, "copies": 20}
],
"item_types": [
{"x": 100, "y": 50},
{"x": 103, "y": 53},
{"x": 106, "y": 56},
{"x": 109, "y": 59},
{"x": 112, "y": 62},
{"x": 115, "y": 65},
{"x": 118, "y": 68},
{"x": 121, "y": 71},
{"x": 124, "y": 74},
{"x": 127, "y": 77},
{"x": 130, "y": 80},
{"x": 133, "y": 83},
{"x": 136, "y": 86},
{"x": 139, "y": 89},
{"x": 142, "y": 92},
{"x": 145, "y": 95},
{"x": 148, "y": 98},
{"x": 151, "y": 101},
{"x": 154, "y": 104},
{"x": 157, "y": 107},
{"x": 160, "y": 110},
{"x": 163, "y": 113},
{"x": 166, "y": 116},
{"x": 169, "y": 119},
{"x": 172, "y": 122},
{"x": 175, "y": 125},
{"x": 178, "y": 128},
{"x": 181, "y": 131},
{"x": 184, "y": 134},
{"x": 187, "y": 137},
{"x": 190, "y": 140},
{"x": 193, "y": 143},
{"x": 196, "y": 146},
{"x": 199, "y": 149},
{"x": 202, "y": 152},
{"x": 205, "y": 155},
{"x": 208, "y": 158},
{"x": 211, "y": 161},
{"x": 214, "y": 164},
{"x": 217, "y": 167}
]
}
import packingsolver.rectangle as psr
instance_builder = psr.InstanceBuilder()
instance_builder.set_objective(psr.Objective.BinPackingWithLeftovers)
instance_builder.add_bin_type(1000, 500, copies=20)
instance_builder.add_item_type(100, 50)
instance_builder.add_item_type(103, 53)
instance_builder.add_item_type(106, 56)
instance_builder.add_item_type(109, 59)
instance_builder.add_item_type(112, 62)
instance_builder.add_item_type(115, 65)
instance_builder.add_item_type(118, 68)
instance_builder.add_item_type(121, 71)
instance_builder.add_item_type(124, 74)
instance_builder.add_item_type(127, 77)
instance_builder.add_item_type(130, 80)
instance_builder.add_item_type(133, 83)
instance_builder.add_item_type(136, 86)
instance_builder.add_item_type(139, 89)
instance_builder.add_item_type(142, 92)
instance_builder.add_item_type(145, 95)
instance_builder.add_item_type(148, 98)
instance_builder.add_item_type(151, 101)
instance_builder.add_item_type(154, 104)
instance_builder.add_item_type(157, 107)
instance_builder.add_item_type(160, 110)
instance_builder.add_item_type(163, 113)
instance_builder.add_item_type(166, 116)
instance_builder.add_item_type(169, 119)
instance_builder.add_item_type(172, 122)
instance_builder.add_item_type(175, 125)
instance_builder.add_item_type(178, 128)
instance_builder.add_item_type(181, 131)
instance_builder.add_item_type(184, 134)
instance_builder.add_item_type(187, 137)
instance_builder.add_item_type(190, 140)
instance_builder.add_item_type(193, 143)
instance_builder.add_item_type(196, 146)
instance_builder.add_item_type(199, 149)
instance_builder.add_item_type(202, 152)
instance_builder.add_item_type(205, 155)
instance_builder.add_item_type(208, 158)
instance_builder.add_item_type(211, 161)
instance_builder.add_item_type(214, 164)
instance_builder.add_item_type(217, 167)
instance = instance_builder.build()
#include "packingsolver/rectangle/instance_builder.hpp"
using namespace packingsolver;
using namespace packingsolver::rectangle;
InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPackingWithLeftovers);
BinTypeId bin_type_id = instance_builder.add_bin_type(1000, 500);
instance_builder.set_bin_type_copies(bin_type_id, 20);
instance_builder.add_item_type(100, 50);
instance_builder.add_item_type(103, 53);
instance_builder.add_item_type(106, 56);
instance_builder.add_item_type(109, 59);
instance_builder.add_item_type(112, 62);
instance_builder.add_item_type(115, 65);
instance_builder.add_item_type(118, 68);
instance_builder.add_item_type(121, 71);
instance_builder.add_item_type(124, 74);
instance_builder.add_item_type(127, 77);
instance_builder.add_item_type(130, 80);
instance_builder.add_item_type(133, 83);
instance_builder.add_item_type(136, 86);
instance_builder.add_item_type(139, 89);
instance_builder.add_item_type(142, 92);
instance_builder.add_item_type(145, 95);
instance_builder.add_item_type(148, 98);
instance_builder.add_item_type(151, 101);
instance_builder.add_item_type(154, 104);
instance_builder.add_item_type(157, 107);
instance_builder.add_item_type(160, 110);
instance_builder.add_item_type(163, 113);
instance_builder.add_item_type(166, 116);
instance_builder.add_item_type(169, 119);
instance_builder.add_item_type(172, 122);
instance_builder.add_item_type(175, 125);
instance_builder.add_item_type(178, 128);
instance_builder.add_item_type(181, 131);
instance_builder.add_item_type(184, 134);
instance_builder.add_item_type(187, 137);
instance_builder.add_item_type(190, 140);
instance_builder.add_item_type(193, 143);
instance_builder.add_item_type(196, 146);
instance_builder.add_item_type(199, 149);
instance_builder.add_item_type(202, 152);
instance_builder.add_item_type(205, 155);
instance_builder.add_item_type(208, 158);
instance_builder.add_item_type(211, 161);
instance_builder.add_item_type(214, 164);
instance_builder.add_item_type(217, 167);
Instance instance = instance_builder.build();
packingsolver_rectangle \
--input instance.json \
--certificate solution_rectangle.csv \
--optimization-mode anytime \
--time-limit 15
=================================
PackingSolver
=================================
Problem type
------------
Rectangle
Instance
--------
Objective: BinPackingWithLeftovers
Number of item types: 40
Number of items: 40
Number of bin types: 1
Number of bins: 20
Number of groups: 1
Number of defects: 0
Unloading constraint: None
Total item area: 735860
Total item width: 6340
Total item height: 4340
Smallest item width: 50
Smallest item height: 50
Total item weight: 0
Maximum item copies: 1
Total bin area: 10000000
Total bin weight: 0
Maximum bin cost: 500000
Time # bins Leftover Comment
---- ------ -------- -------
0.005 2 166300 TS g 1 d X q 1
0.005 2 189800 TS g 1 d X q 1
0.018 2 212864 SSK it 0
0.070 2 216608 TS g 0 d X q 6
0.229 2 218000 TS g 0 d X q 19
0.229 2 221384 TS g 0 d X q 19
0.232 2 223988 TS g 0 d X q 19
0.808 2 224000 TS g 0 d X q 63
0.808 2 225000 TS g 0 d X q 63
0.815 2 226500 TS g 0 d X q 63
1.666 2 230500 SSK it 6
12.251 2 241518 SSK it 9
14.221 2 243015 TS g 1 d X q 1066
Final statistics
----------------
Time (s): 15.0054
Solution
--------
Number of items: 40 / 40 (100%)
Item area: 735860 / 735860 (100%)
Item weight: 0 / 0 (-nan%)
Item profit: 735860 / 735860 (100%)
Number of bins: 2 / 20 (10%)
Bin area: 1000000 / 10000000 (10%)
Bin weight: 0 / 0 (-nan%)
Bin cost: 1e+06
Waste: 21125
Waste (%): 2.79068
Full waste: 264140
Full waste (%): 26.414
Area load: 0.073586
Weight load: -nan
X max: 515
Y max: 499
Leftover value: 243015
Non-anytime modes¶
In non-anytime modes, PackingSolver stops by itself. These modes are meant to always return solutions of similar quality even with instances of different sizes. The resolution time will be smaller for smaller instances and larger for larger instances.
Non-anytime modes are more complex to use, since defining accurately the desired quality requires tuning the algorithms parameters (for now).
Note
Non-anytime mode: let the solver find a solution of a given quality
There are 3 non-anytime modes. The not-anytime mode uses multiple threads, typically about 8 threads. The not-anytime-deterministic mode uses multiple threads as well, but the result doesn’t depend on the order in which the threads find their solutions. The not-anytime-sequential mode uses a single thread.
The not-anytime-deterministic and not-anytime-sequential modes are deterministic. The other optimization modes may not be deterministic even if they should be most of the time.
Here, deterministic means that the same input gives the same result when PackingSolver is run again with the same build on the same machine: same operating system, same compiler and standard library, same versions. The result may differ on another platform or with another standard library, since, for example, the order of elements that compare equal when sorting, the iteration order of hash containers and the last bits of floating-point computations may differ.
Example
Same input as above. The solver terminates after 35 seconds.
packingsolver_rectangle \
--input instance.json \
--certificate solution_rectangle.csv \
--optimization-mode not-anytime
=================================
PackingSolver
=================================
Problem type
------------
Rectangle
Instance
--------
Objective: BinPackingWithLeftovers
Number of item types: 40
Number of items: 40
Number of bin types: 1
Number of bins: 20
Number of groups: 1
Number of defects: 0
Unloading constraint: None
Total item area: 735860
Total item width: 6340
Total item height: 4340
Smallest item width: 50
Smallest item height: 50
Total item weight: 0
Maximum item copies: 1
Total bin area: 10000000
Total bin weight: 0
Maximum bin cost: 500000
Time # bins Leftover Comment
---- ------ -------- -------
17.920 2 234000 TS g 0 d X
17.921 2 241518 TS g 1 d X
28.537 2 246020 SSK it 11
Final statistics
----------------
Time (s): 34.1616
Solution
--------
Number of items: 40 / 40 (100%)
Item area: 735860 / 735860 (100%)
Item weight: 0 / 0 (-nan%)
Item profit: 735860 / 735860 (100%)
Number of bins: 2 / 20 (10%)
Bin area: 1000000 / 10000000 (10%)
Bin weight: 0 / 0 (-nan%)
Bin cost: 1e+06
Waste: 18120
Waste (%): 2.40325
Full waste: 264140
Full waste (%): 26.414
Area load: 0.073586
Weight load: -nan
X max: 510
Y max: 498
Leftover value: 246020
Now if we remove half of the items, the solver terminates after 22 seconds.
Open the example in the online solver: Optimization modes: 20 items.
{
"objective": "bin-packing-with-leftovers",
"bin_types": [
{"x": 1000, "y": 500, "copies": 20}
],
"item_types": [
{"x": 100, "y": 50},
{"x": 106, "y": 56},
{"x": 112, "y": 62},
{"x": 118, "y": 68},
{"x": 124, "y": 74},
{"x": 130, "y": 80},
{"x": 136, "y": 86},
{"x": 142, "y": 92},
{"x": 148, "y": 98},
{"x": 154, "y": 104},
{"x": 160, "y": 110},
{"x": 166, "y": 116},
{"x": 172, "y": 122},
{"x": 178, "y": 128},
{"x": 184, "y": 134},
{"x": 190, "y": 140},
{"x": 196, "y": 146},
{"x": 202, "y": 152},
{"x": 208, "y": 158},
{"x": 214, "y": 164}
]
}
import packingsolver.rectangle as psr
instance_builder = psr.InstanceBuilder()
instance_builder.set_objective(psr.Objective.BinPackingWithLeftovers)
instance_builder.add_bin_type(1000, 500, copies=20)
instance_builder.add_item_type(100, 50)
instance_builder.add_item_type(106, 56)
instance_builder.add_item_type(112, 62)
instance_builder.add_item_type(118, 68)
instance_builder.add_item_type(124, 74)
instance_builder.add_item_type(130, 80)
instance_builder.add_item_type(136, 86)
instance_builder.add_item_type(142, 92)
instance_builder.add_item_type(148, 98)
instance_builder.add_item_type(154, 104)
instance_builder.add_item_type(160, 110)
instance_builder.add_item_type(166, 116)
instance_builder.add_item_type(172, 122)
instance_builder.add_item_type(178, 128)
instance_builder.add_item_type(184, 134)
instance_builder.add_item_type(190, 140)
instance_builder.add_item_type(196, 146)
instance_builder.add_item_type(202, 152)
instance_builder.add_item_type(208, 158)
instance_builder.add_item_type(214, 164)
instance = instance_builder.build()
#include "packingsolver/rectangle/instance_builder.hpp"
using namespace packingsolver;
using namespace packingsolver::rectangle;
InstanceBuilder instance_builder;
instance_builder.set_objective(Objective::BinPackingWithLeftovers);
BinTypeId bin_type_id = instance_builder.add_bin_type(1000, 500);
instance_builder.set_bin_type_copies(bin_type_id, 20);
instance_builder.add_item_type(100, 50);
instance_builder.add_item_type(106, 56);
instance_builder.add_item_type(112, 62);
instance_builder.add_item_type(118, 68);
instance_builder.add_item_type(124, 74);
instance_builder.add_item_type(130, 80);
instance_builder.add_item_type(136, 86);
instance_builder.add_item_type(142, 92);
instance_builder.add_item_type(148, 98);
instance_builder.add_item_type(154, 104);
instance_builder.add_item_type(160, 110);
instance_builder.add_item_type(166, 116);
instance_builder.add_item_type(172, 122);
instance_builder.add_item_type(178, 128);
instance_builder.add_item_type(184, 134);
instance_builder.add_item_type(190, 140);
instance_builder.add_item_type(196, 146);
instance_builder.add_item_type(202, 152);
instance_builder.add_item_type(208, 158);
instance_builder.add_item_type(214, 164);
Instance instance = instance_builder.build();
packingsolver_rectangle \
--input instance.json \
--certificate solution_rectangle.csv \
--optimization-mode not-anytime
=================================
PackingSolver
=================================
Problem type
------------
Rectangle
Instance
--------
Objective: BinPackingWithLeftovers
Number of item types: 20
Number of items: 20
Number of bin types: 1
Number of bins: 20
Number of groups: 1
Number of defects: 0
Unloading constraint: None
Total item area: 359920
Total item width: 3140
Total item height: 2140
Smallest item width: 50
Smallest item height: 50
Total item weight: 0
Maximum item copies: 1
Total bin area: 10000000
Total bin weight: 0
Maximum bin cost: 500000
Time # bins Leftover Comment
---- ------ -------- -------
5.982 1 131000 TS g 0 d X
Final statistics
----------------
Time (s): 22.0075
Solution
--------
Number of items: 20 / 20 (100%)
Item area: 359920 / 359920 (100%)
Item weight: 0 / 0 (-nan%)
Item profit: 359920 / 359920 (100%)
Number of bins: 1 / 20 (5%)
Bin area: 500000 / 10000000 (5%)
Bin weight: 0 / 0 (-nan%)
Bin cost: 500000
Waste: 9080
Waste (%): 2.4607
Full waste: 140080
Full waste (%): 28.016
Area load: 0.035992
Weight load: -nan
X max: 738
Y max: 500
Leftover value: 131000
Exact mode¶
The exact mode is similar to the anytime mode, but it is aimed at proving the optimality of the solution rather than at finding good solutions quickly. It is mainly meant for research purposes.
In exact mode, the subproblems whose result a bound relies on are also solved in exact mode. For example, the master problem and the subproblems of the Benders decomposition, and the pricing subproblems solved to compute a dual bound in the column generation.
packingsolver_rectangle \
--input instance.json \
--certificate solution_rectangle.csv \
--optimization-mode exact