کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
474210 698850 2007 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On Hoffman's celebrated cycling LP example
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
On Hoffman's celebrated cycling LP example
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 34, Issue 9, September 2007, Pages 2709–2717
نویسندگان
, ,