Refine
Year of publication
- 2014 (7) (remove)
Document Type
- In Proceedings (4)
- ZIB-Report (3)
Language
- English (7)
Is part of the Bibliography
- no (7)
Keywords
Institute
A common technique in the solution of large or complex optimization problems is the use of micro–macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconveniently by underestimating the global optimal value.
The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, such as vehicle composition, maintenance constraints, and regularity aspects. In industrial applications existing vehicle rotations often have to be re-optimized to deal with timetable changes or construction sites. We present an integrated modeling and algorithmic approach to this task as well as computational results for industrial problem instances of DB Fernverkehr AG.
We introduce the class of spot-checking games (SC games). These games model
problems where the goal is to distribute fare inspectors over a toll network.
Although SC games are not zero-sum, we show that a Nash equilibrium
can be computed by linear programming.
The computation of a strong Stackelberg equilibrium is
more relevant for this problem, but we show that this is NP-hard.
However, we give some bounds on the \emph{price of spite},
which measures how the
payoff of the inspector
degrades when committing to a Nash equilibrium.
Finally, we demonstrate the quality of these bounds for a real-world application,
namely the enforcement of a truck toll on German motorways.
We introduce the class of spot-checking games (SC games). These games model
problems where the goal is to distribute fare inspectors over a toll network.
Although SC games are not zero-sum, we show that a Nash equilibrium
can be computed by linear programming.
The computation of a strong Stackelberg equilibrium is
more relevant for this problem, but we show that this is NP-hard.
However, we give some bounds on the \emph{price of spite},
which measures how the
payoff of the inspector
degrades when committing to a Nash equilibrium.
Finally, we demonstrate the quality of these bounds for a real-world application,
namely the enforcement of a truck toll on German motorways.
The Cycle Embedding Problem
(2014)
Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design
efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor
details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.