lemon-project-template-glpk
diff deps/glpk/doc/glpk02.tex @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
line diff
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 *%