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 )
7607 SCIP_Longint oldonesweightsum = consdata->onesweightsum;
7609 assert(maxcliqueweight >= secondmaxweights[c]);
7615 assert(consdata->onesweightsum == oldonesweightsum);
7616 assert(!infeasible);
7624 else if( nnegcliques - c == nvars - startvarposclique )
7634 else if( consdata->onesweightsum + minweightsum + (maxcliqueweight - consdata->weights[nvars - 1]) <= consdata->capacity )
7638 for( i = endvarposclique; i > startvarposclique; --i )
7647 assert(maxcliqueweight >= myweights[i]);
7648 assert(i == endvarposclique || myweights[i] >= myweights[i+1]);
7656 if( maxvarfixed || consdata->onesweightsum + minweightsum - myweights[i] + maxcliqueweight > consdata->capacity )
7659 SCIP_Longint oldonesweightsum = consdata->onesweightsum;
7663 assert(consdata->onesweightsum == oldonesweightsum + myweights[i]);
7664 assert(!infeasible);
7672 minweightsum -= myweights[i];
7673 assert(minweightsum >= 0);
7681 for( ; i > startvarposclique; --i )
7684 SCIP_Bool exceedscapacity = consdata->onesweightsum + minweightsum - myweights[i] + maxcliqueweight > consdata->capacity;
7686 assert(i == endvarposclique || myweights[i] >= myweights[i+1]);
7687 assert(varisfixed || !exceedscapacity);
7699 assert(consdata->negcliquepartitioned || minweightsum == 0);
7703 assert(usenegatedclique || minweightsum == 0);
7705 if( consdata->capacity < minweightsum + consdata->onesweightsum )
7707 SCIPdebugMsg(scip,
" -> cutoff - fixed weight: %" SCIP_LONGINT_FORMAT
", capacity: %" SCIP_LONGINT_FORMAT
" \n",
7708 consdata->onesweightsum, consdata->capacity);
7723 for( i = 0; i < nvars && weight <= consdata->capacity; i++ )
7728 weight += consdata->weights[i];
7739 if( !usenegatedclique )
7741 assert(consdata->sorted);
7742 residualcapacity = consdata->capacity - consdata->onesweightsum;
7745 for( i = 0; i < nvars && consdata->weights[i] > residualcapacity; ++i )
7754 assert(consdata->onesweightsum + consdata->weights[i] > consdata->capacity);
7758 assert(!infeasible);
7769 SCIP_Longint unfixedweightsum = consdata->onesweightsum;
7772 for( i = 0; i <
nvars; ++i )
7776 unfixedweightsum += consdata->weights[i];
7779 if( unfixedweightsum > consdata->capacity )
7784 SCIPdebugMsg(scip,
" -> knapsack constraint <%s> is redundant: weightsum=%" SCIP_LONGINT_FORMAT
", unfixedweightsum=%" SCIP_LONGINT_FORMAT
", capacity=%" SCIP_LONGINT_FORMAT
"\n",
7785 SCIPconsGetName(cons), consdata->weightsum, unfixedweightsum, consdata->capacity);
7807 assert(scip != NULL);
7808 assert(cons != NULL);
7809 assert(ndelconss != NULL);
7810 assert(naddconss != NULL);
7813 assert(consdata != NULL);
7814 assert(consdata->nvars > 1);
7817 if( consdata->nvars == 2 )
7889 assert(scip != NULL);
7890 assert(cons != NULL);
7891 assert(nchgcoefs != NULL);
7892 assert(nchgsides != NULL);
7893 assert(naddconss != NULL);
7896 assert(consdata != NULL);
7897 assert(0 < frontsum && frontsum < consdata->weightsum);
7898 assert(0 < splitpos && splitpos < consdata->nvars);
7901 assert(conshdlrdata != NULL);
7903 vars = consdata->vars;
7904 weights = consdata->weights;
7905 nvars = consdata->nvars;
7906 capacity = consdata->capacity;
7912 for( w = nvars - 1; w > 0; --w )
7913 assert(weights[w] <= weights[w-1]);
7917 if( consdata->nvars - 1 == splitpos )
7920 assert(frontsum + weights[splitpos] > capacity);
7923 if( consdata->weightsum - weights[splitpos] <= capacity )
7931 for( w = nvars - 1; w > splitpos; --w )
7933 consdata->capacity -= weights[w];
7936 assert(w == splitpos);
7939 *nchgcoefs += (nvars - splitpos);
7943 for( ; w >= 0 && gcd > 1; --w )
7951 for( w = splitpos; w >= 0; --w )
7955 (*nchgcoefs) +=
nvars;
7957 consdata->capacity /= gcd;
7965 for( w = consdata->nvars - 1; w > 0; --w )
7966 assert(weights[w] <= weights[w - 1]);
7973 else if( conshdlrdata->disaggregation && frontsum + weights[splitpos + 1] <= capacity )
7979 len = nvars - (splitpos + 1);
7996 for( w = 0; w < len; ++w )
7998 assert(clqpart[w] >= 0 && clqpart[w] <= w);
7999 if( clqpart[w] == cliquenum )
8001 maxactduetoclq += weights[w + splitpos + 1];
8009 if( frontsum + maxactduetoclq <= capacity )
8015 assert(maxactduetoclq < weights[splitpos]);
8022 for( c = 0; c < nclq; ++c )
8025 for( w = 0; w < len; ++w )
8027 if( clqpart[w] == c )
8029 clqvars[nclqvars] = vars[w + splitpos + 1];
8055 for( w = nvars - 1; w > splitpos; --w )
8060 consdata->capacity -= maxactduetoclq;
8061 assert(frontsum <= consdata->capacity);
8064 assert(w == splitpos);
8067 weights = consdata->weights;
8071 for( ; w >= 0 && gcd > 1; --w )
8079 for( w = splitpos; w >= 0; --w )
8083 (*nchgcoefs) +=
nvars;
8085 consdata->capacity /= gcd;
8096 for( w = consdata->nvars - 1; w > 0; --w )
8097 assert(weights[w] <= weights[w - 1]);
8140 assert(scip != NULL);
8141 assert(cons != NULL);
8142 assert(ndelconss != NULL);
8143 assert(nchgcoefs != NULL);
8144 assert(nchgsides != NULL);
8145 assert(naddconss != NULL);
8148 assert(consdata != NULL);
8149 assert(consdata->nvars >= 2);
8150 assert(consdata->weightsum > consdata->capacity);
8152 noldchgcoefs = *nchgcoefs;
8153 vars = consdata->vars;
8154 weights = consdata->weights;
8155 nvars = consdata->nvars;
8156 capacity = consdata->capacity;
8160 for( v = 0; v < nvars && sum + weights[v] <= capacity; ++v )
8166 if( v == nvars - 1 )
8178 assert(consdata->nvars > 1);
8181 if( v == consdata->nvars - 1 )
8191 if( *nchgcoefs > noldchgcoefs )
8194 assert(vars == consdata->vars);
8195 assert(weights == consdata->weights);
8196 assert(nvars == consdata->nvars);
8197 assert(capacity == consdata->capacity);
8200 assert(conshdlrdata != NULL);
8205 if( consdata->cliquepartition[v] < v )
8214 maxactduetoclqfront = 0;
8216 clqpart = consdata->cliquepartition;
8220 for( w = 0; w <
nvars; ++w )
8222 assert(clqpart[w] >= 0 && clqpart[w] <= w);
8223 if( clqpart[w] == cliquenum )
8225 if( maxactduetoclqfront + weights[w] <= capacity )
8227 maxactduetoclqfront += weights[w];
8233 sumfront += weights[w];
8240 if( conshdlrdata->disaggregation && w == nvars )
8247 assert(maxactduetoclqfront <= capacity);
8251 ncliques = consdata->ncliques;
8256 for( c = 0; c < ncliques; ++c )
8259 for( w = 0; w <
nvars; ++w )
8261 if( clqpart[w] == c )
8263 clqvars[nclqvars] = vars[w];
8297 if( w > v && w < nvars - 1 )
8319 assert(nchgcoefs != NULL);
8320 assert(nchgsides != NULL);
8324 assert(consdata != NULL);
8325 assert(consdata->row == NULL);
8326 assert(consdata->onesweightsum == 0);
8327 assert(consdata->weightsum > consdata->capacity);
8328 assert(consdata->nvars >= 1);
8333 gcd = consdata->weights[consdata->nvars-1];
8334 for( i = consdata->nvars-2; i >= 0 && gcd >= 2; --i )
8346 for( i = 0; i < consdata->nvars; ++i )
8350 consdata->capacity /= gcd;
8351 (*nchgcoefs) += consdata->nvars;
8356 for( i = consdata->nvars - 1; i > 0; --i )
8357 assert(consdata->weights[i] <= consdata->weights[i - 1]);
8359 consdata->sorted =
TRUE;
8407 assert(scip != NULL);
8408 assert(cons != NULL);
8409 assert(ndelconss != NULL);
8410 assert(nchgcoefs != NULL);
8411 assert(nchgsides != NULL);
8412 assert(naddconss != NULL);
8415 oldnchgsides = *nchgsides;
8419 assert(consdata != NULL);
8420 assert(consdata->weightsum > consdata->capacity);
8421 assert(consdata->nvars >= 2);
8422 assert(consdata->sorted);
8425 assert(consdata->merged);
8427 nvars = consdata->nvars;
8428 weights = consdata->weights;
8429 capacity = consdata->capacity;
8431 oldnchgcoefs = *nchgcoefs;
8434 if( weights[nvars - 1] + weights[nvars - 2] > capacity )
8461 if( consdata->weightsum - weights[nvars - 1] <= consdata->capacity )
8471 if( consdata->weightsum - capacity > weights[0] + weights[1] )
8492 while( v < nvars && weights[v] + weights[nvars - 1] > capacity )
8496 assert(vbig < nvars - 1);
8500 while( v < nvars && exceedsum <= capacity )
8502 exceedsum += weights[v];
8507 if( exceedsum > capacity )
8509 assert(vbig > 0 || v < nvars);
8515 assert(newweight > 0);
8518 for( v = 0; v < vbig; ++v )
8520 if( weights[v] > newweight )
8528 for( ; v <
nvars; ++v )
8530 if( weights[v] > 1 )
8537 consdata->capacity = newweight;
8543 for( v = nvars - 1; v > 0; --v )
8544 assert(weights[v] <= weights[v-1]);
8555 int nexceed = v - vbig;
8557 assert(nexceed > 1);
8560 for( w = nvars - 1; w >= nvars - nexceed; --w )
8561 exceedsumback += weights[w];
8568 if( exceedsumback > capacity )
8573 assert(exceedsumback - weights[nvars - 1] <= capacity);
8576 for( v = 0; v < vbig; ++v )
8578 if( weights[v] > newweight )
8586 for( ; v <
nvars; ++v )
8588 if( weights[v] > 1 )
8595 consdata->capacity = newweight;
8601 for( v = nvars - 1; v > 0; --v )
8602 assert(weights[v] <= weights[v-1]);
8613 assert(vbig > 0 && vbig < nvars);
8625 if( weights[vbig - 1] > (
SCIP_Longint)nvars - vbig || weights[vbig] > 1 )
8631 for( v = 0; v < vbig; ++v )
8632 resweightsum -= weights[v];
8634 assert(exceedsum == resweightsum);
8636 assert(newweight > 0);
8639 for( v = 0; v < vbig; ++v )
8641 if( weights[v] > newweight )
8649 for( ; v <
nvars; ++v )
8651 if( weights[v] > 1 )
8658 consdata->capacity = newweight;
8664 for( v = nvars - 1; v > 0; --v )
8665 assert(weights[v] <= weights[v-1]);
8673 dualcapacity = consdata->weightsum - capacity;
8683 while( weights[v] > dualcapacity )
8685 reductionsum += (weights[v] - dualcapacity);
8693 while( v < nvars && weights[v] == dualcapacity )
8701 if( v >= nvars - 1 )
8704 if( v == nvars - 1 )
8717 if( weights[nvars - 1] + weights[nvars - 2] >= dualcapacity )
8731 if( v > 0 && weights[nvars - 2] > 1 )
8736 for( w = 0; w < v; ++w )
8738 if( weights[w] > 2 )
8745 assert(weights[0] == 2);
8746 assert(weights[v - 1] == 2);
8752 for( w = v; w <
nvars; ++w )
8754 if( weights[w] > 1 )
8760 assert(ncoefchg > 0);
8762 (*nchgcoefs) += ncoefchg;
8765 consdata->capacity = (-2 + v * 2 + nvars - v);
8766 assert(consdata->capacity > 0);
8767 assert(weights[0] <= consdata->capacity);
8768 assert(consdata->weightsum > consdata->capacity);
8774 assert(weights[nvars - 2] == 1);
8788 assert(weights[nvars - 1] + weights[nvars - 2] <= capacity);
8796 while( weights[v] > newweight )
8798 reductionsum += (weights[v] - newweight);
8803 (*nchgcoefs) += (v - startv);
8806 while( weights[v] == newweight )
8811 for( w = v; w <
nvars; ++w )
8812 restsumweights += weights[w];
8815 restsumweights = consdata->weightsum;
8817 if( restsumweights < dualcapacity )
8827 for( w = nvars - 1; w >= v; --w )
8835 for( ; w >= 0; --w )
8836 assert(weights[w] == dualcapacity);
8854 if( weights[v] > 1 || (weights[startv] > (
SCIP_Longint)nvars - v) || (startv > 0 && weights[0] == (
SCIP_Longint)nvars - v + 1) )
8859 for( w = nvars - 1; w >= v; --w )
8861 if( weights[w] > 1 )
8872 assert(newweight > 1);
8873 for( ; w >= startv; --w )
8875 if( weights[w] > newweight )
8881 assert(weights[w] == newweight);
8886 assert(newweight > 2);
8887 for( ; w >= 0; --w )
8889 if( weights[w] > newweight )
8895 assert(weights[w] == newweight);
8900 if( consdata->capacity > newcap )
8902 consdata->capacity = newcap;
8906 assert(consdata->capacity == newcap);
8908 assert(weights[v] == 1 && (weights[startv] == (
SCIP_Longint)nvars - v) && (startv == 0 || weights[0] == (
SCIP_Longint)nvars - v + 1));
8911 assert(consdata->weightsum - consdata->capacity == (
SCIP_Longint)nvars - v + 1);
8917 for( w = nvars - 1; w > 0; --w )
8918 assert(weights[w] <= weights[w - 1]);
8925 while( end >= 0 && weights[end] == weights[end + 1] )
8937 if( 2 * weights[end] > dualcapacity )
8942 for( w = end + 1; w <
nvars; ++w )
8943 restsumweights += weights[w];
8945 if( restsumweights * 2 <= dualcapacity )
8948 while( v < end && restsumweights + weights[v] >= dualcapacity )
8955 if( (dualcapacity & 1) == 0 )
8957 newweight = dualcapacity / 2;
8960 for( ; v <= end; ++v )
8962 if( weights[v] > newweight )
8964 reductionsum += (weights[v] - newweight);
8979 for( w = 0; w < v; ++w )
8984 newweight = dualcapacity;
8986 for( ; v <= end; ++v )
8988 reductionsum += (2 * weights[v] - newweight);
8993 for( w = end + 1; w <
nvars; ++w )
8997 (*nchgcoefs) +=
nvars;
9000 consdata->capacity *= 2;
9015 for( k = 0; k < 4; ++k )
9021 sumcoef = weights[nvars - 1] + weights[nvars - 2];
9025 sumcoef = weights[nvars - 1] + weights[nvars - 3];
9029 if( weights[nvars - 1] + weights[nvars - 4] < weights[nvars - 2] + weights[nvars - 3] )
9032 sumcoef = weights[nvars - 1] + weights[nvars - 4];
9036 sumcoefcase =
FALSE;
9037 sumcoef = weights[nvars - 2] + weights[nvars - 3];
9044 sumcoef = MIN(weights[nvars - 1] + weights[nvars - 5], weights[nvars - 2] + weights[nvars - 3]);
9048 sumcoef = MIN(weights[nvars - 1] + weights[nvars - 4], weights[nvars - 1] + weights[nvars - 2] + weights[nvars - 3]);
9056 minweight = weights[end];
9057 while( minweight <= sumcoef )
9059 newweight = dualcapacity - minweight;
9065 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9067 reductionsum += (weights[v] - newweight);
9072 (*nchgcoefs) += (v - startv);
9075 while( weights[v] + minweight == dualcapacity )
9083 while( end >= 0 && weights[end] == weights[end + 1] )
9089 minweight = weights[end];
9096 if( sumcoef < minweight )
9098 minweight = sumcoef;
9099 newweight = dualcapacity - minweight;
9104 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9106 reductionsum += (weights[v] - newweight);
9111 (*nchgcoefs) += (v - startv);
9114 while( weights[v] + minweight == dualcapacity )
9125 if( 2 * weights[end] > dualcapacity )
9130 for( w = end + 1; w <
nvars; ++w )
9131 restsumweights += weights[w];
9133 if( restsumweights * 2 <= dualcapacity )
9136 while( v < end && restsumweights + weights[v] >= dualcapacity )
9143 if( (dualcapacity & 1) == 0 )
9145 newweight = dualcapacity / 2;
9148 for( ; v <= end; ++v )
9150 if( weights[v] > newweight )
9152 reductionsum += (weights[v] - newweight);
9167 for( w = 0; w < v; ++w )
9172 newweight = dualcapacity;
9174 for( ; v <= end; ++v )
9176 reductionsum += (2 * weights[v] - newweight);
9181 for( w = end + 1; w <
nvars; ++w )
9185 (*nchgcoefs) +=
nvars;
9188 consdata->capacity *= 2;
9197 if( 2 * sumcoef > dualcapacity )
9206 if( reductionsum > 0 )
9210 consdata->capacity -= reductionsum;
9213 assert(consdata->weightsum - dualcapacity == consdata->capacity);
9215 assert(weights[0] <= consdata->capacity);
9221 for( w = nvars - 1; w > 0; --w )
9222 assert(weights[w] <= weights[w - 1]);
9225 if( oldnchgcoefs < *nchgcoefs )
9234 assert(oldnchgcoefs == *nchgcoefs);
9235 assert(oldnchgsides == *nchgsides);
9261 assert(scip != NULL);
9262 assert(cons != NULL);
9263 assert(nfixedvars != NULL);
9264 assert(ndelconss != NULL);
9265 assert(nchgcoefs != NULL);
9268 assert(consdata != NULL);
9270 nvars = consdata->nvars;
9275 assert(consdata->capacity >= 0);
9286 vars = consdata->vars;
9287 weights = consdata->weights;
9288 capacity = consdata->capacity;
9292 while( v < nvars && weights[v] > capacity )
9295 assert(!infeasible);
9315 for( --v; v >= 0; --v )
9323 assert(vars == consdata->vars);
9324 assert(weights == consdata->weights);
9326 assert(consdata->sorted);
9327 assert(weights[0] <= capacity);
9389 assert(scip != NULL);
9390 assert(cons != NULL);
9391 assert(nfixedvars != NULL);
9392 assert(ndelconss != NULL);
9393 assert(nchgcoefs != NULL);
9394 assert(nchgsides != NULL);
9395 assert(naddconss != NULL);
9396 assert(cutoff != NULL);
9400 assert( consdata != NULL );
9406 assert(consdata->merged);
9410 assert(consdata->capacity >= 0);
9432 weights = consdata->weights;
9433 nvars = consdata->nvars;
9437 for( v = nvars - 1; v > 0; --v )
9438 assert(weights[v] <= weights[v-1]);
9442 gcd = weights[nvars - 1];
9443 for( v = nvars - 2; v >= 0 && gcd > 1; --v )
9451 for( v = nvars - 1; v >= 0; --v )
9455 (*nchgcoefs) +=
nvars;
9457 consdata->capacity /= gcd;
9460 assert(consdata->nvars == nvars);
9466 for( v = nvars - 1; v > 0; --v )
9467 assert(weights[v] <= weights[v-1]);
9476 vars = consdata->vars;
9477 weights = consdata->weights;
9478 nvars = consdata->nvars;
9481 if( weights[nvars - 1] == 1 && weights[nvars - 2] == 1 )
9488 while( weights[v] == consdata->capacity )
9495 if( v == nvars - 1 )
9507 for( v = nvars - 1; v >= offsetv; --v )
9509 weight = weights[v];
9510 assert(weight >= 1);
9537 if( v == nvars - 2 )
9543 if( candpos == v + 1 && candpos2 == v + 2 )
9545 assert(candpos2 == nvars - 1);
9570 assert(((candpos >= offsetv) || (candpos == -1 && offsetv > 0)) && candpos < nvars);
9573 rest = consdata->capacity % gcd;
9583 consdata->capacity -= rest;
9587 for( v = 0; v < offsetv; ++v )
9592 *nchgcoefs += offsetv;
9597 restweight = weights[candpos] % gcd;
9598 assert(restweight >= 1);
9599 assert(restweight < gcd);
9602 if( restweight > rest )
9603 newweight = weights[candpos] - restweight + gcd;
9605 newweight = weights[candpos] - restweight;
9609 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);
9614 if( newweight == 0 && offsetv > 0 )
9620 consdata->capacity -= rest;
9624 for( v = 0; v < offsetv; ++v )
9629 *nchgcoefs += offsetv;
9632 if( newweight == 0 )
9636 assert(consdata->nvars == nvars - 1);
9646 assert(consdata->vars == vars);
9647 assert(consdata->nvars == nvars);
9648 assert(consdata->weights == weights);
9652 for( v = nvars - 1; v >= 0; --v )
9656 (*nchgcoefs) +=
nvars;
9658 consdata->capacity /= gcd;
9663 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));
9665 while( nvars >= 2 );
9692 assert(liftcands != NULL);
9693 assert(liftcands[value] != NULL);
9694 assert(nliftcands != NULL);
9695 assert(firstidxs != NULL);
9696 assert(firstidxs[value] != NULL);
9697 assert(zeroweightsums != NULL);
9698 assert(zeroweightsums[value] != NULL);
9699 assert(zeroitems != NULL);
9700 assert(nextidxs != NULL);
9701 assert(zeroitemssize != NULL);
9702 assert(nzeroitems != NULL);
9703 assert(*nzeroitems <= *zeroitemssize);
9705 assert(memlimitreached != NULL);
9707 nzeros = *nzeroitems;
9710 if( nzeros == *zeroitemssize )
9717 SCIPdebugMsg(scip,
"memory limit of %d bytes reached in knapsack preprocessing - abort collecting zero items\n",
9719 *memlimitreached =
TRUE;
9722 *zeroitemssize *= 2;
9727 assert(nzeros < *zeroitemssize);
9729 if( *memlimitreached )
9730 *memlimitreached =
FALSE;
9733 (*zeroitems)[nzeros] = knapsackidx;
9734 (*nextidxs)[nzeros] = firstidxs[value][probindex];
9735 if( firstidxs[value][probindex] == 0 )
9737 liftcands[value][nliftcands[value]] = probindex;
9738 ++nliftcands[value];
9740 firstidxs[value][probindex] = nzeros;
9742 zeroweightsums[value][probindex] += knapsackweight;
9747 #define MAX_CLIQUELENGTH 50 9803 assert(nchgcoefs != NULL);
9807 assert(consdata != NULL);
9808 assert(consdata->row == NULL);
9809 assert(consdata->weightsum > consdata->capacity);
9810 assert(consdata->nvars > 0);
9811 assert(consdata->merged);
9813 nvars = consdata->nvars;
9827 assert(nbinvars > 0);
9832 assert(conshdlr != NULL);
9834 assert(conshdlrdata != NULL);
9841 assert(conshdlrdata->ints1size > 0);
9842 assert(conshdlrdata->ints2size > 0);
9843 assert(conshdlrdata->longints1size > 0);
9844 assert(conshdlrdata->longints2size > 0);
9850 if( conshdlrdata->ints1size < nbinvars )
9852 int oldsize = conshdlrdata->ints1size;
9854 conshdlrdata->ints1size = nbinvars;
9858 if( conshdlrdata->ints2size < nbinvars )
9860 int oldsize = conshdlrdata->ints2size;
9862 conshdlrdata->ints2size = nbinvars;
9866 if( conshdlrdata->longints1size < nbinvars )
9868 int oldsize = conshdlrdata->longints1size;
9870 conshdlrdata->longints1size = nbinvars;
9872 BMSclearMemoryArray(&(conshdlrdata->longints1[oldsize]), conshdlrdata->longints1size - oldsize);
9874 if( conshdlrdata->longints2size < nbinvars )
9876 int oldsize = conshdlrdata->longints2size;
9878 conshdlrdata->longints2size = nbinvars;
9880 BMSclearMemoryArray(&(conshdlrdata->longints2[oldsize]), conshdlrdata->longints2size - oldsize);
9883 firstidxs[0] = conshdlrdata->ints1;
9884 firstidxs[1] = conshdlrdata->ints2;
9885 zeroweightsums[0] = conshdlrdata->longints1;
9886 zeroweightsums[1] = conshdlrdata->longints2;
9890 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
9892 assert(firstidxs[0][tmp] == 0);
9893 assert(firstidxs[1][tmp] == 0);
9894 assert(zeroweightsums[0][tmp] == 0);
9895 assert(zeroweightsums[1][tmp] == 0);
9908 assert(conshdlrdata->bools1size > 0);
9909 assert(conshdlrdata->bools2size > 0);
9915 if( conshdlrdata->bools1size < nbinvars )
9917 int oldsize = conshdlrdata->bools1size;
9919 conshdlrdata->bools1size = nbinvars;
9921 BMSclearMemoryArray(&(conshdlrdata->bools1[oldsize]), conshdlrdata->bools1size - oldsize);
9923 if( conshdlrdata->bools2size < nbinvars )
9925 int oldsize = conshdlrdata->bools2size;
9927 conshdlrdata->bools2size = nbinvars;
9929 BMSclearMemoryArray(&(conshdlrdata->bools2[oldsize]), conshdlrdata->bools2size - oldsize);
9932 zeroiteminserted[0] = conshdlrdata->bools1;
9933 zeroiteminserted[1] = conshdlrdata->bools2;
9937 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
9939 assert(zeroiteminserted[0][tmp] == 0);
9940 assert(zeroiteminserted[1][tmp] == 0);
9953 memlimitreached =
FALSE;
9954 for( i = 0; i < consdata->nvars && !memlimitreached; ++i )
9967 var = consdata->vars[i];
9968 weight = consdata->weights[i];
9972 assert(0 <= varprobindex && varprobindex < nbinvars);
9975 zeroweightsums[!value][varprobindex] += weight;
9976 tmpboolindices3[tmp3] = !value;
9977 tmpindices3[tmp3] = varprobindex;
9987 assert(0 <= probindex && probindex < nbinvars);
9992 assert( !zeroiteminserted[implvalue][probindex] );
9994 if( firstidxs[implvalue][probindex] == 0 )
9996 tmpboolindices2[tmp2] = implvalue;
9997 tmpindices2[tmp2] = probindex;
10001 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue, i, weight,
10002 &memlimitreached) );
10003 zeroiteminserted[implvalue][probindex] =
TRUE;
10004 tmpboolindices[tmp] = implvalue;
10005 tmpindices[tmp] = probindex;
10012 for( j = 0; j < ncliques && !memlimitreached; ++j )
10028 for( k = ncliquevars - 1; k >= 0; --k )
10033 if( var == cliquevars[k] )
10037 if( probindex == -1 )
10040 assert(0 <= probindex && probindex < nbinvars);
10041 implvalue = cliquevalues[k];
10044 if( !zeroiteminserted[implvalue][probindex] )
10046 if( firstidxs[implvalue][probindex] == 0 )
10048 tmpboolindices2[tmp2] = implvalue;
10049 tmpindices2[tmp2] = probindex;
10054 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue, i, weight,
10055 &memlimitreached) );
10056 zeroiteminserted[implvalue][probindex] =
TRUE;
10057 tmpboolindices[tmp] = implvalue;
10058 tmpindices[tmp] = probindex;
10061 if( memlimitreached )
10067 for( --tmp; tmp >= 0; --tmp)
10068 zeroiteminserted[tmpboolindices[tmp]][tmpindices[tmp]] =
FALSE;
10073 assert(consdata->sorted);
10076 assert(conshdlrdata->bools3size > 0);
10082 if( conshdlrdata->bools3size < consdata->nvars )
10084 int oldsize = conshdlrdata->bools3size;
10086 conshdlrdata->bools3size = consdata->nvars;;
10088 BMSclearMemoryArray(&(conshdlrdata->bools3[oldsize]), conshdlrdata->bools3size - oldsize);
10091 cliqueused = conshdlrdata->bools3;
10095 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10096 assert(cliqueused[tmp] == 0);
10099 maxcliqueweightsum = 0;
10103 for( i = 0; i < consdata->nvars; ++i )
10105 cliquenum = consdata->cliquepartition[i];
10106 assert(0 <= cliquenum && cliquenum < consdata->nvars);
10108 if( !cliqueused[cliquenum] )
10110 maxcliqueweightsum += consdata->weights[i];
10111 cliqueused[cliquenum] =
TRUE;
10112 tmpindices[tmp] = cliquenum;
10117 for( --tmp; tmp >= 0; --tmp)
10118 cliqueused[tmp] =
FALSE;
10120 assert(conshdlrdata->bools4size > 0);
10126 if( conshdlrdata->bools4size < consdata->nvars )
10128 int oldsize = conshdlrdata->bools4size;
10130 conshdlrdata->bools4size = consdata->nvars;
10135 itemremoved = conshdlrdata->bools4;
10139 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10140 assert(itemremoved[tmp] == 0);
10151 for( val = 0; val < 2 && addweightsum < consdata->capacity; ++val )
10153 for( i = 0; i < nliftcands[val] && addweightsum < consdata->capacity; ++i )
10162 probindex = liftcands[val][i];
10163 assert(0 <= probindex && probindex < nbinvars);
10166 if( firstidxs[val][probindex] == 0
10167 || maxcliqueweightsum - zeroweightsums[val][probindex] + addweightsum >= consdata->capacity )
10171 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10173 assert(0 < idx && idx < nzeroitems);
10174 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10175 itemremoved[zeroitems[idx]] =
TRUE;
10179 cliqueweightsum = addweightsum;
10180 for( j = 0; j < consdata->nvars; ++j )
10182 cliquenum = consdata->cliquepartition[j];
10183 assert(0 <= cliquenum && cliquenum < consdata->nvars);
10184 if( !itemremoved[j] )
10186 if( !cliqueused[cliquenum] )
10188 cliqueweightsum += consdata->weights[j];
10189 cliqueused[cliquenum] =
TRUE;
10190 tmpindices[tmp] = cliquenum;
10194 if( cliqueweightsum >= consdata->capacity )
10200 if( cliqueweightsum < consdata->capacity )
10206 assert(naddvars < 2*nbinvars);
10207 var = binvars[probindex];
10212 weight = consdata->capacity - cliqueweightsum;
10213 addvars[naddvars] = var;
10214 addweights[naddvars] = weight;
10215 addweightsum += weight;
10218 SCIPdebugMsg(scip,
"knapsack constraint <%s>: adding lifted item %" SCIP_LONGINT_FORMAT
"<%s>\n",
10223 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10225 assert(0 < idx && idx < nzeroitems);
10226 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10227 itemremoved[zeroitems[idx]] =
FALSE;
10230 for( --tmp; tmp >= 0; --tmp)
10231 cliqueused[tmpindices[tmp]] =
FALSE;
10237 for( --tmp3; tmp3 >= 0; --tmp3)
10238 zeroweightsums[tmpboolindices3[tmp3]][tmpindices3[tmp3]] = 0;
10241 for( --tmp2; tmp2 >= 0; --tmp2)
10243 zeroweightsums[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10244 firstidxs[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10253 for( i = 0; i < naddvars; ++i )
10257 *nchgcoefs += naddvars;
10350 assert(nchgcoefs != NULL);
10351 assert(nchgsides != NULL);
10355 assert(conshdlrdata != NULL);
10358 assert(consdata != NULL);
10359 assert(consdata->row == NULL);
10360 assert(consdata->onesweightsum == 0);
10361 assert(consdata->weightsum > consdata->capacity);
10362 assert(consdata->nvars > 0);
10373 assert(consdata->merged);
10378 for( i = 0; i < consdata->nvars; ++i )
10382 weight = consdata->weights[i];
10383 if( consdata->weightsum - weight < consdata->capacity )
10385 newweight = consdata->weightsum - consdata->capacity;
10387 consdata->capacity -= (weight - newweight);
10390 assert(!consdata->sorted);
10391 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",
10393 consdata->capacity + (weight-newweight), consdata->capacity);
10399 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10403 if( consdata->weightsum <= consdata->capacity )
10407 while( pos < consdata->nvars && consdata->weights[pos] == consdata->capacity )
10411 weights = consdata->weights;
10412 nvars = consdata->nvars;
10413 capacity = consdata->capacity;
10416 pos < nvars && weights[pos] + weights[pos + 1] > capacity )
10423 for( k = 0; k < 4; ++k )
10425 newweight = capacity - sumcoef;
10431 sumcoef = weights[nvars - 1];
10432 backpos = nvars - 1;
10435 sumcoef = weights[nvars - 2];
10436 backpos = nvars - 2;
10439 if( weights[nvars - 3] < weights[nvars - 1] + weights[nvars - 2] )
10441 sumcoefcase =
TRUE;
10442 sumcoef = weights[nvars - 3];
10443 backpos = nvars - 3;
10447 sumcoefcase =
FALSE;
10448 sumcoef = weights[nvars - 1] + weights[nvars - 2];
10449 backpos = nvars - 2;
10456 if( weights[nvars - 4] < weights[nvars - 1] + weights[nvars - 2] )
10458 sumcoef = weights[nvars - 4];
10459 backpos = nvars - 4;
10463 sumcoef = weights[nvars - 1] + weights[nvars - 2];
10464 backpos = nvars - 2;
10469 sumcoef = weights[nvars - 3];
10470 backpos = nvars - 3;
10475 if( backpos <= pos )
10479 maxweight = weights[pos];
10481 while( 2 * maxweight > capacity && maxweight + sumcoef > capacity )
10483 assert(newweight > weights[pos]);
10485 SCIPdebugMsg(scip,
"in constraint <%s> changing weight %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10491 assert(pos < nvars);
10493 maxweight = weights[pos];
10495 if( backpos <= pos )
10498 (*nchgcoefs) += (pos - startpos);
10501 while( pos < nvars && weights[pos] + sumcoef == capacity )
10512 if( pos + 1 == backpos && weights[pos] > sumcoef &&
10513 ((k == 0) || (k == 1 && weights[nvars - 1] + sumcoef + weights[pos] > capacity)) )
10515 newweight = capacity - sumcoef;
10516 assert(newweight > weights[pos]);
10518 SCIPdebugMsg(scip,
"in constraint <%s> changing weight %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10526 if( backpos <= pos )
10534 if( conshdlrdata->disaggregation && consdata->nvars - pos <= MAX_USECLIQUES_SIZE && consdata->nvars >= 2 &&
10535 pos > 0 && (
SCIP_Longint)consdata->nvars - pos <= consdata->capacity &&
10536 consdata->weights[pos - 1] == consdata->capacity && (pos == consdata->nvars || consdata->weights[pos] == 1) )
10550 if( pos == consdata->nvars )
10571 len = consdata->nvars - pos;
10578 assert(nclq <= len);
10582 for( w = 0; w < nclq; ++w )
10583 assert(clqpart[w] <= w);
10592 for( w = pos - 1; w >= 0; --w )
10593 clqvars[w] = consdata->vars[w];
10596 for( c = 0; c < nclq; ++c )
10600 for( w = c; w < len; ++w )
10602 if( clqpart[w] == c )
10604 assert(nclqvars < pos + len - nclq + 1);
10605 clqvars[nclqvars] = consdata->vars[w + pos];
10610 assert(nclqvars > 1);
10638 int* newweightidxs;
10652 assert(consdata->merged);
10661 if( consdata->cliquepartition[consdata->nvars - 1] == consdata->nvars - 1 )
10665 cliqueweightsum = 0;
10668 for( i = 0; i < consdata->nvars; ++i )
10672 cliquenum = consdata->cliquepartition[i];
10673 assert(0 <= cliquenum && cliquenum <= ncliques);
10675 weight = consdata->weights[i];
10676 assert(weight > 0);
10678 if( cliquenum == ncliques )
10680 maxcliqueweights[ncliques] = weight;
10681 cliqueweightsum += weight;
10685 assert(maxcliqueweights[cliquenum] >= weight);
10689 zeroweights =
FALSE;
10690 for( i = 0; i < ncliques; ++i )
10694 delta = consdata->capacity - (cliqueweightsum - maxcliqueweights[i]);
10706 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",
10707 SCIPconsGetName(cons), i, maxcliqueweights[i], cliqueweightsum, consdata->capacity, delta);
10708 newcapacity = consdata->capacity - delta;
10709 forceclique =
FALSE;
10712 newmincliqueweight = newcapacity + 1;
10713 for( j = 0; j < i; ++j )
10714 assert(consdata->cliquepartition[j] < i);
10716 for( j = i; j < consdata->nvars; ++j )
10718 if( consdata->cliquepartition[j] == i )
10720 newweight = consdata->weights[j] - delta;
10721 newweight =
MAX(newweight, 0);
10724 assert(nnewweights < consdata->nvars);
10725 newweightvals[nnewweights] = newweight;
10726 newweightidxs[nnewweights] = j;
10730 assert(newweight <= newmincliqueweight);
10731 newmincliqueweight = newweight;
10737 if( nnewweights > 1 )
10740 j = newweightidxs[nnewweights - 2];
10741 assert(0 <= j && j < consdata->nvars);
10742 assert(consdata->cliquepartition[j] == i);
10743 j = newweightidxs[nnewweights - 1];
10744 assert(0 <= j && j < consdata->nvars);
10745 assert(consdata->cliquepartition[j] == i);
10748 newminweightsuminclique = newweightvals[nnewweights - 2];
10749 newminweightsuminclique += newweightvals[nnewweights - 1];
10756 if( newminweightsuminclique <= newcapacity )
10757 forceclique =
TRUE;
10761 if( conshdlrdata->disaggregation || !forceclique )
10763 SCIPdebugMsg(scip,
" -> change capacity from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
" (forceclique:%u)\n",
10764 consdata->capacity, newcapacity, forceclique);
10765 consdata->capacity = newcapacity;
10768 for( k = 0; k < nnewweights; ++k )
10770 j = newweightidxs[k];
10771 assert(0 <= j && j < consdata->nvars);
10772 assert(consdata->cliquepartition[j] == i);
10775 SCIPdebugMsg(scip,
" -> change weight of <%s> from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10776 SCIPvarGetName(consdata->vars[j]), consdata->weights[j], newweightvals[k]);
10779 assert(!consdata->sorted);
10780 zeroweights = zeroweights || (newweightvals[k] == 0);
10794 for( k = 0; k < nnewweights; ++k )
10795 cliquevars[k] = consdata->vars[newweightidxs[k]];
10818 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10826 if( consdata->weightsum <= consdata->capacity )
10838 if( consdata->weightsum <= consdata->capacity )
10841 if( (presoltiming & SCIP_PRESOLTIMING_FAST) != 0 )
10844 assert(consdata->merged);
10846 minweight = consdata->weights[consdata->nvars-1];
10847 for( i = 0; i < consdata->nvars-1; ++i )
10851 weight = consdata->weights[i];
10852 assert(weight >= minweight);
10853 if( minweight + weight > consdata->capacity )
10855 if( weight < consdata->capacity )
10857 SCIPdebugMsg(scip,
"knapsack constraint <%s>: changed weight of <%s> from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10859 assert(consdata->sorted);
10861 assert(i == 0 || consdata->weights[i-1] >= consdata->weights[i]);
10862 consdata->sorted =
TRUE;
10871 if( consdata->nvars >= 2 )
10875 minweight = consdata->weights[consdata->nvars-2];
10876 weight = consdata->weights[consdata->nvars-1];
10877 assert(minweight >= weight);
10878 if( minweight + weight > consdata->capacity && weight < consdata->capacity )
10880 SCIPdebugMsg(scip,
"knapsack constraint <%s>: changed weight of <%s> from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10882 assert(consdata->sorted);
10884 assert(minweight >= consdata->weights[consdata->nvars-1]);
10885 consdata->sorted =
TRUE;
10904 for( b = 0; b < ncliquevars; ++b )
10925 int* gaincliquepartition;
10931 int nposcliquevars;
10935 int lastcliqueused;
10940 assert(scip != NULL);
10941 assert(cons != NULL);
10942 assert(cutoff != NULL);
10943 assert(nbdchgs != NULL);
10948 assert(consdata != NULL);
10950 nvars = consdata->nvars;
10953 if( consdata->cliquesadded || nvars == 0 )
10964 assert(consdata->merged);
10967 assert(conshdlrdata != NULL);
10971 nnegcliques = consdata->nnegcliques;
10974 if( nnegcliques == nvars )
10988 minactduetonegcliques = 0;
10991 for( v = 0; v <
nvars; ++v )
10993 assert(0 <= consdata->negcliquepartition[v] && consdata->negcliquepartition[v] <= nnegcliques);
10994 assert(consdata->weights[v] > 0);
10996 if( consdata->negcliquepartition[v] == nnegcliques )
10999 maxweights[consdata->negcliquepartition[v]] = consdata->weights[v];
11002 minactduetonegcliques += consdata->weights[v];
11005 nposcliquevars = 0;
11008 if( minactduetonegcliques > 0 )
11011 freecapacity = consdata->capacity - minactduetonegcliques;
11014 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",
11015 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
11018 for( v = 0; v <
nvars; ++v )
11020 if( !cliqueused[consdata->negcliquepartition[v]] )
11022 cliqueused[consdata->negcliquepartition[v]] =
TRUE;
11023 for( w = v + 1; w <
nvars; ++w )
11027 if( consdata->negcliquepartition[v] == consdata->negcliquepartition[w]
11028 && consdata->weights[v] > consdata->weights[w] )
11030 poscliquevars[nposcliquevars] = consdata->vars[w];
11031 gainweights[nposcliquevars] = maxweights[consdata->negcliquepartition[v]] - consdata->weights[w];
11032 gaincliquepartition[nposcliquevars] = consdata->negcliquepartition[v];
11040 if( nposcliquevars > 0 )
11045 for( v = 0; v < nposcliquevars; ++v )
11049 lastweight = gainweights[v];
11050 beforelastweight = -1;
11051 lastcliqueused = gaincliquepartition[v];
11054 cliqueused[gaincliquepartition[v]] =
TRUE;
11058 for( w = v + 1; w < nposcliquevars && !cliqueused[gaincliquepartition[w]] && gainweights[w] + lastweight > freecapacity; ++w )
11060 beforelastweight = lastweight;
11061 lastweight = gainweights[w];
11062 lastcliqueused = gaincliquepartition[w];
11063 cliqueused[gaincliquepartition[w]] =
TRUE;
11068 if( ncliquevars > 1 )
11070 SCIPdebug( printClique(cliquevars, ncliquevars) );
11071 assert(beforelastweight > 0);
11077 *nbdchgs += thisnbdchgs;
11080 cliqueused[lastcliqueused] =
FALSE;
11083 for( ++w; w < nposcliquevars && !cliqueused[gaincliquepartition[w]] && beforelastweight + gainweights[w] > freecapacity; ++w )
11086 SCIPdebug( printClique(cliquevars, ncliquevars) );
11090 *nbdchgs += thisnbdchgs;
11137 if( ! sorteditems )
11141 lastweight = weights[0];
11144 for( i = 1; i < nitems && weights[i] + lastweight > capacity; ++i )
11146 lastweight = weights[i];
11150 if( ncliquevars > 1 )
11154 int compareweightidx;
11159 SCIPdebug( printClique(items, ncliquevars) );
11165 *nbdchgs += thisnbdchgs;
11166 nnzadded = ncliquevars;
11169 if( ncliquevars == nitems )
11177 compareweightidx = ncliquevars - 2;
11178 assert(i == nitems || weights[i] + weights[ncliquevars - 1] <= capacity);
11181 minclqsize = (int)(cliqueextractfactor * ncliquevars);
11182 minclqsize =
MAX(minclqsize, 2);
11186 while( compareweightidx >= 0 && i < nitems && ! (*cutoff)
11187 && ncliquevars >= minclqsize
11188 && nnzadded <= 2 * nitems
11191 compareweight = weights[compareweightidx];
11192 assert(compareweight > 0);
11195 if( compareweight + weights[i] > capacity )
11197 assert(compareweightidx == ncliquevars -2);
11198 cliquevars[ncliquevars - 1] = items[i];
11199 SCIPdebug( printClique(cliquevars, ncliquevars) );
11202 nnzadded += ncliquevars;
11206 *nbdchgs += thisnbdchgs;
11214 compareweightidx--;
11245 int nposcliquevars;
11249 assert(scip != NULL);
11250 assert(cons != NULL);
11251 assert(cutoff != NULL);
11252 assert(nbdchgs != NULL);
11257 assert(consdata != NULL);
11259 nvars = consdata->nvars;
11262 if( consdata->cliquesadded || nvars == 0 )
11273 assert(consdata->merged);
11276 assert(conshdlrdata != NULL);
11280 nnegcliques = consdata->nnegcliques;
11281 assert(nnegcliques <= nvars);
11290 minactduetonegcliques = 0;
11293 if( nnegcliques < nvars )
11297 for( i = 0; i <
nvars; ++i )
11301 cliquenum = consdata->negcliquepartition[i];
11302 assert(0 <= cliquenum && cliquenum <= nnegcliques);
11304 weight = consdata->weights[i];
11305 assert(weight > 0);
11307 if( cliquenum == nnegcliques )
11311 minactduetonegcliques += weight;
11312 if( secondmaxweights[cliquenum] == 0 )
11313 secondmaxweights[cliquenum] = weight;
11319 if( minactduetonegcliques > 0 )
11322 freecapacity = consdata->capacity - minactduetonegcliques;
11325 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",
11326 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
11334 nposcliquevars = 0;
11336 for( i = nvars - 1; i >= 0; --i )
11339 cliquenum = consdata->negcliquepartition[i];
11340 if( consdata->weights[i] > secondmaxweights[cliquenum] )
11342 poscliquevars[nposcliquevars] = consdata->vars[i];
11343 gainweights[nposcliquevars] = consdata->weights[i] - secondmaxweights[cliquenum];
11349 if( nposcliquevars > 1 )
11366 consdata->cliquesadded =
TRUE;
11395 assert(consdata1->sorted);
11396 assert(consdata2->sorted);
11398 scip = (
SCIP*)userptr;
11399 assert(scip != NULL);
11403 if( consdata1->nvars != consdata2->nvars )
11406 for( i = consdata1->nvars - 1; i >= 0; --i )
11409 if( consdata1->vars[i] != consdata2->vars[i] )
11411 assert(
SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
11415 assert(
SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 0);
11418 if( consdata1->weights[i] != consdata2->weights[i] )
11438 assert(consdata != NULL);
11439 assert(consdata->nvars > 0);
11442 scip = (
SCIP*)userptr;
11443 assert(scip != NULL);
11452 assert(minidx >= 0 && mididx >= 0 && maxidx >= 0);
11456 consdata->weights[0]);
11476 assert(scip != NULL);
11477 assert(blkmem != NULL);
11478 assert(conss != NULL);
11479 assert(ndelconss != NULL);
11482 hashtablesize = nconss;
11485 hashGetKeyKnapsackcons, hashKeyEqKnapsackcons, hashKeyValKnapsackcons, (
void*) scip) );
11488 for( c = nconss - 1; c >= 0; --c )
11500 assert(consdata0 != NULL);
11501 if( consdata0->nvars == 0 )
11503 if( consdata0->capacity < 0 )
11519 if( cons1 != NULL )
11533 assert(consdata1 != NULL);
11534 assert(consdata0->nvars > 0 && consdata0->nvars == consdata1->nvars);
11536 assert(consdata0->sorted && consdata1->sorted);
11537 assert(consdata0->vars[0] == consdata1->vars[0]);
11538 assert(consdata0->weights[0] == consdata1->weights[0]);
11540 SCIPdebugMsg(scip,
"knapsack constraints <%s> and <%s> with equal coefficients\n",
11544 if( consdata0->capacity < consdata1->capacity )
11599 assert(scip != NULL);
11600 assert(conss != NULL);
11601 assert(firstchange <= chkind);
11602 assert(ndelconss != NULL);
11605 cons0 = conss[chkind];
11606 assert(cons0 != NULL);
11611 assert(consdata0 != NULL);
11612 assert(consdata0->nvars >= 1);
11613 assert(consdata0->merged);
11631 assert(cons1 != NULL);
11636 assert(consdata1 != NULL);
11642 assert(consdata1->nvars >= 1);
11643 assert(consdata1->merged);
11650 if( consdata0->nvars > consdata1->nvars )
11652 iscons0incons1contained =
FALSE;
11653 iscons1incons0contained =
TRUE;
11654 v = consdata1->nvars - 1;
11656 else if( consdata0->nvars < consdata1->nvars )
11658 iscons0incons1contained =
TRUE;
11659 iscons1incons0contained =
FALSE;
11660 v = consdata0->nvars - 1;
11664 iscons0incons1contained =
TRUE;
11665 iscons1incons0contained =
TRUE;
11666 v = consdata0->nvars - 1;
11677 v0 = consdata0->nvars - 1;
11678 v1 = consdata1->nvars - 1;
11682 assert(iscons0incons1contained || iscons1incons0contained);
11687 iscons1incons0contained =
FALSE;
11688 if( !iscons0incons1contained )
11694 iscons0incons1contained =
FALSE;
11695 if( !iscons1incons0contained )
11699 assert(v == v0 || v == v1);
11704 if( consdata0->vars[v0] == consdata1->vars[v1] )
11707 if( iscons1incons0contained &&
SCIPisLT(scip, ((
SCIP_Real) consdata0->weights[v0]) / quotient, (
SCIP_Real) consdata1->weights[v1]) )
11709 iscons1incons0contained =
FALSE;
11710 if( !iscons0incons1contained )
11714 else if( iscons0incons1contained &&
SCIPisGT(scip, ((
SCIP_Real) consdata0->weights[v0]) / quotient, (
SCIP_Real) consdata1->weights[v1]) )
11716 iscons0incons1contained =
FALSE;
11717 if( !iscons1incons0contained )
11727 if( iscons0incons1contained && iscons1incons0contained )
11729 iscons0incons1contained =
FALSE;
11730 iscons1incons0contained =
FALSE;
11733 assert(iscons0incons1contained ? (v1 >= v0) : iscons1incons0contained);
11734 assert(iscons1incons0contained ? (v1 <= v0) : iscons0incons1contained);
11736 if( iscons0incons1contained )
11745 assert(!iscons1incons0contained || !iscons0incons1contained || v0 == -1 || v1 == -1);
11747 if( iscons1incons0contained )
11758 else if( iscons0incons1contained )
11796 SCIPdebugMsg(scip,
"knapsack enforcement of %d/%d constraints for %s solution\n", nusefulconss, nconss,
11797 sol == NULL ?
"LP" :
"relaxation");
11801 assert(conshdlrdata != NULL);
11802 maxncuts = (
SCIPgetDepth(scip) == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
11805 for( i = 0; i < nusefulconss && ncuts < maxncuts && ! cutoff; i++ )
11817 for( i = nusefulconss; i < nconss && ncuts == 0 && ! cutoff; i++ )
11831 else if ( ncuts > 0 )
11884 assert(nvars == 0 || vars != NULL);
11885 assert(nvars == 0 || vals != NULL);
11907 for( v = 0; v <
nvars; ++v )
11913 transvars[v] = vars[v];
11914 weights[v] = weight;
11919 weights[v] = -weight;
11920 capacity -= weight;
11922 assert(transvars[v] != NULL);
11927 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
11942 assert(upgdcons != NULL);
11949 upgrade = (nposbin + nnegbin + nposimplbin + nnegimplbin ==
nvars)
11950 && (ncoeffspone + ncoeffsnone + ncoeffspint + ncoeffsnint == nvars)
11979 assert(scip != NULL);
11980 assert(conshdlr != NULL);
12001 assert(conshdlrdata != NULL);
12019 assert( scip != NULL );
12020 assert( conshdlr != NULL );
12023 assert(conshdlrdata != NULL);
12029 conshdlrdata->reals1size =
nvars;
12040 assert( scip != NULL );
12041 assert( conshdlr != NULL );
12044 assert(conshdlrdata != NULL);
12047 conshdlrdata->reals1size = 0;
12060 assert(scip != NULL);
12061 assert(conshdlr != NULL);
12062 assert(nconss == 0 || conss != NULL);
12065 assert(conshdlrdata != NULL);
12079 conshdlrdata->ints1size =
nvars;
12080 conshdlrdata->ints2size =
nvars;
12081 conshdlrdata->longints1size =
nvars;
12082 conshdlrdata->longints2size =
nvars;
12083 conshdlrdata->bools1size =
nvars;
12084 conshdlrdata->bools2size =
nvars;
12085 conshdlrdata->bools3size =
nvars;
12086 conshdlrdata->bools4size =
nvars;
12088 #ifdef WITH_CARDINALITY_UPGRADE 12089 conshdlrdata->upgradedcard =
FALSE;
12103 assert(scip != NULL);
12104 assert(conshdlr != NULL);
12106 for( c = 0; c < nconss; ++c )
12116 assert(conshdlrdata != NULL);
12127 conshdlrdata->ints1size = 0;
12128 conshdlrdata->ints2size = 0;
12129 conshdlrdata->longints1size = 0;
12130 conshdlrdata->longints2size = 0;
12131 conshdlrdata->bools1size = 0;
12132 conshdlrdata->bools2size = 0;
12133 conshdlrdata->bools3size = 0;
12134 conshdlrdata->bools4size = 0;
12147 assert( scip != NULL );
12150 for( c = 0; c < nconss; ++c )
12153 assert(consdata != NULL);
12155 if( consdata->row != NULL )
12170 assert(conshdlr != NULL);
12175 assert(conshdlrdata != NULL);
12176 assert(conshdlrdata->eventhdlr != NULL);
12193 assert(conshdlr != NULL);
12196 assert(sourcecons != NULL);
12197 assert(targetcons != NULL);
12200 assert(sourcedata != NULL);
12201 assert(sourcedata->row == NULL);
12205 assert(conshdlrdata != NULL);
12206 assert(conshdlrdata->eventhdlr != NULL);
12210 sourcedata->nvars, sourcedata->vars, sourcedata->weights, sourcedata->capacity) );
12232 *infeasible =
FALSE;
12234 for( i = 0; i < nconss && !(*infeasible); i++ )
12267 assert(conshdlrdata != NULL);
12272 SCIPdebugMsg(scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12273 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12276 if( (depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12277 || (depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12282 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12283 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12284 && ((sepacardfreq == 0 && depth == 0) || (sepacardfreq >= 1 && (depth % sepacardfreq == 0)));
12290 maxbound = glblowerbound + conshdlrdata->maxcardbounddist * (cutoffbound - glblowerbound);
12291 sepacardinality = sepacardinality &&
SCIPisLE(scip, loclowerbound, maxbound);
12295 maxsepacuts = (depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12302 for( i = 0; i < nusefulconss && ncuts < maxsepacuts && !
SCIPisStopped(scip); i++ )
12304 SCIP_CALL(
separateCons(scip, conss[i], NULL, sepacardinality, conshdlrdata->usegubs, &cutoff, &ncuts) );
12310 else if ( ncuts > 0 )
12336 assert(conshdlrdata != NULL);
12341 SCIPdebugMsg(scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12342 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12345 if( (depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12346 || (depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12351 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12352 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12353 && ((sepacardfreq == 0 && depth == 0) || (sepacardfreq >= 1 && (depth % sepacardfreq == 0)));
12356 maxsepacuts = (depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12363 for( i = 0; i < nusefulconss && ncuts < maxsepacuts && !
SCIPisStopped(scip); i++ )
12365 SCIP_CALL(
separateCons(scip, conss[i], sol, sepacardinality, conshdlrdata->usegubs, &cutoff, &ncuts) );
12371 else if( ncuts > 0 )
12402 for( i = 0; i < nconss; i++ )
12425 for( i = 0; i < nconss && (*result ==
SCIP_FEASIBLE || completely); i++ )
12450 assert(conshdlrdata != NULL);
12456 for( i = 0; i < nmarkedconss && !cutoff; i++ )
12468 SCIP_CALL(
propagateCons(scip, conss[i], &cutoff, &redundant, &nfixedvars, conshdlrdata->negatedclique) );
12478 else if( nfixedvars > 0 )
12508 oldnfixedvars = *nfixedvars;
12509 oldnchgbds = *nchgbds;
12510 oldndelconss = *ndelconss;
12511 oldnaddconss = *naddconss;
12512 oldnchgcoefs = *nchgcoefs;
12513 oldnchgsides = *nchgsides;
12514 firstchange = INT_MAX;
12516 newchanges = (nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 || nnewupgdconss > 0);
12519 assert(conshdlrdata != NULL);
12523 int thisnfixedvars;
12528 assert(consdata != NULL);
12532 if( newchanges || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
12541 consdata->presolvedtiming = 0;
12542 else if( consdata->presolvedtiming >= presoltiming )
12547 consdata->presolvedtiming = presoltiming;
12549 thisnfixedvars = *nfixedvars;
12550 thisnchgbds = *nchgbds;
12560 SCIP_CALL(
addCliques(scip, cons, conshdlrdata->cliqueextractfactor, &cutoff, nchgbds) );
12568 SCIP_CALL(
propagateCons(scip, cons, &cutoff, &redundant, nfixedvars, (presoltiming & SCIP_PRESOLTIMING_MEDIUM)) );
12580 if( *nfixedvars > thisnfixedvars || *nchgbds > thisnchgbds )
12586 thisnfixedvars = *nfixedvars;
12592 if( consdata->weightsum <= consdata->capacity )
12594 SCIPdebugMsg(scip,
" -> knapsack constraint <%s> is redundant: weightsum=%" SCIP_LONGINT_FORMAT
", capacity=%" SCIP_LONGINT_FORMAT
"\n",
12614 if( *nfixedvars > thisnfixedvars )
12629 if( conshdlrdata->dualpresolving &&
SCIPallowDualReds(scip) && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
12649 if( !cutoff && conshdlrdata->presolusehashing && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
12655 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) || (*naddconss != oldnaddconss) )
12664 npaircomparisons = 0;
12665 oldndelconss = *ndelconss;
12666 oldnchgsides = *nchgsides;
12667 oldnchgcoefs = *nchgcoefs;
12669 for( c = firstchange; c < nconss && !cutoff && !
SCIPisStopped(scip); ++c )
12681 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) )
12683 if( ((
SCIP_Real) (*ndelconss - oldndelconss) + ((
SCIP_Real) (*nchgsides - oldnchgsides))/2.0 +
12686 oldndelconss = *ndelconss;
12687 oldnchgsides = *nchgsides;
12688 oldnchgcoefs = *nchgcoefs;
12689 npaircomparisons = 0;
12693 #ifdef WITH_CARDINALITY_UPGRADE 12702 if ( ! cutoff && conshdlrdata->upgdcardinality && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 &&
SCIPisPresolveFinished(scip) && ! conshdlrdata->upgradedcard )
12711 noldupgdconss = *nupgdconss;
12724 for (makeupgrade = 0; makeupgrade < 2; ++makeupgrade)
12735 assert( cons != NULL );
12737 assert( consdata != NULL );
12739 nvars = consdata->nvars;
12740 vars = consdata->vars;
12741 weights = consdata->weights;
12748 if ( consdata->capacity >= nvars )
12752 assert( consdata->sorted );
12753 if ( weights[0] != 1 || weights[nvars-1] != 1 )
12757 for (v = 0; v <
nvars; ++v)
12766 var = consdata->vars[v];
12767 assert( var != NULL );
12783 for (j = 0; j < nimpls; ++j)
12797 cardvars[v] = implvars[j];
12814 if ( makeupgrade == 0 )
12816 for (v = 0; v <
nvars; ++v)
12840 for (v = 0; v <
nvars; ++v)
12850 conshdlrdata->upgradedcard =
TRUE;
12879 assert( origcons != NULL );
12882 for (v = 0; v <
nvars; ++v)
12898 if ( *nupgdconss > noldupgdconss )
12905 else if( success || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
12921 assert(result != NULL);
12924 assert(consdata != NULL);
12929 for( i = 0; i < consdata->nvars; ++i )
12938 assert(i < consdata->nvars);
12946 if( inferinfo < 0 )
12953 if( inferinfo < consdata->nvars && consdata->vars[inferinfo] == infervar )
12954 capsum = consdata->weights[inferinfo];
12957 for( i = 0; i < consdata->nvars && consdata->vars[i] != infervar; ++i )
12959 assert(i < consdata->nvars);
12960 capsum = consdata->weights[i];
12967 if( capsum <= consdata->capacity )
12969 for( i = 0; i < consdata->nvars; i++ )
12974 capsum += consdata->weights[i];
12975 if( capsum > consdata->capacity )
13005 assert(consdata != NULL);
13007 for( i = 0; i < consdata->nvars; i++)
13021 assert(scip != NULL);
13022 assert(conshdlr != NULL);
13023 assert(conss != NULL || nconss == 0);
13040 assert( scip != NULL );
13041 assert( conshdlr != NULL );
13042 assert( cons != NULL );
13045 assert(consdata != NULL);
13047 for( i = 0; i < consdata->nvars; ++i )
13051 SCIPinfoMessage(scip, file,
"%+" SCIP_LONGINT_FORMAT, consdata->weights[i]);
13054 SCIPinfoMessage(scip, file,
" <= %" SCIP_LONGINT_FORMAT
"", consdata->capacity);
13066 const char* consname;
13076 for( v = 0; v <
nvars; ++v )
13087 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, global, valid) );
13088 assert(cons != NULL);
13109 assert(scip != NULL);
13110 assert(success != NULL);
13111 assert(str != NULL);
13112 assert(name != NULL);
13113 assert(cons != NULL);
13122 while( *str !=
'\0' )
13125 if( sscanf(str,
"%" SCIP_LONGINT_FORMAT
"%n", &weight, &nread) < 1 )
13131 while( isspace((
int)*str) )
13146 if( varssize <= nvars )
13154 weights[
nvars] = weight;
13158 while( isspace((
int)*str) )
13164 if( strncmp(str,
"<= ", 3) != 0 )
13177 if( sscanf(str,
"%" SCIP_LONGINT_FORMAT, &capacity) != 1 )
13185 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
13202 assert(consdata != NULL);
13204 if( varssize < consdata->nvars )
13208 assert(vars != NULL);
13224 assert(consdata != NULL);
13226 (*nvars) = consdata->nvars;
13242 assert(eventdata != NULL);
13243 assert(eventdata->cons != NULL);
13246 assert(consdata != NULL);
13251 consdata->onesweightsum += eventdata->weight;
13252 consdata->presolvedtiming = 0;
13256 consdata->onesweightsum -= eventdata->weight;
13259 consdata->presolvedtiming = 0;
13263 if( !consdata->existmultaggr )
13267 assert(var != NULL);
13272 consdata->existmultaggr =
TRUE;
13273 consdata->merged =
FALSE;
13277 consdata->merged =
FALSE;
13282 consdata->presolvedtiming = 0;
13285 consdata->varsdeleted =
TRUE;
13313 eventhdlrdata = NULL;
13314 conshdlrdata->eventhdlr = NULL;
13316 eventExecKnapsack, eventhdlrdata) );
13319 if( conshdlrdata->eventhdlr == NULL )
13328 consEnfolpKnapsack, consEnfopsKnapsack, consCheckKnapsack, consLockKnapsack,
13331 assert(conshdlr != NULL);
13366 "multiplier on separation frequency, how often knapsack cuts are separated (-1: never, 0: only at root)",
13370 "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for separating knapsack cuts",
13374 "lower clique size limit for greedy clique extraction algorithm (relative to largest clique)",
13378 "maximal number of separation rounds per node (-1: unlimited)",
13382 "maximal number of separation rounds per node in the root node (-1: unlimited)",
13386 "maximal number of cuts separated per separation round",
13390 "maximal number of cuts separated per separation round in the root node",
13394 "should disaggregation of knapsack constraints be allowed in preprocessing?",
13398 "should presolving try to simplify knapsacks",
13402 "should negated clique information be used in solving process",
13406 "should pairwise constraint comparison be performed in presolving?",
13410 "should hash table be used for detecting redundant constraints in advance",
13414 "should dual presolving steps be performed?",
13418 "should GUB information be used for separation?",
13422 "should presolving try to detect constraints parallel to the objective function defining an upper bound and prevent these constraints from entering the LP?",
13426 "should presolving try to detect constraints parallel to the objective function defining a lower bound and prevent these constraints from entering the LP?",
13430 "should clique partition information be updated when old partition seems outdated?",
13434 "factor on the growth of global cliques to decide when to update a previous " 13435 "(negated) clique partition (used only if updatecliquepartitions is set to TRUE)",
13437 #ifdef WITH_CARDINALITY_UPGRADE 13440 "if TRUE then try to update knapsack constraints to cardinality constraints",
13441 &conshdlrdata->upgdcardinality,
TRUE, DEFAULT_UPGDCARDINALITY, NULL, NULL) );
13490 if( conshdlr == NULL )
13498 assert(conshdlrdata != NULL);
13499 assert(conshdlrdata->eventhdlr != NULL);
13505 SCIP_CALL(
SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
13506 local, modifiable, dynamic, removable, stickingatnode) );
13536 assert(scip != NULL);
13552 assert(var != NULL);
13581 assert(consdata != NULL);
13583 return consdata->capacity;
13606 SCIPerrorMessage(
"method can only be called during problem creation stage\n");
13611 assert(consdata != NULL);
13613 consdata->capacity = capacity;
13634 assert(consdata != NULL);
13636 return consdata->nvars;
13655 assert(consdata != NULL);
13657 return consdata->vars;
13676 assert(consdata != NULL);
13678 return consdata->weights;
13697 assert(consdata != NULL);
13699 if( consdata->row != NULL )
13721 assert(consdata != NULL);
13723 if( consdata->row != NULL )
13747 assert(consdata != NULL);
13749 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)