Originally posted by: SystemAdmin

[leo said:]

Hi, all,

Would you please tell me what will happen at each node in turn when solving a MIP? For example, is the first step to add cuts? then solve the LP problem?  If CPLEX find a integer solution, it will call incumbent callback to check whether to accept this solution, etc.

What is the order of solving node LP by CPLEX?  Thanks.


Leo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

This should probably be a FAQ (and someone from ILOG who knows more than I do should probably answer it).  My understanding is:

1.  CPLEX solves the node LP relaxation.  If there is a solve callback, CPLEX calls that to solve the relaxation; otherwise, it solves the relaxation using the specified LP algorithm (which I think defaults to dual simplex once you're past the root node).
  1a. If the LP has an integer-feasible solution (with objective value better than the incumbent), CPLEX calls the incumbent callback (if one exists).  If the solution is accepted, CPLEX updates the incumbent.  Either way, CPLEX fathoms the current node and selects another node (calling the node callback if one exists).  As far as I know, the cut callback is not called in this case.
  1b. Otherwise, CPLEX calls the cut callback (if one exists).  If the callback adds cuts (local or global), CPLEX applies them to this node and repeats step 1.  This continues until the cut callback does not return any cuts.

2.  Assuming the node relaxation solution is not integer-feasible, CPLEX applies its own heuristics (if turned on) and calls the heuristic callback (if present).  Once again, if an integer-feasible solution is found, CPLEX calls the incumbent callback (if present), then updates the incumbent (unless the callback rejected it).  In this case, finding an incumbent does [i]not[/i] cause CPLEX to fathom the node.

3.  CPLEX separates the node.  If a branch callback is present, CPLEX uses it to generate one or two child nodes (based on cuts or goals specified in the callback).  Otherwise, it follows its current branching strategy to create two children.

4.  CPLEX selects the next node to process, either by its current search strategy or using a node callback (if present).

Don't take that to the bank unless someone on ILOG's payroll blesses it.  ;-)

/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[leo said:]

[quote author=prubin link=topic=368.msg1047#msg1047 date=1214753165]
This should probably be a FAQ (and someone from ILOG who knows more than I do should probably answer it).  My understanding is:

1.  CPLEX solves the node LP relaxation.  If there is a solve callback, CPLEX calls that to solve the relaxation; otherwise, it solves the relaxation using the specified LP algorithm (which I think defaults to dual simplex once you're past the root node).
  1a. If the LP has an integer-feasible solution (with objective value better than the incumbent), CPLEX calls the incumbent callback (if one exists).  If the solution is accepted, CPLEX updates the incumbent.  Either way, CPLEX fathoms the current node and selects another node (calling the node callback if one exists).  As far as I know, the cut callback is not called in this case.
  1b. Otherwise, CPLEX calls the cut callback (if one exists).  If the callback adds cuts (local or global), CPLEX applies them to this node and repeats step 1.  This continues until the cut callback does not return any cuts.

2.  Assuming the node relaxation solution is not integer-feasible, CPLEX applies its own heuristics (if turned on) and calls the heuristic callback (if present).  Once again, if an integer-feasible solution is found, CPLEX calls the incumbent callback (if present), then updates the incumbent (unless the callback rejected it).  In this case, finding an incumbent does [i]not[/i] cause CPLEX to fathom the node.

3.  CPLEX separates the node.  If a branch callback is present, CPLEX uses it to generate one or two child nodes (based on cuts or goals specified in the callback).  Otherwise, it follows its current branching strategy to create two children.

4.  CPLEX selects the next node to process, either by its current search strategy or using a node callback (if present).

Don't take that to the bank unless someone on ILOG's payroll blesses it.  ;-)

/Paul



Anyway, thanks careful explanation.
I will send a email to the ILOG support. Once I get the answer, I will tell it to you.
Thanks.

Leo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[Sylvain said:]

[quote author=prubin link=topic=368.msg1047#msg1047 date=1214753165]
This should probably be a FAQ (and someone from ILOG who knows more than I do should probably answer it).  My understanding is:

1.  CPLEX solves the node LP relaxation.  If there is a solve callback, CPLEX calls that to solve the relaxation; otherwise, it solves the relaxation using the specified LP algorithm (which I think defaults to dual simplex once you're past the root node).
  1a. If the LP has an integer-feasible solution (with objective value better than the incumbent), CPLEX calls the incumbent callback (if one exists).  If the solution is accepted, CPLEX updates the incumbent.  Either way, CPLEX fathoms the current node and selects another node (calling the node callback if one exists).  As far as I know, the cut callback is not called in this case.
  1b. Otherwise, CPLEX calls the cut callback (if one exists).  If the callback adds cuts (local or global), CPLEX applies them to this node and repeats step 1.  This continues until the cut callback does not return any cuts.

2.  Assuming the node relaxation solution is not integer-feasible, CPLEX applies its own heuristics (if turned on) and calls the heuristic callback (if present).  Once again, if an integer-feasible solution is found, CPLEX calls the incumbent callback (if present), then updates the incumbent (unless the callback rejected it).  In this case, finding an incumbent does [i]not[/i] cause CPLEX to fathom the node.

3.  CPLEX separates the node.  If a branch callback is present, CPLEX uses it to generate one or two child nodes (based on cuts or goals specified in the callback).  Otherwise, it follows its current branching strategy to create two children.

4.  CPLEX selects the next node to process, either by its current search strategy or using a node callback (if present).

Don't take that to the bank unless someone on ILOG's payroll blesses it.  ;-)

/Paul


There is a small detail that needs to be said about cut callbacks here.
There exists two types of cuts :
- Lazy cuts that need to be satisfied by any integer solution
- User cuts (like Gomory cuts) that are just used to tighten the node LP relaxation, and are not used when the LP solution is integer
There exists two cut callbacks corresponding to these two types of cuts.

I believe that the LazyCutCallback (or CutCallback in C++) is always called after the LP relaxation is solved. If no lazy cuts are added and the LP solution is integer, than the IncumbentCallback is called. If not, the UserCutCallback is called and the LP relaxation is possibly resolved if some cuts are added.

The Cplex manual should be read carefully regarding cuts to better understand the mecanism but I feel that a precise description of the different steps performed in each node is missing.
It would really help those who try to modify/extend/improve the Branch & Cut search...


#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

[quote author=Sylvain link=topic=368.msg1074#msg1074 date=1215056048]
I believe that the LazyCutCallback (or CutCallback in C++) is always called after the LP relaxation is solved. If no lazy cuts are added and the LP solution is integer, than the IncumbentCallback is called. If not, the UserCutCallback is called and the LP relaxation is possibly resolved if some cuts are added.

Thanks for the clarification.  Adding to the confusion level:  UserCutCallback is not a subclass of CutCallback (whereas LazyCutCallback is).  In fact, I believe LazyCutCallback is (currently) a synonym for CutCallback (meaning that if you subclass CutCallback, as I do, you are effectively creating a LazyCutCallback).  My guess is that this is subject to change in some future version.

[quote author=Sylvain link=topic=368.msg1074#msg1074 date=1215056048]
The Cplex manual should be read carefully regarding cuts to better understand the mecanism but I feel that a precise description of the different steps performed in each node is missing.
It would really help those who try to modify/extend/improve the Branch & Cut search...


I agree.  I had an off-forum exchange with someone at ILOG regarding this, and I am cautiously optimistic that an entry on the sequencing of operations at a node will be added to the FAQ.

/Paul

#CPLEXOptimizers
#DecisionOptimization