76#ifdef WITH_CARDINALITY_UPGRADE
81#define CONSHDLR_NAME "knapsack"
82#define CONSHDLR_DESC "knapsack constraint of the form a^T x <= b, x binary and a >= 0"
83#define CONSHDLR_SEPAPRIORITY +600000
84#define CONSHDLR_ENFOPRIORITY -600000
85#define CONSHDLR_CHECKPRIORITY -600000
86#define CONSHDLR_SEPAFREQ 0
87#define CONSHDLR_PROPFREQ 1
88#define CONSHDLR_EAGERFREQ 100
90#define CONSHDLR_MAXPREROUNDS -1
91#define CONSHDLR_DELAYSEPA FALSE
92#define CONSHDLR_DELAYPROP FALSE
93#define CONSHDLR_NEEDSCONS TRUE
95#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
96#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
98#define EVENTHDLR_NAME "knapsack"
99#define EVENTHDLR_DESC "bound change event handler for knapsack constraints"
100#define EVENTTYPE_KNAPSACK SCIP_EVENTTYPE_LBCHANGED \
101 | SCIP_EVENTTYPE_UBTIGHTENED \
102 | SCIP_EVENTTYPE_VARFIXED \
103 | SCIP_EVENTTYPE_VARDELETED \
104 | SCIP_EVENTTYPE_IMPLADDED
106#define LINCONSUPGD_PRIORITY +100000
108#define MAX_USECLIQUES_SIZE 1000
109#define MAX_ZEROITEMS_SIZE 10000
111#define KNAPSACKRELAX_MAXDELTA 0.1
112#define KNAPSACKRELAX_MAXDNOM 1000LL
113#define KNAPSACKRELAX_MAXSCALE 1000.0
115#define DEFAULT_SEPACARDFREQ 1
116#define DEFAULT_MAXROUNDS 5
117#define DEFAULT_MAXROUNDSROOT -1
118#define DEFAULT_MAXSEPACUTS 50
119#define DEFAULT_MAXSEPACUTSROOT 200
120#define DEFAULT_MAXCARDBOUNDDIST 0.0
122#define DEFAULT_DISAGGREGATION TRUE
123#define DEFAULT_SIMPLIFYINEQUALITIES TRUE
124#define DEFAULT_NEGATEDCLIQUE TRUE
126#define MAXABSVBCOEF 1e+5
127#define USESUPADDLIFT FALSE
129#define DEFAULT_PRESOLUSEHASHING TRUE
130#define HASHSIZE_KNAPSACKCONS 500
132#define DEFAULT_PRESOLPAIRWISE TRUE
133#define NMINCOMPARISONS 200000
134#define MINGAINPERNMINCOMPARISONS 1e-06
136#define DEFAULT_DUALPRESOLVING TRUE
137#define DEFAULT_DETECTCUTOFFBOUND TRUE
140#define DEFAULT_DETECTLOWERBOUND TRUE
143#define DEFAULT_CLIQUEEXTRACTFACTOR 0.5
144#define MAXCOVERSIZEITERLEWI 1000
146#define DEFAULT_USEGUBS FALSE
147#define GUBCONSGROWVALUE 6
148#define GUBSPLITGNC1GUBS FALSE
149#define DEFAULT_CLQPARTUPDATEFAC 1.5
151#define DEFAULT_UPDATECLIQUEPARTITIONS FALSE
152#define MAXNCLIQUEVARSCOMP 1000000
153#ifdef WITH_CARDINALITY_UPGRADE
154#define DEFAULT_UPGDCARDINALITY FALSE
164struct SCIP_ConshdlrData
194 int probtoidxmapsize;
220#ifdef WITH_CARDINALITY_UPGRADE
233 int* cliquepartition;
234 int* negcliquepartition;
241 int ncliqueslastnegpart;
242 int ncliqueslastpart;
246 unsigned int presolvedtiming:5;
247 unsigned int sorted:1;
248 unsigned int cliquepartitioned:1;
249 unsigned int negcliquepartitioned:1;
250 unsigned int merged:1;
251 unsigned int cliquesadded:1;
252 unsigned int varsdeleted:1;
253 unsigned int existmultaggr:1;
330 if( sortkeypair1->key1 < sortkeypair2->key1 )
332 else if( sortkeypair1->key1 > sortkeypair2->key1 )
334 else if( sortkeypair1->key2 < sortkeypair2->key2 )
336 else if( sortkeypair1->key2 > sortkeypair2->key2 )
354 (*eventdata)->cons = cons;
355 (*eventdata)->weight = weight;
381 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
382 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
383 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
384 assert(consdata->nvars == 0 || (consdata->cliquepartition !=
NULL && consdata->negcliquepartition !=
NULL));
386 if( !consdata->sorted )
396 (
void**)consdata->vars,
397 (
void**)consdata->eventdata,
398 consdata->cliquepartition,
399 consdata->negcliquepartition,
402 v = consdata->nvars - 1;
408 while(
w >= 0 && consdata->weights[v] == consdata->weights[
w] )
415 (
void**)(&(consdata->vars[
w+1])),
416 (
void**)(&(consdata->eventdata[
w+1])),
417 &(consdata->cliquepartition[
w+1]),
418 &(consdata->negcliquepartition[
w+1]),
426 if( consdata->cliquepartitioned )
430 for( pos = 0; pos < consdata->nvars; ++pos )
434 if( consdata->cliquepartition[pos] > lastcliquenum )
436 consdata->cliquepartitioned =
FALSE;
439 else if( consdata->cliquepartition[pos] == lastcliquenum )
444 if( consdata->negcliquepartitioned )
448 for( pos = 0; pos < consdata->nvars; ++pos )
452 if( consdata->negcliquepartition[pos] > lastcliquenum )
454 consdata->negcliquepartitioned =
FALSE;
457 else if( consdata->negcliquepartition[pos] == lastcliquenum )
462 consdata->sorted =
TRUE;
468 for(
i = 0;
i < consdata->nvars-1; ++
i )
469 assert(consdata->weights[
i] >= consdata->weights[
i+1]);
487 assert(consdata->nvars == 0 || (consdata->cliquepartition !=
NULL && consdata->negcliquepartition !=
NULL));
490 ispartitionoutdated = (conshdlrdata->updatecliquepartitions && consdata->ncliques > 1
491 &&
SCIPgetNCliques(
scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastpart));
493 if( normalclique && ( !consdata->cliquepartitioned || ispartitionoutdated ) )
496 consdata->cliquepartition, &consdata->ncliques) );
497 consdata->cliquepartitioned =
TRUE;
502 isnegpartitionoutdated = (conshdlrdata->updatecliquepartitions && consdata->nnegcliques > 1
503 &&
SCIPgetNCliques(
scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastnegpart));
505 if( negatedclique && (!consdata->negcliquepartitioned || isnegpartitionoutdated) )
508 consdata->negcliquepartition, &consdata->nnegcliques) );
509 consdata->negcliquepartitioned =
TRUE;
512 assert(!consdata->cliquepartitioned || consdata->ncliques <= consdata->nvars);
513 assert(!consdata->negcliquepartitioned || consdata->nnegcliques <= consdata->nvars);
557 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
558 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
559 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
561 for(
i = 0;
i < consdata->nvars;
i++)
565 eventhdlr, consdata->eventdata[
i], &consdata->eventdata[
i]->filterpos) );
582 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
583 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
584 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
586 for(
i = 0;
i < consdata->nvars;
i++)
589 eventhdlr, consdata->eventdata[
i], consdata->eventdata[
i]->filterpos) );
606 assert(consdata->nvars <= consdata->varssize);
608 if( num > consdata->varssize )
627 consdata->varssize = newsize;
629 assert(num <= consdata->varssize);
645 consdata->weightsum += weightdelta;
648 consdata->onesweightsum += weightdelta;
650 assert(consdata->weightsum >= 0);
651 assert(consdata->onesweightsum >= 0);
673 (*consdata)->vars =
NULL;
674 (*consdata)->weights =
NULL;
675 (*consdata)->nvars = 0;
686 for( v = 0; v <
nvars; ++v )
692 assert( weights[v] >= 0 );
701 constant += weights[v];
705 varsbuffer[k] =
vars[v];
706 weightsbuffer[k] = weights[v];
714 (*consdata)->nvars = k;
728 (*consdata)->varssize = (*consdata)->nvars;
729 (*consdata)->capacity = capacity - constant;
730 (*consdata)->eventdata =
NULL;
731 (*consdata)->cliquepartition =
NULL;
732 (*consdata)->negcliquepartition =
NULL;
733 (*consdata)->row =
NULL;
734 (*consdata)->nlrow =
NULL;
735 (*consdata)->weightsum = 0;
736 (*consdata)->onesweightsum = 0;
737 (*consdata)->ncliques = 0;
738 (*consdata)->nnegcliques = 0;
739 (*consdata)->presolvedtiming = 0;
740 (*consdata)->sorted =
FALSE;
741 (*consdata)->cliquepartitioned =
FALSE;
742 (*consdata)->negcliquepartitioned =
FALSE;
743 (*consdata)->ncliqueslastpart = -1;
744 (*consdata)->ncliqueslastnegpart = -1;
745 (*consdata)->merged =
FALSE;
746 (*consdata)->cliquesadded =
FALSE;
747 (*consdata)->varsdeleted =
FALSE;
748 (*consdata)->existmultaggr =
FALSE;
755 for( v = 0; v < (*consdata)->nvars; v++ )
769 for( v = 0; v < (*consdata)->nvars; ++v )
791 if( (*consdata)->row !=
NULL )
795 if( (*consdata)->nlrow !=
NULL )
799 if( (*consdata)->eventdata !=
NULL )
804 if( (*consdata)->negcliquepartition !=
NULL )
808 if( (*consdata)->cliquepartition !=
NULL )
812 if( (*consdata)->vars !=
NULL )
817 for( v = 0; v < (*consdata)->nvars; v++ )
824 assert( (*consdata)->varssize > 0 );
848 oldweight = consdata->weights[item];
849 weightdiff = newweight - oldweight;
850 consdata->weights[item] = newweight;
855 if( consdata->eventdata !=
NULL )
858 assert(consdata->eventdata[item]->weight == oldweight);
859 consdata->eventdata[item]->weight = newweight;
862 consdata->presolvedtiming = 0;
863 consdata->sorted =
FALSE;
866 if( oldweight < newweight )
868 consdata->cliquesadded =
FALSE;
891 for(
i = 0;
i < consdata->nvars; ++
i )
916 if( consdata->row ==
NULL )
952 if( consdata->nlrow ==
NULL )
958 for(
i = 0;
i < consdata->nvars; ++
i )
962 consdata->nvars, consdata->vars, coefs,
NULL,
996 SCIPdebugMsg(
scip,
"checking knapsack constraint <%s> for feasibility of solution %p (lprows=%u)\n",
1018 for( v = consdata->nvars - 1; v >= 0; --v )
1031 if( normsum > consdata->capacity )
1033 absviol = normsum - consdata->capacity;
1069#define IDX(j,d) ((j)*(intcap)+(d))
1112 int greedymedianpos;
1117 int* allcurrminweight;
1140 for( j = nitems - 1; j >= 0; --j )
1147 if( solval !=
NULL )
1151 if( solitems !=
NULL )
1172 for( j = 0; j < nitems; ++j )
1177 if( weights[j] > capacity )
1179 if( solitems !=
NULL )
1180 nonsolitems[(*nnonsolitems)++] = items[j];
1183 else if( profits[j] <= 0.0 )
1185 if( solitems !=
NULL )
1186 nonsolitems[(*nnonsolitems)++] = items[j];
1189 else if( weights[j] == 0 )
1191 if( solitems !=
NULL )
1192 solitems[(*nsolitems)++] = items[j];
1194 if( solval !=
NULL )
1195 *solval += profits[j];
1200 myweights[nmyitems] = weights[j];
1201 myprofits[nmyitems] = profits[j];
1202 myitems[nmyitems] = items[j];
1205 if( myweights[nmyitems] < minweight )
1206 minweight = myweights[nmyitems];
1209 if( myweights[nmyitems] > maxweight )
1210 maxweight = myweights[nmyitems];
1212 weightsum += myweights[nmyitems];
1219 for( j = 0; j < nmyitems && intprofits; ++j )
1231 if( weightsum > 0 && weightsum <= capacity )
1235 for( j = nmyitems - 1; j >= 0; --j )
1237 if( solitems !=
NULL )
1238 solitems[(*nsolitems)++] = myitems[j];
1240 if( solval !=
NULL )
1241 *solval += myprofits[j];
1247 assert(0 < minweight && minweight <= capacity );
1248 assert(0 < maxweight && maxweight <= capacity);
1255 gcd = myweights[nmyitems - 1];
1256 for( j = nmyitems - 2; j >= 0 && gcd >= 2; --j )
1264 for( j = nmyitems - 1; j >= 0; --j )
1266 myweights[j] /= gcd;
1267 eqweights = eqweights && (myweights[j] == 1);
1275 assert(minweight <= capacity);
1278 if( minweight > capacity / 2 )
1282 SCIPdebugMsg(
scip,
"Only one item fits into knapsack, so take the best.\n");
1287 for( j = nmyitems - 2; j >= 0; --j )
1289 if( myprofits[j] > myprofits[p] )
1294 if( solitems !=
NULL )
1298 solitems[(*nsolitems)++] = myitems[p];
1299 for( j = nmyitems - 1; j >= 0; --j )
1302 nonsolitems[(*nnonsolitems)++] = myitems[j];
1306 if( solval !=
NULL )
1307 *solval += myprofits[p];
1322 if( solitems !=
NULL || solval !=
NULL )
1331 for(
i = capacity - 1;
i >= 0; --
i )
1333 if( solitems !=
NULL )
1334 solitems[(*nsolitems)++] = myitems[
i];
1335 addval += myprofits[
i];
1338 if( solitems !=
NULL )
1341 for(
i = nmyitems - 1;
i >= capacity; --
i )
1342 nonsolitems[(*nnonsolitems)++] = myitems[
i];
1346 if( solval !=
NULL )
1363 for( j = 0; j < nmyitems; ++j )
1365 tempsort[j] = myprofits[j]/((
SCIP_Real) myweights[j]);
1366 realweights[j] = (
SCIP_Real)myweights[j];
1370 (
SCIP_Real)capacity, nmyitems, &greedymedianpos);
1376 greedysolweight = 0;
1377 greedysolvalue = 0.0;
1380 for( j = 0; j < greedymedianpos; ++j )
1382 assert(myweights[j] <= capacity);
1385 greedysolweight += myweights[j];
1386 greedysolvalue += myprofits[j];
1389 assert(0 < greedysolweight && greedysolweight <= capacity);
1390 assert(greedysolvalue > 0.0);
1395 greedyupperbound = greedysolvalue + myprofits[j] * (
SCIP_Real) (capacity - greedysolweight)/((
SCIP_Real) myweights[j]);
1398 if( greedysolweight == capacity ||
SCIPisGE(
scip, greedysolvalue, greedyupperbound) )
1403 if( solitems !=
NULL )
1410 for( l = 0; l < j; ++l )
1411 solitems[(*nsolitems)++] = myitems[l];
1412 for ( ; l < nmyitems; ++l )
1413 nonsolitems[(*nnonsolitems)++] = myitems[l];
1416 if( solval !=
NULL )
1418 assert(greedysolvalue > 0.0);
1419 *solval += greedysolvalue;
1426 capacity -= (minweight - 1);
1429 if( capacity >= INT_MAX )
1436 assert(capacity < INT_MAX);
1438 intcap = (int)capacity;
1441 assert(
sizeof(
size_t) >=
sizeof(
int));
1446 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) )) )
1448 SCIPdebugMsg(
scip,
"Too much memory (%lu) would be consumed.\n", (
unsigned long) (((
size_t)nmyitems) * ((
size_t)intcap) *
sizeof(*optvalues)));
1476 assert(myweights[0] - minweight < INT_MAX);
1477 currminweight = (int) (myweights[0] - minweight);
1478 allcurrminweight[0] = currminweight;
1481 for( d = currminweight; d < intcap; ++d )
1482 optvalues[d] = myprofits[0];
1485 for( j = 1; j < nmyitems; ++j )
1490 intweight = (int)(myweights[j] - minweight);
1491 assert(0 <= intweight && intweight < intcap);
1494 for( d = currminweight; d < intweight && d < intcap; ++d )
1495 optvalues[
IDX(j,d)] = optvalues[
IDX(j-1,d)];
1498 for( d = intweight; d < intcap; ++d )
1501 if( d < currminweight )
1502 optvalues[
IDX(j,d)] = myprofits[j];
1507 if( d - myweights[j] < currminweight )
1508 sumprofit = myprofits[j];
1510 sumprofit = optvalues[
IDX(j-1,(
int)(d-myweights[j]))] + myprofits[j];
1512 optvalues[
IDX(j,d)] =
MAX(sumprofit, optvalues[
IDX(j-1,d)]);
1517 if( intweight < currminweight )
1518 currminweight = intweight;
1520 allcurrminweight[j] = currminweight;
1524 if( solitems !=
NULL )
1532 for( j = nmyitems - 1; j > 0; --j )
1535 if( d < allcurrminweight[j] )
1543 if( d < allcurrminweight[j-1] || optvalues[
IDX(j,d)] > optvalues[
IDX(j-1,d)] )
1545 solitems[(*nsolitems)++] = myitems[j];
1549 d = (int)(d - myweights[j]);
1553 nonsolitems[(*nnonsolitems)++] = myitems[j];
1557 if( d >= allcurrminweight[j] )
1560 solitems[(*nsolitems)++] = myitems[j];
1565 assert(d < allcurrminweight[j]);
1567 for( ; j >= 0; --j )
1568 nonsolitems[(*nnonsolitems)++] = myitems[j];
1571 assert(*nsolitems + *nnonsolitems == nitems);
1575 if( solval !=
NULL )
1576 *solval += optvalues[
IDX(nmyitems-1,intcap-1)];
1620 if( solitems !=
NULL )
1625 if( solval !=
NULL )
1631 for( j = nitems - 1; j >= 0; --j )
1633 tempsort[j] = profits[j]/((
SCIP_Real) weights[j]);
1642 for( j = 0; j < nitems && solitemsweight + weights[j] <= capacity; ++j )
1644 if( solitems !=
NULL )
1645 solitems[(*nsolitems)++] = items[j];
1647 if( solval !=
NULL )
1648 (*solval) += profits[j];
1649 solitemsweight += weights[j];
1651 if ( solitems !=
NULL )
1653 for( ; j < nitems; j++ )
1654 nonsolitems[(*nnonsolitems)++] = items[j];
1673 int nnontrivialgubconss;
1676 nnontrivialgubconss = 0;
1701 if( solvals !=
NULL )
1703 gubsolval += solvals[currentvar];
1713 if( solvals !=
NULL )
1722 nnontrivialgubconss++;
1746 (*gubcons)->ngubvars = 0;
1861 assert(oldgubcons != newgubcons);
1878 gubset->
gubvarsidx[replacevar] = oldgubvaridx;
1891 SCIPdebugMsg(
scip,
"deleting empty GUB cons<%d> from current GUB set\n", oldgubcons);
1996 (*gubset)->ngubconss =
nvars;
1997 (*gubset)->nvars =
nvars;
2009 (*gubset)->gubconssidx[
i] =
i;
2010 (*gubset)->gubvarsidx[
i] = 0;
2011 assert((*gubset)->gubconss[
i]->ngubvars == 1);
2014 if( weights[
i] > capacity )
2038 for(
i = (*gubset)->ngubconss-1;
i >= 0; --
i )
2075 for(
i = 0;
i < gubset->
nvars;
i++ )
2082 SCIPdebugMsg(
scip,
" var<%d> should be in GUB<%d> at position<%d>, but stored is var<%d> instead\n",
i,
2083 gubconsidx, gubvaridx, gubset->
gubconss[gubconsidx]->
gubvars[gubvaridx] );
2099 var1negated =
FALSE;
2106 var2negated =
FALSE;
2111 SCIPdebugMsg(
scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n",
i, j,
2114 SCIPdebugMsg(
scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n",
i, j,
2144 int*
const cliquepartition,
2156 int maxncliquevarscomp;
2184 tmpvalues[
i] =
TRUE;
2185 cliquepartition[
i] = -1;
2201 varseq[
nvars-1-nignorevars] =
i;
2207 varseq[nvarsused] =
i;
2223 if( cliquepartition[varseq[
i]] == -1 )
2228 cliquepartition[varseq[
i]] = *ncliques;
2229 cliquevars[0] = tmpvars[varseq[
i]];
2230 cliquevalues[0] = tmpvalues[varseq[
i]];
2239 for( j =
i + 1; j < nvarsused; ++j )
2242 if( cliquepartition[varseq[j]] == -1 &&
SCIPvarIsActive(tmpvars[varseq[j]]) )
2247 for( k = ncliquevars - 1; k >= 0; --k )
2250 cliquevalues[k],
TRUE) )
2257 cliquepartition[varseq[j]] = cliquepartition[varseq[
i]];
2258 cliquevars[ncliquevars] = tmpvars[varseq[j]];
2259 cliquevalues[ncliquevars] = tmpvalues[varseq[j]];
2269 assert(cliquepartition[varseq[
i]] >= 0 && cliquepartition[varseq[
i]] <
i + 1);
2272 if(
i *
nvars > maxncliquevarscomp )
2278 if( cliquepartition[varseq[
i]] == -1 )
2280 cliquepartition[varseq[
i]] = *ncliques;
2305 int* cliquepartition;
2308 int currentgubconsidx;
2331 for(
i = 0;
i < ncliques;
i++ )
2334 gubfirstvar[
i] = -1;
2339 assert(cliquepartition[
i] >= 0);
2341 cliqueidx = cliquepartition[
i];
2346 if( gubfirstvar[cliqueidx] == -1 )
2355 gubfirstvar[cliqueidx] =
i;
2360 assert(gubfirstvar[cliqueidx] >= 0 && gubfirstvar[cliqueidx] <
i);
2365 newgubconsidx = gubset->
gubconssidx[gubfirstvar[cliqueidx]];
2366 assert(newgubconsidx != currentgubconsidx);
2375 GUBsetPrint(
scip, gubset,
vars, solvals);
2466 fixedonesweight = 0;
2469 for( j = 0; j <
nvars; j++ )
2474 if( weights[j] > capacity )
2485 fixedones[nfixedones] = j;
2487 fixedonesweight += weights[j];
2492 fixedzeros[nfixedzeros] = j;
2501 itemsweight += weights[j];
2504 assert(nfixedones + nfixedzeros + nitems ==
nvars - (*ntightened));
2512 *fractional =
FALSE;
2533 for( j = 0; j < nitems; j++ )
2535 transweights[j] = weights[items[j]];
2536 transprofits[j] = 1.0 - solvals[items[j]];
2539 transcapacity = fixedonesweight + itemsweight - capacity - 1;
2544 if( transcapacity < 0 )
2568 for( j = 0; j < nitems; j++ )
2570 transprofits[j] *= weights[items[j]];
2582 noncovervars, covervars, nnoncovervars, ncovervars,
NULL) );
2586 for( j = 0; j < *ncovervars; j++ )
2588 (*coverweight) += weights[covervars[j]];
2592 for( j = 0; j < nfixedones; j++ )
2594 covervars[*ncovervars] = fixedones[j];
2596 (*coverweight) += weights[fixedones[j]];
2600 for( j = 0; j < nfixedzeros; j++ )
2602 noncovervars[*nnoncovervars] = fixedzeros[j];
2605 assert((*ncovervars) + (*nnoncovervars) ==
nvars - (*ntightened));
2606 assert((*coverweight) > capacity);
2643 minweight = weights[covervars[minweightidx]];
2646 for(
i = 0;
i < j;
i++ )
2648 assert(weights[covervars[
i]] > minweight);
2649 if( weights[covervars[
i]] <= minweight )
2654 for(
i = 0;
i < j;
i++ )
2656 assert(coverweight - weights[covervars[
i]] <= capacity);
2657 if( coverweight - weights[covervars[
i]] > capacity )
2693 for( j = 0; j < ncovervars; j++ )
2700 varsC2[*nvarsC2] = covervars[j];
2707 varsC1[*nvarsC1] = covervars[j];
2711 assert((*nvarsC1) + (*nvarsC2) == ncovervars);
2730 assert(*nvarsC1 >= 0 && *nvarsC1 <= 1);
2737 for( j = 0; j < *nvarsC2; j++ )
2738 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
2742 assert(*nvarsC2 == 1 || weights[varsC2[(*nvarsC2)-1]] <= weights[varsC2[(*nvarsC2)-2]]);
2743 while( *nvarsC1 < 2 && *nvarsC2 > 0 )
2745 varsC1[*nvarsC1] = varsC2[(*nvarsC2)-1];
2770 assert(*nvarsC1 >= 0 && *nvarsC1 <= 1);
2777 for( j = 0; j < *nvarsC2; j++ )
2778 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
2782 assert(*nvarsC2 == 1 || weights[varsC2[(*nvarsC2)-1]] <= weights[varsC2[(*nvarsC2)-2]]);
2783 varsC1[*nvarsC1] = varsC2[(*nvarsC2)-1];
2813 assert(nnoncovervars >= 0);
2824 for( j = 0; j < nnoncovervars; j++ )
2829 varsR[*nvarsR] = noncovervars[j];
2836 varsF[*nvarsF] = noncovervars[j];
2840 assert((*nvarsF) + (*nvarsR) == nnoncovervars);
2887 for( j = 0; j < nvarsF; j++ )
2889 sortkeypairsF[j] = &(sortkeypairsFstore[j]);
2890 sortkeypairsF[j]->key1 = solvals[varsF[j]];
2891 sortkeypairsF[j]->key2 = (
SCIP_Real) weights[varsF[j]];
2897 for( j = 0; j < nvarsC2; j++ )
2898 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
2903 for( j = 0; j < nvarsR; j++ )
2904 sortkeysR[j] = (
SCIP_Real) weights[varsR[j]];
2954 int* ngubconscapexceed,
2963 int* nC1varsingubcons;
2971 int nvarsprocessed = 0;
3043 for( j = 0; j < nvarsC1; j++ )
3046 sortkeysC1[j] = (
SCIP_Real) weights[varsC1[j]];
3059 for( j = 0; j < nvarsF; j++ )
3071 for( j = 0; j < nvarsC2; j++ )
3074 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
3086 for( j = 0; j < nvarsR; j++ )
3089 sortkeysR[j] = (
SCIP_Real) weights[varsR[j]];
3122 sortkeypairsGFC1[
i] = &(sortkeypairsGFC1store[
i]);
3123 sortkeypairsGFC1[
i]->key1 = 0.0;
3124 sortkeypairsGFC1[
i]->key2 = 0.0;
3130 *ngubconscapexceed = 0;
3131 *maxgubvarssize = 0;
3144 for(
i = 0;
i < nvarsC1;
i++ )
3146 int nvarsC1capexceed;
3148 nvarsC1capexceed = 0;
3160 targetvar = gubset->
gubconss[gubconsidx]->
gubvars[nC1varsingubcons[gubconsidx]];
3162 nC1varsingubcons[gubconsidx]++;
3176 gubconswithF =
FALSE;
3194 gubconswithF =
TRUE;
3196 sortkeypairsGFC1[*ngubconsGFC1]->key1 += 1.0;
3198 if( solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3199 sortkeypairsGFC1[*ngubconsGFC1]->key2 = solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]];
3210 gubconsGC1[*ngubconsGC1] = gubconsidx;
3265 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3270 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3279 for(
i = 0;
i < nvarsC2;
i++ )
3295 gubconsGC2[*ngubconsGC2] = gubconsidx;
3311 for(
i = 0;
i < nvarsF;
i++ )
3344 sortkeypairsGFC1[*ngubconsGFC1]->key1 += 1.0;
3346 if( solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3347 sortkeypairsGFC1[*ngubconsGFC1]->key2 = solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]];
3352 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3363 for(
i = 0;
i < nvarsR;
i++ )
3389 gubconsGR[*ngubconsGR] = gubconsidx;
3396 assert(nvarsprocessed == nvarsC1 + nvarsC2 + nvarsF + nvarsR);
3399 (*ngubconscapexceed) =
ngubconss - (ngubconsGOC1 + (*ngubconsGC2) + (*ngubconsGFC1) + (*ngubconsGR));
3400 assert(*ngubconscapexceed >= 0);
3413 assert(check == *ngubconscapexceed);
3418 if( (*ngubconsGFC1) > 0 )
3420 SCIPsortDownPtrInt((
void**)sortkeypairsGFC1, gubconsGFC1, compSortkeypairs, (*ngubconsGFC1));
3440 int* minweightssize,
3449 assert(*minweightslen >= 0);
3451 assert(*minweightssize >= 0);
3453 if( newlen > *minweightssize )
3460 *minweightssize = newsize;
3462 assert(newlen <= *minweightssize);
3465 for( j = *minweightslen; j < newlen; ++j )
3467 *minweightslen = newlen;
3526 assert(nvarsM1 >= 0 && nvarsM1 <=
nvars - ntightened);
3527 assert(nvarsM2 >= 0 && nvarsM2 <=
nvars - ntightened);
3528 assert(nvarsF >= 0 && nvarsF <=
nvars - ntightened);
3529 assert(nvarsR >= 0 && nvarsR <=
nvars - ntightened);
3530 assert(nvarsM1 + nvarsM2 + nvarsF + nvarsR ==
nvars - ntightened);
3537 minweightssize = nvarsM1 + 1;
3548 for( j = 0; j < nvarsM1; j++ )
3550 assert(liftcoefs[varsM1[j]] == 0);
3551 liftcoefs[varsM1[j]] = 1;
3552 sortkeys[j] = (
SCIP_Real) (weights[varsM1[j]]);
3553 (*cutact) += solvals[varsM1[j]];
3565 for(
w = 1;
w <= nvarsM1;
w++ )
3566 minweights[
w] = minweights[
w-1] + weights[varsM1[
w-1]];
3567 minweightslen = nvarsM1 + 1;
3570 fixedonesweight = 0;
3571 for( j = 0; j < nvarsM2; j++ )
3572 fixedonesweight += weights[varsM2[j]];
3573 assert(fixedonesweight >= 0);
3579 for( j = 0; j < nvarsF; j++ )
3587 weight = weights[liftvar];
3595 if( capacity - fixedonesweight - weight < 0 )
3603 else if( minweights[*liftrhs] <= capacity - fixedonesweight - weight )
3616 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
3618 right = (*liftrhs) + 1;
3619 while( left < right - 1 )
3621 middle = (left + right) / 2;
3622 assert(0 <= middle && middle < minweightslen);
3623 if( minweights[middle] <= capacity - fixedonesweight - weight )
3628 assert(left == right - 1);
3629 assert(0 <= left && left < minweightslen);
3630 assert(minweights[left] <= capacity - fixedonesweight - weight );
3631 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight - weight);
3639 liftcoef = (*liftrhs) - z;
3640 liftcoefs[liftvar] = liftcoef;
3641 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
3648 (*cutact) += liftcoef * solvals[liftvar];
3662 for(
w = minweightslen - 1;
w >= 0;
w-- )
3667 min =
MIN(minweights[
w], weight);
3668 minweights[
w] = min;
3673 min =
MIN(minweights[
w], minweights[
w - liftcoef] + weight);
3674 minweights[
w] = min;
3678 assert(minweights[0] == 0);
3681 for( j = 0; j < nvarsM2; j++ )
3691 liftvar = varsM2[j];
3692 weight = weights[liftvar];
3701 right = minweightslen;
3702 while( left < right - 1 )
3704 middle = (left + right) / 2;
3705 assert(0 <= middle && middle < minweightslen);
3706 if( minweights[middle] <= capacity - fixedonesweight + weight )
3711 assert(left == right - 1);
3712 assert(0 <= left && left < minweightslen);
3713 assert(minweights[left] <= capacity - fixedonesweight + weight );
3714 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight + weight);
3721 liftcoef = z - (*liftrhs);
3722 liftcoefs[liftvar] = liftcoef;
3726 fixedonesweight -= weight;
3729 (*liftrhs) += liftcoef;
3730 assert(*liftrhs >= alpha0);
3737 (*cutact) += liftcoef * solvals[liftvar];
3751 for(
w = minweightslen - 1;
w >= 0;
w-- )
3756 min =
MIN(minweights[
w], weight);
3757 minweights[
w] = min;
3762 min =
MIN(minweights[
w], minweights[
w - liftcoef] + weight);
3763 minweights[
w] = min;
3767 assert(fixedonesweight == 0);
3768 assert(*liftrhs >= alpha0);
3771 for( j = 0; j < nvarsR; j++ )
3779 weight = weights[liftvar];
3783 assert(capacity - weight >= 0);
3784 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - weight);
3789 if( minweights[*liftrhs] <= capacity - weight )
3802 right = (*liftrhs) + 1;
3803 while( left < right - 1)
3805 middle = (left + right) / 2;
3806 assert(0 <= middle && middle < minweightslen);
3807 if( minweights[middle] <= capacity - weight )
3812 assert(left == right - 1);
3813 assert(0 <= left && left < minweightslen);
3814 assert(minweights[left] <= capacity - weight );
3815 assert(left == minweightslen - 1 || minweights[left+1] > capacity - weight);
3823 liftcoef = (*liftrhs) - z;
3824 liftcoefs[liftvar] = liftcoef;
3825 assert(liftcoef >= 0 && liftcoef <= *liftrhs);
3832 (*cutact) += liftcoef * solvals[liftvar];
3838 for(
w = *liftrhs;
w >= 0;
w-- )
3843 min =
MIN(minweights[
w], weight);
3844 minweights[
w] = min;
3849 min =
MIN(minweights[
w], minweights[
w - liftcoef] + weight);
3850 minweights[
w] = min;
3877 return (val1 + val2);
3899 assert(unfinished[w2] == 0);
3900 for( w1 = 0; w1 < minweightslen; w1++ )
3901 minweights[w1] = finished[w1];
3904 for( w2 = 1; w2 < minweightslen; w2++ )
3909 for( w1 = 0; w1 < minweightslen - w2; w1++ )
3914 if( temp <= minweights[w1+w2] )
3915 minweights[w1+w2] = temp;
3939 int ngubconscapexceed,
4011 assert(ngubconsGC1 >= 0 && ngubconsGC1 <=
ngubconss - ngubconscapexceed);
4012 assert(ngubconsGC2 >= 0 && ngubconsGC2 <=
ngubconss - ngubconscapexceed);
4013 assert(ngubconsGFC1 >= 0 && ngubconsGFC1 <=
ngubconss - ngubconscapexceed);
4014 assert(ngubconsGR >= 0 && ngubconsGR <=
ngubconss - ngubconscapexceed);
4020 minweightssize = ngubconsGC1+1;
4039 for( j = 0; j < ngubconsGC1; j++ )
4043 gubconsGOC1[ngubconsGOC1] = gubconsGC1[j];
4049 gubconsGNC1[ngubconsGNC1] = gubconsGC1[j];
4060 (*cutact) += solvals[
varidx];
4064 assert(ngubconsGOC1 + ngubconsGFC1 + ngubconsGC2 + ngubconsGR ==
ngubconss - ngubconscapexceed);
4065 assert(ngubconsGOC1 + ngubconsGNC1 == ngubconsGC1);
4086 assert(ngubconsGOC1 <= ngubconsGC1);
4088 for(
w = 1;
w <= ngubconsGOC1;
w++ )
4090 liftgubconsidx = gubconsGOC1[
w-1];
4101 finished[
w] = finished[
w-1] + min;
4114 for(
w = ngubconsGOC1+1;
w <= ngubconsGC1;
w++ )
4122 assert(ngubconsGNC1 <= ngubconsGC1);
4124 for(
w = 1;
w <= ngubconsGNC1;
w++ )
4126 liftgubconsidx = gubconsGNC1[
w-1];
4137 unfinished[
w] = unfinished[
w-1] + min;
4150 for(
w = ngubconsGNC1 + 1;
w <= ngubconsGC1;
w++ )
4158 assert(ngubconsGOC1 + ngubconsGNC1 == ngubconsGC1);
4160 for(
w = 1;
w <= ngubconsGC1;
w++ )
4162 liftgubconsidx = gubconsGC1[
w-1];
4174 minweights[
w] = minweights[
w-1] + min;
4187 minweightslen = ngubconsGC1 + 1;
4190 fixedonesweight = 0;
4191 for( j = 0; j < ngubconsGC2; j++ )
4199 fixedonesweight += weights[
varidx];
4201 assert(fixedonesweight >= 0);
4207 for( j = 0; j < ngubconsGFC1; j++ )
4209 liftgubconsidx = gubconsGFC1[j];
4220 assert(ngubconsGNC1 > 0);
4233 weight = weights[liftgubvars[0]];
4235 weightdiff2 = unfinished[ngubconsGNC1] - weight;
4237 for(
w = ngubconsGNC1-1;
w >= 1;
w-- )
4239 weightdiff1 = weightdiff2;
4240 weightdiff2 = unfinished[
w] - weight;
4242 if( unfinished[
w] < weightdiff1 )
4243 unfinished[
w] = weightdiff1;
4251 assert(minweights[0] == 0);
4272 weight = weights[liftvar];
4275 assert(capacity - weight >= 0);
4280 liftgubvars[nliftgubvars] = liftvar;
4286 if( capacity - fixedonesweight - weight < 0 )
4294 else if( minweights[*liftrhs] <= capacity - fixedonesweight - weight )
4303 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
4305 right = (*liftrhs) + 1;
4306 while( left < right - 1 )
4308 middle = (left + right) / 2;
4309 assert(0 <= middle && middle < minweightslen);
4310 if( minweights[middle] <= capacity - fixedonesweight - weight )
4315 assert(left == right - 1);
4316 assert(0 <= left && left < minweightslen);
4317 assert(minweights[left] <= capacity - fixedonesweight - weight);
4318 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight - weight);
4326 liftcoef = (*liftrhs) - z;
4327 liftcoefs[liftvar] = liftcoef;
4328 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
4331 (*cutact) += liftcoef * solvals[liftvar];
4334 sumliftcoef += liftcoefs[liftvar];
4340 assert(nliftgubvars > nliftgubC1);
4346 if( sumliftcoef == 0 )
4350 weight = weights[liftgubvars[0]];
4355 for(
w = minweightslen-1;
w >= 1;
w-- )
4360 finished[
w] =
MIN(finished[
w], tmpval);
4363 minweights[
w] =
MIN(minweights[
w], tmpval);
4378 tmplen = minweightslen;
4379 tmpsize = minweightssize;
4381 tmplen = minweightslen;
4382 tmpsize = minweightssize;
4396 for(
w = minweightslen-1;
w >= 0;
w-- )
4401 for( k = 0; k < nliftgubvars; k++ )
4403 liftcoef = liftcoefs[liftgubvars[k]];
4404 weight = weights[liftgubvars[k]];
4408 minfinished =
MIN(finished[
w], weight);
4409 minminweight =
MIN(minweights[
w], weight);
4411 finished[
w] = minfinished;
4412 minweights[
w] = minminweight;
4421 minfinished =
MIN(finished[
w], tmpval);
4424 minminweight =
MIN(minweights[
w], tmpval);
4426 finished[
w] = minfinished;
4427 minweights[
w] = minminweight;
4431 assert(minweights[0] == 0);
4433 assert(ngubconsGNC1 == 0);
4440 for( j = 0; j < ngubconsGC2; j++ )
4442 liftgubconsidx = gubconsGC2[j];
4450 weight = weights[liftvar];
4460 right = minweightslen;
4461 while( left < right - 1 )
4463 middle = (left + right) / 2;
4464 assert(0 <= middle && middle < minweightslen);
4465 if( minweights[middle] <= capacity - fixedonesweight + weight )
4470 assert(left == right - 1);
4471 assert(0 <= left && left < minweightslen);
4472 assert(minweights[left] <= capacity - fixedonesweight + weight);
4473 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - fixedonesweight + weight);
4480 liftcoef = z - (*liftrhs);
4481 liftcoefs[liftvar] = liftcoef;
4485 fixedonesweight -= weight;
4488 (*liftrhs) += liftcoef;
4489 assert(*liftrhs >= alpha0);
4496 (*cutact) += liftcoef * solvals[liftvar];
4510 for(
w = minweightslen - 1;
w >= 0;
w-- )
4514 min =
MIN(minweights[
w], weight);
4515 minweights[
w] = min;
4524 min =
MIN(minweights[
w], tmpval);
4525 minweights[
w] = min;
4529 assert(fixedonesweight == 0);
4530 assert(*liftrhs >= alpha0);
4533 for( j = 0; j < ngubconsGR; j++ )
4535 liftgubconsidx = gubconsGR[j];
4547 weight = weights[liftvar];
4550 assert(capacity - weight >= 0);
4551 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - weight);
4556 liftgubvars[nliftgubvars] = liftvar;
4562 if( minweights[*liftrhs] <= capacity - weight )
4571 right = (*liftrhs) + 1;
4572 while( left < right - 1 )
4574 middle = (left + right) / 2;
4575 assert(0 <= middle && middle < minweightslen);
4576 if( minweights[middle] <= capacity - weight )
4581 assert(left == right - 1);
4582 assert(0 <= left && left < minweightslen);
4583 assert(minweights[left] <= capacity - weight);
4584 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - weight);
4591 liftcoef = (*liftrhs) - z;
4592 liftcoefs[liftvar] = liftcoef;
4593 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
4596 (*cutact) += liftcoef * solvals[liftvar];
4599 sumliftcoef += liftcoefs[liftvar];
4604 assert(nliftgubvars >= 1);
4607 if( sumliftcoef == 0 )
4613 for(
w = *liftrhs;
w >= 0;
w-- )
4615 for( k = 0; k < nliftgubvars; k++ )
4617 liftcoef = liftcoefs[liftgubvars[k]];
4618 weight = weights[liftgubvars[k]];
4622 min =
MIN(minweights[
w], weight);
4623 minweights[
w] = min;
4632 min =
MIN(minweights[
w], tmpval);
4633 minweights[
w] = min;
4637 assert(minweights[0] == 0);
4704 assert(nnoncovervars >= 0 && nnoncovervars <=
nvars - ntightened);
4705 assert(ncovervars + nnoncovervars ==
nvars - ntightened);
4722 for( j = 0; j < ncovervars; j++ )
4724 assert(liftcoefs[covervars[j]] == 0.0);
4725 liftcoefs[covervars[j]] = 1.0;
4726 sortkeys[j] = (
SCIP_Real) weights[covervars[j]];
4727 (*cutact) += solvals[covervars[j]];
4732 lambda = coverweight - capacity;
4736 maxweightsums[0] = 0;
4737 for(
h = 1;
h <= ncovervars;
h++ )
4739 maxweightsums[
h] = maxweightsums[
h-1] + weights[covervars[
h-1]];
4740 intervalends[
h-1] = maxweightsums[
h] - lambda;
4741 rhos[
h-1] =
MAX(0, weights[covervars[
h-1]] - weights[covervars[0]] + lambda);
4745 for( j = 0; j < nnoncovervars; j++ )
4746 sortkeys[j] = (
SCIP_Real) (weights[noncovervars[j]]);
4751 for( j = 0; j < nnoncovervars; j++ )
4757 liftvar = noncovervars[j];
4758 weight = weights[liftvar];
4760 while( intervalends[
h] < weight )
4767 if( weight <= intervalends[
h-1] + rhos[
h] )
4771 tmp1 = (
SCIP_Real) (intervalends[
h-1] + rhos[
h] - weight);
4773 liftcoef =
h - ( tmp1 / tmp2 );
4780 assert(liftcoefs[liftvar] == 0.0);
4781 liftcoefs[liftvar] = liftcoef;
4784 (*cutact) += liftcoef * solvals[liftvar];
4812 int* nonmincovervars,
4814 int nnonmincovervars,
4849 assert(nvarsC1 + nvarsC2 == nmincovervars);
4850 assert(nmincovervars > 0);
4854 if( nvarsC1 < 2 && nvarsC2 > 0)
4859 assert(nvarsC2 == 0 || nvarsC1 >= 1);
4866 assert(nvarsF + nvarsR == nnonmincovervars);
4867 assert(nvarsC1 + nvarsC2 + nvarsF + nvarsR ==
nvars - ntightened);
4870 if( gubset ==
NULL )
4889 varsF, varsR, nvarsC1, nvarsC2, nvarsF, nvarsR, nvarsC1 - 1, liftcoefs, &cutact, &liftrhs) );
4926 nvarsC2, nvarsF, nvarsR, gubconsGC1, gubconsGC2, gubconsGFC1, gubconsGR, &ngubconsGC1, &ngubconsGC2,
4927 &ngubconsGFC1, &ngubconsGR, &nconstightened, &maxgubvarssize) );
4943 gubconsGC2, gubconsGFC1, gubconsGR, ngubconsGC1, ngubconsGC2, ngubconsGFC1, ngubconsGR,
4944 MIN(nvarsC1 - 1, ngubconsGC1), liftcoefs, &cutact, &liftrhs, maxgubvarssize) );
4969 else if ( sepa !=
NULL )
4982 assert(nvarsC1 + nvarsC2 + nvarsF + nvarsR ==
nvars - ntightened);
4983 for( j = 0; j < nvarsC1; j++ )
4987 for( j = 0; j < nvarsC2; j++ )
4989 if( liftcoefs[varsC2[j]] > 0 )
4994 for( j = 0; j < nvarsF; j++ )
4996 if( liftcoefs[varsF[j]] > 0 )
5001 for( j = 0; j < nvarsR; j++ )
5003 if( liftcoefs[varsR[j]] > 0 )
5046 int* nonfeassetvars,
5048 int nnonfeassetvars,
5083 assert(nvarsT1 + nvarsT2 == nfeassetvars);
5086 if( nvarsT1 == 0 && nvarsT2 > 0)
5091 assert(nvarsT2 == 0 || nvarsT1 > 0);
5098 assert(nvarsF + nvarsR == nnonfeassetvars);
5099 assert(nvarsT1 + nvarsT2 + nvarsF + nvarsR ==
nvars - ntightened);
5118 SCIP_CALL(
sequentialUpAndDownLifting(
scip,
vars,
nvars, ntightened, weights, capacity, solvals, varsT1, varsT2, varsF, varsR,
5119 nvarsT1, nvarsT2, nvarsF, nvarsR, nvarsT1, liftcoefs, &cutact, &liftrhs) );
5136 else if ( sepa !=
NULL )
5149 assert(nvarsT1 + nvarsT2 + nvarsF + nvarsR ==
nvars - ntightened);
5150 for( j = 0; j < nvarsT1; j++ )
5154 for( j = 0; j < nvarsT2; j++ )
5156 if( liftcoefs[varsT2[j]] > 0 )
5161 for( j = 0; j < nvarsF; j++ )
5163 if( liftcoefs[varsF[j]] > 0 )
5168 for( j = 0; j < nvarsR; j++ )
5170 if( liftcoefs[varsR[j]] > 0 )
5213 int* nonmincovervars,
5215 int nnonmincovervars,
5244 nonmincovervars, nmincovervars, nnonmincovervars, mincoverweight, realliftcoefs, &cutact) );
5245 liftrhs = nmincovervars - 1;
5263 else if ( sepa !=
NULL )
5276 assert(nmincovervars + nnonmincovervars ==
nvars - ntightened);
5277 for( j = 0; j < nmincovervars; j++ )
5281 for( j = 0; j < nnonmincovervars; j++ )
5343 assert(*nnoncovervars >= 0);
5345 assert(*coverweight > 0);
5346 assert(*coverweight > capacity);
5350 nsortkeypairs = *ncovervars;
5359 assert(*ncovervars == nsortkeypairs);
5362 for( j = 0; j < *ncovervars; j++ )
5365 sortkeypairssorted[j] = sortkeypairs[j];
5367 sortkeypairs[j]->key1 = solvals[covervars[j]];
5368 sortkeypairs[j]->key2 = (
SCIP_Real) weights[covervars[j]];
5373 for( j = 0; j < *ncovervars; j++ )
5376 sortkeypairssorted[j] = sortkeypairs[j];
5378 sortkeypairs[j]->key1 = (solvals[covervars[j]] - 1.0) / ((
SCIP_Real) weights[covervars[j]]);
5379 sortkeypairs[j]->key2 = (
SCIP_Real) (-weights[covervars[j]]);
5382 SCIPsortPtrInt((
void**)sortkeypairssorted, covervars, compSortkeypairs, *ncovervars);
5386 minweight = weights[covervars[minweightidx]];
5387 for( j = 1; j < *ncovervars; j++ )
5389 if( weights[covervars[j]] <= minweight )
5392 minweight = weights[covervars[minweightidx]];
5395 assert(minweightidx >= 0 && minweightidx < *ncovervars);
5396 assert(minweight > 0 && minweight <= *coverweight);
5400 while( j < *ncovervars && ((*coverweight) - minweight > capacity) )
5402 assert(minweightidx >= j);
5406 if( (*coverweight) - weights[covervars[j]] <= capacity )
5413 noncovervars[*nnoncovervars] = covervars[j];
5417 (*coverweight) -= weights[covervars[j]];
5418 for( k = j; k < (*ncovervars) - 1; k++ )
5419 covervars[k] = covervars[k+1];
5423 if( j == minweightidx )
5426 minweight = weights[covervars[minweightidx]];
5427 for( k = 1; k < *ncovervars; k++ )
5429 if( weights[covervars[k]] <= minweight )
5432 minweight = weights[covervars[minweightidx]];
5435 assert(minweight > 0 && minweight <= *coverweight);
5436 assert(minweightidx >= 0 && minweightidx < *ncovervars);
5440 assert(minweightidx > j);
5445 assert((*coverweight) > capacity);
5446 assert((*coverweight) - minweight <= capacity);
5449 for( j = nsortkeypairs-1; j >= 0; j-- )
5496 assert(*nnoncovervars >= 0);
5498 assert(*coverweight > 0);
5499 assert(*coverweight > capacity);
5500 assert(*ncovervars + *nnoncovervars ==
nvars - ntightened);
5515 for( j = 0; j < *ncovervars; j++ )
5517 sortkeys[j] = solvals[covervars[j]];
5523 for( j = 0; j < *ncovervars; j++ )
5525 sortkeys[j] = (solvals[covervars[j]] - 1.0) / ((
SCIP_Real) weights[covervars[j]]);
5533 while( *ncovervars >= 2 )
5536 noncovervars[*nnoncovervars] = covervars[0];
5540 (*coverweight) -= weights[covervars[0]];
5541 for( k = 0; k < (*ncovervars) - 1; k++ )
5542 covervars[k] = covervars[k+1];
5545 assert(*ncovervars + *nnoncovervars ==
nvars - ntightened);
5546 if( (*coverweight) <= capacity )
5549 covervars, noncovervars, *ncovervars, *nnoncovervars,
sol,
cutoff, ncuts) );
5621 SCIPdebugMsg(
scip,
"separate cuts for knapsack constraint originated by cons <%s>:\n",
5652 modtransused =
TRUE;
5654 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5656 assert(!coverfound || !fractional || ncovervars + nnoncovervars ==
nvars - ntightened);
5661 SCIPdebugMsg(
scip,
" LMCI1-GUB terminated by no variable with fractional LP value.\n");
5676 &nnoncovervars, &coverweight, modtransused) );
5683 solvals, covervars, noncovervars, ncovervars, nnoncovervars,
sol, gubset,
cutoff, ncuts) );
5691 solvals, covervars, noncovervars, ncovervars, nnoncovervars,
sol,
NULL,
cutoff, ncuts) );
5711 modtransused =
TRUE;
5713 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5714 assert(!coverfound || !fractional || ncovervars + nnoncovervars ==
nvars - ntightened);
5727 &nnoncovervars, &coverweight, modtransused) );
5731 solvals, covervars, noncovervars, ncovervars, nnoncovervars,
sol,
NULL,
cutoff, ncuts) );
5738 solvals, covervars, noncovervars, ncovervars, nnoncovervars, coverweight,
sol,
cutoff, ncuts) );
5753 modtransused =
FALSE;
5755 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5757 assert(!coverfound || ncovervars + nnoncovervars ==
nvars - ntightened);
5766 SCIP_CALL(
getFeasibleSet(
scip, cons, sepa,
vars,
nvars, ntightened, weights, capacity, solvals, covervars, noncovervars,
5767 &ncovervars, &nnoncovervars, &coverweight, modtransused,
sol,
cutoff, ncuts) );
5839 if( conshdlr ==
NULL )
5841 noknapsackconshdlr =
TRUE;
5849 noknapsackconshdlr =
FALSE;
5852 usegubs = conshdlrdata->usegubs;
5859 if( conshdlrdata->reals1size == 0 )
5862 conshdlrdata->reals1size = 1;
5863 conshdlrdata->reals1[0] = 0.0;
5866 assert(conshdlrdata->reals1size > 0);
5872 if( conshdlrdata->reals1size < nbinvars )
5874 int oldsize = conshdlrdata->reals1size;
5876 conshdlrdata->reals1size = nbinvars;
5878 BMSclearMemoryArray(&(conshdlrdata->reals1[oldsize]), conshdlrdata->reals1size - oldsize);
5880 binvals = conshdlrdata->reals1;
5884 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
5886 assert(binvals[tmp] == 0);
5904 for(
i = 0;
i < nknapvars;
i++ )
5921 SCIPdebugMsg(
scip,
"Solution value %.15g <%s> outside domain [0.0, 1.0]\n",
5927 if( !noknapsackconshdlr )
5936 else if( valscale * knapvals[
i] > 0.0 )
5955 for( j = 0; j < nvlb; j++ )
5966 SCIPdebugMsg(
scip,
"variable bound <%s>[%g,%g] >= %g<%s>[%g,%g] + %g implies local cutoff\n",
5986 if( bestlbtype == -1 )
5988 rhs -= valscale * knapvals[
i] * bestlbsol;
5989 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with lower bound %.15g (rhs=%.15g)\n",
5995 rhs -= valscale * knapvals[
i] * dvlb[bestlbtype];
6001 if( !noknapsackconshdlr )
6008 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable lower bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6024 assert(valscale * knapvals[
i] < 0.0);
6035 for( j = 0; j < nvub; j++ )
6046 SCIPdebugMsg(
scip,
"variable bound <%s>[%g,%g] <= %g<%s>[%g,%g] + %g implies local cutoff\n",
6066 if( bestubtype == -1 )
6068 rhs -= valscale * knapvals[
i] * bestubsol;
6069 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with upper bound %.15g (rhs=%.15g)\n",
6075 rhs -= valscale * knapvals[
i] * dvub[bestubtype];
6081 if( !noknapsackconshdlr )
6088 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable upper bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6117 rhs = rhs * intscalar;
6122 for(
i = 0;
i < nbinvars;
i++ )
6152 consvals[nconsvars] = val;
6153 consvars[nconsvars] =
var;
6171 for(
i = 0;
i < nconsvars; ++
i )
6178 capacity, rhs, act, minact, maxact);
6182 if( minact > capacity )
6184 SCIPdebugMsg(
scip,
"minactivity of knapsack relaxation implies local cutoff\n");
6189 if( maxact > capacity )
6192 SCIP_CALL(
SCIPseparateKnapsackCuts(
scip, cons, sepa, consvars, nconsvars, consvals, capacity,
sol, usegubs,
cutoff, ncuts) );
6198 if( noknapsackconshdlr)
6205 for( --tmp; tmp >= 0; --tmp)
6208 binvals[tmpindices[tmp]] = 0;
6254 consdata->capacity,
sol, usegubs,
cutoff, ncuts) );
6277 if( consdata->row !=
NULL )
6286 consdata->capacity -= weight;
6297 consdata->vars[consdata->nvars] =
var;
6298 consdata->weights[consdata->nvars] = weight;
6316 conshdlrdata->eventhdlr, consdata->eventdata[consdata->nvars-1],
6317 &consdata->eventdata[consdata->nvars-1]->filterpos) );
6320 consdata->existmultaggr =
TRUE;
6324 consdata->presolvedtiming = 0;
6325 consdata->cliquesadded =
FALSE;
6331 consdata->sorted =
FALSE;
6332 consdata->cliquepartitioned =
FALSE;
6333 consdata->negcliquepartitioned =
FALSE;
6334 consdata->merged =
FALSE;
6355 var = consdata->vars[pos];
6360 if( consdata->row !=
NULL )
6376 conshdlrdata->eventhdlr, consdata->eventdata[pos], consdata->eventdata[pos]->filterpos) );
6380 consdata->presolvedtiming = 0;
6381 consdata->sorted = (consdata->sorted && pos == consdata->nvars - 1);
6388 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
6389 consdata->weights[pos] = consdata->weights[consdata->nvars-1];
6390 if( consdata->eventdata !=
NULL )
6391 consdata->eventdata[pos] = consdata->eventdata[consdata->nvars-1];
6397 if( consdata->cliquepartitioned )
6402 if( consdata->cliquepartition[consdata->nvars - 1] != consdata->nvars - 1 )
6406 oldcliqenum = consdata->cliquepartition[pos];
6407 consdata->cliquepartition[pos] = consdata->cliquepartition[consdata->nvars-1];
6410 if( consdata->cliquepartition[pos] > pos )
6411 consdata->cliquepartitioned =
FALSE;
6415 int cliquenumbefore;
6419 if( oldcliqenum > consdata->cliquepartition[pos] )
6421 for(
i = 0;
i < consdata->nvars; ++
i )
6422 if( oldcliqenum == consdata->cliquepartition[
i] )
6424 else if( oldcliqenum < consdata->cliquepartition[
i] )
6426 consdata->cliquepartitioned =
FALSE;
6432 if(
i == consdata->nvars )
6433 --(consdata->ncliques);
6437 else if( oldcliqenum < consdata->cliquepartition[pos] )
6439 cliquenumbefore = consdata->cliquepartition[pos] - 1;
6440 for(
i = pos - 1;
i >= 0 &&
i >= cliquenumbefore && consdata->cliquepartition[
i] < cliquenumbefore; --
i );
6442 if(
i < cliquenumbefore )
6443 consdata->cliquepartitioned =
FALSE;
6446 else if( pos == consdata->nvars - 1)
6448 cliquenumbefore = consdata->cliquepartition[pos];
6449 for(
i = pos - 1;
i >= 0 &&
i >= cliquenumbefore && consdata->cliquepartition[
i] < cliquenumbefore; --
i );
6451 if(
i < cliquenumbefore )
6452 --(consdata->ncliques);
6458 --(consdata->ncliques);
6461 if( consdata->negcliquepartitioned )
6463 assert(consdata->negcliquepartition !=
NULL);
6466 if( consdata->negcliquepartition[consdata->nvars-1] != consdata->nvars - 1 )
6470 oldcliqenum = consdata->negcliquepartition[pos];
6471 consdata->negcliquepartition[pos] = consdata->negcliquepartition[consdata->nvars-1];
6474 if( consdata->negcliquepartition[pos] > pos )
6475 consdata->negcliquepartitioned =
FALSE;
6479 int cliquenumbefore;
6483 if( oldcliqenum > consdata->negcliquepartition[pos] )
6485 for(
i = 0;
i < consdata->nvars; ++
i )
6486 if( oldcliqenum == consdata->negcliquepartition[
i] )
6488 else if( oldcliqenum < consdata->negcliquepartition[
i] )
6490 consdata->negcliquepartitioned =
FALSE;
6496 if(
i == consdata->nvars )
6497 --(consdata->nnegcliques);
6501 else if( oldcliqenum < consdata->negcliquepartition[pos] )
6503 cliquenumbefore = consdata->negcliquepartition[pos] - 1;
6504 for(
i = pos - 1;
i >= 0 &&
i >= cliquenumbefore && consdata->negcliquepartition[
i] < cliquenumbefore; --
i );
6506 if(
i < cliquenumbefore )
6507 consdata->negcliquepartitioned =
FALSE;
6510 else if( pos == consdata->nvars - 1)
6512 cliquenumbefore = consdata->negcliquepartition[pos];
6513 for(
i = pos - 1;
i >= 0 &&
i >= cliquenumbefore && consdata->negcliquepartition[
i] < cliquenumbefore; --
i );
6515 if(
i < cliquenumbefore )
6516 --(consdata->nnegcliques);
6522 --(consdata->nnegcliques);
6525 --(consdata->nvars);
6543 for( v = consdata->nvars-1; v >= 0; --v )
6545 if( consdata->weights[v] == 0 )
6574 for(
i = 0;
i < nconss;
i++ )
6579 if( consdata->varsdeleted )
6582 for( v = consdata->nvars - 1; v >= 0; --v )
6589 consdata->varsdeleted =
FALSE;
6617 if( consdata->merged )
6620 if( consdata->nvars <= 1 )
6622 consdata->merged =
TRUE;
6626 assert(consdata->vars !=
NULL || consdata->nvars == 0);
6630 consdata->cliquepartition, consdata->negcliquepartition, SCIPvarCompActiveAndNegated, consdata->nvars);
6633 consdata->sorted =
FALSE;
6635 v = consdata->nvars - 1;
6648 var1 = consdata->vars[v];
6658 var2 = consdata->vars[prev];
6671 if( negated1 == negated2 )
6674 consdataChgWeight(consdata, prev, consdata->weights[v] + consdata->weights[prev]);
6680 else if( consdata->weights[v] == consdata->weights[prev] )
6683 consdata->capacity -= consdata->weights[v];
6689 else if( consdata->weights[v] < consdata->weights[prev] )
6691 consdata->capacity -= consdata->weights[v];
6692 consdataChgWeight(consdata, prev, consdata->weights[prev] - consdata->weights[v]);
6693 assert(consdata->weights[prev] > 0);
6698 consdata->capacity -= consdata->weights[prev];
6700 assert(consdata->weights[v] > 0);
6703 if( consdata->nvars != v )
6707 if( prev == 0 || (var1 != consdata->vars[prev - 1] && var1 !=
SCIPvarGetNegatedVar(consdata->vars[prev - 1])) )
6711 consdata->cliquesadded =
FALSE;
6718 consdata->cliquesadded =
FALSE;
6724 consdata->merged =
TRUE;
6727 if( consdata->onesweightsum > consdata->capacity )
6776 nvars = consdata->nvars;
6777 vars = consdata->vars;
6789 for( v = 0; v <
nvars; ++v )
6832 items, solitems, nonsolitems, &nsolitems, &nnonsolitems, &solval, &success) );
6839 for( v = 0; v < nsolitems; ++v )
6844 SCIPdebugMsg(
scip,
"variable <%s> only locked up in knapsack constraints: dual presolve <%s>[%.15g,%.15g] >= 1.0\n",
6852 for( v = 0; v < nnonsolitems; ++v )
6857 SCIPdebugMsg(
scip,
"variable <%s> has no down locks: dual presolve <%s>[%.15g,%.15g] <= 0.0\n",
6908 nvars = consdata->nvars;
6923 vars = consdata->vars;
6930 for( v = 0; v <
nvars && applicable; ++v )
6952 weight = (
SCIP_Real)consdata->weights[v];
6959 scale = weight / -
objval;
6988 cutoffbound = (consdata->capacity - offset) / scale;
6990 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
6998 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
7024 lowerbound = (consdata->capacity - offset) / scale;
7026 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a lower bound <%g>\n",
7044 int* cliquestartposs,
7051 int* cliquepartition;
7068 origweights = consdata->weights;
7069 origvars = consdata->vars;
7070 norigvars = consdata->nvars;
7073 assert(origweights !=
NULL || norigvars == 0);
7075 if( norigvars == 0 )
7078 if( usenegatedclique )
7080 assert(consdata->negcliquepartitioned);
7082 cliquepartition = consdata->negcliquepartition;
7083 ncliques = consdata->nnegcliques;
7087 assert(consdata->cliquepartitioned);
7089 cliquepartition = consdata->cliquepartition;
7090 ncliques = consdata->ncliques;
7101 for( v = norigvars - 1; v >= 0; --v )
7103 assert(0 <= cliquepartition[v] && cliquepartition[v] < ncliques);
7104 ++(cliquecount[cliquepartition[v]]);
7118 for(
c = 0;
c < ncliques; ++
c )
7128 cliquestartposs[
c] = nextpos;
7131 nextpos += cliquecount[
c];
7134 assert(nextpos == norigvars);
7135 cliquestartposs[
c] = nextpos;
7138 for( v = 0; v < norigvars; ++v )
7140 *(varpointers[cliquepartition[v]]) = origvars[v];
7141 ++(varpointers[cliquepartition[v]]);
7142 *(weightpointers[cliquepartition[v]]) = origweights[v];
7143 ++(weightpointers[cliquepartition[v]]);
7146 for( v = 0; v < norigvars; ++v )
7179 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
7188 if ( consdata->onesweightsum > consdata->capacity )
7199 consdata->existmultaggr =
FALSE;
7202 while( v < consdata->
nvars )
7206 var = consdata->vars[v];
7212 consdata->capacity -= consdata->weights[v];
7214 consdata->cliquesadded =
FALSE;
7229 weight = consdata->weights[v];
7282 assert((aggrvars !=
NULL && aggrscalars !=
NULL) || naggrvars == 0);
7286 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-integral value for weight*aggrconst = %g\n", weight*aggrconst);
7294 for(
i = naggrvars - 1;
i >= 0; --
i )
7301 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-binary %svariable <%s> with bounds [%g,%g]\n",
7307 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-integral value for weight*aggrscalars = %g\n", weight*aggrscalars[
i]);
7332 if( consdata->capacity < 0 )
7342 else if( repvar !=
var )
7354 assert(consdata->onesweightsum == 0);
7397 int* cliquestartposs;
7425 for(
i = 0;
i < consdata->nvars && consdata->merged; ++
i )
7431 usenegatedclique = usenegatedclique && consdata->merged;
7436 cliquestartposs =
NULL;
7437 secondmaxweights =
NULL;
7439 nvars = consdata->nvars;
7445 localminweightsum = 0;
7454 if( usenegatedclique &&
nvars > 0 )
7462 nnegcliques = consdata->nnegcliques;
7465 if( nnegcliques ==
nvars )
7468 usenegatedclique =
FALSE;
7484 for(
c = 0;
c < nnegcliques; ++
c )
7486 cliqueendposs[
c] = cliquestartposs[
c+1] - 1;
7487 assert(cliqueendposs[
c] - cliquestartposs[
c] >= 0);
7501 if( nnegcliques -
c ==
nvars -
i )
7503 minweightsum += localminweightsum;
7504 localminweightsum = 0;
7512 if( cliquestartposs[
c] ==
i )
7516 minweightsum += localminweightsum;
7517 localminweightsum = 0;
7536 assert(myweights[
i] <= myweights[cliquestartposs[
c - 1]]);
7543 cliquestartposs[
c - 1] =
i;
7549 if( secondmaxweights[
c - 1] == 0 )
7550 secondmaxweights[
c - 1] = myweights[
i];
7552 localminweightsum += myweights[
i];
7559 for( v = cliquestartposs[
c - 1]; v < cliquestartposs[
c]; ++v )
7596 localminweightsum = 0;
7598 i = cliqueendposs[
c - 1];
7607 minweightsum += localminweightsum;
7613 if( !(*
cutoff) && consdata->capacity >= minweightsum + consdata->onesweightsum )
7618 for(
c = 0;
c < nnegcliques; ++
c )
7622 int endvarposclique;
7623 int startvarposclique;
7626 assert(nnegcliques == consdata->nnegcliques);
7631 endvarposclique = cliqueendposs[
c];
7632 startvarposclique = cliquestartposs[
c];
7634 maxvar = myvars[startvarposclique];
7640 maxcliqueweight = myweights[startvarposclique];
7641 maxvarfixed =
FALSE;
7646 if( consdata->onesweightsum + minweightsum + (maxcliqueweight - secondmaxweights[
c]) > consdata->capacity )
7649 SCIP_Longint oldonesweightsum = consdata->onesweightsum;
7651 assert(maxcliqueweight >= secondmaxweights[
c]);
7657 assert(consdata->onesweightsum == oldonesweightsum);
7666 else if( nnegcliques -
c ==
nvars - startvarposclique )
7676 else if( consdata->onesweightsum + minweightsum + (maxcliqueweight - consdata->weights[
nvars - 1]) <= consdata->capacity )
7680 for(
i = endvarposclique;
i > startvarposclique; --
i )
7689 assert(maxcliqueweight >= myweights[
i]);
7690 assert(
i == endvarposclique || myweights[
i] >= myweights[
i+1]);
7698 if( maxvarfixed || consdata->onesweightsum + minweightsum - myweights[
i] + maxcliqueweight > consdata->capacity )
7701 SCIP_Longint oldonesweightsum = consdata->onesweightsum;
7705 assert(consdata->onesweightsum == oldonesweightsum + myweights[
i]);
7714 minweightsum -= myweights[
i];
7715 assert(minweightsum >= 0);
7723 for( ;
i > startvarposclique; --
i )
7726 SCIP_Bool exceedscapacity = consdata->onesweightsum + minweightsum - myweights[
i] + maxcliqueweight > consdata->capacity;
7728 assert(
i == endvarposclique || myweights[
i] >= myweights[
i+1]);
7729 assert(varisfixed || !exceedscapacity);
7741 assert(consdata->negcliquepartitioned || minweightsum == 0);
7745 assert(usenegatedclique || minweightsum == 0);
7747 if( consdata->capacity < minweightsum + consdata->onesweightsum )
7750 consdata->onesweightsum, consdata->capacity);
7765 for(
i = 0;
i <
nvars && weight <= consdata->capacity;
i++ )
7770 weight += consdata->weights[
i];
7781 if( !usenegatedclique )
7783 assert(consdata->sorted);
7784 residualcapacity = consdata->capacity - consdata->onesweightsum;
7787 for(
i = 0;
i <
nvars && consdata->weights[
i] > residualcapacity; ++
i )
7796 assert(consdata->onesweightsum + consdata->weights[
i] > consdata->capacity);
7811 SCIP_Longint unfixedweightsum = consdata->onesweightsum;
7818 unfixedweightsum += consdata->weights[
i];
7821 if( unfixedweightsum > consdata->capacity )
7827 SCIPconsGetName(cons), consdata->weightsum, unfixedweightsum, consdata->capacity);
7856 assert(consdata->nvars > 1);
7859 if( consdata->nvars == 2 )
7940 assert(0 < frontsum && frontsum < consdata->weightsum);
7941 assert(0 < splitpos && splitpos < consdata->
nvars);
7946 vars = consdata->vars;
7947 weights = consdata->weights;
7948 nvars = consdata->nvars;
7949 capacity = consdata->capacity;
7956 assert(weights[
w] <= weights[
w-1]);
7960 if( consdata->nvars - 1 == splitpos )
7963 assert(frontsum + weights[splitpos] > capacity);
7966 if( consdata->weightsum - weights[splitpos] <= capacity )
7974 for(
w =
nvars - 1;
w > splitpos; --
w )
7976 consdata->capacity -= weights[
w];
7982 *nchgcoefs += (
nvars - splitpos);
7986 for( ;
w >= 0 && gcd > 1; --
w )
7994 for(
w = splitpos;
w >= 0; --
w )
7998 (*nchgcoefs) +=
nvars;
8000 consdata->capacity /= gcd;
8008 for(
w = consdata->nvars - 1;
w > 0; --
w )
8009 assert(weights[
w] <= weights[
w - 1]);
8016 else if( conshdlrdata->disaggregation && frontsum + weights[splitpos + 1] <= capacity )
8022 len =
nvars - (splitpos + 1);
8039 for(
w = 0;
w < len; ++
w )
8041 assert(clqpart[
w] >= 0 && clqpart[
w] <=
w);
8042 if( clqpart[
w] == cliquenum )
8044 maxactduetoclq += weights[
w + splitpos + 1];
8052 if( frontsum + maxactduetoclq <= capacity )
8058 assert(maxactduetoclq < weights[splitpos]);
8065 for(
c = 0;
c < nclq; ++
c )
8068 for(
w = 0;
w < len; ++
w )
8070 if( clqpart[
w] ==
c )
8072 clqvars[nclqvars] =
vars[
w + splitpos + 1];
8100 for(
w =
nvars - 1;
w > splitpos; --
w )
8105 consdata->capacity -= maxactduetoclq;
8106 assert(frontsum <= consdata->capacity);
8112 weights = consdata->weights;
8116 for( ;
w >= 0 && gcd > 1; --
w )
8124 for(
w = splitpos;
w >= 0; --
w )
8128 (*nchgcoefs) +=
nvars;
8130 consdata->capacity /= gcd;
8141 for(
w = consdata->nvars - 1;
w > 0; --
w )
8142 assert(weights[
w] <= weights[
w - 1]);
8193 assert(consdata->nvars >= 2);
8194 assert(consdata->weightsum > consdata->capacity);
8196 vars = consdata->vars;
8197 weights = consdata->weights;
8198 nvars = consdata->nvars;
8199 capacity = consdata->capacity;
8203 for( v = 0; v <
nvars && sum + weights[v] <= capacity; ++v )
8221 assert(consdata->nvars > 1);
8234 assert(weights == consdata->weights);
8236 assert(capacity == consdata->capacity);
8244 if( consdata->cliquepartition[v] < v )
8252 maxactduetoclqfront = 0;
8254 clqpart = consdata->cliquepartition;
8260 assert(clqpart[
w] >= 0 && clqpart[
w] <=
w);
8261 if( clqpart[
w] == cliquenum )
8263 if( maxactduetoclqfront + weights[
w] <= capacity )
8265 maxactduetoclqfront += weights[
w];
8271 sumfront += weights[
w];
8285 assert(maxactduetoclqfront <= capacity);
8289 ncliques = consdata->ncliques;
8294 for(
c = 0;
c < ncliques; ++
c )
8299 if( clqpart[
w] ==
c )
8301 clqvars[nclqvars] =
vars[
w];
8366 assert(consdata->onesweightsum == 0);
8367 assert(consdata->weightsum > consdata->capacity);
8368 assert(consdata->nvars >= 1);
8373 gcd = consdata->weights[consdata->nvars-1];
8374 for(
i = consdata->nvars-2;
i >= 0 && gcd >= 2; --
i )
8386 for(
i = 0;
i < consdata->nvars; ++
i )
8390 consdata->capacity /= gcd;
8391 (*nchgcoefs) += consdata->nvars;
8396 for(
i = consdata->nvars - 1;
i > 0; --
i )
8397 assert(consdata->weights[
i] <= consdata->weights[
i - 1]);
8399 consdata->sorted =
TRUE;
8458 oldnchgsides = *nchgsides;
8463 assert(consdata->weightsum > consdata->capacity);
8464 assert(consdata->nvars >= 2);
8465 assert(consdata->sorted);
8468 assert(consdata->merged);
8470 nvars = consdata->nvars;
8471 weights = consdata->weights;
8472 capacity = consdata->capacity;
8474 oldnchgcoefs = *nchgcoefs;
8477 if( weights[
nvars - 1] + weights[
nvars - 2] > capacity )
8505 if( consdata->weightsum - weights[
nvars - 1] <= consdata->capacity )
8515 if( consdata->weightsum - capacity > weights[0] + weights[1] )
8536 while( v <
nvars && weights[v] + weights[
nvars - 1] > capacity )
8544 while( v <
nvars && exceedsum <= capacity )
8546 exceedsum += weights[v];
8551 if( exceedsum > capacity )
8562 for( v = 0; v < vbig; ++v )
8564 if( weights[v] > newweight )
8572 for( ; v <
nvars; ++v )
8574 if( weights[v] > 1 )
8581 consdata->capacity = newweight;
8587 for( v =
nvars - 1; v > 0; --v )
8588 assert(weights[v] <= weights[v-1]);
8599 int nexceed = v - vbig;
8605 exceedsumback += weights[
w];
8612 if( exceedsumback > capacity )
8617 assert(exceedsumback - weights[
nvars - 1] <= capacity);
8620 for( v = 0; v < vbig; ++v )
8622 if( weights[v] > newweight )
8630 for( ; v <
nvars; ++v )
8632 if( weights[v] > 1 )
8639 consdata->capacity = newweight;
8645 for( v =
nvars - 1; v > 0; --v )
8646 assert(weights[v] <= weights[v-1]);
8675 for( v = 0; v < vbig; ++v )
8676 resweightsum -= weights[v];
8678 assert(exceedsum == resweightsum);
8683 for( v = 0; v < vbig; ++v )
8685 if( weights[v] > newweight )
8693 for( ; v <
nvars; ++v )
8695 if( weights[v] > 1 )
8702 consdata->capacity = newweight;
8708 for( v =
nvars - 1; v > 0; --v )
8709 assert(weights[v] <= weights[v-1]);
8717 dualcapacity = consdata->weightsum - capacity;
8727 while( weights[v] > dualcapacity )
8729 reductionsum += (weights[v] - dualcapacity);
8737 while( v <
nvars && weights[v] == dualcapacity )
8745 if( v >=
nvars - 1 )
8748 if( v ==
nvars - 1 )
8762 if( weights[
nvars - 1] + weights[
nvars - 2] >= dualcapacity )
8776 if( v > 0 && weights[
nvars - 2] > 1 )
8781 for(
w = 0;
w < v; ++
w )
8783 if( weights[
w] > 2 )
8791 assert(weights[v - 1] == 2);
8799 if( weights[
w] > 1 )
8807 (*nchgcoefs) += ncoefchg;
8810 consdata->capacity = (-2 + v * 2 +
nvars - v);
8811 assert(consdata->capacity > 0);
8812 assert(weights[0] <= consdata->capacity);
8813 assert(consdata->weightsum > consdata->capacity);
8841 while( weights[v] > newweight )
8843 reductionsum += (weights[v] - newweight);
8848 (*nchgcoefs) += (v - startv);
8851 while( weights[v] == newweight )
8857 restsumweights += weights[
w];
8860 restsumweights = consdata->weightsum;
8862 if( restsumweights < dualcapacity )
8880 for( ;
w >= 0; --
w )
8881 assert(weights[
w] == dualcapacity);
8906 if( weights[
w] > 1 )
8918 for( ;
w >= startv; --
w )
8920 if( weights[
w] > newweight )
8926 assert(weights[
w] == newweight);
8932 for( ;
w >= 0; --
w )
8934 if( weights[
w] > newweight )
8940 assert(weights[
w] == newweight);
8945 if( consdata->capacity > newcap )
8947 consdata->capacity = newcap;
8951 assert(consdata->capacity == newcap);
8963 assert(weights[
w] <= weights[
w - 1]);
8970 while( end >= 0 && weights[end] == weights[end + 1] )
8982 if( 2 * weights[end] > dualcapacity )
8988 restsumweights += weights[
w];
8990 if( restsumweights * 2 <= dualcapacity )
8993 while( v < end && restsumweights + weights[v] >= dualcapacity )
9000 if( (dualcapacity & 1) == 0 )
9002 newweight = dualcapacity / 2;
9005 for( ; v <= end; ++v )
9007 if( weights[v] > newweight )
9009 reductionsum += (weights[v] - newweight);
9024 for(
w = 0;
w < v; ++
w )
9029 newweight = dualcapacity;
9031 for( ; v <= end; ++v )
9033 reductionsum += (2 * weights[v] - newweight);
9042 (*nchgcoefs) +=
nvars;
9045 consdata->capacity *= 2;
9060 for( k = 0; k < 4; ++k )
9066 sumcoef = weights[
nvars - 1] + weights[
nvars - 2];
9070 sumcoef = weights[
nvars - 1] + weights[
nvars - 3];
9077 sumcoef = weights[
nvars - 1] + weights[
nvars - 4];
9081 sumcoefcase =
FALSE;
9082 sumcoef = weights[
nvars - 2] + weights[
nvars - 3];
9101 minweight = weights[end];
9102 while( minweight <= sumcoef )
9104 newweight = dualcapacity - minweight;
9110 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9112 reductionsum += (weights[v] - newweight);
9117 (*nchgcoefs) += (v - startv);
9120 while( weights[v] + minweight == dualcapacity )
9128 while( end >= 0 && weights[end] == weights[end + 1] )
9134 minweight = weights[end];
9141 if( sumcoef < minweight )
9143 minweight = sumcoef;
9144 newweight = dualcapacity - minweight;
9149 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9151 reductionsum += (weights[v] - newweight);
9156 (*nchgcoefs) += (v - startv);
9159 while( weights[v] + minweight == dualcapacity )
9170 if( 2 * weights[end] > dualcapacity )
9176 restsumweights += weights[
w];
9178 if( restsumweights * 2 <= dualcapacity )
9181 while( v < end && restsumweights + weights[v] >= dualcapacity )
9188 if( (dualcapacity & 1) == 0 )
9190 newweight = dualcapacity / 2;
9193 for( ; v <= end; ++v )
9195 if( weights[v] > newweight )
9197 reductionsum += (weights[v] - newweight);
9212 for(
w = 0;
w < v; ++
w )
9217 newweight = dualcapacity;
9219 for( ; v <= end; ++v )
9221 reductionsum += (2 * weights[v] - newweight);
9230 (*nchgcoefs) +=
nvars;
9233 consdata->capacity *= 2;
9242 if( 2 * sumcoef > dualcapacity )
9250 if( reductionsum > 0 )
9254 consdata->capacity -= reductionsum;
9257 assert(consdata->weightsum - dualcapacity == consdata->capacity);
9259 assert(weights[0] <= consdata->capacity);
9266 assert(weights[
w] <= weights[
w - 1]);
9269 if( oldnchgcoefs < *nchgcoefs )
9278 assert(oldnchgcoefs == *nchgcoefs);
9279 assert(oldnchgsides == *nchgsides);
9314 nvars = consdata->nvars;
9319 assert(consdata->capacity >= 0);
9330 vars = consdata->vars;
9331 weights = consdata->weights;
9332 capacity = consdata->capacity;
9336 while( v <
nvars && weights[v] > capacity )
9359 for( --v; v >= 0; --v )
9368 assert(weights == consdata->weights);
9370 assert(consdata->sorted);
9371 assert(weights[0] <= capacity);
9450 assert(consdata->merged);
9454 assert(consdata->capacity >= 0);
9476 weights = consdata->weights;
9477 nvars = consdata->nvars;
9481 for( v =
nvars - 1; v > 0; --v )
9482 assert(weights[v] <= weights[v-1]);
9486 gcd = weights[
nvars - 1];
9487 for( v =
nvars - 2; v >= 0 && gcd > 1; --v )
9495 for( v =
nvars - 1; v >= 0; --v )
9499 (*nchgcoefs) +=
nvars;
9501 consdata->capacity /= gcd;
9510 for( v =
nvars - 1; v > 0; --v )
9511 assert(weights[v] <= weights[v-1]);
9520 vars = consdata->vars;
9521 weights = consdata->weights;
9522 nvars = consdata->nvars;
9525 if( weights[
nvars - 1] == 1 && weights[
nvars - 2] == 1 )
9532 while( weights[v] == consdata->capacity )
9539 if( v ==
nvars - 1 )
9551 for( v =
nvars - 1; v >= offsetv; --v )
9553 weight = weights[v];
9581 if( v ==
nvars - 2 )
9587 if( candpos == v + 1 && candpos2 == v + 2 )
9614 assert(((candpos >= offsetv) || (candpos == -1 && offsetv > 0)) && candpos <
nvars);
9617 rest = consdata->capacity % gcd;
9627 consdata->capacity -= rest;
9631 for( v = 0; v < offsetv; ++v )
9636 *nchgcoefs += offsetv;
9641 restweight = weights[candpos] % gcd;
9643 assert(restweight < gcd);
9646 if( restweight > rest )
9647 newweight = weights[candpos] - restweight + gcd;
9649 newweight = weights[candpos] - restweight;
9653 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);
9658 if( newweight == 0 && offsetv > 0 )
9664 consdata->capacity -= rest;
9668 for( v = 0; v < offsetv; ++v )
9673 *nchgcoefs += offsetv;
9676 if( newweight == 0 )
9692 assert(consdata->weights == weights);
9696 for( v =
nvars - 1; v >= 0; --v )
9700 (*nchgcoefs) +=
nvars;
9702 consdata->capacity /= gcd;
9707 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));
9709 while(
nvars >= 2 );
9747 assert(*nzeroitems <= *zeroitemssize);
9751 nzeros = *nzeroitems;
9754 if( nzeros == *zeroitemssize )
9761 SCIPdebugMsg(
scip,
"memory limit of %d bytes reached in knapsack preprocessing - abort collecting zero items\n",
9763 *memlimitreached =
TRUE;
9766 *zeroitemssize *= 2;
9771 assert(nzeros < *zeroitemssize);
9773 if( *memlimitreached )
9774 *memlimitreached =
FALSE;
9777 (*zeroitems)[nzeros] = knapsackidx;
9778 (*nextidxs)[nzeros] = firstidxs[value][probindex];
9779 if( firstidxs[value][probindex] == 0 )
9781 liftcands[value][nliftcands[value]] = probindex;
9782 ++nliftcands[value];
9784 firstidxs[value][probindex] = nzeros;
9786 zeroweightsums[value][probindex] += knapsackweight;
9791#define MAX_CLIQUELENGTH 50
9853 assert(consdata->weightsum > consdata->capacity);
9854 assert(consdata->nvars > 0);
9855 assert(consdata->merged);
9857 nvars = consdata->nvars;
9885 assert(conshdlrdata->ints1size > 0);
9886 assert(conshdlrdata->ints2size > 0);
9887 assert(conshdlrdata->longints1size > 0);
9888 assert(conshdlrdata->longints2size > 0);
9894 if( conshdlrdata->ints1size < nbinvars )
9896 int oldsize = conshdlrdata->ints1size;
9898 conshdlrdata->ints1size = nbinvars;
9902 if( conshdlrdata->ints2size < nbinvars )
9904 int oldsize = conshdlrdata->ints2size;
9906 conshdlrdata->ints2size = nbinvars;
9910 if( conshdlrdata->longints1size < nbinvars )
9912 int oldsize = conshdlrdata->longints1size;
9914 conshdlrdata->longints1size = nbinvars;
9916 BMSclearMemoryArray(&(conshdlrdata->longints1[oldsize]), conshdlrdata->longints1size - oldsize);
9918 if( conshdlrdata->longints2size < nbinvars )
9920 int oldsize = conshdlrdata->longints2size;
9922 conshdlrdata->longints2size = nbinvars;
9924 BMSclearMemoryArray(&(conshdlrdata->longints2[oldsize]), conshdlrdata->longints2size - oldsize);
9927 firstidxs[0] = conshdlrdata->ints1;
9928 firstidxs[1] = conshdlrdata->ints2;
9929 zeroweightsums[0] = conshdlrdata->longints1;
9930 zeroweightsums[1] = conshdlrdata->longints2;
9934 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
9936 assert(firstidxs[0][tmp] == 0);
9937 assert(firstidxs[1][tmp] == 0);
9938 assert(zeroweightsums[0][tmp] == 0);
9939 assert(zeroweightsums[1][tmp] == 0);
9952 assert(conshdlrdata->bools1size > 0);
9953 assert(conshdlrdata->bools2size > 0);
9959 if( conshdlrdata->bools1size < nbinvars )
9961 int oldsize = conshdlrdata->bools1size;
9963 conshdlrdata->bools1size = nbinvars;
9965 BMSclearMemoryArray(&(conshdlrdata->bools1[oldsize]), conshdlrdata->bools1size - oldsize);
9967 if( conshdlrdata->bools2size < nbinvars )
9969 int oldsize = conshdlrdata->bools2size;
9971 conshdlrdata->bools2size = nbinvars;
9973 BMSclearMemoryArray(&(conshdlrdata->bools2[oldsize]), conshdlrdata->bools2size - oldsize);
9976 zeroiteminserted[0] = conshdlrdata->bools1;
9977 zeroiteminserted[1] = conshdlrdata->bools2;
9981 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
9983 assert(zeroiteminserted[0][tmp] == 0);
9984 assert(zeroiteminserted[1][tmp] == 0);
9998 memlimitreached =
FALSE;
9999 for(
i = 0;
i < consdata->nvars && !memlimitreached; ++
i )
10012 var = consdata->vars[
i];
10013 weight = consdata->weights[
i];
10017 assert(0 <= varprobindex && varprobindex < nbinvars);
10020 zeroweightsums[!value][varprobindex] += weight;
10021 tmpboolindices3[tmp3] = !value;
10022 tmpindices3[tmp3] = varprobindex;
10032 assert(0 <= probindex && probindex < nbinvars);
10034 implvalue = !value;
10037 assert( !zeroiteminserted[implvalue][probindex] );
10039 if( firstidxs[implvalue][probindex] == 0 )
10041 tmpboolindices2[tmp2] = implvalue;
10042 tmpindices2[tmp2] = probindex;
10046 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue,
i, weight,
10047 &memlimitreached) );
10048 zeroiteminserted[implvalue][probindex] =
TRUE;
10049 tmpboolindices[tmp] = implvalue;
10050 tmpindices[tmp] = probindex;
10057 for( j = 0; j < ncliques && !memlimitreached; ++j )
10073 for( k = ncliquevars - 1; k >= 0; --k )
10078 if(
var == cliquevars[k] )
10082 if( probindex == -1 )
10085 assert(0 <= probindex && probindex < nbinvars);
10086 implvalue = cliquevalues[k];
10089 if( !zeroiteminserted[implvalue][probindex] )
10091 if( firstidxs[implvalue][probindex] == 0 )
10093 tmpboolindices2[tmp2] = implvalue;
10094 tmpindices2[tmp2] = probindex;
10099 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue,
i, weight,
10100 &memlimitreached) );
10101 zeroiteminserted[implvalue][probindex] =
TRUE;
10102 tmpboolindices[tmp] = implvalue;
10103 tmpindices[tmp] = probindex;
10106 if( memlimitreached )
10112 for( --tmp; tmp >= 0; --tmp)
10113 zeroiteminserted[tmpboolindices[tmp]][tmpindices[tmp]] =
FALSE;
10118 assert(consdata->sorted);
10121 assert(conshdlrdata->bools3size > 0);
10127 if( conshdlrdata->bools3size < consdata->nvars )
10129 int oldsize = conshdlrdata->bools3size;
10131 conshdlrdata->bools3size = consdata->nvars;;
10133 BMSclearMemoryArray(&(conshdlrdata->bools3[oldsize]), conshdlrdata->bools3size - oldsize);
10136 cliqueused = conshdlrdata->bools3;
10140 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10141 assert(cliqueused[tmp] == 0);
10144 maxcliqueweightsum = 0;
10148 for(
i = 0;
i < consdata->nvars; ++
i )
10150 cliquenum = consdata->cliquepartition[
i];
10151 assert(0 <= cliquenum && cliquenum < consdata->
nvars);
10153 if( !cliqueused[cliquenum] )
10155 maxcliqueweightsum += consdata->weights[
i];
10156 cliqueused[cliquenum] =
TRUE;
10157 tmpindices[tmp] = cliquenum;
10162 for( --tmp; tmp >= 0; --tmp)
10163 cliqueused[tmp] =
FALSE;
10165 assert(conshdlrdata->bools4size > 0);
10171 if( conshdlrdata->bools4size < consdata->nvars )
10173 int oldsize = conshdlrdata->bools4size;
10175 conshdlrdata->bools4size = consdata->nvars;
10180 itemremoved = conshdlrdata->bools4;
10184 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10185 assert(itemremoved[tmp] == 0);
10196 for( val = 0; val < 2 && addweightsum < consdata->capacity; ++val )
10198 for(
i = 0;
i < nliftcands[val] && addweightsum < consdata->capacity; ++
i )
10207 probindex = liftcands[val][
i];
10208 assert(0 <= probindex && probindex < nbinvars);
10211 if( firstidxs[val][probindex] == 0
10212 || maxcliqueweightsum - zeroweightsums[val][probindex] + addweightsum >= consdata->capacity )
10216 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10218 assert(0 < idx && idx < nzeroitems);
10219 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10220 itemremoved[zeroitems[idx]] =
TRUE;
10224 cliqueweightsum = addweightsum;
10225 for( j = 0; j < consdata->nvars; ++j )
10227 cliquenum = consdata->cliquepartition[j];
10228 assert(0 <= cliquenum && cliquenum < consdata->
nvars);
10229 if( !itemremoved[j] )
10231 if( !cliqueused[cliquenum] )
10233 cliqueweightsum += consdata->weights[j];
10234 cliqueused[cliquenum] =
TRUE;
10235 tmpindices[tmp] = cliquenum;
10239 if( cliqueweightsum >= consdata->capacity )
10245 if( cliqueweightsum < consdata->capacity )
10251 assert(naddvars < 2*nbinvars);
10252 var = binvars[probindex];
10257 weight = consdata->capacity - cliqueweightsum;
10258 addvars[naddvars] =
var;
10259 addweights[naddvars] = weight;
10260 addweightsum += weight;
10268 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10270 assert(0 < idx && idx < nzeroitems);
10271 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10272 itemremoved[zeroitems[idx]] =
FALSE;
10275 for( --tmp; tmp >= 0; --tmp)
10276 cliqueused[tmpindices[tmp]] =
FALSE;
10281 for( --tmp3; tmp3 >= 0; --tmp3)
10282 zeroweightsums[tmpboolindices3[tmp3]][tmpindices3[tmp3]] = 0;
10285 for( --tmp2; tmp2 >= 0; --tmp2)
10287 zeroweightsums[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10288 firstidxs[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10292 for(
i = 0;
i < naddvars; ++
i )
10296 *nchgcoefs += naddvars;
10404 assert(consdata->onesweightsum == 0);
10405 assert(consdata->weightsum > consdata->capacity);
10406 assert(consdata->nvars > 0);
10417 assert(consdata->merged);
10422 for(
i = 0;
i < consdata->nvars; ++
i )
10426 weight = consdata->weights[
i];
10427 if( consdata->weightsum - weight < consdata->capacity )
10429 newweight = consdata->weightsum - consdata->capacity;
10431 consdata->capacity -= (weight - newweight);
10434 assert(!consdata->sorted);
10437 consdata->capacity + (weight-newweight), consdata->capacity);
10443 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10447 if( consdata->weightsum <= consdata->capacity )
10451 while( pos < consdata->
nvars && consdata->weights[pos] == consdata->capacity )
10455 weights = consdata->weights;
10456 nvars = consdata->nvars;
10457 capacity = consdata->capacity;
10460 pos <
nvars && weights[pos] + weights[pos + 1] > capacity )
10467 for( k = 0; k < 4; ++k )
10469 newweight = capacity - sumcoef;
10475 sumcoef = weights[
nvars - 1];
10476 backpos =
nvars - 1;
10479 sumcoef = weights[
nvars - 2];
10480 backpos =
nvars - 2;
10485 sumcoefcase =
TRUE;
10486 sumcoef = weights[
nvars - 3];
10487 backpos =
nvars - 3;
10491 sumcoefcase =
FALSE;
10492 sumcoef = weights[
nvars - 1] + weights[
nvars - 2];
10493 backpos =
nvars - 2;
10502 sumcoef = weights[
nvars - 4];
10503 backpos =
nvars - 4;
10507 sumcoef = weights[
nvars - 1] + weights[
nvars - 2];
10508 backpos =
nvars - 2;
10513 sumcoef = weights[
nvars - 3];
10514 backpos =
nvars - 3;
10519 if( backpos <= pos )
10523 maxweight = weights[pos];
10525 while( 2 * maxweight > capacity && maxweight + sumcoef > capacity )
10527 assert(newweight > weights[pos]);
10537 maxweight = weights[pos];
10539 if( backpos <= pos )
10542 (*nchgcoefs) += (pos - startpos);
10545 while( pos <
nvars && weights[pos] + sumcoef == capacity )
10556 if( pos + 1 == backpos && weights[pos] > sumcoef &&
10557 ((k == 0) || (k == 1 && weights[
nvars - 1] + sumcoef + weights[pos] > capacity)) )
10559 newweight = capacity - sumcoef;
10560 assert(newweight > weights[pos]);
10570 if( backpos <= pos )
10579 && consdata->nvars - pos <= MAX_USECLIQUES_SIZE && consdata->
nvars >= 2 && pos > 0
10580 && (
SCIP_Longint)consdata->nvars - pos <= consdata->capacity
10581 && consdata->weights[pos - 1] == consdata->capacity
10582 && ( pos == consdata->nvars || consdata->weights[pos] == 1 ) )
10596 if( pos == consdata->nvars )
10618 len = consdata->nvars - pos;
10629 for(
w = 0;
w < nclq; ++
w )
10639 for(
w = pos - 1;
w >= 0; --
w )
10640 clqvars[
w] = consdata->vars[
w];
10643 for(
c = 0;
c < nclq; ++
c )
10647 for(
w =
c;
w < len; ++
w )
10649 if( clqpart[
w] ==
c )
10651 assert(nclqvars < pos + len - nclq + 1);
10652 clqvars[nclqvars] = consdata->vars[
w + pos];
10687 int* newweightidxs;
10701 assert(consdata->merged);
10710 if( consdata->cliquepartition[consdata->nvars - 1] == consdata->nvars - 1 )
10714 cliqueweightsum = 0;
10717 for(
i = 0;
i < consdata->nvars; ++
i )
10721 cliquenum = consdata->cliquepartition[
i];
10722 assert(0 <= cliquenum && cliquenum <= ncliques);
10724 weight = consdata->weights[
i];
10727 if( cliquenum == ncliques )
10729 maxcliqueweights[ncliques] = weight;
10730 cliqueweightsum += weight;
10734 assert(maxcliqueweights[cliquenum] >= weight);
10738 zeroweights =
FALSE;
10739 for(
i = 0;
i < ncliques; ++
i )
10743 delta = consdata->capacity - (cliqueweightsum - maxcliqueweights[
i]);
10756 SCIPconsGetName(cons),
i, maxcliqueweights[
i], cliqueweightsum, consdata->capacity, delta);
10757 newcapacity = consdata->capacity - delta;
10758 forceclique =
FALSE;
10761 newmincliqueweight = newcapacity + 1;
10762 for( j = 0; j <
i; ++j )
10763 assert(consdata->cliquepartition[j] <
i);
10765 for( j =
i; j < consdata->nvars; ++j )
10767 if( consdata->cliquepartition[j] ==
i )
10769 newweight = consdata->weights[j] - delta;
10770 newweight =
MAX(newweight, 0);
10774 newweightvals[nnewweights] = newweight;
10775 newweightidxs[nnewweights] = j;
10779 assert(newweight <= newmincliqueweight);
10780 newmincliqueweight = newweight;
10786 if( nnewweights > 1 )
10789 j = newweightidxs[nnewweights - 2];
10791 assert(consdata->cliquepartition[j] ==
i);
10792 j = newweightidxs[nnewweights - 1];
10794 assert(consdata->cliquepartition[j] ==
i);
10797 newminweightsuminclique = newweightvals[nnewweights - 2];
10798 newminweightsuminclique += newweightvals[nnewweights - 1];
10805 if( newminweightsuminclique <= newcapacity )
10806 forceclique =
TRUE;
10810 if( conshdlrdata->disaggregation || !forceclique )
10813 consdata->capacity, newcapacity, forceclique);
10814 consdata->capacity = newcapacity;
10817 for( k = 0; k < nnewweights; ++k )
10819 j = newweightidxs[k];
10821 assert(consdata->cliquepartition[j] ==
i);
10825 SCIPvarGetName(consdata->vars[j]), consdata->weights[j], newweightvals[k]);
10828 assert(!consdata->sorted);
10829 zeroweights = zeroweights || (newweightvals[k] == 0);
10843 for( k = 0; k < nnewweights; ++k )
10844 cliquevars[k] = consdata->vars[newweightidxs[k]];
10871 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10879 if( consdata->weightsum <= consdata->capacity )
10891 if( consdata->weightsum <= consdata->capacity )
10897 assert(consdata->merged);
10899 minweight = consdata->weights[consdata->nvars-1];
10900 for(
i = 0;
i < consdata->nvars-1; ++
i )
10904 weight = consdata->weights[
i];
10905 assert(weight >= minweight);
10906 if( minweight + weight > consdata->capacity )
10908 if( weight < consdata->capacity )
10912 assert(consdata->sorted);
10914 assert(
i == 0 || consdata->weights[
i-1] >= consdata->weights[
i]);
10915 consdata->sorted =
TRUE;
10924 if( consdata->nvars >= 2 )
10928 minweight = consdata->weights[consdata->nvars-2];
10929 weight = consdata->weights[consdata->nvars-1];
10930 assert(minweight >= weight);
10931 if( minweight + weight > consdata->capacity && weight < consdata->capacity )
10935 assert(consdata->sorted);
10937 assert(minweight >= consdata->weights[consdata->nvars-1]);
10938 consdata->sorted =
TRUE;
10957 for(
b = 0;
b < ncliquevars; ++
b )
10978 int* gaincliquepartition;
10984 int nposcliquevars;
10988 int lastcliqueused;
11003 nvars = consdata->nvars;
11006 if( consdata->cliquesadded ||
nvars == 0 )
11017 assert(consdata->merged);
11024 nnegcliques = consdata->nnegcliques;
11027 if( nnegcliques ==
nvars )
11039 minactduetonegcliques = 0;
11042 for( v = 0; v <
nvars; ++v )
11044 assert(0 <= consdata->negcliquepartition[v] && consdata->negcliquepartition[v] <= nnegcliques);
11045 assert(consdata->weights[v] > 0);
11047 if( consdata->negcliquepartition[v] == nnegcliques )
11050 maxweights[consdata->negcliquepartition[v]] = consdata->weights[v];
11053 minactduetonegcliques += consdata->weights[v];
11056 nposcliquevars = 0;
11059 if( minactduetonegcliques > 0 )
11062 freecapacity = consdata->capacity - minactduetonegcliques;
11066 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
11069 for( v = 0; v <
nvars; ++v )
11071 if( !cliqueused[consdata->negcliquepartition[v]] )
11073 cliqueused[consdata->negcliquepartition[v]] =
TRUE;
11078 if( consdata->negcliquepartition[v] == consdata->negcliquepartition[
w]
11079 && consdata->weights[v] > consdata->weights[
w] )
11081 poscliquevars[nposcliquevars] = consdata->vars[
w];
11082 gainweights[nposcliquevars] = maxweights[consdata->negcliquepartition[v]] - consdata->weights[
w];
11083 gaincliquepartition[nposcliquevars] = consdata->negcliquepartition[v];
11091 if( nposcliquevars > 0 )
11096 for( v = 0; v < nposcliquevars; ++v )
11100 lastweight = gainweights[v];
11101 beforelastweight = -1;
11102 lastcliqueused = gaincliquepartition[v];
11105 cliqueused[gaincliquepartition[v]] =
TRUE;
11111 beforelastweight = lastweight;
11112 lastweight = gainweights[
w];
11113 lastcliqueused = gaincliquepartition[
w];
11114 cliqueused[gaincliquepartition[
w]] =
TRUE;
11119 if( ncliquevars > 1 )
11121 SCIPdebug( printClique(cliquevars, ncliquevars) );
11122 assert(beforelastweight > 0);
11128 *nbdchgs += thisnbdchgs;
11131 cliqueused[lastcliqueused] =
FALSE;
11137 SCIPdebug( printClique(cliquevars, ncliquevars) );
11141 *nbdchgs += thisnbdchgs;
11188 if( ! sorteditems )
11192 lastweight = weights[0];
11197 lastweight = weights[
i];
11201 if( ncliquevars > 1 )
11205 int compareweightidx;
11210 SCIPdebug( printClique(items, ncliquevars) );
11216 *nbdchgs += thisnbdchgs;
11217 nnzadded = ncliquevars;
11220 if( ncliquevars == nitems )
11228 compareweightidx = ncliquevars - 2;
11229 assert(
i == nitems || weights[
i] + weights[ncliquevars - 1] <= capacity);
11232 minclqsize = (int)(cliqueextractfactor * ncliquevars);
11233 minclqsize =
MAX(minclqsize, 2);
11237 while( compareweightidx >= 0 &&
i < nitems && ! (*
cutoff)
11238 && ncliquevars >= minclqsize
11239 && nnzadded <= 2 * nitems
11242 compareweight = weights[compareweightidx];
11243 assert(compareweight > 0);
11246 if( compareweight + weights[
i] > capacity )
11248 assert(compareweightidx == ncliquevars -2);
11249 cliquevars[ncliquevars - 1] = items[
i];
11250 SCIPdebug( printClique(cliquevars, ncliquevars) );
11253 nnzadded += ncliquevars;
11257 *nbdchgs += thisnbdchgs;
11265 compareweightidx--;
11295 int nposcliquevars;
11309 nvars = consdata->nvars;
11312 if( consdata->cliquesadded ||
nvars == 0 )
11323 assert(consdata->merged);
11330 nnegcliques = consdata->nnegcliques;
11340 minactduetonegcliques = 0;
11343 if( nnegcliques <
nvars )
11351 cliquenum = consdata->negcliquepartition[
i];
11352 assert(0 <= cliquenum && cliquenum <= nnegcliques);
11354 weight = consdata->weights[
i];
11357 if( cliquenum == nnegcliques )
11361 minactduetonegcliques += weight;
11362 if( secondmaxweights[cliquenum] == 0 )
11363 secondmaxweights[cliquenum] = weight;
11369 if( minactduetonegcliques > 0 )
11372 freecapacity = consdata->capacity - minactduetonegcliques;
11376 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
11384 nposcliquevars = 0;
11389 cliquenum = consdata->negcliquepartition[
i];
11390 if( consdata->weights[
i] > secondmaxweights[cliquenum] )
11392 poscliquevars[nposcliquevars] = consdata->vars[
i];
11393 gainweights[nposcliquevars] = consdata->weights[
i] - secondmaxweights[cliquenum];
11399 if( nposcliquevars > 1 )
11416 consdata->cliquesadded =
TRUE;
11445 assert(consdata1->sorted);
11446 assert(consdata2->sorted);
11453 if( consdata1->nvars != consdata2->nvars )
11456 for(
i = consdata1->nvars - 1;
i >= 0; --
i )
11459 if( consdata1->vars[
i] != consdata2->vars[
i] )
11468 if( consdata1->weights[
i] != consdata2->weights[
i] )
11483 uint64_t firstweight;
11490 assert(consdata->nvars > 0);
11503 assert(minidx >= 0 && mididx >= 0 && maxidx >= 0);
11506 firstweight = (uint64_t)consdata->weights[0];
11507 return SCIPhashSix(consdata->nvars, minidx, mididx, maxidx, firstweight>>32, firstweight);
11533 hashtablesize = nconss;
11536 hashGetKeyKnapsackcons, hashKeyEqKnapsackcons, hashKeyValKnapsackcons, (
void*)
scip) );
11539 for(
c = nconss - 1;
c >= 0; --
c )
11552 if( consdata0->nvars == 0 )
11554 if( consdata0->capacity < 0 )
11570 if( cons1 !=
NULL )
11585 assert(consdata0->nvars > 0 && consdata0->nvars == consdata1->nvars);
11587 assert(consdata0->sorted && consdata1->sorted);
11588 assert(consdata0->vars[0] == consdata1->vars[0]);
11589 assert(consdata0->weights[0] == consdata1->weights[0]);
11591 SCIPdebugMsg(
scip,
"knapsack constraints <%s> and <%s> with equal coefficients\n",
11595 if( consdata0->capacity < consdata1->capacity )
11652 assert(firstchange <= chkind);
11656 cons0 = conss[chkind];
11663 assert(consdata0->nvars >= 1);
11664 assert(consdata0->merged);
11670 if( consdata0->capacity == 0 )
11697 assert(consdata1->nvars >= 1);
11698 assert(consdata1->merged);
11704 if( consdata1->capacity == 0 )
11709 if( consdata0->nvars > consdata1->nvars )
11711 iscons0incons1contained =
FALSE;
11712 iscons1incons0contained =
TRUE;
11713 v = consdata1->nvars - 1;
11715 else if( consdata0->nvars < consdata1->nvars )
11717 iscons0incons1contained =
TRUE;
11718 iscons1incons0contained =
FALSE;
11719 v = consdata0->nvars - 1;
11723 iscons0incons1contained =
TRUE;
11724 iscons1incons0contained =
TRUE;
11725 v = consdata0->nvars - 1;
11736 v0 = consdata0->nvars - 1;
11737 v1 = consdata1->nvars - 1;
11741 assert(iscons0incons1contained || iscons1incons0contained);
11746 iscons1incons0contained =
FALSE;
11747 if( !iscons0incons1contained )
11753 iscons0incons1contained =
FALSE;
11754 if( !iscons1incons0contained )
11758 assert(v == v0 || v == v1);
11763 if( consdata0->vars[v0] == consdata1->vars[v1] )
11768 iscons1incons0contained =
FALSE;
11769 if( !iscons0incons1contained )
11775 iscons0incons1contained =
FALSE;
11776 if( !iscons1incons0contained )
11786 if( iscons0incons1contained && iscons1incons0contained )
11788 iscons0incons1contained =
FALSE;
11789 iscons1incons0contained =
FALSE;
11792 assert(iscons0incons1contained ? (v1 >= v0) : iscons1incons0contained);
11793 assert(iscons1incons0contained ? (v1 <= v0) : iscons0incons1contained);
11795 if( iscons0incons1contained )
11804 assert(!iscons1incons0contained || !iscons0incons1contained || v0 == -1 || v1 == -1);
11806 if( iscons1incons0contained )
11817 else if( iscons0incons1contained )
11855 SCIPdebugMsg(
scip,
"knapsack enforcement of %d/%d constraints for %s solution\n", nusefulconss, nconss,
11856 sol ==
NULL ?
"LP" :
"relaxation");
11861 maxncuts = (
SCIPgetDepth(
scip) == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
11864 for(
i = 0;
i < nusefulconss && ncuts < maxncuts && !
cutoff;
i++ )
11876 for(
i = nusefulconss;
i < nconss && ncuts == 0 && !
cutoff;
i++ )
11890 else if ( ncuts > 0 )
11966 for( v = 0; v <
nvars; ++v )
11972 transvars[v] =
vars[v];
11973 weights[v] = weight;
11978 weights[v] = -weight;
11979 capacity -= weight;
11986 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
12010 upgrade = (nposbin + nnegbin + nposimplbin + nnegimplbin ==
nvars)
12011 && (ncoeffspone + ncoeffsnone + ncoeffspint + ncoeffsnint ==
nvars)
12060 nlocvars = consdata->nvars;
12065 for(
i = 0;
i < consdata->nvars; ++
i )
12067 vars[
i] = consdata->vars[
i];
12143 conshdlrdata->reals1size =
nvars;
12161 conshdlrdata->reals1size = 0;
12193 conshdlrdata->ints1size =
nvars;
12194 conshdlrdata->ints2size =
nvars;
12195 conshdlrdata->longints1size =
nvars;
12196 conshdlrdata->longints2size =
nvars;
12197 conshdlrdata->bools1size =
nvars;
12198 conshdlrdata->bools2size =
nvars;
12199 conshdlrdata->bools3size =
nvars;
12200 conshdlrdata->bools4size =
nvars;
12202#ifdef WITH_CARDINALITY_UPGRADE
12203 conshdlrdata->upgradedcard =
FALSE;
12220 for(
c = 0;
c < nconss; ++
c )
12241 conshdlrdata->ints1size = 0;
12242 conshdlrdata->ints2size = 0;
12243 conshdlrdata->longints1size = 0;
12244 conshdlrdata->longints2size = 0;
12245 conshdlrdata->bools1size = 0;
12246 conshdlrdata->bools2size = 0;
12247 conshdlrdata->bools3size = 0;
12248 conshdlrdata->bools4size = 0;
12261 for(
c = 0;
c < nconss; ++
c )
12280 for(
c = 0;
c < nconss; ++
c )
12285 if( consdata->row !=
NULL )
12290 if( consdata->nlrow !=
NULL )
12345 sourcedata->nvars, sourcedata->vars, sourcedata->weights, sourcedata->capacity) );
12367 *infeasible =
FALSE;
12369 for(
i = 0;
i < nconss && !(*infeasible);
i++ )
12407 SCIPdebugMsg(
scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12408 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12411 if( (
depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12412 || (
depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12417 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12418 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12419 && ((sepacardfreq == 0 &&
depth == 0) || (sepacardfreq >= 1 && (
depth % sepacardfreq == 0)));
12425 maxbound = glblowerbound + conshdlrdata->maxcardbounddist * (cutoffbound - glblowerbound);
12426 sepacardinality = sepacardinality &&
SCIPisLE(
scip, loclowerbound, maxbound);
12430 maxsepacuts = (
depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12445 else if ( ncuts > 0 )
12476 SCIPdebugMsg(
scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12477 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12480 if( (
depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12481 || (
depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12486 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12487 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12488 && ((sepacardfreq == 0 &&
depth == 0) || (sepacardfreq >= 1 && (
depth % sepacardfreq == 0)));
12491 maxsepacuts = (
depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12506 else if( ncuts > 0 )
12537 for(
i = 0;
i < nconss;
i++ )
12591 for(
i = 0;
i < nmarkedconss && !
cutoff;
i++ )
12612 else if( nfixedvars > 0 )
12642 oldnfixedvars = *nfixedvars;
12643 oldnchgbds = *nchgbds;
12644 oldndelconss = *ndelconss;
12645 oldnaddconss = *naddconss;
12646 oldnchgcoefs = *nchgcoefs;
12647 oldnchgsides = *nchgsides;
12648 firstchange = INT_MAX;
12650 newchanges = (nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 || nnewupgdconss > 0);
12657 int thisnfixedvars;
12666 if( newchanges || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
12675 consdata->presolvedtiming = 0;
12676 else if( consdata->presolvedtiming >= presoltiming )
12681 consdata->presolvedtiming = presoltiming;
12683 thisnfixedvars = *nfixedvars;
12684 thisnchgbds = *nchgbds;
12714 if( *nfixedvars > thisnfixedvars || *nchgbds > thisnchgbds )
12720 thisnfixedvars = *nfixedvars;
12726 if( consdata->weightsum <= consdata->capacity )
12748 if( *nfixedvars > thisnfixedvars )
12789 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) || (*naddconss != oldnaddconss) )
12798 npaircomparisons = 0;
12799 oldndelconss = *ndelconss;
12800 oldnchgsides = *nchgsides;
12801 oldnchgcoefs = *nchgcoefs;
12815 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) )
12817 if( ((
SCIP_Real) (*ndelconss - oldndelconss) + ((
SCIP_Real) (*nchgsides - oldnchgsides))/2.0 +
12820 oldndelconss = *ndelconss;
12821 oldnchgsides = *nchgsides;
12822 oldnchgcoefs = *nchgcoefs;
12823 npaircomparisons = 0;
12827#ifdef WITH_CARDINALITY_UPGRADE
12845 noldupgdconss = *nupgdconss;
12858 for (makeupgrade = 0; makeupgrade < 2; ++makeupgrade)
12877 nvars = consdata->nvars;
12878 vars = consdata->vars;
12879 weights = consdata->weights;
12886 if ( consdata->capacity >=
nvars )
12890 assert( consdata->sorted );
12891 if ( weights[0] != 1 || weights[
nvars-1] != 1 )
12895 for (v = 0; v <
nvars; ++v)
12904 var = consdata->vars[v];
12921 for (j = 0; j < nimpls; ++j)
12935 cardvars[v] = implvars[j];
12952 if ( makeupgrade == 0 )
12954 for (v = 0; v <
nvars; ++v)
12978 for (v = 0; v <
nvars; ++v)
12988 conshdlrdata->upgradedcard =
TRUE;
13020 for (v = 0; v <
nvars; ++v)
13036 if ( *nupgdconss > noldupgdconss )
13043 else if( success || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
13067 for(
i = 0;
i < consdata->nvars; ++
i )
13084 if( inferinfo < 0 )
13091 if( inferinfo < consdata->
nvars && consdata->vars[inferinfo] == infervar )
13092 capsum = consdata->weights[inferinfo];
13095 for(
i = 0;
i < consdata->nvars && consdata->vars[
i] != infervar; ++
i )
13098 capsum = consdata->weights[
i];
13105 if( capsum <= consdata->capacity )
13107 for(
i = 0;
i < consdata->nvars;
i++ )
13112 capsum += consdata->weights[
i];
13113 if( capsum > consdata->capacity )
13145 for(
i = 0;
i < consdata->nvars;
i++)
13218 for(
i = 0;
i < consdata->nvars; ++
i )
13237 const char* consname;
13247 for( v = 0; v <
nvars; ++v )
13258 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode, global,
valid) );
13293 while( *str !=
'\0' )
13306 endptr = strchr(endptr,
'<');
13308 if( endptr ==
NULL )
13322 if( varssize <=
nvars )
13330 weights[
nvars] = weight;
13339 if( strncmp(str,
"<=", 2) != 0 )
13364 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
13383 if( varssize < consdata->
nvars )
13384 (*success) =
FALSE;
13405 (*nvars) = consdata->nvars;
13448 consdata->onesweightsum += eventdata->weight;
13449 consdata->presolvedtiming = 0;
13453 consdata->onesweightsum -= eventdata->weight;
13456 consdata->presolvedtiming = 0;
13460 if( !consdata->existmultaggr )
13469 consdata->existmultaggr =
TRUE;
13470 consdata->merged =
FALSE;
13474 consdata->merged =
FALSE;
13478 consdata->presolvedtiming = 0;
13481 consdata->varsdeleted =
TRUE;
13509 eventhdlrdata =
NULL;
13510 conshdlrdata->eventhdlr =
NULL;
13512 eventExecKnapsack, eventhdlrdata) );
13513 conshdlrdata->probtoidxmap =
NULL;
13514 conshdlrdata->probtoidxmapsize = 0;
13517 if( conshdlrdata->eventhdlr ==
NULL )
13526 consEnfolpKnapsack, consEnfopsKnapsack, consCheckKnapsack, consLockKnapsack,
13569 "multiplier on separation frequency, how often knapsack cuts are separated (-1: never, 0: only at root)",
13573 "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for separating knapsack cuts",
13577 "lower clique size limit for greedy clique extraction algorithm (relative to largest clique)",
13581 "maximal number of separation rounds per node (-1: unlimited)",
13585 "maximal number of separation rounds per node in the root node (-1: unlimited)",
13589 "maximal number of cuts separated per separation round",
13593 "maximal number of cuts separated per separation round in the root node",
13597 "should disaggregation of knapsack constraints be allowed in preprocessing?",
13601 "should presolving try to simplify knapsacks",
13605 "should negated clique information be used in solving process",
13609 "should pairwise constraint comparison be performed in presolving?",
13613 "should hash table be used for detecting redundant constraints in advance",
13617 "should dual presolving steps be performed?",
13621 "should GUB information be used for separation?",
13625 "should presolving try to detect constraints parallel to the objective function defining an upper bound and prevent these constraints from entering the LP?",
13629 "should presolving try to detect constraints parallel to the objective function defining a lower bound and prevent these constraints from entering the LP?",
13633 "should clique partition information be updated when old partition seems outdated?",
13637 "factor on the growth of global cliques to decide when to update a previous "
13638 "(negated) clique partition (used only if updatecliquepartitions is set to TRUE)",
13640#ifdef WITH_CARDINALITY_UPGRADE
13643 "if TRUE then try to update knapsack constraints to cardinality constraints",
13644 &conshdlrdata->upgdcardinality,
TRUE, DEFAULT_UPGDCARDINALITY,
NULL,
NULL) );
13694 if( conshdlr ==
NULL )
13720 SCIP_CALL(
SCIPcreateCons(
scip, cons, name, conshdlr, consdata, initial,
separate, enforce, check,
propagate,
13721 local, modifiable, dynamic, removable, stickingatnode) );
13801 return consdata->capacity;
13826 SCIPerrorMessage(
"method can only be called during problem creation stage\n");
13833 consdata->capacity = capacity;
13858 return consdata->nvars;
13881 return consdata->vars;
13904 return consdata->weights;
13927 if( consdata->row !=
NULL )
13953 if( consdata->row !=
NULL )
13981 return consdata->row;
14011 for(
i = 0;
i < consdata->nvars; ++
i )
14034 if( conshdlr ==
NULL )
14038 *infeasible =
FALSE;
14044 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)
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_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_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 (weighted) k-medians
methods for sorting joint arrays of various types
public methods for separators
public methods for problem variables
public methods for branching rule plugins and branching
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for cuts and aggregation rows
public methods for event handler plugins and event handlers
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
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