User Cuts, Callback Efficiency, and Internal Cut Generation

回答済み

Ozge Koc

2025年06月17日 20:00

• 
• 

Hi Gurobi team,

I'm implementing a Branch-and-Cut algorithm using the MIPNODE callback to add problem-specific user cuts via cbCut(...). I do not use cbLazy(...) and do not set LazyConstraints = 1.

My solver parameters are:

PreCrush = 1   Method = 0   MIPFocus = 3   MIPGap = 0   TimeLimit = 900  

I believe this setup should be sufficient to add user cuts correctly, and indeed, Gurobi reports accepted user cuts in the log. However, I have a few questions:

1. I'm checking for violations at every MIP node. While this often reduces nodes and simplex iterations, it significantly increases total solve time — e.g., in the run below, 2708694 cuts were proposed but only 273 were accepted, with 337 seconds spent inside the callback:

With user-cuts:

Cutting planes:  

User: 273  

... 

Explored 14464 nodes (762783 simplex iterations) in 432.96 seconds (54.52 work units)
Thread count was 8 (of 8 available processors)

Solution count 10: 134.817 134.813 134.809 ... 124.807

Optimal solution found (tolerance 0.00e+00)
Best objective 1.348173896580e+02, best bound 1.348173896580e+02, gap 0.0000%

User-callback calls 36671, time in user-callback 337.84 sec

S1 cuts: 1 

S2 directional cuts: 2708694 

S2 subtour cuts: 72

Without user-cuts (baseline run):
Explored 26442 nodes (744735 simplex iterations) in 48.56 seconds (38.04 work units)
Thread count was 8 (of 8 available processors)

Solution count 10: 134.817 134.817 134.817 ... 124.825

Optimal solution found (tolerance 0.00e+00)
Best objective 1.348173896580e+02, best bound 1.348173896580e+02, gap 0.0000%

Is there a recommended way to avoid checking every node, or to check only every X nodes, for performance?

2. Is it correct to assume that Gurobi filters out most of the cuts (e.g., near-duplicate, weak, etc.), and only adds those that significantly help LP relaxation?

3.Interestingly, I observed that when I enable my user cuts, Gurobi ends up generating more internal cutting planes (e.g., flow cover, MIR, RLT, etc.) than in the baseline run without my cuts. Why does Gurobi generate significantly more internal cutting planes when user cuts are added? Does this mean the LP relaxation is improved, leading more structure and enabling more aggressive cut generation?

4. Given I'm adding cuts in MIPNODE with cbCut(...), and setting PreCrush = 1, am I using the correct approach for user cuts? Just confirming that LazyConstraints = 1 is not required in this context.

Thanks in advance!

関連

• Callbacks
• User Cuts
• Cuts

1

• 

  Riley Clement

  • Gurobi Staff

  2025年06月25日 01:27

  Hi Ozge,

  Is there a recommended way to avoid checking every node, or to check only every X nodes, for performance

  There's a couple of ways this could be achieved, for example, say you wanted to check approximately 20% of nodes

  i) generate a random number between 0 and 1 in your callback and exit if it is below 0.8, and run your cut routine otherwise

  ii) check if MIPNODE_NODCNT mod 5 is 0, if it is then run the cut routine, otherwise exit the callback

   

  Is it correct to assume that Gurobi filters out most of the cuts (e.g., near-duplicate, weak, etc.), and only adds those that significantly help LP relaxation?

  Yes.  There are other reasons a cut may be filtered too, such as orthogonality to other candidate cuts.  Note that even if the cut is not filtered out, it is not necessarily applied.  The solver will maintain a pool of potential cuts and apply (or even remove ones that have been applied) as it sees fit.

  Why does Gurobi generate significantly more internal cutting planes when user cuts are added?

  I'd need to run a lot of experiments before deciding what is causal, what is correlation and what is coincidence.  For example, you'd need to test not adding cuts, but keeping PreCrush=1, otherwise it is not a fair comparison.  There is a longer solve when adding your cuts, there would be a positive correlation between solve time and the number of cuts added.  You could set a time limit so that the solves all take the same time (and do not terminate due to MIP gap) but the time is still being affected by the callback, so maybe you'd need to run your cut routine to generate a cut, but not add it.  In summary - I don't think this question can be easily answered and any conclusions based on it would be spurious.

  Given I'm adding cuts in MIPNODE with cbCut(...), and setting PreCrush = 1, am I using the correct approach for user cuts? Just confirming that LazyConstraints = 1 is not required in this context.

  Indeed LazyConstraints=1 is not required for user cuts.

  - Riley

  0

サインインしてコメントを残してください。