■ 論文 ■経営論集

Vol. 5, No. 6, March 2019, pp. 1-24
ISSN 2189-2490

選挙区画定問題の解法
堀

田

敬

介

概要
選挙区制の選挙を実施するためには、選挙区を画定しなければならない。憲法や法律などその国の指針にもとづき、適切な選挙区を構成することは、一般に組合せ最適化問題となる。日本では、選挙区間の一票の較差が問題となることが多く、この指標にもとづいた評価をするためには、近似解ではなく限界値を与える最適解を求めることが必要となる。ところが、事例によっては、この問題の最適解の求解は非常に困難を伴う。本論文は、根本・堀田［38，39］によって確立された最適解の求解法について、
特に最小比最適解をどのように簡便に求めることができるのか、およびその計算複雑度解析について詳細をまとめたものである。

キーワード：議席配分問題、区割画定問題、一票の最大較差、最小比最適化、計算量、 0 - 1 混合整数
計画法、グラフ分割、連結成分分解

（投稿日
（受理日

文教大学経営学部〒253-8550 神奈川県茅ヶ崎市行谷1100
Tel 0467-53-2111（代表） Fax 0467-54-3734
http://www.bunkyo.ac.jp/faculty/business/

2019年 1 月31日）
2019年 １ 月31日）

経営論集

Vol.5, No.6（2019）pp.1-24

選挙区画定問題の解法
堀

田

敬

介＊

市区町村や都道府県で選挙区を構成すること

選挙区を画定するまで

₁と、その選挙区の配分議席数を同時に決定する必要がある場合もある。代表的な例を表1.1に載せる 2 ）。

選挙区を画定する作業は、定数配分問題（議席配分問題）と区割画定問題のどちらか、あるそれぞれの問題において、議席の割り当て方

いは両方を解く問題となる。定数配分問題とは、法や区割の構成の仕方は複数の答えが考えられ与えられた総定数（総議席数）をあらかじめ定るので、何らかの評価値をもってその解の善しめられた複数の対象に、その対象の属性に応じ悪しを決定する必要がある。日本では、日本国て割り当てる問題である。例えば、衆議院議員

憲法第14条の法の下の平等の精神にもとづき、

比例代表制の場合、176議席を11比例ブロック

各選挙区ペアの一票の較差を最重要の評価値とに、各ブロックの人口1）に比例して割り当てる。

して用いる（cf.［61］）。

各対象に割り当てる数値はその性質上整数にし定数配分問題に対しては、政治学、法学、

なければならないが、比例値は通常整数にはな

OR や公共政策等、様々な観点から取り組まれ、らないので、何らかの方法で数値を整数に丸め

過去200年以上にわたり、様々な手法の提案や、る必要が生じ、ここにこの問題の根本的な難し

各手法の性質など、多くの知見が得られているさが潜む。一方、区割画定問題とは、あらかじ（cf.［ 1 ，77］）。一方、区割画定問題に関してめ定められた小地域を複数組み合わせて、条件の数理的な知見も2003年以降、多く得られていに応じた議席を持つ選挙区を構成する問題である（cf.［54，55，38，39，40，42，43，18，

る。例えば、衆議院小選挙区制において、各都

19，21，23，27］）。それ以前まで、区割画定問

道府県に割り当てられた議席数にもとづき、都題に対する数理的な取り組みが少ない原因は大道府県内の市区町村を所与の小地域として、人

きく 2 つ考えられる。 1 つは、アルゴリズムの口がほぼ等しくなるように、選挙区を決定する。

分野では、自身の作成した近似解法やヒューリ

なお、衆議院議員小選挙区制のように、まずスティック等の性能評価の一例としてとりあげ

定数配分問題（289議席を47都道府県に人口にた側面が大きいので、現行区割よりよい実行可

比例して割り当てる）を解き、次に、都道府県

能解を 1 つ見つけた、というだけで終わらせて毎に区割画定問題を解く、 2 つの問題を段階的いるということと、法律や政治的条件等が十分に解く選挙制度や、都道府県議会大選挙区制や考慮されておらず、データの取り方が不正確で合区を考慮する参議院議員選挙区制のように、不十分であることである。最適解を求めねばならない政治的意義をきちんと示したのは坂口・* 文教大学経営学部
khotta@shonan.bunkyo.ac.jp

和田［54，55］である。もう 1 つは、最もシン1表₁．₁：定数配分問題と区割画定問題の例
定数配分問題の例
選挙
国政
国政
国政
国政
国政
国政
地方

対象議会 選挙制度
参議院 選挙区制
衆議院 比例代表制
衆議院 小選挙区制
ドイツ連邦議会 小選挙区制
アメリカ下院 小選挙区制
イギリス庶民院 小選挙区制
指定都市議会 大選挙区制

総定数

配分対象

属性条件

₇₃議席
₁₇₆議席
₂₈₉議席
₂₉₉議席
₄₃₅議席
₆₅₀議席
各指定都市議席

₄₇都道府県₁₁比例ブロック
₄₇都道府県
₃ 市＋₁₃州
₅₀州
₄ 地域
区

人口比例
人口比例
人口比例
人口比例
人口比例
有権者比例
人口比例

対象地域

構成小地域

属性条件

各都道府県
各州
各州
各 ₄ 地域

市区町村
市町村
－
自治体境界

人口比例
人口比例
人口比例
有権者比例

区割画定問題の例
選挙
国政
国政
国政
国政

対象議会 選挙制度
衆議院 小選挙区制
ドイツ連邦議会 小選挙区制
アメリカ下院 小選挙区制
イギリス庶民院 小選挙区制

定数配分と区割画定を同時に考慮する必要がある問題の例
選挙

対象議会 選挙制度

対象地域

構成小地域

属性条件

地方
国政

各都道府県議会 大選挙区制
参議院 選挙区制（合区考慮）

各都道府県
日本

市町村
都道府県

人口比例
人口比例

プルな条件でも NP- 困難なモデルとして定式

ワークを利用した取り組み［53］も近似解法で化されるため、厳密解法で最適解を導出するのある。

がインスタンスによっては極めて困難な点であアメリカにおいては、アルゴリズムやコンる（cf.［54，55］）。様々な工夫を用いて、衆ピュータを利用、あるいは利用を想定した区割

議院小選挙区制（当時300選挙区）の厳密解を画定問題への取り組みが1960年代より行われて全てはじめて示したのは根本・堀田［38，39］

いる［ 6 ， 7 ， 8 ，12，13，26，32，36，37，

である。

65，73，76］。60年代、70年代の研究については、

区割画定問題に対する古典的なモデルは（飛その概説とともに、区割画定において重要とみび地を許さないことを条件とした）集合分割問なされる人口統計的規準、形状的規準および政題として定式化することである［30］。ただし、治的規準や、研究結果のまとめと課題、問題点

この問題は NP- 困難であり、現実のデータをについて言及されている［72］が、ほとんどのそのまま適用して最適解を導出するのは困難で解法は近似解法であり、数少ない厳密解法ではあった。既存研究には、最小 m 全域森問題［74，40～50程度の市区郡から 5 ～ 7 選挙区をつくる

75］やグラフ頂点分割問題［63］としてのモデ

小規模の問題しか解けていない［ 7 ］。アメリ

ル化がある。いずれも分枝限定法で最適解導出

カにおいて重要な形状の基準であるコンパクトを試みているが、高々 5 選挙区までが限界であ性をうまく利用した研究がある［ 2 ，33］が、り、かつ選挙区の中心市区郡を事前に指定する区割線をある程度自由に設定可能という独特のなど最適性の保証がない。ニューラルネット

制度を利用している。カナダでは、複数の規準

2

経営論集

Vol.5, No.6（2019）pp.1-24の重み付け和を関数としてタブサーチで解くとな解のコンパクト保持［27］、衆議院・参議院

いうアイデア［ 3 ］があるが、近似解である。

の合区の評価［17，18，23］、大選挙区（複数

その他、ニュージーランド［ 9 ］など各国で取人選出選挙制度）への拡張［21］などである。

り組まれているが、問題設定が異なるために同本論文は、根本・堀田による最適化モデル［38，じモデルとして捉えることはできない。また、

39］で実問題を解く際の工夫、特に、最適性のいずれも例として 1 ～数州における区割を解い保証、すなわち最小比最適解をどのように求めてみたという程度であり、その国の全ての州のるのかとその反復回数についてまとめたもので区割に取り組んだという研究はない。ドイツ連ある。本論文の構成は以下のようになっている。

邦議会小選挙区制の解を求めた例があるがまず、第 2 節で議席配分に対する最適化モデル［11］、細かい市町村は、地域のつながり等を考とその結果について述べる。次に、第 3 節で区慮してあらかじめ中程度のサイズにした後、割画定に対する最適化モデルと、最適解導出のヒューリスティックで組み合わせ的に求めてい工夫、最適性、反復回数、第 k 最適解（列挙）、る。また、目的関数を様々な関数で評価可能と選挙区割の類似性測定法とその結果について述

述べるのみで、政治的な意義については考慮さべる。最後に、まとめと今後の課題について述れていない。

べる。

いずれにしろ、政治的規準や目的が各国にお定数配分問題の解法

₂

いて異なるので、研究結果をそのまま日本の区割作成に適用できない。また、他国と異なり、日本では一票の最大較差が 2 倍を超えているこ

所与の整数値を、定められたいくつかの部分とをどう解消するか、というのが最大の懸案事にその属性に比例して分割する定数配分問題を項であるため、全てについて厳密解を求めるこ考える。ただし、分割された数値も整数にするとが求められる。

という条件が付く。国政選挙（衆議院小選挙区

根本・堀田［38，39］が、解くのが困難だっ制）では、所与の総議席数（整数値）を47の都た区割画定問題に対し、考えられる数理モデル

道府県にその属性（人口）に比例して配分するから 2 つの有効な定式化を提案し、様々な工夫問題となるし、国政選挙（衆議院比例代表制）

を用いて全小選挙区区割を導出して以降、そのでは、所与の総議席数（整数値）を11の地域に結果や最適化モデルを駆使した様々な分析が行

その属性（人口）に比例して配分する問題とな

われ、多くの知見が得られた。人口動態の変化

り、国政選挙（参議院比例代表）では、所与のや行政界の変更、総定数変化が一票の較差に及総議席数（整数値）を各党にその属性（獲得票

ぼす影響［40，42，43］、市区郡の分割法の影数）に比例して配分する問題となる。属性の比響［14］、議席配分の最適化と既存議席配分法

例値が整数になることは稀なため、整数に丸めとの定量的比較［15，16，20，22］、第 k 最適

る操作によって多くの配分法が考案されている。

解からの実行可能解の列挙法とその解の特徴化

2．1による選挙区画定作業支援［16，19］、フロンティ

既存の定数配分法

よく知られ、各国の選挙制度でも用いられてア法による列挙の高速化と ZDD を用いた膨大

3

表₂．₁：定数配分法の性質による比較（cf．［ ₁ ］）
除数法

方式
名称

剰余法
LRM

SD

HMD

GMD

AMD

LD

割当分特性
総定数単調性
人口単調性
標準性
整合性
配分議席 ₁ 以上

○
×
×
○
×
×

×
○
○
×
×
○

×
○
○
×
×
○

×
○
○
×
×
○

×
○
○
○
○
×

×
○
○
×
×
×

いる剰余法と除数法について、それぞれの手法はほとんどない（cf.［20］表2.2など）。LRM，3）の性質を纏めたものが表2.1である 。表中のAMD，LD は、極端に人口が少ない対象の配○はその性質を満たすことを意味し、×は満分議席が 0 になりうる。各手法は一長一短で、たさないことを示す。

決定的によい方法は知られていないが、定性的割当分特性を満たすとは、対象 i の配分 mi が、には AMD がよい［ 1 ，67］などの主張がある。

比 例 値 の 切 り 捨 て 値 mpi/P か 切 り 上 げ 値

定量的にも考慮すると、HMD か GMD のどち

mpi/P のどちらかになるということである。

らかを用いるのが良いように思う［22］。

ここで、pi は対象 i の人口で、∑i pi＝P である。

2．2

総定数単調性を満たすとは、アラバマパラドク

議席配分最適化モデル［16，20］

スが起こらないことを意味する。人口単調性を所与の総議席数 m を、配分対象 i ∈｛ 1 ，...，

満たすとは、人口パラドクスが起こらないことn｝へ、一票の最大較差が最小となるように割を意味する。標準性や整合性などについてはり当てるのが、議席配分最適化モデルである［ 1 ，77］を参照されたい。配分議席 1 以上とは、［16，20］。
対象 i の人口を pi、対象 i の配分議席候補を必ず全ての対象に 1 議席以上配分されることを（ji＝｛ 1 ， 2 ，...｝）とする。変数 ziji を、
miji、

意味する。
剰余法は割当分特性は満たすが、アラバマパ

各対象 i の配分議席候補 miji を採用するか否か

ラドクス・人口パラドクスなどが起こりうる。

の 0 - 1 変数とすると、議席配分モデルは以下

除数法は、剰余法で問題とされるパラドクスはの通りに定式化される。

回避できるが、割当分特性は成り立たない。 5

定式化［₁₆］:つの除数法のうち、SD と LD の 2 つは両極端

min. u/l

な手法で、配分対象の人口が偏っている場合、

s.t.

（2.1）

SD は相対的に人口の少ない対象により有利に

pi
l ≤∑ziji ≤ u（∀i）
j miji∑ziji = 1（∀i）


議席配分される傾向があり、LD は逆に人口の∑∑miji ziji =m

多い対象へ相対的に多く議席配分される傾向が∑miji ziji ≤ ∑mi' ji' zi' ji'ある。平均的な除数法（HMD，GMD，AMD）（∀i，i' s.t.pi ≤ pi'）

（2.5）

ziji ∈{ 0 ， 1 }（∀i，ji）

（2.6）

i

ji
i

ji

は比較的どちらにも平均的な議席割当を行い、

ji

j'i

（2.2）
（2.3）
（2.4）

式（2.2）は、一選挙区あたりの平均人口 pi/

実際、定量的には割当分特性を満たさないこと

4

経営論集

Vol.5, No.6（2019）pp.1-24
表₂．₂：議席配分最適化モデルにより示される一票の最大較差下限値［₁₆，₂₀］
人口

₂₀₁₀

₂₀₁₅

総議席数

₃₀₀

₂₈₉

最大人口
最小人口

₄₇₀︐₆₃₁₂₉₄︐₂₀₉₄₆₅︐₇₆₅
₂₉₄︐₂₀₉₅₇₃︐₆₄₈
₃₄₇︐₀₉₄

₅₇₃︐₆₄₈
₃₄₇︐₀₉₄

最大較差

₁．₆₀₀

₁．₅₈₃

₁．₆₅₃

₁．₆₅₃

割当分特性
満たさない数

制約
₀

制約とせず
₅

制約
₀

制約とせず
₃

miji が上下限（u，l）内におさまることを要求

このモデルでは、最大較差を与える最大人口している。各対象 i について、式（2.3）で配と最小人口が定まり、残りの議席数には自由度分議席候補 miji のうち 1 つだけを採用し、式がある。従って、最大・最小が定まった後にそ（2.4）でその合計が総議席数 m に等しくなるの範囲内の配分を唯一に定める必要がある。こようにする。式（2.5）は、pi に対する配分議のとき、それぞれの較差は最小値からの比で評

席数の単調性を保証するための制約である。

価されるので、目的関数を min. u に変更し、議席配分最適化モデルは、各 i の配分議席候最大と最小に関連する変数を固定した上で解補 miji を、割当分特性を満たすように決める場

き、 2 番目に大きな人口を決定する。以下同様

合と、満たさなくてよい場合のどちらでも求解に、 3 番目、 4 番目と繰り返し解くことで、内できる。割当分特性を満たす場合は、（ 0 議席

側の配分を決定していく。

が候補になる場合を除き）全ての対象で候補とこのモデルを用い、2010年国勢調査［速報値］

なる議席数は 2 つ（ji＝ 1 ， 2 ）となる。比例Pの切り捨て値、切り上げ値のどちらか
値 pimを採用するからである。

人口と総議席数 m＝300、2015年国勢調査［速報値］人口と総議席数 m＝289について、割当分特性を満たす場合と満たさない場合の都道府－割当分特性を満たさなくてよい場合、l ≥ l，

県への議席配分を行った結果、一票の最大較差

－は表2.2の通りとなる 4 ）。

u ≤ ū となる選挙区の人口下限 l、上限 ū を追加し、都道府県毎にその範囲内に入る全ての配

日本の国政選挙（衆議院・小選挙区制）では、－分議席候補を考慮する。l，ū は、総人口 P（＝

総議席数を47都道府県に議席配分し、その後、∑ni pi）と議席総数 m による一選挙区あたり平

各自治体毎に区割画定を行う 2 段階の選挙区画

均人口 P/m に対して、例えば±α％として定定作業となるが、その 1 段階目の議席配分では、

まる。従って、対象 i の配分議席候補 miji の集

2000年～2015年の人口・行政界では、大体1.6

合は倍程度の最大較差となる。これは 2 段階目の区

pi
－
⎱
⎰
⎱miji l ≤ miji ≤ ū⎰

割画定で定まる最終的な一票の最大較差の下限（2.7）

値を与える。

－となる。ū，l の範囲を狭く取りすぎると、候補集合が空集合となる対象が出てくるので注意が必要である。

5

一の選挙区にするかについては、歴史的沿革や区割画定と最適化モデル

₃

地域のつながり 7 ） を考慮する必要があるが、一票の較差が最高裁の訴訟事項に毎回上がるほ小選挙区（ 1 人選出選挙区）の画定問題を考ど懸念材料となっている日本においては、政治える。この問題は、点 i ∈ V にコスト pi が与的な意義として、最もシンプルな条件のもとでえられたグラフ G＝（V，E）と定数 m ∈［ 2 ，

限界値がどこであるかを示すことが大変重要で|V |− 1 ］⊆ ZZ が与えられたときに、m 個の連結ある。従って、モデル上の制約は必要最低限と5）成分に分割する 。このとき、各連結成分のコして最適値（限界値）を導出する。国政選挙（衆ストの和の最大と最小の比を最小化することを

議院小選挙区制）における一票の最大較差の経目的とする最適化問題を考える。例えば、点集

緯を表3.1に示す［39，42，15，20］。

合 V を市区町村、コストをその人口とし、市

表₃．₁：全国最適区割による一票の最大較差の推移

区町村が境界を線で共有するとき枝を張って市［₃₉，₄₂，₁₅，₂₀］

区町村隣接グラフ G をつくる 6 ）。すると、この最適化問題は、小選挙区制度における一票の

人口
行政界

₂₀₀₀
₂₀₀₁．₃

₂₀₀₅
₂₀₀₆．₃₂₀₁₀₂₀₁₁．₃₂₀₁₅
₂₀₁₆．₃

最大較差を最小化する選挙区割画定問題となる。

総議席数

₃₀₀

₃₀₀

₃₀₀

₂₈₉

4 市区町村（|V |＝ 4 ）と人口が図3.1左の通

最大人口
最小人口

₅₃₆︐₀₀₀
₂₇₁︐₁₃₂

₅₆₆︐₄₆₀
₂₆₃︐₀₈₉

₅₆₁︐₂₁₁
₂₈₉︐₄₉₅

₅₇₈︐₂₄₅₂₉₄︐₆₅₆

最大較差

₁．₉₇₇

₂．₁₅₃

₁．₉₃₉

₁．₉₆₂

りに与えられているとき、その市区町村隣接グ
ラフは右の通りとなる。

3．1

集合分割型モデルとグラフ分割型モデル
集合分割型モデルは、例えば都道府県の選挙区を作る場合、市区町村を構成要素とし、所与

図₃．₁： ₄ 市区町村と人口、およびその隣接グラフ表現の議員定数 m について、条件を満たす分割の
日本の国政選挙（衆議院小選挙区制）の例で中で、目的関数最良のものを求める［38，39］。

は、総定数を都道府県に人口に比例して配分し、このモデルの長所は、定式化が比較的わかりや都道府県毎に配分された議席数 m の選挙区をすく表現が容易な点と、NP- 困難のクラスに市区町村を対象として構成する。このとき、集属す問題であるが、実際には中規模サイズ程度

合 m 分割型とグラフ m 分割型の 2 つのモデル

なら最適解を発見しやすい点である［29］。一方、で全都道府県の最適区割導出が可能である［38，

短所は、選挙区候補数が対象都道府県の市区町

39，15，20］。

村数の人口分布とその接続状況に依存してお日本の場合、最重要な目的は、一票の較差をり、場合によって膨大な数になる点である。

縮小し、公平な選挙区をつくることである。飛グラフ分割型モデルは、グラフ上にフローをび地を作らずに、市区町村を構成要素として選流すことで制約を満たすことを目指す。区割画

挙区を画定する。このとき、どの市区町村を同定問題に対してグラフを利用したアプローチと

6

経営論集

Vol.5, No.6（2019）pp.1-24

図₃．₂：グラフ分割型モデルで用いる図₃．₁の拡大有向グラフ

しては、過去に最小 m 全域森問題からの試み

フローの流量保存則により飛び地を持つ選挙区があるが、大きなサイズでの厳密解の導出は困は実行可能解とはならない。短所は、 0 - 1 変

難であることが報告されており、そもそも森の数の数が 2 mn 個と多い点であり、素朴に分枝

各連結要素の根となる点を事前に指定しなけれ限定法で解こうとすると多くの計算時間を要すばならないため厳密性の保証がない。ここでのため、実際の求解には工夫を要する。

モデルはその欠点を克服し、厳密性の保証があ

いずれも詳細は、［38，39］を参照されたい。

る［38，39］。例えば、都道府県の選挙区を作

どちらのモデルも組合せ最適化問題として表現

る場合、市区町村集合の選挙区数分の拡大有向しているが、飛び地とならない選挙区を構成す

グラフを構成し、選挙区に対応したフローをそるのに、入力段階で強制するか、制約条件としれぞれ流す。

て強制するかの点で異なる。

図3.1の 4 市区町村の例について、今、定数

3．2

2 （m＝ 2 ）の小選挙区制を考えた場合の拡大解法の工夫と効果

有向グラフを図3.2に示す。この拡大有向グラ

集合分割型モデルで用いる選挙区候補集合を

フは、 4 頂点｛v 1 ，v 2 ，v 3 ，v 4 ｝の隣接グラ準備するには、市区町村隣接グラフ（例：図3.1）

フを議席数（m＝ 2 ）個分つくり、議席数分の上で連結な部分グラフを列挙すればよく、再帰

1

2

頂点（s ，s ）からの有向枝と、市区町村分の呼出し型解法で実行可能である（cf.［29］第点に対応した tail 点｛t 1 ，t 2 ，t 3 ，t 4 ｝への各14章）。しかし、市区町村数の少ない都道府県

有向枝からなる（図3.2）。

でも列挙すべき数は膨大になる。そこですぐに

この定式化の長所は、過去のグラフ利用のモ

思いつく工夫は、人口を制限することである。

デルでは必要だった事前指定の中心市区郡が不実際の画定作業でも、 1 選挙区の平均人口を基要のため厳密性が保証される点にある。また、準として上下限 ub、lb を設定することが多い 8 ）。

7

図₃．₃： ₄ 市区町村の例（図₃．₁）における第 ₂ 妥当選挙区集合

ただし、人口の制限だけでは列挙数の膨大さを選挙区制なので、 1 選挙区あたり平均人口は克服できない事例も多い。そこで、根本・堀田

P/m＝50となる。よって、選挙区上下限は±は人口上下限を ub、lb に制限した第 1 妥当選挙

33.33 ％ 規 則 の も と で は、ub＝66、lb＝34と な区に加えて、第 2 妥当選挙区の概念を導入し、る 9 ）。従って、この例における集合分割型モデ

これを克服した［38，39］。

ルの全部分集合、全選挙区候補集合、第 1 妥当
選挙区集合、第 2 妥当選挙区集合は図3.3の通第 2 妥当選挙区とは、市区町村隣接グラフかりとなる。

ら当該選挙区を除いてできる連結成分全てが、人口上下限制約 ub、lb を満たすものをいう。第全部分集合の数は、対象市区町村数 n に対2 妥当選挙区の効果については、付録の表 A.1

して自明に 2 n− 2 で与えられる10） ので、このや、［14］表2.4、［16］表 3 、［21］表 7 などを例では24− 2 ＝14となる。この第 2 妥当選挙区

参照されたい。

集合を制約として、集合分割型モデルは解かれる。

図3.1の 4 市区町村の例では、総人口 P＝100

グラフ分割型では、モデルの対称性を崩して（＝20＋30＋35＋15）であり、定数 m＝ 2 の小求解を容易にするために、 0 - 1 変数の固定を

8

経営論集

Vol.5, No.6（2019）pp.1-24

図₃．₄：グラフ分割型モデルにおける ₀ ︲ ₁ 変数の固定例

行う［38，39］。対象となる 0 - 1 変数は yij（mnとは同一選挙区になる可能性があり、点 4 は同個）と zij（mn 個）の 2 種類である。まず、一一選挙区とはならないことが分かる。次に点 4

般性を失うことなく、任意の 1 対象（市区町村から同様に深さ優先探索を行うと、点 2 ， 3 となど）を第 1 選挙区に指定でき、それにともな

は同一選挙区になる可能性があることがわかう変数固定が可能である。次に、第 2 妥当選挙る。従って、点 1 を第 1 選挙区に指定して、関区の情報を用いて、この対象と同一選挙区にな

連 す る 0 - 1 変 数 を y11＝z11＝ 1 、y21＝y31＝y41

らない対象を第 2 選挙区に指定でき、それにと＝ 0 、y12＝z12＝ 0 と固定できる。同様に、点もなう変数が固定できる。以下同様に、第 2 妥

4 を 第 2 選 挙 区 に 指 定 し て、y42＝z42＝ 1 、y22

当選挙区の情報を用いて、同じ選挙区にならな＝y32＝ 0 、z41＝ 0 と固定できる。故にこの例

い対象を可能な限り指定して変数固定をしていで は、 2 種 類 の 0 - 1 変 数（yij，zij 各 々 4 × 2

くと、モデルの対称性が崩れ、非常に解きやす＝ 8 個）16個のうち、12個が固定でき、残り 4

くなる。どの対象を固定していくかについては、

個 z21，z22，z31，z32を求めれば良いことになる。

全対象から深さ優先探索を用いて計算し、第 2

この処理によって、実際の例ではどの程度固

妥当選挙区の情報も利用して、最も固定数が多定されるかの一例を表 A.2に示す。この表では、

くなる固定の仕方を採用する。

国政選挙（衆議院・小選挙区制）について、

図3.4は 図3.2の 拡 大 有 向 グ ラ フ に お け る

2005年国勢調査人口、2006年行政界のデータに

0 - 1 変数の固定例である。点 1 から深さ優先

もとづき、47都道府県の各々最大固定数を計算探索を行って人口和を求め、同時に第 2 妥当選したものである。ただし、人口過大市区郡11）

挙区の情報（図3.3）を利用すると、点 2 ， 3

は事前に 1 選挙区割当を行っているので、点数

9

|V | と議席数 m がその分減っていることに注意

解を求める。

されたい。

3．3

step₀． lb，ub を設定12） し、［lb，ub］で第 2最小比最適解の求め方

妥当選挙区の列挙と 0 - 1 変数固定（グラ

区割画定問題では一票の較差、つまり比の最フ分割型）を行う
step₁． Min-dif［lb，ub］を解き、最小差最適小を目的としている。比最小の分数計画問題は、

解 u＊d ，l＊d を得る

一般にパラメータを導入し、パラメトリック最

step₂． u＊d ，l＊d の最小差最適性を判定13）

適化問題として解く必要がある（cf.［29］第14章）。パラメータの追跡は単純には 2 分探索

最適なら lb：＝l＊d＋ 1 ，ub：＝ Pu＊d /（u＊d ＋（m法を使えばよいが、Newton 法を用いる方法も－ 1 ）l＊d）として step 3 へ提案されている［51］。しかし、パラメータをそうでなければγl，γu を適当に定め、lb：＝

固定した子問題でも厳密解導出に時間を費やす

lb－γl，ub：＝ub＋γu として step 1 へ

本問題ではこの汎用的な方法の実装では厳密解

step₃． カット不等式 u ≤ r＊l を制約に追加し導出が困難である。実は本問題の性質から、最て Min-dif［lb，ub］を解き、最小差最適解 ũ，小差を達成する区割が最小比も達成しているか

l を得る。ただし、r＊：＝u＊d /l＊dを判定する条件を導くことができ、最小比の保₃．₁． 実行不可能ならば終了（現在得られ証がない時に限って探索範囲を限定した最小差ている u＊d ，l＊d が最小比最適解）の問題を解き直すアプローチが可能である。そ₃．₂． u＊d /l＊d < ũ/l のとき、

～

～

～

こで、根本・堀田は、目的関数を最小差で解く

₃．₂．₁ P/（r＊＋m－ 1 ）≤（P－（ũ－l ））/ことで最小比最適解を求めることを可能にした

m ならば lb：＝（ũ－l ）/（r＊－ 1 ）とし［38，39］。議席配分最適化モデル［16，20］やて step 3 へ～～

複数議員選出選挙に対応したモデル［18，21，

₃．₂．₂ P/（r＊＋m－ 1 ）>（P－（ũ－l ））/23］でも同様である。本節ではその具体的手法

m ならば終了（u＊d ，l＊d が最小比最を説明する。

適解）～

₃．₃． u＊d /l＊d ≥ ũ/l のとき、選挙区の上下限を制限する変数 u、l ∈ IR を～用い、求めたい最小比目的関数は u/l である。

：＝（ũ，l），lb：＝l＊d＋ 1 ，ub：＝（u＊d ，l＊d）

これを、同じ制約のもとで、目的関数を最小差

Pu＊d /（u＊d ＋（m－ 1 ）l＊d） と し て

u−l に変えた最適化問題を最低 2 回解くこと

step 3 へ
Min-dif［lb，ub］は 2 つの定式化のいずれか

で 求 め る。 所 与 の 隣 接 グ ラ フ の 点 i ∈ V＝ni

｛ 1 ，...，n｝の人口を pi、総人口 P＝∑ pi、

で MIP ソルバーを用いて解く。step 2 では最配 分 議 員 定 数 を m と す る。 実 数 変 数 u，l を

小差最適性の判定、step 3 では最小比最適性のl ∈［lb，P/m ］，u ∈［ P/m ，ub］ と 限 定 し判定を行っている。step 2 における最適性判定た問題を Min-dif［lb，ub］とし、その最適解とは、Min-dif［lb，ub］の最小差最適解 u＊d ，l＊d

を u＊d ，l＊d とする。

が Min-dif［ 1 ，P－m＋ 1 ］ の 最 小 差 最 適 解

このとき、以下のアルゴリズムで最小比最適で あ る こ と の 確 認 で あ る（Proposition 3.1参

10

経営論集

Vol.5, No.6（2019）pp.1-24
PuP

P-(m-1)u

P-(m-1)u=P-(m-1)l
u=P-(m-1)lub
P/(m-1)(P-1)/(m-1)
P―mP/(m-1)(P-1)/(m-1)

u=l
u=(P-l)/(m-1)

u=l

P
―
m

u=(P-l)/(m-1)

lb

0 1

P
―
m

l

0 1

図₃．₅：下限 l に対する上限 u の実行可能領域

lb

P
―
m

l

図₃．₆：Min︲dif［lb，ub］の解探索範囲

P m－ 1 ＊⎧d ，
⎜ub ≥ m ＋ m⎨⎜lb ≤ P － m－ 1 d＊mm⎩照 ）。step3.2は 最 小 比 が 更 新 さ れ た 場 合、
step3.3は最小比が更新されない場合である。
なお、Min-dif［lb，ub］の目的関数は、u－l（3.1）

である。ただし、d＊＝u＊d －l＊d である。

で は な く、u－l－αl（α> 0 は 1 / 2 未 満 の 十
分小さな数）を用いる14）。これは、最小差最適

Proof： 2 直線 u＝P－
（m－ 1 ）
l，u＝l＋d＊の解が複数ある場合に、その中で l が最大のもの

交点は、を求めるためである。

（u、l）＝

上限 u の自明な範囲は［ P/m ，P－m＋ 1 ］
だが、下限 l ∈［ 1 ， P/m ］を定義域とした＝

関数 u と見なすと、l に対する u のとりうる範
P－l， P－（m－ 1 ）l で与えられ、
囲は
m－ 1
図3.5の斜線領域となる。

⎛ P－d＊ ， P＋（m－1）d＊ ⎞m⎝ m⎠⎛ P － 1 d＊， P ＋ m－ 1 d＊ ⎞
m
m
⎝m m
⎠

より、
ub ≥

アルゴリズムの step 2 における最小差最適m－ 1 ＊P＋dmm

であればよい。同様に、 2 直線 u＝（P－l）/（m

判定は Proposition 3.1により行う。

－ 1 ），u＝l＋d＊の交点は、

Proposition ₃．₁． Min-dif［lb，ub］ の 最 小 差［ 1 ，P－m＋ 1 ］ の
最 適 解 u＊d ，l＊d が Min-dif（u，l）＝

最小差最適解であるための十分条件は、

11⎛ P－（m－1）d＊ ， P＋d＊ ⎞
m
m ⎠
⎝

P

u

P

u

P-(m-1)P-(m-1)u=P-(m-1)l

u=P-(m-1)lu=l+(u*-l*)ddu=l+(u*-l*)
d
d

ub

ub
u*d
u=l

u=l

u*d

P
―
m

P
―
m
l*d

l*d
lb

lb

lb

0 1

P
―
m

0 1

l

lb

P
―
m

l

図₃．₇：Min︲dif［lb，ub］の最適解 u＊d，l＊d が Min︲dif［ ₁ ，P－m＋ ₁ ］の最適解の時（左）とそうでない時（右）＝⎛ P － m－ 1 d＊， P ＋ 1 d＊ ⎞
m
m m
⎝m
⎠

l ∈

＊
d

⎧
P m－ 1 ＊d －ub，
⎜γu：＝m ＋ m⎨⎜γ：＝ P － m－ 1 d＊－l
b
⎩ l m
m

■

＊
d

ub，lb，u ，l が条件（3.1）を満たさない（3.4）とすればよい。

場合は、図3.7の赤色の 2 つの三角形領域が未アルゴリズムの step 3 において、最小差最探索域となる。従って、式（3.1）の第 1 式を

適解 l＊d，u＊d は必ずしも最小比最適解とはなら満たさない場合は、ない。例えば、（l＊d，u＊d ）＝（200000，400000）、⎛ u ， P ＋ m－ 1 d＊ ，
m
⎝ b m

～

（l，ũ）＝（210000，415000）のとき、～

P－ub ⎛l ∈ ub － d＊，m－１⎝

u＊d －l＊d＝200000 ≤ 205000＝ũ－l

（3.2）

であるが、
～

u＊d /l＊d＝2.0 ≥ 1.976 ≈ ũ/lの範囲を、第 2 式を満たさない場合は、
u∈

（3.3）

リズムの step 2 において、P
m－ 1 ＊－dmmであればよい。

u∈

の範囲を探索すれば十分である。故に、アルゴ

より、
lb ≤

⎛ P － m－ 1 d＊，lbm⎝mである。ただし、初等計算により l＊d，u＊d より⎛ P－l＊d ，l ＋ d＊ ，⎝ m－１ b比がより小さい解が存在するならば、その下限
は l＊d より大きいことがいえる。すなわち、次

12

経営論集

Vol.5, No.6（2019）pp.1-24⎧u＊＊∈［l＊＊＋d＊， r＊d l＊＊ ］for⎜P
⎜ l＊＊∈ l＊ ＋ １ ，，d⎜
r＊+m－ 1
（3.7）
⎨ ＊＊
＊＊
＊
＊＊
［l ＋d ，P－（m－ １ ）l ］for
⎜u ∈
⎜
P－d＊
P
⎜ l＊＊∈，＊
mr +m－ 1⎩uP
P-(m-1)u=P-(m-1)l

u=r*l
d

u=l+(u*-l*)ddである。この領域が空ならば（l＊d，u＊d ）が最小比最適解である。等式

P/(m-1)(P-1)/(m-1)
u*d
P
―
m

u=l

u＊d ＝P－（m－ 1 ）l＊d（3.8）

が成立すれば、この領域は必ず空となる。m＝ 2

u=(P-l)/(m-1)のとき等式（3.8）は必ず成立するが、m ≥ 3の場合は成立するのは稀である。なお、式（3.7）

l*dにおける各 l＊＊ に対する u＊＊ の範囲それぞれに
第 2 妥当選挙区が存在しない場合も、この領域
P
―
m

l*d

0 1

は空となる。

l

アルゴリズムの step 3 において、step3.1は

図₃．₈：最小差最適解（l＊d，u＊d）よりよい比の実行

線形不等式系（3.6）による領域が空のときであ可能解 u＊＊が存在する範囲

り、このとき得られている u＊d ，l＊d が最小差最の Lemma3.2が成り立つ。

適解となることが上記よりわかる。領域が非空～

Lemma ₃．₂． u＊d ，l＊d と ũ，l がで、最小比が更新された場合（step3.3 u＊d /l＊dũu＊d
（ ０ ≤）u －l ≤ ũ－l かつ ＊ > （≥ 1 ）ldl≥ ũ/l ）は、この領域がより狭くなる。領域が非空で、最小比が更新されない場合（step3.2

を満たすならば、

u＊d /l＊d<ũ/l ）は、直線 u＝l ＋（ũ－l ）が、 2 直

＊
d

～

～

＊
d

～

～

～

l > l＊d線 u＝r＊l と u＝P－（m－ 1 ）l の交点の下を通（3.5）

が成り立つ（従って ũ > u＊d である）。

る（step3.2.1）か上を通る（step3.2.2）かで

Lemma 3.2より、アルゴリズムの step 3 に
＊
d

＊
d

＊＊

＊＊

～

場合わけされる。上を通る場合は探索領域が空）となる最小比となるので、現在得られている u＊d ，l＊d が最小最適解（l＊＊，u＊＊ ）が存在するならば、u＊＊ の比最適解となり、下を通る場合はその限りでは

存在範囲は図3.8の黄色三角形領域となる。すないので探索領域を更新してアルゴリズムは反おいて、（l ，u ）≠（l ，u

＊

＊
d

＊
d

＊

＊
d

＊
d

なわち、d ：＝u －l ，r ：＝u /l としたとき、

復する。

＊＊

u がとりうる範囲は、⎧u＊＊≤ r＊l，⎜⎨u＊＊≤ P－（m－ １ ）l，⎜ ＊＊＊⎩u ≥ l＋d

step 3 で 追 加 さ れ る カ ッ ト 不 等 式 は、
step3.3を経て 2 回目以降に追加される場合は、（3.6）

制約の本数が増えるのではなく、元の制約が強化されることに注意されたい。step 0 の lb，ub

で囲まれる三角形領域であり、の初期設定値は、33.33％ルール［59］より、

13

lb：＝

2
P
P
4
・
，ub：＝
・
とする15）。
3
m
3
m

3．4

アルゴリズムの計算量

交点①、Ⅰ

P
r＊P
⎛
⎞（3.12），＊＊⎝ r +m－ 1 r +m－ 1 ⎠（l，u）＝
交点②、Ⅱ⎛ P－d ， P+（m－ １ ）d ⎞（3.13）

m
⎝ m
⎠
～

このアルゴリズムの step 1 、 2 の反復回数は

交点③、Ⅲ

γl の設定法より高々 2 回であり、step 3 のγu，P－d＊－l＊d ＋ 1 回
反復回数は、自明には高々mである。従って、このアルゴリズムは有限回の（l，u）＝⎛ d ， r ＊d ⎞ ⎝ r＊－ １ r＊－ １ ⎠step 3 の 反 復 回 数 を よ り 詳 細 に 求 め る。
実行可能領域は、P⎧ ＊，
⎜l ＋ １ ≤ l ≤
m
⎨
（3.9）
⎜ ＊
｛r＊l，P－（m－ １ ）l｝⎩ l ＋ ２ ≤ u ≤ min

～

～

～

～

～

≥ d ≥ d＊＋ １～⇒∆≥（3.11）～＊d＊ũ－u ＝（l ＋d ）－（l ＋d ）∆≥～＝（l＊d＋∆＋d ）－（l＊d＋d＊）

１
r＊－１



（3.16）≥（l＊d＋∆＋d＊＋ 1 ）－（l＊d＋d＊）である。r＊<r のときは、図3.9の交点③の l 座＝∆＋ １

標が次の探索領域の l の下限なので、～だからである。

～～～（∵ u＊＝r＊l＊）



～

～

～

＊
d

～

d
d－（r＊l＊－l＊） d－（u＊－l＊）
－l＊＝
＝
＊
r －１
r＊－ １
r＊－ １

step 3 の中で繰り返しが起こるのは、step3.2.1
r＊P
P+（m－ １ ）d≥と、
step3.3
r＊<r かつ ＊r +m－ 1m＊r ≥ r の 2 つの場合である。step3.2.1は d＊＝
＊
d

l＊d
１
＝
d＊ r＊－１∆は整数なので、である。なぜなら、～～～である。∆：＝l －l＊d（≥ 1 ）とすると、

＊
d

～

d＊
d
d
r － １ ≥ r －１↔ ＊ ≥
＝ ＊
ld
l
＋∆
d
l
d＊ ＊
d＊
↔ ＊（l d ＋∆）＝d＊＋ ＊ ∆ldld＊（3.10）

ũ−u＊d ≥ ∆＋ １（≥ ２ ）

～

～

～

とおくと、
d ≥ d＊＋ 1 ，l > l＊d，ũ > u＊d d＊↔ r＊－１＝ ＊ldd↔ r －１＝lであるから、r＊≥ r の と き 、で あ る。step 3 に お い て、d：＝ũ−l ，r：＝ũ/l～（3.14）⎛ P －d ＊ ，P ＋（m －１）d ＊ ⎞（3.15）m⎝ m⎠⎧ u＊ ＝r＊l＊ ＝l＊ ＋ d＊
d
d
d
⎜
⎨
～
～
～
⎜
～
⎩ ũ＝r l ＝l ＋dstep 3 で解く Min-dif［lb，ub］の u，l に関する～～（l，u）＝となる。

～～

交点②’、ⅱ

反復で終了する。

～～（l，u）＝＝～

u －l より幅の広い最小差最適解 ũ，l が見つ

d－d＊
１
≥ ＊
（∵ d ＝d＊+１）
r＊－ １
r －１
～

となる。故に、次の探索領域までに少なくともかったが、最小比は更新されない場合であり、
step3.3は同じ状況で最小比が更新される場合

１
r＊－１である。それぞれ、図3.9、3.10の状況となる。

（3.17）の幅がある。つまり、step3.2.1、3.3ともに、
１
次の l の探索領域までの幅の下限が ＊でr －１ある。また、step3.2.1、3.3それぞれ l の上限

このとき、次の u の探索領域は 3 つの交点①、②、③か交点Ⅰ、Ⅱ、Ⅲで囲まれた三角形であり、図中の各交点の座標は

14

経営論集

Vol.5, No.6（2019）pp.1-24

u

u

ub

ub
ⅰ

①
③

~
u

Ⅰ

②

Ⅱ
②'

~
d

u*
P
m

ⅱ

~
u
u*

Ⅲ

d*

lb

~
d

ⅲ

P
m

d*

lb
Δ

45°

0

l* ~l

P
m

0

l

45°

Δ

l* ~l

P
m

l

図₃．₉：step₃．₂．₁の状況

図₃．₁₀：step₃．₃の状況

が交点②’→②（図3.9）、ⅱ→Ⅱ（図3.10）に

査速報人口、2016年行政界、構成要素：市区町

更新されるので、式（3.13），（3.15）より、村）を例として、step 1 の最適解 u＊d ，l＊d から～得られる step 3 の反復回数上限について、表～P －d ＊P －d
d －d ＊－＝m
m
m（3.18）

A.3にまとめた。 1 選挙区の鳥取県と実行不能ずつ小さくなる。

となる千葉県・富山県の 3 県を除いてある。鹿故に、アルゴリズムの step 3 は、児島県は 1 市、東京都は 5 区を人口過大選挙区として事前割当してある。表中の項目［X］は＊＊⎛ P －d － l＊ ⎞/ １ ＋ d－d
＊
d
m
m
⎝
⎠ r －１～高々＋ １ 回

式（3.19）の分子、［Y］は、式（3.17）、［ X/（3.19）
16）～

Y + 1 ］は、式（3.19）の値をそれぞれ示す。

＊の反復で終了する 。式（3.18）の d －d ≥ 1

ただし、式（3.19）の分母は、式（3.17）を用＊である。また、式（3.16），（3.17）における r

いて計算しているので注意されたい。また、表は単調非増加なので、実際の幅の減少速度は反は［ X/Y ＋ 1 ］の値で昇順に並べてある。

復のたびに加速されることに注意されたい。

9 県は 1 回、 5 県が 6 回以下となる。実際のstep 1 の実施は高々 2 回なので、アルゴリズム

事例での反復回数は少なく、例えばこの事例に全体として MIP を解く回数の上限は式（3.19）

お い て は、44都 道 府 県 の う ち43都 道 府 県 がの値 + 2 回である。

step3.1の実行不能で終了となり、唯一神奈川国政選挙（衆議院小選挙区制、2015年国勢調県のみが step3.2.1で解が 1 回更新されただけ

15

で終了する。2000年～2010年の事例においても手法が確立されている。

同様に、40都道府県以上は、step3.1の実行不4．3

能で終了となり、数県のみが step3.2.1の更新

最大・最小以外の選挙区の構成と選挙区の特徴化による選定に進む。従って、パラメトリックに分数計画を

区割画定を行う最適化モデルでは、最大・最解くよりこちらの方がはるかに効率が良い。

小人口の選挙区以外の選挙区には複数解がありその他の話題₄うる17）。政治的意義として、限界較差を示すという点では、これは問題にならないが、区割画

議席配分問題と区割画定問題について、それ定作業を支援するためや実際の区割として利用以外の知見も多く得られているので、簡単に触したい、という場合は、どの解を用いたら良いれておく。

かについて、何らかの指標があるとよい。第 k4．1

最適解の導出［16］や、高速列挙［27］による

較差最小配分モデル

複数解を見つけた後の評価法が与えられている

国政選挙（衆議院・小選挙区制）における小［19］。

選挙区（一人選出選挙区）の作成は、総議席数

まとめ₅m に等しい小選挙区をいきなり作るのではな
く、与えられたいくつかの地域（47都道府県）
へ条件（人口比例）にもとづき議席配分を行い、本論文では、根本・堀田［38，39］によってその後、各地域毎に区割を画定する。従って、確立された、選挙区画定問題の解法について、議席配分で較差が生じ、区割画定でその較差が特に最小比最適解を、パラメータを用いた分数

拡大することになる。議席配分と区割画定を同計画法を使わずに、どのように求めているのか時に考慮して較差を縮小させる方法が較差最小について詳細をまとめたものである。また、こ配分モデルである［38，39］。

のときの計算量（反復回数）を示した。通常、

4．2

分数計画問題の解法は、パラメータを適当に設

第 k 最適解の導出

定し、その値を二分探索や Newton 法などで追区割画定問題において、較差が小さい順に解跡するのが基本である。しかし、NP- 困難なを列挙したいとき、最適解を導いた後、制約に混合整数計画問題を複数回解かねばならず、現カットを加えて順次第 k 最適解を列挙すること

実の事例でこの手法を用いるのは現実的ではなができる［16］。また、この列挙では混合整数

い。選挙区画定問題においては、その構造の特計画問題を欲しい解の個数分解くことになるの殊性から、最小差最適解を複数回解けばよいこ

で、効率的ではない。較差の順に高速に解を列とを利用して最小比最適解を求められる。この挙することが求められる。これを実現するため手法の利点はパラメータを用いない、というこに、川原ら［27］により、フロンティア法ベーとと、同じ複数回解くといっても、現実の事例

スのアルゴリズムを用い、膨大な数に上る列挙

では、ほとんどの場合 2 回解けば十分である（最解を ZDD でコンパクトに保持しながら求める適性が担保される）ことから、非常に有効な方

16

経営論集

Vol.5, No.6（2019）pp.1-24法となる。

を mj で割った値（平均値）の最大と最小の比を最小化する最適化問題となる［21］。ただし、k注1 ）「有権者」を使う場合もある。また、同じ人口

は何らかの（政治的意義のある）規則のもとで制でも外国人を排除し「自国民に限る」場合もあるk ∈［ 1 ，m］で最適化すると、必ず k＝ 1 の自明（cf.［61］）。「外国人」「自国民」の定義はそれぞな最適解（全地域 1 選挙区）が得られるだけだか

限されることによる下限を設定する。なぜなら、れの制度による。

らである。

2 ） 日本の衆議院は小選挙区比例代表並立制であり6 ） 日本の市区町村の行政界には飛び地が複数存在

総定数は465議席、ドイツ連邦議会は小選挙区比するが、大きな飛び地は別の市区町村として扱い、

例代表併用制であり総定数は598議席、イギリス

詳細な地図を用いないと確認できないような細か

庶民院は2020年以降600議席となる予定、また 4な飛び地は同一の市区町村として扱う。陸地でな地域とはイングランド・ウェイルズ・スコットラ

く海・湖・沼などの上に境界線がある場合は、船・ンド・北アイルランドのこと。

飛行機などの定期航路や、橋が存在する場合のみ

3 ） 各手法の名前と別名は以下の通り。

隣接と考える。構成法より、陸上の隣接グラフはLRM ＝ Largest Remainders Method、最大剰余平面グラフとなるが、海上等では K 33（ 3 点× 2

法、Hamilton 法、Vinton 法の完全 2 部グラフ）の航路が現れる可能性もあり、SD ＝ Smallest Divisor method、 最 小 除 数 法、

その限りではない。また、市区町村が点を共有す

Adams 法る場合は隣接とは見なさない。隣接グラフの面は

HMD ＝ Harmonic Mean Divisor method、 調 和

殆どの場合三角形であるが、 4 市区町村が 1 点を平均法、Dean 法

共有する場合や境界が定まっていない場所等が一

GMD ＝ Geometric Mean Divisor method、幾何部見られ、四角形の面が現れる場合がある。

平均法、Hill 法、Huntington 法7 ） 都道府県毎の地域の組合（例：防災災害組合、AMD ＝ Arithmethic Mean Divisor method、 算学校組合、衛生施設組合、清掃管理組合、交通災

術平均法、Webster 法、Sainte-Lagüe 法

害共済組合、etc）や広域連合（中部ふるさと広LD ＝ Largest Divisor method、 最 大 除 数 法、

域連合、後期高齢者医療連合、etc）で同じ構成

Jeﬀerson 法、d’Hondt 法

団体となっている市町村や、小学校区、商圏など

4 ） 割当分特性を条件としない議席配分最適化モデ（cf. 総務省：衆議院議員選挙区画定審議会 議事

ルを、日本の国政選挙（衆議院・小選挙区制）に録など参照）

用いた場合、満たさない都道府県は、2010年人口8 ） 衆議院・小選挙区制（平均±33.33％［59］）、

では兵庫・愛知・大阪・神奈川・東京の 5 箇所、

アメリカ下院・小選挙区制（平均± 5 ％［ 4 ］）、

2015年人口では愛知・大阪・東京の 3 箇所（［20］、ドイツ連邦議会・小選挙区制（平均±15％［11，表2.1）で、いずれも人口の大きな都道府県への46，64］）、イギリス庶民院・小選挙区制（平均割当議席数を減らして較差を小さくする結果が得± 5 ％［46］）、フランス国民議会・小選挙区制（平られる。現状では、これらの地域に比べて人口が均±20％［46］）、オーストラリア連邦下院・小相対的に極端に少ない県への配分議席を増やすこ

選挙区制（平均±10％［46］）など。ただし、同とで較差が縮小する傾向があるためである。

じ小選挙区制でも、比例代表並立、比例代表併用、5 ） 大選挙区制や小＋大選挙区制の場合は、k（≤ m）

単純投票、 2 回投票など詳細はかなり異なる。ま

個の連結成分に分割し、各連結成分に m の割当

た、日・米・独・仏は人口だが、英・豪は有権者も考える。つまり、m1，...，m（m＝∑kj ＝ 1 mj）
kをもとに作成する。

も同時に決めることになる。またこのとき、目的9 ） 上限 ub は切り捨て値、下限 lb は切り上げ値を関数が連結成分 j を構成する点 i のコスト pi の和用いることに注意されたい。

17

［4］ K.D. Burnett： Congressional Apportionment,10） － 2 は、全集合と空集合を除くことに該当。
11） 1994年小選挙区制開始から2010年までは、市区2010 Census Briefs, U.S. Census Bureau（2011）.

町村ではなく市区郡が構成単位であった。人口過［5］ P.G. Cortona, C. Manzi, A. Pennisi, F. Ricca

大と事前割当については［38，39，14］などを参and B. Simeone：Evaluation and Optimization of

照のこと。

Electoral Systems SIAM（1999）.

PP12） 1 ≤ lb ≤≤≤ ub ≤ P−m+ 1mm13） lb, ub の設定の仕方（十分な幅を持たせず、狭［6］ B. Fleischmann and J.N. Paraschis：Solving aLarge Scale Districting Problem：A Case Report,

く設定した場合）によっては、最小差最適解が別

Computers and Operations Research 15-6（1988）に存在する可能性があることに注意されたい。

521–533.

１⎛< １ ⎞
14）α：＝⎛⎞P2 ―＋１ ⎝ ２⎠⎝ m⎠15） 単独の市区町村 i の人口 pi が ub より大きいと［7］ R.S. Garﬁnkel and G.L. Nemhauser：Optimal Political Districting by Implicit Enumeration Techniques, Management Science 16-8（1970）B495–
508.

きは実行不能となるので、市区町村を事前に分割して解くことになる［38，39］。そうでない場合［8］ B.C. Gearhart and J.M. Liittschwager：Legisla-

でも、隣接関係によっては実行不能となる。国政

tive Districting by Computer, Behavioral Science

選挙（衆議院小選挙区制）の場合は、千葉県が、14（1961）404–417.

松戸近辺の隣接関係により、実行不能となること［9］ J.A. George and B.W. Lamar and C.A. Wal-が 多 い［38，42，43，15，20］。 ま た、 第 2 妥 当

lace：Determining New Zealand Electoral Dis-

選 挙 区 の 列 挙 数 が 多 く、step 1 の Min-dif［lb，tricts Using a Network-Based Model, Operationalub］ の 求 解 が 困 難 な 場 合、lb，ub の 設 定 値 をResearch Society of New Zealand, Proceedings 29

33.33% より狭くとる。

（1993）276–283.
［10］ G.R. Grimmett：European apportionment via16） 最後の項＋ 1 は、最初の 1 回分である。アルゴ

the Cambridge Compromise, Mathematical Social＊

リズムが繰り返されるにつれて r は等しいか小P－d＊－l＊d の幅も更新されて狭m
くなっていき、∆は等しいか大きくなるので、実Sciences 63（2012）68-73.

さくなり、かつ［11］ S. Goderbauer : Political Districting for Elections to the German Bundestag：An Optimiza-

際の反復回数はもっと少ない。

tion-Based Multi-stage Heuristic Respecting Ad-17） 最大・最小人口を与える選挙区も複数解が存在

ministrative Boundaries, Operations Research

する場合もあることに注意されたい。

Proceedings（2014）181-187.
［12］ C.C. Harris：A Scientiﬁc Method of District-

参考文献

ing, Behavioral Science 9（1964）219–225.

［1］ M. L. Balinski and H. P. Young：Fair Repre-［13］ S.W. Hess, J.B. Weaver, H.J. Siegfeldt, J.N.

sentation 2nd ed, Brookings（2001）.

Whelan and P.A. Zitlau：Nonpartisan Political Re-［2］ C. Barnhart, E.L. Johnson, G.L. Nemhauser,
M.W.P. Savelsbergh and P.H. Vance：Branch-

districting by Computer, Operations Research 13

and-Price：Column Generation for Solving Huge

（1965）998–1008.
［14］ 堀田敬介：市区郡分割を考慮した選挙区画定

Integer Programs, Operations Research 46-3問題の最適化モデル，情報研究43（2010），41–60．

（1998）316–329.

［15］ 堀田敬介：衆議院議員小選挙区制最適区割［3］ B. Bozkaya, E. Erkut and G. Laporte：A tabu

2011，情報研究47（2012）43–83．

search heuristic and adaptive memory procedure［16］ 堀田敬介：選挙区割の最適化と列挙索引化，

for political districting, European Journal of Oper-オ ペ レ ー シ ョ ン ズ・ リ サ ー チ57-11（2012）623–

ational Research 144（2003）12–26.

18

経営論集

Vol.5, No.6（2019）pp.1-24
entropy and Stolarsky mean-divisor methods of628．

apportionment, Discussions Paper（2008）.

［17］ 堀田敬介：合県モデルと区割人口頑健性によ［32］ P.G. Marlin：Application of the Transporta-

る選挙制度の評価と提言，RIMS 研究集会報告集

tion Model to a Large-Scale “Districting” Prob-

1879（2014）79–90．

lem, Computers and Operations Research 8（1981）［18］ 堀田敬介：合区および総定数変化に対する議席

83–96.

配 分 最 適 化，Japanese Journal of Electoral Studies［33］ A. Mehrotra, E. Johnson and G. L. Nemhauser：

31- 2 （2015）123-141．
［19］ 堀田敬介：区割画定作業支援のための選挙区割

An optimization based heuristic for political dis-の特徴化，Transactions of the Operations Research

tricting. Management Science, 44-8（1998）1100–
1114.

Society of Japan 59（2016）60-85．

［34］ 三輪和宏、河島太朗：参議院の一票の格差・［20］ 堀田敬介：衆議院議員小選挙区制最適区割

定数是正問題，国立国会図書館調査と情報 -ISSUE

2016，経営論集 3 - 1 （2017） 1 -114．

BRIEF-610（2008）．

［21］ 堀田敬介：複数人選出選挙制度の較差是正の［35］ 森脇俊雅：小選挙区制と区割り－制度と実態ための最適化と限界値分析，Transactions of theの国際比較－，芦書房（1998）．

Operations Research Society of Japan 60（2017）［36］ S.S. Nagel：Simpliﬁed Bipartisan Computer

74-99．

Redistricting, Stanford Law Review 17（1965）［22］ 堀田敬介：指定都市議会議員選挙の投票価値

863–899.

の平等，経営論集 5 - 3 （2019） 1 -20.

［37］ S.S. Nagal：Computers and the Law and Pol-［23］ 堀田敬介、根本俊男、和田淳一郎：参議院最itics of Redistricting, Polity 5（1972）77–93.

適合区について，公共選択学会 大会 報告論文

［38］ 根本俊男、堀田敬介：区割画定問題のモデル（2017/11/18）．

化と最適区割の導出，オペレーションズ・リサー［24］ 岩崎美紀子：選挙と議会の比較政治学，岩波チ48- 4 （2003）300–306．

現代全書（2016）．
［25］ 岩崎正洋 編：選挙と民主主義，
吉田書店（2013）．

［39］ 根本俊男、堀田敬介：選挙区最適区割問題の［26］ H.F. Kaiser：An Objective Method for Estab-

モデリングと厳密解導出，第15回 RAMP シンポジ
ウム論文集（2003）104–117．

lishing Legislative Districts, Midwest Journal of［40］ 根本俊男、堀田敬介：衆議院小選挙区制におPolitical Science 10（1966）200–213.

ける一票の重みの格差の限界とその考察，選挙研［27］ J. Kawahara, T. Horiyama, K. Hotta and S.

究20（2005）136–147．

Minato：Generating all patterns of graph partitions within a disparity bound, In Proceedings of［41］ 根本俊男、堀田敬介：公平な小選挙区制のた

the 11th International Conference and Workshops

めの数理モデル，システム / 制御 / 情報49- 3（2005）

on Algorithms and Computation（WALCOM2017）,78-83．
［42］ 根本俊男、堀田敬介：一票の重みの格差から10167（2017）119–131.

観た小選挙区数，選挙研究21（2006）169–181．

［28］ 河村和徳：現代日本の地方選挙と住民意識，［43］ 根本俊男、堀田敬介：平成大合併を経た衆議

慶応義塾大学出版会（2008）．

院小選挙区制区割環境の変化と一票の重みの格差，［29］ 久保幹雄、田村明久、松井知己編：応用数理

Transactions of the Operations Research Society of計画ハンドブック，朝倉書店（2002）．

Japan 53（2010）90–113.

［30］ 今野浩、鈴木久敏編：整数計画法と組合せ最［44］ 西平重喜：各国の選挙 ―変遷と実状―，木鐸

適化，日科技連（1982）．

社（2003）．

［31］ L. Lauwers and T. Van Puyenbroeck：Mini-［45］ 小川 泰：かたちの万華鏡〈 2 〉民主主義の幾mally disproportional representation：generalized19

基づく区割りの改定案の作成方針（2012）．

何学，数学セミナー 40- 5 （2001） 2 – 3 ．

［61］ 衆議院議員選挙区画定審議会：区割り改定案［46］ 大林啓吾、白水隆 編著：世界の選挙制度，三の作成方針（2016）．

省堂（2018）．

［62］ 高橋秀雄：ミニマックス全域森問題に関する［47］ 大山達雄：選挙区議員定数問題の数理，オペ研究，防衛大学修士論文（1995）．

レーションズ・リサーチ32- 5 （1987）269–280．

［63］ 鳥井修：グラフ上の頂点分割問題，東京大学［48］ 大山達雄：選挙区事例からみた議員定数配分

修士論文（1995）．

方法の比較分析，オペレーションズ・リサーチ［64］ 梅津實、森脇俊雅、坪郷實、後房雄、大西裕、

32- 8 （1987）551–561．

山田真裕：新版 比較・選挙政治－21世紀初頭にお［49］ T. Oyama：On a Parametric Divisor Method
for the Apportionment Problem, Journal of the

ける先進 6 カ国の選挙－，ミネルヴァ書房（2004）．

Operations Research Society of Japan 34-2（1991）［65］ W. Vickrey：On the Prevention of Gerrymandering, Political Science Quarterly 76（1961）

187–221.

105–110.

［50］ T. Oyama and T. Ichimori： On the Unbi-［66］ 和田淳一郎：一票の平等について，公共選択

asedness of the Parametric Divisor Method forの研究26（1995）58–67．

the Apportionment Problem, Journal of the Oper-［67］ 和田淳一郎：議席配分の方法としてのサン =ations Research Society of Japan 38-3（1995）

ラグ方式，公共選択の研究18（1991）92–102．

301–321.
［51］ T. Radzik：Newton’s method for fractional［68］ J. Wada：Evaluating the unfairness of repre-

combinatorial optimization, Proceedings., 33rd

sentation with the Nash social welfare function,
Journal of Theoretical Politics 22-4（2010）445–467.

Annual Symposium on Foundations of Computer［69］ 和田淳一郎：一票の平等，公共選択の研究57

Science（1992）659–669.

（2011）64–71．

［52］ 最高裁判所：平成25（行ツ）第209，210，211号選挙無効請求事件［70］ 和田淳一郎：定数配分と区割り－経済学の視

平成25年11月20日大法廷判

点から－，選挙研究28- 2 （2012）26–39．

決（2013）．

［71］ J. Wada：A divisor apportionment method［53］ 斎藤孝之、武藤佳恭：小選挙区区割り問題，

based on the Kolm-Atkinson social welfare func-

Bit 28- 7 （1996）88–91．

tion and generalized entropy, Mathematical Social［54］ 坂口利裕、和田淳一郎：選挙区割りの最適化

Sciences, 63（2012）243–247.

について，三田学会雑誌93- 1 （2000）109–137．
［55］ 坂口利裕、和田淳一郎：選挙区割り問題，オ［72］ J. C. Williams,Jr.：Political Redistricting：A

ペレーションズ・リサーチ，48- 1 （2003）30–35．

Review, Papers in Regional Science 74-1（1995）
13–40.

［56］ 佐藤令：衆議院及び参議院における一票の格［73］ J.B. Weaver and S.W. Hess：A Procedure for

差，国立国会図書館調査と情報－ISSUE BRIEF－

Nonpartisan Districting：Development of Com-714（2011）．

puter Techniques, The Yale Law Journal 72［57］ 佐藤令：諸外国の選挙制度，国立国会図書館（1963）288-308.

調査と情報－ISSUE BRIEF－721（2011）．
［58］ 佐藤令：諸外国における選挙区割りの見直し，［74］ T. Yamada, H. Takahashi and S. Kataoka：A

国立国会図書館 調査と情報－ISSUE BRIEF－782

branch-and-bound algorithm for the mini-max（2013）．

spanning forest problem, European Journal of Operational Research 101（1997）93–103.

［59］ 衆議院議員選挙区画定審議会：区割りの改定［75］ T. Yamada and H. Takahashi：The mini-

案の作成方針（2001）．

max spanning forest problem with an application［60］ 衆議院議員選挙区画定審議会：緊急是正法に

20

経営論集

Vol.5, No.6（2019）pp.1-24
terly XIII（1988）105–115.

to electoral districting, NDA discussion paper［77］ 大和 毅彦：議員定数配分方式について－定数（1997）.

削減、人口変動と整合性の観点から－，オペレー［76］ H.P. Young：Measuring the Compactness of

ションズ・リサーチ48-1（2003）23–29．

Legislative Districts, Legislative Studies Quar-

21

A

付録
表 A．₁：第 ₂ 妥当選挙区数（衆議院小選挙区、₂₀₁₅速報人口・₂₀₁₆行政界、±₃₃．₃％）

id

都道府県

人口

m

平均

|V |

|E |

全選挙区

第 ₁ 妥当第 ₂ 妥当

₁
₂₀
₄₀
₂₁
₇
₁₅

北海道
長野県
福岡県
岐阜県
福島県
新潟県

₅︐₃₈₃︐₅₇₉
₂︐₀₉₉︐₇₅₉
₅︐₁₀₂︐₈₇₁
₂︐₀₃₂︐₅₃₃
₁︐₉₁₃︐₆₀₆
₂︐₃₀₅︐₀₉₈

₁₂
₅
₁₁
₅
₅
₅

₄₄₈︐₆₃₂
₄₁₉︐₉₅₂
₄₆₃︐₈₉₇
₄₀₆︐₅₀₇₃₈₂︐₇₂₁₄₆₁︐₀₂₀

₆₈
₄₂
₅₆
₃₆
₃₁
₃₈

₁₆₁
₉₉
₁₂₃
₈₀
₇₃
₈₁

₆₆₆︐₀₅₃︐₆₆₃
₈︐₃₄₀︐₃₇₇
₉₅₇︐₅₄₀
₃︐₃₄₇︐₂₂₆
₁︐₆₇₆︐₂₆₅
₁︐₀₉₇︐₉₃₇

₆₆₅︐₁₁₈︐₄₄₁
₈︐₃₂₈︐₄₃₈
₉₅₂︐₀₇₁
₃︐₃₃₉︐₉₈₆
₁︐₆₆₇︐₁₀₈
₁︐₀₉₄︐₂₀₆

₃₄︐₈₀₆︐₄₁₇
₉₄₅︐₆₆₈
₂₆₉︐₇₉₀
₂₆₈︐₁₉₉
₂₅₂︐₀₉₃
₁₂₈︐₄₃₄

₃
₁₁
₆
₈
₁₂
₂₈

岩手県
埼玉県
山形県
茨城県
千葉県
兵庫県

₁︐₂₇₉︐₈₁₄
₇︐₂₆₁︐₂₇₁
₁︐₁₂₂︐₉₅₇
₂︐₉₁₇︐₈₅₇
₆︐₂₂₄︐₀₂₇
₅︐₅₃₆︐₉₈₉

₃
₁₆
₃
₇
₁₄
₁₂

₄₂₆︐₆₀₅
₄₅₃︐₈₂₉₃₇₄︐₃₁₉
₄₁₆︐₈₃₇
₄₄₄︐₅₇₃
₄₆₁︐₄₁₆

₂₇
₆₃
₂₃
₄₁
₅₃
₄₆

₆₀
₁₅₈
₅₁
₈₇
₁₁₇
₁₀₀

₂︐₀₈₀︐₅₄₂
₇₁︐₅₁₉₃₇₀︐₈₃₄
₈₅︐₆₀₃
₂₉₀︐₄₅₃
₂₄₃︐₈₅₆

₂︐₀₆₃︐₀₁₄
₇₀︐₃₅₁
₃₅₅︐₅₄₉
₈₄︐₅₄₈₂₈₇︐₉₄₈
₂₃₉︐₁₃₄

₄₇︐₈₀₀₃₄︐₈₂₃₂₅︐₃₀₇
₂₄︐₅₁₁
₂₃︐₈₇₃
₁₈︐₄₉₈

₂₃
₄₆
₂₇
₃₄
₂₂
₁₉
₂₉
₃₃
₂
₂₆
₁₃
₄₃
₉

愛知県
鹿児島県
大阪府
広島県
静岡県
山梨県
奈良県
岡山県
青森県
京都府
東京都
熊本県
栃木県

₇︐₄₈₄︐₀₉₄
₁︐₆₄₈︐₇₅₂
₈︐₈₃₈︐₉₀₈
₂︐₈₄₄︐₉₆₃
₃︐₇₀₁︐₁₈₁
₈₃₅︐₁₆₅
₁︐₃₆₅︐₀₀₈
₁︐₉₂₂︐₁₈₁
₁︐₃₀₈︐₆₄₉
₂︐₆₁₀︐₁₄₀
₁₃︐₅₁₃︐₇₃₄
₁︐₇₈₆︐₉₆₉
₁︐₉₇₄︐₆₇₁

₁₇
₄
₂₀
₆
₈
₂
₃
₅
₃
₆
₃₀
₄
₅

₄₄₀︐₂₄₁
₄₁₂︐₁₈₈₄₄₁︐₉₄₅₄₇₄︐₁₆₁
₄₆₂︐₆₄₈₄₁₇︐₅₈₃
₄₅₅︐₀₀₃
₃₈₄︐₄₃₆₄₃₆︐₂₁₆
₄₃₅︐₀₂₃₄₅₀︐₄₅₈₄₄₆︐₇₄₂₃₉₄︐₉₃₄

₆₂
₃₁
₆₉
₂₈
₃₈
₁₉
₁₉
₂₈
₂₅
₃₃
₅₆
₂₉
₂₂

₁₅₇
₅₈
₁₆₁
₅₇
₈₀
₄₃
₄₂
₆₀
₄₈
₇₁
₁₃₇
₅₅
₄₇

₉︐₄₉₅
₆₅₈︐₄₁₆
₆︐₅₃₈
₂₃︐₁₀₁
₁₂︐₂₇₃
₉₄︐₉₃₇
₃₁︐₂₃₀₂₀₅︐₄₀₇₁₁₀︐₂₁₉
₆︐₈₁₉
₂︐₂₂₅
₄₇︐₃₁₆₃︐₉₁₁

₉︐₁₄₄
₆₅₅︐₉₅₈
₆︐₂₀₇
₂₂︐₆₃₄
₁₁︐₆₆₁
₉₂︐₆₀₀₂₉︐₇₁₀₁₉₆︐₆₃₃
₁₀₈︐₀₂₈
₆︐₃₂₀
₂︐₀₂₀
₄₆︐₅₇₁
₃︐₅₂₅

₇︐₅₇₆
₆︐₁₂₆
₅︐₅₀₆
₄︐₈₆₇
₄︐₇₁₉
₄︐₆₀₆
₄︐₅₉₀
₄︐₁₆₅
₂︐₆₀₆
₁︐₆₄₄
₁︐₄₆₄
₁︐₄₆₀
₁︐₀₁₉

₂₅
₅
₄
₁₀
₁₄
₃₆
₄₅
₄₄
₄₂
₁₈
₃₈
₃₅
₃₀
₃₉
₃₇
₃₂
₄₇
₄₁
₂₄
₁₆
₁₇
₃₁

滋賀県
秋田県
宮城県
群馬県
神奈川県
徳島県
宮崎県
大分県
長崎県
福井県
愛媛県
山口県
和歌山県
高知県
香川県
島根県
沖縄県
佐賀県
三重県
富山県
石川県
鳥取県

₁︐₄₁₃︐₁₈₄
₁︐₀₂₂︐₈₃₉
₂︐₃₃₄︐₂₁₅
₁︐₉₇₃︐₄₇₆
₉︐₁₂₇︐₃₂₃
₇₅₆︐₀₆₃
₁︐₁₀₄︐₃₇₇
₁︐₁₆₆︐₇₂₉
₁︐₃₇₇︐₇₈₀
₇₈₇︐₀₉₉
₁︐₃₈₅︐₈₄₀
₁︐₄₀₅︐₀₀₇
₉₆₃︐₈₅₀
₇₂₈︐₄₆₁
₉₇₆︐₇₅₆
₆₉₄︐₁₈₈
₁︐₄₃₄︐₁₃₈
₈₃₃︐₂₄₅
₁︐₈₁₅︐₈₂₇
₁︐₀₆₆︐₈₈₃
₁︐₁₅₄︐₃₄₃
₅₇₃︐₆₄₈

₃
₂
₅
₅
₂₀
₂
₃
₃
₃
₂
₃
₃
₂
₂
₂
₂
₃
₂
₄
₃
₃
₁

₄₇₁︐₀₆₁
₅₁₁︐₄₂₀
₄₆₆︐₈₄₃₃₉₄︐₆₉₅
₄₅₆︐₃₆₆
₃₇₈︐₀₃₂
₃₆₈︐₁₂₆
₃₈₈︐₉₁₀₄₅₉︐₂₆₀
₃₉₃︐₅₅₀
₄₆₁︐₉₄₇
₄₆₈︐₃₃₆₄₈₁︐₉₂₅₃₆₄︐₂₃₁₄₈₈︐₃₇₈
₃₄₇︐₀₉₄
₄₇₈︐₀₄₆
₄₁₆︐₆₂₃
₄₅₃︐₉₅₇
₃₅₅︐₆₂₈
₃₈₄︐₇₈₁₅₇₃︐₆₄₈

₁₇
₂₁
₂₈
₂₂
₅₀
₁₇
₁₆
₁₇
₁₈
₁₆
₁₈
₁₈
₁₆
₂₀
₁₅
₁₃
₂₁
₁₇
₂₂
₁₂
₁₇
₁₀

₃₄
₄₂
₅₆
₄₄
₁₁₄
₃₅
₃₀
₃₁
₂₇
₂₅
₂₉
₃₀
₂₅
₃₄
₂₄
₂₀
₂₉
₂₅
₃₃
₁₉
₂₅
₁₁

₄︐₄₆₂
₉₈︐₉₇₇
₆︐₅₀₂
₁︐₆₀₂
₆₉₇
₂₀︐₁₆₃
₂︐₃₉₆
₃︐₉₄₅
₂︐₄₈₁
₁︐₃₅₇
₄︐₉₅₅
₁︐₃₈₃
₃︐₁₀₉
₈︐₈₈₁
₁︐₂₂₃
₅₃₇
₁︐₉₁₃
₁︐₈₁₀
₃₂₁
₆₈
₂₆₄
₁

₄︐₀₈₇
₉₅︐₅₄₁
₆︐₀₂₈
₁︐₄₂₃
₆₀₀
₁₄︐₈₁₇
₂︐₀₇₃
₃︐₃₆₃
₂︐₃₀₅
₁︐₁₂₁
₃︐₉₁₉
₁︐₂₀₈
₂︐₁₁₀
₆︐₇₄₁
₁︐₀₁₃
₃₉₆
₁︐₈₃₀
₁︐₄₈₁
₁₆₉
₂₉
₂₄
₁

₉₁₇
₆₅₄
₅₆₃
₄₉₈
₄₁₈
₂₇₂
₁₁₉
₁₀₆
₉₉
₆₂
₄₉
₄₈
₄₀
₂₆
₂₀
₂₀
₁₇
₁₆
₁₃
₁₁
₄
₁

22

経営論集

Vol.5, No.6（2019）pp.1-24
表 A．₂： ₀ ︲ ₁ 変数固定数（衆議院小選挙区、₂₀₀₅速報総人口・₂₀₀₆行政界、±₃₃．₃％）

id

都道府県

₁₁ 埼玉県
₂₃ 愛知県人口

平均m

₀︲₁ 変数

|V |

固定

非固定

₇︐₀₅₃︐₆₈₉
₇︐₂₅₄︐₄₃₂

₁₅
₁₅

₄₇₀︐₂₄₆
₄₈₃︐₆₂₉

₆₇
₆₄

₂︐₀₁₀
₁︐₉₂₀

₇₇₉
₈₄₉

₁︐₂₃₁
₁︐₀₇₁

₂₇
₄₀
₁₄
₁₃
₁₂

大阪府
₈︐₈₁₇︐₀₁₀
福岡県
₅︐₀₄₉︐₁₂₆
神奈川県
₈︐₇₉₀︐₉₀₀
東京都
₁₂︐₅₇₀︐₉₀₄
千葉県
₆︐₀₅₆︐₁₅₉

₁₇
₁₁
₁₇
₂₁
₁₂

₅₁₈︐₆₄₈
₄₅₉︐₀₁₁₅₁₇︐₁₁₂₅₉₈︐₆₁₄₅₀₄︐₆₈₀

₆₃
₅₉
₅₁
₅₆
₅₁

₂︐₁₄₂
₁︐₂₉₈
₁︐₇₃₄
₂︐₃₅₂
₁︐₂₂₄

₁︐₂₇₆
₅₄₅
₉₉₁
₁︐₆₅₃
₆₉₆

₈₆₆
₇₅₃
₇₄₃
₆₉₉
₅₂₈

₂₈
₈
₂₂
₂₀
₂₆
₂₁
₃₄
₄
₇
₄₆
₃
₁₀
₉
₃₃
₄₃
₁₅
₆
₁

兵庫県
茨城県
静岡県
長野県
京都府
岐阜県
広島県
宮城県
福島県
鹿児島県
岩手県
群馬県
栃木県
岡山県
熊本県
新潟県
山形県
北海道

₅︐₅₉₀︐₃₈₁
₂︐₉₇₅︐₀₂₃
₃︐₇₉₂︐₄₅₇
₂︐₁₉₆︐₀₁₂
₂︐₆₄₇︐₅₂₃
₂︐₁₀₇︐₂₉₃
₂︐₈₇₆︐₇₆₂
₂︐₃₅₉︐₉₉₁
₂︐₀₉₁︐₂₂₃
₁︐₇₅₃︐₁₄₄
₁︐₃₈₅︐₀₃₇
₂︐₀₂₄︐₀₄₄
₂︐₀₁₆︐₄₅₂
₁︐₉₅₇︐₀₅₆
₁︐₈₄₂︐₁₄₀
₂︐₄₃₁︐₃₉₆
₁︐₂₁₆︐₁₁₆
₅︐₆₂₇︐₄₂₄

₁₂
₇
₈
₅
₆
₅
₇
₆
₅
₃
₄
₅
₅
₄
₄
₅
₃
₁₂

₄₆₅︐₈₆₅
₄₂₅︐₀₀₃
₄₇₄︐₀₅₇
₄₃₉︐₂₀₂₄₄₁︐₂₅₄₄₂₁︐₄₅₉
₄₁₀︐₉₆₆
₃₉₃︐₃₃₂
₄₁₈︐₂₄₅₅₈₄︐₃₈₁₃₄₆︐₂₅₉
₄₀₄︐₈₀₉₄₀₃︐₂₉₀₄₈₉︐₂₆₄
₄₆₀︐₅₃₅
₄₈₆︐₂₇₉
₄₀₅︐₃₇₂
₄₆₈︐₉₅₂

₄₆
₄₁
₃₈
₄₂
₃₁
₃₆
₂₈
₂₈
₃₀
₃₄
₂₆
₂₆
₂₅
₂₇
₂₇
₃₁
₂₃
₂₅

₁︐₁₀₄
₅₇₄
₆₀₈
₄₂₀
₃₇₂
₃₆₀
₃₉₂
₃₃₆
₃₀₀
₂₀₄
₂₀₈
₂₆₀
₂₅₀
₂₁₆
₂₁₆
₃₁₀
₁₃₈
₆₀₀

₆₃₆
₁₃₅
₂₈₅
₁₂₄
₁₁₀
₁₀₁
₁₉₃
₁₄₈
₁₁₅
₅₅
₇₂
₁₂₅
₁₁₅
₈₈
₈₈
₁₉₁
₃₀
₅₀₀

₄₆₈
₄₃₉
₃₂₃
₂₉₆
₂₆₂
₂₅₉
₁₉₉
₁₈₈
₁₈₅
₁₄₉
₁₃₆
₁₃₅
₁₃₅
₁₂₈
₁₂₈
₁₁₉
₁₀₈
₁₀₀

₄₇
₁₉
₂₅
₂₉
₂₄
₂
₅
₄₅
₃₅
₃₉
₃₈
₃₆
₄₂
₄₄
₁₈
₃₀
₃₂
₁₇
₄₁
₃₁
₁₆
₃₇

沖縄県
山梨県
滋賀県
奈良県
三重県
青森県
秋田県
宮崎県
山口県
高知県
愛媛県
徳島県
長崎県
大分県
福井県
和歌山県
島根県
石川県
佐賀県
鳥取県
富山県
香川県

₁︐₃₆₀︐₈₃₀
₈₈₄︐₅₃₁
₁︐₃₈₀︐₃₄₃
₁︐₄₂₁︐₃₆₇
₁︐₈₆₇︐₁₆₆
₁︐₄₃₆︐₆₂₈
₁︐₁₄₅︐₄₇₁
₁︐₁₅₂︐₉₉₃
₁︐₄₉₂︐₅₇₅
₇₉₆︐₂₁₁
₁︐₄₆₇︐₈₂₄
₈₀₉︐₉₇₄
₁︐₄₇₈︐₆₃₀
₁︐₂₀₉︐₅₈₇
₈₂₁︐₅₈₉
₁︐₀₃₆︐₀₆₁
₇₄₂︐₁₃₅
₁︐₁₇₃︐₉₉₄
₈₆₆︐₄₀₂₆₀₆︐₉₄₇
₁︐₁₁₁︐₆₀₂
₁︐₀₁₂︐₂₆₁

₄
₃
₄
₄
₅
₄
₃
₃
₄
₃
₃
₃
₄
₃
₃
₃
₂
₃
₃
₂
₃
₃

₃₄₀︐₂₀₈
₂₉₄︐₈₄₄
₃₄₅︐₀₈₆
₃₅₅︐₃₄₂
₃₇₃︐₄₃₃
₃₅₉︐₁₅₇
₃₈₁︐₈₂₄
₃₈₄︐₃₃₁
₃₇₃︐₁₄₄
₂₆₅︐₄₀₄
₄₈₉︐₂₇₅
₂₆₉︐₉₉₁
₃₆₉︐₆₅₈
₄₀₃︐₁₉₆
₂₇₃︐₈₆₃₃₄₅︐₃₅₄
₃₇₁︐₀₆₈
₃₉₁︐₃₃₁
₂₈₈︐₈₀₁
₃₀₃︐₄₇₄
₃₇₀︐₅₃₄
₃₃₇︐₄₂₀

₂₁
₂₀
₂₀
₁₉
₂₂
₂₅
₂₁
₂₀
₁₉
₂₀
₁₈
₁₇
₁₈
₁₇
₁₆
₁₆
₁₅
₁₇
₁₉
₁₀
₁₂
₁₅

₁₆₈
₁₂₀
₁₆₀
₁₅₂
₂₂₀
₂₀₀
₁₂₆
₁₂₀
₁₅₂
₁₂₀
₁₀₈
₁₀₂
₁₄₄
₁₀₂
₉₆
₉₆
₆₀
₁₀₂
₁₁₄
₄₀
₇₂
₉₀

₇₂
₂₅
₆₆
₅₉
₁₂₉
₁₁₈
₅₃
₅₂
₉₇
₆₅
₅₄
₄₈
₉₅
₅₄
₄₉
₅₁
₁₈
₈₆
₁₀₃
₂₉
₆₇
₉₀

₉₆
₉₅
₉₄
₉₃
₉₁
₈₂
₇₃
₆₈
₅₅
₅₅
₅₄
₅₄
₄₉
₄₈
₄₇
₄₅
₄₂
₁₆
₁₁
₁₁
₅
₀

23

表 A．₃：アルゴリズム step ₃ 反復回数上限値（衆議院小選挙区、₂₀₁₅速報総人口・₂₀₁₆行政界）
id

都道府県

人口

m

u＊d

l＊d

₂
₃
₅
₆
₁₉
₂₀
₂₉
₃₆
₃₉

青森県
岩手県
秋田県
山形県
山梨県
長野県
奈良県
徳島県
高知県

₁︐₃₀₈︐₆₄₉
₁︐₂₇₉︐₈₁₄
₁︐₀₂₂︐₈₃₉
₁︐₁₂₂︐₉₅₇
₈₃₅︐₁₆₅
₂︐₀₉₉︐₇₅₉
₁︐₃₆₅︐₀₀₈
₇₅₆︐₀₆₃
₇₂₈︐₄₆₁

₃
₃
₂
₃
₂
₅
₃
₂
₂

₄₃₆︐₃₉₂
₄₂₆︐₇₃₇
₅₁₁︐₅₃₃
₃₇₄︐₃₄₆
₄₁₇︐₆₁₅₄₂₀︐₁₇₉
₄₅₅︐₀₆₃
₃₇₈︐₀₇₃₃₆₄︐₄₂₅

₄₃₅︐₈₉₄
₄₂₆︐₅₀₄
₅₁₁︐₃₀₆
₃₇₄︐₂₈₈
₄₁₇︐₅₅₀
₄₁₉︐₈₅₂
₄₅₄︐₉₇₂
₃₇₇︐₉₉₀₃₆₄︐₀₃₆

₄₉₈
₂₃₃
₂₂₇
₅₈
₆₅
₃₂₇
₉₁
₈₃
₃₈₉

₁．₀₀₁
₁．₀₀₁
₁．₀₀₀
₁．₀₀₀
₁．₀₀₀
₁．₀₀₁
₁．₀₀₀
₁．₀₀₀
₁．₀₀₁

₃₂₁
₁₀₀
₁₁₂
₃₀
₃₁
₉₉
₃₀
₄₀
₁₉₃

₈₇₆
₁︐₈₃₁
₂︐₂₅₃
₆︐₄₅₄
₆︐₄₂₄
₁︐₂₈₄
₅︐₀₀₀
₄︐₅₅₅
₉₃₆

₁
₁
₁
₁
₁
₁
₁
₁
₁

₇
₄₃
₄₆
₂₁
₃₀

福島県
熊本県
鹿児島県
岐阜県
和歌山県

₁︐₉₁₃︐₆₀₆
₁︐₇₈₆︐₉₆₉
₁︐₆₄₈︐₇₅₂
₂︐₀₃₂︐₅₃₃
₉₆₃︐₈₅₀₅₄
₄
₅
₂

₃₈₃︐₂₉₇₄₄₇︐₆₃₀
₄₁₃︐₄₉₂
₄₀₇︐₁₉₄
₄₈₃︐₀₆₉

₃₈₂︐₁₅₇
₄₄₆︐₁₀₂₄₁₁︐₅₃₂
₄₀₅︐₂₆₂
₄₈₀︐₇₈₁

₁︐₁₄₀
₁︐₅₂₈
₁︐₉₆₀
₁︐₉₃₂
₂︐₂₈₈

₁．₀₀₃
₁．₀₀₃
₁．₀₀₅
₁．₀₀₅
₁．₀₀₅

₅₆₃
₆₃₉
₆₅₅
₁︐₂₄₄
₁︐₁₄₃

₃₃₆
₂₉₂
₂₁₀
₂₁₀
₂₁₁

₂
₃
₄
₆
₆

₁₅ 新潟県
₄₇ 沖縄県₃₂ 島根県₂︐₃₀₅︐₀₉₈
₁︐₄₃₄︐₁₃₈
₆₉₄︐₁₈₈₅
₃
₂

₄₆₅︐₃₄₅
₄₈₀︐₈₁₁₃₅₁︐₀₄₃₄₅₇︐₇₆₈
₄₇₃︐₇₄₈
₃₄₃︐₁₄₅

₇︐₅₇₇
₇︐₀₆₃
₇︐₈₉₈

₁．₀₁₇
₁．₀₁₅
₁．₀₂₃

₃︐₂₅₁
₄︐₂₉₇
₃︐₉₄₈

₆₁
₆₈
₄₄

₅₄
₆₄
₉₀

₈
₂₅
₄₁
₄
₄₂
₁₈
₂₆
₃₄

茨城県
滋賀県
佐賀県
宮城県
長崎県
福井県
京都府
広島県

₂︐₉₁₇︐₈₅₇
₁︐₄₁₃︐₁₈₄
₈₃₃︐₂₄₅
₂︐₃₃₄︐₂₁₅
₁︐₃₇₇︐₇₈₀
₇₈₇︐₀₉₉
₂︐₆₁₀︐₁₄₀
₂︐₈₄₄︐₉₆₃

₇
₃
₂
₅
₃
₂
₆
₆

₄₂₁︐₇₀₄
₄₇₇︐₆₂₈
₄₂₃︐₅₄₆₄₇₄︐₅₉₂
₄₆₈︐₂₀₉₄₀₂︐₀₄₁₄₅₄︐₈₇₄
₄₉₉︐₄₁₉₄₁₂︐₂₉₉
₄₆₆︐₂₂₁₄₀₉︐₆₉₉
₄₅₉︐₀₂₄₄₅₀︐₁₁₃₃₈₅︐₀₅₈
₄₂₇︐₄₇₁₄₆₅︐₀₀₄

₉︐₄₀₅
₁₁︐₄₀₇
₁₃︐₈₄₇
₁₅︐₅₆₈₁₈︐₀₉₆
₁₆︐₉₈₃₂₇︐₄₀₃₃₄︐₄₁₅

₁．₀₂₃
₁．₀₂₄
₁．₀₃₄
₁．₀₃₄
₁．₀₄₀
₁．₀₄₄
₁．₀₆₄
₁．₀₇₄

₄︐₅₃₇
₄︐₈₃₉
₆︐₉₂₂
₇︐₈₁₈
₉︐₁₄₆
₈︐₄₉₀
₇︐₅₅₂
₉︐₁₅₆

₄₄
₄₁
₃₀
₃₀
₂₅
₂₃
₁₆
₁₄

₁₀₄
₁₁₉
₂₃₁
₂₆₁
₃₆₆
₃₇₀
₄₇₃
₆₅₅

₂₃
₁
₁₀
₃₅
₄₅
₂₂
₄₀
₂₈
₁₁

愛知県
北海道
群馬県
山口県
宮崎県
静岡県
福岡県
兵庫県
埼玉県

₇︐₄₈₄︐₀₉₄
₅︐₃₈₃︐₅₇₉
₁︐₉₇₃︐₄₇₆
₁︐₄₀₅︐₀₀₇
₁︐₁₀₄︐₃₇₇
₃︐₇₀₁︐₁₈₁
₅︐₁₀₂︐₈₇₁
₅︐₅₃₆︐₉₈₉
₇︐₂₆₁︐₂₇₁

₁₇
₁₂
₅
₃
₃
₈
₁₁
₁₂
₁₆

₄₆₇︐₇₅₂
₄₇₅︐₇₁₀₄₀₈︐₃₆₃
₄₈₂︐₈₉₃
₄₀₁︐₁₅₆
₄₈₅︐₅₈₇
₅₂₁︐₄₄₉
₅₃₅︐₈₀₇₅₇₈︐₂₄₅₄₂₇︐₅₁₇₄₃₅︐₃₂₆
₃₇₅︐₃₀₉₄₄₅︐₉₈₁₃₅₁︐₄₉₂
₄₄₀︐₅₄₁₄₄₆︐₈₇₇
₄₂₈︐₆₅₃
₄₃₀︐₃₄₃

₄₀︐₂₃₅₄₀︐₃₈₄₃₃︐₀₅₄₃₆︐₉₁₂
₄₉︐₆₆₄₄₅︐₀₄₆
₇₄︐₅₇₂
₁₀₇︐₁₅₄
₁₄₇︐₉₀₂

₁．₀₉₄
₁．₀₉₃
₁．₀₈₈
₁．₀₈₃
₁．₁₄₁
₁．₁₀₂
₁．₁₆₇
₁．₂₅₀
₁．₃₄₄

₁₂︐₇₂₃
₁₃︐₃₀₅
₁₉︐₃₈₅₂₂︐₃₅₄
₁₆︐₆₃₃
₂₂︐₁₀₆
₁₇︐₀₂₀₃₂︐₇₆₂
₂₃︐₄₈₆

₁₁
₁₁
₁₂
₁₃
₈
₁₀
₆
₅
₃

₁︐₁₅₇
₁︐₂₁₀
₁︐₆₁₆
₁︐₇₂₀
₂︐₀₈₀
₂︐₂₁₁
₂︐₈₃₇
₆︐₅₅₃
₇︐₈₂₉

₃₃
₁₄
₉
₄₄
₃₈
₂₇
₃₇
₁₇
₂₄
₁₃

岡山県
神奈川県
栃木県
大分県
愛媛県
大阪府
香川県
石川県
三重県
東京都

₁︐₉₂₂︐₁₈₁
₅
₉︐₁₂₇︐₃₂₃ ₂₀
₅₁︐₉₇₄︐₆₇₁
₁︐₁₆₆︐₇₂₉
₃
₁︐₃₈₅︐₈₄₀
₃
₈︐₈₃₈︐₉₀₈ ₂₀
₉₇₆︐₇₅₆
₂
₁︐₁₅₄︐₃₄₃
₃
₁︐₈₁₅︐₈₂₇
₄
₁₃︐₅₁₃︐₇₃₄ ₃₀

₄₇₇︐₄₃₅
₅₁₆︐₉₅₁
₅₁₈︐₇₆₁₄₇₈︐₃₃₅
₅₁₅︐₀₉₂
₅₀₂︐₆₀₅
₅₆₂︐₀₀₁
₄₆₅︐₈₁₀₅₉₄︐₃₆₄
₅₇₆︐₅₂₆

₃₅₂︐₈₈₅
₄₀₁︐₂₇₂
₃₅₁︐₃₇₂
₃₄₄︐₀₄₁
₃₈₉︐₈₂₅
₃₇₅︐₁₉₇₄₁₄︐₇₅₅
₂₉₄︐₆₅₆
₃₆₁︐₈₃₅
₃₄₁︐₆₉₁

₁₂₄︐₅₅₀
₁₁₅︐₆₇₉
₁₆₇︐₃₈₉
₁₃₄︐₂₉₄
₁₂₅︐₂₆₇
₁₂₇︐₄₀₈
₁₄₇︐₂₄₆
₁₇₁︐₁₅₄
₂₃₂︐₅₂₉
₂₃₄︐₈₃₅

₁．₃₅₃
₁．₂₈₈
₁．₄₇₆
₁．₃₉₀
₁．₃₂₁
₁．₃₄₀
₁．₃₅₅
₁．₅₈₁
₁．₆₄₃
₁．₆₈₇

₃₁︐₅₅₀₅₅︐₀₉₄₄₃︐₅₆₁
₄₄︐₈₆₈₇₂︐₁₂₁
₆₆︐₇₄₈₇₃︐₆₂₂₉₀︐₁₂₄
₉₂︐₁₂₁
₁₀₈︐₇₆₆

₃
₄
₃
₃
₄
₃
₃
₂
₂
₂

₁₀︐₅₁₇
₁₃︐₇₇₄
₁₄︐₅₂₁
₁₄︐₉₅₇
₁₈︐₀₃₁
₂₂︐₂₅₀₂₄︐₅₄₁₄₅︐₀₆₃₄₆︐₀₆₁
₅₄︐₃₈₄

d＊

24

r＊

X

Y

X/Y +₁

Journal of Public and Private Management
Vol. 5, No. 6, March 2019, pp. 1-24
ISSN 2189-2490

How to solve the electoral districting problem
Keisuke Hotta
Faculty of Business Administration, Bunkyo University
khotta@shonan.bunkyo.ac.jp
Recieved：31 January 2019
Accepted：31 January 2019

Abstract
In order to implement the election of the constituency system, the electoral district must be
deﬁned. It is generally a combinatorial optimization problem to construct an appropriate electoral
district based on the guidelines of the country such as constitutional law and law. In Japan, the gapof one vote in the electoral section often becomes a problem, and in order to evaluate based on thisindex, it is necessary to obtain an optimal solution that gives a limit value, not an approximate
solution. However, in some cases, it is very diﬃcult to obtain the optimal solution for this problem.
This paper summarizes the details about the way to obtain the optimal solution established by
Nemoto and Hotta［38, 39］. In particular the method to get the solution of the minimum ratio easily
and its computational complexity analysis are indicated.

Keywords：apportionment problem, electoral redistricting problem, the maximum disparity among
values of votes in diﬀerent constituencies, optimization for the minimum ratio, complexity, 0-1 mixed integer programming, graph partitioning, connected component
decomposition

Faculty of Business Administration, Bunkyo University
1100 Namegaya, Chigasaki, Kanagawa 253-8550, JAPANTel +81-467-53-2111, Fax +81-467-54-3734
http://www.bunkyo.ac.jp/faculty/business/

経営論集

Vol.5, No.6

ISSN 2189-2490
2019年３月29日発行
発行者

文教大学経営学部

石塚

浩

編集

文教大学経営学部

研究推進委員会

編集長

鈴木誠〒253-8550 神奈川県茅ヶ崎市行谷1100
TEL：0467-53-2111

FAX：0467-54-3734

http://www.bunkyo.ac.jp/faculty/business/