this paper considers the automatic generation of architectural tests (ATGP), a fundamental problem in processor validation. ATGPs are complex conditional constraint satisfaction problems which typically feature both h...
详细信息
ISBN:
(纸本)9783642042430
this paper considers the automatic generation of architectural tests (ATGP), a fundamental problem in processor validation. ATGPs are complex conditional constraint satisfaction problems which typically feature both hard and soft constraints and very large domains (e.g., all memory addresses). Moreover, the goal is to generate a. large number of diverse Solutions under tight runtime constraints. To improve solution diversity, this paper proposes a, novel approach to ATGPs by modeling them as MAXDIVERSEkSET problems and solving them withconstraint-based local search over conditional variables. the paper presents the semantics and implementation of Conditional variables in this context and demonstrates the computational benefits of the approach.
Many production planning problems call for the minimization of stocking/storage costs. this paper introduces a new global constraint StockingCost ([X-1,..., X-n], [d(1),..., d(n)], H, c) that holds when each item X-i ...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Many production planning problems call for the minimization of stocking/storage costs. this paper introduces a new global constraint StockingCost ([X-1,..., X-n], [d(1),..., d(n)], H, c) that holds when each item X-i is produced on or before its due date d(i), the capacity c of the machine is respected, and H is an upper bound on the stocking cost. We propose a linear time algorithm to achieve bound consistency on the StockingCost constraint. On a version of the Discrete Lot Sizing Problem, we demonstrate experimentally the pruning and time efficiency of our algorithm compared to other state-of-the-art approaches.
Efficient constraint propagation is crucial to any constraint solver. We show that watched literals, already a great success in the satisfiability community, can be used to provide highly efficient implementations of ...
详细信息
ISBN:
(纸本)3540462678
Efficient constraint propagation is crucial to any constraint solver. We show that watched literals, already a great success in the satisfiability community, can be used to provide highly efficient implementations of constraint propagators. We describe three important aspects of watched literals as we apply them to constraints, and how they are implemented in the MINION constraint solver. We show three successful applications of to constraint propagators: the sum of Boolean variables;GAC for the 'element' constraint;and GAC for the 'table' constraint.
In a previous work, we introduced a filtering for the Bin-Packing constraint based on a cardinality reasoning for each bin combined with a global cardinality constraint. We improve this filtering with an algorithm pro...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
In a previous work, we introduced a filtering for the Bin-Packing constraint based on a cardinality reasoning for each bin combined with a global cardinality constraint. We improve this filtering with an algorithm providing tighter bounds on the cardinality variables. We experiment it on the Balanced Academic Curriculum Problems demonstrating the benefits of the cardinality reasoning for such bin-packing problems.
In this paper, we study the problem of differential harvest in precision viticulture. Some recent prototypes of grape harvesting machines are supplied with two hoppers and are able to sort two types of grape quality. ...
详细信息
ISBN:
(纸本)9783319232195;9783319232188
In this paper, we study the problem of differential harvest in precision viticulture. Some recent prototypes of grape harvesting machines are supplied with two hoppers and are able to sort two types of grape quality. Given estimated qualities and quantities on the different areas of the vineyard, the problem is to optimize the routing of the grape harvester under several constraints. the main constraints are the amount of first quality grapes to harvest and the capacity of the hoppers. We model the differential harvest problem as a constraint optimization problem. We present preliminary results on real data. We also compare our constraint model to an integer linear programming approach and discuss expressiveness and efficiency.
this paper presents high-level abstractions for nondeterministic search in C++ which provide the counterpart to advanced features found in recent constraint languages. the abstractions have several benefits: they expl...
详细信息
ISBN:
(纸本)3540462678
this paper presents high-level abstractions for nondeterministic search in C++ which provide the counterpart to advanced features found in recent constraint languages. the abstractions have several benefits: they explicitly highlight the nondeterministic nature of the code, provide a natural iterative style, simplify debugging, and are efficiently implementable using macros and continuations. their efficiency is demonstrated by comparing their performance withthe C++ library GECODE, both for programming search procedures and search engines.
Solutions to valid Quantified constraint Satisfaction Problems (QCSPs) are called winning strategies and represent possible ways in which the existential player can react to the moves of the universal one to "win...
详细信息
ISBN:
(纸本)9783540859574
Solutions to valid Quantified constraint Satisfaction Problems (QCSPs) are called winning strategies and represent possible ways in which the existential player can react to the moves of the universal one to "win the game". However, different winning strategies are not necessarily equivalent: some may be preferred to others. We define Quantified constraint Optimization Problems (QCOP) as a framework which allows both to formally express preferences over QCSP strategies, and to solve the related optimization problem. We present examples and some experimental results. We also discuss flow this framework relates to other formalisms for hierarchical decision modeling known as von Stackelberg games and bilevel (and multilevel) programming.
Since the origins of the constraint satisfaction paradigm, its restriction to binary constraints has concentrated a significant part of the work. this is understandable because new ideas/techniques are usually much si...
详细信息
ISBN:
(纸本)3540666265
Since the origins of the constraint satisfaction paradigm, its restriction to binary constraints has concentrated a significant part of the work. this is understandable because new ideas/techniques are usually much simpler to present/elaborate by first restricting them to the binary case. (See for example the are consistency algorithms, such as AC-3 or AC-4, which have been presented first in their binary version [10, 12], before being extended to non-binary constraints [11, 13].) But this inclination has highly increased in the early nineties. Authors indeed justified this restriction by the fact that any non-binary constraint network can polyniomally be converted into an equivalent binary one [6,8,5,19]. And, in most cases, they never extended their work to non-binary constraints.
constraints have played a central role in cp because they capture key substructures of a problem and efficiently exploit them to boost inference. this paper intends to do the same thing for search, proposing constrain...
详细信息
constraints have played a central role in cp because they capture key substructures of a problem and efficiently exploit them to boost inference. this paper intends to do the same thing for search, proposing constraint-centered heuristics which guide the exploration of the search space toward areas that are likely to contain a high number of solutions. We first propose new search heuristics based on solution counting information at the level of individual constraints. We then describe efficient algorithms to evaluate the number of solutions of two important families of constraints: occurrence counting constraints, such as all different, and sequencing constraints, such as regular. In both cases we take advantage of existing filtering algorithms to speed up the evaluation. Experimental results on benchmark problems show the effectiveness of our approach.
Conflict-Driven Clause-Learning (CDCL) SAT solvers can automatically solve very large real-world problems. To go beyond, and in particular in order to solve and optimize problems involving linear arithmetic constraint...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Conflict-Driven Clause-Learning (CDCL) SAT solvers can automatically solve very large real-world problems. To go beyond, and in particular in order to solve and optimize problems involving linear arithmetic constraints, here we introduce IntSat, a generalization of CDCL to Integer Linear programming (ILP). Our simple 1400-line C++ prototype IntSat implementation already shows some competitiveness with commercial solvers such as CPLEX or Gurobi. Here we describe this new IntSat ILP solving method, show how it can be implemented efficiently, and discuss a large list of possible enhancements and extensions.
暂无评论