Dynamic Discretization Discovery and its application to railway schedule optimization

Bjørnar Luteberget

SINTEF Digital, Oslo, Norway

To solve schedule optimization problems over continuous time variables, a standard technique is to discretize the time domain, converting the problem into logical constraints over discrete variables. Such models can be solved using advanced and efficient off-the-shelf solvers for SAT, MaxSAT, or Mixed-Integer Linear Programming (MILP). However, in some problem domains, there is no reasonable choice of coarseness for the discretization: if it is too fine, the problem instance becomes too large to solve, while if it is too coarse, the approximate solutions may prove sub-optimal or even infeasible in the field.

Dynamic Discretization Discovery (DDD) is a technique used to convert scheduling problems over continuous time into discrete variables in a way that mitigates these size and approximation issues. The discretization is built incrementally in a way that ensures convergence to an optimal solution of the complete continuous-time formulation.

In this talk, we will present the DDD technique and our work on adapting the DDD to a railway scheduling problem. Empirical evaluations on industrial problem instances show that these DDD models are best handled using MaxSAT solvers, and that MaxSAT DDD can out-perform continuous-time MILP models for some classes of objective functions.