3
$\begingroup$

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?

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.