Multivalued decision diagrams for optimization

Details

Supervisors

Schaus, Pierre

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en informatique

Abstract

Constraint programming is a well known efficient programming paradigm sometimes called smart brute-force. By using a branch and bound algorithm associated with domain propagation, it allows to solve hard combinational problems. One of the strengths is its expressiveness via the constraint modelization. However two major weaknesses of the paradigm are the lack of usage of memory (branch and bound is a simple DFS) and the lack of communication between the involved constraints. The multivalued decision diagram is a structure that allows to represent the search tree in a condensed way. This allows to circumvent the communication problem by increasing the memory usage. With a better communication between constraints, the time used for the propagation decreases and the number of failures in the search tree lowers as well. Multiple types of decision diagrams are presented in this thesis and all of them are implemented in Oscar - a constraint programming framework. The multivalued decision diagram sub-framework is designed to be flexible and allow the addition of new modules and algorithms in it. Most of the decision diagram algorithms are competitive with the corresponding state of the art propagators. Moreover, when multiple constraints are mixed inside the framework, the combination of state of the art methods is outperformed by the associated multivalued decision diagram.