Question about new constraint and reoptimize

Answered

Rafael González

May 07, 2019 16:57 Edited

• 
• 
• 

I'm implementing the Grötschel-Holland algorithm for solving the matching problem using linear programming. The key of this algorithm is that its use a few restriction of the matching polyhedron and, if the solution hasn't integer coordinates, find a good cut-plane and optimize again. I'm working in Python.

My question is: If I create a model "m",I optimize it using m.optimize() and I add some constrains using m.addConstr, when I optimize again Gurobi use again the pre-solve or it use some information of the previous optimization process.

I'm a little surprised because I'm doing a time-computation analysis versus the integer programming method with Gurobi and I'm getting: for less than 1000 edges, GH is better, and for more the integer solver is better.

Thank you.

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  December 06, 2024 00:59

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Daniel Espinoza

  May 07, 2019 19:23

  Hi Rafael,

  Well, if you are solving an LP, and you want to reuse previous information (e.g. the basis), then I recommend either disabling dual reductions, or even disabling all presolve. That might ever further speed-up the LP approach. Also, it might be that finding your good cut is too time consuming in python, I would do some time profiling of that part.

  1
• 

  Rafael González

  May 08, 2019 17:08

  • 
  • 
  • 

  Hi Daniel, 

  For  the matching problem there are some heuristics for finding cutting planes without using flow-networks methods.

  Disabling dual-reductions works incredible. 

  Thank you very much.

  0

Post is closed for comments.