jOpt Arc Consistency Implementation

jOpt's CSP solver supports many consistency concepts. It allows constraints to be defined on sparse, interval, and set domains for int, long, float, and double Java types as well as set domains for generic objects. The solver also supports node, binary, and generic arcs (including ternary, hyper, and global arcs).

The default algorithm for the solver is based on AC-3 and maintains interval consistency on floating-point domains, bounds consistency on integer domains, and domain consistency on set domains. An alternate algorithm also exists that maintains domain consistency on integer domains. The algorithm used within jOpt can be replaced by implementing a CspAlgorithm interface allowing other consistency algorithms to be defined.

The implementation of jOpt's arc consistency can be broken down into several sub-components.

The components are used to define variables, define constraints on the variables, and provide the ability to generate arcs and nodes that are used to make the variables consistent with their constraints.

The following diagram details some of the components that make up the constraint logic component of jOpt's CSP solver. Note that these components roughly correlate to packages within the code structure of jOpt's CSP solver.

Component Descriptions

• Constraint Store - this component is used by the arc consistency engine to hold constraints that must be applied to variables. The constraint store wraps an arc consistency algorithm that performs that actual work of propagating constraint requirements across nodes (variables)
• Variable - numeric expression, numeric variable, and set variable classes that can be used to build constraints
• Domain - classes that represent possible values that may be assigned to a specific variable
• Constraint - classes determining how values are removed from the domains of the variables
• Solver - utility classes used by the arc consistency engine
• Graph - contains classes that represent the nodes and the arcs for use by the AC algorithm
• Algorithm - represents specific implementations of the AC concept. Many algorithms exist including AC-1, AC-2, AC-3, AC-5, AC-7, etc. The default implementation is a variation on AC-3 that performs generalized arc consistency.