---
artifact_kind: optimizer-card
artifact_name: cp-sat
version: 1.0.0
owner: Nous · agreement-search team
last_reviewed: 2026-04-25
next_review: 2026-07-25
optimizer_kind: cp-sat
related_phase_179_tasks: [179.4.2.4]
---

# Optimizer Card — cp-sat v1.0.0

## 1. Identity

- **Optimizer name:** cp-sat
- **Algorithm family:** branch-and-bound CP-SAT / MILP with bounds consistency,
  all-different propagation, MRV variable selection, and upper-bound pruning.
- **Implementation source:** `libs/nous/agreement-search/src/cp-sat.ts`.
  Self-contained; no external solver dependency. Integration with native solvers
  (OR-Tools, GLPK) is a roadmap item for cases beyond a few dozen variables.
- **Intended use:** discrete-structure agreements — payment schedules, milestone
  fractions, vote thresholds, roster assignments, routing, shipment terms,
  budget allocations — where feasibility is best discovered by inference rather
  than trial and error.

## 2. Scoring rule

- **Utility aggregation:** caller-supplied scalar fitness on each feasible leaf.
  Pruning uses the optional `fitnessUpperBound(partial)` callback: when the
  best-possible completion is below the incumbent, the subtree is skipped.
- **Fairness metrics reported:** post-leaf, via `fairness-metrics.ts`.
- **Handling of hard constraints:** linear constraints `Σ aᵢ·xᵢ ≤ | ≥ | = rhs`
  propagate via interval arithmetic. All- different constraints remove assigned
  values from group domains.
- **Handling of uncertainty:** the kernel itself is deterministic; the caller's
  fitness function may consume posterior mean / LCB.

## 3. Inputs

- **Variable space:** caller-supplied `VariableSpec` records — finite domain
  (integer range, boolean, enum, or discretized continuous) + `apply` callback
  that materializes the value into the candidate.
- **Constraints:** linear constraints + all-different groups + arbitrary
  caller-supplied feasibility predicates.
- **Time / iteration budget:** node-cap, wall-clock cap, optional best-first
  search.
- **Randomness:** value-selection randomization with seeded `mulberry32`;
  default is in-order.

## 4. Outputs

- **Accepted candidate contract:** `AgreementCandidate` materialized from the
  best feasible assignment.
- **Diagnostics:** node count, prune count, propagation steps, conflict count.
- **Uncertainty propagation:** caller's fitness function decides how posterior
  detail rides through; the kernel is transparent.

## 5. Evaluation

| Metric                          | Value                                 | Evaluator card                                                      | Date       |
| ------------------------------- | ------------------------------------- | ------------------------------------------------------------------- | ---------- |
| Pareto-front coverage           | not the goal — single best feasible   | n/a                                                                 | 2026-04-25 |
| Diversity preservation          | enumerable via `top-k` mode if caller | n/a — `cp-sat.test.ts`                                              | 2026-04-25 |
|                                 | requests                              |                                                                     |            |
| Feasibility correctness         | every returned leaf passes            | n/a — `cp-sat.test.ts`                                              | 2026-04-25 |
|                                 | `filterCandidates` (asserted)         |                                                                     |            |
| Regret vs oracle                | optimal under the user's constraint   | [baseline-benchmark-gate](../evaluators/baseline-benchmark-gate.md) | 2026-04-25 |
|                                 | model when search exhausts            |                                                                     |            |
| Specification-gaming resistance | constraint structure prevents stub    | [fairness-suite](../evaluators/fairness-suite.md)                   | 2026-04-25 |
|                                 | clauses; spec-audit on returned leaf  |                                                                     |            |
| Runtime (typical)               | milliseconds-to-seconds for ~30       | n/a — deterministic synchronous kernel                              | 2026-04-25 |
|                                 | variables and ~10 constraints         |                                                                     |            |
| Cost per run                    | $0 (LLM-free, no external solver)     | n/a                                                                 | 2026-04-25 |

## 6. Known limitations

- Memory scales with `O(nodes × variables)`; sized for a few dozen variables.
  Larger problems should shell to a native solver.
- Bounds consistency is not arc-consistency; some constraint structures benefit
  from stronger propagators (GAC, regular constraints) that this kernel does not
  implement.
- Linear constraints only; non-linear (e.g., multiplicative) constraints must be
  linearized by the caller.

## 7. Guardrails

- **Candidate safety gate:** `filterCandidates` on every feasible leaf.
- **Clause static validation:** inside `filterCandidates`.
- **Redline separation:** redlines encoded as hard constraints in the variable /
  linear-constraint spec; the solver cannot relax them.
- **Determinism guarantee:** byte-identical results given seed and problem.

## 8. References

- `libs/nous/agreement-search/src/cp-sat.ts`
- Brailsford, Potts, Smith (1999), "Constraint satisfaction problems".
- `docs/research/bibliography.md` §discrete-optimization