Activities

The project amounted in 8 peer-reviewed publications (4 journal papers, 1 book chapter, and 3 extended conference abstracts), 11 conference presentations (4 by invitation), 1 conference session organization, 1 popular science paper, and three working papers submitted for publication. Click here for a complete list.

See the interview with me in FTP's publication "8 grønne forskerhistorier 2009" here. 

Optimizing Transportation, Planning, and Scheduling Problems using Decomposition Algorithms

Motivation

In the industry many recourses are spend on handling the challenges in transportation, planning, and scheduling problems. The process is optimized on a computer using a mathematical problem formulation. Within the last dozen of years commercial software have had a significant impact on the solution process of problems that are described in a general framework. Partly due too increased computer power but primarily due to algorithmic improvements. However, not all problems fit into this general framework and in particular not the transportation, planning, and scheduling problems considered in this project. These are instead solved with decomposition algorithms.

Algorithm

Decomposition algorithms uses a special mathematical formulation where a problem is split into smaller subproblems. Unfortunately the split makes many of the general algorithmic improvements nontrivial. However, recent research implies that there is a large potential gain in computation speed and solution quality when applying one of these mprovements (denoted cuts), although it comes at an increased complexity in the subproblems of the decomposition algorithm.

Details

To the right a decomposition of a mathematical problem and the cause and effects of applying cuts are illustrated. Left in the figure is the constraints matrix of the "original problem" consisting of "linking constraints" and "blocks" (white boxes), and cuts (green boxes). The decomposed problem on the right, the "master problem", consists of a reformulation of the linking constraints and "convexity constraints" (white boxes), and cuts (green boxes). A column (variable) in the master problem is construced from a solution to the "subproblem" (lower right corner) that holds the constraints from the blocks.

The "restriction" of the master problem refers to, that only a subset of variables are considered at a given time in the master problem, and an iterative modification of the objective function of the subproblem gives rise to new solutions of the subproblem leading to new columns in the master problem.

The "augmentation" of the original problem refers to an addition of variables in the original problem in order to be able to model cuts derived in the master problem. Such an augmentation ripples through the decomposition and also gives rise to augmented "subproblems".

Goals

The goal of this project is to (i) build a theoretical foundation with regard to the cuts applied in decomposition algorithms and (ii) to develop alternative subproblem algorithms to handle the added complexity. A successful outcome of this project would be a large theoretical step in the field of decomposition algorithms and for practical applications the performance could potentially be many doubled as experimentally shown in the recent results.