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]);
8194 assert(consdata->nvars >= 2);
8195 assert(consdata->weightsum > consdata->capacity);
8197 noldchgcoefs = *nchgcoefs;
8198 vars = consdata->vars;
8199 weights = consdata->weights;
8200 nvars = consdata->nvars;
8201 capacity = consdata->capacity;
8205 for( v = 0; v <
nvars && sum + weights[v] <= capacity; ++v )
8223 assert(consdata->nvars > 1);
8236 if( *nchgcoefs > noldchgcoefs )
8240 assert(weights == consdata->weights);
8242 assert(capacity == consdata->capacity);
8250 if( consdata->cliquepartition[v] < v )
8258 maxactduetoclqfront = 0;
8260 clqpart = consdata->cliquepartition;
8266 assert(clqpart[
w] >= 0 && clqpart[
w] <=
w);
8267 if( clqpart[
w] == cliquenum )
8269 if( maxactduetoclqfront + weights[
w] <= capacity )
8271 maxactduetoclqfront += weights[
w];
8277 sumfront += weights[
w];
8291 assert(maxactduetoclqfront <= capacity);
8295 ncliques = consdata->ncliques;
8300 for(
c = 0;
c < ncliques; ++
c )
8305 if( clqpart[
w] ==
c )
8307 clqvars[nclqvars] =
vars[
w];
8372 assert(consdata->onesweightsum == 0);
8373 assert(consdata->weightsum > consdata->capacity);
8374 assert(consdata->nvars >= 1);
8379 gcd = consdata->weights[consdata->nvars-1];
8380 for(
i = consdata->nvars-2;
i >= 0 && gcd >= 2; --
i )
8392 for(
i = 0;
i < consdata->nvars; ++
i )
8396 consdata->capacity /= gcd;
8397 (*nchgcoefs) += consdata->nvars;
8402 for(
i = consdata->nvars - 1;
i > 0; --
i )
8403 assert(consdata->weights[
i] <= consdata->weights[
i - 1]);
8405 consdata->sorted =
TRUE;
8464 oldnchgsides = *nchgsides;
8469 assert(consdata->weightsum > consdata->capacity);
8470 assert(consdata->nvars >= 2);
8471 assert(consdata->sorted);
8474 assert(consdata->merged);
8476 nvars = consdata->nvars;
8477 weights = consdata->weights;
8478 capacity = consdata->capacity;
8480 oldnchgcoefs = *nchgcoefs;
8483 if( weights[
nvars - 1] + weights[
nvars - 2] > capacity )
8511 if( consdata->weightsum - weights[
nvars - 1] <= consdata->capacity )
8521 if( consdata->weightsum - capacity > weights[0] + weights[1] )
8542 while( v <
nvars && weights[v] + weights[
nvars - 1] > capacity )
8550 while( v <
nvars && exceedsum <= capacity )
8552 exceedsum += weights[v];
8557 if( exceedsum > capacity )
8568 for( v = 0; v < vbig; ++v )
8570 if( weights[v] > newweight )
8578 for( ; v <
nvars; ++v )
8580 if( weights[v] > 1 )
8587 consdata->capacity = newweight;
8593 for( v =
nvars - 1; v > 0; --v )
8594 assert(weights[v] <= weights[v-1]);
8605 int nexceed = v - vbig;
8611 exceedsumback += weights[
w];
8618 if( exceedsumback > capacity )
8623 assert(exceedsumback - weights[
nvars - 1] <= capacity);
8626 for( v = 0; v < vbig; ++v )
8628 if( weights[v] > newweight )
8636 for( ; v <
nvars; ++v )
8638 if( weights[v] > 1 )
8645 consdata->capacity = newweight;
8651 for( v =
nvars - 1; v > 0; --v )
8652 assert(weights[v] <= weights[v-1]);
8681 for( v = 0; v < vbig; ++v )
8682 resweightsum -= weights[v];
8684 assert(exceedsum == resweightsum);
8689 for( v = 0; v < vbig; ++v )
8691 if( weights[v] > newweight )
8699 for( ; v <
nvars; ++v )
8701 if( weights[v] > 1 )
8708 consdata->capacity = newweight;
8714 for( v =
nvars - 1; v > 0; --v )
8715 assert(weights[v] <= weights[v-1]);
8723 dualcapacity = consdata->weightsum - capacity;
8733 while( weights[v] > dualcapacity )
8735 reductionsum += (weights[v] - dualcapacity);
8743 while( v <
nvars && weights[v] == dualcapacity )
8751 if( v >=
nvars - 1 )
8754 if( v ==
nvars - 1 )
8768 if( weights[
nvars - 1] + weights[
nvars - 2] >= dualcapacity )
8782 if( v > 0 && weights[
nvars - 2] > 1 )
8787 for(
w = 0;
w < v; ++
w )
8789 if( weights[
w] > 2 )
8797 assert(weights[v - 1] == 2);
8805 if( weights[
w] > 1 )
8813 (*nchgcoefs) += ncoefchg;
8816 consdata->capacity = (-2 + v * 2 +
nvars - v);
8817 assert(consdata->capacity > 0);
8818 assert(weights[0] <= consdata->capacity);
8819 assert(consdata->weightsum > consdata->capacity);
8847 while( weights[v] > newweight )
8849 reductionsum += (weights[v] - newweight);
8854 (*nchgcoefs) += (v - startv);
8857 while( weights[v] == newweight )
8863 restsumweights += weights[
w];
8866 restsumweights = consdata->weightsum;
8868 if( restsumweights < dualcapacity )
8886 for( ;
w >= 0; --
w )
8887 assert(weights[
w] == dualcapacity);
8912 if( weights[
w] > 1 )
8924 for( ;
w >= startv; --
w )
8926 if( weights[
w] > newweight )
8932 assert(weights[
w] == newweight);
8938 for( ;
w >= 0; --
w )
8940 if( weights[
w] > newweight )
8946 assert(weights[
w] == newweight);
8951 if( consdata->capacity > newcap )
8953 consdata->capacity = newcap;
8957 assert(consdata->capacity == newcap);
8969 assert(weights[
w] <= weights[
w - 1]);
8976 while( end >= 0 && weights[end] == weights[end + 1] )
8988 if( 2 * weights[end] > dualcapacity )
8994 restsumweights += weights[
w];
8996 if( restsumweights * 2 <= dualcapacity )
8999 while( v < end && restsumweights + weights[v] >= dualcapacity )
9006 if( (dualcapacity & 1) == 0 )
9008 newweight = dualcapacity / 2;
9011 for( ; v <= end; ++v )
9013 if( weights[v] > newweight )
9015 reductionsum += (weights[v] - newweight);
9030 for(
w = 0;
w < v; ++
w )
9035 newweight = dualcapacity;
9037 for( ; v <= end; ++v )
9039 reductionsum += (2 * weights[v] - newweight);
9048 (*nchgcoefs) +=
nvars;
9051 consdata->capacity *= 2;
9066 for( k = 0; k < 4; ++k )
9072 sumcoef = weights[
nvars - 1] + weights[
nvars - 2];
9076 sumcoef = weights[
nvars - 1] + weights[
nvars - 3];
9083 sumcoef = weights[
nvars - 1] + weights[
nvars - 4];
9087 sumcoefcase =
FALSE;
9088 sumcoef = weights[
nvars - 2] + weights[
nvars - 3];
9107 minweight = weights[end];
9108 while( minweight <= sumcoef )
9110 newweight = dualcapacity - minweight;
9116 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9118 reductionsum += (weights[v] - newweight);
9123 (*nchgcoefs) += (v - startv);
9126 while( weights[v] + minweight == dualcapacity )
9134 while( end >= 0 && weights[end] == weights[end + 1] )
9140 minweight = weights[end];
9147 if( sumcoef < minweight )
9149 minweight = sumcoef;
9150 newweight = dualcapacity - minweight;
9155 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9157 reductionsum += (weights[v] - newweight);
9162 (*nchgcoefs) += (v - startv);
9165 while( weights[v] + minweight == dualcapacity )
9176 if( 2 * weights[end] > dualcapacity )
9182 restsumweights += weights[
w];
9184 if( restsumweights * 2 <= dualcapacity )
9187 while( v < end && restsumweights + weights[v] >= dualcapacity )
9194 if( (dualcapacity & 1) == 0 )
9196 newweight = dualcapacity / 2;
9199 for( ; v <= end; ++v )
9201 if( weights[v] > newweight )
9203 reductionsum += (weights[v] - newweight);
9218 for(
w = 0;
w < v; ++
w )
9223 newweight = dualcapacity;
9225 for( ; v <= end; ++v )
9227 reductionsum += (2 * weights[v] - newweight);
9236 (*nchgcoefs) +=
nvars;
9239 consdata->capacity *= 2;
9248 if( 2 * sumcoef > dualcapacity )
9256 if( reductionsum > 0 )
9260 consdata->capacity -= reductionsum;
9263 assert(consdata->weightsum - dualcapacity == consdata->capacity);
9265 assert(weights[0] <= consdata->capacity);
9272 assert(weights[
w] <= weights[
w - 1]);
9275 if( oldnchgcoefs < *nchgcoefs )
9284 assert(oldnchgcoefs == *nchgcoefs);
9285 assert(oldnchgsides == *nchgsides);
9320 nvars = consdata->nvars;
9325 assert(consdata->capacity >= 0);
9336 vars = consdata->vars;
9337 weights = consdata->weights;
9338 capacity = consdata->capacity;
9342 while( v <
nvars && weights[v] > capacity )
9365 for( --v; v >= 0; --v )
9374 assert(weights == consdata->weights);
9376 assert(consdata->sorted);
9377 assert(weights[0] <= capacity);
9456 assert(consdata->merged);
9460 assert(consdata->capacity >= 0);
9482 weights = consdata->weights;
9483 nvars = consdata->nvars;
9487 for( v =
nvars - 1; v > 0; --v )
9488 assert(weights[v] <= weights[v-1]);
9492 gcd = weights[
nvars - 1];
9493 for( v =
nvars - 2; v >= 0 && gcd > 1; --v )
9501 for( v =
nvars - 1; v >= 0; --v )
9505 (*nchgcoefs) +=
nvars;
9507 consdata->capacity /= gcd;
9516 for( v =
nvars - 1; v > 0; --v )
9517 assert(weights[v] <= weights[v-1]);
9526 vars = consdata->vars;
9527 weights = consdata->weights;
9528 nvars = consdata->nvars;
9531 if( weights[
nvars - 1] == 1 && weights[
nvars - 2] == 1 )
9538 while( weights[v] == consdata->capacity )
9545 if( v ==
nvars - 1 )
9557 for( v =
nvars - 1; v >= offsetv; --v )
9559 weight = weights[v];
9587 if( v ==
nvars - 2 )
9593 if( candpos == v + 1 && candpos2 == v + 2 )
9620 assert(((candpos >= offsetv) || (candpos == -1 && offsetv > 0)) && candpos <
nvars);
9623 rest = consdata->capacity % gcd;
9633 consdata->capacity -= rest;
9637 for( v = 0; v < offsetv; ++v )
9642 *nchgcoefs += offsetv;
9647 restweight = weights[candpos] % gcd;
9649 assert(restweight < gcd);
9652 if( restweight > rest )
9653 newweight = weights[candpos] - restweight + gcd;
9655 newweight = weights[candpos] - restweight;
9659 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);
9664 if( newweight == 0 && offsetv > 0 )
9670 consdata->capacity -= rest;
9674 for( v = 0; v < offsetv; ++v )
9679 *nchgcoefs += offsetv;
9682 if( newweight == 0 )
9698 assert(consdata->weights == weights);
9702 for( v =
nvars - 1; v >= 0; --v )
9706 (*nchgcoefs) +=
nvars;
9708 consdata->capacity /= gcd;
9713 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));
9715 while(
nvars >= 2 );
9753 assert(*nzeroitems <= *zeroitemssize);
9757 nzeros = *nzeroitems;
9760 if( nzeros == *zeroitemssize )
9767 SCIPdebugMsg(
scip,
"memory limit of %d bytes reached in knapsack preprocessing - abort collecting zero items\n",
9769 *memlimitreached =
TRUE;
9772 *zeroitemssize *= 2;
9777 assert(nzeros < *zeroitemssize);
9779 if( *memlimitreached )
9780 *memlimitreached =
FALSE;
9783 (*zeroitems)[nzeros] = knapsackidx;
9784 (*nextidxs)[nzeros] = firstidxs[value][probindex];
9785 if( firstidxs[value][probindex] == 0 )
9787 liftcands[value][nliftcands[value]] = probindex;
9788 ++nliftcands[value];
9790 firstidxs[value][probindex] = nzeros;
9792 zeroweightsums[value][probindex] += knapsackweight;
9797#define MAX_CLIQUELENGTH 50
9859 assert(consdata->weightsum > consdata->capacity);
9860 assert(consdata->nvars > 0);
9861 assert(consdata->merged);
9863 nvars = consdata->nvars;
9891 assert(conshdlrdata->ints1size > 0);
9892 assert(conshdlrdata->ints2size > 0);
9893 assert(conshdlrdata->longints1size > 0);
9894 assert(conshdlrdata->longints2size > 0);
9900 if( conshdlrdata->ints1size < nbinvars )
9902 int oldsize = conshdlrdata->ints1size;
9904 conshdlrdata->ints1size = nbinvars;
9908 if( conshdlrdata->ints2size < nbinvars )
9910 int oldsize = conshdlrdata->ints2size;
9912 conshdlrdata->ints2size = nbinvars;
9916 if( conshdlrdata->longints1size < nbinvars )
9918 int oldsize = conshdlrdata->longints1size;
9920 conshdlrdata->longints1size = nbinvars;
9922 BMSclearMemoryArray(&(conshdlrdata->longints1[oldsize]), conshdlrdata->longints1size - oldsize);
9924 if( conshdlrdata->longints2size < nbinvars )
9926 int oldsize = conshdlrdata->longints2size;
9928 conshdlrdata->longints2size = nbinvars;
9930 BMSclearMemoryArray(&(conshdlrdata->longints2[oldsize]), conshdlrdata->longints2size - oldsize);
9933 firstidxs[0] = conshdlrdata->ints1;
9934 firstidxs[1] = conshdlrdata->ints2;
9935 zeroweightsums[0] = conshdlrdata->longints1;
9936 zeroweightsums[1] = conshdlrdata->longints2;
9940 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
9942 assert(firstidxs[0][tmp] == 0);
9943 assert(firstidxs[1][tmp] == 0);
9944 assert(zeroweightsums[0][tmp] == 0);
9945 assert(zeroweightsums[1][tmp] == 0);
9958 assert(conshdlrdata->bools1size > 0);
9959 assert(conshdlrdata->bools2size > 0);
9965 if( conshdlrdata->bools1size < nbinvars )
9967 int oldsize = conshdlrdata->bools1size;
9969 conshdlrdata->bools1size = nbinvars;
9971 BMSclearMemoryArray(&(conshdlrdata->bools1[oldsize]), conshdlrdata->bools1size - oldsize);
9973 if( conshdlrdata->bools2size < nbinvars )
9975 int oldsize = conshdlrdata->bools2size;
9977 conshdlrdata->bools2size = nbinvars;
9979 BMSclearMemoryArray(&(conshdlrdata->bools2[oldsize]), conshdlrdata->bools2size - oldsize);
9982 zeroiteminserted[0] = conshdlrdata->bools1;
9983 zeroiteminserted[1] = conshdlrdata->bools2;
9987 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
9989 assert(zeroiteminserted[0][tmp] == 0);
9990 assert(zeroiteminserted[1][tmp] == 0);
10004 memlimitreached =
FALSE;
10005 for(
i = 0;
i < consdata->nvars && !memlimitreached; ++
i )
10018 var = consdata->vars[
i];
10019 weight = consdata->weights[
i];
10023 assert(0 <= varprobindex && varprobindex < nbinvars);
10026 zeroweightsums[!value][varprobindex] += weight;
10027 tmpboolindices3[tmp3] = !value;
10028 tmpindices3[tmp3] = varprobindex;
10038 assert(0 <= probindex && probindex < nbinvars);
10040 implvalue = !value;
10043 assert( !zeroiteminserted[implvalue][probindex] );
10045 if( firstidxs[implvalue][probindex] == 0 )
10047 tmpboolindices2[tmp2] = implvalue;
10048 tmpindices2[tmp2] = probindex;
10052 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue,
i, weight,
10053 &memlimitreached) );
10054 zeroiteminserted[implvalue][probindex] =
TRUE;
10055 tmpboolindices[tmp] = implvalue;
10056 tmpindices[tmp] = probindex;
10063 for( j = 0; j < ncliques && !memlimitreached; ++j )
10079 for( k = ncliquevars - 1; k >= 0; --k )
10084 if(
var == cliquevars[k] )
10088 if( probindex == -1 )
10091 assert(0 <= probindex && probindex < nbinvars);
10092 implvalue = cliquevalues[k];
10095 if( !zeroiteminserted[implvalue][probindex] )
10097 if( firstidxs[implvalue][probindex] == 0 )
10099 tmpboolindices2[tmp2] = implvalue;
10100 tmpindices2[tmp2] = probindex;
10105 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue,
i, weight,
10106 &memlimitreached) );
10107 zeroiteminserted[implvalue][probindex] =
TRUE;
10108 tmpboolindices[tmp] = implvalue;
10109 tmpindices[tmp] = probindex;
10112 if( memlimitreached )
10118 for( --tmp; tmp >= 0; --tmp)
10119 zeroiteminserted[tmpboolindices[tmp]][tmpindices[tmp]] =
FALSE;
10124 assert(consdata->sorted);
10127 assert(conshdlrdata->bools3size > 0);
10133 if( conshdlrdata->bools3size < consdata->nvars )
10135 int oldsize = conshdlrdata->bools3size;
10137 conshdlrdata->bools3size = consdata->nvars;;
10139 BMSclearMemoryArray(&(conshdlrdata->bools3[oldsize]), conshdlrdata->bools3size - oldsize);
10142 cliqueused = conshdlrdata->bools3;
10146 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10147 assert(cliqueused[tmp] == 0);
10150 maxcliqueweightsum = 0;
10154 for(
i = 0;
i < consdata->nvars; ++
i )
10156 cliquenum = consdata->cliquepartition[
i];
10157 assert(0 <= cliquenum && cliquenum < consdata->
nvars);
10159 if( !cliqueused[cliquenum] )
10161 maxcliqueweightsum += consdata->weights[
i];
10162 cliqueused[cliquenum] =
TRUE;
10163 tmpindices[tmp] = cliquenum;
10168 for( --tmp; tmp >= 0; --tmp)
10169 cliqueused[tmp] =
FALSE;
10171 assert(conshdlrdata->bools4size > 0);
10177 if( conshdlrdata->bools4size < consdata->nvars )
10179 int oldsize = conshdlrdata->bools4size;
10181 conshdlrdata->bools4size = consdata->nvars;
10186 itemremoved = conshdlrdata->bools4;
10190 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10191 assert(itemremoved[tmp] == 0);
10202 for( val = 0; val < 2 && addweightsum < consdata->capacity; ++val )
10204 for(
i = 0;
i < nliftcands[val] && addweightsum < consdata->capacity; ++
i )
10213 probindex = liftcands[val][
i];
10214 assert(0 <= probindex && probindex < nbinvars);
10217 if( firstidxs[val][probindex] == 0
10218 || maxcliqueweightsum - zeroweightsums[val][probindex] + addweightsum >= consdata->capacity )
10222 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10224 assert(0 < idx && idx < nzeroitems);
10225 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10226 itemremoved[zeroitems[idx]] =
TRUE;
10230 cliqueweightsum = addweightsum;
10231 for( j = 0; j < consdata->nvars; ++j )
10233 cliquenum = consdata->cliquepartition[j];
10234 assert(0 <= cliquenum && cliquenum < consdata->
nvars);
10235 if( !itemremoved[j] )
10237 if( !cliqueused[cliquenum] )
10239 cliqueweightsum += consdata->weights[j];
10240 cliqueused[cliquenum] =
TRUE;
10241 tmpindices[tmp] = cliquenum;
10245 if( cliqueweightsum >= consdata->capacity )
10251 if( cliqueweightsum < consdata->capacity )
10257 assert(naddvars < 2*nbinvars);
10258 var = binvars[probindex];
10263 weight = consdata->capacity - cliqueweightsum;
10264 addvars[naddvars] =
var;
10265 addweights[naddvars] = weight;
10266 addweightsum += weight;
10274 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10276 assert(0 < idx && idx < nzeroitems);
10277 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10278 itemremoved[zeroitems[idx]] =
FALSE;
10281 for( --tmp; tmp >= 0; --tmp)
10282 cliqueused[tmpindices[tmp]] =
FALSE;
10287 for( --tmp3; tmp3 >= 0; --tmp3)
10288 zeroweightsums[tmpboolindices3[tmp3]][tmpindices3[tmp3]] = 0;
10291 for( --tmp2; tmp2 >= 0; --tmp2)
10293 zeroweightsums[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10294 firstidxs[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10298 for(
i = 0;
i < naddvars; ++
i )
10302 *nchgcoefs += naddvars;
10410 assert(consdata->onesweightsum == 0);
10411 assert(consdata->weightsum > consdata->capacity);
10412 assert(consdata->nvars > 0);
10423 assert(consdata->merged);
10428 for(
i = 0;
i < consdata->nvars; ++
i )
10432 weight = consdata->weights[
i];
10433 if( consdata->weightsum - weight < consdata->capacity )
10435 newweight = consdata->weightsum - consdata->capacity;
10437 consdata->capacity -= (weight - newweight);
10440 assert(!consdata->sorted);
10443 consdata->capacity + (weight-newweight), consdata->capacity);
10449 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10453 if( consdata->weightsum <= consdata->capacity )
10457 while( pos < consdata->
nvars && consdata->weights[pos] == consdata->capacity )
10461 weights = consdata->weights;
10462 nvars = consdata->nvars;
10463 capacity = consdata->capacity;
10466 pos <
nvars && weights[pos] + weights[pos + 1] > capacity )
10473 for( k = 0; k < 4; ++k )
10475 newweight = capacity - sumcoef;
10481 sumcoef = weights[
nvars - 1];
10482 backpos =
nvars - 1;
10485 sumcoef = weights[
nvars - 2];
10486 backpos =
nvars - 2;
10491 sumcoefcase =
TRUE;
10492 sumcoef = weights[
nvars - 3];
10493 backpos =
nvars - 3;
10497 sumcoefcase =
FALSE;
10498 sumcoef = weights[
nvars - 1] + weights[
nvars - 2];
10499 backpos =
nvars - 2;
10508 sumcoef = weights[
nvars - 4];
10509 backpos =
nvars - 4;
10513 sumcoef = weights[
nvars - 1] + weights[
nvars - 2];
10514 backpos =
nvars - 2;
10519 sumcoef = weights[
nvars - 3];
10520 backpos =
nvars - 3;
10525 if( backpos <= pos )
10529 maxweight = weights[pos];
10531 while( 2 * maxweight > capacity && maxweight + sumcoef > capacity )
10533 assert(newweight > weights[pos]);
10543 maxweight = weights[pos];
10545 if( backpos <= pos )
10548 (*nchgcoefs) += (pos - startpos);
10551 while( pos <
nvars && weights[pos] + sumcoef == capacity )
10562 if( pos + 1 == backpos && weights[pos] > sumcoef &&
10563 ((k == 0) || (k == 1 && weights[
nvars - 1] + sumcoef + weights[pos] > capacity)) )
10565 newweight = capacity - sumcoef;
10566 assert(newweight > weights[pos]);
10576 if( backpos <= pos )
10585 && consdata->nvars - pos <= MAX_USECLIQUES_SIZE && consdata->
nvars >= 2 && pos > 0
10586 && (
SCIP_Longint)consdata->nvars - pos <= consdata->capacity
10587 && consdata->weights[pos - 1] == consdata->capacity
10588 && ( pos == consdata->nvars || consdata->weights[pos] == 1 ) )
10602 if( pos == consdata->nvars )
10624 len = consdata->nvars - pos;
10635 for(
w = 0;
w < nclq; ++
w )
10645 for(
w = pos - 1;
w >= 0; --
w )
10646 clqvars[
w] = consdata->vars[
w];
10649 for(
c = 0;
c < nclq; ++
c )
10653 for(
w =
c;
w < len; ++
w )
10655 if( clqpart[
w] ==
c )
10657 assert(nclqvars < pos + len - nclq + 1);
10658 clqvars[nclqvars] = consdata->vars[
w + pos];
10693 int* newweightidxs;
10707 assert(consdata->merged);
10716 if( consdata->cliquepartition[consdata->nvars - 1] == consdata->nvars - 1 )
10720 cliqueweightsum = 0;
10723 for(
i = 0;
i < consdata->nvars; ++
i )
10727 cliquenum = consdata->cliquepartition[
i];
10728 assert(0 <= cliquenum && cliquenum <= ncliques);
10730 weight = consdata->weights[
i];
10733 if( cliquenum == ncliques )
10735 maxcliqueweights[ncliques] = weight;
10736 cliqueweightsum += weight;
10740 assert(maxcliqueweights[cliquenum] >= weight);
10744 zeroweights =
FALSE;
10745 for(
i = 0;
i < ncliques; ++
i )
10749 delta = consdata->capacity - (cliqueweightsum - maxcliqueweights[
i]);
10762 SCIPconsGetName(cons),
i, maxcliqueweights[
i], cliqueweightsum, consdata->capacity, delta);
10763 newcapacity = consdata->capacity - delta;
10764 forceclique =
FALSE;
10767 newmincliqueweight = newcapacity + 1;
10768 for( j = 0; j <
i; ++j )
10769 assert(consdata->cliquepartition[j] <
i);
10771 for( j =
i; j < consdata->nvars; ++j )
10773 if( consdata->cliquepartition[j] ==
i )
10775 newweight = consdata->weights[j] - delta;
10776 newweight =
MAX(newweight, 0);
10780 newweightvals[nnewweights] = newweight;
10781 newweightidxs[nnewweights] = j;
10785 assert(newweight <= newmincliqueweight);
10786 newmincliqueweight = newweight;
10792 if( nnewweights > 1 )
10795 j = newweightidxs[nnewweights - 2];
10797 assert(consdata->cliquepartition[j] ==
i);
10798 j = newweightidxs[nnewweights - 1];
10800 assert(consdata->cliquepartition[j] ==
i);
10803 newminweightsuminclique = newweightvals[nnewweights - 2];
10804 newminweightsuminclique += newweightvals[nnewweights - 1];
10811 if( newminweightsuminclique <= newcapacity )
10812 forceclique =
TRUE;
10816 if( conshdlrdata->disaggregation || !forceclique )
10819 consdata->capacity, newcapacity, forceclique);
10820 consdata->capacity = newcapacity;
10823 for( k = 0; k < nnewweights; ++k )
10825 j = newweightidxs[k];
10827 assert(consdata->cliquepartition[j] ==
i);
10831 SCIPvarGetName(consdata->vars[j]), consdata->weights[j], newweightvals[k]);
10834 assert(!consdata->sorted);
10835 zeroweights = zeroweights || (newweightvals[k] == 0);
10849 for( k = 0; k < nnewweights; ++k )
10850 cliquevars[k] = consdata->vars[newweightidxs[k]];
10877 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10885 if( consdata->weightsum <= consdata->capacity )
10897 if( consdata->weightsum <= consdata->capacity )
10903 assert(consdata->merged);
10905 minweight = consdata->weights[consdata->nvars-1];
10906 for(
i = 0;
i < consdata->nvars-1; ++
i )
10910 weight = consdata->weights[
i];
10911 assert(weight >= minweight);
10912 if( minweight + weight > consdata->capacity )
10914 if( weight < consdata->capacity )
10918 assert(consdata->sorted);
10920 assert(
i == 0 || consdata->weights[
i-1] >= consdata->weights[
i]);
10921 consdata->sorted =
TRUE;
10930 if( consdata->nvars >= 2 )
10934 minweight = consdata->weights[consdata->nvars-2];
10935 weight = consdata->weights[consdata->nvars-1];
10936 assert(minweight >= weight);
10937 if( minweight + weight > consdata->capacity && weight < consdata->capacity )
10941 assert(consdata->sorted);
10943 assert(minweight >= consdata->weights[consdata->nvars-1]);
10944 consdata->sorted =
TRUE;
10963 for(
b = 0;
b < ncliquevars; ++
b )
10984 int* gaincliquepartition;
10990 int nposcliquevars;
10994 int lastcliqueused;
11009 nvars = consdata->nvars;
11012 if( consdata->cliquesadded ||
nvars == 0 )
11023 assert(consdata->merged);
11030 nnegcliques = consdata->nnegcliques;
11033 if( nnegcliques ==
nvars )
11045 minactduetonegcliques = 0;
11048 for( v = 0; v <
nvars; ++v )
11050 assert(0 <= consdata->negcliquepartition[v] && consdata->negcliquepartition[v] <= nnegcliques);
11051 assert(consdata->weights[v] > 0);
11053 if( consdata->negcliquepartition[v] == nnegcliques )
11056 maxweights[consdata->negcliquepartition[v]] = consdata->weights[v];
11059 minactduetonegcliques += consdata->weights[v];
11062 nposcliquevars = 0;
11065 if( minactduetonegcliques > 0 )
11068 freecapacity = consdata->capacity - minactduetonegcliques;
11072 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
11075 for( v = 0; v <
nvars; ++v )
11077 if( !cliqueused[consdata->negcliquepartition[v]] )
11079 cliqueused[consdata->negcliquepartition[v]] =
TRUE;
11084 if( consdata->negcliquepartition[v] == consdata->negcliquepartition[
w]
11085 && consdata->weights[v] > consdata->weights[
w] )
11087 poscliquevars[nposcliquevars] = consdata->vars[
w];
11088 gainweights[nposcliquevars] = maxweights[consdata->negcliquepartition[v]] - consdata->weights[
w];
11089 gaincliquepartition[nposcliquevars] = consdata->negcliquepartition[v];
11097 if( nposcliquevars > 0 )
11102 for( v = 0; v < nposcliquevars; ++v )
11106 lastweight = gainweights[v];
11107 beforelastweight = -1;
11108 lastcliqueused = gaincliquepartition[v];
11111 cliqueused[gaincliquepartition[v]] =
TRUE;
11117 beforelastweight = lastweight;
11118 lastweight = gainweights[
w];
11119 lastcliqueused = gaincliquepartition[
w];
11120 cliqueused[gaincliquepartition[
w]] =
TRUE;
11125 if( ncliquevars > 1 )
11127 SCIPdebug( printClique(cliquevars, ncliquevars) );
11128 assert(beforelastweight > 0);
11134 *nbdchgs += thisnbdchgs;
11137 cliqueused[lastcliqueused] =
FALSE;
11143 SCIPdebug( printClique(cliquevars, ncliquevars) );
11147 *nbdchgs += thisnbdchgs;
11194 if( ! sorteditems )
11198 lastweight = weights[0];
11203 lastweight = weights[
i];
11207 if( ncliquevars > 1 )
11211 int compareweightidx;
11216 SCIPdebug( printClique(items, ncliquevars) );
11222 *nbdchgs += thisnbdchgs;
11223 nnzadded = ncliquevars;
11226 if( ncliquevars == nitems )
11234 compareweightidx = ncliquevars - 2;
11235 assert(
i == nitems || weights[
i] + weights[ncliquevars - 1] <= capacity);
11238 minclqsize = (int)(cliqueextractfactor * ncliquevars);
11239 minclqsize =
MAX(minclqsize, 2);
11243 while( compareweightidx >= 0 &&
i < nitems && ! (*
cutoff)
11244 && ncliquevars >= minclqsize
11245 && nnzadded <= 2 * nitems
11248 compareweight = weights[compareweightidx];
11249 assert(compareweight > 0);
11252 if( compareweight + weights[
i] > capacity )
11254 assert(compareweightidx == ncliquevars -2);
11255 cliquevars[ncliquevars - 1] = items[
i];
11256 SCIPdebug( printClique(cliquevars, ncliquevars) );
11259 nnzadded += ncliquevars;
11263 *nbdchgs += thisnbdchgs;
11271 compareweightidx--;
11301 int nposcliquevars;
11315 nvars = consdata->nvars;
11318 if( consdata->cliquesadded ||
nvars == 0 )
11329 assert(consdata->merged);
11336 nnegcliques = consdata->nnegcliques;
11346 minactduetonegcliques = 0;
11349 if( nnegcliques <
nvars )
11357 cliquenum = consdata->negcliquepartition[
i];
11358 assert(0 <= cliquenum && cliquenum <= nnegcliques);
11360 weight = consdata->weights[
i];
11363 if( cliquenum == nnegcliques )
11367 minactduetonegcliques += weight;
11368 if( secondmaxweights[cliquenum] == 0 )
11369 secondmaxweights[cliquenum] = weight;
11375 if( minactduetonegcliques > 0 )
11378 freecapacity = consdata->capacity - minactduetonegcliques;
11382 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
11390 nposcliquevars = 0;
11395 cliquenum = consdata->negcliquepartition[
i];
11396 if( consdata->weights[
i] > secondmaxweights[cliquenum] )
11398 poscliquevars[nposcliquevars] = consdata->vars[
i];
11399 gainweights[nposcliquevars] = consdata->weights[
i] - secondmaxweights[cliquenum];
11405 if( nposcliquevars > 1 )
11422 consdata->cliquesadded =
TRUE;
11451 assert(consdata1->sorted);
11452 assert(consdata2->sorted);
11459 if( consdata1->nvars != consdata2->nvars )
11462 for(
i = consdata1->nvars - 1;
i >= 0; --
i )
11465 if( consdata1->vars[
i] != consdata2->vars[
i] )
11474 if( consdata1->weights[
i] != consdata2->weights[
i] )
11489 uint64_t firstweight;
11496 assert(consdata->nvars > 0);
11509 assert(minidx >= 0 && mididx >= 0 && maxidx >= 0);
11512 firstweight = (uint64_t)consdata->weights[0];
11513 return SCIPhashSix(consdata->nvars, minidx, mididx, maxidx, firstweight>>32, firstweight);
11539 hashtablesize = nconss;
11542 hashGetKeyKnapsackcons, hashKeyEqKnapsackcons, hashKeyValKnapsackcons, (
void*)
scip) );
11545 for(
c = nconss - 1;
c >= 0; --
c )
11558 if( consdata0->nvars == 0 )
11560 if( consdata0->capacity < 0 )
11576 if( cons1 !=
NULL )
11591 assert(consdata0->nvars > 0 && consdata0->nvars == consdata1->nvars);
11593 assert(consdata0->sorted && consdata1->sorted);
11594 assert(consdata0->vars[0] == consdata1->vars[0]);
11595 assert(consdata0->weights[0] == consdata1->weights[0]);
11597 SCIPdebugMsg(
scip,
"knapsack constraints <%s> and <%s> with equal coefficients\n",
11601 if( consdata0->capacity < consdata1->capacity )
11658 assert(firstchange <= chkind);
11662 cons0 = conss[chkind];
11669 assert(consdata0->nvars >= 1);
11670 assert(consdata0->merged);
11676 if( consdata0->capacity == 0 )
11703 assert(consdata1->nvars >= 1);
11704 assert(consdata1->merged);
11710 if( consdata1->capacity == 0 )
11715 if( consdata0->nvars > consdata1->nvars )
11717 iscons0incons1contained =
FALSE;
11718 iscons1incons0contained =
TRUE;
11719 v = consdata1->nvars - 1;
11721 else if( consdata0->nvars < consdata1->nvars )
11723 iscons0incons1contained =
TRUE;
11724 iscons1incons0contained =
FALSE;
11725 v = consdata0->nvars - 1;
11729 iscons0incons1contained =
TRUE;
11730 iscons1incons0contained =
TRUE;
11731 v = consdata0->nvars - 1;
11742 v0 = consdata0->nvars - 1;
11743 v1 = consdata1->nvars - 1;
11747 assert(iscons0incons1contained || iscons1incons0contained);
11752 iscons1incons0contained =
FALSE;
11753 if( !iscons0incons1contained )
11759 iscons0incons1contained =
FALSE;
11760 if( !iscons1incons0contained )
11764 assert(v == v0 || v == v1);
11769 if( consdata0->vars[v0] == consdata1->vars[v1] )
11774 iscons1incons0contained =
FALSE;
11775 if( !iscons0incons1contained )
11781 iscons0incons1contained =
FALSE;
11782 if( !iscons1incons0contained )
11792 if( iscons0incons1contained && iscons1incons0contained )
11794 iscons0incons1contained =
FALSE;
11795 iscons1incons0contained =
FALSE;
11798 assert(iscons0incons1contained ? (v1 >= v0) : iscons1incons0contained);
11799 assert(iscons1incons0contained ? (v1 <= v0) : iscons0incons1contained);
11801 if( iscons0incons1contained )
11810 assert(!iscons1incons0contained || !iscons0incons1contained || v0 == -1 || v1 == -1);
11812 if( iscons1incons0contained )
11823 else if( iscons0incons1contained )
11861 SCIPdebugMsg(
scip,
"knapsack enforcement of %d/%d constraints for %s solution\n", nusefulconss, nconss,
11862 sol ==
NULL ?
"LP" :
"relaxation");
11867 maxncuts = (
SCIPgetDepth(
scip) == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
11870 for(
i = 0;
i < nusefulconss && ncuts < maxncuts && !
cutoff;
i++ )
11882 for(
i = nusefulconss;
i < nconss && ncuts == 0 && !
cutoff;
i++ )
11896 else if ( ncuts > 0 )
11972 for( v = 0; v <
nvars; ++v )
11978 transvars[v] =
vars[v];
11979 weights[v] = weight;
11984 weights[v] = -weight;
11985 capacity -= weight;
11992 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
12016 upgrade = (nposbin + nnegbin + nposimplbin + nnegimplbin ==
nvars)
12017 && (ncoeffspone + ncoeffsnone + ncoeffspint + ncoeffsnint ==
nvars)
12066 nlocvars = consdata->nvars;
12071 for(
i = 0;
i < consdata->nvars; ++
i )
12073 vars[
i] = consdata->vars[
i];
12149 conshdlrdata->reals1size =
nvars;
12167 conshdlrdata->reals1size = 0;
12199 conshdlrdata->ints1size =
nvars;
12200 conshdlrdata->ints2size =
nvars;
12201 conshdlrdata->longints1size =
nvars;
12202 conshdlrdata->longints2size =
nvars;
12203 conshdlrdata->bools1size =
nvars;
12204 conshdlrdata->bools2size =
nvars;
12205 conshdlrdata->bools3size =
nvars;
12206 conshdlrdata->bools4size =
nvars;
12208#ifdef WITH_CARDINALITY_UPGRADE
12209 conshdlrdata->upgradedcard =
FALSE;
12226 for(
c = 0;
c < nconss; ++
c )
12247 conshdlrdata->ints1size = 0;
12248 conshdlrdata->ints2size = 0;
12249 conshdlrdata->longints1size = 0;
12250 conshdlrdata->longints2size = 0;
12251 conshdlrdata->bools1size = 0;
12252 conshdlrdata->bools2size = 0;
12253 conshdlrdata->bools3size = 0;
12254 conshdlrdata->bools4size = 0;
12267 for(
c = 0;
c < nconss; ++
c )
12286 for(
c = 0;
c < nconss; ++
c )
12291 if( consdata->row !=
NULL )
12296 if( consdata->nlrow !=
NULL )
12351 sourcedata->nvars, sourcedata->vars, sourcedata->weights, sourcedata->capacity) );
12373 *infeasible =
FALSE;
12375 for(
i = 0;
i < nconss && !(*infeasible);
i++ )
12413 SCIPdebugMsg(
scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12414 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12417 if( (
depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12418 || (
depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12423 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12424 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12425 && ((sepacardfreq == 0 &&
depth == 0) || (sepacardfreq >= 1 && (
depth % sepacardfreq == 0)));
12431 maxbound = glblowerbound + conshdlrdata->maxcardbounddist * (cutoffbound - glblowerbound);
12432 sepacardinality = sepacardinality &&
SCIPisLE(
scip, loclowerbound, maxbound);
12436 maxsepacuts = (
depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12451 else if ( ncuts > 0 )
12482 SCIPdebugMsg(
scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12483 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12486 if( (
depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12487 || (
depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12492 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12493 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12494 && ((sepacardfreq == 0 &&
depth == 0) || (sepacardfreq >= 1 && (
depth % sepacardfreq == 0)));
12497 maxsepacuts = (
depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12512 else if( ncuts > 0 )
12543 for(
i = 0;
i < nconss;
i++ )
12597 for(
i = 0;
i < nmarkedconss && !
cutoff;
i++ )
12618 else if( nfixedvars > 0 )
12648 oldnfixedvars = *nfixedvars;
12649 oldnchgbds = *nchgbds;
12650 oldndelconss = *ndelconss;
12651 oldnaddconss = *naddconss;
12652 oldnchgcoefs = *nchgcoefs;
12653 oldnchgsides = *nchgsides;
12654 firstchange = INT_MAX;
12656 newchanges = (nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 || nnewupgdconss > 0);
12663 int thisnfixedvars;
12672 if( newchanges || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
12681 consdata->presolvedtiming = 0;
12682 else if( consdata->presolvedtiming >= presoltiming )
12687 consdata->presolvedtiming = presoltiming;
12689 thisnfixedvars = *nfixedvars;
12690 thisnchgbds = *nchgbds;
12720 if( *nfixedvars > thisnfixedvars || *nchgbds > thisnchgbds )
12726 thisnfixedvars = *nfixedvars;
12732 if( consdata->weightsum <= consdata->capacity )
12754 if( *nfixedvars > thisnfixedvars )
12795 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) || (*naddconss != oldnaddconss) )
12804 npaircomparisons = 0;
12805 oldndelconss = *ndelconss;
12806 oldnchgsides = *nchgsides;
12807 oldnchgcoefs = *nchgcoefs;
12821 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) )
12823 if( ((
SCIP_Real) (*ndelconss - oldndelconss) + ((
SCIP_Real) (*nchgsides - oldnchgsides))/2.0 +
12826 oldndelconss = *ndelconss;
12827 oldnchgsides = *nchgsides;
12828 oldnchgcoefs = *nchgcoefs;
12829 npaircomparisons = 0;
12833#ifdef WITH_CARDINALITY_UPGRADE
12851 noldupgdconss = *nupgdconss;
12864 for (makeupgrade = 0; makeupgrade < 2; ++makeupgrade)
12883 nvars = consdata->nvars;
12884 vars = consdata->vars;
12885 weights = consdata->weights;
12892 if ( consdata->capacity >=
nvars )
12896 assert( consdata->sorted );
12897 if ( weights[0] != 1 || weights[
nvars-1] != 1 )
12901 for (v = 0; v <
nvars; ++v)
12910 var = consdata->vars[v];
12927 for (j = 0; j < nimpls; ++j)
12941 cardvars[v] = implvars[j];
12958 if ( makeupgrade == 0 )
12960 for (v = 0; v <
nvars; ++v)
12984 for (v = 0; v <
nvars; ++v)
12994 conshdlrdata->upgradedcard =
TRUE;
13026 for (v = 0; v <
nvars; ++v)
13042 if ( *nupgdconss > noldupgdconss )
13049 else if( success || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
13073 for(
i = 0;
i < consdata->nvars; ++
i )
13090 if( inferinfo < 0 )
13097 if( inferinfo < consdata->
nvars && consdata->vars[inferinfo] == infervar )
13098 capsum = consdata->weights[inferinfo];
13101 for(
i = 0;
i < consdata->nvars && consdata->vars[
i] != infervar; ++
i )
13104 capsum = consdata->weights[
i];
13111 if( capsum <= consdata->capacity )
13113 for(
i = 0;
i < consdata->nvars;
i++ )
13118 capsum += consdata->weights[
i];
13119 if( capsum > consdata->capacity )
13151 for(
i = 0;
i < consdata->nvars;
i++)
13224 for(
i = 0;
i < consdata->nvars; ++
i )
13243 const char* consname;
13253 for( v = 0; v <
nvars; ++v )
13264 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode, global,
valid) );
13299 while( *str !=
'\0' )
13312 endptr = strchr(endptr,
'<');
13314 if( endptr ==
NULL )
13328 if( varssize <=
nvars )
13336 weights[
nvars] = weight;
13345 if( strncmp(str,
"<=", 2) != 0 )
13370 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
13389 if( varssize < consdata->
nvars )
13390 (*success) =
FALSE;
13411 (*nvars) = consdata->nvars;
13454 consdata->onesweightsum += eventdata->weight;
13455 consdata->presolvedtiming = 0;
13459 consdata->onesweightsum -= eventdata->weight;
13462 consdata->presolvedtiming = 0;
13466 if( !consdata->existmultaggr )
13475 consdata->existmultaggr =
TRUE;
13476 consdata->merged =
FALSE;
13480 consdata->merged =
FALSE;
13484 consdata->presolvedtiming = 0;
13487 consdata->varsdeleted =
TRUE;
13515 eventhdlrdata =
NULL;
13516 conshdlrdata->eventhdlr =
NULL;
13518 eventExecKnapsack, eventhdlrdata) );
13519 conshdlrdata->probtoidxmap =
NULL;
13520 conshdlrdata->probtoidxmapsize = 0;
13523 if( conshdlrdata->eventhdlr ==
NULL )
13532 consEnfolpKnapsack, consEnfopsKnapsack, consCheckKnapsack, consLockKnapsack,
13575 "multiplier on separation frequency, how often knapsack cuts are separated (-1: never, 0: only at root)",
13579 "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for separating knapsack cuts",
13583 "lower clique size limit for greedy clique extraction algorithm (relative to largest clique)",
13587 "maximal number of separation rounds per node (-1: unlimited)",
13591 "maximal number of separation rounds per node in the root node (-1: unlimited)",
13595 "maximal number of cuts separated per separation round",
13599 "maximal number of cuts separated per separation round in the root node",
13603 "should disaggregation of knapsack constraints be allowed in preprocessing?",
13607 "should presolving try to simplify knapsacks",
13611 "should negated clique information be used in solving process",
13615 "should pairwise constraint comparison be performed in presolving?",
13619 "should hash table be used for detecting redundant constraints in advance",
13623 "should dual presolving steps be performed?",
13627 "should GUB information be used for separation?",
13631 "should presolving try to detect constraints parallel to the objective function defining an upper bound and prevent these constraints from entering the LP?",
13635 "should presolving try to detect constraints parallel to the objective function defining a lower bound and prevent these constraints from entering the LP?",
13639 "should clique partition information be updated when old partition seems outdated?",
13643 "factor on the growth of global cliques to decide when to update a previous "
13644 "(negated) clique partition (used only if updatecliquepartitions is set to TRUE)",
13646#ifdef WITH_CARDINALITY_UPGRADE
13649 "if TRUE then try to update knapsack constraints to cardinality constraints",
13650 &conshdlrdata->upgdcardinality,
TRUE, DEFAULT_UPGDCARDINALITY,
NULL,
NULL) );
13700 if( conshdlr ==
NULL )
13726 SCIP_CALL(
SCIPcreateCons(
scip, cons, name, conshdlr, consdata, initial,
separate, enforce, check,
propagate,
13727 local, modifiable, dynamic, removable, stickingatnode) );
13807 return consdata->capacity;
13832 SCIPerrorMessage(
"method can only be called during problem creation stage\n");
13839 consdata->capacity = capacity;
13864 return consdata->nvars;
13887 return consdata->vars;
13910 return consdata->weights;
13933 if( consdata->row !=
NULL )
13959 if( consdata->row !=
NULL )
13987 return consdata->row;
14017 for(
i = 0;
i < consdata->nvars; ++
i )
14040 if( conshdlr ==
NULL )
14044 *infeasible =
FALSE;
14050 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