alpar@1: /* glpios.h (integer optimization suite) */
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  This code is part of GLPK (GNU Linear Programming Kit).
alpar@1: *
alpar@1: *  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@1: *  2009, 2010 Andrew Makhorin, Department for Applied Informatics,
alpar@1: *  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@1: *  E-mail: <mao@gnu.org>.
alpar@1: *
alpar@1: *  GLPK is free software: you can redistribute it and/or modify it
alpar@1: *  under the terms of the GNU General Public License as published by
alpar@1: *  the Free Software Foundation, either version 3 of the License, or
alpar@1: *  (at your option) any later version.
alpar@1: *
alpar@1: *  GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@1: *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@1: *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@1: *  License for more details.
alpar@1: *
alpar@1: *  You should have received a copy of the GNU General Public License
alpar@1: *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: #ifndef GLPIOS_H
alpar@1: #define GLPIOS_H
alpar@1: 
alpar@1: #define GLP_TREE_DEFINED
alpar@1: typedef struct glp_tree glp_tree;
alpar@1: 
alpar@1: #include "glpapi.h"
alpar@1: 
alpar@1: typedef struct IOSLOT IOSLOT;
alpar@1: typedef struct IOSNPD IOSNPD;
alpar@1: typedef struct IOSBND IOSBND;
alpar@1: typedef struct IOSTAT IOSTAT;
alpar@1: typedef struct IOSROW IOSROW;
alpar@1: typedef struct IOSAIJ IOSAIJ;
alpar@1: typedef struct IOSPOOL IOSPOOL;
alpar@1: typedef struct IOSCUT IOSCUT;
alpar@1: 
alpar@1: struct glp_tree
alpar@1: {     /* branch-and-bound tree */
alpar@1:       int magic;
alpar@1:       /* magic value used for debugging */
alpar@1:       DMP *pool;
alpar@1:       /* memory pool to store all IOS components */
alpar@1:       int n;
alpar@1:       /* number of columns (variables) */
alpar@1:       /*--------------------------------------------------------------*/
alpar@1:       /* problem components corresponding to the original MIP and its
alpar@1:          LP relaxation (used to restore the original problem object on
alpar@1:          exit from the solver) */
alpar@1:       int orig_m;
alpar@1:       /* number of rows */
alpar@1:       unsigned char *orig_type; /* uchar orig_type[1+orig_m+n]; */
alpar@1:       /* types of all variables */
alpar@1:       double *orig_lb; /* double orig_lb[1+orig_m+n]; */
alpar@1:       /* lower bounds of all variables */
alpar@1:       double *orig_ub; /* double orig_ub[1+orig_m+n]; */
alpar@1:       /* upper bounds of all variables */
alpar@1:       unsigned char *orig_stat; /* uchar orig_stat[1+orig_m+n]; */
alpar@1:       /* statuses of all variables */
alpar@1:       double *orig_prim; /* double orig_prim[1+orig_m+n]; */
alpar@1:       /* primal values of all variables */
alpar@1:       double *orig_dual; /* double orig_dual[1+orig_m+n]; */
alpar@1:       /* dual values of all variables */
alpar@1:       double orig_obj;
alpar@1:       /* optimal objective value for LP relaxation */
alpar@1:       /*--------------------------------------------------------------*/
alpar@1:       /* branch-and-bound tree */
alpar@1:       int nslots;
alpar@1:       /* length of the array of slots (enlarged automatically) */
alpar@1:       int avail;
alpar@1:       /* index of the first free slot; 0 means all slots are in use */
alpar@1:       IOSLOT *slot; /* IOSLOT slot[1+nslots]; */
alpar@1:       /* array of slots:
alpar@1:          slot[0] is not used;
alpar@1:          slot[p], 1 <= p <= nslots, either contains a pointer to some
alpar@1:          node of the branch-and-bound tree, in which case p is used on
alpar@1:          API level as the reference number of corresponding subproblem,
alpar@1:          or is free; all free slots are linked into single linked list;
alpar@1:          slot[1] always contains a pointer to the root node (it is free
alpar@1:          only if the tree is empty) */
alpar@1:       IOSNPD *head;
alpar@1:       /* pointer to the head of the active list */
alpar@1:       IOSNPD *tail;
alpar@1:       /* pointer to the tail of the active list */
alpar@1:       /* the active list is a doubly linked list of active subproblems
alpar@1:          which correspond to leaves of the tree; all subproblems in the
alpar@1:          active list are ordered chronologically (each a new subproblem
alpar@1:          is always added to the tail of the list) */
alpar@1:       int a_cnt;
alpar@1:       /* current number of active nodes (including the current one) */
alpar@1:       int n_cnt;
alpar@1:       /* current number of all (active and inactive) nodes */
alpar@1:       int t_cnt;
alpar@1:       /* total number of nodes including those which have been already
alpar@1:          removed from the tree; this count is increased by one whenever
alpar@1:          a new node is created and never decreased */
alpar@1:       /*--------------------------------------------------------------*/
alpar@1:       /* problem components corresponding to the root subproblem */
alpar@1:       int root_m;
alpar@1:       /* number of rows */
alpar@1:       unsigned char *root_type; /* uchar root_type[1+root_m+n]; */
alpar@1:       /* types of all variables */
alpar@1:       double *root_lb; /* double root_lb[1+root_m+n]; */
alpar@1:       /* lower bounds of all variables */
alpar@1:       double *root_ub; /* double root_ub[1+root_m+n]; */
alpar@1:       /* upper bounds of all variables */
alpar@1:       unsigned char *root_stat; /* uchar root_stat[1+root_m+n]; */
alpar@1:       /* statuses of all variables */
alpar@1:       /*--------------------------------------------------------------*/
alpar@1:       /* current subproblem and its LP relaxation */
alpar@1:       IOSNPD *curr;
alpar@1:       /* pointer to the current subproblem (which can be only active);
alpar@1:          NULL means the current subproblem does not exist */
alpar@1:       glp_prob *mip;
alpar@1:       /* original problem object passed to the solver; if the current
alpar@1:          subproblem exists, its LP segment corresponds to LP relaxation
alpar@1:          of the current subproblem; if the current subproblem does not
alpar@1:          exist, its LP segment corresponds to LP relaxation of the root
alpar@1:          subproblem (note that the root subproblem may differ from the
alpar@1:          original MIP, because it may be preprocessed and/or may have
alpar@1:          additional rows) */
alpar@1:       unsigned char *non_int; /* uchar non_int[1+n]; */
alpar@1:       /* these column flags are set each time when LP relaxation of the
alpar@1:          current subproblem has been solved;
alpar@1:          non_int[0] is not used;
alpar@1:          non_int[j], 1 <= j <= n, is j-th column flag; if this flag is
alpar@1:          set, corresponding variable is required to be integer, but its
alpar@1:          value in basic solution is fractional */
alpar@1:       /*--------------------------------------------------------------*/
alpar@1:       /* problem components corresponding to the parent (predecessor)
alpar@1:          subproblem for the current subproblem; used to inspect changes
alpar@1:          on freezing the current subproblem */
alpar@1:       int pred_m;
alpar@1:       /* number of rows */
alpar@1:       int pred_max;
alpar@1:       /* length of the following four arrays (enlarged automatically),
alpar@1:          pred_max >= pred_m + n */
alpar@1:       unsigned char *pred_type; /* uchar pred_type[1+pred_m+n]; */
alpar@1:       /* types of all variables */
alpar@1:       double *pred_lb; /* double pred_lb[1+pred_m+n]; */
alpar@1:       /* lower bounds of all variables */
alpar@1:       double *pred_ub; /* double pred_ub[1+pred_m+n]; */
alpar@1:       /* upper bounds of all variables */
alpar@1:       unsigned char *pred_stat; /* uchar pred_stat[1+pred_m+n]; */
alpar@1:       /* statuses of all variables */
alpar@1:       /****************************************************************/
alpar@1:       /* built-in cut generators segment */
alpar@1:       IOSPOOL *local;
alpar@1:       /* local cut pool */
alpar@1:       void *mir_gen;
alpar@1:       /* pointer to working area used by the MIR cut generator */
alpar@1:       void *clq_gen;
alpar@1:       /* pointer to working area used by the clique cut generator */
alpar@1:       /*--------------------------------------------------------------*/
alpar@1:       void *pcost;
alpar@1:       /* pointer to working area used on pseudocost branching */
alpar@1:       int *iwrk; /* int iwrk[1+n]; */
alpar@1:       /* working array */
alpar@1:       double *dwrk; /* double dwrk[1+n]; */
alpar@1:       /* working array */
alpar@1:       /*--------------------------------------------------------------*/
alpar@1:       /* control parameters and statistics */
alpar@1:       const glp_iocp *parm;
alpar@1:       /* copy of control parameters passed to the solver */
alpar@1:       glp_long tm_beg;
alpar@1:       /* starting time of the search, in seconds; the total time of the
alpar@1:          search is the difference between xtime() and tm_beg */
alpar@1:       glp_long tm_lag;
alpar@1:       /* the most recent time, in seconds, at which the progress of the
alpar@1:          the search was displayed */
alpar@1:       int sol_cnt;
alpar@1:       /* number of integer feasible solutions found */
alpar@1:       /*--------------------------------------------------------------*/
alpar@1:       /* advanced solver interface */
alpar@1:       int reason;
alpar@1:       /* flag indicating the reason why the callback routine is being
alpar@1:          called (see glpk.h) */
alpar@1:       int stop;
alpar@1:       /* flag indicating that the callback routine requires premature
alpar@1:          termination of the search */
alpar@1:       int next_p;
alpar@1:       /* reference number of active subproblem selected to continue
alpar@1:          the search; 0 means no subproblem has been selected */
alpar@1:       int reopt;
alpar@1:       /* flag indicating that the current LP relaxation needs to be
alpar@1:          re-optimized */
alpar@1:       int reinv;
alpar@1:       /* flag indicating that some (non-active) rows were removed from
alpar@1:          the current LP relaxation, so if there no new rows appear, the
alpar@1:          basis must be re-factorized */
alpar@1:       int br_var;
alpar@1:       /* the number of variable chosen to branch on */
alpar@1:       int br_sel;
alpar@1:       /* flag indicating which branch (subproblem) is suggested to be
alpar@1:          selected to continue the search:
alpar@1:          GLP_DN_BRNCH - select down-branch
alpar@1:          GLP_UP_BRNCH - select up-branch
alpar@1:          GLP_NO_BRNCH - use general selection technique */
alpar@1:       int child;
alpar@1:       /* subproblem reference number corresponding to br_sel */
alpar@1: };
alpar@1: 
alpar@1: struct IOSLOT
alpar@1: {     /* node subproblem slot */
alpar@1:       IOSNPD *node;
alpar@1:       /* pointer to subproblem descriptor; NULL means free slot */
alpar@1:       int next;
alpar@1:       /* index of another free slot (only if this slot is free) */
alpar@1: };
alpar@1: 
alpar@1: struct IOSNPD
alpar@1: {     /* node subproblem descriptor */
alpar@1:       int p;
alpar@1:       /* subproblem reference number (it is the index to corresponding
alpar@1:          slot, i.e. slot[p] points to this descriptor) */
alpar@1:       IOSNPD *up;
alpar@1:       /* pointer to the parent subproblem; NULL means this node is the
alpar@1:          root of the tree, in which case p = 1 */
alpar@1:       int level;
alpar@1:       /* node level (the root node has level 0) */
alpar@1:       int count;
alpar@1:       /* if count = 0, this subproblem is active; if count > 0, this
alpar@1:          subproblem is inactive, in which case count is the number of
alpar@1:          its child subproblems */
alpar@1:       /* the following three linked lists are destroyed on reviving and
alpar@1:          built anew on freezing the subproblem: */
alpar@1:       IOSBND *b_ptr;
alpar@1:       /* linked list of rows and columns of the parent subproblem whose
alpar@1:          types and bounds were changed */
alpar@1:       IOSTAT *s_ptr;
alpar@1:       /* linked list of rows and columns of the parent subproblem whose
alpar@1:          statuses were changed */
alpar@1:       IOSROW *r_ptr;
alpar@1:       /* linked list of rows (cuts) added to the parent subproblem */
alpar@1:       int solved;
alpar@1:       /* how many times LP relaxation of this subproblem was solved;
alpar@1:          for inactive subproblem this count is always non-zero;
alpar@1:          for active subproblem, which is not current, this count may be
alpar@1:          non-zero, if the subproblem was temporarily suspended */
alpar@1:       double lp_obj;
alpar@1:       /* optimal objective value to LP relaxation of this subproblem;
alpar@1:          on creating a subproblem this value is inherited from its
alpar@1:          parent; for the root subproblem, which has no parent, this
alpar@1:          value is initially set to -DBL_MAX (minimization) or +DBL_MAX
alpar@1:          (maximization); each time the subproblem is re-optimized, this
alpar@1:          value is appropriately changed */
alpar@1:       double bound;
alpar@1:       /* local lower (minimization) or upper (maximization) bound for
alpar@1:          integer optimal solution to *this* subproblem; this bound is
alpar@1:          local in the sense that only subproblems in the subtree rooted
alpar@1:          at this node cannot have better integer feasible solutions;
alpar@1:          on creating a subproblem its local bound is inherited from its
alpar@1:          parent and then can be made stronger (never weaker); for the
alpar@1:          root subproblem its local bound is initially set to -DBL_MAX
alpar@1:          (minimization) or +DBL_MAX (maximization) and then improved as
alpar@1:          the root LP relaxation has been solved */
alpar@1:       /* the following two quantities are defined only if LP relaxation
alpar@1:          of this subproblem was solved at least once (solved > 0): */
alpar@1:       int ii_cnt;
alpar@1:       /* number of integer variables whose value in optimal solution to
alpar@1:          LP relaxation of this subproblem is fractional */
alpar@1:       double ii_sum;
alpar@1:       /* sum of integer infeasibilities */
alpar@1: #if 1 /* 30/XI-2009 */
alpar@1:       int changed;
alpar@1:       /* how many times this subproblem was re-formulated (by adding
alpar@1:          cutting plane constraints) */
alpar@1: #endif
alpar@1:       int br_var;
alpar@1:       /* ordinal number of branching variable, 1 <= br_var <= n, used
alpar@1:          to split this subproblem; 0 means that either this subproblem
alpar@1:          is active or branching was made on a constraint */
alpar@1:       double br_val;
alpar@1:       /* (fractional) value of branching variable in optimal solution
alpar@1:          to final LP relaxation of this subproblem */
alpar@1:       void *data; /* char data[tree->cb_size]; */
alpar@1:       /* pointer to the application-specific data */
alpar@1:       IOSNPD *temp;
alpar@1:       /* working pointer used by some routines */
alpar@1:       IOSNPD *prev;
alpar@1:       /* pointer to previous subproblem in the active list */
alpar@1:       IOSNPD *next;
alpar@1:       /* pointer to next subproblem in the active list */
alpar@1: };
alpar@1: 
alpar@1: struct IOSBND
alpar@1: {     /* bounds change entry */
alpar@1:       int k;
alpar@1:       /* ordinal number of corresponding row (1 <= k <= m) or column
alpar@1:          (m+1 <= k <= m+n), where m and n are the number of rows and
alpar@1:          columns, resp., in the parent subproblem */
alpar@1:       unsigned char type;
alpar@1:       /* new type */
alpar@1:       double lb;
alpar@1:       /* new lower bound */
alpar@1:       double ub;
alpar@1:       /* new upper bound */
alpar@1:       IOSBND *next;
alpar@1:       /* pointer to next entry for the same subproblem */
alpar@1: };
alpar@1: 
alpar@1: struct IOSTAT
alpar@1: {     /* status change entry */
alpar@1:       int k;
alpar@1:       /* ordinal number of corresponding row (1 <= k <= m) or column
alpar@1:          (m+1 <= k <= m+n), where m and n are the number of rows and
alpar@1:          columns, resp., in the parent subproblem */
alpar@1:       unsigned char stat;
alpar@1:       /* new status */
alpar@1:       IOSTAT *next;
alpar@1:       /* pointer to next entry for the same subproblem */
alpar@1: };
alpar@1: 
alpar@1: struct IOSROW
alpar@1: {     /* row (constraint) addition entry */
alpar@1:       char *name;
alpar@1:       /* row name or NULL */
alpar@1:       unsigned char origin;
alpar@1:       /* row origin flag (see glp_attr.origin) */
alpar@1:       unsigned char klass;
alpar@1:       /* row class descriptor (see glp_attr.klass) */
alpar@1:       unsigned char type;
alpar@1:       /* row type (GLP_LO, GLP_UP, etc.) */
alpar@1:       double lb;
alpar@1:       /* row lower bound */
alpar@1:       double ub;
alpar@1:       /* row upper bound */
alpar@1:       IOSAIJ *ptr;
alpar@1:       /* pointer to the row coefficient list */
alpar@1:       double rii;
alpar@1:       /* row scale factor */
alpar@1:       unsigned char stat;
alpar@1:       /* row status (GLP_BS, GLP_NL, etc.) */
alpar@1:       IOSROW *next;
alpar@1:       /* pointer to next entry for the same subproblem */
alpar@1: };
alpar@1: 
alpar@1: struct IOSAIJ
alpar@1: {     /* constraint coefficient */
alpar@1:       int j;
alpar@1:       /* variable (column) number, 1 <= j <= n */
alpar@1:       double val;
alpar@1:       /* non-zero coefficient value */
alpar@1:       IOSAIJ *next;
alpar@1:       /* pointer to next coefficient for the same row */
alpar@1: };
alpar@1: 
alpar@1: struct IOSPOOL
alpar@1: {     /* cut pool */
alpar@1:       int size;
alpar@1:       /* pool size = number of cuts in the pool */
alpar@1:       IOSCUT *head;
alpar@1:       /* pointer to the first cut */
alpar@1:       IOSCUT *tail;
alpar@1:       /* pointer to the last cut */
alpar@1:       int ord;
alpar@1:       /* ordinal number of the current cut, 1 <= ord <= size */
alpar@1:       IOSCUT *curr;
alpar@1:       /* pointer to the current cut */
alpar@1: };
alpar@1: 
alpar@1: struct IOSCUT
alpar@1: {     /* cut (cutting plane constraint) */
alpar@1:       char *name;
alpar@1:       /* cut name or NULL */
alpar@1:       unsigned char klass;
alpar@1:       /* cut class descriptor (see glp_attr.klass) */
alpar@1:       IOSAIJ *ptr;
alpar@1:       /* pointer to the cut coefficient list */
alpar@1:       unsigned char type;
alpar@1:       /* cut type:
alpar@1:          GLP_LO: sum a[j] * x[j] >= b
alpar@1:          GLP_UP: sum a[j] * x[j] <= b
alpar@1:          GLP_FX: sum a[j] * x[j]  = b */
alpar@1:       double rhs;
alpar@1:       /* cut right-hand side */
alpar@1:       IOSCUT *prev;
alpar@1:       /* pointer to previous cut */
alpar@1:       IOSCUT *next;
alpar@1:       /* pointer to next cut */
alpar@1: };
alpar@1: 
alpar@1: #define ios_create_tree _glp_ios_create_tree
alpar@1: glp_tree *ios_create_tree(glp_prob *mip, const glp_iocp *parm);
alpar@1: /* create branch-and-bound tree */
alpar@1: 
alpar@1: #define ios_revive_node _glp_ios_revive_node
alpar@1: void ios_revive_node(glp_tree *tree, int p);
alpar@1: /* revive specified subproblem */
alpar@1: 
alpar@1: #define ios_freeze_node _glp_ios_freeze_node
alpar@1: void ios_freeze_node(glp_tree *tree);
alpar@1: /* freeze current subproblem */
alpar@1: 
alpar@1: #define ios_clone_node _glp_ios_clone_node
alpar@1: void ios_clone_node(glp_tree *tree, int p, int nnn, int ref[]);
alpar@1: /* clone specified subproblem */
alpar@1: 
alpar@1: #define ios_delete_node _glp_ios_delete_node
alpar@1: void ios_delete_node(glp_tree *tree, int p);
alpar@1: /* delete specified subproblem */
alpar@1: 
alpar@1: #define ios_delete_tree _glp_ios_delete_tree
alpar@1: void ios_delete_tree(glp_tree *tree);
alpar@1: /* delete branch-and-bound tree */
alpar@1: 
alpar@1: #define ios_eval_degrad _glp_ios_eval_degrad
alpar@1: void ios_eval_degrad(glp_tree *tree, int j, double *dn, double *up);
alpar@1: /* estimate obj. degrad. for down- and up-branches */
alpar@1: 
alpar@1: #define ios_round_bound _glp_ios_round_bound
alpar@1: double ios_round_bound(glp_tree *tree, double bound);
alpar@1: /* improve local bound by rounding */
alpar@1: 
alpar@1: #define ios_is_hopeful _glp_ios_is_hopeful
alpar@1: int ios_is_hopeful(glp_tree *tree, double bound);
alpar@1: /* check if subproblem is hopeful */
alpar@1: 
alpar@1: #define ios_best_node _glp_ios_best_node
alpar@1: int ios_best_node(glp_tree *tree);
alpar@1: /* find active node with best local bound */
alpar@1: 
alpar@1: #define ios_relative_gap _glp_ios_relative_gap
alpar@1: double ios_relative_gap(glp_tree *tree);
alpar@1: /* compute relative mip gap */
alpar@1: 
alpar@1: #define ios_solve_node _glp_ios_solve_node
alpar@1: int ios_solve_node(glp_tree *tree);
alpar@1: /* solve LP relaxation of current subproblem */
alpar@1: 
alpar@1: #define ios_create_pool _glp_ios_create_pool
alpar@1: IOSPOOL *ios_create_pool(glp_tree *tree);
alpar@1: /* create cut pool */
alpar@1: 
alpar@1: #define ios_add_row _glp_ios_add_row
alpar@1: int ios_add_row(glp_tree *tree, IOSPOOL *pool,
alpar@1:       const char *name, int klass, int flags, int len, const int ind[],
alpar@1:       const double val[], int type, double rhs);
alpar@1: /* add row (constraint) to the cut pool */
alpar@1: 
alpar@1: #define ios_find_row _glp_ios_find_row
alpar@1: IOSCUT *ios_find_row(IOSPOOL *pool, int i);
alpar@1: /* find row (constraint) in the cut pool */
alpar@1: 
alpar@1: #define ios_del_row _glp_ios_del_row
alpar@1: void ios_del_row(glp_tree *tree, IOSPOOL *pool, int i);
alpar@1: /* remove row (constraint) from the cut pool */
alpar@1: 
alpar@1: #define ios_clear_pool _glp_ios_clear_pool
alpar@1: void ios_clear_pool(glp_tree *tree, IOSPOOL *pool);
alpar@1: /* remove all rows (constraints) from the cut pool */
alpar@1: 
alpar@1: #define ios_delete_pool _glp_ios_delete_pool
alpar@1: void ios_delete_pool(glp_tree *tree, IOSPOOL *pool);
alpar@1: /* delete cut pool */
alpar@1: 
alpar@1: #define ios_preprocess_node _glp_ios_preprocess_node
alpar@1: int ios_preprocess_node(glp_tree *tree, int max_pass);
alpar@1: /* preprocess current subproblem */
alpar@1: 
alpar@1: #define ios_driver _glp_ios_driver
alpar@1: int ios_driver(glp_tree *tree);
alpar@1: /* branch-and-bound driver */
alpar@1: 
alpar@1: /**********************************************************************/
alpar@1: 
alpar@1: typedef struct IOSVEC IOSVEC;
alpar@1: 
alpar@1: struct IOSVEC
alpar@1: {     /* sparse vector v = (v[j]) */
alpar@1:       int n;
alpar@1:       /* dimension, n >= 0 */
alpar@1:       int nnz;
alpar@1:       /* number of non-zero components, 0 <= nnz <= n */
alpar@1:       int *pos; /* int pos[1+n]; */
alpar@1:       /* pos[j] = k, 1 <= j <= n, is position of (non-zero) v[j] in the
alpar@1:          arrays ind and val, where 1 <= k <= nnz; pos[j] = 0 means that
alpar@1:          v[j] is structural zero */
alpar@1:       int *ind; /* int ind[1+n]; */
alpar@1:       /* ind[k] = j, 1 <= k <= nnz, is index of v[j] */
alpar@1:       double *val; /* double val[1+n]; */
alpar@1:       /* val[k], 1 <= k <= nnz, is a numeric value of v[j] */
alpar@1: };
alpar@1: 
alpar@1: #define ios_create_vec _glp_ios_create_vec
alpar@1: IOSVEC *ios_create_vec(int n);
alpar@1: /* create sparse vector */
alpar@1: 
alpar@1: #define ios_check_vec _glp_ios_check_vec
alpar@1: void ios_check_vec(IOSVEC *v);
alpar@1: /* check that sparse vector has correct representation */
alpar@1: 
alpar@1: #define ios_get_vj _glp_ios_get_vj
alpar@1: double ios_get_vj(IOSVEC *v, int j);
alpar@1: /* retrieve component of sparse vector */
alpar@1: 
alpar@1: #define ios_set_vj _glp_ios_set_vj
alpar@1: void ios_set_vj(IOSVEC *v, int j, double val);
alpar@1: /* set/change component of sparse vector */
alpar@1: 
alpar@1: #define ios_clear_vec _glp_ios_clear_vec
alpar@1: void ios_clear_vec(IOSVEC *v);
alpar@1: /* set all components of sparse vector to zero */
alpar@1: 
alpar@1: #define ios_clean_vec _glp_ios_clean_vec
alpar@1: void ios_clean_vec(IOSVEC *v, double eps);
alpar@1: /* remove zero or small components from sparse vector */
alpar@1: 
alpar@1: #define ios_copy_vec _glp_ios_copy_vec
alpar@1: void ios_copy_vec(IOSVEC *x, IOSVEC *y);
alpar@1: /* copy sparse vector (x := y) */
alpar@1: 
alpar@1: #define ios_linear_comb _glp_ios_linear_comb
alpar@1: void ios_linear_comb(IOSVEC *x, double a, IOSVEC *y);
alpar@1: /* compute linear combination (x := x + a * y) */
alpar@1: 
alpar@1: #define ios_delete_vec _glp_ios_delete_vec
alpar@1: void ios_delete_vec(IOSVEC *v);
alpar@1: /* delete sparse vector */
alpar@1: 
alpar@1: /**********************************************************************/
alpar@1: 
alpar@1: #define ios_gmi_gen _glp_ios_gmi_gen
alpar@1: void ios_gmi_gen(glp_tree *tree);
alpar@1: /* generate Gomory's mixed integer cuts */
alpar@1: 
alpar@1: #define ios_mir_init _glp_ios_mir_init
alpar@1: void *ios_mir_init(glp_tree *tree);
alpar@1: /* initialize MIR cut generator */
alpar@1: 
alpar@1: #define ios_mir_gen _glp_ios_mir_gen
alpar@1: void ios_mir_gen(glp_tree *tree, void *gen);
alpar@1: /* generate MIR cuts */
alpar@1: 
alpar@1: #define ios_mir_term _glp_ios_mir_term
alpar@1: void ios_mir_term(void *gen);
alpar@1: /* terminate MIR cut generator */
alpar@1: 
alpar@1: #define ios_cov_gen _glp_ios_cov_gen
alpar@1: void ios_cov_gen(glp_tree *tree);
alpar@1: /* generate mixed cover cuts */
alpar@1: 
alpar@1: #define ios_clq_init _glp_ios_clq_init
alpar@1: void *ios_clq_init(glp_tree *tree);
alpar@1: /* initialize clique cut generator */
alpar@1: 
alpar@1: #define ios_clq_gen _glp_ios_clq_gen
alpar@1: void ios_clq_gen(glp_tree *tree, void *gen);
alpar@1: /* generate clique cuts */
alpar@1: 
alpar@1: #define ios_clq_term _glp_ios_clq_term
alpar@1: void ios_clq_term(void *gen);
alpar@1: /* terminate clique cut generator */
alpar@1: 
alpar@1: #define ios_pcost_init _glp_ios_pcost_init
alpar@1: void *ios_pcost_init(glp_tree *tree);
alpar@1: /* initialize working data used on pseudocost branching */
alpar@1: 
alpar@1: #define ios_pcost_branch _glp_ios_pcost_branch
alpar@1: int ios_pcost_branch(glp_tree *T, int *next);
alpar@1: /* choose branching variable with pseudocost branching */
alpar@1: 
alpar@1: #define ios_pcost_update _glp_ios_pcost_update
alpar@1: void ios_pcost_update(glp_tree *tree);
alpar@1: /* update history information for pseudocost branching */
alpar@1: 
alpar@1: #define ios_pcost_free _glp_ios_pcost_free
alpar@1: void ios_pcost_free(glp_tree *tree);
alpar@1: /* free working area used on pseudocost branching */
alpar@1: 
alpar@1: #define ios_feas_pump _glp_ios_feas_pump
alpar@1: void ios_feas_pump(glp_tree *T);
alpar@1: /* feasibility pump heuristic */
alpar@1: 
alpar@1: #define ios_process_cuts _glp_ios_process_cuts
alpar@1: void ios_process_cuts(glp_tree *T);
alpar@1: /* process cuts stored in the local cut pool */
alpar@1: 
alpar@1: #define ios_choose_node _glp_ios_choose_node
alpar@1: int ios_choose_node(glp_tree *T);
alpar@1: /* select subproblem to continue the search */
alpar@1: 
alpar@1: #define ios_choose_var _glp_ios_choose_var
alpar@1: int ios_choose_var(glp_tree *T, int *next);
alpar@1: /* select variable to branch on */
alpar@1: 
alpar@1: #endif
alpar@1: 
alpar@1: /* eof */