Loading...Loading...

Discrete optimization with decision diagrams

Coppé, Vianney

(2019)

Details

Supervisors

Schaus, Pierre

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en informatique

Abstract

Discrete optimization problems are everywhere nowadays, from delivery routes planning and flight crews scheduling to choosing the location of a new set of warehouses. Although mathematical programming or constraint programming solvers are very successful for a wide range of these problems, others involve cost functions and constraints which are difficult to formulate with traditional techniques, or contain a combinatorial structure that these techniques currently do not benefit from. This thesis explores a new general-purpose optimization method based on decision diagrams featuring an original modeling approach, a procedure providing tight bounds to the objective function and an adapted branch-and-bound algorithm. Several well-known problems have been successfully modeled with this technique and we will try to apply it to a new problem : the minimum linear arrangement problem (MinLA). This problem has many applications including error-correcting codes, wire length minimization in VLSI design and single machine job scheduling. We present a new formulation for the MinLA using decision diagrams and show that it solves instances with 10 to 20 vertices under 1 hour and outperforms a recent linear programming model. The second objective of this thesis is to build a generic solver for discrete optimization with decision diagrams. We provide a Java library allowing to solve new problems with simple and limited amount of code given a correct decision diagram formulation. We give an overview of the implementation as well as a brief example of how to use the library.