Improving Natural-Language Combinatorial-Optimization Accuracy in Resource-Constrained Language Models via Formal Abstractions

# Improving Natural-Language Combinatorial-Optimization Accuracy in Resource-Constrained Language Models via Formal Abstractions
Source: [https://arxiv.org/html/2608.18409](https://arxiv.org/html/2608.18409)
Shrenil Shaun SharmaAffiliation:Independent ResearcherAffiliation:San Francisco, CA, USAEmail:[shrenil19\+research@gmail\.com](mailto:)Avi SharmaAffiliation:Department of ElectricalAffiliation:Engineering and Computer SciencesAffiliation:University of California, BerkeleyEmail:[avi\_sharma@berkeley\.edu](mailto:)

###### Abstract

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\.

## 1Introduction

Many requests posed to modern language models arrive in ordinary language, including problems whose solutions depend on an underlying mathematical structure\. In such cases, constraints, objectives, and procedures may be specified only implicitly, requiring the model to infer the mathematical problem being described\. For tasks that instantiate optimization problems, this inference is not merely semantic: the model must translate a verbal description into a latent search space of possible solutions and evaluate candidates against implicit feasibility and optimality criteria\. This challenge is especially pronounced in resource\-constrained settings, where model selection is limited to language models with substantially fewer parameters than larger available alternatives\. Generating a solution requires parsing the task description, tracking interacting constraints, reasoning about objectives, and implicitly searching over alternatives within a single autoregressive pass\. For smaller models, this process often yields fluent but infeasible solutions\.

Neuro\-symbolic decomposition may mitigate this limitation by separating language understanding from downstream computation: the language model produces an executable or formal representation, and an external runtime or solver performs the corresponding computation\([5](https://arxiv.org/html/2608.18409#bib.bib1);[13](https://arxiv.org/html/2608.18409#bib.bib4)\)\. In optimization\-specific systems, this formalization may include decision variables, constraints, and objectives\([14](https://arxiv.org/html/2608.18409#bib.bib5);[3](https://arxiv.org/html/2608.18409#bib.bib6);[16](https://arxiv.org/html/2608.18409#bib.bib8)\)\. This approach, however, shifts the bottleneck to translation fidelity\. A solver optimizes only the formalization it receives, so omitted constraints, misdefined variables, or distorted objectives directly undermine the resulting solution\. Combinatorial optimization problems expose this weakness particularly well, where unlike small decision problems or clue\-based logic puzzles, instances must represent objectives, resource capacities, temporal relations, precedence constraints, and disjunctive alternatives at scale\. We find that direct solver\-code generation by resource\-constrained models often fails as a formalization strategy, producing programs that may be executable and solver\-feasible yet unfaithful to the intended problem\. To bridge this gap, we introduceSDDL \(Scheduling Domain Definition Language\), a domain\-specific language that narrows the translation target from open\-ended solver code to a small set of solver\-aligned scheduling primitives\. Rather than requiring models to emit low\-level solver code, SDDL provides scheduling\-native abstractions for tasks, resources, constraints, alternatives, and objectives, where SDDL programs are deterministically compiled into a solver model for execution by an external solver\. Across 13 models we compare direct and generic solver\-code generation, and evaluateSDDLacross multiple resource\-constrained models\. SDDL improves independently verified feasibility for every model tested with it, while reducing the median optimality gap among feasible schedules\. Its strongest result ranks among the strongest configurations evaluated overall, while others improve to several times their baselines, demonstrating the effectiveness of SDDL relative to direct and generic solver\-code generation, and enabling smaller models to match stronger configurations\. Our contributions are:

1. 1\.SDDL \(Scheduling Domain Definition Language\)a domain\-specific language for executable, objective\-bearing combinatorial scheduling formulations that improves the fidelity of resource\-constrained LLM formalization relative to direct solver\-code generation\.
2. 2\.An independently verified evaluation ofSDDLagainst generation strategies matched in conceptual scope and solver target\.
3. 3\.An evaluation showing SDDL enables substantially smaller models to matchor closely approach the performance of the strongest direct\- and solver\-code configurations evaluated, including those using substantially larger frontier models\.

## 2Related Work

### 2\.1Structured Formal Reasoning

Empirical evaluations such as PlanBench document substantial weaknesses in systematic, multi\-step planning\([18](https://arxiv.org/html/2608.18409#bib.bib17)\), while[9](https://arxiv.org/html/2608.18409#bib.bib18)argue that LLMs are better incorporated into frameworks that delegate planning to external modules\. Performance on constrained\-generation tasks also varies substantially across model scales, with smaller, resource\-constrained models achieving lower constraint\-satisfaction rates than larger models, including under zero\-shot prompting\([19](https://arxiv.org/html/2608.18409#bib.bib19)\)\. This gap may be compounded by restrictive output\-format requirements, which have been shown to degrade performance on reasoning\-heavy tasks\([17](https://arxiv.org/html/2608.18409#bib.bib16)\)\. One such formulation arises in combinatorial scheduling problems, where models must simultaneously recover problem semantics, respect representational conventions, and maintain constraint fidelity across interdependent decisions and temporal relations\. Together, these findings suggest that preserving reasoning capacity during inference may depend on reducing what the model must formalize and compute, motivating approaches that delegate execution to external tools\.

### 2\.2Solver\-Delegated Constraint Reasoning

Neuro\-symbolic frameworks leverage LLMs to parse unstructured text into executable representations, delegating computation to external runtimes to bypass internal arithmetic and logical errors\([5](https://arxiv.org/html/2608.18409#bib.bib1);[4](https://arxiv.org/html/2608.18409#bib.bib3)\)\. Logic\-LM extends this approach to symbolic inference, translating natural\-language problems into formal logic and using solver feedback to iteratively repair invalid representations\([13](https://arxiv.org/html/2608.18409#bib.bib4)\)\. These results indicate that LLMs can benefit from constructing executable or symbolic representations while delegating deterministic computation and inference to external tools\. NL4Opt\([14](https://arxiv.org/html/2608.18409#bib.bib5)\), OptiMUS\([3](https://arxiv.org/html/2608.18409#bib.bib6)\), and ConstraintLLM\([16](https://arxiv.org/html/2608.18409#bib.bib8)\)apply this paradigm to optimization and constraint programming at different levels of abstraction\. However, OptiMUS and ConstraintLLM target highly expressive, general\-purpose programming environments, where formalization can require verbose variable declarations, low\-level solver API calls, and, often, explicit control flow on top of translating the underlying problem semantics; generality that may come at the cost of reliable generation\.

### 2\.3Solver\-Free Generation and Decoding

Alternative approaches evaluate LLMs as direct end\-to\-end combinatorial solvers\([8](https://arxiv.org/html/2608.18409#bib.bib9)\)\. In such end\-to\-end generation contexts, evaluation shows that solution quality and feasibility degrade as instance size and structural complexity increase\([8](https://arxiv.org/html/2608.18409#bib.bib9)\)\. Separately, structured\-decoding approaches constrain the generation process itself: syntax\-aware parsing\([20](https://arxiv.org/html/2608.18409#bib.bib10)\)and grammar\-constrained decoding\([6](https://arxiv.org/html/2608.18409#bib.bib11)\)enforce structural validity at the token level\. However, hard formatting constraints can degrade underlying reasoning performance\([17](https://arxiv.org/html/2608.18409#bib.bib16)\), and a syntactically valid representation may still omit a critical constraint or transfer an incorrect value\. SDDL therefore rejects malformed programs at parse time and verifies emitted schedules against the source instance, ensuring syntactic validity alone is not treated as evidence of correctness\.

### 2\.4LLMs for Combinatorial Scheduling

While the paradigms detailed above address general constraint satisfaction, literature targeting scheduling\-native problem structure remains narrow and fragmented\. Existing scheduling applications mimic the solver\-free paradigm through supervised fine\-tuning for job\-shop domains\([2](https://arxiv.org/html/2608.18409#bib.bib12)\)\. Such approaches collapse problem interpretation and combinatorial search into a single generation step, making it difficult to attribute errors in an infeasible schedule to faulty constraint translation rather than search failure\. Conversely, general\-purpose CP systems relevant to scheduling\([12](https://arxiv.org/html/2608.18409#bib.bib7);[16](https://arxiv.org/html/2608.18409#bib.bib8)\)inherit the heavy formalization overhead of general solver APIs and are not designed to exploit the recurring structural patterns \(precedences, resource capacities, coverage requirements, penalized soft constraints\) that span scheduling families\. Closest to our setting, Logic\.py\([10](https://arxiv.org/html/2608.18409#bib.bib20)\)formalizes search\-based problems through a DSL for constraint solving and is evaluated primarily on logic\-grid puzzles\. Its evaluated system focuses on finding satisfying assignments, rather than optimizing objectives over feasible schedules\.

### 2\.5Natural\-Language Scheduling Benchmarks

Scheduling\-specific natural\-language benchmarks remain limited\. Starjob\([1](https://arxiv.org/html/2608.18409#bib.bib13)\)provides a large supervised corpus for end\-to\-end JSSP scheduling, but verbalizes its instances through fixed templates\. R\-ConstraintBench\([7](https://arxiv.org/html/2608.18409#bib.bib15)\)evaluates RCPSP feasibility under systematically varied constraints using similarly structured, field\-like descriptions\. NL⇒\\RightarrowSchedule\([11](https://arxiv.org/html/2608.18409#bib.bib14)\)offers fuller natural\-language descriptions through semi\-synthetic instances constructed from real\-world materials across four domains\. NLCO\([8](https://arxiv.org/html/2608.18409#bib.bib9)\)covers a broader range of combinatorial optimization families outside scheduling and only provides minimally verbalized instances\. As our evaluation emphasizes formalization, we prioritize using a benchmark with unambiguous descriptions and canonical source instances, enabling generated schedules to be verified directly against formal ground truth\. SCHEDBench\([15](https://arxiv.org/html/2608.18409#bib.bib2)\)provides the best guarantee for this requirement by construction, where each description is a controlled, constraint\-preserving verbalization of a canonical source instance drawn from established scheduling literature; providing a definitive formal ground truth and best\-known objective for verifying generated schedules\.

## 3Methods and DSL Creation

SDDL’s design is based on an observation that automated formalization tends to break not only in understanding the problem, but in the many decisions required to render that understanding effectively\([16](https://arxiv.org/html/2608.18409#bib.bib8)\)\. SDDL removes the failure\-prone modeling decisions otherwise left to the model by naming only recurring scheduling structures for the model to identify, while a deterministic compiler handles their downstream encoding\. We articulate first principles underlying this stance, then develop the interface that realizes them and the compilation guarantees it provides\.

JSSP instance, 10 jobs×\\times5 machinesRules \(excerpt\)\.Steps within an item follow the given order; a location processes at most one step at a time; non\-preemptive\.Setup\.10 scenes on 5 crew stations\. Each scene is an ordered sequence of steps; each step names a station and a duration\.Scene Franklinhas a 5\-step sequence\. Step 1 is at theNorth Sound Stagefor 12 hours; Step 2 is at theSecond Unit Screening Roomfor 94 hours…\[\+ 9 more scenes\]Response format:<ItemName\> step k: start=<int\>, one per line\.

Figure 1:Example scheduling problem rendered in natural\-language; model must recover the underlying structure and emit a start time per step\.### 3\.1Scheduling Problems

Scheduling problems require allocating activities to specific time and resource assignments to produce a feasible schedule that satisfies a set of constraints and optimizes an objective\. Although they vary widely in form, their constraint structures are drawn from a few recurring relations: precedence between activities, disjunctive resources that process one activity at a time, cumulative resources that admit concurrency within a capacity, and multiple possible execution modes for each activity\. Different problem families combine these differently: job\-shop scheduling \(JSSP\) chains operations by precedence over disjunctive machines, whereas resource\-constrained project scheduling \(RCPSP\) replaces machines with cumulative resources, and its multi\-mode extension adds mode selection under nonrenewable budgets; all NP\-hard, with makespan as the standard objective\. Instances are constraint\-dense \(ex\. Fig\.[1](https://arxiv.org/html/2608.18409#S3.F1)\), so a single omitted or misread relation silently changes the feasible region, making scheduling a natural and demanding target for studying faithful formalization of natural\-language problem statements\.

### 3\.2Design Principles

We optimize the language for three properties: robustness, ensuring the modeling surface admits few malformed programs; concision, allowing constraints to be expressed without solver\-specific machinery; and sufficient expressiveness for the intended problem families\. We further require bounded expressiveness: rather than exposing a general\-purpose language in which the model may introduce arbitrary variables or predicates, SDDL fixes a vocabulary of recurring scheduling constructs, precedence, disjunctive and cumulative resources, alternative execution modes, alongside supported objectives\. This helps reduce opportunities for formalization errors, where otherwise, each degree of freedom exposed to the model creates another opportunity for errors \(variable declarations, domain bounds, etc\.\) none of which specified by the original problem\. By fixing the vocabulary, SDDL transfers these decisions to the compiler, recasting the model’s role from synthesizing constraints to recognizing pre\-constrained scheduling constructs\. These properties stem from a deliberate design decision, as fixed grammatical primitives yield a closed surface language, parse\-time rejection, and verified compilation\. This also improves solver performance, as CP\-SAT’s global constraints such asNoOverlapandCumulative, propagate more strongly than equivalent Boolean decompositions\. A free\-form encoding may represent a cumulative resource correctly yet bury it in logic that the solver cannot recognize\. Because SDDL names these constructs directly, the compiler can consistently emit the strongest global encoding\. This bounded vocabulary both prevents formalization errors and preserves propagation strength\. The remaining principles then cover a closed surface that rejects malformed programs at parse time, hides solver implementation details, and provides complete coverage without leaving constructs implicit\.

### 3\.3Primitives

program:⁣:=statement∗statement:⁣:=task​\(id,props\)∣resource​\(id,props\)∣before​\(id,id\)∣no\_overlap​\(id\)∣conflict​\(ids,group=s\)∣not\_at​\(id,props\)∣penalize​\(m,weight=w,props\)props:⁣:=ϵ\|prop​\(,​prop\)∗ids:⁣:=id​\(,​id\)∗prop:⁣:=key​=​valuevalue:⁣:=scalar∣\[value,…\]∣\{value:value,…\}\\begin\{array\}\[\]\{r@\{\\;\}c@\{\\;\}l\}\\textit\{program\}&::=&\\textit\{statement\}^\{\*\}\\\\\[1\.0pt\] \\textit\{statement\}&::=&\\texttt\{task\}\(\\textit\{id\},\\textit\{props\}\)\\\\ &\\mid&\\texttt\{resource\}\(\\textit\{id\},\\textit\{props\}\)\\\\ &\\mid&\\texttt\{before\}\(\\textit\{id\},\\textit\{id\}\)\\\\ &\\mid&\\texttt\{no\\\_overlap\}\(\\textit\{id\}\)\\\\ &\\mid&\\texttt\{conflict\}\(\\textit\{ids\},\\texttt\{group\}\{=\}\\textit\{s\}\)\\\\ &\\mid&\\texttt\{not\\\_at\}\(\\textit\{id\},\\textit\{props\}\)\\\\ &\\mid&\\texttt\{penalize\}\(\\textit\{m\},\\texttt\{weight\}\{=\}\\textit\{w\},\\textit\{props\}\)\\\\\[1\.0pt\] \\textit\{props\}&::=&\\epsilon\\;\\mid\\;\\textit\{prop\}\\,\(\\texttt\{,\}\\,\\textit\{prop\}\)^\{\*\}\\\\ \\textit\{ids\}&::=&\\textit\{id\}\\,\(\\texttt\{,\}\\,\\textit\{id\}\)^\{\*\}\\\\ \\textit\{prop\}&::=&\\textit\{key\}\\,\\texttt\{=\}\\,\\textit\{value\}\\\\ \\textit\{value\}&::=&\\textit\{scalar\}\\mid\\ \\texttt\{\[\}\\,\\textit\{value\},\\dots\\,\\texttt\{\]\}\\mid\\ \\texttt\{\\lx@text@lbrace\}\\,\\textit\{value\}\\,\\texttt\{:\}\\,\\textit\{value\},\\dots\\,\\texttt\{\\lx@text@rbrace\}\\\\ \\end\{array\}Figure 2:The SDDL grammar:∗means “zero or more,”ϵ\\epsilonthe empty string, and∣\\midseparates alternatives\. The atoms areid, a quoted identifier;key, a property name;m, a penalty measure;w, an integer weight;s, a group name; andscalar, a number or string\.SDDL defines programs which consist of flat sequences of primitive scheduling constructs, with neither control flow, nor an expression language beyond literal values\. Literals include "lists" and "maps", so values such as themodeslist anddemandsandconsumesmaps are specified directly rather than constructed through code\. The complete grammar is shown in Fig\.[2](https://arxiv.org/html/2608.18409#S3.F2)above\.

Two of the seven primitives,taskandresource, declare problem objects; four express hard constraints whilepenalizedefines soft objectives\. Constraint hardness is encoded structurally through the choice of primitive: a clause is hard unless it appears as a penalty, so the model never signals status through weights or phrasing\. We selected the seven primitives to maximize coverage while minimizing the language surface, adding one only when existing constructs could not represent the required scheduling pattern\. Two design choices illustrate this principle: precedence, which is expressed by the binarybeforeprimitive, capturing the pairwise finish\-to\-start ordering commonly used in these problems, avoiding a general temporal operator that the compiler could not otherwise translate uniformly\. Second is shared\-membership constraints, such as those between courses in the same curriculum, which are expressed usingconflictwith an optionalgrouplabel\. The compiler uses this label both to prohibit concurrent assignments, and to identify group\-level objective terms\. The remaining hard\-constraint primitive,not\_at, forbids a task from executing during specified absolute times\.

task\(id,\*\*props\)resource\(id,\*\*props\)

before\(a,b\)no\_overlap\(r\)

conflict\(t1,\.\.\.,group=\)not\_at\(id,\*\*when\)

penalize\(measure,weight=w,\*\*params\)

As an illustration, the clause*“operation A runs on machinem0m\_\{0\}…”*formalizes to the below primitives,

task\("a",machine="m0",duration=3\)

task\("b",machine="m1",duration=2\)

before\("a","b"\)

whose lowering schedules the two tasks as intervals on their respective machines, then adds the single constraint𝑠𝑡𝑎𝑟𝑡b≥𝑒𝑛𝑑a\\mathit\{start\}\_\{b\}\\geq\\mathit\{end\}\_\{a\}; with the model stating the operations and ordering, while every solver variable is introduced by the compiler\.

### 3\.4Property Polymorphism

To cover varied task structures with a single declaration form, SDDL assignstaska property\-dependent representation, with each task’s form inferred directly from its properties by the compiler\. A task is*continuous*if it specifies a duration or modes and no counts\. Continuous tasks lower to start, end, and interval variables\. This is especially useful for multi\-mode activities, where the model supplies a list of duration\-and\-resource profiles while the compiler introduces the selection variables, optional intervals, and exactly\-one constraint needed to choose a single mode\. A second structure, discrete tasks declared by count, lowers to day\-period\-room variables for timetabling families; while specified and compiler\-verified, it currently lies outside our evaluated scope\. Because well\-formed tasks must satisfy exactly one rule, archetype assignment is therefore deterministic, and the model therefore transcribes properties from the problem statement rather than choosing an internal representation\. Property polymorphism therefore keeps the language compact while moving error\-prone encoding decisions into the compiler\.

### 3\.5Resource Semantics

Resource handling is where the language most clearly justifies its design as it makes explicit a distinction that natural\-language descriptions often obscure but solvers must encode differently\. A machine serving one job at a time is disjunctive, so assigned intervals cannot overlap\. A shared worker pool is cumulative, so tasks may overlap provided total demand does not exceed capacity\. Leaving this distinction implicit is a common source of modeling errors\. The DSL resolves this ambiguity at declaration time\. Renewable resources define a capacity referenced through a per\-taskdemandsmap; their units are occupied during execution and released at completion, so they compile to cumulative constraints\. Nonrenewable resources define a total and use aconsumesmap; their units are permanently expended, and compile to a project\-wide linear budget\. Disjunctive resources useno\_overlap\. The explicit structure determines the encoding:demandsindicates cumulative capacity,consumesindicates exhaustible supply, andno\_overlapindicates one\-at\-a\-time use\. The model need only classify the resource as capacity\-limited, exhaustible, or strictly disjunctive, and the compiler then generates the corresponding constraint and prevents encoding errors\. All 3 resource classes are exercised in our evaluation\.

### 3\.6Objectives

Where hard constraints determine feasibility,penalizeoptimizes quality within the feasible region\. Each penalty specifies a measure and weight; the compiler scales and sums the measures into a single minimized objective\. Measures are selected from a fixed set: completion time, over\-capacity, day spread, isolation, and room instability; rather than defined as free\-form cost functions\. This restriction provides the same safeguards as the closed constraint language\. Arbitrary objectives can be syntactically valid yet semantically incorrect because of counting errors or optimization in the wrong direction\. Named measures are implemented once by the compiler and reused consistently\. The model therefore expresses only the intended preference and its weight, while the compiler realizes the objective correctly\.

### 3\.7Compilation

Compilation is deterministic and requires no further model input\. Programs are parsed through the language’s abstract\-syntax machinery accepting only literals, so generated text is never executed, programs do not introduce side effects, and malformed inputs are rejected\. Correctness is defined by an abstract, solver\-independent semantics specifying schedules and objective values\. A schedule assigns start and end times to continuous tasks, including selected durations for multi\-mode tasks, and day\-period\-room tuples to discrete meetings\. Each statement defines a feasibility condition, whilepenalizedefines a weighted objective\. For example,before\(a,b\)requires \(a\) to end before \(b\) starts,no\_overlapforbids simultaneous resource use, and a renewableresourceof capacity \(k\) limits total active demand to \(k\)\. The compiler lowers each statement into solver variables, constraints, and an objective\. Correctness requires the compiled model to preserve both feasibility and objective values\. Direct primitives map immediately to solver constraints; cumulative resources, mode selection, and penalty measures involving reified constraints require additional equivalence arguments, provided in Appendix[A\.3](https://arxiv.org/html/2608.18409#A1.SS3)\. For continuous tasks, the inferred horizon is \(H=T\+∑imaxm∈Mi⁡di​mH=T\+\\sum\_\{i\}\\max\_\{m\\in M\_\{i\}\}d\_\{im\}\), where \(T\) is one plus the latest forbidden time and \(M\_i\) is task \(i\)’s set of modes\. Every feasible instance admits a serial schedule within this horizon; therefore, under the evaluated makespan objective, the horizon contains at least one optimal schedule\.

### 3\.8Guarantees and Robustness

A closed vocabulary and deterministic compiler provide two guarantees normally unavailable when each instance is independently translated into solver code: every well\-formed program compiles to a unique solver model without a new translation for each problem, and adequacy ensures that compilation preserves its meaning\. Any feasible solution can be read as a horizon\-bounded schedule satisfying the program, and every such schedule corresponds to a feasible solver solution with the same objective value\. As the reference semantics and compiled model are constructed statement by statement, adequacy can be proven for each statement independently\. For well\-formed programs, adequacy removes compiler lowering as a source of semantic discrepancy, leaving the model\-produced formalization as the remaining source of semantic error\. The failure surface is therefore minimized, with every reported schedule tested directly against the source instance by an independent verifier\. Extension beyond evaluated families requires no redesign of the language: discrete timetabling reuses the same declaration form through a second task archetype, and family\-specific objectives are added by registering named measures in the existing compiler\.

## 4Experimental Evaluation

We use publicly released benchmark instances, evaluation harness, and verifiers to evaluate SDDL\. We include previously reported DIRECT and SOLVER results from SCHEDBench, with newly generated results marked explicitly for contextual comparisons to characterize performance across model capabilities and generation modalities, while SDDL tests DSL\-assisted combinatorial optimization in resource\-constrained models\. All conditions use fixed, instance\-independent zero\-shot prompts, greedy decoding \(temperature 0\), and no worked examples\. Transient API failures are retried until generation completes, irrespective of solution quality\. DIRECT includes only task and format instructions\. SOLVER provides an OR\-Tools CP\-SAT guide covering equivalent scheduling concepts, conventions, and solver targets as SDDL; SDDL additionally includes its language specification due to its absence from pretraining corpora\. SOLVER and SDDL therefore share conceptual scope but differ in formalization interface: open\-ended solver code versus a closed language with deterministic compilation\. Appendix[B\.3](https://arxiv.org/html/2608.18409#A2.SS3)gives the full inference settings, sandbox configuration, and pinned software and OR\-Tools versions\.

### 4\.1SCHEDBench Evaluation Subset

We evaluate SDDL on the JSSP, single\-mode RCPSP, and multi\-mode RCPSP families of SCHEDBench, which dominate standard benchmarks and prior work on LLM scheduling\. These families exercise the precedence, disjunctive and cumulative resources, nonrenewable budgets, multi\-mode selection, and the objective channels of the DSL, and use a standardized makespan objectivepenalize, making optimality gap a clean measure of end\-to\-end feasibility; conflict, not\_at, and the discrete archetype are specified and compiler\-verified but left unexercised\. We exclude families scored through benchmark\-specific weighted soft violations, whose instance specific penalty terms could be supported by registering additional named measures in the existing compiler\.

### 4\.2Evaluation Scoring and Metric Definitions

Our primary metric is feasibility, where an emitted schedule must satisfy every hard constraint of the canonical source instance, as determined by an independent verifier\. The pipeline renders a schedule as a structured listing of integer start times, checked directly against the source instance rather than the solver’s reported status\. Violations are classified as precedence, machine\-overlap, or resource\-capacity errors\. For feasible schedules, the verifier recomputes the objective from the schedule itself, preventing an incorrectly encoded objective from inflating performance\. We then report the gap to the canonical optimum or best\-known solution; where*optimal*denotes a feasible schedule with a gap of at most \(10−910^\{\-9\}\)\. Gaps are summarized by the median over feasible runs\. Each run receives exactly 1 outcome:*feasible*,*infeasible*,*no\-solution*, or*run\-fail*\. Failures before verification, including unparseable DSL output, transpilation errors, rendering failures, solver\-reported infeasibility, and timeouts; are recorded as*no\-solution*or*run\-fail*\. Feasibility therefore evaluates the complete path from natural\-language input to verified schedule, not just the solver’s assessment of its own model\. We report 95% Wilson CIs for feasibility rates\. The DSL is parsed using a literal\-only parser, never executed directly\.

### 4\.3Constraint Solving via SAT\-Based Solvers

Constraint programming \(CP\) represents a combinatorial problem using finite\-domain decision variables and constraints over joint assignments\. Search is interleaved with propagation, which reduces variable domains until a solution is found, infeasibility is proved, or an objective bound is certified\. Modern SAT\-based solvers implement this through lazy clause generation: propagators express their inferences as clauses for a conflict\-driven SAT engine, combining CP propagation with SAT clause learning and linear relaxations for objective bounds\. We target CP\-SAT, the SAT\-based constraint solver in Google OR\-Tools\. For scheduling, it provides interval variables linking a task’s start, duration, and end, with global constraints such asNoOverlapfor disjunctive resources andCumulativefor shared\-capacity resources\. Their dedicated propagation methods, including overload checking, edge\-finding, and energetic reasoning, prune more effectively than pairwise Boolean decompositions\. CP\-SAT also supports reified linear constraints andAllDifferentfor assignment problems\. Given an integer objective, CP\-SAT proves optimality, returns the best solution found within the time limit, or proves infeasibility\. Our compiler targets this interface directly, so SDDL primitives map to the solver constructs with the strongest relevant propagation\.

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→\\rightarrowsolver\-mediated→\\rightarrowSDDL, withbluefor qwen3\.5\-27b,orangefor devstral\-small\-2\-24b\.†Evaluated with SDDL, not a new model\.

## 5Results and Discussion

We compare overall feasibility across direct natural\-language scheduling \(Direct\), solver\-assisted scheduling \(Solver\), and SDDL\-assisted configuration \(SDDL\) for 13 models on the same 300\-instance set\. The main table and discussion focus on the two strongest resource\-constrainedSDDLmodels, while Appendix C reports additionalSDDLresults for a broader set of resource\-constrained models, all of which show similar feasibility improvements\. Pairwise feasibility is tested using two\-sided McNemar tests on paired instance\-level outcomes, with Holm correction applied jointly across pairwise comparisons\. UnderDirect, GPT\-5\.5 obtains the highest feasibility at 57\.0%\. Solver\-assisted performance is strongly model\-dependent: 10 of 13 models improve and 3 decline, with changes ranging from−10\.0%\-10\.0\\%to\+52\.0%\+52\.0\\%points\. Against this baseline, Qwen 3\.5 27B withSDDLreaches 55\.3% feasibility, while Devstral Small 2 24B withSDDLreaches 28\.3% feasibility, both substantially improved over Direct\.

### 5\.1Effect on Resource\-Constrained Models

With SDDL, Qwen3\.5\-27B reaches 55\.3% feasibility, up significantly from 23\.7% underDirectgeneration, while Devstral\-Small\-2\-24B similarly improves from 1\.3% to 28\.3%\. For Qwen3\.5\-27B, genericSolverassistance yields only 21\.7% feasibility, slightly belowDirect, whereas SDDL delivers gains of 31\.7 and 33\.7 percentage points over the two conditions, respectively \(p<10−22p<10^\{\-22\}\)\.111SDDL discordant gains/losses: 100/5 and 107/6 \(Qwen vs\. DIRECT and SOLVER\); 82/1 and 67/3 \(Devstral\)\.As both solver\-mediated conditions share solver and conceptual scope, these results indicate that solver access alone is insufficient, and supports SDDL’s constrained formalization\-and\-compilation approach\. Run\-failure rate also falls from 62\.7% underSolverto 16\.0% withSDDL\(a 46\.7\-point reduction\), indicating that the feasibility gain coincides with a increase in solve reliability\. Devstral\-Small\-2\-24B benefits similarly fromSDDL, with feasibility reaching 28\.3%, vs\. 7\.0% with SOLVER and 1\.3% under DIRECT \(p<10−15p<10^\{\-15\}\), while run\-failure falls from 66\.7% to 30\.0%\.

### 5\.2Performance Positioning of SDDL

We position Qwen 3\.5 27B withSDDLagainst the strongest results in Table[1](https://arxiv.org/html/2608.18409#S4.T1)\. The highest direct result is 57\.0% feasibility on the 300 instance SCHEDBench subset, obtained by GPT\-5\.5, while the highest solver\-assisted result is 56\.7%, obtained by Claude Opus 4\.6\. Qwen 3\.5 27B with SDDL reaches 55\.3%, compared with the generic solver\-assisted results of GPT\-5\.5 \(53\.3%\) and GPT\-5\.4 \(51\.7%\), and within 1\.4 and 1\.7 points of the strongest solver\-assisted \(Claude Opus 4\.6, 56\.7%\) and direct \(GPT\-5\.5, 57\.0%\) configurations\. SDDL closes 94\.9% of Qwen’s deficit to GPT\-5\.5 underDirect\(33\.3→\\rightarrow1\.7 %\) and 96\.0% of its deficit to the strongest solver\-assisted configuration \(35\.0→\\rightarrow1\.4 %\)\. The resulting configuration ranks among the highest feasibility overall and exceeds every generic solver\-assisted configuration except Claude Opus 4\.6 without increasing the capacity of the 27B model\. These findings position our approach as a promising means of improving performance across resource\-constrained models; with potential applicability to other resource\-constrained settings\.

### 5\.3Optimality of Feasible Schedules

Feasibility establishes whether a schedule satisfies the problem’s constraints, but not its quality\. Thus, we report the median optimality gap among feasible outputs—the difference between a schedule’s objective value and the best\-known value for its instance, where 0\.0% indicates that the schedule matches the best\-known objective\. Across all four resource\-constrained models evaluated with SDDL, the median gap is 0\.0%, while feasibility ranges from 15\.0% to 55\.3%\. This represents broader feasible coverage than direct generation, whose median gaps range from 111\.2% to 395\.8%, and than generic solver\-code generation, which generally obtains low median gaps but solves considerably fewer instances\. Qwen3\.5\-27B with SDDL reaches 55\.3% feasibility with a 0\.0% median gap, compared with 23\.7% feasibility and a 395\.8% median gap underDirect, and 21\.7% feasibility and a 2\.6% median gap underSolver\. Since gaps are computed only over feasible outputs, the median for each condition may reflect a different subset of instances, and should be interpreted alongside feasibility\. Still, the consistent 0\.0% median gap across SDDL configurations indicates its advantage may extend to objective quality beyond validity\.

## 6Conclusion

We introduced SDDL, a scheduling\-specific language that lets models express problem structure through compact, solver\-aligned primitives while delegating low\-level modeling and search to a compiler and solver\. On 300 SCHEDBench instances spanning multiple scheduling families, SDDL substantially raises feasibility, showing that a DSL can serve as an intermediate representation enabling resource\-constrained models to match or close the deficit to the strongest evaluated configurations\.

## Limitations

We do not evaluate SDDL on frontier\-scale models, as our focus lies on seeking methods that improve performance for resource\-constrained applications where the use of frontier scale sized models may not be possible\. SDDL may also improve frontier models however is left as natural future work\. Although SDDL’s primitives are designed to cover a wide variety of scheduling problems, its generalization to combinatorial domains beyond scheduling remains empirically untested, and represents a natural direction for future work\. Our evaluation also only covers JSSP/SM\-RCPSP/MM\-RCPSP scheduling families, with discrete formulations and their respective measures specified, compiler\-verified, but with evaluation of their LLM\-translation left to future work\. Our evaluation measures single\-pass, zero\-shot formalization under greedy decoding\. We do not evaluate iterative repair or self\-correction which may recover execution failures at additional inference cost\. Because models are accessed via provider APIs, temperature\-0 decoding is not bitwise deterministic, and each instance is evaluated as a single draw with uncertainty quantified across instances rather than sampling seed\. Our use of resource\-constrained concerns only the parameter count of the language\-model component and does not imply lower end\-to\-end compute, latency, memory, or cost for the full solver\-assisted pipeline\.

Based on preliminary pilot experiments, we restrict our evaluation to models with approximately 20B or more parameters\. Models below this range produced substantially lower rates of valid formalizations \(feas\. < 5%\), making a full evaluation prohibitively uninformative under our fixed zero\-shot setting\. This threshold was selected empirically; therefore, our conclusions are limited to the evaluated model\-size range and should not be interpreted as establishing a general minimum model size for SDDL\.

## References

- H\. Abgaryan, T\. Cazenave, and A\. HarutyunyanStarjob: dataset for LLM\-driven job shop scheduling\.External Links:2503\.01877,[Link](https://arxiv.org/abs/2503.01877)Cited by:[§2\.5](https://arxiv.org/html/2608.18409#S2.SS5.p1.1)\.
- Abgaryanet al\.\(2024\)H\. Abgaryan, A\. Harutyunyan, and T\. CazenaveLLMs can schedule\.External Links:2408\.06993,[Link](https://arxiv.org/abs/2408.06993)Cited by:[§2\.4](https://arxiv.org/html/2608.18409#S2.SS4.p1.1)\.
- Ahmaditeshniziet al\.\(2024\)A\. Ahmaditeshnizi, W\. Gao, and M\. UdellOptiMUS: scalable optimization modeling with \(MI\)LP solvers and large language models\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 577–596\.External Links:[Link](https://proceedings.mlr.press/v235/ahmaditeshnizi24a.html)Cited by:[§1](https://arxiv.org/html/2608.18409#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.18409#S2.SS2.p1.1)\.
- Chenet al\.\(2023\)W\. Chen, X\. Ma, X\. Wang, and W\. W\. CohenProgram of thoughts prompting: disentangling computation from reasoning for numerical reasoning tasks\.Transactions on Machine Learning Research\.External Links:ISSN 2835\-8856,[Link](https://arxiv.org/pdf/2211.12588)Cited by:[§2\.2](https://arxiv.org/html/2608.18409#S2.SS2.p1.1)\.
- Gaoet al\.\(2023\)L\. Gao, A\. Madaan, S\. Zhou, U\. Alon, P\. Liu, Y\. Yang, J\. Callan, and G\. NeubigPAL: program\-aided language models\.InProceedings of the 40th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.202,pp\. 10764–10799\.External Links:[Link](https://proceedings.mlr.press/v202/gao23f.html)Cited by:[§1](https://arxiv.org/html/2608.18409#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.18409#S2.SS2.p1.1)\.
- Genget al\.\(2023\)S\. Geng, M\. Josifoski, M\. Peyrard, and R\. WestGrammar\-constrained decoding for structured NLP tasks without finetuning\.InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing,Singapore,pp\. 10932–10952\.External Links:[Document](https://dx.doi.org/10.18653/v1/2023.emnlp-main.674),[Link](https://aclanthology.org/2023.emnlp-main.674/)Cited by:[§2\.3](https://arxiv.org/html/2608.18409#S2.SS3.p1.1)\.
- Jain and Wetter \(2025\)R\. Jain and M\. WetterR\-ConstraintBench: evaluating LLMs on NP\-complete scheduling\.External Links:2508\.15204,[Link](https://arxiv.org/abs/2508.15204)Cited by:[§2\.5](https://arxiv.org/html/2608.18409#S2.SS5.p1.1)\.
- Jianget al\.\(2026\)X\. Jiang, J\. Chen, C\. Zhang, J\. Gao, C\. Hu, C\. Zhang, Y\. Wu, and Y\. ZhangReasoning in a combinatorial and constrained world: benchmarking LLMs on natural\-language combinatorial optimization\.InFindings of the Association for Computational Linguistics: ACL 2026,M\. Liakata, V\. P\. Moreira, J\. Zhang, and D\. Jurgens \(Eds\.\),San Diego, California, United States,pp\. 30592–30648\.External Links:[Link](https://aclanthology.org/2026.findings-acl.1529/),[Document](https://dx.doi.org/10.18653/v1/2026.findings-acl.1529),ISBN 979\-8\-89176\-395\-1Cited by:[§2\.3](https://arxiv.org/html/2608.18409#S2.SS3.p1.1),[§2\.5](https://arxiv.org/html/2608.18409#S2.SS5.p1.1)\.
- Kambhampatiet al\.\(2024\)S\. Kambhampati, K\. Valmeekam, L\. Guan, M\. Verma, K\. Stechly, S\. Bhambri, L\. P\. Saldyt, and A\. B\. MurthyPosition: LLMs can’t plan, but can help planning in LLM\-modulo frameworks\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 22895–22907\.External Links:[Link](https://proceedings.mlr.press/v235/kambhampati24a.html)Cited by:[§2\.1](https://arxiv.org/html/2608.18409#S2.SS1.p1.1)\.
- Kesseliet al\.\(2025\)P\. Kesseli, P\. O’Hearn, and R\. S\. CabralLogic\.py: bridging the gap between LLMs and constraint solvers\.InAdvances in Neural Information Processing Systems,Vol\.38\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2025/hash/5a29c3d172b80bab1238ddc227246c52-Abstract-Conference.html)Cited by:[§2\.4](https://arxiv.org/html/2608.18409#S2.SS4.p1.1)\.
- Liaoet al\.\(2026\)W\. Liao, W\. Du, Y\. Li, H\. Liang, and W\. LeiNL⇒\\Rightarrowschedule: evaluate multitask scheduling capability of large language models\.InProceedings of the 64th Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),M\. Liakata, V\. P\. Moreira, J\. Zhang, and D\. Jurgens \(Eds\.\),San Diego, California, United States,pp\. 35620–35640\.External Links:[Link](https://aclanthology.org/2026.acl-long.1648/),[Document](https://dx.doi.org/10.18653/v1/2026.acl-long.1648),ISBN 979\-8\-89176\-390\-6Cited by:[§2\.5](https://arxiv.org/html/2608.18409#S2.SS5.p1.1)\.
- Michailidiset al\.\(2024\)K\. Michailidis, D\. Tsouros, and T\. GunsConstraint modelling with LLMs using in\-context learning\.In30th International Conference on Principles and Practice of Constraint Programming \(CP 2024\),Leibniz International Proceedings in Informatics \(LIPIcs\), Vol\.307,Dagstuhl, Germany,pp\. 20:1–20:27\.External Links:[Document](https://dx.doi.org/10.4230/LIPIcs.CP.2024.20),[Link](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.20)Cited by:[§2\.4](https://arxiv.org/html/2608.18409#S2.SS4.p1.1)\.
- Panet al\.\(2023\)L\. Pan, A\. Albalak, X\. Wang, and W\. WangLogic\-LM: empowering large language models with symbolic solvers for faithful logical reasoning\.InFindings of the Association for Computational Linguistics: EMNLP 2023,Singapore,pp\. 3806–3824\.External Links:[Document](https://dx.doi.org/10.18653/v1/2023.findings-emnlp.248),[Link](https://aclanthology.org/2023.findings-emnlp.248/)Cited by:[§1](https://arxiv.org/html/2608.18409#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.18409#S2.SS2.p1.1)\.
- Ramamonjisonet al\.\(2022\)R\. Ramamonjison, T\. Yu, R\. Li, H\. Li, G\. Carenini, B\. Ghaddar, S\. He, M\. Mostajabdaveh, A\. Banitalebi\-Dehkordi, Z\. Zhou, and Y\. ZhangNL4Opt competition: formulating optimization problems based on their natural language descriptions\.InProceedings of the NeurIPS 2022 Competitions Track,Proceedings of Machine Learning Research, Vol\.220,pp\. 189–203\.External Links:[Link](https://proceedings.mlr.press/v220/ramamonjison23a.html)Cited by:[§1](https://arxiv.org/html/2608.18409#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.18409#S2.SS2.p1.1)\.
- Sharma and Sharma \(2026\)S\. S\. Sharma and A\. SharmaSCHEDBench: A benchmark for evaluating LLM constraint faithfulness in natural\-language combinatorial scheduling\.arXivarXiv:2608\.00991\.External Links:[Link](https://arxiv.org/abs/2608.00991),[Document](https://dx.doi.org/10.48550/arXiv.2608.00991)Cited by:[§2\.5](https://arxiv.org/html/2608.18409#S2.SS5.p1.1)\.
- Shiet al\.\(2025\)W\. Shi, M\. Liu, W\. Zhang, L\. Shi, F\. Jia, F\. Ma, and J\. ZhangConstraintLLM: a neuro\-symbolic framework for industrial\-level constraint programming\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,Suzhou, China,pp\. 15999–16019\.External Links:[Document](https://dx.doi.org/10.18653/v1/2025.emnlp-main.809),[Link](https://aclanthology.org/2025.emnlp-main.809/)Cited by:[§1](https://arxiv.org/html/2608.18409#S1.p2.1),[§2\.2](https://arxiv.org/html/2608.18409#S2.SS2.p1.1),[§2\.4](https://arxiv.org/html/2608.18409#S2.SS4.p1.1),[§3](https://arxiv.org/html/2608.18409#S3.p1.1)\.
- Tamet al\.\(2024\)Z\. R\. Tam, C\. Wu, Y\. Tsai, C\. Lin, H\. Lee, and Y\. ChenLet me speak freely? A study on the impact of format restrictions on large language model performance\.InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: Industry Track,Miami, Florida, US,pp\. 1218–1236\.External Links:[Document](https://dx.doi.org/10.18653/v1/2024.emnlp-industry.91),[Link](https://aclanthology.org/2024.emnlp-industry.91/)Cited by:[§2\.1](https://arxiv.org/html/2608.18409#S2.SS1.p1.1),[§2\.3](https://arxiv.org/html/2608.18409#S2.SS3.p1.1)\.
- Valmeekamet al\.\(2023\)K\. Valmeekam, M\. Marquez, A\. Olmo, S\. Sreedharan, and S\. KambhampatiPlanBench: an extensible benchmark for evaluating large language models on planning and reasoning about change\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 38975–38987\.External Links:[Document](https://dx.doi.org/10.52202/075280-1693),[Link](https://proceedings.neurips.cc/paper_files/paper/2023/hash/7a92bcdede88c7afd108072faf5485c8-Abstract-Datasets_and_Benchmarks.html)Cited by:[§2\.1](https://arxiv.org/html/2608.18409#S2.SS1.p1.1)\.
- Yaoet al\.\(2024\)S\. Yao, H\. Chen, A\. W\. Hanjie, R\. Yang, and K\. NarasimhanCOLLIE: systematic construction of constrained text generation tasks\.InThe Twelfth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=kxgSlyirUZ)Cited by:[§2\.1](https://arxiv.org/html/2608.18409#S2.SS1.p1.1)\.
- Yin and Neubig \(2018\)P\. Yin and G\. NeubigTRANX: a transition\-based neural abstract syntax parser for semantic parsing and code generation\.InProceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations,Brussels, Belgium,pp\. 7–12\.External Links:[Document](https://dx.doi.org/10.18653/v1/D18-2002),[Link](https://aclanthology.org/D18-2002/)Cited by:[§2\.3](https://arxiv.org/html/2608.18409#S2.SS3.p1.1)\.

## Appendix ASDDL Semantics and Compilation

### A\.1Primitive and Property Reference

Table[5](https://arxiv.org/html/2608.18409#A3.T5)lists every primitive, accepted property, and well\-formedness requirement; Table[2](https://arxiv.org/html/2608.18409#A1.T2)defines the five registered penalty measures\.

Table 2:The five registered penalty measures\. Each is implemented once in the compiler and reused across programs;makespanis the only measure exercised by the evaluated families\.
### A\.2Compiler\-Lowering Summary

Table[6](https://arxiv.org/html/2608.18409#A3.T6)maps each SDDL construct to the CP\-SAT encoding the compiler emits; all solver variables are introduced by the compiler\.

### A\.3Correctness Arguments

Adequacy is proven statement\-by\-statement; the constructs whose lowerings introduce auxiliary variables require the following arguments:

- •Cumulative resources\.AddCumulativeenforces∑i:si≤t<eidi​r≤k\\sum\_\{i:\\,s\_\{i\}\\leq t<e\_\{i\}\}d\_\{ir\}\\leq kat everytt, the reference condition\. Multi\-mode tasks contribute one*optional*interval per mode, present iff its mode Boolean holds;AddExactlyOnepresents exactly the selected mode’s interval and demand, so solutions correspond one\-to\-one with reference schedules\.
- •Mode selection\.AddExactlyOne\(bi⋅\)\(b\_\{i\\cdot\}\)makes selection total and unique; channellingbi​m⇒di=di​mb\_\{im\}\\Rightarrow d\_\{i\}=d\_\{im\}fixes the master interval’s duration, per\-mode optional intervals share the task’s start, and nonrenewable consumption∑mci​m​r​bi​m\\sum\_\{m\}c\_\{imr\}b\_\{im\}equals the selected mode’s consumption\. Starts, durations, consumptions are preserved in both directions\.
- •Reified penalty measures\.Every measure lowers to variables constrained to*equal*the measured quantity \(AddMaxEqualityfor makespan; complementaryOnlyEnforceIfpairs,b⇔b\\Leftrightarrowcondition, for discrete counts\), never one\-sided bounds a minimizer could exploit; compiled objectives therefore equal reference objectives on all feasible schedules\.
- •Horizon soundness\.WithH=T\+∑imaxm∈Mi⁡di​mH=T\+\\sum\_\{i\}\\max\_\{m\\in M\_\{i\}\}d\_\{im\}\(TT= one plus the latest forbidden time; zero for the evaluated families\), the serial schedule in topological order is feasible with span≤H\\leq H, so truncation to\[0,H\]\[0,H\]never empties the feasible set\. The unrestricted optimum is at most the serial span≤H\\leq H, and any schedule attaining it has every end within\[0,H\]\[0,H\]; the compiled optimum equals the reference optimum\.
- •Composition\.Lowerings share only the task variables\(si,di,ei,bi​m\)\(s\_\{i\},d\_\{i\},e\_\{i\},b\_\{im\}\)whose meaning the items above fix, so per\-statement adequacy composes to program adequacy; the residual failure surface is the model\-produced formalization, measured by the independent verifier \([B\.4](https://arxiv.org/html/2608.18409#A2.SS4)\)\.

### A\.4Worked Translation Example

Figure[3](https://arxiv.org/html/2608.18409#A3.F3)shows one complete translation\. CP\-SAT returns the optimum, makespan 7 \(welding:j0\_o0\[0,3\)\[0,3\),j1\_o1\[4,7\)\[4,7\); grinding:j1\_o0\[0,4\)\[0,4\),j0\_o1\[4,6\)\[4,6\); the lower bound from Batch Concord’s4\+34\{\+\}3chain\), rendered back to schedule lines vialabel/position\.

### A\.5Full SDDL, Transpiler, Compiler

- •literal\-onlyast\-based parser \(∼\\sim170 lines; generated text is never executed\);
- •CP\-SAT transpiler \(∼\\sim560 lines; both archetypes, all five measures\);
- •renderer mapping solved variables to schedule lines via task labels;
- •evaluation harness, per\-instance outputs, and scoring records\.

## Appendix BExperimental Details

### B\.1SCHEDBench Evaluation Subset

Instances chosen randomly using a fixed subsampling seed 42; instance identifiers are thesource\_instancefields of the benchmark\. Gaps are computed against canonical optimum or best\-known solution; and breakdown of per family subset composition is below\.

Table 3:Evaluation\-subset composition\.
### B\.2Prompt Templates

Figures[4](https://arxiv.org/html/2608.18409#A3.F4)and[5](https://arxiv.org/html/2608.18409#A3.F5)reproduce the three fixed, instance\-independent system prompts; the user message is the instance’s problem text plus its response\-format section, identical across tested conditions\. All conditions are evaluated zero\-shot, without worked examples\.

#### B\.2\.1Direct Generation

Figure[4](https://arxiv.org/html/2608.18409#A3.F4)reproduces theDirectsystem prompt\.

#### B\.2\.2Generic Solver\-Code Generation

Figure[5](https://arxiv.org/html/2608.18409#A3.F5)reproduces theSolversystem prompt\.

#### B\.2\.3SDDL Generation

TheSDDLsystem prompt is reproduced beginning on p\.[C\.1](https://arxiv.org/html/2608.18409#A3.SS1)\.

### B\.3Model, Inference, and Solver Configuration

Table 4:Inference, sandbox, and solver configuration\.
### B\.4Verification and Outcome Accounting

The verifier parses emitted schedule lines and re\-derives feasibility and the objective directly from the canonical source instance; it shares no code with the DSL parser, transpiler, or CP\-SAT, and is the same component that scoresDirect\(whose pipeline involves no compiler\)\. Solver status is never trusted\.

- •Run\-fail: no scoreable schedule \(unparseable/empty output, parse rejection, transpile or runtime error, sandbox timeout, or no completed generation\)\.
- •No\-solution: program executed; solver reported infeasibility or returned nothing within budget\.
- •Infeasible: schedule produced but violates a hard constraint \(classified precedence / machine\-overlap / resource\-capacity, plus coverage for missing activities\)\.
- •Feasible: all hard constraints verified; objective recomputed from the schedule\.
- •Directaccounting: unparseable→\\torun\-fail; parsed\-but\-violating→\\toinfeasible; no\-solution cannot occur\.
- •Denominator:N=300N\{=\}300per configuration; instances without a completed generation count as run\-fail, so each row’s outcomes sum to 100%\.
- •Wilson 95% CI:\(p^\+z22​n±z​p^​\(1−p^\)n\+z24​n2\)/\(1\+z2n\)\\big\(\\hat\{p\}\+\\tfrac\{z^\{2\}\}\{2n\}\\pm z\\sqrt\{\\tfrac\{\\hat\{p\}\(1\-\\hat\{p\}\)\}\{n\}\+\\tfrac\{z^\{2\}\}\{4n^\{2\}\}\}\\big\)\\big/\\big\(1\+\\tfrac\{z^\{2\}\}\{n\}\\big\),z=1\.96z=1\.96\.
- •Paired tests: two\-sided exact McNemar on instance\-level feasibility,p=min⁡\(1,2​∑i≤min⁡\(b,c\)\(ni\)​2−n\)p=\\min\\\!\\big\(1,2\\sum\_\{i\\leq\\min\(b,c\)\}\\binom\{n\}\{i\}2^\{\-n\}\\big\),n=b\+cn=b\+c; Holm correction applied jointly across all reported pairwise comparisons; unscored instances count as not\-feasible on both sides \(no verdict changes on the jointly\-scored subset\)\. Table[7](https://arxiv.org/html/2608.18409#A3.T7)lists all discordant counts\.

## Appendix CSupplemental Results

### C\.1Error Analysis

Representative exemplars \(one per dominant code\):

- •Dropped edge: all 32 tasks, 4 resources, and every duration/demand of a 30\-activity MM\-RCPSP instance transcribed correctly; twobefore\(\)entries omitted\.
- •Conflation: instance contains both “Waste Removal Planning” and “North Waste Removal Planning”; the program declares onlynorth\_waste\_removal\_planningyet writesbefore\("waste\_removal\_planning", \.\.\.\)→\\toKeyError\.
- •Derailment: correct DSL for 160 lines, then drift into natural\-language commentary; rejected at parse time\.
- •Duplicate declarations: a job\-shop program emits its 300 operation declarations twice \(600 task\(\) calls\), leaving edge semantics attached to shadowed duplicates\.

Table 5:Complete primitive and property reference\. A well\-formedtasksatisfies exactly one archetype rule: it is*continuous*iff it specifiesdurationormodesand nocount, and*discrete*iff it specifiescount; archetype assignment is therefore deterministic and complete, and a task specifying both \(or neither\) is rejected as malformed\.Table 6:Statement\-by\-statement lowering into CP\-SAT\. Discrete\-archetype tasks lower to day, period, and room integer variables with a channelled slot variableslot=day⋅NP\+period\\mathrm\{slot\}=\\mathrm\{day\}\\cdot N\_\{P\}\+\\mathrm\{period\}\.Natural\-language statement\.*2 jobs, 2 machines\. Job “Batch Northview”: step 1 on Main Welding Station for 3 min, step 2 on West Grinding Station for 2 min\. Job “Batch Concord”: step 1 on West Grinding Station for 4 min, step 2 on Main Welding Station for 3 min\.*

SDDL program \(model output\):

resource\("main\_welding\_station"\)

resource\("west\_grinding\_station"\)

task\("j0\_o0",label="BatchNorthview",job=0,position=0,machine="main\_welding\_station",duration=3\)

task\("j0\_o1",label="BatchNorthview",job=0,position=1,machine="west\_grinding\_station",duration=2\)

task\("j1\_o0",label="BatchConcord",job=1,position=0,machine="west\_grinding\_station",duration=4\)

task\("j1\_o1",label="BatchConcord",job=1,position=1,machine="main\_welding\_station",duration=3\)

before\("j0\_o0","j0\_o1"\)

before\("j1\_o0","j1\_o1"\)

no\_overlap\("main\_welding\_station"\)

no\_overlap\("west\_grinding\_station"\)

penalize\("makespan",weight=1\)

Principal compiled constraints:

horizon=12

starts\[’j0\_o0’\]=model\.NewIntVar\(0,horizon,’j0\_o0\_s’\)

ends\[’j0\_o0’\]=model\.NewIntVar\(0,horizon,’j0\_o0\_e’\)

intervals\[’j0\_o0’\]=model\.NewIntervalVar\(starts\[’j0\_o0’\],3,ends\[’j0\_o0’\],’j0\_o0\_iv’\)

\.\.\.\#samethreelinespertask

model\.Add\(starts\[’j0\_o1’\]\>=ends\[’j0\_o0’\]\)

model\.Add\(starts\[’j1\_o1’\]\>=ends\[’j1\_o0’\]\)

model\.AddNoOverlap\(\[intervals\[’j0\_o0’\],intervals\[’j1\_o1’\]\]\)\#main\_welding\_station

model\.AddNoOverlap\(\[intervals\[’j0\_o1’\],intervals\[’j1\_o0’\]\]\)\#west\_grinding\_station

\_ms=model\.NewIntVar\(0,horizon,’makespan’\)

model\.AddMaxEquality\(\_ms,\[ends\[’j0\_o0’\],ends\[’j0\_o1’\],ends\[’j1\_o0’\],ends\[’j1\_o1’\]\]\)

penalties\.append\(\_ms\)

total=model\.NewIntVar\(0,99999999,’total’\)

model\.Add\(total==sum\(penalties\)\)

model\.Minimize\(total\)

Figure 3:Worked end\-to\-end translation: natural\-language instance→\\rightarrowSDDL→\\rightarrowcompiled CP\-SAT model\.Youarecompletinganautomatedbenchmark\.Theusermessagecontainsaschedulingproblemandanexactoutputformat\.Beginyourresponsewiththefirstschedulelineandoutputonlythescheduleinthatformat\-\-nothingelse:nopreamble,noexplanation,noreasoning,nomarkdownformatting\(no\*\*bold\*\*,no‘inlinecode‘,notriple\-backtickcodeblocks\),noXMLtagssuchas<schedule\>or<answer\>,notooltags,noPythoncode\.Donotcallanytools,donotinvokeexternalsolvers,anddonotgeneratecodetobeexecuted\-\-solvetheproblemyourselfusingonlyyourownreasoning\.Yourresponseisfeddirectlyintoaparser;anyextracharacterscausetheresponsetobediscarded\.

Figure 4:Directsystem prompt\.Youarecompletinganautomatedbenchmark\.Theusermessagecontainsaschedulingproblemwritteninnaturallanguageandanexactoutputformat\.Donotsolvetheprobleminyourheadanddonotemitascheduledirectly\.Instead,writeasingleself\-containedPython3programthatsolvestheproblemusingortools\.sat\.python\.cp\_modelandprintstheresultingscheduletostandardoutputinexactlytheoutputformattheusermessagespecifies\.Thefirstcharacterofyourresponsemustbethefirstcharacteroftheprogram\(typically"from"or"import"\);outputnothingelse\-\-nopreamble,noexplanation,noreasoning,nomarkdownformatting,notriple\-backtickcodeblocks,noXMLtags,nocommentsoutsidetheprogrambody\.

EverypieceofinstancedatamustbetranscribedfromtheusermessageintotheprogramasPythonliterals\.Donotreadfromanyfile,donotimportadatamodule,donotmakeanynetworkrequest,anddonotdependonanyenvironmentvariable,command\-lineargument,orsidechannel\.Theprogrammustruntocompletiononitsownwith‘pythonprogram\.py‘inafreshdirectorywithnonetworkaccess\.AllowedimportsarethePythonstandardlibraryandortools\.sat\.python\.cp\_model\-\-nothingelse\.

Theprogram’sstandardoutputmustbe,andonlybe,schedulelinesinexactlytheformattheusermessagespecifies\-\-thesamecharacter\-levelformatthatthedirect\-scheduleconditionuses\.Donotprintstatuslabels,diagnostics,timings,orobjectivevalues;donotwraptheoutputinanyenvelopeorcodefence\.IfthesolverreturnsINFEASIBLEorUNKNOWN,printnothingandexitcleanly\.Theprogram’sstandardoutputisfedunchangedintothesameparserusedtoscoredirect\-scheduleoutputs;anyextracharacterscausetheresponsetobediscarded\.

\#\#CP\-SATmodelingguide

model=cp\_model\.CpModel\(\)\.Giveeveryoperation\(jobshop\)oractivity

\(projectscheduling\)oneinterval:startandendasNewIntVarboundedby

horizon=sumofalldurations,linkedby

NewIntervalVar\(start,duration,end\)\.Milestonesareintervalsof

duration0\.

\#\#Constraints

\-Precedence:foreachsuccessorentry,model\.Add\(start\_b\>=end\_a\)\.

\-Job\-shopmachine\(oneoperationatatime\):AddNoOverlapoverexactlythe

intervalsassignedtothatmachine\.

\-Renewableresourcepool\(capacitylimitwhileactive\):AddCumulativeover

thedemandingintervalswiththeirper\-taskdemandsandthepool’s

capacity\.NEVERencodearenewablepoolwithAddNoOverlap\.

\-Nonrenewablebudget\(consumedonce\):asinglelinearconstraint,

model\.Add\(sumofconsumedamounts<=total\)\.

\-Alternativeexecutionmodes:oneBoolVarpermodewithAddExactlyOne;

eachmodecontributesNewOptionalIntervalVarcarryingthatmode’s

duration,itsdemandstotherelevantAddCumulativecalls,andits

consumptiontothebudgetconstraint\.

\-Slot\-conflictgroups\(timetabling\):AddAllDifferentoverthetasks’slot

variables;forbiddentimes:model\.Add\(slot\!=t\)\.

\#\#Objective

makespan=NewIntVar\(0,horizon\);AddMaxEquality\(makespan,allends\);

model\.Minimize\(makespan\)\.Solvewithcp\_model\.CpSolver\(\);set

solver\.parameters\.max\_time\_in\_seconds=240\.

\#\#Rules

1\.Oneintervalperoperationoractivity,includingstartandfinish

milestones\.

2\.OneAddNoOverlapperjob\-shopmachine;AddCumulativeforevery

capacity\-limitedpool\.

3\.Oneprecedenceconstraintpersuccessorentry;transcribeallofan

activity’slistedsuccessorsbeforemovingtothenext\.Job\-shopsteps

arechainedconsecutively\.

4\.Anactivitywithonefixedprofileusesaplaininterval,notmodes\.

5\.Transcribeeveryduration,demand,capacity,andtotalexactlyasgiven\.

6\.Minimizemakespan\.

7\.PrintONLYschedulelines,withdisplaynamesexactlyaswritteninthe

problemtext\.

Figure 5:Solversystem prompt\.Table 7:McNemar discordant counts \(bb:SDDL\-only feasible;cc: comparison\-only feasible\) and two\-sidedpp\-values for the within\-model contrasts; all remain significant after Holm correction \(padj<10−6p\_\{\\mathrm\{adj\}\}<10^\{\-6\}\)\.Table 8:Resource\-constrained models across all three conditions, direct→\\rightarrowsolver\-mediated→\\rightarrowSDDL, in the format of Table[1](https://arxiv.org/html/2608.18409#S4.T1)\. Brackets list 95% Wilson CIs on feasibility\. Color follows one model across rows, withbluefor qwen3\.5\-27b,orangefor devstral\-small\-2\-24b,greenfor qwen3\-coder\-30b\-a3b,purplefor magistral\-small\-24b\.Table 9:qwen3\.5\-27b by family and condition \(N=300N=300convention; run\-fail includes instances without a completed generation\)\.Failure codeqwen3\.5devstralq3\-codermagistralTotalDropped / garbled precedence edges \(tasks complete\)644519Referenced\-but\-undeclared real activity12036Phantom identifier \(no problem counterpart\)11002Duplicate task declarations01102Coverage collapse / label mismatch01203Primitive\-argument misuse00101Emission derailment \(prose drift, repetition, syntax slip\)20013Coded / sampled10/109/108/109/1036/40Table 10:Hand\-coded causes over a stratified sample ofSDDLfailures \(one primary code per instance\)\.TheSDDLsystem prompt\.

Youarecompletinganautomatedbenchmark\.Theusermessagecontainsaschedulingproblemwritteninnaturallanguage,followedbya"ResponseFormat"sectiondescribingschedulelines\.IGNOREthatResponseFormatsectionentirely\-\-itdescribesadifferentanswermodeanddoesnotapplytoyou\.Donotsolvetheproblemanddonotemitaschedule\.Instead,translatetheproblemintoSDDL:asmalldeclarativelanguagethatadownstreamcompilerturnsintoanexactsolvermodel\.ThefirstcharacterofyourresponsemustbethefirstcharacteroftheDSL;outputnothingelse\-\-nopreamble,noexplanation,noreasoning,nomarkdown,nocodefences,noXMLtags,nocomments\.

EverypieceofinstancedatamustbetranscribedfromtheusermessageintotheDSLasliterals\.Transcriptionaccuracyisthewholetask:asinglewrongdurationormachinesilentlyproducesavalid\-lookingbutwronganswer\.Donotomitanytask,anyprecedence,oranyresource\.

\#\#The7primitives

resource\(id,\*\*props\)amachine,renewableresource,ornonrenewablebudget

task\(id,\*\*props\)oneoperation/activitytoschedule

before\(a,b\)HARD:taskafinishesbeforetaskbstarts

no\_overlap\(resource\_id\)HARD:onetaskatatimeonthatresource

conflict\(t1,\.\.\.,group=\)HARD:listedtaskscannotshareatimeslot

not\_at\(id,day=,period=\)HARD:thetaskcannotrunatthattime

penalize\(measure,weight=1\)softobjective;measures:makespan,

capacity,spread,isolated,room\_stability

\#\#Taskproperties

\-duration=Ntimelength

\-label="ExactName"REQUIREDoneverytask\.SeetheLabelssectionbelow\.

\-machine="rid"fixedresourceassignment;pairwithno\_overlap\(rid\)

\-job=N,position=Njobindexand0\-BASEDoperationindexwithinthatjob

\-demands=\{"r":n\}renewableunitsusedWHILEactive

\-consumes=\{"b":n\}nonrenewableunitsusedONCE

\-modes=\[\{"duration":N,"demands":\{\.\.\.\},"consumes":\{\.\.\.\}\},\.\.\.\]

alternativeexecutionmodes;thesolverpicksexactlyone

\#\#Resourceproperties

\-capacity=Nrenewable:per\-time\-periodlimit

\-total=Nnonrenewable:project\-widebudget

\#\#Labels\-\-readcarefully,resultsarediscardedwithoutthem

‘label‘carriestheentity’sdisplaynamefromtheproblemtext,verbatim:

capitalization,spacing,andpunctuationexactlyaswritten\.

\-Job\-shopproblems:labelistheITEM/JOBnameONLY,neverwithastep

suffix;the0\-basedstepindexgoesinposition=\.

\-Projectproblems:labelistheACTIVITYname,includingthenamedstartand

finishmilestones\.Everyactivitygetsitsowntask\(\)withitsownlabel\.

\#\#Identifiers

‘id‘andresourceidsaresanitizedsnake\_case,neverthedisplayname\.Keysof

demands=\{\}/consumes=\{\}MUSTexactlymatchthecorrespondingresource\(\)id\.

\#\#Rules

1\.Onetask\(\)peroperation\(jobshop\)orperactivity\(projectscheduling\),

includingstartandfinishmilestones\.

2\.Oneresource\(\)permachine,renewableresource,ornonrenewablebudget\.

3\.Onebefore\(\)perSUCCESSORENTRY\.Workthroughtheactivitiesinorder;for

eachone,transcribeallofitslistedsuccessorsbeforemovingtothenext\.

Anactivitylistingksuccessorscontributeskbefore\(\)calls\-\-donotmove

onwithapartialsuccessorlist\.Job\-shopstepsarechainedconsecutively\.

4\.Oneno\_overlap\(\)perjob\-shopmachine\.NEVERuseno\_overlapforaproject

schedulingrenewableresource\-\-capacity=plusdemands=\{\}alreadygivesthe

correctcumulativesemantics,andaddingitmakesthemodelwrong\.

5\.Amodedictomitsresourcesitdoesnotuse\.Anactivitywithonefixedmode

usesplainduration=/demands=/consumes=,notmodes=\[\]\.

6\.Endwithonepenalize\(\)perstatedobjective,namingthemeasurethat

matchestheproblem’sobjectiveanditsweight\.

7\.OutputONLYtheDSLcalls\.