lemon-project-template-glpk
diff deps/glpk/doc/glpk05.tex @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
line diff
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 *%