In many situations, a set of hard constraints encodes the feasible configurations of some system or product over which users have preferences. We consider the problem of computing a best feasible solution when the use...
详细信息
ISBN:
(纸本)3540202021
In many situations, a set of hard constraints encodes the feasible configurations of some system or product over which users have preferences. We consider the problem of computing a best feasible solution when the user's utilities are partially known. Assuming bounds on utilities, efficient mixed integer linear programs are devised to compute the solution with minimax regret while exploiting generalized additive structure in a user's utility function.
Counting the number of solutions to CSP instances has vast applications in several areas ranging from statistical physics to artificial intelligence. We provide a new algorithm for counting the number of solutions to ...
详细信息
ISBN:
(纸本)3540202021
Counting the number of solutions to CSP instances has vast applications in several areas ranging from statistical physics to artificial intelligence. We provide a new algorithm for counting the number of solutions to binary CSP s which has a time complexity ranging from O ((d/4 . alpha(4))(n)) to O((alpha + alpha(5) + [d/4 - 1] . alpha(4))(n)) (where alpha approximate to 1.2561) depending on the domain size d greater than or equal to 3. this is substantially faster than previous algorithms, especially for small d. We also provide an algorithm for counting k-colourings in graphs and its running time ranges from O ([log(2) k](n)) to O ([log(2) k + 1](n)) depending on k greater than or equal to 4. Previously, only an O(1.8171(n)) time algorithm for counting 3-colourings were known, and we improve this upper bound to O(1.7879(n)).
constraintprogramming is a technology which is now widely used to solve combinatorial problems in industrial applications. However, using it requires considerable knowledge and expertise in the field of constraint re...
详细信息
In this paper we propose a semantically well-founded combination of the constraint solvers used in the constraintprogramming languages CLP(SET) and CLP(FD). this work demonstrates that it is possible to provide effic...
详细信息
ISBN:
(纸本)9781581137057
In this paper we propose a semantically well-founded combination of the constraint solvers used in the constraintprogramming languages CLP(SET) and CLP(FD). this work demonstrates that it is possible to provide efficient executions (through CLP(FD) solvers) while maintaining the expressive power and flexibility of the CLP(SET) language. We develop a combined constraint solver and we show how static analysis can help in organizing the distribution of constraints to the two constraint solvers.
An unsatisfiable set of constraints is minimal if all its (strict) subsets aresatisfiable.A number of forms of error diagnosis, including circuit error diagnosis and type error diagnosis, require finding all minimal u...
详细信息
ISBN:
(纸本)9781581137057
An unsatisfiable set of constraints is minimal if all its (strict) subsets aresatisfiable.A number of forms of error diagnosis, including circuit error diagnosis and type error diagnosis, require finding all minimal unsatisfiable subsets of a given set of constraints (representing an error), in order to generate the best explanation of the error. In this paper we give algorithms for efficiently determining all minimal unsatisfiable subsets for any kind of constraints. We show how taking into account notions of independence of constraints and using incremental constraint solvers can significantly improve the calculation of these subsets.
the proceedings contain 41 papers. the special focus in this conference is on principles and practice of constraintprogramming. the topics include: the rough guide to constraint propagation;non-binary constraints;the...
ISBN:
(纸本)3540666265
the proceedings contain 41 papers. the special focus in this conference is on principles and practice of constraintprogramming. the topics include: the rough guide to constraint propagation;non-binary constraints;the theory of discrete lagrange multipliers for nonlinear discrete optimization;operational equivalence of CHR programs and constraints;automatic generation of constraint propagation algorithms for small finite domains;excluding symmetries in constraint based search;onforward checking for non-binary constraint satisfaction;enforcing arc consistency on global constraints by solving subCSPs on the fly;exploiting bipartiteness to identify yet another tractable subclass of CSP;towards a complete classification of tractability in point algebras for nonlinear time;a meta-heuristic factory for vehicle routing problems;closure functions and width 1 problems;cost-based domain filtering;resource allocation in networks using abstraction and constraint satisfaction techniques;optimal distributed arc-consistency;multistep filtering operators for ordinary differential equations and a framework for constraintprogramming based column generation.
Test data generation is the most labor-intensive work for software testing. As a result, automatic test case generation is a way forward. It is typical to denote the conditions of searching the test input that can cau...
详细信息
作者：
Bennaceur, HachemiLi, Chu MinLIPN
Institut Galilée Université Paris 13 Av J B Clément Villetaneuse93240 France LaRIA
Université de Picardie Jules Verne 5 Rue du Moulin Neuf Amiens80000 France
Using the literal encoding of the satisfiability problem (SAT)as a binary constraint satisfaction problem (CSP), we relate the path consistency concept and the row convexity of CSPs withthe inference rules in the pro...
详细信息
this paper presents a new cumulatives constraint, which generalizes the original cumulative constraint in different ways. the two most important aspects consist in permitting multiple cumulative resources as well as n...
详细信息
Symmetries in constraint satisfaction problems (CSPs) areone of the difficulties that practitioners have to deal with. We present in this paper a new method based on the symmetries of decisions taken from the root of ...
详细信息
暂无评论