Why Constraint Solvers Run Alongside LLMs

The Problem

LLMs are good at understanding context and generating solutions that sound reasonable. "Reasonable" is not the same as "feasible."

Resource constraints, scheduling conflicts, capacity limits, regulatory boundaries — these are not approximation problems. They are satisfaction problems. A commitment that violates a hard constraint is not a commitment; it is a promise that cannot be kept. And a promise that cannot be kept is worse than no promise at all, because it consumes resources, creates dependencies, and damages trust before the failure becomes visible.

LLMs hallucinate feasible-sounding but infeasible solutions. Not because they are defective — because they are probabilistic. They generate outputs that are statistically consistent with their training, not outputs that are logically consistent with the constraints of your specific resource allocation problem. Constraint solvers do not hallucinate. They either find a solution that satisfies all constraints, or they prove that no such solution exists and return an infeasibility report.

The architectural question is not "LLM or constraint solver?" The question is "which tool for which step?" LLMs understand context and generate problem formulations. Constraint solvers find exact solutions within those formulations. Using only one of them produces a system that is either brittle (constraint solver without context) or unreliable (LLM without hard constraint enforcement).

Current Options

LLM-Only

The LLM generates solutions directly, including resource allocation and scheduling. No formal constraint verification.

+ Fast to build — no constraint model required

+ Flexible — handles novel situations without schema updates

+ Natural language interface to complex problems

− Hallucinated feasibility — solutions may violate hard constraints

− No infeasibility proof — cannot determine if a constraint is structurally impossible

− Non-reproducible — same inputs may produce different resource allocations

− No audit trail for constraint verification

− Regulatory compliance not tractable

Rule-Based Systems

Handwritten business rules encode constraints explicitly. No LLM involved. Deterministic by construction.

+ Deterministic — same inputs produce same outputs

+ Auditable — every constraint is explicit in the rule set

+ No hallucination — rules are exact

+ Provably correct within the scope of the rule set

− Rigid — novel situations not covered by existing rules produce incorrect or no output

− No context understanding — cannot reason about unstated trade-offs

− Maintenance burden — rules must be updated as constraints evolve

− Does not scale to complex combinatorial problems without becoming intractable

Constraint Solver + LLM Hybrid

LLM understands context and generates the problem formulation. Constraint solver finds the exact feasible solution within that formulation.

+ LLM handles context; solver handles constraints — each does what it is good at

+ Exact feasibility: solver either finds a solution or proves none exists

+ Infeasibility reports are explicit and actionable — not "this seems difficult"

+ Reproducible: same constraint formulation produces same solution

+ Context-aware: LLM can adapt the formulation to novel situations

− Requires explicit constraint modeling — upfront investment in the constraint schema

− LLM must produce a well-formed problem formulation — adds a validation step

− Solver performance can degrade on large problem spaces without careful modeling

Why OR-Tools / Constraint Programming

+ Exact feasibility

A constraint solver either finds a solution that satisfies all constraints or proves that no such solution exists. There is no "probably feasible" or "seems reasonable." The answer is exact.

+ Infeasibility proof

When no solution exists, the solver returns an infeasibility report that identifies which constraints cannot simultaneously be satisfied. This is actionable information — not a failure, but a diagnosis.

+ Reproducibility

The same constraint formulation produces the same solution on every run. This is a requirement for commitment systems: a commitment formed from a resource allocation must be traceable to the specific constraint satisfaction that justified it.

+ No hallucination on hard constraints

A solver does not generate solutions that violate constraints and then explain them away. If a solution violates a constraint, it is not returned. The constraint is not approximate.

Trade-offs

− Requires explicit constraint modeling

Constraints must be formalized. This is an upfront investment — the constraint model must be designed, validated, and maintained as constraints evolve. It cannot be approximated at runtime.

− No context understanding without the LLM layer

A constraint solver operates on a formal problem formulation. It does not understand the organizational context that produced that formulation. The LLM layer provides this context; without it, the solver is a powerful tool without a problem to solve.

− Performance on large problem spaces

Some constraint satisfaction problems are NP-hard. Large problem spaces can make the solver slow or intractable without careful problem decomposition and modeling. Well-scoped commitment problems rarely hit these limits.

Our Motivation

In the commitment infrastructure, constraint solvers act as the feasibility gate on every commitment that involves resource allocation, scheduling, or hard regulatory limits.

The flow is: 1. The coordination layer (LLM) synthesizes context and generates a `CommitmentProposal` — a structured description of what the organization is trying to commit to, including resource requirements and dependencies. 2. The commitment layer passes the `CommitmentProposal` to the constraint solver with the current resource state. 3. The solver returns a `ConstraintVerificationResult`: either `Feasible` (with the specific allocation that satisfies all constraints) or `Infeasible` (with the infeasibility report identifying which constraints cannot be satisfied). 4. A `CommitmentEvent` can only be formed if the `ConstraintVerificationResult` is `Feasible`. An infeasible proposal cannot become a commitment by construction.

The constraint solver is not a validation step added on top of an LLM decision. It is a gate that determines whether the proposed commitment is achievable given the organization's actual resource state and constraints. The LLM understands what the organization is trying to commit to. The solver determines whether that commitment is achievable.

In Practice

constraint_check.py

from ortools.sat.python import cp_model

def verify_resource_commitment(proposal: CommitmentProposal, state: ResourceState) -> ConstraintResult:
    """
    Verify that a commitment proposal is feasible given current resource state.
    Returns Feasible with allocation, or Infeasible with diagnosis.
    """
    model = cp_model.CpModel()

    # Decision variables: how much of each resource does this commitment consume?
    allocations = {
        resource_id: model.new_int_var(0, capacity, f"alloc_{resource_id}")
        for resource_id, capacity in state.available_capacity.items()
    }

    # Hard constraint: total allocation across existing commitments + this proposal
    # must not exceed capacity for any resource
    for resource_id, capacity in state.available_capacity.items():
        existing_load = state.committed_load.get(resource_id, 0)
        required = proposal.resource_requirements.get(resource_id, 0)
        model.add(allocations[resource_id] == required)
        model.add(existing_load + allocations[resource_id] <= capacity)

    # Hard constraint: dependencies must be scheduled before this commitment
    for dep_ref in proposal.dependencies:
        dep_end = state.get_commitment_end_time(dep_ref)
        if dep_end is None:
            return ConstraintResult.infeasible(
                reason=f"Dependency {dep_ref} is not yet committed or scheduled"
            )
        model.add(proposal.earliest_start >= dep_end)

    # Solve
    solver = cp_model.CpSolver()
    status = solver.solve(model)

    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        allocation = {rid: solver.value(var) for rid, var in allocations.items()}
        return ConstraintResult.feasible(allocation=allocation)
    else:
        # Diagnose which constraints are causing infeasibility
        return ConstraintResult.infeasible(
            reason=diagnose_infeasibility(model, proposal, state)
        )

The constraint model is explicit and complete. Every hard constraint is encoded. The solver either returns a valid allocation or an infeasibility report. There is no middle state — no "this might work" or "try adjusting the requirements." The result is binary and exact.

commitment_gate.rs

/// The commitment gate: a commitment can only be formed if constraint verification
/// returns Feasible. This is enforced by the type system — CommitmentEvent requires
/// a ConstraintVerificationResult, and form_commitment checks it is Feasible.
pub enum ConstraintVerificationResult {
    Feasible {
        allocation: ResourceAllocation,
        verified_at: DateTime<Utc>,
    },
    Infeasible {
        report: InfeasibilityReport,
    },
}

impl ConstraintVerificationResult {
    pub fn is_feasible(&self) -> bool {
        matches!(self, Self::Feasible { .. })
    }

    pub fn infeasibility_report(&self) -> Option<&InfeasibilityReport> {
        match self {
            Self::Infeasible { report } => Some(report),
            Self::Feasible { .. } => None,
        }
    }
}

/// An infeasibility report: what constraints cannot be satisfied, and why.
/// Returned to the coordination layer so the next coordination cycle
/// can reformulate the proposal with different parameters.
#[derive(Debug, Serialize)]
pub struct InfeasibilityReport {
    pub violated_constraints: Vec<ConstraintViolation>,
    pub diagnosis: String,
    pub suggested_reformulations: Vec<String>,
}

The Rust type system enforces the gate. ConstraintVerificationResult is an enum — Feasible or Infeasible. form_commitment checks is_feasible() and returns Err if the result is Infeasible. There is no way to form a CommitmentEvent from an infeasible proposal without changing the type — which means changing the code and being reviewed.

Looking Forward

Constraint programming as a component in LLM-augmented systems will become standard as the cost of hallucinated feasibility becomes visible in production. The pattern is already established in operations research and logistics; what is new is the integration with LLMs as the context-understanding layer.

The tooling is maturing. OR-Tools (Google) provides a mature, production-grade constraint solver with Python and C++ bindings. The integration surface with LLM coordination layers is well-defined: the LLM produces a structured problem formulation; the solver consumes it and returns a solution or an infeasibility report.

As constraint modeling libraries mature and LLMs become better at generating valid constraint formulations, the integration overhead will decrease. The fundamental architecture — LLM for context, solver for constraints — will not change, because it reflects a real distinction in what these tools are and what they can guarantee.

Recommendation

Use constraint solvers as the feasibility gate on every commitment that involves resource allocation, scheduling, or hard regulatory limits. OR-Tools is the practical choice: mature, production-grade, Python and C++ bindings, maintained by Google.

Use LLMs to understand what the organization is trying to commit to. Use constraint solvers to determine if that commitment is achievable given the organization's actual resource state and constraints. Do not ask the LLM to verify feasibility — it will approximate. Do not ask the solver to understand organizational context — it will produce a technically correct answer to the wrong problem.

The integration pattern is: LLM produces a structured `CommitmentProposal`; solver returns `Feasible` or `Infeasible`; the commitment layer gates on this result. An infeasible proposal returns to the coordination layer with the infeasibility report as context for the next coordination cycle.