[Math] Binary constraint integer programming problem

linear programming

I have a question to the folowing question:

Explain how to use integer variables and linear inequality constraints to ensure:

A) let $x$ and $y$ be integer variables bounded at 1000. How can you ensure that whenever $x\leq 2$ we have $y\leq 3$. Assume $x$ and $y$ are positive integers.

I've tried to make a constraint for the case where when $x>2$ then $y$ is not restricted as long as it is positive. By introuducing a binary variable $z$, i can assume that when $z=0$ then $y$ is not restricted: $x \leq 2 + M(z)$ and
$y \leq 3 + 997(1-z)$
where $M$ is some big integer. Obviously the inequalities are not making that much sense but this was my attempt to solve it.

Any tips would be appreciated.

Best Answer

If $X \le 2$, $Y\le 3$ is equivalent to $X \gt 2$ or $Y \le 3$ which can be modelled with the following 2 constraints:

$X - 2 + M_1 \delta \gt 0$

$Y - 3 \le M_2 (1- \delta )$

$X \le 1000$

where $\delta$ is a binary variable, $M_1 = 2$ and $M_2 = 1003$.

The values of $M_1$ and $M_2$ are chosen to allow the full posible range of values for X and Y. The constraints become

$X - 2 + 3 \delta \gt 0$

$Y - 3 \le 1003 (1- \delta )$

$X \le 1000$

When $\delta = 0, X \gt 2$ so the only requirement on Y is that it be $\le$ 1000, precisely what the second constraint becomes when $\delta = 0$ is substituted in.

When $\delta = 1$ the first constraint becomes $X \gt 0$, thus allowing $X \le 2$ and so we need Y$\le 3$, which is what the Y constraint becomes when $\delta = 1$ is substituted in.

Related Question