3
$\begingroup$

I have 4 variables. Xl6, Xs6, Pl6, Ps6. I have a constant C as well.

Xl6 and Xs6 are binary whereas Pl6 and Ps6 are integers. Also, all variables can take only positive values.

I have to implement following constraints in an MIP:

If Xl6 == 0 then Pl6 == 0 else Pl6 > 0
If Xs6 == 0 then Ps6 == 0 else Ps6 > 0

Another set of if-else constraints are:

if Xl6 == 1 and Xs6 == 1 then Pl6 + Ps6 >= C
elif Xl6 == 1 and Xs6 == 0 then Pl6 >= C
elif Xl6 == 0 and Xs6 == 1 then Ps6 >= C

Also, we have another constraint that Xl6 and Xs6 both can't be zero at the same time. This has been implemented as Xl6 + Xs6 >= 1.

How can we formulate above set of conditions as linear constraints?

$\endgroup$

3 Answers 3

5
$\begingroup$

For the first part, let $Ul6$ and $Us6$ be upper bounds on $Pl6$ and $Ps6$, respectively, and impose linear constraints: \begin{align} Xl6 \le Pl6 &\le Ul6 Xl6 \\ Xs6 \le Ps6 &\le Us6 Xs6 \end{align} For the second part: \begin{align} Pl6 + Ps6 &\ge C(Xl6 + Xs6 - 1) \\ Pl6 &\ge C(Xl6 - Xs6) \\ Ps6 &\ge C(Xs6 - Xl6) \end{align}

$\endgroup$
2
  • $\begingroup$ Hi @RobPratt, Do you mean $Ul6$ and $Us6$ are upper bounds of $Pl6$ and $Ps6$ respectively? since $Xl6$ and $Xs6$ are already binary. $\endgroup$
    – mufassir
    Feb 3 at 9:41
  • $\begingroup$ @mufassir Yes, corrected. $\endgroup$
    – RobPratt
    Feb 3 at 13:43
4
$\begingroup$

$ \sigma Xl6 \le Pl6 \le UXl6 $
$ \sigma Xs6 \le Ps6 \le UXs6 $
$\sigma$ is very small nonnegative number (even 1 as Prof Rubin suggested since PPl/Ps are integers) & $U$($ \gt$ C) is upper bound for Pl & Ps

$C(Xl6+Xs6 -1) + U(Xl6+Xs6-2) \le Pl6 + Ps6$
$CXl6 - U(Xl6+2Xls6-1)\le Pl6$
$CXs6 - U(2Xl6+Xls6-1)\le Ps6$

$ 1 \le Xl6 + Xs6$ as you've already

If both integer vars can take positive values only then 2nd bunch of constraints can be replaced by
$CXl6 \le Pl6$
$CXs6 \le Ps6$

$\endgroup$
6
  • 1
    $\begingroup$ Since the $P$ variables are integers, $\sigma=1$ will work. The second group of constraints needs some corrections. For instance, if $Xl6=0$ and $Xs6=1,$ the middle constraint in the second group forces $Pl6\ge C$ which is not part of what was requested. $\endgroup$
    – prubin
    Jan 31 at 21:17
  • $\begingroup$ copy-pasting error, corrected it. $\endgroup$ Jan 31 at 21:20
  • $\begingroup$ this is make Pl/Ps free (instead of $\ge 0$) if Xs/Xl = 1 $\endgroup$ Jan 31 at 21:27
  • $\begingroup$ Your final two constraints are too strong when both $X$ variables are $1$. $\endgroup$
    – RobPratt
    Feb 1 at 1:50
  • $\begingroup$ So you mean, if both are 1, then possible the Ps individually may be smaller than C? But if either Xs are 1, the corresponding Ps are greater then C. $\endgroup$ Feb 1 at 1:56
3
$\begingroup$

I am assuming that pl6 is a non-negative integer. (tell me if it holds).
For Xl==0 then Pl6 ==0 you can have :

Pl6<= Xl6

This tells you that if Xl6 = 0 : Pl6<= 0 and since it takes >=0 values , it has to be 0.

Pl6>= Xl6/M where M is a really big integer. Now if Xl6==1 Pl6>1/M --> Pl6 >0


For the second type of contraint:

Pl6 + Ps6 >= C(Xl6 + Xs6 - 1)

Notice that if and only if Xl6 = Xs6 = 1 the right-hand will be exactly C. If both are 0 it will be negative (and therefore do nothing) , and if one of them is 1 if will be 0.

(Everything I said holds if P's are non-negative)

$\endgroup$
3
  • $\begingroup$ yes, all variables are positive. $\endgroup$
    – mufassir
    Jan 31 at 19:48
  • 1
    $\begingroup$ Hey, thank you for attempting this. I see few issues here. In part 1, Pl6<=Xl6 will restrict Pl6 to be 1 or 0 only in case of Xl6=1 , which we don't want. $\endgroup$
    – mufassir
    Jan 31 at 19:57
  • $\begingroup$ in part 2, we want RHS to be greater than C, not greater than 0. $\endgroup$
    – mufassir
    Jan 31 at 19:58

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.