|
1 /* glpios.h (integer optimization suite) */ |
|
2 |
|
3 /*********************************************************************** |
|
4 * This code is part of GLPK (GNU Linear Programming Kit). |
|
5 * |
|
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, |
|
7 * 2009, 2010 Andrew Makhorin, Department for Applied Informatics, |
|
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved. |
|
9 * E-mail: <mao@gnu.org>. |
|
10 * |
|
11 * GLPK is free software: you can redistribute it and/or modify it |
|
12 * under the terms of the GNU General Public License as published by |
|
13 * the Free Software Foundation, either version 3 of the License, or |
|
14 * (at your option) any later version. |
|
15 * |
|
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT |
|
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
|
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public |
|
19 * License for more details. |
|
20 * |
|
21 * You should have received a copy of the GNU General Public License |
|
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>. |
|
23 ***********************************************************************/ |
|
24 |
|
25 #ifndef GLPIOS_H |
|
26 #define GLPIOS_H |
|
27 |
|
28 #define GLP_TREE_DEFINED |
|
29 typedef struct glp_tree glp_tree; |
|
30 |
|
31 #include "glpapi.h" |
|
32 |
|
33 typedef struct IOSLOT IOSLOT; |
|
34 typedef struct IOSNPD IOSNPD; |
|
35 typedef struct IOSBND IOSBND; |
|
36 typedef struct IOSTAT IOSTAT; |
|
37 typedef struct IOSROW IOSROW; |
|
38 typedef struct IOSAIJ IOSAIJ; |
|
39 typedef struct IOSPOOL IOSPOOL; |
|
40 typedef struct IOSCUT IOSCUT; |
|
41 |
|
42 struct glp_tree |
|
43 { /* branch-and-bound tree */ |
|
44 int magic; |
|
45 /* magic value used for debugging */ |
|
46 DMP *pool; |
|
47 /* memory pool to store all IOS components */ |
|
48 int n; |
|
49 /* number of columns (variables) */ |
|
50 /*--------------------------------------------------------------*/ |
|
51 /* problem components corresponding to the original MIP and its |
|
52 LP relaxation (used to restore the original problem object on |
|
53 exit from the solver) */ |
|
54 int orig_m; |
|
55 /* number of rows */ |
|
56 unsigned char *orig_type; /* uchar orig_type[1+orig_m+n]; */ |
|
57 /* types of all variables */ |
|
58 double *orig_lb; /* double orig_lb[1+orig_m+n]; */ |
|
59 /* lower bounds of all variables */ |
|
60 double *orig_ub; /* double orig_ub[1+orig_m+n]; */ |
|
61 /* upper bounds of all variables */ |
|
62 unsigned char *orig_stat; /* uchar orig_stat[1+orig_m+n]; */ |
|
63 /* statuses of all variables */ |
|
64 double *orig_prim; /* double orig_prim[1+orig_m+n]; */ |
|
65 /* primal values of all variables */ |
|
66 double *orig_dual; /* double orig_dual[1+orig_m+n]; */ |
|
67 /* dual values of all variables */ |
|
68 double orig_obj; |
|
69 /* optimal objective value for LP relaxation */ |
|
70 /*--------------------------------------------------------------*/ |
|
71 /* branch-and-bound tree */ |
|
72 int nslots; |
|
73 /* length of the array of slots (enlarged automatically) */ |
|
74 int avail; |
|
75 /* index of the first free slot; 0 means all slots are in use */ |
|
76 IOSLOT *slot; /* IOSLOT slot[1+nslots]; */ |
|
77 /* array of slots: |
|
78 slot[0] is not used; |
|
79 slot[p], 1 <= p <= nslots, either contains a pointer to some |
|
80 node of the branch-and-bound tree, in which case p is used on |
|
81 API level as the reference number of corresponding subproblem, |
|
82 or is free; all free slots are linked into single linked list; |
|
83 slot[1] always contains a pointer to the root node (it is free |
|
84 only if the tree is empty) */ |
|
85 IOSNPD *head; |
|
86 /* pointer to the head of the active list */ |
|
87 IOSNPD *tail; |
|
88 /* pointer to the tail of the active list */ |
|
89 /* the active list is a doubly linked list of active subproblems |
|
90 which correspond to leaves of the tree; all subproblems in the |
|
91 active list are ordered chronologically (each a new subproblem |
|
92 is always added to the tail of the list) */ |
|
93 int a_cnt; |
|
94 /* current number of active nodes (including the current one) */ |
|
95 int n_cnt; |
|
96 /* current number of all (active and inactive) nodes */ |
|
97 int t_cnt; |
|
98 /* total number of nodes including those which have been already |
|
99 removed from the tree; this count is increased by one whenever |
|
100 a new node is created and never decreased */ |
|
101 /*--------------------------------------------------------------*/ |
|
102 /* problem components corresponding to the root subproblem */ |
|
103 int root_m; |
|
104 /* number of rows */ |
|
105 unsigned char *root_type; /* uchar root_type[1+root_m+n]; */ |
|
106 /* types of all variables */ |
|
107 double *root_lb; /* double root_lb[1+root_m+n]; */ |
|
108 /* lower bounds of all variables */ |
|
109 double *root_ub; /* double root_ub[1+root_m+n]; */ |
|
110 /* upper bounds of all variables */ |
|
111 unsigned char *root_stat; /* uchar root_stat[1+root_m+n]; */ |
|
112 /* statuses of all variables */ |
|
113 /*--------------------------------------------------------------*/ |
|
114 /* current subproblem and its LP relaxation */ |
|
115 IOSNPD *curr; |
|
116 /* pointer to the current subproblem (which can be only active); |
|
117 NULL means the current subproblem does not exist */ |
|
118 glp_prob *mip; |
|
119 /* original problem object passed to the solver; if the current |
|
120 subproblem exists, its LP segment corresponds to LP relaxation |
|
121 of the current subproblem; if the current subproblem does not |
|
122 exist, its LP segment corresponds to LP relaxation of the root |
|
123 subproblem (note that the root subproblem may differ from the |
|
124 original MIP, because it may be preprocessed and/or may have |
|
125 additional rows) */ |
|
126 unsigned char *non_int; /* uchar non_int[1+n]; */ |
|
127 /* these column flags are set each time when LP relaxation of the |
|
128 current subproblem has been solved; |
|
129 non_int[0] is not used; |
|
130 non_int[j], 1 <= j <= n, is j-th column flag; if this flag is |
|
131 set, corresponding variable is required to be integer, but its |
|
132 value in basic solution is fractional */ |
|
133 /*--------------------------------------------------------------*/ |
|
134 /* problem components corresponding to the parent (predecessor) |
|
135 subproblem for the current subproblem; used to inspect changes |
|
136 on freezing the current subproblem */ |
|
137 int pred_m; |
|
138 /* number of rows */ |
|
139 int pred_max; |
|
140 /* length of the following four arrays (enlarged automatically), |
|
141 pred_max >= pred_m + n */ |
|
142 unsigned char *pred_type; /* uchar pred_type[1+pred_m+n]; */ |
|
143 /* types of all variables */ |
|
144 double *pred_lb; /* double pred_lb[1+pred_m+n]; */ |
|
145 /* lower bounds of all variables */ |
|
146 double *pred_ub; /* double pred_ub[1+pred_m+n]; */ |
|
147 /* upper bounds of all variables */ |
|
148 unsigned char *pred_stat; /* uchar pred_stat[1+pred_m+n]; */ |
|
149 /* statuses of all variables */ |
|
150 /****************************************************************/ |
|
151 /* built-in cut generators segment */ |
|
152 IOSPOOL *local; |
|
153 /* local cut pool */ |
|
154 void *mir_gen; |
|
155 /* pointer to working area used by the MIR cut generator */ |
|
156 void *clq_gen; |
|
157 /* pointer to working area used by the clique cut generator */ |
|
158 /*--------------------------------------------------------------*/ |
|
159 void *pcost; |
|
160 /* pointer to working area used on pseudocost branching */ |
|
161 int *iwrk; /* int iwrk[1+n]; */ |
|
162 /* working array */ |
|
163 double *dwrk; /* double dwrk[1+n]; */ |
|
164 /* working array */ |
|
165 /*--------------------------------------------------------------*/ |
|
166 /* control parameters and statistics */ |
|
167 const glp_iocp *parm; |
|
168 /* copy of control parameters passed to the solver */ |
|
169 glp_long tm_beg; |
|
170 /* starting time of the search, in seconds; the total time of the |
|
171 search is the difference between xtime() and tm_beg */ |
|
172 glp_long tm_lag; |
|
173 /* the most recent time, in seconds, at which the progress of the |
|
174 the search was displayed */ |
|
175 int sol_cnt; |
|
176 /* number of integer feasible solutions found */ |
|
177 /*--------------------------------------------------------------*/ |
|
178 /* advanced solver interface */ |
|
179 int reason; |
|
180 /* flag indicating the reason why the callback routine is being |
|
181 called (see glpk.h) */ |
|
182 int stop; |
|
183 /* flag indicating that the callback routine requires premature |
|
184 termination of the search */ |
|
185 int next_p; |
|
186 /* reference number of active subproblem selected to continue |
|
187 the search; 0 means no subproblem has been selected */ |
|
188 int reopt; |
|
189 /* flag indicating that the current LP relaxation needs to be |
|
190 re-optimized */ |
|
191 int reinv; |
|
192 /* flag indicating that some (non-active) rows were removed from |
|
193 the current LP relaxation, so if there no new rows appear, the |
|
194 basis must be re-factorized */ |
|
195 int br_var; |
|
196 /* the number of variable chosen to branch on */ |
|
197 int br_sel; |
|
198 /* flag indicating which branch (subproblem) is suggested to be |
|
199 selected to continue the search: |
|
200 GLP_DN_BRNCH - select down-branch |
|
201 GLP_UP_BRNCH - select up-branch |
|
202 GLP_NO_BRNCH - use general selection technique */ |
|
203 int child; |
|
204 /* subproblem reference number corresponding to br_sel */ |
|
205 }; |
|
206 |
|
207 struct IOSLOT |
|
208 { /* node subproblem slot */ |
|
209 IOSNPD *node; |
|
210 /* pointer to subproblem descriptor; NULL means free slot */ |
|
211 int next; |
|
212 /* index of another free slot (only if this slot is free) */ |
|
213 }; |
|
214 |
|
215 struct IOSNPD |
|
216 { /* node subproblem descriptor */ |
|
217 int p; |
|
218 /* subproblem reference number (it is the index to corresponding |
|
219 slot, i.e. slot[p] points to this descriptor) */ |
|
220 IOSNPD *up; |
|
221 /* pointer to the parent subproblem; NULL means this node is the |
|
222 root of the tree, in which case p = 1 */ |
|
223 int level; |
|
224 /* node level (the root node has level 0) */ |
|
225 int count; |
|
226 /* if count = 0, this subproblem is active; if count > 0, this |
|
227 subproblem is inactive, in which case count is the number of |
|
228 its child subproblems */ |
|
229 /* the following three linked lists are destroyed on reviving and |
|
230 built anew on freezing the subproblem: */ |
|
231 IOSBND *b_ptr; |
|
232 /* linked list of rows and columns of the parent subproblem whose |
|
233 types and bounds were changed */ |
|
234 IOSTAT *s_ptr; |
|
235 /* linked list of rows and columns of the parent subproblem whose |
|
236 statuses were changed */ |
|
237 IOSROW *r_ptr; |
|
238 /* linked list of rows (cuts) added to the parent subproblem */ |
|
239 int solved; |
|
240 /* how many times LP relaxation of this subproblem was solved; |
|
241 for inactive subproblem this count is always non-zero; |
|
242 for active subproblem, which is not current, this count may be |
|
243 non-zero, if the subproblem was temporarily suspended */ |
|
244 double lp_obj; |
|
245 /* optimal objective value to LP relaxation of this subproblem; |
|
246 on creating a subproblem this value is inherited from its |
|
247 parent; for the root subproblem, which has no parent, this |
|
248 value is initially set to -DBL_MAX (minimization) or +DBL_MAX |
|
249 (maximization); each time the subproblem is re-optimized, this |
|
250 value is appropriately changed */ |
|
251 double bound; |
|
252 /* local lower (minimization) or upper (maximization) bound for |
|
253 integer optimal solution to *this* subproblem; this bound is |
|
254 local in the sense that only subproblems in the subtree rooted |
|
255 at this node cannot have better integer feasible solutions; |
|
256 on creating a subproblem its local bound is inherited from its |
|
257 parent and then can be made stronger (never weaker); for the |
|
258 root subproblem its local bound is initially set to -DBL_MAX |
|
259 (minimization) or +DBL_MAX (maximization) and then improved as |
|
260 the root LP relaxation has been solved */ |
|
261 /* the following two quantities are defined only if LP relaxation |
|
262 of this subproblem was solved at least once (solved > 0): */ |
|
263 int ii_cnt; |
|
264 /* number of integer variables whose value in optimal solution to |
|
265 LP relaxation of this subproblem is fractional */ |
|
266 double ii_sum; |
|
267 /* sum of integer infeasibilities */ |
|
268 #if 1 /* 30/XI-2009 */ |
|
269 int changed; |
|
270 /* how many times this subproblem was re-formulated (by adding |
|
271 cutting plane constraints) */ |
|
272 #endif |
|
273 int br_var; |
|
274 /* ordinal number of branching variable, 1 <= br_var <= n, used |
|
275 to split this subproblem; 0 means that either this subproblem |
|
276 is active or branching was made on a constraint */ |
|
277 double br_val; |
|
278 /* (fractional) value of branching variable in optimal solution |
|
279 to final LP relaxation of this subproblem */ |
|
280 void *data; /* char data[tree->cb_size]; */ |
|
281 /* pointer to the application-specific data */ |
|
282 IOSNPD *temp; |
|
283 /* working pointer used by some routines */ |
|
284 IOSNPD *prev; |
|
285 /* pointer to previous subproblem in the active list */ |
|
286 IOSNPD *next; |
|
287 /* pointer to next subproblem in the active list */ |
|
288 }; |
|
289 |
|
290 struct IOSBND |
|
291 { /* bounds change entry */ |
|
292 int k; |
|
293 /* ordinal number of corresponding row (1 <= k <= m) or column |
|
294 (m+1 <= k <= m+n), where m and n are the number of rows and |
|
295 columns, resp., in the parent subproblem */ |
|
296 unsigned char type; |
|
297 /* new type */ |
|
298 double lb; |
|
299 /* new lower bound */ |
|
300 double ub; |
|
301 /* new upper bound */ |
|
302 IOSBND *next; |
|
303 /* pointer to next entry for the same subproblem */ |
|
304 }; |
|
305 |
|
306 struct IOSTAT |
|
307 { /* status change entry */ |
|
308 int k; |
|
309 /* ordinal number of corresponding row (1 <= k <= m) or column |
|
310 (m+1 <= k <= m+n), where m and n are the number of rows and |
|
311 columns, resp., in the parent subproblem */ |
|
312 unsigned char stat; |
|
313 /* new status */ |
|
314 IOSTAT *next; |
|
315 /* pointer to next entry for the same subproblem */ |
|
316 }; |
|
317 |
|
318 struct IOSROW |
|
319 { /* row (constraint) addition entry */ |
|
320 char *name; |
|
321 /* row name or NULL */ |
|
322 unsigned char origin; |
|
323 /* row origin flag (see glp_attr.origin) */ |
|
324 unsigned char klass; |
|
325 /* row class descriptor (see glp_attr.klass) */ |
|
326 unsigned char type; |
|
327 /* row type (GLP_LO, GLP_UP, etc.) */ |
|
328 double lb; |
|
329 /* row lower bound */ |
|
330 double ub; |
|
331 /* row upper bound */ |
|
332 IOSAIJ *ptr; |
|
333 /* pointer to the row coefficient list */ |
|
334 double rii; |
|
335 /* row scale factor */ |
|
336 unsigned char stat; |
|
337 /* row status (GLP_BS, GLP_NL, etc.) */ |
|
338 IOSROW *next; |
|
339 /* pointer to next entry for the same subproblem */ |
|
340 }; |
|
341 |
|
342 struct IOSAIJ |
|
343 { /* constraint coefficient */ |
|
344 int j; |
|
345 /* variable (column) number, 1 <= j <= n */ |
|
346 double val; |
|
347 /* non-zero coefficient value */ |
|
348 IOSAIJ *next; |
|
349 /* pointer to next coefficient for the same row */ |
|
350 }; |
|
351 |
|
352 struct IOSPOOL |
|
353 { /* cut pool */ |
|
354 int size; |
|
355 /* pool size = number of cuts in the pool */ |
|
356 IOSCUT *head; |
|
357 /* pointer to the first cut */ |
|
358 IOSCUT *tail; |
|
359 /* pointer to the last cut */ |
|
360 int ord; |
|
361 /* ordinal number of the current cut, 1 <= ord <= size */ |
|
362 IOSCUT *curr; |
|
363 /* pointer to the current cut */ |
|
364 }; |
|
365 |
|
366 struct IOSCUT |
|
367 { /* cut (cutting plane constraint) */ |
|
368 char *name; |
|
369 /* cut name or NULL */ |
|
370 unsigned char klass; |
|
371 /* cut class descriptor (see glp_attr.klass) */ |
|
372 IOSAIJ *ptr; |
|
373 /* pointer to the cut coefficient list */ |
|
374 unsigned char type; |
|
375 /* cut type: |
|
376 GLP_LO: sum a[j] * x[j] >= b |
|
377 GLP_UP: sum a[j] * x[j] <= b |
|
378 GLP_FX: sum a[j] * x[j] = b */ |
|
379 double rhs; |
|
380 /* cut right-hand side */ |
|
381 IOSCUT *prev; |
|
382 /* pointer to previous cut */ |
|
383 IOSCUT *next; |
|
384 /* pointer to next cut */ |
|
385 }; |
|
386 |
|
387 #define ios_create_tree _glp_ios_create_tree |
|
388 glp_tree *ios_create_tree(glp_prob *mip, const glp_iocp *parm); |
|
389 /* create branch-and-bound tree */ |
|
390 |
|
391 #define ios_revive_node _glp_ios_revive_node |
|
392 void ios_revive_node(glp_tree *tree, int p); |
|
393 /* revive specified subproblem */ |
|
394 |
|
395 #define ios_freeze_node _glp_ios_freeze_node |
|
396 void ios_freeze_node(glp_tree *tree); |
|
397 /* freeze current subproblem */ |
|
398 |
|
399 #define ios_clone_node _glp_ios_clone_node |
|
400 void ios_clone_node(glp_tree *tree, int p, int nnn, int ref[]); |
|
401 /* clone specified subproblem */ |
|
402 |
|
403 #define ios_delete_node _glp_ios_delete_node |
|
404 void ios_delete_node(glp_tree *tree, int p); |
|
405 /* delete specified subproblem */ |
|
406 |
|
407 #define ios_delete_tree _glp_ios_delete_tree |
|
408 void ios_delete_tree(glp_tree *tree); |
|
409 /* delete branch-and-bound tree */ |
|
410 |
|
411 #define ios_eval_degrad _glp_ios_eval_degrad |
|
412 void ios_eval_degrad(glp_tree *tree, int j, double *dn, double *up); |
|
413 /* estimate obj. degrad. for down- and up-branches */ |
|
414 |
|
415 #define ios_round_bound _glp_ios_round_bound |
|
416 double ios_round_bound(glp_tree *tree, double bound); |
|
417 /* improve local bound by rounding */ |
|
418 |
|
419 #define ios_is_hopeful _glp_ios_is_hopeful |
|
420 int ios_is_hopeful(glp_tree *tree, double bound); |
|
421 /* check if subproblem is hopeful */ |
|
422 |
|
423 #define ios_best_node _glp_ios_best_node |
|
424 int ios_best_node(glp_tree *tree); |
|
425 /* find active node with best local bound */ |
|
426 |
|
427 #define ios_relative_gap _glp_ios_relative_gap |
|
428 double ios_relative_gap(glp_tree *tree); |
|
429 /* compute relative mip gap */ |
|
430 |
|
431 #define ios_solve_node _glp_ios_solve_node |
|
432 int ios_solve_node(glp_tree *tree); |
|
433 /* solve LP relaxation of current subproblem */ |
|
434 |
|
435 #define ios_create_pool _glp_ios_create_pool |
|
436 IOSPOOL *ios_create_pool(glp_tree *tree); |
|
437 /* create cut pool */ |
|
438 |
|
439 #define ios_add_row _glp_ios_add_row |
|
440 int ios_add_row(glp_tree *tree, IOSPOOL *pool, |
|
441 const char *name, int klass, int flags, int len, const int ind[], |
|
442 const double val[], int type, double rhs); |
|
443 /* add row (constraint) to the cut pool */ |
|
444 |
|
445 #define ios_find_row _glp_ios_find_row |
|
446 IOSCUT *ios_find_row(IOSPOOL *pool, int i); |
|
447 /* find row (constraint) in the cut pool */ |
|
448 |
|
449 #define ios_del_row _glp_ios_del_row |
|
450 void ios_del_row(glp_tree *tree, IOSPOOL *pool, int i); |
|
451 /* remove row (constraint) from the cut pool */ |
|
452 |
|
453 #define ios_clear_pool _glp_ios_clear_pool |
|
454 void ios_clear_pool(glp_tree *tree, IOSPOOL *pool); |
|
455 /* remove all rows (constraints) from the cut pool */ |
|
456 |
|
457 #define ios_delete_pool _glp_ios_delete_pool |
|
458 void ios_delete_pool(glp_tree *tree, IOSPOOL *pool); |
|
459 /* delete cut pool */ |
|
460 |
|
461 #define ios_preprocess_node _glp_ios_preprocess_node |
|
462 int ios_preprocess_node(glp_tree *tree, int max_pass); |
|
463 /* preprocess current subproblem */ |
|
464 |
|
465 #define ios_driver _glp_ios_driver |
|
466 int ios_driver(glp_tree *tree); |
|
467 /* branch-and-bound driver */ |
|
468 |
|
469 /**********************************************************************/ |
|
470 |
|
471 typedef struct IOSVEC IOSVEC; |
|
472 |
|
473 struct IOSVEC |
|
474 { /* sparse vector v = (v[j]) */ |
|
475 int n; |
|
476 /* dimension, n >= 0 */ |
|
477 int nnz; |
|
478 /* number of non-zero components, 0 <= nnz <= n */ |
|
479 int *pos; /* int pos[1+n]; */ |
|
480 /* pos[j] = k, 1 <= j <= n, is position of (non-zero) v[j] in the |
|
481 arrays ind and val, where 1 <= k <= nnz; pos[j] = 0 means that |
|
482 v[j] is structural zero */ |
|
483 int *ind; /* int ind[1+n]; */ |
|
484 /* ind[k] = j, 1 <= k <= nnz, is index of v[j] */ |
|
485 double *val; /* double val[1+n]; */ |
|
486 /* val[k], 1 <= k <= nnz, is a numeric value of v[j] */ |
|
487 }; |
|
488 |
|
489 #define ios_create_vec _glp_ios_create_vec |
|
490 IOSVEC *ios_create_vec(int n); |
|
491 /* create sparse vector */ |
|
492 |
|
493 #define ios_check_vec _glp_ios_check_vec |
|
494 void ios_check_vec(IOSVEC *v); |
|
495 /* check that sparse vector has correct representation */ |
|
496 |
|
497 #define ios_get_vj _glp_ios_get_vj |
|
498 double ios_get_vj(IOSVEC *v, int j); |
|
499 /* retrieve component of sparse vector */ |
|
500 |
|
501 #define ios_set_vj _glp_ios_set_vj |
|
502 void ios_set_vj(IOSVEC *v, int j, double val); |
|
503 /* set/change component of sparse vector */ |
|
504 |
|
505 #define ios_clear_vec _glp_ios_clear_vec |
|
506 void ios_clear_vec(IOSVEC *v); |
|
507 /* set all components of sparse vector to zero */ |
|
508 |
|
509 #define ios_clean_vec _glp_ios_clean_vec |
|
510 void ios_clean_vec(IOSVEC *v, double eps); |
|
511 /* remove zero or small components from sparse vector */ |
|
512 |
|
513 #define ios_copy_vec _glp_ios_copy_vec |
|
514 void ios_copy_vec(IOSVEC *x, IOSVEC *y); |
|
515 /* copy sparse vector (x := y) */ |
|
516 |
|
517 #define ios_linear_comb _glp_ios_linear_comb |
|
518 void ios_linear_comb(IOSVEC *x, double a, IOSVEC *y); |
|
519 /* compute linear combination (x := x + a * y) */ |
|
520 |
|
521 #define ios_delete_vec _glp_ios_delete_vec |
|
522 void ios_delete_vec(IOSVEC *v); |
|
523 /* delete sparse vector */ |
|
524 |
|
525 /**********************************************************************/ |
|
526 |
|
527 #define ios_gmi_gen _glp_ios_gmi_gen |
|
528 void ios_gmi_gen(glp_tree *tree); |
|
529 /* generate Gomory's mixed integer cuts */ |
|
530 |
|
531 #define ios_mir_init _glp_ios_mir_init |
|
532 void *ios_mir_init(glp_tree *tree); |
|
533 /* initialize MIR cut generator */ |
|
534 |
|
535 #define ios_mir_gen _glp_ios_mir_gen |
|
536 void ios_mir_gen(glp_tree *tree, void *gen); |
|
537 /* generate MIR cuts */ |
|
538 |
|
539 #define ios_mir_term _glp_ios_mir_term |
|
540 void ios_mir_term(void *gen); |
|
541 /* terminate MIR cut generator */ |
|
542 |
|
543 #define ios_cov_gen _glp_ios_cov_gen |
|
544 void ios_cov_gen(glp_tree *tree); |
|
545 /* generate mixed cover cuts */ |
|
546 |
|
547 #define ios_clq_init _glp_ios_clq_init |
|
548 void *ios_clq_init(glp_tree *tree); |
|
549 /* initialize clique cut generator */ |
|
550 |
|
551 #define ios_clq_gen _glp_ios_clq_gen |
|
552 void ios_clq_gen(glp_tree *tree, void *gen); |
|
553 /* generate clique cuts */ |
|
554 |
|
555 #define ios_clq_term _glp_ios_clq_term |
|
556 void ios_clq_term(void *gen); |
|
557 /* terminate clique cut generator */ |
|
558 |
|
559 #define ios_pcost_init _glp_ios_pcost_init |
|
560 void *ios_pcost_init(glp_tree *tree); |
|
561 /* initialize working data used on pseudocost branching */ |
|
562 |
|
563 #define ios_pcost_branch _glp_ios_pcost_branch |
|
564 int ios_pcost_branch(glp_tree *T, int *next); |
|
565 /* choose branching variable with pseudocost branching */ |
|
566 |
|
567 #define ios_pcost_update _glp_ios_pcost_update |
|
568 void ios_pcost_update(glp_tree *tree); |
|
569 /* update history information for pseudocost branching */ |
|
570 |
|
571 #define ios_pcost_free _glp_ios_pcost_free |
|
572 void ios_pcost_free(glp_tree *tree); |
|
573 /* free working area used on pseudocost branching */ |
|
574 |
|
575 #define ios_feas_pump _glp_ios_feas_pump |
|
576 void ios_feas_pump(glp_tree *T); |
|
577 /* feasibility pump heuristic */ |
|
578 |
|
579 #define ios_process_cuts _glp_ios_process_cuts |
|
580 void ios_process_cuts(glp_tree *T); |
|
581 /* process cuts stored in the local cut pool */ |
|
582 |
|
583 #define ios_choose_node _glp_ios_choose_node |
|
584 int ios_choose_node(glp_tree *T); |
|
585 /* select subproblem to continue the search */ |
|
586 |
|
587 #define ios_choose_var _glp_ios_choose_var |
|
588 int ios_choose_var(glp_tree *T, int *next); |
|
589 /* select variable to branch on */ |
|
590 |
|
591 #endif |
|
592 |
|
593 /* eof */ |