76#ifdef WITH_CARDINALITY_UPGRADE
81#define CONSHDLR_NAME "knapsack"
82#define CONSHDLR_DESC "knapsack constraint of the form a^T x <= b, x binary and a >= 0"
83#define CONSHDLR_SEPAPRIORITY +600000
84#define CONSHDLR_ENFOPRIORITY -600000
85#define CONSHDLR_CHECKPRIORITY -600000
86#define CONSHDLR_SEPAFREQ 0
87#define CONSHDLR_PROPFREQ 1
88#define CONSHDLR_EAGERFREQ 100
90#define CONSHDLR_MAXPREROUNDS -1
91#define CONSHDLR_DELAYSEPA FALSE
92#define CONSHDLR_DELAYPROP FALSE
93#define CONSHDLR_NEEDSCONS TRUE
95#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
96#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
98#define EVENTHDLR_NAME "knapsack"
99#define EVENTHDLR_DESC "bound change event handler for knapsack constraints"
100#define EVENTTYPE_KNAPSACK SCIP_EVENTTYPE_LBCHANGED \
101 | SCIP_EVENTTYPE_UBTIGHTENED \
102 | SCIP_EVENTTYPE_VARFIXED \
103 | SCIP_EVENTTYPE_VARDELETED \
104 | SCIP_EVENTTYPE_IMPLADDED
106#define LINCONSUPGD_PRIORITY +100000
108#define MAX_USECLIQUES_SIZE 1000
109#define MAX_ZEROITEMS_SIZE 10000
111#define KNAPSACKRELAX_MAXDELTA 0.1
112#define KNAPSACKRELAX_MAXDNOM 1000LL
113#define KNAPSACKRELAX_MAXSCALE 1000.0
115#define DEFAULT_SEPACARDFREQ 1
116#define DEFAULT_MAXROUNDS 5
117#define DEFAULT_MAXROUNDSROOT -1
118#define DEFAULT_MAXSEPACUTS 50
119#define DEFAULT_MAXSEPACUTSROOT 200
120#define DEFAULT_MAXCARDBOUNDDIST 0.0
122#define DEFAULT_DISAGGREGATION TRUE
123#define DEFAULT_SIMPLIFYINEQUALITIES TRUE
124#define DEFAULT_NEGATEDCLIQUE TRUE
126#define MAXABSVBCOEF 1e+5
127#define USESUPADDLIFT FALSE
129#define DEFAULT_PRESOLUSEHASHING TRUE
130#define HASHSIZE_KNAPSACKCONS 500
132#define DEFAULT_PRESOLPAIRWISE TRUE
133#define NMINCOMPARISONS 200000
134#define MINGAINPERNMINCOMPARISONS 1e-06
136#define DEFAULT_DUALPRESOLVING TRUE
137#define DEFAULT_DETECTCUTOFFBOUND TRUE
140#define DEFAULT_DETECTLOWERBOUND TRUE
143#define DEFAULT_CLIQUEEXTRACTFACTOR 0.5
144#define MAXCOVERSIZEITERLEWI 1000
146#define DEFAULT_USEGUBS FALSE
147#define GUBCONSGROWVALUE 6
148#define GUBSPLITGNC1GUBS FALSE
149#define DEFAULT_CLQPARTUPDATEFAC 1.5
151#define DEFAULT_UPDATECLIQUEPARTITIONS FALSE
152#define MAXNCLIQUEVARSCOMP 1000000
153#ifdef WITH_CARDINALITY_UPGRADE
154#define DEFAULT_UPGDCARDINALITY FALSE
164struct SCIP_ConshdlrData
170 SCIP_Longint* longints1;
172 SCIP_Longint* longints2;
194 SCIP_Real maxcardbounddist;
201 SCIP_Bool disaggregation;
202 SCIP_Bool simplifyinequalities;
203 SCIP_Bool negatedclique;
204 SCIP_Bool presolpairwise;
205 SCIP_Bool presolusehashing;
206 SCIP_Bool dualpresolving;
208 SCIP_Bool detectcutoffbound;
211 SCIP_Bool detectlowerbound;
214 SCIP_Bool updatecliquepartitions;
215 SCIP_Real cliqueextractfactor;
216 SCIP_Real clqpartupdatefac;
218#ifdef WITH_CARDINALITY_UPGRADE
229 SCIP_Longint* weights;
231 int* cliquepartition;
232 int* negcliquepartition;
239 int ncliqueslastnegpart;
240 int ncliqueslastpart;
241 SCIP_Longint capacity;
242 SCIP_Longint weightsum;
243 SCIP_Longint onesweightsum;
244 unsigned int presolvedtiming:5;
245 unsigned int sorted:1;
246 unsigned int cliquepartitioned:1;
247 unsigned int negcliquepartitioned:1;
248 unsigned int merged:1;
249 unsigned int cliquesadded:1;
250 unsigned int varsdeleted:1;
251 unsigned int existmultaggr:1;
352 (*eventdata)->cons = cons;
353 (*eventdata)->weight = weight;
379 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
380 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
381 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
382 assert(consdata->nvars == 0 || (consdata->cliquepartition !=
NULL && consdata->negcliquepartition !=
NULL));
384 if( !consdata->sorted )
394 (
void**)consdata->vars,
395 (
void**)consdata->eventdata,
396 consdata->cliquepartition,
397 consdata->negcliquepartition,
400 v = consdata->nvars - 1;
406 while(
w >= 0 && consdata->weights[v] == consdata->weights[
w] )
413 (
void**)(&(consdata->vars[
w+1])),
414 (
void**)(&(consdata->eventdata[
w+1])),
415 &(consdata->cliquepartition[
w+1]),
416 &(consdata->negcliquepartition[
w+1]),
424 if( consdata->cliquepartitioned )
428 for( pos = 0; pos < consdata->nvars; ++pos )
434 consdata->cliquepartitioned =
FALSE;
442 if( consdata->negcliquepartitioned )
446 for( pos = 0; pos < consdata->nvars; ++pos )
452 consdata->negcliquepartitioned =
FALSE;
455 else if( consdata->negcliquepartition[pos] ==
lastcliquenum )
460 consdata->sorted =
TRUE;
466 for(
i = 0;
i < consdata->nvars-1; ++
i )
467 assert(consdata->weights[
i] >= consdata->weights[
i+1]);
479 SCIP_Bool negatedclique
485 assert(consdata->nvars == 0 || (consdata->cliquepartition !=
NULL && consdata->negcliquepartition !=
NULL));
489 &&
SCIPgetNCliques(
scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastpart));
494 consdata->cliquepartitioned =
TRUE;
500 &&
SCIPgetNCliques(
scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastnegpart));
505 consdata->negcliquepartitioned =
TRUE;
508 assert(!consdata->cliquepartitioned || consdata->ncliques <= consdata->nvars);
509 assert(!consdata->negcliquepartitioned || consdata->nnegcliques <= consdata->nvars);
553 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
554 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
555 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
557 for(
i = 0;
i < consdata->nvars;
i++)
561 eventhdlr, consdata->eventdata[
i], &consdata->eventdata[
i]->filterpos) );
578 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
579 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
580 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
582 for(
i = 0;
i < consdata->nvars;
i++)
585 eventhdlr, consdata->eventdata[
i], consdata->eventdata[
i]->filterpos) );
598 SCIP_Bool transformed
602 assert(consdata->nvars <= consdata->varssize);
604 if( num > consdata->varssize )
646 assert(consdata->weightsum >= 0);
647 assert(consdata->onesweightsum >= 0);
657 SCIP_Longint* weights,
658 SCIP_Longint capacity
662 SCIP_Longint constant;
669 (*consdata)->vars =
NULL;
670 (*consdata)->weights =
NULL;
671 (*consdata)->nvars = 0;
682 for( v = 0; v <
nvars; ++v )
688 assert( weights[v] >= 0 );
697 constant += weights[v];
710 (*consdata)->nvars =
k;
724 (*consdata)->varssize = (*consdata)->nvars;
725 (*consdata)->capacity = capacity - constant;
726 (*consdata)->eventdata =
NULL;
727 (*consdata)->cliquepartition =
NULL;
728 (*consdata)->negcliquepartition =
NULL;
729 (*consdata)->row =
NULL;
730 (*consdata)->nlrow =
NULL;
731 (*consdata)->weightsum = 0;
732 (*consdata)->onesweightsum = 0;
733 (*consdata)->ncliques = 0;
734 (*consdata)->nnegcliques = 0;
735 (*consdata)->presolvedtiming = 0;
736 (*consdata)->sorted =
FALSE;
737 (*consdata)->cliquepartitioned =
FALSE;
738 (*consdata)->negcliquepartitioned =
FALSE;
739 (*consdata)->ncliqueslastpart = -1;
740 (*consdata)->ncliqueslastnegpart = -1;
741 (*consdata)->merged =
FALSE;
742 (*consdata)->cliquesadded =
FALSE;
743 (*consdata)->varsdeleted =
FALSE;
744 (*consdata)->existmultaggr =
FALSE;
751 for( v = 0; v < (*consdata)->nvars; v++ )
765 for( v = 0; v < (*consdata)->nvars; ++v )
787 if( (*consdata)->row !=
NULL )
791 if( (*consdata)->nlrow !=
NULL )
795 if( (*consdata)->eventdata !=
NULL )
800 if( (*consdata)->negcliquepartition !=
NULL )
804 if( (*consdata)->cliquepartition !=
NULL )
808 if( (*consdata)->vars !=
NULL )
813 for( v = 0; v < (*consdata)->nvars; v++ )
820 assert( (*consdata)->varssize > 0 );
851 if( consdata->eventdata !=
NULL )
858 consdata->presolvedtiming = 0;
859 consdata->sorted =
FALSE;
864 consdata->cliquesadded =
FALSE;
887 for(
i = 0;
i < consdata->nvars; ++
i )
912 if( consdata->row ==
NULL )
948 if( consdata->nlrow ==
NULL )
954 for(
i = 0;
i < consdata->nvars; ++
i )
955 coefs[
i] = (SCIP_Real)consdata->weights[
i];
958 consdata->nvars, consdata->vars, coefs,
NULL,
992 SCIPdebugMsg(
scip,
"checking knapsack constraint <%s> for feasibility of solution %p (lprows=%u)\n",
1022 for( v = consdata->nvars - 1; v >= 0; --v )
1033 for( v = consdata->nvars - 1; v >= 0; --v )
1044 absviol -= consdata->capacity;
1073#define IDX(j,d) ((j)*(intcap)+(d))
1097 SCIP_Longint* weights,
1099 SCIP_Longint capacity,
1117 SCIP_Longint weightsum;
1125 SCIP_Longint minweight;
1126 SCIP_Longint maxweight;
1144 for(
j = nitems - 1;
j >= 0; --
j )
1151 if( solval !=
NULL )
1176 for(
j = 0;
j < nitems; ++
j )
1181 if( weights[
j] > capacity )
1193 else if( weights[
j] == 0 )
1198 if( solval !=
NULL )
1235 if( weightsum > 0 && weightsum <= capacity )
1244 if( solval !=
NULL )
1251 assert(0 < minweight && minweight <= capacity );
1252 assert(0 < maxweight && maxweight <= capacity);
1279 assert(minweight <= capacity);
1282 if( minweight > capacity / 2 )
1286 SCIPdebugMsg(
scip,
"Only one item fits into knapsack, so take the best.\n");
1310 if( solval !=
NULL )
1335 for(
i = capacity - 1;
i >= 0; --
i )
1350 if( solval !=
NULL )
1414 for(
l = 0;
l <
j; ++
l )
1420 if( solval !=
NULL )
1430 capacity -= (minweight - 1);
1445 assert(
sizeof(
size_t) >=
sizeof(
int));
1542 assert((SCIP_Longint)
d >= -minweight);
1571 for( ;
j >= 0; --
j )
1579 if( solval !=
NULL )
1601 SCIP_Longint* weights,
1603 SCIP_Longint capacity,
1629 if( solval !=
NULL )
1635 for(
j = nitems - 1;
j >= 0; --
j )
1651 if( solval !=
NULL )
1657 for( ;
j < nitems;
j++ )
1685 for(
c = 0;
c <
gubset->ngubconss;
c++ )
1692 if(
gubset->gubconss[
c]->ngubvars > 1 )
1700 for( v = 0; v <
gubset->gubconss[
c]->ngubvars; v++ )
1705 if( solvals !=
NULL )
1717 if( solvals !=
NULL )
1750 (*gubcons)->ngubvars = 0;
1982 SCIP_Longint* weights,
1983 SCIP_Longint capacity
2000 (*gubset)->ngubconss =
nvars;
2001 (*gubset)->nvars =
nvars;
2013 (*gubset)->gubconssidx[
i] =
i;
2014 (*gubset)->gubvarsidx[
i] = 0;
2015 assert((*gubset)->gubconss[
i]->ngubvars == 1);
2018 if( weights[
i] > capacity )
2042 for(
i = (*gubset)->ngubconss-1;
i >= 0; --
i )
2086 SCIPdebugMsg(
scip,
" var<%d> should be in GUB<%d> at position<%d>, but stored is var<%d> instead\n",
i,
2093 for(
i = 0;
i <
gubset->ngubconss;
i++ )
2097 for(
j = 0;
j <
gubset->gubconss[
i]->ngubvars;
j++ )
2106 for(
k =
j+1;
k <
gubset->gubconss[
i]->ngubvars;
k++ )
2115 SCIPdebugMsg(
scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n",
i,
j,
2118 SCIPdebugMsg(
scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n",
i,
j,
2148 int*
const cliquepartition,
2189 cliquepartition[
i] = -1;
2227 if( cliquepartition[
varseq[
i]] == -1 )
2232 cliquepartition[
varseq[
i]] = *ncliques;
2282 if( cliquepartition[
varseq[
i]] == -1 )
2284 cliquepartition[
varseq[
i]] = *ncliques;
2309 int* cliquepartition;
2335 for(
i = 0;
i < ncliques;
i++ )
2343 assert(cliquepartition[
i] >= 0);
2403 SCIP_Longint* weights,
2404 SCIP_Longint capacity,
2422 SCIP_Bool infeasible;
2478 if( weights[
j] > capacity )
2508 assert(nfixedones + nfixedzeros + nitems ==
nvars - (*ntightened));
2537 for(
j = 0;
j < nitems;
j++ )
2572 for(
j = 0;
j < nitems;
j++ )
2596 for(
j = 0;
j < nfixedones;
j++ )
2604 for(
j = 0;
j < nfixedzeros;
j++ )
2631 SCIP_Longint* weights,
2632 SCIP_Longint capacity,
2640 SCIP_Longint minweight;
2650 for(
i = 0;
i <
j;
i++ )
2658 for(
i = 0;
i <
j;
i++ )
2724 SCIP_Longint* weights,
2764 SCIP_Longint* weights,
2854 SCIP_Longint* weights,
2941 SCIP_Longint* weights,
3138 for(
i = 0;
i <
gubset->ngubconss;
i++ )
3403 (*ngubconscapexceed) =
ngubconss - (
ngubconsGOC1 + (*ngubconsGC2) + (*ngubconsGFC1) + (*ngubconsGR));
3495 SCIP_Longint* weights,
3496 SCIP_Longint capacity,
3557 (*cutact) += solvals[
varsM1[
j]];
3585 SCIP_Longint weight;
3622 right = (*liftrhs) + 1;
3623 while( left < right - 1 )
3625 middle = (left + right) / 2;
3632 assert(left == right - 1);
3687 SCIP_Longint weight;
3706 while( left < right - 1 )
3708 middle = (left + right) / 2;
3715 assert(left == right - 1);
3777 SCIP_Longint weight;
3787 assert(capacity - weight >= 0);
3806 right = (*liftrhs) + 1;
3807 while( left < right - 1)
3809 middle = (left + right) / 2;
3816 assert(left == right - 1);
3944 SCIP_Longint* weights,
3945 SCIP_Longint capacity,
3969 SCIP_Longint weight;
4064 (*cutact) += solvals[
varidx];
4279 assert(capacity - weight >= 0);
4309 right = (*liftrhs) + 1;
4310 while( left < right - 1 )
4312 middle = (left + right) / 2;
4319 assert(left == right - 1);
4465 while( left < right - 1 )
4467 middle = (left + right) / 2;
4474 assert(left == right - 1);
4554 assert(capacity - weight >= 0);
4575 right = (*liftrhs) + 1;
4576 while( left < right - 1 )
4578 middle = (left + right) / 2;
4585 assert(left == right - 1);
4679 SCIP_Longint* weights,
4680 SCIP_Longint capacity,
4695 SCIP_Longint lambda;
4758 SCIP_Longint weight;
4812 SCIP_Longint* weights,
4813 SCIP_Longint capacity,
4973 else if ( sepa !=
NULL )
5046 SCIP_Longint* weights,
5047 SCIP_Longint capacity,
5122 SCIP_CALL(
sequentialUpAndDownLifting(
scip,
vars,
nvars, ntightened, weights, capacity, solvals,
varsT1,
varsT2,
varsF,
varsR,
5140 else if ( sepa !=
NULL )
5213 SCIP_Longint* weights,
5214 SCIP_Longint capacity,
5267 else if ( sepa !=
NULL )
5322 SCIP_Longint* weights,
5323 SCIP_Longint capacity,
5335 SCIP_Longint minweight;
5422 for(
k =
j;
k < (*ncovervars) - 1;
k++ )
5476 SCIP_Longint* weights,
5477 SCIP_Longint capacity,
5544 (*coverweight) -= weights[
covervars[0]];
5545 for(
k = 0;
k < (*ncovervars) - 1;
k++ )
5574 SCIP_Longint* weights,
5575 SCIP_Longint capacity,
5625 SCIPdebugMsg(
scip,
"separate cuts for knapsack constraint originated by cons <%s>:\n",
5665 SCIPdebugMsg(
scip,
" LMCI1-GUB terminated by no variable with fractional LP value.\n");
5770 SCIP_CALL(
getFeasibleSet(
scip, cons, sepa,
vars,
nvars, ntightened, weights, capacity, solvals,
covervars,
noncovervars,
5843 if( conshdlr ==
NULL )
5856 usegubs = conshdlrdata->usegubs;
5863 if( conshdlrdata->reals1size == 0 )
5866 conshdlrdata->reals1size = 1;
5867 conshdlrdata->reals1[0] = 0.0;
5870 assert(conshdlrdata->reals1size > 0);
5876 if( conshdlrdata->reals1size <
nbinvars )
5878 int oldsize = conshdlrdata->reals1size;
5880 conshdlrdata->reals1size =
nbinvars;
5884 binvals = conshdlrdata->reals1;
5925 SCIPdebugMsg(
scip,
"Solution value %.15g <%s> outside domain [0.0, 1.0]\n",
5970 SCIPdebugMsg(
scip,
"variable bound <%s>[%g,%g] >= %g<%s>[%g,%g] + %g implies local cutoff\n",
5993 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with lower bound %.15g (rhs=%.15g)\n",
6012 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable lower bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6050 SCIPdebugMsg(
scip,
"variable bound <%s>[%g,%g] <= %g<%s>[%g,%g] + %g implies local cutoff\n",
6073 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with upper bound %.15g (rhs=%.15g)\n",
6092 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable upper bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6157 consvars[nconsvars] =
var;
6163 SCIP_Longint capacity;
6175 for(
i = 0;
i < nconsvars; ++
i )
6188 SCIPdebugMsg(
scip,
"minactivity of knapsack relaxation implies local cutoff\n");
6196 SCIP_CALL(
SCIPseparateKnapsackCuts(
scip, cons, sepa, consvars, nconsvars,
consvals, capacity,
sol, usegubs,
cutoff, ncuts) );
6258 consdata->capacity,
sol, usegubs,
cutoff, ncuts) );
6281 if( consdata->row !=
NULL )
6290 consdata->capacity -= weight;
6301 consdata->vars[consdata->nvars] =
var;
6302 consdata->weights[consdata->nvars] = weight;
6320 conshdlrdata->eventhdlr, consdata->eventdata[consdata->nvars-1],
6321 &consdata->eventdata[consdata->nvars-1]->filterpos) );
6324 consdata->existmultaggr =
TRUE;
6328 consdata->presolvedtiming = 0;
6329 consdata->cliquesadded =
FALSE;
6335 consdata->sorted =
FALSE;
6336 consdata->cliquepartitioned =
FALSE;
6337 consdata->negcliquepartitioned =
FALSE;
6338 consdata->merged =
FALSE;
6359 var = consdata->vars[pos];
6364 if( consdata->row !=
NULL )
6380 conshdlrdata->eventhdlr, consdata->eventdata[pos], consdata->eventdata[pos]->filterpos) );
6384 consdata->presolvedtiming = 0;
6385 consdata->sorted = (consdata->sorted && pos == consdata->nvars - 1);
6392 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
6393 consdata->weights[pos] = consdata->weights[consdata->nvars-1];
6394 if( consdata->eventdata !=
NULL )
6395 consdata->eventdata[pos] = consdata->eventdata[consdata->nvars-1];
6401 if( consdata->cliquepartitioned )
6406 if( consdata->cliquepartition[consdata->nvars - 1] != consdata->nvars - 1 )
6411 consdata->cliquepartition[pos] = consdata->cliquepartition[consdata->nvars-1];
6414 if( consdata->cliquepartition[pos] > pos )
6415 consdata->cliquepartitioned =
FALSE;
6423 if(
oldcliqenum > consdata->cliquepartition[pos] )
6425 for(
i = 0;
i < consdata->nvars; ++
i )
6430 consdata->cliquepartitioned =
FALSE;
6436 if(
i == consdata->nvars )
6437 --(consdata->ncliques);
6447 consdata->cliquepartitioned =
FALSE;
6450 else if( pos == consdata->nvars - 1)
6456 --(consdata->ncliques);
6462 --(consdata->ncliques);
6465 if( consdata->negcliquepartitioned )
6467 assert(consdata->negcliquepartition !=
NULL);
6470 if( consdata->negcliquepartition[consdata->nvars-1] != consdata->nvars - 1 )
6475 consdata->negcliquepartition[pos] = consdata->negcliquepartition[consdata->nvars-1];
6478 if( consdata->negcliquepartition[pos] > pos )
6479 consdata->negcliquepartitioned =
FALSE;
6487 if(
oldcliqenum > consdata->negcliquepartition[pos] )
6489 for(
i = 0;
i < consdata->nvars; ++
i )
6494 consdata->negcliquepartitioned =
FALSE;
6500 if(
i == consdata->nvars )
6501 --(consdata->nnegcliques);
6511 consdata->negcliquepartitioned =
FALSE;
6514 else if( pos == consdata->nvars - 1)
6520 --(consdata->nnegcliques);
6526 --(consdata->nnegcliques);
6529 --(consdata->nvars);
6547 for( v = consdata->nvars-1; v >= 0; --v )
6549 if( consdata->weights[v] == 0 )
6578 for(
i = 0;
i < nconss;
i++ )
6583 if( consdata->varsdeleted )
6586 for( v = consdata->nvars - 1; v >= 0; --v )
6593 consdata->varsdeleted =
FALSE;
6621 if( consdata->merged )
6624 if( consdata->nvars <= 1 )
6626 consdata->merged =
TRUE;
6630 assert(consdata->vars !=
NULL || consdata->nvars == 0);
6637 consdata->sorted =
FALSE;
6639 v = consdata->nvars - 1;
6652 var1 = consdata->vars[v];
6662 var2 = consdata->vars[prev];
6678 consdataChgWeight(consdata, prev, consdata->weights[v] + consdata->weights[prev]);
6684 else if( consdata->weights[v] == consdata->weights[prev] )
6687 consdata->capacity -= consdata->weights[v];
6693 else if( consdata->weights[v] < consdata->weights[prev] )
6695 consdata->capacity -= consdata->weights[v];
6696 consdataChgWeight(consdata, prev, consdata->weights[prev] - consdata->weights[v]);
6697 assert(consdata->weights[prev] > 0);
6702 consdata->capacity -= consdata->weights[prev];
6704 assert(consdata->weights[v] > 0);
6707 if( consdata->nvars != v )
6715 consdata->cliquesadded =
FALSE;
6722 consdata->cliquesadded =
FALSE;
6728 consdata->merged =
TRUE;
6731 if( consdata->onesweightsum > consdata->capacity )
6760 SCIP_Bool infeasible;
6761 SCIP_Bool tightened;
6762 SCIP_Bool applicable;
6780 nvars = consdata->nvars;
6781 vars = consdata->vars;
6793 for( v = 0; v <
nvars; ++v )
6848 SCIPdebugMsg(
scip,
"variable <%s> only locked up in knapsack constraints: dual presolve <%s>[%.15g,%.15g] >= 1.0\n",
6861 SCIPdebugMsg(
scip,
"variable <%s> has no down locks: dual presolve <%s>[%.15g,%.15g] <= 0.0\n",
6899 SCIP_Bool applicable;
6912 nvars = consdata->nvars;
6927 vars = consdata->vars;
6934 for( v = 0; v <
nvars && applicable; ++v )
6956 weight = (
SCIP_Real)consdata->weights[v];
6963 scale = weight / -
objval;
6986 SCIP_Real cutoffbound;
6992 cutoffbound = (consdata->capacity -
offset) / scale;
6994 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
7002 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
7022 SCIP_Real lowerbound;
7028 lowerbound = (consdata->capacity -
offset) / scale;
7030 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a lower bound <%g>\n",
7047 SCIP_Longint* weights,
7049 SCIP_Bool usenegatedclique
7055 int* cliquepartition;
7073 origvars = consdata->vars;
7082 if( usenegatedclique )
7084 assert(consdata->negcliquepartitioned);
7086 cliquepartition = consdata->negcliquepartition;
7087 ncliques = consdata->nnegcliques;
7091 assert(consdata->cliquepartitioned);
7093 cliquepartition = consdata->cliquepartition;
7094 ncliques = consdata->ncliques;
7107 assert(0 <= cliquepartition[v] && cliquepartition[v] < ncliques);
7122 for(
c = 0;
c < ncliques; ++
c )
7183 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
7192 if ( consdata->onesweightsum > consdata->capacity )
7203 consdata->existmultaggr =
FALSE;
7210 var = consdata->vars[v];
7216 consdata->capacity -= consdata->weights[v];
7218 consdata->cliquesadded =
FALSE;
7230 SCIP_Longint weight;
7233 weight = consdata->weights[v];
7290 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-integral value for weight*aggrconst = %g\n", weight*
aggrconst);
7298 for(
i = naggrvars - 1;
i >= 0; --
i )
7305 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-binary %svariable <%s> with bounds [%g,%g]\n",
7336 if( consdata->capacity < 0 )
7358 assert(consdata->onesweightsum == 0);
7383 SCIP_Bool* redundant,
7385 SCIP_Bool usenegatedclique
7389 SCIP_Bool infeasible;
7390 SCIP_Bool tightened;
7429 for(
i = 0;
i < consdata->nvars && consdata->merged; ++
i )
7435 usenegatedclique = usenegatedclique && consdata->merged;
7443 nvars = consdata->nvars;
7458 if( usenegatedclique &&
nvars > 0 )
7466 nnegcliques = consdata->nnegcliques;
7469 if( nnegcliques ==
nvars )
7472 usenegatedclique =
FALSE;
7488 for(
c = 0;
c < nnegcliques; ++
c )
7505 if( nnegcliques -
c ==
nvars -
i )
7622 for(
c = 0;
c < nnegcliques; ++
c )
7630 assert(nnegcliques == consdata->nnegcliques);
7751 if( consdata->capacity <
minweightsum + consdata->onesweightsum )
7754 consdata->onesweightsum, consdata->capacity);
7763 SCIP_Longint weight;
7769 for(
i = 0;
i <
nvars && weight <= consdata->capacity;
i++ )
7774 weight += consdata->weights[
i];
7785 if( !usenegatedclique )
7787 assert(consdata->sorted);
7800 assert(consdata->onesweightsum + consdata->weights[
i] > consdata->capacity);
7860 assert(consdata->nvars > 1);
7863 if( consdata->nvars == 2 )
7929 SCIP_Longint* weights;
7930 SCIP_Longint capacity;
7949 vars = consdata->vars;
7950 weights = consdata->weights;
7951 nvars = consdata->nvars;
7952 capacity = consdata->capacity;
7959 assert(weights[
w] <= weights[
w-1]);
7963 if( consdata->nvars - 1 ==
splitpos )
7969 if( consdata->weightsum - weights[
splitpos] <= capacity )
7979 consdata->capacity -= weights[
w];
7989 for( ;
w >= 0 &&
gcd > 1; --
w )
8001 (*nchgcoefs) +=
nvars;
8003 consdata->capacity /=
gcd;
8011 for(
w = consdata->nvars - 1;
w > 0; --
w )
8012 assert(weights[
w] <= weights[
w - 1]);
8019 else if( conshdlrdata->disaggregation &&
frontsum + weights[
splitpos + 1] <= capacity )
8042 for(
w = 0;
w < len; ++
w )
8071 for(
w = 0;
w < len; ++
w )
8113 weights = consdata->weights;
8117 for( ;
w >= 0 &&
gcd > 1; --
w )
8129 (*nchgcoefs) +=
nvars;
8131 consdata->capacity /=
gcd;
8142 for(
w = consdata->nvars - 1;
w > 0; --
w )
8143 assert(weights[
w] <= weights[
w - 1]);
8178 SCIP_Longint* weights;
8179 SCIP_Longint capacity;
8195 assert(consdata->nvars >= 2);
8196 assert(consdata->weightsum > consdata->capacity);
8199 vars = consdata->vars;
8200 weights = consdata->weights;
8201 nvars = consdata->nvars;
8202 capacity = consdata->capacity;
8206 for( v = 0; v <
nvars && sum + weights[v] <= capacity; ++v )
8212 if( v ==
nvars - 1 )
8224 assert(consdata->nvars > 1);
8227 if( v == consdata->nvars - 1 )
8241 assert(weights == consdata->weights);
8243 assert(capacity == consdata->capacity);
8251 if( consdata->cliquepartition[v] < v )
8261 clqpart = consdata->cliquepartition;
8285 if( conshdlrdata->disaggregation &&
w ==
nvars )
8296 ncliques = consdata->ncliques;
8301 for(
c = 0;
c < ncliques; ++
c )
8371 assert(consdata->onesweightsum == 0);
8372 assert(consdata->weightsum > consdata->capacity);
8373 assert(consdata->nvars >= 1);
8378 gcd = consdata->weights[consdata->nvars-1];
8379 for(
i = consdata->nvars-2;
i >= 0 &&
gcd >= 2; --
i )
8391 for(
i = 0;
i < consdata->nvars; ++
i )
8395 consdata->capacity /=
gcd;
8396 (*nchgcoefs) += consdata->nvars;
8401 for(
i = consdata->nvars - 1;
i > 0; --
i )
8402 assert(consdata->weights[
i] <= consdata->weights[
i - 1]);
8404 consdata->sorted =
TRUE;
8438 SCIP_Longint* weights;
8441 SCIP_Longint capacity;
8465 assert(consdata->weightsum > consdata->capacity);
8466 assert(consdata->nvars >= 2);
8467 assert(consdata->sorted);
8470 assert(consdata->merged);
8472 nvars = consdata->nvars;
8473 weights = consdata->weights;
8474 capacity = consdata->capacity;
8479 if( weights[
nvars - 1] + weights[
nvars - 2] > capacity )
8506 if( consdata->weightsum - weights[
nvars - 1] <= consdata->capacity )
8516 if( consdata->weightsum - capacity > weights[0] + weights[1] )
8537 while( v <
nvars && weights[v] + weights[
nvars - 1] > capacity )
8563 for( v = 0; v <
vbig; ++v )
8573 for( ; v <
nvars; ++v )
8575 if( weights[v] > 1 )
8588 for( v =
nvars - 1; v > 0; --v )
8589 assert(weights[v] <= weights[v-1]);
8621 for( v = 0; v <
vbig; ++v )
8631 for( ; v <
nvars; ++v )
8633 if( weights[v] > 1 )
8646 for( v =
nvars - 1; v > 0; --v )
8647 assert(weights[v] <= weights[v-1]);
8676 for( v = 0; v <
vbig; ++v )
8684 for( v = 0; v <
vbig; ++v )
8694 for( ; v <
nvars; ++v )
8696 if( weights[v] > 1 )
8709 for( v =
nvars - 1; v > 0; --v )
8710 assert(weights[v] <= weights[v-1]);
8746 if( v >=
nvars - 1 )
8749 if( v ==
nvars - 1 )
8776 if( v > 0 && weights[
nvars - 2] > 1 )
8781 for(
w = 0;
w < v; ++
w )
8783 if( weights[
w] > 2 )
8791 assert(weights[v - 1] == 2);
8799 if( weights[
w] > 1 )
8810 consdata->capacity = (-2 + v * 2 +
nvars - v);
8811 assert(consdata->capacity > 0);
8812 assert(weights[0] <= consdata->capacity);
8813 assert(consdata->weightsum > consdata->capacity);
8824 SCIP_Longint minweight = weights[
nvars - 1];
8848 (*nchgcoefs) += (v -
startv);
8880 for( ;
w >= 0; --
w )
8899 if( weights[v] > 1 || (weights[
startv] > (SCIP_Longint)
nvars - v) || (
startv > 0 && weights[0] == (SCIP_Longint)
nvars - v + 1) )
8906 if( weights[
w] > 1 )
8932 for( ;
w >= 0; --
w )
8945 if( consdata->capacity >
newcap )
8947 consdata->capacity =
newcap;
8956 assert(consdata->weightsum - consdata->capacity == (SCIP_Longint)
nvars - v + 1);
8963 assert(weights[
w] <= weights[
w - 1]);
8970 while(
end >= 0 && weights[
end] == weights[
end + 1] )
9005 for( ; v <=
end; ++v )
9024 for(
w = 0;
w < v; ++
w )
9031 for( ; v <=
end; ++v )
9042 (*nchgcoefs) +=
nvars;
9045 consdata->capacity *= 2;
9060 for(
k = 0;
k < 4; ++
k )
9101 minweight = weights[
end];
9117 (*nchgcoefs) += (v -
startv);
9128 while(
end >= 0 && weights[
end] == weights[
end + 1] )
9134 minweight = weights[
end];
9156 (*nchgcoefs) += (v -
startv);
9193 for( ; v <=
end; ++v )
9212 for(
w = 0;
w < v; ++
w )
9219 for( ; v <=
end; ++v )
9230 (*nchgcoefs) +=
nvars;
9233 consdata->capacity *= 2;
9259 assert(weights[0] <= consdata->capacity);
9266 assert(weights[
w] <= weights[
w - 1]);
9298 SCIP_Longint* weights;
9299 SCIP_Longint capacity;
9300 SCIP_Bool infeasible;
9314 nvars = consdata->nvars;
9319 assert(consdata->capacity >= 0);
9330 vars = consdata->vars;
9331 weights = consdata->weights;
9332 capacity = consdata->capacity;
9336 while( v <
nvars && weights[v] > capacity )
9359 for( --v; v >= 0; --v )
9368 assert(weights == consdata->weights);
9370 assert(consdata->sorted);
9371 assert(weights[0] <= capacity);
9418 SCIP_Longint* weights;
9421 SCIP_Longint weight;
9450 assert(consdata->merged);
9454 assert(consdata->capacity >= 0);
9476 weights = consdata->weights;
9477 nvars = consdata->nvars;
9481 for( v =
nvars - 1; v > 0; --v )
9482 assert(weights[v] <= weights[v-1]);
9487 for( v =
nvars - 2; v >= 0 &&
gcd > 1; --v )
9495 for( v =
nvars - 1; v >= 0; --v )
9499 (*nchgcoefs) +=
nvars;
9501 consdata->capacity /=
gcd;
9510 for( v =
nvars - 1; v > 0; --v )
9511 assert(weights[v] <= weights[v-1]);
9520 vars = consdata->vars;
9521 weights = consdata->weights;
9522 nvars = consdata->nvars;
9525 if( weights[
nvars - 1] == 1 && weights[
nvars - 2] == 1 )
9532 while( weights[v] == consdata->capacity )
9539 if( v ==
nvars - 1 )
9553 weight = weights[v];
9581 if( v ==
nvars - 2 )
9617 rest = consdata->capacity %
gcd;
9627 consdata->capacity -=
rest;
9631 for( v = 0; v <
offsetv; ++v )
9653 SCIPdebugMsg(
scip,
"gcd = %" SCIP_LONGINT_FORMAT ", rest = %" SCIP_LONGINT_FORMAT ", restweight = %" SCIP_LONGINT_FORMAT "; possible new weight of variable <%s> %" SCIP_LONGINT_FORMAT ", possible new capacity %" SCIP_LONGINT_FORMAT ", offset of coefficients as big as capacity %d\n",
gcd,
rest,
restweight,
SCIPvarGetName(
vars[
candpos]),
newweight, consdata->capacity -
rest,
offsetv);
9664 consdata->capacity -=
rest;
9668 for( v = 0; v <
offsetv; ++v )
9692 assert(consdata->weights == weights);
9696 for( v =
nvars - 1; v >= 0; --v )
9700 (*nchgcoefs) +=
nvars;
9702 consdata->capacity /=
gcd;
9709 while(
nvars >= 2 );
9761 SCIPdebugMsg(
scip,
"memory limit of %d bytes reached in knapsack preprocessing - abort collecting zero items\n",
9791#define MAX_CLIQUELENGTH 50
9853 assert(consdata->weightsum > consdata->capacity);
9854 assert(consdata->nvars > 0);
9855 assert(consdata->merged);
9857 nvars = consdata->nvars;
9885 assert(conshdlrdata->ints1size > 0);
9886 assert(conshdlrdata->ints2size > 0);
9887 assert(conshdlrdata->longints1size > 0);
9888 assert(conshdlrdata->longints2size > 0);
9894 if( conshdlrdata->ints1size <
nbinvars )
9896 int oldsize = conshdlrdata->ints1size;
9898 conshdlrdata->ints1size =
nbinvars;
9902 if( conshdlrdata->ints2size <
nbinvars )
9904 int oldsize = conshdlrdata->ints2size;
9906 conshdlrdata->ints2size =
nbinvars;
9910 if( conshdlrdata->longints1size <
nbinvars )
9912 int oldsize = conshdlrdata->longints1size;
9914 conshdlrdata->longints1size =
nbinvars;
9918 if( conshdlrdata->longints2size <
nbinvars )
9920 int oldsize = conshdlrdata->longints2size;
9922 conshdlrdata->longints2size =
nbinvars;
9952 assert(conshdlrdata->bools1size > 0);
9953 assert(conshdlrdata->bools2size > 0);
9959 if( conshdlrdata->bools1size <
nbinvars )
9961 int oldsize = conshdlrdata->bools1size;
9963 conshdlrdata->bools1size =
nbinvars;
9967 if( conshdlrdata->bools2size <
nbinvars )
9969 int oldsize = conshdlrdata->bools2size;
9971 conshdlrdata->bools2size =
nbinvars;
10003 SCIP_Longint weight;
10012 var = consdata->vars[
i];
10013 weight = consdata->weights[
i];
10082 if( probindex == -1 )
10118 assert(consdata->sorted);
10121 assert(conshdlrdata->bools3size > 0);
10127 if( conshdlrdata->bools3size < consdata->nvars )
10129 int oldsize = conshdlrdata->bools3size;
10131 conshdlrdata->bools3size = consdata->nvars;;
10140 for(
tmp = consdata->nvars - 1;
tmp >= 0; --
tmp )
10148 for(
i = 0;
i < consdata->nvars; ++
i )
10165 assert(conshdlrdata->bools4size > 0);
10171 if( conshdlrdata->bools4size < consdata->nvars )
10173 int oldsize = conshdlrdata->bools4size;
10175 conshdlrdata->bools4size = consdata->nvars;
10184 for(
tmp = consdata->nvars - 1;
tmp >= 0; --
tmp )
10196 for( val = 0; val < 2 &&
addweightsum < consdata->capacity; ++val )
10225 for(
j = 0;
j < consdata->nvars; ++
j )
10248 SCIP_Longint weight;
10252 var = binvars[probindex];
10380 SCIP_Longint* weights;
10382 SCIP_Longint capacity;
10384 SCIP_Longint maxweight;
10385 SCIP_Longint minweight;
10404 assert(consdata->onesweightsum == 0);
10405 assert(consdata->weightsum > consdata->capacity);
10406 assert(consdata->nvars > 0);
10417 assert(consdata->merged);
10422 for(
i = 0;
i < consdata->nvars; ++
i )
10424 SCIP_Longint weight;
10426 weight = consdata->weights[
i];
10429 newweight = consdata->weightsum - consdata->capacity;
10431 consdata->capacity -= (weight -
newweight);
10434 assert(!consdata->sorted);
10437 consdata->capacity + (weight-
newweight), consdata->capacity);
10443 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10447 if( consdata->weightsum <= consdata->capacity )
10455 weights = consdata->weights;
10456 nvars = consdata->nvars;
10457 capacity = consdata->capacity;
10460 pos <
nvars && weights[pos] + weights[pos + 1] > capacity )
10467 for(
k = 0;
k < 4; ++
k )
10523 maxweight = weights[pos];
10525 while( 2 * maxweight > capacity && maxweight +
sumcoef > capacity )
10537 maxweight = weights[pos];
10545 while( pos <
nvars && weights[pos] +
sumcoef == capacity )
10557 ((
k == 0) || (
k == 1 && weights[
nvars - 1] +
sumcoef + weights[pos] > capacity)) )
10580 consdata->weights[pos - 1] == consdata->capacity && (pos == consdata->nvars || consdata->weights[pos] == 1) )
10594 if( pos == consdata->nvars )
10615 len = consdata->nvars - pos;
10636 for(
w = pos - 1;
w >= 0; --
w )
10644 for(
w =
c;
w < len; ++
w )
10696 assert(consdata->merged);
10705 if( consdata->cliquepartition[consdata->nvars - 1] == consdata->nvars - 1 )
10712 for(
i = 0;
i < consdata->nvars; ++
i )
10714 SCIP_Longint weight;
10719 weight = consdata->weights[
i];
10734 for(
i = 0;
i < ncliques; ++
i )
10736 SCIP_Longint delta;
10757 for(
j = 0;
j <
i; ++
j )
10758 assert(consdata->cliquepartition[
j] <
i);
10760 for(
j =
i;
j < consdata->nvars; ++
j )
10762 if( consdata->cliquepartition[
j] ==
i )
10786 assert(consdata->cliquepartition[
j] ==
i);
10789 assert(consdata->cliquepartition[
j] ==
i);
10805 if( conshdlrdata->disaggregation || !
forceclique )
10816 assert(consdata->cliquepartition[
j] ==
i);
10823 assert(!consdata->sorted);
10862 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10870 if( consdata->weightsum <= consdata->capacity )
10882 if( consdata->weightsum <= consdata->capacity )
10888 assert(consdata->merged);
10890 minweight = consdata->weights[consdata->nvars-1];
10891 for(
i = 0;
i < consdata->nvars-1; ++
i )
10893 SCIP_Longint weight;
10895 weight = consdata->weights[
i];
10896 assert(weight >= minweight);
10897 if( minweight + weight > consdata->capacity )
10903 assert(consdata->sorted);
10905 assert(
i == 0 || consdata->weights[
i-1] >= consdata->weights[
i]);
10906 consdata->sorted =
TRUE;
10915 if( consdata->nvars >= 2 )
10917 SCIP_Longint weight;
10919 minweight = consdata->weights[consdata->nvars-2];
10920 weight = consdata->weights[consdata->nvars-1];
10921 assert(minweight >= weight);
10926 assert(consdata->sorted);
10928 assert(minweight >= consdata->weights[consdata->nvars-1]);
10929 consdata->sorted =
TRUE;
10994 nvars = consdata->nvars;
10997 if( consdata->cliquesadded ||
nvars == 0 )
11008 assert(consdata->merged);
11015 nnegcliques = consdata->nnegcliques;
11018 if( nnegcliques ==
nvars )
11033 for( v = 0; v <
nvars; ++v )
11035 assert(0 <= consdata->negcliquepartition[v] && consdata->negcliquepartition[v] <= nnegcliques);
11036 assert(consdata->weights[v] > 0);
11038 if( consdata->negcliquepartition[v] == nnegcliques )
11041 maxweights[consdata->negcliquepartition[v]] = consdata->weights[v];
11060 for( v = 0; v <
nvars; ++v )
11062 if( !
cliqueused[consdata->negcliquepartition[v]] )
11069 if( consdata->negcliquepartition[v] == consdata->negcliquepartition[
w]
11070 && consdata->weights[v] > consdata->weights[
w] )
11161 SCIP_Longint* weights,
11163 SCIP_Longint capacity,
11165 SCIP_Real cliqueextractfactor,
11272 SCIP_Real cliqueextractfactor,
11300 nvars = consdata->nvars;
11303 if( consdata->cliquesadded ||
nvars == 0 )
11314 assert(consdata->merged);
11321 nnegcliques = consdata->nnegcliques;
11334 if( nnegcliques <
nvars )
11340 SCIP_Longint weight;
11342 cliquenum = consdata->negcliquepartition[
i];
11345 weight = consdata->weights[
i];
11380 cliquenum = consdata->negcliquepartition[
i];
11407 consdata->cliquesadded =
TRUE;
11481 assert(consdata->nvars > 0);
11524 hashtablesize = nconss;
11530 for(
c = nconss - 1;
c >= 0; --
c )
11582 SCIPdebugMsg(
scip,
"knapsack constraints <%s> and <%s> with equal coefficients\n",
11838 SCIP_Bool violated;
11847 sol ==
NULL ?
"LP" :
"relaxation");
11852 maxncuts = (
SCIPgetDepth(
scip) == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
11881 else if ( ncuts > 0 )
11904 SCIP_Bool separate,
11914 SCIP_Bool modifiable,
11920 SCIP_Bool removable,
11922 SCIP_Bool stickingatnode
11928 SCIP_Longint* weights;
11929 SCIP_Longint capacity;
11930 SCIP_Longint weight;
11957 for( v = 0; v <
nvars; ++v )
11964 weights[v] = weight;
11969 weights[v] = -weight;
11970 capacity -= weight;
11977 initial, separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
12034 SCIP_Real constant = 0.0;
12056 for(
i = 0;
i < consdata->nvars; ++
i )
12058 vars[
i] = consdata->vars[
i];
12133 conshdlrdata->reals1size =
nvars;
12151 conshdlrdata->reals1size = 0;
12183 conshdlrdata->ints1size =
nvars;
12184 conshdlrdata->ints2size =
nvars;
12185 conshdlrdata->longints1size =
nvars;
12186 conshdlrdata->longints2size =
nvars;
12187 conshdlrdata->bools1size =
nvars;
12188 conshdlrdata->bools2size =
nvars;
12189 conshdlrdata->bools3size =
nvars;
12190 conshdlrdata->bools4size =
nvars;
12192#ifdef WITH_CARDINALITY_UPGRADE
12193 conshdlrdata->upgradedcard =
FALSE;
12210 for(
c = 0;
c < nconss; ++
c )
12231 conshdlrdata->ints1size = 0;
12232 conshdlrdata->ints2size = 0;
12233 conshdlrdata->longints1size = 0;
12234 conshdlrdata->longints2size = 0;
12235 conshdlrdata->bools1size = 0;
12236 conshdlrdata->bools2size = 0;
12237 conshdlrdata->bools3size = 0;
12238 conshdlrdata->bools4size = 0;
12251 for(
c = 0;
c < nconss; ++
c )
12270 for(
c = 0;
c < nconss; ++
c )
12275 if( consdata->row !=
NULL )
12280 if( consdata->nlrow !=
NULL )
12357 *infeasible =
FALSE;
12359 for(
i = 0;
i < nconss && !(*infeasible);
i++ )
12378 SCIP_Real cutoffbound;
12397 SCIPdebugMsg(
scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12401 if( (
depth == 0 && conshdlrdata->maxroundsroot >= 0 &&
nrounds >= conshdlrdata->maxroundsroot)
12402 || (
depth > 0 && conshdlrdata->maxrounds >= 0 &&
nrounds >= conshdlrdata->maxrounds) )
12407 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12409 && ((sepacardfreq == 0 &&
depth == 0) || (sepacardfreq >= 1 && (
depth % sepacardfreq == 0)));
12420 maxsepacuts = (
depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12435 else if ( ncuts > 0 )
12466 SCIPdebugMsg(
scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12470 if( (
depth == 0 && conshdlrdata->maxroundsroot >= 0 &&
nrounds >= conshdlrdata->maxroundsroot)
12471 || (
depth > 0 && conshdlrdata->maxrounds >= 0 &&
nrounds >= conshdlrdata->maxrounds) )
12476 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12478 && ((sepacardfreq == 0 &&
depth == 0) || (sepacardfreq >= 1 && (
depth % sepacardfreq == 0)));
12481 maxsepacuts = (
depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12496 else if( ncuts > 0 )
12524 SCIP_Bool violated;
12527 for(
i = 0;
i < nconss;
i++ )
12545 SCIP_Bool violated;
12566 SCIP_Bool redundant;
12602 else if( nfixedvars > 0 )
12618 SCIP_Bool redundant;
12665 consdata->presolvedtiming = 0;
12666 else if( consdata->presolvedtiming >= presoltiming )
12671 consdata->presolvedtiming = presoltiming;
12716 if( consdata->weightsum <= consdata->capacity )
12817#ifdef WITH_CARDINALITY_UPGRADE
12854 SCIP_Longint* weights;
12863 nvars = consdata->nvars;
12864 vars = consdata->vars;
12865 weights = consdata->weights;
12872 if ( consdata->capacity >=
nvars )
12876 assert( consdata->sorted );
12877 if ( weights[0] != 1 || weights[
nvars-1] != 1 )
12881 for (v = 0; v <
nvars; ++v)
12890 var = consdata->vars[v];
12907 for (
j = 0;
j < nimpls; ++
j)
12940 for (v = 0; v <
nvars; ++v)
12964 for (v = 0; v <
nvars; ++v)
12974 conshdlrdata->upgradedcard =
TRUE;
13006 for (v = 0; v <
nvars; ++v)
13053 for(
i = 0;
i < consdata->nvars; ++
i )
13070 if( inferinfo < 0 )
13078 capsum = consdata->weights[inferinfo];
13081 for(
i = 0;
i < consdata->nvars && consdata->vars[
i] !=
infervar; ++
i )
13084 capsum = consdata->weights[
i];
13093 for(
i = 0;
i < consdata->nvars;
i++ )
13098 capsum += consdata->weights[
i];
13099 if(
capsum > consdata->capacity )
13131 for(
i = 0;
i < consdata->nvars;
i++)
13204 for(
i = 0;
i < consdata->nvars; ++
i )
13221 SCIP_Longint* weights;
13223 const char* consname;
13233 for( v = 0; v <
nvars; ++v )
13234 coefs[v] = (SCIP_Real) weights[v];
13244 initial, separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode, global,
valid) );
13257 SCIP_Longint weight;
13259 SCIP_Longint* weights;
13260 SCIP_Longint capacity;
13279 while( *
str !=
'\0' )
13308 if( varssize <=
nvars )
13316 weights[
nvars] = weight;
13350 initial, separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
13370 (*success) =
FALSE;
13391 (*nvars) = consdata->nvars;
13434 consdata->onesweightsum += eventdata->weight;
13435 consdata->presolvedtiming = 0;
13439 consdata->onesweightsum -= eventdata->weight;
13442 consdata->presolvedtiming = 0;
13446 if( !consdata->existmultaggr )
13455 consdata->existmultaggr =
TRUE;
13456 consdata->merged =
FALSE;
13460 consdata->merged =
FALSE;
13464 consdata->presolvedtiming = 0;
13467 consdata->varsdeleted =
TRUE;
13495 eventhdlrdata =
NULL;
13496 conshdlrdata->eventhdlr =
NULL;
13501 if( conshdlrdata->eventhdlr ==
NULL )
13553 "multiplier on separation frequency, how often knapsack cuts are separated (-1: never, 0: only at root)",
13557 "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for separating knapsack cuts",
13561 "lower clique size limit for greedy clique extraction algorithm (relative to largest clique)",
13565 "maximal number of separation rounds per node (-1: unlimited)",
13569 "maximal number of separation rounds per node in the root node (-1: unlimited)",
13573 "maximal number of cuts separated per separation round",
13577 "maximal number of cuts separated per separation round in the root node",
13581 "should disaggregation of knapsack constraints be allowed in preprocessing?",
13585 "should presolving try to simplify knapsacks",
13589 "should negated clique information be used in solving process",
13593 "should pairwise constraint comparison be performed in presolving?",
13597 "should hash table be used for detecting redundant constraints in advance",
13601 "should dual presolving steps be performed?",
13605 "should GUB information be used for separation?",
13609 "should presolving try to detect constraints parallel to the objective function defining an upper bound and prevent these constraints from entering the LP?",
13613 "should presolving try to detect constraints parallel to the objective function defining a lower bound and prevent these constraints from entering the LP?",
13617 "should clique partition information be updated when old partition seems outdated?",
13621 "factor on the growth of global cliques to decide when to update a previous "
13622 "(negated) clique partition (used only if updatecliquepartitions is set to TRUE)",
13624#ifdef WITH_CARDINALITY_UPGRADE
13627 "if TRUE then try to update knapsack constraints to cardinality constraints",
13644 SCIP_Longint* weights,
13645 SCIP_Longint capacity,
13648 SCIP_Bool separate,
13658 SCIP_Bool modifiable,
13664 SCIP_Bool removable,
13666 SCIP_Bool stickingatnode
13677 if( conshdlr ==
NULL )
13692 SCIP_CALL(
SCIPcreateCons(
scip, cons, name, conshdlr, consdata, initial, separate, enforce, check,
propagate,
13693 local, modifiable, dynamic, removable, stickingatnode) );
13719 SCIP_Longint* weights,
13720 SCIP_Longint capacity
13736 SCIP_Longint weight
13773 return consdata->capacity;
13783 SCIP_Longint capacity
13798 SCIPerrorMessage(
"method can only be called during problem creation stage\n");
13805 consdata->capacity = capacity;
13830 return consdata->nvars;
13853 return consdata->vars;
13876 return consdata->weights;
13899 if( consdata->row !=
NULL )
13925 if( consdata->row !=
NULL )
13953 return consdata->row;
13960 SCIP_Bool* infeasible
13969 if( conshdlr ==
NULL )
13973 *infeasible =
FALSE;
13978 for(
i = 0;
i < nconss; ++
i )
constraint handler for cardinality constraints
static SCIP_Longint safeAddMinweightsGUB(SCIP_Longint val1, SCIP_Longint val2)
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool sepacuts, SCIP_Bool usegubs, SCIP_Bool *cutoff, int *ncuts)
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
static SCIP_RETCODE getLiftingSequenceGUB(SCIP *scip, SCIP_GUBSET *gubset, SCIP_Real *solvals, SCIP_Longint *weights, int *varsC1, int *varsC2, int *varsF, int *varsR, int nvarsC1, int nvarsC2, int nvarsF, int nvarsR, int *gubconsGC1, int *gubconsGC2, int *gubconsGFC1, int *gubconsGR, int *ngubconsGC1, int *ngubconsGC2, int *ngubconsGFC1, int *ngubconsGR, int *ngubconscapexceed, int *maxgubvarssize)
@ GUBCONSSTATUS_BELONGSTOSET_GF
@ GUBCONSSTATUS_UNINITIAL
@ GUBCONSSTATUS_BELONGSTOSET_GR
@ GUBCONSSTATUS_BELONGSTOSET_GOC1
@ GUBCONSSTATUS_BELONGSTOSET_GNC1
@ GUBCONSSTATUS_BELONGSTOSET_GC2
#define DEFAULT_DUALPRESOLVING
static SCIP_RETCODE deleteRedundantVars(SCIP *scip, SCIP_CONS *cons, SCIP_Longint frontsum, int splitpos, int *nchgcoefs, int *nchgsides, int *naddconss)
#define CONSHDLR_NEEDSCONS
#define DEFAULT_SEPACARDFREQ
#define CONSHDLR_SEPAFREQ
static SCIP_RETCODE insertZerolist(SCIP *scip, int **liftcands, int *nliftcands, int **firstidxs, SCIP_Longint **zeroweightsums, int **zeroitems, int **nextidxs, int *zeroitemssize, int *nzeroitems, int probindex, SCIP_Bool value, int knapsackidx, SCIP_Longint knapsackweight, SCIP_Bool *memlimitreached)
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
#define KNAPSACKRELAX_MAXDELTA
static SCIP_RETCODE eventdataCreate(SCIP *scip, SCIP_EVENTDATA **eventdata, SCIP_CONS *cons, SCIP_Longint weight)
static SCIP_RETCODE prepareCons(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, int *nchgcoefs)
#define CONSHDLR_CHECKPRIORITY
static SCIP_RETCODE enlargeMinweights(SCIP *scip, SCIP_Longint **minweightsptr, int *minweightslen, int *minweightssize, int newlen)
static SCIP_RETCODE separateSequLiftedExtendedWeightInequality(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *feassetvars, int *nonfeassetvars, int nfeassetvars, int nnonfeassetvars, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts)
static SCIP_RETCODE GUBconsCreate(SCIP *scip, SCIP_GUBCONS **gubcons)
#define KNAPSACKRELAX_MAXSCALE
static void normalizeWeights(SCIP_CONS *cons, int *nchgcoefs, int *nchgsides)
static SCIP_RETCODE separateSupLiftedMinimalCoverInequality(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *mincovervars, int *nonmincovervars, int nmincovervars, int nnonmincovervars, SCIP_Longint mincoverweight, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts)
#define DEFAULT_DETECTCUTOFFBOUND
static SCIP_RETCODE addCliques(SCIP *const scip, SCIP_CONS *const cons, SCIP_Real cliqueextractfactor, SCIP_Bool *const cutoff, int *const nbdchgs)
static SCIP_RETCODE upgradeCons(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss)
static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons)
static void updateWeightSums(SCIP_CONSDATA *consdata, SCIP_VAR *var, SCIP_Longint weightdelta)
static void GUBconsFree(SCIP *scip, SCIP_GUBCONS **gubcons)
#define CONSHDLR_PROP_TIMING
static void getPartitionCovervars(SCIP *scip, SCIP_Real *solvals, int *covervars, int ncovervars, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2)
static void GUBsetSwapVars(SCIP *scip, SCIP_GUBSET *gubset, int var1, int var2)
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
static SCIP_RETCODE getCover(SCIP *scip, SCIP_VAR **vars, int nvars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int *ncovervars, int *nnoncovervars, SCIP_Longint *coverweight, SCIP_Bool *found, SCIP_Bool modtransused, int *ntightened, SCIP_Bool *fractional)
static SCIP_RETCODE consdataEnsureVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool transformed)
static void GUBsetFree(SCIP *scip, SCIP_GUBSET **gubset)
static SCIP_RETCODE createNormalizedKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define CONSHDLR_MAXPREROUNDS
static SCIP_RETCODE calcCliquepartition(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSDATA *consdata, SCIP_Bool normalclique, SCIP_Bool negatedclique)
#define DEFAULT_PRESOLPAIRWISE
static SCIP_RETCODE performVarDeletions(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss)
#define CONSHDLR_SEPAPRIORITY
#define DEFAULT_MAXROUNDSROOT
struct sortkeypair SORTKEYPAIR
#define DEFAULT_NEGATEDCLIQUE
enum GUBVarstatus GUBVARSTATUS
static SCIP_RETCODE changePartitionCovervars(SCIP *scip, SCIP_Longint *weights, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2)
#define DEFAULT_MAXCARDBOUNDDIST
#define MAXCOVERSIZEITERLEWI
static SCIP_RETCODE mergeMultiples(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
static SCIP_RETCODE GUBsetCheck(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars)
static SCIP_RETCODE GUBsetMoveVar(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, int var, int oldgubcons, int newgubcons)
static void sortItems(SCIP_CONSDATA *consdata)
static SCIP_RETCODE addNegatedCliques(SCIP *const scip, SCIP_CONS *const cons, SCIP_Bool *const cutoff, int *const nbdchgs)
static SCIP_RETCODE detectRedundantVars(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss)
static SCIP_RETCODE GUBsetGetCliquePartition(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, SCIP_Real *solvals)
static SCIP_RETCODE addSymmetryInformation(SCIP *scip, SYM_SYMTYPE symtype, SCIP_CONS *cons, SYM_GRAPH *graph, SCIP_Bool *success)
static SCIP_RETCODE applyFixings(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
static void computeMinweightsGUB(SCIP_Longint *minweights, SCIP_Longint *finished, SCIP_Longint *unfinished, int minweightslen)
static SCIP_RETCODE sequentialUpAndDownLiftingGUB(SCIP *scip, SCIP_GUBSET *gubset, SCIP_VAR **vars, int ngubconscapexceed, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *gubconsGC1, int *gubconsGC2, int *gubconsGFC1, int *gubconsGR, int ngubconsGC1, int ngubconsGC2, int ngubconsGFC1, int ngubconsGR, int alpha0, int *liftcoefs, SCIP_Real *cutact, int *liftrhs, int maxgubvarssize)
#define HASHSIZE_KNAPSACKCONS
static SCIP_RETCODE GUBsetCalcCliquePartition(SCIP *const scip, SCIP_VAR **const vars, int const nvars, int *const cliquepartition, int *const ncliques, SCIP_Real *solvals)
#define DEFAULT_MAXSEPACUTSROOT
static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checklprows, SCIP_Bool printreason, SCIP_Bool *violated)
static SCIP_RETCODE dualWeightsTightening(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss)
#define DEFAULT_PRESOLUSEHASHING
#define DEFAULT_CLQPARTUPDATEFAC
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight)
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr)
static SCIP_Bool checkMinweightidx(SCIP_Longint *weights, SCIP_Longint capacity, int *covervars, int ncovervars, SCIP_Longint coverweight, int minweightidx, int j)
static SCIP_RETCODE sequentialUpAndDownLifting(SCIP *scip, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *varsM1, int *varsM2, int *varsF, int *varsR, int nvarsM1, int nvarsM2, int nvarsF, int nvarsR, int alpha0, int *liftcoefs, SCIP_Real *cutact, int *liftrhs)
static SCIP_RETCODE separateSequLiftedMinimalCoverInequality(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *mincovervars, int *nonmincovervars, int nmincovervars, int nnonmincovervars, SCIP_SOL *sol, SCIP_GUBSET *gubset, SCIP_Bool *cutoff, int *ncuts)
static SCIP_RETCODE makeCoverMinimal(SCIP *scip, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int *ncovervars, int *nnoncovervars, SCIP_Longint *coverweight, SCIP_Bool modtransused)
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, int pos)
#define MINGAINPERNMINCOMPARISONS
static SCIP_RETCODE greedyCliqueAlgorithm(SCIP *const scip, SCIP_VAR **items, SCIP_Longint *weights, int nitems, SCIP_Longint capacity, SCIP_Bool sorteditems, SCIP_Real cliqueextractfactor, SCIP_Bool *const cutoff, int *const nbdchgs)
#define DEFAULT_CLIQUEEXTRACTFACTOR
#define DEFAULT_SIMPLIFYINEQUALITIES
static SCIP_RETCODE eventdataFree(SCIP *scip, SCIP_EVENTDATA **eventdata)
static SCIP_RETCODE detectRedundantConstraints(SCIP *scip, BMS_BLKMEM *blkmem, SCIP_CONS **conss, int nconss, SCIP_Bool *cutoff, int *ndelconss)
static SCIP_RETCODE GUBsetCreate(SCIP *scip, SCIP_GUBSET **gubset, int nvars, SCIP_Longint *weights, SCIP_Longint capacity)
static SCIP_RETCODE getLiftingSequence(SCIP *scip, SCIP_Real *solvals, SCIP_Longint *weights, int *varsF, int *varsC2, int *varsR, int nvarsF, int nvarsC2, int nvarsR)
#define CONSHDLR_PROPFREQ
#define MAXNCLIQUEVARSCOMP
static SCIP_RETCODE tightenWeightsLift(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, SCIP_Bool *cutoff)
static SCIP_RETCODE getFeasibleSet(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int *ncovervars, int *nnoncovervars, SCIP_Longint *coverweight, SCIP_Bool modtransused, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts)
static SCIP_RETCODE simplifyInequalities(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, int *nchgcoefs, int *nchgsides, int *naddconss, SCIP_Bool *cutoff)
enum GUBConsstatus GUBCONSSTATUS
static SCIP_RETCODE removeZeroWeights(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
#define CONSHDLR_PRESOLTIMING
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result)
#define DEFAULT_MAXSEPACUTS
static SCIP_RETCODE superadditiveUpLifting(SCIP *scip, SCIP_VAR **vars, int nvars, int ntightened, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Real *solvals, int *covervars, int *noncovervars, int ncovervars, int nnoncovervars, SCIP_Longint coverweight, SCIP_Real *liftcoefs, SCIP_Real *cutact)
static SCIP_RETCODE addNlrow(SCIP *scip, SCIP_CONS *cons)
static void getPartitionNoncovervars(SCIP *scip, SCIP_Real *solvals, int *noncovervars, int nnoncovervars, int *varsF, int *varsR, int *nvarsF, int *nvarsR)
static SCIP_RETCODE stableSort(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR **vars, SCIP_Longint *weights, int *cliquestartposs, SCIP_Bool usenegatedclique)
static SCIP_RETCODE tightenWeights(SCIP *scip, SCIP_CONS *cons, SCIP_PRESOLTIMING presoltiming, int *nchgcoefs, int *nchgsides, int *naddconss, int *ndelconss, SCIP_Bool *cutoff)
#define CONSHDLR_EAGERFREQ
static void consdataChgWeight(SCIP_CONSDATA *consdata, int item, SCIP_Longint newweight)
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, SCIP_Bool *redundant, int *nfixedvars, SCIP_Bool usenegatedclique)
#define KNAPSACKRELAX_MAXDNOM
#define DEFAULT_MAXROUNDS
#define CONSHDLR_ENFOPRIORITY
#define LINCONSUPGD_PRIORITY
#define CONSHDLR_DELAYSEPA
#define MAX_USECLIQUES_SIZE
#define DEFAULT_UPDATECLIQUEPARTITIONS
@ GUBVARSTATUS_BELONGSTOSET_F
@ GUBVARSTATUS_BELONGSTOSET_C1
@ GUBVARSTATUS_BELONGSTOSET_R
@ GUBVARSTATUS_BELONGSTOSET_C2
@ GUBVARSTATUS_CAPACITYEXCEEDED
static SCIP_RETCODE checkParallelObjective(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata)
static SCIP_RETCODE GUBconsAddVar(SCIP *scip, SCIP_GUBCONS *gubcons, int var)
static SCIP_RETCODE changePartitionFeasiblesetvars(SCIP *scip, SCIP_Longint *weights, int *varsC1, int *varsC2, int *nvarsC1, int *nvarsC2)
#define DEFAULT_DISAGGREGATION
static SCIP_RETCODE preprocessConstraintPairs(SCIP *scip, SCIP_CONS **conss, int firstchange, int chkind, int *ndelconss)
static SCIP_RETCODE GUBconsDelVar(SCIP *scip, SCIP_GUBCONS *gubcons, int var, int gubvarsidx)
#define DEFAULT_DETECTLOWERBOUND
static SCIP_RETCODE dualPresolving(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *ndelconss, SCIP_Bool *deleted)
#define CONSHDLR_DELAYPROP
#define EVENTTYPE_KNAPSACK
#define MAX_ZEROITEMS_SIZE
Constraint handler for knapsack constraints of the form , x binary and .
Constraint handler for linear constraints in their most general form, .
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIP_MAXTREEDEPTH
#define SCIP_LONGINT_FORMAT
SCIP_RETCODE SCIPincludeLinconsUpgrade(SCIP *scip, SCIP_DECL_LINCONSUPGD((*linconsupgd)), int priority, const char *conshdlrname)
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsCardinality(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int cardval, SCIP_VAR **indvars, SCIP_Real *weights, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPaddCoefKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight)
SCIP_RETCODE SCIPsolveKnapsackApproximately(SCIP *scip, int nitems, SCIP_Longint *weights, SCIP_Real *profits, SCIP_Longint capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval)
SCIP_RETCODE SCIPcleanupConssKnapsack(SCIP *scip, SCIP_Bool onlychecked, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPseparateKnapsackCuts(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, SCIP_VAR **vars, int nvars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_SOL *sol, SCIP_Bool usegubs, SCIP_Bool *cutoff, int *ncuts)
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPcreateConsBasicKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
SCIP_RETCODE SCIPchgCapacityKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_Longint capacity)
SCIP_RETCODE SCIPseparateRelaxedKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_SEPA *sepa, int nknapvars, SCIP_VAR **knapvars, SCIP_Real *knapvals, SCIP_Real valscale, SCIP_Real rhs, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts)
SCIP_RETCODE SCIPsolveKnapsackExactly(SCIP *scip, int nitems, SCIP_Longint *weights, SCIP_Real *profits, SCIP_Longint capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval, SCIP_Bool *success)
#define SCIP_DECL_LINCONSUPGD(x)
SCIP_RETCODE SCIPcreateConsKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPcopyConsLinear(SCIP *scip, SCIP_CONS **cons, SCIP *sourcescip, const char *name, int nvars, SCIP_VAR **sourcevars, SCIP_Real *sourcecoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode, SCIP_Bool global, SCIP_Bool *valid)
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Real SCIPgetDualfarkasKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_ROW * SCIPgetRowKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetDualsolKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPincludeConshdlrKnapsack(SCIP *scip)
SCIP_Bool SCIPisConsCompressionEnabled(SCIP *scip)
SCIP_Bool SCIPisTransformed(SCIP *scip)
SCIP_Bool SCIPisPresolveFinished(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNObjVars(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_CONS * SCIPfindOrigCons(SCIP *scip, const char *name)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
#define SCIPhashSix(a, b, c, d, e, f)
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
SCIP_RETCODE SCIPupdateLocalLowerbound(SCIP *scip, SCIP_Real newbound)
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLocalLowerbound(SCIP *scip)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
#define SCIPdebugMsgPrint
SCIP_Longint SCIPcalcGreComDiv(SCIP_Longint val1, SCIP_Longint val2)
SCIP_RETCODE SCIPcalcIntegralScalar(SCIP_Real *vals, int nvals, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Real *intscalar, SCIP_Bool *success)
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_CONS ** SCIPconshdlrGetCheckConss(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_Longint SCIPconshdlrGetNCutsFound(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrGetSignedPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)),)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrGetPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
int SCIPconshdlrGetSepaFreq(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPsetConshdlrDelvars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
SCIP_RETCODE SCIPsetConsSeparated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool separate)
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial)
SCIP_RETCODE SCIPsetConsEnforced(SCIP *scip, SCIP_CONS *cons, SCIP_Bool enforce)
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
SCIP_RETCODE SCIPunmarkConsPropagate(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPmarkConsPropagate(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPsetConsPropagated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool propagate)
SCIP_RETCODE SCIPsetConsChecked(SCIP *scip, SCIP_CONS *cons, SCIP_Bool check)
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
#define SCIPfreeBuffer(scip, ptr)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBufferArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPallocBuffer(scip, ptr)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_RETCODE SCIPdelNlRow(SCIP *scip, SCIP_NLROW *nlrow)
SCIP_RETCODE SCIPaddNlRow(SCIP *scip, SCIP_NLROW *nlrow)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
SCIP_RETCODE SCIPreleaseNlRow(SCIP *scip, SCIP_NLROW **nlrow)
SCIP_Bool SCIPnlrowIsInNLP(SCIP_NLROW *nlrow)
SCIP_RETCODE SCIPcreateNlRow(SCIP *scip, SCIP_NLROW **nlrow, const char *name, SCIP_Real constant, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, SCIP_EXPR *expr, SCIP_Real lhs, SCIP_Real rhs, SCIP_EXPRCURV curvature)
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONS *cons, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_RETCODE SCIPcreateEmptyRowUnspec(SCIP *scip, SCIP_ROW **row, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_Real SCIProwGetDualfarkas(SCIP_ROW *row)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
SCIP_Longint SCIPsepaGetNCutsFound(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
void SCIPupdateSolLPConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
SCIP_RETCODE SCIPupdateCutoffbound(SCIP *scip, SCIP_Real cutoffbound)
int SCIPgetNSepaRounds(SCIP *scip)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE SCIPgetSymActiveVariables(SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
SCIP_RETCODE SCIPextendPermsymDetectionGraphLinear(SCIP *scip, SYM_GRAPH *graph, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool *success)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPcutoffbounddelta(SCIP *scip)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
int SCIPvarGetNVlbs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsDeleted(SCIP_VAR *var)
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var)
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_RETCODE SCIPaddClique(SCIP *scip, SCIP_VAR **vars, SCIP_Bool *values, int nvars, SCIP_Bool isequation, SCIP_Bool *infeasible, int *nbdchgs)
SCIP_RETCODE SCIPcalcCliquePartition(SCIP *const scip, SCIP_VAR **const vars, int const nvars, int *const cliquepartition, int *const ncliques)
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_RETCODE SCIPcalcNegatedCliquePartition(SCIP *const scip, SCIP_VAR **const vars, int const nvars, int *const cliquepartition, int *const ncliques)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
int SCIPvarGetIndex(SCIP_VAR *var)
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
int SCIPvarGetNVubs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_RETCODE SCIPflattenVarAggregationGraph(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
int SCIPgetNCliques(SCIP *scip)
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_RETCODE SCIPgetNegatedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **negvars)
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
SCIP_RETCODE SCIPvarsGetProbvarBinary(SCIP_VAR ***vars, SCIP_Bool **negatedarr, int nvars)
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
void SCIPselectWeightedDownRealLongRealInt(SCIP_Real *realarray1, SCIP_Longint *longarray, SCIP_Real *realarray3, int *intarray, SCIP_Real *weights, SCIP_Real capacity, int len, int *medianpos)
void SCIPsortDownLongPtr(SCIP_Longint *longarray, void **ptrarray, int len)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortPtrPtrIntInt(void **ptrarray1, void **ptrarray2, int *intarray1, int *intarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortPtrPtrLongIntInt(void **ptrarray1, void **ptrarray2, SCIP_Longint *longarray, int *intarray1, int *intarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortDownPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortDownLongPtrPtrIntInt(SCIP_Longint *longarray, void **ptrarray1, void **ptrarray2, int *intarray1, int *intarray2, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownRealIntLong(SCIP_Real *realarray, int *intarray, SCIP_Longint *longarray, int len)
void SCIPsortPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownLongPtrInt(SCIP_Longint *longarray, void **ptrarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIP_RETCODE SCIPskipSpace(char **s)
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_Bool propagate
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
#define BMSclearMemoryArray(ptr, num)
struct BMS_BlkMem BMS_BLKMEM
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for managing constraints
public methods for managing events
public methods for implications, variable bounds, and cliques
public methods for LP management
public methods for message output
#define SCIPdebugPrintCons(x, y, z)
public data structures and miscellaneous methods
methods for selecting (weighted) k-medians
methods for sorting joint arrays of various types
public methods for separators
public methods for problem variables
public methods for branching rule plugins and branching
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for cuts and aggregation rows
public methods for event handler plugins and event handlers
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
GUBVARSTATUS * gubvarsstatus
GUBCONSSTATUS * gubconsstatus
structs for symmetry computations
methods for dealing with symmetry detection graphs
@ SCIP_CONFTYPE_PROPAGATION
#define SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(x)
#define SCIP_DECL_CONSGETPERMSYMGRAPH(x)
#define SCIP_DECL_CONSENFOLP(x)
#define SCIP_DECL_CONSINITPRE(x)
#define SCIP_DECL_CONSDELETE(x)
#define SCIP_DECL_CONSEXIT(x)
#define SCIP_DECL_CONSGETVARS(x)
#define SCIP_DECL_CONSINITSOL(x)
#define SCIP_DECL_CONSPRINT(x)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
#define SCIP_DECL_CONSSEPALP(x)
#define SCIP_DECL_CONSENFORELAX(x)
#define SCIP_DECL_CONSPROP(x)
#define SCIP_DECL_CONSGETNVARS(x)
#define SCIP_DECL_CONSRESPROP(x)
#define SCIP_DECL_CONSACTIVE(x)
#define SCIP_DECL_CONSENFOPS(x)
#define SCIP_DECL_CONSPARSE(x)
#define SCIP_DECL_CONSTRANS(x)
#define SCIP_DECL_CONSDEACTIVE(x)
#define SCIP_DECL_CONSPRESOL(x)
#define SCIP_DECL_CONSINITLP(x)
#define SCIP_DECL_CONSEXITPRE(x)
#define SCIP_DECL_CONSLOCK(x)
#define SCIP_DECL_CONSCOPY(x)
#define SCIP_DECL_CONSINIT(x)
struct SCIP_ConsData SCIP_CONSDATA
#define SCIP_DECL_CONSCHECK(x)
#define SCIP_DECL_CONSHDLRCOPY(x)
#define SCIP_DECL_CONSEXITSOL(x)
#define SCIP_DECL_CONSFREE(x)
#define SCIP_DECL_CONSSEPASOL(x)
#define SCIP_DECL_CONSDELVARS(x)
struct SCIP_EventData SCIP_EVENTDATA
#define SCIP_EVENTTYPE_UBTIGHTENED
#define SCIP_EVENTTYPE_VARFIXED
#define SCIP_EVENTTYPE_VARDELETED
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_EVENTTYPE_LBRELAXED
#define SCIP_EVENTTYPE_FORMAT
#define SCIP_EVENTTYPE_IMPLADDED
#define SCIP_EVENTTYPE_LBTIGHTENED
enum SCIP_BoundType SCIP_BOUNDTYPE
#define SCIP_DECL_SORTPTRCOMP(x)
#define SCIP_DECL_HASHKEYEQ(x)
#define SCIP_DECL_HASHGETKEY(x)
#define SCIP_DECL_HASHKEYVAL(x)
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_TRANSFORMING
enum SYM_Symtype SYM_SYMTYPE
#define SCIP_PRESOLTIMING_MEDIUM
unsigned int SCIP_PRESOLTIMING
#define SCIP_PRESOLTIMING_FAST
#define SCIP_PRESOLTIMING_EXHAUSTIVE
@ SCIP_VARSTATUS_MULTAGGR
@ SCIP_VARSTATUS_AGGREGATED