lemon-project-template-glpk

annotate deps/glpk/src/glpios.h @ 9:33de93886c88

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