Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
Given that you have identified a new class of valid inequalities.
What are some guidelines on when and how many and which of the violated user cuts you add to the model?
I know that this involves a lot of benchmarking, but are there some common wisdom? What are the first things you try?
For example I saw that adding too many cuts slows down the processing of the nodes in the branch-and-bound tree and I think that will fall under the "Conventional wisdom".
Performance-wise, there are two main classes of cuts: (i) normal cuts, and (ii) global or "deep" cuts (definitions may vary between fields, this is what we use in deterministic global optimisation).
Deep cuts are globally valid, i.e., they are valid at every node of a branch-and-bound tree. This is usually the most desirable type of cut, because we don't have to change the coefficient matrix too much (or at all) when we create a new node.
Every cut that is not deep, is normal, and not necessarily globally valid. These are situational, but often crucial to close the last few % of the optimality gap and converge.
Cuts are nearly always good from a theoretical point of view, the problem is that they make relaxations harder to solve so there's always a tradeoff. The rule of thumb is to add as many deep cuts as you can afford in the beginning (you can measure the tradeoff by resolving at the root node a few times with more cuts), and then add other cuts where necessary. This can be done dynamically by creating and keeping track of a pool of cuts.
Ruth Misener has documented the dynamic approach very well on her papers about the GloMIQO solver.
