OR condition in a MILP

Question

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?

Answer 1

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.

Answer 2

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.