An Approximate, Efficient Solver for LP Rounding

Srikrishna Sridhar, Victor Bittorf, Ji Liu, Ce Zhang, Christopher Ré, Stephen J. Wright

Abstract

Solving NP-hard combinatorial problems often involves "LP rounding," but solving massive Linear Programs (LPs) to high precision is a major computational bottleneck. This paper demonstrates that a crude, approximate LP solution is often sufficient for rounding and introduces Thetis, a solver that uses asynchronous stochastic coordinate descent to achieve order-of-magnitude speedups over commercial solvers like Cplex without sacrificing solution quality.

Introduction

Many fundamental tasks in machine learning—such as entity resolution, text chunking, and image segmentation—can be framed as NP-hard combinatorial problems. Common examples include vertex cover, set packing, and multiway-cuts. A standard approach to tackle these problems is LP rounding: first, formulate the problem as an Integer Program (IP); second, relax the binary constraints (0 or 1) to continuous ones ([0, 1]), creating a Linear Program (LP); and finally, solve the LP and "round" the fractional results back to integers.

The "Achilles’ heel" of this approach is the relax/solve step. Commercial solvers like Cplex or Gurobi are designed to find extremely precise solutions. However, for rounding purposes, high precision is often overkill. If a rounding algorithm eventually maps 0.7 to 1.0, the difference between a solver finding 0.70000 and 0.71234 is negligible. Thetis aims to fill this gap by creating a solver optimized for "good enough" solutions at massive scales.

Problem Families and Applications

The utility of LP rounding spans a wide variety of problem families within the machine learning domain. Each family comes with specific theoretical approximation factors that dictate the quality of the rounded solution relative to the optimal integer solution.

Table 1: Problem families, their theoretical approximation factors, and corresponding machine learning applications.

As shown in the table above, problems like Set Covering are essential for classification and multi-object tracking, while Multiway-cut finds applications in computer vision and entity resolution. Thetis is designed to handle the LPs arising from these specific combinatorial relaxations efficiently.

Methods: The Thetis Solver

The authors propose a system called Thetis, which introduces several core technical contributions to accelerate the LP solving phase:

  • Quadratic Programming (QP) Approximation: Instead of solving the LP directly, Thetis transforms it into a regularized quadratic penalty formulation. This makes the objective function "smoother" and easier to optimize using first-order methods.
  • Stochastic Coordinate Descent (SCD): Thetis applies an SCD algorithm that updates one variable at a time. This approach is computationally cheap and avoids the massive matrix inversions required by traditional interior-point methods used in commercial solvers.
  • Asynchronous Parallelism: Designed for multi-core architectures, Thetis allows different threads to update the solution vector simultaneously without locking. This leads to near-linear speedups on modern hardware.
  • Theoretical Guarantees: Using Renegar’s perturbation theory, the authors prove that an $(\epsilon, \delta)$-approximate solution (one that is slightly infeasible or sub-optimal) can still be rounded to produce a high-quality integral solution.

Experimental Evaluation

The authors evaluated Thetis against several real-world and benchmark datasets to test its speed and robustness:

  • Machine Learning Tasks: Entity Linking (TAC-KBP 2010) and Text Chunking (CoNLL 2000).
  • Combinatorial Benchmarks: The Bhoslib collection of difficult graph instances.
  • Social Network Graphs (SNAP): Large-scale graphs from Amazon, DBLP, and Google+ used for Vertex Cover, Independent Set, and Multiway-cut problems. The largest LPs involved up to 25 million variables and 51 million non-zeros.

Key Insights and Results

The primary "aha moment" of this research is the realization that the inherent "slack" in rounding algorithms allows for significant error in the LP phase. By intentionally seeking a "crude" solution, Thetis utilizes algorithms (like SCD) that scale much better than exact solvers.

Key results include:

  • Speedup: Thetis was consistently up to an order of magnitude faster than Cplex-LP. For example, on the Bhoslib multiway-cut instances, Thetis was approximately 53x faster.
  • Solution Quality: Despite being an approximate solver, the final rounded solutions were nearly identical in quality to those produced by Cplex. In some cases, such as the Google+ multiway-cut, Thetis actually found better solutions than Cplex-IP within a one-hour time limit.
  • Scalability: On large SNAP social graphs, Cplex-IP often timed out or failed to solve the root-node relaxation, while Thetis provided usable solutions in minutes.

Limitations and Future Work

While Thetis represents a significant step forward, it has limitations. The theoretical guarantees currently focus on "oblivious" rounding schemes; more complex, non-oblivious schemes might require higher precision. Additionally, the performance of the quadratic penalty method depends on the penalty parameter $\beta$, which often requires manual tuning. Finally, Thetis is specialized for LPs arising from combinatorial relaxations and may not outperform commercial solvers on general-purpose LPs where high precision is a strict requirement, such as in financial modeling.

Summary updated

BibTeX
@inproceedings{sridhar2013approximate,
  author = {Srikrishna Sridhar and Victor Bittorf and Ji Liu and Ce Zhang and Christopher Ré and Stephen J. Wright},
  title = {{An Approximate, Efficient Solver for LP Rounding}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=B14oudW_-S},
}
Figure