On the number of solutions generated by the simplex method for LP

DOI10.1007/978-3-662-43404-8_4MaRDI QIDQ2948780zbMATH OpenOpenAlexFDO

Authors Tomonari Kitahara, Shinji Mizuno

Publication date 6 October 2015

Published in Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-43404-8_4

zbMATH Keywords

linear programmingpivotingbasic feasible solutionsthe simplex method

Mathematics Subject Classification ID

Linear programming (90C05) Markov and semi-Markov decision processes (90C40)

Recommendations

• A bound for the number of different basic solutions generated by the simplex method
• On the number of solutions generated by Dantzig's simplex method for LP with bounded variables
• Lower bounds for the maximum number of solutions generated by the simplex method
• Klee-Minty's LP and upper bounds for Dantzig's simplex method
• An upper bound for the number of different solutions generated by the primal simplex method with any selection rule of entering variables

Cites work

• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• A bound for the number of different basic solutions generated by the simplex method
• An upper bound for the number of different solutions generated by the primal simplex method with any selection rule of entering variables
• Klee-Minty's LP and upper bounds for Dantzig's simplex method
• New Finite Pivoting Rules for the Simplex Method
• On the number of solutions generated by the dual simplex method
• The Hirsch conjecture is true for (0,1)-polytopes
• The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate

Cited in

(10)

• On the number of solutions generated by the dual simplex method
• A bound for the number of different basic solutions generated by the simplex method
• On the number of solutions generated by Dantzig's simplex method for LP with bounded variables
• Lower bounds for the maximum number of solutions generated by the simplex method
• An upper bound for the number of different solutions generated by the primal simplex method with any selection rule of entering variables
• Upper bounds on the number of solutions of binary integer programs
• Computing Kitahara-Mizuno's bound on the number of basic feasible solutions generated with the simplex algorithm
• Pivot rules for circuit-augmentation algorithms in linear optimization
• A double-pivot simplex algorithm and its upper bounds of the iteration numbers
• Klee-Minty's LP and upper bounds for Dantzig's simplex method

This page was built for publication: On the number of solutions generated by the simplex method for LP

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