Sorting Network Relaxations for Vector Permutation Problems

Cong Han Lim, Stephen J. Wright

Abstract

The Birkhoff polytope (the convex hull of the set of permutation matrices) is frequently invoked in formulating relaxations of optimization problems over permutations. The Birkhoff polytope is represented using $Θ(n^2)$ variables and constraints, significantly more than the $n$ variables one could use to represent a permutation as a vector. 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 $Θ(n \log n)$ in theory and $Θ(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.

Introduction

Many optimization problems, such as seriation in archaeology or DNA sequencing, involve finding an optimal ordering of $n$ objects. Mathematically, this often translates to the 2-SUM problem, which is NP-hard. To handle this, researchers typically relax the discrete set of permutations into a continuous convex set. The standard choice has been the Birkhoff polytope (the set of doubly-stochastic matrices), which requires $O(n^2)$ variables. For large-scale problems where $n=10,000$, this leads to 100 million variables, making standard solvers impractical.

This paper proposes using the permutahedron—the convex hull of permutation vectors—instead. While the permutahedron lives in $n$ dimensions, its direct description requires an exponential number of constraints. The authors overcome this by utilizing an extended formulation based on sorting networks.

Methodology: Sorting Networks as Geometry

The core innovation is the practical application of Goemans' sorting network polytope. A sorting network is a fixed sequence of "comparators" that sorts any input vector. Goemans (2010) proved that the set of all inputs that sort to a specific output can be represented as a polytope with a manageable number of variables and constraints.

A bitonic sorting network for $n=4$ (left) and a single comparator unit (right).

By using a Bitonic Sorting Network, the authors create an extended formulation of the permutahedron that uses only $O(n \log^2 n)$ variables and linear constraints. This "extension complexity" win allows for representing permutations much more efficiently by adding "hidden" internal variables representing the states of the sorting network.

Regularization and Solution Recovery

Since optimization occurs in a relaxed continuous space, the resulting solution is often not a discrete permutation. To address this, the authors introduce two key techniques:

  1. Vector-Based Regularization: Unlike traditional matrix-based methods, this approach penalizes the distance from the "center" of the polytope. This is more natural for vector-based representations and maintains convexity while pushing solutions toward the vertices.
  2. Randomized Recovery: To "snap" the continuous solution back to a valid discrete permutation, the authors add a small amount of Gaussian noise and then sort the resulting vector.
Visualization of the convex relaxation on the permutahedron for $n=3$. The hexagon represents the permutahedron, while the ellipses represent level sets of a quadratic objective.

Key Results and Scalability

The authors evaluated their approach on the Munsingen archaeology dataset and synthetic Linear Markov Chain data.

  • Computational Efficiency: For large problems ($n=5,000$), the sorting network approach converged significantly faster than state-of-the-art Birkhoff-based methods.
  • Scalability: The method successfully solved instances with $n=10,000$, a scale previously prohibitive for $O(n^2)$ formulations.
  • Solution Quality: On real-world data, the method achieved objective values superior to spectral methods and comparable to the much slower Birkhoff-based approach.

Conclusion

By leveraging the geometric properties of sorting networks, this work provides a scalable framework for permutation-based optimization. The reduction from $O(n^2)$ to $O(n \log^2 n)$ complexity opens doors for applying convex relaxation techniques to massive datasets in fields like ranking, computer vision, and bioinformatics.

Summary updated

Abstract

The Birkhoff polytope (the convex hull of the set of permutation matrices) is frequently invoked in formulating relaxations of optimization problems over permutations. The Birkhoff polytope is represented using $Θ(n^2)$ variables and constraints, significantly more than the $n$ variables one could use to represent a permutation as a vector. 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 $Θ(n \log n)$ in theory and $Θ(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{lim2014sorting,
  author = {Cong Han Lim and Stephen J. Wright},
  title = {{Sorting Network Relaxations for Vector Permutation Problems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=Skbgqwbubr},
}
Figure