Methods to solve MIP
149 views
Skip to first unread message
Vladimir Stozhkov
Jun 1, 2012, 7:10:09 PM6/1/12
to Gurobi Optimization
Hello.
I am trying to solve Linear Assignment Problem that is actually
polynomial. The solution polyhydron must be integral. So, LP
relaxation of MIP must provide the same objective.
Right now I am solving MIP. But apparently it works very slowly. I
tried to solve the corresponding LP but the problem is that Gurobi
gives me a solution that is not a basic feasible solution but convex
combination of them, i.e. rational and not integer. I need an integer
optimal solution. I suppose method GRBModel.optimize() uses barrier
method by default. How can I switch it to simplex? It seems to me that
simplex method will give me an integral solution, right?
I found this explanation http://www.gurobi.com/documentation/5.0/reference-manual/node694
but I can't conceive how I can apply it in my C++ environments. What
is the name of this method? What type of Gurobi variable should I use
to switch methods of optimization?
Kind regards,
Vladimir.
I am trying to solve Linear Assignment Problem that is actually
polynomial. The solution polyhydron must be integral. So, LP
relaxation of MIP must provide the same objective.
Right now I am solving MIP. But apparently it works very slowly. I
tried to solve the corresponding LP but the problem is that Gurobi
gives me a solution that is not a basic feasible solution but convex
combination of them, i.e. rational and not integer. I need an integer
optimal solution. I suppose method GRBModel.optimize() uses barrier
method by default. How can I switch it to simplex? It seems to me that
simplex method will give me an integral solution, right?
I found this explanation http://www.gurobi.com/documentation/5.0/reference-manual/node694
but I can't conceive how I can apply it in my C++ environments. What
is the name of this method? What type of Gurobi variable should I use
to switch methods of optimization?
Kind regards,
Vladimir.
Greg Glockner
Jun 4, 2012, 7:10:37 PM6/4/12
to gur...@googlegroups.com
By default, Gurobi will return a basic feasible solution; if barrier is run, then it will run a crossover algorithm to produce a basic feasible solution.
Vladimir Stozhkov
Jun 5, 2012, 12:14:34 PM6/5/12
to Gurobi Optimization
Also, Greg. I encountered with another problem.
I am solving Linear Assignment Problem and I need to find all integer
solutions. It is known that LP relaxation of the corresponding MIP
gives the optimal solution. So, I can use simplex method to solve LP
relaxation and it ends up in an integer vertex (the polyhedron in
question is integral). How can I find other optimal vertices of the
original polyhedron (if I try to add some new constraints to exclude
already obtained integer basic feasible solutions then I will change
the initial polyhedron).
Thank you for assistance.
I am solving Linear Assignment Problem and I need to find all integer
solutions. It is known that LP relaxation of the corresponding MIP
gives the optimal solution. So, I can use simplex method to solve LP
relaxation and it ends up in an integer vertex (the polyhedron in
question is integral). How can I find other optimal vertices of the
original polyhedron (if I try to add some new constraints to exclude
already obtained integer basic feasible solutions then I will change
the initial polyhedron).
Thank you for assistance.
Greg Glockner
Jun 6, 2012, 4:58:17 PM6/6/12
to gur...@googlegroups.com
> How can I find other optimal vertices of the
> original polyhedron (if I try to add some new constraints to exclude
> already obtained integer basic feasible solutions then I will change
> the initial polyhedron).
There is no feature of the software to do this. You will have to do this by modifying the model.
> original polyhedron (if I try to add some new constraints to exclude
> already obtained integer basic feasible solutions then I will change
> the initial polyhedron).
Reply all
Reply to author
Forward
0 new messages