Inspired by its occurrence as a substructure in a stochastic railway timetabling model, we study in this work a special case of the bipartite boolean quadric polytope.
It models conditional relations across three sets of binary variables, where selections within two "if" sets imply a choice in a corresponding "then" set.
We call this polytope the \textit{if-then polytope}.
We introduce a new class of valid inequalities and prove that, in contrast to the well-known McCormick inequalities, they are sufficient to completely characterize the description of the polytope.
We develop a separation algorithm that finds these inequalities in polynomial time and propose an additional clique-based method for precomputing tight cuts.
Furthermore, we show that for a chain of several if-then relations, the descriptions of the if-then polytopes for each individual relation already yield the convex hull of the chained polytope.
This is present in our application from the field of stochastic timetabling and also enables a broader application of our results in practice.
A comprehensive computational study shows the usefulness of the new inequalities in state-of-the-art branch-and-cut solvers for real-world timetabling applications and instances of the quadratic assignment problem.
Article
View The if-then Polytope: Conditional Relations over Multiple Sets of Binary Variables