Improving the efficiency of the simplex algorithm based on a geometric explanation of phase 1

Improving the efficiency of the simplex algorithm based on a geometric explanation of phase 1

0.00 Avg rating0 Votes
Article ID: iaor200968918
Country: United Kingdom
Volume: 5
Issue: 4
Start Page Number: 408
End Page Number: 428
Publication Date: May 2009
Journal: International Journal of Operational Research
Authors: ,
Keywords: simplex algorithm
Abstract:

An open question pertaining to the simplex algorithm is where phase 1 terminates on the feasible region. Here, computer simulations support the conjecture that phase 1 terminates at a feasible point geometrically close to the starting point. This observation leads to a coordinate transformation for bounded Linear Programs (LP) that requires fewer iterations in phase 2. This is confirmed by computational experiments on random LPs and Netlib problems and shows generally increasing benefits as the number of negative coefficients in the minimisation objective function increases. Though not winning on all Netlib problems, the coordinate transformation saves 2–11% of the CPU time.

Reviews

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