A Z-simplex algorithm with partial updates

DOI10.1007/BF01937354MaRDI QIDQ1097835zbMATH OpenOpenAlexFDO

Authors Adi Ben-Israel

Publication date 1987

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01937354

zbMATH Keywords

canonical basespartial updatesY-dualZ-simplex algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Review text

The simplex algorithm for solving \(\max \{c^ Tx:\) \(Ax=b\), \(x\geq 0\}\) can be presented in terms of canonical bases Z of N(A), which is the so- called Z-simplex algorithm. In this implementation the bases Z are updated from iteration to iteration. The author shows that only part of Z needs to be updated at each iteration. A similar result holds for the so- called Y-dual method which implements the simplex dual method in terms of canonical bases Y of R(A).

Recommendations

• An efficient approach to updating simplex multipliers in the simplex algorithm
• A simplex method algorithm using a double basis
• Canonical bases in linear programming
• Two partial pricing strategies for the simplex algorithm
• Novel update techniques for the revised simplex method

Cites work

• A class of methods for linear programming
• A practicable steepest-edge simplex algorithm
• scientific article; zbMATH DE number 3854804 (Why is no real title available?)
• scientific article; zbMATH DE number 3912096 (Why is no real title available?)
• scientific article; zbMATH DE number 3961334 (Why is no real title available?)
• scientific article; zbMATH DE number 3209723 (Why is no real title available?)
• scientific article; zbMATH DE number 3079989 (Why is no real title available?)
• Large-scale linearly constrained optimization
• New Finite Pivoting Rules for the Simplex Method
• Optimality and Degeneracy in Linear Programming
• Sparse Matrix Methods in Optimization
• Stationary points of quadratic functions under linear constraints
• The generalized simplex method for minimizing a linear form under linear inequality restraints

Cited in

(1)

• Canonical bases in linear programming

This page was built for publication: A Z-simplex algorithm with partial updates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1097835)