PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Shrenil Shaun Sharma, Avi Sharma

arXiv:2608.18409v1cs.AI

TL;DR

Resource-constrained language models struggle to formalize natural-language scheduling problems while preserving feasibility. SDDL uses compact scheduling abstractions compiled for external solving, improving independently verified feasibility for every tested resource-constrained model, with the strongest configuration reaching 55.3%.

  • Problem

    Language models must infer mathematical structure from natural-language optimization descriptions, but direct scheduling requires preserving constraints, objectives, and interdependent decisions.

  • Method

    SDDL expresses scheduling tasks, resources, constraints, alternatives, and objectives through compact domain-specific abstractions that a deterministic compiler converts into solver models.

  • Results

    SDDL improves independently verified feasibility for every tested resource-constrained model; the strongest configuration reaches 55.3% feasibility.

  • Takeaways & Limitations

    On 300 instances across multiple scheduling families, SDDL enables resource-constrained models to match or approach the strongest evaluated configurations.

  • Takeaways & Limitations

    The evaluation covers only three scheduling families and does not test generalization beyond scheduling or iterative repair and self-correction.

Abstract

from arXiv · show

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.

1 Introduction

Natural-language combinatorial optimization requires models to infer mathematical structure, track constraints and objectives, and search for feasible solutions, with these demands intensified for resource-constrained smaller models. SDDL addresses this limitation through scheduling-native formal abstractions compiled deterministically for external solver execution, improving verified feasibility and enabling smaller models to approach stronger configurations.

  • Motivation: Natural-language optimization requires models to translate verbal descriptions into search spaces and evaluate candidates against implicit feasibility and optimality criteria.The task also requires parsing descriptions, tracking interacting constraints, reasoning about objectives, and searching over alternatives.
  • Motivation: Resource constraints limit model selection to substantially smaller language models, making single-pass solution generation especially difficult.Smaller models must handle parsing, interacting constraints, objectives, and implicit search during autoregressive generation.
  • Approach: SDDL separates language understanding from computation by representing scheduling tasks, resources, constraints, alternatives, and objectives, then deterministically compiling programs into solver models.The external solver executes the resulting formal representation instead of requiring the model to emit low-level solver code.
  • Evaluation: SDDL improves independently verified feasibility for every evaluated model and enables substantially smaller models to match or closely approach the strongest direct- and solver-code configurations.The evaluation compares direct and generic solver-code generation across 13 models and tests SDDL on multiple resource-constrained models.

2 Related Work

Prior work identifies weaknesses in multistep planning, constrained generation, and end-to-end scheduling, motivating frameworks that delegate computation while preserving formal correctness. Scheduling benchmarks remain limited, with varying degrees of natural-language richness and formal-ground-truth guarantees.

  • Motivation: LLMs show substantial weaknesses in systematic multistep planning, and external modules can reduce the reasoning burden in constrained scheduling.Scheduling requires recovering semantics, respecting representational conventions, and maintaining constraint fidelity across interdependent temporal decisions.
  • Neuro-symbolic approaches: Neuro-symbolic frameworks translate unstructured text into executable representations and delegate computation to external runtimes, while Logic-LM uses solver feedback to repair invalid formalizations.These approaches aim to bypass internal arithmetic and logical errors through external execution and iterative correction.
  • End-to-end and structured generation: End-to-end combinatorial solvers suffer declining solution quality and feasibility as instance size and structural complexity increase.Structured decoding can enforce output formats, but hard formatting constraints may degrade reasoning, and syntactic validity does not ensure constraint completeness or value correctness.
  • Scheduling-specific methods: Scheduling-specific supervised approaches collapse problem interpretation and combinatorial search into one generation step, complicating diagnosis of translation errors versus search failures.The scheduling literature targeting native problem structure remains narrow and fragmented, including job-shop applications using supervised fine-tuning.
  • Scheduling benchmarks: Scheduling benchmarks vary from fixed-template and structured descriptions to fuller semi-synthetic natural language, while SCHEDBench guarantees formal ground truth and best-known objectives by construction.SCHEDBench uses controlled, constraint-preserving verbalizations of canonical instances from established scheduling literature.

3 Methods and DSL Creation

SDDL uses a closed vocabulary of recurring scheduling constructs that models identify, while a deterministic compiler performs solver-specific encoding. Its property-dependent task and resource representations, structural constraint hardness, and fixed objectives preserve problem meaning while limiting malformed or semantically incorrect programs.

  • Design principles: SDDL shifts failure-prone modeling decisions from the language model to a deterministic compiler by exposing only recurring scheduling structures.The model identifies structures, while the compiler handles downstream encoding.
  • Language design: The DSL prioritizes robustness, concision, and sufficient but bounded expressiveness through a fixed vocabulary of scheduling constructs.Programs use flat primitive sequences and literal lists or maps rather than control flow or general-purpose expressions.
  • Primitive vocabulary: Seven primitives separate problem declarations, hard constraints, and soft objectives, with constraint hardness encoded by primitive choice rather than weights or phrasing.The primitives include task, resource, four hard-constraint forms, and penalize for soft objectives.
  • Resource modeling: Explicit resource types compile differently: disjunctive resources forbid overlap, renewable resources impose cumulative capacity limits, and nonrenewable resources impose project-wide budgets.This distinction addresses a common ambiguity in natural-language scheduling descriptions.
  • Compilation guarantees: A deterministic, literal-only compiler produces a unique solver model and preserves feasibility and objective meaning under SDDL’s abstract semantics.Adequacy means feasible schedules correspond to feasible solver solutions with the same objective value.

4 Experimental Evaluation

The evaluation tests SDDL on established scheduling benchmarks under fixed zero-shot generation conditions, using independent verification as the primary measure of feasibility. It also reports optimality gaps from verifier-recomputed objectives over feasible schedules.

  • Evaluation setup: SDDL is evaluated on publicly released benchmark instances using the SCHEDBench harness and independent verifiers.Previously reported DIRECT and SOLVER results are included, while newly generated results are explicitly marked for contextual comparison.
  • Evaluation setup: All conditions use fixed instance-independent zero-shot prompts, greedy decoding at temperature 0, and no worked examples.Transient API failures are retried until generation completes, regardless of solution quality.
  • Benchmark coverage: The evaluation covers JSSP, single-mode RCPSP, and multi-mode RCPSP families exercising precedence, disjunctive and cumulative resources, budgets, mode selection, and objective channels.The families use a standardized makespan objective, while conflict, not_at, and the discrete archetype remain compiler-verified but unexercised.
  • Metrics and verification: Feasibility requires every hard constraint of the canonical source instance to pass an independent verifier checking integer start times.Violations are classified as precedence, machine-overlap, or resource-capacity errors.
  • Metrics and verification: Optimality gaps are computed from the schedule itself against the canonical optimum or best-known solution and summarized by the median over feasible runs.A schedule is optimal when its gap is at most 10^-9, and each run receives exactly one outcome: feasible, infeasible, no-solution, or run-fail.

5 Results and Discussion

Across 300 scheduling instances, SDDL substantially improves feasibility for resource-constrained models, outperforming direct generation and generic solver assistance. Feasible SDDL schedules also achieve a 0.0% median optimality gap, despite broader feasible coverage.

  • Feasibility: 55.3% feasibility is achieved by Qwen3.5-27B with SDDL, versus 23.7% under DIRECT and 21.7% under SOLVER.The SDDL gains over DIRECT and SOLVER are 31.7 and 33.7 percentage points, respectively, with p < 10^-22.
  • Comparison with frontier configurations: 55.3% feasibility places Qwen3.5-27B with SDDL within 1.4 points of Claude Opus 4.6’s strongest solver-assisted result and 1.7 points of GPT-5.5’s strongest direct result.GPT-5.5 reaches 57.0% direct feasibility, while Claude Opus 4.6 reaches 56.7% solver-assisted feasibility on the 300-instance subset.
  • Solution quality: 0.0% is the median optimality gap across all four resource-constrained models evaluated with SDDL, while feasibility ranges from 15.0% to 55.3%.For Qwen3.5-27B, SDDL combines 55.3% feasibility with a 0.0% median gap, compared with DIRECT’s 23.7% feasibility and 395.8% median gap.

6 Conclusion

The conclusion presents SDDL as a scheduling-specific language for expressing problem structure through compact, solver-aligned primitives. Across 300 SCHEDBench instances spanning multiple scheduling families, it raises feasibility and helps resource-constrained models match or narrow the gap to the strongest evaluated configurations.

  • 6 Conclusion: SDDL lets models express scheduling problem structure through compact, solver-aligned primitives.Low-level modeling and search are delegated to a compiler and solver.
  • 6 Conclusion: On 300 SCHEDBench instances spanning multiple scheduling families, SDDL substantially raises feasibility.The evaluation covers a multi-family set of scheduling problems.
  • 6 Conclusion: SDDL enables resource-constrained models to match or close the deficit to the strongest evaluated configurations.The DSL serves as an intermediate representation between model-generated structure and deterministic solving.

Limitations … A.5 Full SDDL, Transpiler, Compiler

The paper limits its empirical claims to resource-constrained models and evaluated scheduling families, while presenting a compiler-based SDDL implementation with formal lowering arguments and a worked translation. The appendices document the primitives, penalty measures, CP-SAT encodings, correctness conditions, and implementation components.

  • Limitations: SDDL is not evaluated on frontier-scale models, and its generalization beyond scheduling remains empirically untested.The evaluation focuses on resource-constrained applications where frontier-scale models may be impractical; frontier-model evaluation and broader combinatorial domains are left for future work.
  • Limitations: Models below approximately 20B parameters produced feasibility rates below 5% in pilot experiments, restricting conclusions to the evaluated model-size range.The threshold was selected empirically under the fixed zero-shot setting and is not a general minimum model size for SDDL.
  • A.1 Primitive and Property Reference: Table 2 defines five registered penalty measures, each implemented once in the compiler and reused across programs; only makespan is exercised by evaluated families.Table 5 lists the primitives, accepted properties, and well-formedness requirements.
  • A.2 Compiler-Lowering Summary: The compiler maps each SDDL construct to a CP-SAT encoding and introduces all solver variables.The lowering summary specifies that solver-variable creation is delegated to the compiler.
  • A.3 Correctness Arguments: Correctness arguments establish adequacy for cumulative resources, unique mode selection, reified penalty measures, bounded horizons, and their composition.The compiled objectives equal reference objectives on feasible schedules, and composition leaves model-produced formalization as the residual failure surface measured by an independent verifier.
  • A.4 Worked Translation Example: CP-SAT returns the worked example’s optimum, makespan 7, which is rendered back into schedule lines through task labels and positions.The example includes welding and grinding intervals and uses the Batch Concord 4+3 chain as a lower bound.
  • A.5 Full SDDL, Transpiler, Compiler: The full implementation includes a literal-only AST parser, a CP-SAT transpiler, a label-based schedule renderer, and an evaluation harness with per-instance outputs and scoring records.The parser is approximately 170 lines, while the transpiler is approximately 560 lines and supports both archetypes and all five measures.

B Experimental Details … B.4 Verification and Outcome Accounting

The evaluation uses a fixed 300-instance subset with zero-shot, condition-specific prompts and independently rederived outcomes. Verification separates run failures, no-solutions, infeasible schedules, and feasible schedules under a uniform accounting scheme.

  • B.1 SCHEDBench Evaluation Subset: Instances were randomly selected with fixed subsampling seed 42, and optimality gaps use canonical optima or best-known solutions.The benchmark instance identifiers are the source_instance fields, with per-family subset composition reported separately.
  • B.2 Prompt Templates: All conditions use the instance problem text and response-format section identically, evaluated zero-shot without worked examples.Figures 4 and 5 reproduce the three fixed, instance-independent system prompts.
  • B.2.1 Direct Generation: The DIRECT condition uses the system prompt reproduced in Figure 4.
  • B.2.2 Generic Solver-Code Generation: The SOLVER condition uses the generic solver-code system prompt reproduced in Figure 5.
  • B.2.3 SDDL Generation: The SDDL condition uses a system prompt reproduced beginning on page 17.
  • B.3 Model, Inference, and Solver Configuration: Inference, sandbox, and solver settings are specified in Table 4.
  • B.4 Verification and Outcome Accounting: The verifier independently parses schedules, recomputes feasibility and objectives from canonical instances, shares no code with modeling components, and never trusts solver status.Run-fail covers unscoreable outputs; no-solution covers executed programs with infeasibility or no solver return; infeasible schedules violate hard constraints, while feasible schedules satisfy all hard constraints.
  • B.4 Verification and Outcome Accounting: Each configuration evaluates N=300 instances, with incomplete generations counted as run-fail so outcomes sum to 100%.Paired feasibility comparisons use two-sided exact McNemar tests with Holm correction, treating unscored instances as not-feasible on both sides.

C Supplemental Results · C.1 Error Analysis

The supplemental results document how SDDL represents scheduling instances, enforces exact transcription through its prompt and compiler, and fails in a small set of identifiable ways. Error exemplars include omitted precedence edges, identifier conflation, output derailment, and duplicate declarations.

  • C.1 Error Analysis: A dropped-edge failure transcribed all 32 tasks, 4 resources, and every duration and demand in a 30-activity MM-RCPSP instance but omitted two before() entries.The failure preserved instance data while losing precedence constraints.
  • C.1 Error Analysis: Other representative failures include conflating similarly named instances, drifting into natural-language commentary after 160 correct DSL lines, and duplicating 300 operation declarations into 600 task() calls.The conflation caused a KeyError, derailment was rejected at parse time, and duplicates left edge semantics attached to shadowed declarations.
  • C Supplemental Results: SDDL translates natural-language scheduling instances into a compact DSL that a downstream compiler lowers into an exact solver model.The worked example maps a two-job, two-machine instance from natural language through SDDL to compiled CP-SAT.
  • C Supplemental Results: Within-model feasibility contrasts remain significant after Holm correction, with adjusted p-values below 10^-6.McNemar tests count instances feasible only under SDDL versus only under the comparison condition.
  • C Supplemental Results: Resource-constrained evaluations compare direct, solver-mediated, and SDDL conditions across four models, with feasibility reported using 95% Wilson confidence intervals.The table covers qwen3.5-27b, devstral-small-2-24b, qwen3-coder-30b-a3b, and magistral-small-24b.
  • C.1 Error Analysis: The SDDL prompt requires outputting only the DSL, beginning with its first character, while ignoring the natural-language schedule response format.It explicitly forbids schedules, explanations, reasoning, markdown, code fences, XML tags, and comments.
  • C.1 Error Analysis: The prompt frames transcription accuracy as the entire task and forbids omitting any task, precedence, or resource.It warns that a single incorrect duration or machine can silently produce a valid-looking but wrong answer.
  • C.1 Error Analysis: The prompt specifies deterministic DSL structure: one task per operation or activity, one resource per machine or budget, and one before() per successor entry.It also requires verbatim display labels, sanitized snake_case identifiers, exact resource-key matching, and chained job-shop steps.
Loading 2608.18409v1…