The clique problem with multiple-choice constraints under a cycle-free dependency graph

Bärmann A, Gemander P, Merkert M (2020)

Publication Type: Journal article

Publication year: 2020

Journal

Discrete Applied Mathematics Elsevier

DOI: 10.1016/j.dam.2019.12.015

Abstract

The clique problem with multiple-choice constraints (CPMC) represents a very common substructure in many real-world applications, for example scheduling problems with precedence constraints. It consists in finding a clique in a graph whose nodes are partitioned into subsets, such that exactly one node from each subset is chosen. Even though we can show that (CPMC) is NP-complete, we will be able to identify and characterize a new interesting subclass which is solvable in polynomial time. It arises whenever there are no circular dependencies between the subsets in the partition when it comes to the compatibilities of their elements. We will be able to show that this subclass is equivalent to the clique problem on a perfect graph with certain additional structure. This finding will allow us to give a full convex-hull description. Although the convex hull can have exponentially-many facets, we can state an efficient and practical separation algorithm. In an application from underground and railway timetabling, we show that, in comparison to a naive formulation, these results lead to significant reductions in computation time.

Authors with CRIS profile

Andreas Bärmann Economics - Discrete Optimization - Mathematics (EDOM)

Involved external institutions

Otto-von-Guericke-Universität Magdeburg DE Germany (DE) Fraunhofer Arbeitsgruppe für Technologien der Logistik-Dienstleistungswirtschaft ATL DE Germany (DE)

How to cite

APA:

Bärmann, A., Gemander, P., & Merkert, M. (2020). The clique problem with multiple-choice constraints under a cycle-free dependency graph. Discrete Applied Mathematics. https://doi.org/10.1016/j.dam.2019.12.015

MLA:

Bärmann, Andreas, Patrick Gemander, and Maximilian Merkert. "The clique problem with multiple-choice constraints under a cycle-free dependency graph." Discrete Applied Mathematics (2020).

BibTeX: Download