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

开发用于超大规模加权部分 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回）において発表予定である．

在这项研究中，我们开发了两种算法：1）一种算法，该算法在分布式环境中解决了极大的加权部分最大 - SAT问题，以及2）一种在集中环境中解决它们的算法。 3）我们还检查了一个协议，以在具有隐私的安全，分布式环境中解决该问题。 1）在这项研究中，我们大大提高了“分布式拉格朗日放松方案的捆绑方法”的数值实验，这是一种改进的分布式拉格朗日放松方案的改进版本，该协议是解决分布式环境中极为大的加权部分最大 - SAT问题的协议，即使信息延迟了巨大的效果，它也会影响到较大的效果。这一研究发现发表在《人工智能学会杂志》上。 2）在这项研究中，我们首先专注于一个称为Multi-Maxsat的现有求解器。该求解器将原始问题分解为子问题，并通过使用严格的解决方案方法反复找到每个子问题的最佳值和最佳解决方案，以寻找原始问题的最佳值和最佳解决方案。新的算法在实验上表明，使用非脱颖而出的解决方案来解决子问题可显着降低计算成本，并且使用半拉格朗日释放方法可以得出非常接近最佳值的值。这些结果是在2015年人工智能学会全国会议上提出的（第29届）。 3）我们使用相关均衡点针对方差最大-SAT问题研究了安全决策。在这项研究中，提出了基于黑匣子还原算法的算法，并进行了理论分析。这项研究的结果计划在2016年人工智能学会全国会议上介绍（第30届）。