線形相補性問題の整数性に関する研究

数理計画法の分野では，制約，条件を満たす解を求める手法が研究されている．本研究では，数理計画法において基礎的かつ理論的にも実用上も重要な，線形相補性問題と呼ばれる問題を扱う．この問題は，行列とベクトルが与えられたとき，条件を満たすベクトルを求める問題である．線形相補性問題は，線形計画問題や凸二次計画問題，双行列ゲームといった基本的な問題を含み，経済学や力学といった周辺分野にも応用をもつ．本研究では，線形相補性問題の解ベクトルの中でも特に，整数ベクトルの解（整数解）が存在するための十分条件に着目した．応用によっては，整数解を得ることが必要な状況があるためである．線形相補性問題の整数解に関する先行研究では，入力行列が主単模と呼ばれる性質をもつならば，基底解が整数となることを示している．一方，線形相補性問題の特殊ケースである線形計画問題（線形制約を満たす中で線形関数を最大にするベクトルを求める問題）では，入力行列の完全単模性や，その拡張である線形制約の完全双対整数性が，整数最適解の存在を保証する性質として知られている．また，主単模行列は完全単模行列のひとつの拡張であり，先行研究で線形計画問題の結果の拡張に対応する結果が知られている．本研究の成果は，線形相補性問題の完全双対整数性を提案し，線形計画問題で知られている結果に対応する線形相補性問題の結果を得たことである．本研究のような研究がなされていなかったのは，線形相補性問題の「双対性」に関する研究が少なかったことがひとつの理由である．本研究では，新たに「方向つき線形相補性問題」を導入し，これを用いて線形相補性問題の双対性を提案した．本研究の成果は現在論文誌に投稿中であり，国内学会で発表を行った．

数理計画法の分野では，制約，条件を満たす解を求める手法が研究されている．本研究では，数理計画法において基礎的かつ理論的にも実用上も重要な，線形相補性問題と呼ばれる問題を扱う．この問題は，行列とベクトルが与えられたとき，条件を満たすベクトルを求める問題である．線形相補性問題は，線形計画問題や凸二次計画問題，双行列ゲームといった基本的な問題を含み，経済学や力学といった周辺分野にも応用をもつ．本研究では，線形相補性問題の解ベクトルの中でも特に，整数ベクトルの解（整数解）が存在するための十分条件に着目した．応用によっては，整数解を得ることが必要な状況があるためである．線形相補性問題の整数解に関する先行研究では，入力行列が主単模と呼ばれる性質をもつならば，基底解が整数となることを示している．一方，線形相補性問題の特殊ケースである線形計画問題（線形制約を満たす中で線形関数を最大にするベクトルを求める問題）では，入力行列の完全単模性や，その拡張である線形制約の完全双対整数性が，整数最適解の存在を保証する性質として知られている．また，主単模行列は完全単模行列のひとつの拡張であり，先行研究で線形計画問題の結果の拡張に対応する結果が知られている．本研究の成果は，線形相補性問題の完全双対整数性を提案し，線形計画問題で知られている結果に対応する線形相補性問題の結果を得たことである．本研究のような研究がなされていなかったのは，線形相補性問題の「双対性」に関する研究が少なかったことがひとつの理由である．本研究では，新たに「方向つき線形相補性問題」を導入し，これを用いて線形相補性問題の双対性を提案した．本研究の成果は現在論文誌に投稿中であり，国内学会で発表を行った．