glpcpx.c

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

      /* parse a variable name */
      if (dsa->token != T_NAME)
         fatal(dsa, "missing variable name");
      /* find the corresponding column */
      j = find_col(dsa, dsa->image);
      /* check if the variable is already used in the linear form */
      if (dsa->map[j])
         fatal(dsa, "multiple use of variable `%s' not allowed",
            dsa->image);
      /* mark that the variable is used in the linear form */
      dsa->map[j] = 1;
      /* add new term to the linear form */
      len++, dsa->ind[len] = j, dsa->val[len] = s * coef;
      scan_token(dsa);
      /* if the next token is a sign, there is another term */
      if (dsa->token == T_PLUS || dsa->token == T_MINUS) goto loop;
      /* clear marks of the variables used in the linear form */
      for (k = 1; k <= len; k++) dsa->map[dsa->ind[k]] = 0;
      /* remove zero coefficients */
      newlen = 0;
      for (k = 1; k <= len; k++)
      {  if (dsa->val[k] != 0.0)
         {  newlen++;
            dsa->ind[newlen] = dsa->ind[k];
            dsa->val[newlen] = dsa->val[k];
         }
      }
      return newlen;
}

/*----------------------------------------------------------------------
-- parse_objective - parse objective function.
--
-- This routine parses definition of the objective function using the
-- following syntax:
--
-- <obj sense> ::= minimize | minimum | min | maximize | maximum | max
-- <obj name> ::= <empty> | <symbolic name> :
-- <obj function> ::= <obj sense> <obj name> <linear form> */

static void parse_objective(struct dsa *dsa)
{     /* parse objective sense */
      int k, len;
      /* parse the keyword 'minimize' or 'maximize' */
      if (dsa->token == T_MINIMIZE)
         lpx_set_obj_dir(dsa->lp, LPX_MIN);
      else if (dsa->token == T_MAXIMIZE)
         lpx_set_obj_dir(dsa->lp, LPX_MAX);
      else
         xassert(dsa != dsa);
      scan_token(dsa);
      /* parse objective name */
      if (dsa->token == T_NAME && dsa->c == ':')
      {  /* objective name is followed by a colon */
         lpx_set_obj_name(dsa->lp, dsa->image);
         scan_token(dsa);
         xassert(dsa->token == T_COLON);
         scan_token(dsa);
      }
      else
      {  /* objective name is not specified; use default */
         lpx_set_obj_name(dsa->lp, "obj");
      }
      /* parse linear form */
      len = parse_linear_form(dsa);
      for (k = 1; k <= len; k++)
         lpx_set_obj_coef(dsa->lp, dsa->ind[k], dsa->val[k]);
      return;
}

/*----------------------------------------------------------------------
-- parse_constraints - parse constraints section.
--
-- This routine parses the constraints section using the following
-- syntax:
--
-- <row name> ::= <empty> | <symbolic name> :
-- <row sense> ::= < | <= | =< | > | >= | => | =
-- <right-hand side> ::= <numeric constant> | + <numeric constant> |
--    - <numeric constant>
-- <constraint> ::= <row name> <linear form> <row sense>
--    <right-hand side>
-- <subject to> ::= subject to | such that | st | s.t. | st.
-- <constraints section> ::= <subject to> <constraint> |
--    <constraints section> <constraint> */

static void parse_constraints(struct dsa *dsa)
{     int i, len, type;
      double s;
      /* parse the keyword 'subject to' */
      xassert(dsa->token == T_SUBJECT_TO);
      scan_token(dsa);
loop: /* create new row (constraint) */
      i = lpx_add_rows(dsa->lp, 1);
      /* parse row name */
      if (dsa->token == T_NAME && dsa->c == ':')
      {  /* row name is followed by a colon */
         if (lpx_find_row(dsa->lp, dsa->image) != 0)
            fatal(dsa, "constraint `%s' multiply defined", dsa->image);
         lpx_set_row_name(dsa->lp, i, dsa->image);
         scan_token(dsa);
         xassert(dsa->token == T_COLON);
         scan_token(dsa);
      }
      else
      {  /* row name is not specified; use default */
         char name[50];
         sprintf(name, "r.%d", dsa->count);
         lpx_set_row_name(dsa->lp, i, name);
      }
      /* parse linear form */
      len = parse_linear_form(dsa);
      lpx_set_mat_row(dsa->lp, i, len, dsa->ind, dsa->val);
      /* parse constraint sense */
      if (dsa->token == T_LE)
         type = LPX_UP, scan_token(dsa);
      else if (dsa->token == T_GE)
         type = LPX_LO, scan_token(dsa);
      else if (dsa->token == T_EQ)
         type = LPX_FX, scan_token(dsa);
      else
         fatal(dsa, "missing constraint sense");
      /* parse right-hand side */
      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;
      if (dsa->token != T_NUMBER)
         fatal(dsa, "missing right-hand side");
      switch (type)
      {  case LPX_LO:
            lpx_set_row_bnds(dsa->lp, i, LPX_LO, s * dsa->value, 0.0);
            break;
         case LPX_UP:
            lpx_set_row_bnds(dsa->lp, i, LPX_UP, 0.0, s * dsa->value);
            break;
         case LPX_FX:
            lpx_set_row_bnds(dsa->lp, i, LPX_FX, s * dsa->value, 0.0);
            break;
      }
      /* the rest of the current line must be empty */
      if (!(dsa->c == '\n' || dsa->c == EOF))
         fatal(dsa, "invalid symbol(s) beyond right-hand side");
      scan_token(dsa);
      /* if the next token is a sign, numeric constant, or a symbolic
         name, here is another constraint */
      if (dsa->token == T_PLUS || dsa->token == T_MINUS ||
         dsa->token == T_NUMBER || dsa->token == T_NAME) goto loop;
      return;
}

static void set_lower_bound(struct dsa *dsa, int j, double lb)
{     /* set upper bound of j-th variable */
      if (dsa->lb[j] != +DBL_MAX)
         xprintf(
            "%s:%d: warning: lower bound of variable `%s' redefined\n",
            dsa->fname, dsa->count, lpx_get_col_name(dsa->lp, j));
      dsa->lb[j] = lb;
      return;
}

static void set_upper_bound(struct dsa *dsa, int j, double ub)
{     /* set upper bound of j-th variable */
      if (dsa->ub[j] != -DBL_MAX)
         xprintf(
            "%s:%d: warning: upper bound of variable `%s' redefined\n",
            dsa->fname, dsa->count, lpx_get_col_name(dsa->lp, j));
      dsa->ub[j] = ub;
      return;
}

/*----------------------------------------------------------------------
-- parse_bounds - parse bounds section.
--
-- This routine parses the bounds section using the following syntax:
--
-- <variable> ::= <symbolic name>
-- <infinity> ::= infinity | inf
-- <bound> ::= <numeric constant> | + <numeric constant> |
--    - <numeric constant> | + <infinity> | - <infinity>
-- <lt> ::= < | <= | =<
-- <gt> ::= > | >= | =>
-- <bound definition> ::= <bound> <lt> <variable> <lt> <bound> |
--    <bound> <lt> <variable> | <variable> <lt> <bound> |
--    <variable> <gt> <bound> | <variable> = <bound> | <variable> free
-- <bounds> ::= bounds | bound
-- <bounds section> ::= <bounds> |
--    <bounds section> <bound definition> */

static void parse_bounds(struct dsa *dsa)
{     int j, lb_flag;
      double lb, s;
      /* parse the keyword 'bounds' */
      xassert(dsa->token == T_BOUNDS);
      scan_token(dsa);
loop: /* bound definition can start with a sign, numeric constant, or
         a symbolic name */
      if (!(dsa->token == T_PLUS || dsa->token == T_MINUS ||
            dsa->token == T_NUMBER || dsa->token == T_NAME)) goto done;
      /* parse bound definition */
      if (dsa->token == T_PLUS || dsa->token == T_MINUS)
      {  /* parse signed lower bound */
         lb_flag = 1;
         s = (dsa->token == T_PLUS ? +1.0 : -1.0);
         scan_token(dsa);
         if (dsa->token == T_NUMBER)
            lb = s * dsa->value, scan_token(dsa);
         else if (the_same(dsa->image, "infinity") ||
                  the_same(dsa->image, "inf"))
         {  if (s > 0.0)
               fatal(dsa, "invalid use of `+inf' as lower bound");
            lb = -DBL_MAX, scan_token(dsa);
         }
         else
            fatal(dsa, "missing lower bound");
      }
      else if (dsa->token == T_NUMBER)
      {  /* parse unsigned lower bound */
         lb_flag = 1;
         lb = dsa->value, scan_token(dsa);
      }
      else
      {  /* lower bound is not specified */
         lb_flag = 0;
      }
      /* parse the token that should follow the lower bound */
      if (lb_flag)
      {  if (dsa->token != T_LE)
            fatal(dsa, "missing `<', `<=', or `=<' after lower bound");
         scan_token(dsa);
      }
      /* parse variable name */
      if (dsa->token != T_NAME)
         fatal(dsa, "missing variable name");
      j = find_col(dsa, dsa->image);
      /* set lower bound */
      if (lb_flag) set_lower_bound(dsa, j, lb);
      scan_token(dsa);
      /* parse the context that follows the variable name */
      if (dsa->token == T_LE)
      {  /* parse upper bound */
         scan_token(dsa);
         if (dsa->token == T_PLUS || dsa->token == T_MINUS)
         {  /* parse signed upper bound */
            s = (dsa->token == T_PLUS ? +1.0 : -1.0);
            scan_token(dsa);
            if (dsa->token == T_NUMBER)
            {  set_upper_bound(dsa, j, s * dsa->value);
               scan_token(dsa);
            }
            else if (the_same(dsa->image, "infinity") ||
                     the_same(dsa->image, "inf"))
            {  if (s < 0.0)
                  fatal(dsa, "invalid use of `-inf' as upper bound");
               set_upper_bound(dsa, j, +DBL_MAX);
               scan_token(dsa);
            }
            else
               fatal(dsa, "missing upper bound");
         }
         else if (dsa->token == T_NUMBER)
         {  /* parse unsigned upper bound */
            set_upper_bound(dsa, j, dsa->value);
            scan_token(dsa);
         }
         else
            fatal(dsa, "missing upper bound");
      }
      else if (dsa->token == T_GE)
      {  /* parse lower bound */
         if (lb_flag)
         {  /* the context '... <= x >= ...' is invalid */
            fatal(dsa, "invalid bound definition");
         }
         scan_token(dsa);
         if (dsa->token == T_PLUS || dsa->token == T_MINUS)
         {  /* parse signed lower bound */
            s = (dsa->token == T_PLUS ? +1.0 : -1.0);
            scan_token(dsa);
            if (dsa->token == T_NUMBER)
            {  set_lower_bound(dsa, j, s * dsa->value);
               scan_token(dsa);
            }
            else if (the_same(dsa->image, "infinity") ||
                     the_same(dsa->image, "inf") == 0)
            {  if (s > 0.0)
                  fatal(dsa, "invalid use of `+inf' as lower bound");
               set_lower_bound(dsa, j, -DBL_MAX);
               scan_token(dsa);
            }
            else
               fatal(dsa, "missing lower bound");
         }
         else if (dsa->token == T_NUMBER)
         {  /* parse unsigned lower bound */
            set_lower_bound(dsa, j, dsa->value);
            scan_token(dsa);
         }
         else
            fatal(dsa, "missing lower bound");
      }
      else if (dsa->token == T_EQ)
      {  /* parse fixed value */
         if (lb_flag)
         {  /* the context '... <= x = ...' is invalid */
            fatal(dsa, "invalid bound definition");
         }
         scan_token(dsa);
         if (dsa->token == T_PLUS || dsa->token == T_MINUS)
         {  /* parse signed fixed value */
            s = (dsa->token == T_PLUS ? +1.0 : -1.0);
            scan_token(dsa);
            if (dsa->token == T_NUMBER)
            {  set_lower_bound(dsa, j, s * dsa->value);
               set_upper_bound(dsa, j, s * dsa->value);
               scan_token(dsa);
            }
            else
               fatal(dsa, "missing fixed value");
         }
         else if (dsa->token == T_NUMBER)
         {  /* parse unsigned fixed value */
            set_lower_bound(dsa, j, dsa->value);
            set_upper_bound(dsa, j, dsa->value);
            scan_token(dsa);
         }
         else
            fatal(dsa, "missing fixed value");
      }
      else if (the_same(dsa->image, "free"))
      {  /* parse the keyword 'free' */
         if (lb_flag)
         {  /* the context '... <= x free ...' is invalid */
            fatal(dsa, "invalid bound definition");
         }
         set_lower_bound(dsa, j, -DBL_MAX);
         set_upper_bound(dsa, j, +DBL_MAX);
         scan_token(dsa);
      }
      else if (!lb_flag)
      {  /* neither lower nor upper bounds are specified */
         fatal(dsa, "invalid bound definition");
      }
      goto loop;
done: return;
}

/*----------------------------------------------------------------------
-- parse_integer - parse general, integer, or binary section.
--
-- <variable> ::= <symbolic name>
-- <general> ::= general | generals | gen
-- <integer> ::= integer | integers | int
-- <binary> ::= binary | binaries | bin
-- <section head> ::= <general> <integer> <binary>
-- <additional section> ::= <section head> |
--    <additional section> <variable> */

static void parse_integer(struct dsa *dsa)
{     int j, binary;
      /* parse the keyword 'general', 'integer', or 'binary' */
      if (dsa->token == T_GENERAL)
         binary = 0, scan_token(dsa);
      else if (dsa->token == T_INTEGER)
         binary = 0, scan_token(dsa);
      else if (dsa->token == T_BINARY)
         binary = 1, scan_token(dsa);
      else
         xassert(dsa != dsa);
      /* parse list of variables (may be empty) */
      while (dsa->token == T_NAME)
      {  /* find the corresponding column */
         j = find_col(dsa, dsa->image);
         /* change kind of the variable */
#if 0
         lpx_set_class(dsa->lp, LPX_MIP);
#endif
         lpx_set_col_kind(dsa->lp, j, LPX_IV);
         /* set 0-1 bounds for the binary variable */
         if (binary)
         {  set_lower_bound(dsa, j, 0.0);
            set_upper_bound(dsa, j, 1.0);
         }
         scan_token(dsa);
      }
      return;
}

int read_cpxlp(glp_prob *lp, const char *fname)
{     /* read problem data in CPLEX LP format */
      struct dsa _dsa, *dsa = &_dsa;
      glp_erase_prob(lp);
      if (setjmp(dsa->jump)) goto fail;
      dsa->lp = lp;
      dsa->fname = fname;
      dsa->fp = NULL;