[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publications: [PUBLink] [PUBLink])

The approach of using global constraints for local search covers only the satisfaction of conventional global constraints. Besides conventional global constraints, there are now global object and structural constraints as well. Conventional and object constraints are added/deleted by productions, whereas there must be a check after each application of a production to decide on the addition/deletion of global structural constraints (see Section [Application of Structural Constraints]). After application of a production, the inconsistency of affected structural constraints must be updated.

Extensible global (conventional or object) constraints must feature additional update functions to integrate/disintegrate variables and object constraints.

The heuristics of global conventional constraints can now additionally change the graph structure by the application of a production or a sequence of productions. For example, the graph contains a structure like the right upper test alternative of the structural constraint S_{SubTaskNeighbor} of Section [Structural Constraints], and the Less constraint's heuristic would decide on a structural change because it is not able to enforce the variables' order. In consequence, the Less constraint might apply the production P_Lessd to delete itself.

The global structural constraints are very similar to global conventional constraints. One difference is that their costs are not associated with variable assignments, but with the existence or nonexistence of graph elements. Thus, their heuristics can only apply productions. A change of variable values is not allowed (apart from an initial value assignment that they have to provide for created variables).

For example, after deletion of the Less constraint, the global structural constraint that corresponds to the structural constraint S_{SubTaskNeighbor} of Section [Structural Constraints] may become inconsistent. The structural constraint's heuristic might decide to satisfy its right lower alternative because the right upper alternative has become inconsistent. This can be accomplished by using the Task's Start variable as the SubTask's Start variable, and by deleting all other SubTasks of the Task.

Global object constraints are only a reference structure and do not have cost or improvement functions. Their role is to maintain a correct linking of conventional constraints and variables such that the variable updates can be passed correctly and the conventional constraints are aware of the variables' structural connection.

A conventional constraint has to inform connected object constraints about the variables it is interested in, as not all connected variables may be important. For example, a Machine needs information about the involved start and duration variables of a Task's SubTasks, but not about the Task's own variables.

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek