Improving Approximate and Exact Approaches Based on Decision Diagrams and Dynamic Programming for Combinatorial Optimization

Combinatorial Optimization (CO) problems arise in a wide range of real-world applications such as logistics, scheduling, and resource allocation. These problems often possess an exponential search space, making it computationally challenging to solve them optimally. One key strategy for addressing this challenge is to develop scalable and general bounding techniques that can provide high-quality primal and dual bounds, crucial components in exact solution methods such as Branch-and-Bound. Alternatively, one can compromise on optimality and pursue non-exact solutions through the use of approximation or heuristic algorithms, where the former provides mathematically guaranteed bounds and the latter offers no such guarantees. This dissertation focuses on advancing approximate and exact methodologies for CO by leveraging Decision Diagrams (DDs) and Dynamic Programming (DP). Decision Diagrams offer a powerful graphical representation of the solution space, enabling both over- and under-approximations, known as relaxed and restricted DDs, that yield dual and primal bounds, respectively. However, the quality of these bounds, which directly influences the effectiveness of exact methods, is significantly affected by two critical factors: the ordering of decision variables and the selection of nodes during compilation. Dynamic Programming provides a general framework for solving a wide range of CO problems by breaking them down into overlapping subproblems. In certain cases, the DP formulations allow for design of Fully Polynomial Time Approximation Schemes (FPTAS), offering solutions with provable bound guarantees. In this thesis, we aim to advance DD-based bounding mechanisms, which potentially accelerates DD-based exact approaches, by introducing several novel node selection and variable ordering strategies. First, we propose a clustering-based node selection heuristic that groups structurally similar states. Second, we introduce a novel top-down compilation strategy inspired by the bottom-up DD reduction algorithm, which groups the nodes based on their partial completions. Third, for the Maximum Independent Set Problem (MISP), we develop a dynamic variable ordering technique based on the graph-theoretical properties of induced subgraphs corresponding to states, along with a tie-based merge heuristic. To complement the DD-based contributions, we propose several pseudo-polynomial-time DPs that exploit state dominance relations for solving a Drone Delivery Scheduling problem. Furthermore, we extend the DP models to FPTAS, providing efficient approximate solutions with provable guarantees. % to prune the search space Overall, this dissertation contributes to both the theoretical and practical advancement of approximate and exact methods for solving CO problems using DDs and DP. All proposed methodologies are validated through extensive computational experiments on a set of CO problems, demonstrating the superiority of the developed techniques in terms of bound quality, runtime, and the number of explored states.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Bielefeld

Year

2025

Author dc:creator

• Nafar, Mohsen

Repository record source_url

https://pub.uni-bielefeld.de/record/3003948

OAI identifier oai:identifier

oai:pub.uni-bielefeld.de:3003948