Decomposition-based algorithms for optimization problems

Despite the recent very significant progress concerning algorithms for combinatorial optimization problems, most large instances of NP-Hard problems remain intractable by general solvers, motivating the development of problem-specific (meta)heuristic algorithms. While often resulting in acceptable results, the development of problem-specific algorithms is time-consuming and traditionally very expensive. In response to these shortcomings, this manuscript investigates decomposition-based algorithms as an alternative for addressing combinatorial optimization problems. These algorithms decompose a problem into multiple subproblems so as to efficiently approach it. Generally, such subproblems are much easier to solve than the entire problem, thereby enabling one to address large problems by employing, for example, general solvers.

Decomposition-based algorithms may be categorized as follows: those which optimally solve the original problem and those which address it heuristically with the goal of producing high-quality solutions. Both algorithm classes are addressed within this thesis, whose primary focus concerns decomposition-based heuristic algorithms. However, can these algorithms replace state-of-the-art problem-specific (meta)heuristics? To answer this question, six different problems are investigated throughout this manuscript, ranging from scheduling to logistic problems. All six problems are associated with challenging benchmark instances extensively studied in the literature, which permits a comparison of the developed methods against several other algorithms. Multiple decomposition strategies are investigated, employing the problems' structure, the decisions associated with them or simple strategies seeking to reduce their size. Several decomposition-based algorithms are proposed and thoroughly analyzed, with some of them proven general despite the various individual problem characteristics. A general framework is proposed, successfully addressing not only some of the problems studied throughout the thesis but also an additional one from the literature.

Computational experiments validate the proposed algorithms, which result in several improvements over the state-of-the-art for all six investigated problems. This thesis not only contributes towards various individual problem domains, but also to the future of decomposition-based methodologies. Its findings, combined with the practical advantages of decomposition-based algorithms, culminate in a discussion concerning the role of decomposition within state-of-the-art algorithms for combinatorial optimization problems. Furthermore, in the spirit of reproducible science, whenever possible the source code produced was made publicly available online together with instance and solutions files.