
The fixed parameter tractable (FPT) approach is a powerful tool in tackling
computationally hard problems. In this paper, we link FPT results to classic
artificial intelligence (AI) techniques to show how they complement each other.
Specifically, we consider the workflow satisfiability problem (WSP) which asks
whether there exists an assignment of authorised users to the steps in a
workflow specification, subject to certain constraints on the assignment. It
was shown by Cohen et al. (JAIR 2014) that WSP restricted to the class of
userindependent constraints (UI), covering many practical cases, admits FPT
algorithms, i.e. can be solved in time exponential only in the number of steps
$k$ and polynomial in the number of users $n$. Since usually $k << n$ in WSP,
such FPT algorithms are of great practical interest. We present a new
interpretation of the FPT nature of the WSP with UI constraints giving a
decomposition of the problem into two levels. Exploiting this twolevel split,
we develop a new FPT algorithm that is by many orders of magnitude faster than
the previous stateoftheart WSP algorithm and also has only polynomialspace
complexity. We also introduce new pseudoBoolean (PB) and Constraint
Satisfaction (CSP) formulations of the WSP with UI constraints which
efficiently exploit this new decomposition of the problem and raise the novel
issue of how to use generalpurpose solvers to tackle FPT problems in a fashion
that meets FPT efficiency expectations. In our computational study, we
investigate, for the first time, the phase transition (PT) properties of the
WSP, under a model for generation of random instances. We show how PT studies
can be extended, in a novel fashion, to support empirical evaluation of scaling
of FPT algorithms.

One way to speed up the algorithm configuration task is to use short runs
instead of long runs as much as possible, but without discarding the
configurations that eventually do well on the long runs. We consider the
problem of selecting the top performing configurations of the Conditional
Markov Chain Search (CMCS), a general algorithm schema that includes, for
examples, VNS. We investigate how the structure of performance on short tests
links with those on long tests, showing that significant differences arise
between test domains. We propose a "performance envelope" method to exploit the
links; that learns when runs should be terminated, but that automatically
adapts to the domain.

The majority of scheduling metaheuristics use indirect representation of
solutions as a way to efficiently explore the search space. Thus, a crucial
part of such metaheuristics is a "schedule generation scheme"  procedure
translating the indirect solution representation into a schedule. Schedule
generation scheme is used every time a new candidate solution needs to be
evaluated. Being relatively slow, it eats up most of the running time of the
metaheuristic and, thus, its speed plays significant role in performance of the
metaheuristic. Despite its importance, little attention has been paid in the
literature to efficient implementation of schedule generation schemes. We give
detailed description of serial schedule generation scheme, including new
improvements, and propose a new approach for speeding it up, by using Bloom
filters. The results are further strengthened by automated control of
parameters. Finally, we employ online algorithm selection to dynamically choose
which of the two implementations to use. This hybrid approach significantly
outperforms conventional implementation on a wide range of instances.

A computerized workflow management system may enforce a security policy,
specified in terms of authorized actions and constraints, thereby restricting
which users can perform particular steps in a workflow. The existence of a
security policy may mean it is impossible to find a valid plan (an assignment
of steps to authorized users such that all constraints are satisfied). Work in
the literature focuses on the workflow satisfiability problem, a
\emph{decision} problem that outputs a valid plan if the instance is
satisfiable (and a negative result otherwise).
In this paper, we introduce the \textsc{BiObjective Workflow Satisfiability
Problem} (\BOWSP), which enables us to solve \emph{optimization} problems
related to workflows and security policies. In particular, we are able to
compute a "least bad" plan when some components of the security policy may be
violated. In general, \BOWSP is intractable from both the classical and
parameterized complexity point of view. We prove there exists an
fixedparameter tractable (FPT) algorithm to compute a Pareto front for \BOWSP
if we restrict our attention to userindependent constraints.
We also present a second algorithm to compute a Pareto front which uses mixed
integer programming (MIP). We compare the performance of both our algorithms on
synthetic instances, and show that the FPT algorithm outperforms the MIPbased
one by several orders of magnitude on most of the instances.
Finally, we study the important question of workflow resiliency and prove new
results establishing that known decision problems are fixedparameter tractable
when restricted to userindependent constraints. We then propose a new way of
modeling the availability of users and demonstrate that many questions related
to resiliency in the context of this new model may be reduced to instances of
\BOWSP.

We study the Bipartite Boolean Quadratic Programming Problem (BBQP) which is
an extension of the well known Boolean Quadratic Programming Problem (BQP).
Applications of the BBQP include mining discrete patterns from binary data,
approximating matrices by rankone binary matrices, computing the cutnorm of a
matrix, and solving optimisation problems such as maximum weight biclique,
bipartite maximum weight cut, maximum weight induced subgraph of a bipartite
graph, etc. For the BBQP, we first present several algorithmic components,
specifically, hill climbers and mutations, and then show how to combine them in
a highperformance metaheuristic. Instead of handtuning a standard
metaheuristic to test the efficiency of the hybrid of the components, we chose
to use an automated generation of a multicomponent metaheuristic to save human
time, and also improve objectivity in the analysis and comparisons of
components. For this we designed a new metaheuristic schema which we call
Conditional Markov Chain Search (CMCS). We show that CMCS is flexible enough to
model several standard metaheuristics; this flexibility is controlled by
multiple numeric parameters, and so is convenient for automated generation. We
study the configurations revealed by our approach and show that the best of
them outperforms the previous stateoftheart BBQP algorithm by several orders
of magnitude. In our experiments we use benchmark instances introduced in the
preliminary version of this paper and described here, which have already become
the de facto standard in the BBQP literature.

Multimode resource and precedenceconstrained project scheduling is a
wellknown challenging realworld optimisation problem. An important variant of
the problem requires scheduling of activities for multiple projects considering
availability of local and global resources while respecting a range of
constraints. A critical aspect of the benchmarks addressed in this paper is
that the primary objective is to minimise the sum of the project completion
times, with the usual makespan minimisation as a secondary objective. We
observe that this leads to an expected different overall structure of good
solutions and discuss the effects this has on the algorithm design. This paper
presents a carefully designed hybrid of MonteCarlo tree search, novel
neighbourhood moves, memetic algorithms, and hyperheuristic methods. The
implementation is also engineered to increase the speed with which iterations
are performed, and to exploit the computing power of multicore machines.
Empirical evaluation shows that the resulting informationsharing
multicomponent algorithm significantly outperforms other solvers on a set of
"hidden" instances, i.e. instances not available at the algorithm design phase.

The workflow satisfiability problem (WSP) asks whether there exists an
assignment of authorised users to the steps in a workflow specification,
subject to certain constraints on the assignment. (Such an assignment is called
valid.) The problem is NPhard even when restricted to the large class of
userindependent constraints. Since the number of steps $k$ is relatively small
in practice, it is natural to consider a parametrisation of the WSP by $k$. We
propose a new fixedparameter algorithm to solve the WSP with userindependent
constraints. The assignments in our method are partitioned into equivalence
classes such that the number of classes is exponential in $k$ only. We show
that one can decide, in polynomial time, whether there is a valid assignment in
an equivalence class. By exploiting this property, our algorithm reduces the
search space to the space of equivalence classes, which it browses within a
backtracking framework, hence emerging as an efficient yet relatively
simpletoimplement or generalise solution method. We empirically evaluate our
algorithm against the stateoftheart methods and show that it clearly wins
the competition on the whole range of our test problems and significantly
extends the domain of practically solvable instances of the WSP.

The synthetic aperture radar (SAR) technology enables satellites to
efficiently acquire high quality images of the Earth surface. This generates
significant communication traffic from the satellite to the ground stations,
and, thus, image downlinking often becomes the bottleneck in the efficiency of
the whole system. In this paper we address the downlink scheduling problem for
Canada's Earth observing SAR satellite, RADARSAT2. Being an applied problem,
downlink scheduling is characterised with a number of constraints that make it
difficult not only to optimise the schedule but even to produce a feasible
solution. We propose a fast schedule generation procedure that abstracts the
problem specific constraints and provides a simple interface to optimisation
algorithms. By comparing empirically several standard metaheuristics applied
to the problem, we select the most suitable one and show that it is clearly
superior to the approach currently in use.

A workflow is a collection of steps that must be executed in some specific
order to achieve an objective. A computerised workflow management system may
enforce authorisation policies and constraints, thereby restricting which users
can perform particular steps in a workflow. The existence of policies and
constraints may mean that a workflow is unsatisfiable, in the sense that it is
impossible to find an authorised user for each step in the workflow and satisfy
all constraints. In this paper, we consider the problem of finding the "least
bad" assignment of users to workflow steps by assigning a weight to each policy
and constraint violation. To this end, we introduce a framework for associating
costs with the violation of workflow policies and constraints and define the
\emph{valued workflow satisfiability problem} (Valued WSP), whose solution is
an assignment of steps to users of minimum cost. We establish the computational
complexity of Valued WSP with userindependent constraints and show that it is
fixedparameter tractable. We then describe an algorithm for solving Valued WSP
with userindependent constraints and evaluate its performance, comparing it to
that of an offtheshelf mixed integer programming package.

We consider the bipartite unconstrained 01 quadratic programming problem
(BQP01) which is a generalization of the well studied unconstrained 01
quadratic programming problem (QP01). BQP01 has numerous applications and the
problem is known to be MAX SNP hard. We show that if the rank of an associated
$m\times n$ cost matrix $Q=(q_{ij})$ is fixed, then BQP01 can be solved in
polynomial time. When $Q$ is of rank one, we provide an $O(n\log n)$ algorithm
and this complexity reduces to $O(n)$ with additional assumptions. Further, if
$q_{ij}=a_i+b_j$ for some $a_i$ and $b_j$, then BQP01 is shown to be solvable
in $O(mn\log n)$ time. By restricting $m=O(\log n),$ we obtain yet another
polynomially solvable case of BQP01 but the problem remains MAX SNP hard if
$m=O(\sqrt[k]{n})$ for a fixed $k$. Finally, if the minimum number of rows and
columns to be deleted from $Q$ to make the remaining matrix nonnegative is
$O(\log n)$ then we show that BQP01 polynomially solvable but it is NPhard if
this number is $O(\sqrt[k]{n})$ for any fixed $k$.
Keywords: quadratic programming, 01 variables, polynomial algorithms,
complexity, pseudoBoolean programming.

We introduce the quadratic balanced optimization problem (QBOP) which can be
used to model equitable distribution of resources with pairwise interaction.
QBOP is strongly NPhard even if the family of feasible solutions has a very
simple structure. Several general purpose exact and heuristic algorithms are
presented. Results of extensive computational experiments are reported using
randomly generated quadratic knapsack problems as the test bed. These results
illustrate the efficacy of our exact and heuristic algorithms. We also show
that when the cost matrix is specially structured, QBOP can be solved as a
sequence of linear balanced optimization problems. As a consequence, we have
several polynomially solvable cases of QBOP.

We study the Bipartite Unconstrained 01 Quadratic Programming Problem (BQP)
which is a relaxation of the Unconstrained 01 Quadratic Programming Problem
(QP). Applications of the BQP include mining discrete patterns from binary
data, approximating matrices by rankone binary matrices, computing cutnorm of
a matrix, and solving optimization problems such as maximum weight biclique,
bipartite maximum weight cut, maximum weight induced subgraph of a bipartite
graph, etc. We propose several classes of heuristic approaches to solve the BQP
and discuss a number of construction algorithms, local search algorithms and
their combinations. Results of extensive computational experiments are reported
to establish the practical performance of our algorithms. For this purpose, we
propose several sets of test instances based on various applications of the
BQP. Our algorithms are compared with stateoftheart heuristics for QP which
can also be used to solve BQP with reformulation. We also study theoretical
properties of the neighborhoods and algorithms. In particular, we establish
complexity of all neighborhood search algorithms and establish tight worstcase
performance ratio for the greedy algorithm.

We consider domination analysis of approximation algorithms for the bipartite
boolean quadratic programming problem (BBQP) with m+n variables. A closed form
formula is developed to compute the average objective function value A of all
solutions in O(mn) time. However, computing the median objective function value
of the solutions is shown to be NPhard. Also, we show that any solution with
objective function value no worse than A dominates at least 2^{m+n2} solutions
and this bound is the best possible. Further, we show that such a solution can
be identified in O(mn) time and hence the dominance ratio of this algorithm is
at least 1/4. We then show that for any fixed rational number a > 1, no
polynomial time approximation algorithm exists for BBQP with dominance ratio
larger than 12^{(m+n)(1a)/a}, unless P=NP. We then analyze some powerful
local search algorithms and show that they can get trapped at a local maximum
with objective function value less than A. One of our approximation algorithms
has an interesting rounding property which provides a data dependent lower
bound on the optimal objective function value. A new integer programming
formulation of BBQP is also given and computational results with our rounding
algorithms are reported.

We present an integer programming model for the ferry scheduling problem,
improving existing models in various ways. In particular, our model has reduced
size in terms of the number of variables and constraints compared to existing
models by a factor of approximately O(n), where n being the number of ports.
The model also handles efficiently load/unload time constraints, crew
scheduling and passenger transfers. Experiments using real world data produced
high quality solutions in 12 hours using CPLEX 12.4 with a performance
guarantee of within 15% of optimality, on average. This establishes that using
a general purpose integer programming solver is a viable alternative in solving
the ferry scheduling problem of moderate size.

Combinatorial optimization is widely applied in a number of areas nowadays.
Unfortunately, many combinatorial optimization problems are NPhard which
usually means that they are unsolvable in practice. However, it is often
unnecessary to have an exact solution. In this case one may use heuristic
approach to obtain a nearoptimal solution in some reasonable time.
We focus on two combinatorial optimization problems, namely the Generalized
Traveling Salesman Problem and the Multidimensional Assignment Problem. The
first problem is an important generalization of the Traveling Salesman Problem;
the second one is a generalization of the Assignment Problem for an arbitrary
number of dimensions. Both problems are NPhard and have hosts of applications.
In this work, we discuss different aspects of heuristics design and
evaluation. A broad spectrum of related subjects, covered in this research,
includes test bed generation and analysis, implementation and performance
issues, local search neighborhoods and efficient exploration algorithms,
metaheuristics design and population sizing in memetic algorithm.
The most important results are obtained in the areas of local search and
memetic algorithms for the considered problems. In both cases we have
significantly advanced the existing knowledge on the local search neighborhoods
and algorithms by systematizing and improving the previous results. We have
proposed a number of efficient heuristics which dominate the existing
algorithms in a wide range of time/quality requirements.
Several new approaches, introduced in our memetic algorithms, make them the
stateoftheart metaheuristics for the corresponding problems. Population
sizing is one of the most promising among these approaches; it is expected to
be applicable to virtually any memetic algorithm.

The Generalized Traveling Salesman Problem (GTSP) is an extension of the
wellknown Traveling Salesman Problem (TSP), where the node set is partitioned
into clusters, and the objective is to find the shortest cycle visiting each
cluster exactly once. In this paper, we present a new hybrid Ant Colony System
(ACS) algorithm for the symmetric GTSP. The proposed algorithm is a
modification of a simple ACS for the TSP improved by an efficient GTSPspecific
local search procedure. Our extensive computational experiments show that the
use of the local search procedure dramatically improves the performance of the
ACS algorithm, making it one of the most successful GTSP metaheuristics to
date.

The Generalized Traveling Salesman Problem (GTSP) is a wellknown
combinatorial optimization problem with a host of applications. It is an
extension of the Traveling Salesman Problem (TSP) where the set of cities is
partitioned into socalled clusters, and the salesman has to visit every
cluster exactly once.
While the GTSP is a very important combinatorial optimization problem and is
well studied in many aspects, the local search algorithms used in the
literature are mostly basic adaptations of simple TSP heuristics. Hence, a
thorough and deep research of the neighborhoods and local search algorithms
specific to the GTSP is required.
We formalize the procedure of adaptation of a TSP neighborhood for the GTSP
and classify all other existing and some new GTSP neighborhoods. For every
neighborhood, we provide efficient exploration algorithms that are often
significantly faster than the ones known from the literature. Finally, we
compare different local search implementations empirically.

The LinKernighan heuristic is known to be one of the most successful
heuristics for the Traveling Salesman Problem (TSP). It has also proven its
efficiency in application to some other problems. In this paper we discuss
possible adaptations of TSP heuristics for the Generalized Traveling Salesman
Problem (GTSP) and focus on the case of the LinKernighan algorithm. At first,
we provide an easytounderstand description of the original LinKernighan
heuristic. Then we propose several adaptations, both trivial and complicated.
Finally, we conduct a fair competition between all the variations of the
LinKernighan adaptation and some other GTSP heuristics. It appears that our
adaptation of the LinKernighan algorithm for the GTSP reproduces the success
of the original heuristic. Different variations of our adaptation outperform
all other heuristics in a wide range of tradeoffs between solution quality and
running time, making LinKernighan the stateoftheart GTSP local search.

Memetic Algorithms are known to be a powerful technique in solving hard
optimization problems. To design a memetic algorithm one needs to make a host
of decisions; selecting a population size is one of the most important among
them. Most algorithms in the literature fix the population size to a certain
constant value. This reduces the algorithm's quality since the optimal
population size varies for different instances, local search procedures and
running times. In this paper we propose an adjustable population size. It is
calculated as a function of the running time of the whole algorithm and the
average running time of the local search for the given instance. Note that in
many applications the running time of a heuristic should be limited and
therefore we use this limit as a parameter of the algorithm. The average
running time of the local search procedure is obtained during the algorithm's
run. Some coefficients which are independent with respect to the instance or
the local search are to be tuned before the algorithm run; we provide a
procedure to find these coefficients. The proposed approach was used to develop
a memetic algorithm for the Multidimensional Assignment Problem (MAP or sAP in
the case of s dimensions) which is an extension of the wellknown assignment
problem. MAP is NPhard and has a host of applications. We show that using
adjustable population size makes the algorithm flexible to perform well for
instances of very different sizes and types and for different running times and
local searches. This allows us to select the most efficient local search for
every instance type. The results of computational experiments for several
instance families and sizes prove that the proposed algorithm performs
efficiently for a wide range of the running times and clearly outperforms the
stateofthe art 3AP memetic algorithm being given the same time.

The Multidimensional Assignment Problem (MAP) (abbreviated sAP in the case
of s dimensions) is an extension of the wellknown assignment problem. The most
studied case of MAP is 3AP, though the problems with larger values of s also
have a large number of applications. We consider several known neighborhoods,
generalize them and propose some new ones. The heuristics are evaluated both
theoretically and experimentally and dominating algorithms are selected. We
also demonstrate a combination of two neighborhoods may yield a heuristics
which is superior to both of its components.

The multidimensional assignment problem (MAP) (abbreviated sAP in the case
of s dimensions) is an extension of the wellknown assignment problem. The most
studied case of MAP is 3AP, though the problems with larger values of s have
also a number of applications. In this paper we consider four fast construction
heuristics for MAP. One of the heuristics is new. A modification of the
heuristics is proposed to optimize the access to slow computer memory. The
results of computational experiments for several instance families are provided
and discussed.

The Multidimensional Assignment Problem (MAP or sAP in the case of s
dimensions) is an extension of the wellknown assignment problem. The most
studied case of MAP is 3AP, though the problems with larger values of s have
also a number of applications. In this paper we propose a memetic algorithm for
MAP that is a combination of a genetic algorithm with a local search procedure.
The main contribution of the paper is an idea of dynamically adjusted
generation size, that yields an outstanding flexibility of the algorithm to
perform well for both small and large fixed running times. The results of
computational experiments for several instance families show that the proposed
algorithm produces solutions of very high quality in a reasonable time and
outperforms the stateofthe art 3AP memetic algorithm.

The generalized traveling salesman problem (GTSP) is an extension of the
wellknown traveling salesman problem. In GTSP, we are given a partition of
cities into groups and we are required to find a minimum length tour that
includes exactly one city from each group. The aim of this paper is to present
a problem reduction algorithm that deletes redundant vertices and edges,
preserving the optimal solution. The algorithm's running time is O(N^3) in the
worst case, but it is significantly faster in practice. The algorithm has
reduced the problem size by 1520% on average in our experiments and this has
decreased the solution time by 1060% for each of the considered solvers.

The generalized traveling salesman problem (GTSP) is an extension of the
wellknown traveling salesman problem. In GTSP, we are given a partition of
cities into groups and we are required to find a minimum length tour that
includes exactly one city from each group. The recent studies on this subject
consider different variations of a memetic algorithm approach to the GTSP. The
aim of this paper is to present a new memetic algorithm for GTSP with a
powerful local search procedure. The experiments show that the proposed
algorithm clearly outperforms all of the known heuristics with respect to both
solution quality and running time. While the other memetic algorithms were
designed only for the symmetric GTSP, our algorithm can solve both symmetric
and asymmetric instances.