Compiling finite linear CSP into SAT

In this paper, we propose a new method to encode Constraint Satisfaction Problems (CSP) and Constraint Optimization Problems (COP) with integer linear constraints into Boolean Satisfiability Testing Problems (SAT). The encoding method (named order encoding) is basically the same as the one used to encode Job-Shop Scheduling Problems by Crawford and Baker. Comparison x ≤ a is encoded by a different Boolean variable for each integer variable x and integer value a. To evaluate the effectiveness of this approach, we applied the method to the Open-Shop Scheduling Problems (OSS). All 192 instances in three OSS benchmark sets are examined, and our program found and proved the optimal results for all instances including three previously undecided problems.     

Reformulation based MaxSAT robustness

The presence of uncertainty in the real world makes robustness a desirable property of solutions to constraint satisfaction problems (CSP). A solution is said to be robust if it can be easily repaired when unexpected events happen. This issue has already been addressed in the frameworks of Boolean satisfiability (SAT) and Constraint Programming (CP). Most existing works on robustness implement search algorithms to look for robust solutions instead of taking the declarative approach of reformulation, since reformulation tends to generate prohibitively large formulas, especially in the CP setting. In this paper we consider the unaddressed problem of robustness in weighted MaxSAT, by showing how robust solutions to weighted MaxSAT instances can be effectively obtained via reformulation into pseudo-Boolean formulae. Our encoding provides a reasonable balance between increase in size and performance, as shown by our experiments in the robust resource allocation framework. We also address the problem of flexible robustness, where some of the breakages may be left unrepaired if a totally robust solution does not exist. In a sense, since the use of SAT and MaxSAT encodings for solving CSP has been gaining wide acceptance in recent years, we provide an easy-to-implement new method for achieving robustness in combinatorial optimization problems.     

Multi-variable distributed backtracking with sessions

The Constraint Satisfaction Problem (CSP) formalism is used to represent many combinatorial decision problems instances simply and efficiently. However, many such problems cannot be solved on a single, centralized computer for various reasons (e.g., their excessive size or privacy). The Distributed CSP (DisCSP) extends the CSP model to allow such combinatorial decision problems to be modelled and handled. In this paper, we propose a complete DisCSP-solving algorithm, called Distributed Backtracking with Sessions (DBS), which can solve DisCSP so that each agent encapsulates a whole “complex” problem with many variables and constraints. We prove that the algorithm is sound and complete, and generates promising experimental results.     

A dynamic constraint satisfaction approach for configuring structural products under mass customization

Configuring structured products poses new challenges to the solving technologies for product configuration. This paper presents a novel and direct approach to encoding configuration models into the Dynamic Constraint Satisfaction Problems (DCSP). In the presented approach, components are encoded as DCSP variables while structural relationships are represented as DCSP activity constraints. Furthermore, the configuration constraints such as the requisition and exclusion constraints are treated as DCSP compatibility constraints, which allow a low-level component to join in the solving process only after its high-level component is selected in the configuration. The presented method allows a more compact encoding representation, compared to CSP and generative CSP. Experimental study shows that the presented DCSP encoding approach makes a significant improvement in the performance of product configuration.     

Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty

In classical Constraint Satisfaction Problems (CSPs) knowledge is embedded in a set of hard constraints, each one restricting the possible values of a set of variables. However constraints in real world problems are seldom hard, and CSP's are often idealizations that do not account for the preference among feasible solutions. Moreover some constraints may have priority over others. Lastly, constraints may involve uncertain parameters. This paper advocates the use of fuzzy sets and possibility theory as a realistic approach for the representation of these three aspects. Fuzzy constraints encompass both preference relations among possible instantiations and priorities among constraints. In a Fuzzy Constraint Satisfaction Problem (FCSP), a constraint is satisfied to a degree (rather than satisfied or not satisfied) and the acceptability of a potential solution becomes a gradual notion. Even if the FCSP is partially inconsistent, best instantiations are provided owing to the relaxation of some constraints. Fuzzy constraints are thus flexible. CSP notions of consistency and k-consistency can be extended to this framework and the classical algorithms used in CSP resolution (e.g., tree search and filtering) can be adapted without losing much of their efficiency. Most classical theoretical results remain applicable to FCSPs. In the paper, various types of constraints are modelled in the same framework. The handling of uncertain parameters is carried out in the same setting because possibility theory can account for both preference and uncertainty. The presence of uncertain parameters leads to ill-defined CSPs, where the set of constraints which defines the problem is not precisely known.     

Cost-based Filtering for Shorter Path Constraints

Many real world problems, e.g. personnel scheduling and transportation planning, can be modeled naturally as Constrained Shortest Path Problems (CSPPs), i.e., as Shortest Path Problems with additional constraints. A well studied problem in this class is the Resource Constrained Shortest Path Problem. Reduction techniques are vital ingredients of solvers for the CSPP, that is frequently NP-hard, depending on the nature of the additional constraints. Viewed as heuristics, these techniques have not been studied theoretically with respect to their efficiency, i.e., with respect to the relation of filtering power and running time. Using the concepts of Constraint Programming, we provide a theoretical study of cost-based filtering for shorter path constraints on acyclic, on undirected, and on directed graphs that do not contain negative cycles. We then show empirically how reasoning about path-substructures in combination with CP-based Lagrangian relaxation can help to improve significantly over previously developed problem-tailored filtering algorithms for the resource constrained shortest path problem and investigate the impact of required-edge detection, undirected versus directed filtering, and the choice of the algorithm optimizing the Lagrangian dual.     

Weight constraint programs with evaluable functions

In the current practice of Answer Set Programming (ASP), evaluable functions are represented as special kinds of relations. This often makes the resulting program unnecessarily large when instantiated over a large domain. The extra constraints needed to enforce the relation as a function also make the logic program less transparent. In this paper, we consider adding evaluable functions to answer set logic programs. The class of logic programs that we consider here is that of weight constraint programs, which are widely used in ASP. We propose an answer set semantics to these extended weight constraint programs and define loop completion to characterize the semantics. Computationally, we provide a translation from loop completions of these programs to instances of the Constraint Satisfaction Problem (CSP) and use the off-the-shelf CSP solvers to compute the answer sets of these programs. A main advantage of this approach is that global constraints implemented in such CSP solvers become available to ASP. The approach also provides a new encoding for CSP problems in the style of weight constraint programs. We have implemented a prototype system based on these results, and our experiments show that this prototype system competes well with the state-of-the-art ASP solvers. In addition, we illustrate the utilities of global constraints in the ASP context.     

A quantitative solution to Constraint Satisfaction Problem (CSP)

Constraint Satisfaction Problem (CSP) is an important problem in artificial intelligence and operations research. Many practical problems can be formulated as CSP, i.e., finding a consistent value assignment to variables subject to a set of constraints. In this paper, we give a quantitative approach to solve the CSPs which deals uniformly with binary constraints as well as high order,k-ary (k ≥ 2) constraints. In this quantitative approach, using variable transformation and constraint transformation, a CSP is transformed into a satisfiability (SAT) problem. The SAT problem is then solved within a continuous search space. We will evaluate the performance of this method based on randomly generated SAT problem instances and regularly generatedk-ary (k ≥ 2) CSP problem instances.     

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.     

Reasoning with Numeric and Symbolic Time Information

Representing and reasoning about time is fundamental in many applications of Artificial Intelligence as well as of other disciplines in computer science, such as scheduling, planning, computational linguistics, database design and molecular biology. The development of a domain-independent temporal reasoning system is then practically important. An important issue when designing such systems is the efficient handling of qualitative and metric time information. We have developed a temporal model, TemPro, based on the Allen interval algebra, to express and manage such information in terms of qualitative and quantitative temporal constraints. TemPro translates an application involving temporal information into a Constraint Satisfaction Problem (CSP). Constraint satisfaction techniques are then used to manage the different time information by solving the CSP. In order for the system to deal with real time applications or those applications where it is impossible or impractical to solve these problems completely, we have studied different methods capable of trading search time for solution quality when solving the temporal CSP. These methods are exact and approximation algorithms based respectively on constraint satisfaction techniques and local search. Experimental tests were performed on randomly generated temporal constraint problems as well as on scheduling problems in order to compare and evaluate the performance of the different methods we propose. The results demonstrate the efficiency of the MCRW approximation method to deal with under constrained and middle constrained problems while Tabu Search and SDRW are the methods of choice for over constrained problems.     

On the Hybrid Propositional Encodings of Planning

Recently, casting planning as propositional satisfiability (SAT) has been shown to be an efficient technique of plan synthesis. This article is a response to the recently proposed challenge of developing novel propositional encodings that are based on a combination of different types of plan refinements and characterizing the tradeoffs. We refer to these encodings as hybrid encodings. An investigation of these encodings is important, because this can give insights into what kinds of planning problems can be solved faster with hybrid encodings.
Encodings based on partial–order planning and state–space planning have been reported in previous research. We propose a new type of encoding called a unifying encoding that subsumes these two encodings. We also report on several other hybrid encodings. Next, we show how the satisfiability framework can be extended to incremental planning. State–space encoding is attractive because of its lower size and causal encoding is attractive because of its highest flexibility in reordering steps. We show that hybrid encodings have a higher size and a lower flexibility in step reordering and, thus, do not combine the best of these encodings. We discuss in detail several specific planning scenarios where hybrid encodings are likely to be superior to nonhybrid encodings.     

On the power of structural decompositions of graph-based representations of constraint problems

The Constraint Satisfaction Problem (CSP) is a central issue of research in Artificial Intelligence. Due to its intractability, many efforts have been made in order to identify tractable classes of CSP instances, and in fact deep and useful results have already been achieved. In particular, this paper focuses on structural decomposition methods, which are essentially meant to look for near-acyclicity properties of the graphs or hypergraphs that encode the structure of the constraints interactions. In general, constraint scopes comprise an arbitrary number of variables, and thus this structure may be naturally encoded via hypergraphs. However, in many practical applications, decomposition methods are applied over suitable graph representations of the (possibly non-binary) CSP instances at hand. Despite the great interest in such binary approaches, a formal analysis of their power, in terms of their ability of identifying islands of tractability, was missing in the literature.The aim of this paper is precisely to fill this gap, by studying the relationships among binary structural methods, and by providing a clear picture of the tractable fragments of CSP that can be specified with respect to each of these decomposition approaches, when they are applied to binary representations of non-binary CSP instances. In particular, various long-standing questions about primal, dual and incidence graph encodings are answered. The picture is then completed by comparing methods on binary encodings with methods specifically conceived for non-binary constraints.     

Approximating Satisfiable Satisfiability Problems

We study the approximability of the Maximum Satisfiability Problem (MAX SAT) and of the boolean k -ary Constraint Satisfaction Problem (MAX k CSP) restricted to satisfiable instances. For both problems we improve on the performance ratios of known algorithms for the unrestricted case. Our approximation for satisfiable MAX 3CSP instances is better than any possible approximation for the unrestricted version of the problem (unless P=NP). This result implies that the requirement of perfect completeness weakens the acceptance power of non-adaptive PCP verifiers that read 3 bits. We also present the first non-trivial results about PCP classes defined in terms of free bits that collapse to P. Received August 1997; revised February 1999.     

Optimization-Oriented Global Constraints

In this paper, we propose a way of exploiting Operations Research techniques within global constraints for cost-based domain filtering. In Constraint Programming, constraint propagation is aimed at removing from variable domains combinations of values which are proven infeasible. Pruning derives from feasibility reasoning. When coping with optimization problems, pruning can be performed also on the basis of costs, i.e., optimality reasoning. Cost-based filtering removes combination of values which are proven sub-optimal. For this purpose, we encapsulate in global constraints optimization components representing suitable relaxations of the constraint itself. These components embed efficient Operations Research algorithms computing the optimal solution of the relaxed problem and a gradient function representing the estimated cost of each variable-value assignment. We exploit these pieces of information for pruning and for guiding the search. We have applied these techniques to a couple of ILOG Solver global constraints (a constraint of difference and a path constraint) and tested the approach on a variety of combinatorial optimization problems such as Timetabling, Travelling Salesman Problems and Scheduling Problems with sequence dependent setup times. Comparisons with pure Constraint Programming approaches and related literature clearly show the benefits of the proposed approach.     

DOC-BRelax: A new multi-agent system to solve Distributed Constraint Optimization Problems

Many problems in multi-agent systems can be described as Distributed Constraint Satisfaction Problems (DCSPs), where the goal is to find a set of assignments to variables that satisfies all constraints among agents. However, when real-life application problems are formalized as DCSPs, they are often over-constrained and have no solution that satisfies all constraints. Moreover, the globalization of the economy and democratization of the Internet, boosted by the huge growth in information and communication technologies, have largely contributed to the expansion of numerous distributed architectures. Thus this paper provides a new distributed management and decision support system suitable to these interdependencies and these complex environments. We present a Distributed Optimization under Constraints Basic Relax (DOC-BRelax) as a new framework for dealing with over-constrained situations. We also present a version of this framework called DOC-MaxRelax and a new algorithm for solving Distributed Maximal Constraint Satisfaction Problems (DMCSPs).     

Assessing Effects of Task and Data Distribution on the Effectiveness of Visual Encodings

In addition to the choice of visual encodings, the effectiveness of a data visualization may vary with the analytical task being performed and the distribution of data values. To better assess these effects and create refined rankings of visual encodings, we conduct an experiment measuring subject performance across task types (e.g., comparing individual versus aggregate values) and data distributions (e.g., with varied cardinalities and entropies). We compare performance across 12 encoding specifications of trivariate data involving 1 categorical and 2 quantitative fields, including the use of x, y, color, size, and spatial subdivision (i.e., faceting). Our results extend existing models of encoding effectiveness and suggest improved approaches for automated design. For example, we find that colored scatterplots (with positionally‐coded quantities and color‐coded categories) perform well for comparing individual points, but perform poorly for summary tasks as the number of categories increases.     

Portfolio approaches for constraint optimization problems

Within the Constraint Satisfaction Problems (CSP) context, a methodology that has proven to be particularly performant consists of using a portfolio of different constraint solvers. Nevertheless, comparatively few studies and investigations have been done in the world of Constraint Optimization Problems (COP). In this work, we provide a generalization to COP as well as an empirical evaluation of different state of the art existing CSP portfolio approaches properly adapted to deal with COP. The results obtained by measuring several evaluation metrics confirm the effectiveness of portfolios even in the optimization field, and could give rise to some interesting future research.     

A unified framework for consistency check

Constraint Satisfaction Problem (CSP) involves finding values for variables to satisfy a set of constraints. Consistency check is the key technique in solving this class of problems. Past research has developed many algorithms for such a purpose, e.g., node consistency, are consistency, generalized node and arc consistency, specific methods for checking specific constraints, etc. In this article, an attempt is made to unify these algorithms into a common framework. This framework consists of two parts. the first part is a generic consistency check algorithm, which allows and encourages each individual constraint to be checked by its specific consistency methods. Such an approach provides a direct way of practical implementation of the CSP model for real problem-solving. the second part is a general schema for describing the handling of each type of constraint. the schema characterizes various issues of constraint handling in constraint satisfaction, and provides a common language for expressing, discussing, and exchanging constraint handling techniques. © 1995 John Wiley & Sons, Inc.     

Applying constraint satisfaction approach to solve product configuration problems with cardinality-based configuration rules

In this paper, the product configuration problems that are characterized by cardinality-based configuration rules are dealt with. Novel configuration rules including FI and EI rules are presented to clarify the semantics of inclusion rules when cardinalities and hierarchies of products are encountered. Then, a configuration graph is proposed to visualize structural rules and configuration rules in product configuration problem. An encoding approach is elaborated to transform the configuration graph as a CSP (Constraint Satisfaction Problem). As a consequence, existing CSP solver, i.e. JCL (Java Constraint Library), is employed to implement the configuration system for product configuration problem with cardinality-related configuration rules. A case study of a bus configuration is used throughout this paper to illustrate the effectiveness of the presented approach.