org.opencyc.constraintsolver
Class ConstraintProblem

java.lang.Object
  |
  +--org.opencyc.constraintsolver.ConstraintProblem

public class ConstraintProblem
extends java.lang.Object

ConstraintRule object to model the attributes and behavior of a constraint problem.

A ProblemParser object is created to parse the input constraint problem representation.
A ValueDomains object is created to model the variables and their value domains.
A VariableDomainPopulator object is created to model variables whose value domain cardinality exceeds a threshold for special case processing.

Author:
Stephen L. Reed

Copyright 2001 Cycorp, Inc., license is open source GNU LGPL.

the license

www.opencyc.org

OpenCyc at SourceForge

THIS SOFTWARE AND KNOWLEDGE BASE CONTENT ARE PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENCYC ORGANIZATION OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE AND KNOWLEDGE BASE CONTENT, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


Field Summary
protected  ArgumentTypeConstrainer argumentTypeConstrainer
          ArgumentTypeConstrainer for this ConstraintProblem.
protected  java.util.ArrayList constraintRules
          Collection of the constraint rules used in the search for solution(s).
static int DEFAULT_VERBOSITY
          The default verbosity of this object's output.
protected  java.util.ArrayList domainPopulationRules
          Collection of the rules which populate variable domains.
protected  ForwardCheckingSearcher forwardCheckingSearcher
          ForwardCheckingSearcher for this ConstraintProblem.
 CycFort mt
          The OpenCyc microtheory in which the constraint rules should be asked.
protected  int nbrAsks
          Number of KB asks performed during the search for solution(s).
 java.lang.Integer nbrSolutionsRequested
          The number of solutions requested.
protected  NodeConsistencyAchiever nodeConsistencyAchiever
          NodeConsistencyAchiever for this ConstraintProblem.
protected  CycList problem
          The input problem CycList.
protected  ProblemParser problemParser
          ProblemParser object for this ConstraintProblem.
 boolean randomizeInput
          When true randomizes the order of the variables and domain values before beginning the search for a solution.
protected  RuleEvaluator ruleEvaluator
          RuleEvaluator for this ConstraintProblem.
protected  java.util.ArrayList simplifiedRules
          Collection of the simplified constraint rules derived from the input problem CycList.
protected  Solution solution
          Solution for this ConstraintProblem.
protected  ValueDomains valueDomains
          ValueDomains object for this ConstraintProblem.
protected  java.util.ArrayList variables
          Collection of the constraint variables as CycVariable objects.
protected  int verbosity
          Sets verbosity of this object's output.
 
Constructor Summary
ConstraintProblem()
          Constructs a new ConstraintProblem object, creating a new CycAccess object.
ConstraintProblem(CycAccess cycAccess)
          Constructs a new ConstraintProblem object given an existing connection to the OpenCyc server.
 
Method Summary
protected  java.util.ArrayList buildDomainPopulationRules(Solution solution, java.util.ArrayList variables)
          Builds a list of domain population rules from the given partial solution object.
protected  CycList buildSolutionConstraint(Solution solution)
          Builds a constraint expression from the given partial solution object.
 void displayConstraintRules()
          Displays the input constraint rules.
 void displayVariablesAndDomains()
          Displays the variables and their value domains.
 int getNbrConstraintRules()
          Returns the number of constraint ConstraintRule objects derived from the input problem.
 int getNbrDomainPopulationRules()
          Returns the number of variable domain populating ConstraintRule objects derived from the input problem.
 int getNbrVariables()
          Returns the number of Variable objects derived from the input problem.
protected static CycAccess initializeCycAccess()
          Creates a CycAccess object to connect to the OpenCyc server and provide api services.
 void setVerbosity(int verbosity)
          Sets verbosity of this object's output.
 java.util.ArrayList solve(CycList problem)
          Solves a constraint problem and return a list of solutions if one or more was found, otherwise returns null.
 java.util.ArrayList solve(java.lang.String problemString)
          Solves a constraint problem and return a list of solutions if one or more was found, otherwise returns null.
 java.util.ArrayList solveUsingPartialSolution(Solution solution, java.util.ArrayList variables, java.util.ArrayList constraintRules)
          Solves a constraint problem and return a list of solutions if one or more was found, otherwise returns null.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

valueDomains

protected ValueDomains valueDomains
ValueDomains object for this ConstraintProblem.

nodeConsistencyAchiever

protected NodeConsistencyAchiever nodeConsistencyAchiever
NodeConsistencyAchiever for this ConstraintProblem.

ruleEvaluator

protected RuleEvaluator ruleEvaluator
RuleEvaluator for this ConstraintProblem.

argumentTypeConstrainer

protected ArgumentTypeConstrainer argumentTypeConstrainer
ArgumentTypeConstrainer for this ConstraintProblem.

solution

protected Solution solution
Solution for this ConstraintProblem.

forwardCheckingSearcher

protected ForwardCheckingSearcher forwardCheckingSearcher
ForwardCheckingSearcher for this ConstraintProblem.

mt

public CycFort mt
The OpenCyc microtheory in which the constraint rules should be asked.

randomizeInput

public boolean randomizeInput
When true randomizes the order of the variables and domain values before beginning the search for a solution. Do this when tuning search heuristics to avoid bias for a particular order of input.

nbrSolutionsRequested

public java.lang.Integer nbrSolutionsRequested
The number of solutions requested. When null, all solutions are sought.

DEFAULT_VERBOSITY

public static final int DEFAULT_VERBOSITY
The default verbosity of this object's output. 0 --> quiet ... 9 -> maximum diagnostic input.

verbosity

protected int verbosity
Sets verbosity of this object's output. 0 --> quiet ... 9 -> maximum diagnostic input.

domainPopulationRules

protected java.util.ArrayList domainPopulationRules
Collection of the rules which populate variable domains.

constraintRules

protected java.util.ArrayList constraintRules
Collection of the constraint rules used in the search for solution(s).

simplifiedRules

protected java.util.ArrayList simplifiedRules
Collection of the simplified constraint rules derived from the input problem CycList. These include #$elementOf predicates which populate variable domains and then are discarded from the constraint rule set.

problemParser

protected ProblemParser problemParser
ProblemParser object for this ConstraintProblem.

variables

protected java.util.ArrayList variables
Collection of the constraint variables as CycVariable objects.

nbrAsks

protected int nbrAsks
Number of KB asks performed during the search for solution(s).

problem

protected CycList problem
The input problem CycList.
Constructor Detail

ConstraintProblem

public ConstraintProblem()
Constructs a new ConstraintProblem object, creating a new CycAccess object.

ConstraintProblem

public ConstraintProblem(CycAccess cycAccess)
Constructs a new ConstraintProblem object given an existing connection to the OpenCyc server.
Parameters:
cycAccess - the CycAccess object to use for this constraint problem
Method Detail

initializeCycAccess

protected static CycAccess initializeCycAccess()
Creates a CycAccess object to connect to the OpenCyc server and provide api services.
Returns:
a CycAccess object to connect to the OpenCyc server and provide api services

solveUsingPartialSolution

public java.util.ArrayList solveUsingPartialSolution(Solution solution,
                                                     java.util.ArrayList variables,
                                                     java.util.ArrayList constraintRules)
                                              throws java.io.IOException,
                                                     CycApiException
Solves a constraint problem and return a list of solutions if one or more was found, otherwise returns null.
Parameters:
solution - the partial solution
variables - the list of variables present in this constraint problem
constraintRules - a list of constraint rules to further restrict the partial solution.
Returns:
an ArrayList of solutions or null if no solutions were found. Each solution is an ArrayList of variable binding ArrayList objects, each binding having the form of an ArrayList where the first element is the CycVariable and the second element is the domain value Object.

buildDomainPopulationRules

protected java.util.ArrayList buildDomainPopulationRules(Solution solution,
                                                         java.util.ArrayList variables)
                                                  throws java.io.IOException,
                                                         CycApiException
Builds a list of domain population rules from the given partial solution object. (#$elementOf ?var1 (#$TheSet value1_1 ... value1_N)) ... (#$elementOf ?varM (#$TheSet valueM_1 ... valueM_N))
Parameters:
solution - the partial solution
variables - the list of variables present in this constraint problem
Returns:
solution constraint built from the given partial solution object

buildSolutionConstraint

protected CycList buildSolutionConstraint(Solution solution)
                                   throws java.io.IOException,
                                          CycApiException
Builds a constraint expression from the given partial solution object. (#$or (#$and (#$equals ?var1 value1_1) ... (#$equals ?varN value1_N)) ... (#$and (#$equals ?var1 valueM_1) ... (#$equals ?varN valueM_N)))
Parameters:
solution - a partial solution
Returns:
solution constraint built from the given partial solution object

solve

public java.util.ArrayList solve(java.lang.String problemString)
                          throws CycApiException
Solves a constraint problem and return a list of solutions if one or more was found, otherwise returns null.
Parameters:
problem - a constraint problem in the form of an OpenCyc query string
Returns:
an ArrayList of solutions or null if no solutions were found. Each solution is an ArrayList of variable binding ArrayList objects, each binding having the form of an ArrayList where the first element is the CycVariable and the second element is the domain value Object.

solve

public java.util.ArrayList solve(CycList problem)
Solves a constraint problem and return a list of solutions if one or more was found, otherwise returns null.
Parameters:
problem - a constraint problem in the form of an OpenCyc query CycList
Returns:
an ArrayList of solutions or null if no solutions were found. Each solution is an ArrayList of variable binding ArrayList objects, each binding having the form of an ArrayList where the first element is the CycVariable and the second element is the domain value Object.

getNbrDomainPopulationRules

public int getNbrDomainPopulationRules()
Returns the number of variable domain populating ConstraintRule objects derived from the input problem.
Returns:
the number of variable domain populating ConstraintRule objects.

getNbrConstraintRules

public int getNbrConstraintRules()
Returns the number of constraint ConstraintRule objects derived from the input problem.
Returns:
the number of constraint ConstraintRule objects.

getNbrVariables

public int getNbrVariables()
Returns the number of Variable objects derived from the input problem.
Returns:
the number of CycVariable objects.

displayConstraintRules

public void displayConstraintRules()
Displays the input constraint rules.

displayVariablesAndDomains

public void displayVariablesAndDomains()
Displays the variables and their value domains.

setVerbosity

public void setVerbosity(int verbosity)
Sets verbosity of this object's output. 0 --> quiet ... 9 -> maximum diagnostic input.
Parameters:
verbosity - 0 --> quiet ... 9 -> maximum diagnostic input