Which of these formulations has the tightest linear relaxation?

Question

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?

Answer 1

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.

Answer 2

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.