alpar@9: %* glpk02.tex *%
alpar@9: 
alpar@9: \chapter{Basic API Routines}
alpar@9: 
alpar@9: This chapter describes GLPK API routines intended for using in
alpar@9: application programs.
alpar@9: 
alpar@9: \subsubsection*{Library header}
alpar@9: 
alpar@9: All GLPK API data types and routines are defined in the header file
alpar@9: \verb|glpk.h|. It should be included in all source files which use
alpar@9: GLPK API, either directly or indirectly through some other header file
alpar@9: as follows:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    #include <glpk.h>
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Error handling}
alpar@9: 
alpar@9: If some GLPK API routine detects erroneous or incorrect data passed by
alpar@9: the application program, it writes appropriate diagnostic messages to
alpar@9: the terminal and then abnormally terminates the application program.
alpar@9: In most practical cases this allows to simplify programming by avoiding
alpar@9: numerous checks of return codes. Thus, in order to prevent crashing the
alpar@9: application program should check all data, which are suspected to be
alpar@9: incorrect, before calling GLPK API routines.
alpar@9: 
alpar@9: Should note that this kind of error handling is used only in cases of
alpar@9: incorrect data passed by the application program. If, for example, the
alpar@9: application program calls some GLPK API routine to read data from an
alpar@9: input file and these data are incorrect, the GLPK API routine reports
alpar@9: about error in the usual way by means of the return code.
alpar@9: 
alpar@9: \subsubsection*{Thread safety}
alpar@9: 
alpar@9: Currently GLPK API routines are non-reentrant and therefore cannot be
alpar@9: used in multi-threaded programs.
alpar@9: 
alpar@9: \subsubsection*{Array indexing}
alpar@9: 
alpar@9: Normally all GLPK API routines start array indexing from 1, not from 0
alpar@9: (except the specially stipulated cases). This means, for example, that
alpar@9: if some vector $x$ of the length $n$ is passed as an array to some GLPK
alpar@9: API routine, the latter expects vector components to be placed in
alpar@9: locations \verb|x[1]|, \verb|x[2]|, \dots, \verb|x[n]|, and the location
alpar@9: \verb|x[0]| normally is not used.
alpar@9: 
alpar@9: In order to avoid indexing errors it is most convenient and most
alpar@9: reliable to declare the array \verb|x| as follows:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    double x[1+n];
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: or to allocate it as follows:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    double *x;
alpar@9:    . . .
alpar@9:    x = calloc(1+n, sizeof(double));
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: In both cases one extra location \verb|x[0]| is reserved that allows
alpar@9: passing the array to GLPK routines in a usual way.
alpar@9: 
alpar@9: \section{Problem object}
alpar@9: 
alpar@9: All GLPK API routines deal with so called {\it problem object}, which
alpar@9: is a program object of type \verb|glp_prob| and intended to represent
alpar@9: a particular LP or MIP instance.
alpar@9: 
alpar@9: The type \verb|glp_prob| is a data structure declared in the header
alpar@9: file \verb|glpk.h| as follows:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    typedef struct { ... } glp_prob;
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: Problem objects (i.e. program objects of the \verb|glp_prob| type) are
alpar@9: allocated and managed internally by the GLPK API routines. The
alpar@9: application program should never use any members of the \verb|glp_prob|
alpar@9: structure directly and should deal only with pointers to these objects
alpar@9: (that is, \verb|glp_prob *| values).
alpar@9: 
alpar@9: \pagebreak
alpar@9: 
alpar@9: The problem object consists of five segments, which are:
alpar@9: 
alpar@9: $\bullet$ problem segment,
alpar@9: 
alpar@9: $\bullet$ basis segment,
alpar@9: 
alpar@9: $\bullet$ interior point segment,
alpar@9: 
alpar@9: $\bullet$ MIP segment, and
alpar@9: 
alpar@9: $\bullet$ control parameters and statistics segment.
alpar@9: 
alpar@9: \subsubsection*{Problem segment}
alpar@9: 
alpar@9: The {\it problem segment} contains original LP/MIP data, which
alpar@9: corresponds to the problem formulation (1.1)---(1.3) (see Section
alpar@9: \ref{seclp}, page \pageref{seclp}). It includes the following
alpar@9: components:
alpar@9: 
alpar@9: $\bullet$ rows (auxiliary variables),
alpar@9: 
alpar@9: $\bullet$ columns (structural variables),
alpar@9: 
alpar@9: $\bullet$ objective function, and
alpar@9: 
alpar@9: $\bullet$ constraint matrix.
alpar@9: 
alpar@9: Rows and columns have the same set of the following attributes:
alpar@9: 
alpar@9: $\bullet$ ordinal number,
alpar@9: 
alpar@9: $\bullet$ symbolic name (1 up to 255 arbitrary graphic characters),
alpar@9: 
alpar@9: $\bullet$ type (free, lower bound, upper bound, double bound, fixed),
alpar@9: 
alpar@9: $\bullet$ numerical values of lower and upper bounds,
alpar@9: 
alpar@9: $\bullet$ scale factor.
alpar@9: 
alpar@9: {\it Ordinal numbers} are intended for referencing rows and columns.
alpar@9: Row ordinal numbers are integers $1, 2, \dots, m$, and column ordinal
alpar@9: numbers are integers $1, 2, \dots, n$, where $m$ and $n$ are,
alpar@9: respectively, the current number of rows and columns in the problem
alpar@9: object.
alpar@9: 
alpar@9: {\it Symbolic names} are intended for informational purposes. They also
alpar@9: can be used for referencing rows and columns.
alpar@9: 
alpar@9: {\it Types and bounds} of rows (auxiliary variables) and columns
alpar@9: (structural variables) are explained above (see Section \ref{seclp},
alpar@9: page \pageref{seclp}).
alpar@9: 
alpar@9: {\it Scale factors} are used internally for scaling rows and columns of
alpar@9: the constraint matrix.
alpar@9: 
alpar@9: Information about the {\it objective function} includes numerical
alpar@9: values of objective coefficients and a flag, which defines the
alpar@9: optimization direction (i.e. minimization or maximization).
alpar@9: 
alpar@9: The {\it constraint matrix} is a $m \times n$ rectangular matrix built
alpar@9: of constraint coefficients $a_{ij}$, which defines the system of linear
alpar@9: constraints (1.2) (see Section \ref{seclp}, page \pageref{seclp}). This
alpar@9: matrix is stored in the problem object in both row-wise and column-wise
alpar@9: sparse formats.
alpar@9: 
alpar@9: Once the problem object has been created, the application program can
alpar@9: access and modify any components of the problem segment in arbitrary
alpar@9: order.
alpar@9: 
alpar@9: \subsubsection*{Basis segment}
alpar@9: 
alpar@9: The {\it basis segment} of the problem object keeps information related
alpar@9: to the current basic solution. It includes:
alpar@9: 
alpar@9: $\bullet$ row and column statuses,
alpar@9: 
alpar@9: $\bullet$ basic solution statuses,
alpar@9: 
alpar@9: $\bullet$ factorization of the current basis matrix, and
alpar@9: 
alpar@9: $\bullet$ basic solution components.
alpar@9: 
alpar@9: The {\it row and column statuses} define which rows and columns are
alpar@9: basic and which are non-basic. These statuses may be assigned either by
alpar@9: the application program of by some API routines. Note that these
alpar@9: statuses are always defined independently on whether the corresponding
alpar@9: basis is valid or not.
alpar@9: 
alpar@9: The {\it basic solution statuses} include the {\it primal status} and
alpar@9: the {\it dual status}, which are set by the simplex-based solver once
alpar@9: the problem has been solved. The primal status shows whether a primal
alpar@9: basic solution is feasible, infeasible, or undefined. The dual status
alpar@9: shows the same for a dual basic solution.
alpar@9: 
alpar@9: The {\it factorization of the basis matrix} is some factorized form
alpar@9: (like LU-factorization) of the current basis matrix (defined by the
alpar@9: current row and column statuses). The factorization is used by the
alpar@9: simplex-based solver and kept when the solver terminates the search.
alpar@9: This feature allows efficiently reoptimizing the problem after some
alpar@9: modifications (for example, after changing some bounds or objective
alpar@9: coefficients). It also allows performing the post-optimal analysis (for
alpar@9: example, computing components of the simplex table, etc.).
alpar@9: 
alpar@9: The {\it basic solution components} include primal and dual values of
alpar@9: all auxiliary and structural variables for the most recently obtained
alpar@9: basic solution.
alpar@9: 
alpar@9: \subsubsection*{Interior point segment}
alpar@9: 
alpar@9: The {\it interior point segment} is automatically allocated after the
alpar@9: problem has been solved using the interior point solver. It contains
alpar@9: interior point solution components, which include the solution status,
alpar@9: and primal and dual values of all auxiliary and structural variables.
alpar@9: 
alpar@9: \subsubsection*{MIP segment}
alpar@9: 
alpar@9: The {\it MIP segment} is used only for MIP problems. This segment
alpar@9: includes:
alpar@9: 
alpar@9: $\bullet$ column kinds,
alpar@9: 
alpar@9: $\bullet$ MIP solution status, and
alpar@9: 
alpar@9: $\bullet$ MIP solution components.
alpar@9: 
alpar@9: The {\it column kinds} define which columns (i.e. structural variables)
alpar@9: are integer and which are continuous.
alpar@9: 
alpar@9: The {\it MIP solution status} is set by the MIP solver and shows whether
alpar@9: a MIP solution is integer optimal, integer feasible (non-optimal), or
alpar@9: undefined.
alpar@9: 
alpar@9: The {\it MIP solution components} are computed by the MIP solver and
alpar@9: include primal values of all auxiliary and structural variables for the
alpar@9: most recently obtained MIP solution.
alpar@9: 
alpar@9: Note that in case of MIP problem the basis segment corresponds to
alpar@9: the optimal solution of LP relaxation, which is also available to the
alpar@9: application program.
alpar@9: 
alpar@9: Currently the search tree is not kept in the MIP segment. Therefore if
alpar@9: the search has been terminated, it cannot be continued.
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Problem creating and modifying routines}
alpar@9: 
alpar@9: \subsection{glp\_create\_prob---create problem object}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: glp_prob *glp_create_prob(void);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_create_prob| creates a new problem object, which
alpar@9: initially is ``empty'', i.e. has no rows and columns.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine returns a pointer to the created object, which should be
alpar@9: used in any subsequent operations on this object.
alpar@9: 
alpar@9: \subsection{glp\_set\_prob\_name---assign (change) problem name}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_prob_name(glp_prob *lp, const char *name);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_prob_name| assigns a given symbolic
alpar@9: \verb|name| (1 up to 255 characters) to the specified problem object.
alpar@9: 
alpar@9: If the parameter \verb|name| is \verb|NULL| or empty string, the routine
alpar@9: erases an existing symbolic name of the problem object.
alpar@9: 
alpar@9: \subsection{glp\_set\_obj\_name---assign (change) objective function
alpar@9: name}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_obj_name(glp_prob *lp, const char *name);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_obj_name| assigns a given symbolic
alpar@9: \verb|name| (1 up to 255 characters) to the objective function of the
alpar@9: specified problem object.
alpar@9: 
alpar@9: If the parameter \verb|name| is \verb|NULL| or empty string, the routine
alpar@9: erases an existing symbolic name of the objective function.
alpar@9: 
alpar@9: \subsection{glp\_set\_obj\_dir---set (change) optimization direction\\
alpar@9: flag}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_obj_dir(glp_prob *lp, int dir);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_obj_dir| sets (changes) the optimization
alpar@9: direction flag (i.e. ``sense'' of the objective function) as specified
alpar@9: by the parameter \verb|dir|:
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|GLP_MIN| & minimization; \\
alpar@9: \verb|GLP_MAX| & maximization. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \noindent
alpar@9: (Note that by default the problem is minimization.)
alpar@9: 
alpar@9: \subsection{glp\_add\_rows---add new rows to problem object}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_add_rows(glp_prob *lp, int nrs);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_add_rows| adds \verb|nrs| rows (constraints) to
alpar@9: the specified problem object. New rows are always added to the end of
alpar@9: the row list, so the ordinal numbers of existing rows are not changed.
alpar@9: 
alpar@9: Being added each new row is initially free (unbounded) and has empty
alpar@9: list of the constraint coefficients.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_add_rows| returns the ordinal number of the first
alpar@9: new row added to the problem object.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_add\_cols---add new columns to problem object}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_add_cols(glp_prob *lp, int ncs);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_add_cols| adds \verb|ncs| columns (structural
alpar@9: variables) to the specified problem object. New columns are always added
alpar@9: to the end of the column list, so the ordinal numbers of existing
alpar@9: columns are not changed.
alpar@9: 
alpar@9: Being added each new column is initially fixed at zero and has empty
alpar@9: list of the constraint coefficients.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_add_cols| returns the ordinal number of the first
alpar@9: new column added to the problem object.
alpar@9: 
alpar@9: \subsection{glp\_set\_row\_name---assign (change) row name}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_row_name(glp_prob *lp, int i, const char *name);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_row_name| assigns a given symbolic
alpar@9: \verb|name| (1 up to 255 characters) to \verb|i|-th row (auxiliary
alpar@9: variable) of the specified problem object.
alpar@9: 
alpar@9: If the parameter \verb|name| is \verb|NULL| or empty string, the routine
alpar@9: erases an existing name of $i$-th row.
alpar@9: 
alpar@9: \subsection{glp\_set\_col\_name---assign (change) column name}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_col_name(glp_prob *lp, int j, const char *name);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_col_name| assigns a given symbolic
alpar@9: \verb|name| (1 up to 255 characters) to \verb|j|-th column (structural
alpar@9: variable) of the specified problem object.
alpar@9: 
alpar@9: If the parameter \verb|name| is \verb|NULL| or empty string, the routine
alpar@9: erases an existing name of $j$-th column.
alpar@9: 
alpar@9: \subsection{glp\_set\_row\_bnds---set (change) row bounds}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_row_bnds(glp_prob *lp, int i, int type,
alpar@9:       double lb, double ub);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_row_bnds| sets (changes) the type and bounds
alpar@9: of \verb|i|-th row (auxiliary variable) of the specified problem object.
alpar@9: 
alpar@9: The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type,
alpar@9: lower bound, and upper bound, respectively, as follows:
alpar@9: 
alpar@9: \begin{center}
alpar@9: \begin{tabular}{cr@{}c@{}ll}
alpar@9: Type & \multicolumn{3}{c}{Bounds} & Comment \\
alpar@9: \hline
alpar@9: \verb|GLP_FR| & $-\infty <$ &$\ x\ $& $< +\infty$
alpar@9:    & Free (unbounded) variable \\
alpar@9: \verb|GLP_LO| & $lb \leq$ &$\ x\ $& $< +\infty$
alpar@9:    & Variable with lower bound \\
alpar@9: \verb|GLP_UP| & $-\infty <$ &$\ x\ $& $\leq ub$
alpar@9:    & Variable with upper bound \\
alpar@9: \verb|GLP_DB| & $lb \leq$ &$\ x\ $& $\leq ub$
alpar@9:    & Double-bounded variable \\
alpar@9: \verb|GLP_FX| & $lb =$ &$\ x\ $& $= ub$
alpar@9:    & Fixed variable \\
alpar@9: \end{tabular}
alpar@9: \end{center}
alpar@9: 
alpar@9: \noindent
alpar@9: where $x$ is the auxiliary variable associated with $i$-th row.
alpar@9: 
alpar@9: If the row has no lower bound, the parameter \verb|lb| is ignored. If
alpar@9: the row has no upper bound, the parameter \verb|ub| is ignored. If the
alpar@9: row is an equality constraint (i.e. the corresponding auxiliary variable
alpar@9: is of fixed type), only the parameter \verb|lb| is used while the
alpar@9: parameter \verb|ub| is ignored.
alpar@9: 
alpar@9: Being added to the problem object each row is initially free, i.e. its
alpar@9: type is \verb|GLP_FR|.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_set\_col\_bnds---set (change) column bounds}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_col_bnds(glp_prob *lp, int j, int type,
alpar@9:       double lb, double ub);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_col_bnds| sets (changes) the type and bounds
alpar@9: of \verb|j|-th column (structural variable) of the specified problem
alpar@9: object.
alpar@9: 
alpar@9: The parameters \verb|type|, \verb|lb|, and \verb|ub| specify the type,
alpar@9: lower bound, and upper bound, respectively, as follows:
alpar@9: 
alpar@9: \begin{center}
alpar@9: \begin{tabular}{cr@{}c@{}ll}
alpar@9: Type & \multicolumn{3}{c}{Bounds} & Comment \\
alpar@9: \hline
alpar@9: \verb|GLP_FR| & $-\infty <$ &$\ x\ $& $< +\infty$
alpar@9:    & Free (unbounded) variable \\
alpar@9: \verb|GLP_LO| & $lb \leq$ &$\ x\ $& $< +\infty$
alpar@9:    & Variable with lower bound \\
alpar@9: \verb|GLP_UP| & $-\infty <$ &$\ x\ $& $\leq ub$
alpar@9:    & Variable with upper bound \\
alpar@9: \verb|GLP_DB| & $lb \leq$ &$\ x\ $& $\leq ub$
alpar@9:    & Double-bounded variable \\
alpar@9: \verb|GLP_FX| & $lb =$ &$\ x\ $& $= ub$
alpar@9:    & Fixed variable \\
alpar@9: \end{tabular}
alpar@9: \end{center}
alpar@9: 
alpar@9: \noindent
alpar@9: where $x$ is the structural variable associated with $j$-th column.
alpar@9: 
alpar@9: If the column has no lower bound, the parameter \verb|lb| is ignored.
alpar@9: If the column has no upper bound, the parameter \verb|ub| is ignored.
alpar@9: If the column is of fixed type, only the parameter \verb|lb| is used
alpar@9: while the parameter \verb|ub| is ignored.
alpar@9: 
alpar@9: Being added to the problem object each column is initially fixed at
alpar@9: zero, i.e. its type is \verb|GLP_FX| and both bounds are 0.
alpar@9: 
alpar@9: \subsection{glp\_set\_obj\_coef---set (change) objective coefficient
alpar@9: or constant term}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_obj_coef(glp_prob *lp, int j, double coef);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_obj_coef| sets (changes) the objective
alpar@9: coefficient at \verb|j|-th column (structural variable). A new value of
alpar@9: the objective coefficient is specified by the parameter \verb|coef|.
alpar@9: 
alpar@9: If the parameter \verb|j| is 0, the routine sets (changes) the constant
alpar@9: term (``shift'') of the objective function.
alpar@9: 
alpar@9: \subsection{glp\_set\_mat\_row---set (replace) row of the constraint
alpar@9: matrix}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_mat_row(glp_prob *lp, int i, int len,
alpar@9:       const int ind[], const double val[]);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_mat_row| stores (replaces) the contents of
alpar@9: \verb|i|-th row of the constraint matrix of the specified problem
alpar@9: object.
alpar@9: 
alpar@9: Column indices and numerical values of new row elements must be placed
alpar@9: in locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
alpar@9: \dots, \verb|val[len]|, respectively, where $0 \leq$ \verb|len| $\leq n$
alpar@9: is the new length of $i$-th row, $n$ is the current number of columns in
alpar@9: the problem object. Elements with identical column indices are not
alpar@9: allowed. Zero elements are allowed, but they are not stored in the
alpar@9: constraint matrix.
alpar@9: 
alpar@9: If the parameter \verb|len| is 0, the parameters \verb|ind| and/or
alpar@9: \verb|val| can be specified as \verb|NULL|.
alpar@9: 
alpar@9: \subsection{glp\_set\_mat\_col---set (replace) column of the
alpar@9: constr\-aint matrix}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_mat_col(glp_prob *lp, int j, int len,
alpar@9:       const int ind[], const double val[]);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_mat_col| stores (replaces) the contents of
alpar@9: \verb|j|-th column of the constraint matrix of the specified problem
alpar@9: object.
alpar@9: 
alpar@9: Row indices and numerical values of new column elements must be placed
alpar@9: in locations \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|,
alpar@9: \dots, \verb|val[len]|, respectively, where $0 \leq$ \verb|len| $\leq m$
alpar@9: is the new length of $j$-th column, $m$ is the current number of rows in
alpar@9: the problem object. Elements with identical row indices are not allowed.
alpar@9: Zero elements are allowed, but they are not stored in the constraint
alpar@9: matrix.
alpar@9: 
alpar@9: If the parameter \verb|len| is 0, the parameters \verb|ind| and/or
alpar@9: \verb|val| can be specified as \verb|NULL|.
alpar@9: 
alpar@9: \subsection{glp\_load\_matrix---load (replace) the whole constraint
alpar@9: matrix}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_load_matrix(glp_prob *lp, int ne, const int ia[],
alpar@9:       const int ja[], const double ar[]);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_load_matrix| loads the constraint matrix passed
alpar@9: in  the arrays \verb|ia|, \verb|ja|, and \verb|ar| into the specified
alpar@9: problem object. Before loading the current contents of the constraint
alpar@9: matrix is destroyed.
alpar@9: 
alpar@9: Constraint coefficients (elements of the constraint matrix) must be
alpar@9: specified as triplets (\verb|ia[k]|, \verb|ja[k]|, \verb|ar[k]|) for
alpar@9: $k=1,\dots,ne$, where \verb|ia[k]| is the row index, \verb|ja[k]| is
alpar@9: the column index, and \verb|ar[k]| is a numeric value of corresponding
alpar@9: constraint coefficient. The parameter \verb|ne| specifies the total
alpar@9: number of (non-zero) elements in the matrix to be loaded. Coefficients
alpar@9: with identical indices are not allowed. Zero coefficients are allowed,
alpar@9: however, they are not stored in the constraint matrix.
alpar@9: 
alpar@9: If the parameter \verb|ne| is 0, the parameters \verb|ia|, \verb|ja|,
alpar@9: and/or \verb|ar| can be specified as \verb|NULL|.
alpar@9: 
alpar@9: \subsection{glp\_check\_dup---check for duplicate elements in sparse
alpar@9: matrix}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_check_dup(int m, int n, int ne, const int ia[],
alpar@9:    const int ja[]);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_check_dup checks| for duplicate elements (that
alpar@9: is, elements with identical indices) in a sparse matrix specified in
alpar@9: the coordinate format.
alpar@9: 
alpar@9: The parameters $m$ and $n$ specifies, respectively, the number of rows
alpar@9: and columns in the matrix, $m\geq 0$, $n\geq 0$.
alpar@9: 
alpar@9: The parameter {\it ne} specifies the number of (structurally) non-zero
alpar@9: elements in the matrix, {\it ne} $\geq 0$.
alpar@9: 
alpar@9: Elements of the matrix are specified as doublets $(ia[k],ja[k])$ for
alpar@9: $k=1,\dots,ne$, where $ia[k]$ is a row index, $ja[k]$ is a column index.
alpar@9: 
alpar@9: The routine \verb|glp_check_dup| can be used prior to a call to the
alpar@9: routine \verb|glp_load_matrix| to check that the constraint matrix to
alpar@9: be loaded has no duplicate elements.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_check_dup| returns one of the following values:
alpar@9: 
alpar@9: \noindent
alpar@9: \begin{tabular}{@{}r@{\ }c@{\ }l@{}}
alpar@9: 0&---&the matrix has no duplicate elements;\\
alpar@9: $-k$&---&indices $ia[k]$ or/and $ja[k]$ are out of range;\\
alpar@9: $+k$&---&element $(ia[k],ja[k])$ is duplicate.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsection{glp\_sort\_matrix---sort elements of the constraint matrix}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_sort_matrix(glp_prob *P);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_sort_matrix| sorts elements of the constraint
alpar@9: matrix rebuilding its row and column linked lists. On exit from the
alpar@9: routine the constraint matrix is not changed, however, elements in the
alpar@9: row linked lists become ordered by ascending column indices, and the
alpar@9: elements in the column linked lists become ordered by ascending row
alpar@9: indices.
alpar@9: 
alpar@9: \subsection{glp\_del\_rows---delete rows from problem object}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_del_rows(glp_prob *lp, int nrs, const int num[]);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_del_rows| deletes rows from the specified problem
alpar@9: ob-\linebreak ject. Ordinal numbers of rows to be deleted should be
alpar@9: placed in locations \verb|num[1]|, \dots, \verb|num[nrs]|, where
alpar@9: ${\tt nrs}>0$.
alpar@9: 
alpar@9: Note that deleting rows involves changing ordinal numbers of other
alpar@9: rows remaining in the problem object. New ordinal numbers of the
alpar@9: remaining rows are assigned under the assumption that the original
alpar@9: order of rows is not changed. Let, for example, before deletion there
alpar@9: be five rows $a$, $b$, $c$, $d$, $e$ with ordinal numbers 1, 2, 3, 4, 5,
alpar@9: and let rows $b$ and $d$ have been deleted. Then after deletion the
alpar@9: remaining rows $a$, $c$, $e$ are assigned new oridinal numbers 1, 2, 3.
alpar@9: 
alpar@9: \subsection{glp\_del\_cols---delete columns from problem object}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_del_cols(glp_prob *lp, int ncs, const int num[]);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_del_cols| deletes columns from the specified
alpar@9: problem object. Ordinal numbers of columns to be deleted should be
alpar@9: placed in locations \verb|num[1]|, \dots, \verb|num[ncs]|, where
alpar@9: ${\tt ncs}>0$.
alpar@9: 
alpar@9: Note that deleting columns involves changing ordinal numbers of other
alpar@9: columns remaining in the problem object. New ordinal numbers of the
alpar@9: remaining columns are assigned under the assumption that the original
alpar@9: order of columns is not changed. Let, for example, before deletion there
alpar@9: be six columns $p$, $q$, $r$, $s$, $t$, $u$ with ordinal numbers 1, 2,
alpar@9: 3, 4, 5, 6, and let columns $p$, $q$, $s$ have been deleted. Then after
alpar@9: deletion the remaining columns $r$, $t$, $u$ are assigned new ordinal
alpar@9: numbers 1, 2, 3.
alpar@9: 
alpar@9: \subsection{glp\_copy\_prob---copy problem object content}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_copy_prob(glp_prob *dest, glp_prob *prob, int names);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_copy_prob| copies the content of the problem
alpar@9: object \verb|prob| to the problem object \verb|dest|.
alpar@9: 
alpar@9: The parameter \verb|names| is a flag. If it is \verb|GLP_ON|,
alpar@9: the routine also copies all symbolic names; otherwise, if it is
alpar@9: \verb|GLP_OFF|, no symbolic names are copied.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_erase\_prob---erase problem object content}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_erase_prob(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_erase_prob| erases the content of the specified
alpar@9: problem object. The effect of this operation is the same as if the
alpar@9: problem object would be deleted with the routine \verb|glp_delete_prob|
alpar@9: and then created anew with the routine \verb|glp_create_prob|, with the
alpar@9: only exception that the handle (pointer) to the problem object remains
alpar@9: valid.
alpar@9: 
alpar@9: \subsection{glp\_delete\_prob---delete problem object}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_delete_prob(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_delete_prob| deletes a problem object, which the
alpar@9: parameter \verb|lp| points to, freeing all the memory allocated to this
alpar@9: object.
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Problem retrieving routines}
alpar@9: 
alpar@9: \subsection{glp\_get\_prob\_name---retrieve problem name}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: const char *glp_get_prob_name(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_prob_name| returns a pointer to an internal
alpar@9: buffer, which contains symbolic name of the problem. However, if the
alpar@9: problem has no assigned name, the routine returns \verb|NULL|.
alpar@9: 
alpar@9: \subsection{glp\_get\_obj\_name---retrieve objective function name}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: const char *glp_get_obj_name(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_obj_name| returns a pointer to an internal
alpar@9: buffer, which contains symbolic name assigned to the objective
alpar@9: function. However, if the objective function has no assigned name, the
alpar@9: routine returns \verb|NULL|.
alpar@9: 
alpar@9: \subsection{glp\_get\_obj\_dir---retrieve optimization direction flag}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_obj_dir(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_obj_dir| returns the optimization direction
alpar@9: flag (i.e. ``sense'' of the objective function):
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|GLP_MIN| & minimization; \\
alpar@9: \verb|GLP_MAX| & maximization. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \pagebreak
alpar@9: 
alpar@9: \subsection{glp\_get\_num\_rows---retrieve number of rows}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_num_rows(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_num_rows| returns the current number of rows
alpar@9: in the specified problem object.
alpar@9: 
alpar@9: \subsection{glp\_get\_num\_cols---retrieve number of columns}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_num_cols(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_num_cols| returns the current number of
alpar@9: columns the specified problem object.
alpar@9: 
alpar@9: \subsection{glp\_get\_row\_name---retrieve row name}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: const char *glp_get_row_name(glp_prob *lp, int i);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_row_name| returns a pointer to an internal
alpar@9: buffer, which contains a symbolic name assigned to \verb|i|-th row.
alpar@9: However, if the row has no assigned name, the routine returns
alpar@9: \verb|NULL|.
alpar@9: 
alpar@9: \subsection{glp\_get\_col\_name---retrieve column name}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: const char *glp_get_col_name(glp_prob *lp, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_col_name| returns a pointer to an internal
alpar@9: buffer, which contains a symbolic name assigned to \verb|j|-th column.
alpar@9: However, if the column has no assigned name, the routine returns
alpar@9: \verb|NULL|.
alpar@9: 
alpar@9: \subsection{glp\_get\_row\_type---retrieve row type}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_row_type(glp_prob *lp, int i);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_row_type| returns the type of \verb|i|-th
alpar@9: row, i.e. the type of corresponding auxiliary variable, as follows:
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|GLP_FR| & free (unbounded) variable; \\
alpar@9: \verb|GLP_LO| & variable with lower bound; \\
alpar@9: \verb|GLP_UP| & variable with upper bound; \\
alpar@9: \verb|GLP_DB| & double-bounded variable; \\
alpar@9: \verb|GLP_FX| & fixed variable. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsection{glp\_get\_row\_lb---retrieve row lower bound}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_get_row_lb(glp_prob *lp, int i);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_row_lb| returns the lower bound of
alpar@9: \verb|i|-th row, i.e. the lower bound of corresponding auxiliary
alpar@9: variable. However, if the row has no lower bound, the routine returns
alpar@9: \verb|-DBL_MAX|.
alpar@9: 
alpar@9: \subsection{glp\_get\_row\_ub---retrieve row upper bound}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_get_row_ub(glp_prob *lp, int i);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_row_ub| returns the upper bound of
alpar@9: \verb|i|-th row, i.e. the upper bound of corresponding auxiliary
alpar@9: variable. However, if the row has no upper bound, the routine returns
alpar@9: \verb|+DBL_MAX|.
alpar@9: 
alpar@9: \subsection{glp\_get\_col\_type---retrieve column type}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_col_type(glp_prob *lp, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_col_type| returns the type of \verb|j|-th
alpar@9: column, i.e. the type of corresponding structural variable, as follows:
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|GLP_FR| & free (unbounded) variable; \\
alpar@9: \verb|GLP_LO| & variable with lower bound; \\
alpar@9: \verb|GLP_UP| & variable with upper bound; \\
alpar@9: \verb|GLP_DB| & double-bounded variable; \\
alpar@9: \verb|GLP_FX| & fixed variable. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsection{glp\_get\_col\_lb---retrieve column lower bound}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_get_col_lb(glp_prob *lp, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_col_lb| returns the lower bound of
alpar@9: \verb|j|-th column, i.e. the lower bound of corresponding structural
alpar@9: variable. However, if the column has no lower bound, the routine returns
alpar@9: \verb|-DBL_MAX|.
alpar@9: 
alpar@9: \subsection{glp\_get\_col\_ub---retrieve column upper bound}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_get_col_ub(glp_prob *lp, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_col_ub| returns the upper bound of
alpar@9: \verb|j|-th column, i.e. the upper bound of corresponding structural
alpar@9: variable. However, if the column has no upper bound, the routine returns
alpar@9: \verb|+DBL_MAX|.
alpar@9: 
alpar@9: \subsection{glp\_get\_obj\_coef---retrieve objective coefficient or\\
alpar@9: constant term}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_get_obj_coef(glp_prob *lp, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_obj_coef| returns the objective coefficient
alpar@9: at \verb|j|-th structural variable (column).
alpar@9: 
alpar@9: If the parameter \verb|j| is 0, the routine returns the constant term
alpar@9: (``shift'') of the objective function.
alpar@9: 
alpar@9: \subsection{glp\_get\_num\_nz---retrieve number of constraint
alpar@9: coefficients}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_num_nz(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_num_nz| returns the number of non-zero
alpar@9: elements in the constraint matrix of the specified problem object.
alpar@9: 
alpar@9: \subsection{glp\_get\_mat\_row---retrieve row of the constraint
alpar@9: matrix}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_mat_row(glp_prob *lp, int i, int ind[],
alpar@9:       double val[]);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_get_mat_row| scans (non-zero) elements of
alpar@9: \verb|i|-th row of the constraint matrix of the specified problem object
alpar@9: and stores their column indices and numeric values to locations
alpar@9: \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
alpar@9: \verb|val[len]|, respectively, where $0\leq{\tt len}\leq n$ is the
alpar@9: number of elements in $i$-th row, $n$ is the number of columns.
alpar@9: 
alpar@9: The parameter \verb|ind| and/or \verb|val| can be specified as
alpar@9: \verb|NULL|, in which case corresponding information is not stored.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_mat_row| returns the length \verb|len|, i.e.
alpar@9: the number of (non-zero) elements in \verb|i|-th row.
alpar@9: 
alpar@9: \subsection{glp\_get\_mat\_col---retrieve column of the constraint\\
alpar@9: matrix}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_mat_col(glp_prob *lp, int j, int ind[],
alpar@9:       double val[]);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_get_mat_col| scans (non-zero) elements of
alpar@9: \verb|j|-th column of the constraint matrix of the specified problem
alpar@9: object and stores their row indices and numeric values to locations
alpar@9: \verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
alpar@9: \verb|val[len]|, respectively, where $0\leq{\tt len}\leq m$ is the
alpar@9: number of elements in $j$-th column, $m$ is the number of rows.
alpar@9: 
alpar@9: The parameter \verb|ind| and/or \verb|val| can be specified as
alpar@9: \verb|NULL|, in which case corresponding information is not stored.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_mat_col| returns the length \verb|len|, i.e.
alpar@9: the number of (non-zero) elements in \verb|j|-th column.
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Row and column searching routines}
alpar@9: 
alpar@9: \subsection{glp\_create\_index---create the name index}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_create_index(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_create_index| creates the name index for the
alpar@9: specified problem object. The name index is an auxiliary data structure,
alpar@9: which is intended to quickly (i.e. for logarithmic time) find rows and
alpar@9: columns by their names.
alpar@9: 
alpar@9: This routine can be called at any time. If the name index already
alpar@9: exists, the routine does nothing.
alpar@9: 
alpar@9: \subsection{glp\_find\_row---find row by its name}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_find_row(glp_prob *lp, const char *name);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_find_row| returns the ordinal number of a row,
alpar@9: which is assigned (by the routine \verb|glp_set_row_name|) the specified
alpar@9: symbolic \verb|name|. If no such row exists, the routine returns 0.
alpar@9: 
alpar@9: \subsection{glp\_find\_col---find column by its name}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_find_col(glp_prob *lp, const char *name);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_find_col| returns the ordinal number of a column,
alpar@9: which is assigned (by the routine \verb|glp_set_col_name|) the specified
alpar@9: symbolic \verb|name|. If no such column exists, the routine returns 0.
alpar@9: 
alpar@9: \subsection{glp\_delete\_index---delete the name index}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_delete_index(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_delete_index| deletes the name index previously
alpar@9: created by the routine \verb|glp_create_index| and frees the memory
alpar@9: allocated to this auxiliary data structure.
alpar@9: 
alpar@9: This routine can be called at any time. If the name index does not
alpar@9: exist, the routine does nothing.
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Problem scaling routines}
alpar@9: 
alpar@9: \subsection{Background}
alpar@9: 
alpar@9: In GLPK the {\it scaling} means a linear transformation applied to the
alpar@9: constraint matrix to improve its numerical properties.\footnote{In many
alpar@9: cases a proper scaling allows making the constraint matrix to be better
alpar@9: conditioned, i.e. decreasing its condition number, that makes
alpar@9: computations numerically more stable.}
alpar@9: 
alpar@9: The main equality is the following:
alpar@9: $$\widetilde{A}=RAS,\eqno(2.1)$$
alpar@9: where $A=(a_{ij})$ is the original constraint matrix, $R=(r_{ii})>0$ is
alpar@9: a diagonal matrix used to scale rows (constraints), $S=(s_{jj})>0$ is a
alpar@9: diagonal matrix used to scale columns (variables), $\widetilde{A}$ is
alpar@9: the scaled constraint matrix.
alpar@9: 
alpar@9: From (2.1) it follows that in the {\it scaled} problem instance each
alpar@9: original constraint coefficient $a_{ij}$ is replaced by corresponding
alpar@9: scaled constraint coefficient:
alpar@9: $$\widetilde{a}_{ij}=r_{ii}a_{ij}s_{jj}.\eqno(2.2)$$
alpar@9: 
alpar@9: Note that the scaling is performed internally and therefore
alpar@9: transparently to the user. This means that on API level the user always
alpar@9: deal with unscaled data.
alpar@9: 
alpar@9: Scale factors $r_{ii}$ and $s_{jj}$ can be set or changed at any time
alpar@9: either directly by the application program in a problem specific way
alpar@9: (with the routines \verb|glp_set_rii| and \verb|glp_set_sjj|), or by
alpar@9: some API routines intended for automatic scaling.
alpar@9: 
alpar@9: \subsection{glp\_set\_rii---set (change) row scale factor}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_rii(glp_prob *lp, int i, double rii);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_rii| sets (changes) the scale factor $r_{ii}$
alpar@9: for $i$-th row of the specified problem object.
alpar@9: 
alpar@9: \subsection{glp\_set\_sjj---set (change) column scale factor}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_sjj(glp_prob *lp, int j, double sjj);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_sjj| sets (changes) the scale factor $s_{jj}$
alpar@9: for $j$-th column of the specified problem object.
alpar@9: 
alpar@9: \subsection{glp\_get\_rii---retrieve row scale factor}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_get_rii(glp_prob *lp, int i);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_rii| returns current scale factor $r_{ii}$ for
alpar@9: $i$-th row of the specified problem object.
alpar@9: 
alpar@9: \subsection{glp\_get\_sjj---retrieve column scale factor}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_get_sjj(glp_prob *lp, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_sjj| returns current scale factor $s_{jj}$ for
alpar@9: $j$-th column of the specified problem object.
alpar@9: 
alpar@9: \subsection{glp\_scale\_prob---scale problem data}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_scale_prob(glp_prob *lp, int flags);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_scale_prob| performs automatic scaling of problem
alpar@9: data for the specified problem object.
alpar@9: 
alpar@9: The parameter \verb|flags| specifies scaling options used by the
alpar@9: routine. The options can be combined with the bitwise OR operator and
alpar@9: may be the following:
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|GLP_SF_GM| & perform geometric mean scaling;\\
alpar@9: \verb|GLP_SF_EQ| & perform equilibration scaling;\\
alpar@9: \verb|GLP_SF_2N| & round scale factors to nearest power of two;\\
alpar@9: \verb|GLP_SF_SKIP| & skip scaling, if the problem is well scaled.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: The parameter \verb|flags| may be specified as \verb|GLP_SF_AUTO|, in
alpar@9: which case the routine chooses the scaling options automatically.
alpar@9: 
alpar@9: \subsection{glp\_unscale\_prob---unscale problem data}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_unscale_prob(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: The routine \verb|glp_unscale_prob| performs unscaling of problem data
alpar@9: for the specified problem object.
alpar@9: 
alpar@9: ``Unscaling'' means replacing the current scaling matrices $R$ and $S$
alpar@9: by unity matrices that cancels the scaling effect.
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{LP basis constructing routines}
alpar@9: 
alpar@9: \subsection{Background}
alpar@9: 
alpar@9: To start the search the simplex method needs a valid initial basis. In
alpar@9: GLPK the basis is completely defined by a set of {\it statuses} assigned
alpar@9: to {\it all} (auxiliary and structural) variables, where the status may
alpar@9: be one of the following:
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|GLP_BS| & basic variable;\\
alpar@9: \verb|GLP_NL| & non-basic variable having active lower bound;\\
alpar@9: \verb|GLP_NU| & non-basic variable having active upper bound;\\
alpar@9: \verb|GLP_NF| & non-basic free variable;\\
alpar@9: \verb|GLP_NS| & non-basic fixed variable.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: The basis is {\it valid}, if the basis matrix, which is a matrix built
alpar@9: of columns of the augmented constraint matrix $(I\:|-A)$ corresponding
alpar@9: to basic variables, is non-singular. This, in particular, means that
alpar@9: the number of basic variables must be the same as the number of rows in
alpar@9: the problem object. (For more details see Section \ref{lpbasis}, page
alpar@9: \pageref{lpbasis}.)
alpar@9: 
alpar@9: Any initial basis may be constructed (or restored) with the API
alpar@9: routines \verb|glp_set_row_stat| and \verb|glp_set_col_stat| by
alpar@9: assigning appropriate statuses to auxiliary and structural variables.
alpar@9: Another way to construct an initial basis is to use API routines like
alpar@9: \verb|glp_adv_basis|, which implement so called
alpar@9: {\it crashing}.\footnote{This term is from early linear programming
alpar@9: systems and means a heuristic to construct a valid initial basis.} Note
alpar@9: that on normal exit the simplex solver remains the basis valid, so in
alpar@9: case of reoptimization there is no need to construct an initial basis
alpar@9: from scratch.
alpar@9: 
alpar@9: \subsection{glp\_set\_row\_stat---set (change) row status}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_row_stat(glp_prob *lp, int i, int stat);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_row_stat| sets (changes) the current status
alpar@9: of \verb|i|-th row (auxiliary variable) as specified by the parameter
alpar@9: \verb|stat|:
alpar@9: 
alpar@9: \begin{tabular}{@{}lp{104.2mm}@{}}
alpar@9: \verb|GLP_BS| & make the row basic (make the constraint inactive); \\
alpar@9: \verb|GLP_NL| & make the row non-basic (make the constraint active); \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \begin{tabular}{@{}lp{104.2mm}@{}}
alpar@9: \verb|GLP_NU| & make the row non-basic and set it to the upper bound;
alpar@9:    if the row is not double-bounded, this status is equivalent to
alpar@9:    \verb|GLP_NL| (only in the case of this routine); \\
alpar@9: \verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this
alpar@9:    routine); \\
alpar@9: \verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this
alpar@9:    routine). \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsection{glp\_set\_col\_stat---set (change) column status}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_col_stat(glp_prob *lp, int j, int stat);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_col_stat sets| (changes) the current status
alpar@9: of \verb|j|-th column (structural variable) as specified by the
alpar@9: parameter \verb|stat|:
alpar@9: 
alpar@9: \begin{tabular}{@{}lp{104.2mm}@{}}
alpar@9: \verb|GLP_BS| & make the column basic; \\
alpar@9: \verb|GLP_NL| & make the column non-basic; \\
alpar@9: \verb|GLP_NU| & make the column non-basic and set it to the upper
alpar@9:    bound; if the column is not double-bounded, this status is equivalent
alpar@9:    to \verb|GLP_NL| (only in the case of this routine); \\
alpar@9: \verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this
alpar@9:    routine); \\
alpar@9: \verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this
alpar@9:    routine).
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsection{glp\_std\_basis---construct standard initial LP basis}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_std_basis(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_std_basis| constructs the ``standard'' (trivial)
alpar@9: initial LP basis for the specified problem object.
alpar@9: 
alpar@9: In the ``standard'' LP basis all auxiliary variables (rows) are basic,
alpar@9: and all structural variables (columns) are non-basic (so the
alpar@9: corresponding basis matrix is unity).
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_adv\_basis---construct advanced initial LP basis}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_adv_basis(glp_prob *lp, int flags);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_adv_basis| constructs an advanced initial LP
alpar@9: basis for the specified problem object.
alpar@9: 
alpar@9: The parameter \verb|flags| is reserved for use in the future and must
alpar@9: be specified as zero.
alpar@9: 
alpar@9: In order to construct the advanced initial LP basis the routine does
alpar@9: the following:
alpar@9: 
alpar@9: 1) includes in the basis all non-fixed auxiliary variables;
alpar@9: 
alpar@9: 2) includes in the basis as many non-fixed structural variables as
alpar@9: possible keeping the triangular form of the basis matrix;
alpar@9: 
alpar@9: 3) includes in the basis appropriate (fixed) auxiliary variables to
alpar@9: complete the basis.
alpar@9: 
alpar@9: As a result the initial LP basis has as few fixed variables as possible
alpar@9: and the corresponding basis matrix is triangular.
alpar@9: 
alpar@9: \subsection{glp\_cpx\_basis---construct Bixby's initial LP basis}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_cpx_basis(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_cpx_basis| constructs an initial basis for the
alpar@9: specified problem object with the algorithm proposed by
alpar@9: R.~Bixby.\footnote{Robert E. Bixby, ``Implementing the Simplex Method:
alpar@9: The Initial Basis.'' ORSA Journal on Computing, Vol. 4, No. 3, 1992,
alpar@9: pp. 267-84.}
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Simplex method routines}
alpar@9: 
alpar@9: The {\it simplex method} is a well known efficient numerical procedure
alpar@9: to solve LP problems.
alpar@9: 
alpar@9: On each iteration the simplex method transforms the original system of
alpar@9: equaility constraints (1.2) resolving them through different sets of
alpar@9: variables to an equivalent system called {\it the simplex table} (or
alpar@9: sometimes {\it the simplex tableau}), which has the following form:
alpar@9: $$
alpar@9: \begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
alpar@9: z&=&d_1(x_N)_1&+&d_2(x_N)_2&+ \dots +&d_n(x_N)_n \\
alpar@9: (x_B)_1&=&\xi_{11}(x_N)_1& +& \xi_{12}(x_N)_2& + \dots +&
alpar@9:    \xi_{1n}(x_N)_n \\
alpar@9: (x_B)_2&=& \xi_{21}(x_N)_1& +& \xi_{22}(x_N)_2& + \dots +&
alpar@9:    \xi_{2n}(x_N)_n \\
alpar@9: \multicolumn{7}{c}
alpar@9: {.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
alpar@9: (x_B)_m&=&\xi_{m1}(x_N)_1& +& \xi_{m2}(x_N)_2& + \dots +&
alpar@9:    \xi_{mn}(x_N)_n \\
alpar@9: \end{array} \eqno (2.3)
alpar@9: $$
alpar@9: where: $(x_B)_1, (x_B)_2, \dots, (x_B)_m$ are basic variables;
alpar@9: $(x_N)_1, (x_N)_2, \dots, (x_N)_n$ are non-basic variables;
alpar@9: $d_1, d_2, \dots, d_n$ are reduced costs;
alpar@9: $\xi_{11}, \xi_{12}, \dots, \xi_{mn}$ are coefficients of the
alpar@9: simplex table. (May note that the original LP problem (1.1)---(1.3) also
alpar@9: has the form of a simplex table, where all equalities are resolved
alpar@9: through auxiliary variables.)
alpar@9: 
alpar@9: From the linear programming theory it is known that if an optimal
alpar@9: solution of the LP problem (1.1)---(1.3) exists, it can always be
alpar@9: written in the form (2.3), where non-basic variables are set on their
alpar@9: bounds while values of the objective function and basic variables are
alpar@9: determined by the corresponding equalities of the simplex table.
alpar@9: 
alpar@9: A set of values of all basic and non-basic variables determined by the
alpar@9: simplex table is called {\it basic solution}. If all basic variables are
alpar@9: within their bounds, the basic solution is called {\it (primal)
alpar@9: feasible}, otherwise it is called {\it (primal) infeasible}. A feasible
alpar@9: basic solution, which provides a smallest (in case of minimization) or
alpar@9: a largest (in case of maximization) value of the objective function is
alpar@9: called {\it optimal}. Therefore, for solving LP problem the simplex
alpar@9: method tries to find its optimal basic solution.
alpar@9: 
alpar@9: Primal feasibility of some basic solution may be stated by simple
alpar@9: checking if all basic variables are within their bounds. Basic solution
alpar@9: is optimal if additionally the following optimality conditions are
alpar@9: satisfied for all non-basic variables:
alpar@9: \begin{center}
alpar@9: \begin{tabular}{lcc}
alpar@9: Status of $(x_N)_j$ & Minimization & Maximization \\
alpar@9: \hline
alpar@9: $(x_N)_j$ is free & $d_j = 0$ & $d_j = 0$ \\
alpar@9: $(x_N)_j$ is on its lower bound & $d_j \geq 0$ & $d_j \leq 0$ \\
alpar@9: $(x_N)_j$ is on its upper bound & $d_j \leq 0$ & $d_j \geq 0$ \\
alpar@9: \end{tabular}
alpar@9: \end{center}
alpar@9: In other words, basic solution is optimal if there is no non-basic
alpar@9: variable, which changing in the feasible direction (i.e. increasing if
alpar@9: it is free or on its lower bound, or decreasing if it is free or on its
alpar@9: upper bound) can improve (i.e. decrease in case of minimization or
alpar@9: increase in case of maximization) the objective function.
alpar@9: 
alpar@9: If all non-basic variables satisfy to the optimality conditions shown
alpar@9: above (independently on whether basic variables are within their bounds
alpar@9: or not), the basic solution is called {\it dual feasible}, otherwise it
alpar@9: is called {\it dual infeasible}.
alpar@9: 
alpar@9: It may happen that some LP problem has no primal feasible solution due
alpar@9: to incorrect formulation---this means that its constraints conflict
alpar@9: with each other. It also may happen that some LP problem has unbounded
alpar@9: solution again due to incorrect formulation---this means that some
alpar@9: non-basic variable can improve the objective function, i.e. the
alpar@9: optimality conditions are violated, and at the same time this variable
alpar@9: can infinitely change in the feasible direction meeting no resistance
alpar@9: from basic variables. (May note that in the latter case the LP problem
alpar@9: has no dual feasible solution.)
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \subsection{glp\_simplex---solve LP problem with the primal or dual
alpar@9: simplex method}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_simplex(glp_prob *lp, const glp_smcp *parm);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_simplex| is a driver to the LP solver based on
alpar@9: the simplex method. This routine retrieves problem data from the
alpar@9: specified problem object, calls the solver to solve the problem
alpar@9: instance, and stores results of computations back into the problem
alpar@9: object.
alpar@9: 
alpar@9: The simplex solver has a set of control parameters. Values of the
alpar@9: control parameters can be passed in the structure \verb|glp_smcp|,
alpar@9: which the parameter \verb|parm| points to. For detailed description of
alpar@9: this structure see paragraph ``Control parameters'' below.
alpar@9: Before specifying some control parameters the application program
alpar@9: should initialize the structure \verb|glp_smcp| by default values of
alpar@9: all control parameters using the routine \verb|glp_init_smcp| (see the
alpar@9: next subsection). This is needed for backward compatibility, because in
alpar@9: the future there may appear new members in the structure
alpar@9: \verb|glp_smcp|.
alpar@9: 
alpar@9: The parameter \verb|parm| can be specified as \verb|NULL|, in which
alpar@9: case the solver uses default settings.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: \def\arraystretch{1}
alpar@9: 
alpar@9: \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9: 0 & The LP problem instance has been successfully solved. (This code
alpar@9: does {\it not} necessarily mean that the solver has found optimal
alpar@9: solution. It only means that the solution process was successful.) \\
alpar@9: \verb|GLP_EBADB| & Unable to start the search, because the initial basis
alpar@9: specified in the problem object is invalid---the number of basic
alpar@9: (auxiliary and structural) variables is not the same as the number of
alpar@9: rows in the problem object.\\
alpar@9: \verb|GLP_ESING| & Unable to start the search, because the basis matrix
alpar@9: corresponding to the initial basis is singular within the working
alpar@9: precision.\\
alpar@9: \verb|GLP_ECOND| & Unable to start the search, because the basis matrix
alpar@9: corresponding to the initial basis is ill-conditioned, i.e. its
alpar@9: condition number is too large.\\
alpar@9: \verb|GLP_EBOUND| & Unable to start the search, because some
alpar@9: double-bounded (auxiliary or structural) variables have incorrect
alpar@9: bounds.\\
alpar@9: \verb|GLP_EFAIL| & The search was prematurely terminated due to the
alpar@9: solver failure.\\
alpar@9: \verb|GLP_EOBJLL| & The search was prematurely terminated, because the
alpar@9: objective function being maximized has reached its lower limit and
alpar@9: continues decreasing (the dual simplex only).\\
alpar@9: \verb|GLP_EOBJUL| & The search was prematurely terminated, because the
alpar@9: objective function being minimized has reached its upper limit and
alpar@9: continues increasing (the dual simplex only).\\
alpar@9: \verb|GLP_EITLIM| & The search was prematurely terminated, because the
alpar@9: simplex iteration limit has been exceeded.\\
alpar@9: \verb|GLP_ETMLIM| & The search was prematurely terminated, because the
alpar@9: time limit has been exceeded.\\
alpar@9: \verb|GLP_ENOPFS| & The LP problem instance has no primal feasible
alpar@9: solution (only if the LP presolver is used).\\
alpar@9: \verb|GLP_ENODFS| & The LP problem instance has no dual feasible
alpar@9: solution (only if the LP presolver is used).\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsubsection*{Built-in LP presolver}
alpar@9: 
alpar@9: The simplex solver has {\it built-in LP presolver}. It is a subprogram
alpar@9: that transforms the original LP problem specified in the problem object
alpar@9: to an equivalent LP problem, which may be easier for solving with the
alpar@9: simplex method than the original one. This is attained mainly due to
alpar@9: reducing the problem size and improving its numeric properties (for
alpar@9: example, by removing some inactive constraints or by fixing some
alpar@9: non-basic variables). Once the transformed LP problem has been solved,
alpar@9: the presolver transforms its basic solution back to the corresponding
alpar@9: basic solution of the original problem.
alpar@9: 
alpar@9: Presolving is an optional feature of the routine \verb|glp_simplex|,
alpar@9: and by default it is disabled. In order to enable the LP presolver the
alpar@9: control parameter \verb|presolve| should be set to \verb|GLP_ON| (see
alpar@9: paragraph ``Control parameters'' below). Presolving may be used when
alpar@9: the problem instance is solved for the first time. However, on
alpar@9: performing re-optimization the presolver should be disabled.
alpar@9: 
alpar@9: The presolving procedure is transparent to the API user in the sense
alpar@9: that all necessary processing is performed internally, and a basic
alpar@9: solution of the original problem recovered by the presolver is the same
alpar@9: as if it were computed directly, i.e. without presolving.
alpar@9: 
alpar@9: Note that the presolver is able to recover only optimal solutions. If
alpar@9: a computed solution is infeasible or non-optimal, the corresponding
alpar@9: solution of the original problem cannot be recovered and therefore
alpar@9: remains undefined. If you need to know a basic solution even if it is
alpar@9: infeasible or non-optimal, the presolver should be disabled.
alpar@9: 
alpar@9: \subsubsection*{Terminal output}
alpar@9: 
alpar@9: Solving large problem instances may take a long time, so the solver
alpar@9: reports some information about the current basic solution, which is sent
alpar@9: to the terminal. This information has the following format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: nnn:  obj = xxx  infeas = yyy (ddd)
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: where: `\verb|nnn|' is the iteration number, `\verb|xxx|' is the
alpar@9: current value of the objective function (it is is unscaled and has
alpar@9: correct sign); `\verb|yyy|' is the current sum of primal or dual
alpar@9: infeasibilities (it is scaled and therefore may be used only for visual
alpar@9: estimating), `\verb|ddd|' is the current number of fixed basic
alpar@9: variables.
alpar@9: 
alpar@9: The symbol preceding the iteration number indicates which phase of the
alpar@9: simplex method is in effect:
alpar@9: 
alpar@9: {\it Blank} means that the solver is searching for primal feasible
alpar@9: solution using the primal simplex or for dual feasible solution using
alpar@9: the dual simplex;
alpar@9: 
alpar@9: {\it Asterisk} (\verb|*|) means that the solver is searching for
alpar@9: optimal solution using the primal simplex;
alpar@9: 
alpar@9: {\it Vertical dash} (\verb/|/) means that the solver is searching for
alpar@9: optimal solution using the dual simplex.
alpar@9: 
alpar@9: \subsubsection*{Control parameters}
alpar@9: 
alpar@9: This paragraph describes all control parameters currently used in the
alpar@9: simplex solver. Symbolic names of control parameters are names of
alpar@9: corresponding members in the structure \verb|glp_smcp|.
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
alpar@9: \\
alpar@9: &Message level for terminal output:\\
alpar@9: &\verb|GLP_MSG_OFF|---no output;\\
alpar@9: &\verb|GLP_MSG_ERR|---error and warning messages only;\\
alpar@9: &\verb|GLP_MSG_ON |---normal output;\\
alpar@9: &\verb|GLP_MSG_ALL|---full output (including informational messages).
alpar@9: \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int meth} (default: {\tt GLP\_PRIMAL})}
alpar@9: \\
alpar@9: &Simplex method option:\\
alpar@9: &\verb|GLP_PRIMAL|---use two-phase primal simplex;\\
alpar@9: &\verb|GLP_DUAL  |---use two-phase dual simplex;\\
alpar@9: &\verb|GLP_DUALP |---use two-phase dual simplex, and if it fails,
alpar@9: switch to the\\
alpar@9: &\verb|            |$\:$ primal simplex.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int pricing} (default: {\tt GLP\_PT\_PSE})}
alpar@9: \\
alpar@9: &Pricing technique:\\
alpar@9: &\verb|GLP_PT_STD|---standard (textbook);\\
alpar@9: &\verb|GLP_PT_PSE|---projected steepest edge.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int r\_test} (default: {\tt GLP\_RT\_HAR})}
alpar@9: \\
alpar@9: &Ratio test technique:\\
alpar@9: &\verb|GLP_RT_STD|---standard (textbook);\\
alpar@9: &\verb|GLP_RT_HAR|---Harris' two-pass ratio test.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt double tol\_bnd} (default: {\tt 1e-7})}
alpar@9: \\
alpar@9: &Tolerance used to check if the basic solution is primal feasible.
alpar@9: (Do not change this parameter without detailed understanding its
alpar@9: purpose.)\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt double tol\_dj} (default: {\tt 1e-7})}
alpar@9: \\
alpar@9: &Tolerance used to check if the basic solution is dual feasible.
alpar@9: (Do not change this parameter without detailed understanding its
alpar@9: purpose.)\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt double tol\_piv} (default: {\tt 1e-10})}
alpar@9: \\
alpar@9: &Tolerance used to choose eligble pivotal elements of the simplex table.
alpar@9: (Do not change this parameter without detailed understanding its
alpar@9: purpose.)\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt double obj\_ll} (default: {\tt -DBL\_MAX})}
alpar@9: \\
alpar@9: &Lower limit of the objective function. If the objective function
alpar@9: reaches this limit and continues decreasing, the solver terminates the
alpar@9: search. (Used in the dual simplex only.)\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt double obj\_ul} (default: {\tt +DBL\_MAX})}
alpar@9: \\
alpar@9: &Upper limit of the objective function. If the objective function
alpar@9: reaches this limit and continues increasing, the solver terminates the
alpar@9: search. (Used in the dual simplex only.)\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int it\_lim} (default: {\tt INT\_MAX})}
alpar@9: \\
alpar@9: &Simplex iteration limit.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int tm\_lim} (default: {\tt INT\_MAX})}
alpar@9: \\
alpar@9: &Searching time limit, in milliseconds.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int out\_frq} (default: {\tt 500})}
alpar@9: \\
alpar@9: &Output frequency, in iterations. This parameter specifies how
alpar@9: frequently the solver sends information about the solution process to
alpar@9: the terminal.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int out\_dly} (default: {\tt 0})}
alpar@9: \\
alpar@9: &Output delay, in milliseconds. This parameter specifies how long the
alpar@9: solver should delay sending information about the solution process to
alpar@9: the terminal.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int presolve} (default: {\tt GLP\_OFF})}
alpar@9: \\
alpar@9: &LP presolver option:\\
alpar@9: &\verb|GLP_ON |---enable using the LP presolver;\\
alpar@9: &\verb|GLP_OFF|---disable using the LP presolver.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsubsection*{Example 1}
alpar@9: 
alpar@9: The following main program reads LP problem instance in fixed MPS
alpar@9: format from file \verb|25fv47.mps|,\footnote{This instance in fixed MPS
alpar@9: format can be found in the Netlib LP collection; see
alpar@9: {\tt ftp://ftp.netlib.org/lp/data/}.} constructs an advanced initial
alpar@9: basis, solves the instance with the primal simplex method (by default),
alpar@9: and writes the solution to file \verb|25fv47.txt|.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: /* spxsamp1.c */
alpar@9: 
alpar@9: #include <stdio.h>
alpar@9: #include <stdlib.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_prob *P;
alpar@9:       P = glp_create_prob();
alpar@9:       glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
alpar@9:       glp_adv_basis(P, 0);
alpar@9:       glp_simplex(P, NULL);
alpar@9:       glp_print_sol(P, "25fv47.txt");
alpar@9:       glp_delete_prob(P);
alpar@9:       return 0;
alpar@9: }
alpar@9: 
alpar@9: /* eof */
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \noindent
alpar@9: Below here is shown the terminal output from this example program.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Reading problem data from `25fv47.mps'...
alpar@9: Problem: 25FV47
alpar@9: Objective: R0000
alpar@9: 822 rows, 1571 columns, 11127 non-zeros
alpar@9: 6919 records were read
alpar@9: Crashing...
alpar@9: Size of triangular part = 799
alpar@9:       0: obj =   1.627307307e+04  infeas =  5.194e+04 (23)
alpar@9:     200: obj =   1.474901610e+04  infeas =  1.233e+04 (19)
alpar@9:     400: obj =   1.343909995e+04  infeas =  3.648e+03 (13)
alpar@9:     600: obj =   1.756052217e+04  infeas =  4.179e+02 (7)
alpar@9: *   775: obj =   1.789251591e+04  infeas =  4.982e-14 (1)
alpar@9: *   800: obj =   1.663354510e+04  infeas =  2.857e-14 (1)
alpar@9: *  1000: obj =   1.024935068e+04  infeas =  1.958e-12 (1)
alpar@9: *  1200: obj =   7.860174791e+03  infeas =  2.810e-29 (1)
alpar@9: *  1400: obj =   6.642378184e+03  infeas =  2.036e-16 (1)
alpar@9: *  1600: obj =   6.037014568e+03  infeas =  0.000e+00 (1)
alpar@9: *  1800: obj =   5.662171307e+03  infeas =  6.447e-15 (1)
alpar@9: *  2000: obj =   5.528146165e+03  infeas =  9.764e-13 (1)
alpar@9: *  2125: obj =   5.501845888e+03  infeas =  0.000e+00 (1)
alpar@9: OPTIMAL SOLUTION FOUND
alpar@9: Writing basic solution to `25fv47.txt'...
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsubsection*{Example 2}
alpar@9: 
alpar@9: The following main program solves the same LP problem instance as in
alpar@9: Example 1 above, however, it uses the dual simplex method, which starts
alpar@9: from the standard initial basis.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: /* spxsamp2.c */
alpar@9: 
alpar@9: #include <stdio.h>
alpar@9: #include <stdlib.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_prob *P;
alpar@9:       glp_smcp parm;
alpar@9:       P = glp_create_prob();
alpar@9:       glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
alpar@9:       glp_init_smcp(&parm);
alpar@9:       parm.meth = GLP_DUAL;
alpar@9:       glp_simplex(P, &parm);
alpar@9:       glp_print_sol(P, "25fv47.txt");
alpar@9:       glp_delete_prob(P);
alpar@9:       return 0;
alpar@9: }
alpar@9: 
alpar@9: /* eof */
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \noindent
alpar@9: Below here is shown the terminal output from this example program.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Reading problem data from `25fv47.mps'...
alpar@9: Problem: 25FV47
alpar@9: Objective: R0000
alpar@9: 822 rows, 1571 columns, 11127 non-zeros
alpar@9: 6919 records were read
alpar@9:       0:                          infeas =  1.223e+03 (516)
alpar@9:     200:                          infeas =  7.000e+00 (471)
alpar@9:     240:                          infeas =  1.106e-14 (461)
alpar@9: |   400: obj =  -5.394267152e+03  infeas =  5.571e-16 (391)
alpar@9: |   600: obj =  -4.586395752e+03  infeas =  1.389e-15 (340)
alpar@9: |   800: obj =  -4.158268146e+03  infeas =  1.640e-15 (264)
alpar@9: |  1000: obj =  -3.725320045e+03  infeas =  5.181e-15 (245)
alpar@9: |  1200: obj =  -3.104802163e+03  infeas =  1.019e-14 (210)
alpar@9: |  1400: obj =  -2.584190499e+03  infeas =  8.865e-15 (178)
alpar@9: |  1600: obj =  -2.073852927e+03  infeas =  7.867e-15 (142)
alpar@9: |  1800: obj =  -1.164037407e+03  infeas =  8.792e-15 (109)
alpar@9: |  2000: obj =  -4.370590250e+02  infeas =  2.591e-14 (85)
alpar@9: |  2200: obj =   1.068240144e+03  infeas =  1.025e-13 (70)
alpar@9: |  2400: obj =   1.607481126e+03  infeas =  3.272e-14 (67)
alpar@9: |  2600: obj =   3.038230551e+03  infeas =  4.850e-14 (52)
alpar@9: |  2800: obj =   4.316238187e+03  infeas =  2.622e-14 (36)
alpar@9: |  3000: obj =   5.443842629e+03  infeas =  3.976e-15 (11)
alpar@9: |  3060: obj =   5.501845888e+03  infeas =  8.806e-15 (2)
alpar@9: OPTIMAL SOLUTION FOUND
alpar@9: Writing basic solution to `25fv47.txt'...
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \subsection{glp\_exact---solve LP problem in exact arithmetic}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_exact(glp_prob *lp, const glp_smcp *parm);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_exact| is a tentative implementation of the
alpar@9: primal two-phase simplex method based on exact (rational) arithmetic.
alpar@9: It is similar to the routine \verb|glp_simplex|, however, for all
alpar@9: internal computations it uses arithmetic of rational numbers, which is
alpar@9: exact in mathematical sense, i.e. free of round-off errors unlike
alpar@9: floating-point arithmetic.
alpar@9: 
alpar@9: Note that the routine \verb|glp_exact| uses only two control parameters
alpar@9: passed in the structure \verb|glp_smcp|, namely, \verb|it_lim| and
alpar@9: \verb|tm_lim|.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: \def\arraystretch{1}
alpar@9: 
alpar@9: \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9: 0 & The LP problem instance has been successfully solved. (This code
alpar@9: does {\it not} necessarily mean that the solver has found optimal
alpar@9: solution. It only means that the solution process was successful.) \\
alpar@9: \verb|GLP_EBADB| & Unable to start the search, because the initial basis
alpar@9: specified in the problem object is invalid---the number of basic
alpar@9: (auxiliary and structural) variables is not the same as the number of
alpar@9: rows in the problem object.\\
alpar@9: \verb|GLP_ESING| & Unable to start the search, because the basis matrix
alpar@9: corresponding to the initial basis is exactly singular.\\
alpar@9: \verb|GLP_EBOUND| & Unable to start the search, because some
alpar@9: double-bounded (auxiliary or structural) variables have incorrect
alpar@9: bounds.\\
alpar@9: \verb|GLP_EFAIL| & The problem instance has no rows/columns.\\
alpar@9: \verb|GLP_EITLIM| & The search was prematurely terminated, because the
alpar@9: simplex iteration limit has been exceeded.\\
alpar@9: \verb|GLP_ETMLIM| & The search was prematurely terminated, because the
alpar@9: time limit has been exceeded.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsubsection*{Comments}
alpar@9: 
alpar@9: Computations in exact arithmetic are very time consuming, so solving
alpar@9: LP problem with the routine \verb|glp_exact| from the very beginning is
alpar@9: not a good idea. It is much better at first to find an optimal basis
alpar@9: with the routine \verb|glp_simplex| and only then to call
alpar@9: \verb|glp_exact|, in which case only a few simplex iterations need to
alpar@9: be performed in exact arithmetic.
alpar@9: 
alpar@9: \subsection{glp\_init\_smcp---initialize simplex solver control
alpar@9: parameters}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_init_smcp(glp_smcp *parm);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_init_smcp| initializes control parameters, which
alpar@9: are used by the simplex solver, with default values.
alpar@9: 
alpar@9: Default values of the control parameters are stored in a \verb|glp_smcp|
alpar@9: structure, which the parameter \verb|parm| points to.
alpar@9: 
alpar@9: \subsection{glp\_get\_status---determine generic status of basic
alpar@9: solution}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_status(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_status| reports the generic status of the
alpar@9: current basic solution for the specified problem object as follows:
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|GLP_OPT|    & solution is optimal; \\
alpar@9: \verb|GLP_FEAS|   & solution is feasible; \\
alpar@9: \verb|GLP_INFEAS| & solution is infeasible; \\
alpar@9: \verb|GLP_NOFEAS| & problem has no feasible solution; \\
alpar@9: \verb|GLP_UNBND|  & problem has unbounded solution; \\
alpar@9: \verb|GLP_UNDEF|  & solution is undefined. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: More detailed information about the status of basic solution can be
alpar@9: retrieved with the routines \verb|glp_get_prim_stat| and
alpar@9: \verb|glp_get_dual_stat|.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_get\_prim\_stat---retrieve status of primal basic
alpar@9: solution}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_prim_stat(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_prim_stat| reports the status of the primal
alpar@9: basic solution for the specified problem object as follows:
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|GLP_UNDEF|  & primal solution is undefined; \\
alpar@9: \verb|GLP_FEAS|   & primal solution is feasible; \\
alpar@9: \verb|GLP_INFEAS| & primal solution is infeasible; \\
alpar@9: \verb|GLP_NOFEAS| & no primal feasible solution exists. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsection{glp\_get\_dual\_stat---retrieve status of dual basic
alpar@9: solution}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_dual_stat(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_dual_stat| reports the status of the dual
alpar@9: basic solution for the specified problem object as follows:
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|GLP_UNDEF|  & dual solution is undefined; \\
alpar@9: \verb|GLP_FEAS|   & dual solution is feasible; \\
alpar@9: \verb|GLP_INFEAS| & dual solution is infeasible; \\
alpar@9: \verb|GLP_NOFEAS| & no dual feasible solution exists. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsection{glp\_get\_obj\_val---retrieve objective value}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_get_obj_val(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_obj_val| returns current value of the
alpar@9: objective function.
alpar@9: 
alpar@9: \subsection{glp\_get\_row\_stat---retrieve row status}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_row_stat(glp_prob *lp, int i);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_row_stat| returns current status assigned to
alpar@9: the auxiliary variable associated with \verb|i|-th row as follows:
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|GLP_BS| & basic variable; \\
alpar@9: \verb|GLP_NL| & non-basic variable on its lower bound; \\
alpar@9: \verb|GLP_NU| & non-basic variable on its upper bound; \\
alpar@9: \verb|GLP_NF| & non-basic free (unbounded) variable; \\
alpar@9: \verb|GLP_NS| & non-basic fixed variable. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsection{glp\_get\_row\_prim---retrieve row primal value}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_get_row_prim(glp_prob *lp, int i);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_row_prim| returns primal value of the
alpar@9: auxiliary variable associated with \verb|i|-th row.
alpar@9: 
alpar@9: \subsection{glp\_get\_row\_dual---retrieve row dual value}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_get_row_dual(glp_prob *lp, int i);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_row_dual| returns dual value (i.e. reduced
alpar@9: cost) of the auxiliary variable associated with \verb|i|-th row.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_get\_col\_stat---retrieve column status}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_col_stat(glp_prob *lp, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_col_stat| returns current status assigned to
alpar@9: the structural variable associated with \verb|j|-th column as follows:
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|GLP_BS| & basic variable; \\
alpar@9: \verb|GLP_NL| & non-basic variable on its lower bound; \\
alpar@9: \verb|GLP_NU| & non-basic variable on its upper bound; \\
alpar@9: \verb|GLP_NF| & non-basic free (unbounded) variable; \\
alpar@9: \verb|GLP_NS| & non-basic fixed variable. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsection{glp\_get\_col\_prim---retrieve column primal value}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_get_col_prim(glp_prob *lp, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_col_prim| returns primal value of the
alpar@9: structural variable associated with \verb|j|-th column.
alpar@9: 
alpar@9: \subsection{glp\_get\_col\_dual---retrieve column dual value}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_get_col_dual(glp_prob *lp, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_col_dual| returns dual value (i.e. reduced
alpar@9: cost) of the structural variable associated with \verb|j|-th column.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_get\_unbnd\_ray---determine variable causing\\
alpar@9: unboundedness}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_unbnd_ray(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_unbnd_ray| returns the number $k$ of
alpar@9: a variable, which causes primal or dual unboundedness.
alpar@9: If $1\leq k\leq m$, it is $k$-th auxiliary variable, and if
alpar@9: $m+1\leq k\leq m+n$, it is $(k-m)$-th structural variable, where $m$ is
alpar@9: the number of rows, $n$ is the number of columns in the problem object.
alpar@9: If such variable is not defined, the routine returns 0.
alpar@9: 
alpar@9: \subsubsection*{Comments}
alpar@9: 
alpar@9: If it is not exactly known which version of the simplex solver
alpar@9: detected unboundedness, i.e. whether the unboundedness is primal or
alpar@9: dual, it is sufficient to check the status of the variable
alpar@9: with the routine \verb|glp_get_row_stat| or \verb|glp_get_col_stat|.
alpar@9: If the variable is non-basic, the unboundedness is primal, otherwise,
alpar@9: if the variable is basic, the unboundedness is dual (the latter case
alpar@9: means that the problem has no primal feasible dolution).
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Interior-point method routines}
alpar@9: 
alpar@9: {\it Interior-point methods} (also known as {\it barrier methods}) are
alpar@9: more modern and powerful numerical methods for large-scale linear
alpar@9: programming. Such methods are especially efficient for very sparse LP
alpar@9: problems and allow solving such problems much faster than the simplex
alpar@9: method.
alpar@9: 
alpar@9: In brief, the GLPK interior-point solver works as follows.
alpar@9: 
alpar@9: At first, the solver transforms the original LP to a {\it working} LP
alpar@9: in the standard format:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: \hspace{.5in} minimize
alpar@9: $$z = c_1x_{m+1} + c_2x_{m+2} + \dots + c_nx_{m+n} + c_0 \eqno (2.4)$$
alpar@9: \hspace{.5in} subject to linear constraints
alpar@9: $$
alpar@9: \begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}l}
alpar@9: a_{11}x_{m+1}&+&a_{12}x_{m+2}&+ \dots +&a_{1n}x_{m+n}&=&b_1 \\
alpar@9: a_{21}x_{m+1}&+&a_{22}x_{m+2}&+ \dots +&a_{2n}x_{m+n}&=&b_2 \\
alpar@9: \multicolumn{7}{c}
alpar@9: {.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
alpar@9: a_{m1}x_{m+1}&+&a_{m2}x_{m+2}&+ \dots +&a_{mn}x_{m+n}&=&b_m \\
alpar@9: \end{array} \eqno (2.5)
alpar@9: $$
alpar@9: \hspace{.5in} and non-negative variables
alpar@9: $$x_1\geq 0,\ \ x_2\geq 0,\ \ \dots,\ \ x_n\geq 0 \eqno(2.6)$$
alpar@9: where: $z$ is the objective function; $x_1$, \dots, $x_n$ are variables;
alpar@9: $c_1$, \dots, $c_n$ are objective coefficients; $c_0$ is a constant term
alpar@9: of the objective function;\linebreak $a_{11}$, \dots, $a_{mn}$ are
alpar@9: constraint coefficients; $b_1$, \dots, $b_m$ are right-hand sides.
alpar@9: 
alpar@9: Using vector and matrix notations the working LP (2.4)---(2.6) can be
alpar@9: written as follows:
alpar@9: $$z=c^Tx+c_0\ \rightarrow\ \min,\eqno(2.7)$$
alpar@9: $$Ax=b,\eqno(2.8)$$
alpar@9: $$x\geq 0,\eqno(2.9)$$
alpar@9: where: $x=(x_j)$ is $n$-vector of variables, $c=(c_j)$ is $n$-vector of
alpar@9: objective coefficients, $A=(a_{ij})$ is $m\times n$-matrix of
alpar@9: constraint coefficients, and $b=(b_i)$ is $m$-vector of right-hand
alpar@9: sides.
alpar@9: 
alpar@9: Karush--Kuhn--Tucker optimality conditions for LP (2.7)---(2.9) are the
alpar@9: following:
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: $$Ax=b,\eqno(2.10)$$
alpar@9: $$A^T\pi+\lambda=c,\eqno(2.11)$$
alpar@9: $$\lambda^Tx=0,\eqno(2.12)$$
alpar@9: $$x\geq 0,\ \ \lambda\geq 0,\eqno(2.13)$$
alpar@9: where: $\pi$ is $m$-vector of Lagrange multipliers (dual variables) for
alpar@9: equality constraints (2.8), $\lambda$ is $n$-vector of Lagrange
alpar@9: multipliers (dual variables) for non-negativity constraints (2.9),
alpar@9: (2.10) is the primal feasibility condition, (2.11) is the dual
alpar@9: feasibility condition, (2.12) is the primal-dual complementarity
alpar@9: condition, and (2.13) is the non-negativity conditions.
alpar@9: 
alpar@9: The main idea of the primal-dual interior-point method is based on
alpar@9: finding a point in the primal-dual space (i.e. in the space of all
alpar@9: primal and dual variables $x$, $\pi$, and $\lambda$), which satisfies
alpar@9: to all optimality conditions (2.10)---(2.13). Obviously, $x$-component
alpar@9: of such point then provides an optimal solution to the working LP
alpar@9: (2.7)---(2.9).
alpar@9: 
alpar@9: To find the optimal point $(x^*,\pi^*,\lambda^*)$ the interior-point
alpar@9: method attempts to solve the system of equations (2.10)---(2.12), which
alpar@9: is closed in the sense that the number of variables $x_j$, $\pi_i$, and
alpar@9: $\lambda_j$ and the number equations are the same and equal to $m+2n$.
alpar@9: Due to condition (2.12) this system of equations is non-linear, so it
alpar@9: can be solved with a version of {\it Newton's method} provided with
alpar@9: additional rules to keep the current point within the positive orthant
alpar@9: as required by the non-negativity conditions (2.13).
alpar@9: 
alpar@9: Finally, once the optimal point $(x^*,\pi^*,\lambda^*)$ has been found,
alpar@9: the solver performs inverse transformations to recover corresponding
alpar@9: solution to the original LP passed to the solver from the application
alpar@9: program.
alpar@9: 
alpar@9: \subsection{glp\_interior---solve LP problem with the interior-point
alpar@9: method}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_interior(glp_prob *P, const glp_iptcp *parm);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_interior| is a driver to the LP solver based on
alpar@9: the primal-dual interior-point method. This routine retrieves problem
alpar@9: data from the specified problem object, calls the solver to solve the
alpar@9: problem instance, and stores results of computations back into the
alpar@9: problem object.
alpar@9: 
alpar@9: The interior-point solver has a set of control parameters. Values of
alpar@9: the control parameters can be passed in the structure \verb|glp_iptcp|,
alpar@9: which the parameter \verb|parm| points to. For detailed description of
alpar@9: this structure see paragraph ``Control parameters'' below. Before
alpar@9: specifying some control parameters the application program should
alpar@9: initialize the structure \verb|glp_iptcp| by default values of all
alpar@9: control parameters using the routine \verb|glp_init_iptcp| (see the
alpar@9: next subsection). This is needed for backward compatibility, because in
alpar@9: the future there may appear new members in the structure
alpar@9: \verb|glp_iptcp|.
alpar@9: 
alpar@9: The parameter \verb|parm| can be specified as \verb|NULL|, in which
alpar@9: case the solver uses default settings.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: \def\arraystretch{1}
alpar@9: 
alpar@9: \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9: 0 & The LP problem instance has been successfully solved. (This code
alpar@9: does {\it not} necessarily mean that the solver has found optimal
alpar@9: solution. It only means that the solution process was successful.) \\
alpar@9: \verb|GLP_EFAIL| & The problem has no rows/columns.\\
alpar@9: \verb|GLP_ENOCVG| & Very slow convergence or divergence.\\
alpar@9: \verb|GLP_EITLIM| & Iteration limit exceeded.\\
alpar@9: \verb|GLP_EINSTAB| & Numerical instability on solving Newtonian
alpar@9: system.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsubsection*{Comments}
alpar@9: 
alpar@9: The routine \verb|glp_interior| implements an easy version of
alpar@9: the primal-dual interior-point method based on Mehrotra's
alpar@9: technique.\footnote{S. Mehrotra. On the implementation of a primal-dual
alpar@9: interior point method. SIAM J. on Optim., 2(4), pp. 575-601, 1992.}
alpar@9: 
alpar@9: Note that currently the GLPK interior-point solver does not include
alpar@9: many important features, in particular:
alpar@9: 
alpar@9: $\bullet$ it is not able to process dense columns. Thus, if the
alpar@9: constraint matrix of the LP problem has dense columns, the solving
alpar@9: process may be inefficient;
alpar@9: 
alpar@9: $\bullet$ it has no features against numerical instability. For some
alpar@9: LP problems premature termination may happen if the matrix $ADA^T$
alpar@9: becomes singular or ill-conditioned;
alpar@9: 
alpar@9: $\bullet$ it is not able to identify the optimal basis, which
alpar@9: corresponds to the interior-point solution found.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsubsection*{Terminal output}
alpar@9: 
alpar@9: Solving large LP problems may take a long time, so the solver reports
alpar@9: some information about every interior-point iteration,\footnote{Unlike
alpar@9: the simplex method the interior point method usually needs 30---50
alpar@9: iterations (independently on the problem size) in order to find an
alpar@9: optimal solution.} which is sent to the terminal. This information has
alpar@9: the following format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: nnn: obj = fff; rpi = ppp; rdi = ddd; gap = ggg
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent where: \verb|nnn| is iteration number, \verb|fff| is the
alpar@9: current value of the objective function (in the case of maximization it
alpar@9: has wrong sign), \verb|ppp| is the current relative primal
alpar@9: infeasibility (cf. (2.10)):
alpar@9: $$\frac{\|Ax^{(k)}-b\|}{1+\|b\|},\eqno(2.14)$$
alpar@9: \verb|ddd| is the current relative dual infeasibility (cf. (2.11)):
alpar@9: $$\frac{\|A^T\pi^{(k)}+\lambda^{(k)}-c\|}{1+\|c\|},\eqno(2.15)$$
alpar@9: \verb|ggg| is the current primal-dual gap (cf. (2.12)):
alpar@9: $$\frac{|c^Tx^{(k)}-b^T\pi^{(k)}|}{1+|c^Tx^{(k)}|},\eqno(2.16)$$
alpar@9: and $[x^{(k)},\pi^{(k)},\lambda^{(k)}]$ is the current point on $k$-th
alpar@9: iteration, $k=0,1,2,\dots$\ . Note that all solution components are
alpar@9: internally scaled, so information sent to the terminal is suitable only
alpar@9: for visual inspection.
alpar@9: 
alpar@9: \subsubsection*{Control parameters}
alpar@9: 
alpar@9: This paragraph describes all control parameters currently used in the
alpar@9: interior-point solver. Symbolic names of control parameters are names of
alpar@9: corresponding members in the structure \verb|glp_iptcp|.
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
alpar@9: \\
alpar@9: &Message level for terminal output:\\
alpar@9: &\verb|GLP_MSG_OFF|---no output;\\
alpar@9: &\verb|GLP_MSG_ERR|---error and warning messages only;\\
alpar@9: &\verb|GLP_MSG_ON |---normal output;\\
alpar@9: &\verb|GLP_MSG_ALL|---full output (including informational messages).
alpar@9: \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int ord\_alg} (default: {\tt GLP\_ORD\_AMD})}
alpar@9: \\
alpar@9: &Ordering algorithm used prior to Cholesky factorization:\\
alpar@9: &\verb|GLP_ORD_NONE  |---use natural (original) ordering;\\
alpar@9: &\verb|GLP_ORD_QMD   |---quotient minimum degree (QMD);\\
alpar@9: &\verb|GLP_ORD_AMD   |---approximate minimum degree (AMD);\\
alpar@9: &\verb|GLP_ORD_SYMAMD|---approximate minimum degree (SYMAMD).\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: The following main program reads LP problem instance in fixed MPS
alpar@9: format from file \verb|25fv47.mps|,\footnote{This instance in fixed MPS
alpar@9: format can be found in the Netlib LP collection; see
alpar@9: {\tt ftp://ftp.netlib.org/lp/data/}.} solves it with the interior-point
alpar@9: solver, and writes the solution to file \verb|25fv47.txt|.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: /* iptsamp.c */
alpar@9: 
alpar@9: #include <stdio.h>
alpar@9: #include <stdlib.h>
alpar@9: #include <glpk.h>
alpar@9: 
alpar@9: int main(void)
alpar@9: {     glp_prob *P;
alpar@9:       P = glp_create_prob();
alpar@9:       glp_read_mps(P, GLP_MPS_DECK, NULL, "25fv47.mps");
alpar@9:       glp_interior(P, NULL);
alpar@9:       glp_print_ipt(P, "25fv47.txt");
alpar@9:       glp_delete_prob(P);
alpar@9:       return 0;
alpar@9: }
alpar@9: 
alpar@9: /* eof */
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \noindent
alpar@9: Below here is shown the terminal output from this example program.
alpar@9: 
alpar@9: \begin{footnotesize}
alpar@9: \begin{verbatim}
alpar@9: Reading problem data from `25fv47.mps'...
alpar@9: Problem: 25FV47
alpar@9: Objective: R0000
alpar@9: 822 rows, 1571 columns, 11127 non-zeros
alpar@9: 6919 records were read
alpar@9: Original LP has 822 row(s), 1571 column(s), and 11127 non-zero(s)
alpar@9: Working LP has 821 row(s), 1876 column(s), and 10705 non-zero(s)
alpar@9: Matrix A has 10705 non-zeros
alpar@9: Matrix S = A*A' has 11895 non-zeros (upper triangle)
alpar@9: Minimal degree ordering...
alpar@9: Computing Cholesky factorization S = L'*L...
alpar@9: Matrix L has 35411 non-zeros
alpar@9: Guessing initial point...
alpar@9: Optimization begins...
alpar@9:   0: obj =   1.823377629e+05; rpi =  1.3e+01; rdi =  1.4e+01; gap =  9.3e-01
alpar@9:   1: obj =   9.260045192e+04; rpi =  5.3e+00; rdi =  5.6e+00; gap =  6.8e+00
alpar@9:   2: obj =   3.596999742e+04; rpi =  1.5e+00; rdi =  1.2e+00; gap =  1.8e+01
alpar@9:   3: obj =   1.989627568e+04; rpi =  4.7e-01; rdi =  3.0e-01; gap =  1.9e+01
alpar@9:   4: obj =   1.430215557e+04; rpi =  1.1e-01; rdi =  8.6e-02; gap =  1.4e+01
alpar@9:   5: obj =   1.155716505e+04; rpi =  2.3e-02; rdi =  2.4e-02; gap =  6.8e+00
alpar@9:   6: obj =   9.660273208e+03; rpi =  6.7e-03; rdi =  4.6e-03; gap =  3.9e+00
alpar@9:   7: obj =   8.694348283e+03; rpi =  3.7e-03; rdi =  1.7e-03; gap =  2.0e+00
alpar@9:   8: obj =   8.019543639e+03; rpi =  2.4e-03; rdi =  3.9e-04; gap =  1.0e+00
alpar@9:   9: obj =   7.122676293e+03; rpi =  1.2e-03; rdi =  1.5e-04; gap =  6.6e-01
alpar@9:  10: obj =   6.514534518e+03; rpi =  6.1e-04; rdi =  4.3e-05; gap =  4.1e-01
alpar@9:  11: obj =   6.361572203e+03; rpi =  4.8e-04; rdi =  2.2e-05; gap =  3.0e-01
alpar@9:  12: obj =   6.203355508e+03; rpi =  3.2e-04; rdi =  1.7e-05; gap =  2.6e-01
alpar@9:  13: obj =   6.032943411e+03; rpi =  2.0e-04; rdi =  9.3e-06; gap =  2.1e-01
alpar@9:  14: obj =   5.796553021e+03; rpi =  9.8e-05; rdi =  3.2e-06; gap =  1.0e-01
alpar@9:  15: obj =   5.667032431e+03; rpi =  4.4e-05; rdi =  1.1e-06; gap =  5.6e-02
alpar@9:  16: obj =   5.613911867e+03; rpi =  2.5e-05; rdi =  4.1e-07; gap =  3.5e-02
alpar@9:  17: obj =   5.560572626e+03; rpi =  9.9e-06; rdi =  2.3e-07; gap =  2.1e-02
alpar@9:  18: obj =   5.537276001e+03; rpi =  5.5e-06; rdi =  8.4e-08; gap =  1.1e-02
alpar@9:  19: obj =   5.522746942e+03; rpi =  2.2e-06; rdi =  4.0e-08; gap =  6.7e-03
alpar@9:  20: obj =   5.509956679e+03; rpi =  7.5e-07; rdi =  1.8e-08; gap =  2.9e-03
alpar@9:  21: obj =   5.504571733e+03; rpi =  1.6e-07; rdi =  5.8e-09; gap =  1.1e-03
alpar@9:  22: obj =   5.502576367e+03; rpi =  3.4e-08; rdi =  1.0e-09; gap =  2.5e-04
alpar@9:  23: obj =   5.502057119e+03; rpi =  8.1e-09; rdi =  3.0e-10; gap =  7.7e-05
alpar@9:  24: obj =   5.501885996e+03; rpi =  9.4e-10; rdi =  1.2e-10; gap =  2.4e-05
alpar@9:  25: obj =   5.501852464e+03; rpi =  1.4e-10; rdi =  1.2e-11; gap =  3.0e-06
alpar@9:  26: obj =   5.501846549e+03; rpi =  1.4e-11; rdi =  1.2e-12; gap =  3.0e-07
alpar@9:  27: obj =   5.501845954e+03; rpi =  1.4e-12; rdi =  1.2e-13; gap =  3.0e-08
alpar@9:  28: obj =   5.501845895e+03; rpi =  1.5e-13; rdi =  1.2e-14; gap =  3.0e-09
alpar@9: OPTIMAL SOLUTION FOUND
alpar@9: Writing interior-point solution to `25fv47.txt'...
alpar@9: \end{verbatim}
alpar@9: \end{footnotesize}
alpar@9: 
alpar@9: \subsection{glp\_init\_iptcp---initialize interior-point solver control
alpar@9: parameters}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_init_iptcp(glp_iptcp *parm);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_init_iptcp| initializes control parameters, which
alpar@9: are used by the interior-point solver, with default values.
alpar@9: 
alpar@9: Default values of the control parameters are stored in the structure
alpar@9: \verb|glp_iptcp|, which the parameter \verb|parm| points to.
alpar@9: 
alpar@9: \subsection{glp\_ipt\_status---determine solution status}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_ipt_status(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ipt_status| reports the status of a solution
alpar@9: found by the interior-point solver as follows:
alpar@9: 
alpar@9: \begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
alpar@9: \verb|GLP_UNDEF| & interior-point solution is undefined. \\
alpar@9: \verb|GLP_OPT|   & interior-point solution is optimal. \\
alpar@9: \verb|GLP_INFEAS|& interior-point solution is infeasible. \\
alpar@9: \verb|GLP_NOFEAS|& no feasible primal-dual solution exists.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsection{glp\_ipt\_obj\_val---retrieve objective value}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_ipt_obj_val(glp_prob *lp);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ipt_obj_val| returns value of the objective
alpar@9: function for interior-point solution.
alpar@9: 
alpar@9: \subsection{glp\_ipt\_row\_prim---retrieve row primal value}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_ipt_row_prim(glp_prob *lp, int i);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ipt_row_prim| returns primal value of the
alpar@9: auxiliary variable associated with \verb|i|-th row.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_ipt\_row\_dual---retrieve row dual value}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_ipt_row_dual(glp_prob *lp, int i);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ipt_row_dual| returns dual value (i.e. reduced
alpar@9: cost) of the auxiliary variable associated with \verb|i|-th row.
alpar@9: 
alpar@9: \subsection{glp\_ipt\_col\_prim---retrieve column primal value}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_ipt_col_prim(glp_prob *lp, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ipt_col_prim| returns primal value of the
alpar@9: structural variable associated with \verb|j|-th column.
alpar@9: 
alpar@9: \subsection{glp\_ipt\_col\_dual---retrieve column dual value}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_ipt_col_dual(glp_prob *lp, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ipt_col_dual| returns dual value (i.e. reduced
alpar@9: cost) of the structural variable associated with \verb|j|-th column.
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Mixed integer programming routines}
alpar@9: 
alpar@9: \subsection{glp\_set\_col\_kind---set (change) column kind}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_set_col_kind(glp_prob *mip, int j, int kind);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_set_col_kind| sets (changes) the kind of
alpar@9: \verb|j|-th column (structural variable) as specified by the parameter
alpar@9: \verb|kind|:
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|GLP_CV| & continuous variable; \\
alpar@9: \verb|GLP_IV| & integer variable; \\
alpar@9: \verb|GLP_BV| & binary variable. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: %If a column is set to \verb|GLP_IV|, its bounds must be exact integer
alpar@9: %numbers with no tolerance, such that the condition
alpar@9: %\verb|bnd == floor(bnd)| would hold.
alpar@9: 
alpar@9: Setting a column to \verb|GLP_BV| has the same effect as if it were
alpar@9: set to \verb|GLP_IV|, its lower bound were set 0, and its upper bound
alpar@9: were set to 1.
alpar@9: 
alpar@9: \subsection{glp\_get\_col\_kind---retrieve column kind}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_col_kind(glp_prob *mip, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_col_kind| returns the kind of \verb|j|-th
alpar@9: column (structural variable) as follows:
alpar@9: 
alpar@9: \begin{tabular}{@{}ll}
alpar@9: \verb|GLP_CV| & continuous variable; \\
alpar@9: \verb|GLP_IV| & integer variable; \\
alpar@9: \verb|GLP_BV| & binary variable. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsection{glp\_get\_num\_int---retrieve number of integer columns}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_num_int(glp_prob *mip);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_num_int| returns the number of columns
alpar@9: (structural variables), which are marked as integer. Note that this
alpar@9: number {\it does} include binary columns.
alpar@9: 
alpar@9: \subsection{glp\_get\_num\_bin---retrieve number of binary columns}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_get_num_bin(glp_prob *mip);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_get_num_bin| returns the number of columns
alpar@9: (structural variables), which are marked as integer and whose lower
alpar@9: bound is zero and upper bound is one.
alpar@9: 
alpar@9: \subsection{glp\_intopt---solve MIP problem with the branch-and-cut
alpar@9: method}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_intopt(glp_prob *mip, const glp_iocp *parm);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_intopt| is a driver to the MIP solver based on
alpar@9: the branch-and-cut method, which is a hybrid of branch-and-bound and
alpar@9: cutting plane methods.
alpar@9: 
alpar@9: If the presolver is disabled (see paragraph ``Control parameters''
alpar@9: below), on entry to the routine \verb|glp_intopt| the problem object,
alpar@9: which the parameter \verb|mip| points to, should contain optimal
alpar@9: solution to LP relaxation (it can be obtained, for example, with the
alpar@9: routine \verb|glp_simplex|). Otherwise, if the presolver is enabled, it
alpar@9: is not necessary.
alpar@9: 
alpar@9: The MIP solver has a set of control parameters. Values of the control
alpar@9: parameters can be passed in the structure \verb|glp_iocp|, which the
alpar@9: parameter \verb|parm| points to. For detailed description of this
alpar@9: structure see paragraph ``Control parameters'' below. Before specifying
alpar@9: some control parameters the application program should initialize the
alpar@9: structure \verb|glp_iocp| by default values of all control parameters
alpar@9: using the routine \verb|glp_init_iocp| (see the next subsection). This
alpar@9: is needed for backward compatibility, because in the future there may
alpar@9: appear new members in the structure \verb|glp_iocp|.
alpar@9: 
alpar@9: The parameter \verb|parm| can be specified as \verb|NULL|, in which case
alpar@9: the solver uses default settings.
alpar@9: 
alpar@9: Note that the GLPK branch-and-cut solver is not perfect, so it is unable
alpar@9: to solve hard or very large scale MIP instances for a reasonable time.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: \def\arraystretch{1}
alpar@9: 
alpar@9: \begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
alpar@9: 0 & The MIP problem instance has been successfully solved. (This code
alpar@9: does {\it not} necessarily mean that the solver has found optimal
alpar@9: solution. It only means that the solution process was successful.) \\
alpar@9: \verb|GLP_EBOUND| & Unable to start the search, because some
alpar@9: double-bounded variables have incorrect bounds or some integer variables
alpar@9: have non-integer (fractional) bounds.\\
alpar@9: \verb|GLP_EROOT| & Unable to start the search, because optimal basis for
alpar@9: initial LP relaxation is not provided. (This code may appear only if the
alpar@9: presolver is disabled.)\\
alpar@9: \verb|GLP_ENOPFS| & Unable to start the search, because LP relaxation
alpar@9: of the MIP problem instance has no primal feasible solution. (This code
alpar@9: may appear only if the presolver is enabled.)\\
alpar@9: \verb|GLP_ENODFS| & Unable to start the search, because LP relaxation
alpar@9: of the MIP problem instance has no dual feasible solution. In other
alpar@9: word, this code means that if the LP relaxation has at least one primal
alpar@9: feasible solution, its optimal solution is unbounded, so if the MIP
alpar@9: problem has at least one integer feasible solution, its (integer)
alpar@9: optimal solution is also unbounded. (This code may appear only if the
alpar@9: presolver is enabled.)\\
alpar@9: \verb|GLP_EFAIL| & The search was prematurely terminated due to the
alpar@9: solver failure.\\
alpar@9: \verb|GLP_EMIPGAP| & The search was prematurely terminated, because the
alpar@9: relative mip gap tolerance has been reached.\\
alpar@9: \verb|GLP_ETMLIM| & The search was prematurely terminated, because the
alpar@9: time limit has been exceeded.\\
alpar@9: \verb|GLP_ESTOP| & The search was prematurely terminated by application.
alpar@9: (This code may appear only if the advanced solver interface is used.)\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsubsection*{Built-in MIP presolver}
alpar@9: 
alpar@9: The branch-and-cut solver has {\it built-in MIP presolver}. It is
alpar@9: a subprogram that transforms the original MIP problem specified in the
alpar@9: problem object to an equivalent MIP problem, which may be easier for
alpar@9: solving with the branch-and-cut method than the original one. For
alpar@9: example, the presolver can remove redundant constraints and variables,
alpar@9: whose optimal values are known, perform bound and coefficient reduction,
alpar@9: etc. Once the transformed MIP problem has been solved, the presolver
alpar@9: transforms its solution back to corresponding solution of the original
alpar@9: problem.
alpar@9: 
alpar@9: Presolving is an optional feature of the routine \verb|glp_intopt|, and
alpar@9: by default it is disabled. In order to enable the MIP presolver, the
alpar@9: control parameter \verb|presolve| should be set to \verb|GLP_ON| (see
alpar@9: paragraph ``Control parameters'' below).
alpar@9: 
alpar@9: \subsubsection*{Advanced solver interface}
alpar@9: 
alpar@9: The routine \verb|glp_intopt| allows the user to control the
alpar@9: branch-and-cut search by passing to the solver a user-defined callback
alpar@9: routine. For more details see Chapter ``Branch-and-Cut API Routines''.
alpar@9: 
alpar@9: \subsubsection*{Terminal output}
alpar@9: 
alpar@9: Solving a MIP problem may take a long time, so the solver reports some
alpar@9: information about best known solutions, which is sent to the terminal.
alpar@9: This information has the following format:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: +nnn: mip = xxx <rho> yyy gap (ppp; qqq)
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: where: `\verb|nnn|' is the simplex iteration number; `\verb|xxx|' is a
alpar@9: value of the objective function for the best known integer feasible
alpar@9: solution (if no integer feasible solution has been found yet,
alpar@9: `\verb|xxx|' is the text `\verb|not found yet|'); `\verb|rho|' is the
alpar@9: string `\verb|>=|' (in case of minimization) or `\verb|<=|' (in case of
alpar@9: maximization); `\verb|yyy|' is a global bound for exact integer optimum
alpar@9: (i.e. the exact integer optimum is always in the range from `\verb|xxx|'
alpar@9: to `\verb|yyy|'); `\verb|gap|' is the relative mip gap, in percents,
alpar@9: computed as $gap=|xxx-yyy|/(|xxx|+{\tt DBL\_EPSILON})\cdot 100\%$ (if
alpar@9: $gap$ is greater than $999.9\%$, it is not printed); `\verb|ppp|' is the
alpar@9: number of subproblems in the active list, `\verb|qqq|' is the number of
alpar@9: subproblems which have been already fathomed and therefore removed from
alpar@9: the branch-and-bound search tree.
alpar@9: 
alpar@9: \subsubsection{Control parameters}
alpar@9: 
alpar@9: This paragraph describes all control parameters currently used in the
alpar@9: MIP solver. Symbolic names of control parameters are names of
alpar@9: corresponding members in the structure \verb|glp_iocp|.
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
alpar@9: \\
alpar@9: &Message level for terminal output:\\
alpar@9: &\verb|GLP_MSG_OFF|---no output;\\
alpar@9: &\verb|GLP_MSG_ERR|---error and warning messages only;\\
alpar@9: &\verb|GLP_MSG_ON |---normal output;\\
alpar@9: &\verb|GLP_MSG_ALL|---full output (including informational messages).
alpar@9: \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int br\_tech} (default: {\tt GLP\_BR\_DTH})}
alpar@9: \\
alpar@9: &Branching technique option:\\
alpar@9: &\verb|GLP_BR_FFV|---first fractional variable;\\
alpar@9: &\verb|GLP_BR_LFV|---last fractional variable;\\
alpar@9: &\verb|GLP_BR_MFV|---most fractional variable;\\
alpar@9: &\verb|GLP_BR_DTH|---heuristic by Driebeck and Tomlin;\\
alpar@9: &\verb|GLP_BR_PCH|---hybrid pseudocost heuristic.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int bt\_tech} (default: {\tt GLP\_BT\_BLB})}
alpar@9: \\
alpar@9: &Backtracking technique option:\\
alpar@9: &\verb|GLP_BT_DFS|---depth first search;\\
alpar@9: &\verb|GLP_BT_BFS|---breadth first search;\\
alpar@9: &\verb|GLP_BT_BLB|---best local bound;\\
alpar@9: &\verb|GLP_BT_BPH|---best projection heuristic.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int pp\_tech} (default: {\tt GLP\_PP\_ALL})}
alpar@9: \\
alpar@9: &Preprocessing technique option:\\
alpar@9: &\verb|GLP_PP_NONE|---disable preprocessing;\\
alpar@9: &\verb|GLP_PP_ROOT|---perform preprocessing only on the root level;\\
alpar@9: &\verb|GLP_PP_ALL |---perform preprocessing on all levels.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int fp\_heur} (default: {\tt GLP\_OFF})}
alpar@9: \\
alpar@9: &Feasibility pump heuristic option:\\
alpar@9: &\verb|GLP_ON |---enable applying the feasibility pump heuristic;\\
alpar@9: &\verb|GLP_OFF|---disable applying the feasibility pump heuristic.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int gmi\_cuts} (default: {\tt GLP\_OFF})}\\
alpar@9: &Gomory's mixed integer cut option:\\
alpar@9: &\verb|GLP_ON |---enable generating Gomory's cuts;\\
alpar@9: &\verb|GLP_OFF|---disable generating Gomory's cuts.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int mir\_cuts} (default: {\tt GLP\_OFF})}\\
alpar@9: &Mixed integer rounding (MIR) cut option:\\
alpar@9: &\verb|GLP_ON |---enable generating MIR cuts;\\
alpar@9: &\verb|GLP_OFF|---disable generating MIR cuts.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int cov\_cuts} (default: {\tt GLP\_OFF})}\\
alpar@9: &Mixed cover cut option:\\
alpar@9: &\verb|GLP_ON |---enable generating mixed cover cuts;\\
alpar@9: &\verb|GLP_OFF|---disable generating mixed cover cuts.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int clq\_cuts} (default: {\tt GLP\_OFF})}\\
alpar@9: &Clique cut option:\\
alpar@9: &\verb|GLP_ON |---enable generating clique cuts;\\
alpar@9: &\verb|GLP_OFF|---disable generating clique cuts.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt double tol\_int} (default: {\tt 1e-5})}\\
alpar@9: &Absolute tolerance used to check if optimal solution to the current LP
alpar@9: relaxation is integer feasible. (Do not change this parameter without
alpar@9: detailed understanding its purpose.)\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt double tol\_obj} (default: {\tt 1e-7})}\\
alpar@9: &Relative tolerance used to check if the objective value in optimal
alpar@9: solution to the current LP relaxation is not better than in the best
alpar@9: known integer feasible solution. (Do not change this parameter without
alpar@9: detailed understanding its purpose.)\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt double mip\_gap} (default: {\tt 0.0})}\\
alpar@9: &The relative mip gap tolerance. If the relative mip gap for currently
alpar@9: known best integer feasible solution falls below this tolerance, the
alpar@9: solver terminates the search. This allows obtainig suboptimal integer
alpar@9: feasible solutions if solving the problem to optimality takes too long
alpar@9: time.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int tm\_lim} (default: {\tt INT\_MAX})}\\
alpar@9: &Searching time limit, in milliseconds.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int out\_frq} (default: {\tt 5000})}\\
alpar@9: &Output frequency, in milliseconds. This parameter specifies how
alpar@9: frequently the solver sends information about the solution process to
alpar@9: the terminal.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int out\_dly} (default: {\tt 10000})}\\
alpar@9: &Output delay, in milliseconds. This parameter specifies how long the
alpar@9: solver should delay sending information about solution of the current
alpar@9: LP relaxation with the simplex method to the terminal.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}
alpar@9: {{\tt void (*cb\_func)(glp\_tree *tree, void *info)}
alpar@9: (default: {\tt NULL})}\\
alpar@9: &Entry point to the user-defined callback routine. \verb|NULL| means
alpar@9: the advanced solver interface is not used. For more details see Chapter
alpar@9: ``Branch-and-Cut API Routines''.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt void *cb\_info} (default: {\tt NULL})}\\
alpar@9: &Transit pointer passed to the routine \verb|cb_func| (see above).\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int cb\_size} (default: {\tt 0})}\\
alpar@9: &The number of extra (up to 256) bytes allocated for each node of the
alpar@9: branch-and-bound tree to store application-specific data. On creating
alpar@9: a node these bytes are initialized by binary zeros.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int presolve} (default: {\tt GLP\_OFF})}\\
alpar@9: &MIP presolver option:\\
alpar@9: &\verb|GLP_ON |---enable using the MIP presolver;\\
alpar@9: &\verb|GLP_OFF|---disable using the MIP presolver.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int binarize} (default: {\tt GLP\_OFF})}\\
alpar@9: &Binarization option (used only if the presolver is enabled):\\
alpar@9: &\verb|GLP_ON |---replace general integer variables by binary ones;\\
alpar@9: &\verb|GLP_OFF|---do not use binarization.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsection{glp\_init\_iocp---initialize integer optimizer control
alpar@9: parameters}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_init_iocp(glp_iocp *parm);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_init_iocp| initializes control parameters, which
alpar@9: are used by the branch-and-cut solver, with default values.
alpar@9: 
alpar@9: Default values of the control parameters are stored in a \verb|glp_iocp|
alpar@9: structure, which the parameter \verb|parm| points to.
alpar@9: 
alpar@9: \subsection{glp\_mip\_status---determine status of MIP solution}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_mip_status(glp_prob *mip);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_mip_status| reports the status of a MIP solution
alpar@9: found by the MIP solver as follows:
alpar@9: 
alpar@9: \smallskip
alpar@9: 
alpar@9: \begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
alpar@9: \verb|GLP_UNDEF| & MIP solution is undefined. \\
alpar@9: \verb|GLP_OPT|   & MIP solution is integer optimal. \\
alpar@9: \verb|GLP_FEAS|  & MIP solution is integer feasible, however, its
alpar@9:    optimality (or non-optimality) has not been proven, perhaps due to
alpar@9:    premature termination of the search. \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
alpar@9: \verb|GLP_NOFEAS| & problem has no integer feasible solution (proven by
alpar@9:    the solver). \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \subsection{glp\_mip\_obj\_val---retrieve objective value}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_mip_obj_val(glp_prob *mip);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_mip_obj_val| returns value of the objective
alpar@9: function for MIP solution.
alpar@9: 
alpar@9: \subsection{glp\_mip\_row\_val---retrieve row value}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_mip_row_val(glp_prob *mip, int i);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_mip_row_val| returns value of the auxiliary
alpar@9: variable associated with \verb|i|-th row for MIP solution.
alpar@9: 
alpar@9: \subsection{glp\_mip\_col\_val---retrieve column value}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_mip_col_val(glp_prob *mip, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_mip_col_val| returns value of the structural
alpar@9: variable associated with \verb|j|-th column for MIP solution.
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Additional routines}
alpar@9: 
alpar@9: \subsection{lpx\_check\_kkt---check Karush-Kuhn-Tucker optimality
alpar@9: conditions}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void lpx_check_kkt(glp_prob *lp, int scaled, LPXKKT *kkt);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|lpx_check_kkt| checks Karush-Kuhn-Tucker optimality
alpar@9: conditions for basic solution. It is assumed that both primal and dual
alpar@9: components of basic solution are valid.
alpar@9: 
alpar@9: If the parameter \verb|scaled| is zero, the optimality conditions are
alpar@9: checked for the original, unscaled LP problem. Otherwise, if the
alpar@9: parameter \verb|scaled| is non-zero, the routine checks the conditions
alpar@9: for an internally scaled LP problem.
alpar@9: 
alpar@9: The parameter \verb|kkt| is a pointer to the structure \verb|LPXKKT|,
alpar@9: to which the routine stores results of the check. Members of this
alpar@9: structure are shown in the table below.
alpar@9: 
alpar@9: \begin{table}[h]
alpar@9: \begin{center}
alpar@9: \begin{tabular}{@{}c|l|l@{}}
alpar@9: Condition & Member & Comment \\
alpar@9: \hline
alpar@9: (KKT.PE) & \verb|pe_ae_max| &
alpar@9:          Largest absolute error \\
alpar@9:          & \verb|pe_ae_row| &
alpar@9:          Number of row with largest absolute error \\
alpar@9:          & \verb|pe_re_max| &
alpar@9:          Largest relative error \\
alpar@9:          & \verb|pe_re_row| &
alpar@9:          Number of row with largest relative error \\
alpar@9:          & \verb|pe_quality| &
alpar@9:          Quality of primal solution \\
alpar@9: \hline
alpar@9: (KKT.PB) & \verb|pb_ae_max| &
alpar@9:          Largest absolute error \\
alpar@9:          & \verb|pb_ae_ind| &
alpar@9:          Number of variable with largest absolute error \\
alpar@9:          & \verb|pb_re_max| &
alpar@9:          Largest relative error \\
alpar@9:          & \verb|pb_re_ind| &
alpar@9:          Number of variable with largest relative error \\
alpar@9:          & \verb|pb_quality| &
alpar@9:          Quality of primal feasibility \\
alpar@9: \hline
alpar@9: (KKT.DE) & \verb|de_ae_max| &
alpar@9:          Largest absolute error \\
alpar@9:          & \verb|de_ae_col| &
alpar@9:          Number of column with largest absolute error \\
alpar@9:          & \verb|de_re_max| &
alpar@9:          Largest relative error \\
alpar@9:          & \verb|de_re_col| &
alpar@9:          Number of column with largest relative error \\
alpar@9:          & \verb|de_quality| &
alpar@9:          Quality of dual solution \\
alpar@9: \hline
alpar@9: (KKT.DB) & \verb|db_ae_max| &
alpar@9:          Largest absolute error \\
alpar@9:          & \verb|db_ae_ind| &
alpar@9:          Number of variable with largest absolute error \\
alpar@9:          & \verb|db_re_max| &
alpar@9:          Largest relative error \\
alpar@9:          & \verb|db_re_ind| &
alpar@9:          Number of variable with largest relative error \\
alpar@9:          & \verb|db_quality| &
alpar@9:          Quality of dual feasibility \\
alpar@9: \end{tabular}
alpar@9: \end{center}
alpar@9: \end{table}
alpar@9: 
alpar@9: The routine performs all computations using only components of the
alpar@9: given LP problem and the current basic solution.
alpar@9: 
alpar@9: \subsubsection*{Background}
alpar@9: 
alpar@9: The first condition checked by the routine is:
alpar@9: $$x_R - A x_S = 0, \eqno{\rm (KKT.PE)}$$
alpar@9: where $x_R$ is the subvector of auxiliary variables (rows), $x_S$ is the
alpar@9: subvector of structural variables (columns), $A$ is the constraint
alpar@9: matrix. This condition expresses the requirement that all primal
alpar@9: variables must satisfy to the system of equality constraints of the
alpar@9: original LP problem. In case of exact arithmetic this condition would be
alpar@9: satisfied for any basic solution; however, in case of inexact
alpar@9: (floating-point) arithmetic, this condition shows how accurate the
alpar@9: primal basic solution is, that depends on accuracy of a representation
alpar@9: of the basis matrix used by the simplex method routines.
alpar@9: 
alpar@9: The second condition checked by the routine is:
alpar@9: $$l_k \leq x_k \leq u_k {\rm \ \ \ for\ all}\ k=1,\dots,m+n,
alpar@9: \eqno{\rm (KKT.PB)}$$
alpar@9: where $x_k$ is auxiliary ($1\leq k\leq m$) or structural
alpar@9: ($m+1\leq k\leq m+n$) variable, $l_k$ and $u_k$ are, respectively,
alpar@9: lower and upper bounds of the variable $x_k$ (including cases of
alpar@9: infinite bounds). This condition expresses the requirement that all
alpar@9: primal variables must satisfy to bound constraints of the original LP
alpar@9: problem. Since in case of basic solution all non-basic variables are
alpar@9: placed on their bounds, actually the condition (KKT.PB) needs to be
alpar@9: checked for basic variables only. If the primal basic solution has
alpar@9: sufficient accuracy, this condition shows primal feasibility of the
alpar@9: solution.
alpar@9: 
alpar@9: The third condition checked by the routine is:
alpar@9: $${\rm grad}\;Z = c = (\tilde{A})^T \pi + d,$$
alpar@9: where $Z$ is the objective function, $c$ is the vector of objective
alpar@9: coefficients, $(\tilde{A})^T$ is a matrix transposed to the expanded
alpar@9: constraint matrix $\tilde{A} = (I|-A)$, $\pi$ is a vector of Lagrange
alpar@9: multipliers that correspond to equality constraints of the original LP
alpar@9: problem, $d$ is a vector of Lagrange multipliers that correspond to
alpar@9: bound constraints for all (auxiliary and structural) variables of the
alpar@9: original LP problem. Geometrically the third condition expresses the
alpar@9: requirement that the gradient of the objective function must belong to
alpar@9: the orthogonal complement of a linear subspace defined by the equality
alpar@9: and active bound constraints, i.e. that the gradient must be a linear
alpar@9: combination of normals to the constraint planes, where Lagrange
alpar@9: multipliers $\pi$ and $d$ are coefficients of that linear combination.
alpar@9: 
alpar@9: To eliminate the vector $\pi$ the third condition can be rewritten as:
alpar@9: $$
alpar@9: \left(\begin{array}{@{}c@{}}I \\ -A^T\end{array}\right) \pi =
alpar@9: \left(\begin{array}{@{}c@{}}d_R \\ d_S\end{array}\right) +
alpar@9: \left(\begin{array}{@{}c@{}}c_R \\ c_S\end{array}\right),
alpar@9: $$
alpar@9: or, equivalently:
alpar@9: $$
alpar@9: \begin{array}{r@{}c@{}c}
alpar@9: \pi + d_R&\ =\ &c_R, \\
alpar@9: -A^T\pi + d_S&\ =\ &c_S. \\
alpar@9: \end{array}
alpar@9: $$
alpar@9: Then substituting the vector $\pi$ from the first equation into the
alpar@9: second one we have:
alpar@9: $$A^T (d_R - c_R) + (d_S - c_S) = 0, \eqno{\rm (KKT.DE)}$$
alpar@9: where $d_R$ is the subvector of reduced costs of auxiliary variables
alpar@9: (rows), $d_S$ is the subvector of reduced costs of structural variables
alpar@9: (columns), $c_R$ and $c_S$ are subvectors of objective coefficients at,
alpar@9: respectively, auxiliary and structural variables, $A^T$ is a matrix
alpar@9: transposed to the constraint matrix of the original LP problem. In case
alpar@9: of exact arithmetic this condition would be satisfied for any basic
alpar@9: solution; however, in case of inexact (floating-point) arithmetic, this
alpar@9: condition shows how accurate the dual basic solution is, that depends on
alpar@9: accuracy of a representation of the basis matrix used by the simplex
alpar@9: method routines.
alpar@9: 
alpar@9: The last, fourth condition checked by the routine is (KKT.DB):
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \begin{tabular}{r@{}c@{}ll}
alpar@9: &$\ d_k\ $& $=0,$&if $x_k$ is basic or free non-basic variable \\
alpar@9: $0\leq$&$\ d_k\ $&$<+\infty$&if $x_k$ is non-basic on its lower
alpar@9: (minimization) \\
alpar@9: &&&or upper (maximization) bound \\
alpar@9: $-\infty<$&$\ d_k\ $&$\leq 0$&if $x_k$ is non-basic on its upper
alpar@9: (minimization) \\
alpar@9: &&&or lower (maximization) bound \\
alpar@9: $-\infty<$&$\ d_k\ $&$<+\infty$&if $x_k$ is non-basic fixed variable \\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: for all $k=1,\dots,m+n$, where $d_k$ is a reduced cost (Lagrange
alpar@9: multiplier) of auxiliary ($1\leq k\leq m$) or structural
alpar@9: ($m+1\leq k\leq m+n$) variable $x_k$. Geometrically this condition
alpar@9: expresses the requirement that constraints of the original problem must
alpar@9: "hold" the point preventing its movement along the anti-gradient (in
alpar@9: case of minimization) or the gradient (in case of maximization) of the
alpar@9: objective function. Since in case of basic solution reduced costs of
alpar@9: all basic variables are placed on their (zero) bounds, actually the
alpar@9: condition (KKT.DB) needs to be checked for non-basic variables only.
alpar@9: If the dual basic solution has sufficient accuracy, this condition shows
alpar@9: dual feasibility of the solution.
alpar@9: 
alpar@9: Should note that the complete set of Karush-Kuhn-Tucker optimality
alpar@9: conditions also includes the fifth, so called complementary slackness
alpar@9: condition, which expresses the requirement that at least either a primal
alpar@9: variable $x_k$ or its dual counterpart $d_k$ must be on its bound for
alpar@9: all $k=1,\dots,m+n$. However, being always satisfied by definition for
alpar@9: any basic solution that condition is not checked by the routine.
alpar@9: 
alpar@9: To check the first condition (KKT.PE) the routine computes a vector of
alpar@9: residuals:
alpar@9: $$g = x_R - A x_S,$$
alpar@9: determines component of this vector that correspond to largest absolute
alpar@9: and relative errors:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \hspace{30mm}
alpar@9: \verb|pe_ae_max| $\displaystyle{= \max_{1\leq i\leq m}|g_i|}$,
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \hspace{30mm}
alpar@9: \verb|pe_re_max| $\displaystyle{= \max_{1\leq i\leq m}
alpar@9: \frac{|g_i|}{1+|(x_R)_i|}}$,
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: and stores these quantities and corresponding row indices to the
alpar@9: structure \verb|LPXKKT|.
alpar@9: 
alpar@9: To check the second condition (KKT.PB) the routine computes a vector
alpar@9: of residuals:
alpar@9: $$
alpar@9: h_k = \left\{
alpar@9: \begin{array}{ll}
alpar@9: 0,         & {\rm if}\ l_k \leq x_k \leq u_k \\
alpar@9: x_k - l_k, & {\rm if}\ x_k < l_k \\
alpar@9: x_k - u_k, & {\rm if}\ x_k > u_k \\
alpar@9: \end{array}
alpar@9: \right.
alpar@9: $$
alpar@9: for all $k=1,\dots,m+n$, determines components of this vector that
alpar@9: correspond to largest absolute and relative errors:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \hspace{30mm}
alpar@9: \verb|pb_ae_max| $\displaystyle{= \max_{1\leq k \leq m+n}|h_k|}$,
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \hspace{30mm}
alpar@9: \verb|pb_re_max| $\displaystyle{= \max_{1\leq k \leq m+n}
alpar@9: \frac{|h_k|}{1+|x_k|}}$,
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: and stores these quantities and corresponding variable indices to the
alpar@9: structure \verb|LPXKKT|.
alpar@9: 
alpar@9: To check the third condition (KKT.DE) the routine computes a vector of
alpar@9: residuals:
alpar@9: $$u = A^T (d_R - c_R) + (d_S - c_S),$$
alpar@9: determines components of this vector that correspond to largest
alpar@9: absolute and relative errors:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \hspace{30mm}
alpar@9: \verb|de_ae_max| $\displaystyle{= \max_{1\leq j\leq n}|u_j|}$,
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \hspace{30mm}
alpar@9: \verb|de_re_max| $\displaystyle{= \max_{1\leq j\leq n}
alpar@9: \frac{|u_j|}{1+|(d_S)_j - (c_S)_j|}}$,
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: and stores these quantities and corresponding column indices to the
alpar@9: structure \verb|LPXKKT|.
alpar@9: 
alpar@9: To check the fourth condition (KKT.DB) the routine computes a vector
alpar@9: of residuals:
alpar@9: 
alpar@9: $$
alpar@9: v_k = \left\{
alpar@9: \begin{array}{ll}
alpar@9: 0,         & {\rm if}\ d_k\ {\rm has\ correct\ sign} \\
alpar@9: d_k,       & {\rm if}\ d_k\ {\rm has\ wrong\ sign} \\
alpar@9: \end{array}
alpar@9: \right.
alpar@9: $$
alpar@9: for all $k=1,\dots,m+n$, determines components of this vector that
alpar@9: correspond to largest absolute and relative errors:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \hspace{30mm}
alpar@9: \verb|db_ae_max| $\displaystyle{= \max_{1\leq k\leq m+n}|v_k|}$,
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \hspace{30mm}
alpar@9: \verb|db_re_max| $\displaystyle{= \max_{1\leq k\leq m+n}
alpar@9: \frac{|v_k|}{1+|d_k - c_k|}}$,
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent
alpar@9: and stores these quantities and corresponding variable indices to the
alpar@9: structure \verb|LPXKKT|.
alpar@9: 
alpar@9: Using the relative errors for all the four conditions listed above the
alpar@9: routine
alpar@9: \verb|lpx_check_kkt| also estimates a "quality" of the basic solution
alpar@9: from the standpoint of these conditions and stores corresponding
alpar@9: quality indicators to the structure \verb|LPXKKT|:
alpar@9: 
alpar@9: \verb|pe_quality|---quality of primal solution;
alpar@9: 
alpar@9: \verb|pb_quality|---quality of primal feasibility;
alpar@9: 
alpar@9: \verb|de_quality|---quality of dual solution;
alpar@9: 
alpar@9: \verb|db_quality|---quality of dual feasibility.
alpar@9: 
alpar@9: Each of these indicators is assigned to one of the following four
alpar@9: values:
alpar@9: 
alpar@9: \verb|'H'| means high quality,
alpar@9: 
alpar@9: \verb|'M'| means medium quality,
alpar@9: 
alpar@9: \verb|'L'| means low quality, or
alpar@9: 
alpar@9: \verb|'?'| means wrong or infeasible solution.
alpar@9: 
alpar@9: If all the indicators show high or medium quality (for an internally
alpar@9: scaled LP problem, i.e. when the parameter \verb|scaled| in a call to
alpar@9: the routine \verb|lpx_check_kkt| is non-zero), the user can be sure that
alpar@9: the obtained basic solution is quite accurate.
alpar@9: 
alpar@9: If some of the indicators show low quality, the solution can still be
alpar@9: considered as relevant, though an additional analysis is needed
alpar@9: depending on which indicator shows low quality.
alpar@9: 
alpar@9: If the indicator \verb|pe_quality| is assigned to \verb|'?'|, the
alpar@9: primal solution is wrong. If the indicator \verb|de_quality| is assigned
alpar@9: to \verb|'?'|, the dual solution is wrong.
alpar@9: 
alpar@9: If the indicator \verb|db_quality| is assigned to \verb|'?'| while
alpar@9: other indicators show a good quality, this means that the current
alpar@9: basic solution being primal feasible is not dual feasible. Similarly,
alpar@9: if the indicator \verb|pb_quality| is assigned to \verb|'?'| while
alpar@9: other indicators are not, this means that the current basic solution
alpar@9: being dual feasible is not primal feasible.
alpar@9: 
alpar@9: %* eof *%