0-1解をもつ線形不等式系に対するChubanovの強多項式時間アルゴリズムの実装と実験的考察

伊藤 優

（指導教員：牧野 和久 准教授／数理情報第2研究室）

研究概要

線形計画問題は、単体法・楕円体法・内点法など弱多項式時間の解法が知られるが、強多項式時間の解法はまだ発見されていない。Chubanovは一部の線形計画問題が強多項式時間で解けることを示した。本研究ではChubanovのアルゴリズムを実装し実際の挙動を観察した。

Chubanovのアルゴリズムが再帰的に出力を求める様子

卒論の感想

研究室の先生・先輩方のご指導の一つひとつが本当にためになり、研究に対する心構えを含めたくさんのことを学ばせていただきました。今後の糧となる有意義な半年でした。