論文の概要: EvoCut: Strengthening Integer Programs via Evolution-Guided Language Models
- arxiv url: http://arxiv.org/abs/2508.11850v1
- Date: Sat, 16 Aug 2025 00:13:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-19 14:49:10.412884
- Title: EvoCut: Strengthening Integer Programs via Evolution-Guided Language Models
- Title（参考訳）: EvoCut:進化誘導言語モデルによる整数プログラムの強化
- Authors: Milad Yazdani, Mahdi Mostajabdaveh, Samin Aref, Zirui Zhou,
- Abstract要約: 整数プログラムを実際に解くための効果的なアプローチは、アクセラレーションカットの手動設計である。
提案するフレームワークであるEvoCutは,大規模言語モデルと進化的検索を組み合わせることで,アクセラレーションカットの生成を自動化する。
EvoCutは、目に見えないインスタンスに一般化するカットを確実に生成し、改善し、実証的に検証する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 整数プログラミングは、重要な組合せ最適化タスクの中心にあるが、NPハードな性質のため、依然として困難である。
整数プログラムを実際に解くための効果的なアプローチは、アクセラレーションカットのマニュアル設計である。
しかし、この創造的なプロセスは深い専門知識を必要としており、まだ自動化されていない。
提案するフレームワークであるEvoCutは,大規模言語モデル(LLM)と進化的検索を組み合わせることで,加速度カットの生成を自動化する。
EvoCut
i) LLMをベースとした初期化剤により、多様な候補カットの個体群を初期化する。
(ii) 各カットにおいて最適解の保存と,検証セットをまたいだ分数解の切断能力の両立を実証的に評価し,
三 進化的交叉及び突然変異剤により個体群を反復的に精製すること。
我々は, 各カットの効用を, ソルバの最適性ギャップを相対的に減少させることで定量化する。
通常の整数プログラミングと比較すると、EvoCutは一定時間内に最適性ギャップを17～57%削減する。
同じ解が最大4倍の速さで得られ、同じ時間内に高品質な解が得られる。
人間の専門家の入力を必要としないEvoCutは、目に見えないインスタンスに一般化するカットを確実に生成し、改善し、実証的に検証する。
コードはhttps://github.com/milad1378yz/EvoCut.comで公開されている。
関連論文リスト
- e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving [12.1096064802958]
Eグラフは多くの分野、特に論理合成と形式的検証に興味を寄せている。
このギャップを3つの重要なイノベーションで埋める新しいフレームワークであるe-boostを紹介します。
e-boostは、従来の正確なアプローチ(ILP)よりも58倍のランタイムスピードアップを示し、最先端の抽出フレームワーク(SmoothE)よりも19.04%パフォーマンスが改善された。
論文 参考訳（メタデータ） (2025-08-18T15:38:12Z) - Scalable Best-of-N Selection for Large Language Models via Self-Certainty [65.31658824274894]
Best-of-N選択は、大規模言語モデルの推論性能を改善するための重要なテクニックである。
本稿では,外部報酬モデルを必要とすることなく,応答品質を推定する新規かつ効率的な指標である自己確実性を提案する。
本研究は, LLM推論能力を向上させるための実用的で効率的な方法として, 自己確実性を確立した。
論文 参考訳（メタデータ） (2025-02-25T19:08:07Z) - V-STaR: Training Verifiers for Self-Taught Reasoners [71.53113558733227]
V-STaR はモデル生成解の正しさを判断する DPO を用いて検証器を訓練する。
複数のイテレーションでV-STaRを実行すると、徐々により良い推論器と検証器が得られる。
論文 参考訳（メタデータ） (2024-02-09T15:02:56Z) - Guided Evolution with Binary Discriminators for ML Program Search [64.44893463120584]
プログラムのペアがどのプログラムの方が優れているかを識別するために、オンラインで訓練された二項判別器による指導進化を提案する。
本稿では,MLの記号探索における3.7倍の高速化,RL損失関数の4倍の高速化など,様々な問題に対する進化の高速化を実証する。
論文 参考訳（メタデータ） (2024-02-08T16:59:24Z) - Genetic-based Constraint Programming for Resource Constrained Job
Scheduling [5.068093754585243]
資源制約されたジョブスケジューリングは、鉱業に起源を持つ計算の最適化問題である。
既成のソリューションはこの問題を合理的な時間枠で十分解決できない。
本稿では,制約プログラミングの効率的な探索手法を探索する遺伝的プログラミングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-01T09:57:38Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Neuroevolution of Physics-Informed Neural Nets: Benchmark Problems and
Comparative Results [25.12291688711645]
物理インフォームドニューラルネットワーク(PINN)は、最近の進歩の最前線にある重要な技術の一つである。
PINNのユニークな損失の定式化は、勾配降下に寄与しない高い複雑さと頑丈さをもたらす。
優れたグローバル検索能力を持つ神経進化アルゴリズムは、PINNにとってより良い選択であるかもしれない。
論文 参考訳（メタデータ） (2022-12-15T05:54:16Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳（メタデータ） (2022-10-31T09:46:26Z) - Learning to Select Cuts for Efficient Mixed-Integer Programming [46.60355046375608]
複数インスタンス学習の設定において,データ駆動型で一般化可能なカット選択手法であるカットランキングを提案する。
カットランキングは、大規模MIPのための産業用解決器に展開されている。
解法の平均スピードアップ比は12.42%に達し、解の精度を損なうことなく製造された。
論文 参考訳（メタデータ） (2021-05-28T07:48:34Z) - Devolutionary genetic algorithms with application to the minimum
labeling Steiner tree problem [0.0]
本稿では、進化的遺伝的アルゴリズムを特徴付けるとともに、最小ラベル付けスタイナーツリー(MLST)問題を解く際の性能を評価する。
我々は、進化的アルゴリズムを、時間とともに超最適で実現不可能な解の集団を進化させることによって実現可能な解に到達する過程として定義する。
我々は, 交叉, 突然変異, 適合性などの古典的進化的概念が, 最適解, 最適解に到達するためにどのように適応できるかを示す。
論文 参考訳（メタデータ） (2020-04-18T13:27:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。