Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/848
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGulpinar, N-
dc.contributor.authorMitra, G-
dc.contributor.authorMaros, I-
dc.coverage.spatial71-93(23)en
dc.date.accessioned2007-06-14T14:50:42Z-
dc.date.available2007-06-14T14:50:42Z-
dc.date.issued2002-
dc.identifier.citationVolume 21, Number 1, January 2002 , pp. 71-93(23)en
dc.identifier.urihttp://bura.brunel.ac.uk/handle/2438/848-
dc.description.abstractIn 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.en
dc.format.extent971446 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoen-
dc.publisherSpringeren
dc.subjectlinear programming; network flows; Lagrangean relaxation; Benders decomposition; advanced basesen
dc.titleCreating advanced bases for large scale linear programs exploiting embedded network structureen
dc.typeResearch Paperen
Appears in Collections:Mathematical Sciences

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.