2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ No: you're modelling !($X \le 2) \equiv X \ge 3 \equiv X - 3 \ge 0$ $\endgroup$ – George Tomlinson Sep 26 '13 at 4:25
  • $\begingroup$ why do you not consider upper boundaries? $\endgroup$ – kuw Sep 26 '13 at 4:33
  • $\begingroup$ There's an upper boundary in the second constraint $\endgroup$ – George Tomlinson Sep 26 '13 at 4:39
  • $\begingroup$ But I might have the $\mu_1$ on the wrong side in the first constraint: just thinking about it. $\endgroup$ – George Tomlinson Sep 26 '13 at 4:45
  • $\begingroup$ 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 $\endgroup$ – George Tomlinson Sep 26 '13 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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