本論文では，非線形整数計画問題の厳密解法を扱う．非線形整数計画問題とは非線形性を有する整数計画問題のことであり，さまざまな問題を記述することができる．本論文では，非線形整数計画問題のうち，特に，「ハブネットワーク設計問題」，「2次準割当問題」，「準分離凸整数計画」，「ロバスト混合整数計画」を扱う．

ハブネットワーク設計問題は，航空路線や通信においてハブと呼ばれる物流の中継点を用いて効率的なハブ・アンド・スポーク・ネットワークを構築する問題である．既存の研究ではハブの配置とネットワークを同時に決定する問題が主流であったが，このような問題は変数の個数が多くなるなどの理由で大きな問題例では厳密解を求めることが困難である．そこで，本論文では特にハブの配置の決定は既知とし，ネットワークの設計のみを考慮する問題を扱い，2種類の混合整数計画問題による定式化を提案する．この定式化は，従来の定式化よりも変数の個数が少なくなることが特徴であり，ハブの配置が既知，あるいは候補が限られている状況では従来の定式化よりも実際の計算では有利である．また，計算機実験によって，これらの定式化のLP緩和がよい下界を与えることを確認する．

2次準割当問題は，2次0-1整数計画問題と呼ばれる非線形整数計画問題の一種であり，ハブネットワーク設計問題を特殊例として含む．本論文では，2次準割当問題の混合整数計画問題による定式化に対し，許容解全体の凸包である多面体（2次準割当多面体）を導入し，切除平面法の構築を目的として，多面体の考察を行う．まず，2次準割当多面体の基本的な幾何学的性質（次元，アフィン包を定める等式系）を明らかにし，ある妥当不等式の族が極大面を定めるための必要十分条件を示す．さらに，この極大面を用いた切除平面法によって，ベンチマーク問題の最適解が容易に得られることを計算機実験によって示す．

準分離凸整数計画問題は，凸多面体内の整数格子点上で準分離凸関数を最小化する問題である．この問題に対し，整数線形計画問題におけるGraverテストセットを拡張し，最適性規準を示す．さらに，整数線形計画問題に対する整数基底法を拡張する．

ロバスト混合整数計画問題は，入力に不確定性をもつ混合整数計画問題に対し，ロバストな解のうちで最適化を行う問題である．この問題を整数制約をもつ錐線形計画問題（混合整数錐計画問題）として定式化し，一種の切除平面法による厳密解法を提案する．ロバスト混合整数計画の観点からは，従来の本質的に線形な不確定性に対し，本論文は楕円体の不確定性という非線形な不確定性を扱った点が新しい．また，本論文の解法は，通常の混合整数計画問題に対するBenders分解法の自然な拡張である．Benders分解法の特徴は，分枝限定法などの緩和問題に基づく従来の解法と異なり，各反復が通常の混合整数計画問題であり，切除平面を発見する分離問題が錐線形計画問題になることにある．従来の分枝限定法においては，緩和問題は錐線形計画になり，内点法によって効率的に解くことはできるが，線形の場合に用いられる単体法に基づく解法が利用できない．また，分枝限定法の実装は分枝ルールなどの工夫が重要であるが，混合整数錐計画問題に対する定評のある実装は未だ存在しない．一方，本論文が提案するBenders分解法は，既存の優れた混合整数計画ソルバを利用できることが利点である．

本論文の手法に共通する考え方は，新たに変数を導入することで非線形な問題を高次元において線形の場合に帰着させることや，逆に，高次元における非線形な問題を射影によって低次元の問題に変換することで線形な問題（の極限）として表現することである．

工学における設計問題の多くは，適切なモデル化を通じて最適化問題の形に定式化される．最適化問題の解法及びモデル化手法を研究する分野は数理計画法と呼ばれ，1940年代後半に線形計画法の枠組みが呈示されて以来，着実な進展を見せており，近年では，数学的構造の探求とアルゴリズムの設計とが以前にも増して密接な関係をもつに至っている．理論的な研究成果がソフトウェアに組み込まれて実際問題の解法に役立っている例も多い．

最適化問題は，通例，最適化変数が連続であるか離散であるかに従って，連続最適化と離散最適化に分類される．後者は組合せ最適化あるいは整数計画などと呼ばれるものの総称である．本論文で扱われる非線形整数計画問題は最も一般的な離散最適化問題のクラスであり，計算量理論の立場からは，いわゆるNP困難な問題である．したがって，多項式時間アルゴリズムは望むべくもないが，理論と応用の両面から，解決すべき問題が多く残されている．

本論文は「非線形整数計画問題に対する高次元構造に基づく解法」と題し，種々の非線形性を有する整数計画問題に対する解法を提案し，主として理論的な立場からの考察を行ったものである．本論文の手法に共通する考え方は，新たに変数を導入することで所与の非線形問題を高次元空間に埋め込んで線形化することや，逆に，高次元空間における非線形問題を射影によって低次元空間における問題に等価変形し，それを線形問題の列によって近似するというものである．第1章「はじめに」，第6章「おわりに」を含め，6章より成る．

第2章「ハブネットワーク設計問題の混合整数計画による解法」では，航空路線の設計などにおいて中継点（ハブ）を利用することによって効率的なネットワークを構築する問題を扱っている．既往研究においてはハブの配置とネットワークの接続構造を同時に決定する問題が扱われることが多かったが，この種の問題を定式化すると最適化変数の個数が極めて多くなり，大きな問題例で厳密解を求めることは困難であった．このような現状を踏まえて，本論文においては，ハブの配置が所与の場合に，従来よりも少ない個数の変数を用いた混合整数計画問題の定式化を示し，計算機実験によって，その連続緩和が良好な下界を与えることを確認している．

第3章「2次準割当問題に対する多面体的アプローチ」では，2次準割当問題の自然な定式化として得られる混合整数計画問題を考え，その許容解全体の凸包のなす多面体に関して，次元，アフィン包，極大面などの数学的な性質を明らかにしている．その中で重要な点は，ある妥当不等式の族が極大面を定めるための必要十分条件を与えたことである．さらに，その極大面を用いた切除平面法によってベンチマーク問題が容易に解けることを計算機実験によって示している．

第4章「整数基底法の準分離凸整数計画への拡張」では，凸多面体内の整数格子点上で準分離凸関数（線形関数と凸関数の合成関数の和）を最小化する問題に対し，整数線形計画問題におけるGraverテストセットを拡張した形の最適性規準を示している．さらにその結果を利用して整数基底法の拡張を与えている．

第5章「ロバスト混合整数計画」では，入力データが不確定性をもつような混合整数計画問題が整数制約をもつ錐線形計画問題の形に定式化できることを示し，Benders分解に基づく厳密解法を提案している．従来のロバスト混合整数計画の枠組みが線形の不確定性に限定されていたのに対し，本論文の手法は楕円体という現実的な不確定性を扱えるという特徴がある．解法の設計という観点から見ると，Benders分解という一般的なアプローチに従いながら錐制約のもつ特殊性を巧妙に利用した手法であり，混合整数計画問題を解くためのソフトウェアの進展を背景として，理論・実用の両面から高く評価できる内容となっている．ナップサック問題や一般化割当問題の入力データに不確定性のある場合について計算機実験を行ない，本論文の手法と分枝限定法とを比較して，提案する手法の有効性を検証している．

以上を総合するに，本論文は，数理計画法における理論の進展とソフトウェアの現状を踏まえて，種々の非線形性をもつ整数計画問題の解法を構築したものであり，数理工学の分野の発展に大きく寄与するものである．

よって本論文は，博士 （情報理工学） の学位請求論文として合格と認められる．