COIN-OR::LEMON - Graph Library

source: glpk-cmake/doc/glpk03.tex @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 52.6 KB
RevLine 
[1]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}
12int glp_read_mps(glp_prob *lp, int fmt, const void *parm,
13      const char *fname);
14\end{verbatim}
15
16\subsubsection*{Description}
17
18The routine \verb|glp_read_mps| reads problem data in MPS format from a
19text file. (The MPS format is described in Appendix \ref{champs}, page
20\pageref{champs}.)
21
22The 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
29The parameter \verb|parm| is reserved for use in the future and must be
30specified as \verb|NULL|.
31
32The character string \verb|fname| specifies a name of the text file to
33be read in. (If the file name ends with suffix `\verb|.gz|', the file is
34assumed to be compressed, in which case the routine \verb|glp_read_mps|
35decompresses it ``on the fly''.)
36
37Note that before reading data the current content of the problem object
38is completely erased with the routine \verb|glp_erase_prob|.
39
40\subsubsection*{Returns}
41
42If the operation was successful, the routine \verb|glp_read_mps|
43returns zero. Otherwise, it prints an error message and returns
44non-zero.
45
46\subsection{glp\_write\_mps---write problem data in MPS format}
47
48\subsubsection*{Synopsis}
49
50\begin{verbatim}
51int glp_write_mps(glp_prob *lp, int fmt, const void *parm,
52      const char *fname);
53\end{verbatim}
54
55\subsubsection*{Description}
56
57The routine \verb|glp_write_mps| writes problem data in MPS format to a
58text file. (The MPS format is described in Appendix \ref{champs}, page
59\pageref{champs}.)
60
61The 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
68The parameter \verb|parm| is reserved for use in the future and must be
69specified as \verb|NULL|.
70
71The character string \verb|fname| specifies a name of the text file to
72be written out. (If the file name ends with suffix `\verb|.gz|', the
73file 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
78If the operation was successful, the routine \verb|glp_write_mps|
79returns zero. Otherwise, it prints an error message and returns
80non-zero.
81
82\subsection{glp\_read\_lp---read problem data in CPLEX LP format}
83
84\subsubsection*{Synopsis}
85
86\begin{verbatim}
87int glp_read_lp(glp_prob *lp, const void *parm,
88      const char *fname);
89\end{verbatim}
90
91\subsubsection*{Description}
92
93The routine \verb|glp_read_lp| reads problem data in CPLEX LP format
94from a text file. (The CPLEX LP format is described in Appendix
95\ref{chacplex}, page \pageref{chacplex}.)
96
97The parameter \verb|parm| is reserved for use in the future and must be
98specified as \verb|NULL|.
99
100The character string \verb|fname| specifies a name of the text file to
101be read in. (If the file name ends with suffix `\verb|.gz|', the file is
102assumed to be compressed, in which case the routine \verb|glp_read_lp|
103decompresses it ``on the fly''.)
104
105Note that before reading data the current content of the problem object
106is completely erased with the routine \verb|glp_erase_prob|.
107
108\subsubsection*{Returns}
109
110If the operation was successful, the routine \verb|glp_read_lp| returns
111zero. 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}
118int glp_write_lp(glp_prob *lp, const void *parm,
119      const char *fname);
120\end{verbatim}
121
122\subsubsection*{Description}
123
124The routine \verb|glp_write_lp| writes problem data in CPLEX LP format
125to a text file. (The CPLEX LP format is described in Appendix
126\ref{chacplex}, page \pageref{chacplex}.)
127
128The parameter \verb|parm| is reserved for use in the future and must be
129specified as \verb|NULL|.
130
131The character string \verb|fname| specifies a name of the text file to
132be written out. (If the file name ends with suffix `\verb|.gz|', the
133file 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
138If the operation was successful, the routine \verb|glp_write_lp|
139returns zero. Otherwise, it prints an error message and returns
140non-zero.
141
142\subsection{glp\_read\_prob---read problem data in GLPK format}
143
144\subsubsection*{Synopsis}
145
146\begin{verbatim}
147int glp_read_prob(glp_prob *P, int flags, const char *fname);
148\end{verbatim}
149
150\subsubsection*{Description}
151
152The routine \verb|glp_read_prob| reads problem data in the GLPK LP/MIP
153format from a text file. (For description of the GLPK LP/MIP format see
154below.)
155
156The parameter \verb|flags| is reserved for use in the future and should
157be specified as zero.
158
159The character string \verb|fname| specifies a name of the text file to
160be read in. (If the file name ends with suffix `\verb|.gz|', the file
161is assumed to be compressed, in which case the routine
162\verb|glp_read_prob| decompresses it ``on the fly''.)
163
164Note that before reading data the current content of the problem object
165is completely erased with the routine \verb|glp_erase_prob|.
166
167\subsubsection*{Returns}
168
169If the operation was successful, the routine \verb|glp_read_prob|
170returns zero. Otherwise, it prints an error message and returns
171non-zero.
172
173\subsubsection*{GLPK LP/MIP format}
174
175The GLPK LP/MIP format is a DIMACS-like format.\footnote{The DIMACS
176formats were developed by the Center for Discrete Mathematics and
177Theoretical Computer Science (DIMACS) to facilitate exchange of problem
178data. For details see: {\tt <http://dimacs.rutgers.edu/Challenges/>}. }
179The file in this format is a plain ASCII text file containing lines of
180several types described below. A line is terminated with the end-of-line
181character. Fields in each line are separated by at least one blank
182space. Each line begins with a one-character designator to identify the
183line type.
184
185The first line of the data file must be the problem line (except
186optional comment lines, which may precede the problem line). The last
187line of the data file must be the end line. Other lines may follow in
188arbitrary order, however, duplicate lines are not allowed.
189
190\paragraph{Comment lines.} Comment lines give human-readable
191information about the data file and are ignored by GLPK routines.
192Comment lines can appear anywhere in the data file. Each comment line
193begins 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
200data file. This line must appear before any other lines except comment
201lines and has the following format:
202
203\begin{verbatim}
204   p CLASS DIR ROWS COLS NONZ
205\end{verbatim}
206
207The lower-case letter \verb|p| specifies that this is the problem line.
208
209The \verb|CLASS| field defines the problem class and can contain either
210the keyword \verb|lp| (that means linear programming problem) or
211\verb|mip| (that means mixed integer programming problem).
212
213The \verb|DIR| field defines the optimization direction (that is, the
214objective function sense) and can contain either the keyword \verb|min|
215(that means minimization) or \verb|max| (that means maximization).
216
217The \verb|ROWS|, \verb|COLS|, and \verb|NONZ| fields contain
218non-negative integer values specifying, respectively, the number of
219rows (constraints), columns (variables), and non-zero constraint
220coefficients in the problem instance. Note that \verb|NONZ| value does
221not account objective coefficients.
222
223\paragraph{Row descriptors.} There must be at most one row descriptor
224line in the data file for each row (constraint). This line has one of
225the 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
235The lower-case letter \verb|i| specifies that this is the row
236descriptor line.
237
238The \verb|ROW| field specifies the row ordinal number, an integer
239between 1 and $m$, where $m$ is the number of rows in the problem
240instance.
241
242The 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
257The \verb|RHS| field contains a floaing-point value specifying the
258row right-hand side. The \verb|RHS1| and \verb|RHS2| fields contain
259floating-point values specifying, respectively, the lower and upper
260right-hand sides for the double-sided row.
261
262If for some row its descriptor line does not appear in the data file,
263by default that row is assumed to be an equality constraint with zero
264right-hand side.
265
266\paragraph{Column descriptors.} There must be at most one column
267descriptor line in the data file for each column (variable). This line
268has one of the following formats depending on the problem class
269specified in the problem line:
270
271\bigskip
272
273\begin{tabular}{@{}l@{\hspace*{40pt}}l}
274LP 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
285The lower-case letter \verb|j| specifies that this is the column
286descriptor line.
287
288The \verb|COL| field specifies the column ordinal number, an integer
289between 1 and $n$, where $n$ is the number of columns in the problem
290instance.
291
292The \verb|KIND| field is used only for MIP problems and specifies the
293column 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
300omitted).
301
302The 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
314The \verb|BND| field contains a floating-point value that specifies the
315column bound. The \verb|BND1| and \verb|BND2| fields contain
316floating-point values specifying, respectively, the lower and upper
317bounds for the double-bounded column.
318
319If for some column its descriptor line does not appear in the file, by
320default that column is assumed to be non-negative (in case of LP class)
321or binary (in case of MIP class).
322
323\paragraph{Coefficient descriptors.} There must be exactly one
324coefficient descriptor line in the data file for each non-zero
325objective or constraint coefficient. This line has the following format:
326
327\begin{verbatim}
328   a ROW COL VAL
329\end{verbatim}
330
331The lower-case letter \verb|a| specifies that this is the coefficient
332descriptor line.
333
334For objective coefficients the \verb|ROW| field must contain 0. For
335constraint coefficients the \verb|ROW| field specifies the row ordinal
336number, an integer between 1 and $m$, where $m$ is the number of rows
337in the problem instance.
338
339The \verb|COL| field specifies the column ordinal number, an integer
340between 1 and $n$, where $n$ is the number of columns in the problem
341instance.
342
343If both the \verb|ROW| and \verb|COL| fields contain 0, the line
344specifies the constant term (``shift'') of the objective function
345rather than objective coefficient.
346
347The \verb|VAL| field contains a floating-point coefficient value (it is
348allowed to specify zero value in this field).
349
350The number of constraint coefficient descriptor lines must be exactly
351the same as specified in the field \verb|NONZ| of the problem line.
352
353\paragraph{Symbolic name descriptors.} There must be at most one
354symbolic name descriptor line for the problem instance, objective
355function, each row (constraint), and each column (variable). This line
356has 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
365The lower-case letter \verb|n| specifies that this is the symbolic name
366descriptor line.
367
368The next lower-case letter specifies which object should be assigned a
369symbolic 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
379The \verb|ROW| field specifies the row ordinal number, an integer
380between 1 and $m$, where $m$ is the number of rows in the problem
381instance.
382
383The \verb|COL| field specifies the column ordinal number, an integer
384between 1 and $n$, where $n$ is the number of columns in the problem
385instance.
386
387The \verb|NAME| field contains the symbolic name, a sequence from 1 to
388255 arbitrary graphic ASCII characters, assigned to corresponding
389object.
390
391\paragraph{End line.} There must be exactly one end line in the data
392file. This line must appear last in the file and has the following
393format:
394
395\begin{verbatim}
396   e
397\end{verbatim}
398
399The lower-case letter \verb|e| specifies that this is the end line.
400Anything that follows the end line is ignored by GLPK routines.
401
402\subsubsection*{Example of data file in GLPK LP/MIP format}
403
404The following example of a data file in GLPK LP/MIP format specifies
405the same LP problem as in Subsection ``Example of MPS file''.
406
407\begin{center}
408\footnotesize\tt
409\begin{tabular}{l@{\hspace*{50pt}}}
410p lp min 8 7 48   \\
411n p PLAN          \\
412n z VALUE         \\
413i 1 f             \\
414n i 1 VALUE       \\
415i 2 s 2000        \\
416n i 2 YIELD       \\
417i 3 u 60          \\
418n i 3 FE          \\
419i 4 u 100         \\
420n i 4 CU          \\
421i 5 u 40          \\
422n i 5 MN          \\
423i 6 u 30          \\
424n i 6 MG          \\
425i 7 l 1500        \\
426n i 7 AL          \\
427i 8 d 250 300     \\
428n i 8 SI          \\
429j 1 d 0 200       \\
430n j 1 BIN1        \\
431j 2 d 0 2500      \\
432n j 2 BIN2        \\
433j 3 d 400 800     \\
434n j 3 BIN3        \\
435j 4 d 100 700     \\
436n j 4 BIN4        \\
437j 5 d 0 1500      \\
438n j 5 BIN5        \\
439n j 6 ALUM        \\
440n j 7 SILICON     \\
441a 0 1 0.03        \\
442a 0 2 0.08        \\
443a 0 3 0.17        \\
444a 0 4 0.12        \\
445a 0 5 0.15        \\
446a 0 6 0.21        \\
447a 0 7 0.38        \\
448a 1 1 0.03        \\
449a 1 2 0.08        \\
450a 1 3 0.17        \\
451a 1 4 0.12        \\
452a 1 5 0.15        \\
453a 1 6 0.21        \\
454\end{tabular}
455\begin{tabular}{|@{\hspace*{80pt}}l}
456a 1 7 0.38        \\
457a 2 1 1           \\
458a 2 2 1           \\
459a 2 3 1           \\
460a 2 4 1           \\
461a 2 5 1           \\
462a 2 6 1           \\
463a 2 7 1           \\
464a 3 1 0.15        \\
465a 3 2 0.04        \\
466a 3 3 0.02        \\
467a 3 4 0.04        \\
468a 3 5 0.02        \\
469a 3 6 0.01        \\
470a 3 7 0.03        \\
471a 4 1 0.03        \\
472a 4 2 0.05        \\
473a 4 3 0.08        \\
474a 4 4 0.02        \\
475a 4 5 0.06        \\
476a 4 6 0.01        \\
477a 5 1 0.02        \\
478a 5 2 0.04        \\
479a 5 3 0.01        \\
480a 5 4 0.02        \\
481a 5 5 0.02        \\
482a 6 1 0.02        \\
483a 6 2 0.03        \\
484a 6 5 0.01        \\
485a 7 1 0.7         \\
486a 7 2 0.75        \\
487a 7 3 0.8         \\
488a 7 4 0.75        \\
489a 7 5 0.8         \\
490a 7 6 0.97        \\
491a 8 1 0.02        \\
492a 8 2 0.06        \\
493a 8 3 0.08        \\
494a 8 4 0.12        \\
495a 8 5 0.02        \\
496a 8 6 0.01        \\
497a 8 7 0.97        \\
498e 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}
510int glp_write_prob(glp_prob *P, int flags, const char *fname);
511\end{verbatim}
512
513\subsubsection*{Description}
514
515The routine \verb|glp_write_prob| writes problem data in the GLPK
516LP/MIP format to a text file. (For description of the GLPK LP/MIP
517format see Subsection ``Read problem data in GLPK format''.)
518
519The parameter \verb|flags| is reserved for use in the future and should
520be specified as zero.
521
522The character string \verb|fname| specifies a name of the text file to
523be written out. (If the file name ends with suffix `\verb|.gz|', the
524file 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
529If the operation was successful, the routine \verb|glp_read_prob|
530returns zero. Otherwise, it prints an error message and returns
531non-zero.
532
533%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
534
535\newpage
536
537\section{Routines for processing MathProg models}
538
539\subsection{Introduction}
540
541GLPK supports the {\it GNU MathProg modeling language}.\footnote{The
542GNU MathProg modeling language is a subset of the AMPL language. For
543its detailed description see the document ``Modeling Language GNU
544MathProg: Language Reference'' included in the GLPK distribution.}
545As a rule, models written in MathProg are solved with the GLPK LP/MIP
546stand-alone solver \verb|glpsol| (see Appendix D) and do not need any
547programming with API routines. However, for various reasons the user
548may need to process MathProg models directly in his/her application
549program, in which case he/she may use API routines described in this
550section. These routines provide an interface to the {\it MathProg
551translator}, a component of GLPK, which translates MathProg models into
552an internal code and then interprets (executes) this code.
553
554The processing of a model written in GNU MathProg includes several
555steps, which should be performed in the following order:
556
557\begin{enumerate}
558\item{\it Allocating the workspace.}
559The translator allocates the workspace, an internal data structure used
560on all subsequent steps.
561\item{\it Reading model section.} The translator reads model section
562and, optionally, data section from a specified text file and translates
563them into the internal code. If necessary, on this step data section
564may be ignored.
565\item{\it Reading data section(s).} The translator reads one or more
566data sections from specified text file(s) and translates them into the
567internal code.
568\item{\it Generating the model.} The translator executes the internal
569code to evaluate the content of the model objects such as sets,
570parameters, variables, constraints, and objectives. On this step the
571execution is suspended at the solve statement.
572\item {\it Building the problem object.} The translator obtains all
573necessary information from the workspace and builds the standard
574problem object (that is, the program object of type \verb|glp_prob|).
575\item{\it Solving the problem.} On this step the problem object built
576on the previous step is passed to a solver, which solves the problem
577instance and stores its solution back to the problem object.
578\item{\it Postsolving the model.} The translator copies the solution
579from the problem object to the workspace and then executes the internal
580code from the solve statement to the end of the model. (If model has
581no solve statement, the translator does nothing on this step.)
582\item{\it Freeing the workspace.} The translator frees all the memory
583allocated to the workspace.
584\end{enumerate}
585
586Note that the MathProg translator performs no error correction, so if
587any of steps 2 to 7 fails (due to errors in the model), the application
588program should terminate processing and go to step 8.
589
590\subsubsection*{Example 1}
591
592In this example the program reads model and data sections from input
593file \verb|egypt.mod|\footnote{This is an example model included in
594the GLPK distribution.} and writes the model to output file
595\verb|egypt.mps| in free MPS format (see Appendix B). No solution is
596performed.
597
598\begin{small}
599\begin{verbatim}
600/* mplsamp1.c */
601
602#include <stdio.h>
603#include <stdlib.h>
604#include <glpk.h>
605
606int 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");
626skip: 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
637In this example the program reads model section from file
638\verb|sudoku.mod|\footnote{This is an example model which is included
639in the GLPK distribution along with alternative data file
640{\tt sudoku.dat}.} ignoring data section in this file, reads alternative
641data section from file \verb|sudoku.dat|, solves the problem instance
642and 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
652int 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");
679skip: 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}
693glp_tran *glp_mpl_alloc_wksp(void);
694\end{verbatim}
695
696\subsubsection*{Description}
697
698The routine \verb|glp_mpl_alloc_wksp| allocates the MathProg translator
699work\-space. (Note that multiple instances of the workspace may be
700allocated, if necessary.)
701
702\subsubsection*{Returns}
703
704The routine returns a pointer to the workspace, which should be used in
705all subsequent operations.
706
707\subsection{glp\_mpl\_read\_model---read and translate model section}
708
709\subsubsection*{Synopsis}
710
711\begin{verbatim}
712int glp_mpl_read_model(glp_tran *tran, const char *fname,
713      int skip);
714\end{verbatim}
715
716\subsubsection*{Description}
717
718The routine \verb|glp_mpl_read_model| reads model section and,
719optionally, data section, which may follow the model section, from a
720text file, whose name is the character string \verb|fname|, performs
721translation of model statements and data blocks, and stores all the
722information in the workspace.
723
724The parameter \verb|skip| is a flag. If the input file contains the
725data section and this flag is non-zero, the data section is not read as
726if there were no data section and a warning message is printed. This
727allows reading data section(s) from other file(s).
728
729\subsubsection*{Returns}
730
731If the operation is successful, the routine returns zero. Otherwise
732the 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}
739int glp_mpl_read_data(glp_tran *tran, const char *fname);
740\end{verbatim}
741
742\subsubsection*{Description}
743
744The routine \verb|glp_mpl_read_data| reads data section from a text
745file, whose name is the character string \verb|fname|, performs
746translation of data blocks, and stores the data read in the translator
747workspace. If necessary, this routine may be called more than once.
748
749\subsubsection*{Returns}
750
751If the operation is successful, the routine returns zero. Otherwise
752the 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}
759int glp_mpl_generate(glp_tran *tran, const char *fname);
760\end{verbatim}
761
762\subsubsection*{Description}
763
764The routine \verb|glp_mpl_generate| generates the model using its
765description stored in the translator workspace. This operation means
766generating all variables, constraints, and objectives, executing check
767and display statements, which precede the solve statement (if it is
768presented).
769
770The character string \verb|fname| specifies the name of an output text
771file, to which output produced by display statements should be written.
772If \verb|fname| is \verb|NULL|, the output is sent to the terminal.
773
774\subsubsection*{Returns}
775
776If the operation is successful, the routine returns zero. Otherwise
777the routine prints an error message and returns non-zero.
778
779\subsection{glp\_mpl\_build\_prob---build problem instance from the
780model}
781
782\subsubsection*{Synopsis}
783
784\begin{verbatim}
785void glp_mpl_build_prob(glp_tran *tran, glp_prob *prob);
786\end{verbatim}
787
788\subsubsection*{Description}
789
790The routine \verb|glp_mpl_build_prob| obtains all necessary information
791from the translator workspace and stores it in the specified problem
792object \verb|prob|. Note that before building the current content of
793the 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}
800int glp_mpl_postsolve(glp_tran *tran, glp_prob *prob,
801      int sol);
802\end{verbatim}
803
804\subsubsection*{Description}
805
806The routine \verb|glp_mpl_postsolve| copies the solution from the
807specified problem object \verb|prob| to the translator workspace and
808then executes all the remaining model statements, which follow the
809solve statement.
810
811The parameter \verb|sol| specifies which solution should be copied
812from 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
822If the operation is successful, the routine returns zero. Otherwise
823the 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}
830void glp_mpl_free_wksp(glp_tran *tran);
831\end{verbatim}
832
833\subsubsection*{Description}
834
835The routine \verb|glp_mpl_free_wksp| frees all the memory allocated to
836the translator workspace. It also frees all other resources, which are
837still 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}
850int glp_print_sol(glp_prob *lp, const char *fname);
851\end{verbatim}
852
853\subsubsection*{Description}
854
855The routine \verb|glp_print_sol writes| the current basic solution of
856an LP problem, which is specified by the pointer \verb|lp|, to a text
857file, whose name is the character string \verb|fname|, in printable
858format.
859
860Information reported by the routine \verb|glp_print_sol| is intended
861mainly for visual analysis.
862
863\subsubsection*{Returns}
864
865If no errors occurred, the routine returns zero. Otherwise the routine
866prints 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}
873int glp_read_sol(glp_prob *lp, const char *fname);
874\end{verbatim}
875
876\subsubsection*{Description}
877
878The routine \verb|glp_read_sol| reads basic solution from a text file
879whose name is specified by the parameter \verb|fname| into the problem
880object.
881
882For the file format see description of the routine \verb|glp_write_sol|.
883
884\subsubsection*{Returns}
885
886On 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}
895int glp_write_sol(glp_prob *lp, const char *fname);
896\end{verbatim}
897
898\subsubsection*{Description}
899
900The routine \verb|glp_write_sol| writes the current basic solution to a
901text file whose name is specified by the parameter \verb|fname|. This
902file can be read back with the routine \verb|glp_read_sol|.
903
904\subsubsection*{Returns}
905
906On success the routine returns zero, otherwise non-zero.
907
908\subsubsection*{File format}
909
910The file created by the routine \verb|glp_write_sol| is a plain text
911file, 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
925where:
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
969printable format}
970
971\subsubsection*{Synopsis}
972
973\begin{verbatim}
974int glp_print_ipt(glp_prob *lp, const char *fname);
975\end{verbatim}
976
977\subsubsection*{Description}
978
979The routine \verb|glp_print_ipt| writes the current interior point
980solution  of an LP problem, which the parameter \verb|lp| points to, to
981a text file, whose name is the character string \verb|fname|, in
982printable format.
983
984Information reported by the routine \verb|glp_print_ipt| is intended
985mainly for visual analysis.
986
987\subsubsection*{Returns}
988
989If no errors occurred, the routine returns zero. Otherwise the routine
990prints an error message and returns non-zero.
991
992\subsection{glp\_read\_ipt---read interior-point solution from text
993file}
994
995\subsubsection*{Synopsis}
996
997\begin{verbatim}
998int glp_read_ipt(glp_prob *lp, const char *fname);
999\end{verbatim}
1000
1001\subsubsection*{Description}
1002
1003The routine \verb|glp_read_ipt| reads interior-point solution from a
1004text file whose name is specified by the parameter \verb|fname| into the
1005problem object.
1006
1007For the file format see description of the routine \verb|glp_write_ipt|.
1008
1009\subsubsection*{Returns}
1010
1011On success the routine returns zero, otherwise non-zero.
1012
1013\subsection{glp\_write\_ipt---write interior-point solution to text
1014file}
1015
1016\subsubsection*{Synopsis}
1017
1018\begin{verbatim}
1019int glp_write_ipt(glp_prob *lp, const char *fname);
1020\end{verbatim}
1021
1022\subsubsection*{Description}
1023
1024The routine \verb|glp_write_ipt| writes the current interior-point
1025solution 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
1031On success the routine returns zero, otherwise non-zero.
1032
1033\subsubsection*{File format}
1034
1035The file created by the routine \verb|glp_write_ipt| is a plain text
1036file, 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
1050where:
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}
1082int glp_print_mip(glp_prob *lp, const char *fname);
1083\end{verbatim}
1084
1085\subsubsection*{Description}
1086
1087The routine \verb|glp_print_mip| writes a best known integer solution
1088of a MIP problem, which is specified by the pointer \verb|lp|, to a text
1089file, whose name is the character string \verb|fname|, in printable
1090format.
1091
1092Information reported by the routine \verb|glp_print_mip| is intended
1093mainly for visual analysis.
1094
1095\subsubsection*{Returns}
1096
1097If no errors occurred, the routine returns zero. Otherwise the routine
1098prints 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}
1107int glp_read_mip(glp_prob *mip, const char *fname);
1108\end{verbatim}
1109
1110\subsubsection*{Description}
1111
1112The routine \verb|glp_read_mip| reads MIP solution from a text file
1113whose name is specified by the parameter \verb|fname| into the problem
1114object.
1115
1116For the file format see description of the routine \verb|glp_write_mip|.
1117
1118\subsubsection*{Returns}
1119
1120On 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}
1127int glp_write_mip(glp_prob *mip, const char *fname);
1128\end{verbatim}
1129
1130\subsubsection*{Description}
1131
1132The routine \verb|glp_write_mip| writes the current MIP solution to a
1133text file whose name is specified by the parameter \verb|fname|. This
1134file can be read back with the routine \verb|glp_read_mip|.
1135
1136\subsubsection*{Returns}
1137
1138On success the routine returns zero, otherwise non-zero.
1139
1140\subsubsection*{File format}
1141
1142The file created by the routine \verb|glp_write_sol| is a plain text
1143file, 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
1157where:
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}
1189int 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
1195The routine \verb|glp_print_ranges| performs sensitivity analysis of
1196current optimal basic solution and writes the analysis report in
1197human-readable format to a text file, whose name is the character
1198string {\it fname}. (Detailed description of the report structure is
1199given below.)
1200
1201The parameter {\it len} specifies the length of the row/column list.
1202
1203The array {\it list} specifies ordinal number of rows and columns to be
1204analyzed. The ordinal numbers should be passed in locations
1205{\it list}[1], {\it list}[2], \dots, {\it list}[{\it len}]. Ordinal
1206numbers 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
1208of rows and columns in the problem object. Rows and columns appear in
1209the analysis report in the same order as they follow in the array list.
1210
1211It is allowed to specify $len=0$, in which case the array {\it list} is
1212not used (so it can be specified as \verb|NULL|), and the routine
1213performs analysis for all rows and columns of the problem object.
1214
1215The parameter {\it flags} is reserved for use in the future and must be
1216specified as zero.
1217
1218On entry to the routine \verb|glp_print_ranges| the current basic
1219solution must be optimal and the basis factorization must exist.
1220The application program can check that with the routine
1221\verb|glp_bf_exists|, and if the factorization does
1222not exist, compute it with the routine \verb|glp_factorize|. Note that
1223if the LP preprocessor is not used, on normal exit from the simplex
1224solver routine \verb|glp_simplex| the basis factorization always exists.
1225
1226\subsubsection*{Returns}
1227
1228If the operation was successful, the routine \verb|glp_print_ranges|
1229returns zero. Otherwise, it prints an error message and returns
1230non-zero.
1231
1232\subsubsection*{Analysis report example}
1233
1234An example of the sensitivity analysis report is shown on the next two
1235pages. This example corresponds to the example of LP problem described
1236in Subsection ``Example of MPS file''.
1237
1238\subsubsection*{Structure of the analysis report}
1239
1240For each row and column specified in the array {\it list} the routine
1241prints two lines containing generic information and analysis
1242information, which depends on the status of corresponding row or column.
1243
1244Note that analysis of a row is analysis of its auxiliary variable,
1245which is equal to the row linear form $\sum a_jx_j$, and analysis of
1246a column is analysis of corresponding structural variable. Therefore,
1247formally, on performing the sensitivity analysis there is no difference
1248between 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.
1259Rows are numbered from 1 to $m$, and columns are numbered from 1 to $n$,
1260where $m$ and $n$ are, resp., the total number of rows and columns in
1261the problem object.
1262
1263\medskip
1264
1265\noindent
1266{\tt Row name} is the symbolic name assigned to the row. If the row has
1267no 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
1273column 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
1283active (row), non-basic column having its lower bound active;
1284
1285{\tt NU} --- inequality constraint having its upper right-hand side
1286active (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
1291case 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
1297structural 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
1308variable).
1309
1310\begin{landscape}
1311\begin{scriptsize}
1312\begin{verbatim}
1313GLPK 4.42 - SENSITIVITY ANALYSIS REPORT                                                                         Page   1
1314
1315Problem:    PLAN
1316Objective:  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}
1351GLPK 4.42 - SENSITIVITY ANALYSIS REPORT                                                                         Page   2
1352
1353Problem:    PLAN
1354Objective:  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
1380End 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
1387variable (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
1411The sensitivity analysis of active bounds is performed only for rows,
1412which are active constraints, and only for non-basic columns, because
1413inactive constraints and basic columns have no active bounds.
1414
1415For every auxiliary (row) or structural (column) non-basic variable the
1416routine starts changing its active bound in both direction. The first
1417of the two lines in the report corresponds to decreasing, and the
1418second line corresponds to increasing of the active bound. Since the
1419variable being analyzed is non-basic, its activity, which is equal to
1420its active bound, also starts changing. This changing leads to changing
1421of basic (auxiliary and structural) variables, which depend on the
1422non-basic variable. The current basis remains primal feasible and
1423therefore optimal while values of all basic variables are primal
1424feasible, i.e. are within their bounds. Therefore, if some basic
1425variable called the {\it limiting variable} reaches its (lower or
1426upper) bound first, before any other basic variables, it thereby limits
1427further changing of the non-basic variable, because otherwise the
1428current basis would become primal infeasible. The point, at which this
1429happens, is called the {\it break point}. Note that there are two break
1430points: the lower break point, which corresponds to decreasing of the
1431non-basic variable, and the upper break point, which corresponds to
1432increasing of the non-basic variable.
1433
1434In the analysis report values of the non-basic variable (i.e. of its
1435active bound) being analyzed at both lower and upper break points are
1436printed in the field `{\tt Activity range}'. Corresponding values of
1437the objective function are printed in the field `{\tt Obj value at
1438break point}', and symbolic names of corresponding limiting basic
1439variables are printed in the field `{\tt Limiting variable}'.
1440If the active bound can decrease or/and increase unlimitedly, the field
1441`{\tt Activity range}' contains {\tt -Inf} or/and {\tt +Inf}, resp.
1442
1443For example (see the example report above), row SI is a double-sided
1444constraint, which is active on its lower bound (right-hand side), and
1445its activity in the optimal solution being equal to the lower bound is
1446250. The activity range for this row is $[235.32871,255.06073]$. This
1447means that the basis remains optimal while the lower bound is
1448increasing up to 255.06073, and further increasing is limited by
1449(structural) variable BIN3. If the lower bound reaches this upper break
1450point, the objective value becomes equal to 298.67206.
1451
1452Note that if the basis does not change, the objective function depends
1453on the non-basic variable linearly, and the per-unit change of the
1454objective function is the reduced cost (marginal value) of the
1455non-basic variable.
1456
1457\bigskip
1458
1459\noindent
1460{\it Sensitivity analysis of objective coefficients at non-basic
1461variables}
1462
1463\medskip
1464
1465\noindent
1466The sensitivity analysis of the objective coefficient at a non-basic
1467variable is quite simple, because in this case change in the objective
1468coefficient leads to equivalent change in the reduced cost (marginal
1469value).
1470
1471For every auxiliary (row) or structural (column) non-basic variable the
1472routine starts changing its objective coefficient in both direction.
1473(Note that auxiliary variables are not included in the objective
1474function and therefore always have zero objective coefficients.) The
1475first of the two lines in the report corresponds to decreasing, and the
1476second line corresponds to increasing of the objective coefficient.
1477This changing leads to changing of the reduced cost of the non-basic
1478variable to be analyzed and does affect reduced costs of all other
1479non-basic variables. The current basis remains dual feasible and
1480therefore optimal while the reduced cost keeps its sign. Therefore, if
1481the reduced cost reaches zero, it limits further changing of the
1482objective coefficient (if only the non-basic variable is non-fixed).
1483
1484In the analysis report minimal and maximal values of the objective
1485coefficient, on which the basis remains optimal, are printed in the
1486field `\verb|Obj coef range|'. If the objective coefficient can
1487decrease or/and increase unlimitedly, this field contains {\tt -Inf}
1488or/and {\tt +Inf}, resp.
1489
1490For example (see the example report above), column BIN5 is non-basic
1491having its lower bound active. Its objective coefficient is 0.15, and
1492reduced cost in the optimal solution 0.01456. The column lower bound
1493remains active while the column reduced cost remains non-negative,
1494thus, minimal value of the objective coefficient, on which the current
1495basis still remains optimal, is $0.15-0.01456=0.13644$, that is
1496indicated 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
1506To perform sensitivity analysis for every auxiliary (row) or structural
1507(column) variable the routine starts changing its objective coefficient
1508in both direction. (Note that auxiliary variables are not included in
1509the objective function and therefore always have zero objective
1510coefficients.) The first of the two lines in the report corresponds to
1511decreasing, and the second line corresponds to increasing of the
1512objective coefficient. This changing leads to changing of reduced costs
1513of non-basic variables. The current basis remains dual feasible and
1514therefore optimal while reduced costs of all non-basic variables
1515(except fixed variables) keep their signs. Therefore, if the reduced
1516cost of some non-basic non-fixed variable called the {\it limiting
1517variable} reaches zero first, before reduced cost of any other
1518non-basic non-fixed variable, it thereby limits further changing of the
1519objective coefficient, because otherwise the current basis would become
1520dual infeasible (non-optimal). The point, at which this happens, is
1521called the {\it break point}. Note that there are two break points: the
1522lower break point, which corresponds to decreasing of the objective
1523coefficient, and the upper break point, which corresponds to increasing
1524of the objective coefficient. Let the objective coefficient reach its
1525limit value and continue changing a bit further in the same direction
1526that makes the current basis dual infeasible (non-optimal). Then the
1527reduced cost of the non-basic limiting variable becomes ``a bit'' dual
1528infeasible that forces the limiting variable to enter the basis
1529replacing there some basic variable, which leaves the basis to keep its
1530primal feasibility. It should be understood that if we change the
1531current basis in this way exactly at the break point, both the current
1532and adjacent bases will be optimal with the same objective value,
1533because at the break point the limiting variable has zero reduced cost.
1534On the other hand, in the adjacent basis the value of the limiting
1535variable changes, because there it becomes basic, that leads to
1536changing of the value of the basic variable being analyzed. Note that
1537on determining the adjacent basis the bounds of the analyzed basic
1538variable are ignored as if it were a free (unbounded) variable, so it
1539cannot leave the current basis.
1540
1541In the analysis report lower and upper limits of the objective
1542coefficient at the basic variable being analyzed, when the basis
1543remains optimal, are printed in the field `{\tt Obj coef range}'.
1544Corresponding values of the objective function at both lower and upper
1545break points are printed in the field `{\tt Obj value at break point}',
1546symbolic names of corresponding non-basic limiting variables are
1547printed in the field `{\tt Limiting variable}', and values of the basic
1548variable, which it would take on in the adjacent bases (as was
1549explained above) are printed in the field `{\tt Activity range}'.
1550If the objective coefficient can increase or/and decrease unlimitedly,
1551the field `{\tt Obj coef range}' contains {\tt -Inf} and/or {\tt +Inf},
1552resp. It also may happen that no dual feasible adjacent basis exists
1553(i.e. on entering the basis the limiting variable can increase or
1554decrease unlimitedly), in which case the field `{\tt Activity range}'
1555contains {\tt -Inf} and/or {\tt +Inf}.
1556
1557\newpage
1558
1559For example (see the example report above), structural variable
1560(column) BIN3 is basic, its optimal value is 490.25271, and its
1561objective coefficient is 0.17. The objective coefficient range for this
1562column is $[0.15982,0.17948]$. This means that the basis remains
1563optimal while the objective coefficient is decreasing down to 0.15982,
1564and further decreasing is limited by (auxiliary) variable MN. If we
1565make the objective coefficient a bit less than 0.15982, the limiting
1566variable MN will enter the basis, and in that adjacent basis the
1567structural variable BIN3 will take on new optimal value 788.61314. At
1568the lower break point, where the objective coefficient is exactly
15690.15982, the objective function takes on the value 291.22807 in both
1570the current and adjacent bases.
1571
1572Note that if the basis does not change, the objective function depends
1573on the objective coefficient at the basic variable linearly, and the
1574per-unit change of the objective function is the value of the basic
1575variable.
1576
1577%* eof *%
Note: See TracBrowser for help on using the repository browser.