One dimensional - big number of items - interesting test case

[lafar6502]

Hi, so i thought my problem sizes are small, but just found something exceeding some of packing solver's data limits. There was an order for few hundred of roller shutters - it did not end up being produced, and such orders are very rare, but still i wanted to see what would happen when trying to do optimization. Roller shutter is bult from small aluminium lamellas (strips) joined together into a roller blind - and one roller can contain a hundred or more such lamellas, all cut to the same length. But the order had few hundred of such rollers, so number of lamellas went into big thousands.

It's still not that difficult packing problem because all these lamellas are cut to the same size, but the numbers exceed some variable limits in packing solver. However, the calculation finished and there was no error - solution was found and it was correct. Just the output on the console was a bit suspicious, and return value from packing solver .exe indicated some error. So i think there might be some potential problems hiding in the code. This case is not very practical, and if such order were to be produced it would have to be split into more manageable parts, but at least makes a nice test case.

Start job 58471|9006: --verbosity-level 9 --objective variable-sized-bin-packing -__debug__- --items C:\Users\rafal\AppData\Local\Temp\items_fc2fb4bc794e418db70f8a6788558c39.csv --bins C:\Users\rafal\AppData\Local\Temp\bins_fc2fb4bc794e418db70f8a6788558c39.csv -c C:\Users\rafal\AppData\Local\Temp\solution_fc2fb4bc794e418db70f8a6788558c39.csv --optimization-mode not-anytime --not-anytime-tree-search-queue-size 768 --not-anytime-sequential-single-knapsack-subproblem-queue-size 768 --not-anytime-sequential-value-correction-number-of-iterations 96 --not-anytime-dichotomic-search-subproblem-queue-size 768
ITEMS:
ID,X,COPIES,NESTING_LENGTH
0,837,820,-4
1,1587,26640,-4
2,1987,372,-4
3,2487,15602,-4
4,727,40,-4
5,1627,40,-4
6,747,40,-4

BINS:
ID,X,COST,COPIES
0,6000,6000,43554

Job 58471|9006 done. result -1073741571. Time 82317 ms
STDOUT:
=================================
          PackingSolver          
=================================

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

Instance
--------
Objective:             VariableSizedBinPacking
Number of item types:  7
Number of items:       -21982
Number of bin types:   1
Number of bins:        43554

    Bin type      Length    Max wght        Cost      Copies  Copies min
    --------      ------    --------        ----      ------  ----------
           0        6000         inf        6000       43554           0

   Item type      Length      Weight   MaxWgtAft     MaxStck      Profit      Copies
   ---------      ------      ------   ---------     -------      ------      ------
           0         837           0         inf       32767         837         820
           1        1587           0         inf       32767        1587       26640
           2        1987           0         inf       32767        1987         372
           3        2487           0         inf       32767        2487       15602
           4         727           0         inf       32767         727          40
           5        1627           0         inf       32767        1627          40
           6         747           0         inf       32767         747          40

        Time          Cost  # bins  Full waste (%)                         Comment
        ----          ----  ------  --------------                         -------

SOLUTION:
TYPE,ID,COPIES,BIN,X,LX
BIN,0,13320,0,0,6000
ITEM,3,13320,0,0,2487
ITEM,1,13320,0,2491,1587
ITEM,1,13320,0,4082,1587
BIN,0,231,1,0,6000
ITEM,3,231,1,0,2487
ITEM,3,231,1,2491,2487
BIN,0,124,2,0,6000
ITEM,2,124,2,0,1987
ITEM,2,124,2,1991,1987
ITEM,2,124,2,3982,1987
BIN,0,820,3,0,6000
ITEM,0,820,3,0,837
ITEM,3,820,3,841,2487
ITEM,3,820,3,3332,2487
BIN,0,40,4,0,6000
ITEM,6,40,4,0,747
ITEM,3,40,4,751,2487
ITEM,3,40,4,3242,2487
BIN,0,40,5,0,6000
ITEM,3,40,5,0,2487
ITEM,3,40,5,2491,2487
ITEM,4,40,5,4982,727
BIN,0,20,6,0,6000
ITEM,3,20,6,0,2487
ITEM,5,20,6,2491,1627
ITEM,5,20,6,4122,1627

[fontanf]

Hi,

I updated the code such that the number of items is now stored on a 32 bit integer. It's nice to see that even with 50K items, the solver still finds a probably near-optimal solution in less than 0.1s.

Be careful, I also updated the build system. It's not using Bazel anymore. It's now using CMake

[lafar6502]

Thanks, will give it a try soon But it wasn't 0.1s in my test - it was 82 seconds. I have increased all queue-size search effort parameters threefold just to get some idea of how it affects the running time - it was a bit long but not bad at all. Such problem sizes aren't a common thing but if it happens - packing solver should be able to deal with it.

And this case - cutting lamellas for roller shutters, is especially nice with optimization. I mean it didnt seem very useful as these lamellas are cheap - lots of them need to be cut, and the cutting guy just went one by one - first cut 500 lamellas of length X, then 100 of length Y, then 200 of length Z... Sometimes lots of scrap were left but it's cheap so who cares. And nobody sane would plan the cutting ahead with so many pieces. But packing solver makes the plan for entire order, and it shines when there are multiple different lengths on the same order - then it will mix them in quite sophisticated ways (like in the example above). The more different lengths, the better the result - sometimes it's quite astonishing for the cutting guys to see almost perfect use of the material. Still, not that much value in scrap saved, but the plan is just awesome to look at.

BTW it seems that packing solver is doing a better job now with grouping the same patterns - did you make some improvements in this area?

---

some things i noticed with cmake build it did not succeed, the third 'install' step would fail - some of the .exes weren't found is it maybe some issue with path length/directory nesting too deep?

  Building Custom Rule D:/devs/packingsolver/build/_deps/optimizationtools-src/src/graph/CMakeLists.txt
C:\Program Files\Microsoft Visual Studio\2022\Community\MSBuild\Current\Bin\amd64\Microsoft.Common.CurrentVersion.targe
ts(392,25): error MSB4184: The expression "[MSBuild]::NormalizePath(D:\devs\packingsolver\build\_deps\knapsacksolver-bu
ild\src\multiple_choice_subset_sum\algorithms, KnapsackSolver_multiple_choice_subset_sum_dynamic_programming_bellman.di
r\Release\, KnapsackSolver_multiple_choice_subset_sum_dynamic_programming_bellman.vcxproj.CopyComplete)" cannot be eval
uated. Path: D:\devs\packingsolver\build\_deps\knapsacksolver-build\src\multiple_choice_subset_sum\algorithms\KnapsackS
olver_multiple_choice_subset_sum_dynamic_programming_bellman.dir\Release\KnapsackSolver_multiple_choice_subset_sum_dyna
mic_programming_bellman.vcxproj.CopyComplete exceeds the OS max path limit. The fully qualified file name must be less
than 260 characters. [D:\devs\packingsolver\build\_deps\knapsacksolver-build\src\multiple_choice_subset_sum\algorithms\
KnapsackSolver_multiple_choice_subset_sum_dynamic_programming_bellman.vcxproj]

  Building Custom Rule D:/devs/packingsolver/build/_deps/googletest-src/googlemock/CMakeLists.txt
  gtest-all.cc
  timer.cpp
C:\Program Files\Microsoft Visual Studio\2022\Community\MSBuild\Current\Bin\amd64\Microsoft.Common.CurrentVersion.targe
ts(392,25): error MSB4184: The expression "[MSBuild]::NormalizePath(D:\devs\packingsolver\build\_deps\knapsacksolver-bu
ild\src\multiple_choice_subset_sum\algorithms, KnapsackSolver_multiple_choice_subset_sum_dynamic_programming_bellman.di
r\Release\, KnapsackSolver_multiple_choice_subset_sum_dynamic_programming_bellman.vcxproj.CopyComplete)" cannot be eval
uated. Path: D:\devs\packingsolver\build\_deps\knapsacksolver-build\src\multiple_choice_subset_sum\algorithms\KnapsackS
olver_multiple_choice_subset_sum_dynamic_programming_bellman.dir\Release\KnapsackSolver_multiple_choice_subset_sum_dyna
mic_programming_bellman.vcxproj.CopyComplete exceeds the OS max path limit. The fully qualified file name must be less
than 260 characters. [D:\devs\packingsolver\build\_deps\knapsacksolver-build\src\multiple_choice_subset_sum\algorithms\
KnapsackSolver_multiple_choice_subset_sum_dynamic_programming_bellman.vcxproj]

  boost_program_options.vcxproj -> D:\devs\packingsolver\build\_deps\boost-build\libs\program_options\Release\libboost_
  program_options-vc143-mt-s-x64-1_84.lib
  generator.cpp
C:\Program Files\Microsoft Visual Studio\2022\Community\MSBuild\Microsoft\VC\v170\Microsoft.CppBuild.targets(382,5): er
ror MSB3491: Could not write lines to file "TreeSearchSolver_example_permutation_flowshop_scheduling_makespan_main.dir\
Release\TreeSear.26F0FEB3.tlog\TreeSearchSolver_example_permutation_flowshop_scheduling_makespan_main.lastbuildstate".
Path: TreeSearchSolver_example_permutation_flowshop_scheduling_makespan_main.dir\Release\TreeSear.26F0FEB3.tlog\TreeSea
rchSolver_example_permutation_flowshop_scheduling_makespan_main.lastbuildstate exceeds the OS max path limit. The fully
 qualified file name must be less than 260 characters. [D:\devs\packingsolver\build\_deps\treesearchsolver-build\src\ex
amples\TreeSearchSolver_example_permutation_flowshop_scheduling_makespan_main.vcxproj]

[fontanf]

The solution comes from the column generation algorithm:

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

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

Instance
--------
Objective:             VariableSizedBinPacking
Number of item types:  7
Number of items:       43554
Number of bin types:   1
Number of bins:        43554

    Bin type      Length    Max wght        Cost      Copies  Copies min
    --------      ------    --------        ----      ------  ----------
           0        6000         inf        6000       43554           0

   Item type      Length      Weight   MaxWgtAft     MaxStck      Profit      Copies
   ---------      ------      ------   ---------     -------      ------      ------
           0         837           0         inf  2147483647         837         820
           1        1587           0         inf  2147483647        1587       26640
           2        1987           0         inf  2147483647        1987         372
           3        2487           0         inf  2147483647        2487       15602
           4         727           0         inf  2147483647         727          40
           5        1627           0         inf  2147483647        1627          40
           6         747           0         inf  2147483647         747          40

        Time          Cost  # bins  Full waste (%)                         Comment
        ----          ----  ------  --------------                         -------
       0.006    8.8338e+07   14723            6.46                        SVC it 0
       0.010     8.769e+07   14615            5.77                        SVC it 1
       0.017    8.7624e+07   14604            5.70                        SVC it 3
       0.021    8.7612e+07   14602            5.69                        SVC it 4
       0.088     8.757e+07   14595            5.64                          CG n 1

Even if you tweak the --column-generation-subproblem-queue-size option, I would find surprising to get a running time of more than 60s.

Thanks for the insights, it's interesting and useful to understand how the optimization tools are used in practice.

BTW it seems that packing solver is doing a better job now with grouping the same patterns - did you make some improvements in this area?

Not directly. It might be due to changes in the column generation algorithm and a better algorithm selection that is more likely to run algorithms working on patterns when the solution will likely contain some patterns many times. It might still happen to get multiple times identical pattern in a solution.

[lafar6502]

Yes, i thought you might like to know a little about how it's used. I'm also learning, and production people too - there's no cookbook for how to organize production so everyone is experimenting. Even if the optimization doesn't solve all the problems, it introduces some order and discipline - there are calculations and plans to stick to, and if they're not good - they will be gradually improved. People will adjust their way of working to make better use of tools available (when they see the tool as reliable and helpful). So i think the value of optimizer is not only in better use of materials available, but it contributes to better organization of the whole process. And regarding the build problems - i'm using c++ compiler coming with visual studio 2022 community edition. Are you using something different? I suspect there's some problem in Microsoft tools, maybe different versions work better.

[fontanf]

Regarding the compilation issue, can you try enabling long paths? https://learn.microsoft.com/en-us/windows/win32/fileio/maximum-file-path-limitation?tabs=registry#enable-long-paths-in-windows-10-version-1607-and-later

[lafar6502]

Thanks. Yesterday i found this tip but it didnt seem to help (and i couldn't figure out what 'manifest changes' these people were talking about - so i did not do anything with the manifest part). But miraculously today it built. And in this version my test problem runs really fast - 0.4 seconds instead of a minute. Great!

[fontanf]

I think only the first point of the page is necessary. I'm glad that it works. I close the issue.