論文の概要: Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction

• arxiv url: http://arxiv.org/abs/2501.00307v1
• Date: Tue, 31 Dec 2024 06:50:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-05 17:16:16.017687
• Title: Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction
• Title（参考訳）: 学習モデル還元による高速かつ解釈可能な混合整数線形計画解法
• Authors: Yixuan Li, Can Chen, Jiajun Li, Jiahui Duan, Xiongwei Han, Tao Zhong, Vincent Chau, Weiwei Wu, Wanyuan Wang,
• Abstract要約: 本稿では,MILPの縮小モデルと等価モデルを中間段階として学習することを目的とする。 縮小モデルはしばしば解釈可能な操作に対応しており、既存の商用解法よりもはるかに高速に大規模MILP問題を解くことができる。 本稿では,モデル縮小学習タスクの性能向上に寄与する嗜好情報を捕捉し,表現するための注意機構を提案する。
• 参考スコア（独自算出の注目度）: 24.3088703166792
• License:
• Abstract: By exploiting the correlation between the structure and the solution of Mixed-Integer Linear Programming (MILP), Machine Learning (ML) has become a promising method for solving large-scale MILP problems. Existing ML-based MILP solvers mainly focus on end-to-end solution learning, which suffers from the scalability issue due to the high dimensionality of the solution space. Instead of directly learning the optimal solution, this paper aims to learn a reduced and equivalent model of the original MILP as an intermediate step. The reduced model often corresponds to interpretable operations and is much simpler, enabling us to solve large-scale MILP problems much faster than existing commercial solvers. However, current approaches rely only on the optimal reduced model, overlooking the significant preference information of all reduced models. To address this issue, this paper proposes a preference-based model reduction learning method, which considers the relative performance (i.e., objective cost and constraint feasibility) of all reduced models on each MILP instance as preferences. We also introduce an attention mechanism to capture and represent preference information, which helps improve the performance of model reduction learning tasks. Moreover, we propose a SetCover based pruning method to control the number of reduced models (i.e., labels), thereby simplifying the learning process. Evaluation on real-world MILP problems shows that 1) compared to the state-of-the-art model reduction ML methods, our method obtains nearly 20% improvement on solution accuracy, and 2) compared to the commercial solver Gurobi, two to four orders of magnitude speedups are achieved.
• Abstract（参考訳）: 混合整数線形計画法(MILP)の構造と解の相関を利用して機械学習(ML)は大規模MILP問題の解法として有望な方法となっている。 既存のMLベースのMILPソルバは、主にエンドツーエンドのソリューション学習に焦点を当てており、ソリューション空間の高次元性に起因するスケーラビリティの問題に悩まされている。 本論文は,最適解を直接学習する代わりに,従来のMILPの縮小モデルと等価モデルを中間段階として学習することを目的とする。 縮小モデルはしばしば解釈可能な操作に対応しており、既存の商用解法よりもはるかに高速に大規模MILP問題を解くことができる。 しかし、現在のアプローチは、全ての縮小されたモデルの重要な嗜好情報を見越して、最適還元モデルのみに依存している。 そこで本研究では,MILPインスタンスごとのモデル全体の相対的性能(客観的コストと制約実現可能性)を嗜好として考慮した,嗜好に基づくモデル還元学習手法を提案する。 また、嗜好情報をキャプチャして表現するための注意機構を導入し、モデル縮小学習タスクの性能向上に寄与する。 さらに,削減されたモデル数(ラベルなど)を制御するためのSetCoverベースのプルーニング手法を提案し,学習プロセスを簡素化する。 実世界のMILP問題の評価は、そのことを示している。 1) 最先端モデル削減ML法と比較すると, 解の精度が約20%向上し, 精度が向上した。 2) 市販のグロビと比較して, 2～4桁のスピードアップが達成された。

関連論文リスト

• Majorization-Minimization Dual Stagewise Algorithm for Generalized Lasso [2.1066879371176395]
  本稿では,一般化ラッソ問題の全解経路を効率的に追従するために,一般化最小化二段階法(MM-DUST)アルゴリズムを提案する。 我々は,MM-DUSTの計算複雑性を解析し,近似解経路の一様収束性を確立する。
  論文  参考訳（メタデータ） (2025-01-04T05:20:26Z)
• Towards An Unsupervised Learning Scheme for Efficiently Solving Parameterized Mixed-Integer Programs [6.1860817947800655]
  教師なし学習方式でバイナリ変数の自動エンコーダを訓練する。 オフライン学習AEのデコーダパラメータから平面制約を切断するクラスを構築する戦略を提案する。 原始的なMIP問題への統合は、実現可能な領域を縮小したMIPの強化につながる。
  論文  参考訳（メタデータ） (2024-12-23T14:48:32Z)
• Multi-task Representation Learning for Mixed Integer Linear Programming [13.106799330951842]
  本稿では,ML誘導MILP問題解決のためのマルチタスク学習フレームワークについて紹介する。 我々は,マルチタスク学習モデルが同一分布内の特殊モデルと類似して動作することを示す。 これは、問題のサイズやタスクの一般化において、それらを著しく上回る。
  論文  参考訳（メタデータ） (2024-12-18T23:33:32Z)
• RL-MILP Solver: A Reinforcement Learning Approach for Solving Mixed-Integer Linear Programs with Graph Neural Networks [3.3894236476098185]
  混合整数線形プログラミング (MILP) は様々な分野にまたがる最適化手法である。 本稿では,最初の実現可能な解を見つけるだけでなく,より有効な解を段階的に発見する新しい強化学習(RL)に基づく解法を提案する。
  論文  参考訳（メタデータ） (2024-11-29T07:23:34Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。 本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。 これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
  論文  参考訳（メタデータ） (2024-03-06T04:43:22Z)
• Zero-Shot Sharpness-Aware Quantization for Pre-trained Language Models [88.80146574509195]
  量子化は、メモリオーバーヘッドを減らし、推論を加速するための有望なアプローチである。 種々のPLMのゼロショット量子化のための新しい量子化(ZSAQ)フレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-20T07:09:56Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。 汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。 我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
  論文  参考訳（メタデータ） (2023-10-10T01:39:04Z)
• 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)
• Sufficiently Accurate Model Learning for Planning [119.80502738709937]
  本稿では,制約付きSufficiently Accurateモデル学習手法を提案する。 これはそのような問題の例を示し、いくつかの近似解がいかに近いかという定理を提示する。 近似解の質は、関数のパラメータ化、損失と制約関数の滑らかさ、モデル学習におけるサンプルの数に依存する。
  論文  参考訳（メタデータ） (2021-02-11T16:27:31Z)
• An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives [54.29001037565384]
  本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。 本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
  論文  参考訳（メタデータ） (2020-06-17T20:19:25Z)

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

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