×

zbMATH — the first resource for mathematics

A constraint-based local search backend for MiniZinc. (English) Zbl 1325.90076
Summary: MiniZinc is a modelling language for combinatorial problems, which can then be solved by a solver provided in a backend. There are many backends, based on technologies such as constraint programming, integer programming, or Boolean satisfiability solving. However, to the best of our knowledge, there is currently no constraint-based local search (CBLS) backend. We discuss the challenges to develop such a backend and give an overview of the design of a CBLS backend for MiniZinc. Experimental results show that for some MiniZinc models, our CBLS backend, based on the OscaR/CBLS solver, is able to give good-quality results in competitive time.

MSC:
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T, SCIP: solving constraint integer programs, Mathematical Programming Computation, 1, 1-41, (2009) · Zbl 1171.90476
[2] Akgün, O., Frisch, A.M., Gent, I.P., Hussain, B.S., Jefferson, C., Kotthoff, L., Miguel, I., & Nightingale, P. (2013). Automated symmetry breaking and model selection in CONJURE. In C. Schulte (Ed.) CP 2013, LNCS, (Vol. 8124 pp. 107-116): Springer. · Zbl 1231.90318
[3] Amadini, R; Gabbrielli, M; Mauro, J, Sunny: a lazy portfolio approach for constraint solving, Theory and Practice of Logic Programming, 14, 509-524, (2014) · Zbl 1307.68077
[4] Beldiceanu, N; Carlsson, M; Demassey, S; Petit, T, Global constraint catalogue: past, present, and future, Constraints, 12, 21-62, (2007) · Zbl 1128.68092
[5] Benoist, T; Estellon, B; Gardi, F; Megel, R; Nouioua, K, Localsolver 1.x: a black-box local-search solver for 0-1 programming. 4OR, A Quarterly Journal of Operations Research, 9, 299-316, (2011) · Zbl 1231.90318
[6] Björdal, G. (2014). The first constraint-based local search backend for MiniZinc. Bachelor Thesis in Computer Science, Report IT 14 066, Faculty of Science and Technology, Uppsala University, Sweden. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-234847. · Zbl 1171.90476
[7] Bofill, M., Palahí, M., Suy, J., & Villaret, M. fzn2smt, a compiler from the FlatZinc language to the standard SMT-LIB language. http://ima.udg.edu/Recerca/lap/fzn2smt/.
[8] Codognet, P., & Diaz, D. (2001). Yet another local search method for constraint solving. In K. Steinhöfel (Ed.) SAGA 2001, First International Symposium on Stochastic Algorithms: Foundations and Applications, LNCS, (Vol. 2264 pp. 73-90): Springer. · Zbl 1054.68646
[9] De Landtsheer, R. (2012). Oscar.cbls: a constraint-based local search engine. https://bitbucket.org/oscarlib/oscar/downloads/Oscar.cbls.pdf.
[10] Dotú, I., & Van Hentenryck, P. (2005). Scheduling social golfers locally. In R. Barták, & M. Milano (Eds.) CP-AI-OR 2005, LNCS, (Vol. 3524 pp. 155-167): Springer. · Zbl 1133.90336
[11] Elsayed, S.A.M., & Michel, L. (2011). Synthesis of search algorithms from high-level CP models. In J. Lee (Ed.) CP 2011, LNCS, (Vol. 6876 pp. 256-270): Springer.
[12] Feydy, T., Somogyi, Z., & Stuckey, P. (2011). Half-reification and flattening. In J. Lee (Ed.) CP 2011, LNCS, (Vol. 6876 pp. 286-301): Springer.
[13] Fontaine, D., Michel, L., & Van Hentenryck, P. (2013). Model combinators for hybrid optimization. In C. Schulte (Ed.) CP 2013, LNCS, (Vol. 8124 pp. 299-314): Springer. · Zbl 1226.90047
[14] Frisch, A.M., Grum, M., Jefferson, C., Martinez Hernandez, B., & Miguel, I. (2007). The design of ESSENCE: A constraint language for specifying combinatorial problems. In M. Veloso (Ed.), IJCAI 2007 (pp. 80-87). AAAI Press.
[15] Fujiwara, T. (2014). iZ based solver for MiniZinc Challenge. http://www.minizinc.org/challenge2014/description_izplus.txt.
[16] Gecode Team. Gecode/FlatZinc. http://www.gecode.org/flatzinc.html.
[17] Glover, F. (1989). Tabu Search Part I. ORSA Journal on Computing, \(1\)(3), 190-206. · Zbl 0753.90054
[18] Y. Hamadi, E. Monfroy, & F. Saubion (Eds.) (2012). Autonomous Search: Springer.
[19] He, J., Flener, P., & Pearson, J. (2012). Solution neighbourhoods for constraint-directed local search. In S. Bistarelli, E. Monfroy, & B. O’Sullivan (Eds.) SAC/CSP 2012. (pp. 74-79): ACM Press.
[20] Hoos, H.H. (2012). Automated algorithm configuration and parameter tuning. In Y. Hamadi, E. Monfroy, & F. Saubion (Eds.) Autonomous Search. (pp. 37-71): Springer. · Zbl 1128.68092
[21] Hoos, H.H., & Stützle, T. (2004). Stochastic Local Search: Foundations & Applications: Elsevier/Morgan Kaufmann. · Zbl 1126.68032
[22] Karp, R.M. (1972). Reducibility among combinatorial problems. In R.E. Miller, & J.W. Thatcher (Eds.) Complexity of Computer Computations. (pp. 85-103): Plenum Press.
[23] Monette, J.N., Deville, Y., & Van Hentenryck, P. (2009). Aeon: Synthesizing scheduling algorithms from high-level models. In J.W. Chinneck, B. Kristjansson, & M.J. Saltzman (Eds.) Operations Research and Cyber-Infrastructure, Operations Research/Computer Science Interfaces, (Vol. 47 pp. 43-59): Springer. · Zbl 1307.68077
[24] Nethercote, N. Converting MiniZinc to FlatZinc. http://www.minizinc.org/downloads/doc-1.6/mzn2fzn.pdf .
[25] Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., & Tack, G. (2007). MiniZinc: Towards a standard CP modelling language. In C. Bessière (Ed.), CP 2007, LNCS (Vol. 4741, pp. 529-543). Springer. http://www.minizinc.org/.
[26] Newton, M.H., Pham, D.N., Sattar, A., & Maher, M. (2011). Kangaroo: An efficient constraint-based local search system using lazy propagation. In J. Lee (Ed.) CP 2011, LNCS, (Vol. 6876 pp. 645-659): Springer.
[27] Nightingale, P., Akgün, O., Gent, I.P., Jefferson, C., & Miguel, I. (2014). Automatically improving constraint models in Savile Row through associative-commutative common subexpression elimination. In B. O’Sullivan (Ed.) CP 2014, LNCS, (Vol. 8656 pp. 590-605): Springer. · Zbl 1419.68099
[28] Nowicki, E; Smutnicki, C, A fast taboo search algorithm for the job shop problem, Management Science, 42, 797-813, (1996) · Zbl 0880.90079
[29] Opturion Pty Ltd. Opturion CPX. http://www.opturion.com/cpx.
[30] OR Team at Google. OR-Tools. https://code.google.com/p/or-tools/.
[31] OscaR Team (2012). OscaR: Scala in OR. https://bitbucket.org/oscarlib/oscar.
[32] Parr, T.J. (2007). The Definitive ANTLR Reference: Building Domain-Specific Languages: The Pragmatic Bookshelf.
[33] Prestwich, S.D. (2002). Supersymmetric modeling for local search. In P. Flener, & J. Pearson (Eds.) SymCon 2002. http://www.it.uu.se/research/group/astra/SymCon02. · Zbl 1013.90104
[34] Stuckey, PJ; Becket, R; Fischer, J, Philosophy of the minizinc challenge, Constraints, 15, 307-316, (2010) · Zbl 1208.68207
[35] Stuckey, PJ; Feydy, T; Schutt, A; Tack, G; Fischer, J, The minizinc challenge 2008-2013, AI Magazine, 35, 55-60, (2014)
[36] Van Hentenryck, P. (1999). The OPL Optimization Programming Language: The MIT Press. · Zbl 0880.90079
[37] Van Hentenryck, P., & Michel, L. (2003) In F. Rossi (Ed.), Control abstractions for local search (Vol. 2833, pp. 65-80): Springer.
[38] Van Hentenryck, P., & Michel, L. (2004). Scheduling abstractions for local search. In J.C. Régin, & M. Rueher (Eds.) CP-AI-OR 2004, LNCS, (Vol. 3011 pp. 319-334): Springer. · Zbl 1094.90565
[39] Van Hentenryck, P., & Michel, L. (2007). Synthesis of constraint-based local search algorithms from high-level models. In A. Howe, & R.C. Holte (Eds.) AAAI 2007. (pp. 273-278): AAAI Press.
[40] Van Hentenryck, P., & Michel, L. (2009). Constraint-Based Local Search: The MIT Press. · Zbl 1179.68141
[41] Van Hentenryck, P., Michel, L., & Liu, L. (2004). Constraint-based combinators for local search. In M. Wallace (Ed.) CP 2004, LNCS, (Vol. 3258 pp. 47-61): Springer. · Zbl 1152.68589
[42] Yunes, TH; Aron, ID; Hooker, JN, An integrated solver for optimization problems, Operations Research, 58, 342-356, (2010) · Zbl 1226.90047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.