A polyhedral study of a constrained flow problem on decision diagrams

In a recent publication [“Graph coloring with decision diagrams,” by W.-J. van Hoeve, 2021], an exact algorithm employing decision diagrams was introduced for the graph coloring problem. This algorithm generates a sequence of relaxed decision diagrams and solves an NP-hard constrained network flow problem posed as an integer linear program (ILP) on each decision diagram. In this thesis project, we examined inequalities that are facet-defining for the integer hull of this ILP. We discovered that the majority of these facet-defining inequalities represented or were implied by objective cuts, and derived a method for efficiently finding these objective cuts. Additionally, we investigated the potential of generating Chvátal-Gomory cuts (CG-cuts) in one iteration and reusing parts of those CG-cuts in successive iterations. We formulated a model that takes part of a CG-cut from a past iteration as input and completes this CG-cut to fit the ILP in the current iteration. We furthermore designed a heuristic algorithm that can complete such CG-cuts efficiently. Our test results indicate that the CG-cut reusage scheme generally yields positive violation CG-cuts. Furthermore, the best cuts produced with the heuristic algorithm in each iteration are close to the theoretically best cuts that can be derived.