2019年6月29日土曜日

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

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

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

2019年6月27日木曜日

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 BestNew Solver
LBUBUB-LB/LBLBUBUB-LB/LB
n030w4 1 6-2-9-1161516854.2%166016700.6%
n030w4 1 6-7-5-3174018405.4%181018150.3%
n035w4 0 1-7-1-81250141511.7%133813601.6%
n035w4 2 8-8-7-5104511458.7%108010800.0%
n040w4 0 2-0-6-11335164018.6%153615702.2%
n040w4 2 6-1-0-61570186515.8%174217500.5%
n050w4 0 0-4-8-71195144517.3%129613201.8%
n050w4 0 7-2-7-21200140514.6%130313150.9%
n060w4 1 6-1-1-5238024653.4%243524500.6%
n060w4 1 9-6-3-8261527304.2%266526750.4%
n070w4 0 3-6-5-1228024306.2%237123800.4%
n070w4 0 4-9-6-7199021256.4%210521150.5%
n080w4 2 4-3-3-3314033205.4%329233000.2%
n080w4 2 6-0-4-8304532406.0%317831900.4%
n100w4 0 1-1-0-81055123014.2%116811750.6%
n100w4 2 0-6-4-61470185520.8%179017900.0%
n110w4 0 1-4-2-8221023907.5%232223300.3%
n110w4 0 1-9-3-52255252510.7%245524550.0%
n120w4 1 4-6-2-61790216517.3%203220400.4%
n120w4 1 5-6-9-81820222018.0%   

2019年6月1日土曜日

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化でご協力頂けるエンジニアの方がおられましたら、ご連絡ください。