65#define CONSHDLR_NAME "cumulative"
66#define CONSHDLR_DESC "cumulative constraint handler"
67#define CONSHDLR_SEPAPRIORITY 2100000
68#define CONSHDLR_ENFOPRIORITY -2040000
69#define CONSHDLR_CHECKPRIORITY -3030000
70#define CONSHDLR_SEPAFREQ 1
71#define CONSHDLR_PROPFREQ 1
72#define CONSHDLR_EAGERFREQ 100
74#define CONSHDLR_MAXPREROUNDS -1
75#define CONSHDLR_DELAYSEPA FALSE
76#define CONSHDLR_DELAYPROP FALSE
77#define CONSHDLR_NEEDSCONS TRUE
79#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
80#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
90#define DEFAULT_MAXTIME 2000000000
93#define DEFAULT_USEBINVARS FALSE
94#define DEFAULT_LOCALCUTS FALSE
95#define DEFAULT_USECOVERCUTS TRUE
96#define DEFAULT_CUTSASCONSS TRUE
97#define DEFAULT_SEPAOLD TRUE
100#define DEFAULT_TTINFER TRUE
101#define DEFAULT_EFCHECK FALSE
102#define DEFAULT_EFINFER FALSE
103#define DEFAULT_USEADJUSTEDJOBS FALSE
104#define DEFAULT_TTEFCHECK TRUE
105#define DEFAULT_TTEFINFER TRUE
108#define DEFAULT_DUALPRESOLVE TRUE
109#define DEFAULT_COEFTIGHTENING FALSE
110#define DEFAULT_NORMALIZE TRUE
111#define DEFAULT_PRESOLPAIRWISE TRUE
112#define DEFAULT_DISJUNCTIVE TRUE
113#define DEFAULT_DETECTDISJUNCTIVE TRUE
114#define DEFAULT_DETECTVARBOUNDS TRUE
115#define DEFAULT_MAXNODES 10000LL
118#define DEFAULT_FILLBRANCHCANDS FALSE
121#define DEFAULT_USEBDWIDENING TRUE
130#define EVENTHDLR_NAME "cumulative"
131#define EVENTHDLR_DESC "bound change event handler for cumulative constraints"
170 unsigned int signature;
172 unsigned int validsignature:1;
173 unsigned int normalized:1;
174 unsigned int covercuts:1;
175 unsigned int propagated:1;
176 unsigned int varbounds:1;
177 unsigned int triedsolving:1;
185struct SCIP_ConshdlrData
237 int nallconsdualfixs;
239 int naddeddisjunctives;
275 unsigned int proprule:2;
276 unsigned int data1:15;
277 unsigned int data2:15;
292 inferinfo.val.asint =
i;
303 return inferinfo.val.asint;
336 return (
PROPRULE) inferinfo.val.asbits.proprule;
345 return (
int) inferinfo.val.asbits.data1;
354 return (
int) inferinfo.val.asbits.data2;
363 return (inferinfo.val.asint != 0);
378 if( proprule ==
PROPRULE_0_INVALID || data1 < 0 || data1 >= (1<<15) || data2 < 0 || data2 >= (1<<15) )
380 inferinfo.val.asint = 0;
386 inferinfo.val.asbits.proprule = proprule;
387 inferinfo.val.asbits.data1 = (
unsigned int) data1;
388 inferinfo.val.asbits.data2 = (
unsigned int) data2;
419 core =
MAX(0,
MIN(end, ect) -
MAX(lst, begin));
424#define computeCoreWithInterval(begin, end, ect, lst) (MAX(0, MIN((end), (ect)) - MAX((lst), (begin))))
436#ifdef SCIP_DISABLED_CODE
449#ifdef SCIP_DISABLED_CODE
457 for( v = 0; v < nvbdvars; ++v )
469 duration = (int)(
size_t)image;
476 if( duration >= vbdconst )
482 if( (*est) < impliedest )
506#ifdef SCIP_DISABLED_CODE
518#ifdef SCIP_DISABLED_CODE
526 for( v = 0; v < nvbdvars; ++v )
541 if( duration >= -vbdconst )
547 if( (*lct) > impliedlct )
581 startindex = nstarted - 1;
587 while( nstarted - nfinished > nrowvars )
596 varidx = startindices[startindex];
600 duration = consdata->durations[
varidx];
601 demand = consdata->demands[
varidx];
607 if( endtime > curtime )
625 start = curtime - duration + 1;
626 end =
MIN(curtime, endtime - duration);
628 for(
b = 0;
b < nbinvars; ++
b )
630 if( vals[
b] < start )
646 (*vars)[*
nvars] = binvars[
b];
647 (*coefs)[*
nvars] = demand;
684 assert(curtime >= consdata->hmin);
685 assert(curtime < consdata->hmax);
692 startindex = nstarted - 1;
695 while( nstarted - nfinished > counter )
700 varidx = startindices[startindex];
704 duration = consdata->durations[
varidx];
713 endtime =
MIN(starttime + duration, consdata->hmax);
716 if( endtime > curtime )
718 (*activevars)[counter] =
var;
719 sumofstarts += starttime;
720 mindelta =
MIN(mindelta, endtime - curtime);
728 *lhs = lower ? sumofstarts + mindelta : sumofstarts - mindelta;
753 for ( j = 0; j <
nvars; ++j )
800 for ( j = 0; j <
nvars; ++j )
840 tmpnvars = consdata->nvars;
844 for ( j = 0; j < tmpnvars; ++j )
846 var = consdata->vars[j];
848 assert(consdata->durations[j] > 0);
849 assert(consdata->demands[j] > 0);
859 startindices[*
nvars] = j;
861 endtimes[*
nvars] = starttimes[*
nvars] + consdata->durations[j];
862 endindices[*
nvars] = j;
864 SCIPdebugMsg(
scip,
"%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
866 consdata->durations[j],
867 starttimes[*
nvars], starttimes[*
nvars] + consdata->durations[startindices[*
nvars]],
868 consdata->demands[startindices[*
nvars]]);
879 startindices[*
nvars] = j;
881 endtimes[*
nvars] = starttimes[*
nvars] + consdata->durations[j];
882 endindices[*
nvars] = j;
884 SCIPdebugMsg(
scip,
"%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
886 consdata->durations[j],
887 starttimes[*
nvars], starttimes[*
nvars] + consdata->durations[startindices[*
nvars]],
888 consdata->demands[startindices[*
nvars]]);
901 for ( j = 0; j < *
nvars; ++j )
903 SCIPdebugMsg(
scip,
"%d: job[%d] starttime %d, endtime = %d, demand = %d\n", j,
904 startindices[j], starttimes[j], starttimes[j] + consdata->durations[startindices[j]],
905 consdata->demands[startindices[j]]);
908 for ( j = 0; j < *
nvars; ++j )
910 SCIPdebugMsg(
scip,
"%d: job[%d] endtime %d, demand = %d\n", j, endindices[j], endtimes[j],
911 consdata->demands[endindices[j]]);
969 (*timepoints)[0] = starttimes[0];
970 (*cumulativedemands)[0] = 0;
974 for( j = 0; j <
nvars; ++j )
979 curtime = starttimes[j];
981 if( curtime >= hmax )
985 while( endindex <
nvars && endtimes[endindex] <= curtime )
989 if( (*timepoints)[*ntimepoints] < endtimes[endindex] )
992 (*timepoints)[*ntimepoints] = endtimes[endindex];
993 (*cumulativedemands)[*ntimepoints] = 0;
996 idx = endindices[endindex];
998 totaldemand -= (
SCIP_Real) demands[idx] * durations[idx] / (endtimes[endindex] - est);
1001 (*cumulativedemands)[*ntimepoints] = totaldemand;
1004 idx = startindices[j];
1006 totaldemand += (
SCIP_Real) demands[idx] * durations[idx] / (lct - starttimes[j]);
1008 if( (*timepoints)[*ntimepoints] < curtime )
1011 (*timepoints)[*ntimepoints] = curtime;
1012 (*cumulativedemands)[*ntimepoints] = 0;
1015 (*cumulativedemands)[*ntimepoints] = totaldemand;
1018 while( j+1 <
nvars && starttimes[j+1] == curtime )
1021 idx = startindices[j];
1023 totaldemand += (
SCIP_Real) demands[idx] * durations[idx] / (lct - starttimes[j]);
1025 (*cumulativedemands)[*ntimepoints] = totaldemand;
1030 while( endindex <
nvars)
1035 if( (*timepoints)[*ntimepoints] < endtimes[endindex] )
1038 (*timepoints)[*ntimepoints] = endtimes[endindex];
1039 (*cumulativedemands)[*ntimepoints] = 0;
1042 idx = endindices[endindex];
1044 totaldemand -= (
SCIP_Real) demands[idx] * durations[idx] / (endtimes[endindex] - est);
1045 (*cumulativedemands)[*ntimepoints] = totaldemand;
1052 (*minfreecapacity) = INT_MAX;
1053 for( j = 0; j < *ntimepoints; ++j )
1055 if( (*timepoints)[j] >= hmin && (*timepoints)[j] < hmax )
1056 *minfreecapacity =
MIN( *minfreecapacity, (
SCIP_Real)capacity - (*cumulativedemands)[j] );
1094 nvars = consdata->nvars;
1095 capacity = consdata->capacity;
1097 globalmaxdemand = 0.0;
1104 for( v = 0; v <
nvars; ++v )
1115 peak = consdata->demands[v];
1120 if( consdata->demands[v] > capacity / 3 )
1123 for( j = 0; j <
nvars; ++j )
1133 if( lb <= timepoint && lb + consdata->durations[j] > timepoint )
1135 peak += consdata->demands[j];
1138 if( consdata->demands[j] > consdata->capacity / 3 )
1144 globalpeak =
MAX(globalpeak, peak);
1145 globalmaxdemand =
MAX(globalmaxdemand, maxdemand);
1147 if( peak > capacity )
1150 cumfactor1 =
MAX( cumfactor1, (peak-capacity)/peak * (capacity-deltademand)/(
SCIP_Real)capacity );
1151 resstrength2 =
MAX(resstrength2, (capacity-maxdemand)/(peak-maxdemand) );
1155 resstrength1 = (capacity-globalmaxdemand) / (globalpeak-globalmaxdemand);
1158 consdata->disjfactor2 = disjfactor2;
1159 consdata->cumfactor1 = cumfactor1;
1160 consdata->resstrength2 = resstrength2;
1161 consdata->resstrength1 = resstrength1;
1175 minfreecapacity = INT_MAX;
1178 consdata->durations, consdata->demands,
1179 capacity, consdata->hmin, consdata->hmax, &timepoints, &estimateddemands,
1180 &ntimepoints, &maxdemand, &minfreecapacity) );
1186 consdata->estimatedstrength = (
SCIP_Real)(capacity - minfreecapacity) / (
SCIP_Real) capacity;
1189 SCIPstatisticPrintf(
"cumulative constraint<%s>: DISJ1=%g, DISJ2=%g, CUM=%g, RS1 = %g, RS2 = %g, EST = %g\n",
1190 SCIPconsGetName(cons), consdata->disjfactor1, disjfactor2, cumfactor1, resstrength1, resstrength2,
1191 consdata->estimatedstrength);
1221 if( realconstant < 0.0 )
1226 if( realscalar < 0.0 )
1255 for( j = 0; j < njobs; ++j )
1308 for( v = 0; v < njobs; ++v )
1315 if( objvals ==
NULL )
1326 njobs, subvars, durations, demands, capacity) );
1371 (*infeasible) =
TRUE;
1375 (*unbounded) =
TRUE;
1386 for( v = 0; v < njobs; ++v )
1403 for( v = 0; v < njobs; ++v )
1425 for( v = 0; v < njobs; ++v )
1446 (*infeasible) =
FALSE;
1447 (*unbounded) =
FALSE;
1450 SCIPdebugMessage(
"solve independent cumulative condition with %d variables\n", njobs);
1457 njobs, capacity, hmin, hmax,
1458 maxnodes, timelimit, memorylimit,
1460 infeasible, unbounded, solved, error);
1470#ifdef SCIP_DISABLED_CODE
1489 (*infeasible) =
FALSE;
1490 (*unbounded) =
FALSE;
1493 SCIPdebugMsg(
scip,
"solve independent cumulative condition with %d variables\n", njobs);
1512 for( v = 0; v < njobs; ++v )
1520 if( objvals ==
NULL )
1529 timeinterval = lst - est + 1;
1530 assert(timeinterval > 0);
1533 minest =
MIN(minest, est);
1534 maxlct =
MAX(maxlct, lst + durations[v]);
1543 for( t = 0; t < timeinterval; ++t )
1556 binvars[v][t] = binvar;
1565 hmin =
MAX(hmin, minest);
1566 hmax =
MIN(hmax, maxlct);
1572 for( t = hmin; t < hmax; ++t )
1583 for( v = 0; v < njobs; ++v )
1596 duration = durations[v];
1600 if( t < est || t >= lst + duration )
1603 demand = demands[v];
1606 start =
MAX(t - duration + 1, est);
1611 for( k = start; k <= end; ++k )
1648 (*infeasible) =
TRUE;
1652 (*unbounded) =
TRUE;
1662 for( v = 0; v < njobs; ++v )
1672 timeinterval = lst - est + 1;
1675 for( t = 0; t < timeinterval; ++t )
1695 for( v = 0; v < njobs; ++v )
1705 timeinterval = lst - est + 1;
1708 for( t = 0; t < timeinterval; ++t )
1718 for( t = timeinterval - 1; t >= 0; --t )
1741 for( v = 0; v < njobs; ++v )
1751 timeinterval = lst - est + 1;
1753 for( t = 0; t < timeinterval; ++t )
1794 (*conshdlrdata)->eventhdlr = eventhdlr;
1797 (*conshdlrdata)->solveCumulative = solveCumulativeViaScipCp;
1799#ifdef SCIP_STATISTIC
1800 (*conshdlrdata)->nlbtimetable = 0;
1801 (*conshdlrdata)->nubtimetable = 0;
1802 (*conshdlrdata)->ncutofftimetable = 0;
1803 (*conshdlrdata)->nlbedgefinder = 0;
1804 (*conshdlrdata)->nubedgefinder = 0;
1805 (*conshdlrdata)->ncutoffedgefinder = 0;
1806 (*conshdlrdata)->ncutoffoverload = 0;
1807 (*conshdlrdata)->ncutoffoverloadTTEF = 0;
1809 (*conshdlrdata)->nirrelevantjobs = 0;
1810 (*conshdlrdata)->nalwaysruns = 0;
1811 (*conshdlrdata)->nremovedlocks = 0;
1812 (*conshdlrdata)->ndualfixs = 0;
1813 (*conshdlrdata)->ndecomps = 0;
1814 (*conshdlrdata)->ndualbranchs = 0;
1815 (*conshdlrdata)->nallconsdualfixs = 0;
1816 (*conshdlrdata)->naddedvarbounds = 0;
1817 (*conshdlrdata)->naddeddisjunctives = 0;
1859 for( v = 0; v < consdata->nvars; ++v )
1903 for( v = 0; v < consdata->nvars; ++v )
1921 nvars = consdata->nvars;
1924 for( v = 0; v <
nvars; ++v )
1926 consdata->downlocks[v] = locked;
1927 consdata->uplocks[v] = locked;
1961 (*consdata)->hmin = hmin;
1962 (*consdata)->hmax = hmax;
1964 (*consdata)->capacity = capacity;
1965 (*consdata)->demandrows =
NULL;
1966 (*consdata)->demandrowssize = 0;
1967 (*consdata)->ndemandrows = 0;
1968 (*consdata)->scoverrows =
NULL;
1969 (*consdata)->nscoverrows = 0;
1970 (*consdata)->scoverrowssize = 0;
1971 (*consdata)->bcoverrows =
NULL;
1972 (*consdata)->nbcoverrows = 0;
1973 (*consdata)->bcoverrowssize = 0;
1974 (*consdata)->nvars =
nvars;
1975 (*consdata)->varssize =
nvars;
1976 (*consdata)->signature = 0;
1977 (*consdata)->validsignature =
FALSE;
1978 (*consdata)->normalized =
FALSE;
1979 (*consdata)->covercuts =
FALSE;
1980 (*consdata)->propagated =
FALSE;
1981 (*consdata)->varbounds =
FALSE;
1982 (*consdata)->triedsolving =
FALSE;
1991 (*consdata)->linkingconss =
NULL;
1999 if( linkingconss !=
NULL )
2015 for( v = 0; v <
nvars; ++v )
2020 if( linkingconss !=
NULL )
2025 for( v = 0; v <
nvars; ++v )
2034 for( v = 0; v < (*consdata)->nvars; ++v )
2040 (*consdata)->vars =
NULL;
2041 (*consdata)->downlocks =
NULL;
2042 (*consdata)->uplocks =
NULL;
2043 (*consdata)->demands =
NULL;
2044 (*consdata)->durations =
NULL;
2045 (*consdata)->linkingconss =
NULL;
2049 (*consdata)->resstrength1 = -1.0;
2050 (*consdata)->resstrength2 = -1.0;
2051 (*consdata)->cumfactor1 = -1.0;
2052 (*consdata)->disjfactor1 = -1.0;
2053 (*consdata)->disjfactor2 = -1.0;
2054 (*consdata)->estimatedstrength = -1.0;
2073 for(
r = 0;
r < (*consdata)->ndemandrows; ++
r )
2081 (*consdata)->ndemandrows = 0;
2082 (*consdata)->demandrowssize = 0;
2085 for(
r = 0;
r < (*consdata)->nscoverrows; ++
r )
2093 (*consdata)->nscoverrows = 0;
2094 (*consdata)->scoverrowssize = 0;
2096 for(
r = 0;
r < (*consdata)->nbcoverrows; ++
r )
2104 (*consdata)->nbcoverrows = 0;
2105 (*consdata)->bcoverrowssize = 0;
2107 (*consdata)->covercuts =
FALSE;
2125 nvars = (*consdata)->nvars;
2126 varssize = (*consdata)->varssize;
2136 if( (*consdata)->linkingconss !=
NULL )
2138 for( v =
nvars-1; v >= 0; --v )
2140 assert((*consdata)->linkingconss[v] !=
NULL );
2176 for( v = 0; v < consdata->nvars; ++v )
2183 consdata->durations[v], consdata->demands[v]);
2185 SCIPinfoMessage(
scip, file,
")[%d,%d) <= %d", consdata->hmin, consdata->hmax, consdata->capacity);
2212 consdata->downlocks[pos] =
FALSE;
2213 consdata->uplocks[pos] =
FALSE;
2215 if( consdata->linkingconss !=
NULL )
2230 SCIPdebugMsg(
scip,
"remove variable <%s>[%g,%g] from cumulative constraint <%s>\n",
2236 if( pos != consdata->nvars - 1 )
2238 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
2239 consdata->downlocks[pos] = consdata->downlocks[consdata->nvars-1];
2240 consdata->uplocks[pos] = consdata->uplocks[consdata->nvars-1];
2241 consdata->demands[pos] = consdata->demands[consdata->nvars-1];
2242 consdata->durations[pos] = consdata->durations[consdata->nvars-1];
2244 if( consdata->linkingconss !=
NULL )
2246 consdata->linkingconss[pos]= consdata->linkingconss[consdata->nvars-1];
2251 consdata->validsignature =
FALSE;
2252 consdata->normalized =
FALSE;
2270 nvars = consdata->nvars;
2276 for( v = 0; v <
nvars; ++v )
2281 var = consdata->vars[v];
2297 consdata->linkingconss[v] = cons;
2342 int* startsolvalues;
2358 (*violated) =
FALSE;
2374 for ( j = 0; j <
nvars; ++j )
2386 startsolvalues[j] =
MAX(solvalue, hmin);
2387 startindices[j] = j;
2389 endsolvalues[j] =
MAX(solvalue + durations[j], hmin);
2400 freecapacity = capacity;
2405 for( j = 0; j <
nvars; ++j )
2408 curtime = startsolvalues[j];
2410 if( curtime >= hmax )
2414 freecapacity -= demands[startindices[j]];
2415 while( j+1 <
nvars && startsolvalues[j+1] == curtime )
2418 freecapacity -= demands[startindices[j]];
2422 while( endindex < nvars && curtime >= endsolvalues[endindex] )
2424 freecapacity += demands[endindices[endindex]];
2427 assert(freecapacity <= capacity);
2430 if( absviol < (
SCIP_Real) (-freecapacity) )
2432 absviol = -freecapacity;
2437 if( freecapacity < 0 && curtime >= hmin )
2451 ";\nviolation: at time point %d available capacity = %d, needed capacity = %d\n",
2452 curtime, capacity, capacity - freecapacity);
2454 for(
i = 0;
i <= j; ++
i )
2456 if( startsolvalues[
i] + durations[startindices[
i]] > curtime )
2460 demands[startindices[
i]]);
2506 consdata->durations, consdata->demands, consdata->capacity, consdata->hmin, consdata->hmax,
2507 violated, cons, printreason) );
2551 SCIPdebugMsg(
scip,
"variable <%s>: (demand %d) resolve propagation of core time algorithm (peak %d)\n",
2556 capacity -= inferdemand;
2566 for( j = 0; j < nvars && capacity >= 0; ++j )
2572 if(
var == infervar )
2575 duration = durations[j];
2584 SCIPdebugMsg(
scip,
"variable <%s>: glb=[%g,%g] conflict=[%g,%g] (duration %d, demand %d)\n",
2594 if( inferpeak < ect && lst <= inferpeak )
2596 capacity -= demands[j];
2599 maxlst =
MAX(maxlst, lst);
2600 minect =
MIN(minect, ect);
2603 if( explanation !=
NULL )
2604 explanation[j] =
TRUE;
2621 if( inferpeak < ect && lst <= inferpeak )
2623 capacity -= demands[j];
2626 maxlst =
MAX(maxlst, lst);
2627 minect =
MIN(minect, ect);
2630 if( explanation !=
NULL )
2631 explanation[j] =
TRUE;
2647 for( j = 0; j <
nvars; ++j )
2653 if(
var == infervar || reported[j] )
2656 duration = durations[j];
2669 SCIPdebugMsg(
scip,
"variable <%s>: loc=[%g,%g] glb=[%g,%g] (duration %d, demand %d)\n",
2674 if( inferpeak < ect && lst <= inferpeak )
2677 canddemands[ncands] = demands[j];
2680 capacity -= demands[j];
2691 while( capacity + canddemands[ncands-1] < 0 )
2694 capacity += canddemands[ncands];
2699 for(
c = 0;
c < ncands; ++
c )
2704 duration = durations[cands[
c]];
2709 maxlst =
MAX(maxlst, lst);
2710 minect =
MIN(minect, ect);
2714 SCIPdebugMsg(
scip,
"infer peak %d, relaxed peak %d, lst %d, ect %d\n", inferpeak, relaxedpeak, maxlst, minect);
2715 assert(inferpeak >= maxlst);
2716 assert(inferpeak < minect);
2719 if( relaxedpeak < inferpeak )
2721 inferpeak =
MAX(maxlst, relaxedpeak);
2723 else if( relaxedpeak > inferpeak )
2725 inferpeak =
MIN(minect-1, relaxedpeak);
2727 assert(inferpeak >= hmin);
2728 assert(inferpeak < hmax);
2729 assert(inferpeak >= maxlst);
2730 assert(inferpeak < minect);
2733 for(
c = 0;
c < ncands; ++
c )
2740 duration = durations[cands[
c]];
2751 if( explanation !=
NULL )
2752 explanation[cands[
c]] =
TRUE;
2761 if( provedpeak !=
NULL )
2762 *provedpeak = inferpeak;
2782 ect = est + duration;
2783 lct = lst + duration;
2786 if( lct <= end && est >= begin )
2789 assert(lst <= end && ect >= begin);
2797 return MIN3(left, right, end - begin);
2835 requiredenergy = ((
SCIP_Longint) end - begin) * capacity;
2842 for( v = 0; v <
nvars; ++v )
2858 demand = demands[v];
2861 duration = durations[v];
2865 if( infervar ==
var )
2873 SCIPdebugMsg(
scip,
"inference variable <%s>[%g,%g] %s %g (duration %d, demand %d)\n",
2896 right =
MIN3(end - lst, end - begin, duration);
2907 left =
MIN(lct - begin + 1, end - begin);
2911 overlap =
MIN(left, right);
2913 assert(overlap <= end - begin);
2914 assert(overlap <= duration);
2944 left =
MIN3(ect - begin, end - begin, duration);
2954 right =
MIN(end - est + 1, end - begin);
2958 overlap =
MIN(left, right);
2960 assert(overlap <= end - begin);
2961 assert(overlap <= duration);
2977 if( explanation !=
NULL )
2978 explanation[v] =
TRUE;
2992 if( est + duration > begin && lst < end )
2995 glbenergy =
computeOverlap(begin, end, est, lst, duration) * demand;
2998 requiredenergy -= glbenergy;
3000 if( explanation !=
NULL )
3001 explanation[v] =
TRUE;
3011 if( est + duration > begin && lst < end )
3016 locenergies[v] = overlaps[v] * demand - glbenergy;
3017 assert(locenergies[v] >= 0);
3025 for( v = 0; v < nvars && requiredenergy >= 0; ++v )
3041 duration = durations[idx];
3044 overlap = overlaps[v];
3047 requiredenergy -= locenergies[v];
3049 if( requiredenergy < -1 )
3053 demand = demands[idx];
3056 overlap += (int)((requiredenergy + 1) / demand);
3059 requiredenergy += locenergies[v];
3061 assert(requiredenergy < 0);
3066 relaxlb = begin - duration + overlap;
3067 relaxub = end - overlap;
3069 SCIPdebugMsg(
scip,
"variable <%s> glb=[%g,%g] loc=[%g,%g], conf=[%g,%g], added=[%d,%d] (demand %d, duration %d)\n",
3074 relaxlb, relaxub, demands[idx], duration);
3079 if( explanation !=
NULL )
3080 explanation[idx] =
TRUE;
3083 assert(requiredenergy < 0);
3126 if( inferpos >=
nvars ||
vars[inferpos] != infervar )
3129 for( inferpos = 0; inferpos <
nvars &&
vars[inferpos] != infervar; ++inferpos )
3135 inferdemand = demands[inferpos];
3136 inferduration = durations[inferpos];
3145 SCIPdebugMsg(
scip,
"variable <%s>: upper bound changed from %g to %g (relaxed %g)\n",
3159 relaxedpeak =
MIN(relaxedpeak, hmax-1);
3165 relaxedpeak =
MAX(relaxedpeak, inferpeak);
3166 assert(relaxedpeak >= inferpeak);
3167 assert(relaxedpeak >= hmin);
3173 SCIPdebugMsg(
scip,
"variable <%s>: lower bound changed from %g to %g (relaxed %g)\n",
3186 relaxedpeak =
MAX(relaxedpeak, hmin);
3192 relaxedpeak =
MIN(relaxedpeak, inferpeak);
3193 assert(relaxedpeak < hmax);
3198 infervar, inferdemand, inferpeak, relaxedpeak, bdchgidx, usebdwidening, &provedpeak, explanation) );
3227 if( explanation !=
NULL )
3228 explanation[inferpos] =
TRUE;
3242 begin =
MAX(begin, hmin);
3243 end =
MIN(end, hmax);
3246 begin, end, infervar, boundtype, bdchgidx, relaxedbd, usebdwidening, explanation) );
3277 int* alternativelbs,
3278 int* alternativeubs,
3286 for( v = 0; v <
nvars; ++v )
3302 if( alternativelbs[v] <= ub )
3320 if( alternativeubs[v] >= lb )
3348#if defined SCIP_DEBUG && !defined NDEBUG
3360 assert(starttimes[*idx] == curtime);
3362 assert(freecapacity != idx);
3365 (*freecapacity) -= consdata->demands[startindices[*idx]];
3367 while( (*idx)+1 <
nvars && starttimes[(*idx)+1] == curtime )
3370 (*freecapacity) -= consdata->demands[startindices[(*idx)]];
3371 assert(freecapacity != idx);
3390#if defined SCIP_DEBUG && !defined NDEBUG
3396 while( endtimes[*idx] <= curtime && *idx <
nvars)
3398 (*freecapacity) += consdata->demands[endindices[*idx]];
3433 nvars = consdata->nvars;
3436 *timepoint = consdata->hmax;
3447 starttimes, endtimes, startindices, endindices);
3450 freecapacity = consdata->capacity;
3451 hmin = consdata->hmin;
3452 hmax = consdata->hmax;
3455 for( j = 0; j <
nvars; ++j )
3457 curtime = starttimes[j];
3460 if( curtime >= hmax )
3469 assert(freecapacity <= consdata->capacity);
3476 if( freecapacity < 0 && curtime >= hmin )
3478 *timepoint = curtime;
3510 SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal,
NULL) );
3515 for(
c = 0;
c < nconss; ++
c )
3535 if( curtime < consdata->hmin || curtime >= consdata->hmax )
3539 for( j = 0; j < consdata->nvars; ++j )
3545 var = consdata->vars[j];
3555 if( lb <= curtime && ub + consdata->durations[j] > curtime && lb < ub )
3561 score =
MIN(solval - lb, ub - solval) / ((
SCIP_Real)ub-lb);
3597 if( nbranchcands > 0 )
3608 for(
c = 0;
c < nconss && !violated; ++
c )
3648 nvars = consdata->nvars;
3649 vars = consdata->vars;
3650 downlocks = consdata->downlocks;
3651 uplocks = consdata->uplocks;
3654 for( v = 0; v <
nvars; ++v )
3719 if( ncheckconss == 1 )
3769 if( consdata->triedsolving )
3779 consdata->triedsolving =
TRUE;
3781 SCIPdebugMsg(
scip,
"the cumulative constraint <%s> is independent from rest of the problem (%d variables, %d constraints)\n",
3785 nvars = consdata->nvars;
3786 vars = consdata->vars;
3792 for( v = 0; v <
nvars; ++v )
3823 consdata->hmin, consdata->hmax, timelimit, memorylimit, maxnodes, &solved,
cutoff, unbounded, &error) );
3825 if( !(*
cutoff) && !(*unbounded) && !error )
3833 for( v = 0; v <
nvars; ++v )
3836 if( lbs[v] + 0.5 > ubs[v] )
3844 consdata->triedsolving =
FALSE;
3855 consdata->triedsolving =
FALSE;
3864 consdata->triedsolving =
FALSE;
3906 SCIPdebugMsg(
scip,
"detected infeasibility due to adding a core to the core resource profile\n");
3916 infervar, inferdemand, inferpeak, inferpeak,
NULL, usebdwidening,
NULL, explanation) );
3932 *initialized =
TRUE;
3976 duration = durations[idx];
3979 demand = demands[idx];
3991 SCIPdebugMsg(
scip,
"propagate earliest start time (lower bound) (pos %d)\n", pos);
4009 ect = est + duration;
4037 newlb =
MIN(newlb, ect);
4046 var, duration, demand, newlb-1, usebdwidening, initialized, explanation) );
4048 if( explanation !=
NULL )
4049 explanation[idx] =
TRUE;
4138 lct = lst + duration;
4196 newub =
MAX(newub, lst) - duration;
4230 lct = lst + duration;
4252 int* coreEnergyAfterEst,
4253 int* coreEnergyAfterLct
4262 t = ntimepoints - 1;
4266 for( v =
nvars-1; v >= 0; --v )
4284 coreEnergyAfterEst[v] = energy;
4287 t = ntimepoints - 1;
4291 for( v =
nvars-1; v >= 0; --v )
4309 coreEnergyAfterLct[v] = energy;
4334 for( v = 0; v <
nvars; ++ v)
4345 duration = durations[v];
4350 ect = est + duration;
4351 lct = lst + duration;
4362 leftadjust =
MAX(0, hmin - est);
4365 rightadjust =
MAX(0, lct - hmax);
4368 flexenergies[v] = duration - leftadjust - rightadjust - core;
4369 flexenergies[v] =
MAX(0, flexenergies[v]);
4370 flexenergies[v] *= demands[v];
4371 assert(flexenergies[v] >= 0);
4374 ects[v] =
MIN(ect, lst);
4377 lsts[v] =
MAX(ect, lst);
4415 if( !conshdlrdata->ttefinfer )
4419 if( est >= end || ect <= begin )
4425 if( est >= begin && ect <= end )
4446 newlb = end - (int) (energy / demand);
4451 if( newlb > lct - duration )
4473 (*initialized) =
TRUE;
4478 else if( newlb > (*bestlb) )
4529 if( !conshdlrdata->ttefinfer )
4533 if( lst >= end || lct <= begin )
4539 if( lst >= begin && lct <= end )
4560 newub = begin - duration + (int) (energy / demand);
4587 (*initialized) =
TRUE;
4592 else if( newub < (*bestub) )
4629 int* coreEnergyAfterEst,
4630 int* coreEnergyAfterLct,
4636 int coreEnergyAfterEnd;
4651 for( v = 0; v <
nvars; ++v )
4656 est =
MIN(est, start);
4657 lct =
MAX(lct, end);
4661 hmin =
MAX(hmin, est);
4662 hmax =
MIN(hmax, lct);
4665 coreEnergyAfterEnd = -1;
4667 maxavailable = ((
SCIP_Longint) hmax - hmin) * capacity;
4668 minavailable = maxavailable;
4680 for( v =
nvars-1; v >= 0 && !(*cutoff); --v )
4699 assert(v == 0 || lcts[v-1] <= lcts[v]);
4715 if( !conshdlrdata->ttefinfer && end <= hmax && minavailable < maxavailable )
4719 assert(coreEnergyAfterLct[v] >= coreEnergyAfterEnd);
4720 assert(coreEnergyAfterEnd >= 0);
4723 freeenergy = capacity * ((
SCIP_Longint) end - lct) - coreEnergyAfterLct[v] + coreEnergyAfterEnd;
4725 if( freeenergy <= minavailable )
4735 coreEnergyAfterEnd = coreEnergyAfterLct[v];
4738 minavailable = maxavailable;
4747 for(
i = nests-1;
i >= 0; --
i )
4777 if( ((
SCIP_Longint) end - est) * capacity >= totalenergy )
4783 duration = durations[idx];
4786 demand = demands[idx];
4798 if( minavailable < maxavailable && est < minbegin )
4804 var, duration, demand, est, lst, lct, minbegin, end, minavailable, &(newubs[idx]), &(ubinferinfos[idx]),
4805 initialized, explanation,
cutoff) );
4811 SCIPdebugMsg(
scip,
"check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, lst of free part <%d>\n",
4828 assert(flexenergies[idx] >= 0);
4829 flexenergy += flexenergies[idx];
4842 energy =
MIN(flexenergies[idx], demands[idx] *
MAX(0, (end - lst)));
4843 assert(end - lst < duration);
4847 flexenergy += energy;
4850 candenergy =
MIN(flexenergies[idx], demands[idx] * (end - begin)) - energy;
4854 if( candenergy > lbenergy )
4856 lbenergy = candenergy;
4861 SCIPdebugMsg(
scip,
"time window [%d,%d) flexible energy <%d>\n", begin, end, flexenergy);
4862 assert(coreEnergyAfterEst[
i] >= coreEnergyAfterEnd);
4865 freeenergy = capacity * ((
SCIP_Longint) end - begin) - flexenergy - coreEnergyAfterEst[
i] + coreEnergyAfterEnd;
4868 if( freeenergy < 0 )
4870 SCIPdebugMsg(
scip,
"analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
4880 conshdlrdata->usebdwidening, explanation) );
4882 (*initialized) =
TRUE;
4894 if( lbenergy > 0 && freeenergy < lbenergy )
4906 newlb = end - (int)(energy / demands[lbcand]);
4918 relaxedbd = lst + 1.0;
4925 conshdlrdata->usebdwidening, explanation) );
4927 (*initialized) =
TRUE;
4933 else if( newlb > newlbs[lbcand] )
4942 newlbs[lbcand] = newlb;
4947 if( minavailable > freeenergy )
4949 minavailable = freeenergy;
4952 assert(minavailable >= 0);
4980 int* coreEnergyAfterEst,
4981 int* coreEnergyAfterLct,
4987 int coreEnergyAfterStart;
5008 for( v = 0; v <
nvars; ++v )
5013 minest =
MIN(minest, start);
5014 maxlct =
MAX(maxlct, end);
5018 hmin =
MAX(hmin, minest);
5019 hmax =
MIN(hmax, maxlct);
5021 maxavailable = ((
SCIP_Longint) hmax - hmin) * capacity;
5033 for( v = 0; v <
nvars; ++v )
5065 coreEnergyAfterStart = coreEnergyAfterEst[v];
5068 minavailable = maxavailable;
5106 if( ((
SCIP_Longint) lct - begin) * capacity >= totalenergy )
5112 duration = durations[idx];
5115 demand = demands[idx];
5127 if( minavailable < maxavailable && lct > minend )
5133 var, duration, demand, est, ect, lct, begin, minend, minavailable, &(newlbs[idx]), &(lbinferinfos[idx]),
5134 initialized, explanation,
cutoff) );
5140 SCIPdebugMsg(
scip,
"check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, ect of free part <%d>\n",
5157 assert(flexenergies[idx] >= 0);
5158 flexenergy += flexenergies[idx];
5171 energy =
MIN(flexenergies[idx], demands[idx] *
MAX(0, (ect - begin)));
5172 assert(ect - begin < duration);
5176 flexenergy += energy;
5179 candenergy =
MIN(flexenergies[idx], demands[idx] * (end - begin)) - energy;
5183 if( candenergy > ubenergy )
5185 ubenergy = candenergy;
5190 SCIPdebugMsg(
scip,
"time window [%d,%d) flexible energy <%d>\n", begin, end, flexenergy);
5191 assert(coreEnergyAfterLct[
i] <= coreEnergyAfterStart);
5194 freeenergy = capacity * ((
SCIP_Longint) end - begin) - flexenergy - coreEnergyAfterStart + coreEnergyAfterLct[
i];
5197 if( freeenergy < 0 )
5199 SCIPdebugMsg(
scip,
"analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
5209 conshdlrdata->usebdwidening, explanation) );
5211 (*initialized) =
TRUE;
5223 if( ubenergy > 0 && freeenergy < ubenergy )
5229 duration = durations[ubcand];
5238 newub = begin - duration + (int)(energy / demands[ubcand]);
5240 if( newub < ect - duration )
5249 relaxedbd = ect - duration - 1.0;
5256 conshdlrdata->usebdwidening, explanation) );
5258 (*initialized) =
TRUE;
5264 else if( newub < newubs[ubcand] )
5273 newubs[ubcand] = newub;
5278 if( minavailable > freeenergy )
5280 minavailable = freeenergy;
5283 assert(minavailable >= 0);
5319 int* coreEnergyAfterEst;
5320 int* coreEnergyAfterLct;
5341 if( !conshdlrdata->ttefcheck )
5362 for( v = 0; v <
nvars; ++v )
5366 lbinferinfos[v] = 0;
5367 ubinferinfos[v] = 0;
5371 collectDataTTEF(
scip,
nvars,
vars, durations, demands, hmin, hmax, permests, ests, permlcts, lcts, ects, lsts, flexenergies);
5384 newlbs, newubs, lbinferinfos, ubinferinfos, lsts, flexenergies,
5385 permests, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation,
cutoff) );
5389 newlbs, newubs, lbinferinfos, ubinferinfos, ects, flexenergies,
5390 permlcts, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation,
cutoff) );
5393 for( v = 0; v <
nvars && !(*cutoff); ++v )
5401 TRUE, &infeasible, &tightened) );
5422 TRUE, &infeasible, &tightened) );
5465 conshdlrdata->usebdwidening, explanation) );
5467 (*initialized) =
TRUE;
5541 if( !conshdlrdata->ttinfer )
5546 SCIPdebugMsg(
scip,
"propagate cores of cumulative condition of constraint <%s>[%d,%d) <= %d\n",
5556 for( v = 0; v <
nvars; ++v )
5569 duration = durations[v];
5581 if( lst + duration <= hmin || est >= hmax )
5585 begin =
MAX(hmin, lst);
5586 end =
MIN(hmax, est + duration);
5588 demand = demands[v];
5594 SCIPdebugMsg(
scip,
"variable <%s>[%g,%g] (duration %d, demand %d): remove core [%d,%d)\n",
5602 profile, v, nchgbds, conshdlrdata->usebdwidening, initialized, explanation,
cutoff) );
5609 profile, v, nchgbds) );
5619 begin =
MAX(hmin, lst);
5620 end =
MIN(hmax, est + duration);
5627 SCIPdebugMsg(
scip,
"variable <%s>[%d,%d] (duration %d, demand %d): add core [%d,%d)\n",
5636 var, duration, demand,
SCIPprofileGetTime(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) );
5638 if( explanation !=
NULL )
5639 explanation[v] =
TRUE;
5689 SCIPdebugMsg(
scip,
"update envelop starting from node <%p>\n", (
void*)node);
5694 while( node !=
NULL )
5713 if( leftdata->enveloptheta >= 0 )
5715 assert(rightdata->energytheta != -1);
5716 nodedata->enveloptheta =
MAX(leftdata->enveloptheta + rightdata->energytheta, rightdata->enveloptheta);
5719 nodedata->enveloptheta = rightdata->enveloptheta;
5721 assert(leftdata->energytheta != -1);
5722 assert(rightdata->energytheta != -1);
5723 nodedata->energytheta = leftdata->energytheta + rightdata->energytheta;
5725 if( leftdata->enveloplambda >= 0 )
5727 assert(rightdata->energytheta != -1);
5728 nodedata->enveloplambda =
MAX(leftdata->enveloplambda + rightdata->energytheta, rightdata->enveloplambda);
5731 nodedata->enveloplambda = rightdata->enveloplambda;
5733 if( leftdata->enveloptheta >= 0 && rightdata->energylambda >= 0 )
5734 nodedata->enveloplambda =
MAX(
nodedata->enveloplambda, leftdata->enveloptheta + rightdata->energylambda);
5738 if( leftdata->energylambda >= 0 && rightdata->energylambda >= 0 )
5740 assert(rightdata->energytheta != -1);
5741 assert(leftdata->energytheta != -1);
5742 nodedata->energylambda =
MAX(leftdata->energylambda + rightdata->energytheta, leftdata->energytheta + rightdata->energylambda);
5744 else if( rightdata->energylambda >= 0 )
5746 assert(leftdata->energytheta != -1);
5747 nodedata->energylambda = leftdata->energytheta + rightdata->energylambda;
5749 else if( leftdata->energylambda >= 0 )
5751 assert(rightdata->energytheta != -1);
5752 nodedata->energylambda = leftdata->energylambda + rightdata->energytheta;
5833 if( grandparent !=
NULL )
5943 if(
nodedata->key < leafdata->key )
5956 newnodedata = &nodedatas[*nnodedatas];
5957 nodedataidx[*nnodedatas] = *nnodedatas;
5961 newnodedata->var =
NULL;
5963 newnodedata->est = INT_MIN;
5964 newnodedata->lct = INT_MAX;
5965 newnodedata->duration = 0;
5966 newnodedata->demand = 0;
5967 newnodedata->enveloptheta = -1;
5968 newnodedata->energytheta = 0;
5969 newnodedata->enveloplambda = -1;
5970 newnodedata->energylambda = -1;
5971 newnodedata->idx = -1;
5972 newnodedata->intheta =
TRUE;
5980 if( parent !=
NULL )
5997 if(
nodedata->key < leafdata->key )
6009 newnodedata->key = leafdata->key;
6059 assert(rightdata->energytheta != -1);
6061 if( leftdata->energylambda >= 0 &&
nodedata->energylambda == leftdata->energylambda + rightdata->energytheta )
6064 assert(leftdata->energytheta != -1);
6065 assert(rightdata->energylambda != -1);
6066 assert(
nodedata->energylambda == leftdata->energytheta + rightdata->energylambda);
6108 assert(rightdata->energytheta != -1);
6111 if( leftdata->enveloplambda >= 0 &&
nodedata->enveloplambda == leftdata->enveloplambda + rightdata->energytheta )
6113 else if( leftdata->enveloptheta >= 0 && rightdata->energylambda >= 0
6114 &&
nodedata->enveloplambda == leftdata->enveloptheta + rightdata->energylambda )
6117 assert(rightdata->enveloplambda != -1);
6150 omegaset[*nelements] = node;
6203 assert(rightdata->energytheta != -1);
6205 if( leftdata->enveloptheta >= 0 &&
nodedata->enveloptheta == leftdata->enveloptheta + rightdata->energytheta )
6212 assert(rightdata->enveloptheta != -1);
6258 assert(rightdata->energytheta != -1);
6260 if( leftdata->energylambda >= 0 &&
nodedata->energylambda == leftdata->energylambda + rightdata->energytheta )
6267 assert(leftdata->energytheta != -1);
6268 assert(rightdata->energylambda != -1);
6269 assert(
nodedata->energylambda == leftdata->energytheta + rightdata->energylambda);
6318 assert(rightdata->energytheta != -1);
6320 if( leftdata->enveloplambda >= 0 &&
nodedata->enveloplambda == leftdata->enveloplambda + rightdata->energytheta )
6327 if( leftdata->enveloptheta >= 0 && rightdata->energylambda >= 0
6328 &&
nodedata->enveloplambda == leftdata->enveloptheta + rightdata->energylambda )
6335 assert(rightdata->enveloplambda != -1);
6358 SCIPdebugMessage(
"variable <%s>: loc=[%g,%g] glb=[%g,%g] (duration %d, demand %d)\n",
6363 return nodedata->demand * duration;
6376 return (est1 - est2);
6386 return (nodedatas[ind1].lct - nodedatas[ind2].lct);
6417 SCIPdebugMsg(
scip,
"est=%d, lct=%d, propest %u, reportedenergy %d, shift %d\n", est, lct, propest, reportedenergy, shift);
6428 for( j = 0; j < nleaves && reportedenergy <= energy; ++j )
6444 assert(reportedenergy > energy);
6472 for( j = nleaves-1; j >= 0; --j )
6492 if( explanation !=
NULL )
6496 (*initialized) =
TRUE;
6564 for( j = ncands-1; j >= 0 && !(*cutoff); --j )
6595 assert(!leafdata->intheta);
6596 assert(leafdata->duration > 0);
6597 assert(leafdata->est >= 0);
6600 if( leafdata->est + leafdata->duration >=
nodedata->lct )
6622 assert(nelements < ncands);
6629 SCIPdebugMsg(
scip,
"an overload was detected duration edge-finder propagattion\n");
6633 conshdlrdata->usebdwidening, initialized, explanation) );
6639 else if( newest > 0 )
6661 TRUE, &infeasible, &tightened) );
6683 TRUE, &infeasible, &tightened) );
6693 leafdata->est = newest;
6712 if( explanation !=
NULL )
6713 explanation[leafdata->idx] =
TRUE;
6716 for(
i = 0;
i < nelements; ++
i )
6724 if( explanation !=
NULL )
6728 (*initialized) =
TRUE;
6822 for( j = 0; j <
nvars; ++j )
6827 shift =
MAX(shift, lct);
6834 for( j = 0; j <
nvars; ++j )
6848 duration = durations[j];
6860 if( conshdlrdata->useadjustedjobs )
6864 leftadjust = (hmin - est);
6869 rightadjust = (lct - hmax);
6876 if( duration - leftadjust - rightadjust <= 0 )
6879 else if( est < hmin || lct > hmax )
6882 energy = demands[j] * (duration - leftadjust - rightadjust);
6885 totalenergy += energy;
6908 nodedataidx[ncands] = ncands;
6920 nodedata->rightadjust = rightadjust;
6935 nnodedatas = ncands;
6938 SCIPsortInd(nodedataidx, compNodedataLct, (
void*)nodedatas, ncands);
6945 for( j = 0; j < ncands; ++j )
6950 idx = nodedataidx[j];
6955 if( ((
SCIP_Longint) nodedatas[idx].lct - nodedatas[idx].est) * capacity >= totalenergy )
6958 nodedatas[idx].est = -1;
6970 leaves[ninsertcands] = leaf;
6978 if( rootdata->enveloptheta > (
SCIP_Longint) capacity * nodedatas[idx].lct )
6980 SCIPdebugMsg(
scip,
"detects cutoff due to overload in time window [?,%d) (ncands %d)\n", nodedatas[idx].lct, j);
6999 est = nodedatas[idx].est;
7000 lct = nodedatas[idx].lct;
7005 for( j = j+1; j < ncands; ++j )
7012 idx = nodedataidx[j];
7024 duration -= (est - glbest);
7027 duration -= (glblct - lct);
7031 glbenery +=
nodedata->demand * duration;
7033 if( explanation !=
NULL )
7040 conshdlrdata->usebdwidening, initialized, explanation) );
7042 else if( ninsertcands > 1 && conshdlrdata->efinfer )
7046 propest, shift, initialized, explanation, nchgbds,
cutoff) );
7089 if( !conshdlrdata->efcheck )
7094 cons,
TRUE, initialized, explanation, nchgbds,
cutoff) );
7101 if( !conshdlrdata->efinfer )
7106 cons,
FALSE, initialized, explanation, nchgbds,
cutoff) );
7145 (*redundant) =
TRUE;
7161 for( j = 0; j <
nvars; ++j )
7163 assert(durations[j] > 0);
7173 if( lb >= hmax || ub <= hmin - durations[j] )
7176 starttimes[njobs] =
MAX(lb, hmin);
7177 startindices[njobs] = j;
7179 endtimes[njobs] =
MIN(ub == INT_MAX ? ub : ub + durations[j], hmax);
7180 endindices[njobs] = j;
7181 assert(starttimes[njobs] <= endtimes[njobs]);
7190 freecapacity = capacity;
7193 for( j = 0; j < njobs; ++j )
7195 curtime = starttimes[j];
7198 if( curtime >= hmax )
7202 freecapacity -= demands[startindices[j]];
7203 while( j+1 < njobs && starttimes[j+1] == curtime )
7206 freecapacity -= demands[startindices[j]];
7210 while( endtimes[endindex] <= curtime )
7212 freecapacity += demands[endindices[endindex]];
7215 assert(freecapacity <= capacity);
7218 if( freecapacity < 0 && curtime >= hmin )
7220 (*redundant) =
FALSE;
7257 for( v = 0; v <
nvars; ++v )
7274 duration = durations[v];
7277 demand = demands[v];
7285 if( lst + duration <= hmin || est >= hmax )
7289 begin =
MAX(hmin, lst);
7290 end =
MIN(hmax, est + duration);
7296 SCIPdebugMsg(
scip,
"variable <%s>[%d,%d] (duration %d, demand %d): add core [%d,%d)\n",
7310 var, duration, demand,
SCIPprofileGetTime(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) );
7312 if( explanation !=
NULL )
7313 explanation[v] =
TRUE;
7369 SCIP_CALL_TERMINATE( retcode,
createCoreProfile(
scip, conshdlrdata, profile,
nvars,
vars, durations, demands, capacity, hmin, hmax,
7370 initialized, explanation,
cutoff), TERMINATE );
7375 SCIP_CALL_TERMINATE( retcode,
propagateTimetable(
scip, conshdlrdata, profile,
nvars,
vars, durations, demands, capacity, hmin, hmax, cons,
7376 nchgbds, initialized, explanation,
cutoff), TERMINATE );
7382 SCIP_CALL_TERMINATE( retcode,
propagateEdgeFinding(
scip, conshdlrdata,
nvars,
vars, durations, demands, capacity, hmin, hmax,
7383 cons, initialized, explanation, nchgbds,
cutoff), TERMINATE );
7389 SCIP_CALL_TERMINATE( retcode,
propagateTTEF(
scip, conshdlrdata, profile,
nvars,
vars, durations, demands, capacity, hmin, hmax, cons,
7390 nchgbds, initialized, explanation,
cutoff), TERMINATE );
7422 oldnchgbds = *nchgbds;
7423 initialized =
FALSE;
7437 consdata->nvars, consdata->vars, consdata->durations, consdata->demands, consdata->capacity,
7438 consdata->hmin, consdata->hmax, cons,
7439 nchgbds, &redundant, &initialized,
NULL,
cutoff) );
7443 SCIPdebugMsg(
scip,
"%s deletes cumulative constraint <%s> since it is redundant\n",
7463 if( *
cutoff || *nchgbds > oldnchgbds )
7470 consdata->propagated =
TRUE;
7524 leftimpllbs, leftimplubs, leftproplbs, leftpropubs,
cutoff) );
7559 rightimpllbs, rightimplubs, rightproplbs, rightpropubs,
cutoff) );
7687 int* alternativelbs,
7688 int* alternativeubs,
7697 for(
c = 0;
c < nconss; ++
c )
7714 assert(consdata->nvars > 1);
7739 hmin = consdata->hmin;
7740 hmax = consdata->hmax;
7746 nvars = consdata->nvars;
7748 for( v = 0; v <
nvars; ++v )
7754 var = consdata->vars[v];
7769 if( consdata->downlocks[v] )
7776 ect = est + consdata->durations[v];
7778 if( ect <= hmin || hmin >= hmax )
7780 else if( est < hmin && alternativelbs[idx] >= (hmin + 1 - constant) / scalar )
7782 alternativelbs[idx] = (hmin + 1 - constant) / scalar;
7788 if( consdata->uplocks[v] )
7794 duration = consdata->durations[v];
7798 lct = lst + duration;
7800 if( lst >= hmax || hmin >= hmax )
7802 else if( lct > hmax && alternativeubs[idx] <= ((hmax - 1 - constant) / scalar) - duration )
7804 alternativeubs[idx] = ((hmax - 1 - constant) / scalar) - duration;
7820 int* alternativelbs,
7821 int* alternativeubs,
7848 for( v = 0; v <
nvars; ++v )
7861 if( alternativelbs[v] == INT_MAX && alternativeubs[v] == INT_MIN )
7877 if( alternativelbs[v] > ub )
7899 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
7900 nfixedvars, &success,
cutoff) );
7923 if( alternativeubs[v] < lb )
7945 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
7946 nfixedvars, &success,
cutoff) );
7985 int* alternativelbs;
7986 int* alternativeubs;
7995 oldnfixedvars = *nfixedvars;
8004 for( v = 0; v <
nvars; ++v )
8008 alternativelbs[v] = INT_MAX;
8009 alternativeubs[v] = INT_MIN;
8019 if( !(*
cutoff) && oldnfixedvars == *nfixedvars && branched !=
NULL )
8072 nvars = consdata->nvars;
8079 remainingcap = consdata->capacity;
8082 for( j = 0; j <
nvars; ++j )
8089 if( startvalues[j] <= time && ub + consdata->durations[j] > time )
8092 if( startvalues[j] == ub )
8094 remainingcap -= consdata->demands[j];
8098 demands[nflexible] = consdata->demands[j];
8099 flexibleids[nflexible] = j;
8104 assert(remainingcap >= 0);
8120 while( j < nflexible && sumdemand <= remainingcap )
8122 sumdemand += demands[j];
8128 assert(sumdemand > remainingcap);
8129 assert(bigcoversize < nflexible);
8141 for( j = 0; j < nflexible; ++j )
8153 idx = flexibleids[j];
8166 start = time - consdata->durations[idx] + 1;
8167 end =
MIN(time, ub);
8170 for(
b = 0;
b < nbinvars; ++
b )
8172 if( vals[
b] < start || vals[
b] < lb )
8186 if( consdata->bcoverrowssize == 0 )
8188 consdata->bcoverrowssize = 10;
8191 if( consdata->nbcoverrows == consdata->bcoverrowssize )
8193 consdata->bcoverrowssize *= 2;
8197 consdata->bcoverrows[consdata->nbcoverrows] = row;
8198 consdata->nbcoverrows++;
8208 while( sumdemand <= remainingcap )
8211 sumdemand += demands[j];
8215 smallcoversize = nflexible - (j + 1) - 1;
8216 while( j > 0 && demands[j] == demands[nflexible-1] )
8219 assert(smallcoversize < nflexible);
8221 if( smallcoversize != 1 || smallcoversize != nflexible - (j + 1) - 1 )
8230 for( j = j + 1; j < nflexible; ++j )
8242 idx = flexibleids[j];
8255 start = time - consdata->durations[idx] + 1;
8256 end =
MIN(time, ub);
8259 for(
b = 0;
b < nbinvars; ++
b )
8261 if( vals[
b] < start || vals[
b] < lb )
8274 if( consdata->scoverrowssize == 0 )
8276 consdata->scoverrowssize = 10;
8279 if( consdata->nscoverrows == consdata->scoverrowssize )
8281 consdata->scoverrowssize *= 2;
8285 consdata->scoverrows[consdata->nscoverrows] = row;
8286 consdata->nscoverrows++;
8307 int* startvaluessorted;
8308 int* endvaluessorted;
8330 if( consdata->vars ==
NULL )
8333 nvars = consdata->nvars;
8334 hmin = consdata->hmin;
8335 hmax = consdata->hmax;
8345 for ( j = 0; j <
nvars; ++j )
8348 startvaluessorted[j] = startvalues[j];
8351 endvaluessorted[j] = endvalues[j];
8353 startindices[j] = j;
8363 freecapacity = consdata->capacity;
8366 for( j = 0; j <
nvars; ++j )
8368 curtime = startvaluessorted[j];
8369 if( curtime >= hmax )
8373 freecapacity -= consdata->demands[startindices[j]];
8375 while( j+1 <
nvars && startvaluessorted[j+1] == curtime )
8378 freecapacity -= consdata->demands[startindices[j]];
8382 while( endidx < nvars && curtime >= endvaluessorted[endidx] )
8384 freecapacity += consdata->demands[endindices[endidx]];
8388 assert(freecapacity <= consdata->capacity);
8398 if( freecapacity < 0 && curtime >= hmin )
8400 int nextprofilechange;
8404 nextprofilechange =
MIN( startvaluessorted[j+1], endvaluessorted[endidx] );
8406 nextprofilechange = endvaluessorted[endidx];
8408 nextprofilechange =
MIN(nextprofilechange, hmax);
8410 for( t = curtime; t < nextprofilechange; ++t )
8420 consdata->covercuts =
TRUE;
8455 assert(nstarted > nfinished);
8459 assert(consdata->nvars > 0);
8461 capacity = consdata->capacity;
8478 for(
b = 0;
b < nbinvars; ++
b )
8494 for(
b = 0;
b < nbinvars; ++
b )
8502 if( consdata->demandrowssize == 0 )
8504 consdata->demandrowssize = 10;
8507 if( consdata->ndemandrows == consdata->demandrowssize )
8509 consdata->demandrowssize *= 2;
8513 consdata->demandrows[consdata->ndemandrows] = row;
8514 consdata->ndemandrows++;
8556 nvars = consdata->nvars;
8569 SCIPdebugMsg(
scip,
"create sorted event points for cumulative constraint <%s> with %d jobs\n",
8574 starttimes, endtimes, startindices, endindices,
FALSE);
8577 freecapacity = consdata->capacity;
8578 hmin = consdata->hmin;
8579 hmax = consdata->hmax;
8582 for( j = 0; j <
nvars; ++j )
8584 curtime = starttimes[j];
8587 if( curtime >= hmax )
8596 assert(freecapacity <= consdata->capacity);
8603 if( freecapacity < 0 && curtime >= hmin )
8610 nextstarttime = starttimes[j+1];
8612 nextstarttime = endtimes[
nvars-1];
8614 nextstarttime =
MIN(nextstarttime, hmax);
8621 for( t = curtime+1 ; t < nextstarttime; ++t )
8626 if( freecapacity < 0 )
8669 assert(consdata->ndemandrows == 0);
8672 if( consdata->linkingconss ==
NULL )
8714 if( consdata->demandrows ==
NULL )
8716 assert(consdata->ndemandrows == 0);
8723 for(
r = 0;
r < consdata->ndemandrows && !(*infeasible); ++
r )
8762 if( consdata->demandrows ==
NULL )
8764 assert(consdata->ndemandrows == 0);
8774 for(
r = 0;
r < consdata->ndemandrows; ++
r )
8805 (*separated) =
TRUE;
8840 if( consdata->linkingconss ==
NULL )
8845 if( !consdata->covercuts )
8854 for(
r = 0;
r < consdata->nscoverrows; ++
r )
8866 if( minfeasibility > feasibility )
8868 minfeasibility = feasibility;
8869 row = consdata->scoverrows[
r];
8878 SCIPdebugMsg(
scip,
"cumulative constraint <%s> separated 1 cover cut with feasibility %g\n",
8885 (*separated) =
TRUE;
8892 for(
r = 0;
r < consdata->nbcoverrows; ++
r )
8904 if( minfeasibility > feasibility )
8906 minfeasibility = feasibility;
8907 row = consdata->bcoverrows[
r];
8916 SCIPdebugMsg(
scip,
"cumulative constraint <%s> separated 1 cover cut with feasibility %g\n",
8924 (*separated) =
TRUE;
8952 assert(nstarted > nfinished);
8956 assert(consdata->nvars > 0);
8978 for( v = 0; v < nstarted - nfinished; ++v )
9029 nvars = consdata->nvars;
9042 SCIPdebugMsg(
scip,
"create sorted event points for cumulative constraint <%s> with %d jobs\n",
9051 freecapacity = consdata->capacity;
9052 hmin = consdata->hmin;
9053 hmax = consdata->hmax;
9056 for( j = 0; j <
nvars && !(*cutoff); ++j )
9058 curtime = starttimes[j];
9060 if( curtime >= hmax )
9069 assert(freecapacity <= consdata->capacity);
9076 if( freecapacity < 0 && curtime >= hmin)
9122 nvars = consdata->nvars;
9129 capacity = consdata->capacity;
9132 for ( j = 0; j <
nvars; ++j )
9134 if( consdata->demands[j] > capacity )
9162 if( consdata->nvars == 0 )
9169 else if( consdata->nvars == 1 )
9171 if( consdata->demands[0] > consdata->capacity )
9210 hmin = consdata->hmin;
9211 hmax = consdata->hmax;
9213 SCIPdebugMsg(
scip,
"check for irrelevant jobs within cumulative constraint <%s>[%d,%d)\n",
9216 for( j = consdata->nvars-1; j >= 0; --j )
9218 var = consdata->vars[j];
9219 demand = consdata->demands[j];
9220 duration = consdata->durations[j];
9226 if( demand == 0 || duration == 0 )
9235 else if( est >= hmax || lct <= hmin )
9271 assert(consdata->durations[pos] > 0);
9272 assert(consdata->demands[pos] > 0);
9274 var = consdata->vars[pos];
9276 duration = consdata->durations[pos];
9279 SCIPdebugMsg(
scip,
" variable <%s>: demand <%d> is larger than the capacity <%d>\n",
9287 if( ect - duration >= consdata->hmax || lst + duration <= consdata->hmin)
9290 if( ect > consdata->hmin && lst < consdata->hmax )
9295 else if( lst < consdata->hmax )
9303 else if( ect > consdata->hmin )
9328 leftbound = consdata->hmin - duration;
9329 rightbound = consdata->hmax;
9379 capacity = consdata->capacity;
9381 for( j = consdata->nvars-1; j >= 0 && !(*
cutoff); --j )
9383 if( consdata->demands[j] > capacity )
9513 if( *capacity == 1 ||
nvars <= 1 )
9523 for( v =
nvars-2; v >= 0 && (gcd >= 2 || mindemand1 + mindemand2 > *capacity); --v )
9525 assert(mindemand1 <= mindemand2);
9526 assert(demands[v] <= *capacity);
9530 if( mindemand1 > demands[v] )
9532 mindemand2 = mindemand1;
9533 mindemand1 = demands[v];
9535 else if( mindemand2 > demands[v] )
9536 mindemand2 = demands[v];
9539 if( mindemand1 + mindemand2 > *capacity )
9541 SCIPdebugMsg(
scip,
"update cumulative condition (%d + %d > %d) to unary cumulative condition\n", mindemand1, mindemand2, *capacity);
9543 for( v = 0; v <
nvars; ++v )
9548 (*nchgcoefs) +=
nvars;
9555 for( v = 0; v <
nvars; ++v )
9556 demands[v] /= (
int) gcd;
9558 (*capacity) /= (int) gcd;
9560 (*nchgcoefs) +=
nvars;
9587 if( consdata->normalized )
9590 capacity = consdata->capacity;
9596 consdata->normalized =
TRUE;
9598 if( capacity > consdata->capacity )
9599 consdata->varbounds =
FALSE;
9655 for( t = 0; t < ntimepoints; ++t )
9658 if( timepoints[t] <= *hmin )
9662 if( timepoints[t] >= *hmax )
9668 if( loads[t] <= capacity )
9670 (*split) = timepoints[t];
9723 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
9754 if( consdata->nvars <= 1 )
9758 consdata->durations, consdata->demands, consdata->capacity, &hmin, &hmax, &split) );
9761 if( consdata->hmin < hmin )
9765 consdata->hmin = hmin;
9770 if( consdata->hmax > hmax )
9773 consdata->hmax = hmax;
9778 if( consdata->hmax <= consdata->hmin )
9780 SCIPdebugMsg(
scip,
"constraint <%s> is redundant since hmax(%d) <= hmin(%d)\n",
9786 else if( consdata->hmin < split && split < consdata->hmax )
9791 SCIPdebugMsg(
scip,
"split cumulative constraint <%s>[%d,%d) with %d jobs at time point %d\n",
9792 SCIPconsGetName(cons), consdata->hmin, consdata->hmax, consdata->nvars, split);
9794 assert(split < consdata->hmax);
9798 consdata->durations, consdata->demands, consdata->capacity, split, consdata->hmax,
9803 consdata->hmax = split;
9805 assert(consdata->hmin < consdata->hmax);
9885 SCIPdebugMsg(
scip,
"check for irrelevant variable for cumulative condition (hmin %d) w.r.t. earlier start time\n", hmin);
9887 firstminect = INT_MAX;
9888 secondminect = INT_MAX;
9891 for( v = 0; v <
nvars; ++v )
9897 if( ect < firstminect )
9899 secondminect = firstminect;
9902 else if( ect < secondminect )
9907 for( v = 0; v <
nvars; ++v )
9922 duration = durations[v];
9929 ect = est + duration;
9931 lct = lst + duration;
9934 if( ect == firstminect )
9935 minect = secondminect;
9937 minect = firstminect;
9940 alternativelb =
MAX(hmin+1, minect);
9941 alternativelb =
MIN(alternativelb, hmax);
9948 SCIPdebugMsg(
scip,
" variable <%s>[%g,%g] with duration <%d> is irrelevant\n",
9952 irrelevants[v] =
TRUE;
9975 SCIPdebugMsg(
scip,
" variables <%s>[%d,%d] (duration <%d>) is irrelevant due to no up lock\n",
9979 irrelevants[v] =
TRUE;
9987 SCIPdebugMsg(
scip,
" remove down lock of variable <%s>[%g,%g] with duration <%d>\n",
9991 downlocks[v] =
FALSE;
9998 else if( ect <= hmin )
10016 SCIPdebugMsg(
scip,
" variable <%s>[%d,%d] with duration <%d> is irrelevant due to dual fixing wrt EST\n",
10023 irrelevants[v] =
TRUE;
10046 if( alternativelb > lst )
10071 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
10072 nfixedvars, &success,
cutoff) );
10083 SCIPdebugMsg(
scip,
"********* check variable <%s>[%g,%g] with duration <%d> (hmin %d)\n",
10170 SCIPdebugMsg(
scip,
"check for irrelevant variable for cumulative condition (hmax %d) w.r.t. latest completion time\n", hmax);
10172 firstmaxlst = INT_MIN;
10173 secondmaxlst = INT_MIN;
10176 for( v = 0; v <
nvars; ++v )
10182 if( lst > firstmaxlst )
10184 secondmaxlst = firstmaxlst;
10187 else if( lst > secondmaxlst )
10188 secondmaxlst = lst;
10192 for( v = 0; v <
nvars; ++v )
10206 duration = durations[v];
10213 ect = est + duration;
10217 if( lst == firstmaxlst )
10218 maxlst = secondmaxlst;
10220 maxlst = firstmaxlst;
10223 alternativeub =
MIN(hmax - 1, maxlst) - duration;
10224 alternativeub =
MAX(alternativeub, hmin);
10231 SCIPdebugMsg(
scip,
" variable <%s>[%g,%g] with duration <%d> is irrelevant\n",
10235 irrelevants[v] =
TRUE;
10249 if( !downlocks[v] )
10255 SCIPdebugMsg(
scip,
" variables <%s>[%d,%d] with duration <%d> is irrelevant due to no down lock\n",
10259 irrelevants[v] =
TRUE;
10267 SCIPdebugMsg(
scip,
" remove up lock of variable <%s>[%g,%g] with duration <%d>\n",
10271 uplocks[v] =
FALSE;
10278 else if( lst >= hmax )
10296 SCIPdebugMsg(
scip,
" variable <%s>[%d,%d] with duration <%d> is irrelevant due to dual fixing wrt LCT\n",
10303 irrelevants[v] =
TRUE;
10326 if( alternativeub < est )
10351 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
10352 nfixedvars, &success,
cutoff) );
10400 nvars = consdata->nvars;
10410 consdata->hmin, consdata->hmax, consdata->downlocks, consdata->uplocks, cons,
10411 irrelevants, nfixedvars, nchgsides,
cutoff) );
10415 consdata->hmin, consdata->hmax, consdata->downlocks, consdata->uplocks, cons,
10416 irrelevants, nfixedvars, nchgsides,
cutoff) );
10421 for( v =
nvars-1; v >= 0; --v )
10423 if( irrelevants[v] )
10429 var = consdata->vars[v];
10436 if( lst <= consdata->hmin && ect >= consdata->hmax )
10438 if( consdata->capacity < consdata->demands[v] )
10444 consdata->capacity -= consdata->demands[v];
10445 consdata->varbounds =
FALSE;
10478 startindex = nstarted - 1;
10483 while( nstarted - nfinished > ncountedvars )
10490 varidx = startindices[startindex];
10499 if( endtime > curtime )
10501 if( consdata->demands[
varidx] < consdata->capacity )
10503 (*demands)[*ndemands] = consdata->demands[
varidx];
10535 assert(nstarted > nfinished);
10539 assert(consdata->nvars > 0);
10540 assert(consdata->capacity > 0);
10546 collectDemands(
scip, consdata, startindices, curtime, nstarted, nfinished, &demands, &ndemands);
10551 for( j = 0; j < ndemands; ++j )
10607 nvars = consdata->nvars;
10615 SCIPdebugMsg(
scip,
"try to tighten capacity for cumulative constraint <%s> with capacity %d\n",
10625 starttimes, endtimes, startindices, endindices,
FALSE);
10629 freecapacity = consdata->capacity;
10632 for( j = 0; j <
nvars && bestcapacity < consdata->capacity; ++j )
10634 curtime = starttimes[j];
10643 assert(freecapacity <= consdata->capacity);
10650 if( freecapacity < 0 )
10660 bestcapacity =
MAX(bestcapacity, newcapacity);
10661 SCIPdebugMsg(
scip,
"after highest cap usage: bestcapacity = %d\n", bestcapacity);
10665 if( freecapacity > 0 && freecapacity != consdata->capacity )
10667 bestcapacity =
MAX(bestcapacity, consdata->capacity - freecapacity);
10668 SCIPdebugMsg(
scip,
"after peak < cap: bestcapacity = %d\n", bestcapacity);
10672 if( freecapacity == 0 && consdata->demands[startindices[j]] < consdata->capacity)
10675 SCIPdebugMsg(
scip,
"--> cannot decrease capacity since sum equals capacity\n");
10676 bestcapacity = consdata->capacity;
10688 if( bestcapacity < consdata->capacity )
10690 SCIPdebug(
int oldnchgcoefs = *nchgcoefs; )
10692 SCIPdebugMsg(
scip,
"+-+-+-+-+-+ --> CHANGE capacity of cons<%s> from %d to %d\n",
10695 for( j = 0; j <
nvars; ++j )
10697 if( consdata->demands[j] == consdata->capacity )
10699 consdata->demands[j] = bestcapacity;
10704 consdata->capacity = bestcapacity;
10709 consdata->varbounds =
FALSE;
10741 nvars = consdata->nvars;
10742 oldnchgcoefs = *nchgcoefs;
10751 mindemand = consdata->demands[0];
10752 for( j = 0; j <
nvars; ++j )
10754 mindemand =
MIN(mindemand, consdata->demands[j]);
10758 for( j = 0; j <
nvars; ++j )
10760 if( mindemand + consdata->demands[j] > consdata->capacity && consdata->demands[j] < consdata->capacity )
10763 consdata->demands[j], consdata->capacity);
10764 consdata->demands[j] = consdata->capacity;
10773 for( j = 0; j <
nvars; ++j )
10780 assert(consdata->demands[j] <= consdata->capacity);
10782 if( consdata->demands[j] == consdata->capacity )
10801 if( est_i >= lct_j || est_j >= lct_i )
10804 if( consdata->demands[j] + consdata->demands[
i] <= consdata->capacity )
10814 consdata->demands[j], consdata->capacity);
10815 consdata->demands[j] = consdata->capacity;
10820 if( (*nchgcoefs) > oldnchgcoefs )
10822 SCIPdebugMsg(
scip,
"+-+-+-+-+-+changed %d coefficients of variables of cumulative constraint<%s>\n",
10829#ifdef SCIP_DISABLED_CODE
10849 nvars = consdata->nvars;
10852 hmin = consdata->hmin;
10853 hmax = consdata->hmax;
10856 for( v = 0; v <
nvars; ++v )
10865 var = consdata->vars[v];
10868 duration = consdata->durations[v];
10871 ect = est + duration;
10873 lct = lst + duration;
10876 assert(lst > hmin || ect < hmax);
10878 if( lst <= hmin && est < hmin - lct +
MIN(hmin, ect) )
10887 shift = est - (hmin - lct +
MIN(hmin, ect));
10890 duration = hmin - lct;
10906 consdata->durations[v] = duration;
10907 consdata->vars[v] = aggrvar;
10944 capacity = consdata->capacity;
10946 if( capacity == 1 )
10953 halfcapacity = capacity / 2;
10954 mindemand = consdata->capacity;
10958 for( v = 0; v < consdata->nvars; ++v )
10960 if( consdata->demands[v] > halfcapacity )
10963 demands[
nvars] = 1;
10964 durations[
nvars] = consdata->durations[v];
10967 mindemand =
MIN(mindemand, consdata->demands[v]);
10976 for( v = 0; v < consdata->nvars; ++v )
10978 if( consdata->demands[v] > halfcapacity )
10981 if( mindemand + consdata->demands[v] > capacity )
10983 demands[
nvars] = 1;
10984 durations[
nvars] = consdata->durations[v];
11058 if( conshdlrdata->normalize )
11070 if( conshdlrdata->coeftightening )
11081#ifdef SCIP_DISABLED_CODE
11095struct TCLIQUE_Graph
11115 return tcliquegraph->nnodes;
11124 return tcliquegraph->weights;
11136 if( tcliquegraph->precedencematrix[node1][node2] || tcliquegraph->precedencematrix[node2][node1] )
11140 if( tcliquegraph->demandmatrix[node1][node2] )
11165 assert(0 <= nodes[
i] && nodes[
i] < tcliquegraph->nnodes);
11166 assert(
i == 0 || nodes[
i-1] < nodes[
i]);
11169 if( tcliqueIsedgeClique(tcliquegraph, node, nodes[
i]) )
11172 adjnodes[nadjnodes] = nodes[
i];
11218 bound = (duration - vlbcoef) / (vlbcoef - 1.0);
11265 vlbcoef = 1.0 / vubcoef;
11266 vlbconst = -vubconst / vubcoef;
11298 if( tcliquegraph->size == tcliquegraph->nnodes )
11303 tcliquegraph->size = size;
11311 for( v = 0; v < tcliquegraph->nnodes; ++v )
11317 assert(tcliquegraph->nnodes < tcliquegraph->size);
11319 pos = tcliquegraph->nnodes;
11322 tcliquegraph->durations[pos] = 0;
11323 tcliquegraph->weights[pos] = 0;
11324 tcliquegraph->vars[pos] =
var;
11334 tcliquegraph->nnodes++;
11336 for( v = 0; v < tcliquegraph->nnodes; ++v )
11338 tcliquegraph->precedencematrix[v][pos] = 0;
11339 tcliquegraph->demandmatrix[v][pos] = 0;
11342 (*idx) = tcliquegraph->nnodes;
11379 for( v = 0; v <
nvars; ++v )
11395 if( tcliquegraph->durations[idx1] == 0 )
11403 for(
b = 0;
b < nvbdvars; ++
b )
11410 if( tcliquegraph->durations[idx2] == 0 )
11414 tcliquegraph->precedencematrix[idx2][idx1] =
TRUE;
11422 for(
b = 0;
b < nvbdvars; ++
b )
11429 if( tcliquegraph->durations[idx2] == 0 )
11433 tcliquegraph->precedencematrix[idx1][idx2] =
TRUE;
11443 if( tcliquegraph->durations[idx2] == 0 )
11448 tcliquegraph->precedencematrix[idx1][idx2] =
TRUE;
11452 tcliquegraph->precedencematrix[idx2][idx1] =
TRUE;
11474 for( j = 0; j <
nnodes; ++j )
11476 if( adjmatrix[
i][j] )
11481 for( k = 0; k <
nnodes; ++k )
11483 if( adjmatrix[j][k] )
11484 adjmatrix[
i][k] =
TRUE;
11503 for(
c = 0;
c < nconss; ++
c )
11515 vars = consdata->vars;
11516 demands = consdata->demands;
11518 nvars = consdata->nvars;
11519 capacity = consdata->capacity;
11532 if( tcliquegraph->durations[idx1] == 0 || tcliquegraph->durations[idx1] > consdata->durations[
i] )
11535 for( j =
i+1; j <
nvars; ++j )
11537 assert(consdata->durations[j] > 0);
11539 if( demands[
i] + demands[j] > capacity )
11552 if( est1 < consdata->hmin && est2 < consdata->hmin )
11559 if( lct1 > consdata->hmax && lct2 > consdata->hmax )
11566 if( tcliquegraph->durations[idx2] == 0 || tcliquegraph->durations[idx2] > consdata->durations[j] )
11571 assert(tcliquegraph->durations[idx1] > 0);
11572 assert(tcliquegraph->durations[idx2] > 0);
11574 tcliquegraph->demandmatrix[idx1][idx2] =
TRUE;
11575 tcliquegraph->demandmatrix[idx2][idx1] =
TRUE;
11602 transitiveClosure(tcliquegraph->precedencematrix, tcliquegraph->ninarcs, tcliquegraph->noutarcs, tcliquegraph->nnodes);
11633 for( v = 0; v < ncliquenodes; ++v )
11635 durations[v] = tcliquegraph->durations[cliquenodes[v]];
11636 assert(durations[v] > 0);
11638 vars[v] = tcliquegraph->vars[cliquenodes[v]];
11678 nnodes = tcliquegraph->nnodes;
11682 for( v = 0; v <
nnodes; ++v )
11684 tcliquegraph->weights[v] = tcliquegraph->durations[v];
11695 SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal,
NULL) );
11704 if( tcliquegraph->durations[v] == 0 )
11716 precedencerow[
c] = tcliquegraph->precedencematrix[v][
c];
11717 precedencecol[
c] = tcliquegraph->precedencematrix[
c][v];
11719 demandrow[
c] = tcliquegraph->demandmatrix[v][
c];
11720 demandcol[
c] = tcliquegraph->demandmatrix[
c][v];
11722 tcliquegraph->precedencematrix[
c][v] =
FALSE;
11723 tcliquegraph->precedencematrix[v][
c] =
FALSE;
11727 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,
11728 tcliquegraph, tcliqueNewsolClique,
NULL,
11729 cliquenodes, &ncliquenodes, &cliqueweight, 1, 1,
11730 10000, 1000, 1000, v, &ntreenodes, &tcliquestatus);
11732 SCIPdebugMsg(
scip,
"tree nodes %d clique size %d (weight %d, status %d)\n", ntreenodes, ncliquenodes, cliqueweight, tcliquestatus);
11734 if( ncliquenodes == 1 )
11744 for(
c = 0;
c < ncliquenodes; ++
c )
11752 tcliquegraph->precedencematrix[v][
c] = precedencerow[
c];
11753 tcliquegraph->precedencematrix[
c][v] = precedencecol[
c];
11755 tcliquegraph->demandmatrix[v][
c] = demandrow[
c];
11756 tcliquegraph->demandmatrix[
c][v] = demandcol[
c];
11768 (*naddconss) += nconss;
11824 if( !tcliquegraph->precedencematrix[source][sink] )
11827 nnodes = tcliquegraph->nnodes;
11828 vars = tcliquegraph->vars;
11846 duration = tcliquegraph->durations[
i];
11848 if(
i == source ||
i == sink )
11851 tcliquegraph->weights[
i] = 0;
11853 else if( tcliquegraph->precedencematrix[source][
i] && tcliquegraph->precedencematrix[
i][sink] )
11856 tcliquegraph->weights[
i] = duration;
11862 tcliquegraph->weights[
i] = duration;
11865 tcliquegraph->weights[
i] = 0;
11871 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,
11872 tcliquegraph, tcliqueNewsolClique,
NULL,
11873 cliquenodes, &ncliquenodes, &cliqueweight, 1, 1,
11874 10000, 1000, 1000, -1, &ntreenodes, &tcliquestatus);
11876 if( ncliquenodes > 1 )
11887 distance = cliqueweight + tcliquegraph->durations[source];
11918 nnodes = tcliquegraph->nnodes;
11930 if( tcliquegraph->ninarcs[
i] == 0 )
11932 sources[nsources] =
i;
11936 if( tcliquegraph->noutarcs[
i] == 0 )
11959 (*naddconss) += nconss;
11982 for(
c = 0;
c < nconss; ++
c )
11992 vars = consdata->vars;
11993 nvars = consdata->nvars;
11995 for( v = 0; v <
nvars; ++v )
12006 tcliquegraph->durations[idx] =
MAX(tcliquegraph->durations[idx], consdata->durations[v]);
12007 assert(tcliquegraph->durations[idx] > 0);
12064 for( v = 0; v <
nvars; ++v )
12082 (*tcliquegraph)->nnodes =
nvars;
12083 (*tcliquegraph)->varmap = varmap;
12084 (*tcliquegraph)->precedencematrix = precedencematrix;
12085 (*tcliquegraph)->demandmatrix = demandmatrix;
12086 (*tcliquegraph)->weights = weights;
12087 (*tcliquegraph)->ninarcs = ninarcs;
12088 (*tcliquegraph)->noutarcs = noutarcs;
12089 (*tcliquegraph)->durations = durations;
12090 (*tcliquegraph)->size =
nvars;
12104 for( v = (*tcliquegraph)->nnodes-1; v >= 0; --v )
12146 if( conshdlrdata->detectvarbounds )
12152 if( conshdlrdata->detectdisjunctive )
12173 if( consdata->validsignature )
12176 vars = consdata->vars;
12177 nvars = consdata->nvars;
12179 for( v = 0; v <
nvars; ++v )
12181 consdata->signature |= ((
unsigned int)1 << ((
unsigned int)
SCIPvarGetIndex(
vars[v]) % (
sizeof(
unsigned int) * 8)));
12184 consdata->validsignature =
TRUE;
12197 return SCIPvarCompare(consdata->vars[ind1], consdata->vars[ind2]);
12212 for(
i = 0;
i < nconss; ++
i )
12224 assert(consdata0->validsignature);
12226 for( j =
i+1; j < nconss; ++j )
12237 if( consdata0->capacity != consdata1->capacity )
12241 assert(consdata1->validsignature);
12243 if( (consdata1->signature & (~consdata0->signature)) == 0 )
12247 assert((consdata0->signature & (~consdata1->signature)) == 0);
12250 if( (consdata0->signature & (~consdata1->signature)) == 0 )
12257 if( consdata0->nvars > consdata1->nvars )
12260 if( consdata0->hmin < consdata1->hmin )
12263 if( consdata0->hmax > consdata1->hmax )
12270 SCIPsort(perm0, consdataCompVar, (
void*)consdata0, consdata0->nvars);
12271 SCIPsort(perm1, consdataCompVar, (
void*)consdata1, consdata1->nvars);
12273 for( v0 = 0, v1 = 0; v0 < consdata0->nvars && v1 < consdata1->nvars; )
12284 var0 = consdata0->vars[idx0];
12286 var1 = consdata1->vars[idx1];
12297 demand0 = consdata0->demands[idx0];
12298 duration0 = consdata0->durations[idx0];
12300 demand1 = consdata1->demands[idx1];
12301 duration1 = consdata1->durations[idx1];
12303 if( demand0 != demand1 )
12306 if( duration0 != duration1 )
12312 else if( comp > 0 )
12318 if( v0 == consdata0->nvars )
12363 if( consdata->varbounds )
12366 vars = consdata->vars;
12367 durations = consdata->durations;
12368 demands = consdata->demands;
12369 capacity = consdata->capacity;
12370 nvars = consdata->nvars;
12384 var = consdata->vars[
i];
12392 for(
b = 0;
b < nvbdvars; ++
b )
12398 for( j = 0; j <
nvars; ++j )
12400 if(
vars[j] == vbdvars[
b] )
12406 if( demands[
i] + demands[j] > capacity &&
12424 (*nchgbds) += nlocalbdchgs;
12431 (*naddconss) += nconss;
12433 consdata->varbounds =
TRUE;
12459 if( solinfeasible )
12465 SCIPdebugMsg(
scip,
"constraint enforcing %d useful cumulative constraints of %d constraints for %s solution\n", nusefulconss, nconss,
12466 sol ==
NULL ?
"LP" :
"relaxation");
12473 if( conshdlrdata->usebinvars )
12482 for(
c = 0;
c < nusefulconss; ++
c )
12503 for( ;
c < nconss && !separated; ++
c )
12575#ifdef SCIP_STATISTIC
12576 if( !conshdlrdata->iscopy )
12580 conshdlrdata->nlbtimetable, conshdlrdata->nubtimetable, conshdlrdata->ncutofftimetable);
12582 conshdlrdata->nlbedgefinder, conshdlrdata->nubedgefinder, conshdlrdata->ncutoffedgefinder);
12584 conshdlrdata->ncutoffoverload, conshdlrdata->ncutoffoverloadTTEF);
12606 conshdlrdata->detectedredundant =
FALSE;
12608 for(
c = 0;
c < nconss; ++
c )
12621#ifdef SCIP_STATISTIC
12631 for(
c = 0;
c < nconss; ++
c )
12635#ifdef SCIP_DISABLED_CODE
12640 if( !conshdlrdata->iscopy )
12642 SCIPstatisticPrintf(
"@11 added variables bounds constraints %d\n", conshdlrdata->naddedvarbounds);
12643 SCIPstatisticPrintf(
"@22 added disjunctive constraints %d\n", conshdlrdata->naddeddisjunctives);
12670 for(
c = 0;
c < nconss; ++
c )
12735 sourcedata->durations, sourcedata->demands, sourcedata->nvars, sourcedata->capacity,
12765 *infeasible =
FALSE;
12767 SCIPdebugMsg(
scip,
"initialize LP relaxation for %d cumulative constraints\n", nconss);
12769 if( conshdlrdata->usebinvars )
12772 for(
c = 0;
c < nconss && !(*infeasible); ++
c )
12777 if( conshdlrdata->cutsasconss )
12810 SCIPdebugMsg(
scip,
"separating %d/%d cumulative constraints\n", nusefulconss, nconss);
12821 if( conshdlrdata->usebinvars )
12824 for(
c = 0;
c < nusefulconss && !
cutoff; ++
c )
12829 if( !
cutoff && conshdlrdata->usecovercuts )
12831 for(
c = 0;
c < nusefulconss; ++
c )
12838 if( conshdlrdata->sepaold )
12841 for(
c = 0;
c < nusefulconss; ++
c )
12850 else if( separated )
12877 SCIPdebugMsg(
scip,
"separating %d/%d cumulative constraints\n", nusefulconss, nconss);
12883 if( conshdlrdata->usebinvars )
12886 for(
c = 0;
c < nusefulconss && !
cutoff; ++
c )
12891 if( !
cutoff && conshdlrdata->usecovercuts )
12893 for(
c = 0;
c < nusefulconss; ++
c )
12899 if( conshdlrdata->sepaold )
12902 for(
c = 0;
c < nusefulconss; ++
c )
12911 else if( separated )
12949 if( objinfeasible )
13004 SCIPdebugMsg(
scip,
"propagate %d of %d useful cumulative constraints\n", nusefulconss, nconss);
13021 for(
c = 0;
c < nusefulconss && !
cutoff; ++
c )
13031 &nchgbds, &nchgbds, &ndelconss, &nchgbds, &nchgbds, &nchgbds, &
cutoff, &
cutoff) );
13043 if( !
cutoff && nchgbds == 0 )
13046 for(
c = nusefulconss;
c < nconss && !
cutoff; ++
c )
13057 else if( nchgbds > 0 )
13059 SCIPdebugMsg(
scip,
"delete (locally) %d constraints and changed %d variable bounds\n", ndelconss, nchgbds);
13098 oldnfixedvars = *nfixedvars;
13099 oldnchgbds = *nchgbds;
13100 oldnchgsides = *nchgsides;
13101 oldnchgcoefs = *nchgcoefs;
13102 oldnupgdconss = *nupgdconss;
13103 oldndelconss = *ndelconss;
13104 oldnaddconss = *naddconss;
13109 for(
c = 0;
c < nconss && !
cutoff; ++
c )
13121 nfixedvars, nchgbds, ndelconss, naddconss, nchgcoefs, nchgsides, &
cutoff, &unbounded) );
13123 if(
cutoff || unbounded )
13131 if( nrounds == 1 &&
SCIPgetNRuns(
scip) == 1 && conshdlrdata->disjunctive )
13154 && (conshdlrdata->detectvarbounds || conshdlrdata->detectdisjunctive)
13161 conshdlrdata->detectedredundant =
TRUE;
13169 SCIPdebugMsg(
scip,
"delete %d constraints and changed %d variable bounds (cutoff %u)\n",
13170 *ndelconss - oldndelconss, *nchgbds - oldnchgbds,
cutoff);
13174 else if( unbounded )
13176 else if( *nchgbds > oldnchgbds || *nfixedvars > oldnfixedvars || *nchgsides > oldnchgsides
13177 || *nchgcoefs > oldnchgcoefs || *nupgdconss > oldnupgdconss || *ndelconss > oldndelconss || *naddconss > oldnaddconss )
13209 SCIPdebugMsg(
scip,
"resolve propagation: variable <%s>, cumulative constraint <%s> (capacity %d, propagation %d, H=[%d,%d))\n",
13214 consdata->durations, consdata->demands, consdata->capacity, consdata->hmin, consdata->hmax,
13215 infervar,
intToInferInfo(inferinfo), boundtype, bdchgidx, relaxedbd, conshdlrdata->usebdwidening,
NULL,
result) );
13237 vars = consdata->vars;
13240 for( v = 0; v < consdata->nvars; ++v )
13242 if( consdata->downlocks[v] && consdata->uplocks[v] )
13247 else if( consdata->downlocks[v] )
13251 else if( consdata->uplocks[v] )
13281 const char* consname;
13290 nvars = sourceconsdata->nvars;
13291 sourcevars = sourceconsdata->vars;
13317 sourceconsdata->durations, sourceconsdata->demands, sourceconsdata->capacity,
13318 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
13321 if( sourceconsdata->hmin > 0 )
13327 if( sourceconsdata->hmax < INT_MAX )
13381 endptr = strchr(endptr,
')');
13383 if( endptr ==
NULL )
13393 duration = atoi(strvalue);
13397 demand = atoi(strvalue);
13403 demands[
nvars] = demand;
13404 durations[
nvars] = duration;
13407 while( *str !=
')' );
13413 hmin = atoi(strvalue);
13426 capacity = (int)value;
13430 initial,
separate, enforce, check,
propagate, local, modifiable, dynamic, removable, stickingatnode) );
13456 if( varssize < consdata->
nvars )
13457 (*success) =
FALSE;
13478 (*nvars) = consdata->nvars;
13509 consdata->propagated =
FALSE;
13538 consEnfolpCumulative, consEnfopsCumulative, consCheckCumulative, consLockCumulative,
13546#ifdef SCIP_STATISTIC
13569 "constraints/" CONSHDLR_NAME "/maxtime",
"maximum range for time horizon",
13573 "should time-table (core-times) propagator be used to infer bounds?",
13577 "should edge-finding be used to detect an overload?",
13581 "should edge-finding be used to infer bounds?",
13584 "constraints/" CONSHDLR_NAME "/useadjustedjobs",
"should edge-finding be executed?",
13588 "should time-table edge-finding be used to detect an overload?",
13592 "should time-table edge-finding be used to infer bounds?",
13596 "constraints/" CONSHDLR_NAME "/usebinvars",
"should the binary representation be used?",
13599 "constraints/" CONSHDLR_NAME "/localcuts",
"should cuts be added only locally?",
13602 "constraints/" CONSHDLR_NAME "/usecovercuts",
"should covering cuts be added every node?",
13606 "should the cumulative constraint create cuts as knapsack constraints?",
13610 "shall old sepa algo be applied?",
13614 "constraints/" CONSHDLR_NAME "/fillbranchcands",
"should branching candidates be added to storage?",
13619 "constraints/" CONSHDLR_NAME "/dualpresolve",
"should dual presolving be applied?",
13622 "constraints/" CONSHDLR_NAME "/coeftightening",
"should coefficient tightening be applied?",
13625 "constraints/" CONSHDLR_NAME "/normalize",
"should demands and capacity be normalized?",
13629 "should pairwise constraint comparison be performed in presolving?",
13632 "constraints/" CONSHDLR_NAME "/disjunctive",
"extract disjunctive constraints?",
13637 "number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit)?",
13640 "constraints/" CONSHDLR_NAME "/detectdisjunctive",
"search for conflict set via maximal cliques to detect disjunctive constraints",
13643 "constraints/" CONSHDLR_NAME "/detectvarbounds",
"search for conflict set via maximal cliques to detect variable bound constraints",
13648 "constraints/" CONSHDLR_NAME "/usebdwidening",
"should bound widening be used during the conflict analysis?",
13697 if( conshdlr ==
NULL )
13707 SCIPerrorMessage(
"detected potential integer overflow for variable <%s> in constraint <%s>: "
13708 "decrease upper bound of variable or time horizon constraints/" CONSHDLR_NAME "/maxtime\n",
13716 SCIP_CALL(
consdataCreate(
scip, &consdata,
vars,
NULL, durations, demands,
nvars, capacity, 0, INT_MAX, check) );
13721 local, modifiable, dynamic, removable, stickingatnode) );
13780 if( hmin < 0 || hmin > consdata->hmax )
13782 SCIPerrorMessage(
"invalid value of hmin for cumulative constraint <%s>\n",
13787 consdata->hmin = hmin;
13805 return consdata->hmin;
13822 if( hmax < consdata->hmin )
13824 SCIPerrorMessage(
"invalid value of hmax for cumulative constraint <%s>\n",
13829 consdata->hmax = hmax;
13847 return consdata->hmax;
13863 return consdata->vars;
13879 return consdata->nvars;
13895 return consdata->capacity;
13911 return consdata->durations;
13927 return consdata->demands;
13952 violated, cons, printreason) );
13988 hmin, hmax, split) );
14015 irrelevants, nfixedvars, nchgsides,
cutoff) );
14019 irrelevants, nfixedvars, nchgsides,
cutoff) );
14055 if( conshdlr ==
NULL )
14067 nvars,
vars, durations, demands, capacity, hmin, hmax, cons,
14068 nchgbds, &redundant, initialized, explanation,
cutoff) );
14116 file = fopen(filename,
"w");
14129 nvars = consdata->nvars;
14132 SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal,
NULL), TERMINATE );
14137 for( v = 0; v <
nvars; ++v )
14141 var = consdata->vars[v];
14148 else if( !consdata->downlocks[v] || !consdata->uplocks[v] )
14156 for( v = 0; v <
nvars; ++v )
14162 var = consdata->vars[v];
14168 for(
b = 0;
b < nvbdvars; ++
b )
14176#ifdef SCIP_MORE_OUTPUT
14181 for(
b = 0;
b < nvbdvars; ++
b )
14213 if( conshdlr ==
NULL )
14257 (*infeasible) =
FALSE;
14258 (*unbounded) =
FALSE;
14266 if( conshdlr ==
NULL )
14277 if( timelimit > 0.0 && memorylimit > 10 )
14279 SCIP_CALL( conshdlrdata->solveCumulative(njobs, ests, lsts, objvals, durations, demands, capacity,
14280 hmin, hmax, timelimit, memorylimit, maxnodes, solved, infeasible, unbounded, error) );
14316 for( v = 0; v <
nvars; ++v )
14318 copydemands[v] = demands[v];
14324 for( v = 0; v <
nvars; ++v )
14334 duration = durations[idx];
14343 if( impliedest < impliedlct )
14353 if( est == impliedest && lct == impliedlct )
14384 for( t = 0; t < ntimepoints - 1; ++t )
14387 if( loads[t] > capacity )
14389 assert(t == 0 || loads[t-1] <= capacity);
14390 return timepoints[t];
14414 for( t = ntimepoints - 1; t >= 0; --t )
14417 if( loads[t] > capacity )
14419 assert(t == ntimepoints-1 || loads[t+1] <= capacity);
14420 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_STRINGEQ(name, reference, retcode)
#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