%* glpk.latex *%

%***********************************************************************
%  This code is part of GLPK (GNU Linear Programming Kit).
%
%  Copyright (C) 2000, 01, 02, 03, 04, 05, 06, 07, 08 Andrew Makhorin,
%  Department for Applied Informatics, Moscow Aviation Institute,
%  Moscow, Russia. All rights reserved. E-mail: <mao@mai2.rcnet.ru>.
%
%  GLPK is free software: you can redistribute it and/or modify it
%  under the terms of the GNU General Public License as published by
%  the Free Software Foundation, either version 3 of the License, or
%  (at your option) any later version.
%
%  GLPK is distributed in the hope that it will be useful, but WITHOUT
%  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
%  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
%  License for more details.
%
%  You should have received a copy of the GNU General Public License
%  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
%***********************************************************************

\documentclass[11pt,draft]{report}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\thispagestyle{empty}

\begin{center}

\vspace*{1in}

\begin{huge}
\bf GNU Linear Programming Kit
\end{huge}

\vspace{0.5in}

\begin{LARGE}
\bf Reference Manual
\end{LARGE}

\vspace{0.5in}

\begin{LARGE}
\bf Version 4.31
\end{LARGE}

\vspace{0.5in}
\begin{Large}
\it(Draft Edition, September 2008)
\end{Large}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\vspace*{1in}

\vfill

\noindent
The GLPK package is part of the GNU Project released under the aegis of
GNU.

\medskip \noindent
Copyright \copyright{} 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
2008 Andrew Makhorin, Department for Applied Informatics, Moscow
Aviation Institute, Moscow, Russia. All rights reserved.

\medskip \noindent
Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
02110-1301, USA.

\medskip \noindent
Permission is granted to make and distribute verbatim copies of this
manual provided the copyright notice and this permission notice are
preserved on all copies.

\medskip \noindent
Permission is granted to copy and distribute modified versions of this
manual under the conditions for verbatim copying, provided also that the
entire resulting derived work is distributed under the terms of
a permission notice identical to this one.

\medskip \noindent
Permission is granted to copy and distribute translations of this manual
into another language, under the above conditions for modified versions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\tableofcontents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Introduction}

GLPK (\underline{G}NU \underline{L}inear \underline{P}rogramming
\underline{K}it) is a set of routines written in the ANSI C programming
language and organized in the form of a callable library. It is intended
for solving linear programming (LP), mixed integer programming (MIP),
and other related problems.

\section{LP problem}
\label{seclp}

GLPK assumes the following formulation of {\it linear programming (LP)}
problem:

\medskip

\noindent
\hspace{.5in} minimize (or maximize)
$$z = c_1x_{m+1} + c_2x_{m+2} + \dots + c_nx_{m+n} + c_0 \eqno (1.1)$$
\hspace{.5in} subject to linear constraints
$$
\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
x_1&=&a_{11}x_{m+1}&+&a_{12}x_{m+2}&+ \dots +&a_{1n}x_{m+n} \\
x_2&=&a_{21}x_{m+1}&+&a_{22}x_{m+2}&+ \dots +&a_{2n}x_{m+n} \\
\multicolumn{7}{c}
{.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
x_m&=&a_{m1}x_{m+1}&+&a_{m2}x_{m+2}&+ \dots +&a_{mn}x_{m+n} \\
\end{array} \eqno (1.2)
$$
\hspace{.5in} and bounds of variables
$$
\begin{array}{r@{\:}c@{\:}c@{\:}c@{\:}l}
l_1&\leq&x_1&\leq&u_1 \\
l_2&\leq&x_2&\leq&u_2 \\
\multicolumn{5}{c}{.\ \ .\ \ .\ \ .\ \ .}\\
l_{m+n}&\leq&x_{m+n}&\leq&u_{m+n} \\
\end{array} \eqno (1.3)
$$
where: $x_1, x_2, \dots, x_m$ are auxiliary variables;
$x_{m+1}, x_{m+2}, \dots, x_{m+n}$ are\linebreak structural variables;
$z$ is the objective function;
$c_1, c_2, \dots, c_n$ are objective coefficients;
$c_0$ is the constant term (``shift'') of the objective function;
$a_{11}, a_{12}, \dots, a_{mn}$ are constraint coefficients;
$l_1, l_2, \dots, l_{m+n}$ are lower bounds of variables;
$u_1, u_2, \dots, u_{m+n}$ are upper bounds of variables.

Auxiliary variables are also called {\it rows}, because they correspond
to rows of the constraint matrix (i.e. a matrix built of the constraint
coefficients). Similarly, structural variables are also called
{\it columns}, because they correspond to columns of the constraint
matrix.

Bounds of variables can be finite as well as infinite. Besides, lower
and upper bounds can be equal to each other. Thus, the following types
of variables are possible:
\begin{center}
\begin{tabular}{r@{}c@{}ll}
\multicolumn{3}{c}{Bounds of variable} & Type of variable \\
\hline
$-\infty <$ &$\ x_k\ $& $< +\infty$ & Free (unbounded) variable \\
$l_k \leq$ &$\ x_k\ $& $< +\infty$  & Variable with lower bound \\
$-\infty <$ &$\ x_k\ $& $\leq u_k$  & Variable with upper bound \\
$l_k \leq$ &$\ x_k\ $& $\leq u_k$   & Double-bounded variable \\
$l_k =$ &$\ x_k\ $& $= u_k$         & Fixed variable \\
\end{tabular}
\end{center}
\noindent
Note that the types of variables shown above are applicable to
structural as well as to auxiliary variables.

To solve the LP problem (1.1)---(1.3) is to find such values of all
structural and auxiliary variables, which:

$\bullet$ satisfy to all the linear constraints (1.2), and

$\bullet$ are within their bounds (1.3), and

$\bullet$ provide the smallest (in case of minimization) or the largest
(in case of maximization) value of the objective function (1.1).

\section{MIP problem}

{\it Mixed integer linear programming (MIP)} problem is LP problem in
which some variables are additionally required to be integer.

GLPK assumes that MIP problem has the same formulation as ordinary
(pure) LP problem (1.1)---(1.3), i.e. includes auxiliary and structural
variables, which may have lower and/or upper bounds. However, in case of
MIP problem some variables may be required to be integer. This
additional constraint means that a value of each {\it integer variable}
must be only integer number. (Should note that GLPK allows only
structural variables to be of integer kind.)

\section{Using the package}

\subsection{Brief example}

In order to understand what GLPK is from the user's standpoint,
consider the following simple LP problem:

\medskip

\noindent
\hspace{.5in} maximize
$$z = 10 x_1 + 6 x_2 + 4 x_3$$
\hspace{.5in} subject to
$$
\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
x_1 &+&x_2 &+&x_3 &\leq 100 \\
10 x_1 &+& 4 x_2 & +&5 x_3 & \leq 600 \\
2 x_1 &+& 2 x_2 & +& 6 x_3 & \leq 300 \\
\end{array}
$$
\hspace{.5in} where all variables are non-negative
$$x_1 \geq 0, \ x_2 \geq 0, \ x_3 \geq 0$$

At first this LP problem should be transformed to the standard form
(1.1)---(1.3). This can be easily done by introducing auxiliary
variables, by one for each original inequality constraint. Thus, the
problem can be reformulated as follows:

\medskip

\noindent
\hspace{.5in} maximize
$$z = 10 x_1 + 6 x_2 + 4 x_3$$
\hspace{.5in} subject to
$$
\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
p& = &x_1 &+&x_2 &+&x_3 \\
q& = &10 x_1 &+& 4 x_2 &+& 5 x_3 \\
r& = &2  x_1 &+& 2 x_2 &+& 6 x_3 \\
\end{array}
$$
\hspace{.5in} and bounds of variables
$$
\begin{array}{ccc}
\nonumber -\infty < p \leq 100 && 0 \leq x_1 < +\infty \\
\nonumber -\infty < q \leq 600 && 0 \leq x_2 < +\infty \\
\nonumber -\infty < r \leq 300 && 0 \leq x_3 < +\infty \\
\end{array}
$$
where $p, q, r$ are auxiliary variables (rows), and $x_1, x_2, x_3$ are
structural variables (columns).

The example C program shown below uses GLPK API routines in order to
solve this LP problem.\footnote{If you just need to solve LP or MIP
instance, you may write it in MPS or CPLEX LP format and then use the
GLPK stand-alone solver to obtain a solution. This is much less
time-consuming than programming in C with GLPK API routines.}

\newpage

\begin{verbatim}
/* sample.c */

#include <stdio.h>
#include <stdlib.h>
#include <glpk.h>

int main(void)
{     glp_prob *lp;
      int ia[1+1000], ja[1+1000];
      double ar[1+1000], z, x1, x2, x3;
s1:   lp = glp_create_prob();
s2:   glp_set_prob_name(lp, "sample");
s3:   glp_set_obj_dir(lp, GLP_MAX);
s4:   glp_add_rows(lp, 3);
s5:   glp_set_row_name(lp, 1, "p");
s6:   glp_set_row_bnds(lp, 1, GLP_UP, 0.0, 100.0);
s7:   glp_set_row_name(lp, 2, "q");
s8:   glp_set_row_bnds(lp, 2, GLP_UP, 0.0, 600.0);
s9:   glp_set_row_name(lp, 3, "r");
s10:  glp_set_row_bnds(lp, 3, GLP_UP, 0.0, 300.0);
s11:  glp_add_cols(lp, 3);
s12:  glp_set_col_name(lp, 1, "x1");
s13:  glp_set_col_bnds(lp, 1, GLP_LO, 0.0, 0.0);
s14:  glp_set_obj_coef(lp, 1, 10.0);
s15:  glp_set_col_name(lp, 2, "x2");
s16:  glp_set_col_bnds(lp, 2, GLP_LO, 0.0, 0.0);
s17:  glp_set_obj_coef(lp, 2, 6.0);
s18:  glp_set_col_name(lp, 3, "x3");
s19:  glp_set_col_bnds(lp, 3, GLP_LO, 0.0, 0.0);
s20:  glp_set_obj_coef(lp, 3, 4.0);
s21:  ia[1] = 1, ja[1] = 1, ar[1] =  1.0; /* a[1,1] =  1 */
s22:  ia[2] = 1, ja[2] = 2, ar[2] =  1.0; /* a[1,2] =  1 */
s23:  ia[3] = 1, ja[3] = 3, ar[3] =  1.0; /* a[1,3] =  1 */
s24:  ia[4] = 2, ja[4] = 1, ar[4] = 10.0; /* a[2,1] = 10 */
s25:  ia[5] = 3, ja[5] = 1, ar[5] =  2.0; /* a[3,1] =  2 */
s26:  ia[6] = 2, ja[6] = 2, ar[6] =  4.0; /* a[2,2] =  4 */
s27:  ia[7] = 3, ja[7] = 2, ar[7] =  2.0; /* a[3,2] =  2 */
s28:  ia[8] = 2, ja[8] = 3, ar[8] =  5.0; /* a[2,3] =  5 */
s29:  ia[9] = 3, ja[9] = 3, ar[9] =  6.0; /* a[3,3] =  6 */
s30:  glp_load_matrix(lp, 9, ia, ja, ar);
s31:  glp_simplex(lp, NULL);
s32:  z = glp_get_obj_val(lp);
s33:  x1 = glp_get_col_prim(lp, 1);
s34:  x2 = glp_get_col_prim(lp, 2);
s35:  x3 = glp_get_col_prim(lp, 3);
s36:  printf("\nz = %g; x1 = %g; x2 = %g; x3 = %g\n",
         z, x1, x2, x3);
s37:  glp_delete_prob(lp);
      return 0;
}

/* eof */
\end{verbatim}

The statement \verb|s1| creates a problem object. Being created the
object is initially empty. The statement \verb|s2| assigns a symbolic
name to the problem object.

The statement \verb|s3| calls the routine \verb|glp_set_obj_dir| in
order to set the optimization direction flag, where \verb|GLP_MAX| means
maximization.

The statement \verb|s4| adds three rows to the problem object.

The statement \verb|s5| assigns the symbolic name `\verb|p|' to the
first row, and the statement \verb|s6| sets the type and bounds of the
first row, where \verb|GLP_UP| means that the row has an upper bound.
The statements \verb|s7|, \verb|s8|, \verb|s9|, \verb|s10| are used in
the same way in order to assign the symbolic names `\verb|q|' and
`\verb|r|' to the second and third rows and set their types and bounds.

The statement \verb|s11| adds three columns to the problem object.

The statement \verb|s12| assigns the symbolic name `\verb|x1|' to the
first column, the statement \verb|s13| sets the type and bounds of the
first column, where \verb|GLP_LO| means that the column has an lower
bound, and the statement \verb|s14| sets the objective coefficient for
the first column. The statements \verb|s15|---\verb|s20| are used in the
same way in order to assign the symbolic names `\verb|x2|' and
`\verb|x3|' to the second and third columns and set their types, bounds,
and objective coefficients.

The statements \verb|s21|---\verb|s29| prepare non-zero elements of the
constraint matrix (i.e. constraint coefficients). Row indices of each
element are stored in the array \verb|ia|, column indices are stored in
the array \verb|ja|, and numerical values of corresponding elements are
stored in the array \verb|ar|. Then the statement \verb|s30| calls
the routine \verb|glp_load_matrix|, which loads information from these
three arrays into the problem object.

Now all data have been entered into the problem object, and therefore
the statement \verb|s31| calls the routine \verb|glp_simplex|, which is
a driver to the simplex method, in order to solve the LP problem. This
routine finds an optimal solution and stores all relevant information
back into the problem object.

The statement \verb|s32| obtains a computed value of the objective
function, and the statements \verb|s33|---\verb|s35| obtain computed
values of structural variables (columns), which correspond to the
optimal basic solution found by the solver.

The statement \verb|s36| writes the optimal solution to the standard
output. The printout may look like follows:

{\footnotesize
\begin{verbatim}
*     0:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
*     2:   objval =   7.333333333e+02   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND

z = 733.333; x1 = 33.3333; x2 = 66.6667; x3 = 0
\end{verbatim}

}

Finally, the statement \verb|s37| calls the routine
\verb|glp_delete_prob|, which frees all the memory allocated to the
problem object.

\subsection{Compiling}

The GLPK package has the only header file \verb|glpk.h|, which should
be available on compiling a C (or C++) program using GLPK API routines.

If the header file is installed in the default location
\verb|/usr/local/include|, the following typical command may be used to
compile, say, the example C program described above with the GNU C
compiler:

\begin{verbatim}
   $ gcc -c sample.c
\end{verbatim}

If \verb|glpk.h| is not in the default location, the corresponding
directory containing it should be made known to the C compiler through
\verb|-I| option, for example:

\begin{verbatim}
   $ gcc -I/foo/bar/glpk-4.15/include -c sample.c
\end{verbatim}

In any case the compilation results in an object file \verb|sample.o|.

\subsection{Linking}

The GLPK library is a single file \verb|libglpk.a|. (On systems which
support shared libraries there may be also a shared version of the
library \verb|libglpk.so|.)

If the library is installed in the default
location \verb|/usr/local/lib|, the following typical command may be
used to link, say, the example C program described above against with
the library:

\begin{verbatim}
   $ gcc sample.o -lglpk -lm
\end{verbatim}

If the GLPK library is not in the default location, the corresponding
directory containing it should be made known to the linker through
\verb|-L| option, for example:

\begin{verbatim}
   $ gcc -L/foo/bar/glpk-4.15 sample.o -lglpk -lm
\end{verbatim}

Depending on configuration of the package linking against with the GLPK
library may require the following optional libraries:

\bigskip

\begin{tabular}{@{}ll}
\verb|-lgmp|  & the GNU MP bignum library; \\
\verb|-lz|    & the zlib data compression library; \\
\verb|-lltdl| & the GNU ltdl shared support library. \\
\end{tabular}

\bigskip

\noindent
in which case corresponding libraries should be also made known to the
linker, for example:

\begin{verbatim}
   $ gcc sample.o -lglpk -lz -lltdl -lm
\end{verbatim}

For more details about configuration options of the GLPK package see
Appendix \ref{install}, page \pageref{install}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Basic API Routines}

This chapter describes GLPK API routines intended for using in
application programs.

\subsubsection*{Library header}

All GLPK API data types and routines are defined in the header file
\verb|glpk.h|. It should be included in all source files which use
GLPK API, either directly or indirectly through some other header file
as follows:

\begin{verbatim}
   #include <glpk.h>
\end{verbatim}

\subsubsection*{Error handling}

If some GLPK API routine detects erroneous or incorrect data passed by
the application program, it writes appropriate diagnostic messages to
the terminal and then abnormally terminates the application program.
In most practical cases this allows to simplify programming by avoiding
numerous checks of return codes. Thus, in order to prevent crashing the
application program should check all data, which are suspected to be
incorrect, before calling GLPK API routines.

Should note that this kind of error handling is used only in cases of
incorrect data passed by the application program. If, for example, the
application program calls some GLPK API routine to read data from an
input file and these data are incorrect, the GLPK API routine reports
about error in the usual way by means of the return code.

\subsubsection*{Thread safety}

Currently GLPK API routines are non-reentrant and therefore cannot be
used in multi-threaded programs.

\subsubsection*{Array indexing}

Normally all GLPK API routines start array indexing from 1, not from 0
(except the specially stipulated cases). This means, for example, that
if some vector $x$ of the length $n$ is passed as an array to some GLPK
API routine, the latter expects vector components to be placed in
locations \verb|x[1]|, \verb|x[2]|, \dots, \verb|x[n]|, and the location
\verb|x[0]| normally is not used.

In order to avoid indexing errors it is most convenient and most
reliable to declare the array \verb|x| as follows:

\begin{verbatim}
   double x[1+n];
\end{verbatim}

\noindent
or to allocate it as follows:

\begin{verbatim}
   double *x;
   . . .
   x = calloc(1+n, sizeof(double));
\end{verbatim}

\noindent
In both cases one extra location \verb|x[0]| is reserved that allows
passing the array to GLPK routines in a usual way.

\section{Problem object}

All GLPK API routines deal with so called {\it problem object}, which
is a program object of type \verb|glp_prob| and intended to represent
a particular LP or MIP instance.

The type \verb|glp_prob| is a data structure declared in the header
file \verb|glpk.h| as follows:

\begin{verbatim}
   typedef struct { ... } glp_prob;
\end{verbatim}

Problem objects (i.e. program objects of the \verb|glp_prob| type) are
allocated and managed internally by the GLPK API routines. The
application program should never use any members of the \verb|glp_prob|
structure directly and should deal only with pointers to these objects
(that is, \verb|glp_prob *| values).

\pagebreak

The problem object consists of five segments, which are:

$\bullet$ problem segment,

$\bullet$ basis segment,

$\bullet$ interior point segment,

$\bullet$ MIP segment, and

$\bullet$ control parameters and statistics segment.

\subsubsection*{Problem segment}

The {\it problem segment} contains original LP/MIP data, which
corresponds to the problem formulation (1.1)---(1.3) (see Section
\ref{seclp}, page \pageref{seclp}). It includes the following
components:

$\bullet$ rows (auxiliary variables),

$\bullet$ columns (structural variables),

$\bullet$ objective function, and

$\bullet$ constraint matrix.

Rows and columns have the same set of the following attributes:

$\bullet$ ordinal number,

$\bullet$ symbolic name (1 up to 255 arbitrary graphic characters),

$\bullet$ type (free, lower bound, upper bound, double bound, fixed),

$\bullet$ numerical values of lower and upper bounds,

$\bullet$ scale factor.

{\it Ordinal numbers} are intended for referencing rows and columns.
Row ordinal numbers are integers $1, 2, \dots, m$, and column ordinal
numbers are integers $1, 2, \dots, n$, where $m$ and $n$ are,
respectively, the current number of rows and columns in the problem
object.

{\it Symbolic names} are intended for informational purposes. They also
can be used for referencing rows and columns.

{\it Types and bounds} of rows (auxiliary variables) and columns
(structural variables) are explained above (see Section \ref{seclp},
page \pageref{seclp}).

{\it Scale factors} are used internally for scaling rows and columns of
the constraint matrix.

Information about the {\it objective function} includes numerical
values of objective coefficients and a flag, which defines the
optimization direction (i.e. minimization or maximization).

The {\it constraint matrix} is a $m \times n$ rectangular matrix built
of constraint coefficients $a_{ij}$, which defines the system of linear
constraints (1.2) (see Section \ref{seclp}, page \pageref{seclp}). This
matrix is stored in the problem object in both row-wise and column-wise
sparse formats.

Once the problem object has been created, the application program can
access and modify any components of the problem segment in arbitrary
order.

\subsubsection*{Basis segment}

The {\it basis segment} of the problem object keeps information related
to the current basic solution. It includes:

$\bullet$ row and column statuses,

$\bullet$ basic solution statuses,

$\bullet$ factorization of the current basis matrix, and

$\bullet$ basic solution components.

The {\it row and column statuses} define which rows and columns are
basic and which are non-basic. These statuses may be assigned either by
the application program of by some API routines. Note that these
statuses are always defined independently on whether the corresponding
basis is valid or not.

The {\it basic solution statuses} include the {\it primal status} and
the {\it dual status}, which are set by the simplex-based solver once
the problem has been solved. The primal status shows whether a primal
basic solution is feasible, infeasible, or undefined. The dual status
shows the same for a dual basic solution.

The {\it factorization of the basis matrix} is some factorized form
(like LU-factorization) of the current basis matrix (defined by the
current row and column statuses). The factorization is used by the
simplex-based solver and kept when the solver terminates the search.
This feature allows efficiently reoptimizing the problem after some
modifications (for example, after changing some bounds or objective
coefficients). It also allows performing the post-optimal analysis (for
example, computing components of the simplex table, etc.).

The {\it basic solution components} include primal and dual values of
all auxiliary and structural variables for the most recently obtained
basic solution.

\subsubsection*{Interior point segment}

The {\it interior point segment} is automatically allocated after the
problem has been solved using the interior point solver. It contains
interior point solution components, which include the solution status,
and primal and dual values of all auxiliary and structural variables.

\subsubsection*{MIP segment}

The {\it MIP segment} is used only for MIP problems. This segment
includes:

$\bullet$ column kinds,

$\bullet$ MIP solution status, and

$\bullet$ MIP solution components.

The {\it column kinds} define which columns (i.e. structural variables)
are integer and which are continuous.

The {\it MIP solution status} is set by the MIP solver and shows whether
a MIP solution is integer optimal, integer feasible (non-optimal), or
undefined.

The {\it MIP solution components} are computed by the MIP solver and
include primal values of all auxiliary and structural variables for the
most recently obtained MIP solution.

Note that in case of MIP problem the basis segment corresponds to
the optimal solution of LP relaxation, which is also available to the
application program.

Currently the search tree is not kept in the MIP segment. Therefore if
the search has been terminated, it cannot be continued.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\section{Problem creating and modifying routines}

\subsection{Create problem object}

\subsubsection*{Synopsis}

\begin{verbatim}
glp_prob *glp_create_prob(void);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_create_prob| creates a new problem object, which
initially is ``empty'', i.e. has no rows and columns.

\subsubsection*{Returns}

The routine returns a pointer to the created object, which should be
used in any subsequent operations on this object.

\subsection{Assign (change) problem name}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_prob_name(glp_prob *lp, const char *name);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_prob_name| assigns a given symbolic
\verb|name| (1 up to 255 characters) to the specified problem object.

If the parameter \verb|name| is \verb|NULL| or empty string, the routine
erases an existing symbolic name of the problem object.

\subsection{Assign (change) objective function name}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_obj_name(glp_prob *lp, const char *name);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_obj_name| assigns a given symbolic
\verb|name| (1 up to 255 characters) to the objective function of the
specified problem object.

If the parameter \verb|name| is \verb|NULL| or empty string, the routine
erases an existing symbolic name of the objective function.

\subsection{Set (change) optimization direction flag}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_obj_dir(glp_prob *lp, int dir);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_obj_dir| sets (changes) the optimization
direction flag (i.e. ``sense'' of the objective function) as specified
by the parameter \verb|dir|:

\begin{tabular}{@{}ll}
\verb|GLP_MIN| & minimization; \\
\verb|GLP_MAX| & maximization. \\
\end{tabular}

\noindent
(Note that by default the problem is minimization.)

\subsection{Add new rows to problem object}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_add_rows(glp_prob *lp, int nrs);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_add_rows| adds \verb|nrs| rows (constraints) to
the specified problem object. New rows are always added to the end of
the row list, so the ordinal numbers of existing rows are not changed.

Being added each new row is initially free (unbounded) and has empty
list of the constraint coefficients.

\subsubsection*{Returns}

The routine \verb|glp_add_rows| returns the ordinal number of the first
new row added to the problem object.

\subsection{Add new columns to problem object}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_add_cols(glp_prob *lp, int ncs);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_add_cols| adds \verb|ncs| columns (structural
variables) to the specified problem object. New columns are always added
to the end of the column list, so the ordinal numbers of existing
columns are not changed.

Being added each new column is initially fixed at zero and has empty
list of the constraint coefficients.

\subsubsection*{Returns}

The routine \verb|glp_add_cols| returns the ordinal number of the first
new column added to the problem object.

\subsection{Assign (change) row name}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_row_name(glp_prob *lp, int i, const char *name);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_row_name| assigns a given symbolic
\verb|name| (1 up to 255 characters) to \verb|i|-th row (auxiliary
variable) of the specified problem object.

If the parameter \verb|name| is \verb|NULL| or empty string, the routine
erases an existing name of $i$-th row.

\subsection{Assign (change) column name}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_col_name(glp_prob *lp, int j, const char *name);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_col_name| assigns a given symbolic
\verb|name| (1 up to 255 characters) to \verb|j|-th column (structural
variable) of the specified problem object.

If the parameter \verb|name| is \verb|NULL| or empty string, the routine
erases an existing name of $j$-th column.

\pagebreak

\subsection{Set (change) row bounds}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_row_bnds(glp_prob *lp, int i, int type,
      double lb, double ub);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_row_bnds| sets (changes) the type and bounds
of \verb|i|-th row (auxiliary variable) of the specified problem object.

The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type,
lower bound, and upper bound, respectively, as follows:

\begin{center}
\begin{tabular}{cr@{}c@{}ll}
Type & \multicolumn{3}{c}{Bounds} & Comment \\
\hline
\verb|GLP_FR| & $-\infty <$ &$\ x\ $& $< +\infty$
   & Free (unbounded) variable \\
\verb|GLP_LO| & $lb \leq$ &$\ x\ $& $< +\infty$
   & Variable with lower bound \\
\verb|GLP_UP| & $-\infty <$ &$\ x\ $& $\leq ub$
   & Variable with upper bound \\
\verb|GLP_DB| & $lb \leq$ &$\ x\ $& $\leq ub$
   & Double-bounded variable \\
\verb|GLP_FX| & $lb =$ &$\ x\ $& $= ub$
   & Fixed variable \\
\end{tabular}
\end{center}

\noindent
where $x$ is the auxiliary variable associated with $i$-th row.

If the row has no lower bound, the parameter \verb|lb| is ignored. If
the row has no upper bound, the parameter \verb|ub| is ignored. If the
row is an equality constraint (i.e. the corresponding auxiliary variable
is of fixed type), only the parameter \verb|lb| is used while the
parameter \verb|ub| is ignored.

Being added to the problem object each row is initially free, i.e. its
type is \verb|GLP_FR|.

\subsection{Set (change) column bounds}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_col_bnds(glp_prob *lp, int j, int type,
      double lb, double ub);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_col_bnds| sets (changes) the type and bounds
of \verb|j|-th column (structural variable) of the specified problem
object.

The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type,
lower bound, and upper bound, respectively, as follows:

\begin{center}
\begin{tabular}{cr@{}c@{}ll}
Type & \multicolumn{3}{c}{Bounds} & Comment \\
\hline
\verb|GLP_FR| & $-\infty <$ &$\ x\ $& $< +\infty$
   & Free (unbounded) variable \\
\verb|GLP_LO| & $lb \leq$ &$\ x\ $& $< +\infty$
   & Variable with lower bound \\
\verb|GLP_UP| & $-\infty <$ &$\ x\ $& $\leq ub$
   & Variable with upper bound \\
\verb|GLP_DB| & $lb \leq$ &$\ x\ $& $\leq ub$
   & Double-bounded variable \\
\verb|GLP_FX| & $lb =$ &$\ x\ $& $= ub$
   & Fixed variable \\
\end{tabular}
\end{center}

\noindent
where $x$ is the structural variable associated with $j$-th column.

If the column has no lower bound, the parameter \verb|lb| is ignored.
If the column has no upper bound, the parameter \verb|ub| is ignored.
If the column is of fixed type, only the parameter \verb|lb| is used
while the parameter \verb|ub| is ignored.

Being added to the problem object each column is initially fixed at
zero, i.e. its type is \verb|GLP_FX| and both bounds are 0.

\subsection{Set (change) objective coefficient or constant term}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_obj_coef(glp_prob *lp, int j, double coef);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_obj_coef| sets (changes) the objective
coefficient at \verb|j|-th column (structural variable). A new value of
the objective coefficient is specified by the parameter \verb|coef|.

If the parameter \verb|j| is 0, the routine sets (changes) the constant
term (``shift'') of the objective function.

\subsection{Set (replace) row of the constraint matrix}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_mat_row(glp_prob *lp, int i, int len,
      const int ind[], const double val[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_mat_row| stores (replaces) the contents of
\verb|i|-th row of the constraint matrix of the specified problem
object.

Column indices and numerical values of new row elements must be placed
in locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
\dots, \verb|val[len]|, respectively, where $0 \leq$ \verb|len| $\leq n$
is the new length of $i$-th row, $n$ is the current number of columns in
the problem object. Elements with identical column indices are not
allowed. Zero elements are allowed, but they are not stored in the
constraint matrix.

If the parameter \verb|len| is 0, the parameters \verb|ind| and/or
\verb|val| can be specified as \verb|NULL|.

\subsection{Set (replace) column of the constraint matrix}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_mat_col(glp_prob *lp, int j, int len,
      const int ind[], const double val[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_mat_col| stores (replaces) the contents of
\verb|j|-th column of the constraint matrix of the specified problem
object.

Row indices and numerical values of new column elements must be placed
in locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
\dots, \verb|val[len]|, respectively, where $0 \leq$ \verb|len| $\leq m$
is the new length of $j$-th column, $m$ is the current number of rows in
the problem object. Elements with identical row indices are not allowed.
Zero elements are allowed, but they are not stored in the constraint
matrix.

If the parameter \verb|len| is 0, the parameters \verb|ind| and/or
\verb|val| can be specified as \verb|NULL|.

\subsection{Load (replace) the whole constraint matrix}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_load_matrix(glp_prob *lp, int ne, const int ia[],
      const int ja[], const double ar[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_load_matrix| loads the constraint matrix passed
in  the arrays \verb|ia|, \verb|ja|, and \verb|ar| into the specified
problem object. Before loading the current contents of the constraint
matrix is destroyed.

Constraint coefficients (elements of the constraint matrix) must be
specified as triplets (\verb|ia[k]|, \verb|ja[k]|, \verb|ar[k]|) for
$k=1,\dots,ne$, where \verb|ia[k]| is the row index, \verb|ja[k]| is
the column index, and \verb|ar[k]| is a numeric value of corresponding
constraint coefficient. The parameter \verb|ne| specifies the total
number of (non-zero) elements in the matrix to be loaded. Coefficients
with identical indices are not allowed. Zero coefficients are allowed,
however, they are not stored in the constraint matrix.

If the parameter \verb|ne| is 0, the parameters \verb|ia|, \verb|ja|,
and/or \verb|ar| can be specified as \verb|NULL|.

\subsection{Delete rows from problem object}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_del_rows(glp_prob *lp, int nrs, const int num[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_del_rows| deletes rows from the specified problem
ob-\linebreak ject. Ordinal numbers of rows to be deleted should be
placed in locations \verb|num[1]|, \dots, \verb|num[nrs]|, where
${\tt nrs}>0$.

Note that deleting rows involves changing ordinal numbers of other
rows remaining in the problem object. New ordinal numbers of the
remaining rows are assigned under the assumption that the original
order of rows is not changed. Let, for example, before deletion there
be five rows $a$, $b$, $c$, $d$, $e$ with ordinal numbers 1, 2, 3, 4, 5,
and let rows $b$ and $d$ have been deleted. Then after deletion the
remaining rows $a$, $c$, $e$ are assigned new oridinal numbers 1, 2, 3.

\subsection{Delete columns from problem object}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_del_cols(glp_prob *lp, int ncs, const int num[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_del_cols| deletes columns from the specified
problem object. Ordinal numbers of columns to be deleted should be
placed in locations \verb|num[1]|, \dots, \verb|num[ncs]|, where
${\tt ncs}>0$.

Note that deleting columns involves changing ordinal numbers of other
columns remaining in the problem object. New ordinal numbers of the
remaining columns are assigned under the assumption that the original
order of columns is not changed. Let, for example, before deletion there
be six columns $p$, $q$, $r$, $s$, $t$, $u$ with ordinal numbers 1, 2,
3, 4, 5, 6, and let columns $p$, $q$, $s$ have been deleted. Then after
deletion the remaining columns $r$, $t$, $u$ are assigned new ordinal
numbers 1, 2, 3.

\subsection{Erase problem object content}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_erase_prob(glp_prob *lp);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_erase_prob| erases the content of the specified
problem object. The effect of this operation is the same as if the
problem object would be deleted with the routine \verb|glp_delete_prob|
and then created anew with the routine \verb|glp_create_prob|, with the
only exception that the handle (pointer) to the problem object remains
valid.

\subsection{Delete problem object}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_delete_prob(glp_prob *lp);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_delete_prob| deletes a problem object, which the
parameter \verb|lp| points to, freeing all the memory allocated to this
object.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\section{Problem retrieving routines}

\subsection{Retrieve problem name}

\subsubsection*{Synopsis}

\begin{verbatim}
const char *glp_get_prob_name(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_prob_name| returns a pointer to an internal
buffer, which contains symbolic name of the problem. However, if the
problem has no assigned name, the routine returns \verb|NULL|.

\subsection{Retrieve objective function name}

\subsubsection*{Synopsis}

\begin{verbatim}
const char *glp_get_obj_name(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_obj_name| returns a pointer to an internal
buffer, which contains symbolic name assigned to the objective
function. However, if the objective function has no assigned name, the
routine returns \verb|NULL|.

\subsection{Retrieve optimization direction flag}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_obj_dir(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_obj_dir| returns the optimization direction
flag (i.e. ``sense'' of the objective function):

\begin{tabular}{@{}ll}
\verb|GLP_MIN| & minimization; \\
\verb|GLP_MAX| & maximization. \\
\end{tabular}

\pagebreak

\subsection{Retrieve number of rows}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_num_rows(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_num_rows| returns the current number of rows
in the specified problem object.

\subsection{Retrieve number of columns}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_num_cols(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_num_cols| returns the current number of
columns the specified problem object.

\subsection{Retrieve row name}

\subsubsection*{Synopsis}

\begin{verbatim}
const char *glp_get_row_name(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_row_name| returns a pointer to an internal
buffer, which contains a symbolic name assigned to \verb|i|-th row.
However, if the row has no assigned name, the routine returns
\verb|NULL|.

\subsection{Retrieve column name}

\subsubsection*{Synopsis}

\begin{verbatim}
const char *glp_get_col_name(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_col_name| returns a pointer to an internal
buffer, which contains a symbolic name assigned to \verb|j|-th column.
However, if the column has no assigned name, the routine returns
\verb|NULL|.

\subsection{Retrieve row type}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_row_type(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_row_type| returns the type of \verb|i|-th
row, i.e. the type of corresponding auxiliary variable, as follows:

\begin{tabular}{@{}ll}
\verb|GLP_FR| & free (unbounded) variable; \\
\verb|GLP_LO| & variable with lower bound; \\
\verb|GLP_UP| & variable with upper bound; \\
\verb|GLP_DB| & double-bounded variable; \\
\verb|GLP_FX| & fixed variable. \\
\end{tabular}

\subsection{Retrieve row lower bound}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_row_lb(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_row_lb| returns the lower bound of
\verb|i|-th row, i.e. the lower bound of corresponding auxiliary
variable. However, if the row has no lower bound, the routine returns
\verb|-DBL_MAX|.

\subsection{Retrieve row upper bound}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_row_ub(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_row_ub| returns the upper bound of
\verb|i|-th row, i.e. the upper bound of corresponding auxiliary
variable. However, if the row has no upper bound, the routine returns
\verb|+DBL_MAX|.

\subsection{Retrieve column type}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_col_type(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_col_type| returns the type of \verb|j|-th
column, i.e. the type of corresponding structural variable, as follows:

\begin{tabular}{@{}ll}
\verb|GLP_FR| & free (unbounded) variable; \\
\verb|GLP_LO| & variable with lower bound; \\
\verb|GLP_UP| & variable with upper bound; \\
\verb|GLP_DB| & double-bounded variable; \\
\verb|GLP_FX| & fixed variable. \\
\end{tabular}

\subsection{Retrieve column lower bound}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_col_lb(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_col_lb| returns the lower bound of
\verb|j|-th column, i.e. the lower bound of corresponding structural
variable. However, if the column has no lower bound, the routine returns
\verb|-DBL_MAX|.

\subsection{Retrieve column upper bound}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_col_ub(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_col_ub| returns the upper bound of
\verb|j|-th column, i.e. the upper bound of corresponding structural
variable. However, if the column has no upper bound, the routine returns
\verb|+DBL_MAX|.

\subsection{Retrieve objective coefficient or constant term}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_obj_coef(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_obj_coef| returns the objective coefficient
at \verb|j|-th structural variable (column).

If the parameter \verb|j| is 0, the routine returns the constant term
(``shift'') of the objective function.

\subsection{Retrieve number of constraint coefficients}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_num_nz(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_num_nz| returns the number of non-zero
elements in the constraint matrix of the specified problem object.

\subsection{Retrieve row of the constraint matrix}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_mat_row(glp_prob *lp, int i, int ind[],
      double val[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_get_mat_row| scans (non-zero) elements of
\verb|i|-th row of the constraint matrix of the specified problem object
and stores their column indices and numeric values to locations
\verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
\verb|val[len]|, respectively, where $0\leq{\tt len}\leq n$ is the
number of elements in $i$-th row, $n$ is the number of columns.

The parameter \verb|ind| and/or \verb|val| can be specified as
\verb|NULL|, in which case corresponding information is not stored.

\subsubsection*{Returns}

The routine \verb|glp_get_mat_row| returns the length \verb|len|, i.e.
the number of (non-zero) elements in \verb|i|-th row.

\subsection{Retrieve column of the constraint matrix}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_mat_col(glp_prob *lp, int j, int ind[],
      double val[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_get_mat_col| scans (non-zero) elements of
\verb|j|-th column of the constraint matrix of the specified problem
object and stores their row indices and numeric values to locations
\verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
\verb|val[len]|, respectively, where $0\leq{\tt len}\leq m$ is the
number of elements in $j$-th column, $m$ is the number of rows.

The parameter \verb|ind| and/or \verb|val| can be specified as
\verb|NULL|, in which case corresponding information is not stored.

\subsubsection*{Returns}

The routine \verb|glp_get_mat_col| returns the length \verb|len|, i.e.
the number of (non-zero) elements in \verb|j|-th column.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\section{Row and column searching routines}

\subsection{Create the name index}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_create_index(glp_prob *lp);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_create_index| creates the name index for the
specified problem object. The name index is an auxiliary data structure,
which is intended to quickly (i.e. for logarithmic time) find rows and
columns by their names.

This routine can be called at any time. If the name index already
exists, the routine does nothing.

\subsection{Find row by its name}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_find_row(glp_prob *lp, const char *name);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_find_row| returns the ordinal number of a row,
which is assigned (by the routine \verb|glp_set_row_name|) the specified
symbolic \verb|name|. If no such row exists, the routine returns 0.

\subsection{Find column by its name}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_find_col(glp_prob *lp, const char *name);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_find_col| returns the ordinal number of a column,
which is assigned (by the routine \verb|glp_set_col_name|) the specified
symbolic \verb|name|. If no such column exists, the routine returns 0.

\subsection{Delete the name index}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_delete_index(glp_prob *lp);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_delete_index| deletes the name index previously
created by the routine \verb|glp_create_index| and frees the memory
allocated to this auxiliary data structure.

This routine can be called at any time. If the name index does not
exist, the routine does nothing.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\section{Problem scaling routines}

\subsection{Background}

In GLPK the {\it scaling} means a linear transformation applied to the
constraint matrix to improve its numerical properties.\footnote{In many
cases a proper scaling allows making the constraint matrix to be better
conditioned, i.e. decreasing its condition number, that makes
computations numerically more stable.}

The main equality is the following:
$$\widetilde{A}=RAS,\eqno(2.1)$$
where $A=(a_{ij})$ is the original constraint matrix, $R=(r_{ii})>0$ is
a diagonal matrix used to scale rows (constraints), $S=(s_{jj})>0$ is a
diagonal matrix used to scale columns (variables), $\widetilde{A}$ is
the scaled constraint matrix.

From (2.1) it follows that in the {\it scaled} problem instance each
original constraint coefficient $a_{ij}$ is replaced by corresponding
scaled constraint coefficient:
$$\widetilde{a}_{ij}=r_{ii}a_{ij}s_{jj}.\eqno(2.2)$$

Note that the scaling is performed internally and therefore
transparently to the user. This means that on API level the user always
deal with unscaled data.

Scale factors $r_{ii}$ and $s_{jj}$ can be set or changed at any time
either directly by the application program in a problem specific way
(with the routines \verb|glp_set_rii| and \verb|glp_set_sjj|), or by
some API routines intended for automatic scaling.

\subsection{Set (change) row scale factor}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_rii(glp_prob *lp, int i, double rii);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_rii| sets (changes) the scale factor $r_{ii}$
for $i$-th row of the specified problem object.

\subsection{Set (change) column scale factor}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_sjj(glp_prob *lp, int j, double sjj);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_sjj| sets (changes) the scale factor $s_{jj}$
for $j$-th column of the specified problem object.

\subsection{Retrieve row scale factor}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_rii(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_rii| returns current scale factor $r_{ii}$ for
$i$-th row of the specified problem object.

\subsection{Retrieve column scale factor}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_sjj(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_sjj| returns current scale factor $s_{jj}$ for
$j$-th column of the specified problem object.

\subsection{Scale problem data}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_scale_prob(glp_prob *lp, int flags);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_scale_prob| performs automatic scaling of problem
data for the specified problem object.

The parameter \verb|flags| specifies scaling options used by the
routine. The options can be combined with the bitwise OR operator and
may be the following:

\begin{tabular}{@{}ll}
\verb|GLP_SF_GM| & perform geometric mean scaling;\\
\verb|GLP_SF_EQ| & perform equilibration scaling;\\
\verb|GLP_SF_2N| & round scale factors to nearest power of two;\\
\verb|GLP_SF_SKIP| & skip scaling, if the problem is well scaled.\\
\end{tabular}

The parameter \verb|flags| may be specified as \verb|GLP_SF_AUTO|, in
which case the routine chooses the scaling options automatically.

\subsection{Unscale problem data}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_unscale_prob(glp_prob *lp);
\end{verbatim}

The routine \verb|glp_unscale_prob| performs unscaling of problem data
for the specified problem object.

``Unscaling'' means replacing the current scaling matrices $R$ and $S$
by unity matrices that cancels the scaling effect.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\section{LP basis constructing routines}

\subsection{Background}

To start the search the simplex method needs a valid initial basis. In
GLPK the basis is completely defined by a set of {\it statuses} assigned
to {\it all} (auxiliary and structural) variables, where the status may
be one of the following:

\begin{tabular}{@{}ll}
\verb|GLP_BS| & basic variable;\\
\verb|GLP_NL| & non-basic variable having active lower bound;\\
\verb|GLP_NU| & non-basic variable having active upper bound;\\
\verb|GLP_NF| & non-basic free variable;\\
\verb|GLP_NS| & non-basic fixed variable.\\
\end{tabular}

The basis is {\it valid}, if the basis matrix, which is a matrix built
of columns of the augmented constraint matrix $(I\:|-A)$ corresponding
to basic variables, is non-singular. This, in particular, means that
the number of basic variables must be the same as the number of rows in
the problem object. (For more details see Section \ref{lpbasis}, page
\pageref{lpbasis}.)

Any initial basis may be constructed (or restored) with the API
routines \verb|glp_set_row_stat| and \verb|glp_set_col_stat| by
assigning appropriate statuses to auxiliary and structural variables.
Another way to construct an initial basis is to use API routines like
\verb|glp_adv_basis|, which implement so called
{\it crashing}.\footnote{This term is from early linear programming
systems and means a heuristic to construct a valid initial basis.} Note
that on normal exit the simplex solver remains the basis valid, so in
case of reoptimization there is no need to construct an initial basis
from scratch.

\subsection{Set (change) row status}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_row_stat(glp_prob *lp, int i, int stat);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_row_stat| sets (changes) the current status
of \verb|i|-th row (auxiliary variable) as specified by the parameter
\verb|stat|:

\begin{tabular}{@{}lp{104.2mm}@{}}
\verb|GLP_BS| & make the row basic (make the constraint inactive); \\
\verb|GLP_NL| & make the row non-basic (make the constraint active); \\
\end{tabular}

\newpage

\begin{tabular}{@{}lp{104.2mm}@{}}
\verb|GLP_NU| & make the row non-basic and set it to the upper bound;
   if the row is not double-bounded, this status is equivalent to
   \verb|GLP_NL| (only in the case of this routine); \\
\verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this
   routine); \\
\verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this
   routine). \\
\end{tabular}

\subsection{Set (change) column status}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_col_stat(glp_prob *lp, int j, int stat);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_col_stat sets| (changes) the current status
of \verb|j|-th column (structural variable) as specified by the
parameter \verb|stat|:

\begin{tabular}{@{}lp{104.2mm}@{}}
\verb|GLP_BS| & make the column basic; \\
\verb|GLP_NL| & make the column non-basic; \\
\verb|GLP_NU| & make the column non-basic and set it to the upper
   bound; if the column is not double-bounded, this status is equivalent
   to \verb|GLP_NL| (only in the case of this routine); \\
\verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this
   routine); \\
\verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this
   routine).
\end{tabular}

\subsection{Construct standard initial LP basis}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_std_basis(glp_prob *lp);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_std_basis| constructs the ``standard'' (trivial)
initial LP basis for the specified problem object.

In the ``standard'' LP basis all auxiliary variables (rows) are basic,
and all structural variables (columns) are non-basic (so the
corresponding basis matrix is unity).

\newpage

\subsection{Construct advanced initial LP basis}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_adv_basis(glp_prob *lp, int flags);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_adv_basis| constructs an advanced initial LP
basis for the specified problem object.

The parameter \verb|flags| is reserved for use in the future and must
be specified as zero.

In order to construct the advanced initial LP basis the routine does
the following:

1) includes in the basis all non-fixed auxiliary variables;

2) includes in the basis as many non-fixed structural variables as
possible keeping the triangular form of the basis matrix;

3) includes in the basis appropriate (fixed) auxiliary variables to
complete the basis.

As a result the initial LP basis has as few fixed variables as possible
and the corresponding basis matrix is triangular.

\subsection{Construct Bixby's initial LP basis}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_cpx_basis(glp_prob *lp);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_cpx_basis| constructs an initial basis for the
specified problem object with the algorithm proposed by
R.~Bixby.\footnote{Robert E. Bixby, ``Implementing the Simplex Method:
The Initial Basis.'' ORSA Journal on Computing, Vol. 4, No. 3, 1992,
pp. 267-84.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\section{Simplex method routines}

The {\it simplex method} is a well known efficient numerical procedure
to solve LP problems.

On each iteration the simplex method transforms the original system of
equaility constraints (1.2) resolving them through different sets of
variables to an equivalent system called {\it the simplex table} (or
sometimes {\it the simplex tableau}), which has the following form:
$$
\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
z&=&d_1(x_N)_1&+&d_2(x_N)_2&+ \dots +&d_n(x_N)_n \\
(x_B)_1&=&\xi_{11}(x_N)_1& +& \xi_{12}(x_N)_2& + \dots +&
   \xi_{1n}(x_N)_n \\
(x_B)_2&=& \xi_{21}(x_N)_1& +& \xi_{22}(x_N)_2& + \dots +&
   \xi_{2n}(x_N)_n \\
\multicolumn{7}{c}
{.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
(x_B)_m&=&\xi_{m1}(x_N)_1& +& \xi_{m2}(x_N)_2& + \dots +&
   \xi_{mn}(x_N)_n \\
\end{array} \eqno (2.1)
$$
where: $(x_B)_1, (x_B)_2, \dots, (x_B)_m$ are basic variables;
$(x_N)_1, (x_N)_2, \dots, (x_N)_n$ are non-basic variables;
$d_1, d_2, \dots, d_n$ are reduced costs;
$\xi_{11}, \xi_{12}, \dots, \xi_{mn}$ are coefficients of the
simplex table. (May note that the original LP problem (1.1)---(1.3) also
has the form of a simplex table, where all equalities are resolved
through auxiliary variables.)

From the linear programming theory it is known that if an optimal
solution of the LP problem (1.1)---(1.3) exists, it can always be
written in the form (2.1), where non-basic variables are set on their
bounds while values of the objective function and basic variables are
determined by the corresponding equalities of the simplex table.

A set of values of all basic and non-basic variables determined by the
simplex table is called {\it basic solution}. If all basic variables are
within their bounds, the basic solution is called {\it (primal)
feasible}, otherwise it is called {\it (primal) infeasible}. A feasible
basic solution, which provides a smallest (in case of minimization) or
a largest (in case of maximization) value of the objective function is
called {\it optimal}. Therefore, for solving LP problem the simplex
method tries to find its optimal basic solution.

Primal feasibility of some basic solution may be stated by simple
checking if all basic variables are within their bounds. Basic solution
is optimal if additionally the following optimality conditions are
satisfied for all non-basic variables:
\begin{center}
\begin{tabular}{lcc}
Status of $(x_N)_j$ & Minimization & Maximization \\
\hline
$(x_N)_j$ is free & $d_j = 0$ & $d_j = 0$ \\
$(x_N)_j$ is on its lower bound & $d_j \geq 0$ & $d_j \leq 0$ \\
$(x_N)_j$ is on its upper bound & $d_j \leq 0$ & $d_j \geq 0$ \\
\end{tabular}
\end{center}
In other words, basic solution is optimal if there is no non-basic
variable, which changing in the feasible direction (i.e. increasing if
it is free or on its lower bound, or decreasing if it is free or on its
upper bound) can improve (i.e. decrease in case of minimization or
increase in case of maximization) the objective function.

If all non-basic variables satisfy to the optimality conditions shown
above (independently on whether basic variables are within their bounds
or not), the basic solution is called {\it dual feasible}, otherwise it
is called {\it dual infeasible}.

It may happen that some LP problem has no primal feasible solution due
to incorrect formulation --- this means that its constraints conflict
with each other. It also may happen that some LP problem has unbounded
solution again due to incorrect formulation --- this means that some
non-basic variable can improve the objective function, i.e. the
optimality conditions are violated, and at the same time this variable
can infinitely change in the feasible direction meeting no resistance
from basic variables. (May note that in the latter case the LP problem
has no dual feasible solution.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Solve LP problem with the simplex method}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_simplex(glp_prob *lp, const glp_smcp *parm);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_simplex| is a driver to the LP solver based on
the simplex method. This routine retrieves problem data from the
specified problem object, calls the solver to solve the problem
instance, and stores results of computations back into the problem
object.

The simplex solver has a set of control parameters. Values of the
control parameters can be passed in the structure \verb|glp_smcp|,
which the parameter \verb|parm| points to. For detailed description of
this structure see paragraph ``Control parameters'' below.
Before specifying some control parameters the application program
should initialize the structure \verb|glp_smcp| by default values of
all control parameters using the routine \verb|glp_init_smcp| (see the
next subsection). This is needed for backward compatibility, because in
the future there may appear new members in the structure
\verb|glp_smcp|.

The parameter \verb|parm| can be specified as \verb|NULL|, in which
case the solver uses default settings.

\subsubsection*{Returns}

\def\arraystretch{1}

\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
0 & The LP problem instance has been successfully solved. (This code
does {\it not} necessarily mean that the solver has found optimal
solution. It only means that the solution process was successful.) \\
\verb|GLP_EBADB| & Unable to start the search, because the initial basis
specified in the problem object is invalid---the number of basic
(auxiliary and structural) variables is not the same as the number of
rows in the problem object.\\
\verb|GLP_ESING| & Unable to start the search, because the basis matrix
corresponding to the initial basis is singular within the working
precision.\\
\verb|GLP_ECOND| & Unable to start the search, because the basis matrix
corresponding to the initial basis is ill-conditioned, i.e. its
condition number is too large.\\
\verb|GLP_EBOUND| & Unable to start the search, because some
double-bounded (auxiliary or structural) variables have incorrect
bounds.\\ 
\verb|GLP_EFAIL| & The search was prematurely terminated due to the
solver failure.\\
\verb|GLP_EOBJLL| & The search was prematurely terminated, because the
objective function being maximized has reached its lower limit and
continues decreasing (the dual simplex only).\\
\verb|GLP_EOBJUL| & The search was prematurely terminated, because the
objective function being minimized has reached its upper limit and
continues increasing (the dual simplex only).\\
\verb|GLP_EITLIM| & The search was prematurely terminated, because the
simplex iteration limit has been exceeded.\\
\verb|GLP_ETMLIM| & The search was prematurely terminated, because the
time limit has been exceeded.\\
\verb|GLP_ENOPFS| & The LP problem instance has no primal feasible
solution (only if the LP presolver is used).\\
\verb|GLP_ENODFS| & The LP problem instance has no dual feasible
solution (only if the LP presolver is used).\\
\end{tabular}

\subsubsection*{Using built-in LP presolver}

The simplex solver has {\it built-in LP presolver}, which is a
subprogram that transforms the original LP problem specified in the
problem object to an equivalent LP problem, which may be easier for
solving with the simplex method than the original one. This is attained
mainly due to reducing the problem size and improving its numeric
properties (for example, by removing some inactive constraints or by
fixing some non-basic variables). Once the transformed LP problem has
been solved, the presolver transforms its basic solution back to
the corresponding basic solution of the original problem.

Presolving is an optional feature of the routine \verb|glp_simplex|,
and by default it is disabled. In order to enable the LP presolver the
control parameter \verb|presolve| should be set to \verb|GLP_ON| (see
paragraph ``Control parameters'' below). Presolving may be used when
the problem instance is solved for the first time. However, on
performing re-optimization the presolver should be disabled.

The presolving procedure is transparent to the API user in the sense
that all necessary processing is performed internally, and a basic
solution of the original problem recovered by the presolver is the same
as if it were computed directly, i.e. without presolving.

Note that the presolver is able to recover only optimal solutions. If
a computed solution is infeasible or non-optimal, the corresponding
solution of the original problem cannot be recovered and therefore
remains undefined. If you need to know a basic solution even if it is
infeasible or non-optimal, the presolver should be disabled.

\subsubsection*{Solver terminal output}

Solving large problem instances may take a long time, so the solver
reports some information about the current basic solution, which is sent
to the terminal. This information has the following format:

\begin{verbatim}
nnn:  obj = xxx  infeas = yyy (ddd)
\end{verbatim}

\noindent
where: `\verb|nnn|' is the iteration number, `\verb|xxx|' is the
current value of the objective function (it is is unscaled and has
correct sign); `\verb|yyy|' is the current sum of primal or dual
infeasibilities (it is scaled and therefore may be used only for visual
estimating), `\verb|ddd|' is the current number of fixed basic
variables.

The symbol preceding the iteration number indicates which phase of the
simplex method is in effect:

{\it Blank} means that the solver is searching for primal feasible
solution using the primal simplex or for dual feasible solution using
the dual simplex;

{\it Asterisk} (\verb|*|) means that the solver is searching for
optimal solution using the primal simplex;

{\it Vertical dash} (\verb/|/) means that the solver is searching for
optimal solution using the dual simplex.

\subsubsection*{Control parameters}

This paragraph describes all control parameters currently used in the
simplex solver. Symbolic names of control parameters are names of
corresponding members in the structure \verb|glp_smcp|.

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
\\
&Message level for terminal output:\\
&\verb|GLP_MSG_OFF| --- no output;\\
&\verb|GLP_MSG_ERR| --- error and warning messages only;\\
&\verb|GLP_MSG_ON | --- normal output;\\
&\verb|GLP_MSG_ALL| --- full output (including informational messages).
\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int meth} (default: {\tt GLP\_PRIMAL})}
\\
&Simplex method option:\\
&\verb|GLP_PRIMAL| --- use two-phase primal simplex;\\
&\verb|GLP_DUAL  | --- use two-phase dual simplex;\\
&\verb|GLP_DUALP | --- use two-phase dual simplex, and if it fails,
switch to the\\
&\verb|            |$\:$ primal simplex.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int pricing} (default: {\tt GLP\_PT\_PSE})}
\\
&Pricing technique:\\
&\verb|GLP_PT_STD| --- standard (textbook);\\
&\verb|GLP_PT_PSE| --- projected steepest edge.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int r\_test} (default: {\tt GLP\_RT\_HAR})}
\\
&Ratio test technique:\\
&\verb|GLP_RT_STD| --- standard (textbook);\\
&\verb|GLP_RT_HAR| --- Harris' two-pass ratio test.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double tol\_bnd} (default: {\tt 1e-7})}
\\
&Tolerance used to check if the basic solution is primal feasible.
(Do not change this parameter without detailed understanding its
purpose.)\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double tol\_dj} (default: {\tt 1e-7})}
\\
&Tolerance used to check if the basic solution is dual feasible.
(Do not change this parameter without detailed understanding its
purpose.)\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double tol\_piv} (default: {\tt 1e-10})}
\\
&Tolerance used to choose eligble pivotal elements of the simplex table.
(Do not change this parameter without detailed understanding its
purpose.)\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double obj\_ll} (default: {\tt -DBL\_MAX})}
\\
&Lower limit of the objective function. If the objective function
reaches this limit and continues decreasing, the solver terminates the
search. (Used in the dual simplex only.)\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double obj\_ul} (default: {\tt +DBL\_MAX})}
\\
&Upper limit of the objective function. If the objective function
reaches this limit and continues increasing, the solver terminates the
search. (Used in the dual simplex only.)\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int it\_lim} (default: {\tt INT\_MAX})}
\\
&Simplex iteration limit.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int tm\_lim} (default: {\tt INT\_MAX})}
\\
&Searching time limit, in milliseconds.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int out\_frq} (default: {\tt 200})}
\\
&Output frequency, in iterations. This parameter specifies how
frequently the solver sends information about the solution process to
the terminal.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int out\_dly} (default: {\tt 0})}
\\
&Output delay, in milliseconds. This parameter specifies how long the
solver should delay sending information about the solution process to
the terminal.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int presolve} (default: {\tt GLP\_OFF})}
\\
&LP presolver option:\\
&\verb|GLP_ON | --- enable using the LP presolver;\\
&\verb|GLP_OFF| --- disable using the LP presolver.\\
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Initialize simplex method control parameters}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_init_smcp(glp_smcp *parm);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_init_smcp| initializes control parameters, which
are used by the simplex solver, with default values.

Default values of the control parameters are stored in a \verb|glp_smcp|
structure, which the parameter \verb|parm| points to.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{Solve LP problem in exact arithmetic}

\subsubsection*{Synopsis}

\begin{verbatim}
int lpx_exact(glp_prob *lp);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_exact| is an experimental implementation of the
primal two-phase simplex method based on exact (rational) arithmetic.
It is similar to the routine \verb|glp_simplex|, however, for all
internal computations it uses arithmetic of rational numbers, which is
exact in mathematical sense, i.e. free of round-off errors unlike
floating-point arithmetic.

\subsubsection*{Returns}

The routine \verb|lpx_exact| returns one of the following exit codes:

\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
\verb|LPX_E_OK|     & the LP problem has been successfully solved.
   (Note that, for example, if the problem has no feasible solution,
   this exit code is reported.) \\
\verb|LPX_E_FAULT|  & either the LP problem has no rows and/or columns,
   or the initial basis is invalid, or the basis matrix is exactly
   singular. \\
\verb|LPX_E_ITLIM|  & the search was prematurely terminated because the
   simplex iterations limit has been exceeded. \\
\verb|LPX_E_TMLIM|  & the search was prematurely terminated because the
   time limit has been exceeded. \\
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{Retrieve generic status of basic solution}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_status(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_status| reports the generic status of the
current basic solution for the specified problem object as follows:

\begin{tabular}{@{}ll}
\verb|GLP_OPT|    & solution is optimal; \\
\verb|GLP_FEAS|   & solution is feasible; \\
\verb|GLP_INFEAS| & solution is infeasible; \\
\verb|GLP_NOFEAS| & problem has no feasible solution; \\
\verb|GLP_UNBND|  & problem has unbounded solution; \\
\verb|GLP_UNDEF|  & solution is undefined. \\
\end{tabular}

More detailed information about the status of basic solution can be
retrieved with the routines \verb|glp_get_prim_stat| and
\verb|glp_get_dual_stat|.

\subsection{Retrieve status of primal basic solution}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_prim_stat(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_prim_stat| reports the status of the primal
basic solution for the specified problem object as follows:

\begin{tabular}{@{}ll}
\verb|GLP_UNDEF|  & primal solution is undefined; \\
\verb|GLP_FEAS|   & primal solution is feasible; \\
\verb|GLP_INFEAS| & primal solution is infeasible; \\
\verb|GLP_NOFEAS| & no primal feasible solution exists. \\
\end{tabular}

\newpage

\subsection{Retrieve status of dual basic solution}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_dual_stat(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_dual_stat| reports the status of the dual
basic solution for the specified problem object as follows:

\begin{tabular}{@{}ll}
\verb|GLP_UNDEF|  & dual solution is undefined; \\
\verb|GLP_FEAS|   & dual solution is feasible; \\
\verb|GLP_INFEAS| & dual solution is infeasible; \\
\verb|GLP_NOFEAS| & no dual feasible solution exists. \\
\end{tabular}

\subsection{Retrieve objective value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_obj_val(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_obj_val| returns current value of the
objective function.

\subsection{Retrieve row status}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_row_stat(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_row_stat| returns current status assigned to
the auxiliary variable associated with \verb|i|-th row as follows:

\begin{tabular}{@{}ll}
\verb|GLP_BS| & basic variable; \\
\verb|GLP_NL| & non-basic variable on its lower bound; \\
\verb|GLP_NU| & non-basic variable on its upper bound; \\
\verb|GLP_NF| & non-basic free (unbounded) variable; \\
\verb|GLP_NS| & non-basic fixed variable. \\
\end{tabular}

\subsection{Retrieve row primal value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_row_prim(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_row_prim| returns primal value of the
auxiliary variable associated with \verb|i|-th row.

\subsection{Retrieve row dual value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_row_dual(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_row_dual| returns dual value (i.e. reduced
cost) of the auxiliary variable associated with \verb|i|-th row.

\subsection{Retrieve column status}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_col_stat(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_col_stat| returns current status assigned to
the structural variable associated with \verb|j|-th column as follows:

\begin{tabular}{@{}ll}
\verb|GLP_BS| & basic variable; \\
\verb|GLP_NL| & non-basic variable on its lower bound; \\
\verb|GLP_NU| & non-basic variable on its upper bound; \\
\verb|GLP_NF| & non-basic free (unbounded) variable; \\
\verb|GLP_NS| & non-basic fixed variable. \\
\end{tabular}

\newpage

\subsection{Retrieve column primal value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_col_prim(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_col_prim| returns primal value of the
structural variable associated with \verb|j|-th column.

\subsection{Retrieve column dual value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_col_dual(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_col_dual| returns dual value (i.e. reduced
cost) of the structural variable associated with \verb|j|-th column.

\subsection{Retrieve non-basic variable causing unboundness}

\subsubsection*{Synopsis}

\begin{verbatim}
int lpx_get_ray_info(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|lpx_get_ray_info| returns the number $k$ of some
non-basic variable $x_k$, which causes primal unboundness. If such a
variable cannot be identified, the routine returns zero.

If $1\leq k\leq m$, $x_k$ is $k$-th auxiliary variable, and if
$m+1\leq k\leq m+n$, $x_k$ is $(k-m)$-th structural variable, where $m$
is the number of rows, $n$ is the number of columns in the specified
problem object.

``Unboundness'' means that the variable $x_k$ is non-basic and able to
{\it infinitely} change in a feasible direction improving the objective
function.

\newpage

\subsection{Check Karush-Kuhn-Tucker conditions}

\subsubsection*{Synopsis}

\begin{verbatim}
void lpx_check_kkt(glp_prob *lp, int scaled, LPXKKT *kkt);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_check_kkt| checks Karush-Kuhn-Tucker optimality
conditions for basic solution. It is assumed that both primal and dual
components of basic solution are valid.

If the parameter \verb|scaled| is zero, the optimality conditions are
checked for the original, unscaled LP problem. Otherwise, if the
parameter \verb|scaled| is non-zero, the routine checks the conditions
for an internally scaled LP problem.

The parameter \verb|kkt| is a pointer to the structure \verb|LPXKKT|,
to which the routine stores results of the check. Members of this
structure are shown in the table below.

\begin{center}
\begin{tabular}{@{}c|l|l@{}}
Condition & Member & Comment \\
\hline
(KKT.PE) & \verb|pe_ae_max| &
         Largest absolute error \\
         & \verb|pe_ae_row| &
         Number of row with largest absolute error \\
         & \verb|pe_re_max| &
         Largest relative error \\
         & \verb|pe_re_row| &
         Number of row with largest relative error \\
         & \verb|pe_quality| &
         Quality of primal solution \\
\hline
(KKT.PB) & \verb|pb_ae_max| &
         Largest absolute error \\
         & \verb|pb_ae_ind| &
         Number of variable with largest absolute error \\
         & \verb|pb_re_max| &
         Largest relative error \\
         & \verb|pb_re_ind| &
         Number of variable with largest relative error \\
         & \verb|pb_quality| &
         Quality of primal feasibility \\
\hline
(KKT.DE) & \verb|de_ae_max| &
         Largest absolute error \\
         & \verb|de_ae_col| &
         Number of column with largest absolute error \\
         & \verb|de_re_max| &
         Largest relative error \\
         & \verb|de_re_col| &
         Number of column with largest relative error \\
         & \verb|de_quality| &
         Quality of dual solution \\
\hline
(KKT.DB) & \verb|db_ae_max| &
         Largest absolute error \\
         & \verb|db_ae_ind| &
         Number of variable with largest absolute error \\
         & \verb|db_re_max| &
         Largest relative error \\
         & \verb|db_re_ind| &
         Number of variable with largest relative error \\
         & \verb|db_quality| &
         Quality of dual feasibility \\
\end{tabular}
\end{center}

The routine performs all computations using only components of the
given LP problem and the current basic solution.

\subsubsection*{Background}

The first condition checked by the routine is:
$$x_R - A x_S = 0, \eqno{\rm (KKT.PE)}$$
where $x_R$ is the subvector of auxiliary variables (rows), $x_S$ is the
subvector of structural variables (columns), $A$ is the constraint
matrix. This condition expresses the requirement that all primal
variables must satisfy to the system of equality constraints of the
original LP problem. In case of exact arithmetic this condition would be
satisfied for any basic solution; however, in case of inexact
(floating-point) arithmetic, this condition shows how accurate the
primal basic solution is, that depends on accuracy of a representation
of the basis matrix used by the simplex method routines.

The second condition checked by the routine is:
$$l_k \leq x_k \leq u_k {\rm \ \ \ for\ all}\ k=1,\dots,m+n,
\eqno{\rm (KKT.PB)}$$
where $x_k$ is auxiliary ($1\leq k\leq m$) or structural
($m+1\leq k\leq m+n$) variable, $l_k$ and $u_k$ are, respectively,
lower and upper bounds of the variable $x_k$ (including cases of
infinite bounds). This condition expresses the requirement that all
primal variables must satisfy to bound constraints of the original LP
problem. Since in case of basic solution all non-basic variables are
placed on their bounds, actually the condition (KKT.PB) needs to be
checked for basic variables only. If the primal basic solution has
sufficient accuracy, this condition shows primal feasibility of the
solution.

The third condition checked by the routine is:
$${\rm grad}\;Z = c = (\tilde{A})^T \pi + d,$$
where $Z$ is the objective function, $c$ is the vector of objective
coefficients, $(\tilde{A})^T$ is a matrix transposed to the expanded
constraint matrix $\tilde{A} = (I|-A)$, $\pi$ is a vector of Lagrange
multipliers that correspond to equality constraints of the original LP
problem, $d$ is a vector of Lagrange multipliers that correspond to
bound constraints for all (auxiliary and structural) variables of the
original LP problem. Geometrically the third condition expresses the
requirement that the gradient of the objective function must belong to
the orthogonal complement of a linear subspace defined by the equality
and active bound constraints, i.e. that the gradient must be a linear
combination of normals to the constraint planes, where Lagrange
multipliers $\pi$ and $d$ are coefficients of that linear combination.

To eliminate the vector $\pi$ the third condition can be rewritten as:
$$
\left(\begin{array}{@{}c@{}}I \\ -A^T\end{array}\right) \pi =
\left(\begin{array}{@{}c@{}}d_R \\ d_S\end{array}\right) +
\left(\begin{array}{@{}c@{}}c_R \\ c_S\end{array}\right),
$$
or, equivalently:
$$
\begin{array}{r@{}c@{}c}
\pi + d_R&\ =\ &c_R, \\
-A^T\pi + d_S&\ =\ &c_S. \\
\end{array}
$$
Then substituting the vector $\pi$ from the first equation into the
second one we have:
$$A^T (d_R - c_R) + (d_S - c_S) = 0, \eqno{\rm (KKT.DE)}$$
where $d_R$ is the subvector of reduced costs of auxiliary variables
(rows), $d_S$ is the subvector of reduced costs of structural variables
(columns), $c_R$ and $c_S$ are subvectors of objective coefficients at,
respectively, auxiliary and structural variables, $A^T$ is a matrix
transposed to the constraint matrix of the original LP problem. In case
of exact arithmetic this condition would be satisfied for any basic
solution; however, in case of inexact (floating-point) arithmetic, this
condition shows how accurate the dual basic solution is, that depends on
accuracy of a representation of the basis matrix used by the simplex
method routines.

The last, fourth condition checked by the routine is (KKT.DB):

\medskip

\begin{tabular}{r@{}c@{}ll}
&$\ d_k\ $& $=0,$&if $x_k$ is basic or free non-basic variable \\
$0\leq$&$\ d_k\ $&$<+\infty$&if $x_k$ is non-basic on its lower
(minimization) \\
&&&or upper (maximization) bound \\
$-\infty<$&$\ d_k\ $&$\leq 0$&if $x_k$ is non-basic on its upper
(minimization) \\
&&&or lower (maximization) bound \\
$-\infty<$&$\ d_k\ $&$<+\infty$&if $x_k$ is non-basic fixed variable \\
\end{tabular}

\medskip

\noindent
for all $k=1,\dots,m+n$, where $d_k$ is a reduced cost (Lagrange
multiplier) of auxiliary ($1\leq k\leq m$) or structural
($m+1\leq k\leq m+n$) variable $x_k$. Geometrically this condition
expresses the requirement that constraints of the original problem must
"hold" the point preventing its movement along the anti-gradient (in
case of minimization) or the gradient (in case of maximization) of the
objective function. Since in case of basic solution reduced costs of
all basic variables are placed on their (zero) bounds, actually the
condition (KKT.DB) needs to be checked for non-basic variables only.
If the dual basic solution has sufficient accuracy, this condition shows
dual feasibility of the solution.

Should note that the complete set of Karush-Kuhn-Tucker optimality
conditions also includes the fifth, so called complementary slackness
condition, which expresses the requirement that at least either a primal
variable $x_k$ or its dual counterpart $d_k$ must be on its bound for
all $k=1,\dots,m+n$. However, being always satisfied by definition for
any basic solution that condition is not checked by the routine.

To check the first condition (KKT.PE) the routine computes a vector of
residuals:
$$g = x_R - A x_S,$$
determines component of this vector that correspond to largest absolute
and relative errors:

\medskip

\hspace{30mm}
\verb|pe_ae_max| $\displaystyle{= \max_{1\leq i\leq m}|g_i|}$,

\medskip

\hspace{30mm}
\verb|pe_re_max| $\displaystyle{= \max_{1\leq i\leq m}
\frac{|g_i|}{1+|(x_R)_i|}}$,

\medskip

\noindent
and stores these quantities and corresponding row indices to the
structure \verb|LPXKKT|.

To check the second condition (KKT.PB) the routine computes a vector
of residuals:
$$
h_k = \left\{
\begin{array}{ll}
0,         & {\rm if}\ l_k \leq x_k \leq u_k \\
x_k - l_k, & {\rm if}\ x_k < l_k \\
x_k - u_k, & {\rm if}\ x_k > u_k \\
\end{array}
\right.
$$
for all $k=1,\dots,m+n$, determines components of this vector that
correspond to largest absolute and relative errors:

\medskip

\hspace{30mm}
\verb|pb_ae_max| $\displaystyle{= \max_{1\leq k \leq m+n}|h_k|}$,

\medskip

\hspace{30mm}
\verb|pb_re_max| $\displaystyle{= \max_{1\leq k \leq m+n}
\frac{|h_k|}{1+|x_k|}}$,

\medskip

\noindent
and stores these quantities and corresponding variable indices to the
structure \verb|LPXKKT|.

To check the third condition (KKT.DE) the routine computes a vector of
residuals:
$$u = A^T (d_R - c_R) + (d_S - c_S),$$
determines components of this vector that correspond to largest
absolute and relative errors:

\medskip

\hspace{30mm}
\verb|de_ae_max| $\displaystyle{= \max_{1\leq j\leq n}|u_j|}$,

\medskip

\hspace{30mm}
\verb|de_re_max| $\displaystyle{= \max_{1\leq j\leq n}
\frac{|u_j|}{1+|(d_S)_j - (c_S)_j|}}$,

\medskip

\noindent
and stores these quantities and corresponding column indices to the
structure \verb|LPXKKT|.

To check the fourth condition (KKT.DB) the routine computes a vector
of residuals:

$$
v_k = \left\{
\begin{array}{ll}
0,         & {\rm if}\ d_k\ {\rm has\ correct\ sign} \\
d_k,       & {\rm if}\ d_k\ {\rm has\ wrong\ sign} \\
\end{array}
\right.
$$
for all $k=1,\dots,m+n$, determines components of this vector that
correspond to largest absolute and relative errors:

\medskip

\hspace{30mm}
\verb|db_ae_max| $\displaystyle{= \max_{1\leq k\leq m+n}|v_k|}$,

\medskip

\hspace{30mm}
\verb|db_re_max| $\displaystyle{= \max_{1\leq k\leq m+n}
\frac{|v_k|}{1+|d_k - c_k|}}$,

\medskip

\noindent
and stores these quantities and corresponding variable indices to the
structure \verb|LPXKKT|.

Using the relative errors for all the four conditions listed above the
routine
\verb|lpx_check_kkt| also estimates a "quality" of the basic solution
from the standpoint of these conditions and stores corresponding
quality indicators to the structure \verb|LPXKKT|:

\verb|pe_quality| --- quality of primal solution;

\verb|pb_quality| --- quality of primal feasibility;

\verb|de_quality| --- quality of dual solution;

\verb|db_quality| --- quality of dual feasibility.

Each of these indicators is assigned to one of the following four
values:

\verb|'H'| means high quality,

\verb|'M'| means medium quality,

\verb|'L'| means low quality, or

\verb|'?'| means wrong or infeasible solution.

If all the indicators show high or medium quality (for an internally
scaled LP problem, i.e. when the parameter \verb|scaled| in a call to
the routine \verb|lpx_check_kkt| is non-zero), the user can be sure that
the obtained basic solution is quite accurate.

If some of the indicators show low quality, the solution can still be
considered as relevant, though an additional analysis is needed
depending on which indicator shows low quality.

If the indicator \verb|pe_quality| is assigned to \verb|'?'|, the
primal solution is wrong. If the indicator \verb|de_quality| is assigned
to \verb|'?'|, the dual solution is wrong.

If the indicator \verb|db_quality| is assigned to \verb|'?'| while
other indicators show a good quality, this means that the current
basic solution being primal feasible is not dual feasible. Similarly,
if the indicator \verb|pb_quality| is assigned to \verb|'?'| while
other indicators are not, this means that the current basic solution
being dual feasible is not primal feasible.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\section{Interior-point method routines}

\subsection{Solve LP problem with the interior-point method}

\subsubsection*{Synopsis}

\begin{verbatim}
int lpx_interior(glp_prob *lp);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_interior| is an interface to the LP problem
solver based on the primal-dual interior-point method.

This routine obtains problem data from the problem object, which the
parameter \verb|lp| points to, calls the solver to solve the LP problem,
and stores the found solution back in the problem object.

Interior-point methods (also known as barrier methods) are more modern
and more powerful numerical methods for large-scale linear programming.
They especially fit for very sparse LP problems and allow solving such
problems much faster than the simplex method.

Solving large LP problems may take a long time, so the routine
displays information about every interior point
iteration\footnote{Unlike the simplex method the interior point method
usually needs 30---50 iterations (independently on the problem size) in
order to find an optimal solution.}. This information is sent to the
output device and has the following format:

\begin{verbatim}
   nnn: F = fff; rpi = ppp; rdi = ddd; gap = ggg
\end{verbatim}

\noindent where \verb|nnn| is iteration number, \verb|fff| is the
current value of the objective function (in the case of maximization it
has wrong sign), \verb|ppp| is the current relative primal
infeasibility, \verb|ddd| is the current relative dual infeasibility,
and \verb|ggg| is the current primal-dual gap.

Should note that currently the GLPK interior-point solver does not
include many important features, in particular:

it is not able to process dense columns. Thus, if the constraint matrix
of the LP problem has dense columns, the solving process will be
inefficient;

it has no features against numerical instability. For some LP problems
premature termination may happen if the matrix $ADA^T$ becomes singular
or ill-conditioned;

it is not able to identify the optimal basis, which corresponds to the
found interior-point solution. 

\subsubsection*{Returns}

The routine \verb|lpx_interior| returns one of the following exit
codes:

\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
\verb|LPX_E_OK|     & the LP problem has been successfully solved (to
   optimality). \\
\verb|LPX_E_FAULT|  & the solver cannot start the search because the
   problem is empty, i.e. has no rows and/or columns. \\
\verb|LPX_E_NOFEAS| & the problem has no feasible (primal or dual)
   solution. \\
\verb|LPX_E_NOCONV| & the search was prematurely terminated due to very
slow convergence or divergence. \\
\verb|LPX_E_ITLIM|  & the search was prematurely terminated because the
   simplex iterations limit has been exceeded. \\
\verb|LPX_E_INSTAB| & the search was prematurely terminated due to
numerical instability on solving Newtonian system. \\
\end{tabular}

\subsection{Retrieve status of interior-point solution}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ipt_status(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ipt_status| reports the status of a solution
found by the interior-point solver as follows:

\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
\verb|GLP_UNDEF| & interior-point solution is undefined. \\
\verb|GLP_OPT|   & interior-point solution is optimal. \\
\end{tabular}

\subsection{Retrieve objective value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_ipt_obj_val(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ipt_obj_val| returns value of the objective
function for interior-point solution.

\newpage

\subsection{Retrieve row primal value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_ipt_row_prim(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ipt_row_prim| returns primal value of the
auxiliary variable associated with \verb|i|-th row.

\subsection{Retrieve row dual value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_ipt_row_dual(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ipt_row_dual| returns dual value (i.e. reduced
cost) of the auxiliary variable associated with \verb|i|-th row.

\subsection{Retrieve column primal value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_ipt_col_prim(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ipt_col_prim| returns primal value of the
structural variable associated with \verb|j|-th column.

\subsection{Retrieve column dual value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_ipt_col_dual(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ipt_col_dual| returns dual value (i.e. reduced
cost) of the structural variable associated with \verb|j|-th column.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\section{Mixed integer programming routines}

\subsection{Set (change) column kind}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_col_kind(glp_prob *mip, int j, int kind);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_col_kind| sets (changes) the kind of
\verb|j|-th column (structural variable) as specified by the parameter
\verb|kind|:

\begin{tabular}{@{}ll}
\verb|GLP_CV| & continuous variable; \\
\verb|GLP_IV| & integer variable; \\
\verb|GLP_BV| & binary variable. \\
\end{tabular}

If a column is set to \verb|GLP_IV|, its bounds must be exact integer
numbers with no tolerance, such that the condition
\verb|bnd == floor(bnd)| would hold.

Setting a column to \verb|GLP_BV| has the same effect as if it were
set to \verb|GLP_IV|, its lower bound were set 0, and its upper bound
were set to 1.

\subsection{Retrieve column kind}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_col_kind(glp_prob *mip, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_col_kind| returns the kind of \verb|j|-th
column (structural variable) as follows:

\begin{tabular}{@{}ll}
\verb|GLP_CV| & continuous variable; \\
\verb|GLP_IV| & integer variable; \\
\verb|GLP_BV| & binary variable. \\
\end{tabular}

\newpage

\subsection{Retrieve number of integer columns}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_num_int(glp_prob *mip);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_num_int| returns the number of columns
(structural variables), which are marked as integer. Note that this
number {\it does} include binary columns.

\subsection{Retrieve number of binary columns}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_num_bin(glp_prob *mip);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_num_bin| returns the number of columns
(structural variables), which are marked as integer and whose lower
bound is zero and upper bound is one.

\subsection{Solve MIP problem with the branch-and-cut method}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_intopt(glp_prob *mip, const glp_iocp *parm);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_intopt| is a driver to the MIP solver based on
the branch-and-cut method.

On entry the problem object should contain optimal solution to LP
relaxation (which can be obtained with the routine \verb|glp_simplex|).

The MIP solver has a set of control parameters. Values of the control
parameters can be passed in a structure \verb|glp_iocp|, which the
parameter parm points to. For a detailed description of this structure
see paragraph ``Control parameters'' below. Before specifying some
control parameters the application program should initialize the
structure \verb|glp_iocp| by default values of all control parameters
using the routine \verb|glp_init_iocp| (see the next subsection). This
is needed for backward compatibility, because in the future there may
appear new members in the structure \verb|glp_iocp|.

The parameter parm can be specified as \verb|NULL|, in which case the
solver uses default settings.

Note that the MIP solver currently implemented in GLPK uses easy
heuristics for branching and backtracking, and therefore it is not
perfect. Most probably this solver can be used for solving MIP problems
with one or two hundreds of integer variables. Hard or very large scale
MIP instances cannot be solved with this routine.

\subsubsection*{Returns}

\def\arraystretch{1}

\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
0 & The MIP problem instance has been successfully solved. (This code
does {\it not} necessarily mean that the solver has found optimal
solution. It only means that the solution process was successful.) \\
\verb|GLP_EBOUND| & Unable to start the search, because some
double-bounded variables have incorrect bounds or some integer variables
have non-integer (fractional) bounds.\\
\verb|GLP_EROOT| & Unable to start the search, because optimal basis for
initial LP relaxation is not provided.\\
\verb|GLP_EFAIL| & The search was prematurely terminated due to the
solver failure.\\
\verb|GLP_ETMLIM| & The search was prematurely terminated, because the
time limit has been exceeded.\\
\verb|GLP_ESTOP| & The search was prematurely terminated by application.
(This code may appear only if the advanced solver interface is used.)\\
\end{tabular}

\subsubsection*{Advanced solver interface}

The routine \verb|glp_intopt| allows the user to control the
branch-and-cut search by passing to the solver a user-defined callback
routine. For more details see Chapter ``Advanced API Routines'',
Section ``Branch-and-cut interface routines''.

\subsubsection*{Solver terminal output}

Solving many MIP problems may take a long time, so the solver reports
some information about best known solutions, which is sent to the output
device. This information has the following format:

\begin{verbatim}
+nnn: mip = xxx <rho> yyy gap (ppp; qqq)
\end{verbatim}

\noindent
where: `\verb|nnn|' is the simplex iteration number; `\verb|xxx|' is a
value of the objective function for the best known integer feasible
solution (if no integer feasible solution has been found yet,
`\verb|xxx|' is the text `\verb|not found yet|'); `\verb|rho|' is the
string `\verb|>=|' (in case of minimization) or `\verb|<=|' (in case of
maximization); `\verb|yyy|' is a global bound for exact integer optimum
(i.e. the exact integer optimum is always in the range from `\verb|xxx|'
to `\verb|yyy|'); `\verb|gap|' is the relative mip gap, in percents,
computed as $gap=|xxx-yyy|/(|xxx|+{\tt DBL\_EPSILON})\cdot 100\%$ (if
$gap$ is greater than $999.9\%$, it is not printed); `\verb|ppp|' is the
number of subproblems in the active list, `\verb|qqq|' is the number of
subproblems which have been already fathomed and therefore removed from
the branch-and-bound search tree.

\subsubsection{Control parameters}

This paragraph describes all control parameters currently used in the
MIP solver. Symbolic names of control parameters are names of
corresponding members in the structure \verb|glp_iocp|.

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
\\
&Message level for terminal output:\\
&\verb|GLP_MSG_OFF| --- no output;\\
&\verb|GLP_MSG_ERR| --- error and warning messages only;\\
&\verb|GLP_MSG_ON | --- normal output;\\
&\verb|GLP_MSG_ALL| --- full output (including informational messages).
\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int br\_tech} (default: {\tt GLP\_BR\_DTH})}
\\
&Branching technique option:\\
&\verb|GLP_BR_FFV| --- first fractional variable;\\
&\verb|GLP_BR_LFV| --- last fractional variable;\\
&\verb|GLP_BR_MFV| --- most fractional variable;\\
&\verb|GLP_BR_DTH| --- heuristic by Driebeck and Tomlin.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int bt\_tech} (default: {\tt GLP\_BT\_BLB})}
\\
&Backtracking technique option:\\
&\verb|GLP_BT_DFS| --- depth first search;\\
&\verb|GLP_BT_BFS| --- breadth first search;\\
&\verb|GLP_BT_BLB| --- best local bound;\\
&\verb|GLP_BT_BPH| --- best projection heuristic.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int pp\_tech} (default: {\tt GLP\_PP\_ALL})}
\\
&Preprocessing technique option:\\
&\verb|GLP_PP_NONE| --- disable preprocessing;\\
&\verb|GLP_PP_ROOT| --- perform preprocessing only on the root level;\\
&\verb|GLP_PP_ALL | --- perform preprocessing on all levels.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int gmi\_cuts} (default: {\tt GLP\_OFF})}
\\
&Gomory's mixed integer cut option:\\
&\verb|GLP_OFF| --- disable generating Gomory's cuts;\\
&\verb|GLP_ON | --- enable generating Gomory's cuts.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int mir\_cuts} (default: {\tt GLP\_OFF})}
\\
&Mixed integer rounding (MIR) cut option:\\
&\verb|GLP_OFF| --- disable generating MIR cuts;\\
&\verb|GLP_ON | --- enable generating MIR cuts.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double tol\_int} (default: {\tt 1e-5})}\\
&Absolute tolerance used to check if optimal solution to the current LP
relaxation is integer feasible. (Do not change this parameter without
detailed understanding its purpose.)\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double tol\_obj} (default: {\tt 1e-7})}\\
&Relative tolerance used to check if the objective value in optimal
solution to the current LP relaxation is not better than in the best
known integer feasible solution. (Do not change this parameter without
detailed understanding its purpose.)\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int tm\_lim} (default: {\tt INT\_MAX})}\\
&Searching time limit, in milliseconds.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int out\_frq} (default: {\tt 5000})}\\
&Output frequency, in milliseconds. This parameter specifies how
frequently the solver sends information about the solution process to
the terminal.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int out\_dly} (default: {\tt 10000})}\\
&Output delay, in milliseconds. This parameter specifies how long the
solver should delay sending information about solution of the current
LP relaxation with the simplex method to the terminal.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}
{{\tt void (*cb\_func)(glp\_tree *tree, void *info)}
(default: {\tt NULL})}\\
&Entry point to the user-defined callback routine. \verb|NULL| means
the advanced solver interface is not used. For more details see Chapter
``Advanced API Routines'', Section ``Branch-and-cut interface
routines''.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt void *cb\_info} (default: {\tt NULL})}\\
&Transit pointer passed to the routine \verb|cb_func| (see above).\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int cb\_size} (default: {\tt 0})}\\
&The number of extra (up to 256) bytes allocated for each node of the
branch-and-bound tree to store application-specific data. On creating
a node these bytes are initialized by binary zeros.\\
\end{tabular}

\newpage

\subsection{Initialize integer optimizer control parameters}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_init_iocp(glp_iocp *parm);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_init_iocp| initializes control parameters, which
are used by the branch-and-cut solver, with default values.

Default values of the control parameters are stored in a \verb|glp_iocp|
structure, which the parameter \verb|parm| points to.

\subsection{Solve MIP problem with the cut-and-branch method}

\subsubsection*{Synopsis}

\begin{verbatim}
int lpx_intopt(glp_prob *mip);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_intopt| is a driver to the MIP solver based on
the cut-and-branch method.

From the user's standpoint it is similar to the routine
\verb|glp_intopt| (see the previous subsection). However, it provides
the following two additional features:

1) presolving MIP that includes removing free, singleton and redundant
rows, improve bounds of columns, removing fixed columns, and reducing
constraint coefficients;

2) generating cutting planes (optionally) to improve LP relaxation of
the specified MIP problem before applying the branch-and-bound method.
(Currently the following cut classes are implemented: mixed cover cuts,
clique cuts, and Gomory's mixed integer cuts.) To enable this option
the user should set the control parameter \verb|LPX_K_USECUTS|.

The routine \verb|lpx_intopt| (unlike the routine \verb|glp_intopt|)
{\it does not} require optimal solution to LP relaxation.

\subsubsection*{Returns}

The routine \verb|lpx_intopt| returns one of the following exit codes:

\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
\verb|LPX_E_OK|     & the MIP problem has been successfully solved.
   (Note that, for example, if the problem has no integer feasible
   solution, this exit code is reported.) \\
\verb|LPX_E_FAULT|  & unable to start the search because either \\
                    & the problem is not of MIP class or \\
                    & some integer variable has non-integer lower or
                      upper bound. \\
\verb|LPX_E_NOPFS|  & the problem has no primal feasible solution
                      (detected either by the MIP presolver, or by the
                      simplex method on solving LP relaxation, or on
                      re-optimization on generating cutting planes).\\
\verb|LPX_E_NODFS|  & LP relaxation of the problem has no dual feasible
                      solution (detected either by the MIP presolver or
                      by the simplex method on solving LP relaxation).\\
\end{tabular}

\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
\verb|LPX_E_ITLIM|  & the search was prematurely terminated because the
   simplex iterations limit has been exceeded. \\
\verb|LPX_E_TMLIM|  & the search was prematurely terminated because the
   time limit has been exceeded. \\
\verb|LPX_E_SING|   & the search was prematurely terminated due to the
   solver failure (the current basis matrix became singular or
   ill-conditioned). \\
\end{tabular}

\subsection{Retrieve status of MIP solution}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_mip_status(glp_prob *mip);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_mip_status| reports the status of a MIP solution
found by the MIP solver as follows:

\smallskip

\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
\verb|GLP_UNDEF| & MIP solution is undefined. \\
\verb|GLP_OPT|   & MIP solution is integer optimal. \\
\verb|GLP_FEAS|  & MIP solution is integer feasible, however, its
   optimality (or non-optimality) has not been proven, perhaps due to
   premature termination of the search. \\
\verb|GLP_NOFEAS| & problem has no integer feasible solution (proven by
   the solver). \\
\end{tabular}

\subsection{Retrieve objective value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_mip_obj_val(glp_prob *mip);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_mip_obj_val| returns value of the objective
function for MIP solution.

\subsection{Retrieve row value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_mip_row_val(glp_prob *mip, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_mip_row_val| returns value of the auxiliary
variable associated with \verb|i|-th row for MIP solution.

\subsection{Retrieve column value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_mip_col_val(glp_prob *mip, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_mip_col_val| returns value of the structural
variable associated with \verb|j|-th column for MIP solution.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Utility API routines}

\section{Problem data reading/writing routines}

\subsection{Read problem data in MPS format}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_read_mps(glp_prob *lp, int fmt, const void *parm,
      const char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_read_mps| reads problem data in MPS format from a
text file. (The MPS format is described in Appendix \ref{champs}, page
\pageref{champs}.)

The parameter \verb|fmt| specifies the MPS format version as follows:

\begin{tabular}{@{}ll}
\verb|GLP_MPS_DECK| & fixed (ancient) MPS format; \\
\verb|GLP_MPS_FILE| & free (modern) MPS format. \\
\end{tabular}

The parameter \verb|parm| is reserved for use in the future and must be
specified as \verb|NULL|.

The character string \verb|fname| specifies a name of the text file to
be read in. (If the file name ends with suffix `\verb|.gz|', the file is
assumed to be compressed, in which case the routine \verb|glp_read_mps|
decompresses it ``on the fly''.)

Note that before reading data the current content of the problem object
is completely erased with the routine \verb|glp_erase_prob|.

\subsubsection*{Returns}

If the operation was successful, the routine \verb|glp_read_mps|
returns zero. Otherwise, it prints an error message and returns
non-zero.

\subsection{Write problem data in MPS format}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_write_mps(glp_prob *lp, int fmt, const void *parm,
      const char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_write_mps| writes problem data in MPS format to a
text file. (The MPS format is described in Appendix \ref{champs}, page
\pageref{champs}.)

The parameter \verb|fmt| specifies the MPS format version as follows:

\begin{tabular}{@{}ll}
\verb|GLP_MPS_DECK| & fixed (ancient) MPS format; \\
\verb|GLP_MPS_FILE| & free (modern) MPS format. \\
\end{tabular}

The parameter \verb|parm| is reserved for use in the future and must be
specified as \verb|NULL|.

The character string \verb|fname| specifies a name of the text file to
be written out. (If the file name ends with suffix `\verb|.gz|', the
file is assumed to be compressed, in which case the routine
\verb|glp_write_mps| performs automatic compression on writing it.)

\subsubsection*{Returns}

If the operation was successful, the routine \verb|glp_write_mps|
returns zero. Otherwise, it prints an error message and returns
non-zero.

\subsection{Read problem data in CPLEX LP format}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_read_lp(glp_prob *lp, const void *parm,
      const char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_read_lp| reads problem data in CPLEX LP format
from a text file. (The CPLEX LP format is described in Appendix
\ref{chacplex}, page \pageref{chacplex}.)

The parameter \verb|parm| is reserved for use in the future and must be
specified as \verb|NULL|.

The character string \verb|fname| specifies a name of the text file to
be read in. (If the file name ends with suffix `\verb|.gz|', the file is
assumed to be compressed, in which case the routine \verb|glp_read_lp|
decompresses it ``on the fly''.)

Note that before reading data the current content of the problem object
is completely erased with the routine \verb|glp_erase_prob|.

\subsubsection*{Returns}

If the operation was successful, the routine \verb|glp_read_lp| returns
zero. Otherwise, it prints an error message and returns non-zero.

\subsection{Write problem data in CPLEX LP format}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_write_lp(glp_prob *lp, const void *parm,
      const char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_write_lp| writes problem data in CPLEX LP format
to a text file. (The CPLEX LP format is described in Appendix
\ref{chacplex}, page \pageref{chacplex}.)

The parameter \verb|parm| is reserved for use in the future and must be
specified as \verb|NULL|.

The character string \verb|fname| specifies a name of the text file to
be written out. (If the file name ends with suffix `\verb|.gz|', the
file is assumed to be compressed, in which case the routine
\verb|glp_write_lp| performs automatic compression on writing it.)

\subsubsection*{Returns}

If the operation was successful, the routine \verb|glp_write_lp|
returns zero. Otherwise, it prints an error message and returns
non-zero.

\subsection{Read model in GNU MathProg modeling language}

\subsubsection*{Synopsis}

\begin{verbatim}
glp_prob *lpx_read_model(char *model, char *data,
      char *output);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_read_model| reads and translates LP/MIP model
(problem) written in the GNU MathProg modeling language.\footnote{The
GNU MathProg modeling language is a subset of the AMPL language.}

The character string \verb|model| specifies name of input text file,
which contains model section and, optionally, data section. This
parameter cannot be \verb|NULL|.

The character string \verb|data| specifies name of input text file,
which contains data section. This parameter can be \verb|NULL|. (If the
data file is specified and the model file also contains data section,
that section is ignored and data section from the data file is used.)

The character string \verb|output| specifies name of output text file,
to which the output produced by display statements is written. If the
parameter output is \verb|NULL|, the display output is sent to stdout
via the routine \verb|print|.

The routine \verb|lpx_read_model| is an interface to the model
translator, which is a program that parses model description and
translates it to some internal data structures.

For detailed description of the modeling language see the document
``GLPK: Modeling Language GNU MathProg'' included in the GLPK
distribution.

\subsubsection*{Returns}

If no errors occurred, the routine returns a pointer to the created
problem object. Otherwise the routine sends diagnostics to the output
device and returns \verb|NULL|.

\newpage

\section{Problem solution reading/writing routines}

\subsection{Write basic solution in printable format}

\subsubsection*{Synopsis}

\begin{verbatim}
int lpx_print_sol(glp_prob *lp, char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_print_sol writes| the current basic solution of
an LP problem, which is specified by the pointer \verb|lp|, to a text
file, whose name is the character string \verb|fname|, in printable
format.

Information reported by the routine \verb|lpx_print_sol| is intended
mainly for visual analysis.

\subsubsection*{Returns}

If no errors occurred, the routine returns zero. Otherwise the routine
prints an error message and returns non-zero.

\subsection{Write bounds sensitivity information}

\subsubsection*{Synopsis}

\begin{verbatim}
int lpx_print_sens_bnds(glp_prob *lp, char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_print_sens_bnds| writes the bounds for objective
coefficients, right-hand-sides of constraints, and variable bounds
for which the current optimal basic solution remains optimal (for LP
only).

The LP is given by the pointer \verb|lp|, and the output is written to
the file specified by \verb|fname|.  The current contents of the file
will be overwritten.

Information reported by the routine \verb|lpx_print_sens_bnds| is
intended mainly for visual analysis.

\subsubsection*{Returns}

If no errors occurred, the routine returns zero. Otherwise the routine
prints an error message and returns non-zero.

\subsection{Write interior point solution in printable format}

\subsubsection*{Synopsis}

\begin{verbatim}
int lpx_print_ips(glp_prob *lp, char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_print_ips| writes the current interior point
solution  of an LP problem, which the parameter \verb|lp| points to, to
a text file, whose name is the character string \verb|fname|, in
printable format.

Information reported by the routine \verb|lpx_print_ips| is intended
mainly  for visual analysis.

\subsubsection*{Returns}

If no errors occurred, the routine returns zero. Otherwise the routine
prints an error message and returns non-zero.

\subsection{Write MIP solution in printable format}

\subsubsection*{Synopsis}

\begin{verbatim}
int lpx_print_mip(glp_prob *lp, char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_print_mip| writes a best known integer solution
of a MIP problem, which is specified by the pointer \verb|lp|, to a text
file, whose name is the character string \verb|fname|, in printable
format.

Information reported by the routine \verb|lpx_print_mip| is intended
mainly for visual analysis.

\subsubsection*{Returns}

If no errors occurred, the routine returns zero. Otherwise the routine
prints an error message and returns non-zero.

\pagebreak

\subsection{Read basic solution from text file}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_read_sol(glp_prob *lp, const char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_read_sol| reads basic solution from a text file
whose name is specified by the parameter \verb|fname| into the problem
object.

For the file format see description of the routine \verb|glp_write_sol|.

\subsubsection*{Returns}

On success the routine returns zero, otherwise non-zero.

\subsection{Write basic solution to text file}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_write_sol(glp_prob *lp, const char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_write_sol| writes the current basic solution to a
text file whose name is specified by the parameter \verb|fname|. This
file can be read back with the routine \verb|glp_read_sol|.

\subsubsection*{Returns}

On success the routine returns zero, otherwise non-zero.

\subsubsection*{File format}

The file created by the routine \verb|glp_write_sol| is a plain text
file, which contains the following information:

\begin{verbatim}
   m n
   p_stat d_stat obj_val
   r_stat[1] r_prim[1] r_dual[1]
   . . .
   r_stat[m] r_prim[m] r_dual[m]
   c_stat[1] c_prim[1] c_dual[1]
   . . .
   c_stat[n] c_prim[n] c_dual[n]
\end{verbatim}

\noindent
where:

\noindent
$m$ is the number of rows (auxiliary variables);

\noindent
$n$ is the number of columns (structural variables);

\noindent
\verb|p_stat| is the primal status of the basic solution
(\verb|GLP_UNDEF| = 1, \verb|GLP_FEAS| = 2, \verb|GLP_INFEAS| = 3, or
\verb|GLP_NOFEAS| = 4);

\noindent
\verb|d_stat| is the dual status of the basic solution
(\verb|GLP_UNDEF| = 1, \verb|GLP_FEAS| = 2, \verb|GLP_INFEAS| = 3, or
\verb|GLP_NOFEAS| = 4);

\noindent
\verb|obj_val| is the objective value;

\noindent
\verb|r_stat[i]|, $i=1,\dots,m$, is the status of $i$-th row
(\verb|GLP_BS| = 1, \verb|GLP_NL| = 2, \verb|GLP_NU| = 3,
\verb|GLP_NF| = 4, or \verb|GLP_NS| = 5);

\noindent
\verb|r_prim[i]|, $i=1,\dots,m$, is the primal value of $i$-th row;

\noindent
\verb|r_dual[i]|, $i=1,\dots,m$, is the dual value of $i$-th row;

\noindent
\verb|c_stat[j]|, $j=1,\dots,n$, is the status of $j$-th column
(\verb|GLP_BS| = 1, \verb|GLP_NL| = 2, \verb|GLP_NU| = 3,
\verb|GLP_NF| = 4, or \verb|GLP_NS| = 5);

\noindent
\verb|c_prim[j]|, $j=1,\dots,n$, is the primal value of $j$-th column;

\noindent
\verb|c_dual[j]|, $j=1,\dots,n$, is the dual value of $j$-th column.

\subsection{Read interior-point solution from text file}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_read_ipt(glp_prob *lp, const char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_read_ipt| reads interior-point solution from a
text file whose name is specified by the parameter \verb|fname| into the
problem object.

For the file format see description of the routine \verb|glp_write_ipt|.

\subsubsection*{Returns}

On success the routine returns zero, otherwise non-zero.

\pagebreak

\subsection{Write interior-point solution to text file}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_write_ipt(glp_prob *lp, const char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_write_ipt| writes the current interior-point
solution to a text file whose name is specified by the parameter
\verb|fname|. This file can be read back with the routine
\verb|glp_read_ipt|.

\subsubsection*{Returns}

On success the routine returns zero, otherwise non-zero.

\subsubsection*{File format}

The file created by the routine \verb|glp_write_ipt| is a plain text
file, which contains the following information:

\begin{verbatim}
   m n
   stat obj_val
   r_prim[1] r_dual[1]
   . . .
   r_prim[m] r_dual[m]
   c_prim[1] c_dual[1]
   . . .
   c_prim[n] c_dual[n]
\end{verbatim}

\noindent
where:

\noindent
$m$ is the number of rows (auxiliary variables);

\noindent
$n$ is the number of columns (structural variables);

\noindent
\verb|stat| is the solution status (\verb|GLP_UNDEF| = 1 or
\verb|GLP_OPT| = 5);

\noindent
\verb|obj_val| is the objective value;

\noindent
\verb|r_prim[i]|, $i=1,\dots,m$, is the primal value of $i$-th row;

\noindent
\verb|r_dual[i]|, $i=1,\dots,m$, is the dual value of $i$-th row;

\noindent
\verb|c_prim[j]|, $j=1,\dots,n$, is the primal value of $j$-th column;

\noindent
\verb|c_dual[j]|, $j=1,\dots,n$, is the dual value of $j$-th column.

\subsection{Read MIP solution from text file}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_read_mip(glp_prob *mip, const char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_read_mip| reads MIP solution from a text file
whose name is specified by the parameter \verb|fname| into the problem
object.

For the file format see description of the routine \verb|glp_write_mip|.

\subsubsection*{Returns}

On success the routine returns zero, otherwise non-zero.

\subsection{Write MIP solution to text file}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_write_mip(glp_prob *mip, const char *fname);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_write_mip| writes the current MIP solution to a
text file whose name is specified by the parameter \verb|fname|. This
file can be read back with the routine \verb|glp_read_mip|.

\subsubsection*{Returns}

On success the routine returns zero, otherwise non-zero.

\subsubsection*{File format}

The file created by the routine \verb|glp_write_sol| is a plain text
file, which contains the following information:

\begin{verbatim}
   m n
   stat obj_val
   r_val[1]
   . . .
   r_val[m]
   c_val[1]
   . . .
   c_val[n]
\end{verbatim}

\noindent
where:

\noindent
$m$ is the number of rows (auxiliary variables);

\noindent
$n$ is the number of columns (structural variables);

\noindent
\verb|stat| is the solution status (\verb|GLP_UNDEF| = 1,
\verb|GLP_FEAS| = 2, \verb|GLP_NOFEAS| = 4, or \verb|GLP_OPT| = 5);

\noindent
\verb|obj_val| is the objective value;

\noindent
\verb|r_val[i]|, $i=1,\dots,m$, is the value of $i$-th row;

\noindent
\verb|c_val[j]|, $j=1,\dots,n$, is the value of $j$-th column.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Advanced API Routines}

\section{LP basis and simplex tableau routines}
\label{lpbasis}

\subsection{Background}
\label{subsecbasbgd}

Using vector and matrix notations LP problem (1.1)---(1.3) (see Section
\ref{seclp}, page \pageref{seclp}) can be stated as follows:

\medskip

\noindent
\hspace{.5in} minimize (or maximize)
$$z=c^Tx_S+c_0\eqno(3.1)$$
\hspace{.5in} subject to linear constraints
$$x_R=Ax_S\eqno(3.2)$$
\hspace{.5in} and bounds of variables
$$
\begin{array}{l@{\ }c@{\ }l@{\ }c@{\ }l}
l_R&\leq&x_R&\leq&u_R\\
l_S&\leq&x_S&\leq&u_S\\
\end{array}\eqno(3.3)
$$
where:

\noindent
$x_R=(x_1,x_2,\dots,x_m)$ is the vector of auxiliary variables;

\noindent
$x_S=(x_{m+1},x_{m+2},\dots,x_{m+n})$ is the vector of structural
variables;

\noindent
$z$ is the objective function;

\noindent
$c=(c_1,c_2,\dots,c_n)$ is the vector of objective coefficients;

\noindent
$c_0$ is the constant term (``shift'') of the objective function;

\noindent
$A=(a_{11},a_{12},\dots,a_{mn})$ is the constraint matrix;

\noindent
$l_R=(l_1,l_2,\dots,l_m)$ is the vector of lower bounds of auxiliary
variables;

\noindent
$u_R=(u_1,u_2,\dots,u_m)$ is the vector of upper bounds of auxiliary
variables;

\noindent
$l_S=(l_{m+1},l_{m+2},\dots,l_{m+n})$ is the vector of lower bounds of
structural variables;

\noindent
$u_S={u_{m+1},u_{m+2},\dots,u_{m+n}}$ is the vector of upper bounds of
structural variables.

\medskip

From the simplex method's standpoint there is no difference between
auxiliary and structural variables. This allows combining all these
variables into one vector that leads to the following problem statement:

\medskip

\noindent
\hspace{.5in} minimize (or maximize)
$$z=(0\ |\ c)^Tx+c_0\eqno(3.4)$$
\hspace{.5in} subject to linear constraints
$$(I\ |-\!A)x=0\eqno(3.5)$$
\hspace{.5in} and bounds of variables
$$l\leq x\leq u\eqno(3.6)$$
where:

\noindent
$x=(x_R\ |\ x_S)$ is the $(m+n)$-vector of (all) variables;

\noindent
$(0\ |\ c)$ is the $(m+n)$-vector of objective
coefficients;\footnote{Subvector 0 corresponds to objective coefficients
at auxiliary variables.}

\noindent
$(I\ |-\!A)$ is the {\it augmented} constraint
$m\times(m+n)$-matrix;\footnote{Note that due to auxiliary variables
matrix $(I\ |-\!A)$ contains the unity submatrix and therefore has full
rank. This means, in particular, that the system (3.5) has no linearly
dependent constraints.}

\noindent
$l=(l_R\ |\ l_S)$ is the $(m+n)$-vector of lower bounds of (all)
variables;

\noindent
$u=(u_R\ |\ u_S)$ is the $(m+n)$-vector of upper bounds of (all)
variables.

\medskip

By definition an {\it LP basic solution} geometrically is a point in
the space of all variables, which is the intersection of planes
corresponding to active constraints\footnote{A constraint is called
{\it active} if in a given point it is satisfied as equality, otherwise
it is called {\it inactive}.}. The space of all variables has the
dimension $m+n$, therefore, to define some basic solution we have to
define $m+n$ active constraints. Note that $m$ constraints (3.5) being
linearly independent equalities are always active, so remaining $n$
active constraints can be chosen only from bound constraints (3.6).

A variable is called {\it non-basic}, if its (lower or upper) bound is
active, otherwise it is called {\it basic}. Since, as was said above,
exactly $n$ bound constraints must be active, in any basic solution
there are always $n$ non-basic variables and $m$ basic variables.
(Note that a free variable also can be non-basic. Although such
variable has no bounds, we can think it as the difference between two
non-negative variables, which both are non-basic in this case.)

Now consider how to determine numeric values of all variables for a
given basic solution.

Let $\Pi$ be an appropriate permutation matrix of the order $(m+n)$.
Then we can write:
$$\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right)=
\Pi\left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)=\Pi x,
\eqno(3.7)$$
where $x_B$ is the vector of basic variables, $x_N$ is the vector of
non-basic variables, $x=(x_R\ |\ x_S)$ is the vector of all variables
in the original order. In this case the system of linear constraints
(3.5) can be rewritten as follows:
$$(I\ |-\!A)\Pi^T\Pi x=0\ \ \ \Rightarrow\ \ \ (B\ |\ N)
\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right)=0,\eqno(3.8)$$
where
$$(B\ |\ N)=(I\ |-\!A)\Pi^T.\eqno(3.9)$$
Matrix $B$ is a square non-singular $m\times m$-matrix, which is
composed from columns of the augmented constraint matrix corresponding
to basic variables. It is called the {\it basis matrix} or simply the
{\it basis}. Matrix $N$ is a rectangular $m\times n$-matrix, which is
composed from columns of the augmented constraint matrix corresponding
to non-basic variables.

From (3.8) it follows that:
$$Bx_B+Nx_N=0,\eqno(3.10)$$
therefore,
$$x_B=-B^{-1}Nx_N.\eqno(3.11)$$
Thus, the formula (3.11) shows how to determine numeric values of basic
variables $x_B$ assuming that non-basic variables $x_N$ are fixed on
their active bounds.

The $m\times n$-matrix
$$\Xi=-B^{-1}N,\eqno(3.12)$$
which appears in (3.11), is called the {\it simplex
tableau}.\footnote{This definition corresponds to the GLPK
implementation.} It shows how basic variables depend on non-basic
variables:
$$x_B=\Xi x_N.\eqno(3.13)$$

The system (3.13) is equivalent to the system (3.5) in the sense that
they both define the same set of points in the space of (primal)
variables, which satisfy to these systems. If, moreover, values of all
basic variables satisfy to their bound constraints (3.3), the
corresponding basic solution is called {\it (primal) feasible},
otherwise {\it (primal) infeasible}. It is understood that any (primal)
feasible basic solution satisfy to all constraints (3.2) and (3.3).

The LP theory says that if LP has optimal solution, it has (at least
one) basic feasible solution, which corresponds to the optimum. And the
most natural way to determine whether a given basic solution is optimal
or not is to use the Karush---Kuhn---Tucker optimality conditions.

\def\arraystretch{1.5}

For the problem statement (3.4)---(3.6) the optimality conditions are
the following:\footnote{These conditions can be appiled to any solution,
not only to a basic solution.}
$$(I\ |-\!A)x=0\eqno(3.14)$$
$$(I\ |-\!A)^T\pi+\lambda_l+\lambda_u=\nabla z=(0\ |\ c)^T\eqno(3.15)$$
$$l\leq x\leq u\eqno(3.16)$$
$$\lambda_l\geq 0,\ \ \lambda_u\leq 0\ \ \mbox{(minimization)}
\eqno(3.17)$$
$$\lambda_l\leq 0,\ \ \lambda_u\geq 0\ \ \mbox{(maximization)}
\eqno(3.18)$$
$$(\lambda_l)_k(x_k-l_k)=0,\ \ (\lambda_u)_k(x_k-u_k)=0,\ \ k=1,2,\dots,
m+n\eqno(3.19)$$
where:
$\pi=(\pi_1,\pi_2,\dots,\pi_m)$ is a $m$-vector of Lagrange
multipliers for equality constraints (3.5);
$\lambda_l=[(\lambda_l)_1,(\lambda_l)_2,\dots,(\lambda_l)_n]$ is a
$n$-vector of Lagrange multipliers for lower bound constraints (3.6);
$\lambda_u=[(\lambda_u)_1,(\lambda_u)_2,\dots,(\lambda_u)_n]$ is a
$n$-vector of Lagrange multipliers for upper bound constraints (3.6).

Condition (3.14) is the {\it primal} (original) system of equality
constraints (3.5).

Condition (3.15) is the {\it dual} system of equality constraints.
It requires the gradient of the objective function to be a linear
combination of normals to the planes defined by constraints of the
original problem.

Condition (3.16) is the primal (original) system of bound constraints
(3.6).

Condition (3.17) (or (3.18) in case of maximization) is the dual system
of bound constraints.

Condition (3.19) is the {\it complementary slackness condition}. It
requires, for each original (auxiliary or structural) variable $x_k$,
that either its (lower or upper) bound must be active, or zero bound of
the corresponding Lagrange multiplier ($(\lambda_l)_k$ or
$(\lambda_u)_k$) must be active.

In GLPK two multipliers $(\lambda_l)_k$ and $(\lambda_u)_k$ for each
primal (original) variable $x_k$, $k=1,2,\dots,m+n$, are combined into
one multiplier:
$$\lambda_k=(\lambda_l)_k+(\lambda_u)_k,\eqno(3.20)$$
which is called a {\it dual variable} for $x_k$. This {\it cannot} lead
to the ambiguity, because both lower and upper bounds of $x_k$ cannot be
active at the same time,\footnote{If $x_k$ is a fixed variable, we can
think it as double-bounded variable $l_k\leq x_k\leq u_k$, where
$l_k=u_k.$} so at least one of $(\lambda_l)_k$ and $(\lambda_u)_k$ must
be equal to zero, and because these multipliers have different signs,
the combined multiplier, which is their sum, uniquely defines each of
them.

\def\arraystretch{1}

Using dual variables $\lambda_k$ the dual system of bound constraints
(3.17) and (3.18) can be written in the form of so called {\it ``rule of
signs''} as follows:

\begin{center}
\begin{tabular}{|@{\,}c@{$\,$}|@{$\,$}c@{$\,$}|@{$\,$}c@{$\,$}|
@{$\,$}c|c@{$\,$}|@{$\,$}c@{$\,$}|@{$\,$}c@{$\,$}|}
\hline
Original bound&\multicolumn{3}{c|}{Minimization}&\multicolumn{3}{c|}
{Maximization}\\
\cline{2-7}
constraint&$(\lambda_l)_k$&$(\lambda_u)_k$&$(\lambda_l)_k+
(\lambda_u)_k$&$(\lambda_l)_k$&$(\lambda_u)_k$&$(\lambda_l)_k+
(\lambda_u)_k$\\
\hline
$-\infty<x_k<+\infty$&$=0$&$=0$&$\lambda_k=0$&$=0$&$=0$&$\lambda_k=0$\\
$x_k\geq l_k$&$\geq 0$&$=0$&$\lambda_k\geq 0$&$\leq 0$&$=0$&$\lambda_k
\leq0$\\
$x_k\leq u_k$&$=0$&$\leq 0$&$\lambda_k\leq 0$&$=0$&$\geq 0$&$\lambda_k
\geq0$\\
$l_k\leq x_k\leq u_k$&$\geq 0$& $\leq 0$& $-\infty\!<\!\lambda_k\!<
\!+\infty$
&$\leq 0$& $\geq 0$& $-\infty\!<\!\lambda_k\!<\!+\infty$\\
$x_k=l_k=u_k$&$\geq 0$& $\leq 0$& $-\infty\!<\!\lambda_k\!<\!+\infty$&
$\leq 0$&
$\geq 0$& $-\infty\!<\!\lambda_k\!<\!+\infty$\\
\hline
\end{tabular}
\end{center}

May note that each primal variable $x_k$ has its dual counterpart
$\lambda_k$ and vice versa. This allows applying the same partition for
the vector of dual variables as (3.7):
$$\left(\begin{array}{@{}c@{}}\lambda_B\\\lambda_N\\\end{array}\right)=
\Pi\lambda,\eqno(3.21)$$
where $\lambda_B$ is a vector of dual variables for basic variables
$x_B$, $\lambda_N$ is a vector of dual variables for non-basic variables
$x_N$.

By definition, bounds of basic variables are inactive constraints, so in
any basic solution $\lambda_B=0$. Corresponding values of dual variables
$\lambda_N$ for non-basic variables $x_N$ can be determined in the
following way. From the dual system (3.15) we have:
$$(I\ |-\!A)^T\pi+\lambda=(0\ |\ c)^T,\eqno(3.22)$$
so multiplying both sides of (3.22) by matrix $\Pi$ gives:
$$\Pi(I\ |-\!A)^T\pi+\Pi\lambda=\Pi(0\ |\ c)^T.\eqno(3.23)$$
From (3.9) it follows that
$$\Pi(I\ |-\!A)^T=[(I\ |-\!A)\Pi^T]^T=(B\ |\ N)^T.\eqno(3.24)$$
Further, we can apply the partition (3.7) also to the vector of
objective coefficients (see (3.4)):
$$\left(\begin{array}{@{}c@{}}c_B\\c_N\\\end{array}\right)=
\Pi\left(\begin{array}{@{}c@{}}0\\c\\\end{array}\right),\eqno(3.25)$$
where $c_B$ is a vector of objective coefficients at basic variables,
$c_N$ is a vector of objective coefficients at non-basic variables.
Now, substituting (3.24), (3.21), and (3.25) into (3.23), leads to:
$$(B\ |\ N)^T\pi+(\lambda_B\ |\ \lambda_N)^T=(c_B\ |\ c_N)^T,
\eqno(3.26)$$
and transposing both sides of (3.26) gives the system:
$$\left(\begin{array}{@{}c@{}}B^T\\N^T\\\end{array}\right)\pi+
\left(\begin{array}{@{}c@{}}\lambda_B\\\lambda_N\\\end{array}\right)=
\left(\begin{array}{@{}c@{}}c_B\\c_T\\\end{array}\right),\eqno(3.27)$$
which can be written as follows:
$$\left\{
\begin{array}{@{\ }r@{\ }c@{\ }r@{\ }c@{\ }l@{\ }}
B^T\pi&+&\lambda_B&=&c_B\\
N^T\pi&+&\lambda_N&=&c_N\\
\end{array}
\right.\eqno(3.28)
$$
Lagrange multipliers $\pi=(\pi_i)$ correspond to equality constraints
(3.5) and therefore can have any sign. This allows resolving the first
subsystem of (3.28) as follows:\footnote{$B^{-T}$ means $(B^T)^{-1}=
(B^{-1})^T$.}
$$\pi=B^{-T}(c_B-\lambda_B)=-B^{-T}\lambda_B+B^{-T}c_B,\eqno(3.29)$$
and substitution of $\pi$ from (3.29) into the second subsystem of
(3.28) gives:
$$\lambda_N=-N^T\pi+c_N=N^TB^{-T}\lambda_B+(c_N-N^TB^{-T}c_B).
\eqno(3.30)$$
The latter system can be written in the following final form:
$$\lambda_N=-\Xi^T\lambda_B+d,\eqno(3.31)$$
where $\Xi$ is the simplex tableau (see (3.12)), and
$$d=c_N-N^TB^{-T}c_B=c_N+\Xi^Tc_B\eqno(3.32)$$
is the vector of so called {\it reduced costs} of non-basic variables.

\pagebreak

Above it was said that in any basic solution $\lambda_B=0$, so
$\lambda_N=d$ as it follows from (3.31).

The system (3.31) is equivalent to the system (3.15) in the sense that
they both define the same set of points in the space of dual variables
$\lambda$, which satisfy to these systems. If, moreover, values of all
dual variables $\lambda_N$ (i.e. reduced costs $d$) satisfy to their
bound constraints (i.e. to the ``rule of signs''; see the table above),
the corresponding basic solution is called {\it dual feasible},
otherwise {\it dual infeasible}. It is understood that any dual feasible
solution satisfy to all constraints (3.15) and (3.17) (or (3.18) in case
of maximization).

It can be easily shown that the complementary slackness condition
(3.19) is always satisfied for {\it any} basic solution. Therefore,
a basic solution\footnote{It is assumed that a complete basic solution
has the form $(x,\lambda)$, i.e. it includes primal as well as dual
variables.} is {\it optimal} if and only if it is primal and dual
feasible, because in this case it satifies to all the optimality
conditions (3.14)---(3.19).

\def\arraystretch{1.5}

The meaning of reduced costs $d=(d_j)$ of non-basic variables can be
explained in the following way. From (3.4), (3.7), and (3.25) it follows
that:
$$z=c_B^Tx_B+c_N^Tx_N+c_0.\eqno(3.33)$$
Substituting $x_B$ from (3.11) into (3.33) we can eliminate basic
variables and express the objective only through non-basic variables:
$$
\begin{array}{r@{\ }c@{\ }l}
z&=&c_B^T(-B^{-1}Nx_N)+c_N^Tx_N+c_0=\\
&=&(c_N^T-c_B^TB^{-1}N)x_N+c_0=\\
&=&(c_N-N^TB^{-T}c_B)^Tx_N+c_0=\\
&=&d^Tx_N+c_0.
\end{array}\eqno(3.34)
$$
From (3.34) it is seen that reduced cost $d_j$ shows how the objective
function $z$ depends on non-basic variable $(x_N)_j$ in the neighborhood
of the current basic solution, i.e. while the current basis remains
unchanged.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{Check if the basis factorization exists}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_bf_exists(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

If the basis factorization for the current basis associated with the
specified problem object exists and therefore is available for
computations, the routine \verb|glp_bf_exists| returns non-zero.
Otherwise the routine returns zero.

\subsubsection*{Comments}

Let the problem object have $m$ rows and $n$ columns. In GLPK the
{\it basis matrix} $B$ is a square non-singular matrix of the order $m$,
whose columns correspond to basic (auxiliary and/or structural)
variables. It is defined by the following main
equality:\footnote{For more details see Subsection \ref{subsecbasbgd},
page \pageref{subsecbasbgd}.}
$$(B\ |\ N)=(I\ |-\!A)\Pi^T,$$
where $I$ is the unity matrix of the order $m$, whose columns correspond
to auxiliary variables; $A$ is the original constraint
$m\times n$-matrix, whose columns correspond to structural variables;
$(I\ |-\!A)$ is the augmented constraint\linebreak
$m\times(m+n)$-matrix, whose columns correspond to all (auxiliary and
structural) variables following in the original order; $\Pi$ is a
permutation matrix of the order $m+n$; and $N$ is a rectangular
$m\times n$-matrix, whose columns correspond to non-basic (auxiliary
and/or structural) variables.

For various reasons it may be necessary to solve linear systems with
matrix $B$. To provide this possibility the GLPK implementation
maintains an invertable form of $B$ (that is, some representation of
$B^{-1}$) called the {\it basis factorization}, which is an internal
component of the problem object. Typically, the basis factorization is
computed by the simplex solver, which keeps it in the problem object
to be available for other computations.

Should note that any changes in the problem object, which affects the
basis matrix (e.g. changing the status of a row or column, changing
a basic column of the constraint matrix, removing an active constraint,
etc.), invalidates the basis factorization. So before calling any API
routine, which uses the basis factorization, the application program
must make sure (using the routine \verb|glp_bf_exists|) that the
factorization exists and therefore available for computations.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{Compute the basis factorization}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_factorize(glp_prob *lp);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_factorize| computes the basis factorization for
the current basis associated with the specified problem
object.\footnote{The current basis is defined by the current statuses
of rows (auxiliary variables) and columns (structural variables).}

The basis factorization is computed from ``scratch'' even if it exists,
so the application program may use the routine \verb|glp_bf_exists|,
and, if the basis factorization already exists, not to call the routine
\verb|glp_factorize| to prevent an extra work.

The routine \verb|glp_factorize| {\it does not} compute components of
the basic solution (i.e. primal and dual values).

\subsubsection*{Returns}

\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
0 & The basis factorization has been successfully computed.\\
\verb|GLP_EBADB| & The basis matrix is invalid, because the number of
basic (auxiliary and structural) variables is not the same as the number
of rows in the problem object.\\
\verb|GLP_ESING| & The basis matrix is singular within the working
precision.\\
\verb|GLP_ECOND| & The basis matrix is ill-conditioned, i.e. its
condition number is too large.\\
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{Check if the basis factorization has been updated}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_bf_updated(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

If the basis factorization has been just computed from ``scratch'', the
routine \verb|glp_bf_updated| returns zero. Otherwise, if the
factorization has been updated at least once, the routine returns
non-zero.

\subsubsection*{Comments}

{\it Updating} the basis factorization means recomputing it to reflect
changes in the basis matrix. For example, on every iteration of the
simplex method some column of the current basis matrix is replaced by a
new column that gives a new basis matrix corresponding to the adjacent
basis. In this case computing the basis factorization for the adjacent
basis from ``scratch'' (as the routine \verb|glp_factorize| does) would
be too time-consuming.

On the other hand, since the basis factorization update is a numeric
computational procedure, applying it many times may lead to accumulating
round-off errors. Therefore the basis is periodically refactorized
(reinverted) from ``scratch'' (with the routine \verb|glp_factorize|)
that allows improving its numerical properties.

The routine \verb|glp_bf_updated| allows determining if the basis
factorization has been updated at least once since it was computed from
``scratch''.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{Retrieve basis factorization control parameters}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_get_bfcp(glp_prob *lp, glp_bfcp *parm);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_get_bfcp| retrieves control parameters, which are
used on computing and updating the basis factorization associated with
the specified problem object.

Current values of the control parameters are stored in a \verb|glp_bfcp|
structure, which the parameter \verb|parm| points to. For a detailed
description of the structure \verb|glp_bfcp| see comments to the routine
\verb|glp_set_bfcp| in the next subsection.

\subsubsection*{Comments}

The purpose of the routine \verb|glp_get_bfcp| is two-fold. First, it
allows the application program obtaining current values of control
parameters used by internal GLPK routines, which compute and update the
basis factorization.

The second purpose of this routine is to provide proper values for all
fields of the structure \verb|glp_bfcp| in the case when the application
program needs to change some control parameters.

\subsection{Change basis factorization control parameters}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_bfcp(glp_prob *lp, const glp_bfcp *parm);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_bfcp| changes control parameters, which are
used by internal GLPK routines on computing and updating the basis
factorization associated with the specified problem object.

New values of the control parameters should be passed in a structure
\verb|glp_bfcp|, which the parameter \verb|parm| points to. For a
detailed description of the structure \verb|glp_bfcp| see paragraph
``Control parameters'' below.

The parameter \verb|parm| can be specified as \verb|NULL|, in which case
all control parameters are reset to their default values.

\subsubsection*{Comments}

Before changing some control parameters with the routine
\verb|glp_set_bfcp| the application program should retrieve current
values of all control parameters with the routine \verb|glp_get_bfcp|.
This is needed for backward compatibility, because in the future there
may appear new members in the structure \verb|glp_bfcp|.

Note that new values of control parameters come into effect on a next
computation of the basis factorization, not immediately.

\subsubsection*{Example}

\begin{verbatim}
glp_prob *lp;
glp_bfcp parm;
. . .
/* retrieve current values of control parameters */
glp_get_bfcp(lp, &parm);
/* change the threshold pivoting tolerance */
parm.piv_tol = 0.05;
/* set new values of control parameters */
glp_set_bfcp(lp, &parm);
. . .
\end{verbatim}

\subsubsection*{Control parameters}

This paragraph describes all basis factorization control parameters
currently used in the package. Symbolic names of control parameters are
names of corresponding members in the structure \verb|glp_bfcp|.

\def\arraystretch{1}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int type} (default: {\tt GLP\_BF\_FT})} \\
&Basis factorization type:\\
&\verb|GLP_BF_FT| --- $LU$ + Forrest--Tomlin update;\\
&\verb|GLP_BF_BG| --- $LU$ + Schur complement + Bartels--Golub update;\\
&\verb|GLP_BF_GR| --- $LU$ + Schur complement + Givens rotation update.
\\
&In case of \verb|GLP_BF_FT| the update is applied to matrix $U$, while
in cases of \verb|GLP_BF_BG| and \verb|GLP_BF_GR| the update is applied
to the Schur complement.
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int lu\_size} (default: {\tt 0})} \\
&The initial size of the Sparse Vector Area, in non-zeros, used on
computing $LU$-factorization of the basis matrix for the first time.
If this parameter is set to 0, the initial SVA size is determined
automatically.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double piv\_tol} (default: {\tt 0.10})} \\
&Threshold pivoting (Markowitz) tolerance, 0 $<$ \verb|piv_tol| $<$ 1,
used on computing $LU$-factorization of the basis matrix. Element
$u_{ij}$ of the active submatrix of factor $U$ fits to be pivot if it
satisfies to the stability criterion
$|u_{ij}| >= {\tt piv\_tol}\cdot\max|u_{i*}|$, i.e. if it is not very
small in the magnitude among other elements in the same row. Decreasing
this parameter may lead to better sparsity at the expense of numerical
accuracy, and vice versa.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int piv\_lim} (default: {\tt 4})} \\
&This parameter is used on computing $LU$-factorization of the basis
matrix and specifies how many pivot candidates needs to be considered
on choosing a pivot element, \verb|piv_lim| $\geq$ 1. If \verb|piv_lim|
candidates have been considered, the pivoting routine prematurely
terminates the search with the best candidate found.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int suhl} (default: {\tt GLP\_ON})} \\
&This parameter is used on computing $LU$-factorization of the basis
matrix. Being set to {\tt GLP\_ON} it enables applying the following
heuristic proposed by Uwe Suhl: if a column of the active submatrix has
no eligible pivot candidates, it is no more considered until it becomes
a column singleton. In many cases this allows reducing the time needed
for pivot searching. To disable this heuristic the parameter \verb|suhl|
should be set to {\tt GLP\_OFF}.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double eps\_tol} (default: {\tt 1e-15})} \\
&Epsilon tolerance, \verb|eps_tol| $\geq$ 0, used on computing
$LU$-factorization of the basis matrix. If an element of the active
submatrix of factor $U$ is less than \verb|eps_tol| in the magnitude,
it is replaced by exact zero.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double max\_gro} (default: {\tt 1e+10})} \\
&Maximal growth of elements of factor $U$, \verb|max_gro| $\geq$ 1,
allowable on computing $LU$-factorization of the basis matrix. If on
some elimination step the ratio $u_{big}/b_{max}$ (where $u_{big}$ is
the largest magnitude of elements of factor $U$ appeared in its active
submatrix during all the factorization process, $b_{max}$ is the largest
magnitude of elements of the basis matrix to be factorized), the basis
matrix is considered as ill-conditioned.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int nfs\_max} (default: {\tt 50})} \\
&Maximal number of additional row-like factors (entries of the eta
file), \verb|nfs_max| $\geq$ 1, which can be added to $LU$-factorization
of the basis matrix on updating it with the Forrest--Tomlin technique.
This parameter is used only once, before $LU$-factorization is computed
for the first time, to allocate working arrays. As a rule, each update
adds one new factor (however, some updates may need no addition), so
this parameter limits the number of updates between refactorizations.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double upd\_tol} (default: {\tt 1e-6})} \\
&Update tolerance, 0 $<$ \verb|upd_tol| $<$ 1, used on updating
$LU$-factorization of the basis matrix with the Forrest--Tomlin
technique. If after updating the magnitude of some diagonal element
$u_{kk}$ of factor $U$ becomes less than
${\tt upd\_tol}\cdot\max(|u_{k*}|, |u_{*k}|)$, the factorization is
considered as inaccurate.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int nrs\_max} (default: {\tt 50})} \\
&Maximal number of additional rows and columns, \verb|nrs_max| $\geq$ 1,
which can be added to $LU$-factorization of the basis matrix on updating
it with the Schur complement technique. This parameter is used only
once, before $LU$-factorization is computed for the first time, to
allocate working arrays. As a rule, each update adds one new row and
column (however, some updates may need no addition), so this parameter
limits the number of updates between refactorizations.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int rs\_size} (default: {\tt 0})} \\
&The initial size of the Sparse Vector Area, in non-zeros, used to
store non-zero elements of additional rows and columns introduced on
updating $LU$-factorization of the basis matrix with the Schur
complement technique. If this parameter is set to 0, the initial SVA
size is determined automatically.\\
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{Retrieve the basis header information}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_bhead(glp_prob *lp, int k);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_get_bhead| returns the basis header information
for the current basis associated with the specified problem object.

\subsubsection*{Returns}

If basic variable $(x_B)_k$, $1\leq k\leq m$, is $i$-th auxiliary
variable ($1\leq i\leq m$), the routine returns $i$. Otherwise, if
$(x_B)_k$ is $j$-th structural variable ($1\leq j\leq n$), the routine
returns $m+j$. Here $m$ is the number of rows and $n$ is the number of
columns in the problem object.

\subsubsection*{Comments}

Sometimes the application program may need to know which original
(auxiliary and structural) variable correspond to a given basic
variable, or, that is the same, which column of the augmented constraint
matrix $(I\ |-\!A)$ correspond to a given column of the basis matrix
$B$.

\def\arraystretch{1}

The correspondence is defined as follows:\footnote{For more details see
Subsection \ref{subsecbasbgd}, page \pageref{subsecbasbgd}.}
$$\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right)=
\Pi\left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)
\ \ \Leftrightarrow
\ \ \left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)=
\Pi^T\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right),$$
where $x_B$ is the vector of basic variables, $x_N$ is the vector of
non-basic variables, $x_R$ is the vector of auxiliary variables
following in their original order,\footnote{The original order of
auxiliary and structural variables is defined by the ordinal numbers
of corresponding rows and columns in the problem object.} $x_S$ is the
vector of structural variables following in their original order, $\Pi$
is a permutation matrix (which is a component of the basis
factorization).

Thus, if $(x_B)_k=(x_R)_i$ is $i$-th auxiliary variable, the routine
returns $i$, and if $(x_B)_k=(x_S)_j$ is $j$-th structural variable,
the routine returns $m+j$, where $m$ is the number of rows in the
problem object.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{Retrieve row index in the basis header}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_row_bind(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_row_bind| returns the index $k$ of basic
variable $(x_B)_k$, $1\leq k\leq m$, which is $i$-th auxiliary variable
(that is, the auxiliary variable corresponding to $i$-th row),
$1\leq i\leq m$, in the current basis associated with the specified
problem object, where $m$ is the number of rows. However, if $i$-th
auxiliary variable is non-basic, the routine returns zero.

\subsubsection*{Comments}

The routine \verb|glp_get_row_bind| is an inverse to the routine
\verb|glp_get_bhead|: if \verb|glp_get_bhead|$(lp,k)$ returns $i$,
\verb|glp_get_row_bind|$(lp,i)$ returns $k$, and vice versa.

\subsection{Retrieve column index in the basis header}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_col_bind(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_col_bind| returns the index $k$ of basic
variable $(x_B)_k$, $1\leq k\leq m$, which is $j$-th structural
variable (that is, the structural variable corresponding to $j$-th
column), $1\leq j\leq n$, in the current basis associated with the
specified problem object, where $m$ is the number of rows, $n$ is the
number of columns. However, if $j$-th structural variable is non-basic,
the routine returns zero.

\subsubsection*{Comments}

The routine \verb|glp_get_col_bind| is an inverse to the routine
\verb|glp_get_bhead|: if \verb|glp_get_bhead|$(lp,k)$ returns $m+j$,
\verb|glp_get_col_bind|$(lp,j)$ returns $k$, and vice versa.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{Perform forward transformation (FTRAN)}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_ftran(glp_prob *lp, double x[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ftran| performs forward transformation (FTRAN),
i.e. it solves the system $Bx=b$, where $B$ is the basis matrix
associated with the specified problem object, $x$ is the vector of
unknowns to be computed, $b$ is the vector of right-hand sides.

On entry to the routine elements of the vector $b$ should be stored in
locations \verb|x[1]|, \dots, \verb|x[m]|, where $m$ is the number of
rows. On exit the routine stores elements of the vector $x$ in the same
locations.

\subsection{Perform backward transformation (BTRAN)}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_btran(glp_prob *lp, double x[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_btran| performs backward transformation (BTRAN),
i.e. it solves the system $B^Tx=b$, where $B^T$ is a matrix transposed
to the basis matrix $B$ associated with the specified problem object,
$x$ is the vector of unknowns to be computed, $b$ is the vector of
right-hand sides.

On entry to the routine elements of the vector $b$ should be stored in
locations \verb|x[1]|, \dots, \verb|x[m]|, where $m$ is the number of
rows. On exit the routine stores elements of the vector $x$ in the same
locations.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{Warm up LP basis}

\subsubsection*{Synopsis}

\begin{verbatim}
int lpx_warm_up(glp_prob *lp);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_warm_up| ``warms up'' the LP basis for the
specified problem object using current statuses assigned to rows and
columns (i.e. to auxiliary and structural variables).

``Warming up'' includes reinverting (factorizing) the basis matrix (if
neccesary), computing primal and dual components as well as determining
primal and dual statuses of the basic solution.

\subsubsection*{Returns}

The routine \verb|lpx_warm_up| returns one of the following exit codes:

\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
\verb|LPX_E_OK| & the LP basis has been successfully ``warmed up''. \\
\verb|LPX_E_EMPTY|  & the problem has no rows and/or no columns. \\
\verb|LPX_E_BADB|   & the LP basis is invalid, because the number of
   basic variables is not the same as the number of rows. \\
\verb|LPX_E_SING|   & the basis matrix is numerically singular or
   ill-condi\-tioned.
\end{tabular}

\subsection{Compute row of the simplex tableau}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_eval_tab_row(glp_prob *lp, int k, int ind[],
      double val[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_eval_tab_row| computes a row of the current
simplex tableau (see Subsection 3.1.1, formula (3.12)), which (row)
corresponds to some basic variable specified by the parameter $k$ as
follows: if $1\leq k\leq m$, the basic variable is $k$-th auxiliary
variable, and if $m+1\leq k\leq m+n$, the basic variable is $(k-m)$-th
structural variable, where $m$ is the number of rows and $n$ is the
number of columns in the specified problem object. The basis
factorization must exist.

The computed row shows how the specified basic variable depends on
non-basic variables:
$$x_k=(x_B)_i=\xi_{i1}(x_N)_1+\xi_{i2}(x_N)_2+\dots+\xi_{in}(x_N)_n,$$
where $\xi_{i1}$, $\xi_{i2}$, \dots, $\xi_{in}$ are elements of the
simplex table row, $(x_N)_1$, $(x_N)_2$, \dots, $(x_N)_n$ are non-basic
(auxiliary and structural) variables.

The routine stores column indices and corresponding numeric values of
non-zero elements of the computed row in unordered sparse format in
locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
\dots, \verb|val[len]|, respectively, where $0\leq{\tt len}\leq n$ is
the number of non-zero elements in the row returned on exit.

Element indices stored in the array \verb|ind| have the same sense as
index $k$, i.e. indices 1 to $m$ denote auxiliary variables while
indices $m+1$ to $m+n$ denote structural variables (all these variables
are obviously non-basic by definition).

\subsubsection*{Returns}

The routine \verb|glp_eval_tab_row| returns \verb|len|, which is the
number of non-zero elements in the simplex table row stored in the
arrays \verb|ind| and \verb|val|.

\subsubsection*{Comments}

A row of the simplex table is computed as follows. At first, the
routine checks that the specified variable $x_k$ is basic and uses the
permutation matrix $\Pi$ (3.7) to determine index $i$ of basic variable
$(x_B)_i$, which corresponds to $x_k$.

The row to be computed is $i$-th row of the matrix $\Xi$ (3.12),
therefore:
$$\xi_i=e_i^T\Xi=-e_i^TB^{-1}N=-(B^{-T}e_i)^TN,$$
where $e_i$ is $i$-th unity vector. So the routine performs BTRAN to
obtain $i$-th row of the inverse $B^{-1}$:
$$\varrho_i=B^{-T}e_i,$$
and then computes elements of the simplex table row as inner products:
$$\xi_{ij}=-\varrho_i^TN_j,\ \ j=1,2,\dots,n,$$
where $N_j$ is $j$-th column of matrix $N$ (3.9), which (column)
corresponds to non-basic variable $(x_N)_j$. The permutation matrix
$\Pi$ is used again to convert indices $j$ of non-basic columns to
original ordinal numbers of auxiliary and structural variables.

\subsection{Compute column of the simplex tableau}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_eval_tab_col(glp_prob *lp, int k, int ind[],
      double val[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_eval_tab_col| computes a column of the current
simplex tableau (see Subsection 3.1.1, formula (3.12)), which (column)
corresponds to some non-basic variable specified by the parameter $k$:
if $1\leq k\leq m$, the non-basic variable is $k$-th auxiliary variable,
and if $m+1\leq k\leq m+n$, the non-basic variable is $(k-m)$-th
structural variable, where $m$ is the number of rows and $n$ is the
number of columns in the specified problem object. The basis
factorization must exist.

The computed column shows how basic variables depends on the specified
non-basic variable $x_k=(x_N)_j$:
$$
\begin{array}{r@{\ }c@{\ }l@{\ }l}
(x_B)_1&=&\dots+\xi_{1j}(x_N)_j&+\dots\\
(x_B)_2&=&\dots+\xi_{2j}(x_N)_j&+\dots\\
.\ \ .&.&.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\\
(x_B)_m&=&\dots+\xi_{mj}(x_N)_j&+\dots\\
\end{array}
$$
where $\xi_{1j}$, $\xi_{2j}$, \dots, $\xi_{mj}$ are elements of the
simplex table column, $(x_B)_1$, $(x_B)_2$, \dots, $(x_B)_m$ are basic
(auxiliary and structural) variables.

The routine stores row indices and corresponding numeric values of
non-zero elements of the computed column in unordered sparse format in
locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
\dots, \verb|val[len]|, respectively, where $0\leq{\tt len}\leq m$ is
the number of non-zero elements in the column returned on exit.

Element indices stored in the array \verb|ind| have the same sense as
index $k$, i.e. indices 1 to $m$ denote auxiliary variables while
indices $m+1$ to $m+n$ denote structural variables (all these variables
are obviously basic by definition).

\subsubsection*{Returns}

The routine \verb|glp_eval_tab_col| returns \verb|len|, which is the
number of non-zero elements in the simplex table column stored in the
arrays \verb|ind| and \verb|val|.

\subsubsection*{Comments}

A column of the simplex table is computed as follows. At first, the
routine checks that the specified variable $x_k$ is non-basic and uses
the permutation matrix $\Pi$ (3.7) to determine index $j$ of non-basic
variable $(x_N)_j$, which corresponds to $x_k$.

The column to be computed is $j$-th column of the matrix $\Xi$ (3.12),
therefore:
$$\Xi_j=\Xi e_j=-B^{-1}Ne_j=-B^{-1}N_j,$$
where $e_j$ is $j$-th unity vector, $N_j$ is $j$-th column of matrix
$N$ (3.9). So the routine performs FTRAN to transform $N_j$ to the
simplex table column $\Xi_j=(\xi_{ij})$ and uses the permutation matrix
$\Pi$ to convert row indices $i$ to original ordinal numbers of
auxiliary and structural variables.

\subsection{Transform explicitly specified row}

\subsubsection*{Synopsis}

\begin{verbatim}
int lpx_transform_row(glp_prob *lp, int len, int ind[],
      double val[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_transform_row| performs the same operation as the
routine \verb|lpx_eval_tab_row|, except that the transformed row is
specified explicitly.

The explicitly specified row may be thought as a linear form:
$$x=a_1x_{m+1}+a_2x_{m+2}+\dots+a_nx_{m+n},\eqno(1)$$
where $x$ is an auxiliary variable for this row, $a_j$ are coefficients
of the linear form, $x_{m+j}$ are structural variables.

On entry column indices and numerical values of non-zero coefficients
$a_j$ of the transformed row should be placed in locations
\verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
\verb|val[len]|, where \verb|len| is number of non-zero coefficients.

This routine uses the system of equality constraints and the current
basis in order to express the auxiliary variable $x$ in (1) through the
current non-basic variables (as if the transformed row were added to
the problem object and the auxiliary variable $x$ were basic), i.e. the
resultant row has the form:
$$x=\alpha_1(x_N)_1+\alpha_2(x_N)_2+\dots+\alpha_n(x_N)_n,\eqno(2)$$
where $\alpha_j$ are influence coefficients, $(x_N)_j$ are non-basic
(auxiliary and structural) variables, $n$ is number of columns in the
specified problem object.

On exit the routine stores indices and numerical values of non-zero
coefficients $\alpha_j$ of the resultant row (2) in locations
\verb|ind[1]|, \dots, \verb|ind[len']| and \verb|val[1]|, \dots,
\verb|val[len']|, where $0\leq{\tt len'}\leq n$ is the number of
non-zero coefficients in the resultant row returned by the routine.
Note that indices of non-basic variables stored in the array \verb|ind|
correspond to original ordinal numbers of variables: indices 1 to $m$
mean auxiliary variables and indices $m+1$ to $m+n$ mean structural
ones.

\subsubsection*{Returns}

The routine \verb|lpx_transform_row| returns \verb|len'|, the number of
non-zero coefficients in the resultant row stored in the arrays
\verb|ind| and \verb|val|.

\subsection{Transform explicitly specified column}

\subsubsection*{Synopsis}

\begin{verbatim}
int lpx_transform_col(glp_prob *lp, int len, int ind[],
      double val[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_transform_col| performs the same operation as the
routine \verb|lpx_eval_tab_col|, except that the transformed column is
specified explicitly.

The explicitly specified column may be thought as it were added to
the original system of equality constraints:
$$
\begin{array}{rl}
x_1 &= a_{11}x_{m+1}+\dots+a_{1n}x_{m+n}+a_1x \\
x_2 &= a_{21}x_{m+1}+\dots+a_{2n}x_{m+n}+a_2x \\
    &  \dots \dots \dots \\
x_m &= a_{m1}x_{m+1}+\dots+a_{mn}x_{m+n}+a_mx \\
\end{array} \eqno(1)
$$
where $x_i$ are auxiliary variables, $x_{m+j}$ are structural variables
(presented in the problem object), $x$ is a structural variable for the
explicitly specified column, $a_i$ are constraint coefficients for $x$.

On entry row indices and numerical values of non-zero coefficients
$a_i$ of the transformed column should be placed in locations
\verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
\verb|val[len]|, where \verb|len| is number of non-zero coefficients.

This routine uses the system of equality constraints and the current
basis in order to express the current basic variables through the
structural variable $x$ in (1) (as if the transformed column were added
to the problem object and the variable $x$ were non-basic):
$$
\begin{array}{rl}
(x_B)_1 &= \dots + \alpha_{1}x \\
(x_B)_2 &= \dots + \alpha_{2}x \\
        &  \dots \dots \dots   \\
(x_B)_m &= \dots + \alpha_{m}x \\
\end{array} \eqno(2)
$$
where $\alpha_i$ are influence coefficients, $x_B$ are basic (auxiliary
and structural) variables, $m$ is number of rows in the specified
problem object.

On exit the routine stores indices and numerical values of non-zero
coefficients $\alpha_i$ of the resultant column (2) in locations
\verb|ind[1]|, \dots, \verb|ind[len']| and \verb|val[1]|, \dots,
\verb|val[len']|, where $0\leq{\tt len'}\leq m$ is the number of
non-zero coefficients in the resultant column returned by the routine.
Note that indices of basic variables stored in the array \verb|ind|
correspond to original ordinal numbers of variables, i.e. indices
1 to $m$ mean auxiliary variables, indices $m+1$ to $m+n$ mean
structural ones.

\subsubsection*{Returns}

The routine \verb|lpx_transform_col| returns \verb|len'|, the number of
non-zero coefficients in the resultant column stored in the arrays
\verb|ind| and \verb|val|.

\subsection{Perform primal ratio test}

\subsubsection*{Synopsis}

\begin{verbatim}
int lpx_prim_ratio_test(glp_prob *lp, int len, int ind[],
      double val[], int how, double tol);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_prim_ratio_test| performs the primal ratio test
for an explicitly specified column of the simplex table.

The primal basic solution associated with an LP problem object, which
the parameter \verb|lp| points to, should be feasible. No components
of the LP problem object are changed by the routine.

The explicitly specified column of the simplex table shows how the
basic variables $x_B$ depend on some non-basic variable $y$ (which is
not necessarily presented in the problem object):
$$
\begin{array}{rl}
(x_B)_1 &= \dots + \alpha_{1}y \\
(x_B)_2 &= \dots + \alpha_{2}y \\
        &  \dots \dots \dots   \\
(x_B)_m &= \dots + \alpha_{m}y \\
\end{array} \eqno(1)
$$

The column (1) is specifed on entry to the routine using the sparse
format. Ordinal numbers of basic variables $(x_B)_i$ should be placed in
locations \verb|ind[1]|, \dots, \verb|ind[len]|, where ordinal number
1 to $m$ denote auxiliary variables, and ordinal numbers $m+1$ to $m+n$
denote structural variables. The corresponding non-zero coefficients
$\alpha_i$ should be placed in locations \verb|val[1]|, \dots,
\verb|val[len]|. The arrays \verb|ind| and \verb|val| are not changed by
the routine.

The parameter \verb|how| specifies in which direction the variable $y$
changes on entering the basis: $+1$ means increasing, $-1$ means
decreasing.

The parameter \verb|tol| is a relative tolerance (small positive number)
used by the routine to skip small $\alpha_i$ in the column (1).

The routine determines the ordinal number of a basic variable
(among specified in \verb|ind[1]|, \dots, \verb|ind[len]|), which
reaches its (lower or upper) bound first before any other basic
variables do and which therefore should leave the basis instead the
variable $y$ in order to keep primal feasibility, and returns it on
exit. If the choice cannot be made (i.e. if the adjacent basic solution
is primal unbounded due to $y$), the routine returns zero.

\subsubsection*{Note}

If the non-basic variable $y$ is presented in the LP problem object, the
column (1) can be computed using the routine \verb|lpx_eval_tab_col|.
Otherwise it can be computed using the routine \verb|lpx_transform_col|.

\subsubsection*{Returns}

The routine \verb|lpx_prim_ratio_test| returns the ordinal number of
some basic variable $(x_B)_i$, which should leave the basis instead the
variable $y$ in order to keep primal feasibility. If the adjacent basic
solution is primal unbounded and therefore the choice cannot be made,
the routine returns zero.

\newpage

\subsection{Perform dual ratio test}

\subsubsection*{Synopsis}

\begin{verbatim}
int lpx_dual_ratio_test(glp_prob *lp, int len, int ind[],
      double val[], int how, double tol);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_dual_ratio_test| performs the dual ratio test for
an explicitly specified row of the simplex table.

The dual basic solution associated with an LP problem object, which the
parameter \verb|lp| points to, should be feasible. No components of the
LP problem object are changed by the routine.

The explicitly specified row of the simplex table is a linear form,
which shows how some basic variable $y$ (not necessarily presented in
the problem object) depends on non-basic variables $x_N$:
$$y=\alpha_1(x_N)_1+\alpha_2(x_N)_2+\dots+\alpha_n(x_N)_n.\eqno(1)$$

The linear form (1) is specified on entry to the routine using the
sparse format. Ordinal numbers of non-basic variables $(x_N)_j$ should
be placed in locations \verb|ind[1]|, \dots, \verb|ind[len]|, where
ordinal numbers 1 to $m$ denote auxiliary variables, and ordinal numbers
$m+1$ to $m+n$ denote structural variables. The corresponding non-zero
coefficients $\alpha_j$ should be placed in locations \verb|val[1]|,
\dots, \verb|val[len]|. The arrays \verb|ind| and \verb|val| are not
changed by the routine.

The parameter \verb|how| specifies in which direction the variable $y$
changes on leaving the basis: $+1$ means increasing, $-1$ means
decreasing.

The parameter \verb|tol| is a relative tolerance (small positive number)
used by the routine to skip small $\alpha_j$ in the form (1).

The routine determines the ordinal number of some non-basic variable
(among specified in \verb|ind[1]|, \dots, \verb|ind[len]|), whose
reduced cost reaches its (zero) bound first before this happens for any
other non-basic variables and which therefore should enter the basis
instead the variable $y$ in order to keep dual feasibility, and returns
it on exit. If the choice cannot be made (i.e. if the adjacent basic
solution is dual unbounded due to $y$), the routine returns zero.

\subsubsection*{Note}

If the basic variable $y$ is presented in the LP problem object, the
row (1) can be computed using the routine \verb|lpx_eval_tab_row|.
Otherwise it can be computed using the routine \verb|lpx_transform_row|.

\subsubsection*{Returns}

The routine \verb|lpx_dual_ratio_test| returns the ordinal number of
some non-basic variable $(x_N)_j$, which should enter the basis instead
the variable $y$ in order to keep dual feasibility. If the adjacent
basic solution is dual unbounded and therefore the choice cannot be
made, the routine returns zero.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\section{Branch-and-cut interface routines}

\subsection{Introduction}

The GLPK MIP solver based on the branch-and-cut method allows the
application to control the solution process. This is attained by means
of the user-defined callback routine, which is called by the solver at
various points of the branch-and-cut algorithm.

The callback routine passed to the MIP solver should be written by the
user and has the following specification:\footnote{The name
{\tt foo\_bar} used here is a placeholder for the callback routine
name.}

\begin{verbatim}
   void foo_bar(glp_tree *tree, void *info);
\end{verbatim}

\noindent
where \verb|tree| is a pointer to the data structure \verb|glp_tree|,
which should be used on subsequent calls to branch-and-cut interface
routines, and \verb|info| is a transit pointer passed to the routine
\verb|glp_intopt|, which may be used by the application program to pass
some external data to the callback routine.

The callback routine is passed to the MIP solver through the control
parameter structure \verb|glp_iocp| (see Chapter ``GLPK API Routines'',
Section ``Solve MIP problem with B\&B method'') as follows:

\begin{verbatim}
   glp_prob *mip;
   glp_iocp parm;
   . . .
   glp_init_iocp(&parm);
   . . .
   parm.cb_func = foo_bar;
   parm.cb_info = ... ;
   ret = glp_intopt(mip, &parm);
   . . .
\end{verbatim}

To determine why it is being called by the MIP solver the callback
routine should use the routine \verb|glp_ios_reason| (described in this
section below), which returns a code indicating the reason for calling.
Depending on the reason the callback routine may perform necessary
actions to control the solution process.

The reason codes, which correspond to various point of the
branch-and-cut algorithm implemented in the MIP solver, are described
in comments to the routine \verb|glp_ios_reason|.

\pagebreak

To ignore calls for reasons, which are not processed by the callback
routine, it should just return to the MIP solver doing nothing. For
example:

\begin{verbatim}
void foo_bar(glp_tree *tree, void *info)
{     . . .
      switch (glp_ios_reason(tree))
      {  case GLP_IBRANCH:
            . . .
            break;
         case GLP_ISELECT:
            . . .
            break;
         default:
            /* ignore call for other reasons */
            break;
      }
      return;
}
\end{verbatim}

To control the solution process as well as to obtain necessary
information the callback routine may use branch-and-cut interface
routines described in this section. Names of all these routines begin
with `\verb|glp_ios_|'.

\subsection{Branch-and-cut algorithm}

This subsection contains a schematic description of the branch-and-cut
algorithm as it is implemented in the GLPK MIP solver.

\medskip

{\it 1. Initialization}

Set $L:=\{P_0\}$, where $L$ is the {\it active list} (i.e. the list of
active subproblems), $P_0$ is the original MIP problem to be solved.

Set $\overline{z}:=+\infty$ (in case of minimization) or
$\overline{z}:=-\infty$ (in case of maximization), where $\overline{z}$
is {\it incumbent value}, i.e. an upper (minimization) or lower
(maximization) global bound for $z^*$, the optimal objective value for
$P^0$.

\medskip

{\it 2. Subproblem selection}

If $L=\emptyset$ then GO TO 9.

Select $P\in L$, i.e. make active subproblem $P$ current.

\medskip

{\it 3. Solving LP relaxation}

Solve $P_{LP}$, which is LP relaxation of $P$.

If $P_{LP}$ has no primal feasible solution then GO TO 8.

Let $z_{LP}^*$ be the optimal objective value for $P_{LP}$.

If $z_{LP}^*\geq\overline{z}$ (in case of minimization) or
$z_{LP}^*\leq\overline{z}$ (in case of maximization) then GO TO 8.

\medskip

{\it 4. Adding ``lazy'' constraints}

Let $x_{LP}^*$ be the optimal solution to $P_{LP}$.

If there are ``lazy'' constraints (i.e. essential constraints not
included in the original MIP problem $P_0$), which are violated at the
optimal point $x_{LP}^*$, add them to $P$, and GO TO 3.

\medskip

{\it 5. Check for integrality}

Let $x_j$ be a variable, which is required to be integer, and let
$x_j^*\in x_{LP}^*$ be its value in the optimal solution to $P_{LP}$.

If $x_j^*$ is integral for all integer variables, then a better integer
feasible solution is found. Store its components, set
$\overline{z}:=z_{LP}^*$, and GO TO 8.

\medskip

{\it 6. Adding cutting planes}

If there are cutting planes (i.e. valid constraints for $P$), which are
violated at the optimal point $x_{LP}^*$, add them to $P$, and GO TO 3.

\medskip

{\it 7. Branching}

Select {\it branching variable} $x_j$, i.e. a variable, which is
required to be integer, and whose value $x_j^*\in x_{LP}^*$ is
fractional in the optimal solution to $P_{LP}$.

Create new subproblem $P_D$ (so called {\it down branch}), which is
identical to the current subproblem $P$ with exception that the upper
bound of $x_j$ is replaced by $\lfloor x_j^*\rfloor$. (For example,
if $x_j^*=3.14$, the new upper bound of $x_j$ in the down branch will
be $\lfloor 3.14\rfloor=3$.)

Create new subproblem $P_U$ (so called {\it up branch}), which is
identical to the current subproblem $P$ with exception that the lower
bound of $x_j$ is replaced by $\lceil x_j^*\rceil$. (For example, if
$x_j^*=3.14$, the new lower bound of $x_j$ in the up branch will be
$\lceil 3.14\rceil=4$.)

Set $L:=L\backslash\{P\}\cup\{P_D,P_U\}$, i.e. remove the current
subproblem $P$ from the active list and add two new subproblems $P_D$
and $P_U$ to the active list. Then GO TO 2.

\medskip

{\it 8. Pruning}

Remove from the active list $L$ all subproblems (including the current
one), whose local bound $\widetilde{z}$ is not better than the global
bound $\overline{z}$, i.e. set $L:=L\backslash\{P\}$ for all $P$, where
$\widetilde{z}\geq\overline{z}$ (in case of minimization) or
$\widetilde{z}\leq\overline{z}$ (in case of maximization), and then
GO TO 2.

The local bound $\widetilde{z}$ for subproblem $P$ is an lower
(minimization) or upper (maximization) bound for integer optimal
solution to {\it this} subproblem (not to the original problem). This
bound is local in the sense that only subproblems in the subtree rooted
at node $P$ cannot have better integer feasible solutions. Note that
the local bound is not necessarily the optimal objective value to LP
relaxation $P_LP$.

\medskip

{\it 9. Termination}

If $\overline{z}=+\infty$ (in case of minimization) or
$\overline{z}=-\infty$ (in case of maximization), the original problem
$P_0$ has no integer feasible solution. Otherwise, the last integer
feasible solution stored on step 5 is the integer optimal solution to
the original problem $P_0$. STOP.

\subsection{Determine reason for calling the callback routine}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_reason(glp_tree *tree);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ios_reason| returns a code, which indicates why
the user-defined callback routine is being called:

\verb|GLP_ISELECT| --- request for subproblem selection;

\verb|GLP_IPREPRO| --- request for preprocessing;

\verb|GLP_IROWGEN| --- request for row generation;

\verb|GLP_IHEUR  | --- request for heuristic solution;

\verb|GLP_ICUTGEN| --- request for cut generation;

\verb|GLP_IBRANCH| --- request for branching;

\verb|GLP_IBINGO | --- better integer solution found.

\subsubsection*{Request for subproblem selection}

The callback routine is called with the reason code \verb|GLP_ISELECT|
if the current subproblem has been fathomed and therefore there is no
current subproblem.

In response the callback routine may select some subproblem from the
active list and pass its reference number to the solver using the
routine \verb|glp_ios_select_node|, in which case the solver will
continue the search from the specified active subproblem.
If no selection is made by the callback routine, the solver uses a
backtracking technique specified by the control parameter
\verb|bt_tech|.

To explore the active list (i.e. active nodes of the branch-and-bound
tree) the callback routine may use the routines \verb|glp_ios_next_node|
and \verb|glp_ios_prev_node|.

\subsubsection*{Request for preprocessing}

The callback routine is called with the reason code \verb|GLP_IPREPRO|
if the current subproblem has just been selected from the active list
and its LP relaxation is not solved yet.

In response the callback routine may perform some preprocessing of the
current subproblem like tightening bounds of some variables or removing
bounds of some redundant constraints.

\subsubsection*{Request for row generation}

The callback routine is called with the reason code \verb|GLP_IROWGEN|
if LP relaxation of the current subproblem has just been solved to
optimality and its objective value is better than the best known integer
feasible solution.

In response the callback routine may add one or more ``lazy''
constraints (rows), which are violated by the current optimal solution
of LP relaxation, using API routines \verb|glp_add_rows|,
\verb|glp_set_row_name|, \verb|glp_set_row_bnds|, and
\verb|glp_set_mat_row|, in which case the solver will perform
re-optimization of LP relaxation. If there are no violated constraints,
the callback routine should just return.

Optimal solution components for LP relaxation can be obtained with API
routines \verb|glp_get_obj_val|, \verb|glp_get_row_prim|,
\verb|glp_get_row_dual|, \verb|glp_get_col_prim|, and
\verb|glp_get_col_dual|.

\subsubsection*{Request for heuristic solution}

The callback routine is called with the reason code \verb|GLP_IHEUR|
if LP relaxation of the current subproblem being solved to optimality
is integer infeasible (i.e. values of some structural variables of
integer kind are fractional), though its objective value is better than
the best known integer feasible solution.

In response the callback routine may try applying a primal heuristic
to find an integer feasible solution,\footnote{Integer feasible to the
original MIP problem, not to the current subproblem.} which is better
than the best known one. In case of success the callback routine may
store such better solution in the problem object using the routine
\verb|glp_ios_heur_sol|.

\subsubsection*{Request for cut generation}

The callback routine is called with the reason code \verb|GLP_ICUTGEN|
if LP relaxation of the current subproblem being solved to optimality
is integer infeasible (i.e. values of some structural variables of
integer kind are fractional), though its objective value is better than
the best known integer feasible solution.

In response the callback routine may reformulate the {\it current}
subproblem (before it will be splitted up due to branching) by adding to
the problem object one or more constraints (cutting planes), which cut
off the fractional optimal point from the MIP polytope.\footnote{Since
these constraints are added to the current subproblem, they may be
globally as well as locally valid.}

Adding cutting plane constraints is performed in the same way as adding
``lazy'' constraints for the reason code \verb|GLP_IROWGEN| (see above).

\subsubsection*{Request for branching}

The callback routine is called with the reason code \verb|GLP_IBRANCH|
if LP relaxation of the current subproblem being solved to optimality
is integer infeasible (i.e. values of some structural variables of
integer kind are fractional), though its objective value is better than
the best known integer feasible solution.

In response the callback routine may choose some variable suitable for
branching (i.e. integer variable, whose value in optimal solution to
LP relaxation of the current subproblem is fractional) and pass its
ordinal number to the solver using the routine
\verb|glp_ios_branch_upon|, in which case the solver splits the current
subproblem in two new subproblems and continues the search. If no choice
is made by the callback routine, the solver uses a branching technique
specified by the control parameter \verb|br_tech|.

\subsubsection*{Better integer solution found}

The callback routine is called with the reason code \verb|GLP_IBINGO|
if LP relaxation of the current subproblem being solved to optimality
is integer feasible (i.e. values of all structural variables of integer
kind are integral within the working precision) and its objective value
is better than the best known integer feasible solution.

Optimal solution components for LP relaxation can be obtained in the
same way as for the reason code \verb|GLP_IROWGEN| (see above).

Components of the new MIP solution can be obtained with API routines
\verb|glp_mip_obj_val|, \verb|glp_mip_row_val|, and
\verb|glp_mip_col_val|. Note, however, that due to row/cut generation
there may be additional rows in the problem object.

The difference between optimal solution to LP relaxation and
corresponding MIP solution is that in the former case some structural
variables of integer kind (namely, basic variables) may have values,
which are close to nearest integers within the working precision, while
in the latter case all such variables have exact integral values.

The reason \verb|GLP_IBINGO| is intended only for informational
purposes, so the callback routine should not modify the problem object
in this case.

\subsection{Access the problem object}

\subsubsection*{Synopsis}

\begin{verbatim}
glp_prob *glp_ios_get_prob(glp_tree *tree);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_get_prob| can be called from the user-defined
callback routine to access the problem object, which is used by the MIP
solver. It is the original problem object passed to the routine
\verb|glp_intopt| if the MIP presolver is not used; otherwise it is an
internal problem object built by the presolver.

\subsubsection*{Returns}

The routine \verb|glp_ios_get_prob| returns a pointer to the problem
object used by the MIP solver.

\subsubsection*{Comments}

To obtain various information about the problem instance the callback
routine can access the problem object (i.e. the object of type
\verb|glp_prob|) using the routine \verb|glp_ios_get_prob|. It is the
original problem object passed to the routine \verb|glp_intopt| if the
MIP presolver is not used; otherwise it is an internal problem object
built by the presolver.\footnote{Currently the latter feature is not
implemented.}

Should note that the problem object is used by the MIP solver during
the solution process for various purposes (to solve LP relaxations,
perform branching, etc.), so it may differ from the original problem
instance, for example, it may have additional rows, bounds of some
variables may be changed, etc. In particular, if the current subproblem
exists, LP segment of the problem object corresponds to its LP
relaxation. However, on exit from the solver the problem object is
restored to its original state.

To obtain information from the problem object the callback routine may
use any API routines, which do not change the object. However, using API
routines, which change the problem object, is restricted to stipulated
cases.

\subsection{Determine size of the branch-and-bound tree}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,
      int *t_cnt);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_tree_size| stores the following three counts
which characterize the current size of the branch-and-bound tree:

\verb|a_cnt| is the current number of active nodes, i.e. the current
size of the active list;

\verb|n_cnt| is the current number of all (active and inactive) nodes;

\verb|t_cnt| is the total number of nodes including those which have
been already removed from the tree. This count is increased whenever
a new node appears in the tree and never decreased.

If some of the parameters \verb|a_cnt|, \verb|n_cnt|, \verb|t_cnt| is
a null pointer, the corresponding count is not stored.

\subsection{Determine current active subproblem}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_curr_node(glp_tree *tree);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ios_curr_node| returns the reference number of the
current active subproblem. However, if the current subproblem does not
exist, the routine returns zero.

\subsection{Determine next active subproblem}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_next_node(glp_tree *tree, int p);
\end{verbatim}

\subsubsection*{Returns}

If the parameter $p$ is zero, the routine \verb|glp_ios_next_node|
returns the reference number of the first active subproblem. However,
if the tree is empty, zero is returned.

If the parameter $p$ is not zero, it must specify the reference number
of some active subproblem, in which case the routine returns the
reference number of the next active subproblem. However, if there is
no next active subproblem in the list, zero is returned.

All subproblems in the active list are ordered chronologically, i.e.
subproblem $A$ precedes subproblem $B$ if $A$ was created before $B$.

\subsection{Determine previous active subproblem}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_prev_node(glp_tree *tree, int p);
\end{verbatim}

\subsubsection*{Returns}

If the parameter $p$ is zero, the routine \verb|glp_ios_prev_node|
returns the reference number of the last active subproblem. However, if
the tree is empty, zero is returned.

If the parameter $p$ is not zero, it must specify the reference number
of some active subproblem, in which case the routine returns the
reference number of the previous active subproblem. However, if there
is no previous active subproblem in the list, zero is returned.

All subproblems in the active list are ordered chronologically, i.e.
subproblem $A$ precedes subproblem $B$ if $A$ was created before $B$.

\newpage

\subsection{Determine parent subproblem}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_up_node(glp_tree *tree, int p);
\end{verbatim}

\subsubsection*{Returns}

The parameter $p$ must specify the reference number of some (active or
inactive) subproblem, in which case the routine \verb|iet_get_up_node|
returns the reference number of its parent subproblem. However, if the
specified subproblem is the root of the tree and, therefore, has
no parent, the routine returns zero.

\subsection{Determine subproblem level}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_node_level(glp_tree *tree, int p);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ios_node_level| returns the level of the
subproblem,\linebreak whose reference number is $p$, in the
branch-and-bound tree. (The root subproblem has level 0, and the level
of any other subproblem is the level of its parent plus one.)

\subsection{Determine subproblem local bound}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_ios_node_bound(glp_tree *tree, int p);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ios_node_bound| returns the local bound for
(active or inactive) subproblem, whose reference number is $p$.

\subsubsection*{Comments}

The local bound for subproblem $p$ is an lower (minimization) or upper
(maximization) bound for integer optimal solution to {\it this}
subproblem (not to the original problem). This bound is local in the
sense that only subproblems in the subtree rooted at node $p$ cannot
have better integer feasible solutions.

On creating a subproblem (due to the branching step) its local bound is
inherited from its parent and then may get only stronger (never weaker).
For the root subproblem its local bound is initially set to
\verb|-DBL_MAX| (minimization) or \verb|+DBL_MAX| (maximization) and
then improved as the root LP relaxation has been solved.

Note that the local bound is not necessarily the optimal objective value
to corresponding LP relaxation.

\subsection{Find active subproblem with best local bound}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_best_node(glp_tree *tree);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ios_best_node| returns the reference number of
the active subproblem, whose local bound is best (i.e. smallest in case
of minimization or largest in case of maximization). However, if the
tree is empty, the routine returns zero.

\subsubsection*{Comments}

The best local bound is an lower (minimization) or upper (maximization)
bound for integer optimal solution to the original MIP problem.

\subsection{Compute relative MIP gap}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_ios_mip_gap(glp_tree *tree);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_mip_gap| computes the relative MIP gap (also
called {\it duality gap}) with the following formula:
$${\tt gap} = \frac{|{\tt best\_mip} - {\tt best\_bnd}|}
{|{\tt best\_mip}| + {\tt DBL\_EPSILON}}$$
where \verb|best_mip| is the best integer feasible solution found so
far, \verb|best_bnd| is the best (global) bound. If no integer feasible
solution has been found yet, \verb|gap| is set to \verb|DBL_MAX|.

\subsubsection*{Returns}

The routine \verb|glp_ios_mip_gap| returns the relative MIP gap.

\subsubsection*{Comments}

The relative MIP gap is used to measure the quality of the best integer
feasible solution found so far, because the optimal solution value
$z^*$ for the original MIP problem always lies in the range
$${\tt best\_bnd}\leq z^*\leq{\tt best\_mip}$$
in case of minimization, or in the range
$${\tt best\_mip}\leq z^*\leq{\tt best\_bnd}$$
in case of maximization.

To express the relative MIP gap in percents the value returned by the
routine \verb|glp_ios_mip_gap| should be multiplied by 100\%.

\subsection{Access subproblem application-specific data}

\subsubsection*{Synopsis}

\begin{verbatim}
void *glp_ios_node_data(glp_tree *tree, int p);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_node_data| allows the application accessing a
memory block allocated for the subproblem (which may be active or
inactive), whose reference number is $p$.

The size of the block is defined by the control parameter \verb|cb_size|
passed to the routine \verb|glp_intopt|. The block is initialized by
binary zeros on creating corresponding subproblem, and its contents is
kept until the subproblem will be removed from the tree.

The application may use these memory blocks to store specific data for
each subproblem.

\subsubsection*{Returns}

The routine \verb|glp_ios_node_data| returns a pointer to the memory
block for the specified subproblem. Note that if \verb|cb_size| = 0, the
routine returns a null pointer.

\subsection{Select subproblem to continue the search}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_ios_select_node(glp_tree *tree, int p);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_select_node| can be called from the
user-defined callback routine in response to the reason
\verb|GLP_ISELECT| to select an active subproblem, whose reference
number is $p$. The search will be continued from the subproblem
selected.

\subsection{Provide solution found by heuristic}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_heur_sol(glp_tree *tree, const double x[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_heur_sol| can be called from the user-defined
callback routine in response to the reason \verb|GLP_IHEUR| to provide
an integer feasible solution found by a primal heuristic.

Primal values of {\it all} variables (columns) found by the heuristic
should be placed in locations $x[1]$, \dots, $x[n]$, where $n$ is the
number of columns in the original problem object. Note that the routine
\verb|glp_ios_heur_sol| {\it does not} check primal feasibility of the
solution provided.

Using the solution passed in the array $x$ the routine computes value
of the objective function. If the objective value is better than the
best known integer feasible solution, the routine computes values of
auxiliary variables (rows) and stores all solution components in the
problem object.

\subsubsection*{Returns}

If the provided solution is accepted, the routine
\verb|glp_ios_heur_sol| returns zero. Otherwise, if the provided
solution is rejected, the routine returns non-zero.

\newpage

\subsection{Check if can branch upon specified variable}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_can_branch(glp_tree *tree, int j);
\end{verbatim}

\subsubsection*{Returns}

If $j$-th variable (column) can be used to branch upon, the routine
returns non-zero, otherwise zero.

\subsection{Choose variable to branch upon}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_ios_branch_upon(glp_tree *tree, int j, int sel);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_branch_upon| can be called from the
user-defined callback routine in response to the reason
\verb|GLP_IBRANCH| to choose a branching variable, whose ordinal number
is $j$. Should note that only variables, for which the routine
\verb|glp_ios_can_branch| returns non-zero, can be used to branch upon.

The parameter \verb|sel| is a flag that indicates which branch
(subproblem) should be selected next to continue the search:

\verb|'D'| --- down branch;

\verb|'U'| --- up branch;

\verb|'N'| --- none of them.

\subsubsection*{Comments}

On branching the solver removes the current active subproblem from the
active list and creates two new subproblems ({\it down-} and {\it
up-branches}), which are added to the end of the active list. Note that
the down-branch is created before the up-branch, so the last active
subproblem will be the up-branch.

The down- and up-branches are identical to the current subproblem with
exception that in the down-branch the upper bound of $x_j$, the variable
chosen to branch upon, is replaced by $\lfloor x_j^*\rfloor$, while in
the up-branch the lower bound of $x_j$ is replaced by
$\lceil x_j^*\rceil$, where $x_j^*$ is the value of $x_j$ in optimal
solution to LP relaxation of the current subproblem. For example, if
$x_j^*=3.14$, the new upper bound of $x_j$ in the down-branch will be
$\lfloor 3.14\rfloor=3$, and the new lower bound in the up-branch will
be $\lceil 3.14\rceil=4$.)

\pagebreak

Additionally the callback routine may select either down- or up-branch,
from which the solver will continue the search. If none of the branches
is selected, a general selection technique will be used.

\subsection{Terminate the solution process}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_ios_terminate(glp_tree *tree);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_terminate| sets a flag indicating that the
MIP solver should prematurely terminate the search.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\section{Library environment routines}

\subsection{64-bit integer data type}

Some GLPK API routines use 64-bit integer data type, which is declared
in the header \verb|glpk.h| as follows:

\begin{verbatim}
typedef struct { int lo, hi; } glp_long;
\end{verbatim}

\noindent
where \verb|lo| contains low 32 bits, and \verb|hi| contains high 32
bits of 64-bit integer value.\footnote{GLPK conforms to ILP32, LLP64,
and LP64 programming models, where the built-in type {\tt int}
corresponds to 32-bit integers.}

\subsection{Determine library version}

\subsubsection*{Synopsis}

\begin{verbatim}
const char *glp_version(void);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_version| returns a pointer to a null-terminated
character string, which specifies the version of the GLPK library in
the form \verb|"X.Y"|, where `\verb|X|' is the major version number, and
`\verb|Y|' is the minor version number, for example, \verb|"4.16"|.

\subsubsection*{Example}

\begin{verbatim}
printf("GLPK version is %s\n", glp_version());
\end{verbatim}

\subsection{Enable/disable terminal output}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_term_out(int flag);
\end{verbatim}

\subsubsection*{Description}

Depending on the parameter flag the routine \verb|glp_term_out| enables
or disables terminal output performed by glpk routines:

\verb|GLP_ON | --- enable terminal output;

\verb|GLP_OFF| --- disable terminal output.

\subsection{Install hook to intercept terminal output}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_term_hook(int (*func)(void *info, const char *s),
      void *info);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_term_hook| installs the user-defined hook routine
to intercept all terminal output performed by GLPK routines.

%This feature can be used to redirect the terminal output to other
%destination, for example, to a file or a text window.

The parameter {\it func} specifies the user-defined hook routine. It is
called from an internal printing routine, which passes to it two
parameters: {\it info} and {\it s}. The parameter {\it info} is a
transit pointer specified in corresponding call to the routine
\verb|glp_term_hook|; it may be used to pass some additional information
to the hook routine. The parameter {\it s} is a pointer to the null
terminated character string, which is intended to be written to the
terminal. If the hook routine returns zero, the printing routine writes
the string {\it s} to the terminal in a usual way; otherwise, if the
hook routine returns non-zero, no terminal output is performed.

To uninstall the hook routine both parameters {\it func} and {\it info}
should be specified as \verb|NULL|.

\subsubsection*{Example}

\begin{verbatim}
static int hook(void *info, const char *s)
{     FILE *foo = info;
      fputs(s, foo);
      return 1;
}

int main(void)
{     FILE *foo;
      . . .
      /* redirect terminal output */
      glp_term_hook(hook, foo);
      . . .
      /* resume terminal output */
      glp_term_hook(NULL, NULL);
      . . .
}
\end{verbatim}

\subsection{Get memory usage information}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_mem_usage(int *count, int *cpeak, glp_long *total,
      glp_long *tpeak);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_mem_usage| reports some information about
utilization of the memory by GLPK routines. Information is stored to
locations specified by corresponding parameters (see below). Any
parameter can be specified as \verb|NULL|, in which case corresponding
information is not stored.

\verb|*count| is the number of currently allocated memory blocks.

\verb|*cpeak| is the peak value of \verb|*count| reached since the
initialization of the GLPK library environment.

\verb|*total| is the total amount, in bytes, of currently allocated
memory blocks.

\verb|*tpeak| is the peak value of \verb|*total| reached since the
initialization of the GLPK library envirionment.

\subsubsection*{Example}

\begin{verbatim}
glp_mem_usage(&count, NULL, NULL, NULL);
printf("%d memory block(s) are still allocated\n", count);
\end{verbatim}

\subsection{Set memory usage limit}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_mem_limit(int limit);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_mem_limit| limits the amount of memory available
for dynamic allocation (in GLPK routines) to \verb|limit| megabytes.

\newpage

\subsection{Free GLPK library environment}

\subsubsection*{Synopsis}

\begin{verbatim}
 void glp_free_env(void);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_free_env| frees all resources used by GLPK
routines (memory blocks, etc.) which are currently still in use.

\subsubsection*{Usage notes}

Normally the application program does not need to call this routine,
because GLPK routines always free all unused resources. However, if
the application program even has deleted all problem objects, there
will be several memory blocks still allocated for the internal library
needs. For some reasons the application program may want GLPK to free
this memory, in which case it should call \verb|glp_free_env|.

Note that a call to \verb|glp_free_env| invalidates all problem objects
which still exist.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\appendix

\chapter{Installing GLPK on Your Computer}
\label{install}

\section{Obtaining GLPK distribution file}

The distrubution file for the most recent version of the GLPK package
can be downloaded from $<$\verb|ftp://ftp.gnu.org/gnu/glpk/|$>$ or from
some mirror GNU ftp sites; for details see
$<$\verb|http://www.gnu.org/order/ftp.html|$>$.

\section{Unpacking the distribution file}

The GLPK package (like all other GNU software) is distributed in the
form of packed archive. This is one file named \verb|glpk-x.y.tar.gz|,
where {\it x} is the major version number and {\it y} is the minor
version number.

In order to prepare the distribution for installation you should:

1. Copy the GLPK distribution file to some subdirectory.

2. Enter the command \verb|gzip -d glpk-x.y.tar.gz| in order to unpack
the distribution file. After unpacking the name of the distribution file
will be automatically changed to \verb|glpk-x.y.tar|.

3. Enter the command \verb|tar -x < glpk-x.y.tar| in order to unarchive
the distribution. After this operation the subdirectory \verb|glpk-x.y|,
which is the GLPK distribution, will be automatically created.

\section{Configuring the package}

After you have unpacked and unarchived GLPK distribution you should
configure the package, i.e. automatically tune it for your computer
(platform).

Normally, you should just \verb|cd| to the subdirectory
\verb|glpk-x.y| and enter the command \verb|./configure|. If you are
using \verb|csh| on an old version of System V, you might need to type
\verb|sh configure| instead to prevent \verb|csh| from trying execute
\verb|configure| itself.

The \verb|configure| shell script attempts to guess correct values for
various system-dependent variables used during compilation, and creates
\verb|Makefile|. It also creates a file \verb|config.status| that you
can run in the future to recreate the current configuration.

Running \verb|configure| takes about a few minutes. While it is running,
it displays some informational messages that tell you what it is doing.
If you don't want to see these messages, run \verb|configure| with its
standard output redirected to \verb|dev/null|; for example,
\verb|./configure >/dev/null|.

\section{Compiling and checking the package}

Normally, in order to compile the package you should just enter the
command \verb|make|. This command reads \verb|Makefile| generated by
\verb|configure| and automatically performs all necessary job.

The result of compilation is:

$\bullet$ the file \verb|libglpk.a|, which is a library archive that
contains object code for all GLPK routines; and

$\bullet$ the program \verb|glpsol|, which is a stand-alone LP/MIP
solver.

If you want, you can override the \verb|make| variables \verb|CFLAGS|
and \verb|LDFLAGS| like this:

\verb|make CFLAGS=-O2 LDFLAGS=-s|

To compile the package in a different directory from the one containing
the source code, you must use a version of \verb|make| that supports
\verb|VPATH| variable, such as GNU make. \verb|cd| to the directory
where you want the object files and executables to go and run the
\verb|configure| script. \verb|configure| automatically checks for the
source code in the directory that \verb|configure| is in and in
`\verb|..|'. If for some reason \verb|configure| is not in the source
code directory that you are configuring, then it will report that it
can't find the source code. In that case, run \verb|configure| with the
option \verb|--srcdir=DIR|, where \verb|DIR| is the directory that
contains the source code.

On systems that require unusual options for compilation or linking the
package's \verb|configure| script does not know about, you can give
\verb|configure| initial values for variables by setting them in the
environment. In Bourne-compatible shells you can do that on the command
line like this:

\verb|CC='gcc -traditional' LIBS=-lposix ./configure|

Here are the \verb|make| variables that you might want to override with
environment variables when running \verb|configure|.

For these variables, any value given in the environment overrides the
value that \verb|configure| would choose:

$\bullet$ variable \verb|CC|: C compiler program. The default is
\verb|cc|.

$\bullet$ variable \verb|INSTALL|: program to use to install files. The
default value is \verb|install| if you have it, otherwise \verb|cp|.

For these variables, any value given in the environment is added to the
value that \verb|configure| chooses:

$\bullet$ variable DEFS: configuration options, in the form
`\verb|-Dfoo -Dbar| \dots'.

$\bullet$ variable LIBS: libraries to link with, in the form
`\verb|-lfoo -lbar| \dots'.

In order to check the package (running some tests included in the
distribution) you can just enter the command \verb|make check|.

\section{Installing the package}

Normally, in order to install the GLPK package (i.e. copy GLPK library,
header files, and the solver to the system places) you should just enter
the command \verb|make install| (note that you should be the root user
or a superuser).

By default, \verb|make install| will install the package's files in
the subdirectories \verb|usr/local/bin|, \verb|usr/local/lib|, etc. You
can specify an installation prefix other than \verb|/usr/local| by
giving \verb|configure| the option \verb|--prefix=PATH|. Alternately,
you can do so by consistently giving a value for the \verb|prefix|
variable when you run \verb|make|, e.g.

\verb|make prefix=/usr/gnu|

\verb|make prefix=/usr/gnu install|

After installing you can remove the program binaries and object files
from the source directory by typing \verb|make clean|. To remove all
files that \verb|configure| created (\verb|Makefile|,
\verb|config.status|, etc.), just type the command
\verb|make distclean|.

The file \verb|configure.in| is used to create \verb|configure| by a
program called \verb|autoconf|. You only need it if you want to remake
\verb|configure| using a newer version of \verb|autoconf|.

\section{Uninstalling the package}

In order to uninstall the GLPK package (i.e. delete all GLPK files from
the system places) you can enter the command \verb|make uninstall|.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{MPS Format}
\label{champs}

\section{Fixed MPS Format}
\label{secmps}

The MPS format\footnote{The MPS format was developed in 1960's by IBM
as input format for their mathematical programming system MPS/360.
Today the MPS format is a most widely used format understood by most
mathematical programming packages. This appendix describes only the
features of the MPS format, which are implemented in the GLPK package.}
is intended for coding LP/MIP problem data. This format assumes the
formulation of LP/MIP problem (1.1)---(1.3) (see Section \ref{seclp},
page \pageref{seclp}).

{\it MPS file} is a text file, which contains two types of
cards\footnote{In 1960's MPS file was a deck of 80-column punched cards,
so the author decided to keep the word ``card'', which may be understood
as ``line of text file''.}: indicator cards and data cards.

Indicator cards determine a kind of succeeding data. Each indicator card
has one word in uppercase letters beginning in column 1.

Data cards contain problem data. Each data card is divided into six
fixed fields:

\begin{center}
\begin{tabular}{lcccccc}
& Field 1 & Field 2 & Field 3 & Field 4 & Field 5 & Feld 6 \\
\hline
Columns & 2---3 & 5---12 & 15---22 & 25---36 & 40---47 & 50---61 \\
Contents & Code & Name & Name & Number & Name & Number \\
\end{tabular}
\end{center}

On a particular data card some fields may be optional.

Names are used to identify rows, columns, and some vectors (see below).

Aligning the indicator code in the field 1 to the left margin is
optional.

All names specified in the fields 2, 3, and 5 should contain from 1 up
to 8 arbitrary characters (except control characters). If a name is
placed in the field 3 or 5, its first character should not be the dollar
sign `\verb|$|'. If a name contains spaces, the spaces are ignored.

All numerical values in the fields 4 and 6 should be coded in the form
$sxx$\verb|E|$syy$, where $s$ is the plus `\verb|+|' or the minus
`\verb|-|' sign, $xx$ is a real number with optional decimal point,
$yy$ is an integer decimal exponent. Any number should contain up to 12
characters. If the sign $s$ is omitted, the plus sign is assumed. The
exponent part is optional. If a number contains spaces, the spaces are
ignored.

If a card has the asterisk `\verb|*|' in the column 1, this card is
considered as a comment and ignored. Besides, if the first character in
the field 3 or 5 is the dollar sign `\verb|$|', all characters from the
dollar sign to the end of card are considered as a comment and ignored.

MPS file should contain cards in the following order:

$\bullet$ NAME indicator card;

$\bullet$ ROWS indicator card;

$\bullet$ data cards specifying rows (constraints);

$\bullet$ COLUMNS indicator card;

$\bullet$ data cards specifying columns (structural variables) and
constraint coefficients;

$\bullet$ RHS indicator card;

$\bullet$ data cards specifying right-hand sides of constraints;

$\bullet$ RANGES indicator card;

$\bullet$ data cards specifying ranges for double-bounded constraints;

$\bullet$ BOUNDS indicator card;

$\bullet$ data cards specifying types and bounds of structural
variables;

$\bullet$ ENDATA indicator card.

{\it Section} is a group of cards consisting of an indicator card and
data cards succeeding this indicator card. For example, the ROWS section
consists of the ROWS indicator card and data cards specifying rows.

The sections RHS, RANGES, and BOUNDS are optional and may be omitted.

\section{Free MPS Format}

{\it Free MPS format} is an improved version of the standard (fixed)
MPS format described above.\footnote{This format was developed in the
beginning of 1990's by IBM as an alternative to the standard fixed MPS
format for Optimization Subroutine Library (OSL).} Note that all
changes in free MPS format concern only the coding of data while the
structure of data is the same for both fixed and free versions of the
MPS format.

In free MPS format indicator and data records\footnote{{\it Record} in
free MPS format has the same meaning as {\it card} in fixed MPS format.}
may have arbitrary length not limited to 80 characters. Fields of data
records have no predefined positions, i.e. the fields may begin in any
position, except position 1, which must be blank, and must be separated
from each other by one or more blanks. However, the fields must appear
in the same order as in fixed MPS format.

Symbolic names in fields 2, 3, and 5 may be longer than 8
characters\footnote{GLPK allows symbolic names having up to 255
characters.}
and must not contain embedded blanks.

Numeric values in fields 4 and 6 are limited to 12 characters and must
not contain embedded blanks.

Only six fields on each data record are used. Any other fields are
ignored.

If the first character of any field (not necessarily fields 3 and 5)
is the dollar sign (\$), all characters from the dollar sign to the end
of record are considered as a comment and ignored.

\section{NAME indicator card}

The NAME indicator card should be the first card in the MPS file (except
optional comment cards, which may precede the NAME card). This card
should contain the word \verb|NAME| in the columns 1---4 and the problem
name in the field 3. The problem name is optional and may be omitted.

\section{ROWS section}
\label{secrows}

The ROWS section should start with the indicator card, which contains
the word \verb|ROWS| in the columns 1---4.

Each data card in the ROWS section specifies one row (constraint) of the
problem. All these data cards have the following format.

`\verb|N|' in the field 1 means that the row is free (unbounded):
$$-\infty < x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
< +\infty;$$

`\verb|L|' in the field 1 means that the row is of ``less than or equal
to'' type:
$$-\infty < x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
\leq b_i;$$

`\verb|G|' in the field 1 means that the row is of ``greater than or
equal to'' type:
$$b_i \leq x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
< +\infty;$$

`\verb|E|' in the field 1 means that the row is of ``equal to'' type:
$$x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n} \leq
b_i,$$
where $b_i$ is a right-hand side. Note that each constraint has a
corresponding implictly defined auxiliary variable ($x_i$ above), whose
value is a value of the corresponding linear form, therefore row bounds
can be considered as bounds of such auxiliary variable.

The filed 2 specifies a row name (which is considered as the name of
the corresponding auxiliary variable).

The fields 3, 4, 5, and 6 are not used and should be empty.

Numerical values of all non-zero right-hand sides $b_i$ should be
specified in the RHS section (see below). All double-bounded (ranged)
constraints should be specified in the RANGES section (see below).

\section{COLUMNS section}

The COLUMNS section should start with the indicator card, which contains
the word \verb|COLUMNS| in the columns 1---7.

Each data card in the COLUMNS section specifies one or two constraint
coefficients $a_{ij}$ and also introduces names of columns, i.e. names
of structural variables. All these data cards have the following format.

The field 1 is not used and should be empty.

The field 2 specifies a column name. If this field is empty, the column
name from the immediately preceeding data card is assumed.

The field 3 specifies a row name defined in the ROWS section.

The field 4 specifies a numerical value of the constraint coefficient
$a_{ij}$, which is placed in the corresponding row and column.

The fields 5 and 6 are optional. If they are used, they should contain
a second pair ``row name---constraint coefficient'' for the same column.

Elements of the constraint matrix (i.e. constraint coefficients) should
be enumerated in the column wise manner: all elements for the current
column should be specified before elements for the next column. However,
the order of rows in the COLUMNS section may differ from the order of
rows in the ROWS section.

Constraint coefficients not specified in the COLUMNS section are
considered as zeros. Therefore zero coefficients may be omitted,
although it is allowed to explicitly specify them.

\section{RHS section}

The RHS section should start with the indicator card, which contains the
word \verb|RHS| in the columns 1---3.

Each data card in the RHS section specifies one or two right-hand sides
$b_i$ (see Section \ref{secrows}, page \pageref{secrows}). All these
data cards have the following format.

The field 1 is not used and should be empty.

The field 2 specifies a name of the right-hand side (RHS)
vector\footnote{This feature allows the user to specify several RHS
vectors in the same MPS file. However, before solving the problem a
particular RHS vector should be chosen.}. If this field is empty, the
RHS vector name from the immediately preceeding data card is assumed.

The field 3 specifies a row name defined in the ROWS section.

The field 4 specifies a right-hand side $b_i$ for the row, whose name is
specified in the field 3. Depending on the row type $b_i$ is a lower
bound (for the row of \verb|G| type), an upper bound (for the row of
\verb|L| type), or a fixed value (for the row of \verb|E|
type).\footnote{If the row is of {\tt N} type, $b_i$ is considered as
a constant term of the corresponding linear form. Should note, however,
this convention is non-standard.}

The fields 5 and 6 are optional. If they are used, they should contain
a second pair ``row name---right-hand side'' for the same RHS vector.

All right-hand sides for the current RHS vector should be specified
before right-hand sides for the next RHS vector. However, the order of
rows in the RHS section may differ from the order of rows in the ROWS
section.

Right-hand sides not specified in the RHS section are considered as
zeros. Therefore zero right-hand sides may be omitted, although it is
allowed to explicitly specify them.

\section{RANGES section}

The RANGES section should start with the indicator card, which contains
the word \verb|RANGES| in the columns 1---6.

Each data card in the RANGES section specifies one or two ranges for
double-side constraints, i.e. for constraints that are of the types
\verb|L| and \verb|G| at the same time:
$$l_i \leq x_i = a_{i1}x_{m+1} + a_{i2}x_{m+2} + \dots + a_{in}x_{m+n}
\leq u_i,$$
where $l_i$ is a lower bound, $u_i$ is an upper bound. All these data
cards have the following format.

The field 1 is not used and should be empty.

The field 2 specifies a name of the range vector\footnote{This feature
allows the user to specify several range vectors in the same MPS file.
However, before solving the problem a particular range vector should be
chosen.}. If this field is empty, the range vector name from the
immediately preceeding data card is assumed.

The field 3 specifies a row name defined in the ROWS section.

The field 4 specifies a range value $r_i$ (see the table below) for the
row, whose name is specified in the field 3.

The fields 5 and 6 are optional. If they are used, they should contain
a second pair ``row name---range value'' for the same range vector.

All range values for the current range vector should be specified before
range values for the next range vector. However, the order of rows in
the RANGES section may differ from the order of rows in the ROWS
section.

For each double-side constraint specified in the RANGES section its
lower and upper bounds are determined as follows:

\begin{center}
\begin{tabular}{cccc}
Row type & Sign of $r_i$ & Lower bound & Upper bound \\
\hline
{\tt G} & $+$ or $-$ & $b_i$ & $b_i + |r_i|$ \\
{\tt L} & $+$ or $-$ & $b_i - |r_i|$ & $b_i$ \\
{\tt E} & $+$ & $b_i$ & $b_i + |r_i|$ \\
{\tt E} & $-$ & $b_i - |r_i|$ & $b_i$ \\
\end{tabular}
\end{center}

\noindent
where $b_i$ is a right-hand side specified in the RHS section (if $b_i$
is not specified, it is considered as zero), $r_i$ is a range value
specified in the RANGES section.

\section{BOUNDS section}
\label{secbounds}

The BOUNDS section should start with the indicator card, which contains
the word \verb|BOUNDS| in the columns 1---6.

Each data card in the BOUNDS section specifies one (lower or upper)
bound for one structural variable (column). All these data cards have
the following format.

The indicator in the field 1 specifies the bound type:

\begin{tabular}{@{}ll}
\verb|LO| & lower bound; \\
\verb|UP| & upper bound; \\
\verb|FX| & fixed variable (lower and upper bounds are equal); \\
\verb|FR| & free variable (no bounds); \\
\verb|MI| & no lower bound (lower bound is ``minus infinity''); \\
\verb|PL| & no upper bound (upper bound is ``plus infinity''); \\
\end{tabular}

The field 2 specifies a name of the bound vector\footnote{This feature
allows the user to specify several bound vectors in the same MPS file.
However, before solving the problem a particular bound vector should be
chosen.}. If this field is empty, the bound vector name from the
immediately preceeding data card is assumed.

The field 3 specifies a column name defined in the COLUMNS section.

The field 4 specifies a bound value. If the bound type in the field 1
differs from \verb|LO|, \verb|UP|, and \verb|FX|, the value in the field
4 is ignored and may be omitted.

The fields 5 and 6 are not used and should be empty.

All bound values for the current bound vector should be specified before
bound values for the next bound vector. However, the order of columns in
the BOUNDS section may differ from the order of columns in the COLUMNS
section. Specification of a lower bound should precede specification of
an upper bound for the same column (if both the lower and upper bounds
are explicitly specified).

By default, all columns (structural variables) are non-negative, i.e.
have zero lower bound and no upper bound. Lower ($l_j$) and upper
($u_j$) bounds of some column (structural variable $x_j$) are set in the
following way, where $s_j$ is a corresponding bound value explicitly
specified in the BOUNDS section:

\begin{tabular}{@{}ll}
\verb|LO| & sets $l_j$ to $s_j$; \\
\verb|UP| & sets $u_j$ to $s_j$; \\
\verb|FX| & sets both $l_j$ and $u_j$ to $s_j$; \\
\verb|FR| & sets $l_j$ to $-\infty$ and $u_j$ to $+\infty$; \\
\verb|MI| & sets $l_j$ to $-\infty$; \\
\verb|PL| & sets $u_j$ to $+\infty$. \\
\end{tabular}

\section{ENDATA indicator card}

The ENDATA indicator card should be the last card of MPS file (except
optional comment cards, which may follow the ENDATA card). This card
should contain the word \verb|ENDATA| in the columns 1---6.

\section{Specifying objective function}

It is impossible to explicitly specify the objective function and
optimization direction in the MPS file. However, the following implicit
rule is used by default: the first row of \verb|N| type is considered
as a row of the objective function (i.e. the objective function is the
corresponding auxiliary variable), which should be {\it minimized}.

GLPK also allows specifying a constant term of the objective function
as a right-hand side of the corresponding row in the RHS section.

\section{Example of MPS file}
\label{secmpsex}

In order to illustrate what the MPS format is, consider the following
example of LP problem:

\medskip
\noindent minimize
$$
value = .03\ bin_1 + .08\ bin_2 + .17\ bin_3 + .12\ bin_4 + .15\ bin_5
+ .21\ al + .38\ si
$$

\noindent subject to linear constraints
$$
\begin{array}{@{}l@{\:}l@{}}
yield &= \ \ \ \ \;bin_1 + \ \ \ \ \;bin_2 + \ \ \ \ \;bin_3 +
         \ \ \ \ \;bin_4 + \ \ \ \ \;bin_5 + \ \ \ \ \;al +
         \ \ \ \ \;si \\
FE    &= .15\ bin_1 + .04\ bin_2 + .02\ bin_3 + .04\ bin_4 + .02\ bin_5
         + .01\ al + .03\ si \\
CU    &= .03\ bin_1 + .05\ bin_2 + .08\ bin_3 + .02\ bin_4 + .06\ bin_5
         + .01\ al \\
MN    &= .02\ bin_1 + .04\ bin_2 + .01\ bin_3 + .02\ bin_4 + .02\ bin_5
         \\
MG    &= .02\ bin_1 + .03\ bin_2
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + .01\ bin_5 \\
AL    &= .70\ bin_1 + .75\ bin_2 + .80\ bin_3 + .75\ bin_4 + .80\ bin_5
         + .97\ al \\
SI    &= .02\ bin_1 + .06\ bin_2 + .08\ bin_3 + .12\ bin_4 + .02\ bin_5
         + .01\ al + .97\ si \\
\end{array}
$$
and bounds of (auxiliary and structural) variables
$$
\begin{array}{r@{\ }l@{\ }l@{\ }l@{\ }rcr@{\ }l@{\ }l@{\ }l@{\ }r}
&&yield&=&2000&&0&\leq&bin_1&\leq&200\\
-\infty&<&FE&\leq&60&&0&\leq&bin_2&\leq&2500\\
-\infty&<&CU&\leq&100&&400&\leq&bin_3&\leq&800\\
-\infty&<&MN&\leq&40&&100&\leq&bin_4&\leq&700\\
-\infty&<&MG&\leq&30&&0&\leq&bin_5&\leq&1500\\
1500&\leq&AL&<&+\infty&&0&\leq&al&<&+\infty\\
250&\leq&SI&\leq&300&&0&\leq&si&<&+\infty\\
\end{array}
$$

A complete MPS file which specifies data for this example is shown
below (the first two comment lines show card positions).

\begin{verbatim}
*000000001111111111222222222233333333334444444444555555555566
*234567890123456789012345678901234567890123456789012345678901
NAME          PLAN
ROWS
 N  VALUE
 E  YIELD
 L  FE
 L  CU
 L  MN
 L  MG
 G  AL
 L  SI
COLUMNS
    BIN1      VALUE           .03000   YIELD          1.00000
              FE              .15000   CU              .03000
              MN              .02000   MG              .02000
              AL              .70000   SI              .02000
    BIN2      VALUE           .08000   YIELD          1.00000
              FE              .04000   CU              .05000
              MN              .04000   MG              .03000
              AL              .75000   SI              .06000
    BIN3      VALUE           .17000   YIELD          1.00000
              FE              .02000   CU              .08000
              MN              .01000   AL              .80000
              SI              .08000
    BIN4      VALUE           .12000   YIELD          1.00000
              FE              .04000   CU              .02000
              MN              .02000   AL              .75000
              SI              .12000
    BIN5      VALUE           .15000   YIELD          1.00000
              FE              .02000   CU              .06000
              MN              .02000   MG              .01000
              AL              .80000   SI              .02000
    ALUM      VALUE           .21000   YIELD          1.00000
              FE              .01000   CU              .01000
              AL              .97000   SI              .01000
    SILICON   VALUE           .38000   YIELD          1.00000
              FE              .03000   SI              .97000
RHS
    RHS1      YIELD       2000.00000   FE            60.00000
              CU           100.00000   MN            40.00000
              SI           300.00000
              MG            30.00000   AL          1500.00000
RANGES
    RNG1      SI            50.00000
BOUNDS
 UP BND1      BIN1         200.00000
 UP           BIN2        2500.00000
 LO           BIN3         400.00000
 UP           BIN3         800.00000
 LO           BIN4         100.00000
 UP           BIN4         700.00000
 UP           BIN5        1500.00000
ENDATA
\end{verbatim}

\section{MIP features}

The MPS format provides two ways for introducing integer variables into
the problem.

The first way is most general and based on using special marker cards
INTORG and INTEND. These marker cards are placed in the COLUMNS section.
The INTORG card indicates the start of a group of integer variables
(columns), and the card INTEND indicates the end of the group. The MPS
file may contain arbitrary number of the marker cards.

The marker cards have the same format as the data cards (see Section
\ref{secmps}, page \pageref{secmps}).

The fields 1, 2, and 6 are not used and should be empty.

The field 2 should contain a marker name. This name may be arbitrary.

The field 3 should contain the word \verb|'MARKER'| (including
apostrophes).

The field 5 should contain either the word \verb|'INTORG'| (including
apostrophes) for the marker card, which begins a group of integer
columns, or the word \verb|'INTEND'| (including apostrophes) for the
marker card, which ends the group.

The second way is less general but more convenient in some cases. It
allows the user declaring integer columns using three additional types
of bounds, which are specified in the field 1 of data cards in the
BOUNDS section (see Section \ref{secbounds}, page \pageref{secbounds}):

\begin{tabular}{@{}lp{112.3mm}@{}}
\verb|LI| & lower integer. This bound type specifies that the
corresponding column (structural variable), whose name is specified in
field 3, is of integer kind. In this case an lower bound of the
column should be specified in field 4 (like in the case of \verb|LO|
bound type). \\
\verb|UI| & upper integer. This bound type specifies that the
corresponding column (structural variable), whose name is specified in
field 3, is of integer kind. In this case an upper bound of the
column should be specified in field 4 (like in the case of \verb|UP|
bound type). \\
\end{tabular}

\pagebreak

\begin{tabular}{@{}lp{112.3mm}@{}}
\verb|BV| & binary variable. This bound type specifies that the
corresponding column (structural variable), whose name is specified in
the field 3, is of integer kind, its lower bound is zero, and its upper
bound is one (thus, such variable being of integer kind can have only
two values zero and one). In this case a numeric value specified in the
field 4 is ignored and may be omitted.\\
\end{tabular}

Consider the following example of MIP problem:

\medskip

\noindent
\hspace{1in} minimize
$$Z = 3 x_1 + 7 x_2 - x_3 + x4$$
\hspace{1in} subject to linear constraints
$$
\begin{array}{c}
\nonumber r_1 = 2   x_1 - \ \ x_2 + \ \ x_3 - \ \;x_4 \\
\nonumber r_2 = \ \;x_1 - \ \;x_2 - 6   x_3 + 4   x_4 \\
\nonumber r_3 = 5   x_1 +   3 x_2 \ \ \ \ \ \ \ \ \ + \ \ x_4 \\
\end{array}
$$
\hspace{1in} and bound of variables
$$
\begin{array}{cccl}
\nonumber 1 \leq r_1 < +\infty && 0 \leq x_1 \leq 4 &{\rm(continuous)}\\
\nonumber 8 \leq r_2 < +\infty && 2 \leq x_2 \leq 5 &{\rm(integer)}   \\
\nonumber 5 \leq r_3 < +\infty && 0 \leq x_3 \leq 1 &{\rm(integer)}   \\
\nonumber                      && 3 \leq x_4 \leq 8 &{\rm(continuous)}\\
\end{array}
$$

The corresponding MPS file may look like the following:

\begin{verbatim}
NAME          SAMP1
ROWS
 N  Z
 G  R1
 G  R2
 G  R3
COLUMNS
    X1        R1                2.0    R2                 1.0
    X1        R3                5.0    Z                  3.0
    MARK0001  'MARKER'                 'INTORG'
    X2        R1               -1.0    R2                -1.0
    X2        R3                3.0    Z                  7.0
    X3        R1                1.0    R2                -6.0
    X3        Z                -1.0
    MARK0002  'MARKER'                 'INTEND'
    X4        R1               -1.0    R2                 4.0
    X4        R3                1.0    Z                  1.0
RHS
    RHS1      R1                1.0
    RHS1      R2                8.0
    RHS1      R3                5.0
BOUNDS
 UP BND1      X1                4.0
 LO BND1      X2                2.0
 UP BND1      X2                5.0
 UP BND1      X3                1.0
 LO BND1      X4                3.0
 UP BND1      X4                8.0
ENDATA
\end{verbatim}

The same example may be coded without INTORG/INTEND markers using the
bound type UI for the variable $x_2$ and the bound type BV for the
variable $x_3$:

\begin{verbatim}
NAME          SAMP2
ROWS
 N  Z
 G  R1
 G  R2
 G  R3
COLUMNS
    X1        R1                2.0    R2                 1.0
    X1        R3                5.0    Z                  3.0
    X2        R1               -1.0    R2                -1.0
    X2        R3                3.0    Z                  7.0
    X3        R1                1.0    R2                -6.0
    X3        Z                -1.0
    X4        R1               -1.0    R2                 4.0
    X4        R3                1.0    Z                  1.0
RHS
    RHS1      R1                1.0
    RHS1      R2                8.0
    RHS1      R3                5.0
BOUNDS
 UP BND1      X1                4.0
 LO BND1      X2                2.0
 UI BND1      X2                5.0
 BV BND1      X3
 LO BND1      X4                3.0
 UP BND1      X4                8.0
ENDATA
\end{verbatim}

\section{Specifying predefined basis}
\label{secbas}

The MPS format can also be used to specify some predefined basis for an
LP problem, i.e. to specify which rows and columns are basic and which
are non-basic.

The order of a basis file in the MPS format is:

$\bullet$ NAME indicator card;

$\bullet$ data cards (can appear in arbitrary order);

$\bullet$ ENDATA indicator card.

Each data card specifies either a pair "basic column---non-basic row"
or a non-basic column. All the data cards have the following format.

`\verb|XL|' in the field 1 means that a column, whose name is given in
the field 2, is basic, and a row, whose name is given in the field 3,
is non-basic and placed on its lower bound.

`\verb|XU|' in the field 1 means that a column, whose name is given in
the field 2, is basic, and a row, whose name is given in the field 3,
is non-basic and placed on its upper bound.

`\verb|LL|' in the field 1 means that a column, whose name is given in
the field 3, is non-basic and placed on its lower bound.

`\verb|UL|' in the field 1 means that a column, whose name is given in
the field 3, is non-basic and placed on its upper bound.

The field 2 contains a column name.

If the indicator given in the field 1 is `\verb|XL|' or `\verb|XU|',
the field 3 contains a row name. Otherwise, if the indicator is
`\verb|LL|' or `\verb|UL|', the field 3 is not used and should be empty.

The field 4, 5, and 6 are not used and should be empty.

A basis file in the MPS format acts like a patch: it doesn't specify
a basis completely, instead that it is just shows in what a given basis
differs from the "standard" basis, where all rows (auxiliary variables)
are assumed to be basic and all columns (structural variables) are
assumed to be non-basic.

As an example here is a basis file that specifies an optimal basis
for the example LP problem given in Section \ref{secmpsex},
Page \pageref{secmpsex}:

\pagebreak

\begin{verbatim}
*000000001111111111222222222233333333334444444444555555555566
*234567890123456789012345678901234567890123456789012345678901
NAME          PLAN
 XL BIN2      YIELD
 XL BIN3      FE
 XL BIN4      MN
 XL ALUM      AL
 XL SILICON   SI
 LL BIN1
 LL BIN5
ENDATA
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{CPLEX LP Format}
\label{chacplex}

\section{Prelude}

The CPLEX LP format\footnote{The CPLEX LP format was developed in
the end of 1980's by CPLEX Optimization, Inc. as an input format for
the CPLEX linear programming system. Although the CPLEX LP format is
not as widely used as the MPS format, being row-oriented it is more
convenient for coding mathematical programming models by human. This
appendix describes only the features of the CPLEX LP format which are
implemented in the GLPK package.} is intended for coding LP/MIP problem
data. It is a row-oriented format that assumes the formulation of LP/MIP
problem (1.1)---(1.3) (see Section \ref{seclp}, page \pageref{seclp}).

CPLEX LP file is a plain text file written in CPLEX LP format. Each text
line of this file may contain up to 255 characters\footnote{GLPK allows
text lines of arbitrary length.}. Blank lines are ignored. If a line
contains the backslash character ($\backslash$), this character and
everything that follows it until the end of line are considered as a
comment and also ignored.

An LP file is coded by the user using the following elements:

$\bullet$ keywords;

$\bullet$ symbolic names;

$\bullet$ numeric constants;

$\bullet$ delimiters;

$\bullet$ blanks.

\newpage

{\it Keywords} which may be used in the LP file are the following:

\begin{verbatim}
      minimize        minimum        min
      maximize        maximum        max
      subject to      such that      s.t.      st.      st
      bounds          bound
      general         generals       gen
      integer         integers       int
      binary          binaries       bin
      infinity        inf
      free
      end
\end{verbatim}

\noindent
All the keywords are case insensitive. Keywords given above on the same
line are equivalent. Any keyword (except \verb|infinity|, \verb|inf|,
and \verb|free|) being used in the LP file must start at the beginning
of a text line.

{\it Symbolic names} are used to identify the objective function,
constraints (rows), and variables (columns). All symbolic names are case
sensitive and may contain up to 16 alphanumeric characters\footnote{GLPK
allows symbolic names having up to 255 characters.} (\verb|a|, \dots,
\verb|z|, \verb|A|, \dots, \verb|Z|, \verb|0|, \dots, \verb|9|) as well
as the following characters:

\begin{verbatim}
!  "  #  $  %  &  (  )  /  ,  .  ;  ?  @  _  `  '  {  }  |  ~
\end{verbatim}

\noindent
with exception that no symbolic name can begin with a digit or a period.

{\it Numeric constants} are used to denote constraint and objective
coefficients, right-hand sides of constraints, and bounds of variables.
They are coded in the standard form $xx$\verb|E|$syy$, where $xx$ is
a real number with optional decimal point, $s$ is a sign (\verb|+| or
\verb|-|), $yy$ is an integer decimal exponent. Numeric constants may
contain arbitrary number of characters. The exponent part is optional.
The letter `\verb|E|' can be coded as `\verb|e|'. If the sign $s$ is
omitted, plus is assumed.

{\it Delimiters} that may be used in the LP file are the following:

\begin{verbatim}
      :
      +
      -
      <   <=   =<
      >   >=   =>
      =
\end{verbatim}

\noindent
Delimiters given above on the same line are equivalent. The meaning of
the delimiters will be explained below.

{\it Blanks} are non-significant characters. They may be used freely to
improve readability of the LP file. Besides, blanks should be used to
separate elements from each other if there is no other way to do that
(for example, to separate a keyword from a following symbolic name).

The order of an LP file is:

$\bullet$ objective function definition;

$\bullet$ constraints section;

$\bullet$ bounds section;

$\bullet$ general, integer, and binary sections (can appear in arbitrary
order);

$\bullet$ end keyword.

These components are discussed in following sections.

\section{Objective function definition}

The objective function definition must appear first in the LP file. It
defines the objective function and specifies the optimization direction.

The objective function definition has the following form:
$$
\left\{
\begin{array}{@{}c@{}}
{\tt minimize} \\ {\tt maximize}
\end{array}
\right\}\ f\ {\tt :}\ s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x
$$
where $f$ is a symbolic name of the objective function, $s$ is a sign
\verb|+| or \verb|-|, $c$ is a numeric constant that denotes an
objective coefficient, $x$ is a symbolic name of a variable.

If necessary, the objective function definition can be continued on as
many text lines as desired.

The name of the objective function is optional and may be omitted
(together with the semicolon that follows it). In this case the default
name `\verb|obj|' is assigned to the objective function.

If the very first sign $s$ is omitted, the sign plus is assumed. Other
signs cannot be omitted.

If some objective coefficient $c$ is omitted, 1 is assumed.

Symbolic names $x$ used to denote variables are recognized by context
and therefore needn't to be declared somewhere else.

Here is an example of the objective function definition:

\begin{verbatim}
   Minimize Z : - x1 + 2 x2 - 3.5 x3 + 4.997e3x(4) + x5 + x6 +
      x7 - .01x8
\end{verbatim}

\section{Constraints section}

The constraints section must follow the objective function definition.
It defines a system of equality and/or inequality constraints.

The constraint section has the following form:

\begin{center}
\begin{tabular}{l}
\verb|subject to| \\
{\it constraint}$_1$ \\
{\it constraint}$_2$ \\
\hspace{20pt}\dots \\
{\it constraint}$_m$ \\
\end{tabular}
\end{center}

\noindent where {\it constraint}$_i, i=1,\dots,m,$ is a particular
constraint definition.

Each constraint definition can be continued on as many text lines as
desired. However, each constraint definition must begin on a new line
except the very first constraint definition which can begin on the same
line as the keyword `\verb|subject to|'.

Constraint definitions have the following form:
$$
r\ {\tt:}\ s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x
\ \left\{
\begin{array}{@{}c@{}}
\mbox{\tt<=} \\ \mbox{\tt>=} \\ \mbox{\tt=}
\end{array}
\right\}\ b
$$
where $r$ is a symbolic name of a constraint, $s$ is a sign \verb|+| or
\verb|-|, $c$ is a numeric constant that denotes a constraint
coefficient, $x$ is a symbolic name of a variable, $b$ is a right-hand
side.

The name $r$ of a constraint (which is the name of the corresponding
auxiliary variable) is optional and may be omitted (together with the
semicolon that follows it). In this case the default names like
`\verb|r.nnn|' are assigned to unnamed constraints.

The linear form $s\ c\ x\ s\ c\ x\ \dots\ s\ c\ x$ in the left-hand
side of a constraint definition has exactly the same meaning as in the
case of the objective function definition (see above).

After the linear form one of the following delimiters that indicate
the constraint sense must be specified:

\verb|<=| \ means `less than or equal to'

\verb|>=| \ means `greater than or equal to'

\verb|= | \ means `equal to'

The right hand side $b$ is a numeric constant with an optional sign.

Here is an example of the constraints section:

\begin{verbatim}
   Subject To
      one: y1 + 3 a1 - a2 - b >= 1.5
      y2 + 2 a3 + 2
         a4 - b >= -1.5
      two : y4 + 3 a1 + 4 a5 - b <= +1
      .20y5 + 5 a2 - b = 0
      1.7 y6 - a6 + 5 a777 - b >= 1
\end{verbatim}

(Should note that it is impossible to express ranged constraints in the
CPLEX LP format. Each a ranged constraint can be coded as two
constraints with identical linear forms in the left-hand side, one of
which specifies a lower bound and other does an upper one of the
original ranged constraint.)

\section{Bounds section}

The bounds section is intended to define bounds of variables. This
section is optional; if it is specified, it must follow the constraints
section. If the bound section is omitted, all variables are assumed to
be non-negative (i.e. that they have zero lower bound and no upper
bound).

The bounds section has the following form:

\begin{center}
\begin{tabular}{l}
\verb|bounds| \\
{\it definition}$_1$ \\
{\it definition}$_2$ \\
\hspace{20pt}\dots \\
{\it definition}$_p$ \\
\end{tabular}
\end{center}

\noindent
where {\it definition}$_k, k=1,\dots,p,$ is a particular bound
definition.

Each bound definition must begin on a new line\footnote{The GLPK
implementation allows several bound definitions to be placed on the same
line.} except the very first bound definition which can begin on the
same line as the keyword `\verb|bounds|'.

Syntactically constraint definitions can have one of the following six
forms:

\begin{center}
\begin{tabular}{ll}
$x$ \verb|>=| $l$ &              specifies a lower bound \\
$l$ \verb|<=| $x$ &              specifies a lower bound \\
$x$ \verb|<=| $u$ &              specifies an upper bound \\
$l$ \verb|<=| $x$ \verb|<=| $u$ &specifies both lower and upper bounds\\
$x$ \verb|=| $t$                &specifies a fixed value \\
$x$ \verb|free|                 &specifies free variable
\end{tabular}
\end{center}

\noindent
where $x$ is a symbolic name of a variable, $l$ is a numeric constant
with an optional sign that defines a lower bound of the variable or
\verb|-inf| that means that the variable has no lower bound, $u$ is a
numeric constant with an optional sign that defines an upper bound of
the variable or \verb|+inf| that means that the variable has no upper
bound, $t$ is a numeric constant with an optional sign that defines a
fixed value of the variable.

By default all variables are non-negative, i.e. have zero lower bound
and no upper bound. Therefore definitions of these default bounds can be
omitted in the bounds section.

Here is an example of the bounds section:

\begin{verbatim}
   Bounds
      -inf <= a1 <= 100
      -100 <= a2
      b <= 100
      x2 = +123.456
      x3 free
\end{verbatim}

\section{General, integer, and binary sections}

The general, integer, and binary sections are intended to define
some variables as integer or binary. All these sections are optional
and needed only in case of MIP problems. If they are specified, they
must follow the bounds section or, if the latter is omitted, the
constraints section.

All the general, integer, and binary sections have the same form as
follows:

\begin{center}
\begin{tabular}{l}
$
\left\{
\begin{array}{@{}l@{}}
\verb|general| \\
\verb|integer| \\
\verb|binary | \\
\end{array}
\right\}
$ \\
\hspace{10pt}$x_1$ \\
\hspace{10pt}$x_2$ \\
\hspace{10pt}\dots \\
\hspace{10pt}$x_q$ \\
\end{tabular}
\end{center}

\noindent
where $x_k$ is a symbolic name of variable, $k=1,\dots,q$.

Each symbolic name must begin on a new line\footnote{The GLPK
implementation allows several symbolic names to be placed on the same
line.} except the very first symbolic name which can begin on the same
line as the keyword `\verb|general|', `\verb|integer|', or
`\verb|binary|'.

If a variable appears in the general or the integer section, it is
assumed to be general integer variable. If a variable appears in the
binary section, it is assumed to be binary variable, i.e. an integer
variable whose lower bound is zero and upper bound is one. (Note that
if bounds of a variable are specified in the bounds section and then
the variable appears in the binary section, its previously specified
bounds are ignored.)

Here is an example of the integer section:

\begin{verbatim}
   Integer
      z12
      z22
      z35
\end{verbatim}

\section{End keyword}

The keyword `\verb|end|' is intended to end the LP file. It must begin
on a separate line and no other elements (except comments and blank
lines) must follow it. Although this keyword is optional, it is strongly
recommended to include it in the LP file.

\section{Example of CPLEX LP file}

Here is a complete example of CPLEX LP file that corresponds to the
example given in Section \ref{secmpsex}, page \pageref{secmpsex}.

{\footnotesize
\begin{verbatim}
\* plan.lp *\

Minimize
   value: .03 bin1 + .08 bin2 + .17 bin3 + .12 bin4 + .15 bin5 +
          .21 alum + .38 silicon

Subject To
   yield:     bin1 +     bin2 +     bin3 +     bin4 +     bin5 +
              alum +     silicon                                 =  2000

   fe:    .15 bin1 + .04 bin2 + .02 bin3 + .04 bin4 + .02 bin5 +
          .01 alum + .03 silicon                                 <=   60

   cu:    .03 bin1 + .05 bin2 + .08 bin3 + .02 bin4 + .06 bin5 +
          .01 alum                                               <=  100

   mn:    .02 bin1 + .04 bin2 + .01 bin3 + .02 bin4 + .02 bin5   <=   40

   mg:    .02 bin1 + .03 bin2                       + .01 bin5   <=   30

   al:    .70 bin1 + .75 bin2 + .80 bin3 + .75 bin4 + .80 bin5 +
          .97 alum                                               >= 1500

   si1:   .02 bin1 + .06 bin2 + .08 bin3 + .12 bin4 + .02 bin5 +
          .01 alum + .97 silicon                                 >=  250

   si2:   .02 bin1 + .06 bin2 + .08 bin3 + .12 bin4 + .02 bin5 +
          .01 alum + .97 silicon                                 <=  300

Bounds
          bin1 <=  200
          bin2 <= 2500
   400 <= bin3 <=  800
   100 <= bin4 <=  700
          bin5 <= 1500

End

\* eof *\
\end{verbatim}

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Stand-alone LP/MIP Solver}
\label{chaglpsol}

The GLPK package includes the program \verb|glpsol| which is a
stand-alone LP/MIP solver. This program can be invoked from the command
line of from the shell to read LP/MIP problem data in any format
supported by GLPK, solve the problem, and write the obtained problem
solution to a text file in plain format.

\subsubsection*{Usage}

\noindent
\verb|glpsol| [{\it options\dots}] [{\it filename}]

\subsubsection*{General options}

\noindent
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
\verb|--mps|      &  read LP/MIP problem in fixed MPS format \\
\verb|--freemps|  &  read LP/MIP problem in free MPS format (default)\\
\verb|--cpxlp|    &  read LP/MIP problem in CPLEX LP format \\
\verb|--math|     &  read LP/MIP model written in GNU MathProg modeling
                     language \\
\multicolumn{2}{@{}l}{{\tt -m} {\it filename}, {\tt --model}
{\it filename}} \\
                  &  read model section and optional data section from
                     filename (the same as \verb|--math|) \\
\multicolumn{2}{@{}l}{{\tt -d} {\it filename}, {\tt --data}
{\it filename}} \\
                  &  read data section from filename (for \verb|--math|
                     only); if model file also has data section, that
                     section is ignored \\
\multicolumn{2}{@{}l}{{\tt -y} {\it filename}, {\tt --display}
{\it filename}} \\
                  &  send display output to filename (for \verb|--math|
                     only); by default the output is sent to
                     \verb|stdout| \\
\end{tabular}

\noindent
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
\verb|--min|      &  minimization \\
\verb|--max|      &  maximization \\
\verb|--scale|    &  scale problem (default) \\
\verb|--noscale|  &  do not scale problem \\
\verb|--simplex|  &  use simplex method (default) \\
\verb|--interior| &  use interior point method (for pure LP only) \\
\multicolumn{2}{@{}l}{{\tt -o} {\it filename}, {\tt --output}
{\it filename}} \\
                  &  write solution to filename in plain text format \\
\multicolumn{2}{@{}l}{{\tt --bounds} {\it filename}} \\
                  &  write sensitivity bounds to filename in plain text
                     format (LP only) \\
\verb|--tmlim| {\it nnn}
                  &  limit solution time to {\it nnn} seconds
                     (\verb|--tmlim 0| allows obtaining solution at
                     initial point) \\
\verb|--memlim| {\it nnn}
                  &  limit available memory to {\it nnn} Megabytes \\
\verb|--check|    &  do not solve problem, check input data only \\
\verb|--name| {\it probname}
                  &  change problem name to {\it probname} \\
\verb|--plain|    &  use plain names of rows and columns (default) \\
\verb|--orig|     &  try using original names of rows and columns \\
\verb|--wmps| {\it filename}
                  &  write problem to {\it filename} in fixed MPS
                     format \\
\multicolumn{2}{@{}l}{{\tt --wfreemps} {\it filename}} \\
                  &  write problem to {\it filename} in free MPS
                     format \\
\multicolumn{2}{@{}l}{{\tt --wcpxlp} {\it filename}} \\
                  &  write problem to {\it filename} in CPLEX LP
                     format \\
\verb|--wtxt| {\it filename}
                  &  write problem to {\it filename} in plain text
                     format \\
\verb|-h|, \verb|--help|
                  &  display this help information and exit \\
\verb|-v|, \verb|--version|
                  &  display program version and exit \\
\end{tabular}

\subsection*{LP basis factorization option}

\noindent
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
\verb|--luf|      &  LU + Forrest--Tomlin update \\
                  &  (faster, less stable; default) \\
\verb|--cbg|      &  LU + Schur complement + Bartels--Golub update \\
                  &  (slower, more stable) \\
\verb|--cbg|      &  LU + Schur complement + Givens rotation update \\
                  &  (slower, more stable) \\
\end{tabular}

\subsubsection*{Options specific to simplex method}

\noindent
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
\verb|--std|      &  use standard initial basis of all slacks \\
\verb|--adv|      &  use advanced initial basis (default) \\
\verb|--bib|      &  use Bixby's initial basis\\
\end{tabular}

\noindent
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
\verb|--bas| {\it filename}
                  &  read initial basis from {\it filename} in MPS
                     format \\
\verb|--steep|    &  use steepest edge technique (default) \\
\verb|--nosteep|  &  use standard ``textbook'' pricing \\
\verb|--relax|    &  use Harris' two-pass ratio test (default) \\
\verb|--norelax|  &  use standard ``textbook'' ratio test \\
\verb|--presol|   &  use LP presolver (default; assumes \verb|--scale|
                     and \verb|--adv|) \\
\verb|--nopresol| &  do not use LP presolver \\
\verb|--exact|    & use simplex method based on exact arithmetic \\
\end{tabular}

\noindent
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
\verb|--xcheck|   & check final basis using exact arithmetic \\
\verb|--wbas| {\it filename}
                  & write final basis to {\it filename} in MPS format \\
\end{tabular}

\subsubsection*{Options specific to MIP}

\noindent
\begin{tabular}{@{}p{30mm}p{92.3mm}@{}}
\verb|--nomip|    &  consider all integer variables as continuous
                     (allows solving MIP as pure LP) \\
\verb|--first|    &  branch on first integer variable \\
\verb|--last|     &  branch on last integer variable \\
\verb|--drtom|    &  branch using heuristic by Driebeck and Tomlin
                     (default) \\
\verb|--mostf|    &  branch on most fractional varaible \\
\verb|--dfs|      &  backtrack using depth first search \\
\verb|--bfs|      &  backtrack using breadth first search \\
\verb|--bestp|    &  backtrack using the best projection heuristic
                     (default) \\
\verb|--bestb|    &  backtrack using node with best local bound \\
\verb|--intopt|   &  use advanced MIP solver (enables MIP presolving)\\
\verb|--binarize| &  replace general integer variables by binary ones
                     (assumes \verb|--intopt|)\\
\verb|--cover|    &  generate mixed cover cuts\\
\verb|--clique|   &  generate clique cuts\\
\verb|--gomory|   &  generate Gomory's mixed integer cuts\\
\verb|--mir|      &  generate MIR (mixed integer rounding) cuts\\
\verb|--cuts|     &  generate cuts of all classes above (assumes
                     \verb|--intopt|)\\
\end{tabular}

\bigskip

\noindent
For description of the MPS format see Appendix \ref{champs},
page \pageref{champs}.

\bigskip

\noindent
For description of the CPLEX LP format see Appendix \ref{chacplex},
page \pageref{chacplex}.

\bigskip

\noindent
For description of the modeling language see the document ``Modeling
Language GNU MathProg: Language Reference'' included in the GLPK
distribution.

\end{document}
