Large Language Model for Discrete Optimization Problems: Evaluation and Step-by-step Reasoning

This paper evaluates the capabilities of various large language models, including Llama-3 and ChatGPT, in solving diverse discrete optimization problems using natural language datasets, revealing that while stronger models generally perform better, Chain-of-Thought reasoning is not universally effective and data augmentation can improve performance on simpler tasks despite introducing instability.

The Gist

Imagine you have a team of super-smart AI assistants (Large Language Models, or LLMs) and you want to see if they can act like master logistics managers. Your goal is to solve complex puzzles like: "How do we pack 1,000 boxes into the fewest trucks?" or "How do we schedule 500 airline crews so everyone gets a break and no one is overworked?"

This paper is essentially a report card for these AI assistants. The researchers didn't just ask them simple math questions; they threw a massive, chaotic variety of real-world "discrete optimization" problems at them to see who could actually get the job done.

Here is the breakdown of their findings, using some everyday analogies:

1. The Test: A "Stress Test" for Brains

The researchers built a giant test bank with 13 different types of puzzles (from packing boxes to landing planes).

• The "Original" Test: The problems were written clearly, like a standard instruction manual.
• The "Expanded" Test: They changed the story behind the problems (e.g., instead of "packing boxes," it's "packing groceries for a party") to see if the AI could understand the logic regardless of the story.
• The "Disordered" Test: This is the crazy part. They took the instructions and scrambled the sentences. Imagine reading a recipe where the sentence "Preheat the oven" comes after "Take the cake out of the oven." They wanted to see if the AI was actually thinking or just memorizing patterns.

2. The Contenders: The "Geniuses" vs. The "Students"

They tested four different AI models:

• The Geniuses (Strong Models): GPT-4o-mini and DeepSeek-R1. These are the top-tier brains.
• The Students (Weak Models): LLaMA-3-8B and ORLM. These are smaller, less powerful models.

They also tested two study methods:

• No-CoT (The "Gut Feeling" approach): The AI just tries to solve it immediately.
• CoT (Chain-of-Thought): The AI is forced to say, "Step 1, Step 2, Step 3..." before giving the answer. It's like asking a student to "show their work."

3. The Big Surprises (The Results)

🚨 Surprise #1: "Show Your Work" (CoT) isn't always helpful.

You'd think forcing a smart AI to "show its work" (CoT) would always make it smarter. Not true.

• For the Geniuses: Sometimes, forcing them to think step-by-step actually slowed them down or made them mess up. They sometimes solved it better by just "knowing" the answer.
• For the Students: Forcing them to show work often made them worse. They got confused by the extra steps and gave up.
• The Lesson: You can't use the same study guide for a genius and a student.

🚨 Surprise #2: Scrambling the instructions sometimes helped the geniuses.

This is the weirdest part. When the researchers scrambled the sentences (the "Disordered" test), the stronger models actually got better at some problems!

• Why? The researchers think it's like a Bayesian update (a fancy way of saying "updating your guess based on new info").
• The Analogy: Imagine you are guessing a word in a game. If I tell you the definition after giving you the clues, you might guess wrong. But if I tell you the definition first, your brain instantly filters out the wrong guesses.
• By scrambling the text, the "goal" of the problem (e.g., "minimize cost") sometimes appeared earlier in the prompt. This gave the smart AI a head start, helping it ignore the noise. However, this made the results unstable—sometimes they were brilliant, sometimes they crashed.

🚨 Surprise #3: The "Weak" models struggled with the "Scrambled" test.

The smaller, weaker models got completely lost when the sentences were mixed up. They relied on the order of the words to make sense of things. If you scrambled the recipe, they couldn't bake the cake.

4. The "Error Report"

The paper also looked at how the AIs failed.

• The "Typo" Errors (Syntax): The AI wrote code that looked like English but had a missing bracket, like a sentence without a period.
• The "Confused" Errors (IndexError/ValueError): The AI tried to grab a box from a shelf that didn't exist, or tried to divide a word by a number.
• The "Timeout" Errors: The AI got stuck in a loop, thinking too hard, and the computer shut it down after 5 minutes.

5. The Final Advice (The "Cheat Sheet")

If you want to use an AI to solve these logistics puzzles, here is what the paper recommends:

1. Know your AI:

   • If you have a Strong AI (like GPT-4 or DeepSeek): Try giving it the problem with scrambled sentences (if you want to push its limits) or use Chain-of-Thought (if you want stability).
   • If you have a Weak AI (like LLaMA): Do not scramble the sentences. Give it a clear, normal instruction. Do not force it to "show its work" step-by-step; just let it try to solve it directly.

2. Know your Problem:

   • Some problems (like packing boxes) are easy for AIs.
   • Some problems (like scheduling airline crews) are very hard, and even the smartest AIs struggle to find the perfect answer, though they can find a "good enough" one.

The Bottom Line

This paper is a reality check. It tells us that bigger AI models aren't automatically better at everything, and forcing them to "think" isn't always the right strategy.

It's like hiring a team: You don't give the same instructions to a senior engineer and a new intern. You have to tailor how you ask the question based on who is answering and what the problem is. The researchers built a massive library of these problems so that in the future, we can pick the right AI and the right prompt to solve our real-world logistics nightmares.

Technical Summary

Here is a detailed technical summary of the paper "Large Language Model for Discrete Optimization Problems: Evaluation and Step-by-step Reasoning."

1. Problem Statement

The paper addresses the capability of Large Language Models (LLMs) to solve Discrete Optimization Problems (DOPs), a core component of Operations Research (OR). While LLMs have shown promise in natural language processing and basic mathematics, their performance on complex, large-scale DOPs (e.g., Vehicle Routing, Bin Packing, Scheduling) remains under-explored.

Key challenges identified include:

• Scale and Complexity: Existing benchmarks often lack large parameter sets or diverse problem types.
• Reasoning vs. Decision Making: Previous works focused on continuous reasoning but failed to test decision-making capabilities in constrained optimization.
• Input Sensitivity: It is unclear how LLMs handle variations in problem narration (e.g., explicit vs. implicit, ordered vs. disordered text) and whether they rely on pattern matching rather than true understanding.
• Methodology Gaps: There is a lack of systematic evaluation regarding prompt engineering techniques (Chain-of-Thought, Program-of-Thought) and their impact on solution quality, execution success, and timeout rates.

2. Methodology

A. Dataset Construction

The authors constructed a comprehensive benchmark dataset comprising 13 types of discrete optimization problems (including Assignment, 1D-Binpacking, CVRP, MDVRP, Steiner, UBQP, Aircraft Landing, etc.). The dataset was created in three distinct forms to test robustness:

1. Original: Natural language descriptions derived from OR-Library and VRP datasets, manually annotated by experts.
2. Expanded: Background contexts were automatically extracted and creatively expanded using GPT-4o-mini to create domain-specific scenarios, aiming to test generalization.
3. Augmented (Disordered): Sentences within the problem descriptions were randomly shuffled. This was designed to test if LLMs rely on semantic logic or mere pattern matching.

The dataset includes a wide range of parameter magnitudes (variable counts), from small to large-scale instances.

B. Models and Techniques Evaluated

The study compared four models with varying capabilities:

• Strong Models: GPT-4o-mini, DeepSeek-R1 (known for strong mathematical reasoning).
• Weaker Models: LLAMA3-8B-Instruct, ORLM (a model fine-tuned on LLAMA3-8B for OR tasks).

Two prompting strategies were tested:

• Program-of-Thought (PoT): The LLM generates code (Python) to solve the problem, which is then executed.
• Chain-of-Thought (CoT): The LLM generates intermediate reasoning steps before generating the code.

C. Evaluation Metrics

Four key indicators were used to assess performance:

1. Pass Rate (PR): Percentage of generated code that executes successfully without syntax or runtime errors.
2. Accuracy Rate (AR): Percentage of solutions that reach or surpass the optimal result (minimization/maximization).
3. Mean Absolute Percentage Error (MAPE): Measures the deviation of the solution from the optimal value.
4. Timeout Rate (TR): Percentage of solutions that fail to complete within a 300-second limit.

3. Key Contributions

1. New Benchmark Dataset: Introduction of a large-scale, natural-language dataset covering 13 diverse DOP types with original, expanded, and disordered variants. This allows for rigorous testing of LLMs on large-scale optimization.
2. Comprehensive Comparative Analysis: A systematic evaluation of strong vs. weak models and CoT vs. No-CoT strategies across four distinct metrics.
3. Insight into Input Sensitivity: Discovery that disordered datasets (shuffled sentences) can paradoxically improve performance for strong models on certain "easy-to-understand" problems by forcing the model to focus on the optimization goal earlier in the context, though this introduces high variance.
4. Error Taxonomy: A detailed classification of error types (IndexError, ValueError, SyntaxError, etc.) specific to different problem types and model capabilities, providing a roadmap for debugging LLM-generated optimization code.
5. Strategic Guidelines: Concrete recommendations on which model and technique to select based on problem difficulty and type.

4. Key Results

• Model Performance: Stronger models (DeepSeek-R1, GPT-4o-mini) consistently outperformed weaker models (LLAMA3-8B, ORLM) in both Pass Rate and Accuracy.
• Impact of CoT:
  • Strong Models: CoT did not universally improve performance. For some problems, it helped; for others, it introduced complexity that led to errors.
  • Weak Models: CoT generally degraded performance, as weaker models struggled to maintain consistency across the multi-step reasoning required by CoT.
• Impact of Disordered Data:
  • Strong Models: Surprisingly, disordered datasets often improved Pass Rates and Accuracy for strong models on problems like Generalized Assignment and Capacitated Warehouse Location. The authors hypothesize this is due to Bayesian posterior updates where the optimization objective is presented earlier, refining the model's probability distribution.
  • Weak Models: Disordered data generally harmed performance, increasing instability and error rates.
• Error Analysis:
  • Assignment Problems: Most prone to ValueError (data type mismatches).
  • Crew Scheduling: High incidence of IndexError due to complex matrix operations.
  • Steiner & VRP: Prone to SyntaxError and TypeError (incorrect solver usage).
  • Timeouts: No-CoT approaches often led to higher timeout rates due to inefficient algorithm selection (e.g., dynamic programming on large datasets).
• Problem Difficulty Correlation: The study categorized problems by difficulty. "Hard" problems (Steiner, UBQP) benefited significantly from CoT, while "Easy" problems (1D-Binpacking, Assignment) sometimes performed better with disordered inputs or without CoT.

5. Significance and Recommendations

This work provides a critical benchmark for the future of automated Operations Research. It challenges the assumption that "more reasoning steps" (CoT) always equals better results, showing that the effectiveness of prompting strategies is highly dependent on the model's base capability and the specific problem type.

Practical Recommendations for Practitioners:

• For Strong Models: Use CoT for complex, hard-to-understand problems (e.g., Steiner, VRP). For easier problems, consider disordered datasets to potentially boost performance, but be aware of the increased variance.
• For Weak Models: Avoid CoT. Use original, ordered datasets with PoT (No-CoT) for the most stable results.
• Strategy Selection: If the goal is a feasible solution within a time limit, CoT on original datasets is the safest bet. If the goal is the absolute optimal solution and the model is strong, experimenting with disordered datasets may yield better results despite the risk of instability.
• Future Research: The paper suggests that future OR-specific LLMs should be fine-tuned on diverse, augmented datasets to improve robustness against input variations and reduce reliance on pattern matching.

In conclusion, the paper establishes that while LLMs are becoming viable tools for discrete optimization, their deployment requires careful selection of models, prompting strategies, and data formatting based on the specific characteristics of the optimization problem.