1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/doc/glpk05.tex	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,1100 @@
     1.4 +%* glpk05.tex *%
     1.5 +
     1.6 +\chapter{Branch-and-Cut API Routines}
     1.7 +
     1.8 +\section{Introduction}
     1.9 +
    1.10 +\subsection{Using the callback routine}
    1.11 +
    1.12 +The GLPK MIP solver based on the branch-and-cut method allows the
    1.13 +application program to control the solution process. This is attained
    1.14 +by means of the user-defined callback routine, which is called by the
    1.15 +solver at various points of the branch-and-cut algorithm.
    1.16 +
    1.17 +The callback routine passed to the MIP solver should be written by the
    1.18 +user and has the following specification:\footnote{The name
    1.19 +{\tt foo\_bar} used here is a placeholder for the callback routine
    1.20 +name.}
    1.21 +
    1.22 +\begin{verbatim}
    1.23 +   void foo_bar(glp_tree *tree, void *info);
    1.24 +\end{verbatim}
    1.25 +
    1.26 +\noindent
    1.27 +where \verb|tree| is a pointer to the data structure \verb|glp_tree|,
    1.28 +which should be used on subsequent calls to branch-and-cut interface
    1.29 +routines, and \verb|info| is a transit pointer passed to the routine
    1.30 +\verb|glp_intopt|, which may be used by the application program to pass
    1.31 +some external data to the callback routine.
    1.32 +
    1.33 +The callback routine is passed to the MIP solver through the control
    1.34 +parameter structure \verb|glp_iocp| (see Chapter ``Basic API Routines'',
    1.35 +Section ``Mixed integer programming routines'', Subsection ``Solve MIP
    1.36 +problem with the branch-and-cut method'') as follows:
    1.37 +
    1.38 +\newpage
    1.39 +
    1.40 +\begin{verbatim}
    1.41 +   glp_prob *mip;
    1.42 +   glp_iocp parm;
    1.43 +   . . .
    1.44 +   glp_init_iocp(&parm);
    1.45 +   . . .
    1.46 +   parm.cb_func = foo_bar;
    1.47 +   parm.cb_info = ... ;
    1.48 +   ret = glp_intopt(mip, &parm);
    1.49 +   . . .
    1.50 +\end{verbatim}
    1.51 +
    1.52 +To determine why it is being called by the MIP solver the callback
    1.53 +routine should use the routine \verb|glp_ios_reason| (described in this
    1.54 +section below), which returns a code indicating the reason for calling.
    1.55 +Depending on the reason the callback routine may perform necessary
    1.56 +actions to control the solution process.
    1.57 +
    1.58 +The reason codes, which correspond to various point of the
    1.59 +branch-and-cut algorithm implemented in the MIP solver, are described
    1.60 +in Subsection ``Reasons for calling the callback routine'' below.
    1.61 +
    1.62 +To ignore calls for reasons, which are not processed by the callback
    1.63 +routine, it should just return to the MIP solver doing nothing. For
    1.64 +example:
    1.65 +
    1.66 +\begin{verbatim}
    1.67 +void foo_bar(glp_tree *tree, void *info)
    1.68 +{     . . .
    1.69 +      switch (glp_ios_reason(tree))
    1.70 +      {  case GLP_IBRANCH:
    1.71 +            . . .
    1.72 +            break;
    1.73 +         case GLP_ISELECT:
    1.74 +            . . .
    1.75 +            break;
    1.76 +         default:
    1.77 +            /* ignore call for other reasons */
    1.78 +            break;
    1.79 +      }
    1.80 +      return;
    1.81 +}
    1.82 +\end{verbatim}
    1.83 +
    1.84 +To control the solution process as well as to obtain necessary
    1.85 +information the callback routine may use the branch-and-cut API
    1.86 +routines described in this chapter. Names of all these routines begin
    1.87 +with `\verb|glp_ios_|'.
    1.88 +
    1.89 +\subsection{Branch-and-cut algorithm}
    1.90 +
    1.91 +This section gives a schematic description of the branch-and-cut
    1.92 +algorithm as it is implemented in the GLPK MIP solver.
    1.93 +
    1.94 +\medskip
    1.95 +
    1.96 +{\it 1. Initialization}
    1.97 +
    1.98 +Set $L:=\{P_0\}$, where $L$ is the {\it active list} (i.e. the list of
    1.99 +active subproblems), $P_0$ is the original MIP problem to be solved.
   1.100 +
   1.101 +Set $z^{\it best}:=+\infty$ (in case of minimization) or
   1.102 +$z^{\it best}:=-\infty$ (in case of maximization), where $z^{\it best}$
   1.103 +is {\it incumbent value}, i.e. an upper (minimization) or lower
   1.104 +(maximization) global bound for $z^{\it opt}$, the optimal objective
   1.105 +value for $P^0$.
   1.106 +
   1.107 +\medskip
   1.108 +
   1.109 +{\it 2. Subproblem selection}
   1.110 +
   1.111 +If $L=\varnothing$ then GO TO 9.
   1.112 +
   1.113 +Select $P\in L$, i.e. make active subproblem $P$ current.
   1.114 +
   1.115 +\medskip
   1.116 +
   1.117 +{\it 3. Solving LP relaxation}
   1.118 +
   1.119 +Solve $P^{\it LP}$, which is LP relaxation of $P$.
   1.120 +
   1.121 +If $P^{\it LP}$ has no primal feasible solution then GO TO 8.
   1.122 +
   1.123 +Let $z^{\it LP}$ be the optimal objective value for $P^{\it LP}$.
   1.124 +
   1.125 +If $z^{\it LP}\geq z^{\it best}$ (in case of minimization) or
   1.126 +$z^{\it LP}\leq z^{\rm best}$ (in case of maximization) then GO TO 8.
   1.127 +
   1.128 +\medskip
   1.129 +
   1.130 +{\it 4. Adding ``lazy'' constraints}
   1.131 +
   1.132 +Let $x^{\it LP}$ be the optimal solution to $P^{\it LP}$.
   1.133 +
   1.134 +If there are ``lazy'' constraints (i.e. essential constraints not
   1.135 +included in the original MIP problem $P_0$), which are violated at the
   1.136 +optimal point $x^{\it LP}$, add them to $P$, and GO TO 3.
   1.137 +
   1.138 +\medskip
   1.139 +
   1.140 +{\it 5. Check for integrality}
   1.141 +
   1.142 +Let $x_j$ be a variable, which is required to be integer, and let
   1.143 +$x^{\it LP}_j\in x^{\it LP}$ be its value in the optimal solution to
   1.144 +$P^{\it LP}$.
   1.145 +
   1.146 +If $x^{\it LP}_j$ are integral for all integer variables, then a better
   1.147 +integer feasible solution is found. Store its components, set
   1.148 +$z^{\it best}:=z^{\it LP}$, and GO TO 8.
   1.149 +
   1.150 +\medskip
   1.151 +
   1.152 +{\it 6. Adding cutting planes}
   1.153 +
   1.154 +If there are cutting planes (i.e. valid constraints for $P$),
   1.155 +which are violated at the optimal point $x^{\it LP}$, add them to $P$,
   1.156 +and GO TO 3.
   1.157 +
   1.158 +\medskip
   1.159 +
   1.160 +{\it 7. Branching}
   1.161 +
   1.162 +Select {\it branching variable} $x_j$, i.e. a variable, which is
   1.163 +required to be integer, and whose value $x^{\it LP}_j\in x^{\it LP}$ is
   1.164 +fractional in the optimal solution to $P^{\it LP}$.
   1.165 +
   1.166 +Create new subproblem $P^D$ (so called {\it down branch}), which is
   1.167 +identical to the current subproblem $P$ with exception that the upper
   1.168 +bound of $x_j$ is replaced by $\lfloor x^{\it LP}_j\rfloor$. (For
   1.169 +example, if $x^{\it LP}_j=3.14$, the new upper bound of $x_j$ in the
   1.170 +down branch will be $\lfloor 3.14\rfloor=3$.)
   1.171 +
   1.172 +Create new subproblem $P^U$ (so called {\it up branch}), which is
   1.173 +identical to the current subproblem $P$ with exception that the lower
   1.174 +bound of $x_j$ is replaced by $\lceil x^{\it LP}_j\rceil$. (For example,
   1.175 +if $x^{\it LP}_j=3.14$, the new lower bound of $x_j$ in the up branch
   1.176 +will be $\lceil 3.14\rceil=4$.)
   1.177 +
   1.178 +Set $L:=(L\backslash\{P\})\cup\{P^D,P^U\}$, i.e. remove the current
   1.179 +subproblem $P$ from the active list $L$ and add two new subproblems
   1.180 +$P^D$ and $P^U$ to it. Then GO TO 2.
   1.181 +
   1.182 +\medskip
   1.183 +
   1.184 +{\it 8. Pruning}
   1.185 +
   1.186 +Remove from the active list $L$ all subproblems (including the current
   1.187 +one), whose local bound $\widetilde{z}$ is not better than the global
   1.188 +bound $z^{\it best}$, i.e. set $L:=L\backslash\{P\}$ for all $P$, where
   1.189 +$\widetilde{z}\geq z^{\it best}$ (in case of minimization) or
   1.190 +$\widetilde{z}\leq z^{\it best}$ (in case of maximization), and then
   1.191 +GO TO 2.
   1.192 +
   1.193 +The local bound $\widetilde{z}$ for subproblem $P$ is an lower
   1.194 +(minimization) or upper (maximization) bound for integer optimal
   1.195 +solution to {\it this} subproblem (not to the original problem). This
   1.196 +bound is local in the sense that only subproblems in the subtree rooted
   1.197 +at node $P$ cannot have better integer feasible solutions. Note that
   1.198 +the local bound is not necessarily the optimal objective value to LP
   1.199 +relaxation $P^{\it LP}$.
   1.200 +
   1.201 +\medskip
   1.202 +
   1.203 +{\it 9. Termination}
   1.204 +
   1.205 +If $z^{\it best}=+\infty$ (in case of minimization) or
   1.206 +$z^{\it best}=-\infty$ (in case of maximization), the original problem
   1.207 +$P_0$ has no integer feasible solution. Otherwise, the last integer
   1.208 +feasible solution stored on step 5 is the integer optimal solution to
   1.209 +the original problem $P_0$ with $z^{\it opt}=z^{\it best}$. STOP.
   1.210 +
   1.211 +\subsection{The search tree}
   1.212 +
   1.213 +On the branching step of the branch-and-cut algorithm the current
   1.214 +subproblem is divided into two\footnote{In more general cases the
   1.215 +current subproblem may be divided into more than two subproblems.
   1.216 +However, currently such feature is not used in GLPK.} new subproblems,
   1.217 +so the set of all subproblems can be represented in the form of a rooted
   1.218 +tree, which is called the {\it search} or {\it branch-and-bound} tree.
   1.219 +An example of the search tree is shown on Fig.~1. Each node of the
   1.220 +search tree corresponds to a subproblem, so the terms `node' and
   1.221 +`subproblem' may be used synonymously.
   1.222 +
   1.223 +\newpage
   1.224 +
   1.225 +\begin{figure}[t]
   1.226 +\noindent\hfil
   1.227 +\xymatrix @R=20pt @C=10pt
   1.228 +{&&&&&&*+<14pt>[o][F=]{A}\ar@{-}[dllll]\ar@{-}[dr]\ar@{-}[drrrr]&&&&\\
   1.229 +&&*+<14pt>[o][F=]{B}\ar@{-}[dl]\ar@{-}[dr]&&&&&*+<14pt>[o][F=]{C}
   1.230 +\ar@{-}[dll]\ar@{-}[dr]\ar@{-}[drrr]&&&*+<14pt>[o][F-]{\times}\\
   1.231 +&*+<14pt>[o][F-]{\times}\ar@{-}[dl]\ar@{-}[d]\ar@{-}[dr]&&
   1.232 +*+<14pt>[o][F-]{D}&&*+<14pt>[o][F=]{E}\ar@{-}[dl]\ar@{-}[dr]&&&
   1.233 +*+<14pt>[o][F=]{F}\ar@{-}[dl]\ar@{-}[dr]&&*+<14pt>[o][F-]{G}\\
   1.234 +*+<14pt>[o][F-]{\times}&*+<14pt>[o][F-]{\times}&*+<14pt>[o][F-]{\times}
   1.235 +&&*+<14pt>[][F-]{H}&&*+<14pt>[o][F-]{I}&*+<14pt>[o][F-]{\times}&&
   1.236 +*+<14pt>[o][F-]{J}&\\}
   1.237 +
   1.238 +\bigskip
   1.239 +
   1.240 +\noindent\hspace{.8in}
   1.241 +\xymatrix @R=11pt
   1.242 +{*+<20pt>[][F-]{}&*\txt{\makebox[1in][l]{Current}}&&
   1.243 +*+<20pt>[o][F-]{}&*\txt{\makebox[1in][l]{Active}}\\
   1.244 +*+<20pt>[o][F=]{}&*\txt{\makebox[1in][l]{Non-active}}&&
   1.245 +*+<14pt>[o][F-]{\times}&*\txt{\makebox[1in][l]{Fathomed}}\\
   1.246 +}
   1.247 +
   1.248 +\begin{center}
   1.249 +Fig. 1. An example of the search tree.
   1.250 +\end{center}
   1.251 +\end{figure}
   1.252 +
   1.253 +In GLPK each node may have one of the following four statuses:
   1.254 +
   1.255 +$\bullet$ {\it current node} is the active node currently being
   1.256 +processed;
   1.257 +
   1.258 +$\bullet$ {\it active node} is a leaf node, which still has to be
   1.259 +processed;
   1.260 +
   1.261 +$\bullet$ {\it non-active node} is a node, which has been processed,
   1.262 +but not fathomed;
   1.263 +
   1.264 +$\bullet$ {\it fathomed node} is a node, which has been processed and
   1.265 +fathomed.
   1.266 +
   1.267 +In the data structure representing the search tree GLPK keeps only
   1.268 +current, active, and non-active nodes. Once a node has been fathomed,
   1.269 +it is removed from the tree data structure.
   1.270 +
   1.271 +Being created each node of the search tree is assigned a distinct
   1.272 +positive integer called the {\it subproblem reference number}, which
   1.273 +may be used by the application program to specify a particular node of
   1.274 +the tree. The root node corresponding to the original problem to be
   1.275 +solved is always assigned the reference number 1.
   1.276 +
   1.277 +\subsection{Current subproblem}
   1.278 +
   1.279 +The current subproblem is a MIP problem corresponding to the current
   1.280 +node of the search tree. It is represented as the GLPK problem object
   1.281 +(\verb|glp_prob|) that allows the application program using API routines
   1.282 +to access its content in the standard way. If the MIP presolver is not
   1.283 +used, it is the original problem object passed to the routine
   1.284 +\verb|glp_intopt|; otherwise, it is an internal problem object built by
   1.285 +the MIP presolver.
   1.286 +
   1.287 +Note that the problem object is used by the MIP solver itself during
   1.288 +the solution process for various purposes (to solve LP relaxations, to
   1.289 +perfom branching, etc.), and even if the MIP presolver is not used, the
   1.290 +current content of the problem object may differ from its original
   1.291 +content. For example, it may have additional rows, bounds of some rows
   1.292 +and columns may be changed, etc. In particular, LP segment of the
   1.293 +problem object corresponds to LP relaxation of the current subproblem.
   1.294 +However, on exit from the MIP solver the content of the problem object
   1.295 +is restored to its original state.
   1.296 +
   1.297 +To obtain information from the problem object the application program
   1.298 +may use any API routines, which do not change the object. Using API
   1.299 +routines, which change the problem object, is restricted to stipulated
   1.300 +cases.
   1.301 +
   1.302 +\subsection{The cut pool}
   1.303 +
   1.304 +The {\it cut pool} is a set of cutting plane constraints maintained by
   1.305 +the MIP solver. It is used by the GLPK cut generation routines and may
   1.306 +be used by the application program in the same way, i.e. rather than
   1.307 +to add cutting plane constraints directly to the problem object the
   1.308 +application program may store them to the cut pool. In the latter case
   1.309 +the solver looks through the cut pool, selects efficient constraints,
   1.310 +and adds them to the problem object.
   1.311 +
   1.312 +\subsection{Reasons for calling the callback routine}
   1.313 +
   1.314 +The callback routine may be called by the MIP solver for the following
   1.315 +reasons.
   1.316 +
   1.317 +\subsubsection*{Request for subproblem selection}
   1.318 +
   1.319 +The callback routine is called with the reason code \verb|GLP_ISELECT|
   1.320 +if the current subproblem has been fathomed and therefore there is no
   1.321 +current subproblem.
   1.322 +
   1.323 +In response the callback routine may select some subproblem from the
   1.324 +active list and pass its reference number to the solver using the
   1.325 +routine \verb|glp_ios_select_node|, in which case the solver continues
   1.326 +the search from the specified active subproblem. If no selection is made
   1.327 +by the callback routine, the solver uses a backtracking technique
   1.328 +specified by the control parameter \verb|bt_tech|.
   1.329 +
   1.330 +To explore the active list (i.e. active nodes of the branch-and-bound
   1.331 +tree) the callback routine may use the routines \verb|glp_ios_next_node|
   1.332 +and \verb|glp_ios_prev_node|.
   1.333 +
   1.334 +\subsubsection*{Request for preprocessing}
   1.335 +
   1.336 +The callback routine is called with the reason code \verb|GLP_IPREPRO|
   1.337 +if the current subproblem has just been selected from the active list
   1.338 +and its LP relaxation is not solved yet.
   1.339 +
   1.340 +In response the callback routine may perform some preprocessing of the
   1.341 +current subproblem like tightening bounds of some variables or removing
   1.342 +bounds of some redundant constraints.
   1.343 +
   1.344 +\subsubsection*{Request for row generation}
   1.345 +
   1.346 +The callback routine is called with the reason code \verb|GLP_IROWGEN|
   1.347 +if LP relaxation of the current subproblem has just been solved to
   1.348 +optimality and its objective value is better than the best known integer
   1.349 +feasible solution.
   1.350 +
   1.351 +In response the callback routine may add one or more ``lazy''
   1.352 +constraints (rows), which are violated by the current optimal solution
   1.353 +of LP relaxation, using API routines \verb|glp_add_rows|,
   1.354 +\verb|glp_set_row_name|, \verb|glp_set_row_bnds|, and
   1.355 +\verb|glp_set_mat_row|, in which case the solver will perform
   1.356 +re-optimization of LP relaxation. If there are no violated constraints,
   1.357 +the callback routine should just return.
   1.358 +
   1.359 +Optimal solution components for LP relaxation can be obtained with API
   1.360 +routines \verb|glp_get_obj_val|, \verb|glp_get_row_prim|,
   1.361 +\verb|glp_get_row_dual|, \verb|glp_get_col_prim|, and
   1.362 +\verb|glp_get_col_dual|.
   1.363 +
   1.364 +\subsubsection*{Request for heuristic solution}
   1.365 +
   1.366 +The callback routine is called with the reason code \verb|GLP_IHEUR|
   1.367 +if LP relaxation of the current subproblem being solved to optimality
   1.368 +is integer infeasible (i.e. values of some structural variables of
   1.369 +integer kind are fractional), though its objective value is better than
   1.370 +the best known integer feasible solution.
   1.371 +
   1.372 +In response the callback routine may try applying a primal heuristic
   1.373 +to find an integer feasible solution,\footnote{Integer feasible to the
   1.374 +original MIP problem, not to the current subproblem.} which is better
   1.375 +than the best known one. In case of success the callback routine may
   1.376 +store such better solution in the problem object using the routine
   1.377 +\verb|glp_ios_heur_sol|.
   1.378 +
   1.379 +\subsubsection*{Request for cut generation}
   1.380 +
   1.381 +The callback routine is called with the reason code \verb|GLP_ICUTGEN|
   1.382 +if LP relaxation of the current subproblem being solved to optimality
   1.383 +is integer infeasible (i.e. values of some structural variables of
   1.384 +integer kind are fractional), though its objective value is better than
   1.385 +the best known integer feasible solution.
   1.386 +
   1.387 +In response the callback routine may reformulate the {\it current}
   1.388 +subproblem (before it will be splitted up due to branching) by adding to
   1.389 +the problem object one or more {\it cutting plane constraints}, which
   1.390 +cut off the fractional optimal point from the MIP
   1.391 +polytope.\footnote{Since these constraints are added to the current
   1.392 +subproblem, they may be globally as well as locally valid.}
   1.393 +
   1.394 +Adding cutting plane constraints may be performed in two ways.
   1.395 +One way is the same as for the reason code \verb|GLP_IROWGEN| (see
   1.396 +above), in which case the callback routine adds new rows corresponding
   1.397 +to cutting plane constraints directly to the current subproblem.
   1.398 +
   1.399 +The other way is to add cutting plane constraints to the {\it cut pool},
   1.400 +a set of cutting plane constraints maintained by the solver, rather than
   1.401 +directly to the current subproblem. In this case after return from the
   1.402 +callback routine the solver looks through the cut pool, selects
   1.403 +efficient cutting plane constraints, adds them to the current
   1.404 +subproblem, drops other constraints, and then performs re-optimization.
   1.405 +
   1.406 +\subsubsection*{Request for branching}
   1.407 +
   1.408 +The callback routine is called with the reason code \verb|GLP_IBRANCH|
   1.409 +if LP relaxation of the current subproblem being solved to optimality
   1.410 +is integer infeasible (i.e. values of some structural variables of
   1.411 +integer kind are fractional), though its objective value is better than
   1.412 +the best known integer feasible solution.
   1.413 +
   1.414 +In response the callback routine may choose some variable suitable for
   1.415 +branching (i.e. integer variable, whose value in optimal solution to
   1.416 +LP relaxation of the current subproblem is fractional) and pass its
   1.417 +ordinal number to the solver using the routine
   1.418 +\verb|glp_ios_branch_upon|, in which case the solver splits the current
   1.419 +subproblem in two new subproblems and continues the search. If no choice
   1.420 +is made by the callback routine, the solver uses a branching technique
   1.421 +specified by the control parameter \verb|br_tech|.
   1.422 +
   1.423 +\subsubsection*{Better integer solution found}
   1.424 +
   1.425 +The callback routine is called with the reason code \verb|GLP_IBINGO|
   1.426 +if LP relaxation of the current subproblem being solved to optimality
   1.427 +is integer feasible (i.e. values of all structural variables of integer
   1.428 +kind are integral within the working precision) and its objective value
   1.429 +is better than the best known integer feasible solution.
   1.430 +
   1.431 +Optimal solution components for LP relaxation can be obtained in the
   1.432 +same way as for the reason code \verb|GLP_IROWGEN| (see above).
   1.433 +
   1.434 +Components of the new MIP solution can be obtained with API routines
   1.435 +\verb|glp_mip_obj_val|, \verb|glp_mip_row_val|, and
   1.436 +\verb|glp_mip_col_val|. Note, however, that due to row/cut generation
   1.437 +there may be additional rows in the problem object.
   1.438 +
   1.439 +The difference between optimal solution to LP relaxation and
   1.440 +corresponding MIP solution is that in the former case some structural
   1.441 +variables of integer kind (namely, basic variables) may have values,
   1.442 +which are close to nearest integers within the working precision, while
   1.443 +in the latter case all such variables have exact integral values.
   1.444 +
   1.445 +The reason \verb|GLP_IBINGO| is intended only for informational
   1.446 +purposes, so the callback routine should not modify the problem object
   1.447 +in this case.
   1.448 +
   1.449 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   1.450 +
   1.451 +\newpage
   1.452 +
   1.453 +\section{Basic routines}
   1.454 +
   1.455 +\subsection{glp\_ios\_reason---determine reason for calling the
   1.456 +callback routine}
   1.457 +
   1.458 +\subsubsection*{Synopsis}
   1.459 +
   1.460 +\begin{verbatim}
   1.461 +int glp_ios_reason(glp_tree *tree);
   1.462 +\end{verbatim}
   1.463 +
   1.464 +\subsubsection*{Returns}
   1.465 +
   1.466 +The routine \verb|glp_ios_reason| returns a code, which indicates why
   1.467 +the user-defined callback routine is being called:
   1.468 +
   1.469 +\verb|GLP_ISELECT|---request for subproblem selection;
   1.470 +
   1.471 +\verb|GLP_IPREPRO|---request for preprocessing;
   1.472 +
   1.473 +\verb|GLP_IROWGEN|---request for row generation;
   1.474 +
   1.475 +\verb|GLP_IHEUR  |---request for heuristic solution;
   1.476 +
   1.477 +\verb|GLP_ICUTGEN|---request for cut generation;
   1.478 +
   1.479 +\verb|GLP_IBRANCH|---request for branching;
   1.480 +
   1.481 +\verb|GLP_IBINGO |---better integer solution found.
   1.482 +
   1.483 +\subsection{glp\_ios\_get\_prob---access the problem object}
   1.484 +
   1.485 +\subsubsection*{Synopsis}
   1.486 +
   1.487 +\begin{verbatim}
   1.488 +glp_prob *glp_ios_get_prob(glp_tree *tree);
   1.489 +\end{verbatim}
   1.490 +
   1.491 +\subsubsection*{Description}
   1.492 +
   1.493 +The routine \verb|glp_ios_get_prob| can be called from the user-defined
   1.494 +callback routine to access the problem object, which is used by the MIP
   1.495 +solver. It is the original problem object passed to the routine
   1.496 +\verb|glp_intopt| if the MIP presolver is not used; otherwise it is an
   1.497 +internal problem object built by the presolver.
   1.498 +
   1.499 +\subsubsection*{Returns}
   1.500 +
   1.501 +The routine \verb|glp_ios_get_prob| returns a pointer to the problem
   1.502 +object used by the MIP solver.
   1.503 +
   1.504 +\subsubsection*{Comments}
   1.505 +
   1.506 +To obtain various information about the problem instance the callback
   1.507 +routine can access the problem object (i.e. the object of type
   1.508 +\verb|glp_prob|) using the routine \verb|glp_ios_get_prob|. It is the
   1.509 +original problem object passed to the routine \verb|glp_intopt| if the
   1.510 +MIP presolver is not used; otherwise it is an internal problem object
   1.511 +built by the presolver.
   1.512 +
   1.513 +\subsection{glp\_ios\_row\_attr---determine additional row attributes}
   1.514 +
   1.515 +\subsubsection*{Synopsis}
   1.516 +
   1.517 +\begin{verbatim}
   1.518 +void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr);
   1.519 +\end{verbatim}
   1.520 +
   1.521 +\subsubsection*{Description}
   1.522 +
   1.523 +The routine \verb|glp_ios_row_attr| retrieves additional attributes of
   1.524 +$i$-th row of the current subproblem and stores them in the structure
   1.525 +\verb|glp_attr|, which the parameter \verb|attr| points to.
   1.526 +
   1.527 +The structure \verb|glp_attr| has the following fields:
   1.528 +
   1.529 +\medskip
   1.530 +
   1.531 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
   1.532 +\multicolumn{2}{@{}l}{{\tt int level}}\\
   1.533 +&Subproblem level at which the row was created. (If \verb|level| = 0,
   1.534 +the row was added either to the original problem object passed to the
   1.535 +routine \verb|glp_intopt| or to the root subproblem on generating
   1.536 +``lazy'' or/and cutting plane constraints.)\\
   1.537 +\end{tabular}
   1.538 +
   1.539 +\medskip
   1.540 +
   1.541 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
   1.542 +\multicolumn{2}{@{}l}{{\tt int origin}}\\
   1.543 +&The row origin flag:\\
   1.544 +&\verb|GLP_RF_REG |---regular constraint;\\
   1.545 +&\verb|GLP_RF_LAZY|---``lazy'' constraint;\\
   1.546 +&\verb|GLP_RF_CUT |---cutting plane constraint.\\
   1.547 +\end{tabular}
   1.548 +
   1.549 +\medskip
   1.550 +
   1.551 +\noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
   1.552 +\multicolumn{2}{@{}l}{{\tt int klass}}\\
   1.553 +&The row class descriptor, which is a number passed to the routine
   1.554 +\verb|glp_ios_add_row| as its third parameter. If the row is a cutting
   1.555 +plane constraint generated by the solver, its class may be the
   1.556 +following:\\
   1.557 +&\verb|GLP_RF_GMI |---Gomory's mixed integer cut;\\
   1.558 +&\verb|GLP_RF_MIR |---mixed integer rounding cut;\\
   1.559 +&\verb|GLP_RF_COV |---mixed cover cut;\\
   1.560 +&\verb|GLP_RF_CLQ |---clique cut.\\
   1.561 +\end{tabular}
   1.562 +
   1.563 +\newpage
   1.564 +
   1.565 +\subsection{glp\_ios\_mip\_gap---compute relative MIP gap}
   1.566 +
   1.567 +\subsubsection*{Synopsis}
   1.568 +
   1.569 +\begin{verbatim}
   1.570 +double glp_ios_mip_gap(glp_tree *tree);
   1.571 +\end{verbatim}
   1.572 +
   1.573 +\subsubsection*{Description}
   1.574 +
   1.575 +The routine \verb|glp_ios_mip_gap| computes the relative MIP gap (also
   1.576 +called {\it duality gap}) with the following formula:
   1.577 +$${\tt gap} = \frac{|{\tt best\_mip} - {\tt best\_bnd}|}
   1.578 +{|{\tt best\_mip}| + {\tt DBL\_EPSILON}}$$
   1.579 +where \verb|best_mip| is the best integer feasible solution found so
   1.580 +far, \verb|best_bnd| is the best (global) bound. If no integer feasible
   1.581 +solution has been found yet, \verb|gap| is set to \verb|DBL_MAX|.
   1.582 +
   1.583 +\subsubsection*{Returns}
   1.584 +
   1.585 +The routine \verb|glp_ios_mip_gap| returns the relative MIP gap.
   1.586 +
   1.587 +\subsubsection*{Comments}
   1.588 +
   1.589 +The relative MIP gap is used to measure the quality of the best integer
   1.590 +feasible solution found so far, because the optimal solution value
   1.591 +$z^*$ for the original MIP problem always lies in the range
   1.592 +$${\tt best\_bnd}\leq z^*\leq{\tt best\_mip}$$
   1.593 +in case of minimization, or in the range
   1.594 +$${\tt best\_mip}\leq z^*\leq{\tt best\_bnd}$$
   1.595 +in case of maximization.
   1.596 +
   1.597 +To express the relative MIP gap in percents the value returned by the
   1.598 +routine \verb|glp_ios_mip_gap| should be multiplied by 100\%.
   1.599 +
   1.600 +\newpage
   1.601 +
   1.602 +\subsection{glp\_ios\_node\_data---access application-specific data}
   1.603 +
   1.604 +\subsubsection*{Synopsis}
   1.605 +
   1.606 +\begin{verbatim}
   1.607 +void *glp_ios_node_data(glp_tree *tree, int p);
   1.608 +\end{verbatim}
   1.609 +
   1.610 +\subsubsection*{Description}
   1.611 +
   1.612 +The routine \verb|glp_ios_node_data| allows the application accessing a
   1.613 +memory block allocated for the subproblem (which may be active or
   1.614 +inactive), whose reference number is $p$.
   1.615 +
   1.616 +The size of the block is defined by the control parameter \verb|cb_size|
   1.617 +passed to the routine \verb|glp_intopt|. The block is initialized by
   1.618 +binary zeros on creating corresponding subproblem, and its contents is
   1.619 +kept until the subproblem will be removed from the tree.
   1.620 +
   1.621 +The application may use these memory blocks to store specific data for
   1.622 +each subproblem.
   1.623 +
   1.624 +\subsubsection*{Returns}
   1.625 +
   1.626 +The routine \verb|glp_ios_node_data| returns a pointer to the memory
   1.627 +block for the specified subproblem. Note that if \verb|cb_size| = 0, the
   1.628 +routine returns a null pointer.
   1.629 +
   1.630 +\subsection{glp\_ios\_select\_node---select subproblem to continue the
   1.631 +search}
   1.632 +
   1.633 +\subsubsection*{Synopsis}
   1.634 +
   1.635 +\begin{verbatim}
   1.636 +void glp_ios_select_node(glp_tree *tree, int p);
   1.637 +\end{verbatim}
   1.638 +
   1.639 +\subsubsection*{Description}
   1.640 +
   1.641 +The routine \verb|glp_ios_select_node| can be called from the
   1.642 +user-defined callback routine in response to the reason
   1.643 +\verb|GLP_ISELECT| to select an active subproblem, whose reference
   1.644 +number is $p$. The search will be continued from the subproblem
   1.645 +selected.
   1.646 +
   1.647 +\newpage
   1.648 +
   1.649 +\subsection{glp\_ios\_heur\_sol---provide solution found by heuristic}
   1.650 +
   1.651 +\subsubsection*{Synopsis}
   1.652 +
   1.653 +\begin{verbatim}
   1.654 +int glp_ios_heur_sol(glp_tree *tree, const double x[]);
   1.655 +\end{verbatim}
   1.656 +
   1.657 +\subsubsection*{Description}
   1.658 +
   1.659 +The routine \verb|glp_ios_heur_sol| can be called from the user-defined
   1.660 +callback routine in response to the reason \verb|GLP_IHEUR| to provide
   1.661 +an integer feasible solution found by a primal heuristic.
   1.662 +
   1.663 +Primal values of {\it all} variables (columns) found by the heuristic
   1.664 +should be placed in locations $x[1]$, \dots, $x[n]$, where $n$ is the
   1.665 +number of columns in the original problem object. Note that the routine
   1.666 +\verb|glp_ios_heur_sol| does {\it not} check primal feasibility of the
   1.667 +solution provided.
   1.668 +
   1.669 +Using the solution passed in the array $x$ the routine computes value
   1.670 +of the objective function. If the objective value is better than the
   1.671 +best known integer feasible solution, the routine computes values of
   1.672 +auxiliary variables (rows) and stores all solution components in the
   1.673 +problem object.
   1.674 +
   1.675 +\subsubsection*{Returns}
   1.676 +
   1.677 +If the provided solution is accepted, the routine
   1.678 +\verb|glp_ios_heur_sol| returns zero. Otherwise, if the provided
   1.679 +solution is rejected, the routine returns non-zero.
   1.680 +
   1.681 +\subsection{glp\_ios\_can\_branch---check if can branch upon specified
   1.682 +variable}
   1.683 +
   1.684 +\subsubsection*{Synopsis}
   1.685 +
   1.686 +\begin{verbatim}
   1.687 +int glp_ios_can_branch(glp_tree *tree, int j);
   1.688 +\end{verbatim}
   1.689 +
   1.690 +\subsubsection*{Returns}
   1.691 +
   1.692 +If $j$-th variable (column) can be used to branch upon, the routine
   1.693 +returns non-zero, otherwise zero.
   1.694 +
   1.695 +\newpage
   1.696 +
   1.697 +\subsection{glp\_ios\_branch\_upon---choose variable to branch upon}
   1.698 +
   1.699 +\subsubsection*{Synopsis}
   1.700 +
   1.701 +\begin{verbatim}
   1.702 +void glp_ios_branch_upon(glp_tree *tree, int j, int sel);
   1.703 +\end{verbatim}
   1.704 +
   1.705 +\subsubsection*{Description}
   1.706 +
   1.707 +The routine \verb|glp_ios_branch_upon| can be called from the
   1.708 +user-defined callback routine in response to the reason
   1.709 +\verb|GLP_IBRANCH| to choose a branching variable, whose ordinal number
   1.710 +is $j$. Should note that only variables, for which the routine
   1.711 +\verb|glp_ios_can_branch| returns non-zero, can be used to branch upon.
   1.712 +
   1.713 +The parameter \verb|sel| is a flag that indicates which branch
   1.714 +(subproblem) should be selected next to continue the search:
   1.715 +
   1.716 +\verb|GLP_DN_BRNCH|---select down-branch;
   1.717 +
   1.718 +\verb|GLP_UP_BRNCH|---select up-branch;
   1.719 +
   1.720 +\verb|GLP_NO_BRNCH|---use general selection technique.
   1.721 +
   1.722 +\subsubsection*{Comments}
   1.723 +
   1.724 +On branching the solver removes the current active subproblem from the
   1.725 +active list and creates two new subproblems ({\it down-} and {\it
   1.726 +up-branches}), which are added to the end of the active list. Note that
   1.727 +the down-branch is created before the up-branch, so the last active
   1.728 +subproblem will be the up-branch.
   1.729 +
   1.730 +The down- and up-branches are identical to the current subproblem with
   1.731 +exception that in the down-branch the upper bound of $x_j$, the variable
   1.732 +chosen to branch upon, is replaced by $\lfloor x_j^*\rfloor$, while in
   1.733 +the up-branch the lower bound of $x_j$ is replaced by
   1.734 +$\lceil x_j^*\rceil$, where $x_j^*$ is the value of $x_j$ in optimal
   1.735 +solution to LP relaxation of the current subproblem. For example, if
   1.736 +$x_j^*=3.14$, the new upper bound of $x_j$ in the down-branch is
   1.737 +$\lfloor 3.14\rfloor=3$, and the new lower bound in the up-branch is
   1.738 +$\lceil 3.14\rceil=4$.)
   1.739 +
   1.740 +Additionally the callback routine may select either down- or up-branch,
   1.741 +from which the solver will continue the search. If none of the branches
   1.742 +is selected, a general selection technique will be used.
   1.743 +
   1.744 +\newpage
   1.745 +
   1.746 +\subsection{glp\_ios\_terminate---terminate the solution process}
   1.747 +
   1.748 +\subsubsection*{Synopsis}
   1.749 +
   1.750 +\begin{verbatim}
   1.751 +void glp_ios_terminate(glp_tree *tree);
   1.752 +\end{verbatim}
   1.753 +
   1.754 +\subsubsection*{Description}
   1.755 +
   1.756 +The routine \verb|glp_ios_terminate| sets a flag indicating that the
   1.757 +MIP solver should prematurely terminate the search.
   1.758 +
   1.759 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   1.760 +
   1.761 +\newpage
   1.762 +
   1.763 +\section{The search tree exploring routines}
   1.764 +
   1.765 +\subsection{glp\_ios\_tree\_size---determine size of the search tree}
   1.766 +
   1.767 +\subsubsection*{Synopsis}
   1.768 +
   1.769 +\begin{verbatim}
   1.770 +void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,
   1.771 +      int *t_cnt);
   1.772 +\end{verbatim}
   1.773 +
   1.774 +\subsubsection*{Description}
   1.775 +
   1.776 +The routine \verb|glp_ios_tree_size| stores the following three counts
   1.777 +which characterize the current size of the search tree:
   1.778 +
   1.779 +\verb|a_cnt| is the current number of active nodes, i.e. the current
   1.780 +size of the active list;
   1.781 +
   1.782 +\verb|n_cnt| is the current number of all (active and inactive) nodes;
   1.783 +
   1.784 +\verb|t_cnt| is the total number of nodes including those which have
   1.785 +been already removed from the tree. This count is increased whenever
   1.786 +a new node appears in the tree and never decreased.
   1.787 +
   1.788 +If some of the parameters \verb|a_cnt|, \verb|n_cnt|, \verb|t_cnt| is
   1.789 +a null pointer, the corresponding count is not stored.
   1.790 +
   1.791 +\subsection{glp\_ios\_curr\_node---determine current active subprob-\\
   1.792 +lem}
   1.793 +
   1.794 +\subsubsection*{Synopsis}
   1.795 +
   1.796 +\begin{verbatim}
   1.797 +int glp_ios_curr_node(glp_tree *tree);
   1.798 +\end{verbatim}
   1.799 +
   1.800 +\subsubsection*{Returns}
   1.801 +
   1.802 +The routine \verb|glp_ios_curr_node| returns the reference number of the
   1.803 +current active subproblem. However, if the current subproblem does not
   1.804 +exist, the routine returns zero.
   1.805 +
   1.806 +\newpage
   1.807 +
   1.808 +\subsection{glp\_ios\_next\_node---determine next active subproblem}
   1.809 +
   1.810 +\subsubsection*{Synopsis}
   1.811 +
   1.812 +\begin{verbatim}
   1.813 +int glp_ios_next_node(glp_tree *tree, int p);
   1.814 +\end{verbatim}
   1.815 +
   1.816 +\subsubsection*{Returns}
   1.817 +
   1.818 +If the parameter $p$ is zero, the routine \verb|glp_ios_next_node|
   1.819 +returns the reference number of the first active subproblem. However,
   1.820 +if the tree is empty, zero is returned.
   1.821 +
   1.822 +If the parameter $p$ is not zero, it must specify the reference number
   1.823 +of some active subproblem, in which case the routine returns the
   1.824 +reference number of the next active subproblem. However, if there is
   1.825 +no next active subproblem in the list, zero is returned.
   1.826 +
   1.827 +All subproblems in the active list are ordered chronologically, i.e.
   1.828 +subproblem $A$ precedes subproblem $B$ if $A$ was created before $B$.
   1.829 +
   1.830 +\subsection{glp\_ios\_prev\_node---determine previous active subproblem}
   1.831 +
   1.832 +\subsubsection*{Synopsis}
   1.833 +
   1.834 +\begin{verbatim}
   1.835 +int glp_ios_prev_node(glp_tree *tree, int p);
   1.836 +\end{verbatim}
   1.837 +
   1.838 +\subsubsection*{Returns}
   1.839 +
   1.840 +If the parameter $p$ is zero, the routine \verb|glp_ios_prev_node|
   1.841 +returns the reference number of the last active subproblem. However, if
   1.842 +the tree is empty, zero is returned.
   1.843 +
   1.844 +If the parameter $p$ is not zero, it must specify the reference number
   1.845 +of some active subproblem, in which case the routine returns the
   1.846 +reference number of the previous active subproblem. However, if there
   1.847 +is no previous active subproblem in the list, zero is returned.
   1.848 +
   1.849 +All subproblems in the active list are ordered chronologically, i.e.
   1.850 +subproblem $A$ precedes subproblem $B$ if $A$ was created before $B$.
   1.851 +
   1.852 +\newpage
   1.853 +
   1.854 +\subsection{glp\_ios\_up\_node---determine parent subproblem}
   1.855 +
   1.856 +\subsubsection*{Synopsis}
   1.857 +
   1.858 +\begin{verbatim}
   1.859 +int glp_ios_up_node(glp_tree *tree, int p);
   1.860 +\end{verbatim}
   1.861 +
   1.862 +\subsubsection*{Returns}
   1.863 +
   1.864 +The parameter $p$ must specify the reference number of some (active or
   1.865 +inactive) subproblem, in which case the routine \verb|iet_get_up_node|
   1.866 +returns the reference number of its parent subproblem. However, if the
   1.867 +specified subproblem is the root of the tree and, therefore, has
   1.868 +no parent, the routine returns zero.
   1.869 +
   1.870 +\subsection{glp\_ios\_node\_level---determine subproblem level}
   1.871 +
   1.872 +\subsubsection*{Synopsis}
   1.873 +
   1.874 +\begin{verbatim}
   1.875 +int glp_ios_node_level(glp_tree *tree, int p);
   1.876 +\end{verbatim}
   1.877 +
   1.878 +\subsubsection*{Returns}
   1.879 +
   1.880 +The routine \verb|glp_ios_node_level| returns the level of the
   1.881 +subproblem,\linebreak whose reference number is $p$, in the
   1.882 +branch-and-bound tree. (The root subproblem has level 0, and the level
   1.883 +of any other subproblem is the level of its parent plus one.)
   1.884 +
   1.885 +\subsection{glp\_ios\_node\_bound---determine subproblem local\\bound}
   1.886 +
   1.887 +\subsubsection*{Synopsis}
   1.888 +
   1.889 +\begin{verbatim}
   1.890 +double glp_ios_node_bound(glp_tree *tree, int p);
   1.891 +\end{verbatim}
   1.892 +
   1.893 +\subsubsection*{Returns}
   1.894 +
   1.895 +The routine \verb|glp_ios_node_bound| returns the local bound for
   1.896 +(active or inactive) subproblem, whose reference number is $p$.
   1.897 +
   1.898 +\subsubsection*{Comments}
   1.899 +
   1.900 +The local bound for subproblem $p$ is an lower (minimization) or upper
   1.901 +(maximization) bound for integer optimal solution to {\it this}
   1.902 +subproblem (not to the original problem). This bound is local in the
   1.903 +sense that only subproblems in the subtree rooted at node $p$ cannot
   1.904 +have better integer feasible solutions.
   1.905 +
   1.906 +On creating a subproblem (due to the branching step) its local bound is
   1.907 +inherited from its parent and then may get only stronger (never weaker).
   1.908 +For the root subproblem its local bound is initially set to
   1.909 +\verb|-DBL_MAX| (minimization) or \verb|+DBL_MAX| (maximization) and
   1.910 +then improved as the root LP relaxation has been solved.
   1.911 +
   1.912 +Note that the local bound is not necessarily the optimal objective value
   1.913 +to corresponding LP relaxation.
   1.914 +
   1.915 +\subsection{glp\_ios\_best\_node---find active subproblem with best
   1.916 +local bound}
   1.917 +
   1.918 +\subsubsection*{Synopsis}
   1.919 +
   1.920 +\begin{verbatim}
   1.921 +int glp_ios_best_node(glp_tree *tree);
   1.922 +\end{verbatim}
   1.923 +
   1.924 +\subsubsection*{Returns}
   1.925 +
   1.926 +The routine \verb|glp_ios_best_node| returns the reference number of
   1.927 +the active subproblem, whose local bound is best (i.e. smallest in case
   1.928 +of minimization or largest in case of maximization). However, if the
   1.929 +tree is empty, the routine returns zero.
   1.930 +
   1.931 +\subsubsection*{Comments}
   1.932 +
   1.933 +The best local bound is an lower (minimization) or upper (maximization)
   1.934 +bound for integer optimal solution to the original MIP problem.
   1.935 +
   1.936 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   1.937 +
   1.938 +\newpage
   1.939 +
   1.940 +\section{The cut pool routines}
   1.941 +
   1.942 +\subsection{glp\_ios\_pool\_size---determine current size of the cut\\
   1.943 +pool}
   1.944 +
   1.945 +\subsubsection*{Synopsis}
   1.946 +
   1.947 +\begin{verbatim}
   1.948 +int glp_ios_pool_size(glp_tree *tree);
   1.949 +\end{verbatim}
   1.950 +
   1.951 +\subsubsection*{Returns}
   1.952 +
   1.953 +The routine \verb|glp_ios_pool_size| returns the current size of the
   1.954 +cut pool, that is, the number of cutting plane constraints currently
   1.955 +added to it.
   1.956 +
   1.957 +\subsection{glp\_ios\_add\_row---add constraint to the cut pool}
   1.958 +
   1.959 +\subsubsection*{Synopsis}
   1.960 +
   1.961 +\begin{verbatim}
   1.962 +int glp_ios_add_row(glp_tree *tree, const char *name,
   1.963 +      int klass, int flags, int len, const int ind[],
   1.964 +      const double val[], int type, double rhs);
   1.965 +\end{verbatim}
   1.966 +
   1.967 +\subsubsection*{Description}
   1.968 +
   1.969 +The routine \verb|glp_ios_add_row| adds specified row (cutting plane
   1.970 +constraint) to the cut pool.
   1.971 +
   1.972 +The cutting plane constraint should have the following format:
   1.973 +$$\sum_{j\in J}a_jx_j\left\{\begin{array}{@{}c@{}}\geq\\\leq\\
   1.974 +\end{array}\right\}b,$$
   1.975 +where $J$ is a set of indices (ordinal numbers) of structural variables,
   1.976 +$a_j$ are constraint coefficients, $x_j$ are structural variables, $b$
   1.977 +is the right-hand side.
   1.978 +
   1.979 +The parameter \verb|name| specifies a symbolic name assigned to the
   1.980 +constraint (1 up to 255 characters). If it is \verb|NULL| or an empty
   1.981 +string, no name is assigned.
   1.982 +
   1.983 +The parameter \verb|klass| specifies the constraint class, which must
   1.984 +be either zero or a number in the range from 101 to 200. The application
   1.985 +may use this attribute to distinguish between cutting plane constraints
   1.986 +of different classes.\footnote{Constraint classes numbered from 1 to 100
   1.987 +are reserved for GLPK cutting plane generators.}
   1.988 +
   1.989 +The parameter \verb|flags| currently is not used and must be zero.
   1.990 +
   1.991 +Ordinal numbers of structural variables (i.e. column indices) $j\in J$
   1.992 +and numerical values of corresponding constraint coefficients $a_j$ must
   1.993 +be placed in locations \verb|ind[1]|, \dots, \verb|ind[len]| and
   1.994 +\verb|val[1]|, \dots, \verb|val[len]|, respectively, where
   1.995 +${\tt len}=|J|$ is the number of constraint coefficients,
   1.996 +$0\leq{\tt len}\leq n$, and $n$ is the number of columns in the problem
   1.997 +object. Coefficients with identical column indices are not allowed.
   1.998 +Zero coefficients are allowed, however, they are ignored.
   1.999 +
  1.1000 +The parameter \verb|type| specifies the constraint type as follows:
  1.1001 +
  1.1002 +\verb|GLP_LO| means inequality constraint $\Sigma a_jx_j\geq b$;
  1.1003 +
  1.1004 +\verb|GLP_UP| means inequality constraint $\Sigma a_jx_j\leq b$;
  1.1005 +
  1.1006 +The parameter \verb|rhs| specifies the right-hand side $b$.
  1.1007 +
  1.1008 +All cutting plane constraints in the cut pool are identified by their
  1.1009 +ordinal numbers 1, 2, \dots, $size$, where $size$ is the current size
  1.1010 +of the cut pool. New constraints are always added to the end of the cut
  1.1011 +pool, thus, ordinal numbers of previously added constraints are not
  1.1012 +changed.
  1.1013 +
  1.1014 +\subsubsection*{Returns}
  1.1015 +
  1.1016 +The routine \verb|glp_ios_add_row| returns the ordinal number of the
  1.1017 +cutting plane constraint added, which is the new size of the cut pool.
  1.1018 +
  1.1019 +\subsubsection*{Example}
  1.1020 +
  1.1021 +\begin{verbatim}
  1.1022 +/* generate triangle cutting plane:
  1.1023 +   x[i] + x[j] + x[k] <= 1 */
  1.1024 +. . .
  1.1025 +/* add the constraint to the cut pool */
  1.1026 +ind[1] = i, val[1] = 1.0;
  1.1027 +ind[2] = j, val[2] = 1.0;
  1.1028 +ind[3] = k, val[3] = 1.0;
  1.1029 +glp_ios_add_row(tree, NULL, TRIANGLE_CUT, 0, 3, ind, val,
  1.1030 +                GLP_UP, 1.0);
  1.1031 +\end{verbatim}
  1.1032 +
  1.1033 +\subsubsection*{Comments}
  1.1034 +
  1.1035 +Cutting plane constraints added to the cut pool are intended to be then
  1.1036 +added only to the {\it current} subproblem, so these constraints can be
  1.1037 +globally as well as locally valid. However, adding a constraint to the
  1.1038 +cut pool does not mean that it will be added to the current
  1.1039 +subproblem---it depends on the solver's decision: if the constraint
  1.1040 +seems to be efficient, it is moved from the pool to the current
  1.1041 +subproblem, otherwise it is simply dropped.\footnote{Globally valid
  1.1042 +constraints could be saved and then re-used for other subproblems, but
  1.1043 +currently such feature is not implemented.}
  1.1044 +
  1.1045 +Normally, every time the callback routine is called for cut generation,
  1.1046 +the cut pool is empty. On the other hand, the solver itself can generate
  1.1047 +cutting plane constraints (like Gomory's or mixed integer rounding
  1.1048 +cuts), in which case the cut pool may be non-empty.
  1.1049 +
  1.1050 +\subsection{glp\_ios\_del\_row---remove constraint from the cut pool}
  1.1051 +
  1.1052 +\subsubsection*{Synopsis}
  1.1053 +
  1.1054 +\begin{verbatim}
  1.1055 +void glp_ios_del_row(glp_tree *tree, int i);
  1.1056 +\end{verbatim}
  1.1057 +
  1.1058 +\subsubsection*{Description}
  1.1059 +
  1.1060 +The routine \verb|glp_ios_del_row| deletes $i$-th row (cutting plane
  1.1061 +constraint) from the cut pool, where $1\leq i\leq size$ is the ordinal
  1.1062 +number of the constraint in the pool, $size$ is the current size of the
  1.1063 +cut pool.
  1.1064 +
  1.1065 +Note that deleting a constraint from the cut pool leads to changing
  1.1066 +ordinal numbers of other constraints remaining in the pool. New ordinal
  1.1067 +numbers of the remaining constraints are assigned under assumption that
  1.1068 +the original order of constraints is not changed. Let, for example,
  1.1069 +there be four constraints $a$, $b$, $c$ and $d$ in the cut pool, which
  1.1070 +have ordinal numbers 1, 2, 3 and 4, respectively, and let constraint
  1.1071 +$b$ have been deleted. Then after deletion the remaining constraint $a$,
  1.1072 +$c$ and $d$ are assigned new ordinal numbers 1, 2 and 3, respectively.
  1.1073 +
  1.1074 +To find the constraint to be deleted the routine \verb|glp_ios_del_row|
  1.1075 +uses ``smart'' linear search, so it is recommended to remove constraints
  1.1076 +in a natural or reverse order and avoid removing them in a random order.
  1.1077 +
  1.1078 +\subsubsection*{Example}
  1.1079 +
  1.1080 +\begin{verbatim}
  1.1081 +/* keep first 10 constraints in the cut pool and remove other
  1.1082 +   constraints */
  1.1083 +while (glp_ios_pool_size(tree) > 10)
  1.1084 +   glp_ios_del_row(tree, glp_ios_pool_size(tree));
  1.1085 +\end{verbatim}
  1.1086 +
  1.1087 +\newpage
  1.1088 +
  1.1089 +\subsection{glp\_ios\_clear\_pool---remove all constraints from the cut
  1.1090 +pool}
  1.1091 +
  1.1092 +\subsubsection*{Synopsis}
  1.1093 +
  1.1094 +\begin{verbatim}
  1.1095 +void glp_ios_clear_pool(glp_tree *tree);
  1.1096 +\end{verbatim}
  1.1097 +
  1.1098 +\subsubsection*{Description}
  1.1099 +
  1.1100 +The routine \verb|glp_ios_clear_pool| makes the cut pool empty deleting
  1.1101 +all existing rows (cutting plane constraints) from it.
  1.1102 +
  1.1103 +%* eof *%