2017年11月5日日曜日

論文読み:Enriching Solutions to Combinatorial Problems via Solution Engineering

11月の optimization online の更新が来ていたので、いくつかを論文読みをしてみた。
そのうちの一つが

Enriching Solutions to Combinatorial Problems via Solution Engineering
http://www.optimization-online.org/DB_HTML/2017/10/6252.html

簡単にいうと、組合せ最適化問題では同じ最適値を達成するような最適解が大量にある場合があって、そのようなときに大量の最適解から特徴的な最適解をどのように取り出すか、という話。

ざっくりと手法をまとめると、多様性を表すような目的関数を作って、別の最適化問題を解いている。
また、既に得られている最適解を切除平面で外すことで別の最適解を得たりしている。

個人的に思うに、「特徴的な解」に含まれる「特徴的な」の部分をどのように数学的に表すかは様々な方法があるから、割り当て問題などでの現実的なサイズになるとどうなるか、というあたりが結構大変そう、と思ったりする。

0 件のコメント:

コメントを投稿