SC2からSC3への変換サービス

SC3のリリースは、遅れに遅れて8月を予定しています。SC2プロジェクトは、曜日定義の若干の変更及び、言語制約をPythonベースに変更、メインソルバの変更により、変更が必要となる場合は、多いと思います。お手持ちのSC2プロジェクトは、お送りくださればSC3プロジェクトに変更して返信します。

→早速送って頂きました。送って頂いた方々へは、最新ソルバーと変換プロジェクトをセットにして、OneDriveにてご案内します。

INRC–II 4Weeks Updated Results

This article deals with the nurse scheduling problem as described in the context of the international
competition INRC–II.The experimental tests focus on a benchmark of twenty instances published during the INRC–II.The instances describe the constraints for the schedule of 30 to 120 nurses over 4 weeks horizon. Table below shows the result obtained by my developping solver.
Significant improvements can be observed compared to staticnurseschduler. The verified data will be published in Github,which includes mps format for such as cplex/gurobi and wcnf(dimacs) format.

	Known Best			New Solver
	LB	UB	UB-LB/LB	LB	UB	UB-LB/LB
n030w4 1 6-2-9-1	1615	1685	4.2%	1660	1670	0.6%
n030w4 1 6-7-5-3	1740	1840	5.4%	1810	1815	0.3%
n035w4 0 1-7-1-8	1250	1415	11.7%	1338	1360	1.6%
n035w4 2 8-8-7-5	1045	1145	8.7%	1080	1080	0.0%
n040w4 0 2-0-6-1	1335	1640	18.6%	1536	1570	2.2%
n040w4 2 6-1-0-6	1570	1865	15.8%	1742	1750	0.5%
n050w4 0 0-4-8-7	1195	1445	17.3%	1296	1320	1.8%
n050w4 0 7-2-7-2	1200	1405	14.6%	1303	1315	0.9%
n060w4 1 6-1-1-5	2380	2465	3.4%	2435	2450	0.6%
n060w4 1 9-6-3-8	2615	2730	4.2%	2665	2675	0.4%
n070w4 0 3-6-5-1	2280	2430	6.2%	2371	2380	0.4%
n070w4 0 4-9-6-7	1990	2125	6.4%	2105	2115	0.5%
n080w4 2 4-3-3-3	3140	3320	5.4%	3292	3300	0.2%
n080w4 2 6-0-4-8	3045	3240	6.0%	3178	3190	0.4%
n100w4 0 1-1-0-8	1055	1230	14.2%	1168	1175	0.6%
n100w4 2 0-6-4-6	1470	1855	20.8%	1790	1790	0.0%
n110w4 0 1-4-2-8	2210	2390	7.5%	2322	2330	0.3%
n110w4 0 1-9-3-5	2255	2525	10.7%	2455	2455	0.0%
n120w4 1 4-6-2-6	1790	2165	17.3%	2032	2040	0.4%
n120w4 1 5-6-9-8	1820	2220	18.0%

UltimateSolver

SC3は、複数種類のソルバを搭載しますが、どのソルバがどの系統の問題に有効かというのは、大体分かっています。しかし、どれが最適かというのは、新しい初めての問題の場合は、正直言って分かりません。そこで、全種類のソルバを一遍に走らせて、その時点の最も良い解を出せば、なにも考えずにすみます。これは、SATソルバのVirtualSolver的発想です。

SATソルバの場合は、ほぼ、同じ系統のソルバを違うパラメータで走らせるポートフォリオ戦略なのですが、ここで考えているのは、

■SAT　BASED
■UNSAT　BASED
■Meta heuristics　（Simulated Annealing)
■Numerical　Solver

です。それぞれ全く異なる性質を持つソルバですので、見かけ上の性能が良く見えるはずです。
上の4つをマルチスレッドで走らせて、その時点の最も良い解をレポートすればよいだけです。


例えば、池上先生のベンチマークは、UNSATベースで数秒で解けますが、世界に名だたるMIPソルバ、Cplexや、Gurobiでも10分程度かかります。実は、この例の方が特殊で、NurseSchedulingの場合、UNSATベースだと殆ど解けません。MIPの方がよく解けます。SATとUNSATでは、大体SATの方が良く解けます。しかし、逆の場合もあります。要は、やってみないと何が良いか分からないというのが本質的な問題です。

UltimateSolverがあれば、一挙にこの問題は解決ということになります。
問題は、それだけのソルバを揃える技術力と工数です。残念ながらSC3は、今、SATBaseの改善に全力で取り組んでいて、そこまで揃えるのは、先になります。もっと進んだ発想はそれをクラウド化
することです。こちらもAWSを視野に準備しようと思います。AWS化でご協力頂けるエンジニアの方がおられましたら、ご連絡ください。