3
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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$$

$\endgroup$
5
  • $\begingroup$ 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! $\endgroup$ Oct 20, 2022 at 17:19
  • 1
    $\begingroup$ Related: or.stackexchange.com/questions/6641/… $\endgroup$
    – RobPratt
    Oct 20, 2022 at 18:14
  • $\begingroup$ 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. $\endgroup$ Oct 20, 2022 at 18:20
  • $\begingroup$ 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? $\endgroup$ Oct 20, 2022 at 18:30
  • $\begingroup$ Yes, or you can just replace each $y^-$ with $1-y$ and omit the equality constraint. $\endgroup$
    – RobPratt
    Oct 20, 2022 at 19:40
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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 $. $\endgroup$ Oct 24, 2022 at 19:52
  • $\begingroup$ 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. $\endgroup$ Oct 25, 2022 at 1:29
  • $\begingroup$ @RobPratt Yes. I implemented Prof. Rob's brilliant solution with one constraint by substituting $y^+ =1-y-y^- $. It works magically. $\endgroup$ Oct 25, 2022 at 1:59
  • $\begingroup$ Please see the above comments that I implemented. $\endgroup$ Oct 25, 2022 at 2:00

Your Answer

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

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