Discrete optimization with decision diagrams : design of a generic solver, improved bounding techniques, and discovery of good feasible solutions with large neighborhood search
(2022)
Files
these_xavier_gillard.pdf
Open Access - Adobe PDF
- 2.4 MB
Details
- Authors
- Supervisors
- Schaus, Pierre
- Abstract
- Dynamic Programming (DP) is a popular tool to solve combinatorial problems. This paradigm is ubiquitous and at the heart of many of the classic algorithms taught to every computer science student around the world. For instance, Dijkstra's shortest path algorithm is a case of DP. Still, when DP is used to solve NP-hard problems, it faces one major pitfall: the algorithm might not only require an exponential time but an exponential amount of memory as well -- which severely hampers its applicability. In 2016, a novel method combining DP with Decision Diagrams (DD) in a branch-and-bound framework was proposed. The strength of that approach stems from the ease of modeling leveraged from DP and the memory efficiency of the DD data structure. The latter is a graphical model providing an efficient encoding for exponentially sized sets of solutions to a given problem and allows the identification of an optimal solution in linear time. This thesis investigates the implementation and the trade-offs to make to benefit the most from this new technology. It also proposes algorithmic improvements to boost the performance of DD-based optimization solvers. It presents techniques to strengthen the bounds derived from each compiled DD and investigates ways to blend them with other resolution techniques such as Large Neighborhood Search (LNS) or approximate DP to swiftly find good solutions to a given problem.
- Affiliations
Citations
Gillard, X. (2022). Discrete optimization with decision diagrams : design of a generic solver, improved bounding techniques, and discovery of good feasible solutions with large neighborhood search. https://hdl.handle.net/2078.5/101412