On Hoffman's celebrated cycling LP example

On Hoffman's celebrated cycling LP example

0.00 Avg rating0 Votes
Article ID: iaor20083416
Country: United Kingdom
Volume: 34
Issue: 9
Start Page Number: 2709
End Page Number: 2717
Publication Date: Sep 2007
Journal: Computers and Operations Research
Authors: ,
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.

Reviews

Required fields are marked *. Your email address will not be published.