I would like to give an introduction into the concept of „extended formulations“, which deals with the question of finding the „best“ way of expressing an optimization problem as a linear (integer) program. While the study of good formulations for problems in combinatorial optimization is an important topic since decades, it has received a renewed attention due to recent breakthroughs in our theoretical understanding of the concept. I will elaborate on these breakthroughs and why I believe that an exchange on this concept can be beneficial for all projects inside AdONE.
Dr. Pirmin Fontaine (TUM): "Multi-Modal Scheduled Service Network Design with Inbound and Outbound Flows for Two-Tier City Logistics"
We introduce a new problem for selecting services in a tactical plan of a two-tier city logistics system. Compared to existing models, we consider different transportation modes with multiple compartments within one model. Moreover, we integrate inbound and outbound demands in the model and consider the used resources in the constraints.
For defining the problem, we introduce a new integer programming formulation that has similarities to the well-known knapsack and bin packing problem. To efficiently solve this problem, we use this formulation in a Benders decomposition algorithm which is implemented in a Branch-and-Cut framework. We further improve the method by using pareto-optimal cuts, valid inequalities, and propose a new partial decomposition technique, which can be generalized to a broad class of deterministic problems.
The numerical results show significant run time improvements compared to the complete formulation ran using CPLEX. Furthermore, our results illustrate the benefits of including both flows and different transportation modes with multiple compartments in the planning.
This is joint work with Teodor Gabriel Crainic, Ola Jabali, and Walter Rei
Venue: Room Z 536 (City Campus)
Date: Monday, April 30th, 2018