Performance of packing problems #3177
Replies: 6 comments 3 replies
-
|
Actually, the no_overlap_2d propagator is poor. |
Beta Was this translation helpful? Give feedback.
-
|
I'm looking forward to when you do find the time and will rerun the comparisons then. |
Beta Was this translation helpful? Give feedback.
-
|
Update for 9.4.1874 A lot of work has been done on scheduling problems. Among others, the new parameter use_energetic_reasoning_in_no_overlap_2d is available and use_cumulative_in_no_overlap_2d has been renamed to use_timetabling_in_no_overlap_2d in 1605046, so I'll update the list from above:
I tested the following variants here:
For these two instances, it looks like a great improvement over 9.3. In ba15d31, Is the Diophantine solver from 0b0f33b (not used in the tests as it came after the release of 9.4.1874) similar to a subset sum solver? Looks like it's somewhat related. |
Beta Was this translation helpful? Give feedback.
-
|
Thanks.
1) are you running with multiple workers ?
2) the diophantine presolve simplifies equations like bin_num_1 * var1 +
big_num_2 * var2 == small_cst
Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53
00
Le ven. 19 août 2022 à 13:01, Leopold Kuttner ***@***.***> a
écrit :
… Update for 9.4.1874
A lot of work has been done on scheduling problems. Among others, the new
parameter use_energetic_reasoning_in_no_overlap_2d is available and
use_cumulative_in_no_overlap_2d has been renamed to
use_timetabling_in_no_overlap_2d in 1605046
<1605046>,
so I'll update the list from above:
1. Preprocessing techniques of CCM07
2. NoOverlap2D
3. Cumulative constraints (AddCumulative())
4. Disjunctive constraints in cumulative constraints
(use_disjunctive_constraint_in_cumulative)
5. Time table edge finding (use_timetabling_in_no_overlap_2d)
6. Time table edge finding
(use_timetable_edge_finding_in_cumulative_constraint)
7. Energetic reasoning (use_overload_checker_in_cumulative)
8. Energetic reasoning (use_energetic_reasoning_in_no_overlap_2d)
9. Pruning the search tree by solving subset sum problems (no
equivalent in ortools!?)
I tested the following variants here
<https://github.com/ktnr/BinPacking2D/blob/730a1e6409023eea557640bbbb6ca64803d14bd5/experiments/ComparisonCJCM.py>
:
- Default: 1-4
- Default-V1: 1-4, 8
- Default-V2: 1-4, 5, 8
- Default-V3: 1-4, 5, 8, use_dual_scheduling_heuristics = False
- Default-V4: 1-4, use_dual_scheduling_heuristics = False
- Basic: 1-6
- Full: 1-8
Variant E00N23 E00X23
CJCM08-Basic 70s 160s
CJCM08-All 1s 6s
ortools-Default 123s 5010s
ortools-Default-V1 100s 2812s
ortools-Default-V2 75s 6018s
ortools-Default-V3 58s 2761s
ortools-Default-V4 54s 2525s
ortools-Basic 643s 10915s
ortools-All 480s 11392s
For these two instances, it looks like a great improvement over 9.3. In
ba15d31
<ba15d31>,
use_dual_scheduling_heuristics was enabled by default, so I disabled it
in two variants. Note that #3407
<#3407> is still unresolved at
the time of testing. More hard instances for testing can be found here
<https://github.com/ktnr/BinPacking2D/tree/master/data/input/OPP/BPP-Subproblems>
.
Is the Diophantine solver from 0b0f33b
<0b0f33b>
(not used in the tests as it came after the release of 9.4.1874) similar to
a subset sum solver? Looks like it's somewhat related.
—
Reply to this email directly, view it on GitHub
<#3177 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACUPL3LOI2TCQZEQ5GTKA4LVZ5SQ5ANCNFSM5Q3BFV4Q>
.
You are receiving this because you commented.Message ID:
***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
|
Yes, 8 Threads. |
Beta Was this translation helpful? Give feedback.
-
|
if you have the hardware, you can try 16 |
Beta Was this translation helpful? Give feedback.
-
|
On my workstation (2018), with 16 workers (default settings), I solve E00N23 in 23s, and E00X23 in 630s. Still far from your code. |
Beta Was this translation helpful? Give feedback.
-
|
Update for 9.5.2237
|
Beta Was this translation helpful? Give feedback.
-
|
Thanks for following up. |
Beta Was this translation helpful? Give feedback.
-
I have observed considerable performance improvements for 2D packing problems since 9.2. That's great, thanks! I have compared the performance against the results reported in CJCM08 and obtained surprising results on the only two hard instances therein: E00N23, E00X23.
CJCM08 uses the following constraints/propagations, most of which have an equivalent in ortools:
The "Basic" row uses: 1-6. The "All" row uses all of the above. The "Default" row uses ortools default parameters. The runtimes are:
Note that the numbers in the CJCM08 rows are taken directly from the tables in the paper, i.e., run with a single thread on hardware from 2008. Unfortunately, the CP solver that was used is not specified in the paper. The ortools numbers are obtained with 8 threads on current hardware with version 9.3.10459. Here are the proto models:
Alternatively, you can run the comparison with different parameters yourself using this repo.
Do you have an intuition what might explain that performance difference?
CJCM08 also highlight the effectiveness of another solution method with sweep propagations by BCT06 for feasible instances. But, from Table 3 it seems to be less effective (maybe even counterproductive?) for infeasible instances.
Does ortools use something like sweep propagations? If so, can it be disabled via a parameter? There are some references to "sweep" in resource.cc, diffn_util.cc, timetable.h/cc.
Beta Was this translation helpful? Give feedback.
All reactions