Optimising Discrete Problems
Decision Diagrams and Context-Aware Heuristics
E. Eigbe (TU Delft - Algorithmics)
N. Yorke-Smith – Promotor (TU Delft - Algorithmics)
B. De Schutter – Promotor (TU Delft - Delft Center for Systems and Control)
M. Nasri Nasrabadi – Copromotor
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Optimisation problems are all around us and play a critical role in the outcomes of various sectors of society including scheduling, logistics, network design, and resource allocation. In this thesis, we look at a subset of problems where some or all the choices to be made can only take on values belonging to a discrete set of values – a limitation which increases the difficulty of finding a solution in most cases. We handle this thesis in two parts: first zooming in on a particular class of problems – scheduling – and then on a particular solution method – decision diagrams.
In Part I of this dissertation, we consider the problem of scheduling in manufacturing systems. This popular discrete optimisation problem has been studied extensively; however, advancements in modern manufacturing systems present new challenges and opportunities. A major driver of the changes in manufacturing systems is the integration of the physical processes with computation, networking, and automated control capabilities. Thus, the domain of activities that can directly be decided upon and actuated from software has expanded. We look at one such activity in Chapter 3 namely,
sequence-dependent maintenance and propose solution methods that directly integrate maintenance and production planning.
Part II of this thesis looks into decision diagrams as a solution method for discrete optimisation problems. Decision diagrams have existed since the 1950s and were originally introduced as a means to represent boolean functions. Since then they have been used in different fields such as in circuit verification, knowledge representation, and most recently, operations research. While decision diagrams have already been shown to be very promising methods for solving optimisation problems, we push the field forward as follows. In Chapter 5, we propose a decision diagram model for the kind of scheduling problems tackled in Part I of this thesis. We further perform a comparative study of the consequences of heuristic decisions made during the decision diagram compilation process in Chapter 6 and integrate reinforcement learning with decision-diagram-based branch-and-bound in Chapter 7. In Chapter 8 we go further into considering uncertainty in optimisation problems. We focus on the paradigm of finding the best solution while accepting some level of risk, i.e., chance constrained optimisation and present a chance constrained decision diagram formulation. We further provide theoretical guarantees for instances with normally distributed variables.
The contributions of this thesis cover different aspects of solving discrete optimisation problems with a focus on scheduling and logistic applications. The hope is that these advances further the adoption of state of the art research in solving optimisation problems in real-world contexts.