• search hit 82 of 89
Back to Result List

Staircase Compatibility and its Applications in Scheduling and Piecewise Linearization

Submission Status:under review
  • We consider 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 case, which we call staircase compatibility, generalizes common properties in 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 applications. 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 flow problems on a gas network. In both cases, we are able to reduce the solution times significantly by passing to the theoretically stronger formulations of the problem.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Andreas Bärmann, Thorsten Gellermann, Maximilian Merkert, Oskar Schneider
Document Type:Preprint
Language:English
Date of Publication (online):2016/09/06
Date of first Publication:2016/09/28
Release Date:2016/09/28
Tag:Clique Problem; Multiple-Choice Constraints; Piecewise Linearization; Scheduling; Total Unimodularity
Page Number:24
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
Subprojects:A05
B06
B07