omnics
Class Problem

java.lang.Object
  omnics.Problem

All Implemented Interfaces:

java.io.Serializable

Direct Known Subclasses:

ColoringProblem, Graceful, LatinSquareProblem, MagicSquareProblem, QueenProblem, SendMoreMoney, StillLifeProblem

public class Problem
extends java.lang.Object
implements java.io.Serializable

Represents a constraint satisfaction problem. Constraint satisfaction problems are used to represent any type of situation where it is necessary to find a state for some objects that satifies a given set of restrictions, called constraints. The objects of the initial problem are modelled as variables having specified domains and a solution is an assignment of these variables with values from their domains that does not violate any constraint. Formally, such a problem will be represented as a constrained network. A constraint network is a triplet (X,D,C) where:

• X = {x1, ..., xn} is a set of variables
• D = {D1, ...,Dn} is a set of finite domains; a variable xi can only be assigned values from Di, i = 1,n;
• C = {C1, ...,Ct} is a set of constraints

There are no assumptions on the types of the variables: they can be integer, boolean, sets or anything else and there are no assumptions regarding the definition of the constraints: they can be represented as the underlying relation of permitted values or as a function defined on a set of variables and returning true or false as a result.

Author:

Cristian Frasinaru

See Also:

Var, Domain, Constraint, Serialized Form

Field Summary

protected ConstraintSet	constraints
protected java.lang.String	description
static int	INCONSISTENT
protected java.lang.String	name
protected int	optimum
static int	SIMPLE
static int	SOLVED
protected Solver	solver
static int	UNKNOWN
protected ValuationStructure	valuation
protected VarSet	variables

Constructor Summary

Problem()
Creates a new instance of Problem, having no name.

Problem(java.lang.String name)
Creates a new instance of Problem, having a specified name.

Method Summary

void	addConstraint(Constraint constraint) Adds a new constraint to the problem.
int	addVariable(Var var) Adds a variable to the problem.
SystematicSolver	createSolver() Creates and sets a default solver for this problem.
SystematicSolver	createSolver(java.lang.String filename) Creates and sets a solver for this problem, whose state is retrieved from an external file.
Var[]	createVariables(int n) Creates and returns n variables for this problem having no domain (the domain of each variable is null).
Var[]	createVariables(int n, Domain domain) Creates and returns n variables for this problem.
ConstraintSet	getConstraints() Gets a reference to the collection of constraints of this problem.
ConstraintSet	getConstraints(VarSet someVars) Creates and returns a set of constraints which are defined on variables containing one or more of the variables received as argument.
java.lang.String	getDescription() Gets the description of this problem.
java.lang.String	getName() Gets the name of this problem.
int	getOptimum() Gets the known optimum of this problem.
Solver	getSolver() Gets the solver which was associated to this problem.
ValuationStructure	getValuationStructure() Gets the valuation structure of this problem.
Var[]	getVarArray() Creates and returns an array (Var[]) containing the variables of the problem.
VarSet	getVariables() Gets a reference to the collection of variables of this problem.
VarSet	getVariables(Var var) Creates and returns a VarSet consisting of the variables of the problem which participate, together with the argument variable, in some constraint of the problem (we say that these variables depend on each other).
void	reduce() Attempts to reduce the problem, eliminating all values that are not good.
void	removeConstraint(Constraint constraint) Removes a constraint from the problem.
void	removeConstraints(ConstraintSet constraintSet) Removes a set of constraints from the problem.
void	removeVariable(Var var) Removes a variable from the problem.
void	removeVariables(VarSet vars) Removes a set of variables from the problem.
long	searchSpaceSize() Computes the size of the problem search space.
void	setConstraints(Constraint... constraints) Sets the constraints of the problem, copying the constraints given as parameters in a ConstraintSet.
void	setConstraints(ConstraintSet constraints) Sets the constraints of the problem.
void	setDescription(java.lang.String description) Sets the description of this problem.
void	setName(java.lang.String name) Sets the name of this problem.
void	setOptimum(int optimum) Sets the known optimum of this problem.
protected void	setSolver(Solver solver) Sets a solver to this problem.
void	setValuationStructure(ValuationStructure valuation) Sets the valuation structure of this problem.
void	setVariables(Var... vars) Sets the variables of the problem, copying the variables given as parameters in a VarSet.
void	setVariables(VarSet variables) Sets the variables of the problem.
int	size() Returns the size of the problem, i.e.
void	sortVariables(java.util.Comparator<Var> comparator) Sorts the variable according to a comparator.
java.lang.String	toString() Gets a string representation of this problem.
Var	variable(int index) Returns the variable having the specified index.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

name

protected java.lang.String name

description

protected java.lang.String description

variables

protected VarSet variables

constraints

protected ConstraintSet constraints

valuation

protected ValuationStructure valuation

solver

protected Solver solver

optimum

protected int optimum

UNKNOWN

public static final int UNKNOWN

See Also:

Constant Field Values

SIMPLE

public static final int SIMPLE

See Also:

Constant Field Values

SOLVED

public static final int SOLVED

See Also:

Constant Field Values

INCONSISTENT

public static final int INCONSISTENT

See Also:

Constant Field Values

Constructor Detail

Problem

public Problem()

Creates a new instance of Problem, having no name.

Problem

public Problem(java.lang.String name)

Creates a new instance of Problem, having a specified name.

Parameters:

name - the name of the problem

Method Detail

getName

public java.lang.String getName()

Gets the name of this problem.

Returns:

the problem's name, or null if the problem has no name.

setName

public void setName(java.lang.String name)

Sets the name of this problem.

Parameters:

name - the name of the problem

getDescription

public java.lang.String getDescription()

Gets the description of this problem.

Returns:

the problem's description, or null if the problem has no description.

setDescription

public void setDescription(java.lang.String description)

Sets the description of this problem.

Parameters:

description - the description of the problem

getVariables

public VarSet getVariables()

Gets a reference to the collection of variables of this problem. The variables of a problem are represented as a VarSet.

Returns:

a reference to the VarSet representing the variables

getVariables

public VarSet getVariables(Var var)

Creates and returns a VarSet consisting of the variables of the problem which participate, together with the argument variable, in some constraint of the problem (we say that these variables depend on each other).

Parameters:

var - a variable of the problem

Returns:

the set of variables dependent on the argument variable

getVarArray

public Var[] getVarArray()

Creates and returns an array (Var[]) containing the variables of the problem. If there are no variable, the array will be empty.

Returns:

an array containing the variables of the problem

setVariables

public void setVariables(VarSet variables)

Sets the variables of the problem. The variables of the problem are represented as an instance of VarSet. The method stores the reference and does not create a copy of the corresponding object.

Parameters:

variables - a set of variables

See Also:

VarSet

setVariables

public void setVariables(Var... vars)

Sets the variables of the problem, copying the variables given as parameters in a VarSet.

Parameters:

vars - an array of variables

createVariables

public Var[] createVariables(int n,
                             Domain domain)

Creates and returns n variables for this problem. The domain of each variable will be a copy of the given domain. The variables are set for the problem and are also returned as an array.

Parameters:

n - the number of variables to be created

domain - the domain which will be set for each variable

Returns:

an array of the problem's variables

See Also:

Domain

createVariables

public Var[] createVariables(int n)

Creates and returns n variables for this problem having no domain (the domain of each variable is null). The variables are set for the problem and are also returned as an array.

Parameters:

n - the number of variables to be created

Returns:

an array of the problem's variables

variable

public Var variable(int index)

Returns the variable having the specified index.

Parameters:

index - index of the variable to return

Returns:

the variable at the specified index

addVariable

public int addVariable(Var var)

Adds a variable to the problem. The variable is informed that it belongs to this problem. The index of the added variable is size() - 1.

Parameters:

var - the variable to be added

Returns:

the index of the added variable

removeVariable

public void removeVariable(Var var)

Removes a variable from the problem. All the constraints that use these variable will be also removed. The remaining variables are reindexed, so the variables indices are always from 0 to size()-1.

Parameters:

var - the variable to be removed

removeVariables

public void removeVariables(VarSet vars)

Removes a set of variables from the problem. All the constraints that use these variables will be also removed. The remaining variables are reindexed, so the variables indices are always from 0 to size()-1.

Parameters:

vars - the variables to be removed

size

public int size()

Returns the size of the problem, i.e. the number of its variables.

Returns:

the size of the problem

getConstraints

public ConstraintSet getConstraints()

Gets a reference to the collection of constraints of this problem. The constraints of a problem are represented as a ConstraintSet.

Returns:

a reference to the ConstraintSet representing the constraints

getConstraints

public ConstraintSet getConstraints(VarSet someVars)

Creates and returns a set of constraints which are defined on variables containing one or more of the variables received as argument.

Parameters:

someVars - a set of variables

Returns:

the set of constraints which use at least one of the given variables

setConstraints

public void setConstraints(ConstraintSet constraints)

Sets the constraints of the problem. The constraints of the problem are represented as an instance of ConstraintSet. The method stores the reference and does not create a copy of the corresponding object.

Parameters:

constraints - a set of constraints

setConstraints

public void setConstraints(Constraint... constraints)

Sets the constraints of the problem, copying the constraints given as parameters in a ConstraintSet.

Parameters:

constraints - an array of constraints

addConstraint

public void addConstraint(Constraint constraint)

Adds a new constraint to the problem. The constraint is informed that it belongs to this problem. Each variable of the constraint is informed that it is involved in this constraint.

Parameters:

constraint - the constraint to be added

removeConstraint

public void removeConstraint(Constraint constraint)

Removes a constraint from the problem.

Parameters:

constraint - the constraint to be removed

removeConstraints

public void removeConstraints(ConstraintSet constraintSet)

Removes a set of constraints from the problem. All the constraints that use these variables will be also removed. The remaining variables are reindexed, so the variables indices are always from 0 to size()-1.

Parameters:

constraintSet - the variables to be removed

searchSpaceSize

public long searchSpaceSize()

Computes the size of the problem search space. |D_1| * |D_2| * ... * |D_n|

getValuationStructure

public ValuationStructure getValuationStructure()

Gets the valuation structure of this problem.

Returns:

the valuation structure of this problem.

See Also:

ValuationStructure

setValuationStructure

public void setValuationStructure(ValuationStructure valuation)

Sets the valuation structure of this problem.

Parameters:

valuation - the valuation structure to be used

See Also:

ValuationStructure

getSolver

public Solver getSolver()

Gets the solver which was associated to this problem.

Returns:

the solver associated to this problem or null if the problems has no solver.

See Also:

Solver

setSolver

protected void setSolver(Solver solver)

Sets a solver to this problem.

Parameters:

solver - the solver which will be used to solve this problem

See Also:

Solver

createSolver

public SystematicSolver createSolver()

Creates and sets a default solver for this problem. The default solver is an instance of Backtracking.

Returns:

a Backtracking solver associated to this problem

See Also:

Backtracking

createSolver

public SystematicSolver createSolver(java.lang.String filename)

Creates and sets a solver for this problem, whose state is retrieved from an external file. This method is used when we need to resume the execution of a previously interrupted solver.

Parameters:

filename - a file containing the serialized state of a solver

Returns:

a solver constructed from the serialized state or null if the creation of the solver fails

getOptimum

public int getOptimum()

Gets the known optimum of this problem. By default, the optimum is ValuationStructure.MAX, meaning no information is available about the problem's optimum.

Returns:

the known optimum of this problem

setOptimum

public void setOptimum(int optimum)

Sets the known optimum of this problem. By default, the optimum is ValuationStructure.MAX, meaning no information is available about the problem's optimum. This value is used as an initial upper bound in the optimization problems.

Parameters:

optimum - a value between ValuationStructure.MIN and ValuationStructure.MAX representing the known optimum

Throws:

IllegalArgumentException - if the value is not in the specified interval.

reduce

public void reduce()

Attempts to reduce the problem, eliminating all values that are not good.

toString

public java.lang.String toString()

Gets a string representation of this problem.

Overrides:

toString in class java.lang.Object

Returns:

a string representation of this problem

sortVariables

public void sortVariables(java.util.Comparator<Var> comparator)

Sorts the variable according to a comparator. After the variables have been sorted they are reindexed, to ensure that each variable's index is the same as its position in the VarSet containing the problem's variables.

Parameters:

comparator - a comparator for variables