39 #ifdef WITH_CARDINALITY_UPGRADE 44 #define CONSHDLR_NAME "knapsack" 45 #define CONSHDLR_DESC "knapsack constraint of the form a^T x <= b, x binary and a >= 0" 46 #define CONSHDLR_SEPAPRIORITY +600000 47 #define CONSHDLR_ENFOPRIORITY -600000 48 #define CONSHDLR_CHECKPRIORITY -600000 49 #define CONSHDLR_SEPAFREQ 0 50 #define CONSHDLR_PROPFREQ 1 51 #define CONSHDLR_EAGERFREQ 100 53 #define CONSHDLR_MAXPREROUNDS -1 54 #define CONSHDLR_DELAYSEPA FALSE 55 #define CONSHDLR_DELAYPROP FALSE 56 #define CONSHDLR_NEEDSCONS TRUE 58 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS 59 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP 61 #define EVENTHDLR_NAME "knapsack" 62 #define EVENTHDLR_DESC "bound change event handler for knapsack constraints" 63 #define EVENTTYPE_KNAPSACK SCIP_EVENTTYPE_LBCHANGED \ 64 | SCIP_EVENTTYPE_UBTIGHTENED \ 65 | SCIP_EVENTTYPE_VARFIXED \ 66 | SCIP_EVENTTYPE_VARDELETED \ 67 | SCIP_EVENTTYPE_IMPLADDED 69 #define LINCONSUPGD_PRIORITY +100000 71 #define MAX_USECLIQUES_SIZE 1000 72 #define MAX_ZEROITEMS_SIZE 10000 74 #define KNAPSACKRELAX_MAXDELTA 0.1 75 #define KNAPSACKRELAX_MAXDNOM 1000LL 76 #define KNAPSACKRELAX_MAXSCALE 1000.0 78 #define DEFAULT_SEPACARDFREQ 1 79 #define DEFAULT_MAXROUNDS 5 80 #define DEFAULT_MAXROUNDSROOT -1 81 #define DEFAULT_MAXSEPACUTS 50 82 #define DEFAULT_MAXSEPACUTSROOT 200 83 #define DEFAULT_MAXCARDBOUNDDIST 0.0 85 #define DEFAULT_DISAGGREGATION TRUE 86 #define DEFAULT_SIMPLIFYINEQUALITIES TRUE 87 #define DEFAULT_NEGATEDCLIQUE TRUE 89 #define MAXABSVBCOEF 1e+5 90 #define USESUPADDLIFT FALSE 92 #define DEFAULT_PRESOLUSEHASHING TRUE 93 #define HASHSIZE_KNAPSACKCONS 500 95 #define DEFAULT_PRESOLPAIRWISE TRUE 96 #define NMINCOMPARISONS 200000 97 #define MINGAINPERNMINCOMPARISONS 1e-06 99 #define DEFAULT_DUALPRESOLVING TRUE 100 #define DEFAULT_DETECTCUTOFFBOUND TRUE 103 #define DEFAULT_DETECTLOWERBOUND TRUE 106 #define DEFAULT_CLIQUEEXTRACTFACTOR 0.5 107 #define MAXCOVERSIZEITERLEWI 1000 109 #define DEFAULT_USEGUBS FALSE 110 #define GUBCONSGROWVALUE 6 111 #define GUBSPLITGNC1GUBS FALSE 112 #define DEFAULT_CLQPARTUPDATEFAC 1.5 114 #define DEFAULT_UPDATECLIQUEPARTITIONS FALSE 115 #define MAXNCLIQUEVARSCOMP 1000000 116 #ifdef WITH_CARDINALITY_UPGRADE 117 #define DEFAULT_UPGDCARDINALITY FALSE 127 struct SCIP_ConshdlrData
181 #ifdef WITH_CARDINALITY_UPGRADE 194 int* cliquepartition;
195 int* negcliquepartition;
201 int ncliqueslastnegpart;
202 int ncliqueslastpart;
206 unsigned int presolvedtiming:5;
207 unsigned int sorted:1;
208 unsigned int cliquepartitioned:1;
209 unsigned int negcliquepartitioned:1;
210 unsigned int merged:1;
211 unsigned int cliquesadded:1;
212 unsigned int varsdeleted:1;
213 unsigned int existmultaggr:1;
217 struct SCIP_EventData
231 typedef struct sortkeypair SORTKEYPAIR;
287 SORTKEYPAIR* sortkeypair1 = (SORTKEYPAIR*)elem1;
288 SORTKEYPAIR* sortkeypair2 = (SORTKEYPAIR*)elem2;
290 if( sortkeypair1->key1 < sortkeypair2->key1 )
292 else if( sortkeypair1->key1 > sortkeypair2->key1 )
294 else if( sortkeypair1->key2 < sortkeypair2->key2 )
296 else if( sortkeypair1->key2 > sortkeypair2->key2 )
311 assert(eventdata != NULL);
314 (*eventdata)->cons = cons;
315 (*eventdata)->weight = weight;
327 assert(eventdata != NULL);
340 assert(consdata != NULL);
341 assert(consdata->nvars == 0 || consdata->vars != NULL);
342 assert(consdata->nvars == 0 || consdata->weights != NULL);
343 assert(consdata->nvars == 0 || consdata->eventdata != NULL);
344 assert(consdata->nvars == 0 || (consdata->cliquepartition != NULL && consdata->negcliquepartition != NULL));
346 if( !consdata->sorted )
356 (
void**)consdata->vars,
357 (
void**)consdata->eventdata,
358 consdata->cliquepartition,
359 consdata->negcliquepartition,
362 v = consdata->nvars - 1;
368 while( w >= 0 && consdata->weights[v] == consdata->weights[w] )
375 (
void**)(&(consdata->vars[w+1])),
376 (
void**)(&(consdata->eventdata[w+1])),
377 &(consdata->cliquepartition[w+1]),
378 &(consdata->negcliquepartition[w+1]),
386 if( consdata->cliquepartitioned )
390 for( pos = 0; pos < consdata->nvars; ++pos )
394 if( consdata->cliquepartition[pos] > lastcliquenum )
396 consdata->cliquepartitioned =
FALSE;
399 else if( consdata->cliquepartition[pos] == lastcliquenum )
404 if( consdata->negcliquepartitioned )
408 for( pos = 0; pos < consdata->nvars; ++pos )
412 if( consdata->negcliquepartition[pos] > lastcliquenum )
414 consdata->negcliquepartitioned =
FALSE;
417 else if( consdata->negcliquepartition[pos] == lastcliquenum )
422 consdata->sorted =
TRUE;
428 for( i = 0; i < consdata->nvars-1; ++i )
429 assert(consdata->weights[i] >= consdata->weights[i+1]);
446 assert(consdata != NULL);
447 assert(consdata->nvars == 0 || (consdata->cliquepartition != NULL && consdata->negcliquepartition != NULL));
450 ispartitionoutdated = (conshdlrdata->updatecliquepartitions && consdata->ncliques > 1
451 &&
SCIPgetNCliques(scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastpart));
453 if( normalclique && ( !consdata->cliquepartitioned || ispartitionoutdated ) )
456 consdata->cliquepartitioned =
TRUE;
461 isnegpartitionoutdated = (conshdlrdata->updatecliquepartitions && consdata->nnegcliques > 1
462 &&
SCIPgetNCliques(scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastnegpart));
464 if( negatedclique && (!consdata->negcliquepartitioned || isnegpartitionoutdated) )
467 consdata->negcliquepartitioned =
TRUE;
470 assert(!consdata->cliquepartitioned || consdata->ncliques <= consdata->nvars);
471 assert(!consdata->negcliquepartitioned || consdata->nnegcliques <= consdata->nvars);
515 assert(cons != NULL);
516 assert(consdata != NULL);
517 assert(consdata->nvars == 0 || consdata->vars != NULL);
518 assert(consdata->nvars == 0 || consdata->weights != NULL);
519 assert(consdata->nvars == 0 || consdata->eventdata != NULL);
521 for( i = 0; i < consdata->nvars; i++)
525 eventhdlr, consdata->eventdata[i], &consdata->eventdata[i]->filterpos) );
541 assert(consdata != NULL);
542 assert(consdata->nvars == 0 || consdata->vars != NULL);
543 assert(consdata->nvars == 0 || consdata->weights != NULL);
544 assert(consdata->nvars == 0 || consdata->eventdata != NULL);
546 for( i = 0; i < consdata->nvars; i++)
549 eventhdlr, consdata->eventdata[i], consdata->eventdata[i]->filterpos) );
565 assert(consdata != NULL);
566 assert(consdata->nvars <= consdata->varssize);
568 if( num > consdata->varssize )
583 assert(consdata->eventdata == NULL);
584 assert(consdata->cliquepartition == NULL);
585 assert(consdata->negcliquepartition == NULL);
587 consdata->varssize = newsize;
589 assert(num <= consdata->varssize);
602 assert(consdata != NULL);
605 consdata->weightsum += weightdelta;
608 consdata->onesweightsum += weightdelta;
610 assert(consdata->weightsum >= 0);
611 assert(consdata->onesweightsum >= 0);
628 assert(consdata != NULL);
633 (*consdata)->vars = NULL;
634 (*consdata)->weights = NULL;
635 (*consdata)->nvars = 0;
646 for( v = 0; v <
nvars; ++v )
648 assert(vars[v] != NULL);
652 assert( weights[v] >= 0 );
661 constant += weights[v];
665 varsbuffer[k] = vars[v];
666 weightsbuffer[k] = weights[v];
673 (*consdata)->nvars = k;
688 assert(capacity >= 0);
689 assert(constant >= 0);
691 (*consdata)->varssize = (*consdata)->nvars;
692 (*consdata)->capacity = capacity - constant;
693 (*consdata)->eventdata = NULL;
694 (*consdata)->cliquepartition = NULL;
695 (*consdata)->negcliquepartition = NULL;
696 (*consdata)->row = NULL;
697 (*consdata)->weightsum = 0;
698 (*consdata)->onesweightsum = 0;
699 (*consdata)->ncliques = 0;
700 (*consdata)->nnegcliques = 0;
701 (*consdata)->presolvedtiming = 0;
702 (*consdata)->sorted =
FALSE;
703 (*consdata)->cliquepartitioned =
FALSE;
704 (*consdata)->negcliquepartitioned =
FALSE;
705 (*consdata)->ncliqueslastpart = -1;
706 (*consdata)->ncliqueslastnegpart = -1;
707 (*consdata)->merged =
FALSE;
708 (*consdata)->cliquesadded =
FALSE;
709 (*consdata)->varsdeleted =
FALSE;
710 (*consdata)->existmultaggr =
FALSE;
717 for( v = 0; v < (*consdata)->nvars; v++ )
731 for( v = 0; v < (*consdata)->nvars; ++v )
750 assert(consdata != NULL);
751 assert(*consdata != NULL);
753 if( (*consdata)->row != NULL )
757 if( (*consdata)->eventdata != NULL )
762 if( (*consdata)->negcliquepartition != NULL )
766 if( (*consdata)->cliquepartition != NULL )
770 if( (*consdata)->vars != NULL )
775 for( v = 0; v < (*consdata)->nvars; v++ )
777 assert((*consdata)->vars[v] != NULL);
781 assert( (*consdata)->weights != NULL );
782 assert( (*consdata)->varssize > 0 );
803 assert(consdata != NULL);
804 assert(0 <= item && item < consdata->
nvars);
806 oldweight = consdata->weights[item];
807 weightdiff = newweight - oldweight;
808 consdata->weights[item] = newweight;
814 if( consdata->eventdata != NULL )
816 assert(consdata->eventdata[item] != NULL);
817 assert(consdata->eventdata[item]->weight == oldweight);
818 consdata->eventdata[item]->weight = newweight;
821 consdata->presolvedtiming = 0;
822 consdata->sorted =
FALSE;
825 if( oldweight < newweight )
827 consdata->cliquesadded =
FALSE;
842 assert(consdata != NULL);
843 assert(consdata->row == NULL);
850 for( i = 0; i < consdata->nvars; ++i )
869 assert( cutoff != NULL );
873 assert(consdata != NULL);
875 if( consdata->row == NULL )
879 assert(consdata->row != NULL);
884 SCIPdebugMsg(scip,
"adding relaxation of knapsack constraint <%s> (capacity %" SCIP_LONGINT_FORMAT
"): ",
906 assert(violated != NULL);
909 assert(consdata != NULL);
911 SCIPdebugMsg(scip,
"checking knapsack constraint <%s> for feasibility of solution %p (lprows=%u)\n",
916 if( checklprows || consdata->row == NULL || !
SCIProwIsInLP(consdata->row) )
941 for( v = consdata->nvars - 1; v >= 0; --v )
944 sum += consdata->weights[v] *
SCIPgetSolVal(scip, sol, consdata->vars[v]);
952 for( v = consdata->nvars - 1; v >= 0; --v )
957 integralsum += consdata->weights[v];
962 absviol = ishuge ? sum : (
SCIP_Real)integralsum;
963 absviol -= consdata->capacity;
983 SCIPinfoMessage(scip, NULL,
"violation: the capacity is violated by %.15g\n", absviol);
993 #define IDX(j,d) ((j)*(intcap)+(d)) 1025 int* allcurrminweight;
1037 const size_t maxsize_t = (size_t)(-1);
1039 assert(weights != NULL);
1040 assert(profits != NULL);
1041 assert(capacity >= 0);
1042 assert(items != NULL);
1043 assert(nitems >= 0);
1044 assert(success != NULL);
1049 for( j = nitems - 1; j >= 0; --j )
1050 assert(weights[j] >= 0);
1056 if( solval != NULL )
1060 if( solitems != NULL)
1062 assert(items != NULL);
1063 assert(nsolitems != NULL);
1064 assert(nonsolitems != NULL);
1065 assert(nnonsolitems != NULL);
1081 for( j = 0; j < nitems; ++j )
1085 if( weights[j] > capacity )
1087 if( solitems != NULL)
1089 nonsolitems[*nnonsolitems] = items[j];
1094 else if( profits[j] <= 0.0 )
1096 if( solitems != NULL)
1098 nonsolitems[*nnonsolitems] = items[j];
1103 else if( weights[j] == 0 )
1105 if( solitems != NULL)
1107 solitems[*nsolitems] = items[j];
1110 if( solval != NULL )
1111 *solval += profits[j];
1116 myweights[nmyitems] = weights[j];
1117 myprofits[nmyitems] = profits[j];
1118 myitems[nmyitems] = items[j];
1121 if( myweights[nmyitems] < minweight )
1122 minweight = myweights[nmyitems];
1125 if( myweights[nmyitems] > maxweight )
1126 maxweight = myweights[nmyitems];
1128 weightsum += myweights[nmyitems];
1136 SCIPdebugMsg(scip,
"After preprocessing no items are left.\n");
1141 else if( weightsum > 0 && weightsum <= capacity )
1143 SCIPdebugMsg(scip,
"After preprocessing all items fit into knapsack.\n");
1145 for( j = nmyitems - 1; j >= 0; --j )
1147 if( solitems != NULL )
1149 solitems[*nsolitems] = myitems[j];
1152 if( solval != NULL )
1153 *solval += myprofits[j];
1159 assert(minweight > 0);
1160 assert(maxweight > 0);
1165 gcd = myweights[nmyitems - 1];
1166 for( j = nmyitems - 2; j >= 0 && gcd >= 2; --j )
1169 SCIPdebugMsg(scip,
"Gcd is %" SCIP_LONGINT_FORMAT
".\n", gcd);
1175 for( j = nmyitems - 1; j >= 0; --j )
1177 myweights[j] /= gcd;
1178 eqweights = eqweights && (myweights[j] == 1);
1188 assert(maxweight == 1);
1192 assert(minweight <= capacity);
1195 if( minweight > capacity / 2 )
1199 SCIPdebugMsg(scip,
"Only one item fits into knapsack, so take the best.\n");
1204 for( j = nmyitems - 2; j >= 0; --j )
1205 if( myprofits[j] > myprofits[p] )
1209 if( solitems != NULL)
1211 solitems[*nsolitems] = myitems[p];
1213 for( j = nmyitems - 1; j >= 0; --j )
1216 nonsolitems[*nnonsolitems] = myitems[j];
1221 if( solval != NULL )
1222 *solval += myprofits[p];
1232 SCIPdebugMsg(scip,
"All weights are equal, so take the best.\n");
1238 if( solitems != NULL || solval != NULL )
1246 for( i = capacity - 1; i >= 0; --i )
1248 if( solitems != NULL)
1250 assert(nonsolitems != NULL);
1251 solitems[*nsolitems] = myitems[i];
1254 addval += myprofits[i];
1257 if( solitems != NULL)
1259 assert(nonsolitems != NULL);
1262 for( i = nmyitems - 1; i >= capacity; --i )
1264 nonsolitems[*nnonsolitems] = myitems[i];
1270 if( solval != NULL )
1272 assert(addval > 0.0);
1280 capacity -= (minweight - 1);
1283 if( capacity >= INT_MAX )
1285 SCIPdebugMsg(scip,
"Capacity is to big, so we cannot handle it here.\n");
1290 assert(capacity < INT_MAX);
1292 intcap = (int)capacity;
1293 assert(intcap >= 0);
1294 assert(nmyitems > 0);
1295 assert(
sizeof(
size_t) >=
sizeof(
int));
1300 if( intcap < 0 || (intcap > 0 && (((
size_t)nmyitems) > (maxsize_t / (
size_t)intcap /
sizeof(*optvalues)) || ((
size_t)nmyitems) * ((
size_t)intcap) *
sizeof(*optvalues) > ((
size_t)INT_MAX) )) )
1302 SCIPdebugMsg(scip,
"Too much memory (%lu) would be consumed.\n", (
unsigned long) (((
size_t)nmyitems) * ((
size_t)intcap) *
sizeof(*optvalues)));
1326 for( j = nmyitems - 1; j >= 0; --j )
1327 tempsort[j] = myprofits[j]/((
SCIP_Real) myweights[j]);
1332 greedysolweight = 0;
1333 greedysolvalue = 0.0;
1335 greedycap = capacity + (minweight - 1);
1340 for( j = 0; j < nmyitems; ++j )
1342 assert(myweights[j] <= greedycap);
1345 if( myweights[j] + greedysolweight <= greedycap )
1348 greedysolweight += myweights[j];
1349 greedysolvalue += myprofits[j];
1352 else if( greedysolweight < greedycap )
1356 assert(greedysolweight > 0);
1357 assert(greedysolvalue > 0.0);
1362 assert(greedysolweight == greedycap);
1366 greedysolweight = 0;
1369 if( solitems != NULL)
1372 for( j = 0; j < nmyitems; ++j )
1375 if( myweights[j] + greedysolweight <= greedycap )
1377 solitems[*nsolitems] = myitems[j];
1379 greedysolweight += myweights[j];
1383 nonsolitems[*nnonsolitems] = myitems[j];
1389 if( solval != NULL )
1391 assert(greedysolvalue > 0.0);
1392 *solval += greedysolvalue;
1409 assert(myweights[0] - minweight < INT_MAX);
1410 currminweight = (int) (myweights[0] - minweight);
1411 allcurrminweight[0] = currminweight;
1414 for( d = currminweight; d < intcap; ++d )
1415 optvalues[d] = myprofits[0];
1417 for( j = 1; j < nmyitems; ++j )
1422 intweight = (int)(myweights[j] - minweight);
1423 assert(0 <= intweight && intweight < intcap);
1426 for( d = currminweight; d < intweight && d < intcap; ++d )
1427 optvalues[
IDX(j,d)] = optvalues[
IDX(j-1,d)];
1430 for( d = intweight; d < intcap; ++d )
1435 if( d < currminweight )
1437 optvalues[
IDX(j,d)] = myprofits[j];
1443 if( d - myweights[j] < currminweight )
1444 sumprofit = myprofits[j];
1446 sumprofit = optvalues[
IDX(j-1,(
int)(d-myweights[j]))] + myprofits[j];
1448 optvalues[
IDX(j,d)] =
MAX(sumprofit, optvalues[
IDX(j-1,d)]);
1452 if( intweight < currminweight )
1453 currminweight = intweight;
1455 allcurrminweight[j] = currminweight;
1459 if( solitems != NULL)
1463 SCIPdebugMsg(scip,
"Fill the solution vector after solving exactly.\n");
1466 for( j = nmyitems - 1; j > 0; --j )
1471 if( d < allcurrminweight[j] )
1478 if( d < allcurrminweight[j-1] || optvalues[
IDX(j,d)] > optvalues[
IDX(j-1,d)] )
1480 solitems[*nsolitems] = myitems[j];
1485 d = (int)(d - myweights[j]);
1490 nonsolitems[*nnonsolitems] = myitems[j];
1496 if( d >= allcurrminweight[j] )
1499 solitems[*nsolitems] = myitems[j];
1505 assert(d < allcurrminweight[j]);
1507 for( ; j >= 0; --j )
1509 nonsolitems[*nnonsolitems] = myitems[j];
1514 assert(*nsolitems + *nnonsolitems == nitems);
1518 if( solval != NULL )
1519 *solval += optvalues[
IDX(nmyitems-1,intcap-1)];
1559 assert(weights != NULL);
1560 assert(profits != NULL);
1561 assert(capacity >= 0);
1562 assert(items != NULL);
1563 assert(nitems >= 0);
1565 if( solitems != NULL )
1570 if( solval != NULL )
1576 for( j = nitems - 1; j >= 0; --j )
1578 tempsort[j] = profits[j]/((
SCIP_Real) weights[j]);
1588 for( j = 0; j < nitems && solitemsweight + weights[j] <= capacity; ++j )
1590 if( solitems != NULL )
1592 solitems[*nsolitems] = items[j];
1595 if( solval != NULL )
1596 (*solval) += profits[j];
1597 solitemsweight += weights[j];
1599 for( ; j < nitems && solitems != NULL; j++ )
1601 nonsolitems[*nnonsolitems] = items[j];
1621 int nnontrivialgubconss;
1624 nnontrivialgubconss = 0;
1626 SCIPdebugMsg(scip,
" Nontrivial GUBs of current GUB set:\n");
1629 for( c = 0; c < gubset->
ngubconss; c++ )
1649 if( solvals != NULL )
1651 gubsolval += solvals[currentvar];
1661 if( solvals != NULL )
1664 SCIPisFeasGT(scip, gubsolval, 1.0) ?
"--> violated" :
"");
1670 nnontrivialgubconss++;
1685 assert(scip != NULL);
1686 assert(gubcons != NULL);
1694 (*gubcons)->ngubvars = 0;
1706 assert(scip != NULL);
1707 assert(gubcons != NULL);
1708 assert((*gubcons)->gubvars != NULL);
1709 assert((*gubcons)->gubvarsstatus != NULL);
1727 assert(scip != NULL);
1728 assert(gubcons != NULL);
1730 assert(gubcons->
gubvars != NULL);
1763 assert(scip != NULL);
1764 assert(gubcons != NULL);
1766 assert(gubvarsidx >= 0 && gubvarsidx < gubcons->ngubvars);
1767 assert(gubcons->
ngubvars >= gubvarsidx+1);
1768 assert(gubcons->
gubvars[gubvarsidx] == var);
1806 assert(scip != NULL);
1807 assert(gubset != NULL);
1809 assert(oldgubcons >= 0 && oldgubcons < gubset->
ngubconss);
1810 assert(newgubcons >= 0 && newgubcons < gubset->ngubconss);
1811 assert(oldgubcons != newgubcons);
1828 gubset->
gubvarsidx[replacevar] = oldgubvaridx;
1841 SCIPdebugMsg(scip,
"deleting empty GUB cons<%d> from current GUB set\n", oldgubcons);
1843 GUBsetPrint(scip, gubset, vars, NULL);
1897 assert(scip != NULL);
1898 assert(gubset != NULL);
1934 assert(scip != NULL);
1935 assert(gubset != NULL);
1937 assert(weights != NULL);
1938 assert(capacity >= 0);
1946 (*gubset)->ngubconss =
nvars;
1947 (*gubset)->nvars =
nvars;
1950 for( i = 0; i <
nvars; i++ )
1959 (*gubset)->gubconssidx[i] = i;
1960 (*gubset)->gubvarsidx[i] = 0;
1961 assert((*gubset)->gubconss[i]->ngubvars == 1);
1964 if( weights[i] > capacity )
1981 assert(scip != NULL);
1982 assert(gubset != NULL);
1983 assert((*gubset)->gubconss != NULL);
1984 assert((*gubset)->gubconsstatus != NULL);
1985 assert((*gubset)->gubconssidx != NULL);
1986 assert((*gubset)->gubvarsidx != NULL);
1989 for( i = (*gubset)->ngubconss-1; i >= 0; --i )
1991 assert((*gubset)->gubconss[i] != NULL);
2022 assert(scip != NULL);
2023 assert(gubset != NULL);
2028 for( i = 0; i < gubset->
nvars; i++ )
2035 SCIPdebugMsg(scip,
" var<%d> should be in GUB<%d> at position<%d>, but stored is var<%d> instead\n", i,
2036 gubconsidx, gubvaridx, gubset->
gubconss[gubconsidx]->
gubvars[gubvaridx] );
2042 for( i = 0; i < gubset->
ngubconss; i++ )
2052 var1negated =
FALSE;
2059 var2negated =
FALSE;
2064 SCIPdebugMsg(scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n", i, j,
2067 SCIPdebugMsg(scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n", i, j,
2097 int*
const cliquepartition,
2109 int maxncliquevarscomp;
2114 assert(scip != NULL);
2115 assert(nvars == 0 || vars != NULL);
2116 assert(nvars == 0 || cliquepartition != NULL);
2117 assert(ncliques != NULL);
2135 for( i = nvars - 1; i >= 0; --i )
2137 tmpvalues[i] =
TRUE;
2138 cliquepartition[i] = -1;
2149 for( i = 0; i <
nvars; i++ )
2154 varseq[nvars-1-nignorevars] = i;
2160 varseq[nvarsused] = i;
2165 assert(nvarsused + nignorevars == nvars);
2174 for( i = 0; i <
nvars; ++i )
2176 if( cliquepartition[varseq[i]] == -1 )
2181 cliquepartition[varseq[i]] = *ncliques;
2182 cliquevars[0] = tmpvars[varseq[i]];
2183 cliquevalues[0] = tmpvalues[varseq[i]];
2192 for( j = i + 1; j < nvarsused; ++j )
2195 if( cliquepartition[varseq[j]] == -1 &&
SCIPvarIsActive(tmpvars[varseq[j]]) )
2200 for( k = ncliquevars - 1; k >= 0; --k )
2203 cliquevalues[k],
TRUE) )
2210 cliquepartition[varseq[j]] = cliquepartition[varseq[i]];
2211 cliquevars[ncliquevars] = tmpvars[varseq[j]];
2212 cliquevalues[ncliquevars] = tmpvalues[varseq[j]];
2222 assert(cliquepartition[varseq[i]] >= 0 && cliquepartition[varseq[i]] < i + 1);
2225 if( i * nvars > maxncliquevarscomp )
2229 for( ; i <
nvars; ++i )
2231 if( cliquepartition[varseq[i]] == -1 )
2233 cliquepartition[varseq[i]] = *ncliques;
2258 int* cliquepartition;
2261 int currentgubconsidx;
2267 assert(scip != NULL);
2268 assert(gubset != NULL);
2269 assert(vars != NULL);
2271 nvars = gubset->
nvars;
2284 for( i = 0; i < ncliques; i++ )
2287 gubfirstvar[i] = -1;
2290 for( i = 0; i <
nvars; i++ )
2292 assert(cliquepartition[i] >= 0);
2294 cliqueidx = cliquepartition[i];
2299 if( gubfirstvar[cliqueidx] == -1 )
2308 gubfirstvar[cliqueidx] = i;
2313 assert(gubfirstvar[cliqueidx] >= 0 && gubfirstvar[cliqueidx] < i);
2318 newgubconsidx = gubset->
gubconssidx[gubfirstvar[cliqueidx]];
2319 assert(newgubconsidx != currentgubconsidx);
2328 GUBsetPrint(scip, gubset, vars, solvals);
2380 assert(scip != NULL);
2381 assert(vars != NULL);
2383 assert(weights != NULL);
2384 assert(capacity >= 0);
2385 assert(solvals != NULL);
2386 assert(covervars != NULL);
2387 assert(noncovervars != NULL);
2388 assert(ncovervars != NULL);
2389 assert(nnoncovervars != NULL);
2390 assert(coverweight != NULL);
2391 assert(found != NULL);
2392 assert(ntightened != NULL);
2393 assert(fractional != NULL);
2395 SCIPdebugMsg(scip,
" get cover for knapsack constraint\n");
2419 fixedonesweight = 0;
2422 for( j = 0; j <
nvars; j++ )
2427 if( weights[j] > capacity )
2430 assert(!infeasible);
2438 fixedones[nfixedones] = j;
2440 fixedonesweight += weights[j];
2445 fixedzeros[nfixedzeros] = j;
2454 itemsweight += weights[j];
2457 assert(nfixedones + nfixedzeros + nitems == nvars - (*ntightened));
2462 assert(nitems >= 0);
2465 *fractional =
FALSE;
2468 assert(*fractional);
2486 for( j = 0; j < nitems; j++ )
2488 transweights[j] = weights[items[j]];
2489 transprofits[j] = 1.0 - solvals[items[j]];
2492 transcapacity = fixedonesweight + itemsweight - capacity - 1;
2497 if( transcapacity < 0 )
2521 for( j = 0; j < nitems; j++ )
2523 transprofits[j] *= weights[items[j]];
2535 noncovervars, covervars, nnoncovervars, ncovervars, NULL) );
2539 for( j = 0; j < *ncovervars; j++ )
2541 (*coverweight) += weights[covervars[j]];
2545 for( j = 0; j < nfixedones; j++ )
2547 covervars[*ncovervars] = fixedones[j];
2549 (*coverweight) += weights[fixedones[j]];
2553 for( j = 0; j < nfixedzeros; j++ )
2555 noncovervars[*nnoncovervars] = fixedzeros[j];
2558 assert((*ncovervars) + (*nnoncovervars) == nvars - (*ntightened));
2559 assert((*coverweight) > capacity);
2570 SCIPdebugMsg(scip,
" get cover for knapsack constraint -- end\n");
2592 assert(weights != NULL);
2593 assert(covervars != NULL);
2594 assert(ncovervars > 0);
2596 minweight = weights[covervars[minweightidx]];
2599 for( i = 0; i < j; i++ )
2601 assert(weights[covervars[i]] > minweight);
2602 if( weights[covervars[i]] <= minweight )
2607 for( i = 0; i < j; i++ )
2609 assert(coverweight - weights[covervars[i]] <= capacity);
2610 if( coverweight - weights[covervars[i]] > capacity )
2635 assert(scip != NULL);
2636 assert(ncovervars >= 0);
2637 assert(solvals != NULL);
2638 assert(covervars != NULL);
2639 assert(varsC1 != NULL);
2640 assert(varsC2 != NULL);
2641 assert(nvarsC1 != NULL);
2642 assert(nvarsC2 != NULL);
2646 for( j = 0; j < ncovervars; j++ )
2648 assert(
SCIPisFeasGT(scip, solvals[covervars[j]], 0.0));
2651 if(
SCIPisGE(scip, solvals[covervars[j]], 1.0) )
2653 varsC2[*nvarsC2] = covervars[j];
2659 assert(
SCIPisLT(scip, solvals[covervars[j]], 1.0));
2660 varsC1[*nvarsC1] = covervars[j];
2664 assert((*nvarsC1) + (*nvarsC2) == ncovervars);
2683 assert(*nvarsC1 >= 0 && *nvarsC1 <= 1);
2684 assert(*nvarsC2 > 0);
2690 for( j = 0; j < *nvarsC2; j++ )
2691 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
2695 assert(*nvarsC2 == 1 || weights[varsC2[(*nvarsC2)-1]] <= weights[varsC2[(*nvarsC2)-2]]);
2696 while( *nvarsC1 < 2 && *nvarsC2 > 0 )
2698 varsC1[*nvarsC1] = varsC2[(*nvarsC2)-1];
2723 assert(*nvarsC1 >= 0 && *nvarsC1 <= 1);
2724 assert(*nvarsC2 > 0);
2730 for( j = 0; j < *nvarsC2; j++ )
2731 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
2735 assert(*nvarsC2 == 1 || weights[varsC2[(*nvarsC2)-1]] <= weights[varsC2[(*nvarsC2)-2]]);
2736 varsC1[*nvarsC1] = varsC2[(*nvarsC2)-1];
2765 assert(scip != NULL);
2766 assert(nnoncovervars >= 0);
2767 assert(solvals != NULL);
2768 assert(noncovervars != NULL);
2769 assert(varsF != NULL);
2770 assert(varsR != NULL);
2771 assert(nvarsF != NULL);
2772 assert(nvarsR != NULL);
2777 for( j = 0; j < nnoncovervars; j++ )
2780 if(
SCIPisFeasEQ(scip, solvals[noncovervars[j]], 0.0) )
2782 varsR[*nvarsR] = noncovervars[j];
2788 assert(
SCIPisFeasGT(scip, solvals[noncovervars[j]], 0.0));
2789 varsF[*nvarsF] = noncovervars[j];
2793 assert((*nvarsF) + (*nvarsR) == nnoncovervars);
2812 SORTKEYPAIR** sortkeypairsF;
2813 SORTKEYPAIR* sortkeypairsFstore;
2818 assert(scip != NULL);
2819 assert(solvals != NULL);
2820 assert(weights != NULL);
2821 assert(varsF != NULL);
2822 assert(varsC2 != NULL);
2823 assert(varsR != NULL);
2824 assert(nvarsF >= 0);
2825 assert(nvarsC2 >= 0);
2826 assert(nvarsR >= 0);
2840 for( j = 0; j < nvarsF; j++ )
2842 sortkeypairsF[j] = &(sortkeypairsFstore[j]);
2843 sortkeypairsF[j]->key1 = solvals[varsF[j]];
2844 sortkeypairsF[j]->key2 = (
SCIP_Real) weights[varsF[j]];
2850 for( j = 0; j < nvarsC2; j++ )
2851 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
2856 for( j = 0; j < nvarsR; j++ )
2857 sortkeysR[j] = (
SCIP_Real) weights[varsR[j]];
2907 int* ngubconscapexceed,
2912 SORTKEYPAIR** sortkeypairsF;
2914 SORTKEYPAIR** sortkeypairsGFC1;
2915 SORTKEYPAIR* sortkeypairsGFC1store;
2919 int* nC1varsingubcons;
2930 #if GUBSPLITGNC1GUBS 2936 assert(scip != NULL);
2937 assert(gubset != NULL);
2938 assert(solvals != NULL);
2939 assert(weights != NULL);
2940 assert(varsC1 != NULL);
2941 assert(varsC2 != NULL);
2942 assert(varsF != NULL);
2943 assert(varsR != NULL);
2944 assert(nvarsC1 > 0);
2945 assert(nvarsC2 >= 0);
2946 assert(nvarsF >= 0);
2947 assert(nvarsR >= 0);
2948 assert(gubconsGC1 != NULL);
2949 assert(gubconsGC2 != NULL);
2950 assert(gubconsGFC1 != NULL);
2951 assert(gubconsGR != NULL);
2952 assert(ngubconsGC1 != NULL);
2953 assert(ngubconsGC2 != NULL);
2954 assert(ngubconsGFC1 != NULL);
2955 assert(ngubconsGR != NULL);
2956 assert(maxgubvarssize != NULL);
3002 for( j = 0; j < nvarsC1; j++ )
3005 sortkeysC1[j] = (
SCIP_Real) weights[varsC1[j]];
3018 for( j = 0; j < nvarsF; j++ )
3023 sortkeypairsF[j]->key1 = solvals[varsF[j]];
3024 sortkeypairsF[j]->key2 = (
SCIP_Real) weights[varsF[j]];
3037 for( j = 0; j < nvarsC2; j++ )
3040 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
3052 for( j = 0; j < nvarsR; j++ )
3055 sortkeysR[j] = (
SCIP_Real) weights[varsR[j]];
3087 for( j = nvarsF-1; j >= 0; j-- )
3100 sortkeypairsGFC1[i] = &(sortkeypairsGFC1store[i]);
3101 sortkeypairsGFC1[i]->key1 = 0.0;
3102 sortkeypairsGFC1[i]->key2 = 0.0;
3108 *ngubconscapexceed = 0;
3109 *maxgubvarssize = 0;
3112 for( i = 0; i < gubset->
ngubconss; i++ )
3122 for( i = 0; i < nvarsC1; i++ )
3124 int nvarsC1capexceed;
3126 nvarsC1capexceed = 0;
3132 assert(gubconsidx >= 0 && gubconsidx < ngubconss);
3138 targetvar = gubset->
gubconss[gubconsidx]->
gubvars[nC1varsingubcons[gubconsidx]];
3140 nC1varsingubcons[gubconsidx]++;
3153 #if GUBSPLITGNC1GUBS 3154 gubconswithF =
FALSE;
3169 #if GUBSPLITGNC1GUBS 3170 gubconswithF =
TRUE;
3172 sortkeypairsGFC1[*ngubconsGFC1]->key1 += 1.0;
3174 if( solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3175 sortkeypairsGFC1[*ngubconsGFC1]->key2 = solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]];
3186 gubconsGC1[*ngubconsGC1] = gubconsidx;
3201 #if GUBSPLITGNC1GUBS 3222 gubconsidx, ngubconss-1) );
3232 gubconsGR[*ngubconsGR] = ngubconss-1;
3238 assert(gubconswithF);
3241 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3246 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3255 for( i = 0; i < nvarsC2; i++ )
3261 assert(gubconsidx >= 0 && gubconsidx < ngubconss);
3263 assert(varidx == 0);
3271 gubconsGC2[*ngubconsGC2] = gubconsidx;
3285 for( i = 0; i < nvarsF; i++ )
3291 assert(gubconsidx >= 0 && gubconsidx < ngubconss);
3316 sortkeypairsGFC1[*ngubconsGFC1]->key1 += 1.0;
3318 if( solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3319 sortkeypairsGFC1[*ngubconsGFC1]->key2 = solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]];
3324 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3335 for( i = 0; i < nvarsR; i++ )
3341 assert(gubconsidx >= 0 && gubconsidx < ngubconss);
3359 gubconsGR[*ngubconsGR] = gubconsidx;
3366 assert(nvarsprocessed == nvarsC1 + nvarsC2 + nvarsF + nvarsR);
3369 (*ngubconscapexceed) = ngubconss - (ngubconsGOC1 + (*ngubconsGC2) + (*ngubconsGFC1) + (*ngubconsGR));
3370 assert(*ngubconscapexceed >= 0);
3383 assert(check == *ngubconscapexceed);
3388 if( (*ngubconsGFC1) > 0 )
3390 SCIPsortDownPtrInt((
void**)sortkeypairsGFC1, gubconsGFC1, compSortkeypairs, (*ngubconsGFC1));
3394 #if GUBSPLITGNC1GUBS 3395 ngubconss = origngubconss;
3410 int* minweightssize,
3416 assert(minweightsptr != NULL);
3417 assert(*minweightsptr != NULL);
3418 assert(minweightslen != NULL);
3419 assert(*minweightslen >= 0);
3420 assert(minweightssize != NULL);
3421 assert(*minweightssize >= 0);
3423 if( newlen > *minweightssize )
3430 *minweightssize = newsize;
3432 assert(newlen <= *minweightssize);
3435 for( j = *minweightslen; j < newlen; ++j )
3437 *minweightslen = newlen;
3486 assert(scip != NULL);
3487 assert(vars != NULL);
3489 assert(weights != NULL);
3490 assert(capacity >= 0);
3491 assert(solvals != NULL);
3492 assert(varsM1 != NULL);
3493 assert(varsM2 != NULL);
3494 assert(varsF != NULL);
3495 assert(varsR != NULL);
3496 assert(nvarsM1 >= 0 && nvarsM1 <= nvars - ntightened);
3497 assert(nvarsM2 >= 0 && nvarsM2 <= nvars - ntightened);
3498 assert(nvarsF >= 0 && nvarsF <= nvars - ntightened);
3499 assert(nvarsR >= 0 && nvarsR <= nvars - ntightened);
3500 assert(nvarsM1 + nvarsM2 + nvarsF + nvarsR == nvars - ntightened);
3501 assert(alpha0 >= 0);
3502 assert(liftcoefs != NULL);
3503 assert(cutact != NULL);
3504 assert(liftrhs != NULL);
3507 minweightssize = nvarsM1 + 1;
3518 for( j = 0; j < nvarsM1; j++ )
3520 assert(liftcoefs[varsM1[j]] == 0);
3521 liftcoefs[varsM1[j]] = 1;
3522 sortkeys[j] = (
SCIP_Real) (weights[varsM1[j]]);
3523 (*cutact) += solvals[varsM1[j]];
3535 for( w = 1; w <= nvarsM1; w++ )
3536 minweights[w] = minweights[w-1] + weights[varsM1[w-1]];
3537 minweightslen = nvarsM1 + 1;
3540 fixedonesweight = 0;
3541 for( j = 0; j < nvarsM2; j++ )
3542 fixedonesweight += weights[varsM2[j]];
3543 assert(fixedonesweight >= 0);
3549 for( j = 0; j < nvarsF; j++ )
3557 weight = weights[liftvar];
3558 assert(liftvar >= 0 && liftvar < nvars);
3565 if( capacity - fixedonesweight - weight < 0 )
3573 else if( minweights[*liftrhs] <= capacity - fixedonesweight - weight )
3586 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
3588 right = (*liftrhs) + 1;
3589 while( left < right - 1 )
3591 middle = (left + right) / 2;
3592 assert(0 <= middle && middle < minweightslen);
3593 if( minweights[middle] <= capacity - fixedonesweight - weight )
3598 assert(left == right - 1);
3599 assert(0 <= left && left < minweightslen);
3600 assert(minweights[left] <= capacity - fixedonesweight - weight );
3601 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight - weight);
3605 assert(z <= *liftrhs);
3609 liftcoef = (*liftrhs) - z;
3610 liftcoefs[liftvar] = liftcoef;
3611 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
3618 (*cutact) += liftcoef * solvals[liftvar];
3632 for( w = minweightslen - 1; w >= 0; w-- )
3637 min = MIN(minweights[w], weight);
3638 minweights[w] = min;
3642 assert(w >= liftcoef);
3643 min = MIN(minweights[w], minweights[w - liftcoef] + weight);
3644 minweights[w] = min;
3648 assert(minweights[0] == 0);
3651 for( j = 0; j < nvarsM2; j++ )
3661 liftvar = varsM2[j];
3662 weight = weights[liftvar];
3664 assert(liftvar >= 0 && liftvar < nvars);
3671 right = minweightslen;
3672 while( left < right - 1 )
3674 middle = (left + right) / 2;
3675 assert(0 <= middle && middle < minweightslen);
3676 if( minweights[middle] <= capacity - fixedonesweight + weight )
3681 assert(left == right - 1);
3682 assert(0 <= left && left < minweightslen);
3683 assert(minweights[left] <= capacity - fixedonesweight + weight );
3684 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight + weight);
3688 assert(z >= *liftrhs);
3691 liftcoef = z - (*liftrhs);
3692 liftcoefs[liftvar] = liftcoef;
3693 assert(liftcoef >= 0);
3696 fixedonesweight -= weight;
3699 (*liftrhs) += liftcoef;
3700 assert(*liftrhs >= alpha0);
3707 (*cutact) += liftcoef * solvals[liftvar];
3721 for( w = minweightslen - 1; w >= 0; w-- )
3726 min = MIN(minweights[w], weight);
3727 minweights[w] = min;
3731 assert(w >= liftcoef);
3732 min = MIN(minweights[w], minweights[w - liftcoef] + weight);
3733 minweights[w] = min;
3737 assert(fixedonesweight == 0);
3738 assert(*liftrhs >= alpha0);
3741 for( j = 0; j < nvarsR; j++ )
3749 weight = weights[liftvar];
3750 assert(liftvar >= 0 && liftvar < nvars);
3753 assert(capacity - weight >= 0);
3754 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - weight);
3759 if( minweights[*liftrhs] <= capacity - weight )
3772 right = (*liftrhs) + 1;
3773 while( left < right - 1)
3775 middle = (left + right) / 2;
3776 assert(0 <= middle && middle < minweightslen);
3777 if( minweights[middle] <= capacity - weight )
3782 assert(left == right - 1);
3783 assert(0 <= left && left < minweightslen);
3784 assert(minweights[left] <= capacity - weight );
3785 assert(left == minweightslen - 1 || minweights[left+1] > capacity - weight);
3789 assert(z <= *liftrhs);
3793 liftcoef = (*liftrhs) - z;
3794 liftcoefs[liftvar] = liftcoef;
3795 assert(liftcoef >= 0 && liftcoef <= *liftrhs);
3802 (*cutact) += liftcoef * solvals[liftvar];
3808 for( w = *liftrhs; w >= 0; w-- )
3813 min = MIN(minweights[w], weight);
3814 minweights[w] = min;
3818 assert(w >= liftcoef);
3819 min = MIN(minweights[w], minweights[w - liftcoef] + weight);
3820 minweights[w] = min;
3847 return (val1 + val2);
3869 assert(unfinished[w2] == 0);
3870 for( w1 = 0; w1 < minweightslen; w1++ )
3871 minweights[w1] = finished[w1];
3874 for( w2 = 1; w2 < minweightslen; w2++ )
3879 for( w1 = 0; w1 < minweightslen - w2; w1++ )
3884 if( temp <= minweights[w1+w2] )
3885 minweights[w1+w2] = temp;
3909 int ngubconscapexceed,
3963 assert(gubset != NULL);
3966 assert(gubset != NULL);
3969 nvars = gubset->
nvars;
3971 assert(scip != NULL);
3972 assert(vars != NULL);
3974 assert(weights != NULL);
3975 assert(capacity >= 0);
3976 assert(solvals != NULL);
3977 assert(gubconsGC1 != NULL);
3978 assert(gubconsGC2 != NULL);
3979 assert(gubconsGFC1 != NULL);
3980 assert(gubconsGR != NULL);
3981 assert(ngubconsGC1 >= 0 && ngubconsGC1 <= ngubconss - ngubconscapexceed);
3982 assert(ngubconsGC2 >= 0 && ngubconsGC2 <= ngubconss - ngubconscapexceed);
3983 assert(ngubconsGFC1 >= 0 && ngubconsGFC1 <= ngubconss - ngubconscapexceed);
3984 assert(ngubconsGR >= 0 && ngubconsGR <= ngubconss - ngubconscapexceed);
3985 assert(alpha0 >= 0);
3986 assert(liftcoefs != NULL);
3987 assert(cutact != NULL);
3988 assert(liftrhs != NULL);
3990 minweightssize = ngubconsGC1+1;
4009 for( j = 0; j < ngubconsGC1; j++ )
4013 gubconsGOC1[ngubconsGOC1] = gubconsGC1[j];
4019 gubconsGNC1[ngubconsGNC1] = gubconsGC1[j];
4026 assert(varidx >= 0 && varidx < nvars);
4027 assert(liftcoefs[varidx] == 0);
4029 liftcoefs[varidx] = 1;
4030 (*cutact) += solvals[varidx];
4034 assert(ngubconsGOC1 + ngubconsGFC1 + ngubconsGC2 + ngubconsGR == ngubconss - ngubconscapexceed);
4035 assert(ngubconsGOC1 + ngubconsGNC1 == ngubconsGC1);
4056 assert(ngubconsGOC1 <= ngubconsGC1);
4058 for( w = 1; w <= ngubconsGOC1; w++ )
4060 liftgubconsidx = gubconsGOC1[w-1];
4067 assert(varidx >= 0 && varidx < nvars);
4068 assert(liftcoefs[varidx] == 1);
4070 min = weights[varidx];
4071 finished[w] = finished[w-1] + min;
4078 assert(varidx >= 0 && varidx < nvars);
4079 assert(liftcoefs[varidx] == 1);
4080 assert(weights[varidx] >= min);
4084 for( w = ngubconsGOC1+1; w <= ngubconsGC1; w++ )
4092 assert(ngubconsGNC1 <= ngubconsGC1);
4094 for( w = 1; w <= ngubconsGNC1; w++ )
4096 liftgubconsidx = gubconsGNC1[w-1];
4103 assert(varidx >= 0 && varidx < nvars);
4104 assert(liftcoefs[varidx] == 1);
4106 min = weights[varidx];
4107 unfinished[w] = unfinished[w-1] + min;
4114 assert(varidx >= 0 && varidx < nvars);
4115 assert(liftcoefs[varidx] == 1);
4116 assert(weights[varidx] >= min );
4120 for( w = ngubconsGNC1 + 1; w <= ngubconsGC1; w++ )
4128 assert(ngubconsGOC1 + ngubconsGNC1 == ngubconsGC1);
4130 for( w = 1; w <= ngubconsGC1; w++ )
4132 liftgubconsidx = gubconsGC1[w-1];
4140 assert(varidx >= 0 && varidx < nvars);
4141 assert(liftcoefs[varidx] == 1);
4143 min = weights[varidx];
4144 minweights[w] = minweights[w-1] + min;
4151 assert(varidx >= 0 && varidx < nvars);
4152 assert(liftcoefs[varidx] == 1);
4153 assert(weights[varidx] >= min);
4157 minweightslen = ngubconsGC1 + 1;
4160 fixedonesweight = 0;
4161 for( j = 0; j < ngubconsGC2; j++ )
4166 assert(varidx >= 0 && varidx < nvars);
4169 fixedonesweight += weights[varidx];
4171 assert(fixedonesweight >= 0);
4177 for( j = 0; j < ngubconsGFC1; j++ )
4179 liftgubconsidx = gubconsGFC1[j];
4180 assert(liftgubconsidx >= 0 && liftgubconsidx < ngubconss);
4190 assert(ngubconsGNC1 > 0);
4203 weight = weights[liftgubvars[0]];
4205 weightdiff2 = unfinished[ngubconsGNC1] - weight;
4207 for( w = ngubconsGNC1-1; w >= 1; w-- )
4209 weightdiff1 = weightdiff2;
4210 weightdiff2 = unfinished[w] - weight;
4212 if( unfinished[w] < weightdiff1 )
4213 unfinished[w] = weightdiff1;
4221 assert(minweights[0] == 0);
4242 weight = weights[liftvar];
4244 assert(liftvar >= 0 && liftvar < nvars);
4245 assert(capacity - weight >= 0);
4250 liftgubvars[nliftgubvars] = liftvar;
4256 if( capacity - fixedonesweight - weight < 0 )
4264 else if( minweights[*liftrhs] <= capacity - fixedonesweight - weight )
4273 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
4275 right = (*liftrhs) + 1;
4276 while( left < right - 1 )
4278 middle = (left + right) / 2;
4279 assert(0 <= middle && middle < minweightslen);
4280 if( minweights[middle] <= capacity - fixedonesweight - weight )
4285 assert(left == right - 1);
4286 assert(0 <= left && left < minweightslen);
4287 assert(minweights[left] <= capacity - fixedonesweight - weight);
4288 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight - weight);
4292 assert(z <= *liftrhs);
4296 liftcoef = (*liftrhs) - z;
4297 liftcoefs[liftvar] = liftcoef;
4298 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
4301 (*cutact) += liftcoef * solvals[liftvar];
4304 sumliftcoef += liftcoefs[liftvar];
4310 assert(nliftgubvars > nliftgubC1);
4316 if( sumliftcoef == 0 )
4320 weight = weights[liftgubvars[0]];
4325 for( w = minweightslen-1; w >= 1; w-- )
4330 finished[w] = MIN(finished[w], tmpval);
4333 minweights[w] = MIN(minweights[w], tmpval);
4348 tmplen = minweightslen;
4349 tmpsize = minweightssize;
4351 tmplen = minweightslen;
4352 tmpsize = minweightssize;
4366 for( w = minweightslen-1; w >= 0; w-- )
4371 for( k = 0; k < nliftgubvars; k++ )
4373 liftcoef = liftcoefs[liftgubvars[k]];
4374 weight = weights[liftgubvars[k]];
4378 minfinished = MIN(finished[w], weight);
4379 minminweight = MIN(minweights[w], weight);
4381 finished[w] = minfinished;
4382 minweights[w] = minminweight;
4388 assert(w >= liftcoef);
4391 minfinished = MIN(finished[w], tmpval);
4394 minminweight = MIN(minweights[w], tmpval);
4396 finished[w] = minfinished;
4397 minweights[w] = minminweight;
4401 assert(minweights[0] == 0);
4403 assert(ngubconsGNC1 == 0);
4410 for( j = 0; j < ngubconsGC2; j++ )
4412 liftgubconsidx = gubconsGC2[j];
4414 assert(liftgubconsidx >=0 && liftgubconsidx < ngubconss);
4420 weight = weights[liftvar];
4422 assert(liftvar >= 0 && liftvar < nvars);
4430 right = minweightslen;
4431 while( left < right - 1 )
4433 middle = (left + right) / 2;
4434 assert(0 <= middle && middle < minweightslen);
4435 if( minweights[middle] <= capacity - fixedonesweight + weight )
4440 assert(left == right - 1);
4441 assert(0 <= left && left < minweightslen);
4442 assert(minweights[left] <= capacity - fixedonesweight + weight);
4443 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - fixedonesweight + weight);
4447 assert(z >= *liftrhs);
4450 liftcoef = z - (*liftrhs);
4451 liftcoefs[liftvar] = liftcoef;
4452 assert(liftcoef >= 0);
4455 fixedonesweight -= weight;
4458 (*liftrhs) += liftcoef;
4459 assert(*liftrhs >= alpha0);
4466 (*cutact) += liftcoef * solvals[liftvar];
4480 for( w = minweightslen - 1; w >= 0; w-- )
4484 min = MIN(minweights[w], weight);
4485 minweights[w] = min;
4491 assert(w >= liftcoef);
4494 min = MIN(minweights[w], tmpval);
4495 minweights[w] = min;
4499 assert(fixedonesweight == 0);
4500 assert(*liftrhs >= alpha0);
4503 for( j = 0; j < ngubconsGR; j++ )
4505 liftgubconsidx = gubconsGR[j];
4507 assert(liftgubconsidx >=0 && liftgubconsidx < ngubconss);
4517 weight = weights[liftvar];
4519 assert(liftvar >= 0 && liftvar < nvars);
4520 assert(capacity - weight >= 0);
4521 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - weight);
4526 liftgubvars[nliftgubvars] = liftvar;
4532 if( minweights[*liftrhs] <= capacity - weight )
4541 right = (*liftrhs) + 1;
4542 while( left < right - 1 )
4544 middle = (left + right) / 2;
4545 assert(0 <= middle && middle < minweightslen);
4546 if( minweights[middle] <= capacity - weight )
4551 assert(left == right - 1);
4552 assert(0 <= left && left < minweightslen);
4553 assert(minweights[left] <= capacity - weight);
4554 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - weight);
4558 assert(z <= *liftrhs);
4561 liftcoef = (*liftrhs) - z;
4562 liftcoefs[liftvar] = liftcoef;
4563 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
4566 (*cutact) += liftcoef * solvals[liftvar];
4569 sumliftcoef += liftcoefs[liftvar];
4574 assert(nliftgubvars >= 1);
4577 if( sumliftcoef == 0 )
4583 for( w = *liftrhs; w >= 0; w-- )
4585 for( k = 0; k < nliftgubvars; k++ )
4587 liftcoef = liftcoefs[liftgubvars[k]];
4588 weight = weights[liftgubvars[k]];
4592 min = MIN(minweights[w], weight);
4593 minweights[w] = min;
4599 assert(w >= liftcoef);
4602 min = MIN(minweights[w], tmpval);
4603 minweights[w] = min;
4607 assert(minweights[0] == 0);
4665 assert(scip != NULL);
4666 assert(vars != NULL);
4668 assert(weights != NULL);
4669 assert(capacity >= 0);
4670 assert(solvals != NULL);
4671 assert(covervars != NULL);
4672 assert(noncovervars != NULL);
4673 assert(ncovervars > 0 && ncovervars <= nvars);
4674 assert(nnoncovervars >= 0 && nnoncovervars <= nvars - ntightened);
4675 assert(ncovervars + nnoncovervars == nvars - ntightened);
4676 assert(liftcoefs != NULL);
4677 assert(cutact != NULL);
4692 for( j = 0; j < ncovervars; j++ )
4694 assert(liftcoefs[covervars[j]] == 0.0);
4695 liftcoefs[covervars[j]] = 1.0;
4696 sortkeys[j] = (
SCIP_Real) weights[covervars[j]];
4697 (*cutact) += solvals[covervars[j]];
4702 lambda = coverweight - capacity;
4706 maxweightsums[0] = 0;
4707 for( h = 1; h <= ncovervars; h++ )
4709 maxweightsums[h] = maxweightsums[h-1] + weights[covervars[h-1]];
4710 intervalends[h-1] = maxweightsums[h] - lambda;
4711 rhos[h-1] =
MAX(0, weights[covervars[h-1]] - weights[covervars[0]] + lambda);
4715 for( j = 0; j < nnoncovervars; j++ )
4716 sortkeys[j] = (
SCIP_Real) (weights[noncovervars[j]]);
4721 for( j = 0; j < nnoncovervars; j++ )
4727 liftvar = noncovervars[j];
4728 weight = weights[liftvar];
4730 while( intervalends[h] < weight )
4737 if( weight <= intervalends[h-1] + rhos[h] )
4741 tmp1 = (
SCIP_Real) (intervalends[h-1] + rhos[h] - weight);
4743 liftcoef = h - ( tmp1 / tmp2 );
4750 assert(liftcoefs[liftvar] == 0.0);
4751 liftcoefs[liftvar] = liftcoef;
4754 (*cutact) += liftcoef * solvals[liftvar];
4782 int* nonmincovervars,
4784 int nnonmincovervars,
4803 assert( cutoff != NULL );
4818 getPartitionCovervars(scip, solvals, mincovervars, nmincovervars, varsC1, varsC2, &nvarsC1, &nvarsC2);
4819 assert(nvarsC1 + nvarsC2 == nmincovervars);
4820 assert(nmincovervars > 0);
4821 assert(nvarsC1 >= 0);
4824 if( nvarsC1 < 2 && nvarsC2 > 0)
4827 assert(nvarsC1 >= 1);
4829 assert(nvarsC2 == 0 || nvarsC1 >= 1);
4836 assert(nvarsF + nvarsR == nnonmincovervars);
4837 assert(nvarsC1 + nvarsC2 + nvarsF + nvarsR == nvars - ntightened);
4840 if( gubset == NULL )
4859 varsF, varsR, nvarsC1, nvarsC2, nvarsF, nvarsR, nvarsC1 - 1, liftcoefs, &cutact, &liftrhs) );
4876 assert(nvars == gubset->
nvars);
4896 nvarsC2, nvarsF, nvarsR, gubconsGC1, gubconsGC2, gubconsGFC1, gubconsGR, &ngubconsGC1, &ngubconsGC2,
4897 &ngubconsGFC1, &ngubconsGR, &nconstightened, &maxgubvarssize) );
4913 gubconsGC2, gubconsGFC1, gubconsGR, ngubconsGC1, ngubconsGC2, ngubconsGFC1, ngubconsGR,
4914 MIN(nvarsC1 - 1, ngubconsGC1), liftcoefs, &cutact, &liftrhs, maxgubvarssize) );
4931 assert( cons == NULL || sepa == NULL );
4939 else if ( sepa != NULL )
4952 assert(nvarsC1 + nvarsC2 + nvarsF + nvarsR == nvars - ntightened);
4953 for( j = 0; j < nvarsC1; j++ )
4957 for( j = 0; j < nvarsC2; j++ )
4959 if( liftcoefs[varsC2[j]] > 0 )
4964 for( j = 0; j < nvarsF; j++ )
4966 if( liftcoefs[varsF[j]] > 0 )
4971 for( j = 0; j < nvarsR; j++ )
4973 if( liftcoefs[varsR[j]] > 0 )
5016 int* nonfeassetvars,
5018 int nnonfeassetvars,
5037 assert( cutoff != NULL );
5052 getPartitionCovervars(scip, solvals, feassetvars, nfeassetvars, varsT1, varsT2, &nvarsT1, &nvarsT2);
5053 assert(nvarsT1 + nvarsT2 == nfeassetvars);
5056 if( nvarsT1 == 0 && nvarsT2 > 0)
5059 assert(nvarsT1 == 1);
5061 assert(nvarsT2 == 0 || nvarsT1 > 0);
5068 assert(nvarsF + nvarsR == nnonfeassetvars);
5069 assert(nvarsT1 + nvarsT2 + nvarsF + nvarsR == nvars - ntightened);
5088 SCIP_CALL(
sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsT1, varsT2, varsF, varsR,
5089 nvarsT1, nvarsT2, nvarsF, nvarsR, nvarsT1, liftcoefs, &cutact, &liftrhs) );
5098 assert( cons == NULL || sepa == NULL );
5106 else if ( sepa != NULL )
5119 assert(nvarsT1 + nvarsT2 + nvarsF + nvarsR == nvars - ntightened);
5120 for( j = 0; j < nvarsT1; j++ )
5124 for( j = 0; j < nvarsT2; j++ )
5126 if( liftcoefs[varsT2[j]] > 0 )
5131 for( j = 0; j < nvarsF; j++ )
5133 if( liftcoefs[varsF[j]] > 0 )
5138 for( j = 0; j < nvarsR; j++ )
5140 if( liftcoefs[varsR[j]] > 0 )
5183 int* nonmincovervars,
5185 int nnonmincovervars,
5196 assert( cutoff != NULL );
5214 nonmincovervars, nmincovervars, nnonmincovervars, mincoverweight, realliftcoefs, &cutact) );
5215 liftrhs = nmincovervars - 1;
5225 assert( cons == NULL || sepa == NULL );
5233 else if ( sepa != NULL )
5246 assert(nmincovervars + nnonmincovervars == nvars - ntightened);
5247 for( j = 0; j < nmincovervars; j++ )
5251 for( j = 0; j < nnonmincovervars; j++ )
5253 assert(
SCIPisFeasGE(scip, realliftcoefs[nonmincovervars[j]], 0.0));
5254 if(
SCIPisFeasGT(scip, realliftcoefs[nonmincovervars[j]], 0.0) )
5299 SORTKEYPAIR** sortkeypairs;
5306 assert(scip != NULL);
5307 assert(covervars != NULL);
5308 assert(noncovervars != NULL);
5309 assert(ncovervars != NULL);
5310 assert(*ncovervars > 0);
5311 assert(nnoncovervars != NULL);
5312 assert(*nnoncovervars >= 0);
5313 assert(coverweight != NULL);
5314 assert(*coverweight > 0);
5315 assert(*coverweight > capacity);
5318 nsortkeypairs = *ncovervars;
5326 assert(*ncovervars == nsortkeypairs);
5329 for( j = 0; j < *ncovervars; j++ )
5333 sortkeypairs[j]->key1 = solvals[covervars[j]];
5334 sortkeypairs[j]->key2 = (
SCIP_Real) weights[covervars[j]];
5339 for( j = 0; j < *ncovervars; j++ )
5343 sortkeypairs[j]->key1 = (solvals[covervars[j]] - 1.0) / ((
SCIP_Real) weights[covervars[j]]);
5344 sortkeypairs[j]->key2 = (
SCIP_Real) (-weights[covervars[j]]);
5347 SCIPsortPtrInt((
void**)sortkeypairs, covervars, compSortkeypairs, *ncovervars);
5351 minweight = weights[covervars[minweightidx]];
5352 for( j = 1; j < *ncovervars; j++ )
5354 if( weights[covervars[j]] <= minweight )
5357 minweight = weights[covervars[minweightidx]];
5360 assert(minweightidx >= 0 && minweightidx < *ncovervars);
5361 assert(minweight > 0 && minweight <= *coverweight);
5365 while( j < *ncovervars && ((*coverweight) - minweight > capacity) )
5367 assert(minweightidx >= j);
5368 assert(
checkMinweightidx(weights, capacity, covervars, *ncovervars, *coverweight, minweightidx, j));
5371 if( (*coverweight) - weights[covervars[j]] <= capacity )
5378 noncovervars[*nnoncovervars] = covervars[j];
5382 (*coverweight) -= weights[covervars[j]];
5383 for( k = j; k < (*ncovervars) - 1; k++ )
5384 covervars[k] = covervars[k+1];
5388 if( j == minweightidx )
5391 minweight = weights[covervars[minweightidx]];
5392 for( k = 1; k < *ncovervars; k++ )
5394 if( weights[covervars[k]] <= minweight )
5397 minweight = weights[covervars[minweightidx]];
5400 assert(minweight > 0 && minweight <= *coverweight);
5401 assert(minweightidx >= 0 && minweightidx < *ncovervars);
5405 assert(minweightidx > j);
5410 assert((*coverweight) > capacity);
5411 assert((*coverweight) - minweight <= capacity);
5414 for( j = nsortkeypairs-1; j >= 0; j-- )
5454 assert(scip != NULL);
5455 assert(covervars != NULL);
5456 assert(noncovervars != NULL);
5457 assert(ncovervars != NULL);
5458 assert(*ncovervars > 0);
5459 assert(nnoncovervars != NULL);
5460 assert(*nnoncovervars >= 0);
5461 assert(coverweight != NULL);
5462 assert(*coverweight > 0);
5463 assert(*coverweight > capacity);
5464 assert(*ncovervars + *nnoncovervars == nvars - ntightened);
5465 assert(cutoff != NULL);
5479 for( j = 0; j < *ncovervars; j++ )
5481 sortkeys[j] = solvals[covervars[j]];
5487 for( j = 0; j < *ncovervars; j++ )
5489 sortkeys[j] = (solvals[covervars[j]] - 1.0) / ((
SCIP_Real) weights[covervars[j]]);
5497 while( *ncovervars >= 2 )
5500 noncovervars[*nnoncovervars] = covervars[0];
5504 (*coverweight) -= weights[covervars[0]];
5505 for( k = 0; k < (*ncovervars) - 1; k++ )
5506 covervars[k] = covervars[k+1];
5509 assert(*ncovervars + *nnoncovervars == nvars - ntightened);
5510 if( (*coverweight) <= capacity )
5513 covervars, noncovervars, *ncovervars, *nnoncovervars, sol, cutoff, ncuts) );
5553 assert(scip != NULL);
5554 assert(capacity >= 0);
5555 assert(cutoff != NULL);
5556 assert(ncuts != NULL);
5563 assert(vars != NULL);
5565 assert(weights != NULL);
5585 SCIPdebugMsg(scip,
"separate cuts for knapsack constraint originated by cons <%s>:\n",
5587 for( i = 0; i <
nvars; ++i )
5616 modtransused =
TRUE;
5617 SCIP_CALL(
getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5618 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5620 assert(!coverfound || !fractional || ncovervars + nnoncovervars == nvars - ntightened);
5625 SCIPdebugMsg(scip,
" LMCI1-GUB terminated by no variable with fractional LP value.\n");
5640 &nnoncovervars, &coverweight, modtransused) );
5647 solvals, covervars, noncovervars, ncovervars, nnoncovervars, sol, gubset, cutoff, ncuts) );
5655 solvals, covervars, noncovervars, ncovervars, nnoncovervars, sol, NULL, cutoff, ncuts) );
5675 modtransused =
TRUE;
5676 SCIP_CALL(
getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5677 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5678 assert(!coverfound || !fractional || ncovervars + nnoncovervars == nvars - ntightened);
5691 &nnoncovervars, &coverweight, modtransused) );
5695 solvals, covervars, noncovervars, ncovervars, nnoncovervars, sol, NULL, cutoff, ncuts) );
5702 solvals, covervars, noncovervars, ncovervars, nnoncovervars, coverweight, sol, cutoff, ncuts) );
5717 modtransused =
FALSE;
5718 SCIP_CALL(
getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5719 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5721 assert(!coverfound || ncovervars + nnoncovervars == nvars - ntightened);
5730 SCIP_CALL(
getFeasibleSet(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, solvals, covervars, noncovervars,
5731 &ncovervars, &nnoncovervars, &coverweight, modtransused, sol, cutoff, ncuts) );
5778 assert(nknapvars > 0);
5779 assert(knapvars != NULL);
5780 assert(cutoff != NULL);
5803 if( conshdlr == NULL )
5805 noknapsackconshdlr =
TRUE;
5813 noknapsackconshdlr =
FALSE;
5815 assert(conshdlrdata != NULL);
5816 usegubs = conshdlrdata->usegubs;
5823 if( conshdlrdata->reals1size == 0 )
5826 conshdlrdata->reals1size = 1;
5827 conshdlrdata->reals1[0] = 0.0;
5830 assert(conshdlrdata->reals1size > 0);
5836 if( conshdlrdata->reals1size < nbinvars )
5838 int oldsize = conshdlrdata->reals1size;
5840 conshdlrdata->reals1size = nbinvars;
5842 BMSclearMemoryArray(&(conshdlrdata->reals1[oldsize]), conshdlrdata->reals1size - oldsize);
5844 binvals = conshdlrdata->reals1;
5848 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
5850 assert(binvals[tmp] == 0);
5868 for( i = 0; i < nknapvars; i++ )
5885 SCIPdebugMsg(scip,
"Solution value %.15g <%s> outside domain [0.0, 1.0]\n",
5891 if( !noknapsackconshdlr )
5893 assert(tmpindices != NULL);
5900 else if( valscale * knapvals[i] > 0.0 )
5919 for( j = 0; j < nvlb; j++ )
5930 SCIPdebugMsg(scip,
"variable bound <%s>[%g,%g] >= %g<%s>[%g,%g] + %g implies local cutoff\n",
5937 vlbsol = bvlb[j] *
SCIPgetSolVal(scip, sol, zvlb[j]) + dvlb[j];
5938 if(
SCIPisGE(scip, vlbsol, bestlbsol) )
5950 if( bestlbtype == -1 )
5952 rhs -= valscale * knapvals[i] * bestlbsol;
5953 SCIPdebugMsg(scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with lower bound %.15g (rhs=%.15g)\n",
5959 rhs -= valscale * knapvals[i] * dvlb[bestlbtype];
5960 binvals[
SCIPvarGetProbindex(zvlb[bestlbtype])] += valscale * knapvals[i] * bvlb[bestlbtype];
5965 if( !noknapsackconshdlr )
5967 assert(tmpindices != NULL);
5972 SCIPdebugMsg(scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable lower bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
5975 SCIPgetSolVal(scip, sol, zvlb[bestlbtype]), dvlb[bestlbtype], rhs);
5988 assert(valscale * knapvals[i] < 0.0);
5999 for( j = 0; j < nvub; j++ )
6010 SCIPdebugMsg(scip,
"variable bound <%s>[%g,%g] <= %g<%s>[%g,%g] + %g implies local cutoff\n",
6017 vubsol = bvub[j] *
SCIPgetSolVal(scip, sol, zvub[j]) + dvub[j];
6018 if(
SCIPisLE(scip, vubsol, bestubsol) )
6030 if( bestubtype == -1 )
6032 rhs -= valscale * knapvals[i] * bestubsol;
6033 SCIPdebugMsg(scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with upper bound %.15g (rhs=%.15g)\n",
6039 rhs -= valscale * knapvals[i] * dvub[bestubtype];
6040 binvals[
SCIPvarGetProbindex(zvub[bestubtype])] += valscale * knapvals[i] * bvub[bestubtype];
6045 if( !noknapsackconshdlr )
6047 assert(tmpindices != NULL);
6052 SCIPdebugMsg(scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable upper bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6055 SCIPgetSolVal(scip, sol, zvub[bestubtype]), dvub[bestubtype], rhs);
6071 SCIPdebugMsg(scip,
" -> intscalar = %.15g\n", intscalar);
6081 rhs = rhs*intscalar;
6086 for( i = 0; i < nbinvars; i++ )
6098 SCIPdebugMsg(scip,
" -> positive scaled binary variable %+" SCIP_LONGINT_FORMAT
"<%s> (unscaled %.15g): not changed (rhs=%.15g)\n",
6108 SCIPdebugMsg(scip,
" -> negative scaled binary variable %+" SCIP_LONGINT_FORMAT
"<%s> (unscaled %.15g): substituted by (1 - <%s>) (rhs=%.15g)\n",
6116 consvals[nconsvars] = val;
6117 consvars[nconsvars] = var;
6125 assert(consvars != NULL);
6126 assert(consvals != NULL);
6135 for( i = 0; i < nconsvars; ++i )
6141 SCIPdebugMsgPrint(scip,
" <= %" SCIP_LONGINT_FORMAT
" (%.15g) [act: %.15g, min: %" SCIP_LONGINT_FORMAT
" max: %" SCIP_LONGINT_FORMAT
"]\n",
6142 capacity, rhs, act, minact, maxact);
6146 if( minact > capacity )
6148 SCIPdebugMsg(scip,
"minactivity of knapsack relaxation implies local cutoff\n");
6153 if( maxact > capacity )
6156 SCIP_CALL(
SCIPseparateKnapsackCuts(scip, cons, sepa, consvars, nconsvars, consvals, capacity, sol, usegubs, cutoff, ncuts) );
6162 if( noknapsackconshdlr)
6169 for( --tmp; tmp >= 0; --tmp)
6171 assert(tmpindices != NULL);
6172 binvals[tmpindices[tmp]] = 0;
6197 assert(ncuts != NULL);
6198 assert(cutoff != NULL);
6202 assert(consdata != NULL);
6218 consdata->capacity, sol, usegubs, cutoff, ncuts) );
6236 assert(consdata != NULL);
6241 if( consdata->row != NULL )
6250 consdata->capacity -= weight;
6261 consdata->vars[consdata->nvars] = var;
6262 consdata->weights[consdata->nvars] = weight;
6277 assert(conshdlrdata != NULL);
6280 conshdlrdata->eventhdlr, consdata->eventdata[consdata->nvars-1],
6281 &consdata->eventdata[consdata->nvars-1]->filterpos) );
6284 consdata->existmultaggr =
TRUE;
6288 consdata->presolvedtiming = 0;
6289 consdata->cliquesadded =
FALSE;
6295 consdata->sorted =
FALSE;
6296 consdata->cliquepartitioned =
FALSE;
6297 consdata->negcliquepartitioned =
FALSE;
6298 consdata->merged =
FALSE;
6316 assert(consdata != NULL);
6317 assert(0 <= pos && pos < consdata->nvars);
6319 var = consdata->vars[pos];
6320 assert(var != NULL);
6324 if( consdata->row != NULL )
6338 assert(conshdlrdata != NULL);
6340 conshdlrdata->eventhdlr, consdata->eventdata[pos], consdata->eventdata[pos]->filterpos) );
6344 consdata->presolvedtiming = 0;
6345 consdata->sorted = (consdata->sorted && pos == consdata->nvars - 1);
6352 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
6353 consdata->weights[pos] = consdata->weights[consdata->nvars-1];
6354 if( consdata->eventdata != NULL )
6355 consdata->eventdata[pos] = consdata->eventdata[consdata->nvars-1];
6361 if( consdata->cliquepartitioned )
6363 assert(consdata->cliquepartition != NULL);
6366 if( consdata->cliquepartition[consdata->nvars - 1] != consdata->nvars - 1 )
6370 oldcliqenum = consdata->cliquepartition[pos];
6371 consdata->cliquepartition[pos] = consdata->cliquepartition[consdata->nvars-1];
6374 if( consdata->cliquepartition[pos] > pos )
6375 consdata->cliquepartitioned =
FALSE;
6379 int cliquenumbefore;
6383 if( oldcliqenum > consdata->cliquepartition[pos] )
6385 for( i = 0; i < consdata->nvars; ++i )
6386 if( oldcliqenum == consdata->cliquepartition[i] )
6388 else if( oldcliqenum < consdata->cliquepartition[i] )
6390 consdata->cliquepartitioned =
FALSE;
6396 if( i == consdata->nvars )
6397 --(consdata->ncliques);
6401 else if( oldcliqenum < consdata->cliquepartition[pos] )
6403 cliquenumbefore = consdata->cliquepartition[pos] - 1;
6404 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->cliquepartition[i] < cliquenumbefore; --i );
6406 if( i < cliquenumbefore )
6407 consdata->cliquepartitioned =
FALSE;
6410 else if( pos == consdata->nvars - 1)
6412 cliquenumbefore = consdata->cliquepartition[pos];
6413 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->cliquepartition[i] < cliquenumbefore; --i );
6415 if( i < cliquenumbefore )
6416 --(consdata->ncliques);
6422 --(consdata->ncliques);
6425 if( consdata->negcliquepartitioned )
6427 assert(consdata->negcliquepartition != NULL);
6430 if( consdata->negcliquepartition[consdata->nvars-1] != consdata->nvars - 1 )
6434 oldcliqenum = consdata->negcliquepartition[pos];
6435 consdata->negcliquepartition[pos] = consdata->negcliquepartition[consdata->nvars-1];
6438 if( consdata->negcliquepartition[pos] > pos )
6439 consdata->negcliquepartitioned =
FALSE;
6443 int cliquenumbefore;
6447 if( oldcliqenum > consdata->negcliquepartition[pos] )
6449 for( i = 0; i < consdata->nvars; ++i )
6450 if( oldcliqenum == consdata->negcliquepartition[i] )
6452 else if( oldcliqenum < consdata->negcliquepartition[i] )
6454 consdata->negcliquepartitioned =
FALSE;
6460 if( i == consdata->nvars )
6461 --(consdata->nnegcliques);
6465 else if( oldcliqenum < consdata->negcliquepartition[pos] )
6467 cliquenumbefore = consdata->negcliquepartition[pos] - 1;
6468 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->negcliquepartition[i] < cliquenumbefore; --i );
6470 if( i < cliquenumbefore )
6471 consdata->negcliquepartitioned =
FALSE;
6474 else if( pos == consdata->nvars - 1)
6476 cliquenumbefore = consdata->negcliquepartition[pos];
6477 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->negcliquepartition[i] < cliquenumbefore; --i );
6479 if( i < cliquenumbefore )
6480 --(consdata->nnegcliques);
6486 --(consdata->nnegcliques);
6489 --(consdata->nvars);
6505 assert(consdata != NULL);
6507 for( v = consdata->nvars-1; v >= 0; --v )
6509 if( consdata->weights[v] == 0 )
6531 assert(scip != NULL);
6532 assert(conshdlr != NULL);
6533 assert(conss != NULL);
6534 assert(nconss >= 0);
6538 for( i = 0; i < nconss; i++ )
6543 if( consdata->varsdeleted )
6546 for( v = consdata->nvars - 1; v >= 0; --v )
6553 consdata->varsdeleted =
FALSE;
6572 assert(scip != NULL);
6573 assert(cons != NULL);
6574 assert(cutoff != NULL);
6577 assert(consdata != NULL);
6581 if( consdata->merged )
6584 if( consdata->nvars <= 1 )
6586 consdata->merged =
TRUE;
6590 assert(consdata->vars != NULL || consdata->nvars == 0);
6594 consdata->cliquepartition, consdata->negcliquepartition, SCIPvarCompActiveAndNegated, consdata->nvars);
6597 consdata->sorted =
FALSE;
6599 v = consdata->nvars - 1;
6612 var1 = consdata->vars[v];
6620 assert(var1 != NULL);
6622 var2 = consdata->vars[prev];
6630 assert(var2 != NULL);
6635 if( negated1 == negated2 )
6638 consdataChgWeight(consdata, prev, consdata->weights[v] + consdata->weights[prev]);
6644 else if( consdata->weights[v] == consdata->weights[prev] )
6647 consdata->capacity -= consdata->weights[v];
6653 else if( consdata->weights[v] < consdata->weights[prev] )
6655 consdata->capacity -= consdata->weights[v];
6656 consdataChgWeight(consdata, prev, consdata->weights[prev] - consdata->weights[v]);
6657 assert(consdata->weights[prev] > 0);
6662 consdata->capacity -= consdata->weights[prev];
6664 assert(consdata->weights[v] > 0);
6667 if( consdata->nvars != v )
6671 if( prev == 0 || (var1 != consdata->vars[prev - 1] && var1 !=
SCIPvarGetNegatedVar(consdata->vars[prev - 1])) )
6675 consdata->cliquesadded =
FALSE;
6682 consdata->cliquesadded =
FALSE;
6688 consdata->merged =
TRUE;
6691 if( consdata->onesweightsum > consdata->capacity )
6693 SCIPdebugMsg(scip,
"merge multiples detected cutoff.\n");
6738 assert(consdata != NULL);
6740 nvars = consdata->nvars;
6741 vars = consdata->vars;
6753 for( v = 0; v <
nvars; ++v )
6759 assert(var != NULL);
6781 SCIPdebugMsg(scip,
"variable <%s> -> item size %" SCIP_LONGINT_FORMAT
", profit <%g>\n",
6795 items, solitems, nonsolitems, &nsolitems, &nnonsolitems, &solval, &success) );
6802 for( v = 0; v < nsolitems; ++v )
6804 var = vars[solitems[v]];
6805 assert(var != NULL);
6807 SCIPdebugMsg(scip,
"variable <%s> only locked up in knapsack constraints: dual presolve <%s>[%.15g,%.15g] >= 1.0\n",
6810 assert(!infeasible);
6815 for( v = 0; v < nnonsolitems; ++v )
6817 var = vars[nonsolitems[v]];
6818 assert(var != NULL);
6820 SCIPdebugMsg(scip,
"variable <%s> has no down locks: dual presolve <%s>[%.15g,%.15g] <= 0.0\n",
6823 assert(!infeasible);
6864 assert(scip != NULL);
6865 assert(cons != NULL);
6866 assert(conshdlrdata != NULL);
6869 assert(consdata != NULL);
6871 nvars = consdata->nvars;
6886 vars = consdata->vars;
6887 assert(vars != NULL);
6893 for( v = 0; v < nvars && applicable; ++v )
6897 assert(var != NULL);
6903 assert(var != NULL);
6915 weight = (
SCIP_Real)consdata->weights[v];
6922 scale = weight / -objval;
6926 else if(
SCIPisEQ(scip, -objval * scale, weight) )
6934 scale = weight / objval;
6936 else if( !
SCIPisEQ(scip, objval * scale, weight) )
6943 if(
SCIPisPositive(scip, scale) && conshdlrdata->detectcutoffbound )
6951 cutoffbound = (consdata->capacity - offset) / scale;
6958 SCIPdebugMsg(scip,
"constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
6963 SCIPdebugMsg(scip,
"update cutoff bound <%g>\n", cutoffbound);
6976 else if(
SCIPisNegative(scip, scale) && conshdlrdata->detectlowerbound )
6984 lowerbound = (consdata->capacity - offset) / scale;
6986 SCIPdebugMsg(scip,
"constraint <%s> is parallel to objective function and provids a lower bound <%g>\n",
7004 int* cliquestartposs,
7011 int* cliquepartition;
7022 assert(scip != NULL);
7023 assert(consdata != NULL);
7024 assert(vars != NULL);
7025 assert(weights != NULL);
7026 assert(cliquestartposs != NULL);
7028 origweights = consdata->weights;
7029 origvars = consdata->vars;
7030 norigvars = consdata->nvars;
7032 assert(origvars != NULL || norigvars == 0);
7033 assert(origweights != NULL || norigvars == 0);
7035 if( norigvars == 0 )
7038 if( usenegatedclique )
7040 assert(consdata->negcliquepartitioned);
7042 cliquepartition = consdata->negcliquepartition;
7043 ncliques = consdata->nnegcliques;
7047 assert(consdata->cliquepartitioned);
7049 cliquepartition = consdata->cliquepartition;
7050 ncliques = consdata->ncliques;
7053 assert(cliquepartition != NULL);
7054 assert(ncliques > 0);
7061 for( v = norigvars - 1; v >= 0; --v )
7063 assert(0 <= cliquepartition[v] && cliquepartition[v] < ncliques);
7064 ++(cliquecount[cliquepartition[v]]);
7078 for( c = 0; c < ncliques; ++c )
7087 varpointers[c] = (
SCIP_VAR**) (vars + nextpos);
7088 cliquestartposs[c] = nextpos;
7089 weightpointers[c] = (
SCIP_Longint*) (weights + nextpos);
7090 assert(cliquecount[c] > 0);
7091 nextpos += cliquecount[c];
7092 assert(nextpos > 0);
7094 assert(nextpos == norigvars);
7095 cliquestartposs[c] = nextpos;
7098 for( v = 0; v < norigvars; ++v )
7100 *(varpointers[cliquepartition[v]]) = origvars[v];
7101 ++(varpointers[cliquepartition[v]]);
7102 *(weightpointers[cliquepartition[v]]) = origweights[v];
7103 ++(weightpointers[cliquepartition[v]]);
7106 for( v = 0; v < norigvars; ++v )
7108 assert(vars[v] != NULL);
7109 assert(weights[v] > 0);
7134 assert(scip != NULL);
7135 assert(cons != NULL);
7138 assert(consdata != NULL);
7139 assert(consdata->nvars == 0 || consdata->vars != NULL);
7141 if( cutoff != NULL )
7148 if ( consdata->onesweightsum > consdata->capacity )
7150 SCIPdebugMsg(scip,
"apply fixings detected cutoff.\n");
7152 if( cutoff != NULL )
7159 consdata->existmultaggr =
FALSE;
7162 while( v < consdata->nvars )
7166 var = consdata->vars[v];
7172 consdata->capacity -= consdata->weights[v];
7174 consdata->cliquesadded =
FALSE;
7189 weight = consdata->weights[v];
7193 assert(repvar != NULL);
7199 assert(workvar != NULL);
7242 assert((aggrvars != NULL && aggrscalars != NULL) || naggrvars == 0);
7246 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-integral value for weight*aggrconst = %g\n", weight*aggrconst);
7254 for( i = naggrvars - 1; i >= 0; --i )
7256 assert(aggrvars != NULL);
7257 assert(aggrscalars != NULL);
7261 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-binary variable <%s>\n", aggrvars[i]);
7266 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-integral value for weight*aggrscalars = %g\n", weight*aggrscalars[i]);
7273 assert(negvar != NULL);
7291 if( consdata->capacity < 0 )
7293 if( cutoff != NULL )
7301 else if( repvar != var )
7313 assert(consdata->onesweightsum == 0);
7315 SCIPdebugMsg(scip,
"after applyFixings, before merging:\n");
7321 if( cutoff != NULL && !(*cutoff) )
7324 SCIPdebugMsg(scip,
"after applyFixings and merging:\n");
7356 int* cliquestartposs;
7362 assert(scip != NULL);
7363 assert(cons != NULL);
7364 assert(cutoff != NULL);
7365 assert(redundant != NULL);
7366 assert(nfixedvars != NULL);
7369 assert(consdata != NULL);
7384 for( i = 0; i < consdata->nvars && consdata->merged; ++i )
7390 usenegatedclique = usenegatedclique && consdata->merged;
7395 cliquestartposs = NULL;
7396 secondmaxweights = NULL;
7398 nvars = consdata->nvars;
7404 localminweightsum = 0;
7413 if( usenegatedclique && nvars > 0 )
7417 assert(conshdlrdata != NULL);
7421 nnegcliques = consdata->nnegcliques;
7424 if( nnegcliques == nvars )
7427 usenegatedclique =
FALSE;
7443 for( c = 0; c < nnegcliques; ++c )
7445 cliqueendposs[c] = cliquestartposs[c+1] - 1;
7446 assert(cliqueendposs[c] - cliquestartposs[c] >= 0);
7460 if( nnegcliques - c == nvars - i )
7462 minweightsum += localminweightsum;
7463 localminweightsum = 0;
7471 if( cliquestartposs[c] == i )
7473 assert(myweights[i] > 0);
7475 minweightsum += localminweightsum;
7476 localminweightsum = 0;
7491 assert(myweights[i] > 0);
7495 assert(myweights[i] <= myweights[cliquestartposs[c - 1]]);
7502 cliquestartposs[c - 1] = i;
7508 if( secondmaxweights[c - 1] == 0 )
7509 secondmaxweights[c - 1] = myweights[i];
7511 localminweightsum += myweights[i];
7518 for( v = cliquestartposs[c - 1]; v < cliquestartposs[c]; ++v )
7557 localminweightsum = 0;
7559 i = cliqueendposs[c - 1];
7565 minweightsum += localminweightsum;
7567 SCIPdebugMsg(scip,
"knapsack constraint <%s> has minimum weight sum of <%" SCIP_LONGINT_FORMAT
">\n",
7571 if( !(*cutoff) && consdata->capacity >= minweightsum + consdata->onesweightsum )
7576 for( c = 0; c < nnegcliques; ++c )
7580 int endvarposclique;
7581 int startvarposclique;
7583 assert(myvars != NULL);
7584 assert(nnegcliques == consdata->nnegcliques);
7585 assert(myweights != NULL);
7586 assert(secondmaxweights != NULL);
7587 assert(cliquestartposs != NULL);
7589 endvarposclique = cliqueendposs[c];
7590 startvarposclique = cliquestartposs[c];
7592 maxvar = myvars[startvarposclique];
7598 maxcliqueweight = myweights[startvarposclique];
7599 maxvarfixed =
FALSE;
7604 if( consdata->onesweightsum + minweightsum + (maxcliqueweight - secondmaxweights[c]) > consdata->capacity )
7606 assert(maxcliqueweight >= secondmaxweights[c]);
7612 assert(!infeasible);
7620 else if( nnegcliques - c == nvars - startvarposclique )
7630 else if( consdata->onesweightsum + minweightsum + (maxcliqueweight - consdata->weights[nvars - 1]) <= consdata->capacity )
7634 for( i = endvarposclique; i > startvarposclique; --i )
7643 assert(maxcliqueweight >= myweights[i]);
7644 assert(i == endvarposclique || myweights[i] >= myweights[i+1]);
7652 if( maxvarfixed || consdata->onesweightsum + minweightsum - myweights[i] + maxcliqueweight > consdata->capacity )
7656 assert(!infeasible);
7664 minweightsum -= myweights[i];
7665 assert(minweightsum >= 0);
7673 for( ; i > startvarposclique; --i )
7676 SCIP_Bool exceedscapacity = consdata->onesweightsum + minweightsum - myweights[i] + maxcliqueweight > consdata->capacity;
7678 assert(i == endvarposclique || myweights[i] >= myweights[i+1]);
7679 assert(varisfixed || !exceedscapacity);
7691 assert(consdata->negcliquepartitioned || minweightsum == 0);
7695 assert(usenegatedclique || minweightsum == 0);
7697 if( consdata->capacity < minweightsum + consdata->onesweightsum )
7699 SCIPdebugMsg(scip,
" -> cutoff - fixed weight: %" SCIP_LONGINT_FORMAT
", capacity: %" SCIP_LONGINT_FORMAT
" \n",
7700 consdata->onesweightsum, consdata->capacity);
7715 for( i = 0; i < nvars && weight <= consdata->capacity; i++ )
7720 weight += consdata->weights[i];
7731 if( !usenegatedclique )
7733 assert(consdata->sorted);
7734 residualcapacity = consdata->capacity - consdata->onesweightsum;
7737 for( i = 0; i < nvars && consdata->weights[i] > residualcapacity; ++i )
7746 assert(consdata->onesweightsum + consdata->weights[i] > consdata->capacity);
7750 assert(!infeasible);
7761 SCIP_Longint unfixedweightsum = consdata->onesweightsum;
7764 for( i = 0; i <
nvars; ++i )
7768 unfixedweightsum += consdata->weights[i];
7771 if( unfixedweightsum > consdata->capacity )
7776 SCIPdebugMsg(scip,
" -> knapsack constraint <%s> is redundant: weightsum=%" SCIP_LONGINT_FORMAT
", unfixedweightsum=%" SCIP_LONGINT_FORMAT
", capacity=%" SCIP_LONGINT_FORMAT
"\n",
7777 SCIPconsGetName(cons), consdata->weightsum, unfixedweightsum, consdata->capacity);
7799 assert(scip != NULL);
7800 assert(cons != NULL);
7801 assert(ndelconss != NULL);
7802 assert(naddconss != NULL);
7805 assert(consdata != NULL);
7806 assert(consdata->nvars > 1);
7809 if( consdata->nvars == 2 )
7881 assert(scip != NULL);
7882 assert(cons != NULL);
7883 assert(nchgcoefs != NULL);
7884 assert(nchgsides != NULL);
7885 assert(naddconss != NULL);
7888 assert(consdata != NULL);
7889 assert(0 < frontsum && frontsum < consdata->weightsum);
7890 assert(0 < splitpos && splitpos < consdata->nvars);
7893 assert(conshdlrdata != NULL);
7895 vars = consdata->vars;
7896 weights = consdata->weights;
7897 nvars = consdata->nvars;
7898 capacity = consdata->capacity;
7904 for( w = nvars - 1; w > 0; --w )
7905 assert(weights[w] <= weights[w-1]);
7909 if( consdata->nvars - 1 == splitpos )
7912 assert(frontsum + weights[splitpos] > capacity);
7915 if( consdata->weightsum - weights[splitpos] <= capacity )
7923 for( w = nvars - 1; w > splitpos; --w )
7925 consdata->capacity -= weights[w];
7928 assert(w == splitpos);
7931 *nchgcoefs += (nvars - splitpos);
7935 for( ; w >= 0 && gcd > 1; --w )
7943 for( w = splitpos; w >= 0; --w )
7947 (*nchgcoefs) +=
nvars;
7949 consdata->capacity /= gcd;
7957 for( w = consdata->nvars - 1; w > 0; --w )
7958 assert(weights[w] <= weights[w - 1]);
7965 else if( conshdlrdata->disaggregation && frontsum + weights[splitpos + 1] <= capacity )
7971 len = nvars - (splitpos + 1);
7988 for( w = 0; w < len; ++w )
7990 assert(clqpart[w] >= 0 && clqpart[w] <= w);
7991 if( clqpart[w] == cliquenum )
7993 maxactduetoclq += weights[w + splitpos + 1];
8001 if( frontsum + maxactduetoclq <= capacity )
8007 assert(maxactduetoclq < weights[splitpos]);
8014 for( c = 0; c < nclq; ++c )
8017 for( w = 0; w < len; ++w )
8019 if( clqpart[w] == c )
8021 clqvars[nclqvars] = vars[w + splitpos + 1];
8047 for( w = nvars - 1; w > splitpos; --w )
8052 consdata->capacity -= maxactduetoclq;
8053 assert(frontsum <= consdata->capacity);
8056 assert(w == splitpos);
8059 weights = consdata->weights;
8063 for( ; w >= 0 && gcd > 1; --w )
8071 for( w = splitpos; w >= 0; --w )
8075 (*nchgcoefs) +=
nvars;
8077 consdata->capacity /= gcd;
8088 for( w = consdata->nvars - 1; w > 0; --w )
8089 assert(weights[w] <= weights[w - 1]);
8132 assert(scip != NULL);
8133 assert(cons != NULL);
8134 assert(ndelconss != NULL);
8135 assert(nchgcoefs != NULL);
8136 assert(nchgsides != NULL);
8137 assert(naddconss != NULL);
8140 assert(consdata != NULL);
8141 assert(consdata->nvars >= 2);
8142 assert(consdata->weightsum > consdata->capacity);
8144 noldchgcoefs = *nchgcoefs;
8145 vars = consdata->vars;
8146 weights = consdata->weights;
8147 nvars = consdata->nvars;
8148 capacity = consdata->capacity;
8152 for( v = 0; v < nvars && sum + weights[v] <= capacity; ++v )
8158 if( v == nvars - 1 )
8170 assert(consdata->nvars > 1);
8173 if( v == consdata->nvars - 1 )
8183 if( *nchgcoefs > noldchgcoefs )
8186 assert(vars == consdata->vars);
8187 assert(weights == consdata->weights);
8188 assert(nvars == consdata->nvars);
8189 assert(capacity == consdata->capacity);
8192 assert(conshdlrdata != NULL);
8197 if( consdata->cliquepartition[v] < v )
8206 maxactduetoclqfront = 0;
8208 clqpart = consdata->cliquepartition;
8212 for( w = 0; w <
nvars; ++w )
8214 assert(clqpart[w] >= 0 && clqpart[w] <= w);
8215 if( clqpart[w] == cliquenum )
8217 if( maxactduetoclqfront + weights[w] <= capacity )
8219 maxactduetoclqfront += weights[w];
8225 sumfront += weights[w];
8232 if( conshdlrdata->disaggregation && w == nvars )
8239 assert(maxactduetoclqfront <= capacity);
8243 ncliques = consdata->ncliques;
8248 for( c = 0; c < ncliques; ++c )
8251 for( w = 0; w <
nvars; ++w )
8253 if( clqpart[w] == c )
8255 clqvars[nclqvars] = vars[w];
8289 if( w > v && w < nvars - 1 )
8311 assert(nchgcoefs != NULL);
8312 assert(nchgsides != NULL);
8316 assert(consdata != NULL);
8317 assert(consdata->row == NULL);
8318 assert(consdata->onesweightsum == 0);
8319 assert(consdata->weightsum > consdata->capacity);
8320 assert(consdata->nvars >= 1);
8325 gcd = consdata->weights[consdata->nvars-1];
8326 for( i = consdata->nvars-2; i >= 0 && gcd >= 2; --i )
8338 for( i = 0; i < consdata->nvars; ++i )
8342 consdata->capacity /= gcd;
8343 (*nchgcoefs) += consdata->nvars;
8348 for( i = consdata->nvars - 1; i > 0; --i )
8349 assert(consdata->weights[i] <= consdata->weights[i - 1]);
8351 consdata->sorted =
TRUE;
8399 assert(scip != NULL);
8400 assert(cons != NULL);
8401 assert(ndelconss != NULL);
8402 assert(nchgcoefs != NULL);
8403 assert(nchgsides != NULL);
8404 assert(naddconss != NULL);
8407 oldnchgsides = *nchgsides;
8411 assert(consdata != NULL);
8412 assert(consdata->weightsum > consdata->capacity);
8413 assert(consdata->nvars >= 2);
8414 assert(consdata->sorted);
8417 assert(consdata->merged);
8419 nvars = consdata->nvars;
8420 weights = consdata->weights;
8421 capacity = consdata->capacity;
8423 oldnchgcoefs = *nchgcoefs;
8426 if( weights[nvars - 1] + weights[nvars - 2] > capacity )
8453 if( consdata->weightsum - weights[nvars - 1] <= consdata->capacity )
8463 if( consdata->weightsum - capacity > weights[0] + weights[1] )
8484 while( v < nvars && weights[v] + weights[nvars - 1] > capacity )
8488 assert(vbig < nvars - 1);
8492 while( v < nvars && exceedsum <= capacity )
8494 exceedsum += weights[v];
8499 if( exceedsum > capacity )
8501 assert(vbig > 0 || v < nvars);
8507 assert(newweight > 0);
8510 for( v = 0; v < vbig; ++v )
8512 if( weights[v] > newweight )
8520 for( ; v <
nvars; ++v )
8522 if( weights[v] > 1 )
8529 consdata->capacity = newweight;
8535 for( v = nvars - 1; v > 0; --v )
8536 assert(weights[v] <= weights[v-1]);
8547 int nexceed = v - vbig;
8549 assert(nexceed > 1);
8552 for( w = nvars - 1; w >= nvars - nexceed; --w )
8553 exceedsumback += weights[w];
8560 if( exceedsumback > capacity )
8565 assert(exceedsumback - weights[nvars - 1] <= 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 assert(vbig > 0 && vbig < nvars);
8617 if( weights[vbig - 1] > (
SCIP_Longint)nvars - vbig || weights[vbig] > 1 )
8623 for( v = 0; v < vbig; ++v )
8624 resweightsum -= weights[v];
8626 assert(exceedsum == resweightsum);
8628 assert(newweight > 0);
8631 for( v = 0; v < vbig; ++v )
8633 if( weights[v] > newweight )
8641 for( ; v <
nvars; ++v )
8643 if( weights[v] > 1 )
8650 consdata->capacity = newweight;
8656 for( v = nvars - 1; v > 0; --v )
8657 assert(weights[v] <= weights[v-1]);
8665 dualcapacity = consdata->weightsum - capacity;
8675 while( weights[v] > dualcapacity )
8677 reductionsum += (weights[v] - dualcapacity);
8685 while( v < nvars && weights[v] == dualcapacity )
8693 if( v >= nvars - 1 )
8696 if( v == nvars - 1 )
8709 if( weights[nvars - 1] + weights[nvars - 2] >= dualcapacity )
8723 if( v > 0 && weights[nvars - 2] > 1 )
8728 for( w = 0; w < v; ++w )
8730 if( weights[w] > 2 )
8737 assert(weights[0] == 2);
8738 assert(weights[v - 1] == 2);
8744 for( w = v; w <
nvars; ++w )
8746 if( weights[w] > 1 )
8752 assert(ncoefchg > 0);
8754 (*nchgcoefs) += ncoefchg;
8757 consdata->capacity = (-2 + v * 2 + nvars - v);
8758 assert(consdata->capacity > 0);
8759 assert(weights[0] <= consdata->capacity);
8760 assert(consdata->weightsum > consdata->capacity);
8766 assert(weights[nvars - 2] == 1);
8780 assert(weights[nvars - 1] + weights[nvars - 2] <= capacity);
8788 while( weights[v] > newweight )
8790 reductionsum += (weights[v] - newweight);
8795 (*nchgcoefs) += (v - startv);
8798 while( weights[v] == newweight )
8803 for( w = v; w <
nvars; ++w )
8804 restsumweights += weights[w];
8807 restsumweights = consdata->weightsum;
8809 if( restsumweights < dualcapacity )
8819 for( w = nvars - 1; w >= v; --w )
8827 for( ; w >= 0; --w )
8828 assert(weights[w] == dualcapacity);
8846 if( weights[v] > 1 || (weights[startv] > (
SCIP_Longint)nvars - v) || (startv > 0 && weights[0] == (
SCIP_Longint)nvars - v + 1) )
8851 for( w = nvars - 1; w >= v; --w )
8853 if( weights[w] > 1 )
8864 assert(newweight > 1);
8865 for( ; w >= startv; --w )
8867 if( weights[w] > newweight )
8873 assert(weights[w] == newweight);
8878 assert(newweight > 2);
8879 for( ; w >= 0; --w )
8881 if( weights[w] > newweight )
8887 assert(weights[w] == newweight);
8892 if( consdata->capacity > newcap )
8894 consdata->capacity = newcap;
8898 assert(consdata->capacity == newcap);
8900 assert(weights[v] == 1 && (weights[startv] == (
SCIP_Longint)nvars - v) && (startv == 0 || weights[0] == (
SCIP_Longint)nvars - v + 1));
8903 assert(consdata->weightsum - consdata->capacity == (
SCIP_Longint)nvars - v + 1);
8909 for( w = nvars - 1; w > 0; --w )
8910 assert(weights[w] <= weights[w - 1]);
8917 while( end >= 0 && weights[end] == weights[end + 1] )
8929 if( 2 * weights[end] > dualcapacity )
8934 for( w = end + 1; w <
nvars; ++w )
8935 restsumweights += weights[w];
8937 if( restsumweights * 2 <= dualcapacity )
8940 while( v < end && restsumweights + weights[v] >= dualcapacity )
8947 if( (dualcapacity & 1) == 0 )
8949 newweight = dualcapacity / 2;
8952 for( ; v <= end; ++v )
8954 if( weights[v] > newweight )
8956 reductionsum += (weights[v] - newweight);
8971 for( w = 0; w < v; ++w )
8976 newweight = dualcapacity;
8978 for( ; v <= end; ++v )
8980 reductionsum += (2 * weights[v] - newweight);
8985 for( w = end + 1; w <
nvars; ++w )
8989 (*nchgcoefs) +=
nvars;
8992 consdata->capacity *= 2;
9007 for( k = 0; k < 4; ++k )
9013 sumcoef = weights[nvars - 1] + weights[nvars - 2];
9017 sumcoef = weights[nvars - 1] + weights[nvars - 3];
9021 if( weights[nvars - 1] + weights[nvars - 4] < weights[nvars - 2] + weights[nvars - 3] )
9024 sumcoef = weights[nvars - 1] + weights[nvars - 4];
9028 sumcoefcase =
FALSE;
9029 sumcoef = weights[nvars - 2] + weights[nvars - 3];
9036 sumcoef = MIN(weights[nvars - 1] + weights[nvars - 5], weights[nvars - 2] + weights[nvars - 3]);
9040 sumcoef = MIN(weights[nvars - 1] + weights[nvars - 4], weights[nvars - 1] + weights[nvars - 2] + weights[nvars - 3]);
9048 minweight = weights[end];
9049 while( minweight <= sumcoef )
9051 newweight = dualcapacity - minweight;
9057 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9059 reductionsum += (weights[v] - newweight);
9064 (*nchgcoefs) += (v - startv);
9067 while( weights[v] + minweight == dualcapacity )
9075 while( end >= 0 && weights[end] == weights[end + 1] )
9081 minweight = weights[end];
9088 if( sumcoef < minweight )
9090 minweight = sumcoef;
9091 newweight = dualcapacity - minweight;
9096 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9098 reductionsum += (weights[v] - newweight);
9103 (*nchgcoefs) += (v - startv);
9106 while( weights[v] + minweight == dualcapacity )
9117 if( 2 * weights[end] > dualcapacity )
9122 for( w = end + 1; w <
nvars; ++w )
9123 restsumweights += weights[w];
9125 if( restsumweights * 2 <= dualcapacity )
9128 while( v < end && restsumweights + weights[v] >= dualcapacity )
9135 if( (dualcapacity & 1) == 0 )
9137 newweight = dualcapacity / 2;
9140 for( ; v <= end; ++v )
9142 if( weights[v] > newweight )
9144 reductionsum += (weights[v] - newweight);
9159 for( w = 0; w < v; ++w )
9164 newweight = dualcapacity;
9166 for( ; v <= end; ++v )
9168 reductionsum += (2 * weights[v] - newweight);
9173 for( w = end + 1; w <
nvars; ++w )
9177 (*nchgcoefs) +=
nvars;
9180 consdata->capacity *= 2;
9189 if( 2 * sumcoef > dualcapacity )
9198 if( reductionsum > 0 )
9202 consdata->capacity -= reductionsum;
9205 assert(consdata->weightsum - dualcapacity == consdata->capacity);
9207 assert(weights[0] <= consdata->capacity);
9213 for( w = nvars - 1; w > 0; --w )
9214 assert(weights[w] <= weights[w - 1]);
9217 if( oldnchgcoefs < *nchgcoefs )
9226 assert(oldnchgcoefs == *nchgcoefs);
9227 assert(oldnchgsides == *nchgsides);
9253 assert(scip != NULL);
9254 assert(cons != NULL);
9255 assert(nfixedvars != NULL);
9256 assert(ndelconss != NULL);
9257 assert(nchgcoefs != NULL);
9260 assert(consdata != NULL);
9262 nvars = consdata->nvars;
9267 assert(consdata->capacity >= 0);
9278 vars = consdata->vars;
9279 weights = consdata->weights;
9280 capacity = consdata->capacity;
9284 while( v < nvars && weights[v] > capacity )
9287 assert(!infeasible);
9307 for( --v; v >= 0; --v )
9315 assert(vars == consdata->vars);
9316 assert(weights == consdata->weights);
9318 assert(consdata->sorted);
9319 assert(weights[0] <= capacity);
9381 assert(scip != NULL);
9382 assert(cons != NULL);
9383 assert(nfixedvars != NULL);
9384 assert(ndelconss != NULL);
9385 assert(nchgcoefs != NULL);
9386 assert(nchgsides != NULL);
9387 assert(naddconss != NULL);
9388 assert(cutoff != NULL);
9392 assert( consdata != NULL );
9398 assert(consdata->merged);
9402 assert(consdata->capacity >= 0);
9424 weights = consdata->weights;
9425 nvars = consdata->nvars;
9429 for( v = nvars - 1; v > 0; --v )
9430 assert(weights[v] <= weights[v-1]);
9434 gcd = weights[nvars - 1];
9435 for( v = nvars - 2; v >= 0 && gcd > 1; --v )
9443 for( v = nvars - 1; v >= 0; --v )
9447 (*nchgcoefs) +=
nvars;
9449 consdata->capacity /= gcd;
9452 assert(consdata->nvars == nvars);
9458 for( v = nvars - 1; v > 0; --v )
9459 assert(weights[v] <= weights[v-1]);
9468 vars = consdata->vars;
9469 weights = consdata->weights;
9470 nvars = consdata->nvars;
9473 if( weights[nvars - 1] == 1 && weights[nvars - 2] == 1 )
9480 while( weights[v] == consdata->capacity )
9487 if( v == nvars - 1 )
9499 for( v = nvars - 1; v >= offsetv; --v )
9501 weight = weights[v];
9502 assert(weight >= 1);
9529 if( v == nvars - 2 )
9535 if( candpos == v + 1 && candpos2 == v + 2 )
9537 assert(candpos2 == nvars - 1);
9562 assert(((candpos >= offsetv) || (candpos == -1 && offsetv > 0)) && candpos < nvars);
9565 rest = consdata->capacity % gcd;
9575 consdata->capacity -= rest;
9579 for( v = 0; v < offsetv; ++v )
9584 *nchgcoefs += offsetv;
9589 restweight = weights[candpos] % gcd;
9590 assert(restweight >= 1);
9591 assert(restweight < gcd);
9594 if( restweight > rest )
9595 newweight = weights[candpos] - restweight + gcd;
9597 newweight = weights[candpos] - restweight;
9601 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);
9606 if( newweight == 0 && offsetv > 0 )
9612 consdata->capacity -= rest;
9616 for( v = 0; v < offsetv; ++v )
9621 *nchgcoefs += offsetv;
9624 if( newweight == 0 )
9628 assert(consdata->nvars == nvars - 1);
9638 assert(consdata->vars == vars);
9639 assert(consdata->nvars == nvars);
9640 assert(consdata->weights == weights);
9644 for( v = nvars - 1; v >= 0; --v )
9648 (*nchgcoefs) +=
nvars;
9650 consdata->capacity /= gcd;
9655 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));
9657 while( nvars >= 2 );
9684 assert(liftcands != NULL);
9685 assert(liftcands[value] != NULL);
9686 assert(nliftcands != NULL);
9687 assert(firstidxs != NULL);
9688 assert(firstidxs[value] != NULL);
9689 assert(zeroweightsums != NULL);
9690 assert(zeroweightsums[value] != NULL);
9691 assert(zeroitems != NULL);
9692 assert(nextidxs != NULL);
9693 assert(zeroitemssize != NULL);
9694 assert(nzeroitems != NULL);
9695 assert(*nzeroitems <= *zeroitemssize);
9697 assert(memlimitreached != NULL);
9699 nzeros = *nzeroitems;
9702 if( nzeros == *zeroitemssize )
9709 SCIPdebugMsg(scip,
"memory limit of %d bytes reached in knapsack preprocessing - abort collecting zero items\n",
9711 *memlimitreached =
TRUE;
9714 *zeroitemssize *= 2;
9719 assert(nzeros < *zeroitemssize);
9721 if( *memlimitreached )
9722 *memlimitreached =
FALSE;
9725 (*zeroitems)[nzeros] = knapsackidx;
9726 (*nextidxs)[nzeros] = firstidxs[value][probindex];
9727 if( firstidxs[value][probindex] == 0 )
9729 liftcands[value][nliftcands[value]] = probindex;
9730 ++nliftcands[value];
9732 firstidxs[value][probindex] = nzeros;
9734 zeroweightsums[value][probindex] += knapsackweight;
9739 #define MAX_CLIQUELENGTH 50 9795 assert(nchgcoefs != NULL);
9799 assert(consdata != NULL);
9800 assert(consdata->row == NULL);
9801 assert(consdata->weightsum > consdata->capacity);
9802 assert(consdata->nvars > 0);
9803 assert(consdata->merged);
9805 nvars = consdata->nvars;
9819 assert(nbinvars > 0);
9824 assert(conshdlr != NULL);
9826 assert(conshdlrdata != NULL);
9833 assert(conshdlrdata->ints1size > 0);
9834 assert(conshdlrdata->ints2size > 0);
9835 assert(conshdlrdata->longints1size > 0);
9836 assert(conshdlrdata->longints2size > 0);
9842 if( conshdlrdata->ints1size < nbinvars )
9844 int oldsize = conshdlrdata->ints1size;
9846 conshdlrdata->ints1size = nbinvars;
9850 if( conshdlrdata->ints2size < nbinvars )
9852 int oldsize = conshdlrdata->ints2size;
9854 conshdlrdata->ints2size = nbinvars;
9858 if( conshdlrdata->longints1size < nbinvars )
9860 int oldsize = conshdlrdata->longints1size;
9862 conshdlrdata->longints1size = nbinvars;
9864 BMSclearMemoryArray(&(conshdlrdata->longints1[oldsize]), conshdlrdata->longints1size - oldsize);
9866 if( conshdlrdata->longints2size < nbinvars )
9868 int oldsize = conshdlrdata->longints2size;
9870 conshdlrdata->longints2size = nbinvars;
9872 BMSclearMemoryArray(&(conshdlrdata->longints2[oldsize]), conshdlrdata->longints2size - oldsize);
9875 firstidxs[0] = conshdlrdata->ints1;
9876 firstidxs[1] = conshdlrdata->ints2;
9877 zeroweightsums[0] = conshdlrdata->longints1;
9878 zeroweightsums[1] = conshdlrdata->longints2;
9882 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
9884 assert(firstidxs[0][tmp] == 0);
9885 assert(firstidxs[1][tmp] == 0);
9886 assert(zeroweightsums[0][tmp] == 0);
9887 assert(zeroweightsums[1][tmp] == 0);
9900 assert(conshdlrdata->bools1size > 0);
9901 assert(conshdlrdata->bools2size > 0);
9907 if( conshdlrdata->bools1size < nbinvars )
9909 int oldsize = conshdlrdata->bools1size;
9911 conshdlrdata->bools1size = nbinvars;
9913 BMSclearMemoryArray(&(conshdlrdata->bools1[oldsize]), conshdlrdata->bools1size - oldsize);
9915 if( conshdlrdata->bools2size < nbinvars )
9917 int oldsize = conshdlrdata->bools2size;
9919 conshdlrdata->bools2size = nbinvars;
9921 BMSclearMemoryArray(&(conshdlrdata->bools2[oldsize]), conshdlrdata->bools2size - oldsize);
9924 zeroiteminserted[0] = conshdlrdata->bools1;
9925 zeroiteminserted[1] = conshdlrdata->bools2;
9929 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
9931 assert(zeroiteminserted[0][tmp] == 0);
9932 assert(zeroiteminserted[1][tmp] == 0);
9945 memlimitreached =
FALSE;
9946 for( i = 0; i < consdata->nvars && !memlimitreached; ++i )
9959 var = consdata->vars[i];
9960 weight = consdata->weights[i];
9964 assert(0 <= varprobindex && varprobindex < nbinvars);
9967 zeroweightsums[!value][varprobindex] += weight;
9968 tmpboolindices3[tmp3] = !value;
9969 tmpindices3[tmp3] = varprobindex;
9979 assert(0 <= probindex && probindex < nbinvars);
9984 assert( !zeroiteminserted[implvalue][probindex] );
9986 if( firstidxs[implvalue][probindex] == 0 )
9988 tmpboolindices2[tmp2] = implvalue;
9989 tmpindices2[tmp2] = probindex;
9993 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue, i, weight,
9994 &memlimitreached) );
9995 zeroiteminserted[implvalue][probindex] =
TRUE;
9996 tmpboolindices[tmp] = implvalue;
9997 tmpindices[tmp] = probindex;
10004 for( j = 0; j < ncliques && !memlimitreached; ++j )
10020 for( k = ncliquevars - 1; k >= 0; --k )
10025 if( var == cliquevars[k] )
10029 if( probindex == -1 )
10032 assert(0 <= probindex && probindex < nbinvars);
10033 implvalue = cliquevalues[k];
10036 if( !zeroiteminserted[implvalue][probindex] )
10038 if( firstidxs[implvalue][probindex] == 0 )
10040 tmpboolindices2[tmp2] = implvalue;
10041 tmpindices2[tmp2] = probindex;
10046 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue, i, weight,
10047 &memlimitreached) );
10048 zeroiteminserted[implvalue][probindex] =
TRUE;
10049 tmpboolindices[tmp] = implvalue;
10050 tmpindices[tmp] = probindex;
10053 if( memlimitreached )
10059 for( --tmp; tmp >= 0; --tmp)
10060 zeroiteminserted[tmpboolindices[tmp]][tmpindices[tmp]] =
FALSE;
10065 assert(consdata->sorted);
10068 assert(conshdlrdata->bools3size > 0);
10074 if( conshdlrdata->bools3size < consdata->nvars )
10076 int oldsize = conshdlrdata->bools3size;
10078 conshdlrdata->bools3size = consdata->nvars;;
10080 BMSclearMemoryArray(&(conshdlrdata->bools3[oldsize]), conshdlrdata->bools3size - oldsize);
10083 cliqueused = conshdlrdata->bools3;
10087 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10088 assert(cliqueused[tmp] == 0);
10091 maxcliqueweightsum = 0;
10095 for( i = 0; i < consdata->nvars; ++i )
10097 cliquenum = consdata->cliquepartition[i];
10098 assert(0 <= cliquenum && cliquenum < consdata->nvars);
10100 if( !cliqueused[cliquenum] )
10102 maxcliqueweightsum += consdata->weights[i];
10103 cliqueused[cliquenum] =
TRUE;
10104 tmpindices[tmp] = cliquenum;
10109 for( --tmp; tmp >= 0; --tmp)
10110 cliqueused[tmp] =
FALSE;
10112 assert(conshdlrdata->bools4size > 0);
10118 if( conshdlrdata->bools4size < consdata->nvars )
10120 int oldsize = conshdlrdata->bools4size;
10122 conshdlrdata->bools4size = consdata->nvars;
10127 itemremoved = conshdlrdata->bools4;
10131 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10132 assert(itemremoved[tmp] == 0);
10143 for( val = 0; val < 2 && addweightsum < consdata->capacity; ++val )
10145 for( i = 0; i < nliftcands[val] && addweightsum < consdata->capacity; ++i )
10154 probindex = liftcands[val][i];
10155 assert(0 <= probindex && probindex < nbinvars);
10158 if( firstidxs[val][probindex] == 0
10159 || maxcliqueweightsum - zeroweightsums[val][probindex] + addweightsum >= consdata->capacity )
10163 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10165 assert(0 < idx && idx < nzeroitems);
10166 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10167 itemremoved[zeroitems[idx]] =
TRUE;
10171 cliqueweightsum = addweightsum;
10172 for( j = 0; j < consdata->nvars; ++j )
10174 cliquenum = consdata->cliquepartition[j];
10175 assert(0 <= cliquenum && cliquenum < consdata->nvars);
10176 if( !itemremoved[j] )
10178 if( !cliqueused[cliquenum] )
10180 cliqueweightsum += consdata->weights[j];
10181 cliqueused[cliquenum] =
TRUE;
10182 tmpindices[tmp] = cliquenum;
10186 if( cliqueweightsum >= consdata->capacity )
10192 if( cliqueweightsum < consdata->capacity )
10198 assert(naddvars < 2*nbinvars);
10199 var = binvars[probindex];
10204 weight = consdata->capacity - cliqueweightsum;
10205 addvars[naddvars] = var;
10206 addweights[naddvars] = weight;
10207 addweightsum += weight;
10210 SCIPdebugMsg(scip,
"knapsack constraint <%s>: adding lifted item %" SCIP_LONGINT_FORMAT
"<%s>\n",
10215 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10217 assert(0 < idx && idx < nzeroitems);
10218 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10219 itemremoved[zeroitems[idx]] =
FALSE;
10222 for( --tmp; tmp >= 0; --tmp)
10223 cliqueused[tmpindices[tmp]] =
FALSE;
10229 for( --tmp3; tmp3 >= 0; --tmp3)
10230 zeroweightsums[tmpboolindices3[tmp3]][tmpindices3[tmp3]] = 0;
10233 for( --tmp2; tmp2 >= 0; --tmp2)
10235 zeroweightsums[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10236 firstidxs[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10245 for( i = 0; i < naddvars; ++i )
10249 *nchgcoefs += naddvars;
10342 assert(nchgcoefs != NULL);
10343 assert(nchgsides != NULL);
10347 assert(conshdlrdata != NULL);
10350 assert(consdata != NULL);
10351 assert(consdata->row == NULL);
10352 assert(consdata->onesweightsum == 0);
10353 assert(consdata->weightsum > consdata->capacity);
10354 assert(consdata->nvars > 0);
10365 assert(consdata->merged);
10370 for( i = 0; i < consdata->nvars; ++i )
10374 weight = consdata->weights[i];
10375 if( consdata->weightsum - weight < consdata->capacity )
10377 newweight = consdata->weightsum - consdata->capacity;
10379 consdata->capacity -= (weight - newweight);
10382 assert(!consdata->sorted);
10383 SCIPdebugMsg(scip,
"knapsack constraint <%s>: changed weight of <%s> from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
", capacity from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10385 consdata->capacity + (weight-newweight), consdata->capacity);
10391 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10395 if( consdata->weightsum <= consdata->capacity )
10399 while( pos < consdata->nvars && consdata->weights[pos] == consdata->capacity )
10403 weights = consdata->weights;
10404 nvars = consdata->nvars;
10405 capacity = consdata->capacity;
10408 pos < nvars && weights[pos] + weights[pos + 1] > capacity )
10415 for( k = 0; k < 4; ++k )
10417 newweight = capacity - sumcoef;
10423 sumcoef = weights[nvars - 1];
10424 backpos = nvars - 1;
10427 sumcoef = weights[nvars - 2];
10428 backpos = nvars - 2;
10431 if( weights[nvars - 3] < weights[nvars - 1] + weights[nvars - 2] )
10433 sumcoefcase =
TRUE;
10434 sumcoef = weights[nvars - 3];
10435 backpos = nvars - 3;
10439 sumcoefcase =
FALSE;
10440 sumcoef = weights[nvars - 1] + weights[nvars - 2];
10441 backpos = nvars - 2;
10448 if( weights[nvars - 4] < weights[nvars - 1] + weights[nvars - 2] )
10450 sumcoef = weights[nvars - 4];
10451 backpos = nvars - 4;
10455 sumcoef = weights[nvars - 1] + weights[nvars - 2];
10456 backpos = nvars - 2;
10461 sumcoef = weights[nvars - 3];
10462 backpos = nvars - 3;
10467 if( backpos <= pos )
10471 maxweight = weights[pos];
10473 while( 2 * maxweight > capacity && maxweight + sumcoef > capacity )
10475 assert(newweight > weights[pos]);
10477 SCIPdebugMsg(scip,
"in constraint <%s> changing weight %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10483 assert(pos < nvars);
10485 maxweight = weights[pos];
10487 if( backpos <= pos )
10490 (*nchgcoefs) += (pos - startpos);
10493 while( pos < nvars && weights[pos] + sumcoef == capacity )
10504 if( pos + 1 == backpos && weights[pos] > sumcoef &&
10505 ((k == 0) || (k == 1 && weights[nvars - 1] + sumcoef + weights[pos] > capacity)) )
10507 newweight = capacity - sumcoef;
10508 assert(newweight > weights[pos]);
10510 SCIPdebugMsg(scip,
"in constraint <%s> changing weight %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10518 if( backpos <= pos )
10526 if( conshdlrdata->disaggregation && consdata->nvars - pos <= MAX_USECLIQUES_SIZE && consdata->nvars >= 2 &&
10527 pos > 0 && (
SCIP_Longint)consdata->nvars - pos <= consdata->capacity &&
10528 consdata->weights[pos - 1] == consdata->capacity && (pos == consdata->nvars || consdata->weights[pos] == 1) )
10542 if( pos == consdata->nvars )
10563 len = consdata->nvars - pos;
10570 assert(nclq <= len);
10574 for( w = 0; w < nclq; ++w )
10575 assert(clqpart[w] <= w);
10584 for( w = pos - 1; w >= 0; --w )
10585 clqvars[w] = consdata->vars[w];
10588 for( c = 0; c < nclq; ++c )
10592 for( w = c; w < len; ++w )
10594 if( clqpart[w] == c )
10596 assert(nclqvars < pos + len - nclq + 1);
10597 clqvars[nclqvars] = consdata->vars[w + pos];
10602 assert(nclqvars > 1);
10630 int* newweightidxs;
10644 assert(consdata->merged);
10653 if( consdata->cliquepartition[consdata->nvars - 1] == consdata->nvars - 1 )
10657 cliqueweightsum = 0;
10660 for( i = 0; i < consdata->nvars; ++i )
10664 cliquenum = consdata->cliquepartition[i];
10665 assert(0 <= cliquenum && cliquenum <= ncliques);
10667 weight = consdata->weights[i];
10668 assert(weight > 0);
10670 if( cliquenum == ncliques )
10672 maxcliqueweights[ncliques] = weight;
10673 cliqueweightsum += weight;
10677 assert(maxcliqueweights[cliquenum] >= weight);
10681 zeroweights =
FALSE;
10682 for( i = 0; i < ncliques; ++i )
10686 delta = consdata->capacity - (cliqueweightsum - maxcliqueweights[i]);
10698 SCIPdebugMsg(scip,
"knapsack constraint <%s>: weights of clique %d (maxweight: %" SCIP_LONGINT_FORMAT
") can be tightened: cliqueweightsum=%" SCIP_LONGINT_FORMAT
", capacity=%" SCIP_LONGINT_FORMAT
" -> delta: %" SCIP_LONGINT_FORMAT
"\n",
10699 SCIPconsGetName(cons), i, maxcliqueweights[i], cliqueweightsum, consdata->capacity, delta);
10700 newcapacity = consdata->capacity - delta;
10701 forceclique =
FALSE;
10704 newmincliqueweight = newcapacity + 1;
10705 for( j = 0; j < i; ++j )
10706 assert(consdata->cliquepartition[j] < i);
10708 for( j = i; j < consdata->nvars; ++j )
10710 if( consdata->cliquepartition[j] == i )
10712 newweight = consdata->weights[j] - delta;
10713 newweight =
MAX(newweight, 0);
10716 assert(nnewweights < consdata->nvars);
10717 newweightvals[nnewweights] = newweight;
10718 newweightidxs[nnewweights] = j;
10722 assert(newweight <= newmincliqueweight);
10723 newmincliqueweight = newweight;
10729 if( nnewweights > 1 )
10732 j = newweightidxs[nnewweights - 2];
10733 assert(0 <= j && j < consdata->nvars);
10734 assert(consdata->cliquepartition[j] == i);
10735 j = newweightidxs[nnewweights - 1];
10736 assert(0 <= j && j < consdata->nvars);
10737 assert(consdata->cliquepartition[j] == i);
10740 newminweightsuminclique = newweightvals[nnewweights - 2];
10741 newminweightsuminclique += newweightvals[nnewweights - 1];
10748 if( newminweightsuminclique <= newcapacity )
10749 forceclique =
TRUE;
10753 if( conshdlrdata->disaggregation || !forceclique )
10755 SCIPdebugMsg(scip,
" -> change capacity from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
" (forceclique:%u)\n",
10756 consdata->capacity, newcapacity, forceclique);
10757 consdata->capacity = newcapacity;
10760 for( k = 0; k < nnewweights; ++k )
10762 j = newweightidxs[k];
10763 assert(0 <= j && j < consdata->nvars);
10764 assert(consdata->cliquepartition[j] == i);
10767 SCIPdebugMsg(scip,
" -> change weight of <%s> from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10768 SCIPvarGetName(consdata->vars[j]), consdata->weights[j], newweightvals[k]);
10771 assert(!consdata->sorted);
10772 zeroweights = zeroweights || (newweightvals[k] == 0);
10786 for( k = 0; k < nnewweights; ++k )
10787 cliquevars[k] = consdata->vars[newweightidxs[k]];
10810 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10818 if( consdata->weightsum <= consdata->capacity )
10830 if( consdata->weightsum <= consdata->capacity )
10833 if( (presoltiming & SCIP_PRESOLTIMING_FAST) != 0 )
10836 assert(consdata->merged);
10838 minweight = consdata->weights[consdata->nvars-1];
10839 for( i = 0; i < consdata->nvars-1; ++i )
10843 weight = consdata->weights[i];
10844 assert(weight >= minweight);
10845 if( minweight + weight > consdata->capacity )
10847 if( weight < consdata->capacity )
10849 SCIPdebugMsg(scip,
"knapsack constraint <%s>: changed weight of <%s> from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10851 assert(consdata->sorted);
10853 assert(i == 0 || consdata->weights[i-1] >= consdata->weights[i]);
10854 consdata->sorted =
TRUE;
10863 if( consdata->nvars >= 2 )
10867 minweight = consdata->weights[consdata->nvars-2];
10868 weight = consdata->weights[consdata->nvars-1];
10869 assert(minweight >= weight);
10870 if( minweight + weight > consdata->capacity && weight < consdata->capacity )
10872 SCIPdebugMsg(scip,
"knapsack constraint <%s>: changed weight of <%s> from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10874 assert(consdata->sorted);
10876 assert(minweight >= consdata->weights[consdata->nvars-1]);
10877 consdata->sorted =
TRUE;
10896 for( b = 0; b < ncliquevars; ++b )
10917 int* gaincliquepartition;
10923 int nposcliquevars;
10927 int lastcliqueused;
10932 assert(scip != NULL);
10933 assert(cons != NULL);
10934 assert(cutoff != NULL);
10935 assert(nbdchgs != NULL);
10940 assert(consdata != NULL);
10942 nvars = consdata->nvars;
10945 if( consdata->cliquesadded || nvars == 0 )
10956 assert(consdata->merged);
10959 assert(conshdlrdata != NULL);
10963 nnegcliques = consdata->nnegcliques;
10966 if( nnegcliques == nvars )
10980 minactduetonegcliques = 0;
10983 for( v = 0; v <
nvars; ++v )
10985 assert(0 <= consdata->negcliquepartition[v] && consdata->negcliquepartition[v] <= nnegcliques);
10986 assert(consdata->weights[v] > 0);
10988 if( consdata->negcliquepartition[v] == nnegcliques )
10991 maxweights[consdata->negcliquepartition[v]] = consdata->weights[v];
10994 minactduetonegcliques += consdata->weights[v];
10997 nposcliquevars = 0;
11000 if( minactduetonegcliques > 0 )
11003 freecapacity = consdata->capacity - minactduetonegcliques;
11006 SCIPdebugMsg(scip,
"Try to add negated cliques in knapsack constraint handler for constraint %s; capacity = %" SCIP_LONGINT_FORMAT
", minactivity(due to neg. cliques) = %" SCIP_LONGINT_FORMAT
", freecapacity = %" SCIP_LONGINT_FORMAT
".\n",
11007 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
11010 for( v = 0; v <
nvars; ++v )
11012 if( !cliqueused[consdata->negcliquepartition[v]] )
11014 cliqueused[consdata->negcliquepartition[v]] =
TRUE;
11015 for( w = v + 1; w <
nvars; ++w )
11019 if( consdata->negcliquepartition[v] == consdata->negcliquepartition[w]
11020 && consdata->weights[v] > consdata->weights[w] )
11022 poscliquevars[nposcliquevars] = consdata->vars[w];
11023 gainweights[nposcliquevars] = maxweights[consdata->negcliquepartition[v]] - consdata->weights[w];
11024 gaincliquepartition[nposcliquevars] = consdata->negcliquepartition[v];
11032 if( nposcliquevars > 0 )
11037 for( v = 0; v < nposcliquevars; ++v )
11041 lastweight = gainweights[v];
11042 beforelastweight = -1;
11043 lastcliqueused = gaincliquepartition[v];
11046 cliqueused[gaincliquepartition[v]] =
TRUE;
11050 for( w = v + 1; w < nposcliquevars && !cliqueused[gaincliquepartition[w]] && gainweights[w] + lastweight > freecapacity; ++w )
11052 beforelastweight = lastweight;
11053 lastweight = gainweights[w];
11054 lastcliqueused = gaincliquepartition[w];
11055 cliqueused[gaincliquepartition[w]] =
TRUE;
11060 if( ncliquevars > 1 )
11062 SCIPdebug( printClique(cliquevars, ncliquevars) );
11063 assert(beforelastweight > 0);
11069 *nbdchgs += thisnbdchgs;
11072 cliqueused[lastcliqueused] =
FALSE;
11075 for( ++w; w < nposcliquevars && !cliqueused[gaincliquepartition[w]] && beforelastweight + gainweights[w] > freecapacity; ++w )
11078 SCIPdebug( printClique(cliquevars, ncliquevars) );
11082 *nbdchgs += thisnbdchgs;
11129 if( ! sorteditems )
11133 lastweight = weights[0];
11136 for( i = 1; i < nitems && weights[i] + lastweight > capacity; ++i )
11138 lastweight = weights[i];
11142 if( ncliquevars > 1 )
11146 int compareweightidx;
11151 SCIPdebug( printClique(items, ncliquevars) );
11157 *nbdchgs += thisnbdchgs;
11158 nnzadded = ncliquevars;
11161 if( ncliquevars == nitems )
11169 compareweightidx = ncliquevars - 2;
11170 assert(i == nitems || weights[i] + weights[ncliquevars - 1] <= capacity);
11173 minclqsize = (int)(cliqueextractfactor * ncliquevars);
11174 minclqsize =
MAX(minclqsize, 2);
11178 while( compareweightidx >= 0 && i < nitems && ! (*cutoff)
11179 && ncliquevars >= minclqsize
11180 && nnzadded <= 2 * nitems
11183 compareweight = weights[compareweightidx];
11184 assert(compareweight > 0);
11187 if( compareweight + weights[i] > capacity )
11189 assert(compareweightidx == ncliquevars -2);
11190 cliquevars[ncliquevars - 1] = items[i];
11191 SCIPdebug( printClique(cliquevars, ncliquevars) );
11194 nnzadded += ncliquevars;
11198 *nbdchgs += thisnbdchgs;
11206 compareweightidx--;
11237 int nposcliquevars;
11241 assert(scip != NULL);
11242 assert(cons != NULL);
11243 assert(cutoff != NULL);
11244 assert(nbdchgs != NULL);
11249 assert(consdata != NULL);
11251 nvars = consdata->nvars;
11254 if( consdata->cliquesadded || nvars == 0 )
11265 assert(consdata->merged);
11268 assert(conshdlrdata != NULL);
11272 nnegcliques = consdata->nnegcliques;
11273 assert(nnegcliques <= nvars);
11282 minactduetonegcliques = 0;
11285 if( nnegcliques < nvars )
11289 for( i = 0; i <
nvars; ++i )
11293 cliquenum = consdata->negcliquepartition[i];
11294 assert(0 <= cliquenum && cliquenum <= nnegcliques);
11296 weight = consdata->weights[i];
11297 assert(weight > 0);
11299 if( cliquenum == nnegcliques )
11303 minactduetonegcliques += weight;
11304 if( secondmaxweights[cliquenum] == 0 )
11305 secondmaxweights[cliquenum] = weight;
11311 if( minactduetonegcliques > 0 )
11314 freecapacity = consdata->capacity - minactduetonegcliques;
11317 SCIPdebugMsg(scip,
"Try to add cliques in knapsack constraint handler for constraint %s; capacity = %" SCIP_LONGINT_FORMAT
", minactivity(due to neg. cliques) = %" SCIP_LONGINT_FORMAT
", freecapacity = %" SCIP_LONGINT_FORMAT
".\n",
11318 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
11326 nposcliquevars = 0;
11328 for( i = nvars - 1; i >= 0; --i )
11331 cliquenum = consdata->negcliquepartition[i];
11332 if( consdata->weights[i] > secondmaxweights[cliquenum] )
11334 poscliquevars[nposcliquevars] = consdata->vars[i];
11335 gainweights[nposcliquevars] = consdata->weights[i] - secondmaxweights[cliquenum];
11341 if( nposcliquevars > 1 )
11358 consdata->cliquesadded =
TRUE;
11387 assert(consdata1->sorted);
11388 assert(consdata2->sorted);
11390 scip = (
SCIP*)userptr;
11391 assert(scip != NULL);
11395 if( consdata1->nvars != consdata2->nvars )
11398 for( i = consdata1->nvars - 1; i >= 0; --i )
11401 if( consdata1->vars[i] != consdata2->vars[i] )
11403 assert(
SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
11407 assert(
SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 0);
11410 if( consdata1->weights[i] != consdata2->weights[i] )
11430 assert(consdata != NULL);
11431 assert(consdata->nvars > 0);
11434 scip = (
SCIP*)userptr;
11435 assert(scip != NULL);
11444 assert(minidx >= 0 && mididx >= 0 && maxidx >= 0);
11448 consdata->weights[0]);
11468 assert(scip != NULL);
11469 assert(blkmem != NULL);
11470 assert(conss != NULL);
11471 assert(ndelconss != NULL);
11474 hashtablesize = nconss;
11477 hashGetKeyKnapsackcons, hashKeyEqKnapsackcons, hashKeyValKnapsackcons, (
void*) scip) );
11480 for( c = nconss - 1; c >= 0; --c )
11492 assert(consdata0 != NULL);
11493 if( consdata0->nvars == 0 )
11495 if( consdata0->capacity < 0 )
11511 if( cons1 != NULL )
11525 assert(consdata1 != NULL);
11526 assert(consdata0->nvars > 0 && consdata0->nvars == consdata1->nvars);
11528 assert(consdata0->sorted && consdata1->sorted);
11529 assert(consdata0->vars[0] == consdata1->vars[0]);
11530 assert(consdata0->weights[0] == consdata1->weights[0]);
11532 SCIPdebugMsg(scip,
"knapsack constraints <%s> and <%s> with equal coefficients\n",
11536 if( consdata0->capacity < consdata1->capacity )
11591 assert(scip != NULL);
11592 assert(conss != NULL);
11593 assert(firstchange <= chkind);
11594 assert(ndelconss != NULL);
11597 cons0 = conss[chkind];
11598 assert(cons0 != NULL);
11603 assert(consdata0 != NULL);
11604 assert(consdata0->nvars >= 1);
11605 assert(consdata0->merged);
11623 assert(cons1 != NULL);
11628 assert(consdata1 != NULL);
11634 assert(consdata1->nvars >= 1);
11635 assert(consdata1->merged);
11642 if( consdata0->nvars > consdata1->nvars )
11644 iscons0incons1contained =
FALSE;
11645 iscons1incons0contained =
TRUE;
11646 v = consdata1->nvars - 1;
11648 else if( consdata0->nvars < consdata1->nvars )
11650 iscons0incons1contained =
TRUE;
11651 iscons1incons0contained =
FALSE;
11652 v = consdata0->nvars - 1;
11656 iscons0incons1contained =
TRUE;
11657 iscons1incons0contained =
TRUE;
11658 v = consdata0->nvars - 1;
11669 v0 = consdata0->nvars - 1;
11670 v1 = consdata1->nvars - 1;
11674 assert(iscons0incons1contained || iscons1incons0contained);
11679 iscons1incons0contained =
FALSE;
11680 if( !iscons0incons1contained )
11686 iscons0incons1contained =
FALSE;
11687 if( !iscons1incons0contained )
11691 assert(v == v0 || v == v1);
11696 if( consdata0->vars[v0] == consdata1->vars[v1] )
11699 if( iscons1incons0contained &&
SCIPisLT(scip, ((
SCIP_Real) consdata0->weights[v0]) / quotient, (
SCIP_Real) consdata1->weights[v1]) )
11701 iscons1incons0contained =
FALSE;
11702 if( !iscons0incons1contained )
11706 else if( iscons0incons1contained &&
SCIPisGT(scip, ((
SCIP_Real) consdata0->weights[v0]) / quotient, (
SCIP_Real) consdata1->weights[v1]) )
11708 iscons0incons1contained =
FALSE;
11709 if( !iscons1incons0contained )
11719 if( iscons0incons1contained && iscons1incons0contained )
11721 iscons0incons1contained =
FALSE;
11722 iscons1incons0contained =
FALSE;
11725 assert(iscons0incons1contained ? (v1 >= v0) : iscons1incons0contained);
11726 assert(iscons1incons0contained ? (v1 <= v0) : iscons0incons1contained);
11728 if( iscons0incons1contained )
11737 assert(!iscons1incons0contained || !iscons0incons1contained || v0 == -1 || v1 == -1);
11739 if( iscons1incons0contained )
11750 else if( iscons0incons1contained )
11788 SCIPdebugMsg(scip,
"knapsack enforcement of %d/%d constraints for %s solution\n", nusefulconss, nconss,
11789 sol == NULL ?
"LP" :
"relaxation");
11793 assert(conshdlrdata != NULL);
11794 maxncuts = (
SCIPgetDepth(scip) == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
11797 for( i = 0; i < nusefulconss && ncuts < maxncuts && ! cutoff; i++ )
11809 for( i = nusefulconss; i < nconss && ncuts == 0 && ! cutoff; i++ )
11823 else if ( ncuts > 0 )
11876 assert(nvars == 0 || vars != NULL);
11877 assert(nvars == 0 || vals != NULL);
11899 for( v = 0; v <
nvars; ++v )
11905 transvars[v] = vars[v];
11906 weights[v] = weight;
11911 weights[v] = -weight;
11912 capacity -= weight;
11914 assert(transvars[v] != NULL);
11919 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
11934 assert(upgdcons != NULL);
11941 upgrade = (nposbin + nnegbin + nposimplbin + nnegimplbin ==
nvars)
11942 && (ncoeffspone + ncoeffsnone + ncoeffspint + ncoeffsnint == nvars)
11971 assert(scip != NULL);
11972 assert(conshdlr != NULL);
11993 assert(conshdlrdata != NULL);
12011 assert( scip != NULL );
12012 assert( conshdlr != NULL );
12015 assert(conshdlrdata != NULL);
12021 conshdlrdata->reals1size =
nvars;
12032 assert( scip != NULL );
12033 assert( conshdlr != NULL );
12036 assert(conshdlrdata != NULL);
12039 conshdlrdata->reals1size = 0;
12052 assert(scip != NULL);
12053 assert(conshdlr != NULL);
12054 assert(nconss == 0 || conss != NULL);
12057 assert(conshdlrdata != NULL);
12071 conshdlrdata->ints1size =
nvars;
12072 conshdlrdata->ints2size =
nvars;
12073 conshdlrdata->longints1size =
nvars;
12074 conshdlrdata->longints2size =
nvars;
12075 conshdlrdata->bools1size =
nvars;
12076 conshdlrdata->bools2size =
nvars;
12077 conshdlrdata->bools3size =
nvars;
12078 conshdlrdata->bools4size =
nvars;
12080 #ifdef WITH_CARDINALITY_UPGRADE 12081 conshdlrdata->upgradedcard =
FALSE;
12095 assert(scip != NULL);
12096 assert(conshdlr != NULL);
12098 for( c = 0; c < nconss; ++c )
12108 assert(conshdlrdata != NULL);
12119 conshdlrdata->ints1size = 0;
12120 conshdlrdata->ints2size = 0;
12121 conshdlrdata->longints1size = 0;
12122 conshdlrdata->longints2size = 0;
12123 conshdlrdata->bools1size = 0;
12124 conshdlrdata->bools2size = 0;
12125 conshdlrdata->bools3size = 0;
12126 conshdlrdata->bools4size = 0;
12139 assert( scip != NULL );
12142 for( c = 0; c < nconss; ++c )
12145 assert(consdata != NULL);
12147 if( consdata->row != NULL )
12162 assert(conshdlr != NULL);
12167 assert(conshdlrdata != NULL);
12168 assert(conshdlrdata->eventhdlr != NULL);
12185 assert(conshdlr != NULL);
12188 assert(sourcecons != NULL);
12189 assert(targetcons != NULL);
12192 assert(sourcedata != NULL);
12193 assert(sourcedata->row == NULL);
12197 assert(conshdlrdata != NULL);
12198 assert(conshdlrdata->eventhdlr != NULL);
12202 sourcedata->nvars, sourcedata->vars, sourcedata->weights, sourcedata->capacity) );
12224 *infeasible =
FALSE;
12226 for( i = 0; i < nconss && !(*infeasible); i++ )
12259 assert(conshdlrdata != NULL);
12264 SCIPdebugMsg(scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12265 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12268 if( (depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12269 || (depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12274 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12275 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12276 && ((sepacardfreq == 0 && depth == 0) || (sepacardfreq >= 1 && (depth % sepacardfreq == 0)));
12282 maxbound = glblowerbound + conshdlrdata->maxcardbounddist * (cutoffbound - glblowerbound);
12283 sepacardinality = sepacardinality &&
SCIPisLE(scip, loclowerbound, maxbound);
12287 maxsepacuts = (depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12294 for( i = 0; i < nusefulconss && ncuts < maxsepacuts && !
SCIPisStopped(scip); i++ )
12296 SCIP_CALL(
separateCons(scip, conss[i], NULL, sepacardinality, conshdlrdata->usegubs, &cutoff, &ncuts) );
12302 else if ( ncuts > 0 )
12328 assert(conshdlrdata != NULL);
12333 SCIPdebugMsg(scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12334 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12337 if( (depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12338 || (depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12343 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12344 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12345 && ((sepacardfreq == 0 && depth == 0) || (sepacardfreq >= 1 && (depth % sepacardfreq == 0)));
12348 maxsepacuts = (depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12355 for( i = 0; i < nusefulconss && ncuts < maxsepacuts && !
SCIPisStopped(scip); i++ )
12357 SCIP_CALL(
separateCons(scip, conss[i], sol, sepacardinality, conshdlrdata->usegubs, &cutoff, &ncuts) );
12363 else if( ncuts > 0 )
12394 for( i = 0; i < nconss; i++ )
12417 for( i = 0; i < nconss && (*result ==
SCIP_FEASIBLE || completely); i++ )
12442 assert(conshdlrdata != NULL);
12448 for( i = 0; i < nmarkedconss && !cutoff; i++ )
12460 SCIP_CALL(
propagateCons(scip, conss[i], &cutoff, &redundant, &nfixedvars, conshdlrdata->negatedclique) );
12470 else if( nfixedvars > 0 )
12500 oldnfixedvars = *nfixedvars;
12501 oldnchgbds = *nchgbds;
12502 oldndelconss = *ndelconss;
12503 oldnaddconss = *naddconss;
12504 oldnchgcoefs = *nchgcoefs;
12505 oldnchgsides = *nchgsides;
12506 firstchange = INT_MAX;
12508 newchanges = (nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 || nnewupgdconss > 0);
12511 assert(conshdlrdata != NULL);
12515 int thisnfixedvars;
12520 assert(consdata != NULL);
12524 if( newchanges || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
12533 consdata->presolvedtiming = 0;
12534 else if( consdata->presolvedtiming >= presoltiming )
12539 consdata->presolvedtiming = presoltiming;
12541 thisnfixedvars = *nfixedvars;
12542 thisnchgbds = *nchgbds;
12552 SCIP_CALL(
addCliques(scip, cons, conshdlrdata->cliqueextractfactor, &cutoff, nchgbds) );
12560 SCIP_CALL(
propagateCons(scip, cons, &cutoff, &redundant, nfixedvars, (presoltiming & SCIP_PRESOLTIMING_MEDIUM)) );
12572 if( *nfixedvars > thisnfixedvars || *nchgbds > thisnchgbds )
12578 thisnfixedvars = *nfixedvars;
12584 if( consdata->weightsum <= consdata->capacity )
12586 SCIPdebugMsg(scip,
" -> knapsack constraint <%s> is redundant: weightsum=%" SCIP_LONGINT_FORMAT
", capacity=%" SCIP_LONGINT_FORMAT
"\n",
12606 if( *nfixedvars > thisnfixedvars )
12621 if( conshdlrdata->dualpresolving &&
SCIPallowDualReds(scip) && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
12641 if( !cutoff && conshdlrdata->presolusehashing && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
12647 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) || (*naddconss != oldnaddconss) )
12656 npaircomparisons = 0;
12657 oldndelconss = *ndelconss;
12658 oldnchgsides = *nchgsides;
12659 oldnchgcoefs = *nchgcoefs;
12661 for( c = firstchange; c < nconss && !cutoff && !
SCIPisStopped(scip); ++c )
12673 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) )
12675 if( ((
SCIP_Real) (*ndelconss - oldndelconss) + ((
SCIP_Real) (*nchgsides - oldnchgsides))/2.0 +
12678 oldndelconss = *ndelconss;
12679 oldnchgsides = *nchgsides;
12680 oldnchgcoefs = *nchgcoefs;
12681 npaircomparisons = 0;
12685 #ifdef WITH_CARDINALITY_UPGRADE 12694 if ( ! cutoff && conshdlrdata->upgdcardinality && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 &&
SCIPisPresolveFinished(scip) && ! conshdlrdata->upgradedcard )
12703 noldupgdconss = *nupgdconss;
12716 for (makeupgrade = 0; makeupgrade < 2; ++makeupgrade)
12727 assert( cons != NULL );
12729 assert( consdata != NULL );
12731 nvars = consdata->nvars;
12732 vars = consdata->vars;
12733 weights = consdata->weights;
12740 if ( consdata->capacity >= nvars )
12744 assert( consdata->sorted );
12745 if ( weights[0] != 1 || weights[nvars-1] != 1 )
12749 for (v = 0; v <
nvars; ++v)
12758 var = consdata->vars[v];
12759 assert( var != NULL );
12775 for (j = 0; j < nimpls; ++j)
12789 cardvars[v] = implvars[j];
12806 if ( makeupgrade == 0 )
12808 for (v = 0; v <
nvars; ++v)
12832 for (v = 0; v <
nvars; ++v)
12842 conshdlrdata->upgradedcard =
TRUE;
12871 assert( origcons != NULL );
12874 for (v = 0; v <
nvars; ++v)
12890 if ( *nupgdconss > noldupgdconss )
12897 else if( success || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
12913 assert(result != NULL);
12916 assert(consdata != NULL);
12921 for( i = 0; i < consdata->nvars; ++i )
12930 assert(i < consdata->nvars);
12938 if( inferinfo < 0 )
12945 if( inferinfo < consdata->nvars && consdata->vars[inferinfo] == infervar )
12946 capsum = consdata->weights[inferinfo];
12949 for( i = 0; i < consdata->nvars && consdata->vars[i] != infervar; ++i )
12951 assert(i < consdata->nvars);
12952 capsum = consdata->weights[i];
12959 if( capsum <= consdata->capacity )
12961 for( i = 0; i < consdata->nvars; i++ )
12966 capsum += consdata->weights[i];
12967 if( capsum > consdata->capacity )
12997 assert(consdata != NULL);
12999 for( i = 0; i < consdata->nvars; i++)
13013 assert(scip != NULL);
13014 assert(conshdlr != NULL);
13015 assert(conss != NULL || nconss == 0);
13032 assert( scip != NULL );
13033 assert( conshdlr != NULL );
13034 assert( cons != NULL );
13037 assert(consdata != NULL);
13039 for( i = 0; i < consdata->nvars; ++i )
13043 SCIPinfoMessage(scip, file,
"%+" SCIP_LONGINT_FORMAT, consdata->weights[i]);
13046 SCIPinfoMessage(scip, file,
" <= %" SCIP_LONGINT_FORMAT
"", consdata->capacity);
13058 const char* consname;
13068 for( v = 0; v <
nvars; ++v )
13079 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, global, valid) );
13080 assert(cons != NULL);
13101 assert(scip != NULL);
13102 assert(success != NULL);
13103 assert(str != NULL);
13104 assert(name != NULL);
13105 assert(cons != NULL);
13114 while( *str !=
'\0' )
13117 if( sscanf(str,
"%" SCIP_LONGINT_FORMAT
"%n", &weight, &nread) < 1 )
13123 while( isspace((
int)*str) )
13138 if( varssize <= nvars )
13146 weights[
nvars] = weight;
13150 while( isspace((
int)*str) )
13156 if( strncmp(str,
"<= ", 3) != 0 )
13169 if( sscanf(str,
"%" SCIP_LONGINT_FORMAT, &capacity) != 1 )
13177 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
13194 assert(consdata != NULL);
13196 if( varssize < consdata->nvars )
13200 assert(vars != NULL);
13216 assert(consdata != NULL);
13218 (*nvars) = consdata->nvars;
13234 assert(eventdata != NULL);
13235 assert(eventdata->cons != NULL);
13238 assert(consdata != NULL);
13243 consdata->onesweightsum += eventdata->weight;
13244 consdata->presolvedtiming = 0;
13248 consdata->onesweightsum -= eventdata->weight;
13251 consdata->presolvedtiming = 0;
13255 if( !consdata->existmultaggr )
13259 assert(var != NULL);
13264 consdata->existmultaggr =
TRUE;
13265 consdata->merged =
FALSE;
13268 consdata->merged =
FALSE;
13273 consdata->presolvedtiming = 0;
13276 consdata->varsdeleted =
TRUE;
13304 eventhdlrdata = NULL;
13305 conshdlrdata->eventhdlr = NULL;
13307 eventExecKnapsack, eventhdlrdata) );
13310 if( conshdlrdata->eventhdlr == NULL )
13319 consEnfolpKnapsack, consEnfopsKnapsack, consCheckKnapsack, consLockKnapsack,
13322 assert(conshdlr != NULL);
13357 "multiplier on separation frequency, how often knapsack cuts are separated (-1: never, 0: only at root)",
13361 "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for separating knapsack cuts",
13365 "lower clique size limit for greedy clique extraction algorithm (relative to largest clique)",
13369 "maximal number of separation rounds per node (-1: unlimited)",
13373 "maximal number of separation rounds per node in the root node (-1: unlimited)",
13377 "maximal number of cuts separated per separation round",
13381 "maximal number of cuts separated per separation round in the root node",
13385 "should disaggregation of knapsack constraints be allowed in preprocessing?",
13389 "should presolving try to simplify knapsacks",
13393 "should negated clique information be used in solving process",
13397 "should pairwise constraint comparison be performed in presolving?",
13401 "should hash table be used for detecting redundant constraints in advance",
13405 "should dual presolving steps be performed?",
13409 "should GUB information be used for separation?",
13413 "should presolving try to detect constraints parallel to the objective function defining an upper bound and prevent these constraints from entering the LP?",
13417 "should presolving try to detect constraints parallel to the objective function defining a lower bound and prevent these constraints from entering the LP?",
13421 "should clique partition information be updated when old partition seems outdated?",
13425 "factor on the growth of global cliques to decide when to update a previous " 13426 "(negated) clique partition (used only if updatecliquepartitions is set to TRUE)",
13428 #ifdef WITH_CARDINALITY_UPGRADE 13431 "if TRUE then try to update knapsack constraints to cardinality constraints",
13432 &conshdlrdata->upgdcardinality,
TRUE, DEFAULT_UPGDCARDINALITY, NULL, NULL) );
13481 if( conshdlr == NULL )
13489 assert(conshdlrdata != NULL);
13490 assert(conshdlrdata->eventhdlr != NULL);
13496 SCIP_CALL(
SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
13497 local, modifiable, dynamic, removable, stickingatnode) );
13527 assert(scip != NULL);
13543 assert(var != NULL);
13572 assert(consdata != NULL);
13574 return consdata->capacity;
13597 SCIPerrorMessage(
"method can only be called during problem creation stage\n");
13602 assert(consdata != NULL);
13604 consdata->capacity = capacity;
13625 assert(consdata != NULL);
13627 return consdata->nvars;
13646 assert(consdata != NULL);
13648 return consdata->vars;
13667 assert(consdata != NULL);
13669 return consdata->weights;
13688 assert(consdata != NULL);
13690 if( consdata->row != NULL )
13712 assert(consdata != NULL);
13714 if( consdata->row != NULL )
13738 assert(consdata != NULL);
13740 return consdata->row;
enum SCIP_Result SCIP_RESULT
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
#define KNAPSACKRELAX_MAXSCALE
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
void SCIPsortPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
enum SCIP_BoundType SCIP_BOUNDTYPE
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
#define DEFAULT_DETECTCUTOFFBOUND
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
SCIP_RETCODE SCIPflattenVarAggregationGraph(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
SCIP_Bool SCIPinRepropagation(SCIP *scip)
static SCIP_RETCODE GUBsetFree(SCIP *scip, SCIP_GUBSET **gubset)
static SCIP_RETCODE performVarDeletions(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss)
static SCIP_RETCODE mergeMultiples(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
SCIP_Real * SCIPvarGetVlbCoefs(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)
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
static SCIP_DECL_EVENTEXEC(eventExecKnapsack)
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)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define CONSHDLR_PROP_TIMING
SCIP_STAGE SCIPgetStage(SCIP *scip)
#define SCIP_EVENTTYPE_VARFIXED
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
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_DECL_CONSRESPROP(consRespropKnapsack)
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_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE GUBsetMoveVar(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, int var, int oldgubcons, int newgubcons)
static SCIP_RETCODE addNegatedCliques(SCIP *const scip, SCIP_CONS *const cons, SCIP_Bool *const cutoff, int *const nbdchgs)
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
static SCIP_DECL_CONSINIT(consInitKnapsack)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
static SCIP_DECL_HASHKEYVAL(hashKeyValKnapsackcons)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
#define SCIPallocClearBufferArray(scip, ptr, num)
int SCIPvarGetNVlbs(SCIP_VAR *var)
#define DEFAULT_CLQPARTUPDATEFAC
void SCIPsortDownLongPtrPtrIntInt(SCIP_Longint *longarray, void **ptrarray1, void **ptrarray2, int *intarray1, int *intarray2, int len)
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool sepacuts, SCIP_Bool usegubs, SCIP_Bool *cutoff, int *ncuts)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
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)
GUBCONSSTATUS * gubconsstatus
SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
SCIP_RETCODE SCIPupdateCutoffbound(SCIP *scip, SCIP_Real cutoffbound)
#define CONSHDLR_ENFOPRIORITY
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 SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
static void updateWeightSums(SCIP_CONSDATA *consdata, SCIP_VAR *var, SCIP_Longint weightdelta)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPsetConsPropagated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool propagate)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPgetNegatedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **negvars)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
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)
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)
#define LINCONSUPGD_PRIORITY
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
#define DEFAULT_CLIQUEEXTRACTFACTOR
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight)
static SCIP_DECL_CONSINITLP(consInitlpKnapsack)
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
static SCIP_DECL_CONSCHECK(consCheckKnapsack)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre)))
static SCIP_RETCODE checkParallelObjective(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata)
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)
static SCIP_RETCODE dualWeightsTightening(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss)
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr)
#define CONSHDLR_SEPAFREQ
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, SCIP_Bool *redundant, int *nfixedvars, SCIP_Bool usenegatedclique)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
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)
#define CONSHDLR_MAXPREROUNDS
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
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)
SCIP_RETCODE SCIPunmarkConsPropagate(SCIP *scip, SCIP_CONS *cons)
enum SCIP_Retcode SCIP_RETCODE
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)
SCIP_Real SCIPgetLocalLowerbound(SCIP *scip)
#define CONSHDLR_EAGERFREQ
SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
int SCIPvarGetNVubs(SCIP_VAR *var)
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)
#define SCIP_PRESOLTIMING_EXHAUSTIVE
static void consdataChgWeight(SCIP_CONSDATA *consdata, int item, SCIP_Longint newweight)
int SCIPvarGetProbindex(SCIP_VAR *var)
SCIP_Longint SCIPsepaGetNCutsFound(SCIP_SEPA *sepa)
SCIP_Longint SCIPconshdlrGetNCutsFound(SCIP_CONSHDLR *conshdlr)
static void getPartitionNoncovervars(SCIP *scip, SCIP_Real *solvals, int *noncovervars, int nnoncovervars, int *varsF, int *varsR, int *nvarsF, int *nvarsR)
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
#define SCIPfreeBlockMemory(scip, ptr)
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
SCIP_Real SCIPgetDualsolKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPvarGetVlbVars(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)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
int SCIPconshdlrGetSepaFreq(SCIP_CONSHDLR *conshdlr)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPaddCoefKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight)
#define SCIPfreeBufferArray(scip, ptr)
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPdebugPrintCons(x, y, z)
SCIP_Bool SCIPisTransformed(SCIP *scip)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPsetConshdlrDelvars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELVARS((*consdelvars)))
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
#define SCIPdebugMsgPrint
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 SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
#define CONSHDLR_PRESOLTIMING
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
#define DEFAULT_PRESOLUSEHASHING
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
static SCIP_RETCODE GUBsetGetCliquePartition(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, SCIP_Real *solvals)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
int SCIPgetNContVars(SCIP *scip)
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_Real SCIPepsilon(SCIP *scip)
#define SCIP_PRESOLTIMING_FAST
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)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
static SCIP_DECL_CONSDELETE(consDeleteKnapsack)
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result)
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
#define DEFAULT_SEPACARDFREQ
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
#define SCIP_EVENTTYPE_LBRELAXED
static SCIP_RETCODE GUBconsFree(SCIP *scip, SCIP_GUBCONS **gubcons)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
static SCIP_DECL_HASHGETKEY(hashGetKeyKnapsackcons)
static SCIP_RETCODE GUBconsDelVar(SCIP *scip, SCIP_GUBCONS *gubcons, int var, int gubvarsidx)
static SCIP_DECL_CONSPARSE(consParseKnapsack)
SCIP_RETCODE SCIPsetConsSeparated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool separate)
SCIP_RETCODE SCIPaddClique(SCIP *scip, SCIP_VAR **vars, SCIP_Bool *values, int nvars, SCIP_Bool isequation, SCIP_Bool *infeasible, int *nbdchgs)
static SCIP_RETCODE stableSort(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR **vars, SCIP_Longint *weights, int *cliquestartposs, SCIP_Bool usenegatedclique)
#define DEFAULT_MAXROUNDS
#define DEFAULT_DISAGGREGATION
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checklprows, SCIP_Bool printreason, SCIP_Bool *violated)
static SCIP_RETCODE applyFixings(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
#define CONSHDLR_SEPAPRIORITY
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_RETCODE SCIPchgCapacityKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_Longint capacity)
Constraint handler for knapsack constraints of the form , x binary and .
SCIP_Bool SCIPisPresolveFinished(SCIP *scip)
void SCIPsortDownPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define SCIP_PRESOLTIMING_MEDIUM
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
static SCIP_DECL_HASHKEYEQ(hashKeyEqKnapsackcons)
static SCIP_DECL_CONSEXITSOL(consExitsolKnapsack)
enum GUBVarstatus GUBVARSTATUS
static void getPartitionCovervars(SCIP *scip, SCIP_Real *solvals, int *covervars, int ncovervars, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2)
static SCIP_RETCODE simplifyInequalities(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss, SCIP_Bool *cutoff)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_CONSDELVARS(consDelvarsKnapsack)
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
static void GUBsetSwapVars(SCIP *scip, SCIP_GUBSET *gubset, int var1, int var2)
#define DEFAULT_PRESOLPAIRWISE
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
#define SCIPallocBuffer(scip, ptr)
SCIPInterval sqrt(const SCIPInterval &x)
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 DEFAULT_DUALPRESOLVING
static SCIP_DECL_CONSINITPRE(consInitpreKnapsack)
SCIP_CONS * SCIPfindOrigCons(SCIP *scip, const char *name)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
SCIP_RETCODE SCIPsetConsChecked(SCIP *scip, SCIP_CONS *cons, SCIP_Bool check)
static SCIP_DECL_CONSENFORELAX(consEnforelaxKnapsack)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
#define SCIP_EVENTTYPE_IMPLADDED
struct SCIP_EventData SCIP_EVENTDATA
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
static SCIP_DECL_SORTPTRCOMP(compSortkeypairs)
static SCIP_Longint safeAddMinweightsGUB(SCIP_Longint val1, SCIP_Longint val2)
SCIP_RETCODE SCIPmarkConsPropagate(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_CONSPRINT(consPrintKnapsack)
#define DEFAULT_NEGATEDCLIQUE
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)
#define SCIPhashTwo(a, b)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
#define SCIP_EVENTTYPE_LBTIGHTENED
unsigned int SCIP_PRESOLTIMING
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var)
static SCIP_DECL_CONSENFOPS(consEnfopsKnapsack)
#define MAXNCLIQUEVARSCOMP
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
GUBVARSTATUS * gubvarsstatus
void SCIPupdateSolLPConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
#define KNAPSACKRELAX_MAXDNOM
#define DEFAULT_MAXSEPACUTSROOT
static SCIP_DECL_CONSFREE(consFreeKnapsack)
void SCIPsortPtrPtrIntInt(void **ptrarray1, void **ptrarray2, int *intarray1, int *intarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_RETCODE SCIPcreateConsBasicKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons)
struct SCIP_ConsData SCIP_CONSDATA
static SCIP_DECL_CONSEXIT(consExitKnapsack)
static SCIP_RETCODE getLiftingSequence(SCIP *scip, SCIP_Real *solvals, SCIP_Longint *weights, int *varsF, int *varsC2, int *varsR, int nvarsF, int nvarsC2, int nvarsR)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
void SCIPsortDownRealLongRealInt(SCIP_Real *realarray1, SCIP_Longint *longarray, SCIP_Real *realarray3, int *intarray, int len)
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
static SCIP_DECL_CONSPRESOL(consPresolKnapsack)
static SCIP_RETCODE consdataEnsureVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool transformed)
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)
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, int pos)
#define SCIPallocBufferArray(scip, ptr, num)
public data structures and miscellaneous methods
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
static SCIP_RETCODE enlargeMinweights(SCIP *scip, SCIP_Longint **minweightsptr, int *minweightslen, int *minweightssize, int newlen)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
#define MINGAINPERNMINCOMPARISONS
static SCIP_RETCODE calcCliquepartition(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSDATA *consdata, SCIP_Bool normalclique, SCIP_Bool negatedclique)
static SCIP_DECL_CONSPROP(consPropKnapsack)
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)
#define CONSHDLR_DELAYSEPA
#define DEFAULT_MAXSEPACUTS
SCIP_RETCODE SCIPcreateEmptyRowCons(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 SCIPincludeConshdlrKnapsack(SCIP *scip)
#define DEFAULT_MAXCARDBOUNDDIST
int SCIPgetDepth(SCIP *scip)
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
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)
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
static SCIP_DECL_CONSEXITPRE(consExitpreKnapsack)
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
static SCIP_RETCODE eventdataCreate(SCIP *scip, SCIP_EVENTDATA **eventdata, SCIP_CONS *cons, SCIP_Longint weight)
SCIP_RETCODE SCIPcalcCliquePartition(SCIP *const scip, SCIP_VAR **const vars, int const nvars, int *const cliquepartition, int *const ncliques)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
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_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
static SCIP_RETCODE GUBsetCreate(SCIP *scip, SCIP_GUBSET **gubset, int nvars, SCIP_Longint *weights, SCIP_Longint capacity)
#define KNAPSACKRELAX_MAXDELTA
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
#define MAX_ZEROITEMS_SIZE
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
#define SCIPcombineFourInt(a, b, c, d)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
#define BMScopyMemoryArray(ptr, source, num)
static void sortItems(SCIP_CONSDATA *consdata)
#define CONSHDLR_DELAYPROP
SCIP_Real SCIProwGetDualfarkas(SCIP_ROW *row)
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
static void normalizeWeights(SCIP_CONS *cons, int *nchgcoefs, int *nchgsides)
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
#define SCIP_EVENTTYPE_UBTIGHTENED
Constraint handler for linear constraints in their most general form, .
int SCIPgetNObjVars(SCIP *scip)
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
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)
static SCIP_RETCODE prepareCons(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, int *nchgcoefs)
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
static SCIP_RETCODE deleteRedundantVars(SCIP *scip, SCIP_CONS *cons, SCIP_Longint frontsum, int splitpos, int *nchgcoefs, int *nchgsides, int *naddconss)
static SCIP_RETCODE changePartitionCovervars(SCIP *scip, SCIP_Longint *weights, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2)
#define SCIP_MAXTREEDEPTH
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
SCIP_Bool SCIPinProbing(SCIP *scip)
static SCIP_RETCODE dualPresolving(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, SCIP_Bool *deleted)
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
SCIP_RETCODE SCIPincludeLinconsUpgrade(SCIP *scip, SCIP_DECL_LINCONSUPGD((*linconsupgd)), int priority, const char *conshdlrname)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPupdateLocalLowerbound(SCIP *scip, SCIP_Real newbound)
static SCIP_RETCODE upgradeCons(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss)
static SCIP_DECL_CONSSEPALP(consSepalpKnapsack)
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre)))
static SCIP_RETCODE sequentialUpAndDownLifting(SCIP *scip, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *varsM1, int *varsM2, int *varsF, int *varsR, int nvarsM1, int nvarsM2, int nvarsF, int nvarsR, int alpha0, int *liftcoefs, SCIP_Real *cutact, int *liftrhs)
static SCIP_RETCODE 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_DECL_LINCONSUPGD(linconsUpgdKnapsack)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
static SCIP_DECL_CONSCOPY(consCopyKnapsack)
static SCIP_RETCODE GUBconsCreate(SCIP *scip, SCIP_GUBCONS **gubcons)
#define SCIPfreeBuffer(scip, ptr)
static SCIP_RETCODE GUBsetCheck(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
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)
static SCIP_DECL_CONSLOCK(consLockKnapsack)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_CONSGETNVARS(consGetNVarsKnapsack)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINIT((*consinit)))
static SCIP_RETCODE detectRedundantConstraints(SCIP *scip, BMS_BLKMEM *blkmem, SCIP_CONS **conss, int nconss, SCIP_Bool *cutoff, int *ndelconss)
SCIP_RETCODE SCIPsetConsEnforced(SCIP *scip, SCIP_CONS *cons, SCIP_Bool enforce)
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit)))
SCIP_Bool SCIPisConsCompressionEnabled(SCIP *scip)
constraint handler for cardinality constraints
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
static SCIP_Bool checkMinweightidx(SCIP_Longint *weights, SCIP_Longint capacity, int *covervars, int ncovervars, SCIP_Longint coverweight, int minweightidx, int j)
SCIP_Bool SCIPallowDualReds(SCIP *scip)
#define DEFAULT_DETECTLOWERBOUND
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
#define HASHSIZE_KNAPSACKCONS
enum GUBConsstatus GUBCONSSTATUS
int SCIPgetNCliques(SCIP *scip)
#define MAX_USECLIQUES_SIZE
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
static SCIP_DECL_CONSGETVARS(consGetVarsKnapsack)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_RETCODE SCIPhashmapSetImage(SCIP_HASHMAP *hashmap, void *origin, void *image)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_RETCODE SCIPcalcNegatedCliquePartition(SCIP *const scip, SCIP_VAR **const vars, int const nvars, int *const cliquepartition, int *const ncliques)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
static SCIP_RETCODE GUBconsAddVar(SCIP *scip, SCIP_GUBCONS *gubcons, int var)
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPvarsGetProbvarBinary(SCIP_VAR ***vars, SCIP_Bool **negatedarr, int nvars)
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_CONSSEPASOL(consSepasolKnapsack)
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
static SCIP_RETCODE tightenWeights(SCIP *scip, SCIP_CONS *cons, SCIP_PRESOLTIMING presoltiming, int *nchgcoefs, int *nchgsides, int *naddconss, int *ndelconss, SCIP_Bool *cutoff)
#define EVENTTYPE_KNAPSACK
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
static SCIP_DECL_CONSENFOLP(consEnfolpKnapsack)
static SCIP_RETCODE removeZeroWeights(SCIP *scip, SCIP_CONS *cons)
#define DEFAULT_MAXROUNDSROOT
#define CONSHDLR_PROPFREQ
#define CONSHDLR_NEEDSCONS
SCIP_Real SCIPcutoffbounddelta(SCIP *scip)
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)
int SCIPvarGetIndex(SCIP_VAR *var)
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)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPsortPtrPtrLongIntInt(void **ptrarray1, void **ptrarray2, SCIP_Longint *longarray, int *intarray1, int *intarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
void SCIPsortDownRealIntLong(SCIP_Real *realarray, int *intarray, SCIP_Longint *longarray, int len)
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 preprocessConstraintPairs(SCIP *scip, SCIP_CONS **conss, int firstchange, int chkind, int *ndelconss)
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
#define BMSclearMemoryArray(ptr, num)
static SCIP_RETCODE eventdataFree(SCIP *scip, SCIP_EVENTDATA **eventdata)
static SCIP_RETCODE detectRedundantVars(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss)
struct BMS_BlkMem BMS_BLKMEM
static SCIP_DECL_CONSTRANS(consTransKnapsack)
SCIP_Real SCIPgetDualfarkasKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
SCIP_ROW * SCIPgetRowKnapsack(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyKnapsack)
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
#define MAXCOVERSIZEITERLEWI
SCIP_Longint SCIPcalcGreComDiv(SCIP_Longint val1, SCIP_Longint val2)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Bool SCIPvarIsDeleted(SCIP_VAR *var)
static SCIP_RETCODE changePartitionFeasiblesetvars(SCIP *scip, SCIP_Longint *weights, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2)
static SCIP_RETCODE tightenWeightsLift(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, SCIP_Bool *cutoff)
void SCIPsortDownLongPtr(SCIP_Longint *longarray, void **ptrarray, int len)
#define DEFAULT_UPDATECLIQUEPARTITIONS
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 SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
static SCIP_RETCODE addCliques(SCIP *const scip, SCIP_CONS *const cons, SCIP_Real cliqueextractfactor, SCIP_Bool *const cutoff, int *const nbdchgs)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
#define CONSHDLR_CHECKPRIORITY
#define SCIP_EVENTTYPE_VARDELETED
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
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 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 SCIPgetNSepaRounds(SCIP *scip)
#define DEFAULT_SIMPLIFYINEQUALITIES
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
static void computeMinweightsGUB(SCIP_Longint *minweights, SCIP_Longint *finished, SCIP_Longint *unfinished, int minweightslen)
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
#define SCIPreallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial)
void SCIPsortDownLongPtrInt(SCIP_Longint *longarray, void **ptrarray, int *intarray, int len)