============================================================ iZplus (fzn_izplus) -- iZ based solver for MiniZinc Challenge 2015 -- Copyright (C) 2015 NTT DATA SEKISUI SYSTEMS CORPORATION. ============================================================ * What is fzn_izplus fzn_izplus is a FlatZinc solver using iZ-C constraint programming library which is developed by NTT DATA SEKISUI SYSTEMS CORPORATION. iZ-C provides : * many built-in constraints * constraint propagation mechanism * simple search strategy And in fzn_izplus, following algorithms are 'plus'ed. * Randomized restarting in search For fast random number generation, Xorshift128 algorithm is used. http://www.jstatsoft.org/v08/i14/paper Restart strategy is geometirc, but counter will be rewinded periodically like Luby strategy. * Local search for optimization problem In real world problems, sometimes finding 'good' solution using short time is more important than finding 'best' solution using long time. And it is known empirically that 'good' solutions are similar to each other, then local search can be a good strategy. For optimization problem, fzn_izplus tries to find first solution using constraint propagation and search. After one solution was found, it searches similar solutions better than first one. * Local search for satisfying problem fzn_izplus tries to maxmize count of assinged variables without conflict. (Local solution will be relaxed after limited restarting) * Variable reordering Failures occured while searching are recorded and variable selection order is changed using this information. Domain size and weighted constraint count are also used. * NG learning NG learning is implemented as described in: http://ijcai.org/papers07/Papers/IJCAI07-019.pdf (To keep NG set small, inactive NGs are removed from learnt set.) * Author Toshimitsu FUJIWARA developer at NTT DATA SEKISUI SYSTEMS CORPORATION * Acknowledgement FlatZinc parser in fzn_izplus is based on 'FlatZinc parser skeleton' written by Guido Tack. http://www.gecode.org/flatzinc.html/ Please refer to header files in flatzinc_skeleton-1.3.zip About its copyright and license. (It's contained in this archive.) Special thanks to Guido Tack and Gecode team. iZ-C is a constraint programming library developed by NTT DATA SEKISUI SYSTEMS CORPORATION. http://www.constraint.org/ja/izc_download.html (Sorry, above web page is NOT written in English.)