DragonBreath
An Optimization Engine based on Constraint Programming and Local Search


[HOMEPAGE] -> [Documentation] -> [Interfaces to the Engine] -> [Java] -> [Structural Constraints] -> [Internal Structure]

  [General Approach]   [Docking Graph]   [Test Graph]   [Graph Repair]


Graph Repair

We can now find structural constraint instances and evaluate to what degree the CSP graph fulfills the constraint. In the next step this knowledge should be used to repair the CSP graph in order to solve the SCSP.

As noted in the presentation of SCSPs they are undecidable. For that reason it is very expensive to find a correct graph via breath first search and impossible to be found via backtracking.

In contrast to these systematical search methods does local search scale very good. So it can also be used in the infinite search space at hand. Therefore we want to use the paradigm of Using Global Constraints for Local Search. The steps a repair can take are explained here.

The local repair takes place at the level of structural constraint instances. Each repair is done via a simple gradient descent. For that gradient descent the matching of the test graph was developed in such a way that it can now be used to guide the descent.

Requirements for the Repair

The changes of the CSP graph should be local and goal-oriented. Goal-oriented means that the graph is changed by a gradient descent algorithm step by step. As with every greedy search there is the danger of local extrema and plateaus. To search the whole search space there has to be a stochastic element in the search.

The criteria of local search is hard to realize as a CSP graph is not planar. Whenever it is possible that there exists an edge between two node-types an edge could be created between each pair of nodes of such types. So all these nodes could get neighbors in just one repair step.

The idea of local search was introduced for each instance to impede as little as possible with the validity of other constraint instances. So beeing local does not mean that only adjacent neighbors are changed, but that as few as possible instances are influenced by a graph repair. That has to be realized for each repair measure.

In spite of such measures it can allways happen that structural constraint instances influence each other in their repair process. That can not be avoided and is part of the search for a solution.

Possible Repairs

If a structural constraint instance is not fulfilled it means that the docking but no test graph could be found. To fulfill a constraint instance either a test graph can be produced in the CSP graph or the docking graph match can be destroyed.

In the next figure at first there is one train and one wagon constraint that are not connected. We want to fulfill the constraint SWagonTrain.

To do so we can:

  1. connect the existing wagon with the train
  2. create a new wagon and connect it
  3. destroy the docking graph
In all these cases the constraint would be fulfilled.


Repair

Graph Changes

The steps of a CSP graph change are determined by the basegraphs and the extensions. And the repair is determined by the error of the test graph. So it can happen that we have to execute a series of CSP graph changes to achieve the requested repair.

Extension

For a requested enlargment of the CSP graph sometimes a series of actions have to be executed. These actions can easily be determined via a greedy algorithm.

Whenever a node is missing first of all it's basegraph is created. To do that we can use both existing and new nodes. Once the basegraph exists the node can be added. If we want to use new nodes to create the basegraph we proceed recursively in the same way.

To add an edge we randomly select an extension that contains the needed edge. To change the graph as little as possible we rather choose smaller then bigger extensions. The nodes that are necessary for the extensions are determined in the same way as for the basegraph. If the requested edge does only exist in the basegraph of the extended node we have to remove the node and afterwards create it again with the requested edge.

Reduction

To remove edges or nodes can be more complicated as the following example shows.

There are two sorts of object constraint nodes. Wagons and Trains. The wagon has an empty basegraph and no extensions. The basegraph of the train is shown in the next figure.

Train Basegraph Extensions

First the steps that lead to such a none trivial task are shown. In the next figure first the basegraph is created. Then two times two Wagon nodes are added. And finally three are removed again. Now the train has three wagons.

3 Wagons

Now we want to remove a special wagon node again. If we simply used one of the two possible extensions the train constraint would be reduced below it's basegraph.

Reduced Below Basegraph

So we first have to add further wagons before we can remove the requested one.

Reducing the Train

If an edge that belongs to a basegraph should be removed we can either remove the whole node, or if a fitting extension exists we can first create a substitute for the removed edge, so that the basegraph stays valid.

In general we can not guarantee that after the removal of an edge there haven't been created extra edges due to necessary extensions.

The biggest problem is the removal of a node. It requires to reduce the node to be reduced exactly to it's basegraph. Only then can it be reduced. We know that there is a sequence of steps that lead to the basegraph, as the graph was created the other way around. But as during creation an arbitrary number of nodes could have been created and deleted again the exact was is not known.

I tried both, a complete search, which worked by transforming the problem of finding the correct combination of extensions and reductions into a problem of linear programming and by a simple greedy search for the solution. The greedy search resulted faster, so that is what is implemented in DragonBreath.

We reduce the node edge after edge. If for a certain reduction other edges are necessary that do not yet exist we simply create them as described above.

These mechanisms are implemented in the GraphRepairer class.

The Repair Mechanism

With the possibilities of graph change from the GraphRepairer class we now can change the graph in such a way that we decrease the structural error. The following algorithm can be seen as a starting point for more specialized repair mechanisms that have to be implemented for new structural constraints. It does a correct repair, but can not take into account the special features of a concrete problem. There are nevertheless some variables that change the behaviour of the repair.

There are generally two ways of fulfilling a constraint instance.

Destroying the DockingGraph

The easiest way of fulfilling a constraint instance is by destroying it's docking graph. That can be achieved by removing one edge or node from a main part or a PAC match. Or an other possibility is to create a NAC match. The creation of a graph part is described below.

Repairing the TestGraph

If there are several test graphs we first have to chose which one to repair. Here we can use the structural error we computed while probing the test graphs. Now we can choose the test graph with the lowest error. Secondly we can use the match to determine where to change the CSP graph to improve the match. As we decided to locate the abstract test graph data in the constraint type we have to do the repair of the instance directly after checking the test graphs. Because then the test graph holds the partial interpretation valid for the instance.

When we want to repair a test graph there can be two situations: One or several mainParst are not complete or a NAC has to be destroyed.

Classes for Graph Repair

The graph repair is split in several layers from the most concrete to the most abstract.

The GraphRepairer is the most concrete class. It provides functions to add and remove single nodes and edges. If there is more then one step required to achieve the requested change it finds them via a greedy search.

The SCGraphRepairer Structural Constraint Graph Repairer is a bit more abstract.
It has two functions:

completeSubgraph() takes a partly interpreted MovableSubgraph and creates a full match for it.

And destroyGraphPart The other one takes a fully interpreted StructualConstraintGraphPart and removes one of the edges or nodes of the interpretation.

The DockingGraphRepairer takes an interpreted DockingGraph and destroys it by either adding a NAC or removing a mainPart or a PAC.

The TestGraphRepairer takes a TestGraph and creates a match for it.

During the repair process some decisions have to be made. For example if new nodes or existing nodes should be used to create a basegraph. These decisions have to be made during the greedy search for repair steps. But the GraphRepairer does not have enough knowledge to decide these items. So it delegates them to it's nodeChooser. The HeuristicNodeChooser is used to implement the locality of the repair process. Therefore it questions all the existing constraint instances if a requested change would impede with their graphs. Also it queries the SCGraphRepairer if a necessary graph change can be incorporated in the actual repair process.

The nodeChooser can be replaced to use the GraphRepairer in other contexts. It can for example be used to create a random CSP graph.

To be able to use the same DockingGraphRepairer and TestGraphRepairer in all instances they are members of the StructuralConstraintType. But they are not used globally, as each constraint type should be able to implement it's own repair strategies.

Repair Class Diagramm

Destroying a Graph Part

If a test graph is not fulfilled because a NAC was found, or we want to delete the docking graph, we have to remove an existing match. Normally we simply have to remove one edge or node that exists in the match. For NACs we also have to test if there is no substitute for the destroyed match. And if there is a substitute we have to keep on destroying until it was removed.

Completing a Graph Part

This done in SCGraphRepairer.completeSubgraph(). One graph part after the other is completed until matches for all parts exist.

A typical sequence of steps during repair is depicted in the next figure.

Repair Sequence Diagramm


[HOMEPAGE] -> [Documentation] -> [Interfaces to the Engine] -> [Java] -> [Structural Constraints] -> [Internal Structure]

  [General Approach]   [Docking Graph]   [Test Graph]   [Graph Repair]



For questions, comments or suggestions, please visit our feedback forum.

Last update:
May 14, 2003 by Tim Baermann