source: glpk-cmake/doc/glpk05.tex @ 1:c445c931472f

%* glpk05.tex *%

\chapter{Branch-and-Cut API Routines}

\section{Introduction}

\subsection{Using the callback routine}

The GLPK MIP solver based on the branch-and-cut method allows the
application program to control the solution process. This is attained
by means of the user-defined callback routine, which is called by the
solver at various points of the branch-and-cut algorithm.

The callback routine passed to the MIP solver should be written by the
user and has the following specification:\footnote{The name
{\tt foo\_bar} used here is a placeholder for the callback routine
name.}

\begin{verbatim}
   void foo_bar(glp_tree *tree, void *info);
\end{verbatim}

\noindent
where \verb|tree| is a pointer to the data structure \verb|glp_tree|,
which should be used on subsequent calls to branch-and-cut interface
routines, and \verb|info| is a transit pointer passed to the routine
\verb|glp_intopt|, which may be used by the application program to pass
some external data to the callback routine.

The callback routine is passed to the MIP solver through the control
parameter structure \verb|glp_iocp| (see Chapter ``Basic API Routines'',
Section ``Mixed integer programming routines'', Subsection ``Solve MIP
problem with the branch-and-cut method'') as follows:

\newpage

\begin{verbatim}
   glp_prob *mip;
   glp_iocp parm;
   . . .
   glp_init_iocp(&parm);
   . . .
   parm.cb_func = foo_bar;
   parm.cb_info = ... ;
   ret = glp_intopt(mip, &parm);
   . . .
\end{verbatim}

To determine why it is being called by the MIP solver the callback
routine should use the routine \verb|glp_ios_reason| (described in this
section below), which returns a code indicating the reason for calling.
Depending on the reason the callback routine may perform necessary
actions to control the solution process.

The reason codes, which correspond to various point of the
branch-and-cut algorithm implemented in the MIP solver, are described
in Subsection ``Reasons for calling the callback routine'' below.

To ignore calls for reasons, which are not processed by the callback
routine, it should just return to the MIP solver doing nothing. For
example:

\begin{verbatim}
void foo_bar(glp_tree *tree, void *info)
{     . . .
      switch (glp_ios_reason(tree))
      {  case GLP_IBRANCH:
            . . .
            break;
         case GLP_ISELECT:
            . . .
            break;
         default:
            /* ignore call for other reasons */
            break;
      }
      return;
}
\end{verbatim}

To control the solution process as well as to obtain necessary
information the callback routine may use the branch-and-cut API
routines described in this chapter. Names of all these routines begin
with `\verb|glp_ios_|'.

\subsection{Branch-and-cut algorithm}

This section gives a schematic description of the branch-and-cut
algorithm as it is implemented in the GLPK MIP solver.

\medskip

{\it 1. Initialization}

Set $L:=\{P_0\}$, where $L$ is the {\it active list} (i.e. the list of
active subproblems), $P_0$ is the original MIP problem to be solved.

Set $z^{\it best}:=+\infty$ (in case of minimization) or
$z^{\it best}:=-\infty$ (in case of maximization), where $z^{\it best}$
is {\it incumbent value}, i.e. an upper (minimization) or lower
(maximization) global bound for $z^{\it opt}$, the optimal objective
value for $P^0$.

\medskip

{\it 2. Subproblem selection}

If $L=\varnothing$ then GO TO 9.

Select $P\in L$, i.e. make active subproblem $P$ current.

\medskip

{\it 3. Solving LP relaxation}

Solve $P^{\it LP}$, which is LP relaxation of $P$.

If $P^{\it LP}$ has no primal feasible solution then GO TO 8.

Let $z^{\it LP}$ be the optimal objective value for $P^{\it LP}$.

If $z^{\it LP}\geq z^{\it best}$ (in case of minimization) or
$z^{\it LP}\leq z^{\rm best}$ (in case of maximization) then GO TO 8.

\medskip

{\it 4. Adding ``lazy'' constraints}

Let $x^{\it LP}$ be the optimal solution to $P^{\it LP}$.

If there are ``lazy'' constraints (i.e. essential constraints not
included in the original MIP problem $P_0$), which are violated at the
optimal point $x^{\it LP}$, add them to $P$, and GO TO 3.

\medskip

{\it 5. Check for integrality}

Let $x_j$ be a variable, which is required to be integer, and let
$x^{\it LP}_j\in x^{\it LP}$ be its value in the optimal solution to
$P^{\it LP}$.

If $x^{\it LP}_j$ are integral for all integer variables, then a better
integer feasible solution is found. Store its components, set
$z^{\it best}:=z^{\it LP}$, and GO TO 8.

\medskip

{\it 6. Adding cutting planes}

If there are cutting planes (i.e. valid constraints for $P$),
which are violated at the optimal point $x^{\it LP}$, add them to $P$,
and GO TO 3.

\medskip

{\it 7. Branching}

Select {\it branching variable} $x_j$, i.e. a variable, which is
required to be integer, and whose value $x^{\it LP}_j\in x^{\it LP}$ is
fractional in the optimal solution to $P^{\it LP}$.

Create new subproblem $P^D$ (so called {\it down branch}), which is
identical to the current subproblem $P$ with exception that the upper
bound of $x_j$ is replaced by $\lfloor x^{\it LP}_j\rfloor$. (For
example, if $x^{\it LP}_j=3.14$, the new upper bound of $x_j$ in the
down branch will be $\lfloor 3.14\rfloor=3$.)

Create new subproblem $P^U$ (so called {\it up branch}), which is
identical to the current subproblem $P$ with exception that the lower
bound of $x_j$ is replaced by $\lceil x^{\it LP}_j\rceil$. (For example,
if $x^{\it LP}_j=3.14$, the new lower bound of $x_j$ in the up branch
will be $\lceil 3.14\rceil=4$.)

Set $L:=(L\backslash\{P\})\cup\{P^D,P^U\}$, i.e. remove the current
subproblem $P$ from the active list $L$ and add two new subproblems
$P^D$ and $P^U$ to it. Then GO TO 2.

\medskip

{\it 8. Pruning}

Remove from the active list $L$ all subproblems (including the current
one), whose local bound $\widetilde{z}$ is not better than the global
bound $z^{\it best}$, i.e. set $L:=L\backslash\{P\}$ for all $P$, where
$\widetilde{z}\geq z^{\it best}$ (in case of minimization) or
$\widetilde{z}\leq z^{\it best}$ (in case of maximization), and then
GO TO 2.

The local bound $\widetilde{z}$ 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. Note that
the local bound is not necessarily the optimal objective value to LP
relaxation $P^{\it LP}$.

\medskip

{\it 9. Termination}

If $z^{\it best}=+\infty$ (in case of minimization) or
$z^{\it best}=-\infty$ (in case of maximization), the original problem
$P_0$ has no integer feasible solution. Otherwise, the last integer
feasible solution stored on step 5 is the integer optimal solution to
the original problem $P_0$ with $z^{\it opt}=z^{\it best}$. STOP.

\subsection{The search tree}

On the branching step of the branch-and-cut algorithm the current
subproblem is divided into two\footnote{In more general cases the
current subproblem may be divided into more than two subproblems.
However, currently such feature is not used in GLPK.} new subproblems,
so the set of all subproblems can be represented in the form of a rooted
tree, which is called the {\it search} or {\it branch-and-bound} tree.
An example of the search tree is shown on Fig.~1. Each node of the
search tree corresponds to a subproblem, so the terms `node' and
`subproblem' may be used synonymously.

\newpage

\begin{figure}[t]
\noindent\hfil
\xymatrix @R=20pt @C=10pt
{&&&&&&*+<14pt>[o][F=]{A}\ar@{-}[dllll]\ar@{-}[dr]\ar@{-}[drrrr]&&&&\\
&&*+<14pt>[o][F=]{B}\ar@{-}[dl]\ar@{-}[dr]&&&&&*+<14pt>[o][F=]{C}
\ar@{-}[dll]\ar@{-}[dr]\ar@{-}[drrr]&&&*+<14pt>[o][F-]{\times}\\
&*+<14pt>[o][F-]{\times}\ar@{-}[dl]\ar@{-}[d]\ar@{-}[dr]&&
*+<14pt>[o][F-]{D}&&*+<14pt>[o][F=]{E}\ar@{-}[dl]\ar@{-}[dr]&&&
*+<14pt>[o][F=]{F}\ar@{-}[dl]\ar@{-}[dr]&&*+<14pt>[o][F-]{G}\\
*+<14pt>[o][F-]{\times}&*+<14pt>[o][F-]{\times}&*+<14pt>[o][F-]{\times}
&&*+<14pt>[][F-]{H}&&*+<14pt>[o][F-]{I}&*+<14pt>[o][F-]{\times}&&
*+<14pt>[o][F-]{J}&\\}

\bigskip

\noindent\hspace{.8in}
\xymatrix @R=11pt
{*+<20pt>[][F-]{}&*\txt{\makebox[1in][l]{Current}}&&
*+<20pt>[o][F-]{}&*\txt{\makebox[1in][l]{Active}}\\
*+<20pt>[o][F=]{}&*\txt{\makebox[1in][l]{Non-active}}&&
*+<14pt>[o][F-]{\times}&*\txt{\makebox[1in][l]{Fathomed}}\\
}

\begin{center}
Fig. 1. An example of the search tree.
\end{center}
\end{figure}

In GLPK each node may have one of the following four statuses:

$\bullet$ {\it current node} is the active node currently being
processed;

$\bullet$ {\it active node} is a leaf node, which still has to be
processed;

$\bullet$ {\it non-active node} is a node, which has been processed,
but not fathomed;

$\bullet$ {\it fathomed node} is a node, which has been processed and
fathomed.

In the data structure representing the search tree GLPK keeps only
current, active, and non-active nodes. Once a node has been fathomed,
it is removed from the tree data structure.

Being created each node of the search tree is assigned a distinct
positive integer called the {\it subproblem reference number}, which
may be used by the application program to specify a particular node of
the tree. The root node corresponding to the original problem to be
solved is always assigned the reference number 1.

\subsection{Current subproblem}

The current subproblem is a MIP problem corresponding to the current
node of the search tree. It is represented as the GLPK problem object
(\verb|glp_prob|) that allows the application program using API routines
to access its content in the standard way. If the MIP presolver is not
used, it is the original problem object passed to the routine
\verb|glp_intopt|; otherwise, it is an internal problem object built by
the MIP presolver.

Note that the problem object is used by the MIP solver itself during
the solution process for various purposes (to solve LP relaxations, to
perfom branching, etc.), and even if the MIP presolver is not used, the
current content of the problem object may differ from its original
content. For example, it may have additional rows, bounds of some rows
and columns may be changed, etc. In particular, LP segment of the
problem object corresponds to LP relaxation of the current subproblem.
However, on exit from the MIP solver the content of the problem object
is restored to its original state.

To obtain information from the problem object the application program
may use any API routines, which do not change the object. Using API
routines, which change the problem object, is restricted to stipulated
cases.

\subsection{The cut pool}

The {\it cut pool} is a set of cutting plane constraints maintained by
the MIP solver. It is used by the GLPK cut generation routines and may
be used by the application program in the same way, i.e. rather than
to add cutting plane constraints directly to the problem object the
application program may store them to the cut pool. In the latter case
the solver looks through the cut pool, selects efficient constraints,
and adds them to the problem object.

\subsection{Reasons for calling the callback routine}

The callback routine may be called by the MIP solver for the following
reasons.

\subsubsection*{Request for subproblem selection}

The callback routine is called with the reason code \verb|GLP_ISELECT|
if the current subproblem has been fathomed and therefore there is no
current subproblem.

In response the callback routine may select some subproblem from the
active list and pass its reference number to the solver using the
routine \verb|glp_ios_select_node|, in which case the solver continues
the search from the specified active subproblem. If no selection is made
by the callback routine, the solver uses a backtracking technique
specified by the control parameter \verb|bt_tech|.

To explore the active list (i.e. active nodes of the branch-and-bound
tree) the callback routine may use the routines \verb|glp_ios_next_node|
and \verb|glp_ios_prev_node|.

\subsubsection*{Request for preprocessing}

The callback routine is called with the reason code \verb|GLP_IPREPRO|
if the current subproblem has just been selected from the active list
and its LP relaxation is not solved yet.

In response the callback routine may perform some preprocessing of the
current subproblem like tightening bounds of some variables or removing
bounds of some redundant constraints.

\subsubsection*{Request for row generation}

The callback routine is called with the reason code \verb|GLP_IROWGEN|
if LP relaxation of the current subproblem has just been solved to
optimality and its objective value is better than the best known integer
feasible solution.

In response the callback routine may add one or more ``lazy''
constraints (rows), which are violated by the current optimal solution
of LP relaxation, using API routines \verb|glp_add_rows|,
\verb|glp_set_row_name|, \verb|glp_set_row_bnds|, and
\verb|glp_set_mat_row|, in which case the solver will perform
re-optimization of LP relaxation. If there are no violated constraints,
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
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 subprob-\\
lem}

\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 *%