75#ifdef WITH_CARDINALITY_UPGRADE
80#define CONSHDLR_NAME "knapsack"
81#define CONSHDLR_DESC "knapsack constraint of the form a^T x <= b, x binary and a >= 0"
82#define CONSHDLR_SEPAPRIORITY +600000
83#define CONSHDLR_ENFOPRIORITY -600000
84#define CONSHDLR_CHECKPRIORITY -600000
85#define CONSHDLR_SEPAFREQ 0
86#define CONSHDLR_PROPFREQ 1
87#define CONSHDLR_EAGERFREQ 100
89#define CONSHDLR_MAXPREROUNDS -1
90#define CONSHDLR_DELAYSEPA FALSE
91#define CONSHDLR_DELAYPROP FALSE
92#define CONSHDLR_NEEDSCONS TRUE
94#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
95#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
97#define EVENTHDLR_NAME "knapsack"
98#define EVENTHDLR_DESC "bound change event handler for knapsack constraints"
99#define EVENTTYPE_KNAPSACK SCIP_EVENTTYPE_LBCHANGED \
100 | SCIP_EVENTTYPE_UBTIGHTENED \
101 | SCIP_EVENTTYPE_VARFIXED \
102 | SCIP_EVENTTYPE_VARDELETED \
103 | SCIP_EVENTTYPE_IMPLADDED
105#define LINCONSUPGD_PRIORITY +100000
107#define MAX_USECLIQUES_SIZE 1000
108#define MAX_ZEROITEMS_SIZE 10000
110#define KNAPSACKRELAX_MAXDELTA 0.1
111#define KNAPSACKRELAX_MAXDNOM 1000LL
112#define KNAPSACKRELAX_MAXSCALE 1000.0
114#define DEFAULT_SEPACARDFREQ 1
115#define DEFAULT_MAXROUNDS 5
116#define DEFAULT_MAXROUNDSROOT -1
117#define DEFAULT_MAXSEPACUTS 50
118#define DEFAULT_MAXSEPACUTSROOT 200
119#define DEFAULT_MAXCARDBOUNDDIST 0.0
121#define DEFAULT_DISAGGREGATION TRUE
122#define DEFAULT_SIMPLIFYINEQUALITIES TRUE
123#define DEFAULT_NEGATEDCLIQUE TRUE
125#define MAXABSVBCOEF 1e+5
126#define USESUPADDLIFT FALSE
128#define DEFAULT_PRESOLUSEHASHING TRUE
129#define HASHSIZE_KNAPSACKCONS 500
131#define DEFAULT_PRESOLPAIRWISE TRUE
132#define NMINCOMPARISONS 200000
133#define MINGAINPERNMINCOMPARISONS 1e-06
135#define DEFAULT_DUALPRESOLVING TRUE
136#define DEFAULT_DETECTCUTOFFBOUND TRUE
139#define DEFAULT_DETECTLOWERBOUND TRUE
142#define DEFAULT_CLIQUEEXTRACTFACTOR 0.5
143#define MAXCOVERSIZEITERLEWI 1000
145#define DEFAULT_USEGUBS FALSE
146#define GUBCONSGROWVALUE 6
147#define GUBSPLITGNC1GUBS FALSE
148#define DEFAULT_CLQPARTUPDATEFAC 1.5
150#define DEFAULT_UPDATECLIQUEPARTITIONS FALSE
151#define MAXNCLIQUEVARSCOMP 1000000
152#ifdef WITH_CARDINALITY_UPGRADE
153#define DEFAULT_UPGDCARDINALITY FALSE
155#define DEFAULT_COPYTYPEDCONS FALSE
164struct SCIP_ConshdlrData
194 int probtoidxmapsize;
220#ifdef WITH_CARDINALITY_UPGRADE
234 int* cliquepartition;
235 int* negcliquepartition;
242 int ncliqueslastnegpart;
243 int ncliqueslastpart;
247 unsigned int presolvedtiming:5;
248 unsigned int sorted:1;
249 unsigned int cliquepartitioned:1;
250 unsigned int negcliquepartitioned:1;
251 unsigned int merged:1;
252 unsigned int cliquesadded:1;
253 unsigned int varsdeleted:1;
254 unsigned int existmultaggr:1;
331 if( sortkeypair1->key1 < sortkeypair2->key1 )
333 else if( sortkeypair1->key1 > sortkeypair2->key1 )
335 else if( sortkeypair1->key2 < sortkeypair2->key2 )
337 else if( sortkeypair1->key2 > sortkeypair2->key2 )
355 (*eventdata)->cons = cons;
356 (*eventdata)->weight = weight;
382 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
383 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
384 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
385 assert(consdata->nvars == 0 || (consdata->cliquepartition !=
NULL && consdata->negcliquepartition !=
NULL));
387 if( !consdata->sorted )
397 (
void**)consdata->vars,
398 (
void**)consdata->eventdata,
399 consdata->cliquepartition,
400 consdata->negcliquepartition,
403 v = consdata->nvars - 1;
409 while(
w >= 0 && consdata->weights[v] == consdata->weights[
w] )
416 (
void**)(&(consdata->vars[
w+1])),
417 (
void**)(&(consdata->eventdata[
w+1])),
418 &(consdata->cliquepartition[
w+1]),
419 &(consdata->negcliquepartition[
w+1]),
427 if( consdata->cliquepartitioned )
431 for( pos = 0; pos < consdata->nvars; ++pos )
435 if( consdata->cliquepartition[pos] > lastcliquenum )
437 consdata->cliquepartitioned =
FALSE;
440 else if( consdata->cliquepartition[pos] == lastcliquenum )
445 if( consdata->negcliquepartitioned )
449 for( pos = 0; pos < consdata->nvars; ++pos )
453 if( consdata->negcliquepartition[pos] > lastcliquenum )
455 consdata->negcliquepartitioned =
FALSE;
458 else if( consdata->negcliquepartition[pos] == lastcliquenum )
463 consdata->sorted =
TRUE;
469 for(
i = 0;
i < consdata->nvars-1; ++
i )
470 assert(consdata->weights[
i] >= consdata->weights[
i+1]);
488 assert(consdata->nvars == 0 || (consdata->cliquepartition !=
NULL && consdata->negcliquepartition !=
NULL));
491 ispartitionoutdated = (conshdlrdata->updatecliquepartitions && consdata->ncliques > 1
492 &&
SCIPgetNCliques(
scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastpart));
494 if( normalclique && ( !consdata->cliquepartitioned || ispartitionoutdated ) )
497 consdata->cliquepartition, &consdata->ncliques) );
498 consdata->cliquepartitioned =
TRUE;
503 isnegpartitionoutdated = (conshdlrdata->updatecliquepartitions && consdata->nnegcliques > 1
504 &&
SCIPgetNCliques(
scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastnegpart));
506 if( negatedclique && (!consdata->negcliquepartitioned || isnegpartitionoutdated) )
509 consdata->negcliquepartition, &consdata->nnegcliques) );
510 consdata->negcliquepartitioned =
TRUE;
513 assert(!consdata->cliquepartitioned || consdata->ncliques <= consdata->nvars);
514 assert(!consdata->negcliquepartitioned || consdata->nnegcliques <= consdata->nvars);
558 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
559 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
560 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
562 for(
i = 0;
i < consdata->nvars;
i++)
566 eventhdlr, consdata->eventdata[
i], &consdata->eventdata[
i]->filterpos) );
583 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
584 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
585 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
587 for(
i = 0;
i < consdata->nvars;
i++)
590 eventhdlr, consdata->eventdata[
i], consdata->eventdata[
i]->filterpos) );
607 assert(consdata->nvars <= consdata->varssize);
609 if( num > consdata->varssize )
628 consdata->varssize = newsize;
630 assert(num <= consdata->varssize);
646 consdata->weightsum += weightdelta;
649 consdata->onesweightsum += weightdelta;
651 assert(consdata->weightsum >= 0);
652 assert(consdata->onesweightsum >= 0);
674 (*consdata)->vars =
NULL;
675 (*consdata)->weights =
NULL;
676 (*consdata)->nvars = 0;
687 for( v = 0; v <
nvars; ++v )
693 assert( weights[v] >= 0 );
702 constant += weights[v];
706 varsbuffer[k] =
vars[v];
707 weightsbuffer[k] = weights[v];
715 (*consdata)->nvars = k;
729 (*consdata)->varssize = (*consdata)->nvars;
730 (*consdata)->capacity = capacity - constant;
731 (*consdata)->eventdata =
NULL;
732 (*consdata)->cliquepartition =
NULL;
733 (*consdata)->negcliquepartition =
NULL;
734 (*consdata)->row =
NULL;
735 (*consdata)->nlrow =
NULL;
736 (*consdata)->weightsum = 0;
737 (*consdata)->onesweightsum = 0;
738 (*consdata)->ncliques = 0;
739 (*consdata)->nnegcliques = 0;
740 (*consdata)->presolvedtiming = 0;
741 (*consdata)->sorted =
FALSE;
742 (*consdata)->cliquepartitioned =
FALSE;
743 (*consdata)->negcliquepartitioned =
FALSE;
744 (*consdata)->ncliqueslastpart = -1;
745 (*consdata)->ncliqueslastnegpart = -1;
746 (*consdata)->merged =
FALSE;
747 (*consdata)->cliquesadded =
FALSE;
748 (*consdata)->varsdeleted =
FALSE;
749 (*consdata)->existmultaggr =
FALSE;
756 for( v = 0; v < (*consdata)->nvars; v++ )
770 for( v = 0; v < (*consdata)->nvars; ++v )
792 if( (*consdata)->row !=
NULL )
796 if( (*consdata)->nlrow !=
NULL )
800 if( (*consdata)->eventdata !=
NULL )
805 if( (*consdata)->negcliquepartition !=
NULL )
809 if( (*consdata)->cliquepartition !=
NULL )
813 if( (*consdata)->vars !=
NULL )
818 for( v = 0; v < (*consdata)->nvars; v++ )
825 assert( (*consdata)->varssize > 0 );
849 oldweight = consdata->weights[item];
850 weightdiff = newweight - oldweight;
851 consdata->weights[item] = newweight;
856 if( consdata->eventdata !=
NULL )
859 assert(consdata->eventdata[item]->weight == oldweight);
860 consdata->eventdata[item]->weight = newweight;
863 consdata->presolvedtiming = 0;
864 consdata->sorted =
FALSE;
867 if( oldweight < newweight )
869 consdata->cliquesadded =
FALSE;
892 for(
i = 0;
i < consdata->nvars; ++
i )
917 if( consdata->row ==
NULL )
953 if( consdata->nlrow ==
NULL )
959 for(
i = 0;
i < consdata->nvars; ++
i )
963 consdata->nvars, consdata->vars, coefs,
NULL,
997 SCIPdebugMsg(
scip,
"checking knapsack constraint <%s> for feasibility of solution %p (lprows=%u)\n",
1019 for( v = consdata->nvars - 1; v >= 0; --v )
1032 if( normsum > consdata->capacity )
1034 absviol = normsum - consdata->capacity;
1070#define IDX(j,d) ((j)*(intcap)+(d))
1113 int greedymedianpos;
1118 int* allcurrminweight;
1142 for( j = nitems - 1; j >= 0; --j )
1149 if( solval !=
NULL )
1153 if( solitems !=
NULL )
1174 for( j = 0; j < nitems; ++j )
1179 if( weights[j] > capacity )
1181 if( solitems !=
NULL )
1182 nonsolitems[(*nnonsolitems)++] = items[j];
1185 else if( profits[j] <= 0.0 )
1187 if( solitems !=
NULL )
1188 nonsolitems[(*nnonsolitems)++] = items[j];
1191 else if( weights[j] == 0 )
1193 if( solitems !=
NULL )
1194 solitems[(*nsolitems)++] = items[j];
1196 if( solval !=
NULL )
1197 *solval += profits[j];
1202 myweights[nmyitems] = weights[j];
1203 myprofits[nmyitems] = profits[j];
1204 myitems[nmyitems] = items[j];
1207 if( myweights[nmyitems] < minweight )
1208 minweight = myweights[nmyitems];
1211 if( myweights[nmyitems] > maxweight )
1212 maxweight = myweights[nmyitems];
1214 weightsum += myweights[nmyitems];
1221 for( j = 0; j < nmyitems && intprofits; ++j )
1233 if( weightsum > 0 && weightsum <= capacity )
1237 for( j = nmyitems - 1; j >= 0; --j )
1239 if( solitems !=
NULL )
1240 solitems[(*nsolitems)++] = myitems[j];
1242 if( solval !=
NULL )
1243 *solval += myprofits[j];
1249 assert(0 < minweight && minweight <= capacity );
1250 assert(0 < maxweight && maxweight <= capacity);
1257 gcd = myweights[nmyitems - 1];
1258 for( j = nmyitems - 2; j >= 0 && gcd >= 2; --j )
1266 for( j = nmyitems - 1; j >= 0; --j )
1268 myweights[j] /= gcd;
1269 eqweights = eqweights && (myweights[j] == 1);
1277 assert(minweight <= capacity);
1280 if( minweight > capacity / 2 )
1284 SCIPdebugMsg(
scip,
"Only one item fits into knapsack, so take the best.\n");
1289 for( j = nmyitems - 2; j >= 0; --j )
1291 if( myprofits[j] > myprofits[p] )
1296 if( solitems !=
NULL )
1300 solitems[(*nsolitems)++] = myitems[p];
1301 for( j = nmyitems - 1; j >= 0; --j )
1304 nonsolitems[(*nnonsolitems)++] = myitems[j];
1308 if( solval !=
NULL )
1309 *solval += myprofits[p];
1324 if( solitems !=
NULL || solval !=
NULL )
1333 for(
i = capacity - 1;
i >= 0; --
i )
1335 if( solitems !=
NULL )
1336 solitems[(*nsolitems)++] = myitems[
i];
1337 addval += myprofits[
i];
1340 if( solitems !=
NULL )
1343 for(
i = nmyitems - 1;
i >= capacity; --
i )
1344 nonsolitems[(*nnonsolitems)++] = myitems[
i];
1348 if( solval !=
NULL )
1365 for( j = 0; j < nmyitems; ++j )
1367 tempsort[j] = myprofits[j]/((
SCIP_Real) myweights[j]);
1368 realweights[j] = (
SCIP_Real)myweights[j];
1372 (
SCIP_Real)capacity, nmyitems, &greedymedianpos);
1378 greedysolweight = 0;
1379 greedysolvalue = 0.0;
1382 for( j = 0; j < greedymedianpos; ++j )
1384 assert(myweights[j] <= capacity);
1387 greedysolweight += myweights[j];
1388 greedysolvalue += myprofits[j];
1391 assert(0 < greedysolweight && greedysolweight <= capacity);
1392 assert(greedysolvalue > 0.0);
1397 greedyupperbound = greedysolvalue + myprofits[j] * (
SCIP_Real) (capacity - greedysolweight)/((
SCIP_Real) myweights[j]);
1400 if( greedysolweight == capacity ||
SCIPisGE(
scip, greedysolvalue, greedyupperbound) )
1405 if( solitems !=
NULL )
1412 for( l = 0; l < j; ++l )
1413 solitems[(*nsolitems)++] = myitems[l];
1414 for ( ; l < nmyitems; ++l )
1415 nonsolitems[(*nnonsolitems)++] = myitems[l];
1418 if( solval !=
NULL )
1420 assert(greedysolvalue > 0.0);
1421 *solval += greedysolvalue;
1428 capacity -= (minweight - 1);
1431 if( capacity >= INT_MAX )
1438 assert(capacity < INT_MAX);
1440 intcap = (int)capacity;
1443 assert(
sizeof(
size_t) >=
sizeof(
int));
1448 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) )) )
1450 SCIPdebugMsg(
scip,
"Too much memory (%lu) would be consumed.\n", (
unsigned long) (((
size_t)nmyitems) * ((
size_t)intcap) *
sizeof(*optvalues)));
1478 assert(myweights[0] - minweight < INT_MAX);
1479 currminweight = (int) (myweights[0] - minweight);
1480 allcurrminweight[0] = currminweight;
1483 for( d = currminweight; d < intcap; ++d )
1484 optvalues[d] = myprofits[0];
1487 lastitem = nmyitems - 1;
1490 for( j = 1; j < nmyitems; ++j )
1495 intweight = (int)(myweights[j] - minweight);
1496 assert(0 <= intweight && intweight < intcap);
1499 for( d = currminweight; d < intweight && d < intcap; ++d )
1500 optvalues[
IDX(j,d)] = optvalues[
IDX(j-1,d)];
1503 for( d = intweight; d < intcap; ++d )
1506 if( d < currminweight )
1507 optvalues[
IDX(j,d)] = myprofits[j];
1512 if( d - myweights[j] < currminweight )
1513 sumprofit = myprofits[j];
1515 sumprofit = optvalues[
IDX(j-1,(
int)(d-myweights[j]))] + myprofits[j];
1517 optvalues[
IDX(j,d)] =
MAX(sumprofit, optvalues[
IDX(j-1,d)]);
1522 if( intweight < currminweight )
1523 currminweight = intweight;
1525 allcurrminweight[j] = currminweight;
1528 if( intprofits && optvalues[
IDX(j, intcap - 1)] >= greedyupperbound )
1536 if( solitems !=
NULL )
1544 for( j = nmyitems - 1; j > lastitem; --j )
1545 nonsolitems[(*nnonsolitems)++] = myitems[j];
1548 for( j = lastitem; j > 0; --j )
1551 if( d < allcurrminweight[j] )
1559 if( d < allcurrminweight[j-1] || optvalues[
IDX(j,d)] > optvalues[
IDX(j-1,d)] )
1561 solitems[(*nsolitems)++] = myitems[j];
1565 d = (int)(d - myweights[j]);
1569 nonsolitems[(*nnonsolitems)++] = myitems[j];
1573 if( d >= allcurrminweight[j] )
1576 solitems[(*nsolitems)++] = myitems[j];
1581 assert(d < allcurrminweight[j]);
1583 for( ; j >= 0; --j )
1584 nonsolitems[(*nnonsolitems)++] = myitems[j];
1587 assert(*nsolitems + *nnonsolitems == nitems);
1591 if( solval !=
NULL )
1592 *solval += optvalues[
IDX(lastitem, intcap - 1)];
1636 if( solitems !=
NULL )
1641 if( solval !=
NULL )
1647 for( j = nitems - 1; j >= 0; --j )
1649 tempsort[j] = profits[j]/((
SCIP_Real) weights[j]);
1658 for( j = 0; j < nitems && solitemsweight + weights[j] <= capacity; ++j )
1660 if( solitems !=
NULL )
1661 solitems[(*nsolitems)++] = items[j];
1663 if( solval !=
NULL )
1664 (*solval) += profits[j];
1665 solitemsweight += weights[j];
1667 if ( solitems !=
NULL )
1669 for( ; j < nitems; j++ )
1670 nonsolitems[(*nnonsolitems)++] = items[j];
1689 int nnontrivialgubconss;
1692 nnontrivialgubconss = 0;
1717 if( solvals !=
NULL )
1719 gubsolval += solvals[currentvar];
1729 if( solvals !=
NULL )
1738 nnontrivialgubconss++;
1762 (*gubcons)->ngubvars = 0;
1877 assert(oldgubcons != newgubcons);
1894 gubset->
gubvarsidx[replacevar] = oldgubvaridx;
1907 SCIPdebugMsg(
scip,
"deleting empty GUB cons<%d> from current GUB set\n", oldgubcons);
2012 (*gubset)->ngubconss =
nvars;
2013 (*gubset)->nvars =
nvars;
2025 (*gubset)->gubconssidx[
i] =
i;
2026 (*gubset)->gubvarsidx[
i] = 0;
2027 assert((*gubset)->gubconss[
i]->ngubvars == 1);
2030 if( weights[
i] > capacity )
2054 for(
i = (*gubset)->ngubconss-1;
i >= 0; --
i )
2091 for(
i = 0;
i < gubset->
nvars;
i++ )
2098 SCIPdebugMsg(
scip,
" var<%d> should be in GUB<%d> at position<%d>, but stored is var<%d> instead\n",
i,
2099 gubconsidx, gubvaridx, gubset->
gubconss[gubconsidx]->
gubvars[gubvaridx] );
2115 var1negated =
FALSE;
2122 var2negated =
FALSE;
2127 SCIPdebugMsg(
scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n",
i, j,
2130 SCIPdebugMsg(
scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n",
i, j,
2160 int*
const cliquepartition,
2172 int maxncliquevarscomp;
2200 tmpvalues[
i] =
TRUE;
2201 cliquepartition[
i] = -1;
2217 varseq[
nvars-1-nignorevars] =
i;
2223 varseq[nvarsused] =
i;
2239 if( cliquepartition[varseq[
i]] == -1 )
2244 cliquepartition[varseq[
i]] = *ncliques;
2245 cliquevars[0] = tmpvars[varseq[
i]];
2246 cliquevalues[0] = tmpvalues[varseq[
i]];
2255 for( j =
i + 1; j < nvarsused; ++j )
2258 if( cliquepartition[varseq[j]] == -1 &&
SCIPvarIsActive(tmpvars[varseq[j]]) )
2263 for( k = ncliquevars - 1; k >= 0; --k )
2266 cliquevalues[k],
TRUE) )
2273 cliquepartition[varseq[j]] = cliquepartition[varseq[
i]];
2274 cliquevars[ncliquevars] = tmpvars[varseq[j]];
2275 cliquevalues[ncliquevars] = tmpvalues[varseq[j]];
2285 assert(cliquepartition[varseq[
i]] >= 0 && cliquepartition[varseq[
i]] <
i + 1);
2288 if(
i *
nvars > maxncliquevarscomp )
2294 if( cliquepartition[varseq[
i]] == -1 )
2296 cliquepartition[varseq[
i]] = *ncliques;
2321 int* cliquepartition;
2324 int currentgubconsidx;
2347 for(
i = 0;
i < ncliques;
i++ )
2350 gubfirstvar[
i] = -1;
2355 assert(cliquepartition[
i] >= 0);
2357 cliqueidx = cliquepartition[
i];
2362 if( gubfirstvar[cliqueidx] == -1 )
2371 gubfirstvar[cliqueidx] =
i;
2376 assert(gubfirstvar[cliqueidx] >= 0 && gubfirstvar[cliqueidx] <
i);
2381 newgubconsidx = gubset->
gubconssidx[gubfirstvar[cliqueidx]];
2382 assert(newgubconsidx != currentgubconsidx);
2391 GUBsetPrint(
scip, gubset,
vars, solvals);
2482 fixedonesweight = 0;
2485 for( j = 0; j <
nvars; j++ )
2490 if( weights[j] > capacity )
2501 fixedones[nfixedones] = j;
2503 fixedonesweight += weights[j];
2508 fixedzeros[nfixedzeros] = j;
2517 itemsweight += weights[j];
2520 assert(nfixedones + nfixedzeros + nitems ==
nvars - (*ntightened));
2528 *fractional =
FALSE;
2549 for( j = 0; j < nitems; j++ )
2551 transweights[j] = weights[items[j]];
2552 transprofits[j] = 1.0 - solvals[items[j]];
2555 transcapacity = fixedonesweight + itemsweight - capacity - 1;
2560 if( transcapacity < 0 )
2584 for( j = 0; j < nitems; j++ )
2586 transprofits[j] *= weights[items[j]];
2598 noncovervars, covervars, nnoncovervars, ncovervars,
NULL) );
2602 for( j = 0; j < *ncovervars; j++ )
2604 (*coverweight) += weights[covervars[j]];
2608 for( j = 0; j < nfixedones; j++ )
2610 covervars[*ncovervars] = fixedones[j];
2612 (*coverweight) += weights[fixedones[j]];
2616 for( j = 0; j < nfixedzeros; j++ )
2618 noncovervars[*nnoncovervars] = fixedzeros[j];
2621 assert((*ncovervars) + (*nnoncovervars) ==
nvars - (*ntightened));
2622 assert((*coverweight) > capacity);
2659 minweight = weights[covervars[minweightidx]];
2662 for(
i = 0;
i < j;
i++ )
2664 assert(weights[covervars[
i]] > minweight);
2665 if( weights[covervars[
i]] <= minweight )
2670 for(
i = 0;
i < j;
i++ )
2672 assert(coverweight - weights[covervars[
i]] <= capacity);
2673 if( coverweight - weights[covervars[
i]] > capacity )
2709 for( j = 0; j < ncovervars; j++ )
2716 varsC2[*nvarsC2] = covervars[j];
2723 varsC1[*nvarsC1] = covervars[j];
2727 assert((*nvarsC1) + (*nvarsC2) == ncovervars);
2746 assert(*nvarsC1 >= 0 && *nvarsC1 <= 1);
2753 for( j = 0; j < *nvarsC2; j++ )
2754 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
2758 assert(*nvarsC2 == 1 || weights[varsC2[(*nvarsC2)-1]] <= weights[varsC2[(*nvarsC2)-2]]);
2759 while( *nvarsC1 < 2 && *nvarsC2 > 0 )
2761 varsC1[*nvarsC1] = varsC2[(*nvarsC2)-1];
2786 assert(*nvarsC1 >= 0 && *nvarsC1 <= 1);
2793 for( j = 0; j < *nvarsC2; j++ )
2794 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
2798 assert(*nvarsC2 == 1 || weights[varsC2[(*nvarsC2)-1]] <= weights[varsC2[(*nvarsC2)-2]]);
2799 varsC1[*nvarsC1] = varsC2[(*nvarsC2)-1];
2829 assert(nnoncovervars >= 0);
2840 for( j = 0; j < nnoncovervars; j++ )
2845 varsR[*nvarsR] = noncovervars[j];
2852 varsF[*nvarsF] = noncovervars[j];
2856 assert((*nvarsF) + (*nvarsR) == nnoncovervars);
2903 for( j = 0; j < nvarsF; j++ )
2905 sortkeypairsF[j] = &(sortkeypairsFstore[j]);
2906 sortkeypairsF[j]->key1 = solvals[varsF[j]];
2907 sortkeypairsF[j]->key2 = (
SCIP_Real) weights[varsF[j]];
2913 for( j = 0; j < nvarsC2; j++ )
2914 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
2919 for( j = 0; j < nvarsR; j++ )
2920 sortkeysR[j] = (
SCIP_Real) weights[varsR[j]];
2970 int* ngubconscapexceed,
2979 int* nC1varsingubcons;
2987 int nvarsprocessed = 0;
3059 for( j = 0; j < nvarsC1; j++ )
3062 sortkeysC1[j] = (
SCIP_Real) weights[varsC1[j]];
3075 for( j = 0; j < nvarsF; j++ )
3087 for( j = 0; j < nvarsC2; j++ )
3090 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
3102 for( j = 0; j < nvarsR; j++ )
3105 sortkeysR[j] = (
SCIP_Real) weights[varsR[j]];
3138 sortkeypairsGFC1[
i] = &(sortkeypairsGFC1store[
i]);
3139 sortkeypairsGFC1[
i]->key1 = 0.0;
3140 sortkeypairsGFC1[
i]->key2 = 0.0;
3146 *ngubconscapexceed = 0;
3147 *maxgubvarssize = 0;
3160 for(
i = 0;
i < nvarsC1;
i++ )
3162 int nvarsC1capexceed;
3164 nvarsC1capexceed = 0;
3176 targetvar = gubset->
gubconss[gubconsidx]->
gubvars[nC1varsingubcons[gubconsidx]];
3178 nC1varsingubcons[gubconsidx]++;
3192 gubconswithF =
FALSE;
3210 gubconswithF =
TRUE;
3212 sortkeypairsGFC1[*ngubconsGFC1]->key1 += 1.0;
3214 if( solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3215 sortkeypairsGFC1[*ngubconsGFC1]->key2 = solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]];
3226 gubconsGC1[*ngubconsGC1] = gubconsidx;
3281 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3286 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3295 for(
i = 0;
i < nvarsC2;
i++ )
3311 gubconsGC2[*ngubconsGC2] = gubconsidx;
3327 for(
i = 0;
i < nvarsF;
i++ )
3360 sortkeypairsGFC1[*ngubconsGFC1]->key1 += 1.0;
3362 if( solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3363 sortkeypairsGFC1[*ngubconsGFC1]->key2 = solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]];
3368 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3379 for(
i = 0;
i < nvarsR;
i++ )
3405 gubconsGR[*ngubconsGR] = gubconsidx;
3412 assert(nvarsprocessed == nvarsC1 + nvarsC2 + nvarsF + nvarsR);
3415 (*ngubconscapexceed) =
ngubconss - (ngubconsGOC1 + (*ngubconsGC2) + (*ngubconsGFC1) + (*ngubconsGR));
3416 assert(*ngubconscapexceed >= 0);
3429 assert(check == *ngubconscapexceed);
3434 if( (*ngubconsGFC1) > 0 )
3436 SCIPsortDownPtrInt((
void**)sortkeypairsGFC1, gubconsGFC1, compSortkeypairs, (*ngubconsGFC1));
3456 int* minweightssize,
3465 assert(*minweightslen >= 0);
3467 assert(*minweightssize >= 0);
3469 if( newlen > *minweightssize )
3476 *minweightssize = newsize;
3478 assert(newlen <= *minweightssize);
3481 for( j = *minweightslen; j < newlen; ++j )
3483 *minweightslen = newlen;
3542 assert(nvarsM1 >= 0 && nvarsM1 <=
nvars - ntightened);
3543 assert(nvarsM2 >= 0 && nvarsM2 <=
nvars - ntightened);
3544 assert(nvarsF >= 0 && nvarsF <=
nvars - ntightened);
3545 assert(nvarsR >= 0 && nvarsR <=
nvars - ntightened);
3546 assert(nvarsM1 + nvarsM2 + nvarsF + nvarsR ==
nvars - ntightened);
3553 minweightssize = nvarsM1 + 1;
3564 for( j = 0; j < nvarsM1; j++ )
3566 assert(liftcoefs[varsM1[j]] == 0);
3567 liftcoefs[varsM1[j]] = 1;
3568 sortkeys[j] = (
SCIP_Real) (weights[varsM1[j]]);
3569 (*cutact) += solvals[varsM1[j]];
3581 for(
w = 1;
w <= nvarsM1;
w++ )
3582 minweights[
w] = minweights[
w-1] + weights[varsM1[
w-1]];
3583 minweightslen = nvarsM1 + 1;
3586 fixedonesweight = 0;
3587 for( j = 0; j < nvarsM2; j++ )
3588 fixedonesweight += weights[varsM2[j]];
3589 assert(fixedonesweight >= 0);
3595 for( j = 0; j < nvarsF; j++ )
3603 weight = weights[liftvar];
3611 if( capacity - fixedonesweight - weight < 0 )
3619 else if( minweights[*liftrhs] <= capacity - fixedonesweight - weight )
3632 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
3634 right = (*liftrhs) + 1;
3635 while( left < right - 1 )
3637 middle = (left + right) / 2;
3638 assert(0 <= middle && middle < minweightslen);
3639 if( minweights[middle] <= capacity - fixedonesweight - weight )
3644 assert(left == right - 1);
3645 assert(0 <= left && left < minweightslen);
3646 assert(minweights[left] <= capacity - fixedonesweight - weight );
3647 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight - weight);
3655 liftcoef = (*liftrhs) - z;
3656 liftcoefs[liftvar] = liftcoef;
3657 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
3664 (*cutact) += liftcoef * solvals[liftvar];
3678 for(
w = minweightslen - 1;
w >= 0;
w-- )
3683 min =
MIN(minweights[
w], weight);
3684 minweights[
w] = min;
3689 min =
MIN(minweights[
w], minweights[
w - liftcoef] + weight);
3690 minweights[
w] = min;
3694 assert(minweights[0] == 0);
3697 for( j = 0; j < nvarsM2; j++ )
3707 liftvar = varsM2[j];
3708 weight = weights[liftvar];
3717 right = minweightslen;
3718 while( left < right - 1 )
3720 middle = (left + right) / 2;
3721 assert(0 <= middle && middle < minweightslen);
3722 if( minweights[middle] <= capacity - fixedonesweight + weight )
3727 assert(left == right - 1);
3728 assert(0 <= left && left < minweightslen);
3729 assert(minweights[left] <= capacity - fixedonesweight + weight );
3730 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight + weight);
3737 liftcoef = z - (*liftrhs);
3738 liftcoefs[liftvar] = liftcoef;
3742 fixedonesweight -= weight;
3745 (*liftrhs) += liftcoef;
3746 assert(*liftrhs >= alpha0);
3753 (*cutact) += liftcoef * solvals[liftvar];
3767 for(
w = minweightslen - 1;
w >= 0;
w-- )
3772 min =
MIN(minweights[
w], weight);
3773 minweights[
w] = min;
3778 min =
MIN(minweights[
w], minweights[
w - liftcoef] + weight);
3779 minweights[
w] = min;
3783 assert(fixedonesweight == 0);
3784 assert(*liftrhs >= alpha0);
3787 for( j = 0; j < nvarsR; j++ )
3795 weight = weights[liftvar];
3799 assert(capacity - weight >= 0);
3800 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - weight);
3805 if( minweights[*liftrhs] <= capacity - weight )
3818 right = (*liftrhs) + 1;
3819 while( left < right - 1)
3821 middle = (left + right) / 2;
3822 assert(0 <= middle && middle < minweightslen);
3823 if( minweights[middle] <= capacity - weight )
3828 assert(left == right - 1);
3829 assert(0 <= left && left < minweightslen);
3830 assert(minweights[left] <= capacity - weight );
3831 assert(left == minweightslen - 1 || minweights[left+1] > capacity - weight);
3839 liftcoef = (*liftrhs) - z;
3840 liftcoefs[liftvar] = liftcoef;
3841 assert(liftcoef >= 0 && liftcoef <= *liftrhs);
3848 (*cutact) += liftcoef * solvals[liftvar];
3854 for(
w = *liftrhs;
w >= 0;
w-- )
3859 min =
MIN(minweights[
w], weight);
3860 minweights[
w] = min;
3865 min =
MIN(minweights[
w], minweights[
w - liftcoef] + weight);
3866 minweights[
w] = min;
3893 return (val1 + val2);
3915 assert(unfinished[w2] == 0);
3916 for( w1 = 0; w1 < minweightslen; w1++ )
3917 minweights[w1] = finished[w1];
3920 for( w2 = 1; w2 < minweightslen; w2++ )
3925 for( w1 = 0; w1 < minweightslen - w2; w1++ )
3930 if( temp <= minweights[w1+w2] )
3931 minweights[w1+w2] = temp;
3955 int ngubconscapexceed,
4027 assert(ngubconsGC1 >= 0 && ngubconsGC1 <=
ngubconss - ngubconscapexceed);
4028 assert(ngubconsGC2 >= 0 && ngubconsGC2 <=
ngubconss - ngubconscapexceed);
4029 assert(ngubconsGFC1 >= 0 && ngubconsGFC1 <=
ngubconss - ngubconscapexceed);
4030 assert(ngubconsGR >= 0 && ngubconsGR <=
ngubconss - ngubconscapexceed);
4036 minweightssize = ngubconsGC1+1;
4055 for( j = 0; j < ngubconsGC1; j++ )
4059 gubconsGOC1[ngubconsGOC1] = gubconsGC1[j];
4065 gubconsGNC1[ngubconsGNC1] = gubconsGC1[j];
4076 (*cutact) += solvals[
varidx];
4080 assert(ngubconsGOC1 + ngubconsGFC1 + ngubconsGC2 + ngubconsGR ==
ngubconss - ngubconscapexceed);
4081 assert(ngubconsGOC1 + ngubconsGNC1 == ngubconsGC1);
4102 assert(ngubconsGOC1 <= ngubconsGC1);
4104 for(
w = 1;
w <= ngubconsGOC1;
w++ )
4106 liftgubconsidx = gubconsGOC1[
w-1];
4117 finished[
w] = finished[
w-1] + min;
4130 for(
w = ngubconsGOC1+1;
w <= ngubconsGC1;
w++ )
4138 assert(ngubconsGNC1 <= ngubconsGC1);
4140 for(
w = 1;
w <= ngubconsGNC1;
w++ )
4142 liftgubconsidx = gubconsGNC1[
w-1];
4153 unfinished[
w] = unfinished[
w-1] + min;
4166 for(
w = ngubconsGNC1 + 1;
w <= ngubconsGC1;
w++ )
4174 assert(ngubconsGOC1 + ngubconsGNC1 == ngubconsGC1);
4176 for(
w = 1;
w <= ngubconsGC1;
w++ )
4178 liftgubconsidx = gubconsGC1[
w-1];
4190 minweights[
w] = minweights[
w-1] + min;
4203 minweightslen = ngubconsGC1 + 1;
4206 fixedonesweight = 0;
4207 for( j = 0; j < ngubconsGC2; j++ )
4215 fixedonesweight += weights[
varidx];
4217 assert(fixedonesweight >= 0);
4223 for( j = 0; j < ngubconsGFC1; j++ )
4225 liftgubconsidx = gubconsGFC1[j];
4236 assert(ngubconsGNC1 > 0);
4249 weight = weights[liftgubvars[0]];
4251 weightdiff2 = unfinished[ngubconsGNC1] - weight;
4253 for(
w = ngubconsGNC1-1;
w >= 1;
w-- )
4255 weightdiff1 = weightdiff2;
4256 weightdiff2 = unfinished[
w] - weight;
4258 if( unfinished[
w] < weightdiff1 )
4259 unfinished[
w] = weightdiff1;
4267 assert(minweights[0] == 0);
4288 weight = weights[liftvar];
4291 assert(capacity - weight >= 0);
4296 liftgubvars[nliftgubvars] = liftvar;
4302 if( capacity - fixedonesweight - weight < 0 )
4310 else if( minweights[*liftrhs] <= capacity - fixedonesweight - weight )
4319 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
4321 right = (*liftrhs) + 1;
4322 while( left < right - 1 )
4324 middle = (left + right) / 2;
4325 assert(0 <= middle && middle < minweightslen);
4326 if( minweights[middle] <= capacity - fixedonesweight - weight )
4331 assert(left == right - 1);
4332 assert(0 <= left && left < minweightslen);
4333 assert(minweights[left] <= capacity - fixedonesweight - weight);
4334 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight - weight);
4342 liftcoef = (*liftrhs) - z;
4343 liftcoefs[liftvar] = liftcoef;
4344 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
4347 (*cutact) += liftcoef * solvals[liftvar];
4350 sumliftcoef += liftcoefs[liftvar];
4356 assert(nliftgubvars > nliftgubC1);
4362 if( sumliftcoef == 0 )
4366 weight = weights[liftgubvars[0]];
4371 for(
w = minweightslen-1;
w >= 1;
w-- )
4376 finished[
w] =
MIN(finished[
w], tmpval);
4379 minweights[
w] =
MIN(minweights[
w], tmpval);
4394 tmplen = minweightslen;
4395 tmpsize = minweightssize;
4397 tmplen = minweightslen;
4398 tmpsize = minweightssize;
4412 for(
w = minweightslen-1;
w >= 0;
w-- )
4417 for( k = 0; k < nliftgubvars; k++ )
4419 liftcoef = liftcoefs[liftgubvars[k]];
4420 weight = weights[liftgubvars[k]];
4424 minfinished =
MIN(finished[
w], weight);
4425 minminweight =
MIN(minweights[
w], weight);
4427 finished[
w] = minfinished;
4428 minweights[
w] = minminweight;
4437 minfinished =
MIN(finished[
w], tmpval);
4440 minminweight =
MIN(minweights[
w], tmpval);
4442 finished[
w] = minfinished;
4443 minweights[
w] = minminweight;
4447 assert(minweights[0] == 0);
4449 assert(ngubconsGNC1 == 0);
4456 for( j = 0; j < ngubconsGC2; j++ )
4458 liftgubconsidx = gubconsGC2[j];
4466 weight = weights[liftvar];
4476 right = minweightslen;
4477 while( left < right - 1 )
4479 middle = (left + right) / 2;
4480 assert(0 <= middle && middle < minweightslen);
4481 if( minweights[middle] <= capacity - fixedonesweight + weight )
4486 assert(left == right - 1);
4487 assert(0 <= left && left < minweightslen);
4488 assert(minweights[left] <= capacity - fixedonesweight + weight);
4489 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - fixedonesweight + weight);
4496 liftcoef = z - (*liftrhs);
4497 liftcoefs[liftvar] = liftcoef;
4501 fixedonesweight -= weight;
4504 (*liftrhs) += liftcoef;
4505 assert(*liftrhs >= alpha0);
4512 (*cutact) += liftcoef * solvals[liftvar];
4526 for(
w = minweightslen - 1;
w >= 0;
w-- )
4530 min =
MIN(minweights[
w], weight);
4531 minweights[
w] = min;
4540 min =
MIN(minweights[
w], tmpval);
4541 minweights[
w] = min;
4545 assert(fixedonesweight == 0);
4546 assert(*liftrhs >= alpha0);
4549 for( j = 0; j < ngubconsGR; j++ )
4551 liftgubconsidx = gubconsGR[j];
4563 weight = weights[liftvar];
4566 assert(capacity - weight >= 0);
4567 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - weight);
4572 liftgubvars[nliftgubvars] = liftvar;
4578 if( minweights[*liftrhs] <= capacity - weight )
4587 right = (*liftrhs) + 1;
4588 while( left < right - 1 )
4590 middle = (left + right) / 2;
4591 assert(0 <= middle && middle < minweightslen);
4592 if( minweights[middle] <= capacity - weight )
4597 assert(left == right - 1);
4598 assert(0 <= left && left < minweightslen);
4599 assert(minweights[left] <= capacity - weight);
4600 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - weight);
4607 liftcoef = (*liftrhs) - z;
4608 liftcoefs[liftvar] = liftcoef;
4609 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
4612 (*cutact) += liftcoef * solvals[liftvar];
4615 sumliftcoef += liftcoefs[liftvar];
4620 assert(nliftgubvars >= 1);
4623 if( sumliftcoef == 0 )
4629 for(
w = *liftrhs;
w >= 0;
w-- )
4631 for( k = 0; k < nliftgubvars; k++ )
4633 liftcoef = liftcoefs[liftgubvars[k]];
4634 weight = weights[liftgubvars[k]];
4638 min =
MIN(minweights[
w], weight);
4639 minweights[
w] = min;
4648 min =
MIN(minweights[
w], tmpval);
4649 minweights[
w] = min;
4653 assert(minweights[0] == 0);
4720 assert(nnoncovervars >= 0 && nnoncovervars <=
nvars - ntightened);
4721 assert(ncovervars + nnoncovervars ==
nvars - ntightened);
4738 for( j = 0; j < ncovervars; j++ )
4740 assert(liftcoefs[covervars[j]] == 0.0);
4741 liftcoefs[covervars[j]] = 1.0;
4742 sortkeys[j] = (
SCIP_Real) weights[covervars[j]];
4743 (*cutact) += solvals[covervars[j]];
4748 lambda = coverweight - capacity;
4752 maxweightsums[0] = 0;
4753 for(
h = 1;
h <= ncovervars;
h++ )
4755 maxweightsums[
h] = maxweightsums[
h-1] + weights[covervars[
h-1]];
4756 intervalends[
h-1] = maxweightsums[
h] - lambda;
4757 rhos[
h-1] =
MAX(0, weights[covervars[
h-1]] - weights[covervars[0]] + lambda);
4761 for( j = 0; j < nnoncovervars; j++ )
4762 sortkeys[j] = (
SCIP_Real) (weights[noncovervars[j]]);
4767 for( j = 0; j < nnoncovervars; j++ )
4773 liftvar = noncovervars[j];
4774 weight = weights[liftvar];
4776 while( intervalends[
h] < weight )
4783 if( weight <= intervalends[
h-1] + rhos[
h] )
4787 tmp1 = (
SCIP_Real) (intervalends[
h-1] + rhos[
h] - weight);
4789 liftcoef =
h - ( tmp1 / tmp2 );
4796 assert(liftcoefs[liftvar] == 0.0);
4797 liftcoefs[liftvar] = liftcoef;
4800 (*cutact) += liftcoef * solvals[liftvar];
4828 int* nonmincovervars,
4830 int nnonmincovervars,
4865 assert(nvarsC1 + nvarsC2 == nmincovervars);
4866 assert(nmincovervars > 0);
4870 if( nvarsC1 < 2 && nvarsC2 > 0)
4875 assert(nvarsC2 == 0 || nvarsC1 >= 1);
4882 assert(nvarsF + nvarsR == nnonmincovervars);
4883 assert(nvarsC1 + nvarsC2 + nvarsF + nvarsR ==
nvars - ntightened);
4886 if( gubset ==
NULL )
4905 varsF, varsR, nvarsC1, nvarsC2, nvarsF, nvarsR, nvarsC1 - 1, liftcoefs, &cutact, &liftrhs) );
4942 nvarsC2, nvarsF, nvarsR, gubconsGC1, gubconsGC2, gubconsGFC1, gubconsGR, &ngubconsGC1, &ngubconsGC2,
4943 &ngubconsGFC1, &ngubconsGR, &nconstightened, &maxgubvarssize) );
4959 gubconsGC2, gubconsGFC1, gubconsGR, ngubconsGC1, ngubconsGC2, ngubconsGFC1, ngubconsGR,
4960 MIN(nvarsC1 - 1, ngubconsGC1), liftcoefs, &cutact, &liftrhs, maxgubvarssize) );
4985 else if ( sepa !=
NULL )
4998 assert(nvarsC1 + nvarsC2 + nvarsF + nvarsR ==
nvars - ntightened);
4999 for( j = 0; j < nvarsC1; j++ )
5003 for( j = 0; j < nvarsC2; j++ )
5005 if( liftcoefs[varsC2[j]] > 0 )
5010 for( j = 0; j < nvarsF; j++ )
5012 if( liftcoefs[varsF[j]] > 0 )
5017 for( j = 0; j < nvarsR; j++ )
5019 if( liftcoefs[varsR[j]] > 0 )
5062 int* nonfeassetvars,
5064 int nnonfeassetvars,
5099 assert(nvarsT1 + nvarsT2 == nfeassetvars);
5102 if( nvarsT1 == 0 && nvarsT2 > 0)
5107 assert(nvarsT2 == 0 || nvarsT1 > 0);
5114 assert(nvarsF + nvarsR == nnonfeassetvars);
5115 assert(nvarsT1 + nvarsT2 + nvarsF + nvarsR ==
nvars - ntightened);
5134 SCIP_CALL(
sequentialUpAndDownLifting(
scip,
vars,
nvars, ntightened, weights, capacity, solvals, varsT1, varsT2, varsF, varsR,
5135 nvarsT1, nvarsT2, nvarsF, nvarsR, nvarsT1, liftcoefs, &cutact, &liftrhs) );
5152 else if ( sepa !=
NULL )
5165 assert(nvarsT1 + nvarsT2 + nvarsF + nvarsR ==
nvars - ntightened);
5166 for( j = 0; j < nvarsT1; j++ )
5170 for( j = 0; j < nvarsT2; j++ )
5172 if( liftcoefs[varsT2[j]] > 0 )
5177 for( j = 0; j < nvarsF; j++ )
5179 if( liftcoefs[varsF[j]] > 0 )
5184 for( j = 0; j < nvarsR; j++ )
5186 if( liftcoefs[varsR[j]] > 0 )
5229 int* nonmincovervars,
5231 int nnonmincovervars,
5260 nonmincovervars, nmincovervars, nnonmincovervars, mincoverweight, realliftcoefs, &cutact) );
5261 liftrhs = nmincovervars - 1;
5279 else if ( sepa !=
NULL )
5292 assert(nmincovervars + nnonmincovervars ==
nvars - ntightened);
5293 for( j = 0; j < nmincovervars; j++ )
5297 for( j = 0; j < nnonmincovervars; j++ )
5359 assert(*nnoncovervars >= 0);
5361 assert(*coverweight > 0);
5362 assert(*coverweight > capacity);
5366 nsortkeypairs = *ncovervars;
5375 assert(*ncovervars == nsortkeypairs);
5378 for( j = 0; j < *ncovervars; j++ )
5381 sortkeypairssorted[j] = sortkeypairs[j];
5383 sortkeypairs[j]->key1 = solvals[covervars[j]];
5384 sortkeypairs[j]->key2 = (
SCIP_Real) weights[covervars[j]];
5389 for( j = 0; j < *ncovervars; j++ )
5392 sortkeypairssorted[j] = sortkeypairs[j];
5394 sortkeypairs[j]->key1 = (solvals[covervars[j]] - 1.0) / ((
SCIP_Real) weights[covervars[j]]);
5395 sortkeypairs[j]->key2 = (
SCIP_Real) (-weights[covervars[j]]);
5398 SCIPsortPtrInt((
void**)sortkeypairssorted, covervars, compSortkeypairs, *ncovervars);
5402 minweight = weights[covervars[minweightidx]];
5403 for( j = 1; j < *ncovervars; j++ )
5405 if( weights[covervars[j]] <= minweight )
5408 minweight = weights[covervars[minweightidx]];
5411 assert(minweightidx >= 0 && minweightidx < *ncovervars);
5412 assert(minweight > 0 && minweight <= *coverweight);
5416 while( j < *ncovervars && ((*coverweight) - minweight > capacity) )
5418 assert(minweightidx >= j);
5422 if( (*coverweight) - weights[covervars[j]] <= capacity )
5429 noncovervars[*nnoncovervars] = covervars[j];
5433 (*coverweight) -= weights[covervars[j]];
5434 for( k = j; k < (*ncovervars) - 1; k++ )
5435 covervars[k] = covervars[k+1];
5439 if( j == minweightidx )
5442 minweight = weights[covervars[minweightidx]];
5443 for( k = 1; k < *ncovervars; k++ )
5445 if( weights[covervars[k]] <= minweight )
5448 minweight = weights[covervars[minweightidx]];
5451 assert(minweight > 0 && minweight <= *coverweight);
5452 assert(minweightidx >= 0 && minweightidx < *ncovervars);
5456 assert(minweightidx > j);
5461 assert((*coverweight) > capacity);
5462 assert((*coverweight) - minweight <= capacity);
5465 for( j = nsortkeypairs-1; j >= 0; j-- )
5512 assert(*nnoncovervars >= 0);
5514 assert(*coverweight > 0);
5515 assert(*coverweight > capacity);
5516 assert(*ncovervars + *nnoncovervars ==
nvars - ntightened);
5531 for( j = 0; j < *ncovervars; j++ )
5533 sortkeys[j] = solvals[covervars[j]];
5539 for( j = 0; j < *ncovervars; j++ )
5541 sortkeys[j] = (solvals[covervars[j]] - 1.0) / ((
SCIP_Real) weights[covervars[j]]);
5549 while( *ncovervars >= 2 )
5552 noncovervars[*nnoncovervars] = covervars[0];
5556 (*coverweight) -= weights[covervars[0]];
5557 for( k = 0; k < (*ncovervars) - 1; k++ )
5558 covervars[k] = covervars[k+1];
5561 assert(*ncovervars + *nnoncovervars ==
nvars - ntightened);
5562 if( (*coverweight) <= capacity )
5565 covervars, noncovervars, *ncovervars, *nnoncovervars,
sol,
cutoff, ncuts) );
5637 SCIPdebugMsg(
scip,
"separate cuts for knapsack constraint originated by cons <%s>:\n",
5668 modtransused =
TRUE;
5670 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5672 assert(!coverfound || !fractional || ncovervars + nnoncovervars ==
nvars - ntightened);
5677 SCIPdebugMsg(
scip,
" LMCI1-GUB terminated by no variable with fractional LP value.\n");
5692 &nnoncovervars, &coverweight, modtransused) );
5699 solvals, covervars, noncovervars, ncovervars, nnoncovervars,
sol, gubset,
cutoff, ncuts) );
5707 solvals, covervars, noncovervars, ncovervars, nnoncovervars,
sol,
NULL,
cutoff, ncuts) );
5727 modtransused =
TRUE;
5729 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5730 assert(!coverfound || !fractional || ncovervars + nnoncovervars ==
nvars - ntightened);
5743 &nnoncovervars, &coverweight, modtransused) );
5747 solvals, covervars, noncovervars, ncovervars, nnoncovervars,
sol,
NULL,
cutoff, ncuts) );
5754 solvals, covervars, noncovervars, ncovervars, nnoncovervars, coverweight,
sol,
cutoff, ncuts) );
5769 modtransused =
FALSE;
5771 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5773 assert(!coverfound || ncovervars + nnoncovervars ==
nvars - ntightened);
5782 SCIP_CALL(
getFeasibleSet(
scip, cons, sepa,
vars,
nvars, ntightened, weights, capacity, solvals, covervars, noncovervars,
5783 &ncovervars, &nnoncovervars, &coverweight, modtransused,
sol,
cutoff, ncuts) );
5855 if( conshdlr ==
NULL )
5857 noknapsackconshdlr =
TRUE;
5865 noknapsackconshdlr =
FALSE;
5868 usegubs = conshdlrdata->usegubs;
5875 if( conshdlrdata->reals1size == 0 )
5878 conshdlrdata->reals1size = 1;
5879 conshdlrdata->reals1[0] = 0.0;
5882 assert(conshdlrdata->reals1size > 0);
5888 if( conshdlrdata->reals1size < nbinvars )
5890 int oldsize = conshdlrdata->reals1size;
5892 conshdlrdata->reals1size = nbinvars;
5894 BMSclearMemoryArray(&(conshdlrdata->reals1[oldsize]), conshdlrdata->reals1size - oldsize);
5896 binvals = conshdlrdata->reals1;
5900 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
5902 assert(binvals[tmp] == 0);
5920 for(
i = 0;
i < nknapvars;
i++ )
5937 SCIPdebugMsg(
scip,
"Solution value %.15g <%s> outside domain [0.0, 1.0]\n",
5943 if( !noknapsackconshdlr )
5952 else if( valscale * knapvals[
i] > 0.0 )
5971 for( j = 0; j < nvlb; j++ )
5982 SCIPdebugMsg(
scip,
"variable bound <%s>[%g,%g] >= %g<%s>[%g,%g] + %g implies local cutoff\n",
6002 if( bestlbtype == -1 )
6004 rhs -= valscale * knapvals[
i] * bestlbsol;
6005 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with lower bound %.15g (rhs=%.15g)\n",
6011 rhs -= valscale * knapvals[
i] * dvlb[bestlbtype];
6017 if( !noknapsackconshdlr )
6024 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable lower bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6040 assert(valscale * knapvals[
i] < 0.0);
6051 for( j = 0; j < nvub; j++ )
6062 SCIPdebugMsg(
scip,
"variable bound <%s>[%g,%g] <= %g<%s>[%g,%g] + %g implies local cutoff\n",
6082 if( bestubtype == -1 )
6084 rhs -= valscale * knapvals[
i] * bestubsol;
6085 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with upper bound %.15g (rhs=%.15g)\n",
6091 rhs -= valscale * knapvals[
i] * dvub[bestubtype];
6097 if( !noknapsackconshdlr )
6104 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable upper bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6133 rhs = rhs * intscalar;
6138 for(
i = 0;
i < nbinvars;
i++ )
6168 consvals[nconsvars] = val;
6169 consvars[nconsvars] =
var;
6187 for(
i = 0;
i < nconsvars; ++
i )
6194 capacity, rhs, act, minact, maxact);
6198 if( minact > capacity )
6200 SCIPdebugMsg(
scip,
"minactivity of knapsack relaxation implies local cutoff\n");
6205 if( maxact > capacity )
6208 SCIP_CALL(
SCIPseparateKnapsackCuts(
scip, cons, sepa, consvars, nconsvars, consvals, capacity,
sol, usegubs,
cutoff, ncuts) );
6214 if( noknapsackconshdlr)
6221 for( --tmp; tmp >= 0; --tmp)
6224 binvals[tmpindices[tmp]] = 0;
6270 consdata->capacity,
sol, usegubs,
cutoff, ncuts) );
6293 if( consdata->row !=
NULL )
6302 consdata->capacity -= weight;
6313 consdata->vars[consdata->nvars] =
var;
6314 consdata->weights[consdata->nvars] = weight;
6332 conshdlrdata->eventhdlr, consdata->eventdata[consdata->nvars-1],
6333 &consdata->eventdata[consdata->nvars-1]->filterpos) );
6336 consdata->existmultaggr =
TRUE;
6340 consdata->presolvedtiming = 0;
6341 consdata->cliquesadded =
FALSE;
6347 consdata->sorted =
FALSE;
6348 consdata->cliquepartitioned =
FALSE;
6349 consdata->negcliquepartitioned =
FALSE;
6350 consdata->merged =
FALSE;
6371 var = consdata->vars[pos];
6376 if( consdata->row !=
NULL )
6392 conshdlrdata->eventhdlr, consdata->eventdata[pos], consdata->eventdata[pos]->filterpos) );
6396 consdata->presolvedtiming = 0;
6397 consdata->sorted = (consdata->sorted && pos == consdata->nvars - 1);
6404 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
6405 consdata->weights[pos] = consdata->weights[consdata->nvars-1];
6406 if( consdata->eventdata !=
NULL )
6407 consdata->eventdata[pos] = consdata->eventdata[consdata->nvars-1];
6413 if( consdata->cliquepartitioned )
6418 if( consdata->cliquepartition[consdata->nvars - 1] != consdata->nvars - 1 )
6422 oldcliqenum = consdata->cliquepartition[pos];
6423 consdata->cliquepartition[pos] = consdata->cliquepartition[consdata->nvars-1];
6426 if( consdata->cliquepartition[pos] > pos )
6427 consdata->cliquepartitioned =
FALSE;
6431 int cliquenumbefore;
6435 if( oldcliqenum > consdata->cliquepartition[pos] )
6437 for(
i = 0;
i < consdata->nvars; ++
i )
6438 if( oldcliqenum == consdata->cliquepartition[
i] )
6440 else if( oldcliqenum < consdata->cliquepartition[
i] )
6442 consdata->cliquepartitioned =
FALSE;
6448 if(
i == consdata->nvars )
6449 --(consdata->ncliques);
6453 else if( oldcliqenum < consdata->cliquepartition[pos] )
6455 cliquenumbefore = consdata->cliquepartition[pos] - 1;
6456 for(
i = pos - 1;
i >= 0 &&
i >= cliquenumbefore && consdata->cliquepartition[
i] < cliquenumbefore; --
i );
6458 if(
i < cliquenumbefore )
6459 consdata->cliquepartitioned =
FALSE;
6462 else if( pos == consdata->nvars - 1)
6464 cliquenumbefore = consdata->cliquepartition[pos];
6465 for(
i = pos - 1;
i >= 0 &&
i >= cliquenumbefore && consdata->cliquepartition[
i] < cliquenumbefore; --
i );
6467 if(
i < cliquenumbefore )
6468 --(consdata->ncliques);
6474 --(consdata->ncliques);
6477 if( consdata->negcliquepartitioned )
6479 assert(consdata->negcliquepartition !=
NULL);
6482 if( consdata->negcliquepartition[consdata->nvars-1] != consdata->nvars - 1 )
6486 oldcliqenum = consdata->negcliquepartition[pos];
6487 consdata->negcliquepartition[pos] = consdata->negcliquepartition[consdata->nvars-1];
6490 if( consdata->negcliquepartition[pos] > pos )
6491 consdata->negcliquepartitioned =
FALSE;
6495 int cliquenumbefore;
6499 if( oldcliqenum > consdata->negcliquepartition[pos] )
6501 for(
i = 0;
i < consdata->nvars; ++
i )
6502 if( oldcliqenum == consdata->negcliquepartition[
i] )
6504 else if( oldcliqenum < consdata->negcliquepartition[
i] )
6506 consdata->negcliquepartitioned =
FALSE;
6512 if(
i == consdata->nvars )
6513 --(consdata->nnegcliques);
6517 else if( oldcliqenum < consdata->negcliquepartition[pos] )
6519 cliquenumbefore = consdata->negcliquepartition[pos] - 1;
6520 for(
i = pos - 1;
i >= 0 &&
i >= cliquenumbefore && consdata->negcliquepartition[
i] < cliquenumbefore; --
i );
6522 if(
i < cliquenumbefore )
6523 consdata->negcliquepartitioned =
FALSE;
6526 else if( pos == consdata->nvars - 1)
6528 cliquenumbefore = consdata->negcliquepartition[pos];
6529 for(
i = pos - 1;
i >= 0 &&
i >= cliquenumbefore && consdata->negcliquepartition[
i] < cliquenumbefore; --
i );
6531 if(
i < cliquenumbefore )
6532 --(consdata->nnegcliques);
6538 --(consdata->nnegcliques);
6541 --(consdata->nvars);
6559 for( v = consdata->nvars-1; v >= 0; --v )
6561 if( consdata->weights[v] == 0 )
6591 for(
i = 0;
i < nconss;
i++ )
6596 if( consdata->varsdeleted )
6599 for( v = consdata->nvars - 1; v >= 0; --v )
6606 consdata->varsdeleted =
FALSE;
6634 if( consdata->merged )
6637 if( consdata->nvars <= 1 )
6639 consdata->merged =
TRUE;
6643 assert(consdata->vars !=
NULL || consdata->nvars == 0);
6647 consdata->cliquepartition, consdata->negcliquepartition, SCIPvarCompActiveAndNegated, consdata->nvars);
6650 consdata->sorted =
FALSE;
6652 v = consdata->nvars - 1;
6665 var1 = consdata->vars[v];
6675 var2 = consdata->vars[prev];
6688 if( negated1 == negated2 )
6691 consdataChgWeight(consdata, prev, consdata->weights[v] + consdata->weights[prev]);
6697 else if( consdata->weights[v] == consdata->weights[prev] )
6700 consdata->capacity -= consdata->weights[v];
6706 else if( consdata->weights[v] < consdata->weights[prev] )
6708 consdata->capacity -= consdata->weights[v];
6709 consdataChgWeight(consdata, prev, consdata->weights[prev] - consdata->weights[v]);
6710 assert(consdata->weights[prev] > 0);
6715 consdata->capacity -= consdata->weights[prev];
6717 assert(consdata->weights[v] > 0);
6720 if( consdata->nvars != v )
6724 if( prev == 0 || (var1 != consdata->vars[prev - 1] && var1 !=
SCIPvarGetNegatedVar(consdata->vars[prev - 1])) )
6728 consdata->cliquesadded =
FALSE;
6735 consdata->cliquesadded =
FALSE;
6741 consdata->merged =
TRUE;
6744 if( consdata->onesweightsum > consdata->capacity )
6793 nvars = consdata->nvars;
6794 vars = consdata->vars;
6806 for( v = 0; v <
nvars; ++v )
6849 items, solitems, nonsolitems, &nsolitems, &nnonsolitems, &solval, &success) );
6856 for( v = 0; v < nsolitems; ++v )
6861 SCIPdebugMsg(
scip,
"variable <%s> only locked up in knapsack constraints: dual presolve <%s>[%.15g,%.15g] >= 1.0\n",
6869 for( v = 0; v < nnonsolitems; ++v )
6874 SCIPdebugMsg(
scip,
"variable <%s> has no down locks: dual presolve <%s>[%.15g,%.15g] <= 0.0\n",
6925 nvars = consdata->nvars;
6940 vars = consdata->vars;
6947 for( v = 0; v <
nvars && applicable; ++v )
6969 weight = (
SCIP_Real)consdata->weights[v];
6976 scale = weight / -
objval;
7005 cutoffbound = (consdata->capacity - offset) / scale;
7007 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
7015 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
7041 lowerbound = (consdata->capacity - offset) / scale;
7043 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a lower bound <%g>\n",
7061 int* cliquestartposs,
7068 int* cliquepartition;
7085 origweights = consdata->weights;
7086 origvars = consdata->vars;
7087 norigvars = consdata->nvars;
7090 assert(origweights !=
NULL || norigvars == 0);
7092 if( norigvars == 0 )
7095 if( usenegatedclique )
7097 assert(consdata->negcliquepartitioned);
7099 cliquepartition = consdata->negcliquepartition;
7100 ncliques = consdata->nnegcliques;
7104 assert(consdata->cliquepartitioned);
7106 cliquepartition = consdata->cliquepartition;
7107 ncliques = consdata->ncliques;
7118 for( v = norigvars - 1; v >= 0; --v )
7120 assert(0 <= cliquepartition[v] && cliquepartition[v] < ncliques);
7121 ++(cliquecount[cliquepartition[v]]);
7135 for(
c = 0;
c < ncliques; ++
c )
7145 cliquestartposs[
c] = nextpos;
7148 nextpos += cliquecount[
c];
7151 assert(nextpos == norigvars);
7152 cliquestartposs[
c] = nextpos;
7155 for( v = 0; v < norigvars; ++v )
7157 *(varpointers[cliquepartition[v]]) = origvars[v];
7158 ++(varpointers[cliquepartition[v]]);
7159 *(weightpointers[cliquepartition[v]]) = origweights[v];
7160 ++(weightpointers[cliquepartition[v]]);
7163 for( v = 0; v < norigvars; ++v )
7196 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
7205 if ( consdata->onesweightsum > consdata->capacity )
7216 consdata->existmultaggr =
FALSE;
7219 while( v < consdata->
nvars )
7223 var = consdata->vars[v];
7229 consdata->capacity -= consdata->weights[v];
7231 consdata->cliquesadded =
FALSE;
7246 weight = consdata->weights[v];
7299 assert((aggrvars !=
NULL && aggrscalars !=
NULL) || naggrvars == 0);
7303 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-integral value for weight*aggrconst = %g\n", weight*aggrconst);
7311 for(
i = naggrvars - 1;
i >= 0; --
i )
7318 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-binary %svariable <%s> with bounds [%g,%g]\n",
7324 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-integral value for weight*aggrscalars = %g\n", weight*aggrscalars[
i]);
7349 if( consdata->capacity < 0 )
7359 else if( repvar !=
var )
7371 assert(consdata->onesweightsum == 0);
7414 int* cliquestartposs;
7442 for(
i = 0;
i < consdata->nvars && consdata->merged; ++
i )
7448 usenegatedclique = usenegatedclique && consdata->merged;
7453 cliquestartposs =
NULL;
7454 secondmaxweights =
NULL;
7456 nvars = consdata->nvars;
7462 localminweightsum = 0;
7471 if( usenegatedclique &&
nvars > 0 )
7479 nnegcliques = consdata->nnegcliques;
7482 if( nnegcliques ==
nvars )
7485 usenegatedclique =
FALSE;
7501 for(
c = 0;
c < nnegcliques; ++
c )
7503 cliqueendposs[
c] = cliquestartposs[
c+1] - 1;
7504 assert(cliqueendposs[
c] - cliquestartposs[
c] >= 0);
7518 if( nnegcliques -
c ==
nvars -
i )
7520 minweightsum += localminweightsum;
7521 localminweightsum = 0;
7529 if( cliquestartposs[
c] ==
i )
7533 minweightsum += localminweightsum;
7534 localminweightsum = 0;
7553 assert(myweights[
i] <= myweights[cliquestartposs[
c - 1]]);
7560 cliquestartposs[
c - 1] =
i;
7566 if( secondmaxweights[
c - 1] == 0 )
7567 secondmaxweights[
c - 1] = myweights[
i];
7569 localminweightsum += myweights[
i];
7576 for( v = cliquestartposs[
c - 1]; v < cliquestartposs[
c]; ++v )
7613 localminweightsum = 0;
7615 i = cliqueendposs[
c - 1];
7624 minweightsum += localminweightsum;
7630 if( !(*
cutoff) && consdata->capacity >= minweightsum + consdata->onesweightsum )
7635 for(
c = 0;
c < nnegcliques; ++
c )
7639 int endvarposclique;
7640 int startvarposclique;
7643 assert(nnegcliques == consdata->nnegcliques);
7648 endvarposclique = cliqueendposs[
c];
7649 startvarposclique = cliquestartposs[
c];
7651 maxvar = myvars[startvarposclique];
7657 maxcliqueweight = myweights[startvarposclique];
7658 maxvarfixed =
FALSE;
7663 if( consdata->onesweightsum + minweightsum + (maxcliqueweight - secondmaxweights[
c]) > consdata->capacity )
7666 SCIP_Longint oldonesweightsum = consdata->onesweightsum;
7668 assert(maxcliqueweight >= secondmaxweights[
c]);
7674 assert(consdata->onesweightsum == oldonesweightsum);
7683 else if( nnegcliques -
c ==
nvars - startvarposclique )
7693 else if( consdata->onesweightsum + minweightsum + (maxcliqueweight - consdata->weights[
nvars - 1]) <= consdata->capacity )
7697 for(
i = endvarposclique;
i > startvarposclique; --
i )
7706 assert(maxcliqueweight >= myweights[
i]);
7707 assert(
i == endvarposclique || myweights[
i] >= myweights[
i+1]);
7715 if( maxvarfixed || consdata->onesweightsum + minweightsum - myweights[
i] + maxcliqueweight > consdata->capacity )
7718 SCIP_Longint oldonesweightsum = consdata->onesweightsum;
7722 assert(consdata->onesweightsum == oldonesweightsum + myweights[
i]);
7731 minweightsum -= myweights[
i];
7732 assert(minweightsum >= 0);
7740 for( ;
i > startvarposclique; --
i )
7743 SCIP_Bool exceedscapacity = consdata->onesweightsum + minweightsum - myweights[
i] + maxcliqueweight > consdata->capacity;
7745 assert(
i == endvarposclique || myweights[
i] >= myweights[
i+1]);
7746 assert(varisfixed || !exceedscapacity);
7758 assert(consdata->negcliquepartitioned || minweightsum == 0);
7762 assert(usenegatedclique || minweightsum == 0);
7764 if( consdata->capacity < minweightsum + consdata->onesweightsum )
7767 consdata->onesweightsum, consdata->capacity);
7782 for(
i = 0;
i <
nvars && weight <= consdata->capacity;
i++ )
7787 weight += consdata->weights[
i];
7798 if( !usenegatedclique )
7800 assert(consdata->sorted);
7801 residualcapacity = consdata->capacity - consdata->onesweightsum;
7804 for(
i = 0;
i <
nvars && consdata->weights[
i] > residualcapacity; ++
i )
7813 assert(consdata->onesweightsum + consdata->weights[
i] > consdata->capacity);
7828 SCIP_Longint unfixedweightsum = consdata->onesweightsum;
7835 unfixedweightsum += consdata->weights[
i];
7838 if( unfixedweightsum > consdata->capacity )
7844 SCIPconsGetName(cons), consdata->weightsum, unfixedweightsum, consdata->capacity);
7873 assert(consdata->nvars > 1);
7876 if( consdata->nvars == 2 )
7957 assert(0 < frontsum && frontsum < consdata->weightsum);
7958 assert(0 < splitpos && splitpos < consdata->
nvars);
7963 vars = consdata->vars;
7964 weights = consdata->weights;
7965 nvars = consdata->nvars;
7966 capacity = consdata->capacity;
7973 assert(weights[
w] <= weights[
w-1]);
7977 if( consdata->nvars - 1 == splitpos )
7980 assert(frontsum + weights[splitpos] > capacity);
7983 if( consdata->weightsum - weights[splitpos] <= capacity )
7991 for(
w =
nvars - 1;
w > splitpos; --
w )
7993 consdata->capacity -= weights[
w];
7999 *nchgcoefs += (
nvars - splitpos);
8003 for( ;
w >= 0 && gcd > 1; --
w )
8011 for(
w = splitpos;
w >= 0; --
w )
8015 (*nchgcoefs) +=
nvars;
8017 consdata->capacity /= gcd;
8025 for(
w = consdata->nvars - 1;
w > 0; --
w )
8026 assert(weights[
w] <= weights[
w - 1]);
8033 else if( conshdlrdata->disaggregation && frontsum + weights[splitpos + 1] <= capacity )
8039 len =
nvars - (splitpos + 1);
8056 for(
w = 0;
w < len; ++
w )
8058 assert(clqpart[
w] >= 0 && clqpart[
w] <=
w);
8059 if( clqpart[
w] == cliquenum )
8061 maxactduetoclq += weights[
w + splitpos + 1];
8069 if( frontsum + maxactduetoclq <= capacity )
8075 assert(maxactduetoclq < weights[splitpos]);
8082 for(
c = 0;
c < nclq; ++
c )
8085 for(
w = 0;
w < len; ++
w )
8087 if( clqpart[
w] ==
c )
8089 clqvars[nclqvars] =
vars[
w + splitpos + 1];
8117 for(
w =
nvars - 1;
w > splitpos; --
w )
8122 consdata->capacity -= maxactduetoclq;
8123 assert(frontsum <= consdata->capacity);
8129 weights = consdata->weights;
8133 for( ;
w >= 0 && gcd > 1; --
w )
8141 for(
w = splitpos;
w >= 0; --
w )
8145 (*nchgcoefs) +=
nvars;
8147 consdata->capacity /= gcd;
8158 for(
w = consdata->nvars - 1;
w > 0; --
w )
8159 assert(weights[
w] <= weights[
w - 1]);
8210 assert(consdata->nvars >= 2);
8211 assert(consdata->weightsum > consdata->capacity);
8213 vars = consdata->vars;
8214 weights = consdata->weights;
8215 nvars = consdata->nvars;
8216 capacity = consdata->capacity;
8220 for( v = 0; v <
nvars && sum + weights[v] <= capacity; ++v )
8238 assert(consdata->nvars > 1);
8251 assert(weights == consdata->weights);
8253 assert(capacity == consdata->capacity);
8261 if( consdata->cliquepartition[v] < v )
8269 maxactduetoclqfront = 0;
8271 clqpart = consdata->cliquepartition;
8277 assert(clqpart[
w] >= 0 && clqpart[
w] <=
w);
8278 if( clqpart[
w] == cliquenum )
8280 if( maxactduetoclqfront + weights[
w] <= capacity )
8282 maxactduetoclqfront += weights[
w];
8288 sumfront += weights[
w];
8302 assert(maxactduetoclqfront <= capacity);
8306 ncliques = consdata->ncliques;
8311 for(
c = 0;
c < ncliques; ++
c )
8316 if( clqpart[
w] ==
c )
8318 clqvars[nclqvars] =
vars[
w];
8383 assert(consdata->onesweightsum == 0);
8384 assert(consdata->weightsum > consdata->capacity);
8385 assert(consdata->nvars >= 1);
8390 gcd = consdata->weights[consdata->nvars-1];
8391 for(
i = consdata->nvars-2;
i >= 0 && gcd >= 2; --
i )
8403 for(
i = 0;
i < consdata->nvars; ++
i )
8407 consdata->capacity /= gcd;
8408 (*nchgcoefs) += consdata->nvars;
8413 for(
i = consdata->nvars - 1;
i > 0; --
i )
8414 assert(consdata->weights[
i] <= consdata->weights[
i - 1]);
8416 consdata->sorted =
TRUE;
8475 oldnchgsides = *nchgsides;
8480 assert(consdata->weightsum > consdata->capacity);
8481 assert(consdata->nvars >= 2);
8482 assert(consdata->sorted);
8485 assert(consdata->merged);
8487 nvars = consdata->nvars;
8488 weights = consdata->weights;
8489 capacity = consdata->capacity;
8491 oldnchgcoefs = *nchgcoefs;
8494 if( weights[
nvars - 1] + weights[
nvars - 2] > capacity )
8522 if( consdata->weightsum - weights[
nvars - 1] <= consdata->capacity )
8532 if( consdata->weightsum - capacity > weights[0] + weights[1] )
8553 while( v <
nvars && weights[v] + weights[
nvars - 1] > capacity )
8561 while( v <
nvars && exceedsum <= capacity )
8563 exceedsum += weights[v];
8568 if( exceedsum > capacity )
8579 for( v = 0; v < vbig; ++v )
8581 if( weights[v] > newweight )
8589 for( ; v <
nvars; ++v )
8591 if( weights[v] > 1 )
8598 consdata->capacity = newweight;
8604 for( v =
nvars - 1; v > 0; --v )
8605 assert(weights[v] <= weights[v-1]);
8616 int nexceed = v - vbig;
8622 exceedsumback += weights[
w];
8629 if( exceedsumback > capacity )
8634 assert(exceedsumback - weights[
nvars - 1] <= capacity);
8637 for( v = 0; v < vbig; ++v )
8639 if( weights[v] > newweight )
8647 for( ; v <
nvars; ++v )
8649 if( weights[v] > 1 )
8656 consdata->capacity = newweight;
8662 for( v =
nvars - 1; v > 0; --v )
8663 assert(weights[v] <= weights[v-1]);
8692 for( v = 0; v < vbig; ++v )
8693 resweightsum -= weights[v];
8695 assert(exceedsum == resweightsum);
8700 for( v = 0; v < vbig; ++v )
8702 if( weights[v] > newweight )
8710 for( ; v <
nvars; ++v )
8712 if( weights[v] > 1 )
8719 consdata->capacity = newweight;
8725 for( v =
nvars - 1; v > 0; --v )
8726 assert(weights[v] <= weights[v-1]);
8734 dualcapacity = consdata->weightsum - capacity;
8744 while( weights[v] > dualcapacity )
8746 reductionsum += (weights[v] - dualcapacity);
8754 while( v <
nvars && weights[v] == dualcapacity )
8762 if( v >=
nvars - 1 )
8765 if( v ==
nvars - 1 )
8779 if( weights[
nvars - 1] + weights[
nvars - 2] >= dualcapacity )
8793 if( v > 0 && weights[
nvars - 2] > 1 )
8798 for(
w = 0;
w < v; ++
w )
8800 if( weights[
w] > 2 )
8808 assert(weights[v - 1] == 2);
8816 if( weights[
w] > 1 )
8824 (*nchgcoefs) += ncoefchg;
8827 consdata->capacity = (-2 + v * 2 +
nvars - v);
8828 assert(consdata->capacity > 0);
8829 assert(weights[0] <= consdata->capacity);
8830 assert(consdata->weightsum > consdata->capacity);
8858 while( weights[v] > newweight )
8860 reductionsum += (weights[v] - newweight);
8865 (*nchgcoefs) += (v - startv);
8868 while( weights[v] == newweight )
8874 restsumweights += weights[
w];
8877 restsumweights = consdata->weightsum;
8879 if( restsumweights < dualcapacity )
8897 for( ;
w >= 0; --
w )
8898 assert(weights[
w] == dualcapacity);
8923 if( weights[
w] > 1 )
8935 for( ;
w >= startv; --
w )
8937 if( weights[
w] > newweight )
8943 assert(weights[
w] == newweight);
8949 for( ;
w >= 0; --
w )
8951 if( weights[
w] > newweight )
8957 assert(weights[
w] == newweight);
8962 if( consdata->capacity > newcap )
8964 consdata->capacity = newcap;
8968 assert(consdata->capacity == newcap);
8980 assert(weights[
w] <= weights[
w - 1]);
8987 while( end >= 0 && weights[end] == weights[end + 1] )
8999 if( 2 * weights[end] > dualcapacity )
9005 restsumweights += weights[
w];
9007 if( restsumweights * 2 <= dualcapacity )
9010 while( v < end && restsumweights + weights[v] >= dualcapacity )
9017 if( (dualcapacity & 1) == 0 )
9019 newweight = dualcapacity / 2;
9022 for( ; v <= end; ++v )
9024 if( weights[v] > newweight )
9026 reductionsum += (weights[v] - newweight);
9041 for(
w = 0;
w < v; ++
w )
9046 newweight = dualcapacity;
9048 for( ; v <= end; ++v )
9050 reductionsum += (2 * weights[v] - newweight);
9059 (*nchgcoefs) +=
nvars;
9062 consdata->capacity *= 2;
9077 for( k = 0; k < 4; ++k )
9083 sumcoef = weights[
nvars - 1] + weights[
nvars - 2];
9087 sumcoef = weights[
nvars - 1] + weights[
nvars - 3];
9094 sumcoef = weights[
nvars - 1] + weights[
nvars - 4];
9098 sumcoefcase =
FALSE;
9099 sumcoef = weights[
nvars - 2] + weights[
nvars - 3];
9118 minweight = weights[end];
9119 while( minweight <= sumcoef )
9121 newweight = dualcapacity - minweight;
9127 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9129 reductionsum += (weights[v] - newweight);
9134 (*nchgcoefs) += (v - startv);
9137 while( weights[v] + minweight == dualcapacity )
9145 while( end >= 0 && weights[end] == weights[end + 1] )
9151 minweight = weights[end];
9158 if( sumcoef < minweight )
9160 minweight = sumcoef;
9161 newweight = dualcapacity - minweight;
9166 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9168 reductionsum += (weights[v] - newweight);
9173 (*nchgcoefs) += (v - startv);
9176 while( weights[v] + minweight == dualcapacity )
9187 if( 2 * weights[end] > dualcapacity )
9193 restsumweights += weights[
w];
9195 if( restsumweights * 2 <= dualcapacity )
9198 while( v < end && restsumweights + weights[v] >= dualcapacity )
9205 if( (dualcapacity & 1) == 0 )
9207 newweight = dualcapacity / 2;
9210 for( ; v <= end; ++v )
9212 if( weights[v] > newweight )
9214 reductionsum += (weights[v] - newweight);
9229 for(
w = 0;
w < v; ++
w )
9234 newweight = dualcapacity;
9236 for( ; v <= end; ++v )
9238 reductionsum += (2 * weights[v] - newweight);
9247 (*nchgcoefs) +=
nvars;
9250 consdata->capacity *= 2;
9259 if( 2 * sumcoef > dualcapacity )
9267 if( reductionsum > 0 )
9271 consdata->capacity -= reductionsum;
9274 assert(consdata->weightsum - dualcapacity == consdata->capacity);
9276 assert(weights[0] <= consdata->capacity);
9283 assert(weights[
w] <= weights[
w - 1]);
9286 if( oldnchgcoefs < *nchgcoefs )
9295 assert(oldnchgcoefs == *nchgcoefs);
9296 assert(oldnchgsides == *nchgsides);
9331 nvars = consdata->nvars;
9336 assert(consdata->capacity >= 0);
9347 vars = consdata->vars;
9348 weights = consdata->weights;
9349 capacity = consdata->capacity;
9353 while( v <
nvars && weights[v] > capacity )
9376 for( --v; v >= 0; --v )
9385 assert(weights == consdata->weights);
9387 assert(consdata->sorted);
9388 assert(weights[0] <= capacity);
9467 assert(consdata->merged);
9471 assert(consdata->capacity >= 0);
9493 weights = consdata->weights;
9494 nvars = consdata->nvars;
9498 for( v =
nvars - 1; v > 0; --v )
9499 assert(weights[v] <= weights[v-1]);
9503 gcd = weights[
nvars - 1];
9504 for( v =
nvars - 2; v >= 0 && gcd > 1; --v )
9512 for( v =
nvars - 1; v >= 0; --v )
9516 (*nchgcoefs) +=
nvars;
9518 consdata->capacity /= gcd;
9527 for( v =
nvars - 1; v > 0; --v )
9528 assert(weights[v] <= weights[v-1]);
9537 vars = consdata->vars;
9538 weights = consdata->weights;
9539 nvars = consdata->nvars;
9542 if( weights[
nvars - 1] == 1 && weights[
nvars - 2] == 1 )
9549 while( weights[v] == consdata->capacity )
9556 if( v ==
nvars - 1 )
9568 for( v =
nvars - 1; v >= offsetv; --v )
9570 weight = weights[v];
9598 if( v ==
nvars - 2 )
9604 if( candpos == v + 1 && candpos2 == v + 2 )
9631 assert(((candpos >= offsetv) || (candpos == -1 && offsetv > 0)) && candpos <
nvars);
9634 rest = consdata->capacity % gcd;
9644 consdata->capacity -= rest;
9648 for( v = 0; v < offsetv; ++v )
9653 *nchgcoefs += offsetv;
9658 restweight = weights[candpos] % gcd;
9660 assert(restweight < gcd);
9663 if( restweight > rest )
9664 newweight = weights[candpos] - restweight + gcd;
9666 newweight = weights[candpos] - restweight;
9670 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);
9675 if( newweight == 0 && offsetv > 0 )
9681 consdata->capacity -= rest;
9685 for( v = 0; v < offsetv; ++v )
9690 *nchgcoefs += offsetv;
9693 if( newweight == 0 )
9709 assert(consdata->weights == weights);
9713 for( v =
nvars - 1; v >= 0; --v )
9717 (*nchgcoefs) +=
nvars;
9719 consdata->capacity /= gcd;
9724 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));
9726 while(
nvars >= 2 );
9764 assert(*nzeroitems <= *zeroitemssize);
9768 nzeros = *nzeroitems;
9771 if( nzeros == *zeroitemssize )
9778 SCIPdebugMsg(
scip,
"memory limit of %d bytes reached in knapsack preprocessing - abort collecting zero items\n",
9780 *memlimitreached =
TRUE;
9783 *zeroitemssize *= 2;
9788 assert(nzeros < *zeroitemssize);
9790 if( *memlimitreached )
9791 *memlimitreached =
FALSE;
9794 (*zeroitems)[nzeros] = knapsackidx;
9795 (*nextidxs)[nzeros] = firstidxs[value][probindex];
9796 if( firstidxs[value][probindex] == 0 )
9798 liftcands[value][nliftcands[value]] = probindex;
9799 ++nliftcands[value];
9801 firstidxs[value][probindex] = nzeros;
9803 zeroweightsums[value][probindex] += knapsackweight;
9808#define MAX_CLIQUELENGTH 50
9870 assert(consdata->weightsum > consdata->capacity);
9871 assert(consdata->nvars > 0);
9872 assert(consdata->merged);
9874 nvars = consdata->nvars;
9902 assert(conshdlrdata->ints1size > 0);
9903 assert(conshdlrdata->ints2size > 0);
9904 assert(conshdlrdata->longints1size > 0);
9905 assert(conshdlrdata->longints2size > 0);
9911 if( conshdlrdata->ints1size < nbinvars )
9913 int oldsize = conshdlrdata->ints1size;
9915 conshdlrdata->ints1size = nbinvars;
9919 if( conshdlrdata->ints2size < nbinvars )
9921 int oldsize = conshdlrdata->ints2size;
9923 conshdlrdata->ints2size = nbinvars;
9927 if( conshdlrdata->longints1size < nbinvars )
9929 int oldsize = conshdlrdata->longints1size;
9931 conshdlrdata->longints1size = nbinvars;
9933 BMSclearMemoryArray(&(conshdlrdata->longints1[oldsize]), conshdlrdata->longints1size - oldsize);
9935 if( conshdlrdata->longints2size < nbinvars )
9937 int oldsize = conshdlrdata->longints2size;
9939 conshdlrdata->longints2size = nbinvars;
9941 BMSclearMemoryArray(&(conshdlrdata->longints2[oldsize]), conshdlrdata->longints2size - oldsize);
9944 firstidxs[0] = conshdlrdata->ints1;
9945 firstidxs[1] = conshdlrdata->ints2;
9946 zeroweightsums[0] = conshdlrdata->longints1;
9947 zeroweightsums[1] = conshdlrdata->longints2;
9951 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
9953 assert(firstidxs[0][tmp] == 0);
9954 assert(firstidxs[1][tmp] == 0);
9955 assert(zeroweightsums[0][tmp] == 0);
9956 assert(zeroweightsums[1][tmp] == 0);
9969 assert(conshdlrdata->bools1size > 0);
9970 assert(conshdlrdata->bools2size > 0);
9976 if( conshdlrdata->bools1size < nbinvars )
9978 int oldsize = conshdlrdata->bools1size;
9980 conshdlrdata->bools1size = nbinvars;
9982 BMSclearMemoryArray(&(conshdlrdata->bools1[oldsize]), conshdlrdata->bools1size - oldsize);
9984 if( conshdlrdata->bools2size < nbinvars )
9986 int oldsize = conshdlrdata->bools2size;
9988 conshdlrdata->bools2size = nbinvars;
9990 BMSclearMemoryArray(&(conshdlrdata->bools2[oldsize]), conshdlrdata->bools2size - oldsize);
9993 zeroiteminserted[0] = conshdlrdata->bools1;
9994 zeroiteminserted[1] = conshdlrdata->bools2;
9998 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
10000 assert(zeroiteminserted[0][tmp] == 0);
10001 assert(zeroiteminserted[1][tmp] == 0);
10015 memlimitreached =
FALSE;
10016 for(
i = 0;
i < consdata->nvars && !memlimitreached; ++
i )
10029 var = consdata->vars[
i];
10030 weight = consdata->weights[
i];
10034 assert(0 <= varprobindex && varprobindex < nbinvars);
10037 zeroweightsums[!value][varprobindex] += weight;
10038 tmpboolindices3[tmp3] = !value;
10039 tmpindices3[tmp3] = varprobindex;
10049 assert(0 <= probindex && probindex < nbinvars);
10051 implvalue = !value;
10054 assert( !zeroiteminserted[implvalue][probindex] );
10056 if( firstidxs[implvalue][probindex] == 0 )
10058 tmpboolindices2[tmp2] = implvalue;
10059 tmpindices2[tmp2] = probindex;
10063 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue,
i, weight,
10064 &memlimitreached) );
10065 zeroiteminserted[implvalue][probindex] =
TRUE;
10066 tmpboolindices[tmp] = implvalue;
10067 tmpindices[tmp] = probindex;
10074 for( j = 0; j < ncliques && !memlimitreached; ++j )
10090 for( k = ncliquevars - 1; k >= 0; --k )
10095 if(
var == cliquevars[k] )
10099 if( probindex == -1 )
10102 assert(0 <= probindex && probindex < nbinvars);
10103 implvalue = cliquevalues[k];
10106 if( !zeroiteminserted[implvalue][probindex] )
10108 if( firstidxs[implvalue][probindex] == 0 )
10110 tmpboolindices2[tmp2] = implvalue;
10111 tmpindices2[tmp2] = probindex;
10116 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue,
i, weight,
10117 &memlimitreached) );
10118 zeroiteminserted[implvalue][probindex] =
TRUE;
10119 tmpboolindices[tmp] = implvalue;
10120 tmpindices[tmp] = probindex;
10123 if( memlimitreached )
10129 for( --tmp; tmp >= 0; --tmp)
10130 zeroiteminserted[tmpboolindices[tmp]][tmpindices[tmp]] =
FALSE;
10135 assert(consdata->sorted);
10138 assert(conshdlrdata->bools3size > 0);
10144 if( conshdlrdata->bools3size < consdata->nvars )
10146 int oldsize = conshdlrdata->bools3size;
10148 conshdlrdata->bools3size = consdata->nvars;;
10150 BMSclearMemoryArray(&(conshdlrdata->bools3[oldsize]), conshdlrdata->bools3size - oldsize);
10153 cliqueused = conshdlrdata->bools3;
10157 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10158 assert(cliqueused[tmp] == 0);
10161 maxcliqueweightsum = 0;
10165 for(
i = 0;
i < consdata->nvars; ++
i )
10167 cliquenum = consdata->cliquepartition[
i];
10168 assert(0 <= cliquenum && cliquenum < consdata->
nvars);
10170 if( !cliqueused[cliquenum] )
10172 maxcliqueweightsum += consdata->weights[
i];
10173 cliqueused[cliquenum] =
TRUE;
10174 tmpindices[tmp] = cliquenum;
10179 for( --tmp; tmp >= 0; --tmp)
10180 cliqueused[tmp] =
FALSE;
10182 assert(conshdlrdata->bools4size > 0);
10188 if( conshdlrdata->bools4size < consdata->nvars )
10190 int oldsize = conshdlrdata->bools4size;
10192 conshdlrdata->bools4size = consdata->nvars;
10197 itemremoved = conshdlrdata->bools4;
10201 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10202 assert(itemremoved[tmp] == 0);
10213 for( val = 0; val < 2 && addweightsum < consdata->capacity; ++val )
10215 for(
i = 0;
i < nliftcands[val] && addweightsum < consdata->capacity; ++
i )
10224 probindex = liftcands[val][
i];
10225 assert(0 <= probindex && probindex < nbinvars);
10228 if( firstidxs[val][probindex] == 0
10229 || maxcliqueweightsum - zeroweightsums[val][probindex] + addweightsum >= consdata->capacity )
10233 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10235 assert(0 < idx && idx < nzeroitems);
10236 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10237 itemremoved[zeroitems[idx]] =
TRUE;
10241 cliqueweightsum = addweightsum;
10242 for( j = 0; j < consdata->nvars; ++j )
10244 cliquenum = consdata->cliquepartition[j];
10245 assert(0 <= cliquenum && cliquenum < consdata->
nvars);
10246 if( !itemremoved[j] )
10248 if( !cliqueused[cliquenum] )
10250 cliqueweightsum += consdata->weights[j];
10251 cliqueused[cliquenum] =
TRUE;
10252 tmpindices[tmp] = cliquenum;
10256 if( cliqueweightsum >= consdata->capacity )
10262 if( cliqueweightsum < consdata->capacity )
10268 assert(naddvars < 2*nbinvars);
10269 var = binvars[probindex];
10274 weight = consdata->capacity - cliqueweightsum;
10275 addvars[naddvars] =
var;
10276 addweights[naddvars] = weight;
10277 addweightsum += weight;
10285 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10287 assert(0 < idx && idx < nzeroitems);
10288 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10289 itemremoved[zeroitems[idx]] =
FALSE;
10292 for( --tmp; tmp >= 0; --tmp)
10293 cliqueused[tmpindices[tmp]] =
FALSE;
10298 for( --tmp3; tmp3 >= 0; --tmp3)
10299 zeroweightsums[tmpboolindices3[tmp3]][tmpindices3[tmp3]] = 0;
10302 for( --tmp2; tmp2 >= 0; --tmp2)
10304 zeroweightsums[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10305 firstidxs[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10309 for(
i = 0;
i < naddvars; ++
i )
10313 *nchgcoefs += naddvars;
10421 assert(consdata->onesweightsum == 0);
10422 assert(consdata->weightsum > consdata->capacity);
10423 assert(consdata->nvars > 0);
10434 assert(consdata->merged);
10439 for(
i = 0;
i < consdata->nvars; ++
i )
10443 weight = consdata->weights[
i];
10444 if( consdata->weightsum - weight < consdata->capacity )
10446 newweight = consdata->weightsum - consdata->capacity;
10448 consdata->capacity -= (weight - newweight);
10451 assert(!consdata->sorted);
10454 consdata->capacity + (weight-newweight), consdata->capacity);
10460 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10464 if( consdata->weightsum <= consdata->capacity )
10468 while( pos < consdata->
nvars && consdata->weights[pos] == consdata->capacity )
10472 weights = consdata->weights;
10473 nvars = consdata->nvars;
10474 capacity = consdata->capacity;
10477 pos <
nvars && weights[pos] + weights[pos + 1] > capacity )
10484 for( k = 0; k < 4; ++k )
10486 newweight = capacity - sumcoef;
10492 sumcoef = weights[
nvars - 1];
10493 backpos =
nvars - 1;
10496 sumcoef = weights[
nvars - 2];
10497 backpos =
nvars - 2;
10502 sumcoefcase =
TRUE;
10503 sumcoef = weights[
nvars - 3];
10504 backpos =
nvars - 3;
10508 sumcoefcase =
FALSE;
10509 sumcoef = weights[
nvars - 1] + weights[
nvars - 2];
10510 backpos =
nvars - 2;
10519 sumcoef = weights[
nvars - 4];
10520 backpos =
nvars - 4;
10524 sumcoef = weights[
nvars - 1] + weights[
nvars - 2];
10525 backpos =
nvars - 2;
10530 sumcoef = weights[
nvars - 3];
10531 backpos =
nvars - 3;
10536 if( backpos <= pos )
10540 maxweight = weights[pos];
10542 while( 2 * maxweight > capacity && maxweight + sumcoef > capacity )
10544 assert(newweight > weights[pos]);
10554 maxweight = weights[pos];
10556 if( backpos <= pos )
10559 (*nchgcoefs) += (pos - startpos);
10562 while( pos <
nvars && weights[pos] + sumcoef == capacity )
10573 if( pos + 1 == backpos && weights[pos] > sumcoef &&
10574 ((k == 0) || (k == 1 && weights[
nvars - 1] + sumcoef + weights[pos] > capacity)) )
10576 newweight = capacity - sumcoef;
10577 assert(newweight > weights[pos]);
10587 if( backpos <= pos )
10596 && consdata->nvars - pos <= MAX_USECLIQUES_SIZE && consdata->
nvars >= 2 && pos > 0
10597 && (
SCIP_Longint)consdata->nvars - pos <= consdata->capacity
10598 && consdata->weights[pos - 1] == consdata->capacity
10599 && ( pos == consdata->nvars || consdata->weights[pos] == 1 ) )
10613 if( pos == consdata->nvars )
10635 len = consdata->nvars - pos;
10646 for(
w = 0;
w < nclq; ++
w )
10656 for(
w = pos - 1;
w >= 0; --
w )
10657 clqvars[
w] = consdata->vars[
w];
10660 for(
c = 0;
c < nclq; ++
c )
10664 for(
w =
c;
w < len; ++
w )
10666 if( clqpart[
w] ==
c )
10668 assert(nclqvars < pos + len - nclq + 1);
10669 clqvars[nclqvars] = consdata->vars[
w + pos];
10704 int* newweightidxs;
10718 assert(consdata->merged);
10727 if( consdata->cliquepartition[consdata->nvars - 1] == consdata->nvars - 1 )
10731 cliqueweightsum = 0;
10734 for(
i = 0;
i < consdata->nvars; ++
i )
10738 cliquenum = consdata->cliquepartition[
i];
10739 assert(0 <= cliquenum && cliquenum <= ncliques);
10741 weight = consdata->weights[
i];
10744 if( cliquenum == ncliques )
10746 maxcliqueweights[ncliques] = weight;
10747 cliqueweightsum += weight;
10751 assert(maxcliqueweights[cliquenum] >= weight);
10755 zeroweights =
FALSE;
10756 for(
i = 0;
i < ncliques; ++
i )
10760 delta = consdata->capacity - (cliqueweightsum - maxcliqueweights[
i]);
10773 SCIPconsGetName(cons),
i, maxcliqueweights[
i], cliqueweightsum, consdata->capacity, delta);
10774 newcapacity = consdata->capacity - delta;
10775 forceclique =
FALSE;
10778 newmincliqueweight = newcapacity + 1;
10779 for( j = 0; j <
i; ++j )
10780 assert(consdata->cliquepartition[j] <
i);
10782 for( j =
i; j < consdata->nvars; ++j )
10784 if( consdata->cliquepartition[j] ==
i )
10786 newweight = consdata->weights[j] - delta;
10787 newweight =
MAX(newweight, 0);
10791 newweightvals[nnewweights] = newweight;
10792 newweightidxs[nnewweights] = j;
10796 assert(newweight <= newmincliqueweight);
10797 newmincliqueweight = newweight;
10803 if( nnewweights > 1 )
10806 j = newweightidxs[nnewweights - 2];
10808 assert(consdata->cliquepartition[j] ==
i);
10809 j = newweightidxs[nnewweights - 1];
10811 assert(consdata->cliquepartition[j] ==
i);
10814 newminweightsuminclique = newweightvals[nnewweights - 2];
10815 newminweightsuminclique += newweightvals[nnewweights - 1];
10822 if( newminweightsuminclique <= newcapacity )
10823 forceclique =
TRUE;
10827 if( conshdlrdata->disaggregation || !forceclique )
10830 consdata->capacity, newcapacity, forceclique);
10831 consdata->capacity = newcapacity;
10834 for( k = 0; k < nnewweights; ++k )
10836 j = newweightidxs[k];
10838 assert(consdata->cliquepartition[j] ==
i);
10842 SCIPvarGetName(consdata->vars[j]), consdata->weights[j], newweightvals[k]);
10845 assert(!consdata->sorted);
10846 zeroweights = zeroweights || (newweightvals[k] == 0);
10860 for( k = 0; k < nnewweights; ++k )
10861 cliquevars[k] = consdata->vars[newweightidxs[k]];
10888 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10896 if( consdata->weightsum <= consdata->capacity )
10908 if( consdata->weightsum <= consdata->capacity )
10914 assert(consdata->merged);
10916 minweight = consdata->weights[consdata->nvars-1];
10917 for(
i = 0;
i < consdata->nvars-1; ++
i )
10921 weight = consdata->weights[
i];
10922 assert(weight >= minweight);
10923 if( minweight + weight > consdata->capacity )
10925 if( weight < consdata->capacity )
10929 assert(consdata->sorted);
10931 assert(
i == 0 || consdata->weights[
i-1] >= consdata->weights[
i]);
10932 consdata->sorted =
TRUE;
10941 if( consdata->nvars >= 2 )
10945 minweight = consdata->weights[consdata->nvars-2];
10946 weight = consdata->weights[consdata->nvars-1];
10947 assert(minweight >= weight);
10948 if( minweight + weight > consdata->capacity && weight < consdata->capacity )
10952 assert(consdata->sorted);
10954 assert(minweight >= consdata->weights[consdata->nvars-1]);
10955 consdata->sorted =
TRUE;
10974 for(
b = 0;
b < ncliquevars; ++
b )
10995 int* gaincliquepartition;
11001 int nposcliquevars;
11005 int lastcliqueused;
11020 nvars = consdata->nvars;
11023 if( consdata->cliquesadded ||
nvars == 0 )
11034 assert(consdata->merged);
11041 nnegcliques = consdata->nnegcliques;
11044 if( nnegcliques ==
nvars )
11056 minactduetonegcliques = 0;
11059 for( v = 0; v <
nvars; ++v )
11061 assert(0 <= consdata->negcliquepartition[v] && consdata->negcliquepartition[v] <= nnegcliques);
11062 assert(consdata->weights[v] > 0);
11064 if( consdata->negcliquepartition[v] == nnegcliques )
11067 maxweights[consdata->negcliquepartition[v]] = consdata->weights[v];
11070 minactduetonegcliques += consdata->weights[v];
11073 nposcliquevars = 0;
11076 if( minactduetonegcliques > 0 )
11079 freecapacity = consdata->capacity - minactduetonegcliques;
11083 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
11086 for( v = 0; v <
nvars; ++v )
11088 if( !cliqueused[consdata->negcliquepartition[v]] )
11090 cliqueused[consdata->negcliquepartition[v]] =
TRUE;
11095 if( consdata->negcliquepartition[v] == consdata->negcliquepartition[
w]
11096 && consdata->weights[v] > consdata->weights[
w] )
11098 poscliquevars[nposcliquevars] = consdata->vars[
w];
11099 gainweights[nposcliquevars] = maxweights[consdata->negcliquepartition[v]] - consdata->weights[
w];
11100 gaincliquepartition[nposcliquevars] = consdata->negcliquepartition[v];
11108 if( nposcliquevars > 0 )
11113 for( v = 0; v < nposcliquevars; ++v )
11117 lastweight = gainweights[v];
11118 beforelastweight = -1;
11119 lastcliqueused = gaincliquepartition[v];
11122 cliqueused[gaincliquepartition[v]] =
TRUE;
11128 beforelastweight = lastweight;
11129 lastweight = gainweights[
w];
11130 lastcliqueused = gaincliquepartition[
w];
11131 cliqueused[gaincliquepartition[
w]] =
TRUE;
11136 if( ncliquevars > 1 )
11138 SCIPdebug( printClique(cliquevars, ncliquevars) );
11139 assert(beforelastweight > 0);
11145 *nbdchgs += thisnbdchgs;
11148 cliqueused[lastcliqueused] =
FALSE;
11154 SCIPdebug( printClique(cliquevars, ncliquevars) );
11158 *nbdchgs += thisnbdchgs;
11205 if( ! sorteditems )
11209 lastweight = weights[0];
11214 lastweight = weights[
i];
11218 if( ncliquevars > 1 )
11222 int compareweightidx;
11227 SCIPdebug( printClique(items, ncliquevars) );
11233 *nbdchgs += thisnbdchgs;
11234 nnzadded = ncliquevars;
11237 if( ncliquevars == nitems )
11245 compareweightidx = ncliquevars - 2;
11246 assert(
i == nitems || weights[
i] + weights[ncliquevars - 1] <= capacity);
11249 minclqsize = (int)(cliqueextractfactor * ncliquevars);
11250 minclqsize =
MAX(minclqsize, 2);
11254 while( compareweightidx >= 0 &&
i < nitems && ! (*
cutoff)
11255 && ncliquevars >= minclqsize
11256 && nnzadded <= 2 * nitems
11259 compareweight = weights[compareweightidx];
11260 assert(compareweight > 0);
11263 if( compareweight + weights[
i] > capacity )
11265 assert(compareweightidx == ncliquevars -2);
11266 cliquevars[ncliquevars - 1] = items[
i];
11267 SCIPdebug( printClique(cliquevars, ncliquevars) );
11270 nnzadded += ncliquevars;
11274 *nbdchgs += thisnbdchgs;
11282 compareweightidx--;
11312 int nposcliquevars;
11326 nvars = consdata->nvars;
11329 if( consdata->cliquesadded ||
nvars == 0 )
11340 assert(consdata->merged);
11347 nnegcliques = consdata->nnegcliques;
11357 minactduetonegcliques = 0;
11360 if( nnegcliques <
nvars )
11368 cliquenum = consdata->negcliquepartition[
i];
11369 assert(0 <= cliquenum && cliquenum <= nnegcliques);
11371 weight = consdata->weights[
i];
11374 if( cliquenum == nnegcliques )
11378 minactduetonegcliques += weight;
11379 if( secondmaxweights[cliquenum] == 0 )
11380 secondmaxweights[cliquenum] = weight;
11386 if( minactduetonegcliques > 0 )
11389 freecapacity = consdata->capacity - minactduetonegcliques;
11393 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
11401 nposcliquevars = 0;
11406 cliquenum = consdata->negcliquepartition[
i];
11407 if( consdata->weights[
i] > secondmaxweights[cliquenum] )
11409 poscliquevars[nposcliquevars] = consdata->vars[
i];
11410 gainweights[nposcliquevars] = consdata->weights[
i] - secondmaxweights[cliquenum];
11416 if( nposcliquevars > 1 )
11433 consdata->cliquesadded =
TRUE;
11462 assert(consdata1->sorted);
11463 assert(consdata2->sorted);
11470 if( consdata1->nvars != consdata2->nvars )
11473 for(
i = consdata1->nvars - 1;
i >= 0; --
i )
11476 if( consdata1->vars[
i] != consdata2->vars[
i] )
11485 if( consdata1->weights[
i] != consdata2->weights[
i] )
11500 uint64_t firstweight;
11507 assert(consdata->nvars > 0);
11520 assert(minidx >= 0 && mididx >= 0 && maxidx >= 0);
11523 firstweight = (uint64_t)consdata->weights[0];
11524 return SCIPhashSix(consdata->nvars, minidx, mididx, maxidx, firstweight>>32, firstweight);
11550 hashtablesize = nconss;
11553 hashGetKeyKnapsackcons, hashKeyEqKnapsackcons, hashKeyValKnapsackcons, (
void*)
scip) );
11556 for(
c = nconss - 1;
c >= 0; --
c )
11569 if( consdata0->nvars == 0 )
11571 if( consdata0->capacity < 0 )
11587 if( cons1 !=
NULL )
11602 assert(consdata0->nvars > 0 && consdata0->nvars == consdata1->nvars);
11604 assert(consdata0->sorted && consdata1->sorted);
11605 assert(consdata0->vars[0] == consdata1->vars[0]);
11606 assert(consdata0->weights[0] == consdata1->weights[0]);
11608 SCIPdebugMsg(
scip,
"knapsack constraints <%s> and <%s> with equal coefficients\n",
11612 if( consdata0->capacity < consdata1->capacity )
11669 assert(firstchange <= chkind);
11673 cons0 = conss[chkind];
11680 assert(consdata0->nvars >= 1);
11681 assert(consdata0->merged);
11687 if( consdata0->capacity == 0 )
11714 assert(consdata1->nvars >= 1);
11715 assert(consdata1->merged);
11721 if( consdata1->capacity == 0 )
11726 if( consdata0->nvars > consdata1->nvars )
11728 iscons0incons1contained =
FALSE;
11729 iscons1incons0contained =
TRUE;
11730 v = consdata1->nvars - 1;
11732 else if( consdata0->nvars < consdata1->nvars )
11734 iscons0incons1contained =
TRUE;
11735 iscons1incons0contained =
FALSE;
11736 v = consdata0->nvars - 1;
11740 iscons0incons1contained =
TRUE;
11741 iscons1incons0contained =
TRUE;
11742 v = consdata0->nvars - 1;
11753 v0 = consdata0->nvars - 1;
11754 v1 = consdata1->nvars - 1;
11758 assert(iscons0incons1contained || iscons1incons0contained);
11763 iscons1incons0contained =
FALSE;
11764 if( !iscons0incons1contained )
11770 iscons0incons1contained =
FALSE;
11771 if( !iscons1incons0contained )
11775 assert(v == v0 || v == v1);
11780 if( consdata0->vars[v0] == consdata1->vars[v1] )
11785 iscons1incons0contained =
FALSE;
11786 if( !iscons0incons1contained )
11792 iscons0incons1contained =
FALSE;
11793 if( !iscons1incons0contained )
11803 if( iscons0incons1contained && iscons1incons0contained )
11805 iscons0incons1contained =
FALSE;
11806 iscons1incons0contained =
FALSE;
11809 assert(iscons0incons1contained ? (v1 >= v0) : iscons1incons0contained);
11810 assert(iscons1incons0contained ? (v1 <= v0) : iscons0incons1contained);
11812 if( iscons0incons1contained )
11821 assert(!iscons1incons0contained || !iscons0incons1contained || v0 == -1 || v1 == -1);
11823 if( iscons1incons0contained )
11834 else if( iscons0incons1contained )
11872 SCIPdebugMsg(
scip,
"knapsack enforcement of %d/%d constraints for %s solution\n", nusefulconss, nconss,
11873 sol ==
NULL ?
"LP" :
"relaxation");
11878 maxncuts = (
SCIPgetDepth(
scip) == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
11881 for(
i = 0;
i < nusefulconss && ncuts < maxncuts && !
cutoff;
i++ )
11893 for(
i = nusefulconss;
i < nconss && ncuts == 0 && !
cutoff;
i++ )
11907 else if ( ncuts > 0 )
11983 for( v = 0; v <
nvars; ++v )
11989 transvars[v] =
vars[v];
11990 weights[v] = weight;
11995 weights[v] = -weight;
11996 capacity -= weight;
12003 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
12027 upgrade = (nposbin + nnegbin + nposimplbin + nnegimplbin ==
nvars)
12028 && (ncoeffspone + ncoeffsnone + ncoeffspint + ncoeffsnint ==
nvars)
12077 nlocvars = consdata->nvars;
12082 for(
i = 0;
i < consdata->nvars; ++
i )
12084 vars[
i] = consdata->vars[
i];
12161 conshdlrdata->reals1size =
nvars;
12179 conshdlrdata->reals1size = 0;
12211 conshdlrdata->ints1size =
nvars;
12212 conshdlrdata->ints2size =
nvars;
12213 conshdlrdata->longints1size =
nvars;
12214 conshdlrdata->longints2size =
nvars;
12215 conshdlrdata->bools1size =
nvars;
12216 conshdlrdata->bools2size =
nvars;
12217 conshdlrdata->bools3size =
nvars;
12218 conshdlrdata->bools4size =
nvars;
12220#ifdef WITH_CARDINALITY_UPGRADE
12221 conshdlrdata->upgradedcard =
FALSE;
12238 for(
c = 0;
c < nconss; ++
c )
12259 conshdlrdata->ints1size = 0;
12260 conshdlrdata->ints2size = 0;
12261 conshdlrdata->longints1size = 0;
12262 conshdlrdata->longints2size = 0;
12263 conshdlrdata->bools1size = 0;
12264 conshdlrdata->bools2size = 0;
12265 conshdlrdata->bools3size = 0;
12266 conshdlrdata->bools4size = 0;
12279 for(
c = 0;
c < nconss; ++
c )
12298 for(
c = 0;
c < nconss; ++
c )
12303 if( consdata->row !=
NULL )
12308 if( consdata->nlrow !=
NULL )
12365 sourcedata->nvars, sourcedata->vars, sourcedata->weights, sourcedata->capacity) );
12387 *infeasible =
FALSE;
12389 for(
i = 0;
i < nconss && !(*infeasible);
i++ )
12427 SCIPdebugMsg(
scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12428 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12431 if( (
depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12432 || (
depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12437 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12438 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12439 && ((sepacardfreq == 0 &&
depth == 0) || (sepacardfreq >= 1 && (
depth % sepacardfreq == 0)));
12445 maxbound = glblowerbound + conshdlrdata->maxcardbounddist * (cutoffbound - glblowerbound);
12446 sepacardinality = sepacardinality &&
SCIPisLE(
scip, loclowerbound, maxbound);
12450 maxsepacuts = (
depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12465 else if ( ncuts > 0 )
12496 SCIPdebugMsg(
scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12497 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12500 if( (
depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12501 || (
depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12506 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12507 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12508 && ((sepacardfreq == 0 &&
depth == 0) || (sepacardfreq >= 1 && (
depth % sepacardfreq == 0)));
12511 maxsepacuts = (
depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12526 else if( ncuts > 0 )
12557 for(
i = 0;
i < nconss;
i++ )
12611 for(
i = 0;
i < nmarkedconss && !
cutoff;
i++ )
12632 else if( nfixedvars > 0 )
12662 oldnfixedvars = *nfixedvars;
12663 oldnchgbds = *nchgbds;
12664 oldndelconss = *ndelconss;
12665 oldnaddconss = *naddconss;
12666 oldnchgcoefs = *nchgcoefs;
12667 oldnchgsides = *nchgsides;
12668 firstchange = INT_MAX;
12670 newchanges = (nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 || nnewupgdconss > 0);
12677 int thisnfixedvars;
12686 if( newchanges || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
12695 consdata->presolvedtiming = 0;
12696 else if( consdata->presolvedtiming >= presoltiming )
12701 consdata->presolvedtiming = presoltiming;
12703 thisnfixedvars = *nfixedvars;
12704 thisnchgbds = *nchgbds;
12734 if( *nfixedvars > thisnfixedvars || *nchgbds > thisnchgbds )
12740 thisnfixedvars = *nfixedvars;
12746 if( consdata->weightsum <= consdata->capacity )
12768 if( *nfixedvars > thisnfixedvars )
12809 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) || (*naddconss != oldnaddconss) )
12818 npaircomparisons = 0;
12819 oldndelconss = *ndelconss;
12820 oldnchgsides = *nchgsides;
12821 oldnchgcoefs = *nchgcoefs;
12835 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) )
12837 if( ((
SCIP_Real) (*ndelconss - oldndelconss) + ((
SCIP_Real) (*nchgsides - oldnchgsides))/2.0 +
12840 oldndelconss = *ndelconss;
12841 oldnchgsides = *nchgsides;
12842 oldnchgcoefs = *nchgcoefs;
12843 npaircomparisons = 0;
12847#ifdef WITH_CARDINALITY_UPGRADE
12865 noldupgdconss = *nupgdconss;
12878 for (makeupgrade = 0; makeupgrade < 2; ++makeupgrade)
12897 nvars = consdata->nvars;
12898 vars = consdata->vars;
12899 weights = consdata->weights;
12906 if ( consdata->capacity >=
nvars )
12910 assert( consdata->sorted );
12911 if ( weights[0] != 1 || weights[
nvars-1] != 1 )
12915 for (v = 0; v <
nvars; ++v)
12924 var = consdata->vars[v];
12941 for (j = 0; j < nimpls; ++j)
12955 cardvars[v] = implvars[j];
12972 if ( makeupgrade == 0 )
12974 for (v = 0; v <
nvars; ++v)
12998 for (v = 0; v <
nvars; ++v)
13008 conshdlrdata->upgradedcard =
TRUE;
13040 for (v = 0; v <
nvars; ++v)
13056 if ( *nupgdconss > noldupgdconss )
13063 else if( success || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
13087 for(
i = 0;
i < consdata->nvars; ++
i )
13104 if( inferinfo < 0 )
13111 if( inferinfo < consdata->
nvars && consdata->vars[inferinfo] == infervar )
13112 capsum = consdata->weights[inferinfo];
13115 for(
i = 0;
i < consdata->nvars && consdata->vars[
i] != infervar; ++
i )
13118 capsum = consdata->weights[
i];
13125 if( capsum <= consdata->capacity )
13127 for(
i = 0;
i < consdata->nvars;
i++ )
13132 capsum += consdata->weights[
i];
13133 if( capsum > consdata->capacity )
13165 for(
i = 0;
i < consdata->nvars;
i++)
13238 for(
i = 0;
i < consdata->nvars; ++
i )
13257 const char* consname;
13273 if( conshdlrdata->copytypedcons )
13301 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
13312 for( v = 0; v <
nvars; ++v )
13323 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode, global,
valid) );
13359 while( *str !=
'\0' )
13372 endptr = strchr(endptr,
'<');
13374 if( endptr ==
NULL )
13388 if( varssize <=
nvars )
13396 weights[
nvars] = weight;
13405 if( strncmp(str,
"<=", 2) != 0 )
13430 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
13449 if( varssize < consdata->
nvars )
13450 (*success) =
FALSE;
13471 (*nvars) = consdata->nvars;
13514 consdata->onesweightsum += eventdata->weight;
13515 consdata->presolvedtiming = 0;
13519 consdata->onesweightsum -= eventdata->weight;
13522 consdata->presolvedtiming = 0;
13526 if( !consdata->existmultaggr )
13535 consdata->existmultaggr =
TRUE;
13536 consdata->merged =
FALSE;
13540 consdata->merged =
FALSE;
13544 consdata->presolvedtiming = 0;
13547 consdata->varsdeleted =
TRUE;
13575 eventhdlrdata =
NULL;
13576 conshdlrdata->eventhdlr =
NULL;
13578 eventExecKnapsack, eventhdlrdata) );
13579 conshdlrdata->probtoidxmap =
NULL;
13580 conshdlrdata->probtoidxmapsize = 0;
13583 if( conshdlrdata->eventhdlr ==
NULL )
13592 consEnfolpKnapsack, consEnfopsKnapsack, consCheckKnapsack, consLockKnapsack,
13635 "multiplier on separation frequency, how often knapsack cuts are separated (-1: never, 0: only at root)",
13639 "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for separating knapsack cuts",
13643 "lower clique size limit for greedy clique extraction algorithm (relative to largest clique)",
13647 "maximal number of separation rounds per node (-1: unlimited)",
13651 "maximal number of separation rounds per node in the root node (-1: unlimited)",
13655 "maximal number of cuts separated per separation round",
13659 "maximal number of cuts separated per separation round in the root node",
13663 "should disaggregation of knapsack constraints be allowed in preprocessing?",
13667 "should presolving try to simplify knapsacks",
13671 "should negated clique information be used in solving process",
13675 "should pairwise constraint comparison be performed in presolving?",
13679 "should hash table be used for detecting redundant constraints in advance",
13683 "should dual presolving steps be performed?",
13687 "should GUB information be used for separation?",
13691 "should presolving try to detect constraints parallel to the objective function defining an upper bound and prevent these constraints from entering the LP?",
13695 "should presolving try to detect constraints parallel to the objective function defining a lower bound and prevent these constraints from entering the LP?",
13699 "should clique partition information be updated when old partition seems outdated?",
13703 "factor on the growth of global cliques to decide when to update a previous "
13704 "(negated) clique partition (used only if updatecliquepartitions is set to TRUE)",
13706#ifdef WITH_CARDINALITY_UPGRADE
13709 "if TRUE then try to update knapsack constraints to cardinality constraints",
13710 &conshdlrdata->upgdcardinality,
TRUE, DEFAULT_UPGDCARDINALITY,
NULL,
NULL) );
13714 "should knapsack constraints be copied as knapsack instead of as linear constraints?",
13765 if( conshdlr ==
NULL )
13791 SCIP_CALL(
SCIPcreateCons(
scip, cons, name, conshdlr, consdata, initial,
separate, enforce, check,
propagate,
13792 local, modifiable, dynamic, removable, stickingatnode) );
13863 return consdata->capacity;
13884 SCIPerrorMessage(
"method can only be called during problem creation stage\n");
13891 consdata->capacity = capacity;
13911 return consdata->nvars;
13929 return consdata->vars;
13947 return consdata->weights;
13965 if( consdata->row !=
NULL )
13986 if( consdata->row !=
NULL )
14009 return consdata->row;
14034 for(
i = 0;
i < consdata->nvars; ++
i )
14057 if( conshdlr ==
NULL )
14061 *infeasible =
FALSE;
14067 for(
i = nconss - 1;
i >= 0; --
i )
#define DEFAULT_DUALPRESOLVING
#define CONSHDLR_NEEDSCONS
#define CONSHDLR_SEPAFREQ
#define CONSHDLR_CHECKPRIORITY
#define CONSHDLR_PROP_TIMING
#define CONSHDLR_MAXPREROUNDS
#define DEFAULT_PRESOLPAIRWISE
#define CONSHDLR_SEPAPRIORITY
#define DEFAULT_PRESOLUSEHASHING
#define MINGAINPERNMINCOMPARISONS
#define CONSHDLR_PROPFREQ
#define CONSHDLR_PRESOLTIMING
#define CONSHDLR_EAGERFREQ
#define CONSHDLR_ENFOPRIORITY
#define CONSHDLR_DELAYSEPA
#define CONSHDLR_DELAYPROP
constraint handler for cardinality constraints
#define DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXSEPACUTSROOT
#define DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXROUNDS
#define LINCONSUPGD_PRIORITY
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
static SCIP_RETCODE deleteRedundantVars(SCIP *scip, SCIP_CONS *cons, SCIP_Longint frontsum, int splitpos, int *nchgcoefs, int *nchgsides, int *naddconss)
#define DEFAULT_SEPACARDFREQ
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)
static SCIP_RETCODE enlargeMinweights(SCIP *scip, SCIP_Longint **minweightsptr, int *minweightslen, int *minweightssize, int newlen)
#define DEFAULT_COPYTYPEDCONS
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)
struct SCIP_GUBSet SCIP_GUBSET
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)
static SCIP_RETCODE calcCliquepartition(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSDATA *consdata, SCIP_Bool normalclique, SCIP_Bool negatedclique)
static SCIP_RETCODE performVarDeletions(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss)
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)
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_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)
struct SCIP_GUBCons SCIP_GUBCONS
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)
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 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)
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result)
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)
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 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 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_STRINGEQ(name, reference, retcode)
#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 SCIPcreateRowKnapsack(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, int *ndelconss)
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_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
SCIP_Bool SCIPisTransformed(SCIP *scip)
SCIP_Bool SCIPisPresolveFinished(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNObjVars(SCIP *scip)
SCIP_RETCODE SCIPaddConsUpgrade(SCIP *scip, SCIP_CONS *oldcons, SCIP_CONS **newcons)
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)
int SCIPconsGetNUpgradeLocks(SCIP_CONS *cons)
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)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
#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 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 *scip, SCIP_VAR **vars, int nvars, int **probtoidxmap, int *probtoidxmapsize, int *cliquepartition, int *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 SCIPcalcCliquePartition(SCIP *scip, SCIP_VAR **vars, int nvars, int **probtoidxmap, int *probtoidxmapsize, int *cliquepartition, int *ncliques)
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
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 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
static SCIP_RETCODE separate(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
Main separation function.
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)
struct SCIP_Cons SCIP_CONS
#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)
struct SYM_Graph SYM_GRAPH
#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)
struct SCIP_Conshdlr SCIP_CONSHDLR
#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_Eventhdlr SCIP_EVENTHDLR
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
struct SCIP_Clique SCIP_CLIQUE
enum SCIP_BoundType SCIP_BOUNDTYPE
struct SCIP_HashMap SCIP_HASHMAP
#define SCIP_DECL_SORTPTRCOMP(x)
#define SCIP_DECL_HASHKEYEQ(x)
#define SCIP_DECL_HASHGETKEY(x)
#define SCIP_DECL_HASHKEYVAL(x)
struct SCIP_HashTable SCIP_HASHTABLE
struct SCIP_NlRow SCIP_NLROW
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_Sepa SCIP_SEPA
@ 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