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 on 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 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 to find the optimal solution and to prove optimality, but the technique can be easily generalized for many other problems.
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 new scheduling and planning 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 timetabling problem originally motivated this constraint which was implemented within the SICStus finite domain solver and evaluated against different problem patterns.
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.
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 hybridising 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 route to a solution, and generate more implications at deep nodes. Experimental results confirm the efficiency of our approach.
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.
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.
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 in comparison 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.
Soft temporal constraints problems allow for a natural description of 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, 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 random 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.
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.
Random instances are widely used as benchmarks for evaluating algorithms for the finite-domain constraint satisfaction problem (CSP). Deciding satisfiability of instances from some distributions is challenging for known complete methods. We present an analysis that shows why. We describe a resolution-like refutation system for CSPs, and identify a structural property of instances which is sufficient to ensure that any refutation in this system is of exponential size. We then consider a typical model for random CSP instances, and show that for many parameter values almost all instances from the model have this property. The refutation system used can efficiently simulate the reasoning behaviour of a wide class of CSP algorithms, all of which will have exponential running time on these instances.
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.
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.
In this paper, a new pre-processing step is proposed in the resolution of SAT instances, that recovers and exploits some 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_1, ..., x_n) where f is a standard connective operator among (or, and, iff) 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.
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 > 1, 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 > 1, there is a polynomial-time a lgorithm 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".
Conway's game of Life provides interesting problems in which modelling issues in constraint programming can be explored. The problem of finding a maximum den sity stable pattern (`still-life') is discussed. A formulation of this proble m as a constraint satisfaction problem with 0-1 variables and non-binary constraints is compare d with its dual graph translation into a binary CSP. The success of the dual translation is surprising, from previously-reported e xperience, 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 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 that the consistency checking of a set of basic cardinal direction constraints can be performed in O(n^5) 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.
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 QBF algorithms, the problem database is presented in Conjunctive Normal Form (CNF), implications are generated from clauses, and backtrackings are 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 a search tree both provide valuable information to the solver in a symmetric way. We have implemented our algorithm in the new QBF solver Quaffle. Experiment results show that for some test cases, satisfiability directed implication and learning can greatly prune the search.
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 O(1.3247^n*(d/2)^n) time, or odd, in which case it runs in O(1.3247^n*((d^2+d+2)/4)^(n/2)) if d=4*k+1, and O(1.3247^n*((d^2+d)/4)^(n/2)) 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 O(1.8171^n), an improvement over the general algorithm gained by using problem specific knowledge.
We present an interface between the ECLIPSE constraint logic programming system and the GAP computational abstract algebra system. The interface provides a method for obtaining 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 provides improved search performance for symmetric constraint satisfaction problems.
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 be discovered 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 aim of this paper is to demonstrate that CP can be a better candi-date than MIP for solving the master problem within a Benders decomposition approach. Our demonstration is based on a case study of a workforce schedul-ing problem encountered in a large call center of Bouygues Telecom, a French mobile phone operator. Our experiments show that CP can advantageously re-place MIP for the implementation of the master problem due to its greater abil-ity 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 method for camera control. The aim is to determine the path of a camera that verifies given declarative properties on the desired image, \eg location or orientation of objects on the screen at a given time. The path is decomposed into 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.
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.
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 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.
This paper presents a hybrid method devleoped at France Telecom R&D to solve a difficult network problem. We introduce a framework for solving this problem within the allowed computing time. The 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 the 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 out method. Moreover, rerouting leads to accept of 46% of connections that are rejected by the greedy algorithm.
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 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 optimisation characteristics of LS. This local probing hybrid achieves sat-completeness, 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.
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. This lower bound is obtained by evaluating the violations involved by 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 month 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 hypothesis is made on the constraints except that their filtering algorithms are related to the bounds of the involved variables, the general case of 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.
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.
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. ACE is both a test-bed for CSP research and a discovery environment for new algorithms.
The pioneering works of [AptM:CP99] and [AbdennadherR:CP2000] have shown that the construction of rule-based solvers could be automated using machine learning techniques. Both works implement the solver as a set of CHRs [Fruhwirth:JLP98]. But many solvers use the more specialized chaotic iteration of operators \cite{FagesFS:JLP98,Apt:TCS99} 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 \cite{DiazC:SAC2000} 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 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 and domains of size d in O(nd) time. 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.
Symmetries in constraint satisfaction problems (CSPs) are one of the difficulties that practioners must 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 a generalization of the nogood recording presented by Focacci and Milano\cite{foca:mil} and Sellman et al.\cite{fahl:all}\cite{sell:harv}. We present a simple formalization of our method. 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. Those advantages result in a much greater efficiency. This is confirmed by an experimental evaluation on the social golfer problem, a very difficult and highly symmetrical real world problem. 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 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 the other PSPACE tasks which naturally arise in AI. Practical, 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, this paper provides a theoretical study of this problem. Our main result is to clarify the way information may be propagated among quantified variables, since we show that arbitrary levels of local consistency can be achieved.
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, making local search competitive with backtrack style approaches. 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.
We propose a new approach to understanding the algorithm-specific empirical hardness of NP-Hard optimization 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. First, we contrast the overall empirical hardness of the different distributions. Second, 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.
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 we gain in our analysis, we developed Scaling and Probabilistic Smoothing (SAPS), a new 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 Novelty+.
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.
The time required for a backtracking search procedure to solve a problem can be minimized with randomized restart procedures. To date, restart policies rely on the simplifying assumption that runs are probabilistically independent from one another. We relax the assumption of independence among runs and highlight 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 restarting. We present results of experiments on applying the methods to create ideal restart policies for several challenging search problems using two different solvers.
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 theGolfer 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 SBSS+, 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.
We introduce SensorCSP, 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 DSCP 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 DCSP algorithms: synchronous 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 DSCP 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.