glpcpx.c

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

      dsa->count = 0;
      dsa->c = '\n';
      dsa->token = T_EOF;
      dsa->image[0] = '\0';
      dsa->imlen = 0;
      dsa->value = 0.0;
      dsa->n_max = 100;
      dsa->map = xcalloc(1+dsa->n_max, sizeof(int));
      memset(&dsa->map[1], 0, dsa->n_max * sizeof(int));
      dsa->ind = xcalloc(1+dsa->n_max, sizeof(int));
      dsa->val = xcalloc(1+dsa->n_max, sizeof(double));
      dsa->lb = xcalloc(1+dsa->n_max, sizeof(double));
      dsa->ub = xcalloc(1+dsa->n_max, sizeof(double));
      xprintf("glp_read_lp: reading problem data from `%s'...\n",
         dsa->fname);
      dsa->fp = fopen(dsa->fname, "r");
      if (dsa->fp == NULL)
      {  xprintf("glp_read_lp: unable to open `%s' - %s\n", dsa->fname,
            strerror(errno));
         goto fail;
      }
      lpx_create_index(dsa->lp);
#if 0
      /* read very first character */
      read_char(dsa);
#endif
      /* scan very first token */
      scan_token(dsa);
      /* parse definition of the objective function */
      if (!(dsa->token == T_MINIMIZE || dsa->token == T_MAXIMIZE))
         fatal(dsa, "`minimize' or `maximize' keyword missing");
      parse_objective(dsa);
      /* parse constraints section */
      if (dsa->token != T_SUBJECT_TO)
         fatal(dsa, "constraints section missing");
      parse_constraints(dsa);
      /* parse optional bounds section */
      if (dsa->token == T_BOUNDS) parse_bounds(dsa);
      /* parse optional general, integer, and binary sections */
      while (dsa->token == T_GENERAL ||
             dsa->token == T_INTEGER ||
             dsa->token == T_BINARY) parse_integer(dsa);
      /* check for the keyword 'end' */
      if (dsa->token == T_END)
         scan_token(dsa);
      else if (dsa->token == T_EOF)
         xprintf("%s:%d: warning: keyword `end' missing\n",
            dsa->fname, dsa->count);
      else
         fatal(dsa, "symbol `%s' in wrong position", dsa->image);
      /* nothing must follow the keyword 'end' (except comments) */
      if (dsa->token != T_EOF)
         fatal(dsa, "extra symbol(s) detected beyond `end'");
      /* set bounds of variables */
      {  int j, type;
         double lb, ub;
         for (j = lpx_get_num_cols(dsa->lp); j >= 1; j--)
         {  lb = dsa->lb[j];
            ub = dsa->ub[j];
            if (lb == +DBL_MAX) lb = 0.0;      /* default lb */
            if (ub == -DBL_MAX) ub = +DBL_MAX; /* default ub */
            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);
         }
      }
      /* print some statistics */
      {  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_lp: %d row%s, %d column%s, %d non-zero%s\n",
            m, m == 1 ? "" : "s", n, n == 1 ? "" : "s", nnz, nnz == 1 ?
            "" : "s");
      }
      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_lp: %d integer column%s, %s which %s binary\n",
            ni, ni == 1 ? "" : "s", s, nb == 1 ? "is" : "are");
      }
      xprintf("glp_read_lp: %d lines were read\n", dsa->count);
      fclose(dsa->fp);
      xfree(dsa->map);
      xfree(dsa->ind);
      xfree(dsa->val);
      xfree(dsa->lb);
      xfree(dsa->ub);
      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) fclose(dsa->fp);
      if (dsa->map != NULL) xfree(dsa->map);
      if (dsa->ind != NULL) xfree(dsa->ind);
      if (dsa->val != NULL) xfree(dsa->val);
      if (dsa->lb != NULL) xfree(dsa->lb);
      if (dsa->ub != NULL) xfree(dsa->ub);
      return 1;
}

/*----------------------------------------------------------------------
-- write_cpxlp - write problem data in CPLEX LP format.
--
-- *Synopsis*
--
-- #include "glpcpx.h"
-- int write_cpxlp(glp_prob *lp, const char *fname);
--
-- *Description*
--
-- The routine write_cpxlp writes problem data in CPLEX LP 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 int check_name(char *name)
{     /* check if given name is valid for CPLEX LP format */
      int k;
      if (isdigit((unsigned char)name[0])) return 1;
      if (name[0] == '.') return 1;
      for (k = 0; name[k] != '\0'; k++)
         if (!isalnum((unsigned char)name[k]) &&
            strchr(CHAR_SET, (unsigned char)name[k]) == NULL) return 1;
      return 0; /* name is ok */
}

static void adjust_name(char *name)
{     /* try changing given name to make it valid for CPLEX LP format */
      int k;
      for (k = 0; name[k] != '\0'; k++)
      {  if (name[k] == ' ')
            name[k] = '_';
         else if (name[k] == '-')
            name[k] = '~';
         else if (name[k] == '[')
            name[k] = '(';
         else if (name[k] == ']')
            name[k] = ')';
      }
      return;
}

static char *row_name(LPX *lp, int i, char rname[255+1])
{     /* construct symbolic name of i-th row (constraint) */
      char *name;
      if (i == 0)
         name = (void *)lpx_get_obj_name(lp);
      else
         name = (void *)lpx_get_row_name(lp, i);
      if (name == NULL) goto fake;
      strcpy(rname, name);
      adjust_name(rname);
      if (check_name(rname)) goto fake;
      return rname;
fake: if (i == 0)
         strcpy(rname, "obj");
      else
         sprintf(rname, "r_%d", i);
      return rname;
}

static char *col_name(LPX *lp, int j, char cname[255+1])
{     /* construct symbolic name of j-th column (variable) */
      const char *name;
      name = lpx_get_col_name(lp, j);
      if (name == NULL) goto fake;
      strcpy(cname, name);
      adjust_name(cname);
      if (check_name(cname)) goto fake;
      return cname;
fake: sprintf(cname, "x_%d", j);
      return cname;
}

int write_cpxlp(glp_prob *lp, const char *fname)
{     /* write problem data in CPLEX LP format */
      FILE *fp;
      int nrows, ncols, i, j, t, len, typx, flag, kind, *ind;
      double lb, ub, temp, *val;
      char line[1023+1], term[1023+1], rname[255+1], cname[255+1];
      xprintf("glp_write_lp: writing problem data to `%s'...\n",
         fname);
      /* open the output text file */
      fp = fopen(fname, "w");
      if (fp == NULL)
      {  xprintf("glp_write_lp: unable to create `%s' - %s\n", fname,
            strerror(errno));
         goto fail;
      }
      /* determine the number of rows and columns */
      nrows = lpx_get_num_rows(lp);
      ncols = lpx_get_num_cols(lp);
#if 0 /* 01/II-2009 */
      /* the problem should contain at least one row and one column */
      if (!(nrows > 0 && ncols > 0))
         xerror("glp_write_lp: problem has no rows/columns\n");
#endif
      /* write problem name */
      {  const char *name = lpx_get_prob_name(lp);
         if (name == NULL) name = "Unknown";
         fprintf(fp, "\\* Problem: %s *\\\n", name);
         fprintf(fp, "\n");
      }
#if 1 /* 01/II-2009 */
      if (!(nrows > 0 && ncols > 0))
      {  fprintf(fp, "\\* WARNING: PROBLEM HAS NO ROWS/COLUMNS *\\\n");
         goto skip;
      }
#endif
      /* allocate working arrays */
      ind = xcalloc(1+ncols, sizeof(int));
      val = xcalloc(1+ncols, sizeof(double));
      /* write the objective function definition and the constraints
         section */
      for (i = 0; i <= nrows; i++)
      {  if (i == 0)
         {  switch (lpx_get_obj_dir(lp))
            {  case LPX_MIN:
                  fprintf(fp, "Minimize\n");
                  break;
               case LPX_MAX:
                  fprintf(fp, "Maximize\n");
                  break;
               default:
                  xassert(lp != lp);
            }
         }
         else if (i == 1)
         {  temp = lpx_get_obj_coef(lp, 0);
            if (temp != 0.0)
               fprintf(fp, "\\* constant term = %.*g *\\\n", DBL_DIG,
                  temp);
            fprintf(fp, "\n");
            fprintf(fp, "Subject To\n");
         }
         row_name(lp, i, rname);
         if (i == 0)
         {  len = 0;
            for (j = 1; j <= ncols; j++)
            {  temp = lpx_get_obj_coef(lp, j);
               if (temp != 0.0)
                  len++, ind[len] = j, val[len] = temp;
            }
         }
         else
         {  lpx_get_row_bnds(lp, i, &typx, &lb, &ub);
            if (typx == LPX_FR) continue;
            len = lpx_get_mat_row(lp, i, ind, val);
         }
         flag = 0;
more:    if (!flag)
            sprintf(line, " %s:", rname);
         else
            sprintf(line, " %*s ", strlen(rname), "");
         for (t = 1; t <= len; t++)
         {  col_name(lp, ind[t], cname);
            if (val[t] == +1.0)
               sprintf(term, " + %s", cname);
            else if (val[t] == -1.0)
               sprintf(term, " - %s", cname);
            else if (val[t] > 0.0)
               sprintf(term, " + %.*g %s", DBL_DIG, +val[t], cname);
            else if (val[t] < 0.0)
               sprintf(term, " - %.*g %s", DBL_DIG, -val[t], cname);
            else
               xassert(lp != lp);
            if (strlen(line) + strlen(term) > 72)
               fprintf(fp, "%s\n", line), line[0] = '\0';
            strcat(line, term);
         }
         if (len == 0)
         {  /* empty row */
            sprintf(term, " 0 %s", col_name(lp, 1, cname));
            strcat(line, term);
         }
         if (i > 0)
         {  switch (typx)
            {  case LPX_LO:
               case LPX_DB:
                  sprintf(term, " >= %.*g", DBL_DIG, lb);
                  break;
               case LPX_UP:
                  sprintf(term, " <= %.*g", DBL_DIG, ub);
                  break;
               case LPX_FX:
                  sprintf(term, " = %.*g", DBL_DIG, lb);
                  break;
               default:
                  xassert(typx != typx);
            }
            if (strlen(line) + strlen(term) > 72)
               fprintf(fp, "%s\n", line), line[0] = '\0';
            strcat(line, term);
         }
         fprintf(fp, "%s\n", line);
         if (i > 0 && typx == LPX_DB)
         {  /* double-bounded row needs a copy for its upper bound */
            flag = 1;
            typx = LPX_UP;
            goto more;
         }
      }
      /* free working arrays */
      xfree(ind);
      xfree(val);
      /* write the bounds section */
      flag = 0;
      for (j = 1; j <= ncols; j++)
      {  col_name(lp, j, cname);
         lpx_get_col_bnds(lp, j, &typx, &lb, &ub);
         if (typx == LPX_LO && lb == 0.0) continue;
         if (!flag)
         {  fprintf(fp, "\n");
            fprintf(fp, "Bounds\n");
            flag = 1;
         }
         switch (typx)
         {  case LPX_FR:
               fprintf(fp, " %s free\n", cname);
               break;
            case LPX_LO:
               fprintf(fp, " %s >= %.*g\n", cname, DBL_DIG, lb);
               break;
            case LPX_UP:
               fprintf(fp, " -inf <= %s <= %.*g\n", cname, DBL_DIG, ub);
               break;
            case LPX_DB:
               fprintf(fp, " %.*g <= %s <= %.*g\n", DBL_DIG, lb, cname,
                  DBL_DIG, ub);
               break;
            case LPX_FX:
               fprintf(fp, " %s = %.*g\n", cname, DBL_DIG, lb);
               break;
            default:
               xassert(typx != typx);
         }
      }
      /* write the general section */
      if (lpx_get_class(lp) == LPX_MIP)
      {  flag = 0;
         for (j = 1; j <= ncols; j++)
         {  kind = lpx_get_col_kind(lp, j);
            if (kind == LPX_CV) continue;
            xassert(kind == LPX_IV);
            if (!flag)
            {  fprintf(fp, "\n");
               fprintf(fp, "Generals\n");
               flag = 1;
            }
            fprintf(fp, " %s\n", col_name(lp, j, cname));
         }
      }
skip: /* write the end keyword */
      fprintf(fp, "\n");
      fprintf(fp, "End\n");
      /* close the output text file */
      fflush(fp);
      if (ferror(fp))
      {  xprintf("glp_write_lp: write error on `%s' - %s\n",
            fname, strerror(errno));
         goto fail;
      }
      fclose(fp);
      /* return to the calling program */
      return 0;
fail: /* the operation failed */
      if (fp != NULL) fclose(fp);
      return 1;
}

/* eof */