1
$\begingroup$

I would like to seek some advice on modeling the following:

I have two integer decisions variables, $x, x'$, that are either equal or greater than zero and either of them is greater than or equal to a third integer decision variable, $z$, which is also equal or greater than zero in accordance to the value of a binary indicator variable, $\beta$.

$\beta=1$ $\implies$ $x\ge z$

$\beta=0$ $\implies$ $x'\ge z$

Also, I would also like to about the case for the opposite too:

$\beta=1$ $\implies$ $x\le z$

$\beta=0$ $\implies$ $x'\le z$

Appreciate your kind guidance.

Thank you!

$\endgroup$

2 Answers 2

2
$\begingroup$

A non-linear formulation is given for $ x \geq 0$, $ x’ \geq 0$, $z \geq 0$ and $ \beta $ binary.

$\left\{ \begin{array}{l} x \geq \beta \cdot z \\ x’ \geq (1- \beta) \cdot z \\ \end{array} \right. $

If $ \beta = 1 $ we get

$\left\{ \begin{array}{l} x \geq z \\ x’ \geq 0 \\ \end{array} \right. $

If $ \beta = 0 $ we get

$\left\{ \begin{array}{l} x \geq 0 \\ x’ \geq z \\ \end{array} \right. $

Oppositive case

$\left\{ \begin{array}{l} z \geq \beta \cdot x \\ z \geq (1- \beta) \cdot x’ \\ \end{array} \right. $

The following formulation is linear, but it is valid only for $z < 1$.

$\left\{ \begin{array}{l} x \geq (\beta -1) + z \\ x’ \geq - \beta + z \\ \end{array} \right. $

As known, $ (0;1) \cong R$ meaning that a bijective function exists between the open interval and the set of real numbers. Also the generic interval $ (a;b) $ is isomorph to $ (0;1) $, $ (a;b) \cong (0;1) $ by means of the following bijection:

$ f(x):= (x-a)/(b-a) $

Thanks to this observation, the linear formulation of the logical constraints can be given changing the interval where variables are defined. From $ x \geq 0$, $ x’ \geq 0$, $z \geq 0$ and $ \beta $ binary, let introduce $ y := (x-a)/(b-a) $, $ y’ := (x’-a)/(b-a) $$ w := (z-a)/(b-a) $ where $a$ and $b$ are suggested from the context of the examinated problem.

‘> $\left\{ \begin{array}{l} y \geq ( \beta - 1) + w \\ y’ \geq - \beta + w \\ y \in (0;1) \\ y’ \in (0;1) \\ w \in (0;1) \\ \beta binary \\ \end{array} \right. $

$\endgroup$
3
  • $\begingroup$ Dear Marco, Thank you for your timely reply! May I ask If you are any linear formulations as I am dealing with a mixed-integer linear programming formulation. Thanks. $\endgroup$
    – Mike
    Sep 19, 2020 at 10:44
  • $\begingroup$ I wrote a linear formulation that is valid only for $z \leq 1$.$\left\{ \begin{array}{l} x \geq (\beta - 1) + z \\ x’ \geq - \beta + z \\ \end{array} \right. $ $\endgroup$ Sep 19, 2020 at 10:59
  • $\begingroup$ Dear Marco, thanks! $\endgroup$
    – Mike
    Sep 20, 2020 at 9:23
3
$\begingroup$

Let $y$ be a binary variable and let $f$ be a linear function bounded above by some constant $M$. The standard approach to enforce $y=1 \implies f\le 0$ is to impose linear big-M constraint $$f\le M(1-y)\tag1.$$ All four of your implications are of this form. For the first one, take $y=\beta$ and $f=z-x$ in $(1)$, yielding $z-x\le M(1-\beta)$. For the second one, take $y=1-\beta$ and $f=z-x’$ in $(1)$, yielding $z-x’\le M\beta$. The other two are similar.

$\endgroup$
1
  • $\begingroup$ Dear Dr Rob, Thank you! $\endgroup$
    – Mike
    Sep 19, 2020 at 16:23

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.