
diff -r d59bea55db9b -r c445c931472f doc/glpk03.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/glpk03.tex	Mon Dec 06 13:09:21 2010 +0100
@@ -0,0 +1,1577 @@
+%* glpk03.tex *%
+
+\chapter{Utility API routines}
+
+\section{Problem data reading/writing routines}
+
+\subsection{glp\_read\_mps---read problem data in MPS format}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_read_mps(glp_prob *lp, int fmt, const void *parm,
+      const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_read_mps| reads problem data in MPS format from a
+text file. (The MPS format is described in Appendix \ref{champs}, page
+\pageref{champs}.)
+
+The parameter \verb|fmt| specifies the MPS format version as follows:
+
+\begin{tabular}{@{}ll}
+\verb|GLP_MPS_DECK| & fixed (ancient) MPS format; \\
+\verb|GLP_MPS_FILE| & free (modern) MPS format. \\
+\end{tabular}
+
+The parameter \verb|parm| is reserved for use in the future and must be
+specified as \verb|NULL|.
+
+The character string \verb|fname| specifies a name of the text file to
+be read in. (If the file name ends with suffix `\verb|.gz|', the file is
+assumed to be compressed, in which case the routine \verb|glp_read_mps|
+decompresses it ``on the fly''.)
+
+Note that before reading data the current content of the problem object
+is completely erased with the routine \verb|glp_erase_prob|.
+
+\subsubsection*{Returns}
+
+If the operation was successful, the routine \verb|glp_read_mps|
+returns zero. Otherwise, it prints an error message and returns
+non-zero.
+
+\subsection{glp\_write\_mps---write problem data in MPS format}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_write_mps(glp_prob *lp, int fmt, const void *parm,
+      const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_write_mps| writes problem data in MPS format to a
+text file. (The MPS format is described in Appendix \ref{champs}, page
+\pageref{champs}.)
+
+The parameter \verb|fmt| specifies the MPS format version as follows:
+
+\begin{tabular}{@{}ll}
+\verb|GLP_MPS_DECK| & fixed (ancient) MPS format; \\
+\verb|GLP_MPS_FILE| & free (modern) MPS format. \\
+\end{tabular}
+
+The parameter \verb|parm| is reserved for use in the future and must be
+specified as \verb|NULL|.
+
+The character string \verb|fname| specifies a name of the text file to
+be written out. (If the file name ends with suffix `\verb|.gz|', the
+file is assumed to be compressed, in which case the routine
+\verb|glp_write_mps| performs automatic compression on writing it.)
+
+\subsubsection*{Returns}
+
+If the operation was successful, the routine \verb|glp_write_mps|
+returns zero. Otherwise, it prints an error message and returns
+non-zero.
+
+\subsection{glp\_read\_lp---read problem data in CPLEX LP format}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_read_lp(glp_prob *lp, const void *parm,
+      const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_read_lp| reads problem data in CPLEX LP format
+from a text file. (The CPLEX LP format is described in Appendix
+\ref{chacplex}, page \pageref{chacplex}.)
+
+The parameter \verb|parm| is reserved for use in the future and must be
+specified as \verb|NULL|.
+
+The character string \verb|fname| specifies a name of the text file to
+be read in. (If the file name ends with suffix `\verb|.gz|', the file is
+assumed to be compressed, in which case the routine \verb|glp_read_lp|
+decompresses it ``on the fly''.)
+
+Note that before reading data the current content of the problem object
+is completely erased with the routine \verb|glp_erase_prob|.
+
+\subsubsection*{Returns}
+
+If the operation was successful, the routine \verb|glp_read_lp| returns
+zero. Otherwise, it prints an error message and returns non-zero.
+
+\subsection{glp\_write\_lp---write problem data in CPLEX LP format}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_write_lp(glp_prob *lp, const void *parm,
+      const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_write_lp| writes problem data in CPLEX LP format
+to a text file. (The CPLEX LP format is described in Appendix
+\ref{chacplex}, page \pageref{chacplex}.)
+
+The parameter \verb|parm| is reserved for use in the future and must be
+specified as \verb|NULL|.
+
+The character string \verb|fname| specifies a name of the text file to
+be written out. (If the file name ends with suffix `\verb|.gz|', the
+file is assumed to be compressed, in which case the routine
+\verb|glp_write_lp| performs automatic compression on writing it.)
+
+\subsubsection*{Returns}
+
+If the operation was successful, the routine \verb|glp_write_lp|
+returns zero. Otherwise, it prints an error message and returns
+non-zero.
+
+\subsection{glp\_read\_prob---read problem data in GLPK format}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_read_prob(glp_prob *P, int flags, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_read_prob| reads problem data in the GLPK LP/MIP
+format from a text file. (For description of the GLPK LP/MIP format see
+below.)
+
+The parameter \verb|flags| is reserved for use in the future and should
+be specified as zero.
+
+The character string \verb|fname| specifies a name of the text file to
+be read in. (If the file name ends with suffix `\verb|.gz|', the file
+is assumed to be compressed, in which case the routine
+\verb|glp_read_prob| decompresses it ``on the fly''.)
+
+Note that before reading data the current content of the problem object
+is completely erased with the routine \verb|glp_erase_prob|.
+
+\subsubsection*{Returns}
+
+If the operation was successful, the routine \verb|glp_read_prob|
+returns zero. Otherwise, it prints an error message and returns
+non-zero.
+
+\subsubsection*{GLPK LP/MIP format}
+
+The GLPK LP/MIP format is a DIMACS-like format.\footnote{The DIMACS
+formats were developed by the Center for Discrete Mathematics and
+Theoretical Computer Science (DIMACS) to facilitate exchange of problem
+data. For details see: {\tt <http://dimacs.rutgers.edu/Challenges/>}. }
+The file in this format is a plain ASCII text file containing lines of
+several types described below. A line is terminated with the end-of-line
+character. Fields in each line are separated by at least one blank
+space. Each line begins with a one-character designator to identify the
+line type.
+
+The first line of the data file must be the problem line (except
+optional comment lines, which may precede the problem line). The last
+line of the data file must be the end line. Other lines may follow in
+arbitrary order, however, duplicate lines are not allowed.
+
+\paragraph{Comment lines.} Comment lines give human-readable
+information about the data file and are ignored by GLPK routines.
+Comment lines can appear anywhere in the data file. Each comment line
+begins with the lower-case character \verb|c|.
+
+\begin{verbatim}
+   c This is an example of comment line
+\end{verbatim}
+
+\paragraph{Problem line.} There must be exactly one problem line in the
+data file. This line must appear before any other lines except comment
+lines and has the following format:
+
+\begin{verbatim}
+   p CLASS DIR ROWS COLS NONZ
+\end{verbatim}
+
+The lower-case letter \verb|p| specifies that this is the problem line.
+
+The \verb|CLASS| field defines the problem class and can contain either
+the keyword \verb|lp| (that means linear programming problem) or
+\verb|mip| (that means mixed integer programming problem).
+
+The \verb|DIR| field defines the optimization direction (that is, the
+objective function sense) and can contain either the keyword \verb|min|
+(that means minimization) or \verb|max| (that means maximization).
+
+The \verb|ROWS|, \verb|COLS|, and \verb|NONZ| fields contain
+non-negative integer values specifying, respectively, the number of
+rows (constraints), columns (variables), and non-zero constraint
+coefficients in the problem instance. Note that \verb|NONZ| value does
+not account objective coefficients.
+
+\paragraph{Row descriptors.} There must be at most one row descriptor
+line in the data file for each row (constraint). This line has one of
+the following formats:
+
+\begin{verbatim}
+   i ROW f
+   i ROW l RHS
+   i ROW u RHS
+   i ROW d RHS1 RHS2
+   i ROW s RHS
+\end{verbatim}
+
+The lower-case letter \verb|i| specifies that this is the row
+descriptor line.
+
+The \verb|ROW| field specifies the row ordinal number, an integer
+between 1 and $m$, where $m$ is the number of rows in the problem
+instance.
+
+The next lower-case letter specifies the row type as follows:
+
+\verb|f| --- free (unbounded) row: $-\infty<\sum a_jx_j<+\infty$;
+
+\verb|l| --- inequality constraint of `$\geq$' type:
+$\sum a_jx_j\geq b$;
+
+\verb|u| --- inequality constraint of `$\leq$' type:
+$\sum a_jx_j\leq b$;
+
+\verb|d| --- double-sided inequality constraint:
+$b_1\leq\sum a_jx_j\leq b_2$;
+
+\verb|s| --- equality constraint: $\sum a_jx_j=b$.
+
+The \verb|RHS| field contains a floaing-point value specifying the
+row right-hand side. The \verb|RHS1| and \verb|RHS2| fields contain
+floating-point values specifying, respectively, the lower and upper
+right-hand sides for the double-sided row.
+
+If for some row its descriptor line does not appear in the data file,
+by default that row is assumed to be an equality constraint with zero
+right-hand side.
+
+\paragraph{Column descriptors.} There must be at most one column
+descriptor line in the data file for each column (variable). This line
+has one of the following formats depending on the problem class
+specified in the problem line:
+
+\bigskip
+
+\begin{tabular}{@{}l@{\hspace*{40pt}}l}
+LP class & MIP class \\
+\hline
+\verb|j COL f|           & \verb|j COL KIND f|           \\
+\verb|j COL l BND|       & \verb|j COL KIND l BND|       \\
+\verb|j COL u BND|       & \verb|j COL KIND u BND|       \\
+\verb|j COL d BND1 BND2| & \verb|j COL KIND d BND1 BND2| \\
+\verb|j COL s BND|       & \verb|j COL KIND s BND|       \\
+\end{tabular}
+
+\bigskip
+
+The lower-case letter \verb|j| specifies that this is the column
+descriptor line.
+
+The \verb|COL| field specifies the column ordinal number, an integer
+between 1 and $n$, where $n$ is the number of columns in the problem
+instance.
+
+The \verb|KIND| field is used only for MIP problems and specifies the
+column kind as follows:
+
+\verb|c| --- continuous column;
+
+\verb|i| --- integer column;
+
+\verb|b| --- binary column (in this case all remaining fields must be
+omitted).
+
+The next lower-case letter specifies the column type as follows:
+
+\verb|f| --- free (unbounded) column: $-\infty<x<+\infty$;
+
+\verb|l| --- column with lower bound: $x\geq l$;
+
+\verb|u| --- column with upper bound: $x\leq u$;
+
+\verb|d| --- double-bounded column: $l\leq x\leq u$;
+
+\verb|s| --- fixed column: $x=s$.
+
+The \verb|BND| field contains a floating-point value that specifies the
+column bound. The \verb|BND1| and \verb|BND2| fields contain
+floating-point values specifying, respectively, the lower and upper
+bounds for the double-bounded column.
+
+If for some column its descriptor line does not appear in the file, by
+default that column is assumed to be non-negative (in case of LP class)
+or binary (in case of MIP class).
+
+\paragraph{Coefficient descriptors.} There must be exactly one
+coefficient descriptor line in the data file for each non-zero
+objective or constraint coefficient. This line has the following format:
+
+\begin{verbatim}
+   a ROW COL VAL
+\end{verbatim}
+
+The lower-case letter \verb|a| specifies that this is the coefficient
+descriptor line.
+
+For objective coefficients the \verb|ROW| field must contain 0. For
+constraint coefficients the \verb|ROW| field specifies the row ordinal
+number, an integer between 1 and $m$, where $m$ is the number of rows
+in the problem instance.
+
+The \verb|COL| field specifies the column ordinal number, an integer
+between 1 and $n$, where $n$ is the number of columns in the problem
+instance.
+
+If both the \verb|ROW| and \verb|COL| fields contain 0, the line
+specifies the constant term (``shift'') of the objective function
+rather than objective coefficient.
+
+The \verb|VAL| field contains a floating-point coefficient value (it is
+allowed to specify zero value in this field).
+
+The number of constraint coefficient descriptor lines must be exactly
+the same as specified in the field \verb|NONZ| of the problem line.
+
+\paragraph{Symbolic name descriptors.} There must be at most one
+symbolic name descriptor line for the problem instance, objective
+function, each row (constraint), and each column (variable). This line
+has one of the following formats:
+
+\begin{verbatim}
+   n p NAME
+   n z NAME
+   n i ROW NAME
+   n j COL NAME
+\end{verbatim}
+
+The lower-case letter \verb|n| specifies that this is the symbolic name
+descriptor line.
+
+The next lower-case letter specifies which object should be assigned a
+symbolic name:
+
+\verb|p| --- problem instance;
+
+\verb|z| --- objective function;
+
+\verb|i| --- row (constraint);
+
+\verb|j| --- column (variable).
+
+The \verb|ROW| field specifies the row ordinal number, an integer
+between 1 and $m$, where $m$ is the number of rows in the problem
+instance.
+
+The \verb|COL| field specifies the column ordinal number, an integer
+between 1 and $n$, where $n$ is the number of columns in the problem
+instance.
+
+The \verb|NAME| field contains the symbolic name, a sequence from 1 to
+255 arbitrary graphic ASCII characters, assigned to corresponding
+object.
+
+\paragraph{End line.} There must be exactly one end line in the data
+file. This line must appear last in the file and has the following
+format:
+
+\begin{verbatim}
+   e
+\end{verbatim}
+
+The lower-case letter \verb|e| specifies that this is the end line.
+Anything that follows the end line is ignored by GLPK routines.
+
+\subsubsection*{Example of data file in GLPK LP/MIP format}
+
+The following example of a data file in GLPK LP/MIP format specifies
+the same LP problem as in Subsection ``Example of MPS file''.
+
+\begin{center}
+\footnotesize\tt
+\begin{tabular}{l@{\hspace*{50pt}}}
+p lp min 8 7 48   \\
+n p PLAN          \\
+n z VALUE         \\
+i 1 f             \\
+n i 1 VALUE       \\
+i 2 s 2000        \\
+n i 2 YIELD       \\
+i 3 u 60          \\
+n i 3 FE          \\
+i 4 u 100         \\
+n i 4 CU          \\
+i 5 u 40          \\
+n i 5 MN          \\
+i 6 u 30          \\
+n i 6 MG          \\
+i 7 l 1500        \\
+n i 7 AL          \\
+i 8 d 250 300     \\
+n i 8 SI          \\
+j 1 d 0 200       \\
+n j 1 BIN1        \\
+j 2 d 0 2500      \\
+n j 2 BIN2        \\
+j 3 d 400 800     \\
+n j 3 BIN3        \\
+j 4 d 100 700     \\
+n j 4 BIN4        \\
+j 5 d 0 1500      \\
+n j 5 BIN5        \\
+n j 6 ALUM        \\
+n j 7 SILICON     \\
+a 0 1 0.03        \\
+a 0 2 0.08        \\
+a 0 3 0.17        \\
+a 0 4 0.12        \\
+a 0 5 0.15        \\
+a 0 6 0.21        \\
+a 0 7 0.38        \\
+a 1 1 0.03        \\
+a 1 2 0.08        \\
+a 1 3 0.17        \\
+a 1 4 0.12        \\
+a 1 5 0.15        \\
+a 1 6 0.21        \\
+\end{tabular}
+\begin{tabular}{|@{\hspace*{80pt}}l}
+a 1 7 0.38        \\
+a 2 1 1           \\
+a 2 2 1           \\
+a 2 3 1           \\
+a 2 4 1           \\
+a 2 5 1           \\
+a 2 6 1           \\
+a 2 7 1           \\
+a 3 1 0.15        \\
+a 3 2 0.04        \\
+a 3 3 0.02        \\
+a 3 4 0.04        \\
+a 3 5 0.02        \\
+a 3 6 0.01        \\
+a 3 7 0.03        \\
+a 4 1 0.03        \\
+a 4 2 0.05        \\
+a 4 3 0.08        \\
+a 4 4 0.02        \\
+a 4 5 0.06        \\
+a 4 6 0.01        \\
+a 5 1 0.02        \\
+a 5 2 0.04        \\
+a 5 3 0.01        \\
+a 5 4 0.02        \\
+a 5 5 0.02        \\
+a 6 1 0.02        \\
+a 6 2 0.03        \\
+a 6 5 0.01        \\
+a 7 1 0.7         \\
+a 7 2 0.75        \\
+a 7 3 0.8         \\
+a 7 4 0.75        \\
+a 7 5 0.8         \\
+a 7 6 0.97        \\
+a 8 1 0.02        \\
+a 8 2 0.06        \\
+a 8 3 0.08        \\
+a 8 4 0.12        \\
+a 8 5 0.02        \\
+a 8 6 0.01        \\
+a 8 7 0.97        \\
+e o f             \\
+\\
+\end{tabular}
+\end{center}
+
+\newpage
+
+\subsection{glp\_write\_prob---write problem data in GLPK format}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_write_prob(glp_prob *P, int flags, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_write_prob| writes problem data in the GLPK
+LP/MIP format to a text file. (For description of the GLPK LP/MIP
+format see Subsection ``Read problem data in GLPK format''.)
+
+The parameter \verb|flags| is reserved for use in the future and should
+be specified as zero.
+
+The character string \verb|fname| specifies a name of the text file to
+be written out. (If the file name ends with suffix `\verb|.gz|', the
+file is assumed to be compressed, in which case the routine
+\verb|glp_write_prob| performs automatic compression on writing it.)
+
+\subsubsection*{Returns}
+
+If the operation was successful, the routine \verb|glp_read_prob|
+returns zero. Otherwise, it prints an error message and returns
+non-zero.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\newpage
+
+\section{Routines for processing MathProg models}
+
+\subsection{Introduction}
+
+GLPK supports the {\it GNU MathProg modeling language}.\footnote{The
+GNU MathProg modeling language is a subset of the AMPL language. For
+its detailed description see the document ``Modeling Language GNU
+MathProg: Language Reference'' included in the GLPK distribution.}
+As a rule, models written in MathProg are solved with the GLPK LP/MIP
+stand-alone solver \verb|glpsol| (see Appendix D) and do not need any
+programming with API routines. However, for various reasons the user
+may need to process MathProg models directly in his/her application
+program, in which case he/she may use API routines described in this
+section. These routines provide an interface to the {\it MathProg
+translator}, a component of GLPK, which translates MathProg models into
+an internal code and then interprets (executes) this code.
+
+The processing of a model written in GNU MathProg includes several
+steps, which should be performed in the following order:
+
+\begin{enumerate}
+\item{\it Allocating the workspace.}
+The translator allocates the workspace, an internal data structure used
+on all subsequent steps.
+\item{\it Reading model section.} The translator reads model section
+and, optionally, data section from a specified text file and translates
+them into the internal code. If necessary, on this step data section
+may be ignored.
+\item{\it Reading data section(s).} The translator reads one or more
+data sections from specified text file(s) and translates them into the
+internal code.
+\item{\it Generating the model.} The translator executes the internal
+code to evaluate the content of the model objects such as sets,
+parameters, variables, constraints, and objectives. On this step the
+execution is suspended at the solve statement.
+\item {\it Building the problem object.} The translator obtains all
+necessary information from the workspace and builds the standard
+problem object (that is, the program object of type \verb|glp_prob|).
+\item{\it Solving the problem.} On this step the problem object built
+on the previous step is passed to a solver, which solves the problem
+instance and stores its solution back to the problem object.
+\item{\it Postsolving the model.} The translator copies the solution
+from the problem object to the workspace and then executes the internal
+code from the solve statement to the end of the model. (If model has
+no solve statement, the translator does nothing on this step.)
+\item{\it Freeing the workspace.} The translator frees all the memory
+allocated to the workspace.
+\end{enumerate}
+
+Note that the MathProg translator performs no error correction, so if
+any of steps 2 to 7 fails (due to errors in the model), the application
+program should terminate processing and go to step 8.
+
+\subsubsection*{Example 1}
+
+In this example the program reads model and data sections from input
+file \verb|egypt.mod|\footnote{This is an example model included in
+the GLPK distribution.} and writes the model to output file
+\verb|egypt.mps| in free MPS format (see Appendix B). No solution is
+performed.
+
+\begin{small}
+\begin{verbatim}
+/* mplsamp1.c */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <glpk.h>
+
+int main(void)
+{     glp_prob *lp;
+      glp_tran *tran;
+      int ret;
+      lp = glp_create_prob();
+      tran = glp_mpl_alloc_wksp();
+      ret = glp_mpl_read_model(tran, "egypt.mod", 0);
+      if (ret != 0)
+      {  fprintf(stderr, "Error on translating model\n");
+         goto skip;
+      }
+      ret = glp_mpl_generate(tran, NULL);
+      if (ret != 0)
+      {  fprintf(stderr, "Error on generating model\n");
+         goto skip;
+      }
+      glp_mpl_build_prob(tran, lp);
+      ret = glp_write_mps(lp, GLP_MPS_FILE, NULL, "egypt.mps");
+      if (ret != 0)
+         fprintf(stderr, "Error on writing MPS file\n");
+skip: glp_mpl_free_wksp(tran);
+      glp_delete_prob(lp);
+      return 0;
+}
+
+/* eof */
+\end{verbatim}
+\end{small}
+
+\subsubsection*{Example 2}
+
+In this example the program reads model section from file
+\verb|sudoku.mod|\footnote{This is an example model which is included
+in the GLPK distribution along with alternative data file
+{\tt sudoku.dat}.} ignoring data section in this file, reads alternative
+data section from file \verb|sudoku.dat|, solves the problem instance
+and passes the solution found back to the model.
+
+\begin{small}
+\begin{verbatim}
+/* mplsamp2.c */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <glpk.h>
+
+int main(void)
+{     glp_prob *mip;
+      glp_tran *tran;
+      int ret;
+      mip = glp_create_prob();
+      tran = glp_mpl_alloc_wksp();
+      ret = glp_mpl_read_model(tran, "sudoku.mod", 1);
+      if (ret != 0)
+      {  fprintf(stderr, "Error on translating model\n");
+         goto skip;
+      }
+      ret = glp_mpl_read_data(tran, "sudoku.dat");
+      if (ret != 0)
+      {  fprintf(stderr, "Error on translating data\n");
+         goto skip;
+      }
+      ret = glp_mpl_generate(tran, NULL);
+      if (ret != 0)
+      {  fprintf(stderr, "Error on generating model\n");
+         goto skip;
+      }
+      glp_mpl_build_prob(tran, mip);
+      glp_simplex(mip, NULL);
+      glp_intopt(mip, NULL);
+      ret = glp_mpl_postsolve(tran, mip, GLP_MIP);
+      if (ret != 0)
+         fprintf(stderr, "Error on postsolving model\n");
+skip: glp_mpl_free_wksp(tran);
+      glp_delete_prob(mip);
+      return 0;
+}
+
+/* eof */
+\end{verbatim}
+\end{small}
+
+\subsection{glp\_mpl\_alloc\_wksp---allocate the translator workspace}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+glp_tran *glp_mpl_alloc_wksp(void);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_mpl_alloc_wksp| allocates the MathProg translator
+work\-space. (Note that multiple instances of the workspace may be
+allocated, if necessary.)
+
+\subsubsection*{Returns}
+
+The routine returns a pointer to the workspace, which should be used in
+all subsequent operations.
+
+\subsection{glp\_mpl\_read\_model---read and translate model section}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_mpl_read_model(glp_tran *tran, const char *fname,
+      int skip);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_mpl_read_model| reads model section and,
+optionally, data section, which may follow the model section, from a
+text file, whose name is the character string \verb|fname|, performs
+translation of model statements and data blocks, and stores all the
+information in the workspace.
+
+The parameter \verb|skip| is a flag. If the input file contains the
+data section and this flag is non-zero, the data section is not read as
+if there were no data section and a warning message is printed. This
+allows reading data section(s) from other file(s).
+
+\subsubsection*{Returns}
+
+If the operation is successful, the routine returns zero. Otherwise
+the routine prints an error message and returns non-zero.
+
+\subsection{glp\_mpl\_read\_data---read and translate data section}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_mpl_read_data(glp_tran *tran, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_mpl_read_data| reads data section from a text
+file, whose name is the character string \verb|fname|, performs
+translation of data blocks, and stores the data read in the translator
+workspace. If necessary, this routine may be called more than once.
+
+\subsubsection*{Returns}
+
+If the operation is successful, the routine returns zero. Otherwise
+the routine prints an error message and returns non-zero.
+
+\subsection{glp\_mpl\_generate---generate the model}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_mpl_generate(glp_tran *tran, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_mpl_generate| generates the model using its
+description stored in the translator workspace. This operation means
+generating all variables, constraints, and objectives, executing check
+and display statements, which precede the solve statement (if it is
+presented).
+
+The character string \verb|fname| specifies the name of an output text
+file, to which output produced by display statements should be written.
+If \verb|fname| is \verb|NULL|, the output is sent to the terminal.
+
+\subsubsection*{Returns}
+
+If the operation is successful, the routine returns zero. Otherwise
+the routine prints an error message and returns non-zero.
+
+\subsection{glp\_mpl\_build\_prob---build problem instance from the
+model}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+void glp_mpl_build_prob(glp_tran *tran, glp_prob *prob);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_mpl_build_prob| obtains all necessary information
+from the translator workspace and stores it in the specified problem
+object \verb|prob|. Note that before building the current content of
+the problem object is erased with the routine \verb|glp_erase_prob|.
+
+\subsection{glp\_mpl\_postsolve---postsolve the model}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_mpl_postsolve(glp_tran *tran, glp_prob *prob,
+      int sol);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_mpl_postsolve| copies the solution from the
+specified problem object \verb|prob| to the translator workspace and
+then executes all the remaining model statements, which follow the
+solve statement.
+
+The parameter \verb|sol| specifies which solution should be copied
+from the problem object to the workspace as follows:
+
+\begin{tabular}{@{}ll}
+\verb|GLP_SOL| & basic solution; \\
+\verb|GLP_IPT| & interior-point solution; \\
+\verb|GLP_MIP| & mixed integer solution. \\
+\end{tabular}
+
+\subsubsection*{Returns}
+
+If the operation is successful, the routine returns zero. Otherwise
+the routine prints an error message and returns non-zero.
+
+\subsection{glp\_mpl\_free\_wksp---free the translator workspace}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+void glp_mpl_free_wksp(glp_tran *tran);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_mpl_free_wksp| frees all the memory allocated to
+the translator workspace. It also frees all other resources, which are
+still used by the translator.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\newpage
+
+\section{Problem solution reading/writing routines}
+
+\subsection{glp\_print\_sol---write basic solution in printable format}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_print_sol(glp_prob *lp, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_print_sol writes| the current basic solution of
+an LP problem, which is specified by the pointer \verb|lp|, to a text
+file, whose name is the character string \verb|fname|, in printable
+format.
+
+Information reported by the routine \verb|glp_print_sol| is intended
+mainly for visual analysis.
+
+\subsubsection*{Returns}
+
+If no errors occurred, the routine returns zero. Otherwise the routine
+prints an error message and returns non-zero.
+
+\subsection{glp\_read\_sol---read basic solution from text file}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_read_sol(glp_prob *lp, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_read_sol| reads basic solution from a text file
+whose name is specified by the parameter \verb|fname| into the problem
+object.
+
+For the file format see description of the routine \verb|glp_write_sol|.
+
+\subsubsection*{Returns}
+
+On success the routine returns zero, otherwise non-zero.
+
+\newpage
+
+\subsection{glp\_write\_sol---write basic solution to text file}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_write_sol(glp_prob *lp, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_write_sol| writes the current basic solution to a
+text file whose name is specified by the parameter \verb|fname|. This
+file can be read back with the routine \verb|glp_read_sol|.
+
+\subsubsection*{Returns}
+
+On success the routine returns zero, otherwise non-zero.
+
+\subsubsection*{File format}
+
+The file created by the routine \verb|glp_write_sol| is a plain text
+file, which contains the following information:
+
+\begin{verbatim}
+   m n
+   p_stat d_stat obj_val
+   r_stat[1] r_prim[1] r_dual[1]
+   . . .
+   r_stat[m] r_prim[m] r_dual[m]
+   c_stat[1] c_prim[1] c_dual[1]
+   . . .
+   c_stat[n] c_prim[n] c_dual[n]
+\end{verbatim}
+
+\noindent
+where:
+
+\noindent
+$m$ is the number of rows (auxiliary variables);
+
+\noindent
+$n$ is the number of columns (structural variables);
+
+\noindent
+\verb|p_stat| is the primal status of the basic solution
+(\verb|GLP_UNDEF| = 1, \verb|GLP_FEAS| = 2, \verb|GLP_INFEAS| = 3, or
+\verb|GLP_NOFEAS| = 4);
+
+\noindent
+\verb|d_stat| is the dual status of the basic solution
+(\verb|GLP_UNDEF| = 1, \verb|GLP_FEAS| = 2, \verb|GLP_INFEAS| = 3, or
+\verb|GLP_NOFEAS| = 4);
+
+\noindent
+\verb|obj_val| is the objective value;
+
+\noindent
+\verb|r_stat[i]|, $i=1,\dots,m$, is the status of $i$-th row
+(\verb|GLP_BS| = 1, \verb|GLP_NL| = 2, \verb|GLP_NU| = 3,
+\verb|GLP_NF| = 4, or \verb|GLP_NS| = 5);
+
+\noindent
+\verb|r_prim[i]|, $i=1,\dots,m$, is the primal value of $i$-th row;
+
+\noindent
+\verb|r_dual[i]|, $i=1,\dots,m$, is the dual value of $i$-th row;
+
+\noindent
+\verb|c_stat[j]|, $j=1,\dots,n$, is the status of $j$-th column
+(\verb|GLP_BS| = 1, \verb|GLP_NL| = 2, \verb|GLP_NU| = 3,
+\verb|GLP_NF| = 4, or \verb|GLP_NS| = 5);
+
+\noindent
+\verb|c_prim[j]|, $j=1,\dots,n$, is the primal value of $j$-th column;
+
+\noindent
+\verb|c_dual[j]|, $j=1,\dots,n$, is the dual value of $j$-th column.
+
+\subsection{glp\_print\_ipt---write interior-point solution in
+printable format}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_print_ipt(glp_prob *lp, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_print_ipt| writes the current interior point
+solution  of an LP problem, which the parameter \verb|lp| points to, to
+a text file, whose name is the character string \verb|fname|, in
+printable format.
+
+Information reported by the routine \verb|glp_print_ipt| is intended
+mainly for visual analysis.
+
+\subsubsection*{Returns}
+
+If no errors occurred, the routine returns zero. Otherwise the routine
+prints an error message and returns non-zero.
+
+\subsection{glp\_read\_ipt---read interior-point solution from text
+file}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_read_ipt(glp_prob *lp, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_read_ipt| reads interior-point solution from a
+text file whose name is specified by the parameter \verb|fname| into the
+problem object.
+
+For the file format see description of the routine \verb|glp_write_ipt|.
+
+\subsubsection*{Returns}
+
+On success the routine returns zero, otherwise non-zero.
+
+\subsection{glp\_write\_ipt---write interior-point solution to text
+file}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_write_ipt(glp_prob *lp, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_write_ipt| writes the current interior-point
+solution to a text file whose name is specified by the parameter
+\verb|fname|. This file can be read back with the routine
+\verb|glp_read_ipt|.
+
+\subsubsection*{Returns}
+
+On success the routine returns zero, otherwise non-zero.
+
+\subsubsection*{File format}
+
+The file created by the routine \verb|glp_write_ipt| is a plain text
+file, which contains the following information:
+
+\begin{verbatim}
+   m n
+   stat obj_val
+   r_prim[1] r_dual[1]
+   . . .
+   r_prim[m] r_dual[m]
+   c_prim[1] c_dual[1]
+   . . .
+   c_prim[n] c_dual[n]
+\end{verbatim}
+
+\noindent
+where:
+
+\noindent
+$m$ is the number of rows (auxiliary variables);
+
+\noindent
+$n$ is the number of columns (structural variables);
+
+\noindent
+\verb|stat| is the solution status (\verb|GLP_UNDEF| = 1 or
+\verb|GLP_OPT| = 5);
+
+\noindent
+\verb|obj_val| is the objective value;
+
+\noindent
+\verb|r_prim[i]|, $i=1,\dots,m$, is the primal value of $i$-th row;
+
+\noindent
+\verb|r_dual[i]|, $i=1,\dots,m$, is the dual value of $i$-th row;
+
+\noindent
+\verb|c_prim[j]|, $j=1,\dots,n$, is the primal value of $j$-th column;
+
+\noindent
+\verb|c_dual[j]|, $j=1,\dots,n$, is the dual value of $j$-th column.
+
+\subsection{glp\_print\_mip---write MIP solution in printable format}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_print_mip(glp_prob *lp, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_print_mip| writes a best known integer solution
+of a MIP problem, which is specified by the pointer \verb|lp|, to a text
+file, whose name is the character string \verb|fname|, in printable
+format.
+
+Information reported by the routine \verb|glp_print_mip| is intended
+mainly for visual analysis.
+
+\subsubsection*{Returns}
+
+If no errors occurred, the routine returns zero. Otherwise the routine
+prints an error message and returns non-zero.
+
+\newpage
+
+\subsection{glp\_read\_mip---read MIP solution from text file}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_read_mip(glp_prob *mip, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_read_mip| reads MIP solution from a text file
+whose name is specified by the parameter \verb|fname| into the problem
+object.
+
+For the file format see description of the routine \verb|glp_write_mip|.
+
+\subsubsection*{Returns}
+
+On success the routine returns zero, otherwise non-zero.
+
+\subsection{glp\_write\_mip---write MIP solution to text file}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_write_mip(glp_prob *mip, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_write_mip| writes the current MIP solution to a
+text file whose name is specified by the parameter \verb|fname|. This
+file can be read back with the routine \verb|glp_read_mip|.
+
+\subsubsection*{Returns}
+
+On success the routine returns zero, otherwise non-zero.
+
+\subsubsection*{File format}
+
+The file created by the routine \verb|glp_write_sol| is a plain text
+file, which contains the following information:
+
+\begin{verbatim}
+   m n
+   stat obj_val
+   r_val[1]
+   . . .
+   r_val[m]
+   c_val[1]
+   . . .
+   c_val[n]
+\end{verbatim}
+
+\noindent
+where:
+
+\noindent
+$m$ is the number of rows (auxiliary variables);
+
+\noindent
+$n$ is the number of columns (structural variables);
+
+\noindent
+\verb|stat| is the solution status (\verb|GLP_UNDEF| = 1,
+\verb|GLP_FEAS| = 2, \verb|GLP_NOFEAS| = 4, or \verb|GLP_OPT| = 5);
+
+\noindent
+\verb|obj_val| is the objective value;
+
+\noindent
+\verb|r_val[i]|, $i=1,\dots,m$, is the value of $i$-th row;
+
+\noindent
+\verb|c_val[j]|, $j=1,\dots,n$, is the value of $j$-th column.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\newpage
+
+\section{Post-optimal analysis routines}
+
+\subsection{glp\_print\_ranges---print sensitivity analysis report}
+
+\subsubsection*{Synopsis}
+
+\begin{verbatim}
+int glp_print_ranges(glp_prob *P, int len, const int list[],
+      int flags, const char *fname);
+\end{verbatim}
+
+\subsubsection*{Description}
+
+The routine \verb|glp_print_ranges| performs sensitivity analysis of
+current optimal basic solution and writes the analysis report in
+human-readable format to a text file, whose name is the character
+string {\it fname}. (Detailed description of the report structure is
+given below.)
+
+The parameter {\it len} specifies the length of the row/column list.
+
+The array {\it list} specifies ordinal number of rows and columns to be
+analyzed. The ordinal numbers should be passed in locations
+{\it list}[1], {\it list}[2], \dots, {\it list}[{\it len}]. Ordinal
+numbers from 1 to $m$ refer to rows, and ordinal numbers from $m+1$ to
+$m+n$ refer to columns, where $m$ and $n$ are, resp., the total number
+of rows and columns in the problem object. Rows and columns appear in
+the analysis report in the same order as they follow in the array list.
+
+It is allowed to specify $len=0$, in which case the array {\it list} is
+not used (so it can be specified as \verb|NULL|), and the routine
+performs analysis for all rows and columns of the problem object.
+
+The parameter {\it flags} is reserved for use in the future and must be
+specified as zero.
+
+On entry to the routine \verb|glp_print_ranges| the current basic
+solution must be optimal and the basis factorization must exist.
+The application program can check that with the routine
+\verb|glp_bf_exists|, and if the factorization does
+not exist, compute it with the routine \verb|glp_factorize|. Note that
+if the LP preprocessor is not used, on normal exit from the simplex
+solver routine \verb|glp_simplex| the basis factorization always exists.
+
+\subsubsection*{Returns}
+
+If the operation was successful, the routine \verb|glp_print_ranges|
+returns zero. Otherwise, it prints an error message and returns
+non-zero.
+
+\subsubsection*{Analysis report example}
+
+An example of the sensitivity analysis report is shown on the next two
+pages. This example corresponds to the example of LP problem described
+in Subsection ``Example of MPS file''.
+
+\subsubsection*{Structure of the analysis report}
+
+For each row and column specified in the array {\it list} the routine
+prints two lines containing generic information and analysis
+information, which depends on the status of corresponding row or column.
+
+Note that analysis of a row is analysis of its auxiliary variable,
+which is equal to the row linear form $\sum a_jx_j$, and analysis of
+a column is analysis of corresponding structural variable. Therefore,
+formally, on performing the sensitivity analysis there is no difference
+between rows and columns.
+
+\bigskip
+
+\noindent
+{\it Generic information}
+
+\medskip
+
+\noindent
+{\tt No.} is the row or column ordinal number in the problem object.
+Rows are numbered from 1 to $m$, and columns are numbered from 1 to $n$,
+where $m$ and $n$ are, resp., the total number of rows and columns in
+the problem object.
+
+\medskip
+
+\noindent
+{\tt Row name} is the symbolic name assigned to the row. If the row has
+no name assigned, this field contains blanks.
+
+\medskip
+
+\noindent
+{\tt Column name} is the symbolic name assigned to the column. If the
+column has no name assigned, this field contains blanks.
+
+\medskip
+
+\noindent
+{\tt St} is the status of the row or column in the optimal solution:
+
+{\tt BS} --- non-active constraint (row), basic column;
+
+{\tt NL} --- inequality constraint having its lower right-hand side
+active (row), non-basic column having its lower bound active;
+
+{\tt NU} --- inequality constraint having its upper right-hand side
+active (row), non-basic column having its upper bound active;
+
+{\tt NS} --- active equality constraint (row), non-basic fixed column.
+
+{\tt NF} --- active free row, non-basic free (unbounded) column. (This
+case means that the optimal solution is dual degenerate.)
+
+\medskip
+
+\noindent
+{\tt Activity} is the (primal) value of the auxiliary variable (row) or
+structural variable (column) in the optimal solution.
+
+\medskip
+
+\noindent
+{\tt Slack} is the (primal) value of the row slack variable.
+
+\medskip
+
+\noindent
+{\tt Obj coef} is the objective coefficient of the column (structural
+variable).
+
+\begin{landscape}
+\begin{scriptsize}
+\begin{verbatim}
+GLPK 4.42 - SENSITIVITY ANALYSIS REPORT                                                                         Page   1
+
+Problem:    PLAN
+Objective:  VALUE = 296.2166065 (MINimum)
+
+   No. Row name     St      Activity         Slack   Lower bound       Activity      Obj coef  Obj value at Limiting
+                                          Marginal   Upper bound          range         range   break point variable
+------ ------------ -- ------------- ------------- -------------  ------------- ------------- ------------- ------------
+     1 VALUE        BS     296.21661    -296.21661          -Inf      299.25255      -1.00000        .      MN
+                                            .               +Inf      296.21661          +Inf          +Inf
+
+     2 YIELD        NS    2000.00000        .         2000.00000     1995.06864          -Inf     296.28365 BIN3
+                                           -.01360    2000.00000     2014.03479          +Inf     296.02579 CU
+
+     3 FE           NU      60.00000        .               -Inf       55.89016          -Inf     306.77162 BIN4
+                                          -2.56823      60.00000       62.69978       2.56823     289.28294 BIN3
+
+     4 CU           BS      83.96751      16.03249          -Inf       93.88467       -.30613     270.51157 MN
+                                            .          100.00000       79.98213        .21474     314.24798 BIN5
+
+     5 MN           NU      40.00000        .               -Inf       34.42336          -Inf     299.25255 BIN4
+                                           -.54440      40.00000       41.68691        .54440     295.29825 BIN3
+
+     6 MG           BS      19.96029      10.03971          -Inf       24.74427      -1.79618     260.36433 BIN1
+                                            .           30.00000        9.40292        .28757     301.95652 MN
+
+     7 AL           NL    1500.00000        .         1500.00000     1485.78425       -.25199     292.63444 CU
+                                            .25199          +Inf     1504.92126          +Inf     297.45669 BIN3
+
+     8 SI           NL     250.00000      50.00000     250.00000      235.32871       -.48520     289.09812 CU
+                                            .48520     300.00000      255.06073          +Inf     298.67206 BIN3
+\end{verbatim}
+\end{scriptsize}
+\end{landscape}
+
+\begin{landscape}
+\begin{scriptsize}
+\begin{verbatim}
+GLPK 4.42 - SENSITIVITY ANALYSIS REPORT                                                                         Page   2
+
+Problem:    PLAN
+Objective:  VALUE = 296.2166065 (MINimum)
+
+   No. Column name  St      Activity      Obj coef   Lower bound       Activity      Obj coef  Obj value at Limiting
+                                          Marginal   Upper bound          range         range   break point variable
+------ ------------ -- ------------- ------------- -------------  ------------- ------------- ------------- ------------
+     1 BIN1         NL        .             .03000        .           -28.82475       -.22362     288.90594 BIN4
+                                            .25362     200.00000       33.88040          +Inf     304.80951 BIN4
+
+     2 BIN2         BS     665.34296        .08000        .           802.22222        .01722     254.44822 BIN1
+                                            .         2500.00000      313.43066        .08863     301.95652 MN
+
+     3 BIN3         BS     490.25271        .17000     400.00000      788.61314        .15982     291.22807 MN
+                                            .          800.00000     -347.42857        .17948     300.86548 BIN5
+
+     4 BIN4         BS     424.18773        .12000     100.00000      710.52632        .10899     291.54745 MN
+                                            .          700.00000     -256.15524        .14651     307.46010 BIN1
+
+     5 BIN5         NL        .             .15000        .          -201.78739        .13544     293.27940 BIN3
+                                            .01456    1500.00000       58.79586          +Inf     297.07244 BIN3
+
+     6 ALUM         BS     299.63899        .21000        .           358.26772        .18885     289.87879 AL
+                                            .               +Inf      112.40876        .22622     301.07527 MN
+
+     7 SILICON      BS     120.57762        .38000        .           124.27093        .14828     268.27586 BIN5
+                                            .               +Inf       85.54745        .46667     306.66667 MN
+
+End of report
+\end{verbatim}
+\end{scriptsize}
+\end{landscape}
+
+\noindent
+{\tt Marginal} is the reduced cost (dual activity) of the auxiliary
+variable (row) or structural variable (column).
+
+\medskip
+
+\noindent
+{\tt Lower bound} is the lower right-hand side (row) or lower bound
+(column). If the row or column has no lower bound, this field contains
+{\tt -Inf}.
+
+\medskip
+
+\noindent
+{\tt Upper bound} is the upper right-hand side (row) or upper bound
+(column). If the row or column has no upper bound, this field contains
+{\tt +Inf}.
+
+\bigskip
+
+\noindent
+{\it Sensitivity analysis of active bounds}
+
+\medskip
+
+\noindent
+The sensitivity analysis of active bounds is performed only for rows,
+which are active constraints, and only for non-basic columns, because
+inactive constraints and basic columns have no active bounds.
+
+For every auxiliary (row) or structural (column) non-basic variable the
+routine starts changing its active bound in both direction. The first
+of the two lines in the report corresponds to decreasing, and the
+second line corresponds to increasing of the active bound. Since the
+variable being analyzed is non-basic, its activity, which is equal to
+its active bound, also starts changing. This changing leads to changing
+of basic (auxiliary and structural) variables, which depend on the
+non-basic variable. The current basis remains primal feasible and
+therefore optimal while values of all basic variables are primal
+feasible, i.e. are within their bounds. Therefore, if some basic
+variable called the {\it limiting variable} reaches its (lower or
+upper) bound first, before any other basic variables, it thereby limits
+further changing of the non-basic variable, because otherwise the
+current basis would become primal infeasible. The point, at which this
+happens, is called the {\it break point}. Note that there are two break
+points: the lower break point, which corresponds to decreasing of the
+non-basic variable, and the upper break point, which corresponds to
+increasing of the non-basic variable.
+
+In the analysis report values of the non-basic variable (i.e. of its
+active bound) being analyzed at both lower and upper break points are
+printed in the field `{\tt Activity range}'. Corresponding values of
+the objective function are printed in the field `{\tt Obj value at
+break point}', and symbolic names of corresponding limiting basic
+variables are printed in the field `{\tt Limiting variable}'.
+If the active bound can decrease or/and increase unlimitedly, the field
+`{\tt Activity range}' contains {\tt -Inf} or/and {\tt +Inf}, resp.
+
+For example (see the example report above), row SI is a double-sided
+constraint, which is active on its lower bound (right-hand side), and
+its activity in the optimal solution being equal to the lower bound is
+250. The activity range for this row is $[235.32871,255.06073]$. This
+means that the basis remains optimal while the lower bound is
+increasing up to 255.06073, and further increasing is limited by
+(structural) variable BIN3. If the lower bound reaches this upper break
+point, the objective value becomes equal to 298.67206.
+
+Note that if the basis does not change, the objective function depends
+on the non-basic variable linearly, and the per-unit change of the
+objective function is the reduced cost (marginal value) of the
+non-basic variable.
+
+\bigskip
+
+\noindent
+{\it Sensitivity analysis of objective coefficients at non-basic
+variables}
+
+\medskip
+
+\noindent
+The sensitivity analysis of the objective coefficient at a non-basic
+variable is quite simple, because in this case change in the objective
+coefficient leads to equivalent change in the reduced cost (marginal
+value).
+
+For every auxiliary (row) or structural (column) non-basic variable the
+routine starts changing its objective coefficient in both direction.
+(Note that auxiliary variables are not included in the objective
+function and therefore always have zero objective coefficients.) The
+first of the two lines in the report corresponds to decreasing, and the
+second line corresponds to increasing of the objective coefficient.
+This changing leads to changing of the reduced cost of the non-basic
+variable to be analyzed and does affect reduced costs of all other
+non-basic variables. The current basis remains dual feasible and
+therefore optimal while the reduced cost keeps its sign. Therefore, if
+the reduced cost reaches zero, it limits further changing of the
+objective coefficient (if only the non-basic variable is non-fixed).
+
+In the analysis report minimal and maximal values of the objective
+coefficient, on which the basis remains optimal, are printed in the
+field `\verb|Obj coef range|'. If the objective coefficient can
+decrease or/and increase unlimitedly, this field contains {\tt -Inf}
+or/and {\tt +Inf}, resp.
+
+For example (see the example report above), column BIN5 is non-basic
+having its lower bound active. Its objective coefficient is 0.15, and
+reduced cost in the optimal solution 0.01456. The column lower bound
+remains active while the column reduced cost remains non-negative,
+thus, minimal value of the objective coefficient, on which the current
+basis still remains optimal, is $0.15-0.01456=0.13644$, that is
+indicated in the field `\verb|Obj coef range|'.
+
+\bigskip
+
+\noindent
+{\it Sensitivity analysis of objective coefficients at basic variables}
+
+\medskip
+
+\noindent
+To perform sensitivity analysis for every auxiliary (row) or structural
+(column) variable the routine starts changing its objective coefficient
+in both direction. (Note that auxiliary variables are not included in
+the objective function and therefore always have zero objective
+coefficients.) The first of the two lines in the report corresponds to
+decreasing, and the second line corresponds to increasing of the
+objective coefficient. This changing leads to changing of reduced costs
+of non-basic variables. The current basis remains dual feasible and
+therefore optimal while reduced costs of all non-basic variables
+(except fixed variables) keep their signs. Therefore, if the reduced
+cost of some non-basic non-fixed variable called the {\it limiting
+variable} reaches zero first, before reduced cost of any other
+non-basic non-fixed variable, it thereby limits further changing of the
+objective coefficient, because otherwise the current basis would become
+dual infeasible (non-optimal). The point, at which this happens, is
+called the {\it break point}. Note that there are two break points: the
+lower break point, which corresponds to decreasing of the objective
+coefficient, and the upper break point, which corresponds to increasing
+of the objective coefficient. Let the objective coefficient reach its
+limit value and continue changing a bit further in the same direction
+that makes the current basis dual infeasible (non-optimal). Then the
+reduced cost of the non-basic limiting variable becomes ``a bit'' dual
+infeasible that forces the limiting variable to enter the basis
+replacing there some basic variable, which leaves the basis to keep its
+primal feasibility. It should be understood that if we change the
+current basis in this way exactly at the break point, both the current
+and adjacent bases will be optimal with the same objective value,
+because at the break point the limiting variable has zero reduced cost.
+On the other hand, in the adjacent basis the value of the limiting
+variable changes, because there it becomes basic, that leads to
+changing of the value of the basic variable being analyzed. Note that
+on determining the adjacent basis the bounds of the analyzed basic
+variable are ignored as if it were a free (unbounded) variable, so it
+cannot leave the current basis.
+
+In the analysis report lower and upper limits of the objective
+coefficient at the basic variable being analyzed, when the basis
+remains optimal, are printed in the field `{\tt Obj coef range}'.
+Corresponding values of the objective function at both lower and upper
+break points are printed in the field `{\tt Obj value at break point}',
+symbolic names of corresponding non-basic limiting variables are
+printed in the field `{\tt Limiting variable}', and values of the basic
+variable, which it would take on in the adjacent bases (as was
+explained above) are printed in the field `{\tt Activity range}'.
+If the objective coefficient can increase or/and decrease unlimitedly,
+the field `{\tt Obj coef range}' contains {\tt -Inf} and/or {\tt +Inf},
+resp. It also may happen that no dual feasible adjacent basis exists
+(i.e. on entering the basis the limiting variable can increase or
+decrease unlimitedly), in which case the field `{\tt Activity range}'
+contains {\tt -Inf} and/or {\tt +Inf}.
+
+\newpage
+
+For example (see the example report above), structural variable
+(column) BIN3 is basic, its optimal value is 490.25271, and its
+objective coefficient is 0.17. The objective coefficient range for this
+column is $[0.15982,0.17948]$. This means that the basis remains
+optimal while the objective coefficient is decreasing down to 0.15982,
+and further decreasing is limited by (auxiliary) variable MN. If we
+make the objective coefficient a bit less than 0.15982, the limiting
+variable MN will enter the basis, and in that adjacent basis the
+structural variable BIN3 will take on new optimal value 788.61314. At
+the lower break point, where the objective coefficient is exactly
+0.15982, the objective function takes on the value 291.22807 in both
+the current and adjacent bases.
+
+Note that if the basis does not change, the objective function depends
+on the objective coefficient at the basic variable linearly, and the
+per-unit change of the objective function is the value of the basic
+variable.
+
+%* eof *%




