cons_cumulative.c
Go to the documentation of this file.
24 * - a set of jobs, represented by their integer start time variables \f$S_j\f$, their array of processing times \f$p_j\f$ and of
28 * The cumulative constraint ensures that for each point in time \f$t\f$ \f$\sum_{j: S_j \leq t < S_j + p_j} d_j \leq C\f$ holds.
42 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
62 #define CONSHDLR_ENFOPRIORITY -2040000 /**< priority of the constraint handler for constraint enforcing */
63 #define CONSHDLR_CHECKPRIORITY -3030000 /**< priority of the constraint handler for checking feasibility */
64 #define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
65 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
66 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
68 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
69 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
70 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
71 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
93 #define DEFAULT_TTINFER TRUE /**< should time-table (core-times) propagator be used to infer bounds? */
96 #define DEFAULT_USEADJUSTEDJOBS FALSE /**< should during edge-finding jobs be adusted which run on the border of the effective time horizon? */
97 #define DEFAULT_TTEFCHECK TRUE /**< should time-table edge-finding be used to detect an overload? */
104 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
106 #define DEFAULT_DETECTDISJUNCTIVE TRUE /**< search for conflict set via maximal cliques to detect disjunctive constraints */
107 #define DEFAULT_DETECTVARBOUNDS TRUE /**< search for conflict set via maximal cliques to detect variable bound constraints */
108 #define DEFAULT_MAXNODES 10000LL /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
114 #define DEFAULT_USEBDWIDENING TRUE /**< should bound widening be used during conflict analysis? */
169 unsigned int varbounds:1; /**< bool to store if variable bound strengthening was already preformed */
170 unsigned int triedsolving:1; /**< bool to store if we tried already to solve that constraint as independent subproblem */
183 SCIP_Bool cutsasconss; /**< should the cumulative constraint create cuts as knapsack constraints? */
187 SCIP_Bool useadjustedjobs; /**< should during edge-finding jobs be adusted which run on the border of the effective time horizon? */
200 SCIP_Bool detectdisjunctive; /**< search for conflict set via maximal cliques to detect disjunctive constraints */
201 SCIP_Bool detectvarbounds; /**< search for conflict set via maximal cliques to detect variable bound constraints */
203 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
206 SCIP_Longint maxnodes; /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
208 SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)); /**< method to use a single cumulative condition */
212 SCIP_Longint nlbtimetable; /**< number of times the lower bound was tightened by the time-table propagator */
213 SCIP_Longint nubtimetable; /**< number of times the upper bound was tightened by the time-table propagator */
214 SCIP_Longint ncutofftimetable; /**< number of times the a cutoff was detected due to time-table propagator */
215 SCIP_Longint nlbedgefinder; /**< number of times the lower bound was tightened by the edge-finder propagator */
216 SCIP_Longint nubedgefinder; /**< number of times the upper bound was tightened by the edge-finder propagator */
217 SCIP_Longint ncutoffedgefinder; /**< number of times the a cutoff was detected due to edge-finder propagator */
218 SCIP_Longint ncutoffoverload; /**< number of times the a cutoff was detected due to overload checking via edge-finding */
219 SCIP_Longint nlbTTEF; /**< number of times the lower bound was tightened by time-table edge-finding */
220 SCIP_Longint nubTTEF; /**< number of times the upper bound was tightened by time-table edge-finding */
221 SCIP_Longint ncutoffoverloadTTEF;/**< number of times the a cutoff was detected due to overload checking via time-table edge-finding */
223 int nirrelevantjobs; /**< number of time a irrelevant/redundant jobs was removed form a constraint */
224 int nalwaysruns; /**< number of time a job removed form a constraint which run completely during the effective horizon */
228 int ndualbranchs; /**< number of times a dual branch was discoverd and applicable via probing */
229 int nallconsdualfixs; /**< number of times a dual fix was performed due to knowledge of all cumulative constraints */
239 * An inference information can be passed with each domain reduction to SCIP. This information is passed back to the
240 * constraint handler if the corresponding bound change has to be explained. It can be used to store information which
241 * help to construct a reason/explanation for a bound change. The inference information is limited to size of integer.
243 * In case of the cumulative constraint handler we store the used propagation algorithms for that particular bound
251 {
256 };
335 /** constructs an inference information out of a propagation rule, an earliest start and a latest completion time */
346 if( proprule == PROPRULE_0_INVALID || data1 < 0 || data1 >= (1<<15) || data2 < 0 || data2 >= (1<<15) )
392 #define computeCoreWithInterval(begin, end, ect, lst) (MAX(0, MIN((end), (ect)) - MAX((lst), (begin))))
417 /* the code contains a bug; we need to check if an implication forces that the jobs do not run in parallel */
485 /* the code contains a bug; we need to check if an implication forces that the jobs do not run in parallel */
527 /** collects all necessary binary variables to represent the jobs which can be active at time point of interest */
572 /* check the end time of this job is larger than the curtime; in this case the job is still running */
681 /* check the end time of this job is larger than the curtime; in this case the job is still running */
741 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
780 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
830 SCIPdebugMsg(scip, "%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
831 *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var),
850 SCIPdebugMsg(scip, "%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
851 *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var),
860 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
895 SCIP_Real** cumulativedemands, /**< array to store the estimated cumulative demand for each point in time */
903 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
904 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
929 createSortedEventpoints(scip, nvars, vars, durations, starttimes, endtimes, startindices, endindices, TRUE);
1115 disjfactor2 = MAX( disjfactor2, (peak-(SCIP_Real)capacity)/peak * (nlarge/(SCIP_Real)ndemands) );
1116 cumfactor1 = MAX( cumfactor1, (peak-capacity)/peak * (capacity-deltademand)/(SCIP_Real)capacity );
1155 SCIPstatisticPrintf("cumulative constraint<%s>: DISJ1=%g, DISJ2=%g, CUM=%g, RS1 = %g, RS2 = %g, EST = %g\n",
1156 SCIPconsGetName(cons), consdata->disjfactor1, disjfactor2, cumfactor1, resstrength1, resstrength2,
1238 SCIP_Real* objvals, /**< array of objective coefficients for each job (linear objective function), or NULL if none */
1286 SCIP_CALL( SCIPcreateVarBasic(subscip, &subvars[v], name, ests[v], lsts[v], objval, SCIP_VARTYPE_INTEGER) );
1304 * @note This "meta" setting has to be set first since this call overwrite all parameters including for example the
1330 SCIPdebugMsg(subscip, "solved single cumulative condition with status %d\n", SCIPgetStatus(subscip));
1402 {
1471 /* create for each job and time step a binary variable which is one if this jobs starts at this time point and a set
1512 SCIP_CALL( SCIPcreateVarBasic(subscip, &binvar, name, 0.0, 1.0, objval, SCIP_VARTYPE_BINARY) );
1515 /* add binary varibale to the set partitioning constraint which ensures that the job is started */
1526 /* adjusted the smallest earliest start time and the largest latest completion time with the effective horizon */
1533 /* create for each time a knapsack constraint which ensures that the resource capacity is not exceeded */
1542 SCIP_CALL( SCIPcreateConsBasicKnapsack(subscip, &cons, name, 0, NULL, NULL, (SCIP_Longint)capacity) );
1603 SCIPdebugMsg(scip, "solved single cumulative condition with status %d\n", SCIPgetStatus(subscip));
1669 /* check which binary varibale is the first binary varibale which is not globally fixed to zero */
1679 /* check which binary varibale is the last binary varibale which is not globally fixed to zero */
1734 * Method used to create and free the constraint handler data when including and removing the cumulative constraint
1899 SCIP_CONS** linkingconss, /**< array of linking constraints for the integer variables, or NULL */
1958 /* initialize variable lock data structure; the locks are only used if the contraint is a check constraint */
1963 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->linkingconss, linkingconss, nvars) );
1972 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
1974 /* multi-aggregated variables cannot be replaced by active variable; therefore we mark all variables for not
1985 SCIP_CALL( SCIPtransformConss(scip, (*consdata)->nvars, (*consdata)->linkingconss, (*consdata)->linkingconss) );
2139 SCIPinfoMessage(scip, file, ")[%d,%d) <= %d", consdata->hmin, consdata->hmax, consdata->capacity);
2164 SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, consdata->downlocks[pos], consdata->uplocks[pos]) );
2185 SCIPvarGetName(consdata->vars[pos]), SCIPvarGetLbGlobal(consdata->vars[pos]), SCIPvarGetUbGlobal(consdata->vars[pos]), SCIPconsGetName(cons));
2187 /* in case the we did not remove the variable in the last slot of the arrays we move the current last to this
2238 SCIPdebugMsg(scip, "linking constraint (%d of %d) for variable <%s>\n", v+1, nvars, SCIPvarGetName(var));
2261 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(consdata->linkingconss[v])), "linking") == 0 );
2276 /** check for the given starting time variables with their demands and durations if the cumulative conditions for the
2284 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
2297 int* startindices; /* we will sort the startsolvalues, thus we need to know which index of a job it corresponds to */
2298 int* endindices; /* we will sort the endsolvalues, thus we need to know which index of a job it corresponds to */
2320 /* compute time points where we have to check whether capacity constraint is infeasible or not */
2331 /* the constraint of the cumulative constraint handler should be called after the integrality check */
2336 /* we need to ensure that we check at least one time point during the effective horizon; therefore we project all
2346 /* sort the arrays not-decreasing according to start solution values and end solution values (and sort the
2434 /** check if the given constrait is valid; checks each starting point of a job whether the remaining capacity is at
2487 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2490 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2504 SCIPdebugMsg(scip, "variable <%s>: (demand %d) resolve propagation of core time algorithm (peak %d)\n",
2516 /* first we loop over all variables and adjust the capacity with those jobs which provide a global core at the
2517 * inference peak and those where the current conflict bounds provide a core at the inference peak
2531 /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */
2532 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)));
2534 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)));
2544 /* check if the inference peak is part of the global bound core; if so we decreasing the capacity by the demand of
2562 /* collect the conflict bound core (the conflict bounds are those bounds which are already part of the conflict)
2563 * hence these bound are already reported by other resolve propation steps. In case a bound (lower or upper) is
2569 /* check if the inference peak is part of the conflict bound core; if so we decreasing the capacity by the demand
2572 * @note we do not need to reported that job to SCIP since the required bounds are already reported
2599 /* collect all cores of the variables which lay in the considered time window except the inference variable */
2612 /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */
2613 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)));
2615 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)));
2623 SCIPvarGetName(var), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE),
2667 SCIPdebugMsg(scip, "infer peak %d, relaxed peak %d, lst %d, ect %d\n", inferpeak, relaxedpeak, maxlst, minect);
2695 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(inferpeak - duration + 1)) );
2721 /** repropagation of edge finding algorithm simplified version from Petr Vilim only a small subset is reported such that
2735 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2737 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2750 SCIPdebugMsg(scip, "repropagate edge-finding with short reasons for variable <%s>\n", SCIPvarGetName(infervar));
2792 /* in case the earliest start time is equal to hmin we have to also consider the jobs which run in that region
2797 /* in case the latest completion time is equal to hmax we have to also consider the jobs which run in that region
2826 /** compute the minimum overlaps w.r.t. the duration of the job and the time window [begin,end) */
2859 /** an overload was detected due to the time-time edge-finding propagate; initialized conflict analysis, add an initial
2862 * @note the conflict analysis is not performend, only the initialized SCIP_Bool pointer is set to TRUE
2876 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2879 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2896 SCIPdebugMsg(scip, "analysis energy load in [%d,%d) (capacity %d, energy %" SCIP_LONGINT_FORMAT ")\n", begin, end, capacity, requiredenergy);
2898 /* collect global contribution and adjusted the required energy by the amount of energy the inference variable
2933 SCIPvarGetName(var), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE),
2936 /* compute the amount of energy which needs to be available for enforcing the propagation and report the bound
2943 /* get the latest start time of the infer start time variable before the propagation took place */
2946 /* the latest start time of the inference start time variable before the propagation needs to be smaller as
2947 * the end of the time interval; meaning the job needs be overlap with the time interval in case the job is
2952 /* compute the overlap of the job in case it would be scheduled w.r.t. its latest start time and the time
2957 /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */
2962 assert(bdchgidx == NULL || SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE)) < begin);
2976 assert(SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)) <= (end - overlap));
2990 /* get the earliest completion time of the infer start time variable before the propagation took place */
2993 /* the earliest start time of the inference start time variable before the propagation needs to be larger as
2994 * than the beginning of the time interval; meaning the job needs be overlap with the time interval in case
2999 /* compute the overlap of the job in case it would be scheduled w.r.t. its earliest start time and the time
3004 /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */
3023 assert(SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) >= (begin + overlap - duration));
3024 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(begin + overlap - duration)) );
3032 /* subtract the amount of energy which is available due to the overlap of the inference start time */
3047 /* check if the has any overlap w.r.t. global bound; meaning some parts of the job will run for sure within the
3066 /* check if the job has any overlap w.r.t. local bound; meaning some parts of the job will run for sure within the
3127 SCIPdebugMsg(scip, "variable <%s> glb=[%g,%g] loc=[%g,%g], conf=[%g,%g], added=[%d,%d] (demand %d, duration %d)\n",
3164 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
3167 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
3168 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
3198 /* we propagated the latest start time (upper bound) step wise with a step length of at most the duration of
3201 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE) - SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < inferduration + 0.5);
3209 /* the bound passed back to be resolved might be tighter as the bound propagted by the core time propagator;
3210 * this can happen if the variable is not activ and aggregated to an activ variable with a scale != 1.0
3212 assert(SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE)) + inferduration <= inferpeak);
3236 /* the bound passed back to be resolved might be tighter as the bound propagted by the core time propagator;
3237 * this can happen if the variable is not activ and aggregated to an activ variable with a scale != 1.0
3239 assert(SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE)) - 1 >= inferpeak);
3254 SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
3255 infervar, inferdemand, inferpeak, relaxedpeak, bdchgidx, usebdwidening, &provedpeak, explanation) );
3275 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, bdchgidx, (SCIP_Real)(provedpeak - inferduration + 1)) );
3353 if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == downlocks[v] && !SCIPisNegative(scip, objval) )
3361 SCIP_CALL( SCIPbranchVarHole(scip, var, SCIPvarGetLbLocal(var), (SCIP_Real)alternativelbs[v], NULL, NULL) );
3371 if( SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == uplocks[v] && !SCIPisPositive(scip, objval) )
3379 SCIP_CALL( SCIPbranchVarHole(scip, var, (SCIP_Real)alternativeubs[v], SCIPvarGetUbLocal(var), NULL, NULL) );
3464 /** computes a point in time when the capacity is exceeded returns hmax if this does not happen */
3475 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
3476 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
3521 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars);
3549 /** checks all cumulative constraints for infeasibility and add branching candidates to storage */
3726 /** in case the cumulative constraint is independent of every else, solve the cumulative problem and apply the fixings
3733 SCIP_Longint maxnodes, /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
3759 /* if SCIP is in probing mode or repropagation we cannot perform this dual reductions since this dual reduction
3765 /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
3773 /* if the cumulative constraint is the only constraint of the original problem or the only check constraint in the
3787 /* after 250 conflict we force a restart since then the variable statistics are reasonable initialized */
3823 /* check if already tried to solve that constraint as independent sub problem; we do not want to try it again if we
3833 /* mark the constraint to be tried of solving it as independent sub problem; in case that is successful the
3838 SCIPdebugMsg(scip, "the cumulative constraint <%s> is independent from rest of the problem (%d variables, %d constraints)\n",
3853 /* if a variables array is given, use the variable bounds otherwise the default values stored in the ests and lsts
3871 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
3879 SCIP_CALL( SCIPsolveCumulative(scip, nvars, lbs, ubs, objvals, consdata->durations, consdata->demands, consdata->capacity,
3880 consdata->hmin, consdata->hmax, timelimit, memorylimit, maxnodes, &solved, cutoff, unbounded, &error) );
3960 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
3963 SCIPdebugMsg(scip, "detected infeasibility due to adding a core to the core resource profile\n");
3964 SCIPdebugMsg(scip, "variable <%s>[%g,%g] (demand %d, duration %d)\n", SCIPvarGetName(infervar),
3972 SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
3977 /* add both bound of the inference variable since these biuld the core which we could not inserted */
3980 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, NULL, (SCIP_Real)(inferpeak - inferduration + 1)) );
3995 /** We are using the core resource profile which contains all core except the one of the start time variable which we
3996 * want to propagate, to incease the earliest start time. This we are doing in steps of length at most the duration of
3997 * the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict
4016 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4043 /* first we find left position of earliest start time (lower bound) in resource profile; this position gives us the
4069 /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we
4082 /* if we found no peak that means current the job could be scheduled at its earliest start time without
4089 /* the peak position gives us a time point where the start time variable is in conflict with the resource
4090 * profile. That means we have to move it to the next time point in the resource profile but at most to the
4102 SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
4113 /* construct the inference information which we are using with the conflict analysis to resolve that particular
4121 SCIP_CALL( SCIPinferVarLbCons(scip, var, (SCIP_Real)newlb, cons, inferInfoToInt(inferinfo), TRUE, infeasible, &tightened) );
4130 SCIPdebugMsg(scip, "variable <%s> new lower bound <%d> -> <%d>\n", SCIPvarGetName(var), est, newlb);
4133 /* for the statistic we count the number of times a lower bound was tightened due the the time-table algorithm */
4138 * @note We are taking the lower of the start time variable on purpose instead of newlb. This is due the fact that
4139 * the proposed lower bound might be even strength by be the core which can be the case if aggregations are
4156 /** We are using the core resource profile which contains all core except the one of the start time variable which we
4157 * want to propagate, to decrease the latest start time. This we are doing in steps of length at most the duration of
4158 * the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict
4197 /* first we find left position of latest completion time minus 1 (upper bound + duration) in resource profile; That
4198 * is the last time point where the job would run if schedule it at its latest start time (upper bound). This
4228 /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we
4240 /* if we found no peak that means the current job could be scheduled at its latest start time without conflicting
4247 /* the peak position gives us a time point where the start time variable is in conflict with the resource
4248 * profile. That means the job has be done until that point. Hence that gives us the latest completion
4249 * time. Note that that we want to move the bound by at most the duration length (the remaining move we are
4256 /* construct the inference information which we are using with the conflict analysis to resolve that particular
4264 SCIP_CALL( SCIPinferVarUbCons(scip, var, (SCIP_Real)newub, cons, inferInfoToInt(inferinfo), TRUE, &infeasible, &tightened) );
4273 SCIPdebugMsg(scip, "variable <%s>: new upper bound <%d> -> <%d>\n", SCIPvarGetName(var), lst, newub);
4276 /* for the statistic we count the number of times a upper bound was tightened due the the time-table algorithm */
4281 * @note We are taking the upper of the start time variable on purpose instead of newub. This is due the fact that
4282 * the proposed upper bound might be even strength by be the core which can be the case if aggregations are
4300 /** compute for the different earliest start and latest completion time the core energy of the corresponding time
4309 int* coreEnergyAfterEst, /**< array to store the core energy after the earliest start time of each job */
4310 int* coreEnergyAfterLct /**< array to store the core energy after the latest completion time of each job */
4329 energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1));
4338 coreEnergyAfterEst[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - ests[v]);
4354 energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1));
4363 coreEnergyAfterLct[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - lcts[v]);
4458 SCIP_Longint energy, /**< available energy for the flexible part of the hob within the time window */
4460 int* inferinfos, /**< pointer to store the inference information which is need for the (best) lower bound change */
4462 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4475 /* if the job can be processed completely before or after the time window, nothing can be tightened */
4479 /* if flexible part runs completely within the time window (assuming it is scheduled on its earliest start time), we
4485 /* check if the available energy in the time window is to small to handle the flexible part if it is schedule on its
4491 /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is
4494 * @note the variable ect define the earliest completion time of the flexible part of the job; hence we need to
4499 /* compute a latest start time (upper bound) such that the job consums at most the available energy
4505 /* check if we detected an infeasibility which is the case if the new lower bound is larger than the current upper
4528 begin, end, var, SCIP_BOUNDTYPE_LOWER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) );
4571 SCIP_Longint energy, /**< available energy for the flexible part of the hob within the time window */
4573 int* inferinfos, /**< pointer to store the inference information which is need for the (best) upper bound change */
4575 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4589 /* if flexible part of the job can be processed completely before or after the time window, nothing can be tightened */
4593 /* if flexible part runs completely within the time window (assuming it is scheduled on its latest start time), we
4599 /* check if the available energy in the time window is to small to handle the flexible part of the job */
4603 /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is
4606 * @note the variable lst define the latest start time of the flexible part of the job; hence we need to compute the
4612 /* compute a latest start time (upper bound) such that the job consums at most the available energy
4619 /* check if we detected an infeasibility which is the case if the new upper bound is smaller than the current lower
4642 begin, end, var, SCIP_BOUNDTYPE_UPPER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) );
4665 /** propagate the upper bounds and "opportunistically" the lower bounds using the time-table edge-finding algorithm */
4679 int* lbinferinfos, /**< array to store the inference information for the lower bound changes */
4680 int* ubinferinfos, /**< array to store the inference information for the upper bound changes */
4681 int* lsts, /**< array of latest start time of the flexible part in the same order as the variables */
4683 int* perm, /**< permutation of the variables w.r.t. the non-decreasing order of the earliest start times */
4689 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4728 /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */
4734 /* loop over all variable in non-increasing order w.r.t. the latest completion time; thereby, the latest completion
4747 /* if the latest completion time is larger then hmax an infeasibility cannot be detected, since after hmax an
4760 /* if the latest completion time equals to previous end time, we can continue since this particular interval
4768 /* In case we only want to detect an overload (meaning no bound propagation) we can skip the interval; this is
4769 * the case if the free energy (the energy which is not occupied by any core) is smaller than the previous minimum
4780 freeenergy = capacity * ((SCIP_Longint) end - lct) - coreEnergyAfterLct[v] + coreEnergyAfterEnd;
4784 SCIPdebugMsg(scip, "skip latest completion time <%d> (minimum available energy <%" SCIP_LONGINT_FORMAT ">, free energy <%" SCIP_LONGINT_FORMAT ">)\n", lct, minavailable, freeenergy);
4800 /* loop over the job in non-increasing order w.r.t. the earliest start time; these earliest start time are
4801 * defining the beginning of the time interval under investigation; Thereby, the time interval gets wider and
4822 /* if the job starts after the current end, we can skip it and do not need to consider it again since the
4831 /* check if the interval has a size such that the total energy fits, if so we can skip all intervals with the
4851 /* in case the earliest start time is equal to minbegin, the job lies completely within the time window under
4860 SCIP_CALL( tightenUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
4861 var, duration, demand, est, lst, lct, minbegin, end, minavailable, &(newubs[idx]), &(ubinferinfos[idx]),
4868 SCIPdebugMsg(scip, "check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, lst of free part <%d>\n",
4869 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, lst);
4874 /* if the earliest start time is smaller than hmin we can stop here since the next job will not decrease the
4894 /* compute the flexible energy which is part of the time interval for sure if the job is scheduled
4906 /* compute the flexible energy of the job which is not part of flexible energy of the time interval */
4922 freeenergy = capacity * ((SCIP_Longint) end - begin) - flexenergy - coreEnergyAfterEst[i] + coreEnergyAfterEnd;
4927 SCIPdebugMsg(scip, "analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
4944 /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */
4945 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
4950 /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */
4961 energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, (SCIP_Longint) end - lsts[lbcand])) * demands[lbcand];
5016 /** propagate the lower bounds and "opportunistically" the upper bounds using the time-table edge-finding algorithm */
5030 int* lbinferinfos, /**< array to store the inference information for the lower bound changes */
5031 int* ubinferinfos, /**< array to store the inference information for the upper bound changes */
5032 int* ects, /**< array of earliest completion time of the flexible part in the same order as the variables */
5034 int* perm, /**< permutation of the variables w.r.t. the non-decreasing order of the latest completion times */
5040 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
5081 /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */
5087 /* loop over all variable in non-decreasing order w.r.t. the earliest start times; thereby, the earliest start times
5101 /* if the earliest start time is smaller then hmin an infeasibility cannot be detected, since before hmin an
5111 /* if the latest earliest start time equals to previous start time, we can continue since this particular interval
5130 /* loop over the job in non-decreasing order w.r.t. the latest completion time; these latest completion times are
5131 * defining the ending of the time interval under investigation; thereby, the time interval gets wider and wider
5151 /* if the job has a latest completion time before the the current start, we can skip it and do not need to
5152 * consider it again since the earliest start times (which define the start) are scant in non-decreasing order
5160 /* check if the interval has a size such that the total energy fits, if so we can skip all intervals which
5180 /* in case the latest completion time is equal to minend, the job lies completely within the time window under
5189 SCIP_CALL( tightenLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5190 var, duration, demand, est, ect, lct, begin, minend, minavailable, &(newlbs[idx]), &(lbinferinfos[idx]),
5197 SCIPdebugMsg(scip, "check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, ect of free part <%d>\n",
5198 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, ect);
5203 /* if the latest completion time is larger than hmax we can stop here since the next job will not decrease the
5223 /* compute the flexible energy which is part of the time interval for sure if the job is scheduled
5235 /* compute the flexible energy of the job which is not part of flexible energy of the time interval */
5251 freeenergy = capacity * ((SCIP_Longint) end - begin) - flexenergy - coreEnergyAfterStart + coreEnergyAfterLct[i];
5256 SCIPdebugMsg(scip, "analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
5273 /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */
5274 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
5279 /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */
5293 energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, (SCIP_Longint) ects[ubcand] - begin)) * demands[ubcand];
5347 /** checks whether the instance is infeasible due to a overload within a certain time frame using the idea of time-table
5351 * - Petr Vilim, "Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources", In: Tobias
5352 * Achterberg and J. Christopher Beck (Eds.), Integration of AI and OR Techniques in Constraint Programming for
5354 * - Andreas Schutt, Thibaut Feydy, and Peter J. Stuckey, "Explaining Time-Table-Edge-Finding Propagation for the
5372 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
5418 /* we need to buffer the bound changes since the propagation algorithm cannot handle new bound dynamically */
5428 collectDataTTEF(scip, nvars, vars, durations, demands, hmin, hmax, permests, ests, permlcts, lcts, ects, lsts, flexenergies);
5434 /* compute for the different earliest start and latest completion time the core energy of the corresponding time
5440 SCIP_CALL( propagateUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5442 permests, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );
5445 SCIP_CALL( propagateLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5447 permlcts, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );
5462 SCIP_CALL( SCIPtightenVarLb(scip, vars[v], (SCIP_Real)newlbs[v], TRUE, &infeasible, &tightened) );
5465 /* since we change first the lower bound of the variable an infeasibilty should not be detected */
5483 SCIP_CALL( SCIPtightenVarUb(scip, vars[v], (SCIP_Real)newubs[v], TRUE, &infeasible, &tightened) );
5486 /* since upper bound was compute w.r.t. the "old" bound the previous lower bound update together with this upper
5491 /* a small performance improvement is possible here: if the tighten...TEFF and propagate...TEFF methods would
5492 * return not only the inferinfos, but the actual begin and end values, then the infeasibility here could also
5495 if( SCIPisConflictAnalysisApplicable(scip) && inferInfoIsValid(intToInferInfo(ubinferinfos[v])) )
5528 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
5562 /** a cumulative condition is not satisfied if its capacity is exceeded at a time where jobs cannot be shifted (core)
5563 * anymore we build up a cumulative profile of all cores of jobs and try to improve bounds of all jobs; also known as
5581 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
5603 SCIPdebugMsg(scip, "propagate cores of cumulative condition of constraint <%s>[%d,%d) <= %d\n",
5637 /* check if the job runs completely outside of the effective horizon [hmin, hmax); if so skip it */
5652 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, begin, end);
5658 SCIP_CALL( coretimesUpdateLb(scip, nvars, vars, durations, demands, capacity, hmin, hmax, cons,
5692 SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
5693 var, duration, demand, SCIPprofileGetTime(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) );
5701 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutofftimetable++ );
5715 SCIP_VAR* var; /**< start time variable of the job if the node data belongs to a leaf, otherwise NULL */
5723 SCIP_Longint enveloptheta; /**< the maximal energy of a subset of jobs part of the theta set */
5773 nodedata->enveloptheta = MAX(leftdata->enveloptheta + rightdata->energytheta, rightdata->enveloptheta);
5785 nodedata->enveloplambda = MAX(leftdata->enveloplambda + rightdata->energytheta, rightdata->enveloplambda);
5791 nodedata->enveloplambda = MAX(nodedata->enveloplambda, leftdata->enveloptheta + rightdata->energylambda);
5793 SCIPdebugMsg(scip, "node <%p> lambda envelop %" SCIP_LONGINT_FORMAT "\n", (void*)node, nodedata->enveloplambda);
5799 nodedata->energylambda = MAX(leftdata->energylambda + rightdata->energytheta, leftdata->energytheta + rightdata->energylambda);