Pith. sign in

REVIEW 5 major objections 5 minor 55 references

STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization

T0 review · 5 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Conditioning LLM code search on graph structural embeddings produces better solver algorithms for MILP and SAT, with SAT timeouts cut by up to 77.8 percent.

desk verdict A novel GNN-LLM combination for heuristic search, but the paper's own tables contradict its 'large margin' claim and the reported wins come from a post hoc variant. read the letter →

arxiv 2506.11057 v1 pith:2KQHVHP6 submitted 2025-05-22 cs.LG cs.AI

Xijun Li , Jiexiang Yang , Jinghao Wang , Bo Peng , Jianguo Yao , Haibing Guan This is my paper
classification cs.LGcs.AI
keywords combinatorialoptimizationlargelanguagemodelsgraphneuralnetworksalgorithmdiscoverymixed-integerlinearprogrammingbooleansatisfiabilityevolutionarysearchstructuralpriors
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

STRCMP sets out to prove that a large language model discovers better solver heuristics for combinatorial optimization when it is conditioned on graph-structured fingerprints of the problem instance, not just a text prompt. The framework converts a MILP or SAT instance into a bipartite graph, trains a graph neural network to classify which problem family the instance belongs to, and feeds the GNN's embedding into an LLM that writes solver-specific code; an evolutionary loop then refines the generated algorithms. Against five neural and LLM-based baselines across MILP and SAT benchmarks, the paper reports large gains in solution quality and computational efficiency, most concretely on SAT, where it cuts timeouts by up to 77.8% on Zamkeller and 66.7% on PRP relative to AutoSAT. It also proves an information-theoretic bound that adding a structural prior cannot lower a generative model's performance upper bound. If the results hold, structure-aware code generation would make automated algorithm discovery for NP-hard problems substantially cheaper and more reliable than text-only LLM search.

What carries the argument

The load-bearing object is the structural embedding $h_q \in \mathbb{R}^d$, produced by a three-layer graph convolutional network with mean pooling over a bipartite instance graph: constraint-variable graphs for MILP and literal-clause graphs for SAT. The GNN is trained on a domain-classification task, and its pooled embedding is zero-padded and prepended to the LLM's token embeddings as $E = [\mathrm{CLS}] \oplus H_q \oplus \text{embeds}[1:]$, so the structural vector participates in attention at every generation step rather than only in the prompt. Around this fusion sit two supporting mechanisms: post-training with SFT then DPO on solver-executed code triplets, and an evolutionary refinement loop (selection, crossover, mutation) that evaluates candidate code by running the solver. The theoretical support is Theorem 1, which shows $\sup(P_{C_K \cup \{C_i\}}) \ge \sup(P_{C_K})$, i.e. adding a prior cannot lower the performance upper bound, and Theorem 2, which says neglecting a performance-enhancing prior does lower it.

What would settle it

Run STRCMP against its own w/o-GNN ablation on all four SAT datasets with multiple random seeds and compare final PAR-2 and timeout counts; the central claim collapses if the no-GNN variant wins or ties on most benchmarks, and the paper's single-run table already points that way on CoinsGrid (PAR-2 1098.34 vs 1124.09) and PRP (1820.38 vs 1804.46). A sharper version: retrain the GNN to predict solver runtime or PD integral rather than domain class, and check whether conditioning on those embeddings ever beats text-only LLM search.

Watch

Extended reading notes

Core claim

The paper's central claim is that combinatorial problem structure, extracted as a learned graph embedding, is a usable conditioning signal for LLM-based algorithm discovery. Given an instance $q$, STRCMP builds a bipartite graph (constraint nodes and variable nodes for MILP; literal nodes and clause nodes for SAT), runs a GNN to obtain $h_q$, and generates solver code token-by-token from $P(w_t \mid w_{<t}; h_q, \mathrm{NL})$. The composite GNN plus LLM is post-trained with SFT and DPO on (mathematical model, code, metric) triplets, then embedded in an evolutionary framework. The paper argues this beats five baselines—L2B, HEM, NeuroSAT, AutoSAT, and LLM4Solver—on solution optimality and efficiency, with the cleanest wins on SAT benchmarks, and it proves that conditioning on additional priors does not reduce the theoretical upper bound of model performance.

Load-bearing premise

The framework's load-bearing premise is that a GNN trained only to classify which problem family an instance comes from produces embeddings that carry enough solver-relevant structure to improve code generation; if those embeddings are mainly a coarse domain tag, the model degenerates into an ordinary LLM-plus-evolutionary search, and the paper's ablation data already show the no-GNN variant matching or beating the full model on some SAT datasets.

Editorial extensions

If this is right

  • If STRCMP's central claim holds, SAT heuristic discovery no longer needs manual expert tuning: on Zamkeller the framework reduces timeouts from 18 to 4 and PAR-2 from 807.75 to 270.62 relative to AutoSAT.
  • The composite model converges faster in evolutionary search than AutoSAT and LLM4Solver, reaching stable low PAR-2 within roughly 60 iterations on Zamkeller while AutoSAT keeps oscillating, which means fewer solver invocations and lower discovery cost per run.
  • The two-stage post-training recipe (SFT then DPO on solver-executed code triplets) is reusable: any pretrained code LLM can be conditioned on a frozen GNN embedding with only LoRA updates, so the framework's overhead beyond the base LLM is modest.
  • Theorem 1's inequality implies that adding a structural prior cannot lower the upper bound of a generative model's performance, so future work can add further modal priors such as constraint patterns or solver metrics without an information-theoretic penalty.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: because the GNN is trained on domain classification rather than on any solver-performance objective, its embeddings may act largely as a domain tag; the strongest reading of the paper's own ablation is that the structural prior helps most where domain label correlates with solver difficulty (Zamkeller) and can be neutral or slightly harmful elsewhere (CoinsGrid, PRP).
  • Editorial inference: a direct test of the structural-prior claim would train the GNN to predict per-instance solver metrics (PAR-2, PD integral, timeout status) instead of domain class; consistent gains over the w/o-GNN ablation on that variant would support the mechanism far more cleanly than the current classification proxy.
  • Editorial inference: the information-theoretic theorems bound the best achievable output, not the trained model's realized behavior, so they justify trying structural priors as a design choice but do not themselves predict empirical gains; the gains must come from whether the GNN's embedding actually tracks solver-relevant structure.
  • Editorial inference: if the recipe generalizes, any CO domain with a natural bipartite encoding such as vehicle routing, scheduling, or network design could reuse the same composite GNN plus LLM setup, with the GNN conditioning the LLM on instance topology and the evolutionary loop refining solver code against real solver feedback.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

Summary. The paper proposes STRCMP, a framework that combines a GNN-based structural embedding with an LLM to generate solver-specific code for MILP and SAT problems, embedded in an evolutionary search. The main claims are (i) STRCMP outperforms five neural and LLM-based baselines by a large margin on nine benchmarks, and (ii) a theoretical result showing that adding structural priors cannot lower the performance upper bound. The experimental section reports results on SAT and MILP datasets, including ablations with and without the GNN and with different post-training schemes.

Significance. The problem is relevant: using LLMs to discover solver heuristics is an active area, and integrating graph structure is a plausible direction. If the empirical claims were fully supported, the paper would provide a useful advance. The paper is also commendable for including ablations and convergence analyses. However, the central empirical claim is internally contradicted by the paper's own tables, and the theoretical analysis is either a tautology or contains an incorrect proof step. As a result, the contribution as presented is not established.

major comments (5)
  1. [Section 5.3, Tables 1 and 5] The claimed 66.7% timeout reduction on PRP (9→3) is attributed to STRCMP, but Table 1 shows the full STRCMP model has 44 timeouts on PRP versus AutoSAT's 9, and Table 5 shows PAR-2 of 1804.46 versus 639.34. The reduction is achieved by STRCMP(DPO Only), not the full model. The abstract's claim that STRCMP outperforms all baselines by a large margin is therefore contradicted by the paper's own data on a main benchmark.
  2. [Section 4.2, Definition 1 and Theorem 1] Theorem 1 is a formal consequence of Definition 1: sup(P_C) is defined as a sum over prior types of p(c) max_w p(w|c)Φ(w), so enlarging the prior set C cannot decrease the sum. The proof in Appendix A confirms this by an inequality that follows from max over a superset. The remark that 'integrating CO structural priors into LLMs does not degrade their performance' is a restatement of the definition, not a substantive theorem. The paper provides no theoretical statement connecting the learned GNN embeddings to code-generation performance, so this section does not contribute empirical or theoretical support to the method.
  3. [Appendix A, Eq. (8) in proof of Theorem 2] The equality max_w p(w|c)Φ(w)_{c∈C} = Σ_{cpe∈Cpe} p(cpe|c) max_w p(w|c)Φ(w)_{c∈C} is incorrect: the maximum over the union of two prior sets is not a convex combination of the maxima over the individual sets. Consequently, the proof of Theorem 2 does not establish that a performance-enhancing prior strictly increases sup(P). This is a load-bearing error in the theoretical analysis.
  4. [Section 4.1 (Step 1), Table 5, and Section 5.3 ablation text] The GNN is trained solely on a domain-classification task, and the paper assumes the resulting embeddings are useful for code generation. The ablation in Table 5 contradicts the text: on CoinsGrid, STRCMP w/o GNN has a better PAR-2 (1098.34) than the full STRCMP (1124.09), and on PRP the two are close (1820.38 vs 1804.46). Section 5.3 states that the w/o GNN variant is 'consistently inferior', which is not supported by the table. The evidence does not demonstrate that the structural prior provides measurable benefits.
  5. [Section 5.3 and Section 5.2] The paper reports results for four variants of STRCMP (full, SFT-Only, DPO-Only, w/o GNN) without specifying a single model that constitutes the proposed method. The best results on PRP and Zamkeller are achieved by different variants (DPO-Only for PRP, SFT-Only for Zamkeller in terms of solving time). Since the abstract and conclusion refer to 'STRCMP' without qualification, the reported 'large margin' appears to rely on post hoc selection of the best variant per benchmark. This makes the claimed comparison ambiguous and not reproducible as a single method.
minor comments (5)
  1. [Section 5.1] The number of benchmark datasets is inconsistent: the abstract says nine, Section 5.1 says ten, and the listed SAT+MILP datasets number eleven (4 SAT + 7 MILP). Please reconcile.
  2. [Section 5.2] The phrase 'ten widely-used benchmark dataset' should be 'ten widely-used benchmark datasets'.
  3. [Table 4] The Hard tier in Section 5.1 includes Load Balancing and Anonymous, but Table 4 lists only Load Balancing; please clarify the role of the Anonymous dataset and provide its statistics if used.
  4. [Section 3, Eq. (2)] The notation A∼A is confusing as written; the authors likely intend A drawn from the space of algorithms A. Please clarify.
  5. [Appendix G.3, Figure 11] The caption 'STRCMP \wo GNN' appears to contain a LaTeX escape that will not render; it should be 'STRCMP w/o GNN' for consistency with the main text.

Circularity Check

3 steps flagged · score 6.0 of 10

The theoretical 'guarantee' is a definitional tautology (adding a prior to a max cannot lower it), and the headline 'large margin' over AutoSAT is taken from the post hoc DPO-Only variant, not the full STRCMP model, which loses on PRP (Table 5: PAR-2 1804.46 vs 639.34).

  1. self definitional [Section 4.2, Definition 1, Theorem 1, Remark 1; Appendix A Eq. (7)]
    "sup(PC) = X C∈C X c∈C p(c) max w p(w|c)Φ(w), (4) ... Theorem 1. ... A generative model with an additional type of prior will not lower the upper bound of model performance sup(P). ... Remark 1. ... integrating combinatorial optimization structural priors into LLMs does not degrade their performance in generating code for solving CO problems."

    By Definition 1, sup(P) is a sum over priors of a maximum over outputs. Adjoining a new prior C_i inserts additional nonnegative terms into this sum/max, so the inequality sup(P_{C_K ∪ {C_i}}) ≥ sup(P_{C_K}) holds by the monotonicity of sums and maxima. The 'result' that structural priors do not degrade performance is therefore a formal identity built into the definition; it carries no information about whether the learned GNN embeddings are informative for solver-code generation. The paper uses this tautology as its theoretical justification (Remark 1), yet the actual empirical comparison in Tables 1 and 5 shows the full STRCMP model is worse than STRCMP w/o GNN on CoinsGrid (PAR-2 1124.09 vs 1098.34) and far worse than AutoSAT on PRP (timeouts 44 vs 9).

  2. self definitional [Section 4.2, Definition 2, Theorem 2, Remark 2]
    "Definition 2 (Performance-Enhancing Prior). Assume a type of prior C can boost the performance of a generative model compared to the one without the prior, then C is the performance-enhancing prior... Theorem 2. If prior Cpe is a performance-enhancing prior, a generative model neglecting prior Cpe will decrease the upper bound of model performance."

    Theorem 2 is a restatement of Definition 2: a 'performance-enhancing prior' is defined as one whose inclusion boosts performance, and the theorem then asserts that omitting such a prior lowers the upper bound. The inequality is equivalent to the definition, so it adds no independent evidence. Remark 2 then asserts that 'the structural prior serves as such performance-enhancing prior ... empirically validated through our comprehensive experiments'; the only empirical validation offered is the same comparison that contradicts the full model on PRP, where Table 5 gives STRCMP PAR-2 = 1804.46 versus AutoSAT's 639.34.

1 more flagged steps
  1. fitted input called prediction [Section 5.3, Results; Tables 1 and 5]
    "Specifically for SAT, STRCMP demonstrates universal superiority over its closest counterpart AutoSAT, particularly achieving significant reductions in terms of timeout (77.8% on Zamkeller: 18 →4; 66.7% on PRP: 9 →3) and solving time (on PRP: 22967 seconds → 21146 seconds; on Zamkeller: 20772 seconds → 6929 seconds)."

    The quoted reductions are not produced by the full STRCMP model. Table 1 reports STRCMP PRP timeouts = 44 versus AutoSAT 9, and Table 5 reports STRCMP PRP PAR-2 = 1804.46 versus AutoSAT 639.34. The 9→3 timeout reduction and the 22967→21146 solving-time reduction come from the STRCMP(DPO Only) row, not from the unified STRCMP model. The abstract's and conclusion's claim that 'STRCMP outperforms five strong ... methods by a large margin' is thus obtained by selecting, per benchmark, the best post-training variant after the results are known. This is a post hoc selection on the evaluation data, so the reported 'prediction' is the maximum over variants rather than the output of a single fixed model.

full rationale

The paper's only formal theoretical results (Theorem 1 and Theorem 2 in Section 4.2) are definitional tautologies: Definition 1 defines the performance upper bound as a maximum over outputs summed over priors, which makes 'adding a prior cannot lower the upper bound' true by construction, and Definition 2 defines a performance-enhancing prior as one whose inclusion improves performance, which makes Theorem 2 a restatement. These theorems therefore provide no genuine support for the claim that the learned GNN embeddings improve code generation. The central empirical claim is also not supported by a single consistent model: the headline 'large margin' over AutoSAT is taken from the STRCMP(DPO Only) variant, while the full STRCMP model loses to AutoSAT on PRP (PAR-2 1804.46 vs 639.34; timeouts 44 vs 9) and is worse than its own no-GNN ablation on CoinsGrid (PAR-2 1124.09 vs 1098.34). The paper's own tables and appendix statements (Section 5.3 and Appendix F) acknowledge that the full model does not uniformly outperform its post-training variants, so the reported advantage reduces to a per-benchmark selection of the best variant rather than a fixed model's prediction. There is no load-bearing self-citation chain: citations to the authors' prior HEM/L2B work are contextual, not the source of the claimed result. The core circularity is that the theoretical guarantee is definitionally vacuous and the empirical 'large margin' is an artifact of post hoc variant selection. Score 6 reflects partial circularity: the formal analysis reduces to its own definitions, and the central empirical prediction is selected after the fact rather than derived from the proposed composite model.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The framework relies on a hand-coded bipartite graph encoding, a GNN trained for domain classification, and an LLM adapted by prepending embeddings. No new physical entities are introduced. The main unmeasured assumption is that classification-style GNN embeddings transfer to code-generation conditioning; the paper's own ablation gives mixed evidence.

free parameters (4)
  • GNN embedding dimension = 16/32/64 layers for SAT; 128 final layer for MILP
    Hand-chosen architecture; the final embedding dimension (64 or 128) is the structure prior injected into the LLM.
  • LoRA hyperparameters = rank 16, alpha 32, dropout 0.05
    Hand-selected for parameter-efficient fine-tuning of the composite model; affects how strongly the structural prior is absorbed.
  • Post-training dataset sizes = 8k MILP, 4k SAT instances
    Collected by querying the same LLM used for post-training; sizes are hand-selected without sensitivity analysis.
  • GNN classification labels = 5 SAT classes; per-dataset MILP classes
    The supervision for the GNN is a hand-assigned domain label; there is no independent evidence that these labels capture solver-relevant structure.
assumptions (4)
  • domain assumption The bipartite graph representation (constraint-variable for MILP, literal-clause for SAT) preserves solver-relevant structure.
    Section 4.1 Step 1 and Appendix B.1 rely on the established encodings from Gasse et al. [14] and Hardsatgen [51].
  • ad hoc to paper A GNN trained on domain classification yields embeddings useful for code generation.
    The transfer from classification to code generation is assumed; the w/o GNN ablation gives mixed evidence, with the no-GNN variant better on CoinsGrid PAR-2.
  • domain assumption An LLM can absorb prepended GNN embeddings without degrading token prediction after SFT/DPO.
    Appendix B.2 modifies the Qwen2.5-Coder model by prepending [CLS] and the padded embedding; the paper provides no formal guarantee or controlled study of this architectural change.
  • ad hoc to paper Theorem 1's performance upper bound is a meaningful proxy for real LLM performance.
    The sup(P) criterion lets the model choose the best output for each prior, which real LLMs cannot do. The paper uses this as theoretical support in Remarks 1 and 2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization." pith.science (2026). https://pith.science/paper/2KQHVHP6

@misc{pith2026250611057,
  author       = {Pith},
  title        = {Pith review of: STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2KQHVHP6}},
  note         = {Machine review of arXiv:2506.11057}
}
read the original abstract

Combinatorial optimization (CO) problems, central to operation research and theoretical computer science, present significant computational challenges due to their NP-hard nature. While large language models (LLMs) have emerged as promising tools for CO--either by directly generating solutions or synthesizing solver-specific codes--existing approaches often neglect critical structural priors inherent to CO problems, leading to suboptimality and iterative inefficiency. Inspired by human experts' success in leveraging CO structures for algorithm design, we propose STRCMP, a novel structure-aware LLM-based algorithm discovery framework that systematically integrates structure priors to enhance solution quality and solving efficiency. Our framework combines a graph neural network (GNN) for extracting structural embeddings from CO instances with an LLM conditioned on these embeddings to identify high-performing algorithms in the form of solver-specific codes. This composite architecture ensures syntactic correctness, preserves problem topology, and aligns with natural language objectives, while an evolutionary refinement process iteratively optimizes generated algorithm. Extensive evaluations across Mixed Integer Linear Programming and Boolean Satisfiability problems, using nine benchmark datasets, demonstrate that our proposed STRCMP outperforms five strong neural and LLM-based methods by a large margin, in terms of both solution optimality and computational efficiency. The code and learned model will be publicly available upon the acceptance of the paper.

Figures

Figures reproduced from arXiv: 2506.11057 by the authors.

Figure 1
Figure 1. Intuitive comparison between prior work and the proposed framework. Making complex plans subject to multiple constraints is a time- and labor-intensive process, but is critical in many aspects of our lives such as scheduling [1], logistics [2], and robotics [3]. These problems are frequently mod￾eled as combinatorial optimization (CO) problem, a cor￾nerstone of operation research and theoretical computer science, wh… view at source ↗
Figure 2
Figure 2. Overview of the proposed STRCMP. ❶ Combinatorial Structure Extraction. We utilize a graph neural network (GNN) to encode the topological structure of combinatorial optimization problems into latent embeddings, capturing problem-specific structural invariants. ❷ Structure￾Aware Code Generation: (a) Data Curation: For a given CO problem’s mathematical model, target solver and the specific prompt, an LLM generates cand… view at source ↗
Figure 3
Figure 3. Optimization performance over different CO domains. Aligned with [ [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (9 more)
Figure 5
Figure 5. Figure 5: Ablation studies in terms of optimization performance and convergence rate. [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 4
Figure 4. Figure 4: Convergence comparison (w.r.t. PAR-2) between evolutionary-based algorithm discovery frameworks on Zamkeller dataset of SAT domain. Efficiency Improvement (Answer to RQ2). Next, we assess the efficiency of our pro￾posed STRCMP framework in discovering high￾performance …
Figure 6
Figure 6. Figure 6: The convergence curve of training GNN for SAT domain. [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]
Figure 7
Figure 7. Figure 7: The convergence curve of post-training composite model for SAT domain. [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]
Figure 8
Figure 8. Figure 8: Convergence comparison (w.r.t. PAR-2) between evolutionary-based algorithm discovery [PITH_FULL_IMAGE:figures/full_fig_p024_8.png]
Figure 9
Figure 9. Figure 9: Convergence comparison (w.r.t. PAR-2, Solving Time, and Number of Timeout) between [PITH_FULL_IMAGE:figures/full_fig_p025_9.png]
Figure 10
Figure 10. Figure 10: Convergence comparison (w.r.t. PD Integral and Solving Time) between evolutionary [PITH_FULL_IMAGE:figures/full_fig_p026_10.png]
Figure 11
Figure 11. Figure 11: Ablation studies (w.r.t. PAR-2, Solving Time, and Number of Timeout) during algorithm [PITH_FULL_IMAGE:figures/full_fig_p027_11.png]
Figure 12
Figure 12. Figure 12: Convergence comparison with variance statistic (w.r.t. PAR-2, Solving Time, Number of [PITH_FULL_IMAGE:figures/full_fig_p028_12.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

55 extracted references · 27 canonical work pages

  1. [1]

    An integer programming approach to scheduling.Computer scheduling of public transport urban passenger vehicle and crew scheduling, pages 269–280, 1981

    David M Ryan and Brian A Foster. An integer programming approach to scheduling.Computer scheduling of public transport urban passenger vehicle and crew scheduling, pages 269–280, 1981

    work page 1981

  2. [2]

    A data-driven three-layer algorithm for split delivery vehicle routing problem with 3d container loading constraint

    Xijun Li, Mingxuan Yuan, Di Chen, Jianguo Yao, and Jia Zeng. A data-driven three-layer algorithm for split delivery vehicle routing problem with 3d container loading constraint. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 528–536, 2018

    work page 2018

  3. [3]

    Llm+ p: Empowering large language models with optimal planning proficiency.arXiv preprint arXiv:2304.11477, 2023

    Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone. Llm+ p: Empowering large language models with optimal planning proficiency.arXiv preprint arXiv:2304.11477, 2023

    arXiv 2023

  4. [4]

    Exploiting special structure in semidefinite programming: A survey of theory and applications.European Journal of Operational Research, 201(1):1–10, 2010

    Etienne De Klerk. Exploiting special structure in semidefinite programming: A survey of theory and applications.European Journal of Operational Research, 201(1):1–10, 2010

    work page 2010

  5. [5]

    PhD thesis, Citeseer, 2011

    Maria Kandyba-Chimani.Exact algorithms for network design problems using graph orienta- tions. PhD thesis, Citeseer, 2011

    work page 2011

  6. [6]

    The molecule problem: Exploiting structure in global optimization.SIAM Journal on Optimization, 5(4):835–857, 1995

    Bruce Hendrickson. The molecule problem: Exploiting structure in global optimization.SIAM Journal on Optimization, 5(4):835–857, 1995

    work page 1995

  7. [7]

    Machine learning for combinatorial optimization: a methodological tour d’horizon.European Journal of Operational Research, 290(2):405–421, 2021

    Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d’horizon.European Journal of Operational Research, 290(2):405–421, 2021

    2021

  8. [8]

    Attention is all you need.Advances in neural information processing systems, 30, 2017

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need.Advances in neural information processing systems, 30, 2017

    2017

Show all 55 references
  1. [9]

    Neural combina- torial optimization with reinforcement learning.arXiv preprint arXiv:1611.09940, 2016

    Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning.arXiv preprint arXiv:1611.09940, 2016

    2016 arXiv

  2. [10]

    Mip-gnn: A data-driven framework for guiding combinatorial solvers

    Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guiding combinatorial solvers. InProceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10219–10227, 2022

    2022

  3. [11]

    Hyper- reactive tabu search for maxsat

    Carlos Ansótegui, Britta Heymann, Josep Pon, Meinolf Sellmann, and Kevin Tierney. Hyper- reactive tabu search for maxsat. InLearning and Intelligent Optimization: 12th International Conference, LION 12, Kalamata, Greece, June 10–15, 2018, Revised Selected Papers 12, pages 309–...

    2018

  4. [12]

    Learning when to use a decompo- sition

    Markus Kruber, Marco E Lübbecke, and Axel Parmentier. Learning when to use a decompo- sition. InInternational conference on AI and OR techniques in constraint programming for combinatorial optimization problems, pages 202–210. Springer, 2017

  5. [13]

    Learning a classification of mixed-integer quadratic programming problems

    Pierre Bonami, Andrea Lodi, and Giulia Zarpellon. Learning a classification of mixed-integer quadratic programming problems. InInternational conference on the integration of constraint programming, artificial intelligence, and operations research, pages 595–604. Springer, 2018

    2018

  6. [14]

    Ex- act combinatorial optimization with graph convolutional neural networks.arXiv preprint arXiv:1906.01629, 2019

    Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Ex- act combinatorial optimization with graph convolutional neural networks.arXiv preprint arXiv:1906.01629, 2019

    1906 arXiv

  7. [15]

    Learning cut selection for mixed-integer linear programming via hierarchical sequence model.arXiv preprint arXiv:2302.00244, 2023

    Zhihai Wang, Xijun Li, Jie Wang, Yufei Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integer linear programming via hierarchical sequence model.arXiv preprint arXiv:2302.00244, 2023

    2023 arXiv

  8. [16]

    Learning to cut via hierarchical sequence/set model for efficient mixed-integer programming.IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024

    Jie Wang, Zhihai Wang, Xijun Li, Yufei Kuang, Zhihao Shi, Fangzhou Zhu, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning to cut via hierarchical sequence/set model for efficient mixed-integer programming.IEEE Transactions on Pattern Analysis and Machine Intellige...

    2024

  9. [17]

    Co-bench: Benchmarking lan- guage model agents in algorithm search for combinatorial optimization.arXiv preprint arXiv:2504.04310, 2025

    Weiwei Sun, Shengyu Feng, Shanda Li, and Yiming Yang. Co-bench: Benchmarking lan- guage model agents in algorithm search for combinatorial optimization.arXiv preprint arXiv:2504.04310, 2025

    2025 arXiv

  10. [18]

    Large language models as optimizers.arXiv preprint arXiv:2309.03409, 2023

    Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. Large language models as optimizers.arXiv preprint arXiv:2309.03409, 2023

    2023 arXiv

  11. [19]

    How multimodal integration boost the performance of llm for optimization: Case study on capacitated vehicle routing problems.arXiv preprint arXiv:2403.01757, 2024

    Yuxiao Huang, Wenjie Zhang, Liang Feng, Xingyu Wu, and Kay Chen Tan. How multimodal integration boost the performance of llm for optimization: Case study on capacitated vehicle routing problems.arXiv preprint arXiv:2403.01757, 2024

    2024 arXiv

  12. [20]

    Mathematical discoveries from program search with large language models

    Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, 625(7995...

    2024

  13. [21]

    Evolution of heuristics: Towards efficient automatic algorithm design using large language model.arXiv preprint arXiv:2401.02051, 2024

    Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language model.arXiv preprint arXiv:2401.02051, 2024

    2024 arXiv

  14. [22]

    Reevo: Large language models as hyper-heuristics with reflective evolution.arXiv preprint arXiv:2402.01145, 2024

    Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. Reevo: Large language models as hyper-heuristics with reflective evolution.arXiv preprint arXiv:2402.01145, 2024

    2024 arXiv

  15. [23]

    The Second Half.https://ysymyth.github.io/The-Second-Half/, 2025

    Shunyu Yao. The Second Half.https://ysymyth.github.io/The-Second-Half/, 2025

    2025

  16. [24]

    Accelerating linear programming solving by exploiting the performance variability via reinforcement learning

    Xijun Li, Qingyu Qu, Fangzhou Zhu, Mingxuan Yuan, Jia Zeng, and Jie Wang. Accelerating linear programming solving by exploiting the performance variability via reinforcement learning. 2023

    2023

  17. [25]

    Pointer networks.Advances in neural information processing systems, 28, 2015

    Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks.Advances in neural information processing systems, 28, 2015

    2015

  18. [26]

    Sequence to sequence learning with neural networks.Advances in neural information processing systems, 27, 2014

    Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks.Advances in neural information processing systems, 27, 2014

    2014

  19. [27]

    A theoretical and com- putational analysis of full strong-branching.Mathematical Programming, 205(1):303–336, 2024

    Santanu S Dey, Yatharth Dubey, Marco Molinaro, and Prachi Shah. A theoretical and com- putational analysis of full strong-branching.Mathematical Programming, 205(1):303–336, 2024

    2024

  20. [28]

    A systematic survey on large language models for algorithm design.arXiv preprint arXiv:2410.14716, 2024

    Fei Liu, Yiming Yao, Ping Guo, Zhiyuan Yang, Zhe Zhao, Xi Lin, Xialiang Tong, Mingxuan Yuan, Zhichao Lu, Zhenkun Wang, et al. A systematic survey on large language models for algorithm design.arXiv preprint arXiv:2410.14716, 2024

  21. [29]

    Autosat: Automatically optimize sat solvers via large language models.arXiv preprint arXiv:2402.10705, 2024

    Yiwen Sun, Furong Ye, Xianyin Zhang, Shiyu Huang, Bingzhen Zhang, Ke Wei, and Shaowei Cai. Autosat: Automatically optimize sat solvers via large language models.arXiv preprint arXiv:2402.10705, 2024

    2024 arXiv

  22. [30]

    Llm4solver: Large language model for efficient algorithm design of combinatorial optimization solver

    Yuyan Zhou, Jie Wang, Yufei Kuang, Xijun Li, Weilin Luo, Jianye HAO, and Feng Wu. Llm4solver: Large language model for efficient algorithm design of combinatorial optimization solver

  23. [31]

    Past and future of the cap set problem.arXiv preprint arXiv:2408.02328, 2024

    Ernie Croot, Vsevolod F Lev, and Péter Pál Pach. Past and future of the cap set problem.arXiv preprint arXiv:2408.02328, 2024

    2024 arXiv

  24. [32]

    Bin packing optimization via deep reinforcement learning.IEEE Robotics and Automation Letters, 2025

    Baoying Wang, Zhaohui Lin, Weijie Kong, and Huixu Dong. Bin packing optimization via deep reinforcement learning.IEEE Robotics and Automation Letters, 2025

    2025

  25. [33]

    Courier Corporation, 1998

    Christos H Papadimitriou and Kenneth Steiglitz.Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998

    1998

  26. [34]

    Traveling salesman problem

    Karla L Hoffman, Manfred Padberg, Giovanni Rinaldi, et al. Traveling salesman problem. Encyclopedia of operations research and management science, 1:1573–1578, 2013. 11

    2013

  27. [35]

    Production planning: a review.European Journal of Operational Research, 7(2):101–110, 1981

    Ludo F Gelders and Luk N Van Wassenhove. Production planning: a review.European Journal of Operational Research, 7(2):101–110, 1981

    1981

  28. [36]

    SIAM, 2002

    Paolo Toth and Daniele Vigo.The vehicle routing problem. SIAM, 2002

    2002

  29. [37]

    Direct preference optimization: Your language model is secretly a reward model

    Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36:53728–53741, 2023

    2023

  30. [38]

    Courier Corporation, 2012

    Robert B Ash.Information theory. Courier Corporation, 2012

    2012

  31. [39]

    Foundations of multimodal co- learning.Information Fusion, 64:188–193, 2020

    Amir Zadeh, Paul Pu Liang, and Louis-Philippe Morency. Foundations of multimodal co- learning.Information Fusion, 64:188–193, 2020

    2020

  32. [40]

    Learning a sat solver from single-bit supervision.arXiv preprint arXiv:1802.03685, 2018

    Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L Dill. Learning a sat solver from single-bit supervision.arXiv preprint arXiv:1802.03685, 2018

    2018 arXiv

  33. [41]

    Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study

    Egon Balas and Andrew Ho. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. InCombinatorial Optimization, pages 37–60. Springer, 1980

    1980

  34. [42]

    Springer, 2016

    David Bergman, Andre A Cire, Willem-Jan Van Hoeve, and John Hooker.Decision diagrams for optimization, volume 1. Springer, 2016

    2016

  35. [43]

    Learning to branch with tree mdps.arXiv preprint arXiv:2205.11107, 2022

    Lara Scavuzzo, Feng Yang Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke- Smith, and Karen Aardal. Learning to branch with tree mdps.arXiv preprint arXiv:2205.11107, 2022

    2022 arXiv

  36. [44]

    Exact com- binatorial optimization with graph convolutional neural networks

    Maxime Gasse, Didier Chetelat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact com- binatorial optimization with graph convolutional neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors,Advances in Neural Inform...

    2019

  37. [45]

    Improving learning to branch via reinforcement learning

    Haoran Sun, Wenbo Chen, Hui Li, and Le Song. Improving learning to branch via reinforcement learning. InLearning Meets Combinatorial Algorithms at NeurIPS2020, 2020

    2020

  38. [46]

    On the facets of the mixed–integer knapsack polyhedron.Mathematical Programming, 98(1):145–175, 2003

    Alper Atamtürk. On the facets of the mixed–integer knapsack polyhedron.Mathematical Programming, 98(1):145–175, 2003

    2003

  39. [47]

    Connections in networks: A hybrid approach

    Carla P Gomes, Willem-Jan van Hoeve, and Ashish Sabharwal. Connections in networks: A hybrid approach. InInternational Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, pages 303–307. Springer, 2008

    2008

  40. [48]

    Machine learning for combinatorial optimization, 2021

    Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Maxime Gasse, Ambros Gleixner, Aleksandr M, Kazachkov, Elias B, Khalil, Pawel Lichocki, Andrea Lodi, Miles Lubin, Chris J, Maddison, Christopher Morris, Dimi...

    2021

  41. [49]

    Proceedings of sat competition 2023: Solver, benchmark and proof checker descriptions

    Tomas Balyo, Marijn Heule, Markus Iser, Matti Järvisalo, and Martin Suda. Proceedings of sat competition 2023: Solver, benchmark and proof checker descriptions. 2023

    2023

  42. [50]

    Ecole: A gym-like library for machine learning in combinatorial optimization solvers.arXiv preprint arXiv:2011.06069, 2020

    Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A gym-like library for machine learning in combinatorial optimization solvers.arXiv preprint arXiv:2011.06069, 2020

    2011 arXiv

  43. [51]

    Hardsatgen: Understanding the difficulty of hard sat formula generation and a strong structure-hardness-aware baseline

    Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula generation and a strong structure-hardness-aware baseline. InProceedings of the 29th ACM SIGKDD Co...

    2023

  44. [52]

    The scip optimization suite 8.0.arXiv preprint arXiv:2112.08872, 2021

    Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, et al. The scip optimization suite 8.0.arXiv preprint arXiv:2112.08872, 2021

    2021 arXiv

  45. [53]

    Solving mixed integer programs using neural networks.arXiv preprint arXiv:2012.13349, 2020

    Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O’Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks.arXiv preprint arXiv:2012.13349, 2020

    2012 arXiv

  46. [54]

    Learning to search in branch and bound algorithms

    He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors,Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014

    2014

  47. [55]

    Automated configuration of mixed in- teger programming solvers

    Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Automated configuration of mixed in- teger programming solvers. InInternational Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, pages 186–202. Spri...

    2010

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.