glpk05.tex

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

the callback routine should just return.

Optimal solution components for LP relaxation can be obtained with API
routines \verb|glp_get_obj_val|, \verb|glp_get_row_prim|,
\verb|glp_get_row_dual|, \verb|glp_get_col_prim|, and
\verb|glp_get_col_dual|.

\subsubsection*{Request for heuristic solution}

The callback routine is called with the reason code \verb|GLP_IHEUR|
if LP relaxation of the current subproblem being solved to optimality
is integer infeasible (i.e. values of some structural variables of
integer kind are fractional), though its objective value is better than
the best known integer feasible solution.

In response the callback routine may try applying a primal heuristic
to find an integer feasible solution,\footnote{Integer feasible to the
original MIP problem, not to the current subproblem.} which is better
than the best known one. In case of success the callback routine may
store such better solution in the problem object using the routine
\verb|glp_ios_heur_sol|.

\subsubsection*{Request for cut generation}

The callback routine is called with the reason code \verb|GLP_ICUTGEN|
if LP relaxation of the current subproblem being solved to optimality
is integer infeasible (i.e. values of some structural variables of
integer kind are fractional), though its objective value is better than
the best known integer feasible solution.

In response the callback routine may reformulate the {\it current}
subproblem (before it will be splitted up due to branching) by adding to
the problem object one or more {\it cutting plane constraints}, which
cut off the fractional optimal point from the MIP
polytope.\footnote{Since these constraints are added to the current
subproblem, they may be globally as well as locally valid.}

Adding cutting plane constraints may be performed in two ways.
One way is the same as for the reason code \verb|GLP_IROWGEN| (see
above), in which case the callback routine adds new rows corresponding
to cutting plane constraints directly to the current subproblem.

The other way is to add cutting plane constraints to the {\it cut pool},
a set of cutting plane constraints maintained by the solver, rather than
directly to the current subproblem. In this case after return from the
callback routine the solver looks through the cut pool, selects
efficient cutting plane constraints, adds them to the current
subproblem, drops other constraints, and then performs re-optimization.

\subsubsection*{Request for branching}

The callback routine is called with the reason code \verb|GLP_IBRANCH|
if LP relaxation of the current subproblem being solved to optimality
is integer infeasible (i.e. values of some structural variables of
integer kind are fractional), though its objective value is better than
the best known integer feasible solution.

In response the callback routine may choose some variable suitable for
branching (i.e. integer variable, whose value in optimal solution to
LP relaxation of the current subproblem is fractional) and pass its
ordinal number to the solver using the routine
\verb|glp_ios_branch_upon|, in which case the solver splits the current
subproblem in two new subproblems and continues the search. If no choice
is made by the callback routine, the solver uses a branching technique
specified by the control parameter \verb|br_tech|.

\subsubsection*{Better integer solution found}

The callback routine is called with the reason code \verb|GLP_IBINGO|
if LP relaxation of the current subproblem being solved to optimality
is integer feasible (i.e. values of all structural variables of integer
kind are integral within the working precision) and its objective value
is better than the best known integer feasible solution.

Optimal solution components for LP relaxation can be obtained in the
same way as for the reason code \verb|GLP_IROWGEN| (see above).

Components of the new MIP solution can be obtained with API routines
\verb|glp_mip_obj_val|, \verb|glp_mip_row_val|, and
\verb|glp_mip_col_val|. Note, however, that due to row/cut generation
there may be additional rows in the problem object.

The difference between optimal solution to LP relaxation and
corresponding MIP solution is that in the former case some structural
variables of integer kind (namely, basic variables) may have values,
which are close to nearest integers within the working precision, while
in the latter case all such variables have exact integral values.

The reason \verb|GLP_IBINGO| is intended only for informational
purposes, so the callback routine should not modify the problem object
in this case.

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

\newpage

\section{Basic routines}

\subsection{glp\_ios\_reason---determine reason for calling the
callback routine}

\subsubsection*{Synopsis}

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

\subsubsection*{Returns}

The routine \verb|glp_ios_reason| returns a code, which indicates why
the user-defined callback routine is being called:

\verb|GLP_ISELECT|---request for subproblem selection;

\verb|GLP_IPREPRO|---request for preprocessing;

\verb|GLP_IROWGEN|---request for row generation;

\verb|GLP_IHEUR  |---request for heuristic solution;

\verb|GLP_ICUTGEN|---request for cut generation;

\verb|GLP_IBRANCH|---request for branching;

\verb|GLP_IBINGO |---better integer solution found.

\subsection{glp\_ios\_get\_prob---access the problem object}

\subsubsection*{Synopsis}

\begin{verbatim}
glp_prob *glp_ios_get_prob(glp_tree *tree);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_get_prob| can be called from the user-defined
callback routine to access the problem object, which is used by the MIP
solver. It is the original problem object passed to the routine
\verb|glp_intopt| if the MIP presolver is not used; otherwise it is an
internal problem object built by the presolver.

\subsubsection*{Returns}

The routine \verb|glp_ios_get_prob| returns a pointer to the problem
object used by the MIP solver.

\subsubsection*{Comments}

To obtain various information about the problem instance the callback
routine can access the problem object (i.e. the object of type
\verb|glp_prob|) using the routine \verb|glp_ios_get_prob|. It is the
original problem object passed to the routine \verb|glp_intopt| if the
MIP presolver is not used; otherwise it is an internal problem object
built by the presolver.

\subsection{glp\_ios\_row\_attr---determine additional row attributes}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|glp_ios_row_attr| retrieves additional attributes of
$i$-th row of the current subproblem and stores them in the structure
\verb|glp_attr|, which the parameter \verb|attr| points to.

The structure \verb|glp_attr| has the following fields:

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int level}}\\
&Subproblem level at which the row was created. (If \verb|level| = 0,
the row was added either to the original problem object passed to the
routine \verb|glp_intopt| or to the root subproblem on generating
``lazy'' or/and cutting plane constraints.)\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int origin}}\\
&The row origin flag:\\
&\verb|GLP_RF_REG |---regular constraint;\\
&\verb|GLP_RF_LAZY|---``lazy'' constraint;\\
&\verb|GLP_RF_CUT |---cutting plane constraint.\\
\end{tabular}

\medskip

\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
\multicolumn{2}{@{}l}{{\tt int klass}}\\
&The row class descriptor, which is a number passed to the routine
\verb|glp_ios_add_row| as its third parameter. If the row is a cutting
plane constraint generated by the solver, its class may be the
following:\\
&\verb|GLP_RF_GMI |---Gomory's mixed integer cut;\\
&\verb|GLP_RF_MIR |---mixed integer rounding cut;\\
&\verb|GLP_RF_COV |---mixed cover cut;\\
&\verb|GLP_RF_CLQ |---clique cut.\\
\end{tabular}

\newpage

\subsection{glp\_ios\_mip\_gap---compute relative MIP gap}

\subsubsection*{Synopsis}

\begin{verbatim}
double glp_ios_mip_gap(glp_tree *tree);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_mip_gap| computes the relative MIP gap (also
called {\it duality gap}) with the following formula:
$${\tt gap} = \frac{|{\tt best\_mip} - {\tt best\_bnd}|}
{|{\tt best\_mip}| + {\tt DBL\_EPSILON}}$$
where \verb|best_mip| is the best integer feasible solution found so
far, \verb|best_bnd| is the best (global) bound. If no integer feasible
solution has been found yet, \verb|gap| is set to \verb|DBL_MAX|.

\subsubsection*{Returns}

The routine \verb|glp_ios_mip_gap| returns the relative MIP gap.

\subsubsection*{Comments}

The relative MIP gap is used to measure the quality of the best integer
feasible solution found so far, because the optimal solution value
$z^*$ for the original MIP problem always lies in the range
$${\tt best\_bnd}\leq z^*\leq{\tt best\_mip}$$
in case of minimization, or in the range
$${\tt best\_mip}\leq z^*\leq{\tt best\_bnd}$$
in case of maximization.

To express the relative MIP gap in percents the value returned by the
routine \verb|glp_ios_mip_gap| should be multiplied by 100\%.

\newpage

\subsection{glp\_ios\_node\_data---access application-specific data}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|glp_ios_node_data| allows the application accessing a
memory block allocated for the subproblem (which may be active or
inactive), whose reference number is $p$.

The size of the block is defined by the control parameter \verb|cb_size|
passed to the routine \verb|glp_intopt|. The block is initialized by
binary zeros on creating corresponding subproblem, and its contents is
kept until the subproblem will be removed from the tree.

The application may use these memory blocks to store specific data for
each subproblem.

\subsubsection*{Returns}

The routine \verb|glp_ios_node_data| returns a pointer to the memory
block for the specified subproblem. Note that if \verb|cb_size| = 0, the
routine returns a null pointer.

\subsection{glp\_ios\_select\_node---select subproblem to continue
the search}

\subsubsection*{Synopsis}

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

\subsubsection*{Description}

The routine \verb|glp_ios_select_node| can be called from the
user-defined callback routine in response to the reason
\verb|GLP_ISELECT| to select an active subproblem, whose reference
number is $p$. The search will be continued from the subproblem
selected.

\newpage

\subsection{glp\_ios\_heur\_sol---provide solution found by heuristic}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_heur_sol(glp_tree *tree, const double x[]);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_heur_sol| can be called from the user-defined
callback routine in response to the reason \verb|GLP_IHEUR| to provide
an integer feasible solution found by a primal heuristic.

Primal values of {\it all} variables (columns) found by the heuristic
should be placed in locations $x[1]$, \dots, $x[n]$, where $n$ is the
number of columns in the original problem object. Note that the routine
\verb|glp_ios_heur_sol| does {\it not} check primal feasibility of the
solution provided.

Using the solution passed in the array $x$ the routine computes value
of the objective function. If the objective value is better than the
best known integer feasible solution, the routine computes values of
auxiliary variables (rows) and stores all solution components in the
problem object.

\subsubsection*{Returns}

If the provided solution is accepted, the routine
\verb|glp_ios_heur_sol| returns zero. Otherwise, if the provided
solution is rejected, the routine returns non-zero.

\subsection{glp\_ios\_can\_branch---check if can branch upon specified
variable}

\subsubsection*{Synopsis}

\begin{verbatim}
int glp_ios_can_branch(glp_tree *tree, int j);
\end{verbatim}

\subsubsection*{Returns}

If $j$-th variable (column) can be used to branch upon, the routine
returns non-zero, otherwise zero.

\newpage

\subsection{glp\_ios\_branch\_upon---choose variable to branch upon}

\subsubsection*{Synopsis}

\begin{verbatim}
void glp_ios_branch_upon(glp_tree *tree, int j, int sel);
\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_ios_branch_upon| can be called from the
user-defined callback routine in response to the reason
\verb|GLP_IBRANCH| to choose a branching variable, whose ordinal number
is $j$. Should note that only variables, for which the routine
\verb|glp_ios_can_branch| returns non-zero, can be used to branch upon.

The parameter \verb|sel| is a flag that indicates which branch
(subproblem) should be selected next to continue the search:

\verb|GLP_DN_BRNCH|---select down-branch;

\verb|GLP_UP_BRNCH|---select up-branch;

\verb|GLP_NO_BRNCH|---use general selection technique.

\subsubsection*{Comments}

On branching the solver removes the current active subproblem from the
active list and creates two new subproblems ({\it down-} and {\it
up-branches}), which are added to the end of the active list. Note that
the down-branch is created before the up-branch, so the last active
subproblem will be the up-branch.

The down- and up-branches are identical to the current subproblem with
exception that in the down-branch the upper bound of $x_j$, the variable