修士論文 要旨

q-ホーンシステムの実行可能性を判定する組合せ的アルゴリズム
数理情報学専攻 48096212
指導教員

木村 慧
牧野 和久 准教授

Conjecture [2] が大きな目標となっている，この予想

1 はじめには，P から NP 完全までの間に無数の計算複雑さのクラ本研究では実行可能性判定の部分問題についての研究を行う．実行可能性判定は現実の問題をモデル化しスがあるが，CSP(Γ) は P かＮＰ完全かの両極端のどちらかであるという予想である．

た施設配置問題やスケジューリング問題を含むだけ

次に整数計画問題について説明する．整数計画問題

でなく，理論的にも計算機科学の中心の一つであり，は線形計画問題に変数の整数性を加えた問題で，組合せ人工知能，数理計画，離散数学の分野を初め幅広い分最適化の分野で 1950 年代から研究されている．整数計野で研究が行われている．人工知能では制約充足問題

画問題に対してはこれまでヒューリスティックな厳密(Constraint Satisfaction Problem, CSP) として，数理解法，効率的に解ける部分問題等の研究が盛んに行わ

計画では線形計画問題や整数計画問題として，離散数学れてきた．厳密解法としては切除平面法動的計画法分では充足可能性問題として実行可能性判定問題は現れ子限定法効率的に解ける部分問題については変数の数る．本研究では，制約充足問題および整数計画問題両方を固定したとき [7]，係数行列が完全単模であるとき [4]の部分問題である整数線形システムの実行可能性判定に多項式時間で解けることが知られている．以上を含に対する研究を行い，計算複雑さの指標を作成する．こめた整数計画問題の歴史については [6] にまとまっての問題は整数行列 A ∈ Zm×n ，整数ベクトル b ∈ Zm ，いる．

自然数 d ∈ N が入力として与えられたとき，線形システム

本研究では線形計画問題による整数線形システムに対する計算複雑さの指標を作成した．そして，この指標

Ax ≥ b, x ∈ Dn(1)が実行可能であるかを判定する問題である．この問題は代表的な NP 完全問題であり，様々な問題を自然に定式化できる．離散数学で最も重要な問題の 1 つである充足可能性問題 (SATisﬁability Problem, SAT 問題)
やグラフ理論におけるハミルトン閉路問題や組合せ最が計算複雑さを二分することを示した．このことは制約充足問題の目標である Dichotomy が，部分問題の違う切り口からではあるが，成り立つことを示していて理論的に大変興味深い．また，整数計画問題における実用性も期待される．

2 先行研究適化の分野に現れる分割問題，部分集合和問題，スケジューリング問題は数多くある例のうちの一部である．
本研究で扱った整数線形システムの実行可能性問題
は制約充足問題および整数計画問題の部分問題である．
まず，制約充足問題について説明する．制約充足問題は与えられた制約を満たす変数への値の割り当てが存在するかを判定する問題である．本研究で扱う整数線形システムの実行可能性問題は，Γ として，線形システムによって表せるような部分集合全てからなる集合族を考えた場合の CSP(Γ) となっている．CSP の表
現力は大変に強力であり，人工知能やオペレーションズ・リサーチの分野において理論，実用共に盛んに研究されている．CSP は NP 完全問題であるので部分問題へ制限したときの CSP の計算複雑さを求める研究も盛んに行われている．このような研究では Dichotomy

本研究に直接的に関連する研究として以下のものがある．Hochbaum–Megiddo–Naor–Tamir [3] は係数行列の各行の非ゼロ成分が高々 2 つであるときに，vanMaaren–Dang [8] は係数行列の各行の正の成分が高々1 つであるときに，整数線形システムの実行可能性問題が多項式時間で判定できることを示した．これらの問
題をそれぞれ 2 システム，ホーンシステムと呼ぶことにする．また，係数行列の成分が {−1, 0, 1} のみである
場合には，係数行列の各行の非ゼロ成分が高々 2 つであるときの多項式時間アルゴリズムが Jaﬀer–Maher–Stuckey–Yap [5] によって提案された．さらに，係数行列の成分が {−1, 0, 1} のみである場合，係数行列の各行の正の成分が高々 1 つであるときの多項式時間で解けることが Chandrasekaran [1] によって示されている．

q-ホーンシステムの実行可能性を判定する組合せ的アルゴリズム (木村 慧)

3 成果

4 まとめ

本研究では整数線形システムの符号情報を用いた実本研究では整数線形システムに対する計算複雑さの行可能性判定問題に対する計算複雑さの指標を作成し指標を作成した．この指標は線形計画問題の最適値なた．実数 a の符号とはので効率的に計算できる．また，この指標における簡単 + (a > 0),0 (a = 0),sign a =
− (a < 0)な問題は先行研究を符号という観点から包括的に捉え(2)る枠組みである．さらに，この指標は計算複雑さの指標を 3 分することを示した．このような Trichotomy がと定義される関数である．また，行列 A の符号パターン成立するのは理論的に興味深い．とは sign(A) = (sign aki ) で定義される {+, −, 0}m×n

今後の課題としては，この指標により，制約充足問題行列である．本研究では符号情報より，元の行列 A にの分野の大きな目標である Dichotomy Conjecture に対する実行可能性問題の解き易さを求める．符号の情新しいアプローチを試みることが考えられる．また，異報のみから以下のような線形計画問題を定式化する：

なる定式化の手法を考えることや，q-ホーンシステムが

min.
s.t.

Z
∑

何故解きやすいのかを離散凸解析や多面体論的な視点
i∈Pk αi +∑0 ≤ αi ≤ 1.

i∈Nk (1 − αi ) ≤ Z,(3)ここで，k = 1, . . . , m, i = 1, . . . , n であり，A =(aki ) として Pk = {i | sign(aki ) = +}, Nk = {i |sign(aki ) = −} である．この線形計画問題の制約式は，行列 A の符号パターンに対する制約となっている．線
形計画問題 (3) の最適解が c 以下である問題例の集合を FC(c) と書くこととする．本研究の主結果は以下の2 つの定理である．
定理 3.1. 整数線形システムに関して以下が成り立つ：(1) 任意の定数 ϵ > 0 に対し，FC(1 − ϵ) は多項式時間可解である．

(2) FC(1)（q-ホーンシステム）は擬多項式時間可解である．

(3) 任意の定数 ϵ > 0 に対し，FC(1 + ϵ) は強 NP 完全である．
また，整数線形システムの中で，係数行列の成分が{−1, 0, 1} のみである問題例の集合を単位整数線形システムと呼ぶこととする．線形計画問題 (3) の最適解がc 以下である単位整数線形システムの問題例の集合をUFC(c) と書くこととする．
定理 3.2. 単位整数線形システムに関して以下が成り立つ：(4) UFC(1) は多項式時間可解である．
(5) 任意の定数 ϵ > 0 に対し，UFC(1+ ϵ) は強 NP 完
全である．

から考察することも今後の課題として挙げられる．

参考文献[1] R. Chandrasekaran, Integer programming problems
for which a simple rounding type algorithm works,
Progress in Combinatorial Optimization, 8 (1984),
pp. 101–106.
[2] T. Feder and M. Y. Vardi, The computational
structure of monotone monadic SNP and constraint
satisfaction: A study through datalog and group theory, SIAM Journal on Computing, 28 (1998), pp. 57–104.
[3] D. S. Hochbaum, N. Megiddo, J. Naor, andA. Tamir, Tight bounds and 2-approximation algorithms for integer programs with two variables per
inequality, Mathematical Programming, 62 (1993),
pp. 69–83.
[4] A. J. Hoffman and J. B. Kruskal, Integral boundary points of convex polyhedra, in Linear Inequalities
and Related Systems, H. Khun and A. Tucker, eds.,
Princeton University Press, 1956, pp. 223–246.
[5] J. Jaffar, M. J. Maher, P. J. Stuckey, andR. H. C. Yap, Beyond finite domains, Principles
and Practice of Constraint Programming, 874 (1994),
pp. 86–94.
[6] M. Jünger, T. M. Liebling, D. Naddef, G. L.
Nemhauser, W. R. Pulleyblank, G. Reinelt,
G. Rinaldi, and L. A. Wolsey, eds., 50 Years of Integer Programming 1958-2008: From the Early Yearsto the State-of-the-Art, Springer-Verlag, Heidelberg,
2010.
[7] H. W. Lenstra, Jr., Integer programming with afixed number of variables, Mathematics of Operations
Research, 8 (1983), pp. 538–548.
[8] H. van Maaren and C. Dang, Simplicial pivoting
algorithms for a tractable class of integer programs,
Journal of Combinatorial Optimization, 6 (2002),
pp. 133–142.