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

Tianhao Qian; Guilin Qi; Z. Y. Wu; Ran Gu; Xuanyi Liu; Canchen Lyu

cs.AIMar 8, 2026

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

Authors: Tianhao Qian, Guilin Qi, Z. Y. Wu, Ran Gu, Xuanyi Liu, Canchen Lyu

Organizations: School of Mathematics, Southeast University, Nanjing, China · School of Computer Science and Engineering, Southeast University, Nanjing, China · School of Mathematical Sciences, Chongqing Normal University, Chongqing, China

Abstract

This work investigated the capabilities of different models, including the Llama-3 series of models and CHATGPT, with different forms of expression in solving discrete optimization problems by testing natural language datasets. In contrast to formal datasets with a limited scope of parameters, our dataset included a variety of problem types in discrete optimization problems and featured a wide range of parameter magnitudes, including instances with large parameter sets, integrated with augmented data. It aimed to (1) provide an overview of LLMs' ability in large-scale problems, (2) offer suggestions to those who want to solve discrete optimization problems automatically, and (3) regard the performance as a benchmark for future research. These datasets included original, expanded and augmented datasets. Among these three datasets, the original and augmented ones aimed for evaluation while the expanded one may help finetune a new model. In the experiment, comparisons were made between strong and week models, CoT methods and No-CoT methods on various datasets. The result showed that stronger model performed better reasonably. Contrary to general agreement, it also showed that CoT technique was not always effective regarding the capability of models and disordered datasets improved performance of models on easy to-understand problems, even though they were sometimes with high variance, a manifestation of instability. Therefore, for those who seek to enhance the automatic resolution of discrete optimization problems, it is recommended to consult the results, including the line charts presented in the Appendix, as well as the conclusions drawn in this study for relevant suggestions.

Figures & tables

PROBLEMS	MANUAL	EXPANDED	AUGMENTED
Assignment	60	48	108
1D-Binpacking	960	640	1600
Crew-scheduling	150	100	250
Steiner	980	980	1960
UBQP	135	90	225
CVRP	606	404	1010

Table 3: Statistics on Various Datasets

Fig. 1 : Statistics on the Number of Variables

Error Types	Description
IndexError	Raised when trying to access an index that is out of range for a list or a sequence.
FileNotFoundError	Raised when a file or directory is requested but cannot be found.
OverflowError	Raised when a calculation exceeds the limits of the data type, typically in numeric operations.
NameError	Raised when a local or global name is not found, meaning the variable or function is not defined.
ValueError	Raised when a function receives an argument of the right type but an inappropriate value, such as converting a non-numeric string to an integer.
AttributeError	Raised when an invalid attribute reference is made, meaning the attribute does not exist on the object.

Table 4: Error Types and Descriptions

①Implicit	①Explicit	① $\downarrow$
There are 120 items S and several boxes B with a capacity of 150. The volumes of the 120 items are [BLANK] , and it is given that $s_{i}\leq 150$ ( $1\leq i\leq 120$ ). The packing problem seeks to pack all items into the boxes in such a way that the number of boxes used is minimized. The following table shows the volumes of the items: [BLANK]	There are 120 items S and several boxes B with a capacity of 150. The volumes of the 120 items are $s_{1},s_{2},\ldots,s_{120}$ , and it is given that $s_{i}\leq 150$ ( $1\leq i\leq 120$ ). The packing problem seeks to pack all items into the boxes in such a way that the number of boxes used is minimized. The following table shows the volumes of the items: $x_{1}$ , $x_{2}$ ,…, $x_{119}$ , $x_{120}$
①Implicit-Disorder
The packing problem seeks to pack all items into the boxes in such a way that the number of boxes used is minimized The following table shows the volumes of the items: $x_{1}$ $x_{2}$ … $x_{119}$ $x_{120}s_{120}$ , and it is given that $s_{i}\leq 150$ ( $1\leq i\leq 120$ ) 1.There are 120 items S and several boxes B with a capacity of 150. The volumes of the 120 items are $s_{1},s_{2},$
②CoT Prompting(Optional)		② $\downarrow$
Dealing with 1D bin - packing problems involves several key steps. Here’s a concise outline: 1. Define the Problem: Clearly state the items to be packed (sizes and quantities) and the capacity of the bins. 2. Choose a Strategy: Select a bin - packing algorithm or heuristic (First - Fit, Best - Fit, FFD, BFD). 3. Sort the Items: If using a decreasing strategy, sort the items in descending order. 4. Initialize Bins: Create an empty list or array to represent the bins. 5. Pack the Items: Iterate through the sorted list and place each item into the first suitable bin. 6. Handle Overflows: If an item cannot fit, create a new bin. 7. Track Usage: Record how many bins are used and their contents. 8. Evaluate the Solution: Assess packing efficiency (number of bins used, waste). 9. Optimize (if needed): Explore further optimization techniques. 10. Implement and Test: Run with various inputs to ensure correctness and efficiency.
③Common Prompting		③

Table 5: A case study of 1D-Binpacking problem

Task	Dataset	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Task	Dataset	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
Assignment	Explicit-origin	\	$76.67$	\	\	\	\	\	\
	Implicit-origin	$80.88$	$91.67$	$9.09$	$43.33$	$0.00$	$8.33$	98.33	$85.00$
	Implicit-disorder	\	92.59	$13.89$	$39.81$	$0.93$	$9.26$	\	\
1D-Binpacking	Explicit-origin	\	$83.37$	\	\	\	\	\	\
	Implicit-origin	$64.06$	$75.73$	$55.21$	$12.50$	$3.54$	$8.12$	$80.47$	82.55

Table 6: PR Task Performance Comparison

Task	Dataset	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Task	Dataset	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
Assignment	Explicit-origin	\	$0.00$	\	\	\	\	\	\
	Implicit-origin	$4.41$	10.00	$2.27$	$5.00$	$0.00$	$0.00$	$8.33$	$6.67$
	Implicit-disorder	\	11.11	$0.00$	$4.63$	$0.00$	$0.93$	\	\
1D-Binpacking	Explicit-origin	\	$10.85$	\	\	\	\	\	\
	Implicit-origin	$5.94$	$4.79$	$6.04$	$1.25$	$0.62$	$0.00$	$9.65$	10.07

Table 7: AR Task Performance Comparison

Task	Dataset	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Task	Dataset	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
Assignment	Explicit-origin	\	-	\	\	\	\	\	\
	Implicit-origin	$1.969$	$1.969$	-	$1.876$	$0.00$	0.534	$1.847$	$1.944$
	Implicit-disorder	\	$1.838$	-	$2.276$	-	0.220	\	\
1D-Binpacking	Explicit-origin	\	$0.089$	\	\	\	\	\	\
	Implicit-origin	$0.2284$	0.092	$0.727$	$0.691$	$1.267$	$1.182$	$0.249$	$0.292$

Table 8: MAPE Task Performance Comparison

Task	Error	Reason
Assignment	cost_matrix[i, j] = c	IndexError: index 3301 is out of bounds for axis 1 with size 3000
1D-Binpacking	with open(’data123.txt’, ’r’) as file: S = [float(line.strip()) for line in file]	ValueError: could not convert string to float: ’[ $\ldots$ ]’
Crew-scheduling	cost[i][j] = c	IndexError: list assignment index out of range
Steiner	Timeout	TimeoutError: Operation Timed Out
UBQP	matrix[i][j] = c_ij	IndexError: list assignment index out of range
CVRP	routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, data, True, ’Capacity’ )	TypeError: ’float’ object cannot be interpreted as an integer

Table 9: Error Case Analysis in Common Research Problems

Task	Dataset	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Task	Dataset	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
Assignment	Explicit-origin	\	0.00	\	\	\	\	\	\
	Implicit-origin	0.00	0.00	0.00	3.33	0.00	1.67	1.67	$\overline{\textbf{11.67}}$
	Implicit-disorder	\	$\underline{\textbf{0.93}}$	1.85	1.85	1.85	$\overline{\textbf{2.78}}$	\	\
1D-Binpacking	Explicit-origin	\	11.55	\	\	\	\	\	\
	Implicit-origin	15.00	4.62	6.04	$\underline{\textbf{0.94}}$	2.92	4.17	$\overline{\textbf{16.74}}$	15.10

Table 10: Timeout Task Performance Comparison

Status	Status Descriptions	Problems
Worsened	Disordered datasets are slightly inferior	1D-Binpacking, Crew-scheduling, CVRP
Significantly Worsened	Disordered datasets are greatly inferior	Steiner, UBQP
Improved	Disordered datasets are slightly superior	Assignment, MDVRP, Aircraft Landing, Multi-dimensional Knapsack
Significantly Improved	Disordered datasets are greatly superior	PVRP, Generalised Assignment, Capacitated Warehouse Location, 2D-Cutting Packing-Constrained Guillotine

Table 11: Performance Effectiveness of Different Problems

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Error Type	Dataset	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Error Type	Dataset	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
IndexError	Explicit-origin	\	0.00	\	\	\	\	\	\
	Implicit-origin	24.24	19.57	2.22	9.80	1.03	3.32	0.00	9.09
	Implicit-disorder	\	0.00	22.22	3.70	2.69	2.85	\	\
FileNotFoundError	Explicit-origin	\	9.52	\	\	\	\	\	\
	Implicit-origin	3.03	2.17	0.00	0.00	0.69	1.85	0.00	0.00

Appendix

Table 12: Assignment Problems Performance Metrics

Error Type	Dataset	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Error Type	Dataset	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
IndexError	Explicit-origin	\	0.00	\	\	\	\	\	\
	Implicit-origin	4.23	3.23	7.19	1.24	17.26	2.98	15.94	29.23
	Implicit-disorder	\	8.47	1.70	1.40	14.50	8.02	\	\
FileNotFoundError	Explicit-origin	\	0.00	\	\	\	\	\	\
	Implicit-origin	0.00	0.00	5.12	0.00	5.58	1.75	0.00	2.31

Appendix

Table 13: 1D-Binpacking Problems Performance Metrics

Error Type	Dataset	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Error Type	Dataset	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
IndexError	Explicit-origin	\	30.77	\	\	\	\	\	\
	Implicit-origin	46.40	48.06	19.61	30.47	11.76	7.05	59.78	32.89
	Implicit-disorder	\	33.67	28.46	22.89	34.78	2.62	\	\
FileNotFoundError	Explicit-origin	\	14.62	\	\	\	\	\	\
	Implicit-origin	3.60	6.20	0.00	0.78	0.00	2.12	3.26	0.67

Appendix

Table 14: Crew-scheduling Problems Performance Metrics

Error Type	Dataset	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Error Type	Dataset	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
IndexError	Explicit-origin	\	0.00	\	\	\	\	\	\
	Implicit-origin	4.14	8.55	7.03	4.51	1.39	6.16	0.23	1.35
	Implicit-disorder	\	0.92	13.82	11.09	1.24	1.68	\	\
FileNotFoundError	Explicit-origin	\	0.00	\	\	\	\	\	\
	Implicit-origin	3.45	1.32	0.41	0.16	0.00	0.47	0.00	1.35

Appendix

Table 15: Steiner Problems Performance Metrics

Error Type	Expression	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Error Type	Expression	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
IndexError	Explicit	\	25.53	\	\	\	\	\	\
	Implicit	62.04	47.83	18.18	17.39	0.92	6.16	34.74	60.66
	Implicit-disorder	\	29.04	18.69	14.29	1.99	3.63	\	\
FileNotFoundError	Explicit	\	8.51	\	\	\	\	\	\
	Implicit	10.22	17.39	0.00	0.00	0.15	1.11	0.00	1.64

Appendix

Table 16: UBQP Problems Performance Metrics

Error Type	Expression	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Error Type	Expression	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
IndexError	Explicit	\	10.29	\	\	\	\	\	\
	Implicit	8.52	2.87	2.51	2.30	3.20	3.17	0.39	1.55
	Implicit-disorder	\	4.98	4.31	2.96	1.71	0.44	\	\
FileNotFoundError	Explicit	\	15.04	\	\	\	\	\	\
	Implicit	0.00	1.91	0.00	0.27	2.28	3.49	0.00	0.62

Appendix

Table 17: CVRP Performance Metrics

Error Type	Expression	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Error Type	Expression	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
IndexError	Explicit	\	29.02	\	\	\	\	\	\
	Implicit	4.05	14.12	7.48	0.95	0.31	0.61	6.54	39.61
	Implicit-disorder	\	5.05	7.81	2.51	0.92	0.31	\	\
FileNotFoundError	Explicit	\	6.70	\	\	\	\	\	\
	Implicit	5.41	4.71	0.00	0.00	0.15	1.23	1.87	0.48

Appendix

Table 18: MDVRP Performance Metrics

Error Type	Expression	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Error Type	Expression	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
IndexError	Explicit	\	2.14	\	\	\	\	\	\
	Implicit	7.97	5.47	1.66	2.11	0.16	0.64	0.00	1.14
	Implicit-disorder	\	3.02	5.09	3.65	0.29	0.68	\	\
FileNotFoundError	Explicit	\	0.00	\	\	\	\	\	\
	Implicit	3.62	2.34	0.00	0.00	0.48	0.48	0.00	0.00

Appendix

Table 19: PVRP Performance Metrics

Error Type	Dataset	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Error Type	Dataset	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
IndexError	Explicit-origin	\	13.00	\	\	\	\	\	\
	Implicit-origin	3.33	2.60	2.38	1.37	0.93	0.00	9.52	50.00
	Implicit-disorder	\	0.74	5.56	3.57	2.30	0.70	\	\
FileNotFoundError	Explicit-origin	\	4.00	\	\	\	\	\	\
	Implicit-origin	0.00	0.00	0.00	0.00	1.40	0.00	0.00	0.00

Appendix

Table 20: Aircraft Landing Problems Performance Metrics

Error Type	Dataset	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Error Type	Dataset	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
IndexError	Explicit-origin	\	60.80	\	\	\	\	\	\
	Implicit-origin	12.98	9.15	13.41	17.95	1.15	2.31	41.67	37.80
	Implicit-disorder	\	3.85	9.25	12.80	3.21	4.24	\	\
FileNotFoundError	Explicit-origin	\	8.52	\	\	\	\	\	\
	Implicit-origin	2.67	5.23	8.94	1.03	0.46	0.93	0.00	0.00

Appendix

Table 21: Generalised Assignment Problems Performance Metrics

Error Type	Dataset	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Error Type	Dataset	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
IndexError	Explicit-origin	\	37.62	\	\	\	\	\	\
	Implicit-origin	26.28	22.61	6.58	6.41	3.38	4.22	15.88	16.22
	Implicit-disorder	\	17.59	4.16	4.87	3.66	2.97	\	\
FileNotFoundError	Explicit-origin	\	0.99	\	\	\	\	\	\
	Implicit-origin	1.53	1.01	0.12	0.38	6.39	5.84	0.00	0.00

Appendix

Table 22: Multi-dimensional Knapsack Problems Performance Metrics

Error Type	Dataset	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Error Type	Dataset	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
IndexError	Explicit-origin	\	43.98	\	\	\	\	\	\
	Implicit-origin	23.51	26.09	0.00	6.29	1.03	1.21	31.47	17.88
	Implicit-disorder	\	21.05	1.81	2.94	1.21	1.19	\	\
FileNotFoundError	Explicit-origin	\	4.71	\	\	\	\	\	\
	Implicit-origin	0.37	3.56	0.00	0.00	1.23	0.60	0.00	1.12

Appendix

Table 23: Capacitated Warehouse Location Problems Performance Metrics

Error Type	Dataset	GPT-4o-mini		LLAMA3-8B		ORLM		DeepSeek-R1
Error Type	Dataset	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT	PoT	PoT+CoT
IndexError	Explicit-origin	\	0.00	\	\	\	\	\	\
	Implicit-origin	16.67	10.00	2.51	0.00	0.00	0.00	15.91	3.32
	Implicit-disorder	\	3.23	6.90	0.00	0.00	6.90	\	\
FileNotFoundError	Explicit-origin	\	0.00	\	\	\	\	\	\
	Implicit-origin	0.00	0.00	0.00	0.00	1.18	1.18	0.00	1.85

Appendix

Table 24: 2D-cutting packing-constrained guillotine Problems Performance Metrics

Fig. 2 : AR/PR Ratio Across Specified Parameter Range with DeepSeek-Implicit on Different Problems

Fig. 3 : AR/PR Ratio Across Specified Parameter Range with LLAMA3-Implicit on Different Problems

Fig. 4 : AR/PR Ratio Across Specified Parameter Range with GPT-4o-mini-CoT-Implicit on Different Problems

Fig. 5 : AR/PR Ratio Across Specified Parameter Range with LLAMA3-CoT-Implicit-Disorder on Different Problems

LLM Evaluation

Large language model evaluation measures what models can do, how reliably they do it, and whether benchmark scores predict real-world performance.

See all 2,408 papers

Right Answers, Costly Models: The Efficiency Gap in LLM-based Optimization Modeling
Sep 30, 2026Zhong Li, Xin Huang, Jinhui Wan +6LLM Evaluation Large Language Model-Guided Optimization
Great Bay University · Beijing Jiaotong University · Beihang University +1
OptiMUS-0.3: Using Large Language Models to Model and Solve Optimization Problems at Scale
Jul 29, 2024Ali AhmadiTeshnizi, Wenzhi Gao, Herman Brunborg +3Mixed-Integer Linear Programming Large Language Model-Guided Optimization
a School of Management Science and Engineering, Stanford University, Stanford, California 94305 · b Institute for Computational and Mathematical Engineering, Stanford University, Stanford, California 94305
Large Language Models as Optimizers: A Survey of Direct vs. Tool-Augmented Approaches and Their Performance Frontiers
Apr 9, 2026Roko Peran, Luka Hobor, Mihael Kovac +1Large Language Model-Guided Optimization Natural Language to Optimization Modeling
Student at University of Zagreb Faculty of Electrical Engineering and Computing, Zagreb, Croatia · University of Zagreb Faculty of Electrical Engineering and Computing, Zagreb, Croatia

Sep 30, 2026J/K move · Enter open · S save

Right Answers, Costly Models: The Efficiency Gap in LLM-based Optimization Modeling

Zhong Li, Xin Huang, Jinhui Wan, Xiangyi Wang+5

Great Bay University · Beijing Jiaotong University · Beihang University+1

LLM Evaluation Large Language Model-Guided Optimization Natural Language to Optimization Modeling

Open paper AskPDF arXiv

Optimization modeling formulates real-world decision problems as mathematical programs that solvers can use to find optimal decisions. Large language models (LLMs) can automate this process, but the resulting correct formulations can require substantial time and memory to construct and solve, limiting practical scalability. Therefore, we systematically investigate whether LLMs can identify problem structure from natural-language descriptions and apply suitable optimization modeling techniques to generate mathematical models and solver code that solve the problems correctly and efficiently. To this end, we first curate OptTips, a knowledge base of 50 expert modeling techniques in eight families. Using this knowledge, we develop OptDachshund, a multi-agent framework that transforms problems from existing optimization benchmarks into new tasks for evaluating LLMs' use of modeling techniques. It constructs conventional and expert mathematical models with solver code for the same task and data, providing baselines for correctness and computational cost. The resulting EfficientOpt benchmark contains 561 expert-reviewed tasks with paired reference implementations. Evaluation of 11 representative LLMs reveals an efficiency gap on correctly solved tasks with comparable measurements: for every LLM, most generated programs take longer to solve than their expert counterparts. Within the comparable reference-size subset, 57% of programs with correct objective values and fewer variables and linear constraints have longer recorded solver times. Case studies show that different modeling techniques can achieve the same optimal value at similar recorded cost. Faster solving may not reduce execution time if the code takes longer to prepare data and build the model. LLM optimization modeling should therefore be evaluated for both correctness and computational efficiency.

Abstract

LLM Evaluation

Explore similar work

Right Answers, Costly Models: The Efficiency Gap in LLM-based Optimization Modeling

OptiMUS-0.3: Using Large Language Models to Model and Solve Optimization Problems at Scale

Large Language Models as Optimizers: A Survey of Direct vs. Tool-Augmented Approaches and Their Performance Frontiers