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