org.optimizationservices.oscommon.nonlinear
Class OSExpressionTree

java.lang.Object
  org.optimizationservices.oscommon.nonlinear.OSExpressionTree

public class OSExpressionTree
extends java.lang.Object

The OSExpressionTree class represents an expression tree for a nonlinear function (linear ones being special cases) and provide convenience methods to process the contained nonlinear function. In essence it contains the root node (of OSnLNode type) of an expression and hides all the internal nodes. It is the only public class that interfaces with any component (e.g. a solver) that needs to manipulate the nonlinear functions in an instance. For example, it is mainly used in the osilReader class to parse a nonlinear optimization instance.

Since:

OS 1.0

Version:

1.0, 03/14/2004

Author:

Robert Fourer, Jun Ma, Kipp Martin

See Also:

org.optimizationservices.oscommon.nonlinear.OSnLNode;, org.optimizationservices.oscommon.parser.OSiLReader;

Constructor Summary

OSExpressionTree()
Constructor.

OSExpressionTree(org.w3c.dom.Element expressionTreeRoot, org.w3c.dom.Element documentRoot)
Constructor

OSExpressionTree(java.util.Vector tokenizedExpression, java.lang.String type, int start, int end)
Constructor

Method Summary

double	calculateDerivative(double[] x, int index, boolean functionEvaluated) Calculate the function derivative value given the current variable values w.r.t one variable.
it.unimi.dsi.fastutil.ints.Int2DoubleOpenHashMap	calculateDerivatives(double[] x, boolean functionEvaluated) Calculate the function partial derivatives given the current variable values w.r.t all variables.
double	calculateFunction(double[] x) Calculate the function value of the expression tree.
double	calculateFunction(double[] x, boolean functionEvaluated) Calculate the expression tree function value given the current variable values.
java.lang.String	calculateFunction(java.lang.String[] x, boolean functionEvaluated) Calculate the expression tree function value given the current variable values.
it.unimi.dsi.fastutil.objects.Object2DoubleOpenHashMap	calculateHessian(double[] x, boolean derivativeEvaluated) Calculate the function Hessian given the current variable values w.r.t all variables.
OSExpressionTree	clone() clone an expression tree to a new copy.
void	concatenate(OSExpressionTree eTree)
static java.lang.String	getDelimiter()
double	getDerivative(int index) Get the expression tree function derivative value given the current variable values values w.r.t one variable.
it.unimi.dsi.fastutil.ints.Int2DoubleOpenHashMap	getDerivatives() Get the expression tree function derivatives given the current variable values w.r.t all variables.
org.w3c.dom.Element	getDomTreeRoot(org.w3c.dom.Document document)
java.lang.String	getDomTreeString(org.w3c.dom.Document document)
it.unimi.dsi.fastutil.objects.Object2DoubleOpenHashMap	getHessian() Calculate the function Hessian given the current variable values w.r.t all variables.
java.util.HashSet	getIdentifiers()
java.util.Vector<java.lang.String>	getInfix()
java.util.HashSet	getLogicAndRelationalSymbols()
java.util.HashSet	getNetworkArcs()
java.util.HashSet	getNetworkNodes()
static java.lang.String	getNlNodeInfo()
int	getNumberOfComplementsOperator()
int	getNumberOfProbabilityFunctions()
int	getNumberOfProbOperator()
int	getNumberOfStatisticFunctions()
int	getNumberOfTrigonometricFunctions()
java.util.HashSet	getNumberValues()
java.util.Vector<java.lang.String>	getPostfix()
java.util.Vector<java.lang.String>	getPrefix()
java.util.HashSet	getQuadraticTerms()
OSnLNode	getRootNode() Get the root node of the expression tree.
java.util.HashSet	getSimulationNames()
int	getSize()
java.util.HashSet	getUserFunctionNames()
it.unimi.dsi.fastutil.ints.IntOpenHashSet	getVariableIndices()
java.util.HashSet	getXPath()
it.unimi.dsi.fastutil.ints.Int2DoubleOpenHashMap	linearize() Linearize the current node so that it doesn't contain linear terms.
static void	main(java.lang.String[] argv) main for test purposes.
boolean	quadratize() Quadratize the current expression tree, or make all the quadratic terms written in the form of a quadratic node with its children being the quadratic terms.
boolean	reLabelVariableIndices(int[] newVariableIndices) relabel variable indices, e.g.
OSnLNode	setExpressionTree(org.w3c.dom.Element expressionTreeRoot) Set the expression tree with an XML element from an OSiL instance that represents a root node of the expression tree.
OSnLNode	setExpressionTreeFromInfix(java.util.Vector tokenizedExpression, int start, int end) Set the expression tree with from a tokenized string vector in infix format.
OSnLNode	setExpressionTreeFromPostfix(java.util.Vector tokenizedExpression, int start, int end) Set the expression tree with from a tokenized string vector in postfix format.
OSnLNode	setExpressionTreeFromPrefix(java.util.Vector tokenizedExpression, int start, int end) Set the expression tree with from a tokenized string vector in prefix format.
void	setGlobalDefinition(org.w3c.dom.Element documentRoot) Set global definitions such as defined userFunctions, simulations, xmlData etc that are used by all the expression trees.
void	setRootNode(OSnLNode treeRoot) Set the root node of the expression tree.
int	simplify() Simplify the current expression tree.

Methods inherited from class java.lang.Object

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

Constructor Detail

OSExpressionTree

public OSExpressionTree()

Constructor.

OSExpressionTree

public OSExpressionTree(org.w3c.dom.Element expressionTreeRoot,
                        org.w3c.dom.Element documentRoot)

Constructor

Parameters:

expressionTreeRoot - holds the XML element from an OSiL instance that represents a root node of the expression tree.

documentRoot - holds the XML element from an OSiL instance that represents a root node of the whole OSiL document. This root element of the document is necessary because some of the node in the expression tree can point to infomation outside of the expression tree, which cannot be accessed through expressionTreeRoot, but can be accessed through documentRoot.

OSExpressionTree

public OSExpressionTree(java.util.Vector tokenizedExpression,
                        java.lang.String type,
                        int start,
                        int end)

Constructor

Parameters:

tokenizedExpression - holds the expression tokenized in a string vector in either postfix, prefix, or infix. The operator name in each token has to be exactly the same as the name specified in the OSnL Schema. The operator name in the token may be followed (without space) by a sequence of ":atrributeValue" and end with [i] to indicate the number of arguments the operator can take if the operator's type is indefinite. The attributes specified have to follow the sequence in the OSnL schema. If one attribute is specified, all attributes have to be specified together. If an attribute is missing, an empty string has to be in place. Two alternative exception can be allowed for variable and number. A number can just a a numeric value and the variable can take the form Xi where i is the integer index of capital letter X.

type - holds whether the expression is in postfix, prefix or infix

start - holds the index of the tokenizedExpression to start processing.

end - holds the index of the tokenizedExpression to finish processing.

Method Detail

getRootNode

public OSnLNode getRootNode()

Get the root node of the expression tree.

Returns:

the treeRoot that holds the root node (of OSnLNode type) of the expression tree.

setRootNode

public void setRootNode(OSnLNode treeRoot)

Set the root node of the expression tree.

Parameters:

treeRoot - holds the root node (of OSnLNode type) of the expression tree.

clone

public OSExpressionTree clone()

clone an expression tree to a new copy.

Overrides:

clone in class java.lang.Object

Returns:

the cloned copy of the current OS expression tree.

setGlobalDefinition

public void setGlobalDefinition(org.w3c.dom.Element documentRoot)

Set global definitions such as defined userFunctions, simulations, xmlData etc that are used by all the expression trees.

Parameters:

documentRoot - holds the XML element from an OSiL instance that represents a root node of the whole OSiL document. This root element of the document is necessary because some of the node in the expression tree can point to infomation outside of the expression tree, which cannot be accessed through expressionTreeRoot, but can be accessed through documentRoot.

setExpressionTree

public OSnLNode setExpressionTree(org.w3c.dom.Element expressionTreeRoot)

Set the expression tree with an XML element from an OSiL instance that represents a root node of the expression tree.

Parameters:

expressionTreeRoot - holds the XML element from an OSiL instance that represents a root node of the expression tree.

setExpressionTreeFromPostfix

public OSnLNode setExpressionTreeFromPostfix(java.util.Vector tokenizedExpression,
                                             int start,
                                             int end)

Set the expression tree with from a tokenized string vector in postfix format.

Parameters:

tokenizedExpression - holds the expression tokenized in a string vector in postfix. The operator name in the token may be followed (without space) by a sequence of ":atrributeValue" and end with [i] to indicate the number of arguments the operator can take if the operator's type is indefinite. The attributes specified have to follow the sequence in the OSnL schema. If one attribute is specified, all attributes have to be specified together. If an attribute is missing, an empty string has to be in place. Two alternative exception can be allowed for variable and number. A number can just a a numeric value and the variable can take the form Xi where i is the integer index of capital letter X.

start - holds the index of the tokenizedExpression to start processing.

end - holds the index of the tokenizedExpression to finish processing.

setExpressionTreeFromPrefix

public OSnLNode setExpressionTreeFromPrefix(java.util.Vector tokenizedExpression,
                                            int start,
                                            int end)

Set the expression tree with from a tokenized string vector in prefix format.

Parameters:

tokenizedExpression - holds the expression tokenized in a string vector in prefix. The operator name in the token may be followed (without space) by a sequence of ":atrributeValue" and end with [i] to indicate the number of arguments the operator can take if the operator's type is indefinite. The attributes specified have to follow the sequence in the OSnL schema. If one attribute is specified, all attributes have to be specified together. If an attribute is missing, an empty string has to be in place. Two alternative exception can be allowed for variable and number. A number can just a a numeric value and the variable can take the form Xi where i is the integer index of capital letter X.

start - holds the index of the tokenizedExpression to start processing.

end - holds the index of the tokenizedExpression to finish processing.

setExpressionTreeFromInfix

public OSnLNode setExpressionTreeFromInfix(java.util.Vector tokenizedExpression,
                                           int start,
                                           int end)

Set the expression tree with from a tokenized string vector in infix format.

Parameters:

tokenizedExpression - holds the expression tokenized in a string vector in infix. The operator name in the token may be followed (without space) by a sequence of ":atrributeValue" and end with [i] to indicate the number of arguments the operator can take if the operator's type is indefinite. The attributes specified have to follow the sequence in the OSnL schema. If one attribute is specified, all attributes have to be specified together. If an attribute is missing, an empty string has to be in place. Two alternative exception can be allowed for variable and number. A number can just a a numeric value and the variable can take the form Xi where i is the integer index of capital letter X.

start - holds the index of the tokenizedExpression to start processing.

end - holds the index of the tokenizedExpression to finish processing.

concatenate

public void concatenate(OSExpressionTree eTree)

Parameters:

eTree - holds the expression tree to be concatenated (i.e. linked with an add operator) to the current expression.

getDelimiter

public static java.lang.String getDelimiter()

Returns:

the delimiter used in OSnLNode classes and expression trees.

getNlNodeInfo

public static java.lang.String getNlNodeInfo()

Returns:

the information of all nonlinear nodes in a colon delimited string. The string is in a table format with the first row being the colmn title.

calculateFunction

public double calculateFunction(double[] x)

Calculate the function value of the expression tree.

Parameters:

x - holds the values of the variables in a double array.

Returns:

the function value of the expression tree given the current variable values.

calculateFunction

public double calculateFunction(double[] x,
                                boolean functionEvaluated)

Calculate the expression tree function value given the current variable values. If the function has been evaluated over the current x values, the method will retrieve it.

Parameters:

x - holds the values of the variables in a double array.

functionEvaluated - holds whether the function has been evaluated.

Returns:

the expression function value given the current variable values.

calculateFunction

public java.lang.String calculateFunction(java.lang.String[] x,
                                          boolean functionEvaluated)

Calculate the expression tree function value given the current variable values. If the function has been evaluated over the current x values, the method will retrieve it.

Parameters:

x - holds the values of the variables in a string array.

functionEvaluated - holds whether the function has been evaluated.

Returns:

the expression tree function derivative value given the current variable values in a string.

calculateDerivative

public double calculateDerivative(double[] x,
                                  int index,
                                  boolean functionEvaluated)

Calculate the function derivative value given the current variable values w.r.t one variable. If the function has been evaluated over the current x values, the method will retrieve it.

Parameters:

x - holds the values of the variables in a double array.

index - holds the variable index on which to take the derivative.

functionEvaluated - holds whether the function has been evaluated.

Returns:

the expression tree function derivative given the current variable values w.r.t the specified variable.

getDerivative

public double getDerivative(int index)

Get the expression tree function derivative value given the current variable values values w.r.t one variable. This method assumes that the derivative has already been calculated over the current variable values.

Parameters:

index - holds the variable index on which to get the derivative.

Returns:

the expression tree function derivative value of the current variable values assuming that the derivative has already been calculated over the current variable values w.r.t the specified variable.

calculateDerivatives

public it.unimi.dsi.fastutil.ints.Int2DoubleOpenHashMap calculateDerivatives(double[] x,
                                                                             boolean functionEvaluated)

Calculate the function partial derivatives given the current variable values w.r.t all variables. If the function has been evaluated over the current x values, the method will retrieve it.

Parameters:

x - holds the values of the variables in a double array.

functionEvaluated - holds whether the function has been evaluated.

Returns:

a hashmap of the nonzero function derivative values given the current variable values. The map keys are variable indexes, and the map values are nonzero derivatives.

getDerivatives

public it.unimi.dsi.fastutil.ints.Int2DoubleOpenHashMap getDerivatives()

Get the expression tree function derivatives given the current variable values w.r.t all variables. This method assumes that the derivatives have already been calculated over the current variable values.

Returns:

a hashmap of the nonzero function derivative values given the current variable values. The map keys are variable indexes, and the map values are nonzero derivatives. This method assumes that the derivative values have already been calculated over the current variable values w.r.t all variables.

calculateHessian

public it.unimi.dsi.fastutil.objects.Object2DoubleOpenHashMap calculateHessian(double[] x,
                                                                               boolean derivativeEvaluated)

Calculate the function Hessian given the current variable values w.r.t all variables.

Parameters:

x - holds the values of the variables in a double array.

derivativeEvaluated - holds whether the function derivatives have been evaluated.

Returns:

a sparse hash map of the upper triangular (i<=j) non-zero second partial derivatives w.r.t to variable i and then j, given the current variable values. The map keys are the strings of variable indexes delimited by a comma, i.e. "i,j" and the map values are the Hessian values.

getHessian

public it.unimi.dsi.fastutil.objects.Object2DoubleOpenHashMap getHessian()

Calculate the function Hessian given the current variable values w.r.t all variables.

Returns:

a sparse hash map of the upper triangular non-zero second partial derivatives w.r.t to variable i and then j, given the current variable values. The map keys are the strings of variable indexes delimited by a comma, i.e. "i,j" and the map values are the Hessian values.

getPostfix

public java.util.Vector<java.lang.String> getPostfix()

Returns:

the expression tree in a postfix vector of operator symbols.

getPrefix

public java.util.Vector<java.lang.String> getPrefix()

Returns:

the expression tree in a prefix vector of operator symbols.

getInfix

public java.util.Vector<java.lang.String> getInfix()

Returns:

the expression tree in a infix vector of operator symbols.

getDomTreeRoot

public org.w3c.dom.Element getDomTreeRoot(org.w3c.dom.Document document)

Parameters:

document - holds the W3C DOM type document to create XML elements and attributes. It is the parent of the root element, e.g. the <OSiL> element in OSiL. It is used to create all the nodes in the DOM tree.

Returns:

the nonlinear expression starting with the root node in an XML DOM Tree.

getDomTreeString

public java.lang.String getDomTreeString(org.w3c.dom.Document document)

Parameters:

document - holds the W3C DOM type document to create XML elements and attributes. It is the parent of the root element, e.g. the <OSiL> element in OSiL. It is used to create all the nodes in the DOM tree.

Returns:

the nonlinear expression string representation starting with the root node in an XML DOM Tree.

reLabelVariableIndices

public boolean reLabelVariableIndices(int[] newVariableIndices)

relabel variable indices, e.g. X0 -> X2; X1 -> X0; X2 -> X1.

Parameters:

newVariableIndices - holds the new varialbe indices. For the example above it would be [2, 0, 1].

Returns:

whether the relabeling is successful or not.

simplify

public int simplify()

Simplify the current expression tree. Also simplify the variables by converting number*variable into just a variable with the number as a coefficient of the varialbe.

Returns:

the reduction size, i.e. the number of nodes taken out of the original expression tree. If 0, the nonlinear function is already the simplest.

linearize

public it.unimi.dsi.fastutil.ints.Int2DoubleOpenHashMap linearize()

Linearize the current node so that it doesn't contain linear terms. The expression tree of the node will become smaller if there are linear terms. If the node is fully linear, the node becomes null. If the node is not linear at all, it will remain the same and the returned hash map has a size zero.

Returns:

a hashmap of linear terms extracted out from this expression tree, with keys being the variable indices and values being the variable coefficients.

quadratize

public boolean quadratize()

Quadratize the current expression tree, or make all the quadratic terms written in the form of a quadratic node with its children being the quadratic terms.

Returns:

whether there is conversion of some quadratic terms.

getVariableIndices

public it.unimi.dsi.fastutil.ints.IntOpenHashSet getVariableIndices()

Returns:

an integer set of indices of the variables that exist in the current nonlinear expression tree.

getSize

public int getSize()

Returns:

the tree size, i.e. the number of nodes, of the expression tree.

getNumberOfTrigonometricFunctions

public int getNumberOfTrigonometricFunctions()

Returns:

the number of trigonometric functions in the expression tree.

getNumberOfStatisticFunctions

public int getNumberOfStatisticFunctions()

Returns:

the number of statistic functions in the expression tree.

getNumberOfProbabilityFunctions

public int getNumberOfProbabilityFunctions()

Returns:

the number of probability functions in the expression tree.

getNumberValues

public java.util.HashSet getNumberValues()

Returns:

a set of number values that exist in the expression tree.

getIdentifiers

public java.util.HashSet getIdentifiers()

Returns:

a set of names of identifiers that exist in the expression tree.

getLogicAndRelationalSymbols

public java.util.HashSet getLogicAndRelationalSymbols()

Returns:

a set of logic and relational operator symbols that exist in the expression tree.

getQuadraticTerms

public java.util.HashSet getQuadraticTerms()

Returns:

a set of quadratic terms that exist in the expression tree.

getSimulationNames

public java.util.HashSet getSimulationNames()

Returns:

a set of names of the simulations that exist in the expression tree.

getUserFunctionNames

public java.util.HashSet getUserFunctionNames()

Returns:

a set of names of the user defined functions that exist in the expression tree.

getXPath

public java.util.HashSet getXPath()

Returns:

a set of XPaths that exist in the expression tree, each set member is of the form: uri:path, that is uri and path delimited by :.

getNetworkNodes

public java.util.HashSet getNetworkNodes()

Returns:

a set of network nodes that are referred in the expression tree, each set member is of the form: nodeName:propertyName, that is nodeName and property name delimited :.

getNetworkArcs

public java.util.HashSet getNetworkArcs()

Returns:

a set of network arcs that are referred in the expression tree, each set member is of the form: arcName:propertyName, that is arcName and property name delimited :.

getNumberOfComplementsOperator

public int getNumberOfComplementsOperator()

Returns:

the number of the complements operator in the expression tree.

getNumberOfProbOperator

public int getNumberOfProbOperator()

Returns:

the number of the probability operator (usually in a chance constraint) in the expression tree.

main

public static void main(java.lang.String[] argv)

main for test purposes.

Parameters:

argv - command line arguments.