How can binary variables be modeled using continuous variables?

268 Views Asked by At

In optimization, is it possible to model a binary variable using continuous variables?

For example, suppose that $X \in \{0,1\}$. Can I define it as $0 \leq X \leq 1$ and impose some additional constraints instead to force $X$ to become only $0$ or $1$?

1

There are 1 best solutions below

0
On

No.

Why would developers work on all these MIP solvers if there is an easy LP formulation?

We can write $x (1-x)=0$. But that does not really help. This is non-linear (quadratic) and non-convex, and you would need a global NLP solver (which often use Branch-and-bound).

Of course, using some Lagrange multiplier technique as suggested elsewhere, is similarly a waste of time. There is a correspondence between non-convexity and binary (integer) restrictions. There is no magic bullet that will get you from "difficult to solve" (discrete/non-convex) to "easy to solve" (linear or convex).