1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/doc/glpk02.tex	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,3406 @@
     1.4 +%* glpk02.tex *%
     1.5 +
     1.6 +\chapter{Basic API Routines}
     1.7 +
     1.8 +This chapter describes GLPK API routines intended for using in
     1.9 +application programs.
    1.10 +
    1.11 +\subsubsection*{Library header}
    1.12 +
    1.13 +All GLPK API data types and routines are defined in the header file
    1.14 +\verb|glpk.h|. It should be included in all source files which use
    1.15 +GLPK API, either directly or indirectly through some other header file
    1.16 +as follows:
    1.17 +
    1.18 +\begin{verbatim}
    1.19 +   #include <glpk.h>
    1.20 +\end{verbatim}
    1.21 +
    1.22 +\subsubsection*{Error handling}
    1.23 +
    1.24 +If some GLPK API routine detects erroneous or incorrect data passed by
    1.25 +the application program, it writes appropriate diagnostic messages to
    1.26 +the terminal and then abnormally terminates the application program.
    1.27 +In most practical cases this allows to simplify programming by avoiding
    1.28 +numerous checks of return codes. Thus, in order to prevent crashing the
    1.29 +application program should check all data, which are suspected to be
    1.30 +incorrect, before calling GLPK API routines.
    1.31 +
    1.32 +Should note that this kind of error handling is used only in cases of
    1.33 +incorrect data passed by the application program. If, for example, the
    1.34 +application program calls some GLPK API routine to read data from an
    1.35 +input file and these data are incorrect, the GLPK API routine reports
    1.36 +about error in the usual way by means of the return code.
    1.37 +
    1.38 +\subsubsection*{Thread safety}
    1.39 +
    1.40 +Currently GLPK API routines are non-reentrant and therefore cannot be
    1.41 +used in multi-threaded programs.
    1.42 +
    1.43 +\subsubsection*{Array indexing}
    1.44 +
    1.45 +Normally all GLPK API routines start array indexing from 1, not from 0
    1.46 +(except the specially stipulated cases). This means, for example, that
    1.47 +if some vector $x$ of the length $n$ is passed as an array to some GLPK
    1.48 +API routine, the latter expects vector components to be placed in
    1.49 +locations \verb|x[1]|, \verb|x[2]|, \dots, \verb|x[n]|, and the location
    1.50 +\verb|x[0]| normally is not used.
    1.51 +
    1.52 +In order to avoid indexing errors it is most convenient and most
    1.53 +reliable to declare the array \verb|x| as follows:
    1.54 +
    1.55 +\begin{verbatim}
    1.56 +   double x[1+n];
    1.57 +\end{verbatim}
    1.58 +
    1.59 +\noindent
    1.60 +or to allocate it as follows:
    1.61 +
    1.62 +\begin{verbatim}
    1.63 +   double *x;
    1.64 +   . . .
    1.65 +   x = calloc(1+n, sizeof(double));
    1.66 +\end{verbatim}
    1.67 +
    1.68 +\noindent
    1.69 +In both cases one extra location \verb|x[0]| is reserved that allows
    1.70 +passing the array to GLPK routines in a usual way.
    1.71 +
    1.72 +\section{Problem object}
    1.73 +
    1.74 +All GLPK API routines deal with so called {\it problem object}, which
    1.75 +is a program object of type \verb|glp_prob| and intended to represent
    1.76 +a particular LP or MIP instance.
    1.77 +
    1.78 +The type \verb|glp_prob| is a data structure declared in the header
    1.79 +file \verb|glpk.h| as follows:
    1.80 +
    1.81 +\begin{verbatim}
    1.82 +   typedef struct { ... } glp_prob;
    1.83 +\end{verbatim}
    1.84 +
    1.85 +Problem objects (i.e. program objects of the \verb|glp_prob| type) are
    1.86 +allocated and managed internally by the GLPK API routines. The
    1.87 +application program should never use any members of the \verb|glp_prob|
    1.88 +structure directly and should deal only with pointers to these objects
    1.89 +(that is, \verb|glp_prob *| values).
    1.90 +
    1.91 +\pagebreak
    1.92 +
    1.93 +The problem object consists of five segments, which are:
    1.94 +
    1.95 +$\bullet$ problem segment,
    1.96 +
    1.97 +$\bullet$ basis segment,
    1.98 +
    1.99 +$\bullet$ interior point segment,
   1.100 +
   1.101 +$\bullet$ MIP segment, and
   1.102 +
   1.103 +$\bullet$ control parameters and statistics segment.
   1.104 +
   1.105 +\subsubsection*{Problem segment}
   1.106 +
   1.107 +The {\it problem segment} contains original LP/MIP data, which
   1.108 +corresponds to the problem formulation (1.1)---(1.3) (see Section
   1.109 +\ref{seclp}, page \pageref{seclp}). It includes the following
   1.110 +components:
   1.111 +
   1.112 +$\bullet$ rows (auxiliary variables),
   1.113 +
   1.114 +$\bullet$ columns (structural variables),
   1.115 +
   1.116 +$\bullet$ objective function, and
   1.117 +
   1.118 +$\bullet$ constraint matrix.
   1.119 +
   1.120 +Rows and columns have the same set of the following attributes:
   1.121 +
   1.122 +$\bullet$ ordinal number,
   1.123 +
   1.124 +$\bullet$ symbolic name (1 up to 255 arbitrary graphic characters),
   1.125 +
   1.126 +$\bullet$ type (free, lower bound, upper bound, double bound, fixed),
   1.127 +
   1.128 +$\bullet$ numerical values of lower and upper bounds,
   1.129 +
   1.130 +$\bullet$ scale factor.
   1.131 +
   1.132 +{\it Ordinal numbers} are intended for referencing rows and columns.
   1.133 +Row ordinal numbers are integers $1, 2, \dots, m$, and column ordinal
   1.134 +numbers are integers $1, 2, \dots, n$, where $m$ and $n$ are,
   1.135 +respectively, the current number of rows and columns in the problem
   1.136 +object.
   1.137 +
   1.138 +{\it Symbolic names} are intended for informational purposes. They also
   1.139 +can be used for referencing rows and columns.
   1.140 +
   1.141 +{\it Types and bounds} of rows (auxiliary variables) and columns
   1.142 +(structural variables) are explained above (see Section \ref{seclp},
   1.143 +page \pageref{seclp}).
   1.144 +
   1.145 +{\it Scale factors} are used internally for scaling rows and columns of
   1.146 +the constraint matrix.
   1.147 +
   1.148 +Information about the {\it objective function} includes numerical
   1.149 +values of objective coefficients and a flag, which defines the
   1.150 +optimization direction (i.e. minimization or maximization).
   1.151 +
   1.152 +The {\it constraint matrix} is a $m \times n$ rectangular matrix built
   1.153 +of constraint coefficients $a_{ij}$, which defines the system of linear
   1.154 +constraints (1.2) (see Section \ref{seclp}, page \pageref{seclp}). This
   1.155 +matrix is stored in the problem object in both row-wise and column-wise
   1.156 +sparse formats.
   1.157 +
   1.158 +Once the problem object has been created, the application program can
   1.159 +access and modify any components of the problem segment in arbitrary
   1.160 +order.
   1.161 +
   1.162 +\subsubsection*{Basis segment}
   1.163 +
   1.164 +The {\it basis segment} of the problem object keeps information related
   1.165 +to the current basic solution. It includes:
   1.166 +
   1.167 +$\bullet$ row and column statuses,
   1.168 +
   1.169 +$\bullet$ basic solution statuses,
   1.170 +
   1.171 +$\bullet$ factorization of the current basis matrix, and
   1.172 +
   1.173 +$\bullet$ basic solution components.
   1.174 +
   1.175 +The {\it row and column statuses} define which rows and columns are
   1.176 +basic and which are non-basic. These statuses may be assigned either by
   1.177 +the application program of by some API routines. Note that these
   1.178 +statuses are always defined independently on whether the corresponding
   1.179 +basis is valid or not.
   1.180 +
   1.181 +The {\it basic solution statuses} include the {\it primal status} and
   1.182 +the {\it dual status}, which are set by the simplex-based solver once
   1.183 +the problem has been solved. The primal status shows whether a primal
   1.184 +basic solution is feasible, infeasible, or undefined. The dual status
   1.185 +shows the same for a dual basic solution.
   1.186 +
   1.187 +The {\it factorization of the basis matrix} is some factorized form
   1.188 +(like LU-factorization) of the current basis matrix (defined by the
   1.189 +current row and column statuses). The factorization is used by the
   1.190 +simplex-based solver and kept when the solver terminates the search.
   1.191 +This feature allows efficiently reoptimizing the problem after some
   1.192 +modifications (for example, after changing some bounds or objective
   1.193 +coefficients). It also allows performing the post-optimal analysis (for
   1.194 +example, computing components of the simplex table, etc.).
   1.195 +
   1.196 +The {\it basic solution components} include primal and dual values of
   1.197 +all auxiliary and structural variables for the most recently obtained
   1.198 +basic solution.
   1.199 +
   1.200 +\subsubsection*{Interior point segment}
   1.201 +
   1.202 +The {\it interior point segment} is automatically allocated after the
   1.203 +problem has been solved using the interior point solver. It contains
   1.204 +interior point solution components, which include the solution status,
   1.205 +and primal and dual values of all auxiliary and structural variables.
   1.206 +
   1.207 +\subsubsection*{MIP segment}
   1.208 +
   1.209 +The {\it MIP segment} is used only for MIP problems. This segment
   1.210 +includes:
   1.211 +
   1.212 +$\bullet$ column kinds,
   1.213 +
   1.214 +$\bullet$ MIP solution status, and
   1.215 +
   1.216 +$\bullet$ MIP solution components.
   1.217 +
   1.218 +The {\it column kinds} define which columns (i.e. structural variables)
   1.219 +are integer and which are continuous.
   1.220 +
   1.221 +The {\it MIP solution status} is set by the MIP solver and shows whether
   1.222 +a MIP solution is integer optimal, integer feasible (non-optimal), or
   1.223 +undefined.
   1.224 +
   1.225 +The {\it MIP solution components} are computed by the MIP solver and
   1.226 +include primal values of all auxiliary and structural variables for the
   1.227 +most recently obtained MIP solution.
   1.228 +
   1.229 +Note that in case of MIP problem the basis segment corresponds to
   1.230 +the optimal solution of LP relaxation, which is also available to the
   1.231 +application program.
   1.232 +
   1.233 +Currently the search tree is not kept in the MIP segment. Therefore if
   1.234 +the search has been terminated, it cannot be continued.
   1.235 +
   1.236 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   1.237 +
   1.238 +\newpage
   1.239 +
   1.240 +\section{Problem creating and modifying routines}
   1.241 +
   1.242 +\subsection{glp\_create\_prob---create problem object}
   1.243 +
   1.244 +\subsubsection*{Synopsis}
   1.245 +
   1.246 +\begin{verbatim}
   1.247 +glp_prob *glp_create_prob(void);
   1.248 +\end{verbatim}
   1.249 +
   1.250 +\subsubsection*{Description}
   1.251 +
   1.252 +The routine \verb|glp_create_prob| creates a new problem object, which
   1.253 +initially is ``empty'', i.e. has no rows and columns.
   1.254 +
   1.255 +\subsubsection*{Returns}
   1.256 +
   1.257 +The routine returns a pointer to the created object, which should be
   1.258 +used in any subsequent operations on this object.
   1.259 +
   1.260 +\subsection{glp\_set\_prob\_name---assign (change) problem name}
   1.261 +
   1.262 +\subsubsection*{Synopsis}
   1.263 +
   1.264 +\begin{verbatim}
   1.265 +void glp_set_prob_name(glp_prob *lp, const char *name);
   1.266 +\end{verbatim}
   1.267 +
   1.268 +\subsubsection*{Description}
   1.269 +
   1.270 +The routine \verb|glp_set_prob_name| assigns a given symbolic
   1.271 +\verb|name| (1 up to 255 characters) to the specified problem object.
   1.272 +
   1.273 +If the parameter \verb|name| is \verb|NULL| or empty string, the routine
   1.274 +erases an existing symbolic name of the problem object.
   1.275 +
   1.276 +\subsection{glp\_set\_obj\_name---assign (change) objective function
   1.277 +name}
   1.278 +
   1.279 +\subsubsection*{Synopsis}
   1.280 +
   1.281 +\begin{verbatim}
   1.282 +void glp_set_obj_name(glp_prob *lp, const char *name);
   1.283 +\end{verbatim}
   1.284 +
   1.285 +\subsubsection*{Description}
   1.286 +
   1.287 +The routine \verb|glp_set_obj_name| assigns a given symbolic
   1.288 +\verb|name| (1 up to 255 characters) to the objective function of the
   1.289 +specified problem object.
   1.290 +
   1.291 +If the parameter \verb|name| is \verb|NULL| or empty string, the routine
   1.292 +erases an existing symbolic name of the objective function.
   1.293 +
   1.294 +\subsection{glp\_set\_obj\_dir---set (change) optimization direction\\
   1.295 +flag}
   1.296 +
   1.297 +\subsubsection*{Synopsis}
   1.298 +
   1.299 +\begin{verbatim}
   1.300 +void glp_set_obj_dir(glp_prob *lp, int dir);
   1.301 +\end{verbatim}
   1.302 +
   1.303 +\subsubsection*{Description}
   1.304 +
   1.305 +The routine \verb|glp_set_obj_dir| sets (changes) the optimization
   1.306 +direction flag (i.e. ``sense'' of the objective function) as specified
   1.307 +by the parameter \verb|dir|:
   1.308 +
   1.309 +\begin{tabular}{@{}ll}
   1.310 +\verb|GLP_MIN| & minimization; \\
   1.311 +\verb|GLP_MAX| & maximization. \\
   1.312 +\end{tabular}
   1.313 +
   1.314 +\noindent
   1.315 +(Note that by default the problem is minimization.)
   1.316 +
   1.317 +\subsection{glp\_add\_rows---add new rows to problem object}
   1.318 +
   1.319 +\subsubsection*{Synopsis}
   1.320 +
   1.321 +\begin{verbatim}
   1.322 +int glp_add_rows(glp_prob *lp, int nrs);
   1.323 +\end{verbatim}
   1.324 +
   1.325 +\subsubsection*{Description}
   1.326 +
   1.327 +The routine \verb|glp_add_rows| adds \verb|nrs| rows (constraints) to
   1.328 +the specified problem object. New rows are always added to the end of
   1.329 +the row list, so the ordinal numbers of existing rows are not changed.
   1.330 +
   1.331 +Being added each new row is initially free (unbounded) and has empty
   1.332 +list of the constraint coefficients.
   1.333 +
   1.334 +\subsubsection*{Returns}
   1.335 +
   1.336 +The routine \verb|glp_add_rows| returns the ordinal number of the first
   1.337 +new row added to the problem object.
   1.338 +
   1.339 +\newpage
   1.340 +
   1.341 +\subsection{glp\_add\_cols---add new columns to problem object}
   1.342 +
   1.343 +\subsubsection*{Synopsis}
   1.344 +
   1.345 +\begin{verbatim}
   1.346 +int glp_add_cols(glp_prob *lp, int ncs);
   1.347 +\end{verbatim}
   1.348 +
   1.349 +\subsubsection*{Description}
   1.350 +
   1.351 +The routine \verb|glp_add_cols| adds \verb|ncs| columns (structural
   1.352 +variables) to the specified problem object. New columns are always added
   1.353 +to the end of the column list, so the ordinal numbers of existing
   1.354 +columns are not changed.
   1.355 +
   1.356 +Being added each new column is initially fixed at zero and has empty
   1.357 +list of the constraint coefficients.
   1.358 +
   1.359 +\subsubsection*{Returns}
   1.360 +
   1.361 +The routine \verb|glp_add_cols| returns the ordinal number of the first
   1.362 +new column added to the problem object.
   1.363 +
   1.364 +\subsection{glp\_set\_row\_name---assign (change) row name}
   1.365 +
   1.366 +\subsubsection*{Synopsis}
   1.367 +
   1.368 +\begin{verbatim}
   1.369 +void glp_set_row_name(glp_prob *lp, int i, const char *name);
   1.370 +\end{verbatim}
   1.371 +
   1.372 +\subsubsection*{Description}
   1.373 +
   1.374 +The routine \verb|glp_set_row_name| assigns a given symbolic
   1.375 +\verb|name| (1 up to 255 characters) to \verb|i|-th row (auxiliary
   1.376 +variable) of the specified problem object.
   1.377 +
   1.378 +If the parameter \verb|name| is \verb|NULL| or empty string, the routine
   1.379 +erases an existing name of $i$-th row.
   1.380 +
   1.381 +\subsection{glp\_set\_col\_name---assign (change) column name}
   1.382 +
   1.383 +\subsubsection*{Synopsis}
   1.384 +
   1.385 +\begin{verbatim}
   1.386 +void glp_set_col_name(glp_prob *lp, int j, const char *name);
   1.387 +\end{verbatim}
   1.388 +
   1.389 +\subsubsection*{Description}
   1.390 +
   1.391 +The routine \verb|glp_set_col_name| assigns a given symbolic
   1.392 +\verb|name| (1 up to 255 characters) to \verb|j|-th column (structural
   1.393 +variable) of the specified problem object.
   1.394 +
   1.395 +If the parameter \verb|name| is \verb|NULL| or empty string, the routine
   1.396 +erases an existing name of $j$-th column.
   1.397 +
   1.398 +\subsection{glp\_set\_row\_bnds---set (change) row bounds}
   1.399 +
   1.400 +\subsubsection*{Synopsis}
   1.401 +
   1.402 +\begin{verbatim}
   1.403 +void glp_set_row_bnds(glp_prob *lp, int i, int type,
   1.404 +      double lb, double ub);
   1.405 +\end{verbatim}
   1.406 +
   1.407 +\subsubsection*{Description}
   1.408 +
   1.409 +The routine \verb|glp_set_row_bnds| sets (changes) the type and bounds
   1.410 +of \verb|i|-th row (auxiliary variable) of the specified problem object.
   1.411 +
   1.412 +The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type,
   1.413 +lower bound, and upper bound, respectively, as follows:
   1.414 +
   1.415 +\begin{center}
   1.416 +\begin{tabular}{cr@{}c@{}ll}
   1.417 +Type & \multicolumn{3}{c}{Bounds} & Comment \\
   1.418 +\hline
   1.419 +\verb|GLP_FR| & $-\infty <$ &$\ x\ $& $< +\infty$
   1.420 +   & Free (unbounded) variable \\
   1.421 +\verb|GLP_LO| & $lb \leq$ &$\ x\ $& $< +\infty$
   1.422 +   & Variable with lower bound \\
   1.423 +\verb|GLP_UP| & $-\infty <$ &$\ x\ $& $\leq ub$
   1.424 +   & Variable with upper bound \\
   1.425 +\verb|GLP_DB| & $lb \leq$ &$\ x\ $& $\leq ub$
   1.426 +   & Double-bounded variable \\
   1.427 +\verb|GLP_FX| & $lb =$ &$\ x\ $& $= ub$
   1.428 +   & Fixed variable \\
   1.429 +\end{tabular}
   1.430 +\end{center}
   1.431 +
   1.432 +\noindent
   1.433 +where $x$ is the auxiliary variable associated with $i$-th row.
   1.434 +
   1.435 +If the row has no lower bound, the parameter \verb|lb| is ignored. If
   1.436 +the row has no upper bound, the parameter \verb|ub| is ignored. If the
   1.437 +row is an equality constraint (i.e. the corresponding auxiliary variable
   1.438 +is of fixed type), only the parameter \verb|lb| is used while the
   1.439 +parameter \verb|ub| is ignored.
   1.440 +
   1.441 +Being added to the problem object each row is initially free, i.e. its
   1.442 +type is \verb|GLP_FR|.
   1.443 +
   1.444 +\newpage
   1.445 +
   1.446 +\subsection{glp\_set\_col\_bnds---set (change) column bounds}
   1.447 +
   1.448 +\subsubsection*{Synopsis}
   1.449 +
   1.450 +\begin{verbatim}
   1.451 +void glp_set_col_bnds(glp_prob *lp, int j, int type,
   1.452 +      double lb, double ub);
   1.453 +\end{verbatim}
   1.454 +
   1.455 +\subsubsection*{Description}
   1.456 +
   1.457 +The routine \verb|glp_set_col_bnds| sets (changes) the type and bounds
   1.458 +of \verb|j|-th column (structural variable) of the specified problem
   1.459 +object.
   1.460 +
   1.461 +The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type,
   1.462 +lower bound, and upper bound, respectively, as follows:
   1.463 +
   1.464 +\begin{center}
   1.465 +\begin{tabular}{cr@{}c@{}ll}
   1.466 +Type & \multicolumn{3}{c}{Bounds} & Comment \\
   1.467 +\hline
   1.468 +\verb|GLP_FR| & $-\infty <$ &$\ x\ $& $< +\infty$
   1.469 +   & Free (unbounded) variable \\
   1.470 +\verb|GLP_LO| & $lb \leq$ &$\ x\ $& $< +\infty$
   1.471 +   & Variable with lower bound \\
   1.472 +\verb|GLP_UP| & $-\infty <$ &$\ x\ $& $\leq ub$
   1.473 +   & Variable with upper bound \\
   1.474 +\verb|GLP_DB| & $lb \leq$ &$\ x\ $& $\leq ub$
   1.475 +   & Double-bounded variable \\
   1.476 +\verb|GLP_FX| & $lb =$ &$\ x\ $& $= ub$
   1.477 +   & Fixed variable \\
   1.478 +\end{tabular}
   1.479 +\end{center}
   1.480 +
   1.481 +\noindent
   1.482 +where $x$ is the structural variable associated with $j$-th column.
   1.483 +
   1.484 +If the column has no lower bound, the parameter \verb|lb| is ignored.
   1.485 +If the column has no upper bound, the parameter \verb|ub| is ignored.
   1.486 +If the column is of fixed type, only the parameter \verb|lb| is used
   1.487 +while the parameter \verb|ub| is ignored.
   1.488 +
   1.489 +Being added to the problem object each column is initially fixed at
   1.490 +zero, i.e. its type is \verb|GLP_FX| and both bounds are 0.
   1.491 +
   1.492 +\subsection{glp\_set\_obj\_coef---set (change) objective coefficient
   1.493 +or constant term}
   1.494 +
   1.495 +\subsubsection*{Synopsis}
   1.496 +
   1.497 +\begin{verbatim}
   1.498 +void glp_set_obj_coef(glp_prob *lp, int j, double coef);
   1.499 +\end{verbatim}
   1.500 +
   1.501 +\subsubsection*{Description}
   1.502 +
   1.503 +The routine \verb|glp_set_obj_coef| sets (changes) the objective
   1.504 +coefficient at \verb|j|-th column (structural variable). A new value of
   1.505 +the objective coefficient is specified by the parameter \verb|coef|.
   1.506 +
   1.507 +If the parameter \verb|j| is 0, the routine sets (changes) the constant
   1.508 +term (``shift'') of the objective function.
   1.509 +
   1.510 +\subsection{glp\_set\_mat\_row---set (replace) row of the constraint
   1.511 +matrix}
   1.512 +
   1.513 +\subsubsection*{Synopsis}
   1.514 +
   1.515 +\begin{verbatim}
   1.516 +void glp_set_mat_row(glp_prob *lp, int i, int len,
   1.517 +      const int ind[], const double val[]);
   1.518 +\end{verbatim}
   1.519 +
   1.520 +\subsubsection*{Description}
   1.521 +
   1.522 +The routine \verb|glp_set_mat_row| stores (replaces) the contents of
   1.523 +\verb|i|-th row of the constraint matrix of the specified problem
   1.524 +object.
   1.525 +
   1.526 +Column indices and numerical values of new row elements must be placed
   1.527 +in locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
   1.528 +\dots, \verb|val[len]|, respectively, where $0 \leq$ \verb|len| $\leq n$
   1.529 +is the new length of $i$-th row, $n$ is the current number of columns in
   1.530 +the problem object. Elements with identical column indices are not
   1.531 +allowed. Zero elements are allowed, but they are not stored in the
   1.532 +constraint matrix.
   1.533 +
   1.534 +If the parameter \verb|len| is 0, the parameters \verb|ind| and/or
   1.535 +\verb|val| can be specified as \verb|NULL|.
   1.536 +
   1.537 +\subsection{glp\_set\_mat\_col---set (replace) column of the
   1.538 +constr\-aint matrix}
   1.539 +
   1.540 +\subsubsection*{Synopsis}
   1.541 +
   1.542 +\begin{verbatim}
   1.543 +void glp_set_mat_col(glp_prob *lp, int j, int len,
   1.544 +      const int ind[], const double val[]);
   1.545 +\end{verbatim}
   1.546 +
   1.547 +\subsubsection*{Description}
   1.548 +
   1.549 +The routine \verb|glp_set_mat_col| stores (replaces) the contents of
   1.550 +\verb|j|-th column of the constraint matrix of the specified problem
   1.551 +object.
   1.552 +
   1.553 +Row indices and numerical values of new column elements must be placed
   1.554 +in locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
   1.555 +\dots, \verb|val[len]|, respectively, where $0 \leq$ \verb|len| $\leq m$
   1.556 +is the new length of $j$-th column, $m$ is the current number of rows in
   1.557 +the problem object. Elements with identical row indices are not allowed.
   1.558 +Zero elements are allowed, but they are not stored in the constraint
   1.559 +matrix.
   1.560 +
   1.561 +If the parameter \verb|len| is 0, the parameters \verb|ind| and/or
   1.562 +\verb|val| can be specified as \verb|NULL|.
   1.563 +
   1.564 +\subsection{glp\_load\_matrix---load (replace) the whole constraint
   1.565 +matrix}
   1.566 +
   1.567 +\subsubsection*{Synopsis}
   1.568 +
   1.569 +\begin{verbatim}
   1.570 +void glp_load_matrix(glp_prob *lp, int ne, const int ia[],
   1.571 +      const int ja[], const double ar[]);
   1.572 +\end{verbatim}
   1.573 +
   1.574 +\subsubsection*{Description}
   1.575 +
   1.576 +The routine \verb|glp_load_matrix| loads the constraint matrix passed
   1.577 +in  the arrays \verb|ia|, \verb|ja|, and \verb|ar| into the specified
   1.578 +problem object. Before loading the current contents of the constraint
   1.579 +matrix is destroyed.
   1.580 +
   1.581 +Constraint coefficients (elements of the constraint matrix) must be
   1.582 +specified as triplets (\verb|ia[k]|, \verb|ja[k]|, \verb|ar[k]|) for
   1.583 +$k=1,\dots,ne$, where \verb|ia[k]| is the row index, \verb|ja[k]| is
   1.584 +the column index, and \verb|ar[k]| is a numeric value of corresponding
   1.585 +constraint coefficient. The parameter \verb|ne| specifies the total
   1.586 +number of (non-zero) elements in the matrix to be loaded. Coefficients
   1.587 +with identical indices are not allowed. Zero coefficients are allowed,
   1.588 +however, they are not stored in the constraint matrix.
   1.589 +
   1.590 +If the parameter \verb|ne| is 0, the parameters \verb|ia|, \verb|ja|,
   1.591 +and/or \verb|ar| can be specified as \verb|NULL|.
   1.592 +
   1.593 +\subsection{glp\_check\_dup---check for duplicate elements in sparse
   1.594 +matrix}
   1.595 +
   1.596 +\subsubsection*{Synopsis}
   1.597 +
   1.598 +\begin{verbatim}
   1.599 +int glp_check_dup(int m, int n, int ne, const int ia[],
   1.600 +   const int ja[]);
   1.601 +\end{verbatim}
   1.602 +
   1.603 +\subsubsection*{Description}
   1.604 +
   1.605 +The routine \verb|glp_check_dup checks| for duplicate elements (that
   1.606 +is, elements with identical indices) in a sparse matrix specified in
   1.607 +the coordinate format.
   1.608 +
   1.609 +The parameters $m$ and $n$ specifies, respectively, the number of rows
   1.610 +and columns in the matrix, $m\geq 0$, $n\geq 0$.
   1.611 +
   1.612 +The parameter {\it ne} specifies the number of (structurally) non-zero
   1.613 +elements in the matrix, {\it ne} $\geq 0$.
   1.614 +
   1.615 +Elements of the matrix are specified as doublets $(ia[k],ja[k])$ for
   1.616 +$k=1,\dots,ne$, where $ia[k]$ is a row index, $ja[k]$ is a column index.
   1.617 +
   1.618 +The routine \verb|glp_check_dup| can be used prior to a call to the
   1.619 +routine \verb|glp_load_matrix| to check that the constraint matrix to
   1.620 +be loaded has no duplicate elements.
   1.621 +
   1.622 +\subsubsection*{Returns}
   1.623 +
   1.624 +The routine \verb|glp_check_dup| returns one of the following values:
   1.625 +
   1.626 +\noindent
   1.627 +\begin{tabular}{@{}r@{\ }c@{\ }l@{}}
   1.628 +0&---&the matrix has no duplicate elements;\\
   1.629 +$-k$&---&indices $ia[k]$ or/and $ja[k]$ are out of range;\\
   1.630 +$+k$&---&element $(ia[k],ja[k])$ is duplicate.\\
   1.631 +\end{tabular}
   1.632 +
   1.633 +\subsection{glp\_sort\_matrix---sort elements of the constraint matrix}
   1.634 +
   1.635 +\subsubsection*{Synopsis}
   1.636 +
   1.637 +\begin{verbatim}
   1.638 +void glp_sort_matrix(glp_prob *P);
   1.639 +\end{verbatim}
   1.640 +
   1.641 +\subsubsection*{Description}
   1.642 +
   1.643 +The routine \verb|glp_sort_matrix| sorts elements of the constraint
   1.644 +matrix rebuilding its row and column linked lists. On exit from the
   1.645 +routine the constraint matrix is not changed, however, elements in the
   1.646 +row linked lists become ordered by ascending column indices, and the
   1.647 +elements in the column linked lists become ordered by ascending row
   1.648 +indices.
   1.649 +
   1.650 +\subsection{glp\_del\_rows---delete rows from problem object}
   1.651 +
   1.652 +\subsubsection*{Synopsis}
   1.653 +
   1.654 +\begin{verbatim}
   1.655 +void glp_del_rows(glp_prob *lp, int nrs, const int num[]);
   1.656 +\end{verbatim}
   1.657 +
   1.658 +\subsubsection*{Description}
   1.659 +
   1.660 +The routine \verb|glp_del_rows| deletes rows from the specified problem
   1.661 +ob-\linebreak ject. Ordinal numbers of rows to be deleted should be
   1.662 +placed in locations \verb|num[1]|, \dots, \verb|num[nrs]|, where
   1.663 +${\tt nrs}>0$.
   1.664 +
   1.665 +Note that deleting rows involves changing ordinal numbers of other
   1.666 +rows remaining in the problem object. New ordinal numbers of the
   1.667 +remaining rows are assigned under the assumption that the original
   1.668 +order of rows is not changed. Let, for example, before deletion there
   1.669 +be five rows $a$, $b$, $c$, $d$, $e$ with ordinal numbers 1, 2, 3, 4, 5,
   1.670 +and let rows $b$ and $d$ have been deleted. Then after deletion the
   1.671 +remaining rows $a$, $c$, $e$ are assigned new oridinal numbers 1, 2, 3.
   1.672 +
   1.673 +\subsection{glp\_del\_cols---delete columns from problem object}
   1.674 +
   1.675 +\subsubsection*{Synopsis}
   1.676 +
   1.677 +\begin{verbatim}
   1.678 +void glp_del_cols(glp_prob *lp, int ncs, const int num[]);
   1.679 +\end{verbatim}
   1.680 +
   1.681 +\subsubsection*{Description}
   1.682 +
   1.683 +The routine \verb|glp_del_cols| deletes columns from the specified
   1.684 +problem object. Ordinal numbers of columns to be deleted should be
   1.685 +placed in locations \verb|num[1]|, \dots, \verb|num[ncs]|, where
   1.686 +${\tt ncs}>0$.
   1.687 +
   1.688 +Note that deleting columns involves changing ordinal numbers of other
   1.689 +columns remaining in the problem object. New ordinal numbers of the
   1.690 +remaining columns are assigned under the assumption that the original
   1.691 +order of columns is not changed. Let, for example, before deletion there
   1.692 +be six columns $p$, $q$, $r$, $s$, $t$, $u$ with ordinal numbers 1, 2,
   1.693 +3, 4, 5, 6, and let columns $p$, $q$, $s$ have been deleted. Then after
   1.694 +deletion the remaining columns $r$, $t$, $u$ are assigned new ordinal
   1.695 +numbers 1, 2, 3.
   1.696 +
   1.697 +\subsection{glp\_copy\_prob---copy problem object content}
   1.698 +
   1.699 +\subsubsection*{Synopsis}
   1.700 +
   1.701 +\begin{verbatim}
   1.702 +void glp_copy_prob(glp_prob *dest, glp_prob *prob, int names);
   1.703 +\end{verbatim}
   1.704 +
   1.705 +\subsubsection*{Description}
   1.706 +
   1.707 +The routine \verb|glp_copy_prob| copies the content of the problem
   1.708 +object \verb|prob| to the problem object \verb|dest|.
   1.709 +
   1.710 +The parameter \verb|names| is a flag. If it is \verb|GLP_ON|,
   1.711 +the routine also copies all symbolic names; otherwise, if it is
   1.712 +\verb|GLP_OFF|, no symbolic names are copied.
   1.713 +
   1.714 +\newpage
   1.715 +
   1.716 +\subsection{glp\_erase\_prob---erase problem object content}
   1.717 +
   1.718 +\subsubsection*{Synopsis}
   1.719 +
   1.720 +\begin{verbatim}
   1.721 +void glp_erase_prob(glp_prob *lp);
   1.722 +\end{verbatim}
   1.723 +
   1.724 +\subsubsection*{Description}
   1.725 +
   1.726 +The routine \verb|glp_erase_prob| erases the content of the specified
   1.727 +problem object. The effect of this operation is the same as if the
   1.728 +problem object would be deleted with the routine \verb|glp_delete_prob|
   1.729 +and then created anew with the routine \verb|glp_create_prob|, with the
   1.730 +only exception that the handle (pointer) to the problem object remains
   1.731 +valid.
   1.732 +
   1.733 +\subsection{glp\_delete\_prob---delete problem object}
   1.734 +
   1.735 +\subsubsection*{Synopsis}
   1.736 +
   1.737 +\begin{verbatim}
   1.738 +void glp_delete_prob(glp_prob *lp);
   1.739 +\end{verbatim}
   1.740 +
   1.741 +\subsubsection*{Description}
   1.742 +
   1.743 +The routine \verb|glp_delete_prob| deletes a problem object, which the
   1.744 +parameter \verb|lp| points to, freeing all the memory allocated to this
   1.745 +object.
   1.746 +
   1.747 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   1.748 +
   1.749 +\newpage
   1.750 +
   1.751 +\section{Problem retrieving routines}
   1.752 +
   1.753 +\subsection{glp\_get\_prob\_name---retrieve problem name}
   1.754 +
   1.755 +\subsubsection*{Synopsis}
   1.756 +
   1.757 +\begin{verbatim}
   1.758 +const char *glp_get_prob_name(glp_prob *lp);
   1.759 +\end{verbatim}
   1.760 +
   1.761 +\subsubsection*{Returns}
   1.762 +
   1.763 +The routine \verb|glp_get_prob_name| returns a pointer to an internal
   1.764 +buffer, which contains symbolic name of the problem. However, if the
   1.765 +problem has no assigned name, the routine returns \verb|NULL|.
   1.766 +
   1.767 +\subsection{glp\_get\_obj\_name---retrieve objective function name}
   1.768 +
   1.769 +\subsubsection*{Synopsis}
   1.770 +
   1.771 +\begin{verbatim}
   1.772 +const char *glp_get_obj_name(glp_prob *lp);
   1.773 +\end{verbatim}
   1.774 +
   1.775 +\subsubsection*{Returns}
   1.776 +
   1.777 +The routine \verb|glp_get_obj_name| returns a pointer to an internal
   1.778 +buffer, which contains symbolic name assigned to the objective
   1.779 +function. However, if the objective function has no assigned name, the
   1.780 +routine returns \verb|NULL|.
   1.781 +
   1.782 +\subsection{glp\_get\_obj\_dir---retrieve optimization direction flag}
   1.783 +
   1.784 +\subsubsection*{Synopsis}
   1.785 +
   1.786 +\begin{verbatim}
   1.787 +int glp_get_obj_dir(glp_prob *lp);
   1.788 +\end{verbatim}
   1.789 +
   1.790 +\subsubsection*{Returns}
   1.791 +
   1.792 +The routine \verb|glp_get_obj_dir| returns the optimization direction
   1.793 +flag (i.e. ``sense'' of the objective function):
   1.794 +
   1.795 +\begin{tabular}{@{}ll}
   1.796 +\verb|GLP_MIN| & minimization; \\
   1.797 +\verb|GLP_MAX| & maximization. \\
   1.798 +\end{tabular}
   1.799 +
   1.800 +\pagebreak
   1.801 +
   1.802 +\subsection{glp\_get\_num\_rows---retrieve number of rows}
   1.803 +
   1.804 +\subsubsection*{Synopsis}
   1.805 +
   1.806 +\begin{verbatim}
   1.807 +int glp_get_num_rows(glp_prob *lp);
   1.808 +\end{verbatim}
   1.809 +
   1.810 +\subsubsection*{Returns}
   1.811 +
   1.812 +The routine \verb|glp_get_num_rows| returns the current number of rows
   1.813 +in the specified problem object.
   1.814 +
   1.815 +\subsection{glp\_get\_num\_cols---retrieve number of columns}
   1.816 +
   1.817 +\subsubsection*{Synopsis}
   1.818 +
   1.819 +\begin{verbatim}
   1.820 +int glp_get_num_cols(glp_prob *lp);
   1.821 +\end{verbatim}
   1.822 +
   1.823 +\subsubsection*{Returns}
   1.824 +
   1.825 +The routine \verb|glp_get_num_cols| returns the current number of
   1.826 +columns the specified problem object.
   1.827 +
   1.828 +\subsection{glp\_get\_row\_name---retrieve row name}
   1.829 +
   1.830 +\subsubsection*{Synopsis}
   1.831 +
   1.832 +\begin{verbatim}
   1.833 +const char *glp_get_row_name(glp_prob *lp, int i);
   1.834 +\end{verbatim}
   1.835 +
   1.836 +\subsubsection*{Returns}
   1.837 +
   1.838 +The routine \verb|glp_get_row_name| returns a pointer to an internal
   1.839 +buffer, which contains a symbolic name assigned to \verb|i|-th row.
   1.840 +However, if the row has no assigned name, the routine returns
   1.841 +\verb|NULL|.
   1.842 +
   1.843 +\subsection{glp\_get\_col\_name---retrieve column name}
   1.844 +
   1.845 +\subsubsection*{Synopsis}
   1.846 +
   1.847 +\begin{verbatim}
   1.848 +const char *glp_get_col_name(glp_prob *lp, int j);
   1.849 +\end{verbatim}
   1.850 +
   1.851 +\subsubsection*{Returns}
   1.852 +
   1.853 +The routine \verb|glp_get_col_name| returns a pointer to an internal
   1.854 +buffer, which contains a symbolic name assigned to \verb|j|-th column.
   1.855 +However, if the column has no assigned name, the routine returns
   1.856 +\verb|NULL|.
   1.857 +
   1.858 +\subsection{glp\_get\_row\_type---retrieve row type}
   1.859 +
   1.860 +\subsubsection*{Synopsis}
   1.861 +
   1.862 +\begin{verbatim}
   1.863 +int glp_get_row_type(glp_prob *lp, int i);
   1.864 +\end{verbatim}
   1.865 +
   1.866 +\subsubsection*{Returns}
   1.867 +
   1.868 +The routine \verb|glp_get_row_type| returns the type of \verb|i|-th
   1.869 +row, i.e. the type of corresponding auxiliary variable, as follows:
   1.870 +
   1.871 +\begin{tabular}{@{}ll}
   1.872 +\verb|GLP_FR| & free (unbounded) variable; \\
   1.873 +\verb|GLP_LO| & variable with lower bound; \\
   1.874 +\verb|GLP_UP| & variable with upper bound; \\
   1.875 +\verb|GLP_DB| & double-bounded variable; \\
   1.876 +\verb|GLP_FX| & fixed variable. \\
   1.877 +\end{tabular}
   1.878 +
   1.879 +\subsection{glp\_get\_row\_lb---retrieve row lower bound}
   1.880 +
   1.881 +\subsubsection*{Synopsis}
   1.882 +
   1.883 +\begin{verbatim}
   1.884 +double glp_get_row_lb(glp_prob *lp, int i);
   1.885 +\end{verbatim}
   1.886 +
   1.887 +\subsubsection*{Returns}
   1.888 +
   1.889 +The routine \verb|glp_get_row_lb| returns the lower bound of
   1.890 +\verb|i|-th row, i.e. the lower bound of corresponding auxiliary
   1.891 +variable. However, if the row has no lower bound, the routine returns
   1.892 +\verb|-DBL_MAX|.
   1.893 +
   1.894 +\subsection{glp\_get\_row\_ub---retrieve row upper bound}
   1.895 +
   1.896 +\subsubsection*{Synopsis}
   1.897 +
   1.898 +\begin{verbatim}
   1.899 +double glp_get_row_ub(glp_prob *lp, int i);
   1.900 +\end{verbatim}
   1.901 +
   1.902 +\subsubsection*{Returns}
   1.903 +
   1.904 +The routine \verb|glp_get_row_ub| returns the upper bound of
   1.905 +\verb|i|-th row, i.e. the upper bound of corresponding auxiliary
   1.906 +variable. However, if the row has no upper bound, the routine returns
   1.907 +\verb|+DBL_MAX|.
   1.908 +
   1.909 +\subsection{glp\_get\_col\_type---retrieve column type}
   1.910 +
   1.911 +\subsubsection*{Synopsis}
   1.912 +
   1.913 +\begin{verbatim}
   1.914 +int glp_get_col_type(glp_prob *lp, int j);
   1.915 +\end{verbatim}
   1.916 +
   1.917 +\subsubsection*{Returns}
   1.918 +
   1.919 +The routine \verb|glp_get_col_type| returns the type of \verb|j|-th
   1.920 +column, i.e. the type of corresponding structural variable, as follows:
   1.921 +
   1.922 +\begin{tabular}{@{}ll}
   1.923 +\verb|GLP_FR| & free (unbounded) variable; \\
   1.924 +\verb|GLP_LO| & variable with lower bound; \\
   1.925 +\verb|GLP_UP| & variable with upper bound; \\
   1.926 +\verb|GLP_DB| & double-bounded variable; \\
   1.927 +\verb|GLP_FX| & fixed variable. \\
   1.928 +\end{tabular}
   1.929 +
   1.930 +\subsection{glp\_get\_col\_lb---retrieve column lower bound}
   1.931 +
   1.932 +\subsubsection*{Synopsis}
   1.933 +
   1.934 +\begin{verbatim}
   1.935 +double glp_get_col_lb(glp_prob *lp, int j);
   1.936 +\end{verbatim}
   1.937 +
   1.938 +\subsubsection*{Returns}
   1.939 +
   1.940 +The routine \verb|glp_get_col_lb| returns the lower bound of
   1.941 +\verb|j|-th column, i.e. the lower bound of corresponding structural
   1.942 +variable. However, if the column has no lower bound, the routine returns
   1.943 +\verb|-DBL_MAX|.
   1.944 +
   1.945 +\subsection{glp\_get\_col\_ub---retrieve column upper bound}
   1.946 +
   1.947 +\subsubsection*{Synopsis}
   1.948 +
   1.949 +\begin{verbatim}
   1.950 +double glp_get_col_ub(glp_prob *lp, int j);
   1.951 +\end{verbatim}
   1.952 +
   1.953 +\subsubsection*{Returns}
   1.954 +
   1.955 +The routine \verb|glp_get_col_ub| returns the upper bound of
   1.956 +\verb|j|-th column, i.e. the upper bound of corresponding structural
   1.957 +variable. However, if the column has no upper bound, the routine returns
   1.958 +\verb|+DBL_MAX|.
   1.959 +
   1.960 +\subsection{glp\_get\_obj\_coef---retrieve objective coefficient or\\
   1.961 +constant term}
   1.962 +
   1.963 +\subsubsection*{Synopsis}
   1.964 +
   1.965 +\begin{verbatim}
   1.966 +double glp_get_obj_coef(glp_prob *lp, int j);
   1.967 +\end{verbatim}
   1.968 +
   1.969 +\subsubsection*{Returns}
   1.970 +
   1.971 +The routine \verb|glp_get_obj_coef| returns the objective coefficient
   1.972 +at \verb|j|-th structural variable (column).
   1.973 +
   1.974 +If the parameter \verb|j| is 0, the routine returns the constant term
   1.975 +(``shift'') of the objective function.
   1.976 +
   1.977 +\subsection{glp\_get\_num\_nz---retrieve number of constraint
   1.978 +coefficients}
   1.979 +
   1.980 +\subsubsection*{Synopsis}
   1.981 +
   1.982 +\begin{verbatim}
   1.983 +int glp_get_num_nz(glp_prob *lp);
   1.984 +\end{verbatim}
   1.985 +
   1.986 +\subsubsection*{Returns}
   1.987 +
   1.988 +The routine \verb|glp_get_num_nz| returns the number of non-zero
   1.989 +elements in the constraint matrix of the specified problem object.
   1.990 +
   1.991 +\subsection{glp\_get\_mat\_row---retrieve row of the constraint
   1.992 +matrix}
   1.993 +
   1.994 +\subsubsection*{Synopsis}
   1.995 +
   1.996 +\begin{verbatim}
   1.997 +int glp_get_mat_row(glp_prob *lp, int i, int ind[],
   1.998 +      double val[]);
   1.999 +\end{verbatim}
  1.1000 +
  1.1001 +\subsubsection*{Description}
  1.1002 +
  1.1003 +The routine \verb|glp_get_mat_row| scans (non-zero) elements of
  1.1004 +\verb|i|-th row of the constraint matrix of the specified problem object
  1.1005 +and stores their column indices and numeric values to locations
  1.1006 +\verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
  1.1007 +\verb|val[len]|, respectively, where $0\leq{\tt len}\leq n$ is the
  1.1008 +number of elements in $i$-th row, $n$ is the number of columns.
  1.1009 +
  1.1010 +The parameter \verb|ind| and/or \verb|val| can be specified as
  1.1011 +\verb|NULL|, in which case corresponding information is not stored.
  1.1012 +
  1.1013 +\subsubsection*{Returns}
  1.1014 +
  1.1015 +The routine \verb|glp_get_mat_row| returns the length \verb|len|, i.e.
  1.1016 +the number of (non-zero) elements in \verb|i|-th row.
  1.1017 +
  1.1018 +\subsection{glp\_get\_mat\_col---retrieve column of the constraint\\
  1.1019 +matrix}
  1.1020 +
  1.1021 +\subsubsection*{Synopsis}
  1.1022 +
  1.1023 +\begin{verbatim}
  1.1024 +int glp_get_mat_col(glp_prob *lp, int j, int ind[],
  1.1025 +      double val[]);
  1.1026 +\end{verbatim}
  1.1027 +
  1.1028 +\subsubsection*{Description}
  1.1029 +
  1.1030 +The routine \verb|glp_get_mat_col| scans (non-zero) elements of
  1.1031 +\verb|j|-th column of the constraint matrix of the specified problem
  1.1032 +object and stores their row indices and numeric values to locations
  1.1033 +\verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
  1.1034 +\verb|val[len]|, respectively, where $0\leq{\tt len}\leq m$ is the
  1.1035 +number of elements in $j$-th column, $m$ is the number of rows.
  1.1036 +
  1.1037 +The parameter \verb|ind| and/or \verb|val| can be specified as
  1.1038 +\verb|NULL|, in which case corresponding information is not stored.
  1.1039 +
  1.1040 +\subsubsection*{Returns}
  1.1041 +
  1.1042 +The routine \verb|glp_get_mat_col| returns the length \verb|len|, i.e.
  1.1043 +the number of (non-zero) elements in \verb|j|-th column.
  1.1044 +
  1.1045 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1.1046 +
  1.1047 +\newpage
  1.1048 +
  1.1049 +\section{Row and column searching routines}
  1.1050 +
  1.1051 +\subsection{glp\_create\_index---create the name index}
  1.1052 +
  1.1053 +\subsubsection*{Synopsis}
  1.1054 +
  1.1055 +\begin{verbatim}
  1.1056 +void glp_create_index(glp_prob *lp);
  1.1057 +\end{verbatim}
  1.1058 +
  1.1059 +\subsubsection*{Description}
  1.1060 +
  1.1061 +The routine \verb|glp_create_index| creates the name index for the
  1.1062 +specified problem object. The name index is an auxiliary data structure,
  1.1063 +which is intended to quickly (i.e. for logarithmic time) find rows and
  1.1064 +columns by their names.
  1.1065 +
  1.1066 +This routine can be called at any time. If the name index already
  1.1067 +exists, the routine does nothing.
  1.1068 +
  1.1069 +\subsection{glp\_find\_row---find row by its name}
  1.1070 +
  1.1071 +\subsubsection*{Synopsis}
  1.1072 +
  1.1073 +\begin{verbatim}
  1.1074 +int glp_find_row(glp_prob *lp, const char *name);
  1.1075 +\end{verbatim}
  1.1076 +
  1.1077 +\subsubsection*{Returns}
  1.1078 +
  1.1079 +The routine \verb|glp_find_row| returns the ordinal number of a row,
  1.1080 +which is assigned (by the routine \verb|glp_set_row_name|) the specified
  1.1081 +symbolic \verb|name|. If no such row exists, the routine returns 0.
  1.1082 +
  1.1083 +\subsection{glp\_find\_col---find column by its name}
  1.1084 +
  1.1085 +\subsubsection*{Synopsis}
  1.1086 +
  1.1087 +\begin{verbatim}
  1.1088 +int glp_find_col(glp_prob *lp, const char *name);
  1.1089 +\end{verbatim}
  1.1090 +
  1.1091 +\subsubsection*{Returns}
  1.1092 +
  1.1093 +The routine \verb|glp_find_col| returns the ordinal number of a column,
  1.1094 +which is assigned (by the routine \verb|glp_set_col_name|) the specified
  1.1095 +symbolic \verb|name|. If no such column exists, the routine returns 0.
  1.1096 +
  1.1097 +\subsection{glp\_delete\_index---delete the name index}
  1.1098 +
  1.1099 +\subsubsection*{Synopsis}
  1.1100 +
  1.1101 +\begin{verbatim}
  1.1102 +void glp_delete_index(glp_prob *lp);
  1.1103 +\end{verbatim}
  1.1104 +
  1.1105 +\subsubsection*{Description}
  1.1106 +
  1.1107 +The routine \verb|glp_delete_index| deletes the name index previously
  1.1108 +created by the routine \verb|glp_create_index| and frees the memory
  1.1109 +allocated to this auxiliary data structure.
  1.1110 +
  1.1111 +This routine can be called at any time. If the name index does not
  1.1112 +exist, the routine does nothing.
  1.1113 +
  1.1114 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1.1115 +
  1.1116 +\newpage
  1.1117 +
  1.1118 +\section{Problem scaling routines}
  1.1119 +
  1.1120 +\subsection{Background}
  1.1121 +
  1.1122 +In GLPK the {\it scaling} means a linear transformation applied to the
  1.1123 +constraint matrix to improve its numerical properties.\footnote{In many
  1.1124 +cases a proper scaling allows making the constraint matrix to be better
  1.1125 +conditioned, i.e. decreasing its condition number, that makes
  1.1126 +computations numerically more stable.}
  1.1127 +
  1.1128 +The main equality is the following:
  1.1129 +$$\widetilde{A}=RAS,\eqno(2.1)$$
  1.1130 +where $A=(a_{ij})$ is the original constraint matrix, $R=(r_{ii})>0$ is
  1.1131 +a diagonal matrix used to scale rows (constraints), $S=(s_{jj})>0$ is a
  1.1132 +diagonal matrix used to scale columns (variables), $\widetilde{A}$ is
  1.1133 +the scaled constraint matrix.
  1.1134 +
  1.1135 +From (2.1) it follows that in the {\it scaled} problem instance each
  1.1136 +original constraint coefficient $a_{ij}$ is replaced by corresponding
  1.1137 +scaled constraint coefficient:
  1.1138 +$$\widetilde{a}_{ij}=r_{ii}a_{ij}s_{jj}.\eqno(2.2)$$
  1.1139 +
  1.1140 +Note that the scaling is performed internally and therefore
  1.1141 +transparently to the user. This means that on API level the user always
  1.1142 +deal with unscaled data.
  1.1143 +
  1.1144 +Scale factors $r_{ii}$ and $s_{jj}$ can be set or changed at any time
  1.1145 +either directly by the application program in a problem specific way
  1.1146 +(with the routines \verb|glp_set_rii| and \verb|glp_set_sjj|), or by
  1.1147 +some API routines intended for automatic scaling.
  1.1148 +
  1.1149 +\subsection{glp\_set\_rii---set (change) row scale factor}
  1.1150 +
  1.1151 +\subsubsection*{Synopsis}
  1.1152 +
  1.1153 +\begin{verbatim}
  1.1154 +void glp_set_rii(glp_prob *lp, int i, double rii);
  1.1155 +\end{verbatim}
  1.1156 +
  1.1157 +\subsubsection*{Description}
  1.1158 +
  1.1159 +The routine \verb|glp_set_rii| sets (changes) the scale factor $r_{ii}$
  1.1160 +for $i$-th row of the specified problem object.
  1.1161 +
  1.1162 +\subsection{glp\_set\_sjj---set (change) column scale factor}
  1.1163 +
  1.1164 +\subsubsection*{Synopsis}
  1.1165 +
  1.1166 +\begin{verbatim}
  1.1167 +void glp_set_sjj(glp_prob *lp, int j, double sjj);
  1.1168 +\end{verbatim}
  1.1169 +
  1.1170 +\subsubsection*{Description}
  1.1171 +
  1.1172 +The routine \verb|glp_set_sjj| sets (changes) the scale factor $s_{jj}$
  1.1173 +for $j$-th column of the specified problem object.
  1.1174 +
  1.1175 +\subsection{glp\_get\_rii---retrieve row scale factor}
  1.1176 +
  1.1177 +\subsubsection*{Synopsis}
  1.1178 +
  1.1179 +\begin{verbatim}
  1.1180 +double glp_get_rii(glp_prob *lp, int i);
  1.1181 +\end{verbatim}
  1.1182 +
  1.1183 +\subsubsection*{Returns}
  1.1184 +
  1.1185 +The routine \verb|glp_get_rii| returns current scale factor $r_{ii}$ for
  1.1186 +$i$-th row of the specified problem object.
  1.1187 +
  1.1188 +\subsection{glp\_get\_sjj---retrieve column scale factor}
  1.1189 +
  1.1190 +\subsubsection*{Synopsis}
  1.1191 +
  1.1192 +\begin{verbatim}
  1.1193 +double glp_get_sjj(glp_prob *lp, int j);
  1.1194 +\end{verbatim}
  1.1195 +
  1.1196 +\subsubsection*{Returns}
  1.1197 +
  1.1198 +The routine \verb|glp_get_sjj| returns current scale factor $s_{jj}$ for
  1.1199 +$j$-th column of the specified problem object.
  1.1200 +
  1.1201 +\subsection{glp\_scale\_prob---scale problem data}
  1.1202 +
  1.1203 +\subsubsection*{Synopsis}
  1.1204 +
  1.1205 +\begin{verbatim}
  1.1206 +void glp_scale_prob(glp_prob *lp, int flags);
  1.1207 +\end{verbatim}
  1.1208 +
  1.1209 +\subsubsection*{Description}
  1.1210 +
  1.1211 +The routine \verb|glp_scale_prob| performs automatic scaling of problem
  1.1212 +data for the specified problem object.
  1.1213 +
  1.1214 +The parameter \verb|flags| specifies scaling options used by the
  1.1215 +routine. The options can be combined with the bitwise OR operator and
  1.1216 +may be the following:
  1.1217 +
  1.1218 +\begin{tabular}{@{}ll}
  1.1219 +\verb|GLP_SF_GM| & perform geometric mean scaling;\\
  1.1220 +\verb|GLP_SF_EQ| & perform equilibration scaling;\\
  1.1221 +\verb|GLP_SF_2N| & round scale factors to nearest power of two;\\
  1.1222 +\verb|GLP_SF_SKIP| & skip scaling, if the problem is well scaled.\\
  1.1223 +\end{tabular}
  1.1224 +
  1.1225 +The parameter \verb|flags| may be specified as \verb|GLP_SF_AUTO|, in
  1.1226 +which case the routine chooses the scaling options automatically.
  1.1227 +
  1.1228 +\subsection{glp\_unscale\_prob---unscale problem data}
  1.1229 +
  1.1230 +\subsubsection*{Synopsis}
  1.1231 +
  1.1232 +\begin{verbatim}
  1.1233 +void glp_unscale_prob(glp_prob *lp);
  1.1234 +\end{verbatim}
  1.1235 +
  1.1236 +The routine \verb|glp_unscale_prob| performs unscaling of problem data
  1.1237 +for the specified problem object.
  1.1238 +
  1.1239 +``Unscaling'' means replacing the current scaling matrices $R$ and $S$
  1.1240 +by unity matrices that cancels the scaling effect.
  1.1241 +
  1.1242 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1.1243 +
  1.1244 +\newpage
  1.1245 +
  1.1246 +\section{LP basis constructing routines}
  1.1247 +
  1.1248 +\subsection{Background}
  1.1249 +
  1.1250 +To start the search the simplex method needs a valid initial basis. In
  1.1251 +GLPK the basis is completely defined by a set of {\it statuses} assigned
  1.1252 +to {\it all} (auxiliary and structural) variables, where the status may
  1.1253 +be one of the following:
  1.1254 +
  1.1255 +\begin{tabular}{@{}ll}
  1.1256 +\verb|GLP_BS| & basic variable;\\
  1.1257 +\verb|GLP_NL| & non-basic variable having active lower bound;\\
  1.1258 +\verb|GLP_NU| & non-basic variable having active upper bound;\\
  1.1259 +\verb|GLP_NF| & non-basic free variable;\\
  1.1260 +\verb|GLP_NS| & non-basic fixed variable.\\
  1.1261 +\end{tabular}
  1.1262 +
  1.1263 +The basis is {\it valid}, if the basis matrix, which is a matrix built
  1.1264 +of columns of the augmented constraint matrix $(I\:|-A)$ corresponding
  1.1265 +to basic variables, is non-singular. This, in particular, means that
  1.1266 +the number of basic variables must be the same as the number of rows in
  1.1267 +the problem object. (For more details see Section \ref{lpbasis}, page
  1.1268 +\pageref{lpbasis}.)
  1.1269 +
  1.1270 +Any initial basis may be constructed (or restored) with the API
  1.1271 +routines \verb|glp_set_row_stat| and \verb|glp_set_col_stat| by
  1.1272 +assigning appropriate statuses to auxiliary and structural variables.
  1.1273 +Another way to construct an initial basis is to use API routines like
  1.1274 +\verb|glp_adv_basis|, which implement so called
  1.1275 +{\it crashing}.\footnote{This term is from early linear programming
  1.1276 +systems and means a heuristic to construct a valid initial basis.} Note
  1.1277 +that on normal exit the simplex solver remains the basis valid, so in
  1.1278 +case of reoptimization there is no need to construct an initial basis
  1.1279 +from scratch.
  1.1280 +
  1.1281 +\subsection{glp\_set\_row\_stat---set (change) row status}
  1.1282 +
  1.1283 +\subsubsection*{Synopsis}
  1.1284 +
  1.1285 +\begin{verbatim}
  1.1286 +void glp_set_row_stat(glp_prob *lp, int i, int stat);
  1.1287 +\end{verbatim}
  1.1288 +
  1.1289 +\subsubsection*{Description}
  1.1290 +
  1.1291 +The routine \verb|glp_set_row_stat| sets (changes) the current status
  1.1292 +of \verb|i|-th row (auxiliary variable) as specified by the parameter
  1.1293 +\verb|stat|:
  1.1294 +
  1.1295 +\begin{tabular}{@{}lp{104.2mm}@{}}
  1.1296 +\verb|GLP_BS| & make the row basic (make the constraint inactive); \\
  1.1297 +\verb|GLP_NL| & make the row non-basic (make the constraint active); \\
  1.1298 +\end{tabular}
  1.1299 +
  1.1300 +\newpage
  1.1301 +
  1.1302 +\begin{tabular}{@{}lp{104.2mm}@{}}
  1.1303 +\verb|GLP_NU| & make the row non-basic and set it to the upper bound;
  1.1304 +   if the row is not double-bounded, this status is equivalent to
  1.1305 +   \verb|GLP_NL| (only in the case of this routine); \\
  1.1306 +\verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this
  1.1307 +   routine); \\
  1.1308 +\verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this
  1.1309 +   routine). \\
  1.1310 +\end{tabular}
  1.1311 +
  1.1312 +\subsection{glp\_set\_col\_stat---set (change) column status}
  1.1313 +
  1.1314 +\subsubsection*{Synopsis}
  1.1315 +
  1.1316 +\begin{verbatim}
  1.1317 +void glp_set_col_stat(glp_prob *lp, int j, int stat);
  1.1318 +\end{verbatim}
  1.1319 +
  1.1320 +\subsubsection*{Description}
  1.1321 +
  1.1322 +The routine \verb|glp_set_col_stat sets| (changes) the current status
  1.1323 +of \verb|j|-th column (structural variable) as specified by the
  1.1324 +parameter \verb|stat|:
  1.1325 +
  1.1326 +\begin{tabular}{@{}lp{104.2mm}@{}}
  1.1327 +\verb|GLP_BS| & make the column basic; \\
  1.1328 +\verb|GLP_NL| & make the column non-basic; \\
  1.1329 +\verb|GLP_NU| & make the column non-basic and set it to the upper
  1.1330 +   bound; if the column is not double-bounded, this status is equivalent
  1.1331 +   to \verb|GLP_NL| (only in the case of this routine); \\
  1.1332 +\verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this
  1.1333 +   routine); \\
  1.1334 +\verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this
  1.1335 +   routine).
  1.1336 +\end{tabular}
  1.1337 +
  1.1338 +\subsection{glp\_std\_basis---construct standard initial LP basis}
  1.1339 +
  1.1340 +\subsubsection*{Synopsis}
  1.1341 +
  1.1342 +\begin{verbatim}
  1.1343 +void glp_std_basis(glp_prob *lp);
  1.1344 +\end{verbatim}
  1.1345 +
  1.1346 +\subsubsection*{Description}
  1.1347 +
  1.1348 +The routine \verb|glp_std_basis| constructs the ``standard'' (trivial)
  1.1349 +initial LP basis for the specified problem object.
  1.1350 +
  1.1351 +In the ``standard'' LP basis all auxiliary variables (rows) are basic,
  1.1352 +and all structural variables (columns) are non-basic (so the
  1.1353 +corresponding basis matrix is unity).
  1.1354 +
  1.1355 +\newpage
  1.1356 +
  1.1357 +\subsection{glp\_adv\_basis---construct advanced initial LP basis}
  1.1358 +
  1.1359 +\subsubsection*{Synopsis}
  1.1360 +
  1.1361 +\begin{verbatim}
  1.1362 +void glp_adv_basis(glp_prob *lp, int flags);
  1.1363 +\end{verbatim}
  1.1364 +
  1.1365 +\subsubsection*{Description}
  1.1366 +
  1.1367 +The routine \verb|glp_adv_basis| constructs an advanced initial LP
  1.1368 +basis for the specified problem object.
  1.1369 +
  1.1370 +The parameter \verb|flags| is reserved for use in the future and must
  1.1371 +be specified as zero.
  1.1372 +
  1.1373 +In order to construct the advanced initial LP basis the routine does
  1.1374 +the following:
  1.1375 +
  1.1376 +1) includes in the basis all non-fixed auxiliary variables;
  1.1377 +
  1.1378 +2) includes in the basis as many non-fixed structural variables as
  1.1379 +possible keeping the triangular form of the basis matrix;
  1.1380 +
  1.1381 +3) includes in the basis appropriate (fixed) auxiliary variables to
  1.1382 +complete the basis.
  1.1383 +
  1.1384 +As a result the initial LP basis has as few fixed variables as possible
  1.1385 +and the corresponding basis matrix is triangular.
  1.1386 +
  1.1387 +\subsection{glp\_cpx\_basis---construct Bixby's initial LP basis}
  1.1388 +
  1.1389 +\subsubsection*{Synopsis}
  1.1390 +
  1.1391 +\begin{verbatim}
  1.1392 +void glp_cpx_basis(glp_prob *lp);
  1.1393 +\end{verbatim}
  1.1394 +
  1.1395 +\subsubsection*{Description}
  1.1396 +
  1.1397 +The routine \verb|glp_cpx_basis| constructs an initial basis for the
  1.1398 +specified problem object with the algorithm proposed by
  1.1399 +R.~Bixby.\footnote{Robert E. Bixby, ``Implementing the Simplex Method:
  1.1400 +The Initial Basis.'' ORSA Journal on Computing, Vol. 4, No. 3, 1992,
  1.1401 +pp. 267-84.}
  1.1402 +
  1.1403 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1.1404 +
  1.1405 +\newpage
  1.1406 +
  1.1407 +\section{Simplex method routines}
  1.1408 +
  1.1409 +The {\it simplex method} is a well known efficient numerical procedure
  1.1410 +to solve LP problems.
  1.1411 +
  1.1412 +On each iteration the simplex method transforms the original system of
  1.1413 +equaility constraints (1.2) resolving them through different sets of
  1.1414 +variables to an equivalent system called {\it the simplex table} (or
  1.1415 +sometimes {\it the simplex tableau}), which has the following form:
  1.1416 +$$
  1.1417 +\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
  1.1418 +z&=&d_1(x_N)_1&+&d_2(x_N)_2&+ \dots +&d_n(x_N)_n \\
  1.1419 +(x_B)_1&=&\xi_{11}(x_N)_1& +& \xi_{12}(x_N)_2& + \dots +&
  1.1420 +   \xi_{1n}(x_N)_n \\
  1.1421 +(x_B)_2&=& \xi_{21}(x_N)_1& +& \xi_{22}(x_N)_2& + \dots +&
  1.1422 +   \xi_{2n}(x_N)_n \\
  1.1423 +\multicolumn{7}{c}
  1.1424 +{.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
  1.1425 +(x_B)_m&=&\xi_{m1}(x_N)_1& +& \xi_{m2}(x_N)_2& + \dots +&
  1.1426 +   \xi_{mn}(x_N)_n \\
  1.1427 +\end{array} \eqno (2.3)
  1.1428 +$$
  1.1429 +where: $(x_B)_1, (x_B)_2, \dots, (x_B)_m$ are basic variables;
  1.1430 +$(x_N)_1, (x_N)_2, \dots, (x_N)_n$ are non-basic variables;
  1.1431 +$d_1, d_2, \dots, d_n$ are reduced costs;
  1.1432 +$\xi_{11}, \xi_{12}, \dots, \xi_{mn}$ are coefficients of the
  1.1433 +simplex table. (May note that the original LP problem (1.1)---(1.3) also
  1.1434 +has the form of a simplex table, where all equalities are resolved
  1.1435 +through auxiliary variables.)
  1.1436 +
  1.1437 +From the linear programming theory it is known that if an optimal
  1.1438 +solution of the LP problem (1.1)---(1.3) exists, it can always be
  1.1439 +written in the form (2.3), where non-basic variables are set on their
  1.1440 +bounds while values of the objective function and basic variables are
  1.1441 +determined by the corresponding equalities of the simplex table.
  1.1442 +
  1.1443 +A set of values of all basic and non-basic variables determined by the
  1.1444 +simplex table is called {\it basic solution}. If all basic variables are
  1.1445 +within their bounds, the basic solution is called {\it (primal)
  1.1446 +feasible}, otherwise it is called {\it (primal) infeasible}. A feasible
  1.1447 +basic solution, which provides a smallest (in case of minimization) or
  1.1448 +a largest (in case of maximization) value of the objective function is
  1.1449 +called {\it optimal}. Therefore, for solving LP problem the simplex
  1.1450 +method tries to find its optimal basic solution.
  1.1451 +
  1.1452 +Primal feasibility of some basic solution may be stated by simple
  1.1453 +checking if all basic variables are within their bounds. Basic solution
  1.1454 +is optimal if additionally the following optimality conditions are
  1.1455 +satisfied for all non-basic variables:
  1.1456 +\begin{center}
  1.1457 +\begin{tabular}{lcc}
  1.1458 +Status of $(x_N)_j$ & Minimization & Maximization \\
  1.1459 +\hline
  1.1460 +$(x_N)_j$ is free & $d_j = 0$ & $d_j = 0$ \\
  1.1461 +$(x_N)_j$ is on its lower bound & $d_j \geq 0$ & $d_j \leq 0$ \\
  1.1462 +$(x_N)_j$ is on its upper bound & $d_j \leq 0$ & $d_j \geq 0$ \\
  1.1463 +\end{tabular}
  1.1464 +\end{center}
  1.1465 +In other words, basic solution is optimal if there is no non-basic
  1.1466 +variable, which changing in the feasible direction (i.e. increasing if
  1.1467 +it is free or on its lower bound, or decreasing if it is free or on its
  1.1468 +upper bound) can improve (i.e. decrease in case of minimization or
  1.1469 +increase in case of maximization) the objective function.
  1.1470 +
  1.1471 +If all non-basic variables satisfy to the optimality conditions shown
  1.1472 +above (independently on whether basic variables are within their bounds
  1.1473 +or not), the basic solution is called {\it dual feasible}, otherwise it
  1.1474 +is called {\it dual infeasible}.
  1.1475 +
  1.1476 +It may happen that some LP problem has no primal feasible solution due
  1.1477 +to incorrect formulation---this means that its constraints conflict
  1.1478 +with each other. It also may happen that some LP problem has unbounded
  1.1479 +solution again due to incorrect formulation---this means that some
  1.1480 +non-basic variable can improve the objective function, i.e. the
  1.1481 +optimality conditions are violated, and at the same time this variable
  1.1482 +can infinitely change in the feasible direction meeting no resistance
  1.1483 +from basic variables. (May note that in the latter case the LP problem
  1.1484 +has no dual feasible solution.)
  1.1485 +
  1.1486 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1.1487 +
  1.1488 +\subsection{glp\_simplex---solve LP problem with the primal or dual
  1.1489 +simplex method}
  1.1490 +
  1.1491 +\subsubsection*{Synopsis}
  1.1492 +
  1.1493 +\begin{verbatim}
  1.1494 +int glp_simplex(glp_prob *lp, const glp_smcp *parm);
  1.1495 +\end{verbatim}
  1.1496 +
  1.1497 +\subsubsection*{Description}
  1.1498 +
  1.1499 +The routine \verb|glp_simplex| is a driver to the LP solver based on
  1.1500 +the simplex method. This routine retrieves problem data from the
  1.1501 +specified problem object, calls the solver to solve the problem
  1.1502 +instance, and stores results of computations back into the problem
  1.1503 +object.
  1.1504 +
  1.1505 +The simplex solver has a set of control parameters. Values of the
  1.1506 +control parameters can be passed in the structure \verb|glp_smcp|,
  1.1507 +which the parameter \verb|parm| points to. For detailed description of
  1.1508 +this structure see paragraph ``Control parameters'' below.
  1.1509 +Before specifying some control parameters the application program
  1.1510 +should initialize the structure \verb|glp_smcp| by default values of
  1.1511 +all control parameters using the routine \verb|glp_init_smcp| (see the
  1.1512 +next subsection). This is needed for backward compatibility, because in
  1.1513 +the future there may appear new members in the structure
  1.1514 +\verb|glp_smcp|.
  1.1515 +
  1.1516 +The parameter \verb|parm| can be specified as \verb|NULL|, in which
  1.1517 +case the solver uses default settings.
  1.1518 +
  1.1519 +\subsubsection*{Returns}
  1.1520 +
  1.1521 +\def\arraystretch{1}
  1.1522 +
  1.1523 +\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
  1.1524 +0 & The LP problem instance has been successfully solved. (This code
  1.1525 +does {\it not} necessarily mean that the solver has found optimal
  1.1526 +solution. It only means that the solution process was successful.) \\
  1.1527 +\verb|GLP_EBADB| & Unable to start the search, because the initial basis
  1.1528 +specified in the problem object is invalid---the number of basic
  1.1529 +(auxiliary and structural) variables is not the same as the number of
  1.1530 +rows in the problem object.\\
  1.1531 +\verb|GLP_ESING| & Unable to start the search, because the basis matrix
  1.1532 +corresponding to the initial basis is singular within the working
  1.1533 +precision.\\
  1.1534 +\verb|GLP_ECOND| & Unable to start the search, because the basis matrix
  1.1535 +corresponding to the initial basis is ill-conditioned, i.e. its
  1.1536 +condition number is too large.\\
  1.1537 +\verb|GLP_EBOUND| & Unable to start the search, because some
  1.1538 +double-bounded (auxiliary or structural) variables have incorrect
  1.1539 +bounds.\\
  1.1540 +\verb|GLP_EFAIL| & The search was prematurely terminated due to the
  1.1541 +solver failure.\\
  1.1542 +\verb|GLP_EOBJLL| & The search was prematurely terminated, because the
  1.1543 +objective function being maximized has reached its lower limit and
  1.1544 +continues decreasing (the dual simplex only).\\
  1.1545 +\verb|GLP_EOBJUL| & The search was prematurely terminated, because the
  1.1546 +objective function being minimized has reached its upper limit and
  1.1547 +continues increasing (the dual simplex only).\\
  1.1548 +\verb|GLP_EITLIM| & The search was prematurely terminated, because the
  1.1549 +simplex iteration limit has been exceeded.\\
  1.1550 +\verb|GLP_ETMLIM| & The search was prematurely terminated, because the
  1.1551 +time limit has been exceeded.\\
  1.1552 +\verb|GLP_ENOPFS| & The LP problem instance has no primal feasible
  1.1553 +solution (only if the LP presolver is used).\\
  1.1554 +\verb|GLP_ENODFS| & The LP problem instance has no dual feasible
  1.1555 +solution (only if the LP presolver is used).\\
  1.1556 +\end{tabular}
  1.1557 +
  1.1558 +\subsubsection*{Built-in LP presolver}
  1.1559 +
  1.1560 +The simplex solver has {\it built-in LP presolver}. It is a subprogram
  1.1561 +that transforms the original LP problem specified in the problem object
  1.1562 +to an equivalent LP problem, which may be easier for solving with the
  1.1563 +simplex method than the original one. This is attained mainly due to
  1.1564 +reducing the problem size and improving its numeric properties (for
  1.1565 +example, by removing some inactive constraints or by fixing some
  1.1566 +non-basic variables). Once the transformed LP problem has been solved,
  1.1567 +the presolver transforms its basic solution back to the corresponding
  1.1568 +basic solution of the original problem.
  1.1569 +
  1.1570 +Presolving is an optional feature of the routine \verb|glp_simplex|,
  1.1571 +and by default it is disabled. In order to enable the LP presolver the
  1.1572 +control parameter \verb|presolve| should be set to \verb|GLP_ON| (see
  1.1573 +paragraph ``Control parameters'' below). Presolving may be used when
  1.1574 +the problem instance is solved for the first time. However, on
  1.1575 +performing re-optimization the presolver should be disabled.
  1.1576 +
  1.1577 +The presolving procedure is transparent to the API user in the sense
  1.1578 +that all necessary processing is performed internally, and a basic
  1.1579 +solution of the original problem recovered by the presolver is the same
  1.1580 +as if it were computed directly, i.e. without presolving.
  1.1581 +
  1.1582 +Note that the presolver is able to recover only optimal solutions. If
  1.1583 +a computed solution is infeasible or non-optimal, the corresponding
  1.1584 +solution of the original problem cannot be recovered and therefore
  1.1585 +remains undefined. If you need to know a basic solution even if it is
  1.1586 +infeasible or non-optimal, the presolver should be disabled.
  1.1587 +
  1.1588 +\subsubsection*{Terminal output}
  1.1589 +
  1.1590 +Solving large problem instances may take a long time, so the solver
  1.1591 +reports some information about the current basic solution, which is sent
  1.1592 +to the terminal. This information has the following format:
  1.1593 +
  1.1594 +\begin{verbatim}
  1.1595 +nnn:  obj = xxx  infeas = yyy (ddd)
  1.1596 +\end{verbatim}
  1.1597 +
  1.1598 +\noindent
  1.1599 +where: `\verb|nnn|' is the iteration number, `\verb|xxx|' is the
  1.1600 +current value of the objective function (it is is unscaled and has
  1.1601 +correct sign); `\verb|yyy|' is the current sum of primal or dual
  1.1602 +infeasibilities (it is scaled and therefore may be used only for visual
  1.1603 +estimating), `\verb|ddd|' is the current number of fixed basic
  1.1604 +variables.
  1.1605 +
  1.1606 +The symbol preceding the iteration number indicates which phase of the
  1.1607 +simplex method is in effect:
  1.1608 +
  1.1609 +{\it Blank} means that the solver is searching for primal feasible
  1.1610 +solution using the primal simplex or for dual feasible solution using
  1.1611 +the dual simplex;
  1.1612 +
  1.1613 +{\it Asterisk} (\verb|*|) means that the solver is searching for
  1.1614 +optimal solution using the primal simplex;
  1.1615 +
  1.1616 +{\it Vertical dash} (\verb/|/) means that the solver is searching for
  1.1617 +optimal solution using the dual simplex.
  1.1618 +
  1.1619 +\subsubsection*{Control parameters}
  1.1620 +
  1.1621 +This paragraph describes all control parameters currently used in the
  1.1622 +simplex solver. Symbolic names of control parameters are names of
  1.1623 +corresponding members in the structure \verb|glp_smcp|.
  1.1624 +
  1.1625 +\medskip
  1.1626 +
  1.1627 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1628 +\multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
  1.1629 +\\
  1.1630 +&Message level for terminal output:\\
  1.1631 +&\verb|GLP_MSG_OFF|---no output;\\
  1.1632 +&\verb|GLP_MSG_ERR|---error and warning messages only;\\
  1.1633 +&\verb|GLP_MSG_ON |---normal output;\\
  1.1634 +&\verb|GLP_MSG_ALL|---full output (including informational messages).
  1.1635 +\\
  1.1636 +\end{tabular}
  1.1637 +
  1.1638 +\medskip
  1.1639 +
  1.1640 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1641 +\multicolumn{2}{@{}l}{{\tt int meth} (default: {\tt GLP\_PRIMAL})}
  1.1642 +\\
  1.1643 +&Simplex method option:\\
  1.1644 +&\verb|GLP_PRIMAL|---use two-phase primal simplex;\\
  1.1645 +&\verb|GLP_DUAL  |---use two-phase dual simplex;\\
  1.1646 +&\verb|GLP_DUALP |---use two-phase dual simplex, and if it fails,
  1.1647 +switch to the\\
  1.1648 +&\verb|            |$\:$ primal simplex.\\
  1.1649 +\end{tabular}
  1.1650 +
  1.1651 +\medskip
  1.1652 +
  1.1653 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1654 +\multicolumn{2}{@{}l}{{\tt int pricing} (default: {\tt GLP\_PT\_PSE})}
  1.1655 +\\
  1.1656 +&Pricing technique:\\
  1.1657 +&\verb|GLP_PT_STD|---standard (textbook);\\
  1.1658 +&\verb|GLP_PT_PSE|---projected steepest edge.\\
  1.1659 +\end{tabular}
  1.1660 +
  1.1661 +\medskip
  1.1662 +
  1.1663 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1664 +\multicolumn{2}{@{}l}{{\tt int r\_test} (default: {\tt GLP\_RT\_HAR})}
  1.1665 +\\
  1.1666 +&Ratio test technique:\\
  1.1667 +&\verb|GLP_RT_STD|---standard (textbook);\\
  1.1668 +&\verb|GLP_RT_HAR|---Harris' two-pass ratio test.\\
  1.1669 +\end{tabular}
  1.1670 +
  1.1671 +\medskip
  1.1672 +
  1.1673 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1674 +\multicolumn{2}{@{}l}{{\tt double tol\_bnd} (default: {\tt 1e-7})}
  1.1675 +\\
  1.1676 +&Tolerance used to check if the basic solution is primal feasible.
  1.1677 +(Do not change this parameter without detailed understanding its
  1.1678 +purpose.)\\
  1.1679 +\end{tabular}
  1.1680 +
  1.1681 +\medskip
  1.1682 +
  1.1683 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1684 +\multicolumn{2}{@{}l}{{\tt double tol\_dj} (default: {\tt 1e-7})}
  1.1685 +\\
  1.1686 +&Tolerance used to check if the basic solution is dual feasible.
  1.1687 +(Do not change this parameter without detailed understanding its
  1.1688 +purpose.)\\
  1.1689 +\end{tabular}
  1.1690 +
  1.1691 +\medskip
  1.1692 +
  1.1693 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1694 +\multicolumn{2}{@{}l}{{\tt double tol\_piv} (default: {\tt 1e-10})}
  1.1695 +\\
  1.1696 +&Tolerance used to choose eligble pivotal elements of the simplex table.
  1.1697 +(Do not change this parameter without detailed understanding its
  1.1698 +purpose.)\\
  1.1699 +\end{tabular}
  1.1700 +
  1.1701 +\medskip
  1.1702 +
  1.1703 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1704 +\multicolumn{2}{@{}l}{{\tt double obj\_ll} (default: {\tt -DBL\_MAX})}
  1.1705 +\\
  1.1706 +&Lower limit of the objective function. If the objective function
  1.1707 +reaches this limit and continues decreasing, the solver terminates the
  1.1708 +search. (Used in the dual simplex only.)\\
  1.1709 +\end{tabular}
  1.1710 +
  1.1711 +\medskip
  1.1712 +
  1.1713 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1714 +\multicolumn{2}{@{}l}{{\tt double obj\_ul} (default: {\tt +DBL\_MAX})}
  1.1715 +\\
  1.1716 +&Upper limit of the objective function. If the objective function
  1.1717 +reaches this limit and continues increasing, the solver terminates the
  1.1718 +search. (Used in the dual simplex only.)\\
  1.1719 +\end{tabular}
  1.1720 +
  1.1721 +\medskip
  1.1722 +
  1.1723 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1724 +\multicolumn{2}{@{}l}{{\tt int it\_lim} (default: {\tt INT\_MAX})}
  1.1725 +\\
  1.1726 +&Simplex iteration limit.\\
  1.1727 +\end{tabular}
  1.1728 +
  1.1729 +\medskip
  1.1730 +
  1.1731 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1732 +\multicolumn{2}{@{}l}{{\tt int tm\_lim} (default: {\tt INT\_MAX})}
  1.1733 +\\
  1.1734 +&Searching time limit, in milliseconds.\\
  1.1735 +\end{tabular}
  1.1736 +
  1.1737 +\medskip
  1.1738 +
  1.1739 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1740 +\multicolumn{2}{@{}l}{{\tt int out\_frq} (default: {\tt 500})}
  1.1741 +\\
  1.1742 +&Output frequency, in iterations. This parameter specifies how
  1.1743 +frequently the solver sends information about the solution process to
  1.1744 +the terminal.\\
  1.1745 +\end{tabular}
  1.1746 +
  1.1747 +\medskip
  1.1748 +
  1.1749 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1750 +\multicolumn{2}{@{}l}{{\tt int out\_dly} (default: {\tt 0})}
  1.1751 +\\
  1.1752 +&Output delay, in milliseconds. This parameter specifies how long the
  1.1753 +solver should delay sending information about the solution process to
  1.1754 +the terminal.\\
  1.1755 +\end{tabular}
  1.1756 +
  1.1757 +\medskip
  1.1758 +
  1.1759 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.1760 +\multicolumn{2}{@{}l}{{\tt int presolve} (default: {\tt GLP\_OFF})}
  1.1761 +\\
  1.1762 +&LP presolver option:\\
  1.1763 +&\verb|GLP_ON |---enable using the LP presolver;\\
  1.1764 +&\verb|GLP_OFF|---disable using the LP presolver.\\
  1.1765 +\end{tabular}
  1.1766 +
  1.1767 +\subsubsection*{Example 1}
  1.1768 +
  1.1769 +The following main program reads LP problem instance in fixed MPS
  1.1770 +format from file \verb|25fv47.mps|,\footnote{This instance in fixed MPS
  1.1771 +format can be found in the Netlib LP collection; see
  1.1772 +{\tt ftp://ftp.netlib.org/lp/data/}.} constructs an advanced initial
  1.1773 +basis, solves the instance with the primal simplex method (by default),
  1.1774 +and writes the solution to file \verb|25fv47.txt|.
  1.1775 +
  1.1776 +\newpage
  1.1777 +
  1.1778 +\begin{footnotesize}
  1.1779 +\begin{verbatim}
  1.1780 +/* spxsamp1.c */
  1.1781 +
  1.1782 +#include <stdio.h>
  1.1783 +#include <stdlib.h>
  1.1784 +#include <glpk.h>
  1.1785 +
  1.1786 +int main(void)
  1.1787 +{     glp_prob *P;
  1.1788 +      P = glp_create_prob();
  1.1789 +      glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
  1.1790 +      glp_adv_basis(P, 0);
  1.1791 +      glp_simplex(P, NULL);
  1.1792 +      glp_print_sol(P, "25fv47.txt");
  1.1793 +      glp_delete_prob(P);
  1.1794 +      return 0;
  1.1795 +}
  1.1796 +
  1.1797 +/* eof */
  1.1798 +\end{verbatim}
  1.1799 +\end{footnotesize}
  1.1800 +
  1.1801 +\noindent
  1.1802 +Below here is shown the terminal output from this example program.
  1.1803 +
  1.1804 +\begin{footnotesize}
  1.1805 +\begin{verbatim}
  1.1806 +Reading problem data from `25fv47.mps'...
  1.1807 +Problem: 25FV47
  1.1808 +Objective: R0000
  1.1809 +822 rows, 1571 columns, 11127 non-zeros
  1.1810 +6919 records were read
  1.1811 +Crashing...
  1.1812 +Size of triangular part = 799
  1.1813 +      0: obj =   1.627307307e+04  infeas =  5.194e+04 (23)
  1.1814 +    200: obj =   1.474901610e+04  infeas =  1.233e+04 (19)
  1.1815 +    400: obj =   1.343909995e+04  infeas =  3.648e+03 (13)
  1.1816 +    600: obj =   1.756052217e+04  infeas =  4.179e+02 (7)
  1.1817 +*   775: obj =   1.789251591e+04  infeas =  4.982e-14 (1)
  1.1818 +*   800: obj =   1.663354510e+04  infeas =  2.857e-14 (1)
  1.1819 +*  1000: obj =   1.024935068e+04  infeas =  1.958e-12 (1)
  1.1820 +*  1200: obj =   7.860174791e+03  infeas =  2.810e-29 (1)
  1.1821 +*  1400: obj =   6.642378184e+03  infeas =  2.036e-16 (1)
  1.1822 +*  1600: obj =   6.037014568e+03  infeas =  0.000e+00 (1)
  1.1823 +*  1800: obj =   5.662171307e+03  infeas =  6.447e-15 (1)
  1.1824 +*  2000: obj =   5.528146165e+03  infeas =  9.764e-13 (1)
  1.1825 +*  2125: obj =   5.501845888e+03  infeas =  0.000e+00 (1)
  1.1826 +OPTIMAL SOLUTION FOUND
  1.1827 +Writing basic solution to `25fv47.txt'...
  1.1828 +\end{verbatim}
  1.1829 +\end{footnotesize}
  1.1830 +
  1.1831 +\newpage
  1.1832 +
  1.1833 +\subsubsection*{Example 2}
  1.1834 +
  1.1835 +The following main program solves the same LP problem instance as in
  1.1836 +Example 1 above, however, it uses the dual simplex method, which starts
  1.1837 +from the standard initial basis.
  1.1838 +
  1.1839 +\begin{footnotesize}
  1.1840 +\begin{verbatim}
  1.1841 +/* spxsamp2.c */
  1.1842 +
  1.1843 +#include <stdio.h>
  1.1844 +#include <stdlib.h>
  1.1845 +#include <glpk.h>
  1.1846 +
  1.1847 +int main(void)
  1.1848 +{     glp_prob *P;
  1.1849 +      glp_smcp parm;
  1.1850 +      P = glp_create_prob();
  1.1851 +      glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
  1.1852 +      glp_init_smcp(&parm);
  1.1853 +      parm.meth = GLP_DUAL;
  1.1854 +      glp_simplex(P, &parm);
  1.1855 +      glp_print_sol(P, "25fv47.txt");
  1.1856 +      glp_delete_prob(P);
  1.1857 +      return 0;
  1.1858 +}
  1.1859 +
  1.1860 +/* eof */
  1.1861 +\end{verbatim}
  1.1862 +\end{footnotesize}
  1.1863 +
  1.1864 +\noindent
  1.1865 +Below here is shown the terminal output from this example program.
  1.1866 +
  1.1867 +\begin{footnotesize}
  1.1868 +\begin{verbatim}
  1.1869 +Reading problem data from `25fv47.mps'...
  1.1870 +Problem: 25FV47
  1.1871 +Objective: R0000
  1.1872 +822 rows, 1571 columns, 11127 non-zeros
  1.1873 +6919 records were read
  1.1874 +      0:                          infeas =  1.223e+03 (516)
  1.1875 +    200:                          infeas =  7.000e+00 (471)
  1.1876 +    240:                          infeas =  1.106e-14 (461)
  1.1877 +|   400: obj =  -5.394267152e+03  infeas =  5.571e-16 (391)
  1.1878 +|   600: obj =  -4.586395752e+03  infeas =  1.389e-15 (340)
  1.1879 +|   800: obj =  -4.158268146e+03  infeas =  1.640e-15 (264)
  1.1880 +|  1000: obj =  -3.725320045e+03  infeas =  5.181e-15 (245)
  1.1881 +|  1200: obj =  -3.104802163e+03  infeas =  1.019e-14 (210)
  1.1882 +|  1400: obj =  -2.584190499e+03  infeas =  8.865e-15 (178)
  1.1883 +|  1600: obj =  -2.073852927e+03  infeas =  7.867e-15 (142)
  1.1884 +|  1800: obj =  -1.164037407e+03  infeas =  8.792e-15 (109)
  1.1885 +|  2000: obj =  -4.370590250e+02  infeas =  2.591e-14 (85)
  1.1886 +|  2200: obj =   1.068240144e+03  infeas =  1.025e-13 (70)
  1.1887 +|  2400: obj =   1.607481126e+03  infeas =  3.272e-14 (67)
  1.1888 +|  2600: obj =   3.038230551e+03  infeas =  4.850e-14 (52)
  1.1889 +|  2800: obj =   4.316238187e+03  infeas =  2.622e-14 (36)
  1.1890 +|  3000: obj =   5.443842629e+03  infeas =  3.976e-15 (11)
  1.1891 +|  3060: obj =   5.501845888e+03  infeas =  8.806e-15 (2)
  1.1892 +OPTIMAL SOLUTION FOUND
  1.1893 +Writing basic solution to `25fv47.txt'...
  1.1894 +\end{verbatim}
  1.1895 +\end{footnotesize}
  1.1896 +
  1.1897 +\subsection{glp\_exact---solve LP problem in exact arithmetic}
  1.1898 +
  1.1899 +\subsubsection*{Synopsis}
  1.1900 +
  1.1901 +\begin{verbatim}
  1.1902 +int glp_exact(glp_prob *lp, const glp_smcp *parm);
  1.1903 +\end{verbatim}
  1.1904 +
  1.1905 +\subsubsection*{Description}
  1.1906 +
  1.1907 +The routine \verb|glp_exact| is a tentative implementation of the
  1.1908 +primal two-phase simplex method based on exact (rational) arithmetic.
  1.1909 +It is similar to the routine \verb|glp_simplex|, however, for all
  1.1910 +internal computations it uses arithmetic of rational numbers, which is
  1.1911 +exact in mathematical sense, i.e. free of round-off errors unlike
  1.1912 +floating-point arithmetic.
  1.1913 +
  1.1914 +Note that the routine \verb|glp_exact| uses only two control parameters
  1.1915 +passed in the structure \verb|glp_smcp|, namely, \verb|it_lim| and
  1.1916 +\verb|tm_lim|.
  1.1917 +
  1.1918 +\subsubsection*{Returns}
  1.1919 +
  1.1920 +\def\arraystretch{1}
  1.1921 +
  1.1922 +\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
  1.1923 +0 & The LP problem instance has been successfully solved. (This code
  1.1924 +does {\it not} necessarily mean that the solver has found optimal
  1.1925 +solution. It only means that the solution process was successful.) \\
  1.1926 +\verb|GLP_EBADB| & Unable to start the search, because the initial basis
  1.1927 +specified in the problem object is invalid---the number of basic
  1.1928 +(auxiliary and structural) variables is not the same as the number of
  1.1929 +rows in the problem object.\\
  1.1930 +\verb|GLP_ESING| & Unable to start the search, because the basis matrix
  1.1931 +corresponding to the initial basis is exactly singular.\\
  1.1932 +\verb|GLP_EBOUND| & Unable to start the search, because some
  1.1933 +double-bounded (auxiliary or structural) variables have incorrect
  1.1934 +bounds.\\
  1.1935 +\verb|GLP_EFAIL| & The problem instance has no rows/columns.\\
  1.1936 +\verb|GLP_EITLIM| & The search was prematurely terminated, because the
  1.1937 +simplex iteration limit has been exceeded.\\
  1.1938 +\verb|GLP_ETMLIM| & The search was prematurely terminated, because the
  1.1939 +time limit has been exceeded.\\
  1.1940 +\end{tabular}
  1.1941 +
  1.1942 +\subsubsection*{Comments}
  1.1943 +
  1.1944 +Computations in exact arithmetic are very time consuming, so solving
  1.1945 +LP problem with the routine \verb|glp_exact| from the very beginning is
  1.1946 +not a good idea. It is much better at first to find an optimal basis
  1.1947 +with the routine \verb|glp_simplex| and only then to call
  1.1948 +\verb|glp_exact|, in which case only a few simplex iterations need to
  1.1949 +be performed in exact arithmetic.
  1.1950 +
  1.1951 +\subsection{glp\_init\_smcp---initialize simplex solver control
  1.1952 +parameters}
  1.1953 +
  1.1954 +\subsubsection*{Synopsis}
  1.1955 +
  1.1956 +\begin{verbatim}
  1.1957 +int glp_init_smcp(glp_smcp *parm);
  1.1958 +\end{verbatim}
  1.1959 +
  1.1960 +\subsubsection*{Description}
  1.1961 +
  1.1962 +The routine \verb|glp_init_smcp| initializes control parameters, which
  1.1963 +are used by the simplex solver, with default values.
  1.1964 +
  1.1965 +Default values of the control parameters are stored in a \verb|glp_smcp|
  1.1966 +structure, which the parameter \verb|parm| points to.
  1.1967 +
  1.1968 +\subsection{glp\_get\_status---determine generic status of basic
  1.1969 +solution}
  1.1970 +
  1.1971 +\subsubsection*{Synopsis}
  1.1972 +
  1.1973 +\begin{verbatim}
  1.1974 +int glp_get_status(glp_prob *lp);
  1.1975 +\end{verbatim}
  1.1976 +
  1.1977 +\subsubsection*{Returns}
  1.1978 +
  1.1979 +The routine \verb|glp_get_status| reports the generic status of the
  1.1980 +current basic solution for the specified problem object as follows:
  1.1981 +
  1.1982 +\begin{tabular}{@{}ll}
  1.1983 +\verb|GLP_OPT|    & solution is optimal; \\
  1.1984 +\verb|GLP_FEAS|   & solution is feasible; \\
  1.1985 +\verb|GLP_INFEAS| & solution is infeasible; \\
  1.1986 +\verb|GLP_NOFEAS| & problem has no feasible solution; \\
  1.1987 +\verb|GLP_UNBND|  & problem has unbounded solution; \\
  1.1988 +\verb|GLP_UNDEF|  & solution is undefined. \\
  1.1989 +\end{tabular}
  1.1990 +
  1.1991 +More detailed information about the status of basic solution can be
  1.1992 +retrieved with the routines \verb|glp_get_prim_stat| and
  1.1993 +\verb|glp_get_dual_stat|.
  1.1994 +
  1.1995 +\newpage
  1.1996 +
  1.1997 +\subsection{glp\_get\_prim\_stat---retrieve status of primal basic
  1.1998 +solution}
  1.1999 +
  1.2000 +\subsubsection*{Synopsis}
  1.2001 +
  1.2002 +\begin{verbatim}
  1.2003 +int glp_get_prim_stat(glp_prob *lp);
  1.2004 +\end{verbatim}
  1.2005 +
  1.2006 +\subsubsection*{Returns}
  1.2007 +
  1.2008 +The routine \verb|glp_get_prim_stat| reports the status of the primal
  1.2009 +basic solution for the specified problem object as follows:
  1.2010 +
  1.2011 +\begin{tabular}{@{}ll}
  1.2012 +\verb|GLP_UNDEF|  & primal solution is undefined; \\
  1.2013 +\verb|GLP_FEAS|   & primal solution is feasible; \\
  1.2014 +\verb|GLP_INFEAS| & primal solution is infeasible; \\
  1.2015 +\verb|GLP_NOFEAS| & no primal feasible solution exists. \\
  1.2016 +\end{tabular}
  1.2017 +
  1.2018 +\subsection{glp\_get\_dual\_stat---retrieve status of dual basic
  1.2019 +solution}
  1.2020 +
  1.2021 +\subsubsection*{Synopsis}
  1.2022 +
  1.2023 +\begin{verbatim}
  1.2024 +int glp_get_dual_stat(glp_prob *lp);
  1.2025 +\end{verbatim}
  1.2026 +
  1.2027 +\subsubsection*{Returns}
  1.2028 +
  1.2029 +The routine \verb|glp_get_dual_stat| reports the status of the dual
  1.2030 +basic solution for the specified problem object as follows:
  1.2031 +
  1.2032 +\begin{tabular}{@{}ll}
  1.2033 +\verb|GLP_UNDEF|  & dual solution is undefined; \\
  1.2034 +\verb|GLP_FEAS|   & dual solution is feasible; \\
  1.2035 +\verb|GLP_INFEAS| & dual solution is infeasible; \\
  1.2036 +\verb|GLP_NOFEAS| & no dual feasible solution exists. \\
  1.2037 +\end{tabular}
  1.2038 +
  1.2039 +\subsection{glp\_get\_obj\_val---retrieve objective value}
  1.2040 +
  1.2041 +\subsubsection*{Synopsis}
  1.2042 +
  1.2043 +\begin{verbatim}
  1.2044 +double glp_get_obj_val(glp_prob *lp);
  1.2045 +\end{verbatim}
  1.2046 +
  1.2047 +\subsubsection*{Returns}
  1.2048 +
  1.2049 +The routine \verb|glp_get_obj_val| returns current value of the
  1.2050 +objective function.
  1.2051 +
  1.2052 +\subsection{glp\_get\_row\_stat---retrieve row status}
  1.2053 +
  1.2054 +\subsubsection*{Synopsis}
  1.2055 +
  1.2056 +\begin{verbatim}
  1.2057 +int glp_get_row_stat(glp_prob *lp, int i);
  1.2058 +\end{verbatim}
  1.2059 +
  1.2060 +\subsubsection*{Returns}
  1.2061 +
  1.2062 +The routine \verb|glp_get_row_stat| returns current status assigned to
  1.2063 +the auxiliary variable associated with \verb|i|-th row as follows:
  1.2064 +
  1.2065 +\begin{tabular}{@{}ll}
  1.2066 +\verb|GLP_BS| & basic variable; \\
  1.2067 +\verb|GLP_NL| & non-basic variable on its lower bound; \\
  1.2068 +\verb|GLP_NU| & non-basic variable on its upper bound; \\
  1.2069 +\verb|GLP_NF| & non-basic free (unbounded) variable; \\
  1.2070 +\verb|GLP_NS| & non-basic fixed variable. \\
  1.2071 +\end{tabular}
  1.2072 +
  1.2073 +\subsection{glp\_get\_row\_prim---retrieve row primal value}
  1.2074 +
  1.2075 +\subsubsection*{Synopsis}
  1.2076 +
  1.2077 +\begin{verbatim}
  1.2078 +double glp_get_row_prim(glp_prob *lp, int i);
  1.2079 +\end{verbatim}
  1.2080 +
  1.2081 +\subsubsection*{Returns}
  1.2082 +
  1.2083 +The routine \verb|glp_get_row_prim| returns primal value of the
  1.2084 +auxiliary variable associated with \verb|i|-th row.
  1.2085 +
  1.2086 +\subsection{glp\_get\_row\_dual---retrieve row dual value}
  1.2087 +
  1.2088 +\subsubsection*{Synopsis}
  1.2089 +
  1.2090 +\begin{verbatim}
  1.2091 +double glp_get_row_dual(glp_prob *lp, int i);
  1.2092 +\end{verbatim}
  1.2093 +
  1.2094 +\subsubsection*{Returns}
  1.2095 +
  1.2096 +The routine \verb|glp_get_row_dual| returns dual value (i.e. reduced
  1.2097 +cost) of the auxiliary variable associated with \verb|i|-th row.
  1.2098 +
  1.2099 +\newpage
  1.2100 +
  1.2101 +\subsection{glp\_get\_col\_stat---retrieve column status}
  1.2102 +
  1.2103 +\subsubsection*{Synopsis}
  1.2104 +
  1.2105 +\begin{verbatim}
  1.2106 +int glp_get_col_stat(glp_prob *lp, int j);
  1.2107 +\end{verbatim}
  1.2108 +
  1.2109 +\subsubsection*{Returns}
  1.2110 +
  1.2111 +The routine \verb|glp_get_col_stat| returns current status assigned to
  1.2112 +the structural variable associated with \verb|j|-th column as follows:
  1.2113 +
  1.2114 +\begin{tabular}{@{}ll}
  1.2115 +\verb|GLP_BS| & basic variable; \\
  1.2116 +\verb|GLP_NL| & non-basic variable on its lower bound; \\
  1.2117 +\verb|GLP_NU| & non-basic variable on its upper bound; \\
  1.2118 +\verb|GLP_NF| & non-basic free (unbounded) variable; \\
  1.2119 +\verb|GLP_NS| & non-basic fixed variable. \\
  1.2120 +\end{tabular}
  1.2121 +
  1.2122 +\subsection{glp\_get\_col\_prim---retrieve column primal value}
  1.2123 +
  1.2124 +\subsubsection*{Synopsis}
  1.2125 +
  1.2126 +\begin{verbatim}
  1.2127 +double glp_get_col_prim(glp_prob *lp, int j);
  1.2128 +\end{verbatim}
  1.2129 +
  1.2130 +\subsubsection*{Returns}
  1.2131 +
  1.2132 +The routine \verb|glp_get_col_prim| returns primal value of the
  1.2133 +structural variable associated with \verb|j|-th column.
  1.2134 +
  1.2135 +\subsection{glp\_get\_col\_dual---retrieve column dual value}
  1.2136 +
  1.2137 +\subsubsection*{Synopsis}
  1.2138 +
  1.2139 +\begin{verbatim}
  1.2140 +double glp_get_col_dual(glp_prob *lp, int j);
  1.2141 +\end{verbatim}
  1.2142 +
  1.2143 +\subsubsection*{Returns}
  1.2144 +
  1.2145 +The routine \verb|glp_get_col_dual| returns dual value (i.e. reduced
  1.2146 +cost) of the structural variable associated with \verb|j|-th column.
  1.2147 +
  1.2148 +\newpage
  1.2149 +
  1.2150 +\subsection{glp\_get\_unbnd\_ray---determine variable causing\\
  1.2151 +unboundedness}
  1.2152 +
  1.2153 +\subsubsection*{Synopsis}
  1.2154 +
  1.2155 +\begin{verbatim}
  1.2156 +int glp_get_unbnd_ray(glp_prob *lp);
  1.2157 +\end{verbatim}
  1.2158 +
  1.2159 +\subsubsection*{Returns}
  1.2160 +
  1.2161 +The routine \verb|glp_get_unbnd_ray| returns the number $k$ of
  1.2162 +a variable, which causes primal or dual unboundedness.
  1.2163 +If $1\leq k\leq m$, it is $k$-th auxiliary variable, and if
  1.2164 +$m+1\leq k\leq m+n$, it is $(k-m)$-th structural variable, where $m$ is
  1.2165 +the number of rows, $n$ is the number of columns in the problem object.
  1.2166 +If such variable is not defined, the routine returns 0.
  1.2167 +
  1.2168 +\subsubsection*{Comments}
  1.2169 +
  1.2170 +If it is not exactly known which version of the simplex solver
  1.2171 +detected unboundedness, i.e. whether the unboundedness is primal or
  1.2172 +dual, it is sufficient to check the status of the variable
  1.2173 +with the routine \verb|glp_get_row_stat| or \verb|glp_get_col_stat|.
  1.2174 +If the variable is non-basic, the unboundedness is primal, otherwise,
  1.2175 +if the variable is basic, the unboundedness is dual (the latter case
  1.2176 +means that the problem has no primal feasible dolution).
  1.2177 +
  1.2178 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1.2179 +
  1.2180 +\newpage
  1.2181 +
  1.2182 +\section{Interior-point method routines}
  1.2183 +
  1.2184 +{\it Interior-point methods} (also known as {\it barrier methods}) are
  1.2185 +more modern and powerful numerical methods for large-scale linear
  1.2186 +programming. Such methods are especially efficient for very sparse LP
  1.2187 +problems and allow solving such problems much faster than the simplex
  1.2188 +method.
  1.2189 +
  1.2190 +In brief, the GLPK interior-point solver works as follows.
  1.2191 +
  1.2192 +At first, the solver transforms the original LP to a {\it working} LP
  1.2193 +in the standard format:
  1.2194 +
  1.2195 +\medskip
  1.2196 +
  1.2197 +\noindent
  1.2198 +\hspace{.5in} minimize
  1.2199 +$$z = c_1x_{m+1} + c_2x_{m+2} + \dots + c_nx_{m+n} + c_0 \eqno (2.4)$$
  1.2200 +\hspace{.5in} subject to linear constraints
  1.2201 +$$
  1.2202 +\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}l}
  1.2203 +a_{11}x_{m+1}&+&a_{12}x_{m+2}&+ \dots +&a_{1n}x_{m+n}&=&b_1 \\
  1.2204 +a_{21}x_{m+1}&+&a_{22}x_{m+2}&+ \dots +&a_{2n}x_{m+n}&=&b_2 \\
  1.2205 +\multicolumn{7}{c}
  1.2206 +{.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
  1.2207 +a_{m1}x_{m+1}&+&a_{m2}x_{m+2}&+ \dots +&a_{mn}x_{m+n}&=&b_m \\
  1.2208 +\end{array} \eqno (2.5)
  1.2209 +$$
  1.2210 +\hspace{.5in} and non-negative variables
  1.2211 +$$x_1\geq 0,\ \ x_2\geq 0,\ \ \dots,\ \ x_n\geq 0 \eqno(2.6)$$
  1.2212 +where: $z$ is the objective function; $x_1$, \dots, $x_n$ are variables;
  1.2213 +$c_1$, \dots, $c_n$ are objective coefficients; $c_0$ is a constant term
  1.2214 +of the objective function;\linebreak $a_{11}$, \dots, $a_{mn}$ are
  1.2215 +constraint coefficients; $b_1$, \dots, $b_m$ are right-hand sides.
  1.2216 +
  1.2217 +Using vector and matrix notations the working LP (2.4)---(2.6) can be
  1.2218 +written as follows:
  1.2219 +$$z=c^Tx+c_0\ \rightarrow\ \min,\eqno(2.7)$$
  1.2220 +$$Ax=b,\eqno(2.8)$$
  1.2221 +$$x\geq 0,\eqno(2.9)$$
  1.2222 +where: $x=(x_j)$ is $n$-vector of variables, $c=(c_j)$ is $n$-vector of
  1.2223 +objective coefficients, $A=(a_{ij})$ is $m\times n$-matrix of
  1.2224 +constraint coefficients, and $b=(b_i)$ is $m$-vector of right-hand
  1.2225 +sides.
  1.2226 +
  1.2227 +Karush--Kuhn--Tucker optimality conditions for LP (2.7)---(2.9) are the
  1.2228 +following:
  1.2229 +
  1.2230 +\newpage
  1.2231 +
  1.2232 +$$Ax=b,\eqno(2.10)$$
  1.2233 +$$A^T\pi+\lambda=c,\eqno(2.11)$$
  1.2234 +$$\lambda^Tx=0,\eqno(2.12)$$
  1.2235 +$$x\geq 0,\ \ \lambda\geq 0,\eqno(2.13)$$
  1.2236 +where: $\pi$ is $m$-vector of Lagrange multipliers (dual variables) for
  1.2237 +equality constraints (2.8), $\lambda$ is $n$-vector of Lagrange
  1.2238 +multipliers (dual variables) for non-negativity constraints (2.9),
  1.2239 +(2.10) is the primal feasibility condition, (2.11) is the dual
  1.2240 +feasibility condition, (2.12) is the primal-dual complementarity
  1.2241 +condition, and (2.13) is the non-negativity conditions.
  1.2242 +
  1.2243 +The main idea of the primal-dual interior-point method is based on
  1.2244 +finding a point in the primal-dual space (i.e. in the space of all
  1.2245 +primal and dual variables $x$, $\pi$, and $\lambda$), which satisfies
  1.2246 +to all optimality conditions (2.10)---(2.13). Obviously, $x$-component
  1.2247 +of such point then provides an optimal solution to the working LP
  1.2248 +(2.7)---(2.9).
  1.2249 +
  1.2250 +To find the optimal point $(x^*,\pi^*,\lambda^*)$ the interior-point
  1.2251 +method attempts to solve the system of equations (2.10)---(2.12), which
  1.2252 +is closed in the sense that the number of variables $x_j$, $\pi_i$, and
  1.2253 +$\lambda_j$ and the number equations are the same and equal to $m+2n$.
  1.2254 +Due to condition (2.12) this system of equations is non-linear, so it
  1.2255 +can be solved with a version of {\it Newton's method} provided with
  1.2256 +additional rules to keep the current point within the positive orthant
  1.2257 +as required by the non-negativity conditions (2.13).
  1.2258 +
  1.2259 +Finally, once the optimal point $(x^*,\pi^*,\lambda^*)$ has been found,
  1.2260 +the solver performs inverse transformations to recover corresponding
  1.2261 +solution to the original LP passed to the solver from the application
  1.2262 +program.
  1.2263 +
  1.2264 +\subsection{glp\_interior---solve LP problem with the interior-point
  1.2265 +method}
  1.2266 +
  1.2267 +\subsubsection*{Synopsis}
  1.2268 +
  1.2269 +\begin{verbatim}
  1.2270 +int glp_interior(glp_prob *P, const glp_iptcp *parm);
  1.2271 +\end{verbatim}
  1.2272 +
  1.2273 +\subsubsection*{Description}
  1.2274 +
  1.2275 +The routine \verb|glp_interior| is a driver to the LP solver based on
  1.2276 +the primal-dual interior-point method. This routine retrieves problem
  1.2277 +data from the specified problem object, calls the solver to solve the
  1.2278 +problem instance, and stores results of computations back into the
  1.2279 +problem object.
  1.2280 +
  1.2281 +The interior-point solver has a set of control parameters. Values of
  1.2282 +the control parameters can be passed in the structure \verb|glp_iptcp|,
  1.2283 +which the parameter \verb|parm| points to. For detailed description of
  1.2284 +this structure see paragraph ``Control parameters'' below. Before
  1.2285 +specifying some control parameters the application program should
  1.2286 +initialize the structure \verb|glp_iptcp| by default values of all
  1.2287 +control parameters using the routine \verb|glp_init_iptcp| (see the
  1.2288 +next subsection). This is needed for backward compatibility, because in
  1.2289 +the future there may appear new members in the structure
  1.2290 +\verb|glp_iptcp|.
  1.2291 +
  1.2292 +The parameter \verb|parm| can be specified as \verb|NULL|, in which
  1.2293 +case the solver uses default settings.
  1.2294 +
  1.2295 +\subsubsection*{Returns}
  1.2296 +
  1.2297 +\def\arraystretch{1}
  1.2298 +
  1.2299 +\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
  1.2300 +0 & The LP problem instance has been successfully solved. (This code
  1.2301 +does {\it not} necessarily mean that the solver has found optimal
  1.2302 +solution. It only means that the solution process was successful.) \\
  1.2303 +\verb|GLP_EFAIL| & The problem has no rows/columns.\\
  1.2304 +\verb|GLP_ENOCVG| & Very slow convergence or divergence.\\
  1.2305 +\verb|GLP_EITLIM| & Iteration limit exceeded.\\
  1.2306 +\verb|GLP_EINSTAB| & Numerical instability on solving Newtonian
  1.2307 +system.\\
  1.2308 +\end{tabular}
  1.2309 +
  1.2310 +\subsubsection*{Comments}
  1.2311 +
  1.2312 +The routine \verb|glp_interior| implements an easy version of
  1.2313 +the primal-dual interior-point method based on Mehrotra's
  1.2314 +technique.\footnote{S. Mehrotra. On the implementation of a primal-dual
  1.2315 +interior point method. SIAM J. on Optim., 2(4), pp. 575-601, 1992.}
  1.2316 +
  1.2317 +Note that currently the GLPK interior-point solver does not include
  1.2318 +many important features, in particular:
  1.2319 +
  1.2320 +$\bullet$ it is not able to process dense columns. Thus, if the
  1.2321 +constraint matrix of the LP problem has dense columns, the solving
  1.2322 +process may be inefficient;
  1.2323 +
  1.2324 +$\bullet$ it has no features against numerical instability. For some
  1.2325 +LP problems premature termination may happen if the matrix $ADA^T$
  1.2326 +becomes singular or ill-conditioned;
  1.2327 +
  1.2328 +$\bullet$ it is not able to identify the optimal basis, which
  1.2329 +corresponds to the interior-point solution found.
  1.2330 +
  1.2331 +\newpage
  1.2332 +
  1.2333 +\subsubsection*{Terminal output}
  1.2334 +
  1.2335 +Solving large LP problems may take a long time, so the solver reports
  1.2336 +some information about every interior-point iteration,\footnote{Unlike
  1.2337 +the simplex method the interior point method usually needs 30---50
  1.2338 +iterations (independently on the problem size) in order to find an
  1.2339 +optimal solution.} which is sent to the terminal. This information has
  1.2340 +the following format:
  1.2341 +
  1.2342 +\begin{verbatim}
  1.2343 +nnn: obj = fff; rpi = ppp; rdi = ddd; gap = ggg
  1.2344 +\end{verbatim}
  1.2345 +
  1.2346 +\noindent where: \verb|nnn| is iteration number, \verb|fff| is the
  1.2347 +current value of the objective function (in the case of maximization it
  1.2348 +has wrong sign), \verb|ppp| is the current relative primal
  1.2349 +infeasibility (cf. (2.10)):
  1.2350 +$$\frac{\|Ax^{(k)}-b\|}{1+\|b\|},\eqno(2.14)$$
  1.2351 +\verb|ddd| is the current relative dual infeasibility (cf. (2.11)):
  1.2352 +$$\frac{\|A^T\pi^{(k)}+\lambda^{(k)}-c\|}{1+\|c\|},\eqno(2.15)$$
  1.2353 +\verb|ggg| is the current primal-dual gap (cf. (2.12)):
  1.2354 +$$\frac{|c^Tx^{(k)}-b^T\pi^{(k)}|}{1+|c^Tx^{(k)}|},\eqno(2.16)$$
  1.2355 +and $[x^{(k)},\pi^{(k)},\lambda^{(k)}]$ is the current point on $k$-th
  1.2356 +iteration, $k=0,1,2,\dots$\ . Note that all solution components are
  1.2357 +internally scaled, so information sent to the terminal is suitable only
  1.2358 +for visual inspection.
  1.2359 +
  1.2360 +\subsubsection*{Control parameters}
  1.2361 +
  1.2362 +This paragraph describes all control parameters currently used in the
  1.2363 +interior-point solver. Symbolic names of control parameters are names of
  1.2364 +corresponding members in the structure \verb|glp_iptcp|.
  1.2365 +
  1.2366 +\medskip
  1.2367 +
  1.2368 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2369 +\multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
  1.2370 +\\
  1.2371 +&Message level for terminal output:\\
  1.2372 +&\verb|GLP_MSG_OFF|---no output;\\
  1.2373 +&\verb|GLP_MSG_ERR|---error and warning messages only;\\
  1.2374 +&\verb|GLP_MSG_ON |---normal output;\\
  1.2375 +&\verb|GLP_MSG_ALL|---full output (including informational messages).
  1.2376 +\\
  1.2377 +\end{tabular}
  1.2378 +
  1.2379 +\medskip
  1.2380 +
  1.2381 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2382 +\multicolumn{2}{@{}l}{{\tt int ord\_alg} (default: {\tt GLP\_ORD\_AMD})}
  1.2383 +\\
  1.2384 +&Ordering algorithm used prior to Cholesky factorization:\\
  1.2385 +&\verb|GLP_ORD_NONE  |---use natural (original) ordering;\\
  1.2386 +&\verb|GLP_ORD_QMD   |---quotient minimum degree (QMD);\\
  1.2387 +&\verb|GLP_ORD_AMD   |---approximate minimum degree (AMD);\\
  1.2388 +&\verb|GLP_ORD_SYMAMD|---approximate minimum degree (SYMAMD).\\
  1.2389 +\end{tabular}
  1.2390 +
  1.2391 +\subsubsection*{Example}
  1.2392 +
  1.2393 +The following main program reads LP problem instance in fixed MPS
  1.2394 +format from file \verb|25fv47.mps|,\footnote{This instance in fixed MPS
  1.2395 +format can be found in the Netlib LP collection; see
  1.2396 +{\tt ftp://ftp.netlib.org/lp/data/}.} solves it with the interior-point
  1.2397 +solver, and writes the solution to file \verb|25fv47.txt|.
  1.2398 +
  1.2399 +\begin{footnotesize}
  1.2400 +\begin{verbatim}
  1.2401 +/* iptsamp.c */
  1.2402 +
  1.2403 +#include <stdio.h>
  1.2404 +#include <stdlib.h>
  1.2405 +#include <glpk.h>
  1.2406 +
  1.2407 +int main(void)
  1.2408 +{     glp_prob *P;
  1.2409 +      P = glp_create_prob();
  1.2410 +      glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
  1.2411 +      glp_interior(P, NULL);
  1.2412 +      glp_print_ipt(P, "25fv47.txt");
  1.2413 +      glp_delete_prob(P);
  1.2414 +      return 0;
  1.2415 +}
  1.2416 +
  1.2417 +/* eof */
  1.2418 +\end{verbatim}
  1.2419 +\end{footnotesize}
  1.2420 +
  1.2421 +\noindent
  1.2422 +Below here is shown the terminal output from this example program.
  1.2423 +
  1.2424 +\begin{footnotesize}
  1.2425 +\begin{verbatim}
  1.2426 +Reading problem data from `25fv47.mps'...
  1.2427 +Problem: 25FV47
  1.2428 +Objective: R0000
  1.2429 +822 rows, 1571 columns, 11127 non-zeros
  1.2430 +6919 records were read
  1.2431 +Original LP has 822 row(s), 1571 column(s), and 11127 non-zero(s)
  1.2432 +Working LP has 821 row(s), 1876 column(s), and 10705 non-zero(s)
  1.2433 +Matrix A has 10705 non-zeros
  1.2434 +Matrix S = A*A' has 11895 non-zeros (upper triangle)
  1.2435 +Minimal degree ordering...
  1.2436 +Computing Cholesky factorization S = L'*L...
  1.2437 +Matrix L has 35411 non-zeros
  1.2438 +Guessing initial point...
  1.2439 +Optimization begins...
  1.2440 +  0: obj =   1.823377629e+05; rpi =  1.3e+01; rdi =  1.4e+01; gap =  9.3e-01
  1.2441 +  1: obj =   9.260045192e+04; rpi =  5.3e+00; rdi =  5.6e+00; gap =  6.8e+00
  1.2442 +  2: obj =   3.596999742e+04; rpi =  1.5e+00; rdi =  1.2e+00; gap =  1.8e+01
  1.2443 +  3: obj =   1.989627568e+04; rpi =  4.7e-01; rdi =  3.0e-01; gap =  1.9e+01
  1.2444 +  4: obj =   1.430215557e+04; rpi =  1.1e-01; rdi =  8.6e-02; gap =  1.4e+01
  1.2445 +  5: obj =   1.155716505e+04; rpi =  2.3e-02; rdi =  2.4e-02; gap =  6.8e+00
  1.2446 +  6: obj =   9.660273208e+03; rpi =  6.7e-03; rdi =  4.6e-03; gap =  3.9e+00
  1.2447 +  7: obj =   8.694348283e+03; rpi =  3.7e-03; rdi =  1.7e-03; gap =  2.0e+00
  1.2448 +  8: obj =   8.019543639e+03; rpi =  2.4e-03; rdi =  3.9e-04; gap =  1.0e+00
  1.2449 +  9: obj =   7.122676293e+03; rpi =  1.2e-03; rdi =  1.5e-04; gap =  6.6e-01
  1.2450 + 10: obj =   6.514534518e+03; rpi =  6.1e-04; rdi =  4.3e-05; gap =  4.1e-01
  1.2451 + 11: obj =   6.361572203e+03; rpi =  4.8e-04; rdi =  2.2e-05; gap =  3.0e-01
  1.2452 + 12: obj =   6.203355508e+03; rpi =  3.2e-04; rdi =  1.7e-05; gap =  2.6e-01
  1.2453 + 13: obj =   6.032943411e+03; rpi =  2.0e-04; rdi =  9.3e-06; gap =  2.1e-01
  1.2454 + 14: obj =   5.796553021e+03; rpi =  9.8e-05; rdi =  3.2e-06; gap =  1.0e-01
  1.2455 + 15: obj =   5.667032431e+03; rpi =  4.4e-05; rdi =  1.1e-06; gap =  5.6e-02
  1.2456 + 16: obj =   5.613911867e+03; rpi =  2.5e-05; rdi =  4.1e-07; gap =  3.5e-02
  1.2457 + 17: obj =   5.560572626e+03; rpi =  9.9e-06; rdi =  2.3e-07; gap =  2.1e-02
  1.2458 + 18: obj =   5.537276001e+03; rpi =  5.5e-06; rdi =  8.4e-08; gap =  1.1e-02
  1.2459 + 19: obj =   5.522746942e+03; rpi =  2.2e-06; rdi =  4.0e-08; gap =  6.7e-03
  1.2460 + 20: obj =   5.509956679e+03; rpi =  7.5e-07; rdi =  1.8e-08; gap =  2.9e-03
  1.2461 + 21: obj =   5.504571733e+03; rpi =  1.6e-07; rdi =  5.8e-09; gap =  1.1e-03
  1.2462 + 22: obj =   5.502576367e+03; rpi =  3.4e-08; rdi =  1.0e-09; gap =  2.5e-04
  1.2463 + 23: obj =   5.502057119e+03; rpi =  8.1e-09; rdi =  3.0e-10; gap =  7.7e-05
  1.2464 + 24: obj =   5.501885996e+03; rpi =  9.4e-10; rdi =  1.2e-10; gap =  2.4e-05
  1.2465 + 25: obj =   5.501852464e+03; rpi =  1.4e-10; rdi =  1.2e-11; gap =  3.0e-06
  1.2466 + 26: obj =   5.501846549e+03; rpi =  1.4e-11; rdi =  1.2e-12; gap =  3.0e-07
  1.2467 + 27: obj =   5.501845954e+03; rpi =  1.4e-12; rdi =  1.2e-13; gap =  3.0e-08
  1.2468 + 28: obj =   5.501845895e+03; rpi =  1.5e-13; rdi =  1.2e-14; gap =  3.0e-09
  1.2469 +OPTIMAL SOLUTION FOUND
  1.2470 +Writing interior-point solution to `25fv47.txt'...
  1.2471 +\end{verbatim}
  1.2472 +\end{footnotesize}
  1.2473 +
  1.2474 +\subsection{glp\_init\_iptcp---initialize interior-point solver control
  1.2475 +parameters}
  1.2476 +
  1.2477 +\subsubsection*{Synopsis}
  1.2478 +
  1.2479 +\begin{verbatim}
  1.2480 +int glp_init_iptcp(glp_iptcp *parm);
  1.2481 +\end{verbatim}
  1.2482 +
  1.2483 +\subsubsection*{Description}
  1.2484 +
  1.2485 +The routine \verb|glp_init_iptcp| initializes control parameters, which
  1.2486 +are used by the interior-point solver, with default values.
  1.2487 +
  1.2488 +Default values of the control parameters are stored in the structure
  1.2489 +\verb|glp_iptcp|, which the parameter \verb|parm| points to.
  1.2490 +
  1.2491 +\subsection{glp\_ipt\_status---determine solution status}
  1.2492 +
  1.2493 +\subsubsection*{Synopsis}
  1.2494 +
  1.2495 +\begin{verbatim}
  1.2496 +int glp_ipt_status(glp_prob *lp);
  1.2497 +\end{verbatim}
  1.2498 +
  1.2499 +\subsubsection*{Returns}
  1.2500 +
  1.2501 +The routine \verb|glp_ipt_status| reports the status of a solution
  1.2502 +found by the interior-point solver as follows:
  1.2503 +
  1.2504 +\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
  1.2505 +\verb|GLP_UNDEF| & interior-point solution is undefined. \\
  1.2506 +\verb|GLP_OPT|   & interior-point solution is optimal. \\
  1.2507 +\verb|GLP_INFEAS|& interior-point solution is infeasible. \\
  1.2508 +\verb|GLP_NOFEAS|& no feasible primal-dual solution exists.\\
  1.2509 +\end{tabular}
  1.2510 +
  1.2511 +\subsection{glp\_ipt\_obj\_val---retrieve objective value}
  1.2512 +
  1.2513 +\subsubsection*{Synopsis}
  1.2514 +
  1.2515 +\begin{verbatim}
  1.2516 +double glp_ipt_obj_val(glp_prob *lp);
  1.2517 +\end{verbatim}
  1.2518 +
  1.2519 +\subsubsection*{Returns}
  1.2520 +
  1.2521 +The routine \verb|glp_ipt_obj_val| returns value of the objective
  1.2522 +function for interior-point solution.
  1.2523 +
  1.2524 +\subsection{glp\_ipt\_row\_prim---retrieve row primal value}
  1.2525 +
  1.2526 +\subsubsection*{Synopsis}
  1.2527 +
  1.2528 +\begin{verbatim}
  1.2529 +double glp_ipt_row_prim(glp_prob *lp, int i);
  1.2530 +\end{verbatim}
  1.2531 +
  1.2532 +\subsubsection*{Returns}
  1.2533 +
  1.2534 +The routine \verb|glp_ipt_row_prim| returns primal value of the
  1.2535 +auxiliary variable associated with \verb|i|-th row.
  1.2536 +
  1.2537 +\newpage
  1.2538 +
  1.2539 +\subsection{glp\_ipt\_row\_dual---retrieve row dual value}
  1.2540 +
  1.2541 +\subsubsection*{Synopsis}
  1.2542 +
  1.2543 +\begin{verbatim}
  1.2544 +double glp_ipt_row_dual(glp_prob *lp, int i);
  1.2545 +\end{verbatim}
  1.2546 +
  1.2547 +\subsubsection*{Returns}
  1.2548 +
  1.2549 +The routine \verb|glp_ipt_row_dual| returns dual value (i.e. reduced
  1.2550 +cost) of the auxiliary variable associated with \verb|i|-th row.
  1.2551 +
  1.2552 +\subsection{glp\_ipt\_col\_prim---retrieve column primal value}
  1.2553 +
  1.2554 +\subsubsection*{Synopsis}
  1.2555 +
  1.2556 +\begin{verbatim}
  1.2557 +double glp_ipt_col_prim(glp_prob *lp, int j);
  1.2558 +\end{verbatim}
  1.2559 +
  1.2560 +\subsubsection*{Returns}
  1.2561 +
  1.2562 +The routine \verb|glp_ipt_col_prim| returns primal value of the
  1.2563 +structural variable associated with \verb|j|-th column.
  1.2564 +
  1.2565 +\subsection{glp\_ipt\_col\_dual---retrieve column dual value}
  1.2566 +
  1.2567 +\subsubsection*{Synopsis}
  1.2568 +
  1.2569 +\begin{verbatim}
  1.2570 +double glp_ipt_col_dual(glp_prob *lp, int j);
  1.2571 +\end{verbatim}
  1.2572 +
  1.2573 +\subsubsection*{Returns}
  1.2574 +
  1.2575 +The routine \verb|glp_ipt_col_dual| returns dual value (i.e. reduced
  1.2576 +cost) of the structural variable associated with \verb|j|-th column.
  1.2577 +
  1.2578 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1.2579 +
  1.2580 +\newpage
  1.2581 +
  1.2582 +\section{Mixed integer programming routines}
  1.2583 +
  1.2584 +\subsection{glp\_set\_col\_kind---set (change) column kind}
  1.2585 +
  1.2586 +\subsubsection*{Synopsis}
  1.2587 +
  1.2588 +\begin{verbatim}
  1.2589 +void glp_set_col_kind(glp_prob *mip, int j, int kind);
  1.2590 +\end{verbatim}
  1.2591 +
  1.2592 +\subsubsection*{Description}
  1.2593 +
  1.2594 +The routine \verb|glp_set_col_kind| sets (changes) the kind of
  1.2595 +\verb|j|-th column (structural variable) as specified by the parameter
  1.2596 +\verb|kind|:
  1.2597 +
  1.2598 +\begin{tabular}{@{}ll}
  1.2599 +\verb|GLP_CV| & continuous variable; \\
  1.2600 +\verb|GLP_IV| & integer variable; \\
  1.2601 +\verb|GLP_BV| & binary variable. \\
  1.2602 +\end{tabular}
  1.2603 +
  1.2604 +%If a column is set to \verb|GLP_IV|, its bounds must be exact integer
  1.2605 +%numbers with no tolerance, such that the condition
  1.2606 +%\verb|bnd == floor(bnd)| would hold.
  1.2607 +
  1.2608 +Setting a column to \verb|GLP_BV| has the same effect as if it were
  1.2609 +set to \verb|GLP_IV|, its lower bound were set 0, and its upper bound
  1.2610 +were set to 1.
  1.2611 +
  1.2612 +\subsection{glp\_get\_col\_kind---retrieve column kind}
  1.2613 +
  1.2614 +\subsubsection*{Synopsis}
  1.2615 +
  1.2616 +\begin{verbatim}
  1.2617 +int glp_get_col_kind(glp_prob *mip, int j);
  1.2618 +\end{verbatim}
  1.2619 +
  1.2620 +\subsubsection*{Returns}
  1.2621 +
  1.2622 +The routine \verb|glp_get_col_kind| returns the kind of \verb|j|-th
  1.2623 +column (structural variable) as follows:
  1.2624 +
  1.2625 +\begin{tabular}{@{}ll}
  1.2626 +\verb|GLP_CV| & continuous variable; \\
  1.2627 +\verb|GLP_IV| & integer variable; \\
  1.2628 +\verb|GLP_BV| & binary variable. \\
  1.2629 +\end{tabular}
  1.2630 +
  1.2631 +\subsection{glp\_get\_num\_int---retrieve number of integer columns}
  1.2632 +
  1.2633 +\subsubsection*{Synopsis}
  1.2634 +
  1.2635 +\begin{verbatim}
  1.2636 +int glp_get_num_int(glp_prob *mip);
  1.2637 +\end{verbatim}
  1.2638 +
  1.2639 +\subsubsection*{Returns}
  1.2640 +
  1.2641 +The routine \verb|glp_get_num_int| returns the number of columns
  1.2642 +(structural variables), which are marked as integer. Note that this
  1.2643 +number {\it does} include binary columns.
  1.2644 +
  1.2645 +\subsection{glp\_get\_num\_bin---retrieve number of binary columns}
  1.2646 +
  1.2647 +\subsubsection*{Synopsis}
  1.2648 +
  1.2649 +\begin{verbatim}
  1.2650 +int glp_get_num_bin(glp_prob *mip);
  1.2651 +\end{verbatim}
  1.2652 +
  1.2653 +\subsubsection*{Returns}
  1.2654 +
  1.2655 +The routine \verb|glp_get_num_bin| returns the number of columns
  1.2656 +(structural variables), which are marked as integer and whose lower
  1.2657 +bound is zero and upper bound is one.
  1.2658 +
  1.2659 +\subsection{glp\_intopt---solve MIP problem with the branch-and-cut
  1.2660 +method}
  1.2661 +
  1.2662 +\subsubsection*{Synopsis}
  1.2663 +
  1.2664 +\begin{verbatim}
  1.2665 +int glp_intopt(glp_prob *mip, const glp_iocp *parm);
  1.2666 +\end{verbatim}
  1.2667 +
  1.2668 +\subsubsection*{Description}
  1.2669 +
  1.2670 +The routine \verb|glp_intopt| is a driver to the MIP solver based on
  1.2671 +the branch-and-cut method, which is a hybrid of branch-and-bound and
  1.2672 +cutting plane methods.
  1.2673 +
  1.2674 +If the presolver is disabled (see paragraph ``Control parameters''
  1.2675 +below), on entry to the routine \verb|glp_intopt| the problem object,
  1.2676 +which the parameter \verb|mip| points to, should contain optimal
  1.2677 +solution to LP relaxation (it can be obtained, for example, with the
  1.2678 +routine \verb|glp_simplex|). Otherwise, if the presolver is enabled, it
  1.2679 +is not necessary.
  1.2680 +
  1.2681 +The MIP solver has a set of control parameters. Values of the control
  1.2682 +parameters can be passed in the structure \verb|glp_iocp|, which the
  1.2683 +parameter \verb|parm| points to. For detailed description of this
  1.2684 +structure see paragraph ``Control parameters'' below. Before specifying
  1.2685 +some control parameters the application program should initialize the
  1.2686 +structure \verb|glp_iocp| by default values of all control parameters
  1.2687 +using the routine \verb|glp_init_iocp| (see the next subsection). This
  1.2688 +is needed for backward compatibility, because in the future there may
  1.2689 +appear new members in the structure \verb|glp_iocp|.
  1.2690 +
  1.2691 +The parameter \verb|parm| can be specified as \verb|NULL|, in which case
  1.2692 +the solver uses default settings.
  1.2693 +
  1.2694 +Note that the GLPK branch-and-cut solver is not perfect, so it is unable
  1.2695 +to solve hard or very large scale MIP instances for a reasonable time.
  1.2696 +
  1.2697 +\subsubsection*{Returns}
  1.2698 +
  1.2699 +\def\arraystretch{1}
  1.2700 +
  1.2701 +\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
  1.2702 +0 & The MIP problem instance has been successfully solved. (This code
  1.2703 +does {\it not} necessarily mean that the solver has found optimal
  1.2704 +solution. It only means that the solution process was successful.) \\
  1.2705 +\verb|GLP_EBOUND| & Unable to start the search, because some
  1.2706 +double-bounded variables have incorrect bounds or some integer variables
  1.2707 +have non-integer (fractional) bounds.\\
  1.2708 +\verb|GLP_EROOT| & Unable to start the search, because optimal basis for
  1.2709 +initial LP relaxation is not provided. (This code may appear only if the
  1.2710 +presolver is disabled.)\\
  1.2711 +\verb|GLP_ENOPFS| & Unable to start the search, because LP relaxation
  1.2712 +of the MIP problem instance has no primal feasible solution. (This code
  1.2713 +may appear only if the presolver is enabled.)\\
  1.2714 +\verb|GLP_ENODFS| & Unable to start the search, because LP relaxation
  1.2715 +of the MIP problem instance has no dual feasible solution. In other
  1.2716 +word, this code means that if the LP relaxation has at least one primal
  1.2717 +feasible solution, its optimal solution is unbounded, so if the MIP
  1.2718 +problem has at least one integer feasible solution, its (integer)
  1.2719 +optimal solution is also unbounded. (This code may appear only if the
  1.2720 +presolver is enabled.)\\
  1.2721 +\verb|GLP_EFAIL| & The search was prematurely terminated due to the
  1.2722 +solver failure.\\
  1.2723 +\verb|GLP_EMIPGAP| & The search was prematurely terminated, because the
  1.2724 +relative mip gap tolerance has been reached.\\
  1.2725 +\verb|GLP_ETMLIM| & The search was prematurely terminated, because the
  1.2726 +time limit has been exceeded.\\
  1.2727 +\verb|GLP_ESTOP| & The search was prematurely terminated by application.
  1.2728 +(This code may appear only if the advanced solver interface is used.)\\
  1.2729 +\end{tabular}
  1.2730 +
  1.2731 +\subsubsection*{Built-in MIP presolver}
  1.2732 +
  1.2733 +The branch-and-cut solver has {\it built-in MIP presolver}. It is
  1.2734 +a subprogram that transforms the original MIP problem specified in the
  1.2735 +problem object to an equivalent MIP problem, which may be easier for
  1.2736 +solving with the branch-and-cut method than the original one. For
  1.2737 +example, the presolver can remove redundant constraints and variables,
  1.2738 +whose optimal values are known, perform bound and coefficient reduction,
  1.2739 +etc. Once the transformed MIP problem has been solved, the presolver
  1.2740 +transforms its solution back to corresponding solution of the original
  1.2741 +problem.
  1.2742 +
  1.2743 +Presolving is an optional feature of the routine \verb|glp_intopt|, and
  1.2744 +by default it is disabled. In order to enable the MIP presolver, the
  1.2745 +control parameter \verb|presolve| should be set to \verb|GLP_ON| (see
  1.2746 +paragraph ``Control parameters'' below).
  1.2747 +
  1.2748 +\subsubsection*{Advanced solver interface}
  1.2749 +
  1.2750 +The routine \verb|glp_intopt| allows the user to control the
  1.2751 +branch-and-cut search by passing to the solver a user-defined callback
  1.2752 +routine. For more details see Chapter ``Branch-and-Cut API Routines''.
  1.2753 +
  1.2754 +\subsubsection*{Terminal output}
  1.2755 +
  1.2756 +Solving a MIP problem may take a long time, so the solver reports some
  1.2757 +information about best known solutions, which is sent to the terminal.
  1.2758 +This information has the following format:
  1.2759 +
  1.2760 +\begin{verbatim}
  1.2761 ++nnn: mip = xxx <rho> yyy gap (ppp; qqq)
  1.2762 +\end{verbatim}
  1.2763 +
  1.2764 +\noindent
  1.2765 +where: `\verb|nnn|' is the simplex iteration number; `\verb|xxx|' is a
  1.2766 +value of the objective function for the best known integer feasible
  1.2767 +solution (if no integer feasible solution has been found yet,
  1.2768 +`\verb|xxx|' is the text `\verb|not found yet|'); `\verb|rho|' is the
  1.2769 +string `\verb|>=|' (in case of minimization) or `\verb|<=|' (in case of
  1.2770 +maximization); `\verb|yyy|' is a global bound for exact integer optimum
  1.2771 +(i.e. the exact integer optimum is always in the range from `\verb|xxx|'
  1.2772 +to `\verb|yyy|'); `\verb|gap|' is the relative mip gap, in percents,
  1.2773 +computed as $gap=|xxx-yyy|/(|xxx|+{\tt DBL\_EPSILON})\cdot 100\%$ (if
  1.2774 +$gap$ is greater than $999.9\%$, it is not printed); `\verb|ppp|' is the
  1.2775 +number of subproblems in the active list, `\verb|qqq|' is the number of
  1.2776 +subproblems which have been already fathomed and therefore removed from
  1.2777 +the branch-and-bound search tree.
  1.2778 +
  1.2779 +\subsubsection{Control parameters}
  1.2780 +
  1.2781 +This paragraph describes all control parameters currently used in the
  1.2782 +MIP solver. Symbolic names of control parameters are names of
  1.2783 +corresponding members in the structure \verb|glp_iocp|.
  1.2784 +
  1.2785 +\medskip
  1.2786 +
  1.2787 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2788 +\multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
  1.2789 +\\
  1.2790 +&Message level for terminal output:\\
  1.2791 +&\verb|GLP_MSG_OFF|---no output;\\
  1.2792 +&\verb|GLP_MSG_ERR|---error and warning messages only;\\
  1.2793 +&\verb|GLP_MSG_ON |---normal output;\\
  1.2794 +&\verb|GLP_MSG_ALL|---full output (including informational messages).
  1.2795 +\\
  1.2796 +\end{tabular}
  1.2797 +
  1.2798 +\medskip
  1.2799 +
  1.2800 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2801 +\multicolumn{2}{@{}l}{{\tt int br\_tech} (default: {\tt GLP\_BR\_DTH})}
  1.2802 +\\
  1.2803 +&Branching technique option:\\
  1.2804 +&\verb|GLP_BR_FFV|---first fractional variable;\\
  1.2805 +&\verb|GLP_BR_LFV|---last fractional variable;\\
  1.2806 +&\verb|GLP_BR_MFV|---most fractional variable;\\
  1.2807 +&\verb|GLP_BR_DTH|---heuristic by Driebeck and Tomlin;\\
  1.2808 +&\verb|GLP_BR_PCH|---hybrid pseudocost heuristic.\\
  1.2809 +\end{tabular}
  1.2810 +
  1.2811 +\medskip
  1.2812 +
  1.2813 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2814 +\multicolumn{2}{@{}l}{{\tt int bt\_tech} (default: {\tt GLP\_BT\_BLB})}
  1.2815 +\\
  1.2816 +&Backtracking technique option:\\
  1.2817 +&\verb|GLP_BT_DFS|---depth first search;\\
  1.2818 +&\verb|GLP_BT_BFS|---breadth first search;\\
  1.2819 +&\verb|GLP_BT_BLB|---best local bound;\\
  1.2820 +&\verb|GLP_BT_BPH|---best projection heuristic.\\
  1.2821 +\end{tabular}
  1.2822 +
  1.2823 +\medskip
  1.2824 +
  1.2825 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2826 +\multicolumn{2}{@{}l}{{\tt int pp\_tech} (default: {\tt GLP\_PP\_ALL})}
  1.2827 +\\
  1.2828 +&Preprocessing technique option:\\
  1.2829 +&\verb|GLP_PP_NONE|---disable preprocessing;\\
  1.2830 +&\verb|GLP_PP_ROOT|---perform preprocessing only on the root level;\\
  1.2831 +&\verb|GLP_PP_ALL |---perform preprocessing on all levels.\\
  1.2832 +\end{tabular}
  1.2833 +
  1.2834 +\medskip
  1.2835 +
  1.2836 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2837 +\multicolumn{2}{@{}l}{{\tt int fp\_heur} (default: {\tt GLP\_OFF})}
  1.2838 +\\
  1.2839 +&Feasibility pump heuristic option:\\
  1.2840 +&\verb|GLP_ON |---enable applying the feasibility pump heuristic;\\
  1.2841 +&\verb|GLP_OFF|---disable applying the feasibility pump heuristic.\\
  1.2842 +\end{tabular}
  1.2843 +
  1.2844 +\medskip
  1.2845 +
  1.2846 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2847 +\multicolumn{2}{@{}l}{{\tt int gmi\_cuts} (default: {\tt GLP\_OFF})}\\
  1.2848 +&Gomory's mixed integer cut option:\\
  1.2849 +&\verb|GLP_ON |---enable generating Gomory's cuts;\\
  1.2850 +&\verb|GLP_OFF|---disable generating Gomory's cuts.\\
  1.2851 +\end{tabular}
  1.2852 +
  1.2853 +\medskip
  1.2854 +
  1.2855 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2856 +\multicolumn{2}{@{}l}{{\tt int mir\_cuts} (default: {\tt GLP\_OFF})}\\
  1.2857 +&Mixed integer rounding (MIR) cut option:\\
  1.2858 +&\verb|GLP_ON |---enable generating MIR cuts;\\
  1.2859 +&\verb|GLP_OFF|---disable generating MIR cuts.\\
  1.2860 +\end{tabular}
  1.2861 +
  1.2862 +\medskip
  1.2863 +
  1.2864 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2865 +\multicolumn{2}{@{}l}{{\tt int cov\_cuts} (default: {\tt GLP\_OFF})}\\
  1.2866 +&Mixed cover cut option:\\
  1.2867 +&\verb|GLP_ON |---enable generating mixed cover cuts;\\
  1.2868 +&\verb|GLP_OFF|---disable generating mixed cover cuts.\\
  1.2869 +\end{tabular}
  1.2870 +
  1.2871 +\medskip
  1.2872 +
  1.2873 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2874 +\multicolumn{2}{@{}l}{{\tt int clq\_cuts} (default: {\tt GLP\_OFF})}\\
  1.2875 +&Clique cut option:\\
  1.2876 +&\verb|GLP_ON |---enable generating clique cuts;\\
  1.2877 +&\verb|GLP_OFF|---disable generating clique cuts.\\
  1.2878 +\end{tabular}
  1.2879 +
  1.2880 +\medskip
  1.2881 +
  1.2882 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2883 +\multicolumn{2}{@{}l}{{\tt double tol\_int} (default: {\tt 1e-5})}\\
  1.2884 +&Absolute tolerance used to check if optimal solution to the current LP
  1.2885 +relaxation is integer feasible. (Do not change this parameter without
  1.2886 +detailed understanding its purpose.)\\
  1.2887 +\end{tabular}
  1.2888 +
  1.2889 +\medskip
  1.2890 +
  1.2891 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2892 +\multicolumn{2}{@{}l}{{\tt double tol\_obj} (default: {\tt 1e-7})}\\
  1.2893 +&Relative tolerance used to check if the objective value in optimal
  1.2894 +solution to the current LP relaxation is not better than in the best
  1.2895 +known integer feasible solution. (Do not change this parameter without
  1.2896 +detailed understanding its purpose.)\\
  1.2897 +\end{tabular}
  1.2898 +
  1.2899 +\medskip
  1.2900 +
  1.2901 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2902 +\multicolumn{2}{@{}l}{{\tt double mip\_gap} (default: {\tt 0.0})}\\
  1.2903 +&The relative mip gap tolerance. If the relative mip gap for currently
  1.2904 +known best integer feasible solution falls below this tolerance, the
  1.2905 +solver terminates the search. This allows obtainig suboptimal integer
  1.2906 +feasible solutions if solving the problem to optimality takes too long
  1.2907 +time.\\
  1.2908 +\end{tabular}
  1.2909 +
  1.2910 +\medskip
  1.2911 +
  1.2912 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2913 +\multicolumn{2}{@{}l}{{\tt int tm\_lim} (default: {\tt INT\_MAX})}\\
  1.2914 +&Searching time limit, in milliseconds.\\
  1.2915 +\end{tabular}
  1.2916 +
  1.2917 +\medskip
  1.2918 +
  1.2919 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2920 +\multicolumn{2}{@{}l}{{\tt int out\_frq} (default: {\tt 5000})}\\
  1.2921 +&Output frequency, in milliseconds. This parameter specifies how
  1.2922 +frequently the solver sends information about the solution process to
  1.2923 +the terminal.\\
  1.2924 +\end{tabular}
  1.2925 +
  1.2926 +\medskip
  1.2927 +
  1.2928 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2929 +\multicolumn{2}{@{}l}{{\tt int out\_dly} (default: {\tt 10000})}\\
  1.2930 +&Output delay, in milliseconds. This parameter specifies how long the
  1.2931 +solver should delay sending information about solution of the current
  1.2932 +LP relaxation with the simplex method to the terminal.\\
  1.2933 +\end{tabular}
  1.2934 +
  1.2935 +\medskip
  1.2936 +
  1.2937 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2938 +\multicolumn{2}{@{}l}
  1.2939 +{{\tt void (*cb\_func)(glp\_tree *tree, void *info)}
  1.2940 +(default: {\tt NULL})}\\
  1.2941 +&Entry point to the user-defined callback routine. \verb|NULL| means
  1.2942 +the advanced solver interface is not used. For more details see Chapter
  1.2943 +``Branch-and-Cut API Routines''.\\
  1.2944 +\end{tabular}
  1.2945 +
  1.2946 +\medskip
  1.2947 +
  1.2948 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2949 +\multicolumn{2}{@{}l}{{\tt void *cb\_info} (default: {\tt NULL})}\\
  1.2950 +&Transit pointer passed to the routine \verb|cb_func| (see above).\\
  1.2951 +\end{tabular}
  1.2952 +
  1.2953 +\medskip
  1.2954 +
  1.2955 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2956 +\multicolumn{2}{@{}l}{{\tt int cb\_size} (default: {\tt 0})}\\
  1.2957 +&The number of extra (up to 256) bytes allocated for each node of the
  1.2958 +branch-and-bound tree to store application-specific data. On creating
  1.2959 +a node these bytes are initialized by binary zeros.\\
  1.2960 +\end{tabular}
  1.2961 +
  1.2962 +\medskip
  1.2963 +
  1.2964 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2965 +\multicolumn{2}{@{}l}{{\tt int presolve} (default: {\tt GLP\_OFF})}\\
  1.2966 +&MIP presolver option:\\
  1.2967 +&\verb|GLP_ON |---enable using the MIP presolver;\\
  1.2968 +&\verb|GLP_OFF|---disable using the MIP presolver.\\
  1.2969 +\end{tabular}
  1.2970 +
  1.2971 +\medskip
  1.2972 +
  1.2973 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
  1.2974 +\multicolumn{2}{@{}l}{{\tt int binarize} (default: {\tt GLP\_OFF})}\\
  1.2975 +&Binarization option (used only if the presolver is enabled):\\
  1.2976 +&\verb|GLP_ON |---replace general integer variables by binary ones;\\
  1.2977 +&\verb|GLP_OFF|---do not use binarization.\\
  1.2978 +\end{tabular}
  1.2979 +
  1.2980 +\subsection{glp\_init\_iocp---initialize integer optimizer control
  1.2981 +parameters}
  1.2982 +
  1.2983 +\subsubsection*{Synopsis}
  1.2984 +
  1.2985 +\begin{verbatim}
  1.2986 +void glp_init_iocp(glp_iocp *parm);
  1.2987 +\end{verbatim}
  1.2988 +
  1.2989 +\subsubsection*{Description}
  1.2990 +
  1.2991 +The routine \verb|glp_init_iocp| initializes control parameters, which
  1.2992 +are used by the branch-and-cut solver, with default values.
  1.2993 +
  1.2994 +Default values of the control parameters are stored in a \verb|glp_iocp|
  1.2995 +structure, which the parameter \verb|parm| points to.
  1.2996 +
  1.2997 +\subsection{glp\_mip\_status---determine status of MIP solution}
  1.2998 +
  1.2999 +\subsubsection*{Synopsis}
  1.3000 +
  1.3001 +\begin{verbatim}
  1.3002 +int glp_mip_status(glp_prob *mip);
  1.3003 +\end{verbatim}
  1.3004 +
  1.3005 +\subsubsection*{Returns}
  1.3006 +
  1.3007 +The routine \verb|glp_mip_status| reports the status of a MIP solution
  1.3008 +found by the MIP solver as follows:
  1.3009 +
  1.3010 +\smallskip
  1.3011 +
  1.3012 +\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
  1.3013 +\verb|GLP_UNDEF| & MIP solution is undefined. \\
  1.3014 +\verb|GLP_OPT|   & MIP solution is integer optimal. \\
  1.3015 +\verb|GLP_FEAS|  & MIP solution is integer feasible, however, its
  1.3016 +   optimality (or non-optimality) has not been proven, perhaps due to
  1.3017 +   premature termination of the search. \\
  1.3018 +\end{tabular}
  1.3019 +
  1.3020 +\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
  1.3021 +\verb|GLP_NOFEAS| & problem has no integer feasible solution (proven by
  1.3022 +   the solver). \\
  1.3023 +\end{tabular}
  1.3024 +
  1.3025 +\subsection{glp\_mip\_obj\_val---retrieve objective value}
  1.3026 +
  1.3027 +\subsubsection*{Synopsis}
  1.3028 +
  1.3029 +\begin{verbatim}
  1.3030 +double glp_mip_obj_val(glp_prob *mip);
  1.3031 +\end{verbatim}
  1.3032 +
  1.3033 +\subsubsection*{Returns}
  1.3034 +
  1.3035 +The routine \verb|glp_mip_obj_val| returns value of the objective
  1.3036 +function for MIP solution.
  1.3037 +
  1.3038 +\subsection{glp\_mip\_row\_val---retrieve row value}
  1.3039 +
  1.3040 +\subsubsection*{Synopsis}
  1.3041 +
  1.3042 +\begin{verbatim}
  1.3043 +double glp_mip_row_val(glp_prob *mip, int i);
  1.3044 +\end{verbatim}
  1.3045 +
  1.3046 +\subsubsection*{Returns}
  1.3047 +
  1.3048 +The routine \verb|glp_mip_row_val| returns value of the auxiliary
  1.3049 +variable associated with \verb|i|-th row for MIP solution.
  1.3050 +
  1.3051 +\subsection{glp\_mip\_col\_val---retrieve column value}
  1.3052 +
  1.3053 +\subsubsection*{Synopsis}
  1.3054 +
  1.3055 +\begin{verbatim}
  1.3056 +double glp_mip_col_val(glp_prob *mip, int j);
  1.3057 +\end{verbatim}
  1.3058 +
  1.3059 +\subsubsection*{Returns}
  1.3060 +
  1.3061 +The routine \verb|glp_mip_col_val| returns value of the structural
  1.3062 +variable associated with \verb|j|-th column for MIP solution.
  1.3063 +
  1.3064 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1.3065 +
  1.3066 +\newpage
  1.3067 +
  1.3068 +\section{Additional routines}
  1.3069 +
  1.3070 +\subsection{lpx\_check\_kkt---check Karush-Kuhn-Tucker optimality
  1.3071 +conditions}
  1.3072 +
  1.3073 +\subsubsection*{Synopsis}
  1.3074 +
  1.3075 +\begin{verbatim}
  1.3076 +void lpx_check_kkt(glp_prob *lp, int scaled, LPXKKT *kkt);
  1.3077 +\end{verbatim}
  1.3078 +
  1.3079 +\subsubsection*{Description}
  1.3080 +
  1.3081 +The routine \verb|lpx_check_kkt| checks Karush-Kuhn-Tucker optimality
  1.3082 +conditions for basic solution. It is assumed that both primal and dual
  1.3083 +components of basic solution are valid.
  1.3084 +
  1.3085 +If the parameter \verb|scaled| is zero, the optimality conditions are
  1.3086 +checked for the original, unscaled LP problem. Otherwise, if the
  1.3087 +parameter \verb|scaled| is non-zero, the routine checks the conditions
  1.3088 +for an internally scaled LP problem.
  1.3089 +
  1.3090 +The parameter \verb|kkt| is a pointer to the structure \verb|LPXKKT|,
  1.3091 +to which the routine stores results of the check. Members of this
  1.3092 +structure are shown in the table below.
  1.3093 +
  1.3094 +\begin{table}[h]
  1.3095 +\begin{center}
  1.3096 +\begin{tabular}{@{}c|l|l@{}}
  1.3097 +Condition & Member & Comment \\
  1.3098 +\hline
  1.3099 +(KKT.PE) & \verb|pe_ae_max| &
  1.3100 +         Largest absolute error \\
  1.3101 +         & \verb|pe_ae_row| &
  1.3102 +         Number of row with largest absolute error \\
  1.3103 +         & \verb|pe_re_max| &
  1.3104 +         Largest relative error \\
  1.3105 +         & \verb|pe_re_row| &
  1.3106 +         Number of row with largest relative error \\
  1.3107 +         & \verb|pe_quality| &
  1.3108 +         Quality of primal solution \\
  1.3109 +\hline
  1.3110 +(KKT.PB) & \verb|pb_ae_max| &
  1.3111 +         Largest absolute error \\
  1.3112 +         & \verb|pb_ae_ind| &
  1.3113 +         Number of variable with largest absolute error \\
  1.3114 +         & \verb|pb_re_max| &
  1.3115 +         Largest relative error \\
  1.3116 +         & \verb|pb_re_ind| &
  1.3117 +         Number of variable with largest relative error \\
  1.3118 +         & \verb|pb_quality| &
  1.3119 +         Quality of primal feasibility \\
  1.3120 +\hline
  1.3121 +(KKT.DE) & \verb|de_ae_max| &
  1.3122 +         Largest absolute error \\
  1.3123 +         & \verb|de_ae_col| &
  1.3124 +         Number of column with largest absolute error \\
  1.3125 +         & \verb|de_re_max| &
  1.3126 +         Largest relative error \\
  1.3127 +         & \verb|de_re_col| &
  1.3128 +         Number of column with largest relative error \\
  1.3129 +         & \verb|de_quality| &
  1.3130 +         Quality of dual solution \\
  1.3131 +\hline
  1.3132 +(KKT.DB) & \verb|db_ae_max| &
  1.3133 +         Largest absolute error \\
  1.3134 +         & \verb|db_ae_ind| &
  1.3135 +         Number of variable with largest absolute error \\
  1.3136 +         & \verb|db_re_max| &
  1.3137 +         Largest relative error \\
  1.3138 +         & \verb|db_re_ind| &
  1.3139 +         Number of variable with largest relative error \\
  1.3140 +         & \verb|db_quality| &
  1.3141 +         Quality of dual feasibility \\
  1.3142 +\end{tabular}
  1.3143 +\end{center}
  1.3144 +\end{table}
  1.3145 +
  1.3146 +The routine performs all computations using only components of the
  1.3147 +given LP problem and the current basic solution.
  1.3148 +
  1.3149 +\subsubsection*{Background}
  1.3150 +
  1.3151 +The first condition checked by the routine is:
  1.3152 +$$x_R - A x_S = 0, \eqno{\rm (KKT.PE)}$$
  1.3153 +where $x_R$ is the subvector of auxiliary variables (rows), $x_S$ is the
  1.3154 +subvector of structural variables (columns), $A$ is the constraint
  1.3155 +matrix. This condition expresses the requirement that all primal
  1.3156 +variables must satisfy to the system of equality constraints of the
  1.3157 +original LP problem. In case of exact arithmetic this condition would be
  1.3158 +satisfied for any basic solution; however, in case of inexact
  1.3159 +(floating-point) arithmetic, this condition shows how accurate the
  1.3160 +primal basic solution is, that depends on accuracy of a representation
  1.3161 +of the basis matrix used by the simplex method routines.
  1.3162 +
  1.3163 +The second condition checked by the routine is:
  1.3164 +$$l_k \leq x_k \leq u_k {\rm \ \ \ for\ all}\ k=1,\dots,m+n,
  1.3165 +\eqno{\rm (KKT.PB)}$$
  1.3166 +where $x_k$ is auxiliary ($1\leq k\leq m$) or structural
  1.3167 +($m+1\leq k\leq m+n$) variable, $l_k$ and $u_k$ are, respectively,
  1.3168 +lower and upper bounds of the variable $x_k$ (including cases of
  1.3169 +infinite bounds). This condition expresses the requirement that all
  1.3170 +primal variables must satisfy to bound constraints of the original LP
  1.3171 +problem. Since in case of basic solution all non-basic variables are
  1.3172 +placed on their bounds, actually the condition (KKT.PB) needs to be
  1.3173 +checked for basic variables only. If the primal basic solution has
  1.3174 +sufficient accuracy, this condition shows primal feasibility of the
  1.3175 +solution.
  1.3176 +
  1.3177 +The third condition checked by the routine is:
  1.3178 +$${\rm grad}\;Z = c = (\tilde{A})^T \pi + d,$$
  1.3179 +where $Z$ is the objective function, $c$ is the vector of objective
  1.3180 +coefficients, $(\tilde{A})^T$ is a matrix transposed to the expanded
  1.3181 +constraint matrix $\tilde{A} = (I|-A)$, $\pi$ is a vector of Lagrange
  1.3182 +multipliers that correspond to equality constraints of the original LP
  1.3183 +problem, $d$ is a vector of Lagrange multipliers that correspond to
  1.3184 +bound constraints for all (auxiliary and structural) variables of the
  1.3185 +original LP problem. Geometrically the third condition expresses the
  1.3186 +requirement that the gradient of the objective function must belong to
  1.3187 +the orthogonal complement of a linear subspace defined by the equality
  1.3188 +and active bound constraints, i.e. that the gradient must be a linear
  1.3189 +combination of normals to the constraint planes, where Lagrange
  1.3190 +multipliers $\pi$ and $d$ are coefficients of that linear combination.
  1.3191 +
  1.3192 +To eliminate the vector $\pi$ the third condition can be rewritten as:
  1.3193 +$$
  1.3194 +\left(\begin{array}{@{}c@{}}I \\ -A^T\end{array}\right) \pi =
  1.3195 +\left(\begin{array}{@{}c@{}}d_R \\ d_S\end{array}\right) +
  1.3196 +\left(\begin{array}{@{}c@{}}c_R \\ c_S\end{array}\right),
  1.3197 +$$
  1.3198 +or, equivalently:
  1.3199 +$$
  1.3200 +\begin{array}{r@{}c@{}c}
  1.3201 +\pi + d_R&\ =\ &c_R, \\
  1.3202 +-A^T\pi + d_S&\ =\ &c_S. \\
  1.3203 +\end{array}
  1.3204 +$$
  1.3205 +Then substituting the vector $\pi$ from the first equation into the
  1.3206 +second one we have:
  1.3207 +$$A^T (d_R - c_R) + (d_S - c_S) = 0, \eqno{\rm (KKT.DE)}$$
  1.3208 +where $d_R$ is the subvector of reduced costs of auxiliary variables
  1.3209 +(rows), $d_S$ is the subvector of reduced costs of structural variables
  1.3210 +(columns), $c_R$ and $c_S$ are subvectors of objective coefficients at,
  1.3211 +respectively, auxiliary and structural variables, $A^T$ is a matrix
  1.3212 +transposed to the constraint matrix of the original LP problem. In case
  1.3213 +of exact arithmetic this condition would be satisfied for any basic
  1.3214 +solution; however, in case of inexact (floating-point) arithmetic, this
  1.3215 +condition shows how accurate the dual basic solution is, that depends on
  1.3216 +accuracy of a representation of the basis matrix used by the simplex
  1.3217 +method routines.
  1.3218 +
  1.3219 +The last, fourth condition checked by the routine is (KKT.DB):
  1.3220 +
  1.3221 +\medskip
  1.3222 +
  1.3223 +\begin{tabular}{r@{}c@{}ll}
  1.3224 +&$\ d_k\ $& $=0,$&if $x_k$ is basic or free non-basic variable \\
  1.3225 +$0\leq$&$\ d_k\ $&$<+\infty$&if $x_k$ is non-basic on its lower
  1.3226 +(minimization) \\
  1.3227 +&&&or upper (maximization) bound \\
  1.3228 +$-\infty<$&$\ d_k\ $&$\leq 0$&if $x_k$ is non-basic on its upper
  1.3229 +(minimization) \\
  1.3230 +&&&or lower (maximization) bound \\
  1.3231 +$-\infty<$&$\ d_k\ $&$<+\infty$&if $x_k$ is non-basic fixed variable \\
  1.3232 +\end{tabular}
  1.3233 +
  1.3234 +\medskip
  1.3235 +
  1.3236 +\noindent
  1.3237 +for all $k=1,\dots,m+n$, where $d_k$ is a reduced cost (Lagrange
  1.3238 +multiplier) of auxiliary ($1\leq k\leq m$) or structural
  1.3239 +($m+1\leq k\leq m+n$) variable $x_k$. Geometrically this condition
  1.3240 +expresses the requirement that constraints of the original problem must
  1.3241 +"hold" the point preventing its movement along the anti-gradient (in
  1.3242 +case of minimization) or the gradient (in case of maximization) of the
  1.3243 +objective function. Since in case of basic solution reduced costs of
  1.3244 +all basic variables are placed on their (zero) bounds, actually the
  1.3245 +condition (KKT.DB) needs to be checked for non-basic variables only.
  1.3246 +If the dual basic solution has sufficient accuracy, this condition shows
  1.3247 +dual feasibility of the solution.
  1.3248 +
  1.3249 +Should note that the complete set of Karush-Kuhn-Tucker optimality
  1.3250 +conditions also includes the fifth, so called complementary slackness
  1.3251 +condition, which expresses the requirement that at least either a primal
  1.3252 +variable $x_k$ or its dual counterpart $d_k$ must be on its bound for
  1.3253 +all $k=1,\dots,m+n$. However, being always satisfied by definition for
  1.3254 +any basic solution that condition is not checked by the routine.
  1.3255 +
  1.3256 +To check the first condition (KKT.PE) the routine computes a vector of
  1.3257 +residuals:
  1.3258 +$$g = x_R - A x_S,$$
  1.3259 +determines component of this vector that correspond to largest absolute
  1.3260 +and relative errors:
  1.3261 +
  1.3262 +\medskip
  1.3263 +
  1.3264 +\hspace{30mm}
  1.3265 +\verb|pe_ae_max| $\displaystyle{= \max_{1\leq i\leq m}|g_i|}$,
  1.3266 +
  1.3267 +\medskip
  1.3268 +
  1.3269 +\hspace{30mm}
  1.3270 +\verb|pe_re_max| $\displaystyle{= \max_{1\leq i\leq m}
  1.3271 +\frac{|g_i|}{1+|(x_R)_i|}}$,
  1.3272 +
  1.3273 +\medskip
  1.3274 +
  1.3275 +\noindent
  1.3276 +and stores these quantities and corresponding row indices to the
  1.3277 +structure \verb|LPXKKT|.
  1.3278 +
  1.3279 +To check the second condition (KKT.PB) the routine computes a vector
  1.3280 +of residuals:
  1.3281 +$$
  1.3282 +h_k = \left\{
  1.3283 +\begin{array}{ll}
  1.3284 +0,         & {\rm if}\ l_k \leq x_k \leq u_k \\
  1.3285 +x_k - l_k, & {\rm if}\ x_k < l_k \\
  1.3286 +x_k - u_k, & {\rm if}\ x_k > u_k \\
  1.3287 +\end{array}
  1.3288 +\right.
  1.3289 +$$
  1.3290 +for all $k=1,\dots,m+n$, determines components of this vector that
  1.3291 +correspond to largest absolute and relative errors:
  1.3292 +
  1.3293 +\medskip
  1.3294 +
  1.3295 +\hspace{30mm}
  1.3296 +\verb|pb_ae_max| $\displaystyle{= \max_{1\leq k \leq m+n}|h_k|}$,
  1.3297 +
  1.3298 +\medskip
  1.3299 +
  1.3300 +\hspace{30mm}
  1.3301 +\verb|pb_re_max| $\displaystyle{= \max_{1\leq k \leq m+n}
  1.3302 +\frac{|h_k|}{1+|x_k|}}$,
  1.3303 +
  1.3304 +\medskip
  1.3305 +
  1.3306 +\noindent
  1.3307 +and stores these quantities and corresponding variable indices to the
  1.3308 +structure \verb|LPXKKT|.
  1.3309 +
  1.3310 +To check the third condition (KKT.DE) the routine computes a vector of
  1.3311 +residuals:
  1.3312 +$$u = A^T (d_R - c_R) + (d_S - c_S),$$
  1.3313 +determines components of this vector that correspond to largest
  1.3314 +absolute and relative errors:
  1.3315 +
  1.3316 +\medskip
  1.3317 +
  1.3318 +\hspace{30mm}
  1.3319 +\verb|de_ae_max| $\displaystyle{= \max_{1\leq j\leq n}|u_j|}$,
  1.3320 +
  1.3321 +\medskip
  1.3322 +
  1.3323 +\hspace{30mm}
  1.3324 +\verb|de_re_max| $\displaystyle{= \max_{1\leq j\leq n}
  1.3325 +\frac{|u_j|}{1+|(d_S)_j - (c_S)_j|}}$,
  1.3326 +
  1.3327 +\medskip
  1.3328 +
  1.3329 +\noindent
  1.3330 +and stores these quantities and corresponding column indices to the
  1.3331 +structure \verb|LPXKKT|.
  1.3332 +
  1.3333 +To check the fourth condition (KKT.DB) the routine computes a vector
  1.3334 +of residuals:
  1.3335 +
  1.3336 +$$
  1.3337 +v_k = \left\{
  1.3338 +\begin{array}{ll}
  1.3339 +0,         & {\rm if}\ d_k\ {\rm has\ correct\ sign} \\
  1.3340 +d_k,       & {\rm if}\ d_k\ {\rm has\ wrong\ sign} \\
  1.3341 +\end{array}
  1.3342 +\right.
  1.3343 +$$
  1.3344 +for all $k=1,\dots,m+n$, determines components of this vector that
  1.3345 +correspond to largest absolute and relative errors:
  1.3346 +
  1.3347 +\medskip
  1.3348 +
  1.3349 +\hspace{30mm}
  1.3350 +\verb|db_ae_max| $\displaystyle{= \max_{1\leq k\leq m+n}|v_k|}$,
  1.3351 +
  1.3352 +\medskip
  1.3353 +
  1.3354 +\hspace{30mm}
  1.3355 +\verb|db_re_max| $\displaystyle{= \max_{1\leq k\leq m+n}
  1.3356 +\frac{|v_k|}{1+|d_k - c_k|}}$,
  1.3357 +
  1.3358 +\medskip
  1.3359 +
  1.3360 +\noindent
  1.3361 +and stores these quantities and corresponding variable indices to the
  1.3362 +structure \verb|LPXKKT|.
  1.3363 +
  1.3364 +Using the relative errors for all the four conditions listed above the
  1.3365 +routine
  1.3366 +\verb|lpx_check_kkt| also estimates a "quality" of the basic solution
  1.3367 +from the standpoint of these conditions and stores corresponding
  1.3368 +quality indicators to the structure \verb|LPXKKT|:
  1.3369 +
  1.3370 +\verb|pe_quality|---quality of primal solution;
  1.3371 +
  1.3372 +\verb|pb_quality|---quality of primal feasibility;
  1.3373 +
  1.3374 +\verb|de_quality|---quality of dual solution;
  1.3375 +
  1.3376 +\verb|db_quality|---quality of dual feasibility.
  1.3377 +
  1.3378 +Each of these indicators is assigned to one of the following four
  1.3379 +values:
  1.3380 +
  1.3381 +\verb|'H'| means high quality,
  1.3382 +
  1.3383 +\verb|'M'| means medium quality,
  1.3384 +
  1.3385 +\verb|'L'| means low quality, or
  1.3386 +
  1.3387 +\verb|'?'| means wrong or infeasible solution.
  1.3388 +
  1.3389 +If all the indicators show high or medium quality (for an internally
  1.3390 +scaled LP problem, i.e. when the parameter \verb|scaled| in a call to
  1.3391 +the routine \verb|lpx_check_kkt| is non-zero), the user can be sure that
  1.3392 +the obtained basic solution is quite accurate.
  1.3393 +
  1.3394 +If some of the indicators show low quality, the solution can still be
  1.3395 +considered as relevant, though an additional analysis is needed
  1.3396 +depending on which indicator shows low quality.
  1.3397 +
  1.3398 +If the indicator \verb|pe_quality| is assigned to \verb|'?'|, the
  1.3399 +primal solution is wrong. If the indicator \verb|de_quality| is assigned
  1.3400 +to \verb|'?'|, the dual solution is wrong.
  1.3401 +
  1.3402 +If the indicator \verb|db_quality| is assigned to \verb|'?'| while
  1.3403 +other indicators show a good quality, this means that the current
  1.3404 +basic solution being primal feasible is not dual feasible. Similarly,
  1.3405 +if the indicator \verb|pb_quality| is assigned to \verb|'?'| while
  1.3406 +other indicators are not, this means that the current basic solution
  1.3407 +being dual feasible is not primal feasible.
  1.3408 +
  1.3409 +%* eof *%