Everything K-culture — comebacks to K-beauty, straight to your inboxGet it in your inbox›
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.
METAL MEDIA explanatory visual
A small language for scheduling problems lets weaker AI models write feasible schedules instead of broken code
01Problem: 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.
02Approach: 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.
03Result: 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.
04Verification: 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.
05Scope: 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.
An explanatory diagram made by METAL MEDIA, not a figure supplied by the paper's authors.
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.
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.
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).
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. To address these limitations, we introduce SDDL, a neuro-symbolic framework that translates natural-language scheduling problems into compact, solver-aligned representations of tasks, resources, constraints, and objectives, while delegating low-level modeling and search to a deterministic compiler and external solver. On a 300-instance, multi-family subset of scheduling problems, SDDL improves independently verified feasibility for every resource-constrained model tested. The two strongest SDDL configurations reach 55.3% and 28.3%, up from direct-generation baselines of 23.7% and 1.3% and solver-code baselines of 21.7% and 7.0%, with a 0.0% median optimality gap among feasible schedules. By expressing problem structure rather than generating solutions or solver code, SDDL enables smaller models to approach the strongest evaluated direct- and solver-code configurations, including substantially larger frontier models.
