lpkit.c

利用c语言编写

void set_infinite(lprec *lp, REAL infinite)
{
  lp->infinite = infinite;
}

REAL get_infinite(lprec *lp)
{
  return(lp->infinite);
}

void set_epsilon(lprec *lp, REAL epsilon)
{
  lp->epsilon = epsilon;
}

REAL get_epsilon(lprec *lp)
{
  return(lp->epsilon);
}

void set_epsb(lprec *lp, REAL epsb)
{
  lp->epsb = epsb;
}

REAL get_epsb(lprec *lp)
{
  return(lp->epsb);
}

void set_epsd(lprec *lp, REAL epsd)
{
  lp->epsd = epsd;
}

REAL get_epsd(lprec *lp)
{
  return(lp->epsd);
}

void set_epsel(lprec *lp, REAL epsel)
{
  lp->epsel = epsel;
}

REAL get_epsel(lprec *lp)
{
  return(lp->epsel);
}

void set_scalemode(lprec *lp, MYBOOL scalemode)
{
  lp->scalemode = scalemode;
}

MYBOOL get_scalemode(lprec *lp)
{
  return(lp->scalemode);
}

void set_improve(lprec *lp, MYBOOL improve)
{
  lp->improve = improve;
}

MYBOOL is_improve(lprec *lp)
{
  return(lp->improve);
}

void set_lag_trace(lprec *lp, MYBOOL lag_trace)
{
  lp->lag_trace = lag_trace;
}

MYBOOL is_lag_trace(lprec *lp)
{
  return(lp->lag_trace);
}

void set_piv_rule(lprec *lp, MYBOOL piv_rule)
{
  lp->piv_rule = piv_rule;
}

MYBOOL get_piv_rule(lprec *lp)
{
  return(lp->piv_rule);
}

void set_break_at_first(lprec *lp, MYBOOL break_at_first)
{
  lp->break_at_first = break_at_first;
}

MYBOOL is_break_at_first(lprec *lp)
{
  return(lp->break_at_first);
}

void set_bb_floorfirst(lprec *lp, short bb_floorfirst)
{
  lp->bb_floorfirst = bb_floorfirst;
}

short is_bb_floorfirst(lprec *lp)
{
  return(lp->bb_floorfirst);
}

void set_break_at_value(lprec *lp, REAL break_at_value)
{
  lp->break_at_value = break_at_value;
}

REAL get_break_at_value(lprec *lp)
{
  return(lp->break_at_value);
}

void set_negrange(lprec *lp, REAL negrange)
{
  lp->negrange = negrange;
}

REAL get_negrange(lprec *lp)
{
  return(lp->negrange);
}

void set_epsperturb(lprec *lp, REAL epsperturb)
{
  lp->epsperturb = epsperturb;
}

REAL get_epsperturb(lprec *lp)
{
  return(lp->epsperturb);
}

void set_epspivot(lprec *lp, REAL epspivot)
{
  lp->epspivot = epspivot;
}

REAL get_epspivot(lprec *lp)
{
  return(lp->epspivot);
}

int get_max_level(lprec *lp)
{
  return(lp->max_level);
}

int get_total_nodes(lprec *lp)
{
  return(lp->total_nodes);
}

int get_total_iter(lprec *lp)
{
  return(lp->total_iter);
}

REAL get_objective(lprec *lp)
{
  if(!lp->basis_valid) {
    report(lp, CRITICAL, "get_objective: Not a valid basis");
    return(0.0);
  }

  return(*(lp->best_solution));
}

int get_variables(lprec *lp, REAL *var)
{
  if(!lp->basis_valid) {
    report(lp, CRITICAL, "get_variables: Not a valid basis");
    return(FALSE);
  }

  memcpy(var, lp->best_solution + (1 + lp->rows), lp->columns * sizeof(*(lp->best_solution)));
  return(TRUE);
}

int get_ptr_variables(lprec *lp, REAL **var)
{
  if(!lp->basis_valid) {
    report(lp, CRITICAL, "get_ptr_variables: Not a valid basis");
    return(FALSE);
  }

  if(var != NULL)
   *var = lp->best_solution + (1 + lp->rows);
  return(TRUE);
}

int get_constraints(lprec *lp, REAL *constr)
{
  if(!lp->basis_valid) {
    report(lp, CRITICAL, "get_constraints: Not a valid basis");
    return(FALSE);
  }

  memcpy(constr, lp->best_solution + 1, lp->rows * sizeof(*(lp->best_solution)));
  return(TRUE);
}

int get_ptr_constraints(lprec *lp, REAL **constr)
{
  if(!lp->basis_valid) {
    report(lp, CRITICAL, "get_ptr_constraints: Not a valid basis");
    return(FALSE);
  }

  if(constr != NULL)
   *constr = lp->best_solution + 1;
  return(TRUE);
}

int get_sensitivity_rhs(lprec *lp, REAL *duals, REAL *dualsfrom, REAL *dualstill)
{
  if(!lp->basis_valid) {
    report(lp, CRITICAL, "get_sensitivity_rhs: Not a valid basis");
    return(FALSE);
  }

  if(duals != NULL)
   memcpy(duals, lp->duals + 1, lp->sum * sizeof(*(lp->duals)));
  if(dualsfrom != NULL)
   memcpy(dualsfrom, lp->dualsfrom + 1, lp->sum * sizeof(*(lp->dualsfrom)));
  if(dualstill != NULL)
   memcpy(dualstill, lp->dualstill + 1, lp->sum * sizeof(*(lp->dualstill)));
  return(TRUE);
}

int get_ptr_sensitivity_rhs(lprec *lp, REAL **duals, REAL **dualsfrom, REAL **dualstill)
{
  if(!lp->basis_valid) {
    report(lp, CRITICAL, "get_ptr_sensitivity_rhs: Not a valid basis");
    return(FALSE);
  }

  if(duals != NULL)
   *duals = lp->duals + 1;
  if(dualsfrom != NULL)
   *dualsfrom = lp->dualsfrom + 1;
  if(dualstill != NULL)
   *dualstill = lp->dualstill + 1;
  return(TRUE);
}

int get_sensitivity_obj(lprec *lp, REAL *objfrom, REAL *objtill)
{
  if(!lp->basis_valid) {
    report(lp, CRITICAL, "get_sensitivity_obj: Not a valid basis");
    return(FALSE);
  }

  if(objfrom != NULL)
   memcpy(objfrom, lp->objfrom + 1, lp->columns * sizeof(*(lp->objfrom)));
  if(objtill != NULL)
   memcpy(objtill, lp->objtill + 1, lp->columns * sizeof(*(lp->objtill)));
  return(TRUE);
}

int get_ptr_sensitivity_obj(lprec *lp, REAL **objfrom, REAL **objtill)
{
  if(!lp->basis_valid) {
    report(lp, CRITICAL, "get_ptr_sensitivity_obj: Not a valid basis");
    return(FALSE);
  }

  if(objfrom != NULL)
   *objfrom = lp->objfrom + 1;
  if(objtill != NULL)
   *objtill = lp->objtill + 1;
  return(TRUE);
}

int get_Nrows(lprec *lp)
{
  if(!lp->basis_valid) {
    report(lp, CRITICAL, "get_Nrows: Not a valid basis");
    return(0);
  }
  return(lp->rows);
}

int get_Ncolumns(lprec *lp)
{
  if(!lp->basis_valid) {
    report(lp, CRITICAL, "get_Ncolumns: Not a valid basis");
    return(0);
  }
  return(lp->columns);
}

/* Sorting and searching functions */
static int SortByREAL(int *item, REAL *weight, int size, int offset, MYBOOL unique)
{
  int i, ii, saveI;
  REAL saveW;

  for(i = 1; i < size; i++) {
    ii = i+offset-1;
    while (ii >= 0 && weight[ii] >= weight[ii+1]) {
      if(unique && (weight[ii] == weight[ii+1]))
        return(item[ii]);
      saveI = item[ii];
      saveW = weight[ii];
      item[ii] = item[ii+1];
      weight[ii] = weight[ii+1];
      item[ii+1] = saveI;
      weight[ii+1] = saveW;
      ii--;
    }
  }
  return(0);
}

static int SortByINT(int *item, int *weight, int size, int offset, MYBOOL unique)
{
  int i, ii, saveI;
  int saveW;

  for(i = 1; i < size; i++) {
    ii = i+offset-1;
    while (ii >= 0 && weight[ii] >= weight[ii+1]) {
      if(unique && (weight[ii] == weight[ii+1]))
        return(item[ii]);
      saveI = item[ii];
      saveW = weight[ii];
      item[ii] = item[ii+1];
      weight[ii] = weight[ii+1];
      item[ii+1] = saveI;
      weight[ii+1] = saveW;
      ii--;
    }
  }
  return(0);
}

static int SearchFor(int target, int *attributes, int size, int offset, MYBOOL absolute)
{
  int beginPos, endPos;
  int newPos, match;

 /* Set starting and ending index offsets */
  beginPos = offset;
  endPos = beginPos + size - 1;

 /* Do binary search logic based on a sorted attribute vector */
  newPos = (beginPos + endPos) / 2;
  match = attributes[newPos];
  if(absolute)
    match = abs(match);
  while(endPos - beginPos > LINEARSEARCH) {
    if(match < target) {
      beginPos = newPos + 1;
      newPos = (beginPos + endPos) / 2;
      match = attributes[newPos];
      if(absolute)
	match = abs(match);
    }
    else if(match > target) {
      endPos = newPos - 1;
      newPos = (beginPos + endPos) / 2;
      match = attributes[newPos];
      if(absolute)
	match = abs(match);
    }
    else {
      beginPos = newPos;
      endPos = newPos;
    }
  }

 /* Do linear (unsorted) search logic */
  if(endPos - beginPos <= LINEARSEARCH) {
    match = attributes[beginPos];
    if(absolute)
      match = abs(match);
    while((beginPos < endPos) && (match != target)) {
      beginPos++;
      match = attributes[beginPos];
      if(absolute)
	match = abs(match);
    }
    if(match == target)
      endPos = beginPos;
  }

 /* Return the index if a match was found, or signal failure with a -1 */
  if((beginPos == endPos) && (match == target))
    return(beginPos);
  else
    return(-1);
}

/* SOS record functions */
int append_SOSrec(lprec *lp, SOSrec *SOS, int size, int *variables, REAL *weights)
{
  int i, oldsize, newsize, nn;

  oldsize = SOS->size;
  newsize = oldsize + size;
  nn = abs(SOS->type);

 /* Shift existing active data right (normally zero) */
  if(SOS->members == NULL) {
    if (CALLOC(SOS->members, 1 + newsize + 1 + nn) == NULL)
      return(-1);
  }
  else {
    if (REALLOC(SOS->members, 1 + newsize + 1 + nn) == NULL)
      return(-1);
    for(i = newsize+1+nn; i > newsize+1; i--)
      SOS->members[i] = SOS->members[i-size];
  }
  SOS->members[0] = newsize;
  SOS->members[newsize+1] = nn;

 /* Copy the new data into the arrays */
  if(SOS->weights == NULL) {
    if (CALLOC(SOS->weights, 1 + newsize) == NULL)
      return(-1);
  }
  else {
    if (REALLOC(SOS->weights, 1 + newsize) == NULL)
      return(-1);
  }
  for(i = oldsize+1; i <= newsize; i++) {
    SOS->members[i] = variables[i-oldsize-1];
    if((SOS->members[i] < 1) || (SOS->members[i] > lp->columns))
      report(lp, IMPORTANT, "Invalid SOS variable definition index %d", SOS->members[i]);
    else
      lp->must_be_int[SOS->members[i]] |= ISSOS;
    if(weights == NULL)
      SOS->weights[i] = i;  /* Follow standard, which is sorted ascending */
    else
      SOS->weights[i] = weights[i-oldsize-1];
    SOS->weights[0] += weights[i-oldsize-1];
  }

 /* Sort the new paired lists ascending by weight (simple bubble sort) */
  i = SortByREAL(SOS->members, SOS->weights, newsize, 1, TRUE);
  if(i > 0)
    report(lp, CRITICAL, "Invalid SOS variable weight at index %d", i);

 /* Define mapping arrays to search large SOS's faster */
  if ((REALLOC(SOS->membersSorted, newsize ) == NULL) || (REALLOC(SOS->membersMapped, newsize ) == NULL))
    return(-1);
  for(i = oldsize+1; i <= newsize; i++) {
    SOS->membersSorted[i - 1] = SOS->members[i];
    SOS->membersMapped[i - 1] = i;
  }
  SortByINT(SOS->membersMapped, SOS->membersSorted, newsize, 0, TRUE);

 /* Confirm the new size */
  SOS->size = newsize;

  return(newsize);
}

static SOSrec *create_SOSrec(lprec *lp, char *name, short type, int priority, int size, int *variables, REAL *weights)
{
  SOSrec *SOS = NULL;

  if (CALLOC(SOS, 1) != NULL) {
    SOS->type = type;
    if(name == NULL)
      SOS->name = NULL;
    else
    {
      SOS->name = (char *) malloc(strlen(name)+1);
      strcpy(SOS->name, name);
    }
    if(type < 0)
      type = (short) abs(type);
    SOS->tagorder = 0;
    SOS->size = 0;
    SOS->priority = priority;
    SOS->members = NULL;
    SOS->weights = NULL;
    SOS->membersSorted = NULL;
    SOS->membersMapped = NULL;

    if(size > 0)
      if ((size = append_SOSrec(lp, SOS, size, variables, weights)) == -1) {
        FREE(SOS);
      }
  }
  return(SOS);
}

static int make_SOSchain(lprec *lp)
{
  int i, j, k, n;
  REAL *order, sum, weight;

  /* Tally SOS variables and create master SOS variable list */
  n = 0;
  for(i = 0; i < lp->sos_count; i++)
    n += lp->sos_list[i]->size;
  lp->sos_vars = n;
  if ((MALLOC(lp->sos_priority, n) == NULL) || (MALLOC(order, n) == NULL))
    return(-1);

  /* Move variable data to the master SOS list and sort */
  n = 0;
  sum = 0;
  for(i = 0; i < lp->sos_count; i++) {
    for(j = 1; j <= lp->sos_list[i]->size; j++) {
      lp->sos_priority[n] = lp->sos_list[i]->members[j];
      weight = lp->sos_list[i]->weights[j];
      sum += weight;
      order[n] = sum;
/*    order[n] = lp->sos_list[i]->priority * 1000000 + weight; */
      n++;
    }
  }
  i = SortByREAL(lp->sos_priority, order, n, 0, FALSE);

  /* Remove duplicate SOS variables */
  for(i = 0; i < n; i++) {
    /* Scan forward to look for duplicate variables */
    for(j = i+1; j < n; j++) {
      if(lp->sos_priority[i] == lp->sos_priority[j]) {
      /* Duplicate found, shrink the tail end of the list */