read.c

生成直角Steiner树的程序包

      fprintf(stderr,
	      "Warning on line %d: useless bound; variables are always >= 0\n",
	      yylineno);
      
    /* bound seems to be sane, add it */
    if((tmp_store.relat == REL_GE) || (tmp_store.relat == REL_EQ)) {
      if(h_tab_p->bnd->lowbo <  boundvalue)
	h_tab_p->bnd->lowbo = boundvalue;
      else
	fprintf(stderr, "Ineffective lower bound on line %d, ignored\n",
		yylineno);
    }
    if((tmp_store.relat == REL_LE) || (tmp_store.relat == REL_EQ)) {
      if(h_tab_p->bnd->upbo >  boundvalue)
	h_tab_p->bnd->upbo  = boundvalue;
      else
	fprintf(stderr, "Ineffective upper bound on line %d, ignored\n",
		yylineno);
    }
      
    /* check for empty range */
    if(h_tab_p->bnd->upbo < h_tab_p->bnd->lowbo) {
      fprintf(stderr,
	      "Error: bound on line %d contradicts earlier bounds, exiting\n",
	      yylineno);
      exit(EXIT_FAILURE);
    }
  }
  else /* tmp_store.value = 0 ! */ {
    fprintf(stderr,
	    "Error, variable %s has an effective coefficient of 0 in bound on line %d. Exiting.\n",
	    tmp_store.name, yylineno);
    exit(EXIT_FAILURE);
  }
  
  null_tmp_store();
} /* store_bounds */

void add_constraint_name(char *name, int row)
{
  constraint_name *cnp;

  if(!First_constraint_name) { /* first time only */
    CALLOC(First_constraint_name, 1);
  }
  else {
    cnp = First_constraint_name;
    CALLOC(First_constraint_name, 1);
    First_constraint_name->next = cnp;
  }
  strcpy(First_constraint_name->name, name);
  First_constraint_name->row = row;
}

/*
 * transport the data from the intermediate structure to the sparse matrix
 * and free the intermediate structure
 */
void readinput(lprec *lp)
{
  int    i, j, index, nn_ind;
  column *cp,*tcp; /* tcp (temporary cp) points to memory-space to free */
  hashelem *hp,*thp;
  bound *bp;
  rside *rp;
  constraint_name *cnp;
   
  /* fill names with the rownames */
  for(cnp = First_constraint_name; cnp; cnp = cnp->next)
    strcpy(lp->row_name[cnp->row], cnp->name);

  for(i = Rows;i >= 0;i--) {
    rp = First_rside;
    relat[i] = rp->relat;
    lp->orig_rh[i] = rp->value;
    First_rside = rp->next;
    free(rp); /* free memory when data has been read */
  }
  
  /* change upperbound to zero if the relational operator is the equal sign */
  for(i = 1; i <= Rows; i++)
    if(relat[i] == REL_EQ)
      lp->orig_upbo[i] = 0;

  for(i = 0; i <= Rows; i++)
    if(strcmp(lp->row_name[i], "")==0)
      sprintf(lp->row_name[i],"r_%d",i); 
  
  /* start reading the Hash_list structure */
  index = 0;
  nn_ind = 0;

  for(i = 0; i < Hash_tab->size; i++) {
    hp = Hash_tab->table[i];
    while(hp != NULL) {
      /* put an index in the cend array when a new name is found */
      lp->col_end[index++] = nn_ind;
      
      /* check if it must be an integer variable */
      if(hp->must_be_int) {
	lp->must_be_int[Rows + index]=TRUE;
      }
      /* check for bound */
      if(hp->bnd != NULL) {
	bp = hp->bnd;
	lp->orig_lowbo[Rows+index] = bp->lowbo;
	lp->orig_upbo[Rows+index] = bp->upbo;
	free(bp); /* free memory when data has been read*/
      }
	  
      /* copy name of column variable */
      strcpy(lp->col_name[index], hp->name);
	  
      /* put matrix values in sparse matrix */
      cp = hp->col;
      while(cp!=NULL) {
	lp->mat[nn_ind].row_nr = cp->row;
	lp->mat[nn_ind].value = cp->value;
	nn_ind++;
	tcp = cp;
	cp = cp->next;
	free(tcp); /* free memory when data has been read */
      }
      thp = hp;
      hp = hp->next;
      free(thp->name);
      free(thp); /* free memory when data has been read */
    }
  }
  lp->col_end[index] = nn_ind; 

  /* the following should be replaced by a call to the MPS print routine MB */
  
  if(Verbose) {
    printf("\n");
    printf("**********Data read**********\n");
    printf("Rows    : %d\n", Rows);
    printf("Columns : %d\n", Columns);
    printf("Nonnuls : %d\n", Non_zeros);
    printf("NAME          LPPROB\n");
    printf("ROWS\n");
    for(i = 0; i <= Rows; i++) {
      if(relat[i] == REL_LE)
	printf(" L  ");
      else if(relat[i] == REL_EQ)
	printf(" E  ");
      else if(relat[i] == REL_GE)
	printf(" G  ");
      else if(relat[i] == REL_OF)
	printf(" N  ");
      printf("%s\n", lp->row_name[i]);
    }
    
    printf("COLUMNS\n");
    j = 0;
    for(i = 0; i < Non_zeros; i++) {
      if(i == lp->col_end[j])
	j++;
      printf("    %-8s  %-8s  %g\n", lp->col_name[j],
	     lp->row_name[lp->mat[i].row_nr], (double)lp->mat[i].value);
    }

    printf("RHS\n");
    for(i = 0; i <= Rows; i++) {
      printf("    RHS       %-8s  %g\n", lp->row_name[i],
	     (double)lp->orig_rh[i]);
    }
      
    printf("RANGES\n");
    for(i = 1; i <= Rows; i++)
      if((lp->orig_upbo[i] != lp->infinite) && (lp->orig_upbo[i] != 0)) {
	printf("    RGS       %-8s  %g\n", lp->row_name[i],
	       (double)lp->orig_upbo[i]);
      }
      else if((lp->orig_lowbo[i] != 0)) {
	printf("    RGS       %-8s  %g\n", lp->row_name[i],
	       (double)-lp->orig_lowbo[i]);
      }
 
    printf("BOUNDS\n");
    for(i = Rows + 1; i <= Sum; i++) {
      if(lp->orig_upbo[i] < lp->infinite)
	printf(" UP BND       %-8s  %g\n", lp->col_name[i - Rows],
	       (double)lp->orig_upbo[i]);
      if(lp->orig_lowbo[i] > 0)
	printf(" LO BND       %-8s  %g\n", lp->col_name[i - Rows],
	       (double)lp->orig_lowbo[i]);
    }
    
    printf("ENDATA\n");
  }
} /* readinput */

lprec *read_lp_file(FILE *input, short verbose, nstring lp_name)
{
  lprec *lp;
  int i;
  Verbose = verbose; 

  yyin = input;
  Maximise = TRUE;  
  yyparse();
  fclose(input);
  
  CALLOC(lp, 1);

  Rows--;
  Sum = Rows + Columns;

  strcpy(lp->lp_name, lp_name);

  lp->verbose         = FALSE;
  lp->print_duals     = FALSE;
  lp->print_sol       = FALSE;
  lp->debug           = FALSE;
  lp->print_at_invert = FALSE;
  lp->trace           = FALSE;

  lp->rows          = Rows;
  lp->columns       = Columns;
  lp->sum           = Sum;
  lp->rows_alloc    = Rows;
  lp->columns_alloc = Columns;
  lp->sum_alloc     = lp->sum;

  CALLOC(lp->row_name, lp->rows + 1);
  CALLOC(lp->col_name, lp->columns + 1);
  
  lp->names_used    = TRUE;
  lp->obj_bound     = DEF_INFINITE;
  lp->bb_rule       = FIRST_NI;
  lp->break_at_int  = FALSE;
  lp->infinite      = DEF_INFINITE;
  lp->epsilon       = DEF_EPSILON;
  lp->epsb          = DEF_EPSB;
  lp->epsd          = DEF_EPSD;
  lp->epsel         = DEF_EPSEL;
  lp->non_zeros     = Non_zeros;
  lp->mat_alloc     = Non_zeros;
  lp->row_end_valid = FALSE;
  
  MALLOC(lp->mat,         Non_zeros);
  CALLOC(lp->col_no,      Non_zeros + 1);
  CALLOC(lp->col_end,     Columns + 1);
  CALLOC(lp->row_end,     Rows + 1);
  CALLOC(lp->orig_rh,     Rows + 1);
  CALLOC(lp->rh,          Rows + 1);
  CALLOC(lp->rhs,         Rows + 1);
  CALLOC(lp->must_be_int, Sum + 1);
  MALLOC(lp->orig_upbo,   Sum + 1);
  CALLOC(lp->upbo,        Sum + 1);
  CALLOC(lp->orig_lowbo,  Sum + 1);
  CALLOC(lp->lowbo,       Sum + 1);

  for(i = 0; i <= Sum; i++) {
    lp->orig_upbo[i]  = lp->infinite;
    lp->orig_lowbo[i] = 0;
  }

  lp->basis_valid = TRUE;

  CALLOC(lp->bas,   Rows + 1);
  CALLOC(lp->basis, Sum + 1);
  CALLOC(lp->lower, Sum + 1);

  for(i = 0; i <= Rows; i++) {
    lp->bas[i]   = i;
    lp->basis[i] = TRUE;
  }

  for(i = Rows + 1; i <= Sum; i++)
    lp->basis[i] = FALSE;

  for(i = 0 ; i <= Sum; i++)
    lp->lower[i] = TRUE;
 
  lp->eta_valid   = TRUE;
  lp->eta_size    = 0;
  lp->eta_alloc   = INITIAL_MAT_SIZE;
  lp->max_num_inv = DEFNUMINV;

  CALLOC(lp->eta_value,   INITIAL_MAT_SIZE);
  CALLOC(lp->eta_row_nr,  INITIAL_MAT_SIZE);
  CALLOC(lp->eta_col_end, Rows + lp->max_num_inv + 1);

  lp->iter       = 0;
  lp->total_iter = 0;

  CALLOC(lp->solution,      Sum + 1);
  CALLOC(lp->best_solution, Sum + 1);
  CALLOC(lp->duals,         Rows + 1);

  lp->maximise     = FALSE;
  lp->floor_first  = TRUE;
  lp->scaling_used = FALSE;

  CALLOC(lp->ch_sign, Rows + 1);

  for(i = 0; i <= Rows; i++)
    lp->ch_sign[i] = FALSE;

  lp->valid = FALSE; 

  CALLOC(relat, Rows + 1);

  readinput(lp);

  if(Maximise)
    set_maxim(lp);

  for(i = 1; i <= Rows; i++)
    set_constr_type(lp, i, relat[i]);

  free(relat);

  /* lets free the temporary list of constraint names */
  while(First_constraint_name) {
    constraint_name *cp;
    
    cp = First_constraint_name;
    First_constraint_name = First_constraint_name->next;
    free(cp);
  }

  return(lp); 
}