COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/doc/glpk05.tex

subpack-glpk
Last change on this file was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 38.5 KB
Line 
1%* glpk05.tex *%
2
3\chapter{Branch-and-Cut API Routines}
4
5\section{Introduction}
6
7\subsection{Using the callback routine}
8
9The GLPK MIP solver based on the branch-and-cut method allows the
10application program to control the solution process. This is attained
11by means of the user-defined callback routine, which is called by the
12solver at various points of the branch-and-cut algorithm.
13
14The callback routine passed to the MIP solver should be written by the
15user and has the following specification:\footnote{The name
16{\tt foo\_bar} used here is a placeholder for the callback routine
17name.}
18
19\begin{verbatim}
20   void foo_bar(glp_tree *tree, void *info);
21\end{verbatim}
22
23\noindent
24where \verb|tree| is a pointer to the data structure \verb|glp_tree|,
25which should be used on subsequent calls to branch-and-cut interface
26routines, 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
28some external data to the callback routine.
29
30The callback routine is passed to the MIP solver through the control
31parameter structure \verb|glp_iocp| (see Chapter ``Basic API Routines'',
32Section ``Mixed integer programming routines'', Subsection ``Solve MIP
33problem 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
49To determine why it is being called by the MIP solver the callback
50routine should use the routine \verb|glp_ios_reason| (described in this
51section below), which returns a code indicating the reason for calling.
52Depending on the reason the callback routine may perform necessary
53actions to control the solution process.
54
55The reason codes, which correspond to various point of the
56branch-and-cut algorithm implemented in the MIP solver, are described
57in Subsection ``Reasons for calling the callback routine'' below.
58
59To ignore calls for reasons, which are not processed by the callback
60routine, it should just return to the MIP solver doing nothing. For
61example:
62
63\begin{verbatim}
64void 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
81To control the solution process as well as to obtain necessary
82information the callback routine may use the branch-and-cut API
83routines described in this chapter. Names of all these routines begin
84with `\verb|glp_ios_|'.
85
86\subsection{Branch-and-cut algorithm}
87
88This section gives a schematic description of the branch-and-cut
89algorithm as it is implemented in the GLPK MIP solver.
90
91\medskip
92
93{\it 1. Initialization}
94
95Set $L:=\{P_0\}$, where $L$ is the {\it active list} (i.e. the list of
96active subproblems), $P_0$ is the original MIP problem to be solved.
97
98Set $z^{\it best}:=+\infty$ (in case of minimization) or
99$z^{\it best}:=-\infty$ (in case of maximization), where $z^{\it best}$
100is {\it incumbent value}, i.e. an upper (minimization) or lower
101(maximization) global bound for $z^{\it opt}$, the optimal objective
102value for $P^0$.
103
104\medskip
105
106{\it 2. Subproblem selection}
107
108If $L=\varnothing$ then GO TO 9.
109
110Select $P\in L$, i.e. make active subproblem $P$ current.
111
112\medskip
113
114{\it 3. Solving LP relaxation}
115
116Solve $P^{\it LP}$, which is LP relaxation of $P$.
117
118If $P^{\it LP}$ has no primal feasible solution then GO TO 8.
119
120Let $z^{\it LP}$ be the optimal objective value for $P^{\it LP}$.
121
122If $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
129Let $x^{\it LP}$ be the optimal solution to $P^{\it LP}$.
130
131If there are ``lazy'' constraints (i.e. essential constraints not
132included in the original MIP problem $P_0$), which are violated at the
133optimal point $x^{\it LP}$, add them to $P$, and GO TO 3.
134
135\medskip
136
137{\it 5. Check for integrality}
138
139Let $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
143If $x^{\it LP}_j$ are integral for all integer variables, then a better
144integer 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
151If there are cutting planes (i.e. valid constraints for $P$),
152which are violated at the optimal point $x^{\it LP}$, add them to $P$,
153and GO TO 3.
154
155\medskip
156
157{\it 7. Branching}
158
159Select {\it branching variable} $x_j$, i.e. a variable, which is
160required to be integer, and whose value $x^{\it LP}_j\in x^{\it LP}$ is
161fractional in the optimal solution to $P^{\it LP}$.
162
163Create new subproblem $P^D$ (so called {\it down branch}), which is
164identical to the current subproblem $P$ with exception that the upper
165bound of $x_j$ is replaced by $\lfloor x^{\it LP}_j\rfloor$. (For
166example, if $x^{\it LP}_j=3.14$, the new upper bound of $x_j$ in the
167down branch will be $\lfloor 3.14\rfloor=3$.)
168
169Create new subproblem $P^U$ (so called {\it up branch}), which is
170identical to the current subproblem $P$ with exception that the lower
171bound of $x_j$ is replaced by $\lceil x^{\it LP}_j\rceil$. (For example,
172if $x^{\it LP}_j=3.14$, the new lower bound of $x_j$ in the up branch
173will be $\lceil 3.14\rceil=4$.)
174
175Set $L:=(L\backslash\{P\})\cup\{P^D,P^U\}$, i.e. remove the current
176subproblem $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
183Remove from the active list $L$ all subproblems (including the current
184one), whose local bound $\widetilde{z}$ is not better than the global
185bound $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
188GO TO 2.
189
190The local bound $\widetilde{z}$ for subproblem $P$ is an lower
191(minimization) or upper (maximization) bound for integer optimal
192solution to {\it this} subproblem (not to the original problem). This
193bound is local in the sense that only subproblems in the subtree rooted
194at node $P$ cannot have better integer feasible solutions. Note that
195the local bound is not necessarily the optimal objective value to LP
196relaxation $P^{\it LP}$.
197
198\medskip
199
200{\it 9. Termination}
201
202If $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
205feasible solution stored on step 5 is the integer optimal solution to
206the original problem $P_0$ with $z^{\it opt}=z^{\it best}$. STOP.
207
208\subsection{The search tree}
209
210On the branching step of the branch-and-cut algorithm the current
211subproblem is divided into two\footnote{In more general cases the
212current subproblem may be divided into more than two subproblems.
213However, currently such feature is not used in GLPK.} new subproblems,
214so the set of all subproblems can be represented in the form of a rooted
215tree, which is called the {\it search} or {\it branch-and-bound} tree.
216An example of the search tree is shown on Fig.~1. Each node of the
217search 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}
246Fig. 1. An example of the search tree.
247\end{center}
248\end{figure}
249
250In GLPK each node may have one of the following four statuses:
251
252$\bullet$ {\it current node} is the active node currently being
253processed;
254
255$\bullet$ {\it active node} is a leaf node, which still has to be
256processed;
257
258$\bullet$ {\it non-active node} is a node, which has been processed,
259but not fathomed;
260
261$\bullet$ {\it fathomed node} is a node, which has been processed and
262fathomed.
263
264In the data structure representing the search tree GLPK keeps only
265current, active, and non-active nodes. Once a node has been fathomed,
266it is removed from the tree data structure.
267
268Being created each node of the search tree is assigned a distinct
269positive integer called the {\it subproblem reference number}, which
270may be used by the application program to specify a particular node of
271the tree. The root node corresponding to the original problem to be
272solved is always assigned the reference number 1.
273
274\subsection{Current subproblem}
275
276The current subproblem is a MIP problem corresponding to the current
277node of the search tree. It is represented as the GLPK problem object
278(\verb|glp_prob|) that allows the application program using API routines
279to access its content in the standard way. If the MIP presolver is not
280used, it is the original problem object passed to the routine
281\verb|glp_intopt|; otherwise, it is an internal problem object built by
282the MIP presolver.
283
284Note that the problem object is used by the MIP solver itself during
285the solution process for various purposes (to solve LP relaxations, to
286perfom branching, etc.), and even if the MIP presolver is not used, the
287current content of the problem object may differ from its original
288content. For example, it may have additional rows, bounds of some rows
289and columns may be changed, etc. In particular, LP segment of the
290problem object corresponds to LP relaxation of the current subproblem.
291However, on exit from the MIP solver the content of the problem object
292is restored to its original state.
293
294To obtain information from the problem object the application program
295may use any API routines, which do not change the object. Using API
296routines, which change the problem object, is restricted to stipulated
297cases.
298
299\subsection{The cut pool}
300
301The {\it cut pool} is a set of cutting plane constraints maintained by
302the MIP solver. It is used by the GLPK cut generation routines and may
303be used by the application program in the same way, i.e. rather than
304to add cutting plane constraints directly to the problem object the
305application program may store them to the cut pool. In the latter case
306the solver looks through the cut pool, selects efficient constraints,
307and adds them to the problem object.
308
309\subsection{Reasons for calling the callback routine}
310
311The callback routine may be called by the MIP solver for the following
312reasons.
313
314\subsubsection*{Request for subproblem selection}
315
316The callback routine is called with the reason code \verb|GLP_ISELECT|
317if the current subproblem has been fathomed and therefore there is no
318current subproblem.
319
320In response the callback routine may select some subproblem from the
321active list and pass its reference number to the solver using the
322routine \verb|glp_ios_select_node|, in which case the solver continues
323the search from the specified active subproblem. If no selection is made
324by the callback routine, the solver uses a backtracking technique
325specified by the control parameter \verb|bt_tech|.
326
327To explore the active list (i.e. active nodes of the branch-and-bound
328tree) the callback routine may use the routines \verb|glp_ios_next_node|
329and \verb|glp_ios_prev_node|.
330
331\subsubsection*{Request for preprocessing}
332
333The callback routine is called with the reason code \verb|GLP_IPREPRO|
334if the current subproblem has just been selected from the active list
335and its LP relaxation is not solved yet.
336
337In response the callback routine may perform some preprocessing of the
338current subproblem like tightening bounds of some variables or removing
339bounds of some redundant constraints.
340
341\subsubsection*{Request for row generation}
342
343The callback routine is called with the reason code \verb|GLP_IROWGEN|
344if LP relaxation of the current subproblem has just been solved to
345optimality and its objective value is better than the best known integer
346feasible solution.
347
348In response the callback routine may add one or more ``lazy''
349constraints (rows), which are violated by the current optimal solution
350of 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
353re-optimization of LP relaxation. If there are no violated constraints,
354the callback routine should just return.
355
356Optimal solution components for LP relaxation can be obtained with API
357routines \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
363The callback routine is called with the reason code \verb|GLP_IHEUR|
364if LP relaxation of the current subproblem being solved to optimality
365is integer infeasible (i.e. values of some structural variables of
366integer kind are fractional), though its objective value is better than
367the best known integer feasible solution.
368
369In response the callback routine may try applying a primal heuristic
370to find an integer feasible solution,\footnote{Integer feasible to the
371original MIP problem, not to the current subproblem.} which is better
372than the best known one. In case of success the callback routine may
373store such better solution in the problem object using the routine
374\verb|glp_ios_heur_sol|.
375
376\subsubsection*{Request for cut generation}
377
378The callback routine is called with the reason code \verb|GLP_ICUTGEN|
379if LP relaxation of the current subproblem being solved to optimality
380is integer infeasible (i.e. values of some structural variables of
381integer kind are fractional), though its objective value is better than
382the best known integer feasible solution.
383
384In response the callback routine may reformulate the {\it current}
385subproblem (before it will be splitted up due to branching) by adding to
386the problem object one or more {\it cutting plane constraints}, which
387cut off the fractional optimal point from the MIP
388polytope.\footnote{Since these constraints are added to the current
389subproblem, they may be globally as well as locally valid.}
390
391Adding cutting plane constraints may be performed in two ways.
392One way is the same as for the reason code \verb|GLP_IROWGEN| (see
393above), in which case the callback routine adds new rows corresponding
394to cutting plane constraints directly to the current subproblem.
395
396The other way is to add cutting plane constraints to the {\it cut pool},
397a set of cutting plane constraints maintained by the solver, rather than
398directly to the current subproblem. In this case after return from the
399callback routine the solver looks through the cut pool, selects
400efficient cutting plane constraints, adds them to the current
401subproblem, drops other constraints, and then performs re-optimization.
402
403\subsubsection*{Request for branching}
404
405The callback routine is called with the reason code \verb|GLP_IBRANCH|
406if LP relaxation of the current subproblem being solved to optimality
407is integer infeasible (i.e. values of some structural variables of
408integer kind are fractional), though its objective value is better than
409the best known integer feasible solution.
410
411In response the callback routine may choose some variable suitable for
412branching (i.e. integer variable, whose value in optimal solution to
413LP relaxation of the current subproblem is fractional) and pass its
414ordinal number to the solver using the routine
415\verb|glp_ios_branch_upon|, in which case the solver splits the current
416subproblem in two new subproblems and continues the search. If no choice
417is made by the callback routine, the solver uses a branching technique
418specified by the control parameter \verb|br_tech|.
419
420\subsubsection*{Better integer solution found}
421
422The callback routine is called with the reason code \verb|GLP_IBINGO|
423if LP relaxation of the current subproblem being solved to optimality
424is integer feasible (i.e. values of all structural variables of integer
425kind are integral within the working precision) and its objective value
426is better than the best known integer feasible solution.
427
428Optimal solution components for LP relaxation can be obtained in the
429same way as for the reason code \verb|GLP_IROWGEN| (see above).
430
431Components 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
434there may be additional rows in the problem object.
435
436The difference between optimal solution to LP relaxation and
437corresponding MIP solution is that in the former case some structural
438variables of integer kind (namely, basic variables) may have values,
439which are close to nearest integers within the working precision, while
440in the latter case all such variables have exact integral values.
441
442The reason \verb|GLP_IBINGO| is intended only for informational
443purposes, so the callback routine should not modify the problem object
444in this case.
445
446%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
447
448\newpage
449
450\section{Basic routines}
451
452\subsection{glp\_ios\_reason---determine reason for calling the
453callback routine}
454
455\subsubsection*{Synopsis}
456
457\begin{verbatim}
458int glp_ios_reason(glp_tree *tree);
459\end{verbatim}
460
461\subsubsection*{Returns}
462
463The routine \verb|glp_ios_reason| returns a code, which indicates why
464the 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}
485glp_prob *glp_ios_get_prob(glp_tree *tree);
486\end{verbatim}
487
488\subsubsection*{Description}
489
490The routine \verb|glp_ios_get_prob| can be called from the user-defined
491callback routine to access the problem object, which is used by the MIP
492solver. 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
494internal problem object built by the presolver.
495
496\subsubsection*{Returns}
497
498The routine \verb|glp_ios_get_prob| returns a pointer to the problem
499object used by the MIP solver.
500
501\subsubsection*{Comments}
502
503To obtain various information about the problem instance the callback
504routine 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
506original problem object passed to the routine \verb|glp_intopt| if the
507MIP presolver is not used; otherwise it is an internal problem object
508built by the presolver.
509
510\subsection{glp\_ios\_row\_attr---determine additional row attributes}
511
512\subsubsection*{Synopsis}
513
514\begin{verbatim}
515void glp_ios_row_attr(glp_tree *tree, int i, glp_attr *attr);
516\end{verbatim}
517
518\subsubsection*{Description}
519
520The 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
524The 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,
531the row was added either to the original problem object passed to the
532routine \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
552plane constraint generated by the solver, its class may be the
553following:\\
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}
567double glp_ios_mip_gap(glp_tree *tree);
568\end{verbatim}
569
570\subsubsection*{Description}
571
572The routine \verb|glp_ios_mip_gap| computes the relative MIP gap (also
573called {\it duality gap}) with the following formula:
574$${\tt gap} = \frac{|{\tt best\_mip} - {\tt best\_bnd}|}
575{|{\tt best\_mip}| + {\tt DBL\_EPSILON}}$$
576where \verb|best_mip| is the best integer feasible solution found so
577far, \verb|best_bnd| is the best (global) bound. If no integer feasible
578solution has been found yet, \verb|gap| is set to \verb|DBL_MAX|.
579
580\subsubsection*{Returns}
581
582The routine \verb|glp_ios_mip_gap| returns the relative MIP gap.
583
584\subsubsection*{Comments}
585
586The relative MIP gap is used to measure the quality of the best integer
587feasible 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}$$
590in case of minimization, or in the range
591$${\tt best\_mip}\leq z^*\leq{\tt best\_bnd}$$
592in case of maximization.
593
594To express the relative MIP gap in percents the value returned by the
595routine \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}
604void *glp_ios_node_data(glp_tree *tree, int p);
605\end{verbatim}
606
607\subsubsection*{Description}
608
609The routine \verb|glp_ios_node_data| allows the application accessing a
610memory block allocated for the subproblem (which may be active or
611inactive), whose reference number is $p$.
612
613The size of the block is defined by the control parameter \verb|cb_size|
614passed to the routine \verb|glp_intopt|. The block is initialized by
615binary zeros on creating corresponding subproblem, and its contents is
616kept until the subproblem will be removed from the tree.
617
618The application may use these memory blocks to store specific data for
619each subproblem.
620
621\subsubsection*{Returns}
622
623The routine \verb|glp_ios_node_data| returns a pointer to the memory
624block for the specified subproblem. Note that if \verb|cb_size| = 0, the
625routine returns a null pointer.
626
627\subsection{glp\_ios\_select\_node---select subproblem to continue the
628search}
629
630\subsubsection*{Synopsis}
631
632\begin{verbatim}
633void glp_ios_select_node(glp_tree *tree, int p);
634\end{verbatim}
635
636\subsubsection*{Description}
637
638The routine \verb|glp_ios_select_node| can be called from the
639user-defined callback routine in response to the reason
640\verb|GLP_ISELECT| to select an active subproblem, whose reference
641number is $p$. The search will be continued from the subproblem
642selected.
643
644\newpage
645
646\subsection{glp\_ios\_heur\_sol---provide solution found by heuristic}
647
648\subsubsection*{Synopsis}
649
650\begin{verbatim}
651int glp_ios_heur_sol(glp_tree *tree, const double x[]);
652\end{verbatim}
653
654\subsubsection*{Description}
655
656The routine \verb|glp_ios_heur_sol| can be called from the user-defined
657callback routine in response to the reason \verb|GLP_IHEUR| to provide
658an integer feasible solution found by a primal heuristic.
659
660Primal values of {\it all} variables (columns) found by the heuristic
661should be placed in locations $x[1]$, \dots, $x[n]$, where $n$ is the
662number 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
664solution provided.
665
666Using the solution passed in the array $x$ the routine computes value
667of the objective function. If the objective value is better than the
668best known integer feasible solution, the routine computes values of
669auxiliary variables (rows) and stores all solution components in the
670problem object.
671
672\subsubsection*{Returns}
673
674If the provided solution is accepted, the routine
675\verb|glp_ios_heur_sol| returns zero. Otherwise, if the provided
676solution is rejected, the routine returns non-zero.
677
678\subsection{glp\_ios\_can\_branch---check if can branch upon specified
679variable}
680
681\subsubsection*{Synopsis}
682
683\begin{verbatim}
684int glp_ios_can_branch(glp_tree *tree, int j);
685\end{verbatim}
686
687\subsubsection*{Returns}
688
689If $j$-th variable (column) can be used to branch upon, the routine
690returns 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}
699void glp_ios_branch_upon(glp_tree *tree, int j, int sel);
700\end{verbatim}
701
702\subsubsection*{Description}
703
704The routine \verb|glp_ios_branch_upon| can be called from the
705user-defined callback routine in response to the reason
706\verb|GLP_IBRANCH| to choose a branching variable, whose ordinal number
707is $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
710The 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
721On branching the solver removes the current active subproblem from the
722active list and creates two new subproblems ({\it down-} and {\it
723up-branches}), which are added to the end of the active list. Note that
724the down-branch is created before the up-branch, so the last active
725subproblem will be the up-branch.
726
727The down- and up-branches are identical to the current subproblem with
728exception that in the down-branch the upper bound of $x_j$, the variable
729chosen to branch upon, is replaced by $\lfloor x_j^*\rfloor$, while in
730the 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
732solution 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
737Additionally the callback routine may select either down- or up-branch,
738from which the solver will continue the search. If none of the branches
739is 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}
748void glp_ios_terminate(glp_tree *tree);
749\end{verbatim}
750
751\subsubsection*{Description}
752
753The routine \verb|glp_ios_terminate| sets a flag indicating that the
754MIP 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}
767void 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
773The routine \verb|glp_ios_tree_size| stores the following three counts
774which characterize the current size of the search tree:
775
776\verb|a_cnt| is the current number of active nodes, i.e. the current
777size 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
782been already removed from the tree. This count is increased whenever
783a new node appears in the tree and never decreased.
784
785If some of the parameters \verb|a_cnt|, \verb|n_cnt|, \verb|t_cnt| is
786a null pointer, the corresponding count is not stored.
787
788\subsection{glp\_ios\_curr\_node---determine current active subprob-\\
789lem}
790
791\subsubsection*{Synopsis}
792
793\begin{verbatim}
794int glp_ios_curr_node(glp_tree *tree);
795\end{verbatim}
796
797\subsubsection*{Returns}
798
799The routine \verb|glp_ios_curr_node| returns the reference number of the
800current active subproblem. However, if the current subproblem does not
801exist, 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}
810int glp_ios_next_node(glp_tree *tree, int p);
811\end{verbatim}
812
813\subsubsection*{Returns}
814
815If the parameter $p$ is zero, the routine \verb|glp_ios_next_node|
816returns the reference number of the first active subproblem. However,
817if the tree is empty, zero is returned.
818
819If the parameter $p$ is not zero, it must specify the reference number
820of some active subproblem, in which case the routine returns the
821reference number of the next active subproblem. However, if there is
822no next active subproblem in the list, zero is returned.
823
824All subproblems in the active list are ordered chronologically, i.e.
825subproblem $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}
832int glp_ios_prev_node(glp_tree *tree, int p);
833\end{verbatim}
834
835\subsubsection*{Returns}
836
837If the parameter $p$ is zero, the routine \verb|glp_ios_prev_node|
838returns the reference number of the last active subproblem. However, if
839the tree is empty, zero is returned.
840
841If the parameter $p$ is not zero, it must specify the reference number
842of some active subproblem, in which case the routine returns the
843reference number of the previous active subproblem. However, if there
844is no previous active subproblem in the list, zero is returned.
845
846All subproblems in the active list are ordered chronologically, i.e.
847subproblem $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}
856int glp_ios_up_node(glp_tree *tree, int p);
857\end{verbatim}
858
859\subsubsection*{Returns}
860
861The parameter $p$ must specify the reference number of some (active or
862inactive) subproblem, in which case the routine \verb|iet_get_up_node|
863returns the reference number of its parent subproblem. However, if the
864specified subproblem is the root of the tree and, therefore, has
865no parent, the routine returns zero.
866
867\subsection{glp\_ios\_node\_level---determine subproblem level}
868
869\subsubsection*{Synopsis}
870
871\begin{verbatim}
872int glp_ios_node_level(glp_tree *tree, int p);
873\end{verbatim}
874
875\subsubsection*{Returns}
876
877The routine \verb|glp_ios_node_level| returns the level of the
878subproblem,\linebreak whose reference number is $p$, in the
879branch-and-bound tree. (The root subproblem has level 0, and the level
880of 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}
887double glp_ios_node_bound(glp_tree *tree, int p);
888\end{verbatim}
889
890\subsubsection*{Returns}
891
892The 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
897The local bound for subproblem $p$ is an lower (minimization) or upper
898(maximization) bound for integer optimal solution to {\it this}
899subproblem (not to the original problem). This bound is local in the
900sense that only subproblems in the subtree rooted at node $p$ cannot
901have better integer feasible solutions.
902
903On creating a subproblem (due to the branching step) its local bound is
904inherited from its parent and then may get only stronger (never weaker).
905For the root subproblem its local bound is initially set to
906\verb|-DBL_MAX| (minimization) or \verb|+DBL_MAX| (maximization) and
907then improved as the root LP relaxation has been solved.
908
909Note that the local bound is not necessarily the optimal objective value
910to corresponding LP relaxation.
911
912\subsection{glp\_ios\_best\_node---find active subproblem with best
913local bound}
914
915\subsubsection*{Synopsis}
916
917\begin{verbatim}
918int glp_ios_best_node(glp_tree *tree);
919\end{verbatim}
920
921\subsubsection*{Returns}
922
923The routine \verb|glp_ios_best_node| returns the reference number of
924the active subproblem, whose local bound is best (i.e. smallest in case
925of minimization or largest in case of maximization). However, if the
926tree is empty, the routine returns zero.
927
928\subsubsection*{Comments}
929
930The best local bound is an lower (minimization) or upper (maximization)
931bound 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\\
940pool}
941
942\subsubsection*{Synopsis}
943
944\begin{verbatim}
945int glp_ios_pool_size(glp_tree *tree);
946\end{verbatim}
947
948\subsubsection*{Returns}
949
950The routine \verb|glp_ios_pool_size| returns the current size of the
951cut pool, that is, the number of cutting plane constraints currently
952added to it.
953
954\subsection{glp\_ios\_add\_row---add constraint to the cut pool}
955
956\subsubsection*{Synopsis}
957
958\begin{verbatim}
959int 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
966The routine \verb|glp_ios_add_row| adds specified row (cutting plane
967constraint) to the cut pool.
968
969The 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,$$
972where $J$ is a set of indices (ordinal numbers) of structural variables,
973$a_j$ are constraint coefficients, $x_j$ are structural variables, $b$
974is the right-hand side.
975
976The parameter \verb|name| specifies a symbolic name assigned to the
977constraint (1 up to 255 characters). If it is \verb|NULL| or an empty
978string, no name is assigned.
979
980The parameter \verb|klass| specifies the constraint class, which must
981be either zero or a number in the range from 101 to 200. The application
982may use this attribute to distinguish between cutting plane constraints
983of different classes.\footnote{Constraint classes numbered from 1 to 100
984are reserved for GLPK cutting plane generators.}
985
986The parameter \verb|flags| currently is not used and must be zero.
987
988Ordinal numbers of structural variables (i.e. column indices) $j\in J$
989and numerical values of corresponding constraint coefficients $a_j$ must
990be 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
994object. Coefficients with identical column indices are not allowed.
995Zero coefficients are allowed, however, they are ignored.
996
997The 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
1003The parameter \verb|rhs| specifies the right-hand side $b$.
1004
1005All cutting plane constraints in the cut pool are identified by their
1006ordinal numbers 1, 2, \dots, $size$, where $size$ is the current size
1007of the cut pool. New constraints are always added to the end of the cut
1008pool, thus, ordinal numbers of previously added constraints are not
1009changed.
1010
1011\subsubsection*{Returns}
1012
1013The routine \verb|glp_ios_add_row| returns the ordinal number of the
1014cutting 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 */
1023ind[1] = i, val[1] = 1.0;
1024ind[2] = j, val[2] = 1.0;
1025ind[3] = k, val[3] = 1.0;
1026glp_ios_add_row(tree, NULL, TRIANGLE_CUT, 0, 3, ind, val,
1027                GLP_UP, 1.0);
1028\end{verbatim}
1029
1030\subsubsection*{Comments}
1031
1032Cutting plane constraints added to the cut pool are intended to be then
1033added only to the {\it current} subproblem, so these constraints can be
1034globally as well as locally valid. However, adding a constraint to the
1035cut pool does not mean that it will be added to the current
1036subproblem---it depends on the solver's decision: if the constraint
1037seems to be efficient, it is moved from the pool to the current
1038subproblem, otherwise it is simply dropped.\footnote{Globally valid
1039constraints could be saved and then re-used for other subproblems, but
1040currently such feature is not implemented.}
1041
1042Normally, every time the callback routine is called for cut generation,
1043the cut pool is empty. On the other hand, the solver itself can generate
1044cutting plane constraints (like Gomory's or mixed integer rounding
1045cuts), 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}
1052void glp_ios_del_row(glp_tree *tree, int i);
1053\end{verbatim}
1054
1055\subsubsection*{Description}
1056
1057The routine \verb|glp_ios_del_row| deletes $i$-th row (cutting plane
1058constraint) from the cut pool, where $1\leq i\leq size$ is the ordinal
1059number of the constraint in the pool, $size$ is the current size of the
1060cut pool.
1061
1062Note that deleting a constraint from the cut pool leads to changing
1063ordinal numbers of other constraints remaining in the pool. New ordinal
1064numbers of the remaining constraints are assigned under assumption that
1065the original order of constraints is not changed. Let, for example,
1066there be four constraints $a$, $b$, $c$ and $d$ in the cut pool, which
1067have 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
1071To find the constraint to be deleted the routine \verb|glp_ios_del_row|
1072uses ``smart'' linear search, so it is recommended to remove constraints
1073in 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 */
1080while (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
1087pool}
1088
1089\subsubsection*{Synopsis}
1090
1091\begin{verbatim}
1092void glp_ios_clear_pool(glp_tree *tree);
1093\end{verbatim}
1094
1095\subsubsection*{Description}
1096
1097The routine \verb|glp_ios_clear_pool| makes the cut pool empty deleting
1098all existing rows (cutting plane constraints) from it.
1099
1100%* eof *%
Note: See TracBrowser for help on using the repository browser.