論文の概要: Designing faster mixed integer linear programming algorithm via learning the optimal path

• arxiv url: http://arxiv.org/abs/2601.16056v1
• Date: Thu, 22 Jan 2026 15:41:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-23 21:37:20.639726
• Title: Designing faster mixed integer linear programming algorithm via learning the optimal path
• Title（参考訳）: 最適経路学習による高速混合整数線形計画法の設計
• Authors: Ruizhi Liu, Liming Xu, Xulin Huang, Jingyan Sui, Shizhe Ding, Boyang Xia, Chungong Yu, Dongbo Bu,
• Abstract要約: DeepBoundは、MILP(Mixed-Integer Linear Programming)問題を解決するためのディープラーニングベースのアルゴリズムである。 最適なソリューションを含むノードを優先順位付けすることで、解決効率が向上する。 従来のルールや既存の学習ベースアプローチよりも優れた解法効率を実現する。
• 参考スコア（独自算出の注目度）: 11.732011034176233
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Designing faster algorithms for solving Mixed-Integer Linear Programming (MILP) problems is highly desired across numerous practical domains, as a vast array of complex real-world challenges can be effectively modeled as MILP formulations. Solving these problems typically employs the branch-and-bound algorithm, the core of which can be conceived as searching for a path of nodes (or sub-problems) that contains the optimal solution to the original MILP problem. Traditional approaches to finding this path rely heavily on hand-crafted, intuition-based heuristic strategies, which often suffer from unstable and unpredictable performance across different MILP problem instances. To address this limitation, we introduce DeepBound, a deep learning-based node selection algorithm that automates the learning of such human intuition from data. The core of DeepBound lies in learning to prioritize nodes containing the optimal solution, thereby improving solving efficiency. DeepBound introduces a multi-level feature fusion network to capture the node representations. To tackle the inherent node imbalance in branch-and-bound trees, DeepBound employs a pairwise training paradigm that enhances the model's ability to discriminate between nodes. Extensive experiments on three NP-hard MILP benchmarks demonstrate that DeepBound achieves superior solving efficiency over conventional heuristic rules and existing learning-based approaches, obtaining optimal feasible solutions with significantly reduced computation time. Moreover, DeepBound demonstrates strong generalization capability on large and complex instances. The analysis of its learned features reveals that the method can automatically discover more flexible and robust feature selection, which may effectively improve and potentially replace human-designed heuristic rules.
• Abstract（参考訳）: MILP(Mixed-Integer Linear Programming)問題を解くためのより高速なアルゴリズムを設計することは、MILPの定式化として効果的にモデル化できるため、多くの実践領域で非常に望まれる。 これらの問題の解法は、通常、分岐とバウンドのアルゴリズムを用いており、その中核は元のMILP問題に対する最適解を含むノード(またはサブプロブレム)の探索として考えられる。 この経路を見つけるための従来のアプローチは手作りの直観に基づくヒューリスティック戦略に大きく依存しており、しばしば様々なMILP問題インスタンスで不安定で予測不能なパフォーマンスに悩まされる。 この制限に対処するために、深層学習に基づくノード選択アルゴリズムであるDeepBoundを導入し、データからの人間の直観の学習を自動化する。 DeepBoundの中核は、最適なソリューションを含むノードの優先順位付けを学習することにある。 DeepBoundはノード表現をキャプチャするマルチレベル機能融合ネットワークを導入した。 ブランチとバウンドツリーの固有のノード不均衡に対処するため、DeepBoundでは、モデルがノード間で識別する能力を向上する、ペアワイズトレーニングパラダイムを採用している。 3つのNPハードMILPベンチマークの大規模な実験により、DeepBoundは従来のヒューリスティックなルールや既存の学習ベースアプローチよりも優れた解法効率を実現し、計算時間を著しく短縮した最適実現可能な解が得られることを示した。 さらに、DeepBoundは大規模で複雑なインスタンスに対して強力な一般化能力を示す。 学習した特徴を分析してみると、この手法は柔軟で堅牢な特徴選択を自動的に発見し、人間の設計したヒューリスティックなルールを効果的に改善し、置き換える可能性があることが分かる。

関連論文リスト

• BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems [7.196057722218442]
  制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。 COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。 提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
  論文  参考訳（メタデータ） (2023-12-26T03:09:08Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• A multiobjective continuation method to compute the regularization path of deep neural networks [1.3654846342364308]
  数値効率を保証し、モデルの解釈性を改善し、堅牢性を向上させるため、ディープニューラルネットワーク(DNN)では、スパシティは高い特徴である。 本稿では,数百万のパラメータを持つ高次元勾配に対して,上述の目的に対するスパースフロント全体を極めて効率的な方法で実現するアルゴリズムを提案する。 正規化パスの知識がネットワークパラメトリゼーションを十分に一般化することを示す。
  論文  参考訳（メタデータ） (2023-08-23T10:08:52Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。 古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。 提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
  論文  参考訳（メタデータ） (2020-06-15T02:57:57Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。