On the degree of decomposition in linear programming

Article type: Research Article

Authors: Ho, James K. | Loute, Etienne

Affiliations: Information and Decision Sciences, University of Illinois at Chicago, m/c 294, 601 South Morgan, Chicago, IL 60607 USA. E-mail: jim.ho@uic.edu | Center for Operations Research and Econometrics, B-1348, Louvain-la-Neuve, Belgium

Abstract: In the application of Dantzig–Wolfe decomposition to block-angular linear programming problems with R natural blocks. it is possible to have from 1 to R subproblems structurally while solving all R independent subproblems computationally. Early literature on the topic was inconclusive regarding the relative merits of such formulations. This paper attempts clarification by characterizing the significance of the degree of decomposition as well as presenting extensive empirical results.

Keywords: linear programming, decomposition, computational mathematical programming

DOI: 10.3233/INF-1996-7304

Journal: Informatica, vol. 7, no. 3, pp. 337-348, 1996