極めて大規模な重み付き部分Ｍａｘ－ＳＡＴ問題に対する新しいソルバーの開発

开发用于超大规模加权部分 Max-SAT 问题的新求解器

基本信息

批准号：
14J02096
负责人：
花田研太
金额：
$ 1.41万
依托单位：
Kobe University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2014
资助国家：
日本
起止时间：
2014-04-25 至 2016-03-31
项目状态：
已结题

项目摘要

本研究では，極めて大規模な重み付き部分Max-SAT問題を 1) 分散環境で解くアルゴリズムと 2) 集中環境で解くアルゴリズムの2つを開発した．また，3) プライバシーを確保したセキュアな分散環境で解くためのプロトコルを検討した．1) 本研究では，極めて大規模な重み付き部分Max-SAT問題を分散環境で解くためのプロトコルである分散ラグランジュ緩和プロトコルの改良版「分散ラグランジュ緩和プロトコルのためのバンドル法」に対する数値実験を大幅に増強し，極めて大規模な問題例に対して，分散環境特有の情報遅れが発生してもシステム全体の性能には影響を及ぼさないことを実験的に明らかにした．この研究成果を人工知能学会論文誌において発表した．2) 本研究では，まずMulti-MaxSATという既存のソルバーに着目した．このソルバーは，原問題を部分問題に分解し，各部分問題の最適値および最適解を厳密解法によって繰り返し求めることによって，原問題の最適値および最適解を探索する．新しいアルゴリズムでは，部分問題の求解に非厳密解法を用いることで大幅に計算コストを低減させると共に，半ラグランジュ緩和法を用いて極めて最適値に近い値を導出できることを実験的に明らかにした．この成果を2015年度人工知能学会全国大会（第29回）で発表した．3) 分散Max-SAT問題に対する相関均衡点を利用したセキュアな意思決定について検討した．本研究ではブラックボックスリダクションアルゴリズムに基づくアルゴリズムを提案し，その理論的な解析を行った．この研究成果は，2016年度人工知能学会全国大会（第30回）において発表予定である．

在这项研究中，我们开发了两种算法来解决超大规模加权部分 Max-SAT 问题：1）一种在分布式环境中解决这些问题的算法；2）一种在集中式环境中解决这些问题的算法。此外，3）我们研究了一种在确保隐私的安全分布式环境中解决问题的协议。 1）在这项研究中，我们对“分布式拉格朗日松弛协议的捆绑方法”进行了广泛的数值实验，这是分布式拉格朗日松弛协议的改进版本，它是一种解决超大规模加权部分Max-SAT的协议我们通过实验证明，即使出现分布式环境中典型的信息延迟，对于超大规模的问题示例，整个系统的性能也不会受到影响。这项研究的结果发表在日本人工智能学会杂志上。 2) 在这项研究中，我们首先关注一个名为 Multi-MaxSAT 的现有求解器。该求解器通过将原问题分解为子问题，并使用精确求解方法重复寻找每个子问题的最优值和解，来搜索原问题的最优值和解。新算法采用非精确求解方法来求解子问题，显着降低了计算成本，并通过实验证明使用半拉格朗日松弛方法可以得出极其接近最优值的值。这些成果已在 2015 年日本人工智能学会全国会议（第 29 届）上发表。 3）我们研究了使用相关平衡点来解决分布式 Max-SAT 问题的安全决策。在本研究中，我们提出了一种基于黑盒约简算法的算法并进行了理论分析。这项研究的结果预计将在2016年日本人工智能学会全国会议（第30届）上公布。