• ### Pattern-Based Approach to the Workflow Satisfiability Problem with User-Independent Constraints(1604.05636)

July 23, 2019 cs.AI, cs.CC
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 user-independent 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 two-level split, we develop a new FPT algorithm that is by many orders of magnitude faster than the previous state-of-the-art WSP algorithm and also has only polynomial-space complexity. We also introduce new pseudo-Boolean (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 general-purpose 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.
• ### Algorithm Configuration: Learning policies for the quick termination of poor performers(1803.09785)

March 26, 2018 cs.AI, cs.DS
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.
• ### Efficient Adaptive Implementation of the Serial Schedule Generation Scheme using Preprocessing and Bloom Filters(1708.07786)

Aug. 25, 2017 cs.PF, cs.DS
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.
• ### The Bi-Objective Workflow Satisfiability Problem and Workflow Resiliency(1512.07019)

Nov. 15, 2016 cs.CR, cs.DS
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{Bi-Objective 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 fixed-parameter tractable (FPT) algorithm to compute a Pareto front for \BOWSP if we restrict our attention to user-independent 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 MIP-based 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 fixed-parameter tractable when restricted to user-independent 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.
• ### Markov Chain methods for the bipartite Boolean quadratic programming problem(1605.02038)

Oct. 24, 2016 cs.AI, cs.DS
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 rank-one binary matrices, computing the cut-norm of a matrix, and solving optimisation problems such as maximum weight biclique, bipartite maximum weight cut, maximum weight induced sub-graph 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 high-performance metaheuristic. Instead of hand-tuning a standard metaheuristic to test the efficiency of the hybrid of the components, we chose to use an automated generation of a multi-component 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 state-of-the-art 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.
• ### Combining Monte-Carlo and Hyper-heuristic methods for the Multi-mode Resource-constrained Multi-project Scheduling Problem(1511.04387)

Sept. 8, 2016 cs.AI, cs.NE, cs.DS
Multi-mode resource and precedence-constrained project scheduling is a well-known challenging real-world 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 Monte-Carlo tree search, novel neighbourhood moves, memetic algorithms, and hyper-heuristic 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 information-sharing multi-component algorithm significantly outperforms other solvers on a set of "hidden" instances, i.e. instances not available at the algorithm design phase.
• ### Pattern Backtracking Algorithm for the Workflow Satisfiability Problem(1412.7834)

March 30, 2015 cs.DS
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 NP-hard even when restricted to the large class of user-independent 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 fixed-parameter algorithm to solve the WSP with user-independent 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 simple-to-implement or generalise solution method. We empirically evaluate our algorithm against the state-of-the-art 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.
• ### Satellite downlink scheduling problem: A case study(1206.5503)

Feb. 14, 2015 cs.DM, math.OC
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, RADARSAT-2. 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 meta-heuristics applied to the problem, we select the most suitable one and show that it is clearly superior to the approach currently in use.
• ### Valued Workflow Satisfiability Problem(1501.07814)

Jan. 30, 2015 cs.CR, cs.DS, cs.CC
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 user-independent constraints and show that it is fixed-parameter tractable. We then describe an algorithm for solving Valued WSP with user-independent constraints and evaluate its performance, comparing it to that of an off-the-shelf mixed integer programming package.
• ### The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases(1212.3736)

April 28, 2014 math.CO, cs.DM, math.OC
We consider the bipartite unconstrained 0-1 quadratic programming problem (BQP01) which is a generalization of the well studied unconstrained 0-1 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 non-negative is $O(\log n)$ then we show that BQP01 polynomially solvable but it is NP-hard if this number is $O(\sqrt[k]{n})$ for any fixed $k$. Keywords: quadratic programming, 0-1 variables, polynomial algorithms, complexity, pseudo-Boolean programming.
• ### The quadratic balanced optimization problem(1212.4211)

Aug. 14, 2013 math.CO, cs.DM, math.OC
We introduce the quadratic balanced optimization problem (QBOP) which can be used to model equitable distribution of resources with pairwise interaction. QBOP is strongly NP-hard 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.
• ### Heuristic algorithms for the bipartite unconstrained 0-1 quadratic programming problem(1210.3684)

July 22, 2013 math.CO, cs.DM
We study the Bipartite Unconstrained 0-1 Quadratic Programming Problem (BQP) which is a relaxation of the Unconstrained 0-1 Quadratic Programming Problem (QP). Applications of the BQP include mining discrete patterns from binary data, approximating matrices by rank-one binary matrices, computing cut-norm 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 state-of-the-art 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 worst-case performance ratio for the greedy algorithm.
• ### Average value of solutions for the bipartite boolean quadratic programs and rounding algorithms(1303.0160)

March 1, 2013 math.CO, cs.DM, math.OC
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 NP-hard. Also, we show that any solution with objective function value no worse than A dominates at least 2^{m+n-2} 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 1-2^{(m+n)(1-a)/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.
• ### A reduced integer programming model for the ferry scheduling problem(1205.3757)

Nov. 23, 2012 cs.DM, math.OC
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.
• ### Design, Evaluation and Analysis of Combinatorial Optimization Heuristic Algorithms(1207.1794)

July 7, 2012 cs.AI, cs.DM, cs.DS, math.OC
Combinatorial optimization is widely applied in a number of areas nowadays. Unfortunately, many combinatorial optimization problems are NP-hard 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 near-optimal 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 NP-hard 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 state-of-the-art 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.
• ### An Efficient Hybrid Ant Colony System for the Generalized Traveling Salesman Problem(1206.1579)

July 5, 2012 math.CO, cs.AI, math.OC
The Generalized Traveling Salesman Problem (GTSP) is an extension of the well-known 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 GTSP-specific 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.
• ### Efficient Local Search Algorithms for Known and New Neighborhoods for the Generalized Traveling Salesman Problem(1005.5525)

Feb. 13, 2012 cs.DS
The Generalized Traveling Salesman Problem (GTSP) is a well-known 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 so-called 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.
• ### Lin-Kernighan Heuristic Adaptations for the Generalized Traveling Salesman Problem(1003.5330)

June 23, 2010 cs.DS
The Lin-Kernighan 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 Lin-Kernighan algorithm. At first, we provide an easy-to-understand description of the original Lin-Kernighan heuristic. Then we propose several adaptations, both trivial and complicated. Finally, we conduct a fair competition between all the variations of the Lin-Kernighan adaptation and some other GTSP heuristics. It appears that our adaptation of the Lin-Kernighan 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 trade-offs between solution quality and running time, making Lin-Kernighan the state-of-the-art GTSP local search.
• ### A New Approach to Population Sizing for Memetic Algorithms: A Case Study for the Multidimensional Assignment Problem(1003.4314)

March 23, 2010 cs.DS
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 s-AP in the case of s dimensions) which is an extension of the well-known assignment problem. MAP is NP-hard 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 state-of-the art 3-AP memetic algorithm being given the same time.
• ### Local Search Heuristics For The Multidimensional Assignment Problem(0806.3258)

July 25, 2009 cs.DS
The Multidimensional Assignment Problem (MAP) (abbreviated s-AP in the case of s dimensions) is an extension of the well-known assignment problem. The most studied case of MAP is 3-AP, 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.
• ### Empirical evaluation of construction heuristics for the multidimensional assignment problem(0906.2960)

June 16, 2009 cs.DS
The multidimensional assignment problem (MAP) (abbreviated s-AP in the case of s dimensions) is an extension of the well-known assignment problem. The most studied case of MAP is 3-AP, 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.
• ### A Memetic Algorithm for the Multidimensional Assignment Problem(0906.0862)

June 4, 2009 cs.DS
The Multidimensional Assignment Problem (MAP or s-AP in the case of s dimensions) is an extension of the well-known assignment problem. The most studied case of MAP is 3-AP, 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 state-of-the art 3-AP memetic algorithm.
• ### Generalized Traveling Salesman Problem Reduction Algorithms(0804.0735)

April 14, 2009 cs.DS
The generalized traveling salesman problem (GTSP) is an extension of the well-known 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 15-20% on average in our experiments and this has decreased the solution time by 10-60% for each of the considered solvers.
• ### A Memetic Algorithm for the Generalized Traveling Salesman Problem(0804.0722)

March 13, 2009 cs.DS
The generalized traveling salesman problem (GTSP) is an extension of the well-known 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.