組合せ問題に対するロバスト最適化

最適化手法のほとんどは，入力データが確定されたものとして扱わされ，アルゴリズムが設計されている．しかし，多くの現実問題では入力データには曖昧さや不確定要素が内在している．この様に不確定要素を深く考慮せず，予測値を確定入力データとして、既存の最適化手法を適用して得られた解の場合は，入力データの変動が解に影響しない機能がないため，大きな後悔を招く場合がある．本研究では，このような問題を現実的に解決可能とする，ロバスト基準での最適化問題に対する手法を提案した．2016年度は多次元ナップサック問題を一般化した多次元ナップサック問題のロバスト最適化を対象とした．多次元ナップサック問題は，NP困難であることが知られているが，ナップサック制約が複数ある問題で，積荷作業や，資金計画問題など，数多く現実社会の最適化問題への定式化の結果として多く見受けられる非常に重要な問題である．多次元ナップサック問題を解くためのロバスト最適化手法として，2015年の研究で提案した相対代替法を行生成アプローチで改善していく手法（反復相対代替法）を提案した．各反復では，得られた制約は線形であり，相対代替法により，最適値に対する上界と下界の両方が得られ，これらの値の近さを検証することで性能を評価することができた．その結果を国内会議で発表を行った．また，性能の善し悪しを判断するため，基本手法と知られているシナリオ固定法，ベンダース分解法とそれに基づいた分枝カット法を実装，生成した問題例に対して各解法の比較実験を行い,その研究成果を国際会議で発表した．加えて，提案した反復相対代替法が汎用的な手法であることを検証するため，他の代表的なロバスト最適化問題として，ナップサック問題，集合被覆問題の研究との比較実験を行った．本実験では既存の研究より良い結果が得られ，手法の汎用性が検証可能となり，ジャーナル論文をまとめている．

最適化手法のほとんどは，入力データが確定されたものとして扱わされ，アルゴリズムが設計されている．しかし，多くの現実問題では入力データには曖昧さや不確定要素が内在している．この様に不確定要素を深く考慮せず，予測値を確定入力データとして、既存の最適化手法を適用して得られた解の場合は，入力データの変動が解に影響しない機能がないため，大きな後悔を招く場合がある．本研究では，このような問題を現実的に解決可能とする，ロバスト基準での最適化問題に対する手法を提案した．2016年度は多次元ナップサック問題を一般化した多次元ナップサック問題のロバスト最適化を対象とした．多次元ナップサック問題は，NP困難であることが知られているが，ナップサック制約が複数ある問題で，積荷作業や，資金計画問題など，数多く現実社会の最適化問題への定式化の結果として多く見受けられる非常に重要な問題である．多次元ナップサック問題を解くためのロバスト最適化手法として，2015年の研究で提案した相対代替法を行生成アプローチで改善していく手法（反復相対代替法）を提案した．各反復では，得られた制約は線形であり，相対代替法により，最適値に対する上界と下界の両方が得られ，これらの値の近さを検証することで性能を評価することができた．その結果を国内会議で発表を行った．また，性能の善し悪しを判断するため，基本手法と知られているシナリオ固定法，ベンダース分解法とそれに基づいた分枝カット法を実装，生成した問題例に対して各解法の比較実験を行い,その研究成果を国際会議で発表した．加えて，提案した反復相対代替法が汎用的な手法であることを検証するため，他の代表的なロバスト最適化問題として，ナップサック問題，集合被覆問題の研究との比較実験を行った．本実験では既存の研究より良い結果が得られ，手法の汎用性が検証可能となり，ジャーナル論文をまとめている．