#include <string.h>
#include "commonlib.h"
#include "lp_lib.h"
#include "lp_report.h"
#include "lp_SOS.h"
#ifdef FORTIFY
# include "lp_fortify.h"
#endif
STATIC SOSgroup *create_SOSgroup(lprec *lp)
{
SOSgroup *group;
group = (SOSgroup *) calloc(1, sizeof(*group));
group->lp = lp;
group->sos_alloc = SOS_START_SIZE;
group->sos_list = (SOSrec **) malloc((group->sos_alloc) * sizeof(*group->sos_list));
return(group);
}
STATIC void resize_SOSgroup(SOSgroup *group)
{
if(group->sos_count == group->sos_alloc) {
group->sos_alloc = (int)((double) group->sos_alloc*RESIZEFACTOR);
group->sos_list = (SOSrec **) realloc(group->sos_list,
(group->sos_alloc) * sizeof(*group->sos_list));
}
}
STATIC int append_SOSgroup(SOSgroup *group, SOSrec *SOS)
{
int i, k;
SOSrec *SOSHold;
resize_SOSgroup(group);
group->sos_list[group->sos_count] = SOS;
group->sos_count++;
i = abs(SOS->type);
SETMAX(group->maxorder, i);
if(i == 1)
group->sos1_count++;
k = group->sos_count;
SOS->tagorder = k;
for(i = group->sos_count-1; i > 0; i--) {
if(group->sos_list[i]->priority < group->sos_list[i-1]->priority) {
SOSHold = group->sos_list[i];
group->sos_list[i] = group->sos_list[i-1];
group->sos_list[i-1] = SOSHold;
if(SOSHold == SOS)
k = i;
}
else
break;
}
return( k );
}
STATIC int clean_SOSgroup(SOSgroup *group, MYBOOL forceupdatemap)
{
int i, n, k;
SOSrec *SOS;
if(group == NULL)
return( 0 );
n = 0;
if(group->sos_alloc > 0) {
group->maxorder = 0;
for(i = group->sos_count; i > 0; i--) {
SOS = group->sos_list[i-1];
k = SOS->members[0];
if((k == 0) ||
((k == abs(SOS->type)) && (k <= 2))) {
delete_SOSrec(group, i);
n++;
}
else {
SETMAX(group->maxorder, abs(SOS->type));
}
}
if((n > 0) || forceupdatemap)
SOS_member_updatemap(group);
}
return( n );
}
STATIC void free_SOSgroup(SOSgroup **group)
{
int i;
if((group == NULL) || (*group == NULL))
return;
if((*group)->sos_alloc > 0) {
for(i = 0; i < (*group)->sos_count; i++)
free_SOSrec((*group)->sos_list[i]);
FREE((*group)->sos_list);
FREE((*group)->membership);
FREE((*group)->memberpos);
}
FREE(*group);
}
STATIC SOSrec *create_SOSrec(SOSgroup *group, char *name, int type, int priority, int size, int *variables, REAL *weights)
{
SOSrec *SOS;
SOS = (SOSrec *) calloc(1 , sizeof(*SOS));
SOS->parent = group;
SOS->type = type;
if(name == NULL)
SOS->name = NULL;
else
{
allocCHAR(group->lp, &SOS->name, (int) (strlen(name)+1), FALSE);
strcpy(SOS->name, name);
}
if(type < 0)
type = 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)
size = append_SOSrec(SOS, size, variables, weights);
return(SOS);
}
STATIC int append_SOSrec(SOSrec *SOS, int size, int *variables, REAL *weights)
{
int i, oldsize, newsize, nn;
lprec *lp = SOS->parent->lp;
oldsize = SOS->size;
newsize = oldsize + size;
nn = abs(SOS->type);
if(SOS->members == NULL)
allocINT(lp, &SOS->members, 1+newsize+1+nn, TRUE);
else {
allocINT(lp, &SOS->members, 1+newsize+1+nn, AUTOMATIC);
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;
if(SOS->weights == NULL)
allocREAL(lp, &SOS->weights, 1+newsize, TRUE);
else
allocREAL(lp, &SOS->weights, 1+newsize, AUTOMATIC);
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, "append_SOS_rec: Invalid SOS variable definition for index %d\n", SOS->members[i]);
else {
if(SOS->isGUB)
lp->var_type[SOS->members[i]] |= ISGUB;
else
lp->var_type[SOS->members[i]] |= ISSOS;
}
if(weights == NULL)
SOS->weights[i] = i;
else
SOS->weights[i] = weights[i-oldsize-1];
SOS->weights[0] += SOS->weights[i];
}
i = sortByREAL(SOS->members, SOS->weights, newsize, 1, TRUE);
if(i > 0)
report(lp, DETAILED, "append_SOS_rec: Non-unique SOS variable weight for index %d\n", i);
allocINT(lp, &SOS->membersSorted, newsize, AUTOMATIC);
allocINT(lp, &SOS->membersMapped, newsize, AUTOMATIC);
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);
SOS->size = newsize;
return(newsize);
}
STATIC int make_SOSchain(lprec *lp, MYBOOL forceresort)
{
int i, j, k, n;
MYBOOL *hold = NULL;
REAL *order, sum, weight;
SOSgroup *group = lp->SOS;
if(forceresort)
SOS_member_sortlist(group, 0);
n = 0;
for(i = 0; i < group->sos_count; i++)
n += group->sos_list[i]->size;
lp->sos_vars = n;
if(lp->sos_vars > 0)
FREE(lp->sos_priority);
allocINT(lp, &lp->sos_priority, n, FALSE);
allocREAL(lp, &order, n, FALSE);
n = 0;
sum = 0;
for(i = 0; i < group->sos_count; i++) {
for(j = 1; j <= group->sos_list[i]->size; j++) {
lp->sos_priority[n] = group->sos_list[i]->members[j];
weight = group->sos_list[i]->weights[j];
sum += weight;
order[n] = sum;
n++;
}
}
hpsortex(order, n, 0, sizeof(*order), FALSE, compareREAL, lp->sos_priority);
FREE(order);
allocMYBOOL(lp, &hold, lp->columns+1, TRUE);
k = 0;
for(i = 0; i < n; i++) {
j = lp->sos_priority[i];
if(!hold[j]) {
hold[j] = TRUE;
if(k < i)
lp->sos_priority[k] = j;
k++;
}
}
FREE(hold);
if(k < lp->sos_vars) {
allocINT(lp, &lp->sos_priority, k, AUTOMATIC);
lp->sos_vars = k;
}
return( k );
}
STATIC MYBOOL delete_SOSrec(SOSgroup *group, int sosindex)
{
#ifdef Paranoia
if((sosindex <= 0) || (sosindex > group->sos_count)) {
report(group->lp, IMPORTANT, "delete_SOSrec: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
#endif
if(abs(SOS_get_type(group, sosindex)) == 1)
group->sos1_count--;
free_SOSrec(group->sos_list[sosindex-1]);
while(sosindex < group->sos_count) {
group->sos_list[sosindex-1] = group->sos_list[sosindex];
sosindex++;
}
group->sos_count--;
group->maxorder = 0;
for(sosindex = 0; sosindex < group->sos_count; sosindex++) {
SETMAX(group->maxorder, abs(group->sos_list[sosindex]->type));
}
return(TRUE);
}
STATIC void free_SOSrec(SOSrec *SOS)
{
if(SOS->name != NULL)
FREE(SOS->name);
if(SOS->size > 0) {
FREE(SOS->members);
FREE(SOS->weights);
FREE(SOS->membersSorted);
FREE(SOS->membersMapped);
}
FREE(SOS);
}
STATIC MYBOOL SOS_member_sortlist(SOSgroup *group, int sosindex)
{
int i, n;
int *list;
lprec *lp = group->lp;
SOSrec *SOS;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_member_sortlist: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
#endif
if((sosindex == 0) && (group->sos_count == 1))
sosindex = 1;
if(sosindex == 0) {
for(i = 1; i <= group->sos_count; i++) {
if(!SOS_member_sortlist(group, i))
return(FALSE);
}
}
else {
SOS = group->sos_list[sosindex-1];
list = SOS->members;
n = list[0];
if(n != group->sos_list[sosindex-1]->size) {
allocINT(lp, &SOS->membersSorted, n, AUTOMATIC);
allocINT(lp, &SOS->membersMapped, n, AUTOMATIC);
group->sos_list[sosindex-1]->size = n;
}
for(i = 1; i <= n; i++) {
SOS->membersSorted[i - 1] = list[i];
SOS->membersMapped[i - 1] = i;
}
sortByINT(SOS->membersMapped, SOS->membersSorted, n, 0, TRUE);
}
return( TRUE );
}
STATIC int SOS_member_updatemap(SOSgroup *group)
{
int i, j, k, n, nvars = 0,
*list, *tally = NULL;
SOSrec *rec;
lprec *lp = group->lp;
allocINT(lp, &group->memberpos, lp->columns+1, AUTOMATIC);
allocINT(lp, &tally, lp->columns+1, TRUE);
for(i = 0; i < group->sos_count; i++) {
rec = group->sos_list[i];
n = rec->size;
list = rec->members;
for(j = 1; j <= n; j++) {
k = list[j];
#ifdef Paranoia
if((k < 1) || (k > lp->columns))
report(lp, SEVERE, "SOS_member_updatemap: Member %j of SOS number %d is out of column range (%d)\n",
j, i+1, k);
#endif
tally[k]++;
}
}
group->memberpos[0] = 0;
for(i = 1; i <= lp->columns; i++) {
n = tally[i];
if(n > 0)
nvars++;
group->memberpos[i] = group->memberpos[i-1] + n;
}
n = group->memberpos[lp->columns];
MEMCOPY(tally+1, group->memberpos, lp->columns);
allocINT(lp, &group->membership, n+1, AUTOMATIC);
for(i = 0; i < group->sos_count; i++) {
rec = group->sos_list[i];
n = rec->size;
list = rec->members;
for(j = 1; j <= n; j++) {
k = tally[list[j]]++;
#ifdef Paranoia
if(k > group->memberpos[lp->columns])
report(lp, SEVERE, "SOS_member_updatemap: Member mapping for variable %j of SOS number %d is invalid\n",
list[j], i+1);
#endif
group->membership[k] = i+1;
}
}
FREE(tally);
return( nvars );
}
STATIC MYBOOL SOS_shift_col(SOSgroup *group, int sosindex, int column, int delta, LLrec *usedmap, MYBOOL forceresort)
{
int i, ii, n, nn, nr;
int changed;
int *list;
REAL *weights;
#ifdef Paranoia
lprec *lp = group->lp;
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_shift_col: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
else if((column < 1) || (delta == 0)) {
report(lp, IMPORTANT, "SOS_shift_col: Invalid column %d specified with delta %d\n",
column, delta);
return(FALSE);
}
#endif
if((sosindex == 0) && (group->sos_count == 1))
sosindex = 1;
if(sosindex == 0) {
for(i = 1; i <= group->sos_count; i++) {
if(!SOS_shift_col(group, i, column, delta, usedmap, forceresort))
return(FALSE);
}
}
else {
list = group->sos_list[sosindex-1]->members;
weights = group->sos_list[sosindex-1]->weights;
n = list[0];
nn = list[n+1];
if(delta > 0) {
for(i = 1; i <= n; i++) {
if(list[i] >= column)
list[i] += delta;
}
}
else {
changed = 0;
if(usedmap != NULL) {
int *newidx = NULL;
if(newidx == NULL) {
allocINT(group->lp, &newidx, group->lp->columns+1, TRUE);
for(i = firstActiveLink(usedmap), ii = 1; i != 0;
i = nextActiveLink(usedmap, i), ii++)
newidx[i] = ii;
}
for(i = 1, ii = 0; i <= n; i++) {
nr = list[i];
if(!isActiveLink(usedmap, nr))
continue;
changed++;
ii++;
list[ii] = newidx[nr];
weights[ii] = weights[i];
}
FREE(newidx);
}
else
for(i = 1, ii = 0; i <= n; i++) {
nr = list[i];
if((nr >= column) && (nr < column-delta))
continue;
if(nr > column) {
changed++;
nr += delta;
}
ii++;
list[ii] = nr;
weights[ii] = weights[i];
}
if(ii < n) {
list[0] = ii;
list[ii+1] = nn;
}
if(forceresort && ((ii < n) || (changed > 0)))
SOS_member_sortlist(group, sosindex);
}
}
return(TRUE);
}
int SOS_member_count(SOSgroup *group, int sosindex)
{
SOSrec *SOS;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(group->lp, IMPORTANT, "SOS_member_count: Invalid SOS index %d\n", sosindex);
return( -1 );
}
#endif
SOS = group->sos_list[sosindex-1];
return( SOS->members[0] );
}
int SOS_member_delete(SOSgroup *group, int sosindex, int member)
{
int *list, i, i2, k, n, nn = 0;
SOSrec *SOS;
lprec *lp = group->lp;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(group->lp, IMPORTANT, "SOS_member_delete: Invalid SOS index %d\n", sosindex);
return( -1 );
}
#endif
if(sosindex == 0) {
for(i = group->memberpos[member-1]; i < group->memberpos[member]; i++) {
k = group->membership[i];
n = SOS_member_delete(group, k, member);
if(n >= 0)
nn += n;
else
return( n );
}
k = group->memberpos[member];
i = group->memberpos[member-1];
n = group->memberpos[lp->columns] - k;
if(n > 0)
MEMCOPY(group->membership + i, group->membership + k, n);
for(i = member; i <= lp->columns; i++)
group->memberpos[i] = group->memberpos[i-1];
}
else {
SOS = group->sos_list[sosindex-1];
list = SOS->members;
n = list[0];
i = 1;
while((i <= n) && (abs(list[i]) != member))
i++;
if(i > n)
return( -1 );
nn++;
while(i <= n) {
list[i] = list[i+1];
i++;
}
list[0]--;
SOS->size--;
i = n + 1;
i2 = i + list[n];
k = i + 1;
while(i < i2) {
if(abs(list[k]) == member)
k++;
list[i] = list[k];
i++;
k++;
}
}
return( nn );
}
int SOS_get_type(SOSgroup *group, int sosindex)
{
#ifdef Paranoia
if((sosindex < 1) || (sosindex > group->sos_count)) {
report(group->lp, IMPORTANT, "SOS_get_type: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
#endif
return(group->sos_list[sosindex-1]->type);
}
int SOS_infeasible(SOSgroup *group, int sosindex)
{
int i, n, nn, varnr, failindex, *list;
lprec *lp = group->lp;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_infeasible: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
#endif
if(sosindex == 0 && group->sos_count == 1)
sosindex = 1;
failindex = 0;
if(sosindex == 0) {
for(i = 1; i <= group->sos_count; i++) {
failindex = SOS_infeasible(group, i);
if(failindex > 0) break;
}
}
else {
list = group->sos_list[sosindex-1]->members;
n = list[0];
nn = list[n+1];
for(i = 1; i <= n; i++) {
varnr = abs(list[i]);
if((lp->orig_lowbo[lp->rows + varnr] > 0) &&
!((lp->sc_vars > 0) && is_semicont(lp, varnr)))
break;
}
i = i+nn;
while(i <= n) {
varnr = abs(list[i]);
if((lp->orig_lowbo[lp->rows + varnr] > 0) &&
!((lp->sc_vars > 0) && is_semicont(lp, varnr)))
break;
i++;
}
if(i <= n)
failindex = abs(list[i]);
}
return(failindex);
}
int SOS_member_index(SOSgroup *group, int sosindex, int member)
{
int n;
SOSrec *SOS;
SOS = group->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_memberships(SOSgroup *group, int varnr)
{
int i, n = 0;
lprec *lp;
if((group == NULL) || (SOS_count(lp = group->lp) == 0))
return( n );
#ifdef Paranoia
if((varnr < 0) || (varnr > lp->columns)) {
report(lp, IMPORTANT, "SOS_memberships: Invalid variable index %d given\n", varnr);
return( n );
}
#endif
if(varnr == 0) {
for(i = 1; i <= lp->columns; i++)
if(group->memberpos[i] > group->memberpos[i-1])
n++;
}
else
n = group->memberpos[varnr] - group->memberpos[varnr-1];
return( n );
}
int SOS_is_member(SOSgroup *group, int sosindex, int column)
{
int i, n = FALSE, *list;
lprec *lp;
if(group == NULL)
return( FALSE );
lp = group->lp;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_is_member: Invalid SOS index %d\n", sosindex);
return(n);
}
#endif
if(sosindex == 0) {
if(lp->var_type[column] & (ISSOS | ISGUB))
n = (MYBOOL) (SOS_memberships(group, column) > 0);
}
else if(lp->var_type[column] & (ISSOS | ISGUB)) {
i = SOS_member_index(group, sosindex, column);
if(i > 0) {
list = group->sos_list[sosindex-1]->members;
if(list[i] < 0)
n = -TRUE;
else
n = TRUE;
}
}
return(n);
}
MYBOOL SOS_is_member_of_type(SOSgroup *group, int column, int sostype)
{
int i, k, n;
if(group != NULL)
for(i = group->memberpos[column-1]; i < group->memberpos[column]; i++) {
k = group->membership[i];
n = SOS_get_type(group, k);
if(((n == sostype) ||
((sostype == SOSn) && (n > 2))) && SOS_is_member(group, k, column))
return(TRUE);
}
return(FALSE);
}
MYBOOL SOS_set_GUB(SOSgroup *group, int sosindex, MYBOOL state)
{
int i;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(group->lp, IMPORTANT, "SOS_set_GUB: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
#endif
if((sosindex == 0) && (group->sos_count == 1))
sosindex = 1;
if(sosindex == 0) {
for(i = 1; i <= group->sos_count; i++)
SOS_set_GUB(group, i, state);
}
else
group->sos_list[sosindex-1]->isGUB = state;
return(TRUE);
}
MYBOOL SOS_is_GUB(SOSgroup *group, int sosindex)
{
int i;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(group->lp, IMPORTANT, "SOS_is_GUB: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
#endif
if((sosindex == 0) && (group->sos_count == 1))
sosindex = 1;
if(sosindex == 0) {
for(i = 1; i <= group->sos_count; i++) {
if(SOS_is_GUB(group, i))
return(TRUE);
}
return(FALSE);
}
else
return( group->sos_list[sosindex-1]->isGUB );
}
MYBOOL SOS_is_marked(SOSgroup *group, int sosindex, int column)
{
int i, k, n, *list;
lprec *lp;
if(group == NULL)
return( FALSE );
lp = group->lp;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_is_marked: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
#endif
if(!(lp->var_type[column] & (ISSOS | ISGUB)))
return(FALSE);
if(sosindex == 0) {
for(i = group->memberpos[column-1]; i < group->memberpos[column]; i++) {
k = group->membership[i];
n = SOS_is_marked(group, k, column);
if(n)
return(TRUE);
}
}
else {
list = group->sos_list[sosindex-1]->members;
n = list[0];
column = -column;
for(i = 1; i <= n; i++)
if(list[i] == column)
return(TRUE);
}
return(FALSE);
}
MYBOOL SOS_is_active(SOSgroup *group, int sosindex, int column)
{
int i, n, nn, *list;
lprec *lp = group->lp;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_is_active: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
#endif
if(!(lp->var_type[column] & (ISSOS | ISGUB)))
return(FALSE);
if(sosindex == 0) {
for(i = group->memberpos[column-1]; i < group->memberpos[column]; i++) {
nn = group->membership[i];
n = SOS_is_active(group, nn, column);
if(n)
return(TRUE);
}
}
else {
list = group->sos_list[sosindex-1]->members;
n = list[0]+1;
nn = list[n];
for(i = 1; (i <= nn) && (list[n+i] != 0); i++)
if(list[n+i] == column)
return(TRUE);
}
return(FALSE);
}
MYBOOL SOS_is_full(SOSgroup *group, int sosindex, int column, MYBOOL activeonly)
{
int i, nn, n, *list;
lprec *lp = group->lp;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_is_full: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
#endif
if(!(lp->var_type[column] & (ISSOS | ISGUB)))
return(FALSE);
if(sosindex == 0) {
for(i = group->memberpos[column-1]; i < group->memberpos[column]; i++) {
nn = group->membership[i];
if(SOS_is_full(group, nn, column, activeonly))
return(TRUE);
}
}
else if(SOS_is_member(group, sosindex, column)) {
list = group->sos_list[sosindex-1]->members;
n = list[0]+1;
nn = list[n];
if(list[n+nn] != 0)
return(TRUE);
if(!activeonly) {
for(i = nn-1; (i > 0) && (list[n+i] == 0); i--);
if(i > 0) {
nn -= i;
i = SOS_member_index(group, sosindex, list[n+i]);
for(; (nn > 0) && (list[i] < 0); i++, nn--);
if(nn == 0)
return(TRUE);
}
}
}
return(FALSE);
}
MYBOOL SOS_can_activate(SOSgroup *group, int sosindex, int column)
{
int i, n, nn, nz, *list;
lprec *lp;
if(group == NULL)
return( FALSE );
lp = group->lp;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_can_activate: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
#endif
if(!(lp->var_type[column] & (ISSOS | ISGUB)))
return(FALSE);
if(sosindex == 0) {
for(i = group->memberpos[column-1]; i < group->memberpos[column]; i++) {
nn = group->membership[i];
n = SOS_can_activate(group, nn, column);
if(n == FALSE)
return(FALSE);
}
}
else if(SOS_is_member(group, sosindex, column)) {
list = group->sos_list[sosindex-1]->members;
n = list[0]+1;
nn = list[n];
#if 0#endif
if(list[n+nn] != 0)
return(FALSE);
nz = 0;
for(i = 1; i < n; i++)
if(lp->bb_bounds->lowbo[lp->rows+abs(list[i])] > 0) {
nz++;
if(list[i] == column)
return(FALSE);
}
#ifdef Paranoia
if(nz > nn)
report(lp, SEVERE, "SOS_can_activate: Found too many non-zero member variables for SOS index %d\n", sosindex);
#endif
for(i = 1; i <= nn; i++) {
if(list[n+i] == 0)
break;
if(lp->bb_bounds->lowbo[lp->rows+list[n+i]] == 0)
nz++;
}
if(nz == nn)
return(FALSE);
if(list[n+1] == 0)
return(TRUE);
if(nn > 1) {
for(i = 1; i <= nn; i++) {
if(list[n+i] == 0)
break;
if(list[n+i] == column)
return(FALSE);
}
i--;
nn = list[n+i];
n = list[0];
for(i = 1; i <= n; i++)
if(abs(list[i]) == nn)
break;
if(i > n) {
report(lp, CRITICAL, "SOS_can_activate: Internal index error at SOS %d\n", sosindex);
return(FALSE);
}
if((i > 1) && (list[i-1] == column))
return(TRUE);
if((i < n) && (list[i+1] == column))
return(TRUE);
return(FALSE);
}
}
return(TRUE);
}
MYBOOL SOS_set_marked(SOSgroup *group, int sosindex, int column, MYBOOL asactive)
{
int i, n, nn, *list;
lprec *lp = group->lp;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_set_marked: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
#endif
if(!(lp->var_type[column] & (ISSOS | ISGUB)))
return(FALSE);
if(sosindex == 0) {
if(asactive && !is_int(lp, column) && SOS_is_member_of_type(group, column, SOS3)) {
lp->var_type[column] |= ISSOSTEMPINT;
set_int(lp, column, TRUE);
}
nn = 0;
for(i = group->memberpos[column-1]; i < group->memberpos[column]; i++) {
n = group->membership[i];
if(SOS_set_marked(group, n, column, asactive))
nn++;
}
return((MYBOOL) (nn == group->sos_count));
}
else {
list = group->sos_list[sosindex-1]->members;
n = list[0]+1;
nn = list[n];
i = SOS_member_index(group, sosindex, column);
if((i > 0) && (list[i] > 0))
list[i] *= -1;
else
return(TRUE);
if(asactive) {
for(i = 1; i <= nn; i++) {
if(list[n+i] == column)
return(FALSE);
else if(list[n+i] == 0) {
list[n+i] = column;
return(FALSE);
}
}
}
return(TRUE);
}
}
MYBOOL SOS_unmark(SOSgroup *group, int sosindex, int column)
{
int i, n, nn, *list;
MYBOOL isactive;
lprec *lp = group->lp;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_unmark: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
#endif
if(!(lp->var_type[column] & (ISSOS | ISGUB)))
return(FALSE);
if(sosindex == 0) {
if(lp->var_type[column] & ISSOSTEMPINT) {
lp->var_type[column] &= !ISSOSTEMPINT;
set_int(lp, column, FALSE);
}
nn = 0;
for(i = group->memberpos[column-1]; i < group->memberpos[column]; i++) {
n = group->membership[i];
if(SOS_unmark(group, n, column))
nn++;
}
return((MYBOOL) (nn == group->sos_count));
}
else {
list = group->sos_list[sosindex-1]->members;
n = list[0]+1;
nn = list[n];
i = SOS_member_index(group, sosindex, column);
if((i > 0) && (list[i] < 0))
list[i] *= -1;
else
return(TRUE);
isactive = SOS_is_active(group, sosindex, column);
if(isactive) {
for(i = 1; i <= nn; i++)
if(list[n+i] == column)
break;
if(i <= nn) {
for(; i<nn; i++)
list[n+i] = list[n+i+1];
list[n+nn] = 0;
return(TRUE);
}
return(FALSE);
}
else
return(TRUE);
}
}
int SOS_fix_unmarked(SOSgroup *group, int sosindex, int variable, REAL *bound, REAL value, MYBOOL isupper,
int *diffcount, DeltaVrec *changelog)
{
int i, ii, count, n, nn, nLeft, nRight, *list;
lprec *lp = group->lp;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_fix_unmarked: Invalid SOS index %d\n", sosindex);
return(FALSE);
}
#endif
count = 0;
if(sosindex == 0) {
for(i = group->memberpos[variable-1]; i < group->memberpos[variable]; i++) {
n = group->membership[i];
count += SOS_fix_unmarked(group, n, variable, bound, value, isupper, diffcount, changelog);
}
}
else {
list = group->sos_list[sosindex-1]->members;
n = list[0]+1;
nn = list[n];
for(i = 1; i <= nn; i++) {
if(list[n+i] == 0)
break;
}
i--;
i = nn - i;
if(i == nn) {
nLeft = 0;
nRight = SOS_member_index(group, sosindex, variable);
}
else {
nLeft = SOS_member_index(group, sosindex, list[n+1]);
if(variable == list[n+1])
nRight = nLeft;
else
nRight = SOS_member_index(group, sosindex, variable);
}
nRight += i;
for(i = 1; i < n; i++) {
if((i >= nLeft) && (i <= nRight))
continue;
ii = list[i];
if(ii > 0) {
ii += lp->rows;
if(bound[ii] != value) {
if(isupper && (value < lp->orig_lowbo[ii]))
return(-ii);
else if(!isupper && (value > lp->orig_upbo[ii]))
return(-ii);
count++;
if(changelog == NULL)
bound[ii] = value;
else
modifyUndoLadder(changelog, ii, bound, value);
}
if((diffcount != NULL) && (lp->solution[ii] != value))
(*diffcount)++;
}
}
}
return(count);
}
int *SOS_get_candidates(SOSgroup *group, int sosindex, int column, MYBOOL excludetarget,
REAL *upbound, REAL *lobound)
{
int i, ii, j, n, nn = 0, *list, *candidates = NULL;
lprec *lp = group->lp;
if(group == NULL)
return( candidates );
#ifdef Paranoia
if(sosindex > group->sos_count) {
report(lp, IMPORTANT, "SOS_get_candidates: Invalid index %d\n", sosindex);
return( candidates );
}
#endif
if(sosindex <= 0) {
i = 0;
ii = group->sos_count;
}
else {
i = sosindex - 1;
ii = sosindex;
}
allocINT(lp, &candidates, lp->columns+1, TRUE);
for(; i < ii; i++) {
if(!SOS_is_member(group, i+1, column))
continue;
list = group->sos_list[i]->members;
n = list[0];
while(n > 0) {
j = list[n];
if((j > 0) && (upbound[lp->rows+j] > 0)) {
if(lobound[lp->rows+j] > 0) {
report(lp, IMPORTANT, "SOS_get_candidates: Invalid non-zero lower bound setting\n");
n = 0;
goto Finish;
}
if(candidates[j] == 0)
nn++;
candidates[j]++;
}
n--;
}
if((sosindex < 0) && (nn > 1))
break;
}
n = 0;
for(i = 1; i <= lp->columns; i++) {
if((candidates[i] > 0) && (!excludetarget || (i != column))) {
n++;
candidates[n] = i;
}
}
Finish:
candidates[0] = n;
if(n == 0)
FREE(candidates);
return( candidates);
}
int SOS_fix_list(SOSgroup *group, int sosindex, int variable, REAL *bound,
int *varlist, MYBOOL isleft, DeltaVrec *changelog)
{
int i, ii, jj, count = 0;
REAL value = 0;
lprec *lp = group->lp;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_fix_list: Invalid index %d\n", sosindex);
return(FALSE);
}
#endif
if(sosindex == 0) {
for(i = group->memberpos[variable-1]; i < group->memberpos[variable]; i++) {
ii = group->membership[i];
count += SOS_fix_list(group, ii, variable, bound, varlist, isleft, changelog);
}
}
else {
ii = varlist[0] / 2;
if(isleft) {
i = 1;
if(isleft == AUTOMATIC)
ii = varlist[0];
}
else {
i = ii + 1;
ii = varlist[0];
}
while(i <= ii) {
if(SOS_is_member(group, sosindex, varlist[i])) {
jj = lp->rows + varlist[i];
if(value < lp->orig_lowbo[jj])
return( -jj );
count++;
if(changelog == NULL)
bound[jj] = value;
else
modifyUndoLadder(changelog, jj, bound, value);
}
i++;
}
}
return( count );
}
int SOS_is_satisfied(SOSgroup *group, int sosindex, REAL *solution)
{
int i, n, nn, count, *list;
int type, status = 0;
lprec *lp = group->lp;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_is_satisfied: Invalid index %d\n", sosindex);
return( SOS_COMPLETE );
}
#endif
if((sosindex == 0) && (group->sos_count == 1))
sosindex = 1;
if(sosindex == 0) {
for(i = 1; i <= group->sos_count; i++) {
status = SOS_is_satisfied(group, i, solution);
if((status != SOS_COMPLETE) && (status != SOS_INCOMPLETE))
break;
}
}
else {
type = SOS_get_type(group, sosindex);
list = group->sos_list[sosindex-1]->members;
n = list[0]+1;
nn = list[n];
for(i = 1; i <= nn; i++) {
if(list[n+i] == 0)
break;
}
count = i-1;
if(count == nn)
status = SOS_COMPLETE;
else
status = SOS_INCOMPLETE;
if(count > 0) {
nn = list[n+1];
for(i = 1; i < n; i++) {
if((abs(list[i]) == nn) || (solution[lp->rows + abs(list[i])] != 0))
break;
}
if(abs(list[i]) != nn)
status = SOS_INTERNALERROR;
else {
while(count > 0) {
if(solution[lp->rows + abs(list[i])] != 0)
break;
i++;
count--;
}
while(count > 0) {
if(solution[lp->rows + abs(list[i])] == 0)
break;
i++;
count--;
}
if(count > 0)
status = SOS_INTERNALERROR;
}
}
else {
i = 1;
while((i < n) && (solution[lp->rows + abs(list[i])] == 0))
i++;
count = 0;
while((i < n) && (count <= nn) && (solution[lp->rows + abs(list[i])] != 0)) {
count++;
i++;
}
if(count > nn)
status = SOS_INFEASIBLE;
}
if(status <= 0) {
n--;
while(i <= n) {
if(solution[lp->rows + abs(list[i])] != 0)
break;
i++;
}
if(i <= n)
status = SOS_INFEASIBLE;
else if((status == -1) && (type <= SOS3))
status = SOS3_INCOMPLETE;
}
}
return( status );
}
MYBOOL SOS_is_feasible(SOSgroup *group, int sosindex, REAL *solution)
{
int i, n, nn, *list;
MYBOOL status = TRUE;
lprec *lp = group->lp;
#ifdef Paranoia
if((sosindex < 0) || (sosindex > group->sos_count)) {
report(lp, IMPORTANT, "SOS_is_feasible: Invalid SOS index %d\n", sosindex);
return( 0 );
}
#endif
if((sosindex == 0) && (group->sos_count == 1))
sosindex = 1;
if(sosindex == 0) {
for(i = 1; status && (i <= group->sos_count); i++) {
status = SOS_is_feasible(group, i, solution);
}
}
else {
list = group->sos_list[sosindex-1]->members;
n = list[0]+1;
nn = list[n];
if(nn <= 2)
return(status);
i = 1;
sosindex = 0;
while((i <= nn) && (list[n+i] != 0)) {
while((i <= nn) && (list[n+i] != 0) && (solution[lp->rows+list[n+i]] == 0))
i++;
if((i <= nn) && (list[n+i] != 0)) {
i++;
while((i <= nn) && (list[n+i] != 0) && (solution[lp->rows+list[n+i]] != 0))
i++;
sosindex++;
}
i++;
}
status = (MYBOOL) (sosindex <= 1);
}
return(status);
}