Using dual decomposition for solving problems involving data uncertainty

August 14, 2013

Many applications mdash; energy, routing, scheduling, and production planning, for example mdash; involve problems in which some or all of the data may not be known when decisions under uncertainty must be made. In such cases, approximations with stochastic mixed-integer programming models are often used.

Two approaches have been suggested to address such problems: dual decomposition (DD) and branch-and-price (BP). Both approaches divide the problem into two or more subproblems, together with linear constraints that enforce agreement between solutions to the different problems through a series of iterations. Unfortunately, both approaches also suffer from lack of scalability.

Researchers at Argonne National Laboratory and the University of Chicago have now developed an alternative strategy that exploits both DD and BP. Specifically, they have showed that solving one provides an optimal solution to both.

Having established this equivalence, the team developed a new formulation for the master problem solved at each iteration. The new formulation results in a quadratic program that can then be solved efficiently by exploiting the problem structure.

"Reducing the time spent solving the master problem significantly increases the scope for parallelism," said Cosmin Petra, an assistant computational mathematician in Argonne’s Mathematics and Computer Science Division.

To test the performance of the new formulation, the team implemented a parallel version and ran a set of experiments on a 320-node cluster at Argonne. The results indicated significant speedups in all by one case, on up to 16 parallel processors.

The next step is to develop an implementation with dynamic load balancing, which is expected to enable further speedups on larger numbers of processors.

For further information, see

M. Lubin, K. Martin, C. Petra, and B. Sandikçi, On parallelizing dual decomposition in stochastic integer programming, Operations Research Letters 41(3), 252-258 (2013)