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