1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpios.h Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,593 @@
1.4 +/* glpios.h (integer optimization suite) */
1.5 +
1.6 +/***********************************************************************
1.7 +* This code is part of GLPK (GNU Linear Programming Kit).
1.8 +*
1.9 +* Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
1.10 +* 2009, 2010 Andrew Makhorin, Department for Applied Informatics,
1.11 +* Moscow Aviation Institute, Moscow, Russia. All rights reserved.
1.12 +* E-mail: <mao@gnu.org>.
1.13 +*
1.14 +* GLPK is free software: you can redistribute it and/or modify it
1.15 +* under the terms of the GNU General Public License as published by
1.16 +* the Free Software Foundation, either version 3 of the License, or
1.17 +* (at your option) any later version.
1.18 +*
1.19 +* GLPK is distributed in the hope that it will be useful, but WITHOUT
1.20 +* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
1.21 +* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
1.22 +* License for more details.
1.23 +*
1.24 +* You should have received a copy of the GNU General Public License
1.25 +* along with GLPK. If not, see <http://www.gnu.org/licenses/>.
1.26 +***********************************************************************/
1.27 +
1.28 +#ifndef GLPIOS_H
1.29 +#define GLPIOS_H
1.30 +
1.31 +#define GLP_TREE_DEFINED
1.32 +typedef struct glp_tree glp_tree;
1.33 +
1.34 +#include "glpapi.h"
1.35 +
1.36 +typedef struct IOSLOT IOSLOT;
1.37 +typedef struct IOSNPD IOSNPD;
1.38 +typedef struct IOSBND IOSBND;
1.39 +typedef struct IOSTAT IOSTAT;
1.40 +typedef struct IOSROW IOSROW;
1.41 +typedef struct IOSAIJ IOSAIJ;
1.42 +typedef struct IOSPOOL IOSPOOL;
1.43 +typedef struct IOSCUT IOSCUT;
1.44 +
1.45 +struct glp_tree
1.46 +{ /* branch-and-bound tree */
1.47 + int magic;
1.48 + /* magic value used for debugging */
1.49 + DMP *pool;
1.50 + /* memory pool to store all IOS components */
1.51 + int n;
1.52 + /* number of columns (variables) */
1.53 + /*--------------------------------------------------------------*/
1.54 + /* problem components corresponding to the original MIP and its
1.55 + LP relaxation (used to restore the original problem object on
1.56 + exit from the solver) */
1.57 + int orig_m;
1.58 + /* number of rows */
1.59 + unsigned char *orig_type; /* uchar orig_type[1+orig_m+n]; */
1.60 + /* types of all variables */
1.61 + double *orig_lb; /* double orig_lb[1+orig_m+n]; */
1.62 + /* lower bounds of all variables */
1.63 + double *orig_ub; /* double orig_ub[1+orig_m+n]; */
1.64 + /* upper bounds of all variables */
1.65 + unsigned char *orig_stat; /* uchar orig_stat[1+orig_m+n]; */
1.66 + /* statuses of all variables */
1.67 + double *orig_prim; /* double orig_prim[1+orig_m+n]; */
1.68 + /* primal values of all variables */
1.69 + double *orig_dual; /* double orig_dual[1+orig_m+n]; */
1.70 + /* dual values of all variables */
1.71 + double orig_obj;
1.72 + /* optimal objective value for LP relaxation */
1.73 + /*--------------------------------------------------------------*/
1.74 + /* branch-and-bound tree */
1.75 + int nslots;
1.76 + /* length of the array of slots (enlarged automatically) */
1.77 + int avail;
1.78 + /* index of the first free slot; 0 means all slots are in use */
1.79 + IOSLOT *slot; /* IOSLOT slot[1+nslots]; */
1.80 + /* array of slots:
1.81 + slot[0] is not used;
1.82 + slot[p], 1 <= p <= nslots, either contains a pointer to some
1.83 + node of the branch-and-bound tree, in which case p is used on
1.84 + API level as the reference number of corresponding subproblem,
1.85 + or is free; all free slots are linked into single linked list;
1.86 + slot[1] always contains a pointer to the root node (it is free
1.87 + only if the tree is empty) */
1.88 + IOSNPD *head;
1.89 + /* pointer to the head of the active list */
1.90 + IOSNPD *tail;
1.91 + /* pointer to the tail of the active list */
1.92 + /* the active list is a doubly linked list of active subproblems
1.93 + which correspond to leaves of the tree; all subproblems in the
1.94 + active list are ordered chronologically (each a new subproblem
1.95 + is always added to the tail of the list) */
1.96 + int a_cnt;
1.97 + /* current number of active nodes (including the current one) */
1.98 + int n_cnt;
1.99 + /* current number of all (active and inactive) nodes */
1.100 + int t_cnt;
1.101 + /* total number of nodes including those which have been already
1.102 + removed from the tree; this count is increased by one whenever
1.103 + a new node is created and never decreased */
1.104 + /*--------------------------------------------------------------*/
1.105 + /* problem components corresponding to the root subproblem */
1.106 + int root_m;
1.107 + /* number of rows */
1.108 + unsigned char *root_type; /* uchar root_type[1+root_m+n]; */
1.109 + /* types of all variables */
1.110 + double *root_lb; /* double root_lb[1+root_m+n]; */
1.111 + /* lower bounds of all variables */
1.112 + double *root_ub; /* double root_ub[1+root_m+n]; */
1.113 + /* upper bounds of all variables */
1.114 + unsigned char *root_stat; /* uchar root_stat[1+root_m+n]; */
1.115 + /* statuses of all variables */
1.116 + /*--------------------------------------------------------------*/
1.117 + /* current subproblem and its LP relaxation */
1.118 + IOSNPD *curr;
1.119 + /* pointer to the current subproblem (which can be only active);
1.120 + NULL means the current subproblem does not exist */
1.121 + glp_prob *mip;
1.122 + /* original problem object passed to the solver; if the current
1.123 + subproblem exists, its LP segment corresponds to LP relaxation
1.124 + of the current subproblem; if the current subproblem does not
1.125 + exist, its LP segment corresponds to LP relaxation of the root
1.126 + subproblem (note that the root subproblem may differ from the
1.127 + original MIP, because it may be preprocessed and/or may have
1.128 + additional rows) */
1.129 + unsigned char *non_int; /* uchar non_int[1+n]; */
1.130 + /* these column flags are set each time when LP relaxation of the
1.131 + current subproblem has been solved;
1.132 + non_int[0] is not used;
1.133 + non_int[j], 1 <= j <= n, is j-th column flag; if this flag is
1.134 + set, corresponding variable is required to be integer, but its
1.135 + value in basic solution is fractional */
1.136 + /*--------------------------------------------------------------*/
1.137 + /* problem components corresponding to the parent (predecessor)
1.138 + subproblem for the current subproblem; used to inspect changes
1.139 + on freezing the current subproblem */
1.140 + int pred_m;
1.141 + /* number of rows */
1.142 + int pred_max;
1.143 + /* length of the following four arrays (enlarged automatically),
1.144 + pred_max >= pred_m + n */
1.145 + unsigned char *pred_type; /* uchar pred_type[1+pred_m+n]; */
1.146 + /* types of all variables */
1.147 + double *pred_lb; /* double pred_lb[1+pred_m+n]; */
1.148 + /* lower bounds of all variables */
1.149 + double *pred_ub; /* double pred_ub[1+pred_m+n]; */
1.150 + /* upper bounds of all variables */
1.151 + unsigned char *pred_stat; /* uchar pred_stat[1+pred_m+n]; */
1.152 + /* statuses of all variables */
1.153 + /****************************************************************/
1.154 + /* built-in cut generators segment */
1.155 + IOSPOOL *local;
1.156 + /* local cut pool */
1.157 + void *mir_gen;
1.158 + /* pointer to working area used by the MIR cut generator */
1.159 + void *clq_gen;
1.160 + /* pointer to working area used by the clique cut generator */
1.161 + /*--------------------------------------------------------------*/
1.162 + void *pcost;
1.163 + /* pointer to working area used on pseudocost branching */
1.164 + int *iwrk; /* int iwrk[1+n]; */
1.165 + /* working array */
1.166 + double *dwrk; /* double dwrk[1+n]; */
1.167 + /* working array */
1.168 + /*--------------------------------------------------------------*/
1.169 + /* control parameters and statistics */
1.170 + const glp_iocp *parm;
1.171 + /* copy of control parameters passed to the solver */
1.172 + glp_long tm_beg;
1.173 + /* starting time of the search, in seconds; the total time of the
1.174 + search is the difference between xtime() and tm_beg */
1.175 + glp_long tm_lag;
1.176 + /* the most recent time, in seconds, at which the progress of the
1.177 + the search was displayed */
1.178 + int sol_cnt;
1.179 + /* number of integer feasible solutions found */
1.180 + /*--------------------------------------------------------------*/
1.181 + /* advanced solver interface */
1.182 + int reason;
1.183 + /* flag indicating the reason why the callback routine is being
1.184 + called (see glpk.h) */
1.185 + int stop;
1.186 + /* flag indicating that the callback routine requires premature
1.187 + termination of the search */
1.188 + int next_p;
1.189 + /* reference number of active subproblem selected to continue
1.190 + the search; 0 means no subproblem has been selected */
1.191 + int reopt;
1.192 + /* flag indicating that the current LP relaxation needs to be
1.193 + re-optimized */
1.194 + int reinv;
1.195 + /* flag indicating that some (non-active) rows were removed from
1.196 + the current LP relaxation, so if there no new rows appear, the
1.197 + basis must be re-factorized */
1.198 + int br_var;
1.199 + /* the number of variable chosen to branch on */
1.200 + int br_sel;
1.201 + /* flag indicating which branch (subproblem) is suggested to be
1.202 + selected to continue the search:
1.203 + GLP_DN_BRNCH - select down-branch
1.204 + GLP_UP_BRNCH - select up-branch
1.205 + GLP_NO_BRNCH - use general selection technique */
1.206 + int child;
1.207 + /* subproblem reference number corresponding to br_sel */
1.208 +};
1.209 +
1.210 +struct IOSLOT
1.211 +{ /* node subproblem slot */
1.212 + IOSNPD *node;
1.213 + /* pointer to subproblem descriptor; NULL means free slot */
1.214 + int next;
1.215 + /* index of another free slot (only if this slot is free) */
1.216 +};
1.217 +
1.218 +struct IOSNPD
1.219 +{ /* node subproblem descriptor */
1.220 + int p;
1.221 + /* subproblem reference number (it is the index to corresponding
1.222 + slot, i.e. slot[p] points to this descriptor) */
1.223 + IOSNPD *up;
1.224 + /* pointer to the parent subproblem; NULL means this node is the
1.225 + root of the tree, in which case p = 1 */
1.226 + int level;
1.227 + /* node level (the root node has level 0) */
1.228 + int count;
1.229 + /* if count = 0, this subproblem is active; if count > 0, this
1.230 + subproblem is inactive, in which case count is the number of
1.231 + its child subproblems */
1.232 + /* the following three linked lists are destroyed on reviving and
1.233 + built anew on freezing the subproblem: */
1.234 + IOSBND *b_ptr;
1.235 + /* linked list of rows and columns of the parent subproblem whose
1.236 + types and bounds were changed */
1.237 + IOSTAT *s_ptr;
1.238 + /* linked list of rows and columns of the parent subproblem whose
1.239 + statuses were changed */
1.240 + IOSROW *r_ptr;
1.241 + /* linked list of rows (cuts) added to the parent subproblem */
1.242 + int solved;
1.243 + /* how many times LP relaxation of this subproblem was solved;
1.244 + for inactive subproblem this count is always non-zero;
1.245 + for active subproblem, which is not current, this count may be
1.246 + non-zero, if the subproblem was temporarily suspended */
1.247 + double lp_obj;
1.248 + /* optimal objective value to LP relaxation of this subproblem;
1.249 + on creating a subproblem this value is inherited from its
1.250 + parent; for the root subproblem, which has no parent, this
1.251 + value is initially set to -DBL_MAX (minimization) or +DBL_MAX
1.252 + (maximization); each time the subproblem is re-optimized, this
1.253 + value is appropriately changed */
1.254 + double bound;
1.255 + /* local lower (minimization) or upper (maximization) bound for
1.256 + integer optimal solution to *this* subproblem; this bound is
1.257 + local in the sense that only subproblems in the subtree rooted
1.258 + at this node cannot have better integer feasible solutions;
1.259 + on creating a subproblem its local bound is inherited from its
1.260 + parent and then can be made stronger (never weaker); for the
1.261 + root subproblem its local bound is initially set to -DBL_MAX
1.262 + (minimization) or +DBL_MAX (maximization) and then improved as
1.263 + the root LP relaxation has been solved */
1.264 + /* the following two quantities are defined only if LP relaxation
1.265 + of this subproblem was solved at least once (solved > 0): */
1.266 + int ii_cnt;
1.267 + /* number of integer variables whose value in optimal solution to
1.268 + LP relaxation of this subproblem is fractional */
1.269 + double ii_sum;
1.270 + /* sum of integer infeasibilities */
1.271 +#if 1 /* 30/XI-2009 */
1.272 + int changed;
1.273 + /* how many times this subproblem was re-formulated (by adding
1.274 + cutting plane constraints) */
1.275 +#endif
1.276 + int br_var;
1.277 + /* ordinal number of branching variable, 1 <= br_var <= n, used
1.278 + to split this subproblem; 0 means that either this subproblem
1.279 + is active or branching was made on a constraint */
1.280 + double br_val;
1.281 + /* (fractional) value of branching variable in optimal solution
1.282 + to final LP relaxation of this subproblem */
1.283 + void *data; /* char data[tree->cb_size]; */
1.284 + /* pointer to the application-specific data */
1.285 + IOSNPD *temp;
1.286 + /* working pointer used by some routines */
1.287 + IOSNPD *prev;
1.288 + /* pointer to previous subproblem in the active list */
1.289 + IOSNPD *next;
1.290 + /* pointer to next subproblem in the active list */
1.291 +};
1.292 +
1.293 +struct IOSBND
1.294 +{ /* bounds change entry */
1.295 + int k;
1.296 + /* ordinal number of corresponding row (1 <= k <= m) or column
1.297 + (m+1 <= k <= m+n), where m and n are the number of rows and
1.298 + columns, resp., in the parent subproblem */
1.299 + unsigned char type;
1.300 + /* new type */
1.301 + double lb;
1.302 + /* new lower bound */
1.303 + double ub;
1.304 + /* new upper bound */
1.305 + IOSBND *next;
1.306 + /* pointer to next entry for the same subproblem */
1.307 +};
1.308 +
1.309 +struct IOSTAT
1.310 +{ /* status change entry */
1.311 + int k;
1.312 + /* ordinal number of corresponding row (1 <= k <= m) or column
1.313 + (m+1 <= k <= m+n), where m and n are the number of rows and
1.314 + columns, resp., in the parent subproblem */
1.315 + unsigned char stat;
1.316 + /* new status */
1.317 + IOSTAT *next;
1.318 + /* pointer to next entry for the same subproblem */
1.319 +};
1.320 +
1.321 +struct IOSROW
1.322 +{ /* row (constraint) addition entry */
1.323 + char *name;
1.324 + /* row name or NULL */
1.325 + unsigned char origin;
1.326 + /* row origin flag (see glp_attr.origin) */
1.327 + unsigned char klass;
1.328 + /* row class descriptor (see glp_attr.klass) */
1.329 + unsigned char type;
1.330 + /* row type (GLP_LO, GLP_UP, etc.) */
1.331 + double lb;
1.332 + /* row lower bound */
1.333 + double ub;
1.334 + /* row upper bound */
1.335 + IOSAIJ *ptr;
1.336 + /* pointer to the row coefficient list */
1.337 + double rii;
1.338 + /* row scale factor */
1.339 + unsigned char stat;
1.340 + /* row status (GLP_BS, GLP_NL, etc.) */
1.341 + IOSROW *next;
1.342 + /* pointer to next entry for the same subproblem */
1.343 +};
1.344 +
1.345 +struct IOSAIJ
1.346 +{ /* constraint coefficient */
1.347 + int j;
1.348 + /* variable (column) number, 1 <= j <= n */
1.349 + double val;
1.350 + /* non-zero coefficient value */
1.351 + IOSAIJ *next;
1.352 + /* pointer to next coefficient for the same row */
1.353 +};
1.354 +
1.355 +struct IOSPOOL
1.356 +{ /* cut pool */
1.357 + int size;
1.358 + /* pool size = number of cuts in the pool */
1.359 + IOSCUT *head;
1.360 + /* pointer to the first cut */
1.361 + IOSCUT *tail;
1.362 + /* pointer to the last cut */
1.363 + int ord;
1.364 + /* ordinal number of the current cut, 1 <= ord <= size */
1.365 + IOSCUT *curr;
1.366 + /* pointer to the current cut */
1.367 +};
1.368 +
1.369 +struct IOSCUT
1.370 +{ /* cut (cutting plane constraint) */
1.371 + char *name;
1.372 + /* cut name or NULL */
1.373 + unsigned char klass;
1.374 + /* cut class descriptor (see glp_attr.klass) */
1.375 + IOSAIJ *ptr;
1.376 + /* pointer to the cut coefficient list */
1.377 + unsigned char type;
1.378 + /* cut type:
1.379 + GLP_LO: sum a[j] * x[j] >= b
1.380 + GLP_UP: sum a[j] * x[j] <= b
1.381 + GLP_FX: sum a[j] * x[j] = b */
1.382 + double rhs;
1.383 + /* cut right-hand side */
1.384 + IOSCUT *prev;
1.385 + /* pointer to previous cut */
1.386 + IOSCUT *next;
1.387 + /* pointer to next cut */
1.388 +};
1.389 +
1.390 +#define ios_create_tree _glp_ios_create_tree
1.391 +glp_tree *ios_create_tree(glp_prob *mip, const glp_iocp *parm);
1.392 +/* create branch-and-bound tree */
1.393 +
1.394 +#define ios_revive_node _glp_ios_revive_node
1.395 +void ios_revive_node(glp_tree *tree, int p);
1.396 +/* revive specified subproblem */
1.397 +
1.398 +#define ios_freeze_node _glp_ios_freeze_node
1.399 +void ios_freeze_node(glp_tree *tree);
1.400 +/* freeze current subproblem */
1.401 +
1.402 +#define ios_clone_node _glp_ios_clone_node
1.403 +void ios_clone_node(glp_tree *tree, int p, int nnn, int ref[]);
1.404 +/* clone specified subproblem */
1.405 +
1.406 +#define ios_delete_node _glp_ios_delete_node
1.407 +void ios_delete_node(glp_tree *tree, int p);
1.408 +/* delete specified subproblem */
1.409 +
1.410 +#define ios_delete_tree _glp_ios_delete_tree
1.411 +void ios_delete_tree(glp_tree *tree);
1.412 +/* delete branch-and-bound tree */
1.413 +
1.414 +#define ios_eval_degrad _glp_ios_eval_degrad
1.415 +void ios_eval_degrad(glp_tree *tree, int j, double *dn, double *up);
1.416 +/* estimate obj. degrad. for down- and up-branches */
1.417 +
1.418 +#define ios_round_bound _glp_ios_round_bound
1.419 +double ios_round_bound(glp_tree *tree, double bound);
1.420 +/* improve local bound by rounding */
1.421 +
1.422 +#define ios_is_hopeful _glp_ios_is_hopeful
1.423 +int ios_is_hopeful(glp_tree *tree, double bound);
1.424 +/* check if subproblem is hopeful */
1.425 +
1.426 +#define ios_best_node _glp_ios_best_node
1.427 +int ios_best_node(glp_tree *tree);
1.428 +/* find active node with best local bound */
1.429 +
1.430 +#define ios_relative_gap _glp_ios_relative_gap
1.431 +double ios_relative_gap(glp_tree *tree);
1.432 +/* compute relative mip gap */
1.433 +
1.434 +#define ios_solve_node _glp_ios_solve_node
1.435 +int ios_solve_node(glp_tree *tree);
1.436 +/* solve LP relaxation of current subproblem */
1.437 +
1.438 +#define ios_create_pool _glp_ios_create_pool
1.439 +IOSPOOL *ios_create_pool(glp_tree *tree);
1.440 +/* create cut pool */
1.441 +
1.442 +#define ios_add_row _glp_ios_add_row
1.443 +int ios_add_row(glp_tree *tree, IOSPOOL *pool,
1.444 + const char *name, int klass, int flags, int len, const int ind[],
1.445 + const double val[], int type, double rhs);
1.446 +/* add row (constraint) to the cut pool */
1.447 +
1.448 +#define ios_find_row _glp_ios_find_row
1.449 +IOSCUT *ios_find_row(IOSPOOL *pool, int i);
1.450 +/* find row (constraint) in the cut pool */
1.451 +
1.452 +#define ios_del_row _glp_ios_del_row
1.453 +void ios_del_row(glp_tree *tree, IOSPOOL *pool, int i);
1.454 +/* remove row (constraint) from the cut pool */
1.455 +
1.456 +#define ios_clear_pool _glp_ios_clear_pool
1.457 +void ios_clear_pool(glp_tree *tree, IOSPOOL *pool);
1.458 +/* remove all rows (constraints) from the cut pool */
1.459 +
1.460 +#define ios_delete_pool _glp_ios_delete_pool
1.461 +void ios_delete_pool(glp_tree *tree, IOSPOOL *pool);
1.462 +/* delete cut pool */
1.463 +
1.464 +#define ios_preprocess_node _glp_ios_preprocess_node
1.465 +int ios_preprocess_node(glp_tree *tree, int max_pass);
1.466 +/* preprocess current subproblem */
1.467 +
1.468 +#define ios_driver _glp_ios_driver
1.469 +int ios_driver(glp_tree *tree);
1.470 +/* branch-and-bound driver */
1.471 +
1.472 +/**********************************************************************/
1.473 +
1.474 +typedef struct IOSVEC IOSVEC;
1.475 +
1.476 +struct IOSVEC
1.477 +{ /* sparse vector v = (v[j]) */
1.478 + int n;
1.479 + /* dimension, n >= 0 */
1.480 + int nnz;
1.481 + /* number of non-zero components, 0 <= nnz <= n */
1.482 + int *pos; /* int pos[1+n]; */
1.483 + /* pos[j] = k, 1 <= j <= n, is position of (non-zero) v[j] in the
1.484 + arrays ind and val, where 1 <= k <= nnz; pos[j] = 0 means that
1.485 + v[j] is structural zero */
1.486 + int *ind; /* int ind[1+n]; */
1.487 + /* ind[k] = j, 1 <= k <= nnz, is index of v[j] */
1.488 + double *val; /* double val[1+n]; */
1.489 + /* val[k], 1 <= k <= nnz, is a numeric value of v[j] */
1.490 +};
1.491 +
1.492 +#define ios_create_vec _glp_ios_create_vec
1.493 +IOSVEC *ios_create_vec(int n);
1.494 +/* create sparse vector */
1.495 +
1.496 +#define ios_check_vec _glp_ios_check_vec
1.497 +void ios_check_vec(IOSVEC *v);
1.498 +/* check that sparse vector has correct representation */
1.499 +
1.500 +#define ios_get_vj _glp_ios_get_vj
1.501 +double ios_get_vj(IOSVEC *v, int j);
1.502 +/* retrieve component of sparse vector */
1.503 +
1.504 +#define ios_set_vj _glp_ios_set_vj
1.505 +void ios_set_vj(IOSVEC *v, int j, double val);
1.506 +/* set/change component of sparse vector */
1.507 +
1.508 +#define ios_clear_vec _glp_ios_clear_vec
1.509 +void ios_clear_vec(IOSVEC *v);
1.510 +/* set all components of sparse vector to zero */
1.511 +
1.512 +#define ios_clean_vec _glp_ios_clean_vec
1.513 +void ios_clean_vec(IOSVEC *v, double eps);
1.514 +/* remove zero or small components from sparse vector */
1.515 +
1.516 +#define ios_copy_vec _glp_ios_copy_vec
1.517 +void ios_copy_vec(IOSVEC *x, IOSVEC *y);
1.518 +/* copy sparse vector (x := y) */
1.519 +
1.520 +#define ios_linear_comb _glp_ios_linear_comb
1.521 +void ios_linear_comb(IOSVEC *x, double a, IOSVEC *y);
1.522 +/* compute linear combination (x := x + a * y) */
1.523 +
1.524 +#define ios_delete_vec _glp_ios_delete_vec
1.525 +void ios_delete_vec(IOSVEC *v);
1.526 +/* delete sparse vector */
1.527 +
1.528 +/**********************************************************************/
1.529 +
1.530 +#define ios_gmi_gen _glp_ios_gmi_gen
1.531 +void ios_gmi_gen(glp_tree *tree);
1.532 +/* generate Gomory's mixed integer cuts */
1.533 +
1.534 +#define ios_mir_init _glp_ios_mir_init
1.535 +void *ios_mir_init(glp_tree *tree);
1.536 +/* initialize MIR cut generator */
1.537 +
1.538 +#define ios_mir_gen _glp_ios_mir_gen
1.539 +void ios_mir_gen(glp_tree *tree, void *gen);
1.540 +/* generate MIR cuts */
1.541 +
1.542 +#define ios_mir_term _glp_ios_mir_term
1.543 +void ios_mir_term(void *gen);
1.544 +/* terminate MIR cut generator */
1.545 +
1.546 +#define ios_cov_gen _glp_ios_cov_gen
1.547 +void ios_cov_gen(glp_tree *tree);
1.548 +/* generate mixed cover cuts */
1.549 +
1.550 +#define ios_clq_init _glp_ios_clq_init
1.551 +void *ios_clq_init(glp_tree *tree);
1.552 +/* initialize clique cut generator */
1.553 +
1.554 +#define ios_clq_gen _glp_ios_clq_gen
1.555 +void ios_clq_gen(glp_tree *tree, void *gen);
1.556 +/* generate clique cuts */
1.557 +
1.558 +#define ios_clq_term _glp_ios_clq_term
1.559 +void ios_clq_term(void *gen);
1.560 +/* terminate clique cut generator */
1.561 +
1.562 +#define ios_pcost_init _glp_ios_pcost_init
1.563 +void *ios_pcost_init(glp_tree *tree);
1.564 +/* initialize working data used on pseudocost branching */
1.565 +
1.566 +#define ios_pcost_branch _glp_ios_pcost_branch
1.567 +int ios_pcost_branch(glp_tree *T, int *next);
1.568 +/* choose branching variable with pseudocost branching */
1.569 +
1.570 +#define ios_pcost_update _glp_ios_pcost_update
1.571 +void ios_pcost_update(glp_tree *tree);
1.572 +/* update history information for pseudocost branching */
1.573 +
1.574 +#define ios_pcost_free _glp_ios_pcost_free
1.575 +void ios_pcost_free(glp_tree *tree);
1.576 +/* free working area used on pseudocost branching */
1.577 +
1.578 +#define ios_feas_pump _glp_ios_feas_pump
1.579 +void ios_feas_pump(glp_tree *T);
1.580 +/* feasibility pump heuristic */
1.581 +
1.582 +#define ios_process_cuts _glp_ios_process_cuts
1.583 +void ios_process_cuts(glp_tree *T);
1.584 +/* process cuts stored in the local cut pool */
1.585 +
1.586 +#define ios_choose_node _glp_ios_choose_node
1.587 +int ios_choose_node(glp_tree *T);
1.588 +/* select subproblem to continue the search */
1.589 +
1.590 +#define ios_choose_var _glp_ios_choose_var
1.591 +int ios_choose_var(glp_tree *T, int *next);
1.592 +/* select variable to branch on */
1.593 +
1.594 +#endif
1.595 +
1.596 +/* eof */