Question about new constraint and reoptimize
AnsweredI'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.
-
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 -
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.
Comments
2 comments