Sherali-Adams Hierarchy
The Sherali-Adams hierarchy is a systematic method for strengthening linear programming relaxations of combinatorial optimization problems by adding variables and constraints that capture local correlations between decision variables. Introduced by Hanif Sherali and Warren Adams in 1990, it was the first hierarchy of convex relaxations to demonstrate that systematically lifting a weak relaxation could yield progressively tighter bounds on discrete optimization problems — anticipating by a decade the more celebrated sum-of-squares hierarchy and proving that the idea of "relax and tighten" was not merely a technique but a research program.
The hierarchy operates on the high-dimensional polytope of a combinatorial problem — the convex hull of all feasible binary assignments — which is typically intractable to describe explicitly. At level k of the Sherali-Adams hierarchy, the relaxation introduces variables representing the joint probabilities of all subsets of k variables taking specific values, then adds consistency constraints that force these joint variables to agree with the marginals on overlapping subsets. The level-1 relaxation is the standard linear programming relaxation. As k increases, the relaxation captures increasingly non-local interactions, converging to the exact integer polytope at level n.
The Mechanism: Lifting and Projection
The core operation is a lift-and-project procedure. Given a set of binary variables x₁, ..., xₙ, the level-k relaxation introduces new variables y_S for every subset S of at most k variables, representing the product ∏_{i∈S} xᵢ. The constraints enforce that these lifted variables behave like products: y_∅ = 1, 0 ≤ y_{i} ≤ 1, and most importantly, the Sherali-Adams constraints: for any subset S of size at most k-1 and any variable xᵢ not in S,
y_{S∪{i}} ≤ y_S and y_{S∪{i}} ≥ y_S + y_{i} - 1
These constraints encode the logical relationship between a subset and its extension: if all variables in S are 1 and xᵢ is 1, then S∪{i} must also be all 1s. The collection of all such constraints for all subsets up to size k defines the level-k Sherali-Adams polytope.
The projection back to the original variables — discarding all y_S except the singletons y_{i} — yields a relaxation of the original problem that is at least as tight as the LP relaxation and typically much tighter. The price is dimensionality: the number of lifted variables grows as O(nᵏ), making the relaxation computationally expensive for large k.
Relationship to Other Hierarchies
The Sherali-Adams hierarchy occupies a precise position in the landscape of convex relaxation hierarchies. It is strictly weaker than the sum-of-squares (SOS) hierarchy at every level: any solution feasible for the level-k SOS relaxation is also feasible for the level-k Sherali-Adams relaxation, but the converse fails. The gap between them captures exactly the difference between linear programming and semidefinite programming: Sherali-Adams is a linear hierarchy (all constraints are linear), while SOS is a semidefinite hierarchy (constraints include positive semidefiniteness of a moment matrix).
The Lovász-Schrijver hierarchy, introduced in 1991, is intermediate between Sherali-Adams and SOS: it adds semidefiniteness constraints to the Sherali-Adams lifting, producing stronger bounds than Sherali-Adams alone but weaker than SOS. The Lasserre hierarchy — another name for the SOS hierarchy in the optimization literature — is the strongest of the three. The relationship is a hierarchy of hierarchies: Sherali-Adams ⊆ Lovász-Schrijver ⊆ SOS, with each inclusion being strict.
This ordering is not merely academic. It reflects a fundamental tradeoff in approximation algorithms: linear programs are much faster to solve than semidefinite programs, and for some problems the Sherali-Adams relaxation achieves the same approximation ratio as SOS with dramatically less computational cost. The question of which hierarchy to use for a given problem is an empirical as well as a theoretical one.
Systems-Theoretic Significance
The Sherali-Adams hierarchy exemplifies a systems principle that recurs across domains: local consistency does not imply global consistency. The hierarchy enforces consistency only on overlapping subsets of bounded size. At low levels, these local consistencies are easy to satisfy simultaneously; at high levels, the accumulated constraints become so restrictive that only globally consistent solutions remain. The phase transition — the level at which local consistency finally forces global consistency — is problem-dependent and deeply connected to the underlying structure of the combinatorial object.
This same principle appears in statistical mechanics, where local Gibbs measures on overlapping regions must be globally consistent (the DLR equations) for the measure to describe a physical system. It appears in constraint satisfaction problems, where local consistency algorithms (k-consistency) succeed exactly when the constraint graph has bounded treewidth. It appears in belief propagation and the cavity method, where messages passed between local neighborhoods must converge to a globally self-consistent fixed point. The Sherali-Adams hierarchy is the optimization-theoretic expression of this universal tension between local and global.
The systems reading is that Sherali-Adams is not merely an algorithmic technique but a theory of how local information aggregates into global structure. Each level of the hierarchy corresponds to a different scale of correlation: level-1 captures no correlations (independent variables), level-2 captures pairwise correlations, level-3 captures three-way correlations, and so on. The convergence to the exact solution at level n is the statement that a system of n binary variables is fully determined by its n-way correlations — which is tautologically true, but the hierarchy reveals at what intermediate level the approximation becomes exact.
The Sherali-Adams hierarchy is undervalued in the contemporary literature, which has fixated on the SOS hierarchy as the "right" way to do convex relaxations. This fixation is a disciplinary bias: semidefinite programming is more mathematically elegant than linear programming, and elegance attracts citations. But for many practical problems — network design, scheduling, facility location — the Sherali-Adams relaxation provides bounds that are nearly as tight as SOS at a fraction of the computational cost. The hierarchy deserves to be studied on its own terms, not merely as the weak cousin of SOS.