glpmpl02.c

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

/* glpmpl02.c */

/***********************************************************************
*  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_STDIO
#include "glplib.h"
#include "glpmpl.h"

/**********************************************************************/
/* * *                  PROCESSING DATA SECTION                   * * */
/**********************************************************************/

/*----------------------------------------------------------------------
-- create_slice - create slice.
--
-- This routine creates a slice, which initially has no components. */

SLICE *create_slice(MPL *mpl)
{     SLICE *slice;
      xassert(mpl == mpl);
      slice = NULL;
      return slice;
}

/*----------------------------------------------------------------------
-- expand_slice - append new component to slice.
--
-- This routine expands slice appending to it either a given symbol or
-- null component, which becomes the last component of the slice. */

SLICE *expand_slice
(     MPL *mpl,
      SLICE *slice,           /* destroyed */
      SYMBOL *sym             /* destroyed */
)
{     SLICE *tail, *temp;
      /* create a new component */
      tail = dmp_get_atom(mpl->tuples, sizeof(SLICE));
      tail->sym = sym;
      tail->next = NULL;
      /* and append it to the component list */
      if (slice == NULL)
         slice = tail;
      else
      {  for (temp = slice; temp->next != NULL; temp = temp->next);
         temp->next = tail;
      }
      return slice;
}

/*----------------------------------------------------------------------
-- slice_dimen - determine dimension of slice.
--
-- This routine returns dimension of slice, which is number of all its
-- components including null ones. */

int slice_dimen
(     MPL *mpl,
      SLICE *slice            /* not changed */
)
{     SLICE *temp;
      int dim;
      xassert(mpl == mpl);
      dim = 0;
      for (temp = slice; temp != NULL; temp = temp->next) dim++;
      return dim;
}

/*----------------------------------------------------------------------
-- slice_arity - determine arity of slice.
--
-- This routine returns arity of slice, i.e. number of null components
-- (indicated by asterisks) in the slice. */

int slice_arity
(     MPL *mpl,
      SLICE *slice            /* not changed */
)
{     SLICE *temp;
      int arity;
      xassert(mpl == mpl);
      arity = 0;
      for (temp = slice; temp != NULL; temp = temp->next)
         if (temp->sym == NULL) arity++;
      return arity;
}

/*----------------------------------------------------------------------
-- fake_slice - create fake slice of all asterisks.
--
-- This routine creates a fake slice of given dimension, which contains
-- asterisks in all components. Zero dimension is allowed. */

SLICE *fake_slice(MPL *mpl, int dim)
{     SLICE *slice;
      slice = create_slice(mpl);
      while (dim-- > 0) slice = expand_slice(mpl, slice, NULL);
      return slice;
}

/*----------------------------------------------------------------------
-- delete_slice - delete slice.
--
-- This routine deletes specified slice. */

void delete_slice
(     MPL *mpl,
      SLICE *slice            /* destroyed */
)
{     SLICE *temp;
      while (slice != NULL)
      {  temp = slice;
         slice = temp->next;
         if (temp->sym != NULL) delete_symbol(mpl, temp->sym);
xassert(sizeof(SLICE) == sizeof(TUPLE));
         dmp_free_atom(mpl->tuples, temp, sizeof(TUPLE));
      }
      return;
}

/*----------------------------------------------------------------------
-- is_number - check if current token is number.
--
-- If the current token is a number, this routine returns non-zero.
-- Otherwise zero is returned. */

int is_number(MPL *mpl)
{     return
         mpl->token == T_NUMBER;
}

/*----------------------------------------------------------------------
-- is_symbol - check if current token is symbol.
--
-- If the current token is suitable to be a symbol, the routine returns
-- non-zero. Otherwise zero is returned. */

int is_symbol(MPL *mpl)
{     return
         mpl->token == T_NUMBER ||
         mpl->token == T_SYMBOL ||
         mpl->token == T_STRING;
}

/*----------------------------------------------------------------------
-- is_literal - check if current token is given symbolic literal.
--
-- If the current token is given symbolic literal, this routine returns
-- non-zero. Otherwise zero is returned.
--
-- This routine is used on processing the data section in the same way
-- as the routine is_keyword on processing the model section. */

int is_literal(MPL *mpl, char *literal)
{     return
         is_symbol(mpl) && strcmp(mpl->image, literal) == 0;
}

/*----------------------------------------------------------------------
-- read_number - read number.
--
-- This routine reads the current token, which must be a number, and
-- returns its numeric value. */

double read_number(MPL *mpl)
{     double num;
      xassert(is_number(mpl));
      num = mpl->value;
      get_token(mpl /* <number> */);
      return num;
}

/*----------------------------------------------------------------------
-- read_symbol - read symbol.
--
-- This routine reads the current token, which must be a symbol, and
-- returns its symbolic value. */

SYMBOL *read_symbol(MPL *mpl)
{     SYMBOL *sym;
      xassert(is_symbol(mpl));
      if (is_number(mpl))
         sym = create_symbol_num(mpl, mpl->value);
      else
         sym = create_symbol_str(mpl, create_string(mpl, mpl->image));
      get_token(mpl /* <symbol> */);
      return sym;
}

/*----------------------------------------------------------------------
-- read_slice - read slice.
--
-- This routine reads slice using the syntax:
--
-- <slice> ::= [ <symbol list> ]
-- <slice> ::= ( <symbol list> )
-- <symbol list> ::= <symbol or star>
-- <symbol list> ::= <symbol list> , <symbol or star>
-- <symbol or star> ::= <symbol>
-- <symbol or star> ::= *
--
-- The bracketed form of slice is used for members of multi-dimensional
-- objects while the parenthesized form is used for elemental sets. */

SLICE *read_slice
(     MPL *mpl,
      char *name,             /* not changed */
      int dim
)
{     SLICE *slice;
      int close;
      xassert(name != NULL);
      switch (mpl->token)
      {  case T_LBRACKET:
            close = T_RBRACKET;
            break;
         case T_LEFT:
            xassert(dim > 0);
            close = T_RIGHT;
            break;
         default:
            xassert(mpl != mpl);
      }
      if (dim == 0)
         error(mpl, "%s cannot be subscripted", name);
      get_token(mpl /* ( | [ */);
      /* read slice components */
      slice = create_slice(mpl);
      for (;;)
      {  /* the current token must be a symbol or asterisk */
         if (is_symbol(mpl))
            slice = expand_slice(mpl, slice, read_symbol(mpl));
         else if (mpl->token == T_ASTERISK)
         {  slice = expand_slice(mpl, slice, NULL);
            get_token(mpl /* * */);
         }
         else
            error(mpl, "number, symbol, or asterisk missing where expec"
               "ted");
         /* check a token that follows the symbol */
         if (mpl->token == T_COMMA)
            get_token(mpl /* , */);
         else if (mpl->token == close)
            break;
         else
            error(mpl, "syntax error in slice");
      }
      /* number of slice components must be the same as the appropriate
         dimension */
      if (slice_dimen(mpl, slice) != dim)
      {  switch (close)
         {  case T_RBRACKET:
               error(mpl, "%s must have %d subscript%s, not %d", name,
                  dim, dim == 1 ? "" : "s", slice_dimen(mpl, slice));
               break;
            case T_RIGHT:
               error(mpl, "%s has dimension %d, not %d", name, dim,
                  slice_dimen(mpl, slice));
               break;
            default:
               xassert(close != close);
         }
      }
      get_token(mpl /* ) | ] */);
      return slice;
}

/*----------------------------------------------------------------------
-- select_set - select set to saturate it with elemental sets.
--
-- This routine selects set to saturate it with elemental sets provided
-- in the data section. */

SET *select_set
(     MPL *mpl,
      char *name              /* not changed */
)
{     SET *set;
      AVLNODE *node;
      xassert(name != NULL);
      node = avl_find_node(mpl->tree, name);
      if (node == NULL || avl_get_node_type(node) != A_SET)
         error(mpl, "%s not a set", name);
      set = (SET *)avl_get_node_link(node);
      if (set->assign != NULL || set->gadget != NULL)
         error(mpl, "%s needs no data", name);
      set->data = 1;
      return set;
}

/*----------------------------------------------------------------------
-- simple_format - read set data block in simple format.
--
-- This routine reads set data block using the syntax:
--
-- <simple format> ::= <symbol> , <symbol> , ... , <symbol>
--
-- where <symbols> are used to construct a complete n-tuple, which is
-- included in elemental set assigned to the set member. Commae between
-- symbols are optional and may be omitted anywhere.
--
-- Number of components in the slice must be the same as dimension of
-- n-tuples in elemental sets assigned to the set members. To construct
-- complete n-tuple the routine replaces null positions in the slice by
-- corresponding <symbols>.
--
-- If the slice contains at least one null position, the current token
-- must be symbol. Otherwise, the routine reads no symbols to construct
-- the n-tuple, so the current token is not checked. */

void simple_format
(     MPL *mpl,
      SET *set,               /* not changed */
      MEMBER *memb,           /* modified */
      SLICE *slice            /* not changed */
)
{     TUPLE *tuple;
      SLICE *temp;
      SYMBOL *sym, *with = NULL;
      xassert(set != NULL);
      xassert(memb != NULL);
      xassert(slice != NULL);
      xassert(set->dimen == slice_dimen(mpl, slice));
      xassert(memb->value.set->dim == set->dimen);
      if (slice_arity(mpl, slice) > 0) xassert(is_symbol(mpl));
      /* read symbols and construct complete n-tuple */
      tuple = create_tuple(mpl);
      for (temp = slice; temp != NULL; temp = temp->next)
      {  if (temp->sym == NULL)
         {  /* substitution is needed; read symbol */
            if (!is_symbol(mpl))
            {  int lack = slice_arity(mpl, temp);
               /* with cannot be null due to assertion above */
               xassert(with != NULL);
               if (lack == 1)
                  error(mpl, "one item missing in data group beginning "
                     "with %s", format_symbol(mpl, with));
               else
                  error(mpl, "%d items missing in data group beginning "
                     "with %s", lack, format_symbol(mpl, with));
            }
            sym = read_symbol(mpl);
            if (with == NULL) with = sym;
         }
         else
         {  /* copy symbol from the slice */
            sym = copy_symbol(mpl, temp->sym);
         }
         /* append the symbol to the n-tuple */
         tuple = expand_tuple(mpl, tuple, sym);
         /* skip optional comma *between* <symbols> */
         if (temp->next != NULL && mpl->token == T_COMMA)
            get_token(mpl /* , */);
      }
      /* add constructed n-tuple to elemental set */
      check_then_add(mpl, memb->value.set, tuple);
      return;
}

/*----------------------------------------------------------------------
-- matrix_format - read set data block in matrix format.
--
-- This routine reads set data block using the syntax:
--
-- <matrix format> ::= <column> <column> ... <column> :=
--               <row>   +/-      +/-    ...   +/-
--               <row>   +/-      +/-    ...   +/-
--                 .  .  .  .  .  .  .  .  .  .  .
--               <row>   +/-      +/-    ...   +/-
--
-- where <rows> are symbols that denote rows of the matrix, <columns>
-- are symbols that denote columns of the matrix, "+" and "-" indicate
-- whether corresponding n-tuple needs to be included in the elemental
-- set or not, respectively.
--
-- Number of the slice components must be the same as dimension of the
-- elemental set. The slice must have two null positions. To construct
-- complete n-tuple for particular element of the matrix the routine
-- replaces first null position of the slice by the corresponding <row>
-- (or <column>, if the flag tr is on) and second null position by the
-- corresponding <column> (or by <row>, if the flag tr is on). */

void matrix_format