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

• 

  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

Please sign in to leave a comment.