The longest common palindromic subsequence (LCPS) problem aims at finding a longest string that appears as a subsequence in each of a set of input strings and is a palindrome at the same time. The problem is a special variant of the well known longest common subsequence problem and has applications in particular in genomics and biology, where strings

correspond to DNA or protein sequences and similarities among them shall be detected or quantified. We first present a more traditional A* search that makes use of an advanced upper bound calculation for partial solutions. This exact approach works well for instances with two input strings and, as we show in experiments, outperforms several other exact methods from the literature. However, the A* search also has natural limitations when a larger number of strings shall be considered due to the problem{\textquoteright}s complexity. To effectively deal with this case in practice, we investigate anytime A* variants, which are able to return a reasonable heuristic solution at almost any time and are expected to find better and better solutions until reaching a proven optimum when enough time given. In particular we propose a novel approach in which Anytime Column Search (ACS) is interleaved with traditional A* node expansions. The ACS iterations are guided by a new heuristic function that approximates the expected length of an LCPS in subproblems usually much better than the available upper bound calculation. This A*+ACS hybrid is able to solve small to medium-sized LCPS instances to proven optimality while returning good heuristic solutions together with upper bounds for large instances. In rigorous experimental evaluations we compare A*+ACS to several other anytime A* search variants and observe its superiority.

We consider a sequencing problem that arises, for example, in the context of scheduling patients in particle therapy facilities for cancer treatment. A set of non-preemptive jobs needs to be scheduled, where each job requires two resources: (1) a common resource that is shared by all jobs and (2) a secondary resource, which is shared with only a subset of the other jobs.\ While the common resource is only required for a part of the job{\textquoteright}s processing time, the secondary resource is required for the whole duration.\ The objective is to minimize the makespan. First we show that the tackled problem is NP-hard and provide three different lower bounds for the makespan.\ These lower bounds are then exploited in a greedy construction heuristic and a novel exact anytime A* algorithm, which uses an advanced diving mechanism based on Beam Search and Local Search to find good heuristic solutions early. For comparison we also provide a basic Constraint Programming model solved with the ILOG CP optimizer.\ An extensive experimental evaluation on two types of problem instances shows that the approach works even for large instances with up to 2000 jobs extremely well. It typically yields either optimal solutions or solutions with an optimality gap of less than 1\%.\

}, doi = {https://doi.org/10.1016/j.artint.2019.103173}, url = {https://authors.elsevier.com/c/1ZoNa-c5JpQT}, author = {Horn, Matthias and Raidl, G{\"u}nther R and Blum, Christian} } @proceedings {56012, title = {Job Sequencing with One Common and Multiple Secondary Resources: A Problem Motivated from Particle Therapy for Cancer Treatment}, journal = {MOD 2017 -- The Third International Conference on Machine Learning, Optimization and Big Data}, year = {2017}, publisher = {Springer Verlag}, abstract = {We consider in this work the problem of scheduling a set of jobs without preemption, where each job requires two resources: (1) a common resource, shared by all jobs, is required during a part of the job{\textquoteright}s processing period, while (2) a secondary resource, which is shared with only a subset of the other jobs, is required during the job{\textquoteright}s whole processing period. This problem models, for example, the scheduling of patients during one day in a particle therapy facility for cancer treatment. First, we show that the tackled problem is NP-hard. We then present a construction heuristic and a novel A* algorithm, both on the basis of an effective lower bound calculation. For comparison, we also model the problem as a mixed-integer linear program (MILP). An extensive experimental evaluation on three types of problem instances shows that A* typically works extremely well, even in the context of large instances with up to 1000 jobs. When our A* does not terminate with proven optimality, which might happen due to excessive memory requirements, it still returns an approximate solution with a usually small optimality gap. In contrast, solving the MILP model with CPLEX is not competitive except for very small problem instances.

}, author = {Horn, Matthias and Raidl, G{\"u}nther R and Blum, Christian} } @article {55921, title = {Large neighborhood search for the most strings with few bad columns problem}, journal = {Soft Computing}, volume = {21}, year = {2017}, pages = {4901{\textendash}4915}, abstract = {In this work, we consider the following NP-hard combinatorial optimization problem from computational biology. Given a set of input strings of equal length, the goal is to identify a maximum cardinality subset of strings that differ maximally in a pre-defined number of positions. First of all, we introduce an integer linear programming model for this problem. Second, two variants of a rather simple greedy strategy are proposed. Finally, a large neighborhood search algorithm is presented. A comprehensive experimental comparison among the proposed techniques shows, first, that larger neighborhood search generally outperforms both greedy strategies. Second, while large neighborhood search shows to be competitive with the stand-alone application of CPLEX for small- and medium-sized problem instances, it outperforms CPLEX in the context of larger instances.

}, issn = {1432-7643}, doi = {http://dx.doi.org/10.1007/s00500-016-2379-4}, author = {Liz{\'a}rraga, Evelia and Blesa, Maria J and Blum, Christian and Raidl, G{\"u}nther R} }