The Bipartite Implication Polytope: Conditional Relations over Multiple Sets of Binary Variables

Abstract. 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 implying sets imply a choice in a corresponding implied set. We call this polytope the Bipartite Implication 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 bipartite implication relations, the descriptions of the bipartite implication 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.