Infeasibility Aware Large Language Models for Combinatorial Optimization

• URL: http://arxiv.org/abs/2604.01455v1
• Date: Wed, 01 Apr 2026 23:02:44 GMT
• Title: Infeasibility Aware Large Language Models for Combinatorial Optimization
• Abstract summary: We propose an infeasibility-aware framework that combines certifiable dataset construction, supervised fine-tuning, and LLM-assisted downstream search.<n>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 $2times$ speedup.
• Score: 12.884852956582762
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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\times$ speedup compared with starting from scratch in downstream local search.

Related papers

• GRIMIP: A General Framework for Instance-Specific Configuration of MIP Solvers Using LLMs [9.2939109839777]
  This paper introduces textbfGRIMIP (textbfunderlineGeneral textbfunderlineReasoning for textbfunderlineInstance-specific textbfunderlineMIP configuration), a novel hybrid intelligence framework.
  arXiv  Detail & Related papers  (2026-06-22T13:10:50Z)
• New Hybrid Fine-Tuning Paradigm for LLMs: Algorithm Design and Convergence Analysis Framework [52.69678300445233]
  Fine-tuning Large Language Models (LLMs) typically involves either full fine-tuning, which updates all model parameters, or.<n>Efficient Fine-Tuning (PEFT) adjusts a small subset of parameters.<n>We propose a novel hybrid fine-tuning approach that jointly updates both LLMs and PEFT modules using a combination of zeroth-order and first-order optimization methods.
  arXiv  Detail & Related papers  (2026-04-10T22:39:38Z)
• AsynDBT: Asynchronous Distributed Bilevel Tuning for efficient In-Context Learning with Large Language Models [4.4866154758274375]
  In-context learning (ICL) has emerged as a promising paradigm that enables LLMs to adapt to new tasks using examples provided within the input.<n>Previous FL approaches that incorporate ICL have struggled with severe straggler problems and challenges associated with heterogeneous non-identically data.<n>We propose an asynchronous distributed bilevel tuning (AsynDBT) algorithm that optimize both in-context learning samples and prompt fragments based on the feedback from the LLM.
  arXiv  Detail & Related papers  (2026-02-06T13:07:49Z)
• Toward a Trustworthy Optimization Modeling Agent via Verifiable Synthetic Data Generation [11.988926173584154]
  We present a framework for training trustworthy large language model (LLM) agents via a synthetic data generation pipeline.<n> OptiTrust is a modular LLM agent that performs multi-language translation from natural language to solver-ready code.<n>Our agent achieves state-of-the-art performance on standard benchmarks.
  arXiv  Detail & Related papers  (2025-08-05T05:54:20Z)
• Can Prompt Difficulty be Online Predicted for Accelerating RL Finetuning of Reasoning Models? [65.18157595903124]
  This work investigates iterative approximate evaluation for arbitrary prompts.<n>It introduces Model Predictive Prompt Selection (MoPPS), a Bayesian risk-predictive framework.<n>MoPPS reliably predicts prompt difficulty and accelerates training with significantly reduced rollouts.
  arXiv  Detail & Related papers  (2025-07-07T03:20:52Z)
• Test-Time Learning for Large Language Models [33.11605667376906]
  We propose a Test-Time Learning (TTL) paradigm for Large Language Models (LLMs)<n>LLMs dynamically adapts to target domains using only unlabeled test data during testing.<n>We demonstrate through experiments that TLM improves performance by at least 20% compared to original LLMs on domain knowledge adaptation.
  arXiv  Detail & Related papers  (2025-05-27T02:18:59Z)
• PEARL: Towards Permutation-Resilient LLMs [29.55886726376898]
  In-context learning (ICL) capability of large language models (LLMs) enables them to perform challenging tasks using provided demonstrations.<n>ICL is highly sensitive to the ordering of demonstrations, leading to instability in predictions.<n>This paper shows that this vulnerability can be exploited to design a natural attack that achieves nearly 80% success rate on LLaMA-3.
  arXiv  Detail & Related papers  (2025-02-20T15:07:02Z)
• Rational Tuning of LLM Cascades via Probabilistic Modeling [0.9208007322096532]
  We present a probabilistic model for the joint performance distribution of a sequence of large language models (LLMs)<n>Compared to selecting confidence thresholds using Bayesian optimization, our Markov parametric-copula model yields more favorable error-cost trade-offs.<n>Our framework's inductive assumptions about the interactions between the error rates of different LLMs enhance sample efficiency.
  arXiv  Detail & Related papers  (2025-01-16T07:58:33Z)
• In-context Demonstration Matters: On Prompt Optimization for Pseudo-Supervision Refinement [71.60563181678323]
  Large language models (LLMs) have achieved great success across diverse tasks, and fine-tuning is sometimes needed to further enhance generation quality.<n>To handle these challenges, a direct solution is to generate high-confidence'' data from unsupervised downstream tasks.<n>We propose a novel approach, pseudo-supervised demonstrations aligned prompt optimization (PAPO) algorithm, which jointly refines both the prompt and the overall pseudo-supervision.
  arXiv  Detail & Related papers  (2024-10-04T03:39:28Z)
• OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling [62.19438812624467]
  Large language models (LLMs) have exhibited their problem-solving abilities in mathematical reasoning.<n>We propose OptiBench, a benchmark for End-to-end optimization problem-solving with human-readable inputs and outputs.
  arXiv  Detail & Related papers  (2024-07-13T13:27:57Z)
• Entropy Law: The Story Behind Data Compression and LLM Performance [115.70395740286422]
  We find that model performance is negatively correlated to the compression ratio of training data, which usually yields a lower training loss. Based on the findings of the entropy law, we propose a quite efficient and universal data selection method. We also present an interesting application of entropy law that can detect potential performance risks at the beginning of model training.
  arXiv  Detail & Related papers  (2024-07-09T08:14:29Z)
• FederatedScope-LLM: A Comprehensive Package for Fine-tuning Large Language Models in Federated Learning [70.38817963253034]
  This paper first discusses these challenges of federated fine-tuning LLMs, and introduces our package FS-LLM as a main contribution. We provide comprehensive federated parameter-efficient fine-tuning algorithm implementations and versatile programming interfaces for future extension in FL scenarios. We conduct extensive experiments to validate the effectiveness of FS-LLM and benchmark advanced LLMs with state-of-the-art parameter-efficient fine-tuning algorithms in FL settings.
  arXiv  Detail & Related papers  (2023-09-01T09:40:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.