# Which of these formulations has the tightest linear relaxation?

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$$ (from here): \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$$ (from here): \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}

I would like to know which of these formulations $$(1)-(2)$$ or $$(3)-(4)$$ has the tightest linear relaxation?

Constraints $$(1)$$ and $$(3)$$ are identical, and $$(4)$$ is just an aggregation of $$(2)$$ and the valid inequality $$x_{i+1} \le 1$$ that is part of the definition of $$x$$ being binary. So Model 1 is at least as tight. To see that it is actually tighter, consider the fractional solution $$(x_{i-1},x_i,x_{i+1},x_{i+2})=(0,1/2,1/2,0)$$, which violates Model 1 but satisfies Model 2.

• I have edited the question to address your first point. Does this seem correct now?
– abcd
Dec 14, 2023 at 7:53
• @abcd Yes, and I just edited my answer accordingly. Dec 14, 2023 at 13:40

At the risk of not answering your "A vs. B" question i would claim, that a better approach would be based on creating the corresponding deterministic finite automaton followed by transforming it into a layered-graph (assuming an upper bound on the sequence-length) and modelling it through network-flow like models.

This also generalizes well (e.g. some small changes / extensions later).

I guess the following resources are a good reference:

Côté, Marie-Claude, Bernard Gendron, and Louis-Martin Rousseau. "Modeling the regular constraint with integer programming." Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 4th International Conference, CPAIOR 2007, Brussels, Belgium, May 23-26, 2007. Proceedings 4. Springer Berlin Heidelberg, 2007.

Côté, Marie-Claude, et al. "Formal languages for integer programming modeling of shift scheduling problems." Constraints 16 (2011): 54-76.

While not much saying about LP/MILP, this DFA-based approach is also known to provide very powerful theoretically-supported propagators in constraint-programming:

Pesant, Gilles. "A regular language membership constraint for sequences of variables." Workshop on modelling and reformulation constraint satisfaction problems. 2003.