Which of these formulations has the tightest linear relaxation ? (Part 2)

Question

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.

Answer 1

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