readmps.c

利用c语言编写

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "lpkit.h"

/* defines */
#define VARNAME    0
#define CONSTRNAME 1

/* MPS defines */
#define MPSUNDEF       -2
#define MPSNAME        -1
#define MPSROWS         0
#define MPSCOLUMNS      1
#define MPSRHS          2
#define MPSBOUNDS       3
#define MPSRANGES       4
#define MPSSOS          5

/* global vars */
short  Column_ready;
short  Int_section;
lprec *Mlp;
REAL  *Last_column;
char   Last_col_name[25];
int    Lineno;
short  Unconstrained_rows_found;

/*
A:  MPS format was named after an early IBM LP product and has emerged
as a de facto standard ASCII medium among most of the commercial LP
codes.  Essentially all commercial LP codes accept this format, but if
you are using public domain software and have MPS files, you may need
to write your own reader routine for this.  It's not too hard.  The
main things to know about MPS format are that it is column oriented (as
opposed to entering the model as equations), and everything (variables,
rows, etc.) gets a name.  MPS format is described in more detail in
Murtagh's book, referenced in another section. Also,

ftp://softlib.cs.rice.edu/pub/miplib/mps_format

is a nice short introduction.

MPS is an old format, so it is set up as though you were using punch
cards, and is not free format. Fields start in column 1, 5, 15, 25, 40
and 50.  Sections of an MPS file are marked by so-called header cards,
which are distinguished by their starting in column 1.  Although it is
typical to use upper-case throughout the file (like I said, MPS has
long historical roots), many MPS-readers will accept mixed-case for
anything except the header cards, and some allow mixed-case anywhere.
The names that you choose for the individual entities (constraints or
variables) are not important to the solver; you should pick names that
are meaningful to you, or will be easy for a post-processing code to
read.

Here is a little sample model written in MPS format (explained in more
detail below):

NAME          TESTPROB
ROWS
 N  COST
 L  LIM1
 G  LIM2
 E  MYEQN
COLUMNS
    XONE      COST                 1   LIM1                 1
    XONE      LIM2                 1
    YTWO      COST                 4   LIM1                 1
    YTWO      MYEQN               -1
    ZTHREE    COST                 9   LIM2                 1
    ZTHREE    MYEQN                1
RHS
    RHS1      LIM1                 5   LIM2                10
    RHS1      MYEQN                7
BOUNDS
 UP BND1      XONE                 4
 LO BND1      YTWO                -1
 UP BND1      YTWO                 1
ENDATA

means:

Optimize
 COST:    XONE + 4 YTWO + 9 ZTHREE
Subject To
 LIM1:    XONE + YTWO <= 5
 LIM2:    XONE + ZTHREE >= 10
 MYEQN:   - YTWO + ZTHREE  = 7
Bounds
 0 <= XONE <= 4
-1 <= YTWO <= 1
End

*/

/* copy a MPS name, only trailing spaces are removed. In MPS, names can have
   embedded spaces! */
static void namecpy(char *into, char *from)
{
  int i;

  /* copy at most 8 characters of from, stop at end of string or newline */
  for(i = 0; (from[i] != '\0') &&  (from[i] != '\n') && (i < 8); i++)
    into[i] = from[i];

  /* end with end of string */
  into[i] = '\0';

  /* remove trailing spaces, if any */
  for(i--; (i >= 0) && (into[i] == ' '); i--)
    into[i] = '\0';
}

/* scan an MPS line, and pick up the information in the fields that are
   present */
static int scan_line(char* line, char *field1, char *field2, char *field3,
		     double *field4, char *field5, double *field6)
{
  int items = 0, line_len;
  char buf[16];

  line_len = strlen(line);
  while ((line_len) && ((line[line_len-1] == '\n') || (line[line_len-1] == '\r')))
   line_len--;

  if(line_len >= 1) { /* spaces or N/L/G/E or UP/LO */
    strncpy(buf, line, 4);
    buf[4] = '\0';
    sscanf(buf, "%s", field1);
    items++;
  }
  else
    field1[0] = '\0';

  line += 4;

  if(line_len >= 5) { /* name */
    namecpy(field2, line);
    items++;
  }
  else
    field2[0] = '\0';

  line += 10;

  if(line_len >= 14) { /* name */
    namecpy(field3, line);
    items++;
  }
  else
    field3[0] = '\0';

  line += 10;

  if(line_len >= 25) { /* number */
    strncpy(buf, line, 15);
    buf[15] = '\0';
    *field4 = atof(buf);
    items++;
  }
  else
    *field4 = 0;

  line += 15;

  if(line_len >= 40) { /* name */
    namecpy(field5, line);
    items++;
  }
  else
    field5[0] = '\0';
  line += 10;

  if(line_len >= 50) { /* number */
    strncpy(buf, line, 15);
    buf[15] = '\0';
    *field6 = atof(buf);
    items++;
  }
  else
    *field6 = 0;

  return(items);
}

static int addmpscolumn(lprec *lp, MYBOOL Int_section, MYBOOL *Column_ready,
  REAL  *Last_column, char *Last_col_name)
{
  int i, ok = TRUE;

  if (*Column_ready) {
    if((!add_column(lp, Last_column)) || (!set_col_name(lp, lp->columns, Last_col_name)))
      ok = FALSE;
    else
      set_int(lp, lp->columns, Int_section);
  }
  *Column_ready = FALSE;
  for(i = 0; i <= lp->rows; i++)
    Last_column[i] = 0;
  return(ok);
}

static int find_row(lprec *lp, char *name, MYBOOL Unconstrained_rows_found)
{
  hashelem *hp;

  hp = findhash(name, lp->rowname_hashtab);

  if (hp == NULL) {
      if(Unconstrained_rows_found) { /* just ignore them in this case */
	return(-1);
      }
      else {
	report(lp, SEVERE, "Unknown row name (%s) on line %d", name, Lineno);
	return(-1);
      }
  }
  return(hp->index);
}

static int find_var(lprec *lp, char *name, MYBOOL verbose)
{
  hashelem *hp;

  hp = findhash(name, lp->colname_hashtab);

  if (hp == NULL) {
    if(verbose)
      report(lp, SEVERE, "Unknown variable name (%s) on line %d", name, Lineno);
    return(-1);
  }
  return(hp->index);
}

lprec *read_MPS(char *input, short verbose)
{
  lprec *lp = NULL;
  FILE *fpin;

  fpin = fopen(input, "r");
  if(fpin != NULL) {
    lp = read_mps(fpin, verbose);
    fclose(fpin);
  }
  return(lp);
}

lprec *read_mps(FILE *input, short verbose)
{
  char field1[5], field2[10], field3[10], field5[10], line[BUFSIZ], tmp[15];
  double field4, field6;
  int section = MPSUNDEF;
  int items;
  int row;
  MYBOOL Int_section;
  MYBOOL Column_ready;
  REAL *Last_column = NULL;
  char Last_col_name[NAMELEN];
  int var, SOS = 0;
  char probname[12];
  lprec *Mlp;
  MYBOOL Unconstrained_rows_found = FALSE;
  MYBOOL OF_found = FALSE;

  Mlp = make_lp(0, 0);
  if (Mlp != NULL) {
    Mlp->verbose = verbose;
    strcpy(Last_col_name, "");
    Int_section = FALSE;
    Column_ready = FALSE;
    Lineno = 0;

    /* let's initialize line to all zero's */
    memset(line, '\0', BUFSIZ);

    while(fgets(line, BUFSIZ - 1, input)) {
      Lineno++;

      /* skip lines which start with "*", they are comment */
      if(line[0] == '*') {
        report(Mlp, FULL, "Comment on line %d: %s", Lineno, line);
	continue;
      }

      report(Mlp, FULL, "Line %d: %s", Lineno, line);

      /* first check for "special" lines: NAME, ROWS, BOUNDS .... */
      /* this must start in the first position of line */
      if(line[0] != ' ') {
	sscanf(line, "%s", tmp);
	if(strcmp(tmp, "NAME") == 0) {
	  section = MPSNAME;
	  sscanf(line, "NAME %s", probname);
	  if (!set_lp_name(Mlp, probname)) {
  	    FREE(Last_column);
            delete_lp(Mlp);
	    return(NULL);
	  }
	}
	else if(strcmp(tmp, "ROWS") == 0) {
	  section = MPSROWS;
	  report(Mlp, FULL, "Switching to ROWS section");
	}
	else if(strcmp(tmp, "COLUMNS") == 0) {
	  if (CALLOC(Last_column, Mlp->rows + 1) == NULL) {
            FREE(Last_column);
            delete_lp(Mlp);
	    return(NULL);
	  }
	  section = MPSCOLUMNS;
	  report(Mlp, FULL, "Switching to COLUMNS section");
	}
	else if(strcmp(tmp, "RHS") == 0) {
	  if (!addmpscolumn(Mlp, Int_section, &Column_ready, Last_column, Last_col_name)) {
            FREE(Last_column);
            delete_lp(Mlp);
	    return(NULL);
	  }
	  section = MPSRHS;
	  report(Mlp, FULL, "Switching to RHS section");
	}
	else if(strcmp(tmp, "BOUNDS") == 0) {
	  section = MPSBOUNDS;
	  report(Mlp, FULL, "Switching to BOUNDS section");
	}
	else if(strcmp(tmp, "RANGES") == 0) {
	  section = MPSRANGES;
	  report(Mlp, FULL, "Switching to RANGES section");
	}
        else if(strcmp(tmp, "SOS") == 0) {
          section = MPSSOS;
          report(Mlp, FULL, "Switching to SOS section");
        }
	else if(strcmp(tmp, "ENDATA") == 0) {
	  report(Mlp, FULL, "Finished reading MPS file");
	}
	else { /* line does not start with space and does not match above */
          report(Mlp, IMPORTANT, "Unrecognized line %d: %s", Lineno, line);
          FREE(Last_column);
	  delete_lp(Mlp);
	  return(NULL);
	}
      }
      else { /* normal line, process */
	items = scan_line(line, field1, field2, field3, &field4, field5,
			  &field6);

	switch(section) {

	case MPSNAME:
          report(Mlp, IMPORTANT, "Error, extra line under NAME line");
          FREE(Last_column);
	  delete_lp(Mlp);
	  return(NULL);
	  break;

        /* Process entries in the ROWS section */
	case MPSROWS:
	  /* field1: rel. operator; field2: name of constraint */

	  report(Mlp, FULL, "Rows line: %s %s", field1, field2);

	  if(strcmp(field1, "N") == 0) {
	    if(!OF_found) { /* take the first N row as OF, ignore others */
	      if (!set_row_name(Mlp, 0, field2)) {
                FREE(Last_column);
	        delete_lp(Mlp);
	        return(NULL);
	      }
	      OF_found = TRUE;
	    }
	    else if(!Unconstrained_rows_found) {
	      report(Mlp, IMPORTANT, "Unconstrained row %s ignored", field2);
	      report(Mlp, IMPORTANT, "Further messages of this kind will be suppressed");
	      Unconstrained_rows_found = TRUE;
	    }
	  }
	  else if(strcmp(field1, "L") == 0) {
	    if ((!str_add_constraint(Mlp, "" ,LE ,0)) || (!set_row_name(Mlp, Mlp->rows, field2))) {
              FREE(Last_column);
	      delete_lp(Mlp);
	      return(NULL);
	    }
	  }
	  else if(strcmp(field1, "G") == 0) {
	    if ((!str_add_constraint(Mlp, "" ,GE ,0)) || (!set_row_name(Mlp, Mlp->rows, field2))) {
              FREE(Last_column);
	      delete_lp(Mlp);
	      return(NULL);
	    }
	  }
	  else if(strcmp(field1, "E") == 0) {
	    if ((!str_add_constraint(Mlp, "",EQ ,0)) || (!set_row_name(Mlp, Mlp->rows, field2))) {
              FREE(Last_column);
	      delete_lp(Mlp);
	      return(NULL);
	    }
	  }
	  else {