simplex-glpk with modified glpk for fpgaHEADmaster

1 files changed, 174 insertions, 0 deletions

diff --git a/glpk-5.0/src/draft/glpios12.c b/glpk-5.0/src/draft/glpios12.c
new file mode 100644
index 0000000..28e54af
--- /dev/null
+++ b/glpk-5.0/src/draft/glpios12.c
@@ -0,0 +1,174 @@
+/* glpios12.c (node selection heuristics) */
+
+/***********************************************************************
+*  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/>.
+***********************************************************************/
+
+#include "env.h"
+#include "ios.h"
+
+/***********************************************************************
+*  NAME
+*
+*  ios_choose_node - select subproblem to continue the search
+*
+*  SYNOPSIS
+*
+*  #include "glpios.h"
+*  int ios_choose_node(glp_tree *T);
+*
+*  DESCRIPTION
+*
+*  The routine ios_choose_node selects a subproblem from the active
+*  list to continue the search. The choice depends on the backtracking
+*  technique option.
+*
+*  RETURNS
+*
+*  The routine ios_choose_node return the reference number of the
+*  subproblem selected. */
+
+static int most_feas(glp_tree *T);
+static int best_proj(glp_tree *T);
+static int best_node(glp_tree *T);
+
+int ios_choose_node(glp_tree *T)
+{     int p;
+      if (T->parm->bt_tech == GLP_BT_DFS)
+      {  /* depth first search */
+         xassert(T->tail != NULL);
+         p = T->tail->p;
+      }
+      else if (T->parm->bt_tech == GLP_BT_BFS)
+      {  /* breadth first search */
+         xassert(T->head != NULL);
+         p = T->head->p;
+      }
+      else if (T->parm->bt_tech == GLP_BT_BLB)
+      {  /* select node with best local bound */
+         p = best_node(T);
+      }
+      else if (T->parm->bt_tech == GLP_BT_BPH)
+      {  if (T->mip->mip_stat == GLP_UNDEF)
+         {  /* "most integer feasible" subproblem */
+            p = most_feas(T);
+         }
+         else
+         {  /* best projection heuristic */
+            p = best_proj(T);
+         }
+      }
+      else
+         xassert(T != T);
+      return p;
+}
+
+static int most_feas(glp_tree *T)
+{     /* select subproblem whose parent has minimal sum of integer
+         infeasibilities */
+      IOSNPD *node;
+      int p;
+      double best;
+      p = 0, best = DBL_MAX;
+      for (node = T->head; node != NULL; node = node->next)
+      {  xassert(node->up != NULL);
+         if (best > node->up->ii_sum)
+            p = node->p, best = node->up->ii_sum;
+      }
+      return p;
+}
+
+static int best_proj(glp_tree *T)
+{     /* select subproblem using the best projection heuristic */
+      IOSNPD *root, *node;
+      int p;
+      double best, deg, obj;
+      /* the global bound must exist */
+      xassert(T->mip->mip_stat == GLP_FEAS);
+      /* obtain pointer to the root node, which must exist */
+      root = T->slot[1].node;
+      xassert(root != NULL);
+      /* deg estimates degradation of the objective function per unit
+         of the sum of integer infeasibilities */
+      xassert(root->ii_sum > 0.0);
+      deg = (T->mip->mip_obj - root->bound) / root->ii_sum;
+      /* nothing has been selected so far */
+      p = 0, best = DBL_MAX;
+      /* walk through the list of active subproblems */
+      for (node = T->head; node != NULL; node = node->next)
+      {  xassert(node->up != NULL);
+         /* obj estimates optimal objective value if the sum of integer
+            infeasibilities were zero */
+         obj = node->up->bound + deg * node->up->ii_sum;
+         if (T->mip->dir == GLP_MAX) obj = - obj;
+         /* select the subproblem which has the best estimated optimal
+            objective value */
+         if (best > obj) p = node->p, best = obj;
+      }
+      return p;
+}
+
+static int best_node(glp_tree *T)
+{     /* select subproblem with best local bound */
+      IOSNPD *node, *best = NULL;
+      double bound, eps;
+      switch (T->mip->dir)
+      {  case GLP_MIN:
+            bound = +DBL_MAX;
+            for (node = T->head; node != NULL; node = node->next)
+               if (bound > node->bound) bound = node->bound;
+            xassert(bound != +DBL_MAX);
+            eps = 1e-10 * (1.0 + fabs(bound));
+            for (node = T->head; node != NULL; node = node->next)
+            {  if (node->bound <= bound + eps)
+               {  xassert(node->up != NULL);
+                  if (best == NULL ||
+#if 1
+                  best->up->ii_sum > node->up->ii_sum) best = node;
+#else
+                  best->lp_obj > node->lp_obj) best = node;
+#endif
+               }
+            }
+            break;
+         case GLP_MAX:
+            bound = -DBL_MAX;
+            for (node = T->head; node != NULL; node = node->next)
+               if (bound < node->bound) bound = node->bound;
+            xassert(bound != -DBL_MAX);
+            eps = 1e-10 * (1.0 + fabs(bound));
+            for (node = T->head; node != NULL; node = node->next)
+            {  if (node->bound >= bound - eps)
+               {  xassert(node->up != NULL);
+                  if (best == NULL ||
+#if 1
+                  best->up->ii_sum > node->up->ii_sum) best = node;
+#else
+                  best->lp_obj < node->lp_obj) best = node;
+#endif
+               }
+            }
+            break;
+         default:
+            xassert(T != T);
+      }
+      xassert(best != NULL);
+      return best->p;
+}
+
+/* eof */