68#define CONSHDLR_NAME "cumulative"
69#define CONSHDLR_DESC "cumulative constraint handler"
70#define CONSHDLR_SEPAPRIORITY 2100000
71#define CONSHDLR_ENFOPRIORITY -2040000
72#define CONSHDLR_CHECKPRIORITY -3030000
73#define CONSHDLR_SEPAFREQ 1
74#define CONSHDLR_PROPFREQ 1
75#define CONSHDLR_EAGERFREQ 100
77#define CONSHDLR_MAXPREROUNDS -1
78#define CONSHDLR_DELAYSEPA FALSE
79#define CONSHDLR_DELAYPROP FALSE
80#define CONSHDLR_NEEDSCONS TRUE
82#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
83#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
93#define DEFAULT_MAXTIME 2000000000
96#define DEFAULT_USEBINVARS FALSE
97#define DEFAULT_LOCALCUTS FALSE
98#define DEFAULT_USECOVERCUTS TRUE
99#define DEFAULT_CUTSASCONSS TRUE
100#define DEFAULT_SEPAOLD TRUE
103#define DEFAULT_TTINFER TRUE
104#define DEFAULT_EFCHECK FALSE
105#define DEFAULT_EFINFER FALSE
106#define DEFAULT_USEADJUSTEDJOBS FALSE
107#define DEFAULT_TTEFCHECK TRUE
108#define DEFAULT_TTEFINFER TRUE
111#define DEFAULT_DUALPRESOLVE TRUE
112#define DEFAULT_COEFTIGHTENING FALSE
113#define DEFAULT_NORMALIZE TRUE
114#define DEFAULT_PRESOLPAIRWISE TRUE
115#define DEFAULT_DISJUNCTIVE TRUE
116#define DEFAULT_DETECTDISJUNCTIVE TRUE
117#define DEFAULT_DETECTVARBOUNDS TRUE
118#define DEFAULT_MAXNODES 10000LL
121#define DEFAULT_FILLBRANCHCANDS FALSE
124#define DEFAULT_USEBDWIDENING TRUE
133#define EVENTHDLR_NAME "cumulative"
134#define EVENTHDLR_DESC "bound change event handler for cumulative constraints"
173 unsigned int signature;
175 unsigned int validsignature:1;
176 unsigned int normalized:1;
177 unsigned int covercuts:1;
178 unsigned int propagated:1;
179 unsigned int varbounds:1;
180 unsigned int triedsolving:1;
188struct SCIP_ConshdlrData
240 int nallconsdualfixs;
242 int naddeddisjunctives;
278 unsigned int proprule:2;
279 unsigned int data1:15;
280 unsigned int data2:15;
295 inferinfo.val.asint =
i;
306 return inferinfo.val.asint;
339 return (
PROPRULE) inferinfo.val.asbits.proprule;
348 return (
int) inferinfo.val.asbits.data1;
357 return (
int) inferinfo.val.asbits.data2;
366 return (inferinfo.val.asint != 0);
381 if( proprule ==
PROPRULE_0_INVALID || data1 < 0 || data1 >= (1<<15) || data2 < 0 || data2 >= (1<<15) )
383 inferinfo.val.asint = 0;
389 inferinfo.val.asbits.proprule = proprule;
390 inferinfo.val.asbits.data1 = (
unsigned int) data1;
391 inferinfo.val.asbits.data2 = (
unsigned int) data2;
422 core =
MAX(0,
MIN(end, ect) -
MAX(lst, begin));
427#define computeCoreWithInterval(begin, end, ect, lst) (MAX(0, MIN((end), (ect)) - MAX((lst), (begin))))
439#ifdef SCIP_DISABLED_CODE
452#ifdef SCIP_DISABLED_CODE
460 for( v = 0; v < nvbdvars; ++v )
472 duration = (int)(
size_t)image;
479 if( duration >= vbdconst )
485 if( (*est) < impliedest )
509#ifdef SCIP_DISABLED_CODE
521#ifdef SCIP_DISABLED_CODE
529 for( v = 0; v < nvbdvars; ++v )
544 if( duration >= -vbdconst )
550 if( (*lct) > impliedlct )
584 startindex = nstarted - 1;
590 while( nstarted - nfinished > nrowvars )
599 varidx = startindices[startindex];
603 duration = consdata->durations[
varidx];
604 demand = consdata->demands[
varidx];
610 if( endtime > curtime )
628 start = curtime - duration + 1;
629 end =
MIN(curtime, endtime - duration);
631 for(
b = 0;
b < nbinvars; ++
b )
633 if( vals[
b] < start )
649 (*vars)[*
nvars] = binvars[
b];
650 (*coefs)[*
nvars] = demand;
687 assert(curtime >= consdata->hmin);
688 assert(curtime < consdata->hmax);
695 startindex = nstarted - 1;
698 while( nstarted - nfinished > counter )
703 varidx = startindices[startindex];
707 duration = consdata->durations[
varidx];
716 endtime =
MIN(starttime + duration, consdata->hmax);
719 if( endtime > curtime )
721 (*activevars)[counter] =
var;
722 sumofstarts += starttime;
723 mindelta =
MIN(mindelta, endtime - curtime);
731 *lhs = lower ? sumofstarts + mindelta : sumofstarts - mindelta;
756 for ( j = 0; j <
nvars; ++j )
803 for ( j = 0; j <
nvars; ++j )
843 tmpnvars = consdata->nvars;
847 for ( j = 0; j < tmpnvars; ++j )
849 var = consdata->vars[j];
851 assert(consdata->durations[j] > 0);
852 assert(consdata->demands[j] > 0);
862 startindices[*
nvars] = j;
864 endtimes[*
nvars] = starttimes[*
nvars] + consdata->durations[j];
865 endindices[*
nvars] = j;
867 SCIPdebugMsg(
scip,
"%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
869 consdata->durations[j],
870 starttimes[*
nvars], starttimes[*
nvars] + consdata->durations[startindices[*
nvars]],
871 consdata->demands[startindices[*
nvars]]);
882 startindices[*
nvars] = j;
884 endtimes[*
nvars] = starttimes[*
nvars] + consdata->durations[j];
885 endindices[*
nvars] = j;
887 SCIPdebugMsg(
scip,
"%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
889 consdata->durations[j],
890 starttimes[*
nvars], starttimes[*
nvars] + consdata->durations[startindices[*
nvars]],
891 consdata->demands[startindices[*
nvars]]);
904 for ( j = 0; j < *
nvars; ++j )
906 SCIPdebugMsg(
scip,
"%d: job[%d] starttime %d, endtime = %d, demand = %d\n", j,
907 startindices[j], starttimes[j], starttimes[j] + consdata->durations[startindices[j]],
908 consdata->demands[startindices[j]]);
911 for ( j = 0; j < *
nvars; ++j )
913 SCIPdebugMsg(
scip,
"%d: job[%d] endtime %d, demand = %d\n", j, endindices[j], endtimes[j],
914 consdata->demands[endindices[j]]);
972 (*timepoints)[0] = starttimes[0];
973 (*cumulativedemands)[0] = 0;
977 for( j = 0; j <
nvars; ++j )
982 curtime = starttimes[j];
984 if( curtime >= hmax )
988 while( endindex <
nvars && endtimes[endindex] <= curtime )
992 if( (*timepoints)[*ntimepoints] < endtimes[endindex] )
995 (*timepoints)[*ntimepoints] = endtimes[endindex];
996 (*cumulativedemands)[*ntimepoints] = 0;
999 idx = endindices[endindex];
1001 totaldemand -= (
SCIP_Real) demands[idx] * durations[idx] / (endtimes[endindex] - est);
1004 (*cumulativedemands)[*ntimepoints] = totaldemand;
1007 idx = startindices[j];
1009 totaldemand += (
SCIP_Real) demands[idx] * durations[idx] / (lct - starttimes[j]);
1011 if( (*timepoints)[*ntimepoints] < curtime )
1014 (*timepoints)[*ntimepoints] = curtime;
1015 (*cumulativedemands)[*ntimepoints] = 0;
1018 (*cumulativedemands)[*ntimepoints] = totaldemand;
1021 while( j+1 <
nvars && starttimes[j+1] == curtime )
1024 idx = startindices[j];
1026 totaldemand += (
SCIP_Real) demands[idx] * durations[idx] / (lct - starttimes[j]);
1028 (*cumulativedemands)[*ntimepoints] = totaldemand;
1033 while( endindex <
nvars)
1038 if( (*timepoints)[*ntimepoints] < endtimes[endindex] )
1041 (*timepoints)[*ntimepoints] = endtimes[endindex];
1042 (*cumulativedemands)[*ntimepoints] = 0;
1045 idx = endindices[endindex];
1047 totaldemand -= (
SCIP_Real) demands[idx] * durations[idx] / (endtimes[endindex] - est);
1048 (*cumulativedemands)[*ntimepoints] = totaldemand;
1055 (*minfreecapacity) = INT_MAX;
1056 for( j = 0; j < *ntimepoints; ++j )
1058 if( (*timepoints)[j] >= hmin && (*timepoints)[j] < hmax )
1059 *minfreecapacity =
MIN( *minfreecapacity, (
SCIP_Real)capacity - (*cumulativedemands)[j] );
1097 nvars = consdata->nvars;
1098 capacity = consdata->capacity;
1100 globalmaxdemand = 0.0;
1107 for( v = 0; v <
nvars; ++v )
1118 peak = consdata->demands[v];
1123 if( consdata->demands[v] > capacity / 3 )
1126 for( j = 0; j <
nvars; ++j )
1136 if( lb <= timepoint && lb + consdata->durations[j] > timepoint )
1138 peak += consdata->demands[j];
1141 if( consdata->demands[j] > consdata->capacity / 3 )
1147 globalpeak =
MAX(globalpeak, peak);
1148 globalmaxdemand =
MAX(globalmaxdemand, maxdemand);
1150 if( peak > capacity )
1153 cumfactor1 =
MAX( cumfactor1, (peak-capacity)/peak * (capacity-deltademand)/(
SCIP_Real)capacity );
1154 resstrength2 =
MAX(resstrength2, (capacity-maxdemand)/(peak-maxdemand) );
1158 resstrength1 = (capacity-globalmaxdemand) / (globalpeak-globalmaxdemand);
1161 consdata->disjfactor2 = disjfactor2;
1162 consdata->cumfactor1 = cumfactor1;
1163 consdata->resstrength2 = resstrength2;
1164 consdata->resstrength1 = resstrength1;
1178 minfreecapacity = INT_MAX;
1181 consdata->durations, consdata->demands,
1182 capacity, consdata->hmin, consdata->hmax, &timepoints, &estimateddemands,
1183 &ntimepoints, &maxdemand, &minfreecapacity) );
1189 consdata->estimatedstrength = (
SCIP_Real)(capacity - minfreecapacity) / (
SCIP_Real) capacity;
1192 SCIPstatisticPrintf(
"cumulative constraint<%s>: DISJ1=%g, DISJ2=%g, CUM=%g, RS1 = %g, RS2 = %g, EST = %g\n",
1193 SCIPconsGetName(cons), consdata->disjfactor1, disjfactor2, cumfactor1, resstrength1, resstrength2,
1194 consdata->estimatedstrength);
1224 if( realconstant < 0.0 )
1229 if( realscalar < 0.0 )
1258 for( j = 0; j < njobs; ++j )
1311 for( v = 0; v < njobs; ++v )
1318 if( objvals ==
NULL )
1329 njobs, subvars, durations, demands, capacity) );
1374 (*infeasible) =
TRUE;
1378 (*unbounded) =
TRUE;
1389 for( v = 0; v < njobs; ++v )
1406 for( v = 0; v < njobs; ++v )
1428 for( v = 0; v < njobs; ++v )
1449 (*infeasible) =
FALSE;
1450 (*unbounded) =
FALSE;
1453 SCIPdebugMessage(
"solve independent cumulative condition with %d variables\n", njobs);
1460 njobs, capacity, hmin, hmax,
1461 maxnodes, timelimit, memorylimit,
1463 infeasible, unbounded, solved, error);
1473#ifdef SCIP_DISABLED_CODE
1492 (*infeasible) =
FALSE;
1493 (*unbounded) =
FALSE;
1496 SCIPdebugMsg(
scip,
"solve independent cumulative condition with %d variables\n", njobs);
1515 for( v = 0; v < njobs; ++v )
1523 if( objvals ==
NULL )
1532 timeinterval = lst - est + 1;
1533 assert(timeinterval > 0);
1536 minest =
MIN(minest, est);
1537 maxlct =
MAX(maxlct, lst + durations[v]);
1546 for( t = 0; t < timeinterval; ++t )
1559 binvars[v][t] = binvar;
1568 hmin =
MAX(hmin, minest);
1569 hmax =
MIN(hmax, maxlct);
1575 for( t = hmin; t < hmax; ++t )
1586 for( v = 0; v < njobs; ++v )
1599 duration = durations[v];
1603 if( t < est || t >= lst + duration )
1606 demand = demands[v];
1609 start =
MAX(t - duration + 1, est);
1614 for( k = start; k <= end; ++k )
1651 (*infeasible) =
TRUE;
1655 (*unbounded) =
TRUE;
1665 for( v = 0; v < njobs; ++v )
1675 timeinterval = lst - est + 1;
1678 for( t = 0; t < timeinterval; ++t )
1698 for( v = 0; v < njobs; ++v )
1708 timeinterval = lst - est + 1;
1711 for( t = 0; t < timeinterval; ++t )
1721 for( t = timeinterval - 1; t >= 0; --t )
1744 for( v = 0; v < njobs; ++v )
1754 timeinterval = lst - est + 1;
1756 for( t = 0; t < timeinterval; ++t )
1797 (*conshdlrdata)->eventhdlr = eventhdlr;
1800 (*conshdlrdata)->solveCumulative = solveCumulativeViaScipCp;
1802#ifdef SCIP_STATISTIC
1803 (*conshdlrdata)->nlbtimetable = 0;
1804 (*conshdlrdata)->nubtimetable = 0;
1805 (*conshdlrdata)->ncutofftimetable = 0;
1806 (*conshdlrdata)->nlbedgefinder = 0;
1807 (*conshdlrdata)->nubedgefinder = 0;
1808 (*conshdlrdata)->ncutoffedgefinder = 0;
1809 (*conshdlrdata)->ncutoffoverload = 0;
1810 (*conshdlrdata)->ncutoffoverloadTTEF = 0;
1812 (*conshdlrdata)->nirrelevantjobs = 0;
1813 (*conshdlrdata)->nalwaysruns = 0;
1814 (*conshdlrdata)->nremovedlocks = 0;
1815 (*conshdlrdata)->ndualfixs = 0;
1816 (*conshdlrdata)->ndecomps = 0;
1817 (*conshdlrdata)->ndualbranchs = 0;
1818 (*conshdlrdata)->nallconsdualfixs = 0;
1819 (*conshdlrdata)->naddedvarbounds = 0;
1820 (*conshdlrdata)->naddeddisjunctives = 0;
1862 for( v = 0; v < consdata->nvars; ++v )
1906 for( v = 0; v < consdata->nvars; ++v )
1924 nvars = consdata->nvars;
1927 for( v = 0; v <
nvars; ++v )
1929 consdata->downlocks[v] = locked;
1930 consdata->uplocks[v] = locked;
1964 (*consdata)->hmin = hmin;
1965 (*consdata)->hmax = hmax;
1967 (*consdata)->capacity = capacity;
1968 (*consdata)->demandrows =
NULL;
1969 (*consdata)->demandrowssize = 0;
1970 (*consdata)->ndemandrows = 0;
1971 (*consdata)->scoverrows =
NULL;
1972 (*consdata)->nscoverrows = 0;
1973 (*consdata)->scoverrowssize = 0;
1974 (*consdata)->bcoverrows =
NULL;
1975 (*consdata)->nbcoverrows = 0;
1976 (*consdata)->bcoverrowssize = 0;
1977 (*consdata)->nvars =
nvars;
1978 (*consdata)->varssize =
nvars;
1979 (*consdata)->signature = 0;
1980 (*consdata)->validsignature =
FALSE;
1981 (*consdata)->normalized =
FALSE;
1982 (*consdata)->covercuts =
FALSE;
1983 (*consdata)->propagated =
FALSE;
1984 (*consdata)->varbounds =
FALSE;
1985 (*consdata)->triedsolving =
FALSE;
1994 (*consdata)->linkingconss =
NULL;
2002 if( linkingconss !=
NULL )
2018 for( v = 0; v <
nvars; ++v )
2023 if( linkingconss !=
NULL )
2028 for( v = 0; v <
nvars; ++v )
2037 for( v = 0; v < (*consdata)->nvars; ++v )
2043 (*consdata)->vars =
NULL;
2044 (*consdata)->downlocks =
NULL;
2045 (*consdata)->uplocks =
NULL;
2046 (*consdata)->demands =
NULL;
2047 (*consdata)->durations =
NULL;
2048 (*consdata)->linkingconss =
NULL;
2052 (*consdata)->resstrength1 = -1.0;
2053 (*consdata)->resstrength2 = -1.0;
2054 (*consdata)->cumfactor1 = -1.0;
2055 (*consdata)->disjfactor1 = -1.0;
2056 (*consdata)->disjfactor2 = -1.0;
2057 (*consdata)->estimatedstrength = -1.0;
2076 for(
r = 0;
r < (*consdata)->ndemandrows; ++
r )
2084 (*consdata)->ndemandrows = 0;
2085 (*consdata)->demandrowssize = 0;
2088 for(
r = 0;
r < (*consdata)->nscoverrows; ++
r )
2096 (*consdata)->nscoverrows = 0;
2097 (*consdata)->scoverrowssize = 0;
2099 for(
r = 0;
r < (*consdata)->nbcoverrows; ++
r )
2107 (*consdata)->nbcoverrows = 0;
2108 (*consdata)->bcoverrowssize = 0;
2110 (*consdata)->covercuts =
FALSE;
2128 nvars = (*consdata)->nvars;
2129 varssize = (*consdata)->varssize;
2139 if( (*consdata)->linkingconss !=
NULL )
2141 for( v =
nvars-1; v >= 0; --v )
2143 assert((*consdata)->linkingconss[v] !=
NULL );
2179 for( v = 0; v < consdata->nvars; ++v )
2186 consdata->durations[v], consdata->demands[v]);
2188 SCIPinfoMessage(
scip, file,
")[%d,%d) <= %d", consdata->hmin, consdata->hmax, consdata->capacity);
2215 consdata->downlocks[pos] =
FALSE;
2216 consdata->uplocks[pos] =
FALSE;
2218 if( consdata->linkingconss !=
NULL )
2233 SCIPdebugMsg(
scip,
"remove variable <%s>[%g,%g] from cumulative constraint <%s>\n",
2239 if( pos != consdata->nvars - 1 )
2241 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
2242 consdata->downlocks[pos] = consdata->downlocks[consdata->nvars-1];
2243 consdata->uplocks[pos] = consdata->uplocks[consdata->nvars-1];
2244 consdata->demands[pos] = consdata->demands[consdata->nvars-1];
2245 consdata->durations[pos] = consdata->durations[consdata->nvars-1];
2247 if( consdata->linkingconss !=
NULL )
2249 consdata->linkingconss[pos]= consdata->linkingconss[consdata->nvars-1];
2254 consdata->validsignature =
FALSE;
2255 consdata->normalized =
FALSE;
2273 nvars = consdata->nvars;
2279 for( v = 0; v <
nvars; ++v )
2284 var = consdata->vars[v];
2300 consdata->linkingconss[v] = cons;
2344 int* startsolvalues;
2360 (*violated) =
FALSE;
2376 for ( j = 0; j <
nvars; ++j )
2388 startsolvalues[j] =
MAX(solvalue, hmin);
2389 startindices[j] = j;
2391 endsolvalues[j] =
MAX(solvalue + durations[j], hmin);
2402 freecapacity = capacity;
2407 for( j = 0; j <
nvars; ++j )
2410 curtime = startsolvalues[j];
2412 if( curtime >= hmax )
2416 freecapacity -= demands[startindices[j]];
2417 while( j+1 <
nvars && startsolvalues[j+1] == curtime )
2420 freecapacity -= demands[startindices[j]];
2424 while( endindex < nvars && curtime >= endsolvalues[endindex] )
2426 freecapacity += demands[endindices[endindex]];
2429 assert(freecapacity <= capacity);
2432 if( absviol < (
SCIP_Real) (-freecapacity) )
2434 absviol = -freecapacity;
2439 if( freecapacity < 0 && curtime >= hmin )
2453 ";\nviolation: at time point %d available capacity = %d, needed capacity = %d\n",
2454 curtime, capacity, capacity - freecapacity);
2456 for(
i = 0;
i <= j; ++
i )
2458 if( startsolvalues[
i] + durations[startindices[
i]] > curtime )
2462 demands[startindices[
i]]);
2508 consdata->durations, consdata->demands, consdata->capacity, consdata->hmin, consdata->hmax,
2509 violated, cons, printreason) );
2553 SCIPdebugMsg(
scip,
"variable <%s>: (demand %d) resolve propagation of core time algorithm (peak %d)\n",
2558 capacity -= inferdemand;
2568 for( j = 0; j < nvars && capacity >= 0; ++j )
2574 if(
var == infervar )
2577 duration = durations[j];
2586 SCIPdebugMsg(
scip,
"variable <%s>: glb=[%g,%g] conflict=[%g,%g] (duration %d, demand %d)\n",
2596 if( inferpeak < ect && lst <= inferpeak )
2598 capacity -= demands[j];
2601 maxlst =
MAX(maxlst, lst);
2602 minect =
MIN(minect, ect);
2605 if( explanation !=
NULL )
2606 explanation[j] =
TRUE;
2623 if( inferpeak < ect && lst <= inferpeak )
2625 capacity -= demands[j];
2628 maxlst =
MAX(maxlst, lst);
2629 minect =
MIN(minect, ect);
2632 if( explanation !=
NULL )
2633 explanation[j] =
TRUE;
2649 for( j = 0; j <
nvars; ++j )
2655 if(
var == infervar || reported[j] )
2658 duration = durations[j];
2671 SCIPdebugMsg(
scip,
"variable <%s>: loc=[%g,%g] glb=[%g,%g] (duration %d, demand %d)\n",
2676 if( inferpeak < ect && lst <= inferpeak )
2679 canddemands[ncands] = demands[j];
2682 capacity -= demands[j];
2693 while( capacity + canddemands[ncands-1] < 0 )
2696 capacity += canddemands[ncands];
2701 for(
c = 0;
c < ncands; ++
c )
2706 duration = durations[cands[
c]];
2711 maxlst =
MAX(maxlst, lst);
2712 minect =
MIN(minect, ect);
2716 SCIPdebugMsg(
scip,
"infer peak %d, relaxed peak %d, lst %d, ect %d\n", inferpeak, relaxedpeak, maxlst, minect);
2717 assert(inferpeak >= maxlst);
2718 assert(inferpeak < minect);
2721 if( relaxedpeak < inferpeak )
2723 inferpeak =
MAX(maxlst, relaxedpeak);
2725 else if( relaxedpeak > inferpeak )
2727 inferpeak =
MIN(minect-1, relaxedpeak);
2729 assert(inferpeak >= hmin);
2730 assert(inferpeak < hmax);
2731 assert(inferpeak >= maxlst);
2732 assert(inferpeak < minect);
2735 for(
c = 0;
c < ncands; ++
c )
2742 duration = durations[cands[
c]];
2753 if( explanation !=
NULL )
2754 explanation[cands[
c]] =
TRUE;
2763 if( provedpeak !=
NULL )
2764 *provedpeak = inferpeak;
2784 ect = est + duration;
2785 lct = lst + duration;
2788 if( lct <= end && est >= begin )
2791 assert(lst <= end && ect >= begin);
2799 return MIN3(left, right, end - begin);
2837 requiredenergy = ((
SCIP_Longint) end - begin) * capacity;
2844 for( v = 0; v <
nvars; ++v )
2860 demand = demands[v];
2863 duration = durations[v];
2867 if( infervar ==
var )
2875 SCIPdebugMsg(
scip,
"inference variable <%s>[%g,%g] %s %g (duration %d, demand %d)\n",
2898 right =
MIN3(end - lst, end - begin, duration);
2909 left =
MIN(lct - begin + 1, end - begin);
2913 overlap =
MIN(left, right);
2915 assert(overlap <= end - begin);
2916 assert(overlap <= duration);
2946 left =
MIN3(ect - begin, end - begin, duration);
2956 right =
MIN(end - est + 1, end - begin);
2960 overlap =
MIN(left, right);
2962 assert(overlap <= end - begin);
2963 assert(overlap <= duration);
2979 if( explanation !=
NULL )
2980 explanation[v] =
TRUE;
2994 if( est + duration > begin && lst < end )
2997 glbenergy =
computeOverlap(begin, end, est, lst, duration) * demand;
3000 requiredenergy -= glbenergy;
3002 if( explanation !=
NULL )
3003 explanation[v] =
TRUE;
3013 if( est + duration > begin && lst < end )
3018 locenergies[v] = overlaps[v] * demand - glbenergy;
3019 assert(locenergies[v] >= 0);
3027 for( v = 0; v < nvars && requiredenergy >= 0; ++v )
3043 duration = durations[idx];
3046 overlap = overlaps[v];
3049 requiredenergy -= locenergies[v];
3051 if( requiredenergy < -1 )
3055 demand = demands[idx];
3058 overlap += (int)((requiredenergy + 1) / demand);
3061 requiredenergy += locenergies[v];
3063 assert(requiredenergy < 0);
3068 relaxlb = begin - duration + overlap;
3069 relaxub = end - overlap;
3071 SCIPdebugMsg(
scip,
"variable <%s> glb=[%g,%g] loc=[%g,%g], conf=[%g,%g], added=[%d,%d] (demand %d, duration %d)\n",
3076 relaxlb, relaxub, demands[idx], duration);
3081 if( explanation !=
NULL )
3082 explanation[idx] =
TRUE;
3085 assert(requiredenergy < 0);
3128 if( inferpos >=
nvars ||
vars[inferpos] != infervar )
3131 for( inferpos = 0; inferpos <
nvars &&
vars[inferpos] != infervar; ++inferpos )
3137 inferdemand = demands[inferpos];
3138 inferduration = durations[inferpos];
3147 SCIPdebugMsg(
scip,
"variable <%s>: upper bound changed from %g to %g (relaxed %g)\n",
3161 relaxedpeak =
MIN(relaxedpeak, hmax-1);
3167 relaxedpeak =
MAX(relaxedpeak, inferpeak);
3168 assert(relaxedpeak >= inferpeak);
3169 assert(relaxedpeak >= hmin);
3175 SCIPdebugMsg(
scip,
"variable <%s>: lower bound changed from %g to %g (relaxed %g)\n",
3188 relaxedpeak =
MAX(relaxedpeak, hmin);
3194 relaxedpeak =
MIN(relaxedpeak, inferpeak);
3195 assert(relaxedpeak < hmax);
3200 infervar, inferdemand, inferpeak, relaxedpeak, bdchgidx, usebdwidening, &provedpeak, explanation) );
3229 if( explanation !=
NULL )
3230 explanation[inferpos] =
TRUE;
3244 begin =
MAX(begin, hmin);
3245 end =
MIN(end, hmax);
3248 begin, end, infervar, boundtype, bdchgidx, relaxedbd, usebdwidening, explanation) );
3279 int* alternativelbs,
3280 int* alternativeubs,
3288 for( v = 0; v <
nvars; ++v )
3304 if( alternativelbs[v] <= ub )
3322 if( alternativeubs[v] >= lb )
3350#if defined SCIP_DEBUG && !defined NDEBUG
3362 assert(starttimes[*idx] == curtime);
3364 assert(freecapacity != idx);
3367 (*freecapacity) -= consdata->demands[startindices[*idx]];
3369 while( (*idx)+1 <
nvars && starttimes[(*idx)+1] == curtime )
3372 (*freecapacity) -= consdata->demands[startindices[(*idx)]];
3373 assert(freecapacity != idx);
3392#if defined SCIP_DEBUG && !defined NDEBUG
3398 while( endtimes[*idx] <= curtime && *idx <
nvars)
3400 (*freecapacity) += consdata->demands[endindices[*idx]];
3435 nvars = consdata->nvars;
3438 *timepoint = consdata->hmax;
3449 starttimes, endtimes, startindices, endindices);
3452 freecapacity = consdata->capacity;
3453 hmin = consdata->hmin;
3454 hmax = consdata->hmax;
3457 for( j = 0; j <
nvars; ++j )
3459 curtime = starttimes[j];
3462 if( curtime >= hmax )
3471 assert(freecapacity <= consdata->capacity);
3478 if( freecapacity < 0 && curtime >= hmin )
3480 *timepoint = curtime;
3512 SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal,
NULL) );
3517 for(
c = 0;
c < nconss; ++
c )
3537 if( curtime < consdata->hmin || curtime >= consdata->hmax )
3541 for( j = 0; j < consdata->nvars; ++j )
3547 var = consdata->vars[j];
3557 if( lb <= curtime && ub + consdata->durations[j] > curtime && lb < ub )
3563 score =
MIN(solval - lb, ub - solval) / ((
SCIP_Real)ub-lb);
3599 if( nbranchcands > 0 )
3610 for(
c = 0;
c < nconss && !violated; ++
c )
3650 nvars = consdata->nvars;
3651 vars = consdata->vars;
3652 downlocks = consdata->downlocks;
3653 uplocks = consdata->uplocks;
3656 for( v = 0; v <
nvars; ++v )
3721 if( ncheckconss == 1 )
3771 if( consdata->triedsolving )
3781 consdata->triedsolving =
TRUE;
3783 SCIPdebugMsg(
scip,
"the cumulative constraint <%s> is independent from rest of the problem (%d variables, %d constraints)\n",
3787 nvars = consdata->nvars;
3788 vars = consdata->vars;
3794 for( v = 0; v <
nvars; ++v )
3825 consdata->hmin, consdata->hmax, timelimit, memorylimit, maxnodes, &solved,
cutoff, unbounded, &error) );
3827 if( !(*
cutoff) && !(*unbounded) && !error )
3835 for( v = 0; v <
nvars; ++v )
3838 if( lbs[v] + 0.5 > ubs[v] )
3846 consdata->triedsolving =
FALSE;
3857 consdata->triedsolving =
FALSE;
3866 consdata->triedsolving =
FALSE;
3908 SCIPdebugMsg(
scip,
"detected infeasibility due to adding a core to the core resource profile\n");
3918 infervar, inferdemand, inferpeak, inferpeak,
NULL, usebdwidening,
NULL, explanation) );
3934 *initialized =
TRUE;
3978 duration = durations[idx];
3981 demand = demands[idx];
3993 SCIPdebugMsg(
scip,
"propagate earliest start time (lower bound) (pos %d)\n", pos);
4011 ect = est + duration;
4039 newlb =
MIN(newlb, ect);
4048 var, duration, demand, newlb-1, usebdwidening, initialized, explanation) );
4050 if( explanation !=
NULL )
4051 explanation[idx] =
TRUE;
4140 lct = lst + duration;
4198 newub =
MAX(newub, lst) - duration;
4232 lct = lst + duration;
4254 int* coreEnergyAfterEst,
4255 int* coreEnergyAfterLct
4264 t = ntimepoints - 1;
4268 for( v =
nvars-1; v >= 0; --v )
4286 coreEnergyAfterEst[v] = energy;
4289 t = ntimepoints - 1;
4293 for( v =
nvars-1; v >= 0; --v )
4311 coreEnergyAfterLct[v] = energy;
4336 for( v = 0; v <
nvars; ++ v)
4347 duration = durations[v];
4352 ect = est + duration;
4353 lct = lst + duration;
4364 leftadjust =
MAX(0, hmin - est);
4367 rightadjust =
MAX(0, lct - hmax);
4370 flexenergies[v] = duration - leftadjust - rightadjust - core;
4371 flexenergies[v] =
MAX(0, flexenergies[v]);
4372 flexenergies[v] *= demands[v];
4373 assert(flexenergies[v] >= 0);
4376 ects[v] =
MIN(ect, lst);
4379 lsts[v] =
MAX(ect, lst);
4417 if( !conshdlrdata->ttefinfer )
4421 if( est >= end || ect <= begin )
4427 if( est >= begin && ect <= end )
4448 newlb = end - (int) (energy / demand);
4453 if( newlb > lct - duration )
4475 (*initialized) =
TRUE;
4480 else if( newlb > (*bestlb) )
4531 if( !conshdlrdata->ttefinfer )
4535 if( lst >= end || lct <= begin )
4541 if( lst >= begin && lct <= end )
4562 newub = begin - duration + (int) (energy / demand);
4589 (*initialized) =
TRUE;
4594 else if( newub < (*bestub) )
4631 int* coreEnergyAfterEst,
4632 int* coreEnergyAfterLct,
4638 int coreEnergyAfterEnd;
4653 for( v = 0; v <
nvars; ++v )
4658 est =
MIN(est, start);
4659 lct =
MAX(lct, end);
4663 hmin =
MAX(hmin, est);
4664 hmax =
MIN(hmax, lct);
4667 coreEnergyAfterEnd = -1;
4669 maxavailable = ((
SCIP_Longint) hmax - hmin) * capacity;
4670 minavailable = maxavailable;
4682 for( v =
nvars-1; v >= 0 && !(*cutoff); --v )
4701 assert(v == 0 || lcts[v-1] <= lcts[v]);
4717 if( !conshdlrdata->ttefinfer && end <= hmax && minavailable < maxavailable )
4721 assert(coreEnergyAfterLct[v] >= coreEnergyAfterEnd);
4722 assert(coreEnergyAfterEnd >= 0);
4725 freeenergy = capacity * ((
SCIP_Longint) end - lct) - coreEnergyAfterLct[v] + coreEnergyAfterEnd;
4727 if( freeenergy <= minavailable )
4737 coreEnergyAfterEnd = coreEnergyAfterLct[v];
4740 minavailable = maxavailable;
4749 for(
i = nests-1;
i >= 0; --
i )
4779 if( ((
SCIP_Longint) end - est) * capacity >= totalenergy )
4785 duration = durations[idx];
4788 demand = demands[idx];
4800 if( minavailable < maxavailable && est < minbegin )
4806 var, duration, demand, est, lst, lct, minbegin, end, minavailable, &(newubs[idx]), &(ubinferinfos[idx]),
4807 initialized, explanation,
cutoff) );
4813 SCIPdebugMsg(
scip,
"check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, lst of free part <%d>\n",
4830 assert(flexenergies[idx] >= 0);
4831 flexenergy += flexenergies[idx];
4844 energy =
MIN(flexenergies[idx], demands[idx] *
MAX(0, (end - lst)));
4845 assert(end - lst < duration);
4849 flexenergy += energy;
4852 candenergy =
MIN(flexenergies[idx], demands[idx] * (end - begin)) - energy;
4856 if( candenergy > lbenergy )
4858 lbenergy = candenergy;
4863 SCIPdebugMsg(
scip,
"time window [%d,%d) flexible energy <%d>\n", begin, end, flexenergy);
4864 assert(coreEnergyAfterEst[
i] >= coreEnergyAfterEnd);
4867 freeenergy = capacity * ((
SCIP_Longint) end - begin) - flexenergy - coreEnergyAfterEst[
i] + coreEnergyAfterEnd;
4870 if( freeenergy < 0 )
4872 SCIPdebugMsg(
scip,
"analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
4882 conshdlrdata->usebdwidening, explanation) );
4884 (*initialized) =
TRUE;
4896 if( lbenergy > 0 && freeenergy < lbenergy )
4908 newlb = end - (int)(energy / demands[lbcand]);
4920 relaxedbd = lst + 1.0;
4927 conshdlrdata->usebdwidening, explanation) );
4929 (*initialized) =
TRUE;
4935 else if( newlb > newlbs[lbcand] )
4944 newlbs[lbcand] = newlb;
4949 if( minavailable > freeenergy )
4951 minavailable = freeenergy;
4954 assert(minavailable >= 0);
4982 int* coreEnergyAfterEst,
4983 int* coreEnergyAfterLct,
4989 int coreEnergyAfterStart;
5010 for( v = 0; v <
nvars; ++v )
5015 minest =
MIN(minest, start);
5016 maxlct =
MAX(maxlct, end);
5020 hmin =
MAX(hmin, minest);
5021 hmax =
MIN(hmax, maxlct);
5023 maxavailable = ((
SCIP_Longint) hmax - hmin) * capacity;
5035 for( v = 0; v <
nvars; ++v )
5067 coreEnergyAfterStart = coreEnergyAfterEst[v];
5070 minavailable = maxavailable;
5108 if( ((
SCIP_Longint) lct - begin) * capacity >= totalenergy )
5114 duration = durations[idx];
5117 demand = demands[idx];
5129 if( minavailable < maxavailable && lct > minend )
5135 var, duration, demand, est, ect, lct, begin, minend, minavailable, &(newlbs[idx]), &(lbinferinfos[idx]),
5136 initialized, explanation,
cutoff) );
5142 SCIPdebugMsg(
scip,
"check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, ect of free part <%d>\n",
5159 assert(flexenergies[idx] >= 0);
5160 flexenergy += flexenergies[idx];
5173 energy =
MIN(flexenergies[idx], demands[idx] *
MAX(0, (ect - begin)));
5174 assert(ect - begin < duration);
5178 flexenergy += energy;
5181 candenergy =
MIN(flexenergies[idx], demands[idx] * (end - begin)) - energy;
5185 if( candenergy > ubenergy )
5187 ubenergy = candenergy;
5192 SCIPdebugMsg(
scip,
"time window [%d,%d) flexible energy <%d>\n", begin, end, flexenergy);
5193 assert(coreEnergyAfterLct[
i] <= coreEnergyAfterStart);
5196 freeenergy = capacity * ((
SCIP_Longint) end - begin) - flexenergy - coreEnergyAfterStart + coreEnergyAfterLct[
i];
5199 if( freeenergy < 0 )
5201 SCIPdebugMsg(
scip,
"analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
5211 conshdlrdata->usebdwidening, explanation) );
5213 (*initialized) =
TRUE;
5225 if( ubenergy > 0 && freeenergy < ubenergy )
5231 duration = durations[ubcand];
5240 newub = begin - duration + (int)(energy / demands[ubcand]);
5242 if( newub < ect - duration )
5251 relaxedbd = ect - duration - 1.0;
5258 conshdlrdata->usebdwidening, explanation) );
5260 (*initialized) =
TRUE;
5266 else if( newub < newubs[ubcand] )
5275 newubs[ubcand] = newub;
5280 if( minavailable > freeenergy )
5282 minavailable = freeenergy;
5285 assert(minavailable >= 0);
5321 int* coreEnergyAfterEst;
5322 int* coreEnergyAfterLct;
5343 if( !conshdlrdata->ttefcheck )
5364 for( v = 0; v <
nvars; ++v )
5368 lbinferinfos[v] = 0;
5369 ubinferinfos[v] = 0;
5373 collectDataTTEF(
scip,
nvars,
vars, durations, demands, hmin, hmax, permests, ests, permlcts, lcts, ects, lsts, flexenergies);
5386 newlbs, newubs, lbinferinfos, ubinferinfos, lsts, flexenergies,
5387 permests, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation,
cutoff) );
5391 newlbs, newubs, lbinferinfos, ubinferinfos, ects, flexenergies,
5392 permlcts, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation,
cutoff) );
5395 for( v = 0; v <
nvars && !(*cutoff); ++v )
5403 TRUE, &infeasible, &tightened) );
5424 TRUE, &infeasible, &tightened) );
5467 conshdlrdata->usebdwidening, explanation) );
5469 (*initialized) =
TRUE;
5543 if( !conshdlrdata->ttinfer )
5548 SCIPdebugMsg(
scip,
"propagate cores of cumulative condition of constraint <%s>[%d,%d) <= %d\n",
5558 for( v = 0; v <
nvars; ++v )
5571 duration = durations[v];
5583 if( lst + duration <= hmin || est >= hmax )
5587 begin =
MAX(hmin, lst);
5588 end =
MIN(hmax, est + duration);
5590 demand = demands[v];
5596 SCIPdebugMsg(
scip,
"variable <%s>[%g,%g] (duration %d, demand %d): remove core [%d,%d)\n",
5604 profile, v, nchgbds, conshdlrdata->usebdwidening, initialized, explanation,
cutoff) );
5611 profile, v, nchgbds) );
5621 begin =
MAX(hmin, lst);
5622 end =
MIN(hmax, est + duration);
5629 SCIPdebugMsg(
scip,
"variable <%s>[%d,%d] (duration %d, demand %d): add core [%d,%d)\n",
5638 var, duration, demand,
SCIPprofileGetTime(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) );
5640 if( explanation !=
NULL )
5641 explanation[v] =
TRUE;
5691 SCIPdebugMsg(
scip,
"update envelop starting from node <%p>\n", (
void*)node);
5696 while( node !=
NULL )
5715 if( leftdata->enveloptheta >= 0 )
5717 assert(rightdata->energytheta != -1);
5718 nodedata->enveloptheta =
MAX(leftdata->enveloptheta + rightdata->energytheta, rightdata->enveloptheta);
5721 nodedata->enveloptheta = rightdata->enveloptheta;
5723 assert(leftdata->energytheta != -1);
5724 assert(rightdata->energytheta != -1);
5725 nodedata->energytheta = leftdata->energytheta + rightdata->energytheta;
5727 if( leftdata->enveloplambda >= 0 )
5729 assert(rightdata->energytheta != -1);
5730 nodedata->enveloplambda =
MAX(leftdata->enveloplambda + rightdata->energytheta, rightdata->enveloplambda);
5733 nodedata->enveloplambda = rightdata->enveloplambda;
5735 if( leftdata->enveloptheta >= 0 && rightdata->energylambda >= 0 )
5736 nodedata->enveloplambda =
MAX(
nodedata->enveloplambda, leftdata->enveloptheta + rightdata->energylambda);
5740 if( leftdata->energylambda >= 0 && rightdata->energylambda >= 0 )
5742 assert(rightdata->energytheta != -1);
5743 assert(leftdata->energytheta != -1);
5744 nodedata->energylambda =
MAX(leftdata->energylambda + rightdata->energytheta, leftdata->energytheta + rightdata->energylambda);
5746 else if( rightdata->energylambda >= 0 )
5748 assert(leftdata->energytheta != -1);
5749 nodedata->energylambda = leftdata->energytheta + rightdata->energylambda;
5751 else if( leftdata->energylambda >= 0 )
5753 assert(rightdata->energytheta != -1);
5754 nodedata->energylambda = leftdata->energylambda + rightdata->energytheta;
5835 if( grandparent !=
NULL )
5945 if(
nodedata->key < leafdata->key )
5958 newnodedata = &nodedatas[*nnodedatas];
5959 nodedataidx[*nnodedatas] = *nnodedatas;
5963 newnodedata->var =
NULL;
5965 newnodedata->est = INT_MIN;
5966 newnodedata->lct = INT_MAX;
5967 newnodedata->duration = 0;
5968 newnodedata->demand = 0;
5969 newnodedata->enveloptheta = -1;
5970 newnodedata->energytheta = 0;
5971 newnodedata->enveloplambda = -1;
5972 newnodedata->energylambda = -1;
5973 newnodedata->idx = -1;
5974 newnodedata->intheta =
TRUE;
5982 if( parent !=
NULL )
5999 if(
nodedata->key < leafdata->key )
6011 newnodedata->key = leafdata->key;
6061 assert(rightdata->energytheta != -1);
6063 if( leftdata->energylambda >= 0 &&
nodedata->energylambda == leftdata->energylambda + rightdata->energytheta )
6066 assert(leftdata->energytheta != -1);
6067 assert(rightdata->energylambda != -1);
6068 assert(
nodedata->energylambda == leftdata->energytheta + rightdata->energylambda);
6110 assert(rightdata->energytheta != -1);
6113 if( leftdata->enveloplambda >= 0 &&
nodedata->enveloplambda == leftdata->enveloplambda + rightdata->energytheta )
6115 else if( leftdata->enveloptheta >= 0 && rightdata->energylambda >= 0
6116 &&
nodedata->enveloplambda == leftdata->enveloptheta + rightdata->energylambda )
6119 assert(rightdata->enveloplambda != -1);
6152 omegaset[*nelements] = node;
6205 assert(rightdata->energytheta != -1);
6207 if( leftdata->enveloptheta >= 0 &&
nodedata->enveloptheta == leftdata->enveloptheta + rightdata->energytheta )
6214 assert(rightdata->enveloptheta != -1);
6260 assert(rightdata->energytheta != -1);
6262 if( leftdata->energylambda >= 0 &&
nodedata->energylambda == leftdata->energylambda + rightdata->energytheta )
6269 assert(leftdata->energytheta != -1);
6270 assert(rightdata->energylambda != -1);
6271 assert(
nodedata->energylambda == leftdata->energytheta + rightdata->energylambda);
6320 assert(rightdata->energytheta != -1);
6322 if( leftdata->enveloplambda >= 0 &&
nodedata->enveloplambda == leftdata->enveloplambda + rightdata->energytheta )
6329 if( leftdata->enveloptheta >= 0 && rightdata->energylambda >= 0
6330 &&
nodedata->enveloplambda == leftdata->enveloptheta + rightdata->energylambda )
6337 assert(rightdata->enveloplambda != -1);
6360 SCIPdebugMessage(
"variable <%s>: loc=[%g,%g] glb=[%g,%g] (duration %d, demand %d)\n",
6365 return nodedata->demand * duration;
6378 return (est1 - est2);
6388 return (nodedatas[ind1].lct - nodedatas[ind2].lct);
6419 SCIPdebugMsg(
scip,
"est=%d, lct=%d, propest %u, reportedenergy %d, shift %d\n", est, lct, propest, reportedenergy, shift);
6430 for( j = 0; j < nleaves && reportedenergy <= energy; ++j )
6446 assert(reportedenergy > energy);
6474 for( j = nleaves-1; j >= 0; --j )
6494 if( explanation !=
NULL )
6498 (*initialized) =
TRUE;
6566 for( j = ncands-1; j >= 0 && !(*cutoff); --j )
6597 assert(!leafdata->intheta);
6598 assert(leafdata->duration > 0);
6599 assert(leafdata->est >= 0);
6602 if( leafdata->est + leafdata->duration >=
nodedata->lct )
6624 assert(nelements < ncands);
6631 SCIPdebugMsg(
scip,
"an overload was detected duration edge-finder propagattion\n");
6635 conshdlrdata->usebdwidening, initialized, explanation) );
6641 else if( newest > 0 )
6663 TRUE, &infeasible, &tightened) );
6685 TRUE, &infeasible, &tightened) );
6695 leafdata->est = newest;
6714 if( explanation !=
NULL )
6715 explanation[leafdata->idx] =
TRUE;
6718 for(
i = 0;
i < nelements; ++
i )
6726 if( explanation !=
NULL )
6730 (*initialized) =
TRUE;
6824 for( j = 0; j <
nvars; ++j )
6829 shift =
MAX(shift, lct);
6836 for( j = 0; j <
nvars; ++j )
6850 duration = durations[j];
6862 if( conshdlrdata->useadjustedjobs )
6866 leftadjust = (hmin - est);
6871 rightadjust = (lct - hmax);
6878 if( duration - leftadjust - rightadjust <= 0 )
6881 else if( est < hmin || lct > hmax )
6884 energy = demands[j] * (duration - leftadjust - rightadjust);
6887 totalenergy += energy;
6910 nodedataidx[ncands] = ncands;
6922 nodedata->rightadjust = rightadjust;
6937 nnodedatas = ncands;
6940 SCIPsortInd(nodedataidx, compNodedataLct, (
void*)nodedatas, ncands);
6947 for( j = 0; j < ncands; ++j )
6952 idx = nodedataidx[j];
6957 if( ((
SCIP_Longint) nodedatas[idx].lct - nodedatas[idx].est) * capacity >= totalenergy )
6960 nodedatas[idx].est = -1;
6972 leaves[ninsertcands] = leaf;
6980 if( rootdata->enveloptheta > (
SCIP_Longint) capacity * nodedatas[idx].lct )
6982 SCIPdebugMsg(
scip,
"detects cutoff due to overload in time window [?,%d) (ncands %d)\n", nodedatas[idx].lct, j);
7001 est = nodedatas[idx].est;
7002 lct = nodedatas[idx].lct;
7007 for( j = j+1; j < ncands; ++j )
7014 idx = nodedataidx[j];
7026 duration -= (est - glbest);
7029 duration -= (glblct - lct);
7033 glbenery +=
nodedata->demand * duration;
7035 if( explanation !=
NULL )
7042 conshdlrdata->usebdwidening, initialized, explanation) );
7044 else if( ninsertcands > 1 && conshdlrdata->efinfer )
7048 propest, shift, initialized, explanation, nchgbds,
cutoff) );
7091 if( !conshdlrdata->efcheck )
7096 cons,
TRUE, initialized, explanation, nchgbds,
cutoff) );
7103 if( !conshdlrdata->efinfer )
7108 cons,
FALSE, initialized, explanation, nchgbds,
cutoff) );
7147 (*redundant) =
TRUE;
7163 for( j = 0; j <
nvars; ++j )
7165 assert(durations[j] > 0);
7175 if( lb >= hmax || ub <= hmin - durations[j] )
7178 starttimes[njobs] =
MAX(lb, hmin);
7179 startindices[njobs] = j;
7181 endtimes[njobs] =
MIN(ub == INT_MAX ? ub : ub + durations[j], hmax);
7182 endindices[njobs] = j;
7183 assert(starttimes[njobs] <= endtimes[njobs]);
7192 freecapacity = capacity;
7195 for( j = 0; j < njobs; ++j )
7197 curtime = starttimes[j];
7200 if( curtime >= hmax )
7204 freecapacity -= demands[startindices[j]];
7205 while( j+1 < njobs && starttimes[j+1] == curtime )
7208 freecapacity -= demands[startindices[j]];
7212 while( endtimes[endindex] <= curtime )
7214 freecapacity += demands[endindices[endindex]];
7217 assert(freecapacity <= capacity);
7220 if( freecapacity < 0 && curtime >= hmin )
7222 (*redundant) =
FALSE;
7259 for( v = 0; v <
nvars; ++v )
7276 duration = durations[v];
7279 demand = demands[v];
7287 if( lst + duration <= hmin || est >= hmax )
7291 begin =
MAX(hmin, lst);
7292 end =
MIN(hmax, est + duration);
7298 SCIPdebugMsg(
scip,
"variable <%s>[%d,%d] (duration %d, demand %d): add core [%d,%d)\n",
7312 var, duration, demand,
SCIPprofileGetTime(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) );
7314 if( explanation !=
NULL )
7315 explanation[v] =
TRUE;
7371 SCIP_CALL_TERMINATE( retcode,
createCoreProfile(
scip, conshdlrdata, profile,
nvars,
vars, durations, demands, capacity, hmin, hmax,
7372 initialized, explanation,
cutoff), TERMINATE );
7377 SCIP_CALL_TERMINATE( retcode,
propagateTimetable(
scip, conshdlrdata, profile,
nvars,
vars, durations, demands, capacity, hmin, hmax, cons,
7378 nchgbds, initialized, explanation,
cutoff), TERMINATE );
7384 SCIP_CALL_TERMINATE( retcode,
propagateEdgeFinding(
scip, conshdlrdata,
nvars,
vars, durations, demands, capacity, hmin, hmax,
7385 cons, initialized, explanation, nchgbds,
cutoff), TERMINATE );
7391 SCIP_CALL_TERMINATE( retcode,
propagateTTEF(
scip, conshdlrdata, profile,
nvars,
vars, durations, demands, capacity, hmin, hmax, cons,
7392 nchgbds, initialized, explanation,
cutoff), TERMINATE );
7424 oldnchgbds = *nchgbds;
7425 initialized =
FALSE;
7439 consdata->nvars, consdata->vars, consdata->durations, consdata->demands, consdata->capacity,
7440 consdata->hmin, consdata->hmax, cons,
7441 nchgbds, &redundant, &initialized,
NULL,
cutoff) );
7445 SCIPdebugMsg(
scip,
"%s deletes cumulative constraint <%s> since it is redundant\n",
7465 if( *
cutoff || *nchgbds > oldnchgbds )
7472 consdata->propagated =
TRUE;
7526 leftimpllbs, leftimplubs, leftproplbs, leftpropubs,
cutoff) );
7561 rightimpllbs, rightimplubs, rightproplbs, rightpropubs,
cutoff) );
7689 int* alternativelbs,
7690 int* alternativeubs,
7699 for(
c = 0;
c < nconss; ++
c )
7716 assert(consdata->nvars > 1);
7741 hmin = consdata->hmin;
7742 hmax = consdata->hmax;
7748 nvars = consdata->nvars;
7750 for( v = 0; v <
nvars; ++v )
7756 var = consdata->vars[v];
7771 if( consdata->downlocks[v] )
7778 ect = est + consdata->durations[v];
7780 if( ect <= hmin || hmin >= hmax )
7782 else if( est < hmin && alternativelbs[idx] >= (hmin + 1 - constant) / scalar )
7784 alternativelbs[idx] = (hmin + 1 - constant) / scalar;
7790 if( consdata->uplocks[v] )
7796 duration = consdata->durations[v];
7800 lct = lst + duration;
7802 if( lst >= hmax || hmin >= hmax )
7804 else if( lct > hmax && alternativeubs[idx] <= ((hmax - 1 - constant) / scalar) - duration )
7806 alternativeubs[idx] = ((hmax - 1 - constant) / scalar) - duration;
7822 int* alternativelbs,
7823 int* alternativeubs,
7850 for( v = 0; v <
nvars; ++v )
7863 if( alternativelbs[v] == INT_MAX && alternativeubs[v] == INT_MIN )
7879 if( alternativelbs[v] > ub )
7901 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
7902 nfixedvars, &success,
cutoff) );
7925 if( alternativeubs[v] < lb )
7947 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
7948 nfixedvars, &success,
cutoff) );
7987 int* alternativelbs;
7988 int* alternativeubs;
7997 oldnfixedvars = *nfixedvars;
8006 for( v = 0; v <
nvars; ++v )
8010 alternativelbs[v] = INT_MAX;
8011 alternativeubs[v] = INT_MIN;
8021 if( !(*
cutoff) && oldnfixedvars == *nfixedvars && branched !=
NULL )
8074 nvars = consdata->nvars;
8081 remainingcap = consdata->capacity;
8084 for( j = 0; j <
nvars; ++j )
8091 if( startvalues[j] <= time && ub + consdata->durations[j] > time )
8094 if( startvalues[j] == ub )
8096 remainingcap -= consdata->demands[j];
8100 demands[nflexible] = consdata->demands[j];
8101 flexibleids[nflexible] = j;
8106 assert(remainingcap >= 0);
8122 while( j < nflexible && sumdemand <= remainingcap )
8124 sumdemand += demands[j];
8130 assert(sumdemand > remainingcap);
8131 assert(bigcoversize < nflexible);
8143 for( j = 0; j < nflexible; ++j )
8155 idx = flexibleids[j];
8168 start = time - consdata->durations[idx] + 1;
8169 end =
MIN(time, ub);
8172 for(
b = 0;
b < nbinvars; ++
b )
8174 if( vals[
b] < start || vals[
b] < lb )
8188 if( consdata->bcoverrowssize == 0 )
8190 consdata->bcoverrowssize = 10;
8193 if( consdata->nbcoverrows == consdata->bcoverrowssize )
8195 consdata->bcoverrowssize *= 2;
8199 consdata->bcoverrows[consdata->nbcoverrows] = row;
8200 consdata->nbcoverrows++;
8210 while( sumdemand <= remainingcap )
8213 sumdemand += demands[j];
8217 smallcoversize = nflexible - (j + 1) - 1;
8218 while( j > 0 && demands[j] == demands[nflexible-1] )
8221 assert(smallcoversize < nflexible);
8223 if( smallcoversize != 1 || smallcoversize != nflexible - (j + 1) - 1 )
8232 for( j = j + 1; j < nflexible; ++j )
8244 idx = flexibleids[j];
8257 start = time - consdata->durations[idx] + 1;
8258 end =
MIN(time, ub);
8261 for(
b = 0;
b < nbinvars; ++
b )
8263 if( vals[
b] < start || vals[
b] < lb )
8276 if( consdata->scoverrowssize == 0 )
8278 consdata->scoverrowssize = 10;
8281 if( consdata->nscoverrows == consdata->scoverrowssize )
8283 consdata->scoverrowssize *= 2;
8287 consdata->scoverrows[consdata->nscoverrows] = row;
8288 consdata->nscoverrows++;
8309 int* startvaluessorted;
8310 int* endvaluessorted;
8332 if( consdata->vars ==
NULL )
8335 nvars = consdata->nvars;
8336 hmin = consdata->hmin;
8337 hmax = consdata->hmax;
8347 for ( j = 0; j <
nvars; ++j )
8350 startvaluessorted[j] = startvalues[j];
8353 endvaluessorted[j] = endvalues[j];
8355 startindices[j] = j;
8365 freecapacity = consdata->capacity;
8368 for( j = 0; j <
nvars; ++j )
8370 curtime = startvaluessorted[j];
8371 if( curtime >= hmax )
8375 freecapacity -= consdata->demands[startindices[j]];
8377 while( j+1 <
nvars && startvaluessorted[j+1] == curtime )
8380 freecapacity -= consdata->demands[startindices[j]];
8384 while( endidx < nvars && curtime >= endvaluessorted[endidx] )
8386 freecapacity += consdata->demands[endindices[endidx]];
8390 assert(freecapacity <= consdata->capacity);
8400 if( freecapacity < 0 && curtime >= hmin )
8402 int nextprofilechange;
8406 nextprofilechange =
MIN( startvaluessorted[j+1], endvaluessorted[endidx] );
8408 nextprofilechange = endvaluessorted[endidx];
8410 nextprofilechange =
MIN(nextprofilechange, hmax);
8412 for( t = curtime; t < nextprofilechange; ++t )
8422 consdata->covercuts =
TRUE;
8457 assert(nstarted > nfinished);
8461 assert(consdata->nvars > 0);
8463 capacity = consdata->capacity;
8480 for(
b = 0;
b < nbinvars; ++
b )
8496 for(
b = 0;
b < nbinvars; ++
b )
8504 if( consdata->demandrowssize == 0 )
8506 consdata->demandrowssize = 10;
8509 if( consdata->ndemandrows == consdata->demandrowssize )
8511 consdata->demandrowssize *= 2;
8515 consdata->demandrows[consdata->ndemandrows] = row;
8516 consdata->ndemandrows++;
8558 nvars = consdata->nvars;
8571 SCIPdebugMsg(
scip,
"create sorted event points for cumulative constraint <%s> with %d jobs\n",
8576 starttimes, endtimes, startindices, endindices,
FALSE);
8579 freecapacity = consdata->capacity;
8580 hmin = consdata->hmin;
8581 hmax = consdata->hmax;
8584 for( j = 0; j <
nvars; ++j )
8586 curtime = starttimes[j];
8589 if( curtime >= hmax )
8598 assert(freecapacity <= consdata->capacity);
8605 if( freecapacity < 0 && curtime >= hmin )
8612 nextstarttime = starttimes[j+1];
8614 nextstarttime = endtimes[
nvars-1];
8616 nextstarttime =
MIN(nextstarttime, hmax);
8623 for( t = curtime+1 ; t < nextstarttime; ++t )
8628 if( freecapacity < 0 )
8671 assert(consdata->ndemandrows == 0);
8674 if( consdata->linkingconss ==
NULL )
8716 if( consdata->demandrows ==
NULL )
8718 assert(consdata->ndemandrows == 0);
8725 for(
r = 0;
r < consdata->ndemandrows && !(*infeasible); ++
r )
8764 if( consdata->demandrows ==
NULL )
8766 assert(consdata->ndemandrows == 0);
8776 for(
r = 0;
r < consdata->ndemandrows; ++
r )
8807 (*separated) =
TRUE;
8842 if( consdata->linkingconss ==
NULL )
8847 if( !consdata->covercuts )
8856 for(
r = 0;
r < consdata->nscoverrows; ++
r )
8868 if( minfeasibility > feasibility )
8870 minfeasibility = feasibility;
8871 row = consdata->scoverrows[
r];
8880 SCIPdebugMsg(
scip,
"cumulative constraint <%s> separated 1 cover cut with feasibility %g\n",
8887 (*separated) =
TRUE;
8894 for(
r = 0;
r < consdata->nbcoverrows; ++
r )
8906 if( minfeasibility > feasibility )
8908 minfeasibility = feasibility;
8909 row = consdata->bcoverrows[
r];
8918 SCIPdebugMsg(
scip,
"cumulative constraint <%s> separated 1 cover cut with feasibility %g\n",
8926 (*separated) =
TRUE;
8954 assert(nstarted > nfinished);
8958 assert(consdata->nvars > 0);
8980 for( v = 0; v < nstarted - nfinished; ++v )
9031 nvars = consdata->nvars;
9044 SCIPdebugMsg(
scip,
"create sorted event points for cumulative constraint <%s> with %d jobs\n",
9053 freecapacity = consdata->capacity;
9054 hmin = consdata->hmin;
9055 hmax = consdata->hmax;
9058 for( j = 0; j <
nvars && !(*cutoff); ++j )
9060 curtime = starttimes[j];
9062 if( curtime >= hmax )
9071 assert(freecapacity <= consdata->capacity);
9078 if( freecapacity < 0 && curtime >= hmin)
9124 nvars = consdata->nvars;
9131 capacity = consdata->capacity;
9134 for ( j = 0; j <
nvars; ++j )
9136 if( consdata->demands[j] > capacity )
9164 if( consdata->nvars == 0 )
9171 else if( consdata->nvars == 1 )
9173 if( consdata->demands[0] > consdata->capacity )
9212 hmin = consdata->hmin;
9213 hmax = consdata->hmax;
9215 SCIPdebugMsg(
scip,
"check for irrelevant jobs within cumulative constraint <%s>[%d,%d)\n",
9218 for( j = consdata->nvars-1; j >= 0; --j )
9220 var = consdata->vars[j];
9221 demand = consdata->demands[j];
9222 duration = consdata->durations[j];
9228 if( demand == 0 || duration == 0 )
9237 else if( est >= hmax || lct <= hmin )
9273 assert(consdata->durations[pos] > 0);
9274 assert(consdata->demands[pos] > 0);
9276 var = consdata->vars[pos];
9278 duration = consdata->durations[pos];
9281 SCIPdebugMsg(
scip,
" variable <%s>: demand <%d> is larger than the capacity <%d>\n",
9289 if( ect - duration >= consdata->hmax || lst + duration <= consdata->hmin)
9292 if( ect > consdata->hmin && lst < consdata->hmax )
9297 else if( lst < consdata->hmax )
9305 else if( ect > consdata->hmin )
9330 leftbound = consdata->hmin - duration;
9331 rightbound = consdata->hmax;
9381 capacity = consdata->capacity;
9383 for( j = consdata->nvars-1; j >= 0 && !(*
cutoff); --j )
9385 if( consdata->demands[j] > capacity )
9515 if( *capacity == 1 ||
nvars <= 1 )
9525 for( v =
nvars-2; v >= 0 && (gcd >= 2 || mindemand1 + mindemand2 > *capacity); --v )
9527 assert(mindemand1 <= mindemand2);
9528 assert(demands[v] <= *capacity);
9532 if( mindemand1 > demands[v] )
9534 mindemand2 = mindemand1;
9535 mindemand1 = demands[v];
9537 else if( mindemand2 > demands[v] )
9538 mindemand2 = demands[v];
9541 if( mindemand1 + mindemand2 > *capacity )
9543 SCIPdebugMsg(
scip,
"update cumulative condition (%d + %d > %d) to unary cumulative condition\n", mindemand1, mindemand2, *capacity);
9545 for( v = 0; v <
nvars; ++v )
9550 (*nchgcoefs) +=
nvars;
9557 for( v = 0; v <
nvars; ++v )
9558 demands[v] /= (
int) gcd;
9560 (*capacity) /= (int) gcd;
9562 (*nchgcoefs) +=
nvars;
9589 if( consdata->normalized )
9592 capacity = consdata->capacity;
9598 consdata->normalized =
TRUE;
9600 if( capacity > consdata->capacity )
9601 consdata->varbounds =
FALSE;
9657 for( t = 0; t < ntimepoints; ++t )
9660 if( timepoints[t] <= *hmin )
9664 if( timepoints[t] >= *hmax )
9670 if( loads[t] <= capacity )
9672 (*split) = timepoints[t];
9725 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
9756 if( consdata->nvars <= 1 )
9760 consdata->durations, consdata->demands, consdata->capacity, &hmin, &hmax, &split) );
9763 if( consdata->hmin < hmin )
9767 consdata->hmin = hmin;
9772 if( consdata->hmax > hmax )
9775 consdata->hmax = hmax;
9780 if( consdata->hmax <= consdata->hmin )
9782 SCIPdebugMsg(
scip,
"constraint <%s> is redundant since hmax(%d) <= hmin(%d)\n",
9788 else if( consdata->hmin < split && split < consdata->hmax )
9793 SCIPdebugMsg(
scip,
"split cumulative constraint <%s>[%d,%d) with %d jobs at time point %d\n",
9794 SCIPconsGetName(cons), consdata->hmin, consdata->hmax, consdata->nvars, split);
9796 assert(split < consdata->hmax);
9800 consdata->durations, consdata->demands, consdata->capacity, split, consdata->hmax,
9805 consdata->hmax = split;
9807 assert(consdata->hmin < consdata->hmax);
9887 SCIPdebugMsg(
scip,
"check for irrelevant variable for cumulative condition (hmin %d) w.r.t. earlier start time\n", hmin);
9889 firstminect = INT_MAX;
9890 secondminect = INT_MAX;
9893 for( v = 0; v <
nvars; ++v )
9899 if( ect < firstminect )
9901 secondminect = firstminect;
9904 else if( ect < secondminect )
9909 for( v = 0; v <
nvars; ++v )
9924 duration = durations[v];
9931 ect = est + duration;
9933 lct = lst + duration;
9936 if( ect == firstminect )
9937 minect = secondminect;
9939 minect = firstminect;
9942 alternativelb =
MAX(hmin+1, minect);
9943 alternativelb =
MIN(alternativelb, hmax);
9950 SCIPdebugMsg(
scip,
" variable <%s>[%g,%g] with duration <%d> is irrelevant\n",
9954 irrelevants[v] =
TRUE;
9977 SCIPdebugMsg(
scip,
" variables <%s>[%d,%d] (duration <%d>) is irrelevant due to no up lock\n",
9981 irrelevants[v] =
TRUE;
9989 SCIPdebugMsg(
scip,
" remove down lock of variable <%s>[%g,%g] with duration <%d>\n",
9993 downlocks[v] =
FALSE;
10000 else if( ect <= hmin )
10018 SCIPdebugMsg(
scip,
" variable <%s>[%d,%d] with duration <%d> is irrelevant due to dual fixing wrt EST\n",
10025 irrelevants[v] =
TRUE;
10048 if( alternativelb > lst )
10073 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
10074 nfixedvars, &success,
cutoff) );
10085 SCIPdebugMsg(
scip,
"********* check variable <%s>[%g,%g] with duration <%d> (hmin %d)\n",
10172 SCIPdebugMsg(
scip,
"check for irrelevant variable for cumulative condition (hmax %d) w.r.t. latest completion time\n", hmax);
10174 firstmaxlst = INT_MIN;
10175 secondmaxlst = INT_MIN;
10178 for( v = 0; v <
nvars; ++v )
10184 if( lst > firstmaxlst )
10186 secondmaxlst = firstmaxlst;
10189 else if( lst > secondmaxlst )
10190 secondmaxlst = lst;
10194 for( v = 0; v <
nvars; ++v )
10208 duration = durations[v];
10215 ect = est + duration;
10219 if( lst == firstmaxlst )
10220 maxlst = secondmaxlst;
10222 maxlst = firstmaxlst;
10225 alternativeub =
MIN(hmax - 1, maxlst) - duration;
10226 alternativeub =
MAX(alternativeub, hmin);
10233 SCIPdebugMsg(
scip,
" variable <%s>[%g,%g] with duration <%d> is irrelevant\n",
10237 irrelevants[v] =
TRUE;
10251 if( !downlocks[v] )
10257 SCIPdebugMsg(
scip,
" variables <%s>[%d,%d] with duration <%d> is irrelevant due to no down lock\n",
10261 irrelevants[v] =
TRUE;
10269 SCIPdebugMsg(
scip,
" remove up lock of variable <%s>[%g,%g] with duration <%d>\n",
10273 uplocks[v] =
FALSE;
10280 else if( lst >= hmax )
10298 SCIPdebugMsg(
scip,
" variable <%s>[%d,%d] with duration <%d> is irrelevant due to dual fixing wrt LCT\n",
10305 irrelevants[v] =
TRUE;
10328 if( alternativeub < est )
10353 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
10354 nfixedvars, &success,
cutoff) );
10402 nvars = consdata->nvars;
10412 consdata->hmin, consdata->hmax, consdata->downlocks, consdata->uplocks, cons,
10413 irrelevants, nfixedvars, nchgsides,
cutoff) );
10417 consdata->hmin, consdata->hmax, consdata->downlocks, consdata->uplocks, cons,
10418 irrelevants, nfixedvars, nchgsides,
cutoff) );
10423 for( v =
nvars-1; v >= 0; --v )
10425 if( irrelevants[v] )
10431 var = consdata->vars[v];
10438 if( lst <= consdata->hmin && ect >= consdata->hmax )
10440 if( consdata->capacity < consdata->demands[v] )
10446 consdata->capacity -= consdata->demands[v];
10447 consdata->varbounds =
FALSE;
10480 startindex = nstarted - 1;
10485 while( nstarted - nfinished > ncountedvars )
10492 varidx = startindices[startindex];
10501 if( endtime > curtime )
10503 if( consdata->demands[
varidx] < consdata->capacity )
10505 (*demands)[*ndemands] = consdata->demands[
varidx];
10537 assert(nstarted > nfinished);
10541 assert(consdata->nvars > 0);
10542 assert(consdata->capacity > 0);
10548 collectDemands(
scip, consdata, startindices, curtime, nstarted, nfinished, &demands, &ndemands);
10553 for( j = 0; j < ndemands; ++j )
10609 nvars = consdata->nvars;
10617 SCIPdebugMsg(
scip,
"try to tighten capacity for cumulative constraint <%s> with capacity %d\n",
10627 starttimes, endtimes, startindices, endindices,
FALSE);
10631 freecapacity = consdata->capacity;
10634 for( j = 0; j <
nvars && bestcapacity < consdata->capacity; ++j )
10636 curtime = starttimes[j];
10645 assert(freecapacity <= consdata->capacity);
10652 if( freecapacity < 0 )
10662 bestcapacity =
MAX(bestcapacity, newcapacity);
10663 SCIPdebugMsg(
scip,
"after highest cap usage: bestcapacity = %d\n", bestcapacity);
10667 if( freecapacity > 0 && freecapacity != consdata->capacity )
10669 bestcapacity =
MAX(bestcapacity, consdata->capacity - freecapacity);
10670 SCIPdebugMsg(
scip,
"after peak < cap: bestcapacity = %d\n", bestcapacity);
10674 if( freecapacity == 0 && consdata->demands[startindices[j]] < consdata->capacity)
10677 SCIPdebugMsg(
scip,
"--> cannot decrease capacity since sum equals capacity\n");
10678 bestcapacity = consdata->capacity;
10690 if( bestcapacity < consdata->capacity )
10692 SCIPdebug(
int oldnchgcoefs = *nchgcoefs; )
10694 SCIPdebugMsg(
scip,
"+-+-+-+-+-+ --> CHANGE capacity of cons<%s> from %d to %d\n",
10697 for( j = 0; j <
nvars; ++j )
10699 if( consdata->demands[j] == consdata->capacity )
10701 consdata->demands[j] = bestcapacity;
10706 consdata->capacity = bestcapacity;
10711 consdata->varbounds =
FALSE;
10743 nvars = consdata->nvars;
10744 oldnchgcoefs = *nchgcoefs;
10753 mindemand = consdata->demands[0];
10754 for( j = 0; j <
nvars; ++j )
10756 mindemand =
MIN(mindemand, consdata->demands[j]);
10760 for( j = 0; j <
nvars; ++j )
10762 if( mindemand + consdata->demands[j] > consdata->capacity && consdata->demands[j] < consdata->capacity )
10765 consdata->demands[j], consdata->capacity);
10766 consdata->demands[j] = consdata->capacity;
10775 for( j = 0; j <
nvars; ++j )
10782 assert(consdata->demands[j] <= consdata->capacity);
10784 if( consdata->demands[j] == consdata->capacity )
10803 if( est_i >= lct_j || est_j >= lct_i )
10806 if( consdata->demands[j] + consdata->demands[
i] <= consdata->capacity )
10816 consdata->demands[j], consdata->capacity);
10817 consdata->demands[j] = consdata->capacity;
10822 if( (*nchgcoefs) > oldnchgcoefs )
10824 SCIPdebugMsg(
scip,
"+-+-+-+-+-+changed %d coefficients of variables of cumulative constraint<%s>\n",
10831#ifdef SCIP_DISABLED_CODE
10851 nvars = consdata->nvars;
10854 hmin = consdata->hmin;
10855 hmax = consdata->hmax;
10858 for( v = 0; v <
nvars; ++v )
10867 var = consdata->vars[v];
10870 duration = consdata->durations[v];
10873 ect = est + duration;
10875 lct = lst + duration;
10878 assert(lst > hmin || ect < hmax);
10880 if( lst <= hmin && est < hmin - lct +
MIN(hmin, ect) )
10889 shift = est - (hmin - lct +
MIN(hmin, ect));
10892 duration = hmin - lct;
10908 consdata->durations[v] = duration;
10909 consdata->vars[v] = aggrvar;
10946 capacity = consdata->capacity;
10948 if( capacity == 1 )
10955 halfcapacity = capacity / 2;
10956 mindemand = consdata->capacity;
10960 for( v = 0; v < consdata->nvars; ++v )
10962 if( consdata->demands[v] > halfcapacity )
10965 demands[
nvars] = 1;
10966 durations[
nvars] = consdata->durations[v];
10969 mindemand =
MIN(mindemand, consdata->demands[v]);
10978 for( v = 0; v < consdata->nvars; ++v )
10980 if( consdata->demands[v] > halfcapacity )
10983 if( mindemand + consdata->demands[v] > capacity )
10985 demands[
nvars] = 1;
10986 durations[
nvars] = consdata->durations[v];
11060 if( conshdlrdata->normalize )
11072 if( conshdlrdata->coeftightening )
11083#ifdef SCIP_DISABLED_CODE
11097struct TCLIQUE_Graph
11117 return tcliquegraph->nnodes;
11126 return tcliquegraph->weights;
11138 if( tcliquegraph->precedencematrix[node1][node2] || tcliquegraph->precedencematrix[node2][node1] )
11142 if( tcliquegraph->demandmatrix[node1][node2] )
11167 assert(0 <= nodes[
i] && nodes[
i] < tcliquegraph->nnodes);
11168 assert(
i == 0 || nodes[
i-1] < nodes[
i]);
11171 if( tcliqueIsedgeClique(tcliquegraph, node, nodes[
i]) )
11174 adjnodes[nadjnodes] = nodes[
i];
11220 bound = (duration - vlbcoef) / (vlbcoef - 1.0);
11267 vlbcoef = 1.0 / vubcoef;
11268 vlbconst = -vubconst / vubcoef;
11300 if( tcliquegraph->size == tcliquegraph->nnodes )
11305 tcliquegraph->size = size;
11313 for( v = 0; v < tcliquegraph->nnodes; ++v )
11319 assert(tcliquegraph->nnodes < tcliquegraph->size);
11321 pos = tcliquegraph->nnodes;
11324 tcliquegraph->durations[pos] = 0;
11325 tcliquegraph->weights[pos] = 0;
11326 tcliquegraph->vars[pos] =
var;
11336 tcliquegraph->nnodes++;
11338 for( v = 0; v < tcliquegraph->nnodes; ++v )
11340 tcliquegraph->precedencematrix[v][pos] = 0;
11341 tcliquegraph->demandmatrix[v][pos] = 0;
11344 (*idx) = tcliquegraph->nnodes;
11381 for( v = 0; v <
nvars; ++v )
11397 if( tcliquegraph->durations[idx1] == 0 )
11405 for(
b = 0;
b < nvbdvars; ++
b )
11412 if( tcliquegraph->durations[idx2] == 0 )
11416 tcliquegraph->precedencematrix[idx2][idx1] =
TRUE;
11424 for(
b = 0;
b < nvbdvars; ++
b )
11431 if( tcliquegraph->durations[idx2] == 0 )
11435 tcliquegraph->precedencematrix[idx1][idx2] =
TRUE;
11445 if( tcliquegraph->durations[idx2] == 0 )
11450 tcliquegraph->precedencematrix[idx1][idx2] =
TRUE;
11454 tcliquegraph->precedencematrix[idx2][idx1] =
TRUE;
11476 for( j = 0; j <
nnodes; ++j )
11478 if( adjmatrix[
i][j] )
11483 for( k = 0; k <
nnodes; ++k )
11485 if( adjmatrix[j][k] )
11486 adjmatrix[
i][k] =
TRUE;
11505 for(
c = 0;
c < nconss; ++
c )
11517 vars = consdata->vars;
11518 demands = consdata->demands;
11520 nvars = consdata->nvars;
11521 capacity = consdata->capacity;
11534 if( tcliquegraph->durations[idx1] == 0 || tcliquegraph->durations[idx1] > consdata->durations[
i] )
11537 for( j =
i+1; j <
nvars; ++j )
11539 assert(consdata->durations[j] > 0);
11541 if( demands[
i] + demands[j] > capacity )
11554 if( est1 < consdata->hmin && est2 < consdata->hmin )
11561 if( lct1 > consdata->hmax && lct2 > consdata->hmax )
11568 if( tcliquegraph->durations[idx2] == 0 || tcliquegraph->durations[idx2] > consdata->durations[j] )
11573 assert(tcliquegraph->durations[idx1] > 0);
11574 assert(tcliquegraph->durations[idx2] > 0);
11576 tcliquegraph->demandmatrix[idx1][idx2] =
TRUE;
11577 tcliquegraph->demandmatrix[idx2][idx1] =
TRUE;
11604 transitiveClosure(tcliquegraph->precedencematrix, tcliquegraph->ninarcs, tcliquegraph->noutarcs, tcliquegraph->nnodes);
11635 for( v = 0; v < ncliquenodes; ++v )
11637 durations[v] = tcliquegraph->durations[cliquenodes[v]];
11638 assert(durations[v] > 0);
11640 vars[v] = tcliquegraph->vars[cliquenodes[v]];
11680 nnodes = tcliquegraph->nnodes;
11684 for( v = 0; v <
nnodes; ++v )
11686 tcliquegraph->weights[v] = tcliquegraph->durations[v];
11697 SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal,
NULL) );
11706 if( tcliquegraph->durations[v] == 0 )
11718 precedencerow[
c] = tcliquegraph->precedencematrix[v][
c];
11719 precedencecol[
c] = tcliquegraph->precedencematrix[
c][v];
11721 demandrow[
c] = tcliquegraph->demandmatrix[v][
c];
11722 demandcol[
c] = tcliquegraph->demandmatrix[
c][v];
11724 tcliquegraph->precedencematrix[
c][v] =
FALSE;
11725 tcliquegraph->precedencematrix[v][
c] =
FALSE;
11729 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,
11730 tcliquegraph, tcliqueNewsolClique,
NULL,
11731 cliquenodes, &ncliquenodes, &cliqueweight, 1, 1,
11732 10000, 1000, 1000, v, &ntreenodes, &tcliquestatus);
11734 SCIPdebugMsg(
scip,
"tree nodes %d clique size %d (weight %d, status %d)\n", ntreenodes, ncliquenodes, cliqueweight, tcliquestatus);
11736 if( ncliquenodes == 1 )
11746 for(
c = 0;
c < ncliquenodes; ++
c )
11754 tcliquegraph->precedencematrix[v][
c] = precedencerow[
c];
11755 tcliquegraph->precedencematrix[
c][v] = precedencecol[
c];
11757 tcliquegraph->demandmatrix[v][
c] = demandrow[
c];
11758 tcliquegraph->demandmatrix[
c][v] = demandcol[
c];
11770 (*naddconss) += nconss;
11826 if( !tcliquegraph->precedencematrix[source][sink] )
11829 nnodes = tcliquegraph->nnodes;
11830 vars = tcliquegraph->vars;
11848 duration = tcliquegraph->durations[
i];
11850 if(
i == source ||
i == sink )
11853 tcliquegraph->weights[
i] = 0;
11855 else if( tcliquegraph->precedencematrix[source][
i] && tcliquegraph->precedencematrix[
i][sink] )
11858 tcliquegraph->weights[
i] = duration;
11864 tcliquegraph->weights[
i] = duration;
11867 tcliquegraph->weights[
i] = 0;
11873 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,
11874 tcliquegraph, tcliqueNewsolClique,
NULL,
11875 cliquenodes, &ncliquenodes, &cliqueweight, 1, 1,
11876 10000, 1000, 1000, -1, &ntreenodes, &tcliquestatus);
11878 if( ncliquenodes > 1 )
11889 distance = cliqueweight + tcliquegraph->durations[source];
11920 nnodes = tcliquegraph->nnodes;
11932 if( tcliquegraph->ninarcs[
i] == 0 )
11934 sources[nsources] =
i;
11938 if( tcliquegraph->noutarcs[
i] == 0 )
11961 (*naddconss) += nconss;
11984 for(
c = 0;
c < nconss; ++
c )
11994 vars = consdata->vars;
11995 nvars = consdata->nvars;
11997 for( v = 0; v <
nvars; ++v )
12008 tcliquegraph->durations[idx] =
MAX(tcliquegraph->durations[idx], consdata->durations[v]);
12009 assert(tcliquegraph->durations[idx] > 0);
12066 for( v = 0; v <
nvars; ++v )
12084 (*tcliquegraph)->nnodes =
nvars;
12085 (*tcliquegraph)->varmap = varmap;
12086 (*tcliquegraph)->precedencematrix = precedencematrix;
12087 (*tcliquegraph)->demandmatrix = demandmatrix;
12088 (*tcliquegraph)->weights = weights;
12089 (*tcliquegraph)->ninarcs = ninarcs;
12090 (*tcliquegraph)->noutarcs = noutarcs;
12091 (*tcliquegraph)->durations = durations;
12092 (*tcliquegraph)->size =
nvars;
12106 for( v = (*tcliquegraph)->nnodes-1; v >= 0; --v )
12148 if( conshdlrdata->detectvarbounds )
12154 if( conshdlrdata->detectdisjunctive )
12175 if( consdata->validsignature )
12178 vars = consdata->vars;
12179 nvars = consdata->nvars;
12181 for( v = 0; v <
nvars; ++v )
12183 consdata->signature |= ((
unsigned int)1 << ((
unsigned int)
SCIPvarGetIndex(
vars[v]) % (
sizeof(
unsigned int) * 8)));
12186 consdata->validsignature =
TRUE;
12199 return SCIPvarCompare(consdata->vars[ind1], consdata->vars[ind2]);
12214 for(
i = 0;
i < nconss; ++
i )
12226 assert(consdata0->validsignature);
12228 for( j =
i+1; j < nconss; ++j )
12239 if( consdata0->capacity != consdata1->capacity )
12243 assert(consdata1->validsignature);
12245 if( (consdata1->signature & (~consdata0->signature)) == 0 )
12249 assert((consdata0->signature & (~consdata1->signature)) == 0);
12252 if( (consdata0->signature & (~consdata1->signature)) == 0 )
12259 if( consdata0->nvars > consdata1->nvars )
12262 if( consdata0->hmin < consdata1->hmin )
12265 if( consdata0->hmax > consdata1->hmax )
12272 SCIPsort(perm0, consdataCompVar, (
void*)consdata0, consdata0->nvars);
12273 SCIPsort(perm1, consdataCompVar, (
void*)consdata1, consdata1->nvars);
12275 for( v0 = 0, v1 = 0; v0 < consdata0->nvars && v1 < consdata1->nvars; )
12286 var0 = consdata0->vars[idx0];
12288 var1 = consdata1->vars[idx1];
12299 demand0 = consdata0->demands[idx0];
12300 duration0 = consdata0->durations[idx0];
12302 demand1 = consdata1->demands[idx1];
12303 duration1 = consdata1->durations[idx1];
12305 if( demand0 != demand1 )
12308 if( duration0 != duration1 )
12314 else if( comp > 0 )
12320 if( v0 == consdata0->nvars )
12365 if( consdata->varbounds )
12368 vars = consdata->vars;
12369 durations = consdata->durations;
12370 demands = consdata->demands;
12371 capacity = consdata->capacity;
12372 nvars = consdata->nvars;
12386 var = consdata->vars[
i];
12394 for(
b = 0;
b < nvbdvars; ++
b )
12400 for( j = 0; j <
nvars; ++j )
12402 if(
vars[j] == vbdvars[
b] )
12408 if( demands[
i] + demands[j] > capacity &&
12426 (*nchgbds) += nlocalbdchgs;
12433 (*naddconss) += nconss;
12435 consdata->varbounds =
TRUE;
12460 if( solinfeasible )
12466 SCIPdebugMsg(
scip,
"constraint enforcing %d useful cumulative constraints of %d constraints for %s solution\n", nusefulconss, nconss,
12467 sol ==
NULL ?
"LP" :
"relaxation");
12474 if( conshdlrdata->usebinvars )
12483 for(
c = 0;
c < nusefulconss; ++
c )
12504 for( ;
c < nconss && !separated; ++
c )
12574#ifdef SCIP_STATISTIC
12575 if( !conshdlrdata->iscopy )
12579 conshdlrdata->nlbtimetable, conshdlrdata->nubtimetable, conshdlrdata->ncutofftimetable);
12581 conshdlrdata->nlbedgefinder, conshdlrdata->nubedgefinder, conshdlrdata->ncutoffedgefinder);
12583 conshdlrdata->ncutoffoverload, conshdlrdata->ncutoffoverloadTTEF);
12605 conshdlrdata->detectedredundant =
FALSE;
12607 for(
c = 0;
c < nconss; ++
c )
12620#ifdef SCIP_STATISTIC
12630 for(
c = 0;
c < nconss; ++
c )
12634#ifdef SCIP_DISABLED_CODE
12639 if( !conshdlrdata->iscopy )
12641 SCIPstatisticPrintf(
"@11 added variables bounds constraints %d\n", conshdlrdata->naddedvarbounds);
12642 SCIPstatisticPrintf(
"@22 added disjunctive constraints %d\n", conshdlrdata->naddeddisjunctives);
12668 for(
c = 0;
c < nconss; ++
c )
12732 sourcedata->durations, sourcedata->demands, sourcedata->nvars, sourcedata->capacity,
12760 *infeasible =
FALSE;
12762 SCIPdebugMsg(
scip,
"initialize LP relaxation for %d cumulative constraints\n", nconss);
12764 if( conshdlrdata->usebinvars )
12767 for(
c = 0;
c < nconss && !(*infeasible); ++
c )
12772 if( conshdlrdata->cutsasconss )
12803 SCIPdebugMsg(
scip,
"separating %d/%d cumulative constraints\n", nusefulconss, nconss);
12814 if( conshdlrdata->usebinvars )
12817 for(
c = 0;
c < nusefulconss && !
cutoff; ++
c )
12822 if( !
cutoff && conshdlrdata->usecovercuts )
12824 for(
c = 0;
c < nusefulconss; ++
c )
12831 if( conshdlrdata->sepaold )
12834 for(
c = 0;
c < nusefulconss; ++
c )
12843 else if( separated )
12869 SCIPdebugMsg(
scip,
"separating %d/%d cumulative constraints\n", nusefulconss, nconss);
12875 if( conshdlrdata->usebinvars )
12878 for(
c = 0;
c < nusefulconss && !
cutoff; ++
c )
12883 if( !
cutoff && conshdlrdata->usecovercuts )
12885 for(
c = 0;
c < nusefulconss; ++
c )
12891 if( conshdlrdata->sepaold )
12894 for(
c = 0;
c < nusefulconss; ++
c )
12903 else if( separated )
12940 if( objinfeasible )
12994 SCIPdebugMsg(
scip,
"propagate %d of %d useful cumulative constraints\n", nusefulconss, nconss);
13010 for(
c = 0;
c < nusefulconss && !
cutoff; ++
c )
13020 &nchgbds, &nchgbds, &ndelconss, &nchgbds, &nchgbds, &nchgbds, &
cutoff, &
cutoff) );
13032 if( !
cutoff && nchgbds == 0 )
13035 for(
c = nusefulconss;
c < nconss && !
cutoff; ++
c )
13046 else if( nchgbds > 0 )
13048 SCIPdebugMsg(
scip,
"delete (locally) %d constraints and changed %d variable bounds\n", ndelconss, nchgbds);
13086 oldnfixedvars = *nfixedvars;
13087 oldnchgbds = *nchgbds;
13088 oldnchgsides = *nchgsides;
13089 oldnchgcoefs = *nchgcoefs;
13090 oldnupgdconss = *nupgdconss;
13091 oldndelconss = *ndelconss;
13092 oldnaddconss = *naddconss;
13097 for(
c = 0;
c < nconss && !
cutoff; ++
c )
13109 nfixedvars, nchgbds, ndelconss, naddconss, nchgcoefs, nchgsides, &
cutoff, &unbounded) );
13111 if(
cutoff || unbounded )
13119 if( nrounds == 1 &&
SCIPgetNRuns(
scip) == 1 && conshdlrdata->disjunctive )
13142 && (conshdlrdata->detectvarbounds || conshdlrdata->detectdisjunctive)
13149 conshdlrdata->detectedredundant =
TRUE;
13157 SCIPdebugMsg(
scip,
"delete %d constraints and changed %d variable bounds (cutoff %u)\n",
13158 *ndelconss - oldndelconss, *nchgbds - oldnchgbds,
cutoff);
13162 else if( unbounded )
13164 else if( *nchgbds > oldnchgbds || *nfixedvars > oldnfixedvars || *nchgsides > oldnchgsides
13165 || *nchgcoefs > oldnchgcoefs || *nupgdconss > oldnupgdconss || *ndelconss > oldndelconss || *naddconss > oldnaddconss )
13196 SCIPdebugMsg(
scip,
"resolve propagation: variable <%s>, cumulative constraint <%s> (capacity %d, propagation %d, H=[%d,%d))\n",
13201 consdata->durations, consdata->demands, consdata->capacity, consdata->hmin, consdata->hmax,
13202 infervar,
intToInferInfo(inferinfo), boundtype, bdchgidx, relaxedbd, conshdlrdata->usebdwidening,
NULL,
result) );
13224 vars = consdata->vars;
13227 for( v = 0; v < consdata->nvars; ++v )
13229 if( consdata->downlocks[v] && consdata->uplocks[v] )
13234 else if( consdata->downlocks[v] )
13238 else if( consdata->uplocks[v] )
13268 const char* consname;
13277 nvars = sourceconsdata->nvars;
13278 sourcevars = sourceconsdata->vars;
13304 sourceconsdata->durations, sourceconsdata->demands, sourceconsdata->capacity,
13305 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
13308 if( sourceconsdata->hmin > 0 )
13314 if( sourceconsdata->hmax < INT_MAX )
13368 endptr = strchr(endptr,
')');
13370 if( endptr ==
NULL )
13380 duration = atoi(strvalue);
13384 demand = atoi(strvalue);
13390 demands[
nvars] = demand;
13391 durations[
nvars] = duration;
13394 while( *str !=
')' );
13400 hmin = atoi(strvalue);
13413 capacity = (int)value;
13417 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
13443 if( varssize < consdata->
nvars )
13444 (*success) =
FALSE;
13465 (*nvars) = consdata->nvars;
13495 consdata->propagated =
FALSE;
13524 consEnfolpCumulative, consEnfopsCumulative, consCheckCumulative, consLockCumulative,
13532#ifdef SCIP_STATISTIC
13555 "constraints/" CONSHDLR_NAME "/maxtime",
"maximum range for time horizon",
13559 "should time-table (core-times) propagator be used to infer bounds?",
13563 "should edge-finding be used to detect an overload?",
13567 "should edge-finding be used to infer bounds?",
13570 "constraints/" CONSHDLR_NAME "/useadjustedjobs",
"should edge-finding be executed?",
13574 "should time-table edge-finding be used to detect an overload?",
13578 "should time-table edge-finding be used to infer bounds?",
13582 "constraints/" CONSHDLR_NAME "/usebinvars",
"should the binary representation be used?",
13585 "constraints/" CONSHDLR_NAME "/localcuts",
"should cuts be added only locally?",
13588 "constraints/" CONSHDLR_NAME "/usecovercuts",
"should covering cuts be added every node?",
13592 "should the cumulative constraint create cuts as knapsack constraints?",
13596 "shall old sepa algo be applied?",
13600 "constraints/" CONSHDLR_NAME "/fillbranchcands",
"should branching candidates be added to storage?",
13605 "constraints/" CONSHDLR_NAME "/dualpresolve",
"should dual presolving be applied?",
13608 "constraints/" CONSHDLR_NAME "/coeftightening",
"should coefficient tightening be applied?",
13611 "constraints/" CONSHDLR_NAME "/normalize",
"should demands and capacity be normalized?",
13615 "should pairwise constraint comparison be performed in presolving?",
13618 "constraints/" CONSHDLR_NAME "/disjunctive",
"extract disjunctive constraints?",
13623 "number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit)?",
13626 "constraints/" CONSHDLR_NAME "/detectdisjunctive",
"search for conflict set via maximal cliques to detect disjunctive constraints",
13629 "constraints/" CONSHDLR_NAME "/detectvarbounds",
"search for conflict set via maximal cliques to detect variable bound constraints",
13634 "constraints/" CONSHDLR_NAME "/usebdwidening",
"should bound widening be used during the conflict analysis?",
13683 if( conshdlr ==
NULL )
13693 SCIPerrorMessage(
"detected potential integer overflow for variable <%s> in constraint <%s>: "
13694 "decrease upper bound of variable or time horizon constraints/" CONSHDLR_NAME "/maxtime\n",
13702 SCIP_CALL(
consdataCreate(
scip, &consdata,
vars,
NULL, durations, demands,
nvars, capacity, 0, INT_MAX, check) );
13707 local, modifiable, dynamic, removable, stickingatnode) );
13769 if( hmin < 0 || hmin > consdata->hmax )
13771 SCIPerrorMessage(
"invalid value of hmin for cumulative constraint <%s>\n",
13776 consdata->hmin = hmin;
13798 return consdata->hmin;
13819 if( hmax < consdata->hmin )
13821 SCIPerrorMessage(
"invalid value of hmax for cumulative constraint <%s>\n",
13826 consdata->hmax = hmax;
13848 return consdata->hmax;
13869 return consdata->vars;
13890 return consdata->nvars;
13911 return consdata->capacity;
13932 return consdata->durations;
13953 return consdata->demands;
13978 violated, cons, printreason) );
14014 hmin, hmax, split) );
14041 irrelevants, nfixedvars, nchgsides,
cutoff) );
14045 irrelevants, nfixedvars, nchgsides,
cutoff) );
14081 if( conshdlr ==
NULL )
14093 nvars,
vars, durations, demands, capacity, hmin, hmax, cons,
14094 nchgbds, &redundant, initialized, explanation,
cutoff) );
14142 file = fopen(filename,
"w");
14155 nvars = consdata->nvars;
14158 SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal,
NULL), TERMINATE );
14163 for( v = 0; v <
nvars; ++v )
14167 var = consdata->vars[v];
14174 else if( !consdata->downlocks[v] || !consdata->uplocks[v] )
14182 for( v = 0; v <
nvars; ++v )
14188 var = consdata->vars[v];
14194 for(
b = 0;
b < nvbdvars; ++
b )
14202#ifdef SCIP_MORE_OUTPUT
14207 for(
b = 0;
b < nvbdvars; ++
b )
14239 if( conshdlr ==
NULL )
14283 (*infeasible) =
FALSE;
14284 (*unbounded) =
FALSE;
14292 if( conshdlr ==
NULL )
14303 if( timelimit > 0.0 && memorylimit > 10 )
14305 SCIP_CALL( conshdlrdata->solveCumulative(njobs, ests, lsts, objvals, durations, demands, capacity,
14306 hmin, hmax, timelimit, memorylimit, maxnodes, solved, infeasible, unbounded, error) );
14342 for( v = 0; v <
nvars; ++v )
14344 copydemands[v] = demands[v];
14350 for( v = 0; v <
nvars; ++v )
14360 duration = durations[idx];
14369 if( impliedest < impliedlct )
14379 if( est == impliedest && lct == impliedlct )
14410 for( t = 0; t < ntimepoints - 1; ++t )
14413 if( loads[t] > capacity )
14415 assert(t == 0 || loads[t-1] <= capacity);
14416 return timepoints[t];
14440 for( t = ntimepoints - 1; t >= 0; --t )
14443 if( loads[t] > capacity )
14445 assert(t == ntimepoints-1 || loads[t+1] <= capacity);
14446 return timepoints[t+1];
static SCIP_RETCODE branch(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_RESULT *result)
#define CONSHDLR_NEEDSCONS
#define CONSHDLR_SEPAFREQ
#define CONSHDLR_CHECKPRIORITY
#define CONSHDLR_PROP_TIMING
#define CONSHDLR_MAXPREROUNDS
#define DEFAULT_PRESOLPAIRWISE
#define CONSHDLR_SEPAPRIORITY
#define CONSHDLR_PROPFREQ
#define CONSHDLR_PRESOLTIMING
#define CONSHDLR_EAGERFREQ
#define CONSHDLR_ENFOPRIORITY
#define CONSHDLR_DELAYSEPA
#define CONSHDLR_DELAYPROP
static SCIP_RETCODE adjustOversizedJobBounds(SCIP *scip, SCIP_CONSDATA *consdata, int pos, int *nchgbds, int *naddconss, SCIP_Bool *cutoff)
static int inferInfoGetData1(INFERINFO inferinfo)
static SCIP_RETCODE createTcliqueGraph(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
#define DEFAULT_USEBDWIDENING
static void createSortedEventpointsSol(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *starttimes, int *endtimes, int *startindices, int *endindices)
static void createSortedEventpoints(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *starttimes, int *endtimes, int *startindices, int *endindices, SCIP_Bool local)
static void consdataCalcSignature(SCIP_CONSDATA *consdata)
static SCIP_RETCODE propagateUbTTEF(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, int *newlbs, int *newubs, int *lbinferinfos, int *ubinferinfos, int *lsts, int *flexenergies, int *perm, int *ests, int *lcts, int *coreEnergyAfterEst, int *coreEnergyAfterLct, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
#define DEFAULT_NORMALIZE
static PROPRULE inferInfoGetProprule(INFERINFO inferinfo)
static SCIP_RETCODE collectIntVars(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR ***activevars, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool lower, int *lhs)
static SCIP_RETCODE getActiveVar(SCIP *scip, SCIP_VAR **var, int *scalar, int *constant)
#define DEFAULT_DETECTVARBOUNDS
static SCIP_RETCODE createConsCumulative(SCIP *scip, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
static SCIP_RETCODE presolveConsEst(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff)
#define DEFAULT_TTEFINFER
static void subtractStartingJobDemands(SCIP_CONSDATA *consdata, int curtime, int *starttimes, int *startindices, int *freecapacity, int *idx, int nvars)
static SCIP_RETCODE varMayRoundUp(SCIP *scip, SCIP_VAR *var, SCIP_Bool *roundable)
#define DEFAULT_USECOVERCUTS
static SCIP_Longint computeCoreWithInterval(int begin, int end, int ect, int lst)
static SCIP_RETCODE applyAlternativeBoundsFixing(SCIP *scip, SCIP_VAR **vars, int nvars, int *alternativelbs, int *alternativeubs, int *downlocks, int *uplocks, int *nfixedvars, SCIP_Bool *cutoff)
#define DEFAULT_LOCALCUTS
static SCIP_RETCODE checkOverloadViaThetaTree(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, SCIP_Bool propest, SCIP_Bool *initialized, SCIP_Bool *explanation, int *nchgbds, SCIP_Bool *cutoff)
#define DEFAULT_COEFTIGHTENING
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PRESOLTIMING presoltiming, int *nchgbds, int *ndelconss, SCIP_Bool *cutoff)
static SCIP_RETCODE createPrecedenceCons(SCIP *scip, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, int distance)
static SCIP_Bool isConsIndependently(SCIP_CONS *cons)
static SCIP_RETCODE separateConsOnIntegerVariables(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool lower, SCIP_Bool *separated, SCIP_Bool *cutoff)
static SCIP_RETCODE analyzeConflictOverload(SCIP *scip, SCIP_BTNODE **leaves, int capacity, int nleaves, int est, int lct, int reportedenergy, SCIP_Bool propest, int shift, SCIP_Bool usebdwidening, SCIP_Bool *initialized, SCIP_Bool *explanation)
static void conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
static void freeTcliqueGraph(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
static SCIP_Bool checkDemands(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE createCoverCuts(SCIP *scip, SCIP_CONS *cons)
static void consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
static SCIP_RETCODE tightenUbTTEF(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *var, int duration, int demand, int est, int lst, int lct, int begin, int end, SCIP_Longint energy, int *bestub, int *inferinfos, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
static SCIP_RETCODE propagateTimetable(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
static SCIP_RETCODE computeImpliedEst(SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *addedvars, int *est)
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_Bool solinfeasible, SCIP_RESULT *result)
static SCIP_RETCODE collectBranchingCands(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, int *nbranchcands)
static SCIP_RETCODE presolveCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PRESOLTIMING presoltiming, int *nfixedvars, int *nchgbds, int *ndelconss, int *naddconss, int *nchgcoefs, int *nchgsides, SCIP_Bool *cutoff, SCIP_Bool *unbounded)
static int computeEnergyContribution(SCIP_BTNODE *node)
static SCIP_RETCODE inferboundsEdgeFinding(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS *cons, SCIP_BT *tree, SCIP_BTNODE **leaves, int capacity, int ncands, SCIP_Bool propest, int shift, SCIP_Bool *initialized, SCIP_Bool *explanation, int *nchgbds, SCIP_Bool *cutoff)
static SCIP_RETCODE presolveConsEffectiveHorizon(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *nchgcoefs, int *nchgsides, SCIP_Bool *cutoff)
static int boundedConvertRealToInt(SCIP *scip, SCIP_Real real)
static SCIP_RETCODE constraintNonOverlappingGraph(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss)
static SCIP_RETCODE createCoreProfile(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
static SCIP_RETCODE consCheckRedundancy(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *redundant)
static SCIP_RETCODE detectRedundantConss(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, int *naddconss)
static SCIP_RETCODE getNodeIdx(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_VAR *var, int *idx)
static SCIP_RETCODE computeAlternativeBounds(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool local, int *alternativelbs, int *alternativeubs, int *downlocks, int *uplocks)
static SCIP_RETCODE removeRedundantConss(SCIP *scip, SCIP_CONS **conss, int nconss, int *ndelconss)
static SCIP_RETCODE findPrecedenceConss(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int *naddconss)
static SCIP_RETCODE fixIntegerVariableUb(SCIP *scip, SCIP_VAR *var, SCIP_Bool uplock, int *nfixedvars)
static SCIP_RETCODE createCapacityRestriction(SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool cutsasconss)
#define DEFAULT_DETECTDISJUNCTIVE
static void addEndingJobDemands(SCIP_CONSDATA *consdata, int curtime, int *endtimes, int *endindices, int *freecapacity, int *idx, int nvars)
static INFERINFO getInferInfo(PROPRULE proprule, int data1, int data2)
static SCIP_RETCODE setupAndSolveCumulativeSubscip(SCIP *subscip, SCIP_Real *objvals, int *durations, int *demands, int njobs, int capacity, int hmin, int hmax, SCIP_Longint maxnodes, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *solved, SCIP_Bool *error)
static int computeOverlap(int begin, int end, int est, int lst, int duration)
static SCIP_Longint computeTotalEnergy(int *durations, int *demands, int njobs)
static SCIP_RETCODE strengthenVarbounds(SCIP *scip, SCIP_CONS *cons, int *nchgbds, int *naddconss)
static SCIP_RETCODE respropCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, INFERINFO inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool usebdwidening, SCIP_Bool *explanation, SCIP_RESULT *result)
static SCIP_RETCODE removeIrrelevantJobs(SCIP *scip, SCIP_CONS *cons)
static INFERINFO intToInferInfo(int i)
static void createSelectedSortedEventpointsSol(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, int *starttimes, int *endtimes, int *startindices, int *endindices, int *nvars, SCIP_Bool lower)
static void updateEnvelope(SCIP *scip, SCIP_BTNODE *node)
static SCIP_RETCODE propagateEdgeFinding(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, SCIP_Bool *initialized, SCIP_Bool *explanation, int *nchgbds, SCIP_Bool *cutoff)
struct SCIP_NodeData SCIP_NODEDATA
#define DEFAULT_CUTSASCONSS
#define DEFAULT_DUALPRESOLVE
static SCIP_RETCODE analyzeEnergyRequirement(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int begin, int end, SCIP_VAR *infervar, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool usebdwidening, SCIP_Bool *explanation)
static SCIP_RETCODE applyAlternativeBoundsBranching(SCIP *scip, SCIP_VAR **vars, int nvars, int *alternativelbs, int *alternativeubs, int *downlocks, int *uplocks, SCIP_Bool *branched)
static SCIP_RETCODE applyProbingVar(SCIP *scip, SCIP_VAR **vars, int nvars, int probingpos, SCIP_Real leftub, SCIP_Real rightlb, SCIP_Real *leftimpllbs, SCIP_Real *leftimplubs, SCIP_Real *leftproplbs, SCIP_Real *leftpropubs, SCIP_Real *rightimpllbs, SCIP_Real *rightimplubs, SCIP_Real *rightproplbs, SCIP_Real *rightpropubs, int *nfixedvars, SCIP_Bool *success, SCIP_Bool *cutoff)
#define DEFAULT_TTEFCHECK
static void normalizeDemands(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides)
static SCIP_Bool inferInfoIsValid(INFERINFO inferinfo)
static void computeCoreEnergyAfter(SCIP_PROFILE *profile, int nvars, int *ests, int *lcts, int *coreEnergyAfterEst, int *coreEnergyAfterLct)
static SCIP_RETCODE consCapacityConstraintsFinder(SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss)
static SCIP_RETCODE createCumulativeCons(SCIP *scip, const char *name, TCLIQUE_GRAPH *tcliquegraph, int *cliquenodes, int ncliquenodes)
static void collectDataTTEF(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int hmin, int hmax, int *permests, int *ests, int *permlcts, int *lcts, int *ects, int *lsts, int *flexenergies)
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR **vars, SCIP_CONS **linkingconss, int *durations, int *demands, int nvars, int capacity, int hmin, int hmax, SCIP_Bool check)
static SCIP_RETCODE createCoverCutsTimepoint(SCIP *scip, SCIP_CONS *cons, int *startvalues, int time)
static SCIP_RETCODE tightenLbTTEF(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *var, int duration, int demand, int est, int ect, int lct, int begin, int end, SCIP_Longint energy, int *bestlb, int *inferinfos, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
static SCIP_RETCODE consdataDeletePos(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_CONS *cons, int pos)
static SCIP_RETCODE propagateAllConss(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool local, int *nfixedvars, SCIP_Bool *cutoff, SCIP_Bool *branched)
static SCIP_RETCODE presolveConsLct(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff)
static int inferInfoGetData2(INFERINFO inferinfo)
static void traceThetaEnvelop(SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy)
static SCIP_RETCODE propagateCumulativeCondition(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PRESOLTIMING presoltiming, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *redundant, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
static SCIP_RETCODE resolvePropagationCoretimes(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferdemand, int inferpeak, int relaxedpeak, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool usebdwidening, int *provedpeak, SCIP_Bool *explanation)
static SCIP_RETCODE consdataDropAllEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
static SCIP_RETCODE collectBinaryVars(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR ***vars, int **coefs, int *nvars, int *startindices, int curtime, int nstarted, int nfinished)
#define DEFAULT_USEADJUSTEDJOBS
static SCIP_RETCODE projectVbd(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph)
static SCIP_RETCODE createDisjuctiveCons(SCIP *scip, SCIP_CONS *cons, int *naddconss)
static SCIP_RETCODE deleteLambdaLeaf(SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node)
static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss)
static SCIP_RETCODE computeEffectiveHorizon(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss, int *nchgsides)
static SCIP_RETCODE enforceSolution(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_Bool branch, SCIP_RESULT *result)
static SCIP_RETCODE deleteTrivilCons(SCIP *scip, SCIP_CONS *cons, int *ndelconss, SCIP_Bool *cutoff)
static SCIP_RETCODE computeMinDistance(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int source, int sink, int *naddconss)
static SCIP_RETCODE varMayRoundDown(SCIP *scip, SCIP_VAR *var, SCIP_Bool *roundable)
static void collectDemands(SCIP *scip, SCIP_CONSDATA *consdata, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Longint **demands, int *ndemands)
static SCIP_RETCODE createCapacityRestrictionIntvars(SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool lower, SCIP_Bool *cutoff)
static SCIP_RETCODE computeImpliedLct(SCIP *scip, SCIP_VAR *var, int duration, SCIP_HASHMAP *addedvars, int *lct)
static SCIP_RETCODE findCumulativeConss(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int *naddconss)
static SCIP_RETCODE tightenCoefs(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs)
static SCIP_RETCODE tightenCapacity(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides)
static SCIP_BTNODE * findResponsibleLambdaLeafTraceEnergy(SCIP_BTNODE *node)
static SCIP_RETCODE analyseInfeasibelCoreInsertion(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferduration, int inferdemand, int inferpeak, SCIP_Bool usebdwidening, SCIP_Bool *initialized, SCIP_Bool *explanation)
static SCIP_RETCODE consdataFreeRows(SCIP *scip, SCIP_CONSDATA **consdata)
static SCIP_RETCODE initializeDurations(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss)
static SCIP_Bool impliesVlbPrecedenceCondition(SCIP *scip, SCIP_VAR *vlbvar, SCIP_Real vlbcoef, SCIP_Real vlbconst, int duration)
static SCIP_RETCODE separateCoverCutsCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff)
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
static SCIP_RETCODE coretimesUpdateLb(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, SCIP_PROFILE *profile, int idx, int *nchgbds, SCIP_Bool usebdwidening, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *infeasible)
static SCIP_RETCODE solveIndependentCons(SCIP *scip, SCIP_CONS *cons, SCIP_Longint maxnodes, int *nchgbds, int *nfixedvars, int *ndelconss, SCIP_Bool *cutoff, SCIP_Bool *unbounded)
static void initializeLocks(SCIP_CONSDATA *consdata, SCIP_Bool locked)
static SCIP_BTNODE * findResponsibleLambdaLeafTraceEnvelop(SCIP_BTNODE *node)
static SCIP_RETCODE fixIntegerVariableLb(SCIP *scip, SCIP_VAR *var, SCIP_Bool downlock, int *nfixedvars)
#define DEFAULT_USEBINVARS
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
static SCIP_RETCODE coretimesUpdateUb(SCIP *scip, SCIP_VAR *var, int duration, int demand, int capacity, SCIP_CONS *cons, SCIP_PROFILE *profile, int idx, int *nchgbds)
static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *violated, SCIP_Bool printreason)
static void collectThetaSubtree(SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy)
static int computeEstOmegaset(SCIP *scip, int duration, int demand, int capacity, int est, int lct, int energy)
struct InferInfo INFERINFO
static SCIP_RETCODE propagateTTEF(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
static SCIP_RETCODE insertThetanode(SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node, SCIP_NODEDATA *nodedatas, int *nodedataidx, int *nnodedatas)
static void traceLambdaEnvelop(SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy)
static SCIP_RETCODE computePeak(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, int *timepoint)
#define DEFAULT_FILLBRANCHCANDS
static SCIP_RETCODE consdataCollectLinkingCons(SCIP *scip, SCIP_CONSDATA *consdata)
static SCIP_RETCODE propagateLbTTEF(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, int *newlbs, int *newubs, int *lbinferinfos, int *ubinferinfos, int *ects, int *flexenergies, int *perm, int *ests, int *lcts, int *coreEnergyAfterEst, int *coreEnergyAfterLct, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
static void transitiveClosure(SCIP_Bool **adjmatrix, int *ninarcs, int *noutarcs, int nnodes)
static SCIP_RETCODE getHighestCapacityUsage(SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, int *bestcapacity)
static SCIP_RETCODE constructIncompatibilityGraph(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss)
static SCIP_RETCODE removeOversizedJobs(SCIP *scip, SCIP_CONS *cons, int *nchgbds, int *nchgcoefs, int *naddconss, SCIP_Bool *cutoff)
static void updateKeyOnTrace(SCIP_BTNODE *node, SCIP_Real key)
static int inferInfoToInt(INFERINFO inferinfo)
static SCIP_RETCODE consdataDropEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
static void traceLambdaEnergy(SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy)
static SCIP_RETCODE computeEffectiveHorizonCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *hmin, int *hmax, int *split)
static SCIP_RETCODE separateConsBinaryRepresentation(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff)
static void normalizeCumulativeCondition(SCIP *scip, int nvars, int *demands, int *capacity, int *nchgcoefs, int *nchgsides)
static SCIP_Bool impliesVubPrecedenceCondition(SCIP *scip, SCIP_VAR *var, SCIP_Real vubcoef, SCIP_Real vubconst, int duration)
static SCIP_RETCODE moveNodeToLambda(SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node)
#define DEFAULT_DISJUNCTIVE
static SCIP_RETCODE consdataCatchEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss, SCIP_Bool *infeasible)
static SCIP_RETCODE checkCumulativeCondition(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *violated, SCIP_CONS *cons, SCIP_Bool printreason)
constraint handler for cumulative constraints
Constraint handler for knapsack constraints of the form , x binary and .
constraint handler for linking binary variables to a linking (continuous or integer) variable
static SCIP_RETCODE solveCumulative(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool local, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Longint maxnodes, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *error)
#define SCIP_CALL_TERMINATE(retcode, x, TERM)
#define SCIP_LONGINT_FORMAT
#define SCIP_CALL_FINALLY(x, y)
static const NodeData nodedata[]
void SCIPbtnodeSetRightchild(SCIP_BTNODE *node, SCIP_BTNODE *right)
SCIP_BTNODE * SCIPbtnodeGetRightchild(SCIP_BTNODE *node)
SCIP_Bool SCIPbtIsEmpty(SCIP_BT *tree)
SCIP_RETCODE SCIPbtCreate(SCIP_BT **tree, BMS_BLKMEM *blkmem)
void SCIPbtnodeFree(SCIP_BT *tree, SCIP_BTNODE **node)
SCIP_Bool SCIPbtnodeIsLeaf(SCIP_BTNODE *node)
void * SCIPbtnodeGetData(SCIP_BTNODE *node)
SCIP_RETCODE SCIPbtnodeCreate(SCIP_BT *tree, SCIP_BTNODE **node, void *dataptr)
SCIP_Bool SCIPbtnodeIsRightchild(SCIP_BTNODE *node)
void SCIPbtnodeSetParent(SCIP_BTNODE *node, SCIP_BTNODE *parent)
SCIP_Bool SCIPbtnodeIsLeftchild(SCIP_BTNODE *node)
void SCIPbtnodeSetLeftchild(SCIP_BTNODE *node, SCIP_BTNODE *left)
SCIP_BTNODE * SCIPbtnodeGetParent(SCIP_BTNODE *node)
void SCIPbtFree(SCIP_BT **tree)
SCIP_BTNODE * SCIPbtnodeGetLeftchild(SCIP_BTNODE *node)
void SCIPbtSetRoot(SCIP_BT *tree, SCIP_BTNODE *root)
SCIP_Bool SCIPbtnodeIsRoot(SCIP_BTNODE *node)
SCIP_BTNODE * SCIPbtGetRoot(SCIP_BT *tree)
int SCIPgetHminCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPpropCumulativeCondition(SCIP *scip, SCIP_PRESOLTIMING presoltiming, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPgetBinvarsLinking(SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***binvars, int *nbinvars)
SCIP_RETCODE SCIPcreateConsBasicSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
int * SCIPgetDurationsCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPexistsConsLinking(SCIP *scip, SCIP_VAR *linkvar)
SCIP_RETCODE SCIPsplitCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *hmin, int *hmax, int *split)
SCIP_RETCODE SCIPaddCoefKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight)
SCIP_RETCODE SCIPvisualizeConsCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsBasicCumulative(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity)
#define SCIP_DECL_SOLVECUMULATIVE(x)
int SCIPcomputeHmax(SCIP *scip, SCIP_PROFILE *profile, int capacity)
SCIP_CONS * SCIPgetConsLinking(SCIP *scip, SCIP_VAR *linkvar)
SCIP_RETCODE SCIPcreateConsBounddisjunction(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds, 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 SCIPcheckCumulativeCondition(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *violated, SCIP_CONS *cons, SCIP_Bool printreason)
SCIP_RETCODE SCIPsetSolveCumulative(SCIP *scip,)
SCIP_VAR ** SCIPgetVarsCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsBasicKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
int * SCIPgetDemandsCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsolveCumulative(SCIP *scip, int njobs, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Real *objvals, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint maxnodes, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *error)
SCIP_RETCODE SCIPcreateConsLinking(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *linkvar, SCIP_VAR **binvars, SCIP_Real *vals, int nbinvars, 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 SCIPsolveKnapsackExactly(SCIP *scip, int nitems, SCIP_Longint *weights, SCIP_Real *profits, SCIP_Longint capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval, SCIP_Bool *success)
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
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)
int SCIPgetHmaxCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPrespropCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool *explanation, SCIP_RESULT *result)
int SCIPgetCapacityCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPnormalizeCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int *capacity, int *nchgcoefs, int *nchgsides)
SCIP_RETCODE SCIPcreateWorstCaseProfile(SCIP *scip, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands)
SCIP_RETCODE SCIPpresolveCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPcreateConsVarbound(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, 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 * SCIPgetValsLinking(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsetHminCumulative(SCIP *scip, SCIP_CONS *cons, int hmin)
int SCIPgetNVarsCumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsetHmaxCumulative(SCIP *scip, SCIP_CONS *cons, int hmax)
SCIP_RETCODE SCIPcreateConsCumulative(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int 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)
int SCIPcomputeHmin(SCIP *scip, SCIP_PROFILE *profile, int capacity)
SCIP_RETCODE SCIPincludeConshdlrCumulative(SCIP *scip)
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
void SCIPgmlWriteClosing(FILE *file)
void SCIPgmlWriteOpening(FILE *file, SCIP_Bool directed)
void SCIPgmlWriteArc(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
SCIP_Bool SCIPisTransformed(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
int SCIPgetNCheckConss(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNConss(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
void * SCIPhashmapGetImage(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 SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
SCIP_Longint SCIPcalcGreComDiv(SCIP_Longint val1, SCIP_Longint val2)
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPapplyProbingVar(SCIP *scip, SCIP_VAR **vars, int nvars, int probingpos, SCIP_BOUNDTYPE boundtype, SCIP_Real bound, int maxproprounds, SCIP_Real *impllbs, SCIP_Real *implubs, SCIP_Real *proplbs, SCIP_Real *propubs, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
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 SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
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)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
void SCIPswapInts(int *value1, int *value2)
void SCIPswapPointers(void **pointer1, void **pointer2)
SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
SCIP_RETCODE SCIPbranchVarHole(SCIP *scip, SCIP_VAR *var, SCIP_Real left, SCIP_Real right, SCIP_NODE **downchild, SCIP_NODE **upchild)
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 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 SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, 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_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 SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(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_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 SCIPtransformConss(SCIP *scip, int nconss, SCIP_CONS **conss, SCIP_CONS **transconss)
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_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_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_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
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)
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
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_Longint SCIPgetMemExternEstim(SCIP *scip)
#define SCIPfreeBuffer(scip, ptr)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
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 SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
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 SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_Real SCIPgetRowSolFeasibility(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
void SCIPupdateSolConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_RETCODE SCIPrestartSolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
int SCIPgetNRuns(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
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 SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPconvertRealToInt(SCIP *scip, SCIP_Real real)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPparseReal(SCIP *scip, const char *str, SCIP_Real *value, char **endptr)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
SCIP_Bool SCIPvarIsInitial(SCIP_VAR *var)
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_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Bool SCIPvarIsTransformed(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 SCIPinferVarUbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Real SCIPvarGetObj(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_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)
int SCIPvarGetIndex(SCIP_VAR *var)
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
SCIP_RETCODE SCIPaddVarVlb(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vlbvar, SCIP_Real vlbcoef, SCIP_Real vlbconstant, SCIP_Bool *infeasible, int *nbdchgs)
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 SCIPvarIsRemovable(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
SCIP_RETCODE SCIPinferVarLbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
SCIP_RETCODE SCIPprofileInsertCore(SCIP_PROFILE *profile, int left, int right, int demand, int *pos, SCIP_Bool *infeasible)
int * SCIPprofileGetTimepoints(SCIP_PROFILE *profile)
SCIP_Bool SCIPprofileFindLeft(SCIP_PROFILE *profile, int timepoint, int *pos)
int SCIPprofileGetNTimepoints(SCIP_PROFILE *profile)
void SCIPprofileFree(SCIP_PROFILE **profile)
int SCIPprofileGetLoad(SCIP_PROFILE *profile, int pos)
int * SCIPprofileGetLoads(SCIP_PROFILE *profile)
SCIP_RETCODE SCIPprofileCreate(SCIP_PROFILE **profile, int capacity)
int SCIPprofileGetTime(SCIP_PROFILE *profile, int pos)
SCIP_RETCODE SCIPprofileDeleteCore(SCIP_PROFILE *profile, int left, int right, int demand)
void SCIPprofilePrint(SCIP_PROFILE *profile, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortDownIntIntInt(int *intarray1, int *intarray2, int *intarray3, int len)
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
void SCIPsortInt(int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
void SCIPstrCopySection(const char *str, char startchar, char endchar, char *token, int size, char **endptr)
void SCIPprintSysError(const char *message)
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_Bool propagate
#define BMScopyMemoryArray(ptr, source, num)
#define BMSclearMemoryArray(ptr, num)
#define SCIPdebugPrintCons(x, y, z)
#define SCIPstatisticPrintf
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
static SCIP_RETCODE separate(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
Main separation function.
#define TCLIQUE_GETWEIGHTS(x)
#define TCLIQUE_GETNNODES(x)
#define TCLIQUE_ISEDGE(x)
#define TCLIQUE_SELECTADJNODES(x)
enum TCLIQUE_Status TCLIQUE_STATUS
void tcliqueMaxClique(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_WEIGHT maxfirstnodeweight, TCLIQUE_WEIGHT minweight, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, int *ntreenodes, TCLIQUE_STATUS *status)
struct TCLIQUE_Graph TCLIQUE_GRAPH
#define TCLIQUE_NEWSOL(x)
@ SCIP_CONFTYPE_PROPAGATION
#define SCIP_DECL_CONSENFOLP(x)
#define SCIP_DECL_CONSINITPRE(x)
#define SCIP_DECL_CONSDELETE(x)
struct SCIP_Cons SCIP_CONS
#define SCIP_DECL_CONSGETVARS(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_CONSENFOPS(x)
#define SCIP_DECL_CONSPARSE(x)
#define SCIP_DECL_CONSTRANS(x)
#define SCIP_DECL_CONSPRESOL(x)
#define SCIP_DECL_CONSINITLP(x)
#define SCIP_DECL_CONSEXITPRE(x)
#define SCIP_DECL_CONSLOCK(x)
struct SCIP_Conshdlr SCIP_CONSHDLR
#define SCIP_DECL_CONSCOPY(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)
struct SCIP_Eventhdlr SCIP_EVENTHDLR
struct SCIP_EventData SCIP_EVENTDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_EVENTTYPE_BOUNDTIGHTENED
enum SCIP_BoundType SCIP_BOUNDTYPE
struct SCIP_HashMap SCIP_HASHMAP
#define SCIP_DECL_SORTPTRCOMP(x)
#define SCIP_DECL_SORTINDCOMP(x)
struct SCIP_BtNode SCIP_BTNODE
struct SCIP_HashTable SCIP_HASHTABLE
struct SCIP_Profile SCIP_PROFILE
@ SCIP_PARAMEMPHASIS_CPSOLVER
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_TRANSFORMING
@ SCIP_STATUS_TOTALNODELIMIT
@ SCIP_STATUS_BESTSOLLIMIT
@ SCIP_STATUS_PRIMALLIMIT
@ SCIP_STATUS_USERINTERRUPT
@ SCIP_STATUS_STALLNODELIMIT
@ SCIP_STATUS_RESTARTLIMIT
#define SCIP_PRESOLTIMING_ALWAYS
#define SCIP_PRESOLTIMING_MEDIUM
unsigned int SCIP_PRESOLTIMING
#define SCIP_PRESOLTIMING_FAST
#define SCIP_PRESOLTIMING_EXHAUSTIVE
struct SCIP_BdChgIdx SCIP_BDCHGIDX
@ SCIP_VARSTATUS_MULTAGGR
@ SCIP_VARSTATUS_AGGREGATED