All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
cons_cumulative.c
Go to the documentation of this file.
23 * - 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
27 * 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.
41 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
61 #define CONSHDLR_ENFOPRIORITY -2040000 /**< priority of the constraint handler for constraint enforcing */
62 #define CONSHDLR_CHECKPRIORITY -3030000 /**< priority of the constraint handler for checking feasibility */
63 #define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
64 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
65 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
67 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
68 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
69 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
70 #define CONSHDLR_DELAYPRESOL FALSE /**< should presolving method be delayed, if other presolvers found reductions? */
71 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
92 #define DEFAULT_TTINFER TRUE /**< should time-table (core-times) propagator be used to infer bounds? */
95 #define DEFAULT_USEADJUSTEDJOBS FALSE /**< should during edge-finding jobs be adusted which run on the border of the effective time horizon? */
96 #define DEFAULT_TTEFCHECK TRUE /**< should time-table edge-finding be used to detect an overload? */
103 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
105 #define DEFAULT_DETECTDISJUNCTIVE TRUE /**< search for conflict set via maximal cliques to detect disjunctive constraints */
106 #define DEFAULT_DETECTVARBOUNDS TRUE /**< search for conflict set via maximal cliques to detect variable bound constraints */
107 #define DEFAULT_MAXNODES 10000LL /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
113 #define DEFAULT_USEBDWIDENING TRUE /**< should bound widening be used during conflict analysis? */
168 unsigned int varbounds:1; /**< bool to store if variable bound strengthening was already preformed */
169 unsigned int triedsolving:1; /**< bool to store if we tried already to solve that constraint as independent subproblem */
182 SCIP_Bool cutsasconss; /**< should the cumulative constraint create cuts as knapsack constraints? */
186 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? */
205 SCIP_Longint maxnodes; /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
207 SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)); /**< method to use a single cumulative condition */
211 SCIP_Longint nlbtimetable; /**< number of times the lower bound was tightened by the time-table propagator */
212 SCIP_Longint nubtimetable; /**< number of times the upper bound was tightened by the time-table propagator */
213 SCIP_Longint ncutofftimetable; /**< number of times the a cutoff was detected due to time-table propagator */
214 SCIP_Longint nlbedgefinder; /**< number of times the lower bound was tightened by the edge-finder propagator */
215 SCIP_Longint nubedgefinder; /**< number of times the upper bound was tightened by the edge-finder propagator */
216 SCIP_Longint ncutoffedgefinder; /**< number of times the a cutoff was detected due to edge-finder propagator */
217 SCIP_Longint ncutoffoverload; /**< number of times the a cutoff was detected due to overload checking via edge-finding */
218 SCIP_Longint nlbTTEF; /**< number of times the lower bound was tightened by time-table edge-finding */
219 SCIP_Longint nubTTEF; /**< number of times the upper bound was tightened by time-table edge-finding */
220 SCIP_Longint ncutoffoverloadTTEF;/**< number of times the a cutoff was detected due to overload checking via time-table edge-finding */
222 int nirrelevantjobs; /**< number of time a irrelevant/redundant jobs was removed form a constraint */
223 int nalwaysruns; /**< number of time a job removed form a constraint which run completely during the effective horizon */
227 int ndualbranchs; /**< number of times a dual branch was discoverd and applicable via probing */
228 int nallconsdualfixs; /**< number of times a dual fix was performed due to knowledge of all cumulative constraints */
238 * An inference information can be passed with each domain reduction to SCIP. This information is passed back to the
239 * constraint handler if the corresponding bound change has to be explained. It can be used to store information which
240 * help to construct a reason/explanation for a bound change. The inference information is limited to size of integer.
242 * In case of the cumulative constraint handler we store the used propagation algorithms for that particular bound
324 /** constructs an inference information out of a propagation rule, an earliest start and a latest completion time */
358 /** converts the given double bound which is integral to an int; in optimized mode the function gets inlined for
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 */
742 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
782 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
833 SCIPdebugMessage("%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
834 *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var),
853 SCIPdebugMessage("%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
854 *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var),
863 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
898 SCIP_Real** cumulativedemands, /**< array to store the estimated cumulative demand for each point in time */
906 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
907 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
932 createSortedEventpoints(scip, nvars, vars, durations, starttimes, endtimes, startindices, endindices, TRUE);
1118 disjfactor2 = MAX( disjfactor2, (peak-(SCIP_Real)capacity)/peak * (nlarge/(SCIP_Real)ndemands) );
1119 cumfactor1 = MAX( cumfactor1, (peak-capacity)/peak * (capacity-deltademand)/(SCIP_Real)capacity );
1159 SCIPstatisticPrintf("cumulative constraint<%s>: DISJ1=%g, DISJ2=%g, CUM=%g, RS1 = %g, RS2 = %g, EST = %g\n",
1160 SCIPconsGetName(cons), consdata->disjfactor1, disjfactor2, cumfactor1, resstrength1, resstrength2,
1282 SCIP_CALL( SCIPcreateVarBasic(subscip, &subvars[v], name, ests[v], lsts[v], objval, SCIP_VARTYPE_INTEGER) );
1300 * @note This "meta" setting has to be set first since this call overwrite all parameters including for example the
1323 SCIPdebugMessage("solved single cumulative condition with status %d\n", SCIPgetStatus(subscip));
1429 /* create for each job and time step a binary variable which is one if this jobs starts at this time point and a set
1470 SCIP_CALL( SCIPcreateVarBasic(subscip, &binvar, name, 0.0, 1.0, objval, SCIP_VARTYPE_BINARY) );
1473 /* add binary varibale to the set partitioning constraint which ensures that the job is started */
1484 /* adjusted the smallest earliest start time and the largest latest completion time with the effective horizon */
1491 /* create for each time a knapsack constraint which ensures that the resource capacity is not exceeded */
1500 SCIP_CALL( SCIPcreateConsBasicKnapsack(subscip, &cons, name, 0, NULL, NULL, (SCIP_Longint)capacity) );
1561 SCIPdebugMessage("solved single cumulative condition with status %d\n", SCIPgetStatus(subscip));
1627 /* check which binary varibale is the first binary varibale which is not globally fixed to zero */
1637 /* check which binary varibale is the last binary varibale which is not globally fixed to zero */
1692 * Method used to create and free the constraint handler data when including and removing the cumulative constraint
1857 SCIP_CONS** linkingconss, /**< array of linking constraints for the integer variables, or NULL */
1916 /* initialize variable lock data structure; the locks are only used if the contraint is a check constraint */
1921 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->linkingconss, linkingconss, nvars) );
1930 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
1932 /* multi-aggregated variables cannot be replaced by active variable; therefore we mark all variables for not
1943 SCIP_CALL( SCIPtransformConss(scip, (*consdata)->nvars, (*consdata)->linkingconss, (*consdata)->linkingconss) );
2097 SCIPinfoMessage(scip, file, ")[%d,%d) <= %d", consdata->hmin, consdata->hmax, consdata->capacity);
2122 SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, consdata->downlocks[pos], consdata->uplocks[pos]) );
2143 SCIPvarGetName(consdata->vars[pos]), SCIPvarGetLbGlobal(consdata->vars[pos]), SCIPvarGetUbGlobal(consdata->vars[pos]), SCIPconsGetName(cons));
2146 /* in case the we did not remove the variable in the last slot of the arrays we move the current last to this
2197 SCIPdebugMessage("linking constraint (%d of %d) for variable <%s>\n", v+1, nvars, SCIPvarGetName(var));
2220 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(consdata->linkingconss[v])), "linking") == 0 );
2235 /** check for the given starting time variables with their demands and durations if the cumulative conditions for the
2243 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
2256 int* startindices; /* we will sort the startsolvalues, thus we need to know which index of a job it corresponds to */
2257 int* endindices; /* we will sort the endsolvalues, thus we need to know which index of a job it corresponds to */
2276 /* compute time points where we have to check whether capacity constraint is infeasible or not */
2287 /* the constraint of the cumulative constraint handler should be called after the integrality check */
2292 /* we need to ensure that we check at least one time point during the effective horizon; therefore we project all
2302 /* sort the arrays not-decreasing according to start solution values and end solution values (and sort the
2377 /** check if the given constrait is valid; checks each starting point of a job whether the remaining capacity is at
2430 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2433 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2447 SCIPdebugMessage("variable <%s>: (demand %d) resolve propagation of core time algorithm (peak %d)\n",
2459 /* first we loop over all variables and adjust the capacity with those jobs which provide a global core at the
2460 * inference peak and those where the current conflict bounds provide a core at the inference peak
2474 /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */
2475 assert(SCIPisFeasEQ(scip, SCIPvarGetUbAtIndex(var, bdchgidx, TRUE), SCIPvarGetUbAtIndex(var, bdchgidx, FALSE)));
2477 assert(SCIPisFeasEQ(scip, SCIPvarGetLbAtIndex(var, bdchgidx, TRUE), SCIPvarGetLbAtIndex(var, bdchgidx, FALSE)));
2487 /* check if the inference peak is part of the global bound core; if so we decreasing the capacity by the demand of
2505 /* collect the conflict bound core (the conflict bounds are those bounds which are already part of the conflict)
2506 * hence these bound are already reported by other resolve propation steps. In case a bound (lower or upper) is
2512 /* check if the inference peak is part of the conflict bound core; if so we decreasing the capacity by the demand
2515 * @note we do not need to reported that job to SCIP since the required bounds are already reported
2542 /* collect all cores of the variables which lay in the considered time window except the inference variable */
2555 /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */
2556 assert(SCIPisFeasEQ(scip, SCIPvarGetUbAtIndex(var, bdchgidx, TRUE), SCIPvarGetUbAtIndex(var, bdchgidx, FALSE)));
2558 assert(SCIPisFeasEQ(scip, SCIPvarGetLbAtIndex(var, bdchgidx, TRUE), SCIPvarGetLbAtIndex(var, bdchgidx, FALSE)));
2566 SCIPvarGetName(var), SCIPvarGetLbAtIndex(var, bdchgidx, FALSE), SCIPvarGetUbAtIndex(var, bdchgidx, FALSE),
2610 SCIPdebugMessage("infer peak %d, relaxed peak %d, lst %d, ect %d\n", inferpeak, relaxedpeak, maxlst, minect);
2638 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(inferpeak - duration + 1)) );
2664 /** repropagation of edge finding algorithm simplified version from Petr Vilim only a small subset is reported such that
2678 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2680 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2693 SCIPdebugMessage("repropagate edge-finding with short reasons for variable <%s>\n", SCIPvarGetName(infervar));
2735 /* in case the earliest start time is equal to hmin we have to also consider the jobs which run in that region
2740 /* in case the latest completion time is equal to hmax we have to also consider the jobs which run in that region
2769 /** compute the minimum overlaps w.r.t. the duration of the job and the time window [begin,end) */
2802 /** an overload was detected due to the time-time edge-finding propagate; initialized conflict analysis, add an initial
2805 * @note the conflict analysis is not performend, only the initialized SCIP_Bool pointer is set to TRUE
2819 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2822 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2839 SCIPdebugMessage("analysis energy load in [%d,%d) (capacity %d, energy %d)\n", begin, end, capacity, requiredenergy);
2841 /* collect global contribution and adjusted the required energy by the amount of energy the inference variable
2876 SCIPvarGetName(var), SCIPvarGetLbAtIndex(var, bdchgidx, FALSE), SCIPvarGetUbAtIndex(var, bdchgidx, FALSE),
2879 /* compute the amount of energy which needs to be available for enforcing the propagation and report the bound
2886 /* get the latest start time of the infer start time variable before the propagation took place */
2889 /* the latest start time of the inference start time variable before the propagation needs to be smaller as
2890 * the end of the time interval; meaning the job needs be overlap with the time interval in case the job is
2895 /* compute the overlap of the job in case it would be scheduled w.r.t. its latest start time and the time
2900 /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */
2905 assert(bdchgidx == NULL || convertBoundToInt(scip, SCIPvarGetUbAtIndex(var, bdchgidx, TRUE)) < begin);
2933 /* get the earliest completion time of the infer start time variable before the propagation took place */
2936 /* the earliest start time of the inference start time variable before the propagation needs to be larger as
2937 * than the beginning of the time interval; meaning the job needs be overlap with the time interval in case
2942 /* compute the overlap of the job in case it would be scheduled w.r.t. its earliest start time and the time
2947 /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */
2966 assert(convertBoundToInt(scip, SCIPvarGetLbAtIndex(var, bdchgidx, FALSE)) >= (begin + overlap - duration));
2967 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(begin + overlap - duration)) );
2975 /* subtract the amount of energy which is available due to the overlap of the inference start time */
2990 /* check if the has any overlap w.r.t. global bound; meaning some parts of the job will run for sure within the
3009 /* check if the job has any overlap w.r.t. local bound; meaning some parts of the job will run for sure within the
3070 SCIPdebugMessage("variable <%s> glb=[%g,%g] loc=[%g,%g], conf=[%g,%g], added=[%d,%d] (demand %d, duration %d)\n",
3107 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
3110 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
3111 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
3141 /* we propagated the latest start time (upper bound) step wise with a step length of at most the duration of
3144 assert(SCIPvarGetUbAtIndex(infervar, bdchgidx, FALSE) - SCIPvarGetUbAtIndex(infervar, bdchgidx, TRUE) < inferduration + 0.5);
3151 inferpeak = convertBoundToInt(scip, SCIPvarGetUbAtIndex(infervar, bdchgidx, TRUE)) + inferduration;
3180 SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
3181 infervar, inferdemand, inferpeak, relaxedpeak, bdchgidx, usebdwidening, &provedpeak, explanation) );
3201 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, bdchgidx, (SCIP_Real)(provedpeak - inferduration + 1)) );
3286 SCIP_CALL( SCIPbranchVarHole(scip, var, SCIPvarGetLbLocal(var), (SCIP_Real)alternativelbs[v], NULL, NULL) );
3304 SCIP_CALL( SCIPbranchVarHole(scip, var, (SCIP_Real)alternativeubs[v], SCIPvarGetUbLocal(var), NULL, NULL) );
3387 /** computes a point in time when the capacity is exceeded returns hmax if this does not happen */
3398 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
3399 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
3444 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars);
3472 /** checks all cumulative constraints for infeasibility and add branching candidates to storage */
3489 SCIP_CALL( SCIPhashtableCreate(&collectedvars, SCIPblkmem(scip), SCIPcalcHashtableSize(SCIPgetNVars(scip)),
3641 if( SCIPvarGetNLocksDown(var) > (int)downlocks[v] || SCIPvarGetNLocksUp(var) > (int)uplocks[v] )
3648 /** in case the cumulative constraint is independent of every else, solve the cumulative problem and apply the fixings
3655 SCIP_Longint maxnodes, /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
3681 /* if SCIP is in probing mode or repropagation we cannot perform this dual reductions since this dual reduction
3687 /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
3695 /* if the cumulative constraint is the only constraint of the original problem or the only check constraint in the
3709 /* after 250 conflict we force a restart since then the variable statistics are reasonable initialized */
3745 /* check if already tried to solve that constraint as independent sub problem; we do not want to try it again if we
3755 /* mark the constraint to be tried of solving it as independent sub problem; in case that is successful the
3760 SCIPdebugMessage("the cumulative constraint <%s> is independent from rest of the problem (%d variables, %d constraints)\n",
3775 /* if a variables array is given, use the variable bounds otherwise the default values stored in the ests and lsts
3793 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
3801 SCIP_CALL( SCIPsolveCumulative(scip, nvars, lbs, ubs, objvals, consdata->durations, consdata->demands, consdata->capacity,
3802 consdata->hmin, consdata->hmax, timelimit, memorylimit, maxnodes, &solved, cutoff, unbounded, &error) );
3882 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
3885 SCIPdebugMessage("detected infeasibility due to adding a core to the core resource profile\n");
3894 SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
3899 /* add both bound of the inference variable since these biuld the core which we could not inserted */
3902 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, NULL, (SCIP_Real)(inferpeak - inferduration + 1)) );
3917 /** We are using the core resource profile which contains all core except the one of the start time variable which we
3918 * want to propagate, to incease the earliest start time. This we are doing in steps of length at most the duration of
3919 * the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict
3938 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
3965 /* first we find left position of earliest start time (lower bound) in resource profile; this position gives us the
3991 /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we
4004 /* if we found no peak that means current the job could be scheduled at its earliest start time without
4010 /* the peak position gives us a time point where the start time variable is in conflict with the resource
4011 * profile. That means we have to move it to the next time point in the resource profile but at most to the
4023 SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
4034 /* construct the inference information which we are using with the conflict analysis to resolve that particular
4040 SCIP_CALL( SCIPinferVarLbCons(scip, var, (SCIP_Real)newlb, cons, inferInfoToInt(inferinfo), TRUE, infeasible, &tightened) );
4044 SCIPdebugMessage("variable <%s> new lower bound <%d> -> <%d>\n", SCIPvarGetName(var), est, newlb);
4047 /* for the statistic we count the number of times a lower bound was tightened due the the time-table algorithm */
4052 * @note We are taking the lower of the start time variable on purpose instead of newlb. This is due the fact that
4053 * the proposed lower bound might be even strength by be the core which can be the case if aggregations are
4070 /** We are using the core resource profile which contains all core except the one of the start time variable which we
4071 * want to propagate, to decrease the latest start time. This we are doing in steps of length at most the duration of
4072 * the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict
4111 /* first we find left position of latest completion time minus 1 (upper bound + duration) in resource profile; That
4112 * is the last time point where the job would run if schedule it at its latest start time (upper bound). This
4142 /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we
4154 /* if we found no peak that means the current job could be scheduled at its latest start time without conflicting
4160 /* the peak position gives us a time point where the start time variable is in conflict with the resource
4161 * profile. That means the job has be done until that point. Hence that gives us the latest completion
4162 * time. Note that that we want to move the bound by at most the duration length (the remaining move we are
4169 /* construct the inference information which we are using with the conflict analysis to resolve that particular
4175 SCIP_CALL( SCIPinferVarUbCons(scip, var, (SCIP_Real)newub, cons, inferInfoToInt(inferinfo), TRUE, &infeasible, &tightened) );
4179 SCIPdebugMessage("variable <%s>: new upper bound <%d> -> <%d>\n", SCIPvarGetName(var), lst, newub);
4182 /* for the statistic we count the number of times a upper bound was tightened due the the time-table algorithm */
4187 * @note We are taking the upper of the start time variable on purpose instead of newub. This is due the fact that
4188 * the proposed upper bound might be even strength by be the core which can be the case if aggregations are
4206 /** compute for the different earliest start and latest completion time the core energy of the corresponding time
4216 int* coreEnergyAfterEst, /**< array to store the core energy after the earliest start time of each job */
4217 int* coreEnergyAfterLct /**< array to store the core energy after the latest completion time of each job */
4236 energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1));
4245 coreEnergyAfterEst[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - ests[v]);
4261 energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1));
4270 coreEnergyAfterLct[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - lcts[v]);
4369 int* inferinfos, /**< pointer to store the inference information which is need for the (best) lower bound change */
4371 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4384 /* if the job can be processed completely before or after the time window, nothing can be tightened */
4388 /* if flexible part runs completely within the time window (assuming it is scheduled on its earliest start time), we
4394 /* check if the available energy in the time window is to small to handle the flexible part if it is schedule on its
4400 /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is
4403 * @note the variable ect define the earliest completion time of the flexible part of the job; hence we need to
4408 /* compute a latest start time (upper bound) such that the job consums at most the available energy
4414 /* check if we detected an infeasibility which is the case if the new lower bound is larger than the current upper
4437 begin, end, var, SCIP_BOUNDTYPE_LOWER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) );
4482 int* inferinfos, /**< pointer to store the inference information which is need for the (best) upper bound change */
4484 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4498 /* if flexible part of the job can be processed completely before or after the time window, nothing can be tightened */
4502 /* if flexible part runs completely within the time window (assuming it is scheduled on its latest start time), we
4508 /* check if the available energy in the time window is to small to handle the flexible part of the job */
4512 /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is
4515 * @note the variable lst define the latest start time of the flexible part of the job; hence we need to compute the
4521 /* compute a latest start time (upper bound) such that the job consums at most the available energy
4528 /* check if we detected an infeasibility which is the case if the new upper bound is smaller than the current lower
4551 begin, end, var, SCIP_BOUNDTYPE_UPPER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) );
4574 /** propagate the upper bounds and "opportunistically" the lower bounds using the time-table edge-finding algorithm */
4588 int* lbinferinfos, /**< array to store the inference information for the lower bound changes */
4589 int* ubinferinfos, /**< array to store the inference information for the upper bound changes */
4590 int* lsts, /**< array of latest start time of the flexible part in the same order as the variables */
4592 int* perm, /**< permutation of the variables w.r.t. the non-decreasing order of the earliest start times */
4598 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4637 /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */
4643 /* loop over all variable in non-increasing order w.r.t. the latest completion time; thereby, the latest completion
4656 /* if the latest completion time is larger then hmax an infeasibility cannot be detected, since after hmax an
4669 /* if the latest completion time equals to previous end time, we can continue since this particular interval
4677 /* In case we only want to detect an overload (meaning no bound propagation) we can skip the interval; this is
4678 * the case if the free energy (the energy which is not occupied by any core) is smaller than the previous minimum
4693 SCIPdebugMessage("skip latest completion time <%d> (minimum available energy <%d>, free energy <%d>)\n", lct, minavailable, freeenergy);
4709 /* loop over the job in non-increasing order w.r.t. the earliest start time; these earliest start time are
4710 * defining the beginning of the time interval under investigation; Thereby, the time interval gets wider and
4731 /* if the job starts after the current end, we can skip it and do not need to consider it again since the
4740 /* check if the interval has a size such that the total energy fits, if so we can skip all intervals with the
4760 /* in case the earliest start time is equal to minbegin, the job lies completely within the time window under
4769 SCIP_CALL( tightenUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
4770 var, duration, demand, est, lst, lct, minbegin, end, minavailable, &(newubs[idx]), &(ubinferinfos[idx]),
4777 SCIPdebugMessage("check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, lst of free part <%d>\n",
4778 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, lst);
4783 /* if the earliest start time is smaller than hmin we can stop here since the next job will not decrease the
4803 /* compute the flexible energy which is part of the time interval for sure if the job is scheduled
4815 /* compute the flexible energy of the job which is not part of flexible energy of the time interval */
4831 freeenergy = capacity * (end - begin) - flexenergy - coreEnergyAfterEst[i] + coreEnergyAfterEnd;
4836 SCIPdebugMessage("analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
4853 /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */
4854 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
4859 /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */
4870 energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, end - lsts[lbcand])) * demands[lbcand];
4925 /** propagate the lower bounds and "opportunistically" the upper bounds using the time-table edge-finding algorithm */
4939 int* lbinferinfos, /**< array to store the inference information for the lower bound changes */
4940 int* ubinferinfos, /**< array to store the inference information for the upper bound changes */
4941 int* ects, /**< array of earliest completion time of the flexible part in the same order as the variables */
4943 int* perm, /**< permutation of the variables w.r.t. the non-decreasing order of the latest completion times */
4949 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4992 /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */
4998 /* loop over all variable in non-decreasing order w.r.t. the earliest start times; thereby, the earliest start times
5012 /* if the earliest start time is smaller then hmin an infeasibility cannot be detected, since before hmin an
5022 /* if the latest earliest start time equals to previous start time, we can continue since this particular interval
5041 /* loop over the job in non-decreasing order w.r.t. the latest completion time; these latest completion times are
5042 * defining the ending of the time interval under investigation; thereby, the time interval gets wider and wider
5062 /* if the job has a latest completion time before the the current start, we can skip it and do not need to
5063 * consider it again since the earliest start times (which define the start) are scant in non-decreasing order
5071 /* check if the interval has a size such that the total energy fits, if so we can skip all intervals which
5091 /* in case the latest completion time is equal to minend, the job lies completely within the time window under
5100 SCIP_CALL( tightenLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5101 var, duration, demand, est, ect, lct, begin, minend, minavailable, &(newlbs[idx]), &(lbinferinfos[idx]),
5108 SCIPdebugMessage("check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, ect of free part <%d>\n",
5109 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, ect);
5114 /* if the latest completion time is larger than hmax we can stop here since the next job will not decrease the
5134 /* compute the flexible energy which is part of the time interval for sure if the job is scheduled
5146 /* compute the flexible energy of the job which is not part of flexible energy of the time interval */
5162 freeenergy = capacity * (end - begin) - flexenergy - coreEnergyAfterStart + coreEnergyAfterLct[i];
5167 SCIPdebugMessage("analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
5184 /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */
5185 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
5190 /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */
5204 energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, ects[ubcand] - begin)) * demands[ubcand];
5258 /** checks whether the instance is infeasible due to a overload within a certain time frame using the idea of time-table
5262 * - Petr Vilim, "Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources", In: Tobias
5263 * Achterberg and J. Christopher Beck (Eds.), Integration of AI and OR Techniques in Constraint Programming for
5265 * - Andreas Schutt, Thibaut Feydy, and Peter J. Stuckey, "Explaining Time-Table-Edge-Finding Propagation for the
5283 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
5329 /* we need to buffer the bound changes since the propagation algorithm cannot handle new bound dynamically */
5339 collectDataTTEF(scip, nvars, vars, durations, demands, hmin, hmax, permests, ests, permlcts, lcts, ects, lsts, flexenergies);
5345 /* compute for the different earliest start and latest completion time the core energy of the corresponding time
5348 SCIP_CALL( computeCoreEngeryAfter(scip, profile, nvars, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct) );
5351 SCIP_CALL( propagateUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5353 permests, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );
5356 SCIP_CALL( propagateLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5358 permlcts, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );
5366 SCIP_CALL( SCIPinferVarLbCons(scip, vars[v], (SCIP_Real)newlbs[v], cons, lbinferinfos[v], TRUE, &infeasible, &tightened) );
5380 SCIP_CALL( SCIPinferVarUbCons(scip, vars[v], (SCIP_Real)newubs[v], cons, ubinferinfos[v], TRUE, &infeasible, &tightened) );
5382 /* since upper bound was compute w.r.t. the "old" bound the previous lower bound update together with this upper
5420 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
5454 /** a cumulative condition is not satisfied if its capacity is exceeded at a time where jobs cannot be shifted (core)
5455 * anymore we build up a cumulative profile of all cores of jobs and try to improve bounds of all jobs; also known as
5473 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
5529 /* check if the job runs completely outside of the effective horizon [hmin, hmax); if so skip it */
5544 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, begin, end);
5550 SCIP_CALL( coretimesUpdateLb(scip, nvars, vars, durations, demands, capacity, hmin, hmax, cons,
5584 SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
5585 var, duration, demand, SCIPprofileGetTime(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) );
5593 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutofftimetable++ );
5607 SCIP_VAR* var; /**< start time variable of the job if the node data belongs to a leaf, otherwise NULL */
5701 nodedata->enveloptheta = MAX(leftdata->enveloptheta + rightdata->energytheta, rightdata->enveloptheta);
5713 nodedata->enveloplambda = MAX(leftdata->enveloplambda + rightdata->energytheta, rightdata->enveloplambda);
5719 nodedata->enveloplambda = MAX(nodedata->enveloplambda, leftdata->enveloptheta + rightdata->energylambda);
5727 nodedata->energylambda = MAX(leftdata->energylambda + rightdata->energytheta, leftdata->energytheta + rightdata->energylambda);
6036 if( leftdata->energylambda >= 0 && nodedata->energylambda == leftdata->energylambda + rightdata->energytheta )
6086 if( leftdata->enveloplambda >= 0 && nodedata->enveloplambda == leftdata->enveloplambda + rightdata->energytheta )
6123 SCIPdebugMessage("add variable <%s> as elements %d to omegaset\n", SCIPvarGetName(nodedata->var), *nelements);
6128 (*energy) += (nodedata->duration - nodedata->leftadjust - nodedata->rightadjust) * nodedata->demand;
6181 if( leftdata->enveloptheta >= 0 && nodedata->enveloptheta == leftdata->enveloptheta + rightdata->energytheta )
6236 if( leftdata->energylambda >= 0 && nodedata->energylambda == leftdata->energylambda + rightdata->energytheta )
6296 if( leftdata->enveloplambda >= 0 && nodedata->enveloplambda == leftdata->enveloplambda + rightdata->energytheta )
6335 SCIPvarGetName(nodedata->var), SCIPvarGetLbLocal(nodedata->var), SCIPvarGetUbLocal(nodedata->var),
6336 SCIPvarGetLbGlobal(nodedata->var), SCIPvarGetUbGlobal(nodedata->var), duration, nodedata->demand);
6371 * @note the conflict analysis is not performend, only the initialized SCIP_Bool pointer is set to TRUE
6382 SCIP_Bool propest, /**< should the earliest start times be propagated, otherwise the latest completion times */
6386 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
6396 SCIPdebugMessage("est=%d, lct=%d, propest %u, reportedenergy %d, shift %d\n", est, lct, propest, reportedenergy, shift);
6404 /* collect the energy of the responsible leaves until the cumulative energy is large enough to detect an overload;
6425 SCIPdebugMessage("time window [%d,%d) available energy %d, required energy %d\n", est, lct, energy, reportedenergy);
6448 /* report the variables and relax their bounds to final time interval [est,lct) which was been detected to be
6462 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, nodedata->var, NULL, (SCIP_Real)(est - nodedata->leftadjust)) );
6463 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, nodedata->var, NULL, (SCIP_Real)(lct - nodedata->duration + nodedata->rightadjust)) );
6480 /** computes a new latest starting time of the job in 'respleaf' due to the energy consumption and stores the
6504 newest = (int)SCIPfeasCeil(scip, (energy - (SCIP_Real)(capacity - demand) * (lct - est)) / (SCIP_Real)demand);
6512 /** propagates start time using an edge finding algorithm which is based on binary trees (theta lambda trees)
6514 * @note The algorithm is based on the paper: Petr Vilim, "Edge Finding Filtering Algorithm for Discrete Cumulative
6526 SCIP_Bool propest, /**< should the earliest start times be propagated, otherwise the latest completion times */
6529 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
6542 /* iterate over all added candidate (leaves) in non-increasing order w.r.t. their latest completion time */
6603 newest = computeEstOmegaset(scip, leafdata->duration, leafdata->demand, capacity, est, lct, energy);
6605 /* if the computed earliest start time is greater than the latest completion time of the omega set we detected an overload */
6611 SCIP_CALL( analyzeConflictOverload(scip, omegaset, capacity, nelements, est, lct, 0, propest, shift,
6616 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffedgefinder++ );
6626 /* constuct inference information; store used propagation rule and the the time window of the omega set */
6635 /* for the statistic we count the number of times a lower bound was tightened due the edge-finder */
6640 /* constuct inference information; store used propagation rule and the the time window of the omega set */
6644 SCIPvarGetName(leafdata->var), SCIPvarGetUbLocal(leafdata->var), shift - newest - leafdata->duration);
6646 SCIP_CALL( SCIPinferVarUbCons(scip, leafdata->var, (SCIP_Real)(shift - newest - leafdata->duration),
6649 /* for the statistic we count the number of times a upper bound was tightened due the edge-finder */
6697 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffedgefinder++ );
6719 /** checks whether the instance is infeasible due to a overload within a certain time frame using the idea of theta trees
6721 * @note The algorithm is based on the paper: Petr Vilim, "Max Energy Filtering Algorithm for Discrete Cumulative
6722 * Resources". In: Willem Jan van Hoeve and John N. Hooker (Eds.), Integration of AI and OR Techniques in
6723 * Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2009), LNCS 5547, pp 294--308
6737 SCIP_Bool propest, /**< should the earliest start times be propagated, otherwise the latest completion times */
6739 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
6762 SCIPdebugMessage("check overload of cumulative condition of constraint <%s> (capacity %d)\n", SCIPconsGetName(cons), capacity);
6779 /* compute the latest completion time of all jobs which define the shift we apply to run the algorithm for the
6791 /* collect earliest and latest completion times and ignore jobs which do not run completion within the effective
6817 /* adjust the duration, earliest start time, and latest completion time of jobs which do not lie completely in the
6833 /* only consider jobs which have a (adjusted) duration greater than zero (the amound which will run defenetly
6870 /* adjust earliest start time to make it unique in case several jobs have the same earliest start time */
6880 /* the envelop is the energy of the job plus the total amount of energy which is available in the time period
6881 * before that job can start, that is [0,est). The envelop is later used to compare the energy consumption of a
6903 /* iterate over all jobs in non-decreasing order of their latest completion times and add them to the theta set until
6911 /* check if the new job opens a time window which size is so large that it offers more energy than the total
6939 SCIPdebugMessage("detects cutoff due to overload in time window [?,%d) (ncands %d)\n", nodedatas[j]->lct, j);
6943 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverload++ );
6949 /* in case an overload was detected and the conflict analysis is applicable, create an initialize explanation */
6960 /* scan the remaining candidates for a global contributions within the time window of the last inserted candidate
6996 SCIP_CALL( analyzeConflictOverload(scip, leaves, capacity, ninsertcands, est, lct, glbenery, propest, shift,
7002 SCIP_CALL( inferboundsEdgeFinding(scip, conshdlrdata, cons, tree, leaves, capacity, ninsertcands,
7022 /** checks whether the instance is infeasible due to a overload within a certain time frame using the idea of theta trees
7024 * @note The algorithm is based on the paper: Petr Vilim, "Max Energy Filtering Algorithm for Discrete Cumulative
7025 * Resources". In: Willem Jan van Hoeve and John N. Hooker (Eds.), Integration of AI and OR Techniques in
7026 * Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2009), LNCS 5547, pp 294--308
7041 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
7055 SCIP_CALL( checkOverloadViaThetaTree(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
7067 SCIP_CALL( checkOverloadViaThetaTree(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
7073 /** checks if the constraint is redundant; that is the case if its capacity can never be exceeded; therefore we check
7074 * with respect to the lower and upper bounds of the integer start time variables the maximum capacity usage for all
7094 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
7095 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
7148 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
7197 /** creates the worst case resource profile, that is, all jobs are inserted with the earliest start and latest
7206 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
7213 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
7247 /* check if the job runs completely outside of the effective horizon [hmin, hmax); if so skip it */
7272 SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
7273 var, duration, demand, SCIPprofileGetTime(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) );
7281 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutofftimetable++ );
7306 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
7320 SCIP_CALL( consCheckRedundancy(scip, nvars, vars, durations, demands, capacity, hmin, hmax, redundant) );
7329 SCIP_CALL( createCoreProfile(scip, conshdlrdata, profile, nvars, vars, durations, demands, capacity, hmin, hmax,
7333 SCIP_CALL( propagateTimetable(scip, conshdlrdata, profile, nvars, vars, durations, demands, capacity, hmin, hmax, cons,
7337 SCIP_CALL( propagateEdgeFinding(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
7341 SCIP_CALL( propagateTTEF(scip, conshdlrdata, profile, nvars, vars, durations, demands, capacity, hmin, hmax, cons,
7427 /** it is dual feasible to remove the values {leftub+1, ..., rightlb-1} since SCIP current does not feature domain holes
7428 * we use the probing mode to check if one of the two branches is infeasible. If this is the case the dual redundant can
7439 SCIP_Real* leftimpllbs, /**< lower bounds after applying implications and cliques in left branch, or NULL */
7440 SCIP_Real* leftimplubs, /**< upper bounds after applying implications and cliques in left branch, or NULL */
7443 SCIP_Real* rightimpllbs, /**< lower bounds after applying implications and cliques in right branch, or NULL */
7444 SCIP_Real* rightimplubs, /**< upper bounds after applying implications and cliques in right branch, or NULL */
7445 SCIP_Real* rightproplbs, /**< lower bounds after applying domain propagation in right branch */
7446 SCIP_Real* rightpropubs, /**< upper bounds after applying domain propagation in right branch */
7447 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */
7473 SCIP_CALL( SCIPapplyProbingVar(scip, vars, nvars, probingpos, SCIP_BOUNDTYPE_UPPER, leftub, -1,
7490 /* note that probing can change the upper bound and thus the right branch may have been detected infeasible if
7508 SCIP_CALL( SCIPapplyProbingVar(scip, vars, nvars, probingpos, SCIP_BOUNDTYPE_LOWER, rightlb, -1,
7547 /* in case the variable is not active we need to check the object coefficient of the active variable */
7566 /* rounding the integer variable down is only a valid dual reduction if the object coefficient is zero or positive
7571 if( (scalar > 0 && SCIPisNegative(scip, objval)) || (scalar < 0 && SCIPisPositive(scip, objval)) )
7596 /* in case the variable is not active we need to check the object coefficient of the active variable */
7615 /* rounding the integer variable up is only a valid dual reduction if the object coefficient is zero or negative
7620 if( (scalar > 0 && SCIPisPositive(scip, objval)) || (scalar < 0 && SCIPisNegative(scip, objval)) )
7626 /** For each variable we compute an alternative lower and upper bounds. That is, if the variable is not fixed to its
7627 * lower or upper bound the next reasonable lower or upper bound would be this alternative bound (implying that certain
7628 * values are not of interest). An alternative bound for a particular is only valied if the cumulative constarints are
7675 SCIP_CALL( SCIPcreateWorstCaseProfile(scip, profile, consdata->nvars, consdata->vars, consdata->durations, consdata->demands) );
7703 /* multi-aggregated variables should appear here since we mark the variables to be not mutlt-aggregated */
7771 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */
7829 /* for the statistic we count the number of jobs which are dual fixed due the information of all cumulative
7832 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nallconsdualfixs++ );
7838 /* In the current version SCIP, variable domains are single intervals. Meaning that domain holes or not
7839 * representable. To retrieve a potential dual reduction we using probing to check both branches. If one in
7842 SCIP_CALL( applyProbingVar(scip, vars, nvars, v, (SCIP_Real) lb, (SCIP_Real) alternativelbs[v],
7843 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
7848 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nallconsdualfixs++ );
7876 /* for the statistic we count the number of jobs which are dual fixed due the information of all cumulative
7879 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nallconsdualfixs++ );
7885 /* In the current version SCIP, variable domains are single intervals. Meaning that domain holes or not
7886 * representable. To retrieve a potential dual reduction we using probing to check both branches. If one in
7889 SCIP_CALL( applyProbingVar(scip, vars, nvars, v, (SCIP_Real) alternativeubs[v], (SCIP_Real) ub,
7890 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
7895 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nallconsdualfixs++ );
7923 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */
7925 SCIP_Bool* branched /**< pointer to store if a branching was applied, or NULL to avoid branching */
7959 SCIP_CALL( computeAlternativeBounds(scip, conss, nconss, local, alternativelbs, alternativeubs, downlocks, uplocks) );
7962 SCIP_CALL( applyAlternativeBoundsFixing(scip, vars, nvars, alternativelbs, alternativeubs, downlocks, uplocks,
7967 SCIP_CALL( applyAlternativeBoundsBranching(scip, vars, nvars, alternativelbs, alternativeubs, downlocks, uplocks, branched) );
7992 int* startvalues, /**< upper bounds on finishing time per job for activities from 0,..., nactivities -1 */
8083 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), rowname, -SCIPinfinity(scip), (SCIP_Real)bigcoversize,
8140 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->bcoverrows, consdata->nbcoverrows, consdata->bcoverrowssize) );
8171 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), rowname, -SCIPinfinity(scip), (SCIP_Real)smallcoversize,
8228 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->scoverrows, consdata->nscoverrows, consdata->scoverrowssize) );
8255 int* startindices; /* we sort the startvalues, so we need to know wich index of a job it corresponds to */
8256 int* endindices; /* we sort the endvalues, so we need to know wich index of a job it corresponds to */
8296 endvalues[j] = convertBoundToInt(scip, SCIPvarGetUbLocal(consdata->vars[j])) + consdata->durations[j];
8349 /* we can create covering constraints for each pint in time in interval [curtime; nextprofilechange[ */
8382 /** this method creates a row for time point curtime which insures the capacity restriction of the cumulative
8414 SCIP_CALL( collectBinaryVars(scip, consdata, &binvars, &coefs, &nbinvars, startindices, curtime, nstarted, nfinished) );
8417 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d[%d]", SCIPconsGetName(cons), nstarted-1, curtime);
8424 SCIP_CALL( SCIPcreateConsKnapsack(scip, &lincons, name, 0, NULL, NULL, (SCIP_Longint)(capacity),
8440 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)capacity, FALSE, FALSE, SCIPconsIsRemovable(cons)) );
8459 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->demandrows, consdata->ndemandrows, consdata->demandrowssize) );
8472 /** this method checks how many cumulatives can run at most at one time if this is greater than the capacity it creates
8486 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
8487 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
8540 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars);
8557 /* step forward until next job is released and see whether capacity constraint is met or not */
8566 SCIP_CALL( createCapacityRestriction(scip, cons, startindices, curtime, j+1, endindex, cutsasconss) );
8568 /* create for all points in time between the current event point and next start event point a row if the free
8581 SCIP_CALL( createCapacityRestriction(scip, cons, startindices, t, j+1, endindex, cutsasconss) );
8598 /** creates LP rows corresponding to cumulative constraint; therefore, check each point in time if the maximal needed
8675 assert( ! infeasible ); /* this function is only called by initlp -> the cut should be feasible */
8744 SCIPdebugMessage("cumulative constraint <%s> separated %d cuts\n", SCIPconsGetName(cons), ncuts);
8870 /** this method creates a row for time point @p curtime which ensures the capacity restriction of the cumulative constraint */
8902 SCIP_CALL( collectIntVars(scip, consdata, &activevars, startindices, curtime, nstarted, nfinished, lower, &lhs ) );
8908 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, (SCIP_Real) lhs, SCIPinfinity(scip),
8914 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real) lhs,
8954 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
8955 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
8989 createSelectedSortedEventpointsSol(scip, consdata, sol, starttimes, endtimes, startindices, endindices, &nvars, lower);
9007 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars);
9022 SCIP_CALL( createCapacityRestrictionIntvars(scip, cons, sol, startindices, curtime, j+1, endindex, lower) );
9045 /** returns TRUE if all demands are smaller than the capacity of the cumulative constraint and if the total demand is
9067 /* if no activities are associated with this cumulative then this constraint is not infeasible, return */
9128 /** remove jobs which have a duration or demand of zero (zero energy) or lay outside the efficient horizon [hmin, hmax);
9187 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nirrelevantjobs++ );
9221 /* jobs with a demand greater than the the capacity have to moved outside the time interval [hmin,hmax) */
9229 /* the jobs has to have an overlap with the efficient horizon otherwise it would be already removed */
9235 /* the job will at least run partly in the time interval [hmin,hmax) this means the problem is infeasible */
9241 SCIP_CALL( SCIPtightenVarUb(scip, var, (SCIP_Real)(consdata->hmin - duration), TRUE, cutoff, &tightened) );
9249 SCIP_CALL( SCIPtightenVarLb(scip, var, (SCIP_Real)(consdata->hmax), TRUE, cutoff, &tightened) );
9256 /* this job can run before or after the time interval [hmin,hmax) thus we create a bound disjunction
9286 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, name, 2, vartuple, boundtypetuple, boundtuple,
9336 SCIPdebugMessage("cumulative constraint <%s> has %d jobs left, cutoff %u\n", SCIPconsGetName(cons), consdata->nvars, *cutoff);
9341 /** fix integer variable to upper bound if the rounding locks and the object coefficient are in favor of that */
9354 /* if SCIP is in probing mode or repropagation we cannot perform this dual reductions since this dual reduction
9360 /* rounding the variable to the upper bound is only a feasible dual reduction if the cumulative constraint
9372 /* rounding the integer variable up is only a valid dual reduction if the object coefficient is zero or negative
9386 SCIPdebugMessage("fix variable <%s> to upper bound %g\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var));
9393 /** fix integer variable to lower bound if the rounding locks and the object coefficient are in favor of that */
9406 /* if SCIP is in probing mode or repropagation we cannot perform this dual reductions since this dual reduction
9412 /* rounding the variable to the lower bound is only a feasible dual reduction if the cumulative constraint
9433 SCIPdebugMessage("fix variable <%s> to lower bound %g\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var));
9486 SCIPdebugMessage("update cumulative condition (%d + %d > %d) to unary cumulative condition\n", mindemand1, mindemand2, *capacity);
9512 /** divides demands by their greatest common divisor and divides capacity by the same value, rounding down the result;
9513 * in case the the smallest demands add up to more than the capacity we reductions all demands to one as well as the
9539 /**@todo sort items w.r.t. the demands, because we can stop earlier if the smaller weights are evaluated first */
9541 SCIP_CALL( normalizeCumulativeCondition(scip, consdata->nvars, consdata->vars, consdata->durations,
9557 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
9592 /* If SCIP is repropagating the root node, it is not possible to decompose the constraints. This is the case since
9593 * the conflict analysis stores the constraint pointer for bound changes made by this constraint. These pointer
9594 * are used during the resolve propagation phase to explain bound changes. If we would decompose certain jobs into
9595 * a new cumulative constraint, the "old" pointer is not valid. More precise, the "old" constraint is not able to
9604 /* check if there exist a time point within the effective horizon [hmin,hmax) such that the capacity is not exceed w.r.t. worst case profile */
9615 /* check if the current time point does not exceed the capacity w.r.t. worst case resource profile; if so we
9638 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
9662 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
9664 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
9672 SCIP_CALL( SCIPcreateConsCumulative(scip, &cons, name, nvars, vars, durations, demands, capacity,
9673 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
9713 SCIPdebugMessage("cumulative constraint <%s> adjust hmin <%d> -> <%d>\n", SCIPconsGetName(cons), consdata->hmin, hmin);
9722 SCIPdebugMessage("cumulative constraint <%s> adjust hmax <%d> -> <%d>\n", SCIPconsGetName(cons), consdata->hmax, hmax);
9749 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
9750 SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
9766 /** presolve cumulative condition w.r.t. the earlier start times (est) and the hmin of the effective horizon
9768 * (1) If the latest completion time (lct) of a job is smaller or equal than hmin, the corresponding job can be removed
9769 * form the constraint. This is the case since it cannot effect any assignment within the effective horizon
9771 * (2) If the latest start time (lst) of a job is smaller or equal than hmin it follows that the this jobs can run
9772 * before the effective horizon or it overlaps with the effective horizon such that hmin in included. Hence, the
9775 * (3) If the earlier completion time (ect) of a job is smaller or equal than hmin, the cumulative is the only one
9776 * locking the corresponding variable down, and the objective coefficient of the start time variable is not
9779 * (4) If the earlier start time (est) of job is smaller than the hmin, the cumulative is the only one locking the
9780 * corresponding variable down, and the objective coefficient of the start time variable is not negative, than
9783 * (5) If the earlier start time (est) of job is smaller than the smallest earlier completion times of all other jobs
9784 * (lets denote this with minect), the cumulative is the only one locking the corresponding variable down, and the
9785 * objective coefficient of the start time variable is not negative, than removing the values {est+1,...,minect-1}
9788 * @note That method does not remove any variable form the arrays. It only marks the variables which are irrelevant for
9802 SCIP_Bool* irrelevants, /**< array mark those variables which are irrelevant for the cumulative condition */
9835 SCIPdebugMessage("check for irrelevant variable for cumulative condition (hmin %d) w.r.t. earlier start time\n", hmin);
9875 /* collect earlier start time (est), earlier completion time (ect), latest start time (lst), and latest completion
9895 /* (1) check if the job runs completely before the effective horizon; if so the job can be removed form the
9905 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nirrelevantjobs++ );
9909 /* (2) check if the jobs overlaps with the time point hmin if it overlaps at all with the effective horizon; if
9922 * We mark the job to be deletable. The removement together with the capacity reducion is done later
9931 /* for the statistic we count the number of jobs which always run during the effective horizon */
9950 /* (3) check if the job can finish before the effective horizon starts; if so and the job can be fixed to its
9951 * earliest start time (which implies that it finishes before the effective horizon starts), the job can be
9955 /* job can be removed from the constraint only if the integer start time variable can be fixed to its lower
9966 SCIPdebugMessage(" variable <%s>[%d,%d] with duration <%d> is irrelevant due to dual fixing wrt EST\n",
9969 /* after fixing the start time variable to its lower bound, the (new) earliest completion time should be smaller or equal ti hmin */
9985 /* check if the cumulative constraint is the only one looking this variable down and if the objective function
10007 /* for the statistic we count the number of jobs which are dual fixed due the information of all cumulative
10016 /* In the current version SCIP, variable domains are single intervals. Meaning that domain holes or not
10017 * representable. To retrieve a potential dual reduction we using probing to check both branches. If one in
10021 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
10050 /** presolve cumulative condition w.r.t. the latest completion times (lct) and the hmax of the effective horizon
10052 * (1) If the earliest start time (est) of a job is larger or equal than hmax, the corresponding job can be removed
10053 * form the constraint. This is the case since it cannot effect any assignment within the effective horizon
10055 * (2) If the earliest completion time (ect) of a job is larger or equal than hmax it follows that the this jobs can run
10056 * before the effective horizon or it overlaps with the effective horizon such that hmax in included. Hence, the
10059 * (3) If the latest start time (lst) of a job is larger or equal than hmax, the cumulative is the only one
10060 * locking the corresponding variable up, and the objective coefficient of the start time variable is not
10063 * (4) If the latest completion time (lct) of job is larger than the hmax, the cumulative is the only one locking the
10064 * corresponding variable up, and the objective coefficient of the start time variable is not positive, than
10065 * removing the values {hmax - p_j, ..., lst-1} form variable domain is dual feasible (p_j is the processing time
10068 * (5) If the latest completion time (lct) of job is smaller than the largerst latest start time of all other jobs
10069 * (lets denote this with maxlst), the cumulative is the only one locking the corresponding variable up, and the
10070 * objective coefficient of the start time variable is not positive, than removing the values {maxlst - p_j + 1,
10071 * ..., lst-1} form variable domain is dual feasible (p_j is the processing time of the corresponding job).
10073 * @note That method does not remove any variable form the arrays. It only marks the variables which are irrelevant for
10087 SCIP_Bool* irrelevants, /**< array mark those variables which are irrelevant for the cumulative condition */
10088 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */
10120 SCIPdebugMessage("check for irrelevant variable for cumulative condition (hmax %d) w.r.t. latest completion time\n", hmax);
10159 /* collect earlier start time (est), earlier completion time (ect), latest start time (lst), and latest completion
10178 /* (1) check if the job runs completely after the effective horizon; if so the job can be removed form the
10188 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nirrelevantjobs++ );
10195 /* (2) check if the jobs overlaps with the time point hmax if it overlaps at all with the effective horizon; if
10205 SCIPdebugMessage(" variables <%s>[%d,%d] with duration <%d> is irrelevant due to no down lock\n",
10211 /* for the statistic we count the number of jobs which always run during the effective horizon */
10230 /* (3) check if the job can start after the effective horizon finishes; if so and the job can be fixed to its
10231 * latest start time (which implies that it starts after the effective horizon finishes), the job can be
10235 /* job can be removed from the constraint only if the integer start time variable can be fixed to its upper
10246 SCIPdebugMessage(" variable <%s>[%d,%d] with duration <%d> is irrelevant due to dual fixing wrt LCT\n",
10249 /* after fixing the start time variable to its upper bound, the (new) latest start time should be greather or equal ti hmax */
10265 /* check if the cumulative constraint is the only one looking this variable down and if the objective function
10287 /* for the statistic we count the number of jobs which are dual fixed due the information of all cumulative
10296 /* In the current version SCIP, variable domains are single intervals. Meaning that domain holes or not
10297 * representable. To retrieve a potential dual reduction we using probing to check both branches. If one
10301 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
10368 /* remove variables from the cumulative constraint which are marked to be deleted; we need to that in the reverse
10408 /** stores all demands which are smaller than the capacity of those jobs that are running at 'curtime' */
10448 /* check the end time of this job is larger than the curtime; in this case the job is still running */
10465 /** this method creates a row for time point curtime which insures the capacity restriction of the cumulative
10498 SCIP_CALL( collectDemands(scip, consdata, startindices, curtime, nstarted, nfinished, &demands, &ndemands) );
10510 SCIP_CALL( SCIPsolveKnapsackExactly(scip, ndemands, demands, profits, (SCIP_Longint)consdata->capacity,
10540 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
10541 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
10561 /* if no activities are associated with this cumulative or the capacity is 1, then this constraint is redundant */
10590 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars);
10593 addEndingJobDemands(consdata, curtime, endtimes, endindices, &freecapacity, &endindex, nvars);
10609 SCIP_CALL( getHighestCapacityUsage(scip, cons, startindices, curtime, j+1, endindex, &newcapacity) );
10616 /* also those points in time, where the capacity limit is not exceeded, must be taken into account */
10623 /* capacity cannot be decreased if the demand sum over more than one job equals the capacity */
10713 if( mindemand + consdata->demands[j] > consdata->capacity && consdata->demands[j] < consdata->capacity )
10715 SCIPdebugMessage("+-+-+-+-+-+change demand of var<%s> from %d to capacity %d\n", SCIPvarGetName(consdata->vars[j]),
10741 lct_j = convertBoundToInt(scip, SCIPvarGetUbLocal(consdata->vars[j])) + consdata->durations[j];
10752 lct_i = convertBoundToInt(scip, SCIPvarGetUbLocal(consdata->vars[i])) + consdata->durations[i];
10766 SCIPdebugMessage("+-+-+-+-+-+change demand of var<%s> from %d to capacity %d\n", SCIPvarGetName(consdata->vars[j]),
10776 SCIPdebugMessage("+-+-+-+-+-+changed %d coefficients of variables of cumulative constraint<%s>\n",
10848 SCIP_CALL( SCIPcreateVar(scip, &aggrvar, name, (SCIP_Real)(est+shift), (SCIP_Real)lst, 0.0, SCIPvarGetType(var),
10851 SCIP_CALL( SCIPaggregateVars(scip, var, aggrvar, 1.0, -1.0, (SCIP_Real)shift, &infeasible, &redundant, &aggregated) );
10862 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, consdata->downlocks[v], consdata->uplocks[v]) );
10925 /* add all jobs which has a demand smaller than one half of the capacity but together with the smallest collected
10946 SCIP_CALL( createConsCumulative(scip, SCIPconsGetName(cons), nvars, vars, durations, demands, 1, consdata->hmin, consdata->hmax,
10966 int* naggrvars, /**< pointer to counter which is increased by the number of deduced variable aggregations */
10988 /* in case the cumulative constraint is independent of every else, solve the cumulative problem and apply the
10991 SCIP_CALL( solveIndependentCons(scip, cons, conshdlrdata->maxnodes, nchgbds, nfixedvars, ndelconss, cutoff, unbounded) );
10996 SCIP_CALL( presolveConsEffectiveHorizon(scip, cons, nfixedvars, nchgcoefs, nchgsides, cutoff) );
11086 if( tcliquegraph->precedencematrix[node1][node2] || tcliquegraph->precedencematrix[node2][node1] )
11114 /* check if the node is adjacent to the given node (nodes and adjacent nodes are ordered by node index) */
11157 SCIPinfoMessage(scip, NULL, "(%d/%d) ", tcliquegraph->precedencematrix[i][j], tcliquegraph->demandmatrix[i][j]);
11166 /** analyzes if the given variable lower bound condition implies a precedence condition w.r.t. given duration for the
11200 /* if vlbcoef < 1 and ub(vlbvar) <= (duration - vlbconst)/(vlbcoef - 1) -> precedence condition */
11212 /* if vlbcoef > 1 and lb(vlbvar) >= (duration - vlbconst)/(vlbcoef - 1) -> precedence condition */
11221 /** analyzes if the given variable upper bound condition implies a precedence condition w.r.t. given duration for the
11245 /** get the corresponding index of the given variables; this in case of an active variable the problem index and for
11287 SCIP_CALL( SCIPreallocBufferArray(scip, &tcliquegraph->precedencematrix[v], size) ); /*lint !e866*/
11288 SCIP_CALL( SCIPreallocBufferArray(scip, &tcliquegraph->demandmatrix[v], size) ); /*lint !e866*/
11299 SCIP_CALL( SCIPallocBufferArray(scip, &tcliquegraph->precedencematrix[pos], tcliquegraph->size) ); /*lint !e866*/
11300 BMSclearMemoryArray(tcliquegraph->precedencematrix[pos], tcliquegraph->nnodes); /*lint !e866*/
11302 SCIP_CALL( SCIPallocBufferArray(scip, &tcliquegraph->demandmatrix[pos], tcliquegraph->size) ); /*lint !e866*/
11328 /** use the variables bounds of SCIP to projected variables bound graph into a precedence garph
11330 * Let d be the (assumed) duration of variable x and consider a variable bound of the form b * x + c <= y. This
11331 * variable bounds implies a precedence condition x -> y (meaning job y starts after job x is finished) if:
11386 if( impliesVlbPrecedenceCondition(scip, vbdvars[b], vbdcoefs[b], vbdconsts[b], tcliquegraph->durations[idx2]) )
11405 if( impliesVubPrecedenceCondition(scip, var, vbdcoefs[b], vbdconsts[b], tcliquegraph->durations[idx1]) )
11419 /* check if the latest completion time of job1 is smaller than the earliest start time of job2 */
11420 if( SCIPisLE(scip, SCIPvarGetUbLocal(var) + tcliquegraph->durations[idx1], SCIPvarGetLbLocal(vars[b])) )
11423 /* check if the latest completion time of job2 is smaller than the earliest start time of job1 */
11424 if( SCIPisLE(scip, SCIPvarGetUbLocal(vars[b]) + tcliquegraph->durations[idx2], SCIPvarGetLbLocal(var)) )
11464 /** constructs a non-overlapping graph w.r.t. given durations and available cumulative constraints */
11505 if( tcliquegraph->durations[idx1] == 0 || tcliquegraph->durations[idx1] > consdata->durations[i] )
11539 if( tcliquegraph->durations[idx2] == 0 || tcliquegraph->durations[idx2] > consdata->durations[j] )
11542 SCIPdebugMessage(" *** variable <%s> and variable <%s>\n", SCIPvarGetName(vars[i]), SCIPvarGetName(vars[j]));
11558 /** constructs a conflict set graph (undirected) which contains for each job a node and edge if the corresponding pair
11572 /* use the variables bounds of SCIP to project the variables bound graph inot a precedence graph */
11575 /* compute the transitive closure of the precedence graph and the number of in and out arcs */
11576 transitiveClosure(tcliquegraph->precedencematrix, tcliquegraph->ninarcs, tcliquegraph->noutarcs, tcliquegraph->nnodes);
11616 SCIP_CALL( SCIPcreateConsCumulative(scip, &cons, name, ncliquenodes, vars, durations, demands, 1,
11667 /* create a hash table to store all start time variables which are already covered by at least one clique */
11709 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,
11714 SCIPdebugMessage("tree nodes %d clique size %d (weight %d, status %d)\n", ntreenodes, ncliquenodes, cliqueweight, tcliquestatus);
11753 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->naddeddisjunctives += nconss );
11765 int distance /**< minimum distance between the start time of the job corresponding to var and the job corresponding to vbdvar */
11771 SCIP_CALL( SCIPcreateConsVarbound(scip, &cons, name, var, vbdvar, -1.0, -SCIPinfinity(scip), -(SCIP_Real)distance,
11783 /** compute a minimum distance between the start times of the two given jobs and post it as variable bound constraint */
11815 /* get latest completion time (lct) of the source and the earliest start time (est) of sink */
11816 lct = convertBoundToInt(scip, SCIPvarGetUbLocal(vars[source])) + tcliquegraph->durations[source];
11835 else if( tcliquegraph->precedencematrix[source][i] && tcliquegraph->precedencematrix[i][sink] )
11853 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,
11866 /* the minimum distance between the start times of source job and the sink job is the clique weight plus the
11882 * for each arc of the transitive closure of the precedence graph, we are computing a minimum distance between the
11944 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->naddedvarbounds += nconss );
11984 /**@todo For the test sets, which we are considere, the durations are independent of the cumulative
11985 * constaints. Meaning each job has a fixed duration which is the same for all cumulative constraints. In
11986 * general this is not the case. Therefore, the question would be which duration should be used?
12104 /** construct an incompatibility graph and search for precedence constraints (variables bounds) and unary cumulative
12145 /** compute the constraint signature which is used to detect constraints which contain potentially the same set of variables */
12163 consdata->signature |= ((unsigned int)1 << ((unsigned int)SCIPvarGetIndex(vars[v]) % (sizeof(unsigned int) * 8)));
12169 /** index comparison method of linear constraints: compares two indices of the variable set in the linear constraint */
12387 if( demands[i] + demands[j] > capacity && convertBoundToInt(scip, vbdconsts[b]) < durations[j] )
12393 SCIPdebugMessage("<%s>[%d] + %g <= <%s>[%d]\n", SCIPvarGetName(vbdvars[b]), durations[j], vbdconsts[b], SCIPvarGetName(var), durations[i]);
12401 SCIP_CALL( SCIPaddVarVlb(scip, var, vbdvars[b], 1.0, (SCIP_Real) durations[j], &infeasible, &nlocalbdchgs) );
12444 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
12460 SCIPstatisticPrintf("time-table: lb=%"SCIP_LONGINT_FORMAT", ub=%"SCIP_LONGINT_FORMAT", cutoff=%"SCIP_LONGINT_FORMAT"\n",
12462 SCIPstatisticPrintf("edge-finder: lb=%"SCIP_LONGINT_FORMAT", ub=%"SCIP_LONGINT_FORMAT", cutoff=%"SCIP_LONGINT_FORMAT"\n",
12464 SCIPstatisticPrintf("overload: time-table=%"SCIP_LONGINT_FORMAT" time-time edge-finding=%"SCIP_LONGINT_FORMAT"\n",
12477 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
12485 /* remove jobs which have a duration or demand of zero (zero energy) or lay outside the effective horizon [hmin,
12495 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
12517 SCIPstatisticPrintf("@11 added variables bounds constraints %d\n", conshdlrdata->naddedvarbounds);
12518 SCIPstatisticPrintf("@22 added disjunctive constraints %d\n", conshdlrdata->naddeddisjunctives);
12533 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
12565 /* if constraint belongs to transformed problem space, drop bound change events on variables */
12612 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
12613 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
12616 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
12808 SCIPdebugMessage("LP enforcing %d useful cumulative constraints of %d constraints\n", nusefulconss, nconss);
12975 &nchgbds, &naggrvars, &nchgbds, &ndelconss, &nchgbds, &nchgbds, &nchgbds, &cutoff, &cutoff) );
13002 SCIP_CALL( propagateAllConss(scip, conshdlrdata, conss, nconss, TRUE, &nchgbds, &cutoff, NULL) );
13013 SCIPdebugMessage("delete (locally) %d constraints and changed %d variable bounds\n", ndelconss, nchgbds);
13066 /* remove jobs which have a duration or demand of zero (zero energy) or lay outside the effective horizon [hmin,
13073 nfixedvars, naggrvars, nchgbds, ndelconss, naddconss, nchgcoefs, nchgsides, &cutoff, &unbounded) );
13085 /* in the first round we create a disjunctive constraint containing those jobs which cannot run in parallel */
13109 /* combine different source and detect disjunctive constraints and variable bound constraints to improve the
13128 || *nchgcoefs > oldnchgcoefs || *nupgdconss > oldnupgdconss || *ndelconss > oldndelconss || *naddconss > oldnaddconss )
13159 SCIPdebugMessage("resolve propagation: variable <%s>, cumulative constraint <%s> (capacity %d, propagation %d, H=[%d,%d))\n",
13160 SCIPvarGetName(infervar), SCIPconsGetName(cons), consdata->capacity, inferInfoGetProprule(intToInferInfo(inferinfo)),
13165 infervar, intToInferInfo(inferinfo), boundtype, bdchgidx, relaxedbd, conshdlrdata->usebdwidening, NULL, result) );
13178 SCIPdebugMessage("lock cumulative constraint <%s> with nlockspos = %d, nlocksneg = %d\n", SCIPconsGetName(cons), nlockspos, nlocksneg);
13252 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &vars[v], varmap, consmap, global, valid) );
13267 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
13338 SCIPdebugMessage("parse job <%s>, duration %d, demand %d\n", SCIPvarGetName(var), duration, demand);
13366 SCIP_CALL( SCIPcreateConsCumulative(scip, cons, name, nvars, vars, durations, demands, capacity,
13367 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
13406 /** constraint method of constraint handler which returns the number of variables (if possible) */
13471 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecCumulative, NULL) );
13500 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropCumulative, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
13503 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpCumulative, consSepasolCumulative, CONSHDLR_SEPAFREQ,
13551 "constraints/"CONSHDLR_NAME"/fillbranchcands", "should branching candidates be added to storage?",
13574 "number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit)?",
13577 "constraints/"CONSHDLR_NAME"/detectdisjunctive", "search for conflict set via maximal cliques to detect disjunctive constraints",
13580 "constraints/"CONSHDLR_NAME"/detectvarbounds", "search for conflict set via maximal cliques to detect variable bound constraints",
13585 "constraints/"CONSHDLR_NAME"/usebdwidening", "should bound widening be used during the conflict analysis?",
13597 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
13619 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
13621 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
13642 SCIP_CALL( consdataCreate(scip, &consdata, vars, NULL, durations, demands, nvars, capacity, 0, INT_MAX, check) );
13667 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
13668 * method SCIPcreateConsCumulative(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
13670 * @see SCIPcreateConsCumulative() for information about the basic constraint flag configuration
13672 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
13679 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
13687 SCIP_CALL( SCIPcreateConsCumulative(scip, cons, name, nvars, vars, durations, demands, capacity,
13886 /** check for the given starting time variables with their demands and durations if the cumulative conditions for the
13893 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
13907 SCIP_CALL( checkCumulativeCondition(scip, sol, nvars, vars, durations, demands, capacity, hmin, hmax,
13931 /** searches for a time point within the cumulative condition were the cumulative condition can be split */
13935 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
13944 SCIP_CALL( computeEffectiveHorizonCumulativeCondition(scip, nvars, vars, durations, demands, capacity,
13950 /** presolve cumulative condition w.r.t. effective horizon by detecting irrelevant variables */
13961 SCIP_Bool* irrelevants, /**< array mark those variables which are irrelevant for the cumulative condition */
13971 SCIP_CALL( presolveConsEst(scip, nvars, vars, durations, hmin, hmax, downlocks, uplocks, cons,
13975 SCIP_CALL( presolveConsLct(scip, nvars, vars, durations, hmin, hmax, downlocks, uplocks, cons,
13985 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
13994 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
14042 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
14044 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
14045 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
14048 SCIP_CALL( respropCumulativeCondition(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
14049 infervar, intToInferInfo(inferinfo), boundtype, bdchgidx, relaxedbd, TRUE, explanation, result) );
14107 SCIPgmlWriteNode(file, (unsigned int)(size_t)var, SCIPvarGetName(var), "rectangle", color, NULL);
14126 SCIPgmlWriteArc(file, (unsigned int)(size_t)vbdvars[b], (unsigned int)(size_t)var, NULL, NULL);
14138 SCIPgmlWriteArc(file, (unsigned int)(size_t)var, (unsigned int)(size_t)vbdvars[b], NULL, NULL);
14158 SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)) /**< method to use an individual cumulative condition */
14182 * @note If the problem was solved to the earliest start times (ests) and latest start times (lsts) array contain the
14183 * solution values; If the problem was not solved these two arrays contain the global bounds at the time the sub
14191 SCIP_Real* objvals, /**< array of objective coefficients for each job (linear objective function), or NULL if none */
14199 SCIP_Longint maxnodes, /**< maximum number of branch-and-bound nodes to solve the single cumulative constraint (-1: no limit) */
14229 /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
14232 SCIP_CALL( conshdlrdata->solveCumulative(njobs, ests, lsts, objvals, durations, demands, capacity,
14239 /** creates the worst case resource profile, that is, all jobs are inserted with the earliest start and latest
14246 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
14276 /* add each job with its earliest start and latest completion time into the resource profile */
14301 SCIP_CALL( SCIPprofileInsertCore(profile, impliedest, impliedlct, copydemands[v], &pos, &infeasible) );
14320 /** computes w.r.t. the given worst case resource profile the first time point where the given capacity can be violated */
|