unifier

Constraint satisfaction / optimization (CSP/COP) modeling and solver framework for Rust, integrating with pathwise's generic search and optimization traits (see "Solver stack" below for how far that integration currently goes).

Status

Pre-release, not yet published to crates.io. The core model, constraint propagation, global constraints, hard/soft scoring with weighted objectives, fallible model validation (ConstraintGraph::validate / ModelBuilder::build), and five solver strategies (Backtracking, Branch & Bound with optimistic-bound pruning, Local Search, LNS, Parallel Portfolio) are implemented and tested. SolveOutcome reports status (Optimal / Feasible / Infeasible / Aborted(reason)), the best solution found, search statistics, and — for Branch & Bound — a score bound.

See plan/00-STATUS.md (local, untracked) for the implementation log, plan/08-project-evaluation.md for the first independent maturity assessment, and plan/09-project-reevaluation-roadmap.md for the follow-up assessment (including a since-fixed false-optimality-proof bug) and the maturity roadmap — read its release recommendation before relying on this for production planning scenarios.

Problem class

Constraint Satisfaction Problems (CSP) — and, once an objective is optimized rather than just satisfied, Constraint Optimization Problems (COP): variables, domains, constraints, and (for COP) an objective. Typical instances: scheduling, timetabling, resource allocation.

These problems are generally NP-hard — there is no single "best algorithm" the way there is for sorting. unifier's solver strategies are therefore interchangeable rather than fixed, and the design targets an anytime solver: a valid solution fast, then iterative improvement, cancellable at any point.

Core model

• Variable / Domain — Variable (integer-valued, identified by VariableId) with a Domain: Range { min, max } for contiguous bounds, or Explicit(BTreeSet<i64>) once a value is punched out of the middle of a range
• Constraint — Equal, NotEqual, LessThanOrEqual, AllDifferent, NoOverlap, Cumulative, Precedence, AllowedValues/ForbiddenValues, ExactlyOne/AtMost/AtLeast
• Objective — WeightedSum soft-score terms (hard constraints are never violated in a feasible solution; soft terms are a weighted preference to maximize), aggregated into a HardSoftScore
• Interval / Resource / Activity / Group — scheduling-oriented data types (start/duration/end, capacity, resource demands, grouped activities sharing one interval). ModelBuilder::compile_scheduling_model compiles them into the constraint graph automatically (Cumulative for capacity > 1 resources, NoOverlap for unary ones, LessThanOrEqual pairs for group containment), plus calendar exclusions, optional (presence-gated) activities, resource alternatives, and a tardiness objective helper — see plan/12-scheduling-vertical.md

The problem itself is modeled as a constraint graph (a hypergraph of variables, constraints, and objectives), not a tree — the tree only emerges as part of a solver's search process. ConstraintGraph::validate / ModelBuilder::build reject structurally invalid models (unknown variable references, empty domains, duplicate IDs, self-contradictory constraint parameters) before a solver ever sees them.

Solver stack

pathwise provides the generic Problem/OptimizationProblem traits and interchangeable search/optimization strategies (A*, branch and bound, local search, simulated annealing, ...). unifier does not implement those traits or route search through pathwise's generic algorithms. It ships its own CSP/COP-specialized solver stack: constraint propagation (full generalized arc consistency for AllDifferent via Régin's matching + SCC algorithm; bounds- /singleton-consistency plus energetic-reasoning overload detection and, for NoOverlap, edge-finding bound-tightening for the scheduling constraints; AC-3 otherwise), dom/wdeg and MRV/fail-first variable ordering, reversible (checkpoint/undo) domains instead of cloning per search node, and Branch & Bound with its own optimistic-bound pruning. What unifier does share with pathwise: two generic, CSP-independent portfolio-coordination primitives — a cancellation token and a shared incumbent for anytime/parallel search coordination (pathwise::core::cancellation, pathwise::core::incumbent) — used by unifier's solvers instead of duplicating that logic locally.

See plan/01-concept.md for the full architecture (4 layers: DSL, constraint model, solver engine, runtime) and the MVP scope for 0.1.

Installation

Not yet published to crates.io.

License

MIT — see LICENSE.