jopt.csp
Class CspSolver

java.lang.Object
  jopt.csp.CspSolver

public abstract class CspSolver

extends java.lang.Object

Class that is used to construct and solve CSP problems. The solver can be based on various different CSP algorithms and searching techniques, but it also has default algorithms if the user does not wish to override these options.

Author:

Nick Coleman

Constructor Summary

CspSolver()

Method Summary

abstract void	addConstraint(CspBooleanExpr bool) Adds a boolean expression as a constraint to the CspSolver.
abstract void	addConstraint(CspConstraint constraint) Adds a constraint to the constraint reduction algorithm of this CspSolver.
abstract void	addConstraint(CspConstraint constraint, boolean keepAfterReset) Adds a constraint to the constraint reduction algorithm of this CspSolver.
abstract void	addVariable(CspVariable var) Adds a variable to be managed by the solver.
abstract void	clear() Resets all variables and removes all constraints and variables added to solver
static CspSolver	createSolver() Creates a new solver based upon a default generalized AC5 bounds algorithm with a default search manager
static CspSolver	createSolver(CspAlgorithm alg) Creates a new solver based upon a specific algorithm with the default search manager
static CspSolver	createSolver(CspAlgorithm alg, SearchManager mgr) Creates a new solver based upon a given CSP algorithm and search manager
static CspSolver	createSolver(SearchManager mgr) Creates a new solver based upon a default generalized AC5 algorithm with a specific search manager
abstract boolean	getAutoPropagate() Retrieves the auto propagation status
LocalSearch	getLocalSearch() Returns a LocalSearch object that is used to create common objects for use during local neighborhood search operations
SearchActions	getSearchActions() Returns a SearchActions object that is used to create common search operations
SearchGoals	getSearchGoals() Returns a SearchGoals object that is will create common goals for guiding searches
SearchLimits	getSearchLimits() Returns a SearchLimits object that is used to create common limits for use to control search operations
SearchTechniques	getSearchTechniques() Returns a SearchTechniques object that is used to create common techniques for guiding searches such as Breadth First Searching and Depth First Searching
CspVariableFactory	getVarFactory() Returns the variable factory for the algorithm the solver is based upon
abstract boolean	nextSolution() Searches for another solution to a previous search initiated by a call to a solve method.
abstract boolean	propagate() Propagates the constraints currently defined using the constraint reduction algorithm of this CspSolver.
abstract void	reset() Resets all variables by undoing all changes stored in the CspSolver for the wrapped algorithm and leaving any constraints that have been added.
abstract void	restoreNeighboringSolution(SolverSolution initial, SolverSolution neighbor) Restores a neighboring solution to another solution that was previously stored.
abstract void	restoreSolution(SolverSolution solution) Restores domain state information for variables defined within a solution.
void	restoreSolution(SolverSolution solution, boolean reset) Calls reset() before calling restoreSolution(SolverSolution) depending on boolean flag passed
abstract void	setAutoPropagate(boolean autoPropagate) Sets the auto propagation status of this CspSolver.
boolean	solve(CspDoubleVariable[] vars, double precision) Resets the solver and locates a solution for an array of variables within the problem contained by the solver Since real numbers can be divided an infinite number of times, a precision value must be specified to indicate when the range of the variable is small enough to consider the variable completely instantiated.
boolean	solve(CspFloatVariable[] vars, float precision) Resets the solver and locates a solution for an array of variables within the problem contained by the solver Since real numbers can be divided an infinite number of times, a precision value must be specified to indicate when the range of the variable is small enough to consider the variable completely instantiated.
boolean	solve(CspIntVariable[] vars) Resets the solver and locates a solution for an array of variables within the problem contained by the solver
boolean	solve(CspIntVariable[] vars, boolean reset) Locates a solution for an array of variables within the problem contained by the solver
boolean	solve(CspLongVariable[] vars) Resets the solver and locates a solution for an array of variables within the problem contained by the solver
boolean	solve(CspSetVariable[] vars) Resets the solver and locates a solution for an array of variables within the problem contained by the solver
boolean	solve(Search search) Resets the solver and locates a solution for the current problem given a Search object.
boolean	solve(SearchAction action) Resets the solver and locates a solution for the current problem given a search action that defines a set of operations that should be performed in order to locate a solution.
boolean	solve(SearchAction action, boolean reset) Locates a solution for the current problem given a search action that defines a set of operations that should be searched in order to locate a solution.
boolean	solve(SearchAction action, SearchGoal goal) Resets the solver and locates a solution for the current problem given a search action that defines a set of operations that should be performed in order to locate a solution.
boolean	solve(SearchAction action, SearchGoal goal, boolean continuallyImprove) Resets the solver and locates a solution for the current problem given a search action that defines a set of operations that should be performed in order to locate a solution.
boolean	solve(SearchAction action, SearchGoal goal, SearchTechnique technique) Resets the solver and locates a solution.
boolean	solve(SearchAction action, SearchGoal goal, SearchTechnique technique, boolean continuallyImprove) Resets the solver and locates a solution for the current problem.
abstract boolean	solve(SearchAction action, SearchGoal goal, SearchTechnique technique, boolean continuallyImprove, boolean reset) Locates a solution for the current problem.
boolean	solve(SearchAction action, SearchTechnique technique) Resets the solver and locates a solution.
boolean	solve(SearchAction action, SearchTechnique technique, boolean reset) Locates a solution for the current problem.
abstract boolean	solve(Search search, boolean reset) Locates a solution for the current problem given a Search object.
SolverSolution	storeSolution(SolutionScope scope) Returns a solution that has recorded the variable domain information for the variables within the scope specified.
abstract void	storeSolution(SolverSolution solution) Records domain values for variables that are defined in the scope of the specified solution.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

CspSolver

public CspSolver()

Method Detail

createSolver

public static CspSolver createSolver()

Creates a new solver based upon a default generalized AC5 bounds algorithm with a default search manager

createSolver

public static CspSolver createSolver(CspAlgorithm alg,
                                     SearchManager mgr)

Creates a new solver based upon a given CSP algorithm and search manager

Parameters:

alg - Algorithm the new solver should be based upon. If null, the implementing class should use a default of its choice.

mgr - Search manager that will be used to locate solutions by solver. If null, the implementing class should use a default solver of its choice.

createSolver

public static CspSolver createSolver(SearchManager mgr)

Creates a new solver based upon a default generalized AC5 algorithm with a specific search manager

Parameters:

mgr - Search manager that will be used to locate solutions by solver

createSolver

public static CspSolver createSolver(CspAlgorithm alg)

Creates a new solver based upon a specific algorithm with the default search manager

Parameters:

alg - Algorithm solver is based upon

getVarFactory

public CspVariableFactory getVarFactory()

Returns the variable factory for the algorithm the solver is based upon

getSearchActions

public SearchActions getSearchActions()

Returns a SearchActions object that is used to create common search operations

getSearchGoals

public SearchGoals getSearchGoals()

Returns a SearchGoals object that is will create common goals for guiding searches

getSearchTechniques

public SearchTechniques getSearchTechniques()

Returns a SearchTechniques object that is used to create common techniques for guiding searches such as Breadth First Searching and Depth First Searching

getLocalSearch

public LocalSearch getLocalSearch()

Returns a LocalSearch object that is used to create common objects for use during local neighborhood search operations

getSearchLimits

public SearchLimits getSearchLimits()

Returns a SearchLimits object that is used to create common limits for use to control search operations

getAutoPropagate

public abstract boolean getAutoPropagate()

Retrieves the auto propagation status

Returns:

the auto update status of this CspSolver

setAutoPropagate

public abstract void setAutoPropagate(boolean autoPropagate)

Sets the auto propagation status of this CspSolver.

Parameters:

autoPropagate - The new value of the autoUpdate flag.

propagate

public abstract boolean propagate()

Propagates the constraints currently defined using the constraint reduction algorithm of this CspSolver. Note that calls to this method are unnecessary when the auto propagate flag is set.

Returns:

True if propagation was successful, false if it fails

addVariable

public abstract void addVariable(CspVariable var)

Adds a variable to be managed by the solver. This ensures the variable's state is maintained as the solver searches for a solution.

addConstraint

public abstract void addConstraint(CspConstraint constraint)
                            throws PropagationFailureException

Adds a constraint to the constraint reduction algorithm of this CspSolver. Constraint will be kept after store is reset.

Parameters:

constraint - The constraint to be added to the reduction algorithm.

Throws:

If - auto propagate is set, this forces the wrapped algorithm to propagate the constraint. If the propagation fails, an appropriate exception is thrown. If, however, the auto propagate flag is not set, this method will not throw an exception.

PropagationFailureException

addConstraint

public abstract void addConstraint(CspConstraint constraint,
                                   boolean keepAfterReset)
                            throws PropagationFailureException

Adds a constraint to the constraint reduction algorithm of this CspSolver. Allows you to specify whether the constraint will be kept after store is reset.

Parameters:

constraint - The constraint to be added to the reduction algorithm.

keepAfterReset - True if constraint should be kept after reset if performed

Throws:

If - autoPropagate is set, this forces the wrapped algorithm to propagate the constraint. If the propagation fails, an appropriate exception is thrown. If, however, the autoPropagate is not set, this method will not throw an exception.

PropagationFailureException

addConstraint

public abstract void addConstraint(CspBooleanExpr bool)
                            throws PropagationFailureException

Adds a boolean expression as a constraint to the CspSolver.

Parameters:

bool - Boolean expression representing a constraint

Throws:

PropagationFailureException

clear

public abstract void clear()

Resets all variables and removes all constraints and variables added to solver

reset

public abstract void reset()

Resets all variables by undoing all changes stored in the CspSolver for the wrapped algorithm and leaving any constraints that have been added.

solve

public abstract boolean solve(Search search,
                              boolean reset)

Locates a solution for the current problem given a Search object.

Parameters:

search - Search object used to locate solutions

reset - True if state of problem should be reset before starting search

Returns:

True if a solution was found

solve

public boolean solve(Search search)

Resets the solver and locates a solution for the current problem given a Search object.

Parameters:

search - Search object used to locate solutions

Returns:

True if a solution was found

solve

public abstract boolean solve(SearchAction action,
                              SearchGoal goal,
                              SearchTechnique technique,
                              boolean continuallyImprove,
                              boolean reset)

Locates a solution for the current problem.

Parameters:

action - Search action used to locate a solution

goal - Goal to guide search towards a solution

technique - Search technique used to locate a solution

continuallyImprove - True if each successive solution found will be an improvement over previous, false if the best solution (according to the goal) is found during the original search

reset - True if state of problem should be reset before starting search

Returns:

True if a solution was found

solve

public boolean solve(SearchAction action,
                     SearchGoal goal,
                     SearchTechnique technique,
                     boolean continuallyImprove)

Resets the solver and locates a solution for the current problem.

Parameters:

action - Search action used to locate a solution

goal - Goal to guide search towards a solution.

technique - Search technique used to locate a solution

continuallyImprove - True if successive solutions found will be an improvement over previous, false if the best solution (according to the goal) is found during the original search

Returns:

True if a solution was found

solve

public boolean solve(SearchAction action,
                     SearchGoal goal,
                     SearchTechnique technique)

Resets the solver and locates a solution.

Parameters:

action - Search action used to locate a solution

goal - Goal to guide search towards a solution.

technique - Search technique used to locate a solution

Returns:

True if a solution was found

solve

public boolean solve(SearchAction action,
                     SearchTechnique technique)

Resets the solver and locates a solution.

Parameters:

action - Search action used to locate a solution

technique - Search technique used to locate a solution

Returns:

True if a solution was found

solve

public boolean solve(SearchAction action,
                     SearchTechnique technique,
                     boolean reset)

Locates a solution for the current problem.

Parameters:

action - Search action used to locate a solution

technique - Search technique used to locate a solution

reset - True if state of problem should be reset before starting search

Returns:

True if a solution was found

solve

public boolean solve(SearchAction action,
                     SearchGoal goal,
                     boolean continuallyImprove)

Resets the solver and locates a solution for the current problem given a search action that defines a set of operations that should be performed in order to locate a solution. A default DFS searching technique is used to find the solution along with a goal to guide the search towards that desired result.

Parameters:

action - Search action used to locate a solution

goal - Goal to guide search towards a solution.

continuallyImprove - True if each successive solution found will be an improvement over previous, false if the best solution (according to the goal) is found during the original search

Returns:

True if a solution was found

solve

public boolean solve(SearchAction action,
                     SearchGoal goal)

Resets the solver and locates a solution for the current problem given a search action that defines a set of operations that should be performed in order to locate a solution. A default DFS searching technique is used to find the solution along with a goal to guide the search towards that desired result. This will return after all solutions have been located and the best solution has been found.

Parameters:

action - Search action used to locate a solution

goal - Goal to guide search towards a solution.

Returns:

True if a solution was found

solve

public boolean solve(SearchAction action)

Resets the solver and locates a solution for the current problem given a search action that defines a set of operations that should be performed in order to locate a solution. A default DFS searching technique is used to find the solution.

Parameters:

action - Search action used to locate a solution

Returns:

True if a solution was found

solve

public boolean solve(SearchAction action,
                     boolean reset)

Locates a solution for the current problem given a search action that defines a set of operations that should be searched in order to locate a solution. A default DFS searching technique is used to find the solution.

Parameters:

action - Search action used to locate a solution

reset - True if solver should be reset before solving

Returns:

True if a solution was found

solve

public boolean solve(CspIntVariable[] vars)

Resets the solver and locates a solution for an array of variables within the problem contained by the solver

Parameters:

vars - Array of variables to instantiate

Returns:

True if a solution was found

solve

public boolean solve(CspIntVariable[] vars,
                     boolean reset)

Locates a solution for an array of variables within the problem contained by the solver

Parameters:

vars - Array of variables to instantiate

reset - True if solver should be reset before solving

Returns:

True if a solution was found

solve

public boolean solve(CspLongVariable[] vars)

Resets the solver and locates a solution for an array of variables within the problem contained by the solver

Parameters:

vars - Array of variables to instantiate

Returns:

True if a solution was found

solve

public boolean solve(CspFloatVariable[] vars,
                     float precision)

Resets the solver and locates a solution for an array of variables within the problem contained by the solver Since real numbers can be divided an infinite number of times, a precision value must be specified to indicate when the range of the variable is small enough to consider the variable completely instantiated.

Parameters:

vars - Array of variables to instantiate

precision - Minimum precision to which variable domain will be reduced

Returns:

True if a solution was found

solve

public boolean solve(CspDoubleVariable[] vars,
                     double precision)

Resets the solver and locates a solution for an array of variables within the problem contained by the solver Since real numbers can be divided an infinite number of times, a precision value must be specified to indicate when the range of the variable is small enough to consider the variable completely instantiated.

Parameters:

vars - Array of variables to instantiate

precision - Minimum precision to which variable domain will be reduced

Returns:

True if a solution was found

solve

public boolean solve(CspSetVariable[] vars)

Resets the solver and locates a solution for an array of variables within the problem contained by the solver

Parameters:

vars - Array of variables to instantiate

Returns:

True if a solution was found

nextSolution

public abstract boolean nextSolution()

Searches for another solution to a previous search initiated by a call to a solve method.

Returns:

True if a solution was found

storeSolution

public SolverSolution storeSolution(SolutionScope scope)

Returns a solution that has recorded the variable domain information for the variables within the scope specified.

Parameters:

scope - Scope of variables to include in solution

storeSolution

public abstract void storeSolution(SolverSolution solution)

Records domain values for variables that are defined in the scope of the specified solution.

Parameters:

solution - Solution object to record data that specifies which variables should be captured in solution

restoreSolution

public void restoreSolution(SolverSolution solution,
                            boolean reset)
                     throws PropagationFailureException

Calls reset() before calling restoreSolution(SolverSolution) depending on boolean flag passed

Parameters:

solution - Solution object with recorded variable data that should be restored

reset - True if solver should be reset before restoration

Throws:

PropagationFailureException

restoreSolution

public abstract void restoreSolution(SolverSolution solution)
                              throws PropagationFailureException

Restores domain state information for variables defined within a solution. A restoration simply reduces the variables defined within the solutions to be within the limits of the solution. A reset call must be made before restoring if the solution should not be applied to the current state of the solver but instead should be applied to the original state of the solver.

Parameters:

solution - Solution object with recorded variable data that should be restored to problem

Throws:

PropagationFailureException

restoreNeighboringSolution

public abstract void restoreNeighboringSolution(SolverSolution initial,
                                                SolverSolution neighbor)
                                         throws PropagationFailureException

Restores a neighboring solution to another solution that was previously stored. A neighbor does not need to include any variables that already exist in the initial solution if the values of those variables should not be altered from the initial. If the neighbor wants to restore a different value than the initial, it must include it in the neighboring solution. The neighbor may also define new variables not included in the initial solution.

Parameters:

initial - Initial solution that was previously stored

neighbor - Neighboring solution to restore

Throws:

PropagationFailureException