Lazy and generated constraint model much slower than complete model about cbc

[jjhforrest]

I have made changes - which I hope do not break anything. Lazy looks OK - Gen still does not work - will look at that - but it is slightly awkward debugging C++ called from python. In debug mode my Complete took 47 seconds for 100 model and Lazy 38.

[ciderale]

Thanks again for the rapid response and changes.

This new version solves N=10 with lazy constraints quickly (0.85 CPU seconds). However for N=11 the lazy variant does not converge within a 30 seconds time limit (the complete model does in 0.1second) and was not able to find the optimal solution (it selects x_{N-2}=x_{N-1}=1, but x_N=0):

	Complete Model N=11	Lazy Model N=11
Result	Optimal solution found	stopped on time limit
Objective value:	0.190909090909	0.211111111111
Lower bound:	-	0.166667
Gap:	-	0.266667
Enumerated nodes:	4	70383
Total iterations:	692	202
Time (CPU seconds):	0.106367	30.9555

Looking at the solvers output, I'm surprised by the reported gap of 0.26 -- shouldn't that be 0.045(=0.211-0.1667)?

Moreover, the constraint generation model now fails to find the optimal solution for N=8 and aborts after the 30s time limit with a sub optimal solution of 0.375 instead of 0.267.

[jjhforrest]

I knew I might have made Gen model worse - was going to dig into that today.
The reported gap is correct - it is a fraction so (0.211-0.1667)/0.1667

[jjhforrest]

Just ran lazy with 11 -
####### SOLVING ######### Mode.Lazy N= 11
OptimizationStatus.OPTIMAL
obj= 0.19090909090909092 solution: [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0]

Result - Optimal solution found
Objective value: 0.190909090909
Enumerated nodes: 16
Total iterations: 102
Time (CPU seconds): 0.018546

[jjhforrest]

Have made more changes. Works for me with 8,9,10,11,50 and 100

One point that might be of interest to people using Cbc master and python-mip is that to help me debug, I modified Cbc_C_Interface which is used by python-mip. Now if the environment variable COIN_CBC_OPTIONS is set
e.g.
export COIN_CBC_OPTIONS=/tmp/options_py.txt

the code reads standard cbc options which adds some items not directly accessible from the C interface. The format is one parameter per line - without the leading -. Lines starting * are comments. Any options that you can see by going into cbc and entering ? can be used.

[ciderale]

Many thanks for these changes, cbc now solves up to N=100 with ease -- and the lazy constraint variant being extremely fast, actually the fastest of the 3 variants. I guess the reason that the generated constraint model is slower is due to the python interoperability overhead, isn't it? Or could there be something else?

One thing I noticed though is that the lazy variant reports a sub optimal solution as optimal. For example with N=105, it selects x_N=x_{N-2}=1 and x_{N-1}=0 with objective value of 0.0192325473879 instead of 0.0191391941392. Is that within some epsilon tolerance or is this an issue?

(Similarly for N=107 and N=109. Interestingly the odd numbers 106, 108 are not affected, neither are N>110 (have not tested extensively).

Again thanks a lot for your work to improve the lazy constraint generation feature. I hope debugging the solver when called from python was not too bothersome, or at least, that the minimalistic examples made up for that and helped to identify the root causes quickly.

[jjhforrest]

The default cutoff increment is 0.0001 and 0.0191391 is not 0.0001 better than 0.019232, which is why you got that behaviour. I will get round to adding a setCutoffIncrement to the C interface - unless someone else wants to get involved with C interface. However you can fix the problem. So I have a file /tmp/options_py.txt which just has one line

increment 1.0e-6

and I export COIN_CBC_OPTIONS="/tmp/options_py.txt"