OS Protocols

The objective of (OS) is to provide a set of standards for representing optimization instances, results, solver options, and communication between clients and solvers in a distributed environment using Web Services. These standards are specified by W3C XSD schemas. The schemas for the OS project are contained in the schemas folder under the OS root. There are numerous schemas in this directory that are part of the OS standard. For a full description of all the schemas see Ma [4]. We briefly discuss the standards most relevant to the current version of the OS project.

OSiL (Optimization Services instance Language): an XML-based language for representing instances of large-scale optimization problems including linear programs, mixed-integer programs, quadratic programs, and very general nonlinear programs.

OSiL stores optimization problem instances as XML files. Consider the following problem instance that is a modification of an example of Rosenbrock [5]:

$$\quad (1 - x_{0})^{2} + 100(x_{1} - x_{0}^{2})^{2} + 9x_{1}$$ Minimize (1)

$$\quad x_{0} + 10.5 x_{0}^{2} + 11.7 x_{1}^{2} + 3x_{0}x_{1} \le 25$$ s.t. (2)

$$\ln(x_{0} x_{1}) + 7.5 x_{0} + 5.25 x_{1} \ge 10$$ (3)

$$x_{0}, x_{1} \ge 0$$ (4)

There are two continuous variables, $x_{0}$ and $x_{1}$, in this instance, each with a lower bound of 0. Figure 4 shows how we represent this information in an XML-based OSiL file. Like all XML files, this is a text file that contains both markup and data. In this case there are two types of markup, elements (or tags) and attributes that describe the elements. Specifically, there are a <variables> element and two <var> elements. Each <var> element has attributes lb, name, and type that describe properties of a decision variable: its lower bound, ``name'', and domain type (continuous, binary, general integer).

Figure 4: The <variables> element for the example (1)-(4).

To be useful for communication between solvers and modeling languages, OSiL instance files must conform to a standard. An XML-based representation standard is imposed through the use of a W3C XML Schema. The W3C, or World Wide Web Consortium (www.w3.org), promotes standards for the evolution of the web and for interoperability between web products. XML Schema (www.w3.org/XML/Schema) is one such standard. A schema specifies the elements and attributes that define a specific XML vocabulary. The W3C XML Schema is thus a schema for schemas; it specifies the elements and attributes for a schema that in turn specifies elements and attributes for an XML vocabulary such as OSiL. An XML file that conforms to a schema is called valid for that schema.

By analogy to object-oriented programming, a schema is akin to a header file in C++ that defines the members and methods in a class. Just as a class in C++ very explicitly describes member and method names and properties, a schema explicitly describes element and attribute names and properties.

Figure 5: The Variables complexType in the OSiL schema.

Figure 6: The Variable complexType in the OSiL schema.

Figure 5 is a piece of our schema for OSiL. In W3C XML Schema jargon, it defines a complexType, whose purpose is to specify elements and attributes that are allowed to appear in a valid XML instance file such as the one excerpted in Figure 4. In particular, Figure 5 defines the complexType named Variables, which comprises an element named <var> and an attribute named numberOfVariables. The numberOfVariables attribute is of a standard type positiveInteger, whereas the <var> element is a user-defined complexType named Variable. Thus the complexType Variables contains a sequence of <var> elements that are of complexType Variable. OSiL's schema must also provide a specification for the Variable complexType, which is shown in Figure 6.

In OSiL the linear part of the problem is stored in the <linearConstraintCoefficients> element, which stores the coefficient matrix using three arrays as proposed in the earlier LPFML schema [2]. There is a child element of <linearConstraintCoefficients> to represent each array: <value> for an array of nonzero coefficients, <rowIdx> or <colIdx> for a corresponding array of row indices or column indices, and <start> for an array that indicates where each row or column begins in the previous two arrays.

Figure 7: The <linearConstraintCoefficients> element for constraints (2) and (3).

The quadratic part of the problem is represented in Figure 2.

Figure 8: The <quadraticCoefficients> element for constraint (2).

The nonlinear part of the problem is given in Figure 9.

Figure 9: The <nl> element for the nonlinear part of the objective (1).

The complete OSiL representation is given in the Appendix (Section 14.2).

OSrL (Optimization Services result Language): an XML-based language for representing the solution of large-scale optimization problems including linear programs, mixed-integer programs, quadratic programs, and very general nonlinear programs. As example solution (for the problem given in (1)-(4) ) in OSrL format is given below.

<?xml version="1.0" encoding="UTF-8"?>
<?xml-stylesheet type = "text/xsl"
  href = "/Users/kmartin/Documents/files/code/cpp/OScpp/COIN-OSX/OS/stylesheets/OSrL.xslt"?>
<osrl xmlns="os.optimizationservices.org"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="os.optimizationservices.org
http://www.optimizationservices.org/schemas/OSrL.xsd">
    <resultHeader>
        <generalStatus type="success"/>
        <serviceName>Solved using a LINDO service</serviceName>
        <instanceName>Modified Rosenbrock</instanceName>
    </resultHeader>
    <resultData>
        <optimization numberOfSolutions="1" numberOfVariables="2" numberOfConstraints="2"
            numberOfObjectives="1">
            <solution objectiveIdx="-1">
                <status type="optimal"/>
                <variables>
                    <values>
                        <var idx="0">0.87243</var>
                        <var idx="1">0.741417</var>
                    </values>
                    <other name="reduced costs" description="the variable reduced costs">
                        <var idx="0">-4.06909e-08</var>
                        <var idx="1">0</var>
                    </other>
                </variables>
                <objectives>
                    <values>
                        <obj idx="-1">6.7279</obj>
                    </values>
                </objectives>
                <constraints>
                    <dualValues>
                        <con idx="0">0</con>
                        <con idx="1">0.766294</con>
                    </dualValues>
                </constraints>
            </solution>
        </optimization>

OSoL (Optimization Services option Language): an XML-based language for representing options that get passed to an optimization solver or a hosted optimization solver Web service. It contains both standard options for generic services and extendable option tags for solver-specific directives.

OSnL (Optimization Services nonlinear Language): The OSnL schema is imported by the OSiL schema and is used to represent the nonlinear part of an optimization instane. This is explained in greater detail in Section 7.2.4. Also refer to Figure 9 for an illustration of elements from the OSnL standard.

OSpL (Optimization Services process Language): is a standard for dynamic process information that is kept by the Optimization Services registry. It is the result of a knock operation. See the example given in Section 10.3.5.