Solver-computed reference solutions: constraint solvers as ground truth

A frozen, solver-computed reference gives every score a fixed target. How to model a task, compute and freeze the reference, score against it, and where the method stops.

By Gabriel HöllerPublished 17 October 20269 min read

Drafted with AI tools, checked against the sources below, and reviewed by Gabriel Höller.

Key takeaways

A solver-computed reference solution is a known good answer, computed from a task's rules by a constraint solver and frozen, that agents' work is scored against.
A reference gives every task a fixed target, so a verifier can say how close an agent's valid answer comes to the cheapest one and scores stay comparable across seeds.
References should be computed once per seed with fixed solver settings and stored with their status, so scores never drift.
Solver-computed is not the same as proven optimal: a solver stopped by a time limit may only report a feasible solution, and the model encodes only the rules someone wrote down.

A solver-computed reference solution is a known good answer to a task, computed from the task's rules by a constraint solver and frozen, so every agent's work is scored against the same fixed target. It tells the verifier how good a valid answer is compared with the best one found, and proves optimality only when the solver says so.

This article explains what constraint solvers do, models a small scheduling task with CP-SAT, an open-source solver, and shows how to freeze references and score against them. It closes with what solver references do not prove and when not to use them. The series overview is RLVR, explained.

What does a constraint solver do?

A constraint solver is a program that searches a very large set of possible solutions for ones that satisfy every given constraint, and, if asked, for the best one under an objective such as cost. You describe the problem; the solver does the search.

Google's OR-Tools documentation describes constraint programming as identifying feasible solutions out of a very large set of candidates. Constraint programming is based on feasibility first: finding a solution that satisfies all constraints. An objective, such as minimising cost, can be added on top.

Scheduling is a typical use. The OR-Tools scheduling guide notes that organisations whose employees work shifts must schedule enough workers for each shift, under constraints such as no employee working two shifts in a row, and that finding a schedule that satisfies all constraints can be computationally difficult. Solver references are most useful for problems that are hard for people but small enough for the solver to solve to optimality. Instances that are hard for the solver too may only yield references with the status FEASIBLE.

What is CP-SAT?

CP-SAT is the primary constraint-programming solver in OR-Tools, Google's open-source software suite for optimisation. According to its documentation, it is designed for integer programming problems; the OR-Tools scheduling examples use it.

Three of its result statuses matter most for references:

OPTIMAL: an optimal feasible solution was found.
FEASIBLE: a feasible solution was found, but the solver does not know whether it is optimal.
UNKNOWN: no solution was found, and the problem was not proven infeasible, for example because a limit stopped the search first.

The solver can stop early because of a time limit or another limit set by the user. The OR-Tools guide on solver limits recommends setting a time limit when a program takes long to run. When that limit stops the search, the best solution found so far may be only feasible.

While it searches, the solver also keeps a bound: a proven limit on how good any solution can be. For a cost that is minimised, the bound says no valid solution can be cheaper; in the Python interface it is solver.best_objective_bound. The gap between the reference's cost and the bound shows how far from optimal a FEASIBLE reference can be at most.

How do you model a scheduling task?

Model a scheduling task as decision variables, constraints and an objective. The example below is a weekly rota for a small shop, kept small enough to read in one go. Its decision variable x[p, d, s] is 1 if person p works shift s on day d, and 0 otherwise.

Illustrative example. A shop is open seven days with an early and a late shift of six hours each. One person covers each shift, except Saturday morning, which needs two. Four staff have different hourly wages.

Each person works at most one shift a day and at most five a week. Nobody works a late shift followed by an early shift the next morning, which stands in for a minimum rest rule. Three staff are unavailable on one day each, and the objective is the lowest wage cost.

Each rule becomes one line of the model:

Rule	Constraint in the model
Every shift is covered	The number of people on each shift equals the demand
One shift a day	Early plus late is at most one, per person and day
Unavailable days	No shift on those days
Minimum rest	Late today plus early tomorrow is at most one
At most five shifts	The sum over the week is at most five, per person
Lowest cost	Minimise wage times hours over all assignments

Illustrative example. Simplified sketch. It runs with Python 3 after pip install ortools; it was tested with OR-Tools 9.12.

python

from ortools.sat.python import cp_model

staff = {"Ana": 16, "Ben": 14, "Cleo": 13, "Dev": 12}       # hourly wage
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
shifts = {"early": 6, "late": 6}                             # hours per shift
need = {(d, s): 2 if (d, s) == ("Sat", "early") else 1 for d in days for s in shifts}
away = {("Ben", "Tue"), ("Cleo", "Sat"), ("Dev", "Sun")}     # not available

m = cp_model.CpModel()
x = {(p, d, s): m.new_bool_var(f"{p}_{d}_{s}") for p in staff for d in days for s in shifts}
for (d, s), n in need.items():                               # cover opening hours
    m.add(sum(x[p, d, s] for p in staff) == n)
for p in staff:
    for i, d in enumerate(days):
        m.add(x[p, d, "early"] + x[p, d, "late"] <= 1)        # one shift a day
        if (p, d) in away:
            m.add(x[p, d, "early"] + x[p, d, "late"] == 0)
        if i + 1 < len(days):                                # minimum rest: no late, then early
            m.add(x[p, d, "late"] + x[p, days[i + 1], "early"] <= 1)
    m.add(sum(x[p, d, s] for d in days for s in shifts) <= 5)  # at most five shifts a week
m.minimize(sum(staff[p] * shifts[s] * x[p, d, s] for p in staff for d in days for s in shifts))

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10.0
solver.parameters.num_workers = 1                            # reproducible search
status = solver.solve(m)
print(solver.status_name(status), "cost", solver.objective_value)
for d in days:
    print(d, {s: [p for p in staff if solver.value(x[p, d, s])] for s in shifts})

Run as written, the solver reports OPTIMAL with a wage cost of 1,182 and prints the rota. If the example asked for two people on both Saturday shifts, the solver would report the model as infeasible, because one of the four staff is away on Saturday. The infeasible variant shows why the task generator must only produce tasks that can be solved.

How do you compute and freeze references per seed?

Compute the reference once for each seed, with fixed solver settings, and store it with everything needed to reproduce it. Never recompute it during training or evaluation.

Generate the task from its seed: staff, wages, availability and demand. How to build an RL environment covers task generation.
Solve with fixed settings: the same solver version, time limit and search settings for every seed. Limiting the search to one worker, as in the sketch, removes one source of run-to-run variation. A wall-clock time limit can still stop the search at different points on different machines; the CP-SAT parameter file also offers a limit in deterministic time (max_deterministic_time), which does not depend on the clock.
Store the reference: the seed, the objective value, the bound, the status, the solver name and version, the settings, the task generator version and the solution itself.
Freeze it: the stored reference becomes part of the environment version. Changing the model or the settings means a new version, with new references.

Frozen references give every score a fixed target, so results from different months stay comparable.

What gets stored with a reference?

Store enough to reproduce the reference and to explain any score computed from it. A stored reference for the shop example might look like this:

Illustrative example. A frozen reference record. The field names are an example, not a standard.

json

{
  "task_family": "weekly-rota",
  "seed": 104217,
  "status": "OPTIMAL",
  "objective": "wage_cost",
  "objective_value": 1182,
  "best_objective_bound": 1182,
  "solver": {"name": "CP-SAT", "version": "9.12", "max_time_in_seconds": 10, "num_workers": 1},
  "model_version": "rota-rules-3",
  "generator_version": "rota-gen-2",
  "solution_file": "refs/weekly-rota/104217.json",
  "solution_hash": "sha256:…"
}

The solution itself is stored in a separate file, and the hash identifies it. The status and bound fields are easy to forget and often needed: when someone later asks whether an agent "beat the optimum", they answer the question in one line.

How do you check a reference before freezing it?

Check every reference with code that does not share the solver's model, then freeze it. A reference is a target for thousands of scores, so an error in it spreads widely.

Verify the solution independently. Run the environment's own verifier on the solver's solution. It must pass every gate. If the solver's model and the verifier disagree about a rule, one of them is wrong.
Re-solve on a second machine with the same settings, for a sample of seeds, and confirm the same objective value and status.
Check infeasible and unknown seeds. The generator should not produce infeasible tasks, but if it does, the solver should say so, and the seed should be dropped. A seed whose status is UNKNOWN has no reference at all; drop it or solve it with a longer limit.
Look at the distribution of statuses and gaps. If many references are only FEASIBLE with a large gap to the bound, the tasks may be too large for the time limit, and their scores will be softer than they look.

How do you score against the reference?

Score in two stages: gates check that the agent's solution is valid, and only then is its quality compared with the reference. A gate is a check that sets the whole score to zero when it fails. Comparing an invalid roster with a reference makes no sense, however cheap it is.

For a cost objective, a simple quality score is the reference cost divided by the agent's cost, capped at 1.0. This ratio works only for a cost that is positive and minimised.

Illustrative example. Rosters for the shop example, scored against the reference of 1,182. All costs in the passing rows are possible under the model above; the failing row breaks the five-shift limit.

Agent's roster	Gates	Cost	Cost score
Matches the reference	Pass	1,182	1.00
Valid, slightly more expensive	Pass	1,230	0.96
The most expensive valid roster	Pass	1,284	0.92
Cheaper, but Dev works six shifts	Fail	1,170	not counted

The failing row is the reason gates come first. In this example, breaking the five-shift limit is a way to lower the cost below the reference, and without a gate the agent could learn exactly that.

The ratio has a weakness the table makes visible: even the most expensive valid roster still scores 0.92, so only 8% of the score separates the best valid roster from the worst. An agent earns almost everything just by being valid.

A normalised gap spreads the signal: (baseline − agent) / (baseline − reference), where the baseline is a known poor valid solution, such as a greedy roster or the worst one found. With the most expensive valid roster, 1,284, as the baseline, the roster costing 1,230 scores (1,284 − 1,230) / (1,284 − 1,182) ≈ 0.53 instead of 0.96. Scoring agent tasks shows how the cost score combines with other weighted scores.

Compare scores, not solutions. Many tasks have several solutions with the same optimal cost, and an agent that finds a different one deserves full marks.

What does a solver-computed reference not prove?

A solver-computed reference proves that the solution satisfies the model, and, if the status is OPTIMAL, that nothing in the model is cheaper. It does not prove more than that. Three limits matter.

A time limit may stop the proof. A reference with status FEASIBLE is a good solution, not necessarily the best one. An agent may find a cheaper valid solution; score it at full marks and flag it for review. Never describe a FEASIBLE reference as optimal.

The model is only as good as its rules. The solver optimises the rules someone wrote down. If a real rule is missing from the model, the reference may break it. A world should state which subset of real rules it models, and rules taken from law need care; Labour-law rules as code covers that.

The objective is a choice. Lowest cost is one objective among many. Fairness, preferences or stability may matter too, and they change which solution is best. Document the objective with the reference.

When should you not use a solver?

Use a solver only when the task has many valid answers of different quality and the rules can be encoded. Otherwise it adds complexity without adding information.

One correct answer. An invoice total or a tax code is either right or wrong; compare it with the generated data directly.
Rules that cannot be written down. If the constraints depend on judgement, the model would be guesswork.
Problems too large to solve in time. If most references end up FEASIBLE with a large gap to the solver's bound, they are weak targets. Shrink the tasks or use another method.
Subjective quality. If "better" means more pleasant or clearer, no objective function captures it.

For tasks with many valid answers and encodable rules, a frozen solver reference is one of the most reliable targets an environment can offer. Every Vencur world, a simulated workplace with its tasks and verifier, scores against frozen, solver-computed references; see Vencur Environments.

Frequently asked questions

What is a reference solution in an RL environment?

A reference solution is a known good answer to a task, used as the target when scoring. For tasks with many valid answers, such as rosters, the reference lets the verifier measure quality: an agent whose valid roster costs a little more than the reference earns slightly fewer points than one that matches it. Without a reference, the verifier can still measure cost, but it cannot say how close that cost is to the best achievable roster.

Why freeze reference solutions instead of computing them on the fly?

Reference solutions should be frozen because a reference computed again later can differ. A different solver version, time limit or search setting can return a different solution, and, when the search stops at a limit, a different objective value, so scores would drift for no reason the agent controls. Freezing the reference per seed, with its status and settings recorded, keeps every score comparable over time.

What happens if an agent beats the reference?

When an agent beats a reference that was proven optimal, something is wrong: a valid agent solution cannot be cheaper, so a cheaper valid solution points to a bug in the model or the verifier. If the reference was only feasible, because the solver stopped at a time limit, an agent can genuinely find a better solution. Score it at full marks, flag the episode for review and consider improving the reference.

Do I need a commercial solver for reference solutions?

A commercial solver is not necessarily needed for reference solutions. CP-SAT, the open-source solver in Google's OR-Tools, is designed for integer problems such as scheduling and assignment, and it reports whether a solution is proven optimal. Which solver fits best depends on the size and structure of your tasks; what matters most is that you record the solver, its version and its settings with every reference.

Sources

OR-Tools. Google, 2026.
Constraint Optimization. Google OR-Tools, 2026.
CP-SAT Solver. Google OR-Tools, 2024.
Setting solver limits. Google OR-Tools, 2024.
Employee Scheduling. Google OR-Tools, 2024.
sat_parameters.proto. Google OR-Tools (GitHub), 2026.

Need verified worlds for your agents?

Request a sample How Vencur checks every result

How we write: articles are researched and drafted with the help of AI tools, checked against the sources listed under each article, and reviewed and approved by Gabriel Höller before publication. Examples marked 'Illustrative example' are made up to explain an idea.