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

组合问题的鲁棒优化

基本信息

批准号：
16J11392
负责人：
呉偉
金额：
$ 0.83万
依托单位：
Nagoya University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2016
资助国家：
日本
起止时间：
2016-04-22 至 2018-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16J11392/
关键词：
ロバスト最適化組合せ最適化

项目摘要

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

大多数优化技术被视为具有固定的输入数据，并且设计了算法。但是，在许多现实世界中，歧义性和不确定性是输入数据中固有的。这样，当通过应用现有优化方法获得的解决方案而无需考虑不确定性并将预测的值作为确定输入数据而获得的问题时，没有任何函数不会影响解决方案，这可能会导致遗憾。在这项研究中，我们提出了一种基于可以实际解决此类问题的可靠标准来优化问题的方法。在2016财年，我们专注于对多维背包问题的强大优化，这是多维背包问题的概括。已知多维背包问题很难NP，但这是一个具有多个背包约束的问题，并且是一个非常重要的问题，通常是由于将工作和财务计划问题等成真实的优化问题而导致的。作为解决多维背包问题的强大优化方法，我们提出了一种方法（迭代相对替代方法），该方法改善了使用行生成方法的2015年研究中提出的相对替代方法。对于每次迭代，所得约束是线性的，相对替代方案给出了最佳值的上限和下限，并且可以通过验证这些值的接近度来评估性能。结果是在国内会议上提出的。此外，为了确定绩效是好还是坏，实施了基于基于它们的基本方法和已知的固定方案方法，Bender的分解方法以及基于它们的分支切割方法，并在生成的问题示例上进行了比较实验，并在国际会议上提出了研究结果。此外，为了验证提出的迭代相对替代方法是一种通用方法，我们对背包问题的研究进行了比较实验，并将覆盖问题设置为其他典型的可靠优化问题。该实验比现有研究提供了更好的结果，因此可以验证该方法的多功能性并编译期刊文章。