glpk04.tex

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

int glp_bf_exists(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

If the basis factorization for the current basis associated with the
specified problem object exists and therefore is available for
computations, the routine \verb|glp_bf_exists| returns non-zero.
Otherwise the routine returns zero.

\subsubsection*{Comments}

Let the problem object have $m$ rows and $n$ columns. In GLPK the
{\it basis matrix} $B$ is a square non-singular matrix of the order $m$,
whose columns correspond to basic (auxiliary and/or structural)
variables. It is defined by the following main
equality:\footnote{For more details see Subsection \ref{subsecbasbgd},
page \pageref{subsecbasbgd}.}
$$(B\ |\ N)=(I\ |-\!A)\Pi^T,$$
where $I$ is the unity matrix of the order $m$, whose columns correspond
to auxiliary variables; $A$ is the original constraint
$m\times n$-matrix, whose columns correspond to structural variables;
$(I\ |-\!A)$ is the augmented constraint\linebreak
$m\times(m+n)$-matrix, whose columns correspond to all (auxiliary and
structural) variables following in the original order; $\Pi$ is a
permutation matrix of the order $m+n$; and $N$ is a rectangular
$m\times n$-matrix, whose columns correspond to non-basic (auxiliary
and/or structural) variables.

For various reasons it may be necessary to solve linear systems with
matrix $B$. To provide this possibility the GLPK implementation
maintains an invertable form of $B$ (that is, some representation of
$B^{-1}$) called the {\it basis factorization}, which is an internal
component of the problem object. Typically, the basis factorization is
computed by the simplex solver, which keeps it in the problem object
to be available for other computations.

Should note that any changes in the problem object, which affects the
basis matrix (e.g. changing the status of a row or column, changing
a basic column of the constraint matrix, removing an active constraint,
etc.), invalidates the basis factorization. So before calling any API
routine, which uses the basis factorization, the application program
must make sure (using the routine \verb|glp_bf_exists|) that the
factorization exists and therefore available for computations.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{glp\_factorize---compute the basis factorization}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_factorize(glp_prob *lp);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_factorize| computes the basis factorization for
the current basis associated with the specified problem
object.\footnote{The current basis is defined by the current statuses
of rows (auxiliary variables) and columns (structural variables).}

The basis factorization is computed from ``scratch'' even if it exists,
so the application program may use the routine \verb|glp_bf_exists|,
and, if the basis factorization already exists, not to call the routine
\verb|glp_factorize| to prevent an extra work.

The routine \verb|glp_factorize| {\it does not} compute components of
the basic solution (i.e. primal and dual values).

\subsubsection*{Returns}

\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
0 & The basis factorization has been successfully computed.\\
\verb|GLP_EBADB| & The basis matrix is invalid, because the number of
basic (auxiliary and structural) variables is not the same as the number
of rows in the problem object.\\
\verb|GLP_ESING| & The basis matrix is singular within the working
precision.\\
\verb|GLP_ECOND| & The basis matrix is ill-conditioned, i.e. its
condition number is too large.\\
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{glp\_bf\_updated---check if the basis factorization has\\
been updated}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_bf_updated(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

If the basis factorization has been just computed from ``scratch'', the
routine \verb|glp_bf_updated| returns zero. Otherwise, if the
factorization has been updated at least once, the routine returns
non-zero.

\subsubsection*{Comments}

{\it Updating} the basis factorization means recomputing it to reflect
changes in the basis matrix. For example, on every iteration of the
simplex method some column of the current basis matrix is replaced by a
new column that gives a new basis matrix corresponding to the adjacent
basis. In this case computing the basis factorization for the adjacent
basis from ``scratch'' (as the routine \verb|glp_factorize| does) would
be too time-consuming.

On the other hand, since the basis factorization update is a numeric
computational procedure, applying it many times may lead to accumulating
round-off errors. Therefore the basis is periodically refactorized
(reinverted) from ``scratch'' (with the routine \verb|glp_factorize|)
that allows improving its numerical properties.

The routine \verb|glp_bf_updated| allows determining if the basis
factorization has been updated at least once since it was computed from
``scratch''.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{glp\_get\_bfcp---retrieve basis factorization control
parameters}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_get_bfcp(glp_prob *lp, glp_bfcp *parm);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_get_bfcp| retrieves control parameters, which are
used on computing and updating the basis factorization associated with
the specified problem object.

Current values of the control parameters are stored in a \verb|glp_bfcp|
structure, which the parameter \verb|parm| points to. For a detailed
description of the structure \verb|glp_bfcp| see comments to the routine
\verb|glp_set_bfcp| in the next subsection.

\subsubsection*{Comments}

The purpose of the routine \verb|glp_get_bfcp| is two-fold. First, it
allows the application program obtaining current values of control
parameters used by internal GLPK routines, which compute and update the
basis factorization.

The second purpose of this routine is to provide proper values for all
fields of the structure \verb|glp_bfcp| in the case when the application
program needs to change some control parameters.

\subsection{Change basis factorization control parameters}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_bfcp(glp_prob *lp, const glp_bfcp *parm);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_bfcp| changes control parameters, which are
used by internal GLPK routines on computing and updating the basis
factorization associated with the specified problem object.

New values of the control parameters should be passed in a structure
\verb|glp_bfcp|, which the parameter \verb|parm| points to. For a
detailed description of the structure \verb|glp_bfcp| see paragraph
``Control parameters'' below.

The parameter \verb|parm| can be specified as \verb|NULL|, in which case
all control parameters are reset to their default values.

\subsubsection*{Comments}

Before changing some control parameters with the routine
\verb|glp_set_bfcp| the application program should retrieve current
values of all control parameters with the routine \verb|glp_get_bfcp|.
This is needed for backward compatibility, because in the future there
may appear new members in the structure \verb|glp_bfcp|.

Note that new values of control parameters come into effect on a next
computation of the basis factorization, not immediately.

\subsubsection*{Example}

\begin{verbatim}
glp_prob *lp;
glp_bfcp parm;
. . .
/* retrieve current values of control parameters */
glp_get_bfcp(lp, &parm);
/* change the threshold pivoting tolerance */
parm.piv_tol = 0.05;
/* set new values of control parameters */
glp_set_bfcp(lp, &parm);
. . .
\end{verbatim}

\subsubsection*{Control parameters}

This paragraph describes all basis factorization control parameters
currently used in the package. Symbolic names of control parameters are
names of corresponding members in the structure \verb|glp_bfcp|.

\def\arraystretch{1}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int type} (default: {\tt GLP\_BF\_FT})} \\
&Basis factorization type:\\
&\verb|GLP_BF_FT|---$LU$ + Forrest--Tomlin update;\\
&\verb|GLP_BF_BG|---$LU$ + Schur complement + Bartels--Golub update;\\
&\verb|GLP_BF_GR|---$LU$ + Schur complement + Givens rotation update.
\\
&In case of \verb|GLP_BF_FT| the update is applied to matrix $U$, while
in cases of \verb|GLP_BF_BG| and \verb|GLP_BF_GR| the update is applied
to the Schur complement.
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int lu\_size} (default: {\tt 0})} \\
&The initial size of the Sparse Vector Area, in non-zeros, used on
computing $LU$-factorization of the basis matrix for the first time.
If this parameter is set to 0, the initial SVA size is determined
automatically.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double piv\_tol} (default: {\tt 0.10})} \\
&Threshold pivoting (Markowitz) tolerance, 0 $<$ \verb|piv_tol| $<$ 1,
used on computing $LU$-factorization of the basis matrix. Element
$u_{ij}$ of the active submatrix of factor $U$ fits to be pivot if it
satisfies to the stability criterion
$|u_{ij}| >= {\tt piv\_tol}\cdot\max|u_{i*}|$, i.e. if it is not very
small in the magnitude among other elements in the same row. Decreasing
this parameter may lead to better sparsity at the expense of numerical
accuracy, and vice versa.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int piv\_lim} (default: {\tt 4})} \\
&This parameter is used on computing $LU$-factorization of the basis
matrix and specifies how many pivot candidates needs to be considered
on choosing a pivot element, \verb|piv_lim| $\geq$ 1. If \verb|piv_lim|
candidates have been considered, the pivoting routine prematurely
terminates the search with the best candidate found.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int suhl} (default: {\tt GLP\_ON})} \\
&This parameter is used on computing $LU$-factorization of the basis
matrix. Being set to {\tt GLP\_ON} it enables applying the following
heuristic proposed by Uwe Suhl: if a column of the active submatrix has
no eligible pivot candidates, it is no more considered until it becomes
a column singleton. In many cases this allows reducing the time needed
for pivot searching. To disable this heuristic the parameter \verb|suhl|
should be set to {\tt GLP\_OFF}.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double eps\_tol} (default: {\tt 1e-15})} \\
&Epsilon tolerance, \verb|eps_tol| $\geq$ 0, used on computing
$LU$-factorization of the basis matrix. If an element of the active
submatrix of factor $U$ is less than \verb|eps_tol| in the magnitude,
it is replaced by exact zero.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double max\_gro} (default: {\tt 1e+10})} \\
&Maximal growth of elements of factor $U$, \verb|max_gro| $\geq$ 1,
allowable on computing $LU$-factorization of the basis matrix. If on
some elimination step the ratio $u_{big}/b_{max}$ (where $u_{big}$ is
the largest magnitude of elements of factor $U$ appeared in its active
submatrix during all the factorization process, $b_{max}$ is the largest
magnitude of elements of the basis matrix to be factorized), the basis
matrix is considered as ill-conditioned.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int nfs\_max} (default: {\tt 50})} \\
&Maximal number of additional row-like factors (entries of the eta
file), \verb|nfs_max| $\geq$ 1, which can be added to $LU$-factorization
of the basis matrix on updating it with the Forrest--Tomlin technique.
This parameter is used only once, before $LU$-factorization is computed
for the first time, to allocate working arrays. As a rule, each update
adds one new factor (however, some updates may need no addition), so
this parameter limits the number of updates between refactorizations.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double upd\_tol} (default: {\tt 1e-6})} \\
&Update tolerance, 0 $<$ \verb|upd_tol| $<$ 1, used on updating
$LU$-factorization of the basis matrix with the Forrest--Tomlin
technique. If after updating the magnitude of some diagonal element
$u_{kk}$ of factor $U$ becomes less than
${\tt upd\_tol}\cdot\max(|u_{k*}|, |u_{*k}|)$, the factorization is
considered as inaccurate.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int nrs\_max} (default: {\tt 50})} \\
&Maximal number of additional rows and columns, \verb|nrs_max| $\geq$ 1,
which can be added to $LU$-factorization of the basis matrix on updating
it with the Schur complement technique. This parameter is used only
once, before $LU$-factorization is computed for the first time, to
allocate working arrays. As a rule, each update adds one new row and
column (however, some updates may need no addition), so this parameter
limits the number of updates between refactorizations.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int rs\_size} (default: {\tt 0})} \\
&The initial size of the Sparse Vector Area, in non-zeros, used to
store non-zero elements of additional rows and columns introduced on
updating $LU$-factorization of the basis matrix with the Schur
complement technique. If this parameter is set to 0, the initial SVA
size is determined automatically.\\
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\subsection{glp\_get\_bhead---retrieve the basis header information}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_bhead(glp_prob *lp, int k);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_get_bhead| returns the basis header information
for the current basis associated with the specified problem object.

\subsubsection*{Returns}

If basic variable $(x_B)_k$, $1\leq k\leq m$, is $i$-th auxiliary