Minisearch: a solver-independent meta-search language for MiniZinc

Andrea Rendl, Tias Guns, Peter James Stuckey, Guido Tack

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    17 Citations (Scopus)

    Abstract

    Much of the power of CP comes from the ability to create complex hybrid search algorithms specific to an application. Unfortunately there is no widely accepted standard for specifying search, and each solver typically requires detailed knowledge in order to build complex searches. This makes the barrier to entry for exploring different search methods quite high. Furthermore, search is a core part of the solver and usually highly optimised. Any imposition on the solver writer to change this part of their system is significant.

    In this paper we investigate how powerful we can make a uniform language for meta-search without placing any burden on the solver writer. The key to this is to only interact with the solver when a solution is found. We present MINISEARCH, a meta-search language that can directly use any FLATZINC solver. Optionally, it can interact with solvers through an efficient C++ API. We illustrate the expressiveness of the language and performance using different solvers on a number of examples.
    Original languageEnglish
    Title of host publication21st International Conference, CP 2015, Proceedings: Principles and Practice of Constraint Programming
    EditorsGilles Pesant
    Place of PublicationCham Switzerland
    PublisherSpringer
    Pages376 - 392
    Number of pages17
    ISBN (Electronic)9783319232195
    ISBN (Print)9783319232188
    DOIs
    Publication statusPublished - 2015
    EventInternational Conference on Principles and Practice of Constraint Programming 2015 - Cork, Ireland
    Duration: 31 Aug 20154 Sep 2015
    Conference number: 21st
    https://web.archive.org/web/20150810094235/http://booleconferences.ucc.ie/cp2015

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume9255
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    ConferenceInternational Conference on Principles and Practice of Constraint Programming 2015
    Abbreviated titleCP 2015
    CountryIreland
    CityCork
    Period31/08/154/09/15
    Internet address

    Keywords

    • Master Problem
    • Global Constraint
    • Capacitate Vehicle Route Problem
    • Search Node
    • Search Combinators

    Cite this