論文の概要: The Edge-based Contiguous p-median Problem with Connections to Logistics Districting

• arxiv url: http://arxiv.org/abs/2608.11230v1
• Date: Thu, 30 Jul 2026 03:49:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-17 01:32:04.586525
• Title: The Edge-based Contiguous p-median Problem with Connections to Logistics Districting
• Title（参考訳）: エッジ型連続p中間問題とロジスティックス分割との接続
• Authors: Zeyad Kassem, Adolfo R. Escobedo,
• Abstract要約: 本稿では,ネットワーク内の道路をコンパクトかつ連続な領域に分割するエッジベース連続p-median(ECpM)問題を提案する。 2つのバイナリプログラミングモデルが導入され、どちらもネットワーク距離が組み込まれている。 それぞれのソリューションアプローチは2,700以上のノードと3,400近いエッジを持つロードネットワーク上でテストされる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces the edge-based contiguous p-median (ECpM) problem to partition the roads in a network into a given number of compact and contiguous territories. Two binary programming models are introduced, both of which incorporate a network distance. The first model requires an exponential number of cut set-based constraints to model contiguity; it is paired with a separation scheme that usually generates only a small number of these constraints, namely, a branch-and-cut (B&C) algorithm. The second model utilizes a polynomial number of shortest-path constraints to model contiguity and can be solved with off-the-shelf solvers. The respective solution approaches are tested on road networks with over 2,700 nodes and close to 3,400 edges, yielding models with over 9.6 million binary variables. Solving the model based on shortest path contiguity (SPC) constraints via standard branch and bound attains speedups in computational time of up to 17x relative to the cut set-based B&C implementation. In addition, the SPC constraints are demonstrated to be supervalid inequalities of the edge-based p-median (EpM) model (i.e., for which contiguity is not explicitly required), meaning that they may cut off integer-feasible solutions and some, but not all, of the optimal solutions of this simpler problem. Finally, the paper explores structural insights and connections between ECpM and the edge-based districting (EBD) problem, which enforces an additional work balance criterion. An existing model that utilizes cut set-based contiguity constraints was unable to find a feasible solution within 12 hours for any of the tested instances, while an SPC-based EBD model was able to solve most of these to optimality.
• Abstract（参考訳）: 本稿では,ネットワーク内の道路をコンパクトかつ連続な領域に分割するエッジベース連続p-median(ECpM)問題を提案する。 2つのバイナリプログラミングモデルが導入され、どちらもネットワーク距離が組み込まれている。 最初のモデルは連続性をモデル化するために、指数関数的な数のカットセットベースの制約を必要とし、通常はこれらの制約のごく一部、すなわちブランチ・アンド・カット(B&C)アルゴリズムを生成する分離スキームと組み合わせられる。 2番目のモデルは、最短経路制約の多項式数を利用して連続性をモデル化し、既成の解法で解ける。 それぞれのソリューションアプローチは2700以上のノードと3400のエッジを持つロードネットワーク上でテストされ、960万のバイナリ変数を持つモデルが得られる。 標準分岐による最短経路整合性(SPC)制約に基づくモデルの解法は、カットされたセットベースのB&C実装と比較して最大17倍の計算時間で高速化される。 さらに、SPCの制約は、エッジベースのp-中間子(EpM)モデルの超有益不等式(すなわち、連続性は明示的に要求されない)であることが示される。 最後に、ECpMとエッジベース分割(EBD)問題の間の構造的洞察と接続について検討し、追加の作業バランス基準を適用した。 カットされたセットベースの連続性制約を利用する既存のモデルは、テストされたインスタンスの12時間以内に実現可能なソリューションを見つけることができず、SPCベースのEBDモデルはこれらのほとんどを最適に解決することができた。

関連論文リスト

• MAP: Low-compute Model Merging with Amortized Pareto Fronts via Quadratic Approximation [80.47072100963017]
  Amortized Pareto Front (MAP) を用いた新しい低演算アルゴリズム Model Merging を導入する。 MAPは、複数のモデルをマージするためのスケーリング係数のセットを効率的に識別し、関連するトレードオフを反映する。 また,タスク数が比較的少ないシナリオではベイジアンMAP,タスク数の多い状況ではNested MAPを導入し,計算コストを削減した。
  論文  参考訳（メタデータ） (2024-06-11T17:55:25Z)
• Typical and atypical solutions in non-convex neural networks with discrete and continuous weights [2.7127628066830414]
  ランダムな規則や関連を学習する単純な非拘束型ネットワークモデルとして、二項および連続負マージンパーセプトロンについて検討する。 どちらのモデルも、非常に平坦で幅の広い劣支配的な最小化器を示す。 両モデルにおいて、学習装置としての一般化性能は、広い平坦な最小化器の存在により大幅に向上することを示した。
  論文  参考訳（メタデータ） (2023-04-26T23:34:40Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
  このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。 従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
  論文  参考訳（メタデータ） (2021-11-24T13:38:34Z)
• Adaptive Subcarrier, Parameter, and Power Allocation for Partitioned Edge Learning Over Broadband Channels [69.18343801164741]
  パーティショニングエッジ学習(PARTEL)は、無線ネットワークにおいてよく知られた分散学習手法であるパラメータサーバトレーニングを実装している。 本稿では、いくつかの補助変数を導入してParticleELを用いてトレーニングできるディープニューラルネットワーク(DNN)モデルについて考察する。
  論文  参考訳（メタデータ） (2020-10-08T15:27:50Z)
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks [2.7473982588529653]
  連続観測データからBNのスパースDAG構造を学習する問題について検討する。 この数学的プログラムの最適解は、ある条件下では望ましい統計的性質を持つことが知られている。 ほぼ最適解を得るために, 分岐・結合プロセスの終了に向け, 早期停止条件を提案する。
  論文  参考訳（メタデータ） (2020-05-29T00:13:15Z)

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

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