An improved initial basis for the Simplex algorithm |
| |
| Affiliation: | 1. Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany;2. Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA 02139, United States;1. Air Force Institute of Technology, Department of Mathematics and Statistics, 2950 Hobson Way, Wright-Patterson AFB, OH 45433, USA;2. University of Colorado, Department of Applied Mathematics, 526 UCB, Boulder, CO 80309, USA;1. Institute of Automation and Control Engineering, UMIT GmbH, Eduard-Wallnöfer-Zentrum 1, 6060 Hall i.T., Austria;2. GE Jenbacher GmbH & Co OG, Achenseestr. 1-3, 6200 Jenbach, Austria;3. Institute for Robotics and Mechatronics, JOANNEUM RESEARCH - Forschungsgesellschaft mbH, Lakeside B08a, 9020 Klagenfurt, Austria;1. Fritz Haber Center for Molecular Dynamics, Institute of Chemistry, Hebrew University, Jerusalem 91904, Israel;2. Theoretical and Physical Chemistry Institute, The National Hellenic Research Foundation, 48 Vassileos Constantinou Ave., Athens 116 35, Greece |
| |
| Abstract: | A lot of research has been done to find a faster (polynomial) algorithm that can solve linear programming (LP) problems. The main branch of this research has been devoted to interior point methods (IPM). The IPM outperforms the Simplex method in large LPs. However, there is still much research being done in order to improve pivoting algorithms. In this paper, we present a new approach to the problem of improving the pivoting algorithms: instead of starting the Simplex with the canonical basis, we suggest as initial basis a vertex of the feasible region that is much closer to the optimal vertex than the initial solution adopted by the Simplex. By supplying the Simplex with a better initial basis, we were able to improve the iteration number efficiency of the Simplex algorithm in about 33%. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
