lpkit.c

利用c语言编写

	for(k = j+1; k < n; k++)
          lp->sos_priority[k-1] = lp->sos_priority[k];
	n--;
      }
    }
  }

  /* Adjust the size of the master variable list, if necessary*/
  if(n < lp->sos_vars) {
    if (REALLOC(lp->sos_priority, n) == NULL)
      n = -1;
    lp->sos_vars = n;
  }

  free(order);
  return(n);
}

int is_int(lprec *lp, int column)
{
  if(column > lp->columns || column < 1) {
    report(lp, IMPORTANT, "is_int: Column %d out of range", column);
    return(FALSE);
  }
  return((lp->must_be_int[column] & ISINTEGER) != 0);
}

int set_semicont(lprec *lp, int column, short must_be_sc)
{
  if(column > lp->columns || column < 1) {
    report(lp, IMPORTANT, "set_semicont: Column %d out of range", column);
    return(FALSE);
  }
  if(lp->var_is_sc[column] != 0) {
    lp->sc_count--;
    lp->must_be_int[column] &= !ISSEMI;
  }
  lp->var_is_sc[column] = must_be_sc;
  if(must_be_sc) {
    lp->must_be_int[column] |= ISSEMI;
    lp->sc_count++;
  }
  return(TRUE);
}

int is_semicont(lprec *lp, int column)
{
  if(column > lp->columns || column < 1) {
    report(lp, IMPORTANT, "is_semicont: Column %d out of range", column);
    return(FALSE);
  }
  return((lp->must_be_int[column] & ISSEMI) != 0);
}

int is_SOS_var(lprec *lp, int column)
{
  if(column > lp->columns || column < 1) {
    report(lp, IMPORTANT, "is_SOS_var: Column %d out of range", column);
    return(FALSE);
  }
  return((lp->must_be_int[column] & ISSOS) != 0);
}

int add_SOS(lprec *lp, char *name, short sostype, int priority, int count, int *sosvars, REAL *weights)
{
  SOSrec *SOS, *SOSHold;
  int i,k;

  if((sostype<1) || (sostype>3) || (count<0)) {
    report(lp, IMPORTANT, "add_SOS: Invalid SOS type definition %d", sostype);
    return(FALSE);
  }
  /* Make size in the list to handle another SOS record */
  if(lp->sos_alloc == 0) {
    lp->sos_alloc = SOS_START_SIZE;
    if (MALLOC(lp->sos_list, lp->sos_alloc) == NULL) {
      lp->spx_status = OUT_OF_MEMORY;
      return(FALSE);
    }
  }
  else if(lp->sos_count == lp->sos_alloc) {
    lp->sos_alloc = (int)((double) lp->sos_alloc*RESIZEFACTOR);
    if (REALLOC(lp->sos_list, lp->sos_alloc) == NULL) {
      lp->spx_status = OUT_OF_MEMORY;
      return(FALSE);
    }
  }

  /* Create and append SOS to list */
  if ((SOS = create_SOSrec(lp, name, sostype, priority, count, sosvars, weights)) == NULL) {
    lp->spx_status = OUT_OF_MEMORY;
    return(FALSE);
  }
  lp->sos_list[lp->sos_count] = SOS;
  lp->sos_count++;
  k = lp->sos_count;
  SOS->tagorder = k;

  /* Sort the SOS list by given priority */

  for(i = lp->sos_count-1; i > 0; i--)
    if(lp->sos_list[i]->priority < lp->sos_list[i-1]->priority) {
      SOSHold = lp->sos_list[i];
      lp->sos_list[i] = lp->sos_list[i-1];
      lp->sos_list[i-1] = SOSHold;
      if(SOSHold == SOS)
	k = i-1;
    }
    else
      break;

  return(k);
}

int SOS_get_type(lprec *lp, int sosindex)
{
  if((sosindex<1) || (sosindex>lp->sos_count)) {
    report(lp, IMPORTANT, "SOS_get_type: Invalid SOS index %d", sosindex);
    return(FALSE);
  }
  return(lp->sos_list[sosindex-1]->type);
}

int SOS_infeasible(lprec *lp, int sosindex)
{
  int i, n, nn, failindex;
  int *list;

  if((sosindex<0) || (sosindex>lp->sos_count)) {
    report(lp, IMPORTANT, "SOS_infeasible: Invalid SOS index %d", sosindex);
    return(FALSE);
  }

  if(sosindex == 0 && lp->sos_count == 1)
    sosindex = 1;

  failindex = 0;
  if(sosindex == 0) {
    for(i = 1; i <= lp->sos_count; i++) {
      failindex = SOS_infeasible(lp, i);
      if(failindex > 0) break;
    }
  }
  else {
    list = lp->sos_list[sosindex-1]->members;
    n = list[0];
    nn = list[n+1];
   /* Find index of next lower-bounded variable */
    for(i = 1; i <= n; i++) {
      if(lp->orig_lowbo[lp->rows + abs(list[i])] > 0)
	break;
    }

   /* Find if there is another lower-bounded variable beyond the type window */
    i = i + nn;
    while(i <= n) {
      if(lp->orig_lowbo[lp->rows + abs(list[i])] > 0)
	break;
      i++;
    }
    if(i <= n)
      failindex = abs(list[i]);
  }
  return(failindex);
}

int SOS_member_index(lprec *lp, int sosindex, int member)
{
  int n;
  SOSrec *SOS;

  SOS = lp->sos_list[sosindex-1];
  n = SOS->members[0];

  n = SearchFor(member, SOS->membersSorted, n, 0, FALSE);
  if(n >= 0)
    n = SOS->membersMapped[n];

  return(n);
}

int SOS_is_member(lprec *lp, int sosindex, int column)
{
  int i;
  short n;
  int *list;

  n = FALSE;
  if((sosindex<0) || (sosindex>lp->sos_count)) {
    report(lp, IMPORTANT, "SOS_is_member: Invalid SOS index %d", sosindex);
    return(n);
  }

  if(sosindex == 0 && lp->sos_count == 1)
    sosindex = 1;

  if(sosindex == 0) {
    if(lp->must_be_int[column] & ISSOS) {
      for(i = 1; i <= lp->sos_count; i++) {
        n = (short) SOS_is_member(lp, i, column);
	if(n != FALSE) break;
      }
    }
  }
  else if(lp->must_be_int[column] & ISSOS) {

   /* Search for the variable */
    i = SOS_member_index(lp, sosindex, column);

   /* Signal active status if found, otherwise return FALSE */
    if(i > 0) {
      list = lp->sos_list[sosindex-1]->members;
      if(list[i] < 0)
        n = -TRUE;
      else
	n = TRUE;
    }
  }
  return(n);
}

MYBOOL SOS_is_member_of_type(lprec *lp, int column, short sostype)
{
  int i;

  for(i = 1; i <= lp->sos_count; i++) {
    if(SOS_get_type(lp, i) == sostype && SOS_is_member(lp, i, column))
      return(TRUE);
  }
  return(FALSE);
}

MYBOOL SOS_is_marked(lprec *lp, int sosindex, int column)
{
  int i, n, nn;
  int *list;

  if((sosindex<0) || (sosindex>lp->sos_count)) {
    report(lp, IMPORTANT, "SOS_is_marked: Invalid SOS index %d", sosindex);
    return(FALSE);
  }
  if(!(lp->must_be_int[column] & ISSOS))
    return(FALSE);

  if(sosindex == 0 && lp->sos_count == 1)
    sosindex = 1;

  if(sosindex == 0) {
    for(i = 1; i<=lp->sos_count; i++) {
      nn = SOS_is_marked(lp, i, column);
      if(nn) return(TRUE);
    }
  }
  else
  {
    list = lp->sos_list[sosindex-1]->members;
    n = list[0]+1;
    nn = list[n];

   /* Search for the variable (normally always faster to do linear search here) */
    for(i = 1; i <= nn; i++)
      if(list[n+i] == column)
        return(TRUE);
  }
  return(FALSE);
}

MYBOOL SOS_is_active(lprec *lp, int sosindex, int column)
{
  int i, n;

  if((sosindex<0) || (sosindex>lp->sos_count)) {
    report(lp, IMPORTANT, "SOS_is_active: Invalid SOS index %d", sosindex);
    return(FALSE);
  }
  if(!(lp->must_be_int[column] & ISSOS))
    return(FALSE);

  if(sosindex == 0 && lp->sos_count == 1)
    sosindex = 1;

  if(sosindex == 0) {
    for(i = 1; i<=lp->sos_count; i++) {
      n = SOS_is_active(lp, i, column);
      if(n) return(TRUE);
    }
  }
  else {

   /* Search for the variable */
    i = SOS_member_index(lp, sosindex, column);
    if(i > 0) {
      if(lp->sos_list[sosindex-1]->members[i] < 0)
        return(TRUE);
    }
  }
  return(FALSE);
}

MYBOOL SOS_can_mark(lprec *lp, int sosindex, int column)
{
  int i, n, nn;
  int *list;
  short type;

  if((sosindex<0) || (sosindex>lp->sos_count)) {
    report(lp, IMPORTANT, "SOS_can_mark: Invalid SOS index %d", sosindex);
    return(FALSE);
  }

  if(!(lp->must_be_int[column] & ISSOS))
    return(FALSE);

  if(sosindex == 0 && lp->sos_count == 1)
    sosindex = 1;

  if(sosindex == 0) {
    for(i = 1; i<=lp->sos_count; i++) {
      nn = SOS_can_mark(lp, i, column);
      if(nn == FALSE)
        return(FALSE);
    }
  }
  else if(SOS_is_member(lp, sosindex, column)) {
    type = (short) abs(SOS_get_type(lp, sosindex));
    list = lp->sos_list[sosindex-1]->members;
    n = list[0]+1;

   /* Accept if the SOS is empty */
    if(list[n+1] == 0)
      return(TRUE);

   /* Cannot activate a variable if the SOS is full */
    if(list[n+type] != 0)
      return(FALSE);

   /* Check if we can set variable active in SOS2..SOSn
     (must check left and right neighbours if one variable is already active) */
    if(type > 1) {

     /* Find the variable that was last activated;
	   	Also check that the candidate variable is not already active */
      for(i = 1; i <= type; i++) {
        nn = list[n+i];
	if(nn == 0)
	  break;
        if(nn == column)
          return(FALSE);
      }
      i--;
      nn = list[n+i];

     /* SOS accepts an additional variable; confirm neighbourness of candidate
        Search for the SOS set index of the last activated variable */
      n = list[0];
      for(i = 1; i < n; i++)
        if(abs(list[i]) == nn) break;

     /* SOS accepts an additional variable; confirm neighbourness of candidate */
      if(i < n) {
       /* Check left neighbour */
        if((i > 1) && (list[i-1] == column))
          return(TRUE);
       /* Check right neighbour */
        if((i < n-1) && (list[i+1] == column))
          return(TRUE);
        return(FALSE);
      }
      report(lp, CRITICAL, "SOS_can_mark: Internal index error at SOS %d", sosindex);
    }
  }
  return(TRUE);
}

MYBOOL SOS_set_marked(lprec *lp, int sosindex, int column, MYBOOL islive)
{
  int i, n, nn;
  int *list;

  if((sosindex<0) || (sosindex>lp->sos_count)) {
    report(lp, IMPORTANT, "SOS_set_marked: Invalid SOS index %d", sosindex);
    return(FALSE);
  }

  if(!(lp->must_be_int[column] & ISSOS))
    return(FALSE);

  if(sosindex == 0 && lp->sos_count == 1)
    sosindex = 1;

 /* Define an IBM-"SOS3" member variable temporarily as integer, if it is
    not already a permanent integer; is reset in SOS_unmark */
  if(islive && !is_int(lp, column) && SOS_is_member_of_type(lp, column, SOS3)) {
    lp->must_be_int[column] |= ISSOSTEMPINT;
    set_int(lp, column, TRUE);
  }

  if(sosindex == 0) {
    for(i = 1; i<=lp->sos_count; i++) {
      nn = SOS_set_marked(lp, i, column, islive);
    }
    return(TRUE);
  }
  else
  {
    list = lp->sos_list[sosindex-1]->members;
    n = list[0]+1;
    nn = list[n];

   /* Search for the variable */
    i = SOS_member_index(lp, sosindex, column);

   /* First mark active in the set member list as used */
    if(i > 0 && list[i] > 0)
      list[i] *= -1;
    else
      return(FALSE);

   /* The move the variable to the live list */
    if(islive) {
      for(i = 1; i <= nn; i++) {
        if(list[n+i] == column)
          return(TRUE);
	else if(list[n+i] == 0) {
          list[n+i] = column;
          return(TRUE);
	}
      }
    }
    return(FALSE);
  }
}

MYBOOL SOS_unmark(lprec *lp, int sosindex, int column, MYBOOL islive)
{
  int i, n, nn;
  int *list;

  if((sosindex<0) || (sosindex>lp->sos_count)) {
    report(lp, IMPORTANT, "SOS_unmark: Invalid SOS index %d", sosindex);
    return(FALSE);
  }

  if(!(lp->must_be_int[column] & ISSOS))
    return(FALSE);

  if(sosindex == 0 && lp->sos_count == 1)
    sosindex = 1;

 /* Undefine a SOS3 member variable that has temporarily been set as integer */
  if(islive && (lp->must_be_int[column] & ISSOSTEMPINT)) {
    lp->must_be_int[column] &= !ISSOSTEMPINT;
    set_int(lp, column, FALSE);
  }

  if(sosindex == 0) {
    for(i = 1; i<=lp->sos_count; i++)
      nn = SOS_unmark(lp, i, column, islive);
    return(TRUE);
  }
  else
  {
    list = lp->sos_list[sosindex-1]->members;
    n = list[0]+1;
    nn = list[n];

   /* Search for the variable */
    i = SOS_member_index(lp, sosindex, column);

   /* Restore sign in main list */
    if(i > 0 && list[i] < 0)
      list[i] *= -1;
    else
      return(FALSE);

   /* Find the variable in the marked list... */
    if(i < n && islive) {
      for(i = 1; i <= nn; i++)
        if(list[n+i] == column)
          break;
     /* ...shrink the list if found, otherwise return error */
      if(i<=nn) {
        for(; i<nn; i++)
	  list[n+i] = list[n+i+1];
        list[n+nn] = 0;
        return(TRUE);
      }
      return(FALSE);
    }
    else
      return(FALSE);
  }
}

int SOS_fix_unmarked(lprec *lp, int variable, int sosindex, REAL *bound, REAL value, MYBOOL isupper, int *diffcount)
{
  int i, ii, n, count;
  int *list;

  if((sosindex<0) || (sosindex>lp->sos_count)) {
    report(lp, IMPORTANT, "SOS_fix_unmarked: Invalid SOS index %d", sosindex);
    return(FALSE);
  }

  if(sosindex == 0 && lp->sos_count == 1)
    sosindex = 1;

  count = 0;
  if(sosindex == 0) {
    for(i = 1; i<=lp->sos_count; i++) {
      if(SOS_is_member(lp, i, variable))
      count += SOS_fix_unmarked(lp, variable, i, bound, value, isupper, diffcount);
    }
  }
  else
  {
    list = lp->sos_list[sosindex-1]->members;
    n = list[0]+1;

   /* Spool to the target variable */
/*  for(i = 1; i < n; i++) */
/*    if(abs(list[i]) == variable) */
/*	break; */

   /* Fix variables to the right */
/*  for(; i < n; i++)  { */

    for(i = 1; i < n; i++)  {
      ii = l