Originally posted by: kreitzpa

Hi all,

I have been trying to find a way to relax binary variables while trying to drive them towards either 1 or 0. 

For a constant M>>1 the minimum value of the penalty term M*b(1-b) for b \in [0,1] is when either b=0 or b=1.  I figured I would be able to add this to the objective function and try and minimize the objective function but I get that it is a nonconvex function.  I understand why this gives an error, but is there a way to successfully implement this trick?  Or a similar trick in order to relax binary variables while driving them to either 0 or 1?  I really want to see if I can make my MILP just an LP.

Thanks

Your model would not be linear program (LP) but a quadratic program (QP). CPLEX can solve non-convex QPs (see here and parameter CPX_PARAM_OPTIMALITYTARGET). However, solving non-convex QP to global optimality requires branching as well, so that may not improve things for you.

I'm pretty sure everyone mucking with IP models has asked himself/herself this question at one time or another (myself included), and to date the answer has always been "no way". If you can find a way to relax a binary ILP model to an LP model while preserving linearity, convexity etc. (and keeping the solution the same), I'm pretty sure you will have a proof in hand that NP = P. Since most people believe NP != P, I'm not optimistic about your chances.