simplex-glpk with modified glpk for fpgaHEADmaster

1 files changed, 544 insertions, 0 deletions

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