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

DOI10.1007/978-3-662-43404-8_4zbMATH Open1327.90104OpenAlexW215256906MaRDI QIDQ2948780FDOQ2948780

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

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

zbMATH Keywords

linear programmingpivotingbasic feasible solutionsthe simplex method

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• 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
• Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization
• Computing Kitahara-Mizuno's bound on the number of basic feasible solutions generated with the simplex algorithm
• On the number of solutions generated by the dual simplex method
• Upper bounds on the number of solutions of binary integer programs
• On the number of solutions generated by Dantzig's simplex method for LP with bounded variables
• A bound for the number of different basic solutions generated by the simplex method
• 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)