IJPAM: Volume 32, No. 4 (2006)

A BIG-M FREE SOLUTION ALGORITHM FOR
GENERAL LINEAR PROGRAMS

Hossein Arsham
Information and Quantitative Science Department
Merrick School of Business
University of Baltimore
1420 North Charles Street, Baltimore, Maryland, 21201-5779, USA
e-mail: harsham@ubalt.edu


Abstract.A three-phase simplex type solution algorithm is developed for solving general linear programs. In Phase 1, greater-than constraints are relaxed and the problem is solved starting at the origin. If it is unbounded; then the objective function is modified in order to have a bound feasible solution. Then, in Phase 2 the greater-than constraints are introduced in a dual simplex framework. Following this, in the case the original objective function was modified, Phase 3 restores optimality for the original objective function. The algorithm is numerically stable and works with the original decision variables. Our initial experimental study indicates that the proposed algorithm is more efficient than both the primal and the dual simplex in terms of the number of iterations.

Received: October 20, 2006

AMS Subject Classification: 90C05, 90C06, 49M20, 65K05

Key Words and Phrases: large-scale linear programs, artificial variable free, artificial constraint free, pivot algorithm, advance basis, non-Big-M method

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2006
Volume: 32
Issue: 4