glpk02.tex

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

\\
&Tolerance used to check if the basic solution is primal feasible.
(Do not change this parameter without detailed understanding its
purpose.)\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double tol\_dj} (default: {\tt 1e-7})}
\\
&Tolerance used to check if the basic solution is dual feasible.
(Do not change this parameter without detailed understanding its
purpose.)\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double tol\_piv} (default: {\tt 1e-10})}
\\
&Tolerance used to choose eligble pivotal elements of the simplex table.
(Do not change this parameter without detailed understanding its
purpose.)\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double obj\_ll} (default: {\tt -DBL\_MAX})}
\\
&Lower limit of the objective function. If the objective function
reaches this limit and continues decreasing, the solver terminates the
search. (Used in the dual simplex only.)\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt double obj\_ul} (default: {\tt +DBL\_MAX})}
\\
&Upper limit of the objective function. If the objective function
reaches this limit and continues increasing, the solver terminates the
search. (Used in the dual simplex only.)\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int it\_lim} (default: {\tt INT\_MAX})}
\\
&Simplex iteration limit.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int tm\_lim} (default: {\tt INT\_MAX})}
\\
&Searching time limit, in milliseconds.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int out\_frq} (default: {\tt 200})}
\\
&Output frequency, in iterations. This parameter specifies how
frequently the solver sends information about the solution process to
the terminal.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int out\_dly} (default: {\tt 0})}
\\
&Output delay, in milliseconds. This parameter specifies how long the
solver should delay sending information about the solution process to
the terminal.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int presolve} (default: {\tt GLP\_OFF})}
\\
&LP presolver option:\\
&\verb|GLP_ON |---enable using the LP presolver;\\
&\verb|GLP_OFF|---disable using the LP presolver.\\
\end{tabular}

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

\subsection{glp\_exact---solve LP problem in exact arithmetic}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|glp_exact| is a tentative implementation of the
primal two-phase simplex method based on exact (rational) arithmetic.
It is similar to the routine \verb|glp_simplex|, however, for all
internal computations it uses arithmetic of rational numbers, which is
exact in mathematical sense, i.e. free of round-off errors unlike
floating-point arithmetic.

Note that the routine \verb|glp_exact| uses only two control parameters
passed in the structure \verb|glp_smcp|, namely, \verb|it_lim| and
\verb|tm_lim|.

\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 exactly singular.\\
\verb|GLP_EBOUND| & Unable to start the search, because some
double-bounded (auxiliary or structural) variables have incorrect
bounds.\\
\verb|GLP_EFAIL| & The problem instance has no rows/columns.\\
\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.\\
\end{tabular}

\subsubsection*{Comments}

Computations in exact arithmetic are very time consuming, so solving
LP problem with the routine \verb|glp_exact| from the very beginning is
not a good idea. It is much better at first to find an optimal basis
with the routine \verb|glp_simplex| and only then to call
\verb|glp_exact|, in which case only a few simplex iterations need to
be performed in exact arithmetic.

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

\subsection{glp\_init\_smcp---initialize simplex method control
parameters}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_init_smcp(glp_smcp *parm);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_init_smcp| initializes control parameters, which
are used by the simplex solver, with default values.

Default values of the control parameters are stored in a \verb|glp_smcp|
structure, which the parameter \verb|parm| points to.

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

\newpage

\subsection{glp\_get\_status---retrieve generic status of basic
solution}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_get_status| reports the generic status of the
current basic solution for the specified problem object as follows:

\begin{tabular}{@{}ll}
\verb|GLP_OPT|    & solution is optimal; \\
\verb|GLP_FEAS|   & solution is feasible; \\
\verb|GLP_INFEAS| & solution is infeasible; \\
\verb|GLP_NOFEAS| & problem has no feasible solution; \\
\verb|GLP_UNBND|  & problem has unbounded solution; \\
\verb|GLP_UNDEF|  & solution is undefined. \\
\end{tabular}

More detailed information about the status of basic solution can be
retrieved with the routines \verb|glp_get_prim_stat| and
\verb|glp_get_dual_stat|.

\subsection{glp\_get\_prim\_stat---retrieve status of primal basic
solution}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_get_prim_stat| reports the status of the primal
basic solution for the specified problem object as follows:

\begin{tabular}{@{}ll}
\verb|GLP_UNDEF|  & primal solution is undefined; \\
\verb|GLP_FEAS|   & primal solution is feasible; \\
\verb|GLP_INFEAS| & primal solution is infeasible; \\
\verb|GLP_NOFEAS| & no primal feasible solution exists. \\
\end{tabular}

\newpage

\subsection{glp\_get\_dual\_stat---retrieve status of dual basic
solution}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_get_dual_stat| reports the status of the dual
basic solution for the specified problem object as follows:

\begin{tabular}{@{}ll}
\verb|GLP_UNDEF|  & dual solution is undefined; \\
\verb|GLP_FEAS|   & dual solution is feasible; \\
\verb|GLP_INFEAS| & dual solution is infeasible; \\
\verb|GLP_NOFEAS| & no dual feasible solution exists. \\
\end{tabular}

\subsection{glp\_get\_obj\_val---retrieve objective value}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_get_obj_val(glp_prob *lp);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_get_obj_val| returns current value of the
objective function.

\subsection{glp\_get\_row\_stat---retrieve row status}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_get_row_stat| returns current status assigned to
the auxiliary variable associated with \verb|i|-th row as follows:

\begin{tabular}{@{}ll}
\verb|GLP_BS| & basic variable; \\
\verb|GLP_NL| & non-basic variable on its lower bound; \\
\verb|GLP_NU| & non-basic variable on its upper bound; \\
\verb|GLP_NF| & non-basic free (unbounded) variable; \\
\verb|GLP_NS| & non-basic fixed variable. \\
\end{tabular}

\subsection{glp\_get\_row\_prim---retrieve row primal value}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_get_row_prim| returns primal value of the
auxiliary variable associated with \verb|i|-th row.

\subsection{glp\_get\_row\_dual---retrieve row dual value}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_get_row_dual| returns dual value (i.e. reduced
cost) of the auxiliary variable associated with \verb|i|-th row.

\subsection{glp\_get\_col\_stat---retrieve column status}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_get_col_stat| returns current status assigned to
the structural variable associated with \verb|j|-th column as follows:

\begin{tabular}{@{}ll}
\verb|GLP_BS| & basic variable; \\
\verb|GLP_NL| & non-basic variable on its lower bound; \\
\verb|GLP_NU| & non-basic variable on its upper bound; \\
\verb|GLP_NF| & non-basic free (unbounded) variable; \\
\verb|GLP_NS| & non-basic fixed variable. \\
\end{tabular}

\newpage

\subsection{glp\_get\_col\_prim---retrieve column primal value}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_get_col_prim| returns primal value of the
structural variable associated with \verb|j|-th column.

\subsection{glp\_get\_col\_dual---retrieve column dual value}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_get_col_dual| returns dual value (i.e. reduced
cost) of the structural variable associated with \verb|j|-th column.

\subsection{glp\_get\_unbnd\_ray---determine variable causing\\
unboundedness}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_get_unbnd_ray| returns the number $k$ of
a variable, which causes primal or dual unboundedness.
If $1\leq k\leq m$, it is $k$-th auxiliary variable, and if
$m+1\leq k\leq m+n$, it is $(k-m)$-th structural variable, where $m$ is
the number of rows, $n$ is the number of columns in the problem object.
If such variable is not defined, the routine returns 0.

\subsubsection*{Comments}

If it is not exactly known which version of the simplex solver
detected unboundedness, i.e. whether the unboundedness is primal or
dual, it is sufficient to check the status of the variable
with the routine \verb|glp_get_row_stat| or \verb|glp_get_col_stat|.
If the variable is non-basic, the unboundedness is primal, otherwise,
if the variable is basic, the unboundedness is dual (the latter case
means that the problem has no primal feasible dolution).

\subsection{lpx\_check\_kkt---check Karush-Kuhn-Tucker optimality
conditions}

\subsubsection*{Synopsis}

\begin{verbatim}
void lpx_check_kkt(glp_prob *lp, int scaled, LPXKKT *kkt);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|lpx_check_kkt| checks Karush-Kuhn-Tucker optimality
conditions for basic solution. It is assumed that both primal and dual
components of basic solution are valid.

If the parameter \verb|scaled| is zero, the optimality conditions are
checked for the original, unscaled LP problem. Otherwise, if the
parameter \verb|scaled| is non-zero, the routine checks the conditions
for an internally scaled LP problem.

The paramete