Operations Research Seminar: Dieter Weninger

Exact Approaches and Heuristics for Solving Mixed-Integer Time-Space Network Problems

Dieter Weninger, University of Erlangen

A time-space network is a directed graph, in which each node is associated with a specific time-period. Time-space networks are widely used to model a variety of problems from different contexts, such as production planning and supply chain management. In this talk, we address the topics presolving, primal heuristics, and variable decomposition for tackling mixed-integer time-space networks.
In the first part, we consider presolving, which is a set of routines that reduce the size and improve the formulation of a given model. We show some recently developed presolving algorithms, which have been integrated into the open-source solver SCIP. All presented algorithms use pairs of rows or columns of the underlying constraint matrix to derive model reductions. The key for finding promising pairs of rows or columns as quickly as possible are specially-tailored hash functions. Especially on supply chain problems these presolving algorithms find many reductions.
Feasibility pumps are an efficient class of primal heuristics for mixed-integer linear and nonlinear optimization. At their core, they can be seen as alternating direction methods applied to a special reformulation of the original problem. Building on this insight, we propose a novel decomposition framework that combines hypergraph partitioning with a penalty alternating direction method for computing primal solutions of real-world supply chain problems.
Gas network models incorporate the physical properties of gas flow on the pipes and discrete decisions for using control elements. The resulting model is a time-continuous mixed-integer nonlinear program with partial differential equations. We reformulate this model to get a time-space and block-structured mixed-integer linear model with linking variables. As only few variables link adjacent blocks, there is hope to obtain a good approximation of the corresponding value function. We show a generalized Benders decomposition approach for achieving this aim.