3

I am trying to formulate indicator-type of constraints. $y$ is binary $0$ or $1$ and $x$ is a continuous variable. $$ y = \begin{cases} 1, & \text{ if } a \leq x \leq b \\ 0, & \text{ Otherwise } \end{cases} $$

The question is how to model this using linear constraints? I have researched and done my homework below with thoughts:

  1. Define binary $$ y_1 = \begin{cases} 1, & \text{ if } a \leq x \\ 0, & \text{ Otherwise } \end{cases} $$

Define binary $$ y_2 = \begin{cases} 1, & \text{ if } x \leq b \\ 0, & \text{ Otherwise } \end{cases} $$

Big-M methods can be used to define linear constraints for $ x, y_1 $ and $ y_2.$

  1. Enforce $ y=1 $ if both $ y_1=1 $ and $ y_2=1 $; $ y=0 $ otherwise, as follows: $$ y \leq y_1, y \leq y_2, y \geq y_1+y_2-1 $$

However I ended up with two many ( 4 with Big-M methods and 3 above) constraints. I was wondering if anyone has other more efficient or better approaches?

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
GuanghuiLiu
  • 53
  • 5

2 Answers2

3

Suppose $\ell \le a \le b \le u$, where $\ell$, $a$, $b$, and $u$ are constants. Introduce binary variables $y^-$ and $y^+$, and impose the following linear constraints: $$\ell y^- + a y + b y^+ \le x \le a y^- + b y + u y^+ \\ y^- + y + y^+ = 1$$ If you want to avoid the ambiguity at $x=a$ and $x=b$, introduce a small constant $\epsilon > 0$ and instead impose $$\ell y^- + a y + (b + \epsilon) y^+ \le x \le (a - \epsilon) y^- + b y + u y^+ \\ y^- + y + y^+ = 1$$

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • Your solution is amazing! It's awesome and admirable - 2 lines of your codes solved the problem. I tried to find any holes with your solution but ended up with being convinced after considering all sorts of case work with your solution. Thank you so much for your very intelligent and efficient solution! – GuanghuiLiu Oct 20 '22 at 17:19
  • 1
    Related: https://or.stackexchange.com/questions/6641/write-in-ilp-if-x-within-range-then-s-1-else-0 – RobPratt Oct 20 '22 at 18:14
  • Hi Rob: I would like to get your expert suggestions on the one-side variant: $ y $ is binary 0 or 1. $ x $ is a continuous variable. $$ y = \begin{cases} 1, & \text{ if } x \geq a \ 0, & \text{ if } x <a \end{cases} $$ using your $\epsilon $ method. – GuanghuiLiu Oct 20 '22 at 18:20
  • I modify your code as below $$\ell y^- + a y \le x \le (a - \epsilon) y^- + My \ y^- + y = 1$$, where $ M $ is an upper bound of $ x, $ and $ y^-, y $ are binary. Is it correct? – GuanghuiLiu Oct 20 '22 at 18:30
  • Yes, or you can just replace each $y^-$ with $1-y$ and omit the equality constraint. – RobPratt Oct 20 '22 at 19:40
1

I can think of:

a <= xy, since a/x will b smaller than 1, so y ==1.

Similarly, x <= by.

If want to avoid bilinear terms then z+y =1, then az <= x

If it's AND situation which means both have to be true:

a <= xy1

x <= by2

both y1 & y2 are binary followed by

2y <= y1+y2

Sutanu Majumdar
  • 3,461
  • 1
  • 2
  • 11
  • Thanks for your thoughts. $ a \leq xy $ will ensure that if $ x \geq a $ then $y=1$. But if $x<a$ , it will not force $y=0 $ because $ y \geq a/x > 1 $. – GuanghuiLiu Oct 24 '22 at 19:52
  • That's true, it will be infeasible. So only way is what Prof Rob has suggested above, unless as you have mentioned, you want to use bigM method. – Sutanu Majumdar Oct 25 '22 at 01:29
  • @RobPratt Yes. I implemented Prof. Rob's brilliant solution with one constraint by substituting $y^+ =1-y-y^- $. It works magically. – GuanghuiLiu Oct 25 '22 at 01:59
  • Please see the above comments that I implemented. – GuanghuiLiu Oct 25 '22 at 02:00