Search

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. [ABSTRACT FROM AUTHOR]

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). [ABSTRACT FROM AUTHOR]

Abstract: We propose a min-flow algorithm for detecting Minimal Critical Sets (MCS) in Resource Constrained Project Scheduling Problems (RCPSP). The MCS detection is a fundamental step in the Precedence Constraint Posting method (PCP), one of the most successful approaches for the RCPSP. The proposed approach is considerably simpler compared to existing flow based MCS detection procedures and has better scalability compared to enumeration- and envelope-based ones, while still providing good quality Critical Sets. The method is suitable for problem variants with generalized precedence relations or uncertain/variable durations. [Copyright &y& Elsevier]

Abstract: The integration of tree search and metaheuristic techniques for the solution of combinatorial optimization problems is a research area widely explored in the last decade. We propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing constraint programming tree search (along with constraint propagation). SNS encloses concepts from metaheuristic techniques. SNS can be used both as a stand alone search strategy, and embedded in other strategies as intensification and diversification mechanism. We provide an extensive experimental evaluation of SNS on hard instances of the Asymmetric Traveling Salesman Problem with Time Windows. We show the effectiveness of SNS as a stand alone strategy when compared to Limited Discrepancy Search and of SNS when included in a heuristic framework such as the constraint programming based local branching. [Copyright &y& Elsevier]

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. Diving consists in repeatedly performing depth first search attempts with random variable and value selection, constraint propagation enabled and backtracking disabled; each attempt is called a dive and, unless a feasible solution is found, it is a partial assignment of variables (whereas a sample is a -possibly infeasible- complete assignment). While the probability of finding a feasible solution via sampling or diving is negligible if the problem is difficult enough, samples and dives are very fast to generate and, intuitively, even when they are infeasible, they can provide some statistical information on search space structure. The aim of this paper is to understand to what extent it is possible to support the CSP solving process with information derived from sampling and diving. In particular, we are interested in extracting from samples and dives precise indications on the quality of individual variable-value assignments with respect to feasibility. We formally prove that even uniform sampling could provide precise evaluation of the quality of single variable-value assignments; as expected, this requires huge sample sizes and is therefore not useful in practice. On the contrary, diving is much better suited for assignment evaluation purposes. We undertake a thorough experimental analysis on a collection of Partial Latin Square and Car Sequencing instances to assess the quality of information provided by dives. Dive features are identified and their impact on search is evaluated. Results show that diving provides information that can be fruitfully exploited. [ABSTRACT FROM AUTHOR]

Abstract: We propose an original, complete and efficient approach to the allocation and scheduling of Conditional Task Graphs (CTGs). In CTGs, nodes represent activities, some of them are branches and are labeled with a condition, arcs rooted in branch nodes are labeled with condition outcomes and a corresponding probability. A task is executed at run time if the condition outcomes that label the arcs in the path to the task hold at schedule execution time; this can be captured off-line by adopting a stochastic model. Tasks need for their execution either unary or cumulative resources and some tasks can be executed on alternative resources. The solution to the problem is a single assignment of a resource and of a start time to each task so that the allocation and schedule is feasible in each scenario and the expected value of a given objective function is optimized. For this problem we need to extend traditional constraint-based scheduling techniques in two directions: (i) compute the probability of sets of scenarios in polynomial time, in order to get the expected value of the objective function; (ii) define conditional constraints that ensure feasibility in all scenarios. We show the application of this framework on problems with objective functions depending either on the allocation of resources to tasks or on the scheduling part. Also, we present the conditional extension to the timetable global constraint. Experimental results show the effectiveness of the approach on a set of benchmarks taken from the field of embedded system design. Comparing our solver with a scenario based solver proposed in the literature, we show the advantages of our approach both in terms of execution time and solution quality. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 can predict the 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. [ABSTRACT FROM AUTHOR]

An introduction to the journal is presented in which the guest editors discuss on the topics including computational sustainability, monitoring of environmental phenomena and a decision support system (DSS) for the waste water management.

Energy efficiency is of paramount importance for the sustainability of high performance computing (HPC) systems. Energy consumption limits the peak performance of supercomputers and accounts for a large share of Total Cost of Ownership (TCO). Consequently, system owners and final users have started exploring mechanisms to trade off performance for power consumption, for example, through frequency and voltage scaling. However, only a limited number of studies have been devoted to explore the economic viability of performance scaling solutions and to devise pricing mechanisms fostering a more energy-conscious usage of resources, without adversely impacting return-of-investment on the HPC facility. How to foster green-computing to take advantage of power management knobs? Would today's accounting systems be sufficient or are novel pricing schemes needed? How to model the link between TCO and power management? To answer these questions, we present a parametrized model to analyze the impact of frequency scaling on energy consumption and to assess the potential cost benefits for the HPC facility and users. We evaluate four pricing schemes, considering both facility manager and the user perspectives. We then perform a design space exploration considering current and near-future HPC systems and technologies. [ABSTRACT FROM AUTHOR]

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 ourmodel 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. [ABSTRACT FROM AUTHOR]

Abstract: Data-Flow models are attracting renewed attention because they lend themselves to efficient mapping on multi-core architectures. The key problem of finding a maximum-throughput allocation and scheduling of Synchronous Data-Flow graphs (SDFGs) onto a multi-core architecture is NP-hard and has been traditionally solved by means of heuristic (incomplete) algorithms with no guarantee of global optimality. In this paper we propose an exact (complete) algorithm for the computation of a maximum-throughput mapping of applications specified as SDFG onto multi-core architectures. This is, to the best of our knowledge, the first complete algorithm for generic SDF graphs, including those with loops and a finite iteration bound. Our approach is based on Constraint Programming, it guarantees optimality and can handle realistic instances in terms of size and complexity. Extensive experiments on a large number of SDFGs demonstrate that our approach is effective and robust. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In recent years, the uptake of Artificial Intelligence (AI) in industry is increasing. For many AI techniques, like Deep Learning, optimization, planning, etc., computational and storage requirements are significant. The problem of determining what is the right hardware (HW on premise or on the cloud) architecture and its dimensioning for AI algorithms is still crucial. Searching for the optimal solution is often challenging, as it is not trivial to anticipate the behavior of an algorithm on diverse architectures. This is especially true if the AI application must respect quality-of-service constraints or budgets. In this scenario, having an automated decision support tool to match algorithms, user constraints and HW resources would be a great advantage for companies and practitioners working with AI applications. In this paper, we tackle this challenge with an approach that relies on the Empirical Model Learning paradigm, based on the integration of Machine Learning (ML) models into an optimization problem. The key idea is to integrate domain knowledge held by experts with data-driven models that learn the relationships between HW requirements and AI algorithm performances. In particular, the approach starts with benchmarking multiple AI algorithms on different HW resources, generating data used to train ML models; then, optimization is used to find the best HW configuration that respects user-defined constraints (e.g., budget, time, solution quality). In the experimental evaluation we validate our approach on a complex problem, namely online algorithms for energy systems, an area characterized by uncertainty and tight HW and real-time constraints. Results show the effectiveness of our approach and its flexibility: We can train the ML models only once and reuse them in the optimization model to tackle a variety of problems, determined by different data instances and user-defined constraints. [ABSTRACT FROM AUTHOR]

Abstract: Cyclic scheduling problems consist in ordering a set of activities executed indefinitely over time in a periodic fashion, subject to precedence and resource constraints. This class of problems has many applications in manufacturing, embedded systems and compiler design, production and chemical systems. This paper proposes a Constraint Programming approach for cyclic scheduling problems, based on modular arithmetic: in particular, we introduce a modular precedence constraint and a global cumulative constraint along with their filtering algorithms. We discuss two possible formulations. The first one (referred to as CROSS) models a pure cyclic scheduling problem and makes use of both our novel constraints. The second formulation (referred to as ) introduces a restrictive assumption to enable the use of classical resources constraints, but may incur a loss of solution quality. Many traditional approaches to cyclic scheduling operate by fixing the period value and then solving a linear problem in a generate-and-test fashion. Conversely, our technique is based on a non-linear model and tackles the problem as a whole: the period value is inferred from the scheduling decisions. Our approach has been tested on a number of non-trivial synthetic instances and on a set of realistic industrial instances. The method proved to effective in finding high quality solutions in a very short amount of time. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

The problem of allocating and scheduling precedence-constrained tasks on the processors of a distributed real-time system is NP-hard. As such, it has been traditionally tackled by means of heuristics, which provide only approximate or near-optimal solutions. This paper proposes a complete allocation and scheduling framework, and deploys an MPSoC virtual platform to validate the accuracy of modelling assumptions. The optimizer implements an efficient and exact approach to the mapping problem based on a decomposition strategy. The allocation subproblem is solved through Integer Programming (IP) while the scheduling one through Constraint Programming (CP). The two solvers interact by means of an iterative procedure which has been proven to converge to the optimal solution. Experimental results show significant speed-ups w.r.t. pure IP and CP exact solution strategies as well as high accuracy with respect to cycle-accurate functional simulation. Two case studies further demonstrate the practical viability of our framework for real-life applications. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]