論文の概要: Competitive Facility Location under Random Utilities and Routing
Constraints
- arxiv url: http://arxiv.org/abs/2403.04264v2
- Date: Sat, 9 Mar 2024 20:17:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-12 17:23:20.773350
- Title: Competitive Facility Location under Random Utilities and Routing
Constraints
- Title（参考訳）: ランダム利用と経路制約下における競争施設配置
- Authors: Hoang Giang Pham, Tien Thanh Dam, Ngan Ha Duong, Tien Mai and Minh
Hoang Ha
- Abstract要約: 競争市場における施設配置問題について検討し、ランダムなユーティリティ選択モデルにより顧客の需要が予測される。
我々は,選択した場所を訪問するツアーの存在を保証するために,場所の選択を必要とするルーティング制約を導入する。
- 参考スコア（独自算出の注目度）: 4.9873153106566575
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study a facility location problem within a competitive
market context, where customer demand is predicted by a random utility choice
model. Unlike prior research, which primarily focuses on simple constraints
such as a cardinality constraint on the number of selected locations, we
introduce routing constraints that necessitate the selection of locations in a
manner that guarantees the existence of a tour visiting all chosen locations
while adhering to a specified tour length upper bound. Such routing constraints
find crucial applications in various real-world scenarios. The problem at hand
features a non-linear objective function, resulting from the utilization of
random utilities, together with complex routing constraints, making it
computationally challenging. To tackle this problem, we explore three types of
valid cuts, namely, outer-approximation and submodular cuts to handle the
nonlinear objective function, as well as sub-tour elimination cuts to address
the complex routing constraints. These lead to the development of two exact
solution methods: a nested cutting plane and nested branch-and-cut algorithms,
where these valid cuts are iteratively added to a master problem through two
nested loops. We also prove that our nested cutting plane method always
converges to optimality after a finite number of iterations. Furthermore, we
develop a local search-based metaheuristic tailored for solving large-scale
instances and show its pros and cons compared to exact methods. Extensive
experiments are conducted on problem instances of varying sizes, demonstrating
that our approach excels in terms of solution quality and computation time when
compared to other baseline approaches.
- Abstract（参考訳）: 本稿では,顧客需要をランダムなユーティリティ選択モデルによって予測する競争市場環境における施設立地問題について検討する。
選択した場所数に対する基数制約などの単純な制約に主に焦点をあてた先行研究とは異なり、指定されたツアー長上限に固執しながら、選択した場所を訪問するツアーの存在を保証するために、場所の選択を必要とするルーティング制約を導入する。
このようなルーティング制約は、現実世界のさまざまなシナリオにおいて重要なアプリケーションを見つける。
この問題は、複雑なルーティング制約とともにランダムなユーティリティの利用による非線形目的関数が特徴であり、計算的に困難である。
この問題に対処するために,非線形目的関数を扱うための外周切断と部分モジュラー切断,複雑なルーティング制約に対処する部分変数除去切断の3種類の有効切断について検討した。
これらは、ネストカットプレーンとネストブランチ・アンド・カットアルゴリズムの2つの厳密な解法の開発につながり、これらの有効なカットを2つのネストループを通じてマスター問題に反復的に付加する。
また、ネストされた切断平面法は有限反復の後に常に最適に収束することを示す。
さらに,大規模インスタンスの解決に適した局所探索型メタヒューリスティクスを開発し,その長所と短所を正確な方法と比較した。
様々なサイズの問題インスタンスについて広範な実験を行い、我々のアプローチが、他のベースラインアプローチと比較してソリューションの品質と計算時間において優れていることを実証した。
関連論文リスト
- Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。
本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。
2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
論文 参考訳（メタデータ） (2024-09-24T04:39:47Z) - A Multi-population Integrated Approach for Capacitated Location Routing [14.897794986447474]
本稿では, 静電容量化問題に対するマルチポピュレーション統合フレームワークを提案する。
効果的な地区ベースの局所探索、実現可能性回復手順、多様化指向の突然変異を含む。
文献からの281のベンチマークインスタンスの実験は、アルゴリズムが驚くほどよく機能していることを示している。
論文 参考訳（メタデータ） (2024-03-14T13:11:30Z) - Decentralized Multi-Task Online Convex Optimization Under Random Link
Failures [5.513958040574729]
我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。
我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
論文 参考訳（メタデータ） (2024-01-04T00:57:33Z) - 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) - Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
本稿では,大域最適化に基づく二乗ジグソーパズルの解法を提案する。
この手法は完全に自動化されており、事前情報を前提とせず、未知または未知のピースオリエンテーションでパズルを扱うことができる。
論文 参考訳（メタデータ） (2023-03-26T18:53:51Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳（メタデータ） (2022-11-29T05:52:17Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Generalized Conflict-directed Search for Optimal Ordering Problems [18.231677739397973]
本稿では,イベントの全順序を最適に生成する分枝順序付け法GCDOを提案する。
汎用的な紛争を推論する能力があるため、GCDOは以前の競合指向アプローチCDITOよりも高品質の総注文を見つけるのにはるかに効率的です。
論文 参考訳（メタデータ） (2021-03-31T18:46:48Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Exact and heuristic methods for the discrete parallel machine scheduling
location problem [0.0]
問題は、有限個の候補の中から$p$マシンの位置を選択し、これらのマシン上の一連のジョブをスケジューリングすることである。
広範囲な計算実験によって評価される新しいアークフロー定式化,列生成,3つの手順を提案する。
論文 参考訳（メタデータ） (2020-06-09T00:10:18Z) - From Local SGD to Local Fixed-Point Methods for Federated Learning [17.04886864943171]
分散環境で,演算子の平均点の固定点,あるいは近似を求めるという一般的な問題を考える。
このようなコンセンサスを達成するための2つの戦略について検討する。一方は局所的なステップの固定数に基づくもので、もう一方はランダム化された計算に基づくものである。
論文 参考訳（メタデータ） (2020-04-03T09:24:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。