View source for 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 (SoS) Hierarchy|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|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|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|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|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|constraint satisfaction problems]]''', where local consistency algorithms (k-consistency) succeed exactly when the constraint graph has bounded treewidth. It appears in '''[[Belief Propagation|belief propagation]]''' and the '''[[Cavity Method|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.''

[[Category:Mathematics]]
[[Category:Computer Science]]
[[Category:Systems]]
[[Category:Optimization]]