lpkit.c

matlab整数规划工具箱

  MALLOC(scalechange, lp->sum + 1);

  /* initialise min and max values */
  for(i = 0; i <= lp->rows; i++) {
    row_max[i] = 0;
    row_min[i] = lp->infinite;
  }

  /* calculate min and max absolute values of rows */
  for(j = 1; j <= lp->columns; j++)
    for(i = lp->col_end[j - 1]; i < lp->col_end[j]; i++) {
      row_nr = lp->mat[i].row_nr;
      absval = my_abs(lp->mat[i].value);
      if(absval != 0) {
	row_max[row_nr] = my_max(row_max[row_nr], absval);
	row_min[row_nr] = my_min(row_min[row_nr], absval);
      }
    }    
  /* calculate scale factors for rows */
  for(i = 0; i <= lp->rows; i++) {
    scalechange[i] = minmax_to_scale(row_min[i], row_max[i]);
    lp->scale[i] *= scalechange[i];
  }

  /* now actually scale the matrix */
  for(j = 1; j <= lp->columns; j++)
    for(i = lp->col_end[j - 1]; i < lp->col_end[j]; i++)
      lp->mat[i].value *= scalechange[lp->mat[i].row_nr];

  /* and scale the rhs and the row bounds (RANGES in MPS!!) */
  for(i = 0; i <= lp->rows; i++) {
    lp->orig_rh[i] *= scalechange[i];

    if((lp->orig_upbo[i] < lp->infinite) && (lp->orig_upbo[i] != 0))
      lp->orig_upbo[i] *= scalechange[i];

    if(lp->orig_lowbo[i] != 0)
      lp->orig_lowbo[i] *= scalechange[i];
  }

  free(row_max);
  free(row_min);
  
  /* calculate column scales */
  for(j = 1; j <= lp->columns; j++) {
    if(lp->must_be_int[lp->rows + j]) { /* do not scale integer columns */
      scalechange[lp->rows + j] = 1;
    }
    else {
      col_max = 0;
      col_min = lp->infinite;
      for(i = lp->col_end[j - 1]; i < lp->col_end[j]; i++) {
	if(lp->mat[i].value != 0) {
	  col_max = my_max(col_max, my_abs(lp->mat[i].value));
	  col_min = my_min(col_min, my_abs(lp->mat[i].value));
	}
      }
      scalechange[lp->rows + j]  = minmax_to_scale(col_min, col_max);
      lp->scale[lp->rows + j] *= scalechange[lp->rows + j];
    }
  }
  
  /* scale mat */
  for(j = 1; j <= lp->columns; j++)
    for(i = lp->col_end[j - 1]; i < lp->col_end[j]; i++)
      lp->mat[i].value *= scalechange[lp->rows + j];
  
  /* scale bounds as well */
  for(i = lp->rows + 1; i <= lp->sum; i++) { /* was < *//* changed by PN */
    if(lp->orig_lowbo[i] != 0)
      lp->orig_lowbo[i] /= scalechange[i];
    if(lp->orig_upbo[i] != lp->infinite)
      lp->orig_upbo[i] /= scalechange[i];
  }
  lp->columns_scaled = TRUE;

  free(scalechange);
  lp->scaling_used = TRUE;
  lp->eta_valid = FALSE;
}

void reset_basis(lprec *lp)
{
  lp->basis_valid = FALSE;
}

void print_solution(lprec *lp)
{
  int i;
  FILE *stream;

  stream = stdout;

  fprintf(stream, "Value of objective function: %g\n",
	  (double)lp->best_solution[0]);

  /* print normal variables */
  for(i = 1; i <= lp->columns; i++)
    if(lp->names_used)
      fprintf(stream, "%-20s %g\n", lp->col_name[i],
	      (double)lp->best_solution[lp->rows + i]);
    else
      fprintf(stream, "Var [%d] %g\n", i,
	      (double)lp->best_solution[lp->rows + i]);

  /* print achieved constraint values */
  if(lp->verbose) {
    fprintf(stream, "\nActual values of the constraints:\n");
    for(i = 1; i <= lp->rows; i++)
      if(lp->names_used)
	fprintf(stream, "%-20s %g\n", lp->row_name[i],
		(double)lp->best_solution[i]);
      else
	fprintf(stream, "Row [%d] %g\n", i,
		(double)lp->best_solution[i]);  
  }

  if((lp->verbose || lp->print_duals)) {
    if(lp->max_level != 1)
      fprintf(stream,
	      "These are the duals from the node that gave the optimal solution.\n");
    else
      fprintf(stream, "\nDual values:\n");
    for(i = 1; i <= lp->rows; i++)
      if(lp->names_used)
	fprintf(stream, "%-20s %g\n", lp->row_name[i],
		(double)lp->duals[i]);
      else
	fprintf(stream, "Row [%d] %g\n", i, (double)lp->duals[i]); 
  }
  fflush(stream);
} /* Printsolution */

void write_LP(lprec *lp, FILE *output)
{
  int i, j;
  REAL *row;
  
  MALLOC(row, lp->columns+1);
  if(lp->maximise)
    fprintf(output, "max:");
  else
    fprintf(output, "min:");

  get_row(lp, 0, row);
  for(i = 1; i <= lp->columns; i++)
    if(row[i] != 0) {
      if(row[i] == -1)
	fprintf(output, " -");
      else if(row[i] == 1)
	fprintf(output, " +");
      else 
	fprintf(output, " %+g ", (double)row[i]);
      if(lp->names_used)
	fprintf(output, "%s", lp->col_name[i]);
      else
	fprintf(output, "x%d", i);
    }
  fprintf(output, ";\n");

  for(j = 1; j <= lp->rows; j++) {
    if(lp->names_used)
      fprintf(output, "%s:", lp->row_name[j]);
    get_row(lp, j, row);
    for(i = 1; i <= lp->columns; i++)
      if(row[i] != 0) {
	if(row[i] == -1)
	  fprintf(output, " -");
	else if(row[i] == 1)
	  fprintf(output, " +");
	else 
	  fprintf(output, " %+g ", (double)row[i]);
	if(lp->names_used)
	  fprintf(output, "%s", lp->col_name[i]);
	else
	  fprintf(output, "x%d", i);
      }
    if(lp->orig_upbo[j] == 0)
      fprintf(output, " =");
    else if(lp->ch_sign[j])
      fprintf(output, " >");
    else
      fprintf(output, " <");
    if(lp->ch_sign[j])
      fprintf(output, " %16g;\n", (double)-lp->orig_rh[j]);
    else
      fprintf(output, " %16g;\n", (double)lp->orig_rh[j]);
  }
  for(i = lp->rows + 1; i <= lp->sum; i++) {
    if(lp->orig_lowbo[i] != 0) {
      if(lp->names_used)
	fprintf(output, "%s > %16g;\n", lp->col_name[i - lp->rows],
		(double)lp->orig_lowbo[i]);
      else
	fprintf(output, "x%d > %16g;\n", i - lp->rows,
		(double)lp->orig_lowbo[i]);
    }
    if(lp->orig_upbo[i] != lp->infinite) {
      if(lp->names_used)
	fprintf(output, "%s < %16g;\n", lp->col_name[i - lp->rows],
		(double)lp->orig_upbo[i]);
      else
	fprintf(output, "x%d < %16g;\n", i - lp->rows,
		(double)lp->orig_upbo[i]);
    }
  }


  i = 1;
  while(!lp->must_be_int[lp->rows + i]  && i <= lp->columns)
    i++;
  if(i <= lp->columns) {
    if(lp->names_used)  
      fprintf(output, "\nint %s", lp->col_name[i]);
    else
      fprintf(output, "\nint x%d", i);
    i++;
    for(; i <= lp->columns; i++)
      if(lp->must_be_int[lp->rows + i]) {
	if(lp->names_used)  
	  fprintf(output, ",%s", lp->col_name[i]);
	else
	  fprintf(output, ", x%d", i);
      }
    fprintf(output, ";\n");
  }
  free(row);
}




void write_MPS(lprec *lp, FILE *output)
{
  int i, j, marker, putheader;
  REAL *column, a;


  MALLOC(column, lp->rows + 1);
  marker = 0;   
  fprintf(output, "NAME          %s\n", lp->lp_name);
  fprintf(output, "ROWS\n");
  for(i = 0; i <= lp->rows; i++) {
    if(i == 0)
      fprintf(output, " N  ");
    else
      if(lp->orig_upbo[i] != 0) {
	if(lp->ch_sign[i])
	  fprintf(output, " G  ");
	else
	  fprintf(output, " L  ");
      }
      else
	fprintf(output, " E  ");
    if(lp->names_used)
      fprintf(output, "%s\n", lp->row_name[i]);
    else
      fprintf(output, "r_%d\n", i);
  }
      
  fprintf(output, "COLUMNS\n");

  for(i = 1; i <= lp->columns; i++) {
    if((lp->must_be_int[i + lp->rows]) && (marker % 2) == 0) {
      fprintf(output,
	      "    MARK%04d  'MARKER'                 'INTORG'\n",
	      marker);
      marker++;
    }
    if((!lp->must_be_int[i + lp->rows]) && (marker % 2) == 1) {
      fprintf(output,
	      "    MARK%04d  'MARKER'                 'INTEND'\n",
	      marker);
      marker++;
    }
    /* this gets slow for large LP problems. Implement a sparse version? */
    get_column(lp, i, column);
    j = 0;
    if(lp->maximise) {
      if(column[j] != 0) { 
	if(lp->names_used)
	  fprintf(output, "    %-8s  %-8s  %12g\n", lp->col_name[i],
		  lp->row_name[j], (double)-column[j]);
	else
	  fprintf(output, "    var_%-4d  r_%-6d  %12g\n", i, j,
		  (double)-column[j]);
      }
    } 
    else {
      if(column[j] != 0) { 
	if(lp->names_used)
	  fprintf(output, "    %-8s  %-8s  %12g\n", lp->col_name[i],
		  lp->row_name[j], (double)column[j]);
	else
	  fprintf(output, "    var_%-4d  r_%-6d  %12g\n", i, j,
		  (double)column[j]);
      }
    }
    for(j = 1; j <= lp->rows; j++)
      if(column[j] != 0) { 
	if(lp->names_used)
	  fprintf(output, "    %-8s  %-8s  %12g\n", lp->col_name[i],
		  lp->row_name[j], (double)column[j]);
	else
	  fprintf(output, "    var_%-4d  r_%-6d  %12g\n", i, j,
		  (double)column[j]);
      }
  }
  if((marker % 2) == 1) {
    fprintf(output, "    MARK%04d  'MARKER'                 'INTEND'\n",
	    marker);
    /* marker++; */ /* marker not used after this */
  }

  fprintf(output, "RHS\n");
  for(i = 1; i <= lp->rows; i++) {
    a = lp->orig_rh[i];
    if(lp->scaling_used)
      a /= lp->scale[i];

    if(lp->ch_sign[i]) {
      if(lp->names_used)
	fprintf(output, "    RHS       %-8s  %12g\n", lp->row_name[i],
		(double)-a);
      else
	fprintf(output, "    RHS       r_%-6d  %12g\n", i, (double)-a);
    }
    else {
      if(lp->names_used)
	fprintf(output, "    RHS       %-8s  %12g\n", lp->row_name[i],
		(double)a);
      else
	fprintf(output, "    RHS       r_%-6d  %12g\n", i, (double)a);
    }
  }

  putheader = TRUE;
  for(i = 1; i <= lp->rows; i++)
    if((lp->orig_upbo[i] != lp->infinite) && (lp->orig_upbo[i] != 0.0)) {
      if(putheader) {
	fprintf(output, "RANGES\n");
	putheader = FALSE;
      }
      a = lp->orig_upbo[i];
      if(lp->scaling_used)
	a /= lp->scale[i];
      if(lp->names_used)
	fprintf(output, "    RGS       %-8s  %12g\n", lp->row_name[i],
		(double)a);
      else
	fprintf(output, "    RGS       r_%-6d  %12g\n", i,
		(double)a);
    }
    else if((lp->orig_lowbo[i] != 0.0)) {
      if(putheader) {
	fprintf(output, "RANGES\n");
	putheader = FALSE;
      }
      a = lp->orig_lowbo[i];
      if(lp->scaling_used)
	a /= lp->scale[i];
      if(lp->names_used)
	fprintf(output, "    RGS       %-8s  %12g\n", lp->row_name[i],
		(double)-a);
      else
	fprintf(output, "    RGS       r_%-6d  %12g\n", i,
		(double)-a);
    }

  fprintf(output, "BOUNDS\n");
  if(lp->names_used)
    for(i = lp->rows + 1; i <= lp->sum; i++) {
      if((lp->orig_lowbo[i] != 0) && (lp->orig_upbo[i] < lp->infinite) &&
	 (lp->orig_lowbo[i] == lp->orig_upbo[i])) {
	a = lp->orig_upbo[i];
	if(lp->scaling_used)
	  a *= lp->scale[i];
	fprintf(output, " FX BND       %-8s  %12g\n",
		lp->col_name[i - lp->rows], (double)a);
      }
      else {
	if(lp->orig_upbo[i] < lp->infinite) {
	  a = lp->orig_upbo[i];
	  if(lp->scaling_used)
	    a *= lp->scale[i];
	  fprintf(output, " UP BND       %-8s  %12g\n",
		  lp->col_name[i - lp->rows], (double)a);
	}
	if(lp->orig_lowbo[i] != 0) {
	  a = lp->orig_lowbo[i];
	  if(lp->scaling_used)
	    a *= lp->scale[i];
	  /* bug? should a be used instead of lp->orig_lowbo[i] MB */
	  fprintf(output, " LO BND       %-8s  %12g\n",
		  lp->col_name[i - lp->rows], (double)lp->orig_lowbo[i]);
	}
      }
    }
  else
    for(i = lp->rows + 1; i <= lp->sum; i++) {
      if((lp->orig_lowbo[i] != 0) && (lp->orig_upbo[i] < lp->infinite) &&
	 (lp->orig_lowbo[i] == lp->orig_upbo[i])) {
	a = lp->orig_upbo[i];
	if(lp->scaling_used)
	  a *= lp->scale[i];
	fprintf(output, " FX BND       %-8s  %12g\n",
		lp->col_name[i - lp->rows], (double)a);
      }
      else {
	if(lp->orig_upbo[i] < lp->infinite) {
	  a = lp->orig_upbo[i];
	  if(lp->scaling_used)
	    a *= lp->scale[i];
	  fprintf(output, " UP BND       var_%-4d  %12g\n",
		  i - lp->rows, (double)a);
	}
	if(lp->orig_lowbo[i] != 0) {
	  a = lp->orig_lowbo[i];
	  if(lp->scaling_used)
	    a *= lp->scale[i];
	  fprintf(output, " LO BND       var_%-4d  %12g\n", i - lp->rows,
		  (double)a);
	}
      }
    }
  fprintf(output, "ENDATA\n");
  free(column);
}

void print_duals(lprec *lp)
{
  int i;
  for(i = 1; i <= lp->rows; i++)
    if(lp->names_used)
      fprintf(stdout, "%s [%d] %g\n", lp->row_name[i], i,
	      (double)lp->duals[i]);
    else
      fprintf(stdout, "Dual [%d] %g\n", i, (double)lp->duals[i]);
}

void print_scales(lprec *lp)
{
  int i;
  if(lp->scaling_used) {
    for(i = 0; i <= lp->rows; i++)
      fprintf(stdout, "Row[%d]    scaled at %g\n", i,
	      (double)lp->scale[i]);
    for(i = 1; i <= lp->columns; i++)
      fprintf(stdout, "Column[%d] scaled at %g\n", i,
	      (double)lp->scale[lp->rows + i]);
  }
}