Multi-pass high-level presolving

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

    Abstract

    Presolving is a preprocessing step performed by optimisation solvers to improve performance. However, these solvers cannot easily exploit high-level model structure as available in modelling languages such as MiniZinc or Essence. We present an integrated approach that performs presolving as a separate pass during the compilation from high-level optimisation models to solverlevel programs. The compiler produces a representation of the model that is suitable for presolving by retaining some of the high-level structure. It then uses information learned during presolving to generate the final solver-level representation. Our approach introduces the novel concept of variable paths that identify variables which are common across multiple compilation passes, increasing the amount of shared information. We show that this approach can lead to both faster compilation and more efficient solver-level programs.
    Original languageEnglish
    Title of host publicationProceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)
    Subtitle of host publicationBuenos Aires, Argentina, 25-31 July 2015
    EditorsQiang Yang
    Place of PublicationPalo Alto CA USA
    PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
    Pages346-352
    Number of pages7
    ISBN (Print)9781577357384
    Publication statusPublished - 2015
    EventInternational Joint Conference on Artificial Intelligence 2015 - Buenos Aires, Argentina
    Duration: 25 Jul 20151 Aug 2015
    Conference number: 24th
    https://www.ijcai-15.org/index.php?option=com_content&view=article&id=71:call-for-papers&catid=9:uncategorised&Itemid=477

    Conference

    ConferenceInternational Joint Conference on Artificial Intelligence 2015
    Abbreviated titleIJCAI 2015
    CountryArgentina
    CityBuenos Aires
    Period25/07/151/08/15
    Internet address

    Cite this

    Leo, K., & Tack, G. (2015). Multi-pass high-level presolving. In Q. Yang (Ed.), Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015): Buenos Aires, Argentina, 25-31 July 2015 (pp. 346-352). Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI).
    Leo, Kevin ; Tack, Guido. / Multi-pass high-level presolving. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015): Buenos Aires, Argentina, 25-31 July 2015. editor / Qiang Yang. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2015. pp. 346-352
    @inproceedings{7f673dc5868d42cdad1eab526ea9b448,
    title = "Multi-pass high-level presolving",
    abstract = "Presolving is a preprocessing step performed by optimisation solvers to improve performance. However, these solvers cannot easily exploit high-level model structure as available in modelling languages such as MiniZinc or Essence. We present an integrated approach that performs presolving as a separate pass during the compilation from high-level optimisation models to solverlevel programs. The compiler produces a representation of the model that is suitable for presolving by retaining some of the high-level structure. It then uses information learned during presolving to generate the final solver-level representation. Our approach introduces the novel concept of variable paths that identify variables which are common across multiple compilation passes, increasing the amount of shared information. We show that this approach can lead to both faster compilation and more efficient solver-level programs.",
    author = "Kevin Leo and Guido Tack",
    year = "2015",
    language = "English",
    isbn = "9781577357384",
    pages = "346--352",
    editor = "Qiang Yang",
    booktitle = "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)",
    publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",
    address = "United States",

    }

    Leo, K & Tack, G 2015, Multi-pass high-level presolving. in Q Yang (ed.), Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015): Buenos Aires, Argentina, 25-31 July 2015. Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 346-352, International Joint Conference on Artificial Intelligence 2015, Buenos Aires, Argentina, 25/07/15.

    Multi-pass high-level presolving. / Leo, Kevin; Tack, Guido.

    Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015): Buenos Aires, Argentina, 25-31 July 2015. ed. / Qiang Yang. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2015. p. 346-352.

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

    TY - GEN

    T1 - Multi-pass high-level presolving

    AU - Leo, Kevin

    AU - Tack, Guido

    PY - 2015

    Y1 - 2015

    N2 - Presolving is a preprocessing step performed by optimisation solvers to improve performance. However, these solvers cannot easily exploit high-level model structure as available in modelling languages such as MiniZinc or Essence. We present an integrated approach that performs presolving as a separate pass during the compilation from high-level optimisation models to solverlevel programs. The compiler produces a representation of the model that is suitable for presolving by retaining some of the high-level structure. It then uses information learned during presolving to generate the final solver-level representation. Our approach introduces the novel concept of variable paths that identify variables which are common across multiple compilation passes, increasing the amount of shared information. We show that this approach can lead to both faster compilation and more efficient solver-level programs.

    AB - Presolving is a preprocessing step performed by optimisation solvers to improve performance. However, these solvers cannot easily exploit high-level model structure as available in modelling languages such as MiniZinc or Essence. We present an integrated approach that performs presolving as a separate pass during the compilation from high-level optimisation models to solverlevel programs. The compiler produces a representation of the model that is suitable for presolving by retaining some of the high-level structure. It then uses information learned during presolving to generate the final solver-level representation. Our approach introduces the novel concept of variable paths that identify variables which are common across multiple compilation passes, increasing the amount of shared information. We show that this approach can lead to both faster compilation and more efficient solver-level programs.

    M3 - Conference Paper

    SN - 9781577357384

    SP - 346

    EP - 352

    BT - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)

    A2 - Yang, Qiang

    PB - Association for the Advancement of Artificial Intelligence (AAAI)

    CY - Palo Alto CA USA

    ER -

    Leo K, Tack G. Multi-pass high-level presolving. In Yang Q, editor, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015): Buenos Aires, Argentina, 25-31 July 2015. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2015. p. 346-352