Hybrid Neuro-Symbolic Planning for Combinatorial Constraints
Implement a neuro-symbolic architecture that restricts language models to parsing shopping constraints and formulating optimization problems using solver libraries to guarantee mathematically optimal product and coupon combinations.
Time
Compute level
Resources
Prerequisites
Scope
The Gap
In 'Shopping Planning', agents frequently fail Pattern C (Global Optimization Failures) because they cannot perform the combinatorial optimization required to maximize coupon usage against a budget (Section 4.5). The paper notes agents struggle to 'integrate interdependent decisions into a holistic plan'.
“agents still lack robust global consistency checking and backtracking for long-horizon, tightly coupled tasks.”
Limitation
LLMs rely on probabilistic token generation, which is inherently ill-suited for the strict arithmetic and combinatorial logic needed to solve Knapsack-style problems (like coupon stacking) or strict budget balancing.
Proposed Solution
Implement a neuro-symbolic architecture where the LLM is restricted to parsing constraints and formulating them into a Python-based optimization problem (using libraries like `scipy.optimize` or `z3-solver`). The agent then executes this code to derive the mathematically optimal product/coupon combination before converting the result back into the required JSON plan.
Why This Matters
This addresses the fundamental inability of LLMs to perform reliable arithmetic and logic over long horizons, potentially solving the 'fragility' issues identified in the benchmark.
How to Get Started
How to test it: We hypothesize that integrating an external optimizer will reduce arithmetic constraint violations. We will compare a standard LLM agent baseline against our neuro-symbolic agent using constraint-satisfaction success rate as the metric, stopping if success rate does not improve by at least 15%.
- Review the Shopping Planning benchmark specification and codebase for Pattern C failure modes.
- Set up an integration pipeline using `z3-solver` and `scipy.optimize` within a sandbox environment.
- Write a prompt parser that translates natural language coupon and budget constraints into executable Python optimization code.
- Evaluate the hybrid planner against baseline LLM agents on the Shopping Planning test split.
Code linked to this paper on Hugging Face: github.com/QwenLM/Qwen-Agent
Suggested by AI. Adapt it to your setup.
Has This Been Done?
None of the provided literature specifically examines using LLMs to parse and formulate coupon or product combinatorial constraints into Python solver libraries like scipy or z3. While papers like Neuro-Symbolic Constraint Programming for Structured Prediction explore neuro-symbolic reasoning, they do not address this exact application pipeline.
- Neuro-Symbolic Constraint Programming for Structured Prediction · 2021 · 19 citations
- Fast Task Planning With Neuro-Symbolic Relaxation · 2026 · 9 citations
- Learning Symbolic Constraint Representations from Examples: A Neuro-Symbolic Approach · 2026 · 0 citations
- Neuro-Symbolic Learning for Long-Horizon Task Planning Under Complex Logical Constraints · 2026 · 1 citations
- Scaling Neuro-symbolic Problem Solving: Solver-Free Learning of Constraints and Objectives · 2026 · 6 citations
We searched OpenAlex and arXiv for “Implement a neuro-symbolic architecture that restricts language models to parsing shopping constraints and formulating optimization problems using solver libraries to guarantee mathematically optimal product and coupon combinations.” and “Hybrid Neuro-Symbolic Planning for Combinatorial Constraints” and an AI compared the idea with the top 10 results. A small search can miss relevant work.
Source Paper
DeepPlanning: Benchmarking Long-Horizon Agentic Planning with Verifiable ConstraintsYinger Zhang, Shutong Jiang, Renhao Li +6 more · 2026
The paper introduces DEEPPLANNING, a challenging benchmark for evaluating Long-Horizon Agentic Planning (LHAP) in realistic scenarios like multi-day travel and complex shopping. It utilizes a "Layered Task Generation" pipeline to create solvable tasks with strict global constraints (e.g., budgets, schedules) and evaluates agents using code-based verification metrics rather than LLM judges, revealing that even state-of-the-art models struggle with combinatorial optimization and implicit constraint discovery.
Related Ideas
- Neuro-Symbolic Constraint Enforcement ModuleMobilityBench: A Benchmark for Evaluating Route-Planning Agents in Real-World Mobility Scenarios🟠Medium
- Graph-Augmented Episodic Memory for Constraint-Aware Agentic PlanningEnterpriseOps-Gym: Environments and Evaluations for Stateful Agentic Planning and Tool Use in Enterprise Settings🔴Hard
- Strategy-Conditioned Policy for Pre-IMO ProblemsTowards Robust Mathematical Reasoning🟡Fairly easy
- Compressive Memory for Agentic ContextsGLM-5: from Vibe Coding to Agentic Engineering🟠Medium
- Hierarchical Dual-System Architecture for Asynchronous Strategic Deliberation in Real-Time AgentsGamer: A Generalist Vision-Language-Action Foundation Model for Long-Horizon Real-Time Game Agent🟠Medium