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

• arxiv url: http://arxiv.org/abs/2305.00188v4
• Date: Fri, 1 Mar 2024 05:56:59 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-04 14:42:31.413380
• Title: New Characterizations and Efficient Local Search for General Integer Linear Programming
• Title（参考訳）: 一般整数線形計画法の新しい特徴と効率的な局所探索
• Authors: Peng Lin, Shaowei Cai, Mengchuan Zou, Jinkun Lin
• Abstract要約: 本研究では境界解の概念を用いた線形プログラミング(ILP)の新たな特徴付けを提案する。 そこで我々は,局所探索アルゴリズムのLocal-ILPを開発した。 MIPLIBデータセットで行った実験は、大規模ハードILP問題の解法におけるアルゴリズムの有効性を示した。
• 参考スコア（独自算出の注目度）: 17.80124240223163
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Integer linear programming (ILP) models a wide range of practical combinatorial optimization problems and significantly impacts industry and management sectors. This work proposes new characterizations of ILP with the concept of boundary solutions. Motivated by the new characterizations, we develop a new local search algorithm Local-ILP, which is efficient for solving 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. Two new operators are proposed, namely the tight move and the lift move operators, which are associated with appropriate scoring functions. Different modes apply different operators to realize different search strategies and the algorithm switches between three modes according to the current search state. Putting these together, we develop a local search ILP solver called Local-ILP. Experiments conducted on the MIPLIB dataset show the effectiveness of our algorithm in solving large-scale hard ILP problems. In the aspect of finding a good feasible solution quickly, 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 algorithm 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.
• Abstract（参考訳）: Integer linear programming (ILP) は、様々な実用的な組合せ最適化問題をモデル化し、産業や管理分野に大きな影響を及ぼす。 本研究は,境界解の概念を用いたILPの新たな特徴付けを提案する。 そこで本研究では,新しい特徴量に着目した局所探索アルゴリズムlocal-ilpを開発した。 本研究では,検索モード,改善モード,復元モードの3つのモードを切り替えるローカル検索フレームワークを提案する。 2つの新しい演算子、すなわち、適切なスコアリング関数に関連するタイト移動とリフト移動演算子を提案する。 異なるモードは異なる演算子を適用して異なる検索戦略を実現し、アルゴリズムは現在の検索状態に応じて3つのモードを切り替える。 そこで我々はローカル検索型ILPソルバであるLocal-ILPを開発した。 MIPLIBデータセットで行った実験は、大規模ハードILP問題の解法におけるアルゴリズムの有効性を示した。 優れた実現可能な解を迅速に見つけるという側面において、Local-ILPは最先端の商用解法であるGurobiと競合し相補的であり、最先端の非商用解法SCIPを著しく上回っている。 さらに,提案アルゴリズムは,MIPLIBオープンインスタンス6個に対する新しいレコードを確立する。 また,本アルゴリズムの理論的解析を行い,不要な領域への接近を回避できることを示した。

関連論文リスト

• 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)

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

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