Originally posted by: SystemAdmin
[prubin said:]
There is an instructive flowchart (Powerpoint) of what is done at each node, in what order, at [url=https://support.ilog.com/cse/ilog_cplex/kbi/mixed_integer_programming/kbi_439/(search)/1]https://support.ilog.com/cse/ilog_cplex/kbi/mixed_integer_programming/kbi_439/(search)/1[/url]. Unfortunately, you may need a support ID to be able to access it. Also, the author of the chart tried to keep it relatively simple and uncluttered, and so there are a couple of possible flows that are not documented on the chart (such as what happens if a heuristic detects a new incumbent).
You might want to look at the forum thread at [url=http://forums.ilog.com/optimization/index.php/topic,375.msg1067.html#msg1067]http://forums.ilog.com/optimization/index.php/topic,375.msg1067.html#msg1067[/url].
If you know all the relevant cuts up front, you can introduce them as lazy constraints. They'll sit off to the side as long as they are not violated, and CPLEX will automatically introduce them as needed. Since you specified that you would add violated cuts only when an integer feasible solution occurs, I'm going to guess that you'll be computing the new cuts on the fly and won't know them all up front.
Fundamentally, you'll need to use an incumbent callback to check new incumbents and a cut callback to add the new cuts. The incumbent callback will be responsible for computing the violated cuts and storing them someplace where the cut callback can find them. (The incumbent callback can reject the new incumbent but cannot add any cuts itself.) The cut callback will be called at every node, not just nodes with new incumbents. It's job is to check for any queued cuts and, if present, add them (and then clear the cut queue).
That almost but not quite handles it. The catch is that if the heuristic callback is triggered by an integer-feasible solution to the node LP, the cut callback will not be called at that node. So if you reject the incumbent, CPLEX doesn't know what to do -- it can't branch normally (on an integer variable with a fractional value) because there are no variables on which to branch. Adding your violated cut might create fractional values, but you've missed the opportunity to add it at this node. So you also need a branch callback. The branch callback is called at every node, and unless the heuristic callback has queued a cut, the branch callback should just let CPLEX branch normally. If the branch callback sees a queued cut, though, it should create a single child node, using the queued cut (or cuts) to define the child. (It also needs to leave the cuts in the queue -- the cut callback will need them later). CPLEX will then branch to the child (which is just the parent plus your violated cuts) and process it normally.
Hope that helps.
/Paul
#DecisionOptimization#MathematicalProgramming-General