Introducing Pareto Minimal Correction Subsets : MCSがMax-SAT的な最適化問題の近似解と見なせるように、多目的最適化問題のパレート最適解の近似をMCSを使って与えようというような話。
PBO (Pseudo Boolean Optimization) と WBO (Weighted Boolean Optimization) は相互に変換できるが、同様に多目的の組み合わせ最適化問題MOCO (Multi-Objective Combinatorial Optimization) に対して、MOWBO (Multi-Objective Weighted Boolean Optimization) を定義。MOWBOに対するMCSであるMulti-MCSの列挙は通常のMCSの列挙に帰着できるので、普通に列挙して支配されるものを取り除く。
MOCOに対応するMOWBOは、制約に対して重みのベクトルを持たせるのかと思ったら、目的関数毎に制約集合を分けるような形になっていて、ちょっと面白かった。 一方で、Multi-MCSの定義やその通常のMCSへの帰着などは非常に自明な話に思える。
評価では、仮想マシンのサーバへの配置問題を題材に、Guided Improvement Algorithm (GIA) [2] および進化的アルゴリズムと比較。多目的最適化アルゴリズムの性能を比較するのにHV(hyper volume)を用いるのは知らなかったので面白かった。結果としては、GIAよりも良い結果で、また進化的アルゴリズムとの比較では、VMのマイグレーションのbudgetが小さい場合（＝強いハード制約がある場合）に特に優れていたという結果（まあ、そりゃそうよね）。
ちなみに、GIAはAlloyベースのMoolloyというツールで提案されてたのだけれど、今見たらサイトが消えてた…… http://sdg.csail.mit.edu/moolloy/
[1] M. Terra-Neves, I. Lynce, and V. Manquinho, "Introducing pareto minimal correction subsets," in Theory and Applications of Satisfiability Testing – SAT 2017, ser. Lecture Notes in Computer Science, S. Gaspers and T. Walsh, Eds. Springer International Publishing, 2017, vol. 10491, pp. 195-211.
https://link.springer.com/chapter/10.1007/978-3-319-66263-3_13
(9/24まで http://sat2017.gitlab.io/proceedings/ から無料でダウンロード可能)
[2] Derek Rayside, H.-Christian Estler, and Daniel Jackson. A Guided Improvement Algorithm for Exact, General Purpose, Many-Objective Combinatorial Optimization. Technical Report MIT-CSAIL-TR-2009-033, MIT Computer Science and Artificial Intelligence Laboratory, 2009. URL http://hdl.handle.net/1721.1/46322
Introducing Pareto Minimal Correction Subsets
