2608.07040-Not All Problems Are Best Modeled as MILP: ADSL-Centric Framework for Flexible and Accurate Optimization Modeling

Introduction to the show: ident: Paper Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Not All Problems Are Best Modeled as MILP: ADSL-Centric Framework for Flexible and Accurate Optimization Modeling".

Jane: The paper was written by Shaofeng Zhang, Hongyuan Su, Shengcai Liu, Ke Tang, Qingwen Peng et al. from Southern University of Science and Technology and Tsinghua University and Tianjin University and Zhongguancun Academy.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Paper summary: Tom: We just finished a paper that swings a sledgehammer at a field-wide assumption. Everyone building LLM tools for optimization assumes the output has to be a mixed-integer linear program.

Jane: This team says that assumption is exactly what's failing. They built OptiDSL, which maps natural language into the domain-specific formats optimization practitioners already use.

Lu: The numbers are hard to ignore. Across 44 problem types, they report a 51.66 percent gain in formulation accuracy and a 91.71 percent cut in modeling time.

Meng: They also beat MILP pipelines on existing benchmarks by 23.09 percent in formulation accuracy. So this isn't just a win on their own turf.

Tom: The example that sold me is almost comically small. One depot, three customers, one vehicle with capacity sixteen.

Jane: Go on.

Tom: The MILP version still needs a tangle of variables plus subtour-elimination constraints, while the DSL version is a plain text file with a distance matrix and a demand section. Night and day.

Lalam: That's the deeper thesis. Forcing every problem into one universal math format adds complexity that doesn't belong to the problem itself.

Lu: It also locks you into the slow exact solvers. The fast heuristics and neural methods all speak DSL, so MILP pipelines can't touch them.

Meng: Their benchmark spans routing, scheduling, bin packing, graph problems, and knapsack — 4,400 instances.

Tom: The framework routes each instance to a specialized solver depending on whether you want speed or solution quality.

Jane: I keep circling back to the central claim. Not every optimization problem wants to be a MILP, and forcing it makes the modeling worse.

Lalam: That reframes what the LLM should do. Instead of generating mathematical machinery, it fills standardized templates.

Lu: The template point explains the modeling time collapse. Filling in fields beats generating theorems line by line.

Meng: I'm curious how they pick the right template without tripping on unusual constraints.

Tom: The machinery for that starts on page one.

Page 1: Jane: Page one frames the battle. The paper calls formulation the "overlooked challenge" in combinatorial optimization.

Tom: Everyone studies solving algorithms, but getting a problem into solver-ready form is still manual, slow, and error-prone. That's the real bottleneck.

Lu: LLMs were supposed to automate that translation. Feed in plain English, get back a formal model, hand it to Gurobi, done.

Meng: Except the automation assumed MILP was the only destination. The paper lists two failure modes for that assumption.

Jane: First, modeling complexity. Capacitated vehicle routing is the canonical victim — the MTZ formulation needs constraints that explode with problem scale.

Tom: Wait, exponential growth? Already?

Jane: The growth is dramatic even on small instances, and an LLM has to write every constraint by hand. Context window fills, accuracy nosedives.

Lu: Second, solver rigidity. MILP output can only feed MILP solvers. You're shut out of the fast heuristics and neural methods that dominate large-scale practice.

Meng: So even a flawless MILP formulation under-serves you. Slow solver, limited scale, and a mountain of constraints to generate.

Tom: OptiDSL's answer is to use DSLs as the intermediate representation. VRPLIB for routing, OR-Library formats for packing — the formats the domain already speaks.

Jane: They call it decoupling problem formulation from solver execution. The representation stops dictating the algorithm.

Lalam: That's a genuinely different philosophy. The LLM becomes a translator between human language and an established data standard.

Lu: And almost every specialized solver natively consumes those standards, so the integration barrier just vanishes.

Meng: The abstract promises a 51.66 percent accuracy gain, but at this point it's only a claim.

Jane: Page two gives the visual proof — the same routing problem rendered as a five-element MILP and as a bare DSL file.

Tom: That figure is the whole paper in miniature.

Page 2: Tom: So page two delivers that figure, and it's a knockout. The same problem statement, two radically different translations.

Jane: The MILP side shows the classic five-element structure — sets, parameters, variables, objective, constraints. You get route decision variables, auxiliary visit-order variables, and cumulative load variables.

Lu: Then the constraints stack on top. Visit and leave constraints, MTZ subtour elimination, load bounds. All to stop a truck from looping in a circle.

Meng: And this is a four-node problem. The complexity only compounds as the instance grows.

Tom: The DSL side is a flat data file. DIMENSION four, CAPACITY sixteen, an explicit distance matrix, a demand section, a depot marker, end of file.

Jane: The LLM doesn't generate mathematical relationships. It extracts numbers and slots them into fixed fields.

Lu: That's why modeling time drops by over ninety percent. Filling a template is a far lighter task than writing a theorem.

Meng: And structural errors have nowhere to hide. The template syntax catches what the LLM might mangle.

Tom: The contributions section then lists three pillars: the DSL workflow, a 44-type benchmark, and the evaluation suite.

Jane: I also like how they frame related work. Exact MILP solvers guarantee optimality but scale terribly; flexible solvers are fast but demand domain-specific inputs.

Lu: So the field had an integration barrier. The fast tools couldn't plug into automated text-to-model pipelines.

Meng: OptiDSL makes the DSL the universal handshake, and that unlocks the fast tools for the first time.

Tom: There's a subtle point too — they argue these DSLs are foundational. Adding time windows to a base CVRP template gives you a new problem variant almost for free.

Jane: That extensibility is what makes 24 VRP variants tractable rather than terrifying.

Lu: The formal problem statement on page three lays out exactly which domains they target.

Tom: Let's see the menu.

Page 3: Jane: Page three gives the genealogy. NL4Opt started the text-to-MILP direction, and Chain-of-Experts brought multi-agent cooperation for the hard cases.

Tom: ORLM attacked data scarcity by synthesizing training examples, while LLMOPT unified instruction tuning with self-correction.

Lu: But every one of those pipelines ends at the same place — a MILP formulation. The destination never changes.

Meng: The paper calls that an expressive bottleneck. Complex combinatorics, like subtour elimination, resist clean linear encoding.

Tom: And the second limitation is the solver dead end. MILP output precludes the specialized algorithms that actually scale.

Jane: Then comes their formal setup: given natural language, automate formulation and solution, with a DSL file as the output target.

Lu: I appreciate the observation that problem families already have their own standards. The formats exist; LLM pipelines just weren't using them.

Meng: The domain coverage is the impressive part. Twenty-four VRP variants built from flags — open routes, backhauls, mixed backhauls, duration limits, time windows.

Tom: Those flags combine into monsters like open VRP with backhaul, duration limit, and time windows together. That's realistic messiness.

Jane: Scheduling brings six classics, from job shop to assembly scheduling. Bin packing gives eight variants crossing 2D, three dee, and rotation constraints.

Lu: Graph problems contribute maximum independent set, minimum vertex cover, max cut, and max clique. Knapsack adds 0-1, bounded, unbounded, and multidimensional forms.

Meng: Forty-four types, five domains. The breadth is deliberate — the whole argument is that one format can't fit everything.

Tom: And the solver pool on page four shows what they plug all of this into.

Page 4: Meng: The solver pool on page four reads like a who's who. Gurobi and LKH, PyVRP and OR-Tools, CP-SAT and dispatching rules.

Jane: Genetic algorithms cover bin packing, dynamic programming covers knapsack, and the learning side brings RouteFinder, MatNet, DANIEL, POMO, DiffUCO, and FastT2T.

Tom: Each expects a particular input format. That's precisely why a universal MILP bridge never worked.

Lu: The architecture splits into three parts: DSL-based formulation, adaptive solver execution, and benchmark evaluation.

Meng: The formulation stage has a clever routing trick. Instead of loading every template's syntax into context, the LLM first reads short meta-descriptions and selects one template.

Tom: That kills context bloat early. No reason to carry twenty grammar books when you only need one.

Jane: Then instantiation goes beyond data extraction. Their example: "vehicles are not required to return to the depot" becomes OPEN_ROUTE set to TRUE.

Lu: The model has to deduce a boolean flag from a natural phrase. That's genuine semantic inference.

Meng: And the templates extend. Standard CVRP plus time window fields becomes CVRPTW.

Tom: That extensibility explains how 24 VRP variants stay manageable — they're mutations of one base format.

Jane: The execution side profiles every solver offline on representative instances, building multi-dimensional performance profiles.

Lu: Exact solvers ace optimality but eat time; neural solvers flip the trade. The profiles trace a Pareto front for each domain.

Meng: At run time, the router consults those profiles plus the user's stated preference — speed or quality — to choose the solver.

Tom: The same DSL file can go to Gurobi for a tiny instance or RouteFinder for a massive one.

Jane: That's the flexibility MILP pipelines structurally cannot offer.

Lu: Next page explains how they built the benchmark without hallucinated data ruining it.

Page 5: Jane: Benchmark construction here is methodical. Three stages: generate, check and modify, then substitute data placeholders.

Tom: The generation stage has the LLM expand seed scenarios into novel descriptions, with explicit bans on duplicate titles.

Lu: The check stage is the anti-hallucination firewall. A checking agent verifies each scenario logically matches its formal COP definition.

Meng: Invalid scenarios get manually revised based on the agent's rationale, and valid ones face random sampling audits.

Tom: The placeholder trick is subtle. The LLM writes scenarios using tags like ⟨demand⟩, and the actual numerical data gets filled separately.

Jane: That separation is smart because LLMs are unreliable at generating consistent numeric tables. You decouple structure from numbers.

Lu: The experimental setup then pins down the comparison. Baselines are Chain-of-Experts, ORLM, and LLMOPT — the three main MILP paradigms.

Meng: OptiDSL and Chain-of-Experts run on DeepSeek-V3.2, while ORLM uses fine-tuned Llama3 and LLMOPT runs Qwen2.5-14B.

Tom: Everyone shares Gurobi as the downstream solver, which isolates formulation quality from solver differences.

Jane: Metrics are execution rate and optimality rate. Did it parse, and did it hit the optimum.

Lu: Problem sizes stay small — five nodes for VRP, ten elsewhere — so true optima are computable.

Meng: That actually makes the comparison conservative. MILP solvers handle tiny instances easily.

Tom: So any advantage has to come from the formulation itself rather than solver power.

Jane: And the results table on the next page shows exactly that advantage.

Page 6: Jane: The results table is the payoff. On average, OptiDSL lifts execution rate by 10.13 percent and optimality rate by 51.66 percent over the baselines.

Tom: VRP shows the widest gap. Execution rate up 13.05 percent, optimality rate up 68.83 percent relative to the MILP pipelines.

Lu: Put that in context. The best baseline across the VRP variants lands at 11.79 percent optimality.

Meng: Really? Under twelve percent?

Lu: Right. OptiDSL stays above 80 percent optimality in every domain it touches.

Tom: Modeling time drops from an average of 69.52 seconds per problem to 9.89 seconds.

Jane: Token consumption falls too, because a DSL data file is far more compact than a mathematical model.

Meng: The scalability test then pushes CVRP up to fifty nodes. At that scale, OptiDSL still executes 84 percent of instances; the best baseline manages 76 percent.

Lu: And at ten nodes, the optimality comparison is stark — around 75 percent for OptiDSL versus 9 percent for the strongest baseline.

Tom: That's the exponential constraint explosion showing up exactly where the paper predicted.

Jane: Then they test on an existing benchmark from LLMCoSolver, covering CVRP, job shop, MIS, and vertex cover. Data they didn't create.

Meng: OptiDSL reaches an execution rate of 0.94 and optimality of 0.89 there, beating the strongest baselines by 10.96 percent and 23.09 percent.

Lu: So the advantage transfers off their own benchmark, which strengthens the whole paper.

Tom: The VRP gain of 68.83 percent in optimality is the most striking number in the results section.

Jane: Next page shows the MILP-native benchmarks and the solver trade-off analysis.

Page 7: Jane: Page seven opens with the modeling time and token consumption charts, which visually confirm the efficiency story.

Tom: Then comes the sharpest test — the MILP-native benchmarks, NL4Opt, MamoComplex, and NLP4LP.

Lu: Those datasets are built for MILP formulations. If the baselines have a home turf advantage, this is it.

Meng: OptiDSL posts 100 percent optimality on NL4Opt and NLP4LP, and 89.6 percent on MamoComplex — 26 correct out of 29.

Tom: The average optimality rate lands at 92.3 percent, beating Chain-of-Experts by 10.2 points, ORLM by 32.3, and LLMOPT by 43.6.

Jane: Even on the opponents' home field, the DSL approach wins. That's a serious blow to the "MILP is the only standard" position.

Lu: Then the downstream solver analysis shows why decoupling pays. Gurobi solves tiny CVRP instances in about half a second, but at fifty nodes it's over 200 seconds.

Meng: PyVRP handles a hundred nodes in 25.6 seconds, landing an objective of 14.58.

Tom: RouteFinder does the same hundred nodes in 0.56 seconds with a 14.98 objective. Slightly worse answer, far faster.

Jane: So the user chooses. Need proof of optimality on small cases? Gurobi. Need near-optimal at scale? PyVRP. Need real-time? RouteFinder.

Lu: A MILP-only pipeline can't make that choice. You're married to exponential cost whether you like it or not.

Meng: The paper's conclusion then restates the package: DSL formulation, 44-type benchmark, solver flexibility, and drastic efficiency gains.

Tom: The references on the next page are worth a close read. They map the whole competitive landscape.

Page 8: Jane: Page eight is all references, but this list is a strategic map. Every major text-to-MILP system gets cited and then displaced.

Tom: NL4Opt, OptiMUS, ORLM, LLMOPT, Chain-of-Experts — the full lineage of the paradigm they're arguing against.

Lu: The Miller-Tucker-Zemlin paper from 1960 anchors the critique. A technique older than most readers is the exact bottleneck they sidestep.

Meng: And the solver citations span decades too — LKH from the nineties, OR-Tools, Gurobi, PyVRP, RouteFinder.

Tom: The neural solver citations are equally telling. POMO, MatNet, DIFUSCO, DiffUCO, FastT2T all need structured inputs.

Jane: Those structured inputs are precisely what DSL files provide. The reference list doubles as an argument for the architecture.

Lu: I also notice the benchmark heritage. VRPLIB, OR-Library, Network Repository — they borrowed established formats instead of inventing new ones.

Meng: That's the adoption strategy. No one has to learn a new standard; the formats are already in production.

Tom: And the hallucination literature gets cited, which explains their obsessive benchmark checking pipeline.

Jane: The dataset statistics tables in the supplement show why that care mattered. 4,400 samples, averaging over 33 parameters each — the largest and densest of the group.

Lu: The supplementary pages also profile every solver in the pool, which tells you exactly what each execution strategy costs.

Tom: Those profiles turn the trade-off table from abstract into concrete.

Page 9: Meng: The supplementary opens with a full profile of the non-learning solvers. LKH uses edge-exchange local search; PyVRP is built specifically for VRP variants.

Jane: OR-Tools is the generalist toolkit, CP-SAT blends constraint programming with SAT, and Gurobi brings branch-and-bound and cutting planes.

Tom: Genetic algorithms and dispatching rules cover the fast-and-dirty end, while dynamic programming serves the knapsack family.

Lu: The learning side gets equal detail. RouteFinder trains across 48 VRP variants using mixed batch training and reward normalization.

Meng: PCT structures three dee bin packing as a configuration tree, which is a beautifully concrete idea.

Tom: L2D learns dispatching policies for job shops, DANIEL uses dual attention networks, MatNet does matrix-based encoding, GOAL is order-agnostic.

Jane: FastT2T and DiffUCO aim at unified combinatorial optimization with transformers and diffusion. POMO explores multiple optima in parallel.

Lu: The key fact is that all of them consume the same DSL file. One representation, a dozen execution strategies.

Meng: That's the payoff of the decoupling design, spelled out in detail.

Tom: It also makes the trade-off table from earlier concrete — the reader now knows exactly what each solver's profile means.

Jane: I want to see how their dataset statistics hold up against the existing benchmarks.

Lu: That comparison comes next, and it shows OptiDSLBench is the largest of the group.

Conclusion: Tom: So what do we take away from this paper? The central claim — not all problems are best modeled as MILP — is backed by hard numbers.

Jane: A 51.66 percent gain in formulation accuracy, a 91.71 percent reduction in modeling time, and a 23.09 percent improvement on existing benchmarks.

Lu: The OptiDSL framework treats DSLs as the interface between natural language and a diverse solver ecosystem.

Meng: The benchmark spans 44 problem types and 4,400 instances, and the transfer results show the approach generalizes.

Tom: The scalability experiments show the advantage grows with problem size, exactly where MILP pipelines break down.

Jane: And the solver analysis demonstrates real flexibility — exact solvers, heuristics, and neural methods all reachable from one DSL file.

Lalam: The broader lesson extends beyond optimization. LLMs perform best when they emit formats the existing ecosystem already consumes.

Lu: That principle applies to code generation, scientific computing, and data analysis. Match the representation to the domain.

Meng: The open questions are also obvious. How does the template pool extend to brand-new problem types with no established format?

Tom: And can the DSL generation hold up at industrial scale, where instances are dense and constraints are messy?

Jane: For now, the paper makes a convincing case that representation flexibility beats mathematical rigidity.

Tom: Strong discussion. Let's clear the table for the next paper.