Article ID Journal Published Year Pages File Type
474210 Computers & Operations Research 2007 9 Pages PDF
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θ=2π/5, and what on θθ with ω=±tan(θ)ω=±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.

Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, ,