I have a MILP problem with binary variables and the algorithm required to solve the problem says that once the problems is seperated into master and sub problems the binary variables should be used only in the master problem and then in solving the subproblem the binary variables are relaxed to be continous so I'll appreciate If I could get an explanation or a hint on how to relax binary variables to be continous
Hi Farouk,
In the case that you mentioned, relax binary variables mean that your binary variables in the subproblem should have a continuous [0,1] domain instead of {0,1}; and it is not necessary additional constraints (as I did in the paper that you requested).
Hi Alireza, I'm not sure what you mean by unrelaxation. Could you explain it a little bit?
Hi Petra Maria Bartmeyer
My question is about after relaxation,
Suppose I have a set of binary variables x∈{0,1}^N, wherein in the context of my optimization problem these binary parameters mean to include the parameter in a model or not include it, where there is a total of N parameters. If one was to solve this problem using the standard techniques of integer programming, i.e., continuous relaxation 0≤x≤1, I arrive at a troublesome point because the relaxation of the variable (which means include or not include) makes no sense (I can't include 3/4 of a parameter in the model).
This seems like a problem that many would inevitably run into, so I was curious how people would resolve this problem. The only way seems to reformulate the model, but I'd be very curious if you could give insight.
Thanks for the explanation Alireza! At this point, what I'm doing to avoid the problem you just described is using a penalization parameter BigM. If the BigM value is large enough, the x value will be close to an integer value {0,1}. In my experience, the difference between the x value and the nearest integer will be smaller than 1e-5, which is similar to the approximations allowed by commercial solvers (for instance, Gurobi considers 1e-5 as default for integer feasibility https://www.gurobi.com/documentation/9.5/refman/intfeastol.html).
Petra Maria Bartmeyer Thank you for your guidance, Petra! best wishes!
Do you say that I need to penalize objective value?
could you explain how can I do penalize exactly for binary relaxation?
Is This correct?
main objective func. + BigM*(|v|^2-|v|)
Yes! It's precisely like that main objective func. + BigM*(|v|^2-|v|).
Note that, for better numeric stability the BigM should note be giant, just large enough to achieve the necessary integer feasibility.
Petra Maria Bartmeyer very thanks, what about SDP problems?
can we apply such a method to these problems?
Hi Alireza, I never worked with SDP methods. I have no idea if they can be a nice fit for the binary relaxation.
- Badges
- Science topic
- Similar topics
- Engineering
- Control Theory
- Control Systems
- Control Systems Engineering