lpkit.c

利用c语言编写

#include <stdlib.h>
#include <stdarg.h>
#include <stdio.h>
#include <string.h>
#include "lpkit.h"
#include "patchlevel.h"
#include "lpglob.h"

/* Globals */
int     Rows;
int     Columns;
int     Non_zeros;

short   Maximise;

int     Warn_count; /* used in CHECK version of rounding macro */

int     max_allowed_columns = -1;

void set_magic(int code, int param)
{
  if(code != HASHSIZE) return;
  max_allowed_columns = param;
}

/* Return lp_solve version information */
void lp_solve_version(int *majorversion, int *minorversion,
                      int *release, int *build)
{
  int a;

  a=sizeof(lprec);

  (*majorversion) = MAJORVERSION;
  (*minorversion) = MINORVERSION;
  (*release) = RELEASE;
  (*build) = BUILD;
}

lprec *make_lpext(int rows, int columns, int non_zeros, int mat_alloc, char *lp_name)
{
  lprec *lp;
  int i, sum;

  if(rows < 0 || columns < 0 ||
     ((max_allowed_columns > 0) && (columns > max_allowed_columns))) {
    report(NULL, CRITICAL, "make_lpext: rows < 0 or columns < 0 or columns > %d", max_allowed_columns);
    lp = NULL;
  }
  else if (CALLOC(lp, 1) != NULL) {
    if (!set_lp_name(lp, lp_name)) {
      FREE(lp);
    }
    else {
      lp->verbose = CRITICALSTOP;
      lp->print_duals = FALSE;
      lp->print_sol = FALSE;
      lp->improve = IMPROVE_NONE;
      lp->scalemode = MMSCALING;
      lp->trace = FALSE;
      lp->lag_trace = FALSE;
      lp->debug = FALSE;
      lp->print_at_invert = FALSE;

      sum = rows + columns;
      lp->rows = rows;
      lp->columns = columns;
      lp->orig_columns = 0;
      lp->sum = sum;
      lp->rows_alloc = rows;
      lp->columns_alloc = columns;
      lp->sum_alloc = sum;

      lp->names_used = FALSE;

      lp->spx_status = NOTRUN;
      lp->lag_status = NOTRUN;

      lp->infinite = DEF_INFINITE;
      lp->negrange = DEF_NEGRANGE;
      lp->epsilon = DEF_EPSILON;
      lp->epsb = DEF_EPSB;
      lp->epsd = DEF_EPSD;
      lp->epsel = DEF_EPSEL;
      lp->epsperturb = DEF_PERTURB;
      lp->epspivot = DEF_EPSPIVOT;
      lp->lag_accept = DEF_LAGACCEPT;
      lp->wasprocessed = FALSE;

      lp->non_zeros = non_zeros;
      lp->mat_alloc = mat_alloc;
      lp->eta_alloc = INITIAL_MAT_SIZE;
      lp->max_num_inv = DEFNUMINV;

      if ((CALLOC(lp->mat, lp->mat_alloc) == NULL) ||
	  (CALLOC(lp->col_no, lp->mat_alloc + 1) == NULL) ||
	  (CALLOC(lp->col_end, columns + 1) == NULL) ||
	  (CALLOC(lp->row_end, rows + 1) == NULL) ||
	  (CALLOC(lp->orig_rh, rows + 1) == NULL) ||
	  (CALLOC(lp->rh, rows + 1) == NULL) ||
	  (CALLOC(lp->rhs, rows + 1) == NULL) ||
	  (CALLOC(lp->must_be_int, columns + 1) == NULL) ||
	  (CALLOC(lp->var_is_sc, columns + 1) == NULL) ||
	  (CALLOC(lp->var_is_free, columns + 1) == NULL) ||
	  (CALLOC(lp->orig_upbo, sum + 1) == NULL) ||
	  (CALLOC(lp->upbo, sum + 1) == NULL) ||
	  (CALLOC(lp->orig_lowbo, sum + 1) == NULL) ||
	  (CALLOC(lp->lowbo, sum + 1) == NULL) ||
	  (CALLOC(lp->bas, rows + 1) == NULL) ||
	  (CALLOC(lp->basis, sum + 1) == NULL) ||
	  (CALLOC(lp->lower, sum + 1) == NULL) ||
	  (CALLOC(lp->eta_value, lp->eta_alloc + 1) == NULL) ||
	  (CALLOC(lp->eta_row_nr, lp->eta_alloc + 1) == NULL) ||
	  (CALLOC(lp->eta_col_end, rows + lp->max_num_inv + 1) == NULL) ||
	  (CALLOC(lp->solution, sum + 1) == NULL) ||
	  (CALLOC(lp->best_solution, sum + 1) == NULL) ||
#if 0
	  (CALLOC(lp->var_to_orig, sum + 1) == NULL) ||
	  (CALLOC(lp->orig_to_var, sum + 1) == NULL) ||
#endif
	  (CALLOC(lp->duals, sum + 1) == NULL) ||
	  (CALLOC(lp->dualsfrom, sum + 1) == NULL) ||
	  (CALLOC(lp->dualstill, sum + 1) == NULL) ||
	  (CALLOC(lp->objfrom, columns + 1) == NULL) ||
	  (CALLOC(lp->objtill, columns + 1) == NULL) ||
	  (CALLOC(lp->ch_sign, rows + 1) == NULL)
	 ) {
	delete_lp(lp);
	lp = NULL;
      }
      else {
	lp->row_end_valid = FALSE;
	lp->int_count = 0;
	lp->sc_count = 0;

        lp->sos_list = NULL;
        lp->sos_alloc = 0;
        lp->sos_count = 0;
        lp->sos_ints = 0;
        lp->sos_vars = 0;
        lp->sos_priority = NULL;

        for(i = 0; i <= columns; i++)
          lp->must_be_int[i] = ISREAL;

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

	lp->basis_valid = TRUE;

	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->nr_lagrange = 0;

	lp->maximise = FALSE;
	lp->obj_bound = lp->infinite;
	lp->break_at_value = -lp->infinite;

        lp->piv_rule = BEST_SELECT;
	/* lp->piv_rule = WORST_SELECT; */
	/* lp->piv_rule = FIRST_SELECT; */

	lp->floor_first = TRUE;
	lp->bb_rule = FIRST_SELECT;

	lp->iter = 0;
	lp->total_iter = 0;
	lp->do_presolve = FALSE;
	lp->anti_degen = FALSE;

	lp->scaling_used = FALSE;
	lp->columns_scaled = FALSE;

	lp->valid = FALSE;

	lp->sectimeout = 0;
	lp->solutioncount = 0;
	lp->solutionlimit = 1;

	lp->abort = NULL;
	lp->aborthandle = NULL;
	lp->writelog = NULL;
	lp->loghandle = NULL;
	lp->debuginfo = NULL;
	lp->usermessage = NULL;
	lp->msgmask = MSG_NONE;
	lp->msghandle = NULL;
      }
    }
  }
  return(lp);
}

lprec *make_lp(int rows, int columns)
{
  return(make_lpext(rows, columns, 0, 1, "Unnamed"));
}

static void free_SOSrec(SOSrec *SOS)
{
  FREE(SOS->name);
  if(SOS->size > 0) {
    FREE(SOS->members);
    FREE(SOS->weights);
    FREE(SOS->membersSorted);
    FREE(SOS->membersMapped);
  }
  FREE(SOS);
}

void delete_lp(lprec *lp)
{
  int i;

  if(lp != NULL) {
    FREE(lp->lp_name);
    if(lp->names_used) {
      FREE(lp->row_name);
      FREE(lp->col_name);
      if (lp->rowname_hashtab != NULL)
	free_hash_table(lp->rowname_hashtab);
      if (lp->colname_hashtab != NULL)
	free_hash_table(lp->colname_hashtab);
    }

    FREE(lp->mat);
    FREE(lp->col_no);
    FREE(lp->col_end);
    FREE(lp->row_end);
    FREE(lp->orig_rh);
    FREE(lp->rh);
    FREE(lp->rhs);
    FREE(lp->must_be_int);
    FREE(lp->var_is_sc);
    FREE(lp->var_is_free);
    FREE(lp->orig_upbo);
    FREE(lp->orig_lowbo);
    FREE(lp->upbo);
    FREE(lp->lowbo);
    FREE(lp->bas);
    FREE(lp->basis);
    FREE(lp->lower);
    FREE(lp->eta_value);
    FREE(lp->eta_row_nr);
    FREE(lp->eta_col_end);
    FREE(lp->solution);
    FREE(lp->best_solution);
#if 0
    FREE(lp->var_to_orig);
    FREE(lp->orig_to_var);
#endif
    FREE(lp->duals);
    FREE(lp->dualsfrom);
    FREE(lp->dualstill);
    FREE(lp->objfrom);
    FREE(lp->objtill);
    FREE(lp->ch_sign);
    if(lp->sos_alloc > 0) {
      for(i = 0; i < lp->sos_count; i++)
        free_SOSrec(lp->sos_list[i]);
      FREE(lp->sos_list);
    }
    if(lp->sos_vars > 0) {
      FREE(lp->sos_priority);
    }
    if(lp->scaling_used) {
      FREE(lp->scale);
    }
    if(lp->nr_lagrange > 0) {
      FREE(lp->lag_rhs);
      FREE(lp->lambda);
      FREE(lp->lag_con_type);
      if (lp->lag_row != NULL)
        for(i = 0; i < lp->nr_lagrange; i++) {
	  FREE(lp->lag_row[i]);
        }
      FREE(lp->lag_row);
    }

    FREE(lp);
  }
}

static int copy_lagrange(lprec *lp, lprec *newlp)
{
  int i, colsplus = lp->columns_alloc + 1;

  for(i = 0; (i < newlp->nr_lagrange) && (MALLOCCPY(newlp->lag_row[i], lp->lag_row[i], colsplus) != NULL); i++);
  return(!(i < newlp->nr_lagrange));
}

/* this code has not been reviewed yet and is not complete <peno> */
lprec *copy_lp(lprec *lp)
{
  lprec *newlp;
  int rowsplus, colsplus, sumplus;

  rowsplus = lp->rows_alloc + 1;
  colsplus = lp->columns_alloc + 1;
  sumplus  = lp->sum_alloc + 1;

  if (MALLOCCPY(newlp, lp, 1) != NULL) { /* copy all non pointers */
    newlp->col_name = newlp->row_name = NULL;
    newlp->rowname_hashtab = newlp->colname_hashtab = NULL;
    newlp->mat = NULL;
    newlp->col_end = NULL;
    newlp->col_no = NULL;
    newlp->row_end = NULL;
    newlp->orig_rh = NULL;
    newlp->rh = NULL;
    newlp->rhs = NULL;
    newlp->must_be_int = NULL;
    newlp->var_is_sc = NULL;
    newlp->orig_upbo = NULL;
    newlp->orig_lowbo = NULL;
    newlp->upbo = NULL;
    newlp->lowbo = NULL;
    newlp->bas = NULL;
    newlp->basis = NULL;
    newlp->lower = NULL;
    newlp->eta_value = NULL;
    newlp->eta_row_nr = NULL;
    newlp->eta_col_end = NULL;
    newlp->solution = NULL;
    newlp->best_solution = NULL;
#if 0
    newlp->var_to_orig = NULL;
    newlp->var_is_free = NULL;
#endif
    newlp->duals = NULL;
    newlp->dualsfrom = NULL;
    newlp->dualstill = NULL;
    newlp->objfrom = NULL;
    newlp->objtill = NULL;
    newlp->ch_sign = NULL;
    newlp->scale = NULL;
    newlp->lag_rhs = NULL;
    newlp->lambda = NULL;
    newlp->lag_con_type = NULL;
    newlp->lag_row = NULL;
    if (((newlp->names_used) &&
	 ((MALLOCCPY(newlp->col_name, lp->col_name, colsplus) == NULL) ||
	  (MALLOCCPY(newlp->row_name, lp->row_name, rowsplus) == NULL)
	 )
	) ||
	((newlp->rowname_hashtab = copy_hash_table(lp->rowname_hashtab)) == NULL) ||
	((newlp->colname_hashtab = copy_hash_table(lp->colname_hashtab)) == NULL) ||
	(MALLOCCPY(newlp->mat, lp->mat, newlp->mat_alloc) == NULL) ||
	(MALLOCCPY(newlp->col_end, lp->col_end, colsplus) == NULL) ||
	(MALLOCCPY(newlp->col_no, lp->col_no, newlp->mat_alloc + 1) == NULL) ||
	(MALLOCCPY(newlp->row_end, lp->row_end, rowsplus) == NULL) ||
	(MALLOCCPY(newlp->orig_rh, lp->orig_rh, rowsplus) == NULL) ||
	(MALLOCCPY(newlp->rh, lp->rh, rowsplus) == NULL) ||
	(MALLOCCPY(newlp->rhs, lp->rhs, rowsplus) == NULL) ||
	(MALLOCCPY(newlp->must_be_int, lp->must_be_int, colsplus) == NULL) ||
	(MALLOCCPY(newlp->var_is_sc, lp->var_is_sc, colsplus) == NULL) ||
	(MALLOCCPY(newlp->orig_upbo, lp->orig_upbo, sumplus) == NULL) ||
	(MALLOCCPY(newlp->orig_lowbo, lp->orig_lowbo, sumplus) == NULL) ||
	(MALLOCCPY(newlp->upbo, lp->upbo, sumplus) == NULL) ||
	(MALLOCCPY(newlp->lowbo, lp->lowbo, sumplus) == NULL) ||
	(MALLOCCPY(newlp->bas, lp->bas, rowsplus) == NULL) ||
	(MALLOCCPY(newlp->basis, lp->basis, sumplus) == NULL) ||
	(MALLOCCPY(newlp->lower, lp->lower, sumplus) == NULL) ||
	(MALLOCCPY(newlp->eta_value, lp->eta_value, lp->eta_alloc) == NULL) ||
	(MALLOCCPY(newlp->eta_row_nr, lp->eta_row_nr, lp->eta_alloc) == NULL) ||
	(MALLOCCPY(newlp->eta_col_end, lp->eta_col_end, lp->rows_alloc + lp->max_num_inv + 1) == NULL) ||
	(MALLOCCPY(newlp->solution, lp->solution, sumplus) == NULL) ||
	(MALLOCCPY(newlp->best_solution, lp->best_solution, sumplus) == NULL) ||
#if 0
	(MALLOCCPY(newlp->var_to_orig, lp->var_to_orig, sumplus) == NULL) ||
	(MALLOCCPY(newlp->orig_to_var, lp->orig_to_var, sumplus) == NULL) ||
#endif
	(MALLOCCPY(newlp->var_is_free, lp->var_is_free, colsplus) == NULL) ||
	(MALLOCCPY(newlp->duals, lp->duals, sumplus) == NULL) ||
	(MALLOCCPY(newlp->dualsfrom, lp->dualsfrom, sumplus) == NULL) ||
	(MALLOCCPY(newlp->dualstill, lp->dualstill, sumplus) == NULL) ||
	(MALLOCCPY(newlp->objfrom, lp->objfrom, colsplus) == NULL) ||
	(MALLOCCPY(newlp->objtill, lp->objtill, colsplus) == NULL) ||
	(MALLOCCPY(newlp->ch_sign, lp->ch_sign, rowsplus) == NULL) ||
	((newlp->scaling_used) && (MALLOCCPY(newlp->scale, lp->scale, sumplus) == NULL)) ||
	((newlp->nr_lagrange > 0) &&
	 ((MALLOCCPY(newlp->lag_rhs, lp->lag_rhs, newlp->nr_lagrange) == NULL) ||
	  (MALLOCCPY(newlp->lambda, lp->lambda, newlp->nr_lagrange) == NULL) ||
	  (MALLOCCPY(newlp->lag_con_type, lp->lag_con_type, newlp->nr_lagrange) == NULL) ||
	  (MALLOCCPY(newlp->lag_row, lp->lag_row, newlp->nr_lagrange) == NULL) ||
	  (copy_lagrange(lp, newlp) == FALSE)
	 )
	)
       ) {
      delete_lp(newlp);
      FREE(newlp);
    }
  }
  return(newlp);
}

int inc_mat_space(lprec *lp, int maxextra)
{
   int ok = TRUE;

   if(lp->non_zeros + maxextra >= lp->mat_alloc) {
     /* let's allocate at least INITIAL_MAT_SIZE  entries */
     if(lp->mat_alloc < INITIAL_MAT_SIZE)
       lp->mat_alloc = INITIAL_MAT_SIZE;

     /* increase the size by RESIZEFACTOR each time it becomes too small */
     while(lp->non_zeros + maxextra >= lp->mat_alloc)
       lp->mat_alloc = (int) ((double) lp->mat_alloc*RESIZEFACTOR);

     if ((REALLOC(lp->mat, lp->mat_alloc) == NULL) ||
         (REALLOC(lp->col_no, lp->mat_alloc + 1) == NULL)) {
       lp->spx_status = OUT_OF_MEMORY;
       ok = FALSE;
     }
   }
   return(ok);
}

int inc_row_space(lprec *lp)
{
  int i, rowsum, oldrowsalloc, rowcolsum, ok = TRUE;

  if(lp->rows > lp->rows_alloc) {
    oldrowsalloc = lp->rows_alloc;
    lp->rows_alloc = lp->rows + 10;
    lp->sum_alloc  = lp->rows_alloc + lp->columns_alloc;
    rowsum    = lp->rows_alloc + 1;
    rowcolsum = lp->sum_alloc + 1;
    if ((REALLOC(lp->orig_rh, rowsum) == NULL) ||
        (REALLOC(lp->rh, rowsum) == NULL) ||
        (REALLOC(lp->rhs, rowsum) == NULL) ||
        (REALLOC(lp->upbo, rowcolsum) == NULL) ||
        (REALLOC(lp->orig_upbo, rowcolsum) == NULL) ||
        (REALLOC(lp->lowbo, rowcolsum) == NULL) ||
        (REALLOC(lp->orig_lowbo, rowcolsum) == NULL) ||
        (REALLOC(lp->solution, rowcolsum) == NULL) ||
        (REALLOC(lp->best_solution, rowcolsum) == NULL) ||
#if 0
        (REALLOC(lp->var_to_orig, rowcolsum) == NULL) ||
        (REALLOC(lp->orig_to_var, rowcolsum) == NULL) ||
#endif
        (REALLOC(lp->basis, rowcolsum) == NULL) ||
        (REALLOC(lp->lower, rowcolsum) == NULL) ||
        ((lp->scale != NULL) && (REALLOC(lp->scale, rowcolsum + lp->nr_lagrange) == NULL)) ||
        (REALLOC(lp->row_end, rowsum) == NULL) ||
        ((lp->names_used) && (REALLOC(lp->row_name, rowsum) == NULL)) ||
        (REALLOC(lp->bas, rowsum) == NULL) ||
        (REALLOC(lp->duals, rowcolsum) == NULL) ||
        (REALLOC(lp->dualsfrom, rowcolsum) == NULL) ||
        (REALLOC(lp->dualstill, rowcolsum) == NULL) ||
        (REALLOC(lp->ch_sign, rowsum) == NULL) ||
        (REALLOC(lp->eta_col_end, rowsum + lp->max_num_inv) == NULL)
       ) {
       lp->spx_status = OUT_OF_MEMORY;
       ok = FALSE;
    }
    else if ((lp->names_used) && (lp->row_name != NULL)) {
      for(i = oldrowsalloc + 1; i < rowsum; i++)
        lp->row_name[i] = NULL;
    }
  }
  return(ok);
}

int inc_col_space(lprec *lp)
{
  int i, colsum, oldcolsalloc, rowcolsum, ok = TRUE;

  if(lp->columns >= lp->columns_alloc) {
    oldcolsalloc = lp->columns_alloc;
    if((max_allowed_columns > 0) && (oldcolsalloc >= max_allowed_columns))
      ok = FALSE;
    else {
      lp->columns_alloc = lp->columns + DELTACOLALLOC;
      if((max_allowed_columns > 0) && (lp->columns_alloc > max_allowed_columns))
	lp->columns_alloc = max_allowed_columns;
      lp->sum_alloc = lp->rows_alloc + lp->columns_alloc;
      colsum    = lp->columns_alloc + 1;
      rowcolsum = lp->sum_alloc + 1;
      if ((REALLOC(lp->must_be_int, colsum) == NULL) ||
          (REALLOC(lp->var_is_sc, colsum) == NULL) ||
          (REALLOC(lp->var_is_free, colsum) == NULL) ||
          (REALLOC(lp->upbo, rowcolsum) == NULL) ||
          (REALLOC(lp->orig_upbo, rowcolsum) == NULL) ||
          (REALLOC(lp->lowbo, rowcolsum) == NULL) ||
          (REALLOC(lp->orig_lowbo, rowcolsum) == NULL) ||
          (REALLOC(lp->solution, rowcolsum) == NULL) ||
          (REALLOC(lp->best_solution, rowcolsum) == NULL) ||
#if 0
          (REALLOC(lp->var_to_orig, rowcolsum) == NULL) ||
          (REALLOC(lp->orig_to_var, rowcolsum) == NULL) ||
#endif
          (REALLOC(lp->basis, rowcolsum) == NULL) ||
          (REALLOC(lp->lower, rowcolsum) == NULL) ||
          ((lp->scale != NULL) && (REALLOC(lp->scale, rowcolsum + lp->nr_lagrange) == NULL)) ||
          (REALLOC(lp->col_end, colsum) == NULL) ||
          ((lp->names_used) && (REALLOC(lp->col_name, colsum) ==NULL)) ||
          (REALLOC(lp->duals, rowcolsum) == NULL) ||
          (REALLOC(lp->dualsfrom, rowcolsum) == NULL) ||
          (REALLOC(lp->dualstill, rowcolsum) == NULL) ||
          (REALLOC(lp->objfrom, colsum) == NULL) ||
          (REALLOC(lp->objtill, colsum) == NULL)
	 ) {
         lp->spx_status = OUT_OF_MEMORY;
         ok = FALSE;
      }
      else if ((lp->names_used) && (lp->col_name != NULL)) {
	for(i = oldcolsalloc+1; i < colsum; i++)
	  lp->col_name[i] = NULL;
      }
    }
  }
  return(ok);
}

/* Implement pure binary search for matrix look-up */
/* This routine only works if the sparse matrix is sorted correctly. This can not be guaranteed at this time */