Distributed Constraint Optimization

"I know my own variable and I hear from my neighbors. From that keyhole I am asked to help optimize a problem no single one of us has ever seen whole."

An Agent Holding One Corner of a Constraint

The earlier sections of this chapter described coordination as a style: a blackboard where agents post partial results, a contract net where a manager auctions a task to bidders. Those are protocols, useful and intuitive, but they do not by themselves tell you whether the joint decision the agents reach is good, let alone optimal. Distributed Constraint Optimization, almost always abbreviated DCOP, is the framework that makes the question answerable. It models a coordination problem as a graph of variables and constraints, fixes a single scalar objective, and then asks for algorithms that optimize that objective using only local communication. Because the objective is explicit and the communication restriction is explicit, we can finally say precise things: this algorithm is guaranteed to find the best joint assignment, that one is not but uses far fewer messages, this third one is belief propagation in disguise. Coordination stops being a vibe and becomes an optimization problem with a cost model.

1. The DCOP Model: Variables You Own, Constraints You Share Intermediate

A DCOP has four ingredients. There is a set of agents. There is a set of variables, and each variable is owned and controlled by exactly one agent; the agent, and only that agent, decides the value its variable takes. Each variable draws its value from a finite domain (the colors a region may take, the time slots a meeting may occupy, the target a sensor may track). Finally there are constraints, and this is where the distribution bites: a constraint is a function that assigns a utility to a combination of values of two or more variables, and the variables a single constraint touches can belong to different agents. No agent owns a constraint that spans others; the constraint is a shared object that two neighbors must jointly satisfy. The agents whose variables appear together in a constraint are called neighbors, and the only communication a DCOP algorithm permits is between neighbors.

The global objective is the sum of all constraint utilities. Writing $\mathbf{x}$ for the full joint assignment of every variable, $u_{ij}(x_i, x_j)$ for the utility of the constraint between variables $i$ and $j$, and $E$ for the set of constrained pairs, the problem is

The catch that makes this hard, and the reason it belongs in a book about distribution, is that no single agent can evaluate $U(\mathbf{x})$. Agent $i$ can see the terms $u_{ij}$ for its own neighbors $j$, because it can ask those neighbors for their current values, but it has no access to the rest of the sum and no authority to set anyone else's variable. The whole problem exists nowhere except spread across the agents, exactly the situation Figure 27.6.1 depicts. Optimizing a function that no participant can compute, using only conversations between neighbors, is the defining challenge of the field.

2. Three Problems That Are Secretly the Same DCOP Beginner

The reason DCOP earns a chapter rather than a footnote is that a strikingly broad range of coordination tasks collapse onto this one model. Distributed meeting scheduling is the canonical example: each person is an agent, each meeting they must attend is a variable whose domain is the candidate time slots, and a constraint between two people who share a meeting pays high utility when they pick a slot that works for both and low utility when their calendars collide. Nobody publishes their full calendar to a central server; people negotiate pairwise, which is exactly the neighbor-only communication DCOP assumes.

Sensor-target assignment is a second instance. Each sensor is an agent choosing which target to track, constraints between sensors that can see overlapping regions reward complementary coverage and penalize redundant focus, and the global objective is total tracking quality across the field. Distributed resource allocation is a third: agents are tasks or services, variables are the machines or channels they claim, and constraints penalize two agents grabbing the same scarce resource. In every case the structure is identical, agents owning variables, neighbor constraints, one global sum to maximize, which is precisely why a single family of algorithms serves all of them. Our runnable demo in Section 5 uses distributed graph coloring, the cleanest stand-in for the meeting-scheduling structure: pick a color (slot) so that you differ from your neighbors.

3. The Completeness-Versus-Cost Spectrum Advanced

Given the model, the algorithms arrange themselves along one axis, and understanding that axis is more valuable than memorizing any single method. At one end sit the complete algorithms, which guarantee they return the true global optimum $\mathbf{x}^\star$. ADOPT (Asynchronous Distributed Optimization) arranges the agents into a tree and runs an asynchronous, distributed branch-and-bound search, propagating cost bounds up and down until every agent can certify that no better joint assignment exists. DPOP (Distributed Pseudotree Optimization) also builds a tree but instead performs one bottom-up pass of dynamic programming: each agent sends its parent a utility table summarizing the best it can do for every combination of values along its separator, then a top-down pass reads off the optimal assignment. Both are correct for any DCOP. The price is structural: ADOPT can send an exponential number of messages on hard instances, and DPOP's utility tables grow exponentially with the tree's induced width, so a single message can be astronomically large. Completeness is real, but it is not free, and on a densely constrained graph it can be unaffordable.

At the other end sit the incomplete local-search algorithms, which give up the guarantee in exchange for graceful scaling. The Distributed Stochastic Algorithm (DSA) is the simplest: every agent repeatedly looks at its neighbors' current values, computes its own best response, and switches to it with some probability $p$ (the randomness is essential, because if every agent greedily switched at once, two neighbors could flip in lockstep forever). Maximum-Gain Messages (MGM) replaces the coin flip with a negotiation: each agent computes the utility gain it could achieve by moving, tells its neighbors that number, and only the agent with the locally largest gain is permitted to move this round, which guarantees the global utility never decreases. Max-Sum is the most sophisticated of the three and the most interesting structurally, because it is belief propagation run on the constraint graph. Each of these uses a bounded, typically small, number of messages per round and scales to thousands of agents, but each can halt at a local optimum that the complete algorithms would have escaped. Table 27.6.1 lays the spectrum out.

4. Max-Sum Is Message Passing on a Factor Graph Advanced

Max-Sum deserves a closer look because it ties this chapter directly to ideas the book has already built. Represent the DCOP as a factor graph: a node for every variable, a node for every constraint (a "factor"), and an edge connecting a constraint to each variable it touches. Max-Sum then runs the max-sum (max-plus) variant of belief propagation on this graph. Variable nodes and factor nodes exchange messages: a variable sends each neighboring factor a vector, one entry per domain value, summarizing the best total utility it can contribute for each of its possible values, and a factor sends back the best it can offer given the constraint it enforces. After messages converge, each agent reads off the value that maximizes the sum of incoming messages. On a tree the procedure returns the exact optimum; on a graph with cycles it becomes the incomplete, loopy variant that usually finds a strong local optimum.

If "message passing on a graph, where each node aggregates vectors from its neighbors and sends a summary back" sounds familiar, that is not a coincidence. It is the same computational skeleton as the vertex-centric and message-passing model behind graph neural networks, developed in Section 13.3: a node gathers messages from neighbors, applies a local function, and scatters a new message outward, all in parallel across the graph. Max-Sum is that pattern applied to coordination rather than representation learning, which is why a DCOP coordinating a thousand agents and a GNN embedding a million nodes can share a runtime and a mental model. The factor-graph view also explains the cost entry in Table 27.6.1: a Max-Sum message carries one value per domain element, so its size is linear in the domain, far cheaper than DPOP's exponential separator tables.

5. A Distributed Local-Search Solver, From Scratch Intermediate

The cleanest way to feel how an incomplete DCOP algorithm works is to build one. The code below implements DSA on a small distributed graph-coloring problem, our meeting-scheduling stand-in: six agents, each owning one variable with three possible colors (time slots), and nine constraints that each pay one unit of utility when the two endpoints differ. The maximum possible utility is a proper coloring with no clashes. Crucially, each agent's local_gain is computed from only its own candidate value and the values its neighbors currently report; no function ever touches the whole assignment except the referee that scores the run. The agents improve the global objective purely through local best-response moves, exactly the dynamic Figure 27.6.1 sketched. We then compare against the true optimum found by brute force, the centralized answer a complete algorithm would guarantee.

import itertools, random

# A small distributed graph-coloring DCOP (a meeting-scheduling stand-in):
# each agent owns ONE variable (a color / time slot). A constraint on an edge
# pays utility 1 when the two endpoints differ, 0 when they clash. Maximizing
# the global sum of edge utilities = a proper coloring with the fewest clashes.
# Agents see ONLY their own value and the values their neighbors send them.

EDGES = [(0,1),(0,2),(1,2),(1,3),(2,4),(3,4),(3,5),(4,5),(0,5)]
N, K = 6, 3                      # 6 agents, 3 available colors
NEI = {i: [b if a==i else a for (a,b) in EDGES if i in (a,b)] for i in range(N)}

def global_util(assign):
    return sum(1 for (a,b) in EDGES if assign[a] != assign[b])

def local_gain(i, val, assign):
    # utility this agent contributes given ONLY its neighbors' current values
    return sum(1 for j in NEI[i] if val != assign[j])

def brute_optimum():
    best = max(global_util(list(a)) for a in itertools.product(range(K), repeat=N))
    return best

def dsa(seed, rounds=30, p=0.7):
    rng = random.Random(seed)
    assign = [rng.randrange(K) for _ in range(N)]   # random start
    history = [global_util(assign)]
    for _ in range(rounds):
        # every agent looks at the neighbor values it just received, finds its
        # best response, and adopts it with probability p (DSA breaks symmetry)
        proposals = {}
        for i in range(N):
            cur = local_gain(i, assign[i], assign)
            best_val, best_g = assign[i], cur
            for v in range(K):
                g = local_gain(i, v, assign)
                if g > best_g:
                    best_val, best_g = v, g
            if best_val != assign[i] and rng.random() < p:
                proposals[i] = best_val
        for i, v in proposals.items():
            assign[i] = v
        history.append(global_util(assign))
    return assign, history

opt = brute_optimum()
print(f"agents={N}  colors={K}  constraints={len(EDGES)}  centralized optimum={opt}")
print()
solved = 0
for seed in range(5):
    final, hist = dsa(seed)
    print(f"run seed={seed}: utility trace {hist[0]:>2} -> "
          + " ".join(f"{h}" for h in hist[1:9]) + f" ...  final={hist[-1]}/{opt}")
    if hist[-1] == opt:
        solved += 1
print()
print(f"reached the optimum in {solved}/5 random restarts using only neighbor messages")

agents=6  colors=3  constraints=9  centralized optimum=9

run seed=0: utility trace  5 -> 8 9 9 9 9 9 9 9 ...  final=9/9
run seed=1: utility trace  6 -> 7 7 8 8 8 8 8 8 ...  final=8/9
run seed=2: utility trace  5 -> 8 9 9 9 9 9 9 9 ...  final=9/9
run seed=3: utility trace  8 -> 9 9 9 9 9 9 9 9 ...  final=9/9
run seed=4: utility trace  7 -> 7 8 9 9 9 9 9 9 ...  final=9/9

reached the optimum in 4/5 random restarts using only neighbor messages

Two things in Output 27.6.1 carry the section's message. First, the utility rises toward the optimum using nothing but neighbor information; no agent ever computed $U(\mathbf{x})$, yet $U$ went up, which is the entire promise of distributed local search. Second, the seed=1 run got stuck at 8, one below optimal, and stayed there. That is not a bug; it is the definition of an incomplete algorithm. DSA found a configuration where no single agent can improve its own contribution by moving alone, even though a coordinated two-agent swap would have reached 9. ADOPT or DPOP would have proven the value 9 and never settled for 8, at the cost of much heavier communication. The gap between "4 out of 5" and "always" is the price of the cheap messages, and seeing it in real output is worth more than any guarantee stated in prose.

# pip install pydcop ; problem.yaml declares agents, variables, domains, constraints
# Run the same coloring problem with an incomplete solver ...
#   dcop.py solve --algo dsa      --timeout 10 problem.yaml
# ... then with a complete one, by changing a single argument:
#   dcop.py solve --algo dpop                  problem.yaml
#
# Or drive it from Python:
from pydcop.dcop.yamldcop import load_dcop_from_file
from pydcop.algorithms import dsa
dcop = load_dcop_from_file("problem.yaml")     # variables + constraints, no central view
# pyDCOP builds the agent computation graph and the neighbor message passing itself

6. Where DCOP Sits, and Where It Leads Intermediate

DCOP is the rigorous spine of decentralized coordination, but it is a static one: it assumes the constraints and utilities are fixed and known to the agents that share them, and it solves for one good joint assignment. Real multi-agent systems are rarely so still. When the utilities are unknown and must be learned from experience, and when the joint decision must adapt as the environment changes, the natural successor is multi-agent reinforcement learning, where agents learn coordinating policies rather than solving a fixed constraint graph; that is the subject of Chapter 30, and the factored value functions used there borrow the constraint-graph structure of DCOP directly. When coordination must emerge from very simple agents following local rules at massive scale, the framing shifts again toward swarm intelligence, Chapter 31, where the global objective is implicit in the collective behavior rather than written as an explicit sum.

What makes DCOP worth carrying into those settings is the discipline it imposes: state the objective, fix the communication budget, and then ask plainly which point on the completeness-versus-cost spectrum a system can afford. That discipline is the same one the next section applies more broadly, turning from the formal optimization frame to the general patterns of coordination and cooperation that hold when agents share goals but not a solver. We pick up that thread in Section 27.7.