代数的組合せ最適化

代数的組合せ最適化

Edmonds 問題の最近の発展について

平井広志

東京大学 大学院情報理工学系研究科 数理情報学専攻

[email protected]

組合せ最適化セミナー 京都大学数理解析研究所

２０１９年８月７日

組合せ最適化の発展

• 1960 年代 : J. Edmonds --- 多項式時間アルゴリズム，

最大最小定理，良い特徴付け，多面体的方法，

マトロイド，劣モジュラ関数， ...

• 1970 年代 : P と NP

• 1980 年代 : Grotschel-Lovasz-Schrijver

⋮

A.Schrijver: Combinatorial Optimization---Polyhedra and Efficiency, 2003.

---- 多面体的方法による組合せ最適化の集大成

今回のセミナー：

多面体的方法とは異なる代数的視点からのアプローチ

多面体的パラダイム：問題 X P 良い LP 定式化を持つ

2

代数的組合せ最適化 part I

非可換 Edmonds 問題

1. 導入：２部マッチング，行列式，ランク 2. Edmonds 問題

3. 非可換 Edmonds 問題

• 非可換ランク (nc-rank)

• Fortin-Reutenauer の定理， MVSP

• Wong sequence

導入：２部マッチング，行列式，ランク

1 2 3 4

1 2 3 4

�=(� ,� ; �) 最大マッチング問題：

最大サイズ（枝数）のマッチングを求めよ

• 最大最小定理（ König-Egerváry , Hall ）

• 多項式時間アルゴリズム（増加道アルゴリズム）

4

最大マッチング問題の線形代数的解釈

1 2 3 4

1 2 3 4

�¿12

�₂₁

�₂₃ �₂₄

¿

¿ �₃₂

¿ � ₄₁

¿ ¿

¿

1

3 4 2

1 2 3 4

�=(� ,� ;�) �≔

∑

� �∈ �

�_���_��

Lem: の最大マッチング数

ランクの復習＋証明

，体上上線形独立な列（行）の最大数

(Lem の証明 )

det   �=

∑

�

sgn(�)

∏

�=1, …,�

�_{� �(�)}=

∑

�:∀�,��(�)∈�

sgn(�)

∏

�=1, … ,�

�_��(�)

¿

∑

�

sgn(�)

∏

� �∈ �

�_��

{

完全マッチング 6

Edmonds 問題

変数付き行列

のランクは効率的に計算できるか？

: 変数 体

有理関数体 �(�₁,�₂, … ,�_�)

↪

• ２部マッチング問題の代数的拡張

 いくつかの重要な P に属する組合せ最適化問題を含む

• 変数にの値を代入すると Gauss の消去法で簡単

 ||= 大 : 乱択多項式時間アルゴリズム (Lovasz 79)

一般 : NP 困難 (Buss et al. 1999)

• 未解決：決定性多項式時間アルゴリズム

• 回路計算量の関係 (Kabanets-Impagliazzo 2004)

8

Edmonds 問題

変数付き行列

のランクは効率的に計算できるか？

: 変数 体

非可換

�_� � _�≠� _� �_�

上

自由斜体�(⟨^�1, �₂, … , �_�⟩⁾

↪

非可換ランク nc-rank

Ivanyos-Qiao-Subrahmanyam 2015

10

nc-rank in P !!

• Garg-Gurvits-Oliveira-Wigderson 2015:

 part II

• Ivanyos-Qiao-Subrahmanyam 2015: 任意  part I ( いまから )

• Hamada-Hirai 2017: 任意 , bit-size unbounded  part III

のランクとは？

体 : 非可換変数

非可換ランクの定義 I ( 自由環上の行列としての inner rank)

非可換ランクの定義 II ( 自由斜体上の行列としての rank) , where

２つの定義は一致する (Cohn)

斜体（ skew field, division ring ）とは

逆元をもつ環 , i.e.,

～ 積演算が可換とは限らない体

例：四元数体

，斜体上

上右 ( 左 ) 線形独立な列 ( 行 ) の最大数

: 正則逆行列 ()

Dieudonne 行列式 (part III)¹²

自由斜体（ free skew field ）とは

～有理関数体の非可換アナログ

�₂�₃+5

�₁²+2�₃−3

∋

• Rational expression constructed from

•

( ) Thm (Amitsur 1966)

{ all rational expressions } / is a skew field

14

Edmonds 問題 ( 再掲 )

変数付き行列

のランクは効率的に計算できるか？

: 変数 体

非可換

�_� � _�≠� _� �_�

上

自由斜体�(⟨^�1, �₂, … , �_�⟩⁾

↪

非可換ランク nc-rank

Fortin-Reutenauer の定理

～非可換ランクの双対定理

s.t. ^{(∀ �)}

,

0

∗ ∗

∗

� ∗

�

� �

� =¿

, ，体

Thm (Fortin-Reutenauer 2004) _{注：この値は}

以上

注 : この双対問題 MVSP 自体は， Lovasz 1989 や分割行列の研究（ Ito,Iwata,Murota 1994 ） にでてきている．

証明の簡単な方向（）

(∀ �)

0

∗ ∗ ∗

� ∗

�

� �

� =¿

�−�

�

0

�

⇒ ��� = ¿

� ^�

0

�

�

�

�

0

�

0

�

�−�

�−�

¿

⇒ nc−rank � ≤ � + � − � − �

Cor:

Prop (Fortin-Reutenauer 2004)

�= �₁ �₁+ �₂ �₂+…+ �_��_�

16

組合せ最適化からの興味

• ２部マッチングや線形マトロイド交差に対応する 成立

• Fortin-Reutenauer の公式 組合せ最適化の最大最小定理

c.f. 多面体的パラダイム LP-duality min-max

• となるケース

歪対称行列，非２部マッチング，線形マトロイドマッチング ,...

• モジュラ束上の劣モジュラ最適化（ part III ）

18

König-Egerváry from Fortin-Reutenauer

s.t.

(∀ �=�� ∈ �)

nonsingular over

0

∗ ∗

∗

� ∗

�

� =¿

�

�

�

グラフ

permutation matrices

集合 |

¿ | 最小頂点カバー |

Ivanyos-Qiao-Subrahmanyam のアルゴリズム

• Wong sequence ～ ベクトル空間交互道

• : nc- 正則

• のバウンド (Derksen-Makam 2015)  不変式論の結果 キーアイデア

ここでは， Wong sequence の考え方を紹介する

クロネッカー積 正方

�(^�1)

�₁ , ，体

行列空間 Obs.

Wong sequence w.r.t.

�^� �^�

�₀≔{0}

~�⁻¹

�₂

�₂

�₃

20

Lem:

Wong sequence w.r.t.

行列空間

∵� _�+1=~�⁻¹(^�(� �))^⊇~�−1

(

)

~�∈�

�^� �^�

� _�

� _� ^~�−1

� _�+1 �

Lem (Ivanyos, Karpinski, Qiao, Santha 2015)

最適性の十分条件

�^� �^�

�_∞ � _∞

ker_�~

�

ker_�~

�

22

�^� �^�

�_∞ � _∞

ker_�~

�

ker_�~

�

証明

�_∞^⊥

: 正則行列， はの基底を含む， はの基底を含む

(∀ �)

0

∗ ∗ ∗

�

�

� =¿

�_∞^⊥

�_∞

�_∞

�

�

0

∗ ∗ ∗

�

~

�� = ¿

�_∞^⊥

�_∞

�_∞

0

列 full rank

rank  ~

�=rank  �^�~

� �=�−�+�−� ≥nc −rank   �

24

IQS アルゴリズム概略

行列空間 1.

2. Wong sequence w.r.t. を計算を得る．

3. なら， ( 終了 )

4. なら，

• を更新して， rank を増加させる，

• 行列空間をブローアップ : ,

• も拡大するかも．

※ ビットサイズも考慮する必要あり．

∕

難解であり，これ以上立ち入らない

増加道アルゴリズムとの関係

1 2 3 4

1’

2’

3’

4’

∈

1 2 3 4

1’ 2’ 3’ 4’

1 1

1

�₀=ker_�~

�=� �_4′

�₁=� �₂

�₁=� �_4′+� �_3′

�₂=� �₂+� �₄

�₂=� �_1′+� �_4′+� �_3′

¿�_∞

¿� _∞

⊆Im  ~

�

26

• この場合，マッチングに対応する増加道探索に一致する．

（一般のでは，はぐちゃぐちゃ）

• ，の更新して rank 増加 i.e., .

よって増加道アルゴリズムが実現できる．

（もの更新は一般に容易でない）

• 線形マトロイド交差のときは， Edmonds のアルゴリズムを実現できる．

_{（石川巧，卒業論文} 2018 ）

• Wong sequence の考え方は増加道タイプのアルゴリズムの設計の指針と

統一的理解につながるかもしれない．

∕

２ x ２型分割行列

�=

(

)

ここで，

• (Iwata, Murota 1995 の結果より )

Hirai-Iwamasa ( 準備中 ): Wong sequence のアイデアに基づいた

組合せ的多項式時間アルゴリズム

28

part I まとめ

• ２部マッチングの拡張としての Edmonds 問題

• 非可換 Edmonds 問題

• 非可換ランク

• Fortin-Reutenauer の定理

• IQS アルゴリズムと Wong sequence