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

| improve this answer | |
$\endgroup$
  • $\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 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$ – marco tognoli Sep 19 at 10:59
  • $\begingroup$ Dear Marco, thanks! $\endgroup$ – Mike Sep 20 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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Dear Dr Rob, Thank you! $\endgroup$ – Mike Sep 19 at 16:23

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.