4
$\begingroup$

I have five integer variables, and I need to write some constraints on them:

$x_0$ , $[x_1, x_2, x_3, x_4 ]$. $1 \leq x_i \leq 3$

  • if $x_0 =1$ then no constraint on $[x_1, x_2, x_3, x_4 ]$
  • if $x_0 =2$ then 1 $\in$ $[x_1, x_2, x_3, x_4 ]$
  • if $x_0 =3$ then 1,2 $\in$ $[x_1, x_2, x_3, x_4 ]$

What is the most efficient way of doing it?

$\endgroup$
1

3 Answers 3

6
$\begingroup$

Here is one option: first define $x_i$ with binaries:

\begin{align} x_i&=y_i^1+2y_i^2+3y_i^3 \\ 1&=y_i^1+y_i^2+y_i^3 \\ y_i^j &\in \{0,1\} \end{align}

You can enforce $x_0=2 \implies 1 \in [x_1,x_2,x_3,x_4]$ with: $$ y_0^2 \implies \bigvee_{i=1}^4 y_i^1 \quad \equiv \quad y_0^2 \le \sum_{i=1}^4 y_i^1 $$

And $x_0=3 \implies 1,2 \in [x_1,x_2,x_3,x_4] $ with $ y_0^3 \implies (\bigvee_{i=1}^4 y_i^1) \wedge (\bigvee_{i=1}^4 y_i^2)$:

$$ y_0^3 \le \sum_{i=1}^4 y_i^1 \\ y_0^3 \le \sum_{i=1}^4 y_i^2 $$

$\endgroup$
2
  • $\begingroup$ Your $\ge 1-(2-x_0)$ is too restrictive when $x_0=3$. $\endgroup$
    – RobPratt
    Commented Apr 15, 2023 at 12:16
  • $\begingroup$ Yes, thank you !! safer to work with binaries all the way. $\endgroup$
    – Kuifje
    Commented Apr 15, 2023 at 12:22
3
$\begingroup$

Here’s a binary-expansion-based modification of @Kuifje’s formulation, and it uses fewer variables and constraints, but the last two are quadratic:

\begin{align} x_i&=y_i^1+2y_i^2 &&\text{for $i\in\{0,\dots,4\}$}\\ 1&\le y_i^1+y_i^2 &&\text{for $i\in\{0,\dots,4\}$}\\ y_i^j &\in \{0,1\} &&\text{for $i\in\{0,\dots,4\}$ and $j\in\{1,2\}$}\\ y_0^2 &\le \sum_{i=1}^4 y_i^1 (1-y_i^2) \\ y_0^1 + y_0^2 -1&\le \sum_{i=1}^4 y_i^2 (1-y_i^1) \end{align}

There are $196$ feasible solutions.

PORTA yields the following (linear) formulation with $10$ variables and $21$ constraints for the $y$ space: \begin{align} y_i^1 + y_i^2 &\ge 1 &&\text{for $i\in\{0,\dots,4\}$} \\ y_i^j &\le 1 &&\text{for $i\in\{0,\dots,4\}$ and $j\in\{1,2\}$} \\ \sum_{i=0}^4 y_i^2 &\le 4 \\ y_0^1 + y_0^2 + \sum_{i=1}^4 y_i^1 &\le 5 \\ \sum_{i=0}^4 \sum_{j=1}^2 y_i^j &\le 7 + y_k^1 + y_k^2 && \text{for $k\in\{1,2,3,4\}$} \\ \end{align}


For comparison, note that PORTA yields the following formulation with $15$ variables and $26$ constraints for @Kuifje's $y_i^j$: \begin{align} \sum_{j=1}^3 y_i^j &= 1 &&\text{for $i\in\{0,\dots,4\}$}\\ y_i^j &\ge 0 &&\text{for $i\in\{0,\dots,4\}$ and $j\in\{1,2,3\}$} \\ y_0^3 &\le \sum_{i=1}^4 y_i^2 \\ \sum_{i=0}^4 y_i^3 &\le 3 + y_k^3 &&\text{for $k\in\{1,2,3,4\}$}\\ \sum_{i=0}^4 (y_i^2+y_i^3) &\le 4 \end{align}

$\endgroup$
2
  • 1
    $\begingroup$ I finally did this. $\forall_{n} \sum_{j\in A_0} y_{j,n} \geq \sum_{m>n} y_{0,m} $ Where $A_0 = [x_1, x_2,x_3,x_4]$ $\endgroup$ Commented Apr 15, 2023 at 22:12
  • 1
    $\begingroup$ @Optimizationteam Yes, that is correct. $\endgroup$
    – RobPratt
    Commented Apr 17, 2023 at 2:15
-1
$\begingroup$

As @RobPratt implies an integer can be expressed as $2^{n}y^{n}$ with $ n =\{0,1,2,...\}$ & $y$ as binary.
So integers $[x_i] $ can be expressed as $2^ny_i^{n} $ where $n =\{0,1\}$
Constraints can be
$ x_0 - 1 \le 2\sum_{i=1}^4 y_{i}^0$
$x_0-2 \le \sum_i y_{i}^1 \le 5-x_0$

$\endgroup$
7
  • 1
    $\begingroup$ Right idea, but needs correction when $x_0=3$. $\endgroup$
    – RobPratt
    Commented Apr 15, 2023 at 15:34
  • $\begingroup$ @RobPratt Completed the answer just now $\endgroup$ Commented Apr 15, 2023 at 15:37
  • $\begingroup$ Sorry, still not right. $\endgroup$
    – RobPratt
    Commented Apr 15, 2023 at 19:02
  • $\begingroup$ @RobPratt yes an upper bound was needed. $\endgroup$ Commented Apr 15, 2023 at 19:33
  • $\begingroup$ Your $x_0-1\le$ constraint is too restrictive when $x_0=3$. $\endgroup$
    – RobPratt
    Commented Apr 15, 2023 at 21:53

Your Answer

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

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