Improving the efficiency of the simplex algorithm based on a geometric explanation of phase 1
type: Item
instance of: scholarly article
title: Improving the efficiency of the simplex algorithm based on a geometric explanation of phase 1
zbMATH Open document ID: 1169.90400
DOI: 10.1504/IJOR.2009.025701
author: Daniel Solow
author: Hans Halim
published in: International Journal of Operational Research
publication date: 2009-09-13T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 5603407
zbMATH Keywords: linear programming
zbMATH Keywords: simplex algorithm
zbMATH Keywords: phase 1
zbMATH Keywords: phase 2
zbMATH Keywords: coordinate transformations
describes a project that uses: NETLIB LP Test Set
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5603407