"The Crossword puzzle (CP) is a simple problem to illustrate the formalization process of a problem into a CSP. The problem is to place words of a dictionary in a given structure satisfying certain constraints. The variables are the rows and columns in the crossword, and their values are the words in a dictionary."
– Marc Torrens. An Application using the JCL: The Air Travel Planning System. Diploma Thesis, 1997, Chapter 1, Section 1.2.1.
A computer-aided process planning system should ideally generate and optimize process plans to ensure the application of good manufacturing practices and maintain the consistency of the desired functional specifications of a part during its production processes. Crucial processes, such as selecting machining resources, determining set-up plans and sequencing operations of a part should be considered simultaneously to achieve global optimal solutions. In this paper, these processes are integrated and modelled as a constraint-based optimization problem, and a tabu search-based approach is proposed to solve it effectively. In the optimization model, costs of the utilized machines and cutting tools, machine changes, tool changes, set-ups and departure from good manufacturing practices (penalty function) are the optimization evaluation criteria. Precedence constraints from the geometric and manufacturing interactions between features and their related operations in a part are defined and classified according to their effects on the plan feasibility and processing quality.
Answer Set Planning refers to the use of Answer Set Programming (ASP) to compute plans, i.e., solutions to planning problems, that transform a given state of the world to another state. The development of efficient and scalable answer set solvers has provided a significant boost to the development of ASP-based planning systems. This paper surveys the progress made during the last two and a half decades in the area of answer set planning, from its foundations to its use in challenging planning domains. The survey explores the advantages and disadvantages of answer set planning. It also discusses typical applications of answer set planning and presents a set of challenges for future research.
Ganian, Robert (Algorithms and Complexity Group, TU Wien) | Kim, Eun Jung (LAMSADE/CNRS, Université Paris-Dauphin) | Slivovsky, Friedrich (TU Wien) | Szeider, Stefan (Algorithms and Complexity Group, TU Wien)
Weighted Counting for Constraint Satisfaction with Default Values (#CSPD) is a powerful special case of the sum-of-products problem that admits succinct encodings of #CSP, #SAT, and inference in probabilistic graphical models. We investigate #CSPD under the fundamental parameter of incidence treewidth (i.e., the treewidth of the incidence graph of the constraint hypergraph). We show that if the incidence treewidth is bounded, #CSPD can be solved in polynomial time. More specifically, we show that the problem is fixed-parameter tractable for the combined parameter incidence treewidth, domain size, and support size (the maximum number of non-default tuples in a constraint). This generalizes known results on the fixed-parameter tractability of #CSPD under the combined parameter primal treewidth and domain size. We further prove that the problem is not fixed-parameter tractable if any of the three components is dropped from the parameterization.
In this paper, we present an efficient algorithm for verifying path-consistency on a binary constraint network. The complexities of our algorithm beat the previous conjectures on the lower bounds for verifying path-consistency. We therefore defeat the proofs for several published results that incorrectly rely on these conjectures. Our algorithm is motivated by the idea of reformulating path-consistency verification as fast matrix multiplication. Further, for a computational model that counts arithmetic operations (rather than bit operations), a clever use of the properties of prime numbers allows us to design an even faster variant of the algorithm. Based on our algorithm, we hope to inspire a new class of techniques for verifying and even establishing varying levels of local-consistency on given constraint networks.
Unlike mathematical programming and SAT solving, ConstraintProgramming (CP) is based on the idea that both modeling and solving of combinatorial optimization problems can be based on conjunctions of loosely coupled, recurring, combinatorial sub-problems (aka "global constraints"). This rich representational approach means that, for better or for worse, pretty much anything can be expressed as a global constraint. Much of CP's success, however, has come from exploiting only one aspect of the rich constraint definition: global constraint propagation. In this talk, I will investigate how work in CP, SAT, AI planning, and mathematical programming can be understood as more seriously pursuing the implications of a rich constraint definition and how the interplay between local and global information can lead to dynamic problem reformulations and a flexible hybrid solver architecture.
A constraint satisfaction problem has compactness if any infinite set of constraints is satisfiable whenever all its finite subsets are satisfiable. We prove a sufficient condition for compactness, which holds for a range of problems including those based on the well-known Interval Algebra (IA) and RCC8. Furthermore, we show that compactness leads to a useful necessary and sufficient condition for the recently introduced patchwork property, namely that patchwork holds exactly when every satisfiable finite network (i.e., set of constraints) has a canonical solution, that is, a solution that can be extended to a solution for any satisfiable finite extension of the network. Applying these general theorems to qualitative reasoning, we obtain important new results as well as significant strengthenings of previous results regarding IA, RCC8, and their fragments and extensions. In particular, we show that all the maximal tractable fragments of IA and RCC8 (containing the base relations) have patchwork and canonical solutions as long as networks are algebraically closed.
The size of these networks is quadratic in the number of variables, which has severely limited the real-world application of QSR. In this paper, we propose another representation of spatial scenarios, in which each variable is associated with one or more rectangles. Instead of requiring these rectangles to define a solution of the corresponding constraint network, we construct sequences of rectangles that define partial solutions to progressively weaker constraint networks. We present experimental results that illustrate the effectiveness of this strategy.
RCC8 is a constraint language that serves for qualitative spatial representation and reasoning by encoding the topological relations between spatial entities. We focus on efficiently characterizing non-redundant constraints in large real world RCC8 networks and obtaining their prime networks. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N. A prime network of N is a network which contains no redundant constraints, but has the same solution set as N. We make use of a particular partial consistency, namely, G-path consistency, and obtain new complexity results for various cases of RCC8 networks, while we also show that given a maximal distributive subclass for RCC8 and a network N defined on that subclass, the prunning capacity of G-path consistency and path consistency is identical on the common edges of G and the complete graph of N, when G is a triangulation of the constraint graph of N. Finally, we devise an algorithm based on G-path consistency to compute the unique prime network of a RCC8 network, and show that it significantly progresses the state-of-the-art for practical reasoning with real RCC8 networks scaling up to millions of nodes.
Formal Concept Analysis (FCA) is a prominent field of applied mathematics using object-attribute relationships to define formal concepts -- groups of objects with common attributes -- which can be ordered into conceptual hierarchies, so-called concept lattices. We consider the problem of satisfiability of membership constraints, i.e., to determine if a formal concept exists whose object and attribute set include certain elements and exclude others. We analyze the computational complexity of this problem in general and for restricted forms of membership constraints. We perform the same analysis for generalizations of FCA to incidence structures of arity three (objects, attributes and conditions) and higher. We present a generic answer set programming (ASP) encoding of the membership constraint satisfaction problem, which allows for deploying available highly optimized ASP tools for its solution. Finally, we discuss the importance of membership constraints in the context of navigational approaches to data analysis.
In this paper, we propose a qualitative formalism for representing and reasoning about time at different scales. It extends the algebra of Euzenat and overcomes its major limitations, allowing one to reason about relations between points and intervals. Our approach is more expressive than the other algebras of temporal relations: for instance, some relations are more relaxed than those in Allen's algebra, while others are stricter. In particular, it enables the modeling of imprecise, gradual, or intuitive relations, such as "just before" or "almost meet." In addition, we give several results about how a relation changes when considered at different granularities. Finally, we provide an algorithm to compute the algebraic closure of a temporal constraint network in our formalism, which can be used to check its consistency.