Scholarlink

<p>The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point along an improving edge-direction of the underlying polyhedron. A key issue in the simplex algorithm’s performance is <i>degeneracy</i>, which may lead to a (potentially long) sequence of basis exchanges which do not change the current extreme point solution. In this paper, we prove that one can employ any improving feasible direction at an extreme point to limit the number of consecutive degenerate pivots that the simplex algorithm performs to <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(n-m-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>-</mo> <mi>m</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, where <i>n</i> is the number of variables and <i>m</i> is the number of equality constraints of a given LP in standard equality form.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On the number of degenerate simplex pivots

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年3月23日

查看全文
  • Kirill Kukharenko,
  • Laura Sanità

摘要

The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point along an improving edge-direction of the underlying polyhedron. A key issue in the simplex algorithm’s performance is degeneracy, which may lead to a (potentially long) sequence of basis exchanges which do not change the current extreme point solution. In this paper, we prove that one can employ any improving feasible direction at an extreme point to limit the number of consecutive degenerate pivots that the simplex algorithm performs to \(n-m-1\) n - m - 1 , where n is the number of variables and m is the number of equality constraints of a given LP in standard equality form.