# OR condition in a MILP

I have the following constraint requirements.

2.x1-x2 = 0 OR x1 - 2.x2 = 0

x1,x2 are positive integers less than a given value, say 10 for the question

How do I implement this? Basically its looking for integers on the line x1 = 2.x2, or x1 = 1/2.x2

The solution is clearly not a convex hull. I presume there must be some formulation using a binary variable.

Is there a general approach to implementing constraint1 OR constraint2?

Disjunctions ("or" constraints) are typically implemented by adding a binary variable to choose one disjunct or the other, plus constraints to enforce that choice. What you have in mind can be done with "big M" constraints, provided that your $$x$$ variables are bounded. Let $$y\in\lbrace 0,1 \rbrace$$ be 1 if $$x_1 = 2x_2$$ and 0 if $$x_2 = 2x_1$$. Assume that we know a priori that $$x_1 \in [L, U].$$ If $$x_1 = 2x_2,$$ then $$2x_1 - x_2 = 1.5x_1 \in [1.5L, 1.5U].$$ If $$2x_1 = x_2,$$ then $$x_1 - 2x_2 = -3x_1\in [-3U, -3L].$$ Using that, we add the following constraints: $$-3U(1-y) \le x_1 - 2x_2 \le -3L(1-y)\\ 1.5Ly \le 2x_1 - x_2 \le 1.5Uy.$$ If $$y=1$$, the first constraint enforces $$x_1 = 2x_2$$ and the second constraint has no effect. If $$y=0$$, the second constraint enforces $$x_2 = 2x_1$$ and the first constraint has no effect.

To make things more precise, suppose we are given: 1 <= X1, X2 <= 10; The so-called disjunctive formulation is:

! Case A;

X1A = 2 * X2A;

X1A <= 10 * ZA;  ! Enforce upper bounds;

X2A >= 1 * ZA;   ! Enforce lower bounds;


! Case B;

X2B = 2 * X1B;

X2B <= 10 * ZB; ! Enforce Upper bounds;

X1B >= 1 * ZB;  ! Enforce lower bounds;


! Tie all the cases together;

ZA + ZB = 1;    !Must choose 1 of the cases;

X1A + X1B = X1;

X2A + X2B = X2;


! ZA and ZB = 0 or 1;

Suppose we choose the arbitrary objective:

Max = X1 + 0.9* X2;

If you relax the requirement that ZA, ZB = 0 or 1 to:

0 <= ZA, ZB <= 1, and solve the resulting Linear(not integer) program, you get the naturally integer solution:

 Variable           Value
X1A        10.00000
X2A        5.000000
ZA        1.000000
X1        10.00000
X2        5.000000


So Branch-and-Bound is not required in this particular example for this formulation. Other formulations may not have this nice quality.