# Binary constraint integer programming problem

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.

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.

• No: you're modelling !($X \le 2) \equiv X \ge 3 \equiv X - 3 \ge 0$ – George Tomlinson Sep 26 '13 at 4:25
• why do you not consider upper boundaries? – kuw Sep 26 '13 at 4:33
• There's an upper boundary in the second constraint – George Tomlinson Sep 26 '13 at 4:39
• But I might have the $\mu_1$ on the wrong side in the first constraint: just thinking about it. – George Tomlinson Sep 26 '13 at 4:45
• I've given it some thought and found the answer: I had the $M1 \delta$ on the wrong side in the X constraint. Also you were right: I needed to include an upper boundary for X, which I've done in a third constraint. Also to, to respond to an earlier query I think you had, you could use $X \ge 3$ or $X \gt 2$, but I've changed it to the latter as you were more comfortable with that and it does underline that you're using 'if X then Y' $\equiv$ 'not X or Y' @kuw – George Tomlinson Sep 26 '13 at 9:27