Cyber-physical systems (CPSs) are part of many critical infrastructures such as industrial automation and transportation systems. Thus, security incidents targeting CPSs can have disruptive consequences to assets and people. As incidents tend to re-occur, sharing knowledge about these incidents can help organizations be more prepared to prevent, mitigate or investigate future incidents. This paper proposes a novel approach to enable representation and sharing of knowledge about CPS incidents across different organizations. To support sharing, we represent incident knowledge (incident patterns) capturing incident characteristics that can manifest again, such as incident activities or vulnerabilities exploited by offenders. Incident patterns are a more abstract representation of specific incident instances and, thus, are general enough to be applicable to various systems - different from the one in which the incident originally occurred. They can also avoid disclosing potentially sensitive information about an organization's assets and resources. We provide an automated technique toextractan incident pattern from a specific incident instance. To understand how an incident pattern can manifest again in other cyber-physical systems, we also provide an automated technique toinstantiateincident patterns to specific systems. We demonstrate the feasibility of our approach in the application domain of smart buildings. We evaluate correctness, scalability, and performance using two substantive scenarios inspired by real-world systems and incidents.

Energy consumed by computation and cooling represents the greatest percentage of the average energy consumed in a data centre. As these two aspects are not always coordinated, energy consumption is not optimised. Data centres lack an integrated system that jointly optimises and controls all the operations in order to reduce energy consumption and increase the usage of renewable sources. GENiC is addressing this through a novel scalable, integrate energy management and control platform for data centre wide optimisation. We have implemented and prototype of the platform together with workload and thermal management algorithms. We evaluate the algorithms in a simulation based model of a real data centre. Results show significant energy savings potential, in some cases up to 40%, by integrating workload and thermal management.

This paper formalises a packing problem that emerges as a core sub-problem for managing workload consolidation in data centres. As a generalisation of the Bin Packing (BP) problem, it considers a set of tasks (items) to be assigned to a set of machines (bins) under capacity constraints (CPU usage) on each machine. Unlike classic BP settings, items have a lifespan. We define the cost of using a bin as the product of the bin's capacity and the time for which it is used. This problem will be referred to as the Temporal Bin Packing problem (TBP). We formalise the problem and present optimisation models using Mixed Integer Programming (MIP) and Constraint Programming (CP) for two contrasting but equivalent perspectives on the problem. The Packing model (PA) extends traditional BP models while the Temporal model (TP) explicitly models time with a sequence of packing problems. In addition, symmetry breaking techniques are developed. Finally, we introduce both a lower bound and an upper bound on the objective function. Our empirical results suggest that the TBP is a rather challenging problem for complete solvers to prove optimality. While breaking symmetry considerably reduces the computational effort for both PA and TP models, the Packing model using CP should be considered for larger instances.

Energy consumption in data centres accounts for a significant proportion of national energy usage in many countries. One approach for reducing energy consumption is to improve the server usage efficiency via workload consolidation. However, there are two primary reasons why this is not done to a large extent. The first reason is that greater consolidation could result in violations of Service Level Agreements (SLAs) if resources are over-utilised. The second reason is that users specify the requirements of a virtual machine (VM) based on the maximum estimated usage for each resource over the whole life span of the VM, and usually over-estimate these maximum values to avoid possible contract violations. Typically, the VM will have significantly lower resource usage in most time periods. Recently, a number of methods have been proposed to predict resource usage of VMs. We show that although these prediction techniques are efficient when their performances are measured using well known metrics, a low prediction error can still result in significant violations of SLAs if not handled properly during workload allocation. Our results emphasise the importance of analysing workload prediction in conjunction with workload allocation techniques. We examine the impact of using predicted resource usage for optimal server consolidation. We investigate the occurrences of over-utilised resources on servers due to under-predicted resource usage. We propose methods to reduce the likelihood of such occurrences, both through the enforcement of safety capacities on the server side, and through biasing towards over-prediction on the VM side. The results indicate that an appropriate balance can be found between energy savings and non-violation of SLAs.

The power consumption of a data centre (DC)can be attributed to the power consumed for running the servers and to the computer room air conditioner (CRAC)power for cooling them. The challenge is to distribute the load among servers, controlling the number of active servers and optimally balancing IT and cooling power requirement. This goal demands integration of thermal, power and workload models that minimises a non-linear energy utilisation function. In this paper first we encode this problem using a non-linear objective function and use local search for solving it. We carryout simulation experiments using data provided by the Bluesimtool. The results encourage the effectiveness of our approach, showing that system-wide energy utilisation can be reduced using a holistic approach.

The electric rail sector, like many sectors, is looking for means to reduce its energy consumption and energy cost. In this work we consider the scenario where the utility provider charges based on the maximum consumption over a period. Therefore one wishes to schedule the departure of trains such that the aggregate load is balanced across time periods while satisfying timetabling and resource restrictions. We present an approach which combines the strengths of a number of research areas such as constraint programming, linear programming, mixed-integer programming, and large neighbourhood search. The empirical performance on instances from an ongoing research challenge demonstrates the approach's ability to dramatically reduce the overall energy cost. In addition, we are able to close a number of the instances for which we prove optimality.

Data centre energy requirements have grown massively in the last few years. One of the optimisation challenges for reducing its energy requirements is to keep servers well utilised by deciding which Virtual Machines (VMs) to migrate, where to migrate, when to migrate, and, when and which servers to switch on/off. Achieving this goal optimally requires the capability of predicting the future time-variable resource demands of VMs accurately and computing the plan for migrating VMs for efficient workload consolidation quickly. We call this Proactive Workload Consolidation Problem (PWCP). Solving PWCP as a giant monolithic problem with infinite time windows is impossible both for forecasting demands and optimal assignments of VMs to servers. We formulate PWCP in a more realistic way by defining a time window of a particular size in which the information is known more accurately and solve a - possibly infinite - sequence of optimisation problems moving forwards in time. The question is how far one is required to look ahead in terms of the number time-periods and still retain the minimum energy cost of a given horizon without violating the Service Level Agreements (SLAs). We perform investigations to understand the relationship between the number of time-periods considered in one optimisation step and migration-limits on the SLAs, energy cost, server-transition cost and migration cost. Our results suggest that looking ahead by only a few more time-periods can lead to more efficient resource provisioning over the entire horizon and consequently higher energy efficiency and close to no SLA violations.

This paper addresses the discovery of discriminative nary motifs in databases of labeled sequences. We consider databases made up of positive and negative sequences and define a motif as a set of patterns embedded in all positive sequences and subject to alignment constraints. We formulate constraints to eliminate redundant motifs and present a general constraint optimization framework to compute motifs that are exclusive to the positive sequences. We cast the discovery of closed and replication-free motifs in this framework and propose a two-stage approach whose last stage reduces to a minimum set covering problem. Experiments on protein sequence datasets demonstrate its efficiency.

Many network design problems arising in the fields of transportation, distribution and logistics require clients to be connected to facilities through a set of carriers subject to distance and capacity constraints. Here a carrier could be a cable, vehicle, salesman etc. The distance from a facility to client using a carrier could be expressed as signal loss, time spent, path length, etc. The capacity of a carrier could be interpreted as the maximum number of commodities that a carrier can carry, the maximum number of clients or links that a single carrier can visit, etc. The main decisions are to determine the number of carriers, assign clients to carriers, and design a network for each carrier subject to distance, capacity and some side constraints. In this paper, we focus on the Cable Routing Problem (CRP), which is NP-hard. We present a constraint-based local search algorithm and two efficient local move operators. The effectiveness of our approach is demonstrated by experimenting with 300 instances of the CRP taken from real-world passive optical network deployments in Ireland. The results show that our algorithm can scale to very large problem instances and it can compute good quality solutions in a very limited time.

Considerable effort has been invested over the years in ad-hoc algorithms for item set and pattern mining. Constraint programming has recently been proposed as a means to tackle item set mining tasks within a general modelling framework. We follow this approach to address the discovery of discriminative n-ary motifs in databases of labeled sequences. We define a n-ary motif as a mapping of n patterns to n class-wide embeddings and we restrict the interpretation of constraints on a motif to the sequences embedding all patterns. We formulate core constraints that minimize redundancy between motifs and introduce a general constraint optimization framework to compute common and exclusive motifs. We cast the discovery of closed and replication-free motifs in this framework for which we propose a two-stage approach based on constraint programming. Experimental results on datasets of protein sequences demonstrate the efficiency of the approach.

We consider a network design problem arising in the development of an all-optical future generation Internet network called a flex-grid. An optical island is a set of core nodes that can be fully interconnected by transparent wavelength routes. We present a mathematical model for finding an optimal optical island, show that it is an NP-hard problem, and present a decomposition for solving it. In a first phase, we choose network links and route the traffic over the resulting network. In the second phase, we allocate the light-paths associated with the traffic requests to individual fibres and spectrum segments on the fibres. This so-called routing and spectrum assignment (RSA) problem is a generalisation of the well-known routing and wavelength assignment problem (RWA) of conventional optical networks. Flex-grid optical networks allow us to bundle higher capacity connection requests by allocating channels in a number of contiguous frequency slots, providing increased throughput, as long as the connection length is below technological limits. We solve the first part of the decomposition with a large neighborhood search, and the second with a CP model using a single GEOST global constraint. Results for Ireland and Italy show that solutions of high quality can be found by this decomposition.

When solving a constraint satisfaction problem using a systematic backtracking method the branching scheme normally selects a variable to which a value is assigned. In this paper we refer to such strategies as eager branching schemes. These contrast with the alternative class of novel branchings considered in this paper whereby having selected a variable we proceed by removing values from its domain. In this paper we study such lazy branching schemes in depth. We define three lazy branchings based on k-way, binary and split branching. We show how each can be incorporated into MAC, and define a novel value ordering heuristic that is suitable in this setting. Our results show that lazy branching can significantly out-perform traditional branching schemes across a variety of problem classes. While, in general, neither lazy nor eager branching dominates the other, our results clearly show that choosing the correct branching scheme for a given problem instances can significantly reduce search effort. Therefore, we implemented a variety of branching portfolios for choosing amongst all of the branching strategies studied in this paper. The results demonstrate that a good branching scheme can be automatically selected for a given problem instances and that including lazy branching schemes in the portfolio significantly reduces runtime.

Combinatorial problems are ubiquitous in artificial intelligence and related areas. While there has been a significant amount of research into the design and implementation of solvers for combinatorial problems, it is well-known that there is still no single solver that performs best across a broad set of problem types and domains.This has motivated the development of portfolios of solvers. A portfolio typically comprises either many different solvers, instances of the same solver tuned in different ways, or some combination of these. However, current approaches to portfolio design take a static view of the process.Specifically, the design of the portfolio is determined offline, and then deployed in some setting.In this paper we propose an approach to evolving the portfolio over time based on the problems instances that it encounters.We study several challenges raised by such a dynamic approach, such as how to re-tune the portfolio over time.Our empirical results demonstrate that our evolving portfolio approach significantly out-performed the standard static approach in the case when the type of instances observed change over time.

We report on an emerging application focused on the design of resilient long reach passive optical networks using combinatorial optimisation techniques. The objective of the application is to determine the optimal position and capacity of a set of metro nodes. We specifically consider dual parented networks whereby each customer must be associated with two metro nodes. An important property of such a placement is resilience to single node failure. Therefore excess capacity should be provided at each metro node in order to ensure that customers can be redistributed amongst the metro sites. Our application, as well as finding optimal node placements, can compute the minimum level of excess capacity on all metro nodes. In this paper we present three alternative approaches to optimal metro node placement. We present a detailed analysis of the impact of different placement approaches on the distribution of excess capacity throughout the network. We show that preferential distributions occur in practice, based on a case-study in Ireland. Finally we show that load and excess capacity provision are independent of each other.

We present an application focused on the design of resilient long-reach passive optical networks. We specifically consider dual parented networks whereby each customer must be connected to two metro sites via a local exchange sites. An important property of such a placement is resilience to single metro node failure. The objective of the application is to determine the optimal position of a set of metro-nodes such that the total optical fibre length is minimised. We prove that the decision variant of this problem is NP-Complete. We present three alternative combinatorial optimisation approaches to finding an optimal metro node placement using: a mixed integer linear programming formulation of the problem, a hybrid approach that uses clustering as a preprocessing step, and, finally, a local search approach. We consider a detailed case-study based on a network for Ireland. The hybrid approach scales well and finds solutions that are close to optimal, with a runtime that is two orders-of-magnitude better than the MIP model. The local search approach is consistently good on all benchmarks.

A soft global constraint SOFTPREC has been proposed recently for solving optimisation problems involving precedence relations. In this paper we present new pruning rules for this global constraint. We introduce a pruning rule that improves propagation from the objective variable to the decision variables, which is believed to be harder to achieve. We further introduce a pruning rule based on linear programming, and thereby make SOFTPREC a hybrid of constraint programming and linear programming. We present results demonstrating the efficiency of the pruning rules.

The Quantified Constraint Satisfaction Problem(QCSP) is a generalization of the classical constraint satisfaction problem in which some variables can be universally quantified. This additional expressiveness can help model problems in which a subset of the variables take value assignments that are outside the control of the decision maker. Typical examples of such domains are game-playing, conformant planning and reasoning under uncertainty. In these domains decision makers need explanations when a QCSP does not admit a winning strategy. We present an approach to defining preferences amongst the requirements of a QCSP, and an approach to finding most preferred explanations of inconsistency based on preferences over relaxations of quantifiers and constraints. This paper unifies work from the fields of constraint satisfaction, explanation generation, and reasoning under preferences and uncertainty.

Call control features (e.g., call-divert, voice-mail) are primitive options to which users can subscribe off-line to personalise their service. The configuration of a feature subscription involves choosing and sequencing features from a catalogue and is subject to constraints that prevent undesirable feature interactions at run-time. When the subscription requested by a user is inconsistent, one problem is to find an optimal relaxation, which is a generalisation of the feedback vertex set problem on directed graphs, and thus it is an NP-hard task. We present several constraint programming formulations of the problem. We also present formulations using partial weighted maximum Boolean satisfiability and mixed integer linear programming. We study all these formulations by experimentally comparing them on a variety of randomly generated instances of the feature subscription problem.

Modern feature-rich telecommunications services offer significant opportunities to human users. To make these services more usable, facilitating personalisation is very important since it enhances the users' experience considerably. However, regardless how service providers organise their catalogues of features, they cannot achieve complete configurability due to the existence of feature interactions. Distributed Feature Composition (DFC) provides a comprehensive methodology, underpinned by a formal architecture model to address this issue. In this paper we present an approach based on using Binary Decision Diagrams (BDD) to find optimal reconfigurations of features when a user's preferences violate the technical constraints defined by a set of DFC rules. In particular, we propose hybridizing constraint programming and standard BDD compilation techniques in order to scale the construction of a BDD for larger size catalogues. Our approach outperforms the standard BDD techniques by reducing the memory requirements by as much as five orders-of-magnitude and compiles the catalogues for which the standard techniques ran out of memory.

Telecommunication services are playing an increasing and potentially disruptive role in our lives. As a result, service providers seek to develop personalisation solutions that put customers in charge of controlling and enriching their services. In this context, the personalisation approach consists of exposing a catalogue of call control features (e.g., call-divert, voice-mail) to end-users and letting them subscribe to a subset of features subject to a set of precedence and exclusion constraints. When a subscription is inconsistent, the problem is to find an optimal relaxation. We present a constraint programming formulation to find an optimal reconfiguration of features. We investigate the performance of maintaining arc consistency within branch and bound search. We also study the impact of maintaining mixed consistency, that is maintaining different levels of consistency on different sets of variables. We further present a global constraint and a set of filtering rules that exploit the structure of our problem. We theoretically and experimentally compare all approaches. Our results demonstrate that the filtering rules of the global constraint outperform all other approaches when a catalogue is dense, and mixed consistency pays off when a catalogue is sparse.