Generating cuts to remove current LP solution

[Minh Vu Duc]

Hi Gurobiers,

I solve a LP. I would like to know there are methods or functions that help me to generate cuts that allow me to remove the solution to LP in the next solution. If not, there is someway (and how I should do) to obtain information from the current LP solution and generate cuts for the next LP.

Best,

M.

[Kostja Siefen]

Dea Minh,

cutting planes ("cuts") are constraints used for (mixed-)integer problems that remove non-integer solutions from the set of feasible solutions of the LP relaxation. So there is nothing like a cut for pure LP problems.

If you are trying to enumerate (optimal) solutions for your LP by iteratively removing previous solutions please keep in mind that the number of optimal solutions can be infinite.

Kostja

[Minh Vu Duc]

Hi Kostja

Many thanks for your comments. I have a MIP problem which has a special structure. In each iteration, I typically remove the current LP solution by modifying the model, until when no modification can be performed. At this step, I need to add cuts to remove the LP solution.  And this is the question of this thread. 

 

And I believe it could work in my case, especially for "hard instances" inwhich solving a big MIP is much harder (time-consuming) than a series of LP.

If you know how I can implement the cut, please explain some ideas to me.

Best,

Vào 05:08:30 UTC-5 Thứ Hai, ngày 09 tháng 11 năm 2015, Kostja Siefen đã viết:

[Tobias Achterberg]

Hi Minh,

the main question is whether you are solving your MIP as a MIP, or whether you
just pass the LP relaxation of your MIP to Gurobi and let Gurobi solve it as an LP.

In the former case, you would use a callback to separate cuts while Gurobi is
solving the MIP. In the latter case, your cutting planes are just ordinary rows
of the LP which you add as usual using GRBaddconstr() (or corresponding methods
in other APIs). After adding one more multiple cuts you would typically resolve
your LP with the dual simplex algorithm, because adding cuts only destroys
primal feasibility but not dual feasibility.

Or is your question about how to find cuts that cut off the current LP solution?
This you would have to answer yourself, because this obviously depends on the
model you are trying to solve.


Tobias

> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "Gurobi Optimization" group.
> To unsubscribe from this group and stop receiving emails from it, send an email
> to gurobi+un...@googlegroups.com <mailto:gurobi+un...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout.

[Minh Vu Duc]

Hi Tobias,

Many thanks for your reply. I am very appreciate your reply, I  have no much experience about primal method and dual method, so it is valuable for me. 

More specifically, I would like to generate a Gomory's cut to cut off the current solution to LP (the original model has only binary variables). Could you elaborate what I should do using Gurobi's API (C++ specifically) to achieve the goal.  

Best,

 

Vào 08:59:45 UTC-5 Thứ Ba, ngày 10 tháng 11 năm 2015, Tobias Achterberg đã viết:

[T.]

Selecting efficient and numerically stable Gomory mixed-integer (GMI) cuts is quite a difficult task, though the algorithm for computing them is not very difficult. I doubt, you will be able to generate better GMI cuts by hand than gurobi does.

Still, for calculating these cuts, you need the C API, as the advanced simplex routines are not available in the C++ API.