glpk04.tex

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

$$
\begin{array}{rl}
x_1 &= a_{11}x_{m+1}+\dots+a_{1n}x_{m+n}+a_1x \\
x_2 &= a_{21}x_{m+1}+\dots+a_{2n}x_{m+n}+a_2x \\
    &  \dots \dots \dots \\
x_m &= a_{m1}x_{m+1}+\dots+a_{mn}x_{m+n}+a_mx \\
\end{array} \eqno(1)
$$
where $x_i$ are auxiliary variables, $x_{m+j}$ are structural variables
(presented in the problem object), $x$ is a structural variable for the
explicitly specified column, $a_i$ are constraint coefficients for $x$.

On entry row indices and numerical values of non-zero coefficients
$a_i$ of the transformed column 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 current basic variables through the
structural variable $x$ in (1) (as if the transformed column were added
to the problem object and the variable $x$ were non-basic):
$$
\begin{array}{rl}
(x_B)_1 &= \dots + \alpha_{1}x \\
(x_B)_2 &= \dots + \alpha_{2}x \\
        &  \dots \dots \dots   \\
(x_B)_m &= \dots + \alpha_{m}x \\
\end{array} \eqno(2)
$$
where $\alpha_i$ are influence coefficients, $x_B$ are basic (auxiliary
and structural) variables, $m$ is number of rows in the specified
problem object.

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

\subsubsection*{Returns}

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

\subsection{lpx\_prim\_ratio\_test---perform primal ratio test}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|lpx_prim_ratio_test| performs the primal ratio test
for an explicitly specified column of the simplex table.

The primal basic solution associated with an LP problem object, which
the parameter \verb|lp| points to, should be feasible. No components
of the LP problem object are changed by the routine.

The explicitly specified column of the simplex table shows how the
basic variables $x_B$ depend on some non-basic variable $y$ (which is
not necessarily presented in the problem object):
$$
\begin{array}{rl}
(x_B)_1 &= \dots + \alpha_{1}y \\
(x_B)_2 &= \dots + \alpha_{2}y \\
        &  \dots \dots \dots   \\
(x_B)_m &= \dots + \alpha_{m}y \\
\end{array} \eqno(1)
$$

The column (1) is specifed on entry to the routine using the sparse
format. Ordinal numbers of basic variables $(x_B)_i$ should be placed in
locations \verb|ind[1]|, \dots, \verb|ind[len]|, where ordinal number
1 to $m$ denote auxiliary variables, and ordinal numbers $m+1$ to $m+n$
denote structural variables. The corresponding non-zero coefficients
$\alpha_i$ should be placed in locations \verb|val[1]|, \dots,
\verb|val[len]|. The arrays \verb|ind| and \verb|val| are not changed by
the routine.

The parameter \verb|how| specifies in which direction the variable $y$
changes on entering the basis: $+1$ means increasing, $-1$ means
decreasing.

The parameter \verb|tol| is a relative tolerance (small positive number)
used by the routine to skip small $\alpha_i$ in the column (1).

The routine determines the ordinal number of a basic variable
(among specified in \verb|ind[1]|, \dots, \verb|ind[len]|), which
reaches its (lower or upper) bound first before any other basic
variables do and which therefore should leave the basis instead the
variable $y$ in order to keep primal feasibility, and returns it on
exit. If the choice cannot be made (i.e. if the adjacent basic solution
is primal unbounded due to $y$), the routine returns zero.

\subsubsection*{Note}

If the non-basic variable $y$ is presented in the LP problem object, the
column (1) can be computed using the routine \verb|lpx_eval_tab_col|.
Otherwise it can be computed using the routine \verb|lpx_transform_col|.

\subsubsection*{Returns}

The routine \verb|lpx_prim_ratio_test| returns the ordinal number of
some basic variable $(x_B)_i$, which should leave the basis instead the
variable $y$ in order to keep primal feasibility. If the adjacent basic
solution is primal unbounded and therefore the choice cannot be made,
the routine returns zero.

\newpage

\subsection{lpx\_dual\_ratio\_test---perform dual ratio test}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|lpx_dual_ratio_test| performs the dual ratio test for
an explicitly specified row of the simplex table.

The dual basic solution associated with an LP problem object, which the
parameter \verb|lp| points to, should be feasible. No components of the
LP problem object are changed by the routine.

The explicitly specified row of the simplex table is a linear form,
which shows how some basic variable $y$ (not necessarily presented in
the problem object) depends on non-basic variables $x_N$:
$$y=\alpha_1(x_N)_1+\alpha_2(x_N)_2+\dots+\alpha_n(x_N)_n.\eqno(1)$$

The linear form (1) is specified on entry to the routine using the
sparse format. Ordinal numbers of non-basic variables $(x_N)_j$ should
be placed in locations \verb|ind[1]|, \dots, \verb|ind[len]|, where
ordinal numbers 1 to $m$ denote auxiliary variables, and ordinal numbers
$m+1$ to $m+n$ denote structural variables. The corresponding non-zero
coefficients $\alpha_j$ should be placed in locations \verb|val[1]|,
\dots, \verb|val[len]|. The arrays \verb|ind| and \verb|val| are not
changed by the routine.

The parameter \verb|how| specifies in which direction the variable $y$
changes on leaving the basis: $+1$ means increasing, $-1$ means
decreasing.

The parameter \verb|tol| is a relative tolerance (small positive number)
used by the routine to skip small $\alpha_j$ in the form (1).

The routine determines the ordinal number of some non-basic variable
(among specified in \verb|ind[1]|, \dots, \verb|ind[len]|), whose
reduced cost reaches its (zero) bound first before this happens for any
other non-basic variables and which therefore should enter the basis
instead the variable $y$ in order to keep dual feasibility, and returns
it on exit. If the choice cannot be made (i.e. if the adjacent basic
solution is dual unbounded due to $y$), the routine returns zero.

\subsubsection*{Note}

If the basic variable $y$ is presented in the LP problem object, the
row (1) can be computed using the routine \verb|lpx_eval_tab_row|.
Otherwise it can be computed using the routine \verb|lpx_transform_row|.

\subsubsection*{Returns}

The routine \verb|lpx_dual_ratio_test| returns the ordinal number of
some non-basic variable $(x_N)_j$, which should enter the basis instead
the variable $y$ in order to keep dual feasibility. If the adjacent
basic solution is dual unbounded and therefore the choice cannot be
made, the routine returns zero.

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

\newpage

\section{Library environment routines}

\subsection{glp\_long---64-bit integer data type}

Some GLPK API routines use 64-bit integer data type, which is declared
in the header \verb|glpk.h| as follows:

\begin{verbatim}
typedef struct { int lo, hi; } glp_long;
\end{verbatim}

\noindent
where \verb|lo| contains low 32 bits, and \verb|hi| contains high 32
bits of 64-bit integer value.\footnote{GLPK conforms to ILP32, LLP64,
and LP64 programming models, where the built-in type {\tt int}
corresponds to 32-bit integers.}

\subsection{glp\_version---determine library version}

\subsubsection*{Synopsis}

\begin{verbatim}
const char *glp_version(void);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_version| returns a pointer to a null-terminated
character string, which specifies the version of the GLPK library in
the form \verb|"X.Y"|, where `\verb|X|' is the major version number, and
`\verb|Y|' is the minor version number, for example, \verb|"4.16"|.

\subsubsection*{Example}

\begin{verbatim}
printf("GLPK version is %s\n", glp_version());
\end{verbatim}

\subsection{glp\_term\_out---enable/disable terminal output}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_term_out(int flag);
\end{verbatim}

\subsubsection*{Description}

Depending on the parameter flag the routine \verb|glp_term_out| enables
or disables terminal output performed by glpk routines:

\verb|GLP_ON |---enable terminal output;

\verb|GLP_OFF|---disable terminal output.

\subsection{glp\_term\_hook---intercept terminal output}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_term_hook(int (*func)(void *info, const char *s),
      void *info);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_term_hook| installs the user-defined hook routine
to intercept all terminal output performed by GLPK routines.

%This feature can be used to redirect the terminal output to other
%destination, for example, to a file or a text window.

The parameter {\it func} specifies the user-defined hook routine. It is
called from an internal printing routine, which passes to it two
parameters: {\it info} and {\it s}. The parameter {\it info} is a
transit pointer specified in corresponding call to the routine
\verb|glp_term_hook|; it may be used to pass some additional information
to the hook routine. The parameter {\it s} is a pointer to the null
terminated character string, which is intended to be written to the
terminal. If the hook routine returns zero, the printing routine writes
the string {\it s} to the terminal in a usual way; otherwise, if the
hook routine returns non-zero, no terminal output is performed.

To uninstall the hook routine both parameters {\it func} and {\it info}
should be specified as \verb|NULL|.

\subsubsection*{Example}

\begin{verbatim}
static int hook(void *info, const char *s)
{     FILE *foo = info;
      fputs(s, foo);
      return 1;
}

int main(void)
{     FILE *foo;
      . . .
      /* redirect terminal output */
      glp_term_hook(hook, foo);
      . . .
      /* resume terminal output */
      glp_term_hook(NULL, NULL);
      . . .
}
\end{verbatim}

\subsection{glp\_mem\_usage---get memory usage information}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_mem_usage(int *count, int *cpeak, glp_long *total,
      glp_long *tpeak);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_mem_usage| reports some information about
utilization of the memory by GLPK routines. Information is stored to
locations specified by corresponding parameters (see below). Any
parameter can be specified as \verb|NULL|, in which case corresponding
information is not stored.

\verb|*count| is the number of currently allocated memory blocks.

\verb|*cpeak| is the peak value of \verb|*count| reached since the
initialization of the GLPK library environment.

\verb|*total| is the total amount, in bytes, of currently allocated
memory blocks.

\verb|*tpeak| is the peak value of \verb|*total| reached since the
initialization of the GLPK library envirionment.

\subsubsection*{Example}

\begin{verbatim}
glp_mem_usage(&count, NULL, NULL, NULL);
printf("%d memory block(s) are still allocated\n", count);
\end{verbatim}

\subsection{glp\_mem\_limit---set memory usage limit}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_mem_limit(int limit);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_mem_limit| limits the amount of memory available
for dynamic allocation (in GLPK routines) to \verb|limit| megabytes.

\newpage

\subsection{glp\_free\_env---free GLPK library environment}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_free_env(void);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_free_env| frees all resources used by GLPK
routines (memory blocks, etc.) which are currently still in use.

\subsubsection*{Usage notes}

Normally the application program does not need to call this routine,
because GLPK routines always free all unused resources. However, if
the application program even has deleted all problem objects, there
will be several memory blocks still allocated for the internal library
needs. For some reasons the application program may want GLPK to free
this memory, in which case it should call \verb|glp_free_env|.

Note that a call to \verb|glp_free_env| invalidates all problem objects
which still exist.

%* eof *%