論文の概要: 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中間問題とロジスティックス分割との接続
- 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モデルはこれらのほとんどを最適に解決することができた。
関連論文リスト
- Model-Based and Sample-Efficient AI-Assisted Math Discovery in Sphere Packing [51.30643063554434]
上界の先導手法である三点法は、大高精度半確定プログラム(SDP)の解法に問題を還元する。
我々は、SDP構成を、ポリシーが一連の許容成分からSDP定式化を組み立てる逐次決定過程、SDPゲームとして定式化する。
従来からある幾何学的問題において,モデルに基づく探索が計算の進歩を推し進めることができることを示す。
論文 参考訳（メタデータ） (2025-12-04T14:11:52Z) - MOSIC: Model-Agnostic Optimal Subgroup Identification with Multi-Constraint for Improved Reliability [11.997050225896679]
そこで本研究では,最適部分群を同定するために,初期制約付き最適化問題を直接解決する統一最適化フレームワークを提案する。
我々の鍵となる革新は、勾配降下勾配アルゴリズムによって解決された、制約のない微分可能な min-max の目的として、制約された原始問題の再構成である。
このフレームワークは、モデルに依存しず、幅広いCATE推定器と互換性があり、コスト制限や公正性基準のような追加の制約への適合性がある。
論文 参考訳（メタデータ） (2025-04-29T16:25:23Z) - Training Deep Learning Models with Norm-Constrained LMOs [56.00317694850397]
線形最小化オラクル(LMO)を用いて問題の幾何学に適応する新しいアルゴリズム群を提案する。
我々は,Adamに頼らずに,我々のアルゴリズムであるScionを用いたナノGPTトレーニングの大幅な高速化を示す。
論文 参考訳（メタデータ） (2025-02-11T13:10:34Z) - 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) - Exploiting Temporal Structures of Cyclostationary Signals for
Data-Driven Single-Channel Source Separation [98.95383921866096]
単一チャネルソース分離(SCSS)の問題点について検討する。
我々は、様々なアプリケーション領域に特に適するサイクロ定常信号に焦点を当てる。
本稿では,最小MSE推定器と競合するU-Netアーキテクチャを用いたディープラーニング手法を提案する。
論文 参考訳（メタデータ） (2022-08-22T14:04:56Z) - Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。
従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
論文 参考訳（メタデータ） (2021-11-24T13:38:34Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳（メタデータ） (2020-12-04T15:36:29Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。