Staircase Compatibility and its Applications in Scheduling and Piecewise Linearization

Beitrag in einer Fachzeitschrift


Details zur Publikation

Autorinnen und Autoren: Bärmann A, Gellermann T, Merkert M, Schneider O
Zeitschrift: Discrete Optimization
Jahr der Veröffentlichung: 2018
Band: 29
Seitenbereich: 111-132
ISSN: 1572-5286
Sprache: Englisch


Abstract

We introduce the Clique Problem with Multiple-Choice constraints (CPMC) and characterize a case where it is possible to give an efficient description of the convex hull of its feasible solutions. This special case, which we name staircase compatibility, generalizes common properties in several applications and allows for a linear description of the integer feasible solutions to (CPMC) with a totally unimodular constraint matrix of polynomial size. We derive two such totally unimodular reformulations for the problem: one that is obtained by a strengthening of the compatibility constraints and one that is based on a representation as a dual network flow problem. Furthermore, we show a natural way to derive integral solutions from fractional solutions to the problem by determining integral extreme points generating this fractional solution. We also evaluate our reformulations from a computational point of view by applying them to two different real-world problem settings. The first one is a problem in railway timetabling, where we try to adapt a given timetable slightly such that energy costs from operating the trains are reduced. The second one is the piecewise linearization of non-linear network flow problems, illustrated at the example of gas networks. In both cases, we are able to reduce the solution times significantly by passing to the theoretically stronger formulations of the problem.


FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Bärmann, Andreas Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Gellermann, Thorsten
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Merkert, Maximilian
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)
Schneider, Oskar
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)


Zitierweisen

APA:
Bärmann, A., Gellermann, T., Merkert, M., & Schneider, O. (2018). Staircase Compatibility and its Applications in Scheduling and Piecewise Linearization. Discrete Optimization, 29, 111-132. https://dx.doi.org/10.1016/j.disopt.2018.04.001

MLA:
Bärmann, Andreas, et al. "Staircase Compatibility and its Applications in Scheduling and Piecewise Linearization." Discrete Optimization 29 (2018): 111-132.

BibTeX: 

Zuletzt aktualisiert 2019-05-01 um 05:10