lemon-project-template-glpk
view 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 source
1 %* glpk05.tex *%
3 \chapter{Branch-and-Cut API Routines}
5 \section{Introduction}
7 \subsection{Using the callback routine}
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.
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.}
19 \begin{verbatim}
20 void foo_bar(glp_tree *tree, void *info);
21 \end{verbatim}
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.
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:
35 \newpage
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}
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.
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.
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:
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}
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_|'.
86 \subsection{Branch-and-cut algorithm}
88 This section gives a schematic description of the branch-and-cut
89 algorithm as it is implemented in the GLPK MIP solver.
91 \medskip
93 {\it 1. Initialization}
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.
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$.
104 \medskip
106 {\it 2. Subproblem selection}
108 If $L=\varnothing$ then GO TO 9.
110 Select $P\in L$, i.e. make active subproblem $P$ current.
112 \medskip
114 {\it 3. Solving LP relaxation}
116 Solve $P^{\it LP}$, which is LP relaxation of $P$.
118 If $P^{\it LP}$ has no primal feasible solution then GO TO 8.
120 Let $z^{\it LP}$ be the optimal objective value for $P^{\it LP}$.
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.
125 \medskip
127 {\it 4. Adding ``lazy'' constraints}
129 Let $x^{\it LP}$ be the optimal solution to $P^{\it LP}$.
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.
135 \medskip
137 {\it 5. Check for integrality}
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}$.
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.
147 \medskip
149 {\it 6. Adding cutting planes}
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.
155 \medskip
157 {\it 7. Branching}
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}$.
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$.)
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$.)
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.
179 \medskip
181 {\it 8. Pruning}
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.
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}$.
198 \medskip
200 {\it 9. Termination}
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.
208 \subsection{The search tree}
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.
220 \newpage
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}&\\}
235 \bigskip
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 }
245 \begin{center}
246 Fig. 1. An example of the search tree.
247 \end{center}
248 \end{figure}
250 In GLPK each node may have one of the following four statuses:
252 $\bullet$ {\it current node} is the active node currently being
253 processed;
255 $\bullet$ {\it active node} is a leaf node, which still has to be
256 processed;
258 $\bullet$ {\it non-active node} is a node, which has been processed,
259 but not fathomed;
261 $\bullet$ {\it fathomed node} is a node, which has been processed and
262 fathomed.
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.
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.
274 \subsection{Current subproblem}
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.
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.
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.
299 \subsection{The cut pool}
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.
309 \subsection{Reasons for calling the callback routine}
311 The callback routine may be called by the MIP solver for the following
312 reasons.
314 \subsubsection*{Request for subproblem selection}
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.
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|.
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|.
331 \subsubsection*{Request for preprocessing}
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.
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.
341 \subsubsection*{Request for row generation}
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.
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.
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|.
361 \subsubsection*{Request for heuristic solution}
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.
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|.
376 \subsubsection*{Request for cut generation}
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.
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.}
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.
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.
403 \subsubsection*{Request for branching}
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.
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|.
420 \subsubsection*{Better integer solution found}
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.
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).
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.
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.
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.
446 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
448 \newpage
450 \section{Basic routines}
452 \subsection{glp\_ios\_reason---determine reason for calling the
453 callback routine}
455 \subsubsection*{Synopsis}
457 \begin{verbatim}
458 int glp_ios_reason(glp_tree *tree);
459 \end{verbatim}
461 \subsubsection*{Returns}
463 The routine \verb|glp_ios_reason| returns a code, which indicates why
464 the user-defined callback routine is being called:
466 \verb|GLP_ISELECT|---request for subproblem selection;
468 \verb|GLP_IPREPRO|---request for preprocessing;
470 \verb|GLP_IROWGEN|---request for row generation;
472 \verb|GLP_IHEUR |---request for heuristic solution;
474 \verb|GLP_ICUTGEN|---request for cut generation;
476 \verb|GLP_IBRANCH|---request for branching;
478 \verb|GLP_IBINGO |---better integer solution found.
480 \subsection{glp\_ios\_get\_prob---access the problem object}
482 \subsubsection*{Synopsis}
484 \begin{verbatim}
485 glp_prob *glp_ios_get_prob(glp_tree *tree);
486 \end{verbatim}
488 \subsubsection*{Description}
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.
496 \subsubsection*{Returns}
498 The routine \verb|glp_ios_get_prob| returns a pointer to the problem
499 object used by the MIP solver.
501 \subsubsection*{Comments}
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.
510 \subsection{glp\_ios\_row\_attr---determine additional row attributes}
512 \subsubsection*{Synopsis}
514 \begin{verbatim}
515 void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr);
516 \end{verbatim}
518 \subsubsection*{Description}
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.
524 The structure \verb|glp_attr| has the following fields:
526 \medskip
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}
536 \medskip
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}
546 \medskip
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}
560 \newpage
562 \subsection{glp\_ios\_mip\_gap---compute relative MIP gap}
564 \subsubsection*{Synopsis}
566 \begin{verbatim}
567 double glp_ios_mip_gap(glp_tree *tree);
568 \end{verbatim}
570 \subsubsection*{Description}
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|.
580 \subsubsection*{Returns}
582 The routine \verb|glp_ios_mip_gap| returns the relative MIP gap.
584 \subsubsection*{Comments}
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.
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\%.
597 \newpage
599 \subsection{glp\_ios\_node\_data---access application-specific data}
601 \subsubsection*{Synopsis}
603 \begin{verbatim}
604 void *glp_ios_node_data(glp_tree *tree, int p);
605 \end{verbatim}
607 \subsubsection*{Description}
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$.
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.
618 The application may use these memory blocks to store specific data for
619 each subproblem.
621 \subsubsection*{Returns}
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.
627 \subsection{glp\_ios\_select\_node---select subproblem to continue the
628 search}
630 \subsubsection*{Synopsis}
632 \begin{verbatim}
633 void glp_ios_select_node(glp_tree *tree, int p);
634 \end{verbatim}
636 \subsubsection*{Description}
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.
644 \newpage
646 \subsection{glp\_ios\_heur\_sol---provide solution found by heuristic}
648 \subsubsection*{Synopsis}
650 \begin{verbatim}
651 int glp_ios_heur_sol(glp_tree *tree, const double x[]);
652 \end{verbatim}
654 \subsubsection*{Description}
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.
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.
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.
672 \subsubsection*{Returns}
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.
678 \subsection{glp\_ios\_can\_branch---check if can branch upon specified
679 variable}
681 \subsubsection*{Synopsis}
683 \begin{verbatim}
684 int glp_ios_can_branch(glp_tree *tree, int j);
685 \end{verbatim}
687 \subsubsection*{Returns}
689 If $j$-th variable (column) can be used to branch upon, the routine
690 returns non-zero, otherwise zero.
692 \newpage
694 \subsection{glp\_ios\_branch\_upon---choose variable to branch upon}
696 \subsubsection*{Synopsis}
698 \begin{verbatim}
699 void glp_ios_branch_upon(glp_tree *tree, int j, int sel);
700 \end{verbatim}
702 \subsubsection*{Description}
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.
710 The parameter \verb|sel| is a flag that indicates which branch
711 (subproblem) should be selected next to continue the search:
713 \verb|GLP_DN_BRNCH|---select down-branch;
715 \verb|GLP_UP_BRNCH|---select up-branch;
717 \verb|GLP_NO_BRNCH|---use general selection technique.
719 \subsubsection*{Comments}
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.
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$.)
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.
741 \newpage
743 \subsection{glp\_ios\_terminate---terminate the solution process}
745 \subsubsection*{Synopsis}
747 \begin{verbatim}
748 void glp_ios_terminate(glp_tree *tree);
749 \end{verbatim}
751 \subsubsection*{Description}
753 The routine \verb|glp_ios_terminate| sets a flag indicating that the
754 MIP solver should prematurely terminate the search.
756 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
758 \newpage
760 \section{The search tree exploring routines}
762 \subsection{glp\_ios\_tree\_size---determine size of the search tree}
764 \subsubsection*{Synopsis}
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}
771 \subsubsection*{Description}
773 The routine \verb|glp_ios_tree_size| stores the following three counts
774 which characterize the current size of the search tree:
776 \verb|a_cnt| is the current number of active nodes, i.e. the current
777 size of the active list;
779 \verb|n_cnt| is the current number of all (active and inactive) nodes;
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.
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.
788 \subsection{glp\_ios\_curr\_node---determine current active subprob-\\
789 lem}
791 \subsubsection*{Synopsis}
793 \begin{verbatim}
794 int glp_ios_curr_node(glp_tree *tree);
795 \end{verbatim}
797 \subsubsection*{Returns}
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.
803 \newpage
805 \subsection{glp\_ios\_next\_node---determine next active subproblem}
807 \subsubsection*{Synopsis}
809 \begin{verbatim}
810 int glp_ios_next_node(glp_tree *tree, int p);
811 \end{verbatim}
813 \subsubsection*{Returns}
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.
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.
824 All subproblems in the active list are ordered chronologically, i.e.
825 subproblem $A$ precedes subproblem $B$ if $A$ was created before $B$.
827 \subsection{glp\_ios\_prev\_node---determine previous active subproblem}
829 \subsubsection*{Synopsis}
831 \begin{verbatim}
832 int glp_ios_prev_node(glp_tree *tree, int p);
833 \end{verbatim}
835 \subsubsection*{Returns}
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.
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.
846 All subproblems in the active list are ordered chronologically, i.e.
847 subproblem $A$ precedes subproblem $B$ if $A$ was created before $B$.
849 \newpage
851 \subsection{glp\_ios\_up\_node---determine parent subproblem}
853 \subsubsection*{Synopsis}
855 \begin{verbatim}
856 int glp_ios_up_node(glp_tree *tree, int p);
857 \end{verbatim}
859 \subsubsection*{Returns}
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.
867 \subsection{glp\_ios\_node\_level---determine subproblem level}
869 \subsubsection*{Synopsis}
871 \begin{verbatim}
872 int glp_ios_node_level(glp_tree *tree, int p);
873 \end{verbatim}
875 \subsubsection*{Returns}
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.)
882 \subsection{glp\_ios\_node\_bound---determine subproblem local\\bound}
884 \subsubsection*{Synopsis}
886 \begin{verbatim}
887 double glp_ios_node_bound(glp_tree *tree, int p);
888 \end{verbatim}
890 \subsubsection*{Returns}
892 The routine \verb|glp_ios_node_bound| returns the local bound for
893 (active or inactive) subproblem, whose reference number is $p$.
895 \subsubsection*{Comments}
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.
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.
909 Note that the local bound is not necessarily the optimal objective value
910 to corresponding LP relaxation.
912 \subsection{glp\_ios\_best\_node---find active subproblem with best
913 local bound}
915 \subsubsection*{Synopsis}
917 \begin{verbatim}
918 int glp_ios_best_node(glp_tree *tree);
919 \end{verbatim}
921 \subsubsection*{Returns}
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.
928 \subsubsection*{Comments}
930 The best local bound is an lower (minimization) or upper (maximization)
931 bound for integer optimal solution to the original MIP problem.
933 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
935 \newpage
937 \section{The cut pool routines}
939 \subsection{glp\_ios\_pool\_size---determine current size of the cut\\
940 pool}
942 \subsubsection*{Synopsis}
944 \begin{verbatim}
945 int glp_ios_pool_size(glp_tree *tree);
946 \end{verbatim}
948 \subsubsection*{Returns}
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.
954 \subsection{glp\_ios\_add\_row---add constraint to the cut pool}
956 \subsubsection*{Synopsis}
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}
964 \subsubsection*{Description}
966 The routine \verb|glp_ios_add_row| adds specified row (cutting plane
967 constraint) to the cut pool.
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.
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.
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.}
986 The parameter \verb|flags| currently is not used and must be zero.
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.
997 The parameter \verb|type| specifies the constraint type as follows:
999 \verb|GLP_LO| means inequality constraint $\Sigma a_jx_j\geq b$;
1001 \verb|GLP_UP| means inequality constraint $\Sigma a_jx_j\leq b$;
1003 The parameter \verb|rhs| specifies the right-hand side $b$.
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.
1011 \subsubsection*{Returns}
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.
1016 \subsubsection*{Example}
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}
1030 \subsubsection*{Comments}
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.}
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.
1047 \subsection{glp\_ios\_del\_row---remove constraint from the cut pool}
1049 \subsubsection*{Synopsis}
1051 \begin{verbatim}
1052 void glp_ios_del_row(glp_tree *tree, int i);
1053 \end{verbatim}
1055 \subsubsection*{Description}
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.
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.
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.
1075 \subsubsection*{Example}
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}
1084 \newpage
1086 \subsection{glp\_ios\_clear\_pool---remove all constraints from the cut
1087 pool}
1089 \subsubsection*{Synopsis}
1091 \begin{verbatim}
1092 void glp_ios_clear_pool(glp_tree *tree);
1093 \end{verbatim}
1095 \subsubsection*{Description}
1097 The routine \verb|glp_ios_clear_pool| makes the cut pool empty deleting
1098 all existing rows (cutting plane constraints) from it.
1100 %* eof *%