# 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.

- **Category**: Agentic AI
- **Subcategory**: Planning & Control Flow
- **Canonical URL**: https://designpattern.fyi/patterns/distributed_constraint_optimization/

---

## Description
**Intent**: 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.
**Context**: Several agents each hold private variables and constraints — meeting scheduling across users who don't want to expose calendars, resource allocation across teams that don't share budgets, sensor coordination across nodes that can't centralise. The global cost depends on all variables, but no single agent has the right to see them all.
**Solution**: - Cast the problem as a DCOP: each agent owns variables; constraints are factored across agents. - Run a distributed solver: ADOPT for optimal solutions; DPOP, Max-Sum, or local-search heuristics for cheaper approximate solutions. - Each agent communicates only with its 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.


## Use Cases
- 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.





## Trade-offs


### Advantages

- Global optimisation without centralising private data.

- Information boundaries respected by construction.

- Algorithm choice tunes communication cost vs solution quality.




### Considerations & Drawbacks

- Optimal algorithms (ADOPT) have exponential worst-case message complexity.

- Constraint factorisation is itself a design problem.

- Heuristic solvers may stall in local optima.







---
**Reference**: [Original Source](https://www.agentpatternscatalog.org/patterns/distributed-constraint-optimization/)