Groupe d’études et de recherche en analyse des décisions


Decomposition of Multi-Player Linear Programs

, et

In this paper a class of large, structured linear programs arising in multi-regional (or multi-sectoral) commodity exchange problems, is examined. A decomposition approach is described, inspired by the computation of a cooperative economic equilibrium between the regions considered as players in a competitive game. The approach consists in computing for each player an approximation of its supply/demand function, and to compute a competitive equilibrium between these functions. The general algorithms proposed here may be viewed as extensions of the PIES approach to the case where supply/demand functions are defined implicitly rather than explicitly. Alternatively, our method may be looked at as a refinement of the cob web algorithm. Contrary to the classical Dantzig-Wolfe or Benders' decompositions, our approach is easily extended to the computation of a regulated equilibrium (as opposed to a purely competitive one). In the absence of a complete proof of convergence, we present numerical results for large realistic problems arising in energy modelling, which are extremely encouraging.

, 26 pages

Ce cahier a été révisé en juillet 1992