Brunel University Research Archive (BURA) >
Research Areas >
Mathematical Science >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/848

Title: Creating advanced bases for large scale linear programs exploiting embedded network structure
Authors: Gulpinar, N
Mitra, G
Maros, I
Keywords: linear programming; network flows; Lagrangean relaxation; Benders decomposition; advanced bases
Publication Date: 2002
Publisher: Springer
Citation: Volume 21, Number 1, January 2002 , pp. 71-93(23)
Abstract: In this paper, we investigate how an embedded pure network structure arising in many linear programming (LP) problems can be exploited to create improved sparse simplex solution algorithms. The original coefficient matrix is partitioned into network and non-network parts. For this partitioning, a decomposition technique can be applied. The embedded network flow problem can be solved to optimality using a fast network flow algorithm. We investigate two alternative decompositions namely, Lagrangean and Benders. In the Lagrangean approach, the optimal solution of a network flow problem and in Benders the combined solution of the master and the subproblem are used to compute good (near optimal and near feasible) solutions for a given LP problem. In both cases, we terminate the decomposition algorithms after a preset number of passes and active variables identified by this procedure are then used to create an advanced basis for the original LP problem. We present comparisons with unit basis and a well established crash procedure. We find that the computational results of applying these techniques to a selection of Netlib models are promising enough to encourage further research in this area.
URI: http://bura.brunel.ac.uk/handle/2438/848
Appears in Collections:Mathematical Science

Files in This Item:

File Description SizeFormat
lagrel_COAP.pdf948.68 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.