37 #define PROP_NAME "genvbounds" 38 #define PROP_DESC "generalized variable bounds propagator" 39 #define PROP_TIMING SCIP_PROPTIMING_ALWAYS 40 #define PROP_PRIORITY 3000000 42 #define PROP_DELAY FALSE 44 #define PROP_PRESOL_PRIORITY -2000000 46 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST 47 #define PROP_PRESOL_MAXROUNDS -1 49 #define DEFAULT_GLOBAL_PROPAGATION TRUE 50 #define DEFAULT_PROPAGATE_IN_ROOT_NODE TRUE 51 #define DEFAULT_SORT TRUE 53 #define DEFAULT_PROPASCONSS FALSE 55 #define EVENTHDLR_NAME "genvbounds" 56 #define EVENTHDLR_DESC "event handler for generalized variable bounds propagator" 110 int* componentsstart;
113 int componentsstartsize;
115 int* startcomponents;
116 int startindicessize;
119 int* gstartcomponents;
120 int gstartindicessize;
122 int genvboundstoresize;
150 SCIPdebugMsg(scip,
"cutoff = %.9g (%.9g + %.9g * %.9g)\n",
174 assert(scip !=
NULL);
175 assert(propdata !=
NULL);
194 assert(genvbound !=
NULL);
204 for( i = 0; i < genvbound->
ncoefs; i++ )
243 assert(scip !=
NULL);
244 assert(vars !=
NULL);
245 assert(coefs !=
NULL);
250 for( i = 0; i < nvars; i++ )
265 minval += coefs[i] *
bound;
284 assert(scip !=
NULL);
285 assert(vars !=
NULL);
286 assert(coefs !=
NULL);
291 for( i = 0; i < nvars; i++ )
325 minval += coefs[i] *
bound;
341 assert(scip !=
NULL);
342 assert(genvbound !=
NULL);
360 #ifdef SCIP_DEBUG_SOLUTION 373 assert(scip !=
NULL);
374 assert(genvbound !=
NULL);
376 if( !SCIPdebugIsMainscip(scip) )
380 for( i = 0; i < genvbound->
ncoefs; i++ )
384 activity += genvbound->
coefs[i] * solval;
386 printf(
"***** debug: ignoring variable with %s value in debug solution\n",
391 SCIP_CALL( SCIPdebugGetSol(scip, &debugsol) );
420 assert(scip !=
NULL);
421 assert(propdata !=
NULL);
423 assert(propdata->startcomponents ==
NULL);
424 assert(propdata->startindices ==
NULL);
425 assert(propdata->startmap ==
NULL);
426 assert(propdata->nindices == -1);
428 assert(propdata->gstartindices ==
NULL);
429 assert(propdata->gstartcomponents ==
NULL);
430 assert(propdata->ngindices == -1);
432 assert(propdata->ngenvbounds >= 1);
433 assert(propdata->ncomponents >= 1);
442 propdata->startindicessize = propdata->ncomponents;
443 propdata->gstartindicessize = propdata->ncomponents;
448 propdata->nindices = 0;
449 propdata->ngindices = 0;
461 assert(scip !=
NULL);
462 assert(propdata !=
NULL);
466 if( propdata->startcomponents !=
NULL )
468 assert(propdata->startindices !=
NULL);
469 assert(propdata->startmap !=
NULL);
470 assert(propdata->nindices >= 0);
474 propdata->startindicessize = 0;
476 propdata->nindices = -1;
478 assert(propdata->gstartindices !=
NULL);
479 assert(propdata->gstartcomponents !=
NULL);
480 assert(propdata->ngindices >= 0);
484 propdata->gstartindicessize = 0;
485 propdata->ngindices = -1;
488 assert(propdata->startcomponents ==
NULL);
489 assert(propdata->startindices ==
NULL);
490 assert(propdata->startmap ==
NULL);
491 assert(propdata->nindices == -1);
493 assert(propdata->gstartindices ==
NULL);
494 assert(propdata->gstartcomponents ==
NULL);
495 assert(propdata->ngindices == -1);
508 assert(scip !=
NULL);
509 assert(propdata !=
NULL);
511 assert(propdata->gstartindices !=
NULL);
512 assert(propdata->gstartcomponents !=
NULL);
513 assert(propdata->ngindices == 0);
517 for( i = 0; i < propdata->ncomponents; i++ )
521 for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ )
523 assert(j < propdata->ngenvbounds);
525 if( !
SCIPisZero(scip, propdata->genvboundstore[j]->cutoffcoef) )
527 assert(
SCIPisNegative(scip, propdata->genvboundstore[j]->cutoffcoef));
529 propdata->gstartcomponents[propdata->ngindices] = i;
530 propdata->gstartindices[propdata->ngindices] = j;
533 propdata->ngindices++;
540 if( propdata->gstartindicessize != propdata->ngindices )
543 propdata->ngindices) );
545 propdata->ngindices) );
546 propdata->gstartindicessize = propdata->ngindices;
560 assert(scip !=
NULL);
561 assert(propdata !=
NULL);
562 assert(propdata->startcomponents !=
NULL);
563 assert(propdata->startindices !=
NULL);
564 assert(propdata->startmap !=
NULL);
565 assert(propdata->nindices >= 0);
568 propdata->nindices = 0;
580 assert(scip !=
NULL);
581 assert(propdata !=
NULL);
585 if( propdata->componentsstart !=
NULL )
587 assert(propdata->ncomponents > 0);
590 propdata->componentsstartsize = 0;
591 propdata->ncomponents = -1;
594 assert(propdata->componentsstart ==
NULL);
595 assert(propdata->ncomponents == -1);
609 assert(scip !=
NULL);
610 assert(genvbound !=
NULL);
613 assert(genvbound->
var !=
NULL);
616 for( i = 0; i < genvbound->
ncoefs; ++i )
649 assert(scip !=
NULL);
650 assert(genvbound !=
NULL);
651 assert(boundval !=
NULL);
652 assert(success !=
NULL);
657 lhsvar = genvbound->
var;
658 assert(lhsvar !=
NULL);
661 vars = genvbound->
vars;
662 nvars = genvbound->
ncoefs;
663 assert(vars !=
NULL);
684 SCIPdebugMsg(scip,
"resolving genvbound propagation: lhs=%s<%s> >= boundval=%.15g\n",
688 tmpboundval = *boundval;
692 SCIPdebugMsg(scip,
"subtracting constant terms gives boundval=%.15g\n", tmpboundval);
697 SCIPdebugMsg(scip,
"minactivity of right-hand side is minactivity=%.15g\n", minactivity);
703 if(
SCIPisLT(scip, minactivity, tmpboundval) )
705 SCIPdebugMsg(scip,
"minactivity is too small to explain propagation; was genvbound replaced?\n");
710 assert(
SCIPisGE(scip, minactivity, tmpboundval));
712 slack =
MAX(minactivity - tmpboundval, 0.0);
717 for( i = 0; i < nvars; i++ )
719 assert(vars[i] !=
NULL);
724 if( genvbound->
coefs[i] > 0.0 )
736 SCIPdebugMsg(scip,
"lower bound of variable <%s> (genvbound->vars[%d]) in conflict set / at index is %.15g / %.15g\n",
742 if(
SCIPisLE(scip, lbatindex, conflictlb) )
744 SCIPdebugMsg(scip,
"skipping lower bound of variable <%s> (genvbound->vars[%d]) already enforced in conflict set\n",
752 relaxedlb = lbatindex - (slack / genvbound->
coefs[i]);
753 assert(relaxedlb <= lbatindex);
762 assert(
SCIPisGE(scip, relaxedlb, conflictlb));
763 assert(
SCIPisLE(scip, relaxedlb, lbatindex));
766 slack -= genvbound->
coefs[i] * (lbatindex - relaxedlb);
767 slack =
MAX(slack, 0.0);
769 SCIPdebugMsg(scip,
"added lower bound of variable <%s> (genvbound->vars[%d]); new slack=%.15g\n",
786 SCIPdebugMsg(scip,
"upper bound of variable <%s> (genvbound->vars[%d]) in conflict set / at index is %.15g / %.15g\n",
792 if(
SCIPisGE(scip, ubatindex, conflictub) )
794 SCIPdebugMsg(scip,
"skipping upper bound of variable <%s> (genvbound->vars[%d]) already enforced in conflict set\n",
802 relaxedub = ubatindex - (slack / genvbound->
coefs[i]);
803 assert(relaxedub >= ubatindex);
812 assert(
SCIPisLE(scip, relaxedub, conflictub));
813 assert(
SCIPisGE(scip, relaxedub, ubatindex));
816 slack -= genvbound->
coefs[i] * (ubatindex - relaxedub);
817 slack =
MAX(slack, 0.0);
819 SCIPdebugMsg(scip,
"added upper bound of variable <%s> (genvbound->vars[%d]); new slack=%.15g\n",
827 tmpboundval += slack;
836 if(
SCIPisLT(scip, tmpboundval, *boundval) )
838 SCIPdebugMsg(scip,
"boundval was reduced from %.15g to %.15g; propagation not resolved\n", *boundval, tmpboundval);
843 *boundval = tmpboundval;
858 assert(scip !=
NULL);
859 assert(genvbound !=
NULL);
897 bound -= infeasthreshold;
903 SCIPdebugMsg(scip,
"strange: could not create initial reason to start conflict analysis\n");
910 SCIPdebugMsg(scip,
"skipping upper bound of left-hand side variable <%s> already enforced in conflict set\n",
949 bound = -bound + infeasthreshold;
955 SCIPdebugMsg(scip,
"strange: could not create initial reason to start conflict analysis\n");
962 SCIPdebugMsg(scip,
"skipping lower bound of left-hand side variable <%s> already enforced in conflict set\n",
996 assert(scip !=
NULL);
997 assert(genvbound !=
NULL);
998 assert(genvbound->
var !=
NULL);
1000 assert(result !=
NULL);
1021 SCIPdebugMsg(scip,
" %s genvbound propagation for <%s>\n", global ?
1024 printGenVBound(scip, genvbound);
1025 SCIPdebugMsg(scip,
" [%.15g,%.15g] -> [%.15g,%.15g]\n", lb, ub, new_lb, new_ub);
1030 if( global || genvbound->
ncoefs <= 0 )
1053 SCIPdebugMsg(scip,
" -> lower bound tightening on variable <%s> led to infeasibility\n",
1066 SCIPdebugMsg(scip,
" -> upper bound tightening on variable <%s> led to infeasibility\n",
1080 else if( tightened )
1083 if( nchgbds !=
NULL )
1094 void printEventData(
1101 SCIPdebugMessage(
"event data: %s bound of <%s> tightened ==> start propagating at ",
1105 assert(eventdata->nstarts > 0);
1107 for( i = 0; i < eventdata->nstarts; i++ )
1109 SCIPdebugPrintf(
"(component %d, index %d) ", eventdata->startcomponents[i], eventdata->startindices[i]);
1122 assert(scip !=
NULL);
1123 assert(eventdata !=
NULL);
1124 assert(*eventdata !=
NULL);
1129 (*eventdata)->startindicessize = 0;
1130 (*eventdata)->nstarts = -1;
1131 (*eventdata)->var =
NULL;
1132 (*eventdata)->prop =
NULL;
1148 assert(scip !=
NULL);
1149 assert(propdata !=
NULL);
1151 if( propdata->lbevents !=
NULL )
1153 assert(propdata->ubevents !=
NULL);
1154 assert(propdata->lbeventsmap !=
NULL);
1155 assert(propdata->ubeventsmap !=
NULL);
1160 for( i = propdata->nlbevents - 1; i >= 0; i-- )
1165 for( i = propdata->nubevents - 1; i >= 0; i-- )
1172 propdata->nlbevents = -1;
1173 propdata->nubevents = -1;
1176 assert(propdata->lbevents ==
NULL);
1177 assert(propdata->ubevents ==
NULL);
1178 assert(propdata->lbeventsmap ==
NULL);
1179 assert(propdata->ubeventsmap ==
NULL);
1180 assert(propdata->nlbevents == -1);
1181 assert(propdata->nubevents == -1);
1197 assert(scip !=
NULL);
1198 assert(propdata !=
NULL);
1199 assert(propdata->eventhdlr !=
NULL);
1201 if( propdata->lbevents !=
NULL )
1203 assert(propdata->ubevents !=
NULL);
1204 assert(propdata->nlbevents >= 0);
1205 assert(propdata->nubevents >= 0);
1207 for( i = propdata->nlbevents - 1; i >= 0; i-- )
1211 propdata->lbevents[i], -1) );
1214 for( i = propdata->nubevents - 1; i >= 0; i-- )
1218 propdata->ubevents[i], -1) );
1225 assert(propdata->lbevents ==
NULL);
1226 assert(propdata->ubevents ==
NULL);
1227 assert(propdata->nlbevents == -1);
1228 assert(propdata->nubevents == -1);
1247 assert(scip !=
NULL);
1248 assert(propdata !=
NULL);
1249 assert(var !=
NULL);
1261 (*eventdata)->startindicessize = propdata->ncomponents;
1262 (*eventdata)->nstarts = 0;
1263 (*eventdata)->var =
var;
1264 (*eventdata)->prop = propdata->prop;
1269 propdata->lbevents[propdata->nlbevents] = *eventdata;
1270 propdata->nlbevents++;
1274 propdata->ubevents[propdata->nubevents] = *eventdata;
1275 propdata->nubevents++;
1300 assert(scip !=
NULL);
1301 assert(propdata !=
NULL);
1302 assert(var !=
NULL);
1303 assert(startindex >= 0);
1304 assert(startcomponent >= 0);
1308 assert(eventdata !=
NULL);
1310 if( eventdata->nstarts > 0 && eventdata->startcomponents[eventdata->nstarts - 1] == startcomponent )
1316 assert(eventdata->startindices[eventdata->nstarts - 1] < startindex);
1321 eventdata->startcomponents[eventdata->nstarts] = startcomponent;
1322 eventdata->startindices[eventdata->nstarts] = startindex;
1325 eventdata->nstarts++;
1340 assert(scip !=
NULL);
1341 assert(propdata !=
NULL);
1342 assert(propdata->eventhdlr !=
NULL);
1343 assert(propdata->lbevents ==
NULL);
1344 assert(propdata->ubevents ==
NULL);
1345 assert(propdata->issorted);
1346 assert(propdata->nlbevents == -1);
1347 assert(propdata->nubevents == -1);
1357 propdata->nlbevents = 0;
1358 propdata->nubevents = 0;
1361 for( i = 0; i < propdata->ncomponents; i++ )
1366 for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ )
1371 assert(j < propdata->ngenvbounds);
1373 genvbound = propdata->genvboundstore[j];
1374 assert(genvbound !=
NULL);
1377 for( k = 0; k < genvbound->
ncoefs; k++ )
1392 assert(propdata->nlbevents <= nprobvars);
1393 assert(propdata->nubevents <= nprobvars);
1394 if( propdata->nlbevents < nprobvars )
1398 if( propdata->nubevents < nprobvars )
1404 for( i = 0; i < propdata->nlbevents; i++ )
1408 assert(eventdata !=
NULL);
1409 assert(eventdata->nstarts > 0);
1410 assert(eventdata->startcomponents !=
NULL);
1411 assert(eventdata->startindices !=
NULL);
1414 if( eventdata->startindicessize != eventdata->nstarts )
1417 eventdata->nstarts) );
1419 eventdata->nstarts) );
1420 eventdata->startindicessize = eventdata->nstarts;
1429 for( i = 0; i < propdata->nubevents; i++ )
1433 assert(eventdata !=
NULL);
1434 assert(eventdata->nstarts > 0);
1435 assert(eventdata->startcomponents !=
NULL);
1436 assert(eventdata->startindices !=
NULL);
1439 if( eventdata->startindicessize != eventdata->nstarts )
1442 eventdata->nstarts) );
1444 eventdata->nstarts) );
1445 eventdata->startindicessize = eventdata->nstarts;
1480 int* strongcomponents;
1481 int* strongcompstartidx;
1485 assert(scip !=
NULL);
1486 assert(propdata !=
NULL);
1487 assert(propdata->componentsstart ==
NULL);
1489 SCIPdebugMsg(scip,
"(re-)sort genvbounds topologically\n");
1495 for( i = 0; i < propdata->ngenvbounds; i++ )
1500 assert(i < propdata->ngenvbounds);
1502 genvbound = propdata->genvboundstore[i];
1504 for( j = 0; j < genvbound->
ncoefs; j++ )
1529 propdata->componentsstartsize = propdata->ncomponents + 1;
1537 propdata->componentsstart[propdata->ncomponents] = propdata->ngenvbounds;
1538 for( i = 0; i < propdata->ncomponents; i++ )
1543 int nstrongcomponents;
1546 propdata->componentsstart[i] = sortedindex;
1552 &nstrongcomponents) );
1554 for( j = 0; j <
nnodes; ++j )
1561 node = strongcomponents[nnodes - j - 1];
1563 assert(node < propdata->ngenvbounds);
1564 genvboundssorted[sortedindex] = propdata->genvboundstore[node];
1570 for( j = 0; j <
nnodes; j++ )
1572 assert(nodes[j] < propdata->ngenvbounds);
1573 genvboundssorted[sortedindex] = propdata->genvboundstore[nodes[j]];
1578 assert(sortedindex == propdata->ngenvbounds);
1581 for( i = 0; i < propdata->ngenvbounds; i++ )
1583 assert(genvboundssorted[i] !=
NULL);
1585 propdata->genvboundstore[i] = genvboundssorted[i];
1586 propdata->genvboundstore[i]->
index = i;
1598 propdata->issorted =
TRUE;
1601 SCIPdebugMsg(scip,
"genvbounds got: %d\n", propdata->ngenvbounds);
1602 for( i = 0; i < propdata->ncomponents; i++ )
1608 for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ )
1611 printGenVBound(scip, propdata->genvboundstore[j]);
1632 int* startingcomponents;
1633 int* startingindices;
1637 SCIPdebugMsg(scip,
"applying %s genvbound propagation in depth %d\n", global ?
1640 assert(scip !=
NULL);
1641 assert(prop !=
NULL);
1642 assert(result !=
NULL);
1645 assert(propdata !=
NULL);
1646 assert(propdata->genvboundstore !=
NULL);
1654 if( !propdata->issorted )
1660 for( j = 0; j < propdata->ngenvbounds && *result !=
SCIP_CUTOFF; j++ )
1668 SCIPdebugMsg(scip,
"applying genvbound with index %d (unsorted mode)\n", j);
1677 startingcomponents = global ? propdata->gstartcomponents : propdata->startcomponents;
1678 startingindices = global ? propdata->gstartindices : propdata->startindices;
1679 nindices = global ? propdata->ngindices : propdata->nindices;
1681 for( i = 0; i < nindices && *result !=
SCIP_CUTOFF; i++ )
1685 SCIPdebugMsg(scip,
"starting in component %d at index %d\n", startingcomponents[i], startingindices[i]);
1686 for( j = startingindices[i]; j < propdata->componentsstart[startingcomponents[i] + 1] &&
1689 assert(j < propdata->ngenvbounds);
1697 SCIPdebugMsg(scip,
"applying genvbound with index %d, component %d\n", j, startingcomponents[i]);
1721 assert(scip !=
NULL);
1722 assert(propdata !=
NULL);
1723 assert(propdata->eventhdlr !=
NULL);
1730 propdata->genvboundstoresize = 2 * nprobvars;
1733 propdata->ngenvbounds = 0;
1752 assert(scip !=
NULL);
1753 assert(propdata !=
NULL);
1754 assert(genvbound !=
NULL);
1755 assert(
getGenVBound(scip, propdata, genvbound->var, genvbound->boundtype) ==
NULL);
1757 hashmap = genvbound->boundtype ==
SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds;
1763 assert(propdata->ngenvbounds <= propdata->genvboundstoresize);
1764 if( propdata->ngenvbounds == propdata->genvboundstoresize )
1766 int oldsize = propdata->genvboundstoresize;
1767 propdata->genvboundstoresize = 2*propdata->genvboundstoresize + 1;
1773 propdata->genvboundstore[propdata->ngenvbounds] = genvbound;
1774 genvbound->index = propdata->ngenvbounds;
1775 propdata->ngenvbounds++;
1777 assert(propdata->ngenvbounds <= propdata->genvboundstoresize);
1792 assert(scip !=
NULL);
1793 assert(propdata !=
NULL);
1794 assert(propdata->prop !=
NULL);
1795 assert(result !=
NULL);
1831 if( propdata->ngindices > 0 )
1847 if(
SCIPgetDepth(scip) > 0 || propdata->propinrootnode )
1850 if( !propdata->issorted || (
SCIPgetCurrentNode(scip) == propdata->lastnodecaught && propdata->nindices > 0 ) )
1870 assert(scip !=
NULL);
1871 assert(propdata !=
NULL);
1872 assert(propdata->propasconss);
1875 if( propdata->cutoffboundvar ==
NULL )
1883 SCIPdebugMsg(scip,
"initialize cutoffboundvar with UB = %e\n", ub);
1898 assert(propdata->cutoffboundvar !=
NULL);
1901 for( i = 0; i < propdata->ngenvbounds; ++i )
1911 genvbound = propdata->genvboundstore[i];
1912 assert(genvbound !=
NULL);
1914 nvars = genvbound->
ncoefs + 2;
1921 for( j = 0; j < genvbound->
ncoefs; j++ )
1923 vars[j] = genvbound->
vars[j];
1924 vals[j] = genvbound->
coefs[j];
1929 vars[genvbound->
ncoefs] = genvbound->
var;
1935 vars[genvbound->
ncoefs + 1] = propdata->cutoffboundvar;
1955 if( propdata->ngenvbounds > 0 )
1957 assert(propdata->genvboundstore !=
NULL);
1959 for( i = propdata->ngenvbounds - 1; i >= 0; i-- )
1978 propdata->genvboundstore =
NULL;
1979 propdata->genvboundstoresize = 0;
1980 propdata->ngenvbounds = 0;
2014 assert(scip !=
NULL);
2015 assert(genvboundprop !=
NULL);
2017 assert(vars !=
NULL);
2018 assert(var !=
NULL);
2021 assert(coefcutoffbound <= 0.0);
2026 SCIPerrorMessage(
"cannot create generalized variable bound from invalid data\n");
2031 assert(propdata !=
NULL);
2034 if( propdata->genvboundstore ==
NULL )
2040 newgenvbound = (genvbound ==
NULL);
2045 for( i = 0; i < genvbound->
ncoefs; ++i )
2047 assert(genvbound->
vars[i] !=
NULL);
2064 else if( !newgenvbound && genvbound->
ncoefs ==
ncoefs )
2067 for( i = 0; i <
ncoefs; i++ )
2070 genvbound->
vars[i] = vars[i];
2084 for( i = 0; i <
ncoefs; i++ )
2087 genvbound->
vars[i] = vars[i];
2090 else if( newgenvbound )
2108 for( i = 0; i < genvbound->
ncoefs; ++i )
2110 assert(genvbound->
vars[i] !=
NULL);
2115 assert(genvbound->
var !=
NULL);
2150 propdata->issorted =
FALSE;
2154 SCIPdebug( printGenVBound(scip, genvbound) );
2155 #ifdef SCIP_DEBUG_SOLUTION 2156 SCIP_CALL( checkDebugSolutionGenVBound(scip, genvbound) );
2175 assert(prop !=
NULL);
2180 assert(propdata !=
NULL);
2182 propdata->genvboundstore =
NULL;
2183 propdata->genvboundstoresize = 0;
2184 propdata->lbevents =
NULL;
2185 propdata->ubevents =
NULL;
2186 propdata->lbgenvbounds =
NULL;
2187 propdata->ubgenvbounds =
NULL;
2188 propdata->lbeventsmap =
NULL;
2189 propdata->ubeventsmap =
NULL;
2190 propdata->startmap =
NULL;
2191 propdata->componentsstart =
NULL;
2192 propdata->startindices =
NULL;
2193 propdata->startcomponents =
NULL;
2194 propdata->gstartindices =
NULL;
2195 propdata->gstartcomponents =
NULL;
2197 propdata->lastnodecaught =
NULL;
2198 propdata->cutoffboundvar =
NULL;
2199 propdata->ngenvbounds = -1;
2200 propdata->ncomponents = -1;
2201 propdata->nindices = -1;
2202 propdata->ngindices = -1;
2203 propdata->nlbevents = -1;
2204 propdata->nubevents = -1;
2205 propdata->issorted =
FALSE;
2207 propdata->prop = prop;
2220 assert(prop !=
NULL);
2230 assert(propdata !=
NULL);
2235 if( propdata->ngenvbounds < 1 )
2255 assert(prop !=
NULL);
2260 assert(propdata !=
NULL);
2263 if( propdata->cutoffboundvar !=
NULL )
2265 SCIPdebugMsg(scip,
"propinitpre in problem <%s>: locking cutoffboundvar (current downlocks=%d, uplocks=%d)\n",
2284 assert(scip !=
NULL);
2285 assert(prop !=
NULL);
2288 SCIPdebugMsg(scip,
"propexitpre in problem <%s>: removing fixed, aggregated, negated, and multi-aggregated variables from right-hand side\n",
2295 assert(propdata !=
NULL);
2298 assert(propdata->lbevents ==
NULL);
2299 assert(propdata->ubevents ==
NULL);
2301 for( i = 0; i < propdata->ngenvbounds; )
2308 genvbound = propdata->genvboundstore[i];
2309 assert(genvbound !=
NULL);
2314 nvars = genvbound->
ncoefs;
2322 if( requiredsize > genvbound->
ncoefs )
2325 if( genvbound->
coefssize < requiredsize )
2333 assert(requiredsize <= genvbound->
ncoefs);
2337 for( j = 0; j < genvbound->
ncoefs; ++j )
2339 assert(genvbound->
vars[j] !=
NULL);
2342 for( j = 0; j < nvars; ++j )
2344 assert(vars[j] !=
NULL);
2368 --(propdata->ngenvbounds);
2371 if( i < propdata->ngenvbounds )
2373 propdata->genvboundstore[i] = propdata->genvboundstore[propdata->ngenvbounds];
2374 propdata->genvboundstore[i]->index = i;
2377 propdata->issorted =
FALSE;
2397 assert(prop !=
NULL);
2408 assert(propdata !=
NULL);
2411 if( propdata->cutoffboundvar !=
NULL )
2418 assert(propdata->propasconss);
2430 SCIPdebugMsg(scip,
"tightened UB of cutoffboundvar to %e (old: %e, infeas: %u, tightened: %u)\n",
2431 newub, oldub, infeasible, tightened);
2434 assert(infeasible ==
FALSE);
2442 if( propdata->ngenvbounds < 1 )
2450 if( propdata->propasconss )
2479 SCIPdebugMsg(scip,
"explain %s bound change of variable <%s>\n",
2484 assert(propdata !=
NULL);
2485 assert(propdata->genvboundstore !=
NULL);
2490 assert(inferinfo >= 0);
2491 assert(inferinfo < propdata->ngenvbounds);
2496 if( inferinfo >= propdata->ngenvbounds)
2498 SCIPerrorMessage(
"generalized variable bounds propagator received inferinfo out of range; propagation not resolved, safe to continue\n");
2503 genvbound = propdata->genvboundstore[inferinfo];
2504 assert(genvbound !=
NULL);
2505 assert(genvbound->
var == infervar);
2508 if( genvbound->
var != infervar )
2510 SCIPerrorMessage(
"generalized variable bounds propagator received incorrect inferinfo; propagation not resolved, but it's safe to continue\n");
2527 boundval =
MIN(boundval, roundedboundval);
2546 assert(scip !=
NULL);
2547 assert(prop !=
NULL);
2554 assert(propdata !=
NULL);
2559 for( i = propdata->ngenvbounds - 1; i >= 0; i-- )
2572 propdata->ngenvbounds = 0;
2589 propdata->cutoffboundvar =
NULL;
2606 assert(propdata !=
NULL);
2626 assert(scip !=
NULL);
2627 assert(eventdata !=
NULL);
2632 assert(eventdata->startcomponents !=
NULL);
2633 assert(eventdata->startindices !=
NULL);
2634 assert(eventdata->nstarts > 0);
2635 assert(eventdata->prop !=
NULL);
2638 assert(propdata !=
NULL);
2640 assert(propdata->startcomponents !=
NULL);
2641 assert(propdata->startmap !=
NULL);
2642 assert(propdata->startindices !=
NULL);
2655 for( i = 0; i < eventdata->nstarts; i++ )
2660 component = eventdata->startcomponents[i];
2661 assert(component >= 0);
2662 startidx = eventdata->startindices[i];
2670 componentidx = ((int)(
size_t)
SCIPhashmapGetImage(propdata->startmap, (
void*)(
size_t) (component + 1))) - 1;
2671 assert(componentidx >= 0);
2672 assert(propdata->startcomponents[componentidx] == component);
2674 if( propdata->startindices[componentidx] > startidx )
2675 propdata->startindices[componentidx] = startidx;
2681 componentidx = propdata->nindices;
2684 propdata->startcomponents[componentidx] = component;
2685 propdata->startindices[componentidx] = startidx;
2689 (
void*)(
size_t) (componentidx + 1)) );
2692 propdata->nindices++;
2716 propExecGenvbounds, propdata) );
2728 "apply global propagation?",
2732 "apply genvbounds in root node if no new incumbent was found?",
2736 "sort genvbounds and wait for bound change events?",
2740 "should genvbounds be transformed to (linear) constraints?",
enum SCIP_Result SCIP_RESULT
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
enum SCIP_BoundType SCIP_BOUNDTYPE
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
static SCIP_RETCODE applyGenVBound(SCIP *scip, SCIP_PROP *prop, GENVBOUND *genvbound, SCIP_Bool global, SCIP_RESULT *result, int *nchgbds)
SCIP_Real SCIPfeastol(SCIP *scip)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
static SCIP_RETCODE freeComponentsData(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
static SCIP_RETCODE freeGenVBound(SCIP *scip, GENVBOUND *genvbound)
static SCIP_RETCODE execGenVBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_RESULT *result, SCIP_Bool local, int *nchgbds)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
static SCIP_RETCODE initPropdata(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
static SCIP_RETCODE applyGenVBounds(SCIP *scip, SCIP_PROP *prop, SCIP_Bool global, SCIP_RESULT *result, int *nchgbds)
static SCIP_RETCODE dropAndFreeEvents(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
#define PROP_PRESOL_MAXROUNDS
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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)
static SCIP_DECL_PROPEXEC(propExecGenvbounds)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_RETCODE freeAllEventData(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
static SCIP_RETCODE analyzeGenVBoundConflict(SCIP *scip, GENVBOUND *genvbound)
static SCIP_RETCODE freeEventData(SCIP *scip, SCIP_EVENTDATA **eventdata)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var)
enum SCIP_Retcode SCIP_RETCODE
SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup)
static SCIP_DECL_PROPEXITSOL(propExitsolGenvbounds)
static GENVBOUND * getGenVBound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype)
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
#define SCIPfreeBlockMemory(scip, ptr)
static SCIP_RETCODE resetLocalStartingData(SCIP *scip, SCIP_PROPDATA *propdata)
#define PROP_PRESOLTIMING
void SCIPdigraphGetComponent(SCIP_DIGRAPH *digraph, int compidx, int **nodes, int *nnodes)
static SCIP_Real getGenVBoundsMinActivity(SCIP *scip, SCIP_VAR **vars, SCIP_Real *coefs, int nvars, SCIP_Bool global)
#define DEFAULT_PROPASCONSS
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
static SCIP_RETCODE fillGlobalStartingData(SCIP *scip, SCIP_PROPDATA *propdata)
#define SCIPdebugMsgPrint
SCIP_RETCODE SCIPdigraphTopoSortComponents(SCIP_DIGRAPH *digraph)
static SCIP_DECL_PROPEXITPRE(propExitpreGenvbounds)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE addEventData(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, int startindex, int startcomponent, SCIP_BOUNDTYPE boundtype)
const char * SCIPgetProbName(SCIP *scip)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
int SCIPdigraphGetNNodes(SCIP_DIGRAPH *digraph)
int SCIPgetNFixedVars(SCIP *scip)
SCIP_RETCODE SCIPdigraphCreate(SCIP_DIGRAPH **digraph, int nnodes)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_RETCODE SCIPsetPropExitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITPRE((*propexitpre)))
static SCIP_RETCODE addNewGenVBound(SCIP *scip, SCIP_PROPDATA *propdata, GENVBOUND *genvbound)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_Real getGenVBoundsBound(SCIP *scip, GENVBOUND *genvbound, SCIP_Bool global)
static SCIP_RETCODE resolveGenVBoundPropagation(SCIP *scip, GENVBOUND *genvbound, SCIP_BDCHGIDX *bdchgidx, SCIP_Real *boundval, SCIP_Bool *success)
static SCIP_DECL_EVENTEXEC(eventExecGenvbounds)
SCIP_RETCODE SCIPgenVBoundAdd(SCIP *scip, SCIP_PROP *genvboundprop, SCIP_VAR **vars, SCIP_VAR *var, SCIP_Real *coefs, int ncoefs, SCIP_Real coefcutoffbound, SCIP_Real constant, SCIP_BOUNDTYPE boundtype)
#define DEFAULT_PROPAGATE_IN_ROOT_NODE
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
static SCIP_Real getGenVBoundsMinActivityConflict(SCIP *scip, SCIP_VAR **vars, SCIP_Real *coefs, int nvars, SCIP_BDCHGIDX *bdchgidx)
struct SCIP_EventData SCIP_EVENTDATA
const char * SCIPvarGetName(SCIP_VAR *var)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
#define SCIP_EVENTTYPE_LBTIGHTENED
int SCIPgetNTotalVars(SCIP *scip)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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 SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
#define SCIPdebugCheckLbGlobal(scip, var, lb)
#define SCIPdebugGetSolVal(scip, var, val)
#define SCIPdebugCheckUbGlobal(scip, var, ub)
#define PROP_PRESOL_PRIORITY
static SCIP_RETCODE createConstraints(SCIP *scip, SCIP_PROPDATA *propdata)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetPropInit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINIT((*propinit)))
static SCIP_RETCODE setUpEvents(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
SCIP_RETCODE SCIPhashmapRemoveAll(SCIP_HASHMAP *hashmap)
int SCIPgetDepth(SCIP *scip)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
SCIP_RETCODE SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub)
static SCIP_Real getCutoffboundGenVBound(SCIP *scip)
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
SCIP_RETCODE SCIPdigraphComputeDirectedComponents(SCIP_DIGRAPH *digraph, int compidx, int *strongcomponents, int *strongcompstartidx, int *nstrongcomponents)
#define BMScopyMemoryArray(ptr, source, num)
static SCIP_DECL_PROPFREE(propFreeGenvbounds)
static SCIP_DECL_PROPINITPRE(propInitpreGenvbounds)
#define SCIP_EVENTTYPE_UBTIGHTENED
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetTransObjscale(SCIP *scip)
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
SCIP_Bool SCIPinProbing(SCIP *scip)
const char * SCIPpropGetName(SCIP_PROP *prop)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPcreateConsLinear(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)
SCIP_Real SCIPgetTransObjoffset(SCIP *scip)
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_Bool SCIPallowDualReds(SCIP *scip)
static SCIP_RETCODE createStartingData(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
static SCIP_RETCODE getEventData(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_EVENTDATA **eventdata)
struct SCIP_PropData SCIP_PROPDATA
static SCIP_RETCODE sortGenVBounds(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_GLOBAL_PROPAGATION
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_RETCODE SCIPincludePropGenvbounds(SCIP *scip)
static SCIP_DECL_PROPRESPROP(propRespropGenvbounds)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
#define BMSclearMemoryArray(ptr, num)
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
static SCIP_RETCODE freeStartingData(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_Bool SCIPisInRestart(SCIP *scip)
static SCIP_DECL_PROPPRESOL(propPresolGenvbounds)
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
SCIP_Bool SCIPallowObjProp(SCIP *scip)
static SCIP_DECL_PROPINIT(propInitGenvbounds)
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)
generalized variable bounds propagator
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)