Search

none 4 no Deep Neural Networks (DNNs) have been shaking the AI scene, for their ability to excel at Machine Learning tasks without relying on complex, hand-crafted, features. Here, we probe whether a DNN can learn how to construct solutions of a CSP, without any explicit symbolic information about the problem constraints. We train a DNN to extend a feasible solution by making a single, globally consistent, variable assignment. The training is done over intermediate steps of the construction of feasible solutions. From a scientific standpoint, we are interested in whether a DNN can learn the structure of a combinatorial problem, even when trained on (arbitrarily chosen) construction sequences of feasible solutions. In practice, the network could also be used to guide a search process, e.g. to take into account (soft) constraints that are implicit in past solutions or hard to capture in a traditional declarative model. This research line is still at an early stage, and a number of complex issues remain open. Nevertheless, we already have intriguing results on the classical Partial Latin Square and N-Queen completion problems. mixed Galassi Andrea, Lombardi Michele, Mello Paola, Milano Michela Galassi Andrea, Lombardi Michele, Mello Paola, Milano Michela

This paper is motivated by the concept that the successful, effective, and sustainable implementation of the smart city paradigm requires a close cooperation among researchers with different, complementary interests and, in most cases, a multidisciplinary approach. It first briefly discusses how such a multidisciplinary methodology, transversal to various disciplines such as architecture, computer science, civil engineering, electrical, electronic and telecommunication engineering, social science and behavioral science, etc., can be successfully employed for the development of suitable modeling tools and real solutions of such sociotechnical systems. Then, the paper presents some pilot projects accomplished by the authors within the framework of some major European Union (EU) and national research programs, also involving the Bologna municipality and some of the key players of the smart city industry. Each project, characterized by different and complementary approaches/modeling tools, is illustrated along with the relevant contextualization and the advancements with respect to the state of the art.

Supercomputer installed capacity worldwide increased for many years and further growth is expected in the future. The next goal for high performance computing (HPC) systems is reaching Exascale. The increase in computational power threatens to lead to unacceptable power demands, if future machines will be built using current technology. Therefore reducing supercomputer power consumption has been the subject of intense research. A common approach to curtail the excessive power demands of supercomputers is to hard-bound their consumption, power capping. Power capping can be enforced by reactively throttling system performance when the power bound is hit, or by scheduling workload in a proactive fashion to avoid hitting the bound. In this paper we explore the second approach: our scheduler meets power capping constraints and minimizes quality-of-service (QoS) disruption through smart planning of the job execution order. The approach is based on constraint programming in conjunction with a machine learning module predicting the power consumptions of HPC applications. We evaluate our method on the Eurora supercomputer, using both synthetic workloads and historical traces. Our approach outperforms the state-of-the-art power capping techniques in terms of waiting time and QoS, while keeping schedule computation time under control.

Demand response mechanisms and load control in the electricity market represent an important area of research at the international level: the trend towards competition and market liberalization has led to the development of methodologies and tools to support energy providers. Demand side management helps energy suppliers to reduce the peak demand and remodel load profiles. This work is intended to support energy suppliers and policy makers in developing strategies to act on the behavior of energy consumers, with the aim to make a more efficient use of energy. We develop a non-linear optimization model for the dynamics of the electricity market, which can be used to obtain tariff recommendations or for setting the goals of a sensibilization campaign. The model comes in two variants: a stochastic version, designed for residential electricity consumption, and a deterministic version, suitable for large electricity users (e.g., public buildings, industrial users). We have tested our model on data from the Italian energy market and performed an extensive analysis of different scenarios. We also tested the optimization model in a real setting in the context of the FP7 DAREED project (http://www.dareed.eu/), where the model has been employed to provide tariff recommendations or to help the identification of goals for local policies.

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.

Recently, a number of noteworthy results have been achieved in various fields of artificial intelligence, and many aspects of the problem solving process have received significant attention by the scientific community. In this context, the extraction of comprehensive knowledge suitable for problem solving and reasoning, from textual and pictorial problem descriptions, has been less investigated, but recognized as essential for autonomous thinking in Artificial Intelligence. In this work we present a challenge where methods and tools for deep understanding are strongly needed for enabling problem solving: we propose to solve mathematical puzzles by means of computers, starting from text and diagrams describing them, without any human intervention. We are aware that the proposed challenge is hard and of difficult solution nowadays (and in the foreseeable future), but even studying and solving only single parts of the proposed challenge would represent an important step forward for artificial intelligence.

Virtual Power Plants (VPP) are one of the main components of future smart electrical grids, connecting and integrating several types of energy sources, loads and storage devices. A typical VPP is a large industrial plant with high (partially shiftable) electric and thermal loads, renewable energy generators and electric and thermal storages. Optimizing the use and the cost of energy could lead to a significant economic impact. This work proposes a VPP Energy Management System (EMS), based on a two-step optimization model that decides the minimum-cost energy balance at each point in time considering the following data: electrical load, photovoltaic production, electricity costs, upper and lower limits for generating units and storage units. The first (day-ahead) step models the prediction uncertainty using a robust approach defining scenarios to optimize the load demand shift and to estimate the cost. The second step is an online optimization algorithm, implemented within a simulator, that uses the optimal shifts produced by the previous step to minimize, for each timestamp, the real cost while fully covering the optimally shifted energy demand. The system is implemented and tested using real data and we provide analysis of results and comparison between real and estimated optimal costs.

I started my term as Editor in Chief of the Constraint Journal on the 1st of January 2015. The purpose of this short report is to provide some news about the journal to the Editorial and Advisory board members and to the constraint programming community.

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.

Scheduling and dispatching tools for high-performance computing (HPC) machines have the key role of mapping jobs to the available resources, trying to maximize performance and quality-of-service (QoS). Allocation and Scheduling in the general case are well-known NP-hard problems, forcing commercial schedulers to adopt greedy approaches to improve performance and QoS. Search-based approaches featuring the exploration of the solution space have seldom been employed in this setting, but mostly applied in off-line scenarios. In this paper, we present the first search-based approach to job allocation and scheduling for HPC machines, working in a production environment. The scheduler is based on Constraint Programming, an effective programming technique for optimization problems. The resulting scheduler is flexible, as it can be easily customized for dealing with heterogeneous resources, user-defined constraints and different metrics. We evaluate our solution both on virtual machines using synthetic workloads, and on the Eurora HPC with production workloads. Tests on a wide range of operating conditions show significant improvements in waitings and QoS in mid-tier HPC machines w.r.t state-of-the-art commercial rule-based dispatchers. Furthermore, we analyze the conditions under which our approach outperforms commercial approaches, to create a portfolio of scheduling algorithms that ensures robustness, flexibility and scalability.

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.

Scheduling and dispatching are critical enabling technologies in supercomputing and grid computing. In these contexts, scalability is an issue: we have to allocate and schedule upi?źto tens of thousands of tasks on tens of thousands of resources. This problem scale is out of reach for complete and centralized scheduling approaches. We propose a distributed allocation and scheduling paradigm called DARDIS that is lightweight, scalable and fully customizable in many domains. In DARDIS each task offloads to the available resources the computation of a probability index associated with each possible start time for the given task on the specific resource. The task then selects the proper resource and start time on the basis of the above probability. The scheduler can be customized with different policies to fit several objective functions like load balancing or makespan. We evaluate our approach in the domain of grids and supercomputers. We compare DARDIS with the most widely used algorithms used in these specific domains to show that this approach can reach better solutions in several cases.

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.

Business intelligence and big data represent two different technologies within decision support systems. The present paper concerns the two concepts within the context of e-government. Thus, the purpose of the paper is to present the preliminary findings regarding publication patterns and topic coverage within the two technologies by conducting a comparative literature review. A total of 281 papers published in the years 2005–2014 were included in the analysis. A rapid increase of papers regarding big data were identified, the majority being journal papers. As regards business intelligence, researchers publish in conference proceedings to a greater extent. Further, big data journal papers are published within a broader range of journal topics compared to business intelligence journal papers. The paper concludes by pointing to further analyses that will be carried out within the 281 selected papers.

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.

Sustainable energy policies are becoming of paramount importance for our future, shaping the environment around us, underpinning economic growth, and increasingly affecting the geopolitical considerations of governments world-wide. Renewable energy diffusion and energy efficiency measures are key for obtaining a transition toward low carbon energy systems. A number of policy instruments have been devised to foster such a transition: feed-in-tariffs, tax exemptions, fiscal incentives, grants. The impact of such schemes on the actual adoption of renewable energy sources is affected by a number of economic and social factors. In this paper, we propose a novel approach to model the diffusion of residential PV systems and assess the impact of incentives. We model the diffusion’s environment using an agent-based model and we study the emergent, global behaviour emerging from the interactions among the agents. While economic factors are easily modelled, social ones are much more difficult to extract and assess. For this reason, in the model we have inserted a large number of social parameters that have been automatically tuned on the basis of past data. The Emilia-Romagna region of Italy has been used as a case study for our approach.

Today’s politicians are confronted with new information technologies to tackle complex decision-making problems. In order to make sustainable decisions, a profound analysis of societal problems and possible solutions (policy options) needs to be performed. In this policy-analysis process, different stakeholders are involved. Besides internal direct advisors of the policy makers (policy analysts), external experts from different scientific disciplines can support evidence-based decision making. Despite the alleged importance of scientific advice in the policy-making process, it is observed that scientific results are often not used. In this work, a concept is described that supports the collaboration between scientists and politicians. We propose a science–policy interface that is realized by including information visualization in the policy-analysis process. Therefore, we identify synergy effects between both fields and introduce a methodology for addressing the current challenges of science–policy interfaces with visualization. Finally, we describe three exemplary case studies carried out in European research projects that instantiate the concept of this approach.

Our society is organized around a number of (interdependent) global systems. Logistic and supply chains, health services, energy networks, financial markets, computer networks, and cities are just a few examples of such global, complex systems. These global systems are socio-technical and involve interactions between complex infrastructures, man-made processes, natural phenomena, multiple stakeholders, and human behavior. For the first time in the history of manking, we have access to data sets of unprecedented scale and accuracy about these infrastructures, processes, natural phenomena, and human behaviors. In addition, progress in high-performancing computing, data mining, machine learning, and decision support opens the possibility of looking at these problems more holistically, capturing many of these aspects simultaneously. This paper addresses emergent architectures enabling controlling, predicting and reaoning on these systems.

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.

In the era of Cloud Computing, Big Data, and Quantum Physics Simulations, data centers play in the world ICT infrastructure a role as big as (sadly) their power consumption. In many cases, a surprising amount of such consumption is due to idle resources, either introduced to face workload peaks or leftovers of workload fragmentation. In this context, proactive workload dispatching has the chance to improve the utilization of computing resources, thus reducing the idle time and improving the ability to handle peaks. In this paper, we devise a CP based approach for proactive workload dispatching on the EURORA supercomputer placed at the CINECA computing center in Bologna. The new system is evaluated on simulated job traces, where it leads to remarkable improvements in terms of both machine utilization and waiting times for queued jobs with respect to the currently used dispatcher, i.e., Portable Batch System (PBS).

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.

In this paper, we propose a challenging research direction for Constraint Programming and optimization techniques in general. We address problems where decisions to be taken affect and are affected by complex systems, which exhibit phenomena emerging from a collection of interacting objects, capable to self organize and to adapt their behaviour according to their history and feedback. Such systems are unfortunately impervious to modeling efforts via state-of-the-art combinatorial optimization techniques. We provide some hints on approaches to connect and integrate decision making and optimization technology with complex systems via machine learning, game theory and mechanism design. In the first case, the aim is to extract modeling components to express the relation between global decisions and observables emerging from the real system, or from an accurate predictive model (e.g. a simulator). In the second case, the idea is to exploit game theory, mechanism design and distributed decision making to drive the process toward realistic equilibrium points avoiding globally optimal, but unrealistic, configurations. We conclude by observing how dealing with the complexity of the considered problems will require to greatly extend the capabilities of state of the art solvers: in this context, we identify some key issues and highlight future research directions.

An interesting exercise for a research community is to foresee its future, identify key research challenges and open problems and be forward-looking in both technology and application fields. The Constraint Programming community, in more than 20 years, has performed this exercise several times. One example is the recent book on Trends in Constraint Programming edited in 2007 by Benhamou, Jussien and O’Sullivan [1] and the recent challenge paper at AAAI 2012 by O’Sullivan [17] entitled Opportunities and challenges for Constraint Programming. Other examples are the earlier papers by Van Hentenryck and Saraswat [8] on Strategic Directions in Constraint Programming in 1996 and the ACM 50th Anniversary Issue of ACM Computing Surveys of the same year on Strategic Directions in Computing Research containing a number of forward looking papers [2–7, 9–16, 18–21]. Some of these papers have correctly foreseen the future, some challenges have received less then expected attention, but overall these papers have always provided a useful guide for researchers and newcomers. Here we are offering another snapshot of the constraint programming community and what its members consider as promising directions. We have intentionally invited contribution without structuring them into a schema. Rather we have preferred a bottom-up call for proposals providing supported-by-evidence viewpoints on future directions of CP.

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.

International audience; The constraint NValue counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing even the lower bound on the number of values is NP-hard. We therefore study different approximation heuristics for this problem. We introduce three new methods for computing a lower bound on the number of values. The first two are based on the maximum independent set problem and are incomparable to a previous approach based on intervals. The last method is a linear relaxation of the problem. This gives a tighter lower bound than all other methods, but at a greater asymptotic cost.

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.