%* glpk02.tex *%
\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{glp\_create\_prob---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{glp\_set\_prob\_name---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{glp\_set\_obj\_name---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{glp\_set\_obj\_dir---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{glp\_add\_rows---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.
\newpage
\subsection{glp\_add\_cols---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{glp\_set\_row\_name---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{glp\_set\_col\_name---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.
\subsection{glp\_set\_row\_bnds---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|.
\newpage
\subsection{glp\_set\_col\_bnds---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{glp\_set\_obj\_coef---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{glp\_set\_mat\_row---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{glp\_set\_mat\_col---set (replace) column of the
constr\-aint 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{glp\_load\_matrix---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{glp\_check\_dup---check for duplicate elements in sparse
matrix}
\subsubsection*{Synopsis}
\begin{verbatim}
int glp_check_dup(int m, int n, int ne, const int ia[],
const int ja[]);
\end{verbatim}
\subsubsection*{Description}
The routine \verb|glp_check_dup checks| for duplicate elements (that
is, elements with identical indices) in a sparse matrix specified in
the coordinate format.
The parameters $m$ and $n$ specifies, respectively, the number of rows
and columns in the matrix, $m\geq 0$, $n\geq 0$.
The parameter {\it ne} specifies the number of (structurally) non-zero
elements in the matrix, {\it ne} $\geq 0$.
Elements of the matrix are specified as doublets $(ia[k],ja[k])$ for
$k=1,\dots,ne$, where $ia[k]$ is a row index, $ja[k]$ is a column index.
The routine \verb|glp_check_dup| can be used prior to a call to the
routine \verb|glp_load_matrix| to check that the constraint matrix to
be loaded has no duplicate elements.
\subsubsection*{Returns}
The routine \verb|glp_check_dup| returns one of the following values:
\noindent
\begin{tabular}{@{}r@{\ }c@{\ }l@{}}
0&---&the matrix has no duplicate elements;\\
$-k$&---&indices $ia[k]$ or/and $ja[k]$ are out of range;\\
$+k$&---&element $(ia[k],ja[k])$ is duplicate.\\
\end{tabular}
\subsection{glp\_sort\_matrix---sort elements of the constraint matrix}
\subsubsection*{Synopsis}
\begin{verbatim}
void glp_sort_matrix(glp_prob *P);
\end{verbatim}
\subsubsection*{Description}
The routine \verb|glp_sort_matrix| sorts elements of the constraint
matrix rebuilding its row and column linked lists. On exit from the
routine the constraint matrix is not changed, however, elements in the
row linked lists become ordered by ascending column indices, and the
elements in the column linked lists become ordered by ascending row
indices.
\subsection{glp\_del\_rows---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{glp\_del\_cols---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{glp\_copy\_prob---copy problem object content}
\subsubsection*{Synopsis}
\begin{verbatim}
void glp_copy_prob(glp_prob *dest, glp_prob *prob, int names);
\end{verbatim}
\subsubsection*{Description}
The routine \verb|glp_copy_prob| copies the content of the problem
object \verb|prob| to the problem object \verb|dest|.
The parameter \verb|names| is a flag. If it is \verb|GLP_ON|,
the routine also copies all symbolic names; otherwise, if it is
\verb|GLP_OFF|, no symbolic names are copied.
\newpage
\subsection{glp\_erase\_prob---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{glp\_delete\_prob---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{glp\_get\_prob\_name---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{glp\_get\_obj\_name---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{glp\_get\_obj\_dir---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{glp\_get\_num\_rows---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{glp\_get\_num\_cols---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{glp\_get\_row\_name---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{glp\_get\_col\_name---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{glp\_get\_row\_type---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{glp\_get\_row\_lb---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{glp\_get\_row\_ub---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{glp\_get\_col\_type---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{glp\_get\_col\_lb---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{glp\_get\_col\_ub---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{glp\_get\_obj\_coef---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{glp\_get\_num\_nz---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{glp\_get\_mat\_row---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{glp\_get\_mat\_col---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{glp\_create\_index---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{glp\_find\_row---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{glp\_find\_col---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{glp\_delete\_index---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{glp\_set\_rii---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{glp\_set\_sjj---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{glp\_get\_rii---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{glp\_get\_sjj---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{glp\_scale\_prob---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{glp\_unscale\_prob---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{glp\_set\_row\_stat---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{glp\_set\_col\_stat---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{glp\_std\_basis---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{glp\_adv\_basis---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{glp\_cpx\_basis---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.3)
$$
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.3), 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{glp\_simplex---solve LP problem with the primal or dual
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*{Built-in LP presolver}
The simplex solver has {\it built-in LP presolver}. It 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*{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 500})}
\\
&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}
\subsubsection*{Example 1}
The following main program reads LP problem instance in fixed MPS
format from file \verb|25fv47.mps|,\footnote{This instance in fixed MPS
format can be found in the Netlib LP collection; see
{\tt ftp://ftp.netlib.org/lp/data/}.} constructs an advanced initial
basis, solves the instance with the primal simplex method (by default),
and writes the solution to file \verb|25fv47.txt|.
\newpage
\begin{footnotesize}
\begin{verbatim}
/* spxsamp1.c */
#include <stdio.h>
#include <stdlib.h>
#include <glpk.h>
int main(void)
{ glp_prob *P;
P = glp_create_prob();
glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
glp_adv_basis(P, 0);
glp_simplex(P, NULL);
glp_print_sol(P, "25fv47.txt");
glp_delete_prob(P);
return 0;
}
/* eof */
\end{verbatim}
\end{footnotesize}
\noindent
Below here is shown the terminal output from this example program.
\begin{footnotesize}
\begin{verbatim}
Reading problem data from `25fv47.mps'...
Problem: 25FV47
Objective: R0000
822 rows, 1571 columns, 11127 non-zeros
6919 records were read
Crashing...
Size of triangular part = 799
0: obj = 1.627307307e+04 infeas = 5.194e+04 (23)
200: obj = 1.474901610e+04 infeas = 1.233e+04 (19)
400: obj = 1.343909995e+04 infeas = 3.648e+03 (13)
600: obj = 1.756052217e+04 infeas = 4.179e+02 (7)
* 775: obj = 1.789251591e+04 infeas = 4.982e-14 (1)
* 800: obj = 1.663354510e+04 infeas = 2.857e-14 (1)
* 1000: obj = 1.024935068e+04 infeas = 1.958e-12 (1)
* 1200: obj = 7.860174791e+03 infeas = 2.810e-29 (1)
* 1400: obj = 6.642378184e+03 infeas = 2.036e-16 (1)
* 1600: obj = 6.037014568e+03 infeas = 0.000e+00 (1)
* 1800: obj = 5.662171307e+03 infeas = 6.447e-15 (1)
* 2000: obj = 5.528146165e+03 infeas = 9.764e-13 (1)
* 2125: obj = 5.501845888e+03 infeas = 0.000e+00 (1)
OPTIMAL SOLUTION FOUND
Writing basic solution to `25fv47.txt'...
\end{verbatim}
\end{footnotesize}
\newpage
\subsubsection*{Example 2}
The following main program solves the same LP problem instance as in
Example 1 above, however, it uses the dual simplex method, which starts
from the standard initial basis.
\begin{footnotesize}
\begin{verbatim}
/* spxsamp2.c */
#include <stdio.h>
#include <stdlib.h>
#include <glpk.h>
int main(void)
{ glp_prob *P;
glp_smcp parm;
P = glp_create_prob();
glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
glp_init_smcp(&parm);
parm.meth = GLP_DUAL;
glp_simplex(P, &parm);
glp_print_sol(P, "25fv47.txt");
glp_delete_prob(P);
return 0;
}
/* eof */
\end{verbatim}
\end{footnotesize}
\noindent
Below here is shown the terminal output from this example program.
\begin{footnotesize}
\begin{verbatim}
Reading problem data from `25fv47.mps'...
Problem: 25FV47
Objective: R0000
822 rows, 1571 columns, 11127 non-zeros
6919 records were read
0: infeas = 1.223e+03 (516)
200: infeas = 7.000e+00 (471)
240: infeas = 1.106e-14 (461)
| 400: obj = -5.394267152e+03 infeas = 5.571e-16 (391)
| 600: obj = -4.586395752e+03 infeas = 1.389e-15 (340)
| 800: obj = -4.158268146e+03 infeas = 1.640e-15 (264)
| 1000: obj = -3.725320045e+03 infeas = 5.181e-15 (245)
| 1200: obj = -3.104802163e+03 infeas = 1.019e-14 (210)
| 1400: obj = -2.584190499e+03 infeas = 8.865e-15 (178)
| 1600: obj = -2.073852927e+03 infeas = 7.867e-15 (142)
| 1800: obj = -1.164037407e+03 infeas = 8.792e-15 (109)
| 2000: obj = -4.370590250e+02 infeas = 2.591e-14 (85)
| 2200: obj = 1.068240144e+03 infeas = 1.025e-13 (70)
| 2400: obj = 1.607481126e+03 infeas = 3.272e-14 (67)
| 2600: obj = 3.038230551e+03 infeas = 4.850e-14 (52)
| 2800: obj = 4.316238187e+03 infeas = 2.622e-14 (36)
| 3000: obj = 5.443842629e+03 infeas = 3.976e-15 (11)
| 3060: obj = 5.501845888e+03 infeas = 8.806e-15 (2)
OPTIMAL SOLUTION FOUND
Writing basic solution to `25fv47.txt'...
\end{verbatim}
\end{footnotesize}
\subsection{glp\_exact---solve LP problem in exact arithmetic}
\subsubsection*{Synopsis}
\begin{verbatim}
int glp_exact(glp_prob *lp, const glp_smcp *parm);
\end{verbatim}
\subsubsection*{Description}
The routine \verb|glp_exact| is a tentative 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.
Note that the routine \verb|glp_exact| uses only two control parameters
passed in the structure \verb|glp_smcp|, namely, \verb|it_lim| and
\verb|tm_lim|.
\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 exactly singular.\\
\verb|GLP_EBOUND| & Unable to start the search, because some
double-bounded (auxiliary or structural) variables have incorrect
bounds.\\
\verb|GLP_EFAIL| & The problem instance has no rows/columns.\\
\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.\\
\end{tabular}
\subsubsection*{Comments}
Computations in exact arithmetic are very time consuming, so solving
LP problem with the routine \verb|glp_exact| from the very beginning is
not a good idea. It is much better at first to find an optimal basis
with the routine \verb|glp_simplex| and only then to call
\verb|glp_exact|, in which case only a few simplex iterations need to
be performed in exact arithmetic.
\subsection{glp\_init\_smcp---initialize simplex solver 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.
\subsection{glp\_get\_status---determine 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|.
\newpage
\subsection{glp\_get\_prim\_stat---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}
\subsection{glp\_get\_dual\_stat---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{glp\_get\_obj\_val---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{glp\_get\_row\_stat---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{glp\_get\_row\_prim---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{glp\_get\_row\_dual---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.
\newpage
\subsection{glp\_get\_col\_stat---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}
\subsection{glp\_get\_col\_prim---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{glp\_get\_col\_dual---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.
\newpage
\subsection{glp\_get\_unbnd\_ray---determine variable causing\\
unboundedness}
\subsubsection*{Synopsis}
\begin{verbatim}
int glp_get_unbnd_ray(glp_prob *lp);
\end{verbatim}
\subsubsection*{Returns}
The routine \verb|glp_get_unbnd_ray| returns the number $k$ of
a variable, which causes primal or dual unboundedness.
If $1\leq k\leq m$, it is $k$-th auxiliary variable, and if
$m+1\leq k\leq m+n$, it is $(k-m)$-th structural variable, where $m$ is
the number of rows, $n$ is the number of columns in the problem object.
If such variable is not defined, the routine returns 0.
\subsubsection*{Comments}
If it is not exactly known which version of the simplex solver
detected unboundedness, i.e. whether the unboundedness is primal or
dual, it is sufficient to check the status of the variable
with the routine \verb|glp_get_row_stat| or \verb|glp_get_col_stat|.
If the variable is non-basic, the unboundedness is primal, otherwise,
if the variable is basic, the unboundedness is dual (the latter case
means that the problem has no primal feasible dolution).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{Interior-point method routines}
{\it Interior-point methods} (also known as {\it barrier methods}) are
more modern and powerful numerical methods for large-scale linear
programming. Such methods are especially efficient for very sparse LP
problems and allow solving such problems much faster than the simplex
method.
In brief, the GLPK interior-point solver works as follows.
At first, the solver transforms the original LP to a {\it working} LP
in the standard format:
\medskip
\noindent
\hspace{.5in} minimize
$$z = c_1x_{m+1} + c_2x_{m+2} + \dots + c_nx_{m+n} + c_0 \eqno (2.4)$$
\hspace{.5in} subject to linear constraints
$$
\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}l}
a_{11}x_{m+1}&+&a_{12}x_{m+2}&+ \dots +&a_{1n}x_{m+n}&=&b_1 \\
a_{21}x_{m+1}&+&a_{22}x_{m+2}&+ \dots +&a_{2n}x_{m+n}&=&b_2 \\
\multicolumn{7}{c}
{.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
a_{m1}x_{m+1}&+&a_{m2}x_{m+2}&+ \dots +&a_{mn}x_{m+n}&=&b_m \\
\end{array} \eqno (2.5)
$$
\hspace{.5in} and non-negative variables
$$x_1\geq 0,\ \ x_2\geq 0,\ \ \dots,\ \ x_n\geq 0 \eqno(2.6)$$
where: $z$ is the objective function; $x_1$, \dots, $x_n$ are variables;
$c_1$, \dots, $c_n$ are objective coefficients; $c_0$ is a constant term
of the objective function;\linebreak $a_{11}$, \dots, $a_{mn}$ are
constraint coefficients; $b_1$, \dots, $b_m$ are right-hand sides.
Using vector and matrix notations the working LP (2.4)---(2.6) can be
written as follows:
$$z=c^Tx+c_0\ \rightarrow\ \min,\eqno(2.7)$$
$$Ax=b,\eqno(2.8)$$
$$x\geq 0,\eqno(2.9)$$
where: $x=(x_j)$ is $n$-vector of variables, $c=(c_j)$ is $n$-vector of
objective coefficients, $A=(a_{ij})$ is $m\times n$-matrix of
constraint coefficients, and $b=(b_i)$ is $m$-vector of right-hand
sides.
Karush--Kuhn--Tucker optimality conditions for LP (2.7)---(2.9) are the
following:
\newpage
$$Ax=b,\eqno(2.10)$$
$$A^T\pi+\lambda=c,\eqno(2.11)$$
$$\lambda^Tx=0,\eqno(2.12)$$
$$x\geq 0,\ \ \lambda\geq 0,\eqno(2.13)$$
where: $\pi$ is $m$-vector of Lagrange multipliers (dual variables) for
equality constraints (2.8), $\lambda$ is $n$-vector of Lagrange
multipliers (dual variables) for non-negativity constraints (2.9),
(2.10) is the primal feasibility condition, (2.11) is the dual
feasibility condition, (2.12) is the primal-dual complementarity
condition, and (2.13) is the non-negativity conditions.
The main idea of the primal-dual interior-point method is based on
finding a point in the primal-dual space (i.e. in the space of all
primal and dual variables $x$, $\pi$, and $\lambda$), which satisfies
to all optimality conditions (2.10)---(2.13). Obviously, $x$-component
of such point then provides an optimal solution to the working LP
(2.7)---(2.9).
To find the optimal point $(x^*,\pi^*,\lambda^*)$ the interior-point
method attempts to solve the system of equations (2.10)---(2.12), which
is closed in the sense that the number of variables $x_j$, $\pi_i$, and
$\lambda_j$ and the number equations are the same and equal to $m+2n$.
Due to condition (2.12) this system of equations is non-linear, so it
can be solved with a version of {\it Newton's method} provided with
additional rules to keep the current point within the positive orthant
as required by the non-negativity conditions (2.13).
Finally, once the optimal point $(x^*,\pi^*,\lambda^*)$ has been found,
the solver performs inverse transformations to recover corresponding
solution to the original LP passed to the solver from the application
program.
\subsection{glp\_interior---solve LP problem with the interior-point
method}
\subsubsection*{Synopsis}
\begin{verbatim}
int glp_interior(glp_prob *P, const glp_iptcp *parm);
\end{verbatim}
\subsubsection*{Description}
The routine \verb|glp_interior| is a driver to the LP solver based on
the primal-dual interior-point 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 interior-point solver has a set of control parameters. Values of
the control parameters can be passed in the structure \verb|glp_iptcp|,
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_iptcp| by default values of all
control parameters using the routine \verb|glp_init_iptcp| (see the
next subsection). This is needed for backward compatibility, because in
the future there may appear new members in the structure
\verb|glp_iptcp|.
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_EFAIL| & The problem has no rows/columns.\\
\verb|GLP_ENOCVG| & Very slow convergence or divergence.\\
\verb|GLP_EITLIM| & Iteration limit exceeded.\\
\verb|GLP_EINSTAB| & Numerical instability on solving Newtonian
system.\\
\end{tabular}
\subsubsection*{Comments}
The routine \verb|glp_interior| implements an easy version of
the primal-dual interior-point method based on Mehrotra's
technique.\footnote{S. Mehrotra. On the implementation of a primal-dual
interior point method. SIAM J. on Optim., 2(4), pp. 575-601, 1992.}
Note that currently the GLPK interior-point solver does not include
many important features, in particular:
$\bullet$ it is not able to process dense columns. Thus, if the
constraint matrix of the LP problem has dense columns, the solving
process may be inefficient;
$\bullet$ 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;
$\bullet$ it is not able to identify the optimal basis, which
corresponds to the interior-point solution found.
\newpage
\subsubsection*{Terminal output}
Solving large LP problems may take a long time, so the solver reports
some 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.} which is sent to the terminal. This information 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 (cf. (2.10)):
$$\frac{\|Ax^{(k)}-b\|}{1+\|b\|},\eqno(2.14)$$
\verb|ddd| is the current relative dual infeasibility (cf. (2.11)):
$$\frac{\|A^T\pi^{(k)}+\lambda^{(k)}-c\|}{1+\|c\|},\eqno(2.15)$$
\verb|ggg| is the current primal-dual gap (cf. (2.12)):
$$\frac{|c^Tx^{(k)}-b^T\pi^{(k)}|}{1+|c^Tx^{(k)}|},\eqno(2.16)$$
and $[x^{(k)},\pi^{(k)},\lambda^{(k)}]$ is the current point on $k$-th
iteration, $k=0,1,2,\dots$\ . Note that all solution components are
internally scaled, so information sent to the terminal is suitable only
for visual inspection.
\subsubsection*{Control parameters}
This paragraph describes all control parameters currently used in the
interior-point solver. Symbolic names of control parameters are names of
corresponding members in the structure \verb|glp_iptcp|.
\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 ord\_alg} (default: {\tt GLP\_ORD\_AMD})}
\\
&Ordering algorithm used prior to Cholesky factorization:\\
&\verb|GLP_ORD_NONE |---use natural (original) ordering;\\
&\verb|GLP_ORD_QMD |---quotient minimum degree (QMD);\\
&\verb|GLP_ORD_AMD |---approximate minimum degree (AMD);\\
&\verb|GLP_ORD_SYMAMD|---approximate minimum degree (SYMAMD).\\
\end{tabular}
\subsubsection*{Example}
The following main program reads LP problem instance in fixed MPS
format from file \verb|25fv47.mps|,\footnote{This instance in fixed MPS
format can be found in the Netlib LP collection; see
{\tt ftp://ftp.netlib.org/lp/data/}.} solves it with the interior-point
solver, and writes the solution to file \verb|25fv47.txt|.
\begin{footnotesize}
\begin{verbatim}
/* iptsamp.c */
#include <stdio.h>
#include <stdlib.h>
#include <glpk.h>
int main(void)
{ glp_prob *P;
P = glp_create_prob();
glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
glp_interior(P, NULL);
glp_print_ipt(P, "25fv47.txt");
glp_delete_prob(P);
return 0;
}
/* eof */
\end{verbatim}
\end{footnotesize}
\noindent
Below here is shown the terminal output from this example program.
\begin{footnotesize}
\begin{verbatim}
Reading problem data from `25fv47.mps'...
Problem: 25FV47
Objective: R0000
822 rows, 1571 columns, 11127 non-zeros
6919 records were read
Original LP has 822 row(s), 1571 column(s), and 11127 non-zero(s)
Working LP has 821 row(s), 1876 column(s), and 10705 non-zero(s)
Matrix A has 10705 non-zeros
Matrix S = A*A' has 11895 non-zeros (upper triangle)
Minimal degree ordering...
Computing Cholesky factorization S = L'*L...
Matrix L has 35411 non-zeros
Guessing initial point...
Optimization begins...
0: obj = 1.823377629e+05; rpi = 1.3e+01; rdi = 1.4e+01; gap = 9.3e-01
1: obj = 9.260045192e+04; rpi = 5.3e+00; rdi = 5.6e+00; gap = 6.8e+00
2: obj = 3.596999742e+04; rpi = 1.5e+00; rdi = 1.2e+00; gap = 1.8e+01
3: obj = 1.989627568e+04; rpi = 4.7e-01; rdi = 3.0e-01; gap = 1.9e+01
4: obj = 1.430215557e+04; rpi = 1.1e-01; rdi = 8.6e-02; gap = 1.4e+01
5: obj = 1.155716505e+04; rpi = 2.3e-02; rdi = 2.4e-02; gap = 6.8e+00
6: obj = 9.660273208e+03; rpi = 6.7e-03; rdi = 4.6e-03; gap = 3.9e+00
7: obj = 8.694348283e+03; rpi = 3.7e-03; rdi = 1.7e-03; gap = 2.0e+00
8: obj = 8.019543639e+03; rpi = 2.4e-03; rdi = 3.9e-04; gap = 1.0e+00
9: obj = 7.122676293e+03; rpi = 1.2e-03; rdi = 1.5e-04; gap = 6.6e-01
10: obj = 6.514534518e+03; rpi = 6.1e-04; rdi = 4.3e-05; gap = 4.1e-01
11: obj = 6.361572203e+03; rpi = 4.8e-04; rdi = 2.2e-05; gap = 3.0e-01
12: obj = 6.203355508e+03; rpi = 3.2e-04; rdi = 1.7e-05; gap = 2.6e-01
13: obj = 6.032943411e+03; rpi = 2.0e-04; rdi = 9.3e-06; gap = 2.1e-01
14: obj = 5.796553021e+03; rpi = 9.8e-05; rdi = 3.2e-06; gap = 1.0e-01
15: obj = 5.667032431e+03; rpi = 4.4e-05; rdi = 1.1e-06; gap = 5.6e-02
16: obj = 5.613911867e+03; rpi = 2.5e-05; rdi = 4.1e-07; gap = 3.5e-02
17: obj = 5.560572626e+03; rpi = 9.9e-06; rdi = 2.3e-07; gap = 2.1e-02
18: obj = 5.537276001e+03; rpi = 5.5e-06; rdi = 8.4e-08; gap = 1.1e-02
19: obj = 5.522746942e+03; rpi = 2.2e-06; rdi = 4.0e-08; gap = 6.7e-03
20: obj = 5.509956679e+03; rpi = 7.5e-07; rdi = 1.8e-08; gap = 2.9e-03
21: obj = 5.504571733e+03; rpi = 1.6e-07; rdi = 5.8e-09; gap = 1.1e-03
22: obj = 5.502576367e+03; rpi = 3.4e-08; rdi = 1.0e-09; gap = 2.5e-04
23: obj = 5.502057119e+03; rpi = 8.1e-09; rdi = 3.0e-10; gap = 7.7e-05
24: obj = 5.501885996e+03; rpi = 9.4e-10; rdi = 1.2e-10; gap = 2.4e-05
25: obj = 5.501852464e+03; rpi = 1.4e-10; rdi = 1.2e-11; gap = 3.0e-06
26: obj = 5.501846549e+03; rpi = 1.4e-11; rdi = 1.2e-12; gap = 3.0e-07
27: obj = 5.501845954e+03; rpi = 1.4e-12; rdi = 1.2e-13; gap = 3.0e-08
28: obj = 5.501845895e+03; rpi = 1.5e-13; rdi = 1.2e-14; gap = 3.0e-09
OPTIMAL SOLUTION FOUND
Writing interior-point solution to `25fv47.txt'...
\end{verbatim}
\end{footnotesize}
\subsection{glp\_init\_iptcp---initialize interior-point solver control
parameters}
\subsubsection*{Synopsis}
\begin{verbatim}
int glp_init_iptcp(glp_iptcp *parm);
\end{verbatim}
\subsubsection*{Description}
The routine \verb|glp_init_iptcp| initializes control parameters, which
are used by the interior-point solver, with default values.
Default values of the control parameters are stored in the structure
\verb|glp_iptcp|, which the parameter \verb|parm| points to.
\subsection{glp\_ipt\_status---determine solution status}
\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. \\
\verb|GLP_INFEAS|& interior-point solution is infeasible. \\
\verb|GLP_NOFEAS|& no feasible primal-dual solution exists.\\
\end{tabular}
\subsection{glp\_ipt\_obj\_val---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.
\subsection{glp\_ipt\_row\_prim---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.
\newpage
\subsection{glp\_ipt\_row\_dual---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{glp\_ipt\_col\_prim---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{glp\_ipt\_col\_dual---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{glp\_set\_col\_kind---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{glp\_get\_col\_kind---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}
\subsection{glp\_get\_num\_int---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{glp\_get\_num\_bin---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{glp\_intopt---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, which is a hybrid of branch-and-bound and
cutting plane methods.
If the presolver is disabled (see paragraph ``Control parameters''
below), on entry to the routine \verb|glp_intopt| the problem object,
which the parameter \verb|mip| points to, should contain optimal
solution to LP relaxation (it can be obtained, for example, with the
routine \verb|glp_simplex|). Otherwise, if the presolver is enabled, it
is not necessary.
The MIP solver has a set of control parameters. Values of the control
parameters can be passed in the structure \verb|glp_iocp|, 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_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 \verb|parm| can be specified as \verb|NULL|, in which case
the solver uses default settings.
Note that the GLPK branch-and-cut solver is not perfect, so it is unable
to solve hard or very large scale MIP instances for a reasonable time.
\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. (This code may appear only if the
presolver is disabled.)\\
\verb|GLP_ENOPFS| & Unable to start the search, because LP relaxation
of the MIP problem instance has no primal feasible solution. (This code
may appear only if the presolver is enabled.)\\
\verb|GLP_ENODFS| & Unable to start the search, because LP relaxation
of the MIP problem instance has no dual feasible solution. In other
word, this code means that if the LP relaxation has at least one primal
feasible solution, its optimal solution is unbounded, so if the MIP
problem has at least one integer feasible solution, its (integer)
optimal solution is also unbounded. (This code may appear only if the
presolver is enabled.)\\
\verb|GLP_EFAIL| & The search was prematurely terminated due to the
solver failure.\\
\verb|GLP_EMIPGAP| & The search was prematurely terminated, because the
relative mip gap tolerance has been reached.\\
\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*{Built-in MIP presolver}
The branch-and-cut solver has {\it built-in MIP presolver}. It is
a subprogram that transforms the original MIP problem specified in the
problem object to an equivalent MIP problem, which may be easier for
solving with the branch-and-cut method than the original one. For
example, the presolver can remove redundant constraints and variables,
whose optimal values are known, perform bound and coefficient reduction,
etc. Once the transformed MIP problem has been solved, the presolver
transforms its solution back to corresponding solution of the original
problem.
Presolving is an optional feature of the routine \verb|glp_intopt|, and
by default it is disabled. In order to enable the MIP presolver, the
control parameter \verb|presolve| should be set to \verb|GLP_ON| (see
paragraph ``Control parameters'' below).
\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 ``Branch-and-Cut API Routines''.
\subsubsection*{Terminal output}
Solving a MIP problem may take a long time, so the solver reports some
information about best known solutions, which is sent to the terminal.
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;\\
&\verb|GLP_BR_PCH|---hybrid pseudocost heuristic.\\
\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 fp\_heur} (default: {\tt GLP\_OFF})}
\\
&Feasibility pump heuristic option:\\
&\verb|GLP_ON |---enable applying the feasibility pump heuristic;\\
&\verb|GLP_OFF|---disable applying the feasibility pump heuristic.\\
\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_ON |---enable generating Gomory's cuts;\\
&\verb|GLP_OFF|---disable 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_ON |---enable generating MIR cuts;\\
&\verb|GLP_OFF|---disable generating MIR cuts.\\
\end{tabular}
\medskip
\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int cov\_cuts} (default: {\tt GLP\_OFF})}\\
&Mixed cover cut option:\\
&\verb|GLP_ON |---enable generating mixed cover cuts;\\
&\verb|GLP_OFF|---disable generating mixed cover cuts.\\
\end{tabular}
\medskip
\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int clq\_cuts} (default: {\tt GLP\_OFF})}\\
&Clique cut option:\\
&\verb|GLP_ON |---enable generating clique cuts;\\
&\verb|GLP_OFF|---disable generating clique 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 double mip\_gap} (default: {\tt 0.0})}\\
&The relative mip gap tolerance. If the relative mip gap for currently
known best integer feasible solution falls below this tolerance, the
solver terminates the search. This allows obtainig suboptimal integer
feasible solutions if solving the problem to optimality takes too long
time.\\
\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
``Branch-and-Cut API 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}
\medskip
\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int presolve} (default: {\tt GLP\_OFF})}\\
&MIP presolver option:\\
&\verb|GLP_ON |---enable using the MIP presolver;\\
&\verb|GLP_OFF|---disable using the MIP presolver.\\
\end{tabular}
\medskip
\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int binarize} (default: {\tt GLP\_OFF})}\\
&Binarization option (used only if the presolver is enabled):\\
&\verb|GLP_ON |---replace general integer variables by binary ones;\\
&\verb|GLP_OFF|---do not use binarization.\\
\end{tabular}
\subsection{glp\_init\_iocp---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{glp\_mip\_status---determine 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. \\
\end{tabular}
\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
\verb|GLP_NOFEAS| & problem has no integer feasible solution (proven by
the solver). \\
\end{tabular}
\subsection{glp\_mip\_obj\_val---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{glp\_mip\_row\_val---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{glp\_mip\_col\_val---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.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{Additional routines}
\subsection{lpx\_check\_kkt---check Karush-Kuhn-Tucker optimality
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{table}[h]
\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}
\end{table}
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.
%* eof *%
