Sources of and Parameters for Tightening Variable Bounds during Branch and Cut beyond Branching

[spkelle2]

I've noticed for many MILP's that I solve with CBC that the LP relaxation associated with a child node may have more variable bounds tightened relative to its parent node's LP relaxation than just the variable that was branched on. Would anyone be able to point me to where I can read more about what are the causes of this and what parameters are available to control them?

[jjhforrest]

Not sure where to read more, but there would be three main reasons (with different computing costs) -

1. Fixing on reduced cost. If the gap between current solution value and best so far is less than the reduced cost of an integer variable then the variable can be fixed (or the bound tightened). This is very cheap.
2. Some cut generators (e.g. probing) can do the same. These are only run at some nodes - this can be influenced by options in an obscure way.
3. cbc uses estimates of branching costs (pseudo-costs). If a variable has not been branched on much then a quick (full or partial) solve may be done to get these before choosing a variable - strong branching. Often this can fix variables. This is mainly influenced by -strong and -trust.

[spkelle2]

The reasons why variable tightening occurs between nodes seem sufficiently clear to me. Thank you for the quick reply!

However, per my second question, could you point me to any relevant API end points in CBC, OSI, etc. that control for 1-3? I did go ahead and search the docs for strong and trust, and it appears those related endpoints (if I understood them correctly) control for the amount of strong branching that occurs but not the frequency with which variables are tightened during strong branching.

Also, I did find this (option 262144) and this. Are either of those related to our conversation?

[spkelle2]

So I tried running what experiments I could, but knowing what API endpoints control for 1-3 above would be a huge help in what we're working on. Would you be able to point me to any relevant sections of documentation?

[jjhforrest]

Forget about 1 - always done
3 - changing bounds is a by product of strong branching i.e. branching says one way infeasible.
tightenBounds is always called in CbcModel::resolve

as for 2 - you could try probing more. I am experimenting at present with doing some probing at every depth 10 - which may make its way into master sometime.

[spkelle2]

Cool this is helpful, even if just for the sake of telling my higher ups that we are limited in how we can control for tightened variable bounds in between branching decisions.

Thank you for getting back to me on this!