On the number of degenerate simplex pivots

• 成果类型: Article
• 署名作者: Kukharenko, Kirill; Sanita, Laura
• 署名单位: Otto von Guericke University; Bocconi University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02349-x
• 发表日期: 2026-03
• 页码: 757-791
• 关键词: simplex algorithm; linear programming; degeneracy; WORST-CASE BEHAVIOR; algorithm; diameter

摘要

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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-m-1$$\end{document}, where n is the number of variables and m is the number of equality constraints of a given LP in standard equality form.