DragonBreath An Optimization Engine based on Constraint Programming and Local Search |
[HOMEPAGE] -> [Documentation] -> [Interfaces to the Engine] -> [Java] -> [Structural Constraints]->[Usage]
Structural Constraints can be controled directly via the GlobalSearchControl.
A complete example of a SCSP is included in the sources of DragonBreath, an explanation can be found here.
Structural Constraints can be loaded via the GlobalSearchControl object. The loading is done by the following member functions of the GlobalSearchControl object:
boolean loadStructuralConstraints(java.io.File file); boolean loadStructuralConstraints(java.lang.String filename);
Each Structural Constraint loaded has to have a unique name. If there was a constraint with the same name loaded before, the new one will not be loaded. The loaded file can contain an initial CSP graph.
The change of the CSP graph via the Structural Constraints can be switched on and off in the GlobalSearchControl. By default the changes are enabled.
void enableStructuralChanges(); void disableStructuralChanges();
An example code that loads a SCSP.
import com.ai_center.dragonbreath.GlobalSearchControl;
public class scExample {
public static void main(String[] args) {
GlobalSearchControl gsc = new GlobalSearchControl(0);
gsc.enableStructuralChanges();
gsc.loadStructuralConstraints("AllStructuralConstraints.sc" );
while (gsc.executeImprovementIteration()) {
System.out.println(gsc.getCostFunctionInfo());
}
}
}
Structural Constraints can not yet be created automatically. They have to be defined manually in an XML-file. A Structural Constraint is defined in as follows:
<SC> <Name>A Unique Name</Name> <Docking> ... </Docking> <Test> ... </Test> <Test> ... </Test> </SC>
Each Structural Constraint contains one <Docking> section and an arbitrary number of <Test> sections.
A <Docking> part has one <Main> section and an arbitrary number of <PAC> and <NAC> sections:
<Docking> <Main> </Main> <PAC> </PAC> <NAC> </NAC> </Docking>
A Test part can not contain PACs, so there are no <PAC> sections.
Each <Main>, <PAC> or <NAC> section can contain one or more <Graph> subsections.
These <Graph> definitions each stand for one contiguous graph-part. They can be taken from the *.scp files stored by DragonBreath. Sometimes for Structural Constraint subgraphs less nodes are needed then can be produced by saving a graph. The graph above can for example not be saved by DragonBreath, as the Proportion Constraint needs two connected Variables (see here for an explanation why nodes sometimes need a defined neighborhood). In such a case the nodes and edges that surplus have to be removed. Also all Cost information have to be removed from the graphs. The node's ids have to be unique for the whole <sc> definition.<Main> <Graph> <Nodes> <Node Id="12" X="2" Y="4" NType="Variable" Name="c1" Value="4.0" /> <Node Id="72" X="3" Y="5" NType="Proportion" Coefficient="0.3" /> </Nodes> <Edges> <Edge EType="*" From="12" To="72" /> </Edges> </Graph> <Graph> </Graph> </Main>
To connect the different <Graph> definitions, for example, when a PAC shares a node with a normal graph part, or if the docking and a test part share a common node, links have to be established. Links are defined via the nodes they connect: <Link From="fromID" To="toID"> The fromID and the toID both are the node's ids. Each link has to be defined from test to docking, from application condition to main part. They are defined at the end of the <Docking> or the <Test> section the from node is part of.
Here the Structural Constraint SAA is first shown graphical:
<SC> <Name>AA</Name> <Docking> <Main> <Graph> <Nodes> <Node Id="10" X="168" Y="63" NType="Variable" Name=":1" Value="0.0" /> <Node Id="15" X="161" Y="267" NType="Variable" Name=":2" Value="0.0" /> <Node Id="86" X="221" Y="157" NType="AA" /> </Nodes> <Edges> <Edge EType="fluff" From="15" To="86" /> <Edge EType="cruft" From="10" To="86" /> </Edges> </Graph> </Main> </Docking> <Test> <Main> <Graph> <Nodes> <Node Id="83" X="64" Y="68" NType="Variable" Name=":1" Value="1.0" /> <Node Id="12" X="66" Y="243" NType="Variable" Name=":2" Value="4.0" /> <Node Id="52" X="66" Y="146" NType="Exponential" Exponent="0.25" /> <Node Id="72" X="52" Y="233" NType="Range" RangeL="2.0" RangeU="7.0" /> </Nodes> <Edges> <Edge EType="power" From="12" To="52" /> <Edge EType="plain" From="12" To="72" /> <Edge EType="powerResult" From="83" To="52" /> </Edges> </Graph> </Main> <Links> <Link From="83" To="10"/> <Link From="12" To="15"/> </Links> </Test> </SC>
The <SC> definitions have to be stored in a *.sc file. Such a file can then be loaded via loadStructuralConstraints() Several <SC> definitions can be combined to one SCSP definition. Also an initial CSP graph can be defined in the <CSP> section. The *.sc file has the following form:
<scsp xmlns="http://www.ai-center.com/projects/dragonbreath" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.ai-center.com/projects/dragonbreath scsp.xsd"> <StructuralConstraints> <SC> </SC> ... <SC> ... </SC> </StructuralConstraints> <CSP> <Graph> ... </Graph> </CSP> </scsp>
The repair process has some parameters that can be customized to easily adjust it to the needs of special Structural Constraints. The following parameters can be used:
<SC removeDockingProbability = "0.005" millisForRepair = "1000">
If the customization by parameters is not sufficient the classes TestGraphRepairer and DockingGraphRepairer can be overwritten. To achive this subclasses of the two classes can be defined. They are registered by the parameter customDockingGraphRepairerClassName or customTestGraphRepairerClassName. These parameters are added as the previous ones.
<SC customTestGraphRepairerClassName = "myCustomTGRepairer" customDockingGraphRepairerClassName = "myCustomDGRepairer">
To create a new repair heuristic two existing classes can be used. One is a high-level class, that takes a graph part and completes or destroys it, the SCGraphRepairer class. And the other one is more low-level the GraphRepairer class which can add and remove single nodes and edges to and from the CSP graph.
Both classes can be parameterized by an object of the class NodeChooseInterface. It defines some of the strategies used during the graph repair.
The StructuralConstraintInstance class can also be replaced. This facilitates the replacement of the strategy of testing part choice or even testing part implementation. The new class has to be a subclass of StructuralConstraintInstance. The name of the new class is registered via the customInstanceClassName parameter.
<SC customInstanceClassName = "myCustomSCInstance">
[HOMEPAGE] -> [Documentation] -> [Interfaces to the Engine] -> [Java] -> [Structural Constraints]->[Usage]
For questions, comments or suggestions, please visit our feedback forum.
Last update:
August 22, 2002 by Alexander Nareyek