論文の概要: New Characterizations and Efficient Local Search for General Integer Linear Programming

• arxiv url: http://arxiv.org/abs/2305.00188v3
• Date: Tue, 20 Jun 2023 04:14:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-22 02:43:53.360239
• Title: New Characterizations and Efficient Local Search for General Integer Linear Programming
• Title（参考訳）: 一般整数線形計画法の新しい特徴と効率的な局所探索
• Authors: Peng Lin, Shaowei Cai, Mengchuan Zou, Jinkun Lin
• Abstract要約: Local-ILPは、大規模な異種問題データセット上で検証された最初のローカル検索解決器である。 本稿では,検索,改善,再ストアという3つのモードを切り替える新しいローカル検索フレームワークを提案する。 MIPLIBデータセットで行った実験は、大規模ハード整数線形計画問題の解法の有効性を示した。
• 参考スコア（独自算出の注目度）: 22.381435196829184
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Integer linear programming (ILP) models a wide range of practical combinatorial optimization problems and has significant impacts in industry and management sectors. This work proposes new characterizations of ILP with the concept of boundary solutions. Motivated by the new characterizations, we develop an efficient local search solver, which is the first local search solver for general ILP validated on a large heterogeneous problem dataset. We propose a new local search framework that switches between three modes, namely Search, Improve, and Restore modes. We design tailored operators adapted to different modes, thus improving the quality of the current solution according to different situations. For the Search and Restore modes, we propose an operator named tight move, which adaptively modifies variables' values, trying to make some constraint tight. For the Improve mode, an efficient operator lift move is proposed to improve the quality of the objective function while maintaining feasibility. Putting these together, we develop a local search solver for integer linear programming called Local-ILP. Experiments conducted on the MIPLIB dataset show the effectiveness of our solver in solving large-scale hard integer linear programming problems within a reasonably short time. Local-ILP is competitive and complementary to the state-of-the-art commercial solver Gurobi and significantly outperforms the state-of-the-art non-commercial solver SCIP. Moreover, our solver establishes new records for 6 MIPLIB open instances. The theoretical analysis of our algorithm is also presented, which shows our algorithm could avoid visiting unnecessary regions and also maintain good connectivity of targeted solutions.
• Abstract（参考訳）: 整数線形プログラミング(ilp)は、様々な実用的組合せ最適化問題をモデル化し、産業や経営分野に大きな影響を与える。 本研究は,境界解の概念を用いたILPの新たな特徴付けを提案する。 提案手法を応用した局所探索解法は,大規模な異種問題データセット上で検証された一般ILPの局所探索解法としては初めてである。 本研究では,検索モード,改善モード,復元モードの3つのモードを切り替えるローカル検索フレームワークを提案する。 異なるモードに適応した調整された演算子を設計し、状況に応じて現在のソリューションの品質を改善する。 探索・復元モードでは,変数の値を適応的に修正し,制約を厳格にしようとするtight moveという演算子を提案する。 改良モードでは, 有効性を維持しつつ, 目的関数の品質向上を図るために, 効率的な昇降動作が提案されている。 これらを組み合わせることで、ローカルILPと呼ばれる整数線形プログラミングのための局所探索解法を開発する。 MIPLIBデータセットで行った実験は,大規模ハード整数線形計画問題の解法の有効性を合理的に短時間で示すものである。 ローカルILPは最先端の商用ソルバであるGurobiと競合し相補的であり、最先端の非商用ソルバSCIPを著しく上回っている。 さらに,6つのMIPLIBオープンインスタンスの新たなレコードを確立する。 また,本アルゴリズムの理論的解析により,不要領域への接近を回避し,適切な解の接続性を維持することができることを示した。

関連論文リスト

• Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
  本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。 これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。 我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
  論文  参考訳（メタデータ） (2024-07-22T23:24:03Z)
• Learning to Control Local Search for Combinatorial Optimization [4.243592852049962]
  一般化の動物園と問題固有の局所探索の変種は、近似解を計算するのによく用いられる。 本稿では,そのような局所探索アルゴリズムの3つの独立したアルゴリズム的側面を同定し,最適化プロセス上でのシーケンシャルな選択を形式化する。 我々は、NeuroLSがオペレーティングリサーチの汎用ローカルサーチコントローラと最新の機械学習ベースのアプローチの両方より優れていることを示す。
  論文  参考訳（メタデータ） (2022-06-27T10:48:56Z)
• Flipping the switch on local exploration: Genetic Algorithms with Reversals [0.0]
  著者らは、勾配のない探索手法が離散領域における最適解を提供するのに適していることを示した。 また、複数のローカル検索を使用することで、ローカル検索のパフォーマンスが向上することを示した。 提案したGA変種は,提案した問題を含む全てのベンチマークにおいて,最小平均コストであり,ICが構成成分よりも優れた性能を発揮することが観察された。
  論文  参考訳（メタデータ） (2022-02-02T08:27:11Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• Memetic Search for Vehicle Routing with Simultaneous Pickup-Delivery and Time Windows [31.512563458410963]
  本稿では,この問題を解決するために,局所探索を効率的に行うメメティックアルゴリズム(MATE)を提案する。 MATEは最先端のアルゴリズムをすべて上回り、特に12インスタンス(合計65インスタンス)でよく知られた新しいソリューションを見つける。
  論文  参考訳（メタデータ） (2020-11-12T12:06:11Z)
• A global-local neighborhood search algorithm and tabu search for flexible job shop scheduling problem [3.946442574906068]
  この研究はGLNSA(Global-local neighborhood search algorithm)と呼ばれる新しいメタヒューリスティックアルゴリズムを提案する。 提案アルゴリズムは,Nopt1地区の簡易版を実装したタブ検索と補完する。 実験の結果,提案アルゴリズムの性能は,最近発表された他のアルゴリズムと比較すると良好であった。
  論文  参考訳（メタデータ） (2020-10-23T23:08:51Z)
• Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions [9.89901717499058]
  局所探索は基本的なアルゴリズムであり、様々な最適化問題に広く利用されている。 ローカライズ可能性の観点から,様々な制約の下で,標準的な局所探索アルゴリズムの近似保証を提供する。 本フレームワークの主な用途はスパース最適化であり, 強い凹凸や目的関数の滑らかさの制限は局所性を意味することを示す。
  論文  参考訳（メタデータ） (2020-06-02T05:37:52Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• A General Large Neighborhood Search Framework for Solving Integer Linear Programs [46.62993477453986]
  我々は整数プログラムの解法に重点を置いており、我々のアプローチは大規模近傍探索(SLN)パラダイムに根ざしている。 我々のLSSフレームワークは、Gurobiのような最先端の商用解法と比較して、大幅に性能が向上することを示した。
  論文  参考訳（メタデータ） (2020-03-29T23:08:14Z)

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

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