On Hoffman's celebrated cycling LP example |
| |
Authors: | Pablo Guerrero-García Ángel Santos-Palomo |
| |
Affiliation: | Department of Applied Mathematics, University of Málaga, 29071 Málaga, Spain |
| |
Abstract: | We answer two questions that naturally arise while dealing with Hoffman's celebrated 50-year-old linear program to be solved by the primal simplex method, where an angle θ and a scaling factor ω are adjustable parameters. In particular, we determine what conditions have to be imposed on ω for classical cycling to occur with θ=2π/5, and what on θ with ω=±tan(θ). The first answer reveals that the sufficient condition widely spread over the literature is false, so fixing it turns this example into a correct example of classical cycling. Some progress towards necessary and sufficient conditions for cycling to occur in this example is also reported. |
| |
Keywords: | 90C05 90C60 |
本文献已被 ScienceDirect 等数据库收录! |
|