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

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.

• Your try violates $(5)$. Dec 14, 2023 at 15:37

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

• 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)$. Dec 16, 2023 at 16:24
• 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? Dec 16, 2023 at 18:08
• 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. Dec 16, 2023 at 19:18
• Please, let me check that. Dec 16, 2023 at 19:23
• Dear @RobPratt, you are right. My thought was the OP wants to know the only consecutive ones. Thanks for pointing this out. Dec 17, 2023 at 5:17