glpk02.tex

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

assigning appropriate statuses to auxiliary and structural variables.
Another way to construct an initial basis is to use API routines like
\verb|glp_adv_basis|, which implement so called
{\it crashing}.\footnote{This term is from early linear programming
systems and means a heuristic to construct a valid initial basis.} Note
that on normal exit the simplex solver remains the basis valid, so in
case of reoptimization there is no need to construct an initial basis
from scratch.

\subsection{glp\_set\_row\_stat---set (change) row status}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_row_stat(glp_prob *lp, int i, int stat);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_row_stat| sets (changes) the current status
of \verb|i|-th row (auxiliary variable) as specified by the parameter
\verb|stat|:

\begin{tabular}{@{}lp{104.2mm}@{}}
\verb|GLP_BS| & make the row basic (make the constraint inactive); \\
\verb|GLP_NL| & make the row non-basic (make the constraint active); \\
\end{tabular}

\newpage

\begin{tabular}{@{}lp{104.2mm}@{}}
\verb|GLP_NU| & make the row non-basic and set it to the upper bound;
   if the row is not double-bounded, this status is equivalent to
   \verb|GLP_NL| (only in the case of this routine); \\
\verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this
   routine); \\
\verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this
   routine). \\
\end{tabular}

\subsection{glp\_set\_col\_stat---set (change) column status}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_set_col_stat(glp_prob *lp, int j, int stat);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_col_stat sets| (changes) the current status
of \verb|j|-th column (structural variable) as specified by the
parameter \verb|stat|:

\begin{tabular}{@{}lp{104.2mm}@{}}
\verb|GLP_BS| & make the column basic; \\
\verb|GLP_NL| & make the column non-basic; \\
\verb|GLP_NU| & make the column non-basic and set it to the upper
   bound; if the column is not double-bounded, this status is equivalent
   to \verb|GLP_NL| (only in the case of this routine); \\
\verb|GLP_NF| & the same as \verb|GLP_NL| (only in the case of this
   routine); \\
\verb|GLP_NS| & the same as \verb|GLP_NL| (only in the case of this
   routine).
\end{tabular}

\subsection{glp\_std\_basis---construct standard initial LP basis}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|glp_std_basis| constructs the ``standard'' (trivial)
initial LP basis for the specified problem object.

In the ``standard'' LP basis all auxiliary variables (rows) are basic,
and all structural variables (columns) are non-basic (so the
corresponding basis matrix is unity).

\newpage

\subsection{glp\_adv\_basis---construct advanced initial LP basis}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|glp_adv_basis| constructs an advanced initial LP
basis for the specified problem object.

The parameter \verb|flags| is reserved for use in the future and must
be specified as zero.

In order to construct the advanced initial LP basis the routine does
the following:

1) includes in the basis all non-fixed auxiliary variables;

2) includes in the basis as many non-fixed structural variables as
possible keeping the triangular form of the basis matrix;

3) includes in the basis appropriate (fixed) auxiliary variables to
complete the basis.

As a result the initial LP basis has as few fixed variables as possible
and the corresponding basis matrix is triangular.

\subsection{glp\_cpx\_basis---construct Bixby's initial LP basis}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|glp_cpx_basis| constructs an initial basis for the
specified problem object with the algorithm proposed by
R.~Bixby.\footnote{Robert E. Bixby, ``Implementing the Simplex Method:
The Initial Basis.'' ORSA Journal on Computing, Vol. 4, No. 3, 1992,
pp. 267-84.}

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

\newpage

\section{Simplex method routines}

The {\it simplex method} is a well known efficient numerical procedure
to solve LP problems.

On each iteration the simplex method transforms the original system of
equaility constraints (1.2) resolving them through different sets of
variables to an equivalent system called {\it the simplex table} (or
sometimes {\it the simplex tableau}), which has the following form:
$$
\begin{array}{r@{\:}c@{\:}r@{\:}c@{\:}r@{\:}c@{\:}r}
z&=&d_1(x_N)_1&+&d_2(x_N)_2&+ \dots +&d_n(x_N)_n \\
(x_B)_1&=&\xi_{11}(x_N)_1& +& \xi_{12}(x_N)_2& + \dots +&
   \xi_{1n}(x_N)_n \\
(x_B)_2&=& \xi_{21}(x_N)_1& +& \xi_{22}(x_N)_2& + \dots +&
   \xi_{2n}(x_N)_n \\
\multicolumn{7}{c}
{.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .} \\
(x_B)_m&=&\xi_{m1}(x_N)_1& +& \xi_{m2}(x_N)_2& + \dots +&
   \xi_{mn}(x_N)_n \\
\end{array} \eqno (2.1)
$$
where: $(x_B)_1, (x_B)_2, \dots, (x_B)_m$ are basic variables;
$(x_N)_1, (x_N)_2, \dots, (x_N)_n$ are non-basic variables;
$d_1, d_2, \dots, d_n$ are reduced costs;
$\xi_{11}, \xi_{12}, \dots, \xi_{mn}$ are coefficients of the
simplex table. (May note that the original LP problem (1.1)---(1.3) also
has the form of a simplex table, where all equalities are resolved
through auxiliary variables.)

From the linear programming theory it is known that if an optimal
solution of the LP problem (1.1)---(1.3) exists, it can always be
written in the form (2.1), where non-basic variables are set on their
bounds while values of the objective function and basic variables are
determined by the corresponding equalities of the simplex table.

A set of values of all basic and non-basic variables determined by the
simplex table is called {\it basic solution}. If all basic variables are
within their bounds, the basic solution is called {\it (primal)
feasible}, otherwise it is called {\it (primal) infeasible}. A feasible
basic solution, which provides a smallest (in case of minimization) or
a largest (in case of maximization) value of the objective function is
called {\it optimal}. Therefore, for solving LP problem the simplex
method tries to find its optimal basic solution.

Primal feasibility of some basic solution may be stated by simple
checking if all basic variables are within their bounds. Basic solution
is optimal if additionally the following optimality conditions are
satisfied for all non-basic variables:
\begin{center}
\begin{tabular}{lcc}
Status of $(x_N)_j$ & Minimization & Maximization \\
\hline
$(x_N)_j$ is free & $d_j = 0$ & $d_j = 0$ \\
$(x_N)_j$ is on its lower bound & $d_j \geq 0$ & $d_j \leq 0$ \\
$(x_N)_j$ is on its upper bound & $d_j \leq 0$ & $d_j \geq 0$ \\
\end{tabular}
\end{center}
In other words, basic solution is optimal if there is no non-basic
variable, which changing in the feasible direction (i.e. increasing if
it is free or on its lower bound, or decreasing if it is free or on its
upper bound) can improve (i.e. decrease in case of minimization or
increase in case of maximization) the objective function.

If all non-basic variables satisfy to the optimality conditions shown
above (independently on whether basic variables are within their bounds
or not), the basic solution is called {\it dual feasible}, otherwise it
is called {\it dual infeasible}.

It may happen that some LP problem has no primal feasible solution due
to incorrect formulation---this means that its constraints conflict
with each other. It also may happen that some LP problem has unbounded
solution again due to incorrect formulation---this means that some
non-basic variable can improve the objective function, i.e. the
optimality conditions are violated, and at the same time this variable
can infinitely change in the feasible direction meeting no resistance
from basic variables. (May note that in the latter case the LP problem
has no dual feasible solution.)

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

\subsection{glp\_simplex---solve LP problem with the primal or dual
simplex method}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_simplex(glp_prob *lp, const glp_smcp *parm);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_simplex| is a driver to the LP solver based on
the simplex method. This routine retrieves problem data from the
specified problem object, calls the solver to solve the problem
instance, and stores results of computations back into the problem
object.

The simplex solver has a set of control parameters. Values of the
control parameters can be passed in the structure \verb|glp_smcp|,
which the parameter \verb|parm| points to. For detailed description of
this structure see paragraph ``Control parameters'' below.
Before specifying some control parameters the application program
should initialize the structure \verb|glp_smcp| by default values of
all control parameters using the routine \verb|glp_init_smcp| (see the
next subsection). This is needed for backward compatibility, because in
the future there may appear new members in the structure
\verb|glp_smcp|.

The parameter \verb|parm| can be specified as \verb|NULL|, in which
case the solver uses default settings.

\subsubsection*{Returns}

\def\arraystretch{1}

\begin{tabular}{@{}p{25mm}p{97.3mm}@{}}
0 & The LP problem instance has been successfully solved. (This code
does {\it not} necessarily mean that the solver has found optimal
solution. It only means that the solution process was successful.) \\
\verb|GLP_EBADB| & Unable to start the search, because the initial basis
specified in the problem object is invalid---the number of basic
(auxiliary and structural) variables is not the same as the number of
rows in the problem object.\\
\verb|GLP_ESING| & Unable to start the search, because the basis matrix
corresponding to the initial basis is singular within the working
precision.\\
\verb|GLP_ECOND| & Unable to start the search, because the basis matrix
corresponding to the initial basis is ill-conditioned, i.e. its
condition number is too large.\\
\verb|GLP_EBOUND| & Unable to start the search, because some
double-bounded (auxiliary or structural) variables have incorrect
bounds.\\
\verb|GLP_EFAIL| & The search was prematurely terminated due to the
solver failure.\\
\verb|GLP_EOBJLL| & The search was prematurely terminated, because the
objective function being maximized has reached its lower limit and
continues decreasing (the dual simplex only).\\
\verb|GLP_EOBJUL| & The search was prematurely terminated, because the
objective function being minimized has reached its upper limit and
continues increasing (the dual simplex only).\\
\verb|GLP_EITLIM| & The search was prematurely terminated, because the
simplex iteration limit has been exceeded.\\
\verb|GLP_ETMLIM| & The search was prematurely terminated, because the
time limit has been exceeded.\\
\verb|GLP_ENOPFS| & The LP problem instance has no primal feasible
solution (only if the LP presolver is used).\\
\verb|GLP_ENODFS| & The LP problem instance has no dual feasible
solution (only if the LP presolver is used).\\
\end{tabular}

\subsubsection*{Built-in LP presolver}

The simplex solver has {\it built-in LP presolver}. It is a subprogram
that transforms the original LP problem specified in the problem object
to an equivalent LP problem, which may be easier for solving with the
simplex method than the original one. This is attained mainly due to
reducing the problem size and improving its numeric properties (for
example, by removing some inactive constraints or by fixing some
non-basic variables). Once the transformed LP problem has been solved,
the presolver transforms its basic solution back to the corresponding
basic solution of the original problem.

Presolving is an optional feature of the routine \verb|glp_simplex|,
and by default it is disabled. In order to enable the LP presolver the
control parameter \verb|presolve| should be set to \verb|GLP_ON| (see
paragraph ``Control parameters'' below). Presolving may be used when
the problem instance is solved for the first time. However, on
performing re-optimization the presolver should be disabled.

The presolving procedure is transparent to the API user in the sense
that all necessary processing is performed internally, and a basic
solution of the original problem recovered by the presolver is the same
as if it were computed directly, i.e. without presolving.

Note that the presolver is able to recover only optimal solutions. If
a computed solution is infeasible or non-optimal, the corresponding
solution of the original problem cannot be recovered and therefore
remains undefined. If you need to know a basic solution even if it is
infeasible or non-optimal, the presolver should be disabled.

\subsubsection*{Terminal output}

Solving large problem instances may take a long time, so the solver
reports some information about the current basic solution, which is sent
to the terminal. This information has the following format:

\begin{verbatim}
nnn:  obj = xxx  infeas = yyy (ddd)
\end{verbatim}

\noindent
where: `\verb|nnn|' is the iteration number, `\verb|xxx|' is the
current value of the objective function (it is is unscaled and has
correct sign); `\verb|yyy|' is the current sum of primal or dual
infeasibilities (it is scaled and therefore may be used only for visual
estimating), `\verb|ddd|' is the current number of fixed basic
variables.

The symbol preceding the iteration number indicates which phase of the
simplex method is in effect:

{\it Blank} means that the solver is searching for primal feasible
solution using the primal simplex or for dual feasible solution using
the dual simplex;

{\it Asterisk} (\verb|*|) means that the solver is searching for
optimal solution using the primal simplex;

{\it Vertical dash} (\verb/|/) means that the solver is searching for
optimal solution using the dual simplex.

\subsubsection*{Control parameters}

This paragraph describes all control parameters currently used in the
simplex solver. Symbolic names of control parameters are names of
corresponding members in the structure \verb|glp_smcp|.

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int msg\_lev} (default: {\tt GLP\_MSG\_ALL})}
\\
&Message level for terminal output:\\
&\verb|GLP_MSG_OFF|---no output;\\
&\verb|GLP_MSG_ERR|---error and warning messages only;\\
&\verb|GLP_MSG_ON |---normal output;\\
&\verb|GLP_MSG_ALL|---full output (including informational messages).
\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int meth} (default: {\tt GLP\_PRIMAL})}
\\
&Simplex method option:\\
&\verb|GLP_PRIMAL|---use two-phase primal simplex;\\
&\verb|GLP_DUAL  |---use two-phase dual simplex;\\
&\verb|GLP_DUALP |---use two-phase dual simplex, and if it fails,
switch to the\\
&\verb|            |$\:$ primal simplex.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int pricing} (default: {\tt GLP\_PT\_PSE})}
\\
&Pricing technique:\\
&\verb|GLP_PT_STD|---standard (textbook);\\
&\verb|GLP_PT_PSE|---projected steepest edge.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int r\_test} (default: {\tt GLP\_RT\_HAR})}
\\
&Ratio test technique:\\
&\verb|GLP_RT_STD|---standard (textbook);\\
&\verb|GLP_RT_HAR|---Harris' two-pass ratio test.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double tol\_bnd} (default: {\tt 1e-7})}