lemon-project-template-glpk
view deps/glpk/doc/glpk03.tex @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
1 %* glpk03.tex *%
3 \chapter{Utility API routines}
5 \section{Problem data reading/writing routines}
7 \subsection{glp\_read\_mps---read problem data in MPS format}
9 \subsubsection*{Synopsis}
11 \begin{verbatim}
12 int glp_read_mps(glp_prob *lp, int fmt, const void *parm,
13 const char *fname);
14 \end{verbatim}
16 \subsubsection*{Description}
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}.)
22 The parameter \verb|fmt| specifies the MPS format version as follows:
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}
29 The parameter \verb|parm| is reserved for use in the future and must be
30 specified as \verb|NULL|.
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''.)
37 Note that before reading data the current content of the problem object
38 is completely erased with the routine \verb|glp_erase_prob|.
40 \subsubsection*{Returns}
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.
46 \subsection{glp\_write\_mps---write problem data in MPS format}
48 \subsubsection*{Synopsis}
50 \begin{verbatim}
51 int glp_write_mps(glp_prob *lp, int fmt, const void *parm,
52 const char *fname);
53 \end{verbatim}
55 \subsubsection*{Description}
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}.)
61 The parameter \verb|fmt| specifies the MPS format version as follows:
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}
68 The parameter \verb|parm| is reserved for use in the future and must be
69 specified as \verb|NULL|.
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.)
76 \subsubsection*{Returns}
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.
82 \subsection{glp\_read\_lp---read problem data in CPLEX LP format}
84 \subsubsection*{Synopsis}
86 \begin{verbatim}
87 int glp_read_lp(glp_prob *lp, const void *parm,
88 const char *fname);
89 \end{verbatim}
91 \subsubsection*{Description}
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}.)
97 The parameter \verb|parm| is reserved for use in the future and must be
98 specified as \verb|NULL|.
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''.)
105 Note that before reading data the current content of the problem object
106 is completely erased with the routine \verb|glp_erase_prob|.
108 \subsubsection*{Returns}
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.
113 \subsection{glp\_write\_lp---write problem data in CPLEX LP format}
115 \subsubsection*{Synopsis}
117 \begin{verbatim}
118 int glp_write_lp(glp_prob *lp, const void *parm,
119 const char *fname);
120 \end{verbatim}
122 \subsubsection*{Description}
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}.)
128 The parameter \verb|parm| is reserved for use in the future and must be
129 specified as \verb|NULL|.
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.)
136 \subsubsection*{Returns}
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.
142 \subsection{glp\_read\_prob---read problem data in GLPK format}
144 \subsubsection*{Synopsis}
146 \begin{verbatim}
147 int glp_read_prob(glp_prob *P, int flags, const char *fname);
148 \end{verbatim}
150 \subsubsection*{Description}
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.)
156 The parameter \verb|flags| is reserved for use in the future and should
157 be specified as zero.
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''.)
164 Note that before reading data the current content of the problem object
165 is completely erased with the routine \verb|glp_erase_prob|.
167 \subsubsection*{Returns}
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.
173 \subsubsection*{GLPK LP/MIP format}
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.
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.
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|.
195 \begin{verbatim}
196 c This is an example of comment line
197 \end{verbatim}
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:
203 \begin{verbatim}
204 p CLASS DIR ROWS COLS NONZ
205 \end{verbatim}
207 The lower-case letter \verb|p| specifies that this is the problem line.
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).
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).
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.
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:
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}
235 The lower-case letter \verb|i| specifies that this is the row
236 descriptor line.
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.
242 The next lower-case letter specifies the row type as follows:
244 \verb|f| --- free (unbounded) row: $-\infty<\sum a_jx_j<+\infty$;
246 \verb|l| --- inequality constraint of `$\geq$' type:
247 $\sum a_jx_j\geq b$;
249 \verb|u| --- inequality constraint of `$\leq$' type:
250 $\sum a_jx_j\leq b$;
252 \verb|d| --- double-sided inequality constraint:
253 $b_1\leq\sum a_jx_j\leq b_2$;
255 \verb|s| --- equality constraint: $\sum a_jx_j=b$.
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.
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.
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:
271 \bigskip
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}
283 \bigskip
285 The lower-case letter \verb|j| specifies that this is the column
286 descriptor line.
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.
292 The \verb|KIND| field is used only for MIP problems and specifies the
293 column kind as follows:
295 \verb|c| --- continuous column;
297 \verb|i| --- integer column;
299 \verb|b| --- binary column (in this case all remaining fields must be
300 omitted).
302 The next lower-case letter specifies the column type as follows:
304 \verb|f| --- free (unbounded) column: $-\infty<x<+\infty$;
306 \verb|l| --- column with lower bound: $x\geq l$;
308 \verb|u| --- column with upper bound: $x\leq u$;
310 \verb|d| --- double-bounded column: $l\leq x\leq u$;
312 \verb|s| --- fixed column: $x=s$.
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.
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).
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:
327 \begin{verbatim}
328 a ROW COL VAL
329 \end{verbatim}
331 The lower-case letter \verb|a| specifies that this is the coefficient
332 descriptor line.
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.
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.
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.
347 The \verb|VAL| field contains a floating-point coefficient value (it is
348 allowed to specify zero value in this field).
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.
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:
358 \begin{verbatim}
359 n p NAME
360 n z NAME
361 n i ROW NAME
362 n j COL NAME
363 \end{verbatim}
365 The lower-case letter \verb|n| specifies that this is the symbolic name
366 descriptor line.
368 The next lower-case letter specifies which object should be assigned a
369 symbolic name:
371 \verb|p| --- problem instance;
373 \verb|z| --- objective function;
375 \verb|i| --- row (constraint);
377 \verb|j| --- column (variable).
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.
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.
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.
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:
395 \begin{verbatim}
396 e
397 \end{verbatim}
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.
402 \subsubsection*{Example of data file in GLPK LP/MIP format}
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''.
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}
503 \newpage
505 \subsection{glp\_write\_prob---write problem data in GLPK format}
507 \subsubsection*{Synopsis}
509 \begin{verbatim}
510 int glp_write_prob(glp_prob *P, int flags, const char *fname);
511 \end{verbatim}
513 \subsubsection*{Description}
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''.)
519 The parameter \verb|flags| is reserved for use in the future and should
520 be specified as zero.
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.)
527 \subsubsection*{Returns}
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.
533 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
535 \newpage
537 \section{Routines for processing MathProg models}
539 \subsection{Introduction}
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.
554 The processing of a model written in GNU MathProg includes several
555 steps, which should be performed in the following order:
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}
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.
590 \subsubsection*{Example 1}
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.
598 \begin{small}
599 \begin{verbatim}
600 /* mplsamp1.c */
602 #include <stdio.h>
603 #include <stdlib.h>
604 #include <glpk.h>
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 }
631 /* eof */
632 \end{verbatim}
633 \end{small}
635 \subsubsection*{Example 2}
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.
644 \begin{small}
645 \begin{verbatim}
646 /* mplsamp2.c */
648 #include <stdio.h>
649 #include <stdlib.h>
650 #include <glpk.h>
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 }
684 /* eof */
685 \end{verbatim}
686 \end{small}
688 \subsection{glp\_mpl\_alloc\_wksp---allocate the translator workspace}
690 \subsubsection*{Synopsis}
692 \begin{verbatim}
693 glp_tran *glp_mpl_alloc_wksp(void);
694 \end{verbatim}
696 \subsubsection*{Description}
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.)
702 \subsubsection*{Returns}
704 The routine returns a pointer to the workspace, which should be used in
705 all subsequent operations.
707 \subsection{glp\_mpl\_read\_model---read and translate model section}
709 \subsubsection*{Synopsis}
711 \begin{verbatim}
712 int glp_mpl_read_model(glp_tran *tran, const char *fname,
713 int skip);
714 \end{verbatim}
716 \subsubsection*{Description}
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.
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).
729 \subsubsection*{Returns}
731 If the operation is successful, the routine returns zero. Otherwise
732 the routine prints an error message and returns non-zero.
734 \subsection{glp\_mpl\_read\_data---read and translate data section}
736 \subsubsection*{Synopsis}
738 \begin{verbatim}
739 int glp_mpl_read_data(glp_tran *tran, const char *fname);
740 \end{verbatim}
742 \subsubsection*{Description}
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.
749 \subsubsection*{Returns}
751 If the operation is successful, the routine returns zero. Otherwise
752 the routine prints an error message and returns non-zero.
754 \subsection{glp\_mpl\_generate---generate the model}
756 \subsubsection*{Synopsis}
758 \begin{verbatim}
759 int glp_mpl_generate(glp_tran *tran, const char *fname);
760 \end{verbatim}
762 \subsubsection*{Description}
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).
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.
774 \subsubsection*{Returns}
776 If the operation is successful, the routine returns zero. Otherwise
777 the routine prints an error message and returns non-zero.
779 \subsection{glp\_mpl\_build\_prob---build problem instance from the
780 model}
782 \subsubsection*{Synopsis}
784 \begin{verbatim}
785 void glp_mpl_build_prob(glp_tran *tran, glp_prob *prob);
786 \end{verbatim}
788 \subsubsection*{Description}
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|.
795 \subsection{glp\_mpl\_postsolve---postsolve the model}
797 \subsubsection*{Synopsis}
799 \begin{verbatim}
800 int glp_mpl_postsolve(glp_tran *tran, glp_prob *prob,
801 int sol);
802 \end{verbatim}
804 \subsubsection*{Description}
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.
811 The parameter \verb|sol| specifies which solution should be copied
812 from the problem object to the workspace as follows:
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}
820 \subsubsection*{Returns}
822 If the operation is successful, the routine returns zero. Otherwise
823 the routine prints an error message and returns non-zero.
825 \subsection{glp\_mpl\_free\_wksp---free the translator workspace}
827 \subsubsection*{Synopsis}
829 \begin{verbatim}
830 void glp_mpl_free_wksp(glp_tran *tran);
831 \end{verbatim}
833 \subsubsection*{Description}
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.
839 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
841 \newpage
843 \section{Problem solution reading/writing routines}
845 \subsection{glp\_print\_sol---write basic solution in printable format}
847 \subsubsection*{Synopsis}
849 \begin{verbatim}
850 int glp_print_sol(glp_prob *lp, const char *fname);
851 \end{verbatim}
853 \subsubsection*{Description}
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.
860 Information reported by the routine \verb|glp_print_sol| is intended
861 mainly for visual analysis.
863 \subsubsection*{Returns}
865 If no errors occurred, the routine returns zero. Otherwise the routine
866 prints an error message and returns non-zero.
868 \subsection{glp\_read\_sol---read basic solution from text file}
870 \subsubsection*{Synopsis}
872 \begin{verbatim}
873 int glp_read_sol(glp_prob *lp, const char *fname);
874 \end{verbatim}
876 \subsubsection*{Description}
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.
882 For the file format see description of the routine \verb|glp_write_sol|.
884 \subsubsection*{Returns}
886 On success the routine returns zero, otherwise non-zero.
888 \newpage
890 \subsection{glp\_write\_sol---write basic solution to text file}
892 \subsubsection*{Synopsis}
894 \begin{verbatim}
895 int glp_write_sol(glp_prob *lp, const char *fname);
896 \end{verbatim}
898 \subsubsection*{Description}
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|.
904 \subsubsection*{Returns}
906 On success the routine returns zero, otherwise non-zero.
908 \subsubsection*{File format}
910 The file created by the routine \verb|glp_write_sol| is a plain text
911 file, which contains the following information:
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}
924 \noindent
925 where:
927 \noindent
928 $m$ is the number of rows (auxiliary variables);
930 \noindent
931 $n$ is the number of columns (structural variables);
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);
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);
943 \noindent
944 \verb|obj_val| is the objective value;
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);
951 \noindent
952 \verb|r_prim[i]|, $i=1,\dots,m$, is the primal value of $i$-th row;
954 \noindent
955 \verb|r_dual[i]|, $i=1,\dots,m$, is the dual value of $i$-th row;
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);
962 \noindent
963 \verb|c_prim[j]|, $j=1,\dots,n$, is the primal value of $j$-th column;
965 \noindent
966 \verb|c_dual[j]|, $j=1,\dots,n$, is the dual value of $j$-th column.
968 \subsection{glp\_print\_ipt---write interior-point solution in
969 printable format}
971 \subsubsection*{Synopsis}
973 \begin{verbatim}
974 int glp_print_ipt(glp_prob *lp, const char *fname);
975 \end{verbatim}
977 \subsubsection*{Description}
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.
984 Information reported by the routine \verb|glp_print_ipt| is intended
985 mainly for visual analysis.
987 \subsubsection*{Returns}
989 If no errors occurred, the routine returns zero. Otherwise the routine
990 prints an error message and returns non-zero.
992 \subsection{glp\_read\_ipt---read interior-point solution from text
993 file}
995 \subsubsection*{Synopsis}
997 \begin{verbatim}
998 int glp_read_ipt(glp_prob *lp, const char *fname);
999 \end{verbatim}
1001 \subsubsection*{Description}
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.
1007 For the file format see description of the routine \verb|glp_write_ipt|.
1009 \subsubsection*{Returns}
1011 On success the routine returns zero, otherwise non-zero.
1013 \subsection{glp\_write\_ipt---write interior-point solution to text
1014 file}
1016 \subsubsection*{Synopsis}
1018 \begin{verbatim}
1019 int glp_write_ipt(glp_prob *lp, const char *fname);
1020 \end{verbatim}
1022 \subsubsection*{Description}
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|.
1029 \subsubsection*{Returns}
1031 On success the routine returns zero, otherwise non-zero.
1033 \subsubsection*{File format}
1035 The file created by the routine \verb|glp_write_ipt| is a plain text
1036 file, which contains the following information:
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}
1049 \noindent
1050 where:
1052 \noindent
1053 $m$ is the number of rows (auxiliary variables);
1055 \noindent
1056 $n$ is the number of columns (structural variables);
1058 \noindent
1059 \verb|stat| is the solution status (\verb|GLP_UNDEF| = 1 or
1060 \verb|GLP_OPT| = 5);
1062 \noindent
1063 \verb|obj_val| is the objective value;
1065 \noindent
1066 \verb|r_prim[i]|, $i=1,\dots,m$, is the primal value of $i$-th row;
1068 \noindent
1069 \verb|r_dual[i]|, $i=1,\dots,m$, is the dual value of $i$-th row;
1071 \noindent
1072 \verb|c_prim[j]|, $j=1,\dots,n$, is the primal value of $j$-th column;
1074 \noindent
1075 \verb|c_dual[j]|, $j=1,\dots,n$, is the dual value of $j$-th column.
1077 \subsection{glp\_print\_mip---write MIP solution in printable format}
1079 \subsubsection*{Synopsis}
1081 \begin{verbatim}
1082 int glp_print_mip(glp_prob *lp, const char *fname);
1083 \end{verbatim}
1085 \subsubsection*{Description}
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.
1092 Information reported by the routine \verb|glp_print_mip| is intended
1093 mainly for visual analysis.
1095 \subsubsection*{Returns}
1097 If no errors occurred, the routine returns zero. Otherwise the routine
1098 prints an error message and returns non-zero.
1100 \newpage
1102 \subsection{glp\_read\_mip---read MIP solution from text file}
1104 \subsubsection*{Synopsis}
1106 \begin{verbatim}
1107 int glp_read_mip(glp_prob *mip, const char *fname);
1108 \end{verbatim}
1110 \subsubsection*{Description}
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.
1116 For the file format see description of the routine \verb|glp_write_mip|.
1118 \subsubsection*{Returns}
1120 On success the routine returns zero, otherwise non-zero.
1122 \subsection{glp\_write\_mip---write MIP solution to text file}
1124 \subsubsection*{Synopsis}
1126 \begin{verbatim}
1127 int glp_write_mip(glp_prob *mip, const char *fname);
1128 \end{verbatim}
1130 \subsubsection*{Description}
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|.
1136 \subsubsection*{Returns}
1138 On success the routine returns zero, otherwise non-zero.
1140 \subsubsection*{File format}
1142 The file created by the routine \verb|glp_write_sol| is a plain text
1143 file, which contains the following information:
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}
1156 \noindent
1157 where:
1159 \noindent
1160 $m$ is the number of rows (auxiliary variables);
1162 \noindent
1163 $n$ is the number of columns (structural variables);
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);
1169 \noindent
1170 \verb|obj_val| is the objective value;
1172 \noindent
1173 \verb|r_val[i]|, $i=1,\dots,m$, is the value of $i$-th row;
1175 \noindent
1176 \verb|c_val[j]|, $j=1,\dots,n$, is the value of $j$-th column.
1178 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1180 \newpage
1182 \section{Post-optimal analysis routines}
1184 \subsection{glp\_print\_ranges---print sensitivity analysis report}
1186 \subsubsection*{Synopsis}
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}
1193 \subsubsection*{Description}
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.)
1201 The parameter {\it len} specifies the length of the row/column list.
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.
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.
1215 The parameter {\it flags} is reserved for use in the future and must be
1216 specified as zero.
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.
1226 \subsubsection*{Returns}
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.
1232 \subsubsection*{Analysis report example}
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''.
1238 \subsubsection*{Structure of the analysis report}
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.
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.
1250 \bigskip
1252 \noindent
1253 {\it Generic information}
1255 \medskip
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.
1263 \medskip
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.
1269 \medskip
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.
1275 \medskip
1277 \noindent
1278 {\tt St} is the status of the row or column in the optimal solution:
1280 {\tt BS} --- non-active constraint (row), basic column;
1282 {\tt NL} --- inequality constraint having its lower right-hand side
1283 active (row), non-basic column having its lower bound active;
1285 {\tt NU} --- inequality constraint having its upper right-hand side
1286 active (row), non-basic column having its upper bound active;
1288 {\tt NS} --- active equality constraint (row), non-basic fixed column.
1290 {\tt NF} --- active free row, non-basic free (unbounded) column. (This
1291 case means that the optimal solution is dual degenerate.)
1293 \medskip
1295 \noindent
1296 {\tt Activity} is the (primal) value of the auxiliary variable (row) or
1297 structural variable (column) in the optimal solution.
1299 \medskip
1301 \noindent
1302 {\tt Slack} is the (primal) value of the row slack variable.
1304 \medskip
1306 \noindent
1307 {\tt Obj coef} is the objective coefficient of the column (structural
1308 variable).
1310 \begin{landscape}
1311 \begin{scriptsize}
1312 \begin{verbatim}
1313 GLPK 4.42 - SENSITIVITY ANALYSIS REPORT Page 1
1315 Problem: PLAN
1316 Objective: VALUE = 296.2166065 (MINimum)
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
1324 2 YIELD NS 2000.00000 . 2000.00000 1995.06864 -Inf 296.28365 BIN3
1325 -.01360 2000.00000 2014.03479 +Inf 296.02579 CU
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
1330 4 CU BS 83.96751 16.03249 -Inf 93.88467 -.30613 270.51157 MN
1331 . 100.00000 79.98213 .21474 314.24798 BIN5
1333 5 MN NU 40.00000 . -Inf 34.42336 -Inf 299.25255 BIN4
1334 -.54440 40.00000 41.68691 .54440 295.29825 BIN3
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
1339 7 AL NL 1500.00000 . 1500.00000 1485.78425 -.25199 292.63444 CU
1340 .25199 +Inf 1504.92126 +Inf 297.45669 BIN3
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}
1348 \begin{landscape}
1349 \begin{scriptsize}
1350 \begin{verbatim}
1351 GLPK 4.42 - SENSITIVITY ANALYSIS REPORT Page 2
1353 Problem: PLAN
1354 Objective: VALUE = 296.2166065 (MINimum)
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
1362 2 BIN2 BS 665.34296 .08000 . 802.22222 .01722 254.44822 BIN1
1363 . 2500.00000 313.43066 .08863 301.95652 MN
1365 3 BIN3 BS 490.25271 .17000 400.00000 788.61314 .15982 291.22807 MN
1366 . 800.00000 -347.42857 .17948 300.86548 BIN5
1368 4 BIN4 BS 424.18773 .12000 100.00000 710.52632 .10899 291.54745 MN
1369 . 700.00000 -256.15524 .14651 307.46010 BIN1
1371 5 BIN5 NL . .15000 . -201.78739 .13544 293.27940 BIN3
1372 .01456 1500.00000 58.79586 +Inf 297.07244 BIN3
1374 6 ALUM BS 299.63899 .21000 . 358.26772 .18885 289.87879 AL
1375 . +Inf 112.40876 .22622 301.07527 MN
1377 7 SILICON BS 120.57762 .38000 . 124.27093 .14828 268.27586 BIN5
1378 . +Inf 85.54745 .46667 306.66667 MN
1380 End of report
1381 \end{verbatim}
1382 \end{scriptsize}
1383 \end{landscape}
1385 \noindent
1386 {\tt Marginal} is the reduced cost (dual activity) of the auxiliary
1387 variable (row) or structural variable (column).
1389 \medskip
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}.
1396 \medskip
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}.
1403 \bigskip
1405 \noindent
1406 {\it Sensitivity analysis of active bounds}
1408 \medskip
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.
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.
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.
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.
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.
1457 \bigskip
1459 \noindent
1460 {\it Sensitivity analysis of objective coefficients at non-basic
1461 variables}
1463 \medskip
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).
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).
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.
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|'.
1498 \bigskip
1500 \noindent
1501 {\it Sensitivity analysis of objective coefficients at basic variables}
1503 \medskip
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.
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}.
1557 \newpage
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.
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.
1577 %* eof *%