論文の概要: Interpretable Cutting Plane Selection for Mixed-Integer Linear Programming Using Genetic Programming
- arxiv url: http://arxiv.org/abs/2610.29311v1
- Date: Wed, 21 Oct 2026 07:06:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-23 00:40:06.267017
- Title: Interpretable Cutting Plane Selection for Mixed-Integer Linear Programming Using Genetic Programming
- Title（参考訳）: 遺伝的プログラミングを用いた混合整数線形計画法における解釈可能なカット平面選択
- Abstract要約: カット平面(カット)は混合整数線形プログラム(MILP)から分数解を除去する
現在の最先端の解法は、細調整された手作りのカット戦略に依存している。
GPSCSは、手作業によるカット選択を完全に解釈可能なポリシーに明示的に一般化する、最初の学習ベースのフレームワークである。
- 参考スコア（独自算出の注目度）: 4.697267141773321
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Cutting planes (cuts) remove fractional solutions from mixed-integer linear programs (MILPs) without excluding any feasible integer solutions, making them a key ingredient in modern MILP solvers. Current state-of-the-art solvers rely on fine-tuned handcrafted cut strategies, which, despite their effectiveness, remain inherently static and can be suboptimal. More recently, learning-based approaches have been proposed to design adaptive cut strategies; however, most of these methods are based on neural networks, offering limited interpretability and providing no guarantees of convergence. In this paper, we propose \emph{Genetic Programming and Statistics-based Cut Selection} (GPSCS), the first learning-based framework that explicitly generalizes handcrafted cut selection heuristics into a fully interpretable policy. First, a genetic programming model evolves a symbolic scoring function that ranks candidate cuts using features derived from the cuts and the solving context. Second, a lightweight statistics-based mechanism adaptively determines the number of top-ranked cuts to add at each separation round by detecting significant score dropouts. We evaluate GPSCS within the SCIP solver on seven classes of synthetic and real-world benchmark instances, with a strong emphasis on generalization: evaluation instances are on average 41 times harder than those used for training. Experimental results show that GPSCS improves average solving time by $6\%$ compared to SCIP's default cut selection strategy and achieves a two-fold speedup over both a recent neural-network-based approach and a no-cut baseline, demonstrating strong robustness and generalization across heterogeneous MILP families.
- Abstract（参考訳）: カット平面(カット)は、可能な整数解を排除せずに混合整数線形プログラム(MILP)から分数解を除去し、現代のMILP解法において重要な要素となる。
現在の最先端の解法は、細調整された手作りのカット戦略に依存しており、その効果にもかかわらず、本質的に静的であり、準最適である。
最近では、適応的なカット戦略を設計するための学習ベースのアプローチが提案されているが、これらの手法のほとんどはニューラルネットワークに基づいており、限定的な解釈可能性を提供し、収束の保証を提供していない。
本稿では,手作りカット選択ヒューリスティックスを完全に解釈可能なポリシーに明示的に一般化した最初の学習ベースフレームワークである,GPSCS(emph{Genetic Programming and Statistics-based Cut Selection})を提案する。
まず、遺伝的プログラミングモデルは、カットと解決コンテキストから派生した特徴を用いて、候補カットをランク付けするシンボルスコアリング関数を進化させる。
第二に、軽量統計に基づくメカニズムは、各分離ラウンドにおいて、重要なスコアのドロップアウトを検出して、トップランクのカット数を適応的に決定する。
SCIPソルバ内のGPSCSを,7種類の総合的および実世界のベンチマークインスタンスで評価する。
実験結果から,GPSCSはSCIPのデフォルトカット選択戦略と比較して平均解法時間を6倍に改善し,最近のニューラルネットワークベースのアプローチとノーカットベースラインの両方に対して2倍の高速化を実現し,異種MILPファミリー間の堅牢性と一般化を実証した。
関連論文リスト
- Using Weisfeiler-Leman Features for Algorithm Selection in Constraint Optimisation [1.052782170493037]
本稿では,グラフ変換とWeisfeiler-Lehmanグラフカーネルを統合した自動特徴抽出手法を提案する。
我々の主な貢献は、構造分割をモデル化し、よりニュアンスな予測信号を提供するために設計されたカットベース表現(textttWLc)である。
論文 参考訳（メタデータ） (2026-10-08T15:16:16Z) - Generalized Optimal Classification Trees: A Mixed-Integer Programming Approach [17.725629133949955]
混合整数プログラミング(MIP)は高度なモデリングの柔軟性を提供する。
非線形性能指標に基づく最適分類木学習のためのMIPベースのフレームワークを提案する。
提案手法を50のベンチマークデータセットで評価した。
論文 参考訳（メタデータ） (2026-02-02T14:46:01Z) - LOP: Learning Optimal Pruning for Efficient On-Demand MLLMs Scaling [52.1366057696919]
LOPは、ターゲットプルーニング制約から最適なプルーニング戦略を学ぶ、効率的なニューラルプルーニングフレームワークである。
LOPアプローチでは、自動回帰ニューラルネットワーク(NN)を使用して、ターゲットプルーニング制約に適応したレイヤワイズプルーニング戦略を直接予測する。
実験の結果,LOPは最大3桁のスピードアップを達成しつつ,様々な測定値において最先端のプルーニング手法よりも優れていた。
論文 参考訳（メタデータ） (2025-06-15T12:14:16Z) - Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming [35.5099165939453]
混合整数計画法(MIP)では、分枝・分枝・分枝(B&C)アルゴリズムには切断平面が不可欠である。
本稿では,二部グラフを用いて探索木を表現し,グラフニューラルネットワークと強化学習を組み合わせてカット選択戦略を開発するGCSを提案する。
実験により、GCSは従来の学習手法と比較して、合成および大規模現実世界のMIPの解法効率を著しく改善することが示された。
論文 参考訳（メタデータ） (2025-03-20T04:59:18Z) - Towards An Unsupervised Learning Scheme for Efficiently Solving Parameterized Mixed-Integer Programs [6.1860817947800655]
教師なし学習方式でバイナリ変数の自動エンコーダを訓練する。
オフライン学習AEのデコーダパラメータから平面制約を切断するクラスを構築する戦略を提案する。
原始的なMIP問題への統合は、実現可能な領域を縮小したMIPの強化につながる。
論文 参考訳（メタデータ） (2024-12-23T14:48:32Z) - Learning to Remove Cuts in Integer Linear Programming [57.15699051569638]
本研究では, 学習可能なパラメトリック基準の下で, 手法の前回の繰り返しで導入された前回のカットの除去について検討する。
基本的な最適化設定では、カット削除ポリシーは、ヒューマンベースおよび機械学習誘導のカット追加ポリシーよりも大幅に改善される可能性があることを実証する。
論文 参考訳（メタデータ） (2024-06-26T22:50:43Z) - General Cutting Planes for Bound-Propagation-Based Neural Network
Verification [144.7290035694459]
任意の切削平面制約を加えることができるような境界伝搬手順を一般化する。
MIPソルバは、境界プロパゲーションベースの検証器を強化するために高品質な切削面を生成することができる。
本手法は,oval20ベンチマークを完全解き,oval21ベンチマークの2倍のインスタンスを検証できる最初の検証器である。
論文 参考訳（メタデータ） (2022-08-11T10:31:28Z) - COPS: Controlled Pruning Before Training Starts [68.8204255655161]
最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。
この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
論文 参考訳（メタデータ） (2021-07-27T08:48:01Z) - Learning to Select Cuts for Efficient Mixed-Integer Programming [46.60355046375608]
複数インスタンス学習の設定において,データ駆動型で一般化可能なカット選択手法であるカットランキングを提案する。
カットランキングは、大規模MIPのための産業用解決器に展開されている。
解法の平均スピードアップ比は12.42%に達し、解の精度を損なうことなく製造された。
論文 参考訳（メタデータ） (2021-05-28T07:48:34Z) - Revisiting LSTM Networks for Semi-Supervised Text Classification via
Mixed Objective Function [106.69643619725652]
我々は,単純なBiLSTMモデルであっても,クロスエントロピー損失でトレーニングした場合に,競争的な結果が得られるようなトレーニング戦略を開発する。
いくつかのベンチマークデータセット上で,テキスト分類タスクの最先端結果について報告する。
論文 参考訳（メタデータ） (2020-09-08T21:55:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。