Optimizing calls to a separation problem in branch and cut

Question

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):
    try:
        if context.in_candidate():
            self.add_type1_cut(context)
        elif context.in_relaxation() and self.should_add_user_cuts(context):
            self.add_type2_cut(context)
    except:
        info = sys.exc_info()
        print('#### Exception in callback: ', info[0])
        print('####                        ', info[1])
        print('####                        ', info[2])
        traceback.print_tb(info[2], file=sys.stdout)
        raise
```

Answer 1

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.

Answer 2

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++).