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

组合问题的鲁棒优化

基本信息

批准号：
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-hard问题，但它是一个具有多个背包约束的问题，并且已经针对现实世界中的许多优化问题制定了公式，例如装载操作和财务规划问题，这是一个非常重要的问题。可以看到。作为解决多维背包问题的鲁棒优化方法，我们提出了一种使用行生成方法来改进我们2015年研究中提出的相对替代方法的方法（迭代相对替代方法）。在每次迭代中，产生的约束都是线性的，并且相对替换方法产生最优值的上限和下限，允许通过验证这些值的接近度来评估性能．结果在全国会议上公布。另外，为了判断性能的好坏，我们实现了被称为基本方法的场景固定方法、Wenders分解方法以及基于它的分支切割方法，并对每种方法进行了对比实验研究结果在国际会议上发表。此外，为了验证所提出的迭代相对替代方法是一种通用方法，我们与背包问题、集合覆盖问题等其他典型鲁棒优化问题的研究进行了对比实验。在这个实验中，我们获得了比现有研究更好的结果，使得验证该方法的通用性成为可能，并编写了一篇期刊文章。