glpk04.tex

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

variable ($1\leq i\leq m$), the routine returns $i$. Otherwise, if
$(x_B)_k$ is $j$-th structural variable ($1\leq j\leq n$), the routine
returns $m+j$. Here $m$ is the number of rows and $n$ is the number of
columns in the problem object.

\subsubsection*{Comments}

Sometimes the application program may need to know which original
(auxiliary and structural) variable correspond to a given basic
variable, or, that is the same, which column of the augmented constraint
matrix $(I\ |-\!A)$ correspond to a given column of the basis matrix
$B$.

\def\arraystretch{1}

The correspondence is defined as follows:\footnote{For more details see
Subsection \ref{subsecbasbgd}, page \pageref{subsecbasbgd}.}
$$\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right)=
\Pi\left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)
\ \ \Leftrightarrow
\ \ \left(\begin{array}{@{}c@{}}x_R\\x_S\\\end{array}\right)=
\Pi^T\left(\begin{array}{@{}c@{}}x_B\\x_N\\\end{array}\right),$$
where $x_B$ is the vector of basic variables, $x_N$ is the vector of
non-basic variables, $x_R$ is the vector of auxiliary variables
following in their original order,\footnote{The original order of
auxiliary and structural variables is defined by the ordinal numbers
of corresponding rows and columns in the problem object.} $x_S$ is the
vector of structural variables following in their original order, $\Pi$
is a permutation matrix (which is a component of the basis
factorization).

Thus, if $(x_B)_k=(x_R)_i$ is $i$-th auxiliary variable, the routine
returns $i$, and if $(x_B)_k=(x_S)_j$ is $j$-th structural variable,
the routine returns $m+j$, where $m$ is the number of rows in the
problem object.

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

\newpage

\subsection{glp\_get\_row\_bind---retrieve row index in the basis\\
header}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_get_row_bind| returns the index $k$ of basic
variable $(x_B)_k$, $1\leq k\leq m$, which is $i$-th auxiliary variable
(that is, the auxiliary variable corresponding to $i$-th row),
$1\leq i\leq m$, in the current basis associated with the specified
problem object, where $m$ is the number of rows. However, if $i$-th
auxiliary variable is non-basic, the routine returns zero.

\subsubsection*{Comments}

The routine \verb|glp_get_row_bind| is an inverse to the routine
\verb|glp_get_bhead|: if \verb|glp_get_bhead|$(lp,k)$ returns $i$,
\verb|glp_get_row_bind|$(lp,i)$ returns $k$, and vice versa.

\subsection{glp\_get\_col\_bind---retrieve column index in the basis
header}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_get_col_bind| returns the index $k$ of basic
variable $(x_B)_k$, $1\leq k\leq m$, which is $j$-th structural
variable (that is, the structural variable corresponding to $j$-th
column), $1\leq j\leq n$, in the current basis associated with the
specified problem object, where $m$ is the number of rows, $n$ is the
number of columns. However, if $j$-th structural variable is non-basic,
the routine returns zero.

\subsubsection*{Comments}

The routine \verb|glp_get_col_bind| is an inverse to the routine
\verb|glp_get_bhead|: if \verb|glp_get_bhead|$(lp,k)$ returns $m+j$,
\verb|glp_get_col_bind|$(lp,j)$ returns $k$, and vice versa.

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

\newpage

\subsection{glp\_ftran---perform forward transformation}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_ftran(glp_prob *lp, double x[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ftran| performs forward transformation (FTRAN),
i.e. it solves the system $Bx=b$, where $B$ is the basis matrix
associated with the specified problem object, $x$ is the vector of
unknowns to be computed, $b$ is the vector of right-hand sides.

On entry to the routine elements of the vector $b$ should be stored in
locations \verb|x[1]|, \dots, \verb|x[m]|, where $m$ is the number of
rows. On exit the routine stores elements of the vector $x$ in the same
locations.

\subsection{glp\_btran---perform backward transformation}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_btran(glp_prob *lp, double x[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_btran| performs backward transformation (BTRAN),
i.e. it solves the system $B^Tx=b$, where $B^T$ is a matrix transposed
to the basis matrix $B$ associated with the specified problem object,
$x$ is the vector of unknowns to be computed, $b$ is the vector of
right-hand sides.

On entry to the routine elements of the vector $b$ should be stored in
locations \verb|x[1]|, \dots, \verb|x[m]|, where $m$ is the number of
rows. On exit the routine stores elements of the vector $x$ in the same
locations.

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

\newpage

\subsection{lpx\_warm\_up---``warm up'' LP basis}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|lpx_warm_up| ``warms up'' the LP basis for the
specified problem object using current statuses assigned to rows and
columns (i.e. to auxiliary and structural variables).

``Warming up'' includes reinverting (factorizing) the basis matrix (if
neccesary), computing primal and dual components as well as determining
primal and dual statuses of the basic solution.

\subsubsection*{Returns}

The routine \verb|lpx_warm_up| returns one of the following exit codes:

\begin{tabular}{@{}p{25mm}p{91.3mm}@{}}
\verb|LPX_E_OK| & the LP basis has been successfully ``warmed up''. \\
\verb|LPX_E_EMPTY|  & the problem has no rows and/or no columns. \\
\verb|LPX_E_BADB|   & the LP basis is invalid, because the number of
   basic variables is not the same as the number of rows. \\
\verb|LPX_E_SING|   & the basis matrix is numerically singular or
   ill-condi\-tioned.
\end{tabular}

\subsection{glp\_eval\_tab\_row---compute row of the tableau}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|glp_eval_tab_row| computes a row of the current
simplex tableau (see Subsection 3.1.1, formula (3.12)), which (row)
corresponds to some basic variable specified by the parameter $k$ as
follows: if $1\leq k\leq m$, the basic variable is $k$-th auxiliary
variable, and if $m+1\leq k\leq m+n$, the basic variable is $(k-m)$-th
structural variable, where $m$ is the number of rows and $n$ is the
number of columns in the specified problem object. The basis
factorization must exist.

The computed row shows how the specified basic variable depends on
non-basic variables:
$$x_k=(x_B)_i=\xi_{i1}(x_N)_1+\xi_{i2}(x_N)_2+\dots+\xi_{in}(x_N)_n,$$
where $\xi_{i1}$, $\xi_{i2}$, \dots, $\xi_{in}$ are elements of the
simplex table row, $(x_N)_1$, $(x_N)_2$, \dots, $(x_N)_n$ are non-basic
(auxiliary and structural) variables.

The routine stores column indices and corresponding numeric values of
non-zero elements of the computed row in unordered sparse format in
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 non-zero elements in the row returned on exit.

Element indices stored in the array \verb|ind| have the same sense as
index $k$, i.e. indices 1 to $m$ denote auxiliary variables while
indices $m+1$ to $m+n$ denote structural variables (all these variables
are obviously non-basic by definition).

\subsubsection*{Returns}

The routine \verb|glp_eval_tab_row| returns \verb|len|, which is the
number of non-zero elements in the simplex table row stored in the
arrays \verb|ind| and \verb|val|.

\subsubsection*{Comments}

A row of the simplex table is computed as follows. At first, the
routine checks that the specified variable $x_k$ is basic and uses the
permutation matrix $\Pi$ (3.7) to determine index $i$ of basic variable
$(x_B)_i$, which corresponds to $x_k$.

The row to be computed is $i$-th row of the matrix $\Xi$ (3.12),
therefore:
$$\xi_i=e_i^T\Xi=-e_i^TB^{-1}N=-(B^{-T}e_i)^TN,$$
where $e_i$ is $i$-th unity vector. So the routine performs BTRAN to
obtain $i$-th row of the inverse $B^{-1}$:
$$\varrho_i=B^{-T}e_i,$$
and then computes elements of the simplex table row as inner products:
$$\xi_{ij}=-\varrho_i^TN_j,\ \ j=1,2,\dots,n,$$
where $N_j$ is $j$-th column of matrix $N$ (3.9), which (column)
corresponds to non-basic variable $(x_N)_j$. The permutation matrix
$\Pi$ is used again to convert indices $j$ of non-basic columns to
original ordinal numbers of auxiliary and structural variables.

\subsection{glp\_eval\_tab\_col---compute column of the tableau}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|glp_eval_tab_col| computes a column of the current
simplex tableau (see Subsection 3.1.1, formula (3.12)), which (column)
corresponds to some non-basic variable specified by the parameter $k$:
if $1\leq k\leq m$, the non-basic variable is $k$-th auxiliary variable,
and if $m+1\leq k\leq m+n$, the non-basic variable is $(k-m)$-th
structural variable, where $m$ is the number of rows and $n$ is the
number of columns in the specified problem object. The basis
factorization must exist.

The computed column shows how basic variables depends on the specified
non-basic variable $x_k=(x_N)_j$:
$$
\begin{array}{r@{\ }c@{\ }l@{\ }l}
(x_B)_1&=&\dots+\xi_{1j}(x_N)_j&+\dots\\
(x_B)_2&=&\dots+\xi_{2j}(x_N)_j&+\dots\\
.\ \ .&.&.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\\
(x_B)_m&=&\dots+\xi_{mj}(x_N)_j&+\dots\\
\end{array}
$$
where $\xi_{1j}$, $\xi_{2j}$, \dots, $\xi_{mj}$ are elements of the
simplex table column, $(x_B)_1$, $(x_B)_2$, \dots, $(x_B)_m$ are basic
(auxiliary and structural) variables.

The routine stores row indices and corresponding numeric values of
non-zero elements of the computed column in unordered sparse format in
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 non-zero elements in the column returned on exit.

Element indices stored in the array \verb|ind| have the same sense as
index $k$, i.e. indices 1 to $m$ denote auxiliary variables while
indices $m+1$ to $m+n$ denote structural variables (all these variables
are obviously basic by definition).

\subsubsection*{Returns}

The routine \verb|glp_eval_tab_col| returns \verb|len|, which is the
number of non-zero elements in the simplex table column stored in the
arrays \verb|ind| and \verb|val|.

\subsubsection*{Comments}

A column of the simplex table is computed as follows. At first, the
routine checks that the specified variable $x_k$ is non-basic and uses
the permutation matrix $\Pi$ (3.7) to determine index $j$ of non-basic
variable $(x_N)_j$, which corresponds to $x_k$.

The column to be computed is $j$-th column of the matrix $\Xi$ (3.12),
therefore:
$$\Xi_j=\Xi e_j=-B^{-1}Ne_j=-B^{-1}N_j,$$
where $e_j$ is $j$-th unity vector, $N_j$ is $j$-th column of matrix
$N$ (3.9). So the routine performs FTRAN to transform $N_j$ to the
simplex table column $\Xi_j=(\xi_{ij})$ and uses the permutation matrix
$\Pi$ to convert row indices $i$ to original ordinal numbers of
auxiliary and structural variables.

\subsection{lpx\_transform\_row---transform explicitly specified\\
row}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|lpx_transform_row| performs the same operation as the
routine \verb|lpx_eval_tab_row|, except that the transformed row is
specified explicitly.

The explicitly specified row may be thought as a linear form:
$$x=a_1x_{m+1}+a_2x_{m+2}+\dots+a_nx_{m+n},\eqno(1)$$
where $x$ is an auxiliary variable for this row, $a_j$ are coefficients
of the linear form, $x_{m+j}$ are structural variables.

On entry column indices and numerical values of non-zero coefficients
$a_j$ of the transformed row should be placed in locations
\verb|ind[1]|, \dots, \verb|ind[len]| and \verb|val[1]|, \dots,
\verb|val[len]|, where \verb|len| is number of non-zero coefficients.

This routine uses the system of equality constraints and the current
basis in order to express the auxiliary variable $x$ in (1) through the
current non-basic variables (as if the transformed row were added to
the problem object and the auxiliary variable $x$ were basic), i.e. the
resultant row has the form:
$$x=\alpha_1(x_N)_1+\alpha_2(x_N)_2+\dots+\alpha_n(x_N)_n,\eqno(2)$$
where $\alpha_j$ are influence coefficients, $(x_N)_j$ are non-basic
(auxiliary and structural) variables, $n$ is number of columns in the
specified problem object.

On exit the routine stores indices and numerical values of non-zero
coefficients $\alpha_j$ of the resultant row (2) in locations
\verb|ind[1]|, \dots, \verb|ind[len']| and \verb|val[1]|, \dots,
\verb|val[len']|, where $0\leq{\tt len'}\leq n$ is the number of
non-zero coefficients in the resultant row returned by the routine.
Note that indices of non-basic variables stored in the array \verb|ind|
correspond to original ordinal numbers of variables: indices 1 to $m$
mean auxiliary variables and indices $m+1$ to $m+n$ mean structural
ones.

\subsubsection*{Returns}

The routine \verb|lpx_transform_row| returns \verb|len'|, the number of
non-zero coefficients in the resultant row stored in the arrays
\verb|ind| and \verb|val|.

\subsection{lpx\_transform\_col---transform explicitly specified\\
column}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|lpx_transform_col| performs the same operation as the
routine \verb|lpx_eval_tab_col|, except that the transformed column is
specified explicitly.

The explicitly specified column may be thought as it were added to
the original system of equality constraints: