alpar@9: %* glpk05.tex *%
alpar@9: 
alpar@9: \chapter{Branch-and-Cut API Routines}
alpar@9: 
alpar@9: \section{Introduction}
alpar@9: 
alpar@9: \subsection{Using the callback routine}
alpar@9: 
alpar@9: The GLPK MIP solver based on the branch-and-cut method allows the
alpar@9: application program to control the solution process. This is attained
alpar@9: by means of the user-defined callback routine, which is called by the
alpar@9: solver at various points of the branch-and-cut algorithm.
alpar@9: 
alpar@9: The callback routine passed to the MIP solver should be written by the
alpar@9: user and has the following specification:\footnote{The name
alpar@9: {\tt foo\_bar} used here is a placeholder for the callback routine
alpar@9: name.}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    void foo_bar(glp_tree *tree, void *info);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \noindent
alpar@9: where \verb|tree| is a pointer to the data structure \verb|glp_tree|,
alpar@9: which should be used on subsequent calls to branch-and-cut interface
alpar@9: routines, and \verb|info| is a transit pointer passed to the routine
alpar@9: \verb|glp_intopt|, which may be used by the application program to pass
alpar@9: some external data to the callback routine.
alpar@9: 
alpar@9: The callback routine is passed to the MIP solver through the control
alpar@9: parameter structure \verb|glp_iocp| (see Chapter ``Basic API Routines'',
alpar@9: Section ``Mixed integer programming routines'', Subsection ``Solve MIP
alpar@9: problem with the branch-and-cut method'') as follows:
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9:    glp_prob *mip;
alpar@9:    glp_iocp parm;
alpar@9:    . . .
alpar@9:    glp_init_iocp(&parm);
alpar@9:    . . .
alpar@9:    parm.cb_func = foo_bar;
alpar@9:    parm.cb_info = ... ;
alpar@9:    ret = glp_intopt(mip, &parm);
alpar@9:    . . .
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: To determine why it is being called by the MIP solver the callback
alpar@9: routine should use the routine \verb|glp_ios_reason| (described in this
alpar@9: section below), which returns a code indicating the reason for calling.
alpar@9: Depending on the reason the callback routine may perform necessary
alpar@9: actions to control the solution process.
alpar@9: 
alpar@9: The reason codes, which correspond to various point of the
alpar@9: branch-and-cut algorithm implemented in the MIP solver, are described
alpar@9: in Subsection ``Reasons for calling the callback routine'' below.
alpar@9: 
alpar@9: To ignore calls for reasons, which are not processed by the callback
alpar@9: routine, it should just return to the MIP solver doing nothing. For
alpar@9: example:
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void foo_bar(glp_tree *tree, void *info)
alpar@9: {     . . .
alpar@9:       switch (glp_ios_reason(tree))
alpar@9:       {  case GLP_IBRANCH:
alpar@9:             . . .
alpar@9:             break;
alpar@9:          case GLP_ISELECT:
alpar@9:             . . .
alpar@9:             break;
alpar@9:          default:
alpar@9:             /* ignore call for other reasons */
alpar@9:             break;
alpar@9:       }
alpar@9:       return;
alpar@9: }
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: To control the solution process as well as to obtain necessary
alpar@9: information the callback routine may use the branch-and-cut API
alpar@9: routines described in this chapter. Names of all these routines begin
alpar@9: with `\verb|glp_ios_|'.
alpar@9: 
alpar@9: \subsection{Branch-and-cut algorithm}
alpar@9: 
alpar@9: This section gives a schematic description of the branch-and-cut
alpar@9: algorithm as it is implemented in the GLPK MIP solver.
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: {\it 1. Initialization}
alpar@9: 
alpar@9: Set $L:=\{P_0\}$, where $L$ is the {\it active list} (i.e. the list of
alpar@9: active subproblems), $P_0$ is the original MIP problem to be solved.
alpar@9: 
alpar@9: Set $z^{\it best}:=+\infty$ (in case of minimization) or
alpar@9: $z^{\it best}:=-\infty$ (in case of maximization), where $z^{\it best}$
alpar@9: is {\it incumbent value}, i.e. an upper (minimization) or lower
alpar@9: (maximization) global bound for $z^{\it opt}$, the optimal objective
alpar@9: value for $P^0$.
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: {\it 2. Subproblem selection}
alpar@9: 
alpar@9: If $L=\varnothing$ then GO TO 9.
alpar@9: 
alpar@9: Select $P\in L$, i.e. make active subproblem $P$ current.
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: {\it 3. Solving LP relaxation}
alpar@9: 
alpar@9: Solve $P^{\it LP}$, which is LP relaxation of $P$.
alpar@9: 
alpar@9: If $P^{\it LP}$ has no primal feasible solution then GO TO 8.
alpar@9: 
alpar@9: Let $z^{\it LP}$ be the optimal objective value for $P^{\it LP}$.
alpar@9: 
alpar@9: If $z^{\it LP}\geq z^{\it best}$ (in case of minimization) or
alpar@9: $z^{\it LP}\leq z^{\rm best}$ (in case of maximization) then GO TO 8.
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: {\it 4. Adding ``lazy'' constraints}
alpar@9: 
alpar@9: Let $x^{\it LP}$ be the optimal solution to $P^{\it LP}$.
alpar@9: 
alpar@9: If there are ``lazy'' constraints (i.e. essential constraints not
alpar@9: included in the original MIP problem $P_0$), which are violated at the
alpar@9: optimal point $x^{\it LP}$, add them to $P$, and GO TO 3.
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: {\it 5. Check for integrality}
alpar@9: 
alpar@9: Let $x_j$ be a variable, which is required to be integer, and let
alpar@9: $x^{\it LP}_j\in x^{\it LP}$ be its value in the optimal solution to
alpar@9: $P^{\it LP}$.
alpar@9: 
alpar@9: If $x^{\it LP}_j$ are integral for all integer variables, then a better
alpar@9: integer feasible solution is found. Store its components, set
alpar@9: $z^{\it best}:=z^{\it LP}$, and GO TO 8.
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: {\it 6. Adding cutting planes}
alpar@9: 
alpar@9: If there are cutting planes (i.e. valid constraints for $P$),
alpar@9: which are violated at the optimal point $x^{\it LP}$, add them to $P$,
alpar@9: and GO TO 3.
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: {\it 7. Branching}
alpar@9: 
alpar@9: Select {\it branching variable} $x_j$, i.e. a variable, which is
alpar@9: required to be integer, and whose value $x^{\it LP}_j\in x^{\it LP}$ is
alpar@9: fractional in the optimal solution to $P^{\it LP}$.
alpar@9: 
alpar@9: Create new subproblem $P^D$ (so called {\it down branch}), which is
alpar@9: identical to the current subproblem $P$ with exception that the upper
alpar@9: bound of $x_j$ is replaced by $\lfloor x^{\it LP}_j\rfloor$. (For
alpar@9: example, if $x^{\it LP}_j=3.14$, the new upper bound of $x_j$ in the
alpar@9: down branch will be $\lfloor 3.14\rfloor=3$.)
alpar@9: 
alpar@9: Create new subproblem $P^U$ (so called {\it up branch}), which is
alpar@9: identical to the current subproblem $P$ with exception that the lower
alpar@9: bound of $x_j$ is replaced by $\lceil x^{\it LP}_j\rceil$. (For example,
alpar@9: if $x^{\it LP}_j=3.14$, the new lower bound of $x_j$ in the up branch
alpar@9: will be $\lceil 3.14\rceil=4$.)
alpar@9: 
alpar@9: Set $L:=(L\backslash\{P\})\cup\{P^D,P^U\}$, i.e. remove the current
alpar@9: subproblem $P$ from the active list $L$ and add two new subproblems
alpar@9: $P^D$ and $P^U$ to it. Then GO TO 2.
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: {\it 8. Pruning}
alpar@9: 
alpar@9: Remove from the active list $L$ all subproblems (including the current
alpar@9: one), whose local bound $\widetilde{z}$ is not better than the global
alpar@9: bound $z^{\it best}$, i.e. set $L:=L\backslash\{P\}$ for all $P$, where
alpar@9: $\widetilde{z}\geq z^{\it best}$ (in case of minimization) or
alpar@9: $\widetilde{z}\leq z^{\it best}$ (in case of maximization), and then
alpar@9: GO TO 2.
alpar@9: 
alpar@9: The local bound $\widetilde{z}$ for subproblem $P$ is an lower
alpar@9: (minimization) or upper (maximization) bound for integer optimal
alpar@9: solution to {\it this} subproblem (not to the original problem). This
alpar@9: bound is local in the sense that only subproblems in the subtree rooted
alpar@9: at node $P$ cannot have better integer feasible solutions. Note that
alpar@9: the local bound is not necessarily the optimal objective value to LP
alpar@9: relaxation $P^{\it LP}$.
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: {\it 9. Termination}
alpar@9: 
alpar@9: If $z^{\it best}=+\infty$ (in case of minimization) or
alpar@9: $z^{\it best}=-\infty$ (in case of maximization), the original problem
alpar@9: $P_0$ has no integer feasible solution. Otherwise, the last integer
alpar@9: feasible solution stored on step 5 is the integer optimal solution to
alpar@9: the original problem $P_0$ with $z^{\it opt}=z^{\it best}$. STOP.
alpar@9: 
alpar@9: \subsection{The search tree}
alpar@9: 
alpar@9: On the branching step of the branch-and-cut algorithm the current
alpar@9: subproblem is divided into two\footnote{In more general cases the
alpar@9: current subproblem may be divided into more than two subproblems.
alpar@9: However, currently such feature is not used in GLPK.} new subproblems,
alpar@9: so the set of all subproblems can be represented in the form of a rooted
alpar@9: tree, which is called the {\it search} or {\it branch-and-bound} tree.
alpar@9: An example of the search tree is shown on Fig.~1. Each node of the
alpar@9: search tree corresponds to a subproblem, so the terms `node' and
alpar@9: `subproblem' may be used synonymously.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \begin{figure}[t]
alpar@9: \noindent\hfil
alpar@9: \xymatrix @R=20pt @C=10pt
alpar@9: {&&&&&&*+<14pt>[o][F=]{A}\ar@{-}[dllll]\ar@{-}[dr]\ar@{-}[drrrr]&&&&\\
alpar@9: &&*+<14pt>[o][F=]{B}\ar@{-}[dl]\ar@{-}[dr]&&&&&*+<14pt>[o][F=]{C}
alpar@9: \ar@{-}[dll]\ar@{-}[dr]\ar@{-}[drrr]&&&*+<14pt>[o][F-]{\times}\\
alpar@9: &*+<14pt>[o][F-]{\times}\ar@{-}[dl]\ar@{-}[d]\ar@{-}[dr]&&
alpar@9: *+<14pt>[o][F-]{D}&&*+<14pt>[o][F=]{E}\ar@{-}[dl]\ar@{-}[dr]&&&
alpar@9: *+<14pt>[o][F=]{F}\ar@{-}[dl]\ar@{-}[dr]&&*+<14pt>[o][F-]{G}\\
alpar@9: *+<14pt>[o][F-]{\times}&*+<14pt>[o][F-]{\times}&*+<14pt>[o][F-]{\times}
alpar@9: &&*+<14pt>[][F-]{H}&&*+<14pt>[o][F-]{I}&*+<14pt>[o][F-]{\times}&&
alpar@9: *+<14pt>[o][F-]{J}&\\}
alpar@9: 
alpar@9: \bigskip
alpar@9: 
alpar@9: \noindent\hspace{.8in}
alpar@9: \xymatrix @R=11pt
alpar@9: {*+<20pt>[][F-]{}&*\txt{\makebox[1in][l]{Current}}&&
alpar@9: *+<20pt>[o][F-]{}&*\txt{\makebox[1in][l]{Active}}\\
alpar@9: *+<20pt>[o][F=]{}&*\txt{\makebox[1in][l]{Non-active}}&&
alpar@9: *+<14pt>[o][F-]{\times}&*\txt{\makebox[1in][l]{Fathomed}}\\
alpar@9: }
alpar@9: 
alpar@9: \begin{center}
alpar@9: Fig. 1. An example of the search tree.
alpar@9: \end{center}
alpar@9: \end{figure}
alpar@9: 
alpar@9: In GLPK each node may have one of the following four statuses:
alpar@9: 
alpar@9: $\bullet$ {\it current node} is the active node currently being
alpar@9: processed;
alpar@9: 
alpar@9: $\bullet$ {\it active node} is a leaf node, which still has to be
alpar@9: processed;
alpar@9: 
alpar@9: $\bullet$ {\it non-active node} is a node, which has been processed,
alpar@9: but not fathomed;
alpar@9: 
alpar@9: $\bullet$ {\it fathomed node} is a node, which has been processed and
alpar@9: fathomed.
alpar@9: 
alpar@9: In the data structure representing the search tree GLPK keeps only
alpar@9: current, active, and non-active nodes. Once a node has been fathomed,
alpar@9: it is removed from the tree data structure.
alpar@9: 
alpar@9: Being created each node of the search tree is assigned a distinct
alpar@9: positive integer called the {\it subproblem reference number}, which
alpar@9: may be used by the application program to specify a particular node of
alpar@9: the tree. The root node corresponding to the original problem to be
alpar@9: solved is always assigned the reference number 1.
alpar@9: 
alpar@9: \subsection{Current subproblem}
alpar@9: 
alpar@9: The current subproblem is a MIP problem corresponding to the current
alpar@9: node of the search tree. It is represented as the GLPK problem object
alpar@9: (\verb|glp_prob|) that allows the application program using API routines
alpar@9: to access its content in the standard way. If the MIP presolver is not
alpar@9: used, it is the original problem object passed to the routine
alpar@9: \verb|glp_intopt|; otherwise, it is an internal problem object built by
alpar@9: the MIP presolver.
alpar@9: 
alpar@9: Note that the problem object is used by the MIP solver itself during
alpar@9: the solution process for various purposes (to solve LP relaxations, to
alpar@9: perfom branching, etc.), and even if the MIP presolver is not used, the
alpar@9: current content of the problem object may differ from its original
alpar@9: content. For example, it may have additional rows, bounds of some rows
alpar@9: and columns may be changed, etc. In particular, LP segment of the
alpar@9: problem object corresponds to LP relaxation of the current subproblem.
alpar@9: However, on exit from the MIP solver the content of the problem object
alpar@9: is restored to its original state.
alpar@9: 
alpar@9: To obtain information from the problem object the application program
alpar@9: may use any API routines, which do not change the object. Using API
alpar@9: routines, which change the problem object, is restricted to stipulated
alpar@9: cases.
alpar@9: 
alpar@9: \subsection{The cut pool}
alpar@9: 
alpar@9: The {\it cut pool} is a set of cutting plane constraints maintained by
alpar@9: the MIP solver. It is used by the GLPK cut generation routines and may
alpar@9: be used by the application program in the same way, i.e. rather than
alpar@9: to add cutting plane constraints directly to the problem object the
alpar@9: application program may store them to the cut pool. In the latter case
alpar@9: the solver looks through the cut pool, selects efficient constraints,
alpar@9: and adds them to the problem object.
alpar@9: 
alpar@9: \subsection{Reasons for calling the callback routine}
alpar@9: 
alpar@9: The callback routine may be called by the MIP solver for the following
alpar@9: reasons.
alpar@9: 
alpar@9: \subsubsection*{Request for subproblem selection}
alpar@9: 
alpar@9: The callback routine is called with the reason code \verb|GLP_ISELECT|
alpar@9: if the current subproblem has been fathomed and therefore there is no
alpar@9: current subproblem.
alpar@9: 
alpar@9: In response the callback routine may select some subproblem from the
alpar@9: active list and pass its reference number to the solver using the
alpar@9: routine \verb|glp_ios_select_node|, in which case the solver continues
alpar@9: the search from the specified active subproblem. If no selection is made
alpar@9: by the callback routine, the solver uses a backtracking technique
alpar@9: specified by the control parameter \verb|bt_tech|.
alpar@9: 
alpar@9: To explore the active list (i.e. active nodes of the branch-and-bound
alpar@9: tree) the callback routine may use the routines \verb|glp_ios_next_node|
alpar@9: and \verb|glp_ios_prev_node|.
alpar@9: 
alpar@9: \subsubsection*{Request for preprocessing}
alpar@9: 
alpar@9: The callback routine is called with the reason code \verb|GLP_IPREPRO|
alpar@9: if the current subproblem has just been selected from the active list
alpar@9: and its LP relaxation is not solved yet.
alpar@9: 
alpar@9: In response the callback routine may perform some preprocessing of the
alpar@9: current subproblem like tightening bounds of some variables or removing
alpar@9: bounds of some redundant constraints.
alpar@9: 
alpar@9: \subsubsection*{Request for row generation}
alpar@9: 
alpar@9: The callback routine is called with the reason code \verb|GLP_IROWGEN|
alpar@9: if LP relaxation of the current subproblem has just been solved to
alpar@9: optimality and its objective value is better than the best known integer
alpar@9: feasible solution.
alpar@9: 
alpar@9: In response the callback routine may add one or more ``lazy''
alpar@9: constraints (rows), which are violated by the current optimal solution
alpar@9: of LP relaxation, using API routines \verb|glp_add_rows|,
alpar@9: \verb|glp_set_row_name|, \verb|glp_set_row_bnds|, and
alpar@9: \verb|glp_set_mat_row|, in which case the solver will perform
alpar@9: re-optimization of LP relaxation. If there are no violated constraints,
alpar@9: the callback routine should just return.
alpar@9: 
alpar@9: Optimal solution components for LP relaxation can be obtained with API
alpar@9: routines \verb|glp_get_obj_val|, \verb|glp_get_row_prim|,
alpar@9: \verb|glp_get_row_dual|, \verb|glp_get_col_prim|, and
alpar@9: \verb|glp_get_col_dual|.
alpar@9: 
alpar@9: \subsubsection*{Request for heuristic solution}
alpar@9: 
alpar@9: The callback routine is called with the reason code \verb|GLP_IHEUR|
alpar@9: if LP relaxation of the current subproblem being solved to optimality
alpar@9: is integer infeasible (i.e. values of some structural variables of
alpar@9: integer kind are fractional), though its objective value is better than
alpar@9: the best known integer feasible solution.
alpar@9: 
alpar@9: In response the callback routine may try applying a primal heuristic
alpar@9: to find an integer feasible solution,\footnote{Integer feasible to the
alpar@9: original MIP problem, not to the current subproblem.} which is better
alpar@9: than the best known one. In case of success the callback routine may
alpar@9: store such better solution in the problem object using the routine
alpar@9: \verb|glp_ios_heur_sol|.
alpar@9: 
alpar@9: \subsubsection*{Request for cut generation}
alpar@9: 
alpar@9: The callback routine is called with the reason code \verb|GLP_ICUTGEN|
alpar@9: if LP relaxation of the current subproblem being solved to optimality
alpar@9: is integer infeasible (i.e. values of some structural variables of
alpar@9: integer kind are fractional), though its objective value is better than
alpar@9: the best known integer feasible solution.
alpar@9: 
alpar@9: In response the callback routine may reformulate the {\it current}
alpar@9: subproblem (before it will be splitted up due to branching) by adding to
alpar@9: the problem object one or more {\it cutting plane constraints}, which
alpar@9: cut off the fractional optimal point from the MIP
alpar@9: polytope.\footnote{Since these constraints are added to the current
alpar@9: subproblem, they may be globally as well as locally valid.}
alpar@9: 
alpar@9: Adding cutting plane constraints may be performed in two ways.
alpar@9: One way is the same as for the reason code \verb|GLP_IROWGEN| (see
alpar@9: above), in which case the callback routine adds new rows corresponding
alpar@9: to cutting plane constraints directly to the current subproblem.
alpar@9: 
alpar@9: The other way is to add cutting plane constraints to the {\it cut pool},
alpar@9: a set of cutting plane constraints maintained by the solver, rather than
alpar@9: directly to the current subproblem. In this case after return from the
alpar@9: callback routine the solver looks through the cut pool, selects
alpar@9: efficient cutting plane constraints, adds them to the current
alpar@9: subproblem, drops other constraints, and then performs re-optimization.
alpar@9: 
alpar@9: \subsubsection*{Request for branching}
alpar@9: 
alpar@9: The callback routine is called with the reason code \verb|GLP_IBRANCH|
alpar@9: if LP relaxation of the current subproblem being solved to optimality
alpar@9: is integer infeasible (i.e. values of some structural variables of
alpar@9: integer kind are fractional), though its objective value is better than
alpar@9: the best known integer feasible solution.
alpar@9: 
alpar@9: In response the callback routine may choose some variable suitable for
alpar@9: branching (i.e. integer variable, whose value in optimal solution to
alpar@9: LP relaxation of the current subproblem is fractional) and pass its
alpar@9: ordinal number to the solver using the routine
alpar@9: \verb|glp_ios_branch_upon|, in which case the solver splits the current
alpar@9: subproblem in two new subproblems and continues the search. If no choice
alpar@9: is made by the callback routine, the solver uses a branching technique
alpar@9: specified by the control parameter \verb|br_tech|.
alpar@9: 
alpar@9: \subsubsection*{Better integer solution found}
alpar@9: 
alpar@9: The callback routine is called with the reason code \verb|GLP_IBINGO|
alpar@9: if LP relaxation of the current subproblem being solved to optimality
alpar@9: is integer feasible (i.e. values of all structural variables of integer
alpar@9: kind are integral within the working precision) and its objective value
alpar@9: is better than the best known integer feasible solution.
alpar@9: 
alpar@9: Optimal solution components for LP relaxation can be obtained in the
alpar@9: same way as for the reason code \verb|GLP_IROWGEN| (see above).
alpar@9: 
alpar@9: Components of the new MIP solution can be obtained with API routines
alpar@9: \verb|glp_mip_obj_val|, \verb|glp_mip_row_val|, and
alpar@9: \verb|glp_mip_col_val|. Note, however, that due to row/cut generation
alpar@9: there may be additional rows in the problem object.
alpar@9: 
alpar@9: The difference between optimal solution to LP relaxation and
alpar@9: corresponding MIP solution is that in the former case some structural
alpar@9: variables of integer kind (namely, basic variables) may have values,
alpar@9: which are close to nearest integers within the working precision, while
alpar@9: in the latter case all such variables have exact integral values.
alpar@9: 
alpar@9: The reason \verb|GLP_IBINGO| is intended only for informational
alpar@9: purposes, so the callback routine should not modify the problem object
alpar@9: in this case.
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{Basic routines}
alpar@9: 
alpar@9: \subsection{glp\_ios\_reason---determine reason for calling the
alpar@9: callback routine}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_ios_reason(glp_tree *tree);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ios_reason| returns a code, which indicates why
alpar@9: the user-defined callback routine is being called:
alpar@9: 
alpar@9: \verb|GLP_ISELECT|---request for subproblem selection;
alpar@9: 
alpar@9: \verb|GLP_IPREPRO|---request for preprocessing;
alpar@9: 
alpar@9: \verb|GLP_IROWGEN|---request for row generation;
alpar@9: 
alpar@9: \verb|GLP_IHEUR  |---request for heuristic solution;
alpar@9: 
alpar@9: \verb|GLP_ICUTGEN|---request for cut generation;
alpar@9: 
alpar@9: \verb|GLP_IBRANCH|---request for branching;
alpar@9: 
alpar@9: \verb|GLP_IBINGO |---better integer solution found.
alpar@9: 
alpar@9: \subsection{glp\_ios\_get\_prob---access the problem object}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: glp_prob *glp_ios_get_prob(glp_tree *tree);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_ios_get_prob| can be called from the user-defined
alpar@9: callback routine to access the problem object, which is used by the MIP
alpar@9: solver. It is the original problem object passed to the routine
alpar@9: \verb|glp_intopt| if the MIP presolver is not used; otherwise it is an
alpar@9: internal problem object built by the presolver.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ios_get_prob| returns a pointer to the problem
alpar@9: object used by the MIP solver.
alpar@9: 
alpar@9: \subsubsection*{Comments}
alpar@9: 
alpar@9: To obtain various information about the problem instance the callback
alpar@9: routine can access the problem object (i.e. the object of type
alpar@9: \verb|glp_prob|) using the routine \verb|glp_ios_get_prob|. It is the
alpar@9: original problem object passed to the routine \verb|glp_intopt| if the
alpar@9: MIP presolver is not used; otherwise it is an internal problem object
alpar@9: built by the presolver.
alpar@9: 
alpar@9: \subsection{glp\_ios\_row\_attr---determine additional row attributes}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_ios_row_attr| retrieves additional attributes of
alpar@9: $i$-th row of the current subproblem and stores them in the structure
alpar@9: \verb|glp_attr|, which the parameter \verb|attr| points to.
alpar@9: 
alpar@9: The structure \verb|glp_attr| has the following fields:
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int level}}\\
alpar@9: &Subproblem level at which the row was created. (If \verb|level| = 0,
alpar@9: the row was added either to the original problem object passed to the
alpar@9: routine \verb|glp_intopt| or to the root subproblem on generating
alpar@9: ``lazy'' or/and cutting plane constraints.)\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int origin}}\\
alpar@9: &The row origin flag:\\
alpar@9: &\verb|GLP_RF_REG |---regular constraint;\\
alpar@9: &\verb|GLP_RF_LAZY|---``lazy'' constraint;\\
alpar@9: &\verb|GLP_RF_CUT |---cutting plane constraint.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \medskip
alpar@9: 
alpar@9: \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}}
alpar@9: \multicolumn{2}{@{}l}{{\tt int klass}}\\
alpar@9: &The row class descriptor, which is a number passed to the routine
alpar@9: \verb|glp_ios_add_row| as its third parameter. If the row is a cutting
alpar@9: plane constraint generated by the solver, its class may be the
alpar@9: following:\\
alpar@9: &\verb|GLP_RF_GMI |---Gomory's mixed integer cut;\\
alpar@9: &\verb|GLP_RF_MIR |---mixed integer rounding cut;\\
alpar@9: &\verb|GLP_RF_COV |---mixed cover cut;\\
alpar@9: &\verb|GLP_RF_CLQ |---clique cut.\\
alpar@9: \end{tabular}
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_ios\_mip\_gap---compute relative MIP gap}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_ios_mip_gap(glp_tree *tree);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_ios_mip_gap| computes the relative MIP gap (also
alpar@9: called {\it duality gap}) with the following formula:
alpar@9: $${\tt gap} = \frac{|{\tt best\_mip} - {\tt best\_bnd}|}
alpar@9: {|{\tt best\_mip}| + {\tt DBL\_EPSILON}}$$
alpar@9: where \verb|best_mip| is the best integer feasible solution found so
alpar@9: far, \verb|best_bnd| is the best (global) bound. If no integer feasible
alpar@9: solution has been found yet, \verb|gap| is set to \verb|DBL_MAX|.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ios_mip_gap| returns the relative MIP gap.
alpar@9: 
alpar@9: \subsubsection*{Comments}
alpar@9: 
alpar@9: The relative MIP gap is used to measure the quality of the best integer
alpar@9: feasible solution found so far, because the optimal solution value
alpar@9: $z^*$ for the original MIP problem always lies in the range
alpar@9: $${\tt best\_bnd}\leq z^*\leq{\tt best\_mip}$$
alpar@9: in case of minimization, or in the range
alpar@9: $${\tt best\_mip}\leq z^*\leq{\tt best\_bnd}$$
alpar@9: in case of maximization.
alpar@9: 
alpar@9: To express the relative MIP gap in percents the value returned by the
alpar@9: routine \verb|glp_ios_mip_gap| should be multiplied by 100\%.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_ios\_node\_data---access application-specific data}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void *glp_ios_node_data(glp_tree *tree, int p);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_ios_node_data| allows the application accessing a
alpar@9: memory block allocated for the subproblem (which may be active or
alpar@9: inactive), whose reference number is $p$.
alpar@9: 
alpar@9: The size of the block is defined by the control parameter \verb|cb_size|
alpar@9: passed to the routine \verb|glp_intopt|. The block is initialized by
alpar@9: binary zeros on creating corresponding subproblem, and its contents is
alpar@9: kept until the subproblem will be removed from the tree.
alpar@9: 
alpar@9: The application may use these memory blocks to store specific data for
alpar@9: each subproblem.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ios_node_data| returns a pointer to the memory
alpar@9: block for the specified subproblem. Note that if \verb|cb_size| = 0, the
alpar@9: routine returns a null pointer.
alpar@9: 
alpar@9: \subsection{glp\_ios\_select\_node---select subproblem to continue the
alpar@9: search}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_ios_select_node(glp_tree *tree, int p);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_ios_select_node| can be called from the
alpar@9: user-defined callback routine in response to the reason
alpar@9: \verb|GLP_ISELECT| to select an active subproblem, whose reference
alpar@9: number is $p$. The search will be continued from the subproblem
alpar@9: selected.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_ios\_heur\_sol---provide solution found by heuristic}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_ios_heur_sol(glp_tree *tree, const double x[]);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_ios_heur_sol| can be called from the user-defined
alpar@9: callback routine in response to the reason \verb|GLP_IHEUR| to provide
alpar@9: an integer feasible solution found by a primal heuristic.
alpar@9: 
alpar@9: Primal values of {\it all} variables (columns) found by the heuristic
alpar@9: should be placed in locations $x[1]$, \dots, $x[n]$, where $n$ is the
alpar@9: number of columns in the original problem object. Note that the routine
alpar@9: \verb|glp_ios_heur_sol| does {\it not} check primal feasibility of the
alpar@9: solution provided.
alpar@9: 
alpar@9: Using the solution passed in the array $x$ the routine computes value
alpar@9: of the objective function. If the objective value is better than the
alpar@9: best known integer feasible solution, the routine computes values of
alpar@9: auxiliary variables (rows) and stores all solution components in the
alpar@9: problem object.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the provided solution is accepted, the routine
alpar@9: \verb|glp_ios_heur_sol| returns zero. Otherwise, if the provided
alpar@9: solution is rejected, the routine returns non-zero.
alpar@9: 
alpar@9: \subsection{glp\_ios\_can\_branch---check if can branch upon specified
alpar@9: variable}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_ios_can_branch(glp_tree *tree, int j);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If $j$-th variable (column) can be used to branch upon, the routine
alpar@9: returns non-zero, otherwise zero.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_ios\_branch\_upon---choose variable to branch upon}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_ios_branch_upon(glp_tree *tree, int j, int sel);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_ios_branch_upon| can be called from the
alpar@9: user-defined callback routine in response to the reason
alpar@9: \verb|GLP_IBRANCH| to choose a branching variable, whose ordinal number
alpar@9: is $j$. Should note that only variables, for which the routine
alpar@9: \verb|glp_ios_can_branch| returns non-zero, can be used to branch upon.
alpar@9: 
alpar@9: The parameter \verb|sel| is a flag that indicates which branch
alpar@9: (subproblem) should be selected next to continue the search:
alpar@9: 
alpar@9: \verb|GLP_DN_BRNCH|---select down-branch;
alpar@9: 
alpar@9: \verb|GLP_UP_BRNCH|---select up-branch;
alpar@9: 
alpar@9: \verb|GLP_NO_BRNCH|---use general selection technique.
alpar@9: 
alpar@9: \subsubsection*{Comments}
alpar@9: 
alpar@9: On branching the solver removes the current active subproblem from the
alpar@9: active list and creates two new subproblems ({\it down-} and {\it
alpar@9: up-branches}), which are added to the end of the active list. Note that
alpar@9: the down-branch is created before the up-branch, so the last active
alpar@9: subproblem will be the up-branch.
alpar@9: 
alpar@9: The down- and up-branches are identical to the current subproblem with
alpar@9: exception that in the down-branch the upper bound of $x_j$, the variable
alpar@9: chosen to branch upon, is replaced by $\lfloor x_j^*\rfloor$, while in
alpar@9: the up-branch the lower bound of $x_j$ is replaced by
alpar@9: $\lceil x_j^*\rceil$, where $x_j^*$ is the value of $x_j$ in optimal
alpar@9: solution to LP relaxation of the current subproblem. For example, if
alpar@9: $x_j^*=3.14$, the new upper bound of $x_j$ in the down-branch is
alpar@9: $\lfloor 3.14\rfloor=3$, and the new lower bound in the up-branch is
alpar@9: $\lceil 3.14\rceil=4$.)
alpar@9: 
alpar@9: Additionally the callback routine may select either down- or up-branch,
alpar@9: from which the solver will continue the search. If none of the branches
alpar@9: is selected, a general selection technique will be used.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_ios\_terminate---terminate the solution process}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_ios_terminate(glp_tree *tree);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_ios_terminate| sets a flag indicating that the
alpar@9: MIP solver should prematurely terminate the search.
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{The search tree exploring routines}
alpar@9: 
alpar@9: \subsection{glp\_ios\_tree\_size---determine size of the search tree}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt,
alpar@9:       int *t_cnt);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_ios_tree_size| stores the following three counts
alpar@9: which characterize the current size of the search tree:
alpar@9: 
alpar@9: \verb|a_cnt| is the current number of active nodes, i.e. the current
alpar@9: size of the active list;
alpar@9: 
alpar@9: \verb|n_cnt| is the current number of all (active and inactive) nodes;
alpar@9: 
alpar@9: \verb|t_cnt| is the total number of nodes including those which have
alpar@9: been already removed from the tree. This count is increased whenever
alpar@9: a new node appears in the tree and never decreased.
alpar@9: 
alpar@9: If some of the parameters \verb|a_cnt|, \verb|n_cnt|, \verb|t_cnt| is
alpar@9: a null pointer, the corresponding count is not stored.
alpar@9: 
alpar@9: \subsection{glp\_ios\_curr\_node---determine current active subprob-\\
alpar@9: lem}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_ios_curr_node(glp_tree *tree);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ios_curr_node| returns the reference number of the
alpar@9: current active subproblem. However, if the current subproblem does not
alpar@9: exist, the routine returns zero.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_ios\_next\_node---determine next active subproblem}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_ios_next_node(glp_tree *tree, int p);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the parameter $p$ is zero, the routine \verb|glp_ios_next_node|
alpar@9: returns the reference number of the first active subproblem. However,
alpar@9: if the tree is empty, zero is returned.
alpar@9: 
alpar@9: If the parameter $p$ is not zero, it must specify the reference number
alpar@9: of some active subproblem, in which case the routine returns the
alpar@9: reference number of the next active subproblem. However, if there is
alpar@9: no next active subproblem in the list, zero is returned.
alpar@9: 
alpar@9: All subproblems in the active list are ordered chronologically, i.e.
alpar@9: subproblem $A$ precedes subproblem $B$ if $A$ was created before $B$.
alpar@9: 
alpar@9: \subsection{glp\_ios\_prev\_node---determine previous active subproblem}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_ios_prev_node(glp_tree *tree, int p);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: If the parameter $p$ is zero, the routine \verb|glp_ios_prev_node|
alpar@9: returns the reference number of the last active subproblem. However, if
alpar@9: the tree is empty, zero is returned.
alpar@9: 
alpar@9: If the parameter $p$ is not zero, it must specify the reference number
alpar@9: of some active subproblem, in which case the routine returns the
alpar@9: reference number of the previous active subproblem. However, if there
alpar@9: is no previous active subproblem in the list, zero is returned.
alpar@9: 
alpar@9: All subproblems in the active list are ordered chronologically, i.e.
alpar@9: subproblem $A$ precedes subproblem $B$ if $A$ was created before $B$.
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_ios\_up\_node---determine parent subproblem}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_ios_up_node(glp_tree *tree, int p);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The parameter $p$ must specify the reference number of some (active or
alpar@9: inactive) subproblem, in which case the routine \verb|iet_get_up_node|
alpar@9: returns the reference number of its parent subproblem. However, if the
alpar@9: specified subproblem is the root of the tree and, therefore, has
alpar@9: no parent, the routine returns zero.
alpar@9: 
alpar@9: \subsection{glp\_ios\_node\_level---determine subproblem level}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_ios_node_level(glp_tree *tree, int p);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ios_node_level| returns the level of the
alpar@9: subproblem,\linebreak whose reference number is $p$, in the
alpar@9: branch-and-bound tree. (The root subproblem has level 0, and the level
alpar@9: of any other subproblem is the level of its parent plus one.)
alpar@9: 
alpar@9: \subsection{glp\_ios\_node\_bound---determine subproblem local\\bound}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: double glp_ios_node_bound(glp_tree *tree, int p);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ios_node_bound| returns the local bound for
alpar@9: (active or inactive) subproblem, whose reference number is $p$.
alpar@9: 
alpar@9: \subsubsection*{Comments}
alpar@9: 
alpar@9: The local bound for subproblem $p$ is an lower (minimization) or upper
alpar@9: (maximization) bound for integer optimal solution to {\it this}
alpar@9: subproblem (not to the original problem). This bound is local in the
alpar@9: sense that only subproblems in the subtree rooted at node $p$ cannot
alpar@9: have better integer feasible solutions.
alpar@9: 
alpar@9: On creating a subproblem (due to the branching step) its local bound is
alpar@9: inherited from its parent and then may get only stronger (never weaker).
alpar@9: For the root subproblem its local bound is initially set to
alpar@9: \verb|-DBL_MAX| (minimization) or \verb|+DBL_MAX| (maximization) and
alpar@9: then improved as the root LP relaxation has been solved.
alpar@9: 
alpar@9: Note that the local bound is not necessarily the optimal objective value
alpar@9: to corresponding LP relaxation.
alpar@9: 
alpar@9: \subsection{glp\_ios\_best\_node---find active subproblem with best
alpar@9: local bound}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_ios_best_node(glp_tree *tree);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ios_best_node| returns the reference number of
alpar@9: the active subproblem, whose local bound is best (i.e. smallest in case
alpar@9: of minimization or largest in case of maximization). However, if the
alpar@9: tree is empty, the routine returns zero.
alpar@9: 
alpar@9: \subsubsection*{Comments}
alpar@9: 
alpar@9: The best local bound is an lower (minimization) or upper (maximization)
alpar@9: bound for integer optimal solution to the original MIP problem.
alpar@9: 
alpar@9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \section{The cut pool routines}
alpar@9: 
alpar@9: \subsection{glp\_ios\_pool\_size---determine current size of the cut\\
alpar@9: pool}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_ios_pool_size(glp_tree *tree);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ios_pool_size| returns the current size of the
alpar@9: cut pool, that is, the number of cutting plane constraints currently
alpar@9: added to it.
alpar@9: 
alpar@9: \subsection{glp\_ios\_add\_row---add constraint to the cut pool}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: int glp_ios_add_row(glp_tree *tree, const char *name,
alpar@9:       int klass, int flags, int len, const int ind[],
alpar@9:       const double val[], int type, double rhs);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_ios_add_row| adds specified row (cutting plane
alpar@9: constraint) to the cut pool.
alpar@9: 
alpar@9: The cutting plane constraint should have the following format:
alpar@9: $$\sum_{j\in J}a_jx_j\left\{\begin{array}{@{}c@{}}\geq\\\leq\\
alpar@9: \end{array}\right\}b,$$
alpar@9: where $J$ is a set of indices (ordinal numbers) of structural variables,
alpar@9: $a_j$ are constraint coefficients, $x_j$ are structural variables, $b$
alpar@9: is the right-hand side.
alpar@9: 
alpar@9: The parameter \verb|name| specifies a symbolic name assigned to the
alpar@9: constraint (1 up to 255 characters). If it is \verb|NULL| or an empty
alpar@9: string, no name is assigned.
alpar@9: 
alpar@9: The parameter \verb|klass| specifies the constraint class, which must
alpar@9: be either zero or a number in the range from 101 to 200. The application
alpar@9: may use this attribute to distinguish between cutting plane constraints
alpar@9: of different classes.\footnote{Constraint classes numbered from 1 to 100
alpar@9: are reserved for GLPK cutting plane generators.}
alpar@9: 
alpar@9: The parameter \verb|flags| currently is not used and must be zero.
alpar@9: 
alpar@9: Ordinal numbers of structural variables (i.e. column indices) $j\in J$
alpar@9: and numerical values of corresponding constraint coefficients $a_j$ must
alpar@9: be placed in locations \verb|ind[1]|, \dots, \verb|ind[len]| and
alpar@9: \verb|val[1]|, \dots, \verb|val[len]|, respectively, where
alpar@9: ${\tt len}=|J|$ is the number of constraint coefficients,
alpar@9: $0\leq{\tt len}\leq n$, and $n$ is the number of columns in the problem
alpar@9: object. Coefficients with identical column indices are not allowed.
alpar@9: Zero coefficients are allowed, however, they are ignored.
alpar@9: 
alpar@9: The parameter \verb|type| specifies the constraint type as follows:
alpar@9: 
alpar@9: \verb|GLP_LO| means inequality constraint $\Sigma a_jx_j\geq b$;
alpar@9: 
alpar@9: \verb|GLP_UP| means inequality constraint $\Sigma a_jx_j\leq b$;
alpar@9: 
alpar@9: The parameter \verb|rhs| specifies the right-hand side $b$.
alpar@9: 
alpar@9: All cutting plane constraints in the cut pool are identified by their
alpar@9: ordinal numbers 1, 2, \dots, $size$, where $size$ is the current size
alpar@9: of the cut pool. New constraints are always added to the end of the cut
alpar@9: pool, thus, ordinal numbers of previously added constraints are not
alpar@9: changed.
alpar@9: 
alpar@9: \subsubsection*{Returns}
alpar@9: 
alpar@9: The routine \verb|glp_ios_add_row| returns the ordinal number of the
alpar@9: cutting plane constraint added, which is the new size of the cut pool.
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: /* generate triangle cutting plane:
alpar@9:    x[i] + x[j] + x[k] <= 1 */
alpar@9: . . .
alpar@9: /* add the constraint to the cut pool */
alpar@9: ind[1] = i, val[1] = 1.0;
alpar@9: ind[2] = j, val[2] = 1.0;
alpar@9: ind[3] = k, val[3] = 1.0;
alpar@9: glp_ios_add_row(tree, NULL, TRIANGLE_CUT, 0, 3, ind, val,
alpar@9:                 GLP_UP, 1.0);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Comments}
alpar@9: 
alpar@9: Cutting plane constraints added to the cut pool are intended to be then
alpar@9: added only to the {\it current} subproblem, so these constraints can be
alpar@9: globally as well as locally valid. However, adding a constraint to the
alpar@9: cut pool does not mean that it will be added to the current
alpar@9: subproblem---it depends on the solver's decision: if the constraint
alpar@9: seems to be efficient, it is moved from the pool to the current
alpar@9: subproblem, otherwise it is simply dropped.\footnote{Globally valid
alpar@9: constraints could be saved and then re-used for other subproblems, but
alpar@9: currently such feature is not implemented.}
alpar@9: 
alpar@9: Normally, every time the callback routine is called for cut generation,
alpar@9: the cut pool is empty. On the other hand, the solver itself can generate
alpar@9: cutting plane constraints (like Gomory's or mixed integer rounding
alpar@9: cuts), in which case the cut pool may be non-empty.
alpar@9: 
alpar@9: \subsection{glp\_ios\_del\_row---remove constraint from the cut pool}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_ios_del_row(glp_tree *tree, int i);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_ios_del_row| deletes $i$-th row (cutting plane
alpar@9: constraint) from the cut pool, where $1\leq i\leq size$ is the ordinal
alpar@9: number of the constraint in the pool, $size$ is the current size of the
alpar@9: cut pool.
alpar@9: 
alpar@9: Note that deleting a constraint from the cut pool leads to changing
alpar@9: ordinal numbers of other constraints remaining in the pool. New ordinal
alpar@9: numbers of the remaining constraints are assigned under assumption that
alpar@9: the original order of constraints is not changed. Let, for example,
alpar@9: there be four constraints $a$, $b$, $c$ and $d$ in the cut pool, which
alpar@9: have ordinal numbers 1, 2, 3 and 4, respectively, and let constraint
alpar@9: $b$ have been deleted. Then after deletion the remaining constraint $a$,
alpar@9: $c$ and $d$ are assigned new ordinal numbers 1, 2 and 3, respectively.
alpar@9: 
alpar@9: To find the constraint to be deleted the routine \verb|glp_ios_del_row|
alpar@9: uses ``smart'' linear search, so it is recommended to remove constraints
alpar@9: in a natural or reverse order and avoid removing them in a random order.
alpar@9: 
alpar@9: \subsubsection*{Example}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: /* keep first 10 constraints in the cut pool and remove other
alpar@9:    constraints */
alpar@9: while (glp_ios_pool_size(tree) > 10)
alpar@9:    glp_ios_del_row(tree, glp_ios_pool_size(tree));
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \newpage
alpar@9: 
alpar@9: \subsection{glp\_ios\_clear\_pool---remove all constraints from the cut
alpar@9: pool}
alpar@9: 
alpar@9: \subsubsection*{Synopsis}
alpar@9: 
alpar@9: \begin{verbatim}
alpar@9: void glp_ios_clear_pool(glp_tree *tree);
alpar@9: \end{verbatim}
alpar@9: 
alpar@9: \subsubsection*{Description}
alpar@9: 
alpar@9: The routine \verb|glp_ios_clear_pool| makes the cut pool empty deleting
alpar@9: all existing rows (cutting plane constraints) from it.
alpar@9: 
alpar@9: %* eof *%