Strategies for creating advanced bases for large-scale linear programming problems

Strategies for creating advanced bases for large-scale linear programming problems

0.00 Avg rating0 Votes
Article ID: iaor19991451
Country: United States
Volume: 10
Issue: 2
Start Page Number: 248
End Page Number: 260
Publication Date: Mar 1998
Journal: INFORMS Journal On Computing
Authors: ,
Abstract:

The performance of the revised sparse simplex method, or its variants, for the solution of large scale linear programming problems can be considerably enhanced if an advanced starting basis is introduced instead of the traditional all-logical initial basis. We consider three such procedures known as crash procedures to obtain advanced starting points for the revised sparse simplex: (1) We extend traditional crash procedures whereby triangularity of the basis is always maintained and take advantage of the problem characteristics; we apply additional criteria for determining the entering structural variables and their position in the basis. (2) We allow the triangularity to be slightly ‘violated’, and make some cheap pivot steps to find a better basis. (3) We use the iterative successive-over-relaxation technique to compute a non-extreme point solution and make a crossover to a basic solution. In this article, we first review the work done by other researchers. Then we present an analysis of issues, followed by a description of the techniques and our computational experience.

Reviews

Required fields are marked *. Your email address will not be published.