Interactive constraint systems often suffer from infeasibility (no solution) due to conflicting user constraints. A common approach to recover feasibility is to eliminate the constraints that cause the conflicts in the system. This approach allows the system to provide an explanation as: “if the user is willing to drop some of their constraints, there exists a solution”. However, this form of explanation might not be very informative. A counter-factual explanation is a type of explanation that can provide a basis for the user to recover feasibility by helping them understand what changes can be applied to their existing constraints rather than removing them. We propose an efficient approach NoPropCounter-factualXplain to find counter-factual explanations for infeasible problems. We also propose a version of this algorithm which takes into account preferences called PrefnoPropCounter-factualXplain. We showcase it's usability in real world scenario using the producer/consumer constraint which is useful in problems which involve resource allocation.

Interactive constraint systems often suffer from infeasibility (no solution) due to conflicting user constraints. A common approach to recover feasibility is to eliminate the constraints that cause the conflicts in the system. This approach allows the system to provide an explanation as: “if the user is willing to drop some of their constraints, there exists a solution”. However, this form of explanation might not be very informative. A counterfactual explanation is a type of explanation that can provide a basis for the user to recover feasibility by helping them understand what changes can be applied to their existing constraints rather than removing them. We propose an iterative method based on conflict detection and maximal relaxations in over-constrained constraint satisfaction problems to help compute a counterfactual explanation. We have evaluated our approach using well known instances that occur in industrial applications and demonstrated the relevance of multi-point relaxations.

Constraint programming has proven to be a successful framework for determining whether a given instance of the three-dimensional stable matching problem with cyclic preferences (3dsm-cyc) admits a solution. If such an instance is satisfiable, constraint models can even compute its optimal solution for several different objective functions. On the other hand, the only existing output for unsatisfiable 3dsm-cyc instances is a simple declaration of impossibility. In this paper, we explore four ways to adapt constraint models designed for 3dsm-cyc to the maximum relaxation version of the problem, that is, the computation of the smallest part of an instance whose modification leads to satisfiability. We also extend our models to support the presence of costs on elements in the instance, and to return the relaxation with lowest total cost for each of the four types of relaxation. Empirical results reveal that our relaxation models are efficient, as in most cases, they show little overhead compared to the satisfaction version.

We introduce five constraint models for the 3-dimensional stable matching problem with cyclic preferences and study their relative performances under diverse configurations. While several constraint models have been proposed for variants of the two-dimensional stable matching problem, we are the first to present constraint models for a higher number of dimensions. We show for all five models how to capture two different stability notions, namely weak and strong stability. Additionally, we translate some well-known fairness notions (i.e. sex-equal, minimum regret, egalitarian) into 3-dimensional matchings, and present how to capture them in each model. Our tests cover dozens of problem sizes and four different instance generation methods. We explore two levels of commitment in our models: one where we have an individual variable for each agent (individual commitment), and another one where the determination of a variable involves pairing the three agents at once (group commitment). Our experiments show that the suitability of the commitment depends on the type of stability we are dealing with. Our experiments not only led us to discover dependencies between the type of stability and the instance generation method, but also brought light to the role that learning and restarts can play in solving this kind of problems.

In many application problems, including physical security and wildlife conservation, infrastructure must be configured to ensure or deny paths between specified locations. We model the problem as sub-graph design subject to constraints on paths and path lengths, and propose length-bound reachability constraints. Although reachability in graphs has been modelled before in constraint programming, the interaction of positive and negative reachability has not been studied in depth. We prove that deciding whether a set of positive and negative reachability constraints are satisfiable is NP complete. We show the effectiveness of our approach on decision problems, and also on optimisation problems. We compare our approach with existing constraint models, and we demonstrate significant improvements in runtime and solution costs, on a new problem set.

In this paper we describe a complex optimization application arising in maintenance scheduling, developed in close collaboration with an industrial partner. We have to plan and schedule preventive and corrective maintenance activities at customer sites by a group of traveling repair technicians. A specific property of the problem considered here is a mix of customers in both urban centers and rural areas. This means that travel times between customers must be considered when balancing overall workload for each agent. We discuss a problem decomposition compatible with current management practice, describe different solvers for the individual problem steps, and show results on real-world data from the industrial partner.

Network on Chip (NoC) is a well known approach that aims at improving the performance of many-core systems. The design of such systems involves the optimal mapping of tasks to nodes, and the corresponding scheduling of the tasks at every node, which results in a challenging optimisation problem considering the constraints that need to be respected. In this paper, after formalising the problem and elaborating on its complexity, we present an AI approach to solve the problem and evaluate it against a MIP approach. Our empirical evaluation shows that the AI approach is able to obtain solutions of good quality very quickly.

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.

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.

A Wireless Sensor Network (WSN) is composed of many sensor nodes which transmit their data wirelessly over a multi-hop network to data sinks. Since WSNs are subject to node failures, the network topology should be robust, so that when a failure does occur, data delivery can continue from all surviving nodes. A WSN is k-robust if an alternate length-constrained route to a sink is available for each surviving node after the failure of up to k-1 nodes. Determining whether a network is k-robust is an NP-complete problem. We develop a Constraint Programming (CP) approach for solving this problem which outperforms a Mixed-Integer Programming (MIP) model on larger problems. A network can be made robust by deploying extra relay nodes, and we extend our CP approach to an optimisation problem by using QuickXplain to search for a minimal set of relays, and compare it to a state-of-the-art local search approach.

The k-medoids problem is a combinatorial optimisation problem with multiples applications in Resource Allocation, Mobile Computing, Sensor Networks and Telecommunications.Real instances of this problem involve hundreds of thousands of points and thousands of medoids.Despite the proliferation of parallel architectures, this problem has been mostly tackled using sequential approaches.In this paper, we study the impact of space-partitioning techniques on the performance of parallel local search algorithms to tackle the k-medoids clustering problem, and compare these results with the ones obtained using sampling.Our experiments suggest that approaches relying on partitioning scale more while preserving the quality of the solution.

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.