University of Twente Student Theses
A polyhedral study of a constrained flow problem on decision diagrams
Hugen, T.E. (2023) A polyhedral study of a constrained flow problem on decision diagrams.
|
PDF
2MB |
| Abstract: | 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. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics |
| Programme: | Applied Mathematics MSc (60348) |
| Link to this item: | https://purl.utwente.nl/essays/97883 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page