[Back]

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