論文の概要: 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（参考訳）: 複合移動タブサーチによる高速かつ効果的な再限定最適化
• 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は現実世界のプラクティスや意思決定支援ワークフローに適した最適化性能を提供する。

関連論文リスト

• Learning Discrete Decisions for MIPs with Constraint-Aware Diffusion [40.25954048196068]
  本稿では,混合整数最適化問題の事例を大まかに解くための,学習に基づく新しい手法を提案する。 提案手法は,混合整数最適化問題の離散成分を学習するグラフベース生成拡散モデルに依存する。 Constrained Graph Diffusion (CGD) という名前のフレームワークは問題に依存しず、様々な混合整数最適化問題に対応できる。
  論文  参考訳（メタデータ） (2026-08-13T10:46:18Z)
• Optimal Counterfactual Search in Tree Ensembles: A Study Across Modeling and Solution Paradigms [6.9087441566570105]
  本研究では,木組の最適対実的説明を,可否制約と行動可能性制約の下で計算する問題について検討する。 これは問題である: 固定モデルの場合、反事実探索は、一貫した分岐決定と、距離目標の下でしきい値定義された領域を選択することに沸騰する。 我々は、この構造をCPCF(制約プログラミング)の定式化によって利用し、数値的特徴を分割しきい値によって誘導される区間領域として符号化する。
  論文  参考訳（メタデータ） (2026-05-07T16:54:38Z)
• Lagrangian Relaxation Score-based Generation for Mixed Integer linear Programming [13.20958452268089]
  ラグランジュ緩和誘導微分方程式(SDE)に基づく生成的枠組み システムは、標準MILPソルバに対して、コンパクトで効果的な信頼領域サブプロブレムを集合的に定義する、多種多様な高品質なソリューション候補を生成する。
  論文  参考訳（メタデータ） (2026-03-25T07:48:01Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• 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)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。 頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。 特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-01-18T11:16:40Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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