Title of article
On Hoffmanʹs celebrated cycling LP example
Author/Authors
Pablo Guerrero-Garc?، نويسنده , , ?ngel Santos-Palomo، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2007
Pages
9
From page
2709
To page
2717
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
Linear programming , Simplex method , Cycling
Journal title
Computers and Operations Research
Serial Year
2007
Journal title
Computers and Operations Research
Record number
928489
Link To Document