simplex-glpk with modified glpk for fpgaHEADmaster

1 files changed, 140 insertions, 0 deletions

diff --git a/glpk-5.0/src/intopt/gmigen.c b/glpk-5.0/src/intopt/gmigen.c
new file mode 100644
index 0000000..5ecf70e
--- /dev/null
+++ b/glpk-5.0/src/intopt/gmigen.c
@@ -0,0 +1,140 @@
+/* gmigen.c (Gomory's mixed integer cuts generator) */
+
+/***********************************************************************
+*  This code is part of GLPK (GNU Linear Programming Kit).
+*  Copyright (C) 2002-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 "prob.h"
+
+/***********************************************************************
+*  NAME
+*
+*  glp_gmi_gen - generate Gomory's mixed integer cuts
+*
+*  SYNOPSIS
+*
+*  int glp_gmi_gen(glp_prob *P, glp_prob *pool, int max_cuts);
+*
+*  DESCRIPTION
+*
+*  This routine attempts to generate Gomory's mixed integer cuts for
+*  integer variables, whose primal values in current basic solution are
+*  integer infeasible (fractional).
+*
+*  On entry to the routine the basic solution contained in the problem
+*  object P should be optimal, and the basis factorization should be
+*  valid.
+*
+*  The cutting plane inequalities generated by the routine are added to
+*  the specified cut pool.
+*
+*  The parameter max_cuts specifies the maximal number of cuts to be
+*  generated. Note that the number of cuts cannot exceed the number of
+*  basic variables, which is the number of rows in the problem object.
+*
+*  RETURNS
+*
+*  The routine returns the number of cuts that have been generated and
+*  added to the cut pool. */
+
+#define f(x) ((x) - floor(x))
+/* compute fractional part of x */
+
+struct var { int j; double f; };
+
+static int CDECL fcmp(const void *p1, const void *p2)
+{     const struct var *v1 = p1, *v2 = p2;
+      if (v1->f > v2->f) return -1;
+      if (v1->f < v2->f) return +1;
+      return 0;
+}
+
+int glp_gmi_gen(glp_prob *P, glp_prob *pool, int max_cuts)
+{     int m = P->m;
+      int n = P->n;
+      GLPCOL *col;
+      struct var *var;
+      int i, j, k, t, len, nv, nnn, *ind;
+      double frac, *val, *phi;
+      /* sanity checks */
+      if (!(P->m == 0 || P->valid))
+         xerror("glp_gmi_gen: basis factorization does not exist\n");
+      if (!(P->pbs_stat == GLP_FEAS && P->dbs_stat == GLP_FEAS))
+         xerror("glp_gmi_gen: optimal basic solution required\n");
+      if (pool->n != n)
+         xerror("glp_gmi_gen: cut pool has wrong number of columns\n");
+      /* allocate working arrays */
+      var = xcalloc(1+n, sizeof(struct var));
+      ind = xcalloc(1+n, sizeof(int));
+      val = xcalloc(1+n, sizeof(double));
+      phi = xcalloc(1+m+n, sizeof(double));
+      /* build the list of integer structural variables, which are
+       * basic and have integer infeasible (fractional) primal values
+       * in optimal solution to specified LP */
+      nv = 0;
+      for (j = 1; j <= n; j++)
+      {  col = P->col[j];
+         if (col->kind != GLP_IV)
+            continue;
+         if (col->type == GLP_FX)
+            continue;
+         if (col->stat != GLP_BS)
+            continue;
+         frac = f(col->prim);
+         if (!(0.05 <= frac && frac <= 0.95))
+            continue;
+         /* add variable to the list */
+         nv++, var[nv].j = j, var[nv].f = frac;
+      }
+      /* sort the list by descending fractionality */
+      qsort(&var[1], nv, sizeof(struct var), fcmp);
+      /* try to generate cuts by one for each variable in the list, but
+       * not more than max_cuts cuts */
+      nnn = 0;
+      for (t = 1; t <= nv; t++)
+      {  len = glp_gmi_cut(P, var[t].j, ind, val, phi);
+         if (len < 1)
+            goto skip;
+         /* if the cut inequality seems to be badly scaled, reject it
+          * to avoid numerical difficulties */
+         for (k = 1; k <= len; k++)
+         {  if (fabs(val[k]) < 1e-03)
+               goto skip;
+            if (fabs(val[k]) > 1e+03)
+               goto skip;
+         }
+         /* add the cut to the cut pool for further consideration */
+         i = glp_add_rows(pool, 1);
+         glp_set_row_bnds(pool, i, GLP_LO, val[0], 0);
+         glp_set_mat_row(pool, i, len, ind, val);
+         /* one cut has been generated */
+         nnn++;
+         if (nnn == max_cuts)
+            break;
+skip:    ;
+      }
+      /* free working arrays */
+      xfree(var);
+      xfree(ind);
+      xfree(val);
+      xfree(phi);
+      return nnn;
+}
+
+/* eof */