Solving Constraint Satisfaction and Optimization Problems

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.

Advertisements

About jacobfeldman

CTO at www.openrules.com http://www.linkedin.com/in/jacobfeldmanopenrules
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s