Organizations: Lehigh University, Bethlehem, PA 18015, USA · Department of Computer Science, University of Pittsburgh, Pittsburgh, PA 15260, USA · Johnson & Johnson, New Brunswick, NJ 08933, USA
Large language models (LLMs) are increasingly explored for NP-hard combinatorial optimization problems, but most existing methods emphasize feasible-instance solution generation and do not explicitly address infeasibility detection. We propose an infeasibility-aware framework that combines certifiable dataset construction, supervised fine-tuning, and LLM-assisted downstream search. For the minor-embedding problem, we introduce a new mathematical programming formulation together with provable zero-phase infeasibility screening, which enables scalable construction of training instances labeled either as feasible with structured certificates or as certifiably infeasible. Using training data generated through this exact optimization pipeline, we show that an 8B-parameter LLM can be fine-tuned to jointly perform solution generation and infeasibility detection. We further utilize LLM outputs as warm starts for downstream local search, providing a practical way to accelerate optimization even when the LLM outputs are imperfect. Experiments show that our fine-tuned model improves overall accuracy by up to 30% over GPT-5.2; meanwhile LLM-guided warm starts provide up to 2× speedup compared with starting from scratch in downstream local search.
Figures & tables
Figure 1: Framework.
Model
Inf. Det.
SAT Acc.
UNSAT Acc.
Time (s)
Deepseek-V3.2
55.1%
74.2%
36.0%
17.37±71.72
Llama3.3-70B
73.0%
79.0%
67.0%
3.72±5.09
Grok-4.1-Fast (Reasoning)
71.2%
42.4%
100%
114.40±107.72
GPT5.2
78.5%
61.2%
95.8%
8.67±5.55
GPT5.2-Reasoning
77.5%
55.0%
100%
49.68±54.36
Llama-8b SFT BestOf1
98.5%
98.0%
99.0%
2.30±2.66
Table 1: Evaluation of infeasibility detection accuracy (Inf. Det.), breakdown accuracy for satisfiable (SAT) and unsatisfiable (UNSAT) instances on the minor-embedding problem. Bold values indicate the best performance for each metric.
Figure 2: Accuracy breakdown by the problem graph vertices number. Subplots show results for (a) the full dataset, (b) SAT instances only, and (c) UNSAT instances only.
Model
Inf. Det.
SAT Acc.
UNSAT Acc.
Time (s)
Deepseek-V3.2
48.1%
26.9%
71.7%
11.75±56.95
Llama3.3-70B
47.7%
1.3%
99.2%
1.08±0.92
Grok-4.1-Fast (Reasoning)
60.0%
23.5%
99.2%
111.42±61.20
GPT5.2
50.4%
5.89%
99.79%
7.92±10.14
GPT5.2-Reasoning
62.3%
28.33%
100 %
42.98±55.19
Llama3.1-8b SFT BestOf1
83.1%
83.84%
82.28%
11.22±11.58
Table 2: Evaluation of infeasibility detection (Inf. Det.), breakdown accuracy for satisfiable (SAT) and unsatisfiable (UNSAT) instances on the 3-coloring problem. Bold values indicate the best performance for each metric.
Figure 3: Accuracy breakdown by instance size. Subplots show results for (a) the full dataset, (b) SAT instances only, and (c) UNSAT instances only.
Model
SAT Sol. Feas.
Avg. Error
FJ Succ.
FJ time (s)
Gap ↓
Random
N/A
N/A
87.16%
5.05±10.29
16.73%
GPT5.2
8.6%
20.64
87.32%
4.99±10.20
18.78%
GPT5.2-Reasoning
31.2%
14.33
87.76%
4.86±10.12
15.10%
Llama-8b SFT BestOf1
11.2%
15.20
87.32%
4.97±10.25
16.33%
Llama-8b SFT BestOf8
23.4%
13.58
91.40%
4.06±9.20
10.00%
Table 3: Feasibility Jump results for minor-embedding. SAT Sol. Feas. is the LLM’s solution feasibility rate specifically for the satisfiable (SAT) instances, while Avg. Error measures intial solution’s constraint violations. These metrics are N/A for the Random baseline as it is not LLM warm-started. FJ Succ. and FJ time denote success rate and runtime within 30s; Gap represents the relative objective gap ( (method obj−best known obj)/method obj ).
Model
SAT Sol. Feas.
Avg. Error
FJ Succ.
FJ time (s)
Random
N/A
N/A
94.98%
2.12 ± 6.83
GPT5.2
4.37%
30.14
94.71%
2.21 ± 7.01
GPT5.2-Reasoning
24.33%
12.38
95.25%
2.08 ± 6.70
Llama-8b SFT BestOf1
2.28%
15.51
94.80%
2.13 ± 6.87
Llama-8b SFT BestOf8
6.84%
12.30
98.56%
0.96 ± 3.98
Table 4: Feasibility Jump Results of 3-coloring
Problem
Inf. Det.
SAT Acc.
UNSAT Acc.
3-coloring
88.00%
94.40%
81.60%
minor-embedding
87.70%
99.8%
75.6%
Table 5: Out of distribution performance.
Method
SAT Succ.
Gap ↓
UNSAT Succ.
Time (s)
Gurobi
54.6%
6.23%
17.2%
47.02
Gurobi NoRel Heuristic
72.8%
5.76%
N/A
25.32
Llama-8b SFT BestOf8 + FJ
93.8 %
8.02%
99.8%
10.22
Table 6: Comparison with Gurobi.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Representative sparse hardware topologies used in quantum annealing: Chimera (left) and Pegasus (right). Pegasus has higher local connectivity than Chimera, but both remain sparse compared with many logical problem graphs. The figure was generated using the open-source dwave_networkx package from exact Chimera and Pegasus graph constructions ( D-Wave Systems Inc., 2025 ) ; Chimera is shown with size parameter (m=2,n=2,t=4) and Pegasus with m=4 .
Formulation
Solved
UNSAT
Gap ↓
Time (s)
Decomposition
65.41%
6.20%
15.15%
42.95
Chain-enumeration
96.40%
100.00%
5.14%
17.88
Appendix
Table 7: Comparison of the two formulations on 2000 instances with a 60-second Gurobi time limit per instance. The table reports results on the 1100 instances that were solved by at least one method or certified infeasible. Solved is the fraction of instances solved within the time limit, UNSAT is the fraction of infeasible instances certified infeasible, Gap is the mean final relative optimality gap at termination (returned by Gurobi), computed as (upper bound−lower bound)/∣upper bound∣ , and Time (s) is the mean total runtime.
Model
Feasibility ↑
Optimality Gap ↓
Error Ratio ↓
GPT5.2
22.2%
70.58%
17.04%
Llama-8b SFT BestOf1
10.1%
16.64%
3.90%
Llama-8b SFT BestOf8
24.1%
10.04%
2.06%
Appendix
Table 8: Evaluation of feasibility and optimality gap (min-coloring). Bold indicates optimal performance per metric. Error Ratio is defined as the percentage of violated edges among all edges.
Method
Inf. Cert.
Feas.
Coverage
Opt. Cert.
Avg. Gap ↓
Gurobi+Zero
4,816
5,281
10,097 (50.5%)
82.0%
0.47%
minorminer
N/A
6,947
6,947 (34.7%)
N/A
2.21%
Appendix
Table 9: Comparison of Gurobi+Zero-Phase Infeasibility Detection and minorminer on 20,000 minor-embedding instances. Inf. Cert. is the number of instances certified infeasible. Feas. is the number of feasible solutions found. Coverage counts all instances resolved by the method, i.e., infeasibility certificates plus feasible solutions. Opt. Cert. reports the fraction of feasible solutions additionally proved globally optimal. Avg. Gap is the average relative gap on the 4,842 instances solved by both methods, computed against the best objective found by either method.
Setting
Value
Base model
Llama-3 8B
Framework
Unsloth + TRL SFTTrainer
LoRA rank r
32
LoRA alpha α
32
LoRA target modules
q,k,v,o , gate, up, down proj
Max sequence length
20000
Appendix
Table 10: Main supervised fine-tuning hyperparameters.
Figure 5: Token usage for GPT-5.2 and Grok-4.1 across tasks. As instance size increases, these models often default to an ”infeasible” verdict, bypassing the search for valid solutions to save tokens. In contrast, our fine-tuned model’s token usage scales linearly with problem size due to its structured format.
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.