DragonBreath An Optimization Engine based on Constraint Programming and Local Search |
[HOMEPAGE] -> [Documentation] -> [Interfaces to the Engine] -> [Java] -> [Structural Constraints] -> [Usage] -> [Example]
In this section a simple example SCSP is developed. The source code can be found in com.ai_center.dragonbreath.examples.structuralConstraintExample.
The imaginary substance Fluff is produced via some machines. During the production of fluff some Cruft is also created. The produced cruft can be removed by a special machine, the Chute. But the usage of the Chute consumes some fluff. There are three different machines to create fluff and the one that disposes cruft. Each machine generates different amounts of the products and has different efficiency factors. The efficiency factor determines the amount of cruft that is produced per unit produced fluff.
The formula is cruft = fluff Efficiency. The biggest machine AAA produces apart from the cruft that is determined by the efficiency and the amount of fluff a constant amount of cruft of one unit.
For the Chute the Efficiency is defined the other way around: fluff = cruft Efficiency.
In the following table the productions of the different machines are presented.
Machine | Produced Fluff | Efficiency | Produced Cruft |
A | [0, 3] | 0.3 | [0, 1.39] |
AA | [2, 7] | 0.25 | [1.19, 1.62] |
AAA | [5, 10] | 0.2 | [1.37, 1.58] |
Chute | [-2, -1.1] | 3 | [-1.25, -1.03] |
To solve the Problem we need some conventional and structural constraints. The next figure shows a typical CSP graph that might solve the problem.
The productions of machines are represented by variables that contain the produced amounts of the substances and by restrictions on the possible values of these variables. Each machine is represented as an object-constraint. In the next figure the base graphs of the machines are depicted. Each machine has two variables connected, one for the produced fluff and one for the produced cruft. Machine AAA has an extra variable for the constant cruft production. To register the cruft and fluff production we need two variables. Two object-constraints Fluff and Cruft give semantic to the variables. These two constraints each have one variable in their base graph. They can also be seen in the next figure.
With the object-constraints from the last section all the needed variable can be fixed in their semantic. But we also need conventional constraints to determine the values the variables can take. All used constraints and their base graphs are depicted in the next figure.
The Range-Constraints and the Exponential-Constraint from com.ai_center.dragonbreath.constraints can be used to restrict the amount of substance a machine can produce, and the efficiency of the machines.
Then we have to be able to compare the sum of a set of variables with a single value. This is necessary to compare the amount produced substances with the requested amount fluff and cruft. But the repair strategie has to be different for fluff and cruft. Therefore we need two different constraints. For fluff we call it FluffSum, for cruft CruftSum. The base graph of the two contains only one Variable which contains the result of the summation. The extensions can be used to add addends.
For both constraints the repair tries to fulfill it by changing randomly the connected variables. But as the other constraints of the CSP graph also change the values of the variables the structure of the graph determines if a stable solution can be found. Only if the right combination of machines is present a pure value change can lead to a solution.
For this reason in a small random number of repair attempts not the variables but the CSP graph is changed. The exact number of times the structure and not the variables are changed can either be determined automatically by machine learning algorithms or as it happened here by simple trial and error. The sort of structural change necessary depends on the situation. Generally either a machine is added or removed. Take a look at the function structuralRepair() in the FluffSumConstraint and the CruftSumConstraint to see how exactly the structure is changed.
Registering the Constraints
All the new structural and conventional constraints have to be registered at the Registry. In this example that is done in the class com.ai_center.dragonbreath.examples.structuralConstraintExample.fluffExampleConstraints.RegistryConstants with the function registerConstants().
With all the elements to design the problem were created we now have to develop structural constraints which determine the form of a solution CSP graph.
The search for a valid solution starts with an empty graph. We need structural constraints that add the first elements. This is done by two simple structural constraints SFluffInit and SCruftInit. They can be seen in the next figure. For the graph to contain only one Cruft and one Fluff object constraint there are the constraints SOneFluff and SOneCruft.
The domains of the cruft and the fluff variable have to be restrained to the requested values and the sum of the produced fluff and the produced fluff have to be compared with the request. This is done by SRequestedFluff and SCruftMinimize.
The variable that represent the produced amounts have to be constrainted to values that are determined by the specifications of the machines. This is achieved via the structural constraints SA, SAA, SAAA and SChute.
The variables also have to be added to the total of produced substance in FluffSum and CruftSum. All this is done with the constraints SFluffProduktion, SCruftProduktion and SAAAConstCruftProduktion. The last necessary constraint is SVarRemoval. It is used to remove superfluous variables. Whenever during the search process a machine is removed the variables stay in the graph. But as they are still connected to the sum-constraints they would impede the finding of a solution.
With these 14 structural constraints the problem can be solved.
[HOMEPAGE] -> [Documentation] -> [Interfaces to the Engine] -> [Java] -> [Structural Constraints] -> [Usage] -> [Example]
For questions, comments or suggestions, please visit our feedback forum.
Last update:
August 22, 2002 by Alexander Nareyek