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.
Traditionally, local consistency is defined as a relaxation of consistency which can be checked in polynomial time. It is accompanied by a corresponding "filtering" or "enforcing" algorithm that co...
详细信息
Local Consistency has proven to be an important notion in the study of constraint satisfaction problems. We give an algebraic condition that characterizes all the constraint types for which generalized are-consistency...
详细信息
ISBN:
(纸本)3540666265
Local Consistency has proven to be an important notion in the study of constraint satisfaction problems. We give an algebraic condition that characterizes all the constraint types for which generalized are-consistency is sufficient to ensure the existence of a solution. We give some examples to illustrate the application of this result.
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.
this paper investigates the relations among different partial consistencies which have been proposed for pruning the domains of the variables in constraint systems over the real numbers. We establish several propertie...
详细信息
ISBN:
(纸本)3540652248
this paper investigates the relations among different partial consistencies which have been proposed for pruning the domains of the variables in constraint systems over the real numbers. We establish several properties of the filtering achieved by the algorithms based upon these partial consistencies. Especially, we prove that : 1) 2B-Consistency (or Hull consistency) algorithms actually yield a weaker pruning than Box-consistency;2) 3B-Consistency algorithms perform a stronger pruning than Box-consistency. this paper also provides an analysis of boththe capabilities and the inherent limits of the filtering algorithms which achieve these partial consistencies.
the protein structure prediction problem is one of the most (if not the most) important problem in computational biology. this problem consists of finding the conformation of a protein (i.e., a sequence of amino-acids...
详细信息
ISBN:
(纸本)3540652248
the protein structure prediction problem is one of the most (if not the most) important problem in computational biology. this problem consists of finding the conformation of a protein (i.e., a sequence of amino-acids) with minimal energy. Because of the complexity of this problem, simplified models like Dill's HP-lattice model [12] have become a major tool for investigating general properties of protein folding. Even for this simplified model, the structure prediction problem has been shown to be NP-complete [3, 5]. We describe a constraint formulation of the HP-model structure prediction problem, present the basic constraints and search strategy. We then introduce a novel, general technique for excluding geometrical symmetries in constraintprogramming. To our knowledge, this is the first general and declarative technique for excluding symmetries in constraintprogrammingthat can be added to an existing implementation. Finally, we describe a new lower bound on the energy of an HP-protein. Both techniques yield an efficient pruning of the search tree.
暂无评论