Solver communications: Options and results

Horand I. Gassmann, Jun Ma, R. Kipp Martin

1. Introduction

Instance representation for optimization models is well understood. Instance generators, particularly algebraic modelling languages (see, e.g., ref:AMPL, ref:MPL) communicate with solvers via standard or private problem descriptions such as the MPS format (ref:MPS), AMPL nl format (ref:AMPL.nl), OSiL (ref:OSiL), etc. A lot of effort has gone into making these problem formulations tight, efficient, and shareable among many different solvers.

However, the problem instance is not the only piece of information shared between the instance generator and the solver. Addiitonally, solver options such as the maximum number of iterations or a starting point for the optimization algorithm must be communicated to the solver, and once the solver has finished execution, the results, including status, statistics and values of the instance variables must be reported back so that proper reports can be generated.

Unlike optimization instances, solver options and solver results are not generally shared among solvers, and to our knowledge there is no commonly accepted format for recording them. The MPS System that gave rise to the well-established and widely used MPS description format for linear  programs also featured a format for solver options (using so-called agenda cards) and LP results (ref:Murtagh), which, however, were not generally accepted.

In the course of developing the Optimization Services framework that aims to support the solution of a wide variety of optimization problems in a web-aware distributed computing environment, we had to deal with the issues of solver communication and learned a few guiding principles that make it easier to develop and maintain stable, platform-independent interfaces. We gather our experiences and recommendations in this paper and propose two XML schemas, OSoL for recording and communicating solver options to the solver, and OSrL for communicating solver results back to the calling program and ultimately to the user.

This paper is organized as follows. Section 2 describes the OSoL schema that underlies the options file supplied by the user. The options contained in this file are parsed by OS into an internal representation described in Section 3. The internal representation is then passed to one of many solvers using one of the mechanisms described in Section 4. Section 4 also contains some suggestions for proper interface design on the solver side, which were derived from our experience over the last few years with a variety of solvers. In Section 5 we describe the OSrL schema used to communicate the solver option and related status information back to the caller.
 
2. Description of the OSoL schema

In the OS framework the user communicates with the solver through XML files. There are several reasons for using XML for this task, not the least of which is that XML is an accepted format for data transmission over the internet. This section describes the OSoL (OS option language) schema in more detail.

An OSoL file is broken down into several optional sections, as shown in Figure 1. (ref:fig1):

a header section that can be used to document basic information about the file itself, its creation date, its source if appropriate, its author, etc., and data sections that contain options to be sent to the solver. 
 
The options that need to be transmitted fall into several categories:

general information about which solver is to be used, location of input files, how the user is to be notified of completion of the process, etc.

system options, which are especially important in a distributed environment or when cloud computing is involved. These options include  minimum requirements of disk space and memory availability, number of CPU cores, etc.

service options that allow the same option file format to be used for communication not just with optimization solvers but also other software such as analyzers, schedulers, simulation software, etc.

job options, including preparatory and cleanup steps to be used prior to, respectively, after the solver phase. These include files and directories that may have to be created, moved, destroyed. This information would be intercepted by the operating system through appropriate system actions, and would not be passed on to the solver directly.

optimization options which are the options seen by the solver. These can further be subdivided into options acting on (a subset of) the variables, such as initial values, basis status or the like, options acting on the constraints or objectives, and general options. (See figure 2 (ref:fig2).)

The most important realization is that all such options can be transmitted by the communication layer without knowledge of the underlying semantics; only syntax information is required. For instance, the element solverOption expands as follows (ref:fig3).

The name attribute identifies this option to the solver. There is no requirement on the parser to check the name or to match it against a list of valid names. The only assumption is that the user supplied a name in the osol file that is valid in the sense that the solver will understand it once it is passed in. Error detection is left entirely to the solver. 

The value attribute is used to communicate the option value to the solver. For full flexibility all values are stored as strings ---  both in the osol file and in the internal representation once the file has been parsed into memory.

The type attribute is used to record the type of variable. Since solvers are not uniform in their language (ipopt uses the term "numeric" to describe floating point or "double" values), there is no assumption made about the types that can be expected; the vaue of this attribute is again an ordinary string.

The solver attribute is used to limit the option to one particular solver. If the solver attribute is missing, the option will be passed to any solver that is selected at runtime.

The description attribute can be used for annotation about the purpose of this option.

The category attribute allows additional information to be passed to the solver regarding the option. In Lindo (ref:Lindo), for instance, it is possible to set attributes affecting either the entire session, or just on individual model. Both use cases are illustrated in the next two lines.

			<solverOption name="LS_IPARAM_LP_PRINTLEVEL" solver="lindo" category="model"  type="integer" value="0"/>
			<solverOption name="LS_IPARAM_LP_PRINTLEVEL" solver="lindo" category="environment" type="integer" value="1"/>

Another use of the category attribute is to allow a solver to pass options on to external pieces of software that are used by the solver. For instance, Couenne (ref:Couenne) is an open-source global optimization solver in the COIN-OR collection. It uses Bonmin (ref:bonmin) as an underlying MINLP solver, which in turn may take options that can be fine-tuned by the user. Specifying

		<solverOptions numberOfSolverOptions="5">	
			<solverOption name="node_limit" solver="couenne" type="integer" value="1000" category="bonmin"/> 
			<solverOption name="max_iter" solver="couenne" type="integer" value="2000" category="ipopt"/>		

informs the Couenne solver to pass the node_limit option to Bonmin, in order to affect the size of the search tree and to pass the option max_iter to ipopt in order to limit the number of iterations during the solution of a convexified subproblem. 

Bonmin in turn relies on the linear integer solver Cbc for the solution of continuous relaxations of its subproblems, and it may be necessary to use options to control the behaviour of this action, as follows:  

The optional attribute NumberOfItems and the optional sequence of item elements can be used to provide values for array-valued options. These complement other constructions in the variables, constraints and objectives elements, which provide array-valued options when the array elements are indexed over the columns, constraint rows and objectives of the problem. Sometimes, however, an array of options must be specified that is indexed over a different set, such as an array of seed values for a random number generator.

3. Internal representation --- the OSOption class

Internally the option file can be represented as an C++ class exhibiting the same tree structure as the XML file. In particular, the solver options are represented as an array of 6-tuples, each tuple consisting of a name, solver, type, value, description, and scope. No attempt is made by the parser to interpret an option in any way. Changes to the solver options therefore do not require any changes to the parser, the storage scheme, or the API.

4. API and solver communication

There are many ways in which a framework such as OS can communicate with a solver. We illustrate three such methods in increasing order of rigidity.

1. Ipopt
Communication with Ipopt is very flexible, because Ipopt exposes three methods that can be used to communicate options as name/value pairs. The great advantage of this approach is its extensibility. The solver developer is free to change the internal options without _any_ modifications to the server code. Let's say, for instance, that the solver developer wishes to implement a new pivot rule for a simplex sover. The internal name for this option is NewRule, and it can take an optional integer parameter. This can be recorded by the user (upon receiving the pertinent information from the solver developer) as

<option name="NewRule" solver=""ipopt" value="5">

The parser reads and stores this into the data structure and passes it on to ipopt as a name/value tuple --- no interpretation of the semantics takes place. Ipopt decodes the option, checks its validity, and acts appropriately.

2.Cbc

Slightly less flexible is the way in which OS communicates with Cbc. Cbc exposes as part of its API a command line parser. This makes it possible to  string together all the options selected in an osol file into a long string and to have Cbc parse that string. Again, there is nearly no need for OS to know the meaning of the Cbc options. The situation would be fully equivalent to the Ipopt interface if all Cbc options are given in the same form as name/ value pairs. However, since some options   

3. Osi

The Osi interface is used by a number of open source (e.g., Clp, Dylp, Symphony, Glpk) and commercial (e.g., Cplex) linear programming solvers. Unlike the others just described, it relies on an enumeration of commonly available option. This limits the use, as only very common options are supported. Options not covered by the enumeration (such as whether to use a simplex or interior point method) thus cannot be communicated. Extending the interface is also quite cumbersome, and the interface must be aware of the solutions that can be passed, as well as their semantics.

4. Other interfaces

Other interfaces would be possible, based on exposing more or fewer methods in the API. In the extreme, the user could be directed to put all the solver options into a file and to supply only the location of the file to the solver. This would again limit the knowledge needed by the OS interface 
concerning the options, but it would be challenging to implement in a distributed environment.

OSrL schema