データの精度を考慮した組合せ最適化問題に対する問題構造とアルゴリズムの研究

点击翻译按钮获取中文摘要

組合せ最適化問題は,いくつかの数値データを用いてある組合せ構造をもつシステムを表し,最適な状態(解)を求める.本研究では,主にネットワーク構造をもつ問題を対象に,与えられた実行可能な解を最適にするように,逆にデータを修正する問題である逆最適化問題や,データの与え方をより一般的にした問題に対するアルゴリズムの開発を行った.1.最小カット問題に対するミニマックス型逆最適化問題:与えられたカットが最小容量をもつように,枝容量を修正する問題.最大平均カット問題と深い関わりがあることを示し,最大平均カット問題に対するアルゴリズムを適用することで効率的に解けることを示した.2.一般化最小費用流問題に対するミニマックス型逆最適化問題:各枝に利得/損失のある一般化ネットワーク上の実行可能流が最小費用となるように枝費用を修正する問題.最小平均閉路問題との関係を示した.さらに,パラメトリックサーチによるアルゴリズムを詳しく解析することで,繰り返し回数がこれまで知られている回数よりも少なく押さえられることを示した.3.利得関数を一般化した一般化最大流問題:各枝に利得/損失めある一般化ネットワークでは,その利得/損失は線形関数で与えられていた.この利得/損失のデータの与え方をより一般的に凹関数とし,そのときの最大流問題に対する最適性条件とアルゴリズムを示した.