Default CPLEX

Callbacks allow user written code to be run at select points to monitor or influence the behavior of the CPLEX solver. Before modifying the behavior of the solver, lets understand exactly how the solver works. Below is a somewhat simplified picture of the algorithm CPLEX is using to solve an integer program.

The algorithm terminates when the node stack is empty, and the best incumbent found is the new solution. The first node pushed on, the LP relaxation of the original problem is often called the root node.

LazyConstraintCallback

Lazy constraints, at a high level, are constraints that are only checked when a candidate for an integer solution has been identified. They can be added to the model at the start though the IloCplex method addLazyConstraint(IloRange range), or they can be added on the fly with a LazyConstraintCallback (documentation here). The LazyConstraintCallback provides a user implemented routine to take a new potential incumbent solution, determine any of the lazy constraints were violated, and if so, to add at least one of them to the model. Typically, you would want to use lazy constraints when you have a large number of constraints and you expect that few will be violated, as they allow you to have smaller LPs to solve when processing each node. In the case of the LazyConstraintCallback, you gain an additional advantage in that you do not need to explicitly store all of the lazy constraints in memory, which is critical for problems like TSP that have an exponential number of constraints. The downside is that you can waste a lot of time in branch and bound trying to generate integer solutions, only to find that they are actually infeasible. Regardless of whether addLazyConstraint(IloRange range)) or a LazyConstraintCallback was used, the model becomes