Express the constraint "$x = 0$ or $y = 0$" in linear programming

Question

How to express the constraint "$x = 0$ or $y = 0$" in a linear program? Is it possible at all?

Answer 1

I am afraid that is not possible in a pure continuous Linear Programming problem.

A quadratic formulation would look like: $$ x \cdot y=0 $$ but that is a nasty one also. Most quadratic solvers don't like this one.

If you can solve MIP (Mixed Integer Programming) problems, you could introduce a binary variable $\delta$ and formulate: $$ \begin{align} &x \le M_1\delta \\ &y \le M_2(1-\delta)\\ &\delta \in \{0,1\}\\ & x,y \ge 0 \end{align} $$ where $M_1$ and $M_2$ are upper bounds on $x$ and $y$ (these should be chosen as tight as possible).

Just to be complete: a more esoteric way is to use SOS1 variables (Special Ordered Sets of type 1). Some solvers support this thing. Usually I recommend the above formulation using the binary variable.

Finally you could solve the problem twice. One time with $x=0$ and then with $y=0$. Pick the solution that is best. Of course that would not work if you have many of these constructs in the model. In that case the MIP route is probably best.