Portfolio Approaches in Constraint Programming

Roberto Amadini 1, 2
1 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : Recent research has shown that the performance of a single, arbitrarily efficient algorithm can be significantly outperformed by using a portfolio of —possibly on-average slower— algorithms. Within the Constraint Programming (CP) context, a portfolio solver can be seen as a particular constraint solver that exploits the synergy between the constituent solvers of its portfolio for predicting which is (or which are) the best solver(s) to run for solving a new, unseen instance. In this thesis we examine the benefits of portfolio solvers in CP. Despite portfolio approaches have been extensively studied for Boolean Satisfiability (SAT) problems, in the more general CP field these techniques have been only marginally studied and used. We conducted this work through the investigation, the analysis and the construction of several portfolio approaches for solving both satisfaction and optimization problems. We focused in particular on sequential approaches, i.e., single-threaded portfolio solvers always running on the same core. We started from a first empirical evaluation on portfolio approaches for solving Constraint Satisfaction Problems (CSPs), and then we improved on it by introducing new data, solvers, features, algorithms, and tools. Afterwards, we addressed the more general Constraint Optimization Problems (COPs) by implementing and testing a number of models for dealing with COP portfolio solvers. Finally, we have come full circle by developing sunny-cp: a sequential CP portfolio solver that turned out to be competitive also in the MiniZinc Challenge, the reference competition for CP solvers.
Document type :
Theses
Complete list of metadatas

Cited literature [168 references]  Display  Hide  Download

https://hal.inria.fr/tel-01227582
Contributor : Amadini Roberto <>
Submitted on : Wednesday, November 11, 2015 - 4:10:47 PM
Last modification on : Wednesday, October 10, 2018 - 10:09:14 AM
Long-term archiving on : Friday, April 28, 2017 - 5:12:51 AM

Identifiers

  • HAL Id : tel-01227582, version 1

Collections

Citation

Roberto Amadini. Portfolio Approaches in Constraint Programming. Computer Science [cs]. University of Bologna, 2015. English. ⟨tel-01227582⟩

Share

Metrics

Record views

421

Files downloads

491