Optimizer Card — cp-sat v1.0.0

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

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#

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