glpk05.tex

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

chosen to branch upon, is replaced by $\lfloor x_j^*\rfloor$, while in
the up-branch the lower bound of $x_j$ is replaced by
$\lceil x_j^*\rceil$, where $x_j^*$ is the value of $x_j$ in optimal
solution to LP relaxation of the current subproblem. For example, if
$x_j^*=3.14$, the new upper bound of $x_j$ in the down-branch is
$\lfloor 3.14\rfloor=3$, and the new lower bound in the up-branch is
$\lceil 3.14\rceil=4$.)

Additionally the callback routine may select either down- or up-branch,
from which the solver will continue the search. If none of the branches
is selected, a general selection technique will be used.

\newpage

\subsection{glp\_ios\_terminate---terminate the solution process}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_ios_terminate(glp_tree *tree);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_terminate| sets a flag indicating that the
MIP solver should prematurely terminate the search.

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

\newpage

\section{The search tree exploring routines}

\subsection{glp\_ios\_tree\_size---determine size of the search tree}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,
      int *t_cnt);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_tree_size| stores the following three counts
which characterize the current size of the search tree:

\verb|a_cnt| is the current number of active nodes, i.e. the current
size of the active list;

\verb|n_cnt| is the current number of all (active and inactive) nodes;

\verb|t_cnt| is the total number of nodes including those which have
been already removed from the tree. This count is increased whenever
a new node appears in the tree and never decreased.

If some of the parameters \verb|a_cnt|, \verb|n_cnt|, \verb|t_cnt| is
a null pointer, the corresponding count is not stored.

\subsection{glp\_ios\_curr\_node---determine current active
subproblem}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_curr_node(glp_tree *tree);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ios_curr_node| returns the reference number of the
current active subproblem. However, if the current subproblem does not
exist, the routine returns zero.

\newpage

\subsection{glp\_ios\_next\_node---determine next active subproblem}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_next_node(glp_tree *tree, int p);
\end{verbatim}

\subsubsection*{Returns}

If the parameter $p$ is zero, the routine \verb|glp_ios_next_node|
returns the reference number of the first active subproblem. However,
if the tree is empty, zero is returned.

If the parameter $p$ is not zero, it must specify the reference number
of some active subproblem, in which case the routine returns the
reference number of the next active subproblem. However, if there is
no next active subproblem in the list, zero is returned.

All subproblems in the active list are ordered chronologically, i.e.
subproblem $A$ precedes subproblem $B$ if $A$ was created before $B$.

\subsection{glp\_ios\_prev\_node---determine previous active
subproblem}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_prev_node(glp_tree *tree, int p);
\end{verbatim}

\subsubsection*{Returns}

If the parameter $p$ is zero, the routine \verb|glp_ios_prev_node|
returns the reference number of the last active subproblem. However, if
the tree is empty, zero is returned.

If the parameter $p$ is not zero, it must specify the reference number
of some active subproblem, in which case the routine returns the
reference number of the previous active subproblem. However, if there
is no previous active subproblem in the list, zero is returned.

All subproblems in the active list are ordered chronologically, i.e.
subproblem $A$ precedes subproblem $B$ if $A$ was created before $B$.

\newpage

\subsection{glp\_ios\_up\_node---determine parent subproblem}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_up_node(glp_tree *tree, int p);
\end{verbatim}

\subsubsection*{Returns}

The parameter $p$ must specify the reference number of some (active or
inactive) subproblem, in which case the routine \verb|iet_get_up_node|
returns the reference number of its parent subproblem. However, if the
specified subproblem is the root of the tree and, therefore, has
no parent, the routine returns zero.

\subsection{glp\_ios\_node\_level---determine subproblem level}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_node_level(glp_tree *tree, int p);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ios_node_level| returns the level of the
subproblem,\linebreak whose reference number is $p$, in the
branch-and-bound tree. (The root subproblem has level 0, and the level
of any other subproblem is the level of its parent plus one.)

\subsection{glp\_ios\_node\_bound---determine subproblem local\\bound}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_ios_node_bound(glp_tree *tree, int p);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ios_node_bound| returns the local bound for
(active or inactive) subproblem, whose reference number is $p$.

\subsubsection*{Comments}

The local bound for subproblem $p$ is an lower (minimization) or upper
(maximization) bound for integer optimal solution to {\it this}
subproblem (not to the original problem). This bound is local in the
sense that only subproblems in the subtree rooted at node $p$ cannot
have better integer feasible solutions.

On creating a subproblem (due to the branching step) its local bound is
inherited from its parent and then may get only stronger (never weaker).
For the root subproblem its local bound is initially set to
\verb|-DBL_MAX| (minimization) or \verb|+DBL_MAX| (maximization) and
then improved as the root LP relaxation has been solved.

Note that the local bound is not necessarily the optimal objective value
to corresponding LP relaxation.

\subsection{glp\_ios\_best\_node---find active subproblem with best
local bound}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_best_node(glp_tree *tree);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ios_best_node| returns the reference number of
the active subproblem, whose local bound is best (i.e. smallest in case
of minimization or largest in case of maximization). However, if the
tree is empty, the routine returns zero.

\subsubsection*{Comments}

The best local bound is an lower (minimization) or upper (maximization)
bound for integer optimal solution to the original MIP problem.

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

\newpage

\section{The cut pool routines}

\subsection{glp\_ios\_pool\_size---determine current size of the cut\\
pool}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_pool_size(glp_tree *tree);
\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_ios_pool_size| returns the current size of the
cut pool, that is, the number of cutting plane constraints currently
added to it.

\subsection{glp\_ios\_add\_row---add constraint to the cut pool}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_add_row(glp_tree *tree, const char *name,
      int klass, int flags, int len, const int ind[],
      const double val[], int type, double rhs);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_add_row| adds specified row (cutting plane
constraint) to the cut pool.

The cutting plane constraint should have the following format:
$$\sum_{j\in J}a_jx_j\left\{\begin{array}{@{}c@{}}\geq\\\leq\\
\end{array}\right\}b,$$
where $J$ is a set of indices (ordinal numbers) of structural variables,
$a_j$ are constraint coefficients, $x_j$ are structural variables, $b$
is the right-hand side.

The parameter \verb|name| specifies a symbolic name assigned to the
constraint (1 up to 255 characters). If it is \verb|NULL| or an empty
string, no name is assigned.

The parameter \verb|klass| specifies the constraint class, which must
be either zero or a number in the range from 101 to 200. The application
may use this attribute to distinguish between cutting plane constraints
of different classes.\footnote{Constraint classes numbered from 1 to 100
are reserved for GLPK cutting plane generators.}

The parameter \verb|flags| currently is not used and must be zero.

Ordinal numbers of structural variables (i.e. column indices) $j\in J$
and numerical values of corresponding constraint coefficients $a_j$ must
be placed in locations \verb|ind[1]|, \dots, \verb|ind[len]| and
\verb|val[1]|, \dots, \verb|val[len]|, respectively, where
${\tt len}=|J|$ is the number of constraint coefficients,
$0\leq{\tt len}\leq n$, and $n$ is the number of columns in the problem
object. Coefficients with identical column indices are not allowed.
Zero coefficients are allowed, however, they are ignored.

The parameter \verb|type| specifies the constraint type as follows:

\verb|GLP_LO| means inequality constraint $\Sigma a_jx_j\geq b$;

\verb|GLP_UP| means inequality constraint $\Sigma a_jx_j\leq b$;

The parameter \verb|rhs| specifies the right-hand side $b$.

All cutting plane constraints in the cut pool are identified by their
ordinal numbers 1, 2, \dots, $size$, where $size$ is the current size
of the cut pool. New constraints are always added to the end of the cut
pool, thus, ordinal numbers of previously added constraints are not
changed.

\subsubsection*{Returns}

The routine \verb|glp_ios_add_row| returns the ordinal number of the
cutting plane constraint added, which is the new size of the cut pool.

\subsubsection*{Example}

\begin{verbatim}
/* generate triangle cutting plane:
   x[i] + x[j] + x[k] <= 1 */
. . .
/* add the constraint to the cut pool */
ind[1] = i, val[1] = 1.0;
ind[2] = j, val[2] = 1.0;
ind[3] = k, val[3] = 1.0;
glp_ios_add_row(tree, NULL, TRIANGLE_CUT, 0, 3, ind, val,
                GLP_UP, 1.0);
\end{verbatim}

\subsubsection*{Comments}

Cutting plane constraints added to the cut pool are intended to be then
added only to the {\it current} subproblem, so these constraints can be
globally as well as locally valid. However, adding a constraint to the
cut pool does not mean that it will be added to the current
subproblem---it depends on the solver's decision: if the constraint
seems to be efficient, it is moved from the pool to the current
subproblem, otherwise it is simply dropped.\footnote{Globally valid
constraints could be saved and then re-used for other subproblems, but
currently such feature is not implemented.}

Normally, every time the callback routine is called for cut generation,
the cut pool is empty. On the other hand, the solver itself can generate
cutting plane constraints (like Gomory's or mixed integer rounding
cuts), in which case the cut pool may be non-empty.

\subsection{glp\_ios\_del\_row---remove constraint from the cut pool}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_ios_del_row(glp_tree *tree, int i);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_del_row| deletes $i$-th row (cutting plane
constraint) from the cut pool, where $1\leq i\leq size$ is the ordinal
number of the constraint in the pool, $size$ is the current size of the
cut pool.

Note that deleting a constraint from the cut pool leads to changing
ordinal numbers of other constraints remaining in the pool. New ordinal
numbers of the remaining constraints are assigned under assumption that
the original order of constraints is not changed. Let, for example,
there be four constraints $a$, $b$, $c$ and $d$ in the cut pool, which
have ordinal numbers 1, 2, 3 and 4, respectively, and let constraint
$b$ have been deleted. Then after deletion the remaining constraint $a$,
$c$ and $d$ are assigned new ordinal numbers 1, 2 and 3, respectively.

To find the constraint to be deleted the routine \verb|glp_ios_del_row|
uses ``smart'' linear search, so it is recommended to remove constraints
in a natural or reverse order and avoid removing them in a random order.

\subsubsection*{Example}

\begin{verbatim}
/* keep first 10 constraints in the cut pool and remove other
   constraints */
while (glp_ios_pool_size(tree) > 10)
   glp_ios_del_row(tree, glp_ios_pool_size(tree));
\end{verbatim}

\newpage

\subsection{glp\_ios\_clear\_pool---remove all constraints from the
cut pool}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_ios_clear_pool(glp_tree *tree);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_clear_pool| makes the cut pool empty deleting
all existing rows (cutting plane constraints) from it.

%* eof *%