福井大学 学術研究院工学系部門 研究報告 第 70 巻 2021 年 10 月
Mem. Fac. Eng., Univ. Fukui, Vol. 70（ October 2021 ）15

安定マッチングとそのいくつかの拡張問題の混合整数計画による定式化について
鈴川

欣秀 ∗

小原

敦美 †

On Formulation of Stable Matching Problems into Mixed Integer Program
Yoshihide SUZUKAWA∗

Atsumi OHARA†(Received September 20, 2021)
We show several techniques to formulate fundamental stable matching problems and their variants into mathematical program called mixed integer program (MIP). One-to-one or many-to-one
stable matching problems have practically wide applications for mechanism designs in economics
or in the real world. Recently MIP has emerged to be a powerful and cheap tool to solve many
optimization problems including large-scale combinatorial ones. We demonstrate how to apply MIP
to ﬁnd satisfactory solutions, and results of numerical experiments to know current status of its
computational ability.
Key words : Stable matching problems, Mixed integer program, Optimization of stability criterion,
Blocking pairs, Stable marriage

1.

緒言

デザイン（制度設計）へ応用も広がっている [3]–[7] ∗ ．
一方，近年の計算機の性能/価格比の著しい向上に加マッチング問題とは，結婚における男女，研究室配えて，混合整数計画（Mixed Integer Program: MIP）† ア

属における学生と研究室，就職活動における学生と企

ルゴリズムのめざましい進歩と種々の汎用ソルバーへ

業のように，異なる集合に属し個々の選好をもつ主体の実装・整備が整うにつれ，大規模な MIP の問題が手同士を関係づける際，最も望ましい組み合わせを求め軽に試せるようになってきている [8], [9] ．また「安定性」

る問題である．ここで「望ましい」とは，例えば研究については次節で紹介するが，安定なマッチングは所与室配属の場合，学生は志望研究室の順位・満足度などの問題に対して，存在しても唯一とは限らない [1], [5], [7] ．

にそれぞれの選好があり，研究室側も GPA や専門科目

従って，標準的な安定マッチング問題を MIP へ定式の評価など学生に対する個々の選好がある中で，マッ化しておけば，様々な応用で解きたい個々の問題におチングの結果が双方に不満を残さないことである．

いて考慮すべき固有な条件を，MIP の柔軟な記述力をこの意味で望ましいマッチングの解が満たすべき最活かして表現し書き加えることで，標準的な定式化をも基本的な条件として「安定性」という概念が提唱さ

カスタマイズできる．これにより，個々の問題に合われ，安定なマッチングを求めるアルゴリズムが考案させたアルゴリズムを一から新たに考案せずに，固有のれた [1] ．以来，安定マッチングの理論は離散数学，計安定マッチング解を探索することが可能となる．

算機科学，数理経済学の分野で様々な問題への拡張，安さらに，安定性は最適化問題においては制約条件と定解の存在性と構造，計算複雑度，離散凸解析との関して表せる概念なので，解きたいマッチング問題に合係などが研究され，実社会・経済などではメカニズム

わせた目的関数を設定できれば，その意味で最適な安定マッチングを見いだすことも可能となる．

∗（株）アイシンAISIN Corporation† 電気・電子工学講座† Department of Electrical and Electronics Engineering∗∗ 文献 [1] の著者 Shapley 氏は安定マッチング理論が関わる「安定配分理論と市場設計の実践に関する功績」で 2012 年度のノーベル経済学賞を受賞している（Gale 氏は当時すでに他界）．
† 本報告では，純粋な整数計画（IP）も含んだ意味で用いる．

16

本稿の内容は，学術的な研究というより，上記の状況

チング µ に対する満足度は当然低くなる．したがって，に促されて便利なツールを使うために取り組んで得た不安定なマッチングは，ブロッキングペアがマッチン「ある種の工夫・ノウハウ」の説明の類いである．従っ

グ成立後にペアを組みなおした場合，マッチングが崩て学術論文として公表される性格のものでないためか，

壊してしまう．

‡

同様な内容の先行報告は我々には見つけられなかった ．

結婚問題には「安定マッチングは必ず存在するが，一また，もしマッチング問題に携わる機会・業務があっ般に唯一ではない」ことが知られ [1], [5], [7] ，文献 [1] でたとき，自動化が容易で負担が軽減し，理論的な公平提案されたアルゴリズムで安定マッチングが得られる．

性の担保にも役立つため，知っておくと便利な「豆知本報告では考案者の頭文字をとって GS アルゴリズム§

識」という意味もあろうと考え ，ここに報告する．

（詳細は省略．例えば文献 [1], [5], [7] 参照）と呼ぶ．

第 2 節は，安定マッチングと MIP に関する準備であ

しかし，「GS アルゴリズムで得られる解は，男性側，る．第 3 節で，標準的な安定マッチング問題の MIP へ

女性側どちらか一方の満足度が最適になるような特殊の定式化を考察する．安定性を制約条件とするために，な安定マッチングである」ことも知られている [5], [7] ．

不安定性の定義の否定を考え，MIP で離接条件（OR の条件）が表現可能なことを用いる．第 4 節で，この定式化をもとにいくつかの拡張もしくは変形されたマッチング問題を MIP で表している．これらの問題は，新しく提案したもの，最適性を追求したもの，NP 困難と（不）等
さて，MIP は下記のように線形な目的関数，
式制約をもつ最適化問題のクラスである：{
A1 x ≤ b 1 ,minimize cT x, subject toA 2 x = b2 .

(1)

されるものがある．NP 困難な問題の結果は，現時点のここで，x は成分の一部を整数に限定した実変数ベク

ごく普通の計算環境でどれほどのことが可能かの目安

トルで，Ai , bi (i = 1, 2), c は上の等式・不等式を満たにもなると思われる．第 5 節は，パソコンでの計算機

す適当なサイズの与えられた実定数の行列またはベク

実験で，第 6 節でまとめている．

トルである．ただし，ベクトルの不等号 a ≤ b は，第なお，本報告は主に文献[12]に基づいている．

i 成分同士が ai ≤ bi , ∀i を満たすことを表す．

以後，本報告では特に変数ベクトルのすべての成分

2.

準備：安定なマッチングと混合整数計画（MIP）

が 0 か 1 の値に限定されたバイナリ変数のみを考える．

3.

標準的な安定マッチング問題の MIP への定式化

される概念を説明する．n 人ずつの男女の集合 M =3.1

１対１のマッチング：安定結婚問題

員に対する選好の順位・満足度を持つとする（選好度た安定結婚を取り上げる．実定数 cij , gij をそれぞれ男は同順位・同点はなしとする）．男性 mi が女性 wj を

性 mi の女性 wj への満足度，女性 wj の男性 mi への

女性 wk より選好するとき，次のように書く：

満足度とする（順位なら符号反転など前処理）．マッチ

簡単な安定マッチング問題として，1 対 1 で全員を誰かとマッチさせる結婚問題を例に，問題設定や導入{m1 , · · · , mn } と W = {w1 , · · · , wn } の各人が異性全

ング µ において mi と wj がマッチしている，いないと

w j ≻mi w k

き，バイナリ変数 xij の値をそれぞれ 1，0 とする．以M と W の 1 対 1 マッチング µ で mi と wj がマッチしていることを µ(mi ) = wj や µ(wj ) = mi と表す．

定義 1. マッチング µ において，以下の 2 条件を満たすペア (mi , wj ) は µ のブロッキングペアであるという．
ブロッキングペアが存在しないマッチングを安定マッ
チングと呼ぶ．

i) wj ≻mi µ(mi ),標準的な安定マッチング問題として，前節で説明し

下，mi , wj の添え字の集合も M, W と表すと，µ で全員が１人にマッチしている条件は次の通り：
n
∑

i=1
n
∑

xij = 1,∀j ∈ W := {1, ..., n},(2)xij = 1,∀i ∈ M := {1, ..., n}

(3)

j=1

ii) mi ≻wj µ(wj )すなわちブロッキングペアは，それぞれが µ でマッチしている相手に比べより選好しあうので，このマッ

これらの条件の下で，(mI , wJ ) ∈ M × W がブロッキ

ングペアであることは次と同値になる：

cIJ >‡ MIP に定式化している興味深い文献はあった [10], [11] が，本報告で考える意味の安定性は扱われていない．

§ 実は，筆者の一人が学科の卒研配属を担当したことが，本報告の内容を考えてみるきっかけであった．

n
∑
j=1

cIj xIj and gIJ >n∑

giJ xiJ

i=1

よって，この同値関係の否定を考えると以下のように
なる．

17

補題 1. マッチング µ が安定であることは式 (2), (3) のn∑j=1

cIj xIj or gIJ ≤n∑

多対１のマッチング：卒研配属問題

次に多対 1 の安定マッチングの標準的な問題として，

もとで以下が成立することと同値である：

cIJ ≤

3.2

(4)

giJ xiJ ,i=1

卒研配属問題（専門用語では研修医配属問題と呼ばれ・・,sn }る）を考えよう．学生 n 人の集合 S = {s1 ,s2 ,・と研究室 m 個の集合 L = {L1 ,L2 ,・・・,Lm } がある状況∀ (I, J) ∈ M × W

を考える．以下，ss , Ll の添え字 s, l だけ用いる．

MIP では十分大きな正定数 M （big-M）と一つのバ

バイナリ変数 xsl を用いて，学生 s が研究室 l に配属

イナリ変数 yIJ で，式 (4) のような離接 (or) 条件を次される場合 xsl = 1，そうでない時 xsl = 0 とする．各のような合接 (and) 条件として表せる：

研究室の定員上限 (Upper Bound) を U Bl とし，学生 s∃yIJ ∈ {0, 1},

cIJ ≤

gIJ ≤

n
∑

cIj xIj + M yIJ

j=1

n
∑
i=1

giJ xiJ + M (1 − yIJ )M は，例えばこの問題では ∀(I, J) ∈ M × W に対して


m
n


∑
∑
M ≥ max cIJ −cIj xIj , gIJ −giJ xiJ
i=1¶を満たせばよい ．以下にまとめる．

定理 1. α, β を重みを表す正定数とする．男女の重み付
き満足度の和を最大化する安定結婚問題は，バイナリ
変数 xij , yij に関する次の MIP に定式化される：

maximize α
s.t.

n ∑
n
∑

cij xij + β

i=1 j=1n∑xij = 1,i=1n∑xij = 1,

j=1

cIJ ≤
gIJ ≤

n
∑

n ∑
n
∑

i=1

定義 2. 多対１マッチング µ において，以下の 2 条件を満たすペア (s, l) ∈ S × L は µ のブロッキングペア
である．

(i) s は µ でどこにも配属されていないか，またはl ≻s µ(s)(ii) µ で l に配属された学生数は定員未満か∥ ，またはl に配属された学生の中に l にとっての満足度が s
より低い学生がいる
すべての学生が研究室に配属され，定員も満たすことを表す条件m∑

gij xij

i=1 j=1l=1n∑∀j ∈ W,

s=1

cIj xIj + M yIJ ,∀s ∈ S,xsl = 1,xsl ≤ U Bl ,∀l ∈ Lの下で，(S, L) がブロッキングペアであることは次と∀i ∈ M,

j=1n∑

学生 s を迎え入れた場合の満足度を gsl とする．他の記
号の使い方は結婚問題と同様である．

and

j=1

の研究室 l に配属した場合の満足度を csl ，研究室 l の










giJ xiJ + M (1 − yIJ ), ∀(I, J) ∈ M × W,

xij , yij ∈ {0, 1}, (i, j) ∈ M × W
M : 十分大きな正の定数

同値：

cSL >

m
∑

cSl xSl

l=1

and
n
∑
s=1

xsL < U BL or ( gSL xsL > gsL xsL , ∃s ∈ S )この同値関係の否定をとり，結婚問題と同様に離接条件を処理すると次の結果を得る：

注：特に α と β のどちらかのみを 0 としたとき得られる

定理 2. 学生と研究室の満足度の和を最大化する安定

解が女性最適，男性最適の安定マッチングであり，GS

な卒研配属問題は，バイナリ変数 xsl , ysl に関する次のアルゴリズムの解と一致する．数値実験では，重みを調整することでその他の安定マッチングが（存在すれば）得られることが多かった．

MIP に定式化される：
maximizemn ∑∑s=1 l=1
n
∑

s.t.

s=1

¶ あまり大きすぎると，数値実験では計算時間が長くなる傾向が見られた．

csl xsl +mn ∑∑gsl xsl

s=1 l=1

xsl ≤ U Bl , ∀l ∈ L,

∥ この条件は不要な場合もあろう．

18
m
∑

cSL ≤

l=1
m
∑
l=1

ある男性 mi のリストに女性 wj が書かれているとき,

xsl = 1, ∀s ∈ S,
cSl xSl + M (1 − ySL ),mi は wj を受け入れ可能という. SMI のマッチングは，









互いに受け入れ可能なペアを要素とする集合のうち誰も２人以上とマッチしていないものである．これに応じて SMI ではブロッキングペアを次のように定義する．

gSL xsL ≤ gsL xsL + M ySL , ∀s ∈ S,

n

∑




xsL + M ySL ,U BL ≤


定義 3. 互いに受け入れ可能な男女ペア (mi , wj ) すべてを要素とする集合を A と記す．SMI マッチング µ に

s=1∀(S, L) ∈ S × L

おいて以下の２条件を満たすペア (mi , wj ) ∈ A が µ の4. 拡張されたいくつかのマッチング問題と定式化
4.1

下限つき卒研配属問題でのブロッキングペア最小化

3.2 節の卒研配属問題では，定員に上限がある場合はブロッキングペアである∗∗ ．

(i) mi は µ で独身か，または wj ≻mi µ(mi )(ii) wj は µ で独身か，または mi ≻wj µ(wj )安定マッチングが必ず存在し，GS アルゴリズムで求解

前節と同様，添え字のみ記す．上の定義より，互いできる．しかし，下限がある場合は安定マッチングはに受け入れ可能な男性 I と女性 J のペア (I, J) ∈ A が存在するとは限らないことが知られている [7] ．その場
合，ブロッキングペア (BP) の数が最小のマッチングを選ぶことは一つの妥当な策であろう．これには定理 2で，満足度の最大化を捨て，ブロッキングペア数を検出するバイナリ変数 zsl を追加し最小化すればよい．
系 1. 研究室配属数に下限 LBl がある場合にブロッキ
ングペア数を最小化する卒研配属問題は，バイナリ変数 xsl , ysl , zsl に関する次の MIP に定式化される：

minimizemn ∑∑s.t. LBl ≤
m
∑
l=1

cSL ≤

m
∑
l=1

s=1

ングの条件（補題 2 の式 (5), (6)）の下で
m∑xIj = 0n∑xiJ = 0j=1

m∑

cIj xIjn∑

giJ xiJ

j=1

and
or

gIJ >

i=1

i=1

とは，式 (5), (6) の下で ∀(I, J) ∈ A に対して

xsl ≤ U Bl , ∀l ∈ L,m∑

xIj ̸= 0n∑xiJ ̸= 0

j=1

xsl = 1, ∀s ∈ S,









gSL xsL ≤ gsL xsL + M ySL + M zSL , ∀s ∈ S,

n

∑




xsL + M ySL + M zSL ,U BL ≤

s=1∀(S, L) ∈ S × L

i=1

リストに書かなくて良いという不完全リストを考える．
リストにない相手とペアになるより独身を好むことを意味する．これを SMI(Stable Marriage with Incomplete

lists) と書く．独身も考慮するので男女の集合 M, W は同人数である必要はなく，それぞれの人数を n, m と

cIJ ≤

m
∑

cIj xIj

and

gIJ ≤

n
∑

giJ xiJ

j=1

i=1となる．従って，SMI 問題は次のように書ける．
補題 2. マッチした男女の満足度を最大化する SMI 問
題は，バイナリ変数 si , tj , xij , yij に関する MIP で以下のように定式化される：

4.2 不完全リスト結婚問題と最大サイズ最小 BP 問題
安定結婚問題で，ペアになりたくない相手は満足度

andormaximize

する．

cIJ >

である．この否定から SMI マッチングが安定であるこzSLcSl xSl + M (1 − ySL ) + M zSL ,or

xij ∈ {0, 1}, (i, j) ∈ M × W

S=1 L=1n∑

SMI のブロッキングペアであることは，1 対 1 マッチ

s.t.

n ∑
m
∑

cij xij +i=1 j=1n∑xij = ti ,j=1

xI ′ J ′ = 0,

gij xij

i=1 j=1

xij = sj ,

i=1
m
∑

n ∑
m
∑

∀j ∈ W,∀i ∈ M,(5)(6)∀(I ′ , J ′ ) ̸∈ A,∗∗ µ(m ) ̸= w かつ (m , w ) ∈ A の条件 [7] は，仮定と i), ii) か
i
j
i
j
ら従う．

19

0.5 ≤
cIJ ≤

m
∑

xIj + M yIJ ,

j=1
m
∑

cIj xIj + M yIJ ,

j=1
n
∑

























i=1


n

∑


gIJ ≤
giJ xiJ + M (1 − yIJ ), 


0.5 ≤

xiJ + M (1 − yIJ ),i=1∀(I, J) ∈ A「SMI の安定マッチングは必ず存在し，GS アルゴリ
ズムで求められる」や「すべての安定マッチングのサイズ（成立しているペアの数）は等しい」ことが知られている[5], [7]．

安定とは限らない SMI マッチング（つまり，A の部

分集合で 1 対 1 のマッチング）の中で最大サイズのマッ

n ∑
m
∑

xij = Smax ,i=1 j=1

xI ′ J ′ = 0, ∀(I ′ , J ′ ) ̸∈ A,
m
∑
0.5 ≤
xIj + M yIJ + M zIJ ,
j=1

cIJ ≤

m
∑

cIj xIj + M yIJ + M zIJ ,

j=1
n
∑

























i=1


n

∑


gIJ ≤
giJ xiJ + M (1 − yIJ ) + M zIJ , 


0.5 ≤

xiJ + M (1 − yIJ ) + M zIJ ,i=1∀(I, J) ∈ A

4.3 安定ルームメイト問題
2n 人の寮生 P = {p1 , p2 , · · · , p2n } と n 室の 2 人部

チングを考える（これも一般に複数ある）．もしこの最屋があり，各寮生 pi は自分以外の学生 pj に対する選大サイズが安定マッチングのサイズより十分に大きい

好満足度 cij , (i ̸= j) を持っているとする．

場合，安定性を多少犠牲にして「最大サイズマッチン

安定ルームメイト問題は，この選好リストから次のグの中でブロッキングペア（BP）の数が最小な」マッように定義されるブロッキングペアが存在しない，完チングを求めることは意味がある（かもしれない†† ）．

全な（すべての寮生が誰かとペアになっている）マッ

Biró らはこのような問題を最大サイズ最小 BP 問題とチング µ を求める問題である．

して提案し，それが NP 困難であることを示した [13] ．

定義 4. 異なる 2 者からなるペアすべてを要素とする集この問題は，二段階に分けて MIP で定式化できる．
まず SMI マッチングの最大サイズは si , tj , xij をバイ
ナリ変数として次のように求められる：

maximize

n ∑
m
∑

s.t.

j=1
m
∑

ii) pi ≻pj µ(pj )この定義は，定義 1 で男女の区別を略したものである．したがって，安定ルームメイト問題は 3.1 節の安∀j ∈ W,

定結婚問題を特別ケースとして含む，あるいは，安定′

結婚問題は無向 2 部グラフ上での安定マッチング問題

xij = tj ,i=1′∀(I , J ) ̸∈ A

xI ′ J ′ = 0,の 2 条件を満たすペア (pi , pj ) ∈ E は µ のブロッキンi) pj ≻pi µ(pi ),∀i ∈ M,

xij = si ,す．完全なルームメイトマッチング µ において，以下
グペアであるという．

xij

i=1 j=1m∑

合を E = {(pi , pj )|1 ≤ i < j ≤ 2n, i, j : 自然数 } と記

求まった最大値を Smax とすると，補題 2 を利用して次の結果を得られる．

ととらえられるが，安定ルームメイト問題は一般の無向グラフ上での安定マッチング問題と考えられる．
ルームメイト問題も「安定マッチングが存在すると定理 3. SMI 最大サイズ最小 BP 問題は，バイナリ変数

は限らない」[7] ．そこで，4.1 節，4.2 節と同様にブロッ

si , tj , xij , yij , zij に関する MIP で以下のように定式化

キングペア (BP) の数を安定度の一つと見なして最小化

される：

することが次善策の一つとして浮かぶ．ただし，このminimize

m
n ∑
∑

zIJ

I=1 J=1

s.t.

n
∑

i=1
m
∑

xij = sj ,xij = ti ,j=1

∀j ∈ W,∀i ∈ M,†† 例えばマッチメーカーの商業的理由などで．

問題も NP 困難であることが知られている [7], [14] ので，
計算機実験してみる価値がある．

2 部グラフにならない点のみに注意して，前節までの方法を踏襲すると次の結果は明らかであろう．
定理 4. 最小 BP 安定ルームメイト問題は，バイナリ変数 xij , yij , zij に関する MIP で以下のように定式化で20記述できる．

きる：

minimize∑zIJ

dst xsl xtl =(I,J)∈E

s.t. xij = xji ,∀(i, j) ∈ E,

xii = 0, ∀i ∈ P,
2n∑
xij = 1, ∀j ∈ P,
i=1

cIJ ≤
cJI ≤

2n
∑
j=1
2n
∑
j=1

cIj xIj + M yIJ + M zIJ ,0otherwise(x and y) は線形等式・不等式で以下のように表せる：







∀(I, J) ∈ E,

(i, j) ∈ P × P,

yij , zij ∈ {0, 1},

xsl = xtl = 1 のとき

これは論理積の and の関係に他ならない．論理積 z =cJj xJj + M (1 − yIJ ) + M zIJ , xij ∈ {0, 1},


dst

x+y
≥ z ≥ x + y − 1,2

これを用いて，式 (7) の項を書き換えると次のように

MIP にできる．
定理 5. 学生と研究室の満足度及び各研究室内での友好度の和を最大化する安定な卒研配属問題は，バイナリ
変数 xsl , ysl , zstl に関する次の MIP に定式化できる：

maximize(i, j) ∈ E

x, y, z ∈ {0, 1}

m
n ∑
∑

csl xsl +s=1 l=1

+

m
n ∑
∑

gsl xsl

s=1 l=1
n ∑
m ∑
n
∑

dst zstl

l=1 s=1 t=1

4.4

学生の相互関係を考慮した卒研配属

s.t.

この節では，3.2 節で考えた定員上限つき卒研配属問

s=1
m
∑

題の拡張として，学生と研究室の間の満足度だけでなく，同一研究室に配属される学生の選好（友好度）も考慮した問題を提案しその MIP 定式化を示す．
例えば，研究チームやスポーツチームの構成員が協力し合いながら活動・プレーする場合，構成員間の友好度が高ければ，成績の向上も期待できるという点で構成員のみならずチーム側にとってもメリットがある．
このマッチング問題は，そのような状況で考える意味があると思われる．
ブロッキングペアの定義など 3.2 節の設定はすべて同じとし，これらに加えて各学生 ss の自分以外の全ての学生 st それぞれへの友好度 dst , (s ̸= t), s, t ∈ S を

実定数データと考える．ただし，一般に dst ̸= dts で，

dss = 0 とする．

すると最適化問題の定式化は，定理 2 と比べて，制約条件 (subject to の部分) は同じだが，目的関数には新
しい項，すなわち一つの研究室 l 内での学生友好度を
研究室毎にとった和
n
n ∑
m ∑
∑

dst xsl xtl

n
∑

cSL ≤

l=1
m
∑
l=1

xsl ≤ U Bl , ∀l ∈ L,

xsl = 1, ∀s ∈ S,

cSl xSl + M (1 − ySL ),










gSL xsL ≤ gsL xsL + M ySL , ∀s ∈ S,

n

∑




xsL + M ySL ,U BL ≤

s=1∀(S, L) ∈ S × L,
xsl + xtl
≥ zstl ≥ xsl + xtl − 1,2∀(s, t, l) ∈ S × S × L

5. 数値実験
数 値 実 験 で は ，MIP ソ ル バ ー と し て 非 商 用 のSCIP(Solving Constraint Integer Programs)[15] を用いた．
また，数値解析ソフトウェア (インターフェース) は mat-labR2014b[16] ，コンピューターは Intel(R)Core(TM) i54440(3.10GHz)8GB メモリを用いた．SCIP は非商用ソ(7)l=1 s=1 t=1が加わることになる．
ところが，この項はバイナリ変数 xsl に対し二次なので，このままでは MIP（線形計画）でない．幸い，変数がバイナリであるので式 (7) の各項は以下のようにルバーの中では高速であり，いくつかの商用ソルバー
よりも性能が良いことが知られている.
多くの MIP ソルバーは分枝限定法が動作するので，
仮に最適解が実行時間内に求まらなくても得られている解 (暫定解) には精度保証があり，現実的な計算時間で十分な精度の解が得られることが多い．
数値実験は，入力データとしての満足度や友好度を乱数で生成した例題を 100 題解き，最適解を得るまでの平均実行時間などを調べた．

21

5.1

研究室配属問題解法にも関わらず平均時間のみに着目するともう少し研究室配属問題について，3.2 節の定員数上限のみの標準的な問題と 4.1 節の定員数上下限つき最小 BP のそ
れぞれの MIP での最適化実験結果を示す．

規模の大きい問題でも，現実的時間の範囲でなんとかなりそうである．
ただしその他の評価項目を比較すると，最大サイズ
最小 BP 問題を考える意義のある状況が発生するには，

表 1 ：標準的な定員上限のみ研究室配属問題

入力データに何らかの偏りが必要ではないかと推測される．

学生, 研究室 [人:室] ＼時間 [s]

平均実行時間最大実行時間最小実行時間

10:5

0.380

0.446

0.331

20:5

0.499

0.608

0.365

30:10

1.403

2.178

1.056

40:10

4.900

6.189

3.624

また参考のため，3.1 節で述べた標準的な安定結婚問
題の計算実行時間を以下に示す．
表 5 ：標準的な安定結婚問題
10:10 20:20 50:50

男性, 女性 [人:人]平均実行時間 [s]

表 2 ：定員上下限付き最小 BP
学生, 研究室 [人:室] ＼時間 [s]

平均実行時間最大実行時間最小実行時間

10:5

1.04

1.846

0.902

20:5

2.188

7.049

1.006

30:10

122.745

3430.863

4.421

40:10

431.8293300.819

7.509

0.76

1.62

80:80

9.92

23.65

興味深いことは，表 3 と比較できる 10:10 と 20:20の 2 ケースでしかないが，SMI 問題の方が標準的安定
結婚問題より平均時間が短いことである．両問題では，

SMI の方が変数の数はやや多いが，それ以上に制約条件が増えるので，ソルバーの分枝限定法がより効果的

定員上限のみはより大規模な問題でも扱えそうであに働くからではないかという仮説が立つ．

る．これに比較し定員数上下限つきの BP 最小化は大幅に時間がかかっており，下の 5.4 節の結果も勘案す
ると変数が増えていること以上に難しい問題であることがわかる．例題により実行時間のばらつきが大きい．

5.3

最小 BP 安定ルームメイト問題

4.3 節で述べた最小 BP 安定ルームメイト問題の MIP
での最適化実験結果を示す．

5.2 SMI 問題と最大サイズ最小 BP 問題

表 6 ：最小 BP 安定ルームメイト問題
人数 [人]
1020
30

4.2 節で述べた不完全リスト安定結婚 (SMI) 問題と最
大サイズ最小 BP 問題それぞれの MIP での最適化実験

平均実行時間 [s]0.594

11.3271750.006

結果を示す．
表 3 ：不完全リストを許す安定結婚 (SMI) 問題

最小 BP 安定ルームメイト問題では標準的安定結婚

平均値＼男性, 女性 [人:人]

10:10

20:20

30:30

問題（表 5）に比べ，変数の数が増えることに加えて平均実行時間 [s]

0.546

0.655

0.790

男女の区別が無いことから組み合わせの数も増大する．

一人あたりの平均満足度

27.06256.08086.354

安定マッチングの平均サイズ

7.72

17.89

28.05

計算機実験では，NP 困難問題らしく，問題スケールの

平均ブロッキングペア数

0

0

0

増加につれて求解時間が急激に大きくなった．40 人の問題については，30000[s]～62000[s] 程度かかった．

5.4

4.4 節で述べたこの問題の数値実験結果を示す．

表 4 ：最大サイズ最小 BP 問題
平均値＼男性, 女性 [人:人]

10:10

学生の相互関係を考慮した卒研配属問題

20:20

30:30

平均実行時間 [s]

1.023

2.961

280.870

一人あたりの平均満足度

24.67351.74382.638

最大サイズマッチングの平均サイズ

8.85

19.86

30.00

平均ブロッキングペア数

1.36

2.74

1.85

SMI 問題の方はより大規模な問題も扱えそうである．
最大サイズ最小 BP 問題は NP 困難ではあるが，二段階

表 7 ：相互関係を考慮した研究室配属問題
学生, 研究室 [人, 室] ＼時間 [s]

平均実行時間最大実行時間最小実行時間

10,5

0.477

0.968

0.347

20,5

0.799

1.188

0.612

30,10

1.769

2.917

1.312

50,10

6.181

12.5203.649

22

相互関係（友好度）を考えない標準的な多対１の結果である表 1 と比べやや時間が長くなった程度で，論理積を表すために新しく導入した変数による負荷はさほどではないようである．

6.

結言[3] 田村 明久：離散凸解析とゲーム理論，朝倉書店(2009).
[4] 田村 明久：オペレーションズ・リサーチ, 58-6,
325-331 (2013).
[5] 安田 洋祐:：数学セミナー, 52-4, 40-45 (2013).

本稿では，いくつかの安定マッチング問題の MIP への定式化例と計算機実験結果を示した．これらは，変[6] 岩崎 敦：オペレーションズ・リサーチ, 60-6, 323329 (2015).

数の数を削減したり，big-M の値の調整などで改善の[7] 宮崎 修一：安定マッチングの数理とアルゴリズ

余地は多分にあろう．安定マッチングが存在するとは

ム～トラブルのない配属を求めて～, 現代数学社

限らない発展問題に対しては，ブロッキングペアの数(2018).

が安定度の指標の一つと見なせることから，この指標最小化も考察した．また，配属者の相互関係も考慮したマッチングにも取り組んだ．
本報告では省略したが，定員下限つき研究室配属問題に対処するため安定性を緩和した「無駄のないマッ
チング」，「フェアなマッチング」という概念も提案されており，無駄がなくフェアなマッチングが安定マッチ
ングと対応する [17] ．これらの概念も，MIP に定式化できる．

[8] 宮代 隆平：http://web.tuat.ac.jp/ miya/ipmemo.html(2021/9).
[9] 梅谷 俊治：自然言語処理, 21-5, 1059-1090 (2014).
[10] 今野 浩：数理決定法入門 キャンパスの OR，朝倉書店 (1992).

[11] 堀田 敬介：文教大学経営論集, 2-1, 1-18 (2016).

一方，マッチングアルゴリズムで重要な「耐戦略性」[12] 鈴川 欣秀：整数計画を用いた不安定マッチングの定式化については，本報告では考察していない．マッの安定度最大化とその評価，福井大学大学院 工チングアルゴリズムが耐戦略性を持つとは，他の主体

学研究科がどうするかに関わらず，各主体は選好順位・満足度
リストで嘘をついても利のないことを指す.

GS アルゴリズムは，それが適用可能な問題に対しては二つの集合のどちらか，すなわち結婚問題なら男性側あるいは女性側のみに対戦略性を持たせることができる [7] ．また，定員下限つき多対１マッチング問題でやや緩和した意味の安定性と耐戦略性をもつアルゴリ
ズムが提案されている

[18]

．

MIP は様々な最適化問題のプラットフォームなので，計算機の方式が変化してもその汎用ソルバーとしての性能は今後しばらく上昇すると予想され，より規模の大きい問題の解決が期待できる．耐戦略性が MIP に定式化できるかは今後の課題としたい．

電気電子工学専攻

修士論文 (2021).

[13] P. Biró, D. F. Manlove and S. Mittal: Proc. WAOA,
LNCS 5426, 15-28 (2008). (Full version: Technical Report TR-2008-283, University of Glasgow, Department of Computing Science (2008).)[14] D. J. Abraham , P. Biró and D. F. Manlove: Proc.
WAOA, LNCS 3879, 1-14 (2005).
[15] https://www.scipopt.org/ (2021/9).
[16] https://jp.mathworks.com/ (2021/9).
[17] 横尾 真：日本ソフトウェア科学会第 30 回大会講演論文集，493-500 (2013).

[18] 鎌田，小島，和光：医療経済研究, 23-1, 5-20 (2011).
参考文献[1] D. Gale and L.S. Shapley: American Mathematical
Monthly, 69, 9-15 (1962).
[2] D. Gusﬁeld and R.W. Irving: The Stable Marriage Problem: Structure and Algorithms, MIT Press(1989).