Principles and Practice of Constraint Programming - CP 2002

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.

We consider the problem of Mutually Orthogonal Latin Squares and propose two algorithms which integrate Integer Programming (IP) and Constraint Programming (CP). Their behaviour is examined and compared to traditional CP and IP algorithms. The results assess the quality of inference achieved by the CP and IP, mainly in terms of early identification of infeasible subproblems. It is clearly illustrated that the integration of CP and IP is beneficial and that one hybrid algorithm exhibits the best performance as the problem size grows. An approach for reducing the search by excluding isomorphic cases is also presented.

In practice one has often to deal with the problem of inconsistency between constraints, as the result, among others, of the complexity of real models. To overcome these conflicts we can outline two major actions: removal of constraints or changes in the coefficients of the model. This last approach, that can be generically described as “model correction” is the problem we address in this paper. The correction of the right hand side alone was one of the first approaches. The correction of both the matrix of coefficients and the right hand side introduces non linearity in the constraints. The degree of difficulty in solving the problem of the optimal correction depends on the objective function, whose purpose is to measure the closeness between the original and corrected model. Contrary to other norms, the optimization of the important Frobenius was still an open problem. We have analyzed the problem using the KKT conditions and derived necessary and sufficient conditions which enabled us to unequivocally characterize local optima, in terms of the solution of the Total Least Squares and the set of active constraints. These conditions justify a set of pruning rules, which proved, in preliminary experimental results, quite successful in a tree search procedure for determining the global minimizer.

Temporal planning is an important problem, as in many real world planning domains actions have different durations and the goals should be achieved by a specified deadline, or as soon as possible. This paper presents a novel approach to temporal planning that is based on Mixed Integer Programming. In the new framework, a temporal planning domain is modeled by two sets of linear inequalities. The first set involves integer variables and is a Graphplan-like encoding of a simplification of the original problem where the duration of the actions is ignored. The second set involves both integer and real valued variables, and models the temporal aspects of the problem. The two sets interact through the common integer variables, and their combination can be solved by using available Mixed Integer Programming software. The new method aims at generating good solutions quickly, under different minimization objectives. Preliminary experimental results illustrate the effectiveness of our approach.

This paper presents a new cumulatives constraint, which generalizes the original cumulative constraint in different ways. The two most important aspects consist in permitting multiple cumulative resources as well as negative heights for the resource consumption of the tasks. This allows modeling in an easy way workload covering, producer-consumer, and scheduling problems. The introduction of negative heights has forced us to come up with new filtering algorithms and to revisit existing ones. The first filtering algorithm is derived from an idea called sweep, which is extensively used in computational geometry; the second algorithm is based on a combination of sweep and constructive disjunction; while the last is a generalization of task intervals to this new context. A real-life crew scheduling problem originally motivated this constraint which was implemented within the SICStus finite domain solver and evaluated against different problem patterns.

The global constraint sum can be used as a tool to implement summations over sets of variables whose indices are not known in advance. This paper has two major contributions. On the theoretical side, we present the convex hull relaxation for the sum constraint in terms of linear inequalities, whose importance in the context of hybrid models is then justified. On the practical side, we demonstrate the applicability of the sum constraint in a scheduling problem that arises as part of the development of new products in the pharmaceutical and agrochemical industries. This problem can be modeled in two alternative ways: by using the sum constraint in a natural and straightforward manner, or by using the element constraint in a trickier fashion. With the convex hull relaxation developed earlier, we prove that the linear relaxation obtained from the former model is tighter than the one obtained from the latter. Moreover, our computational experiments indicate that the CP model based on the sum constraint is significantly more efficient as well.

We propose some global constraints for lexicographic orderings on vectors of variables. These constraints are very useful for breaking a certain kind of symmetry arising in matrices of decision variables. We show that decomposing such constraints carries a penalty either in the amount or the cost of constraint propagation. We therefore present a global consistency algorithm which enforces a lexicographic ordering between two vectors of n variables in O(nb) time, where b is the cost of adjusting the bounds of a variable. The algorithm can be modified very slightly to enforce a strict lexicographic ordering. Our experimental results on a number of domains (balanced incomplete block design, social golfer, and sports tournament scheduling) confirm the efficiency and value of these new global constraints.

This paper introduces a new filtering algorithm for handling systems of quadratic equations and inequations. Such constraints are widely used to model distance relations in numerous application areas ranging from robotics to chemistry. Classical filtering algorithms are based upon local consistencies and thus, are unable to achieve a significant pruning of the domains of the variables occurring in quadratic constraints systems. The drawback of these approaches comes from the fact that the constraints are handled independently. We introduce here a global filtering algorithm that works on a tight linear relaxation of the quadratic constraints. First experimentations show that this new algorithm yields a much more effective pruning of the domains than local consistency filtering algorithms.

Randomization as a means for improving search performance in combinatorial domains has received increasing interest in recent years. In optimization contexts, it can provide a means for overcoming the deficiencies of available search heuristics and broadening search in productive directions. In this paper, we consider the issue of amplifying the performance of a search heuristic through randomization. We introduce a general framework for embedding a base heuristic within an iterative sampling process and searching a stochastic neighborhood of the heuristic’s prescribed trajectory. In contrast to previous approaches, which have used rank-ordering as a basis for randomization, our approach instead relies on assigned heuristic value. Use of heuristic value is important because it makes it possible to vary the level of stochasticity in relation to the discriminatory power of the heuristic in different decision contexts, and hence concentrate search around those decisions where the heuristic is least informative. To evaluate the efficacy of the approach, we apply it to a complex, weighted-tardiness scheduling problem. Taking a state-of-the-art heuristic for this scheduling problem as a starting point, we demonstrate an ability to consistently and significantly improve on the deterministic heuristic solution across a broad range of problem instances. Our approach is also shown to consistently outperform a previously developed, rank-ordering based approach to randomizing the same heuristic in terms of percentage of improvement obtained.

Computing tight resource-level bounds is a fundamental problem in the construction of flexible plans with resource utilization. In this paper we describe an efficient algorithm that builds a resource envelope, the tightest possible such bound. The algorithm is based on transforming the temporal network of resource consuming and producing events into a flow network with nodes equal to the events and edges equal to the necessary predecessor links between events. A staged maximum flow problem on the network is then used to compute the time of occurrence and the height of each step of the resource envelope profile. Each stage has the same computational complexity of solving a maximum flow problem on the entire flow network. This makes this method computationally feasible and promising for use in the inner loop of flexible-time scheduling algorithms.

This paper describes local probing, an algorithm hybridization form that combines backtrack search enhanced with local consistency techniques (BT+CS) with local search (LS) via probe backtracking. Generally BT+CS can be effective at finding solutions for (or proving the infeasibility of) tightly constrained problems with complex and overlapping constraints, but lacks good optimization characteristics. By contrast, LS can be superior at optimizing problems that are loosely constrained, or that have constraints which are satisfiable by simple neighbourhood procedures, but it also has several weaknesses of its own. It is weaker on problems with a complex constraint satisfaction element, and cannot prove problem infeasibility, causing prolonged execution times and ambiguous search outcomes for even trivially infeasible problems.We show these divergent characteristics on a general resource constrained scheduling problem class, extended with a widely applicable objective function. We then detail a local probing hybrid that marries the strengths of constraint satisfaction techniques, including good satisfaction characteristics and proofs of problem infeasibility, with the superior optimization characteristics of LS. This local probing hybrid achieves satcompleteness, without incorporating all the constraints into the LS neighbourhood function. Finally, we discuss the principal questions that must be answered in creating local probing hybrids for other problems.

Exploiting variable dependencies has been shown very useful in local search algorithms for SAT. In this paper, we extend the use of such dependencies by hybridizing a local search algorithm, Walksat, and the DPLL procedure, Satz. At each node reached in the DPLL search tree to a fixed depth, we construct the literal implication graph. Its strongly connected components are viewed as equivalency classes. Each one is substituted by a unique representative literal to reduce the constructed graph and the input formula. Finally, the implication dependencies are closed under transitivity. The resulted implications and equivalencies are exploited by Walksat at each node of the DPLL tree. Our approach is motivated by the power of the branching rule used in Satz that may provide a valid path to a solution, and generate more implications at deep nodes. Experimental results confirm the efficiency of our approach.

In this paper, a new pre-processing step is proposed in the resolution of SAT instances, that recovers and exploits structural knowledge that is hidden in the CNF. It delivers an hybrid formula made of clauses together with a set of equations of the form y = f(x₁,..., x _n ) where f is a standard connective operator among (∨, ∧, ⇔) and where y and x _i are boolean variables of the initial SAT instance. This set of equations is then exploited to eliminate clauses and variables, while preserving satisfiability. These extraction and simplification techniques allowed us to implement a new SAT solver that proves to be the most efficient current one w.r.t. several important classes of instances.

In this paper, we describe a new framework for evaluating Quantified Boolean Formulas (QBF). The new framework is based on the Davis-Putnam (DPLL) search algorithm. In existing DPLL based QBF algorithms, the problem database is represented in Conjunctive Normal Form (CNF) as a set of clauses, implications are generated from these clauses, and backtracking in the search tree is chronological. In this work, we augment the basic DPLL algorithm with conflict driven learning as well as satisfiability directed implication and learning. In addition to the traditional clause database, we add a cube database to the data structure. We show that cubes can be used to generate satisfiability directed implications similar to conflict directed implications generated by the clauses. We show that in a QBF setting, conflicting leaves and satisfying leaves of the search tree both provide valuable information to the solver in a symmetric way. We have implemented our algorithm in the new QBF solver Quaffle. Experimental results show that for some test cases, satisfiability directed implication and learning significantly prunes the search.

In recent years, there has been much research on local search techniques for solving constraint satisfaction problems, including Boolean satisfiability problems. Some of the most successful procedures combine a form of random walk with a greedy bias. These procedures are quite effective in a number of problem domains, for example, constraint-based planning and scheduling, graph coloring, and hard random problem instances. However, in other structured domains, backtrack-style procedures are often more effective. We introduce a technique that leads to significant speedups of random walk style procedures on structured problem domains. Our method identifies long range dependencies among variables in the underlying problem instance. Such dependencies are made explicit by adding new problem constraints. These new constraints can be derived efficiently, and, literally, “accelerate” the Random Walk search process. We provide a formal analysis of our approach and an empirical validation on a recent benchmark collection of hardware verification problems.

In this paper, we study the approach of dynamic local search for the SAT problem. We focus on the recent and promising Exponentiated Sub-Gradient (ESG) algorithm, and examine the factors determining the time complexity of its search steps. Based on the insights gained from our analysis, we developed Scaling and Probabilistic Smoothing (SAPS), an efficient SAT algorithm that is conceptually closely related to ESG. We also introduce a reactive version of SAPS (RSAPS) that adaptively tunes one of the algorithm’s important parameters. We show that for a broad range of standard benchmark problems for SAT, SAPS and RSAPS achieve significantly better performance than both ESG and the state-of-the-art WalkSAT variant, Novelty+.

Soft temporal constraints problems allow for a natural description of scenarios where events happen over time and preferences are associated with event distances and durations. However, sometimes such local preferences are difficult to set, and it may be easier instead to associate preferences to some complete solutions of the problem, and then to learn from them suitable preferences over distances and durations.In this paper, we describe our learning algorithm and we show its behaviour on classes of randomly generated problems. Moreover, we also describe two solvers (one more general and the other one more efficient) for tractable subclasses of soft temporal problems, and we give experimental results to compare them.

Russian Doll Search (RDS) is a clever procedure to solve overconstrained problems. RDS solves a sequence of nested subproblems, each including one more variable than the previous, until the whole problem is solved. Specialized RDS (SRDS) solves each subproblem for every value of the new variable. SRDS lower bound is better than RDS lower bound, causing a higher efficiency. A natural extension is Full Specialized RDS (FSRDS), which solves each subproblem for every value of every variable. Although FSRDS lower bound is better than the SRDS one, the extra work performed by FSRDS renders it inefficient. However, much of the useless work can be avoided. With this aim, we present Opportunistic Specialization in RDS (OSRDS), an algorithm that lies between SRDS and FSRDS. In addition to specialize the values of one variable, OSRDS specializes some values of other variables that look promising to increase the lower bound in the current distribution of inconsistency counts. Experimental results on random and real problems show the benefits of this approach.

A Max-CSP consists of searching for a solution which minimizes the number of violated constraints. The best existing solving algorithm is PFC-MRDAC. It is based on the computation of a lower bound of the number of violations. To compute this lower bound it is required to evaluate the violations with respect to each value of each domain. Unfortunately, some applications imply thousands of variables with huge domains. In scheduling, it arises that numerous activities have to be scheduled over several months with a unit of time of a few minutes. In this situation using PFC-MRDAC requires a large amount of memory which can prevent from using it. In this paper, we propose an algorithm called the Range-based Max-CSP Algorithm (RMA), based on the exploitation of bound-based filtering algorithms of constraints. This technique does not require to study each value of each domain: its complexity depends only on the number of variables and the number of constraints. No assumption is made on the constraints except that their filtering algorithms are related to the bounds of the involved variables, the general case for scheduling constraints. Then, when the only information available for a variable x w.r.t. a constraint C are the new bounds of D(x) obtained by applying the filtering algorithm of C, the lower bounds of violations provided by PFC-MRDAC and RMA are identical.

Random instances are widely used as benchmarks in evaluating algorithms for finite-domain constraint satisfaction problems (CSPs). We present an analysis that shows why deciding satisfiability of instances from some distributions is challenging for current complete methods. For a typical random CSP model, we show that when constraints are not too tight almost all unsatisfiable instances have a structural property which guarantees that unsatisfiability proofs in a certain resolution-like system must be of exponential size. This proof system can efficiently simulate the reasoning of a large class of CSP algorithms which will thus have exponential running time on these instances.

We systematically investigate the connections between constraint satisfaction problems, structures of bounded treewidth, and definability in logics with a finite number of variables. We first show that constraint satisfaction problems on inputs of treewidth less than k are definable using Datalog programs with at most k variables; this provides a new explanation for the tractability of these classes of problems. After this, we investigate constraint satisfaction on inputs that are homomorphically equivalent to structures of bounded treewidth. We show that these problems are solvable in polynomial time by establishing that they are actually definable in Datalog; moreover, we obtain a logical characterization of the property “being homomorphically equivalent to a structure of bounded treewidth” in terms of definability in finite-variable logics. Unfortunately, this expansion of the tractability landscape comes at a price, because we also show that, for each k ⩾ 2, determining whether a structure is homomorphically equivalent to a structure of treewidth less than k is an NP-complete problem. In contrast, it is well known that, for each k ⩾ 2, there is a polynomial-time algorithm for testing whether a given structure is of treewidth less than k. Finally, we obtain a logical characterization of the property “having bounded treewidth” that sheds light on the complexity-theoretic difference between this property and the property ‘being homomorphically equivalent to a structure of bounded treewidth”.

Counting the number of solutions to CSP instances has applications in several areas, ranging from statistical physics to artificial intelligence. We give an algorithm for counting the number of solutions to binary CSPs, which works by transforming the problem into a number of 2-sat instances, where the total number of solutions to these instances is the same as those of the original problem. The algorithm consists of two main cases, depending on whether the domain size d is even, in which case the algorithm runs in time, or odd, in which case it runs in if d = 4 · k + 1, and if d = 4 · k + 3. We also give an algorithm for counting the number of possible 3-colourings of a given graph, which runs in , an improvement over our general algorithm gained by using problem specific knowledge.

We present a formal model for qualitative spatial reasoning with cardinal directions and study the problem of checking the consistency of a set of cardinal direction constraints. We present the first algorithm for this problem, prove its correctness and analyze its computational complexity. Utilizing the above algorithm we prove that the consistency checking of a set of basic cardinal direction constraints can be performed in time while the consistency checking of an unrestricted set of cardinal direction constraints is NP-complete. Finally, we briefly discuss some extensions to the basic model.

Traditionally, constraint satisfaction has been applied in closed-world scenarios, where all choices and constraints are known from the beginning and fixed. With the Internet, many of the traditional CSP applications in resource allocation, scheduling and planning pose themselves in open-world settings, where choices and constraints are to bediscovered from different servers in a network. We examine how such a distributed setting affects changes the assumptions underlying most CSP algorithms, and show how solvers can be augmented with an information gathering component that allows open-world constraint satisfaction. We report on experiments that show strong performance of such methods over others where gathering information and solving the CSP are separated.

The generalization of the satisfiability problem with arbitrary quantifiers is a challenging problem of both theoretical and practical relevance. Being PSPACE-complete, it provides a canonical model for solving other PSPACE tasks which naturally arise in AI.Effective SAT-based solvers have been designed very recently for the special case of boolean constraints. We propose to consider the more general problem where constraints are arbitrary relations over finite domains. Adopting the viewpoint of constraint-propagation techniques so successful for CSPs, we provide a theoretical study of this problem. Our main result is to propose quantified arc-consistency as a natural extension of the classical CSP notion.

This paper develops a secure distributed Constraint Satisfaction algorithm. A Distributed Constraint Satisfaction Problem (DisCSP) is a CSP in which variables and constraints are distributed among multiple agents. A major motivation for solving a DisCSP without gathering all information in one server is the concern about privacy/security. However, existing DisCSP algorithms leak some information during the search process and privacy/security issues are not dealt with formally. Our newly developed algorithm utilizes a public key encryption scheme. In this algorithm, multiple servers, which receive encrypted information from agents, cooperatively perform a search process that is equivalent to a standard chronological backtracking. This algorithm does not leak any private information, i.e., neither agents nor servers can obtain any additional information on the value assignment of variables that belong to other agents.

Conway’s game of Life provides interesting problems in which modelling issues in constraint programming can be explored. The problem of finding a maximum density stable pattern (‘still-life’) is discussed. A formulation of this problem as a constraint satisfaction problem with 0-1 variables and non-binary constraints is compared with its dual graph translation into a binary CSP. The success of the dual translation is surprising, from previously-reported experience, since it has as many variables as the non-binary CSP and very large domains. An important factor is the identification of many redundant constraints: it is shown that these can safely be removed from a dual graph translation if arc consistency is maintained during search.

We present an interface between the ECLiPSe constraint logic programming system and the GAP computational abstract algebra system. The interface provides a method for efficiently dealing with large numbers of symmetries of constraint satisfaction problems for minimal programming effort. We also report an implementation of SBDS using the GAP-ECLiPSe interface which is capable of handling many more symmetries than previous implementations and provides improved search performance for symmetric constraint satisfaction problems.

In this paper we define partial symmetry breaking, a concept that has been used in many previous papers without being the main topic of any research. This paper is the first systematic study of partial symmetry breaking in constraint programming. We show experimentally that performing symmetry breaking with only a subset of all symmetries can result in greatly reduced run-times. We also look at the consequences of using partial symmetry breaking in terms of variable and value ordering heuristics. Finally, different methods of selecting symmetries are considered before presenting a general algorithm for selecting subsets of symmetries.

Symmetries in constraint satisfaction problems (CSPs) are one of the difficulties that practitioners have to deal with. We present in this paper a new method based on the symmetries of decisions taken from the root of the search tree. This method can be seen as an improvement of the nogood recording presented by Focacci and Milano[5] and Fahle, Schamberger and Sellmann[4]. We present a simple formalization of our method for which we prove correctness and completeness results. We also show that our method is theoretically more efficient as the number of dominance checks, the number of nogoods and the size of each nogood are smaller. This is confirmed by an experimental evaluation on the social golfer problem, a very difficult and highly symmetrical real world problem. We are able to break all symmetries for problems with more than 1036 symmetries. We report both new results, and a comparison with previous work.

We identify an important class of symmetries in constraint programming, arising from matrices of decision variables where rows and columns can be swapped. Whilst lexicographically ordering the rows (columns) breaks all the row (column) symmetries, lexicographically ordering both the rows and the columns fails to break all the compositions of the row and column symmetries. Nevertheless, our experimental results show that this is effective at dealing with these compositions of symmetries. We extend these results to cope with symmetries in any number of dimensions, with partial symmetries, and with symmetric values. Finally, we identify special cases where all compositions of the row and column symmetries can be eliminated by the addition of only a linear number of symmetry-breaking constraints.

The Social Golfer Problem has been extensively used in recent years by the constraint community as an example of highly symmetric problem. It is an excellent problem for benchmarking symmetry breaking mechanisms such as SBDS or SBDD and for demonstrating the importance of the choice of the right model for one problem. We address in this paper a specific instance of the Golfer Problem well known as the Kirkman’s Schoolgirl Problem and list a collection of techniques and tricks to find efficiently all its unique solutions. In particular, we propose SBDD+, an generic improvement over SBDD which allows a deep pruning when a symmetry is detected during the search. Our implementation of the presented techniques allows us to improve previous published results by an order of magnitude for CPU time as well as number of backtracks, and to compute the seven unique solutions of the Kirkman’s problem in a few seconds.

Capturing constraint structure is critical in Constraint Programming to support the configuration and adaptation of domain filtering algorithms. To this end, we propose a software model coupling a relational constraint language, a constraint type inference system, and an algorithm configuration system. The relational language allows for expressing constraints from primitive constraints; the type system infers the type of constraint expressions out of primitive constraint types; and the configuration system synthesises algorithms out of primitive routines using constraint types. In this paper, we focus on the issue of constraint type inferencing, and present a method to implement sound and extendible inference systems.

Programming complex embedded systems involves reasoning through intricate system interactions along paths between sensors, actuators and control processors. This is a time-consuming and error-prone process. Furthermore, the resulting code generally lacks modularity and robustness. Model-based programming addresses these limitations, allowing engineers to program by specifying high-level control strategies and by assembling common-sense models of the system hardware and software. To execute a control strategy, model-based executives reason about the models “on the fly”, to track system state, diagnose faults and perform reconfigurations. This paper describes the Reactive Model-based Programming Language (RMPL) and its executive, called Titan. RMPL provides the features of synchronous reactive languages within a constraint-based modeling framework, with the added ability of being able to read and write to state variables that are hidden within the physical plant.

The Adaptive Constraint Engine (ACE) seeks to automate the application of constraint programming expertise and the extraction of domain-specific expertise. Under the aegis of FORR, an architecture for learning and problem-solving, ACE learns search-order heuristics from problem solving experience. This paper describes ACE’s approach, as well as new experimental results on specific problem classes. ACE is both a test-bed for CSP research and a discovery environment for new algorithms.

The pioneering works of Apt and Monfroy, and Abdennadher and Rigotti have shown that the construction of rule-based solvers can be automated using machine learning techniques. Both works implement the solver as a set of CHRs. But many solvers use the more specialized chaotic iteration of operators as operational semantics and not CHR’s rewriting semantics. In this paper, we first define a language-independent framework for operator learning and then we apply it to the learning of partial arc-consistency operators for a subset of the indexical language of Gnu-Prolog and show the effectiveness of our approach by two implementations. On tested examples, Gnu-Prolog solvers are learned from their original constraints and powerful propagators are found for user-defined constraints.

We propose a new approach for understanding the algorithm-specific empirical hardness of -Hard problems. In this work we focus on the empirical hardness of the winner determination problem—an optimization problem arising in combinatorial auctions—when solved by ILOG’s CPLEX software. We consider nine widely-used problem distributions and sample randomly from a continuum of parameter settings for each distribution. We identify a large number of distribution-nonspecific features of data instances and use statistical regression techniques to learn, evaluate and interpret a function from these features to the predicted hardness of an instance.

The time required for a backtracking search procedure to solve a problem can be minimized by employing randomized restart procedures. To date, researchers designing restart policies have relied on the simplifying assumption that runs are probabilistically independent from one another. We relax the assumption of independence among runs and address the challenge of identifying an optimal restart policy for the dependent case. We show how offline dynamic programming can be used to generate an ideal restart policy, and how the policy can be used in conjunction with real-time observations to control the timing of restarts. We present results of experiments on applying the methods to create ideal restart policies for several challenging search problems using two different solvers.

Visopt ShopFloor is a complete system for solving real-life scheduling problems in complex industries. In particular, the system is intended to problem areas where traditional scheduling methods failed. In the paper we describe the heart of the Visopt system, a generic scheduling engine. This engine goes beyond traditional scheduling by offering some planning capabilities. We achieved this integrated behaviour by applying Constraint Logic Programming in a less standard way - the definition of a constraint model is dynamic and introduction of constraints interleaves with search.

The aim of this paper is to demonstrate that CP could be a better candidate than MIP for solving the master problem within a Benders decomposition approach. Our demonstration is based on a case study of a workforce scheduling problem encountered in a large call center of Bouygues Telecom, a French mobile phone operator. Our experiments show that CP can advantageously replace MIP for the implementation of the master problem due to its greater ability to efficiently manage a wide variety of constraints such as the ones occurring in time tabling applications.

In this paper, we introduce a high-level modeling approach to camera control. The aim is to determine the path of a camera that verifies given declarative properties on the desired image, e.g., location or orientation of objects on the screen at a given time. The path is composed of elementary movements called hypertubes, based on established cinematographic techniques. Hypertubes are connected by relations that guarantee smooth transitions. Interval consistency techniques and quantified constraint solving algorithms are used to compute and propagate solutions between consecutive hypertubes. Preliminary experimental results from a prototype show a great improvement in time and quality of animations with respect to former approaches.

Industrial optimization applications must be “robust,” i.e., must provide good solutions to problem instances of different size and numerical characteristics, and continue to work well when side constraints are added. This paper presents a case study in which this requirement and its consequences on the applicability of different optimization techniques have been addressed. An extensive benchmark suite, built on real network design data provided by France Telecom R&D, has been used to test multiple algorithms for robustness against variations in problem size, numerical characteristics, and side constraints. The experimental results illustrate the performance discrepancies that have occurred and how some have been corrected. In the end, the results suggest that we shall remain very humble when assessing the adequacy of a given algorithm for a given problem, and that a new generation of public optimization benchmark suites is needed for the academic community to attack the issue of algorithm robustness as it is encountered in industrial settings.

This paper presents a hybrid method developed at France Telecom R&D to solve a difficult network problem. It takes place in an ATM network administration context and consists in planning connection demands over a period of one year.We introduce a new framework for solving this problem within the allowed computing time. This framework is based on two major elements: first a hybrid method which mixes shortest path algorithms, constraint propagation and repairing principles, then a model for the time dimension which is a critical issue in this ATM network administration problem.We compare our method with a greedy method (without rerouting) presently used in FTR&D upon realistic problems. The results of our experiments show that the difficult problem of rerouting can be solved with our method. Moreover, rerouting leads to accept of 46% of connections that are rejected with the greedy algorithm.This paper is a revised version of [14].

We introduce SensorDCSP, a naturally distributed benchmark based on a real-world application that arises in the context of networked distributed systems. In order to study the performance of Distributed CSP (DisCSP) algorithms in a truly distributed setting, we use a discrete-event network simulator, which allows us to model the impact of different network traffic conditions on the performance of the algorithms. We consider two complete DisCSP algorithms: asynchronous backtracking (ABT) and asynchronous weak commitment search (AWC). In our study of different network traffic distributions, we found that, random delays, in some cases combined with a dynamic decentralized restart strategy, can improve the performance of DisCSP algorithms. More interestingly, we also found that the active introduction of message delays by agents can improve performance and robustness, while reducing the overall network load. Finally, our work confirms that AWC performs better than ABT on satisfiable instances. However, on unsatisfiable instances, the performance of AWC is considerably worse than ABT.

In an earlier paper we have shown, how one can successfully use constraint satisfaction techniques for proving and solving formulae in the first-order predicate language over the real numbers (i.e., real first-order constraints). This approach was restricted to inputs that contain inequality symbols such as ≤, but no equality symbols (=) or disequality symbols (≠). In this paper we lay the basis for extending this approach to inputs that contain (dis)equalities. This considerably widens the practical applicability of numerical constraint satisfaction methods.

Hybrid methods that combine constraint programming with mathematical programming make essential use of continuous relaxations for global constraints. We state a relaxation for the cumulative constraint. In particular we identify facet-defining inequalities for problems in which some jobs have the same duration, release time, and resource consumption rate. We also identify a much larger class of valid inequalities that exist in all problems.

GSAT has been proven highly effective for solving certain classes of large SAT problems. It starts from a randomly generated truth assignment and tries to reduce the number of violated clauses by iteratively flipping some variables’ truth value. GSATs effectiveness arises from the speed of a single flip, since this allows a large space of possible solutions to be explored. It does not examine any inter-relationship between the clauses of the problem it attacks.2SAT problems are highly tractable (linear time solvable), and some SAT problems, such as graph colouring, contain a high proportion of 2SAT information. In this paper we show how we can alter GSAT to take into account the 2SAT clauses, so that it never investigates truth assignments that violate a binary clause. This reduces the search space considerably. We give experimental results illustrating the benefit of our new approach on hard 3SAT problems involving a substantial 2SAT component.

Model-based applications in engineering, such as diagnosis, configuration or interactive decision-support systems, require embedded constraint solvers with challenging capabilities. Not only consistency checking and solving, but also the computation of (minimal) conflicts and explanations are required. Moreover, realistic models of engineered systems often require the usage of very expressive constraint languages, which mix continuous and discrete variable domains, linear and non-linear equations, inequations, and even procedural constraints. A positive feature of the models of typical engineered systems is, however, that their corresponding constraint problems have a bounded and even relatively small density (induced width).We present here our relational constraint solver RCS that has been specifically designed to address these requirements. RCS is based on variable elimination, exploiting the low-density property. To analyze a set of constraints, RCS builds a so-called aggregation tree by joining the input constraints and eliminating certain variables after every single join. The aggregation tree is then used to compute solutions, as well as explanations and conflicts. We also report some preliminary experimental results obtained with a prototype implementation of this framework.

Scheduling problems have been studied a lot over the last decade. Due to the complexity and the variety of such problems, most work consider static problems in which activities are known in advance and constraints are fixed. However, every schedule is subject to unexpected events (consider for example a new activity to schedule or a machine breakdown). In these cases, a new solution taking these events into account is needed in a preferably short time and as close as possible to the current solution.

Experimental results are given on the scaling of the Pure Random Walk version (PRWSAT) of WalkSAT. PRWSAT is very simple because of the absence of heuristics: not only the clause is selected at random, but also the literal within that clause. The main result is that, despite the simplicity and absence of heuristics, it has non-trivial behavior on Random 3-SAT. There appears to be a threshold at a clause/variable ratio of about 2.65. Below the threshold, problems are solved in a tightly-distributed and linear number of flips. Above the threshold scaling appears to be non-polynomial. The simplicity and the nontrivial threshold make it a good candidate for theoretical analysis.

In this work we address the question of whether and how parallel local search exhibits the criticality and parallelism phenomenon when performed on structured instances. We experimentally show that also for structured instances there exists an optimal value of parallelism which enables the algorithm to reach the optimal performance and, by analyzing the frequency of node degree of the graphs associated with the SAT instances, we observe that an asymmetric and not regular distribution strongly affects the algorithm performance with respect to the parallelism.

Using the literal encoding of the satisfiability problem (SAT) as a binary constraint satisfaction problem (CSP), we relate the path consistency concept and the row convexity of CSPs with the inference rules in the propositional logic field. Then, we use this result to propose a measure characterizing satisfiable and unsatisfiable 3-SAT instances. The correlation between the computational results allows us to validate this measure.

Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we consider how the same concepts can be extended to soft constraint satisfaction problems (SCSPs).We introduce the notions of threshold α and degradation δ for substitutability and interchangeability. In _αinterchangeability, values are interchangeable in any solution that is better than a threshold α, thus allowing to disregard differences among solutions that are not sufficiently good anyway. In δinterchangeability, values are interchangeable if their exchange could not degrade the solution by more than a factor of δ.Theorems, algorithms to compute (δ/α)interchangeable sets of values, and a more general treatment of all the ideas presented in this paper can be found in [2].

Real-world constraint problems abound with uncertainty. Problems with incomplete or erroneous data are often simplified at present to tractable deterministic models, or modified using error correction methods, with the aim of seeking a solution. However, this can lead us to solve the wrong problem because of the approximations made, an outcome of little help to the user who expects the right problem to be tackled and correct information returned. The certainty closure framework aims at fulfilling these expectations of correct, reliable reasoning in the presence of uncertain data. In this short paper we give an intuition and brief overview of the framework. We define the certainty closure to an uncertain constraint problem and show how it can be derived by transformation to an equivalent certain problem. We outline an application of the framework to a real-world network traffic analysis problem.

For NP-hard constraint satisfaction problems the existence of a feasible solution cannot be decided efficiently. Applying a tree search often results in the exploration of parts of the search space that do not contain feasible solutions at all. Redundant constraints can help to detect inconsistencies of partial assignments higher up in the search tree. Using the social golfer problem as an example we show how complex redundant constraints can be propagated incompletely using local search heuristics.

Historically, discrete minimization problems in constrained logical programming were modeled with the help of an isolated bounding constraint on the objective that is to be decreased. To overcome this frequently inefficient way of searching for improving solutions, the notion of optimization constraints was introduced. Optimization constraints can be viewed as global constraints that link the objective with other constraints of the problem at hand. We present an arc-consistency (actually: hyper-arc-consistency) algorithm for the minimum weight all different constraint which is an optimization constraint that consists in the combination of a linear objective with an all different constraint.

The task at hand is to tackle Constraint Satisfaction Problems (CSPs) defined in the sense of Mackworth [4]. This paper aims to take a first step towards a CSP-based module systems for constraint programming languages and modeling tools. The call for such a system is two-fold. First, most existing constraint programming languages have some sort of module systems, but these systems are designed for the underlying languages. Thus these module systems facilitate the construction of large constraint programs in a particular language, but not of CSP models. Second, a module system designed for CSP models with clear and clean semantics should allow us to reason the properties of CSP models declaratively without actually solving the CSPs. As a first attempt, we introduce six operators for manipulating and transforming CSP models: namely intersection, union, channeling, induction, negation, and complementation. For each operator, we give its syntactic construction rule, define its set-theoretic meaning, and also examine its algebraic properties, all illustrated with examples where appropriate. Our results show that model intersection and union form abelian monoids respectively among others.

Arc-consistency algorithms prune the search-space of Constraint Satisfaction Problems (CSPs). They use support-checks to find out about the properties of CSPs. Their arc-heuristics select the constraint and their domain-heuristics select the values for the next support-check. We shall combine AC-3 and DEE and equip the resulting hybrid with a double-support domain-heuristic. The resulting hybrid AC-3_d is easy to implement and requires the same data structures as AC-3 thereby improving on AC-7’s space-complexity. We shall present experimental results which indicate that AC-3 can compete with AC-7.

Asynchronous Constraint Solving (ACS) integrates dynamic constraint processing into concurrent Object Oriented Programming. Cooperating constraint solvers run in parallel to the application program and infer actual variable domains incrementally from constraints that are added or retracted in the application thread. Constraint addition starts a chaotic iteration on the variable domains leading to a fixed point where no more domain reductions can be deduced from the constraint implementations. Constraint retraction removes all consequences of a constraint from the knowledge represented in the variables and can thus be considered the inverse operation to constraint addition.

In Railway Simulation, given timetables have to be checked against various criteria, mainly correctness and robustness. Most existing approaches use classical centralized simulation techniques. This work goes beyond that in two main aspects: I use Constraint Satisfaction to get rid of dead lock problems and the simulation is done distributed. This should make it possible to solve a Railway Simulation problem, never solved before in its complexity: the German railway network. In all existing simulation approaches, physical systems are described in terms of states and (mostly discrete) events. In Constraint-Based Simulation, we use a modeling that is completely different to classical approaches: The system to be simulated is described as one complex Constraint Satisfaction Problem (CSP). This CSP is solved using the well-known propagation and search techniques. In our application, the railway network is mapped into an abstract discrete model: It is divided into blocks, while each real track section may belong to more than one block. A block is then the atomical exclusion unit: In no event, one block may be occupied by more than one train at the same time. The way of a train through the network is divided into parts such that each part refers to exactly one block and the concatenation of all parts makes up the whole way of the train from its source to its destination. Assigning start and duration times to each part wrt. its block then gives directly a solution to the simulation problem. The big advantage of this approach is that dead lock situations are detected very early: constraint propagation does this for us.

The “Peaceably Coexisting Armies of Queens” problem [1] is a difficult optimisation problem on a chess-board, requiring equal numbers of black and white papers to be placed on the board so that the white queens cannot attack the black queens (and necessarily vice versa).

Batch processing with sequence dependent setup times is a new extension of the disjunctive scheduling (scheduling on a unary resource). There are several successful filtering algorithms for solving disjunctive scheduling problem in a constraint programming framework. I adapted two of these algorithms (namely edge-finding and not-first/not-last) for the new extended problem and developed other three algorithms (not-before/not-after, precedence-graph-based filtering, sequence composition). Each of these algorithms filters out a different type of inconsistent values so they can be used together to achieve the maximum filtering.

We present a hybrid heuristic search algorithm for constraint satisfaction problems, which was proposed as a mixture of two basic approaches: local search and backtrack based search. One of its major advantages is interactive behaviour in the sense of changing the task during the search. Some results are presented using the well known n-queens problem.

Real-world Large Scale Combinatorial Optimisation problems (LSCOs) have inherent data uncertainties. The uncertainty can be due to the dynamic and unpredictable nature of the commercial world, but also due to the information available to those modelling the problem. We are concerned with the latter form of uncertainty, which can arise when the data is not fully known or is even erroneous. Our work is motivated by practical issues faced in real-world applications, for instance in energy trading [1]. Here, the demand and cost profiles have evolved due to market privatisation; thus the existing simulation or stochastic data models would not help address the actual problem.

Metaheuristics [1] are approximate algorithms which effectively and efficiently exploit search space characteristics to find near-optimal solutions. Their combination with CP [2] is also very successful. In this work we present a new metaheuristic for tackling large MAXSAT instances. A survey of the state of the art of metaheuristics for MAXSAT can be found in [4]. The algorithm we designed is based on Iterated Local Search strategy [3] and combines the most effective local search strategies for SAT problems. Its high level scheme is the following: The most important property of ILS-MAXSAT is to achieve a dynamic balance between intensi.cation and diversi.cation, crucial in the exploration of large search spaces. The algorithm has been proven very effective on large unweighted MAXSAT instances and extensive comparisons with the best available algorithms is subject of ongoing work.

In this work, we extend the class of Horn constraints to include disjunctions with an arbitrary number of linear inequalities, linear disequations and non-linear disequations. We propose a preprocess step in which two algorithms are carried out. The first algorithm called Constraint Selection Algorithm (CSA) translates the disjunctive non-binary CSP into a non-disjunctive one. This algorithm selects the more appropriate set of atomic constraints that is more likely to be consistent. The second algorithm called Constraint Ordering Algorithm (COA) classifies the resultant constraints from the most restricted to the least restricted one. Then, a CSP solver carries out the search through the non-disjunctive and ordered problem.

Propositional Satisfiability (SAT) is a well-known NP-complete problem, being fundamental in solving many application problems in Computer Science and Engineering. Recent work on SAT has provided experimental and theoretical evidence that the use of randomization can be quite effective at solving hard instances of SAT. First, randomization was used in local search SAT algorithms, where the search is started over again to avoid getting stuck in a locally optimal partial solution. Moreover, in the last few years randomization has also been included in systematic search algorithms. As a result, backtrack search is given more freedom either to find a solution or to prove unsatisfiability. Indeed, backtrack search algorithms, randomized and run with restarts, were shown to perform significantly better on specific problem instances.

Test data generation is the most labor-intensive work for software testing. As a result, automatic test case generation is a way forward. It is typical to denote the conditions of searching the test input that can cause a particular action to occur into constraint problems. Consequently, practical method for solving the constraints is desired.

Local search for constraint satisfaction is usually performed by local minimization of a cost function. Traditionally, the cost function used is simply the number of violated constraints for a given assignment. When introducing global constraints in local search, use of this cost function will give the effect that practically no global constraints will be satisfied. The reason for this is that global constraints in general are much harder to satisfy than other constraints, and are as a consequence of this also hard to satisfy within the limited neighborhood of the current assignment. Another reason is that the value of satisfying a global constraint is as low as for any other constraint. Specific cost functions for global constraints have been proposed to amend this. The total cost of an assignment using this scheme is the sum of the costs of the constraints present.

This paper reports on the macron (Modeling and Acquiring Constraints Reusing Object Notation) project, which defines a modeling framework for CSPs compliant to available standards.

We will present an algorithm for the satisfiability problem, which finds its origin in the Integer Programming area, and therefore will also generalize to more general constraint programming problems. This algorithm is based on single-lookahead unit resolution ([2]), linear programming and a new search tree design based on a tree design by ([1]). The special aspect of the tree is that it is not a binary search tree. The advantage of our algorithm over a standard integer programming approach, is that we need to solve a linear program only in a very limited number of nodes in the search tree. In every node in the search tree we first apply single-lookahead unit resolution. The unit propagation algorithm we used in our implementation is based on the watched literal strategy. Only in case the unit resolution does not lead to the conclusion that the formula in the node is unsatisfiable or has a satisfying assignment, we solve a linear program. The solution of the linear program is used to split the part of the search into subparts. This splitting aims for getting a formula close to a Horn formula.

We present trajectory determination of Autonomous Vehicles as an extension of the open-path asymmetric Traveling Salesman Problem with Time Windows.

We discuss how the use of Constraint Programming can help speed up a Column Generation process for the Tail Assignment problem. A generalized preprocessing technique based on constraint propagation is presented that can remove up to 98% of the connections of the flight network, much more than methods currently in use. The result is substantial speed-up and increased solution quality for the column generator. We also show how propagation can be used within fixing heuristics, and present a heuristic propagation-based preprocessing method taking cost into consideration. Computational results on data from several airlines is presented.

Soft temporal constraints problems (TCSPs) allow to describe in a natural way scenarios where events happen over time and preferences are associated to event distances and durations. However, sometimes such local preferences are difficult to set, and it may be easier instead to associate preferences to some complete solutions of the problem. The Constraint Satisfaction framework combined with Machine learning techniques can be useful in this respect. Soft constraints are useful in general for manipulating preferences. In particular it is possible to approximate CP nets, a graphical representation of ceteris paribus conditional preference statements, with semiring based soft constraints problems.

In order to support constraint solving for challenging engineering applications, as e.g. accomplished by the Relational Constraint Solver (see [MST]), we need to implement join and project operators (see e.g. [AHV] or [M]) for heterogeneous constraints. The heterogeneity is due to finite domain and real-valued variables, linear and non-linear arithmetic constraints, (dis-)equations and inequalities.

There are many problems that can be modelled as injection problems. These problems can be scheduling problems, combinatorial graph problems, cryptarithmetic puzzles, etc. Injection problems can be modelled as constraint satisfaction problems. The straightforward formulation would be to have as many variables as the elements of the source set that range over the target set, which captures a total function. To enforce that the function is injective, we would need to state an alldifferent constraint among all the variables. Dual variables can also be used along with the primal ones and linked through channeling constraints. We propose three different ways of achieveing this, as well as we add some implied constraints. The proposed models of injection problems are compared using the constraint tightness parameterized by the level of local consistency being enforced [2]. We proved that, with respect to arc-consistency a single primal alldifferent constraint is tighter than channeling constraints together with the implied or the dual not-equals constraints, but that the channeling constraints alone are as tight as the primal not-equals constraints. Both these gaps can lead to an exponential reduction in search cost when MAC or MGAC are used. The theoretical results showed that occurs constraints on dual variables are redundant, so we can safely discard them. The asymptotic analysis added details to the theoretical results. We conclude that it is safe to discard some of the models because they achieve less pruning than other models at the same cost. However, we keep a model employing primal and dual variables even though it achieves the same amount of pruning as a primal model at a higher cost because it might allow the development of cheap value ordering heuristics. Experimental results on a sport scheduling problem confirmed that MGAC on channeling and implied constraints outperformed MAC on primal not-equals constraints, and could be competitive with maintaining GAC on a primal alldifferent constraint.

In this paper I define partial symmetry breaking, a concept that has been used in many previous papers without being the main topic of any research.

Propositional satisfiability (SAT) is the archetypal NP-complete problem [1]. A great deal of recent SAT research, particularly on the performance of SAT solvers, has been driven by structured instances, which are obtained by mapping other problem classes into SAT. It is possible to efficiently solve a wide range of problems by mapping them into SAT and solving the SAT representation of the problem.

Our research program is aimed at bridging the gap between propositional satisfiability encodings and constraint satisfaction formalisms. The challenge is to combine the inherent efficiencies of SAT solvers operating on uniform satisfiability encodings with the much more compact and natural representations, and more sophisticated propagation techniques of CSP formalisms. Our research objective is to define a new language —MV-SAT— that incorporates the best characteristics of the existing many-valued languages [1,2], as well as to develop fast MV-SAT solvers. MV-SAT is formally defined as the problem of deciding the satisfiability of MV-formulas. An MV-formula is a classical propositional conjunctive clause form based on a generalized notion of literal, called MV-literal. Given a domain T (|T| ≥ 2) equipped with a total ordering ≤, an MV-literal is an expression of the form S: p, where p is a propositional variable and S is a subset of T which is of the form {i}, ↑ i = {j ∈ T | j ≥ i}, or ↓ i = {j ∈ T | j ≤ i} for some i ∈ T. The informal meaning of S: p is “p is constrained to the values in S”.

Symmetry in a CSP is a permutation of variables, or the values in the domains, or both which preserve the state of the search: either all of them lead to a solution or none does. Hence, elimination of symmetry is essential to avoid exploring equivalent branches in a search tree. An important class of symmetries in constraint programming arises from matrices of decision variables where any two rows can be interchanged, as well as any two columns. Eliminating all such symmetries is not so easy as the effort required may be exponential. We are thus interested in reducing significant amount of row and column symmetries in matrix models with a polynomial effort. In this respect, we have shown that lexicographically ordering both rows and columns of a matrix model reduces much of such symmetries. For an n × n matrix model with row and column symmetry, O(n) lexicographic constraints between adjacent rows and columns are imposed. We have shown that decomposing a lexicographic ordering constraint between a pair of vectors carries a penalty either in the amount or the cost of constraint propagation. We have therefore developed a linear-time global-consistency algorithm which enforces a lexicographic ordering between two vectors. Our experiments confirm the efficiency and value of this new global constraint. As a matrix model has multiple rows and columns, we can treat such a problem as a single global ordering constraint over the whole matrix. Alternatively, we can decompose it into lexicographic ordering constraints between all or adjacent pairs of vectors. Such decompositions hinder constraint propagation in general. However, we identify the special case of a lexicographical ordering on 0/1 variables where it does not.

Most work in constraint satisfaction has concentrated on computing a solution to a given problem. In practice, it often happens that an existing solution needs to be modified to satisfy additional criteria or changes in the problem. For example, a schedule or plan might have to be adjusted when a resource is missing. The concept of interchangeability characterizes the possibilities for making local changes to CSP solutions.

We explore fundamental issues of the modeling, implementation, and processing of non-binary constraints. General techniques for reformulating non-binary constraints (i.e., hidden variable, dual graph [1]) are not practical for high-arity constraints [4]. In our study, we motivate our need to express practical requirements as non-binary constraints, then we explore reformulation methods to deal with them since the conventional methods [1] become impractical. Our work builds on the work of Gent et al. [2], while we motivate and anchor our investigations in the practical context of a real-world application. This is the assignment of graduate teaching assistants to courses in our department. This task is a critical responsibility that our department’s administration has to drudge through every semester. The idea for this particular application is borrowed from Rina Dechter, at the UC Irvine. We model this application using 4 types of unary constraints, one type of binary constraint, and 3 types of non-binary constraints. Since in our application problems are over-constrained, a satisfactory assignment is one that maximizes the number of courses covered. For this purpose, we adopt a new consistency checking mechanism that allows variables to be assigned a null value during search. For two assignments that cover the same number of courses, we further discriminate between them by choosing the one of highest quality, obtained by a combination of the value of the preferences in each assignment. We experiment with two different criteria to maximize preferences. We establish that two of our non-binary constraints are decomposable into equivalent networks of binary constraints, which significantly improves the performance of search [3]. Our efforts have resulted in a prototype system under field-test since August 2001. This system has effectively reduced the number of conflicts, thus yielding a commensurate increase in course quality. It has also decreased the amount of time and effort spent on making the assignment and gained the approval and satisfaction of our staff, faculty and student body.

We examine several issues associated with the design of agents trading in e-marketplaces. We use an adaptive, robust agent architecture combining principled methods and empirical knowledge. The agent needs to solve an optimization problem in order to maximize its gain. Deciding the optimal quantities to buy and sell is only part of the problem. The desired prices and the time of bid placement is also important. Bid aggressiveness must be balanced against the cost of obtaining increased flexibility.