Search

In this paper we present a new approach to solve the satisfiability problem (SAT), based on boolean networks (BN). We define a mapping between a SAT instance and a BN, and we solve SAT problem by simulating the BN dynamics. We prove that BN fixed points correspond to the SAT solutions. The mapping presented allows to develop a new class of algorithms to solve SAT. Moreover, this new approach suggests new ways to combine symbolic and connectionist computation and provides a general framework for local search algorithms., Comment: 12 pages, 6 figures, 2 tables

This paper considers multi-stage optimization problems under uncertainty that involve distinct offline and online phases. In particular it addresses the issue of integrating these phases to show how the two are often interrelated in real-world applications. Our methods are applicable under two (fairly general) conditions: 1) the uncertainty is exogenous; 2) it is possible to define a greedy heuristic for the online phase that can be modeled as a parametric convex optimization problem. We start with a baseline composed by a two-stage offline approach paired with the online greedy heuristic. We then propose multiple methods to tighten the offline/online integration, leading to significant quality improvements, at the cost of an increased computation effort either in the offline or the online phase. Overall, our methods provide multiple options to balance the solution quality/time trade-off, suiting a variety of practical application scenarios. To test our methods, we ground our approaches on two real cases studies with both offline and online decisions: an energy management problem with uncertain renewable generation and demand, and a vehicle routing problem with uncertain travel times. The application domains feature respectively continuous and discrete decisions. An extensive analysis of the experimental results shows that indeed offline/online integration may lead to substantial benefits.

In data mining, finding interesting patterns is a challenging task. Constraint-based mining is a well-known approach to this, and one for which constraint programming has been shown to be a well-suited and generic framework. Constraint dominance programming (CDP) has been proposed as an extension that can capture an even wider class of constraint-based mining problems, by allowing us to compare relations between patterns. In this paper we improve CDP with the ability to specify an incomparability condition. This allows us to overcome two major shortcomings of CDP: finding dominated solutions that must then be filtered out after search, and unnecessarily adding dominance blocking constraints between incomparable solutions. We demonstrate the efficacy of our approach by extending the problem specification language ESSENCE and implementing it in a solver-independent manner on top of the constraint modelling tool CONJURE. Our experiments on pattern mining tasks with both a CP solver and a SAT solver show that using the incomparability condition during search significantly improves the efficiency of dominance programming and reduces (and often eliminates entirely) the need for post-processing to filter dominated solutions. Publisher PDF

One of the biggest challenges in the design of real-world decision support systems is coming up with a good combinatorial optimization model. Often enough, accurate predictive models (e.g. simulators) can be devised, but they are too complex or too slow to be employed in combinatorial optimization. In this paper, we propose a methodology called Empirical Model Learning (EML) that relies on Machine Learning for obtaining components of a prescriptive model, using data either extracted from a predictive model or harvested from a real system. In a way, EML can be considered as a technique to merge predictive and prescriptive analytics. All models introduce some form of approximation. Citing G.E.P. Box [1] “Essentially, all models are wrong, but some of them are useful”. In EML, models are useful if they provide adequate accuracy, and if they can be effectively exploited by solvers for finding high-quality solutions. We show how to ground EML on a case study of thermal-aware workload dispatching. We use two learning methods, namely Artificial Neural Networks and Decision Trees and we show how to encapsulate the learned model in a number of optimization techniques, namely Local Search, Constraint Programming, Mixed Integer Non-Linear Programming and SAT Modulo Theories. We demonstrate the effectiveness of the EML approach by comparing our results with those obtained using expert-designed models.

Power consumption is an increasingly limiting factor in modern ICT infrastructure, especially in the context of High Performance Computing. Common strategies to curb energy consumption are power capping, i.e. constraining the system power consumption within certain power budget, and Dynamic Voltage/Frequency Scaling, i.e. reducing the computing elements operating clock to decrease power usage. In this paper we tackle the frequency assignment problem in the context of a power capped system. We propose three approaches to solve the problem, a greedy algorithm, a CP model and MIP model. As a case study, we consider the Eurora supercomputer, hosted at CINECA computing center in Bologna. The experimental results show that the MIP approach outperforms the other methods when the problem is loosely constrained. With tighter bounds, the CP method can always find a solution, whereas the MIP fails to provide a solution for half of the considered instances.

In the past few years, the area of Machine Learning (ML) has witnessed tremendous advancements, becoming a pervasive technology in a wide range of applications. One area that can significantly benefit from the use of ML is Combinatorial Optimization. The three pillars of constraint satisfaction and optimization problem solving, i.e., modeling, search, and optimization, can exploit ML techniques to boost their accuracy, efficiency and effectiveness. In this survey we focus on the modeling component, whose effectiveness is crucial for solving the problem. The modeling activity has been traditionally shaped by optimization and domain experts, interacting to provide realistic results. Machine Learning techniques can tremendously ease the process, and exploit the available data to either create models or refine expert-designed ones. In this survey we cover approaches that have been recently proposed to enhance the modeling process by learning either single constraints, objective functions, or the whole model. We highlight common themes to multiple approaches and draw connections with related fields of research., Comment: Originally submitted to IJCAI2018

Optimization problems under uncertainty arise in many application areas and their solution is very challenging. We propose here methods that merge off-line and on-line decision stages: we start with a two stage off-line approach coupled with an on-line heuristic. We improve this baseline in two directions: (1) by replacing the on-line heuristics with a simple anticipatory method; (2) by making the off-line component aware of the on-line heuristic. Our approach is grounded on a virtual power plant management system, where the load shifts can be planned off-line and the energy balance should be maintained on-line. The overall goal is to find the minimum cost energy flows at each point in time considering (partially shiftable) electric loads, renewable and non-renewable energy generators, and electric storages. We compare our models with an oracle operating under perfect information and we show that both our improved models achieve a high solution quality, while striking different trade-offs in terms of computation time and complexity of the off-line and on-line optimization techniques.

Policy making is an extremely complex process occurring in changing environments and affecting the three pillars of sustainable development: society, economy and the environment. Each political decision in fact implies some form of social reactions, it affects economic and financial aspects and has substantial environmental impacts. Improving decision making in this context could have a huge beneficial impact on all these aspects. There are a number of Artificial Intelligence techniques that could play an important role in improving the policy making process such as decision support and optimization techniques, game theory, data and opinion mining and agent-based simulation. We outline here some potential use of AI technology as it emerged by the European Union (EU) EU FP7 project ePolicy: Engineering the Policy Making Life-Cycle, and we identify some potential research challenges.

Traffic simulators are effective tools to support decisions in urban planning systems, to identify criticalities, to observe emerging behaviours in road networks and to configure road infrastructures, such as road side units and traffic lights. Clearly the more realistic the simulator the more precise the insight provided to decision makers. This paper provides a first step toward the design and calibration of traffic micro-simulator to produce realistic behaviour. The long term idea is to collect and analyse real traffic traces collecting vehicular information, to cluster them in groups representing similar driving behaviours and then to extract from these clusters relevant parameters to tune the microsimulator. In this paper we have run controlled experiments where traffic traces have been synthetized to obtain different driving styles, so that the effectiveness of the clustering algorithm could be checked on known labels. We describe the overall methodology and the results already achieved on the controlled experiment, showing the clusters obtained and reporting guidelines for future experiments.

Demand Response mechanisms and load control in the electricity market represent an important area of research at international level, and the market liberalization is opening new perspectives. This calls for the development of methodologies and tools that energy providers can use to define specific business models. In this work we develop an optimization model to provide recommendations on time-of-use based prices to providers, taking into account some key factors of the customer and market behavior. We have tested our model on data from the Italian energy market, merging statistical census and population information. The main advantage of the model is that it provides a tool for sensitivity analysis, namely for understanding the impact of economical and behavioral parameters on the consumption profiles.

Power consumption is a critical aspect for next generation High Performance Computing systems: Supercomputers are expected to reach Exascale in 2023 but this will require a significant improvement in terms of energy efficiency. In this domain, power-capping can significant increase the final energy-efficiency by cutting cooling effort and worst-case design margins. A key aspect for an optimal implementation of power capping is the ability to estimate the power consumption of HPC applications before they run on the real system. In this paper we propose a Machine-Learning approach, based on the user and application resource request, to accurately predict the power consumption of typical supercomputer workloads. We demonstrate our method on real production workloads executed on the Eurora supercomputer hosted at CINECA computing center in Bologna and we provide useful insights to apply our technique in other installations.

Many real world cyclic scheduling problems involve applications that need to be repeated with different periodicity. For example, multirate control systems present multiple control loops that are organized hierarchically: the higher-level loop responds to the slower system dynamics and typically its period can be a few orders of magnitude longer than the lowest level. Cyclic scheduling problems can be cast into classical RCPSP instances via a technique called unfolding [4, 6], which causes graph expansion. In the case of multirate applications, this expansion can be significantly large. In this context, finding a high-quality allocation and schedule could be very challenging. In this paper, we propose a new Multirate Resource Constraint, modeling unary resources, that avoids graph expansion by exploiting the multirate nature of the schedule in its filtering algorithm. In an experimentation on synthetic and real-world instances, we show that our method drastically outperforms approaches based on state-of-the-art unfolding and constraint based scheduling.

Power consumption is a key factor in modern ICT infrastructure, especially in the expanding world of High Performance Computing, Cloud Computing and Big Data. Such consumption is bound to become an even greater issue as supercomputers are envisioned to enter the Exascale by 2020, granted that they obtain an order of magnitude energy efficiency gain. An important component in many strategies devised to decrease energy usage is “power capping”, i.e., the possibility to constrain the system power consumption within certain power budget. In this paper we propose two novel approaches for power capped workload dispatching and we demonstrate them on a real-life high-performance machine: the Eurora supercomputer hosted at CINECA computing center in Bologna. Power capping is a feature not included in the commercial Portable Batch System (PBS) dispatcher currently in use on Eurora. The first method is based on a heuristic technique while the second one relies on a hybrid strategy which combines a CP and a heuristic approach. Both systems are evaluated and compared on simulated job traces.

In past papers, we have introduced Empirical Model Learning (EML) as a method to enable Combinatorial Optimization on real world systems that are impervious to classical modeling approaches. The core idea in EML consists in embedding a Machine Learning model in a traditional combinatorial model. So far, the method has been demonstrated by using Neural Networks and Constraint Programming (CP). In this paper we add one more technique to the EML arsenal, by devising methods to embed Decision Trees (DTs) in CP. In particular, we propose three approaches: 1) a simple encoding based on meta-constraints; 2) a method using attribute discretization and a global table constraint; 3) an approach based on converting a DT into a Multi-valued Decision Diagram, which is then fed to an mdd constraint. We finally show how to embed in CP a Random Forest, a powerful type of ensemble classifier based on DTs. The proposed methods are compared in an experimental evaluation, highlighting their strengths and their weaknesses.

This paper is about characterizing the expected makespan of a Partial Order Schedule POS under duration uncertainty. Our analysis is based on very general assumptions about the uncertainty: in particular, we assume that only the min, max, and average durations are known. This information is compatible with a whole range of values for the expected makespan. We prove that the largest of these values and the corresponding "worst-case" distribution can be obtained in polynomial time and we present an $$On^3$$On3 computation algorithm. Then, using theoretical and empirical arguments, we show that such expected makespan is strongly correlated with certain global properties of the POS, and we exploit this correlation to obtain a linear-time estimator. The estimator provides accurate results under a very large variety of POS structures, scheduling problem types, and uncertainty models. The algorithm and the estimator may be used during search by an optimization approach, in particular one based on Constraint Programming: this allows to tackle a stochastic problem by solving a dramatically simpler and yet accurate deterministic approximation.

Renewable energy technologies have benefited to varying extent from the support of incentive programmes introduced in the industrialised countries over the last 20 years. Understanding the impact of incentive schemas on the adoption of renewable energy sources is a crucial aspect for policy makers. We study in this paper the impact of national incentives on photovoltaic plant diffusion in Italy by devising an agent-based simulator which is currently being tuned on real data and will help policy makers to forecast future adoptions.

This paper presents a Traffic Lights control system, inspired by Swarm intelligence methodologies, in which every intersection controller makes independent decisions to pursue common goals and is able to improve global traffic performance. The solution is low cost and widely applicable to different urban scenarios. This work is developed within the COLOMBO European project. Control methods are divided into macroscopic and microscopic control level methods. The former react to macroscopic key figures such as mean congestion length and mean traffic density and acts on the signal program choice or the development of the frame signal program. The latter include changes at short notice based on changes in the traffic flow: they include methods for signal program adaptation and development. The developed system has been widely tested on synthetic benchmarks with promising results.

A growing number of applications require continuous processing of high-throughput data streams, e.g., financial analysis, network traffic monitoring, or big data analytics. Performing these analyses by using Distributed Stream Processing Systems (DSPSs) in large clusters is emerging as a promising solution to address the scalability challenges posed by these kind of scenarios. Yet, the high time-variability of stream characteristics makes it very inefficient to statically allocate the data-center resources needed to guarantee application Service Level Agreements (SLAs) and calls for original, dynamic, and adaptive resource allocation strategies. In this paper we analyze the problem of planning adaptive replication strategies for DSPS applications under the challenging assumption of minimal statistical knowledge of input characteristics. We investigate and evaluate how different CP techniques can be employed, and quantitatively show how different alternatives offer different trade-offs between problem solution time and stream processing runtime cost through experimental results over realistic testbeds.

International audience; MinimaxWeighted Constraint Satisfaction Problems (formerly called QWCSPs) are a framework for modeling soft constrained problems with adversarial conditions. In this paper, we describe novel definitions and implementations of node, arc and full directional arc consistency notions to help reduce search space on top of the basic tree search with alpha-beta pruning for solving ultraweak solutions. In particular, these consistencies approximate the lower and upper bounds of the cost of a problem by exploiting the semantics of the quantifiers and reusing techniques from both Weighted and Quantified CSPs. Lower bound computation employs standard estimation of costs in the sub-problems used in alpha-beta search. In estimating upper bounds, we propose two approaches based on the Duality Principle: duality of quantifiers and duality of constraints. The first duality amounts to changing quantifiers from min to max, while the second duality re-uses the lower bound approximation functions on dual constraints to generate upper bounds. Experiments on three benchmarks comparing basic alpha-beta pruning and the six consistencies from the two dualities are performed to confirm the feasibility and efficiency of our proposal.

This contribution is aimed at providing an overview of the main Italian research areas and activities. In this chapter we first analyze the collaboration structure of Italian research, that involves more than eight hundred scholars and researchers from both the University and the Industry and, from a network perspective, it appears to be scale-free. Then, we briefly illustrate the main subjects of investigation and applications. AI research in Italy traces back to the '70s with an increase in the last twenty years and spans the main research AI areas, from automated reasoning and ontologies, to machine learning, robotics and evolutionary computation.

Anomaly detection in supercomputers is a very difficult problem due to the big scale of the systems and the high number of components. The current state of the art for automated anomaly detection employs Machine Learning methods or statistical regression models in a supervised fashion, meaning that the detection tool is trained to distinguish among a fixed set of behaviour classes (healthy and unhealthy states). We propose a novel approach for anomaly detection in High Performance Computing systems based on a Machine (Deep) Learning technique, namely a type of neural network called autoencoder. The key idea is to train a set of autoencoders to learn the normal (healthy) behaviour of the supercomputer nodes and, after training, use them to identify abnormal conditions. This is different from previous approaches which where based on learning the abnormal condition, for which there are much smaller datasets (since it is very hard to identify them to begin with). We test our approach on a real supercomputer equipped with a fine-grained, scalable monitoring infrastructure that can provide large amount of data to characterize the system behaviour. The results are extremely promising: after the training phase to learn the normal system behaviour, our method is capable of detecting anomalies that have never been seen before with a very good accuracy (values ranging between 88% and 96%)., 9 pages, 3 figures

Scheduling and dispatching tools for High-Performance Computing (HPC) machines have the role of mapping incoming jobs to the available resources, trying to maximize equipment utilization and user satisfaction. Optimal Job Scheduling is a well-known NP-hard problem, forcing commercial schedulers to adopt greedy approaches based on rules. Constraint Programming (CP) is a well-known combinatorial optimization approach that has been shown to be very effective in optimally solving scheduling problems. We present the first CP-based job scheduler for HPC machines, working in a real-life production environment. We evaluate our solution both on a cluster of virtual machines and on the Eurora Supercomputer with production workloads. Results show significant improvements in terms of user fair-waiting without degradation in overall machine utilization w.r.t state-of-the-art rule-based dispatchers.