DragonBreath An Optimization Engine based on Constraint Programming and Local Search |
[HOMEPAGE] -> [Documentation] -> [Concepts] -> [Costs]
Costs are a central component of the solver concept. They determine what constitutes a consistent solution and which solutions are preferred.
Every constraint type provides functions to calculate its own costs as a measure to indicate how much the constraint is inconsistent. These costs must
For example, a simple Sum constraint with two variables a and b to be added and an s variable for the sum could specify its costs as Sumcosts = round(abs(a + b - s)). If the current variables' assignments are a = 5, b = -4 and s = 4.5, the Sum constraint's current costs would be round(abs(5 - 4 - 4.5)) = 4.
Costs can also be used to represent a value that needs to be optimized, i.e., to indicate preferences among solutions. For example, the Sum constraint could specify an additional cost type that returns the value of its s variable for maximization. Costs to be maximized will increase during optimization instead of being decreased toward 0.
As it is often useful to regulate the quantitative relation between cost types for different optimization problems in a different way, there is a cost mapping from the costs how they are represented by the constraint's cost function to the constraint's objective costs. The default cost mapping uses simple factors, e.g., SumobjectiveCosts = 10 × Sumcosts, but a lot more complex mappings can be used or even added by the user.
Costs of constraint instances are assigned to cost functions. A cost function computes the addition of the assigned constraint instances' objective costs. For every constraint instance, at least one of its cost types must be assigned to such a cost function, and every cost type of a constraint instance can only be included once. Cost functions are used by the global search control in order to select a constraint instance for initiating an improvement of the costs.
There is not only one cost function, and the user can introduce arbitrarily many additional cost functions. All cost functions are stored in a list, in which the most recently added cost function has the highest priority for improvement. Costs of a cost function with lower priority will only be selected for an improvement if all constraints of cost functions with higher priority are satisfied, i.e., have costs of 0.
However, two special pre-fabricated cost functions always stay at the very beginning/end of the list: the Maximization Function and the Structural Costs. In addition, there is a Default Cost Function, which will be added automatically when the user adds costs without specifying a concrete cost function. This default function makes the specification of problem a bit easier if there is no need for any specific handling of the constraints' costs.
The Maximization Function is slightly different from the other cost functions. Constraints of costs that are assigned to this function are expected to try to increase this cost value, whereas all other cost functions try to decrease their cost values. Optimization tasks of maximization can be realized by this.
A specific type of constraints that takes care of the structural consistency of the constraint graph uses the cost function Structural Costs. This cost function has the highest priority because other costs may not be computable in a structurally inconsistent graph, e.g., if two variables for the sum and no variable to be added are connected to a Sum constraint. Conventional constraints should not use this cost function.
For every cost function, a specific constraint selection method can be specified, which will be used to select one of the constraint instances for an improvement of the costs. For example, a method can be specified such that always the constraint instance with the highest costs is selected, or one that always selects a random constraint instance.
[HOMEPAGE] -> [Documentation] -> [Concepts] -> [Costs]
For questions, comments or suggestions, please visit our feedback forum.
Last update:
August 21, 2002 by Alexander Nareyek