39 #define CONSHDLR_NAME "knapsack" 40 #define CONSHDLR_DESC "knapsack constraint of the form a^T x <= b, x binary and a >= 0" 41 #define CONSHDLR_SEPAPRIORITY +600000 42 #define CONSHDLR_ENFOPRIORITY -600000 43 #define CONSHDLR_CHECKPRIORITY -600000 44 #define CONSHDLR_SEPAFREQ 0 45 #define CONSHDLR_PROPFREQ 1 46 #define CONSHDLR_EAGERFREQ 100 48 #define CONSHDLR_MAXPREROUNDS -1 49 #define CONSHDLR_DELAYSEPA FALSE 50 #define CONSHDLR_DELAYPROP FALSE 51 #define CONSHDLR_NEEDSCONS TRUE 53 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS 54 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP 56 #define EVENTHDLR_NAME "knapsack" 57 #define EVENTHDLR_DESC "bound change event handler for knapsack constraints" 58 #define EVENTTYPE_KNAPSACK SCIP_EVENTTYPE_LBCHANGED \ 59 | SCIP_EVENTTYPE_UBTIGHTENED \ 60 | SCIP_EVENTTYPE_VARFIXED \ 61 | SCIP_EVENTTYPE_VARDELETED \ 62 | SCIP_EVENTTYPE_IMPLADDED 64 #define LINCONSUPGD_PRIORITY +100000 66 #define MAX_USECLIQUES_SIZE 1000 67 #define MAX_ZEROITEMS_SIZE 10000 69 #define KNAPSACKRELAX_MAXDELTA 0.1 70 #define KNAPSACKRELAX_MAXDNOM 1000LL 71 #define KNAPSACKRELAX_MAXSCALE 1000.0 73 #define DEFAULT_SEPACARDFREQ 1 74 #define DEFAULT_MAXROUNDS 5 75 #define DEFAULT_MAXROUNDSROOT -1 76 #define DEFAULT_MAXSEPACUTS 50 77 #define DEFAULT_MAXSEPACUTSROOT 200 78 #define DEFAULT_MAXCARDBOUNDDIST 0.0 80 #define DEFAULT_DISAGGREGATION TRUE 81 #define DEFAULT_SIMPLIFYINEQUALITIES TRUE 82 #define DEFAULT_NEGATEDCLIQUE TRUE 84 #define MAXABSVBCOEF 1e+5 85 #define USESUPADDLIFT FALSE 87 #define DEFAULT_PRESOLUSEHASHING TRUE 88 #define HASHSIZE_KNAPSACKCONS 500 90 #define DEFAULT_PRESOLPAIRWISE TRUE 91 #define NMINCOMPARISONS 200000 92 #define MINGAINPERNMINCOMPARISONS 1e-06 94 #define DEFAULT_DUALPRESOLVING TRUE 95 #define DEFAULT_DETECTCUTOFFBOUND TRUE 98 #define DEFAULT_DETECTLOWERBOUND TRUE 101 #define DEFAULT_CLIQUEEXTRACTFACTOR 0.5 103 #define MAXCOVERSIZEITERLEWI 1000 105 #define DEFAULT_USEGUBS FALSE 106 #define GUBCONSGROWVALUE 6 107 #define GUBSPLITGNC1GUBS FALSE 108 #define DEFAULT_CLQPARTUPDATEFAC 1.5 110 #define DEFAULT_UPDATECLIQUEPARTITIONS FALSE 112 #define MAXNCLIQUEVARSCOMP 1000000 121 struct SCIP_ConshdlrData
184 int* cliquepartition;
185 int* negcliquepartition;
191 int ncliqueslastnegpart;
192 int ncliqueslastpart;
196 unsigned int presolvedtiming:5;
197 unsigned int sorted:1;
198 unsigned int cliquepartitioned:1;
199 unsigned int negcliquepartitioned:1;
200 unsigned int merged:1;
201 unsigned int cliquesadded:1;
202 unsigned int varsdeleted:1;
203 unsigned int existmultaggr:1;
207 struct SCIP_EventData
221 typedef struct sortkeypair SORTKEYPAIR;
277 SORTKEYPAIR* sortkeypair1 = (SORTKEYPAIR*)elem1;
278 SORTKEYPAIR* sortkeypair2 = (SORTKEYPAIR*)elem2;
280 if( sortkeypair1->key1 < sortkeypair2->key1 )
282 else if( sortkeypair1->key1 > sortkeypair2->key1 )
284 else if( sortkeypair1->key2 < sortkeypair2->key2 )
286 else if( sortkeypair1->key2 > sortkeypair2->key2 )
301 assert(eventdata !=
NULL);
304 (*eventdata)->cons = cons;
305 (*eventdata)->weight = weight;
317 assert(eventdata !=
NULL);
330 assert(consdata !=
NULL);
331 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
332 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
333 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
334 assert(consdata->nvars == 0 || (consdata->cliquepartition !=
NULL && consdata->negcliquepartition !=
NULL));
336 if( !consdata->sorted )
346 (
void**)consdata->vars,
347 (
void**)consdata->eventdata,
348 consdata->cliquepartition,
349 consdata->negcliquepartition,
352 v = consdata->nvars - 1;
358 while( w >= 0 && consdata->weights[v] == consdata->weights[w] )
365 (
void**)(&(consdata->vars[w+1])),
366 (
void**)(&(consdata->eventdata[w+1])),
367 &(consdata->cliquepartition[w+1]),
368 &(consdata->negcliquepartition[w+1]),
376 if( consdata->cliquepartitioned )
380 for( pos = 0; pos < consdata->nvars; ++pos )
384 if( consdata->cliquepartition[pos] > lastcliquenum )
386 consdata->cliquepartitioned =
FALSE;
389 else if( consdata->cliquepartition[pos] == lastcliquenum )
394 if( consdata->negcliquepartitioned )
398 for( pos = 0; pos < consdata->nvars; ++pos )
402 if( consdata->negcliquepartition[pos] > lastcliquenum )
404 consdata->negcliquepartitioned =
FALSE;
407 else if( consdata->negcliquepartition[pos] == lastcliquenum )
412 consdata->sorted =
TRUE;
418 for( i = 0; i < consdata->nvars-1; ++i )
419 assert(consdata->weights[i] >= consdata->weights[i+1]);
436 assert(consdata !=
NULL);
437 assert(consdata->nvars == 0 || (consdata->cliquepartition !=
NULL && consdata->negcliquepartition !=
NULL));
440 ispartitionoutdated = (conshdlrdata->updatecliquepartitions && consdata->ncliques > 1
441 &&
SCIPgetNCliques(scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastpart));
443 if( normalclique && ( !consdata->cliquepartitioned || ispartitionoutdated ) )
446 consdata->cliquepartitioned =
TRUE;
451 isnegpartitionoutdated = (conshdlrdata->updatecliquepartitions && consdata->nnegcliques > 1
452 &&
SCIPgetNCliques(scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastnegpart));
454 if( negatedclique && (!consdata->negcliquepartitioned || isnegpartitionoutdated) )
457 consdata->negcliquepartitioned =
TRUE;
460 assert(!consdata->cliquepartitioned || consdata->ncliques <= consdata->nvars);
461 assert(!consdata->negcliquepartitioned || consdata->nnegcliques <= consdata->nvars);
505 assert(cons !=
NULL);
506 assert(consdata !=
NULL);
507 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
508 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
509 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
511 for( i = 0; i < consdata->nvars; i++)
515 eventhdlr, consdata->eventdata[i], &consdata->eventdata[i]->filterpos) );
532 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
533 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
534 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
536 for( i = 0; i < consdata->nvars; i++)
539 eventhdlr, consdata->eventdata[i], consdata->eventdata[i]->filterpos) );
555 assert(consdata !=
NULL);
556 assert(consdata->nvars <= consdata->varssize);
558 if( num > consdata->varssize )
573 assert(consdata->eventdata ==
NULL);
574 assert(consdata->cliquepartition ==
NULL);
575 assert(consdata->negcliquepartition ==
NULL);
577 consdata->varssize = newsize;
579 assert(num <= consdata->varssize);
592 assert(consdata !=
NULL);
595 consdata->weightsum += weightdelta;
598 consdata->onesweightsum += weightdelta;
600 assert(consdata->weightsum >= 0);
601 assert(consdata->onesweightsum >= 0);
618 assert(consdata !=
NULL);
623 (*consdata)->vars =
NULL;
624 (*consdata)->weights =
NULL;
625 (*consdata)->nvars = 0;
636 for( v = 0; v <
nvars; ++v )
638 assert(vars[v] !=
NULL);
642 assert( weights[v] >= 0 );
651 constant += weights[v];
655 varsbuffer[k] = vars[v];
656 weightsbuffer[k] = weights[v];
663 (*consdata)->nvars = k;
678 assert(capacity >= 0);
679 assert(constant >= 0);
681 (*consdata)->varssize = (*consdata)->nvars;
682 (*consdata)->capacity = capacity - constant;
683 (*consdata)->eventdata =
NULL;
684 (*consdata)->cliquepartition =
NULL;
685 (*consdata)->negcliquepartition =
NULL;
686 (*consdata)->row =
NULL;
687 (*consdata)->weightsum = 0;
688 (*consdata)->onesweightsum = 0;
689 (*consdata)->ncliques = 0;
690 (*consdata)->nnegcliques = 0;
691 (*consdata)->presolvedtiming = 0;
692 (*consdata)->sorted =
FALSE;
693 (*consdata)->cliquepartitioned =
FALSE;
694 (*consdata)->negcliquepartitioned =
FALSE;
695 (*consdata)->ncliqueslastpart = -1;
696 (*consdata)->ncliqueslastnegpart = -1;
697 (*consdata)->merged =
FALSE;
698 (*consdata)->cliquesadded =
FALSE;
699 (*consdata)->varsdeleted =
FALSE;
700 (*consdata)->existmultaggr =
FALSE;
707 for( v = 0; v < (*consdata)->nvars; v++ )
721 for( v = 0; v < (*consdata)->nvars; ++v )
740 assert(consdata !=
NULL);
741 assert(*consdata !=
NULL);
743 if( (*consdata)->row !=
NULL )
747 if( (*consdata)->eventdata !=
NULL )
752 if( (*consdata)->negcliquepartition !=
NULL )
756 if( (*consdata)->cliquepartition !=
NULL )
760 if( (*consdata)->vars !=
NULL )
765 for( v = 0; v < (*consdata)->nvars; v++ )
767 assert((*consdata)->vars[v] !=
NULL);
771 assert( (*consdata)->weights !=
NULL );
772 assert( (*consdata)->varssize > 0 );
793 assert(consdata !=
NULL);
794 assert(0 <= item && item < consdata->
nvars);
796 oldweight = consdata->weights[item];
797 weightdiff = newweight - oldweight;
798 consdata->weights[item] = newweight;
804 if( consdata->eventdata !=
NULL )
806 assert(consdata->eventdata[item] !=
NULL);
807 assert(consdata->eventdata[item]->weight == oldweight);
808 consdata->eventdata[item]->weight = newweight;
811 consdata->presolvedtiming = 0;
812 consdata->sorted =
FALSE;
815 if( oldweight < newweight )
817 consdata->cliquesadded =
FALSE;
832 assert(consdata !=
NULL);
833 assert(consdata->row ==
NULL);
840 for( i = 0; i < consdata->nvars; ++i )
860 assert( cutoff !=
NULL );
864 assert(consdata !=
NULL);
866 if( consdata->row ==
NULL )
870 assert(consdata->row !=
NULL);
875 SCIPdebugMsg(scip,
"adding relaxation of knapsack constraint <%s> (capacity %" SCIP_LONGINT_FORMAT
"): ",
897 assert(violated !=
NULL);
900 assert(consdata !=
NULL);
902 SCIPdebugMsg(scip,
"checking knapsack constraint <%s> for feasibility of solution %p (lprows=%u)\n",
930 for( v = consdata->nvars - 1; v >= 0; --v )
933 sum += consdata->weights[v] *
SCIPgetSolVal(scip, sol, consdata->vars[v]);
941 for( v = consdata->nvars - 1; v >= 0; --v )
946 integralsum += consdata->weights[v];
950 if( (!ishuge && integralsum > consdata->capacity) || (ishuge &&
SCIPisFeasGT(scip, sum, (
SCIP_Real)consdata->capacity)) )
964 viol -= consdata->capacity;
979 #define IDX(j,d) ((j)*(intcap)+(d)) 1011 int* allcurrminweight;
1023 const size_t maxsize_t = (size_t)(-1);
1025 assert(weights !=
NULL);
1026 assert(profits !=
NULL);
1027 assert(capacity >= 0);
1028 assert(items !=
NULL);
1029 assert(nitems >= 0);
1030 assert(success !=
NULL);
1035 for( j = nitems - 1; j >= 0; --j )
1036 assert(weights[j] >= 0);
1042 if( solval !=
NULL )
1046 if( solitems !=
NULL)
1048 assert(items !=
NULL);
1049 assert(nsolitems !=
NULL);
1050 assert(nonsolitems !=
NULL);
1051 assert(nnonsolitems !=
NULL);
1067 for( j = 0; j < nitems; ++j )
1071 if( weights[j] > capacity )
1073 if( solitems !=
NULL)
1075 nonsolitems[*nnonsolitems] = items[j];
1080 else if( profits[j] <= 0.0 )
1082 if( solitems !=
NULL)
1084 nonsolitems[*nnonsolitems] = items[j];
1089 else if( weights[j] == 0 )
1091 if( solitems !=
NULL)
1093 solitems[*nsolitems] = items[j];
1096 if( solval !=
NULL )
1097 *solval += profits[j];
1102 myweights[nmyitems] = weights[j];
1103 myprofits[nmyitems] = profits[j];
1104 myitems[nmyitems] = items[j];
1107 if( myweights[nmyitems] < minweight )
1108 minweight = myweights[nmyitems];
1111 if( myweights[nmyitems] > maxweight )
1112 maxweight = myweights[nmyitems];
1114 weightsum += myweights[nmyitems];
1122 SCIPdebugMsg(scip,
"After preprocessing no items are left.\n");
1127 else if( weightsum > 0 && weightsum <= capacity )
1129 SCIPdebugMsg(scip,
"After preprocessing all items fit into knapsack.\n");
1131 for( j = nmyitems - 1; j >= 0; --j )
1133 if( solitems !=
NULL )
1135 solitems[*nsolitems] = myitems[j];
1138 if( solval !=
NULL )
1139 *solval += myprofits[j];
1145 assert(minweight > 0);
1146 assert(maxweight > 0);
1151 gcd = myweights[nmyitems - 1];
1152 for( j = nmyitems - 2; j >= 0 && gcd >= 2; --j )
1155 SCIPdebugMsg(scip,
"Gcd is %" SCIP_LONGINT_FORMAT
".\n", gcd);
1161 for( j = nmyitems - 1; j >= 0; --j )
1163 myweights[j] /= gcd;
1164 eqweights = eqweights && (myweights[j] == 1);
1174 assert(maxweight == 1);
1178 assert(minweight <= capacity);
1181 if( minweight > capacity / 2 )
1185 SCIPdebugMsg(scip,
"Only one item fits into knapsack, so take the best.\n");
1190 for( j = nmyitems - 2; j >= 0; --j )
1191 if( myprofits[j] > myprofits[p] )
1195 if( solitems !=
NULL)
1197 solitems[*nsolitems] = myitems[p];
1199 for( j = nmyitems - 1; j >= 0; --j )
1202 nonsolitems[*nnonsolitems] = myitems[j];
1207 if( solval !=
NULL )
1208 *solval += myprofits[p];
1218 SCIPdebugMsg(scip,
"All weights are equal, so take the best.\n");
1224 if( solitems !=
NULL || solval !=
NULL )
1232 for( i = capacity - 1; i >= 0; --i )
1234 if( solitems !=
NULL)
1236 assert(nonsolitems !=
NULL);
1237 solitems[*nsolitems] = myitems[i];
1240 addval += myprofits[i];
1243 if( solitems !=
NULL)
1245 assert(nonsolitems !=
NULL);
1248 for( i = nmyitems - 1; i >= capacity; --i )
1250 nonsolitems[*nnonsolitems] = myitems[i];
1256 if( solval !=
NULL )
1258 assert(addval > 0.0);
1266 capacity -= (minweight - 1);
1269 if( capacity >= INT_MAX )
1271 SCIPdebugMsg(scip,
"Capacity is to big, so we cannot handle it here.\n");
1276 assert(capacity < INT_MAX);
1278 intcap = (int)capacity;
1279 assert(intcap >= 0);
1280 assert(nmyitems > 0);
1281 assert(
sizeof(
size_t) >=
sizeof(
int));
1286 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) )) )
1288 SCIPdebugMsg(scip,
"Too much memory (%lu) would be consumed.\n", (
unsigned long) (((
size_t)nmyitems) * ((
size_t)intcap) *
sizeof(*optvalues)));
1312 for( j = nmyitems - 1; j >= 0; --j )
1313 tempsort[j] = myprofits[j]/((
SCIP_Real) myweights[j]);
1318 greedysolweight = 0;
1319 greedysolvalue = 0.0;
1321 greedycap = capacity + (minweight - 1);
1326 for( j = 0; j < nmyitems; ++j )
1328 assert(myweights[j] <= greedycap);
1331 if( myweights[j] + greedysolweight <= greedycap )
1334 greedysolweight += myweights[j];
1335 greedysolvalue += myprofits[j];
1338 else if( greedysolweight < greedycap )
1342 assert(greedysolweight > 0);
1343 assert(greedysolvalue > 0.0);
1348 assert(greedysolweight == greedycap);
1352 greedysolweight = 0;
1355 if( solitems !=
NULL)
1358 for( j = 0; j < nmyitems; ++j )
1361 if( myweights[j] + greedysolweight <= greedycap )
1363 solitems[*nsolitems] = myitems[j];
1365 greedysolweight += myweights[j];
1369 nonsolitems[*nnonsolitems] = myitems[j];
1375 if( solval !=
NULL )
1377 assert(greedysolvalue > 0.0);
1378 *solval += greedysolvalue;
1395 assert(myweights[0] - minweight < INT_MAX);
1396 currminweight = (int) (myweights[0] - minweight);
1397 allcurrminweight[0] = currminweight;
1400 for( d = currminweight; d < intcap; ++d )
1401 optvalues[d] = myprofits[0];
1403 for( j = 1; j < nmyitems; ++j )
1408 intweight = (int)(myweights[j] - minweight);
1409 assert(0 <= intweight && intweight < intcap);
1412 for( d = currminweight; d < intweight && d < intcap; ++d )
1413 optvalues[
IDX(j,d)] = optvalues[
IDX(j-1,d)];
1416 for( d = intweight; d < intcap; ++d )
1421 if( d < currminweight )
1423 optvalues[
IDX(j,d)] = myprofits[j];
1429 if( d - myweights[j] < currminweight )
1430 sumprofit = myprofits[j];
1432 sumprofit = optvalues[
IDX(j-1,(
int)(d-myweights[j]))] + myprofits[j];
1434 optvalues[
IDX(j,d)] =
MAX(sumprofit, optvalues[
IDX(j-1,d)]);
1438 if( intweight < currminweight )
1439 currminweight = intweight;
1441 allcurrminweight[j] = currminweight;
1445 if( solitems !=
NULL)
1449 SCIPdebugMsg(scip,
"Fill the solution vector after solving exactly.\n");
1452 for( j = nmyitems - 1; j > 0; --j )
1457 if( d < allcurrminweight[j] )
1464 if( d < allcurrminweight[j-1] || optvalues[
IDX(j,d)] > optvalues[
IDX(j-1,d)] )
1466 solitems[*nsolitems] = myitems[j];
1471 d = (int)(d - myweights[j]);
1476 nonsolitems[*nnonsolitems] = myitems[j];
1482 if( d >= allcurrminweight[j] )
1485 solitems[*nsolitems] = myitems[j];
1491 assert(d < allcurrminweight[j]);
1493 for( ; j >= 0; --j )
1495 nonsolitems[*nnonsolitems] = myitems[j];
1500 assert(*nsolitems + *nnonsolitems == nitems);
1504 if( solval !=
NULL )
1505 *solval += optvalues[
IDX(nmyitems-1,intcap-1)];
1545 assert(weights !=
NULL);
1546 assert(profits !=
NULL);
1547 assert(capacity >= 0);
1548 assert(items !=
NULL);
1549 assert(nitems >= 0);
1551 if( solitems !=
NULL )
1556 if( solval !=
NULL )
1562 for( j = nitems - 1; j >= 0; --j )
1564 tempsort[j] = profits[j]/((
SCIP_Real) weights[j]);
1574 for( j = 0; j < nitems && solitemsweight + weights[j] <= capacity; ++j )
1576 if( solitems !=
NULL )
1578 solitems[*nsolitems] = items[j];
1581 if( solval !=
NULL )
1582 (*solval) += profits[j];
1583 solitemsweight += weights[j];
1585 for( ; j < nitems && solitems !=
NULL; j++ )
1587 nonsolitems[*nnonsolitems] = items[j];
1607 int nnontrivialgubconss;
1610 nnontrivialgubconss = 0;
1612 SCIPdebugMsg(scip,
" Nontrivial GUBs of current GUB set:\n");
1615 for( c = 0; c < gubset->
ngubconss; c++ )
1635 if( solvals !=
NULL )
1637 gubsolval += solvals[currentvar];
1647 if( solvals !=
NULL )
1650 SCIPisFeasGT(scip, gubsolval, 1.0) ?
"--> violated" :
"");
1656 nnontrivialgubconss++;
1671 assert(scip !=
NULL);
1672 assert(gubcons !=
NULL);
1680 (*gubcons)->ngubvars = 0;
1692 assert(scip !=
NULL);
1693 assert(gubcons !=
NULL);
1694 assert((*gubcons)->gubvars !=
NULL);
1695 assert((*gubcons)->gubvarsstatus !=
NULL);
1713 assert(scip !=
NULL);
1714 assert(gubcons !=
NULL);
1749 assert(scip !=
NULL);
1752 assert(gubvarsidx >= 0 && gubvarsidx < gubcons->ngubvars);
1753 assert(gubcons->
ngubvars >= gubvarsidx+1);
1754 assert(gubcons->
gubvars[gubvarsidx] == var);
1792 assert(scip !=
NULL);
1793 assert(gubset !=
NULL);
1795 assert(oldgubcons >= 0 && oldgubcons < gubset->
ngubconss);
1796 assert(newgubcons >= 0 && newgubcons < gubset->ngubconss);
1797 assert(oldgubcons != newgubcons);
1814 gubset->
gubvarsidx[replacevar] = oldgubvaridx;
1827 SCIPdebugMsg(scip,
"deleting empty GUB cons<%d> from current GUB set\n", oldgubcons);
1829 GUBsetPrint(scip, gubset, vars,
NULL);
1883 assert(scip !=
NULL);
1884 assert(gubset !=
NULL);
1920 assert(scip !=
NULL);
1921 assert(gubset !=
NULL);
1923 assert(weights !=
NULL);
1924 assert(capacity >= 0);
1932 (*gubset)->ngubconss =
nvars;
1933 (*gubset)->nvars =
nvars;
1936 for( i = 0; i <
nvars; i++ )
1945 (*gubset)->gubconssidx[i] = i;
1946 (*gubset)->gubvarsidx[i] = 0;
1947 assert((*gubset)->gubconss[i]->ngubvars == 1);
1950 if( weights[i] > capacity )
1967 assert(scip !=
NULL);
1969 assert((*gubset)->gubconss !=
NULL);
1970 assert((*gubset)->gubconsstatus !=
NULL);
1971 assert((*gubset)->gubconssidx !=
NULL);
1972 assert((*gubset)->gubvarsidx !=
NULL);
1975 for( i = (*gubset)->ngubconss-1; i >= 0; --i )
1977 assert((*gubset)->gubconss[i] !=
NULL);
2008 assert(scip !=
NULL);
2009 assert(gubset !=
NULL);
2014 for( i = 0; i < gubset->
nvars; i++ )
2021 SCIPdebugMsg(scip,
" var<%d> should be in GUB<%d> at position<%d>, but stored is var<%d> instead\n", i,
2022 gubconsidx, gubvaridx, gubset->
gubconss[gubconsidx]->
gubvars[gubvaridx] );
2028 for( i = 0; i < gubset->
ngubconss; i++ )
2038 var1negated =
FALSE;
2045 var2negated =
FALSE;
2050 SCIPdebugMsg(scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n", i, j,
2053 SCIPdebugMsg(scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n", i, j,
2083 int*
const cliquepartition,
2095 int maxncliquevarscomp;
2100 assert(scip !=
NULL);
2101 assert(nvars == 0 || vars !=
NULL);
2102 assert(nvars == 0 || cliquepartition !=
NULL);
2103 assert(ncliques !=
NULL);
2121 for( i = nvars - 1; i >= 0; --i )
2123 tmpvalues[i] =
TRUE;
2124 cliquepartition[i] = -1;
2135 for( i = 0; i <
nvars; i++ )
2140 varseq[nvars-1-nignorevars] = i;
2146 varseq[nvarsused] = i;
2151 assert(nvarsused + nignorevars == nvars);
2160 for( i = 0; i <
nvars; ++i )
2162 if( cliquepartition[varseq[i]] == -1 )
2167 cliquepartition[varseq[i]] = *ncliques;
2168 cliquevars[0] = tmpvars[varseq[i]];
2169 cliquevalues[0] = tmpvalues[varseq[i]];
2178 for( j = i + 1; j < nvarsused; ++j )
2181 if( cliquepartition[varseq[j]] == -1 &&
SCIPvarIsActive(tmpvars[varseq[j]]) )
2186 for( k = ncliquevars - 1; k >= 0; --k )
2189 cliquevalues[k],
TRUE) )
2196 cliquepartition[varseq[j]] = cliquepartition[varseq[i]];
2197 cliquevars[ncliquevars] = tmpvars[varseq[j]];
2198 cliquevalues[ncliquevars] = tmpvalues[varseq[j]];
2208 assert(cliquepartition[varseq[i]] >= 0 && cliquepartition[varseq[i]] < i + 1);
2211 if( i * nvars > maxncliquevarscomp )
2215 for( ; i <
nvars; ++i )
2217 if( cliquepartition[varseq[i]] == -1 )
2219 cliquepartition[varseq[i]] = *ncliques;
2244 int* cliquepartition;
2247 int currentgubconsidx;
2253 assert(scip !=
NULL);
2254 assert(gubset !=
NULL);
2255 assert(vars !=
NULL);
2257 nvars = gubset->
nvars;
2270 for( i = 0; i < ncliques; i++ )
2273 gubfirstvar[i] = -1;
2276 for( i = 0; i <
nvars; i++ )
2278 assert(cliquepartition[i] >= 0);
2280 cliqueidx = cliquepartition[i];
2285 if( gubfirstvar[cliqueidx] == -1 )
2294 gubfirstvar[cliqueidx] = i;
2299 assert(gubfirstvar[cliqueidx] >= 0 && gubfirstvar[cliqueidx] < i);
2304 newgubconsidx = gubset->
gubconssidx[gubfirstvar[cliqueidx]];
2305 assert(newgubconsidx != currentgubconsidx);
2314 GUBsetPrint(scip, gubset, vars, solvals);
2366 assert(scip !=
NULL);
2367 assert(vars !=
NULL);
2369 assert(weights !=
NULL);
2370 assert(capacity >= 0);
2371 assert(solvals !=
NULL);
2372 assert(covervars !=
NULL);
2373 assert(noncovervars !=
NULL);
2374 assert(ncovervars !=
NULL);
2375 assert(nnoncovervars !=
NULL);
2376 assert(coverweight !=
NULL);
2377 assert(found !=
NULL);
2378 assert(ntightened !=
NULL);
2379 assert(fractional !=
NULL);
2381 SCIPdebugMsg(scip,
" get cover for knapsack constraint\n");
2405 fixedonesweight = 0;
2408 for( j = 0; j <
nvars; j++ )
2413 if( weights[j] > capacity )
2416 assert(!infeasible);
2424 fixedones[nfixedones] = j;
2426 fixedonesweight += weights[j];
2431 fixedzeros[nfixedzeros] = j;
2440 itemsweight += weights[j];
2443 assert(nfixedones + nfixedzeros + nitems == nvars - (*ntightened));
2448 assert(nitems >= 0);
2451 *fractional =
FALSE;
2454 assert(*fractional);
2472 for( j = 0; j < nitems; j++ )
2474 transweights[j] = weights[items[j]];
2475 transprofits[j] = 1.0 - solvals[items[j]];
2478 transcapacity = fixedonesweight + itemsweight - capacity - 1;
2483 if( transcapacity < 0 )
2507 for( j = 0; j < nitems; j++ )
2509 transprofits[j] *= weights[items[j]];
2521 noncovervars, covervars, nnoncovervars, ncovervars,
NULL) );
2525 for( j = 0; j < *ncovervars; j++ )
2527 (*coverweight) += weights[covervars[j]];
2531 for( j = 0; j < nfixedones; j++ )
2533 covervars[*ncovervars] = fixedones[j];
2535 (*coverweight) += weights[fixedones[j]];
2539 for( j = 0; j < nfixedzeros; j++ )
2541 noncovervars[*nnoncovervars] = fixedzeros[j];
2544 assert((*ncovervars) + (*nnoncovervars) == nvars - (*ntightened));
2545 assert((*coverweight) > capacity);
2556 SCIPdebugMsg(scip,
" get cover for knapsack constraint -- end\n");
2578 assert(weights !=
NULL);
2579 assert(covervars !=
NULL);
2580 assert(ncovervars > 0);
2582 minweight = weights[covervars[minweightidx]];
2585 for( i = 0; i < j; i++ )
2587 assert(weights[covervars[i]] > minweight);
2588 if( weights[covervars[i]] <= minweight )
2593 for( i = 0; i < j; i++ )
2595 assert(coverweight - weights[covervars[i]] <= capacity);
2596 if( coverweight - weights[covervars[i]] > capacity )
2621 assert(scip !=
NULL);
2622 assert(ncovervars >= 0);
2623 assert(solvals !=
NULL);
2624 assert(covervars !=
NULL);
2625 assert(varsC1 !=
NULL);
2626 assert(varsC2 !=
NULL);
2627 assert(nvarsC1 !=
NULL);
2628 assert(nvarsC2 !=
NULL);
2632 for( j = 0; j < ncovervars; j++ )
2634 assert(
SCIPisFeasGT(scip, solvals[covervars[j]], 0.0));
2637 if(
SCIPisGE(scip, solvals[covervars[j]], 1.0) )
2639 varsC2[*nvarsC2] = covervars[j];
2645 assert(
SCIPisLT(scip, solvals[covervars[j]], 1.0));
2646 varsC1[*nvarsC1] = covervars[j];
2650 assert((*nvarsC1) + (*nvarsC2) == ncovervars);
2669 assert(*nvarsC1 >= 0 && *nvarsC1 <= 1);
2670 assert(*nvarsC2 > 0);
2676 for( j = 0; j < *nvarsC2; j++ )
2677 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
2681 assert(*nvarsC2 == 1 || weights[varsC2[(*nvarsC2)-1]] <= weights[varsC2[(*nvarsC2)-2]]);
2682 while( *nvarsC1 < 2 && *nvarsC2 > 0 )
2684 varsC1[*nvarsC1] = varsC2[(*nvarsC2)-1];
2709 assert(*nvarsC1 >= 0 && *nvarsC1 <= 1);
2710 assert(*nvarsC2 > 0);
2716 for( j = 0; j < *nvarsC2; j++ )
2717 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
2721 assert(*nvarsC2 == 1 || weights[varsC2[(*nvarsC2)-1]] <= weights[varsC2[(*nvarsC2)-2]]);
2722 varsC1[*nvarsC1] = varsC2[(*nvarsC2)-1];
2751 assert(scip !=
NULL);
2752 assert(nnoncovervars >= 0);
2753 assert(solvals !=
NULL);
2754 assert(noncovervars !=
NULL);
2755 assert(varsF !=
NULL);
2756 assert(varsR !=
NULL);
2757 assert(nvarsF !=
NULL);
2758 assert(nvarsR !=
NULL);
2763 for( j = 0; j < nnoncovervars; j++ )
2766 if(
SCIPisFeasEQ(scip, solvals[noncovervars[j]], 0.0) )
2768 varsR[*nvarsR] = noncovervars[j];
2774 assert(
SCIPisFeasGT(scip, solvals[noncovervars[j]], 0.0));
2775 varsF[*nvarsF] = noncovervars[j];
2779 assert((*nvarsF) + (*nvarsR) == nnoncovervars);
2798 SORTKEYPAIR** sortkeypairsF;
2799 SORTKEYPAIR* sortkeypairsFstore;
2804 assert(scip !=
NULL);
2805 assert(solvals !=
NULL);
2806 assert(weights !=
NULL);
2807 assert(varsF !=
NULL);
2808 assert(varsC2 !=
NULL);
2809 assert(varsR !=
NULL);
2810 assert(nvarsF >= 0);
2811 assert(nvarsC2 >= 0);
2812 assert(nvarsR >= 0);
2826 for( j = 0; j < nvarsF; j++ )
2828 sortkeypairsF[j] = &(sortkeypairsFstore[j]);
2829 sortkeypairsF[j]->key1 = solvals[varsF[j]];
2830 sortkeypairsF[j]->key2 = (
SCIP_Real) weights[varsF[j]];
2836 for( j = 0; j < nvarsC2; j++ )
2837 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
2842 for( j = 0; j < nvarsR; j++ )
2843 sortkeysR[j] = (
SCIP_Real) weights[varsR[j]];
2893 int* ngubconscapexceed,
2898 SORTKEYPAIR** sortkeypairsF;
2900 SORTKEYPAIR** sortkeypairsGFC1;
2901 SORTKEYPAIR* sortkeypairsGFC1store;
2905 int* nC1varsingubcons;
2916 #if GUBSPLITGNC1GUBS 2922 assert(scip !=
NULL);
2923 assert(gubset !=
NULL);
2924 assert(solvals !=
NULL);
2925 assert(weights !=
NULL);
2926 assert(varsC1 !=
NULL);
2927 assert(varsC2 !=
NULL);
2928 assert(varsF !=
NULL);
2929 assert(varsR !=
NULL);
2930 assert(nvarsC1 > 0);
2931 assert(nvarsC2 >= 0);
2932 assert(nvarsF >= 0);
2933 assert(nvarsR >= 0);
2934 assert(gubconsGC1 !=
NULL);
2935 assert(gubconsGC2 !=
NULL);
2936 assert(gubconsGFC1 !=
NULL);
2937 assert(gubconsGR !=
NULL);
2938 assert(ngubconsGC1 !=
NULL);
2939 assert(ngubconsGC2 !=
NULL);
2940 assert(ngubconsGFC1 !=
NULL);
2941 assert(ngubconsGR !=
NULL);
2942 assert(maxgubvarssize !=
NULL);
2988 for( j = 0; j < nvarsC1; j++ )
2991 sortkeysC1[j] = (
SCIP_Real) weights[varsC1[j]];
3004 for( j = 0; j < nvarsF; j++ )
3009 sortkeypairsF[j]->key1 = solvals[varsF[j]];
3010 sortkeypairsF[j]->key2 = (
SCIP_Real) weights[varsF[j]];
3023 for( j = 0; j < nvarsC2; j++ )
3026 sortkeysC2[j] = (
SCIP_Real) weights[varsC2[j]];
3038 for( j = 0; j < nvarsR; j++ )
3041 sortkeysR[j] = (
SCIP_Real) weights[varsR[j]];
3073 for( j = nvarsF-1; j >= 0; j-- )
3086 sortkeypairsGFC1[i] = &(sortkeypairsGFC1store[i]);
3087 sortkeypairsGFC1[i]->key1 = 0.0;
3088 sortkeypairsGFC1[i]->key2 = 0.0;
3094 *ngubconscapexceed = 0;
3095 *maxgubvarssize = 0;
3098 for( i = 0; i < gubset->
ngubconss; i++ )
3108 for( i = 0; i < nvarsC1; i++ )
3110 int nvarsC1capexceed;
3112 nvarsC1capexceed = 0;
3118 assert(gubconsidx >= 0 && gubconsidx < ngubconss);
3124 targetvar = gubset->
gubconss[gubconsidx]->
gubvars[nC1varsingubcons[gubconsidx]];
3126 nC1varsingubcons[gubconsidx]++;
3139 #if GUBSPLITGNC1GUBS 3140 gubconswithF =
FALSE;
3155 #if GUBSPLITGNC1GUBS 3156 gubconswithF =
TRUE;
3158 sortkeypairsGFC1[*ngubconsGFC1]->key1 += 1.0;
3160 if( solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3161 sortkeypairsGFC1[*ngubconsGFC1]->key2 = solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]];
3172 gubconsGC1[*ngubconsGC1] = gubconsidx;
3187 #if GUBSPLITGNC1GUBS 3208 gubconsidx, ngubconss-1) );
3218 gubconsGR[*ngubconsGR] = ngubconss-1;
3224 assert(gubconswithF);
3227 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3232 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3241 for( i = 0; i < nvarsC2; i++ )
3247 assert(gubconsidx >= 0 && gubconsidx < ngubconss);
3249 assert(varidx == 0);
3257 gubconsGC2[*ngubconsGC2] = gubconsidx;
3271 for( i = 0; i < nvarsF; i++ )
3277 assert(gubconsidx >= 0 && gubconsidx < ngubconss);
3302 sortkeypairsGFC1[*ngubconsGFC1]->key1 += 1.0;
3304 if( solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]] > sortkeypairsGFC1[*ngubconsGFC1]->key2 )
3305 sortkeypairsGFC1[*ngubconsGFC1]->key2 = solvals[gubset->
gubconss[gubconsidx]->
gubvars[j]];
3310 gubconsGFC1[*ngubconsGFC1] = gubconsidx;
3321 for( i = 0; i < nvarsR; i++ )
3327 assert(gubconsidx >= 0 && gubconsidx < ngubconss);
3345 gubconsGR[*ngubconsGR] = gubconsidx;
3352 assert(nvarsprocessed == nvarsC1 + nvarsC2 + nvarsF + nvarsR);
3355 (*ngubconscapexceed) = ngubconss - (ngubconsGOC1 + (*ngubconsGC2) + (*ngubconsGFC1) + (*ngubconsGR));
3356 assert(*ngubconscapexceed >= 0);
3369 assert(check == *ngubconscapexceed);
3374 if( (*ngubconsGFC1) > 0 )
3376 SCIPsortDownPtrInt((
void**)sortkeypairsGFC1, gubconsGFC1, compSortkeypairs, (*ngubconsGFC1));
3380 #if GUBSPLITGNC1GUBS 3381 ngubconss = origngubconss;
3396 int* minweightssize,
3402 assert(minweightsptr !=
NULL);
3403 assert(*minweightsptr !=
NULL);
3404 assert(minweightslen !=
NULL);
3405 assert(*minweightslen >= 0);
3406 assert(minweightssize !=
NULL);
3407 assert(*minweightssize >= 0);
3409 if( newlen > *minweightssize )
3416 *minweightssize = newsize;
3418 assert(newlen <= *minweightssize);
3421 for( j = *minweightslen; j < newlen; ++j )
3423 *minweightslen = newlen;
3472 assert(scip !=
NULL);
3473 assert(vars !=
NULL);
3475 assert(weights !=
NULL);
3476 assert(capacity >= 0);
3477 assert(solvals !=
NULL);
3478 assert(varsM1 !=
NULL);
3479 assert(varsM2 !=
NULL);
3480 assert(varsF !=
NULL);
3481 assert(varsR !=
NULL);
3482 assert(nvarsM1 >= 0 && nvarsM1 <= nvars - ntightened);
3483 assert(nvarsM2 >= 0 && nvarsM2 <= nvars - ntightened);
3484 assert(nvarsF >= 0 && nvarsF <= nvars - ntightened);
3485 assert(nvarsR >= 0 && nvarsR <= nvars - ntightened);
3486 assert(nvarsM1 + nvarsM2 + nvarsF + nvarsR == nvars - ntightened);
3487 assert(alpha0 >= 0);
3488 assert(liftcoefs !=
NULL);
3489 assert(cutact !=
NULL);
3490 assert(liftrhs !=
NULL);
3493 minweightssize = nvarsM1 + 1;
3504 for( j = 0; j < nvarsM1; j++ )
3506 assert(liftcoefs[varsM1[j]] == 0);
3507 liftcoefs[varsM1[j]] = 1;
3508 sortkeys[j] = (
SCIP_Real) (weights[varsM1[j]]);
3509 (*cutact) += solvals[varsM1[j]];
3521 for( w = 1; w <= nvarsM1; w++ )
3522 minweights[w] = minweights[w-1] + weights[varsM1[w-1]];
3523 minweightslen = nvarsM1 + 1;
3526 fixedonesweight = 0;
3527 for( j = 0; j < nvarsM2; j++ )
3528 fixedonesweight += weights[varsM2[j]];
3529 assert(fixedonesweight >= 0);
3535 for( j = 0; j < nvarsF; j++ )
3543 weight = weights[liftvar];
3544 assert(liftvar >= 0 && liftvar < nvars);
3551 if( capacity - fixedonesweight - weight < 0 )
3559 else if( minweights[*liftrhs] <= capacity - fixedonesweight - weight )
3572 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
3574 right = (*liftrhs) + 1;
3575 while( left < right - 1 )
3577 middle = (left + right) / 2;
3578 assert(0 <= middle && middle < minweightslen);
3579 if( minweights[middle] <= capacity - fixedonesweight - weight )
3584 assert(left == right - 1);
3585 assert(0 <= left && left < minweightslen);
3586 assert(minweights[left] <= capacity - fixedonesweight - weight );
3587 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight - weight);
3591 assert(z <= *liftrhs);
3595 liftcoef = (*liftrhs) - z;
3596 liftcoefs[liftvar] = liftcoef;
3597 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
3604 (*cutact) += liftcoef * solvals[liftvar];
3618 for( w = minweightslen - 1; w >= 0; w-- )
3623 min =
MIN(minweights[w], weight);
3624 minweights[w] = min;
3628 assert(w >= liftcoef);
3629 min =
MIN(minweights[w], minweights[w - liftcoef] + weight);
3630 minweights[w] = min;
3634 assert(minweights[0] == 0);
3637 for( j = 0; j < nvarsM2; j++ )
3647 liftvar = varsM2[j];
3648 weight = weights[liftvar];
3650 assert(liftvar >= 0 && liftvar < nvars);
3657 right = minweightslen;
3658 while( left < right - 1 )
3660 middle = (left + right) / 2;
3661 assert(0 <= middle && middle < minweightslen);
3662 if( minweights[middle] <= capacity - fixedonesweight + weight )
3667 assert(left == right - 1);
3668 assert(0 <= left && left < minweightslen);
3669 assert(minweights[left] <= capacity - fixedonesweight + weight );
3670 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight + weight);
3674 assert(z >= *liftrhs);
3677 liftcoef = z - (*liftrhs);
3678 liftcoefs[liftvar] = liftcoef;
3679 assert(liftcoef >= 0);
3682 fixedonesweight -= weight;
3685 (*liftrhs) += liftcoef;
3686 assert(*liftrhs >= alpha0);
3693 (*cutact) += liftcoef * solvals[liftvar];
3707 for( w = minweightslen - 1; w >= 0; w-- )
3712 min =
MIN(minweights[w], weight);
3713 minweights[w] = min;
3717 assert(w >= liftcoef);
3718 min =
MIN(minweights[w], minweights[w - liftcoef] + weight);
3719 minweights[w] = min;
3723 assert(fixedonesweight == 0);
3724 assert(*liftrhs >= alpha0);
3727 for( j = 0; j < nvarsR; j++ )
3735 weight = weights[liftvar];
3736 assert(liftvar >= 0 && liftvar < nvars);
3739 assert(capacity - weight >= 0);
3740 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - weight);
3745 if( minweights[*liftrhs] <= capacity - weight )
3758 right = (*liftrhs) + 1;
3759 while( left < right - 1)
3761 middle = (left + right) / 2;
3762 assert(0 <= middle && middle < minweightslen);
3763 if( minweights[middle] <= capacity - weight )
3768 assert(left == right - 1);
3769 assert(0 <= left && left < minweightslen);
3770 assert(minweights[left] <= capacity - weight );
3771 assert(left == minweightslen - 1 || minweights[left+1] > capacity - weight);
3775 assert(z <= *liftrhs);
3779 liftcoef = (*liftrhs) - z;
3780 liftcoefs[liftvar] = liftcoef;
3781 assert(liftcoef >= 0 && liftcoef <= *liftrhs);
3788 (*cutact) += liftcoef * solvals[liftvar];
3794 for( w = *liftrhs; w >= 0; w-- )
3799 min =
MIN(minweights[w], weight);
3800 minweights[w] = min;
3804 assert(w >= liftcoef);
3805 min =
MIN(minweights[w], minweights[w - liftcoef] + weight);
3806 minweights[w] = min;
3833 return (val1 + val2);
3855 assert(unfinished[w2] == 0);
3856 for( w1 = 0; w1 < minweightslen; w1++ )
3857 minweights[w1] = finished[w1];
3860 for( w2 = 1; w2 < minweightslen; w2++ )
3865 for( w1 = 0; w1 < minweightslen - w2; w1++ )
3870 if( temp <= minweights[w1+w2] )
3871 minweights[w1+w2] = temp;
3895 int ngubconscapexceed,
3949 assert(gubset !=
NULL);
3952 assert(gubset !=
NULL);
3955 nvars = gubset->
nvars;
3957 assert(scip !=
NULL);
3958 assert(vars !=
NULL);
3960 assert(weights !=
NULL);
3961 assert(capacity >= 0);
3962 assert(solvals !=
NULL);
3963 assert(gubconsGC1 !=
NULL);
3964 assert(gubconsGC2 !=
NULL);
3965 assert(gubconsGFC1 !=
NULL);
3966 assert(gubconsGR !=
NULL);
3967 assert(ngubconsGC1 >= 0 && ngubconsGC1 <= ngubconss - ngubconscapexceed);
3968 assert(ngubconsGC2 >= 0 && ngubconsGC2 <= ngubconss - ngubconscapexceed);
3969 assert(ngubconsGFC1 >= 0 && ngubconsGFC1 <= ngubconss - ngubconscapexceed);
3970 assert(ngubconsGR >= 0 && ngubconsGR <= ngubconss - ngubconscapexceed);
3971 assert(alpha0 >= 0);
3972 assert(liftcoefs !=
NULL);
3973 assert(cutact !=
NULL);
3974 assert(liftrhs !=
NULL);
3976 minweightssize = ngubconsGC1+1;
3995 for( j = 0; j < ngubconsGC1; j++ )
3999 gubconsGOC1[ngubconsGOC1] = gubconsGC1[j];
4005 gubconsGNC1[ngubconsGNC1] = gubconsGC1[j];
4012 assert(varidx >= 0 && varidx < nvars);
4013 assert(liftcoefs[varidx] == 0);
4015 liftcoefs[varidx] = 1;
4016 (*cutact) += solvals[varidx];
4020 assert(ngubconsGOC1 + ngubconsGFC1 + ngubconsGC2 + ngubconsGR == ngubconss - ngubconscapexceed);
4021 assert(ngubconsGOC1 + ngubconsGNC1 == ngubconsGC1);
4042 assert(ngubconsGOC1 <= ngubconsGC1);
4044 for( w = 1; w <= ngubconsGOC1; w++ )
4046 liftgubconsidx = gubconsGOC1[w-1];
4053 assert(varidx >= 0 && varidx < nvars);
4054 assert(liftcoefs[varidx] == 1);
4056 min = weights[varidx];
4057 finished[w] = finished[w-1] + min;
4064 assert(varidx >= 0 && varidx < nvars);
4065 assert(liftcoefs[varidx] == 1);
4066 assert(weights[varidx] >= min);
4070 for( w = ngubconsGOC1+1; w <= ngubconsGC1; w++ )
4078 assert(ngubconsGNC1 <= ngubconsGC1);
4080 for( w = 1; w <= ngubconsGNC1; w++ )
4082 liftgubconsidx = gubconsGNC1[w-1];
4089 assert(varidx >= 0 && varidx < nvars);
4090 assert(liftcoefs[varidx] == 1);
4092 min = weights[varidx];
4093 unfinished[w] = unfinished[w-1] + min;
4100 assert(varidx >= 0 && varidx < nvars);
4101 assert(liftcoefs[varidx] == 1);
4102 assert(weights[varidx] >= min );
4106 for( w = ngubconsGNC1 + 1; w <= ngubconsGC1; w++ )
4114 assert(ngubconsGOC1 + ngubconsGNC1 == ngubconsGC1);
4116 for( w = 1; w <= ngubconsGC1; w++ )
4118 liftgubconsidx = gubconsGC1[w-1];
4126 assert(varidx >= 0 && varidx < nvars);
4127 assert(liftcoefs[varidx] == 1);
4129 min = weights[varidx];
4130 minweights[w] = minweights[w-1] + min;
4137 assert(varidx >= 0 && varidx < nvars);
4138 assert(liftcoefs[varidx] == 1);
4139 assert(weights[varidx] >= min);
4143 minweightslen = ngubconsGC1 + 1;
4146 fixedonesweight = 0;
4147 for( j = 0; j < ngubconsGC2; j++ )
4152 assert(varidx >= 0 && varidx < nvars);
4155 fixedonesweight += weights[varidx];
4157 assert(fixedonesweight >= 0);
4163 for( j = 0; j < ngubconsGFC1; j++ )
4165 liftgubconsidx = gubconsGFC1[j];
4166 assert(liftgubconsidx >= 0 && liftgubconsidx < ngubconss);
4176 assert(ngubconsGNC1 > 0);
4189 weight = weights[liftgubvars[0]];
4191 weightdiff2 = unfinished[ngubconsGNC1] - weight;
4193 for( w = ngubconsGNC1-1; w >= 1; w-- )
4195 weightdiff1 = weightdiff2;
4196 weightdiff2 = unfinished[w] - weight;
4198 if( unfinished[w] < weightdiff1 )
4199 unfinished[w] = weightdiff1;
4207 assert(minweights[0] == 0);
4228 weight = weights[liftvar];
4230 assert(liftvar >= 0 && liftvar < nvars);
4231 assert(capacity - weight >= 0);
4236 liftgubvars[nliftgubvars] = liftvar;
4242 if( capacity - fixedonesweight - weight < 0 )
4250 else if( minweights[*liftrhs] <= capacity - fixedonesweight - weight )
4259 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - fixedonesweight - weight);
4261 right = (*liftrhs) + 1;
4262 while( left < right - 1 )
4264 middle = (left + right) / 2;
4265 assert(0 <= middle && middle < minweightslen);
4266 if( minweights[middle] <= capacity - fixedonesweight - weight )
4271 assert(left == right - 1);
4272 assert(0 <= left && left < minweightslen);
4273 assert(minweights[left] <= capacity - fixedonesweight - weight);
4274 assert(left == minweightslen - 1 || minweights[left+1] > capacity - fixedonesweight - weight);
4278 assert(z <= *liftrhs);
4282 liftcoef = (*liftrhs) - z;
4283 liftcoefs[liftvar] = liftcoef;
4284 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
4287 (*cutact) += liftcoef * solvals[liftvar];
4290 sumliftcoef += liftcoefs[liftvar];
4296 assert(nliftgubvars > nliftgubC1);
4302 if( sumliftcoef == 0 )
4306 weight = weights[liftgubvars[0]];
4311 for( w = minweightslen-1; w >= 1; w-- )
4316 finished[w] =
MIN(finished[w], tmpval);
4319 minweights[w] =
MIN(minweights[w], tmpval);
4334 tmplen = minweightslen;
4335 tmpsize = minweightssize;
4337 tmplen = minweightslen;
4338 tmpsize = minweightssize;
4352 for( w = minweightslen-1; w >= 0; w-- )
4357 for( k = 0; k < nliftgubvars; k++ )
4359 liftcoef = liftcoefs[liftgubvars[k]];
4360 weight = weights[liftgubvars[k]];
4364 minfinished =
MIN(finished[w], weight);
4365 minminweight =
MIN(minweights[w], weight);
4367 finished[w] = minfinished;
4368 minweights[w] = minminweight;
4374 assert(w >= liftcoef);
4377 minfinished =
MIN(finished[w], tmpval);
4380 minminweight =
MIN(minweights[w], tmpval);
4382 finished[w] = minfinished;
4383 minweights[w] = minminweight;
4387 assert(minweights[0] == 0);
4389 assert(ngubconsGNC1 == 0);
4396 for( j = 0; j < ngubconsGC2; j++ )
4398 liftgubconsidx = gubconsGC2[j];
4400 assert(liftgubconsidx >=0 && liftgubconsidx < ngubconss);
4406 weight = weights[liftvar];
4408 assert(liftvar >= 0 && liftvar < nvars);
4416 right = minweightslen;
4417 while( left < right - 1 )
4419 middle = (left + right) / 2;
4420 assert(0 <= middle && middle < minweightslen);
4421 if( minweights[middle] <= capacity - fixedonesweight + weight )
4426 assert(left == right - 1);
4427 assert(0 <= left && left < minweightslen);
4428 assert(minweights[left] <= capacity - fixedonesweight + weight);
4429 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - fixedonesweight + weight);
4433 assert(z >= *liftrhs);
4436 liftcoef = z - (*liftrhs);
4437 liftcoefs[liftvar] = liftcoef;
4438 assert(liftcoef >= 0);
4441 fixedonesweight -= weight;
4444 (*liftrhs) += liftcoef;
4445 assert(*liftrhs >= alpha0);
4452 (*cutact) += liftcoef * solvals[liftvar];
4466 for( w = minweightslen - 1; w >= 0; w-- )
4470 min =
MIN(minweights[w], weight);
4471 minweights[w] = min;
4477 assert(w >= liftcoef);
4480 min =
MIN(minweights[w], tmpval);
4481 minweights[w] = min;
4485 assert(fixedonesweight == 0);
4486 assert(*liftrhs >= alpha0);
4489 for( j = 0; j < ngubconsGR; j++ )
4491 liftgubconsidx = gubconsGR[j];
4493 assert(liftgubconsidx >=0 && liftgubconsidx < ngubconss);
4503 weight = weights[liftvar];
4505 assert(liftvar >= 0 && liftvar < nvars);
4506 assert(capacity - weight >= 0);
4507 assert((*liftrhs) + 1 >= minweightslen || minweights[(*liftrhs) + 1] > capacity - weight);
4512 liftgubvars[nliftgubvars] = liftvar;
4518 if( minweights[*liftrhs] <= capacity - weight )
4527 right = (*liftrhs) + 1;
4528 while( left < right - 1 )
4530 middle = (left + right) / 2;
4531 assert(0 <= middle && middle < minweightslen);
4532 if( minweights[middle] <= capacity - weight )
4537 assert(left == right - 1);
4538 assert(0 <= left && left < minweightslen);
4539 assert(minweights[left] <= capacity - weight);
4540 assert(left == minweightslen - 1 || minweights[left + 1] > capacity - weight);
4544 assert(z <= *liftrhs);
4547 liftcoef = (*liftrhs) - z;
4548 liftcoefs[liftvar] = liftcoef;
4549 assert(liftcoef >= 0 && liftcoef <= (*liftrhs) + 1);
4552 (*cutact) += liftcoef * solvals[liftvar];
4555 sumliftcoef += liftcoefs[liftvar];
4560 assert(nliftgubvars >= 1);
4563 if( sumliftcoef == 0 )
4569 for( w = *liftrhs; w >= 0; w-- )
4571 for( k = 0; k < nliftgubvars; k++ )
4573 liftcoef = liftcoefs[liftgubvars[k]];
4574 weight = weights[liftgubvars[k]];
4578 min =
MIN(minweights[w], weight);
4579 minweights[w] = min;
4585 assert(w >= liftcoef);
4588 min =
MIN(minweights[w], tmpval);
4589 minweights[w] = min;
4593 assert(minweights[0] == 0);
4651 assert(scip !=
NULL);
4652 assert(vars !=
NULL);
4654 assert(weights !=
NULL);
4655 assert(capacity >= 0);
4656 assert(solvals !=
NULL);
4657 assert(covervars !=
NULL);
4658 assert(noncovervars !=
NULL);
4659 assert(ncovervars > 0 && ncovervars <= nvars);
4660 assert(nnoncovervars >= 0 && nnoncovervars <= nvars - ntightened);
4661 assert(ncovervars + nnoncovervars == nvars - ntightened);
4662 assert(liftcoefs !=
NULL);
4663 assert(cutact !=
NULL);
4678 for( j = 0; j < ncovervars; j++ )
4680 assert(liftcoefs[covervars[j]] == 0.0);
4681 liftcoefs[covervars[j]] = 1.0;
4682 sortkeys[j] = (
SCIP_Real) weights[covervars[j]];
4683 (*cutact) += solvals[covervars[j]];
4688 lambda = coverweight - capacity;
4692 maxweightsums[0] = 0;
4693 for( h = 1; h <= ncovervars; h++ )
4695 maxweightsums[h] = maxweightsums[h-1] + weights[covervars[h-1]];
4696 intervalends[h-1] = maxweightsums[h] - lambda;
4697 rhos[h-1] =
MAX(0, weights[covervars[h-1]] - weights[covervars[0]] + lambda);
4701 for( j = 0; j < nnoncovervars; j++ )
4702 sortkeys[j] = (
SCIP_Real) (weights[noncovervars[j]]);
4707 for( j = 0; j < nnoncovervars; j++ )
4713 liftvar = noncovervars[j];
4714 weight = weights[liftvar];
4716 while( intervalends[h] < weight )
4723 if( weight <= intervalends[h-1] + rhos[h] )
4727 tmp1 = (
SCIP_Real) (intervalends[h-1] + rhos[h] - weight);
4729 liftcoef = h - ( tmp1 / tmp2 );
4736 assert(liftcoefs[liftvar] == 0.0);
4737 liftcoefs[liftvar] = liftcoef;
4740 (*cutact) += liftcoef * solvals[liftvar];
4768 int* nonmincovervars,
4770 int nnonmincovervars,
4789 assert( cutoff !=
NULL );
4804 getPartitionCovervars(scip, solvals, mincovervars, nmincovervars, varsC1, varsC2, &nvarsC1, &nvarsC2);
4805 assert(nvarsC1 + nvarsC2 == nmincovervars);
4806 assert(nmincovervars > 0);
4807 assert(nvarsC1 >= 0);
4810 if( nvarsC1 < 2 && nvarsC2 > 0)
4813 assert(nvarsC1 >= 1);
4815 assert(nvarsC2 == 0 || nvarsC1 >= 1);
4822 assert(nvarsF + nvarsR == nnonmincovervars);
4823 assert(nvarsC1 + nvarsC2 + nvarsF + nvarsR == nvars - ntightened);
4826 if( gubset ==
NULL )
4845 varsF, varsR, nvarsC1, nvarsC2, nvarsF, nvarsR, nvarsC1 - 1, liftcoefs, &cutact, &liftrhs) );
4862 assert(nvars == gubset->
nvars);
4882 nvarsC2, nvarsF, nvarsR, gubconsGC1, gubconsGC2, gubconsGFC1, gubconsGR, &ngubconsGC1, &ngubconsGC2,
4883 &ngubconsGFC1, &ngubconsGR, &nconstightened, &maxgubvarssize) );
4899 gubconsGC2, gubconsGFC1, gubconsGR, ngubconsGC1, ngubconsGC2, ngubconsGFC1, ngubconsGR,
4900 MIN(nvarsC1 - 1, ngubconsGC1), liftcoefs, &cutact, &liftrhs, maxgubvarssize) );
4917 assert( cons ==
NULL || sepa ==
NULL );
4925 else if ( sepa !=
NULL )
4938 assert(nvarsC1 + nvarsC2 + nvarsF + nvarsR == nvars - ntightened);
4939 for( j = 0; j < nvarsC1; j++ )
4943 for( j = 0; j < nvarsC2; j++ )
4945 if( liftcoefs[varsC2[j]] > 0 )
4950 for( j = 0; j < nvarsF; j++ )
4952 if( liftcoefs[varsF[j]] > 0 )
4957 for( j = 0; j < nvarsR; j++ )
4959 if( liftcoefs[varsR[j]] > 0 )
5002 int* nonfeassetvars,
5004 int nnonfeassetvars,
5023 assert( cutoff !=
NULL );
5038 getPartitionCovervars(scip, solvals, feassetvars, nfeassetvars, varsT1, varsT2, &nvarsT1, &nvarsT2);
5039 assert(nvarsT1 + nvarsT2 == nfeassetvars);
5042 if( nvarsT1 == 0 && nvarsT2 > 0)
5045 assert(nvarsT1 == 1);
5047 assert(nvarsT2 == 0 || nvarsT1 > 0);
5054 assert(nvarsF + nvarsR == nnonfeassetvars);
5055 assert(nvarsT1 + nvarsT2 + nvarsF + nvarsR == nvars - ntightened);
5074 SCIP_CALL(
sequentialUpAndDownLifting(scip, vars, nvars, ntightened, weights, capacity, solvals, varsT1, varsT2, varsF, varsR,
5075 nvarsT1, nvarsT2, nvarsF, nvarsR, nvarsT1, liftcoefs, &cutact, &liftrhs) );
5084 assert( cons ==
NULL || sepa ==
NULL );
5092 else if ( sepa !=
NULL )
5105 assert(nvarsT1 + nvarsT2 + nvarsF + nvarsR == nvars - ntightened);
5106 for( j = 0; j < nvarsT1; j++ )
5110 for( j = 0; j < nvarsT2; j++ )
5112 if( liftcoefs[varsT2[j]] > 0 )
5117 for( j = 0; j < nvarsF; j++ )
5119 if( liftcoefs[varsF[j]] > 0 )
5124 for( j = 0; j < nvarsR; j++ )
5126 if( liftcoefs[varsR[j]] > 0 )
5169 int* nonmincovervars,
5171 int nnonmincovervars,
5182 assert( cutoff !=
NULL );
5200 nonmincovervars, nmincovervars, nnonmincovervars, mincoverweight, realliftcoefs, &cutact) );
5201 liftrhs = nmincovervars - 1;
5211 assert( cons ==
NULL || sepa ==
NULL );
5219 else if ( sepa !=
NULL )
5232 assert(nmincovervars + nnonmincovervars == nvars - ntightened);
5233 for( j = 0; j < nmincovervars; j++ )
5237 for( j = 0; j < nnonmincovervars; j++ )
5239 assert(
SCIPisFeasGE(scip, realliftcoefs[nonmincovervars[j]], 0.0));
5240 if(
SCIPisFeasGT(scip, realliftcoefs[nonmincovervars[j]], 0.0) )
5285 SORTKEYPAIR** sortkeypairs;
5292 assert(scip !=
NULL);
5293 assert(covervars !=
NULL);
5294 assert(noncovervars !=
NULL);
5295 assert(ncovervars !=
NULL);
5296 assert(*ncovervars > 0);
5297 assert(nnoncovervars !=
NULL);
5298 assert(*nnoncovervars >= 0);
5299 assert(coverweight !=
NULL);
5300 assert(*coverweight > 0);
5301 assert(*coverweight > capacity);
5304 nsortkeypairs = *ncovervars;
5312 assert(*ncovervars == nsortkeypairs);
5315 for( j = 0; j < *ncovervars; j++ )
5319 sortkeypairs[j]->key1 = solvals[covervars[j]];
5320 sortkeypairs[j]->key2 = (
SCIP_Real) weights[covervars[j]];
5325 for( j = 0; j < *ncovervars; j++ )
5329 sortkeypairs[j]->key1 = (solvals[covervars[j]] - 1.0) / ((
SCIP_Real) weights[covervars[j]]);
5330 sortkeypairs[j]->key2 = (
SCIP_Real) (-weights[covervars[j]]);
5333 SCIPsortPtrInt((
void**)sortkeypairs, covervars, compSortkeypairs, *ncovervars);
5337 minweight = weights[covervars[minweightidx]];
5338 for( j = 1; j < *ncovervars; j++ )
5340 if( weights[covervars[j]] <= minweight )
5343 minweight = weights[covervars[minweightidx]];
5346 assert(minweightidx >= 0 && minweightidx < *ncovervars);
5347 assert(minweight > 0 && minweight <= *coverweight);
5351 while( j < *ncovervars && ((*coverweight) - minweight > capacity) )
5353 assert(minweightidx >= j);
5354 assert(
checkMinweightidx(weights, capacity, covervars, *ncovervars, *coverweight, minweightidx, j));
5357 if( (*coverweight) - weights[covervars[j]] <= capacity )
5364 noncovervars[*nnoncovervars] = covervars[j];
5368 (*coverweight) -= weights[covervars[j]];
5369 for( k = j; k < (*ncovervars) - 1; k++ )
5370 covervars[k] = covervars[k+1];
5374 if( j == minweightidx )
5377 minweight = weights[covervars[minweightidx]];
5378 for( k = 1; k < *ncovervars; k++ )
5380 if( weights[covervars[k]] <= minweight )
5383 minweight = weights[covervars[minweightidx]];
5386 assert(minweight > 0 && minweight <= *coverweight);
5387 assert(minweightidx >= 0 && minweightidx < *ncovervars);
5391 assert(minweightidx > j);
5396 assert((*coverweight) > capacity);
5397 assert((*coverweight) - minweight <= capacity);
5400 for( j = nsortkeypairs-1; j >= 0; j-- )
5440 assert(scip !=
NULL);
5441 assert(covervars !=
NULL);
5442 assert(noncovervars !=
NULL);
5443 assert(ncovervars !=
NULL);
5444 assert(*ncovervars > 0);
5445 assert(nnoncovervars !=
NULL);
5446 assert(*nnoncovervars >= 0);
5447 assert(coverweight !=
NULL);
5448 assert(*coverweight > 0);
5449 assert(*coverweight > capacity);
5450 assert(*ncovervars + *nnoncovervars == nvars - ntightened);
5451 assert(cutoff !=
NULL);
5465 for( j = 0; j < *ncovervars; j++ )
5467 sortkeys[j] = solvals[covervars[j]];
5473 for( j = 0; j < *ncovervars; j++ )
5475 sortkeys[j] = (solvals[covervars[j]] - 1.0) / ((
SCIP_Real) weights[covervars[j]]);
5483 while( *ncovervars >= 2 )
5486 noncovervars[*nnoncovervars] = covervars[0];
5490 (*coverweight) -= weights[covervars[0]];
5491 for( k = 0; k < (*ncovervars) - 1; k++ )
5492 covervars[k] = covervars[k+1];
5495 assert(*ncovervars + *nnoncovervars == nvars - ntightened);
5496 if( (*coverweight) <= capacity )
5499 covervars, noncovervars, *ncovervars, *nnoncovervars, sol, cutoff, ncuts) );
5539 assert(scip !=
NULL);
5540 assert(capacity >= 0);
5541 assert(cutoff !=
NULL);
5542 assert(ncuts !=
NULL);
5549 assert(vars !=
NULL);
5551 assert(weights !=
NULL);
5571 SCIPdebugMsg(scip,
"separate cuts for knapsack constraint originated by cons <%s>:\n",
5573 for( i = 0; i <
nvars; ++i )
5602 modtransused =
TRUE;
5603 SCIP_CALL(
getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5604 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5606 assert(!coverfound || !fractional || ncovervars + nnoncovervars == nvars - ntightened);
5611 SCIPdebugMsg(scip,
" LMCI1-GUB terminated by no variable with fractional LP value.\n");
5626 &nnoncovervars, &coverweight, modtransused) );
5633 solvals, covervars, noncovervars, ncovervars, nnoncovervars, sol, gubset, cutoff, ncuts) );
5641 solvals, covervars, noncovervars, ncovervars, nnoncovervars, sol,
NULL, cutoff, ncuts) );
5661 modtransused =
TRUE;
5662 SCIP_CALL(
getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5663 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5664 assert(!coverfound || !fractional || ncovervars + nnoncovervars == nvars - ntightened);
5677 &nnoncovervars, &coverweight, modtransused) );
5681 solvals, covervars, noncovervars, ncovervars, nnoncovervars, sol,
NULL, cutoff, ncuts) );
5688 solvals, covervars, noncovervars, ncovervars, nnoncovervars, coverweight, sol, cutoff, ncuts) );
5703 modtransused =
FALSE;
5704 SCIP_CALL(
getCover(scip, vars, nvars, weights, capacity, solvals, covervars, noncovervars, &ncovervars,
5705 &nnoncovervars, &coverweight, &coverfound, modtransused, &ntightened, &fractional) );
5707 assert(!coverfound || ncovervars + nnoncovervars == nvars - ntightened);
5716 SCIP_CALL(
getFeasibleSet(scip, cons, sepa, vars, nvars, ntightened, weights, capacity, solvals, covervars, noncovervars,
5717 &ncovervars, &nnoncovervars, &coverweight, modtransused, sol, cutoff, ncuts) );
5764 assert(nknapvars > 0);
5765 assert(knapvars !=
NULL);
5766 assert(cutoff !=
NULL);
5789 if( conshdlr ==
NULL )
5791 noknapsackconshdlr =
TRUE;
5799 noknapsackconshdlr =
FALSE;
5801 assert(conshdlrdata !=
NULL);
5802 usegubs = conshdlrdata->usegubs;
5809 if( conshdlrdata->reals1size == 0 )
5812 conshdlrdata->reals1size = 1;
5813 conshdlrdata->reals1[0] = 0.0;
5816 assert(conshdlrdata->reals1size > 0);
5822 if( conshdlrdata->reals1size < nbinvars )
5824 int oldsize = conshdlrdata->reals1size;
5826 conshdlrdata->reals1size = nbinvars;
5828 BMSclearMemoryArray(&(conshdlrdata->reals1[oldsize]), conshdlrdata->reals1size - oldsize);
5830 binvals = conshdlrdata->reals1;
5834 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
5836 assert(binvals[tmp] == 0);
5854 for( i = 0; i < nknapvars; i++ )
5864 if( !noknapsackconshdlr )
5866 assert(tmpindices !=
NULL);
5873 else if( valscale * knapvals[i] > 0.0 )
5892 for( j = 0; j < nvlb; j++ )
5903 SCIPdebugMsg(scip,
"variable bound <%s>[%g,%g] >= %g<%s>[%g,%g] + %g implies local cutoff\n",
5910 vlbsol = bvlb[j] *
SCIPgetSolVal(scip, sol, zvlb[j]) + dvlb[j];
5911 if(
SCIPisGE(scip, vlbsol, bestlbsol) )
5923 if( bestlbtype == -1 )
5925 rhs -= valscale * knapvals[i] * bestlbsol;
5926 SCIPdebugMsg(scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with lower bound %.15g (rhs=%.15g)\n",
5932 rhs -= valscale * knapvals[i] * dvlb[bestlbtype];
5933 binvals[
SCIPvarGetProbindex(zvlb[bestlbtype])] += valscale * knapvals[i] * bvlb[bestlbtype];
5938 if( !noknapsackconshdlr )
5940 assert(tmpindices !=
NULL);
5945 SCIPdebugMsg(scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable lower bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
5948 SCIPgetSolVal(scip, sol, zvlb[bestlbtype]), dvlb[bestlbtype], rhs);
5961 assert(valscale * knapvals[i] < 0.0);
5972 for( j = 0; j < nvub; j++ )
5983 SCIPdebugMsg(scip,
"variable bound <%s>[%g,%g] <= %g<%s>[%g,%g] + %g implies local cutoff\n",
5990 vubsol = bvub[j] *
SCIPgetSolVal(scip, sol, zvub[j]) + dvub[j];
5991 if(
SCIPisLE(scip, vubsol, bestubsol) )
6003 if( bestubtype == -1 )
6005 rhs -= valscale * knapvals[i] * bestubsol;
6006 SCIPdebugMsg(scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with upper bound %.15g (rhs=%.15g)\n",
6012 rhs -= valscale * knapvals[i] * dvub[bestubtype];
6013 binvals[
SCIPvarGetProbindex(zvub[bestubtype])] += valscale * knapvals[i] * bvub[bestubtype];
6018 if( !noknapsackconshdlr )
6020 assert(tmpindices !=
NULL);
6025 SCIPdebugMsg(scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable upper bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6028 SCIPgetSolVal(scip, sol, zvub[bestubtype]), dvub[bestubtype], rhs);
6044 SCIPdebugMsg(scip,
" -> intscalar = %.15g\n", intscalar);
6054 rhs = rhs*intscalar;
6059 for( i = 0; i < nbinvars; i++ )
6071 SCIPdebugMsg(scip,
" -> positive scaled binary variable %+" SCIP_LONGINT_FORMAT
"<%s> (unscaled %.15g): not changed (rhs=%.15g)\n",
6081 SCIPdebugMsg(scip,
" -> negative scaled binary variable %+" SCIP_LONGINT_FORMAT
"<%s> (unscaled %.15g): substituted by (1 - <%s>) (rhs=%.15g)\n",
6089 consvals[nconsvars] = val;
6090 consvars[nconsvars] = var;
6098 assert(consvars !=
NULL);
6099 assert(consvals !=
NULL);
6108 for( i = 0; i < nconsvars; ++i )
6114 SCIPdebugMsgPrint(scip,
" <= %" SCIP_LONGINT_FORMAT
" (%.15g) [act: %.15g, min: %" SCIP_LONGINT_FORMAT
" max: %" SCIP_LONGINT_FORMAT
"]\n",
6115 capacity, rhs, act, minact, maxact);
6119 if( minact > capacity )
6121 SCIPdebugMsg(scip,
"minactivity of knapsack relaxation implies local cutoff\n");
6126 if( maxact > capacity )
6129 SCIP_CALL(
SCIPseparateKnapsackCuts(scip, cons, sepa, consvars, nconsvars, consvals, capacity, sol, usegubs, cutoff, ncuts) );
6135 if( noknapsackconshdlr)
6142 for( --tmp; tmp >= 0; --tmp)
6144 assert(tmpindices !=
NULL);
6145 binvals[tmpindices[tmp]] = 0;
6170 assert(ncuts !=
NULL);
6171 assert(cutoff !=
NULL);
6175 assert(consdata !=
NULL);
6191 consdata->capacity, sol, usegubs, cutoff, ncuts) );
6209 assert(consdata !=
NULL);
6214 if( consdata->row !=
NULL )
6223 consdata->capacity -= weight;
6234 consdata->vars[consdata->nvars] = var;
6235 consdata->weights[consdata->nvars] = weight;
6250 assert(conshdlrdata !=
NULL);
6253 conshdlrdata->eventhdlr, consdata->eventdata[consdata->nvars-1],
6254 &consdata->eventdata[consdata->nvars-1]->filterpos) );
6257 consdata->existmultaggr =
TRUE;
6261 consdata->presolvedtiming = 0;
6262 consdata->cliquesadded =
FALSE;
6268 consdata->sorted =
FALSE;
6269 consdata->cliquepartitioned =
FALSE;
6270 consdata->negcliquepartitioned =
FALSE;
6271 consdata->merged =
FALSE;
6289 assert(consdata !=
NULL);
6290 assert(0 <= pos && pos < consdata->nvars);
6292 var = consdata->vars[pos];
6293 assert(var !=
NULL);
6297 if( consdata->row !=
NULL )
6311 assert(conshdlrdata !=
NULL);
6313 conshdlrdata->eventhdlr, consdata->eventdata[pos], consdata->eventdata[pos]->filterpos) );
6317 consdata->presolvedtiming = 0;
6318 consdata->sorted = (consdata->sorted && pos == consdata->nvars - 1);
6325 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
6326 consdata->weights[pos] = consdata->weights[consdata->nvars-1];
6327 if( consdata->eventdata !=
NULL )
6328 consdata->eventdata[pos] = consdata->eventdata[consdata->nvars-1];
6334 if( consdata->cliquepartitioned )
6336 assert(consdata->cliquepartition !=
NULL);
6339 if( consdata->cliquepartition[consdata->nvars - 1] != consdata->nvars - 1 )
6343 oldcliqenum = consdata->cliquepartition[pos];
6344 consdata->cliquepartition[pos] = consdata->cliquepartition[consdata->nvars-1];
6347 if( consdata->cliquepartition[pos] > pos )
6348 consdata->cliquepartitioned =
FALSE;
6352 int cliquenumbefore;
6356 if( oldcliqenum > consdata->cliquepartition[pos] )
6358 for( i = 0; i < consdata->nvars; ++i )
6359 if( oldcliqenum == consdata->cliquepartition[i] )
6361 else if( oldcliqenum < consdata->cliquepartition[i] )
6363 consdata->cliquepartitioned =
FALSE;
6369 if( i == consdata->nvars )
6370 --(consdata->ncliques);
6374 else if( oldcliqenum < consdata->cliquepartition[pos] )
6376 cliquenumbefore = consdata->cliquepartition[pos] - 1;
6377 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->cliquepartition[i] < cliquenumbefore; --i );
6379 if( i < cliquenumbefore )
6380 consdata->cliquepartitioned =
FALSE;
6383 else if( pos == consdata->nvars - 1)
6385 cliquenumbefore = consdata->cliquepartition[pos];
6386 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->cliquepartition[i] < cliquenumbefore; --i );
6388 if( i < cliquenumbefore )
6389 --(consdata->ncliques);
6395 --(consdata->ncliques);
6398 if( consdata->negcliquepartitioned )
6400 assert(consdata->negcliquepartition !=
NULL);
6403 if( consdata->negcliquepartition[consdata->nvars-1] != consdata->nvars - 1 )
6407 oldcliqenum = consdata->negcliquepartition[pos];
6408 consdata->negcliquepartition[pos] = consdata->negcliquepartition[consdata->nvars-1];
6411 if( consdata->negcliquepartition[pos] > pos )
6412 consdata->negcliquepartitioned =
FALSE;
6416 int cliquenumbefore;
6420 if( oldcliqenum > consdata->negcliquepartition[pos] )
6422 for( i = 0; i < consdata->nvars; ++i )
6423 if( oldcliqenum == consdata->negcliquepartition[i] )
6425 else if( oldcliqenum < consdata->negcliquepartition[i] )
6427 consdata->negcliquepartitioned =
FALSE;
6433 if( i == consdata->nvars )
6434 --(consdata->nnegcliques);
6438 else if( oldcliqenum < consdata->negcliquepartition[pos] )
6440 cliquenumbefore = consdata->negcliquepartition[pos] - 1;
6441 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->negcliquepartition[i] < cliquenumbefore; --i );
6443 if( i < cliquenumbefore )
6444 consdata->negcliquepartitioned =
FALSE;
6447 else if( pos == consdata->nvars - 1)
6449 cliquenumbefore = consdata->negcliquepartition[pos];
6450 for( i = pos - 1; i >= 0 && i >= cliquenumbefore && consdata->negcliquepartition[i] < cliquenumbefore; --i );
6452 if( i < cliquenumbefore )
6453 --(consdata->nnegcliques);
6459 --(consdata->nnegcliques);
6462 --(consdata->nvars);
6478 assert(consdata !=
NULL);
6480 for( v = consdata->nvars-1; v >= 0; --v )
6482 if( consdata->weights[v] == 0 )
6504 assert(scip !=
NULL);
6505 assert(conshdlr !=
NULL);
6506 assert(conss !=
NULL);
6507 assert(nconss >= 0);
6511 for( i = 0; i < nconss; i++ )
6516 if( consdata->varsdeleted )
6519 for( v = consdata->nvars - 1; v >= 0; --v )
6526 consdata->varsdeleted =
FALSE;
6545 assert(scip !=
NULL);
6546 assert(cons !=
NULL);
6547 assert(cutoff !=
NULL);
6550 assert(consdata !=
NULL);
6554 if( consdata->merged )
6557 if( consdata->nvars <= 1 )
6559 consdata->merged =
TRUE;
6563 assert(consdata->vars !=
NULL || consdata->nvars == 0);
6567 consdata->cliquepartition, consdata->negcliquepartition, SCIPvarCompActiveAndNegated, consdata->nvars);
6570 consdata->sorted =
FALSE;
6572 v = consdata->nvars - 1;
6585 var1 = consdata->vars[v];
6593 assert(var1 !=
NULL);
6595 var2 = consdata->vars[prev];
6603 assert(var2 !=
NULL);
6608 if( negated1 == negated2 )
6611 consdataChgWeight(consdata, prev, consdata->weights[v] + consdata->weights[prev]);
6617 else if( consdata->weights[v] == consdata->weights[prev] )
6620 consdata->capacity -= consdata->weights[v];
6626 else if( consdata->weights[v] < consdata->weights[prev] )
6628 consdata->capacity -= consdata->weights[v];
6629 consdataChgWeight(consdata, prev, consdata->weights[prev] - consdata->weights[v]);
6630 assert(consdata->weights[prev] > 0);
6635 consdata->capacity -= consdata->weights[prev];
6637 assert(consdata->weights[v] > 0);
6640 if( consdata->nvars != v )
6644 if( prev == 0 || (var1 != consdata->vars[prev - 1] && var1 !=
SCIPvarGetNegatedVar(consdata->vars[prev - 1])) )
6648 consdata->cliquesadded =
FALSE;
6655 consdata->cliquesadded =
FALSE;
6661 consdata->merged =
TRUE;
6664 if( consdata->onesweightsum > consdata->capacity )
6666 SCIPdebugMsg(scip,
"merge multiples detected cutoff.\n");
6711 assert(consdata !=
NULL);
6713 nvars = consdata->nvars;
6714 vars = consdata->vars;
6726 for( v = 0; v <
nvars; ++v )
6732 assert(var !=
NULL);
6754 SCIPdebugMsg(scip,
"variable <%s> -> item size %" SCIP_LONGINT_FORMAT
", profit <%g>\n",
6768 items, solitems, nonsolitems, &nsolitems, &nnonsolitems, &solval, &success) );
6775 for( v = 0; v < nsolitems; ++v )
6777 var = vars[solitems[v]];
6778 assert(var !=
NULL);
6780 SCIPdebugMsg(scip,
"variable <%s> only locked up in knapsack constraints: dual presolve <%s>[%.15g,%.15g] >= 1.0\n",
6783 assert(!infeasible);
6788 for( v = 0; v < nnonsolitems; ++v )
6790 var = vars[nonsolitems[v]];
6791 assert(var !=
NULL);
6793 SCIPdebugMsg(scip,
"variable <%s> has no down locks: dual presolve <%s>[%.15g,%.15g] <= 0.0\n",
6796 assert(!infeasible);
6837 assert(scip !=
NULL);
6838 assert(cons !=
NULL);
6839 assert(conshdlrdata !=
NULL);
6842 assert(consdata !=
NULL);
6844 nvars = consdata->nvars;
6859 vars = consdata->vars;
6860 assert(vars !=
NULL);
6866 for( v = 0; v < nvars && applicable; ++v )
6870 assert(var !=
NULL);
6876 assert(var !=
NULL);
6888 weight = (
SCIP_Real)consdata->weights[v];
6895 scale = weight / -objval;
6899 else if(
SCIPisEQ(scip, -objval * scale, weight) )
6907 scale = weight / objval;
6909 else if( !
SCIPisEQ(scip, objval * scale, weight) )
6916 if(
SCIPisPositive(scip, scale) && conshdlrdata->detectcutoffbound )
6924 cutoffbound = (consdata->capacity - offset) / scale;
6931 SCIPdebugMsg(scip,
"constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
6936 SCIPdebugMsg(scip,
"update cutoff bound <%g>\n", cutoffbound);
6949 else if(
SCIPisNegative(scip, scale) && conshdlrdata->detectlowerbound )
6957 lowerbound = (consdata->capacity - offset) / scale;
6959 SCIPdebugMsg(scip,
"constraint <%s> is parallel to objective function and provids a lower bound <%g>\n",
6977 int* cliquestartposs,
6984 int* cliquepartition;
6995 assert(scip !=
NULL);
6996 assert(consdata !=
NULL);
6997 assert(vars !=
NULL);
6998 assert(weights !=
NULL);
6999 assert(cliquestartposs !=
NULL);
7001 origweights = consdata->weights;
7002 origvars = consdata->vars;
7003 norigvars = consdata->nvars;
7005 assert(origvars !=
NULL || norigvars == 0);
7006 assert(origweights !=
NULL || norigvars == 0);
7008 if( norigvars == 0 )
7011 if( usenegatedclique )
7013 assert(consdata->negcliquepartitioned);
7015 cliquepartition = consdata->negcliquepartition;
7016 ncliques = consdata->nnegcliques;
7020 assert(consdata->cliquepartitioned);
7022 cliquepartition = consdata->cliquepartition;
7023 ncliques = consdata->ncliques;
7026 assert(cliquepartition !=
NULL);
7027 assert(ncliques > 0);
7034 for( v = norigvars - 1; v >= 0; --v )
7036 assert(0 <= cliquepartition[v] && cliquepartition[v] < ncliques);
7037 ++(cliquecount[cliquepartition[v]]);
7051 for( c = 0; c < ncliques; ++c )
7060 varpointers[c] = (
SCIP_VAR**) (vars + nextpos);
7061 cliquestartposs[c] = nextpos;
7062 weightpointers[c] = (
SCIP_Longint*) (weights + nextpos);
7063 assert(cliquecount[c] > 0);
7064 nextpos += cliquecount[c];
7065 assert(nextpos > 0);
7067 assert(nextpos == norigvars);
7068 cliquestartposs[c] = nextpos;
7071 for( v = 0; v < norigvars; ++v )
7073 *(varpointers[cliquepartition[v]]) = origvars[v];
7074 ++(varpointers[cliquepartition[v]]);
7075 *(weightpointers[cliquepartition[v]]) = origweights[v];
7076 ++(weightpointers[cliquepartition[v]]);
7079 for( v = 0; v < norigvars; ++v )
7081 assert(vars[v] !=
NULL);
7082 assert(weights[v] > 0);
7107 assert(scip !=
NULL);
7108 assert(cons !=
NULL);
7111 assert(consdata !=
NULL);
7112 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
7114 if( cutoff !=
NULL )
7121 if ( consdata->onesweightsum > consdata->capacity )
7123 SCIPdebugMsg(scip,
"apply fixings detected cutoff.\n");
7125 if( cutoff !=
NULL )
7132 consdata->existmultaggr =
FALSE;
7135 while( v < consdata->nvars )
7139 var = consdata->vars[v];
7145 consdata->capacity -= consdata->weights[v];
7147 consdata->cliquesadded =
FALSE;
7162 weight = consdata->weights[v];
7166 assert(repvar !=
NULL);
7172 assert(workvar !=
NULL);
7215 assert((aggrvars !=
NULL && aggrscalars !=
NULL) || naggrvars == 0);
7219 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-integral value for weight*aggrconst = %g\n", weight*aggrconst);
7227 for( i = naggrvars - 1; i >= 0; --i )
7229 assert(aggrvars !=
NULL);
7230 assert(aggrscalars !=
NULL);
7234 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-binary variable <%s>\n", aggrvars[i]);
7239 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-integral value for weight*aggrscalars = %g\n", weight*aggrscalars[i]);
7246 assert(negvar !=
NULL);
7264 if( consdata->capacity < 0 )
7266 if( cutoff !=
NULL )
7274 else if( repvar != var )
7286 assert(consdata->onesweightsum == 0);
7288 SCIPdebugMsg(scip,
"after applyFixings, before merging:\n");
7294 if( cutoff !=
NULL && !(*cutoff) )
7297 SCIPdebugMsg(scip,
"after applyFixings and merging:\n");
7329 int* cliquestartposs;
7335 assert(scip !=
NULL);
7336 assert(cons !=
NULL);
7337 assert(cutoff !=
NULL);
7338 assert(redundant !=
NULL);
7339 assert(nfixedvars !=
NULL);
7342 assert(consdata !=
NULL);
7357 for( i = 0; i < consdata->nvars && consdata->merged; ++i )
7363 usenegatedclique = usenegatedclique && consdata->merged;
7368 cliquestartposs =
NULL;
7369 secondmaxweights =
NULL;
7371 nvars = consdata->nvars;
7377 localminweightsum = 0;
7386 if( usenegatedclique && nvars > 0 )
7390 assert(conshdlrdata !=
NULL);
7394 nnegcliques = consdata->nnegcliques;
7397 if( nnegcliques == nvars )
7400 usenegatedclique =
FALSE;
7416 for( c = 0; c < nnegcliques; ++c )
7418 cliqueendposs[c] = cliquestartposs[c+1] - 1;
7419 assert(cliqueendposs[c] - cliquestartposs[c] >= 0);
7433 if( nnegcliques - c == nvars - i )
7435 minweightsum += localminweightsum;
7436 localminweightsum = 0;
7444 if( cliquestartposs[c] == i )
7446 assert(myweights[i] > 0);
7448 minweightsum += localminweightsum;
7449 localminweightsum = 0;
7464 assert(myweights[i] > 0);
7468 assert(myweights[i] <= myweights[cliquestartposs[c - 1]]);
7475 cliquestartposs[c - 1] = i;
7481 if( secondmaxweights[c - 1] == 0 )
7482 secondmaxweights[c - 1] = myweights[i];
7484 localminweightsum += myweights[i];
7491 for( v = cliquestartposs[c - 1]; v < cliquestartposs[c]; ++v )
7530 localminweightsum = 0;
7532 i = cliqueendposs[c - 1];
7538 minweightsum += localminweightsum;
7540 SCIPdebugMsg(scip,
"knapsack constraint <%s> has minimum weight sum of <%" SCIP_LONGINT_FORMAT
">\n",
7544 if( !(*cutoff) && consdata->capacity >= minweightsum + consdata->onesweightsum )
7549 for( c = 0; c < nnegcliques; ++c )
7553 int endvarposclique;
7554 int startvarposclique;
7556 assert(myvars !=
NULL);
7557 assert(nnegcliques == consdata->nnegcliques);
7558 assert(myweights !=
NULL);
7559 assert(secondmaxweights !=
NULL);
7560 assert(cliquestartposs !=
NULL);
7562 endvarposclique = cliqueendposs[c];
7563 startvarposclique = cliquestartposs[c];
7565 maxvar = myvars[startvarposclique];
7571 maxcliqueweight = myweights[startvarposclique];
7572 maxvarfixed =
FALSE;
7577 if( consdata->onesweightsum + minweightsum + (maxcliqueweight - secondmaxweights[c]) > consdata->capacity )
7579 assert(maxcliqueweight >= secondmaxweights[c]);
7585 assert(!infeasible);
7593 else if( nnegcliques - c == nvars - startvarposclique )
7603 else if( consdata->onesweightsum + minweightsum + (maxcliqueweight - consdata->weights[nvars - 1]) <= consdata->capacity )
7607 for( i = endvarposclique; i > startvarposclique; --i )
7616 assert(maxcliqueweight >= myweights[i]);
7617 assert(i == endvarposclique || myweights[i] >= myweights[i+1]);
7625 if( maxvarfixed || consdata->onesweightsum + minweightsum - myweights[i] + maxcliqueweight > consdata->capacity )
7629 assert(!infeasible);
7637 minweightsum -= myweights[i];
7638 assert(minweightsum >= 0);
7646 for( ; i > startvarposclique; --i )
7649 SCIP_Bool exceedscapacity = consdata->onesweightsum + minweightsum - myweights[i] + maxcliqueweight > consdata->capacity;
7651 assert(i == endvarposclique || myweights[i] >= myweights[i+1]);
7652 assert(varisfixed || !exceedscapacity);
7664 assert(consdata->negcliquepartitioned || minweightsum == 0);
7668 assert(usenegatedclique || minweightsum == 0);
7670 if( consdata->capacity < minweightsum + consdata->onesweightsum )
7672 SCIPdebugMsg(scip,
" -> cutoff - fixed weight: %" SCIP_LONGINT_FORMAT
", capacity: %" SCIP_LONGINT_FORMAT
" \n",
7673 consdata->onesweightsum, consdata->capacity);
7688 for( i = 0; i < nvars && weight <= consdata->capacity; i++ )
7693 weight += consdata->weights[i];
7704 if( !usenegatedclique )
7706 assert(consdata->sorted);
7707 residualcapacity = consdata->capacity - consdata->onesweightsum;
7710 for( i = 0; i < nvars && consdata->weights[i] > residualcapacity; ++i )
7719 assert(consdata->onesweightsum + consdata->weights[i] > consdata->capacity);
7723 assert(!infeasible);
7734 SCIP_Longint unfixedweightsum = consdata->onesweightsum;
7737 for( i = 0; i <
nvars; ++i )
7741 unfixedweightsum += consdata->weights[i];
7744 if( unfixedweightsum > consdata->capacity )
7749 SCIPdebugMsg(scip,
" -> knapsack constraint <%s> is redundant: weightsum=%" SCIP_LONGINT_FORMAT
", unfixedweightsum=%" SCIP_LONGINT_FORMAT
", capacity=%" SCIP_LONGINT_FORMAT
"\n",
7750 SCIPconsGetName(cons), consdata->weightsum, unfixedweightsum, consdata->capacity);
7772 assert(scip !=
NULL);
7773 assert(cons !=
NULL);
7774 assert(ndelconss !=
NULL);
7775 assert(naddconss !=
NULL);
7778 assert(consdata !=
NULL);
7779 assert(consdata->nvars > 1);
7782 if( consdata->nvars == 2 )
7854 assert(scip !=
NULL);
7855 assert(cons !=
NULL);
7856 assert(nchgcoefs !=
NULL);
7857 assert(nchgsides !=
NULL);
7858 assert(naddconss !=
NULL);
7861 assert(consdata !=
NULL);
7862 assert(0 < frontsum && frontsum < consdata->weightsum);
7863 assert(0 < splitpos && splitpos < consdata->nvars);
7866 assert(conshdlrdata !=
NULL);
7868 vars = consdata->vars;
7869 weights = consdata->weights;
7870 nvars = consdata->nvars;
7871 capacity = consdata->capacity;
7877 for( w = nvars - 1; w > 0; --w )
7878 assert(weights[w] <= weights[w-1]);
7882 if( consdata->nvars - 1 == splitpos )
7885 assert(frontsum + weights[splitpos] > capacity);
7888 if( consdata->weightsum - weights[splitpos] <= capacity )
7896 for( w = nvars - 1; w > splitpos; --w )
7898 consdata->capacity -= weights[w];
7901 assert(w == splitpos);
7904 *nchgcoefs += (nvars - splitpos);
7908 for( ; w >= 0 && gcd > 1; --w )
7916 for( w = splitpos; w >= 0; --w )
7920 (*nchgcoefs) +=
nvars;
7922 consdata->capacity /= gcd;
7930 for( w = consdata->nvars - 1; w > 0; --w )
7931 assert(weights[w] <= weights[w - 1]);
7938 else if( conshdlrdata->disaggregation && frontsum + weights[splitpos + 1] <= capacity )
7944 len = nvars - (splitpos + 1);
7961 for( w = 0; w < len; ++w )
7963 assert(clqpart[w] >= 0 && clqpart[w] <= w);
7964 if( clqpart[w] == cliquenum )
7966 maxactduetoclq += weights[w + splitpos + 1];
7974 if( frontsum + maxactduetoclq <= capacity )
7980 assert(maxactduetoclq < weights[splitpos]);
7987 for( c = 0; c < nclq; ++c )
7990 for( w = 0; w < len; ++w )
7992 if( clqpart[w] == c )
7994 clqvars[nclqvars] = vars[w + splitpos + 1];
8020 for( w = nvars - 1; w > splitpos; --w )
8025 consdata->capacity -= maxactduetoclq;
8026 assert(frontsum <= consdata->capacity);
8029 assert(w == splitpos);
8032 weights = consdata->weights;
8036 for( ; w >= 0 && gcd > 1; --w )
8044 for( w = splitpos; w >= 0; --w )
8048 (*nchgcoefs) +=
nvars;
8050 consdata->capacity /= gcd;
8061 for( w = consdata->nvars - 1; w > 0; --w )
8062 assert(weights[w] <= weights[w - 1]);
8105 assert(scip !=
NULL);
8106 assert(cons !=
NULL);
8107 assert(ndelconss !=
NULL);
8108 assert(nchgcoefs !=
NULL);
8109 assert(nchgsides !=
NULL);
8110 assert(naddconss !=
NULL);
8113 assert(consdata !=
NULL);
8114 assert(consdata->nvars >= 2);
8115 assert(consdata->weightsum > consdata->capacity);
8117 noldchgcoefs = *nchgcoefs;
8118 vars = consdata->vars;
8119 weights = consdata->weights;
8120 nvars = consdata->nvars;
8121 capacity = consdata->capacity;
8125 for( v = 0; v < nvars && sum + weights[v] <= capacity; ++v )
8131 if( v == nvars - 1 )
8143 assert(consdata->nvars > 1);
8146 if( v == consdata->nvars - 1 )
8156 if( *nchgcoefs > noldchgcoefs )
8159 assert(vars == consdata->vars);
8160 assert(weights == consdata->weights);
8161 assert(nvars == consdata->nvars);
8162 assert(capacity == consdata->capacity);
8165 assert(conshdlrdata !=
NULL);
8170 if( consdata->cliquepartition[v] < v )
8179 maxactduetoclqfront = 0;
8181 clqpart = consdata->cliquepartition;
8185 for( w = 0; w <
nvars; ++w )
8187 assert(clqpart[w] >= 0 && clqpart[w] <= w);
8188 if( clqpart[w] == cliquenum )
8190 if( maxactduetoclqfront + weights[w] <= capacity )
8192 maxactduetoclqfront += weights[w];
8198 sumfront += weights[w];
8205 if( conshdlrdata->disaggregation && w == nvars )
8212 assert(maxactduetoclqfront <= capacity);
8216 ncliques = consdata->ncliques;
8221 for( c = 0; c < ncliques; ++c )
8224 for( w = 0; w <
nvars; ++w )
8226 if( clqpart[w] == c )
8228 clqvars[nclqvars] = vars[w];
8262 if( w > v && w < nvars - 1 )
8284 assert(nchgcoefs !=
NULL);
8285 assert(nchgsides !=
NULL);
8289 assert(consdata !=
NULL);
8290 assert(consdata->row ==
NULL);
8291 assert(consdata->onesweightsum == 0);
8292 assert(consdata->weightsum > consdata->capacity);
8293 assert(consdata->nvars >= 1);
8298 gcd = consdata->weights[consdata->nvars-1];
8299 for( i = consdata->nvars-2; i >= 0 && gcd >= 2; --i )
8311 for( i = 0; i < consdata->nvars; ++i )
8315 consdata->capacity /= gcd;
8316 (*nchgcoefs) += consdata->nvars;
8321 for( i = consdata->nvars - 1; i > 0; --i )
8322 assert(consdata->weights[i] <= consdata->weights[i - 1]);
8324 consdata->sorted =
TRUE;
8372 assert(scip !=
NULL);
8373 assert(cons !=
NULL);
8374 assert(ndelconss !=
NULL);
8375 assert(nchgcoefs !=
NULL);
8376 assert(nchgsides !=
NULL);
8377 assert(naddconss !=
NULL);
8380 oldnchgsides = *nchgsides;
8384 assert(consdata !=
NULL);
8385 assert(consdata->weightsum > consdata->capacity);
8386 assert(consdata->nvars >= 2);
8387 assert(consdata->sorted);
8390 assert(consdata->merged);
8392 nvars = consdata->nvars;
8393 weights = consdata->weights;
8394 capacity = consdata->capacity;
8396 oldnchgcoefs = *nchgcoefs;
8399 if( weights[nvars - 1] + weights[nvars - 2] > capacity )
8426 if( consdata->weightsum - weights[nvars - 1] <= consdata->capacity )
8436 if( consdata->weightsum - capacity > weights[0] + weights[1] )
8457 while( v < nvars && weights[v] + weights[nvars - 1] > capacity )
8461 assert(vbig < nvars - 1);
8465 while( v < nvars && exceedsum <= capacity )
8467 exceedsum += weights[v];
8472 if( exceedsum > capacity )
8474 assert(vbig > 0 || v < nvars);
8480 assert(newweight > 0);
8483 for( v = 0; v < vbig; ++v )
8485 if( weights[v] > newweight )
8493 for( ; v <
nvars; ++v )
8495 if( weights[v] > 1 )
8502 consdata->capacity = newweight;
8508 for( v = nvars - 1; v > 0; --v )
8509 assert(weights[v] <= weights[v-1]);
8520 int nexceed = v - vbig;
8522 assert(nexceed > 1);
8525 for( w = nvars - 1; w >= nvars - nexceed; --w )
8526 exceedsumback += weights[w];
8533 if( exceedsumback > capacity )
8538 assert(exceedsumback - weights[nvars - 1] <= capacity);
8541 for( v = 0; v < vbig; ++v )
8543 if( weights[v] > newweight )
8551 for( ; v <
nvars; ++v )
8553 if( weights[v] > 1 )
8560 consdata->capacity = newweight;
8566 for( v = nvars - 1; v > 0; --v )
8567 assert(weights[v] <= weights[v-1]);
8578 assert(vbig > 0 && vbig < nvars);
8590 if( weights[vbig - 1] > (
SCIP_Longint)nvars - vbig || weights[vbig] > 1 )
8596 for( v = 0; v < vbig; ++v )
8597 resweightsum -= weights[v];
8599 assert(exceedsum == resweightsum);
8601 assert(newweight > 0);
8604 for( v = 0; v < vbig; ++v )
8606 if( weights[v] > newweight )
8614 for( ; v <
nvars; ++v )
8616 if( weights[v] > 1 )
8623 consdata->capacity = newweight;
8629 for( v = nvars - 1; v > 0; --v )
8630 assert(weights[v] <= weights[v-1]);
8638 dualcapacity = consdata->weightsum - capacity;
8648 while( weights[v] > dualcapacity )
8650 reductionsum += (weights[v] - dualcapacity);
8658 while( v < nvars && weights[v] == dualcapacity )
8666 if( v >= nvars - 1 )
8669 if( v == nvars - 1 )
8682 if( weights[nvars - 1] + weights[nvars - 2] >= dualcapacity )
8696 if( v > 0 && weights[nvars - 2] > 1 )
8701 for( w = 0; w < v; ++w )
8703 if( weights[w] > 2 )
8710 assert(weights[0] == 2);
8711 assert(weights[v - 1] == 2);
8717 for( w = v; w <
nvars; ++w )
8719 if( weights[w] > 1 )
8725 assert(ncoefchg > 0);
8727 (*nchgcoefs) += ncoefchg;
8730 consdata->capacity = (-2 + v * 2 + nvars - v);
8731 assert(consdata->capacity > 0);
8732 assert(weights[0] <= consdata->capacity);
8733 assert(consdata->weightsum > consdata->capacity);
8739 assert(weights[nvars - 2] == 1);
8753 assert(weights[nvars - 1] + weights[nvars - 2] <= capacity);
8761 while( weights[v] > newweight )
8763 reductionsum += (weights[v] - newweight);
8768 (*nchgcoefs) += (v - startv);
8771 while( weights[v] == newweight )
8776 for( w = v; w <
nvars; ++w )
8777 restsumweights += weights[w];
8780 restsumweights = consdata->weightsum;
8782 if( restsumweights < dualcapacity )
8792 for( w = nvars - 1; w >= v; --w )
8800 for( ; w >= 0; --w )
8801 assert(weights[w] == dualcapacity);
8819 if( weights[v] > 1 || (weights[startv] > (
SCIP_Longint)nvars - v) || (startv > 0 && weights[0] == (
SCIP_Longint)nvars - v + 1) )
8824 for( w = nvars - 1; w >= v; --w )
8826 if( weights[w] > 1 )
8837 assert(newweight > 1);
8838 for( ; w >= startv; --w )
8840 if( weights[w] > newweight )
8846 assert(weights[w] == newweight);
8851 assert(newweight > 2);
8852 for( ; w >= 0; --w )
8854 if( weights[w] > newweight )
8860 assert(weights[w] == newweight);
8865 if( consdata->capacity > newcap )
8867 consdata->capacity = newcap;
8871 assert(consdata->capacity == newcap);
8873 assert(weights[v] == 1 && (weights[startv] == (
SCIP_Longint)nvars - v) && (startv == 0 || weights[0] == (
SCIP_Longint)nvars - v + 1));
8876 assert(consdata->weightsum - consdata->capacity == (
SCIP_Longint)nvars - v + 1);
8882 for( w = nvars - 1; w > 0; --w )
8883 assert(weights[w] <= weights[w - 1]);
8890 while( end >= 0 && weights[end] == weights[end + 1] )
8902 if( 2 * weights[end] > dualcapacity )
8907 for( w = end + 1; w <
nvars; ++w )
8908 restsumweights += weights[w];
8910 if( restsumweights * 2 <= dualcapacity )
8913 while( v < end && restsumweights + weights[v] >= dualcapacity )
8920 if( (dualcapacity & 1) == 0 )
8922 newweight = dualcapacity / 2;
8925 for( ; v <= end; ++v )
8927 if( weights[v] > newweight )
8929 reductionsum += (weights[v] - newweight);
8944 for( w = 0; w < v; ++w )
8949 newweight = dualcapacity;
8951 for( ; v <= end; ++v )
8953 reductionsum += (2 * weights[v] - newweight);
8958 for( w = end + 1; w <
nvars; ++w )
8962 (*nchgcoefs) +=
nvars;
8965 consdata->capacity *= 2;
8980 for( k = 0; k < 4; ++k )
8986 sumcoef = weights[nvars - 1] + weights[nvars - 2];
8990 sumcoef = weights[nvars - 1] + weights[nvars - 3];
8994 if( weights[nvars - 1] + weights[nvars - 4] < weights[nvars - 2] + weights[nvars - 3] )
8997 sumcoef = weights[nvars - 1] + weights[nvars - 4];
9001 sumcoefcase =
FALSE;
9002 sumcoef = weights[nvars - 2] + weights[nvars - 3];
9009 sumcoef =
MIN(weights[nvars - 1] + weights[nvars - 5], weights[nvars - 2] + weights[nvars - 3]);
9013 sumcoef =
MIN(weights[nvars - 1] + weights[nvars - 4], weights[nvars - 1] + weights[nvars - 2] + weights[nvars - 3]);
9021 minweight = weights[end];
9022 while( minweight <= sumcoef )
9024 newweight = dualcapacity - minweight;
9030 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9032 reductionsum += (weights[v] - newweight);
9037 (*nchgcoefs) += (v - startv);
9040 while( weights[v] + minweight == dualcapacity )
9048 while( end >= 0 && weights[end] == weights[end + 1] )
9054 minweight = weights[end];
9061 if( sumcoef < minweight )
9063 minweight = sumcoef;
9064 newweight = dualcapacity - minweight;
9069 while( weights[v] + minweight > dualcapacity && 2 * minweight <= dualcapacity )
9071 reductionsum += (weights[v] - newweight);
9076 (*nchgcoefs) += (v - startv);
9079 while( weights[v] + minweight == dualcapacity )
9090 if( 2 * weights[end] > dualcapacity )
9095 for( w = end + 1; w <
nvars; ++w )
9096 restsumweights += weights[w];
9098 if( restsumweights * 2 <= dualcapacity )
9101 while( v < end && restsumweights + weights[v] >= dualcapacity )
9108 if( (dualcapacity & 1) == 0 )
9110 newweight = dualcapacity / 2;
9113 for( ; v <= end; ++v )
9115 if( weights[v] > newweight )
9117 reductionsum += (weights[v] - newweight);
9132 for( w = 0; w < v; ++w )
9137 newweight = dualcapacity;
9139 for( ; v <= end; ++v )
9141 reductionsum += (2 * weights[v] - newweight);
9146 for( w = end + 1; w <
nvars; ++w )
9150 (*nchgcoefs) +=
nvars;
9153 consdata->capacity *= 2;
9162 if( 2 * sumcoef > dualcapacity )
9171 if( reductionsum > 0 )
9175 consdata->capacity -= reductionsum;
9178 assert(consdata->weightsum - dualcapacity == consdata->capacity);
9180 assert(weights[0] <= consdata->capacity);
9186 for( w = nvars - 1; w > 0; --w )
9187 assert(weights[w] <= weights[w - 1]);
9190 if( oldnchgcoefs < *nchgcoefs )
9199 assert(oldnchgcoefs == *nchgcoefs);
9200 assert(oldnchgsides == *nchgsides);
9226 assert(scip !=
NULL);
9227 assert(cons !=
NULL);
9228 assert(nfixedvars !=
NULL);
9229 assert(ndelconss !=
NULL);
9230 assert(nchgcoefs !=
NULL);
9233 assert(consdata !=
NULL);
9235 nvars = consdata->nvars;
9240 assert(consdata->capacity >= 0);
9251 vars = consdata->vars;
9252 weights = consdata->weights;
9253 capacity = consdata->capacity;
9257 while( v < nvars && weights[v] > capacity )
9260 assert(!infeasible);
9280 for( --v; v >= 0; --v )
9288 assert(vars == consdata->vars);
9289 assert(weights == consdata->weights);
9291 assert(consdata->sorted);
9292 assert(weights[0] <= capacity);
9354 assert(scip !=
NULL);
9355 assert(cons !=
NULL);
9356 assert(nfixedvars !=
NULL);
9357 assert(ndelconss !=
NULL);
9358 assert(nchgcoefs !=
NULL);
9359 assert(nchgsides !=
NULL);
9360 assert(naddconss !=
NULL);
9361 assert(cutoff !=
NULL);
9365 assert( consdata !=
NULL );
9371 assert(consdata->merged);
9375 assert(consdata->capacity >= 0);
9397 weights = consdata->weights;
9398 nvars = consdata->nvars;
9402 for( v = nvars - 1; v > 0; --v )
9403 assert(weights[v] <= weights[v-1]);
9407 gcd = weights[nvars - 1];
9408 for( v = nvars - 2; v >= 0 && gcd > 1; --v )
9416 for( v = nvars - 1; v >= 0; --v )
9420 (*nchgcoefs) +=
nvars;
9422 consdata->capacity /= gcd;
9425 assert(consdata->nvars == nvars);
9431 for( v = nvars - 1; v > 0; --v )
9432 assert(weights[v] <= weights[v-1]);
9441 vars = consdata->vars;
9442 weights = consdata->weights;
9443 nvars = consdata->nvars;
9446 if( weights[nvars - 1] == 1 && weights[nvars - 2] == 1 )
9453 while( weights[v] == consdata->capacity )
9460 if( v == nvars - 1 )
9472 for( v = nvars - 1; v >= offsetv; --v )
9474 weight = weights[v];
9475 assert(weight >= 1);
9502 if( v == nvars - 2 )
9508 if( candpos == v + 1 && candpos2 == v + 2 )
9510 assert(candpos2 == nvars - 1);
9535 assert(((candpos >= offsetv) || (candpos == -1 && offsetv > 0)) && candpos < nvars);
9538 rest = consdata->capacity % gcd;
9548 consdata->capacity -= rest;
9552 for( v = 0; v < offsetv; ++v )
9557 *nchgcoefs += offsetv;
9562 restweight = weights[candpos] % gcd;
9563 assert(restweight >= 1);
9564 assert(restweight < gcd);
9567 if( restweight > rest )
9568 newweight = weights[candpos] - restweight + gcd;
9570 newweight = weights[candpos] - restweight;
9574 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);
9579 if( newweight == 0 && offsetv > 0 )
9585 consdata->capacity -= rest;
9589 for( v = 0; v < offsetv; ++v )
9594 *nchgcoefs += offsetv;
9597 if( newweight == 0 )
9601 assert(consdata->nvars == nvars - 1);
9611 assert(consdata->vars == vars);
9612 assert(consdata->nvars == nvars);
9613 assert(consdata->weights == weights);
9617 for( v = nvars - 1; v >= 0; --v )
9621 (*nchgcoefs) +=
nvars;
9623 consdata->capacity /= gcd;
9628 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));
9630 while( nvars >= 2 );
9657 assert(liftcands !=
NULL);
9658 assert(liftcands[value] !=
NULL);
9659 assert(nliftcands !=
NULL);
9660 assert(firstidxs !=
NULL);
9661 assert(firstidxs[value] !=
NULL);
9662 assert(zeroweightsums !=
NULL);
9663 assert(zeroweightsums[value] !=
NULL);
9664 assert(zeroitems !=
NULL);
9665 assert(nextidxs !=
NULL);
9666 assert(zeroitemssize !=
NULL);
9667 assert(nzeroitems !=
NULL);
9668 assert(*nzeroitems <= *zeroitemssize);
9670 assert(memlimitreached !=
NULL);
9672 nzeros = *nzeroitems;
9675 if( nzeros == *zeroitemssize )
9682 SCIPdebugMsg(scip,
"memory limit of %d bytes reached in knapsack preprocessing - abort collecting zero items\n",
9684 *memlimitreached =
TRUE;
9687 *zeroitemssize *= 2;
9692 assert(nzeros < *zeroitemssize);
9694 if( *memlimitreached )
9695 *memlimitreached =
FALSE;
9698 (*zeroitems)[nzeros] = knapsackidx;
9699 (*nextidxs)[nzeros] = firstidxs[value][probindex];
9700 if( firstidxs[value][probindex] == 0 )
9702 liftcands[value][nliftcands[value]] = probindex;
9703 ++nliftcands[value];
9705 firstidxs[value][probindex] = nzeros;
9707 zeroweightsums[value][probindex] += knapsackweight;
9712 #define MAX_CLIQUELENGTH 50 9768 assert(nchgcoefs !=
NULL);
9772 assert(consdata !=
NULL);
9773 assert(consdata->row ==
NULL);
9774 assert(consdata->weightsum > consdata->capacity);
9775 assert(consdata->nvars > 0);
9776 assert(consdata->merged);
9778 nvars = consdata->nvars;
9792 assert(nbinvars > 0);
9797 assert(conshdlr !=
NULL);
9799 assert(conshdlrdata !=
NULL);
9806 assert(conshdlrdata->ints1size > 0);
9807 assert(conshdlrdata->ints2size > 0);
9808 assert(conshdlrdata->longints1size > 0);
9809 assert(conshdlrdata->longints2size > 0);
9815 if( conshdlrdata->ints1size < nbinvars )
9817 int oldsize = conshdlrdata->ints1size;
9819 conshdlrdata->ints1size = nbinvars;
9823 if( conshdlrdata->ints2size < nbinvars )
9825 int oldsize = conshdlrdata->ints2size;
9827 conshdlrdata->ints2size = nbinvars;
9831 if( conshdlrdata->longints1size < nbinvars )
9833 int oldsize = conshdlrdata->longints1size;
9835 conshdlrdata->longints1size = nbinvars;
9837 BMSclearMemoryArray(&(conshdlrdata->longints1[oldsize]), conshdlrdata->longints1size - oldsize);
9839 if( conshdlrdata->longints2size < nbinvars )
9841 int oldsize = conshdlrdata->longints2size;
9843 conshdlrdata->longints2size = nbinvars;
9845 BMSclearMemoryArray(&(conshdlrdata->longints2[oldsize]), conshdlrdata->longints2size - oldsize);
9848 firstidxs[0] = conshdlrdata->ints1;
9849 firstidxs[1] = conshdlrdata->ints2;
9850 zeroweightsums[0] = conshdlrdata->longints1;
9851 zeroweightsums[1] = conshdlrdata->longints2;
9855 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
9857 assert(firstidxs[0][tmp] == 0);
9858 assert(firstidxs[1][tmp] == 0);
9859 assert(zeroweightsums[0][tmp] == 0);
9860 assert(zeroweightsums[1][tmp] == 0);
9873 assert(conshdlrdata->bools1size > 0);
9874 assert(conshdlrdata->bools2size > 0);
9880 if( conshdlrdata->bools1size < nbinvars )
9882 int oldsize = conshdlrdata->bools1size;
9884 conshdlrdata->bools1size = nbinvars;
9886 BMSclearMemoryArray(&(conshdlrdata->bools1[oldsize]), conshdlrdata->bools1size - oldsize);
9888 if( conshdlrdata->bools2size < nbinvars )
9890 int oldsize = conshdlrdata->bools2size;
9892 conshdlrdata->bools2size = nbinvars;
9894 BMSclearMemoryArray(&(conshdlrdata->bools2[oldsize]), conshdlrdata->bools2size - oldsize);
9897 zeroiteminserted[0] = conshdlrdata->bools1;
9898 zeroiteminserted[1] = conshdlrdata->bools2;
9902 for( tmp = nbinvars - 1; tmp >= 0; --tmp )
9904 assert(zeroiteminserted[0][tmp] == 0);
9905 assert(zeroiteminserted[1][tmp] == 0);
9918 memlimitreached =
FALSE;
9919 for( i = 0; i < consdata->nvars && !memlimitreached; ++i )
9932 var = consdata->vars[i];
9933 weight = consdata->weights[i];
9937 assert(0 <= varprobindex && varprobindex < nbinvars);
9940 zeroweightsums[!value][varprobindex] += weight;
9941 tmpboolindices3[tmp3] = !value;
9942 tmpindices3[tmp3] = varprobindex;
9952 assert(0 <= probindex && probindex < nbinvars);
9957 assert( !zeroiteminserted[implvalue][probindex] );
9959 if( firstidxs[implvalue][probindex] == 0 )
9961 tmpboolindices2[tmp2] = implvalue;
9962 tmpindices2[tmp2] = probindex;
9966 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue, i, weight,
9967 &memlimitreached) );
9968 zeroiteminserted[implvalue][probindex] =
TRUE;
9969 tmpboolindices[tmp] = implvalue;
9970 tmpindices[tmp] = probindex;
9977 for( j = 0; j < ncliques && !memlimitreached; ++j )
9993 for( k = ncliquevars - 1; k >= 0; --k )
9998 if( var == cliquevars[k] )
10002 if( probindex == -1 )
10005 assert(0 <= probindex && probindex < nbinvars);
10006 implvalue = cliquevalues[k];
10009 if( !zeroiteminserted[implvalue][probindex] )
10011 if( firstidxs[implvalue][probindex] == 0 )
10013 tmpboolindices2[tmp2] = implvalue;
10014 tmpindices2[tmp2] = probindex;
10019 &zeroitems, &nextidxs, &zeroitemssize, &nzeroitems, probindex, implvalue, i, weight,
10020 &memlimitreached) );
10021 zeroiteminserted[implvalue][probindex] =
TRUE;
10022 tmpboolindices[tmp] = implvalue;
10023 tmpindices[tmp] = probindex;
10026 if( memlimitreached )
10032 for( --tmp; tmp >= 0; --tmp)
10033 zeroiteminserted[tmpboolindices[tmp]][tmpindices[tmp]] =
FALSE;
10038 assert(consdata->sorted);
10041 assert(conshdlrdata->bools3size > 0);
10047 if( conshdlrdata->bools3size < consdata->nvars )
10049 int oldsize = conshdlrdata->bools3size;
10051 conshdlrdata->bools3size = consdata->nvars;;
10053 BMSclearMemoryArray(&(conshdlrdata->bools3[oldsize]), conshdlrdata->bools3size - oldsize);
10056 cliqueused = conshdlrdata->bools3;
10060 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10061 assert(cliqueused[tmp] == 0);
10064 maxcliqueweightsum = 0;
10068 for( i = 0; i < consdata->nvars; ++i )
10070 cliquenum = consdata->cliquepartition[i];
10071 assert(0 <= cliquenum && cliquenum < consdata->nvars);
10073 if( !cliqueused[cliquenum] )
10075 maxcliqueweightsum += consdata->weights[i];
10076 cliqueused[cliquenum] =
TRUE;
10077 tmpindices[tmp] = cliquenum;
10082 for( --tmp; tmp >= 0; --tmp)
10083 cliqueused[tmp] =
FALSE;
10085 assert(conshdlrdata->bools4size > 0);
10091 if( conshdlrdata->bools4size < consdata->nvars )
10093 int oldsize = conshdlrdata->bools4size;
10095 conshdlrdata->bools4size = consdata->nvars;
10100 itemremoved = conshdlrdata->bools4;
10104 for( tmp = consdata->nvars - 1; tmp >= 0; --tmp )
10105 assert(itemremoved[tmp] == 0);
10116 for( val = 0; val < 2 && addweightsum < consdata->capacity; ++val )
10118 for( i = 0; i < nliftcands[val] && addweightsum < consdata->capacity; ++i )
10127 probindex = liftcands[val][i];
10128 assert(0 <= probindex && probindex < nbinvars);
10131 if( firstidxs[val][probindex] == 0
10132 || maxcliqueweightsum - zeroweightsums[val][probindex] + addweightsum >= consdata->capacity )
10136 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10138 assert(0 < idx && idx < nzeroitems);
10139 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10140 itemremoved[zeroitems[idx]] =
TRUE;
10144 cliqueweightsum = addweightsum;
10145 for( j = 0; j < consdata->nvars; ++j )
10147 cliquenum = consdata->cliquepartition[j];
10148 assert(0 <= cliquenum && cliquenum < consdata->nvars);
10149 if( !itemremoved[j] )
10151 if( !cliqueused[cliquenum] )
10153 cliqueweightsum += consdata->weights[j];
10154 cliqueused[cliquenum] =
TRUE;
10155 tmpindices[tmp] = cliquenum;
10159 if( cliqueweightsum >= consdata->capacity )
10165 if( cliqueweightsum < consdata->capacity )
10171 assert(naddvars < 2*nbinvars);
10172 var = binvars[probindex];
10177 weight = consdata->capacity - cliqueweightsum;
10178 addvars[naddvars] = var;
10179 addweights[naddvars] = weight;
10180 addweightsum += weight;
10183 SCIPdebugMsg(scip,
"knapsack constraint <%s>: adding lifted item %" SCIP_LONGINT_FORMAT
"<%s>\n",
10188 for( idx = firstidxs[val][probindex]; idx != 0; idx = nextidxs[idx] )
10190 assert(0 < idx && idx < nzeroitems);
10191 assert(0 <= zeroitems[idx] && zeroitems[idx] < consdata->nvars);
10192 itemremoved[zeroitems[idx]] =
FALSE;
10195 for( --tmp; tmp >= 0; --tmp)
10196 cliqueused[tmpindices[tmp]] =
FALSE;
10202 for( --tmp3; tmp3 >= 0; --tmp3)
10203 zeroweightsums[tmpboolindices3[tmp3]][tmpindices3[tmp3]] = 0;
10206 for( --tmp2; tmp2 >= 0; --tmp2)
10208 zeroweightsums[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10209 firstidxs[tmpboolindices2[tmp2]][tmpindices2[tmp2]] = 0;
10218 for( i = 0; i < naddvars; ++i )
10222 *nchgcoefs += naddvars;
10315 assert(nchgcoefs !=
NULL);
10316 assert(nchgsides !=
NULL);
10320 assert(conshdlrdata !=
NULL);
10323 assert(consdata !=
NULL);
10324 assert(consdata->row ==
NULL);
10325 assert(consdata->onesweightsum == 0);
10326 assert(consdata->weightsum > consdata->capacity);
10327 assert(consdata->nvars > 0);
10338 assert(consdata->merged);
10343 for( i = 0; i < consdata->nvars; ++i )
10347 weight = consdata->weights[i];
10348 if( consdata->weightsum - weight < consdata->capacity )
10350 newweight = consdata->weightsum - consdata->capacity;
10352 consdata->capacity -= (weight - newweight);
10355 assert(!consdata->sorted);
10356 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",
10358 consdata->capacity + (weight-newweight), consdata->capacity);
10364 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10368 if( consdata->weightsum <= consdata->capacity )
10372 while( pos < consdata->nvars && consdata->weights[pos] == consdata->capacity )
10376 weights = consdata->weights;
10377 nvars = consdata->nvars;
10378 capacity = consdata->capacity;
10381 pos < nvars && weights[pos] + weights[pos + 1] > capacity )
10388 for( k = 0; k < 4; ++k )
10390 newweight = capacity - sumcoef;
10396 sumcoef = weights[nvars - 1];
10397 backpos = nvars - 1;
10400 sumcoef = weights[nvars - 2];
10401 backpos = nvars - 2;
10404 if( weights[nvars - 3] < weights[nvars - 1] + weights[nvars - 2] )
10406 sumcoefcase =
TRUE;
10407 sumcoef = weights[nvars - 3];
10408 backpos = nvars - 3;
10412 sumcoefcase =
FALSE;
10413 sumcoef = weights[nvars - 1] + weights[nvars - 2];
10414 backpos = nvars - 2;
10421 if( weights[nvars - 4] < weights[nvars - 1] + weights[nvars - 2] )
10423 sumcoef = weights[nvars - 4];
10424 backpos = nvars - 4;
10428 sumcoef = weights[nvars - 1] + weights[nvars - 2];
10429 backpos = nvars - 2;
10434 sumcoef = weights[nvars - 3];
10435 backpos = nvars - 3;
10440 if( backpos <= pos )
10444 maxweight = weights[pos];
10446 while( 2 * maxweight > capacity && maxweight + sumcoef > capacity )
10448 assert(newweight > weights[pos]);
10450 SCIPdebugMsg(scip,
"in constraint <%s> changing weight %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10456 assert(pos < nvars);
10458 maxweight = weights[pos];
10460 if( backpos <= pos )
10463 (*nchgcoefs) += (pos - startpos);
10466 while( pos < nvars && weights[pos] + sumcoef == capacity )
10477 if( pos + 1 == backpos && weights[pos] > sumcoef &&
10478 ((k == 0) || (k == 1 && weights[nvars - 1] + sumcoef + weights[pos] > capacity)) )
10480 newweight = capacity - sumcoef;
10481 assert(newweight > weights[pos]);
10483 SCIPdebugMsg(scip,
"in constraint <%s> changing weight %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10491 if( backpos <= pos )
10499 if( conshdlrdata->disaggregation && consdata->nvars - pos <= MAX_USECLIQUES_SIZE && consdata->nvars >= 2 &&
10500 pos > 0 && (
SCIP_Longint)consdata->nvars - pos <= consdata->capacity &&
10501 consdata->weights[pos - 1] == consdata->capacity && (pos == consdata->nvars || consdata->weights[pos] == 1) )
10515 if( pos == consdata->nvars )
10536 len = consdata->nvars - pos;
10543 assert(nclq <= len);
10547 for( w = 0; w < nclq; ++w )
10548 assert(clqpart[w] <= w);
10557 for( w = pos - 1; w >= 0; --w )
10558 clqvars[w] = consdata->vars[w];
10561 for( c = 0; c < nclq; ++c )
10565 for( w = c; w < len; ++w )
10567 if( clqpart[w] == c )
10569 assert(nclqvars < pos + len - nclq + 1);
10570 clqvars[nclqvars] = consdata->vars[w + pos];
10575 assert(nclqvars > 1);
10603 int* newweightidxs;
10617 assert(consdata->merged);
10626 if( consdata->cliquepartition[consdata->nvars - 1] == consdata->nvars - 1 )
10630 cliqueweightsum = 0;
10633 for( i = 0; i < consdata->nvars; ++i )
10637 cliquenum = consdata->cliquepartition[i];
10638 assert(0 <= cliquenum && cliquenum <= ncliques);
10640 weight = consdata->weights[i];
10641 assert(weight > 0);
10643 if( cliquenum == ncliques )
10645 maxcliqueweights[ncliques] = weight;
10646 cliqueweightsum += weight;
10650 assert(maxcliqueweights[cliquenum] >= weight);
10654 zeroweights =
FALSE;
10655 for( i = 0; i < ncliques; ++i )
10659 delta = consdata->capacity - (cliqueweightsum - maxcliqueweights[i]);
10671 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",
10672 SCIPconsGetName(cons), i, maxcliqueweights[i], cliqueweightsum, consdata->capacity, delta);
10673 newcapacity = consdata->capacity - delta;
10674 forceclique =
FALSE;
10677 newmincliqueweight = newcapacity + 1;
10678 for( j = 0; j < i; ++j )
10679 assert(consdata->cliquepartition[j] < i);
10681 for( j = i; j < consdata->nvars; ++j )
10683 if( consdata->cliquepartition[j] == i )
10685 newweight = consdata->weights[j] - delta;
10686 newweight =
MAX(newweight, 0);
10689 assert(nnewweights < consdata->nvars);
10690 newweightvals[nnewweights] = newweight;
10691 newweightidxs[nnewweights] = j;
10695 assert(newweight <= newmincliqueweight);
10696 newmincliqueweight = newweight;
10702 if( nnewweights > 1 )
10705 j = newweightidxs[nnewweights - 2];
10706 assert(0 <= j && j < consdata->nvars);
10707 assert(consdata->cliquepartition[j] == i);
10708 j = newweightidxs[nnewweights - 1];
10709 assert(0 <= j && j < consdata->nvars);
10710 assert(consdata->cliquepartition[j] == i);
10713 newminweightsuminclique = newweightvals[nnewweights - 2];
10714 newminweightsuminclique += newweightvals[nnewweights - 1];
10721 if( newminweightsuminclique <= newcapacity )
10722 forceclique =
TRUE;
10726 if( conshdlrdata->disaggregation || !forceclique )
10728 SCIPdebugMsg(scip,
" -> change capacity from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
" (forceclique:%u)\n",
10729 consdata->capacity, newcapacity, forceclique);
10730 consdata->capacity = newcapacity;
10733 for( k = 0; k < nnewweights; ++k )
10735 j = newweightidxs[k];
10736 assert(0 <= j && j < consdata->nvars);
10737 assert(consdata->cliquepartition[j] == i);
10740 SCIPdebugMsg(scip,
" -> change weight of <%s> from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10741 SCIPvarGetName(consdata->vars[j]), consdata->weights[j], newweightvals[k]);
10744 assert(!consdata->sorted);
10745 zeroweights = zeroweights || (newweightvals[k] == 0);
10759 for( k = 0; k < nnewweights; ++k )
10760 cliquevars[k] = consdata->vars[newweightidxs[k]];
10783 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10791 if( consdata->weightsum <= consdata->capacity )
10803 if( consdata->weightsum <= consdata->capacity )
10806 if( (presoltiming & SCIP_PRESOLTIMING_FAST) != 0 )
10809 assert(consdata->merged);
10811 minweight = consdata->weights[consdata->nvars-1];
10812 for( i = 0; i < consdata->nvars-1; ++i )
10816 weight = consdata->weights[i];
10817 assert(weight >= minweight);
10818 if( minweight + weight > consdata->capacity )
10820 if( weight < consdata->capacity )
10822 SCIPdebugMsg(scip,
"knapsack constraint <%s>: changed weight of <%s> from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10824 assert(consdata->sorted);
10826 assert(i == 0 || consdata->weights[i-1] >= consdata->weights[i]);
10827 consdata->sorted =
TRUE;
10836 if( consdata->nvars >= 2 )
10840 minweight = consdata->weights[consdata->nvars-2];
10841 weight = consdata->weights[consdata->nvars-1];
10842 assert(minweight >= weight);
10843 if( minweight + weight > consdata->capacity && weight < consdata->capacity )
10845 SCIPdebugMsg(scip,
"knapsack constraint <%s>: changed weight of <%s> from %" SCIP_LONGINT_FORMAT
" to %" SCIP_LONGINT_FORMAT
"\n",
10847 assert(consdata->sorted);
10849 assert(minweight >= consdata->weights[consdata->nvars-1]);
10850 consdata->sorted =
TRUE;
10869 for( b = 0; b < ncliquevars; ++b )
10890 int* gaincliquepartition;
10896 int nposcliquevars;
10900 int lastcliqueused;
10905 assert(scip !=
NULL);
10906 assert(cons !=
NULL);
10907 assert(cutoff !=
NULL);
10908 assert(nbdchgs !=
NULL);
10913 assert(consdata !=
NULL);
10915 nvars = consdata->nvars;
10918 if( consdata->cliquesadded || nvars == 0 )
10929 assert(consdata->merged);
10932 assert(conshdlrdata !=
NULL);
10936 nnegcliques = consdata->nnegcliques;
10939 if( nnegcliques == nvars )
10953 minactduetonegcliques = 0;
10956 for( v = 0; v <
nvars; ++v )
10958 assert(0 <= consdata->negcliquepartition[v] && consdata->negcliquepartition[v] <= nnegcliques);
10959 assert(consdata->weights[v] > 0);
10961 if( consdata->negcliquepartition[v] == nnegcliques )
10964 maxweights[consdata->negcliquepartition[v]] = consdata->weights[v];
10967 minactduetonegcliques += consdata->weights[v];
10970 nposcliquevars = 0;
10973 if( minactduetonegcliques > 0 )
10976 freecapacity = consdata->capacity - minactduetonegcliques;
10979 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",
10980 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
10983 for( v = 0; v <
nvars; ++v )
10985 if( !cliqueused[consdata->negcliquepartition[v]] )
10987 cliqueused[consdata->negcliquepartition[v]] =
TRUE;
10988 for( w = v + 1; w <
nvars; ++w )
10992 if( consdata->negcliquepartition[v] == consdata->negcliquepartition[w]
10993 && consdata->weights[v] > consdata->weights[w] )
10995 poscliquevars[nposcliquevars] = consdata->vars[w];
10996 gainweights[nposcliquevars] = maxweights[consdata->negcliquepartition[v]] - consdata->weights[w];
10997 gaincliquepartition[nposcliquevars] = consdata->negcliquepartition[v];
11005 if( nposcliquevars > 0 )
11010 for( v = 0; v < nposcliquevars; ++v )
11014 lastweight = gainweights[v];
11015 beforelastweight = -1;
11016 lastcliqueused = gaincliquepartition[v];
11019 cliqueused[gaincliquepartition[v]] =
TRUE;
11023 for( w = v + 1; w < nposcliquevars && !cliqueused[gaincliquepartition[w]] && gainweights[w] + lastweight > freecapacity; ++w )
11025 beforelastweight = lastweight;
11026 lastweight = gainweights[w];
11027 lastcliqueused = gaincliquepartition[w];
11028 cliqueused[gaincliquepartition[w]] =
TRUE;
11033 if( ncliquevars > 1 )
11035 SCIPdebug( printClique(cliquevars, ncliquevars) );
11036 assert(beforelastweight > 0);
11042 *nbdchgs += thisnbdchgs;
11045 cliqueused[lastcliqueused] =
FALSE;
11048 for( ++w; w < nposcliquevars && !cliqueused[gaincliquepartition[w]] && beforelastweight + gainweights[w] > freecapacity; ++w )
11051 SCIPdebug( printClique(cliquevars, ncliquevars) );
11055 *nbdchgs += thisnbdchgs;
11102 if( ! sorteditems )
11106 lastweight = weights[0];
11109 for( i = 1; i < nitems && weights[i] + lastweight > capacity; ++i )
11111 lastweight = weights[i];
11115 if( ncliquevars > 1 )
11119 int compareweightidx;
11123 SCIPdebug( printClique(items, ncliquevars) );
11129 *nbdchgs += thisnbdchgs;
11132 if( ncliquevars == nitems )
11140 compareweightidx = ncliquevars - 2;
11141 assert(i == nitems || weights[i] + weights[ncliquevars - 1] <= capacity);
11144 minclqsize = (int)(cliqueextractfactor * ncliquevars);
11145 minclqsize =
MAX(minclqsize, 2);
11148 while( compareweightidx >= 0 && i < nitems && ncliquevars >= minclqsize && ! (*cutoff) )
11150 compareweight = weights[compareweightidx];
11151 assert(compareweight > 0);
11154 if( compareweight + weights[i] > capacity )
11156 assert(compareweightidx == ncliquevars -2);
11157 cliquevars[ncliquevars - 1] = items[i];
11158 SCIPdebug( printClique(cliquevars, ncliquevars) );
11163 *nbdchgs += thisnbdchgs;
11171 compareweightidx--;
11202 int nposcliquevars;
11206 assert(scip !=
NULL);
11207 assert(cons !=
NULL);
11208 assert(cutoff !=
NULL);
11209 assert(nbdchgs !=
NULL);
11214 assert(consdata !=
NULL);
11216 nvars = consdata->nvars;
11219 if( consdata->cliquesadded || nvars == 0 )
11230 assert(consdata->merged);
11233 assert(conshdlrdata !=
NULL);
11237 nnegcliques = consdata->nnegcliques;
11238 assert(nnegcliques <= nvars);
11247 minactduetonegcliques = 0;
11250 if( nnegcliques < nvars )
11254 for( i = 0; i <
nvars; ++i )
11258 cliquenum = consdata->negcliquepartition[i];
11259 assert(0 <= cliquenum && cliquenum <= nnegcliques);
11261 weight = consdata->weights[i];
11262 assert(weight > 0);
11264 if( cliquenum == nnegcliques )
11268 minactduetonegcliques += weight;
11269 if( secondmaxweights[cliquenum] == 0 )
11270 secondmaxweights[cliquenum] = weight;
11276 if( minactduetonegcliques > 0 )
11279 freecapacity = consdata->capacity - minactduetonegcliques;
11282 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",
11283 SCIPconsGetName(cons), consdata->capacity, minactduetonegcliques, freecapacity);
11291 nposcliquevars = 0;
11293 for( i = nvars - 1; i >= 0; --i )
11296 cliquenum = consdata->negcliquepartition[i];
11297 if( consdata->weights[i] > secondmaxweights[cliquenum] )
11299 poscliquevars[nposcliquevars] = consdata->vars[i];
11300 gainweights[nposcliquevars] = consdata->weights[i] - secondmaxweights[cliquenum];
11306 if( nposcliquevars > 1 )
11323 consdata->cliquesadded =
TRUE;
11352 assert(consdata1->sorted);
11353 assert(consdata2->sorted);
11355 scip = (
SCIP*)userptr;
11356 assert(scip !=
NULL);
11360 if( consdata1->nvars != consdata2->nvars )
11363 for( i = consdata1->nvars - 1; i >= 0; --i )
11366 if( consdata1->vars[i] != consdata2->vars[i] )
11368 assert(
SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
11372 assert(
SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 0);
11375 if( consdata1->weights[i] != consdata2->weights[i] )
11395 assert(consdata !=
NULL);
11396 assert(consdata->nvars > 0);
11399 scip = (
SCIP*)userptr;
11400 assert(scip !=
NULL);
11409 assert(minidx >= 0 && mididx >= 0 && maxidx >= 0);
11413 consdata->weights[0]);
11433 assert(scip !=
NULL);
11434 assert(blkmem !=
NULL);
11435 assert(conss !=
NULL);
11436 assert(ndelconss !=
NULL);
11439 hashtablesize = nconss;
11442 hashGetKeyKnapsackcons, hashKeyEqKnapsackcons, hashKeyValKnapsackcons, (
void*) scip) );
11445 for( c = nconss - 1; c >= 0; --c )
11457 assert(consdata0 !=
NULL);
11458 if( consdata0->nvars == 0 )
11460 if( consdata0->capacity < 0 )
11476 if( cons1 !=
NULL )
11490 assert(consdata1 !=
NULL);
11491 assert(consdata0->nvars > 0 && consdata0->nvars == consdata1->nvars);
11493 assert(consdata0->sorted && consdata1->sorted);
11494 assert(consdata0->vars[0] == consdata1->vars[0]);
11495 assert(consdata0->weights[0] == consdata1->weights[0]);
11497 SCIPdebugMsg(scip,
"knapsack constraints <%s> and <%s> with equal coefficients\n",
11501 if( consdata0->capacity < consdata1->capacity )
11556 assert(scip !=
NULL);
11557 assert(conss !=
NULL);
11558 assert(firstchange <= chkind);
11559 assert(ndelconss !=
NULL);
11562 cons0 = conss[chkind];
11563 assert(cons0 !=
NULL);
11568 assert(consdata0 !=
NULL);
11569 assert(consdata0->nvars >= 1);
11570 assert(consdata0->merged);
11588 assert(cons1 !=
NULL);
11593 assert(consdata1 !=
NULL);
11599 assert(consdata1->nvars >= 1);
11600 assert(consdata1->merged);
11607 if( consdata0->nvars > consdata1->nvars )
11609 iscons0incons1contained =
FALSE;
11610 iscons1incons0contained =
TRUE;
11611 v = consdata1->nvars - 1;
11613 else if( consdata0->nvars < consdata1->nvars )
11615 iscons0incons1contained =
TRUE;
11616 iscons1incons0contained =
FALSE;
11617 v = consdata0->nvars - 1;
11621 iscons0incons1contained =
TRUE;
11622 iscons1incons0contained =
TRUE;
11623 v = consdata0->nvars - 1;
11634 v0 = consdata0->nvars - 1;
11635 v1 = consdata1->nvars - 1;
11639 assert(iscons0incons1contained || iscons1incons0contained);
11644 iscons1incons0contained =
FALSE;
11645 if( !iscons0incons1contained )
11651 iscons0incons1contained =
FALSE;
11652 if( !iscons1incons0contained )
11656 assert(v == v0 || v == v1);
11661 if( consdata0->vars[v0] == consdata1->vars[v1] )
11664 if( iscons1incons0contained &&
SCIPisLT(scip, ((
SCIP_Real) consdata0->weights[v0]) / quotient, (
SCIP_Real) consdata1->weights[v1]) )
11666 iscons1incons0contained =
FALSE;
11667 if( !iscons0incons1contained )
11671 else if( iscons0incons1contained &&
SCIPisGT(scip, ((
SCIP_Real) consdata0->weights[v0]) / quotient, (
SCIP_Real) consdata1->weights[v1]) )
11673 iscons0incons1contained =
FALSE;
11674 if( !iscons1incons0contained )
11684 if( iscons0incons1contained && iscons1incons0contained )
11686 iscons0incons1contained =
FALSE;
11687 iscons1incons0contained =
FALSE;
11690 assert(iscons0incons1contained ? (v1 >= v0) : iscons1incons0contained);
11691 assert(iscons1incons0contained ? (v1 <= v0) : iscons0incons1contained);
11693 if( iscons0incons1contained )
11702 assert(!iscons1incons0contained || !iscons0incons1contained || v0 == -1 || v1 == -1);
11704 if( iscons1incons0contained )
11715 else if( iscons0incons1contained )
11753 SCIPdebugMsg(scip,
"knapsack enforcement of %d/%d constraints for %s solution\n", nusefulconss, nconss,
11754 sol ==
NULL ?
"LP" :
"relaxation");
11758 assert(conshdlrdata !=
NULL);
11759 maxncuts = (
SCIPgetDepth(scip) == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
11762 for( i = 0; i < nusefulconss && ncuts < maxncuts && ! cutoff; i++ )
11774 for( i = nusefulconss; i < nconss && ncuts == 0 && ! cutoff; i++ )
11788 else if ( ncuts > 0 )
11841 assert(nvars == 0 || vars !=
NULL);
11842 assert(nvars == 0 || vals !=
NULL);
11864 for( v = 0; v <
nvars; ++v )
11870 transvars[v] = vars[v];
11871 weights[v] = weight;
11876 weights[v] = -weight;
11877 capacity -= weight;
11879 assert(transvars[v] !=
NULL);
11884 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
11899 assert(upgdcons !=
NULL);
11906 upgrade = (nposbin + nnegbin + nposimplbin + nnegimplbin ==
nvars)
11907 && (ncoeffspone + ncoeffsnone + ncoeffspint + ncoeffsnint == nvars)
11936 assert(scip !=
NULL);
11937 assert(conshdlr !=
NULL);
11958 assert(conshdlrdata !=
NULL);
11976 assert( scip !=
NULL );
11977 assert( conshdlr !=
NULL );
11980 assert(conshdlrdata !=
NULL);
11986 conshdlrdata->reals1size =
nvars;
11997 assert( scip !=
NULL );
11998 assert( conshdlr !=
NULL );
12004 conshdlrdata->reals1size = 0;
12017 assert(scip !=
NULL);
12018 assert(conshdlr !=
NULL);
12019 assert(nconss == 0 || conss !=
NULL);
12022 assert(conshdlrdata !=
NULL);
12036 conshdlrdata->ints1size =
nvars;
12037 conshdlrdata->ints2size =
nvars;
12038 conshdlrdata->longints1size =
nvars;
12039 conshdlrdata->longints2size =
nvars;
12040 conshdlrdata->bools1size =
nvars;
12041 conshdlrdata->bools2size =
nvars;
12042 conshdlrdata->bools3size =
nvars;
12043 conshdlrdata->bools4size =
nvars;
12056 assert(scip !=
NULL);
12057 assert(conshdlr !=
NULL);
12059 for( c = 0; c < nconss; ++c )
12069 assert(conshdlrdata !=
NULL);
12080 conshdlrdata->ints1size = 0;
12081 conshdlrdata->ints2size = 0;
12082 conshdlrdata->longints1size = 0;
12083 conshdlrdata->longints2size = 0;
12084 conshdlrdata->bools1size = 0;
12085 conshdlrdata->bools2size = 0;
12086 conshdlrdata->bools3size = 0;
12087 conshdlrdata->bools4size = 0;
12100 assert( scip !=
NULL );
12103 for( c = 0; c < nconss; ++c )
12106 assert(consdata !=
NULL);
12108 if( consdata->row !=
NULL )
12123 assert(conshdlr !=
NULL);
12128 assert(conshdlrdata !=
NULL);
12129 assert(conshdlrdata->eventhdlr !=
NULL);
12146 assert(conshdlr !=
NULL);
12149 assert(sourcecons !=
NULL);
12150 assert(targetcons !=
NULL);
12153 assert(sourcedata !=
NULL);
12154 assert(sourcedata->row ==
NULL);
12158 assert(conshdlrdata !=
NULL);
12159 assert(conshdlrdata->eventhdlr !=
NULL);
12163 sourcedata->nvars, sourcedata->vars, sourcedata->weights, sourcedata->capacity) );
12185 *infeasible =
FALSE;
12187 for( i = 0; i < nconss && !(*infeasible); i++ )
12220 assert(conshdlrdata !=
NULL);
12225 SCIPdebugMsg(scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12226 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12229 if( (depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12230 || (depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12235 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12236 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12237 && ((sepacardfreq == 0 && depth == 0) || (sepacardfreq >= 1 && (depth % sepacardfreq == 0)));
12243 maxbound = glblowerbound + conshdlrdata->maxcardbounddist * (cutoffbound - glblowerbound);
12244 sepacardinality = sepacardinality &&
SCIPisLE(scip, loclowerbound, maxbound);
12248 maxsepacuts = (depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12255 for( i = 0; i < nusefulconss && ncuts < maxsepacuts && !
SCIPisStopped(scip); i++ )
12263 else if ( ncuts > 0 )
12289 assert(conshdlrdata !=
NULL);
12294 SCIPdebugMsg(scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12295 nusefulconss, nconss, nrounds, conshdlrdata->maxroundsroot, conshdlrdata->maxrounds);
12298 if( (depth == 0 && conshdlrdata->maxroundsroot >= 0 && nrounds >= conshdlrdata->maxroundsroot)
12299 || (depth > 0 && conshdlrdata->maxrounds >= 0 && nrounds >= conshdlrdata->maxrounds) )
12304 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12305 sepacardinality = (conshdlrdata->sepacardfreq >= 0)
12306 && ((sepacardfreq == 0 && depth == 0) || (sepacardfreq >= 1 && (depth % sepacardfreq == 0)));
12309 maxsepacuts = (depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12316 for( i = 0; i < nusefulconss && ncuts < maxsepacuts && !
SCIPisStopped(scip); i++ )
12318 SCIP_CALL(
separateCons(scip, conss[i], sol, sepacardinality, conshdlrdata->usegubs, &cutoff, &ncuts) );
12324 else if( ncuts > 0 )
12355 for( i = 0; i < nconss; i++ )
12378 for( i = 0; i < nconss && (*result ==
SCIP_FEASIBLE || completely); i++ )
12403 assert(conshdlrdata !=
NULL);
12409 for( i = 0; i < nmarkedconss && !cutoff; i++ )
12421 SCIP_CALL(
propagateCons(scip, conss[i], &cutoff, &redundant, &nfixedvars, conshdlrdata->negatedclique) );
12431 else if( nfixedvars > 0 )
12461 oldnfixedvars = *nfixedvars;
12462 oldnchgbds = *nchgbds;
12463 oldndelconss = *ndelconss;
12464 oldnaddconss = *naddconss;
12465 oldnchgcoefs = *nchgcoefs;
12466 oldnchgsides = *nchgsides;
12467 firstchange = INT_MAX;
12469 newchanges = (nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgbds > 0 || nnewupgdconss > 0);
12472 assert(conshdlrdata !=
NULL);
12476 int thisnfixedvars;
12481 assert(consdata !=
NULL);
12485 if( newchanges || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
12494 consdata->presolvedtiming = 0;
12495 else if( consdata->presolvedtiming >= presoltiming )
12500 consdata->presolvedtiming = presoltiming;
12502 thisnfixedvars = *nfixedvars;
12503 thisnchgbds = *nchgbds;
12513 SCIP_CALL(
addCliques(scip, cons, conshdlrdata->cliqueextractfactor, &cutoff, nchgbds) );
12521 SCIP_CALL(
propagateCons(scip, cons, &cutoff, &redundant, nfixedvars, (presoltiming & SCIP_PRESOLTIMING_MEDIUM)) );
12533 if( *nfixedvars > thisnfixedvars || *nchgbds > thisnchgbds )
12539 thisnfixedvars = *nfixedvars;
12545 if( consdata->weightsum <= consdata->capacity )
12547 SCIPdebugMsg(scip,
" -> knapsack constraint <%s> is redundant: weightsum=%" SCIP_LONGINT_FORMAT
", capacity=%" SCIP_LONGINT_FORMAT
"\n",
12567 if( *nfixedvars > thisnfixedvars )
12582 if( conshdlrdata->dualpresolving &&
SCIPallowDualReds(scip) && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
12602 if( !cutoff && conshdlrdata->presolusehashing && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
12608 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) || (*naddconss != oldnaddconss) )
12617 npaircomparisons = 0;
12618 oldndelconss = *ndelconss;
12619 oldnchgsides = *nchgsides;
12620 oldnchgcoefs = *nchgcoefs;
12622 for( c = firstchange; c < nconss && !cutoff && !
SCIPisStopped(scip); ++c )
12634 if( (*ndelconss != oldndelconss) || (*nchgsides != oldnchgsides) || (*nchgcoefs != oldnchgcoefs) )
12636 if( ((
SCIP_Real) (*ndelconss - oldndelconss) + ((
SCIP_Real) (*nchgsides - oldnchgsides))/2.0 +
12639 oldndelconss = *ndelconss;
12640 oldnchgsides = *nchgsides;
12641 oldnchgcoefs = *nchgcoefs;
12642 npaircomparisons = 0;
12649 else if( success || *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds )
12665 assert(result !=
NULL);
12668 assert(consdata !=
NULL);
12673 for( i = 0; i < consdata->nvars; ++i )
12682 assert(i < consdata->nvars);
12690 if( inferinfo < 0 )
12697 if( inferinfo < consdata->nvars && consdata->vars[inferinfo] == infervar )
12698 capsum = consdata->weights[inferinfo];
12701 for( i = 0; i < consdata->nvars && consdata->vars[i] != infervar; ++i )
12703 assert(i < consdata->nvars);
12704 capsum = consdata->weights[i];
12711 if( capsum <= consdata->capacity )
12713 for( i = 0; i < consdata->nvars; i++ )
12718 capsum += consdata->weights[i];
12719 if( capsum > consdata->capacity )
12749 assert(consdata !=
NULL);
12751 for( i = 0; i < consdata->nvars; i++)
12765 assert(scip !=
NULL);
12766 assert(conshdlr !=
NULL);
12767 assert(conss !=
NULL || nconss == 0);
12784 assert( scip !=
NULL );
12785 assert( conshdlr !=
NULL );
12786 assert( cons !=
NULL );
12789 assert(consdata !=
NULL);
12791 for( i = 0; i < consdata->nvars; ++i )
12795 SCIPinfoMessage(scip, file,
"%+" SCIP_LONGINT_FORMAT, consdata->weights[i]);
12798 SCIPinfoMessage(scip, file,
" <= %" SCIP_LONGINT_FORMAT
"", consdata->capacity);
12810 const char* consname;
12820 for( v = 0; v <
nvars; ++v )
12831 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, global, valid) );
12832 assert(cons !=
NULL);
12853 assert(scip !=
NULL);
12854 assert(success !=
NULL);
12855 assert(str !=
NULL);
12856 assert(name !=
NULL);
12857 assert(cons !=
NULL);
12866 while( *str !=
'\0' )
12869 if( sscanf(str,
"%" SCIP_LONGINT_FORMAT
"%n", &weight, &nread) < 1 )
12875 while( isspace((
int)*str) )
12890 if( varssize <= nvars )
12898 weights[
nvars] = weight;
12902 while( isspace((
int)*str) )
12908 if( strncmp(str,
"<= ", 3) != 0 )
12921 if( sscanf(str,
"%" SCIP_LONGINT_FORMAT, &capacity) != 1 )
12929 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
12946 assert(consdata !=
NULL);
12948 if( varssize < consdata->nvars )
12952 assert(vars !=
NULL);
12968 assert(consdata !=
NULL);
12970 (*nvars) = consdata->nvars;
12986 assert(eventdata !=
NULL);
12987 assert(eventdata->cons !=
NULL);
12995 consdata->onesweightsum += eventdata->weight;
12996 consdata->presolvedtiming = 0;
13000 consdata->onesweightsum -= eventdata->weight;
13003 consdata->presolvedtiming = 0;
13007 if( !consdata->existmultaggr )
13011 assert(var !=
NULL);
13016 consdata->existmultaggr =
TRUE;
13017 consdata->merged =
FALSE;
13020 consdata->merged =
FALSE;
13025 consdata->presolvedtiming = 0;
13028 consdata->varsdeleted =
TRUE;
13056 eventhdlrdata =
NULL;
13057 conshdlrdata->eventhdlr =
NULL;
13059 eventExecKnapsack, eventhdlrdata) );
13062 if( conshdlrdata->eventhdlr ==
NULL )
13071 consEnfolpKnapsack, consEnfopsKnapsack, consCheckKnapsack, consLockKnapsack,
13074 assert(conshdlr !=
NULL);
13109 "multiplier on separation frequency, how often knapsack cuts are separated (-1: never, 0: only at root)",
13113 "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for separating knapsack cuts",
13117 "lower clique size limit for greedy clique extraction algorithm (relative to largest clique)",
13121 "maximal number of separation rounds per node (-1: unlimited)",
13125 "maximal number of separation rounds per node in the root node (-1: unlimited)",
13129 "maximal number of cuts separated per separation round",
13133 "maximal number of cuts separated per separation round in the root node",
13137 "should disaggregation of knapsack constraints be allowed in preprocessing?",
13141 "should presolving try to simplify knapsacks",
13145 "should negated clique information be used in solving process",
13149 "should pairwise constraint comparison be performed in presolving?",
13153 "should hash table be used for detecting redundant constraints in advance",
13157 "should dual presolving steps be performed?",
13161 "should GUB information be used for separation?",
13165 "should presolving try to detect constraints parallel to the objective function defining an upper bound and prevent these constraints from entering the LP?",
13169 "should presolving try to detect constraints parallel to the objective function defining a lower bound and prevent these constraints from entering the LP?",
13173 "should clique partition information be updated when old partition seems outdated?",
13177 "factor on the growth of global cliques to decide when to update a previous " 13178 "(negated) clique partition (used only if updatecliquepartitions is set to TRUE)",
13228 if( conshdlr ==
NULL )
13236 assert(conshdlrdata !=
NULL);
13237 assert(conshdlrdata->eventhdlr !=
NULL);
13243 SCIP_CALL(
SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
13244 local, modifiable, dynamic, removable, stickingatnode) );
13274 assert(scip !=
NULL);
13290 assert(var !=
NULL);
13319 assert(consdata !=
NULL);
13321 return consdata->capacity;
13344 SCIPerrorMessage(
"method can only be called during problem creation stage\n");
13349 assert(consdata !=
NULL);
13351 consdata->capacity = capacity;
13372 assert(consdata !=
NULL);
13374 return consdata->nvars;
13393 assert(consdata !=
NULL);
13395 return consdata->vars;
13414 assert(consdata !=
NULL);
13416 return consdata->weights;
13435 assert(consdata !=
NULL);
13437 if( consdata->row !=
NULL )
13459 assert(consdata !=
NULL);
13461 if( consdata->row !=
NULL )
13485 assert(consdata !=
NULL);
13487 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)
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)
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 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)
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
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
#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 .
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_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)
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)))
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
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)
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *cutoff)
#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 SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
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
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)
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)
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_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)
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)
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_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)
#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)