Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools

Several grammar-based genetic programming algorithms have been proposed in the literature to automatically generate heuristics for hard optimization problems. These approaches specify the algorithmic building blocks and the way in which they can be combined in a grammar; the best heuristic for the problem being tackled is found by an evolutionary algorithm that searches in the algorithm design space defined by the grammar.In this work, we propose a novel representation of the grammar by a sequence of categorical, integer, and real-valued parameters. We then use a tool for automatic algorithm configuration to search for the best algorithm for the problem at hand. Our experimental evaluation on the one-dimensional bin packing problem and the permutation flowshop problem with weighted tardiness objective shows that the proposed approach produces better algorithms than grammatical evolution, a well-established variant of grammar-based genetic programming. The reasons behind such improvement lie both in the representation proposed and in the method used to search the algorithm design space.     

Backjump-based backtracking for constraint satisfaction problems

The performance of backtracking algorithms for solving finite-domain constraint satisfaction problems can be improved substantially by look-back and look-ahead methods. Look-back techniques extract information by analyzing failing search paths that are terminated by dead-ends. Look-ahead techniques use constraint propagation algorithms to avoid such dead-ends altogether. This paper describes a number of look-back variants including backjumping and constraint recording which recognize and avoid some unnecessary explorations of the search space. The last portion of the paper gives an overview of look-ahead methods such as forward checking and dynamic variable ordering, and discusses their combination with backjumping.     

Lexicographically-ordered constraint satisfaction problems

We describe a simple CSP formalism for handling multi-attribute preference problems with hard constraints, one that combines hard constraints and preferences so the two are easily distinguished conceptually and for purposes of problem solving. Preferences are represented as a lexicographic order over complete assignments based on variable importance and rankings of values in each domain. Feasibility constraints are treated in the usual manner. Since the preference representation is ordinal in character, these problems can be solved with algorithms that do not require evaluations to be represented explicitly. This includes ordinary CSP algorithms, although these cannot stop searching until all solutions have been checked, with the important exception of heuristics that follow the preference order (lexical variable and value ordering). We describe relations between lexicographic CSPs and more general soft constraint formalisms and show how a full lexicographic ordering can be expressed in the latter. We discuss relations with (T)CP-nets, highlighting the advantages of the present formulation, and we discuss the use of lexicographic ordering in multiobjective optimisation. We also consider strengths and limitations of this form of representation with respect to expressiveness and usability. We then show how the simple structure of lexicographic CSPs can support specialised algorithms: a branch and bound algorithm with an implicit cost function, and an iterative algorithm that obtains optimal values for successive variables in the importance ordering, both of which can be combined with appropriate variable ordering heuristics to improve performance. We show experimentally that with these procedures a variety of problems can be solved efficiently, including some for which the basic lexically ordered search is infeasible in practice.     

A knowledge representation for constraint satisfaction problems

We present a general representation for problems that can be reduced to constraint satisfaction problems (CSP) and a model for reasoning about their solution. The novel part of the model is a constraint-driven reasoner that manages a set of constraints specified in terms of arbitrarily complex Boolean expressions and represented in the form of a dependency network. This dependency network incorporates control information (derived from the syntax of the constraints) that is used for constraint propagation, contains dependency information that can be used for explanation and for dependency-directed backtracking, and is incremental in the sense that if the problem specification is modified, a new solution can be derived by modifying the existing solution. The constraint-driven reasoner is coupled to a problem solver which contains information about the problem variables and preference orderings     

Nogood-FC for solving partitionable constraint satisfaction problems

Many real problems can be naturally modelled as constraint satisfaction problems (CSPs). However, some of these problems are of a distributed nature, which requires problems of this kind to be modelled as distributed constraint satisfaction problems (DCSPs). In this work, we present a distributed model for solving CSPs. Our technique carries out a partition over the constraint network using a graph partitioning software; after partitioning, each sub-CSP is arranged into a DFS-tree CSP structure that is used as a hierarchy of communication by our distributed algorithm. We show that our distributed algorithm outperforms well-known centralized algorithms solving partitionable CSPs.     

Low-level dichotomy for quantified constraint satisfaction problems

Building on a result of Larose and Tesson for constraint satisfaction problems (CSPs), we uncover a dichotomy for the quantified constraint satisfaction problem QCSP(B), where B is a finite structure that is a core. Specifically, such problems are either in ALogtime or are L-hard. This involves demonstrating that if CSP(B) is first-order expressible, and B is a core, then QCSP(B) is in ALogtime.We show that the class of B such that CSP(B) is first-order expressible (indeed trivial) is a microcosm for all QCSPs. Specifically, for any B there exists a C — generally not a core — such that CSP(C) is trivial, yet QCSP(B) and QCSP(C) are equivalent under logspace reductions.     

Solving quantified constraint satisfaction problems

We make a number of contributions to the study of the Quantified Constraint Satisfaction Problem (QCSP). The QCSP is an extension of the constraint satisfaction problem that can be used to model combinatorial problems containing contingency or uncertainty. It allows for universally quantified variables that can model uncertain actions and events, such as the unknown weather for a future party, or an opponent's next move in a game. In this paper we report significant contributions to two very different methods for solving QCSPs. The first approach is to implement special purpose algorithms for QCSPs; and the second is to encode QCSPs as Quantified Boolean Formulas and then use specialized QBF solvers. The discovery of particularly effective encodings influenced the design of more effective algorithms: by analyzing the properties of these encodings, we identify the features in QBF solvers responsible for their efficiency. This enables us to devise analogues of these features in QCSPs, and implement them in special purpose algorithms, yielding an effective special purpose solver, QCSP-Solve. Experiments show that this solver and a highly optimized QBF encoding are several orders of magnitude more efficient than the initially developed algorithms. A final, but significant, contribution is the identification of flaws in simple methods of generating random QCSP instances, and a means of generating instances which are not known to be flawed.     

Solving set-valued constraint satisfaction problems

In this paper, we consider the resolution of constraint satisfaction problems in the case where the variables of the problem are subsets of ${\mathbb{R}^{n}}$ . In order to use a constraint propagation approach, we introduce set intervals (named i-sets), which are sets of subsets of ${\mathbb{R}^{n}}$ with a lower bound and an upper bound with respect to the inclusion. Then, we propose basic operations for i-sets. This makes possible to build contractors that are then used by the propagation to solve problem involving sets as unknown variables. In order to illustrate the principle and the efficiency of the approach, a testcase is provided.     

Relaxations of semiring constraint satisfaction problems

The Semiring Constraint Satisfaction Problem (SCSP) framework is a popular approach for the representation of partial constraint satisfaction problems. In this framework preferences can be associated with tuples of values of the variable domains. Bistarelli et al. [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraint solving and optimization, Journal of the ACM 44 (2) (1997) 201-236] defines a maximal solution to a SCSP as the best set of solution tuples for the variables in the problem. Sometimes this maximal solution may not be good enough, and in this case we want to change the constraints so that we solve a problem that is slightly different from the original problem but has an acceptable solution. We propose a relaxation of a SCSP, and use a semiring to give a measure of the difference between the original SCSP and the relaxed SCSP. We introduce a relaxation scheme but do not address the computational aspects.     

Increasing tree search efficiency for constraint satisfaction problems

In this paper we explore the number of tree search operations required to solve binary constraint satisfaction problems. We show analytically and experimentally that the two principles of first trying the places most likely to fail and remembering what has been done to avoid repeating the same mistake twice improve the standard backtracking search. We experimentally show that a lookahead procedure called forward checking (to anticipate the future) which employs the most likely to fail principle performs better than standard backtracking, Ullman's, Waltz's, Mackworth's, and Haralick's discrete relaxation in all cases tested, and better than Gaschnig's backmarking in the larger problems.     

Dynamic structural symmetry breaking for constraint satisfaction problems

In recent years, symmetry breaking for constraint satisfaction problems (CSPs) has attracted considerable attention. Various general schemes have been proposed to eliminate symmetries. In general, these schemes may take exponential space or time to eliminate all the symmetries. We identify several classes of CSPs that encompass many practical problems and for which symmetry breaking for various forms of value or variable interchangeability is tractable using dedicated search procedures. We also show the limits of efficient symmetry breaking for such dominance-detection schemes by proving intractability results for some classes of CSPs.     

Dynamic constraint satisfaction problems over models

In early phases of designing complex systems, models are not sufficiently detailed to serve as an input for automated synthesis tools. Instead, a design space is constituted by multiple models representing different valid design candidates. Design space exploration aims at searching through these candidates defined in the design space to find solutions that satisfy the structural and numeric design constraints and provide a balanced choice with respect to various quality metrics. Design space exploration in an model-driven engineering (MDE) context is frequently tackled as specific sort of constraint satisfaction problem (CSP). In CSP, declarative constraints capture restrictions over variables with finite domains where both the number of variables and their domains are required to be a priori finite. However, the existing formulation of constraint satisfaction problems can be too restrictive to capture design space exploration in many MDE applications with complex structural constraints expressed over the underlying models. In this paper, we interpret flexible and dynamic constraint satisfaction problems directly in the context of models. These extensions allow the relaxation of constraints during a solving process and address problems that are subject to change and require incremental re-evaluation. Furthermore, we present our prototype constraint solver for the domain of graph models built upon the Viatra2 model transformation framework and provide an evaluation of its performance with comparison to related tools.     

Argumentation frameworks as constraint satisfaction problems

Argumentation is a promising approach for defeasible reasoning. It consists of justifying each plausible conclusion by arguments. Since the available information may be inconsistent, a conclusion and its negation may both be justified. The arguments are thus said to be conflicting. The main issue is how to evaluate the arguments. Several semantics were proposed for that purpose. The most important ones are: stable, preferred, complete, grounded and admissible. A semantics is a set of criteria that should be satisfied by a set of arguments, called extension, in order to be acceptable. Different decision problems related to these semantics were defined (like whether an argumentation framework has a stable extension). It was also shown that most of these problems are intractable. Consequently, developing algorithms for these problems is not trivial and thus the implementation of argumentation systems not obvious. Recently, some solutions to this problem were found. The idea is to use a reduction method where a given problem is translated in another one like SAT or ASP. This paper follows this line of research. It studies how to encode the problem of computing the extensions of an argumentation framework (under each of the previous semantics) as a constraint satisfaction problem (CSP). Such encoding is of great importance since it makes it possible to use the very efficient solvers (developed by the CSP community) for computing the extensions. Our encodings take advantage of existing reductions to SAT problems in the case of Dung’s abstract framework. Among the various ways of translating a SAT problem into a CSP one, we propose the most appropriate one in the argumentation context. We also provide encodings in case two other families of argumentation frameworks: the constrained version of Dung’s abstract framework and preference-based argumentation framework.     

Ants can solve constraint satisfaction problems

We describe a novel incomplete approach for solving constraint satisfaction problems (CSPs) based on the ant colony optimization (ACO) metaheuristic. The idea is to use artificial ants to keep track of promising areas of the search space by laying trails of pheromone. This pheromone information is used to guide the search, as a heuristic for choosing values to be assigned to variables. We first describe the basic ACO algorithm for solving CSPs and we show how it can be improved by combining it with local search techniques. Then, we introduce a preprocessing step, the goal of which is to favor a larger exploration of the search space at a lower cost, and we show that it allows ants to find better solutions faster. Finally, we evaluate our approach on random binary problems     

A multiagent evolutionary algorithm for constraint satisfaction problems.

With the intrinsic properties of constraint satisfaction problems (CSPs) in mind, we divide CSPs into two types, namely, permutation CSPs and nonpermutation CSPs. According to their characteristics, several behaviors are designed for agents by making use of the ability of agents to sense and act on the environment. These behaviors are controlled by means of evolution, so that the multiagent evolutionary algorithm for constraint satisfaction problems (MAEA-CSPs) results. To overcome the disadvantages of the general encoding methods, the minimum conflict encoding is also proposed. Theoretical analyzes show that MAEA-CSPs has a linear space complexity and converges to the global optimum. The first part of the experiments uses 250 benchmark binary CSPs and 79 graph coloring problems from the DIMACS challenge to test the performance of MAEA-CSPs for nonpermutation CSPs. MAEA-CSPs is compared with six well-defined algorithms and the effect of the parameters is analyzed systematically. The second part of the experiments uses a classical CSP, n-queen problems, and a more practical case, job-shop scheduling problems (JSPs), to test the performance of MAEA-CSPs for permutation CSPs. The scalability of MAEA-CSPs along n for n-queen problems is studied with great care. The results show that MAEA-CSPs achieves good performance when n increases from 10(4) to 10(7), and has a linear time complexity. Even for 10(7)-queen problems, MAEA-CSPs finds the solutions by only 150 seconds. For JSPs, 59 benchmark problems are used, and good performance is also obtained.