the recent series 5 of the Answer Set programming (ASP) system clingo provides generic means to enhance basic ASP withtheory reasoning capabilities. We instantiate this framework with different forms of linear constr...
详细信息
the recent series 5 of the Answer Set programming (ASP) system clingo provides generic means to enhance basic ASP withtheory reasoning capabilities. We instantiate this framework with different forms of linear constraints and elaborate upon its formal properties. Given this, we discuss the respective implementations, and present techniques for using these constraints in a reactive context. More precisely, we introduce extensions to clingo with difference and linear constraints over integers and reals, respectively, and realize them in complementary ways. Finally, we empirically evaluate the resulting clingo derivatives clingo[dl] and clingo[lp] on common language fragments and contrast them to related ASP systems.
Linear integer constraints are one of the most important constraints in combinatorial problems since they are commonly found in many practical applications. Typically, encoding linear constraints to SAT performs poorl...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Linear integer constraints are one of the most important constraints in combinatorial problems since they are commonly found in many practical applications. Typically, encoding linear constraints to SAT performs poorly in problems withthese constraints in comparison to constraintprogramming (cp) or mixed integer programming (MIP) solvers. But some problems contain a mix of combinatoric constraints and linear constraints, where encoding to SAT is highly effective. In this paper we define new approaches to encoding linear constraints into SAT, by extending encoding methods for pseudo-Boolean constraints. Experimental results show that these methods are not only better than the state-of-the-art SAT encodings, but also improve on MIP and cp solvers on appropriate problems. Combining the new encoding with lazy decomposition, which during runtime only encodes constraints that are important to the solving process that occurs, gives a robust approach to many highly combinatorial problems involving linear constraints.
the generalization of the constraint satisfaction problem with universal quantifiers is a challenging PSPACE-complete problem, which is interesting theoretically and also relevant to solving other PSPACE problems aris...
详细信息
ISBN:
(纸本)3540292381
the generalization of the constraint satisfaction problem with universal quantifiers is a challenging PSPACE-complete problem, which is interesting theoretically and also relevant to solving other PSPACE problems arising in AI, such as reasoning with uncertainty, and multiplayer games. I define two new levels of consistency for QCSP, and give an algorithm to enforce consistency for one of these definitions. the algorithm is embedded in backtracking search, and tested empirically. the aims of this work are to increase the facilities available for modelling and to increase the power of constraint propagation for QCSPs. the work is motivated by examples from adversarial games.
the state-of-the-art global constraint for bin packing is due to Shaw. We compare two linear continuous relaxations of the bin packing problem, based on the DP-flow and Arc-flow models, withthe filtering of the bin p...
详细信息
ISBN:
(纸本)9783642153952
the state-of-the-art global constraint for bin packing is due to Shaw. We compare two linear continuous relaxations of the bin packing problem, based on the DP-flow and Arc-flow models, withthe filtering of the bin packing constraint. Our experiments show that we often obtain significant improvements in runtime. the DP-flow model is a novel formulation of the problem.
LODE is a logic-based web tool for Italian deaf children. It aims at stimulating global reasoning on e-stories written in a verbal language. Presently, we are focusing on temporal reasoning, that is, LODE stimulates c...
详细信息
ISBN:
(纸本)9783540749691
LODE is a logic-based web tool for Italian deaf children. It aims at stimulating global reasoning on e-stories written in a verbal language. Presently, we are focusing on temporal reasoning, that is, LODE stimulates children to reason with global temporal relations between events possibly distant in a story. this is done through apt exercises and withthe support of a constraintprogramming system. Children can also reinvent the e-story by rearranging its events along a new temporal order;it is the task of the constraint system to determine the consistency of the temporally reorganised story and provide children with feedback. To the best of our knowledge, LODE is the first e-learning tool for Italian deaf children that aims at stimulating global reasoning on whole e-stories.
Engineering conceptual design can be defined as that phase of the product development process during which the designer takes a specification for a product to be designed and generates many broad solutions for it. It ...
详细信息
ISBN:
(纸本)3540202021
Engineering conceptual design can be defined as that phase of the product development process during which the designer takes a specification for a product to be designed and generates many broad solutions for it. It is well recognized that few computational tools exist that are capable of supporting the designer work through the conceptual phase of design. However, significant recent developments have been made in solid modeling and 3D computer-aided design. the use of such tools has become a critical element in the more sophisticated product development processes to be found in modem industry. this paper presents a prototype constraint-based computer-aided design (CAD) technology that can be used to support designers working in the early stages of design. the technology has been developed as an add-in application for Autodesk Inventor, a 3D solid-modeling environment. the add-in has, at its core, a constraint filtering system based on generalised arc-consistency processing and backtrack search. We present our current prototype and a detailed demonstration of its functionality. Finally, we describe our current work on a number of additional features for the next prototype, which will be deployed in an industrial context.
this work presents a hybrid approach to solve the maximum stable set problem, using constraint and semidefinite programming. the approach consists of two steps: subproblem generation and subproblem solution. First we ...
详细信息
Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraintprogramming approach. In this paper we present an efficient algorithm f...
详细信息
Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraintprogramming approach. In this paper we present an efficient algorithm for bounds consistency propagation of the generalized cardinality constraint (gcc). Using a variety of benchmark and random problems, we show that on some problems our bounds consistency algorithm can dramatically outperform existing state-of-the-art commercial implementations of constraint propagators for the gcc. We also present a new algorithm for domain consistency propagation of the gcc which improves on the worst-case performance of the best previous algorithm for problems that occur often in applications.
the steel mill slab design problem from the CSPLIB is real-life problem from the steel industry. Finding optimal solutions to this problem is difficult. Existing constraintprogramming approaches can solve problems up...
详细信息
ISBN:
(纸本)9783540749691
the steel mill slab design problem from the CSPLIB is real-life problem from the steel industry. Finding optimal solutions to this problem is difficult. Existing constraintprogramming approaches can solve problems up to 30 orders. We propose a strong constraintprogramming model based on logical and global constraints. By designing a specific strategy for variable and value selection, we are able to solve instances having more than 70 orders to optimality using depth-first search. Injecting this strategy into a large neighborhood search, we are able to solve the real-life instance of the CSPLIB having 111 orders in just 3 seconds.
Fixed-width MDDs were introduced recently as a more refined alternative for the domain store to represent partial solutions to CSPs. In this work, we present a systematic approach to MDD-based constraintprogramming. ...
详细信息
ISBN:
(纸本)9783642153952
Fixed-width MDDs were introduced recently as a more refined alternative for the domain store to represent partial solutions to CSPs. In this work, we present a systematic approach to MDD-based constraintprogramming. First, we introduce a generic scheme for constraint propagation in MDDs. We show that all previously known propagation algorithms for MDDs can be expressed using this scheme. Moreover, we use the scheme to produce algorithms for a number of other constraints, including Among, Element, and unary resource constraints. Finally, we discuss an implementation of our MDD-based cp solver, and provide experimental evidence of the benefits of MDD-based constraintprogramming.
暂无评论