What are LLP Algorithms?

The Lattice-Linear Predicate framework.

The key insight

Many classical optimisation problems — stable marriage, shortest paths, minimum spanning trees, market-clearing prices, housing allocation, Horn satisfiability — appear to require entirely different algorithmic techniques. Yet they share a common structure: in every case, the set of feasible solutions is closed under a natural “meet” operation, and the optimal solution is the least element of a distributive lattice that satisfies a Boolean predicate expressing feasibility.

Three ingredients

1. A distributive lattice $L$ that models the search space. Each element of $L$ is a candidate solution represented as a vector of component values.
2. A Boolean predicate $B$ on $L$ that captures the goal: $B(G)$ is true when $G$ is a feasible (or optimal) solution.
3. Lattice-linearity of $B$: whenever $B(G)$ is false, at least one component $j$ of $G$ is forbidden — meaning that no solution above $G$ with the same value of $G[j]$ can satisfy $B$. Advancing that component brings $G$ closer to a feasible solution.

The generic algorithm

Once these ingredients are in place, a single algorithm solves the problem:

LLP(B):
  G := zero vector
  while exists j such that forbidden(G, j, B):
    for all such j in parallel:
      if advancing G[j] goes beyond the top
        of the lattice: return null
      else: advance G[j]
  return G    // the least feasible solution

The algorithm repeatedly advances forbidden components until the predicate is satisfied (or the top of the lattice is reached, signalling that no solution exists). Lattice-linearity guarantees that every advance makes irrevocable progress, so the algorithm terminates at the unique least fixpoint.

Forbidden and advance — formally

Given a predicate $B$ and a vector $G$, index $j$ is forbidden if for any vector $H \geq G$ with $H[j] = G[j]$, the predicate $B(H)$ is false:

A predicate $B$ is lattice-linear if whenever $B(G)$ is false, there exists at least one forbidden index $j$.

We write $\alpha(G, j, B)$ for the minimum value to which $G[j]$ must be advanced — the smallest value such that keeping $G[j]$ below $\alpha$ would still make $B$ false for every vector above $G$. Formally:

The generic algorithm sets $G[j] := \alpha(G, j, B)$ at each step, and returns null when $\alpha$ exceeds the top of the lattice $T[j]$.

Two notations: forbidden/advance and ensure

LLP programs can be written in two equivalent ways. Consider the job scheduling problem: $n$ jobs with execution times $t[j]$ and prerequisites $\mathrm{pre}(j)$.

(a) Forbidden / advance form:

forbidden (j): G[j] < max{G[i] + t[j] | i ∈ pre(j)}
  advance:   G[j] := max{G[i] + t[j] | i ∈ pre(j)}

(b) Ensure form (when the advance expression is monotone):

ensure (j): G[j] ≥ max{G[i] + t[j] | i ∈ pre(j)}

Why it matters

• Unification. Classical algorithms are specific schedules of the generic LLP algorithm. Dijkstra and Bellman–Ford, for example, are two schedules of the same LLP instance; delta-stepping interpolates between them.
• Composability. The conjunction of two lattice-linear predicates is itself lattice-linear. This means you can add side constraints — forced or forbidden pairs in stable marriage, fairness constraints in shortest paths, budget caps in market-clearing prices — and the same algorithm solves the constrained version with no additional machinery.
• Parallelism. Because forbidden components can be advanced independently, every LLP algorithm is naturally parallel.
• Correctness by construction. Lattice-linearity guarantees termination at the unique least fixpoint, so the algorithm is correct for any evaluation order.

Problems unified by the LLP framework

For the full development — proofs, examples, and runnable demos — see Chapter 2.