Branch-and-cut performance and PreCrush

Answered

Cheng-Lung Chen

• October 04, 2021 16:42

Hello, 

I am implementing a branch-and-cut algorithm with my own user cuts. Initially, I forgot to change the PreCrush parameter to 1. I quickly realize this is necessary for user cut callback and I fix it in the second round of experiment. 

However, I notice that even I forgot to set PreCrush to 1 in the first experiment, there are still user cuts added. And the optimal gap when time limit hit for first experiment is actually better than the second experiment where PreCrush was set to 1. 

All other parameters (PreSolve, Heuristics, Cuts) were in their default setting between these two experiment, the only thing changed is PreCrush. I am wondering if I got a worse result when adjusting PreCrush to 1, what does that mean for my user cuts and problem?

Any insights is appreciated. 

0

• 

  Maliheh Aramon

  Gurobi Staff

  • October 05, 2021 01:20
  • Edited

  Hi Cheng-Lung,

   

  The user cuts are expressed with respect to the decision variables of the original model. Setting the PreCrush parameter to 1 shuts off a few reductions to allow the presolve to represent the user cuts in terms of the decision variables defining the presolved model.
  
  Are you sure that your cuts are not silently ignored when \(\texttt{PreCrush}=0\)? Have you tried to solve the model without user cuts to make sure that the addition of user cuts improves the performance? It is likely that the benefit of the extra presolve procedures, which are turned off by setting \(\texttt{PreCrush}=1\), is greater than the benefit of adding user cuts. Could you please share the log files of your runs with different \(\texttt{PreCrush}\) values? It would be great if you could share the log file without the user cuts as well. 

   

  Best regards,

  Maliheh

  0
• 

  Cheng-Lung Chen

  • October 05, 2021 07:54

  

  

  

  Hello Maliheh,

  Thanks for responding! I did a couple of experiment and you are correct. The Gurobi presolve, heuristics and cuts are so powerful that the optimization performance is actually better without my user cuts (which is derived from a substructure aka relaxation not the entire problem). 

  However, when I turn off the presolve, heuristics and cuts, both optimality gap and number of b&c nodes are smaller and better for the problem with my user cuts than without them. But that's just a limited observation as my problem is network optimization, the topology and density of network might also play some roles in optimization performance as well. 

  I just need to revise my experiment and setting and presentation strategy to address my contribution for the polyhedral study I have done. Thanks so much!

  0

Please sign in to leave a comment.