
%%% Need to specify the required parts of the component interfaces and
%%% the optional parts.

%%% Work needs to be put into a section in iteratively calling
%%% the software.  CommonWorkspace_Create(), _Destroy()

\chapter{Interfaces}\label{chap:interfaces}

% This chapter is an update to sections of the following papers:
%   ``Interfaces to PATH 3.0: Design, Implementation, and Usage''
%       - Standalone interfaces
%       - Problem structures
% Added examples to standalone exposition, updated the structures to
% be correct with PATH 4.4a.
%
% The QP section is new to the document and is meant to serve as an
% illustration of the things that can be done with the interface.  I
% implemented the QP code for someone...

The previous chapter discussed complementarity from a modeling perspective and
demonstrated how to use the AMPL, GAMS, MATLAB, and NEOS tools to write a 
complementarity problem and convey it to a solver.  This chapter looks at the 
solver from an application programmer's point of view and documents the
mechanisms available for integrating PATH 4.x and SEMI into other environments
or applications.

The solver interface needs to be able to support the requirements for each 
individual environment.  For example, GAMS provides a heap for memory 
allocation purposes, while MATLAB provides a special function for reporting 
errors.  
Therefore, the solver interface abstracts core components, output and
memory allocation in particular, from the algorithm so that implementations 
tailored to a particular environment can be supplied either at compile or 
run time.  In addition to specifying a problem and invoking a solver, the 
solver interface can then be used to control output, memory allocation, and 
interrupt handling.  

\secref{subroutine} discusses a simplified interface to the PATH 4.x and SEMI 
codes meant to eliminate most of the errors that may occur while coding a 
particular application.  The remaining sections in this chapter detail the 
solver interface used to implement the links to the environments from
\chapref{environments}.  An application programmer could use this 
documentation to write interfaces for other uses.  In particular, an 
example interface for solving convex quadratic programs is developed in 
\secref{driver}.

\section{Subroutines}\label{sec:subroutine}
A simplified subroutine interface has been developed that hides many of the 
details associated with invoking PATH 4.x or SEMI directly, eliminating 
most of the 
errors that may occur while coding a particular application.  To use the 
subroutine library, a user supplies function and Jacobian evaluation routines, 
and calls the PATH 4.x or SEMI algorithms within their main program.

The subroutine called by the user's program is declared as
\single\begin{verbatim}
     void pathMain(int n, int nnz, int *status, 
                   double *z, double *F, double *l, double *u);
\end{verbatim}
\double
for PATH 4.x.
The inputs to this routine are $n$ and $nnz$, the number of
variables in the problem and an \textbf{over-estimate} of the number of 
nonzeros in the Jacobian of $F$ respectively, and vectors containing the 
starting point and lower and upper bounds.  The numerical value used for 
infinity in the subroutine library interface is $10^{20}$.  The subroutine 
returns the solver status, the solution vector, $z$, and function evaluation, 
$F(z)$.  The status codes are fully described in \tabref{codes-standalone}.
SEMI can be used by calling the \texttt{semiMain} subroutine which has the 
same input and output arguments as \texttt{pathMain}.

\begin{table}
\centering
\caption{Status codes for Subroutine
Interfaces}\label{tab:codes-standalone}
\begin{tabular}{llp{8.5cm}}
Code & String & Meaning \\
\hline
1 & Solver & A solution to the problem was found. \\
2 & No Progress & Algorithm could not improve upon the current iterate. \\
3 & Major Iteration Limit & An iteration limit was reached.\\
4 & Cumulative Iteration Limit & The minor iteration limit was
reached.\\
5 & Time Limit & Time limit was exceeded. \\
6 & User Interrupt & The user requested that the solver stop
execution. \\
7 & Bound Error & The problem is infeasible because $\ell_l > u_i$ for
some components. \\
8 & Domain Error & A starting point where the function is defined
could not be found. \\
9 & Infeasible & The preprocessor determined the problem is
infeasible.\\
10 & Error & An internal error occurred in the algorithm.\\
\end{tabular}
\end{table}

The remaining components of the simplified interface are the function
and Jacobian evaluation routines with declarations:
\single\begin{verbatim}
     int funcEval(int n, double *z, double *F);
     int jacEval(int n, int nnz, double *z, int *col, 
                 int *len, int *row, double *data);
\end{verbatim}
\double
The \texttt{funcEval} routine is given the problem size, $n$, and a 
vector containing a point, $z$.  The user is then requested to place
the function evaluation at $z$ into $F$.  The \texttt{jacEval} routine is
also given the problem size, $n$, the number of nonzeros allocated for
the Jacobian, $nnz$, and a given point, $z$.  The Jacobian of $F$ at $z$
should be places into \texttt{col}, \texttt{len}, \texttt{row}, and
\texttt{data}, where the Jacobian is in a compressed sparse column
format.  The indices in \texttt{col} and \texttt{len} \textbf{must}
take on values between $1$ and $n$.  That is, the indices should be
written in the FORTRAN style.  Note that the algorithm will not change the 
structure passed for the Jacobian.  Therefore, if the structure of the 
Jacobian does not change, \texttt{col}, \texttt{len}, and \texttt{row} only 
need to be filled once.  The function and Jacobian evaluation routines should 
return the number of domain violations encountered.  For example, a domain 
violation occurs when we have division by zero.

An implementation for the transportation model from \secref{applications} 
with isoelastic demand is 
given in \figref{transportation-c} and \figref{transportation-c2}.  Note that 
an initial starting point is
specified where the function is well-defined and that the structure of the
Jacobian matrix uses the correct FORTRAN style indices.

\begin{figure}
\begin{smallverb}
#include "Standalone.h"
#include <math.h>

int main()
{
     int n = 11, nnz = 27, status, i;
     double z[11], F[11], l[11], u[11];

     for (i = 0; i < n; i++)
     {
          z[i] = 1.0; l[i] = 0; u[i] = 1e20;
     }

     pathMain(n, nnz, &status, z, F, l, u);
     return 0;
}

int funcEval(int n, double *z, double *F)
{
     if ((z[6] <= 0) || (z[7] <= 0) || (z[8] <= 0))
          return 1;

     /* Rational marketplace constraints */
     F[0]  = z[9]  - z[6] + 0.225;
     F[1]  = z[9]  - z[7] + 0.153;
     F[2]  = z[9]  - z[8] + 0.162;
     F[3]  = z[10] - z[6] + 0.225;
     F[4]  = z[10] - z[7] + 0.162;
     F[5]  = z[10] - z[8] + 0.126;
     
     /* Capacity constraints */
     F[6]  = z[0] + z[3] - 325.0 / pow(z[6], 0.5);
     F[7]  = z[1] + z[4] - 300.0 / pow(z[7], 0.5);
     F[8]  = z[2] + z[5] - 275.0 / pow(z[8], 0.5);
     
     /* Satisfaction of demand constraints */
     F[9]  = 325.0 - z[0] - z[1] - z[2]; 
     F[10] = 575.0 - z[3] - z[4] - z[5];
     return 0;
}
\end{smallverb}
\caption{Transportation model using Simplified
Interface}\label{fig:transportation-c}
\end{figure}

\begin{figure}
\begin{smallverb}
int jacEval(int n, int nnz, double *z, int *col,
            int *len, int *row, double *data)
{
     static int filled = 0;

     if (!filled)
     {
          /* Fill in the structure of the Jacobian */

          col[0] = 1;  len[0] = 2; row[0] = 7; row[1] = 10;
          col[1] = 3;  len[1] = 2; row[2] = 8; row[3] = 10;
          col[2] = 5;  len[2] = 2; row[4] = 9; row[5] = 10;
          col[3] = 7;  len[3] = 2; row[6] = 7; row[7] = 11;
          col[4] = 9;  len[4] = 2; row[8] = 8; row[9] = 11;
          col[5] = 11; len[5] = 2; row[10]= 9; row[11]= 11;
          col[6] = 13; len[6] = 3; row[12]= 1; row[13]=  4; row[14]= 7;
          col[7] = 16; len[7] = 3; row[15]= 2; row[16]=  5; row[17]= 8;
          col[8] = 19; len[8] = 3; row[18]= 3; row[19]=  6; row[20]= 9;
          col[9] = 22; len[9] = 3; row[21]= 1; row[22]=  2; row[23]= 3;
          col[10]= 25; len[10]= 3; row[24]= 4; row[25]=  5; row[26]= 6;
          filled = 1;
     }	         

     if ((z[6] <= 0) || (z[7] <= 0) || (z[8] <= 0))
          return 1;

     data[0] =  1; data[1] = -1;
     data[2] =  1; data[3] = -1;
     data[4] =  1; data[5] = -1;
     data[6] =  1; data[7] = -1;
     data[8] =  1; data[9] = -1;
     data[10]=  1; data[11]= -1;
     data[12]= -1; data[13]= -1; data[14]=  0.5*325 / pow(z[6], 1.5);
     data[15]= -1; data[16]= -1; data[17]=  0.5*300 / pow(z[7], 1.5);
     data[18]= -1; data[19]= -1; data[20]=  0.5*275 / pow(z[8], 1.5);
     data[21]=  1; data[22]=  1; data[23]=  1;
     data[24]=  1; data[25]=  1; data[26]=  1;
     return 0;
}
\end{smallverb}
\caption{Transportation model using Simplified
Interface (cont.)}\label{fig:transportation-c2}
\end{figure}

Algorithm specific 
options can be placed in a file called \texttt{path.opt} for PATH 4.x or 
\texttt{semi.opt} for SEMI.  Furthermore, if the solver fails to find a 
complementary solution, the user might find it 
helpful to look at the log file.  The user can specify a file where the log 
will be written by calling the function:
\single\begin{verbatim}
     void Output_SetLog(FILE *fp);
\end{verbatim}
\double
before the call to \texttt{pathMain} or \texttt{semiMain}.  The argument is an 
opened file where the log will be written.  

\begin{comment}
The FORTRAN interface is almost identical to the C interfaces.  It
consists of one function that the user invokes:
\single\begin{verbatim}
     subroutine pathmain(n, nnz, status, z, F, l, u)
\end{verbatim}
\double
and the analogous user supplied functions for $f$ and the Jacobian of
$f$.
\single\begin{verbatim}
     integer function funceval(n, z, F)
     integer function jaceval(n, nnz, z, col, len, row, data)
\end{verbatim}
\double
The input and output to the functions are the same as the C versions.
The log can be printed to a unit number from the FORTRAN interface.
To supply a unit number, the subroutine declared as
\single\begin{verbatim}
     subroutine set_log(int unitnum)
\end{verbatim}
\double
can be issued before the call to \texttt{pathmain}.

The Walrasian equilibrium model written using the simplified FORTRAN
interface is found in \figref{walrasian-fortran}.  Note that a
starting point other than zero is used in the implementation to avoid
a domain error at the starting point.

\begin{figure}
\begin{verbatim}
       integer function funceval(n, z, f)
       implicit none

       integer n
       double precision z(n), f(n)

       return 0
       end

       integer function funceval(n, z, f)
       implicit none

       integer n
       double precision z(n), f(n)

       return 0
       end

       program walrasian
       implicit none

       double precision z(10), f(10), l(10), u(10)

       call pathmain(z,l,u,status)
       end
\end{verbatim}
\caption{Walrasian Equilibrium using Simplified FORTRAN
Interface}\label{fig:walrasian-fortran}
\end{figure}
\end{comment}

\section{Problem Structures}\label{sec:problem}
We now look at the complete solver interface used to implement the simplified 
subroutine library and the links to the environments in 
\chapref{environments}.  
The core component of the interface is the notion of a mixed 
complementarity problem.  The \texttt{MCP} structure serves as a repository for
information 
about the particular complementarity problem a user wants to solve.  Associated
with each \texttt{MCP} is an \texttt{MCP\_Interface}, which contains pointers 
to user specified functions for obtaining bounds, and function and Jacobian 
evaluations.  An optional \texttt{Presolve\_Interface} provides additional 
information about the problem for use in the preprocessor developed in
\chapref{preprocessing}.  The header file, \texttt{MCP.h}, is found in
\figref{mcp-header} and contains all of the function declarations
used in conjunction with the \texttt{MCP}, \texttt{MCP\_Interface} and
\texttt{Presolve\_Interface} structures.

\begin{figure}
\begin{verbatim}
struct _MCP;
typedef struct _MCP MCP;

/* Allocation and deallocation functions. */
MCP *MCP_Create(int maxModSize, int maxModNNZ);
void MCP_Destroy(MCP *m);
void MCP_Size(MCP *m, int maxModSize, int maxModNNZ);

/* Jacobian flag functions. */
void MCP_Jacobian_Structure_Constant(MCP *m, int b);
void MCP_Jacobian_Data_Contiguous(MCP *m, int b);
void MCP_Jacobian_Diagonal(MCP *m, int b);
void MCP_Jacobian_Diagonal_First(MCP *m, int b);

/* Interface functions. */
void MCP_GetInterface(MCP *m, MCP_Interface *i);
void MCP_SetInterface(MCP *m, MCP_Interface *i);

void MCP_GetPresolveInterface(MCP *m, Presolve_Interface *i);
void MCP_SetPresolveInterface(MCP *m, Presolve_Interface *i);

/* Access routines. */
double *MCP_GetX(MCP *m);
double *MCP_GetL(MCP *m);
double *MCP_GetU(MCP *m);
int *   MCP_GetB(MCP *m);

double *MCP_GetF(MCP *m);
void    MCP_GetJ(MCP *m, int *nz, int **col, int **len, 
                 int **row, double **data);
\end{verbatim}
\caption{Header file, \texttt{MCP.h}}\label{fig:mcp-header}
\end{figure}

A fundamental operation is to allocate and deallocate a problem instance.
\tabref{mcp-initialization} lists the functions used for this
purpose.  The \texttt{MCP\_Create} function has arguments for the
problem size and number of nonzeros, $n$ and $nnz$ respectively, which
can take on any values.  However, for best performance, they should be 
{\bf over-estimates} of the actual size and number of nonzeros in the problem.
Otherwise, memory reallocation will be performed within the solver.  
The \texttt{MCP\_Destroy} function is used to deallocate a previously 
allocated problem instance, while \texttt{MCP\_Size} can be used to 
increase the number of variables or nonzeros in a particular problem
instance.

\begin{table}
\centering
\caption{Initialization routines}\label{tab:mcp-initialization}
\begin{tabular}{lp{12cm}}
Function & Description\\
\hline
MCP\_Create & Allocate an MCP structure with $n$ variables and $nnz$ 
elements in the Jacobian \\
MCP\_Destroy & Deallocate an MCP \\
MCP\_Size & Resize the MCP structure to have $n$ variables and $nnz$ 
elements in the Jacobian
\end{tabular}
\end{table}

The set of functions described in \tabref{mcp-jacobian} provide information 
about the Jacobian matrix, which is then used
to improve the performance of operations internal to the solver.  The most 
important of these functions is \texttt{MCP\_Jacobian\_Structure\_Constant} 
which tells the library whether the structure of the Jacobian remains constant
or changes depending on the input vector.  If set to a nonzero value, 
\texttt{col}, \texttt{len}, and \texttt{row} are assumed to be a constant 
compressed sparse column representation of the Jacobian.
\textit{In order to use the preprocessor developed in 
\chapref{preprocessing}, a 
constant Jacobian structure is required.}  The remaining flags indicate 
other features of the Jacobian.  Setting 
\texttt{MCP\_Jacobian\_Data\_Contiguous} to a nonzero value means that
the compressed sparse column representation of the Jacobian
is in a contiguous block.  That is, there are no unused elements in 
the \texttt{row} and \texttt{data} vectors.
The two remaining functions, \texttt{MCP\_Jacobian\_Diagonal} and 
\texttt{MCP\_Jacobian\_Diagonal\_First}, should be set if each column 
has an entry on the diagonal and if the diagonal element appears as the
first entry in each column respectively.

\begin{table}
\centering
\caption{Jacobian information routines}\label{tab:mcp-jacobian}
\begin{tabular}{lp{8.5cm}}
Function & Description\\
\hline
MCP\_Jacobian\_Data\_Contiguous &
Inform algorithm that the compressed sparse column representation of the
Jacobian is in a contiguous block.\\
MCP\_Jacobian\_Diagonal & 
Inform algorithm that each column has an entry on the diagonal. \\
MCP\_Jacobian\_Diagonal\_First &
Inform algorithm that the first element in each column is the diagonal
entry if it exists. \\
MCP\_Jacobian\_Structure\_Constant & 
Inform algorithm that the structure of the Jacobian matrix remains constant \\
\end{tabular}
\end{table}

The access routines listed in \tabref{mcp-access} are used to obtain
information about the specified model.  For example, after the model is 
solved, a user would typically like to know the answer.  The solution
can be obtained by using the \texttt{MCP\_GetX} routine, which returns 
a vector 
containing the current iterate, and the \texttt{MCP\_GetF} routine, which
returns a vector containing the function evaluation at the current iterate.
The other routines provide the Jacobian evaluation at the current iterate 
in a compressed sparse column format, \texttt{MCP\_GetJ}, and the lower 
and upper bounds, \texttt{MCP\_GetL} and \texttt{MCP\_GetU} respectively.  
\texttt{MCP\_GetB} returns basis information when using an active-set 
method.  For each variable, the vector indicates the active-set with the 
flags described in \tabref{basis}.
These indicators can then be used to ``warm'' start the algorithm when 
solving related problem instances.

\begin{table}
\centering
\caption{Access functions}\label{tab:mcp-access}
\begin{tabular}{ll}
Function & Description\\
\hline
MCP\_GetB & Obtain the current basis information \\
MCP\_GetF & Obtain the function evaluation at the current iterate \\
MCP\_GetJ & Obtain the Jacobian evaluation at the current iterate \\
MCP\_GetL & Obtain the lower bounds \\
MCP\_GetU & Obtain the upper bounds \\
MCP\_GetX & Obtain the current iterate \\
\end{tabular}
\end{table}

\begin{table}
\centering
\caption{Basis information codes}\label{tab:basis}
\begin{tabular}{lp{12cm}}
Identifier & Meaning \\
\hline
Basis\_Basic & Variable is between lower and upper bounds and basic. \\
Basis\_Fixed & Variable was fixed by the preprocessor and removed from the
model. \\
Basis\_Lower & Variable is fixed at its lower bound. \\
Basis\_Upper & Variable is fixed at its upper bound. \\
Basis\_Superbasic & Variable is between lower and upper bounds, but non-basic.  Typically, this type is caused by singularity in the Jacobian matrix. \\
Basis\_Unknown & Algorithm does not return basis information.
\end{tabular}
\end{table}

Finally, the functions used to bind interface structures to the
complementarity problem are given in \tabref{mcp-interface}.
The key functions are \texttt{MCP\_SetInterface}, which is used to
specify the problem instance, and \texttt{MCP\_SetPresolveInterface},
which is used to supply the additional information needed for the
preprocessor.  The contents of these two structures are discussed in
the sequel.

\begin{table}
\centering
\caption{Interface functions}\label{tab:mcp-interface}
\begin{tabular}{ll}
Function & Description\\
\hline
MCP\_SetInterface & Set the \texttt{MCP\_Interface} for the problem. \\
MCP\_SetPresolveInterface & Set the \texttt{Presolve\_Interface} for the problem. \\
MCP\_GetInterface & Obtain the \texttt{MCP\_Interface} for the problem. \\
MCP\_GetPresolveInterface & Obtain the \texttt{Presolve\_Interface} for the problem.
\end{tabular}
\end{table}

\subsection{MCP\_Interface}\label{sec:external}
All of the required problem information is conveyed in the
\texttt{MCP\_Interface} structure declared in \figref{mcp-interface}.
The user allocates an interface
structure and fills in the function pointers for their particular
application.  These functions are then used by the algorithm to obtain 
problem information.  The \texttt{interface\_data} 
can be any user allocated data and is passed as the first argument to all 
of the functions.  

\begin{figure}
\begin{verbatim}
typedef struct
{
     void *interface_data;

     void (*problem_size)(void *id, int *size, int *nnz);
     void (*bounds)(void *id, int size, 
                    double *x, double *l, double *u);

     int (*function_evaluation)(void *id, int n, double *x, 
                                double *f);
     int (*jacobian_evaluation)(void *id, int n, double *x, 
                                int wantf, double *f, 
                                int *nnz, int *col, int *len, 
                                int *row, double *data);

     void (*start)(void *id);
     void (*finish)(void *id, double *x);
     void (*variable_name)(void *id, int variable, 
                           char *buffer, int buf_size);
     void (*constraint_name)(void *id, int constr, 
                             char *buffer, int buf_size);
     void (*basis)(void *id, int size, int *basX);
} MCP_Interface;
\end{verbatim}
\caption{\texttt{MCP\_Interface} declaration}\label{fig:mcp-interface}
\end{figure}

Some of the functions alluded to in the declaration of
\texttt{MCP\_Interface} are required while others are optional.
The user must provide implementations for the 
\texttt{problem\_size}, \texttt{bounds}, \texttt{function\_evaluation}, 
and \texttt{jacobian\_evaluation} functions described
in \tabref{mcp-required}.
The number of domain violations encountered during the evaluation should
be returned by the \texttt{function\_evaluation} and 
\texttt{jacobian\_evaluation} routines.
A domain violation occurs, for example, when we attempt to 
take the log of a negative number or we encounter division by zero.
The Jacobian matrix is stored in a compressed sparse column format
with the indices written in the FORTRAN style.  That is, each index element 
takes on a value between one and the number of indices.  Furthermore, the 
structure 
of the sparse matrix need only be determined and allocated once.  We 
guarantee that the algorithms will not alter the structure.

\begin{table}
\centering
\caption{Required functions for \texttt{MCP\_Interface}}\label{tab:mcp-required}
\begin{tabular}{lp{11cm}}
Function & Description\\
\hline
problem\_size & Give the size of the problem and number of nonzeros in the Jacobian.\\
bounds &  Give the lower and upper bounds and a starting point for the problem.\\
function\_evaluation & Evaluate the function for a point $z$.  Return the number of domain violations.\\
jacobian\_evaluation & Evaluate 
the function and Jacobian for a point $z$.  Return the number of domain 
violations.  The Jacobian is stored in a compressed column format.  Initially
nnz is the allocated size for the row and data arrays.  The actual number of 
nonzeros in the Jacobian should be supplied before returning.
\end{tabular}
\end{table}

The user can optionally provide the functions documented
in \tabref{mcp-optional}.  The \texttt{start} and \texttt{finish} routines
are called exactly once at the beginning and the end of the computation
respectively.
For example, an implementation of the \texttt{start} function can be used 
to perform allocation and initialization at the beginning of the solve, while
the \texttt{finish} function can deallocate.  The \texttt{variable\_name}
and \texttt{constraint\_name} are used to provide names for the variables
and constraints.  The indices passed into the functions are in
FORTRAN style.  For example, \texttt{var} will take on a value between
1 and the number of variables in the problem.  If not provided, the
defaults names are ``x'' and ``f'' for the variables and constraints.
Finally, the \texttt{basis} function can be used to specify basis information
at the start of the computation.  This information can help an
active-set type method to identify the correct active-set at the
beginning of the solve, leading to improved performance.
The indicators used for this purpose are given in \tabref{basis}.

\begin{table}
\centering
\caption{Optional functions for \texttt{MCP\_Interface}}\label{tab:mcp-optional}
\begin{tabular}{ll}
Function & Description\\
\hline
start & Function called at the start of the solve. \\
finish & Function called at the end of the
solve with the final iterate. \\
variable\_name & Provide a 
name for the specified variable.\\
constraint\_name & Provide 
a name for the specified constraint.\\
basis & Used to provide basis information at the
start of the computation.
\end{tabular}
\end{table}

\begin{comment}
\begin{figure}
\begin{verbatim}
#include "Standalone.h"
#include "MCP_Interface.h"

typedef struct
{
     int n;
     int nnz;

     double *z;
     double *lb;
     double *ub;
} Problem;

static Problem problem;

static void problem_size(void *id, int *n, int *nnz)
{
     *n = problem.n;
     *nnz = problem.nnz;
     return;
}

static void bounds(void *id, int n, double *z, double *lb, double *ub)
{
     int i;

     for (i = 0; i < n; i++)
     {
          z[i] = problem.z[i];
          lb[i] = problem.lb[i];
          ub[i] = problem.ub[i];
     }
     return;
}
\end{verbatim}
\caption{Implementation of MCP\_Interface for C subroutines}\label{mcp-c-implementation}
\end{figure}

\begin{figure}
\begin{verbatim}
static int function_evaluation(void *id, int n, double *z, double *f)
{
     return funcEval(n, z, f);
}

static int jacobian_evaluation(void *id, int n, double *z, int wantf,
                               double *f, int *nnz,
                               int *col_start, int *col_len,
                               int *row, double *data)
{
     int i, err = 0;

     if (wantf)
     {
          err += function_evaluation(id, n, z, f);
     }

     err += jacEval(n, *nnz, z, col_start, col_len, row, data);

     (*nnz) = 0;
     for (i = 0; i < n; i++)
     {
         (*nnz) += col_len[i];
     }
     return err;
}

static MCP_Interface interface =
{
     NULL,
     problem_size, bounds,
     function_evaluation, jacobian_evaluation,
     NULL, NULL,
     NULL, NULL,
     NULL
};
\end{verbatim}
\caption{Implementation of MCP\_Interface for C subroutines (cont.)}\label{mcp-c-implementation2}
\end{figure}
\end{comment}

\subsection{Preprocessing\_Interface}
The final component of the \texttt{MCP} specification
is the \texttt{Presolve\_Interface}, which is used to provide 
additional information about the model needed for preprocessing.  
\textit{Note that use of the 
preprocessor requires that the Jacobian structure remain constant, which is
communicated with the \texttt{MCP\_Jacobian\_Structure\_Constant} function.}
The declaration for the \texttt{Presolve\_Interface} is found in 
\figref{mcp-presolve}.  The \texttt{presolve\_data} component can be any user 
allocated data and is passed as the first argument to all of the presolve 
interface functions.

\begin{figure}
\begin{verbatim}
typedef struct
{
     void *presolve_data;

     void (*start_pre)(void *pd);
     void (*start_post)(void *pd);

     void (*finish_pre)(void *pd);
     void (*finish_post)(void *pd);

     void (*jac_typ)(void *pd, int nnz, int *typ);
     void (*con_typ)(void *pd, int n, int *typ);
} Presolve_Interface;
\end{verbatim}
\caption{\texttt{Presolve\_Interface} declaration}\label{fig:mcp-presolve}
\end{figure}

The only required function, \texttt{jac\_typ}, fills in the type of each 
element in the Jacobian.  The defined symbols, \texttt{PRESOLVE\_LINEAR} and 
\texttt{PRESOLVE\_NONLINEAR}, are used to indicate linear and nonlinear
elements respectively.  The elements in the \texttt{typ} vector correspond to 
the compressed sparse column representation of the Jacobian.  For example, in
\figref{mcp-linear} we give an implementation of the presolve interface for
linear complementarity problems.  Note that in this example, we have assumed
that the Jacobian elements are stored in a contiguous block, leading to the
simple loop indicating that each element is linear.

Additionally, if your problem comes from the Karush-Kuhn-Tucker conditions
for a variational inequality or nonlinear program, the primal and dual
constraints can be specified using the \texttt{con\_typ} function.
\texttt{PRESOLVE\_PRIMAL} and \texttt{PRESOLVE\_DUAL},
are the defined symbols used to indicate which of the constraints are
primal and dual.  If a constraint is
not a primal or dual constraint, the \texttt{PRESOLVE\_UNKNOWN} symbol
can be used.  The \texttt{con\_typ} function is optional and does not
need to be specified for the presolve to work.

\begin{figure}
\begin{verbatim}
static void mcp_typ(void *d, int nnz, int *typ)
{
     int i;

     for (i = 0; i < nnz; i++)
     {
          typ[i] = PRESOLVE_LINEAR;
     }
     return;
}

static Presolve_Interface mcp_presolve =
{
     NULL,
     NULL, NULL,
     NULL, NULL,
     mcp_typ,
     NULL
};
\end{verbatim}
\caption{Presolve for linear complementary problems}\label{fig:mcp-linear}
\end{figure}

The four remaining routines are called when the presolve phase starts and 
finishes,
\texttt{start\_pre} and \texttt{finish\_pre}, and when the postsolve phase 
starts and finishes, \texttt{start\_post} and \texttt{finish\_post}.

\section{Solver Structures}\label{sec:solver}
The next ingredients to the interface are the structures and functions
associated with the particular algorithms.  The entry routine for solving 
an MCP with PATH 4.x is declared as:
\single\begin{verbatim}
     MCP_Termination Path_Solve(MCP *m, Information *info);
\end{verbatim}
\double
The corresponding declaration for the semismooth algorithm has identical
arguments but is called \texttt{Semi\_Solve}.  \texttt{MCP\_Termination}, is 
an enumerated type that indicates the termination status for the algorithm.  
The identifiers are documented in \tabref{mcp-termination}.  
The \texttt{Information} structure contains statistics about the solution 
process.  The key fields are documented in \tabref{mcp-information}.

\begin{table}
\centering
\caption{\texttt{MCP\_Termination} codes}\label{tab:mcp-termination}
\begin{tabular}{lp{10cm}}
Identifier & Meaning \\
\hline
MCP\_Solved & A solution to the problem was found. \\
MCP\_NoProgress & The algorithm stopped because it could not improve
upon the current iterate. \\
MCP\_MajorIterationLimit & An iteration limit was reached.\\
MCP\_MinorIterationLimit & The minor iteration limit was
reached.\\
MCP\_TimeLimit & Time limit was exceeded. \\
MCP\_UserInterrupt & The user requested that the solver stop
execution. \\
MCP\_BoundError & The problem is infeasible because $\ell_l > u_i$ for
some components. \\
MCP\_DomainError & A starting point where the function is defined
could not be found. \\
MCP\_Infeasible & The preprocessor determined the problem is
infeasible.\\
MCP\_Error & An internal error occurred in the algorithm.\\
\end{tabular}
\end{table}

\begin{table}
\centering
\caption{Key fields in \texttt{Information} structure}\label{tab:mcp-information}
\begin{tabular}{ll}
Field & Meaning \\
\hline
residual & Value of residual at final point. \\
major\_iterations & Major iterations taken. \\
minor\_iterations & Minor iterations taken. \\
crash\_iterations & Crash iterations taken. \\
function\_evaluations & Function evaluations performed. \\
jacobian\_evaluations & Jacobian evaluations performed. \\
gradient\_steps & Gradient steps taken. \\
restarts & Restarts used. \\
\end{tabular}
\end{table}

In addition, each algorithm defines a function used to install their
specific options and check the license.  For PATH 4.x, these function 
declarations are:
\single\begin{verbatim}
     void Path_AddOptions(Options_Interface *i);
     int  Path_CheckLicense(int n, int nnz);
\end{verbatim}
\double
The corresponding declaration for the semismooth algorithm has identical
arguments but is called \texttt{Semi\_AddOptions}.  The next section
describes how the options are used, while the following section describes
the license checking functionality.

\subsection{Options}
Associated with each algorithm is a set of options that can be used to
modify the algorithm's behavior.  \figref{mcp-options} contains the 
declaration for the header file associated with the options and 
\tabref{mcp-options} discusses the functions for setting and obtaining 
option values.

\begin{figure}
\begin{verbatim}
Options_Interface *Options_Create();
void Options_Destroy(Options_Interface *i);
void Options_Add(Options_Interface *i, Option_Set *opt);
void Options_Default(Options_Interface *i);

void Options_Display(Options_Interface *i);
void Options_Read(Options_Interface *i, char *filename);

void Options_Set(Options_Interface *i, char *opt);
void Options_SetBoolean(Options_Interface *i, char *opt, int val);
void Options_SetInt(Options_Interface *i, char *opt, int val);
void Options_SetDouble(Options_Interface *i, char *opt, double val);
void Options_SetOther(Options_Interface *i, char *opt, int val);

int    Options_GetBoolean(Options_Interface *i, char *opt);
int    Options_GetInt(Options_Interface *i, char *opt);
double Options_GetDouble(Options_Interface *i, char *opt);
int    Options_GetOther(Options_Interface *i, char *opt);
\end{verbatim}
\caption{Header file \texttt{Options.h}}\label{fig:mcp-options}
\end{figure}

\begin{table}
\centering
\caption{Functions for dealing with options}\label{tab:mcp-options}
\begin{tabular}{lp{10cm}}
Function & Description\\
\hline
Options\_Add & Add user defined options to the option set.\\
Options\_Create & Create a new option set. \\
Options\_Default & Set the options to their default values. \\
Options\_Destroy & Deallocate an option set.\\
Options\_Display & Display the values of the options.\\
Options\_GetBoolean & Obtain the value for the named boolean option. \\
Options\_GetInt & Obtain the value for the named integer option. \\
Options\_GetDouble & Obtain the value for the named double precision option. \\
Options\_GetOther & Obtain the value for the name option that takes on a different value. \\
Options\_Read & Read the options from the given file. \\
Options\_Set & Use the string to set an option value.  The string has the form ``$<$option$>$ $<$value$>$''. \\
Options\_SetBoolean & Set the named boolean options to the value specified. \\
Options\_SetInt & Set the names integer option to the value specified. \\
Options\_SetDouble & Set the named double precision option to the value specified. \\
Options\_SetOther & Set the named other option to the value specified.
\end{tabular}
\end{table}

Each algorithm has a particular set of options, contained in an
\texttt{Options\_Interface}, obtained using the \texttt{Options\_Create}
function.  The correct sequence for obtaining an algorithm specific option
set is:
\single\begin{verbatim}
     Options_Interface i;

     i = Options_Create();
     Path_AddOptions(i);
     ...
     Options_Destroy(i);
\end{verbatim}
\double
where \texttt{Path} can be replaced with any of the other available
solvers.  The interface created is the first argument to all of the option
functions.  Components in the option names are separated by underscore 
characters (\_).  Only the first three characters of each component are 
relevant.  Therefore, to change the \texttt{convergence\_tolerance} 
option to $10^{-4}$, we can issue the command:
\single\begin{verbatim}
     Options_SetDouble(i, "con_tol", 1e-4);
\end{verbatim}
\double
Complete lists of the options for PATH 4.x and SEMI can be found in the
available user documentation.

\subsection{License Management}
Users will need to specify licensing information prior to using PATH 4.x
or SEMI to solve any complementarity problems.  Licensing information is 
specified by a user either through the {\tt License\_SetString} function 
call or by setting the {\tt PATH\_LICENSE\_STRING} environment variable.  The 
format for the license string is the same for both methods.  For example,
\single\begin{verbatim}
  setenv PATH_LICENSE_STRING \
  "2866407532&Evaluation&&&USR&&10_12_2001&1000&PATH&GEN&1_3_2002&1_3_2002&0&0_0"
\end{verbatim}
\double
will set the {\tt PATH\_LICENSE\_STRING} environment variable on a Solaris or
Linux system to an evaluation license.  Alternatively, in the interface
code, the same license can be set with with the following function call
\single\begin{verbatim}
     License_SetString("2866407532&Evaluation&&&USR&&"
                       "10_12_2001&1000&PATH&GEN&"
                       "1_3_2002&1_3_2002&0&0_0");
\end{verbatim}
\double

Additional functions are found in \figref{mcp-license} which contains the 
declaration for the header file associated with license management.  
\tabref{mcp-license} discusses the functions for setting and obtaining 
particular values.  All of these functions return a nonzero value on
successful completion and a zero value on failure.

\begin{figure}
\begin{verbatim}
int License_SetString(const char *str);

int License_GetAlgorithms(char *algs, int len);
int License_GetArchitectures(char *archs, int len);
int License_GetExpiration(int *day, int *month, int *year);
int License_GetMaxVersion(int *ver);
int License_GetMaxBuild(int *day, int *month, int *year);
int License_GetRestrictions(int *n, int *nnz);

int License_GetDemoRestrictions(int *n, int *nnz);

License_Termination License_GetTermination(void);
License_Termination License_GetDemoTermination(void);
\end{verbatim}
\caption{Header file \texttt{License.h}}\label{fig:mcp-license}
\end{figure}

\begin{table}
\centering
\caption{Functions for dealing with license management}\label{tab:mcp-license}
\begin{tabular}{lp{10cm}}
Function & Description\\
\hline
License\_GetAlgorithms & Obtain the algorithms licensed.  Each algorithm is
specified by a sequence of four characters.  All of the licensed algorithms
are concatenated together in the string returned.\\
License\_GetArchitectures & Obtain the architectures licensed.  Each 
architecture is specified by a sequence of three characters.  All of the
licensed architectures are conctenated together in the string returned.\\
License\_GetDemoRestrictions & Obtain the size and number of nonzero
restrictions for demonstration licenses.\\
License\_GetDemoTermination & Obtain the termination status for the last time
the demonstration license was checked.\\
License\_GetExpiration & Obtain the expiration date for the license.\\
License\_GetMaxBuild & Obtain the maximum build date licensed for the library.\\
License\_GetMaxVersion & Obtain the maximum version number licensed for the library.\\
License\_GetRestrictions & Obtain the size and number of nonzero restrictions
for the license.\\
License\_GetTermination & Obtain the termination status for the last time
the license was checked.\\
License\_SetString & Set the string containing the license information.
\end{tabular}
\end{table}

Each algorithm has a method for explicitly checking the license.  The
declaration is
\single\begin{verbatim}
     int Path_CheckLicense(int n, int nnz)
\end{verbatim}
\double
where \texttt{Path} can be replaced with any of the other available
solvers.  A nonzero return value indicates that the license check
succeeded, while a zero value indicates that the license check failed.

\subsection{Workspace Allocation}
A workspace can be allocated for each algorithm which will be used on all
subsequent calls to the algorithm.  The functions needed are:
\single\begin{verbatim}
    void Path_Create(int maxSize, int maxNNZ);
    void Path_Destroy();
\end{verbatim}
\double
which will allocate and deallocate the workspaces for the PATH 4.x
algorithm.  For the semismooth algorithm, we can use the \texttt{Semi\_Create}
and \texttt{Semi\_Destroy} functions.  These workspace allocation routines 
are particularly useful when solving multiple complementarity problems in the 
same session because the workspaces will be reused.  That is, memory 
allocation will only be performed once.

\section{Control Structures}\label{sec:control}
The control structures are used to change the error reporting, interrupt 
handling, memory allocation, output, and timing mechanisms.  We discuss each 
of these control structures in the sequel and provide examples of their use.

\subsection{Error}
The functions contained in the \texttt{Error\_Interface} structure are used
to provide information concerning warnings and errors. 
\figref{mcp-error} contains the declaration for the component and 
\tabref{mcp-error} describes each of the functions. A warning tells the 
user about difficulties or nonstandard events encountered.  At the end of the 
warning, control should
be returned back to the algorithm.  An error on the other hand is fatal.
Execution stops at the end of the error routine.

\begin{figure}
\begin{verbatim}
typedef struct
{
    void *error_data;

    void (*error)(void *ed, char *msg);
    void (*warning)(void *ed, char *msg);
} Error_Interface;

void Error_SetInterface(Error_Interface *i);
\end{verbatim}
\caption{\texttt{Error\_Interface} declaration}\label{fig:mcp-error}
\end{figure}

\begin{table}
\centering
\caption{Error Object Functions}\label{tab:mcp-error}
\begin{tabular}{lp{13cm}}
Function & Description \\
\hline
error & (Optional) An error has been generated.  Do something 
with the information and exit from the program. \\
warning & (Optional) A warning has been generated.  Do something with
the information and return to the code.
\end{tabular}
\end{table}

An interesting contrast in the error function implementation can be found 
by comparing a standard implementation, which uses \texttt{exit},
to the MATLAB interface error routine, which uses \texttt{mexErrMsgTxt}.  
The code for the MATLAB \texttt{Error\_Interface} can be found in 
\figref{mcp-error-matlab}.  When \texttt{exit} is used, the operating 
system frees all previously allocated memory and the program terminates.  
In the case of MATLAB, we need to relinquish all allocated memory before
returning control back to MATLAB by using the \texttt{mexErrMsgTxt} routine.  
The use of \texttt{exit} is entirely inappropriate within a MATLAB session.  
Note that warnings are ignored in this implementation.

\begin{figure}
\begin{verbatim}
#include <stdio.h>
#include "Error_Interface.h"
#include "mex.h"

static void mat_error(void *ed, char *msg)
{
     mexErrMsgTxt(msg);
     return;
}

static Error_Interface mat_error_interface =
{
     NULL,
     mat_error,
     NULL
};
\end{verbatim}
\caption{MATLAB implementation of the \texttt{Error\_Interface}}\label{fig:mcp-error-matlab}
\end{figure}

\subsection{Interrupts}
Interrupts can be used to terminate an algorithm before it has finished
computing a solution.  \figref{mcp-interrupt} contains the declaration for 
the \texttt{Interrupt\_Interface} structure and \tabref{mcp-interrupt} 
describes each of the functions.  The default implementation uses the
\texttt{signal} standard function and issues an \texttt{Error} if
a user repeatedly types CTRL-C.

%An implementation using the
%\texttt{signal} function that terminates if the user types CTRL-C five
%times can be found in \figref{mcp-interrupt-five}.

\begin{figure}
\begin{verbatim}
typedef struct
{
    void *interrupt_data;

    void (*set)(void *id);
    void (*restore)(void *id);
    int  (*check)(void *id);
} Interrupt_Interface;

void Interrupt_SetInterface(Interrupt_Interface *i);
\end{verbatim}
\caption{\texttt{Interrupt\_Interface} declaration}\label{fig:mcp-interrupt}
\end{figure}

\begin{table}
\centering
\caption{Interrupt Object Functions}\label{tab:mcp-interrupt}
\begin{tabular}{ll}
Function & Description \\
\hline
set & (Required) Turn the interrupt handler on. \\
restore & (Required) Turn the interrupt handler off and restore the
default handler. \\
check & (Required) Check to see whether an interrupt has been issued. \\
\end{tabular}
\end{table}

\begin{comment}
\begin{figure}
\begin{verbatim}
static void (*sig_func)(int);
static int interrupted;
static int times;

static void five_handler(int sig)
{
     signal(SIGINT, SIG_IGN);

     interrupted = 1; times++;

     if (times >= 5)
     {
          Error("User termination.\n");
     }
     signal(SIGINT, five_handler);
     return;
}

void five_set(void *id)
{
     interrupted = 0; times = 0;

     sig_func = signal(SIGINT, five_handler);
     return;
}

void five_restore(void *id)
{
     signal(SIGINT, sig_func);
     return;
}

int five_check(void *id)
{
     return interrupted;
}

static Interrupt_Interface five_interface =
{
     NULL,
     five_set, five_restore, five_check
};
\end{verbatim}
\caption{Interrupt implementation that terminates after five CTRL-C's encountered}\label{fig:mcp-interrupt-five}
\end{figure}
\end{comment}

\subsection{Memory}
The memory structure contains all of the necessary functions to allocate and 
relinquish memory.  \figref{mcp-memory} contains the declaration for 
the \texttt{Memory\_Interface} structure and \tabref{mcp-memory} describes 
each of the functions.  We distinguish between two different types of memory
allocation: general memory allocation using \texttt{allocate} and 
the allocation necessary for the basis factors, 
\texttt{allocate\_factors}.  The general memory allocation routine is 
frequently called upon to allocate relatively small pieces of memory.  The 
factor allocation requires a single large section of memory to be obtained. 
Mechanisms optimized for these differing types of memory request patterns 
can be written.  We guarantee that within the algorithm only one set of 
factors will be allocated at a time.  However, the sequence 
\texttt{allocate\_factors}, \texttt{free\_factors} may be 
repeated within the code.

\begin{figure}
\begin{verbatim}
typedef struct
{
     void *memory_data;

     void * (*allocate)(void *data, long int n);
     void * (*allocate_factors)(void *data, long int n);
     void   (*free)(void *data, void *v);
     void   (*free_factors)(void *data, void *v);
} Memory_Interface;

void Memory_SetInterface(Memory_Interface *i);
\end{verbatim}
\caption{\texttt{Memory\_Interface} declaration}\label{fig:mcp-memory}
\end{figure}

\begin{table}
\centering
\caption{Memory Object Functions}\label{tab:mcp-memory}
\begin{tabular}{lp{12cm}}
Function & Description \\
\hline
allocate & (Required) Allocate the specified number of bytes
from memory and return a pointer to the allocated memory. \\
allocate\_factors & (Required) Allocate the specified number of 
bytes of memory and return a pointer to the allocated memory.  The amount of 
memory  requested in \texttt{allocate\_factors} is typically much greater than 
that requested in \texttt{allocate}. \\
free & (Required) Free the indicated memory allocated with 
\texttt{allocate}. \\
free\_factors & (Required) Deallocate the indicated memory previously 
allocated by \texttt{allocate\_factors}. \\
\end{tabular}
\end{table}

A standard implementation for the memory component uses the routines
\texttt{malloc} and \texttt{free}.  
More sophisticated implementations are 
possible.  For example, the GAMS implementation of these routines places the 
factors on the GAMS heap, a portion of memory previously allocated as 
workspace for the MPSGE \cite{rutherford:applied} preprocessor.

The MATLAB interface uses the \texttt{mxMalloc} routines for memory 
allocation.  The implementation of the memory subsystem for MATLAB can
be found in \figref{mcp-memory-matlab}.  Note that in MATLAB, both the
\texttt{allocate} and \texttt{allocate\_factors} routines are the
same.  This implementation guarantees that MATLAB will free all of the 
memory allocated within the mex function on termination.

\begin{figure}
\begin{verbatim}
#include <stdlib.h>
#include "Memory_Interface.h"
#include "mex.h"

static void *mat_allocate(void *md, long int n)
{
     void *v;

     v = (void *)mxMalloc(n);
     return v;
}

static void mat_free(void *md, void *v)
{
     mxFree(v);
     return;
}

static Memory_Interface mat_memory_interface =
{
     NULL,
     mat_allocate,
     mat_allocate,
     mat_free,
     mat_free
};
\end{verbatim}
\caption{Memory subsystem implementation for MATLAB}\label{fig:mcp-memory-matlab}
\end{figure}

\subsection{Output}
The output interface is key in order to support both C and FORTRAN 
output. \figref{mcp-output} contains the declaration for the 
\texttt{Output\_Interface} structure and \tabref{mcp-output} describes each 
of the functions.  The default implementation uses the \texttt{fprintf} 
command to write the messages to the indicated files.  The mode passed into
the function contains the descriptors:
\begin{description}
\item{\textbf{Output\_Log}} The log is used to demonstrate that the algorithm is making
progress.
\item{\textbf{Output\_Status}} The status file is used for debugging purposes
and records the essential information for this task.
\item{\textbf{Output\_Listing}} Output specified for listing file.
\end{description}
These descriptors are combined together with the `or' operator to indicate 
the locations for the output.  That is
\single\begin{verbatim}
     Output_Log | Output_Status
\end{verbatim}
\double
should send the message to both the log and status files.
Note that the \texttt{Output\_SetLog}, \texttt{Output\_SetStatus}, and
\texttt{Output\_SetListing} are convenience routines for use with the
default implementation.  

\begin{figure}
\begin{verbatim}
#define Output_Log 1
#define Output_Status 2
#define Output_Listing 4

typedef struct
{
     void *output_data;

     void (*print)(void *od, int mode, char *msg);
     void (*flush)(void *od, int mode);
} Output_Interface;

void Output_SetLog(FILE *f);
void Output_SetStatus(FILE *f);
void Output_SetListing(FILE *f);

void Output_SetInterface(Output_Interface *i);
\end{verbatim}
\caption{\texttt{Output\_Interface} declaration}\label{fig:mcp-output}
\end{figure}

\begin{table}
\centering
\caption{Output Object Functions}\label{tab:mcp-output}
\begin{tabular}{ll}
Function & Description \\
\hline
flush & (Optional) Flush the output for each of the 
specified files. \\
print & (Required) Output the indicated message to
each of the specified files. \\
\end{tabular}
\end{table}

%FORTRAN output depends upon the system and compiler.  For a SUN workstation,
%we can modify the output to be FORTRAN based as developed in
%\figref{mcp-output-fortran}.  The \texttt{fout} routine is written as
%a FORTRAN subroutine as given in \figref{mcp-output-fortran2}.

\begin{comment}
\begin{figure}
\begin{verbatim}
static char buffer[1024];
static int log_file = -1;
static int status_file = -1;
static int listing_file = -1;

static void for_out(int unitnum, char *buf)
{
     strcpy(buffer, buf);
     if (buffer[strlen(buffer) - 2] == '\n')
     {
          buffer[strlen(buffer) - 2] = '\0';
     }
     fout_(&log_file, buffer, strlen(buffer) - 1);
     return;
}

void for_print(void *data, int mode, char *buf)
{
     if ((mode & Output_Log) && (log_file >= 0))
     {
          for_out(log_file, buf);
     }

     if ((mode & Output_Status) && (status_file >= 0))
     {
         for_out(status_file, buf)
     }

     if ((mode & Output_Listing) && (listing_file >= 0))
     {
         for_out(listing_file, buf)
     }
     return;
}

static Output_Interface for_output_interface =
{
     NULL,
     for_print,
     NULL
};
\end{verbatim}
\caption{Output subsystem implementation for FORTRAN}\label{fig:mcp-output-fortran}
\end{figure}

\begin{figure}
\begin{verbatim}
      subroutine fout(unitnum, messag)
      integer unitnum
      character*(*) messag

      write (unitnum, 10) messag

 10   format (a)
      return
      end
\end{verbatim}
\caption{FORTRAN fout subroutine implementation}\label{fig:mcp-output-fortran2}
\end{figure}
\end{comment}

\subsection{Timer}
The final control structure is used to determine the amount of time spent
in particular sections of the code.  
\figref{mcp-timer} contains the declaration for 
the \texttt{Timer\_Interface} structure and \tabref{mcp-timer} describes 
each of the functions.  The default implementation uses the \texttt{clock}
standard function.

\begin{figure}
\begin{verbatim}
typedef struct
{
    void *timer_data;

    void * (*create)(void *td);
    void   (*destroy)(void *td, void *timer);
    void   (*start)(void *td, void *timer);
    double (*query)(void *td, void *timer);
} Timer_Interface;

void Timer_SetInterface(Timer_Interface *p);
\end{verbatim}
\caption{\texttt{Timer\_Interface} declaration}\label{fig:mcp-timer}
\end{figure}

\begin{table}
\centering
\caption{Timer Object Functions}\label{tab:mcp-timer}
\begin{tabular}{lp{13cm}}
Function & Description \\
\hline
create & (Required) Allocate and return a time structure. \\
destroy & (Required) Free the indicated time structure. \\
start &  (Required) Place the correct value for the current time in
the indicated structure. \\
query & (Required) Return the number of seconds elapsed since
the indicated structure has been started. \\
\end{tabular}
\end{table}

%System-dependent routines such as \texttt{rusage} on a UNIX platform can 
%be used to implement the time object.  \figref{mcp-timer-rusage} contains an
%implementation of the timer using the \texttt{rusage} function.

\begin{comment}
\begin{figure}
\begin{verbatim}
#include <stdio.h>
#include <sys/resource.h>
#include "Timer_Interface.h"

typedef struct
{
     struct rusage start;
     struct rusage curr;
} Timer;

void *rusage_create(void *td)
{
     Timer *t;

     t = (Timer *)malloc(sizeof(Timer));
     return (void *) t;
}

void rusage_destroy(void *td, void *timer)
{
     Timer *t = timer;
     Memory_Free(t);
     return;
}

void rusage_start(void *td, void *timer)
{
     Timer *t = timer;
     getrusage(RUSAGE_SELF, &(t->start));
     return;
}
\end{verbatim}
\caption{Timer subsystem implementation using \texttt{rusage}}\label{fig:mcp-timer-rusage}
\end{figure}

\begin{figure}
\begin{verbatim}
double rusage_query(void *td, void *timer)
{
     Timer *t = v;
     Double t1, t2, m1, m2, s1, s2, m, s;

     getrusage(RUSAGE_SELF, &(t->curr));

     m1 = (Double) t->curr.ru_utime.tv_usec;
     m2 = (Double) t->start.ru_utime.tv_usec;
     m = m1 - m2;

     s1 = (Double) t->curr.ru_utime.tv_sec;
     s2 = (Double) t->start.ru_utime.tv_sec;
     s = s1 - s2;

     t1 = s + m / MICROSEC;

     m1 = (Double) t->curr.ru_stime.tv_usec;
     m2 = (Double) t->start.ru_stime.tv_usec;
     m = m1 - m2;

     s1 = (Double) t->curr.ru_stime.tv_sec;
     s2 = (Double) t->start.ru_stime.tv_sec;
     s = s1 - s2;

     t2 = s + m / MICROSEC;

     return t1 + t2;
}

static Timer_Interface rusage_timer_interface =
{
     NULL,
     rusage_create,
     rusage_destroy,
     rusage_start,
     rusage_query
};
\end{verbatim}
\caption{Timer subsystem implementation using \texttt{rusage} (cont.)}\label{fig:mcp-timer-rusage2}
\end{figure}
\end{comment}

\section{Driver}\label{sec:driver}

Once the interfaces have been written and a solver has been chosen, a main 
driver routine must be specified.  Pseudocode for such a routine follows:
\single\begin{verbatim}
     1. Initialize control components.
     2. Create options set and default.
     3. Initialize user defined components.
     4. Work with the options.
     5. Create and setup an MCP structure.
     6. Solve the problem.
     7. Do something with the results.
     8. Destroy the MCP structure.
     9. Destroy the option set.
\end{verbatim}
\double
If special setups need to be performed for the system-dependent parts of
the code, they are done at the beginning.

As a concrete illustration, we have written a simple interface for 
solving a convex quadratic program using PATH 4.x or SEMI.  The quadratic 
program is to solve the minimization problem:
\begin{eqnarray}
\label{eqn:qp-model}
\begin{array}{rc}
\min_x & \frac{1}{2}x^TQx + c^Tx \\
\text{subject to} & Ax \geq b \\
 & \ell \leq x \leq u
\end{array}
\end{eqnarray}
where $Q \in \real^{n \times n}$ is a symmetric positive semidefinite matrix.
In order to find a solution, we write the Karush-Kuhn-Tucker optimality 
conditions \cite{karush:minima,kuhn.tucker:nonlinear} for \eqnref{qp-model} 
as the complementarity problem:
\begin{eqnarray*}
\begin{array}{lcl}
\ell \leq x \leq u & \perp & Qx - A^T\mu + c \\
0 \leq \mu & \perp & Ax - b \geq 0
\end{array}
\end{eqnarray*}

\begin{comment}
\begin{figure}
\begin{verbatim}
#define QP_LE -1
#define QP_EQ 0
#define QP_GE 1

typedef enum
{
     QP_Solved,
     QP_Unbounded,
     QP_Infeasible,
     QP_Error
} QP_Termination;

void QPMain(int variables, int constraints,
            int q_nz, int *q_i, int *q_j, double *q_ij, double *c,
            int a_nz, int *a_i, int *a_j, double *a_ij, double *b,
            int *c_type, double *lb, double *ub,
            QP_Termination *status, 
            double *z, double *mu, double *obj);
\end{verbatim}
\caption{Header file \texttt{QP.h}}\label{fig:qp-header}
\end{figure}
\end{comment}

A \texttt{QPMain} routine has been written which takes as inputs $Q$ and $A$ 
in (row,col,val) format and the vectors, $c$, $b$, $\ell$, $u$.  An additional 
vector is passed along, \texttt{c\_type}, telling the orientation of the 
constraints.  Note that the \texttt{QP\_Create} routine used in the following 
implementation simply forms the KKT conditions.
\single\begin{verbatim}
     void QPMain(int variables, int constraints,
                 int q_nz, int *q_i, int *q_j, double *q_ij, double *c,
                 int a_nz, int *a_i, int *a_j, double *a_ij, double *b,
                 int *c_type, double *lb, double *ub,
                 QP_Termination *status, 
                 double *z, double *mu, double *obj)
     {
          Options_Interface *o;
          MCP *m;
          MCP_Termination t;
          Information info;

          double *x;

          /* 1.  Initialize control components */
          /* 2.  Create options set and default */

          o = Options_Create();
          Path_AddOptions(o);
          Options_Default(o);

          /* 3. Initialize user defined components */

          QP_Create(variables, constraints, 
                    q_nnz, q_i, q_j, q_ij, c,
                    a_nnz, a_i, a_j, a_ij, b, c_type, 
                    z, mu, lb, ub);


          /* 4.  Work with the options */

          Options_Read(o, "path.opt");
          Options_Display(o);

          /* 5.  Create and setup an MCP structure */

          m = MCP_Create(problem.n, problem.nnz+1);
          MCP_Jacobian_Structure_Constant(m, 1);
          MCP_SetInterface(m, &mcp_interface);
          MCP_SetPresolveInterface(m, &mcp_presolve);

          /* 6.  Solve the problem */

          t = Path_Solve(m, &info);

          /* 7.  Do something with the results */

          if (t == MCP_Solved)
          {
               *status = QP_Solved;
          } else
          {
               /* code omitted */
          }

          x = MCP_GetX(m);

          for (i = 0; i < variables; i++)
          {
               z[i] = x[i];
          }

          for (i = 0; i < constraints; i++)
          {
               mu[i] = x[i + variables];
          }

          /* code omitted */

          /* 8.  Destroy the MCP structure */

          MCP_Destroy(m);
          QP_Destroy();

          /* 9.  Destroy the option set */

          Options_Destroy(o);
          return;
     }
\end{verbatim}
\double

\section{Summary}
This chapter documented the solver interface to PATH 4.x and SEMI used to 
support the environments in \chapref{environments} as well as simplified 
subroutine calls and a specialized convex quadratic programming interface.  
The main documentation for the interface was split into three parts: the 
problem structures used to specify a problem and its characteristics, the 
solver structures used to invoke a particular algorithm, and the control 
structures used to control output, memory allocation, and interrupt 
handling.  We then demonstrated the usage of the interface with a
quadratic programming interface.
In particular, the solver interface described can be used by applications
programmers to make PATH 4.x and SEMI available in other environments.

We remark that an earlier specification of the solver interface appeared
in \cite{ferris.munson:interfaces}.  The current solver interface 
specification, simplified subroutine call, 
and convex quadratic programming interface are new to this thesis.  A FORTRAN 
equivalent of the subroutine libraries is also available where the main 
program and function and Jacobian evaluation routines are written in FORTRAN.  
Finally, to support loadable library versions of the PATH 4.x and SEMI codes,
function pointers were used in the solver interface specification so that 
implementations of the control structures can be set at run time.

