1
$\begingroup$

This is a follow up question of this question, in which it was asked to compare the "tightness" of two models:

I have a sequence of binary variables $x_i$ and want to enforce consecutive $1$'s of length at least $3$. I have $2$ formulations:

  • Model $1$: \begin{align} x_i \le x_{i-1}+x_{i+1} \tag{1}\\ x_i \le x_{i-1}+x_{i+2} \tag{2}\\ \end{align}

  • Model $2$: \begin{align} x_i &\le x_{i-1}+x_{i+1} \tag{3}\\ x_i +x_{i+1} &\le x_{i-1}+x_{i+2}+1 \tag{4}\\ \end{align}

A third option (Model 3) would be to define a new binary variable $s_i$ to detect when the sequence starts: $$ s_i \ge x_i -x_{i-1} \tag{5} $$ and to enforce $s_i \implies x_i \wedge x_{i+1} \wedge x_{i+2}$: \begin{align} s_i &\le x_i \tag{6}\\ s_i &\le x_{i+1} \tag{7}\\ s_i &\le x_{i+2} \tag{8} \end{align}

My question is the same. How does model $(5)-(8)$ compare to models $(1)-(2)$ and $(3)-(4)$?

My try: the fractional solution $(s_i, x_{i-1}, x_{i},x_{i+1},x_{i+2})=(0.1,0,0.2,0.5,0.1)$ is violated by model $1$, but satisfies models $2$ and $3$. Therefore model $1$ is tighter than models $2$ and $3$. And we already know that model $1$ is tighter than model $2$. Not sure how models $2$ and $3$ compare.

$\endgroup$
1
  • 2
    $\begingroup$ Your try violates $(5)$. $\endgroup$
    – RobPratt
    Dec 14, 2023 at 15:37

1 Answer 1

3
$\begingroup$

As a simple test, I tried solving the problem in the three states you mentioned. Also, the pre-solving, separating, and heuristics were all turned off in all cases to test the problem with only the $\text{B&B}$ scheme.

The first model:

presolved problem has 11 variables (10 bin, 0 int, 0 impl, 1 cont) and 22 constraints
     22 constraints of type <linear>
Presolving Time: 0.00

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
  1.0s|     1 |     0 |     7 |     - |   654k |   0 |  11 |  22 |  22 |   0 |  0 |   0 |   0 |-3.000000e+00 |      --      |    Inf | unknown
  1.0s|     1 |     0 |     7 |     - |   654k |   0 |  11 |  22 |  22 |   0 |  0 |   0 |   0 |-3.000000e+00 |      --      |    Inf | unknown
* 1.0s|     1 |     0 |     7 |     - |strongbr|   0 |  11 |  22 |  22 |   0 |  1 |   0 |   0 |-3.000000e+00 |-3.000000e+00 |   0.00%| unknown
  1.0s|     1 |     0 |     7 |     - |   657k |   0 |  11 |  22 |  22 |   0 |  1 |   0 |   1 |-3.000000e+00 |-3.000000e+00 |   0.00%| unknown

The second model:

presolved problem has 11 variables (10 bin, 0 int, 0 impl, 1 cont) and 22 constraints
     22 constraints of type <linear>
Presolving Time: 0.00

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
* 0.0s|     1 |     0 |     8 |     - |    LP  |   0 |  11 |  21 |  21 |   0 |  0 |   0 |   0 |-3.000000e+00 |-3.000000e+00 |   0.00%| unknown
  0.0s|     1 |     0 |     8 |     - |   738k |   0 |  11 |  21 |  21 |   0 |  0 |   0 |   0 |-3.000000e+00 |-3.000000e+00 |   0.00%| unknown

The third model:

presolved problem has 21 variables (20 bin, 0 int, 0 impl, 1 cont) and 42 constraints
     42 constraints of type <linear>
Presolving Time: 0.00

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
  0.0s|     1 |     0 |    13 |     - |  1557k |   0 |  21 |  36 |  36 |   0 |  0 |   0 |   0 |-3.000000e+00 |      --      |    Inf | unknown
  0.0s|     1 |     0 |    13 |     - |  1557k |   0 |  21 |  36 |  36 |   0 |  0 |   0 |   0 |-3.000000e+00 |      --      |    Inf | unknown
* 0.0s|     1 |     0 |    13 |     - |strongbr|   0 |  21 |  36 |  36 |   0 |  1 |   0 |   0 |-3.000000e+00 |-3.000000e+00 |   0.00%| unknown
  0.0s|     1 |     0 |    13 |     - |  1569k |   0 |  21 |  36 |  36 |   0 |  1 |   0 |   1 |-3.000000e+00 |-3.000000e+00 |   0.00%| unknown

It seems the first and the third cases need strong branching (the syntax strongbr) to achive the optimal solution, while in the second case, the solver finds the optimal solution in the first row. Also, in the third one adding the new binary variable leads to an increase in the variable around $2x$.

$\endgroup$
5
  • 1
    $\begingroup$ Your fourth model prevents only $(x_i,x_j,x_k)=(1,0,1)$, which should be allowed. We instead want to prevent $(0,1,0)$ and $(0,1,1,0)$. $\endgroup$
    – RobPratt
    Dec 16, 2023 at 16:24
  • $\begingroup$ Dear @RobPratt, in the OP mentioned conservative ones. The first three model actually do that. Would you say what you mean by $(1,0,1)$ as a solution? $\endgroup$
    – A.Omidi
    Dec 16, 2023 at 18:08
  • $\begingroup$ Your fourth model enforces $(x_i\land x_k)\implies x_j$. Equivalently, it prevents $x_i=1,x_j=0,x_k=1$, but that is not what the OP wants. You have the roles of $0$ and $1$ reversed in the fourth model. $\endgroup$
    – RobPratt
    Dec 16, 2023 at 19:18
  • $\begingroup$ Please, let me check that. $\endgroup$
    – A.Omidi
    Dec 16, 2023 at 19:23
  • $\begingroup$ Dear @RobPratt, you are right. My thought was the OP wants to know the only consecutive ones. Thanks for pointing this out. $\endgroup$
    – A.Omidi
    Dec 17, 2023 at 5:17

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.