When we confront NP-hard combinatorial optimization problems, our standard recourse is relaxation. We take discrete, intractable constraints—such as forcing a variable $x_i$ to be exactly $0$ or $1$—and relax them into continuous bounds, allowing $x_i$ to sit anywhere in the interval $[0, 1]$. This transforms a hard discrete problem into a tractable Linear Program (LP) or Semidefinite Program (SDP).
However, standard relaxations suffer from a fundamental flaw: integrality gaps. A standard LP or SDP looks at the optimization landscape through a highly localized or purely pairwise lens. It can easily be fooled by fractional solutions that look valid locally but are globally impossible. For instance, as shown by Amit Kumar et al. in On the Optimality of a Class of LP-based Algorithms, simple LP relaxations hit an insurmountable performance barrier for broad classes of packing and covering problems.
To breach these barriers, we need a systematic way to tighten our mathematical programs. This is where lift-and-project hierarchies (such as the Sherali-Adams, Lovász-Schrijver, and Lasserre hierarchies) come in. Instead of treating variables in isolation, these hierarchies systematically introduce higher-order constraints that capture dependencies between multiple variables at once.
The Core Intuition: Lifting and Local Consistency
To understand why lift-and-project hierarchies work, we must look at how they alter the geometry of the relaxation. The process relies on two core steps:
- Lifting: We project our problem into a much higher-dimensional space. If our original problem has $n$ variables, we introduce new variables $x_S$ for subsets of variables $S$. A variable like $x_{\{i, j, k\}}$ is designed to represent the joint behavior or higher-moment relationship of the base variables $i, j,$ and $k$.
- Projecting: After enforcing strict consistency constraints on these higher-dimensional variables, we project the tightened space back down to our original dimensions.
The magic of this architecture lies in enforcing local consistency. In a standard relaxation, an LP might assign fractional values to variables in a way that corresponds to no real-world discrete assignment. A lift-and-project hierarchy prevents this by requiring that for any small subset of variables, the fractional values must behave exactly like a valid probability distribution over true, local integer solutions.
As Anupam Gupta et al. demonstrate in Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results, lifting variables into a higher-dimensional space allows the relaxation to capture these local distributions over solutions. By forcing the optimization process to respect joint probability distributions over small subsets of elements, as highlighted by Dmitrii Avdiukhin et al. in Approximation Scheme for Weighted Metric Clustering via Sherali-Adams, we eliminate the fractional anomalies that typically trick simpler linear programs.
The Hierarchy: Trading Time for Tightness
This framework is called a hierarchy because it operates in rounds or levels, creating a tunable trade-off between computational complexity and approximation quality.
- Level 1 corresponds to the standard, weak LP or SDP relaxation.
- Level $k$ enforces local consistency on all subsets of variables up to size $k$.
- Level $n$ (where $n$ is the total number of variables) perfectly reconstructs the convex hull of all feasible integer solutions, yielding the exact optimal integer solution.
Of course, this precision comes at a cost. Enforcing consistency across subsets of size $k$ requires solving an optimization problem with $O(n^k)$ variables and constraints. Mark Rowland et al. explore this trade-off in Conditions beyond treewidth for tightness of higher-order LP relaxations, detailing how each successive level systematically tightens the relaxation relative to the integer optimum.
Level 1 (Standard LP) ---> Level k (Consistent Subsets of size k) ---> Level n (Exact Convex Hull)
[Fast / Large Gap] [Polynomial Time / Tighter Gap] [Exponential Time / Zero Gap]
To understand the theoretical limits of these tools, researchers map out "integrality gaps" at higher levels of the hierarchy. For example, Eden Chlamtác et al. in Sherali-Adams Integrality Gaps Matching the Log-Density Threshold proved that even higher rounds of the hierarchy cannot breach certain fundamental performance barriers for dense subgraph problems. Similarly, Aditya Bhaskara et al. established polynomial integrality gaps in Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph, defining the boundaries of what strong semidefinite programming relaxations can achieve.
Why It Works: Faithful Rounding and Conditioning
Solving a tightened relaxation only gives us a fractional solution. The ultimate goal is to round this fractional solution into a valid integer solution without losing too much value.
In standard relaxations, rounding is difficult because variables are rounded independently, which destroys structural correlations. Hierarchies solve this problem because the higher-level variables explicitly preserve high-moment relationships. As Eden Chlamtac et al. demonstrate in Everywhere-Sparse Spanners via Dense Subgraphs, this higher-order structural information enables "faithful" randomized rounding, allowing algorithms to maintain complex probabilistic dependencies across network structures where simpler hierarchies fail.
Furthermore, because the lifted variables behave like local probability distributions, they unlock a powerful algorithmic technique: conditioning. An algorithm can select a variable, fix its value to a specific discrete choice (as if conditioning a random variable), and then propagate that choice to mathematically force consistency across the remaining variables.
The authors of Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints leverage this exact mechanism. By increasing the level of the hierarchy and conditioning on specific variables, their algorithm systematically steers the fractional solution toward the true convex hull of feasible schedules.
From Linear Programs to Semidefinite Matrices and Ideals
The lift-and-project philosophy is not restricted to linear constraints; it extends naturally to Semidefinite Programming (SDP) and algebraic geometry.
When applied to SDPs, higher levels of the hierarchy (like the Lasserre hierarchy) introduce matrix constraints that capture non-linear, global dependencies. For instance, Siavosh Benabbas et al. demonstrate in Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection that higher levels of the Lasserre hierarchy provide the necessary constraints to handle complex vertex partitioning dependencies that defeat standard pairwise SDPs. Similarly, Nikhil Bansal et al. show in On the Lovász Theta Function for Independent Sets in Sparse Graphs that combining higher levels of a hierarchy with semidefinite relaxations yields significantly tighter integrality gaps for independent set problems on sparse graphs.
This perspective can be generalized even further to optimize systems of higher-degree polynomials. As João Gouveia et al. establish in Theta Bodies for Polynomial Ideals, we can construct a sequence of nested convex sets called "theta bodies." These bodies are defined using polynomials that are representable as sums of squares (SOS) modulo a given polynomial ideal. By utilizing combinatorial moment matrices, these abstract algebraic structures are rendered computationally tractable as projections of spectrahedra, bridging algebraic geometry with practical semidefinite programming.
Breaching Long-Standing Theoretical Walls
The ultimate validation of lift-and-project hierarchies is their practical success in breaking through approximation barriers that resisted traditional methods for decades.
Correlation Clustering
For nearly twenty years, researchers hit a mathematical wall in Correlation Clustering, unable to achieve an approximation ratio better than 2. Standard edge-based relaxations simply could not see the global structure. By moving to a higher-order relaxation hierarchy, Vincent Cohen-Addad et al. proved in Correlation Clustering with Sherali-Adams that considering the joint distributions of larger vertex subsets allows the optimization process to capture complex dependencies, finally breaching the approximation barrier of 2.
The Santa Claus Problem
In the "Santa Claus" max-min fair allocation problem, standard configuration LPs suffer from massive integrality gaps. To circumvent this, Etienne Bamas et al. designed a path-based linear programming relaxation incorporating lift-and-project constraints in Better Trees for Santa Claus, successfully breaking a long-standing logarithmic barrier.
While Etienne Bamas later mapped out the precise limitations of these tools in Lift-and-Project Integrality Gaps for Santa Claus by proving where path-based variants fail, the work highlights a remarkable property of the hierarchy: the transition from a single round to two rounds of a hierarchy can fundamentally bridge the gap between algorithmic failure and successful problem resolution.
Key Foundational Work
Theta Bodies for Polynomial Ideals (2010) — contributed 5 concept elements to this direction.
On the Optimality of a Class of LP-based Algorithms (2009) — contributed 1 concept elements to this direction.