To solve a constraint satisfaction/optimization problem we may utilize the following concepts:
- Solver
- Search Strategies
- Solution
An instance of the class Solver can be created for every instance of the class Problem. The standard should provide a unified way to implement (as a minimum) the following functions:
- Find a solution
- Find all solutions
- Find an optimal solution that minimizes/maximizes an objective variable
To implement these functions the Solver will execute Search Strategies. The standard supports at least one default search strategy that can enumerate (assign values to) constrained variables that define the problem while satisfying all currently posted constraints. Concrete implementations may provide different search strategies as long as they implement the standardized SearchStrategy interface.
A user should be able to limit search by available time (total and for certain search subtrees), by a number of considered solutions, a number of failures, etc.
The Solver should allow a user to define and combine several strategies together in one search by using different arrays of constrained variables and different selectors.
A search strategy can be customized by an end user who may specify a way of how to assign values to an array of constrained variable using predefined or custom selectors:
- VariableSelector(s), e.g. VariableSelector.MAX_VALUE selects an unbound constrained variable with teh largest upper bound
- ValueSelector(s), e.g. ValueSelector.MIN selects the smallest value from the domain of a constrained variable.
Click here to see the proposed list of the standard selectors.
It should be possible to:
- Add new variable selectors and value selectors
- Define new search strategies
I think the above concepts present a common deniminator for many existing CP solvers.
In the future posts I plan to discuss more controversial concepts:
- Reversible Objects and Actions that support a user-defined interface during the search process
- Representing Search Strategies as Goals (Goal Programming)
- Solution Iterator
- Well-known but not yet standardized Search Strategies
- Allowing a user to write custom Search Strategies.
The Problem Resolution is a favorite research topic for many CP professionals and all comments and suggestions are very welcome.
