71#ifdef WITH_CARDINALITY_UPGRADE
76#define CONSHDLR_NAME "knapsack"
77#define CONSHDLR_DESC "knapsack constraint of the form a^T x <= b, x binary and a >= 0"
78#define CONSHDLR_SEPAPRIORITY +600000
79#define CONSHDLR_ENFOPRIORITY -600000
80#define CONSHDLR_CHECKPRIORITY -600000
81#define CONSHDLR_SEPAFREQ 0
82#define CONSHDLR_PROPFREQ 1
83#define CONSHDLR_EAGERFREQ 100
85#define CONSHDLR_MAXPREROUNDS -1
86#define CONSHDLR_DELAYSEPA FALSE
87#define CONSHDLR_DELAYPROP FALSE
88#define CONSHDLR_NEEDSCONS TRUE
90#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
91#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
93#define EVENTHDLR_NAME "knapsack"
94#define EVENTHDLR_DESC "bound change event handler for knapsack constraints"
95#define EVENTTYPE_KNAPSACK SCIP_EVENTTYPE_LBCHANGED \
96 | SCIP_EVENTTYPE_UBTIGHTENED \
97 | SCIP_EVENTTYPE_VARFIXED \
98 | SCIP_EVENTTYPE_VARDELETED \
99 | SCIP_EVENTTYPE_IMPLADDED
101#define LINCONSUPGD_PRIORITY +100000
103#define MAX_USECLIQUES_SIZE 1000
104#define MAX_ZEROITEMS_SIZE 10000
106#define KNAPSACKRELAX_MAXDELTA 0.1
107#define KNAPSACKRELAX_MAXDNOM 1000LL
108#define KNAPSACKRELAX_MAXSCALE 1000.0
110#define DEFAULT_SEPACARDFREQ 1
111#define DEFAULT_MAXROUNDS 5
112#define DEFAULT_MAXROUNDSROOT -1
113#define DEFAULT_MAXSEPACUTS 50
114#define DEFAULT_MAXSEPACUTSROOT 200
115#define DEFAULT_MAXCARDBOUNDDIST 0.0
117#define DEFAULT_DISAGGREGATION TRUE
118#define DEFAULT_SIMPLIFYINEQUALITIES TRUE
119#define DEFAULT_NEGATEDCLIQUE TRUE
121#define MAXABSVBCOEF 1e+5
122#define USESUPADDLIFT FALSE
124#define DEFAULT_PRESOLUSEHASHING TRUE
125#define HASHSIZE_KNAPSACKCONS 500
127#define DEFAULT_PRESOLPAIRWISE TRUE
128#define NMINCOMPARISONS 200000
129#define MINGAINPERNMINCOMPARISONS 1e-06
131#define DEFAULT_DUALPRESOLVING TRUE
132#define DEFAULT_DETECTCUTOFFBOUND TRUE
135#define DEFAULT_DETECTLOWERBOUND TRUE
138#define DEFAULT_CLIQUEEXTRACTFACTOR 0.5
139#define MAXCOVERSIZEITERLEWI 1000
141#define DEFAULT_USEGUBS FALSE
142#define GUBCONSGROWVALUE 6
143#define GUBSPLITGNC1GUBS FALSE
144#define DEFAULT_CLQPARTUPDATEFAC 1.5
146#define DEFAULT_UPDATECLIQUEPARTITIONS FALSE
147#define MAXNCLIQUEVARSCOMP 1000000
148#ifdef WITH_CARDINALITY_UPGRADE
149#define DEFAULT_UPGDCARDINALITY FALSE
159struct SCIP_ConshdlrData
165 SCIP_Longint* longints1;
167 SCIP_Longint* longints2;
189 SCIP_Real maxcardbounddist;
196 SCIP_Bool disaggregation;
197 SCIP_Bool simplifyinequalities;
198 SCIP_Bool negatedclique;
199 SCIP_Bool presolpairwise;
200 SCIP_Bool presolusehashing;
201 SCIP_Bool dualpresolving;
203 SCIP_Bool detectcutoffbound;
206 SCIP_Bool detectlowerbound;
209 SCIP_Bool updatecliquepartitions;
210 SCIP_Real cliqueextractfactor;
211 SCIP_Real clqpartupdatefac;
213#ifdef WITH_CARDINALITY_UPGRADE
224 SCIP_Longint* weights;
226 int* cliquepartition;
227 int* negcliquepartition;
234 int ncliqueslastnegpart;
235 int ncliqueslastpart;
236 SCIP_Longint capacity;
237 SCIP_Longint weightsum;
238 SCIP_Longint onesweightsum;
239 unsigned int presolvedtiming:5;
240 unsigned int sorted:1;
241 unsigned int cliquepartitioned:1;
242 unsigned int negcliquepartitioned:1;
243 unsigned int merged:1;
244 unsigned int cliquesadded:1;
245 unsigned int varsdeleted:1;
246 unsigned int existmultaggr:1;
347 (*eventdata)->cons = cons;
348 (*eventdata)->weight = weight;
374 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
375 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
376 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
377 assert(consdata->nvars == 0 || (consdata->cliquepartition !=
NULL && consdata->negcliquepartition !=
NULL));
379 if( !consdata->sorted )
389 (
void**)consdata->vars,
390 (
void**)consdata->eventdata,
391 consdata->cliquepartition,
392 consdata->negcliquepartition,
395 v = consdata->nvars - 1;
401 while(
w >= 0 && consdata->weights[v] == consdata->weights[
w] )
408 (
void**)(&(consdata->vars[
w+1])),
409 (
void**)(&(consdata->eventdata[
w+1])),
410 &(consdata->cliquepartition[
w+1]),
411 &(consdata->negcliquepartition[
w+1]),
419 if( consdata->cliquepartitioned )
423 for( pos = 0; pos < consdata->nvars; ++pos )
429 consdata->cliquepartitioned =
FALSE;
437 if( consdata->negcliquepartitioned )
441 for( pos = 0; pos < consdata->nvars; ++pos )
447 consdata->negcliquepartitioned =
FALSE;
450 else if( consdata->negcliquepartition[pos] ==
lastcliquenum )
455 consdata->sorted =
TRUE;
461 for(
i = 0;
i < consdata->nvars-1; ++
i )
462 assert(consdata->weights[
i] >= consdata->weights[
i+1]);
474 SCIP_Bool negatedclique
480 assert(consdata->nvars == 0 || (consdata->cliquepartition !=
NULL && consdata->negcliquepartition !=
NULL));
484 &&
SCIPgetNCliques(
scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastpart));
489 consdata->cliquepartitioned =
TRUE;
495 &&
SCIPgetNCliques(
scip) >= (int)(conshdlrdata->clqpartupdatefac * consdata->ncliqueslastnegpart));
500 consdata->negcliquepartitioned =
TRUE;
503 assert(!consdata->cliquepartitioned || consdata->ncliques <= consdata->nvars);
504 assert(!consdata->negcliquepartitioned || consdata->nnegcliques <= consdata->nvars);
548 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
549 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
550 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
552 for(
i = 0;
i < consdata->nvars;
i++)
556 eventhdlr, consdata->eventdata[
i], &consdata->eventdata[
i]->filterpos) );
573 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
574 assert(consdata->nvars == 0 || consdata->weights !=
NULL);
575 assert(consdata->nvars == 0 || consdata->eventdata !=
NULL);
577 for(
i = 0;
i < consdata->nvars;
i++)
580 eventhdlr, consdata->eventdata[
i], consdata->eventdata[
i]->filterpos) );
593 SCIP_Bool transformed
597 assert(consdata->nvars <= consdata->varssize);
599 if( num > consdata->varssize )
641 assert(consdata->weightsum >= 0);
642 assert(consdata->onesweightsum >= 0);
652 SCIP_Longint* weights,
653 SCIP_Longint capacity
657 SCIP_Longint constant;
664 (*consdata)->vars =
NULL;
665 (*consdata)->weights =
NULL;
666 (*consdata)->nvars = 0;
677 for( v = 0; v <
nvars; ++v )
683 assert( weights[v] >= 0 );
692 constant += weights[v];
705 (*consdata)->nvars =
k;
719 (*consdata)->varssize = (*consdata)->nvars;
720 (*consdata)->capacity = capacity - constant;
721 (*consdata)->eventdata =
NULL;
722 (*consdata)->cliquepartition =
NULL;
723 (*consdata)->negcliquepartition =
NULL;
724 (*consdata)->row =
NULL;
725 (*consdata)->nlrow =
NULL;
726 (*consdata)->weightsum = 0;
727 (*consdata)->onesweightsum = 0;
728 (*consdata)->ncliques = 0;
729 (*consdata)->nnegcliques = 0;
730 (*consdata)->presolvedtiming = 0;
731 (*consdata)->sorted =
FALSE;
732 (*consdata)->cliquepartitioned =
FALSE;
733 (*consdata)->negcliquepartitioned =
FALSE;
734 (*consdata)->ncliqueslastpart = -1;
735 (*consdata)->ncliqueslastnegpart = -1;
736 (*consdata)->merged =
FALSE;
737 (*consdata)->cliquesadded =
FALSE;
738 (*consdata)->varsdeleted =
FALSE;
739 (*consdata)->existmultaggr =
FALSE;
746 for( v = 0; v < (*consdata)->nvars; v++ )
760 for( v = 0; v < (*consdata)->nvars; ++v )
782 if( (*consdata)->row !=
NULL )
786 if( (*consdata)->nlrow !=
NULL )
790 if( (*consdata)->eventdata !=
NULL )
795 if( (*consdata)->negcliquepartition !=
NULL )
799 if( (*consdata)->cliquepartition !=
NULL )
803 if( (*consdata)->vars !=
NULL )
808 for( v = 0; v < (*consdata)->nvars; v++ )
815 assert( (*consdata)->varssize > 0 );
846 if( consdata->eventdata !=
NULL )
853 consdata->presolvedtiming = 0;
854 consdata->sorted =
FALSE;
859 consdata->cliquesadded =
FALSE;
882 for(
i = 0;
i < consdata->nvars; ++
i )
907 if( consdata->row ==
NULL )
943 if( consdata->nlrow ==
NULL )
949 for(
i = 0;
i < consdata->nvars; ++
i )
950 coefs[
i] = (SCIP_Real)consdata->weights[
i];
953 consdata->nvars, consdata->vars, coefs,
NULL,
987 SCIPdebugMsg(
scip,
"checking knapsack constraint <%s> for feasibility of solution %p (lprows=%u)\n",
1017 for( v = consdata->nvars - 1; v >= 0; --v )
1028 for( v = consdata->nvars - 1; v >= 0; --v )
1039 absviol -= consdata->capacity;
1068#define IDX(j,d) ((j)*(intcap)+(d))
1092 SCIP_Longint* weights,
1094 SCIP_Longint capacity,
1112 SCIP_Longint weightsum;
1120 SCIP_Longint minweight;
1121 SCIP_Longint maxweight;
1139 for(
j = nitems - 1;
j >= 0; --
j )
1146 if( solval !=
NULL )
1171 for(
j = 0;
j < nitems; ++
j )
1176 if( weights[
j] > capacity )
1188 else if( weights[
j] == 0 )
1193 if( solval !=
NULL )
1230 if( weightsum > 0 && weightsum <= capacity )
1239 if( solval !=
NULL )
1246 assert(0 < minweight && minweight <= capacity );
1247 assert(0 < maxweight && maxweight <= capacity);
1274 assert(minweight <= capacity);
1277 if( minweight > capacity / 2 )
1281 SCIPdebugMsg(
scip,
"Only one item fits into knapsack, so take the best.\n");
1305 if( solval !=
NULL )
1330 for(
i = capacity - 1;
i >= 0; --
i )
1345 if( solval !=
NULL )
1409 for(
l = 0;
l <
j; ++
l )
1415 if( solval !=
NULL )
1425 capacity -= (minweight - 1);
1440 assert(
sizeof(
size_t) >=
sizeof(
int));
1537 assert((SCIP_Longint)
d >= -minweight);
1566 for( ;
j >= 0; --
j )
1574 if( solval !=
NULL )
1596 SCIP_Longint* weights,
1598 SCIP_Longint capacity,
1624 if( solval !=
NULL )
1630 for(
j = nitems - 1;
j >= 0; --
j )
1646 if( solval !=
NULL )
1652 for( ;
j < nitems;
j++ )
1680 for(
c = 0;
c <
gubset->ngubconss;
c++ )
1687 if(
gubset->gubconss[
c]->ngubvars > 1 )
1695 for( v = 0; v <
gubset->gubconss[
c]->ngubvars; v++ )
1700 if( solvals !=
NULL )
1712 if( solvals !=
NULL )
1745 (*gubcons)->ngubvars = 0;
1977 SCIP_Longint* weights,
1978 SCIP_Longint capacity
1995 (*gubset)->ngubconss =
nvars;
1996 (*gubset)->nvars =
nvars;
2008 (*gubset)->gubconssidx[
i] =
i;
2009 (*gubset)->gubvarsidx[
i] = 0;
2010 assert((*gubset)->gubconss[
i]->ngubvars == 1);
2013 if( weights[
i] > capacity )
2037 for(
i = (*gubset)->ngubconss-1;
i >= 0; --
i )
2081 SCIPdebugMsg(
scip,
" var<%d> should be in GUB<%d> at position<%d>, but stored is var<%d> instead\n",
i,
2088 for(
i = 0;
i <
gubset->ngubconss;
i++ )
2092 for(
j = 0;
j <
gubset->gubconss[
i]->ngubvars;
j++ )
2101 for(
k =
j+1;
k <
gubset->gubconss[
i]->ngubvars;
k++ )
2110 SCIPdebugMsg(
scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n",
i,
j,
2113 SCIPdebugMsg(
scip,
" GUB<%d>: var<%d,%s> and var<%d,%s> do not share a clique\n",
i,
j,
2143 int*
const cliquepartition,
2184 cliquepartition[
i] = -1;
2222 if( cliquepartition[
varseq[
i]] == -1 )
2227 cliquepartition[
varseq[
i]] = *ncliques;
2277 if( cliquepartition[
varseq[
i]] == -1 )
2279 cliquepartition[
varseq[
i]] = *ncliques;
2304 int* cliquepartition;
2330 for(
i = 0;
i < ncliques;
i++ )
2338 assert(cliquepartition[
i] >= 0);
2398 SCIP_Longint* weights,
2399 SCIP_Longint capacity,
2417 SCIP_Bool infeasible;
2473 if( weights[
j] > capacity )
2503 assert(nfixedones + nfixedzeros + nitems ==
nvars - (*ntightened));
2532 for(
j = 0;
j < nitems;
j++ )
2567 for(
j = 0;
j < nitems;
j++ )
2591 for(
j = 0;
j < nfixedones;
j++ )
2599 for(
j = 0;
j < nfixedzeros;
j++ )
2626 SCIP_Longint* weights,
2627 SCIP_Longint capacity,
2635 SCIP_Longint minweight;
2645 for(
i = 0;
i <
j;
i++ )
2653 for(
i = 0;
i <
j;
i++ )
2719 SCIP_Longint* weights,
2759 SCIP_Longint* weights,
2849 SCIP_Longint* weights,
2936 SCIP_Longint* weights,
3133 for(
i = 0;
i <
gubset->ngubconss;
i++ )
3398 (*ngubconscapexceed) =
ngubconss - (
ngubconsGOC1 + (*ngubconsGC2) + (*ngubconsGFC1) + (*ngubconsGR));
3490 SCIP_Longint* weights,
3491 SCIP_Longint capacity,
3552 (*cutact) += solvals[
varsM1[
j]];
3580 SCIP_Longint weight;
3617 right = (*liftrhs) + 1;
3618 while( left < right - 1 )
3620 middle = (left + right) / 2;
3627 assert(left == right - 1);
3682 SCIP_Longint weight;
3701 while( left < right - 1 )
3703 middle = (left + right) / 2;
3710 assert(left == right - 1);
3772 SCIP_Longint weight;
3782 assert(capacity - weight >= 0);
3801 right = (*liftrhs) + 1;
3802 while( left < right - 1)
3804 middle = (left + right) / 2;
3811 assert(left == right - 1);
3939 SCIP_Longint* weights,
3940 SCIP_Longint capacity,
3964 SCIP_Longint weight;
4059 (*cutact) += solvals[
varidx];
4274 assert(capacity - weight >= 0);
4304 right = (*liftrhs) + 1;
4305 while( left < right - 1 )
4307 middle = (left + right) / 2;
4314 assert(left == right - 1);
4460 while( left < right - 1 )
4462 middle = (left + right) / 2;
4469 assert(left == right - 1);
4549 assert(capacity - weight >= 0);
4570 right = (*liftrhs) + 1;
4571 while( left < right - 1 )
4573 middle = (left + right) / 2;
4580 assert(left == right - 1);
4674 SCIP_Longint* weights,
4675 SCIP_Longint capacity,
4690 SCIP_Longint lambda;
4753 SCIP_Longint weight;
4807 SCIP_Longint* weights,
4808 SCIP_Longint capacity,
4968 else if ( sepa !=
NULL )
5041 SCIP_Longint* weights,
5042 SCIP_Longint capacity,
5117 SCIP_CALL(
sequentialUpAndDownLifting(
scip,
vars,
nvars, ntightened, weights, capacity, solvals,
varsT1,
varsT2,
varsF,
varsR,
5135 else if ( sepa !=
NULL )
5208 SCIP_Longint* weights,
5209 SCIP_Longint capacity,
5262 else if ( sepa !=
NULL )
5317 SCIP_Longint* weights,
5318 SCIP_Longint capacity,
5330 SCIP_Longint minweight;
5417 for(
k =
j;
k < (*ncovervars) - 1;
k++ )
5471 SCIP_Longint* weights,
5472 SCIP_Longint capacity,
5539 (*coverweight) -= weights[
covervars[0]];
5540 for(
k = 0;
k < (*ncovervars) - 1;
k++ )
5569 SCIP_Longint* weights,
5570 SCIP_Longint capacity,
5620 SCIPdebugMsg(
scip,
"separate cuts for knapsack constraint originated by cons <%s>:\n",
5660 SCIPdebugMsg(
scip,
" LMCI1-GUB terminated by no variable with fractional LP value.\n");
5765 SCIP_CALL(
getFeasibleSet(
scip, cons, sepa,
vars,
nvars, ntightened, weights, capacity, solvals,
covervars,
noncovervars,
5838 if( conshdlr ==
NULL )
5851 usegubs = conshdlrdata->usegubs;
5858 if( conshdlrdata->reals1size == 0 )
5861 conshdlrdata->reals1size = 1;
5862 conshdlrdata->reals1[0] = 0.0;
5865 assert(conshdlrdata->reals1size > 0);
5871 if( conshdlrdata->reals1size <
nbinvars )
5873 int oldsize = conshdlrdata->reals1size;
5875 conshdlrdata->reals1size =
nbinvars;
5879 binvals = conshdlrdata->reals1;
5920 SCIPdebugMsg(
scip,
"Solution value %.15g <%s> outside domain [0.0, 1.0]\n",
5965 SCIPdebugMsg(
scip,
"variable bound <%s>[%g,%g] >= %g<%s>[%g,%g] + %g implies local cutoff\n",
5988 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with lower bound %.15g (rhs=%.15g)\n",
6007 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable lower bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6045 SCIPdebugMsg(
scip,
"variable bound <%s>[%g,%g] <= %g<%s>[%g,%g] + %g implies local cutoff\n",
6068 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with upper bound %.15g (rhs=%.15g)\n",
6087 SCIPdebugMsg(
scip,
" -> non-binary variable %+.15g<%s>(%.15g) replaced with variable upper bound %+.15g<%s>(%.15g) %+.15g (rhs=%.15g)\n",
6152 consvars[nconsvars] =
var;
6158 SCIP_Longint capacity;
6170 for(
i = 0;
i < nconsvars; ++
i )
6183 SCIPdebugMsg(
scip,
"minactivity of knapsack relaxation implies local cutoff\n");
6191 SCIP_CALL(
SCIPseparateKnapsackCuts(
scip, cons, sepa, consvars, nconsvars,
consvals, capacity,
sol, usegubs,
cutoff, ncuts) );
6253 consdata->capacity,
sol, usegubs,
cutoff, ncuts) );
6276 if( consdata->row !=
NULL )
6285 consdata->capacity -= weight;
6296 consdata->vars[consdata->nvars] =
var;
6297 consdata->weights[consdata->nvars] = weight;
6315 conshdlrdata->eventhdlr, consdata->eventdata[consdata->nvars-1],
6316 &consdata->eventdata[consdata->nvars-1]->filterpos) );
6319 consdata->existmultaggr =
TRUE;
6323 consdata->presolvedtiming = 0;
6324 consdata->cliquesadded =
FALSE;
6330 consdata->sorted =
FALSE;
6331 consdata->cliquepartitioned =
FALSE;
6332 consdata->negcliquepartitioned =
FALSE;
6333 consdata->merged =
FALSE;
6354 var = consdata->vars[pos];
6359 if( consdata->row !=
NULL )
6375 conshdlrdata->eventhdlr, consdata->eventdata[pos], consdata->eventdata[pos]->filterpos) );
6379 consdata->presolvedtiming = 0;
6380 consdata->sorted = (consdata->sorted && pos == consdata->nvars - 1);
6387 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
6388 consdata->weights[pos] = consdata->weights[consdata->nvars-1];
6389 if( consdata->eventdata !=
NULL )
6390 consdata->eventdata[pos] = consdata->eventdata[consdata->nvars-1];
6396 if( consdata->cliquepartitioned )
6401 if( consdata->cliquepartition[consdata->nvars - 1] != consdata->nvars - 1 )
6406 consdata->cliquepartition[pos] = consdata->cliquepartition[consdata->nvars-1];
6409 if( consdata->cliquepartition[pos] > pos )
6410 consdata->cliquepartitioned =
FALSE;
6418 if(
oldcliqenum > consdata->cliquepartition[pos] )
6420 for(
i = 0;
i < consdata->nvars; ++
i )
6425 consdata->cliquepartitioned =
FALSE;
6431 if(
i == consdata->nvars )
6432 --(consdata->ncliques);
6442 consdata->cliquepartitioned =
FALSE;
6445 else if( pos == consdata->nvars - 1)
6451 --(consdata->ncliques);
6457 --(consdata->ncliques);
6460 if( consdata->negcliquepartitioned )
6462 assert(consdata->negcliquepartition !=
NULL);
6465 if( consdata->negcliquepartition[consdata->nvars-1] != consdata->nvars - 1 )
6470 consdata->negcliquepartition[pos] = consdata->negcliquepartition[consdata->nvars-1];
6473 if( consdata->negcliquepartition[pos] > pos )
6474 consdata->negcliquepartitioned =
FALSE;
6482 if(
oldcliqenum > consdata->negcliquepartition[pos] )
6484 for(
i = 0;
i < consdata->nvars; ++
i )
6489 consdata->negcliquepartitioned =
FALSE;
6495 if(
i == consdata->nvars )
6496 --(consdata->nnegcliques);
6506 consdata->negcliquepartitioned =
FALSE;
6509 else if( pos == consdata->nvars - 1)
6515 --(consdata->nnegcliques);
6521 --(consdata->nnegcliques);
6524 --(consdata->nvars);
6542 for( v = consdata->nvars-1; v >= 0; --v )
6544 if( consdata->weights[v] == 0 )
6573 for(
i = 0;
i < nconss;
i++ )
6578 if( consdata->varsdeleted )
6581 for( v = consdata->nvars - 1; v >= 0; --v )
6588 consdata->varsdeleted =
FALSE;
6616 if( consdata->merged )
6619 if( consdata->nvars <= 1 )
6621 consdata->merged =
TRUE;
6625 assert(consdata->vars !=
NULL || consdata->nvars == 0);
6632 consdata->sorted =
FALSE;
6634 v = consdata->nvars - 1;
6647 var1 = consdata->vars[v];
6657 var2 = consdata->vars[prev];
6673 consdataChgWeight(consdata, prev, consdata->weights[v] + consdata->weights[prev]);
6679 else if( consdata->weights[v] == consdata->weights[prev] )
6682 consdata->capacity -= consdata->weights[v];
6688 else if( consdata->weights[v] < consdata->weights[prev] )
6690 consdata->capacity -= consdata->weights[v];
6691 consdataChgWeight(consdata, prev, consdata->weights[prev] - consdata->weights[v]);
6692 assert(consdata->weights[prev] > 0);
6697 consdata->capacity -= consdata->weights[prev];
6699 assert(consdata->weights[v] > 0);
6702 if( consdata->nvars != v )
6710 consdata->cliquesadded =
FALSE;
6717 consdata->cliquesadded =
FALSE;
6723 consdata->merged =
TRUE;
6726 if( consdata->onesweightsum > consdata->capacity )
6755 SCIP_Bool infeasible;
6756 SCIP_Bool tightened;
6757 SCIP_Bool applicable;
6775 nvars = consdata->nvars;
6776 vars = consdata->vars;
6788 for( v = 0; v <
nvars; ++v )
6843 SCIPdebugMsg(
scip,
"variable <%s> only locked up in knapsack constraints: dual presolve <%s>[%.15g,%.15g] >= 1.0\n",
6856 SCIPdebugMsg(
scip,
"variable <%s> has no down locks: dual presolve <%s>[%.15g,%.15g] <= 0.0\n",
6894 SCIP_Bool applicable;
6907 nvars = consdata->nvars;
6922 vars = consdata->vars;
6929 for( v = 0; v <
nvars && applicable; ++v )
6951 weight = (
SCIP_Real)consdata->weights[v];
6958 scale = weight / -
objval;
6981 SCIP_Real cutoffbound;
6987 cutoffbound = (consdata->capacity -
offset) / scale;
6989 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
6997 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a cutoff bound <%g>\n",
7017 SCIP_Real lowerbound;
7023 lowerbound = (consdata->capacity -
offset) / scale;
7025 SCIPdebugMsg(
scip,
"constraint <%s> is parallel to objective function and provids a lower bound <%g>\n",
7042 SCIP_Longint* weights,
7044 SCIP_Bool usenegatedclique
7050 int* cliquepartition;
7068 origvars = consdata->vars;
7077 if( usenegatedclique )
7079 assert(consdata->negcliquepartitioned);
7081 cliquepartition = consdata->negcliquepartition;
7082 ncliques = consdata->nnegcliques;
7086 assert(consdata->cliquepartitioned);
7088 cliquepartition = consdata->cliquepartition;
7089 ncliques = consdata->ncliques;
7102 assert(0 <= cliquepartition[v] && cliquepartition[v] < ncliques);
7117 for(
c = 0;
c < ncliques; ++
c )
7178 assert(consdata->nvars == 0 || consdata->vars !=
NULL);
7187 if ( consdata->onesweightsum > consdata->capacity )
7198 consdata->existmultaggr =
FALSE;
7205 var = consdata->vars[v];
7211 consdata->capacity -= consdata->weights[v];
7213 consdata->cliquesadded =
FALSE;
7225 SCIP_Longint weight;
7228 weight = consdata->weights[v];
7285 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-integral value for weight*aggrconst = %g\n", weight*
aggrconst);
7293 for(
i = naggrvars - 1;
i >= 0; --
i )
7300 SCIPerrorMessage(
"try to resolve a multi-aggregation with a non-binary %svariable <%s> with bounds [%g,%g]\n",
7331 if( consdata->capacity < 0 )
7353 assert(consdata->onesweightsum == 0);
7378 SCIP_Bool* redundant,
7380 SCIP_Bool usenegatedclique
7384 SCIP_Bool infeasible;
7385 SCIP_Bool tightened;
7424 for(
i = 0;
i < consdata->nvars && consdata->merged; ++
i )
7430 usenegatedclique = usenegatedclique && consdata->merged;
7438 nvars = consdata->nvars;
7453 if( usenegatedclique &&
nvars > 0 )
7461 nnegcliques = consdata->nnegcliques;
7464 if( nnegcliques ==
nvars )
7467 usenegatedclique =
FALSE;
7483 for(
c = 0;
c < nnegcliques; ++
c )
7500 if( nnegcliques -
c ==
nvars -
i )
7617 for(
c = 0;
c < nnegcliques; ++
c )
7625 assert(nnegcliques == consdata->nnegcliques);
7746 if( consdata->capacity <
minweightsum + consdata->onesweightsum )
7749 consdata->onesweightsum, consdata->capacity);
7758 SCIP_Longint weight;
7764 for(
i = 0;
i <
nvars && weight <= consdata->capacity;
i++ )
7769 weight += consdata->weights[
i];
7780 if( !usenegatedclique )
7782 assert(consdata->sorted);
7795 assert(consdata->onesweightsum + consdata->weights[
i] > consdata->capacity);
7855 assert(consdata->nvars > 1);
7858 if( consdata->nvars == 2 )
7924 SCIP_Longint* weights;
7925 SCIP_Longint capacity;
7944 vars = consdata->vars;
7945 weights = consdata->weights;
7946 nvars = consdata->nvars;
7947 capacity = consdata->capacity;
7954 assert(weights[
w] <= weights[
w-1]);
7958 if( consdata->nvars - 1 ==
splitpos )
7964 if( consdata->weightsum - weights[
splitpos] <= capacity )
7974 consdata->capacity -= weights[
w];
7984 for( ;
w >= 0 &&
gcd > 1; --
w )
7996 (*nchgcoefs) +=
nvars;
7998 consdata->capacity /=
gcd;
8006 for(
w = consdata->nvars - 1;
w > 0; --
w )
8007 assert(weights[
w] <= weights[
w - 1]);
8014 else if( conshdlrdata->disaggregation &&
frontsum + weights[
splitpos + 1] <= capacity )
8037 for(
w = 0;
w < len; ++
w )
8066 for(
w = 0;
w < len; ++
w )
8108 weights = consdata->weights;
8112 for( ;
w >= 0 &&
gcd > 1; --
w )
8124 (*nchgcoefs) +=
nvars;
8126 consdata->capacity /=
gcd;
8137 for(
w = consdata->nvars - 1;
w > 0; --
w )
8138 assert(weights[
w] <= weights[
w - 1]);
8173 SCIP_Longint* weights;
8174 SCIP_Longint capacity;
8190 assert(consdata->nvars >= 2);
8191 assert(consdata->weightsum > consdata->capacity);
8194 vars = consdata->vars;
8195 weights = consdata->weights;
8196 nvars = consdata->nvars;
8197 capacity = consdata->capacity;
8201 for( v = 0; v <
nvars && sum + weights[v] <= capacity; ++v )
8207 if( v ==
nvars - 1 )
8219 assert(consdata->nvars > 1);
8222 if( v == consdata->nvars - 1 )
8236 assert(weights == consdata->weights);
8238 assert(capacity == consdata->capacity);
8246 if( consdata->cliquepartition[v] < v )
8256 clqpart = consdata->cliquepartition;
8280 if( conshdlrdata->disaggregation &&
w ==
nvars )
8291 ncliques = consdata->ncliques;
8296 for(
c = 0;
c < ncliques; ++
c )
8366 assert(consdata->onesweightsum == 0);
8367 assert(consdata->weightsum > consdata->capacity);
8368 assert(consdata->nvars >= 1);
8373 gcd = consdata->weights[consdata->nvars-1];
8374 for(
i = consdata->nvars-2;
i >= 0 &&
gcd >= 2; --
i )
8386 for(
i = 0;
i < consdata->nvars; ++
i )
8390 consdata->capacity /=
gcd;
8391 (*nchgcoefs) += consdata->nvars;
8396 for(
i = consdata->nvars - 1;
i > 0; --
i )
8397 assert(consdata->weights[
i] <= consdata->weights[
i - 1]);
8399 consdata->sorted =
TRUE;
8433 SCIP_Longint* weights;
8436 SCIP_Longint capacity;
8460 assert(consdata->weightsum > consdata->capacity);
8461 assert(consdata->nvars >= 2);
8462 assert(consdata->sorted);
8465 assert(consdata->merged);
8467 nvars = consdata->nvars;
8468 weights = consdata->weights;
8469 capacity = consdata->capacity;
8474 if( weights[
nvars - 1] + weights[
nvars - 2] > capacity )
8501 if( consdata->weightsum - weights[
nvars - 1] <= consdata->capacity )
8511 if( consdata->weightsum - capacity > weights[0] + weights[1] )
8532 while( v <
nvars && weights[v] + weights[
nvars - 1] > capacity )
8558 for( v = 0; v <
vbig; ++v )
8568 for( ; v <
nvars; ++v )
8570 if( weights[v] > 1 )
8583 for( v =
nvars - 1; v > 0; --v )
8584 assert(weights[v] <= weights[v-1]);
8616 for( v = 0; v <
vbig; ++v )
8626 for( ; v <
nvars; ++v )
8628 if( weights[v] > 1 )
8641 for( v =
nvars - 1; v > 0; --v )
8642 assert(weights[v] <= weights[v-1]);
8671 for( v = 0; v <
vbig; ++v )
8679 for( v = 0; v <
vbig; ++v )
8689 for( ; v <
nvars; ++v )
8691 if( weights[v] > 1 )
8704 for( v =
nvars - 1; v > 0; --v )
8705 assert(weights[v] <= weights[v-1]);
8741 if( v >=
nvars - 1 )
8744 if( v ==
nvars - 1 )
8771 if( v > 0 && weights[
nvars - 2] > 1 )
8776 for(
w = 0;
w < v; ++
w )
8778 if( weights[
w] > 2 )
8786 assert(weights[v - 1] == 2);
8794 if( weights[
w] > 1 )
8805 consdata->capacity = (-2 + v * 2 +
nvars - v);
8806 assert(consdata->capacity > 0);
8807 assert(weights[0] <= consdata->capacity);
8808 assert(consdata->weightsum > consdata->capacity);
8819 SCIP_Longint minweight = weights[
nvars - 1];
8843 (*nchgcoefs) += (v -
startv);
8875 for( ;
w >= 0; --
w )
8894 if( weights[v] > 1 || (weights[
startv] > (SCIP_Longint)
nvars - v) || (
startv > 0 && weights[0] == (SCIP_Longint)
nvars - v + 1) )
8901 if( weights[
w] > 1 )
8927 for( ;
w >= 0; --
w )
8940 if( consdata->capacity >
newcap )
8942 consdata->capacity =
newcap;
8951 assert(consdata->weightsum - consdata->capacity == (SCIP_Longint)
nvars - v + 1);
8958 assert(weights[
w] <= weights[
w - 1]);
8965 while(
end >= 0 && weights[
end] == weights[
end + 1] )
9000 for( ; v <=
end; ++v )
9019 for(
w = 0;
w < v; ++
w )
9026 for( ; v <=
end; ++v )
9037 (*nchgcoefs) +=
nvars;
9040 consdata->capacity *= 2;
9055 for(
k = 0;
k < 4; ++
k )
9096 minweight = weights[
end];
9112 (*nchgcoefs) += (v -
startv);
9123 while(
end >= 0 && weights[
end] == weights[
end + 1] )
9129 minweight = weights[
end];
9151 (*nchgcoefs) += (v -
startv);
9188 for( ; v <=
end; ++v )
9207 for(
w = 0;
w < v; ++
w )
9214 for( ; v <=
end; ++v )
9225 (*nchgcoefs) +=
nvars;
9228 consdata->capacity *= 2;
9254 assert(weights[0] <= consdata->capacity);
9261 assert(weights[
w] <= weights[
w - 1]);
9293 SCIP_Longint* weights;
9294 SCIP_Longint capacity;
9295 SCIP_Bool infeasible;
9309 nvars = consdata->nvars;
9314 assert(consdata->capacity >= 0);
9325 vars = consdata->vars;
9326 weights = consdata->weights;
9327 capacity = consdata->capacity;
9331 while( v <
nvars && weights[v] > capacity )
9354 for( --v; v >= 0; --v )
9363 assert(weights == consdata->weights);
9365 assert(consdata->sorted);
9366 assert(weights[0] <= capacity);
9413 SCIP_Longint* weights;
9416 SCIP_Longint weight;
9445 assert(consdata->merged);
9449 assert(consdata->capacity >= 0);
9471 weights = consdata->weights;
9472 nvars = consdata->nvars;
9476 for( v =
nvars - 1; v > 0; --v )
9477 assert(weights[v] <= weights[v-1]);
9482 for( v =
nvars - 2; v >= 0 &&
gcd > 1; --v )
9490 for( v =
nvars - 1; v >= 0; --v )
9494 (*nchgcoefs) +=
nvars;
9496 consdata->capacity /=
gcd;
9505 for( v =
nvars - 1; v > 0; --v )
9506 assert(weights[v] <= weights[v-1]);
9515 vars = consdata->vars;
9516 weights = consdata->weights;
9517 nvars = consdata->nvars;
9520 if( weights[
nvars - 1] == 1 && weights[
nvars - 2] == 1 )
9527 while( weights[v] == consdata->capacity )
9534 if( v ==
nvars - 1 )
9548 weight = weights[v];
9576 if( v ==
nvars - 2 )
9612 rest = consdata->capacity %
gcd;
9622 consdata->capacity -=
rest;
9626 for( v = 0; v <
offsetv; ++v )
9648 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);
9659 consdata->capacity -=
rest;
9663 for( v = 0; v <
offsetv; ++v )
9687 assert(consdata->weights == weights);
9691 for( v =
nvars - 1; v >= 0; --v )
9695 (*nchgcoefs) +=
nvars;
9697 consdata->capacity /=
gcd;
9704 while(
nvars >= 2 );
9756 SCIPdebugMsg(
scip,
"memory limit of %d bytes reached in knapsack preprocessing - abort collecting zero items\n",
9786#define MAX_CLIQUELENGTH 50
9848 assert(consdata->weightsum > consdata->capacity);
9849 assert(consdata->nvars > 0);
9850 assert(consdata->merged);
9852 nvars = consdata->nvars;
9880 assert(conshdlrdata->ints1size > 0);
9881 assert(conshdlrdata->ints2size > 0);
9882 assert(conshdlrdata->longints1size > 0);
9883 assert(conshdlrdata->longints2size > 0);
9889 if( conshdlrdata->ints1size <
nbinvars )
9891 int oldsize = conshdlrdata->ints1size;
9893 conshdlrdata->ints1size =
nbinvars;
9897 if( conshdlrdata->ints2size <
nbinvars )
9899 int oldsize = conshdlrdata->ints2size;
9901 conshdlrdata->ints2size =
nbinvars;
9905 if( conshdlrdata->longints1size <
nbinvars )
9907 int oldsize = conshdlrdata->longints1size;
9909 conshdlrdata->longints1size =
nbinvars;
9913 if( conshdlrdata->longints2size <
nbinvars )
9915 int oldsize = conshdlrdata->longints2size;
9917 conshdlrdata->longints2size =
nbinvars;
9947 assert(conshdlrdata->bools1size > 0);
9948 assert(conshdlrdata->bools2size > 0);
9954 if( conshdlrdata->bools1size <
nbinvars )
9956 int oldsize = conshdlrdata->bools1size;
9958 conshdlrdata->bools1size =
nbinvars;
9962 if( conshdlrdata->bools2size <
nbinvars )
9964 int oldsize = conshdlrdata->bools2size;
9966 conshdlrdata->bools2size =
nbinvars;
9998 SCIP_Longint weight;
10007 var = consdata->vars[
i];
10008 weight = consdata->weights[
i];
10077 if( probindex == -1 )
10113 assert(consdata->sorted);
10116 assert(conshdlrdata->bools3size > 0);
10122 if( conshdlrdata->bools3size < consdata->nvars )
10124 int oldsize = conshdlrdata->bools3size;
10126 conshdlrdata->bools3size = consdata->nvars;;
10135 for(
tmp = consdata->nvars - 1;
tmp >= 0; --
tmp )
10143 for(
i = 0;
i < consdata->nvars; ++
i )
10160 assert(conshdlrdata->bools4size > 0);
10166 if( conshdlrdata->bools4size < consdata->nvars )
10168 int oldsize = conshdlrdata->bools4size;
10170 conshdlrdata->bools4size = consdata->nvars;
10179 for(
tmp = consdata->nvars - 1;
tmp >= 0; --
tmp )
10191 for( val = 0; val < 2 &&
addweightsum < consdata->capacity; ++val )
10220 for(
j = 0;
j < consdata->nvars; ++
j )
10243 SCIP_Longint weight;
10247 var = binvars[probindex];
10375 SCIP_Longint* weights;
10377 SCIP_Longint capacity;
10379 SCIP_Longint maxweight;
10380 SCIP_Longint minweight;
10399 assert(consdata->onesweightsum == 0);
10400 assert(consdata->weightsum > consdata->capacity);
10401 assert(consdata->nvars > 0);
10412 assert(consdata->merged);
10417 for(
i = 0;
i < consdata->nvars; ++
i )
10419 SCIP_Longint weight;
10421 weight = consdata->weights[
i];
10424 newweight = consdata->weightsum - consdata->capacity;
10426 consdata->capacity -= (weight -
newweight);
10429 assert(!consdata->sorted);
10432 consdata->capacity + (weight-
newweight), consdata->capacity);
10438 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10442 if( consdata->weightsum <= consdata->capacity )
10450 weights = consdata->weights;
10451 nvars = consdata->nvars;
10452 capacity = consdata->capacity;
10455 pos <
nvars && weights[pos] + weights[pos + 1] > capacity )
10462 for(
k = 0;
k < 4; ++
k )
10518 maxweight = weights[pos];
10520 while( 2 * maxweight > capacity && maxweight +
sumcoef > capacity )
10532 maxweight = weights[pos];
10540 while( pos <
nvars && weights[pos] +
sumcoef == capacity )
10552 ((
k == 0) || (
k == 1 && weights[
nvars - 1] +
sumcoef + weights[pos] > capacity)) )
10575 consdata->weights[pos - 1] == consdata->capacity && (pos == consdata->nvars || consdata->weights[pos] == 1) )
10589 if( pos == consdata->nvars )
10610 len = consdata->nvars - pos;
10631 for(
w = pos - 1;
w >= 0; --
w )
10639 for(
w =
c;
w < len; ++
w )
10691 assert(consdata->merged);
10700 if( consdata->cliquepartition[consdata->nvars - 1] == consdata->nvars - 1 )
10707 for(
i = 0;
i < consdata->nvars; ++
i )
10709 SCIP_Longint weight;
10714 weight = consdata->weights[
i];
10729 for(
i = 0;
i < ncliques; ++
i )
10731 SCIP_Longint delta;
10752 for(
j = 0;
j <
i; ++
j )
10753 assert(consdata->cliquepartition[
j] <
i);
10755 for(
j =
i;
j < consdata->nvars; ++
j )
10757 if( consdata->cliquepartition[
j] ==
i )
10781 assert(consdata->cliquepartition[
j] ==
i);
10784 assert(consdata->cliquepartition[
j] ==
i);
10800 if( conshdlrdata->disaggregation || !
forceclique )
10811 assert(consdata->cliquepartition[
j] ==
i);
10818 assert(!consdata->sorted);
10857 while( !consdata->sorted && consdata->weightsum > consdata->capacity );
10865 if( consdata->weightsum <= consdata->capacity )
10877 if( consdata->weightsum <= consdata->capacity )
10883 assert(consdata->merged);
10885 minweight = consdata->weights[consdata->nvars-1];
10886 for(
i = 0;
i < consdata->nvars-1; ++
i )
10888 SCIP_Longint weight;
10890 weight = consdata->weights[
i];
10891 assert(weight >= minweight);
10892 if( minweight + weight > consdata->capacity )
10898 assert(consdata->sorted);
10900 assert(
i == 0 || consdata->weights[
i-1] >= consdata->weights[
i]);
10901 consdata->sorted =
TRUE;
10910 if( consdata->nvars >= 2 )
10912 SCIP_Longint weight;
10914 minweight = consdata->weights[consdata->nvars-2];
10915 weight = consdata->weights[consdata->nvars-1];
10916 assert(minweight >= weight);
10921 assert(consdata->sorted);
10923 assert(minweight >= consdata->weights[consdata->nvars-1]);
10924 consdata->sorted =
TRUE;
10989 nvars = consdata->nvars;
10992 if( consdata->cliquesadded ||
nvars == 0 )
11003 assert(consdata->merged);
11010 nnegcliques = consdata->nnegcliques;
11013 if( nnegcliques ==
nvars )
11028 for( v = 0; v <
nvars; ++v )
11030 assert(0 <= consdata->negcliquepartition[v] && consdata->negcliquepartition[v] <= nnegcliques);
11031 assert(consdata->weights[v] > 0);
11033 if( consdata->negcliquepartition[v] == nnegcliques )
11036 maxweights[consdata->negcliquepartition[v]] = consdata->weights[v];
11055 for( v = 0; v <
nvars; ++v )
11057 if( !
cliqueused[consdata->negcliquepartition[v]] )
11064 if( consdata->negcliquepartition[v] == consdata->negcliquepartition[
w]
11065 && consdata->weights[v] > consdata->weights[
w] )
11156 SCIP_Longint* weights,
11158 SCIP_Longint capacity,
11160 SCIP_Real cliqueextractfactor,
11267 SCIP_Real cliqueextractfactor,
11295 nvars = consdata->nvars;
11298 if( consdata->cliquesadded ||
nvars == 0 )
11309 assert(consdata->merged);
11316 nnegcliques = consdata->nnegcliques;
11329 if( nnegcliques <
nvars )
11335 SCIP_Longint weight;
11337 cliquenum = consdata->negcliquepartition[
i];
11340 weight = consdata->weights[
i];
11375 cliquenum = consdata->negcliquepartition[
i];
11402 consdata->cliquesadded =
TRUE;
11476 assert(consdata->nvars > 0);
11519 hashtablesize = nconss;
11525 for(
c = nconss - 1;
c >= 0; --
c )
11577 SCIPdebugMsg(
scip,
"knapsack constraints <%s> and <%s> with equal coefficients\n",
11833 SCIP_Bool violated;
11842 sol ==
NULL ?
"LP" :
"relaxation");
11847 maxncuts = (
SCIPgetDepth(
scip) == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
11876 else if ( ncuts > 0 )
11899 SCIP_Bool separate,
11909 SCIP_Bool modifiable,
11915 SCIP_Bool removable,
11917 SCIP_Bool stickingatnode
11923 SCIP_Longint* weights;
11924 SCIP_Longint capacity;
11925 SCIP_Longint weight;
11952 for( v = 0; v <
nvars; ++v )
11959 weights[v] = weight;
11964 weights[v] = -weight;
11965 capacity -= weight;
11972 initial, separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
12076 conshdlrdata->reals1size =
nvars;
12094 conshdlrdata->reals1size = 0;
12126 conshdlrdata->ints1size =
nvars;
12127 conshdlrdata->ints2size =
nvars;
12128 conshdlrdata->longints1size =
nvars;
12129 conshdlrdata->longints2size =
nvars;
12130 conshdlrdata->bools1size =
nvars;
12131 conshdlrdata->bools2size =
nvars;
12132 conshdlrdata->bools3size =
nvars;
12133 conshdlrdata->bools4size =
nvars;
12135#ifdef WITH_CARDINALITY_UPGRADE
12136 conshdlrdata->upgradedcard =
FALSE;
12153 for(
c = 0;
c < nconss; ++
c )
12174 conshdlrdata->ints1size = 0;
12175 conshdlrdata->ints2size = 0;
12176 conshdlrdata->longints1size = 0;
12177 conshdlrdata->longints2size = 0;
12178 conshdlrdata->bools1size = 0;
12179 conshdlrdata->bools2size = 0;
12180 conshdlrdata->bools3size = 0;
12181 conshdlrdata->bools4size = 0;
12194 for(
c = 0;
c < nconss; ++
c )
12213 for(
c = 0;
c < nconss; ++
c )
12218 if( consdata->row !=
NULL )
12223 if( consdata->nlrow !=
NULL )
12300 *infeasible =
FALSE;
12302 for(
i = 0;
i < nconss && !(*infeasible);
i++ )
12321 SCIP_Real cutoffbound;
12340 SCIPdebugMsg(
scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12344 if( (
depth == 0 && conshdlrdata->maxroundsroot >= 0 &&
nrounds >= conshdlrdata->maxroundsroot)
12345 || (
depth > 0 && conshdlrdata->maxrounds >= 0 &&
nrounds >= conshdlrdata->maxrounds) )
12350 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12352 && ((sepacardfreq == 0 &&
depth == 0) || (sepacardfreq >= 1 && (
depth % sepacardfreq == 0)));
12363 maxsepacuts = (
depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12378 else if ( ncuts > 0 )
12409 SCIPdebugMsg(
scip,
"knapsack separation of %d/%d constraints, round %d (max %d/%d)\n",
12413 if( (
depth == 0 && conshdlrdata->maxroundsroot >= 0 &&
nrounds >= conshdlrdata->maxroundsroot)
12414 || (
depth > 0 && conshdlrdata->maxrounds >= 0 &&
nrounds >= conshdlrdata->maxrounds) )
12419 sepacardfreq = sepafreq * conshdlrdata->sepacardfreq;
12421 && ((sepacardfreq == 0 &&
depth == 0) || (sepacardfreq >= 1 && (
depth % sepacardfreq == 0)));
12424 maxsepacuts = (
depth == 0 ? conshdlrdata->maxsepacutsroot : conshdlrdata->maxsepacuts);
12439 else if( ncuts > 0 )
12467 SCIP_Bool violated;
12470 for(
i = 0;
i < nconss;
i++ )
12488 SCIP_Bool violated;
12509 SCIP_Bool redundant;
12545 else if( nfixedvars > 0 )
12561 SCIP_Bool redundant;
12608 consdata->presolvedtiming = 0;
12609 else if( consdata->presolvedtiming >= presoltiming )
12614 consdata->presolvedtiming = presoltiming;
12659 if( consdata->weightsum <= consdata->capacity )
12760#ifdef WITH_CARDINALITY_UPGRADE
12797 SCIP_Longint* weights;
12806 nvars = consdata->nvars;
12807 vars = consdata->vars;
12808 weights = consdata->weights;
12815 if ( consdata->capacity >=
nvars )
12819 assert( consdata->sorted );
12820 if ( weights[0] != 1 || weights[
nvars-1] != 1 )
12824 for (v = 0; v <
nvars; ++v)
12833 var = consdata->vars[v];
12850 for (
j = 0;
j < nimpls; ++
j)
12883 for (v = 0; v <
nvars; ++v)
12907 for (v = 0; v <
nvars; ++v)
12917 conshdlrdata->upgradedcard =
TRUE;
12949 for (v = 0; v <
nvars; ++v)
12996 for(
i = 0;
i < consdata->nvars; ++
i )
13013 if( inferinfo < 0 )
13021 capsum = consdata->weights[inferinfo];
13024 for(
i = 0;
i < consdata->nvars && consdata->vars[
i] !=
infervar; ++
i )
13027 capsum = consdata->weights[
i];
13036 for(
i = 0;
i < consdata->nvars;
i++ )
13041 capsum += consdata->weights[
i];
13042 if(
capsum > consdata->capacity )
13074 for(
i = 0;
i < consdata->nvars;
i++)
13147 for(
i = 0;
i < consdata->nvars; ++
i )
13164 SCIP_Longint* weights;
13166 const char* consname;
13176 for( v = 0; v <
nvars; ++v )
13177 coefs[v] = (SCIP_Real) weights[v];
13187 initial, separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode, global,
valid) );
13200 SCIP_Longint weight;
13202 SCIP_Longint* weights;
13203 SCIP_Longint capacity;
13222 while( *
str !=
'\0' )
13251 if( varssize <=
nvars )
13259 weights[
nvars] = weight;
13293 initial, separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
13313 (*success) =
FALSE;
13334 (*nvars) = consdata->nvars;
13359 consdata->onesweightsum += eventdata->weight;
13360 consdata->presolvedtiming = 0;
13364 consdata->onesweightsum -= eventdata->weight;
13367 consdata->presolvedtiming = 0;
13371 if( !consdata->existmultaggr )
13380 consdata->existmultaggr =
TRUE;
13381 consdata->merged =
FALSE;
13385 consdata->merged =
FALSE;
13389 consdata->presolvedtiming = 0;
13392 consdata->varsdeleted =
TRUE;
13420 eventhdlrdata =
NULL;
13421 conshdlrdata->eventhdlr =
NULL;
13426 if( conshdlrdata->eventhdlr ==
NULL )
13476 "multiplier on separation frequency, how often knapsack cuts are separated (-1: never, 0: only at root)",
13480 "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for separating knapsack cuts",
13484 "lower clique size limit for greedy clique extraction algorithm (relative to largest clique)",
13488 "maximal number of separation rounds per node (-1: unlimited)",
13492 "maximal number of separation rounds per node in the root node (-1: unlimited)",
13496 "maximal number of cuts separated per separation round",
13500 "maximal number of cuts separated per separation round in the root node",
13504 "should disaggregation of knapsack constraints be allowed in preprocessing?",
13508 "should presolving try to simplify knapsacks",
13512 "should negated clique information be used in solving process",
13516 "should pairwise constraint comparison be performed in presolving?",
13520 "should hash table be used for detecting redundant constraints in advance",
13524 "should dual presolving steps be performed?",
13528 "should GUB information be used for separation?",
13532 "should presolving try to detect constraints parallel to the objective function defining an upper bound and prevent these constraints from entering the LP?",
13536 "should presolving try to detect constraints parallel to the objective function defining a lower bound and prevent these constraints from entering the LP?",
13540 "should clique partition information be updated when old partition seems outdated?",
13544 "factor on the growth of global cliques to decide when to update a previous "
13545 "(negated) clique partition (used only if updatecliquepartitions is set to TRUE)",
13547#ifdef WITH_CARDINALITY_UPGRADE
13550 "if TRUE then try to update knapsack constraints to cardinality constraints",
13567 SCIP_Longint* weights,
13568 SCIP_Longint capacity,
13571 SCIP_Bool separate,
13581 SCIP_Bool modifiable,
13587 SCIP_Bool removable,
13589 SCIP_Bool stickingatnode
13600 if( conshdlr ==
NULL )
13615 SCIP_CALL(
SCIPcreateCons(
scip, cons, name, conshdlr, consdata, initial, separate, enforce, check,
propagate,
13616 local, modifiable, dynamic, removable, stickingatnode) );
13642 SCIP_Longint* weights,
13643 SCIP_Longint capacity
13659 SCIP_Longint weight
13696 return consdata->capacity;
13706 SCIP_Longint capacity
13721 SCIPerrorMessage(
"method can only be called during problem creation stage\n");
13728 consdata->capacity = capacity;
13753 return consdata->nvars;
13776 return consdata->vars;
13799 return consdata->weights;
13822 if( consdata->row !=
NULL )
13848 if( consdata->row !=
NULL )
13876 return consdata->row;
13883 SCIP_Bool* infeasible
13892 if( conshdlr ==
NULL )
13896 *infeasible =
FALSE;
13901 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 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
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,)
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 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_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
@ SCIP_CONFTYPE_PROPAGATION
#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
#define SCIP_PRESOLTIMING_MEDIUM
unsigned int SCIP_PRESOLTIMING
#define SCIP_PRESOLTIMING_FAST
#define SCIP_PRESOLTIMING_EXHAUSTIVE
@ SCIP_VARSTATUS_MULTAGGR
@ SCIP_VARSTATUS_AGGREGATED