glpk02.tex

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

row, i.e. the type of corresponding auxiliary variable, as follows:

\begin{tabular}{@{}ll}
\verb|GLP_FR| & free (unbounded) variable; \\
\verb|GLP_LO| & variable with lower bound; \\
\verb|GLP_UP| & variable with upper bound; \\
\verb|GLP_DB| & double-bounded variable; \\
\verb|GLP_FX| & fixed variable. \\
\end{tabular}

\subsection{glp\_get\_row\_lb---retrieve row lower bound}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_row_lb(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_row_lb| returns the lower bound of
\verb|i|-th row, i.e. the lower bound of corresponding auxiliary
variable. However, if the row has no lower bound, the routine returns
\verb|-DBL_MAX|.

\subsection{glp\_get\_row\_ub---retrieve row upper bound}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_row_ub(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_row_ub| returns the upper bound of
\verb|i|-th row, i.e. the upper bound of corresponding auxiliary
variable. However, if the row has no upper bound, the routine returns
\verb|+DBL_MAX|.

\subsection{glp\_get\_col\_type---retrieve column type}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_col_type(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_col_type| returns the type of \verb|j|-th
column, i.e. the type of corresponding structural variable, as follows:

\begin{tabular}{@{}ll}
\verb|GLP_FR| & free (unbounded) variable; \\
\verb|GLP_LO| & variable with lower bound; \\
\verb|GLP_UP| & variable with upper bound; \\
\verb|GLP_DB| & double-bounded variable; \\
\verb|GLP_FX| & fixed variable. \\
\end{tabular}

\subsection{glp\_get\_col\_lb---retrieve column lower bound}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_col_lb(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_col_lb| returns the lower bound of
\verb|j|-th column, i.e. the lower bound of corresponding structural
variable. However, if the column has no lower bound, the routine returns
\verb|-DBL_MAX|.

\subsection{glp\_get\_col\_ub---retrieve column upper bound}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_col_ub(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_col_ub| returns the upper bound of
\verb|j|-th column, i.e. the upper bound of corresponding structural
variable. However, if the column has no upper bound, the routine returns
\verb|+DBL_MAX|.

\subsection{glp\_get\_obj\_coef---retrieve objective coefficient or\\
constant term}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_obj_coef(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_obj_coef| returns the objective coefficient
at \verb|j|-th structural variable (column).

If the parameter \verb|j| is 0, the routine returns the constant term
(``shift'') of the objective function.

\subsection{glp\_get\_num\_nz---retrieve number of constraint
coefficients}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_get_num_nz| returns the number of non-zero
elements in the constraint matrix of the specified problem object.

\subsection{glp\_get\_mat\_row---retrieve row of the constraint
matrix}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_mat_row(glp_prob *lp, int i, int ind[],
      double val[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_get_mat_row| scans (non-zero) elements of
\verb|i|-th row of the constraint matrix of the specified problem object
and stores their column indices and numeric values to locations
\verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
\verb|val[len]|, respectively, where $0\leq{\tt len}\leq n$ is the
number of elements in $i$-th row, $n$ is the number of columns.

The parameter \verb|ind| and/or \verb|val| can be specified as
\verb|NULL|, in which case corresponding information is not stored.

\subsubsection*{Returns}

The routine \verb|glp_get_mat_row| returns the length \verb|len|, i.e.
the number of (non-zero) elements in \verb|i|-th row.

\subsection{glp\_get\_mat\_col---retrieve column of the constraint\\
matrix}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_get_mat_col(glp_prob *lp, int j, int ind[],
      double val[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_get_mat_col| scans (non-zero) elements of
\verb|j|-th column of the constraint matrix of the specified problem
object and stores their row indices and numeric values to locations
\verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
\verb|val[len]|, respectively, where $0\leq{\tt len}\leq m$ is the
number of elements in $j$-th column, $m$ is the number of rows.

The parameter \verb|ind| and/or \verb|val| can be specified as
\verb|NULL|, in which case corresponding information is not stored.

\subsubsection*{Returns}

The routine \verb|glp_get_mat_col| returns the length \verb|len|, i.e.
the number of (non-zero) elements in \verb|j|-th column.

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

\newpage

\section{Row and column searching routines}

\subsection{glp\_create\_index---create the name index}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_create_index(glp_prob *lp);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_create_index| creates the name index for the
specified problem object. The name index is an auxiliary data structure,
which is intended to quickly (i.e. for logarithmic time) find rows and
columns by their names.

This routine can be called at any time. If the name index already
exists, the routine does nothing.

\subsection{glp\_find\_row---find row by its name}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_find_row(glp_prob *lp, const char *name);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_find_row| returns the ordinal number of a row,
which is assigned (by the routine \verb|glp_set_row_name|) the specified
symbolic \verb|name|. If no such row exists, the routine returns 0.

\subsection{glp\_find\_col---find column by its name}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_find_col(glp_prob *lp, const char *name);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_find_col| returns the ordinal number of a column,
which is assigned (by the routine \verb|glp_set_col_name|) the specified
symbolic \verb|name|. If no such column exists, the routine returns 0.

\subsection{glp\_delete\_index---delete the name index}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_delete_index(glp_prob *lp);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_delete_index| deletes the name index previously
created by the routine \verb|glp_create_index| and frees the memory
allocated to this auxiliary data structure.

This routine can be called at any time. If the name index does not
exist, the routine does nothing.

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

\newpage

\section{Problem scaling routines}

\subsection{Background}

In GLPK the {\it scaling} means a linear transformation applied to the
constraint matrix to improve its numerical properties.\footnote{In many
cases a proper scaling allows making the constraint matrix to be better
conditioned, i.e. decreasing its condition number, that makes
computations numerically more stable.}

The main equality is the following:
$$\widetilde{A}=RAS,\eqno(2.1)$$
where $A=(a_{ij})$ is the original constraint matrix, $R=(r_{ii})>0$ is
a diagonal matrix used to scale rows (constraints), $S=(s_{jj})>0$ is a
diagonal matrix used to scale columns (variables), $\widetilde{A}$ is
the scaled constraint matrix.

From (2.1) it follows that in the {\it scaled} problem instance each
original constraint coefficient $a_{ij}$ is replaced by corresponding
scaled constraint coefficient:
$$\widetilde{a}_{ij}=r_{ii}a_{ij}s_{jj}.\eqno(2.2)$$

Note that the scaling is performed internally and therefore
transparently to the user. This means that on API level the user always
deal with unscaled data.

Scale factors $r_{ii}$ and $s_{jj}$ can be set or changed at any time
either directly by the application program in a problem specific way
(with the routines \verb|glp_set_rii| and \verb|glp_set_sjj|), or by
some API routines intended for automatic scaling.

\subsection{glp\_set\_rii---set (change) row scale factor}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_rii(glp_prob *lp, int i, double rii);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_rii| sets (changes) the scale factor $r_{ii}$
for $i$-th row of the specified problem object.

\subsection{glp\_set\_sjj---set (change) column scale factor}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_sjj(glp_prob *lp, int j, double sjj);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_sjj| sets (changes) the scale factor $s_{jj}$
for $j$-th column of the specified problem object.

\subsection{glp\_get\_rii---retrieve row scale factor}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_rii(glp_prob *lp, int i);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_rii| returns current scale factor $r_{ii}$ for
$i$-th row of the specified problem object.

\subsection{glp\_get\_sjj---retrieve column scale factor}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_sjj(glp_prob *lp, int j);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_sjj| returns current scale factor $s_{jj}$ for
$j$-th column of the specified problem object.

\subsection{glp\_scale\_prob---scale problem data}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_scale_prob(glp_prob *lp, int flags);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_scale_prob| performs automatic scaling of problem
data for the specified problem object.

The parameter \verb|flags| specifies scaling options used by the
routine. The options can be combined with the bitwise OR operator and
may be the following:

\begin{tabular}{@{}ll}
\verb|GLP_SF_GM| & perform geometric mean scaling;\\
\verb|GLP_SF_EQ| & perform equilibration scaling;\\
\verb|GLP_SF_2N| & round scale factors to nearest power of two;\\
\verb|GLP_SF_SKIP| & skip scaling, if the problem is well scaled.\\
\end{tabular}

The parameter \verb|flags| may be specified as \verb|GLP_SF_AUTO|, in
which case the routine chooses the scaling options automatically.

\subsection{glp\_unscale\_prob---unscale problem data}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_unscale_prob(glp_prob *lp);
\end{verbatim}

The routine \verb|glp_unscale_prob| performs unscaling of problem data
for the specified problem object.

``Unscaling'' means replacing the current scaling matrices $R$ and $S$
by unity matrices that cancels the scaling effect.

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

\newpage

\section{LP basis constructing routines}

\subsection{Background}

To start the search the simplex method needs a valid initial basis. In
GLPK the basis is completely defined by a set of {\it statuses} assigned
to {\it all} (auxiliary and structural) variables, where the status may
be one of the following:

\begin{tabular}{@{}ll}
\verb|GLP_BS| & basic variable;\\
\verb|GLP_NL| & non-basic variable having active lower bound;\\
\verb|GLP_NU| & non-basic variable having active upper bound;\\
\verb|GLP_NF| & non-basic free variable;\\
\verb|GLP_NS| & non-basic fixed variable.\\
\end{tabular}

The basis is {\it valid}, if the basis matrix, which is a matrix built
of columns of the augmented constraint matrix $(I\:|-A)$ corresponding
to basic variables, is non-singular. This, in particular, means that
the number of basic variables must be the same as the number of rows in
the problem object. (For more details see Section \ref{lpbasis}, page
\pageref{lpbasis}.)

Any initial basis may be constructed (or restored) with the API
routines \verb|glp_set_row_stat| and \verb|glp_set_col_stat| by