Recent advances have enabled Large Language Models (LLMs) to tackle reasoning tasks by generating chain-of-thought (CoT) rationales, yet these gains have largely applied to high-resource languages, leaving low-resource languages underperformed. In this work, we first investigate CoT techniques in extremely low-resource scenarios through previous prompting, model editing, and fine-tuning approaches. We introduce \emph{English-Pivoted CoT Training}, leveraging the insight that LLMs internally operate in a latent space aligned toward the dominant language. Given input in a low-resource language, we perform supervised fine-tuning to generate CoT in English and output the final response in the target language. Across mathematical reasoning benchmarks, our approach outperforms other baselines with up to 28.33% improvement in low-resource scenarios. Our analyses and additional experiments, including Mixed-Language CoT and Two-Stage Training, show that explicitly separating language understanding from reasoning enhances crosslingual reasoning abilities. To facilitate future work, we also release LC2024, the first benchmark for mathematical task in Irish, an extremely low-resource and endangered language. Our results and resources highlight a practical pathway to multilingual reasoning without extensive retraining in every extremely low-resource language, despite data scarcity.

25th ACM Interaction Design and Children 25th Conference (IDC 2026). June 22nd – 25th 2026, Brighton UK

Recent advances in Large Language Models (LLMs) have demonstrated promising capabilities, yet their performance in multilingual and low-resource settings remains modest. Existing benchmarks often exhibit cultural bias, restrict evaluation to text-only, rely on multiple-choice formats, and, more importantly, are ineffectual for extremely low-resource languages. To address these gaps, we introduce IRLBench, presented in parallel English and Irish, which is considered definitely endangered by UNESCO. Our benchmark consists of 12 representative subjects developed from the 2024 Irish Leaving Certificate exam, enabling fine-grained analysis of model capabilities across domains. By framing the task as long-form generation and leveraging the official marking scheme, it supports not only a comprehensive evaluation of correctness but also language fidelity. Our extensive experiments of leading closed-source and open-source LLMs reveal a persistent performance gap between English and Irish, in which models produce valid Irish responses less than 80% of the time, and answer correctly 55.8% of the time compared to 76.2% in English for the best-performing model. With Irish as the case study, our work exposes systemic weaknesses in today's multilingual LLMs and provides a rigorous benchmark for evaluating true multilingual capabilities. We release IRLBench and an accompanying evaluation codebase to enable future research on robust, culturally aware multilingual AI development.

Simulation-based clinical training generates rich multimodal data that remains underused due to fragmented modalities, annotation bottlenecks, weak provenance, and tools misaligned with educator workflows. We introduce ClinVision, an educator-in-the-loop platform that operationalizes end-to-end multimodal learning analytics: synchronized multi-camera review, ISBAR-aligned scoring (a validated clinical communication framework), and templated reports with jump-to-evidence provenance. Agentic AI - systems that act on behalf of users while preserving human authority - assists with phrasing under explicit control (accept/edit/reject) and visible provenance, supporting accountable use rather than prescriptive automation. An in-learning deployment with five educators revealed full ISBAR coverage and time-efficient workflows, though AI suggestions were used selectively. We surface three transferable design tensions (assistance vs. authority, structure vs. flexibility, evidence vs. overload) and demonstrate that workflow integration, temporal primitives, and background AI assistance may better support high-stakes assessment than analytics or automation alone.

This paper investigates the maximization of the achievable rate for users served by a high-altitude platform (HAP) acting as a flying base station in the downlink of rate-splitting multiple access (RSMA)-based terahertz (THz) communication systems. Considering the dynamic and uncertain environment caused by user mobility and molecular absorption effects, we propose a generative diffusion model (DM)-based deep reinforcement learning approach to address this challenge. The problem is formulated as a Markov decision process, aiming to maximize the long-term achievable rate for all users by jointly optimizing power allocation and the common rate splitting ratio. Moreover, the generative DM significantly improves the decision-making capabilities of a deep reinforcement learning algorithm, namely the deep deterministic policy gradient (DDPG). Experimental simulations demonstrate the effectiveness of the proposed DM-DDPG algorithm compared to alternative schemes.

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.

Induction motors are the primary way to convert electrical current into mechanical power. They are a fundamental component of industrial processes and equipment. Early fault detection and preventive maintenance are of great concern. In the last few years, many deep learning data-driven approaches have been used to detect faults in electric motors. This problem comes with two significant challenges: some faults are easier to detect using a specific sensor (e.g., vibration or current); in industrial applications, it is hard to obtain fault measurements. In most cases, only measurements of normal behaviour are available. This paper presents a multi-signal unsupervised anomaly detection system based on deep convolutional variational autoencoders (VAE). We use three sensors to sample from operating industrial motors: vibration, current, and magnetic flux. We divide the dataset into a training set, in which the network fits the nominal working condition of the motor. The system is then deployed in detection mode, analyzing the stream of data provided by the sensors. The experimental results show that the system accurately detects anomalies and has sufficient sensitivity to recognize changes in the motor load and behavior in practice.

As Artificial Intelligence (AI) continues to permeate various aspects of societies, understanding the disparities in AI knowledge and skills across different living areas becomes imperative. Small living areas have emerged as significant contributors to Europe's economy, offering an alternative to the bustling environment of larger cities for those seeking an improved quality of life. Nonetheless, they often encounter challenges related to digital infrastructure, access to financial resources, and digital skills gaps, limiting their economic and social growth prospects. This study investigates the digital and AI skills gaps in the context of small and large European living areas, shedding light on the potential hindrances to unleashing the full economic and social potentials of these regions in an AI-enabled economy. Drawing from a comprehensive dataset encompassing 4,006 respondents across eight EU countries, this research examines the current perceptions and understandings of AI and digital skills within two distinct population groups: residents of smaller living areas and their counterparts in larger communities. Through bivariate analysis, notable insights are revealed concerning trust in AI solutions and entities, self-assessed digital skills, AI Awareness, AI Attitudes and demography variables in both population groups. These insights may refer to the significance of addressing digital and AI skills gaps in fostering growth and preparedness for the AI-driven future. As AI becomes increasingly integral to various aspects of society, targeted interventions and policies are essential to bridge these gaps and enable individuals and communities to harness the transformative potential of AI-enabled economies.

The development of Large Language Models (LLMs) has predominantly focused on high-resource languages, leaving extremely low-resource languages like Irish with limited representation. This work presents UCCIX, a pioneering effort on the development of an open-source Irish-based LLM. We propose a novel framework for continued pre-training of LLMs specifically adapted for extremely low-resource languages, requiring only a fraction of the textual data typically needed for training LLMs according to scaling laws. Our model, based on Llama 2-13B [23], outperforms much larger models on Irish language tasks with up to 12% performance improvement, showcasing the effectiveness and efficiency of our approach. We also contribute comprehensive Irish benchmarking datasets, including IrishQA, a question-answering dataset, and Irish version of MT-bench [28]. These datasets enable rigorous evaluation and facilitate future research in Irish LLM systems. Our work aims to preserve and promote the Irish language, knowledge, and culture of Ireland in the digital era while providing a framework for adapting LLMs to other indigenous languages.

This paper presents a SAT instance generator using a Graph Variational Autoencoder (GVAE2SAT ) architecture that outperforms existing generative deep learning models in speed and requires minimal post-processing.Our computational analyses benchmark this model against current deep learning techniques, introducing advanced metrics for more accurate evaluation.This new model is unique in its ability to maintain partial satisfiability of SAT instances while significantly reducing computational time.Although no method perfectly addresses all challenges in generating SAT instances, our approach marks a significant step forward in the efficiency and effectiveness of SAT instance generation.

Model counting (#SAT) is the problem of computing the number of satisfying assignments for a given Boolean formula. It has a significant theoretical and practical interest. Tackling it can be challenging since the number of potential solution grows exponentially with the number of variables. Due to the inherent complexity of the problem, approaches to approximate model counting have been developed as a practical alternative. These methods extract the number of solutions within user-specified tolerance and confidence levels and in a fraction of the time required by exact model counters. However, even these methods require extensive computations, restricting their applicability to relatively small instances. In this paper, we propose a new approximate machine learning model counter that overcome this limitation. Predicting the number of solutions can be seen as a regression problem. We deploy an array of machine learning techniques trained to infer the approximate number of solutions based on statistical features extracted from a SAT propositional formula. Extensive numerical experiments performed on synthetic crafted and benchmark datasets show that learning approaches can provide a good approximation of the number of solutions with a much lower computational time and resource cost than the state-of-the-art approximate and exact model counters, making it possible to approximate the model count of instances previously out of reach. We then investigated the structural factors that lead to a high model count using AI explainability approaches.

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.

This article investigated the automatic recognition of felt and musically communicated emotions using electroencephalogram (EEG), electrocardiogram (ECG), and acoustic signals, which were recorded from eleven musicians instructed to perform music in order to communicate happiness, sadness, relaxation, and anger. Musicians' self-reports indicated that the emotions they musically expressed were highly consistent with those they actually felt. Results showed that the best classification performances, in a subject-dependent classification using a KNN classifier were achieved by using features derived from both the EEG and ECG (with an accuracy of 98.11%). Which was significantly more accurate than using ECG features alone, but was not significantly more accurate than using EEG features alone. The use of acoustic features alone or in combination with EEG and/or ECG features did not lead to better performances than those achieved with EEG plus ECG or EEG alone. Our results suggest that emotion detection of playing musicians, both felt and musically communicated, when coherent, can be classified in a more reliable way using physiological features than involving acoustic features. The reported machine learning results are a step toward the development of affective brain–computer interfaces capable of automatically inferring the emotions of a playing musician in real-time.

Metaheuristics are essential tools for efficiently solving combinatorial optimization problems in arising from many fields. As incomplete methods, metaheuristics can provide goodquality results in a very short time. Among these approaches, the Iterated Greedy algorithm (IG) has appeared as a powerful and flexible method for finding near-optimal solutions to combinatorial problems. In this paper, we conducted a comprehensive systematic literature review on the variants of IG approach, and its applications covering the period from its inception in 2007 up to 2022. To the best of our knowledge, this is the first work in which all operators and aspects of IG are discussed to provide a detailed idea about this approach.

The social context in relation to energy policies, energy supply, and sustainability concerns, as well as advances in more energy-efficient technologies is driving a need for a change in the manufacturing industry. In this paper, a hybrid ftowshop production system with blocking constraints is investigated from both sustainability and productivity dimensions. For an efficient solution to this proven NP-hard problem, we implemented a multi-objective iterated greedy algorithm first time to minimize the makespan and total energy consumption simultaneously. We provide small, medium, and large instances to benchmark our approach against non-dominated sorting genetic algorithm-II (NSGA-II) which shows efficiency of the proposed methodology.

Our goal in this paper is to significantly decrease the compiled size of a given Boolean instance with a large representation, while preserving as much information about the instance as possible. We achieve this by assigning values to a subset of the variables in such a way that the resulting instance has a much smaller representation than the original one, and its number of solutions is almost as high as the starting one. We call the set of variable instantiations that we make the selective backbone of the solutions that we keep. Large selective backbones allow for smaller representations, but also eliminate more solutions. We compare different methods of computing the selective backbone that offer the best compromise.

A significant challenge in detecting and mitigating bias is creating a mindset amongst AI developers to address unfairness. The current literature on fairness is broad, and the learning curve to distinguish where to use existing metrics and techniques for bias detection or mitigation is difficult. This survey systematises the state-of-the-art about distinct notions of fairness and relative techniques for bias mitigation according to the AI lifecycle. Gaps and challenges identified during the development of this work are also discussed.

The Boolean Satisfiability Problem (SAT) can be framed as a binary classification task. Recently, numerous machine and deep learning techniques have been successfully deployed to predict whether a CNF has a solution. However, these approaches do not provide a variables assignment when the instance is satisfiable and have not been used as part of SAT solvers. In this work, we investigate the possibility of using a machine-learning SAT/UNSAT classifier to assign a truth value to a variable. A heuristic solver can be created by iteratively assigning one variable to the value that leads to higher predicted satisfiability. We test our approach with and without probing features and compare it to a heuristic assignment based on the variable's purity. We consider as objective the maximisation of the number of literals fixed before making the CNF unsatisfiable. The preliminary results show that this iterative procedure can consistently fix variables without compromising the formula's satisfiability, finding a complete assignment in almost all test instances.

The extraction of meaningful features from CNF instances is crucial to applying machine learning to SAT solving, enabling algorithm selection and configuration for solver portfolios and satisfiability classification. While many approaches have been proposed for feature extraction, their relevance to these tasks is unclear. Their applicability and comparison of the information extracted and the computational effort needed are complicated by the lack of working or updated implementations, negatively affecting reproducibility. In this paper, we analyse the performance of five sets of features presented in the literature on SAT/UNSAT and problem category classification over a dataset of 3000 instances across ten problem classes distributed equally between SAT and UNSAT. To increase reproducibility and encourage research in this area, we released a Python library containing an updated and clear implementation of structural, graph-based, statistical and probing features presented in the literature for SAT CNF instances; and we define a clear pipeline to compare feature sets in a given learning task robustly. We analysed which of the computed features are relevant for the specific task and the tradeoff they provide between accuracy and computational effort. The results of the analysis provide insights into which features mostly affect an instance's satisfiability and which can be used to identify the problem's type. These insights can be used to develop more effective solver portfolios and satisfiability classification algorithms.

We study the graph coloring problem under two kinds of simultaneous restrictions. First we forbid some patterns to appear in the graph, where a pattern is a small subgraph. Second we only consider regular graphs, meaning that all nodes have the same degree. Having both types of constraints at once leads us to the discovery of new tractable classes for graph coloring. However, we also show that some classes of pattern-free graphs remain NP-Complete even after enforcing regularity. Based on the latter results, we provide several complementary ways to generate difficult graph coloring instances, relying on balancing the degree of the nodes and avoiding a particular subgraph. Our constructions are parameterizable, so characteristics of the instances like size (number of nodes) and density (number of edges) can be set to any value.

The potential for bias embedded in data to lead to the perpetuation of social injustice though Artificial Intelligence (AI) necessitates an urgent reform of data curation practices for AI systems, especially those based on machine learning. Without appropriate ethical and regulatory frameworks there is a risk that decades of advances in human rights and civil liberties may be undermined. This paper proposes an approach to data curation for AI, grounded in feminist epistemology and informed by critical theories of race and feminist principles. The objective of this approach is to support critical evaluation of the social dynamics of power embedded in data for AI systems. We propose a set of fundamental guiding principles for ethical data curation that address the social construction of knowledge, call for inclusion of subjugated and new forms of knowledge, support critical evaluation of theoretical concepts within data and recognise the reflexive nature of knowledge. In developing this ethical framework for data curation, we aim to contribute to a virtue ethics for AI and ensure protection of fundamental and human rights.

This paper presents the hybrid, flexible flowshop problem with transportation times between stages, which is an extension of an existing scheduling problem that is well-studied in the literature. We explore different models for the problem with Constraint Programming, MILP, and local search, and compare them on generated benchmark problems that reflect the problem of the industrial partner. We then study two different factory layout design problems, and use the optimization tool to understand the impact of the design choices on the solution quality.

The Boolean Satisfiability Problem (SAT) was the first known NP-complete problem and has a very broad literature focusing on it. It has been applied successfully to various real-world problems, such as scheduling, planning and cryptography. SAT problem feature extraction plays an essential role in this field. SAT solvers are complex, fine-tuned systems that exploit problem structure. The ability to represent/encode a large SAT problem using a compact set of features has broad practical use in instance classification, algorithm portfolios, and solver configuration. The performance of these techniques relies on the ability of feature extraction to convey helpful information. Researchers often craft these features "by hand" to capture particular structures of the problem. Instead, in this paper, we extract features using semi-supervised deep learning. We train a convolutional autoencoder (AE) to compress the SAT problem into a limited latent space and reconstruct it minimizing the reconstruction error. The latent space projection should preserve much of the structural features of the problem. We compare our approach to a set of features commonly used for algorithm selection. Firstly, we train classifiers on the projection to predict if the problems are satisfiable or not. If the compression conveys valuable information, a classifier should be able to take correct decisions. In the second experiment, we check if the classifiers can identify the original problem that was encoded as SAT. The empirical analysis shows that the autoencoder is able to represent problem features in a limited latent space efficiently, as well as convey more information than current feature extraction methods.

Much of the focus on explanation in the field of artificial intelligence has focused on machine learning methods and, in particular, concepts produced by advanced methods such as neural networks and deep learning. However, there has been a long history of explanation generation in the general field of constraint satisfaction, one of the AI's most ubiquitous subfields. In this paper we survey the major seminal papers on the explanation and constraints, as well as some more recent works. The survey sets out to unify many disparate lines of work in areas such as model-based diagnosis, constraint programming, Boolean satisfiability, truth maintenance systems, quantified logics, and related areas.

This paper introduces the notion of ‘Privacy-Anomaly Detection’ and considers the question of whether behaviour-based anomaly detection approaches can have a privacy semantic interpretation and whether the detected anomalies can be related to the conventional (formal) definitions of privacy semantics. The idea is to learn user's past querying behaviour in terms of privacy and then identify deviations from past behaviour in order to detect privacy violations. Privacy attacks, violations of formal privacy definition, based on a sequence of SQL queries (query correlations) are considered in this paper and it is shown that interactive querying settings are vulnerable to privacy attacks based on query sequences. Investigation on whether these types of privacy attacks can potentially manifest themselves as anomalies, specifically as privacy-anomalies was carried out. It is shown, in this paper, that behaviour-based anomaly detection approaches have the potential to detect privacy attacks based on query sequences (violation of formal privacy definition) as privacy-anomalies.

Natural language processing and machine learning are gaining wide popularity in supporting judicial decision-making. Research in this area is particularly active. However, a methodological issue in the use of AI methods can lead to poor statistical soundness in the results. We consider and improve the work of Aletras et. al. [1] for predicting the outcome of cases at the European Court of Human Rights. We replicate their experiments using a more statistically reliable methodology and analyzed the results using state-of-the-art Bayesian techniques for classifier comparison. We also improved classification accuracy using an ensemble-based approach. These techniques will widely improve the statistical soundness of machine learning applications in law by providing robust baselines for comparison.

Many modern combinatorial solvers have a variety of parameters through which a user can customise their behaviour. Algorithm configuration is the process of selecting good values for these parameters in order to improve performance. Time and again algorithm configuration has been shown to significa ntly improve the performance of many algorithms for solving challenging computational problems. Automated systems for tuning parameters regularly out-perform human experts, sometimes but orders of magnitude. Online algorithm configurators, such as ReACTR, are able to tune a solver online without incurring costly offline training. As such ReACTR’s main focus is on runtime minimisation while solving combinatorial problems. To do this ReACTR adopts a one-pass methodology where each instance in a stream of instances to be solved is considered only as it arrives. As such ReACTR’s performance is sensitive to the order in which instances arrive. It is still not understood which instance orderings positively or negatively effect the performance of ReACTR. This paper investigates the effect of instance ordering and grouping by empirically evaluating different instance orderings based on difficulty and feature values. Though the end use is generally unable to control the order in which instances arrive it is important to understand which orderings impact Re- ACTR’s performance and to what extent. This study also has practical benefit as such orderings can occur organically. For example as business grows the problems it may encounter, such as routing or scheduling, often grow in size and difficulty. ReACTR’s performance also depends strongly configuration selection procedure used. This component controls which configurations are selected to run in parallel from the internal configuration pool. This paper evaluates various ranking mechanisms and different ways of combining them to better understand how the candidate selection procedure affects realtime algorithm configuration. We show that certain selection procedures are superior to others and that the order which instances arrive in determines which selection procedure performs best. We find that both instance order and grouping can significantly affect the overall solving time of the online automatic algorithm configurator ReACTR. One of the more surprising discoveries is that having groupings of similar instances can actually negatively impact on the overall performance of the configurator. In particular we show that orderings based on nearly any instance feature values can lead to significant reductions in total runtime over random instance orderings. In addition, certain candidate selection procedures are more suited to certain orderings than others and selecting the correct one can show a marked improvement in solving times.

The heart of any enterprise is its databases where the application data is stored. Organizations frequently place certain access control mechanisms to prevent access by unauthorized employees. However, there is persistent concern about malicious insiders. Anomaly-based intrusion detection systems are known to have the potential to detect insider attacks. Accurate modelling of insiders behaviour within the framework of Relational Database Management Systems (RDBMS) requires attention. The majority of past research considers SQL queries in isolation when modelling insiders behaviour. However, a query in isolation can be safe, while a sequence of queries might result in malicious access. In this work, we consider sequences of SQL queries when modelling behaviours to detect malicious RDBMS accesses using frequent and rare item-sets mining. Preliminary results demonstrate that the proposed approach has the potential to detect malicious RDBMS accesses by insiders.

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.

Kidney exchange programs enable willing, but incompatible, donor-patient pairs to swap donors, thus allowing persons suffering from organ failure to access transplantation. Choosing which pairs to match requires solving a stochastic online optimization problem where patients and donors arrive over time. Despite this, most of the related scientific literature has focused on deterministic offline models. In this paper, we present a simple approach to employ a model for the offline Kidney Exchange Problem (KEP) as the basis of an on-line anticipatory algorithm. Our approach grounds on existing techniques for the on-line KEP, but it generalizes them and provides a more accurate estimate of the expected impact of current decisions. In an experimentation based on a state-of-the-art donor pool generation method, the approach provides improvements in terms of quality and is able to deal with realistic instance size in reasonable time.

In constraint satisfaction problems, constrainedness provides a way to predict the number of solutions: for instances of a same size, the number of constraints is inversely correlated with the number of solutions. However, there is no obvious equivalent metric for stable matching problems. We introduce the contrarian score, a simple metric that is to matching problems what constrainedness is to constraint satisfaction problems. In addition to comparing the contrarian score against other potential tightness metrics, we test it for different instance sizes as well as extremely distinct versions of the stable matching problem. In all cases, we find that the correlation between contrarian score and number of solutions is very strong.

Stable Marriage (SM) is a well-known matching problem, where the aim is to match a set of men and women. The resulting matching must satisfy two properties: there is no unassigned person and there are no other assignments where two people of opposite gender prefer each other to their current assignments. We propose a new version of SM called as Robust Stable Marriage (RSM) by combining stability and robustness. We define robustness by introducing (a,b)-supermatches, which has been inspired by (a,b)-supermodels. An (a,b)-supermatch is a stable matching, where if at most a pairs want to break up, it is possible to find another stable matching by breaking at most b other pairs.

We study the problem of matching a set of applicants to a set of posts, where each applicant has an ordinal preference list, which may contain ties, ranking a subset of posts. A matching M is popular if there exists no matching M' where more applicants prefer M' to M . Several notions of optimality are studied in the literature for the case of strictly ordered preference lists. In this paper we address the case involving ties and propose novel algorithmic and complexity results for this variant. Next, we focus on the NP-hard case where additional copies of posts can be added in the preference lists, called Popular Matching with Copies. We define new dominance rules for this problem and present several novel graph properties characterising the posts that should be copied with priority. We present a comprehensive set of experiments for the popular matching problem with copies to evaluate our dominance rules as well as the different branching strategies. Our experimental study emphasizes the importance of the dominance rules and characterises the key aspects of a good branching strategy.

Many real-life problems can be formulated as boolean satisfiability (SAT). In addition, in many of these problems, there are some hard clauses that must be satisfied but also some other soft clauses that can remain unsatisfied at some cost. These problems are referred to as Weighted Partial Maximum Satisfiability (WPMS). For solving them, the challenge is to find a solution that minimizes the total sum of costs of the unsatisfied clauses. Configuration problems are real-life examples of these, which involve customizing products according to a user's specific requirements. In the literature there exist many efficient techniques for finding solutions having minimum total cost. However, less attention has been paid to the fact that in many real-life problems the associated weights for soft clauses can be unknown. An example of such situations is when users cannot provide local preferences but instead express global preferences over complete assignments. In these cases, the acquisition of preferences can be the key for finding the best solution. In this paper, we propose a method to formalize the acquisition of local preferences. The process involves solving the associated system of linear equations for a set of complete assignments and their costs. Furthermore, we formalize the characteristics and size of the complete assignments required to acquire all local weights. We present an heuristic algorithm that searches for such assignments which performs promisingly on many benchmarks from the literature.

We study the notion of robustness in stable matching problems. We first define robustness by introducing (a,b)-supermatches. An (a,b)-supermatch is a stable matching in which if a pairs break up it is possible to find another stable matching by changing the partners of those a pairs and at most b other pairs. In this context, we define the most robust stable matching as a (1,b)-supermatch where b is minimum. We show that checking whether a given stable matching is a (1,b)-supermatch can be done in polynomial time. Next, we use this procedure to design a constraint programming model, a local search approach, and a genetic algorithm to find the most robust stable matching. Our empirical evaluation on large instances show that local search outperforms the other approaches.

We propose a constraint programming approach to the popular matching problem. We show that one can use the Global Cardinality Constraint to encode the problem even in cases that involve ties in the ordinal preferences of the applicants.

Boliden Tara Mines Ltd. consumed 184.7 GWh of electricity in 2014, equating to over 1% of the national demand of Ireland or approximately 35,000 homes. Ireland’s industrial electricity prices, at an average of 13 c/KWh in 2014, are amongst the most expensive in Europe. Cost effective electricity procurement is ever more pressing for businesses to remain competitive. In parallel, the proliferation of intelligent devices has led to the industrial Internet of Things paradigm becoming mainstream. As more and more devices become equipped with network connectivity, smart metering is fast becoming a means of giving energy users access to a rich array of consumption data. These modern sensor networks have facilitated the development of applications to process, analyse, and react to continuous data streams in real-time. Subsequently, future procurement and consumption decisions can be informed by a highly detailed evaluation of energy usage. With these considerations in mind, this paper uses variable energy prices from Ireland’s Single Electricity Market, along with smart meter sensor data, to simulate the scheduling of an industrial-sized underground pump station in Tara Mines. The objective is to reduce the overall energy costs whilst still functioning within the system’s operational constraints. An evaluation using real-world electricity prices and detailed sensor data for 2014 demonstrates significant savings of up to 10.72% over the year compared to the existing control systems.

In cloud systems, computation time can be rented by the hour and for a given number of processors. Thus, accurate predictions of the behaviour of both sequential and parallel algorithms has become an important issue, in particular in the case of costly methods such as randomized combinatorial optimization tools. In this work, our objective is to use machine learning to predict performance of sequential and parallel local search algorithms. In addition to classical features of the instances used by other machine learning tools, we consider data on the sequential runtime distributions of a local search method. This allows us to predict with a high accuracy the parallel computation time of a large class of instances, by learning the behaviour of the sequential version of the algorithm on a small number of instances. Experiments with three solvers on SAT and TSP instances indicate that our method works well, with a correlation coefficient of up to 0.85 for SAT instances and up to 0.95 for TSP instances.

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.

Critique graphs were introduced as a device for analysing the behaviour of conversational recommender systems. A conversational recommender allows a user to critique a recommended product with statements such as "I'd like a similar product to this one, but cheaper". A critique graph is a directed multigraph in which the nodes represent products, and a directed edge between a pair of products represents how a user can move from one product to another by tweaking a particular product feature. It has been shown that critique graphs are not symmetric: if a user critiques a product pi and is presented with product pj, critiquing product pj in the opposite manner does not necessarily return product pi. Furthermore, it might not be possible to reach all products in a catalogue starting from a given product, or as a consequence of a particular critique some products become unreachable. This latter point is quite unsatisfactory since a user would assume that it is possible to explore the full catalogue by critiquing alone. A number of approaches to overcoming this problem have been proposed in the literature. In this paper we propose a novel approach that exploits the critique graph directly. Specifically, the unreachability is a consequence of a critique graph having more than one strongly connected component. We show how the critique graph can be modified in a minor way, thereby modifying the semantics of critiquing for a given catalogue, so that all products are always reachable.

Frequent itemset mining is one of the most common of data mining tasks. In its simplest form, one is given a table of data in which the columns represent attributes and each row specifies a value for each attribute, each attribute-value pair being referred to as an item. The task is to find sets of these items that occur frequently in the data, where frequency is specified as a minimum occurrence threshold. Such frequent sets of items are referred to as "frequent itemsets". Many efficient techniques have been developed for finding all frequent itemsets. However, a practical problem is that the results sets can be exponentially large in the number of items. In this paper we propose representative frequent itemset mining in which the set of itemsets returned provide examples of the space of all possible frequent itemsets. Specifically, every item that appears in a frequent itemset at least once is shown in at least one representative itemset. If there are frequent itemsets without a particular item, one such example will be presented. One can generalise our framework to seek representative sets in which pairs, triples, etc. of frequent itemsets are presented. One can see the representative frequent itemset framework as a generalisation of traditional frequent itemset mining that provides an additional parameter for controlling the size of the result set. Specifically, one has access to the traditional frequency threshold, but also the maximum arity of the tuples of itemsets being exemplified. We propose a dedicated algorithm that significantly outperforms using a state-of-the-art itemset miner in generating representative itemsets.

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.

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.

We present a greedy version of an existing metaheuristic al-gorithm for a special version of the Cutting Stock Problem(CSP). For this version, it is only possible to have indirectcontrol over the patterns via a vector of continuous valueswhich we refer to as a weights vector. Our algorithm itera-tively generates new weights vectors by making local changesover the best weights vector computed so far. This allows usto achieve better solutions much faster than is possible withthe original metaheuristic.

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.

This paper outlines an online approach for algorithm configuration which uses the power of modern multicore system to evaluate multiple parameters configurations in parallel.

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.

The dial-a-ride problem is a classic challenge in transportation and continues to be relevant across a large spectrum of applications, e.g. door-to-door transportation services, patient transportation, etc. Recently a new variant of the dial-a-ride problem, called ride-sharing, has received attention due to emergence of the use of smartphone-based applications that support location-aware transportation services. The general dial-a-ride problem involves complex constraints on a time-dependent network. In ride-sharing riders (resp. drivers) specify transportation requests (resp. offers) between journey origins and destinations. The two sets of participants, namely riders and drivers, have different constraints; the riders have time windows for starting and finishing the journey, while drivers have a starting time window, a destination, and a vehicle capacity. The challenge is to maximise the overall utility of the participants in the system which can be defined in a variety of ways. In this paper we study variations of the ride-sharing problem, under different notions of utility, from a computational complexity perspective, and identify a number of tractable and intractable cases. These results provide a basis for the development of efficient methods and heuristics for solving problems of real-world scale.

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.

Data uncertainty in real-life problems is a current challenge in many areas, including Operations Research (OR) and Constraint Programming (CP). This is especially true given the continual and accelerating increase in the amount of data associated with real-life problems, to which Large Scale Combinatorial Optimization (LSCO) techniques may be applied. Although data uncertainty has been studied extensively in the literature, many approaches do not take into account the partial or complete lack of information about uncertainty in real-life settings. To meet this challenge, in this paper we present a strategy for extrapolating data from limited uncertain information to ensure a certain level of robustness in the solutions obtained. Our approach is motivated by real-world applications of supply of timber from forests to saw-mills.

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.

The success or failure of a solver is oftentimes closely tied to the proper configuration of the solver's parameters. However, tuning such parameters by hand requires expert knowledge, is time consuming, and is error-prone. In recent years, automatic algorithm configuration tools have made significant advances and can nearly always find better parameters than those found through hand tuning. However, current approaches require significant offline computational resources, and follow a train-once methodology that is unable to later adapt to changes in the type of problem solved. To this end, this paper presents Real-time Algorithm Configuration through Tournaments (ReACT), a method that does not require any offline training to perform algorithm configuration. ReACT exploits the multi-core infrastructure available on most modern machines to create a system that continuously searches for improving parameterizations, while guaranteeing a particular level of performance. The experimental results show that, despite the simplicity of the approach, ReACT quickly finds a set of parameters that is better than the default parameters and is competitive with state-of-the-art algorithm configurators.

The success and power of algorithm selection techniques has been empirically demonstrated on numerous occasions, most noticeably in the competition settings like those for SAT, CSP, MaxSAT, QBF, etc. Yet while there is now a plethora of competing approaches, all of them are dependent on the quality of a set of structural features they use to distinguish amongst the instances. Over the years, each domain has defined and refined its own set of features, yet at their core they are mostly a collection of everything that was considered useful in the past. As an alternative to this shotgun generation of features, this paper instead proposes a more systematic approach. Specifically, the paper shows how latent features gathered from matrix decomposition are enough for a linear model to achieve a level of performance comparable to a perfect Oracle portfolio. This information can, in turn, help guide researchers to the kinds of structural features they should be looking for, or even just identifying when such features are missing.

COMPUTATIONAL sustainability is concerned with the development and application of computational methods for balancing environmental, economic, and societal needs for a sustainable future [1]. Specifically, it considers the major problem domains that impact global sustainability, those technologies and processes that offer the greatest opportunity to increase sustainability in these domains, and the fundamental computational methods that support these technologies and processes. The literature demonstrates that key sustainability issues translate into decision and optimization problems that fall within the realm of computing and information science, but generally they have not been studied by computer scientists. Computational sustainability encompasses problems in disciplines as diverse as ecology, natural resources, atmospheric science, materials science, renewable energy, and biological and environmental engineering. According to the Brundtland Commission [2], sustainable development is development that meets the needs of the present generation without compromising the ability of future generations to meet their own needs. Computational sustainability is a new interdisciplinary field [1] that aims to apply techniques from computer science and related fields, namely information science, operations research, applied mathematics, and statistics, to applications related to sustainable development. The range of problems that fall under computational sustainability is rather wide, encompassing computational challenges in disciplines as diverse as ecology, natural resources, atmospheric science, biological and environmental engineering, and land use, conservation, or transportation planning. Research in computational sustainability is necessarily interdisciplinary. The objective of this special section is to promote awareness and deepen understanding of the critical role computer science and computational methods can play in studying and providing solutions to sustainability-related problems. The special section also aims to provide a resource to the research community that we hope will assist in developing the expertise that society will need to address sustainability challenges by inspiring scientists to pursue sustainability-related research. Finally, this special section showcases a variety of cutting-edge techniques and methods that address the scale and complexity of the challenges facing societal efforts to move towards sustainability. Collaboration between computer scientists and fields more traditionally associated with sustainability-related research provides an opportunity to introduce enhanced or new computational methods and techniques to advance work in numerous disciplines. We hope that this special section will also appeal to those working outside computer science, demonstrating what that discipline has to offer to the broader sustainability agenda. We have selected seven papers to be included in this special section, covering a variety of computational sustainability topics. In “Nationwide Prediction of Drough Conditions in Iran Based on Remote Sensing Data,” Mahdi Jalili, Joobin Gharibshah, Seyed Morsal Ghavami, Mohammadreza Beheshtifar, and Reza Farshi, propose the use of artificial neural networks to model and predict the drough conditions based on satellite imagery collecting indexes on vegetation and land cover as well as the temperature. The paper applies multi-layer neural networks, radial-base function networks and support vector machines to the drough forecasting. The three models have been trained with time series and predict the drough conditions in terms of Standardized Precipitation Index. The accuracy of the model achieves up to the 90 percent and the multi-layer perception model is the best performing predictor. Marco Chiarandini, Niels H. Kjeldsen, and Napoleao Nepomuceno, in their paper entitled “Integrated Planning of Biomass Inventory and Energy Production,” essentially merge two problems that have been traditionally kept separate, namely biomass provisioning and its use for heating or energy production of each power plant. The paper proposes a stochastic 0-1 MILP to model the problem. Due to the large instance size, a relaxation of the problem and a Benders decomposition approach are compared in terms of solution quality, ease of implementation, and scalability, showing good accuracy of the relaxed model, but a simpler implementation and higher scalability for the Benders decomposition approach. Sensing and monitoring of environmental phenomena is an important part of computational sustainability; a promising approach is community sensing, where measurements are gathered by individual agents, and aggregated into publicly available maps by a public authority. In their paper entitled “Incentive Mechanisms for Community Sensing,” Boi Faltings, Jason Jingshi Li, and Radu Jurca, present a novel, game theoretic incentive mechanism that rewards accurate and truthful measurements in a community sensing scenario, providing the necessary quality control, and ensuring that the results are valid despite the absence of a centralized control. The scheme is analyzed and evaluated in a testbed of 88 IEEE TRANSACTIONS ON COMPUTERS, VOL. 63, NO. 1, JANUARY 2014

We describe a constraint-based timetabling system that was developed for the dental school based at Cork University Hospital in Ireland. This system has been deployed since 2010. Dental school timetabling differs from other university course scheduling in that certain clinic sessions can be used by multiple courses at the same time, provided a limit on room capacity is satisfied. Starting from a constraint programming solution using a web interface, we have moved to a mixed integer programming-based solver to deal with multiple objective functions, along with a dedicated Java application, which provides a rich user interface. Solutions for the years 2010, 2011 and 2012 have been used in the dental school, replacing a manual timetabling process, which could no longer cope with increasing student numbers and resulting resource bottlenecks. The use of the automated system allowed the dental school to increase student numbers to the maximum possible given the available resources. It also provides the school with a valuable “what-if” analysis tool.

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.

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.

Physical access control policies define sets of rulesthat govern people's access to physical resources such asrooms and buildings. While simple decision-precedence can be used to reconcile different rules that result in conflicting access decisions, the presence of rule conflicts and other rule anomalies can make it difficult for a policy-administrator to comprehend and effectively manage complex policies. In this paper we are concerned with discovering conflicts and computing relaxations of access policies in order to eliminate conflicting rule instances. We propose several SAT based encodings in which these rule conflicts and anomalies areexpressed as explanation style problems. Relaxation techniques are in turn used to eliminate these anomalies by recommending what rules have to be revoked or what permissions have to beremoved from which rules. Moreover, we discuss a relaxation strategy that preserves most of the access constraints of theoriginal policy. Finally we provide a preliminary performancestudy of our techniques. Our approach is applicable to access control policies in general.

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 present a method for reducing the treewidth of a graph while preserving all of its minimal s - t separators up to a certain fixed size k . This technique allows us to solve s - t Cut and Multicut problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set or induce a connected graph) in linear time for every fixed number k of removed vertices. Our results have applications for problems that are not directly defined by separators, but the known solution methods depend on some variant of separation. For example, we can solve similarly restricted generalizations of Bipartization (delete at most k vertices from G to make it bipartite) in almost linear time for every fixed number k of removed vertices. These results answer a number of open questions in the area of parameterized complexity. Furthermore, our technique turns out to be relevant for ( H , C , K )- and ( H , C ,≤K)-coloring problems as well, which are cardinality constrained variants of the classical H -coloring problem. We make progress in the classification of the parameterized complexity of these problems by identifying new cases that can be solved in almost linear time for every fixed cardinality bound.

Constraint programming has become an important technology for solving hard combinatorial problems in a diverse range of application domains. It has its roots in artificial intelligence, mathematical programming, op- erations research, and programming languages. This paper gives a perspective on where constraint programming is today, and discusses a number of opportunities and challenges that could provide focus for the research community into the future.

Physical Access Controls, such as supervised doors, surveillance cameras and alarms, act as important points of demarcation between physical zones (areas/rooms) of different levels of trust. They do so by controlling personnel flow to and from areas in accordance with the enterprise security policy. A significant challenge in providing physical access control for (restricted) areas is attaining a degree of confidence that a Physical Access Control security configuration adequately addresses the threats. A misconfiguration may result in a threat of unapproved personnel access or the denial of approved personnel access to a restricted zone. In practice, Physical Access Control security configurations typically span multiple zones, involve many users and run to many thousands of access-control rules, and such complexity may increase the likelihood of misconfiguration. In this paper, a formal model for Physical Access Control security configurations is presented. This model, implemented in SAT, captures a number of unique anomalies specific to Physical Access Control domain. A preliminary set of experiments that evaluate our approach is presented.

This paper proposes to improve traditional what-if analysis for policy making by a novel integration of different components. When a simulator is available, a human expert, e.g., a policy maker, might understand the impact of her choices by running a simulator on a set of scenarios of interest. In many cases, when the number of scenarios is exponential in the number of choices, identifying the scenarios of interest might be particularly challenging. We claim that abandoning this generate and test approach could greatly enhance the decision process and the quality of political actions undertaken. In this paper we propose and experiment with one approach for combining simulation with a combinatorial optimization and decision making component. In addition, we propose two alternative approaches that can reasonably combine decision making with simulation in a coherent way and avoid the generate and test behaviour.

This paper presents a method for computing all the domain consequences of a constraint satisfaction problem. Domain consequences are a generalisation of prime implicates to multi-valued constraint problems. We define ordered automata to encode a large, potentially exponential, number of domain consequences. We design a range of algorithms that directly operate on this compact representation, with a complexity that depends on its size and not the size of the encoded set. This allows us to generate the domain consequences of a problem even for problems that have an exponential number of domain consequences. Furthermore, a simple empirical study illustrates the effectiveness of the method in compiling a large number of domain consequences, and the compactness of this representation.

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.

In many combinatorial problems one may need to model the diversity or similarity of assignments in a solution. For example, one may wish to maximise or minimise the number of distinct values in a solution. To formulate problems of this type, we can use soft variants of the well known AllDifferent and AllEqual constraints. We present a taxonomy of six soft global constraints, generated by combining the two latter ones and the two standard cost functions, which are either maximised or minimised. We characterise the complexity of achieving arc and bounds consistency on these constraints, resolving those cases for which NP-hardness was neither proven nor disproven. In particular, we explore in depth the constraint ensuring that at least k pairs of variables have a common value. We show that achieving arc consistency is NP-hard, however achieving bounds consistency can be done in polynomial time through dynamic programming. Moreover, we show that the maximum number of pairs of equal variables can be approximated by a factor 1/2 with a linear time greedy algorithm. Finally, we provide a fixed parameter tractable algorithm with respect to the number of values appearing in more than two distinct domains. Interestingly, this taxonomy shows that enforcing equality is harder than enforcing difference.

Constraint programming can be divided very crudely into modeling and solving. Modeling defines the problem, in terms of variables that can take on different values, subject to restrictions (constraints) on which combinations of variables are allowed. Solving finds values for all the variables that simultaneously satisfy all the constraints. However, the impact of constraint programming has been constrained by a lack of "user-friendliness''. Constraint programming has a major "declarative" aspect, in that a problem model can be handed off for solution to a variety of standard solving methods. These methods are embedded in algorithms, libraries, or specialized constraint programming languages. To fully exploit this declarative opportunity however, we must provide more assistance and automation in the modeling process, as well as in the design of application-specific problem solvers. Automated modelling and solving in constraint programming presents a major challenge for the artificial intelligence community. Artificial intelligence, and in particular machine learning, is a natural field in which to explore opportunities for moving more of the burden of constraint programming from the user to the machine. This paper presents technical challenges in the areas of constraint model acquisition, formulation and reformulation, synthesis of filtering algorithms for global constraints, and automated solving. We also present the metrics by which success and progress can be measured.

We present a novel approach to itemset mining whereby the set of all itemsets are compiled into a compact form, closely related to binary decision diagrams. While there were previous attempts to utilize decision diagrams for storing the set of frequent itemsets this is the first approach that does not rely on backtrack search to generate such a set. Our empirical evaluation demonstrates that our approach is complementary to current approaches.

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.

We present a method for reducing the treewidth of a graph while preserving all the minimal $s-t$ separators. This technique turns out to be very useful for establishing the fixed-parameter tractability of constrained separation and bipartization problems. To demonstrate the power of this technique, we prove the fixed-parameter tractability of a number of well-known separation and bipartization problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set). These results answer a number of open questions in the area of parameterized complexity.

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.

Abstract Multitrust provides a flexible approach to encoding trust metrics whereby definitions for trust propagation and aggregation are specified in terms of a semiring. Determining the degree of trust between principals across a trust network (TN) is, in turn, programmed as a (semiring‐based) soft‐constraint satisfaction problem. In this paper, we consider the use of semiring‐based metrics in reasoning about trust between coalition‐forming principals. The configurable nature of multitrust makes it well‐suited to modeling trust within coalitions: whether adding more principals to a coalition increases trust or decreases trust is captured by the definition of trust aggregation within the semiring. Copyright © 2010 John Wiley & Sons, Ltd.

Many complex real-world systems can be modeled using a graphical structure such as a constraint network. If the properties of such a structure can be exploited, many challenging computational tasks can have good typical-case runtimes even if they are theoretically intractable in general. In this paper we show that many real-world constraint networks induce binary networks that share a common underlying structural characterisation; namely, that their degree distributions exhibit preferential attachment. We report on a novel constraint network generator for random constraint networks that have a scale-free macrostructure. This scale-free generator is based on the well known Barabasi-Albert preferential attachment model. Using this model we demonstrate that real-world constraint networks exhibit degree distributions that are more like those found in scale-free graphs. We also show that the effect of standard degree-based search heuristics on real-world problems exhibiting power-law degree distributions is greater than problems with a uniform random structure. We also show that the backdoor sizes for preferentially attached constraint networks are smaller than those of uniform random problems. This paper provides a novel basis for studying realistic constraint models.

Product configuration is a major industrial application domain for constraint satisfaction techniques. Conditional constraint satisfaction problems (CCSPs) have been developed to represent configuration problems in a natural way. CCSPs are like constraint satisfaction problems (CSPs), but they may also include potential variables, which might or might not exist in any given solution, as well as classical variables, which are required to take a value in every solution. CCSPs model, for example, options on a car, for which the style of sunroof (a variable) only makes sense if the car has a sunroof at all. We show that existing techniques from formal methods and answer set programming can be used to naturally model CCSPs. We demonstrate configurators in both approaches. An advantage of these approaches is that the model builder does not have to reformulate the CCSP into a classic CSP, converting potential variables into classical variables by adding a ¿does not exist¿' value and modifying the problem constraints. Our configurators automatically reason about the model itself, enumerating all solutions and discovering several kinds of model flaws.

Inference in constraint programming is usually based on the deductions generated by individual constraints which are then communicated to other constraints through domain filtering. Frequently we find that this is a too coarse-grained form of communication since constraints could exchange more powerful forms of deductions that could help reduce the search effort. In this paper we propose a particular technique for enhancing inference in constraint programming, by generating deductions that involve tighter interleaving of constraints. We apply our method to the market split problem and obtain massive speed-ups which brings a new order of market split problems into the realm of solvability by means of constraint programming.

In many interactive decision making scenarios there is often no solution that satisfies all of the user's preferences. The decision process can be helped by providing explanations. Relaxations show sets of consistent preferences and, thus, indicate which preferences can be enforced, while exclusion sets show which preferences can be relaxed to obtain a solution. Many approaches have been proposed to generate relaxations of over-constrained sets of constraints. However, most focus on generating a single relaxation. In this paper we study a variety of heuristic methods for generating diverse sets of relaxations. We show that a heuristic based approach can generate diverse relaxations quickly enough to support user interaction. We also describe a prototype explanation visualisation tool that can help a user navigate over diverse sets of explanations.

A functional dependency is a logical relationship amongst the attributes that define a table of data. Specifically, a functional dependency holds when the values of a subset of the attributes in a dataset determine the values of one or more other attributes. Uncovering such dependencies is utilized in many domains, such as database design. We demonstrate that it can also be utilized in a recommendation context when datasets represent product catalogues. State-of-the-art approaches to discovering functional dependencies require a tabular representation of the data. However, product catalogues can sometimes be defined implicitly, for example, as a set of solutions to a combinatorial problem. Such combinatorial catalogues can have a very large number of products, thus making standard approaches to uncovering functional dependencies inapplicable. In this paper we present the first approach to computing functional dependencies over compiled knowledge representations which can often be small even for huge catalogues. In particular, we develop efficient algorithms that operate over decision diagrams, which allow us to handle catalogues that are out of reach for current approaches. We apply our algorithms to tabular and combinatorial benchmarks and detect a number of properties that could be considered as anomalies in product catalogues.

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.

A number of compact representation forms that are investigated in the knowledge compilation community are utilized in interactive product configuration and other forms of decision support. Multi-valued decision diagrams (MDDs) are particularly well suited for interactive configuration. However, for large variable domains MDDs can be unnecessarily large if many values are repeating on different edges. In this paper we suggest exploiting the repetitive occurrences of values through the introduction of pseudo-nodes. The technique can be easily applied over MDDs as well as their more succinct counterpart, interval decision diagrams (IDDs). The compactness of the resulting representations, layer-compressed MDDs (lcMDDs) and layer-compressed IDDs (lcIDDs), is demonstrated empirically on artificial and real-world instances.

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.

Critique-based conversational recommender systems are becoming common place, facilitating richer dialogues with the user than pure content-based or collaborative approaches. Most implementations of these systems combine similarity-based reasoning with constraints to enable users express preferences as critiques of products. Critiques are simple statements like "I like this product, but would prefer one that is less expensive". In this paper we exploit the fact that the repertoire of critiques available to the user is usually known ahead of interaction time to construct a critique graph representation of a catalogue. The critique graph provides a formal basis for reasoning about the set of products that can be reached using critiques from a given product. We introduce the concepts of product cover, support sets of products and catalogue cover. The latter is defined as a set of products from which all products in a catalogue can be reached using a specified best-case maximum number of critiques. We show that for the catalogues we considered, catalogue covers are typically small. We show that the sizes and distributions of product covers and support sets can be used to inform us of the structure of a catalogue and the challenges it would present for interactive navigation. We also propose the notion of a minimum catalogue cover as a set of "entry products" that ensure that all products in the catalogue can be reached by critiquing.

The (parameterized) feedback vertex set problem on directed graphs, which we refer to as the dfvs problem, is defined as follows: given a directed graph G and a parameter k, either construct a feedback vertex set of at most k vertices in G or report that no such set exists. Whether or not the dfvs problem is fixed-parameter tractable has been a well-known open problem in parameterized computation and complexity, i.e., whether the problem can be solved in time f(k)nO(1) for some function f. In this paper we develop new algorithmic techniques that result in an algorithm with running time 4k k! nO(1) for the dfvs problem, thus showing that this problem is fixed-parameter tractable.

The (parameterized) FEEDBACK VERTEX SET problem on directed graphs (i.e., the DFVS problem) is defined as follows: given a directed graph G and a parameter k , either construct a feedback vertex set of at most k vertices in G or report that no such a set exists. It has been a well-known open problem in parameterized computation and complexity whether the DFVS problem is fixed-parameter tractable, that is, whether the problem can be solved in time f ( k ) n O (1) for some function f . In this article, we develop new algorithmic techniques that result in an algorithm with running time 4 k k ! n O (1) for the DFVS problem. Therefore, we resolve this open problem.

Constraint programming offers a declarative approach to solving problems modeled as constraint satisfaction problems (CSPs). However, the precise specification of a set of constraints is sometimes not available, but may have to be learned, for instance, from a set of examples of its solutions and non-solutions. In general, one may wish to learn generalized CSPs involving classical, fuzzy, weighted or probabilistic constraints, for example. This paper introduces a unifying framework for CSP learning. The framework is generic in that it can be instantiated to obtain specific formulations for learning classical, fuzzy, weighted or probabilistic CSPs. In particular, a new formulation for classical CSP learning, which minimizes the number of examples violated by candidate CSPs, is obtained by instantiating the framework. This formulation is equivalent to a simple pseudo-boolean optimization problem, thus being efficiently solvable using many optimization tools.

Bids submitted in auctions are usually treated as enforceable commitments in most bidding and auction theory literature. In reality bidders often withdraw winning bids before the transaction when it is in their best interests to do so. Given a bid withdrawal in a combinatorial auction, finding an alternative repair solution of adequate revenue without causing undue disturbance to the remaining winning bids in the original solution may be difficult or even impossible. We have called this the "Bid-taker's Exposure Problem". When faced with such unreliable bidders, it is preferable for the bid-taker to preempt such uncertainty by having a solution that is robust to bid withdrawal and provides a guarantee that possible withdrawals may be repaired easily with a bounded loss in revenue.In this paper, we propose an approach to addressing the Bid-taker's Exposure Problem. Firstly, we use the Weighted Super Solutions framework [13], from the field of constraint programming, to solve the problem of finding a robust solution. A weighted super solution guarantees that any subset of bids likely to be withdrawn can be repaired to form a new solution of at least a given revenue by making limited changes. Secondly, we introduce an auction model that uses a form of leveled commitment contract [26, 27], which we have called mutual bid bonds, to improve solution reparability by facilitating backtracking on winning bids by the bid-taker. We then examine the trade-off between robustness and revenue in different economically motivated auction scenarios for different constraints on the revenue of repair solutions. We also demonstrate experimentally that fewer winning bids partake in robust solutions, thereby reducing any associated overhead in dealing with extra bidders. Robust solutions can also provide a means of selectively discriminating against distrusted bidders in a measured manner.

The security of a network configuration is based not just on the security of its individual components and their direct interconnections, but also on the potential for systems to interoperate indirectly across network routes. Such interoperation has

The partial constraint satisfaction paradigm focuses on solving relaxations of problems that either do not admit solutions, or that are either impractical or impossible to solve completely. The semiring-based framework for soft constraints is a unifying model for a variety of extensions of the constraint satisfaction formalism. For example, the semiring-based framework can represent weighted, fuzzy, probabilistic and set-based constraint satisfaction problems. We discuss how the semiring-based framework for soft constraints can be used to model partial constraint satisfaction problems. We show how the semiring framework can be used to capture a notion of distance between a solution and a problem based on the known distance metrics used in the partial constraint satisfaction literature. These solution-problem distance metrics can be seen as providing lower-bounds on the distance between a problem and its relaxation.

Constraint satisfaction is becoming the paradigm of choice for solving many real-world problems. To date, most approaches to constraint satisfaction have focused on solving a problem using some form of backtrack search. Furthermore, the typical view is that a constraint satisfaction problem will be solved only once. However, in many real-world contexts, problems are solved repeatedly over time. Also such problems often exhibit some structure. This motivates the application of some form of learning to improve the performance of search from previously discovered solutions. We present an approach that uses knowledge about known solutions to a problem to improve search. The approach we present is based on a combination of decision tree learning and constraint satisfaction. We demonstrate that significant improvements, almost an order-of-magnitude, in search effort can be achieved using this hybrid approach over traditional search. We also show that the space complexity using this approach is almost negligible. This work is of interest in domains such as product configuration, and interactive constraint solving in general where the system takes the initiative by asking questions.

The digital networked world is enabling and requiring a new emphasis on personalized document creation. The new, more dynamic digital environment demands tools that can reproduce both the contents and the layout automatically, tailored to personal needs and transformed for the presentation device, and can enable novices to easily create such documents. In order to achieve such automated document assembly and transformation, we have formalized custom document creation as a multiobjective optimization problem, and use a genetic algorithm to assemble and transform compound personalized documents. While we have found that such an automated process for document creation opens new possibilities and new workflows, we have also found several areas where further research would enable the approach to be more broadly and practically applied. This paper reviews the current system and outlines several areas where future research will broaden its current capabilities.