Suboptimal MIP Solution with LazyConstraints due to analyzeObjective?

[ciderale]

My experiments with lazy constraints in cbc/python-mip yield sub optimal solution. I distilled a minimal example to reproduce the issue (coin-or/python-mip#331). I recently found more time to analyse the problem and made an interesting observation.

Is it possible that CbcModel::analyseObjective is problematic in the context of lazy constraint generation? This method analyses the rows of the model, but many rows do not yet exist in a lazy setting. I wonder if analyseObjective makes sense with partially defined rows?

Skipping the CbcModel::analyseObjective call altogether provides the correct global optimum for all three modes (Complete Model, Lazy Constraints, Generated Constraints) in the minimal example. Below is short description of what happens when not skipping analyseObjective with lazy constraints.

The initial CbcModel::analyseObjective analyses the problem. At that point, no lazy constraints have been added to the model. This method now increases the cutoff increment from near 0 to near 1. Cbc0045I Cutoff increment increased from 0.0001 to 0.9999 (CbcModel.cpp:1225:analyzeObjective) That cutoff increment is later used to adjust the cutoff = bestObjective - dblParams_[CbcCutoffIncrement] (CbcModel.cpp:14360:setBestSolution)

This adjustment causes problems in the node branching. It properly branches, but both (up and down) branches are considered infeasible. Below some manually added traceouts with line numbers to illustrate the behaviour.

The first call to setBestSolution with the 1.25 objective value adjusts the cutoff

CbcModel:setBestSolution:14361 bestObjective=1.25 new cutoff = 0.2501

Both up and down branches are revalidated against this new cutoff

CbcNode::chooseDynamicBranch:3628 newObjective=1.25 => considered infeasible CbcNode::chooseDynamicBranch:3806 newObjective=1.15 => considered infeasible

which makes neither branch side feabible

CbcNode:chooseDynamicBranch:4242: neihter side is feasible

Hence, the optimisation concludes with the first found solution 1.25, which is not the optimal solution.

Should CbcModel::analyseObjective not do anything in case of lazy/generated constraints? Or is there a modification to account for lazy constraints?

[jjhforrest]

Should be fixed when using Cbc master. Your analysis is perfectly correct but analyzeObjective was being called twice and the first time the lazy constraint generator had not been added to model so my first modification was not enough.

[ciderale]

Thank you very much for quick reaction and the fix. The change fixes the problem described. Unfortunately, I found some more unexpected behaviour in relation to lazy constraints. I will provide that in a new issue.