Automatic logic-based benders decomposition with minizinc

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

3 Citations (Scopus)

Abstract

Logic-based Benders decomposition (LBBD) is a powerful hybrid optimisation technique that can combine the strong dual bounds of mixed integer programming (MIP) with the combinatorial search strengths of constraint programming (CP). A major drawback of LBBD is that it is a far more involved process to implement an LBBD solution to a problem than the "model-and-run" approach provided by both CP and MIP. We propose an automated approach that accepts an arbitrary MiniZinc model and solves it using LBBD with no additional intervention on the part of the modeller. The design of this approach also reveals an interesting duality between LBBD and large neighborhood search (LNS). We compare our implementation of this approach to CP and MIP solvers on 4 different problem classes where LBBD has been applied before.

Original languageEnglish
Title of host publicationProceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)
Subtitle of host publicationSan Francisco, California, USA — February 04 - 09, 2017
EditorsSatinder Singh, Shaul Markovitch
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages787-793
Number of pages7
ISBN (Electronic)9781577357810
Publication statusPublished - 2017
Externally publishedYes
EventAAAI Conference on Artificial Intelligence 2017 - Hilton San Francisco Union Square, San Francisco, United States of America
Duration: 4 Feb 201710 Feb 2017
Conference number: 31st
http://www.aaai.org/Conferences/AAAI/aaai17.php

Conference

ConferenceAAAI Conference on Artificial Intelligence 2017
Abbreviated titleAAAI 2017
CountryUnited States of America
CitySan Francisco
Period4/02/1710/02/17
Internet address

Cite this

Davies, T. O., Gange, G., & Stuckey, P. J. (2017). Automatic logic-based benders decomposition with minizinc. In S. Singh, & S. Markovitch (Eds.), Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17): San Francisco, California, USA — February 04 - 09, 2017 (pp. 787-793). [1642] Association for the Advancement of Artificial Intelligence (AAAI). https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14489