Beyond Objective Equivalence: Constraint Injection for LLM-Based Optimization Modeling on Vehicle Routing Problems

• URL: http://arxiv.org/abs/2606.04816v1
• Date: Wed, 03 Jun 2026 12:39:04 GMT
• Title: Beyond Objective Equivalence: Constraint Injection for LLM-Based Optimization Modeling on Vehicle Routing Problems
• Abstract summary: We propose constraint injection to expose spurious over-constraints and one-constraint-violating probes to reveal silent constraint omission.<n>We develop VRPCoder, an 8B end-to-end model that translates natural-language VRP scenarios into Gurobi scripts.<n>VRPCoder-GRPO reaches 93% average Pass@1, Gemini outperforms-3.1-Pro Preview on three benchmarks, exceeds Claude-Sonnet-4.5 by 28 average points, and surpasses prior-LLMs by 78 average points.
• Score: 3.024294453714127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large language models (LLMs) increasingly translate natural-language optimization problems into executable solver code. Yet for constraint-dense operations research (OR) problems, existing data-filtering and training pipelines largely rely on objective-equivalence signals such as differential testing and answer agreement, which a program can pass while adding spurious constraints or silently omitting required ones, whenever those constraints are non-binding on the tested instance. We propose constraint injection, which uses feasible probes to expose spurious over-constraint and one-constraint-violating probes to reveal silent constraint omission. Combined with differential testing, it forms a dual verifier. We instantiate and evaluate it on vehicle routing problems (VRPs), a representative constraint-dense combinatorial optimization testbed with coupled operational constraints. We develop VRPCoder, an 8B end-to-end model that translates natural-language VRP scenarios into Gurobi scripts, together with an expert-verified VRP benchmark suite covering 21 variants. The verifier is reused as a rejection-sampling filter during data synthesis and as a per-rollout reward in group relative policy optimization (GRPO). Across four VRP benchmarks, VRPCoder-GRPO reaches 93\% average Pass@1, outperforms Gemini-3.1-Pro Preview on three benchmarks, exceeds Claude-Sonnet-4.5 by 28 average points, and surpasses prior OR-LLMs by 78 average points.

Related papers

• When RLVR Shrinks the Reasoning Boundary: Diagnosing Pass@k Inversion [0.0]
  Reinforcement learning with verifiable rewards (RLVR) can improve one-sample accuracy while making a model worse under repeated sampling.<n>We study this pass@k inversion: after training, the policy may solve fewer distinct problems than its base model at large $k$.<n>The failure concentrates on boundary prompts, where the base model contains rare correct trajectories that are recoverable by sampling but too sparse to reliably appear in finite RLVR rollout groups.
  arXiv  Detail & Related papers  (2026-07-12T17:17:18Z)
• Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata [57.27430779838529]
  We present an exact and tractable algorithm for sampling from the constrained mean-field posterior under any constraint expressible as a finite automaton.<n>The approach guarantees constraint satisfaction by construction, supports both greedy and sampling-based decoding, and is compatible with parallel and block-wise decoding.<n> Empirical evaluations on Dream-7B and LLaDA-8 show substantial accuracy gains across various tasks.
  arXiv  Detail & Related papers  (2026-07-08T05:48:57Z)
• CLEAR: Cognition and Latent Evaluation for Adaptive Routing in End-to-End Autonomous Driving [19.474428775260034]
  We propose CLEAR, a framework that combines ultra-fast generative planning with deep semantic reasoning.<n> CLEAR employs Drive-JEPA as the visual encoder and replaces the multi-step denoising chain with a single-step conditional drift in a VAE latent space.<n>On the NAVSIM v1 benchmark, CLEAR achieves a state-of-the-art PDMS of 93.7.
  arXiv  Detail & Related papers  (2026-06-04T14:32:10Z)
• LiveFMBench: Unveiling the Power and Limits of Agentic Workflows in Specification Generation [75.05397479715576]
  Large language models (LLMs) and agents have shown promising progress, but their true capabilities and failure modes remain unclear.<n>We present the first systematic and contamination-aware study of LLM- and agent-based formal specification generation for C programs.
  arXiv  Detail & Related papers  (2026-05-02T11:31:33Z)
• Too Correct to Learn: Reinforcement Learning on Saturated Reasoning Data [55.84428098924793]
  We propose Constrained Uniform Top-K Sampling (CUTS), a parameter-free decoding strategy enforcing structure-preserving exploration.<n>We integrate this into Mixed-CUTS, a training framework synergizing exploitative and exploratory rollouts to amplify intra-group advantage variance.<n> Notably, Mixed-CUTS improves Pass@1 accuracy on the challenging AIME25 benchmark by up to 15.1% over standard GRPO.
  arXiv  Detail & Related papers  (2026-04-20T16:43:28Z)
• CCTU: A Benchmark for Tool Use under Complex Constraints [66.87622847854337]
  We introduce CCTU, a benchmark for evaluating large language models (LLMs) under complex constraints.<n>The benchmark comprises 200 carefully curated and challenging test cases across diverse tool-use scenarios.<n>We develop an executable constraint validation module that performs step-level validation and enforces compliance.
  arXiv  Detail & Related papers  (2026-03-16T14:05:13Z)
• An Evaluation Study of Hybrid Methods for Multilingual PII Detection [0.026059379504241156]
  We present RECAP, a framework that combines deterministic regular expressions with context-aware large language models (LLMs) for scalable PII detection.<n>Our system outperforms fine-tuned NER models by 82% and zero-shot LLMs by 17% in weighted F1-score.<n>This work offers a scalable and adaptable solution for efficient PII detection in compliance-focused applications.
  arXiv  Detail & Related papers  (2025-10-08T21:03:59Z)
• Reverse Preference Optimization for Complex Instruction Following [61.39734201711077]
  We propose a simple yet effective method called Reverse Preference Optimization (RPO)<n>It mitigates noise in preference pairs by dynamically reversing the constraints within the instruction to ensure the chosen response is perfect.<n>RPO scales effectively across model sizes, with the 70B RPO model surpassing GPT-4o.
  arXiv  Detail & Related papers  (2025-05-28T09:44:27Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.