Improving Natural-Language Combinatorial-Optimization Accuracy in Resource-Constrained Language Models via Formal Abstractions
arXiv:2608.184092026-08-20
A small language for scheduling problems lets weaker AI models write feasible schedules instead of broken code
Small, resource-limited language models often produce schedules that sound right but violate real constraints when asked to solve scheduling problems in plain language. The authors built SDDL, a narrow mini-language that only lets a model name scheduling elements like tasks, resources, and precedence rules, while a separate deterministic program converts that into a formal math problem for an external solver. On a 300-instance benchmark spanning job-shop and project scheduling problems, models using SDDL produced valid schedules far more often than when generating direct answers or generic solver code.
What they did
- Problem: small language models used in resource-constrained settings often generate fluent-looking schedules from natural-language descriptions that secretly break hard constraints like machine overlaps or task ordering.
- Approach: SDDL gives the model only 7 fixed building blocks (tasks, resources, precedence, conflicts, etc.) instead of letting it write arbitrary solver code; a deterministic compiler then turns these into constraints for the CP-SAT solver, so the model never has to invent variables or write executable code.
- Result: Qwen3.5-27B improved from 23.7% feasible schedules (direct generation) and 21.7% (generic solver-code) to 55.3% with SDDL; Devstral-Small-2-24B improved from 1.3% and 7.0% respectively to 28.3% with SDDL, with schedules that were also nearly optimal when feasible.
- Verification: every schedule was independently checked against the original problem's real constraints, not just trusted based on whether the solver claimed success, and improvements held up under statistical significance testing.
- Scope: the method was tested on job-shop and project scheduling problem types and works because it narrows what the model has to express, moving error-prone decisions like variable definitions into a fixed compiler.
Table 1: Per-model results on SCHEDBench subset, ‡ marks new results. Brackets list 95% Wilson CIs on feasibility. Bold figures follow model feasibility through all three conditions, direct → solver-mediated → SDDL, with blue for qwen3.5-27b, orange for devstral-small-2-24b. †Evaluated with SDDL, not a new model. | Solver-Mediated Generation | Direct Generation | |
|---|
| Model | N | Feas. (%) | 95% CI (%) | R. fail (%) | Med. gap (%) | N | Feas. (%) | 95% CI (%) | Med. gap (%) | Δ Feas. |
| claude-opus-4-6 | 300 | 56.7‡ | [51.0, 62.2] | 21.0 | 0.0 | 300 | 4.7 | [2.8, 7.7] | 18.3 | +52.0 |
| qwen3.5-27b + SDDL† | 300 | 55.3‡ | [49.7, 60.9] | 16.0 | 0.0 | 300 | 23.7 | [19.2, 28.8] | 395.8 | +31.7 |
| gpt-5.5 (2026-04-23) | 300 | 53.3‡ | [47.7, 58.9] | 5.0 | 0.0 | 300 | 57.0 | [51.3, 62.5] | 36.7 | −3.7 |
| gpt-5.4 (2026-03-05) | 300 | 51.7 | [46.0, 57.3] | 18.3 | 0.0 | 300 | 0.3 | [0.1, 1.9] | 16.7 | +51.3 |
| gpt-5.4-mini (2026-03-17) | 300 | 36.7 | [31.4, 42.3] | 32.3 | 7.5 | 300 | 0.7 | [0.2, 2.4] | 131.8 | +36.0 |
| claude-sonnet-4-6 | 300 | 35.0‡ | [29.8, 40.6] | 24.3 | 0.0 | 300 | 8.3 | [5.7, 12.0] | 19.5 | +26.7 |
| qwen/qwen3.5-397b (2026-02-16) | 300 | 33.3 | [28.2, 38.8] | 12.3 | 0.0 | 300 | 19.3 | [15.3, 24.2] | 14.6 | +14.0 |
| devstral-small-2-24b + SDDL† | 300 | 28.3‡ | [23.5, 33.7] | 30.0 | 0.0 | 300 | 1.3‡ | [0.5, 3.4] | 111.2 | +27.0 |
| qwen/qwen3.5-122b (2026-02-24) | 300 | 23.3 | [18.9, 28.4] | 56.0 | 0.6 | 300 | 7.0 | [4.6, 10.5] | 7.1 | +16.3 |
| qwen/qwen3.5-27b (2026-02-24) | 300 | 21.7 | [17.4, 26.7] | 62.7 | 2.6 | 300 | 23.7 | [19.2, 28.8] | 395.8 | −2.0 |
| gemini-3.1-flash-lite | 300 | 17.0 | [13.2, 21.7] | 56.7 | 0.0 | 300 | 0.3 | [0.1, 1.9] | 107.1 | +16.7 |
| gemini-3-flash-preview | 300 | 12.0‡ | [8.8, 16.2] | 74.3 | 0.0 | 300 | 22.0 | [17.7, 27.0] | 24.5 | −10.0 |
| devstral-small-2-24b (2025-12-09) | 300 | 7.0‡ | [4.6, 10.5] | 66.7 | 0.0 | 300 | 1.3‡ | [0.5, 3.4] | 111.2 | +5.7 |
| claude-haiku-4-5 (2025-10-01) | 300 | 2.0 | [0.9, 4.3] | 37.0 | 0.0 | 300 | 1.0 | [0.3, 2.9] | 135.3 | +1.0 |
| meta-llama-4-maverick-17bX123e | 300 | 1.0 | [0.3, 2.9] | 92.0 | 0.0 | 300 | 0.3 | [0.1, 1.9] | 150.0 | +0.7 |
Table 2: The five registered penalty measures. Each is implemented once in the compiler and reused across programs; makespan is the only measure exercised by the evaluated families.| Measure | Archetype | Definition (minimized) |
|---|
| makespan | continuous | maxiendi over all scheduled tasks |
| capacity | discrete | total enrolment exceeding room capacity, summed over assignments |
| spread | discrete | shortfall below each task’s min_days distinct meeting days |
| isolated | discrete | count of meetings with no adjacent same-group meeting |
| room_stability | discrete | number of distinct rooms used by a task beyond the first |
Table 3: Evaluation-subset composition.| Family | Source suites | N |
|---|
| JSSP | Taillard, DMU, LA, ORB, ABZ, SWV | 100 |
| SM-RCPSP | PSPLIB J30–J120 | 100 |
| MM-RCPSP | PSPLIB MM J10–J30 | 100 |
Table 4: Inference, sandbox, and solver configuration.| Setting | Value |
|---|
| Resource-Constrained models | qwen3.5-27b (2026-02-24), devstral-small-2-24b (2025-12-09), qwen3-coder-30b-a3b (2025-07-31), magistral-small-24b (2025-09-17) |
| Reproduced | pinned versions of Table 1 (SCHEDBench) |
| Decoding | greedy (temperature 0), zero-shot, single pass, no tools |
| Max output tokens | 96,000 default; provider ceilings; token-terminated responses retained and scored |
| Sandbox | no network, fresh directory, 4 GB memory, 300 s wall-clock limit; CP-SAT budget fixed at 240 s in both solver-mediated conditions |
| Software | Python 3.11.2; OR-Tools 9.15.6755 (CP-SAT, default parameters except max_time_in_seconds) |
Table 5: Complete primitive and property reference. A well-formed task satisfies exactly one archetype rule: it is continuous iff it specifies duration or modes and no count, and discrete iff it specifies count; archetype assignment is therefore deterministic and complete, and a task specifying both (or neither) is rejected as malformed.| Primitive | Property | Value | Meaning / well-formedness |
|---|
| task(id, ...) | duration | int ≥0 | processing time; declares a continuous task |
| modes | list of maps | alternative execution modes, each a map with duration and optional demands/consumes; declares a continuous multi-mode task; mutually exclusive with a top-level duration |
| demands | map {rid: int} | renewable units held while active; keys must name declared resource() ids with capacity |
| consumes | map {rid: int} | nonrenewable units expended once; keys must name resources with total |
| machine | string rid | fixed disjunctive-resource assignment; pair with no_overlap(rid) |
| job, position | int, int | job index and 0-based operation index (job-shop bookkeeping used by the renderer) |
| label | string | verbatim display name from the problem text; consumed by the renderer/verifier, not the solver |
| count | int ≥1 | number of meetings; declares a discrete (timetabling) task |
| min_days, students | int | discrete-archetype spread/enrolment attributes |
| demand | int ≥1 | units required while assigned (discrete archetype: enrolment, checked against room capacity and scored by the capacity measure) |
| resource(id, ...) | capacity | int ≥1 | renewable per-time capacity ⇒ cumulative semantics; for the discrete archetype, a room’s seat capacity |
| total | int ≥1 | nonrenewable project-wide budget ⇒ linear budget semantics |
| (neither) | — | strictly disjunctive resource; meaningful with no_overlap |
| before(a, b) | — | task ids | hard finish-to-start precedence: enda≤startb; both ids must be declared |
| no_overlap(r) | — | resource id | at most one assigned task active on r at any time |
| conflict(...) | group | string (opt.) | listed tasks may not occupy the same time slot; group label also keys group-level objective terms (discrete archetype) |
| not_at(id, ...) | day, period | int | forbids execution at the given absolute time; on continuous tasks the forbidden times enter the horizon offset T (§3.7) |
| penalize(m, ...) | weight | int ≥1 | soft objective term; m must be a registered measure name (Table 2) |
Table 6: Statement-by-statement lowering into CP-SAT. Discrete-archetype tasks lower to day, period, and room integer variables with a channelled slot variable slot=day⋅NP+period.| SDDL construct | CP-SAT lowering |
|---|
| continuous task (fixed duration d) | si,ei∈[0,H] (NewIntVar); interval NewIntervalVar(si,d,ei) |
| continuous task with modes Mi | mode Booleans bim (NewBoolVar) with AddExactlyOne; duration variable di∈[minmdim,maxmdim] channelled by bim⇒di=dim (OnlyEnforceIf); a master interval on (si,di,ei) plus one NewOptionalFixedSizeIntervalVar(si,dim,bim) per mode |
| before(a, b) | model.Add(sb≥ea) |
| no_overlap(r) | AddNoOverlap over the intervals of tasks with machine =r |
| renewable resource (capacity=k) | AddCumulative(intervals, demands, k); multi-mode tasks contribute their per-mode optional intervals with mode-specific demands |
| nonrenewable resource (total=B) | linear budget ∑i∑mcimbim≤B (fixed-mode consumption enters as constants) |
| conflict(...) | AddAllDifferent over the members’ slot variables (discrete archetype) |
| discrete task (count c) | c meetings, each with day, period, and room integer variables and channelled slot =day⋅NP+period; room assignment respects seat capacity |
| not_at(id, day, period) | continuous tasks: reified exclusion ei≤t∨si>t per forbidden time t; discrete tasks: slot-exclusion constraints on the day/period variables, reified per meeting |
| penalize("makespan", w) | 𝑚𝑠∈[0,H] with AddMaxEquality(𝑚𝑠,{ei}); contributes w⋅𝑚𝑠 |
| objective | Minimize(∑penalty terms) |
Table 7: McNemar discordant counts (b: SDDL-only feasible; c: comparison-only feasible) and two-sided p-values for the within-model contrasts; all remain significant after Holm correction (padj<10−6).| Model | Contrast | b | c | p |
|---|
| qwen3.5-27b | SDDL vs. Direct | 100 | 5 | 5.0×10−24 |
| SDDL vs. Solver | 107 | 6 | 5.2×10−25 |
| devstral-small-2-24b | SDDL vs. Direct | 82 | 1 | 1.7×10−23 |
| SDDL vs. Solver | 67 | 3 | 9.7×10−17 |
| qwen3-coder-30b-a3b | SDDL vs. Direct | 70 | 1 | 6.1×10−20 |
| SDDL vs. Solver | 61 | 2 | 4.4×10−16 |
| magistral-small-24b | SDDL vs. Direct | 41 | 0 | 9.1×10−13 |
| SDDL vs. Solver | 42 | 5 | 2.5×10−8 |
Table 8: Resource-constrained models across all three conditions, direct → solver-mediated → SDDL, in the format of Table 1. Brackets list 95% Wilson CIs on feasibility. Color follows one model across rows, with blue for qwen3.5-27b, orange for devstral-small-2-24b, green for qwen3-coder-30b-a3b, purple for magistral-small-24b. | Solver-Mediated Generation | Direct Generation | |
|---|
| Model | N | Feas. (%) | 95% CI (%) | R. fail (%) | Med. gap (%) | N | Feas. (%) | 95% CI (%) | Med. gap (%) | Δ Feas. |
| qwen3.5-27b + SDDL | 300 | 55.3 | [49.7, 60.9] | 16.0 | 0.0 | 300 | 23.7 | [19.2, 28.8] | 395.8 | +31.7 |
| devstral-small-2-24b + SDDL | 300 | 28.3 | [23.5, 33.7] | 30.0 | 0.0 | 300 | 1.3 | [0.5, 3.4] | 111.2 | +27.0 |
| qwen3-coder-30b-a3b + SDDL | 300 | 23.3 | [18.9, 28.4] | 28.7 | 0.0 | 300 | 0.3 | [0.1, 1.9] | 357.1 | +23.0 |
| qwen/qwen3.5-27b (2026-02-24) | 300 | 21.7 | [17.4, 26.7] | 62.7 | 2.6 | 300 | 23.7 | [19.2, 28.8] | 395.8 | −2.0 |
| magistral-small-24b + SDDL | 300 | 15.0 | [11.4, 19.5] | 47.3 | 0.0 | 300 | 1.3 | [0.5, 3.4] | 159.9 | +13.7 |
| devstral-small-2-24b (2025-12-09) | 300 | 7.0 | [4.6, 10.5] | 66.7 | 0.0 | 300 | 1.3 | [0.5, 3.4] | 111.2 | +5.7 |
| qwen3-coder-30b-a3b (2025-07-31) | 300 | 3.7 | [2.1, 6.4] | 74.3 | 0.0 | 300 | 0.3 | [0.1, 1.9] | 357.1 | +3.3 |
| magistral-small-24b (2025-09-17) | 300 | 2.7 | [1.4, 5.2] | 88.0 | 0.0 | 300 | 1.3 | [0.5, 3.4] | 159.9 | +1.3 |
Table 9: qwen3.5-27b by family and condition (N=300 convention; run-fail includes instances without a completed generation).| Cond. | Family | N | Feas. (%) | R. fail (%) | Med. gap (%) |
|---|
| SDDL | JSSP | 100 | 96.0 | 3.0 | 0.0 |
| SDDL | SM-RCPSP | 100 | 17.0 | 44.0 | 0.0 |
| SDDL | MM-RCPSP | 100 | 53.0 | 1.0 | 0.0 |
| Solver | JSSP | 100 | 53.0 | 40.0 | 5.4 |
| Solver | SM-RCPSP | 100 | 7.0 | 68.0 | 0.0 |
| Solver | MM-RCPSP | 100 | 5.0 | 80.0 | 0.0 |
| Direct | JSSP | 100 | 52.0 | 0.0 | 697.4 |
| Direct | SM-RCPSP | 100 | 4.0 | 0.0 | 0.0 |
| Direct | MM-RCPSP | 100 | 15.0 | 0.0 | 0.0 |
Table 10: Hand-coded causes over a stratified sample of SDDL failures (one primary code per instance).| Failure code | qwen3.5 | devstral | q3-coder | magistral | Total |
|---|
| Dropped / garbled precedence edges (tasks complete) | 6 | 4 | 4 | 5 | 19 |
| Referenced-but-undeclared real activity | 1 | 2 | 0 | 3 | 6 |
| Phantom identifier (no problem counterpart) | 1 | 1 | 0 | 0 | 2 |
| Duplicate task declarations | 0 | 1 | 1 | 0 | 2 |
| Coverage collapse / label mismatch | 0 | 1 | 2 | 0 | 3 |
| Primitive-argument misuse | 0 | 0 | 1 | 0 | 1 |
| Emission derailment (prose drift, repetition, syntax slip) | 2 | 0 | 0 | 1 | 3 |
| Coded / sampled | 10/10 | 9/10 | 8/10 | 9/10 | 36/40 |
Why it matters
Many real-world scheduling tasks (staff rosters, factory operations, project planning) are described in plain language, but running large frontier AI models for every such request is often too costly or impractical. This work shows that giving smaller, cheaper models a narrow, purpose-built format to express the problem structure—rather than asking them to solve or code the whole thing themselves—can make them dramatically more reliable without needing a bigger model.
Terms in this paper
- CP-SAT · a constraint-solving engine from Google OR-Tools that finds feasible or optimal solutions to combinatorial problems
- feasibility · whether a produced schedule actually satisfies all the required real-world constraints
- neuro-symbolic framework · a system combining a language model with a separate rule-based or mathematical component that does the actual computation
- domain-specific language (DSL) · a small, purpose-built language, here restricted to scheduling concepts only
- optimality gap · how far a found solution is from the best possible solution
Original abstract (English)
Combinatorial scheduling poses a significant challenge for language models, requiring them to identify feasible solutions within exponentially large search spaces while satisfying complex constraints. This challenge is especially pronounced in resource-constrained settings, where larger language models are impractical and selection is limited to smaller models which often fail to preserve feasibility when scheduling directly from natural language.
Authors · Shrenil Shaun Sharma, Avi Sharma
Read on arXiv
