Techniques to relax a MIP problem to reduce compute time

[Umar Waqas]

Dear all,

 

I am in search of techniques/literature/tools to relax a MIP problem in order to reduce the computation requirements.

Does YALMIP already does that? Any help/material/links in this regard are appreciated. Thanks in advance.

 

Kind regards,

Umar

[Johan Löfberg]

What do you mean with relaxing an integer program?

In YALMIP, simply don't define the decision variables as integers, and you have the continuous relaxation by definition. Alternatively, define your MIP as usual, and then tell YALMIP to skip the integrality constraints by sdpsettings('relax',1). Of course, that would be silly since then there is no reason to introduce integrality to begin with.

I guess you mean some more elaborate heuristics.

[Umar Waqas]

Hi Johan, all,

 

Thanks for your reply. In fact I a newbie so please excuse me if I use improper terminology.

 

What I mean with relaxing a Mixed Integer Program?

I have a problem formulated as MIP. It takes too long to get an optimal result. I would like to have a solution with reduced quality but faster.

Intuitively, what I understand that there are would be some ways to reformulate (what I think as relaxation) the problem such that it becomes easier to solve for YALMIP or any other solver. Following are my questions:

 

1. Are there existing such reformulation techniques which allow the solver to get a solution faster?
2. Does YALMIP implements one of those techniques?

Thanks in advance for your time and effort.

 

Kind regards,

Umar

[Johan Löfberg]

What do you mean with reduced quality? Sub-optimal? Then you simply decrease the tolerance in the solver options, or introduce a time-limit etc.

There is no general way. If it was, it would always be used. Most solvers have a lot of parameters though to tweak cutting planes, b&b and heuristics, and all of them are of course available though YALMIP.