• 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