論文の概要: DistrictNet: Decision-aware learning for geographical districting
- arxiv url: http://arxiv.org/abs/2412.08287v1
- Date: Wed, 11 Dec 2024 11:02:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-12 14:00:59.065196
- Title: DistrictNet: Decision-aware learning for geographical districting
- Title（参考訳）: DistrictNet: 地理的区分けのための決定型学習
- Authors: Cheikh Ahmed, Alexandre Forel, Axel Parmentier, Thibaut Vidal,
- Abstract要約: 地区化は地理的地域を小さな地区に分割する複雑な問題である。
実世界の地区問題に対する高品質な解決策を数分で見つけるための構造化学習手法を提案する。
実際の都市ではコストを大幅に削減できるため,既存手法よりも優れている。
- 参考スコア（独自算出の注目度）: 47.36059095502583
- License:
- Abstract: Districting is a complex combinatorial problem that consists in partitioning a geographical area into small districts. In logistics, it is a major strategic decision determining operating costs for several years. Solving districting problems using traditional methods is intractable even for small geographical areas and existing heuristics often provide sub-optimal results. We present a structured learning approach to find high-quality solutions to real-world districting problems in a few minutes. It is based on integrating a combinatorial optimization layer, the capacitated minimum spanning tree problem, into a graph neural network architecture. To train this pipeline in a decision-aware fashion, we show how to construct target solutions embedded in a suitable space and learn from target solutions. Experiments show that our approach outperforms existing methods as it can significantly reduce costs on real-world cities.
- Abstract（参考訳）: ディストリクトリングは地理的地域を小さな地区に分割する複雑な組合せ問題である。
物流では、数年の運用コストを決定する重要な戦略的決定である。
従来の方法での分割問題を解くことは、小さな地理的領域であっても難解であり、既存のヒューリスティックスは、しばしば準最適結果をもたらす。
実世界の地区問題に対する高品質な解決策を数分で見つけるための構造化学習手法を提案する。
グラフニューラルネットワークアーキテクチャに、容量化された最小スパンニングツリー問題である組合せ最適化層を統合することに基づいている。
このパイプラインを意思決定対応で訓練するために、適切な空間に埋め込まれたターゲットソリューションを構築し、ターゲットソリューションから学習する方法を示す。
実験の結果,実際の都市ではコストを大幅に削減できるため,既存の手法よりも優れていることがわかった。
関連論文リスト
- Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - Swap-based Deep Reinforcement Learning for Facility Location Problems in
Networks [11.613708854129037]
グラフ上の施設位置問題は、実世界ではユビキタスであり、非常に重要である。
p-median問題とグラフ上の施設配置問題に対処するスワップベースフレームワークを提案する。
また,複雑なグラフ構造に対する意識を示す新しい強化学習モデルも導入する。
論文 参考訳（メタデータ） (2023-12-25T09:00:25Z) - 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) - New Characterizations and Efficient Local Search for General Integer
Linear Programming [17.80124240223163]
本研究では境界解の概念を用いた線形プログラミング(ILP)の新たな特徴付けを提案する。
そこで我々は,局所探索アルゴリズムのLocal-ILPを開発した。
MIPLIBデータセットで行った実験は、大規模ハードILP問題の解法におけるアルゴリズムの有効性を示した。
論文 参考訳（メタデータ） (2023-04-29T07:22:07Z) - A machine learning framework for neighbor generation in metaheuristic
search [4.521119623956821]
メタヒューリスティック検索における近隣世代のための汎用機械学習フレームワークを提案する。
メタヒューリスティックな2つの応用法について検証する。
論文 参考訳（メタデータ） (2022-12-22T01:58:04Z) - Less Emphasis on Difficult Layer Regions: Curriculum Learning for
Singularly Perturbed Convection-Diffusion-Reaction Problems [21.615494601195472]
マルチスケールフィールドの学習を同時に行うことで,ネットワークがトレーニングを前進させることができなくなり,ローカル・ミニマの貧弱さに容易に立ち往生することを示す。
本稿では,ニューラルネットワークがより容易な非層領域での学習を優先し,より難しい層領域での学習を軽視する新たなカリキュラム学習手法を提案する。
論文 参考訳（メタデータ） (2022-10-23T10:15:32Z) - Hierarchical Planning for Resource Allocation in Emergency Response
Systems [0.8602553195689513]
都市規模のサイバー物理システムにおける古典的な問題は、不確実性の下で資源割り当てである。
オンライン、オフライン、分散型のアプローチはそのような問題に適用されていますが、大規模な決定問題へのスケーリングは困難です。
不確実性下における資源配分のための都市レベルのCPS問題の構造を利用する階層計画への一般的なアプローチを提示する。
論文 参考訳（メタデータ） (2020-12-24T15:55:23Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
本稿では,マイニングパターンを用いて問題サイズの削減を行うMineReduceという手法を提案する。
異種車両ルーティング問題に対するMineReduceの適用について述べる。
論文 参考訳（メタデータ） (2020-05-15T08:49:50Z) - Optimizing Wireless Systems Using Unsupervised and
Reinforced-Unsupervised Deep Learning [96.01176486957226]
無線ネットワークにおけるリソース割り当てとトランシーバーは、通常最適化問題の解決によって設計される。
本稿では,変数最適化と関数最適化の両問題を解くための教師なし・教師なし学習フレームワークを紹介する。
論文 参考訳（メタデータ） (2020-01-03T11:01:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。