search

fontanf / packingsolver

A solver for (geometrical) packing problems
MIT License
89 stars 14 forks source link

Sometimes optimization produces no result - time limit exceeded? Running packing solver in parallel. #15

Closed lafar6502 closed 6 months ago

lafar6502 commented 6 months ago

Hi, i have another problem with one-dimensional. Sometimes it doesn't produce a result at all (the solution file is empty). But this happens only in production server. The same test case isolated and checked separately - produces a correct solution file, each time, no problem at all. So i can't provide a good test case for you.

The production server runs the optimization tasks in parallel (because a production order contains several types of profiles to be cut, so each profile type is a separate job for packing solver). In my case it was 13 optimization tasks to be calculated. I could see on the process list that 3 or 4 instances of packing solver .exe were running in parallel and the CPU was used in 100%.

So my assumption is that the CPU is exhausted by packing solver and the time limit is reached before the optimizer finds a solution. Is it correct / possible?

Below is the console output in one of such cases - you can see that solution has 0 items in it. Commandline arguments are at the bottom. You can see i'm using time limit of 30 seconds (-t 30). But the same thing happened with time limit of 10 seconds, 20 seconds. Finally i got it to calculate at time limit 60 seconds, but the whole job took quite a long time (packing solver spends more time calculating when the time limit is longer)

My questions to this case

  1. The time limit - is it possible that a solution is not found within packingsolver's time limit when the CPU is saturated with other work? I mean, the success depends on activity of other processes on the machine?
  2. Is it possible to tell (by checking console output, for example) that the solution wasn't found because time limit was reached? Would be nice for my program to know that the solution may exist but more time is needed.
  3. What should be the strategy here - increase the time limit for all packing solver jobs, or decrease it? Increase - it's clear, not enough time so let's give it more. But then packingsolver takes its time there and spends more time finding the solution for every job, thus increasing overall CPU load and making it even more difficult for the remaining jobs to finish within time limit. So i thought maybe decreasing the limit would be the answer..
  4. Is there an option for some time limit that would be independent of current CPU load? I mean set a limit on CPU time spent actually doing the optimization task (active CPU time), not the absolute/clock time.
  5. Or maybe another way of approaching this - set a time limit for finding a better solution. So, first of all, packing solver spends as much time as necessary to find ANY solution. And then tries to find a better one but only until reaching the time limit (i know there's a trap...)

Thanks RG


14:16:34.4083|Warn|T102|RQ212|M|Configurator.Services.Optimization.PackingsolverCutOptimizer|Job 96313|7016MI done result 0 output =================================
          PackingSolver          
=================================

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

Instance
--------
Objective:             VariableSizedBinPacking
Number of item types:  2
Number of items:       3
Number of bin types:   8
Number of bins:        24

    Bin type      Length    Max wght        Cost      Copies  Copies min
    --------      ------    --------        ----      ------  ----------
           0         950         inf         950           3           0
           1        1450         inf        1450           3           0
           2        1950         inf        1950           3           0
           3        2450         inf        2450           3           0
           4        2950         inf        2950           3           0
           5        3450         inf        3450           3           0
           6        3950         inf        3950           3           0
           7        4450         inf        4450           3           0

   Item type      Length      Weight   MaxWgtAft     MaxStck      Profit      Copies
   ---------      ------      ------   ---------     -------      ------      ------
           0        1174           0         inf       32767        1174           2
           1        2474           0         inf       32767        2474           1

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

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

Solution
--------
Number of items:  0 / 3 (0%)
Item length:      0 / 4822 (0%)
Item profit:      0 / 4822 (0%)
Number of bins:   0 / 24 (0%)
Bin length:       0 / 64800 (0%)
Bin cost:         0
Waste:            0
Waste (%):        0
Full waste:       0
Full waste (%):   0

         Bin        Type      Copies      Length      Weight     # items
         ---        ----      ------      ------      ------     -------

ARGS:--verbosity-level 9 --objective variable-sized-bin-packing --items C:\windows\TEMP\items_d2e0522d18bc4e54a6012d5009cf28b0.csv --bins C:\windows\TEMP\bins_d2e0522d18bc4e54a6012d5009cf28b0.csv -c C:\windows\TEMP\solution_d2e0522d18bc4e54a6012d5009cf28b0.csv -t 30
fontanf commented 6 months ago

Hi,

Considering the size of the problem, the solver should be able to find a solution instantaneously.

I don't understand from your message if the solver is able to find a solution with the 60s time limit. If yes, can you post the log in this case?

Are you able to reproduce the issue on the same machine? The solver should be deterministic if executed on the same machine. If it's not the case, it means there might be an issue with the parallelization.

Could you also post the input files? I see that some items are larger that some bins. I'm not sure if this is optimally handled by the algorithms.

lafar6502 commented 6 months ago

Yeah, thats a mystery - the problem sizes are so small. But the server was busy with other work too at that time so i thought maybe packing solver doesn't have a chance to run any calculations within the time limit. Will need some time to come up with more details.

Some of my inputs here:

tmpopt.zip

lafar6502 commented 6 months ago

And some task example that finished with results within 60 sec, but no results within 30 secs. Take note that the same cases run separately produce a result even with 5 sec time limit. BTW the instances running 30 or 60 secs - they really were busy, eating all CPU. And i tried to isolate the failing case on the same machine, just running a single instance at a time - but then the solution was always found.

30 sec:


14:16:34.4083|Warn|T102|RQ212|M|Configurator.Services.Optimization.PackingsolverCutOptimizer|Job 96313|7016MI done result 0 output =================================
          PackingSolver          
=================================

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

Instance
--------
Objective:             VariableSizedBinPacking
Number of item types:  2
Number of items:       3
Number of bin types:   8
Number of bins:        24

    Bin type      Length    Max wght        Cost      Copies  Copies min
    --------      ------    --------        ----      ------  ----------
           0         950         inf         950           3           0
           1        1450         inf        1450           3           0
           2        1950         inf        1950           3           0
           3        2450         inf        2450           3           0
           4        2950         inf        2950           3           0
           5        3450         inf        3450           3           0
           6        3950         inf        3950           3           0
           7        4450         inf        4450           3           0

   Item type      Length      Weight   MaxWgtAft     MaxStck      Profit      Copies
   ---------      ------      ------   ---------     -------      ------      ------
           0        1174           0         inf       32767        1174           2
           1        2474           0         inf       32767        2474           1

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

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

Solution
--------
Number of items:  0 / 3 (0%)
Item length:      0 / 4822 (0%)
Item profit:      0 / 4822 (0%)
Number of bins:   0 / 24 (0%)
Bin length:       0 / 64800 (0%)
Bin cost:         0
Waste:            0
Waste (%):        0
Full waste:       0
Full waste (%):   0

         Bin        Type      Copies      Length      Weight     # items
         ---        ----      ------      ------      ------     -------

ARGS:--verbosity-level 9 --objective variable-sized-bin-packing --items C:\windows\TEMP\items_d2e0522d18bc4e54a6012d5009cf28b0.csv --bins C:\windows\TEMP\bins_d2e0522d18bc4e54a6012d5009cf28b0.csv -c C:\windows\TEMP\solution_d2e0522d18bc4e54a6012d5009cf28b0.csv -t 30

60 sec:


14:18:05.6246|Warn|T183|RQ197|M|Configurator.Services.Optimization.PackingsolverCutOptimizer|Job 96313|7016MI done result 0 output =================================
          PackingSolver          
=================================

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

Instance
--------
Objective:             VariableSizedBinPacking
Number of item types:  2
Number of items:       3
Number of bin types:   8
Number of bins:        24

    Bin type      Length    Max wght        Cost      Copies  Copies min
    --------      ------    --------        ----      ------  ----------
           0         950         inf         950           3           0
           1        1450         inf        1450           3           0
           2        1950         inf        1950           3           0
           3        2450         inf        2450           3           0
           4        2950         inf        2950           3           0
           5        3450         inf        3450           3           0
           6        3950         inf        3950           3           0
           7        4450         inf        4450           3           0

   Item type      Length      Weight   MaxWgtAft     MaxStck      Profit      Copies
   ---------      ------      ------   ---------     -------      ------      ------
           0        1174           0         inf       32767        1174           2
           1        2474           0         inf       32767        2474           1

        Time          Cost  # bins  Full waste (%)                         Comment
        ----          ----  ------  --------------                         -------
      38.466          5400       2           10.70                          CG n 2

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

Solution
--------
Number of items:  3 / 3 (100%)
Item length:      4822 / 4822 (100%)
Item profit:      4822 / 4822 (100%)
Number of bins:   2 / 24 (8.33333%)
Bin length:       5400 / 64800 (8.33333%)
Bin cost:         5400
Waste:            302
Waste (%):        5.89383
Full waste:       578
Full waste (%):   10.7037

         Bin        Type      Copies      Length      Weight     # items
         ---        ----      ------      ------      ------     -------
           0           6           1        3652           0           2
           1           1           1        1174           0           1

ARGS:--verbosity-level 9 --objective variable-sized-bin-packing --items C:\windows\TEMP\items_65c63e56c3f34d3fb11a712d865112bd.csv --bins C:\windows\TEMP\bins_65c63e56c3f34d3fb11a712d865112bd.csv -c C:\windows\TEMP\solution_65c63e56c3f34d3fb11a712d865112bd.csv -t 60
fontanf commented 6 months ago

Ok, that's very slow, the CPUs are probably completely saturated.

The right solution is probably to use a job scheduler on the machine.

Another solution would be too use an "effort" limit instead of a time limit. You can get this with the option --optimization-mode not-anytime or --optimization-mode not-anytime-sequential to use a single thread. You would need some tuning to find the effort values that match the running time / solution quality compromise that suits you. For now, I haven't implemented all the tuning options for onedimensional problems, but you can experiment with the default behavior.

lafar6502 commented 6 months ago

C:\tmpopt>onedim.exe --verbosity-level 9 --objective variable-sized-bin-packing --items items_20240418_1.csv --bins bins_20240418_1.csv -c solution_20240418_1.csv --optimization-mode not-anytime With this command line the program hangs indefinitely. Solution is only found when i press Ctrl+C What's the correct way of specifying effort limit?

fontanf commented 6 months ago

Indeed, there was a bug with this option for onedimensional problems. I pushed a fix in the main branch. It should work now.

I also added the additional options:

You can see their default values here: https://github.com/fontanf/packingsolver/blob/master/packingsolver/onedimensional/optimize.hpp#L68

lafar6502 commented 6 months ago

Thanks, will check this out. Yesterday i've been testing this a bit more, running local tests of multiple problems in parallel. Increased the size a bit, added more parallel instances - no luck, it still produced the solution in all cases. So i suppose this is because production runs on Azure server, and these virtual machines dont really have as much CPU power as the physical ones, or the OS scheduler works different way - so that it's possible to saturate the CPU and starve some processes.

lafar6502 commented 6 months ago

And i confirm that the --optimization-mode not-anytime command line option works now (the process terminates with a solution). Thanks. Would you explain the mechanics of not-anytime mode a bit? What does the 'effort' mean in this case - is this the number of solution variants checked, or the limit on optimization iterations performed? Or, is it specific to the algorithm used and every one controls the search effort in its own way?

I noticed in not-anytime mode (with default limits) the execution time is in general much faster than with a time limit i've been using (3 sec, 5 sec usually). In not-anytime the result is generated almost instantaneously (but i assume, with increased risk of getting worse solution or no solution at all when the limits are too low).

However, when using time limit (and anytime mode), packing solver takes as much time as the limit allows and doesnt seem to finish earlier. And it's computing all that time. So i assume it runs the optimization algorithms as long as allowed to, even if the optimal solution is already found. Does packing solver know in any way that it has already found the optimum (is it possible at all for these algorithms to determine if the solution is the optimum and there's no point in further search?)

fontanf commented 6 months ago

All the algorithms with the not-anytime-*-queue-size option rely on a tree search algorithm which has this queue size parameter. The greater the queue size, the better the solution found, but the higher the execution time. By default, the algorithms are first executed with a small queue size and are then restarted with a gradually increasing one: 2, 4, 8, 16... until the time limit is reached. This is the best known way to run these algorithms when having a time limit imposed. The solver quickly finds a feasible solution and then find better and better ones.

Otherwise, it is possible to fix this parameter and run once the algorithms with a fixed queue size. It's the non-anytime mode. One will typically need to wait for the end of the optimization to get a solution. As I mentioned in the previous message, there is a compromise to choose between running time and solution quality. The default values are set to favor solution quality. So if the running time is good for you, you can keep the default values.

In non-anytime mode, if the solver hits the time limit, it will probably not return any solution. So one should only set a time limit if there is another fallback solution.

The solver doesn't know if the solution found is optimal in general.

lafar6502 commented 6 months ago

Thanks, not-anytime is very useful in my case, switching to that. Works much better than clock time limit in case when CPU availability is unpredictable. And for my problem sizes the response time is almost instantaneous.

fontanf commented 6 months ago

Ok great. I close the issue.

Note that I just pushed a new update improving the SVC algorithm and the default algorithm selection. I did these changes because of a not ideal behavior that I noticed on one of the example you provided me. So do not hesitate to provide additional ones, representative of the real problems you solve. That could lead to further improvements.

lafar6502 commented 6 months ago

Hi, i think i need to reopen this (instead of creating another issue) - pulled the last source code and re-compiled. But after that the program fails in every case. Also, one thing is interesting - the binary size for one dimensional is reduced to less than half of it's previous size - from 1300 to 550 kilobytes. Doesn't look right.

This is just a fragment of my log file. You will find the command line arguments there, console output of packing solver and the bins/items data. Let me know if you need some better test case.

16:15:36.8080|Warn|T102|RQ|M|Facile.Core.Util.ProcessUtil|D:\devs\webconfigurator\WebConfigurator\tools\onedim.exe --verbosity-level 9 --objective variable-sized-bin-packing --items C:\Users\rafal\AppData\Local\Temp\items_2182a3d7c7be44a4a564f64950a0f3a9.csv --bins C:\Users\rafal\AppData\Local\Temp\bins_2182a3d7c7be44a4a564f64950a0f3a9.csv -c C:\Users\rafal\AppData\Local\Temp\solution_2182a3d7c7be44a4a564f64950a0f3a9.csv --optimization-mode not-anytime --not-anytime-tree-search-queue-size 2048 --not-anytime-sequential-single-knapsack-subproblem-queue-size 2048 --not-anytime-sequential-value-correction-number-of-iterations 256 --not-anytime-dichotomic-search-subproblem-queue-size 2048
16:15:36.8080|Warn|T102|RQ|M|Facile.Core.Util.ProcessUtil|STDERR: 
16:15:36.8080|Warn|T102|RQ|M|Configurator.Services.Optimization.PackingsolverCutOptimizer|Job 95965|7021MI done result -1073740791 output =================================
          PackingSolver          
=================================

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

Instance
--------
Objective:             VariableSizedBinPacking
Number of item types:  8
Number of items:       48
Number of bin types:   9
Number of bins:        75

    Bin type      Length    Max wght        Cost      Copies  Copies min
    --------      ------    --------        ----      ------  ----------
           0        6950         inf        6950          48           0
           1        1918         inf         767          10           0
           2        1938         inf         775           1           0
           3        2012         inf         805           1           0
           4        1975         inf         790           1           0
           5        1918         inf         767          11           0
           6        1928         inf         771           1           0
           7        1903         inf         761           1           0
           8        4481         inf        1792           1           0

   Item type      Length      Weight   MaxWgtAft     MaxStck      Profit      Copies
   ---------      ------      ------   ---------     -------      ------      ------
           0        2512           0         inf       32767        2512          24
           1        2527           0         inf       32767        2527          12
           2        2502           0         inf       32767        2502           2
           3        2465           0         inf       32767        2465           2
           4        2902           0         inf       32767        2902           1
           5        3689           0         inf       32767        3689           3
           6        1893           0         inf       32767        1893           3
           7        1897           0         inf       32767        1897           1

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

ARGS:--verbosity-level 9 --objective variable-sized-bin-packing --items C:\Users\rafal\AppData\Local\Temp\items_2182a3d7c7be44a4a564f64950a0f3a9.csv --bins C:\Users\rafal\AppData\Local\Temp\bins_2182a3d7c7be44a4a564f64950a0f3a9.csv -c C:\Users\rafal\AppData\Local\Temp\solution_2182a3d7c7be44a4a564f64950a0f3a9.csv --optimization-mode not-anytime --not-anytime-tree-search-queue-size 2048 --not-anytime-sequential-single-knapsack-subproblem-queue-size 2048 --not-anytime-sequential-value-correction-number-of-iterations 256 --not-anytime-dichotomic-search-subproblem-queue-size 2048
16:15:36.8080|Error|T102|RQ|M|Configurator.Services.Optimization.PackingsolverCutOptimizer|Optimize job 95965|7021MI no results file. Bins:
ID,X,COST,COPIES
0,6950,6950,48
1,1918,767,10
2,1938,775,1
3,2012,805,1
4,1975,790,1
5,1918,767,11
6,1928,771,1
7,1903,761,1
8,4481,1792,1
, Items:
ID,X,COPIES,NESTING_LENGTH
0,2512,24,-4
1,2527,12,-4
2,2502,2,-4
3,2465,2,-4
4,2902,1,-4
5,3689,3,-4
6,1893,3,-4
7,1897,1,-4

And another case, with anytime mode - fails to, but there's no console ouput in this case:

2024-04-20 16:39:33.0286|WARN|Configurator.Services.Optimization.PackingsolverCutOptimizer|Job J16 done result -1073740791 output 
ARGS:--verbosity-level 9 --objective variable-sized-bin-packing --items C:\Users\rafal\AppData\Local\Temp\items_6c944b23dae941f791522e9363f664d0.csv --bins C:\Users\rafal\AppData\Local\Temp\bins_6c944b23dae941f791522e9363f664d0.csv -c C:\Users\rafal\AppData\Local\Temp\solution_6c944b23dae941f791522e9363f664d0.csv -t 5
2024-04-20 16:39:33.0286|ERROR|Configurator.Services.Optimization.PackingsolverCutOptimizer|Optimize job J3 no results file. Bins:
ID,X,COST,COPIES
0,3000,3000,23
1,7000,7000,23
2,1800,1800,23
3,800,800,23
4,400,400,23
, Items:
ID,X,COPIES,NESTING_LENGTH
0,1290,2,-5
1,1496,3,-5
2,2751,3,-5
3,3351,7,-5
4,1950,4,-5
5,2250,4,-5
fontanf commented 6 months ago

I can't reproduce. The Windows pipeline looks good. Maybe try to re-compile from scratch.

lafar6502 commented 6 months ago

Sorry, my mistake - i compiled without CLP... Now rebuilt and all looks good

fontanf commented 6 months ago

No problem. Now that CLP is downloaded automatically and work well on all platforms, I'll soon enable it in the default build setting