Advances in search techniques for combinatorial optimization: New anytime A* search and decision diagram based approaches

Abstract

Graph search strategies are important methodologies in order to solve combinatorial optimization problems (COPs). Thereby a search tree or search graph is usually considered during the search that covers certain parts of a COP’s solution space. In this thesis the search graphs will be mainly based on a state-space representation. We will apply different search techniques to obtain (proven optimal) solutions as well as dual bounds for different COPs. Most considered approaches in this thesis are based on the informed search algorithm A∗ search, which uses a heuristic function to guide the search towards the solution space and, under certain conditions, is able to terminate with a proven optimal solution. The main contributions of this thesis are- A novel anytime A∗ search that is able to find a feasible heuristic solution shortly after the start and then continuously update it until a proven optimal solution is finally found. To find heuristic solutions, the approach switches in regular intervals from best-first search to an advanced diving mechanism based on beam search. The anytime algorithm is applied on a NP-hard job sequencing problem that arises in the field of scheduling treatments for cancer patients who are to receive particle therapies. Computational experiments show that the proposed algorithm outperforms other anytime algorithms as well as different exact approaches.- A novel construction algorithm for relaxed decision diagrams (DDs) that is based on the principles of A∗ search. Decision diagrams are a rather new methodology for solving COPs that has a strong connection to state-space representation as well. In particular relaxed DDs represent compact discrete relaxations of a COP’s solution space and have the potential to provide strong dual bounds on problems where traditional relaxations may be rather weak. The A∗-based construction algorithm compiles relaxed DDs for a variation of the already mentioned job sequencing problem as well as for the longest common subsequence problem. For both problems it is possible to compile, in a shorter time, stronger relaxed DDs that are more compact than relaxed DDs compiled with traditional methods from the literature. Furthermore, besides deriving dual bounds the constructed relaxed DDs are also used for accelerating a hybrid heuristic of beam search and limited discrepancy search. Moreover, with the aid of relaxed DDs, new state-of-the-art results could be obtained for the repetition-free longest common subsequence problem.