glpmps02.c

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

/* glpmps02.c (reading/writing data files in free MPS format) */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  Copyright (C) 2000,01,02,03,04,05,06,07,08,2009 Andrew Makhorin,
*  Department for Applied Informatics, Moscow Aviation Institute,
*  Moscow, Russia. All rights reserved. E-mail: <[e-mail]>.
*
*  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 "glpmps.h"
#define strerror(errno) xerrmsg()

/*----------------------------------------------------------------------
-- read_freemps - read problem data in free MPS format.
--
-- *Synopsis*
--
-- #include "glpmps.h"
-- int read_freemps(LPX *lp, const char *fname);
--
-- *Description*
--
-- The routine read_freemps reads LP/MIP problem data in free MPS
-- format from an input 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. */

struct dsa
{     /* working area used by MPS routines */
      LPX *lp;
      /* LP/MIP problem object */
      const char *fname;
      /* name of input text file */
      XFILE *fp;
      /* stream assigned to input text file */
      int count;
      /* line count */
      int c;
      /* current character */
      char item[255+1];
      /* current item */
      int obj;
      /* ordinal number of free (unbounded) row used as the objective
         function */
};

static int read_c(struct dsa *dsa)
{     /* read character from input file */
      int c;
      if (dsa->c == '\n') dsa->count++;
      c = xfgetc(dsa->fp);
      if (xferror(dsa->fp))
      {  xprintf("%s:%d: read error - %s\n", dsa->fname, dsa->count,
            strerror(errno));
         goto fail;
      }
      if (xfeof(dsa->fp))
      {  if (dsa->c == '\n')
         {  xprintf("%s:%d: unexpected EOF\n", dsa->fname, dsa->count);
            goto fail;
         }
         c = '\n';
      }
      if (c == '\n')
         ;
      else if (isspace(c))
         c = ' ';
      else if (iscntrl(c))
      {  xprintf("%s:%d: invalid control character 0x%02X\n",
            dsa->fname, dsa->count, c);
         goto fail;
      }
      dsa->c = c;
      return 0;
fail: return 1;
}

static int read_char(struct dsa *dsa)
{     /* read character from input file and skip comment lines */
      int nl;
loop: nl = (dsa->c == '\n');
      if (read_c(dsa)) goto fail;
      if (nl && dsa->c == '*')
      {  while (dsa->c != '\n')
            if (read_c(dsa)) goto fail;
         goto loop;
      }
      return 0;
fail: return 1;
}

static int read_item(struct dsa *dsa)
{     /* read item from input file */
      /* skip uninteresting characters */
      while (dsa->c == ' ')
         if (read_char(dsa)) goto fail;
      /* scan item */
      if (dsa->c == '$')
      {  /* dollar sign begins a comment */
         while (dsa->c != '\n')
            if (read_char(dsa)) goto fail;
      }
      if (dsa->c == '\n')
      {  /* empty item indicates end of line */
         dsa->item[0] = '\0';
         if (read_char(dsa)) goto fail;
      }
      else
      {  int len = 0;
         while (!(dsa->c == ' ' || dsa->c == '\n'))
         {  if (len == sizeof(dsa->item) - 1)
            {  xprintf("%s:%d: item `%.15s...' too long\n", dsa->fname,
                  dsa->count, dsa->item);
               goto fail;
            }
            dsa->item[len++] = (char)dsa->c;
            if (read_char(dsa)) goto fail;
         }
         dsa->item[len] = '\0';
      }
      return 0;
fail: return 1;
}

static int read_rows(struct dsa *dsa)
{     /* process data lines in ROWS section */
      int i, type;
loop: /* check if there is more data lines */
      if (dsa->c != ' ') goto done;
      /* create new row */
      i = lpx_add_rows(dsa->lp, 1);
      /* scan row type */
      if (read_item(dsa)) goto fail;
      if (dsa->item[0] == '\0')
      {  xprintf("%s:%d: missing row type\n", dsa->fname, dsa->count);
         goto fail;
      }
      else if (strcmp(dsa->item, "N") == 0)
      {  type = LPX_FR;
         /* the first free (unbounded) row is used as the objective
            function */
         if (dsa->obj == 0) dsa->obj = i;
      }
      else if (strcmp(dsa->item, "L") == 0)
         type = LPX_UP;
      else if (strcmp(dsa->item, "G") == 0)
         type = LPX_LO;
      else if (strcmp(dsa->item, "E") == 0)
         type = LPX_FX;
      else
      {  xprintf("%s:%d: invalid row type\n", dsa->fname, dsa->count);
         goto fail;
      }
      lpx_set_row_bnds(dsa->lp, i, type, 0.0, 0.0);
      /* scan row name */
      if (read_item(dsa)) goto fail;
      if (dsa->item[0] == '\0')
      {  xprintf("%s:%d: missing row name\n", dsa->fname, dsa->count);
         goto fail;
      }
      lpx_set_row_name(dsa->lp, i, dsa->item);
      if (dsa->obj == i) lpx_set_obj_name(dsa->lp, dsa->item);
      /* skip remaining characters */
      while (dsa->c != '\n')
         if (read_char(dsa)) goto fail;
      if (read_item(dsa)) goto fail;
      xassert(dsa->item[0] == '\0');
      goto loop;
done: return 0;
fail: return 1;
}

static void put_column(struct dsa *dsa, int j, int len, int ind[],
      double aij[])
{     /* store j-th column to the constraint matrix */
      int k, newlen = 0;
      for (k = 1; k <= len; k++)
      {  if (aij[k] != 0.0)
         {  newlen++;
            ind[newlen] = ind[k];
            aij[newlen] = aij[k];
            if (dsa->obj == ind[newlen])
               lpx_set_obj_coef(dsa->lp, j, aij[newlen]);
         }
      }
      lpx_set_mat_col(dsa->lp, j, newlen, ind, aij);
      return;
}

static int read_columns(struct dsa *dsa)
{     /* process data lines in COLUMNS section */
      int i, j = 0, k, len = 0, m, marker = 0, *map, *ind;
      double *aij, temp;
      char cname[sizeof(dsa->item)], rname[sizeof(dsa->item)];
      /* allocate working arrays */
      m = lpx_get_num_rows(dsa->lp);
      map = xcalloc(1+m, sizeof(int));
      for (i = 1; i <= m; i++) map[i] = 0;
      ind = xcalloc(1+m, sizeof(int));
      aij = xcalloc(1+m, sizeof(double));
loop: /* check if there is more data lines */
      if (dsa->c != ' ') goto done;
      /* scan column name */
      if (read_item(dsa)) goto fail;
      if (dsa->item[0] == '\0')
      {  xprintf(
            "%s:%d: missing column name\n", dsa->fname, dsa->count);
         goto fail;
      }
      strcpy(cname, dsa->item);
      /* scan row name */
      if (read_item(dsa)) goto fail;
      if (dsa->item[0] == '\0')
      {  xprintf("%s:%d: missing row name\n", dsa->fname, dsa->count);
         goto fail;
      }
      strcpy(rname, dsa->item);
      /* scan optional INTORG/INTEND marker */
      if (strcmp(rname, "'MARKER'") == 0)
      {  if (read_item(dsa)) goto fail;
         if (dsa->item[0] == '\0')
         {  xprintf(
               "%s:%d: missing marker type\n", dsa->fname, dsa->count);
            goto fail;
         }
         else if (strcmp(dsa->item, "'INTORG'") == 0)
            marker = 1;
         else if (strcmp(dsa->item, "'INTEND'") == 0)
            marker = 0;
         else
         {  xprintf(
               "%s:%d: invalid marker type\n", dsa->fname, dsa->count);
            goto fail;
         }
         goto skip;
      }
      if (j == 0 || strcmp(lpx_get_col_name(dsa->lp, j), cname) != 0)
      {  /* new column begins, so finish the current column */
         if (j != 0)
         {  for (k = 1; k <= len; k++) map[ind[k]] = 0;
            put_column(dsa, j, len, ind, aij), len = 0;
         }
         /* create new column */
         if (lpx_find_col(dsa->lp, cname) != 0)
         {  xprintf("%s:%d: column %s multiply specified\n",
               dsa->fname, dsa->count, cname);
            goto fail;
         }
         j = lpx_add_cols(dsa->lp, 1);
         lpx_set_col_name(dsa->lp, j, cname);
         if (marker)
         {  /* lpx_set_class(dsa->lp, LPX_MIP); */
            lpx_set_col_kind(dsa->lp, j, LPX_IV);
         }
         lpx_set_col_bnds(dsa->lp, j, LPX_LO, 0.0, 0.0);
      }
      /* find row */
      i = lpx_find_row(dsa->lp, rname);
      if (i == 0)
      {  xprintf("%s:%d: row %s not found\n", dsa->fname, dsa->count,
            rname);
         goto fail;
      }
      /* scan coefficient value */
      if (read_item(dsa)) goto fail;
      if (dsa->item[0] == '\0')
      {  xprintf("%s:%d: missing coefficient value\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      if (str2num(dsa->item, &temp))
      {  xprintf("%s:%d: invalid coefficient value\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      if (map[i])
      {  xprintf("%s:%d: coefficient in row %s multiply specified\n",
            dsa->fname, dsa->count, rname);
         goto fail;
      }
      map[i] = 1, len++, ind[len] = i, aij[len] = temp;
      /* there may be another row name and coefficient value */
      if (read_item(dsa)) goto fail;
      if (dsa->item[0] == '\0') goto loop;
      strcpy(rname, dsa->item);
      /* find row */
      i = lpx_find_row(dsa->lp, rname);
      if (i == 0)
      {  xprintf("%s:%d: row %s not found\n", dsa->fname, dsa->count,
            rname);
         goto fail;
      }
      /* scan coefficient value */
      if (read_item(dsa)) goto fail;
      if (dsa->item[0] == '\0')
      {  xprintf("%s:%d: missing coefficient value\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      if (str2num(dsa->item, &temp))
      {  xprintf("%s:%d: invalid coefficient value\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      if (map[i])
      {  xprintf("%s:%d: coefficient in row %s multiply specified\n",
            dsa->fname, dsa->count, rname);
         goto fail;
      }
      map[i] = 1, len++, ind[len] = i, aij[len] = temp;
skip: /* skip remaining characters */
      while (dsa->c != '\n')
         if (read_char(dsa)) goto fail;
      if (read_item(dsa)) goto fail;
      xassert(dsa->item[0] == '\0');
      goto loop;
done: /* finish the last column */
      if (j != 0) put_column(dsa, j, len, ind, aij);
      xfree(map), xfree(ind), xfree(aij);
      return 0;
fail: xfree(map), xfree(ind), xfree(aij);
      return 1;
}

static void set_rhs(struct dsa *dsa, int i, double b)
{     /* set right-hand side for i-th row */
      switch (lpx_get_row_type(dsa->lp, i))
      {  case LPX_FR:
            if (dsa->obj == i)
               lpx_set_obj_coef(dsa->lp, 0, b);
            else if (b != 0.0)
               xprintf("%s:%d: warning: non-zero rhs for free row %s ig"
                  "nored\n", dsa->fname, dsa->count,
                  lpx_get_row_name(dsa->lp, i));
            break;
         case LPX_LO:
            lpx_set_row_bnds(dsa->lp, i, LPX_LO, b, 0.0);
            break;
         case LPX_UP:
            lpx_set_row_bnds(dsa->lp, i, LPX_UP, 0.0, b);
            break;
         case LPX_FX:
            lpx_set_row_bnds(dsa->lp, i, LPX_FX, b, b);
            break;
         default:
            xassert(dsa != dsa);
      }
      return;
}

static int read_rhs(struct dsa *dsa)
{     /* process data lines in RHS section */
      int i, m, *map;
      double temp;
      char name[sizeof(dsa->item)] = "";
      /* allocate working array */
      m = lpx_get_num_rows(dsa->lp);
      map = xcalloc(1+m, sizeof(int));
      for (i = 1; i <= m; i++) map[i] = 0;
loop: /* check if there is more data lines */
      if (dsa->c != ' ') goto done;
      /* scan rhs vector name */
      if (read_item(dsa)) goto fail;
      if (dsa->item[0] == '\0')
      {  xprintf("%s:%d: missing rhs vector name\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      if (name[0] == '\0') strcpy(name, dsa->item);
      if (strcmp(dsa->item, name) != 0)
      {  xprintf("%s:%d: at most one rhs vector allowed\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      /* scan row name */