An Implementation Of The Dual Local Decomposition Method

Abstract

The paper deals with a method for solving a linear programming problem with a primal block-angular structure. Any basic solution of such a problem can be decomposed into a principal problem and the remaining independent subproblems. A dual method working on an infeasible principal problem interacts with all the remaining independent subproblems to yield an optimal solution to the entire problem. Some implementation results for primally and dually feasible initial solutions using randomly generated problems are given.

Résumé

Cet article traite d’une méthode de résolution pour des problèmes de programmation linéaire avec structure angulaire en blocs. Toute solution de base à de tels problèmes peut se décomposer entre le problème principal et les sous-problèmes indépendants qui restent. Une méthode duale est appliquée au problème principal et entre en interaction avec les sous-problèmes, pour déboucher sur une solution optimale au problème global. On présente des résultats pour des problèmes aléatoires ayant une solution initiate primale ou duale réalisable.

Additional information

Notes on contributors

Leonard A. Coad

Leonard Coad is currently Director, Natural Gas Research at the Canadian Energy Research Institute. Mr. Coad holds an M.A. in Operations Research and has worked in a variety of energy related groups in government, industry and research.

Cornelis Van De Panne

Cornelis van de Panne is Professor of Economics at The University of Calgary. He specializes in mathematical programming and its economic applications. He has degrees from Erasmus University and the University of Birmingham. He has written two books and many articles in the area of mathematical programming.