lemon-project-template-glpk

annotate deps/glpk/doc/glpk03.tex @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 %* glpk03.tex *%
alpar@9 2
alpar@9 3 \chapter{Utility API routines}
alpar@9 4
alpar@9 5 \section{Problem data reading/writing routines}
alpar@9 6
alpar@9 7 \subsection{glp\_read\_mps---read problem data in MPS format}
alpar@9 8
alpar@9 9 \subsubsection*{Synopsis}
alpar@9 10
alpar@9 11 \begin{verbatim}
alpar@9 12 int glp_read_mps(glp_prob *lp, int fmt, const void *parm,
alpar@9 13 const char *fname);
alpar@9 14 \end{verbatim}
alpar@9 15
alpar@9 16 \subsubsection*{Description}
alpar@9 17
alpar@9 18 The routine \verb|glp_read_mps| reads problem data in MPS format from a
alpar@9 19 text file. (The MPS format is described in Appendix \ref{champs}, page
alpar@9 20 \pageref{champs}.)
alpar@9 21
alpar@9 22 The parameter \verb|fmt| specifies the MPS format version as follows:
alpar@9 23
alpar@9 24 \begin{tabular}{@{}ll}
alpar@9 25 \verb|GLP_MPS_DECK| & fixed (ancient) MPS format; \\
alpar@9 26 \verb|GLP_MPS_FILE| & free (modern) MPS format. \\
alpar@9 27 \end{tabular}
alpar@9 28
alpar@9 29 The parameter \verb|parm| is reserved for use in the future and must be
alpar@9 30 specified as \verb|NULL|.
alpar@9 31
alpar@9 32 The character string \verb|fname| specifies a name of the text file to
alpar@9 33 be read in. (If the file name ends with suffix `\verb|.gz|', the file is
alpar@9 34 assumed to be compressed, in which case the routine \verb|glp_read_mps|
alpar@9 35 decompresses it ``on the fly''.)
alpar@9 36
alpar@9 37 Note that before reading data the current content of the problem object
alpar@9 38 is completely erased with the routine \verb|glp_erase_prob|.
alpar@9 39
alpar@9 40 \subsubsection*{Returns}
alpar@9 41
alpar@9 42 If the operation was successful, the routine \verb|glp_read_mps|
alpar@9 43 returns zero. Otherwise, it prints an error message and returns
alpar@9 44 non-zero.
alpar@9 45
alpar@9 46 \subsection{glp\_write\_mps---write problem data in MPS format}
alpar@9 47
alpar@9 48 \subsubsection*{Synopsis}
alpar@9 49
alpar@9 50 \begin{verbatim}
alpar@9 51 int glp_write_mps(glp_prob *lp, int fmt, const void *parm,
alpar@9 52 const char *fname);
alpar@9 53 \end{verbatim}
alpar@9 54
alpar@9 55 \subsubsection*{Description}
alpar@9 56
alpar@9 57 The routine \verb|glp_write_mps| writes problem data in MPS format to a
alpar@9 58 text file. (The MPS format is described in Appendix \ref{champs}, page
alpar@9 59 \pageref{champs}.)
alpar@9 60
alpar@9 61 The parameter \verb|fmt| specifies the MPS format version as follows:
alpar@9 62
alpar@9 63 \begin{tabular}{@{}ll}
alpar@9 64 \verb|GLP_MPS_DECK| & fixed (ancient) MPS format; \\
alpar@9 65 \verb|GLP_MPS_FILE| & free (modern) MPS format. \\
alpar@9 66 \end{tabular}
alpar@9 67
alpar@9 68 The parameter \verb|parm| is reserved for use in the future and must be
alpar@9 69 specified as \verb|NULL|.
alpar@9 70
alpar@9 71 The character string \verb|fname| specifies a name of the text file to
alpar@9 72 be written out. (If the file name ends with suffix `\verb|.gz|', the
alpar@9 73 file is assumed to be compressed, in which case the routine
alpar@9 74 \verb|glp_write_mps| performs automatic compression on writing it.)
alpar@9 75
alpar@9 76 \subsubsection*{Returns}
alpar@9 77
alpar@9 78 If the operation was successful, the routine \verb|glp_write_mps|
alpar@9 79 returns zero. Otherwise, it prints an error message and returns
alpar@9 80 non-zero.
alpar@9 81
alpar@9 82 \subsection{glp\_read\_lp---read problem data in CPLEX LP format}
alpar@9 83
alpar@9 84 \subsubsection*{Synopsis}
alpar@9 85
alpar@9 86 \begin{verbatim}
alpar@9 87 int glp_read_lp(glp_prob *lp, const void *parm,
alpar@9 88 const char *fname);
alpar@9 89 \end{verbatim}
alpar@9 90
alpar@9 91 \subsubsection*{Description}
alpar@9 92
alpar@9 93 The routine \verb|glp_read_lp| reads problem data in CPLEX LP format
alpar@9 94 from a text file. (The CPLEX LP format is described in Appendix
alpar@9 95 \ref{chacplex}, page \pageref{chacplex}.)
alpar@9 96
alpar@9 97 The parameter \verb|parm| is reserved for use in the future and must be
alpar@9 98 specified as \verb|NULL|.
alpar@9 99
alpar@9 100 The character string \verb|fname| specifies a name of the text file to
alpar@9 101 be read in. (If the file name ends with suffix `\verb|.gz|', the file is
alpar@9 102 assumed to be compressed, in which case the routine \verb|glp_read_lp|
alpar@9 103 decompresses it ``on the fly''.)
alpar@9 104
alpar@9 105 Note that before reading data the current content of the problem object
alpar@9 106 is completely erased with the routine \verb|glp_erase_prob|.
alpar@9 107
alpar@9 108 \subsubsection*{Returns}
alpar@9 109
alpar@9 110 If the operation was successful, the routine \verb|glp_read_lp| returns
alpar@9 111 zero. Otherwise, it prints an error message and returns non-zero.
alpar@9 112
alpar@9 113 \subsection{glp\_write\_lp---write problem data in CPLEX LP format}
alpar@9 114
alpar@9 115 \subsubsection*{Synopsis}
alpar@9 116
alpar@9 117 \begin{verbatim}
alpar@9 118 int glp_write_lp(glp_prob *lp, const void *parm,
alpar@9 119 const char *fname);
alpar@9 120 \end{verbatim}
alpar@9 121
alpar@9 122 \subsubsection*{Description}
alpar@9 123
alpar@9 124 The routine \verb|glp_write_lp| writes problem data in CPLEX LP format
alpar@9 125 to a text file. (The CPLEX LP format is described in Appendix
alpar@9 126 \ref{chacplex}, page \pageref{chacplex}.)
alpar@9 127
alpar@9 128 The parameter \verb|parm| is reserved for use in the future and must be
alpar@9 129 specified as \verb|NULL|.
alpar@9 130
alpar@9 131 The character string \verb|fname| specifies a name of the text file to
alpar@9 132 be written out. (If the file name ends with suffix `\verb|.gz|', the
alpar@9 133 file is assumed to be compressed, in which case the routine
alpar@9 134 \verb|glp_write_lp| performs automatic compression on writing it.)
alpar@9 135
alpar@9 136 \subsubsection*{Returns}
alpar@9 137
alpar@9 138 If the operation was successful, the routine \verb|glp_write_lp|
alpar@9 139 returns zero. Otherwise, it prints an error message and returns
alpar@9 140 non-zero.
alpar@9 141
alpar@9 142 \subsection{glp\_read\_prob---read problem data in GLPK format}
alpar@9 143
alpar@9 144 \subsubsection*{Synopsis}
alpar@9 145
alpar@9 146 \begin{verbatim}
alpar@9 147 int glp_read_prob(glp_prob *P, int flags, const char *fname);
alpar@9 148 \end{verbatim}
alpar@9 149
alpar@9 150 \subsubsection*{Description}
alpar@9 151
alpar@9 152 The routine \verb|glp_read_prob| reads problem data in the GLPK LP/MIP
alpar@9 153 format from a text file. (For description of the GLPK LP/MIP format see
alpar@9 154 below.)
alpar@9 155
alpar@9 156 The parameter \verb|flags| is reserved for use in the future and should
alpar@9 157 be specified as zero.
alpar@9 158
alpar@9 159 The character string \verb|fname| specifies a name of the text file to
alpar@9 160 be read in. (If the file name ends with suffix `\verb|.gz|', the file
alpar@9 161 is assumed to be compressed, in which case the routine
alpar@9 162 \verb|glp_read_prob| decompresses it ``on the fly''.)
alpar@9 163
alpar@9 164 Note that before reading data the current content of the problem object
alpar@9 165 is completely erased with the routine \verb|glp_erase_prob|.
alpar@9 166
alpar@9 167 \subsubsection*{Returns}
alpar@9 168
alpar@9 169 If the operation was successful, the routine \verb|glp_read_prob|
alpar@9 170 returns zero. Otherwise, it prints an error message and returns
alpar@9 171 non-zero.
alpar@9 172
alpar@9 173 \subsubsection*{GLPK LP/MIP format}
alpar@9 174
alpar@9 175 The GLPK LP/MIP format is a DIMACS-like format.\footnote{The DIMACS
alpar@9 176 formats were developed by the Center for Discrete Mathematics and
alpar@9 177 Theoretical Computer Science (DIMACS) to facilitate exchange of problem
alpar@9 178 data. For details see: {\tt <http://dimacs.rutgers.edu/Challenges/>}. }
alpar@9 179 The file in this format is a plain ASCII text file containing lines of
alpar@9 180 several types described below. A line is terminated with the end-of-line
alpar@9 181 character. Fields in each line are separated by at least one blank
alpar@9 182 space. Each line begins with a one-character designator to identify the
alpar@9 183 line type.
alpar@9 184
alpar@9 185 The first line of the data file must be the problem line (except
alpar@9 186 optional comment lines, which may precede the problem line). The last
alpar@9 187 line of the data file must be the end line. Other lines may follow in
alpar@9 188 arbitrary order, however, duplicate lines are not allowed.
alpar@9 189
alpar@9 190 \paragraph{Comment lines.} Comment lines give human-readable
alpar@9 191 information about the data file and are ignored by GLPK routines.
alpar@9 192 Comment lines can appear anywhere in the data file. Each comment line
alpar@9 193 begins with the lower-case character \verb|c|.
alpar@9 194
alpar@9 195 \begin{verbatim}
alpar@9 196 c This is an example of comment line
alpar@9 197 \end{verbatim}
alpar@9 198
alpar@9 199 \paragraph{Problem line.} There must be exactly one problem line in the
alpar@9 200 data file. This line must appear before any other lines except comment
alpar@9 201 lines and has the following format:
alpar@9 202
alpar@9 203 \begin{verbatim}
alpar@9 204 p CLASS DIR ROWS COLS NONZ
alpar@9 205 \end{verbatim}
alpar@9 206
alpar@9 207 The lower-case letter \verb|p| specifies that this is the problem line.
alpar@9 208
alpar@9 209 The \verb|CLASS| field defines the problem class and can contain either
alpar@9 210 the keyword \verb|lp| (that means linear programming problem) or
alpar@9 211 \verb|mip| (that means mixed integer programming problem).
alpar@9 212
alpar@9 213 The \verb|DIR| field defines the optimization direction (that is, the
alpar@9 214 objective function sense) and can contain either the keyword \verb|min|
alpar@9 215 (that means minimization) or \verb|max| (that means maximization).
alpar@9 216
alpar@9 217 The \verb|ROWS|, \verb|COLS|, and \verb|NONZ| fields contain
alpar@9 218 non-negative integer values specifying, respectively, the number of
alpar@9 219 rows (constraints), columns (variables), and non-zero constraint
alpar@9 220 coefficients in the problem instance. Note that \verb|NONZ| value does
alpar@9 221 not account objective coefficients.
alpar@9 222
alpar@9 223 \paragraph{Row descriptors.} There must be at most one row descriptor
alpar@9 224 line in the data file for each row (constraint). This line has one of
alpar@9 225 the following formats:
alpar@9 226
alpar@9 227 \begin{verbatim}
alpar@9 228 i ROW f
alpar@9 229 i ROW l RHS
alpar@9 230 i ROW u RHS
alpar@9 231 i ROW d RHS1 RHS2
alpar@9 232 i ROW s RHS
alpar@9 233 \end{verbatim}
alpar@9 234
alpar@9 235 The lower-case letter \verb|i| specifies that this is the row
alpar@9 236 descriptor line.
alpar@9 237
alpar@9 238 The \verb|ROW| field specifies the row ordinal number, an integer
alpar@9 239 between 1 and $m$, where $m$ is the number of rows in the problem
alpar@9 240 instance.
alpar@9 241
alpar@9 242 The next lower-case letter specifies the row type as follows:
alpar@9 243
alpar@9 244 \verb|f| --- free (unbounded) row: $-\infty<\sum a_jx_j<+\infty$;
alpar@9 245
alpar@9 246 \verb|l| --- inequality constraint of `$\geq$' type:
alpar@9 247 $\sum a_jx_j\geq b$;
alpar@9 248
alpar@9 249 \verb|u| --- inequality constraint of `$\leq$' type:
alpar@9 250 $\sum a_jx_j\leq b$;
alpar@9 251
alpar@9 252 \verb|d| --- double-sided inequality constraint:
alpar@9 253 $b_1\leq\sum a_jx_j\leq b_2$;
alpar@9 254
alpar@9 255 \verb|s| --- equality constraint: $\sum a_jx_j=b$.
alpar@9 256
alpar@9 257 The \verb|RHS| field contains a floaing-point value specifying the
alpar@9 258 row right-hand side. The \verb|RHS1| and \verb|RHS2| fields contain
alpar@9 259 floating-point values specifying, respectively, the lower and upper
alpar@9 260 right-hand sides for the double-sided row.
alpar@9 261
alpar@9 262 If for some row its descriptor line does not appear in the data file,
alpar@9 263 by default that row is assumed to be an equality constraint with zero
alpar@9 264 right-hand side.
alpar@9 265
alpar@9 266 \paragraph{Column descriptors.} There must be at most one column
alpar@9 267 descriptor line in the data file for each column (variable). This line
alpar@9 268 has one of the following formats depending on the problem class
alpar@9 269 specified in the problem line:
alpar@9 270
alpar@9 271 \bigskip
alpar@9 272
alpar@9 273 \begin{tabular}{@{}l@{\hspace*{40pt}}l}
alpar@9 274 LP class & MIP class \\
alpar@9 275 \hline
alpar@9 276 \verb|j COL f| & \verb|j COL KIND f| \\
alpar@9 277 \verb|j COL l BND| & \verb|j COL KIND l BND| \\
alpar@9 278 \verb|j COL u BND| & \verb|j COL KIND u BND| \\
alpar@9 279 \verb|j COL d BND1 BND2| & \verb|j COL KIND d BND1 BND2| \\
alpar@9 280 \verb|j COL s BND| & \verb|j COL KIND s BND| \\
alpar@9 281 \end{tabular}
alpar@9 282
alpar@9 283 \bigskip
alpar@9 284
alpar@9 285 The lower-case letter \verb|j| specifies that this is the column
alpar@9 286 descriptor line.
alpar@9 287
alpar@9 288 The \verb|COL| field specifies the column ordinal number, an integer
alpar@9 289 between 1 and $n$, where $n$ is the number of columns in the problem
alpar@9 290 instance.
alpar@9 291
alpar@9 292 The \verb|KIND| field is used only for MIP problems and specifies the
alpar@9 293 column kind as follows:
alpar@9 294
alpar@9 295 \verb|c| --- continuous column;
alpar@9 296
alpar@9 297 \verb|i| --- integer column;
alpar@9 298
alpar@9 299 \verb|b| --- binary column (in this case all remaining fields must be
alpar@9 300 omitted).
alpar@9 301
alpar@9 302 The next lower-case letter specifies the column type as follows:
alpar@9 303
alpar@9 304 \verb|f| --- free (unbounded) column: $-\infty<x<+\infty$;
alpar@9 305
alpar@9 306 \verb|l| --- column with lower bound: $x\geq l$;
alpar@9 307
alpar@9 308 \verb|u| --- column with upper bound: $x\leq u$;
alpar@9 309
alpar@9 310 \verb|d| --- double-bounded column: $l\leq x\leq u$;
alpar@9 311
alpar@9 312 \verb|s| --- fixed column: $x=s$.
alpar@9 313
alpar@9 314 The \verb|BND| field contains a floating-point value that specifies the
alpar@9 315 column bound. The \verb|BND1| and \verb|BND2| fields contain
alpar@9 316 floating-point values specifying, respectively, the lower and upper
alpar@9 317 bounds for the double-bounded column.
alpar@9 318
alpar@9 319 If for some column its descriptor line does not appear in the file, by
alpar@9 320 default that column is assumed to be non-negative (in case of LP class)
alpar@9 321 or binary (in case of MIP class).
alpar@9 322
alpar@9 323 \paragraph{Coefficient descriptors.} There must be exactly one
alpar@9 324 coefficient descriptor line in the data file for each non-zero
alpar@9 325 objective or constraint coefficient. This line has the following format:
alpar@9 326
alpar@9 327 \begin{verbatim}
alpar@9 328 a ROW COL VAL
alpar@9 329 \end{verbatim}
alpar@9 330
alpar@9 331 The lower-case letter \verb|a| specifies that this is the coefficient
alpar@9 332 descriptor line.
alpar@9 333
alpar@9 334 For objective coefficients the \verb|ROW| field must contain 0. For
alpar@9 335 constraint coefficients the \verb|ROW| field specifies the row ordinal
alpar@9 336 number, an integer between 1 and $m$, where $m$ is the number of rows
alpar@9 337 in the problem instance.
alpar@9 338
alpar@9 339 The \verb|COL| field specifies the column ordinal number, an integer
alpar@9 340 between 1 and $n$, where $n$ is the number of columns in the problem
alpar@9 341 instance.
alpar@9 342
alpar@9 343 If both the \verb|ROW| and \verb|COL| fields contain 0, the line
alpar@9 344 specifies the constant term (``shift'') of the objective function
alpar@9 345 rather than objective coefficient.
alpar@9 346
alpar@9 347 The \verb|VAL| field contains a floating-point coefficient value (it is
alpar@9 348 allowed to specify zero value in this field).
alpar@9 349
alpar@9 350 The number of constraint coefficient descriptor lines must be exactly
alpar@9 351 the same as specified in the field \verb|NONZ| of the problem line.
alpar@9 352
alpar@9 353 \paragraph{Symbolic name descriptors.} There must be at most one
alpar@9 354 symbolic name descriptor line for the problem instance, objective
alpar@9 355 function, each row (constraint), and each column (variable). This line
alpar@9 356 has one of the following formats:
alpar@9 357
alpar@9 358 \begin{verbatim}
alpar@9 359 n p NAME
alpar@9 360 n z NAME
alpar@9 361 n i ROW NAME
alpar@9 362 n j COL NAME
alpar@9 363 \end{verbatim}
alpar@9 364
alpar@9 365 The lower-case letter \verb|n| specifies that this is the symbolic name
alpar@9 366 descriptor line.
alpar@9 367
alpar@9 368 The next lower-case letter specifies which object should be assigned a
alpar@9 369 symbolic name:
alpar@9 370
alpar@9 371 \verb|p| --- problem instance;
alpar@9 372
alpar@9 373 \verb|z| --- objective function;
alpar@9 374
alpar@9 375 \verb|i| --- row (constraint);
alpar@9 376
alpar@9 377 \verb|j| --- column (variable).
alpar@9 378
alpar@9 379 The \verb|ROW| field specifies the row ordinal number, an integer
alpar@9 380 between 1 and $m$, where $m$ is the number of rows in the problem
alpar@9 381 instance.
alpar@9 382
alpar@9 383 The \verb|COL| field specifies the column ordinal number, an integer
alpar@9 384 between 1 and $n$, where $n$ is the number of columns in the problem
alpar@9 385 instance.
alpar@9 386
alpar@9 387 The \verb|NAME| field contains the symbolic name, a sequence from 1 to
alpar@9 388 255 arbitrary graphic ASCII characters, assigned to corresponding
alpar@9 389 object.
alpar@9 390
alpar@9 391 \paragraph{End line.} There must be exactly one end line in the data
alpar@9 392 file. This line must appear last in the file and has the following
alpar@9 393 format:
alpar@9 394
alpar@9 395 \begin{verbatim}
alpar@9 396 e
alpar@9 397 \end{verbatim}
alpar@9 398
alpar@9 399 The lower-case letter \verb|e| specifies that this is the end line.
alpar@9 400 Anything that follows the end line is ignored by GLPK routines.
alpar@9 401
alpar@9 402 \subsubsection*{Example of data file in GLPK LP/MIP format}
alpar@9 403
alpar@9 404 The following example of a data file in GLPK LP/MIP format specifies
alpar@9 405 the same LP problem as in Subsection ``Example of MPS file''.
alpar@9 406
alpar@9 407 \begin{center}
alpar@9 408 \footnotesize\tt
alpar@9 409 \begin{tabular}{l@{\hspace*{50pt}}}
alpar@9 410 p lp min 8 7 48 \\
alpar@9 411 n p PLAN \\
alpar@9 412 n z VALUE \\
alpar@9 413 i 1 f \\
alpar@9 414 n i 1 VALUE \\
alpar@9 415 i 2 s 2000 \\
alpar@9 416 n i 2 YIELD \\
alpar@9 417 i 3 u 60 \\
alpar@9 418 n i 3 FE \\
alpar@9 419 i 4 u 100 \\
alpar@9 420 n i 4 CU \\
alpar@9 421 i 5 u 40 \\
alpar@9 422 n i 5 MN \\
alpar@9 423 i 6 u 30 \\
alpar@9 424 n i 6 MG \\
alpar@9 425 i 7 l 1500 \\
alpar@9 426 n i 7 AL \\
alpar@9 427 i 8 d 250 300 \\
alpar@9 428 n i 8 SI \\
alpar@9 429 j 1 d 0 200 \\
alpar@9 430 n j 1 BIN1 \\
alpar@9 431 j 2 d 0 2500 \\
alpar@9 432 n j 2 BIN2 \\
alpar@9 433 j 3 d 400 800 \\
alpar@9 434 n j 3 BIN3 \\
alpar@9 435 j 4 d 100 700 \\
alpar@9 436 n j 4 BIN4 \\
alpar@9 437 j 5 d 0 1500 \\
alpar@9 438 n j 5 BIN5 \\
alpar@9 439 n j 6 ALUM \\
alpar@9 440 n j 7 SILICON \\
alpar@9 441 a 0 1 0.03 \\
alpar@9 442 a 0 2 0.08 \\
alpar@9 443 a 0 3 0.17 \\
alpar@9 444 a 0 4 0.12 \\
alpar@9 445 a 0 5 0.15 \\
alpar@9 446 a 0 6 0.21 \\
alpar@9 447 a 0 7 0.38 \\
alpar@9 448 a 1 1 0.03 \\
alpar@9 449 a 1 2 0.08 \\
alpar@9 450 a 1 3 0.17 \\
alpar@9 451 a 1 4 0.12 \\
alpar@9 452 a 1 5 0.15 \\
alpar@9 453 a 1 6 0.21 \\
alpar@9 454 \end{tabular}
alpar@9 455 \begin{tabular}{|@{\hspace*{80pt}}l}
alpar@9 456 a 1 7 0.38 \\
alpar@9 457 a 2 1 1 \\
alpar@9 458 a 2 2 1 \\
alpar@9 459 a 2 3 1 \\
alpar@9 460 a 2 4 1 \\
alpar@9 461 a 2 5 1 \\
alpar@9 462 a 2 6 1 \\
alpar@9 463 a 2 7 1 \\
alpar@9 464 a 3 1 0.15 \\
alpar@9 465 a 3 2 0.04 \\
alpar@9 466 a 3 3 0.02 \\
alpar@9 467 a 3 4 0.04 \\
alpar@9 468 a 3 5 0.02 \\
alpar@9 469 a 3 6 0.01 \\
alpar@9 470 a 3 7 0.03 \\
alpar@9 471 a 4 1 0.03 \\
alpar@9 472 a 4 2 0.05 \\
alpar@9 473 a 4 3 0.08 \\
alpar@9 474 a 4 4 0.02 \\
alpar@9 475 a 4 5 0.06 \\
alpar@9 476 a 4 6 0.01 \\
alpar@9 477 a 5 1 0.02 \\
alpar@9 478 a 5 2 0.04 \\
alpar@9 479 a 5 3 0.01 \\
alpar@9 480 a 5 4 0.02 \\
alpar@9 481 a 5 5 0.02 \\
alpar@9 482 a 6 1 0.02 \\
alpar@9 483 a 6 2 0.03 \\
alpar@9 484 a 6 5 0.01 \\
alpar@9 485 a 7 1 0.7 \\
alpar@9 486 a 7 2 0.75 \\
alpar@9 487 a 7 3 0.8 \\
alpar@9 488 a 7 4 0.75 \\
alpar@9 489 a 7 5 0.8 \\
alpar@9 490 a 7 6 0.97 \\
alpar@9 491 a 8 1 0.02 \\
alpar@9 492 a 8 2 0.06 \\
alpar@9 493 a 8 3 0.08 \\
alpar@9 494 a 8 4 0.12 \\
alpar@9 495 a 8 5 0.02 \\
alpar@9 496 a 8 6 0.01 \\
alpar@9 497 a 8 7 0.97 \\
alpar@9 498 e o f \\
alpar@9 499 \\
alpar@9 500 \end{tabular}
alpar@9 501 \end{center}
alpar@9 502
alpar@9 503 \newpage
alpar@9 504
alpar@9 505 \subsection{glp\_write\_prob---write problem data in GLPK format}
alpar@9 506
alpar@9 507 \subsubsection*{Synopsis}
alpar@9 508
alpar@9 509 \begin{verbatim}
alpar@9 510 int glp_write_prob(glp_prob *P, int flags, const char *fname);
alpar@9 511 \end{verbatim}
alpar@9 512
alpar@9 513 \subsubsection*{Description}
alpar@9 514
alpar@9 515 The routine \verb|glp_write_prob| writes problem data in the GLPK
alpar@9 516 LP/MIP format to a text file. (For description of the GLPK LP/MIP
alpar@9 517 format see Subsection ``Read problem data in GLPK format''.)
alpar@9 518
alpar@9 519 The parameter \verb|flags| is reserved for use in the future and should
alpar@9 520 be specified as zero.
alpar@9 521
alpar@9 522 The character string \verb|fname| specifies a name of the text file to
alpar@9 523 be written out. (If the file name ends with suffix `\verb|.gz|', the
alpar@9 524 file is assumed to be compressed, in which case the routine
alpar@9 525 \verb|glp_write_prob| performs automatic compression on writing it.)
alpar@9 526
alpar@9 527 \subsubsection*{Returns}
alpar@9 528
alpar@9 529 If the operation was successful, the routine \verb|glp_read_prob|
alpar@9 530 returns zero. Otherwise, it prints an error message and returns
alpar@9 531 non-zero.
alpar@9 532
alpar@9 533 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9 534
alpar@9 535 \newpage
alpar@9 536
alpar@9 537 \section{Routines for processing MathProg models}
alpar@9 538
alpar@9 539 \subsection{Introduction}
alpar@9 540
alpar@9 541 GLPK supports the {\it GNU MathProg modeling language}.\footnote{The
alpar@9 542 GNU MathProg modeling language is a subset of the AMPL language. For
alpar@9 543 its detailed description see the document ``Modeling Language GNU
alpar@9 544 MathProg: Language Reference'' included in the GLPK distribution.}
alpar@9 545 As a rule, models written in MathProg are solved with the GLPK LP/MIP
alpar@9 546 stand-alone solver \verb|glpsol| (see Appendix D) and do not need any
alpar@9 547 programming with API routines. However, for various reasons the user
alpar@9 548 may need to process MathProg models directly in his/her application
alpar@9 549 program, in which case he/she may use API routines described in this
alpar@9 550 section. These routines provide an interface to the {\it MathProg
alpar@9 551 translator}, a component of GLPK, which translates MathProg models into
alpar@9 552 an internal code and then interprets (executes) this code.
alpar@9 553
alpar@9 554 The processing of a model written in GNU MathProg includes several
alpar@9 555 steps, which should be performed in the following order:
alpar@9 556
alpar@9 557 \begin{enumerate}
alpar@9 558 \item{\it Allocating the workspace.}
alpar@9 559 The translator allocates the workspace, an internal data structure used
alpar@9 560 on all subsequent steps.
alpar@9 561 \item{\it Reading model section.} The translator reads model section
alpar@9 562 and, optionally, data section from a specified text file and translates
alpar@9 563 them into the internal code. If necessary, on this step data section
alpar@9 564 may be ignored.
alpar@9 565 \item{\it Reading data section(s).} The translator reads one or more
alpar@9 566 data sections from specified text file(s) and translates them into the
alpar@9 567 internal code.
alpar@9 568 \item{\it Generating the model.} The translator executes the internal
alpar@9 569 code to evaluate the content of the model objects such as sets,
alpar@9 570 parameters, variables, constraints, and objectives. On this step the
alpar@9 571 execution is suspended at the solve statement.
alpar@9 572 \item {\it Building the problem object.} The translator obtains all
alpar@9 573 necessary information from the workspace and builds the standard
alpar@9 574 problem object (that is, the program object of type \verb|glp_prob|).
alpar@9 575 \item{\it Solving the problem.} On this step the problem object built
alpar@9 576 on the previous step is passed to a solver, which solves the problem
alpar@9 577 instance and stores its solution back to the problem object.
alpar@9 578 \item{\it Postsolving the model.} The translator copies the solution
alpar@9 579 from the problem object to the workspace and then executes the internal
alpar@9 580 code from the solve statement to the end of the model. (If model has
alpar@9 581 no solve statement, the translator does nothing on this step.)
alpar@9 582 \item{\it Freeing the workspace.} The translator frees all the memory
alpar@9 583 allocated to the workspace.
alpar@9 584 \end{enumerate}
alpar@9 585
alpar@9 586 Note that the MathProg translator performs no error correction, so if
alpar@9 587 any of steps 2 to 7 fails (due to errors in the model), the application
alpar@9 588 program should terminate processing and go to step 8.
alpar@9 589
alpar@9 590 \subsubsection*{Example 1}
alpar@9 591
alpar@9 592 In this example the program reads model and data sections from input
alpar@9 593 file \verb|egypt.mod|\footnote{This is an example model included in
alpar@9 594 the GLPK distribution.} and writes the model to output file
alpar@9 595 \verb|egypt.mps| in free MPS format (see Appendix B). No solution is
alpar@9 596 performed.
alpar@9 597
alpar@9 598 \begin{small}
alpar@9 599 \begin{verbatim}
alpar@9 600 /* mplsamp1.c */
alpar@9 601
alpar@9 602 #include <stdio.h>
alpar@9 603 #include <stdlib.h>
alpar@9 604 #include <glpk.h>
alpar@9 605
alpar@9 606 int main(void)
alpar@9 607 { glp_prob *lp;
alpar@9 608 glp_tran *tran;
alpar@9 609 int ret;
alpar@9 610 lp = glp_create_prob();
alpar@9 611 tran = glp_mpl_alloc_wksp();
alpar@9 612 ret = glp_mpl_read_model(tran, "egypt.mod", 0);
alpar@9 613 if (ret != 0)
alpar@9 614 { fprintf(stderr, "Error on translating model\n");
alpar@9 615 goto skip;
alpar@9 616 }
alpar@9 617 ret = glp_mpl_generate(tran, NULL);
alpar@9 618 if (ret != 0)
alpar@9 619 { fprintf(stderr, "Error on generating model\n");
alpar@9 620 goto skip;
alpar@9 621 }
alpar@9 622 glp_mpl_build_prob(tran, lp);
alpar@9 623 ret = glp_write_mps(lp, GLP_MPS_FILE, NULL, "egypt.mps");
alpar@9 624 if (ret != 0)
alpar@9 625 fprintf(stderr, "Error on writing MPS file\n");
alpar@9 626 skip: glp_mpl_free_wksp(tran);
alpar@9 627 glp_delete_prob(lp);
alpar@9 628 return 0;
alpar@9 629 }
alpar@9 630
alpar@9 631 /* eof */
alpar@9 632 \end{verbatim}
alpar@9 633 \end{small}
alpar@9 634
alpar@9 635 \subsubsection*{Example 2}
alpar@9 636
alpar@9 637 In this example the program reads model section from file
alpar@9 638 \verb|sudoku.mod|\footnote{This is an example model which is included
alpar@9 639 in the GLPK distribution along with alternative data file
alpar@9 640 {\tt sudoku.dat}.} ignoring data section in this file, reads alternative
alpar@9 641 data section from file \verb|sudoku.dat|, solves the problem instance
alpar@9 642 and passes the solution found back to the model.
alpar@9 643
alpar@9 644 \begin{small}
alpar@9 645 \begin{verbatim}
alpar@9 646 /* mplsamp2.c */
alpar@9 647
alpar@9 648 #include <stdio.h>
alpar@9 649 #include <stdlib.h>
alpar@9 650 #include <glpk.h>
alpar@9 651
alpar@9 652 int main(void)
alpar@9 653 { glp_prob *mip;
alpar@9 654 glp_tran *tran;
alpar@9 655 int ret;
alpar@9 656 mip = glp_create_prob();
alpar@9 657 tran = glp_mpl_alloc_wksp();
alpar@9 658 ret = glp_mpl_read_model(tran, "sudoku.mod", 1);
alpar@9 659 if (ret != 0)
alpar@9 660 { fprintf(stderr, "Error on translating model\n");
alpar@9 661 goto skip;
alpar@9 662 }
alpar@9 663 ret = glp_mpl_read_data(tran, "sudoku.dat");
alpar@9 664 if (ret != 0)
alpar@9 665 { fprintf(stderr, "Error on translating data\n");
alpar@9 666 goto skip;
alpar@9 667 }
alpar@9 668 ret = glp_mpl_generate(tran, NULL);
alpar@9 669 if (ret != 0)
alpar@9 670 { fprintf(stderr, "Error on generating model\n");
alpar@9 671 goto skip;
alpar@9 672 }
alpar@9 673 glp_mpl_build_prob(tran, mip);
alpar@9 674 glp_simplex(mip, NULL);
alpar@9 675 glp_intopt(mip, NULL);
alpar@9 676 ret = glp_mpl_postsolve(tran, mip, GLP_MIP);
alpar@9 677 if (ret != 0)
alpar@9 678 fprintf(stderr, "Error on postsolving model\n");
alpar@9 679 skip: glp_mpl_free_wksp(tran);
alpar@9 680 glp_delete_prob(mip);
alpar@9 681 return 0;
alpar@9 682 }
alpar@9 683
alpar@9 684 /* eof */
alpar@9 685 \end{verbatim}
alpar@9 686 \end{small}
alpar@9 687
alpar@9 688 \subsection{glp\_mpl\_alloc\_wksp---allocate the translator workspace}
alpar@9 689
alpar@9 690 \subsubsection*{Synopsis}
alpar@9 691
alpar@9 692 \begin{verbatim}
alpar@9 693 glp_tran *glp_mpl_alloc_wksp(void);
alpar@9 694 \end{verbatim}
alpar@9 695
alpar@9 696 \subsubsection*{Description}
alpar@9 697
alpar@9 698 The routine \verb|glp_mpl_alloc_wksp| allocates the MathProg translator
alpar@9 699 work\-space. (Note that multiple instances of the workspace may be
alpar@9 700 allocated, if necessary.)
alpar@9 701
alpar@9 702 \subsubsection*{Returns}
alpar@9 703
alpar@9 704 The routine returns a pointer to the workspace, which should be used in
alpar@9 705 all subsequent operations.
alpar@9 706
alpar@9 707 \subsection{glp\_mpl\_read\_model---read and translate model section}
alpar@9 708
alpar@9 709 \subsubsection*{Synopsis}
alpar@9 710
alpar@9 711 \begin{verbatim}
alpar@9 712 int glp_mpl_read_model(glp_tran *tran, const char *fname,
alpar@9 713 int skip);
alpar@9 714 \end{verbatim}
alpar@9 715
alpar@9 716 \subsubsection*{Description}
alpar@9 717
alpar@9 718 The routine \verb|glp_mpl_read_model| reads model section and,
alpar@9 719 optionally, data section, which may follow the model section, from a
alpar@9 720 text file, whose name is the character string \verb|fname|, performs
alpar@9 721 translation of model statements and data blocks, and stores all the
alpar@9 722 information in the workspace.
alpar@9 723
alpar@9 724 The parameter \verb|skip| is a flag. If the input file contains the
alpar@9 725 data section and this flag is non-zero, the data section is not read as
alpar@9 726 if there were no data section and a warning message is printed. This
alpar@9 727 allows reading data section(s) from other file(s).
alpar@9 728
alpar@9 729 \subsubsection*{Returns}
alpar@9 730
alpar@9 731 If the operation is successful, the routine returns zero. Otherwise
alpar@9 732 the routine prints an error message and returns non-zero.
alpar@9 733
alpar@9 734 \subsection{glp\_mpl\_read\_data---read and translate data section}
alpar@9 735
alpar@9 736 \subsubsection*{Synopsis}
alpar@9 737
alpar@9 738 \begin{verbatim}
alpar@9 739 int glp_mpl_read_data(glp_tran *tran, const char *fname);
alpar@9 740 \end{verbatim}
alpar@9 741
alpar@9 742 \subsubsection*{Description}
alpar@9 743
alpar@9 744 The routine \verb|glp_mpl_read_data| reads data section from a text
alpar@9 745 file, whose name is the character string \verb|fname|, performs
alpar@9 746 translation of data blocks, and stores the data read in the translator
alpar@9 747 workspace. If necessary, this routine may be called more than once.
alpar@9 748
alpar@9 749 \subsubsection*{Returns}
alpar@9 750
alpar@9 751 If the operation is successful, the routine returns zero. Otherwise
alpar@9 752 the routine prints an error message and returns non-zero.
alpar@9 753
alpar@9 754 \subsection{glp\_mpl\_generate---generate the model}
alpar@9 755
alpar@9 756 \subsubsection*{Synopsis}
alpar@9 757
alpar@9 758 \begin{verbatim}
alpar@9 759 int glp_mpl_generate(glp_tran *tran, const char *fname);
alpar@9 760 \end{verbatim}
alpar@9 761
alpar@9 762 \subsubsection*{Description}
alpar@9 763
alpar@9 764 The routine \verb|glp_mpl_generate| generates the model using its
alpar@9 765 description stored in the translator workspace. This operation means
alpar@9 766 generating all variables, constraints, and objectives, executing check
alpar@9 767 and display statements, which precede the solve statement (if it is
alpar@9 768 presented).
alpar@9 769
alpar@9 770 The character string \verb|fname| specifies the name of an output text
alpar@9 771 file, to which output produced by display statements should be written.
alpar@9 772 If \verb|fname| is \verb|NULL|, the output is sent to the terminal.
alpar@9 773
alpar@9 774 \subsubsection*{Returns}
alpar@9 775
alpar@9 776 If the operation is successful, the routine returns zero. Otherwise
alpar@9 777 the routine prints an error message and returns non-zero.
alpar@9 778
alpar@9 779 \subsection{glp\_mpl\_build\_prob---build problem instance from the
alpar@9 780 model}
alpar@9 781
alpar@9 782 \subsubsection*{Synopsis}
alpar@9 783
alpar@9 784 \begin{verbatim}
alpar@9 785 void glp_mpl_build_prob(glp_tran *tran, glp_prob *prob);
alpar@9 786 \end{verbatim}
alpar@9 787
alpar@9 788 \subsubsection*{Description}
alpar@9 789
alpar@9 790 The routine \verb|glp_mpl_build_prob| obtains all necessary information
alpar@9 791 from the translator workspace and stores it in the specified problem
alpar@9 792 object \verb|prob|. Note that before building the current content of
alpar@9 793 the problem object is erased with the routine \verb|glp_erase_prob|.
alpar@9 794
alpar@9 795 \subsection{glp\_mpl\_postsolve---postsolve the model}
alpar@9 796
alpar@9 797 \subsubsection*{Synopsis}
alpar@9 798
alpar@9 799 \begin{verbatim}
alpar@9 800 int glp_mpl_postsolve(glp_tran *tran, glp_prob *prob,
alpar@9 801 int sol);
alpar@9 802 \end{verbatim}
alpar@9 803
alpar@9 804 \subsubsection*{Description}
alpar@9 805
alpar@9 806 The routine \verb|glp_mpl_postsolve| copies the solution from the
alpar@9 807 specified problem object \verb|prob| to the translator workspace and
alpar@9 808 then executes all the remaining model statements, which follow the
alpar@9 809 solve statement.
alpar@9 810
alpar@9 811 The parameter \verb|sol| specifies which solution should be copied
alpar@9 812 from the problem object to the workspace as follows:
alpar@9 813
alpar@9 814 \begin{tabular}{@{}ll}
alpar@9 815 \verb|GLP_SOL| & basic solution; \\
alpar@9 816 \verb|GLP_IPT| & interior-point solution; \\
alpar@9 817 \verb|GLP_MIP| & mixed integer solution. \\
alpar@9 818 \end{tabular}
alpar@9 819
alpar@9 820 \subsubsection*{Returns}
alpar@9 821
alpar@9 822 If the operation is successful, the routine returns zero. Otherwise
alpar@9 823 the routine prints an error message and returns non-zero.
alpar@9 824
alpar@9 825 \subsection{glp\_mpl\_free\_wksp---free the translator workspace}
alpar@9 826
alpar@9 827 \subsubsection*{Synopsis}
alpar@9 828
alpar@9 829 \begin{verbatim}
alpar@9 830 void glp_mpl_free_wksp(glp_tran *tran);
alpar@9 831 \end{verbatim}
alpar@9 832
alpar@9 833 \subsubsection*{Description}
alpar@9 834
alpar@9 835 The routine \verb|glp_mpl_free_wksp| frees all the memory allocated to
alpar@9 836 the translator workspace. It also frees all other resources, which are
alpar@9 837 still used by the translator.
alpar@9 838
alpar@9 839 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9 840
alpar@9 841 \newpage
alpar@9 842
alpar@9 843 \section{Problem solution reading/writing routines}
alpar@9 844
alpar@9 845 \subsection{glp\_print\_sol---write basic solution in printable format}
alpar@9 846
alpar@9 847 \subsubsection*{Synopsis}
alpar@9 848
alpar@9 849 \begin{verbatim}
alpar@9 850 int glp_print_sol(glp_prob *lp, const char *fname);
alpar@9 851 \end{verbatim}
alpar@9 852
alpar@9 853 \subsubsection*{Description}
alpar@9 854
alpar@9 855 The routine \verb|glp_print_sol writes| the current basic solution of
alpar@9 856 an LP problem, which is specified by the pointer \verb|lp|, to a text
alpar@9 857 file, whose name is the character string \verb|fname|, in printable
alpar@9 858 format.
alpar@9 859
alpar@9 860 Information reported by the routine \verb|glp_print_sol| is intended
alpar@9 861 mainly for visual analysis.
alpar@9 862
alpar@9 863 \subsubsection*{Returns}
alpar@9 864
alpar@9 865 If no errors occurred, the routine returns zero. Otherwise the routine
alpar@9 866 prints an error message and returns non-zero.
alpar@9 867
alpar@9 868 \subsection{glp\_read\_sol---read basic solution from text file}
alpar@9 869
alpar@9 870 \subsubsection*{Synopsis}
alpar@9 871
alpar@9 872 \begin{verbatim}
alpar@9 873 int glp_read_sol(glp_prob *lp, const char *fname);
alpar@9 874 \end{verbatim}
alpar@9 875
alpar@9 876 \subsubsection*{Description}
alpar@9 877
alpar@9 878 The routine \verb|glp_read_sol| reads basic solution from a text file
alpar@9 879 whose name is specified by the parameter \verb|fname| into the problem
alpar@9 880 object.
alpar@9 881
alpar@9 882 For the file format see description of the routine \verb|glp_write_sol|.
alpar@9 883
alpar@9 884 \subsubsection*{Returns}
alpar@9 885
alpar@9 886 On success the routine returns zero, otherwise non-zero.
alpar@9 887
alpar@9 888 \newpage
alpar@9 889
alpar@9 890 \subsection{glp\_write\_sol---write basic solution to text file}
alpar@9 891
alpar@9 892 \subsubsection*{Synopsis}
alpar@9 893
alpar@9 894 \begin{verbatim}
alpar@9 895 int glp_write_sol(glp_prob *lp, const char *fname);
alpar@9 896 \end{verbatim}
alpar@9 897
alpar@9 898 \subsubsection*{Description}
alpar@9 899
alpar@9 900 The routine \verb|glp_write_sol| writes the current basic solution to a
alpar@9 901 text file whose name is specified by the parameter \verb|fname|. This
alpar@9 902 file can be read back with the routine \verb|glp_read_sol|.
alpar@9 903
alpar@9 904 \subsubsection*{Returns}
alpar@9 905
alpar@9 906 On success the routine returns zero, otherwise non-zero.
alpar@9 907
alpar@9 908 \subsubsection*{File format}
alpar@9 909
alpar@9 910 The file created by the routine \verb|glp_write_sol| is a plain text
alpar@9 911 file, which contains the following information:
alpar@9 912
alpar@9 913 \begin{verbatim}
alpar@9 914 m n
alpar@9 915 p_stat d_stat obj_val
alpar@9 916 r_stat[1] r_prim[1] r_dual[1]
alpar@9 917 . . .
alpar@9 918 r_stat[m] r_prim[m] r_dual[m]
alpar@9 919 c_stat[1] c_prim[1] c_dual[1]
alpar@9 920 . . .
alpar@9 921 c_stat[n] c_prim[n] c_dual[n]
alpar@9 922 \end{verbatim}
alpar@9 923
alpar@9 924 \noindent
alpar@9 925 where:
alpar@9 926
alpar@9 927 \noindent
alpar@9 928 $m$ is the number of rows (auxiliary variables);
alpar@9 929
alpar@9 930 \noindent
alpar@9 931 $n$ is the number of columns (structural variables);
alpar@9 932
alpar@9 933 \noindent
alpar@9 934 \verb|p_stat| is the primal status of the basic solution
alpar@9 935 (\verb|GLP_UNDEF| = 1, \verb|GLP_FEAS| = 2, \verb|GLP_INFEAS| = 3, or
alpar@9 936 \verb|GLP_NOFEAS| = 4);
alpar@9 937
alpar@9 938 \noindent
alpar@9 939 \verb|d_stat| is the dual status of the basic solution
alpar@9 940 (\verb|GLP_UNDEF| = 1, \verb|GLP_FEAS| = 2, \verb|GLP_INFEAS| = 3, or
alpar@9 941 \verb|GLP_NOFEAS| = 4);
alpar@9 942
alpar@9 943 \noindent
alpar@9 944 \verb|obj_val| is the objective value;
alpar@9 945
alpar@9 946 \noindent
alpar@9 947 \verb|r_stat[i]|, $i=1,\dots,m$, is the status of $i$-th row
alpar@9 948 (\verb|GLP_BS| = 1, \verb|GLP_NL| = 2, \verb|GLP_NU| = 3,
alpar@9 949 \verb|GLP_NF| = 4, or \verb|GLP_NS| = 5);
alpar@9 950
alpar@9 951 \noindent
alpar@9 952 \verb|r_prim[i]|, $i=1,\dots,m$, is the primal value of $i$-th row;
alpar@9 953
alpar@9 954 \noindent
alpar@9 955 \verb|r_dual[i]|, $i=1,\dots,m$, is the dual value of $i$-th row;
alpar@9 956
alpar@9 957 \noindent
alpar@9 958 \verb|c_stat[j]|, $j=1,\dots,n$, is the status of $j$-th column
alpar@9 959 (\verb|GLP_BS| = 1, \verb|GLP_NL| = 2, \verb|GLP_NU| = 3,
alpar@9 960 \verb|GLP_NF| = 4, or \verb|GLP_NS| = 5);
alpar@9 961
alpar@9 962 \noindent
alpar@9 963 \verb|c_prim[j]|, $j=1,\dots,n$, is the primal value of $j$-th column;
alpar@9 964
alpar@9 965 \noindent
alpar@9 966 \verb|c_dual[j]|, $j=1,\dots,n$, is the dual value of $j$-th column.
alpar@9 967
alpar@9 968 \subsection{glp\_print\_ipt---write interior-point solution in
alpar@9 969 printable format}
alpar@9 970
alpar@9 971 \subsubsection*{Synopsis}
alpar@9 972
alpar@9 973 \begin{verbatim}
alpar@9 974 int glp_print_ipt(glp_prob *lp, const char *fname);
alpar@9 975 \end{verbatim}
alpar@9 976
alpar@9 977 \subsubsection*{Description}
alpar@9 978
alpar@9 979 The routine \verb|glp_print_ipt| writes the current interior point
alpar@9 980 solution of an LP problem, which the parameter \verb|lp| points to, to
alpar@9 981 a text file, whose name is the character string \verb|fname|, in
alpar@9 982 printable format.
alpar@9 983
alpar@9 984 Information reported by the routine \verb|glp_print_ipt| is intended
alpar@9 985 mainly for visual analysis.
alpar@9 986
alpar@9 987 \subsubsection*{Returns}
alpar@9 988
alpar@9 989 If no errors occurred, the routine returns zero. Otherwise the routine
alpar@9 990 prints an error message and returns non-zero.
alpar@9 991
alpar@9 992 \subsection{glp\_read\_ipt---read interior-point solution from text
alpar@9 993 file}
alpar@9 994
alpar@9 995 \subsubsection*{Synopsis}
alpar@9 996
alpar@9 997 \begin{verbatim}
alpar@9 998 int glp_read_ipt(glp_prob *lp, const char *fname);
alpar@9 999 \end{verbatim}
alpar@9 1000
alpar@9 1001 \subsubsection*{Description}
alpar@9 1002
alpar@9 1003 The routine \verb|glp_read_ipt| reads interior-point solution from a
alpar@9 1004 text file whose name is specified by the parameter \verb|fname| into the
alpar@9 1005 problem object.
alpar@9 1006
alpar@9 1007 For the file format see description of the routine \verb|glp_write_ipt|.
alpar@9 1008
alpar@9 1009 \subsubsection*{Returns}
alpar@9 1010
alpar@9 1011 On success the routine returns zero, otherwise non-zero.
alpar@9 1012
alpar@9 1013 \subsection{glp\_write\_ipt---write interior-point solution to text
alpar@9 1014 file}
alpar@9 1015
alpar@9 1016 \subsubsection*{Synopsis}
alpar@9 1017
alpar@9 1018 \begin{verbatim}
alpar@9 1019 int glp_write_ipt(glp_prob *lp, const char *fname);
alpar@9 1020 \end{verbatim}
alpar@9 1021
alpar@9 1022 \subsubsection*{Description}
alpar@9 1023
alpar@9 1024 The routine \verb|glp_write_ipt| writes the current interior-point
alpar@9 1025 solution to a text file whose name is specified by the parameter
alpar@9 1026 \verb|fname|. This file can be read back with the routine
alpar@9 1027 \verb|glp_read_ipt|.
alpar@9 1028
alpar@9 1029 \subsubsection*{Returns}
alpar@9 1030
alpar@9 1031 On success the routine returns zero, otherwise non-zero.
alpar@9 1032
alpar@9 1033 \subsubsection*{File format}
alpar@9 1034
alpar@9 1035 The file created by the routine \verb|glp_write_ipt| is a plain text
alpar@9 1036 file, which contains the following information:
alpar@9 1037
alpar@9 1038 \begin{verbatim}
alpar@9 1039 m n
alpar@9 1040 stat obj_val
alpar@9 1041 r_prim[1] r_dual[1]
alpar@9 1042 . . .
alpar@9 1043 r_prim[m] r_dual[m]
alpar@9 1044 c_prim[1] c_dual[1]
alpar@9 1045 . . .
alpar@9 1046 c_prim[n] c_dual[n]
alpar@9 1047 \end{verbatim}
alpar@9 1048
alpar@9 1049 \noindent
alpar@9 1050 where:
alpar@9 1051
alpar@9 1052 \noindent
alpar@9 1053 $m$ is the number of rows (auxiliary variables);
alpar@9 1054
alpar@9 1055 \noindent
alpar@9 1056 $n$ is the number of columns (structural variables);
alpar@9 1057
alpar@9 1058 \noindent
alpar@9 1059 \verb|stat| is the solution status (\verb|GLP_UNDEF| = 1 or
alpar@9 1060 \verb|GLP_OPT| = 5);
alpar@9 1061
alpar@9 1062 \noindent
alpar@9 1063 \verb|obj_val| is the objective value;
alpar@9 1064
alpar@9 1065 \noindent
alpar@9 1066 \verb|r_prim[i]|, $i=1,\dots,m$, is the primal value of $i$-th row;
alpar@9 1067
alpar@9 1068 \noindent
alpar@9 1069 \verb|r_dual[i]|, $i=1,\dots,m$, is the dual value of $i$-th row;
alpar@9 1070
alpar@9 1071 \noindent
alpar@9 1072 \verb|c_prim[j]|, $j=1,\dots,n$, is the primal value of $j$-th column;
alpar@9 1073
alpar@9 1074 \noindent
alpar@9 1075 \verb|c_dual[j]|, $j=1,\dots,n$, is the dual value of $j$-th column.
alpar@9 1076
alpar@9 1077 \subsection{glp\_print\_mip---write MIP solution in printable format}
alpar@9 1078
alpar@9 1079 \subsubsection*{Synopsis}
alpar@9 1080
alpar@9 1081 \begin{verbatim}
alpar@9 1082 int glp_print_mip(glp_prob *lp, const char *fname);
alpar@9 1083 \end{verbatim}
alpar@9 1084
alpar@9 1085 \subsubsection*{Description}
alpar@9 1086
alpar@9 1087 The routine \verb|glp_print_mip| writes a best known integer solution
alpar@9 1088 of a MIP problem, which is specified by the pointer \verb|lp|, to a text
alpar@9 1089 file, whose name is the character string \verb|fname|, in printable
alpar@9 1090 format.
alpar@9 1091
alpar@9 1092 Information reported by the routine \verb|glp_print_mip| is intended
alpar@9 1093 mainly for visual analysis.
alpar@9 1094
alpar@9 1095 \subsubsection*{Returns}
alpar@9 1096
alpar@9 1097 If no errors occurred, the routine returns zero. Otherwise the routine
alpar@9 1098 prints an error message and returns non-zero.
alpar@9 1099
alpar@9 1100 \newpage
alpar@9 1101
alpar@9 1102 \subsection{glp\_read\_mip---read MIP solution from text file}
alpar@9 1103
alpar@9 1104 \subsubsection*{Synopsis}
alpar@9 1105
alpar@9 1106 \begin{verbatim}
alpar@9 1107 int glp_read_mip(glp_prob *mip, const char *fname);
alpar@9 1108 \end{verbatim}
alpar@9 1109
alpar@9 1110 \subsubsection*{Description}
alpar@9 1111
alpar@9 1112 The routine \verb|glp_read_mip| reads MIP solution from a text file
alpar@9 1113 whose name is specified by the parameter \verb|fname| into the problem
alpar@9 1114 object.
alpar@9 1115
alpar@9 1116 For the file format see description of the routine \verb|glp_write_mip|.
alpar@9 1117
alpar@9 1118 \subsubsection*{Returns}
alpar@9 1119
alpar@9 1120 On success the routine returns zero, otherwise non-zero.
alpar@9 1121
alpar@9 1122 \subsection{glp\_write\_mip---write MIP solution to text file}
alpar@9 1123
alpar@9 1124 \subsubsection*{Synopsis}
alpar@9 1125
alpar@9 1126 \begin{verbatim}
alpar@9 1127 int glp_write_mip(glp_prob *mip, const char *fname);
alpar@9 1128 \end{verbatim}
alpar@9 1129
alpar@9 1130 \subsubsection*{Description}
alpar@9 1131
alpar@9 1132 The routine \verb|glp_write_mip| writes the current MIP solution to a
alpar@9 1133 text file whose name is specified by the parameter \verb|fname|. This
alpar@9 1134 file can be read back with the routine \verb|glp_read_mip|.
alpar@9 1135
alpar@9 1136 \subsubsection*{Returns}
alpar@9 1137
alpar@9 1138 On success the routine returns zero, otherwise non-zero.
alpar@9 1139
alpar@9 1140 \subsubsection*{File format}
alpar@9 1141
alpar@9 1142 The file created by the routine \verb|glp_write_sol| is a plain text
alpar@9 1143 file, which contains the following information:
alpar@9 1144
alpar@9 1145 \begin{verbatim}
alpar@9 1146 m n
alpar@9 1147 stat obj_val
alpar@9 1148 r_val[1]
alpar@9 1149 . . .
alpar@9 1150 r_val[m]
alpar@9 1151 c_val[1]
alpar@9 1152 . . .
alpar@9 1153 c_val[n]
alpar@9 1154 \end{verbatim}
alpar@9 1155
alpar@9 1156 \noindent
alpar@9 1157 where:
alpar@9 1158
alpar@9 1159 \noindent
alpar@9 1160 $m$ is the number of rows (auxiliary variables);
alpar@9 1161
alpar@9 1162 \noindent
alpar@9 1163 $n$ is the number of columns (structural variables);
alpar@9 1164
alpar@9 1165 \noindent
alpar@9 1166 \verb|stat| is the solution status (\verb|GLP_UNDEF| = 1,
alpar@9 1167 \verb|GLP_FEAS| = 2, \verb|GLP_NOFEAS| = 4, or \verb|GLP_OPT| = 5);
alpar@9 1168
alpar@9 1169 \noindent
alpar@9 1170 \verb|obj_val| is the objective value;
alpar@9 1171
alpar@9 1172 \noindent
alpar@9 1173 \verb|r_val[i]|, $i=1,\dots,m$, is the value of $i$-th row;
alpar@9 1174
alpar@9 1175 \noindent
alpar@9 1176 \verb|c_val[j]|, $j=1,\dots,n$, is the value of $j$-th column.
alpar@9 1177
alpar@9 1178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9 1179
alpar@9 1180 \newpage
alpar@9 1181
alpar@9 1182 \section{Post-optimal analysis routines}
alpar@9 1183
alpar@9 1184 \subsection{glp\_print\_ranges---print sensitivity analysis report}
alpar@9 1185
alpar@9 1186 \subsubsection*{Synopsis}
alpar@9 1187
alpar@9 1188 \begin{verbatim}
alpar@9 1189 int glp_print_ranges(glp_prob *P, int len, const int list[],
alpar@9 1190 int flags, const char *fname);
alpar@9 1191 \end{verbatim}
alpar@9 1192
alpar@9 1193 \subsubsection*{Description}
alpar@9 1194
alpar@9 1195 The routine \verb|glp_print_ranges| performs sensitivity analysis of
alpar@9 1196 current optimal basic solution and writes the analysis report in
alpar@9 1197 human-readable format to a text file, whose name is the character
alpar@9 1198 string {\it fname}. (Detailed description of the report structure is
alpar@9 1199 given below.)
alpar@9 1200
alpar@9 1201 The parameter {\it len} specifies the length of the row/column list.
alpar@9 1202
alpar@9 1203 The array {\it list} specifies ordinal number of rows and columns to be
alpar@9 1204 analyzed. The ordinal numbers should be passed in locations
alpar@9 1205 {\it list}[1], {\it list}[2], \dots, {\it list}[{\it len}]. Ordinal
alpar@9 1206 numbers from 1 to $m$ refer to rows, and ordinal numbers from $m+1$ to
alpar@9 1207 $m+n$ refer to columns, where $m$ and $n$ are, resp., the total number
alpar@9 1208 of rows and columns in the problem object. Rows and columns appear in
alpar@9 1209 the analysis report in the same order as they follow in the array list.
alpar@9 1210
alpar@9 1211 It is allowed to specify $len=0$, in which case the array {\it list} is
alpar@9 1212 not used (so it can be specified as \verb|NULL|), and the routine
alpar@9 1213 performs analysis for all rows and columns of the problem object.
alpar@9 1214
alpar@9 1215 The parameter {\it flags} is reserved for use in the future and must be
alpar@9 1216 specified as zero.
alpar@9 1217
alpar@9 1218 On entry to the routine \verb|glp_print_ranges| the current basic
alpar@9 1219 solution must be optimal and the basis factorization must exist.
alpar@9 1220 The application program can check that with the routine
alpar@9 1221 \verb|glp_bf_exists|, and if the factorization does
alpar@9 1222 not exist, compute it with the routine \verb|glp_factorize|. Note that
alpar@9 1223 if the LP preprocessor is not used, on normal exit from the simplex
alpar@9 1224 solver routine \verb|glp_simplex| the basis factorization always exists.
alpar@9 1225
alpar@9 1226 \subsubsection*{Returns}
alpar@9 1227
alpar@9 1228 If the operation was successful, the routine \verb|glp_print_ranges|
alpar@9 1229 returns zero. Otherwise, it prints an error message and returns
alpar@9 1230 non-zero.
alpar@9 1231
alpar@9 1232 \subsubsection*{Analysis report example}
alpar@9 1233
alpar@9 1234 An example of the sensitivity analysis report is shown on the next two
alpar@9 1235 pages. This example corresponds to the example of LP problem described
alpar@9 1236 in Subsection ``Example of MPS file''.
alpar@9 1237
alpar@9 1238 \subsubsection*{Structure of the analysis report}
alpar@9 1239
alpar@9 1240 For each row and column specified in the array {\it list} the routine
alpar@9 1241 prints two lines containing generic information and analysis
alpar@9 1242 information, which depends on the status of corresponding row or column.
alpar@9 1243
alpar@9 1244 Note that analysis of a row is analysis of its auxiliary variable,
alpar@9 1245 which is equal to the row linear form $\sum a_jx_j$, and analysis of
alpar@9 1246 a column is analysis of corresponding structural variable. Therefore,
alpar@9 1247 formally, on performing the sensitivity analysis there is no difference
alpar@9 1248 between rows and columns.
alpar@9 1249
alpar@9 1250 \bigskip
alpar@9 1251
alpar@9 1252 \noindent
alpar@9 1253 {\it Generic information}
alpar@9 1254
alpar@9 1255 \medskip
alpar@9 1256
alpar@9 1257 \noindent
alpar@9 1258 {\tt No.} is the row or column ordinal number in the problem object.
alpar@9 1259 Rows are numbered from 1 to $m$, and columns are numbered from 1 to $n$,
alpar@9 1260 where $m$ and $n$ are, resp., the total number of rows and columns in
alpar@9 1261 the problem object.
alpar@9 1262
alpar@9 1263 \medskip
alpar@9 1264
alpar@9 1265 \noindent
alpar@9 1266 {\tt Row name} is the symbolic name assigned to the row. If the row has
alpar@9 1267 no name assigned, this field contains blanks.
alpar@9 1268
alpar@9 1269 \medskip
alpar@9 1270
alpar@9 1271 \noindent
alpar@9 1272 {\tt Column name} is the symbolic name assigned to the column. If the
alpar@9 1273 column has no name assigned, this field contains blanks.
alpar@9 1274
alpar@9 1275 \medskip
alpar@9 1276
alpar@9 1277 \noindent
alpar@9 1278 {\tt St} is the status of the row or column in the optimal solution:
alpar@9 1279
alpar@9 1280 {\tt BS} --- non-active constraint (row), basic column;
alpar@9 1281
alpar@9 1282 {\tt NL} --- inequality constraint having its lower right-hand side
alpar@9 1283 active (row), non-basic column having its lower bound active;
alpar@9 1284
alpar@9 1285 {\tt NU} --- inequality constraint having its upper right-hand side
alpar@9 1286 active (row), non-basic column having its upper bound active;
alpar@9 1287
alpar@9 1288 {\tt NS} --- active equality constraint (row), non-basic fixed column.
alpar@9 1289
alpar@9 1290 {\tt NF} --- active free row, non-basic free (unbounded) column. (This
alpar@9 1291 case means that the optimal solution is dual degenerate.)
alpar@9 1292
alpar@9 1293 \medskip
alpar@9 1294
alpar@9 1295 \noindent
alpar@9 1296 {\tt Activity} is the (primal) value of the auxiliary variable (row) or
alpar@9 1297 structural variable (column) in the optimal solution.
alpar@9 1298
alpar@9 1299 \medskip
alpar@9 1300
alpar@9 1301 \noindent
alpar@9 1302 {\tt Slack} is the (primal) value of the row slack variable.
alpar@9 1303
alpar@9 1304 \medskip
alpar@9 1305
alpar@9 1306 \noindent
alpar@9 1307 {\tt Obj coef} is the objective coefficient of the column (structural
alpar@9 1308 variable).
alpar@9 1309
alpar@9 1310 \begin{landscape}
alpar@9 1311 \begin{scriptsize}
alpar@9 1312 \begin{verbatim}
alpar@9 1313 GLPK 4.42 - SENSITIVITY ANALYSIS REPORT Page 1
alpar@9 1314
alpar@9 1315 Problem: PLAN
alpar@9 1316 Objective: VALUE = 296.2166065 (MINimum)
alpar@9 1317
alpar@9 1318 No. Row name St Activity Slack Lower bound Activity Obj coef Obj value at Limiting
alpar@9 1319 Marginal Upper bound range range break point variable
alpar@9 1320 ------ ------------ -- ------------- ------------- ------------- ------------- ------------- ------------- ------------
alpar@9 1321 1 VALUE BS 296.21661 -296.21661 -Inf 299.25255 -1.00000 . MN
alpar@9 1322 . +Inf 296.21661 +Inf +Inf
alpar@9 1323
alpar@9 1324 2 YIELD NS 2000.00000 . 2000.00000 1995.06864 -Inf 296.28365 BIN3
alpar@9 1325 -.01360 2000.00000 2014.03479 +Inf 296.02579 CU
alpar@9 1326
alpar@9 1327 3 FE NU 60.00000 . -Inf 55.89016 -Inf 306.77162 BIN4
alpar@9 1328 -2.56823 60.00000 62.69978 2.56823 289.28294 BIN3
alpar@9 1329
alpar@9 1330 4 CU BS 83.96751 16.03249 -Inf 93.88467 -.30613 270.51157 MN
alpar@9 1331 . 100.00000 79.98213 .21474 314.24798 BIN5
alpar@9 1332
alpar@9 1333 5 MN NU 40.00000 . -Inf 34.42336 -Inf 299.25255 BIN4
alpar@9 1334 -.54440 40.00000 41.68691 .54440 295.29825 BIN3
alpar@9 1335
alpar@9 1336 6 MG BS 19.96029 10.03971 -Inf 24.74427 -1.79618 260.36433 BIN1
alpar@9 1337 . 30.00000 9.40292 .28757 301.95652 MN
alpar@9 1338
alpar@9 1339 7 AL NL 1500.00000 . 1500.00000 1485.78425 -.25199 292.63444 CU
alpar@9 1340 .25199 +Inf 1504.92126 +Inf 297.45669 BIN3
alpar@9 1341
alpar@9 1342 8 SI NL 250.00000 50.00000 250.00000 235.32871 -.48520 289.09812 CU
alpar@9 1343 .48520 300.00000 255.06073 +Inf 298.67206 BIN3
alpar@9 1344 \end{verbatim}
alpar@9 1345 \end{scriptsize}
alpar@9 1346 \end{landscape}
alpar@9 1347
alpar@9 1348 \begin{landscape}
alpar@9 1349 \begin{scriptsize}
alpar@9 1350 \begin{verbatim}
alpar@9 1351 GLPK 4.42 - SENSITIVITY ANALYSIS REPORT Page 2
alpar@9 1352
alpar@9 1353 Problem: PLAN
alpar@9 1354 Objective: VALUE = 296.2166065 (MINimum)
alpar@9 1355
alpar@9 1356 No. Column name St Activity Obj coef Lower bound Activity Obj coef Obj value at Limiting
alpar@9 1357 Marginal Upper bound range range break point variable
alpar@9 1358 ------ ------------ -- ------------- ------------- ------------- ------------- ------------- ------------- ------------
alpar@9 1359 1 BIN1 NL . .03000 . -28.82475 -.22362 288.90594 BIN4
alpar@9 1360 .25362 200.00000 33.88040 +Inf 304.80951 BIN4
alpar@9 1361
alpar@9 1362 2 BIN2 BS 665.34296 .08000 . 802.22222 .01722 254.44822 BIN1
alpar@9 1363 . 2500.00000 313.43066 .08863 301.95652 MN
alpar@9 1364
alpar@9 1365 3 BIN3 BS 490.25271 .17000 400.00000 788.61314 .15982 291.22807 MN
alpar@9 1366 . 800.00000 -347.42857 .17948 300.86548 BIN5
alpar@9 1367
alpar@9 1368 4 BIN4 BS 424.18773 .12000 100.00000 710.52632 .10899 291.54745 MN
alpar@9 1369 . 700.00000 -256.15524 .14651 307.46010 BIN1
alpar@9 1370
alpar@9 1371 5 BIN5 NL . .15000 . -201.78739 .13544 293.27940 BIN3
alpar@9 1372 .01456 1500.00000 58.79586 +Inf 297.07244 BIN3
alpar@9 1373
alpar@9 1374 6 ALUM BS 299.63899 .21000 . 358.26772 .18885 289.87879 AL
alpar@9 1375 . +Inf 112.40876 .22622 301.07527 MN
alpar@9 1376
alpar@9 1377 7 SILICON BS 120.57762 .38000 . 124.27093 .14828 268.27586 BIN5
alpar@9 1378 . +Inf 85.54745 .46667 306.66667 MN
alpar@9 1379
alpar@9 1380 End of report
alpar@9 1381 \end{verbatim}
alpar@9 1382 \end{scriptsize}
alpar@9 1383 \end{landscape}
alpar@9 1384
alpar@9 1385 \noindent
alpar@9 1386 {\tt Marginal} is the reduced cost (dual activity) of the auxiliary
alpar@9 1387 variable (row) or structural variable (column).
alpar@9 1388
alpar@9 1389 \medskip
alpar@9 1390
alpar@9 1391 \noindent
alpar@9 1392 {\tt Lower bound} is the lower right-hand side (row) or lower bound
alpar@9 1393 (column). If the row or column has no lower bound, this field contains
alpar@9 1394 {\tt -Inf}.
alpar@9 1395
alpar@9 1396 \medskip
alpar@9 1397
alpar@9 1398 \noindent
alpar@9 1399 {\tt Upper bound} is the upper right-hand side (row) or upper bound
alpar@9 1400 (column). If the row or column has no upper bound, this field contains
alpar@9 1401 {\tt +Inf}.
alpar@9 1402
alpar@9 1403 \bigskip
alpar@9 1404
alpar@9 1405 \noindent
alpar@9 1406 {\it Sensitivity analysis of active bounds}
alpar@9 1407
alpar@9 1408 \medskip
alpar@9 1409
alpar@9 1410 \noindent
alpar@9 1411 The sensitivity analysis of active bounds is performed only for rows,
alpar@9 1412 which are active constraints, and only for non-basic columns, because
alpar@9 1413 inactive constraints and basic columns have no active bounds.
alpar@9 1414
alpar@9 1415 For every auxiliary (row) or structural (column) non-basic variable the
alpar@9 1416 routine starts changing its active bound in both direction. The first
alpar@9 1417 of the two lines in the report corresponds to decreasing, and the
alpar@9 1418 second line corresponds to increasing of the active bound. Since the
alpar@9 1419 variable being analyzed is non-basic, its activity, which is equal to
alpar@9 1420 its active bound, also starts changing. This changing leads to changing
alpar@9 1421 of basic (auxiliary and structural) variables, which depend on the
alpar@9 1422 non-basic variable. The current basis remains primal feasible and
alpar@9 1423 therefore optimal while values of all basic variables are primal
alpar@9 1424 feasible, i.e. are within their bounds. Therefore, if some basic
alpar@9 1425 variable called the {\it limiting variable} reaches its (lower or
alpar@9 1426 upper) bound first, before any other basic variables, it thereby limits
alpar@9 1427 further changing of the non-basic variable, because otherwise the
alpar@9 1428 current basis would become primal infeasible. The point, at which this
alpar@9 1429 happens, is called the {\it break point}. Note that there are two break
alpar@9 1430 points: the lower break point, which corresponds to decreasing of the
alpar@9 1431 non-basic variable, and the upper break point, which corresponds to
alpar@9 1432 increasing of the non-basic variable.
alpar@9 1433
alpar@9 1434 In the analysis report values of the non-basic variable (i.e. of its
alpar@9 1435 active bound) being analyzed at both lower and upper break points are
alpar@9 1436 printed in the field `{\tt Activity range}'. Corresponding values of
alpar@9 1437 the objective function are printed in the field `{\tt Obj value at
alpar@9 1438 break point}', and symbolic names of corresponding limiting basic
alpar@9 1439 variables are printed in the field `{\tt Limiting variable}'.
alpar@9 1440 If the active bound can decrease or/and increase unlimitedly, the field
alpar@9 1441 `{\tt Activity range}' contains {\tt -Inf} or/and {\tt +Inf}, resp.
alpar@9 1442
alpar@9 1443 For example (see the example report above), row SI is a double-sided
alpar@9 1444 constraint, which is active on its lower bound (right-hand side), and
alpar@9 1445 its activity in the optimal solution being equal to the lower bound is
alpar@9 1446 250. The activity range for this row is $[235.32871,255.06073]$. This
alpar@9 1447 means that the basis remains optimal while the lower bound is
alpar@9 1448 increasing up to 255.06073, and further increasing is limited by
alpar@9 1449 (structural) variable BIN3. If the lower bound reaches this upper break
alpar@9 1450 point, the objective value becomes equal to 298.67206.
alpar@9 1451
alpar@9 1452 Note that if the basis does not change, the objective function depends
alpar@9 1453 on the non-basic variable linearly, and the per-unit change of the
alpar@9 1454 objective function is the reduced cost (marginal value) of the
alpar@9 1455 non-basic variable.
alpar@9 1456
alpar@9 1457 \bigskip
alpar@9 1458
alpar@9 1459 \noindent
alpar@9 1460 {\it Sensitivity analysis of objective coefficients at non-basic
alpar@9 1461 variables}
alpar@9 1462
alpar@9 1463 \medskip
alpar@9 1464
alpar@9 1465 \noindent
alpar@9 1466 The sensitivity analysis of the objective coefficient at a non-basic
alpar@9 1467 variable is quite simple, because in this case change in the objective
alpar@9 1468 coefficient leads to equivalent change in the reduced cost (marginal
alpar@9 1469 value).
alpar@9 1470
alpar@9 1471 For every auxiliary (row) or structural (column) non-basic variable the
alpar@9 1472 routine starts changing its objective coefficient in both direction.
alpar@9 1473 (Note that auxiliary variables are not included in the objective
alpar@9 1474 function and therefore always have zero objective coefficients.) The
alpar@9 1475 first of the two lines in the report corresponds to decreasing, and the
alpar@9 1476 second line corresponds to increasing of the objective coefficient.
alpar@9 1477 This changing leads to changing of the reduced cost of the non-basic
alpar@9 1478 variable to be analyzed and does affect reduced costs of all other
alpar@9 1479 non-basic variables. The current basis remains dual feasible and
alpar@9 1480 therefore optimal while the reduced cost keeps its sign. Therefore, if
alpar@9 1481 the reduced cost reaches zero, it limits further changing of the
alpar@9 1482 objective coefficient (if only the non-basic variable is non-fixed).
alpar@9 1483
alpar@9 1484 In the analysis report minimal and maximal values of the objective
alpar@9 1485 coefficient, on which the basis remains optimal, are printed in the
alpar@9 1486 field `\verb|Obj coef range|'. If the objective coefficient can
alpar@9 1487 decrease or/and increase unlimitedly, this field contains {\tt -Inf}
alpar@9 1488 or/and {\tt +Inf}, resp.
alpar@9 1489
alpar@9 1490 For example (see the example report above), column BIN5 is non-basic
alpar@9 1491 having its lower bound active. Its objective coefficient is 0.15, and
alpar@9 1492 reduced cost in the optimal solution 0.01456. The column lower bound
alpar@9 1493 remains active while the column reduced cost remains non-negative,
alpar@9 1494 thus, minimal value of the objective coefficient, on which the current
alpar@9 1495 basis still remains optimal, is $0.15-0.01456=0.13644$, that is
alpar@9 1496 indicated in the field `\verb|Obj coef range|'.
alpar@9 1497
alpar@9 1498 \bigskip
alpar@9 1499
alpar@9 1500 \noindent
alpar@9 1501 {\it Sensitivity analysis of objective coefficients at basic variables}
alpar@9 1502
alpar@9 1503 \medskip
alpar@9 1504
alpar@9 1505 \noindent
alpar@9 1506 To perform sensitivity analysis for every auxiliary (row) or structural
alpar@9 1507 (column) variable the routine starts changing its objective coefficient
alpar@9 1508 in both direction. (Note that auxiliary variables are not included in
alpar@9 1509 the objective function and therefore always have zero objective
alpar@9 1510 coefficients.) The first of the two lines in the report corresponds to
alpar@9 1511 decreasing, and the second line corresponds to increasing of the
alpar@9 1512 objective coefficient. This changing leads to changing of reduced costs
alpar@9 1513 of non-basic variables. The current basis remains dual feasible and
alpar@9 1514 therefore optimal while reduced costs of all non-basic variables
alpar@9 1515 (except fixed variables) keep their signs. Therefore, if the reduced
alpar@9 1516 cost of some non-basic non-fixed variable called the {\it limiting
alpar@9 1517 variable} reaches zero first, before reduced cost of any other
alpar@9 1518 non-basic non-fixed variable, it thereby limits further changing of the
alpar@9 1519 objective coefficient, because otherwise the current basis would become
alpar@9 1520 dual infeasible (non-optimal). The point, at which this happens, is
alpar@9 1521 called the {\it break point}. Note that there are two break points: the
alpar@9 1522 lower break point, which corresponds to decreasing of the objective
alpar@9 1523 coefficient, and the upper break point, which corresponds to increasing
alpar@9 1524 of the objective coefficient. Let the objective coefficient reach its
alpar@9 1525 limit value and continue changing a bit further in the same direction
alpar@9 1526 that makes the current basis dual infeasible (non-optimal). Then the
alpar@9 1527 reduced cost of the non-basic limiting variable becomes ``a bit'' dual
alpar@9 1528 infeasible that forces the limiting variable to enter the basis
alpar@9 1529 replacing there some basic variable, which leaves the basis to keep its
alpar@9 1530 primal feasibility. It should be understood that if we change the
alpar@9 1531 current basis in this way exactly at the break point, both the current
alpar@9 1532 and adjacent bases will be optimal with the same objective value,
alpar@9 1533 because at the break point the limiting variable has zero reduced cost.
alpar@9 1534 On the other hand, in the adjacent basis the value of the limiting
alpar@9 1535 variable changes, because there it becomes basic, that leads to
alpar@9 1536 changing of the value of the basic variable being analyzed. Note that
alpar@9 1537 on determining the adjacent basis the bounds of the analyzed basic
alpar@9 1538 variable are ignored as if it were a free (unbounded) variable, so it
alpar@9 1539 cannot leave the current basis.
alpar@9 1540
alpar@9 1541 In the analysis report lower and upper limits of the objective
alpar@9 1542 coefficient at the basic variable being analyzed, when the basis
alpar@9 1543 remains optimal, are printed in the field `{\tt Obj coef range}'.
alpar@9 1544 Corresponding values of the objective function at both lower and upper
alpar@9 1545 break points are printed in the field `{\tt Obj value at break point}',
alpar@9 1546 symbolic names of corresponding non-basic limiting variables are
alpar@9 1547 printed in the field `{\tt Limiting variable}', and values of the basic
alpar@9 1548 variable, which it would take on in the adjacent bases (as was
alpar@9 1549 explained above) are printed in the field `{\tt Activity range}'.
alpar@9 1550 If the objective coefficient can increase or/and decrease unlimitedly,
alpar@9 1551 the field `{\tt Obj coef range}' contains {\tt -Inf} and/or {\tt +Inf},
alpar@9 1552 resp. It also may happen that no dual feasible adjacent basis exists
alpar@9 1553 (i.e. on entering the basis the limiting variable can increase or
alpar@9 1554 decrease unlimitedly), in which case the field `{\tt Activity range}'
alpar@9 1555 contains {\tt -Inf} and/or {\tt +Inf}.
alpar@9 1556
alpar@9 1557 \newpage
alpar@9 1558
alpar@9 1559 For example (see the example report above), structural variable
alpar@9 1560 (column) BIN3 is basic, its optimal value is 490.25271, and its
alpar@9 1561 objective coefficient is 0.17. The objective coefficient range for this
alpar@9 1562 column is $[0.15982,0.17948]$. This means that the basis remains
alpar@9 1563 optimal while the objective coefficient is decreasing down to 0.15982,
alpar@9 1564 and further decreasing is limited by (auxiliary) variable MN. If we
alpar@9 1565 make the objective coefficient a bit less than 0.15982, the limiting
alpar@9 1566 variable MN will enter the basis, and in that adjacent basis the
alpar@9 1567 structural variable BIN3 will take on new optimal value 788.61314. At
alpar@9 1568 the lower break point, where the objective coefficient is exactly
alpar@9 1569 0.15982, the objective function takes on the value 291.22807 in both
alpar@9 1570 the current and adjacent bases.
alpar@9 1571
alpar@9 1572 Note that if the basis does not change, the objective function depends
alpar@9 1573 on the objective coefficient at the basic variable linearly, and the
alpar@9 1574 per-unit change of the objective function is the value of the basic
alpar@9 1575 variable.
alpar@9 1576
alpar@9 1577 %* eof *%