組合せ最適化の近似解法の設計方針

http://research.nii.ac.jp/~uno/approx.htm

宇野先生のページに載っている通りの解法があります。
目指しているのは、厳密解を目標にしつつ、必要なら途中途中で解を得るような方法です。
　

ナーススケジューリング問題としては、最近シミュレーテッドアニーリングで成果が出ているので、
こちらについても見てみたいのですが、残念ながら上記の要件を満たすことは難しいです。
メタヒューリスティクスでは、高速に近似解を得ることができますが、CPUパワーをそちらに摂られてしまうと、厳密解パワーに廻せなくなってしまいます。極初期に、少しだけ使うのは、意味があると思いますが、厳密解の50%や20%程度の劣化を意識したところでは、かなり難しいと感じています。

　現在は、途中途中でMaxSATソルバを動かしていますが、このままですと、かなり性能が悪く、近似解でも良い解が中々出てきません。具体的には、厳密解近くまで来ないと中々良い解になりません。INRC2の8WEEKSが厳密解近くの解を出すまでには、丸一日程度かかるのですが、それらしい近似解の出力にもあまり変わらない時間であり、今のままだと全く実用的ではありません。
（実は、問題領域をどこにするかで、得意なソルバの種類は違ってきます。今問題にしているのは、INRC2の8WEEKS程度でのお話です。この辺の話も後で。かなり色々な事が分かってきました。）

そこで、上記主旨を踏まえて、MAXSATソルバを新たに設計することにしました。新しい挑戦です。