The core area of operations research focuses on classical combinatorial optimisation problems. This topic includes many common problems that arise, e.g., in industrial logistics such as supply chain management or scheduling. The aim here, roughly speaking, is to find realisable solutions in a reasonable amount of time. At our chair, we investigate, on one side, various meta- and matheuristic algorithms like simulated annealing, tabu search, genetic algorithms or the large neighbourhood search and, on the other side, the exact boundary between $\mathcal{NP}$-hard problems and polynomial solvable special cases of them.
All these topics are essential parts of the bachelor’s and master’s programmes Industrial Logistics (Industrial Logistics) and Industrial Data Science (Industrial Data Science).
Research topics of our special interest
Travelling salesperson problem (TSP)
The travelling salesperson problem (TSP) is one of the best known combinatorial optimisation problems which has been exhaustively investigated for many decades. Given a complete graph $G = (V, E)$ with $|V|$ and $|E| = n(n-1)/2$ and non-negative distances $d_e$ for each $e \in E$, the TSP asks for a shortest tour with respect to the distances $d_e$ containing each vertex exactly once.
In our research we target very large instances with up to $10^9$ vertices. For such dimensions common approaches are useless, because even algorithms having a quadratic running time are too slow. Therefore we develop matheurstics dividing the original problem into many small subproblems, which are solved to optimality.
Quadratic assignment problem (QAP)
The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems for which it is very hard to find good solutions even for relatively small instances. Given $n$ departments with pairwise flow volumes and $n$ locations with relative distances for each pair of them, the QAP asks for an assignment of all departments to different locations that minimises the sum of all distances multiplied by the corresponding flow volumes.
We solve this problem by dividing the test instances into many subproblems, which then are solved. Because all flow volumes and all distances always contribute to the objective function value, we cannot make local changes without considering the remainder of the test instance. We address this issue by weighting the particular changes based on an estimate.
Quadratic travelling salesperson problem (QTSP)
Similarly to the TSP in the quadratic travelling salesperson problem (QTSP), we are looking for a tour; however, not only the costs of direct movements from one vertex to the next vertex are considered, but beyond that, costs arising for the successive use of two edges are taken into account. This means that we consider the transition in each vertex $v$ which depends both on the predecessor and on the successor of $v$ in the tour. As a consequence, transition costs, such as the effort of turning in path planning, changing equipment in scheduling, or the change of transportation means in logistic networks from one edge to another, can be modelled. If the transition costs correspond to turning angles, we speak of the angular-metric travelling salesperson problem (AngleTSP); the AngleTSP is therefore a special case of the QTSP.
In our research, we look for efficient meta- and matheuristics for solving this problem. They are based 1) on geometric properties of “good” tours when considering the AngleTSP and 2) on rounding matheuristics using a linearisation of the original quadratic program in the general case.
Maximum quadratic travelling salesperson problem (MaxQTSP)
The maximum quadratic travelling salesperson problem (MaxQTSP) and the maximum angular-metric travelling salesperson problem (MaxAngleTSP) are the maximisation versions of the QTSP and of the AngleTSP, respectively.
In our research, we proved that the MaxAngleTSP is solvable in a polynomial time if the number of vertices $n$ is odd. The open question is whether the MaxAngleTSP is solvable in a polynomial time if $n$ is even as well. If this is not the case, which complexity class does this problem belong to?
Data arrangement problem on regular trees (DAPT)
The data arrangement problem on regular trees (DAPT) consists in assigning the vertices of a given graph $G$, called the guest graph, to the leaves of a $d$-regular tree $T$, called the host graph, such that the sum of the pairwise distances of all pairs of leaves in $T$ which correspond to the edges of $G$ is minimised. Luczak and Noble (2002) have shown that this problem is $\mathcal{NP}$-hard for every fixed $d \geq 2$. We proved that the DAPT remains $\mathcal{NP}$-hard even if the guest graph is a tree.
In the next step, we focussed on an even more restricted case of the DAPT, where both the guest and host graphs are regular binary trees. We found a 1.015-approximation algorithm and provided the value of the objective function corresponding to the solution computed by the algorithm in closed form. The computational complexity of this special case of the DAPT remains, however, a compelling open question. The decision version of this problem belongs to the complexity class $\mathcal{P}/poly$ and a classic result by Mahaney (1982) implies that, unless $\mathcal{P} = \mathcal{NP}$, this specific special case cannot be $\mathcal{NP}$-hard. Our structural analysis and computational experiments suggest that optimal solutions do not follow simple recursive patterns. This leads us to conjecture that this version of the DAPT belongs to the $\mathcal{NP}$-intermediate complexity class.
Further, we also focus on other special cases of the DAPT, where the guest graph $G$ and host graph $T$ are $d$-regular and $d^\prime$-regular trees, respectively, with $d = d^\prime \geq 3$ or $d \neq d^\prime$.
Queen/knight/janus domination problem
The queen (/knight/janus) domination problem asks for the minimum number of queens (/knights/jani) needed to attack or occupy all squares on an $n \times n$ chessboard. In our research, we focus on ILP-based matheuristics producing good upper bounds used within a branch-and-bound framework. In particular, we utilise and envelop the kernel search and the corridor method. These matheuristics are used, on the one hand, to find a feasible solution for the whole chessboard and, on the other hand, to solve subproblems whose solutions are then combined to obtain a feasible solution to the original problem.
Bachelor's and master's theses
Students who would like to write their bachelor’s or master’s thesis (theoretical as well as practical) on the field of operations research are welcome to contact me via e-mail: rostislav.stanek(at)unileoben.ac.at. Some bachelor’s and master’s thesis topics are listed here. Collaborations with companies are welcome, too!