the proceedings contain 49 papers. the topics discussed include: constraint-directed search in computational finance and economics;constraints, graphs, algebra, logic, and complexity;testing expressibility is hard;app...
ISBN:
(纸本)364215395X
the proceedings contain 49 papers. the topics discussed include: constraint-directed search in computational finance and economics;constraints, graphs, algebra, logic, and complexity;testing expressibility is hard;applying constraintprogramming to identification and assignment of service professionals;computing the density of states of Boolean formulas;towards parallel non serial dynamic programming for solving hard weighted CSP;making adaptive an interval constraint propagation algorithm exploiting monotonicity;checking-up on branch-and-check;spatial, temporal, and hybrid decompositions for large-scale vehicle routing with time windows;propagating the bin packing constraint using linear programming;sweeping with continuous domains;a new hybrid tractable class of soft constraint problems;a propagator for maximum weight string alignment with arbitrary pairwise dependencies;and generating special-purpose stateless propagators for arbitrary constraints.
constraints shield solutions from a problem solver. However, in the hands of trained constraint problem solvers, the same constraints that create the problems in the first place can also guide problem solvers to solut...
详细信息
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.
We address the problem of designing constraint logic languages that usefully combine backward and forward chaining in a sound and complete way. Following the approach of constraint Logic programming, we define a class...
详细信息
ISBN:
(纸本)9781450329477
We address the problem of designing constraint logic languages that usefully combine backward and forward chaining in a sound and complete way. Following the approach of constraint Logic programming, we define a class of programming languages that generalize bothconstraint Logic and Concurrent constraintprogramming. Syntactically, this class corresponds to constraint Handling Rules with disjunctions, but differ operationally by featuring set-based semantics instead of multiset-based ones;i. e., conjunction and disjunction are idempotent. the assumption of program confluence is the crux on which boththe committed choice strategy and the logical completeness of the languages rely.
the aim of this paper is to model and mine patterns combining several local patterns (n-ary patterns). First, the user expresses his/her query under constraints involving n-ary patterns. Second, a constraint solver ge...
详细信息
ISBN:
(纸本)9783642153952
the aim of this paper is to model and mine patterns combining several local patterns (n-ary patterns). First, the user expresses his/her query under constraints involving n-ary patterns. Second, a constraint solver generates the correct and complete set of solutions. this approach enables to model in a flexible way sets of constraints combining several local patterns and it leads to discover patterns of higher level. Experiments show the feasibility and the interest of our approach.
the geost constraint has been proposed to model and solve discrete placement problems involving multi-dimensional boxes (packing in space and time). the filtering technique is based on a sweeping algorithm that requir...
详细信息
ISBN:
(纸本)9783642153952
the geost constraint has been proposed to model and solve discrete placement problems involving multi-dimensional boxes (packing in space and time). the filtering technique is based on a sweeping algorithm that requires the ability for each constraint to compute a forbidden box around a given fixed point and within a. surrounding area.. Several cases have been studied so far, including integer linear inequalities. Motivated by the placement of objects with curved shapes, this paper shows how to implement this service for continuous constraints with arbitrary mathematical expressions. the approach relies on symbolic processing and defines a new interval arithmetic.
We study the expressibility problem: given a finite constraint language F on a finite domain and another relation R, can F express R? We prove, by an explicit family of examples;that the standard witnesses to expressi...
详细信息
ISBN:
(纸本)9783642153952
We study the expressibility problem: given a finite constraint language F on a finite domain and another relation R, can F express R? We prove, by an explicit family of examples;that the standard witnesses to expressibility and inexpressibility (gadgets/formulas/conjunctive queries and polymorphisms respectively) may be required to be exponentially larger than the instances. We also show that the full expressibility problem is co-NEXPTIME-hard. Our proofs hinge on a novel interpretation of a tiling problem into the expressibility problem.
Research on constraint propagation has primarily focused on designing polynomial-time propagators sometimes at the cost of a weaker filtering. Interestingly, the evolution of constraintprogramming over sets have been...
详细信息
ISBN:
(纸本)9783642153952
Research on constraint propagation has primarily focused on designing polynomial-time propagators sometimes at the cost of a weaker filtering. Interestingly, the evolution of constraintprogramming over sets have been diametrically different. the domain representations are becoming increasingly expensive computationally and theoretical results appear to question the wisdom of these research directions. this paper explores this apparent contradiction by pursuing even more complexity in the domain representation and the filtering algorithms. It shows that;the product of the length-lex and subset-bound domains improves filtering and produces orders of magnitude improvements over existing approaches on standard benchmarks. Moreover, the paper proposes exponential-time algorithms for NP-hard intersection constraints and demonstrates that they bring significant performance improvements and speeds up constraint propagation considerably.
Feature modeling has been found very effective for modeling and managing variability in Software Product Lines. the nature of feature models invites, sometimes even requires, the use of global constraints. this paper ...
详细信息
ISBN:
(纸本)9783642153952
Feature modeling has been found very effective for modeling and managing variability in Software Product Lines. the nature of feature models invites, sometimes even requires, the use of global constraints. this paper lays the groundwork for the inclusion of global constraints in automated reasoning on feature models. We present a mapping from extended feature models to constraint logic programming over finite domains, and show that this mapping enables using global constraints on feature attributes, as well as features, for a variety of analysis operations on feature models. We also present performance test results and discuss the benefits of using global constraints.
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.
暂无评论