Gemander P (2019)
Publication Type: Conference contribution
Publication year: 2019
Publisher: Springer International Publishing
City/Town: Cham
Pages Range: 3--9
Conference Proceedings Title: Operations Research Proceedings 2018
ISBN: 978-3-030-18500-8
URI: https://link.springer.com/chapter/10.1007/978-3-030-18500-8_1
DOI: 10.1007/978-3-030-18500-8_1
The clique problem under multiple-choice constraints is an NP-hard variant of the general clique problem, which incorporates a structure commonly found in real-world applications like underground, railway or runway scheduling. It is relevant whenever there is a set of decisions with discrete options for each decision and possible conflicts between options. In this article, we identify a polynomial-time solvable subclass and determine its complete convex hull using graph-theoretic arguments related to perfect graphs. Since the convex hull can have exponentially many facets, we present criteria on how to more efficiently find the stable sets required to describe the convex hull as well as a polynomial-time separation algorithm. Finally, the theoretical results were successfully applied to energy-efficient underground and railway scheduling.
APA:
Gemander, P. (2019). On a Polynomially Solvable Subclass of the Clique Problem with Applications in Energy-Efficient Timetabling. In Fortz B, Labbé M (Eds.), Operations Research Proceedings 2018 (pp. 3--9). Cham: Springer International Publishing.
MLA:
Gemander, Patrick. "On a Polynomially Solvable Subclass of the Clique Problem with Applications in Energy-Efficient Timetabling." Proceedings of the Operations Research Proceedings 2018 Ed. Fortz B, Labbé M, Cham: Springer International Publishing, 2019. 3--9.
BibTeX: Download