glpcpx.c

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

/* glpcpx.c (reading/writing data files in CPLEX LP 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/>.
***********************************************************************/

#define _GLPSTD_ERRNO
#define _GLPSTD_STDIO
#include "glpcpx.h"

/*----------------------------------------------------------------------
-- read_cpxlp - read problem data in CPLEX LP format.
--
-- *Synopsis*
--
-- #include "glpcpx.h"
-- int read_cpxlp(glp_prob *lp, const char *fname);
--
-- *Description*
--
-- The routine read_cpxlp reads LP/MIP problem data in CPLEX LP 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 lpx_read_cpxlp routine */
      jmp_buf jump;
      /* label used for non-local go to in case of error */
      LPX *lp;
      /* LP/MIP problem object */
      const char *fname;
      /* name of input text file */
      FILE *fp;
      /* stream assigned to input text file */
      int count;
      /* line count */
      int c;
      /* current character or EOF */
      int token;
      /* code of current token: */
#define T_EOF        0  /* end of file */
#define T_MINIMIZE   1  /* keyword 'minimize' */
#define T_MAXIMIZE   2  /* keyword 'maximize' */
#define T_SUBJECT_TO 3  /* keyword 'subject to' */
#define T_BOUNDS     4  /* keyword 'bounds' */
#define T_GENERAL    5  /* keyword 'general' */
#define T_INTEGER    6  /* keyword 'integer' */
#define T_BINARY     7  /* keyword 'binary' */
#define T_END        8  /* keyword 'end' */
#define T_NAME       9  /* symbolic name */
#define T_NUMBER     10 /* numeric constant */
#define T_PLUS       11 /* delimiter '+' */
#define T_MINUS      12 /* delimiter '-' */
#define T_COLON      13 /* delimiter ':' */
#define T_LE         14 /* delimiter '<=' */
#define T_GE         15 /* delimiter '>=' */
#define T_EQ         16 /* delimiter '=' */
      char image[255+1];
      /* image of current token */
      int imlen;
      /* length of token image */
      double value;
      /* value of numeric constant */
      int n_max;
      /* length of the following five arrays (enlarged automatically,
         if necessary) */
      int *map; /* int map[1+n_max]; */
      int *ind; /* int ind[1+n_max]; */
      double *val; /* double val[1+n_max]; */
      /* working arrays used for constructing linear forms */
      double *lb; /* double lb[1+n_max]; */
      double *ub; /* double ub[1+n_max]; */
      /* lower and upper bounds of variables (columns) */
};

#define CHAR_SET "!\"#$%&()/,.;?@_`'{}|~"
/* characters which may appear in symbolic names */

static void fatal(struct dsa *dsa, char *fmt, ...)
{     /* print error message and terminate processing */
      va_list arg;
      char msg[4095+1];
      va_start(arg, fmt);
      vsprintf(msg, fmt, arg);
      xassert(strlen(msg) <= 4095);
      va_end(arg);
      xprintf("%s:%d: %s\n", dsa->fname, dsa->count, msg);
      longjmp(dsa->jump, 1);
      /* no return */
}

static void read_char(struct dsa *dsa)
{     /* read next character from input file */
      int c;
      xassert(dsa->c != EOF);
      if (dsa->c == '\n') dsa->count++;
      c = fgetc(dsa->fp);
      if (ferror(dsa->fp))
         fatal(dsa, "read error - %s", strerror(errno));
      if (feof(dsa->fp))
      {  if (dsa->c == '\n')
         {  dsa->count--;
            c = EOF;
         }
         else
         {  xprintf("%s:%d: warning: missing final LF\n",
               dsa->fname, dsa->count);
            c = '\n';
         }
      }
      else if (c == '\n')
         ;
      else if (isspace(c))
         c = ' ';
      else if (iscntrl(c))
         fatal(dsa, "invalid control character 0x%02X", c);
      dsa->c = c;
      return;
}

static void add_char(struct dsa *dsa)
{     /* append current character to current token */
      if (dsa->imlen == sizeof(dsa->image) - 1)
         fatal(dsa, "token `%.15s...' too long", dsa->image);
      dsa->image[dsa->imlen++] = (char)dsa->c;
      dsa->image[dsa->imlen] = '\0';
      read_char(dsa);
      return;
}

static int the_same(char *s1, char *s2)
{     /* compare two character strings without case sensitivity */
      for (; *s1 != '\0'; s1++, s2++)
         if (tolower((unsigned char)*s1) != tolower((unsigned char)*s2))
            return 0;
      return 1;
}

static void scan_token(struct dsa *dsa)
{     /* scan next token */
      int flag;
      dsa->token = -1;
      dsa->image[0] = '\0';
      dsa->imlen = 0;
      dsa->value = 0.0;
loop: flag = 0;
      /* skip non-significant characters */
      while (dsa->c == ' ') read_char(dsa);
      /* recognize and scan current token */
      if (dsa->c == EOF)
         dsa->token = T_EOF;
      else if (dsa->c == '\n')
      {  read_char(dsa);
         /* if the next character is letter, it may begin a keyword */
         if (isalpha(dsa->c))
         {  flag = 1;
            goto name;
         }
         goto loop;
      }
      else if (dsa->c == '\\')
      {  /* comment; ignore everything until end-of-line */
         while (dsa->c != '\n') read_char(dsa);
         goto loop;
      }
      else if (isalpha(dsa->c) || dsa->c != '.' && strchr(CHAR_SET,
         dsa->c) != NULL)
name: {  /* symbolic name */
         dsa->token = T_NAME;
         while (isalnum(dsa->c) || strchr(CHAR_SET, dsa->c) != NULL)
            add_char(dsa);
         if (flag)
         {  /* check for keyword */
            if (the_same(dsa->image, "minimize"))
               dsa->token = T_MINIMIZE;
            else if (the_same(dsa->image, "minimum"))
               dsa->token = T_MINIMIZE;
            else if (the_same(dsa->image, "min"))
               dsa->token = T_MINIMIZE;
            else if (the_same(dsa->image, "maximize"))
               dsa->token = T_MAXIMIZE;
            else if (the_same(dsa->image, "maximum"))
               dsa->token = T_MAXIMIZE;
            else if (the_same(dsa->image, "max"))
               dsa->token = T_MAXIMIZE;
            else if (the_same(dsa->image, "subject"))
            {  if (dsa->c == ' ')
               {  read_char(dsa);
                  if (tolower(dsa->c) == 't')
                  {  dsa->token = T_SUBJECT_TO;
                     dsa->image[dsa->imlen++] = ' ';
                     dsa->image[dsa->imlen] = '\0';
                     add_char(dsa);
                     if (tolower(dsa->c) != 'o')
                        fatal(dsa, "keyword `subject to' incomplete");
                     add_char(dsa);
                     if (isalpha(dsa->c))
                        fatal(dsa, "keyword `%s%c...' not recognized",
                           dsa->image, dsa->c);
                  }
               }
            }
            else if (the_same(dsa->image, "such"))
            {  if (dsa->c == ' ')
               {  read_char(dsa);
                  if (tolower(dsa->c) == 't')
                  {  dsa->token = T_SUBJECT_TO;
                     dsa->image[dsa->imlen++] = ' ';
                     dsa->image[dsa->imlen] = '\0';
                     add_char(dsa);
                     if (tolower(dsa->c) != 'h')
err:                    fatal(dsa, "keyword `such that' incomplete");
                     add_char(dsa);
                     if (tolower(dsa->c) != 'a') goto err;
                     add_char(dsa);
                     if (tolower(dsa->c) != 't') goto err;
                     add_char(dsa);
                     if (isalpha(dsa->c))
                        fatal(dsa, "keyword `%s%c...' not recognized",
                           dsa->image, dsa->c);
                  }
               }
            }
            else if (the_same(dsa->image, "st"))
               dsa->token = T_SUBJECT_TO;
            else if (the_same(dsa->image, "s.t."))
               dsa->token = T_SUBJECT_TO;
            else if (the_same(dsa->image, "st."))
               dsa->token = T_SUBJECT_TO;
            else if (the_same(dsa->image, "bounds"))
               dsa->token = T_BOUNDS;
            else if (the_same(dsa->image, "bound"))
               dsa->token = T_BOUNDS;
            else if (the_same(dsa->image, "general"))
               dsa->token = T_GENERAL;
            else if (the_same(dsa->image, "generals"))
               dsa->token = T_GENERAL;
            else if (the_same(dsa->image, "gen"))
               dsa->token = T_GENERAL;
            else if (the_same(dsa->image, "integer"))
               dsa->token = T_INTEGER;
            else if (the_same(dsa->image, "integers"))
               dsa->token = T_INTEGER;
            else if (the_same(dsa->image, "int"))
              dsa->token = T_INTEGER;
            else if (the_same(dsa->image, "binary"))
               dsa->token = T_BINARY;
            else if (the_same(dsa->image, "binaries"))
               dsa->token = T_BINARY;
            else if (the_same(dsa->image, "bin"))
               dsa->token = T_BINARY;
            else if (the_same(dsa->image, "end"))
               dsa->token = T_END;
         }
      }
      else if (isdigit(dsa->c) || dsa->c == '.')
      {  /* numeric constant */
         dsa->token = T_NUMBER;
         /* scan integer part */
         while (isdigit(dsa->c)) add_char(dsa);
         /* scan optional fractional part (it is mandatory, if there is
            no integer part) */
         if (dsa->c == '.')
         {  add_char(dsa);
            if (dsa->imlen == 1 && !isdigit(dsa->c))
               fatal(dsa, "invalid use of decimal point");
            while (isdigit(dsa->c)) add_char(dsa);
         }
         /* scan optional decimal exponent */
         if (dsa->c == 'e' || dsa->c == 'E')
         {  add_char(dsa);
            if (dsa->c == '+' || dsa->c == '-') add_char(dsa);
            if (!isdigit(dsa->c))
               fatal(dsa, "numeric constant `%s' incomplete",
                  dsa->image);
            while (isdigit(dsa->c)) add_char(dsa);
         }
         /* convert the numeric constant to floating-point */
         if (str2num(dsa->image, &dsa->value))
            fatal(dsa, "numeric constant `%s' out of range",
               dsa->image);
      }
      else if (dsa->c == '+')
         dsa->token = T_PLUS, add_char(dsa);
      else if (dsa->c == '-')
         dsa->token = T_MINUS, add_char(dsa);
      else if (dsa->c == ':')
         dsa->token = T_COLON, add_char(dsa);
      else if (dsa->c == '<')
      {  dsa->token = T_LE, add_char(dsa);
         if (dsa->c == '=') add_char(dsa);
      }
      else if (dsa->c == '>')
      {  dsa->token = T_GE, add_char(dsa);
         if (dsa->c == '=') add_char(dsa);
      }
      else if (dsa->c == '=')
      {  dsa->token = T_EQ, add_char(dsa);
         if (dsa->c == '<')
            dsa->token = T_LE, add_char(dsa);
         else if (dsa->c == '>')
            dsa->token = T_GE, add_char(dsa);
      }
      else
         fatal(dsa, "character `%c' not recognized", dsa->c);
      /* skip non-significant characters */
      while (dsa->c == ' ') read_char(dsa);
      return;
}

static int find_col(struct dsa *dsa, char *name)
{     /* find column by its symbolic name */
      int j;
      j = lpx_find_col(dsa->lp, name);
      if (j == 0)
      {  /* not found; create new column */
         j = lpx_add_cols(dsa->lp, 1);
         lpx_set_col_name(dsa->lp, j, name);
         /* enlarge auxiliary arrays, if necessary */
         if (dsa->n_max < j)
         {  int n_max = dsa->n_max;
            int *map = dsa->map;
            int *ind = dsa->ind;
            double *val = dsa->val;
            double *lb = dsa->lb;
            double *ub = dsa->ub;
            dsa->n_max += dsa->n_max;
            dsa->map = xcalloc(1+dsa->n_max, sizeof(int));
            memset(&dsa->map[1], 0, dsa->n_max * sizeof(int));
            memcpy(&dsa->map[1], &map[1], n_max * sizeof(int));
            xfree(map);
            dsa->ind = xcalloc(1+dsa->n_max, sizeof(int));
            memcpy(&dsa->ind[1], &ind[1], n_max * sizeof(int));
            xfree(ind);
            dsa->val = xcalloc(1+dsa->n_max, sizeof(double));
            memcpy(&dsa->val[1], &val[1], n_max * sizeof(double));
            xfree(val);
            dsa->lb = xcalloc(1+dsa->n_max, sizeof(double));
            memcpy(&dsa->lb[1], &lb[1], n_max * sizeof(double));
            xfree(lb);
            dsa->ub = xcalloc(1+dsa->n_max, sizeof(double));
            memcpy(&dsa->ub[1], &ub[1], n_max * sizeof(double));
            xfree(ub);
         }
         dsa->lb[j] = +DBL_MAX, dsa->ub[j] = -DBL_MAX;
      }
      return j;
}

/*----------------------------------------------------------------------
-- parse_linear_form - parse linear form.
--
-- This routine parses linear form using the following syntax:
--
-- <variable> ::= <symbolic name>
-- <coefficient> ::= <numeric constant>
-- <term> ::= <variable> | <numeric constant> <variable>
-- <linear form> ::= <term> | + <term> | - <term> |
--    <linear form> + <term> | <linear form> - <term>
--
-- The routine returns the number of terms in the linear form. */

static int parse_linear_form(struct dsa *dsa)
{     int j, k, len = 0, newlen;
      double s, coef;
loop: /* parse an optional sign */
      if (dsa->token == T_PLUS)
         s = +1.0, scan_token(dsa);
      else if (dsa->token == T_MINUS)
         s = -1.0, scan_token(dsa);
      else
         s = +1.0;
      /* parse an optional coefficient */
      if (dsa->token == T_NUMBER)
         coef = dsa->value, scan_token(dsa);
      else
         coef = 1.0;