Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

A constraint-based local search backend for MiniZinc

  • Published:
Constraints Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Achterberg, T. (2009). SCIP: Solving constraint integer programs. Mathematical Programming Computation, 1(1), 1–41.

    Article  MATH  MathSciNet  Google Scholar 

  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.

  3. Amadini, R., Gabbrielli, M., & Mauro, J. (2014). Sunny: a lazy portfolio approach for constraint solving. Theory and Practice of Logic Programming, 14, 509–524.

    Article  MATH  Google Scholar 

  4. Beldiceanu, N., Carlsson, M., Demassey, S., & Petit, T. (2007). Global constraint catalogue: Past, present, and future. Constraints, 12(1), 21–62. The catalogue is at http://sofdem.github.io/gccat.

    Article  MATH  MathSciNet  Google Scholar 

  5. Benoist, T., Estellon, B., Gardi, F., Megel, R., & Nouioua, K. (2011). LocalSolver 1.x: a black-box local-search solver for 0-1 programming. 4OR. A Quarterly Journal of Operations Research, 9(3), 299–316.

    MATH  MathSciNet  Google Scholar 

  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.

  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.

  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.

  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.

  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.

  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.

  21. Hoos, H.H., & Stützle, T. (2004). Stochastic Local Search: Foundations & Applications: Elsevier/Morgan Kaufmann.

  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.

  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.

  28. Nowicki, E., & Smutnicki, C. (1996). A fast taboo search algorithm for the job shop problem. Management Science, 42(6), 797–813.

    Article  MATH  Google Scholar 

  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.

  34. Stuckey, P.J., Becket, R., & Fischer, J. (2010). Philosophy of the MiniZinc challenge. Constraints, 15(3), 307–316.

    Article  MATH  Google Scholar 

  35. Stuckey, P.J., Feydy, T., Schutt, A., Tack, G., & Fischer, J. (2014). The MiniZinc challenge 2008–2013. AI Magazine, 35(2), 55–60.

    Google Scholar 

  36. Van Hentenryck, P. (1999). The OPL Optimization Programming Language: The MIT Press.

  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.

  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.

  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.

  42. Yunes, T.H., Aron, I.D., & Hooker, J.N. (2010). An integrated solver for optimization problems. Operations Research, 58(2), 342–356.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Information Technology, Uppsala University, 751 05, Uppsala, Sweden

    Gustav Björdal, Jean-Noël Monette, Pierre Flener & Justin Pearson

Authors
  1. Gustav Björdal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jean-Noël Monette
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pierre Flener
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Justin Pearson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jean-Noël Monette.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Björdal, G., Monette, JN., Flener, P. et al. A constraint-based local search backend for MiniZinc. Constraints 20, 325–345 (2015). https://doi.org/10.1007/s10601-015-9184-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10601-015-9184-z

Keywords

Search

Navigation