整数計画問題に対して,トーリックイデアルの離散性を用いてGrobner基底やstandard pairを適用する研究が近年なされている.これらのアプローチは既存の整数計画問題に対する解法に比べて計算量を改善するようなものではないが,トーリックイデアルの組合せ論的な構造に関する結果が多くあるため,整数計画問題の構造に対する代数的な解析が与えられると期待される.

多項式環上のイデアルにおいて,Grobner基底とstandard pairの集合は,Grobner基底のinitial termで生成されるinitial idealに属する単項式の集合の補集合の,ある性質の良い分解がstandard pair分解である,という意味で,双対の関係にあると言える.このような双対性が組合せ最適化における新たな双対性を与え,さらに双対定理の成り立つ整数計画問題のクラスを考え,このクラスの特徴を用いることにより,一般的な整数計画問題からは得られないような計算量の上下限を得ることができると期待される.本論文では,特に係数行列が単模のとき,およびLawrence型であるときに着目する.

係数行列Aが単模であるような問題は,不等式系yA〓cが完全双対整数性(TDI)を満たし,さらに各standard pairが双対実行可能基底に対応する,という点で性質の良い問題のクラスである.本論文では,係数行列が単模であるような整数計画問題に対してstandard pairを用いた方法は,そのstandard pairに対応する基底での被約コストを計算することと等価であることを示す.よって,standard pairの数(つまり,双対実行可能基底の数)がこの方法の計算量を与える.さらに,双対実行可能基底の数の最大値が,行列Aを斉次化して定義される多面体の正規化体積で表せることを示す.

　さらに,本論文では特に最小費用流問題に着目する.最小費用流問題は,単模な整数計画問題の中でも多項式時間で解くことのできる問題のクラスをなすことが知られている.この問題に対するGrobner基底を用いたアプローチは,既存の負閉路消去アルゴリズム ,つまり実行可能流に対して残余ネットワーク内の負閉路を見つけて流し変えていく方法の変形である.一方,standard pairを用いたアプローチでは,まずstandard pairの集合を求め,非負整数解が得られるまで,各pairに対応する線型連立方程式を解く方法である.ここでは,もっとも基本的な有向グラフである無閉路トーナメントグラフ上の最小費用流問題に着目する.このとき,Grobner基底はグラフの言葉で特徴づけることができる.これを用いて,主問題に対する双対実行可能基底の数が高々Catalan数であるのに対し,双対問題に対する主実行可能基底の数が少なくとも指数オーダになることを示す.ネットワーク最適化問題において,Grobner基底と双対実行可能基底の関係はサーキットと双対実行可能補木(双対的には,カットセットと主実行可能木)の関係に対応する.これらの関係はほとんど明らかでないので,この結果は計算代数的双対性を用いた解析の面白い結果である.

　一方,組合せ最適化において,Lawrence型の行列は容量付き整数計画問題やある多次元輸送問題など,多くの問題に表れる.また,統計学において,各行和を固定したある型の多次元分割表のサンプリングや数え上げにLawrence型の行列が用いられることが知られている.行和の固定された3元分割表を数え上げる問題が#P-completeであることが知られている一方で,近年2×2×…×2×N型の分割表に対して,多項式時間マルコフ連鎖モンテカルロ法が提案された.

　Lawrence型の行列に対するGrobner基底と行列のベクトルマトロイドとの関係は良く研究されているが,standard pairについては良く分かっていない.そこで本論文では,特に双対実行可能基底に対応するstandard pairに着目し,このようなstandard pairの集合とベクトルマトロイドの基集合の間の全単射を与え,さらにそのようなstandard pairたちのマトロイド的な構造を示す.特に,行列が単模であるときは,上の関係は双対実行可能基底の数とベクトルマトロイドの基の数が等しいことを表している.さらにその系として,無閉路トーナメントグラフ上での容量付き最小費用流問題に対する双対実行可能基底の数が与えられることを示す.また,2×2×…×2×M×N型の多次元輸送問題に対する双対実行可能基底の数についても解析する.一方,多次元輸送問題の双対問題に対しては,2×2×…×2×2×N型の輸送問題の双対問題に関して双対実行可能基底の数を解析し,2×2×…×2×M×N(M〓3)型の多次元輸送問題に対する解析は複雑であることを示す.これは,多元分割表に関する統計的・組合わせ的な問題に対して,2×2×…×2×2×N型の輸送問題とそうでない型の問題との複雑さの違いを計算代数的に与えている.

　本論文は5章より成り、第1章では整数計画問題、特に単模な整数計画問題やLawrence型整数計画問題を、Grobner基底やtoric idealsのstandard pairなどの計算代数的手法と関係付けるという本論文の基本的な主張の背景について述べる。第2章ではGrobner基底とstandard pair分解という二つの計算代数的手法を導入し整数計画問題との関係を示す。第3章は単模な整数計画問題を取り上げ、standard pairsの数の最大が、polytopeの体積で与えられることを示し、無閉路トーナメントグラフ上の最小費用流問題の主問題と双対問題への計算代数的アプローチを示す。第4章ではLawrence型の整数計画問題を取り上げ、双対実行可能空間のstandard pairsの集合と、ベクトルマトロイドの基集合との間に全単射が成立することを示す。第5章では、主要な結果をまとめ、その意味について考察する。

　整数計画問題に対して、近年Grobner基底やstandard pairを用いた計算代数的手法が研究されている。これらの手法と既存の組合せ的手法の橋渡しを行うことにより、双方の手法の理解が高まり、新たな構造解析手法やアルゴリズムの構築が期待される。多項式環上のイデアルにおいて、Grobner基底は初項イデアルの生成系であり、standard pairの集合は初項イデアルに含まれない単項式の集合の分解であるため、双対の関係にあると言える。このような双対性に着目し、さらに双対定理の成り立つ整数計画問題のクラスを考え、より豊かな橋渡しができ、一般的な整数計画問題からは得られないような計算量の上下限を得ることができると期待される。本論文では、そのような整数計画問題のクラスとして、係数行列が単模のとき、およびLawrence型であるときに着目した。

係数行列Aが単模であるような問題は、不等式系が完全双対整数性(TDI)を満たし、さらに各standard pairが双対実行可能基底に対応する、という点で性質の良い問題のクラスである。本論文では、係数行列が単模であるような整数計画問題に対してstandard pairを用いた方法が、そのstandard pairに対応する基底での被約コストを計算することと等価であることを示した。よって、standard pairの数(つまり、双対実行可能基底の数)がこの方法の計算量を与える。さらに、双対実行可能基底の数の最大値が、行列Aを斉次化して定義される多面体の正規化体積で表せることを示す。これにより、Grobner基底から体積計算を通じて双対多面体の頂点数を解析するという統一的なアプローチを与えることができた。

　さらに、本論文では特に輸送問題、および最小費用流問題に着目した。これらの問題に対するGrobner基底を用いたアプローチは、既存の負閉路消去アルゴリズム、つまり実行可能流に対して残余ネットワーク内の負閉路を見つけて流し変えていく方法の変形である。一方、standard pairを用いたアプローチでは、まずstandard pairの集合を求め、非負整数解が得られるまで、各pairに対応する線形連立方程式を解く方法である。輸送問題の主問題および双対問題の実行可能領域の頂点数に関しては、これまでに既存の結果が知られているが、ここでは上のアプローチによる別証を与えた。さらに、無閉路トーナメントグラフ上の最小費用流問題に着目し、最小費用流問題に対する双対実行可能基底の数が高々Catalan数となること、および主実行可能基底の数が少なくとも指数オーダになることを示した。ネットワーク最適化問題において、Grobner基底と双対実行可能基底の関係はサーキットと双対実行可能補木(双対的には、カットセットと主実行可能木)の関係に対応することを示した。これらの関係はほとんど明らかにされていないので、この結果は計算代数的双対性を用いた解析の面白い結果である。

　一方、組合せ最適化において、Lawrence型の行列は容量付き整数計画問題やある多次元輸送問題など、多くの問題に現れる。また、数理統計学において、各行和を固定したある型の多次元分割表のサンプリングや数え上げにLawrence型の行列が用いられることが知られている。行和の固定された2元分割表を数え上げる問題がP-completeであることが知られている一方で、2×2×…×2×N型の分割表に対してmixing timeが多項式時間となるマルコフ連鎖モンテカルロ法が提案されている。Lawrence型の行列に対して、行列の定めるベクトルマトロイドとGrobner基底との関係は良く研究されているが、standard pairについては良く分かっていない。そこで本論文では、特に双対実行可能基底に対応するstandard pairに着目し、まず双対実行可能基底に対応するstandard pairの集合とベクトルマトロイドの基集合の間の全単射を与え、さらにそのようなstandard pairsのマトロイド的な構造を示した。特に、この関係は双対実行可能基底の数とベクトルマトロイドの基の数が等しいことを表している。さらにその系として、無閉路トーナメントグラフ上での容量付き最小費用流問題に対する双対実行可能基底の数、2×2×…×2×M×N型の多次元輸送問題に対する双対実行可能基底の数、2×2×…×2×N型の輸送問題の主実行可能基底の数を解析した。

　本研究は整数計画問題を計算代数的な新しい視点からその構造を明らかにしたものであり、今後の発展が期待できる。

　本研究の一部は、今井浩および中山裕貴との共同研究であるが、論文提出者が主体となって分析及び検証を行ったもので、論文提出者の寄与が十分であると判断する。

　したがって、博士(理学)の学位を授与できると認める。