1
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

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

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.

$\endgroup$

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.