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.
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.
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.
this paper introduces a new velocity tuning approach for autonomous vehicles based on constraintprogramming (CP) over continuous domains. We use CP to compute a safe approximation of configurations where collisions w...
详细信息
ISBN:
(纸本)9783642153952
this paper introduces a new velocity tuning approach for autonomous vehicles based on constraintprogramming (CP) over continuous domains. We use CP to compute a safe approximation of configurations where collisions with obstacles may occur or technological limits may be violated. the use of CP leads to a flexible approach, facilitating the incorporation of new characteristics, e.g., constraints modeling the influence of currents. We illustrate these capabilities offered by CP in the context of UAV missions. Experimental results obtained on actual wind charts are provided.
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.
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.
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.
A new interval constraint propagation algorithm;called MOnotonic Hall Consistency (Mohc), has recently been proposed. Mohc exploits monotonicity of functions to better filter variable domains. Embedded in an interval-...
详细信息
ISBN:
(纸本)9783642153952
A new interval constraint propagation algorithm;called MOnotonic Hall Consistency (Mohc), has recently been proposed. Mohc exploits monotonicity of functions to better filter variable domains. Embedded in an interval-based solver, Mohc shows very high performance for solving systems of numerical constraints (equations or inequalities) over the reals. However, the main drawback is that its revise procedure depends on two user-defined parameters. this paper reports a rigourous empirical study resulting in a variant of Mohc that avoids a manual tuning of the parameters. In particular, we propose a policy to adjust in an auto-adaptive way;during the search, the parameter sensitive to the monotonicity of the revised function.
暂无评论