 |
Constraint techniques In ConSolve® optimization problems are specified as constraint problems. Such problems comprise a number of variables that have to be labelled with a value from a set of permitted values - the variables' domains. This assignment is required to comply with a set of constraints which are also part of the problem description.
The objective function evaluates the quality of a labelling of the variables and identifies thereby solutions of the optimization problem. In the case of ConSolve® the objective function is also defined by constraints. Consequently, the description of an optimization problem contains both: - Hard constraints must be satisfied by a solution of the optimization problem.
- Soft constraints do not inevitably have to be satisfied by solutions, however they represent the objective function that destinguishes more from less preferred solutions. Fuzzy constraints represent a special kind of soft constraints which can be partially satisfied (and therefore also partially be violated).
To solve a problem, ConSolve searches the set of possible solutions by scanning the labelings of the variables. Therefore a so-called search tree is created. During the search the constraints are evaluated (propagated), whereby labelings, which do not represent solutions are recognized promptly and removed from the search tree. Only the combination of these two procedures leads to an acceptable performance for large optimization problems. The search for a solution can be described by the following example:  The above illustration shows the variables A, B and C, which are related to each other by an "unequal" constraint. Every variable has the domain "red", "green", and "blue". With the constraints being evaluated, inadmissible variable allocations are recognized immediately. From this arises the following search tree, which contains six solutions: For example after assigning value "red" to the variable A it is immediately recognized that the value "red" cannot likewise be assigned to the variable B (unequal condition between A and B), so that this particular branch can be removed from the search tree. If we alternatively accomplish a complete tree search without a propagation of the constraints, a much larger search tree representing 27 labelings results. The following illustration shows a cutout of this search tree, of which one branch ("red" assigned to variable A) is scanned completely. Therefore seven inadequate labelings are scanned, which leads to a costly backtracking process in the search tree in each of these cases.
|
|
About
