• First real-world FTL for anomaly detection on Tier-0 supercomputer. • Validated on 100 Marconi100 nodes under three learning paradigms. • FTL boosts F1 by up to 0.50 on nodes not in federated training. • Top-N vs Random-N shows diversity can outperform performance-based selection. • Enables privacy-preserving, scalable HPC fault detection without raw data sharing. High-Performance Computing (HPC) systems increasingly require intelligent, scalable anomaly detection to ensure operational reliability. However, conventional centralized approaches often struggle with data privacy constraints, poor generalization across heterogeneous nodes, and limited scalability. This study presents the first real-world application of federated transfer learning (FTL) for anomaly detection in a production-grade Tier-0 supercomputer. By combining federated learning with transfer learning, the proposed framework enables decentralized model training and personalized adaptation to unseen nodes, without accessing raw data. We validate the approach using two large-scale telemetry datasets collected from 100 nodes of the Marconi100 supercomputer, evaluating its effectiveness across supervised, semi-supervised, and unsupervised learning paradigms. Results show that FTL consistently improves anomaly detection performance on nodes that did not participate in federated training, with F1-score gains reaching up to 0.50. These improvements demonstrate the framework’s ability to generalize across non-identically distributed data and maintain detection accuracy under real-world conditions. This work establishes FTL as a scalable, privacy-preserving solution for fault detection in HPC environments. Its practical deployment on production hardware confirms its readiness for real-time monitoring applications in large-scale, heterogeneous computing systems.

High-Performance Computing (HPC) systems are becoming increasingly vulnerable to anomalies as their scale and complexity grow. In this work, we propose a federated learning (FL) framework that integrates Long Short-Term Memory (LSTM) autoencoders for time series anomaly detection, allowing decentralized model training without sharing raw data. Using real telemetry from the Marconi100 Tier-0 supercomputer, our approach improves the average F1-score from 0.388 to 0.867 (+123 %) and the AUC from 0.334 to 0.808 (+142 %). It also cuts the training data requirement by a factor of 15, reducing the collection period from 4.5 months to just 1.25 weeks. These improvements are consistent across unsupervised, semi-supervised, and supervised settings, and significance testing with the Wilcoxon signed-rank test confirms they are statistically robust ( p < 0.01). To our knowledge, this is the first comprehensive evaluation of FL-based LSTM autoencoders for anomaly detection in real HPC environments.

With the growing focus on Green AI, there is an urgent need for algorithms that are designed to minimize their environmental impact while maintaining satisfying performance.In this paper, we introduce a novel early stopping strategy that considers carbon footprint data while training a recommendation algorithm.In particular, during the training phase, our criterion epoch-by-epoch analyzes the improvement in terms of predictive accuracy and compares it to the increase in carbon emissions.Then, we analyze the trade-off between the scores, and when the accuracy improves at a rate that is not favorable, the training is stopped.In the experimental evaluation, we showed that our strategy could significantly reduce the carbon footprint of several state-ofthe-art recommendation models, with a limited decrease in accuracy and fairness.While more work is needed to automatically balance the trade-off between accuracy and emissions, this paper sheds light on the need for more sustainable recommendation models and takes a significant step toward designing green training strategies.

This work investigates the path toward green recommender systems by examining the impact of data reduction on both model performance and carbon footprint. In the pursuit of developing energy-efficient recommender systems, we investigated whether and how reducing the training data impacts the performances of several representative recommendation models. In order to obtain a fair comparison, all the models were run based on the implementations available in a popular recommendation library, i.e., RecBole, and used the same experimental settings. Results indicate that: (a) data reduction can be a promising strategy to make recommender systems more sustainable, at the cost of a lower accuracy; (b) training recommender systems with less data makes the suggestions more diverse and less biased. Overall, this study contributes to the ongoing discourse on the development of recommendation models that meet the principles of SDGs, laying the groundwork for the adoption of more sustainable practices in the field.

The integration of Machine Learning (ML) and Constrained Optimization (CO) techniques has recently gained significant interest. While pure CO methods struggle with scalability and robustness, and ML methods like constrained Reinforcement Learning (RL) face difficulties with combinatorial decision spaces and hard constraints, a hybrid approach shows promise. However, multi-stage decision-making under uncertainty remains challenging for current methods, which often rely on restrictive assumptions or specialized algorithms. This paper introduces unify , a versatile framework for tackling a wide range of problems, including multi-stage decision-making under uncertainty, using standard ML and CO components. unify integrates a CO problem with an unconstrained ML model through parameters controlled by the ML model, guiding the decision process. This ensures feasible decisions, minimal costs over time, and robustness to uncertainty. In the empirical evaluation, unify demonstrates its capability to address problems typically handled by Decision Focused Learning, Constrained RL, and Stochastic Optimization. While not always outperforming specialized methods, unify ’s flexibility offers broader applicability and maintainability . The paper includes the method’s formalization and empirical evaluation through case studies in energy management and production scheduling, concluding with future research directions.

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.

Artificial Intelligence (AI) has gradually attracted attention in the field of artistic creation, resulting in a debate on the evaluation of AI artistic outputs. However, there is a lack of common criteria for objective artistic evaluation both of human and AI creations. This is a frequent issue in the field of dance, where different performance metrics focus either on evaluating human or computational skills separately. This work proposes a methodological approach for the artistic evaluation of both AI and human artistic creations in the field of robotic dance. First, we define a series of common initial constraints to create robotic dance choreographies in a balanced initial setting, in collaboration with a group of human dancers and choreographer. Then, we compare both creation processes through a human audience evaluation. Finally, we investigate which choreography aspects (e.g., the music genre) have the largest impact on the evaluation, and we provide useful guidelines and future research directions for the analysis of interconnections between AI and human dance creation.

In this paper, we present a comparative analysis of the trade-off between the performance of state-of-the-art recommendation algorithms and their environmental impact. In particular, we compared 18 popular recommendation algorithms in terms of both performance metrics (i.e., accuracy and diversity of the recommendations) as well as in terms of energy consumption and carbon footprint on three different datasets. In order to obtain a fair comparison, all the algorithms were run based on the implementations available in a popular recommendation library, i.e., RecBole, and used the same experimental settings. The outcomes of the experiments showed that the choice of the optimal recommendation algorithm requires a thorough analysis, since more sophisticated algorithms often led to tiny improvements at the cost of an exponential increase of carbon emissions. Through this paper, we aim to shed light on the problem of carbon footprint and energy consumption of recommender systems, and we make the first step towards the development of sustainability-aware recommendation algorithms.

In their quest toward Exascale, High Performance Computing (HPC) systems are rapidly becoming larger and more complex, together with the issues concerning their maintenance. Luckily, many current HPC systems are endowed with data monitoring infrastructures that characterize the system state, and whose data can be used to train Deep Learning (DL) anomaly detection models, a very popular research area. However, the lack of labels describing the state of the system is a wide-spread issue, as annotating data is a costly task, generally falling on human system administrators and thus does not scale toward exascale. In this article we investigate the possibility to extract labels from a service monitoring tool (Nagios) currently used by HPC system administrators to flag the nodes which undergo maintenance operations. This allows to automatically annotate data collected by a fine-grained monitoring infrastructure; this labelled data is then used to train and validate a DL model for anomaly detection. We conduct the experimental evaluation on a tier-0 production supercomputer hosted at CINECA, Bologna, Italy. The results reveal that the DL model can accurately detect the real failures, and, moreover, it canpredictthe insurgency of anomalies, by systematically anticipating the actual labels (i.e., the moment when system administrators realize when an anomalous event happened); the average advance time computed on historical traces is around 45 minutes. The proposed technology can be easily scaled toward exascale systems to easy their maintenance.

Adding constraint support in Machine Learning has the potential to address outstanding issues in data-driven AI systems, such as safety and fairness. Existing approaches typically apply constrained optimization techniques to ML training, enforce constraint satisfaction by adjusting the model design, or use constraints to correct the output. Here, we investigate a different, complementary, strategy based on "teaching" constraint satisfaction to a supervised ML method via the direct use of a state-of-the-art constraint solver: this enables taking advantage of decades of research on constrained optimization with limited effort. In practice, we use a decomposition scheme alternating master steps (in charge of enforcing the constraints) and learner steps (where any supervised ML model and training algorithm can be employed). The process leads to approximate constraint satisfaction in general, and convergence properties are difficult to establish; despite this fact, we found empirically that even a naive setup of our approach performs well on ML tasks with fairness constraints, and on classical datasets with synthetic constraints.

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.

The growing demands of the worldwide IT infrastructure stress the need for reduced power consumption, which is addressed in so-called transprecision computing by improving energy efficiency at the expense of precision. For example, reducing the number of bits for some floating-point operations leads to higher efficiency, but also to a non-linear decrease of the computation accuracy. Depending on the application, small errors can be tolerated, thus allowing to fine-tune the precision of the computation. Finding the optimal precision for all variables in respect of an error bound is a complex task, which is tackled in the literature via heuristics. In this paper, we report on a first attempt to address the problem by combining a Mathematical Programming (MP) model and a Machine Learning (ML) model, following the Empirical Model Learning methodology. The ML model learns the relation between variables precision and the output error; this information is then embedded in the MP focused on minimizing the number of bits. An additional refinement phase is then added to improve the quality of the solution. The experimental results demonstrate an average speedup of 6.5% and a 3% increase in solution quality compared to the state-of-the-art. In addition, experiments on a hardware platform capable of mixed-precision arithmetic (PULPissimo) show the benefits of the proposed approach, with energy savings of around 40% compared to fixed-precision.

In this work we consider optimization problems that require to make interdependent offline and online decisions under uncertainty.We broadly refer to long-term strategic decisions as offline and to short-term operational decisions as online.For example, in Distributed Energy Management Systems we may need to define (offline) a daily production schedule for an industrial plant, and then manage (online) its power supply on a hour by hour basis.Traditionally offline and online phases are tackled in isolation, leading to some drawbacks: offline decisions are taken without regard for the capabilities of the downstream online solver; while the applicability of the best approaches for online decisions (e.g.anticipatory algorithms) is limited by the need to provide high responsiveness.Starting from a (literature-based) baseline, we define general methods for leading to significant quality improvements, at the cost of an increased computation effort either in the offline or the online phase.All our methods have broad applicability, and provide multiple options to balance the solution quality/time trade-off, suiting a variety of practical application scenarios with both offline and online decisions and featuring continuous and discrete decisions.An extensive analysis of the experimental results shows that offline/online integration may lead to substantial benefits.

Optimization problems under uncertainty are traditionally solved either via offline or online methods. Offline approaches can obtain high-quality robust solutions, but have a considerable computational cost. Online algorithms can react to unexpected events once they are observed, but often run under strict time constraints, preventing the computation of optimal solutions. Many real world problems, however, have both offline and online elements: a substantial amount of time and information is frequently available (offline) before an online problem is solved (e.g. energy production forecasts, or historical travel times in routing problems); in other cases both offline (i.e. strategic) and online (i.e. operational) decisions need to be made. Surprisingly, the interplay of these offline and online phases has received little attention: like in the blind men and the elephant tale, we risk missing the whole picture, and the benefits that could come from integrated offline/online optimization. In this survey we highlight the potential shortcomings of pure methods when applied to mixed offline/online problems, we review the strategies that have been designed to take advantage of this integration, and we suggest directions for future research.

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 HighPerformance 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%).

Sampling-based anticipatory algorithms can be very effective at solving online optimization problems under uncertainty, but their computational cost may be prohibitive in some cases. Given an arbitrary anticipatory algorithm, we present three methods that allow to retain its solution quality at a fraction of the online computational cost, via a substantial degree of offline preparation. Our approaches are obtained by combining: 1) a simple technique to identify likely future outcomes based on past observations; 2) the (expensive) offline computation of a "contingency table"; and 3) an efficient solution-fixing heuristic. We ground our techniques on two case studies: an energy management system with uncertain renewable generation and load demand, and a traveling salesman problem with uncertain travel times. In both cases, our techniques achieve high solution quality, while substantially reducing the online computation time.

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 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.

In this work we present two general techniques to deal with multi-stage optimization problems under uncertainty, featuring off-line and on-line decisions. The methods are applicable when: 1) the uncertainty is exogenous; 2) there exists a heuristic for the on-line phase that can be modeled as a parametric convex optimization problem. The first technique replaces the on-line heuristics with an anticipatory solver, obtained through a systematic procedure. The second technique consists in making the off-line solver aware of the on-line heuristic, and capable of controlling its parameters so as to steer its behavior. We instantiate our approaches on two case studies: an energy management system with uncertain renewable generation and load demand, and a vehicle routing problem with uncertain travel times. We show how both techniques achieve high solution quality w.r.t. an oracle operating under perfect information, by obtaining different trade-offs in terms of computation time.

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.

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.

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 up 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.

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.

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

Designing sustainable energy policies heavily impacts the economic development, environmental resource management and social acceptance. There are four main steps in the policy making process: planning, environmental assessment, implementation and monitoring. We focus here on the first three steps that are performed ex-ante. We describe in this paper these steps tailored on the energy policy process. We also propose enabling technologies for implementing a decision support system for energy policy making.

Designing sustainable energy policies has a strong impact on economy, society and environment. Beside a planning activity, policy makers are called to design a number of implementation instruments to enforce their plans. They encompass subsidies, fiscal incentives, feed in tariffs to name a few. Understanding the impact of these instruments on the energy market is essential to select the most efficient one. We propose in this paper a multi-agent simulator that mimics the adoption of photovoltaic as a consequence of a number of implementation instruments. The simulator mainly considers economic evaluations in the agent decision-making procedure, but we are aware also social aspects play an important role and they are subject of current research.

Effective multicore computing requires to make efficient usage of the computational resources on a chip. Offline mapping and scheduling can be applied to improve the performance, but classical approaches require considerable a priori knowledge of the target application. In a practical setting, precise information is often unavailable; one can then resort to approximate time and resource usage figures, but this usually requires to make conservative assumptions. The issue is further stressed if real-time guarantees must be provided. We tackle predictable and efficient nonpreemptive scheduling of multitask applications in the presence of duration uncertainty. Hard real-time guarantees are provided with limited idle time insertion, by exploiting a hybrid offline/online technique known as Precedence Constraint Posting (PCP). Our approach does not require probability distributions to be specified, relying instead on simple and cheaper-to-obtain information (bounds, average values). The method has been tested on synthetic applications/platforms and compared with an offline optimized Fixed Priority Scheduling (FPS) approach and a pure online FIFO scheduler; the results are very promising, as the PCP schedules exhibit good stability and improved average execution time (14 percent on average, up to 30 percent versus FPS and up to 40 percent versus the FIFO scheduler).

Although successfully employed on many industrial problems, Combinatorial Optimization still has limited applicability on several real-world domains, often due to modeling difficulties. This is typically the case for systems under the control of an on-line policy: even when the policy itself is well known, capturing its effect on the system in a declarative model is often impossible by conventional means. Such a difficulty is at the root of the classical, sharp separation between off- line and on-line approaches. In this paper, we investigate a general method to model controlled systems, based on the integration of Machine Learning and Constraint Programming (CP). Specifically, we use an Artificial Neural Network (ANN) to learn the behavior of a controlled system (a multicore CPU with thermal con- trollers) and plug it into a CP model by means of Neuron Constraints. The method obtains significantly better results compared to an approach with no ANN guidance. Neuron Constraints were first introduced in [Bartolini et al., 2011b] as a mean to model complex systems: providing evidence of their applicability to controlled systems is a significant step forward, broadening the application field of combinatorial methods and disclosing opportunities for hybrid off-line/on-line optimization.

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.

We investigate the impact of information extracted from sampling and diving on the solution of Constraint Satisfaction Problems (CSP). A sample is a complete assignment of variables to values taken from their domain according to a given distribution.

Biomass power plants are very promising for reducing carbon oxides emissions, because they provide energy with a carbon-neutral process. Biomass comes from trees and vegetables, so they provide a renewable type of energy. However, biomass plants location, along with their provisioning basins, are heavily regulated by economical aspects, often without careful consideration of their environmental footprint. For example, some Italian biomass plants import from overseas palm-tree oil that is economically convenient. However, the energy consumed for the oil transportation is definitely greater than the energy produced by the palm-tree oil burning. In this way biomass power plants turn out to be environmentally inefficient, even if they produce renewable energy. We propose an Integer Linear Programming approach for defining the energy and cost-efficient biomass plant location along with the corresponding provisioning basin. In addition, the model enables to evaluate existing plants and their energy and cost efficiency. Our study is based on real data gathered in the Emilia-Romagna region of Italy. Finally, this optimization tool is just a small part of a wider perspective that is aimed to define decision support tools for the improvement of regional planning and its precise strategic environmental assessment.

Our work focuses on allocating and scheduling a synchronous data-flow (SDF) graph onto a multi-core platform subject to a minimum throughput requirement. This problem has traditionally be tackled by incomplete approaches based on problem decomposition and local search, which could not guarantee optimality. Exact algorithms used to be considered reasonable only for small problem instances. We propose a complete algorithm based on Constraint Programming which solves the allocation and scheduling problem as a whole. We introduce a number of search acceleration techniques that significantly reduce run-time by aggressively pruning the search space without compromising optimality. The solver has been tested on a number of non-trivial instances and demonstrated promising run-times on SDFGs of practical size and one order of magnitude speed-up w.r.t. the fastest known complete approach.

Abstract Strategic Environmental Assessment is a procedure aimed at introducing systematic assessment of the environmental effects of plans and programs. This procedure is based on the so-called coaxial matrices that define dependencies between plan activities (infrastructures, plants, resource extractions, buildings, etc.) and positive and negative environmental impacts, and dependencies between these impacts and environmental receptors. Up to now, this procedure is manually implemented by environmental experts for checking the environmental effects of a given plan or program, but it is never applied during the plan/program construction. A decision support system, based on a clear logic semantics, would be an invaluable tool not only in assessing a single, already defined plan, but also during the planning process in order to produce an optimized, environmentally assessed plan and to study possible alternative scenarios. We propose two logic-based approaches to the problem, one based on Constraint Logic Programming and one on Probabilistic Logic Programming that could be, in the future, conveniently merged to exploit the advantages of both. We test the proposed approaches on a real energy plan and we discuss their limitations and advantages.

Scheduling task graphs under hard (end-to-end) timing constraints is an extensively studied NP-hard problem of critical importance for predictable software mapping on Multiprocessor System-on-chip (MPSoC) platforms. In this work we focus on an off-line (design-time) version of this problem, where the target task graph is known before execution time. We address the issue of scheduling robustness, i.e. providing hard guarantees that the schedule will meet the end-to-end deadline in presence of bounded variations of task execution times expressed as min-max intervals known at design time. We present a robust scheduling algorithm that proactively inserts sequencing constraints when they are needed to ensure that execution will have no inserted idle times and will meet the deadline for any possible combination of task execution times within the specified intervals. The algorithm is complete, i.e. it will return a feasible graph augmentation if one exists. Moreover, we provide an optimization version of the algorithm that can compute the shortest deadline that can be met in a robust way.

This paper proposes a novel approach to solve the allocation and scheduling problems for variable voltage/frequency multiprocessor systems-on-chip, which minimizes overall system energy dissipation. The optimality of derived system configurations is guaranteed, while the computation efficiency of the optimizer allows for solving problem instances that were traditionally considered beyond reach for exact solvers (optimality gap). Furthermore, this paper illustrates the development- and run-time software infrastructures that assist the user in developing applications and implementing optimizer solutions. The proposed approach guarantees a high level of power, performance, and constraint satisfaction predictability as from validation on the target platform, thus bridging the abstraction gap.

The Cell BE processor provides both scalable computation power and flexibility, and it is already being adopted for many computational intensive applications. Despite of its merits, it also presents many challenges, as it is now widely known that is very difficult to program the Cell BE in an efficient manner. Hence, the creation of an efficient software development framework is becoming the key challenge for this computational platform. We propose a novel software toolkit, called Cellflow, which enables developers to quickly build multi-task applications for Cell-based platform. We support programmers from the initial stage of their work, through a development-time software infrastructure, to the final stage of the application development, proposing a safe and easy-to-use explicit parallel programming model. Experimental results show that in Cellflow we reduced to minimum the abstraction gap between the optimization and development phases.

The increasing levels of system integration in Multi-Processor System-on-Chips (MPSoCs) emphasize the need for new design flows for efficient mapping of multi-task applications onto hardware platforms. Even though data-flow graphs are often used for pure data-streaming, many realistic applications can only be specified as conditional task graphs (CTG). The problem of allocating and scheduling conditional task graphs on processors in a distributed real-time system is NP-hard. The first contribution of this paper is a complete stochastic allocation and scheduling framework, where an MPSoC virtual platform is used to accurately derive input parameters, validate abstract models of system components and assess constraint satisfaction and objective function optimization. The optimizer implements an efficient and exact approach to allocation and scheduling based on problem decomposition. The original contributions of the approach appear both in the allocation and in the scheduling part of the optimizer. For the first, we propose an exact analytic formulation of the stochastic objective function based on the task graph analysis, while for the scheduling part we extend the timetable constraint for conditional activities. The second contribution of this paper is the introduction of a software library and API for the deployment of conditional task graph applications onto Multi-Processor System-on-Chips. With our library support, programmers can quickly develop multi-task applications which will run on a multi-core architecture and can easily apply the optimal solution found by our optimizer. The proposed programming support manages OS-level issues, such as task allocation and scheduling, as well as task-level issues, like inter-task communication and synchronization.

This paper proposes a complete allocation and scheduling framework, where an MPSoC virtual platform is used to accurately derive input parameters, validate abstract models of system components and assess constraint satisfaction and objective function optimization. The optimizer implements an efficient and exact approach to allocation and scheduling based on problem decomposition. The allocation subproblem is solved through integer programming while the scheduling one through constraint programming. The two solvers can interact by means of no-good generation, thus building an iterative procedure which has been proven to converge to the optimal solution. Experimental results show significant speedups w.r.t. pure IP and CP exact solution strategies as well as high accuracy with respect to cycle accurate functional simulation. A case study further demonstrates the practical viability of our framework for real-life systems and applications.

We model portions of the search tree via so-called search constraints. We focus on a particular kind of search constraint, the k-discrepancy constraint appearing in discrepancy-based search. The property that a node has an associated discrepancy k can be modeled (and enforced) through a linear constraint. Our key result is the exploitation of the k-discrepancy constraint to improve the bound given by any relaxation of a combinatorial optimization problem through the additive bounding technique (Fischetti and Toth 1989). We show how this simple idea can be effectively exploited to tighten relaxations in CP solvers and speed up the proof of optimality by performing a large variety of computational experiments on test problems involving the AllDifferent constraint. In this view, the additive bounding technique represents a non-trivial link between search and bound. Moreover, such a technique is general because it does not depend on either the AllDifferent constraint or the discrepancy search technique.

Constraint Logic Programming languages on Finite Domains, CLP( FD ), provide a declarative framework for Artificial Intelligence problems. However, in many real life cases, domains are not known and must be acquired or computed. In systems that interact with the outer world, domain elements synthesize information on the environment, they are not all known at the beginning of the computation, and must be retrieved through an expensive acquisition process.In this article, we extend the CLP( FD ) language by combining it with a new sort (called Incrementally specified Sets, I-Set ). In the resulting language, CLP( FD + I-Set ), FD variables can be defined on partially or fully unknown domains ( I-Set ). Domains can be linked each other through relations, and constraints can be imposed on them. We describe a propagation algorithm (called Known Arc Consistency (KAC)) based on known domain elements, and theoretically compare it with arc-consistency.The language can be implemented on top of different CLP systems, thus letting the user exploit different possible semantics for domains (e.g., lists, sets or streams). We state the specifications that the employed system should provide, and we show that two different CLP systems (Conjunto and { log }) can be effectively used.We provide motivating examples and describe promising applications.

In classical CLP(FD) systems, domains of variables are completely known at the beginning of the constraint propagation process. However, in systems interacting with an external environment, acquiring the whole domains of variables before the beginning of constraint propagation may cause waste of computation time, or even obsolescence of the acquired data at the time of use. For such cases, the Interactive Constraint Satisfaction Problem (ICSP) model has been proposed (Cucchiara et al. 1999a) as an extension of the CSP model, to make it possible to start constraint propagation even when domains are not fully known, performing acquisition of domain elements only when necessary, and without the need for restarting the propagation after every acquisition. In this paper, we show how a solver for the two sorted CLP language, defined in previous work (Gavanelli et al. 2005) to express ICSPs, has been implemented in the Constraint Handling Rules (CHR) language, a declarative language particularly suitable for high level implementation of constraint solvers.

In this work, we introduce a multiagent architecture called the MultiAGent Metaheuristic Architecture (MAGMA) conceived as a conceptual and practical framework for metaheuristic algorithms. Metaheuristics can be seen as the result of the interaction among different kinds of agents: The basic architecture contains three levels, each hosting one or more agents. Level-0 agents build solutions, level-1 agents improve solutions, and level-2 agents provide the high level strategy. In this framework, classical metaheuristic algorithms can be smoothly accommodated and extended. The basic three level architecture can be enhanced with the introduction of a fourth level of agents (level-3 agents) coordinating lower level agents. With this additional level, MAGMA can also describe, in a uniform way, cooperative search and, in general, any combination of metaheuristics. We describe the entire architecture, the structure of agents in each level in terms of tuples, and the structure of their coordination as a labeled transition system. We propose this perspective with the aim to achieve a better and clearer understanding of metaheuristics, obtain hybrid algorithms, suggest guidelines for a software engineering-oriented implementation and for didactic purposes. Some specializations of the general architecture will be provided in order to show that existing metaheuristics [e.g., greedy randomized adaptive procedure (GRASP), ant colony optimization (ACO), iterated local search (ILS), memetic algorithms (MAs)] can be easily described in our framework. We describe cooperative search and large neighborhood search (LNS) in the proposed framework exploiting level-3 agents. We show also that a simple hybrid algorithm, called guided restart ILS, can be easily conceived as a combination of existing components in our framework.

The Traveling Salesman Problem with Time Windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a specific time window. We propose a hybrid approach for solving the TSPTW that merges Constraint Programming propagation algorithms for the feasibility viewpoint (find a path), and Operations Research techniques for coping with the optimization perspective (find the best path). We show with extensive computational results that the synergy between Operations Research optimization techniques embedded in global constraints, and Constraint Programming constraint solving techniques, makes the resulting framework effective in the TSPTW context also if these results are compared with state-of-the-art algorithms from the literature.

Efforts aimed at combining operations research and constraint programming have become increasingly prominent and successful in the last few years. It is now widely recognized that integration, e.g., inference in the form of constraint propagation and relaxation in the form of linear programming, can yield substantial results. In this paper, we argue the benefits of constraint programming's global constraints as a basis for such an integration and discuss the advantages along with some examples. We illustrate the integration on the global cardinality structure, on piecewise linear functions, on variable subscripts, on the cycle structure and on resource constraints. Each example is completed with a case study.

In this paper, we propose a constraint logic programming (CLP) approach to the solution of a job shop scheduling problem in the field of production planning in orthopaedic hospital departments. A pure CLP on finite domain (CLP(FD)) approach to the problem has been developed, leading to disappointing results. In fact, although CLP(FD) has been recognized as a suitable tool for solving combinatorial problems, it presents some drawbacks for optimization problems. The main reason concerns the fact that CLP(FD) solvers do not effectively handle the objective function and cost-based reasoning through the simple branch and bound scheme they embed. Therefore, we have proposed an improvement of the standard CLP branch and bound algorithm by exploiting some well-known operations research results. The branch and bound we integrate in a CLP environment is based on the optimal solution of a relaxation of the original problem. In particular, the relaxation used for the job shop scheduling problem considered is the well-known shifted bottleneck procedure considering single machine problems. The idea is to decompose the original problem into subproblems and solve each of them independently. Clearly, the solutions of each subproblem may violate constraints among different subproblems which are not taken into account. However, these solutions can be exploited in order to improve the pruning of the search space and to guide the search by defining cost-based heuristics. The resulting algorithm achieves a significant improvement with respect to the pure CLP(FD) approach that enables the solution of problems which are one order of magnitude greater than those solved by a pure CLP(FD) algorithm. In addition, the resulting code is less dependent on the input data configuration. Copyright © 2001 John Wiley & Sons, Ltd.

In this paper, we investigate the possibility of integrating Artificial Intelligence (AI) and Operations Research (OR) techniques for solving the Crew Rostering Problem (CRP). CRP calls for the optimal sequencing of a given set of duties into rosters satisfying a set of constraints. The optimality criterion requires the minimization of the number of crews needed to cover the duties. This kind of problem has been traditionally solved by OR techniques. In recent years, a new programming paradigm based on Logic Programming, named Constraint Logic Programming (CLP), has been successfully used for solving hard combinatorial optimization problems. CLP maintains all the advantages of logic programming such as declarativeness, non-determinism and an incremental style of programming, while overcoming its limitations, mainly due to the inefficiency in exploring the search space. CLP achieves good results on hard combinatorial optimization problems which, however, are not comparable with those achieved by OR approaches. Therefore, we integrate both techniques in order to design an effective heuristic algorithm for CRP which fully exploits the advantages of the two methodologies: on the one hand, we maintain the declarativeness of CLP, its ease of representing knowledge and its rapid prototyping; on the other hand, we inherit from OR some efficient procedures based on a mathematical approach to the problem. Finally, we compare the results we achieved by means of the integration with those obtained by a pure OR approach, showing that AI and OR techniques for hard combinatorial optimization problems can be effectively integrated. © 1998 John Wiley & Sons, Ltd.