Is it possible to model a logical OR without boolean variables in linear programming?

0
votes

I want to state a linear model where I can't use boolean variables due to efficiency reasons. I can only use a solver that can handle boolean variables not that efficiently. And in a productive model I would need hundreds of those variables.

I use a boolean variable to decide if I can satisfy demand either from one source (continuous variable A) or another source (continuous variable B) but not both. The constraint is:

A + B >= demand

But either A OR B can be non-zero. This can be ensured by using a boolean variable (Bool_A) and the following constraints:

A <= 1000 * Bool_A

B <= 1000 * (1- Bool_A)

If Bool_A = 1, then the variable A can take non-zero values and B is forced to 0, and if Bool_A = 0 then vice versa.

My question is now: does anyone know, if it is possible to model this using only linear variables (no booleans and integer variables) or has a proof that it is not possible.

1
linear-programmingboolean-logic
Proof: use convexity ("or" is non-convex so can never be implemented in a pure LP) - Erwin Kalvelagen
Erwin, thanks for this! Great hint to look for the convexity! I could not see the forest for the trees and did not think that convexity is the key! - stahldonnerklinge

1 Answers

1
votes

In Brown, G. and Dell, R., "Formulating linear and integer linear programs: A rogues’ gallery" the following linear programming formulation for the XOR (exclusive or) can be found :

X = A xor B

resolves to

X ≤ A + B
X ≥ A - B
X ≥ - A + B
X ≤ 2 - A - B

Using an auxiliary variable:

X = A + B - 2*H
H ≤ A
H ≤ B
H ≥ A + B - 1
H ≥ 0