Search

The purpose of this chapter is to introduce the collection that celebrates the 10years of CPAIOR. First, a short overview of research topics addressed by the ever growing CPAIOR community is presented. Then, a short chapter summary follows that describes the book structure and its content. [ABSTRACT FROM AUTHOR]

Limited Discrepancy Search (LDS) is one of the most widely used search strategies in Constraint Programming; given a solution suggested by a search heuristics, LDS explores the search space at increasing discrepancy with respect to such solution. In optimization problems, LDS is used as a way to explore the k-distance neighborhood of an incumbent solution using constraint propagation and tree search. However, for large problems, the size of the resulting neighborhoods limits the k-distance (i.e. the number of discrepancies) that can be efficiently explored. If the first solution is far from the optimal one, exploring limited neighborhood leads to small improvements. Therefore, we propose a variant of LDS that samples the LDS space by exploring slices of (possibly very large) discrepancy based neighborhoods. Instead of deciding only the number of variables that can change (the k-distance) we decide which n − k variables should be fixed to the value they have in the incumbent solution. We present results on hard Asymmetric Traveling Salesman Problem with Time Windows (ATSPTW) instances to show the effectiveness of the approach. [ABSTRACT FROM AUTHOR]

In this paper we propose off-line and on-line extensions to the Resource Constrained Project Scheduling Problem. The off-line extension is a variant of RCPSP with time lags and uncertain, bounded activity durations. In this context we improve over our previous work presented in [12] by proposing an incremental flow computation for finding minimal conflict sets and a set of filtering rules for cumulative constraint propagation. The on-line extension is based instead on considering an on-line semantics such as the Self-Timed Execution and take it into account in the scheduling process. Adding the on-line aspect to the problem makes the CSP framework no longer suitable. We have extended the CSP framework to take into account general search decisions and auxiliary unbound variables. An extensive set of experimental results show an improvement of up to two orders of magnitude over our previous approach. [ABSTRACT FROM AUTHOR]

Stream (data-flow) computing is considered an effective para-digm for parallel programming of high-end multi-core architectures for embedded applications (networking, multimedia, wireless communication). Our work addresses a key step in stream programming for embedded multicores, namely, the efficient mapping of a synchronous data-flow graph (SDFG) onto a multi-core platform subject to a minimum throughput requirement. This problem has been extensively studied in the past, and its complexity has lead researches to develop incomplete algorithms which cannot exclude false negatives. We developed a CP-based complete algorithm based on a new throughput-bounding constraint. The algorithm has been tested on a number of non-trivial SDFG mapping problems with promising results. [ABSTRACT FROM AUTHOR]

This chapter aims to provide an overview of the main Italian research areas and activities. We first analyze the collaboration structure of Italian research, which involves more than eight hundred scholars and researchers from both universities and industry. From a network perspective it appears to be scale-free. Next, we briefly illustrate the main subjects of investigation and applications. AI research in Italy goes back to the 1970s 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. [ABSTRACT FROM AUTHOR]

We investigate the impact of sampling and diving in the solution of constraint satisfaction problems. A sample is a complete assignment of variables to values taken from their domain according to a 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 give some statistic information on search space structure. The aim of this paper is to understand to what extent it is possible to help 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 how good/bad are individual variable-value assignments with respect to feasibility. We formally prove that even uniform sampling could provide precise evaluation of the quality of variable-value assignments; as expected, this requires huge sample sizes and is therefore not useful in practice. On the contrary, diving seems to be much better suited for assignment evaluation purposes. Three dive features are identified and evaluated on a collection of Partial Latin Square instances, showing that diving provides information that can be fruitfully exploited. Many promising direction for future research are proposed. [ABSTRACT FROM AUTHOR]

Resource Constrained Project Scheduling Problem is a very important problem in project management, manufacturing and resource optimization. We focus on a variant of RCPSP with time lags and variable activity durations. The solving approach is based on Precedence Constraint Posting that adds new precedence constraints to the original project graph so that all resource conflicts are solved and a consistent assignment of start times can be computed for whatever combination of activity durations. We propose a novel method for computing resource conflicts based on the minimum flow on the resource graph and we use it in an efficient complete search strategy. We experiment the approach on instances coming from the scheduling of parallel applications on multi processor systems on chip. [ABSTRACT FROM AUTHOR]

Software optimization for multicore architectures is one of the most critical challenges in today΄s high-end computing. In this paper we focus on a well-known multicore platform, namely the Cell BE processor, and we address the problem of allocating and scheduling its processors, communication channels and memories, with the goal of minimizing application execution time. We have developed a complete optimization strategy based on Benders΄ decomposition. Unfortunately, a traditional two-stage decomposition produces unbalanced components: the allocation part is difficult, while the scheduling part is much easier. To address this issue, we have developed a multi-stage decomposition, which is a recursive application of standard Logic based Benders΄ Decomposition (LBD). Our experiments demonstrate that this approach is very effective in obtaining balanced sub-problems and in reducing the runtime of the optimizer. [ABSTRACT FROM AUTHOR]

The Cell BE processor provides both scalable computation power and flexibility, and it is already being adopted for many computational intensive applications like aerospace, defense, medical imaging and gaming. 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 have developed 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. A fundamental component of the software toolkit is the off-line allocator and scheduler that manages hardware resources while optimizing performance metrics such as execution time, allocation costs, power. The optimization engine receives as input a task graph representing an application, the hardware resources and produces an optimal allocation and scheduling. We have developed various approaches, either based on decomposition [5] or based on pure Constraint Programming, this latter being the core of this paper. We have identified instance features that guide toward the choice of the best solver for the instance at hand. Experimental result show that Constraint Programming (possibly combined with Integer Programming) is a proper tool for dealing with this kind of applications achieving very good performance. [ABSTRACT FROM AUTHOR]

Cancer screening is a method of preventing cancer by early detecting and treating abnormalities. One of the most critical screening phase is invitation planning since screening resources are limited and there are many people to invite. For this reason, smart resource allocation approaches are needed. In the paper, we propose and compare two solutions for smart invitation plan definition, one based on greedy approaches and one based on Constraint Programming techniques that enable the definition of the optimal invitation plan. [ABSTRACT FROM AUTHOR]

Local branching is a general purpose heuristic search method successfully used in Mixed Integer Programming (MIP). We propose its integration and extension in Constraint Programming (CP). [ABSTRACT FROM AUTHOR]

This paper describes a complete and efficient solution to the scheduling of conditional task graphs whose nodes are activities and whose arcs can be labelled with a probability distribution. Tasks are executed if a set of conditions hold at scheduling execution time. The model is therefore stochastic. The minimization of the expected makespan implies an exponential-sized description of the objective function. We propose an analytic formulation of the stochastic objective function based on the task graph analysis, and a conditional constraint that handles it efficiently. Experimental results show the effectiveness of our approach in comparison with (1) an approach using a deterministic objective function and (2) scenario based constraint programming taking into account all scenarios or only a part of them. [ABSTRACT FROM AUTHOR]

We propose two algorithms achieving generalized arc consistency for the soft global cardinality constraint with variable-based violation and with value-based violation. They are based on graph theory and their complexity is $O(\sqrt{n}m)$ where n is the number of variables and m is the sum of the cardinalities of the domains. They improve previous algorithms that ran respectively in O(n(m+nlog n)) and O((n+k)(m+nlog n)) where k is the cardinality of the union of the domains. [ABSTRACT FROM AUTHOR]

In this paper we introduce a complex allocation and scheduling problem for variable voltage Multi-Processor System-on-Chip (MPSoC) platforms. We propose a methodology to formulate and solve to optimality the allocation, scheduling and discrete voltage selection problem, minimizing the system energy dissipation and the overhead for frequency switching. Our approach is based on the Logic Benders decomposition technique where the allocation is solved through an Integer Programming solver, and the scheduling through a Constraint Programming solver. The two solvers are interleaved and their interaction regulated by cutting plane generation. The objective function depends on both master and sub-problem variables. We demonstrate the efficiency of our approach on a set of realistic instances. [ABSTRACT FROM AUTHOR]

This paper describes a complete and efficient solution to the stochastic allocation and scheduling for Multi-Processor System-on-Chip (MPSoC). Given a conditional task graph characterizing a target application and a target architecture with alternative memory and computation resources, we compute an allocation and schedule minimizing the expected value of communication cost, being the communication resources one of the major bottlenecks in modern MPSoCs. Our approach is based on the Logic Based Benders decomposition where the stochastic allocation is solved through an Integer Programming solver, while the scheduling problem with conditional activities is faced with Constraint Programming. The two solvers interact through no-goods. The original contributions of the approach appear both in the allocation and in the scheduling part. 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. Experimental results show the effectiveness of the approach. [ABSTRACT FROM AUTHOR]

In this paper, we propose an effective search procedure that interleaves two steps: subproblem generation and subproblem solution. We mainly focus on the first part. It consists of a variable domain value ranking based on reduced costs. Exploiting the ranking, we generate, in a Limited Discrepancy Search tree, the most promising subproblems first. An interesting result is that reduced costs provide a very precise ranking that allows to almost always find the optimal solution in the first generated subproblem, even if its dimension is significantly smaller than that of the original problem. Concerning the proof of optimality, we exploit a way to increase the lower bound for subproblems at higher discrepancies. We show experimental results on the TSP and its time constrained variant to show the effectiveness of the proposed approach, but the technique could be generalized for other problems. [ABSTRACT FROM AUTHOR]

Hybrid algorithms combining local and systematic search often use nondeterminism in fundamentally different ways. They may differ in the strategy to explore the search tree and/or in how computation states are represented. This paper presents nondeterministic control structures to express a variety of hybrid search algorithms concisely and elegantly. These nondeterministic abstractions describe the search tree and are compiled in terms of first-class continuations. They are also parameterized by search controllers that are under user control and specify the state representation and the exploration strategy. The resulting search language is thus high-level, flexible, and directly extensible. The abstractions are illustrated on a jobshop scheduling algorithm that combines tabu search and a limited form of backtracking. Preliminary experimental results indicate that the control structures induce small, often negligible, overheads. [ABSTRACT FROM AUTHOR]

Integration of explanations into a CSP solver is a technique addressing difficult question "why my problem has no solution". Moreover, explanations together with advanced search methods like directed backjumping can effectively cut off parts of the search tree and thus speed up the search. In order to use explanations, propagation algorithms must provide some sort of reasons (justifications) for their actions. For binary constraints it is mostly easy. In the case of global constraints computation of factual justifications can be tricky and/or computationally expensive. This paper shows how to effectively compute explanations for the unary resource constraint. The explanations are computed in a lazy way. The technique is experimentally demonstrated on job-shop benchmark problems. The following propagation algorithms are considered: edge-finding, not-first/not-last and detectable precedences. Speed of these filtering algorithms and speed of the explanation computation is the main interest. [ABSTRACT FROM AUTHOR]

Creating good integer programming formulations had, as a basic axiom, the rule "Find formulations with tighter linear relaxations". This rule, while useful when using unsophisticated branch-and-bound codes,is insufficient when using state-of-the-art codes that understand and embed many of the obvious formulation improvements. As these optimization codes become more sophisticated it is important to have finer control over their operation. Modelers need to be even more creative in reformulating their integer programs in order to improve on the automatic reformulations of the optimization codes. [ABSTRACT FROM AUTHOR]

An optimization problem arising in the design of optical fibre networks is discussed. A network contains client nodes, each installed on one or more SONET rings. A constraint programming model of the problem is described and compared with a mixed integer programming formulation. In the CP model the search is decomposed into two stages; first partially solving the problem by deciding how many rings each node should be on, and then making specific assignments of nodes to rings. The model includes implied constraints derived by considering optimal solutions to subproblems. In both the MIP and CP models, it is important to deal with the symmetry of the problem. In the CP model, two sources of symmetry are separated; one is eliminated dynamically during search and the other by assigning ranges rather than explicit values to one set of decision variables. The resulting CP model allows optimal solutions to be found easily for benchmark problems. [ABSTRACT FROM AUTHOR]

We present the tree-of-BDDs approach, a decomposition scheme for compiling configuration problems. Methods for minimum explanations and full interchangeable value sets detection are also given. Experiments show that the techniques presented here can drastically reduce the time and space requirements for interactive configurators. [ABSTRACT FROM AUTHOR]

In this paper, we present a method for solving Mixed Logical/ Integer Linear Programming (MLILP) problems that integrates a polynomial-time ILP solver for the special class of Unit-Two-Variable-Per-Inequality (unit TVPI or UTVPI) constraints of the form ax + by ≤ d, where a, b ∈ {-1, 0, 1}, into generic Boolean SAT solvers. In our approach the linear constraints are viewed as special literals and replaced by binary "indicator" variables to generate a pure logical problem. The resulting problem is subsequently solved using a SAT search procedure which invokes the linear UTVPI solver to incrementally check the consistency of the UTVPI constraints whenever any of the indicator variables are assigned to true. The linear UTVPI solver, on the other hand, can possibly pass implications or no-good constraints to the Boolean SAT solver. Checking the consistency of the UTVPI constraints incrementally enables the UTVPI solver to efficiently interact with the different components of the SAT solver. Additionally, several heuristics and encoding methods are proposed to accommodate the special circumstances of activating UTVPI constraints by the SAT solver. Empirical evidence is presented that demonstrates the advantages of our combined method for large problems. [ABSTRACT FROM AUTHOR]

We identify a property of constraints called smoothness, and present an extremely simple randomized algorithm for solving smooth constraints. The complexity of the algorithm is much less than the lower bound for establishing path-consistency, and because smoothness is shown to be identical to connected row-convexity (CRC) for the case of binary constraints, the time and space complexity of solving CRC constraints is improved. Central to our algorithm is the relationship of smooth constraints to random walks on directed graphs. We also provide simple deterministic algorithms to test for the smoothness of a given CSP under given domain orderings of the variables. Finally, we show that some other known tractable constraint languages, like the set of implicational constraints, and the set of binary integer linear constraints, are special cases of smooth constraints, and can therefore be solved much more efficiently than the traditional time and space complexities attached with them. [ABSTRACT FROM AUTHOR]

A cardinality constraint imposes that each value of a set V must be taken a certain number of times by a set of variables X, whereas an among constraint imposes that a certain number of variables of a set X must take a value in the set V. This paper studies several combinations of among constraints and several conjunctions of among constraints and cardinality constraints. Some filtering algorithms are proposed and they are characterized when it is possible. Moreover, a weak form of Singleton arc consistency is considered. At last, it is shown how the global sequencing constraint and the global minimum distance constraint can be easily modeled by some conjunctions of cardinality and among constraints. Some results are also given for the global minimum distance constraint. They show that our study outperforms the existing constraint in ILOG Solver. [ABSTRACT FROM AUTHOR]

This paper presents a CSPs filtering method combining arc-consistency and dual Lagrangean relaxation techniques. First, we model the constraint satisfaction problem as a 0/1 linear integer program (IP); then, the consistency of a value is defined as an optimization problem on which a dual Lagrangean relaxation is defined. While solving the dual Lagrangean relaxation, values inconsistencies may be detected (dual Lagrangean inconsistent values); the constraint propagation of this inconsistency can be performed by arc-consistency. After having made the CSP arc-consistent, the process iteratively selects values of variables which may be dual Lagrangean inconsistent. Computational experiments performed over randomly generated problems show the advantages of the hybrid filtering technique combining arc-consistency and dual Lagrangean relaxation. Keywords: Arc-Consistency, Lagrangean Relaxation, Subgradient Algorithm. [ABSTRACT FROM AUTHOR]

The effects of combining search and modelling techniques can be complex and unpredictable, so guidelines are very important for the design and development of effective and robust solvers and models. A recently observed phenomenon is the negative effect of symmetry breaking constraints on local search performance. The reasons for this are poorly understood, and we attempt to shed light on the phenomenon by testing three conjectures: that the constraints create deep new local optima; that they can reduce the relative size of the basins of attraction of global optima; and that complex local search heuristics reduce their negative effects. [ABSTRACT FROM AUTHOR]

We present an algorithmic framework for integrating solution methods that is based on search, inference, and relaxation and their interactions. We show that the following are special cases: branch and cut, CP domain splitting with propagation, popular global optimization methods, DPL methods for SAT with conflict clauses, Benders decomposition and other nogood-based methods, partial-order dynamic backtracking, various local search metaheuristics, and GRASPs (greedy randomized adaptive search procedures). The framework allows elements of different solution methods to be combined at will, resulting in a variety of integrated methods. These include continuous relaxations for global constraints, the linking of integer and constraint programming via Benders decomposition, constraint propagation in global optimization, relaxation bounds in local search and GRASPs, and many others. [ABSTRACT FROM AUTHOR]

Producing work schedules for airline crew normally results in individually different schedules. Some airlines do however want to give the same schedule to groups of people. The construction of such groups must respect certain rules, provide a good matching of certain factors and fit well into the normal process of producing anonymous trips starting and ending at the home base and assigning these to the crew. In this paper we present an application, implemented and delivered to a large European airline, which addresses these needs. The problem is challenging to solve for certain cases. Hence two different approaches have been applied, one using constraint programming and the other using column generation. These two methods are described and compared - along with computational results. [ABSTRACT FROM AUTHOR]

Constraint programming (CP) based column generation uses CP to solve the pricing subproblem. We consider a set partitioning formulation with a huge number of variables, each of which can be generated by solving a CP subproblem. We propose two customized search strategies to solve the CP subproblem, which aim to improve the coordination between the master problem and the subproblem. Specifically, these two strategies attempt to generate more promising columns for the master problem in order to counter the effect of slow convergence and the difficulty of reaching integer solutions. The first strategy uses the dual variables to direct the search towards columns that drive the relaxed master problem faster to optimality. The second strategy exploits the structure of the constraints in the master problem to generate columns that help to reach integer solutions more quickly. We use a physician scheduling problem to test the strategies. [ABSTRACT FROM AUTHOR]

We describe the problem of scheduling astronomy observations for the Stratospheric Observatory for Infrared Astronomy, an airborne telescope. The problem requires maximizing the number of requested observations scheduled subject to a mixture of discrete and continuous constraints relating the feasibility of an astronomical observation to the position and time at which the observation begins, telescope elevation limits, Special Use Airspace limitations, and available fuel. Solving the problem requires making discrete choices (e.g. selection and sequencing of observations) and continuous ones (e.g. takeoff time and setup actions for observations by repositioning the aircraft). Previously, we developed an incomplete algorithm called ForwardPlanner using a combination of AI and OR techniques including progression planning, lookahead heuristics, stochastic sampling and numerical optimization, to solve a simplified version of this problem. While initial results were promising, ForwardPlanner fails to scale when accounting for all relevant constraints. We describe a novel combination of Squeaky Wheel Optimization (SWO), an incomplete algorithm designed to solve scheduling problems, with previously devised numerical optimization methods and stochastic sampling approaches, as well as heuristics based on reformulations of the SFPP to traditional OR scheduling problems. We show that this new algorithm finds as good or better flight plans as the previous approaches, often with less computation time. [ABSTRACT FROM AUTHOR]

Recently, new cost-based filtering algorithms for shorter-path constraints have been developed. However, so far only the theoretical properties of shorter-path constraint filtering have been studied. We provide the first extensive experimental evaluation of the new algorithms in the context of the resource constrained shortest path problem. We show how reasoning about path-substructures in combination with CP-based Lagrangian relaxation can help to improve significantly over previously developed problem-tailored filtering algorithms and investigate the impact of required-edge detection, undirected versus directed filtering, and the choice of the algorithm optimizing the Lagrangian dual. [ABSTRACT FROM AUTHOR]

We propose a natural generalization of arc-consistency, which we call multiconsistency: A value v in the domain of a variable x is k-multiconsistent with respect to a constraint C if there are at least k solutions to C in which x is assigned the value v. We present algorithms that determine which variable-value pairs are k-multiconsistent with respect to several well known global constraints. In addition, we show that finding super solutions is strictly harder than finding arbitrary solutions and suggest multiconsistency as an alternative way to search for robust solutions. [ABSTRACT FROM AUTHOR]

The Employee Timetabling Problem (ETP) is a general class of problems widely encountered in service organizations (such as call centers for instance). Given a set of activities, a set of demand curves (specifying the demand in terms of employees for each activity for each time period) the problem consists of constructing a set of work shifts such that each activity is at all time covered by a sufficient number of employees. Work shifts can cover many activities and must meet work regulations such as breaks, meals and maximum working time constraints. Furthermore, it is often desired to optimize a global objective function such as minimizing labor costs or maximizing a quality of service measure. This paper presents variants of this problem which are modeled with the Dantzig formulation. This approach consists of first generating all feasible work shifts and then selecting the optimal set. We propose to address the shift generation problem with constraint satisfaction techniques based on expressive and efficient global constraints such as gcc and regular. The selection problem, which is modeled with an integer linear program, is solved by a standard MIP solver for smaller instances and addressed by column generation for larger ones. Since a column generation procedure needs to generate only shifts of negative reduced cost, the optimization constraint cost-regular is introduced and described. Preliminary experimental results are given on a typical ETP. [ABSTRACT FROM AUTHOR]

The scheduling of social golfers has attracted significant attention in recent years because of its highly symmetrical and combinatorial nature. In particular, it has become one of the standard benchmarks for symmetry breaking in constraint programming. This paper presents a very effective, local search, algorithm for scheduling social golfers. The algorithm find the first known solutions to 11 instances and matches, or improves, state-of-the-art results from constraint programming on all but 3 instances. Moreover, most instances of the social golfers are solved within a couple of seconds. Interestingly, the algorithm does not incorporate any symmetry-breaking scheme and illustrates the nice complementarity between constraint programming and local search on this scheduling application. [ABSTRACT FROM AUTHOR]