EvoCut: Strengthening Integer Programs via Evolution-Guided Language Models

• URL: http://arxiv.org/abs/2508.11850v1
• Date: Sat, 16 Aug 2025 00:13:49 GMT
• Title: EvoCut: Strengthening Integer Programs via Evolution-Guided Language Models
• Abstract summary: An effective approach for practically solving integer programs is the manual design of acceleration cuts.<n>Our proposed framework, EvoCut, automates the generation of acceleration cuts by combining large language models with an evolutionary search.<n>EvoCut reliably generates, improves, and empirically verifies cuts that generalize to unseen instances.
• Score: 6.40947897069488
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Integer programming lies at the heart of crucial combinatorial optimization tasks but remains challenging due to its NP-hard nature. An effective approach for practically solving integer programs is the manual design of acceleration cuts, i.e. inequalities that improve solver performance. However, this creative process demands deep expertise and is yet to be automated. Our proposed framework, EvoCut, automates the generation of acceleration cuts by combining large language models (LLMs) with an evolutionary search. EvoCut (i) initializes a diverse population of candidate cuts via an LLM-based initializer agent; (ii) for each cut empirically evaluates both preservation of the optimal solution and its ability to cut off fractional solutions across a verification set; and (iii) iteratively refines the population through evolutionary crossover and mutation agents. We quantify each cut's utility by its relative reduction in the solver's optimality gap. Our comparisons against standard integer programming practice show that EvoCut reduces optimality gap by 17-57% within a fixed time. It obtains the same solutions up to 4 times as fast, and obtains higher-quality solutions within the same time limit. Requiring no human expert input, EvoCut reliably generates, improves, and empirically verifies cuts that generalize to unseen instances. The code is available at https://github.com/milad1378yz/EvoCut.

Related papers

• Applying a Random-Key Optimizer on Mixed Integer Programs [0.36700088931938835]
  Mixed-Integer Programs (MIPs) are NP-hard optimization models that arise in a broad range of decision-making applications.<n>This paper explores the use of the Random-Key integer (RKO) framework as a flexible, metaheuristic alternative for computing high-quality solutions to MIPs.
  arXiv  Detail & Related papers  (2026-02-25T18:20:03Z)
• Learning to Refine: Self-Refinement of Parallel Reasoning in LLMs [102.48588475875749]
  We introduce Generative Self-Refinement (GSR), a novel parallel test-time scaling framework.<n>GSR generates a set of candidate responses in parallel and then performs self-refinement to synthesize a new superior solution.<n>We show that our method achieves state-of-the-art performance across five mathematical benchmarks.
  arXiv  Detail & Related papers  (2025-08-27T06:51:48Z)
• e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving [12.1096064802958]
  E-graphs have attracted interest in many fields, particularly in logic synthesis and formal verification.<n>We present e-boost, a novel framework that bridges this gap through three key innovations.<n>e-boost demonstrates 558x runtime speedup over traditional exact approaches (ILP) and 19.04% performance improvement over the state-of-the-art extraction framework (SmoothE)
  arXiv  Detail & Related papers  (2025-08-18T15:38:12Z)
• Scalable Best-of-N Selection for Large Language Models via Self-Certainty [65.31658824274894]
  Best-of-N selection is a key technique for improving the reasoning performance of Large Language Models.<n>We propose self-certainty, a novel and efficient metric to estimate response quality without requiring external reward models.<n>Our findings establish self-certainty as a practical and efficient way for improving LLM reasoning capabilities.
  arXiv  Detail & Related papers  (2025-02-25T19:08:07Z)
• V-STaR: Training Verifiers for Self-Taught Reasoners [71.53113558733227]
  V-STaR trains a verifier using DPO that judges correctness of model-generated solutions. Running V-STaR for multiple iterations results in progressively better reasoners and verifiers.
  arXiv  Detail & Related papers  (2024-02-09T15:02:56Z)
• Guided Evolution with Binary Discriminators for ML Program Search [64.44893463120584]
  We propose guiding evolution with a binary discriminator, trained online to distinguish which program is better given a pair of programs. We demonstrate our method can speed up evolution across a set of diverse problems including a 3.7x speedup on the symbolic search for MLs and a 4x speedup for RL loss functions.
  arXiv  Detail & Related papers  (2024-02-08T16:59:24Z)
• Genetic-based Constraint Programming for Resource Constrained Job Scheduling [5.068093754585243]
  Resource constrained job scheduling is a hard computation optimisation problem that originates in the mining industry. Off-the-shelf solutions cannot solve this problem satisfactorily in reasonable timeframes. This paper proposes a genetic programming algorithm to discover efficient search strategies of constraint programming.
  arXiv  Detail & Related papers  (2024-02-01T09:57:38Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Neuroevolution of Physics-Informed Neural Nets: Benchmark Problems and Comparative Results [25.12291688711645]
  Physics-informed neural networks (PINNs) are one of the key techniques at the forefront of recent advances. PINNs' unique loss formulations lead to a high degree of complexity and ruggedness that may not be conducive for gradient descent. Neuroevolution algorithms, with their superior global search capacity, may be a better choice for PINNs.
  arXiv  Detail & Related papers  (2022-12-15T05:54:16Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• Learning to Select Cuts for Efficient Mixed-Integer Programming [46.60355046375608]
  We propose a data-driven and generalizable cut selection approach, named Cut Ranking, in the settings of multiple instance learning. Cut Ranking has been deployed in an industrial solver for large-scale MIPs. It has achieved the average speedup ratio of 12.42% over the production solver without any accuracy loss of solution.
  arXiv  Detail & Related papers  (2021-05-28T07:48:34Z)
• Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem [0.0]
  This paper characterizes and discusses devolutionary genetic algorithms and evaluates their performances in solving the minimum labeling Steiner tree (MLST) problem. We define devolutionary algorithms as the process of reaching a feasible solution by devolving a population of super-optimal unfeasible solutions over time. We show how classical evolutionary concepts, such as crossing, mutation and fitness can be adapted to aim at reaching an optimal or close-to-optimal solution.
  arXiv  Detail & Related papers  (2020-04-18T13:27:28Z)

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.