A Stochastic Optimization Approach to Energy-Efficient Underground Timetabling under Uncertain Dwell and Running Times

We consider a problem from the context of energy-efficient underground railway timetabling, in which an existing timetable draft is improved by slightly changing departure and running times. In practice, synchronization between accelerating and braking trains to utilize regenerative braking plays a major role for the energy-efficiency of a timetable. Since deviations from a planned timetable … Read more

EETTlib – Energy-Efficient Train Timetabling Library

We introduce EETTlib, an instance library for the Energy-Efficient Train Timetabling problem. The task in this problem is to adjust a given timetable draft such that several key indicators relating to the energy consumption of the resulting railway traffic are minimized. These include peak power consumption, total energy consumption, loss in recuperation energy, fluctuation in … Read more

Algorithms for the Clique Problem with Multiple-Choice Constraints under a Series-Parallel Dependency Graph

The clique problem with multiple-choice constraints (CPMC), i.e. the problem of finding a k-clique in a k-partite graph with known partition, occurs as a substructure in many real-world applications, in particular scheduling and railway timetabling. Although CPMC is NP-complete in general, it is known to be solvable in polynomial time when the so-called dependency graph … Read more

On Recognizing Staircase Compatibility

For the problem to find an m-clique in an m-partite graph, staircase compatibility has recently been introduced as a polynomial-time solvable special case. It is a property of a graph together with an m-partition of the vertex set and total orders on each subset of the partition. In optimization problems involving m-cliques in m-partite graphs … Read more

Energy-Efficient Timetabling in a German Underground System

Timetabling of railway traffic and other modes of transport is among the most prominent applications of discrete optimization in practice. However, it has only been recently that the connection between timetabling and energy consumption has been studied more extensively. In our joint project VAG Verkehrs-Aktiengesellschaft, the transit authority and operator of underground transport in the … Read more

The SCIP Optimization Suite 7.0

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies … Read more

Two-row and two-column mixed-integer presolve using hash-based pairing methods

In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolving techniques successfully is … Read more

The Clique Problem with Multiple-Choice Constraints under a Cycle-Free Dependency Graph

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) … Read more

The SCIP Optimization Suite 5.0

This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over … Read more