組み合わせ最適化問題に対するテスト例題生成手法の研究

组合优化问题测试例生成方法研究

基本信息

批准号：
15700008
负责人：
元木光雄
金额：
$ 2.05万
依托单位：
Japan Advanced Institute of Science and Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2005
项目状态：
已结题

项目摘要

テスト例題生成手法は,問題を解くアルゴリズムの性能を実験的に解析する際に必要となる.対象となる問題が困難なものである場合,特に,最適化問題では最適解を与えられても,それが本当に最適かどうかを判定することも困難であるので,テスト例題には正解がついていることが望ましい.したがって,本研究では,組合せ最適化問題に対する正解付きテスト例題生成手法の開発を目標とした.本年度は,昨年度に行った2CNF論理式の最大充足化問題であるMAX 2SAT問題に対するテスト例題生成手法によって生成される例題集合の難しさの解析の更なる改善を行った.昨年度に証明した結果では,生成された例題集合を判定することがNP困難であることだけではなく,近似比55/56以内で判定することも難しいということを証明していた.しかし,この近似比はMAX 2SAT問題の近似不可能性の結果である21/22と比べると大きく,最適であるとはいえなかった.そこで,証明で用いた還元を見直し,生成された例題集合を近似比21/22以内で判定することが困難であることを理論的に証明した.具体的には,各式にちょうど3個の変数が出現する,剰余2のもとでの線形連立方程式の系を解く問題であるE3Lin2問題からの還元を用いた.この還元はMAX 2SATの近似不可能性21/22を示すために用いられたものであるが,今回の証明ではこの還元がある種の性質を満たすことを示す必要があったので,必ずしも自明な結果ではない.この結果はさらに,他の最適化問題における最適解付きのテスト例題生成手法で生成される例題集合の難しさを確立するための手段として有望であることが考えられる.

在实验分析问题求解算法的性能时，测试实例生成方法是必要的。当目标问题较困难时，尤其是优化问题，即使给出最优解，也很难确定其是否真正最优。因此，希望测试样例具有正确的答案。因此，本研究的目标是开发一种为组合优化问题 MAX（最大满足问题）生成具有正确答案的测试样例的方法。我们进一步改进了对2SAT问题的测试实例生成方法生成的实例集难度的分析。我们去年证明的结果表明，仅仅判断生成的实例集是NP-hard是不够的。在55/56的近似比例内很难做出判断。但是，这个近似比例是MAX。它大于21/22，这是2SAT问题不可逼近的结果，并不能说是最优的，因此，我们回顾了证明中使用的约简，并将生成的示例集约简到了约比之内。可以通过21/22来判断。我们已经从理论上证明了这是困难的，具体来说，我们已经解决了 E3Lin2 问题的约简，这是一个求解余数为 2 的线性联立方程组的问题，其中每个方程中恰好出现三个变量。减少量为 MAX这被用来证明 2SAT21/22 的不可近似性，但在这个证明中，有必要证明这种约简满足某些性质，因此它不一定是一个明显的结果，这个结果也可以被认为是建立 2SAT21/22 的有前途的手段。通过为其他优化问题生成具有最佳解决方案的测试示例的方法生成的示例集的难度。