glpmps01.c

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

/* glpmps01.c (reading/writing data files in fixed 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_mps - read problem data in fixed MPS format.
--
-- *Synopsis*
--
-- #include "glpmps.h"
-- int read_mps(LPX *lp, const char *fname);
--
-- *Description*
--
-- The routine read_mps reads LP/MIP problem data in fixed 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;
      /* card count */
      char card[80+1];
      /* card image */
      char f1[2+1], f2[8+1], f3[8+1], f4[12+1], f5[8+1], f6[12+1];
      /* data card fields */
      int obj;
      /* ordinal number of free (unbounded) row used as the objective
         function */
};

static int read_card(struct dsa *dsa)
{     /* read image of 80-column punched card from input file */
      int j, c;
loop: dsa->count++;
      memset(dsa->card, ' ', 80), dsa->card[80] = '\0';
      j = 0;
      for (;;)
      {  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 (j == 0)
               xprintf("%s:%d: unexpected EOF\n",
                  dsa->fname, dsa->count);
            else
               xprintf("%s:%d: missing final NL\n",
                  dsa->fname, dsa->count);
            goto fail;
         }
         if (c == '\r') continue;
         if (c == '\n') break;
         if (iscntrl(c))
         {  xprintf("%s:%d: invalid control character 0x%02X\n",
               dsa->fname, dsa->count, c);
            goto fail;
         }
         if (j == 80)
         {  xprintf("%s:%d: card image exceeds 80 chars\n",
               dsa->fname, dsa->count);
            goto fail;
         }
         dsa->card[j++] = (char)c;
      }
      /* asterisk in the first column begins a comment */
      if (dsa->card[0] == '*') goto loop;
      return 0;
fail: return 1;
}

static int blank = '_';
/* character code to replace blanks in symbolic names; it may be any
   printable ASCII character (including blank) or '\0', in which case
   all blanks are simply removed */

static void adjust_name(char name[8+1])
{     /* adjust symbolic name by replacing or removing blanks */
      if (blank == '\0')
      {  /* remove all blanks */
         strspx(name);
      }
      else
      {  int k;
         /* remove trailing blanks */
         strtrim(name);
         /* and replace remaining blanks by given character */
         for (k = 0; name[k] != '\0'; k++)
            if (name[k] == ' ') name[k] = (char)blank;
      }
      return;
}

static int split_card(struct dsa *dsa)
{     /* split data card into six fields */
      /* column 1 must be blank */
      xassert(dsa->card[0] == ' ');
      /* scan field 1 (code) in columns 2-3 */
      memcpy(dsa->f1, dsa->card+1, 2);
      dsa->f1[2] = '\0'; strspx(dsa->f1);
      /* column 4 must be blank */
      if (dsa->card[3] != ' ')
      {  xprintf("%s:%d: invalid data card; column 4 must be blank\n",
            dsa->fname, dsa->count);
         goto fail;
      }
      /* scan field 2 (name) in columns 5-12 */
      memcpy(dsa->f2, dsa->card+4, 8);
      dsa->f2[8] = '\0'; adjust_name(dsa->f2);
      /* columns 13-14 must be blank */
      if (memcmp(dsa->card+12, "  ", 2) != 0)
      {  xprintf("%s:%d: invalid data card; columns 13-14 must be blank"
            "\n", dsa->fname, dsa->count);
         goto fail;
      }
      /* dollar sign in column 15 begins a comment */
      if (dsa->card[14] == '$')
      {  dsa->f3[0] = dsa->f4[0] = dsa->f5[0] = dsa->f6[0] = '\0';
         goto done;
      }
      /* scan field 3 (name) in columns 15-22 */
      memcpy(dsa->f3, dsa->card+14, 8);
      dsa->f3[8] = '\0'; adjust_name(dsa->f3);
      /* columns 23-24 must be blank */
      if (memcmp(dsa->card+22, "  ", 2) != 0)
      {  xprintf("%s:%d: invalid data card; columns 23-24 must be blank"
            "\n", dsa->fname, dsa->count);
         goto fail;
      }
      /* scan field 4 (number) in columns 25-36 */
      memcpy(dsa->f4, dsa->card+24, 12);
      dsa->f4[12] = '\0'; strspx(dsa->f4);
      /* columns 37-39 must be blank */
      if (memcmp(dsa->card+36, "   ", 3) != 0)
      {  xprintf("%s:%d: invalid data card; columns 37-39 must be blank"
            "\n", dsa->fname, dsa->count);
         goto fail;
      }
      /* dollar sign in column 40 begins a comment */
      if (dsa->card[39] == '$')
      {  dsa->f5[0] = dsa->f6[0] = '\0';
         goto done;
      }
      /* scan field 5 (name) in columns 40-47 */
      memcpy(dsa->f5, dsa->card+39, 8);
      dsa->f5[8] = '\0'; adjust_name(dsa->f5);
      /* columns 48-49 must be blank */
      if (memcmp(dsa->card+47, "  ", 2) != 0)
      {  xprintf("%s:%d: invalid data card; columns 48-49 must be blank"
            "\n", dsa->fname, dsa->count);
         goto fail;
      }
      /* scan field 6 (number) in columns 50-61 */
      memcpy(dsa->f6, dsa->card+49, 12);
      dsa->f6[12] = '\0'; strspx(dsa->f6);
      /* columns 62-72 must be blank */
      if (memcmp(dsa->card+61, "           ", 11) != 0)
      {  xprintf("%s:%d: invalid data card; columns 62-72 must be blank"
            "\n", dsa->fname, dsa->count);
         goto fail;
      }
done: return 0;
fail: return 1;
}

static int read_rows(struct dsa *dsa)
{     /* process data cards in ROWS section */
      int i, type;
loop: /* read and split next data card */
      if (read_card(dsa)) goto fail;
      if (dsa->card[0] != ' ') goto done;
      if (split_card(dsa)) goto fail;
      /* create new row */
      i = lpx_add_rows(dsa->lp, 1);
      /* scan row type in field 1 */
      if (dsa->f1[0] == '\0')
      {  xprintf("%s:%d: missing row type in field 1\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      else if (strcmp(dsa->f1, "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->f1, "L") == 0)
         type = LPX_UP;
      else if (strcmp(dsa->f1, "G") == 0)
         type = LPX_LO;
      else if (strcmp(dsa->f1, "E") == 0)
         type = LPX_FX;
      else
      {  xprintf("%s:%d: invalid row type in field 1\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      lpx_set_row_bnds(dsa->lp, i, type, 0.0, 0.0);
      /* scan row name in field 2 */
      if (dsa->f2[0] == '\0')
      {  xprintf("%s:%d: missing row name in field 2\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      if (lpx_find_row(dsa->lp, dsa->f2) != 0)
      {  xprintf("%s:%d: row %s multiply specified\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      lpx_set_row_name(dsa->lp, i, dsa->f2);
      if (dsa->obj == i) lpx_set_obj_name(dsa->lp, dsa->f2);
      /* fields 3-6 must be blank */
      if (!(dsa->f3[0] == '\0' && dsa->f4[0] == '\0' &&
            dsa->f5[0] == '\0' && dsa->f6[0] == '\0'))
      {  xprintf("%s:%d: invalid data card; fields 3-6 must be blank\n",
            dsa->fname, dsa->count);
         goto fail;
      }
      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 cards in COLUMNS section */
      int i, j = 0, k, len = 0, m, marker = 0, *map, *ind;
      double *aij, temp;
      /* 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: /* read and split next data card */
      if (read_card(dsa)) goto fail;
      if (dsa->card[0] != ' ') goto done;
      if (split_card(dsa)) goto fail;
      /* field 1 must be blank */
      if (dsa->f1[0] != '\0')
      {  xprintf("%s:%d: invalid data card; field 1 must be blank\n",
            dsa->fname, dsa->count);
         goto fail;
      }
      /* scan optional INTORG/INTEND marker */
      if (strcmp(dsa->f3, "'MARKER'") == 0)
      {  /* fields 4 and 6 must be blank */
         if (!(dsa->f4[0] == '\0' && dsa->f6[0] == '\0'))
         {  xprintf("%s:%d: invalid data card; fields 4 and 6 must be b"
               "lank\n", dsa->fname, dsa->count);
            goto fail;
         }
         /* scan marker name in field 2 */
         if (dsa->f2[0] == '\0')
         {  xprintf("%s:%d: missing marker name in field 2\n",
               dsa->fname, dsa->count);
            goto fail;
         }
         /* scan marker type in field 5 */
         if (dsa->f5[0] == '\0')
         {  xprintf("%s:%d: missing marker type in field 5\n",
               dsa->fname, dsa->count);
            goto fail;
         }
         else if (strcmp(dsa->f5, "'INTORG'") == 0)
            marker = 1;
         else if (strcmp(dsa->f5, "'INTEND'") == 0)
            marker = 0;
         else
         {  xprintf("%s:%d: invalid marker type in field 5\n",
               dsa->fname, dsa->count);
            goto fail;
         }
         goto loop;
      }
      /* scan column name in field 2 */
      if (dsa->f2[0] == '\0')
      {  if (j == 0)
         {  xprintf("%s:%d: missing column name in field 2\n",
               dsa->fname, dsa->count);
            goto fail;
         }
         /* still the current column */
         goto skip;
      }
      if (j != 0 && strcmp(lpx_get_col_name(dsa->lp, j), dsa->f2) == 0)
      {  /* still the current column */
         goto skip;
      }
      /* 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, dsa->f2) != 0)
      {  xprintf("%s:%d: column %s multiply specified\n", dsa->fname,
            dsa->count, dsa->f2);
         goto fail;
      }
      j = lpx_add_cols(dsa->lp, 1);
      lpx_set_col_name(dsa->lp, j, dsa->f2);
      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);
skip: /* scan row name and coefficient in fields 3 and 4 */
      if (dsa->f3[0] == '\0')
      {  xprintf("%s:%d: missing row name in field 3\n", dsa->fname,
            dsa->count);
         goto fail;
      }
      i = lpx_find_row(dsa->lp, dsa->f3);
      if (i == 0)
      {  xprintf("%s:%d: row %s not found\n", dsa->fname, dsa->count,
            dsa->f3);
         goto fail;