Inspired by its occurrence as a substructure in a stochastic railway timetabling model, we study in this work a special case of the bipartite boolean quadric polytope. It models conditional relations across three sets of binary variables, where selections within two “if” sets imply a choice in a corresponding “then” set. We call this polytope … Read more
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
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
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
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
We consider the bipartite boolean quadric polytope (BQP) with multiple-choice constraints and analyse its combinatorial properties. The well-studied BQP is defined as the convex hull of all quadric incidence vectors over a bipartite graph. In this work, we study the case where there is a partition on one of the two bipartite node sets such … Read more
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