[1] | 1 | %* glpk05.tex *% |
---|
| 2 | |
---|
| 3 | \chapter{Branch-and-Cut API Routines} |
---|
| 4 | |
---|
| 5 | \section{Introduction} |
---|
| 6 | |
---|
| 7 | \subsection{Using the callback routine} |
---|
| 8 | |
---|
| 9 | The GLPK MIP solver based on the branch-and-cut method allows the |
---|
| 10 | application program to control the solution process. This is attained |
---|
| 11 | by means of the user-defined callback routine, which is called by the |
---|
| 12 | solver at various points of the branch-and-cut algorithm. |
---|
| 13 | |
---|
| 14 | The callback routine passed to the MIP solver should be written by the |
---|
| 15 | user and has the following specification:\footnote{The name |
---|
| 16 | {\tt foo\_bar} used here is a placeholder for the callback routine |
---|
| 17 | name.} |
---|
| 18 | |
---|
| 19 | \begin{verbatim} |
---|
| 20 | void foo_bar(glp_tree *tree, void *info); |
---|
| 21 | \end{verbatim} |
---|
| 22 | |
---|
| 23 | \noindent |
---|
| 24 | where \verb|tree| is a pointer to the data structure \verb|glp_tree|, |
---|
| 25 | which should be used on subsequent calls to branch-and-cut interface |
---|
| 26 | routines, and \verb|info| is a transit pointer passed to the routine |
---|
| 27 | \verb|glp_intopt|, which may be used by the application program to pass |
---|
| 28 | some external data to the callback routine. |
---|
| 29 | |
---|
| 30 | The callback routine is passed to the MIP solver through the control |
---|
| 31 | parameter structure \verb|glp_iocp| (see Chapter ``Basic API Routines'', |
---|
| 32 | Section ``Mixed integer programming routines'', Subsection ``Solve MIP |
---|
| 33 | problem with the branch-and-cut method'') as follows: |
---|
| 34 | |
---|
| 35 | \newpage |
---|
| 36 | |
---|
| 37 | \begin{verbatim} |
---|
| 38 | glp_prob *mip; |
---|
| 39 | glp_iocp parm; |
---|
| 40 | . . . |
---|
| 41 | glp_init_iocp(&parm); |
---|
| 42 | . . . |
---|
| 43 | parm.cb_func = foo_bar; |
---|
| 44 | parm.cb_info = ... ; |
---|
| 45 | ret = glp_intopt(mip, &parm); |
---|
| 46 | . . . |
---|
| 47 | \end{verbatim} |
---|
| 48 | |
---|
| 49 | To determine why it is being called by the MIP solver the callback |
---|
| 50 | routine should use the routine \verb|glp_ios_reason| (described in this |
---|
| 51 | section below), which returns a code indicating the reason for calling. |
---|
| 52 | Depending on the reason the callback routine may perform necessary |
---|
| 53 | actions to control the solution process. |
---|
| 54 | |
---|
| 55 | The reason codes, which correspond to various point of the |
---|
| 56 | branch-and-cut algorithm implemented in the MIP solver, are described |
---|
| 57 | in Subsection ``Reasons for calling the callback routine'' below. |
---|
| 58 | |
---|
| 59 | To ignore calls for reasons, which are not processed by the callback |
---|
| 60 | routine, it should just return to the MIP solver doing nothing. For |
---|
| 61 | example: |
---|
| 62 | |
---|
| 63 | \begin{verbatim} |
---|
| 64 | void foo_bar(glp_tree *tree, void *info) |
---|
| 65 | { . . . |
---|
| 66 | switch (glp_ios_reason(tree)) |
---|
| 67 | { case GLP_IBRANCH: |
---|
| 68 | . . . |
---|
| 69 | break; |
---|
| 70 | case GLP_ISELECT: |
---|
| 71 | . . . |
---|
| 72 | break; |
---|
| 73 | default: |
---|
| 74 | /* ignore call for other reasons */ |
---|
| 75 | break; |
---|
| 76 | } |
---|
| 77 | return; |
---|
| 78 | } |
---|
| 79 | \end{verbatim} |
---|
| 80 | |
---|
| 81 | To control the solution process as well as to obtain necessary |
---|
| 82 | information the callback routine may use the branch-and-cut API |
---|
| 83 | routines described in this chapter. Names of all these routines begin |
---|
| 84 | with `\verb|glp_ios_|'. |
---|
| 85 | |
---|
| 86 | \subsection{Branch-and-cut algorithm} |
---|
| 87 | |
---|
| 88 | This section gives a schematic description of the branch-and-cut |
---|
| 89 | algorithm as it is implemented in the GLPK MIP solver. |
---|
| 90 | |
---|
| 91 | \medskip |
---|
| 92 | |
---|
| 93 | {\it 1. Initialization} |
---|
| 94 | |
---|
| 95 | Set $L:=\{P_0\}$, where $L$ is the {\it active list} (i.e. the list of |
---|
| 96 | active subproblems), $P_0$ is the original MIP problem to be solved. |
---|
| 97 | |
---|
| 98 | Set $z^{\it best}:=+\infty$ (in case of minimization) or |
---|
| 99 | $z^{\it best}:=-\infty$ (in case of maximization), where $z^{\it best}$ |
---|
| 100 | is {\it incumbent value}, i.e. an upper (minimization) or lower |
---|
| 101 | (maximization) global bound for $z^{\it opt}$, the optimal objective |
---|
| 102 | value for $P^0$. |
---|
| 103 | |
---|
| 104 | \medskip |
---|
| 105 | |
---|
| 106 | {\it 2. Subproblem selection} |
---|
| 107 | |
---|
| 108 | If $L=\varnothing$ then GO TO 9. |
---|
| 109 | |
---|
| 110 | Select $P\in L$, i.e. make active subproblem $P$ current. |
---|
| 111 | |
---|
| 112 | \medskip |
---|
| 113 | |
---|
| 114 | {\it 3. Solving LP relaxation} |
---|
| 115 | |
---|
| 116 | Solve $P^{\it LP}$, which is LP relaxation of $P$. |
---|
| 117 | |
---|
| 118 | If $P^{\it LP}$ has no primal feasible solution then GO TO 8. |
---|
| 119 | |
---|
| 120 | Let $z^{\it LP}$ be the optimal objective value for $P^{\it LP}$. |
---|
| 121 | |
---|
| 122 | If $z^{\it LP}\geq z^{\it best}$ (in case of minimization) or |
---|
| 123 | $z^{\it LP}\leq z^{\rm best}$ (in case of maximization) then GO TO 8. |
---|
| 124 | |
---|
| 125 | \medskip |
---|
| 126 | |
---|
| 127 | {\it 4. Adding ``lazy'' constraints} |
---|
| 128 | |
---|
| 129 | Let $x^{\it LP}$ be the optimal solution to $P^{\it LP}$. |
---|
| 130 | |
---|
| 131 | If there are ``lazy'' constraints (i.e. essential constraints not |
---|
| 132 | included in the original MIP problem $P_0$), which are violated at the |
---|
| 133 | optimal point $x^{\it LP}$, add them to $P$, and GO TO 3. |
---|
| 134 | |
---|
| 135 | \medskip |
---|
| 136 | |
---|
| 137 | {\it 5. Check for integrality} |
---|
| 138 | |
---|
| 139 | Let $x_j$ be a variable, which is required to be integer, and let |
---|
| 140 | $x^{\it LP}_j\in x^{\it LP}$ be its value in the optimal solution to |
---|
| 141 | $P^{\it LP}$. |
---|
| 142 | |
---|
| 143 | If $x^{\it LP}_j$ are integral for all integer variables, then a better |
---|
| 144 | integer feasible solution is found. Store its components, set |
---|
| 145 | $z^{\it best}:=z^{\it LP}$, and GO TO 8. |
---|
| 146 | |
---|
| 147 | \medskip |
---|
| 148 | |
---|
| 149 | {\it 6. Adding cutting planes} |
---|
| 150 | |
---|
| 151 | If there are cutting planes (i.e. valid constraints for $P$), |
---|
| 152 | which are violated at the optimal point $x^{\it LP}$, add them to $P$, |
---|
| 153 | and GO TO 3. |
---|
| 154 | |
---|
| 155 | \medskip |
---|
| 156 | |
---|
| 157 | {\it 7. Branching} |
---|
| 158 | |
---|
| 159 | Select {\it branching variable} $x_j$, i.e. a variable, which is |
---|
| 160 | required to be integer, and whose value $x^{\it LP}_j\in x^{\it LP}$ is |
---|
| 161 | fractional in the optimal solution to $P^{\it LP}$. |
---|
| 162 | |
---|
| 163 | Create new subproblem $P^D$ (so called {\it down branch}), which is |
---|
| 164 | identical to the current subproblem $P$ with exception that the upper |
---|
| 165 | bound of $x_j$ is replaced by $\lfloor x^{\it LP}_j\rfloor$. (For |
---|
| 166 | example, if $x^{\it LP}_j=3.14$, the new upper bound of $x_j$ in the |
---|
| 167 | down branch will be $\lfloor 3.14\rfloor=3$.) |
---|
| 168 | |
---|
| 169 | Create new subproblem $P^U$ (so called {\it up branch}), which is |
---|
| 170 | identical to the current subproblem $P$ with exception that the lower |
---|
| 171 | bound of $x_j$ is replaced by $\lceil x^{\it LP}_j\rceil$. (For example, |
---|
| 172 | if $x^{\it LP}_j=3.14$, the new lower bound of $x_j$ in the up branch |
---|
| 173 | will be $\lceil 3.14\rceil=4$.) |
---|
| 174 | |
---|
| 175 | Set $L:=(L\backslash\{P\})\cup\{P^D,P^U\}$, i.e. remove the current |
---|
| 176 | subproblem $P$ from the active list $L$ and add two new subproblems |
---|
| 177 | $P^D$ and $P^U$ to it. Then GO TO 2. |
---|
| 178 | |
---|
| 179 | \medskip |
---|
| 180 | |
---|
| 181 | {\it 8. Pruning} |
---|
| 182 | |
---|
| 183 | Remove from the active list $L$ all subproblems (including the current |
---|
| 184 | one), whose local bound $\widetilde{z}$ is not better than the global |
---|
| 185 | bound $z^{\it best}$, i.e. set $L:=L\backslash\{P\}$ for all $P$, where |
---|
| 186 | $\widetilde{z}\geq z^{\it best}$ (in case of minimization) or |
---|
| 187 | $\widetilde{z}\leq z^{\it best}$ (in case of maximization), and then |
---|
| 188 | GO TO 2. |
---|
| 189 | |
---|
| 190 | The local bound $\widetilde{z}$ for subproblem $P$ is an lower |
---|
| 191 | (minimization) or upper (maximization) bound for integer optimal |
---|
| 192 | solution to {\it this} subproblem (not to the original problem). This |
---|
| 193 | bound is local in the sense that only subproblems in the subtree rooted |
---|
| 194 | at node $P$ cannot have better integer feasible solutions. Note that |
---|
| 195 | the local bound is not necessarily the optimal objective value to LP |
---|
| 196 | relaxation $P^{\it LP}$. |
---|
| 197 | |
---|
| 198 | \medskip |
---|
| 199 | |
---|
| 200 | {\it 9. Termination} |
---|
| 201 | |
---|
| 202 | If $z^{\it best}=+\infty$ (in case of minimization) or |
---|
| 203 | $z^{\it best}=-\infty$ (in case of maximization), the original problem |
---|
| 204 | $P_0$ has no integer feasible solution. Otherwise, the last integer |
---|
| 205 | feasible solution stored on step 5 is the integer optimal solution to |
---|
| 206 | the original problem $P_0$ with $z^{\it opt}=z^{\it best}$. STOP. |
---|
| 207 | |
---|
| 208 | \subsection{The search tree} |
---|
| 209 | |
---|
| 210 | On the branching step of the branch-and-cut algorithm the current |
---|
| 211 | subproblem is divided into two\footnote{In more general cases the |
---|
| 212 | current subproblem may be divided into more than two subproblems. |
---|
| 213 | However, currently such feature is not used in GLPK.} new subproblems, |
---|
| 214 | so the set of all subproblems can be represented in the form of a rooted |
---|
| 215 | tree, which is called the {\it search} or {\it branch-and-bound} tree. |
---|
| 216 | An example of the search tree is shown on Fig.~1. Each node of the |
---|
| 217 | search tree corresponds to a subproblem, so the terms `node' and |
---|
| 218 | `subproblem' may be used synonymously. |
---|
| 219 | |
---|
| 220 | \newpage |
---|
| 221 | |
---|
| 222 | \begin{figure}[t] |
---|
| 223 | \noindent\hfil |
---|
| 224 | \xymatrix @R=20pt @C=10pt |
---|
| 225 | {&&&&&&*+<14pt>[o][F=]{A}\ar@{-}[dllll]\ar@{-}[dr]\ar@{-}[drrrr]&&&&\\ |
---|
| 226 | &&*+<14pt>[o][F=]{B}\ar@{-}[dl]\ar@{-}[dr]&&&&&*+<14pt>[o][F=]{C} |
---|
| 227 | \ar@{-}[dll]\ar@{-}[dr]\ar@{-}[drrr]&&&*+<14pt>[o][F-]{\times}\\ |
---|
| 228 | &*+<14pt>[o][F-]{\times}\ar@{-}[dl]\ar@{-}[d]\ar@{-}[dr]&& |
---|
| 229 | *+<14pt>[o][F-]{D}&&*+<14pt>[o][F=]{E}\ar@{-}[dl]\ar@{-}[dr]&&& |
---|
| 230 | *+<14pt>[o][F=]{F}\ar@{-}[dl]\ar@{-}[dr]&&*+<14pt>[o][F-]{G}\\ |
---|
| 231 | *+<14pt>[o][F-]{\times}&*+<14pt>[o][F-]{\times}&*+<14pt>[o][F-]{\times} |
---|
| 232 | &&*+<14pt>[][F-]{H}&&*+<14pt>[o][F-]{I}&*+<14pt>[o][F-]{\times}&& |
---|
| 233 | *+<14pt>[o][F-]{J}&\\} |
---|
| 234 | |
---|
| 235 | \bigskip |
---|
| 236 | |
---|
| 237 | \noindent\hspace{.8in} |
---|
| 238 | \xymatrix @R=11pt |
---|
| 239 | {*+<20pt>[][F-]{}&*\txt{\makebox[1in][l]{Current}}&& |
---|
| 240 | *+<20pt>[o][F-]{}&*\txt{\makebox[1in][l]{Active}}\\ |
---|
| 241 | *+<20pt>[o][F=]{}&*\txt{\makebox[1in][l]{Non-active}}&& |
---|
| 242 | *+<14pt>[o][F-]{\times}&*\txt{\makebox[1in][l]{Fathomed}}\\ |
---|
| 243 | } |
---|
| 244 | |
---|
| 245 | \begin{center} |
---|
| 246 | Fig. 1. An example of the search tree. |
---|
| 247 | \end{center} |
---|
| 248 | \end{figure} |
---|
| 249 | |
---|
| 250 | In GLPK each node may have one of the following four statuses: |
---|
| 251 | |
---|
| 252 | $\bullet$ {\it current node} is the active node currently being |
---|
| 253 | processed; |
---|
| 254 | |
---|
| 255 | $\bullet$ {\it active node} is a leaf node, which still has to be |
---|
| 256 | processed; |
---|
| 257 | |
---|
| 258 | $\bullet$ {\it non-active node} is a node, which has been processed, |
---|
| 259 | but not fathomed; |
---|
| 260 | |
---|
| 261 | $\bullet$ {\it fathomed node} is a node, which has been processed and |
---|
| 262 | fathomed. |
---|
| 263 | |
---|
| 264 | In the data structure representing the search tree GLPK keeps only |
---|
| 265 | current, active, and non-active nodes. Once a node has been fathomed, |
---|
| 266 | it is removed from the tree data structure. |
---|
| 267 | |
---|
| 268 | Being created each node of the search tree is assigned a distinct |
---|
| 269 | positive integer called the {\it subproblem reference number}, which |
---|
| 270 | may be used by the application program to specify a particular node of |
---|
| 271 | the tree. The root node corresponding to the original problem to be |
---|
| 272 | solved is always assigned the reference number 1. |
---|
| 273 | |
---|
| 274 | \subsection{Current subproblem} |
---|
| 275 | |
---|
| 276 | The current subproblem is a MIP problem corresponding to the current |
---|
| 277 | node of the search tree. It is represented as the GLPK problem object |
---|
| 278 | (\verb|glp_prob|) that allows the application program using API routines |
---|
| 279 | to access its content in the standard way. If the MIP presolver is not |
---|
| 280 | used, it is the original problem object passed to the routine |
---|
| 281 | \verb|glp_intopt|; otherwise, it is an internal problem object built by |
---|
| 282 | the MIP presolver. |
---|
| 283 | |
---|
| 284 | Note that the problem object is used by the MIP solver itself during |
---|
| 285 | the solution process for various purposes (to solve LP relaxations, to |
---|
| 286 | perfom branching, etc.), and even if the MIP presolver is not used, the |
---|
| 287 | current content of the problem object may differ from its original |
---|
| 288 | content. For example, it may have additional rows, bounds of some rows |
---|
| 289 | and columns may be changed, etc. In particular, LP segment of the |
---|
| 290 | problem object corresponds to LP relaxation of the current subproblem. |
---|
| 291 | However, on exit from the MIP solver the content of the problem object |
---|
| 292 | is restored to its original state. |
---|
| 293 | |
---|
| 294 | To obtain information from the problem object the application program |
---|
| 295 | may use any API routines, which do not change the object. Using API |
---|
| 296 | routines, which change the problem object, is restricted to stipulated |
---|
| 297 | cases. |
---|
| 298 | |
---|
| 299 | \subsection{The cut pool} |
---|
| 300 | |
---|
| 301 | The {\it cut pool} is a set of cutting plane constraints maintained by |
---|
| 302 | the MIP solver. It is used by the GLPK cut generation routines and may |
---|
| 303 | be used by the application program in the same way, i.e. rather than |
---|
| 304 | to add cutting plane constraints directly to the problem object the |
---|
| 305 | application program may store them to the cut pool. In the latter case |
---|
| 306 | the solver looks through the cut pool, selects efficient constraints, |
---|
| 307 | and adds them to the problem object. |
---|
| 308 | |
---|
| 309 | \subsection{Reasons for calling the callback routine} |
---|
| 310 | |
---|
| 311 | The callback routine may be called by the MIP solver for the following |
---|
| 312 | reasons. |
---|
| 313 | |
---|
| 314 | \subsubsection*{Request for subproblem selection} |
---|
| 315 | |
---|
| 316 | The callback routine is called with the reason code \verb|GLP_ISELECT| |
---|
| 317 | if the current subproblem has been fathomed and therefore there is no |
---|
| 318 | current subproblem. |
---|
| 319 | |
---|
| 320 | In response the callback routine may select some subproblem from the |
---|
| 321 | active list and pass its reference number to the solver using the |
---|
| 322 | routine \verb|glp_ios_select_node|, in which case the solver continues |
---|
| 323 | the search from the specified active subproblem. If no selection is made |
---|
| 324 | by the callback routine, the solver uses a backtracking technique |
---|
| 325 | specified by the control parameter \verb|bt_tech|. |
---|
| 326 | |
---|
| 327 | To explore the active list (i.e. active nodes of the branch-and-bound |
---|
| 328 | tree) the callback routine may use the routines \verb|glp_ios_next_node| |
---|
| 329 | and \verb|glp_ios_prev_node|. |
---|
| 330 | |
---|
| 331 | \subsubsection*{Request for preprocessing} |
---|
| 332 | |
---|
| 333 | The callback routine is called with the reason code \verb|GLP_IPREPRO| |
---|
| 334 | if the current subproblem has just been selected from the active list |
---|
| 335 | and its LP relaxation is not solved yet. |
---|
| 336 | |
---|
| 337 | In response the callback routine may perform some preprocessing of the |
---|
| 338 | current subproblem like tightening bounds of some variables or removing |
---|
| 339 | bounds of some redundant constraints. |
---|
| 340 | |
---|
| 341 | \subsubsection*{Request for row generation} |
---|
| 342 | |
---|
| 343 | The callback routine is called with the reason code \verb|GLP_IROWGEN| |
---|
| 344 | if LP relaxation of the current subproblem has just been solved to |
---|
| 345 | optimality and its objective value is better than the best known integer |
---|
| 346 | feasible solution. |
---|
| 347 | |
---|
| 348 | In response the callback routine may add one or more ``lazy'' |
---|
| 349 | constraints (rows), which are violated by the current optimal solution |
---|
| 350 | of LP relaxation, using API routines \verb|glp_add_rows|, |
---|
| 351 | \verb|glp_set_row_name|, \verb|glp_set_row_bnds|, and |
---|
| 352 | \verb|glp_set_mat_row|, in which case the solver will perform |
---|
| 353 | re-optimization of LP relaxation. If there are no violated constraints, |
---|
| 354 | the callback routine should just return. |
---|
| 355 | |
---|
| 356 | Optimal solution components for LP relaxation can be obtained with API |
---|
| 357 | routines \verb|glp_get_obj_val|, \verb|glp_get_row_prim|, |
---|
| 358 | \verb|glp_get_row_dual|, \verb|glp_get_col_prim|, and |
---|
| 359 | \verb|glp_get_col_dual|. |
---|
| 360 | |
---|
| 361 | \subsubsection*{Request for heuristic solution} |
---|
| 362 | |
---|
| 363 | The callback routine is called with the reason code \verb|GLP_IHEUR| |
---|
| 364 | if LP relaxation of the current subproblem being solved to optimality |
---|
| 365 | is integer infeasible (i.e. values of some structural variables of |
---|
| 366 | integer kind are fractional), though its objective value is better than |
---|
| 367 | the best known integer feasible solution. |
---|
| 368 | |
---|
| 369 | In response the callback routine may try applying a primal heuristic |
---|
| 370 | to find an integer feasible solution,\footnote{Integer feasible to the |
---|
| 371 | original MIP problem, not to the current subproblem.} which is better |
---|
| 372 | than the best known one. In case of success the callback routine may |
---|
| 373 | store such better solution in the problem object using the routine |
---|
| 374 | \verb|glp_ios_heur_sol|. |
---|
| 375 | |
---|
| 376 | \subsubsection*{Request for cut generation} |
---|
| 377 | |
---|
| 378 | The callback routine is called with the reason code \verb|GLP_ICUTGEN| |
---|
| 379 | if LP relaxation of the current subproblem being solved to optimality |
---|
| 380 | is integer infeasible (i.e. values of some structural variables of |
---|
| 381 | integer kind are fractional), though its objective value is better than |
---|
| 382 | the best known integer feasible solution. |
---|
| 383 | |
---|
| 384 | In response the callback routine may reformulate the {\it current} |
---|
| 385 | subproblem (before it will be splitted up due to branching) by adding to |
---|
| 386 | the problem object one or more {\it cutting plane constraints}, which |
---|
| 387 | cut off the fractional optimal point from the MIP |
---|
| 388 | polytope.\footnote{Since these constraints are added to the current |
---|
| 389 | subproblem, they may be globally as well as locally valid.} |
---|
| 390 | |
---|
| 391 | Adding cutting plane constraints may be performed in two ways. |
---|
| 392 | One way is the same as for the reason code \verb|GLP_IROWGEN| (see |
---|
| 393 | above), in which case the callback routine adds new rows corresponding |
---|
| 394 | to cutting plane constraints directly to the current subproblem. |
---|
| 395 | |
---|
| 396 | The other way is to add cutting plane constraints to the {\it cut pool}, |
---|
| 397 | a set of cutting plane constraints maintained by the solver, rather than |
---|
| 398 | directly to the current subproblem. In this case after return from the |
---|
| 399 | callback routine the solver looks through the cut pool, selects |
---|
| 400 | efficient cutting plane constraints, adds them to the current |
---|
| 401 | subproblem, drops other constraints, and then performs re-optimization. |
---|
| 402 | |
---|
| 403 | \subsubsection*{Request for branching} |
---|
| 404 | |
---|
| 405 | The callback routine is called with the reason code \verb|GLP_IBRANCH| |
---|
| 406 | if LP relaxation of the current subproblem being solved to optimality |
---|
| 407 | is integer infeasible (i.e. values of some structural variables of |
---|
| 408 | integer kind are fractional), though its objective value is better than |
---|
| 409 | the best known integer feasible solution. |
---|
| 410 | |
---|
| 411 | In response the callback routine may choose some variable suitable for |
---|
| 412 | branching (i.e. integer variable, whose value in optimal solution to |
---|
| 413 | LP relaxation of the current subproblem is fractional) and pass its |
---|
| 414 | ordinal number to the solver using the routine |
---|
| 415 | \verb|glp_ios_branch_upon|, in which case the solver splits the current |
---|
| 416 | subproblem in two new subproblems and continues the search. If no choice |
---|
| 417 | is made by the callback routine, the solver uses a branching technique |
---|
| 418 | specified by the control parameter \verb|br_tech|. |
---|
| 419 | |
---|
| 420 | \subsubsection*{Better integer solution found} |
---|
| 421 | |
---|
| 422 | The callback routine is called with the reason code \verb|GLP_IBINGO| |
---|
| 423 | if LP relaxation of the current subproblem being solved to optimality |
---|
| 424 | is integer feasible (i.e. values of all structural variables of integer |
---|
| 425 | kind are integral within the working precision) and its objective value |
---|
| 426 | is better than the best known integer feasible solution. |
---|
| 427 | |
---|
| 428 | Optimal solution components for LP relaxation can be obtained in the |
---|
| 429 | same way as for the reason code \verb|GLP_IROWGEN| (see above). |
---|
| 430 | |
---|
| 431 | Components of the new MIP solution can be obtained with API routines |
---|
| 432 | \verb|glp_mip_obj_val|, \verb|glp_mip_row_val|, and |
---|
| 433 | \verb|glp_mip_col_val|. Note, however, that due to row/cut generation |
---|
| 434 | there may be additional rows in the problem object. |
---|
| 435 | |
---|
| 436 | The difference between optimal solution to LP relaxation and |
---|
| 437 | corresponding MIP solution is that in the former case some structural |
---|
| 438 | variables of integer kind (namely, basic variables) may have values, |
---|
| 439 | which are close to nearest integers within the working precision, while |
---|
| 440 | in the latter case all such variables have exact integral values. |
---|
| 441 | |
---|
| 442 | The reason \verb|GLP_IBINGO| is intended only for informational |
---|
| 443 | purposes, so the callback routine should not modify the problem object |
---|
| 444 | in this case. |
---|
| 445 | |
---|
| 446 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 447 | |
---|
| 448 | \newpage |
---|
| 449 | |
---|
| 450 | \section{Basic routines} |
---|
| 451 | |
---|
| 452 | \subsection{glp\_ios\_reason---determine reason for calling the |
---|
| 453 | callback routine} |
---|
| 454 | |
---|
| 455 | \subsubsection*{Synopsis} |
---|
| 456 | |
---|
| 457 | \begin{verbatim} |
---|
| 458 | int glp_ios_reason(glp_tree *tree); |
---|
| 459 | \end{verbatim} |
---|
| 460 | |
---|
| 461 | \subsubsection*{Returns} |
---|
| 462 | |
---|
| 463 | The routine \verb|glp_ios_reason| returns a code, which indicates why |
---|
| 464 | the user-defined callback routine is being called: |
---|
| 465 | |
---|
| 466 | \verb|GLP_ISELECT|---request for subproblem selection; |
---|
| 467 | |
---|
| 468 | \verb|GLP_IPREPRO|---request for preprocessing; |
---|
| 469 | |
---|
| 470 | \verb|GLP_IROWGEN|---request for row generation; |
---|
| 471 | |
---|
| 472 | \verb|GLP_IHEUR |---request for heuristic solution; |
---|
| 473 | |
---|
| 474 | \verb|GLP_ICUTGEN|---request for cut generation; |
---|
| 475 | |
---|
| 476 | \verb|GLP_IBRANCH|---request for branching; |
---|
| 477 | |
---|
| 478 | \verb|GLP_IBINGO |---better integer solution found. |
---|
| 479 | |
---|
| 480 | \subsection{glp\_ios\_get\_prob---access the problem object} |
---|
| 481 | |
---|
| 482 | \subsubsection*{Synopsis} |
---|
| 483 | |
---|
| 484 | \begin{verbatim} |
---|
| 485 | glp_prob *glp_ios_get_prob(glp_tree *tree); |
---|
| 486 | \end{verbatim} |
---|
| 487 | |
---|
| 488 | \subsubsection*{Description} |
---|
| 489 | |
---|
| 490 | The routine \verb|glp_ios_get_prob| can be called from the user-defined |
---|
| 491 | callback routine to access the problem object, which is used by the MIP |
---|
| 492 | solver. It is the original problem object passed to the routine |
---|
| 493 | \verb|glp_intopt| if the MIP presolver is not used; otherwise it is an |
---|
| 494 | internal problem object built by the presolver. |
---|
| 495 | |
---|
| 496 | \subsubsection*{Returns} |
---|
| 497 | |
---|
| 498 | The routine \verb|glp_ios_get_prob| returns a pointer to the problem |
---|
| 499 | object used by the MIP solver. |
---|
| 500 | |
---|
| 501 | \subsubsection*{Comments} |
---|
| 502 | |
---|
| 503 | To obtain various information about the problem instance the callback |
---|
| 504 | routine can access the problem object (i.e. the object of type |
---|
| 505 | \verb|glp_prob|) using the routine \verb|glp_ios_get_prob|. It is the |
---|
| 506 | original problem object passed to the routine \verb|glp_intopt| if the |
---|
| 507 | MIP presolver is not used; otherwise it is an internal problem object |
---|
| 508 | built by the presolver. |
---|
| 509 | |
---|
| 510 | \subsection{glp\_ios\_row\_attr---determine additional row attributes} |
---|
| 511 | |
---|
| 512 | \subsubsection*{Synopsis} |
---|
| 513 | |
---|
| 514 | \begin{verbatim} |
---|
| 515 | void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr); |
---|
| 516 | \end{verbatim} |
---|
| 517 | |
---|
| 518 | \subsubsection*{Description} |
---|
| 519 | |
---|
| 520 | The routine \verb|glp_ios_row_attr| retrieves additional attributes of |
---|
| 521 | $i$-th row of the current subproblem and stores them in the structure |
---|
| 522 | \verb|glp_attr|, which the parameter \verb|attr| points to. |
---|
| 523 | |
---|
| 524 | The structure \verb|glp_attr| has the following fields: |
---|
| 525 | |
---|
| 526 | \medskip |
---|
| 527 | |
---|
| 528 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 529 | \multicolumn{2}{@{}l}{{\tt int level}}\\ |
---|
| 530 | &Subproblem level at which the row was created. (If \verb|level| = 0, |
---|
| 531 | the row was added either to the original problem object passed to the |
---|
| 532 | routine \verb|glp_intopt| or to the root subproblem on generating |
---|
| 533 | ``lazy'' or/and cutting plane constraints.)\\ |
---|
| 534 | \end{tabular} |
---|
| 535 | |
---|
| 536 | \medskip |
---|
| 537 | |
---|
| 538 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 539 | \multicolumn{2}{@{}l}{{\tt int origin}}\\ |
---|
| 540 | &The row origin flag:\\ |
---|
| 541 | &\verb|GLP_RF_REG |---regular constraint;\\ |
---|
| 542 | &\verb|GLP_RF_LAZY|---``lazy'' constraint;\\ |
---|
| 543 | &\verb|GLP_RF_CUT |---cutting plane constraint.\\ |
---|
| 544 | \end{tabular} |
---|
| 545 | |
---|
| 546 | \medskip |
---|
| 547 | |
---|
| 548 | \noindent\begin{tabular}{@{}p{17pt}@{}p{120.5mm}@{}} |
---|
| 549 | \multicolumn{2}{@{}l}{{\tt int klass}}\\ |
---|
| 550 | &The row class descriptor, which is a number passed to the routine |
---|
| 551 | \verb|glp_ios_add_row| as its third parameter. If the row is a cutting |
---|
| 552 | plane constraint generated by the solver, its class may be the |
---|
| 553 | following:\\ |
---|
| 554 | &\verb|GLP_RF_GMI |---Gomory's mixed integer cut;\\ |
---|
| 555 | &\verb|GLP_RF_MIR |---mixed integer rounding cut;\\ |
---|
| 556 | &\verb|GLP_RF_COV |---mixed cover cut;\\ |
---|
| 557 | &\verb|GLP_RF_CLQ |---clique cut.\\ |
---|
| 558 | \end{tabular} |
---|
| 559 | |
---|
| 560 | \newpage |
---|
| 561 | |
---|
| 562 | \subsection{glp\_ios\_mip\_gap---compute relative MIP gap} |
---|
| 563 | |
---|
| 564 | \subsubsection*{Synopsis} |
---|
| 565 | |
---|
| 566 | \begin{verbatim} |
---|
| 567 | double glp_ios_mip_gap(glp_tree *tree); |
---|
| 568 | \end{verbatim} |
---|
| 569 | |
---|
| 570 | \subsubsection*{Description} |
---|
| 571 | |
---|
| 572 | The routine \verb|glp_ios_mip_gap| computes the relative MIP gap (also |
---|
| 573 | called {\it duality gap}) with the following formula: |
---|
| 574 | $${\tt gap} = \frac{|{\tt best\_mip} - {\tt best\_bnd}|} |
---|
| 575 | {|{\tt best\_mip}| + {\tt DBL\_EPSILON}}$$ |
---|
| 576 | where \verb|best_mip| is the best integer feasible solution found so |
---|
| 577 | far, \verb|best_bnd| is the best (global) bound. If no integer feasible |
---|
| 578 | solution has been found yet, \verb|gap| is set to \verb|DBL_MAX|. |
---|
| 579 | |
---|
| 580 | \subsubsection*{Returns} |
---|
| 581 | |
---|
| 582 | The routine \verb|glp_ios_mip_gap| returns the relative MIP gap. |
---|
| 583 | |
---|
| 584 | \subsubsection*{Comments} |
---|
| 585 | |
---|
| 586 | The relative MIP gap is used to measure the quality of the best integer |
---|
| 587 | feasible solution found so far, because the optimal solution value |
---|
| 588 | $z^*$ for the original MIP problem always lies in the range |
---|
| 589 | $${\tt best\_bnd}\leq z^*\leq{\tt best\_mip}$$ |
---|
| 590 | in case of minimization, or in the range |
---|
| 591 | $${\tt best\_mip}\leq z^*\leq{\tt best\_bnd}$$ |
---|
| 592 | in case of maximization. |
---|
| 593 | |
---|
| 594 | To express the relative MIP gap in percents the value returned by the |
---|
| 595 | routine \verb|glp_ios_mip_gap| should be multiplied by 100\%. |
---|
| 596 | |
---|
| 597 | \newpage |
---|
| 598 | |
---|
| 599 | \subsection{glp\_ios\_node\_data---access application-specific data} |
---|
| 600 | |
---|
| 601 | \subsubsection*{Synopsis} |
---|
| 602 | |
---|
| 603 | \begin{verbatim} |
---|
| 604 | void *glp_ios_node_data(glp_tree *tree, int p); |
---|
| 605 | \end{verbatim} |
---|
| 606 | |
---|
| 607 | \subsubsection*{Description} |
---|
| 608 | |
---|
| 609 | The routine \verb|glp_ios_node_data| allows the application accessing a |
---|
| 610 | memory block allocated for the subproblem (which may be active or |
---|
| 611 | inactive), whose reference number is $p$. |
---|
| 612 | |
---|
| 613 | The size of the block is defined by the control parameter \verb|cb_size| |
---|
| 614 | passed to the routine \verb|glp_intopt|. The block is initialized by |
---|
| 615 | binary zeros on creating corresponding subproblem, and its contents is |
---|
| 616 | kept until the subproblem will be removed from the tree. |
---|
| 617 | |
---|
| 618 | The application may use these memory blocks to store specific data for |
---|
| 619 | each subproblem. |
---|
| 620 | |
---|
| 621 | \subsubsection*{Returns} |
---|
| 622 | |
---|
| 623 | The routine \verb|glp_ios_node_data| returns a pointer to the memory |
---|
| 624 | block for the specified subproblem. Note that if \verb|cb_size| = 0, the |
---|
| 625 | routine returns a null pointer. |
---|
| 626 | |
---|
| 627 | \subsection{glp\_ios\_select\_node---select subproblem to continue the |
---|
| 628 | search} |
---|
| 629 | |
---|
| 630 | \subsubsection*{Synopsis} |
---|
| 631 | |
---|
| 632 | \begin{verbatim} |
---|
| 633 | void glp_ios_select_node(glp_tree *tree, int p); |
---|
| 634 | \end{verbatim} |
---|
| 635 | |
---|
| 636 | \subsubsection*{Description} |
---|
| 637 | |
---|
| 638 | The routine \verb|glp_ios_select_node| can be called from the |
---|
| 639 | user-defined callback routine in response to the reason |
---|
| 640 | \verb|GLP_ISELECT| to select an active subproblem, whose reference |
---|
| 641 | number is $p$. The search will be continued from the subproblem |
---|
| 642 | selected. |
---|
| 643 | |
---|
| 644 | \newpage |
---|
| 645 | |
---|
| 646 | \subsection{glp\_ios\_heur\_sol---provide solution found by heuristic} |
---|
| 647 | |
---|
| 648 | \subsubsection*{Synopsis} |
---|
| 649 | |
---|
| 650 | \begin{verbatim} |
---|
| 651 | int glp_ios_heur_sol(glp_tree *tree, const double x[]); |
---|
| 652 | \end{verbatim} |
---|
| 653 | |
---|
| 654 | \subsubsection*{Description} |
---|
| 655 | |
---|
| 656 | The routine \verb|glp_ios_heur_sol| can be called from the user-defined |
---|
| 657 | callback routine in response to the reason \verb|GLP_IHEUR| to provide |
---|
| 658 | an integer feasible solution found by a primal heuristic. |
---|
| 659 | |
---|
| 660 | Primal values of {\it all} variables (columns) found by the heuristic |
---|
| 661 | should be placed in locations $x[1]$, \dots, $x[n]$, where $n$ is the |
---|
| 662 | number of columns in the original problem object. Note that the routine |
---|
| 663 | \verb|glp_ios_heur_sol| does {\it not} check primal feasibility of the |
---|
| 664 | solution provided. |
---|
| 665 | |
---|
| 666 | Using the solution passed in the array $x$ the routine computes value |
---|
| 667 | of the objective function. If the objective value is better than the |
---|
| 668 | best known integer feasible solution, the routine computes values of |
---|
| 669 | auxiliary variables (rows) and stores all solution components in the |
---|
| 670 | problem object. |
---|
| 671 | |
---|
| 672 | \subsubsection*{Returns} |
---|
| 673 | |
---|
| 674 | If the provided solution is accepted, the routine |
---|
| 675 | \verb|glp_ios_heur_sol| returns zero. Otherwise, if the provided |
---|
| 676 | solution is rejected, the routine returns non-zero. |
---|
| 677 | |
---|
| 678 | \subsection{glp\_ios\_can\_branch---check if can branch upon specified |
---|
| 679 | variable} |
---|
| 680 | |
---|
| 681 | \subsubsection*{Synopsis} |
---|
| 682 | |
---|
| 683 | \begin{verbatim} |
---|
| 684 | int glp_ios_can_branch(glp_tree *tree, int j); |
---|
| 685 | \end{verbatim} |
---|
| 686 | |
---|
| 687 | \subsubsection*{Returns} |
---|
| 688 | |
---|
| 689 | If $j$-th variable (column) can be used to branch upon, the routine |
---|
| 690 | returns non-zero, otherwise zero. |
---|
| 691 | |
---|
| 692 | \newpage |
---|
| 693 | |
---|
| 694 | \subsection{glp\_ios\_branch\_upon---choose variable to branch upon} |
---|
| 695 | |
---|
| 696 | \subsubsection*{Synopsis} |
---|
| 697 | |
---|
| 698 | \begin{verbatim} |
---|
| 699 | void glp_ios_branch_upon(glp_tree *tree, int j, int sel); |
---|
| 700 | \end{verbatim} |
---|
| 701 | |
---|
| 702 | \subsubsection*{Description} |
---|
| 703 | |
---|
| 704 | The routine \verb|glp_ios_branch_upon| can be called from the |
---|
| 705 | user-defined callback routine in response to the reason |
---|
| 706 | \verb|GLP_IBRANCH| to choose a branching variable, whose ordinal number |
---|
| 707 | is $j$. Should note that only variables, for which the routine |
---|
| 708 | \verb|glp_ios_can_branch| returns non-zero, can be used to branch upon. |
---|
| 709 | |
---|
| 710 | The parameter \verb|sel| is a flag that indicates which branch |
---|
| 711 | (subproblem) should be selected next to continue the search: |
---|
| 712 | |
---|
| 713 | \verb|GLP_DN_BRNCH|---select down-branch; |
---|
| 714 | |
---|
| 715 | \verb|GLP_UP_BRNCH|---select up-branch; |
---|
| 716 | |
---|
| 717 | \verb|GLP_NO_BRNCH|---use general selection technique. |
---|
| 718 | |
---|
| 719 | \subsubsection*{Comments} |
---|
| 720 | |
---|
| 721 | On branching the solver removes the current active subproblem from the |
---|
| 722 | active list and creates two new subproblems ({\it down-} and {\it |
---|
| 723 | up-branches}), which are added to the end of the active list. Note that |
---|
| 724 | the down-branch is created before the up-branch, so the last active |
---|
| 725 | subproblem will be the up-branch. |
---|
| 726 | |
---|
| 727 | The down- and up-branches are identical to the current subproblem with |
---|
| 728 | exception that in the down-branch the upper bound of $x_j$, the variable |
---|
| 729 | chosen to branch upon, is replaced by $\lfloor x_j^*\rfloor$, while in |
---|
| 730 | the up-branch the lower bound of $x_j$ is replaced by |
---|
| 731 | $\lceil x_j^*\rceil$, where $x_j^*$ is the value of $x_j$ in optimal |
---|
| 732 | solution to LP relaxation of the current subproblem. For example, if |
---|
| 733 | $x_j^*=3.14$, the new upper bound of $x_j$ in the down-branch is |
---|
| 734 | $\lfloor 3.14\rfloor=3$, and the new lower bound in the up-branch is |
---|
| 735 | $\lceil 3.14\rceil=4$.) |
---|
| 736 | |
---|
| 737 | Additionally the callback routine may select either down- or up-branch, |
---|
| 738 | from which the solver will continue the search. If none of the branches |
---|
| 739 | is selected, a general selection technique will be used. |
---|
| 740 | |
---|
| 741 | \newpage |
---|
| 742 | |
---|
| 743 | \subsection{glp\_ios\_terminate---terminate the solution process} |
---|
| 744 | |
---|
| 745 | \subsubsection*{Synopsis} |
---|
| 746 | |
---|
| 747 | \begin{verbatim} |
---|
| 748 | void glp_ios_terminate(glp_tree *tree); |
---|
| 749 | \end{verbatim} |
---|
| 750 | |
---|
| 751 | \subsubsection*{Description} |
---|
| 752 | |
---|
| 753 | The routine \verb|glp_ios_terminate| sets a flag indicating that the |
---|
| 754 | MIP solver should prematurely terminate the search. |
---|
| 755 | |
---|
| 756 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 757 | |
---|
| 758 | \newpage |
---|
| 759 | |
---|
| 760 | \section{The search tree exploring routines} |
---|
| 761 | |
---|
| 762 | \subsection{glp\_ios\_tree\_size---determine size of the search tree} |
---|
| 763 | |
---|
| 764 | \subsubsection*{Synopsis} |
---|
| 765 | |
---|
| 766 | \begin{verbatim} |
---|
| 767 | void glp_ios_tree_size(glp_tree *tree, int *a_cnt, int *n_cnt, |
---|
| 768 | int *t_cnt); |
---|
| 769 | \end{verbatim} |
---|
| 770 | |
---|
| 771 | \subsubsection*{Description} |
---|
| 772 | |
---|
| 773 | The routine \verb|glp_ios_tree_size| stores the following three counts |
---|
| 774 | which characterize the current size of the search tree: |
---|
| 775 | |
---|
| 776 | \verb|a_cnt| is the current number of active nodes, i.e. the current |
---|
| 777 | size of the active list; |
---|
| 778 | |
---|
| 779 | \verb|n_cnt| is the current number of all (active and inactive) nodes; |
---|
| 780 | |
---|
| 781 | \verb|t_cnt| is the total number of nodes including those which have |
---|
| 782 | been already removed from the tree. This count is increased whenever |
---|
| 783 | a new node appears in the tree and never decreased. |
---|
| 784 | |
---|
| 785 | If some of the parameters \verb|a_cnt|, \verb|n_cnt|, \verb|t_cnt| is |
---|
| 786 | a null pointer, the corresponding count is not stored. |
---|
| 787 | |
---|
| 788 | \subsection{glp\_ios\_curr\_node---determine current active subprob-\\ |
---|
| 789 | lem} |
---|
| 790 | |
---|
| 791 | \subsubsection*{Synopsis} |
---|
| 792 | |
---|
| 793 | \begin{verbatim} |
---|
| 794 | int glp_ios_curr_node(glp_tree *tree); |
---|
| 795 | \end{verbatim} |
---|
| 796 | |
---|
| 797 | \subsubsection*{Returns} |
---|
| 798 | |
---|
| 799 | The routine \verb|glp_ios_curr_node| returns the reference number of the |
---|
| 800 | current active subproblem. However, if the current subproblem does not |
---|
| 801 | exist, the routine returns zero. |
---|
| 802 | |
---|
| 803 | \newpage |
---|
| 804 | |
---|
| 805 | \subsection{glp\_ios\_next\_node---determine next active subproblem} |
---|
| 806 | |
---|
| 807 | \subsubsection*{Synopsis} |
---|
| 808 | |
---|
| 809 | \begin{verbatim} |
---|
| 810 | int glp_ios_next_node(glp_tree *tree, int p); |
---|
| 811 | \end{verbatim} |
---|
| 812 | |
---|
| 813 | \subsubsection*{Returns} |
---|
| 814 | |
---|
| 815 | If the parameter $p$ is zero, the routine \verb|glp_ios_next_node| |
---|
| 816 | returns the reference number of the first active subproblem. However, |
---|
| 817 | if the tree is empty, zero is returned. |
---|
| 818 | |
---|
| 819 | If the parameter $p$ is not zero, it must specify the reference number |
---|
| 820 | of some active subproblem, in which case the routine returns the |
---|
| 821 | reference number of the next active subproblem. However, if there is |
---|
| 822 | no next active subproblem in the list, zero is returned. |
---|
| 823 | |
---|
| 824 | All subproblems in the active list are ordered chronologically, i.e. |
---|
| 825 | subproblem $A$ precedes subproblem $B$ if $A$ was created before $B$. |
---|
| 826 | |
---|
| 827 | \subsection{glp\_ios\_prev\_node---determine previous active subproblem} |
---|
| 828 | |
---|
| 829 | \subsubsection*{Synopsis} |
---|
| 830 | |
---|
| 831 | \begin{verbatim} |
---|
| 832 | int glp_ios_prev_node(glp_tree *tree, int p); |
---|
| 833 | \end{verbatim} |
---|
| 834 | |
---|
| 835 | \subsubsection*{Returns} |
---|
| 836 | |
---|
| 837 | If the parameter $p$ is zero, the routine \verb|glp_ios_prev_node| |
---|
| 838 | returns the reference number of the last active subproblem. However, if |
---|
| 839 | the tree is empty, zero is returned. |
---|
| 840 | |
---|
| 841 | If the parameter $p$ is not zero, it must specify the reference number |
---|
| 842 | of some active subproblem, in which case the routine returns the |
---|
| 843 | reference number of the previous active subproblem. However, if there |
---|
| 844 | is no previous active subproblem in the list, zero is returned. |
---|
| 845 | |
---|
| 846 | All subproblems in the active list are ordered chronologically, i.e. |
---|
| 847 | subproblem $A$ precedes subproblem $B$ if $A$ was created before $B$. |
---|
| 848 | |
---|
| 849 | \newpage |
---|
| 850 | |
---|
| 851 | \subsection{glp\_ios\_up\_node---determine parent subproblem} |
---|
| 852 | |
---|
| 853 | \subsubsection*{Synopsis} |
---|
| 854 | |
---|
| 855 | \begin{verbatim} |
---|
| 856 | int glp_ios_up_node(glp_tree *tree, int p); |
---|
| 857 | \end{verbatim} |
---|
| 858 | |
---|
| 859 | \subsubsection*{Returns} |
---|
| 860 | |
---|
| 861 | The parameter $p$ must specify the reference number of some (active or |
---|
| 862 | inactive) subproblem, in which case the routine \verb|iet_get_up_node| |
---|
| 863 | returns the reference number of its parent subproblem. However, if the |
---|
| 864 | specified subproblem is the root of the tree and, therefore, has |
---|
| 865 | no parent, the routine returns zero. |
---|
| 866 | |
---|
| 867 | \subsection{glp\_ios\_node\_level---determine subproblem level} |
---|
| 868 | |
---|
| 869 | \subsubsection*{Synopsis} |
---|
| 870 | |
---|
| 871 | \begin{verbatim} |
---|
| 872 | int glp_ios_node_level(glp_tree *tree, int p); |
---|
| 873 | \end{verbatim} |
---|
| 874 | |
---|
| 875 | \subsubsection*{Returns} |
---|
| 876 | |
---|
| 877 | The routine \verb|glp_ios_node_level| returns the level of the |
---|
| 878 | subproblem,\linebreak whose reference number is $p$, in the |
---|
| 879 | branch-and-bound tree. (The root subproblem has level 0, and the level |
---|
| 880 | of any other subproblem is the level of its parent plus one.) |
---|
| 881 | |
---|
| 882 | \subsection{glp\_ios\_node\_bound---determine subproblem local\\bound} |
---|
| 883 | |
---|
| 884 | \subsubsection*{Synopsis} |
---|
| 885 | |
---|
| 886 | \begin{verbatim} |
---|
| 887 | double glp_ios_node_bound(glp_tree *tree, int p); |
---|
| 888 | \end{verbatim} |
---|
| 889 | |
---|
| 890 | \subsubsection*{Returns} |
---|
| 891 | |
---|
| 892 | The routine \verb|glp_ios_node_bound| returns the local bound for |
---|
| 893 | (active or inactive) subproblem, whose reference number is $p$. |
---|
| 894 | |
---|
| 895 | \subsubsection*{Comments} |
---|
| 896 | |
---|
| 897 | The local bound for subproblem $p$ is an lower (minimization) or upper |
---|
| 898 | (maximization) bound for integer optimal solution to {\it this} |
---|
| 899 | subproblem (not to the original problem). This bound is local in the |
---|
| 900 | sense that only subproblems in the subtree rooted at node $p$ cannot |
---|
| 901 | have better integer feasible solutions. |
---|
| 902 | |
---|
| 903 | On creating a subproblem (due to the branching step) its local bound is |
---|
| 904 | inherited from its parent and then may get only stronger (never weaker). |
---|
| 905 | For the root subproblem its local bound is initially set to |
---|
| 906 | \verb|-DBL_MAX| (minimization) or \verb|+DBL_MAX| (maximization) and |
---|
| 907 | then improved as the root LP relaxation has been solved. |
---|
| 908 | |
---|
| 909 | Note that the local bound is not necessarily the optimal objective value |
---|
| 910 | to corresponding LP relaxation. |
---|
| 911 | |
---|
| 912 | \subsection{glp\_ios\_best\_node---find active subproblem with best |
---|
| 913 | local bound} |
---|
| 914 | |
---|
| 915 | \subsubsection*{Synopsis} |
---|
| 916 | |
---|
| 917 | \begin{verbatim} |
---|
| 918 | int glp_ios_best_node(glp_tree *tree); |
---|
| 919 | \end{verbatim} |
---|
| 920 | |
---|
| 921 | \subsubsection*{Returns} |
---|
| 922 | |
---|
| 923 | The routine \verb|glp_ios_best_node| returns the reference number of |
---|
| 924 | the active subproblem, whose local bound is best (i.e. smallest in case |
---|
| 925 | of minimization or largest in case of maximization). However, if the |
---|
| 926 | tree is empty, the routine returns zero. |
---|
| 927 | |
---|
| 928 | \subsubsection*{Comments} |
---|
| 929 | |
---|
| 930 | The best local bound is an lower (minimization) or upper (maximization) |
---|
| 931 | bound for integer optimal solution to the original MIP problem. |
---|
| 932 | |
---|
| 933 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
| 934 | |
---|
| 935 | \newpage |
---|
| 936 | |
---|
| 937 | \section{The cut pool routines} |
---|
| 938 | |
---|
| 939 | \subsection{glp\_ios\_pool\_size---determine current size of the cut\\ |
---|
| 940 | pool} |
---|
| 941 | |
---|
| 942 | \subsubsection*{Synopsis} |
---|
| 943 | |
---|
| 944 | \begin{verbatim} |
---|
| 945 | int glp_ios_pool_size(glp_tree *tree); |
---|
| 946 | \end{verbatim} |
---|
| 947 | |
---|
| 948 | \subsubsection*{Returns} |
---|
| 949 | |
---|
| 950 | The routine \verb|glp_ios_pool_size| returns the current size of the |
---|
| 951 | cut pool, that is, the number of cutting plane constraints currently |
---|
| 952 | added to it. |
---|
| 953 | |
---|
| 954 | \subsection{glp\_ios\_add\_row---add constraint to the cut pool} |
---|
| 955 | |
---|
| 956 | \subsubsection*{Synopsis} |
---|
| 957 | |
---|
| 958 | \begin{verbatim} |
---|
| 959 | int glp_ios_add_row(glp_tree *tree, const char *name, |
---|
| 960 | int klass, int flags, int len, const int ind[], |
---|
| 961 | const double val[], int type, double rhs); |
---|
| 962 | \end{verbatim} |
---|
| 963 | |
---|
| 964 | \subsubsection*{Description} |
---|
| 965 | |
---|
| 966 | The routine \verb|glp_ios_add_row| adds specified row (cutting plane |
---|
| 967 | constraint) to the cut pool. |
---|
| 968 | |
---|
| 969 | The cutting plane constraint should have the following format: |
---|
| 970 | $$\sum_{j\in J}a_jx_j\left\{\begin{array}{@{}c@{}}\geq\\\leq\\ |
---|
| 971 | \end{array}\right\}b,$$ |
---|
| 972 | where $J$ is a set of indices (ordinal numbers) of structural variables, |
---|
| 973 | $a_j$ are constraint coefficients, $x_j$ are structural variables, $b$ |
---|
| 974 | is the right-hand side. |
---|
| 975 | |
---|
| 976 | The parameter \verb|name| specifies a symbolic name assigned to the |
---|
| 977 | constraint (1 up to 255 characters). If it is \verb|NULL| or an empty |
---|
| 978 | string, no name is assigned. |
---|
| 979 | |
---|
| 980 | The parameter \verb|klass| specifies the constraint class, which must |
---|
| 981 | be either zero or a number in the range from 101 to 200. The application |
---|
| 982 | may use this attribute to distinguish between cutting plane constraints |
---|
| 983 | of different classes.\footnote{Constraint classes numbered from 1 to 100 |
---|
| 984 | are reserved for GLPK cutting plane generators.} |
---|
| 985 | |
---|
| 986 | The parameter \verb|flags| currently is not used and must be zero. |
---|
| 987 | |
---|
| 988 | Ordinal numbers of structural variables (i.e. column indices) $j\in J$ |
---|
| 989 | and numerical values of corresponding constraint coefficients $a_j$ must |
---|
| 990 | be placed in locations \verb|ind[1]|, \dots, \verb|ind[len]| and |
---|
| 991 | \verb|val[1]|, \dots, \verb|val[len]|, respectively, where |
---|
| 992 | ${\tt len}=|J|$ is the number of constraint coefficients, |
---|
| 993 | $0\leq{\tt len}\leq n$, and $n$ is the number of columns in the problem |
---|
| 994 | object. Coefficients with identical column indices are not allowed. |
---|
| 995 | Zero coefficients are allowed, however, they are ignored. |
---|
| 996 | |
---|
| 997 | The parameter \verb|type| specifies the constraint type as follows: |
---|
| 998 | |
---|
| 999 | \verb|GLP_LO| means inequality constraint $\Sigma a_jx_j\geq b$; |
---|
| 1000 | |
---|
| 1001 | \verb|GLP_UP| means inequality constraint $\Sigma a_jx_j\leq b$; |
---|
| 1002 | |
---|
| 1003 | The parameter \verb|rhs| specifies the right-hand side $b$. |
---|
| 1004 | |
---|
| 1005 | All cutting plane constraints in the cut pool are identified by their |
---|
| 1006 | ordinal numbers 1, 2, \dots, $size$, where $size$ is the current size |
---|
| 1007 | of the cut pool. New constraints are always added to the end of the cut |
---|
| 1008 | pool, thus, ordinal numbers of previously added constraints are not |
---|
| 1009 | changed. |
---|
| 1010 | |
---|
| 1011 | \subsubsection*{Returns} |
---|
| 1012 | |
---|
| 1013 | The routine \verb|glp_ios_add_row| returns the ordinal number of the |
---|
| 1014 | cutting plane constraint added, which is the new size of the cut pool. |
---|
| 1015 | |
---|
| 1016 | \subsubsection*{Example} |
---|
| 1017 | |
---|
| 1018 | \begin{verbatim} |
---|
| 1019 | /* generate triangle cutting plane: |
---|
| 1020 | x[i] + x[j] + x[k] <= 1 */ |
---|
| 1021 | . . . |
---|
| 1022 | /* add the constraint to the cut pool */ |
---|
| 1023 | ind[1] = i, val[1] = 1.0; |
---|
| 1024 | ind[2] = j, val[2] = 1.0; |
---|
| 1025 | ind[3] = k, val[3] = 1.0; |
---|
| 1026 | glp_ios_add_row(tree, NULL, TRIANGLE_CUT, 0, 3, ind, val, |
---|
| 1027 | GLP_UP, 1.0); |
---|
| 1028 | \end{verbatim} |
---|
| 1029 | |
---|
| 1030 | \subsubsection*{Comments} |
---|
| 1031 | |
---|
| 1032 | Cutting plane constraints added to the cut pool are intended to be then |
---|
| 1033 | added only to the {\it current} subproblem, so these constraints can be |
---|
| 1034 | globally as well as locally valid. However, adding a constraint to the |
---|
| 1035 | cut pool does not mean that it will be added to the current |
---|
| 1036 | subproblem---it depends on the solver's decision: if the constraint |
---|
| 1037 | seems to be efficient, it is moved from the pool to the current |
---|
| 1038 | subproblem, otherwise it is simply dropped.\footnote{Globally valid |
---|
| 1039 | constraints could be saved and then re-used for other subproblems, but |
---|
| 1040 | currently such feature is not implemented.} |
---|
| 1041 | |
---|
| 1042 | Normally, every time the callback routine is called for cut generation, |
---|
| 1043 | the cut pool is empty. On the other hand, the solver itself can generate |
---|
| 1044 | cutting plane constraints (like Gomory's or mixed integer rounding |
---|
| 1045 | cuts), in which case the cut pool may be non-empty. |
---|
| 1046 | |
---|
| 1047 | \subsection{glp\_ios\_del\_row---remove constraint from the cut pool} |
---|
| 1048 | |
---|
| 1049 | \subsubsection*{Synopsis} |
---|
| 1050 | |
---|
| 1051 | \begin{verbatim} |
---|
| 1052 | void glp_ios_del_row(glp_tree *tree, int i); |
---|
| 1053 | \end{verbatim} |
---|
| 1054 | |
---|
| 1055 | \subsubsection*{Description} |
---|
| 1056 | |
---|
| 1057 | The routine \verb|glp_ios_del_row| deletes $i$-th row (cutting plane |
---|
| 1058 | constraint) from the cut pool, where $1\leq i\leq size$ is the ordinal |
---|
| 1059 | number of the constraint in the pool, $size$ is the current size of the |
---|
| 1060 | cut pool. |
---|
| 1061 | |
---|
| 1062 | Note that deleting a constraint from the cut pool leads to changing |
---|
| 1063 | ordinal numbers of other constraints remaining in the pool. New ordinal |
---|
| 1064 | numbers of the remaining constraints are assigned under assumption that |
---|
| 1065 | the original order of constraints is not changed. Let, for example, |
---|
| 1066 | there be four constraints $a$, $b$, $c$ and $d$ in the cut pool, which |
---|
| 1067 | have ordinal numbers 1, 2, 3 and 4, respectively, and let constraint |
---|
| 1068 | $b$ have been deleted. Then after deletion the remaining constraint $a$, |
---|
| 1069 | $c$ and $d$ are assigned new ordinal numbers 1, 2 and 3, respectively. |
---|
| 1070 | |
---|
| 1071 | To find the constraint to be deleted the routine \verb|glp_ios_del_row| |
---|
| 1072 | uses ``smart'' linear search, so it is recommended to remove constraints |
---|
| 1073 | in a natural or reverse order and avoid removing them in a random order. |
---|
| 1074 | |
---|
| 1075 | \subsubsection*{Example} |
---|
| 1076 | |
---|
| 1077 | \begin{verbatim} |
---|
| 1078 | /* keep first 10 constraints in the cut pool and remove other |
---|
| 1079 | constraints */ |
---|
| 1080 | while (glp_ios_pool_size(tree) > 10) |
---|
| 1081 | glp_ios_del_row(tree, glp_ios_pool_size(tree)); |
---|
| 1082 | \end{verbatim} |
---|
| 1083 | |
---|
| 1084 | \newpage |
---|
| 1085 | |
---|
| 1086 | \subsection{glp\_ios\_clear\_pool---remove all constraints from the cut |
---|
| 1087 | pool} |
---|
| 1088 | |
---|
| 1089 | \subsubsection*{Synopsis} |
---|
| 1090 | |
---|
| 1091 | \begin{verbatim} |
---|
| 1092 | void glp_ios_clear_pool(glp_tree *tree); |
---|
| 1093 | \end{verbatim} |
---|
| 1094 | |
---|
| 1095 | \subsubsection*{Description} |
---|
| 1096 | |
---|
| 1097 | The routine \verb|glp_ios_clear_pool| makes the cut pool empty deleting |
---|
| 1098 | all existing rows (cutting plane constraints) from it. |
---|
| 1099 | |
---|
| 1100 | %* eof *% |
---|