1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/doc/glpk03.tex Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,1577 @@
1.4 +%* glpk03.tex *%
1.5 +
1.6 +\chapter{Utility API routines}
1.7 +
1.8 +\section{Problem data reading/writing routines}
1.9 +
1.10 +\subsection{glp\_read\_mps---read problem data in MPS format}
1.11 +
1.12 +\subsubsection*{Synopsis}
1.13 +
1.14 +\begin{verbatim}
1.15 +int glp_read_mps(glp_prob *lp, int fmt, const void *parm,
1.16 + const char *fname);
1.17 +\end{verbatim}
1.18 +
1.19 +\subsubsection*{Description}
1.20 +
1.21 +The routine \verb|glp_read_mps| reads problem data in MPS format from a
1.22 +text file. (The MPS format is described in Appendix \ref{champs}, page
1.23 +\pageref{champs}.)
1.24 +
1.25 +The parameter \verb|fmt| specifies the MPS format version as follows:
1.26 +
1.27 +\begin{tabular}{@{}ll}
1.28 +\verb|GLP_MPS_DECK| & fixed (ancient) MPS format; \\
1.29 +\verb|GLP_MPS_FILE| & free (modern) MPS format. \\
1.30 +\end{tabular}
1.31 +
1.32 +The parameter \verb|parm| is reserved for use in the future and must be
1.33 +specified as \verb|NULL|.
1.34 +
1.35 +The character string \verb|fname| specifies a name of the text file to
1.36 +be read in. (If the file name ends with suffix `\verb|.gz|', the file is
1.37 +assumed to be compressed, in which case the routine \verb|glp_read_mps|
1.38 +decompresses it ``on the fly''.)
1.39 +
1.40 +Note that before reading data the current content of the problem object
1.41 +is completely erased with the routine \verb|glp_erase_prob|.
1.42 +
1.43 +\subsubsection*{Returns}
1.44 +
1.45 +If the operation was successful, the routine \verb|glp_read_mps|
1.46 +returns zero. Otherwise, it prints an error message and returns
1.47 +non-zero.
1.48 +
1.49 +\subsection{glp\_write\_mps---write problem data in MPS format}
1.50 +
1.51 +\subsubsection*{Synopsis}
1.52 +
1.53 +\begin{verbatim}
1.54 +int glp_write_mps(glp_prob *lp, int fmt, const void *parm,
1.55 + const char *fname);
1.56 +\end{verbatim}
1.57 +
1.58 +\subsubsection*{Description}
1.59 +
1.60 +The routine \verb|glp_write_mps| writes problem data in MPS format to a
1.61 +text file. (The MPS format is described in Appendix \ref{champs}, page
1.62 +\pageref{champs}.)
1.63 +
1.64 +The parameter \verb|fmt| specifies the MPS format version as follows:
1.65 +
1.66 +\begin{tabular}{@{}ll}
1.67 +\verb|GLP_MPS_DECK| & fixed (ancient) MPS format; \\
1.68 +\verb|GLP_MPS_FILE| & free (modern) MPS format. \\
1.69 +\end{tabular}
1.70 +
1.71 +The parameter \verb|parm| is reserved for use in the future and must be
1.72 +specified as \verb|NULL|.
1.73 +
1.74 +The character string \verb|fname| specifies a name of the text file to
1.75 +be written out. (If the file name ends with suffix `\verb|.gz|', the
1.76 +file is assumed to be compressed, in which case the routine
1.77 +\verb|glp_write_mps| performs automatic compression on writing it.)
1.78 +
1.79 +\subsubsection*{Returns}
1.80 +
1.81 +If the operation was successful, the routine \verb|glp_write_mps|
1.82 +returns zero. Otherwise, it prints an error message and returns
1.83 +non-zero.
1.84 +
1.85 +\subsection{glp\_read\_lp---read problem data in CPLEX LP format}
1.86 +
1.87 +\subsubsection*{Synopsis}
1.88 +
1.89 +\begin{verbatim}
1.90 +int glp_read_lp(glp_prob *lp, const void *parm,
1.91 + const char *fname);
1.92 +\end{verbatim}
1.93 +
1.94 +\subsubsection*{Description}
1.95 +
1.96 +The routine \verb|glp_read_lp| reads problem data in CPLEX LP format
1.97 +from a text file. (The CPLEX LP format is described in Appendix
1.98 +\ref{chacplex}, page \pageref{chacplex}.)
1.99 +
1.100 +The parameter \verb|parm| is reserved for use in the future and must be
1.101 +specified as \verb|NULL|.
1.102 +
1.103 +The character string \verb|fname| specifies a name of the text file to
1.104 +be read in. (If the file name ends with suffix `\verb|.gz|', the file is
1.105 +assumed to be compressed, in which case the routine \verb|glp_read_lp|
1.106 +decompresses it ``on the fly''.)
1.107 +
1.108 +Note that before reading data the current content of the problem object
1.109 +is completely erased with the routine \verb|glp_erase_prob|.
1.110 +
1.111 +\subsubsection*{Returns}
1.112 +
1.113 +If the operation was successful, the routine \verb|glp_read_lp| returns
1.114 +zero. Otherwise, it prints an error message and returns non-zero.
1.115 +
1.116 +\subsection{glp\_write\_lp---write problem data in CPLEX LP format}
1.117 +
1.118 +\subsubsection*{Synopsis}
1.119 +
1.120 +\begin{verbatim}
1.121 +int glp_write_lp(glp_prob *lp, const void *parm,
1.122 + const char *fname);
1.123 +\end{verbatim}
1.124 +
1.125 +\subsubsection*{Description}
1.126 +
1.127 +The routine \verb|glp_write_lp| writes problem data in CPLEX LP format
1.128 +to a text file. (The CPLEX LP format is described in Appendix
1.129 +\ref{chacplex}, page \pageref{chacplex}.)
1.130 +
1.131 +The parameter \verb|parm| is reserved for use in the future and must be
1.132 +specified as \verb|NULL|.
1.133 +
1.134 +The character string \verb|fname| specifies a name of the text file to
1.135 +be written out. (If the file name ends with suffix `\verb|.gz|', the
1.136 +file is assumed to be compressed, in which case the routine
1.137 +\verb|glp_write_lp| performs automatic compression on writing it.)
1.138 +
1.139 +\subsubsection*{Returns}
1.140 +
1.141 +If the operation was successful, the routine \verb|glp_write_lp|
1.142 +returns zero. Otherwise, it prints an error message and returns
1.143 +non-zero.
1.144 +
1.145 +\subsection{glp\_read\_prob---read problem data in GLPK format}
1.146 +
1.147 +\subsubsection*{Synopsis}
1.148 +
1.149 +\begin{verbatim}
1.150 +int glp_read_prob(glp_prob *P, int flags, const char *fname);
1.151 +\end{verbatim}
1.152 +
1.153 +\subsubsection*{Description}
1.154 +
1.155 +The routine \verb|glp_read_prob| reads problem data in the GLPK LP/MIP
1.156 +format from a text file. (For description of the GLPK LP/MIP format see
1.157 +below.)
1.158 +
1.159 +The parameter \verb|flags| is reserved for use in the future and should
1.160 +be specified as zero.
1.161 +
1.162 +The character string \verb|fname| specifies a name of the text file to
1.163 +be read in. (If the file name ends with suffix `\verb|.gz|', the file
1.164 +is assumed to be compressed, in which case the routine
1.165 +\verb|glp_read_prob| decompresses it ``on the fly''.)
1.166 +
1.167 +Note that before reading data the current content of the problem object
1.168 +is completely erased with the routine \verb|glp_erase_prob|.
1.169 +
1.170 +\subsubsection*{Returns}
1.171 +
1.172 +If the operation was successful, the routine \verb|glp_read_prob|
1.173 +returns zero. Otherwise, it prints an error message and returns
1.174 +non-zero.
1.175 +
1.176 +\subsubsection*{GLPK LP/MIP format}
1.177 +
1.178 +The GLPK LP/MIP format is a DIMACS-like format.\footnote{The DIMACS
1.179 +formats were developed by the Center for Discrete Mathematics and
1.180 +Theoretical Computer Science (DIMACS) to facilitate exchange of problem
1.181 +data. For details see: {\tt <http://dimacs.rutgers.edu/Challenges/>}. }
1.182 +The file in this format is a plain ASCII text file containing lines of
1.183 +several types described below. A line is terminated with the end-of-line
1.184 +character. Fields in each line are separated by at least one blank
1.185 +space. Each line begins with a one-character designator to identify the
1.186 +line type.
1.187 +
1.188 +The first line of the data file must be the problem line (except
1.189 +optional comment lines, which may precede the problem line). The last
1.190 +line of the data file must be the end line. Other lines may follow in
1.191 +arbitrary order, however, duplicate lines are not allowed.
1.192 +
1.193 +\paragraph{Comment lines.} Comment lines give human-readable
1.194 +information about the data file and are ignored by GLPK routines.
1.195 +Comment lines can appear anywhere in the data file. Each comment line
1.196 +begins with the lower-case character \verb|c|.
1.197 +
1.198 +\begin{verbatim}
1.199 + c This is an example of comment line
1.200 +\end{verbatim}
1.201 +
1.202 +\paragraph{Problem line.} There must be exactly one problem line in the
1.203 +data file. This line must appear before any other lines except comment
1.204 +lines and has the following format:
1.205 +
1.206 +\begin{verbatim}
1.207 + p CLASS DIR ROWS COLS NONZ
1.208 +\end{verbatim}
1.209 +
1.210 +The lower-case letter \verb|p| specifies that this is the problem line.
1.211 +
1.212 +The \verb|CLASS| field defines the problem class and can contain either
1.213 +the keyword \verb|lp| (that means linear programming problem) or
1.214 +\verb|mip| (that means mixed integer programming problem).
1.215 +
1.216 +The \verb|DIR| field defines the optimization direction (that is, the
1.217 +objective function sense) and can contain either the keyword \verb|min|
1.218 +(that means minimization) or \verb|max| (that means maximization).
1.219 +
1.220 +The \verb|ROWS|, \verb|COLS|, and \verb|NONZ| fields contain
1.221 +non-negative integer values specifying, respectively, the number of
1.222 +rows (constraints), columns (variables), and non-zero constraint
1.223 +coefficients in the problem instance. Note that \verb|NONZ| value does
1.224 +not account objective coefficients.
1.225 +
1.226 +\paragraph{Row descriptors.} There must be at most one row descriptor
1.227 +line in the data file for each row (constraint). This line has one of
1.228 +the following formats:
1.229 +
1.230 +\begin{verbatim}
1.231 + i ROW f
1.232 + i ROW l RHS
1.233 + i ROW u RHS
1.234 + i ROW d RHS1 RHS2
1.235 + i ROW s RHS
1.236 +\end{verbatim}
1.237 +
1.238 +The lower-case letter \verb|i| specifies that this is the row
1.239 +descriptor line.
1.240 +
1.241 +The \verb|ROW| field specifies the row ordinal number, an integer
1.242 +between 1 and $m$, where $m$ is the number of rows in the problem
1.243 +instance.
1.244 +
1.245 +The next lower-case letter specifies the row type as follows:
1.246 +
1.247 +\verb|f| --- free (unbounded) row: $-\infty<\sum a_jx_j<+\infty$;
1.248 +
1.249 +\verb|l| --- inequality constraint of `$\geq$' type:
1.250 +$\sum a_jx_j\geq b$;
1.251 +
1.252 +\verb|u| --- inequality constraint of `$\leq$' type:
1.253 +$\sum a_jx_j\leq b$;
1.254 +
1.255 +\verb|d| --- double-sided inequality constraint:
1.256 +$b_1\leq\sum a_jx_j\leq b_2$;
1.257 +
1.258 +\verb|s| --- equality constraint: $\sum a_jx_j=b$.
1.259 +
1.260 +The \verb|RHS| field contains a floaing-point value specifying the
1.261 +row right-hand side. The \verb|RHS1| and \verb|RHS2| fields contain
1.262 +floating-point values specifying, respectively, the lower and upper
1.263 +right-hand sides for the double-sided row.
1.264 +
1.265 +If for some row its descriptor line does not appear in the data file,
1.266 +by default that row is assumed to be an equality constraint with zero
1.267 +right-hand side.
1.268 +
1.269 +\paragraph{Column descriptors.} There must be at most one column
1.270 +descriptor line in the data file for each column (variable). This line
1.271 +has one of the following formats depending on the problem class
1.272 +specified in the problem line:
1.273 +
1.274 +\bigskip
1.275 +
1.276 +\begin{tabular}{@{}l@{\hspace*{40pt}}l}
1.277 +LP class & MIP class \\
1.278 +\hline
1.279 +\verb|j COL f| & \verb|j COL KIND f| \\
1.280 +\verb|j COL l BND| & \verb|j COL KIND l BND| \\
1.281 +\verb|j COL u BND| & \verb|j COL KIND u BND| \\
1.282 +\verb|j COL d BND1 BND2| & \verb|j COL KIND d BND1 BND2| \\
1.283 +\verb|j COL s BND| & \verb|j COL KIND s BND| \\
1.284 +\end{tabular}
1.285 +
1.286 +\bigskip
1.287 +
1.288 +The lower-case letter \verb|j| specifies that this is the column
1.289 +descriptor line.
1.290 +
1.291 +The \verb|COL| field specifies the column ordinal number, an integer
1.292 +between 1 and $n$, where $n$ is the number of columns in the problem
1.293 +instance.
1.294 +
1.295 +The \verb|KIND| field is used only for MIP problems and specifies the
1.296 +column kind as follows:
1.297 +
1.298 +\verb|c| --- continuous column;
1.299 +
1.300 +\verb|i| --- integer column;
1.301 +
1.302 +\verb|b| --- binary column (in this case all remaining fields must be
1.303 +omitted).
1.304 +
1.305 +The next lower-case letter specifies the column type as follows:
1.306 +
1.307 +\verb|f| --- free (unbounded) column: $-\infty<x<+\infty$;
1.308 +
1.309 +\verb|l| --- column with lower bound: $x\geq l$;
1.310 +
1.311 +\verb|u| --- column with upper bound: $x\leq u$;
1.312 +
1.313 +\verb|d| --- double-bounded column: $l\leq x\leq u$;
1.314 +
1.315 +\verb|s| --- fixed column: $x=s$.
1.316 +
1.317 +The \verb|BND| field contains a floating-point value that specifies the
1.318 +column bound. The \verb|BND1| and \verb|BND2| fields contain
1.319 +floating-point values specifying, respectively, the lower and upper
1.320 +bounds for the double-bounded column.
1.321 +
1.322 +If for some column its descriptor line does not appear in the file, by
1.323 +default that column is assumed to be non-negative (in case of LP class)
1.324 +or binary (in case of MIP class).
1.325 +
1.326 +\paragraph{Coefficient descriptors.} There must be exactly one
1.327 +coefficient descriptor line in the data file for each non-zero
1.328 +objective or constraint coefficient. This line has the following format:
1.329 +
1.330 +\begin{verbatim}
1.331 + a ROW COL VAL
1.332 +\end{verbatim}
1.333 +
1.334 +The lower-case letter \verb|a| specifies that this is the coefficient
1.335 +descriptor line.
1.336 +
1.337 +For objective coefficients the \verb|ROW| field must contain 0. For
1.338 +constraint coefficients the \verb|ROW| field specifies the row ordinal
1.339 +number, an integer between 1 and $m$, where $m$ is the number of rows
1.340 +in the problem instance.
1.341 +
1.342 +The \verb|COL| field specifies the column ordinal number, an integer
1.343 +between 1 and $n$, where $n$ is the number of columns in the problem
1.344 +instance.
1.345 +
1.346 +If both the \verb|ROW| and \verb|COL| fields contain 0, the line
1.347 +specifies the constant term (``shift'') of the objective function
1.348 +rather than objective coefficient.
1.349 +
1.350 +The \verb|VAL| field contains a floating-point coefficient value (it is
1.351 +allowed to specify zero value in this field).
1.352 +
1.353 +The number of constraint coefficient descriptor lines must be exactly
1.354 +the same as specified in the field \verb|NONZ| of the problem line.
1.355 +
1.356 +\paragraph{Symbolic name descriptors.} There must be at most one
1.357 +symbolic name descriptor line for the problem instance, objective
1.358 +function, each row (constraint), and each column (variable). This line
1.359 +has one of the following formats:
1.360 +
1.361 +\begin{verbatim}
1.362 + n p NAME
1.363 + n z NAME
1.364 + n i ROW NAME
1.365 + n j COL NAME
1.366 +\end{verbatim}
1.367 +
1.368 +The lower-case letter \verb|n| specifies that this is the symbolic name
1.369 +descriptor line.
1.370 +
1.371 +The next lower-case letter specifies which object should be assigned a
1.372 +symbolic name:
1.373 +
1.374 +\verb|p| --- problem instance;
1.375 +
1.376 +\verb|z| --- objective function;
1.377 +
1.378 +\verb|i| --- row (constraint);
1.379 +
1.380 +\verb|j| --- column (variable).
1.381 +
1.382 +The \verb|ROW| field specifies the row ordinal number, an integer
1.383 +between 1 and $m$, where $m$ is the number of rows in the problem
1.384 +instance.
1.385 +
1.386 +The \verb|COL| field specifies the column ordinal number, an integer
1.387 +between 1 and $n$, where $n$ is the number of columns in the problem
1.388 +instance.
1.389 +
1.390 +The \verb|NAME| field contains the symbolic name, a sequence from 1 to
1.391 +255 arbitrary graphic ASCII characters, assigned to corresponding
1.392 +object.
1.393 +
1.394 +\paragraph{End line.} There must be exactly one end line in the data
1.395 +file. This line must appear last in the file and has the following
1.396 +format:
1.397 +
1.398 +\begin{verbatim}
1.399 + e
1.400 +\end{verbatim}
1.401 +
1.402 +The lower-case letter \verb|e| specifies that this is the end line.
1.403 +Anything that follows the end line is ignored by GLPK routines.
1.404 +
1.405 +\subsubsection*{Example of data file in GLPK LP/MIP format}
1.406 +
1.407 +The following example of a data file in GLPK LP/MIP format specifies
1.408 +the same LP problem as in Subsection ``Example of MPS file''.
1.409 +
1.410 +\begin{center}
1.411 +\footnotesize\tt
1.412 +\begin{tabular}{l@{\hspace*{50pt}}}
1.413 +p lp min 8 7 48 \\
1.414 +n p PLAN \\
1.415 +n z VALUE \\
1.416 +i 1 f \\
1.417 +n i 1 VALUE \\
1.418 +i 2 s 2000 \\
1.419 +n i 2 YIELD \\
1.420 +i 3 u 60 \\
1.421 +n i 3 FE \\
1.422 +i 4 u 100 \\
1.423 +n i 4 CU \\
1.424 +i 5 u 40 \\
1.425 +n i 5 MN \\
1.426 +i 6 u 30 \\
1.427 +n i 6 MG \\
1.428 +i 7 l 1500 \\
1.429 +n i 7 AL \\
1.430 +i 8 d 250 300 \\
1.431 +n i 8 SI \\
1.432 +j 1 d 0 200 \\
1.433 +n j 1 BIN1 \\
1.434 +j 2 d 0 2500 \\
1.435 +n j 2 BIN2 \\
1.436 +j 3 d 400 800 \\
1.437 +n j 3 BIN3 \\
1.438 +j 4 d 100 700 \\
1.439 +n j 4 BIN4 \\
1.440 +j 5 d 0 1500 \\
1.441 +n j 5 BIN5 \\
1.442 +n j 6 ALUM \\
1.443 +n j 7 SILICON \\
1.444 +a 0 1 0.03 \\
1.445 +a 0 2 0.08 \\
1.446 +a 0 3 0.17 \\
1.447 +a 0 4 0.12 \\
1.448 +a 0 5 0.15 \\
1.449 +a 0 6 0.21 \\
1.450 +a 0 7 0.38 \\
1.451 +a 1 1 0.03 \\
1.452 +a 1 2 0.08 \\
1.453 +a 1 3 0.17 \\
1.454 +a 1 4 0.12 \\
1.455 +a 1 5 0.15 \\
1.456 +a 1 6 0.21 \\
1.457 +\end{tabular}
1.458 +\begin{tabular}{|@{\hspace*{80pt}}l}
1.459 +a 1 7 0.38 \\
1.460 +a 2 1 1 \\
1.461 +a 2 2 1 \\
1.462 +a 2 3 1 \\
1.463 +a 2 4 1 \\
1.464 +a 2 5 1 \\
1.465 +a 2 6 1 \\
1.466 +a 2 7 1 \\
1.467 +a 3 1 0.15 \\
1.468 +a 3 2 0.04 \\
1.469 +a 3 3 0.02 \\
1.470 +a 3 4 0.04 \\
1.471 +a 3 5 0.02 \\
1.472 +a 3 6 0.01 \\
1.473 +a 3 7 0.03 \\
1.474 +a 4 1 0.03 \\
1.475 +a 4 2 0.05 \\
1.476 +a 4 3 0.08 \\
1.477 +a 4 4 0.02 \\
1.478 +a 4 5 0.06 \\
1.479 +a 4 6 0.01 \\
1.480 +a 5 1 0.02 \\
1.481 +a 5 2 0.04 \\
1.482 +a 5 3 0.01 \\
1.483 +a 5 4 0.02 \\
1.484 +a 5 5 0.02 \\
1.485 +a 6 1 0.02 \\
1.486 +a 6 2 0.03 \\
1.487 +a 6 5 0.01 \\
1.488 +a 7 1 0.7 \\
1.489 +a 7 2 0.75 \\
1.490 +a 7 3 0.8 \\
1.491 +a 7 4 0.75 \\
1.492 +a 7 5 0.8 \\
1.493 +a 7 6 0.97 \\
1.494 +a 8 1 0.02 \\
1.495 +a 8 2 0.06 \\
1.496 +a 8 3 0.08 \\
1.497 +a 8 4 0.12 \\
1.498 +a 8 5 0.02 \\
1.499 +a 8 6 0.01 \\
1.500 +a 8 7 0.97 \\
1.501 +e o f \\
1.502 +\\
1.503 +\end{tabular}
1.504 +\end{center}
1.505 +
1.506 +\newpage
1.507 +
1.508 +\subsection{glp\_write\_prob---write problem data in GLPK format}
1.509 +
1.510 +\subsubsection*{Synopsis}
1.511 +
1.512 +\begin{verbatim}
1.513 +int glp_write_prob(glp_prob *P, int flags, const char *fname);
1.514 +\end{verbatim}
1.515 +
1.516 +\subsubsection*{Description}
1.517 +
1.518 +The routine \verb|glp_write_prob| writes problem data in the GLPK
1.519 +LP/MIP format to a text file. (For description of the GLPK LP/MIP
1.520 +format see Subsection ``Read problem data in GLPK format''.)
1.521 +
1.522 +The parameter \verb|flags| is reserved for use in the future and should
1.523 +be specified as zero.
1.524 +
1.525 +The character string \verb|fname| specifies a name of the text file to
1.526 +be written out. (If the file name ends with suffix `\verb|.gz|', the
1.527 +file is assumed to be compressed, in which case the routine
1.528 +\verb|glp_write_prob| performs automatic compression on writing it.)
1.529 +
1.530 +\subsubsection*{Returns}
1.531 +
1.532 +If the operation was successful, the routine \verb|glp_read_prob|
1.533 +returns zero. Otherwise, it prints an error message and returns
1.534 +non-zero.
1.535 +
1.536 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1.537 +
1.538 +\newpage
1.539 +
1.540 +\section{Routines for processing MathProg models}
1.541 +
1.542 +\subsection{Introduction}
1.543 +
1.544 +GLPK supports the {\it GNU MathProg modeling language}.\footnote{The
1.545 +GNU MathProg modeling language is a subset of the AMPL language. For
1.546 +its detailed description see the document ``Modeling Language GNU
1.547 +MathProg: Language Reference'' included in the GLPK distribution.}
1.548 +As a rule, models written in MathProg are solved with the GLPK LP/MIP
1.549 +stand-alone solver \verb|glpsol| (see Appendix D) and do not need any
1.550 +programming with API routines. However, for various reasons the user
1.551 +may need to process MathProg models directly in his/her application
1.552 +program, in which case he/she may use API routines described in this
1.553 +section. These routines provide an interface to the {\it MathProg
1.554 +translator}, a component of GLPK, which translates MathProg models into
1.555 +an internal code and then interprets (executes) this code.
1.556 +
1.557 +The processing of a model written in GNU MathProg includes several
1.558 +steps, which should be performed in the following order:
1.559 +
1.560 +\begin{enumerate}
1.561 +\item{\it Allocating the workspace.}
1.562 +The translator allocates the workspace, an internal data structure used
1.563 +on all subsequent steps.
1.564 +\item{\it Reading model section.} The translator reads model section
1.565 +and, optionally, data section from a specified text file and translates
1.566 +them into the internal code. If necessary, on this step data section
1.567 +may be ignored.
1.568 +\item{\it Reading data section(s).} The translator reads one or more
1.569 +data sections from specified text file(s) and translates them into the
1.570 +internal code.
1.571 +\item{\it Generating the model.} The translator executes the internal
1.572 +code to evaluate the content of the model objects such as sets,
1.573 +parameters, variables, constraints, and objectives. On this step the
1.574 +execution is suspended at the solve statement.
1.575 +\item {\it Building the problem object.} The translator obtains all
1.576 +necessary information from the workspace and builds the standard
1.577 +problem object (that is, the program object of type \verb|glp_prob|).
1.578 +\item{\it Solving the problem.} On this step the problem object built
1.579 +on the previous step is passed to a solver, which solves the problem
1.580 +instance and stores its solution back to the problem object.
1.581 +\item{\it Postsolving the model.} The translator copies the solution
1.582 +from the problem object to the workspace and then executes the internal
1.583 +code from the solve statement to the end of the model. (If model has
1.584 +no solve statement, the translator does nothing on this step.)
1.585 +\item{\it Freeing the workspace.} The translator frees all the memory
1.586 +allocated to the workspace.
1.587 +\end{enumerate}
1.588 +
1.589 +Note that the MathProg translator performs no error correction, so if
1.590 +any of steps 2 to 7 fails (due to errors in the model), the application
1.591 +program should terminate processing and go to step 8.
1.592 +
1.593 +\subsubsection*{Example 1}
1.594 +
1.595 +In this example the program reads model and data sections from input
1.596 +file \verb|egypt.mod|\footnote{This is an example model included in
1.597 +the GLPK distribution.} and writes the model to output file
1.598 +\verb|egypt.mps| in free MPS format (see Appendix B). No solution is
1.599 +performed.
1.600 +
1.601 +\begin{small}
1.602 +\begin{verbatim}
1.603 +/* mplsamp1.c */
1.604 +
1.605 +#include <stdio.h>
1.606 +#include <stdlib.h>
1.607 +#include <glpk.h>
1.608 +
1.609 +int main(void)
1.610 +{ glp_prob *lp;
1.611 + glp_tran *tran;
1.612 + int ret;
1.613 + lp = glp_create_prob();
1.614 + tran = glp_mpl_alloc_wksp();
1.615 + ret = glp_mpl_read_model(tran, "egypt.mod", 0);
1.616 + if (ret != 0)
1.617 + { fprintf(stderr, "Error on translating model\n");
1.618 + goto skip;
1.619 + }
1.620 + ret = glp_mpl_generate(tran, NULL);
1.621 + if (ret != 0)
1.622 + { fprintf(stderr, "Error on generating model\n");
1.623 + goto skip;
1.624 + }
1.625 + glp_mpl_build_prob(tran, lp);
1.626 + ret = glp_write_mps(lp, GLP_MPS_FILE, NULL, "egypt.mps");
1.627 + if (ret != 0)
1.628 + fprintf(stderr, "Error on writing MPS file\n");
1.629 +skip: glp_mpl_free_wksp(tran);
1.630 + glp_delete_prob(lp);
1.631 + return 0;
1.632 +}
1.633 +
1.634 +/* eof */
1.635 +\end{verbatim}
1.636 +\end{small}
1.637 +
1.638 +\subsubsection*{Example 2}
1.639 +
1.640 +In this example the program reads model section from file
1.641 +\verb|sudoku.mod|\footnote{This is an example model which is included
1.642 +in the GLPK distribution along with alternative data file
1.643 +{\tt sudoku.dat}.} ignoring data section in this file, reads alternative
1.644 +data section from file \verb|sudoku.dat|, solves the problem instance
1.645 +and passes the solution found back to the model.
1.646 +
1.647 +\begin{small}
1.648 +\begin{verbatim}
1.649 +/* mplsamp2.c */
1.650 +
1.651 +#include <stdio.h>
1.652 +#include <stdlib.h>
1.653 +#include <glpk.h>
1.654 +
1.655 +int main(void)
1.656 +{ glp_prob *mip;
1.657 + glp_tran *tran;
1.658 + int ret;
1.659 + mip = glp_create_prob();
1.660 + tran = glp_mpl_alloc_wksp();
1.661 + ret = glp_mpl_read_model(tran, "sudoku.mod", 1);
1.662 + if (ret != 0)
1.663 + { fprintf(stderr, "Error on translating model\n");
1.664 + goto skip;
1.665 + }
1.666 + ret = glp_mpl_read_data(tran, "sudoku.dat");
1.667 + if (ret != 0)
1.668 + { fprintf(stderr, "Error on translating data\n");
1.669 + goto skip;
1.670 + }
1.671 + ret = glp_mpl_generate(tran, NULL);
1.672 + if (ret != 0)
1.673 + { fprintf(stderr, "Error on generating model\n");
1.674 + goto skip;
1.675 + }
1.676 + glp_mpl_build_prob(tran, mip);
1.677 + glp_simplex(mip, NULL);
1.678 + glp_intopt(mip, NULL);
1.679 + ret = glp_mpl_postsolve(tran, mip, GLP_MIP);
1.680 + if (ret != 0)
1.681 + fprintf(stderr, "Error on postsolving model\n");
1.682 +skip: glp_mpl_free_wksp(tran);
1.683 + glp_delete_prob(mip);
1.684 + return 0;
1.685 +}
1.686 +
1.687 +/* eof */
1.688 +\end{verbatim}
1.689 +\end{small}
1.690 +
1.691 +\subsection{glp\_mpl\_alloc\_wksp---allocate the translator workspace}
1.692 +
1.693 +\subsubsection*{Synopsis}
1.694 +
1.695 +\begin{verbatim}
1.696 +glp_tran *glp_mpl_alloc_wksp(void);
1.697 +\end{verbatim}
1.698 +
1.699 +\subsubsection*{Description}
1.700 +
1.701 +The routine \verb|glp_mpl_alloc_wksp| allocates the MathProg translator
1.702 +work\-space. (Note that multiple instances of the workspace may be
1.703 +allocated, if necessary.)
1.704 +
1.705 +\subsubsection*{Returns}
1.706 +
1.707 +The routine returns a pointer to the workspace, which should be used in
1.708 +all subsequent operations.
1.709 +
1.710 +\subsection{glp\_mpl\_read\_model---read and translate model section}
1.711 +
1.712 +\subsubsection*{Synopsis}
1.713 +
1.714 +\begin{verbatim}
1.715 +int glp_mpl_read_model(glp_tran *tran, const char *fname,
1.716 + int skip);
1.717 +\end{verbatim}
1.718 +
1.719 +\subsubsection*{Description}
1.720 +
1.721 +The routine \verb|glp_mpl_read_model| reads model section and,
1.722 +optionally, data section, which may follow the model section, from a
1.723 +text file, whose name is the character string \verb|fname|, performs
1.724 +translation of model statements and data blocks, and stores all the
1.725 +information in the workspace.
1.726 +
1.727 +The parameter \verb|skip| is a flag. If the input file contains the
1.728 +data section and this flag is non-zero, the data section is not read as
1.729 +if there were no data section and a warning message is printed. This
1.730 +allows reading data section(s) from other file(s).
1.731 +
1.732 +\subsubsection*{Returns}
1.733 +
1.734 +If the operation is successful, the routine returns zero. Otherwise
1.735 +the routine prints an error message and returns non-zero.
1.736 +
1.737 +\subsection{glp\_mpl\_read\_data---read and translate data section}
1.738 +
1.739 +\subsubsection*{Synopsis}
1.740 +
1.741 +\begin{verbatim}
1.742 +int glp_mpl_read_data(glp_tran *tran, const char *fname);
1.743 +\end{verbatim}
1.744 +
1.745 +\subsubsection*{Description}
1.746 +
1.747 +The routine \verb|glp_mpl_read_data| reads data section from a text
1.748 +file, whose name is the character string \verb|fname|, performs
1.749 +translation of data blocks, and stores the data read in the translator
1.750 +workspace. If necessary, this routine may be called more than once.
1.751 +
1.752 +\subsubsection*{Returns}
1.753 +
1.754 +If the operation is successful, the routine returns zero. Otherwise
1.755 +the routine prints an error message and returns non-zero.
1.756 +
1.757 +\subsection{glp\_mpl\_generate---generate the model}
1.758 +
1.759 +\subsubsection*{Synopsis}
1.760 +
1.761 +\begin{verbatim}
1.762 +int glp_mpl_generate(glp_tran *tran, const char *fname);
1.763 +\end{verbatim}
1.764 +
1.765 +\subsubsection*{Description}
1.766 +
1.767 +The routine \verb|glp_mpl_generate| generates the model using its
1.768 +description stored in the translator workspace. This operation means
1.769 +generating all variables, constraints, and objectives, executing check
1.770 +and display statements, which precede the solve statement (if it is
1.771 +presented).
1.772 +
1.773 +The character string \verb|fname| specifies the name of an output text
1.774 +file, to which output produced by display statements should be written.
1.775 +If \verb|fname| is \verb|NULL|, the output is sent to the terminal.
1.776 +
1.777 +\subsubsection*{Returns}
1.778 +
1.779 +If the operation is successful, the routine returns zero. Otherwise
1.780 +the routine prints an error message and returns non-zero.
1.781 +
1.782 +\subsection{glp\_mpl\_build\_prob---build problem instance from the
1.783 +model}
1.784 +
1.785 +\subsubsection*{Synopsis}
1.786 +
1.787 +\begin{verbatim}
1.788 +void glp_mpl_build_prob(glp_tran *tran, glp_prob *prob);
1.789 +\end{verbatim}
1.790 +
1.791 +\subsubsection*{Description}
1.792 +
1.793 +The routine \verb|glp_mpl_build_prob| obtains all necessary information
1.794 +from the translator workspace and stores it in the specified problem
1.795 +object \verb|prob|. Note that before building the current content of
1.796 +the problem object is erased with the routine \verb|glp_erase_prob|.
1.797 +
1.798 +\subsection{glp\_mpl\_postsolve---postsolve the model}
1.799 +
1.800 +\subsubsection*{Synopsis}
1.801 +
1.802 +\begin{verbatim}
1.803 +int glp_mpl_postsolve(glp_tran *tran, glp_prob *prob,
1.804 + int sol);
1.805 +\end{verbatim}
1.806 +
1.807 +\subsubsection*{Description}
1.808 +
1.809 +The routine \verb|glp_mpl_postsolve| copies the solution from the
1.810 +specified problem object \verb|prob| to the translator workspace and
1.811 +then executes all the remaining model statements, which follow the
1.812 +solve statement.
1.813 +
1.814 +The parameter \verb|sol| specifies which solution should be copied
1.815 +from the problem object to the workspace as follows:
1.816 +
1.817 +\begin{tabular}{@{}ll}
1.818 +\verb|GLP_SOL| & basic solution; \\
1.819 +\verb|GLP_IPT| & interior-point solution; \\
1.820 +\verb|GLP_MIP| & mixed integer solution. \\
1.821 +\end{tabular}
1.822 +
1.823 +\subsubsection*{Returns}
1.824 +
1.825 +If the operation is successful, the routine returns zero. Otherwise
1.826 +the routine prints an error message and returns non-zero.
1.827 +
1.828 +\subsection{glp\_mpl\_free\_wksp---free the translator workspace}
1.829 +
1.830 +\subsubsection*{Synopsis}
1.831 +
1.832 +\begin{verbatim}
1.833 +void glp_mpl_free_wksp(glp_tran *tran);
1.834 +\end{verbatim}
1.835 +
1.836 +\subsubsection*{Description}
1.837 +
1.838 +The routine \verb|glp_mpl_free_wksp| frees all the memory allocated to
1.839 +the translator workspace. It also frees all other resources, which are
1.840 +still used by the translator.
1.841 +
1.842 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1.843 +
1.844 +\newpage
1.845 +
1.846 +\section{Problem solution reading/writing routines}
1.847 +
1.848 +\subsection{glp\_print\_sol---write basic solution in printable format}
1.849 +
1.850 +\subsubsection*{Synopsis}
1.851 +
1.852 +\begin{verbatim}
1.853 +int glp_print_sol(glp_prob *lp, const char *fname);
1.854 +\end{verbatim}
1.855 +
1.856 +\subsubsection*{Description}
1.857 +
1.858 +The routine \verb|glp_print_sol writes| the current basic solution of
1.859 +an LP problem, which is specified by the pointer \verb|lp|, to a text
1.860 +file, whose name is the character string \verb|fname|, in printable
1.861 +format.
1.862 +
1.863 +Information reported by the routine \verb|glp_print_sol| is intended
1.864 +mainly for visual analysis.
1.865 +
1.866 +\subsubsection*{Returns}
1.867 +
1.868 +If no errors occurred, the routine returns zero. Otherwise the routine
1.869 +prints an error message and returns non-zero.
1.870 +
1.871 +\subsection{glp\_read\_sol---read basic solution from text file}
1.872 +
1.873 +\subsubsection*{Synopsis}
1.874 +
1.875 +\begin{verbatim}
1.876 +int glp_read_sol(glp_prob *lp, const char *fname);
1.877 +\end{verbatim}
1.878 +
1.879 +\subsubsection*{Description}
1.880 +
1.881 +The routine \verb|glp_read_sol| reads basic solution from a text file
1.882 +whose name is specified by the parameter \verb|fname| into the problem
1.883 +object.
1.884 +
1.885 +For the file format see description of the routine \verb|glp_write_sol|.
1.886 +
1.887 +\subsubsection*{Returns}
1.888 +
1.889 +On success the routine returns zero, otherwise non-zero.
1.890 +
1.891 +\newpage
1.892 +
1.893 +\subsection{glp\_write\_sol---write basic solution to text file}
1.894 +
1.895 +\subsubsection*{Synopsis}
1.896 +
1.897 +\begin{verbatim}
1.898 +int glp_write_sol(glp_prob *lp, const char *fname);
1.899 +\end{verbatim}
1.900 +
1.901 +\subsubsection*{Description}
1.902 +
1.903 +The routine \verb|glp_write_sol| writes the current basic solution to a
1.904 +text file whose name is specified by the parameter \verb|fname|. This
1.905 +file can be read back with the routine \verb|glp_read_sol|.
1.906 +
1.907 +\subsubsection*{Returns}
1.908 +
1.909 +On success the routine returns zero, otherwise non-zero.
1.910 +
1.911 +\subsubsection*{File format}
1.912 +
1.913 +The file created by the routine \verb|glp_write_sol| is a plain text
1.914 +file, which contains the following information:
1.915 +
1.916 +\begin{verbatim}
1.917 + m n
1.918 + p_stat d_stat obj_val
1.919 + r_stat[1] r_prim[1] r_dual[1]
1.920 + . . .
1.921 + r_stat[m] r_prim[m] r_dual[m]
1.922 + c_stat[1] c_prim[1] c_dual[1]
1.923 + . . .
1.924 + c_stat[n] c_prim[n] c_dual[n]
1.925 +\end{verbatim}
1.926 +
1.927 +\noindent
1.928 +where:
1.929 +
1.930 +\noindent
1.931 +$m$ is the number of rows (auxiliary variables);
1.932 +
1.933 +\noindent
1.934 +$n$ is the number of columns (structural variables);
1.935 +
1.936 +\noindent
1.937 +\verb|p_stat| is the primal status of the basic solution
1.938 +(\verb|GLP_UNDEF| = 1, \verb|GLP_FEAS| = 2, \verb|GLP_INFEAS| = 3, or
1.939 +\verb|GLP_NOFEAS| = 4);
1.940 +
1.941 +\noindent
1.942 +\verb|d_stat| is the dual status of the basic solution
1.943 +(\verb|GLP_UNDEF| = 1, \verb|GLP_FEAS| = 2, \verb|GLP_INFEAS| = 3, or
1.944 +\verb|GLP_NOFEAS| = 4);
1.945 +
1.946 +\noindent
1.947 +\verb|obj_val| is the objective value;
1.948 +
1.949 +\noindent
1.950 +\verb|r_stat[i]|, $i=1,\dots,m$, is the status of $i$-th row
1.951 +(\verb|GLP_BS| = 1, \verb|GLP_NL| = 2, \verb|GLP_NU| = 3,
1.952 +\verb|GLP_NF| = 4, or \verb|GLP_NS| = 5);
1.953 +
1.954 +\noindent
1.955 +\verb|r_prim[i]|, $i=1,\dots,m$, is the primal value of $i$-th row;
1.956 +
1.957 +\noindent
1.958 +\verb|r_dual[i]|, $i=1,\dots,m$, is the dual value of $i$-th row;
1.959 +
1.960 +\noindent
1.961 +\verb|c_stat[j]|, $j=1,\dots,n$, is the status of $j$-th column
1.962 +(\verb|GLP_BS| = 1, \verb|GLP_NL| = 2, \verb|GLP_NU| = 3,
1.963 +\verb|GLP_NF| = 4, or \verb|GLP_NS| = 5);
1.964 +
1.965 +\noindent
1.966 +\verb|c_prim[j]|, $j=1,\dots,n$, is the primal value of $j$-th column;
1.967 +
1.968 +\noindent
1.969 +\verb|c_dual[j]|, $j=1,\dots,n$, is the dual value of $j$-th column.
1.970 +
1.971 +\subsection{glp\_print\_ipt---write interior-point solution in
1.972 +printable format}
1.973 +
1.974 +\subsubsection*{Synopsis}
1.975 +
1.976 +\begin{verbatim}
1.977 +int glp_print_ipt(glp_prob *lp, const char *fname);
1.978 +\end{verbatim}
1.979 +
1.980 +\subsubsection*{Description}
1.981 +
1.982 +The routine \verb|glp_print_ipt| writes the current interior point
1.983 +solution of an LP problem, which the parameter \verb|lp| points to, to
1.984 +a text file, whose name is the character string \verb|fname|, in
1.985 +printable format.
1.986 +
1.987 +Information reported by the routine \verb|glp_print_ipt| is intended
1.988 +mainly for visual analysis.
1.989 +
1.990 +\subsubsection*{Returns}
1.991 +
1.992 +If no errors occurred, the routine returns zero. Otherwise the routine
1.993 +prints an error message and returns non-zero.
1.994 +
1.995 +\subsection{glp\_read\_ipt---read interior-point solution from text
1.996 +file}
1.997 +
1.998 +\subsubsection*{Synopsis}
1.999 +
1.1000 +\begin{verbatim}
1.1001 +int glp_read_ipt(glp_prob *lp, const char *fname);
1.1002 +\end{verbatim}
1.1003 +
1.1004 +\subsubsection*{Description}
1.1005 +
1.1006 +The routine \verb|glp_read_ipt| reads interior-point solution from a
1.1007 +text file whose name is specified by the parameter \verb|fname| into the
1.1008 +problem object.
1.1009 +
1.1010 +For the file format see description of the routine \verb|glp_write_ipt|.
1.1011 +
1.1012 +\subsubsection*{Returns}
1.1013 +
1.1014 +On success the routine returns zero, otherwise non-zero.
1.1015 +
1.1016 +\subsection{glp\_write\_ipt---write interior-point solution to text
1.1017 +file}
1.1018 +
1.1019 +\subsubsection*{Synopsis}
1.1020 +
1.1021 +\begin{verbatim}
1.1022 +int glp_write_ipt(glp_prob *lp, const char *fname);
1.1023 +\end{verbatim}
1.1024 +
1.1025 +\subsubsection*{Description}
1.1026 +
1.1027 +The routine \verb|glp_write_ipt| writes the current interior-point
1.1028 +solution to a text file whose name is specified by the parameter
1.1029 +\verb|fname|. This file can be read back with the routine
1.1030 +\verb|glp_read_ipt|.
1.1031 +
1.1032 +\subsubsection*{Returns}
1.1033 +
1.1034 +On success the routine returns zero, otherwise non-zero.
1.1035 +
1.1036 +\subsubsection*{File format}
1.1037 +
1.1038 +The file created by the routine \verb|glp_write_ipt| is a plain text
1.1039 +file, which contains the following information:
1.1040 +
1.1041 +\begin{verbatim}
1.1042 + m n
1.1043 + stat obj_val
1.1044 + r_prim[1] r_dual[1]
1.1045 + . . .
1.1046 + r_prim[m] r_dual[m]
1.1047 + c_prim[1] c_dual[1]
1.1048 + . . .
1.1049 + c_prim[n] c_dual[n]
1.1050 +\end{verbatim}
1.1051 +
1.1052 +\noindent
1.1053 +where:
1.1054 +
1.1055 +\noindent
1.1056 +$m$ is the number of rows (auxiliary variables);
1.1057 +
1.1058 +\noindent
1.1059 +$n$ is the number of columns (structural variables);
1.1060 +
1.1061 +\noindent
1.1062 +\verb|stat| is the solution status (\verb|GLP_UNDEF| = 1 or
1.1063 +\verb|GLP_OPT| = 5);
1.1064 +
1.1065 +\noindent
1.1066 +\verb|obj_val| is the objective value;
1.1067 +
1.1068 +\noindent
1.1069 +\verb|r_prim[i]|, $i=1,\dots,m$, is the primal value of $i$-th row;
1.1070 +
1.1071 +\noindent
1.1072 +\verb|r_dual[i]|, $i=1,\dots,m$, is the dual value of $i$-th row;
1.1073 +
1.1074 +\noindent
1.1075 +\verb|c_prim[j]|, $j=1,\dots,n$, is the primal value of $j$-th column;
1.1076 +
1.1077 +\noindent
1.1078 +\verb|c_dual[j]|, $j=1,\dots,n$, is the dual value of $j$-th column.
1.1079 +
1.1080 +\subsection{glp\_print\_mip---write MIP solution in printable format}
1.1081 +
1.1082 +\subsubsection*{Synopsis}
1.1083 +
1.1084 +\begin{verbatim}
1.1085 +int glp_print_mip(glp_prob *lp, const char *fname);
1.1086 +\end{verbatim}
1.1087 +
1.1088 +\subsubsection*{Description}
1.1089 +
1.1090 +The routine \verb|glp_print_mip| writes a best known integer solution
1.1091 +of a MIP problem, which is specified by the pointer \verb|lp|, to a text
1.1092 +file, whose name is the character string \verb|fname|, in printable
1.1093 +format.
1.1094 +
1.1095 +Information reported by the routine \verb|glp_print_mip| is intended
1.1096 +mainly for visual analysis.
1.1097 +
1.1098 +\subsubsection*{Returns}
1.1099 +
1.1100 +If no errors occurred, the routine returns zero. Otherwise the routine
1.1101 +prints an error message and returns non-zero.
1.1102 +
1.1103 +\newpage
1.1104 +
1.1105 +\subsection{glp\_read\_mip---read MIP solution from text file}
1.1106 +
1.1107 +\subsubsection*{Synopsis}
1.1108 +
1.1109 +\begin{verbatim}
1.1110 +int glp_read_mip(glp_prob *mip, const char *fname);
1.1111 +\end{verbatim}
1.1112 +
1.1113 +\subsubsection*{Description}
1.1114 +
1.1115 +The routine \verb|glp_read_mip| reads MIP solution from a text file
1.1116 +whose name is specified by the parameter \verb|fname| into the problem
1.1117 +object.
1.1118 +
1.1119 +For the file format see description of the routine \verb|glp_write_mip|.
1.1120 +
1.1121 +\subsubsection*{Returns}
1.1122 +
1.1123 +On success the routine returns zero, otherwise non-zero.
1.1124 +
1.1125 +\subsection{glp\_write\_mip---write MIP solution to text file}
1.1126 +
1.1127 +\subsubsection*{Synopsis}
1.1128 +
1.1129 +\begin{verbatim}
1.1130 +int glp_write_mip(glp_prob *mip, const char *fname);
1.1131 +\end{verbatim}
1.1132 +
1.1133 +\subsubsection*{Description}
1.1134 +
1.1135 +The routine \verb|glp_write_mip| writes the current MIP solution to a
1.1136 +text file whose name is specified by the parameter \verb|fname|. This
1.1137 +file can be read back with the routine \verb|glp_read_mip|.
1.1138 +
1.1139 +\subsubsection*{Returns}
1.1140 +
1.1141 +On success the routine returns zero, otherwise non-zero.
1.1142 +
1.1143 +\subsubsection*{File format}
1.1144 +
1.1145 +The file created by the routine \verb|glp_write_sol| is a plain text
1.1146 +file, which contains the following information:
1.1147 +
1.1148 +\begin{verbatim}
1.1149 + m n
1.1150 + stat obj_val
1.1151 + r_val[1]
1.1152 + . . .
1.1153 + r_val[m]
1.1154 + c_val[1]
1.1155 + . . .
1.1156 + c_val[n]
1.1157 +\end{verbatim}
1.1158 +
1.1159 +\noindent
1.1160 +where:
1.1161 +
1.1162 +\noindent
1.1163 +$m$ is the number of rows (auxiliary variables);
1.1164 +
1.1165 +\noindent
1.1166 +$n$ is the number of columns (structural variables);
1.1167 +
1.1168 +\noindent
1.1169 +\verb|stat| is the solution status (\verb|GLP_UNDEF| = 1,
1.1170 +\verb|GLP_FEAS| = 2, \verb|GLP_NOFEAS| = 4, or \verb|GLP_OPT| = 5);
1.1171 +
1.1172 +\noindent
1.1173 +\verb|obj_val| is the objective value;
1.1174 +
1.1175 +\noindent
1.1176 +\verb|r_val[i]|, $i=1,\dots,m$, is the value of $i$-th row;
1.1177 +
1.1178 +\noindent
1.1179 +\verb|c_val[j]|, $j=1,\dots,n$, is the value of $j$-th column.
1.1180 +
1.1181 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1.1182 +
1.1183 +\newpage
1.1184 +
1.1185 +\section{Post-optimal analysis routines}
1.1186 +
1.1187 +\subsection{glp\_print\_ranges---print sensitivity analysis report}
1.1188 +
1.1189 +\subsubsection*{Synopsis}
1.1190 +
1.1191 +\begin{verbatim}
1.1192 +int glp_print_ranges(glp_prob *P, int len, const int list[],
1.1193 + int flags, const char *fname);
1.1194 +\end{verbatim}
1.1195 +
1.1196 +\subsubsection*{Description}
1.1197 +
1.1198 +The routine \verb|glp_print_ranges| performs sensitivity analysis of
1.1199 +current optimal basic solution and writes the analysis report in
1.1200 +human-readable format to a text file, whose name is the character
1.1201 +string {\it fname}. (Detailed description of the report structure is
1.1202 +given below.)
1.1203 +
1.1204 +The parameter {\it len} specifies the length of the row/column list.
1.1205 +
1.1206 +The array {\it list} specifies ordinal number of rows and columns to be
1.1207 +analyzed. The ordinal numbers should be passed in locations
1.1208 +{\it list}[1], {\it list}[2], \dots, {\it list}[{\it len}]. Ordinal
1.1209 +numbers from 1 to $m$ refer to rows, and ordinal numbers from $m+1$ to
1.1210 +$m+n$ refer to columns, where $m$ and $n$ are, resp., the total number
1.1211 +of rows and columns in the problem object. Rows and columns appear in
1.1212 +the analysis report in the same order as they follow in the array list.
1.1213 +
1.1214 +It is allowed to specify $len=0$, in which case the array {\it list} is
1.1215 +not used (so it can be specified as \verb|NULL|), and the routine
1.1216 +performs analysis for all rows and columns of the problem object.
1.1217 +
1.1218 +The parameter {\it flags} is reserved for use in the future and must be
1.1219 +specified as zero.
1.1220 +
1.1221 +On entry to the routine \verb|glp_print_ranges| the current basic
1.1222 +solution must be optimal and the basis factorization must exist.
1.1223 +The application program can check that with the routine
1.1224 +\verb|glp_bf_exists|, and if the factorization does
1.1225 +not exist, compute it with the routine \verb|glp_factorize|. Note that
1.1226 +if the LP preprocessor is not used, on normal exit from the simplex
1.1227 +solver routine \verb|glp_simplex| the basis factorization always exists.
1.1228 +
1.1229 +\subsubsection*{Returns}
1.1230 +
1.1231 +If the operation was successful, the routine \verb|glp_print_ranges|
1.1232 +returns zero. Otherwise, it prints an error message and returns
1.1233 +non-zero.
1.1234 +
1.1235 +\subsubsection*{Analysis report example}
1.1236 +
1.1237 +An example of the sensitivity analysis report is shown on the next two
1.1238 +pages. This example corresponds to the example of LP problem described
1.1239 +in Subsection ``Example of MPS file''.
1.1240 +
1.1241 +\subsubsection*{Structure of the analysis report}
1.1242 +
1.1243 +For each row and column specified in the array {\it list} the routine
1.1244 +prints two lines containing generic information and analysis
1.1245 +information, which depends on the status of corresponding row or column.
1.1246 +
1.1247 +Note that analysis of a row is analysis of its auxiliary variable,
1.1248 +which is equal to the row linear form $\sum a_jx_j$, and analysis of
1.1249 +a column is analysis of corresponding structural variable. Therefore,
1.1250 +formally, on performing the sensitivity analysis there is no difference
1.1251 +between rows and columns.
1.1252 +
1.1253 +\bigskip
1.1254 +
1.1255 +\noindent
1.1256 +{\it Generic information}
1.1257 +
1.1258 +\medskip
1.1259 +
1.1260 +\noindent
1.1261 +{\tt No.} is the row or column ordinal number in the problem object.
1.1262 +Rows are numbered from 1 to $m$, and columns are numbered from 1 to $n$,
1.1263 +where $m$ and $n$ are, resp., the total number of rows and columns in
1.1264 +the problem object.
1.1265 +
1.1266 +\medskip
1.1267 +
1.1268 +\noindent
1.1269 +{\tt Row name} is the symbolic name assigned to the row. If the row has
1.1270 +no name assigned, this field contains blanks.
1.1271 +
1.1272 +\medskip
1.1273 +
1.1274 +\noindent
1.1275 +{\tt Column name} is the symbolic name assigned to the column. If the
1.1276 +column has no name assigned, this field contains blanks.
1.1277 +
1.1278 +\medskip
1.1279 +
1.1280 +\noindent
1.1281 +{\tt St} is the status of the row or column in the optimal solution:
1.1282 +
1.1283 +{\tt BS} --- non-active constraint (row), basic column;
1.1284 +
1.1285 +{\tt NL} --- inequality constraint having its lower right-hand side
1.1286 +active (row), non-basic column having its lower bound active;
1.1287 +
1.1288 +{\tt NU} --- inequality constraint having its upper right-hand side
1.1289 +active (row), non-basic column having its upper bound active;
1.1290 +
1.1291 +{\tt NS} --- active equality constraint (row), non-basic fixed column.
1.1292 +
1.1293 +{\tt NF} --- active free row, non-basic free (unbounded) column. (This
1.1294 +case means that the optimal solution is dual degenerate.)
1.1295 +
1.1296 +\medskip
1.1297 +
1.1298 +\noindent
1.1299 +{\tt Activity} is the (primal) value of the auxiliary variable (row) or
1.1300 +structural variable (column) in the optimal solution.
1.1301 +
1.1302 +\medskip
1.1303 +
1.1304 +\noindent
1.1305 +{\tt Slack} is the (primal) value of the row slack variable.
1.1306 +
1.1307 +\medskip
1.1308 +
1.1309 +\noindent
1.1310 +{\tt Obj coef} is the objective coefficient of the column (structural
1.1311 +variable).
1.1312 +
1.1313 +\begin{landscape}
1.1314 +\begin{scriptsize}
1.1315 +\begin{verbatim}
1.1316 +GLPK 4.42 - SENSITIVITY ANALYSIS REPORT Page 1
1.1317 +
1.1318 +Problem: PLAN
1.1319 +Objective: VALUE = 296.2166065 (MINimum)
1.1320 +
1.1321 + No. Row name St Activity Slack Lower bound Activity Obj coef Obj value at Limiting
1.1322 + Marginal Upper bound range range break point variable
1.1323 +------ ------------ -- ------------- ------------- ------------- ------------- ------------- ------------- ------------
1.1324 + 1 VALUE BS 296.21661 -296.21661 -Inf 299.25255 -1.00000 . MN
1.1325 + . +Inf 296.21661 +Inf +Inf
1.1326 +
1.1327 + 2 YIELD NS 2000.00000 . 2000.00000 1995.06864 -Inf 296.28365 BIN3
1.1328 + -.01360 2000.00000 2014.03479 +Inf 296.02579 CU
1.1329 +
1.1330 + 3 FE NU 60.00000 . -Inf 55.89016 -Inf 306.77162 BIN4
1.1331 + -2.56823 60.00000 62.69978 2.56823 289.28294 BIN3
1.1332 +
1.1333 + 4 CU BS 83.96751 16.03249 -Inf 93.88467 -.30613 270.51157 MN
1.1334 + . 100.00000 79.98213 .21474 314.24798 BIN5
1.1335 +
1.1336 + 5 MN NU 40.00000 . -Inf 34.42336 -Inf 299.25255 BIN4
1.1337 + -.54440 40.00000 41.68691 .54440 295.29825 BIN3
1.1338 +
1.1339 + 6 MG BS 19.96029 10.03971 -Inf 24.74427 -1.79618 260.36433 BIN1
1.1340 + . 30.00000 9.40292 .28757 301.95652 MN
1.1341 +
1.1342 + 7 AL NL 1500.00000 . 1500.00000 1485.78425 -.25199 292.63444 CU
1.1343 + .25199 +Inf 1504.92126 +Inf 297.45669 BIN3
1.1344 +
1.1345 + 8 SI NL 250.00000 50.00000 250.00000 235.32871 -.48520 289.09812 CU
1.1346 + .48520 300.00000 255.06073 +Inf 298.67206 BIN3
1.1347 +\end{verbatim}
1.1348 +\end{scriptsize}
1.1349 +\end{landscape}
1.1350 +
1.1351 +\begin{landscape}
1.1352 +\begin{scriptsize}
1.1353 +\begin{verbatim}
1.1354 +GLPK 4.42 - SENSITIVITY ANALYSIS REPORT Page 2
1.1355 +
1.1356 +Problem: PLAN
1.1357 +Objective: VALUE = 296.2166065 (MINimum)
1.1358 +
1.1359 + No. Column name St Activity Obj coef Lower bound Activity Obj coef Obj value at Limiting
1.1360 + Marginal Upper bound range range break point variable
1.1361 +------ ------------ -- ------------- ------------- ------------- ------------- ------------- ------------- ------------
1.1362 + 1 BIN1 NL . .03000 . -28.82475 -.22362 288.90594 BIN4
1.1363 + .25362 200.00000 33.88040 +Inf 304.80951 BIN4
1.1364 +
1.1365 + 2 BIN2 BS 665.34296 .08000 . 802.22222 .01722 254.44822 BIN1
1.1366 + . 2500.00000 313.43066 .08863 301.95652 MN
1.1367 +
1.1368 + 3 BIN3 BS 490.25271 .17000 400.00000 788.61314 .15982 291.22807 MN
1.1369 + . 800.00000 -347.42857 .17948 300.86548 BIN5
1.1370 +
1.1371 + 4 BIN4 BS 424.18773 .12000 100.00000 710.52632 .10899 291.54745 MN
1.1372 + . 700.00000 -256.15524 .14651 307.46010 BIN1
1.1373 +
1.1374 + 5 BIN5 NL . .15000 . -201.78739 .13544 293.27940 BIN3
1.1375 + .01456 1500.00000 58.79586 +Inf 297.07244 BIN3
1.1376 +
1.1377 + 6 ALUM BS 299.63899 .21000 . 358.26772 .18885 289.87879 AL
1.1378 + . +Inf 112.40876 .22622 301.07527 MN
1.1379 +
1.1380 + 7 SILICON BS 120.57762 .38000 . 124.27093 .14828 268.27586 BIN5
1.1381 + . +Inf 85.54745 .46667 306.66667 MN
1.1382 +
1.1383 +End of report
1.1384 +\end{verbatim}
1.1385 +\end{scriptsize}
1.1386 +\end{landscape}
1.1387 +
1.1388 +\noindent
1.1389 +{\tt Marginal} is the reduced cost (dual activity) of the auxiliary
1.1390 +variable (row) or structural variable (column).
1.1391 +
1.1392 +\medskip
1.1393 +
1.1394 +\noindent
1.1395 +{\tt Lower bound} is the lower right-hand side (row) or lower bound
1.1396 +(column). If the row or column has no lower bound, this field contains
1.1397 +{\tt -Inf}.
1.1398 +
1.1399 +\medskip
1.1400 +
1.1401 +\noindent
1.1402 +{\tt Upper bound} is the upper right-hand side (row) or upper bound
1.1403 +(column). If the row or column has no upper bound, this field contains
1.1404 +{\tt +Inf}.
1.1405 +
1.1406 +\bigskip
1.1407 +
1.1408 +\noindent
1.1409 +{\it Sensitivity analysis of active bounds}
1.1410 +
1.1411 +\medskip
1.1412 +
1.1413 +\noindent
1.1414 +The sensitivity analysis of active bounds is performed only for rows,
1.1415 +which are active constraints, and only for non-basic columns, because
1.1416 +inactive constraints and basic columns have no active bounds.
1.1417 +
1.1418 +For every auxiliary (row) or structural (column) non-basic variable the
1.1419 +routine starts changing its active bound in both direction. The first
1.1420 +of the two lines in the report corresponds to decreasing, and the
1.1421 +second line corresponds to increasing of the active bound. Since the
1.1422 +variable being analyzed is non-basic, its activity, which is equal to
1.1423 +its active bound, also starts changing. This changing leads to changing
1.1424 +of basic (auxiliary and structural) variables, which depend on the
1.1425 +non-basic variable. The current basis remains primal feasible and
1.1426 +therefore optimal while values of all basic variables are primal
1.1427 +feasible, i.e. are within their bounds. Therefore, if some basic
1.1428 +variable called the {\it limiting variable} reaches its (lower or
1.1429 +upper) bound first, before any other basic variables, it thereby limits
1.1430 +further changing of the non-basic variable, because otherwise the
1.1431 +current basis would become primal infeasible. The point, at which this
1.1432 +happens, is called the {\it break point}. Note that there are two break
1.1433 +points: the lower break point, which corresponds to decreasing of the
1.1434 +non-basic variable, and the upper break point, which corresponds to
1.1435 +increasing of the non-basic variable.
1.1436 +
1.1437 +In the analysis report values of the non-basic variable (i.e. of its
1.1438 +active bound) being analyzed at both lower and upper break points are
1.1439 +printed in the field `{\tt Activity range}'. Corresponding values of
1.1440 +the objective function are printed in the field `{\tt Obj value at
1.1441 +break point}', and symbolic names of corresponding limiting basic
1.1442 +variables are printed in the field `{\tt Limiting variable}'.
1.1443 +If the active bound can decrease or/and increase unlimitedly, the field
1.1444 +`{\tt Activity range}' contains {\tt -Inf} or/and {\tt +Inf}, resp.
1.1445 +
1.1446 +For example (see the example report above), row SI is a double-sided
1.1447 +constraint, which is active on its lower bound (right-hand side), and
1.1448 +its activity in the optimal solution being equal to the lower bound is
1.1449 +250. The activity range for this row is $[235.32871,255.06073]$. This
1.1450 +means that the basis remains optimal while the lower bound is
1.1451 +increasing up to 255.06073, and further increasing is limited by
1.1452 +(structural) variable BIN3. If the lower bound reaches this upper break
1.1453 +point, the objective value becomes equal to 298.67206.
1.1454 +
1.1455 +Note that if the basis does not change, the objective function depends
1.1456 +on the non-basic variable linearly, and the per-unit change of the
1.1457 +objective function is the reduced cost (marginal value) of the
1.1458 +non-basic variable.
1.1459 +
1.1460 +\bigskip
1.1461 +
1.1462 +\noindent
1.1463 +{\it Sensitivity analysis of objective coefficients at non-basic
1.1464 +variables}
1.1465 +
1.1466 +\medskip
1.1467 +
1.1468 +\noindent
1.1469 +The sensitivity analysis of the objective coefficient at a non-basic
1.1470 +variable is quite simple, because in this case change in the objective
1.1471 +coefficient leads to equivalent change in the reduced cost (marginal
1.1472 +value).
1.1473 +
1.1474 +For every auxiliary (row) or structural (column) non-basic variable the
1.1475 +routine starts changing its objective coefficient in both direction.
1.1476 +(Note that auxiliary variables are not included in the objective
1.1477 +function and therefore always have zero objective coefficients.) The
1.1478 +first of the two lines in the report corresponds to decreasing, and the
1.1479 +second line corresponds to increasing of the objective coefficient.
1.1480 +This changing leads to changing of the reduced cost of the non-basic
1.1481 +variable to be analyzed and does affect reduced costs of all other
1.1482 +non-basic variables. The current basis remains dual feasible and
1.1483 +therefore optimal while the reduced cost keeps its sign. Therefore, if
1.1484 +the reduced cost reaches zero, it limits further changing of the
1.1485 +objective coefficient (if only the non-basic variable is non-fixed).
1.1486 +
1.1487 +In the analysis report minimal and maximal values of the objective
1.1488 +coefficient, on which the basis remains optimal, are printed in the
1.1489 +field `\verb|Obj coef range|'. If the objective coefficient can
1.1490 +decrease or/and increase unlimitedly, this field contains {\tt -Inf}
1.1491 +or/and {\tt +Inf}, resp.
1.1492 +
1.1493 +For example (see the example report above), column BIN5 is non-basic
1.1494 +having its lower bound active. Its objective coefficient is 0.15, and
1.1495 +reduced cost in the optimal solution 0.01456. The column lower bound
1.1496 +remains active while the column reduced cost remains non-negative,
1.1497 +thus, minimal value of the objective coefficient, on which the current
1.1498 +basis still remains optimal, is $0.15-0.01456=0.13644$, that is
1.1499 +indicated in the field `\verb|Obj coef range|'.
1.1500 +
1.1501 +\bigskip
1.1502 +
1.1503 +\noindent
1.1504 +{\it Sensitivity analysis of objective coefficients at basic variables}
1.1505 +
1.1506 +\medskip
1.1507 +
1.1508 +\noindent
1.1509 +To perform sensitivity analysis for every auxiliary (row) or structural
1.1510 +(column) variable the routine starts changing its objective coefficient
1.1511 +in both direction. (Note that auxiliary variables are not included in
1.1512 +the objective function and therefore always have zero objective
1.1513 +coefficients.) The first of the two lines in the report corresponds to
1.1514 +decreasing, and the second line corresponds to increasing of the
1.1515 +objective coefficient. This changing leads to changing of reduced costs
1.1516 +of non-basic variables. The current basis remains dual feasible and
1.1517 +therefore optimal while reduced costs of all non-basic variables
1.1518 +(except fixed variables) keep their signs. Therefore, if the reduced
1.1519 +cost of some non-basic non-fixed variable called the {\it limiting
1.1520 +variable} reaches zero first, before reduced cost of any other
1.1521 +non-basic non-fixed variable, it thereby limits further changing of the
1.1522 +objective coefficient, because otherwise the current basis would become
1.1523 +dual infeasible (non-optimal). The point, at which this happens, is
1.1524 +called the {\it break point}. Note that there are two break points: the
1.1525 +lower break point, which corresponds to decreasing of the objective
1.1526 +coefficient, and the upper break point, which corresponds to increasing
1.1527 +of the objective coefficient. Let the objective coefficient reach its
1.1528 +limit value and continue changing a bit further in the same direction
1.1529 +that makes the current basis dual infeasible (non-optimal). Then the
1.1530 +reduced cost of the non-basic limiting variable becomes ``a bit'' dual
1.1531 +infeasible that forces the limiting variable to enter the basis
1.1532 +replacing there some basic variable, which leaves the basis to keep its
1.1533 +primal feasibility. It should be understood that if we change the
1.1534 +current basis in this way exactly at the break point, both the current
1.1535 +and adjacent bases will be optimal with the same objective value,
1.1536 +because at the break point the limiting variable has zero reduced cost.
1.1537 +On the other hand, in the adjacent basis the value of the limiting
1.1538 +variable changes, because there it becomes basic, that leads to
1.1539 +changing of the value of the basic variable being analyzed. Note that
1.1540 +on determining the adjacent basis the bounds of the analyzed basic
1.1541 +variable are ignored as if it were a free (unbounded) variable, so it
1.1542 +cannot leave the current basis.
1.1543 +
1.1544 +In the analysis report lower and upper limits of the objective
1.1545 +coefficient at the basic variable being analyzed, when the basis
1.1546 +remains optimal, are printed in the field `{\tt Obj coef range}'.
1.1547 +Corresponding values of the objective function at both lower and upper
1.1548 +break points are printed in the field `{\tt Obj value at break point}',
1.1549 +symbolic names of corresponding non-basic limiting variables are
1.1550 +printed in the field `{\tt Limiting variable}', and values of the basic
1.1551 +variable, which it would take on in the adjacent bases (as was
1.1552 +explained above) are printed in the field `{\tt Activity range}'.
1.1553 +If the objective coefficient can increase or/and decrease unlimitedly,
1.1554 +the field `{\tt Obj coef range}' contains {\tt -Inf} and/or {\tt +Inf},
1.1555 +resp. It also may happen that no dual feasible adjacent basis exists
1.1556 +(i.e. on entering the basis the limiting variable can increase or
1.1557 +decrease unlimitedly), in which case the field `{\tt Activity range}'
1.1558 +contains {\tt -Inf} and/or {\tt +Inf}.
1.1559 +
1.1560 +\newpage
1.1561 +
1.1562 +For example (see the example report above), structural variable
1.1563 +(column) BIN3 is basic, its optimal value is 490.25271, and its
1.1564 +objective coefficient is 0.17. The objective coefficient range for this
1.1565 +column is $[0.15982,0.17948]$. This means that the basis remains
1.1566 +optimal while the objective coefficient is decreasing down to 0.15982,
1.1567 +and further decreasing is limited by (auxiliary) variable MN. If we
1.1568 +make the objective coefficient a bit less than 0.15982, the limiting
1.1569 +variable MN will enter the basis, and in that adjacent basis the
1.1570 +structural variable BIN3 will take on new optimal value 788.61314. At
1.1571 +the lower break point, where the objective coefficient is exactly
1.1572 +0.15982, the objective function takes on the value 291.22807 in both
1.1573 +the current and adjacent bases.
1.1574 +
1.1575 +Note that if the basis does not change, the objective function depends
1.1576 +on the objective coefficient at the basic variable linearly, and the
1.1577 +per-unit change of the objective function is the value of the basic
1.1578 +variable.
1.1579 +
1.1580 +%* eof *%