Architecture

Architecture

The functionalities of Asteroid are split into two main packages:

• Invariants: proposes a framework for specifying variables, and invariants to represent complex formulas in such a way that the output values of these formulas can be updated efficiently by relying on an incremental process. An invariant is merely an operator or a function that inputs one or more variables, controls one or more variables, and compute their values by applying its defining formula on its inputs.
• Constraints: proposes a framework for specifying constraints, which are basically functions that compute the degree of violation of these constraints.

These two package come with a core, that define the framework, interfaces, etc. and a library, including a set of standard invariants or constraints to use for solving combinatorial problems.

The invariants package

This package is made of three architectural layers:

1. The computation structure layer defines concepts like Model, Invariants, Variables and its two derived types: IntVar and IntSetVar representing variables with integer types, and set of integer types, respectively. See Invariants.Core.ComputationStructure
2. The layer just below is the PropagationStructure layer, which handles propagation of updates on the graphs defined by invariants and variables. The main idea is that variables and invariants of the computation structure layer are both modelled as PropagationElement, while the model defined in the computation structure layer is a propagation structure. See Invariants.Core.PropagationStructure. The two main concepts of this layer are PropagationElements and PropagationStructure. PropagationElements have two main features:
   • They are nodes in a DAG, having references to the propagation elements that are before and after them in the propagation process.
   • They have a method PerformPropagation which is called when propagation is performed by the PropagationStructure
3. The bottom layer is a package for managing directed acyclic graphs (DAG) that is able to incrementally maintain a topological sorting on the elements of DAG’s. The dependencies between propagation elements are represented as a graph, which is supposed to be acyclic. We need to compute a topological sort on these graphs in order to ensure that updates to the variables are performed at most once per variable. See Invariants.Core.Algo.DAG

The library of invariants is proposed on top of the computation structure layer. It includes logic, numeric, min/max, and set invariants and can of course be extended by implementing the proper interfaces defined in the computation structure layer, typically the Invariant interface. See Invariants.Library

The constraint package

The constraint package adds an additional layer on top of the invariant package. It defines the Constraint and the Constraint System classes. A constraint is merely a function that computes the degree of violation of the constraint. Within the constraint, this computation is typically implemented by means of invariants to ensure that the violation is updated incrementally when neighbours are explored. Furthermore, constraints are also able to attribute a degree of violation to each of the variable they are posted on. This degree of violation can be queried through a dedicated method.

Constraint systems aim at aggregating constraints. A constraint system is a constraint, exhibiting the same violation degrees. The violation degree of the while constraint system is the sum of the violation of the constraints posted in it.

The violation degree associated with specific variables is handled differently. To have an associated violation degree, a variable must be registered to the constraint system. The constraint system sums the degree of violation, associated to each variable referenced by constraints posted in it, and whose value is derived from the registered variable. This is performed by exploring the structure of invariants posted in the model. This enables one to associate a violation degree with any variables, but this violation degree must be handled carefully, as it is not equal to a differentiation.

Other packages

Search engine

The search engine package provides a set of primitives generally used when implementing a search script, namely:

• Selectors such as select max, randomized selectors, random permutations, etc.
• Stopwatch to enable benchmarking of solutions.

Job shop

This package proposes a layer on top of the invariant package to solve job hop scheduling problems. It proposes concepts such as tasks, resources, schedule, etc.

Asteroid was initially built to solve a JobShop problem, so that the emphasis was not set on features that do not contribute directly to the JobShop solver. This justifies many of the features of Asteroid.