Bop set_time_limit does not work correctly

[seechu...@gmail.com]

Hi,

The below is the log from bop. Model solves for 44.23s when timeLimit of 180s was set. Using MPSolver::set_time_limit() yields the same result. Bop set_time_limit does not work correctly.

>solve -input test.mps -solver bop -time_limit_ms 180000
 LS_1 :   0/12   (  0.00%)  Total gain:      0  Total Dtime: 0.001 score: 0.000001
                                        LS_2 :   0/12   (  0.00%)  Total gain:      0  Total Dtime: 0.003 score: 0.000001
                                        LS_3 :   6/17   ( 35.29%)  Total gain:     65  Total Dtime: 3.431 score: 3.265365
                                        LS_4 :   0/11   (  0.00%)  Total gain:      0  Total Dtime: 7.128 score: 0.000001
                      SATRandomFirstSolution :   8/32   ( 25.00%)  Total gain:     21  Total Dtime: 3.290 score: 0.168057
                            LinearRelaxation :   0/12   (  0.00%)  Total gain:      0  Total Dtime: 0.043 score: 0.000001
                          SATLPFirstSolution :   0/19   (  0.00%)  Total gain:      0  Total Dtime: 1.771 score: 0.000001
                   SATObjectiveFirstSolution :   0/18   (  0.00%)  Total gain:      0  Total Dtime: 1.664 score: 0.000001
                   RandomConstraintLnsWithLp :   0/12   (  0.00%)  Total gain:      0  Total Dtime: 4.777 score: 0.000001
                     RandomVariableLnsWithLp :   0/12   (  0.00%)  Total gain:      0  Total Dtime: 4.399 score: 0.000001
                            RelationGraphLns :   4/118  (  3.39%)  Total gain:      8  Total Dtime: 1.327 score: 0.003026
                      RelationGraphLnsWithLp :  10/114  (  8.77%)  Total gain:     22  Total Dtime: 1.773 score: 4.404582
                         RandomConstraintLns :   0/12   (  0.00%)  Total gain:      0  Total Dtime: 4.285 score: 0.000001
                           RandomVariableLns :   0/13   (  0.00%)  Total gain:      0  Total Dtime: 4.733 score: 0.000001
                       SatCoreBasedOptimizer :   0/10   (  0.00%)  Total gain:      0  Total Dtime: 5.240 score: 0.000001
                                         LNS :   2/16   ( 12.50%)  Total gain:      2  Total Dtime: 4.814 score: 0.792790

Status      : MPSOLVER_FEASIBLE
Objective   : 1.080000000000000e+02
Time        : 44.23

[seechu...@gmail.com]

Forget to mentioned that the below refers to bop compiled using MSVC 2015 win 64.

[seechu...@gmail.com]

 I have run more test cases. It seems that bop set_time_limit works fine for some problem, but is incorrect for other problems.

[Driss Lahlou]

Hello,

Can you please provide us with the data and options that you used in this example? we will have someone to check this. Thank you.

Regards,

On Sat, Jul 30, 2016 at 4:22 PM, <seechu...@gmail.com> wrote:

 I have run more test cases. It seems that bop set_time_limit works fine for some problem, but is incorrect for other problems.

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

driss

[seechu...@gmail.com]

solve.exe is compiled using msvc 2015 update 3. I created my own project file to compile it. The test cases are as follows. The mps file are attached as bop.7z. I will attach solve.exe in another email, so that this email will go through even if solve.exe gets filtered off.

Case1:
solve --input aBop.mps -solver bop -time_limit_ms 60000

Status      : MPSOLVER_NOT_SOLVED
Objective   : 0.000000000000000e+00
Time        : 60.07

Case2:
solve --input pBop.mps -solver bop -time_limit_ms 60000

Status      : MPSOLVER_FEASIBLE
Objective   : 5.500000000000000e+02
Time        : 13.76

[seechu...@gmail.com]

Attaching solve.7z which contains solve.exe. To unzip it, the password is 12345678

[Driss Lahlou]

After investigation, this is the expected behavior.

For instance the problem pBop contains 31212 variables. The problem can be trivially decomposed into 25054 independent sub-problems, all but one containing only one variable.

The current heuristic is to split the time limit proportionally to the number of variables of a sub-problem. That means that all one-variable sub-problems are given 2ms to solve and the large one 12 seconds. The one-variable sub-problems are obviously super fast to solve, hence the total solving time of 13 seconds.

A workaround would be to not introduce all those one-variable sub-problems.

Hope it helps.

[seechu...@gmail.com]

Thanks a lot for the explanation. For the time being, I would use InterruptSolve() to stop bop. It will be good if there is a set_time_limit function that stops using wall clock.

[seechu...@gmail.com]

For the suggestion on "A workaround would be to not introduce all those one-variable sub-problems", how could it be done, possible to do it via bop params settings?

[seechu...@gmail.com]

1) I used the following & it seems to work correctly.
solve --input pBop.mps -solver bop -time_limit_ms 60000 -params decomposer_num_variables_threshold:100000

2) Amending integral_solver.cc line 1017 to the below & it seems to work fine.
NestedTimeLimit subproblem_time_limit(
      time_limit, parameters.max_time_in_seconds(), parameters.max_time_in_seconds());