論文の概要: Design and Implementation of an Heuristic-Enhanced Branch-and-Bound Solver for MILP

• arxiv url: http://arxiv.org/abs/2206.01857v1
• Date: Sat, 4 Jun 2022 00:09:02 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-07 17:20:22.980822
• Title: Design and Implementation of an Heuristic-Enhanced Branch-and-Bound Solver for MILP
• Title（参考訳）: MILP用ヒューリスティック分岐境界解法の設計と実装
• Authors: Warley Almeida Silva, Federico Bobbio, Flore Caye, Defeng Liu, Justine Pepin, Carl Perreault-Lafleur, William St-Arnaud
• Abstract要約: MIPコンペティションのために開発したMixed Programs (MIP) の解法について述べる。 コンペティションのルールによって確立された計算時間に制限された10分間を考慮し、本手法は実現可能な解を見つけることに焦点を当てる。 計算能力の広い組み合わせにより、トレーニングデータセットの19の問題の11を解くことができる。
• 参考スコア（独自算出の注目度）: 1.03905835096574
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We present a solver for Mixed Integer Programs (MIP) developed for the MIP competition 2022. Given the 10 minutes bound on the computational time established by the rules of the competition, our method focuses on finding a feasible solution and improves it through a Branch-and-Bound algorithm. Another rule of the competition allows the use of up to 8 threads. Each thread is given a different primal heuristic, which has been tuned by hyper-parameters, to find a feasible solution. In every thread, once a feasible solution is found, we stop and we use a Branch-and-Bound method, embedded with local search heuristics, to ameliorate the incumbent solution. The three variants of the Diving heuristic that we implemented manage to find a feasible solution for 10 instances of the training data set. These heuristics are the best performing among the heuristics that we implemented. Our Branch-and-Bound algorithm is effective on a small portion of the training data set, and it manages to find an incumbent feasible solution for an instance that we could not solve with the Diving heuristics. Overall, our combined methods, when implemented with extensive computational power, can solve 11 of the 19 problems of the training data set within the time limit. Our submission to the MIP competition was awarded the "Outstanding Student Submission" honorable mention.
• Abstract（参考訳）: 本稿では,MIPコンペティション2022のために開発されたMixed Integer Programs(MIP)について述べる。 コンペティションのルールによって確立された計算時間に10分を割って考えると、本手法は実現可能な解を見つけ、分岐境界アルゴリズムにより改善することに焦点を当てる。 コンペティションの別のルールは、最大8スレッドの使用を可能にする。 各スレッドは、実現可能な解を見つけるために、ハイパーパラメータによって調整された異なる基本ヒューリスティックを与える。 すべてのスレッドで、実現可能なソリューションが見つかると停止し、ローカル検索ヒューリスティックを組み込んだブランチ・アンド・バウンドメソッドを使用して、既存のソリューションを改善する。 私たちが実装したダイビングヒューリスティックの3つの変種は、トレーニングデータセットの10インスタンスに対して実現可能なソリューションを見つけることができました。 これらのヒューリスティックスは、我々が実施したヒューリスティックの中で最高のパフォーマンスである。 我々のブランチ・アンド・バウンドアルゴリズムはトレーニングデータセットのごく一部で有効であり、Divingヒューリスティックスでは解けないインスタンスに対して、既存の実現可能な解を見つけることができる。 全体として,計算能力の広範な実装を行う場合,学習データセットの19問題のうち11問題を時間制限内で解くことができる。 mipコンペティションへの私たちの応募は、"outstanding student submit"を授与されました。

関連論文リスト

• Quantum Algorithms for Drone Mission Planning [0.0]
  ミッションプランニングはしばしば、一連のミッション目標を達成するためにISR(Intelligence, Surveillance and Reconnaissance)資産の使用を最適化する。 このような解を見つけることはNP-Hard問題であり、古典的なコンピュータでは効率的に解けないことが多い。 我々は、現在の古典的手法に対してスピードアップを提供する可能性のある、短期量子アルゴリズムについて検討する。
  論文  参考訳（メタデータ） (2024-09-27T10:58:25Z)
• Interpretable Decision Tree Search as a Markov Decision Process [8.530182510074983]
  教師付き学習タスクに最適な決定木を見つけることは、大規模に解決する上で難しい問題である。 近年、マルコフ決定問題 (MDP) としてこの問題の枠組みを定め、深層強化学習を用いてスケーリングに取り組むことが提案されている。 そこで我々は,全ての状態に対して生成する情報理論テスト生成関数を用いて,MDPの分解能を拡大する手法を提案する。
  論文  参考訳（メタデータ） (2023-09-22T08:18:08Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• A Novel Approach for Auto-Formulation of Optimization Problems [66.94228200699997]
  Natural Language for Optimization (NL4Opt) NeurIPS 2022コンペティションでは、最適化ソルバのアクセシビリティとユーザビリティの改善に重点を置いている。 本稿では,チームのソリューションについて述べる。 提案手法は,サブタスク1のF1スコアとサブタスク2の0.867の精度を達成し,それぞれ第4位,第3位を獲得した。
  論文  参考訳（メタデータ） (2023-02-09T13:57:06Z)
• The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights [59.93939636422896]
  ML4COは、キーコンポーネントを置き換えることで最先端の最適化問題を解決することを目的としている。 このコンペティションでは、最高の実現可能なソリューションを見つけること、最も厳密な最適性証明書を生成すること、適切なルーティング設定を提供すること、という3つの課題があった。
  論文  参考訳（メタデータ） (2022-03-04T17:06:00Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
  ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。 すべての予測と最適化アプローチのボトルネックに対処する。 非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-11-10T19:09:12Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
  論文  参考訳（メタデータ） (2020-10-31T18:19:29Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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