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