lemon-project-template-glpk: deps/glpk/doc/glpk02.tex comparison

lemon-project-template-glpk

comparison deps/glpk/doc/glpk02.tex @ 11:4fc6ad2fb8a6

Test GLPK in src/main.cc

author	Alpar Juttner <alpar@cs.elte.hu>
date	Sun, 06 Nov 2011 21:43:29 +0100
parents
children

comparison

equal deleted inserted replaced

--1:000000000000
+:9afd438bb9eb
+%* 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: obj = 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 *%