M. Horn:

"Advances in Search Techniques for Combinatorial Optimization: New Anytime A* Search and Decision Diagram Based Approaches";

Supervisor, Reviewer: G. Raidl, C. Blum, L. Di Gaspero; Institute of Logic and Computation, 2021; oral examination: 2021-09-09.

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, where a node of

the search graph corresponds to a state that represents a set of partial solutions of the

considered COP. A transition from one state to another state, indicated by an arc in

the search graph, represents a feasible extension of the partial solutions. 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 first part of this thesis focuses on turning A∗ search into an anytime A∗ search

such that the algorithm is able to find a feasible heuristic solution shortly after the

start and then continuously updates 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 (BS). The novel anytime

A∗ approach is tested on the job sequencing problem with one common and multiple

secondary resources (JSOCMSR), which consists of a set of jobs that must be feasible

scheduled, a common resource, and a set of secondary resources. Each job needs during

its execution the common resource and one of the secondary resources. The common

resource acts as a bottleneck resource. The objective is to minimize the makespan. One

main application of the JSOCMSR is in the field of scheduling treatments for cancer

patients who are to receive particle therapies. Experimental evaluation will show an

excellent anytime behavior of our novel anytime A∗ search. Furthermore, the anytime A∗

approach is compared to other anytime algorithms as well as to different exact approaches.

The second part of this thesis considers decision diagrams (DDs), which are a rather new

methodology for solving COPs that has a strong connection to state-space representations

as well. Decision diagrams provide graphical representations of a COPīs solution space.

In particular relaxed DDs represent compact discrete relaxations of the solution space.

Thus, relaxed DDs have the potential to provide strong dual bounds on problems

where traditional relaxations, e.g. linear programming relaxations, may be rather weak.Restricted DDs are another important kind of DDs, which encode a compact subset

of a COPīs solution space. Hence, they are able to provide heuristic solutions. This

thesis will propose a novel construction algorithm of relaxed DDs that is based on the

principles of A∗ search. The construction algorithm is tested by creating relaxed DDs for

two NP-hard problems. The first problem is a prize-collecting variant of the JSOCMSR,

where each job is equipped with a prize and a set of time windows such that a job can

only be feasibly scheduled within one of its time windows. The task is to find a subset of

jobs that can be feasible scheduled and that maximizes the total prize over the selected

jobs. The second problem is the well known classical longest common subsequence (LCS)

problem, which consists of multiple input strings over a finite alphabet. The task is to

find a longest subsequence that is common to all input strings. The LCS problem has its

application, for instance, in bioinformatics, where strings often represent RNA or DNA

segments. For both problems we are able to compile in a shorter time relaxed DDs with

the novel A∗-based compilation method that are smaller and yield stronger dual bounds

than relaxed DDs compiled with traditional methods from the literature.

For the JSOCMSR variant we create further restricted DDs by using structural information

of a previously compiled relaxed DD such that the compilation time of the restricted

DDs is substantially accelerated. This idea of exploiting structural information of relaxed

DDs is pursued further in this thesis by accelerating other search heuristics as well. In

particular, we used a previously compiled relaxed DD to accelerate a hybrid approach of

limited discrepancy search (LDS) and BS, which is used to heuristically solve the prizecollecting

variant of the JSOCMSR with additional precedence constraints. Exhaustive

experiments confirm that the LDS/BS approach exploiting a relaxed DD is substantially

faster than a standalone approach. In this way it is possible to scan larger parts of

the solution space in the same time as a standalone approach in order to obtain better

heuristic solutions.

Finally, this thesis considers the repetition-free longest common susequence (RFLCS)

problem, which consists of two input strings over a finite alphabet. The task is to find a

LCS of both input strings that is repetition-free, i.e., each character in the subsequence

appears no more than once. An instance of the problem is solved by transforming it into

an instance of the maximum independent set (MIS) problem, which is then solved by an

integer linear programming (ILP) approach. We contribute by using a relaxed DD to

extensively reduce the size of the MIS problemīs conflict graph. Numerical experiments

confirm that, as a consequence of the reduction, the corresponding ILP model can be

substantially faster solved.

http://dx.doi.org/10.34726/hss.2021.96303

https://publik.tuwien.ac.at/files/publik_301839.pdf

Created from the Publication Database of the Vienna University of Technology.