 |
|
|
|
|
|
|
|
|
|
 |
||||
|
|
|||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
Optimization Services nonlinear Language (OSnL) Click to see or download the OSnL XML Schema -> OSnL.xsd [stable] OSnL (nonlinear) contains definitions of all the nonlinear, combinatorial, and other nodes (e.g. operators, operands, etc.) used in other OSxL's, mainly OSiL. In keeping with the philosophy of separating out the linear and nonlinear parts of an optimization instance, the nonlinear expressions in an instance are defined using the OSnL schema. OSnL itself is not a nonlinear program instance representation. Remember, all types of optimization instances are described using OSiL. More appropriately OSnL should be interpreted as Optimization Services nonlinear node Language. OSnL defines nonlinear nodes and nodes only. The nodes can be operators, functions or terminal operands. Operators always have child nodes. Function may or may not have child nodes. Terminal operands do not have children. Examples of terminal nodes are the number node and constant nodes such as PI and E. OSnL is then included in the OSiL schema to support nonlinear instance representation in OSiL. The way OSiL uses OSnL is through the use of a sequence of 0 or more <nl>; each <nl> element has an only child OSnLNode as an expression tree root to define a nonlinear function. This is described in detail in the OSiL paper. For a nonlinear expression, we use an expression tree and view every node in the expression tree as a generic node, which we call “OSnLNode.” Each OSnLNode can have 0 or more OSnLNode children. A terminal node is just an OSnLNode without children. To represent a generic node, at the beginning of the OSnL schema, we create a complex type OSnLNode: <xs:complexType name="OSnLNode" mixed="false"> The annotation element is just an XML schema comment. Next we create a substitution group based on the named element OSnLNode, which is of the above type OSnLNode. <xs:element name="OSnLNode" type="OSnLNode" abstract="true"> So we can think of OSnLNode as a derived class. Note the abstract attribute is set to the value of true in order to create the abstract class. Now with the substitution group defined, throughout the rest of the OSnL schema, we create concrete OSnLNode elements that are in the substitution group for OSnLNode. For example, the first concrete element we define is an OSnLNode for addition: <xs:complexType name="OSnLNodePlus"> We first define the complex type OSnLNodePlus and we then create the derived element plus that is in the substitution group OSnLNode. Note that the plus element requires exactly two child elements (<xs:sequence minOccurs="2" maxOccurs="2">), both of which should be in the OSnLNode substitution group too (<xs:element ref="OSnLNode"/>). In a similar fashion, we define all other OSnL nodes such as minus, divide, arcsin, sum, E, var, leq, if, complements, xPath, userF, quadratic. For nodes such as sum, as the sum operator is an indefinite type, the corresponding OSnLNodeSum requires one or more child elements: <xs:complexType name="OSnLNodeSum"> For nodes such as E, as E is a constant, the corresponding OSnLNodeE has no children: <xs:complexType name="OSnLNodeE"> The recursive design provides a significantly simple and powerful way to construct a nonlinear expression. When a concrete expression tree is finally constructed, it may look like: <sum> for the nonlinear expression The OSnL schema is very compressive; over 200 elements are supported. They fall broadly into the following 8 categories:
In the following table, we list the arithmetic operator elements.
“Child #” indicates the number of OSnLNode children that an element can take as operands. Elements with 1 operand are of unary type. Elements with 2 operands are of binary type. Elments with n (n>2) operands are of n-nary type. Some of the subsequent element types have n-nary functions. Elements such as sum and product are of indefinite types. As useful as the validation concept is, validation is about syntax not semantics. For example, the OSnL schema can make sure there are exactly 2 child elements for the <divide> element, but the schema cannot make sure the second child evaluates to a non-zero. Similarly the schema does not check whether the child elements of the integer-based quotient and rem operators evaluate to integers. These require additional checking and interpretation on the part of a parser. In the following table, we list the elementary function elements.
Most of the elementary functions are self-explanatory. The round function takes 2 children. The first child is the number to be rounded. The second child is the number of digits to round; a negative number rounds to the left of the decimal point; zero to the nearest integer. The truncate function truncates a number to an integer by removing the fractional part of the number. It takes 2 children. The first child is the number to be truncated. The second child indicates truncation precision; negative number truncates to the left of the decimal point; zero to the nearest integer. The rand function takes 1 child as a seed. It returns a random number from a continuous uniform distribution All the 24 standard trigonometric functions are defined in OSnL.
A trigonometric function takes one and only one child. 4. Statistical and probability functions In the following table, we list the statistical function elements that take one list of data, and hence are of indefinite types.
Each entry in the data list corresponds to a child node. The parameters (if any) of a statistical function go before the data list children. For example the large function takes a number n as its first child to indicate the nth largest number in the rest of the children. Most of the statistical functions are self-explanatory. The trimMean function takes 2 or more children. The first child is a number ( In the following table, we list the statistical function elements that take two data lists as operands.
Each entry in the 2 data lists corresponds to a child node. The parameters (if any) of a statistical function go before the data list children. After the parameter children, there should be even number of the rest of the children; the first half of these children corresponds to the first data list; the second half of these children corresponds to the second data list. In the following table, we list the probability function elements. Almost all probability functions can have three versions: density, cumulative, and inverse; child arguments for the three versions are exactly the same. An OSnL element is created for each version (if there is one). Density type elements are suffixed with “Dist”, cumulative type elements are suffixed with “Cum”, and inverse type elements are suffixed with “Inv.”
All the probability functions and related parameters are quite standard; they are named to be indicative of what are used in common practice. The last child (or last two in bivariate cases) always evaluates to a number that corresponds to the distribution function variable (or variables). The parameters of a probability function (if any) go before the variable child (or children). In the following table, we list the terminal elements, which do not have children.
The number schema is shown below: <xs:complexType name="OSnLNodeNumber"> The <number> element has three optional attributes value, type, and id. The value attribute is required and is of string type. The type attribute is optional and can take on a value of either real (default), string, or random. A “string-valued” number is often used in constraint programming. A “random” number is often used in stochastic programming and in this case the value attribute of number can either be treated as an initial value or ignored. The id attribute is optional. But if there is one, it has to be unique as it of type ID. A number with an id can be located. For example, in stochastic programming, we may need to change the number to different values in different scenarios. For example, all the following are valid number elements: <number value="100"/> The identifier schema is shown below: <xs:complexType name="OSnLNodeIdentifier"> The <identifier> element has one required name attribute. It is seldom used in numerical optimization. It can potentially be used for symbolic optimization. The following is an example of an identifier element: <identifer name="a"/> A variable is not always a terminal node, as it may take a child operand as its index. This is explained later. In the following table, we list the constant elements, which do not have children.
Most of these constants are well supported in various programming languages. So parser implementation can leverage on the support from the programming languages. TRUE and FALSE are not double values, but parsers may for example choose to use a positive number to represent TRUE and a negative number to represent FALSE. 6. Optimization related elements In the following table, we list the three optimization related elements.
The var element schema is shown below: <xs:complexType name="OSnLNodeVar"> <var> has two optional attributes, idx and coef. The idx attribute is nonnegative and if it’s not there, an optional child can be used to evaluate to the variable index. This can be useful in, for example, constraint programming in which a variable’s index can sometimes be an integer-valued variable or expression. The coef attribute is designed as a shorthand to avoid explicitly expressing a constant times a variable, which appears frequently in optimization. By default, coef is 1. For example, all the following are valid variable elements: X[0]: <var idx="0"/> The objective element schema is shown below: <xs:complexType name="OSnLNodeObjective"> <objective> has one optional attribute idx; idx is negative and by default -1, which corresponds to the first objective. The element evaluates to the objective value corresponding to the index. Like the var element, an optional child can be used to evaluate to the objective index. The following is an example of an objective element: <objective idx="-1"/> The Constraint element schema is shown below: <xs:complexType name="OSnLNodeConstraint"> The <constraint> element has two optional attributes idx, and valueType. The idx attribute is nonnegative. Like the var and objective elements, an optional child can be used to evaluate to the constraint index. The value of the valueType attribute can be either of “value” (default), “status” (whether the constraint is satisfied, a boolean), “surplus” ( <constraint idx="2"/> 7. Logic and relational operators In the following table, we list the standard logic and relational operator elements.
In the following table 6‑13, we list the extended logic and relational operator elements.
For instance, the first example (forAll) in the table: <forAll> means that the forAll operator is true if constanint 0 and constraint 1 are both true, and one of the constraints, constraint 3 or constraint 4, is true. All of the extended logic and relational operators are explained with an example in the above table. Most of these are used in combinatorial and discrete optimization such as constraint programming. Potentially more logic and relational operators will be added, especially the set-valued operators. In the following table, we list the special elements.
Unlike most of the previous elements, many of these special elements have complex attributes and indefinite number of children. The special elements are described below. Several elements are explained using the Markowitz optimization problem in using a three stock instance where Xi represents the percentage of the portfolio invested in stock i. Assume the portfolio is re-balanced when returns and covariances are updated.
The <quadratic> and <qpTerm> schemas are shown below: <xs:complexType name="OSnLNodeQuadratic"> <xs:complexType name="OSnLNodeQpTerm"> Although the instance of any quadratic program is easily represented as a general nonlinear program using OSnLNode elements, a more compact representation is provided for quadratic terms. A <qpTerm> element is used to represent each quadratic term. The <quadratic> element sums up all its <qpTerm> child elements. The <qpTerm> element has two required integer attributes (idxOne, indxTwo) that specify the two variable indices in the quadratic term. The coefficient of the quadratic term is specified using either a third optional double attribute coef or by a single child element. One advantage of using the <qpTerm> elements is that quadratic programming solvers typically take coefficient lists rather than nonlinear expressions. An added advantage is that if an analyzer applied to the problem instance discovers that the only nonlinear terms are <quadratic> and <qpTerm> terms, it can classify the problem as a quadratic program. Suppose in the instance representation of the above Markowitz optimization example, the variable index for X[msfg] is 0, for X[pg] is 1, and for X[ge] is 2. The objective function is represented as <quadratic> Often a problem instance has an expression that is repeated numerous times. As in programming, where a method (subroutine) simplifies repeated logic, the <userF> element is used to simplify instance representation by calling a pre-defined user function. Consider the constraint set (3)-(5) of the above Markowitz optimization example. These constraints require that if a nonzero investment is made in stock i, then at least 10% of the portfolio must be invested in stock i. Rather than repeat the same logic for each stock, it is much cleaner to first write the logic only once in a user defined function: [minInv(arg0) = if (arg0 > 0) then arg0 - .1 else 0], where arg0 is to be passed a value of Xi. User functions are defined in OSiL though the <userFunction> element in OSiL. The representation for the minInv function looks like: <userFunction name="minInv" numArg="1"> The <userF> and <arg> schemas are shown below: <xs:complexType name="OSnLNodeUserF"> <xs:complexType name="OSnLNodeArg"> The definition of the user function should be independent of the optimization problem instance represented by the OSiL instance; thus it is required that the user function definition use the <arg> elements instead of the math program variables <var> elements. The <arg> element has one required index attribute (idx) which is a nonnegative number. The numArg attribute of userFunction is used to check that all the argument indexes are >=0 and <=numArg-1. Now with the minInv user function definition, we can write constraint set (3)-(5) of the above Markowitz optimization problem using the <userF> element as: <nl idx="2"> In this example, the <userF> element’s required attribute name is minInv. <userF> can take 0 or more children as function arguments to pass. Here, we only have one argument which is <var idx="…"/>. In some optimization problems there may not be a closed form expression for all functions – they may be black boxes. This case is handled by the <sim> element. A simulation is similar to a user function, only that there is no longer a closed-form that can be expressed; three things have to be specified for the simulation: input, output, and the simulation’s address. The simulation definition, like the user function definition is specified in OSiL. Suppose the above minInv user function is now calculated by a simulation called stockSimulation shown in the following figure.
There are two inputs of the simulation service: ticker for the stock symbol and amount for the percentage of the stock in the portfolio. Notice the stockSimulation engine provides more “services” than just calculating the minimum investment. It can look up a stock price according to a stock ticker (a string). It also outputs the day of the week (no input needed for this function). So it has three outputs: mininv, price and day. The stockSimulation element is then be represented using the <simulation> element in OSiL as <simulation name="stockSimulation"> The format of the OSsL child is described in detail in the OSsL page . It contains information about inputs and outputs. Note that simulations generally refer to inputs and outputs by name rather than by order. The <sim>, <simInput>, and <simOutput> schemas are shown below: <xs:complexType name="OSnLNodeSim"> <xs:complexType name="OSnLNodeSimInput"> <xs:element name="simInput" type="OSnLNodeSimInput" substitutionGroup="OSnLNode"/> <xs:complexType name="OSnLNodeSimOutput"> <xs:element name="simOutput" type="OSnLNodeSimOutput" substitutionGroup="OSnLNode"/> Now with the stockSimulation definition, we can write constraint set (3)-(5) of the above Markowitz problem using the <sim> element as: <nl idx="2"> In this example, the <sim> element’s required attribute name is stockSimulation. <sim> can take 0 or more <simInput> child elements, followed by one required <simOutput> child element because we must have one output value to further calculate an objective or constraint function value. So <sim> always has at least one child. Here, we only have one <simInput> element which is <var idx="…"/>. Each <simInput> element has a required inputName attribute, which refers to an input defined in the corresponding <simulation> definition. Each <simInput> element also has an optional simName attribute. If the attribute is not there, as in the above example, it defaults to the name of the parent <sim> element. So in the above example we can also write <simInput simName=”stockSimulation” inputName="amount"> with an explicit simName attribute. The same rule applies to the <simOutput> element. <simInput> can have an optional child that evaluates to an input value and <simOutput> can have an optional child that evaluates to an output value. If the child is not there, <simInput> or <simOutput> takes the value from the OSsL element (<el>) with the same input or output name. In our example <simOutput> is a taker. If there is a child of <simInput>, it supplies the value to the OSsL element with the same input name. In our example <simInput> is a supplier. If there is a child of <simOutput>, it constructs a new value from the OSsL elements. Of course the example is somewhat simplified. The child element of <simInput> can be more complex than just one single <var> node. In reality, the child can be a more complex expression tree with many nodes. Also <simOutput> may not just directly take the minInv output value. For example we can say if the day output from stockSimulation is 1 (Monday), we want to add a fixed amount (say 0.05) to the minimum investment requirement for the stock ge. This corresponds to constraint (4). So constraint (4) now looks like: <nl idx="4"> Here <simOutput> constructs a new output. That is why, unlike <simInput> whose inputName attribute is required, the outputName attribute of <simOutput> is optional. Such a construction can be commonly used in optimization via stochastic simulation, where the simulation usually outputs a variance value as well as a mean value, and the optimization uses some combination of both the mean and the variance. In practice, problem parameters are often dynamic over time. If the value of a parameter changes, a new instance must be created using the modeling language. These problems are eliminated using <xPath> and <xPathIndex> elements. By allowing xPath nodes in an OSiL instance representation it is possible to reference data in an external XML data file. Thus a modeler, in a distributed environment, can generate a model, send it to the server, and the server can operate with current data without the necessity of the modeling language creating a new instance file. The <xPath> and <xPathIndex> schemas are shown below: <xs:complexType name="OSnLNodeXPath"> <xs:complexType name="OSnLNodeXPathIndex"> The <xPath> element has an optional uri attribute which specifies where the XML data file is. It is by default “.” which is the current OSiL instance file, that is, the data are included in the <xmlData> element as explained in the OSiL section. The <xPath> element also has a required path attribute which is a string of XPath syntax, used to locate values within the XML data. An XPath string may contain one or more “XPath variables” indicated by an initial “$” sign. The <xPath> element can have zero or more <xPathIndex> child elements. Each <xPathIndex> has a required indexName attribute and an optional indexValue attribute. An optional child of xPathIndex can be used that evaluates to the index value if indexValue is missing. The indexName attribute is used to match the xPathIndex with a $variable in the path attribute of <xPath> and indexValue is used to supply the value for the variable. So the number of xPathIndex child elements has to be exactly the same as the number of variables in the path attribute of <xPath>. As an example, consider the Markowitz optimization problem (6‑2). Assume the data on returns and covariances are located within the file stockdata.xml in same directory as the OSiL instance (uri = “./stockdata.xml”). The xml data file is shown below: <?xml version="1.0" encoding="UTF-8"?> There are three stocks each corresponding to a <stock> element. Each <stock> contains information about its ticker (name), index (idx), return (ret), minimum investment requirement (minInv) and covariances with all the stocks (<cov>). The data within the XML file at the indicated uri are located using the path attribute of XPath syntax. So if we use the <xPath> elements to locate the coefficients (stock return values) for each variable in constraint (1) of the above Markowitz example instead of directly specifying the values inside the instance, we come up with the following representation for constraint (1): <nl idx="0"> The above two examples are equivalent, but by using the variable $stockName and xPathIndex to supply the values (“msft”, “pg”, “ge”), the 3 xPath elements become the same and we can potentially simplify the syntax by designing a user function using an argument to pass the stock names. The library that reads the OSiL instance can use the xPath element to locate the stock return data before sending the instance to the solver. It is also possible to carry the XML data with the instance file. If this is desired, it is done by putting the data in the xmlData element. The <complements> schema from OSnL is shown below: <xs:complexType name="OSnLNodeComplements"> The <complements> element allows complementarity problems to be constructed for solvers to search for a feasible solution. Linear or smooth nonlinear optimization problems can be viewed as special cases of complementarity problems. Complementarity more or less means that at least one of a pair of logic expressions (e.g. two constraints) must hold with equality. The <complements> element is one of the few special elements that don’t have attributes. It also has a definite number of 2 children, which are often constraints. The sequence of the 2 children does not matter. Both children can consist from 1 to 3 expressions separated by logic operators =, >=, and <=. Of the two children of <complements>, there must be either exactly two inequality operators or one equality operator. The <complements> element evaluates to true if both children are true and at least one inequality is tight. For example if constraint1 is of the form expression1>=0 and constraint2 is of the form expression2<=5, we can express the complementarity as <complements> because the bound information is already specified in the <constraints> element of OSiL. Of course it has to be made sure that in using the concise form, the constraint is only constrained on one side; otherwise there can be ambiguities. Notice if the valueType attribute of constraint is not specified, it defaults to the constraint value. When one constraint constrainti, i in {1, 2}, involves two inequalities and is of the form lb<=expressioni or ub>=expressioni>=lb (lb and ub are numbers), then the other constraintj, j in {1, 2}, j != i , must be just of the free form expressionj. In this case, the <complements> element evaluates to true if constrainti is true and expressionj = 0 if lb < expressioni < ub For example if constraint1is of the form 2<=expression1<=7 and constraint2 is of the form expression2, we can express the complementarity as <complements> Of course it has to be made sure that in using the concise representation, constraint1 is bounded on both sides, that is, both lb (!= -INF) are ub (!= INF) attributes have to be specified on constraint1 in the <constraints> element of OSiL. Child elements of <complements> do not always have to be constraints. For example the following is also valid: <complements> for 0 <= X0 <= 0 complements X1+X2. Links: Click to see or download the OSnL XML Schema -> OSnL.xsd
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
| © Optimization Services (OS) 2006 | All rights reserved. | |
and 
.
is the 1st child
; n is the 1st child
) indicating the fraction of data points to exclude from the top and bottom of the data list. The rest of the children (from the second on) are the data list. 
), or “shortage” (
). The following are valid examples of a constraint element:
