Distributed Constraint Optimization
A group of agents jointly assigns values to shared variables to minimise (or maximise) a global cost defined by inter-agent constraints, exchanging only the messages needed.
Problem
Centralising the whole problem is the easy answer but often illegal, expensive, or politically infeasible. Each agent solving locally produces solutions that violate global constraints. Without a distributed coordination algorithm that respects information boundaries, the team cannot find a global-cost-minimising assignment without surrendering privacy or autonomy.
Solution
Cast the problem as a DCOP: each agent owns variables; constraints are factored across agents. Run a distributed solver (ADOPT for optimal, DPOP, Max-Sum, or local-search heuristics for cheaper). Each agent communicates only with constraint-neighbours. The algorithm terminates with each agent holding an assignment that is consistent with the others and minimises (or approximately minimises) global cost. For LLM-agent applications, the LLM may serve as a propose-and-evaluate step at each agent, with a small DCOP-like backbone enforcing global consistency.
When to use
- Several agents hold variables/constraints that cannot be centralised.
- Global cost depends on the joint assignment.
- Some algorithm in the DCOP family fits the cost/quality budget.
Open the full interactive page →
Diagram, neighbourhood map, code examples, related patterns and full provenance.