I have a MIP in which I am able to generate cuts at intermediate relaxation solutions using the context class. These cuts are derived from a separation problem. However, after adding them, the code runs very slowly since the separation problem takes some time to solve.

I tried adding cuts sparingly based on the iteration number or the node number, but this did little to improve the LP relaxation solutions.

Does anyone have advice on how best to schedule the calls to the separator to improve the LP bounds? Additionally, I am unsure about what CPLEX does when I ask it to apply the cuts every (say) 2000 iterations. Does it call the separation problem for all nodes left or just a single node?

I am using the following code before I call the solve function.

connectivity_cb = SeparationProblem(arguments...)
contextmask = 0

contextmask |= cplex.callbacks.Context.id.relaxation
contextmask |= cplex.callbacks.Context.id.candidate

if contextmask:
    problem.set_callback(connectivity_cb, contextmask)

The SeparationProblem has an invoke function like the CPLEX examples.

def should_add_user_cuts(self, context):
    iteration_count = context.get_int_info(context.info.iteration_count)
    return (iteration_count % 20) == 0

def invoke(self, context):
        if context.in_candidate():
        elif context.in_relaxation() and self.should_add_user_cuts(context):
        info = sys.exc_info()
        print('#### Exception in callback: ', info[0])
        print('####                        ', info[1])
        print('####                        ', info[2])
        traceback.print_tb(info[2], file=sys.stdout)
  • $\begingroup$ Is the slow-down a result of long computation times for the separation problem, or does the cuts slow down the solution process themselves? If you add very dense cuts, it may significantly slow down reoptimization of the LP relaxation of subsequent noses. $\endgroup$
    – Sune
    Commented May 27 at 17:06
  • $\begingroup$ The separation problem takes a few milliseconds and I am adding only one cut per call based on the maximum separation. $\endgroup$
    – tr244
    Commented May 28 at 8:21
  • $\begingroup$ It might be a good idea to investigate where the problem lies: 1) do you create a gazillion cuts in each node, leading to many iterations of the cut-loop? 2) Do you create cuts, that significantly slow down the reoptimisation of each node? 3) I don't known the CPLEX python API, but you may also want to measure the time used to communicate with the solver when you retrieve values and add the cut. This may be a bottleneck as well $\endgroup$
    – Sune
    Commented May 28 at 12:46
  • $\begingroup$ I just create one cut at each node, but I want add cuts at multiple nodes that haven't been branched by solving multiple separation problems. $\endgroup$
    – tr244
    Commented May 29 at 0:20

2 Answers 2


Are you solving the separation problem inside a generic callback? If so, CPLEX will solve the problem once per call to the callback (or less, if the callback sometimes chooses not to solve the problem). How often the callback is invoked depends on what contexts you specified for invoking it.

  • $\begingroup$ I added some extra code snippets to demonstrate how I am solving the separation problem. add_type1_cut and add_type2_cut generates extra cut(s) and adds it to the model. $\endgroup$
    – tr244
    Commented May 28 at 8:21
  • $\begingroup$ If I'm reading the code correctly, it will attempt to add cuts whenever a new candidate is found or after solving the LP relaxation at every 20th relaxed (feasible but not integer-feasible) solution (which is usually a node LP solution but could come from a heuristic, I think). This invocation will be at the current node, not simultaneously at all live nodes. $\endgroup$
    – prubin
    Commented May 28 at 18:28
  • $\begingroup$ I see. Is there a way to call the function at all live nodes in CPLEX? $\endgroup$
    – tr244
    Commented May 29 at 0:25
  • $\begingroup$ The every 20th relaxation is in your code. If you take that out, it will be called (eventually) at every node that is not pruned based on bound or infeasibility. $\endgroup$
    – prubin
    Commented May 29 at 16:09
  • $\begingroup$ I'm sorry I was not clear. I was hoping to apply the separation problem at all live nodes every k iterations of the the branch and bound method. I am trying to do this with a large k so that the calls to the separation problem are rare. Do you think this can be done? Would you recommend any other strategy for adding cuts? $\endgroup$
    – tr244
    Commented May 30 at 18:29

As far as I understand, you have a branch-and-cut algorithm that separates valid inequalities for integer and fractional solutions. The cuts you separate are valid and improve the quality of the continuous relaxation, but the model would still be correct without them. You notice a trade-off between the relaxation quality and the time it takes to separate the cuts.

There are a few strategies that you could use in this case:

  1. Improve your cuts. Your cuts are effective, but perhaps they could be more effective, thus requiring fewer rounds of separation and the exploration of fewer branch-and-bound nodes. For example, you could try lifting your cuts or analysing your polytope in search of facet-defining inequalities.

  2. Use more cuts. Even without a rigorous analysis, you could simply try to devise other families of valid inequalities. Maybe your problem has a known structure (e.g., a routing problem) for which there is extensive literature on valid inequalities. Even if you cannot use them as-is, you could get inspired by these cuts from the literature to devise your own. If you have many families of valid inequalities, you could then analyse which ones are more effective (especially in relation to the time it takes to separate them) and only enable cuts that improve the overall branch-and-cut performance.

  3. Separate your cuts heuristically. Since your formulation is correct even without valid inequalities, you might decide that you don't want to find all the violated ones. Instead of a time-consuming exact separation procedure, you could use a heuristic one that identifies most—but not necessarily all—violated inequalities.

  4. Separate your cuts at select branch-and-bound nodes. This is basically what you are trying. In the most extreme case, I have seen branch-and-cut algorithms where separation only happens at the root node. Another approach is to attempt separation every n nodes which, if I understand correctly, is what you are doing. Maybe this procedure could be improved with a more careful selection of the nodes. E.g., are the inequalities more likely to cut off a good portion of the relaxed polytope in the first few branch-and-bound nodes? If so, you could use the separation procedure at the beginning of the algorithm and then "turn it off". Also, as it is popular nowadays, you might try to learn the characteristics of promising nodes where to perform cut separation. (See, e.g., this paper.)

  5. Only separate cuts when you find integer solutions. In this case, you lose some (or most) benefits when it comes to quickly improving the continuous relaxation. Still, cuts that are expensive to separate for fractional solutions are often separated trivially for integer solutions.

  6. Let the solver separate some cuts for you. Most solvers (Cplex included) have settings that specify how aggressive they should be at generating cuts. Of course, a generic MIP solver will not generate problem-specific cuts. Still, there have been a lot of improvements in general integer cuts in the last few years, and a more aggressive setting might help. In this respect, my impression is that a more actively developed solver could be better than Cplex, but you never know.

  7. Optimise your cut separation routine. Is your cut separation routine as efficient as it could be? First, check that you are using an efficient algorithm. Second, if separation is the bottleneck and you have development time to spare, you could try to implement it in a more performant programming language that interfaces with Python (e.g., C or C++).

  • $\begingroup$ Thanks for the detailed response. Yes, I am trying to do #4. I do find good integer solution bounds but the LP relaxations stop improving quickly after a point. Hence, I want to add cuts at all unexplored nodes. But this is proving to be difficult. I will check out the paper you suggested. $\endgroup$
    – tr244
    Commented May 29 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.