Beyond the Birkhoff Polytope: Convex Relaxations for Vector Permutation Problems

Cong Han Lim, Stephen J. Wright

Many real-world computational challenges—from DNA sequencing and image reconstruction to ranking systems—require finding the optimal ordering, or permutation, of $n$ objects. Because searching through all $n!$ possible permutations is computationally impossible for large datasets, researchers typically "relax" the problem into a continuous one that can be solved using convex optimization.

The standard tool for this relaxation is the Birkhoff polytope, which is the convex hull of all permutation matrices. However, this approach comes with a severe scaling bottleneck: the Birkhoff polytope requires $O(n^2)$ variables and constraints. If you are trying to order 10,000 items, you are faced with 100 million variables—a scale that overwhelms most standard solvers.

This paper introduces a significantly more efficient method for solving optimization problems involving permutations. By swapping the computationally expensive Birkhoff polytope for a "sorting network polytope," the authors reduce the constraint complexity from $O(n^2)$ to $O(n \log^2 n)$ in practice. This allows solvers to handle much larger datasets without sacrificing solution quality.

The Permutahedron and Sorting Networks

Instead of relying on $n \times n$ matrices, the authors focus on the permutahedron, the convex hull of permutation vectors (e.g., $[1, 2, 3]$). While the permutahedron has a simple definition, it traditionally features an exponential number of facets, making it seemingly unusable for optimization.

The key innovation in this work is the first practical application of Goemans’ sorting network construction. Rather than defining the permutahedron directly, the authors utilize a "sorting network"—a sequence of comparators designed to sort a list.

A 4-wire sorting network illustrating the comparator structure used to define the extended formulation of the permutahedron.

By representing the internal states of these comparators as linear constraints, they create an "extended formulation" of the permutahedron. This "lifting" technique adds a few helper variables to describe a complex shape with far fewer constraints than would be required in its original space. While the theoretically optimal AKS sorting network achieves $O(n \log n)$ complexity, the authors found that Batcher’s bitonic sorting network ($O(n \log^2 n)$) is much easier to implement and performs excellently in practice.

Vector-Based Regularization

When relaxing a discrete problem into a continuous convex space, there is a risk that the solver will settle for a "fuzzy" average in the middle of the polytope rather than a distinct ordering. To prevent this, the authors introduce a novel vector-based regularization scheme.

The permutahedron (hexagon) with level sets illustrating how the regularization scheme pushes the continuous solution toward the discrete permutation vertices.

This regularization term is specifically designed to push the continuous solution outward toward the vertices of the permutahedron (which correspond to actual, discrete permutations) while maintaining the problem's overall convexity. It is mathematically "looser" than previous matrix-based versions, allowing for stronger regularization without breaking the properties that make the problem solvable.

Experimental Results: 2-SUM Seriation

The authors applied this framework to the "noisy seriation problem" (specifically the 2-SUM formulation), which involves recovering a linear order from a noisy similarity matrix. They evaluated the approach using a Linear Markov Chain reordering problem, generating a chain of $n$ random variables where similarity decreases with distance, and adding Gaussian noise to the covariance matrix.

The results demonstrated significant improvements:

  • Scaling: The permutahedron-based formulation converged significantly faster than the Birkhoff-based formulation as $n$ increased. Using the Gurobi interior-point solver, they successfully scaled the problem up to $n=10,000$.
  • Solution Quality: In noisy scenarios, this convex approach outperformed traditional spectral methods (like the Fiedler vector). A major advantage of this convex formulation is its ability to easily incorporate "side information" (e.g., hard constraints like "item A must come before item B").

Limitations and Future Work

While highly effective for vector permutation problems like seriation and ranking, the authors note that the permutahedron is a projection of the Birkhoff polytope. For more complex problems that depend heavily on the full mapping matrix (such as graph matching), this projection might lose vital information.

Furthermore, while the formulation is compact, it still relies on high-quality interior-point solvers. Future work may involve applying specialized first-order methods to push the scale even further, and extending this "sorting network" technique to other permutation-heavy fields like computer vision and machine learning ranking systems.

Summary updated

Abstract

The Birkhoff polytope (the convex hull of the set of permutation matrices), which is represented using $\Theta(n^2)$ variables and constraints, is frequently invoked in formulating relaxations of optimization problems over permutations. Using a recent construction of Goemans (2010), we show that when optimizing over the convex hull of the permutation vectors (the permutahedron), we can reduce the number of variables and constraints to $\Theta(n \log n)$ in theory and $\Theta(n \log^2 n)$ in practice. We modify the recent convex formulation of the 2-SUM problem introduced by Fogel et al. (2013) to use this polytope, and demonstrate how we can attain results of similar quality in significantly less computational time for large $n$. To our knowledge, this is the first usage of Goemans' compact formulation of the permutahedron in a convex optimization problem. We also introduce a simpler regularization scheme for this convex formulation of the 2-SUM problem that yields good empirical results.
BibTeX
@inproceedings{lim2014beyond,
  author = {Cong Han Lim and Stephen J. Wright},
  title = {{Beyond the Birkhoff Polytope: Convex Relaxations for Vector Permutation Problems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=Skbgqwbubr},
}

Loading related content...

Figure