76#ifdef WITH_CARDINALITY_UPGRADE
81#define CONSHDLR_NAME "knapsack"
82#define CONSHDLR_DESC "knapsack constraint of the form a^T x <= b, x binary and a >= 0"
83#define CONSHDLR_SEPAPRIORITY +600000
84#define CONSHDLR_ENFOPRIORITY -600000
85#define CONSHDLR_CHECKPRIORITY -600000
86#define CONSHDLR_SEPAFREQ 0
87#define CONSHDLR_PROPFREQ 1
88#define CONSHDLR_EAGERFREQ 100
90#define CONSHDLR_MAXPREROUNDS -1
91#define CONSHDLR_DELAYSEPA FALSE
92#define CONSHDLR_DELAYPROP FALSE
93#define CONSHDLR_NEEDSCONS TRUE
95#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
96#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
98#define EVENTHDLR_NAME "knapsack"
99#define EVENTHDLR_DESC "bound change event handler for knapsack constraints"
100#define EVENTTYPE_KNAPSACK SCIP_EVENTTYPE_LBCHANGED \
101 | SCIP_EVENTTYPE_UBTIGHTENED \
102 | SCIP_EVENTTYPE_VARFIXED \
103 | SCIP_EVENTTYPE_VARDELETED \
104 | SCIP_EVENTTYPE_IMPLADDED
106#define LINCONSUPGD_PRIORITY +100000
108#define MAX_USECLIQUES_SIZE 1000
109#define MAX_ZEROITEMS_SIZE 10000
111#define KNAPSACKRELAX_MAXDELTA 0.1
112#define KNAPSACKRELAX_MAXDNOM 1000LL
113#define KNAPSACKRELAX_MAXSCALE 1000.0
115#define DEFAULT_SEPACARDFREQ 1
116#define DEFAULT_MAXROUNDS 5
117#define DEFAULT_MAXROUNDSROOT -1
118#define DEFAULT_MAXSEPACUTS 50
119#define DEFAULT_MAXSEPACUTSROOT 200
120#define DEFAULT_MAXCARDBOUNDDIST 0.0
122#define DEFAULT_DISAGGREGATION TRUE
123#define DEFAULT_SIMPLIFYINEQUALITIES TRUE
124#define DEFAULT_NEGATEDCLIQUE TRUE
126#define MAXABSVBCOEF 1e+5
127#define USESUPADDLIFT FALSE
129#define DEFAULT_PRESOLUSEHASHING TRUE
130#define HASHSIZE_KNAPSACKCONS 500
132#define DEFAULT_PRESOLPAIRWISE TRUE
133#define NMINCOMPARISONS 200000
134#define MINGAINPERNMINCOMPARISONS 1e-06
136#define DEFAULT_DUALPRESOLVING TRUE
137#define DEFAULT_DETECTCUTOFFBOUND TRUE
140#define DEFAULT_DETECTLOWERBOUND TRUE
143#define DEFAULT_CLIQUEEXTRACTFACTOR 0.5
144#define MAXCOVERSIZEITERLEWI 1000
146#define DEFAULT_USEGUBS FALSE
147#define GUBCONSGROWVALUE 6
148#define GUBSPLITGNC1GUBS FALSE
149#define DEFAULT_CLQPARTUPDATEFAC 1.5
151#define DEFAULT_UPDATECLIQUEPARTITIONS FALSE
152#define MAXNCLIQUEVARSCOMP 1000000
153#ifdef WITH_CARDINALITY_UPGRADE
154#define DEFAULT_UPGDCARDINALITY FALSE
164struct SCIP_ConshdlrData
170 SCIP_Longint* longints1;
172 SCIP_Longint* longints2;
194 SCIP_Real maxcardbounddist;
201 SCIP_Bool disaggregation;
202 SCIP_Bool simplifyinequalities;
203 SCIP_Bool negatedclique;
204 SCIP_Bool presolpairwise;
205 SCIP_Bool presolusehashing;
206 SCIP_Bool dualpresolving;
208 SCIP_Bool detectcutoffbound;
211 SCIP_Bool detectlowerbound;
214 SCIP_Bool updatecliquepartitions;
215 SCIP_Real cliqueextractfactor;
216 SCIP_Real clqpartupdatefac;
218#ifdef WITH_CARDINALITY_UPGRADE
219 SCIP_Bool upgdcardinality;
220 SCIP_Bool upgradedcard;
229 SCIP_Longint* weights;
231 int* cliquepartition;
232 int* negcliquepartition;
239 int ncliqueslastnegpart;
240 int ncliqueslastpart;
241 SCIP_Longint capacity;
242 SCIP_Longint weightsum;
243 SCIP_Longint onesweightsum;
244 unsigned int presolvedtiming:5;
245 unsigned int sorted:1;
246 unsigned int cliquepartitioned:1;
247 unsigned int negcliquepartitioned:1;
248 unsigned int merged:1;
249 unsigned int cliquesadded:1;
250 unsigned int varsdeleted:1;
251 unsigned int existmultaggr:1;
328 if( sortkeypair1->key1 < sortkeypair2->key1 )
330 else if( sortkeypair1->key1 > sortkeypair2->key1 )
332 else if( sortkeypair1->key2 < sortkeypair2->key2 )
334 else if( sortkeypair1->key2 > sortkeypair2->key2 )
352 (*eventdata)->cons = cons;
353 (*eventdata)->weight = weight;
379 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
380 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
381 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
382 assert(consdata->nvars == 0 || (consdata->cliquepartition !=
NULL && consdata->negcliquepartition !=
NULL));
384 if( !consdata->sorted )
394 (
void**)consdata->vars,
395 (
void**)consdata->eventdata,
396 consdata->cliquepartition,
397 consdata->negcliquepartition,
400 v = consdata->nvars - 1;
406 while(
w >= 0 && consdata->weights[v] == consdata->weights[
w] )
413 (
void**)(&(consdata->vars[
w+1])),
414 (
void**)(&(consdata->eventdata[
w+1])),
415 &(consdata->cliquepartition[
w+1]),
416 &(consdata->negcliquepartition[
w+1]),
424 if( consdata->cliquepartitioned )
428 for( pos = 0; pos < consdata->nvars; ++pos )
432 if( consdata->cliquepartition[pos] > lastcliquenum )
434 consdata->cliquepartitioned =
FALSE;
437 else if( consdata->cliquepartition[pos] == lastcliquenum )
442 if( consdata->negcliquepartitioned )
446 for( pos = 0; pos < consdata->nvars; ++pos )
450 if( consdata->negcliquepartition[pos] > lastcliquenum )
452 consdata->negcliquepartitioned =
FALSE;
455 else if( consdata->negcliquepartition[pos] == lastcliquenum )
460 consdata->sorted =
TRUE;
466 for(
i = 0;
i < consdata->nvars-1; ++
i )
467 assert(consdata->weights[
i] >= consdata->weights[
i+1]);
478 SCIP_Bool normalclique,
479 SCIP_Bool negatedclique
482 SCIP_Bool ispartitionoutdated;
483 SCIP_Bool isnegpartitionoutdated;
485 assert(consdata->nvars == 0 || (consdata->cliquepartition !=
NULL && consdata->negcliquepartition !=
NULL));
488 ispartitionoutdated = (conshdlrdata->updatecliquepartitions && consdata->ncliques > 1
489 &&
SCIPgetNCliques(
scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastpart));
491 if( normalclique && ( !consdata->cliquepartitioned || ispartitionoutdated ) )
494 consdata->cliquepartitioned =
TRUE;
499 isnegpartitionoutdated = (conshdlrdata->updatecliquepartitions && consdata->nnegcliques > 1
500 &&
SCIPgetNCliques(
scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastnegpart));
502 if( negatedclique && (!consdata->negcliquepartitioned || isnegpartitionoutdated) )
505 consdata->negcliquepartitioned =
TRUE;
508 assert(!consdata->cliquepartitioned || consdata->ncliques <= consdata->nvars);
509 assert(!consdata->negcliquepartitioned || consdata->nnegcliques <= consdata->nvars);
553 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
554 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
555 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
557 for(
i = 0;
i < consdata->nvars;
i++)
561 eventhdlr, consdata->eventdata[
i], &consdata->eventdata[
i]->filterpos) );
578 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
579 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
580 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
582 for(
i = 0;
i < consdata->nvars;
i++)
585 eventhdlr, consdata->eventdata[
i], consdata->eventdata[
i]->filterpos) );
598 SCIP_Bool transformed
602 assert(consdata->nvars <= consdata->varssize);
604 if( num > consdata->varssize )
623 consdata->varssize = newsize;
625 assert(num <= consdata->varssize);
635 SCIP_Longint weightdelta
641 consdata->weightsum += weightdelta;
644 consdata->onesweightsum += weightdelta;
646 assert(consdata->weightsum >= 0);
647 assert(consdata->onesweightsum >= 0);
657 SCIP_Longint* weights,
658 SCIP_Longint capacity
662 SCIP_Longint constant;
669 (*consdata)->vars =
NULL;
670 (*consdata)->weights =
NULL;
671 (*consdata)->nvars = 0;
675 SCIP_Longint* weightsbuffer;
682 for( v = 0; v <
nvars; ++v )
688 assert( weights[v] >= 0 );
697 constant += weights[v];
701 varsbuffer[k] =
vars[v];
702 weightsbuffer[k] = weights[v];
710 (*consdata)->nvars = k;
724 (*consdata)->varssize = (*consdata)->nvars;
725 (*consdata)->capacity = capacity - constant;
726 (*consdata)->eventdata =
NULL;
727 (*consdata)->cliquepartition =
NULL;
728 (*consdata)->negcliquepartition =
NULL;
729 (*consdata)->row =
NULL;
730 (*consdata)->nlrow =
NULL;
731 (*consdata)->weightsum = 0;
732 (*consdata)->onesweightsum = 0;
733 (*consdata)->ncliques = 0;
734 (*consdata)->nnegcliques = 0;
735 (*consdata)->presolvedtiming = 0;
736 (*consdata)->sorted =
FALSE;
737 (*consdata)->cliquepartitioned =
FALSE;
738 (*consdata)->negcliquepartitioned =
FALSE;
739 (*consdata)->ncliqueslastpart = -1;
740 (*consdata)->ncliqueslastnegpart = -1;
741 (*consdata)->merged =
FALSE;
742 (*consdata)->cliquesadded =
FALSE;
743 (*consdata)->varsdeleted =
FALSE;
744 (*consdata)->existmultaggr =
FALSE;
751 for( v = 0; v < (*consdata)->nvars; v++ )
765 for( v = 0; v < (*consdata)->nvars; ++v )
787 if( (*consdata)->row !=
NULL )
791 if( (*consdata)->nlrow !=
NULL )
795 if( (*consdata)->eventdata !=
NULL )
800 if( (*consdata)->negcliquepartition !=
NULL )
804 if( (*consdata)->cliquepartition !=
NULL )
808 if( (*consdata)->vars !=
NULL )
813 for( v = 0; v < (*consdata)->nvars; v++ )
820 assert( (*consdata)->varssize > 0 );
835 SCIP_Longint newweight
838 SCIP_Longint oldweight;
839 SCIP_Longint weightdiff;
844 oldweight = consdata->weights[item];
845 weightdiff = newweight - oldweight;
846 consdata->weights[item] = newweight;
851 if( consdata->eventdata !=
NULL )
854 assert(consdata->eventdata[item]->weight == oldweight);
855 consdata->eventdata[item]->weight = newweight;
858 consdata->presolvedtiming = 0;
859 consdata->sorted =
FALSE;
862 if( oldweight < newweight )
864 consdata->cliquesadded =
FALSE;
887 for(
i = 0;
i < consdata->nvars; ++
i )
912 if( consdata->row ==
NULL )
948 if( consdata->nlrow ==
NULL )
954 for(
i = 0;
i < consdata->nvars; ++
i )
955 coefs[
i] = (SCIP_Real)consdata->weights[
i];
958 consdata->nvars, consdata->vars, coefs,
NULL,
980 SCIP_Bool checklprows,
981 SCIP_Bool printreason,
992 SCIPdebugMsg(
scip,
"checking knapsack constraint <%s> for feasibility of solution %p (lprows=%u)\n",
999 SCIP_Real normsum = 0.0;
1000 SCIP_Real hugesum = 0.0;
1014 for( v = consdata->nvars - 1; v >= 0; --v )
1027 if( normsum > consdata->capacity )
1029 absviol = normsum - consdata->capacity;
1030 relviol =
SCIPrelDiff(normsum, (SCIP_Real)consdata->capacity);
1065#define IDX(j,d) ((j)*(intcap)+(d))
1089 SCIP_Longint* weights,
1091 SCIP_Longint capacity,
1103 SCIP_Real* tempsort;
1104 SCIP_Real* optvalues;
1108 int greedymedianpos;
1109 SCIP_Longint weightsum;
1111 SCIP_Longint* myweights;
1112 SCIP_Real* realweights;
1113 int* allcurrminweight;
1114 SCIP_Real* myprofits;
1117 SCIP_Longint minweight;
1118 SCIP_Longint maxweight;
1120 SCIP_Longint greedysolweight;
1121 SCIP_Real greedysolvalue;
1122 SCIP_Real greedyupperbound;
1123 SCIP_Bool eqweights;
1124 SCIP_Bool intprofits;
1136 for( j = nitems - 1; j >= 0; --j )
1143 if( solval !=
NULL )
1147 if( solitems !=
NULL )
1168 for( j = 0; j < nitems; ++j )
1173 if( weights[j] > capacity )
1175 if( solitems !=
NULL )
1176 nonsolitems[(*nnonsolitems)++] = items[j];
1179 else if( profits[j] <= 0.0 )
1181 if( solitems !=
NULL )
1182 nonsolitems[(*nnonsolitems)++] = items[j];
1185 else if( weights[j] == 0 )
1187 if( solitems !=
NULL )
1188 solitems[(*nsolitems)++] = items[j];
1190 if( solval !=
NULL )
1191 *solval += profits[j];
1196 myweights[nmyitems] = weights[j];
1197 myprofits[nmyitems] = profits[j];
1198 myitems[nmyitems] = items[j];
1201 if( myweights[nmyitems] < minweight )
1202 minweight = myweights[nmyitems];
1205 if( myweights[nmyitems] > maxweight )
1206 maxweight = myweights[nmyitems];
1208 weightsum += myweights[nmyitems];
1215 for( j = 0; j < nmyitems && intprofits; ++j )
1227 if( weightsum > 0 && weightsum <= capacity )
1231 for( j = nmyitems - 1; j >= 0; --j )
1233 if( solitems !=
NULL )
1234 solitems[(*nsolitems)++] = myitems[j];
1236 if( solval !=
NULL )
1237 *solval += myprofits[j];
1243 assert(0 < minweight && minweight <= capacity );
1244 assert(0 < maxweight && maxweight <= capacity);
1251 gcd = myweights[nmyitems - 1];
1252 for( j = nmyitems - 2; j >= 0 && gcd >= 2; --j )
1260 for( j = nmyitems - 1; j >= 0; --j )
1262 myweights[j] /= gcd;
1263 eqweights = eqweights && (myweights[j] == 1);
1271 assert(minweight <= capacity);
1274 if( minweight > capacity / 2 )
1278 SCIPdebugMsg(
scip,
"Only one item fits into knapsack, so take the best.\n");
1283 for( j = nmyitems - 2; j >= 0; --j )
1285 if( myprofits[j] > myprofits[p] )
1290 if( solitems !=
NULL )
1294 solitems[(*nsolitems)++] = myitems[p];
1295 for( j = nmyitems - 1; j >= 0; --j )
1298 nonsolitems[(*nnonsolitems)++] = myitems[j];
1302 if( solval !=
NULL )
1303 *solval += myprofits[p];
1311 SCIP_Real addval = 0.0;
1318 if( solitems !=
NULL || solval !=
NULL )
1323 assert((SCIP_Longint) nmyitems > capacity);
1327 for(
i = capacity - 1;
i >= 0; --
i )
1329 if( solitems !=
NULL )
1330 solitems[(*nsolitems)++] = myitems[
i];
1331 addval += myprofits[
i];
1334 if( solitems !=
NULL )
1337 for(
i = nmyitems - 1;
i >= capacity; --
i )
1338 nonsolitems[(*nnonsolitems)++] = myitems[
i];
1342 if( solval !=
NULL )
1359 for( j = 0; j < nmyitems; ++j )
1361 tempsort[j] = myprofits[j]/((
SCIP_Real) myweights[j]);
1362 realweights[j] = (
SCIP_Real)myweights[j];
1366 (SCIP_Real)capacity, nmyitems, &greedymedianpos);
1372 greedysolweight = 0;
1373 greedysolvalue = 0.0;
1376 for( j = 0; j < greedymedianpos; ++j )
1378 assert(myweights[j] <= capacity);
1381 greedysolweight += myweights[j];
1382 greedysolvalue += myprofits[j];
1385 assert(0 < greedysolweight && greedysolweight <= capacity);
1386 assert(greedysolvalue > 0.0);
1391 greedyupperbound = greedysolvalue + myprofits[j] * (
SCIP_Real) (capacity - greedysolweight)/((
SCIP_Real) myweights[j]);
1394 if( greedysolweight == capacity ||
SCIPisGE(
scip, greedysolvalue, greedyupperbound) )
1399 if( solitems !=
NULL )
1406 for( l = 0; l < j; ++l )
1407 solitems[(*nsolitems)++] = myitems[l];
1408 for ( ; l < nmyitems; ++l )
1409 nonsolitems[(*nnonsolitems)++] = myitems[l];
1412 if( solval !=
NULL )
1414 assert(greedysolvalue > 0.0);
1415 *solval += greedysolvalue;
1422 capacity -= (minweight - 1);
1425 if( capacity >= INT_MAX )
1432 assert(capacity < INT_MAX);
1434 intcap = (int)capacity;
1437 assert(
sizeof(
size_t) >=
sizeof(
int));
1442 if( intcap < 0 || (intcap > 0 && (((
size_t)nmyitems) > (SIZE_MAX / (
size_t)intcap /
sizeof(*optvalues)) || ((
size_t)nmyitems) * ((
size_t)intcap) *
sizeof(*optvalues) > ((
size_t)INT_MAX) )) )
1444 SCIPdebugMsg(
scip,
"Too much memory (%lu) would be consumed.\n", (
unsigned long) (((
size_t)nmyitems) * ((
size_t)intcap) *
sizeof(*optvalues)));
1472 assert(myweights[0] - minweight < INT_MAX);
1473 currminweight = (int) (myweights[0] - minweight);
1474 allcurrminweight[0] = currminweight;
1477 for( d = currminweight; d < intcap; ++d )
1478 optvalues[d] = myprofits[0];
1481 for( j = 1; j < nmyitems; ++j )
1486 intweight = (int)(myweights[j] - minweight);
1487 assert(0 <= intweight && intweight < intcap);
1490 for( d = currminweight; d < intweight && d < intcap; ++d )
1491 optvalues[
IDX(j,d)] = optvalues[
IDX(j-1,d)];
1494 for( d = intweight; d < intcap; ++d )
1497 if( d < currminweight )
1498 optvalues[
IDX(j,d)] = myprofits[j];
1501 SCIP_Real sumprofit;
1503 if( d - myweights[j] < currminweight )
1504 sumprofit = myprofits[j];
1506 sumprofit = optvalues[
IDX(j-1,(
int)(d-myweights[j]))] + myprofits[j];
1508 optvalues[
IDX(j,d)] =
MAX(sumprofit, optvalues[
IDX(j-1,d)]);
1513 if( intweight < currminweight )
1514 currminweight = intweight;
1516 allcurrminweight[j] = currminweight;
1520 if( solitems !=
NULL )
1528 for( j = nmyitems - 1; j > 0; --j )
1531 if( d < allcurrminweight[j] )
1534 assert((SCIP_Longint) d >= -minweight);
1539 if( d < allcurrminweight[j-1] || optvalues[
IDX(j,d)] > optvalues[
IDX(j-1,d)] )
1541 solitems[(*nsolitems)++] = myitems[j];
1544 assert(myweights[j] <= (INT_MAX + (SCIP_Longint) d));
1545 d = (int)(d - myweights[j]);
1549 nonsolitems[(*nnonsolitems)++] = myitems[j];
1553 if( d >= allcurrminweight[j] )
1556 solitems[(*nsolitems)++] = myitems[j];
1561 assert(d < allcurrminweight[j]);
1563 for( ; j >= 0; --j )
1564 nonsolitems[(*nnonsolitems)++] = myitems[j];
1567 assert(*nsolitems + *nnonsolitems == nitems);
1571 if( solval !=
NULL )
1572 *solval += optvalues[
IDX(nmyitems-1,intcap-1)];
1593 SCIP_Longint* weights,
1595 SCIP_Longint capacity,
1604 SCIP_Real* tempsort;
1605 SCIP_Longint solitemsweight;
1606 SCIP_Real* realweights;
1616 if( solitems !=
NULL )
1621 if( solval !=
NULL )
1627 for( j = nitems - 1; j >= 0; --j )
1629 tempsort[j] = profits[j]/((
SCIP_Real) weights[j]);
1638 for( j = 0; j < nitems && solitemsweight + weights[j] <= capacity; ++j )
1640 if( solitems !=
NULL )
1641 solitems[(*nsolitems)++] = items[j];
1643 if( solval !=
NULL )
1644 (*solval) += profits[j];
1645 solitemsweight += weights[j];
1647 if ( solitems !=
NULL )
1649 for( ; j < nitems; j++ )
1650 nonsolitems[(*nnonsolitems)++] = items[j];
1669 int nnontrivialgubconss;
1672 nnontrivialgubconss = 0;
1679 SCIP_Real gubsolval;
1697 if( solvals !=
NULL )
1699 gubsolval += solvals[currentvar];
1709 if( solvals !=
NULL )
1718 nnontrivialgubconss++;
1742 (*gubcons)->ngubvars = 0;
1857 assert(oldgubcons != newgubcons);
1874 gubset->
gubvarsidx[replacevar] = oldgubvaridx;
1887 SCIPdebugMsg(
scip,
"deleting empty GUB cons<%d> from current GUB set\n", oldgubcons);
1974 SCIP_Longint* weights,
1975 SCIP_Longint capacity
1992 (*gubset)->ngubconss =
nvars;
1993 (*gubset)->nvars =
nvars;
2005 (*gubset)->gubconssidx[
i] =
i;
2006 (*gubset)->gubvarsidx[
i] = 0;
2007 assert((*gubset)->gubconss[
i]->ngubvars == 1);
2010 if( weights[
i] > capacity )
2034 for(
i = (*gubset)->ngubconss-1;
i >= 0; --
i )
2062 SCIP_Bool var1negated;
2063 SCIP_Bool var2negated;
2071 for(
i = 0;
i < gubset->
nvars;
i++ )
2078 SCIPdebugMsg(
scip,
" var<%d> should be in GUB<%d> at position<%d>, but stored is var<%d> instead\n",
i,
2079 gubconsidx, gubvaridx, gubset->
gubconss[gubconsidx]->
gubvars[gubvaridx] );
2095 var1negated =
FALSE;
2102 var2negated =
FALSE;
2107 SCIPdebugMsg(
scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n",
i, j,
2110 SCIPdebugMsg(
scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n",
i, j,
2140 int*
const cliquepartition,
2147 SCIP_Bool* cliquevalues;
2148 SCIP_Bool* tmpvalues;
2152 int maxncliquevarscomp;
2180 tmpvalues[
i] =
TRUE;
2181 cliquepartition[
i] = -1;
2197 varseq[
nvars-1-nignorevars] =
i;
2203 varseq[nvarsused] =
i;
2219 if( cliquepartition[varseq[
i]] == -1 )
2224 cliquepartition[varseq[
i]] = *ncliques;
2225 cliquevars[0] = tmpvars[varseq[
i]];
2226 cliquevalues[0] = tmpvalues[varseq[
i]];
2235 for( j =
i + 1; j < nvarsused; ++j )
2238 if( cliquepartition[varseq[j]] == -1 &&
SCIPvarIsActive(tmpvars[varseq[j]]) )
2243 for( k = ncliquevars - 1; k >= 0; --k )
2246 cliquevalues[k],
TRUE) )
2253 cliquepartition[varseq[j]] = cliquepartition[varseq[
i]];
2254 cliquevars[ncliquevars] = tmpvars[varseq[j]];
2255 cliquevalues[ncliquevars] = tmpvalues[varseq[j]];
2265 assert(cliquepartition[varseq[
i]] >= 0 && cliquepartition[varseq[
i]] <
i + 1);
2268 if(
i *
nvars > maxncliquevarscomp )
2274 if( cliquepartition[varseq[
i]] == -1 )
2276 cliquepartition[varseq[
i]] = *ncliques;
2301 int* cliquepartition;
2304 int currentgubconsidx;
2327 for(
i = 0;
i < ncliques;
i++ )
2330 gubfirstvar[
i] = -1;
2335 assert(cliquepartition[
i] >= 0);
2337 cliqueidx = cliquepartition[
i];
2342 if( gubfirstvar[cliqueidx] == -1 )
2351 gubfirstvar[cliqueidx] =
i;
2356 assert(gubfirstvar[cliqueidx] >= 0 && gubfirstvar[cliqueidx] <
i);
2361 newgubconsidx = gubset->
gubconssidx[gubfirstvar[cliqueidx]];
2362 assert(newgubconsidx != currentgubconsidx);
2371 GUBsetPrint(
scip, gubset,
vars, solvals);
2395 SCIP_Longint* weights,
2396 SCIP_Longint capacity,
2402 SCIP_Longint* coverweight,
2404 SCIP_Bool modtransused,
2406 SCIP_Bool* fractional
2409 SCIP_Longint* transweights;
2410 SCIP_Real* transprofits;
2411 SCIP_Longint transcapacity;
2412 SCIP_Longint fixedonesweight;
2413 SCIP_Longint itemsweight;
2414 SCIP_Bool infeasible;
2462 fixedonesweight = 0;
2465 for( j = 0; j <
nvars; j++ )
2470 if( weights[j] > capacity )
2481 fixedones[nfixedones] = j;
2483 fixedonesweight += weights[j];
2488 fixedzeros[nfixedzeros] = j;
2497 itemsweight += weights[j];
2500 assert(nfixedones + nfixedzeros + nitems ==
nvars - (*ntightened));
2508 *fractional =
FALSE;
2529 for( j = 0; j < nitems; j++ )
2531 transweights[j] = weights[items[j]];
2532 transprofits[j] = 1.0 - solvals[items[j]];
2535 transcapacity = fixedonesweight + itemsweight - capacity - 1;
2540 if( transcapacity < 0 )
2564 for( j = 0; j < nitems; j++ )
2566 transprofits[j] *= weights[items[j]];
2578 noncovervars, covervars, nnoncovervars, ncovervars,
NULL) );
2582 for( j = 0; j < *ncovervars; j++ )
2584 (*coverweight) += weights[covervars[j]];
2588 for( j = 0; j < nfixedones; j++ )
2590 covervars[*ncovervars] = fixedones[j];
2592 (*coverweight) += weights[fixedones[j]];
2596 for( j = 0; j < nfixedzeros; j++ )
2598 noncovervars[*nnoncovervars] = fixedzeros[j];
2601 assert((*ncovervars) + (*nnoncovervars) ==
nvars - (*ntightened));
2602 assert((*coverweight) > capacity);
2623 SCIP_Longint* weights,
2624 SCIP_Longint capacity,
2627 SCIP_Longint coverweight,
2632 SCIP_Longint minweight;
2639 minweight = weights[covervars[minweightidx]];
2642 for(
i = 0;
i < j;
i++ )
2644 assert(weights[covervars[
i]] > minweight);
2645 if( weights[covervars[
i]] <= minweight )
2650 for(
i = 0;
i < j;
i++ )
2652 assert(coverweight - weights[covervars[
i]] <= capacity);
2653 if( coverweight - weights[covervars[
i]] > capacity )
2689 for( j = 0; j < ncovervars; j++ )
2696 varsC2[*nvarsC2] = covervars[j];
2703 varsC1[*nvarsC1] = covervars[j];
2707 assert((*nvarsC1) + (*nvarsC2) == ncovervars);
2716 SCIP_Longint* weights,
2723 SCIP_Real* sortkeysC2;
2726 assert(*nvarsC1 >= 0 && *nvarsC1 <= 1);
2733 for( j = 0; j < *nvarsC2; j++ )
2734 sortkeysC2[j] = (SCIP_Real) weights[varsC2[j]];
2738 assert(*nvarsC2 == 1 || weights[varsC2[(*nvarsC2)-1]] <= weights[varsC2[(*nvarsC2)-2]]);
2739 while( *nvarsC1 < 2 && *nvarsC2 > 0 )
2741 varsC1[*nvarsC1] = varsC2[(*nvarsC2)-1];
2756 SCIP_Longint* weights,
2763 SCIP_Real* sortkeysC2;
2766 assert(*nvarsC1 >= 0 && *nvarsC1 <= 1);
2773 for( j = 0; j < *nvarsC2; j++ )
2774 sortkeysC2[j] = (SCIP_Real) weights[varsC2[j]];
2778 assert(*nvarsC2 == 1 || weights[varsC2[(*nvarsC2)-1]] <= weights[varsC2[(*nvarsC2)-2]]);
2779 varsC1[*nvarsC1] = varsC2[(*nvarsC2)-1];
2809 assert(nnoncovervars >= 0);
2820 for( j = 0; j < nnoncovervars; j++ )
2825 varsR[*nvarsR] = noncovervars[j];
2832 varsF[*nvarsF] = noncovervars[j];
2836 assert((*nvarsF) + (*nvarsR) == nnoncovervars);
2846 SCIP_Longint* weights,
2857 SCIP_Real* sortkeysC2;
2858 SCIP_Real* sortkeysR;
2883 for( j = 0; j < nvarsF; j++ )
2885 sortkeypairsF[j] = &(sortkeypairsFstore[j]);
2886 sortkeypairsF[j]->key1 = solvals[varsF[j]];
2887 sortkeypairsF[j]->key2 = (
SCIP_Real) weights[varsF[j]];
2893 for( j = 0; j < nvarsC2; j++ )
2894 sortkeysC2[j] = (SCIP_Real) weights[varsC2[j]];
2899 for( j = 0; j < nvarsR; j++ )
2900 sortkeysR[j] = (SCIP_Real) weights[varsR[j]];
2933 SCIP_Longint* weights,
2950 int* ngubconscapexceed,
2956 SCIP_Real* sortkeysC1;
2957 SCIP_Real* sortkeysC2;
2958 SCIP_Real* sortkeysR;
2959 int* nC1varsingubcons;
2967 int nvarsprocessed = 0;
2973 SCIP_Bool gubconswithF;
3039 for( j = 0; j < nvarsC1; j++ )
3042 sortkeysC1[j] = (
SCIP_Real) weights[varsC1[j]];
3055 for( j = 0; j < nvarsF; j++ )
3067 for( j = 0; j < nvarsC2; j++ )
3070 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
3082 for( j = 0; j < nvarsR; j++ )
3085 sortkeysR[j] = (
SCIP_Real) weights[varsR[j]];
3118 sortkeypairsGFC1[
i] = &(sortkeypairsGFC1store[
i]);
3119 sortkeypairsGFC1[
i]->key1 = 0.0;
3120 sortkeypairsGFC1[
i]->key2 = 0.0;
3126 *ngubconscapexceed = 0;
3127 *maxgubvarssize = 0;
3140 for(
i = 0;
i < nvarsC1;
i++ )
3142 int nvarsC1capexceed;
3144 nvarsC1capexceed = 0;
3156 targetvar = gubset->
gubconss[gubconsidx]->
gubvars[nC1varsingubcons[gubconsidx]];
3158 nC1varsingubcons[gubconsidx]++;
3172 gubconswithF =
FALSE;
3190 gubconswithF =
TRUE;
3192 sortkeypairsGFC1[*ngubconsGFC1]->key1 += 1.0;
3194 if( solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3195 sortkeypairsGFC1[*ngubconsGFC1]->key2 = solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]];
3206 gubconsGC1[*ngubconsGC1] = gubconsidx;
3261 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3266 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3275 for(
i = 0;
i < nvarsC2;
i++ )
3291 gubconsGC2[*ngubconsGC2] = gubconsidx;
3307 for(
i = 0;
i < nvarsF;
i++ )
3340 sortkeypairsGFC1[*ngubconsGFC1]->key1 += 1.0;
3342 if( solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3343 sortkeypairsGFC1[*ngubconsGFC1]->key2 = solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]];
3348 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3359 for(
i = 0;
i < nvarsR;
i++ )
3385 gubconsGR[*ngubconsGR] = gubconsidx;
3392 assert(nvarsprocessed == nvarsC1 + nvarsC2 + nvarsF + nvarsR);
3395 (*ngubconscapexceed) =
ngubconss - (ngubconsGOC1 + (*ngubconsGC2) + (*ngubconsGFC1) + (*ngubconsGR));
3396 assert(*ngubconscapexceed >= 0);
3409 assert(check == *ngubconscapexceed);
3414 if( (*ngubconsGFC1) > 0 )
3416 SCIPsortDownPtrInt((
void**)sortkeypairsGFC1, gubconsGFC1, compSortkeypairs, (*ngubconsGFC1));
3434 SCIP_Longint** minweightsptr,
3436 int* minweightssize,
3445 assert(*minweightslen >= 0);
3447 assert(*minweightssize >= 0);
3449 if( newlen > *minweightssize )
3456 *minweightssize = newsize;
3458 assert(newlen <= *minweightssize);
3461 for( j = *minweightslen; j < newlen; ++j )
3463 *minweightslen = newlen;
3487 SCIP_Longint* weights,
3488 SCIP_Longint capacity,
3504 SCIP_Longint* minweights;
3505 SCIP_Real* sortkeys;
3506 SCIP_Longint fixedonesweight;
3522 assert(nvarsM1 >= 0 && nvarsM1 <=
nvars - ntightened);
3523 assert(nvarsM2 >= 0 && nvarsM2 <=
nvars - ntightened);
3524 assert(nvarsF >= 0 && nvarsF <=
nvars - ntightened);
3525 assert(nvarsR >= 0 && nvarsR <=
nvars - ntightened);
3526 assert(nvarsM1 + nvarsM2 + nvarsF + nvarsR ==
nvars - ntightened);
3533 minweightssize = nvarsM1 + 1;
3544 for( j = 0; j < nvarsM1; j++ )
3546 assert(liftcoefs[varsM1[j]] == 0);
3547 liftcoefs[varsM1[j]] = 1;
3548 sortkeys[j] = (
SCIP_Real) (weights[varsM1[j]]);
3549 (*cutact) += solvals[varsM1[j]];
3561 for(
w = 1;
w <= nvarsM1;
w++ )
3562 minweights[
w] = minweights[
w-1] + weights[varsM1[
w-1]];
3563 minweightslen = nvarsM1 + 1;
3566 fixedonesweight = 0;
3567 for( j = 0; j < nvarsM2; j++ )
3568 fixedonesweight += weights[varsM2[j]];
3569 assert(fixedonesweight >= 0);
3575 for( j = 0; j < nvarsF; j++ )
3577 SCIP_Longint weight;
3583 weight = weights[liftvar];
3591 if( capacity - fixedonesweight - weight < 0 )
3599 else if( minweights[*liftrhs] <= capacity - fixedonesweight - weight )
3612 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
3614 right = (*liftrhs) + 1;
3615 while( left < right - 1 )
3617 middle = (left + right) / 2;
3618 assert(0 <= middle && middle < minweightslen);
3619 if( minweights[middle] <= capacity - fixedonesweight - weight )
3624 assert(left == right - 1);
3625 assert(0 <= left && left < minweightslen);
3626 assert(minweights[left] <= capacity - fixedonesweight - weight );
3627 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight - weight);
3635 liftcoef = (*liftrhs) - z;
3636 liftcoefs[liftvar] = liftcoef;
3637 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
3644 (*cutact) += liftcoef * solvals[liftvar];
3658 for(
w = minweightslen - 1;
w >= 0;
w-- )
3663 min =
MIN(minweights[
w], weight);
3664 minweights[
w] = min;
3669 min =
MIN(minweights[
w], minweights[
w - liftcoef] + weight);
3670 minweights[
w] = min;
3674 assert(minweights[0] == 0);
3677 for( j = 0; j < nvarsM2; j++ )
3679 SCIP_Longint weight;
3687 liftvar = varsM2[j];
3688 weight = weights[liftvar];
3697 right = minweightslen;
3698 while( left < right - 1 )
3700 middle = (left + right) / 2;
3701 assert(0 <= middle && middle < minweightslen);
3702 if( minweights[middle] <= capacity - fixedonesweight + weight )
3707 assert(left == right - 1);
3708 assert(0 <= left && left < minweightslen);
3709 assert(minweights[left] <= capacity - fixedonesweight + weight );
3710 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight + weight);
3717 liftcoef = z - (*liftrhs);
3718 liftcoefs[liftvar] = liftcoef;
3722 fixedonesweight -= weight;
3725 (*liftrhs) += liftcoef;
3726 assert(*liftrhs >= alpha0);
3733 (*cutact) += liftcoef * solvals[liftvar];
3747 for(
w = minweightslen - 1;
w >= 0;
w-- )
3752 min =
MIN(minweights[
w], weight);
3753 minweights[
w] = min;
3758 min =
MIN(minweights[
w], minweights[
w - liftcoef] + weight);
3759 minweights[
w] = min;
3763 assert(fixedonesweight == 0);
3764 assert(*liftrhs >= alpha0);
3767 for( j = 0; j < nvarsR; j++ )
3769 SCIP_Longint weight;
3775 weight = weights[liftvar];
3779 assert(capacity - weight >= 0);
3780 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - weight);
3785 if( minweights[*liftrhs] <= capacity - weight )
3798 right = (*liftrhs) + 1;
3799 while( left < right - 1)
3801 middle = (left + right) / 2;
3802 assert(0 <= middle && middle < minweightslen);
3803 if( minweights[middle] <= capacity - weight )
3808 assert(left == right - 1);
3809 assert(0 <= left && left < minweightslen);
3810 assert(minweights[left] <= capacity - weight );
3811 assert(left == minweightslen - 1 || minweights[left+1] > capacity - weight);
3819 liftcoef = (*liftrhs) - z;
3820 liftcoefs[liftvar] = liftcoef;
3821 assert(liftcoef >= 0 && liftcoef <= *liftrhs);
3828 (*cutact) += liftcoef * solvals[liftvar];
3834 for(
w = *liftrhs;
w >= 0;
w-- )
3839 min =
MIN(minweights[
w], weight);
3840 minweights[
w] = min;
3845 min =
MIN(minweights[
w], minweights[
w - liftcoef] + weight);
3846 minweights[
w] = min;
3873 return (val1 + val2);
3880 SCIP_Longint* minweights,
3881 SCIP_Longint* finished,
3882 SCIP_Longint* unfinished,
3895 assert(unfinished[w2] == 0);
3896 for( w1 = 0; w1 < minweightslen; w1++ )
3897 minweights[w1] = finished[w1];
3900 for( w2 = 1; w2 < minweightslen; w2++ )
3905 for( w1 = 0; w1 < minweightslen - w2; w1++ )
3910 if( temp <= minweights[w1+w2] )
3911 minweights[w1+w2] = temp;
3935 int ngubconscapexceed,
3936 SCIP_Longint* weights,
3937 SCIP_Longint capacity,
3954 SCIP_Longint* minweights;
3955 SCIP_Longint* finished;
3956 SCIP_Longint* unfinished;
3960 SCIP_Longint fixedonesweight;
3961 SCIP_Longint weight;
3962 SCIP_Longint weightdiff1;
3963 SCIP_Longint weightdiff2;
4007 assert(ngubconsGC1 >= 0 && ngubconsGC1 <=
ngubconss - ngubconscapexceed);
4008 assert(ngubconsGC2 >= 0 && ngubconsGC2 <=
ngubconss - ngubconscapexceed);
4009 assert(ngubconsGFC1 >= 0 && ngubconsGFC1 <=
ngubconss - ngubconscapexceed);
4010 assert(ngubconsGR >= 0 && ngubconsGR <=
ngubconss - ngubconscapexceed);
4016 minweightssize = ngubconsGC1+1;
4035 for( j = 0; j < ngubconsGC1; j++ )
4039 gubconsGOC1[ngubconsGOC1] = gubconsGC1[j];
4045 gubconsGNC1[ngubconsGNC1] = gubconsGC1[j];
4056 (*cutact) += solvals[
varidx];
4060 assert(ngubconsGOC1 + ngubconsGFC1 + ngubconsGC2 + ngubconsGR ==
ngubconss - ngubconscapexceed);
4061 assert(ngubconsGOC1 + ngubconsGNC1 == ngubconsGC1);
4082 assert(ngubconsGOC1 <= ngubconsGC1);
4084 for(
w = 1;
w <= ngubconsGOC1;
w++ )
4086 liftgubconsidx = gubconsGOC1[
w-1];
4097 finished[
w] = finished[
w-1] + min;
4110 for(
w = ngubconsGOC1+1;
w <= ngubconsGC1;
w++ )
4118 assert(ngubconsGNC1 <= ngubconsGC1);
4120 for(
w = 1;
w <= ngubconsGNC1;
w++ )
4122 liftgubconsidx = gubconsGNC1[
w-1];
4133 unfinished[
w] = unfinished[
w-1] + min;
4146 for(
w = ngubconsGNC1 + 1;
w <= ngubconsGC1;
w++ )
4154 assert(ngubconsGOC1 + ngubconsGNC1 == ngubconsGC1);
4156 for(
w = 1;
w <= ngubconsGC1;
w++ )
4158 liftgubconsidx = gubconsGC1[
w-1];
4170 minweights[
w] = minweights[
w-1] + min;
4183 minweightslen = ngubconsGC1 + 1;
4186 fixedonesweight = 0;
4187 for( j = 0; j < ngubconsGC2; j++ )
4195 fixedonesweight += weights[
varidx];
4197 assert(fixedonesweight >= 0);
4203 for( j = 0; j < ngubconsGFC1; j++ )
4205 liftgubconsidx = gubconsGFC1[j];
4216 assert(ngubconsGNC1 > 0);
4229 weight = weights[liftgubvars[0]];
4231 weightdiff2 = unfinished[ngubconsGNC1] - weight;
4233 for(
w = ngubconsGNC1-1;
w >= 1;
w-- )
4235 weightdiff1 = weightdiff2;
4236 weightdiff2 = unfinished[
w] - weight;
4238 if( unfinished[
w] < weightdiff1 )
4239 unfinished[
w] = weightdiff1;
4247 assert(minweights[0] == 0);
4268 weight = weights[liftvar];
4271 assert(capacity - weight >= 0);
4276 liftgubvars[nliftgubvars] = liftvar;
4282 if( capacity - fixedonesweight - weight < 0 )
4290 else if( minweights[*liftrhs] <= capacity - fixedonesweight - weight )
4299 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
4301 right = (*liftrhs) + 1;
4302 while( left < right - 1 )
4304 middle = (left + right) / 2;
4305 assert(0 <= middle && middle < minweightslen);
4306 if( minweights[middle] <= capacity - fixedonesweight - weight )
4311 assert(left == right - 1);
4312 assert(0 <= left && left < minweightslen);
4313 assert(minweights[left] <= capacity - fixedonesweight - weight);
4314 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight - weight);
4322 liftcoef = (*liftrhs) - z;
4323 liftcoefs[liftvar] = liftcoef;
4324 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
4327 (*cutact) += liftcoef * solvals[liftvar];
4330 sumliftcoef += liftcoefs[liftvar];
4336 assert(nliftgubvars > nliftgubC1);
4342 if( sumliftcoef == 0 )
4346 weight = weights[liftgubvars[0]];
4351 for(
w = minweightslen-1;
w >= 1;
w-- )
4353 SCIP_Longint tmpval;
4356 finished[
w] =
MIN(finished[
w], tmpval);
4359 minweights[
w] =
MIN(minweights[
w], tmpval);
4374 tmplen = minweightslen;
4375 tmpsize = minweightssize;
4377 tmplen = minweightslen;
4378 tmpsize = minweightssize;
4392 for(
w = minweightslen-1;
w >= 0;
w-- )
4394 SCIP_Longint minminweight;
4395 SCIP_Longint minfinished;
4397 for( k = 0; k < nliftgubvars; k++ )
4399 liftcoef = liftcoefs[liftgubvars[k]];
4400 weight = weights[liftgubvars[k]];
4404 minfinished =
MIN(finished[
w], weight);
4405 minminweight =
MIN(minweights[
w], weight);
4407 finished[
w] = minfinished;
4408 minweights[
w] = minminweight;
4412 SCIP_Longint tmpval;
4417 minfinished =
MIN(finished[
w], tmpval);
4420 minminweight =
MIN(minweights[
w], tmpval);
4422 finished[
w] = minfinished;
4423 minweights[
w] = minminweight;
4427 assert(minweights[0] == 0);
4429 assert(ngubconsGNC1 == 0);
4436 for( j = 0; j < ngubconsGC2; j++ )
4438 liftgubconsidx = gubconsGC2[j];
4446 weight = weights[liftvar];
4456 right = minweightslen;
4457 while( left < right - 1 )
4459 middle = (left + right) / 2;
4460 assert(0 <= middle && middle < minweightslen);
4461 if( minweights[middle] <= capacity - fixedonesweight + weight )
4466 assert(left == right - 1);
4467 assert(0 <= left && left < minweightslen);
4468 assert(minweights[left] <= capacity - fixedonesweight + weight);
4469 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - fixedonesweight + weight);
4476 liftcoef = z - (*liftrhs);
4477 liftcoefs[liftvar] = liftcoef;
4481 fixedonesweight -= weight;
4484 (*liftrhs) += liftcoef;
4485 assert(*liftrhs >= alpha0);
4492 (*cutact) += liftcoef * solvals[liftvar];
4506 for(
w = minweightslen - 1;
w >= 0;
w-- )
4510 min =
MIN(minweights[
w], weight);
4511 minweights[
w] = min;
4515 SCIP_Longint tmpval;
4520 min =
MIN(minweights[
w], tmpval);
4521 minweights[
w] = min;
4525 assert(fixedonesweight == 0);
4526 assert(*liftrhs >= alpha0);
4529 for( j = 0; j < ngubconsGR; j++ )
4531 liftgubconsidx = gubconsGR[j];
4543 weight = weights[liftvar];
4546 assert(capacity - weight >= 0);
4547 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - weight);
4552 liftgubvars[nliftgubvars] = liftvar;
4558 if( minweights[*liftrhs] <= capacity - weight )
4567 right = (*liftrhs) + 1;
4568 while( left < right - 1 )
4570 middle = (left + right) / 2;
4571 assert(0 <= middle && middle < minweightslen);
4572 if( minweights[middle] <= capacity - weight )
4577 assert(left == right - 1);
4578 assert(0 <= left && left < minweightslen);
4579 assert(minweights[left] <= capacity - weight);
4580 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - weight);
4587 liftcoef = (*liftrhs) - z;
4588 liftcoefs[liftvar] = liftcoef;
4589 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
4592 (*cutact) += liftcoef * solvals[liftvar];
4595 sumliftcoef += liftcoefs[liftvar];
4600 assert(nliftgubvars >= 1);
4603 if( sumliftcoef == 0 )
4609 for(
w = *liftrhs;
w >= 0;
w-- )
4611 for( k = 0; k < nliftgubvars; k++ )
4613 liftcoef = liftcoefs[liftgubvars[k]];
4614 weight = weights[liftgubvars[k]];
4618 min =
MIN(minweights[
w], weight);
4619 minweights[
w] = min;
4623 SCIP_Longint tmpval;
4628 min =
MIN(minweights[
w], tmpval);
4629 minweights[
w] = min;
4633 assert(minweights[0] == 0);
4671 SCIP_Longint* weights,
4672 SCIP_Longint capacity,
4678 SCIP_Longint coverweight,
4679 SCIP_Real* liftcoefs,
4683 SCIP_Longint* maxweightsums;
4684 SCIP_Longint* intervalends;
4686 SCIP_Real* sortkeys;
4687 SCIP_Longint lambda;
4700 assert(nnoncovervars >= 0 && nnoncovervars <=
nvars - ntightened);
4701 assert(ncovervars + nnoncovervars ==
nvars - ntightened);
4718 for( j = 0; j < ncovervars; j++ )
4720 assert(liftcoefs[covervars[j]] == 0.0);
4721 liftcoefs[covervars[j]] = 1.0;
4722 sortkeys[j] = (
SCIP_Real) weights[covervars[j]];
4723 (*cutact) += solvals[covervars[j]];
4728 lambda = coverweight - capacity;
4732 maxweightsums[0] = 0;
4733 for(
h = 1;
h <= ncovervars;
h++ )
4735 maxweightsums[
h] = maxweightsums[
h-1] + weights[covervars[
h-1]];
4736 intervalends[
h-1] = maxweightsums[
h] - lambda;
4737 rhos[
h-1] =
MAX(0, weights[covervars[
h-1]] - weights[covervars[0]] + lambda);
4741 for( j = 0; j < nnoncovervars; j++ )
4742 sortkeys[j] = (SCIP_Real) (weights[noncovervars[j]]);
4747 for( j = 0; j < nnoncovervars; j++ )
4750 SCIP_Longint weight;
4753 liftvar = noncovervars[j];
4754 weight = weights[liftvar];
4756 while( intervalends[
h] < weight )
4763 if( weight <= intervalends[
h-1] + rhos[
h] )
4767 tmp1 = (
SCIP_Real) (intervalends[
h-1] + rhos[
h] - weight);
4769 liftcoef =
h - ( tmp1 / tmp2 );
4776 assert(liftcoefs[liftvar] == 0.0);
4777 liftcoefs[liftvar] = liftcoef;
4780 (*cutact) += liftcoef * solvals[liftvar];
4804 SCIP_Longint* weights,
4805 SCIP_Longint capacity,
4808 int* nonmincovervars,
4810 int nnonmincovervars,
4845 assert(nvarsC1 + nvarsC2 == nmincovervars);
4846 assert(nmincovervars > 0);
4850 if( nvarsC1 < 2 && nvarsC2 > 0)
4855 assert(nvarsC2 == 0 || nvarsC1 >= 1);
4862 assert(nvarsF + nvarsR == nnonmincovervars);
4863 assert(nvarsC1 + nvarsC2 + nvarsF + nvarsR ==
nvars - ntightened);
4866 if( gubset ==
NULL )
4885 varsF, varsR, nvarsC1, nvarsC2, nvarsF, nvarsR, nvarsC1 - 1, liftcoefs, &cutact, &liftrhs) );
4922 nvarsC2, nvarsF, nvarsR, gubconsGC1, gubconsGC2, gubconsGFC1, gubconsGR, &ngubconsGC1, &ngubconsGC2,
4923 &ngubconsGFC1, &ngubconsGR, &nconstightened, &maxgubvarssize) );
4939 gubconsGC2, gubconsGFC1, gubconsGR, ngubconsGC1, ngubconsGC2, ngubconsGFC1, ngubconsGR,
4940 MIN(nvarsC1 - 1, ngubconsGC1), liftcoefs, &cutact, &liftrhs, maxgubvarssize) );
4965 else if ( sepa !=
NULL )
4978 assert(nvarsC1 + nvarsC2 + nvarsF + nvarsR ==
nvars - ntightened);
4979 for( j = 0; j < nvarsC1; j++ )
4983 for( j = 0; j < nvarsC2; j++ )
4985 if( liftcoefs[varsC2[j]] > 0 )
4990 for( j = 0; j < nvarsF; j++ )
4992 if( liftcoefs[varsF[j]] > 0 )
4997 for( j = 0; j < nvarsR; j++ )
4999 if( liftcoefs[varsR[j]] > 0 )
5038 SCIP_Longint* weights,
5039 SCIP_Longint capacity,
5042 int* nonfeassetvars,
5044 int nnonfeassetvars,
5079 assert(nvarsT1 + nvarsT2 == nfeassetvars);
5082 if( nvarsT1 == 0 && nvarsT2 > 0)
5087 assert(nvarsT2 == 0 || nvarsT1 > 0);
5094 assert(nvarsF + nvarsR == nnonfeassetvars);
5095 assert(nvarsT1 + nvarsT2 + nvarsF + nvarsR ==
nvars - ntightened);
5114 SCIP_CALL(
sequentialUpAndDownLifting(
scip,
vars,
nvars, ntightened, weights, capacity, solvals, varsT1, varsT2, varsF, varsR,
5115 nvarsT1, nvarsT2, nvarsF, nvarsR, nvarsT1, liftcoefs, &cutact, &liftrhs) );
5132 else if ( sepa !=
NULL )
5145 assert(nvarsT1 + nvarsT2 + nvarsF + nvarsR ==
nvars - ntightened);
5146 for( j = 0; j < nvarsT1; j++ )
5150 for( j = 0; j < nvarsT2; j++ )
5152 if( liftcoefs[varsT2[j]] > 0 )
5157 for( j = 0; j < nvarsF; j++ )
5159 if( liftcoefs[varsF[j]] > 0 )
5164 for( j = 0; j < nvarsR; j++ )
5166 if( liftcoefs[varsR[j]] > 0 )
5205 SCIP_Longint* weights,
5206 SCIP_Longint capacity,
5209 int* nonmincovervars,
5211 int nnonmincovervars,
5212 SCIP_Longint mincoverweight,
5218 SCIP_Real* realliftcoefs;
5240 nonmincovervars, nmincovervars, nnonmincovervars, mincoverweight, realliftcoefs, &cutact) );
5241 liftrhs = nmincovervars - 1;
5259 else if ( sepa !=
NULL )
5272 assert(nmincovervars + nnonmincovervars ==
nvars - ntightened);
5273 for( j = 0; j < nmincovervars; j++ )
5277 for( j = 0; j < nnonmincovervars; j++ )
5314 SCIP_Longint* weights,
5315 SCIP_Longint capacity,
5321 SCIP_Longint* coverweight,
5322 SCIP_Bool modtransused
5327 SCIP_Longint minweight;
5339 assert(*nnoncovervars >= 0);
5341 assert(*coverweight > 0);
5342 assert(*coverweight > capacity);
5346 nsortkeypairs = *ncovervars;
5355 assert(*ncovervars == nsortkeypairs);
5358 for( j = 0; j < *ncovervars; j++ )
5361 sortkeypairssorted[j] = sortkeypairs[j];
5363 sortkeypairs[j]->key1 = solvals[covervars[j]];
5364 sortkeypairs[j]->key2 = (
SCIP_Real) weights[covervars[j]];
5369 for( j = 0; j < *ncovervars; j++ )
5372 sortkeypairssorted[j] = sortkeypairs[j];
5374 sortkeypairs[j]->key1 = (solvals[covervars[j]] - 1.0) / ((SCIP_Real) weights[covervars[j]]);
5375 sortkeypairs[j]->key2 = (
SCIP_Real) (-weights[covervars[j]]);
5378 SCIPsortPtrInt((
void**)sortkeypairssorted, covervars, compSortkeypairs, *ncovervars);
5382 minweight = weights[covervars[minweightidx]];
5383 for( j = 1; j < *ncovervars; j++ )
5385 if( weights[covervars[j]] <= minweight )
5388 minweight = weights[covervars[minweightidx]];
5391 assert(minweightidx >= 0 && minweightidx < *ncovervars);
5392 assert(minweight > 0 && minweight <= *coverweight);
5396 while( j < *ncovervars && ((*coverweight) - minweight > capacity) )
5398 assert(minweightidx >= j);
5402 if( (*coverweight) - weights[covervars[j]] <= capacity )
5409 noncovervars[*nnoncovervars] = covervars[j];
5413 (*coverweight) -= weights[covervars[j]];
5414 for( k = j; k < (*ncovervars) - 1; k++ )
5415 covervars[k] = covervars[k+1];
5419 if( j == minweightidx )
5422 minweight = weights[covervars[minweightidx]];
5423 for( k = 1; k < *ncovervars; k++ )
5425 if( weights[covervars[k]] <= minweight )
5428 minweight = weights[covervars[minweightidx]];
5431 assert(minweight > 0 && minweight <= *coverweight);
5432 assert(minweightidx >= 0 && minweightidx < *ncovervars);
5436 assert(minweightidx > j);
5441 assert((*coverweight) > capacity);
5442 assert((*coverweight) - minweight <= capacity);
5445 for( j = nsortkeypairs-1; j >= 0; j-- )
5468 SCIP_Longint* weights,
5469 SCIP_Longint capacity,
5475 SCIP_Longint* coverweight,
5476 SCIP_Bool modtransused,
5482 SCIP_Real* sortkeys;
5492 assert(*nnoncovervars >= 0);
5494 assert(*coverweight > 0);
5495 assert(*coverweight > capacity);
5496 assert(*ncovervars + *nnoncovervars ==
nvars - ntightened);
5511 for( j = 0; j < *ncovervars; j++ )
5513 sortkeys[j] = solvals[covervars[j]];
5519 for( j = 0; j < *ncovervars; j++ )
5521 sortkeys[j] = (solvals[covervars[j]] - 1.0) / ((SCIP_Real) weights[covervars[j]]);
5529 while( *ncovervars >= 2 )
5532 noncovervars[*nnoncovervars] = covervars[0];
5536 (*coverweight) -= weights[covervars[0]];
5537 for( k = 0; k < (*ncovervars) - 1; k++ )
5538 covervars[k] = covervars[k+1];
5541 assert(*ncovervars + *nnoncovervars ==
nvars - ntightened);
5542 if( (*coverweight) <= capacity )
5545 covervars, noncovervars, *ncovervars, *nnoncovervars,
sol,
cutoff, ncuts) );
5566 SCIP_Longint* weights,
5567 SCIP_Longint capacity,
5577 SCIP_Bool coverfound;
5578 SCIP_Bool fractional;
5579 SCIP_Bool modtransused;
5580 SCIP_Longint coverweight;
5617 SCIPdebugMsg(
scip,
"separate cuts for knapsack constraint originated by cons <%s>:\n",
5648 modtransused =
TRUE;
5650 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5652 assert(!coverfound || !fractional || ncovervars + nnoncovervars ==
nvars - ntightened);
5657 SCIPdebugMsg(
scip,
" LMCI1-GUB terminated by no variable with fractional LP value.\n");
5672 &nnoncovervars, &coverweight, modtransused) );
5679 solvals, covervars, noncovervars, ncovervars, nnoncovervars,
sol, gubset,
cutoff, ncuts) );
5687 solvals, covervars, noncovervars, ncovervars, nnoncovervars,
sol,
NULL,
cutoff, ncuts) );
5707 modtransused =
TRUE;
5709 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5710 assert(!coverfound || !fractional || ncovervars + nnoncovervars ==
nvars - ntightened);
5723 &nnoncovervars, &coverweight, modtransused) );
5727 solvals, covervars, noncovervars, ncovervars, nnoncovervars,
sol,
NULL,
cutoff, ncuts) );
5734 solvals, covervars, noncovervars, ncovervars, nnoncovervars, coverweight,
sol,
cutoff, ncuts) );
5749 modtransused =
FALSE;
5751 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5753 assert(!coverfound || ncovervars + nnoncovervars ==
nvars - ntightened);
5762 SCIP_CALL(
getFeasibleSet(
scip, cons, sepa,
vars,
nvars, ntightened, weights, capacity, solvals, covervars, noncovervars,
5763 &ncovervars, &nnoncovervars, &coverweight, modtransused,
sol,
cutoff, ncuts) );
5783 SCIP_Real* knapvals,
5794 SCIP_Longint* consvals;
5795 SCIP_Longint minact;
5796 SCIP_Longint maxact;
5797 SCIP_Real intscalar;
5807 SCIP_Bool noknapsackconshdlr;
5835 if( conshdlr ==
NULL )
5837 noknapsackconshdlr =
TRUE;
5845 noknapsackconshdlr =
FALSE;
5848 usegubs = conshdlrdata->usegubs;
5855 if( conshdlrdata->reals1size == 0 )
5858 conshdlrdata->reals1size = 1;
5859 conshdlrdata->reals1[0] = 0.0;
5862 assert(conshdlrdata->reals1size > 0);
5868 if( conshdlrdata->reals1size <
nbinvars )
5870 int oldsize = conshdlrdata->reals1size;
5872 conshdlrdata->reals1size =
nbinvars;
5874 BMSclearMemoryArray(&(conshdlrdata->reals1[oldsize]), conshdlrdata->reals1size - oldsize);
5876 binvals = conshdlrdata->reals1;
5880 for( tmp =
nbinvars - 1; tmp >= 0; --tmp )
5882 assert(binvals[tmp] == 0);
5900 for(
i = 0;
i < nknapvars;
i++ )
5917 SCIPdebugMsg(
scip,
"Solution value %.15g <%s> outside domain [0.0, 1.0]\n",
5923 if( !noknapsackconshdlr )
5932 else if( valscale * knapvals[
i] > 0.0 )
5937 SCIP_Real bestlbsol;
5951 for( j = 0; j < nvlb; j++ )
5962 SCIPdebugMsg(
scip,
"variable bound <%s>[%g,%g] >= %g<%s>[%g,%g] + %g implies local cutoff\n",
5982 if( bestlbtype == -1 )
5984 rhs -= valscale * knapvals[
i] * bestlbsol;
5985 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with lower bound %.15g (rhs=%.15g)\n",
5991 rhs -= valscale * knapvals[
i] * dvlb[bestlbtype];
5997 if( !noknapsackconshdlr )
6004 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable lower bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6015 SCIP_Real bestubsol;
6020 assert(valscale * knapvals[
i] < 0.0);
6031 for( j = 0; j < nvub; j++ )
6042 SCIPdebugMsg(
scip,
"variable bound <%s>[%g,%g] <= %g<%s>[%g,%g] + %g implies local cutoff\n",
6062 if( bestubtype == -1 )
6064 rhs -= valscale * knapvals[
i] * bestubsol;
6065 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with upper bound %.15g (rhs=%.15g)\n",
6071 rhs -= valscale * knapvals[
i] * dvub[bestubtype];
6077 if( !noknapsackconshdlr )
6084 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable upper bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6113 rhs = rhs * intscalar;
6148 consvals[nconsvars] = val;
6149 consvars[nconsvars] =
var;
6155 SCIP_Longint capacity;
6167 for(
i = 0;
i < nconsvars; ++
i )
6174 capacity, rhs, act, minact, maxact);
6178 if( minact > capacity )
6180 SCIPdebugMsg(
scip,
"minactivity of knapsack relaxation implies local cutoff\n");
6185 if( maxact > capacity )
6188 SCIP_CALL(
SCIPseparateKnapsackCuts(
scip, cons, sepa, consvars, nconsvars, consvals, capacity,
sol, usegubs,
cutoff, ncuts) );
6194 if( noknapsackconshdlr)
6201 for( --tmp; tmp >= 0; --tmp)
6204 binvals[tmpindices[tmp]] = 0;
6250 consdata->capacity,
sol, usegubs,
cutoff, ncuts) );
6273 if( consdata->row !=
NULL )
6282 consdata->capacity -= weight;
6293 consdata->vars[consdata->nvars] =
var;
6294 consdata->weights[consdata->nvars] = weight;
6312 conshdlrdata->eventhdlr, consdata->eventdata[consdata->nvars-1],
6313 &consdata->eventdata[consdata->nvars-1]->filterpos) );
6316 consdata->existmultaggr =
TRUE;
6320 consdata->presolvedtiming = 0;
6321 consdata->cliquesadded =
FALSE;
6327 consdata->sorted =
FALSE;
6328 consdata->cliquepartitioned =
FALSE;
6329 consdata->negcliquepartitioned =
FALSE;
6330 consdata->merged =
FALSE;
6351 var = consdata->vars[pos];
6356 if( consdata->row !=
NULL )
6372 conshdlrdata->eventhdlr, consdata->eventdata[pos], consdata->eventdata[pos]->filterpos) );
6376 consdata->presolvedtiming = 0;
6377 consdata->sorted = (consdata->sorted && pos == consdata->nvars - 1);
6384 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
6385 consdata->weights[pos] = consdata->weights[consdata->nvars-1];
6386 if( consdata->eventdata !=
NULL )
6387 consdata->eventdata[pos] = consdata->eventdata[consdata->nvars-1];
6393 if( consdata->cliquepartitioned )
6398 if( consdata->cliquepartition[consdata->nvars - 1] != consdata->nvars - 1 )
6402 oldcliqenum = consdata->cliquepartition[pos];
6403 consdata->cliquepartition[pos] = consdata->cliquepartition[consdata->nvars-1];
6406 if( consdata->cliquepartition[pos] > pos )
6407 consdata->cliquepartitioned =
FALSE;
6411 int cliquenumbefore;
6415 if( oldcliqenum > consdata->cliquepartition[pos] )
6417 for(
i = 0;
i < consdata->nvars; ++
i )
6418 if( oldcliqenum == consdata->cliquepartition[
i] )
6420 else if( oldcliqenum < consdata->cliquepartition[
i] )
6422 consdata->cliquepartitioned =
FALSE;
6428 if(
i == consdata->nvars )
6429 --(consdata->ncliques);
6433 else if( oldcliqenum < consdata->cliquepartition[pos] )
6435 cliquenumbefore = consdata->cliquepartition[pos] - 1;
6436 for(
i = pos - 1;
i >= 0 &&
i >= cliquenumbefore && consdata->cliquepartition[
i] < cliquenumbefore; --
i );
6438 if(
i < cliquenumbefore )
6439 consdata->cliquepartitioned =
FALSE;
6442 else if( pos == consdata->nvars - 1)
6444 cliquenumbefore = consdata->cliquepartition[pos];
6445 for(
i = pos - 1;
i >= 0 &&
i >= cliquenumbefore && consdata->cliquepartition[
i] < cliquenumbefore; --
i );
6447 if(
i < cliquenumbefore )
6448 --(consdata->ncliques);
6454 --(consdata->ncliques);
6457 if( consdata->negcliquepartitioned )
6459 assert(consdata->negcliquepartition !=
NULL);
6462 if( consdata->negcliquepartition[consdata->nvars-1] != consdata->nvars - 1 )
6466 oldcliqenum = consdata->negcliquepartition[pos];
6467 consdata->negcliquepartition[pos] = consdata->negcliquepartition[consdata->nvars-1];
6470 if( consdata->negcliquepartition[pos] > pos )
6471 consdata->negcliquepartitioned =
FALSE;
6475 int cliquenumbefore;
6479 if( oldcliqenum > consdata->negcliquepartition[pos] )
6481 for(
i = 0;
i < consdata->nvars; ++
i )
6482 if( oldcliqenum == consdata->negcliquepartition[
i] )
6484 else if( oldcliqenum < consdata->negcliquepartition[
i] )
6486 consdata->negcliquepartitioned =
FALSE;
6492 if(
i == consdata->nvars )
6493 --(consdata->nnegcliques);
6497 else if( oldcliqenum < consdata->negcliquepartition[pos] )
6499 cliquenumbefore = consdata->negcliquepartition[pos] - 1;
6500 for(
i = pos - 1;
i >= 0 &&
i >= cliquenumbefore && consdata->negcliquepartition[
i] < cliquenumbefore; --
i );
6502 if(
i < cliquenumbefore )
6503 consdata->negcliquepartitioned =
FALSE;
6506 else if( pos == consdata->nvars - 1)
6508 cliquenumbefore = consdata->negcliquepartition[pos];
6509 for(
i = pos - 1;
i >= 0 &&
i >= cliquenumbefore && consdata->negcliquepartition[
i] < cliquenumbefore; --
i );
6511 if(
i < cliquenumbefore )
6512 --(consdata->nnegcliques);
6518 --(consdata->nnegcliques);
6521 --(consdata->nvars);
6539 for( v = consdata->nvars-1; v >= 0; --v )
6541 if( consdata->weights[v] == 0 )
6570 for(
i = 0;
i < nconss;
i++ )
6575 if( consdata->varsdeleted )
6578 for( v = consdata->nvars - 1; v >= 0; --v )
6585 consdata->varsdeleted =
FALSE;
6613 if( consdata->merged )
6616 if( consdata->nvars <= 1 )
6618 consdata->merged =
TRUE;
6622 assert(consdata->vars !=
NULL || consdata->nvars == 0);
6626 consdata->cliquepartition, consdata->negcliquepartition, SCIPvarCompActiveAndNegated, consdata->nvars);
6629 consdata->sorted =
FALSE;
6631 v = consdata->nvars - 1;
6644 var1 = consdata->vars[v];
6654 var2 = consdata->vars[prev];
6667 if( negated1 == negated2 )
6670 consdataChgWeight(consdata, prev, consdata->weights[v] + consdata->weights[prev]);
6676 else if( consdata->weights[v] == consdata->weights[prev] )
6679 consdata->capacity -= consdata->weights[v];
6685 else if( consdata->weights[v] < consdata->weights[prev] )
6687 consdata->capacity -= consdata->weights[v];
6688 consdataChgWeight(consdata, prev, consdata->weights[prev] - consdata->weights[v]);
6689 assert(consdata->weights[prev] > 0);
6694 consdata->capacity -= consdata->weights[prev];
6696 assert(consdata->weights[v] > 0);
6699 if( consdata->nvars != v )
6703 if( prev == 0 || (var1 != consdata->vars[prev - 1] && var1 !=
SCIPvarGetNegatedVar(consdata->vars[prev - 1])) )
6707 consdata->cliquesadded =
FALSE;
6714 consdata->cliquesadded =
FALSE;
6720 consdata->merged =
TRUE;
6723 if( consdata->onesweightsum > consdata->capacity )
6752 SCIP_Bool infeasible;
6753 SCIP_Bool tightened;
6754 SCIP_Bool applicable;
6772 nvars = consdata->nvars;
6773 vars = consdata->vars;
6785 for( v = 0; v <
nvars; ++v )
6828 items, solitems, nonsolitems, &nsolitems, &nnonsolitems, &solval, &success) );
6835 for( v = 0; v < nsolitems; ++v )
6840 SCIPdebugMsg(
scip,
"variable <%s> only locked up in knapsack constraints: dual presolve <%s>[%.15g,%.15g] >= 1.0\n",
6848 for( v = 0; v < nnonsolitems; ++v )
6853 SCIPdebugMsg(
scip,
"variable <%s> has no down locks: dual presolve <%s>[%.15g,%.15g] <= 0.0\n",
6891 SCIP_Bool applicable;
6904 nvars = consdata->nvars;
6919 vars = consdata->vars;
6926 for( v = 0; v <
nvars && applicable; ++v )
6948 weight = (
SCIP_Real)consdata->weights[v];
6955 scale = weight / -
objval;
6978 SCIP_Real cutoffbound;
6984 cutoffbound = (consdata->capacity - offset) / scale;
6986 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
6994 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
7014 SCIP_Real lowerbound;
7020 lowerbound = (consdata->capacity - offset) / scale;
7022 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a lower bound <%g>\n",
7039 SCIP_Longint* weights,
7040 int* cliquestartposs,
7041 SCIP_Bool usenegatedclique
7046 SCIP_Longint* origweights;
7047 int* cliquepartition;
7051 SCIP_Longint** weightpointers;
7064 origweights = consdata->weights;
7065 origvars = consdata->vars;
7066 norigvars = consdata->nvars;
7069 assert(origweights !=
NULL || norigvars == 0);
7071 if( norigvars == 0 )
7074 if( usenegatedclique )
7076 assert(consdata->negcliquepartitioned);
7078 cliquepartition = consdata->negcliquepartition;
7079 ncliques = consdata->nnegcliques;
7083 assert(consdata->cliquepartitioned);
7085 cliquepartition = consdata->cliquepartition;
7086 ncliques = consdata->ncliques;
7097 for( v = norigvars - 1; v >= 0; --v )
7099 assert(0 <= cliquepartition[v] && cliquepartition[v] < ncliques);
7100 ++(cliquecount[cliquepartition[v]]);
7114 for(
c = 0;
c < ncliques; ++
c )
7124 cliquestartposs[
c] = nextpos;
7125 weightpointers[
c] = (SCIP_Longint*) (weights + nextpos);
7127 nextpos += cliquecount[
c];
7130 assert(nextpos == norigvars);
7131 cliquestartposs[
c] = nextpos;
7134 for( v = 0; v < norigvars; ++v )
7136 *(varpointers[cliquepartition[v]]) = origvars[v];
7137 ++(varpointers[cliquepartition[v]]);
7138 *(weightpointers[cliquepartition[v]]) = origweights[v];
7139 ++(weightpointers[cliquepartition[v]]);
7142 for( v = 0; v < norigvars; ++v )
7175 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
7184 if ( consdata->onesweightsum > consdata->capacity )
7195 consdata->existmultaggr =
FALSE;
7198 while( v < consdata->
nvars )
7202 var = consdata->vars[v];
7208 consdata->capacity -= consdata->weights[v];
7210 consdata->cliquesadded =
FALSE;
7222 SCIP_Longint weight;
7225 weight = consdata->weights[v];
7268 SCIP_Real* aggrscalars;
7269 SCIP_Real aggrconst;
7278 assert((aggrvars !=
NULL && aggrscalars !=
NULL) || naggrvars == 0);
7282 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-integral value for weight*aggrconst = %g\n", weight*aggrconst);
7290 for(
i = naggrvars - 1;
i >= 0; --
i )
7297 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-binary %svariable <%s> with bounds [%g,%g]\n",
7303 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-integral value for weight*aggrscalars = %g\n", weight*aggrscalars[
i]);
7328 if( consdata->capacity < 0 )
7338 else if( repvar !=
var )
7350 assert(consdata->onesweightsum == 0);
7375 SCIP_Bool* redundant,
7377 SCIP_Bool usenegatedclique
7381 SCIP_Bool infeasible;
7382 SCIP_Bool tightened;
7383 SCIP_Longint* secondmaxweights;
7384 SCIP_Longint minweightsum;
7385 SCIP_Longint residualcapacity;
7392 SCIP_Longint* myweights;
7393 int* cliquestartposs;
7395 SCIP_Longint localminweightsum;
7421 for(
i = 0;
i < consdata->nvars && consdata->merged; ++
i )
7427 usenegatedclique = usenegatedclique && consdata->merged;
7432 cliquestartposs =
NULL;
7433 secondmaxweights =
NULL;
7435 nvars = consdata->nvars;
7441 localminweightsum = 0;
7450 if( usenegatedclique &&
nvars > 0 )
7458 nnegcliques = consdata->nnegcliques;
7461 if( nnegcliques ==
nvars )
7464 usenegatedclique =
FALSE;
7480 for(
c = 0;
c < nnegcliques; ++
c )
7482 cliqueendposs[
c] = cliquestartposs[
c+1] - 1;
7483 assert(cliqueendposs[
c] - cliquestartposs[
c] >= 0);
7497 if( nnegcliques -
c ==
nvars -
i )
7499 minweightsum += localminweightsum;
7500 localminweightsum = 0;
7508 if( cliquestartposs[
c] ==
i )
7512 minweightsum += localminweightsum;
7513 localminweightsum = 0;
7532 assert(myweights[
i] <= myweights[cliquestartposs[
c - 1]]);
7539 cliquestartposs[
c - 1] =
i;
7545 if( secondmaxweights[
c - 1] == 0 )
7546 secondmaxweights[
c - 1] = myweights[
i];
7548 localminweightsum += myweights[
i];
7555 for( v = cliquestartposs[
c - 1]; v < cliquestartposs[
c]; ++v )
7592 localminweightsum = 0;
7594 i = cliqueendposs[
c - 1];
7603 minweightsum += localminweightsum;
7609 if( !(*
cutoff) && consdata->capacity >= minweightsum + consdata->onesweightsum )
7611 SCIP_Longint maxcliqueweight = -1LL;
7614 for(
c = 0;
c < nnegcliques; ++
c )
7617 SCIP_Bool maxvarfixed;
7618 int endvarposclique;
7619 int startvarposclique;
7622 assert(nnegcliques == consdata->nnegcliques);
7627 endvarposclique = cliqueendposs[
c];
7628 startvarposclique = cliquestartposs[
c];
7630 maxvar = myvars[startvarposclique];
7636 maxcliqueweight = myweights[startvarposclique];
7637 maxvarfixed =
FALSE;
7642 if( consdata->onesweightsum + minweightsum + (maxcliqueweight - secondmaxweights[
c]) > consdata->capacity )
7645 SCIP_Longint oldonesweightsum = consdata->onesweightsum;
7647 assert(maxcliqueweight >= secondmaxweights[
c]);
7653 assert(consdata->onesweightsum == oldonesweightsum);
7662 else if( nnegcliques -
c ==
nvars - startvarposclique )
7672 else if( consdata->onesweightsum + minweightsum + (maxcliqueweight - consdata->weights[
nvars - 1]) <= consdata->capacity )
7676 for(
i = endvarposclique;
i > startvarposclique; --
i )
7685 assert(maxcliqueweight >= myweights[
i]);
7686 assert(
i == endvarposclique || myweights[
i] >= myweights[
i+1]);
7694 if( maxvarfixed || consdata->onesweightsum + minweightsum - myweights[
i] + maxcliqueweight > consdata->capacity )
7697 SCIP_Longint oldonesweightsum = consdata->onesweightsum;
7701 assert(consdata->onesweightsum == oldonesweightsum + myweights[
i]);
7710 minweightsum -= myweights[
i];
7711 assert(minweightsum >= 0);
7719 for( ;
i > startvarposclique; --
i )
7722 SCIP_Bool exceedscapacity = consdata->onesweightsum + minweightsum - myweights[
i] + maxcliqueweight > consdata->capacity;
7724 assert(
i == endvarposclique || myweights[
i] >= myweights[
i+1]);
7725 assert(varisfixed || !exceedscapacity);
7737 assert(consdata->negcliquepartitioned || minweightsum == 0);
7741 assert(usenegatedclique || minweightsum == 0);
7743 if( consdata->capacity < minweightsum + consdata->onesweightsum )
7746 consdata->onesweightsum, consdata->capacity);
7755 SCIP_Longint weight;
7761 for(
i = 0;
i <
nvars && weight <= consdata->capacity;
i++ )
7766 weight += consdata->weights[
i];
7777 if( !usenegatedclique )
7779 assert(consdata->sorted);
7780 residualcapacity = consdata->capacity - consdata->onesweightsum;
7783 for(
i = 0;
i <
nvars && consdata->weights[
i] > residualcapacity; ++
i )
7792 assert(consdata->onesweightsum + consdata->weights[
i] > consdata->capacity);
7807 SCIP_Longint unfixedweightsum = consdata->onesweightsum;
7814 unfixedweightsum += consdata->weights[
i];
7817 if( unfixedweightsum > consdata->capacity )
7823 SCIPconsGetName(cons), consdata->weightsum, unfixedweightsum, consdata->capacity);
7852 assert(consdata->nvars > 1);
7855 if( consdata->nvars == 2 )
7910 SCIP_Longint frontsum,
7921 SCIP_Longint* weights;
7922 SCIP_Longint capacity;
7935 assert(0 < frontsum && frontsum < consdata->weightsum);
7936 assert(0 < splitpos && splitpos < consdata->
nvars);
7941 vars = consdata->vars;
7942 weights = consdata->weights;
7943 nvars = consdata->nvars;
7944 capacity = consdata->capacity;
7951 assert(weights[
w] <= weights[
w-1]);
7955 if( consdata->nvars - 1 == splitpos )
7958 assert(frontsum + weights[splitpos] > capacity);
7961 if( consdata->weightsum - weights[splitpos] <= capacity )
7969 for(
w =
nvars - 1;
w > splitpos; --
w )
7971 consdata->capacity -= weights[
w];
7977 *nchgcoefs += (
nvars - splitpos);
7981 for( ;
w >= 0 && gcd > 1; --
w )
7989 for(
w = splitpos;
w >= 0; --
w )
7993 (*nchgcoefs) +=
nvars;
7995 consdata->capacity /= gcd;
8003 for(
w = consdata->nvars - 1;
w > 0; --
w )
8004 assert(weights[
w] <= weights[
w - 1]);
8011 else if( conshdlrdata->disaggregation && frontsum + weights[splitpos + 1] <= capacity )
8017 len =
nvars - (splitpos + 1);
8027 SCIP_Longint maxactduetoclq;
8034 for(
w = 0;
w < len; ++
w )
8036 assert(clqpart[
w] >= 0 && clqpart[
w] <=
w);
8037 if( clqpart[
w] == cliquenum )
8039 maxactduetoclq += weights[
w + splitpos + 1];
8047 if( frontsum + maxactduetoclq <= capacity )
8053 assert(maxactduetoclq < weights[splitpos]);
8060 for(
c = 0;
c < nclq; ++
c )
8063 for(
w = 0;
w < len; ++
w )
8065 if( clqpart[
w] ==
c )
8067 clqvars[nclqvars] =
vars[
w + splitpos + 1];
8093 for(
w =
nvars - 1;
w > splitpos; --
w )
8098 consdata->capacity -= maxactduetoclq;
8099 assert(frontsum <= consdata->capacity);
8105 weights = consdata->weights;
8109 for( ;
w >= 0 && gcd > 1; --
w )
8117 for(
w = splitpos;
w >= 0; --
w )
8121 (*nchgcoefs) +=
nvars;
8123 consdata->capacity /= gcd;
8134 for(
w = consdata->nvars - 1;
w > 0; --
w )
8135 assert(weights[
w] <= weights[
w - 1]);
8170 SCIP_Longint* weights;
8171 SCIP_Longint capacity;
8187 assert(consdata->nvars >= 2);
8188 assert(consdata->weightsum > consdata->capacity);
8190 noldchgcoefs = *nchgcoefs;
8191 vars = consdata->vars;
8192 weights = consdata->weights;
8193 nvars = consdata->nvars;
8194 capacity = consdata->capacity;
8198 for( v = 0; v <
nvars && sum + weights[v] <= capacity; ++v )
8204 if( v ==
nvars - 1 )
8216 assert(consdata->nvars > 1);
8219 if( v == consdata->nvars - 1 )
8229 if( *nchgcoefs > noldchgcoefs )
8233 assert(weights == consdata->weights);
8235 assert(capacity == consdata->capacity);
8243 if( consdata->cliquepartition[v] < v )
8245 SCIP_Longint sumfront;
8246 SCIP_Longint maxactduetoclqfront;
8251 maxactduetoclqfront = 0;
8253 clqpart = consdata->cliquepartition;
8259 assert(clqpart[
w] >= 0 && clqpart[
w] <=
w);
8260 if( clqpart[
w] == cliquenum )
8262 if( maxactduetoclqfront + weights[
w] <= capacity )
8264 maxactduetoclqfront += weights[
w];
8270 sumfront += weights[
w];
8277 if( conshdlrdata->disaggregation &&
w ==
nvars )
8284 assert(maxactduetoclqfront <= capacity);
8288 ncliques = consdata->ncliques;
8293 for(
c = 0;
c < ncliques; ++
c )
8298 if( clqpart[
w] ==
c )
8300 clqvars[nclqvars] =
vars[
w];
8363 assert(consdata->onesweightsum == 0);
8364 assert(consdata->weightsum > consdata->capacity);
8365 assert(consdata->nvars >= 1);
8370 gcd = consdata->weights[consdata->nvars-1];
8371 for(
i = consdata->nvars-2;
i >= 0 && gcd >= 2; --
i )
8383 for(
i = 0;
i < consdata->nvars; ++
i )
8387 consdata->capacity /= gcd;
8388 (*nchgcoefs) += consdata->nvars;
8393 for(
i = consdata->nvars - 1;
i > 0; --
i )
8394 assert(consdata->weights[
i] <= consdata->weights[
i - 1]);
8396 consdata->sorted =
TRUE;
8430 SCIP_Longint* weights;
8431 SCIP_Longint dualcapacity;
8432 SCIP_Longint reductionsum;
8433 SCIP_Longint capacity;
8434 SCIP_Longint exceedsum;
8452 oldnchgsides = *nchgsides;
8457 assert(consdata->weightsum > consdata->capacity);
8458 assert(consdata->nvars >= 2);
8459 assert(consdata->sorted);
8462 assert(consdata->merged);
8464 nvars = consdata->nvars;
8465 weights = consdata->weights;
8466 capacity = consdata->capacity;
8468 oldnchgcoefs = *nchgcoefs;
8471 if( weights[
nvars - 1] + weights[
nvars - 2] > capacity )
8498 if( consdata->weightsum - weights[
nvars - 1] <= consdata->capacity )
8508 if( consdata->weightsum - capacity > weights[0] + weights[1] )
8529 while( v <
nvars && weights[v] + weights[
nvars - 1] > capacity )
8537 while( v <
nvars && exceedsum <= capacity )
8539 exceedsum += weights[v];
8544 if( exceedsum > capacity )
8555 for( v = 0; v < vbig; ++v )
8557 if( weights[v] > newweight )
8565 for( ; v <
nvars; ++v )
8567 if( weights[v] > 1 )
8574 consdata->capacity = newweight;
8580 for( v =
nvars - 1; v > 0; --v )
8581 assert(weights[v] <= weights[v-1]);
8591 SCIP_Longint exceedsumback = 0;
8592 int nexceed = v - vbig;
8598 exceedsumback += weights[
w];
8605 if( exceedsumback > capacity )
8607 SCIP_Longint newweight = nexceed - 1;
8610 assert(exceedsumback - weights[
nvars - 1] <= capacity);
8613 for( v = 0; v < vbig; ++v )
8615 if( weights[v] > newweight )
8623 for( ; v <
nvars; ++v )
8625 if( weights[v] > 1 )
8632 consdata->capacity = newweight;
8638 for( v =
nvars - 1; v > 0; --v )
8639 assert(weights[v] <= weights[v-1]);
8662 if( weights[vbig - 1] > (SCIP_Longint)
nvars - vbig || weights[vbig] > 1 )
8666 SCIP_Longint resweightsum = consdata->weightsum;
8668 for( v = 0; v < vbig; ++v )
8669 resweightsum -= weights[v];
8671 assert(exceedsum == resweightsum);
8676 for( v = 0; v < vbig; ++v )
8678 if( weights[v] > newweight )
8686 for( ; v <
nvars; ++v )
8688 if( weights[v] > 1 )
8695 consdata->capacity = newweight;
8701 for( v =
nvars - 1; v > 0; --v )
8702 assert(weights[v] <= weights[v-1]);
8710 dualcapacity = consdata->weightsum - capacity;
8720 while( weights[v] > dualcapacity )
8722 reductionsum += (weights[v] - dualcapacity);
8730 while( v <
nvars && weights[v] == dualcapacity )
8738 if( v >=
nvars - 1 )
8741 if( v ==
nvars - 1 )
8754 if( weights[
nvars - 1] + weights[
nvars - 2] >= dualcapacity )
8768 if( v > 0 && weights[
nvars - 2] > 1 )
8773 for(
w = 0;
w < v; ++
w )
8775 if( weights[
w] > 2 )
8783 assert(weights[v - 1] == 2);
8791 if( weights[
w] > 1 )
8799 (*nchgcoefs) += ncoefchg;
8802 consdata->capacity = (-2 + v * 2 +
nvars - v);
8803 assert(consdata->capacity > 0);
8804 assert(weights[0] <= consdata->capacity);
8805 assert(consdata->weightsum > consdata->capacity);
8816 SCIP_Longint minweight = weights[
nvars - 1];
8817 SCIP_Longint newweight = dualcapacity - minweight;
8818 SCIP_Longint restsumweights = 0;
8819 SCIP_Longint sumcoef;
8820 SCIP_Bool sumcoefcase =
FALSE;
8833 while( weights[v] > newweight )
8835 reductionsum += (weights[v] - newweight);
8840 (*nchgcoefs) += (v - startv);
8843 while( weights[v] == newweight )
8849 restsumweights += weights[
w];
8852 restsumweights = consdata->weightsum;
8854 if( restsumweights < dualcapacity )
8872 for( ;
w >= 0; --
w )
8873 assert(weights[
w] == dualcapacity);
8891 if( weights[v] > 1 || (weights[startv] > (SCIP_Longint)
nvars - v) || (startv > 0 && weights[0] == (SCIP_Longint)
nvars - v + 1) )
8893 SCIP_Longint newcap;
8898 if( weights[
w] > 1 )
8910 for( ;
w >= startv; --
w )
8912 if( weights[
w] > newweight )
8918 assert(weights[
w] == newweight);
8924 for( ;
w >= 0; --
w )
8926 if( weights[
w] > newweight )
8932 assert(weights[
w] == newweight);
8936 newcap = ((
SCIP_Longint)startv - 1) * newweight + ((SCIP_Longint)v - startv) * (newweight - 1) + ((SCIP_Longint)
nvars - v);
8937 if( consdata->capacity > newcap )
8939 consdata->capacity = newcap;
8943 assert(consdata->capacity == newcap);
8945 assert(weights[v] == 1 && (weights[startv] == (SCIP_Longint)
nvars - v) && (startv == 0 || weights[0] == (SCIP_Longint)
nvars - v + 1));
8948 assert(consdata->weightsum - consdata->capacity == (SCIP_Longint)
nvars - v + 1);
8955 assert(weights[
w] <= weights[
w - 1]);
8962 while( end >= 0 && weights[end] == weights[end + 1] )
8974 if( 2 * weights[end] > dualcapacity )
8980 restsumweights += weights[
w];
8982 if( restsumweights * 2 <= dualcapacity )
8985 while( v < end && restsumweights + weights[v] >= dualcapacity )
8992 if( (dualcapacity & 1) == 0 )
8994 newweight = dualcapacity / 2;
8997 for( ; v <= end; ++v )
8999 if( weights[v] > newweight )
9001 reductionsum += (weights[v] - newweight);
9016 for(
w = 0;
w < v; ++
w )
9021 newweight = dualcapacity;
9023 for( ; v <= end; ++v )
9025 reductionsum += (2 * weights[v] - newweight);
9034 (*nchgcoefs) +=
nvars;
9037 consdata->capacity *= 2;
9052 for( k = 0; k < 4; ++k )
9058 sumcoef = weights[
nvars - 1] + weights[
nvars - 2];
9062 sumcoef = weights[
nvars - 1] + weights[
nvars - 3];
9069 sumcoef = weights[
nvars - 1] + weights[
nvars - 4];
9073 sumcoefcase =
FALSE;
9074 sumcoef = weights[
nvars - 2] + weights[
nvars - 3];
9093 minweight = weights[end];
9094 while( minweight <= sumcoef )
9096 newweight = dualcapacity - minweight;
9102 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9104 reductionsum += (weights[v] - newweight);
9109 (*nchgcoefs) += (v - startv);
9112 while( weights[v] + minweight == dualcapacity )
9120 while( end >= 0 && weights[end] == weights[end + 1] )
9126 minweight = weights[end];
9133 if( sumcoef < minweight )
9135 minweight = sumcoef;
9136 newweight = dualcapacity - minweight;
9141 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9143 reductionsum += (weights[v] - newweight);
9148 (*nchgcoefs) += (v - startv);
9151 while( weights[v] + minweight == dualcapacity )
9162 if( 2 * weights[end] > dualcapacity )
9168 restsumweights += weights[
w];
9170 if( restsumweights * 2 <= dualcapacity )
9173 while( v < end && restsumweights + weights[v] >= dualcapacity )
9180 if( (dualcapacity & 1) == 0 )
9182 newweight = dualcapacity / 2;
9185 for( ; v <= end; ++v )
9187 if( weights[v] > newweight )
9189 reductionsum += (weights[v] - newweight);
9204 for(
w = 0;
w < v; ++
w )
9209 newweight = dualcapacity;
9211 for( ; v <= end; ++v )
9213 reductionsum += (2 * weights[v] - newweight);
9222 (*nchgcoefs) +=
nvars;
9225 consdata->capacity *= 2;
9234 if( 2 * sumcoef > dualcapacity )
9242 if( reductionsum > 0 )
9246 consdata->capacity -= reductionsum;
9249 assert(consdata->weightsum - dualcapacity == consdata->capacity);
9251 assert(weights[0] <= consdata->capacity);
9258 assert(weights[
w] <= weights[
w - 1]);
9261 if( oldnchgcoefs < *nchgcoefs )
9270 assert(oldnchgcoefs == *nchgcoefs);
9271 assert(oldnchgsides == *nchgsides);
9290 SCIP_Longint* weights;
9291 SCIP_Longint capacity;
9292 SCIP_Bool infeasible;
9306 nvars = consdata->nvars;
9311 assert(consdata->capacity >= 0);
9322 vars = consdata->vars;
9323 weights = consdata->weights;
9324 capacity = consdata->capacity;
9328 while( v <
nvars && weights[v] > capacity )
9351 for( --v; v >= 0; --v )
9360 assert(weights == consdata->weights);
9362 assert(consdata->sorted);
9363 assert(weights[0] <= capacity);
9410 SCIP_Longint* weights;
9411 SCIP_Longint restweight;
9412 SCIP_Longint newweight;
9413 SCIP_Longint weight;
9414 SCIP_Longint oldgcd;
9442 assert(consdata->merged);
9446 assert(consdata->capacity >= 0);
9468 weights = consdata->weights;
9469 nvars = consdata->nvars;
9473 for( v =
nvars - 1; v > 0; --v )
9474 assert(weights[v] <= weights[v-1]);
9478 gcd = weights[
nvars - 1];
9479 for( v =
nvars - 2; v >= 0 && gcd > 1; --v )
9487 for( v =
nvars - 1; v >= 0; --v )
9491 (*nchgcoefs) +=
nvars;
9493 consdata->capacity /= gcd;
9502 for( v =
nvars - 1; v > 0; --v )
9503 assert(weights[v] <= weights[v-1]);
9512 vars = consdata->vars;
9513 weights = consdata->weights;
9514 nvars = consdata->nvars;
9517 if( weights[
nvars - 1] == 1 && weights[
nvars - 2] == 1 )
9524 while( weights[v] == consdata->capacity )
9531 if( v ==
nvars - 1 )
9543 for( v =
nvars - 1; v >= offsetv; --v )
9545 weight = weights[v];
9573 if( v ==
nvars - 2 )
9579 if( candpos == v + 1 && candpos2 == v + 2 )
9606 assert(((candpos >= offsetv) || (candpos == -1 && offsetv > 0)) && candpos <
nvars);
9609 rest = consdata->capacity % gcd;
9619 consdata->capacity -= rest;
9623 for( v = 0; v < offsetv; ++v )
9628 *nchgcoefs += offsetv;
9633 restweight = weights[candpos] % gcd;
9635 assert(restweight < gcd);
9638 if( restweight > rest )
9639 newweight = weights[candpos] - restweight + gcd;
9641 newweight = weights[candpos] - restweight;
9645 SCIPdebugMsg(
scip,
"gcd = %" SCIP_LONGINT_FORMAT ", rest = %" SCIP_LONGINT_FORMAT ", restweight = %" SCIP_LONGINT_FORMAT "; possible new weight of variable <%s> %" SCIP_LONGINT_FORMAT ", possible new capacity %" SCIP_LONGINT_FORMAT ", offset of coefficients as big as capacity %d\n", gcd, rest, restweight,
SCIPvarGetName(
vars[candpos]), newweight, consdata->capacity - rest, offsetv);
9650 if( newweight == 0 && offsetv > 0 )
9656 consdata->capacity -= rest;
9660 for( v = 0; v < offsetv; ++v )
9665 *nchgcoefs += offsetv;
9668 if( newweight == 0 )
9684 assert(consdata->weights == weights);
9688 for( v =
nvars - 1; v >= 0; --v )
9692 (*nchgcoefs) +=
nvars;
9694 consdata->capacity /= gcd;
9699 SCIPdebugMsg(
scip,
"we did %d coefficient changes and %d side changes on constraint %s when applying one round of the gcd algorithm\n", *nchgcoefs - oldnchgcoefs, *nchgsides - oldnchgsides,
SCIPconsGetName(cons));
9701 while(
nvars >= 2 );
9714 SCIP_Longint** zeroweightsums,
9722 SCIP_Longint knapsackweight,
9723 SCIP_Bool* memlimitreached
9739 assert(*nzeroitems <= *zeroitemssize);
9743 nzeros = *nzeroitems;
9746 if( nzeros == *zeroitemssize )
9753 SCIPdebugMsg(
scip,
"memory limit of %d bytes reached in knapsack preprocessing - abort collecting zero items\n",
9755 *memlimitreached =
TRUE;
9758 *zeroitemssize *= 2;
9763 assert(nzeros < *zeroitemssize);
9765 if( *memlimitreached )
9766 *memlimitreached =
FALSE;
9769 (*zeroitems)[nzeros] = knapsackidx;
9770 (*nextidxs)[nzeros] = firstidxs[value][probindex];
9771 if( firstidxs[value][probindex] == 0 )
9773 liftcands[value][nliftcands[value]] = probindex;
9774 ++nliftcands[value];
9776 firstidxs[value][probindex] = nzeros;
9778 zeroweightsums[value][probindex] += knapsackweight;
9783#define MAX_CLIQUELENGTH 50
9807 SCIP_Longint* zeroweightsums[2];
9812 SCIP_Bool* zeroiteminserted[2];
9813 SCIP_Bool memlimitreached;
9815 SCIP_Bool* cliqueused;
9816 SCIP_Bool* itemremoved;
9817 SCIP_Longint maxcliqueweightsum;
9819 SCIP_Longint* addweights;
9820 SCIP_Longint addweightsum;
9828 SCIP_Bool* tmpboolindices;
9830 SCIP_Bool* tmpboolindices2;
9832 SCIP_Bool* tmpboolindices3;
9845 assert(consdata->weightsum > consdata->capacity);
9846 assert(consdata->nvars > 0);
9847 assert(consdata->merged);
9849 nvars = consdata->nvars;
9877 assert(conshdlrdata->ints1size > 0);
9878 assert(conshdlrdata->ints2size > 0);
9879 assert(conshdlrdata->longints1size > 0);
9880 assert(conshdlrdata->longints2size > 0);
9886 if( conshdlrdata->ints1size <
nbinvars )
9888 int oldsize = conshdlrdata->ints1size;
9890 conshdlrdata->ints1size =
nbinvars;
9894 if( conshdlrdata->ints2size <
nbinvars )
9896 int oldsize = conshdlrdata->ints2size;
9898 conshdlrdata->ints2size =
nbinvars;
9902 if( conshdlrdata->longints1size <
nbinvars )
9904 int oldsize = conshdlrdata->longints1size;
9906 conshdlrdata->longints1size =
nbinvars;
9908 BMSclearMemoryArray(&(conshdlrdata->longints1[oldsize]), conshdlrdata->longints1size - oldsize);
9910 if( conshdlrdata->longints2size <
nbinvars )
9912 int oldsize = conshdlrdata->longints2size;
9914 conshdlrdata->longints2size =
nbinvars;
9916 BMSclearMemoryArray(&(conshdlrdata->longints2[oldsize]), conshdlrdata->longints2size - oldsize);
9919 firstidxs[0] = conshdlrdata->ints1;
9920 firstidxs[1] = conshdlrdata->ints2;
9921 zeroweightsums[0] = conshdlrdata->longints1;
9922 zeroweightsums[1] = conshdlrdata->longints2;
9926 for( tmp =
nbinvars - 1; tmp >= 0; --tmp )
9928 assert(firstidxs[0][tmp] == 0);
9929 assert(firstidxs[1][tmp] == 0);
9930 assert(zeroweightsums[0][tmp] == 0);
9931 assert(zeroweightsums[1][tmp] == 0);
9944 assert(conshdlrdata->bools1size > 0);
9945 assert(conshdlrdata->bools2size > 0);
9951 if( conshdlrdata->bools1size <
nbinvars )
9953 int oldsize = conshdlrdata->bools1size;
9955 conshdlrdata->bools1size =
nbinvars;
9957 BMSclearMemoryArray(&(conshdlrdata->bools1[oldsize]), conshdlrdata->bools1size - oldsize);
9959 if( conshdlrdata->bools2size <
nbinvars )
9961 int oldsize = conshdlrdata->bools2size;
9963 conshdlrdata->bools2size =
nbinvars;
9965 BMSclearMemoryArray(&(conshdlrdata->bools2[oldsize]), conshdlrdata->bools2size - oldsize);
9968 zeroiteminserted[0] = conshdlrdata->bools1;
9969 zeroiteminserted[1] = conshdlrdata->bools2;
9973 for( tmp =
nbinvars - 1; tmp >= 0; --tmp )
9975 assert(zeroiteminserted[0][tmp] == 0);
9976 assert(zeroiteminserted[1][tmp] == 0);
9990 memlimitreached =
FALSE;
9991 for(
i = 0;
i < consdata->nvars && !memlimitreached; ++
i )
9995 SCIP_Longint weight;
10004 var = consdata->vars[
i];
10005 weight = consdata->weights[
i];
10012 zeroweightsums[!value][varprobindex] += weight;
10013 tmpboolindices3[tmp3] = !value;
10014 tmpindices3[tmp3] = varprobindex;
10020 SCIP_Bool implvalue;
10026 implvalue = !value;
10029 assert( !zeroiteminserted[implvalue][probindex] );
10031 if( firstidxs[implvalue][probindex] == 0 )
10033 tmpboolindices2[tmp2] = implvalue;
10034 tmpindices2[tmp2] = probindex;
10038 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue,
i, weight,
10039 &memlimitreached) );
10040 zeroiteminserted[implvalue][probindex] =
TRUE;
10041 tmpboolindices[tmp] = implvalue;
10042 tmpindices[tmp] = probindex;
10049 for( j = 0; j < ncliques && !memlimitreached; ++j )
10052 SCIP_Bool* cliquevalues;
10065 for( k = ncliquevars - 1; k >= 0; --k )
10067 SCIP_Bool implvalue;
10070 if(
var == cliquevars[k] )
10074 if( probindex == -1 )
10078 implvalue = cliquevalues[k];
10081 if( !zeroiteminserted[implvalue][probindex] )
10083 if( firstidxs[implvalue][probindex] == 0 )
10085 tmpboolindices2[tmp2] = implvalue;
10086 tmpindices2[tmp2] = probindex;
10091 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue,
i, weight,
10092 &memlimitreached) );
10093 zeroiteminserted[implvalue][probindex] =
TRUE;
10094 tmpboolindices[tmp] = implvalue;
10095 tmpindices[tmp] = probindex;
10098 if( memlimitreached )
10104 for( --tmp; tmp >= 0; --tmp)
10105 zeroiteminserted[tmpboolindices[tmp]][tmpindices[tmp]] =
FALSE;
10110 assert(consdata->sorted);
10113 assert(conshdlrdata->bools3size > 0);
10119 if( conshdlrdata->bools3size < consdata->nvars )
10121 int oldsize = conshdlrdata->bools3size;
10123 conshdlrdata->bools3size = consdata->nvars;;
10125 BMSclearMemoryArray(&(conshdlrdata->bools3[oldsize]), conshdlrdata->bools3size - oldsize);
10128 cliqueused = conshdlrdata->bools3;
10132 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10133 assert(cliqueused[tmp] == 0);
10136 maxcliqueweightsum = 0;
10140 for(
i = 0;
i < consdata->nvars; ++
i )
10142 cliquenum = consdata->cliquepartition[
i];
10143 assert(0 <= cliquenum && cliquenum < consdata->
nvars);
10145 if( !cliqueused[cliquenum] )
10147 maxcliqueweightsum += consdata->weights[
i];
10148 cliqueused[cliquenum] =
TRUE;
10149 tmpindices[tmp] = cliquenum;
10154 for( --tmp; tmp >= 0; --tmp)
10155 cliqueused[tmp] =
FALSE;
10157 assert(conshdlrdata->bools4size > 0);
10163 if( conshdlrdata->bools4size < consdata->nvars )
10165 int oldsize = conshdlrdata->bools4size;
10167 conshdlrdata->bools4size = consdata->nvars;
10172 itemremoved = conshdlrdata->bools4;
10176 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10177 assert(itemremoved[tmp] == 0);
10188 for( val = 0; val < 2 && addweightsum < consdata->capacity; ++val )
10190 for(
i = 0;
i < nliftcands[val] && addweightsum < consdata->capacity; ++
i )
10192 SCIP_Longint cliqueweightsum;
10199 probindex = liftcands[val][
i];
10203 if( firstidxs[val][probindex] == 0
10204 || maxcliqueweightsum - zeroweightsums[val][probindex] + addweightsum >= consdata->capacity )
10208 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10210 assert(0 < idx && idx < nzeroitems);
10211 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10212 itemremoved[zeroitems[idx]] =
TRUE;
10216 cliqueweightsum = addweightsum;
10217 for( j = 0; j < consdata->nvars; ++j )
10219 cliquenum = consdata->cliquepartition[j];
10220 assert(0 <= cliquenum && cliquenum < consdata->
nvars);
10221 if( !itemremoved[j] )
10223 if( !cliqueused[cliquenum] )
10225 cliqueweightsum += consdata->weights[j];
10226 cliqueused[cliquenum] =
TRUE;
10227 tmpindices[tmp] = cliquenum;
10231 if( cliqueweightsum >= consdata->capacity )
10237 if( cliqueweightsum < consdata->capacity )
10240 SCIP_Longint weight;
10244 var = binvars[probindex];
10249 weight = consdata->capacity - cliqueweightsum;
10250 addvars[naddvars] =
var;
10251 addweights[naddvars] = weight;
10252 addweightsum += weight;
10260 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10262 assert(0 < idx && idx < nzeroitems);
10263 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10264 itemremoved[zeroitems[idx]] =
FALSE;
10267 for( --tmp; tmp >= 0; --tmp)
10268 cliqueused[tmpindices[tmp]] =
FALSE;
10273 for( --tmp3; tmp3 >= 0; --tmp3)
10274 zeroweightsums[tmpboolindices3[tmp3]][tmpindices3[tmp3]] = 0;
10277 for( --tmp2; tmp2 >= 0; --tmp2)
10279 zeroweightsums[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10280 firstidxs[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10284 for(
i = 0;
i < naddvars; ++
i )
10288 *nchgcoefs += naddvars;
10372 SCIP_Longint* weights;
10373 SCIP_Longint sumcoef;
10374 SCIP_Longint capacity;
10375 SCIP_Longint newweight;
10376 SCIP_Longint maxweight;
10377 SCIP_Longint minweight;
10378 SCIP_Bool sumcoefcase =
FALSE;
10396 assert(consdata->onesweightsum == 0);
10397 assert(consdata->weightsum > consdata->capacity);
10398 assert(consdata->nvars > 0);
10409 assert(consdata->merged);
10414 for(
i = 0;
i < consdata->nvars; ++
i )
10416 SCIP_Longint weight;
10418 weight = consdata->weights[
i];
10419 if( consdata->weightsum - weight < consdata->capacity )
10421 newweight = consdata->weightsum - consdata->capacity;
10423 consdata->capacity -= (weight - newweight);
10426 assert(!consdata->sorted);
10429 consdata->capacity + (weight-newweight), consdata->capacity);
10435 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10439 if( consdata->weightsum <= consdata->capacity )
10443 while( pos < consdata->
nvars && consdata->weights[pos] == consdata->capacity )
10447 weights = consdata->weights;
10448 nvars = consdata->nvars;
10449 capacity = consdata->capacity;
10452 pos <
nvars && weights[pos] + weights[pos + 1] > capacity )
10459 for( k = 0; k < 4; ++k )
10461 newweight = capacity - sumcoef;
10467 sumcoef = weights[
nvars - 1];
10468 backpos =
nvars - 1;
10471 sumcoef = weights[
nvars - 2];
10472 backpos =
nvars - 2;
10477 sumcoefcase =
TRUE;
10478 sumcoef = weights[
nvars - 3];
10479 backpos =
nvars - 3;
10483 sumcoefcase =
FALSE;
10484 sumcoef = weights[
nvars - 1] + weights[
nvars - 2];
10485 backpos =
nvars - 2;
10494 sumcoef = weights[
nvars - 4];
10495 backpos =
nvars - 4;
10499 sumcoef = weights[
nvars - 1] + weights[
nvars - 2];
10500 backpos =
nvars - 2;
10505 sumcoef = weights[
nvars - 3];
10506 backpos =
nvars - 3;
10511 if( backpos <= pos )
10515 maxweight = weights[pos];
10517 while( 2 * maxweight > capacity && maxweight + sumcoef > capacity )
10519 assert(newweight > weights[pos]);
10529 maxweight = weights[pos];
10531 if( backpos <= pos )
10534 (*nchgcoefs) += (pos - startpos);
10537 while( pos <
nvars && weights[pos] + sumcoef == capacity )
10548 if( pos + 1 == backpos && weights[pos] > sumcoef &&
10549 ((k == 0) || (k == 1 && weights[
nvars - 1] + sumcoef + weights[pos] > capacity)) )
10551 newweight = capacity - sumcoef;
10552 assert(newweight > weights[pos]);
10562 if( backpos <= pos )
10570 if( conshdlrdata->disaggregation && consdata->nvars - pos <= MAX_USECLIQUES_SIZE && consdata->
nvars >= 2 &&
10571 pos > 0 && (SCIP_Longint)consdata->nvars - pos <= consdata->capacity &&
10572 consdata->weights[pos - 1] == consdata->capacity && (pos == consdata->nvars || consdata->weights[pos] == 1) )
10586 if( pos == consdata->nvars )
10607 len = consdata->nvars - pos;
10618 for(
w = 0;
w < nclq; ++
w )
10628 for(
w = pos - 1;
w >= 0; --
w )
10629 clqvars[
w] = consdata->vars[
w];
10632 for(
c = 0;
c < nclq; ++
c )
10636 for(
w =
c;
w < len; ++
w )
10638 if( clqpart[
w] ==
c )
10640 assert(nclqvars < pos + len - nclq + 1);
10641 clqvars[nclqvars] = consdata->vars[
w + pos];
10672 SCIP_Longint* maxcliqueweights;
10673 SCIP_Longint* newweightvals;
10674 int* newweightidxs;
10675 SCIP_Longint cliqueweightsum;
10686 SCIP_Bool zeroweights;
10688 assert(consdata->merged);
10697 if( consdata->cliquepartition[consdata->nvars - 1] == consdata->nvars - 1 )
10701 cliqueweightsum = 0;
10704 for(
i = 0;
i < consdata->nvars; ++
i )
10706 SCIP_Longint weight;
10708 cliquenum = consdata->cliquepartition[
i];
10709 assert(0 <= cliquenum && cliquenum <= ncliques);
10711 weight = consdata->weights[
i];
10714 if( cliquenum == ncliques )
10716 maxcliqueweights[ncliques] = weight;
10717 cliqueweightsum += weight;
10721 assert(maxcliqueweights[cliquenum] >= weight);
10725 zeroweights =
FALSE;
10726 for(
i = 0;
i < ncliques; ++
i )
10728 SCIP_Longint delta;
10730 delta = consdata->capacity - (cliqueweightsum - maxcliqueweights[
i]);
10733 SCIP_Longint newcapacity;
10735 SCIP_Longint newmincliqueweight;
10737 SCIP_Longint newminweightsuminclique;
10738 SCIP_Bool forceclique;
10743 SCIPconsGetName(cons),
i, maxcliqueweights[
i], cliqueweightsum, consdata->capacity, delta);
10744 newcapacity = consdata->capacity - delta;
10745 forceclique =
FALSE;
10748 newmincliqueweight = newcapacity + 1;
10749 for( j = 0; j <
i; ++j )
10750 assert(consdata->cliquepartition[j] <
i);
10752 for( j =
i; j < consdata->nvars; ++j )
10754 if( consdata->cliquepartition[j] ==
i )
10756 newweight = consdata->weights[j] - delta;
10757 newweight =
MAX(newweight, 0);
10761 newweightvals[nnewweights] = newweight;
10762 newweightidxs[nnewweights] = j;
10766 assert(newweight <= newmincliqueweight);
10767 newmincliqueweight = newweight;
10773 if( nnewweights > 1 )
10776 j = newweightidxs[nnewweights - 2];
10778 assert(consdata->cliquepartition[j] ==
i);
10779 j = newweightidxs[nnewweights - 1];
10781 assert(consdata->cliquepartition[j] ==
i);
10784 newminweightsuminclique = newweightvals[nnewweights - 2];
10785 newminweightsuminclique += newweightvals[nnewweights - 1];
10792 if( newminweightsuminclique <= newcapacity )
10793 forceclique =
TRUE;
10797 if( conshdlrdata->disaggregation || !forceclique )
10800 consdata->capacity, newcapacity, forceclique);
10801 consdata->capacity = newcapacity;
10804 for( k = 0; k < nnewweights; ++k )
10806 j = newweightidxs[k];
10808 assert(consdata->cliquepartition[j] ==
i);
10812 SCIPvarGetName(consdata->vars[j]), consdata->weights[j], newweightvals[k]);
10815 assert(!consdata->sorted);
10816 zeroweights = zeroweights || (newweightvals[k] == 0);
10830 for( k = 0; k < nnewweights; ++k )
10831 cliquevars[k] = consdata->vars[newweightidxs[k]];
10854 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10862 if( consdata->weightsum <= consdata->capacity )
10874 if( consdata->weightsum <= consdata->capacity )
10880 assert(consdata->merged);
10882 minweight = consdata->weights[consdata->nvars-1];
10883 for(
i = 0;
i < consdata->nvars-1; ++
i )
10885 SCIP_Longint weight;
10887 weight = consdata->weights[
i];
10888 assert(weight >= minweight);
10889 if( minweight + weight > consdata->capacity )
10891 if( weight < consdata->capacity )
10895 assert(consdata->sorted);
10897 assert(
i == 0 || consdata->weights[
i-1] >= consdata->weights[
i]);
10898 consdata->sorted =
TRUE;
10907 if( consdata->nvars >= 2 )
10909 SCIP_Longint weight;
10911 minweight = consdata->weights[consdata->nvars-2];
10912 weight = consdata->weights[consdata->nvars-1];
10913 assert(minweight >= weight);
10914 if( minweight + weight > consdata->capacity && weight < consdata->capacity )
10918 assert(consdata->sorted);
10920 assert(minweight >= consdata->weights[consdata->nvars-1]);
10921 consdata->sorted =
TRUE;
10940 for(
b = 0;
b < ncliquevars; ++
b )
10959 SCIP_Longint* maxweights;
10960 SCIP_Longint* gainweights;
10961 int* gaincliquepartition;
10962 SCIP_Bool* cliqueused;
10963 SCIP_Longint minactduetonegcliques;
10964 SCIP_Longint freecapacity;
10965 SCIP_Longint lastweight;
10966 SCIP_Longint beforelastweight;
10967 int nposcliquevars;
10971 int lastcliqueused;
10986 nvars = consdata->nvars;
10989 if( consdata->cliquesadded ||
nvars == 0 )
11000 assert(consdata->merged);
11007 nnegcliques = consdata->nnegcliques;
11010 if( nnegcliques ==
nvars )
11022 minactduetonegcliques = 0;
11025 for( v = 0; v <
nvars; ++v )
11027 assert(0 <= consdata->negcliquepartition[v] && consdata->negcliquepartition[v] <= nnegcliques);
11028 assert(consdata->weights[v] > 0);
11030 if( consdata->negcliquepartition[v] == nnegcliques )
11033 maxweights[consdata->negcliquepartition[v]] = consdata->weights[v];
11036 minactduetonegcliques += consdata->weights[v];
11039 nposcliquevars = 0;
11042 if( minactduetonegcliques > 0 )
11045 freecapacity = consdata->capacity - minactduetonegcliques;
11049 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
11052 for( v = 0; v <
nvars; ++v )
11054 if( !cliqueused[consdata->negcliquepartition[v]] )
11056 cliqueused[consdata->negcliquepartition[v]] =
TRUE;
11061 if( consdata->negcliquepartition[v] == consdata->negcliquepartition[
w]
11062 && consdata->weights[v] > consdata->weights[
w] )
11064 poscliquevars[nposcliquevars] = consdata->vars[
w];
11065 gainweights[nposcliquevars] = maxweights[consdata->negcliquepartition[v]] - consdata->weights[
w];
11066 gaincliquepartition[nposcliquevars] = consdata->negcliquepartition[v];
11074 if( nposcliquevars > 0 )
11079 for( v = 0; v < nposcliquevars; ++v )
11083 lastweight = gainweights[v];
11084 beforelastweight = -1;
11085 lastcliqueused = gaincliquepartition[v];
11088 cliqueused[gaincliquepartition[v]] =
TRUE;
11094 beforelastweight = lastweight;
11095 lastweight = gainweights[
w];
11096 lastcliqueused = gaincliquepartition[
w];
11097 cliqueused[gaincliquepartition[
w]] =
TRUE;
11102 if( ncliquevars > 1 )
11104 SCIPdebug( printClique(cliquevars, ncliquevars) );
11105 assert(beforelastweight > 0);
11111 *nbdchgs += thisnbdchgs;
11114 cliqueused[lastcliqueused] =
FALSE;
11120 SCIPdebug( printClique(cliquevars, ncliquevars) );
11124 *nbdchgs += thisnbdchgs;
11153 SCIP_Longint* weights,
11155 SCIP_Longint capacity,
11156 SCIP_Bool sorteditems,
11157 SCIP_Real cliqueextractfactor,
11162 SCIP_Longint lastweight;
11171 if( ! sorteditems )
11175 lastweight = weights[0];
11180 lastweight = weights[
i];
11184 if( ncliquevars > 1 )
11186 SCIP_Longint compareweight;
11188 int compareweightidx;
11193 SCIPdebug( printClique(items, ncliquevars) );
11199 *nbdchgs += thisnbdchgs;
11200 nnzadded = ncliquevars;
11203 if( ncliquevars == nitems )
11211 compareweightidx = ncliquevars - 2;
11212 assert(
i == nitems || weights[
i] + weights[ncliquevars - 1] <= capacity);
11215 minclqsize = (int)(cliqueextractfactor * ncliquevars);
11216 minclqsize =
MAX(minclqsize, 2);
11220 while( compareweightidx >= 0 &&
i < nitems && ! (*
cutoff)
11221 && ncliquevars >= minclqsize
11222 && nnzadded <= 2 * nitems
11225 compareweight = weights[compareweightidx];
11226 assert(compareweight > 0);
11229 if( compareweight + weights[
i] > capacity )
11231 assert(compareweightidx == ncliquevars -2);
11232 cliquevars[ncliquevars - 1] = items[
i];
11233 SCIPdebug( printClique(cliquevars, ncliquevars) );
11236 nnzadded += ncliquevars;
11240 *nbdchgs += thisnbdchgs;
11248 compareweightidx--;
11264 SCIP_Real cliqueextractfactor,
11272 SCIP_Longint minactduetonegcliques;
11273 SCIP_Longint freecapacity;
11277 SCIP_Longint* gainweights;
11278 int nposcliquevars;
11279 SCIP_Longint* secondmaxweights;
11292 nvars = consdata->nvars;
11295 if( consdata->cliquesadded ||
nvars == 0 )
11306 assert(consdata->merged);
11313 nnegcliques = consdata->nnegcliques;
11323 minactduetonegcliques = 0;
11326 if( nnegcliques <
nvars )
11332 SCIP_Longint weight;
11334 cliquenum = consdata->negcliquepartition[
i];
11335 assert(0 <= cliquenum && cliquenum <= nnegcliques);
11337 weight = consdata->weights[
i];
11340 if( cliquenum == nnegcliques )
11344 minactduetonegcliques += weight;
11345 if( secondmaxweights[cliquenum] == 0 )
11346 secondmaxweights[cliquenum] = weight;
11352 if( minactduetonegcliques > 0 )
11355 freecapacity = consdata->capacity - minactduetonegcliques;
11359 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
11367 nposcliquevars = 0;
11372 cliquenum = consdata->negcliquepartition[
i];
11373 if( consdata->weights[
i] > secondmaxweights[cliquenum] )
11375 poscliquevars[nposcliquevars] = consdata->vars[
i];
11376 gainweights[nposcliquevars] = consdata->weights[
i] - secondmaxweights[cliquenum];
11382 if( nposcliquevars > 1 )
11399 consdata->cliquesadded =
TRUE;
11428 assert(consdata1->sorted);
11429 assert(consdata2->sorted);
11436 if( consdata1->nvars != consdata2->nvars )
11439 for(
i = consdata1->nvars - 1;
i >= 0; --
i )
11442 if( consdata1->vars[
i] != consdata2->vars[
i] )
11451 if( consdata1->weights[
i] != consdata2->weights[
i] )
11466 uint64_t firstweight;
11473 assert(consdata->nvars > 0);
11486 assert(minidx >= 0 && mididx >= 0 && maxidx >= 0);
11489 firstweight = (uint64_t)consdata->weights[0];
11490 return SCIPhashSix(consdata->nvars, minidx, mididx, maxidx, firstweight>>32, firstweight);
11516 hashtablesize = nconss;
11519 hashGetKeyKnapsackcons, hashKeyEqKnapsackcons, hashKeyValKnapsackcons, (
void*)
scip) );
11522 for(
c = nconss - 1;
c >= 0; --
c )
11535 if( consdata0->nvars == 0 )
11537 if( consdata0->capacity < 0 )
11553 if( cons1 !=
NULL )
11568 assert(consdata0->nvars > 0 && consdata0->nvars == consdata1->nvars);
11570 assert(consdata0->sorted && consdata1->sorted);
11571 assert(consdata0->vars[0] == consdata1->vars[0]);
11572 assert(consdata0->weights[0] == consdata1->weights[0]);
11574 SCIPdebugMsg(
scip,
"knapsack constraints <%s> and <%s> with equal coefficients\n",
11578 if( consdata0->capacity < consdata1->capacity )
11635 assert(firstchange <= chkind);
11639 cons0 = conss[chkind];
11646 assert(consdata0->nvars >= 1);
11647 assert(consdata0->merged);
11653 if( consdata0->capacity == 0 )
11661 SCIP_Bool iscons0incons1contained;
11662 SCIP_Bool iscons1incons0contained;
11663 SCIP_Real quotient;
11680 assert(consdata1->nvars >= 1);
11681 assert(consdata1->merged);
11687 if( consdata1->capacity == 0 )
11690 quotient = ((
SCIP_Real) consdata0->capacity) / ((SCIP_Real) consdata1->capacity);
11692 if( consdata0->nvars > consdata1->nvars )
11694 iscons0incons1contained =
FALSE;
11695 iscons1incons0contained =
TRUE;
11696 v = consdata1->nvars - 1;
11698 else if( consdata0->nvars < consdata1->nvars )
11700 iscons0incons1contained =
TRUE;
11701 iscons1incons0contained =
FALSE;
11702 v = consdata0->nvars - 1;
11706 iscons0incons1contained =
TRUE;
11707 iscons1incons0contained =
TRUE;
11708 v = consdata0->nvars - 1;
11719 v0 = consdata0->nvars - 1;
11720 v1 = consdata1->nvars - 1;
11724 assert(iscons0incons1contained || iscons1incons0contained);
11729 iscons1incons0contained =
FALSE;
11730 if( !iscons0incons1contained )
11736 iscons0incons1contained =
FALSE;
11737 if( !iscons1incons0contained )
11741 assert(v == v0 || v == v1);
11746 if( consdata0->vars[v0] == consdata1->vars[v1] )
11749 if( iscons1incons0contained &&
SCIPisLT(
scip, ((SCIP_Real) consdata0->weights[v0]) / quotient, (SCIP_Real) consdata1->weights[v1]) )
11751 iscons1incons0contained =
FALSE;
11752 if( !iscons0incons1contained )
11756 else if( iscons0incons1contained &&
SCIPisGT(
scip, ((SCIP_Real) consdata0->weights[v0]) / quotient, (SCIP_Real) consdata1->weights[v1]) )
11758 iscons0incons1contained =
FALSE;
11759 if( !iscons1incons0contained )
11769 if( iscons0incons1contained && iscons1incons0contained )
11771 iscons0incons1contained =
FALSE;
11772 iscons1incons0contained =
FALSE;
11775 assert(iscons0incons1contained ? (v1 >= v0) : iscons1incons0contained);
11776 assert(iscons1incons0contained ? (v1 <= v0) : iscons0incons1contained);
11778 if( iscons0incons1contained )
11787 assert(!iscons1incons0contained || !iscons0incons1contained || v0 == -1 || v1 == -1);
11789 if( iscons1incons0contained )
11800 else if( iscons0incons1contained )
11830 SCIP_Bool violated;
11838 SCIPdebugMsg(
scip,
"knapsack enforcement of %d/%d constraints for %s solution\n", nusefulconss, nconss,
11839 sol ==
NULL ?
"LP" :
"relaxation");
11844 maxncuts = (
SCIPgetDepth(
scip) == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
11847 for(
i = 0;
i < nusefulconss && ncuts < maxncuts && !
cutoff;
i++ )
11859 for(
i = nusefulconss;
i < nconss && ncuts == 0 && !
cutoff;
i++ )
11873 else if ( ncuts > 0 )
11896 SCIP_Bool separate,
11906 SCIP_Bool modifiable,
11912 SCIP_Bool removable,
11914 SCIP_Bool stickingatnode
11920 SCIP_Longint* weights;
11921 SCIP_Longint capacity;
11922 SCIP_Longint weight;
11949 for( v = 0; v <
nvars; ++v )
11955 transvars[v] =
vars[v];
11956 weights[v] = weight;
11961 weights[v] = -weight;
11962 capacity -= weight;
11969 initial, separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
11993 upgrade = (nposbin + nnegbin + nposimplbin + nnegimplbin ==
nvars)
11994 && (ncoeffspone + ncoeffsnone + ncoeffspint + ncoeffsnint ==
nvars)
12026 SCIP_Real constant = 0.0;
12043 nlocvars = consdata->nvars;
12048 for(
i = 0;
i < consdata->nvars; ++
i )
12050 vars[
i] = consdata->vars[
i];
12125 conshdlrdata->reals1size =
nvars;
12143 conshdlrdata->reals1size = 0;
12175 conshdlrdata->ints1size =
nvars;
12176 conshdlrdata->ints2size =
nvars;
12177 conshdlrdata->longints1size =
nvars;
12178 conshdlrdata->longints2size =
nvars;
12179 conshdlrdata->bools1size =
nvars;
12180 conshdlrdata->bools2size =
nvars;
12181 conshdlrdata->bools3size =
nvars;
12182 conshdlrdata->bools4size =
nvars;
12184#ifdef WITH_CARDINALITY_UPGRADE
12185 conshdlrdata->upgradedcard =
FALSE;
12202 for(
c = 0;
c < nconss; ++
c )
12223 conshdlrdata->ints1size = 0;
12224 conshdlrdata->ints2size = 0;
12225 conshdlrdata->longints1size = 0;
12226 conshdlrdata->longints2size = 0;
12227 conshdlrdata->bools1size = 0;
12228 conshdlrdata->bools2size = 0;
12229 conshdlrdata->bools3size = 0;
12230 conshdlrdata->bools4size = 0;
12243 for(
c = 0;
c < nconss; ++
c )
12262 for(
c = 0;
c < nconss; ++
c )
12267 if( consdata->row !=
NULL )
12272 if( consdata->nlrow !=
NULL )
12327 sourcedata->nvars, sourcedata->vars, sourcedata->weights, sourcedata->capacity) );
12349 *infeasible =
FALSE;
12351 for(
i = 0;
i < nconss && !(*infeasible);
i++ )
12365 SCIP_Bool sepacardinality;
12368 SCIP_Real loclowerbound;
12369 SCIP_Real glblowerbound;
12370 SCIP_Real cutoffbound;
12371 SCIP_Real maxbound;
12389 SCIPdebugMsg(
scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12390 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12393 if( (
depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12394 || (
depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12399 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12400 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12401 && ((sepacardfreq == 0 &&
depth == 0) || (sepacardfreq >= 1 && (
depth % sepacardfreq == 0)));
12407 maxbound = glblowerbound + conshdlrdata->maxcardbounddist * (cutoffbound - glblowerbound);
12408 sepacardinality = sepacardinality &&
SCIPisLE(
scip, loclowerbound, maxbound);
12412 maxsepacuts = (
depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12427 else if ( ncuts > 0 )
12439 SCIP_Bool sepacardinality;
12458 SCIPdebugMsg(
scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12459 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12462 if( (
depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12463 || (
depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12468 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12469 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12470 && ((sepacardfreq == 0 &&
depth == 0) || (sepacardfreq >= 1 && (
depth % sepacardfreq == 0)));
12473 maxsepacuts = (
depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12488 else if( ncuts > 0 )
12516 SCIP_Bool violated;
12519 for(
i = 0;
i < nconss;
i++ )
12537 SCIP_Bool violated;
12558 SCIP_Bool redundant;
12559 SCIP_Bool inpresolve;
12573 for(
i = 0;
i < nmarkedconss && !
cutoff;
i++ )
12594 else if( nfixedvars > 0 )
12610 SCIP_Bool redundant;
12620 SCIP_Bool newchanges;
12624 oldnfixedvars = *nfixedvars;
12625 oldnchgbds = *nchgbds;
12626 oldndelconss = *ndelconss;
12627 oldnaddconss = *naddconss;
12628 oldnchgcoefs = *nchgcoefs;
12629 oldnchgsides = *nchgsides;
12630 firstchange = INT_MAX;
12632 newchanges = (nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 || nnewupgdconss > 0);
12639 int thisnfixedvars;
12648 if( newchanges || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
12657 consdata->presolvedtiming = 0;
12658 else if( consdata->presolvedtiming >= presoltiming )
12663 consdata->presolvedtiming = presoltiming;
12665 thisnfixedvars = *nfixedvars;
12666 thisnchgbds = *nchgbds;
12696 if( *nfixedvars > thisnfixedvars || *nchgbds > thisnchgbds )
12702 thisnfixedvars = *nfixedvars;
12708 if( consdata->weightsum <= consdata->capacity )
12730 if( *nfixedvars > thisnfixedvars )
12771 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) || (*naddconss != oldnaddconss) )
12778 SCIP_Longint npaircomparisons;
12780 npaircomparisons = 0;
12781 oldndelconss = *ndelconss;
12782 oldnchgsides = *nchgsides;
12783 oldnchgcoefs = *nchgcoefs;
12797 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) )
12799 if( ((SCIP_Real) (*ndelconss - oldndelconss) + ((SCIP_Real) (*nchgsides - oldnchgsides))/2.0 +
12802 oldndelconss = *ndelconss;
12803 oldnchgsides = *nchgsides;
12804 oldnchgcoefs = *nchgcoefs;
12805 npaircomparisons = 0;
12809#ifdef WITH_CARDINALITY_UPGRADE
12822 SCIP_Real* cardweights;
12827 noldupgdconss = *nupgdconss;
12840 for (makeupgrade = 0; makeupgrade < 2; ++makeupgrade)
12846 SCIP_Longint* weights;
12855 nvars = consdata->nvars;
12856 vars = consdata->vars;
12857 weights = consdata->weights;
12864 if ( consdata->capacity >=
nvars )
12868 assert( consdata->sorted );
12869 if ( weights[0] != 1 || weights[
nvars-1] != 1 )
12873 for (v = 0; v <
nvars; ++v)
12876 SCIP_Real* implbounds;
12882 var = consdata->vars[v];
12899 for (j = 0; j < nimpls; ++j)
12913 cardvars[v] = implvars[j];
12930 if ( makeupgrade == 0 )
12932 for (v = 0; v <
nvars; ++v)
12956 for (v = 0; v <
nvars; ++v)
12966 conshdlrdata->upgradedcard =
TRUE;
12998 for (v = 0; v <
nvars; ++v)
13014 if ( *nupgdconss > noldupgdconss )
13021 else if( success || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
13034 SCIP_Longint capsum;
13045 for(
i = 0;
i < consdata->nvars; ++
i )
13062 if( inferinfo < 0 )
13069 if( inferinfo < consdata->
nvars && consdata->vars[inferinfo] == infervar )
13070 capsum = consdata->weights[inferinfo];
13073 for(
i = 0;
i < consdata->nvars && consdata->vars[
i] != infervar; ++
i )
13076 capsum = consdata->weights[
i];
13083 if( capsum <= consdata->capacity )
13085 for(
i = 0;
i < consdata->nvars;
i++ )
13090 capsum += consdata->weights[
i];
13091 if( capsum > consdata->capacity )
13123 for(
i = 0;
i < consdata->nvars;
i++)
13196 for(
i = 0;
i < consdata->nvars; ++
i )
13213 SCIP_Longint* weights;
13215 const char* consname;
13225 for( v = 0; v <
nvars; ++v )
13226 coefs[v] = (SCIP_Real) weights[v];
13236 initial, separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode, global,
valid) );
13249 SCIP_Longint weight;
13251 SCIP_Longint* weights;
13252 SCIP_Longint capacity;
13271 while( *str !=
'\0' )
13284 endptr = strchr(endptr,
'<');
13286 if( endptr ==
NULL )
13300 if( varssize <=
nvars )
13308 weights[
nvars] = weight;
13317 if( strncmp(str,
"<=", 2) != 0 )
13342 initial, separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
13361 if( varssize < consdata->
nvars )
13362 (*success) =
FALSE;
13383 (*nvars) = consdata->nvars;
13426 consdata->onesweightsum += eventdata->weight;
13427 consdata->presolvedtiming = 0;
13431 consdata->onesweightsum -= eventdata->weight;
13434 consdata->presolvedtiming = 0;
13438 if( !consdata->existmultaggr )
13447 consdata->existmultaggr =
TRUE;
13448 consdata->merged =
FALSE;
13452 consdata->merged =
FALSE;
13456 consdata->presolvedtiming = 0;
13459 consdata->varsdeleted =
TRUE;
13487 eventhdlrdata =
NULL;
13488 conshdlrdata->eventhdlr =
NULL;
13490 eventExecKnapsack, eventhdlrdata) );
13493 if( conshdlrdata->eventhdlr ==
NULL )
13502 consEnfolpKnapsack, consEnfopsKnapsack, consCheckKnapsack, consLockKnapsack,
13545 "multiplier on separation frequency, how often knapsack cuts are separated (-1: never, 0: only at root)",
13549 "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for separating knapsack cuts",
13553 "lower clique size limit for greedy clique extraction algorithm (relative to largest clique)",
13557 "maximal number of separation rounds per node (-1: unlimited)",
13561 "maximal number of separation rounds per node in the root node (-1: unlimited)",
13565 "maximal number of cuts separated per separation round",
13569 "maximal number of cuts separated per separation round in the root node",
13573 "should disaggregation of knapsack constraints be allowed in preprocessing?",
13577 "should presolving try to simplify knapsacks",
13581 "should negated clique information be used in solving process",
13585 "should pairwise constraint comparison be performed in presolving?",
13589 "should hash table be used for detecting redundant constraints in advance",
13593 "should dual presolving steps be performed?",
13597 "should GUB information be used for separation?",
13601 "should presolving try to detect constraints parallel to the objective function defining an upper bound and prevent these constraints from entering the LP?",
13605 "should presolving try to detect constraints parallel to the objective function defining a lower bound and prevent these constraints from entering the LP?",
13609 "should clique partition information be updated when old partition seems outdated?",
13613 "factor on the growth of global cliques to decide when to update a previous "
13614 "(negated) clique partition (used only if updatecliquepartitions is set to TRUE)",
13616#ifdef WITH_CARDINALITY_UPGRADE
13619 "if TRUE then try to update knapsack constraints to cardinality constraints",
13620 &conshdlrdata->upgdcardinality,
TRUE, DEFAULT_UPGDCARDINALITY,
NULL,
NULL) );
13636 SCIP_Longint* weights,
13637 SCIP_Longint capacity,
13640 SCIP_Bool separate,
13650 SCIP_Bool modifiable,
13656 SCIP_Bool removable,
13658 SCIP_Bool stickingatnode
13669 if( conshdlr ==
NULL )
13684 SCIP_CALL(
SCIPcreateCons(
scip, cons, name, conshdlr, consdata, initial, separate, enforce, check,
propagate,
13685 local, modifiable, dynamic, removable, stickingatnode) );
13711 SCIP_Longint* weights,
13712 SCIP_Longint capacity
13728 SCIP_Longint weight
13765 return consdata->capacity;
13775 SCIP_Longint capacity
13790 SCIPerrorMessage(
"method can only be called during problem creation stage\n");
13797 consdata->capacity = capacity;
13822 return consdata->nvars;
13845 return consdata->vars;
13868 return consdata->weights;
13891 if( consdata->row !=
NULL )
13917 if( consdata->row !=
NULL )
13945 return consdata->row;
13951 SCIP_Bool onlychecked,
13952 SCIP_Bool* infeasible
13961 if( conshdlr ==
NULL )
13965 *infeasible =
FALSE;
13970 for(
i = 0;
i < nconss; ++
i )
constraint handler for cardinality constraints
static SCIP_Longint safeAddMinweightsGUB(SCIP_Longint val1, SCIP_Longint val2)
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool sepacuts, SCIP_Bool usegubs, SCIP_Bool *cutoff, int *ncuts)
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
static SCIP_RETCODE getLiftingSequenceGUB(SCIP *scip, SCIP_GUBSET *gubset, SCIP_Real *solvals, SCIP_Longint *weights, int *varsC1, int *varsC2, int *varsF, int *varsR, int nvarsC1, int nvarsC2, int nvarsF, int nvarsR, int *gubconsGC1, int *gubconsGC2, int *gubconsGFC1, int *gubconsGR, int *ngubconsGC1, int *ngubconsGC2, int *ngubconsGFC1, int *ngubconsGR, int *ngubconscapexceed, int *maxgubvarssize)
@ GUBCONSSTATUS_BELONGSTOSET_GF
@ GUBCONSSTATUS_UNINITIAL
@ GUBCONSSTATUS_BELONGSTOSET_GR
@ GUBCONSSTATUS_BELONGSTOSET_GOC1
@ GUBCONSSTATUS_BELONGSTOSET_GNC1
@ GUBCONSSTATUS_BELONGSTOSET_GC2
#define DEFAULT_DUALPRESOLVING
static SCIP_RETCODE deleteRedundantVars(SCIP *scip, SCIP_CONS *cons, SCIP_Longint frontsum, int splitpos, int *nchgcoefs, int *nchgsides, int *naddconss)
#define CONSHDLR_NEEDSCONS
#define DEFAULT_SEPACARDFREQ
#define CONSHDLR_SEPAFREQ
static SCIP_RETCODE insertZerolist(SCIP *scip, int **liftcands, int *nliftcands, int **firstidxs, SCIP_Longint **zeroweightsums, int **zeroitems, int **nextidxs, int *zeroitemssize, int *nzeroitems, int probindex, SCIP_Bool value, int knapsackidx, SCIP_Longint knapsackweight, SCIP_Bool *memlimitreached)
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
#define KNAPSACKRELAX_MAXDELTA
static SCIP_RETCODE eventdataCreate(SCIP *scip, SCIP_EVENTDATA **eventdata, SCIP_CONS *cons, SCIP_Longint weight)
static SCIP_RETCODE prepareCons(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, int *nchgcoefs)
#define CONSHDLR_CHECKPRIORITY
static SCIP_RETCODE enlargeMinweights(SCIP *scip, SCIP_Longint **minweightsptr, int *minweightslen, int *minweightssize, int newlen)
static SCIP_RETCODE separateSequLiftedExtendedWeightInequality(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *feassetvars, int *nonfeassetvars, int nfeassetvars, int nnonfeassetvars, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts)
static SCIP_RETCODE GUBconsCreate(SCIP *scip, SCIP_GUBCONS **gubcons)
#define KNAPSACKRELAX_MAXSCALE
static void normalizeWeights(SCIP_CONS *cons, int *nchgcoefs, int *nchgsides)
static SCIP_RETCODE separateSupLiftedMinimalCoverInequality(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *mincovervars, int *nonmincovervars, int nmincovervars, int nnonmincovervars, SCIP_Longint mincoverweight, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts)
#define DEFAULT_DETECTCUTOFFBOUND
static SCIP_RETCODE addCliques(SCIP *const scip, SCIP_CONS *const cons, SCIP_Real cliqueextractfactor, SCIP_Bool *const cutoff, int *const nbdchgs)
static SCIP_RETCODE upgradeCons(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss)
static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons)
static void updateWeightSums(SCIP_CONSDATA *consdata, SCIP_VAR *var, SCIP_Longint weightdelta)
static void GUBconsFree(SCIP *scip, SCIP_GUBCONS **gubcons)
#define CONSHDLR_PROP_TIMING
static void getPartitionCovervars(SCIP *scip, SCIP_Real *solvals, int *covervars, int ncovervars, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2)
static void GUBsetSwapVars(SCIP *scip, SCIP_GUBSET *gubset, int var1, int var2)
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
static SCIP_RETCODE getCover(SCIP *scip, SCIP_VAR **vars, int nvars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int *ncovervars, int *nnoncovervars, SCIP_Longint *coverweight, SCIP_Bool *found, SCIP_Bool modtransused, int *ntightened, SCIP_Bool *fractional)
static SCIP_RETCODE consdataEnsureVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool transformed)
static void GUBsetFree(SCIP *scip, SCIP_GUBSET **gubset)
static SCIP_RETCODE createNormalizedKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define CONSHDLR_MAXPREROUNDS
static SCIP_RETCODE calcCliquepartition(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSDATA *consdata, SCIP_Bool normalclique, SCIP_Bool negatedclique)
#define DEFAULT_PRESOLPAIRWISE
static SCIP_RETCODE performVarDeletions(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss)
#define CONSHDLR_SEPAPRIORITY
#define DEFAULT_MAXROUNDSROOT
struct sortkeypair SORTKEYPAIR
#define DEFAULT_NEGATEDCLIQUE
enum GUBVarstatus GUBVARSTATUS
static SCIP_RETCODE changePartitionCovervars(SCIP *scip, SCIP_Longint *weights, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2)
#define DEFAULT_MAXCARDBOUNDDIST
#define MAXCOVERSIZEITERLEWI
static SCIP_RETCODE mergeMultiples(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
static SCIP_RETCODE GUBsetCheck(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars)
static SCIP_RETCODE GUBsetMoveVar(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, int var, int oldgubcons, int newgubcons)
static void sortItems(SCIP_CONSDATA *consdata)
static SCIP_RETCODE addNegatedCliques(SCIP *const scip, SCIP_CONS *const cons, SCIP_Bool *const cutoff, int *const nbdchgs)
static SCIP_RETCODE detectRedundantVars(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss)
static SCIP_RETCODE GUBsetGetCliquePartition(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, SCIP_Real *solvals)
static SCIP_RETCODE addSymmetryInformation(SCIP *scip, SYM_SYMTYPE symtype, SCIP_CONS *cons, SYM_GRAPH *graph, SCIP_Bool *success)
static SCIP_RETCODE applyFixings(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
static void computeMinweightsGUB(SCIP_Longint *minweights, SCIP_Longint *finished, SCIP_Longint *unfinished, int minweightslen)
static SCIP_RETCODE sequentialUpAndDownLiftingGUB(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, int ngubconscapexceed, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *gubconsGC1, int *gubconsGC2, int *gubconsGFC1, int *gubconsGR, int ngubconsGC1, int ngubconsGC2, int ngubconsGFC1, int ngubconsGR, int alpha0, int *liftcoefs, SCIP_Real *cutact, int *liftrhs, int maxgubvarssize)
#define HASHSIZE_KNAPSACKCONS
static SCIP_RETCODE GUBsetCalcCliquePartition(SCIP *const scip, SCIP_VAR **const vars, int const nvars, int *const cliquepartition, int *const ncliques, SCIP_Real *solvals)
#define DEFAULT_MAXSEPACUTSROOT
static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checklprows, SCIP_Bool printreason, SCIP_Bool *violated)
static SCIP_RETCODE dualWeightsTightening(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss)
#define DEFAULT_PRESOLUSEHASHING
#define DEFAULT_CLQPARTUPDATEFAC
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight)
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr)
static SCIP_Bool checkMinweightidx(SCIP_Longint *weights, SCIP_Longint capacity, int *covervars, int ncovervars, SCIP_Longint coverweight, int minweightidx, int j)
static SCIP_RETCODE sequentialUpAndDownLifting(SCIP *scip, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *varsM1, int *varsM2, int *varsF, int *varsR, int nvarsM1, int nvarsM2, int nvarsF, int nvarsR, int alpha0, int *liftcoefs, SCIP_Real *cutact, int *liftrhs)
static SCIP_RETCODE separateSequLiftedMinimalCoverInequality(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *mincovervars, int *nonmincovervars, int nmincovervars, int nnonmincovervars, SCIP_SOL *sol, SCIP_GUBSET *gubset, SCIP_Bool *cutoff, int *ncuts)
static SCIP_RETCODE makeCoverMinimal(SCIP *scip, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int *ncovervars, int *nnoncovervars, SCIP_Longint *coverweight, SCIP_Bool modtransused)
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, int pos)
#define MINGAINPERNMINCOMPARISONS
static SCIP_RETCODE greedyCliqueAlgorithm(SCIP *const scip, SCIP_VAR **items, SCIP_Longint *weights, int nitems, SCIP_Longint capacity, SCIP_Bool sorteditems, SCIP_Real cliqueextractfactor, SCIP_Bool *const cutoff, int *const nbdchgs)
#define DEFAULT_CLIQUEEXTRACTFACTOR
#define DEFAULT_SIMPLIFYINEQUALITIES
static SCIP_RETCODE eventdataFree(SCIP *scip, SCIP_EVENTDATA **eventdata)
static SCIP_RETCODE detectRedundantConstraints(SCIP *scip, BMS_BLKMEM *blkmem, SCIP_CONS **conss, int nconss, SCIP_Bool *cutoff, int *ndelconss)
static SCIP_RETCODE GUBsetCreate(SCIP *scip, SCIP_GUBSET **gubset, int nvars, SCIP_Longint *weights, SCIP_Longint capacity)
static SCIP_RETCODE getLiftingSequence(SCIP *scip, SCIP_Real *solvals, SCIP_Longint *weights, int *varsF, int *varsC2, int *varsR, int nvarsF, int nvarsC2, int nvarsR)
#define CONSHDLR_PROPFREQ
#define MAXNCLIQUEVARSCOMP
static SCIP_RETCODE tightenWeightsLift(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, SCIP_Bool *cutoff)
static SCIP_RETCODE getFeasibleSet(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int *ncovervars, int *nnoncovervars, SCIP_Longint *coverweight, SCIP_Bool modtransused, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts)
static SCIP_RETCODE simplifyInequalities(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss, SCIP_Bool *cutoff)
enum GUBConsstatus GUBCONSSTATUS
static SCIP_RETCODE removeZeroWeights(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
#define CONSHDLR_PRESOLTIMING
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result)
#define DEFAULT_MAXSEPACUTS
static SCIP_RETCODE superadditiveUpLifting(SCIP *scip, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int ncovervars, int nnoncovervars, SCIP_Longint coverweight, SCIP_Real *liftcoefs, SCIP_Real *cutact)
static SCIP_RETCODE addNlrow(SCIP *scip, SCIP_CONS *cons)
static void getPartitionNoncovervars(SCIP *scip, SCIP_Real *solvals, int *noncovervars, int nnoncovervars, int *varsF, int *varsR, int *nvarsF, int *nvarsR)
static SCIP_RETCODE stableSort(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR **vars, SCIP_Longint *weights, int *cliquestartposs, SCIP_Bool usenegatedclique)
static SCIP_RETCODE tightenWeights(SCIP *scip, SCIP_CONS *cons, SCIP_PRESOLTIMING presoltiming, int *nchgcoefs, int *nchgsides, int *naddconss, int *ndelconss, SCIP_Bool *cutoff)
#define CONSHDLR_EAGERFREQ
static void consdataChgWeight(SCIP_CONSDATA *consdata, int item, SCIP_Longint newweight)
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, SCIP_Bool *redundant, int *nfixedvars, SCIP_Bool usenegatedclique)
#define KNAPSACKRELAX_MAXDNOM
#define DEFAULT_MAXROUNDS
#define CONSHDLR_ENFOPRIORITY
#define LINCONSUPGD_PRIORITY
#define CONSHDLR_DELAYSEPA
#define MAX_USECLIQUES_SIZE
#define DEFAULT_UPDATECLIQUEPARTITIONS
@ GUBVARSTATUS_BELONGSTOSET_F
@ GUBVARSTATUS_BELONGSTOSET_C1
@ GUBVARSTATUS_BELONGSTOSET_R
@ GUBVARSTATUS_BELONGSTOSET_C2
@ GUBVARSTATUS_CAPACITYEXCEEDED
static SCIP_RETCODE checkParallelObjective(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata)
static SCIP_RETCODE GUBconsAddVar(SCIP *scip, SCIP_GUBCONS *gubcons, int var)
static SCIP_RETCODE changePartitionFeasiblesetvars(SCIP *scip, SCIP_Longint *weights, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2)
#define DEFAULT_DISAGGREGATION
static SCIP_RETCODE preprocessConstraintPairs(SCIP *scip, SCIP_CONS **conss, int firstchange, int chkind, int *ndelconss)
static SCIP_RETCODE GUBconsDelVar(SCIP *scip, SCIP_GUBCONS *gubcons, int var, int gubvarsidx)
#define DEFAULT_DETECTLOWERBOUND
static SCIP_RETCODE dualPresolving(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, SCIP_Bool *deleted)
#define CONSHDLR_DELAYPROP
#define EVENTTYPE_KNAPSACK
#define MAX_ZEROITEMS_SIZE
Constraint handler for knapsack constraints of the form , x binary and .
Constraint handler for linear constraints in their most general form, .
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIP_MAXTREEDEPTH
#define SCIP_LONGINT_FORMAT
SCIP_RETCODE SCIPincludeLinconsUpgrade(SCIP *scip, SCIP_DECL_LINCONSUPGD((*linconsupgd)), int priority, const char *conshdlrname)
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsCardinality(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int cardval, SCIP_VAR **indvars, SCIP_Real *weights, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPaddCoefKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight)
SCIP_RETCODE SCIPsolveKnapsackApproximately(SCIP *scip, int nitems, SCIP_Longint *weights, SCIP_Real *profits, SCIP_Longint capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval)
SCIP_RETCODE SCIPcleanupConssKnapsack(SCIP *scip, SCIP_Bool onlychecked, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPseparateKnapsackCuts(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_SOL *sol, SCIP_Bool usegubs, SCIP_Bool *cutoff, int *ncuts)
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPcreateConsBasicKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
SCIP_RETCODE SCIPchgCapacityKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_Longint capacity)
SCIP_RETCODE SCIPseparateRelaxedKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, int nknapvars, SCIP_VAR **knapvars, SCIP_Real *knapvals, SCIP_Real valscale, SCIP_Real rhs, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts)
SCIP_RETCODE SCIPsolveKnapsackExactly(SCIP *scip, int nitems, SCIP_Longint *weights, SCIP_Real *profits, SCIP_Longint capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval, SCIP_Bool *success)
#define SCIP_DECL_LINCONSUPGD(x)
SCIP_RETCODE SCIPcreateConsKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPcopyConsLinear(SCIP *scip, SCIP_CONS **cons, SCIP *sourcescip, const char *name, int nvars, SCIP_VAR **sourcevars, SCIP_Real *sourcecoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode, SCIP_Bool global, SCIP_Bool *valid)
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Real SCIPgetDualfarkasKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_ROW * SCIPgetRowKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetDualsolKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPincludeConshdlrKnapsack(SCIP *scip)
SCIP_Bool SCIPisConsCompressionEnabled(SCIP *scip)
SCIP_Bool SCIPisTransformed(SCIP *scip)
SCIP_Bool SCIPisPresolveFinished(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNObjVars(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_CONS * SCIPfindOrigCons(SCIP *scip, const char *name)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
#define SCIPhashSix(a, b, c, d, e, f)
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
SCIP_RETCODE SCIPupdateLocalLowerbound(SCIP *scip, SCIP_Real newbound)
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLocalLowerbound(SCIP *scip)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
#define SCIPdebugMsgPrint
SCIP_Longint SCIPcalcGreComDiv(SCIP_Longint val1, SCIP_Longint val2)
SCIP_RETCODE SCIPcalcIntegralScalar(SCIP_Real *vals, int nvals, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Real *intscalar, SCIP_Bool *success)
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_CONS ** SCIPconshdlrGetCheckConss(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_Longint SCIPconshdlrGetNCutsFound(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrGetSignedPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)),)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrGetPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
int SCIPconshdlrGetSepaFreq(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPsetConshdlrDelvars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
SCIP_RETCODE SCIPsetConsSeparated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool separate)
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial)
SCIP_RETCODE SCIPsetConsEnforced(SCIP *scip, SCIP_CONS *cons, SCIP_Bool enforce)
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
SCIP_RETCODE SCIPunmarkConsPropagate(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPmarkConsPropagate(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPsetConsPropagated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool propagate)
SCIP_RETCODE SCIPsetConsChecked(SCIP *scip, SCIP_CONS *cons, SCIP_Bool check)
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
#define SCIPfreeBuffer(scip, ptr)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBufferArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPallocBuffer(scip, ptr)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_RETCODE SCIPdelNlRow(SCIP *scip, SCIP_NLROW *nlrow)
SCIP_RETCODE SCIPaddNlRow(SCIP *scip, SCIP_NLROW *nlrow)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
SCIP_RETCODE SCIPreleaseNlRow(SCIP *scip, SCIP_NLROW **nlrow)
SCIP_Bool SCIPnlrowIsInNLP(SCIP_NLROW *nlrow)
SCIP_RETCODE SCIPcreateNlRow(SCIP *scip, SCIP_NLROW **nlrow, const char *name, SCIP_Real constant, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, SCIP_EXPR *expr, SCIP_Real lhs, SCIP_Real rhs, SCIP_EXPRCURV curvature)
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONS *cons, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_RETCODE SCIPcreateEmptyRowUnspec(SCIP *scip, SCIP_ROW **row, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_Real SCIProwGetDualfarkas(SCIP_ROW *row)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
SCIP_Longint SCIPsepaGetNCutsFound(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
void SCIPupdateSolLPConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
SCIP_RETCODE SCIPupdateCutoffbound(SCIP *scip, SCIP_Real cutoffbound)
int SCIPgetNSepaRounds(SCIP *scip)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPcutoffbounddelta(SCIP *scip)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
int SCIPvarGetNVlbs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsDeleted(SCIP_VAR *var)
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var)
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_RETCODE SCIPaddClique(SCIP *scip, SCIP_VAR **vars, SCIP_Bool *values, int nvars, SCIP_Bool isequation, SCIP_Bool *infeasible, int *nbdchgs)
SCIP_RETCODE SCIPcalcCliquePartition(SCIP *const scip, SCIP_VAR **const vars, int const nvars, int *const cliquepartition, int *const ncliques)
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_RETCODE SCIPcalcNegatedCliquePartition(SCIP *const scip, SCIP_VAR **const vars, int const nvars, int *const cliquepartition, int *const ncliques)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
int SCIPvarGetIndex(SCIP_VAR *var)
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
int SCIPvarGetNVubs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_RETCODE SCIPflattenVarAggregationGraph(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
int SCIPgetNCliques(SCIP *scip)
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_RETCODE SCIPgetNegatedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **negvars)
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
SCIP_RETCODE SCIPvarsGetProbvarBinary(SCIP_VAR ***vars, SCIP_Bool **negatedarr, int nvars)
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
void SCIPselectWeightedDownRealLongRealInt(SCIP_Real *realarray1, SCIP_Longint *longarray, SCIP_Real *realarray3, int *intarray, SCIP_Real *weights, SCIP_Real capacity, int len, int *medianpos)
void SCIPsortDownLongPtr(SCIP_Longint *longarray, void **ptrarray, int len)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortPtrPtrIntInt(void **ptrarray1, void **ptrarray2, int *intarray1, int *intarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortPtrPtrLongIntInt(void **ptrarray1, void **ptrarray2, SCIP_Longint *longarray, int *intarray1, int *intarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortDownPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortDownLongPtrPtrIntInt(SCIP_Longint *longarray, void **ptrarray1, void **ptrarray2, int *intarray1, int *intarray2, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownRealIntLong(SCIP_Real *realarray, int *intarray, SCIP_Longint *longarray, int len)
void SCIPsortPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownLongPtrInt(SCIP_Longint *longarray, void **ptrarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIP_RETCODE SCIPskipSpace(char **s)
SCIP_RETCODE SCIPgetSymActiveVariables(SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
SCIP_RETCODE SCIPextendPermsymDetectionGraphLinear(SCIP *scip, SYM_GRAPH *graph, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool *success)
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_Bool propagate
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
#define BMSclearMemoryArray(ptr, num)
struct BMS_BlkMem BMS_BLKMEM
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for managing constraints
public methods for managing events
public methods for implications, variable bounds, and cliques
public methods for LP management
public methods for message output
#define SCIPdebugPrintCons(x, y, z)
public data structures and miscellaneous methods
methods for selecting (weighted) k-medians
methods for sorting joint arrays of various types
public methods for separators
public methods for problem variables
public methods for branching rule plugins and branching
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for cuts and aggregation rows
public methods for event handler plugins and event handlers
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
GUBVARSTATUS * gubvarsstatus
GUBCONSSTATUS * gubconsstatus
structs for symmetry computations
methods for dealing with symmetry detection graphs
@ SCIP_CONFTYPE_PROPAGATION
#define SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(x)
#define SCIP_DECL_CONSGETPERMSYMGRAPH(x)
#define SCIP_DECL_CONSENFOLP(x)
#define SCIP_DECL_CONSINITPRE(x)
#define SCIP_DECL_CONSDELETE(x)
#define SCIP_DECL_CONSEXIT(x)
#define SCIP_DECL_CONSGETVARS(x)
#define SCIP_DECL_CONSINITSOL(x)
#define SCIP_DECL_CONSPRINT(x)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
#define SCIP_DECL_CONSSEPALP(x)
#define SCIP_DECL_CONSENFORELAX(x)
#define SCIP_DECL_CONSPROP(x)
#define SCIP_DECL_CONSGETNVARS(x)
#define SCIP_DECL_CONSRESPROP(x)
#define SCIP_DECL_CONSACTIVE(x)
#define SCIP_DECL_CONSENFOPS(x)
#define SCIP_DECL_CONSPARSE(x)
#define SCIP_DECL_CONSTRANS(x)
#define SCIP_DECL_CONSDEACTIVE(x)
#define SCIP_DECL_CONSPRESOL(x)
#define SCIP_DECL_CONSINITLP(x)
#define SCIP_DECL_CONSEXITPRE(x)
#define SCIP_DECL_CONSLOCK(x)
#define SCIP_DECL_CONSCOPY(x)
#define SCIP_DECL_CONSINIT(x)
struct SCIP_ConsData SCIP_CONSDATA
#define SCIP_DECL_CONSCHECK(x)
#define SCIP_DECL_CONSHDLRCOPY(x)
#define SCIP_DECL_CONSEXITSOL(x)
#define SCIP_DECL_CONSFREE(x)
#define SCIP_DECL_CONSSEPASOL(x)
#define SCIP_DECL_CONSDELVARS(x)
struct SCIP_EventData SCIP_EVENTDATA
#define SCIP_EVENTTYPE_UBTIGHTENED
#define SCIP_EVENTTYPE_VARFIXED
#define SCIP_EVENTTYPE_VARDELETED
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_EVENTTYPE_LBRELAXED
#define SCIP_EVENTTYPE_FORMAT
#define SCIP_EVENTTYPE_IMPLADDED
#define SCIP_EVENTTYPE_LBTIGHTENED
enum SCIP_BoundType SCIP_BOUNDTYPE
#define SCIP_DECL_SORTPTRCOMP(x)
#define SCIP_DECL_HASHKEYEQ(x)
#define SCIP_DECL_HASHGETKEY(x)
#define SCIP_DECL_HASHKEYVAL(x)
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_TRANSFORMING
enum SYM_Symtype SYM_SYMTYPE
#define SCIP_PRESOLTIMING_MEDIUM
unsigned int SCIP_PRESOLTIMING
#define SCIP_PRESOLTIMING_FAST
#define SCIP_PRESOLTIMING_EXHAUSTIVE
@ SCIP_VARSTATUS_MULTAGGR
@ SCIP_VARSTATUS_AGGREGATED