BMIBNB solver does not terminate after time limit

[dumpram]

If time limit is exceeded with BMIBNB sovler, YALMIP hangs until Ctrl + C is pressed.

[johanlofberg]

You would have to supply a reproducible example, as it is not generic. Could it be that a sub-solver stalls? (bmibnb does not terminate the sub-solver if it exceeds bmibnbs timelimit, although it is a good feature to add, works like that in bnb)

`>> optimize([-1 <= x <= 1],x'Qx,sdpsettings('solver','bmibnb','bmibnb.maxtime',1))

• Starting YALMIP global branch & bound.
• Branch-variables : 20
• Upper solver : CPLEX
• Lower solver : CPLEX
• LP solver : CPLEX Node Upper Gap(%) Lower Open 1 : 0.000E+00 199.95 -7.619E+03 2
  2 : 0.000E+00 199.95 -7.619E+03 3
  3 : 0.000E+00 199.94 -7.220E+03 4
• Finished. Cost: 0 Gap: 199.9446
• Termination due to time limit
• Timing: 1% spent in upper solver (3 problems solved)
• 2% spent in lower solver (43 problems solved)
• 50% spent in LP-based domain reduction (120 problems solved)

ans =

struct with fields:

yalmipversion: '20190425'
   yalmiptime: 0.2370
   solvertime: 2.0910
         info: 'Maximum iterations or time limit exceeded (BMIBNB)'
      problem: 3

`

[dumpram]

If understand correctly, I should add time limit to every solver which BMIBNB uses:

* Starting YALMIP global branch & bound.
* Branch-variables : 168
* Upper solver     : fmincon
* Lower solver     : MOSEK
* LP solver        : MOSEK
 Node       Upper      Gap(%)       Lower    Open

in this case MOSEK and fmincon?

[johanlofberg]

At the moment you will have to do that, but I will update the code so that it is handled automatically

[johanlofberg]

fmincon does not support time limit so a bit tricky...

btw, are you sure that is where it stalls? (set verbose to 2 and you will see local solver iterations)

[dumpram]

In this particular case, it spends only 1 % of the time in fmincon. After I added time limit to MOSEK, BMIBNB stopped as expected.

[johanlofberg]

Care to share the example? Sounds weird that it would stall in the lower solver which should take no time. Send privately by mail if you wish

[dumpram]

Here is an output from example:

* Starting YALMIP global branch & bound.
* Branch-variables : 168
* Upper solver     : fmincon
* Lower solver     : MOSEK
* LP solver        : MOSEK
 Node       Upper      Gap(%)       Lower    Open
    1 :    2.146E-01     1.10      2.013E-01   2  Improved solution  
* Finished.  Cost: 0.21459 Gap: 1.1034
* Termination due to time limit 
* Timing: 1% spent in upper solver (2 problems solved)
*         43% spent in lower solver (337 problems solved)
*         33% spent in LP-based domain reduction (656 problems solved)

Is this enough? When I turn on verbose, output from MOSEK solver can be seen. I could provide an example but not at this moment.

[johanlofberg]

To act I would have to have a reproducible example

Or do you mean perhaps that it spends a lot of time in Mosek in general (as it solves around 1000 problems for bound propagation etc), and not necessarily in a single call to mosek

[dumpram]

There are definitely multiple MOSEK calls. I'll try to prepare an example.

[johanlofberg]

I guess what you mean then is simply that YALMIP should check for time limit also during the bound propagation routines, and not just in the end of every node iteration. With as many branching variables as you have here, most of the time might easily be spent in bound propagation, in particular with the default settings which assumes a low number of branching variables. (With 168 variables, it requires pure luck for bmibnb to work)