On the facet pivot simplex method for linear programming

This paper proposes a novel facet pivot simplex method for linear programming that demonstrates superior promise over the traditional vertex pivot approach in numerical tests, offering new hope for discovering a polynomial-time pivot algorithm.

The Gist

Imagine you are trying to find the absolute best spot to set up a lemonade stand in a city. The city is shaped like a complex, multi-sided building (a polytope), and you want to find the corner that will make you the most money.

For over 70 years, the standard way to do this has been the Vertex Pivot Method (invented by George Dantzig). Think of this method like a tourist walking around the outside of the building. They start at one corner (vertex), look at the neighboring corners, and walk to the one that looks better. They keep hopping from corner to corner along the edges until they find the best spot.

The problem is that sometimes, the building is designed with a tricky maze of corners. In the worst-case scenarios, the tourist might have to walk through every single corner in a specific, exhausting order before finding the best one. This is like walking through a maze that gets exponentially longer as the building gets bigger.

The New Idea: The "Facet Pivot" Method

In this paper, the author, Yaguang Yang, proposes a new way to solve this problem called the Facet Pivot Simplex Method.

Instead of walking along the corners (vertices), imagine you are a construction inspector looking at the facets of the building.

• The Old Way (Vertex): You are a tourist hopping from corner to corner.
• The New Way (Facet): You are an inspector swapping out the facets that define your current "base" to get closer to the best spot.

Here is how the new method works in simple terms:

1. Start with the Facets, Not the Corners: Instead of starting at a corner, the algorithm starts by picking a set of facets (constraints) that define a temporary, perhaps imperfect, position.
2. Swap Facets, Not Corners: The algorithm looks at the facets that are currently "violated" or not satisfied (like a facet that is oriented the wrong way). It picks the worst one and swaps it out for a different facet that helps fix the problem.
3. No "Phase 1" Detour: The old method often requires a long, expensive "Phase 1" trip just to find a valid starting corner before it can even begin looking for the best one. The new method is clever: it starts with a setup that is mathematically guaranteed to work immediately, skipping that long detour entirely. It's like having a magic key that opens the door to the building instantly, rather than trying to pick the lock first.

Why is this exciting?

The paper claims this new method is very promising for two main reasons:

• It's Faster on Hard Mazes: The author tested this on "Klee-Minty cubes," which are mathematical mazes specifically designed to trick the old tourist method into taking forever. The new facet-swapping method solved these mazes much faster, taking only a few steps instead of thousands.
• It's More Robust: When tested on a huge collection of real-world math problems (the Netlib benchmarks), the new method solved almost all of them successfully. The old "tourist" method sometimes got stuck or took a very long time, and the "dual" method (a different type of tourist) sometimes gave up because the building's geometry was too tricky. The facet-swapping method handled these tricky geometries better.

The Catch (and the Hope)

The paper admits that for very large, simple problems, the old method (or other methods like "Interior Point" methods, which are like flying a drone through the middle of the building) might still be faster.

However, the big hope is that this new "facet-swapping" approach might be the key to solving a famous 60-year-old math mystery: Can we find a method that is guaranteed to be fast (polynomial time) for every problem?

For decades, mathematicians have tried to prove that the old "corner-hopping" method is fast enough, but they found cases where it is incredibly slow. This new "facet-swapping" method offers a fresh perspective. It doesn't rely on the same old rules, and early tests suggest it might be the path to a solution that is both fast and reliable for all types of linear programming problems.

In summary: The paper introduces a new way to solve math optimization problems by swapping "facets" instead of hopping "corners." It skips the boring setup steps, handles tricky mazes better than the old methods, and gives mathematicians new hope for finding a perfect, fast solution for all problems.

Technical Summary

Technical Summary: On the facet pivot simplex method for linear programming

Problem Statement
The paper addresses the computational efficiency and theoretical limitations of the standard vertex pivot simplex method for solving Linear Programming (LP) problems. While Dantzig's vertex simplex method remains highly effective in practice, it lacks a proven polynomial-time complexity bound. Theoretically, the worst-case scenario for vertex methods involves an exponential number of iterations (as demonstrated by Klee-Minty cubes), and the search for a polynomial-time pivot algorithm has remained elusive for decades. Furthermore, traditional vertex methods often require a computationally expensive "Phase I" process to find an initial feasible basic solution, particularly for general LP problems involving inequality and bound constraints.

Methodology
The authors propose a facet pivot simplex method that fundamentally shifts the pivot operation from vertices to facets (constraints).

• General Formulation: The method operates on a general LP formulation:
  $$\min c^T x$$
  $$\text{subject to } A_I x = b_I, \quad A_J x \ge b_J, \quad \ell \le x \le u$$
  Unlike standard forms that convert inequalities to equalities via slack variables, this approach treats inequality constraints directly as facets of the feasible polytope.

• Algorithmic Logic:

  • Basis Definition: Instead of a basis of variables (vertices), the algorithm maintains a basis of $d$ linearly independent facets (constraints), where $d$ is the dimension of the problem.
  • Iterative Process: The algorithm starts with an initial basic solution (often derived directly from bound constraints) which is not necessarily feasible. In each iteration, it selects an entering facet (a non-basic constraint) and a leaving facet (a basic constraint) to update the basis.
  • Feasibility and Optimality: The algorithm maintains a representation of the objective vector $c$ as a non-negative linear combination of the current basic facets (satisfying a condition derived from Farkas' Lemma). It iteratively improves the solution by replacing facets to reduce constraint violations.
  • Termination: The process stops when a basic feasible solution is found. According to the optimality theorems presented, if the objective vector can be expressed as a non-negative combination of the active basic facets at a feasible point, that point is optimal.
  • Finite Convergence: The paper proves that if the "least/lowest index rule" is applied for selecting entering and leaving facets, the algorithm avoids cycling and terminates in a finite number of steps.

• Key Distinctions from Dual Simplex: While the facet pivot method shares some geometric similarities with the dual simplex method (moving between bases of constraints), it is distinct because it operates solely on the primal problem without explicitly constructing or solving a dual problem. It handles the general form directly, avoiding the conversion to standard form.

Key Contributions

1. Algorithmic Proposal: The paper introduces a specific facet pivot algorithm (Algorithm 4.1) that solves general LP problems without requiring a Phase I initialization step.
2. Theoretical Guarantees: The authors provide mathematical proofs (based on Farkas' Lemma) demonstrating that the algorithm finds an optimal solution in finite iterations and correctly identifies infeasible or unbounded problems.
3. Implementation: A MATLAB implementation of the algorithm is provided, along with implementations of Dantzig's simplex, dual simplex, and interior-point methods for comparison.
4. Handling of Constraints: The method naturally handles lower and upper bounds and free variables without introducing artificial slack variables, resulting in a smaller problem size compared to standard form conversions.

Experimental Results
The authors conducted numerical tests on several benchmark sets:

• Netlib Benchmarks: On standard Netlib problems with lower and upper bounds, the facet pivot method generally required fewer CPU seconds than Dantzig's most negative pivot rule. It successfully solved problems where the dual simplex method failed due to rank deficiency or ill-conditioning.
• Large-Scale Problems: For very large problems (e.g., $n > 50,000$), Interior Point Methods (IPM) outperformed all pivot methods, as expected. However, the facet pivot method showed robustness where the dual simplex method failed.
• Klee-Minty Cubes: The facet pivot method demonstrated significantly better performance than Dantzig's vertex method on Klee-Minty variants, requiring far fewer iterations (often linear or near-linear in dimension $d$) compared to the exponential iterations required by the vertex method.
• Random General Problems: For general LP problems requiring a Phase I in standard methods, the facet pivot method was significantly more efficient than Dantzig's method because it bypassed the Phase I initialization.
• Standard Random Problems: For standard LP problems where Phase I is not required, Dantzig's method was observed to be slightly more efficient in CPU time, though iteration counts were comparable.

Significance and Claims
The paper claims that the facet pivot simplex method offers a promising alternative to vertex-based methods, particularly for general LP problems with inequality constraints. Its primary significance lies in:

• Eliminating Phase I: By starting from a basic solution derived from bound constraints, it avoids the expensive initialization phase required by traditional simplex methods for general problems.
• Robustness: It demonstrates greater numerical stability than the dual simplex method on ill-conditioned Netlib problems.
• Hope for Polynomial Complexity: While the authors do not claim to have proven a polynomial-time bound, they suggest that this new type of pivot algorithm (operating on facets rather than vertices) provides a new avenue for research toward finding a polynomial pivot simplex method, addressing Smale's 9th problem.
• Practical Efficiency: The method is shown to be highly competitive and often superior to Dantzig's method for problems involving many inequality constraints, without the overhead of converting them to equalities.

The authors maintain a modest tone, acknowledging that Interior Point Methods remain superior for very large-scale problems and that the facet pivot method is a new direction that requires further investigation to fully understand its theoretical complexity bounds.