glpmps01.c

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

#if 1 /* 11/V-2006 */
      else if (strcmp(dsa->f1, "LI") == 0)
      {  /* lpx_set_class(dsa->lp, LPX_MIP); */
         lpx_set_col_kind(dsa->lp, j, LPX_IV);
         lb = temp;
      }
#endif
      else if (strcmp(dsa->f1, "UI") == 0)
      {  /* lpx_set_class(dsa->lp, LPX_MIP); */
         lpx_set_col_kind(dsa->lp, j, LPX_IV);
         ub = temp;
      }
      else if (strcmp(dsa->f1, "BV") == 0)
      {  /* lpx_set_class(dsa->lp, LPX_MIP); */
         lpx_set_col_kind(dsa->lp, j, LPX_IV);
         lb = 0.0, ub = 1.0;
      }
      else
      {  xprintf("%s:%d: invalid bound type in field 1\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      if (lb == -DBL_MAX && ub == +DBL_MAX)
         type = LPX_FR;
      else if (ub == +DBL_MAX)
         type = LPX_LO;
      else if (lb == -DBL_MAX)
         type = LPX_UP;
      else if (lb != ub)
         type = LPX_DB;
      else
         type = LPX_FX;
      lpx_set_col_bnds(dsa->lp, j, type, lb, ub);
      /* fields 5-6 must be blank */
      if (!(dsa->f5[0] == '\0' && dsa->f6[0] == '\0'))
      {  xprintf("%s:%d: invalid data card; fields 5-6 must be blank\n",
            dsa->fname, dsa->count);
         goto fail;
      }
      goto loop;
done: return 0;
fail: return 1;
}

int read_mps(LPX *lp, const char *fname)
{     /* read problem data in MPS format */
      struct dsa _dsa, *dsa = &_dsa;
      glp_erase_prob(lp);
      dsa->lp = lp;
      dsa->fname = fname;
      dsa->fp = NULL;
      dsa->count = 0;
      dsa->obj = 0;
      xprintf("glp_read_mps: reading problem data from `%s'...\n",
         dsa->fname);
      dsa->fp = xfopen(dsa->fname, "r");
      if (dsa->fp == NULL)
      {  xprintf("glp_read_mps: unable to open `%s' - %s\n",
            dsa->fname, strerror(errno));
         goto fail;
      }
      lpx_create_index(dsa->lp);
      /* read NAME indicator card */
      if (read_card(dsa)) goto fail;
      if (memcmp(dsa->card, "NAME ", 5) != 0)
      {  xprintf("%s:%d: NAME indicator card missing\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      memcpy(dsa->f3, dsa->card+14, 8);
      dsa->f3[8] = '\0'; adjust_name(dsa->f3);
      lpx_set_prob_name(dsa->lp, dsa->f3);
      if (dsa->f3[0] == '\0')
         xprintf("glp_read_mps: problem name not specified\n");
      else
         xprintf("glp_read_mps: problem %s\n", dsa->f3);
      /* read ROWS section */
      if (read_card(dsa)) goto fail;
      if (memcmp(dsa->card, "ROWS ", 5) != 0)
      {  xprintf("%s:%d: ROWS indicator card missing\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      if (read_rows(dsa)) goto fail;
      /* read COLUMNS section */
      if (memcmp(dsa->card, "COLUMNS ", 8) != 0)
      {  xprintf("%s:%d: COLUMNS indicator card missing\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      if (read_columns(dsa)) goto fail;
      {  int m = lpx_get_num_rows(dsa->lp);
         int n = lpx_get_num_cols(dsa->lp);
         int nnz = lpx_get_num_nz(dsa->lp);
         xprintf("glp_read_mps: %d row%s, %d column%s, %d non-zero%s\n",
            m, m == 1 ? "" : "s", n, n == 1 ? "" : "s", nnz, nnz == 1 ?
            "" : "s");
      }
      /* read RHS section (optional) */
      if (memcmp(dsa->card, "RHS ", 4) == 0)
         if (read_rhs(dsa)) goto fail;
      /* read RANGES section (optional) */
      if (memcmp(dsa->card, "RANGES ", 7) == 0)
         if (read_ranges(dsa)) goto fail;
      /* read BOUNDS section (optional) */
      if (memcmp(dsa->card, "BOUNDS ", 7) == 0)
         if (read_bounds(dsa)) goto fail;
      /* check ENDATA indicator card */
      if (memcmp(dsa->card, "ENDATA ", 7) != 0)
      {  xprintf("%s:%d: ENDATA indicator card missing\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      if (lpx_get_class(dsa->lp) == LPX_MIP)
      {  int ni = lpx_get_num_int(dsa->lp);
         int nb = lpx_get_num_bin(dsa->lp);
         char s[50];
         if (nb == 0)
            strcpy(s, "none of");
         else if (ni == 1 && nb == 1)
            strcpy(s, "");
         else if (nb == 1)
            strcpy(s, "one of");
         else if (nb == ni)
            strcpy(s, "all of");
         else
            sprintf(s, "%d of", nb);
         xprintf("glp_read_mps: %d integer column%s, %s which %s binary"
            "\n", ni, ni == 1 ? "" : "s", s, nb == 1 ? "is" : "are");
      }
      xprintf("glp_read_mps: %d cards were read\n", dsa->count);
      xfclose(dsa->fp);
      lpx_delete_index(dsa->lp);
      lpx_order_matrix(dsa->lp);
      return 0;
fail: if (dsa->lp != NULL) glp_erase_prob(dsa->lp);
      if (dsa->fp != NULL) xfclose(dsa->fp);
      return 1;
}

/*----------------------------------------------------------------------
-- write_mps - write problem data in fixed MPS format.
--
-- *Synopsis*
--
-- #include "glpmps.h"
-- int write_mps(LPX *lp, const char *fname);
--
-- *Description*
--
-- The routine write_mps writes problem data in fixed MPS format to an
-- output text file whose name is the character string fname.
--
-- *Returns*
--
-- If the operation was successful, the routine returns zero. Otherwise
-- the routine prints an error message and returns non-zero. */

static char *row_name(LPX *lp, int i, char rname[8+1])
{     const char *str = NULL;
      if (lpx_get_int_parm(lp, LPX_K_MPSORIG))
      {  if (i == 0)
            str = lpx_get_obj_name(lp);
         else
            str = lpx_get_row_name(lp, i);
         if (str != NULL && strlen(str) > 8) str = NULL;
      }
      if (str == NULL)
         sprintf(rname, "R%07d", i);
      else
         strcpy(rname, str);
      return rname;
}

static char *col_name(LPX *lp, int j, char cname[8+1])
{     const char *str = NULL;
      if (lpx_get_int_parm(lp, LPX_K_MPSORIG))
      {  str = lpx_get_col_name(lp, j);
         if (str != NULL && strlen(str) > 8) str = NULL;
      }
      if (str == NULL)
         sprintf(cname, "C%07d", j);
      else
         strcpy(cname, str);
      return cname;
}

static char *mps_numb(double val, char numb[12+1])
{     int n;
      char str[255+1], *e;
      for (n = 12; n >= 6; n--)
      {  if (val != 0.0 && fabs(val) < 0.002)
#if 0
            sprintf(str, "%.*E", n, val);
#else
            /* n is number of desired decimal places, but in case of E
               format precision means number of digits that follow the
               decimal point */
            sprintf(str, "%.*E", n-1, val);
#endif
         else
            sprintf(str, "%.*G", n, val);
         xassert(strlen(str) <= 255);
         e = strchr(str, 'E');
         if (e != NULL) sprintf(e+1, "%d", atoi(e+1));
         if (strlen(str) <= 12) return strcpy(numb, str);
      }
      xerror("glp_write_mps: unable to convert floating point number %g"
         " to character string\n", val);
      return NULL; /* make the compiler happy */
}

int write_mps(LPX *lp, const char *fname)
{     XFILE *fp;
      int wide = lpx_get_int_parm(lp, LPX_K_MPSWIDE);
      int frei = lpx_get_int_parm(lp, LPX_K_MPSFREE);
      int skip = lpx_get_int_parm(lp, LPX_K_MPSSKIP);
      int marker = 0; /* intorg/intend marker count */
      int mip, make_obj, nrows, ncols, i, j, flag, *ndx;
      double *obj, *val;
      char rname[8+1], cname[8+1], vname[8+1], numb[12+1];
      xprintf("glp_write_mps: writing problem data to `%s'...\n",
         fname);
      /* open the output text file */
      fp = xfopen(fname, "w");
      if (fp == NULL)
      {  xprintf("glp_write_mps: unable to create `%s' - %s\n", fname,
            strerror(errno));
         goto fail;
      }
      /* determine whether the problem is LP or MIP */
      mip = (lpx_get_class(lp) == LPX_MIP);
      /* determine number of rows and number of columns */
      nrows = lpx_get_num_rows(lp);
      ncols = lpx_get_num_cols(lp);
      /* the problem should contain at least one row and one column */
      if (!(nrows > 0 && ncols > 0))
         xerror("glp_write_mps: problem has no rows/columns\n");
      /* determine if the routine should output the objective row */
      make_obj = lpx_get_int_parm(lp, LPX_K_MPSOBJ);
      if (make_obj == 2)
      {  for (i = 1; i <= nrows; i++)
         {  int typx;
            lpx_get_row_bnds(lp, i, &typx, NULL, NULL);
            if (typx == LPX_FR)
            {  make_obj = 0;
               break;
            }
         }
      }
      /* write comment cards (if required) */
      if (lpx_get_int_parm(lp, LPX_K_MPSINFO))
      {  const char *name = lpx_get_prob_name(lp);
         if (name == NULL) name = "UNKNOWN";
         xfprintf(fp, "* Problem:    %.31s\n", name);
         xfprintf(fp, "* Class:      %s\n", !mip ? "LP" : "MIP");
         xfprintf(fp, "* Rows:       %d\n", nrows);
         if (!mip)
            xfprintf(fp, "* Columns:    %d\n", ncols);
         else
            xfprintf(fp, "* Columns:    %d (%d integer, %d binary)\n",
               ncols, lpx_get_num_int(lp), lpx_get_num_bin(lp));
         xfprintf(fp, "* Non-zeros:  %d\n", lpx_get_num_nz(lp));
         xfprintf(fp, "* Format:     Fixed MPS\n");
         xfprintf(fp, "*\n");
      }
      /* write NAME indicator card */
      {  const char *name = lpx_get_prob_name(lp);
         if (name == NULL)
            xfprintf(fp, "NAME\n");
         else
            xfprintf(fp, "NAME          %.8s\n", name);
      }
      /* write ROWS section */
      xfprintf(fp, "ROWS\n");
      if (make_obj)
         xfprintf(fp, " %c  %s\n", 'N', row_name(lp, 0, rname));
      for (i = 1; i <= nrows; i++)
      {  int typx;
         lpx_get_row_bnds(lp, i, &typx, NULL, NULL);
         switch (typx)
         {  case LPX_FR: typx = 'N'; break;
            case LPX_LO: typx = 'G'; break;
            case LPX_UP: typx = 'L'; break;
            case LPX_DB: typx = 'E'; break;
            case LPX_FX: typx = 'E'; break;
            default: xassert(typx != typx);
         }
         xfprintf(fp, " %c  %s\n", typx, row_name(lp, i, rname));
      }
      /* prepare coefficients of the objective function */
      obj = xcalloc(1+ncols, sizeof(double));
      obj[0] = lpx_get_obj_coef(lp, 0);
      for (j = 1; j <= ncols; j++)
         obj[j] = lpx_get_obj_coef(lp, j);
      ndx = xcalloc(1+ncols, sizeof(int));
      val = xcalloc(1+ncols, sizeof(double));
      for (i = 1; i <= nrows; i++)
#if 0
      {  double ci = lpx_get_row_coef(lp, i);
#else
      {  double ci = 0.0;
#endif
         if (ci != 0.0)
         {  int len, t;
            len = lpx_get_mat_row(lp, i, ndx, val);
            for (t = 1; t <= len; t++)
               obj[ndx[t]] += ci * val[t];
         }
      }
      xfree(ndx);
      xfree(val);
      for (j = 0; j <= ncols; j++)
         if (fabs(obj[j]) < 1e-12) obj[j] = 0.0;
      /* write COLUMNS section */
      xfprintf(fp, "COLUMNS\n");
      ndx = xcalloc(1+nrows, sizeof(int));
      val = xcalloc(1+nrows, sizeof(double));
      for (j = 1; j <= ncols; j++)
      {  int nl = 1, iv, len, t;
         col_name(lp, j, cname);
         iv = (mip && lpx_get_col_kind(lp, j) == LPX_IV);
         if (iv && marker % 2 == 0)
         {  /* open new intorg/intend group */
            marker++;
           xfprintf(fp, "    M%07d  'MARKER'                 'INTORG'\n"
               , marker);
         }
         else if (!iv && marker % 2 == 1)
         {  /* close the current intorg/intend group */
            marker++;
           xfprintf(fp, "    M%07d  'MARKER'                 'INTEND'\n"
               , marker);
         }
         /* obtain j-th column of the constraint matrix */
         len = lpx_get_mat_col(lp, j, ndx, val);
         ndx[0] = 0;
         val[0] = (make_obj ? obj[j] : 0.0);
         if (len == 0 && val[0] == 0.0 && !skip)
            xfprintf(fp, "    %-8s  %-8s  %12s   $ empty column\n",
               cname, row_name(lp, 1, rname), mps_numb(0.0, numb));
         for (t = val[0] != 0.0 ? 0 : 1; t <= len; t++)
         {  if (nl)
               xfprintf(fp, "    %-8s  ", cname);
            else
               xfprintf(fp, "   ");
            xfprintf(fp, "%-8s  %12s",
               row_name(lp, ndx[t], rname), mps_numb(val[t], numb));
            if (wide) nl = 1 - nl;
            if (nl) xfprintf(fp, "\n");
            if (frei) strcpy(cname, "");
         }
         if (!nl) xfprintf(fp, "\n");
      }
      if (marker % 2 == 1)
      {  /* close the last intorg/intend group (if not closed) */
         marker++;
         xfprintf(fp, "    M%07d  'MARKER'                 'INTEND'\n",
            marker);
      }
      xfree(ndx);
      xfree(val);
      /* write RHS section */
      flag = 0;
      {  int nl = 1;
         strcpy(vname, frei ? "" : "RHS1");
         for (i = make_obj ? 0 : 1; i <= nrows; i++)
         {  int typx;