111#define PROP_NAME "vbounds"
112#define PROP_DESC "propagates variable upper and lower bounds"
113#define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP
114#define PROP_PRIORITY 3000000
116#define PROP_DELAY FALSE
118#define PROP_PRESOL_PRIORITY -90000
119#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM | SCIP_PRESOLTIMING_EXHAUSTIVE
120#define PROP_PRESOL_MAXROUNDS -1
129#define EVENTHDLR_NAME "vbounds"
130#define EVENTHDLR_DESC "bound change event handler for for vbounds propagator"
139#define DEFAULT_USEBDWIDENING TRUE
140#define DEFAULT_USEIMPLICS FALSE
141#define DEFAULT_USECLIQUES FALSE
142#define DEFAULT_USEVBOUNDS TRUE
143#define DEFAULT_DOTOPOSORT TRUE
144#define DEFAULT_SORTCLIQUES FALSE
145#define DEFAULT_DETECTCYCLES FALSE
146#define DEFAULT_MINNEWCLIQUES 0.1
147#define DEFAULT_MAXCLIQUESMEDIUM 50.0
149#define DEFAULT_MAXCLIQUESEXHAUSTIVE 100.0
165#define getLbIndex(idx) (2*(idx))
166#define getUbIndex(idx) (2*(idx)+1)
167#define getVarIndex(idx) ((idx)/2)
168#define getBoundtype(idx) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)
169#define isIndexLowerbound(idx) ((idx) % 2 == 0)
170#define getBoundString(lower) ((lower) ? "lb" : "ub")
171#define getBoundtypeString(type) ((type) == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper")
172#define indexGetBoundString(idx) (getBoundString(isIndexLowerbound(idx)))
173#define getOtherBoundIndex(idx) ((idx) + 1 - 2 * ((idx) % 2))
194 int** vboundboundedidx;
205 int lastpresolncliques;
229 unsigned int boundtype:1;
244 inferinfo.val.asint =
i;
255 return inferinfo.val.asint;
275 return (
int) inferinfo.val.asbits.pos;
290 inferinfo.val.asbits.pos = (
unsigned int) pos;
291 inferinfo.val.asbits.boundtype = (
unsigned int) boundtype;
340 propdata->vars =
NULL;
341 propdata->varhashmap =
NULL;
342 propdata->topoorder =
NULL;
343 propdata->vboundboundedidx =
NULL;
344 propdata->vboundcoefs =
NULL;
345 propdata->vboundconstants =
NULL;
346 propdata->nvbounds =
NULL;
347 propdata->vboundsize =
NULL;
348 propdata->nbounds = 0;
349 propdata->initialized =
FALSE;
374 eventhdlr = propdata->eventhdlr;
377 vars = propdata->vars;
378 nbounds = propdata->nbounds;
381 for( v = 0; v < nbounds; ++v )
383 idx = propdata->topoorder[v];
384 assert(idx >= 0 && idx < nbounds);
395 propdata->topoorder[v] = -1;
429 eventhdlr = propdata->eventhdlr;
432 vars = propdata->vars;
433 nbounds = propdata->nbounds;
435 for( v = 0; v < nbounds; ++v )
437 idx = propdata->topoorder[v];
442 assert(idx >= 0 && idx < nbounds);
477 if( propdata->vboundsize[startidx] == 0 )
486 else if( propdata->nvbounds[startidx] >= propdata->vboundsize[startidx] )
490 assert(propdata->nvbounds[startidx] < propdata->vboundsize[startidx]);
497 nvbounds = propdata->nvbounds[startidx];
498 propdata->vboundboundedidx[startidx][nvbounds] = endidx;
499 propdata->vboundcoefs[startidx][nvbounds] = coef;
500 propdata->vboundconstants[startidx][nvbounds] = constant;
501 (propdata->nvbounds[startidx])++;
512 int idx1 = (int)(
size_t)elem1;
513 int idx2 = (int)(
size_t)elem2;
553 vars = propdata->vars;
556 cycleidx = dfsstack[stacksize - 1];
572 for( j = stacksize - 2; dfsstack[j] != startidx && j >= 0; --j ){};
575 for( ; j < stacksize - 1; ++j )
581 ntmpimpls = (propdata->useimplics ?
SCIPvarGetNImpls(currvar, currlower) : 0);
586 if( stacknextedge[j] <= 0 )
589#if defined(SCIP_DEBUG) || defined(SCIP_MORE_DEBUG)
609 if( currlower != nextlower )
612 constant = -constant + 1.0;
620#if defined(SCIP_DEBUG) || defined(SCIP_MORE_DEBUG)
621 if( stacknextedge[j] == 0 )
628 assert(stacknextedge[j] <= -2);
630 k = -stacknextedge[j] - 2;
640 for( v = 0; v < ncliquevars; ++v )
646#ifdef SCIP_MORE_DEBUG
647 for( v = 0; v < ncliquevars; ++v )
649 if( cliquevars[v] ==
vars[
getVarIndex(dfsstack[j+1])] && cliquevals[v] == !nextlower )
655 SCIPdebugMsg(
scip,
"%s(%s) -- (*%g + %g)[clique(<%s%s>,<%s%s>,...)] --> %s(%s)\n",
657 (currlower != nextlower ? -1.0 : 1.0),
658 (currlower != nextlower ? 1.0 : 0.0),
668 else if( stacknextedge[j] <= ntmpimpls )
679 k = stacknextedge[j] - 1;
694 newconstant = implbounds[k];
711 newconstant = implbounds[k];
715 coef = coef * newcoef;
716 constant = constant * newcoef + newconstant;
720 newcoef, newconstant,
726 assert(stacknextedge[j] > ntmpimpls);
728 k = stacknextedge[j] - ntmpimpls - 1;
729 assert(k < propdata->nvbounds[dfsstack[j]]);
730 assert(propdata->vboundboundedidx[dfsstack[j]][k] == dfsstack[j+1]);
734 propdata->vboundcoefs[dfsstack[j]][k], propdata->vboundconstants[dfsstack[j]][k],
737 coef = coef * propdata->vboundcoefs[dfsstack[j]][k];
738 constant = constant * propdata->vboundcoefs[dfsstack[j]][k] + propdata->vboundconstants[dfsstack[j]][k];
764 SCIPdebugMsg(
scip,
"-> infeasible aggregated variable bound relation 0 >= %g\n", constant);
769 SCIPdebugMsg(
scip,
"-> infeasible aggregated variable bound relation 0 <= %g\n", constant);
777 newbound = constant / (1.0 - coef);
831 int visitedflag = (propdata->detectcycles ?
ACTIVE :
VISITED);
834 assert(startnode < propdata->nbounds);
836 assert(visited[startnode] == 0);
844 vars = propdata->vars;
847 dfsstack[0] = startnode;
848 stacknextedge[0] = 0;
853 while( stacksize > 0 )
856 curridx = dfsstack[stacksize - 1];
859 assert((visited[curridx] != 0) == (stacknextedge[stacksize - 1] != 0));
860 visited[curridx] = visitedflag;
871 if( propdata->sortcliques && propdata->usecliques && stacknextedge[stacksize - 1] == 0 )
872 stacknextedge[stacksize - 1] = -1;
877 if( propdata->sortcliques && propdata->usecliques && stacknextedge[stacksize - 1] < 0 )
889 assert(stacknextedge[stacksize - 1] == -1 || -stacknextedge[stacksize - 1] - 1 <= ncliques);
892 for( j = -stacknextedge[stacksize - 1] - 1; j < ncliques; ++j )
902 for(
i = 0;
i < ncliquevars; ++
i )
904 if( cliquevars[
i] == startvar )
920 dfsstack[stacksize] = idx;
921 stacknextedge[stacksize - 1] = -j - 2;
924 visited[idx] ==
ACTIVE, infeasible) );
931 if( idx >= 0 && !visited[idx] )
952 dfsstack[stacksize] = idx;
953 stacknextedge[stacksize] = 0;
954 stacknextedge[stacksize - 1] = -j - 2;
956 assert(stacksize <= propdata->nbounds);
964 stacknextedge[stacksize - 1] = 0;
967 assert(stacknextedge[stacksize - 1] >= 0);
970 if( propdata->useimplics )
974 if( stacknextedge[stacksize - 1] < nimpls )
985 for(
i = stacknextedge[stacksize - 1];
i < nimpls; ++
i )
996 if( propdata->usecliques && !propdata->sortcliques && implids[
i] < 0 )
1010 dfsstack[stacksize] = idx;
1011 stacknextedge[stacksize - 1] =
i + 1;
1014 visited[idx] ==
ACTIVE, infeasible) );
1021 if( idx >= 0 && !visited[idx] )
1034 dfsstack[stacksize] = idx;
1035 stacknextedge[stacksize] = 0;
1036 stacknextedge[stacksize - 1] =
i + 1;
1038 assert(stacksize <= propdata->nbounds);
1045 stacknextedge[stacksize - 1] = nimpls;
1049 assert(stacknextedge[stacksize - 1] >= nimpls);
1052 if( propdata->usevbounds )
1058 nvbounds = propdata->nvbounds[curridx];
1059 vboundidx = propdata->vboundboundedidx[curridx];
1062 for(
i = stacknextedge[stacksize - 1] - nimpls;
i < nvbounds; ++
i )
1072 dfsstack[stacksize] = idx;
1073 stacknextedge[stacksize - 1] = nimpls +
i + 1;
1079 visited[idx] ==
ACTIVE, infeasible) );
1102 dfsstack[stacksize] = idx;
1103 stacknextedge[stacksize] = 0;
1104 stacknextedge[stacksize - 1] = nimpls +
i + 1;
1106 assert(stacksize <= propdata->nbounds);
1119 dfsnodes[(*ndfsnodes)] = curridx;
1120 assert(visited[curridx] == visitedflag);
1147 nbounds = propdata->nbounds;
1159 for(
i = 0;
i < nbounds && !(*infeasible); ++
i )
1163 SCIP_CALL(
dfs(
scip, propdata,
i, visited, dfsstack, stacknextedge, propdata->topoorder, &nsortednodes, infeasible) );
1166 assert((nsortednodes == nbounds) || (*infeasible));
1198 assert(!propdata->initialized);
1204 nbounds = 2 *
nvars;
1206 *infeasible =
FALSE;
1209 propdata->nbounds = nbounds;
1214 propdata->initialized =
TRUE;
1227 for( v = 0; v <
nvars; ++v )
1245 for( v = 0; v < nbounds; ++v )
1247 propdata->topoorder[v] = v;
1248 propdata->vboundboundedidx[v] =
NULL;
1249 propdata->vboundcoefs[v] =
NULL;
1250 propdata->vboundconstants[v] =
NULL;
1251 propdata->nvbounds[v] = 0;
1252 propdata->vboundsize[v] = 0;
1256 for( v = 0; v < nbounds; ++v )
1286 for( n = 0; n < nvbvars; ++n )
1294 constant = constants[n];
1319 SCIPdebugMsg(
scip,
"varbound <%s> %s %g * <%s> + %g not added to propagator data due to reverse implication\n",
1327 SCIPdebugMsg(
scip,
"varbound <%s> %s %g * <%s> + %g added to propagator data\n",
1335 if( propdata->dotoposort )
1421 relaxedbd = (inferlb - constant) / coef;
1463 if( canwide && propdata->usebdwidening )
1468 SCIPdebugMsg(
scip,
"try to create conflict using bound widening order: inference variable, variable bound variable\n");
1478 relaxedub = inferlb - 1.0;
1490 relaxedub = relaxedub + 1.0;
1536 relaxedbd = (inferub - constant) / coef;
1577 if( canwide && propdata->usebdwidening )
1582 SCIPdebugMsg(
scip,
"try to create conflict using bound widening order: inference variable, variable bound variable\n");
1592 relaxedlb = inferub + 1.0;
1604 relaxedlb = relaxedlb - 1.0;
1694 SCIPdebugMsg(
scip,
"tightening%s lower bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1709 else if( tightened )
1711 SCIPdebugMsg(
scip,
"tightened%s lower bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1778 SCIPdebugMsg(
scip,
"tightening%s upper bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1793 else if( tightened )
1795 SCIPdebugMsg(
scip,
"tightened%s upper bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1818 int* queuelist =
NULL;
1843 if( !propdata->initialized )
1855 assert(propdata->nbounds == 0 || propdata->propqueue !=
NULL);
1857 vars = propdata->vars;
1858 nbounds = propdata->nbounds;
1869 for( v = nbounds - 1; v >= 0; --v )
1871 idx = propdata->topoorder[v];
1872 if( idx != -1 && !propdata->inqueue[v] )
1880 propdata->inqueue[v] =
TRUE;
1906 assert(propdata->inqueue[topopos]);
1907 startpos = propdata->topoorder[topopos];
1909 queuelist[nqueuelist++] = topopos;
1910 assert( nqueuelist <= nbounds );
1932 if( lower != (startbound > 0.5) )
1936 if( propdata->useimplics )
1958 for( n = 0; n < nimplvars; ++n )
1963 if( implids[n] < 0 )
1975 starttype, force, 0.0, 0.0,
FALSE, &nchgbds,
result) );
1980 starttype, force, 0.0, 0.0,
FALSE, &nchgbds,
result) );
1992 if( propdata->usecliques )
2009 for( j = 0; j < ncliques; ++j )
2020 for( n = 0; n < ncliquevars; ++n )
2022 if( cliquevars[n] == startvar )
2058 for( n = 0; n < propdata->nvbounds[startpos]; ++n )
2060 boundedvar =
vars[
getVarIndex(propdata->vboundboundedidx[startpos][n])];
2061 coef = propdata->vboundcoefs[startpos][n];
2062 constant = propdata->vboundconstants[startpos][n];
2065 newbound = startbound * coef + constant;
2088 for( v = 0; v < nqueuelist; ++v )
2090 assert( 0 <= queuelist[v] && queuelist[v] < nbounds );
2091 propdata->inqueue[queuelist[v]] =
FALSE;
2097 for( v = 0; v < nbounds; ++v)
2099 if( propdata->inqueue[v] )
2158 propdata->lastpresolncliques = 0;
2174 if( propdata->initialized )
2180 for( v = 0; v < propdata->nbounds; ++v )
2183 if( propdata->vboundsize[v] > 0 )
2242 int* stacknextclique,
2244 int* stacknextcliquevar,
2248 int* cliquefirstentry,
2251 int* cliquecurrentexit,
2264 int label = *startindex;
2273 assert(nodeindex[startnode] == 0);
2275 assert(nodelowlink[startnode] == 0);
2280 *infeasible =
FALSE;
2285 dfsstack[0] = startnode;
2286 stacknextclique[0] = 0;
2287 stacknextcliquevar[0] = 0;
2288 predstackidx[0] = -1;
2298 while( stacksize > 0 )
2308 curridx = dfsstack[currstackidx];
2309 assert(nodelowlink[curridx] <= nodeindex[curridx]);
2315 if( nodeindex[curridx] == 0 )
2317 assert(!nodeonstack[curridx]);
2318 assert(stacknextclique[currstackidx] == 0);
2319 assert(stacknextcliquevar[currstackidx] == 0);
2320 nodeonstack[curridx] = 1;
2321 nodeindex[curridx] = label;
2322 nodelowlink[curridx] = label;
2332 for( j = 0; j < ncliques; ++j )
2343 SCIPdebugMsg(
scip,
"clique %d [%d vars, stacksize: %d]...\n", clqidx, ncliquevars, stacksize);
2344 for(
int v = 0; v < ncliquevars; ++v )
2356 assert(stacknextclique[currstackidx] > 0 || stacknextcliquevar[currstackidx] > 0);
2357 assert(nodeindex[curridx] < label);
2359 assert(stacknextclique[currstackidx] >= 0);
2366 for( j = stacknextclique[currstackidx]; j < ncliques; ++j )
2380 if( stacknextcliquevar[currstackidx] == 0 )
2383 SCIPdebugMsg(
scip,
"clique %d [%d vars, stacksize: %d]...\n", clqidx, ncliquevars, stacksize);
2384 for(
int v = 0; v < ncliquevars; ++v )
2391 if( cliquefirstentry[clqidx] == 0 )
2393 cliquefirstentry[clqidx] = curridx + 1;
2397 int cliquefirstentryidx = (cliquefirstentry[clqidx] > 0 ? cliquefirstentry[clqidx] : -cliquefirstentry[clqidx]) - 1;
2398 int infeasnode = -1;
2399 assert(cliquefirstentryidx != curridx);
2406 if( nodeonstack[cliquefirstentryidx] && !nodeinfeasible[cliquefirstentryidx] )
2410 infeasnode = cliquefirstentryidx;
2415 else if( nodeindex[cliquefirstentryidx] >= *startindex && !nodeinfeasible[startnode] )
2419 infeasnode = startnode;
2423 if( infeasnode >= 0 )
2431 infeasnodes[*ninfeasnodes] = infeasnode;
2432 nodeinfeasible[infeasnode] =
TRUE;
2438 if( cliquecurrentexit[clqidx] > 0
2440 && nodeonstack[cliquecurrentexit[clqidx] - 1]
2441 && nodeindex[cliquecurrentexit[clqidx] - 1] < nodelowlink[curridx] )
2443 nodelowlink[curridx] = nodeindex[cliquecurrentexit[clqidx] - 1];
2449 else if( cliquefirstentry[clqidx] > 0 )
2457 if( nodeindex[idx] == 0 )
2460 else if( nodeonstack[idx] && nodeindex[idx] < nodelowlink[curridx] )
2461 nodelowlink[curridx] = nodeindex[idx];
2464 cliquefirstentry[clqidx] = -cliquefirstentry[clqidx];
2469 SCIPdebugMsg(
scip,
"skip clique %d: visited more than twice already!\n", clqidx);
2472 stacknextcliquevar[currstackidx] = ncliquevars;
2477 for(
i = stacknextcliquevar[currstackidx];
i < ncliquevars; ++
i )
2479 if( cliquevars[
i] == startvar )
2492 if( nodeindex[idx] == 0 )
2494 assert(!nodeonstack[idx]);
2495 stacknextcliquevar[currstackidx] =
i + 1;
2499 else if( nodeonstack[idx] && nodeindex[idx] < nodelowlink[curridx] )
2501 nodelowlink[curridx] = nodeindex[idx];
2506 if( stacknextcliquevar[currstackidx] < ncliquevars )
2507 stacknextclique[currstackidx] = j;
2510 stacknextclique[currstackidx] = j + 1;
2511 stacknextcliquevar[currstackidx] = 0;
2518 stacknextclique[currstackidx] = j + 1;
2519 stacknextcliquevar[currstackidx] = 0;
2522 assert(found || j == ncliques);
2523 assert(found || stacknextclique[currstackidx] == ncliques);
2529 int infeasnode = -1;
2532 assert(!nodeonstack[idx]);
2539 if( nodeonstack[otheridx] && !nodeinfeasible[otheridx] )
2543 infeasnode = otheridx;
2548 else if( nodeindex[otheridx] >= *startindex && !nodeinfeasible[startnode] )
2552 infeasnode = startnode;
2555 if( infeasnode >= 0 )
2562 infeasnodes[*ninfeasnodes] = infeasnode;
2563 nodeinfeasible[infeasnode] =
TRUE;
2571 dfsstack[stacksize] = idx;
2572 stacknextclique[stacksize] = 0;
2573 stacknextcliquevar[stacksize] = 0;
2574 cliquecurrentexit[clqidx] = idx + 1;
2575 predstackidx[stacksize] = currstackidx;
2576 currstackidx = stacksize;
2586 assert(stacknextclique[currstackidx] == ncliques);
2591 if( nodelowlink[curridx] == nodeindex[curridx] )
2594 if( dfsstack[stacksize-1] != curridx )
2596 int sccvarspos = sccstarts[*nsccs];
2603 idx = dfsstack[stacksize];
2604 nodeonstack[idx] = 0;
2605 sccvars[sccvarspos] = idx;
2612 while( idx != curridx );
2615 sccstarts[*nsccs] = sccvarspos;
2624 idx = dfsstack[stacksize];
2625 nodeonstack[idx] = 0;
2626 assert(nodeindex[idx] > 0);
2630 if( topoorder !=
NULL && (stacksize > 0 || label > *startindex + 1) )
2633 topoorder[*nordered] = curridx;
2640 idx = dfsstack[predstackidx[currstackidx]];
2641 nodelowlink[idx] =
MIN(nodelowlink[idx], nodelowlink[curridx]);
2642 currstackidx = predstackidx[currstackidx];
2646 *startindex = label;
2677 if( !(*infeasible) && ninfeasnodes > 0 )
2679 for(
i = 0;
i < ninfeasnodes; ++
i )
2685 assert(nodeinfeasible[infeasnodes[
i]]);
2686 nodeinfeasible[infeasnodes[
i]] =
FALSE;
2705 assert((*infeasible) ||
i == ninfeasnodes);
2708 for( ;
i < ninfeasnodes; ++
i )
2710 assert(nodeinfeasible[infeasnodes[
i]]);
2711 nodeinfeasible[infeasnodes[
i]] =
FALSE;
2714 if( !(*infeasible) && nsccs > 0 )
2717 for(
i = 0;
i < nsccs; ++
i )
2725 assert(sccstarts[
i] < sccstarts[
i+1] - 1);
2731 for( v = sccstarts[
i] + 1; v < sccstarts[
i+1]; ++v )
2740 infeasible, &redundant, &aggregated) );
2742 SCIPdebugMsg(
scip,
"aggregate <%s> + %g <%s> = %g: inf=%u, red=%u, aggr=%u\n",
2745 *infeasible, redundant, aggregated);
2779 int* stacknextclique;
2780 int* stacknextcliquevar;
2784 int* cliquefirstentry;
2785 int* cliquecurrentexit;
2864 for(
i = 0;
i < nbounds && !infeasible; ++
i )
2866 if( nodeindex[
i] == 0 )
2869 dfsstack, predstackidx, stacknextclique, stacknextcliquevar, topoorder, &nordered,
2870 cliquefirstentry, cliquecurrentexit, sccvars, sccstarts, &nsccs,
2871 infeasnodes, &ninfeasnodes, &infeasible) );
2874 assert(nordered <= nbounds);
2877 if( ninfeasnodes > 0 || nsccs > 0 )
2880 sccvars, sccstarts, nsccs, &infeasible, nfixedvars, naggrvars,
result) );
2884 if( !infeasible && nordered > 0 )
2917 for(
i = nordered - 1;
i >= 0 && !infeasible; --
i )
2921 assert(topoorder[
i] < nbounds);
2930 if( nodeindex[startpos] == 0 )
2932 SCIP_CALL(
tarjan(
scip, startpos, &startindex, nodeonstack, nodeindex, nodelowlink, nodeinfeasible,
2933 dfsstack, predstackidx, stacknextclique, stacknextcliquevar,
NULL,
NULL,
2934 cliquefirstentry, cliquecurrentexit, sccvars, sccstarts, &nsccs,
2935 infeasnodes, &ninfeasnodes, &infeasible) );
2941 if( ninfeasnodes > 0 || nsccs > 0 )
2944 sccvars, sccstarts, nsccs, &infeasible, nfixedvars, naggrvars,
result) );
2954 for(
i = 0;
i < nbounds; ++
i )
3013 assert(pos < propdata->nbounds);
3015 vars = propdata->vars;
3019 assert(startvar != infervar);
3026 int* vboundboundedidx;
3033 nvbounds = propdata->nvbounds[pos];
3034 vboundboundedidx = propdata->vboundboundedidx[pos];
3039 for(
b = 0;
b < nvbounds; ++
b )
3041 if( vboundboundedidx[
b] == inferidx )
3046 coef = propdata->vboundcoefs[pos][
b];
3047 constant = propdata->vboundconstants[pos][
b];
3089 idx = (int) (
size_t) eventdata;
3109 if( !propdata->inqueue[idx] )
3112 propdata->inqueue[idx] =
TRUE;
3138 propExecVbounds, propdata) );
3155 "propagating/" PROP_NAME "/usebdwidening",
"should bound widening be used to initialize conflict analysis?",
3158 "propagating/" PROP_NAME "/useimplics",
"should implications be propagated?",
3161 "propagating/" PROP_NAME "/usecliques",
"should cliques be propagated?",
3164 "propagating/" PROP_NAME "/usevbounds",
"should vbounds be propagated?",
3167 "propagating/" PROP_NAME "/dotoposort",
"should the bounds be topologically sorted in advance?",
3170 "propagating/" PROP_NAME "/sortcliques",
"should cliques be regarded for the topological sort?",
3173 "propagating/" PROP_NAME "/detectcycles",
"should cycles in the variable bound graph be identified?",
3176 "propagating/" PROP_NAME "/minnewcliques",
"minimum percentage of new cliques to trigger another clique table analysis",
3179 "maximum number of cliques per variable to run clique table analysis in medium presolving",
3182 "maximum number of cliques per variable to run clique table analysis in exhaustive presolving",
#define DEFAULT_USEBDWIDENING
struct InferInfo INFERINFO
SCIP_STAGE SCIPgetStage(SCIP *scip)
const char * SCIPgetProbName(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(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)
#define SCIPdebugMsgPrint
SCIP_Bool SCIPisPropagatedVbounds(SCIP *scip)
SCIP_RETCODE SCIPexecPropVbounds(SCIP *scip, SCIP_Bool force, SCIP_RESULT *result)
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 SCIPpqueueFind(SCIP_PQUEUE *pqueue, void *elem)
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)),)
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
int SCIPpqueueNElems(SCIP_PQUEUE *pqueue)
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
SCIP_RETCODE SCIPincludePropVbounds(SCIP *scip)
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb)
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
SCIP_RETCODE SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
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)
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
#define SCIPfreeCleanBufferArray(scip, ptr)
#define SCIPallocCleanBufferArray(scip, ptr, num)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
#define SCIPallocClearBufferArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeMemoryArray(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_PROP * SCIPfindProp(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop,)
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop,)
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop,)
const char * SCIPpropGetName(SCIP_PROP *prop)
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop,)
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop,)
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Real SCIPgetHugeValue(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
SCIP_NODE * SCIPgetRootNode(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_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_RETCODE SCIPinferVarUbProp(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_PROP *inferprop, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Bool SCIPvarHasImplic(SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype)
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
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)
int SCIPgetNCliquesCreated(SCIP *scip)
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
int * SCIPvarGetImplIds(SCIP_VAR *var, SCIP_Bool varfixing)
int SCIPvarGetNVubs(SCIP_VAR *var)
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_Real SCIPvarGetLbLocal(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)
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_RETCODE SCIPinferVarLbProp(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_PROP *inferprop, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
assert(minobj< SCIPgetCutoffbound(scip))
#define isIndexLowerbound(idx)
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
int SCIPcliqueGetIndex(SCIP_CLIQUE *clique)
SCIP_Bool SCIPcliqueIsEquation(SCIP_CLIQUE *clique)
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
#define PROP_PRESOL_MAXROUNDS
#define PROP_PRESOLTIMING
#define PROP_PRESOL_PRIORITY
#define DEFAULT_USEIMPLICS
#define getOtherBoundIndex(idx)
static SCIP_RETCODE propagateVbounds(SCIP *scip, SCIP_PROP *prop, SCIP_Bool force, SCIP_RESULT *result)
#define DEFAULT_MINNEWCLIQUES
static SCIP_RETCODE relaxVbdvar(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd)
static SCIP_RETCODE topologicalSort(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible)
#define isIndexLowerbound(idx)
#define getBoundString(lower)
static SCIP_RETCODE extractCycle(SCIP *scip, SCIP_PROPDATA *propdata, int *dfsstack, int *stacknextedge, int stacksize, SCIP_Bool samebound, SCIP_Bool *infeasible)
static SCIP_RETCODE dfs(SCIP *scip, SCIP_PROPDATA *propdata, int startnode, int *visited, int *dfsstack, int *stacknextedge, int *dfsnodes, int *ndfsnodes, SCIP_Bool *infeasible)
static SCIP_Real computeRelaxedLowerbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferlb, SCIP_Real coef, SCIP_Real constant)
#define DEFAULT_MAXCLIQUESMEDIUM
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_PROPDATA *propdata)
#define DEFAULT_USECLIQUES
static int varGetLbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
static SCIP_RETCODE analyzeConflictUpperbound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *infervar, SCIP_Real inferub, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide)
static SCIP_RETCODE addVbound(SCIP *scip, SCIP_PROPDATA *propdata, int startidx, int endidx, SCIP_Real coef, SCIP_Real constant)
#define indexGetBoundString(idx)
static int inferInfoGetPos(INFERINFO inferinfo)
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_PROPDATA *propdata)
static INFERINFO intToInferInfo(int i)
static SCIP_RETCODE applyFixingsAndAggregations(SCIP *scip, SCIP_VAR **vars, int *infeasnodes, int ninfeasnodes, SCIP_Shortbool *nodeinfeasible, int *sccvars, int *sccstarts, int nsccs, SCIP_Bool *infeasible, int *nfixedvars, int *naggrvars, SCIP_RESULT *result)
#define getBoundtypeString(type)
static SCIP_RETCODE tarjan(SCIP *scip, int startnode, int *startindex, SCIP_Shortbool *nodeonstack, int *nodeindex, int *nodelowlink, SCIP_Shortbool *nodeinfeasible, int *dfsstack, int *predstackidx, int *stacknextclique, int *stacknextcliquevar, int *topoorder, int *nordered, int *cliquefirstentry, int *cliquecurrentexit, int *sccvars, int *sccstarts, int *nsccs, int *infeasnodes, int *ninfeasnodes, SCIP_Bool *infeasible)
static SCIP_BOUNDTYPE inferInfoGetBoundtype(INFERINFO inferinfo)
static void resetPropdata(SCIP_PROPDATA *propdata)
static int varGetUbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
static SCIP_RETCODE analyzeConflictLowerbound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *infervar, SCIP_Real inferlb, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide)
#define getBoundtype(idx)
static SCIP_RETCODE tightenVarUb(SCIP *scip, SCIP_PROP *prop, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_Real newub, SCIP_Bool global, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Bool force, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide, int *nchgbds, SCIP_RESULT *result)
#define DEFAULT_MAXCLIQUESEXHAUSTIVE
#define DEFAULT_USEVBOUNDS
#define DEFAULT_DETECTCYCLES
static int inferInfoToInt(INFERINFO inferinfo)
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
static SCIP_RETCODE tightenVarLb(SCIP *scip, SCIP_PROP *prop, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_Real newlb, SCIP_Bool global, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Bool force, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide, int *nchgbds, SCIP_RESULT *result)
#define DEFAULT_DOTOPOSORT
static SCIP_RETCODE initData(SCIP *scip, SCIP_PROP *prop, SCIP_Bool *infeasible)
static INFERINFO getInferInfo(int pos, SCIP_BOUNDTYPE boundtype)
static SCIP_Real computeRelaxedUpperbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferub, SCIP_Real coef, SCIP_Real constant)
#define DEFAULT_SORTCLIQUES
variable upper and lower bound propagator
public methods for managing events
public methods for implications, variable bounds, and cliques
public methods for message output
public data structures and miscellaneous methods
public methods for propagators
public methods for problem variables
public methods for conflict handler plugins and conflict analysis
public methods for event handler plugins and event handlers
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for propagator plugins
public methods for the branch-and-bound tree
public methods for SCIP variables
@ SCIP_CONFTYPE_PROPAGATION
struct SCIP_Eventhdlr SCIP_EVENTHDLR
#define SCIP_EVENTTYPE_GUBCHANGED
struct SCIP_EventData SCIP_EVENTDATA
#define SCIP_EVENTTYPE_UBTIGHTENED
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_EVENTTYPE_FORMAT
#define SCIP_EVENTTYPE_GLBCHANGED
#define SCIP_EVENTTYPE_LBTIGHTENED
struct SCIP_Clique SCIP_CLIQUE
enum SCIP_BoundType SCIP_BOUNDTYPE
struct SCIP_HashMap SCIP_HASHMAP
#define SCIP_DECL_SORTPTRCOMP(x)
struct SCIP_PQueue SCIP_PQUEUE
#define SCIP_DECL_PROPCOPY(x)
#define SCIP_DECL_PROPFREE(x)
#define SCIP_DECL_PROPEXITSOL(x)
struct SCIP_Prop SCIP_PROP
#define SCIP_DECL_PROPPRESOL(x)
#define SCIP_DECL_PROPINITPRE(x)
#define SCIP_DECL_PROPRESPROP(x)
struct SCIP_PropData SCIP_PROPDATA
#define SCIP_DECL_PROPEXEC(x)
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
#define SCIP_PRESOLTIMING_MEDIUM
struct SCIP_BdChgIdx SCIP_BDCHGIDX