論文の概要: Fast and Effective Redistricting Optimization via Composite-Move Tabu Search

• arxiv url: http://arxiv.org/abs/2605.06682v1
• Date: Fri, 24 Apr 2026 08:50:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-25 12:34:33.67818
• Title: Fast and Effective Redistricting Optimization via Composite-Move Tabu Search
• Title（参考訳）: 複合移動タブサーチによる高速かつ効果的な再限定最適化
• Authors: Hai Jin, Diansheng Guo,
• Abstract要約: 本稿では,連続性を保ちながら,田ぶ探索において実現可能な近傍空間を拡大する複合移動型田ぶ探索(CM-Tabu)を提案する。 大規模な実験により、提案手法は、解の質、実行時の堅牢性、計算効率を大幅に改善することが示された。
• 参考スコア（独自算出の注目度）: 19.932790314892213
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Spatial redistricting is a practical combinatorial optimization problem that demands high-quality solutions, rapid turnaround, and flexibility to accommodate multi-criteria objectives and interactive refinement. A central challenge is the contiguity constraint: enforcing contiguity in integer-programming or heuristic search can severely shrink the feasible neighborhood, weaken exploration, and trap the search in poor local optima. We introduce a composite-move Tabu search (CM-Tabu) that systematically expands the feasible neighborhood space in Tabu search while preserving contiguity. When a boundary unit cannot be reassigned individually without disconnecting its district, our method identifies a minimal set of units that can move together, or a pair of units (or sets of units) that can be switched, as a contiguity-preserving composite move. Candidate single-unit and composite moves are generated in linear time by analyzing each district's contiguity graph using articulation points and biconnected components. Extensive experiments demonstrate that the proposed approach substantially improves solution quality, run-to-run robustness, and computational efficiency relative to traditional Tabu search and other baselines. For example, in the Philadelphia case, the approach can consistently attain the theoretical global optimum in population-equality and support multi-criteria trade-offs. CM-Tabu delivers optimization performance suitable for real-world practices and decision-support workflows.
• Abstract（参考訳）: 空間再限定化は、高品質なソリューション、高速なターンアラウンド、フレキシビリティを必要とする実用的な組合せ最適化問題である。 整数プログラミングやヒューリスティック探索において連続性を強制することは、実現可能な近傍を著しく縮小し、探索を弱め、探索を貧弱な局所最適条件でトラップする。 本稿では,連続性を保ちながら,田ぶ探索において実現可能な近傍空間を体系的に拡張する複合移動型田ぶ探索(CM-Tabu)を提案する。 地区を分割することなく、境界単位を個別に割り当てることができない場合、我々の手法は、一緒に動ける最小の単位の組、あるいは一対の単位(または単位の集合)を連続保存された複合移動として識別する。 各地区の連続グラフを調音点と二連結成分を用いて解析することにより、線形時間で候補単ユニットと合成の動きを生成する。 大規模な実験により,提案手法は,従来のタブサーチや他のベースラインと比較して,解の質,実行時の堅牢性,計算効率を大幅に向上することが示された。 例えば、フィラデルフィアの場合、この手法は、人口平等の理論的グローバルな最適化を一貫して達成し、マルチ基準トレードオフをサポートすることができる。 CM-Tabuは現実世界のプラクティスや意思決定支援ワークフローに適した最適化性能を提供する。

関連論文リスト

• Optimal Counterfactual Search in Tree Ensembles: A Study Across Modeling and Solution Paradigms [6.9087441566570105]
  本研究では,木組の最適対実的説明を,可否制約と行動可能性制約の下で計算する問題について検討する。 これは問題である: 固定モデルの場合、反事実探索は、一貫した分岐決定と、距離目標の下でしきい値定義された領域を選択することに沸騰する。 我々は、この構造をCPCF(制約プログラミング)の定式化によって利用し、数値的特徴を分割しきい値によって誘導される区間領域として符号化する。
  論文  参考訳（メタデータ） (2026-05-07T16:54:38Z)
• Learning with Local Search MCMC Layers [12.613397606663801]
  不正確な解法による学習に理論的に根ざしたアプローチを導入する。 局所探索で使用される問題固有近傍系を提案分布に変換する。 時間窓を用いた大規模動的車両ルーティング問題に対する我々のアプローチを実証する。
  論文  参考訳（メタデータ） (2025-05-20T11:47:42Z)
• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  提案するSEQUOIAは,動作空間に対する長期報酬を直接最適化するRLアルゴリズムである。 我々は,複数介入,経路制約,二部間マッチング,容量制約という,制約を伴う4つの新しいレスレス・バンディット問題に対して,SEQUOIAを実証的に検証した。
  論文  参考訳（メタデータ） (2025-03-01T21:25:21Z)
• A Random-Key Optimizer for Combinatorial Optimization [0.0]
  本稿では,最適化問題に適した汎用的で効率的な局所探索手法を提案する。 ランダムキーの概念を用いて、RKOは解をランダムキーのベクトルとしてエンコードし、後に実行可能な解に復号する。 RKOフレームワークは古典的メタヒューリスティクスの多元体を組み合わせ、それぞれが独立して、あるいは並列に動作可能であり、エリートソリューションプールを通じてソリューション共有が促進される。
  論文  参考訳（メタデータ） (2024-11-06T22:23:29Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)

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

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