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_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? */ 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 { 255 }; 325 /** constructs an inference information out of a propagation rule, an earliest start and a latest completion time */ 376 #define computeCoreWithInterval(begin, end, ect, lst) (MAX(0, MIN((end), (ect)) - MAX((lst), (begin)))) 401 /* the code contains a bug; we need to check if an implication forces that the jobs do not run in parallel */ 469 /* the code contains a bug; we need to check if an implication forces that the jobs do not run in parallel */ 511 /** collects all necessary binary variables to represent the jobs which can be active at time point of interest */ 556 /* check the end time of this job is larger than the curtime; in this case the job is still running */ 665 /* check the end time of this job is larger than the curtime; in this case the job is still running */ 726 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */ 766 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */ 817 SCIPdebugMessage("%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n", 818 *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var), 837 SCIPdebugMessage("%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n", 838 *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var), 847 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */ 882 SCIP_Real** cumulativedemands, /**< array to store the estimated cumulative demand for each point in time */ 890 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */ 891 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */ 916 createSortedEventpoints(scip, nvars, vars, durations, starttimes, endtimes, startindices, endindices, TRUE); 1102 disjfactor2 = MAX( disjfactor2, (peak-(SCIP_Real)capacity)/peak * (nlarge/(SCIP_Real)ndemands) ); 1103 cumfactor1 = MAX( cumfactor1, (peak-capacity)/peak * (capacity-deltademand)/(SCIP_Real)capacity ); 1143 SCIPstatisticPrintf("cumulative constraint<%s>: DISJ1=%g, DISJ2=%g, CUM=%g, RS1 = %g, RS2 = %g, EST = %g\n", 1144 SCIPconsGetName(cons), consdata->disjfactor1, disjfactor2, cumfactor1, resstrength1, resstrength2, 1225 { 1266 SCIP_CALL( SCIPcreateVarBasic(subscip, &subvars[v], name, ests[v], lsts[v], objval, SCIP_VARTYPE_INTEGER) ); 1284 * @note This "meta" setting has to be set first since this call overwrite all parameters including for example the 1312 SCIPdebugMessage("solved single cumulative condition with status %d\n", SCIPgetStatus(subscip)); 1419 /* create for each job and time step a binary variable which is one if this jobs starts at this time point and a set 1460 SCIP_CALL( SCIPcreateVarBasic(subscip, &binvar, name, 0.0, 1.0, objval, SCIP_VARTYPE_BINARY) ); 1463 /* add binary varibale to the set partitioning constraint which ensures that the job is started */ 1474 /* adjusted the smallest earliest start time and the largest latest completion time with the effective horizon */ 1481 /* create for each time a knapsack constraint which ensures that the resource capacity is not exceeded */ 1490 SCIP_CALL( SCIPcreateConsBasicKnapsack(subscip, &cons, name, 0, NULL, NULL, (SCIP_Longint)capacity) ); 1551 SCIPdebugMessage("solved single cumulative condition with status %d\n", SCIPgetStatus(subscip)); 1617 /* check which binary varibale is the first binary varibale which is not globally fixed to zero */ 1627 /* check which binary varibale is the last binary varibale which is not globally fixed to zero */ 1682 * Method used to create and free the constraint handler data when including and removing the cumulative constraint 1847 SCIP_CONS** linkingconss, /**< array of linking constraints for the integer variables, or NULL */ 1906 /* initialize variable lock data structure; the locks are only used if the contraint is a check constraint */ 1911 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->linkingconss, linkingconss, nvars) ); 1920 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) ); 1922 /* multi-aggregated variables cannot be replaced by active variable; therefore we mark all variables for not 1933 SCIP_CALL( SCIPtransformConss(scip, (*consdata)->nvars, (*consdata)->linkingconss, (*consdata)->linkingconss) ); 2087 SCIPinfoMessage(scip, file, ")[%d,%d) <= %d", consdata->hmin, consdata->hmax, consdata->capacity); 2112 SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, consdata->downlocks[pos], consdata->uplocks[pos]) ); 2133 SCIPvarGetName(consdata->vars[pos]), SCIPvarGetLbGlobal(consdata->vars[pos]), SCIPvarGetUbGlobal(consdata->vars[pos]), SCIPconsGetName(cons)); 2136 /* in case the we did not remove the variable in the last slot of the arrays we move the current last to this 2187 SCIPdebugMessage("linking constraint (%d of %d) for variable <%s>\n", v+1, nvars, SCIPvarGetName(var)); 2210 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(consdata->linkingconss[v])), "linking") == 0 ); 2225 /** check for the given starting time variables with their demands and durations if the cumulative conditions for the 2233 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 2246 int* startindices; /* we will sort the startsolvalues, thus we need to know which index of a job it corresponds to */ 2247 int* endindices; /* we will sort the endsolvalues, thus we need to know which index of a job it corresponds to */ 2266 /* compute time points where we have to check whether capacity constraint is infeasible or not */ 2277 /* the constraint of the cumulative constraint handler should be called after the integrality check */ 2282 /* we need to ensure that we check at least one time point during the effective horizon; therefore we project all 2292 /* sort the arrays not-decreasing according to start solution values and end solution values (and sort the 2367 /** check if the given constrait is valid; checks each starting point of a job whether the remaining capacity is at 2420 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */ 2423 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 2437 SCIPdebugMessage("variable <%s>: (demand %d) resolve propagation of core time algorithm (peak %d)\n", 2449 /* first we loop over all variables and adjust the capacity with those jobs which provide a global core at the 2450 * inference peak and those where the current conflict bounds provide a core at the inference peak 2464 /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */ 2465 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPvarGetUbAtIndex(var, bdchgidx, TRUE), SCIPvarGetUbAtIndex(var, bdchgidx, FALSE))); 2467 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPvarGetLbAtIndex(var, bdchgidx, TRUE), SCIPvarGetLbAtIndex(var, bdchgidx, FALSE))); 2477 /* check if the inference peak is part of the global bound core; if so we decreasing the capacity by the demand of 2495 /* collect the conflict bound core (the conflict bounds are those bounds which are already part of the conflict) 2496 * hence these bound are already reported by other resolve propation steps. In case a bound (lower or upper) is 2502 /* check if the inference peak is part of the conflict bound core; if so we decreasing the capacity by the demand 2505 * @note we do not need to reported that job to SCIP since the required bounds are already reported 2532 /* collect all cores of the variables which lay in the considered time window except the inference variable */ 2545 /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */ 2546 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPvarGetUbAtIndex(var, bdchgidx, TRUE), SCIPvarGetUbAtIndex(var, bdchgidx, FALSE))); 2548 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPvarGetLbAtIndex(var, bdchgidx, TRUE), SCIPvarGetLbAtIndex(var, bdchgidx, FALSE))); 2556 SCIPvarGetName(var), SCIPvarGetLbAtIndex(var, bdchgidx, FALSE), SCIPvarGetUbAtIndex(var, bdchgidx, FALSE), 2600 SCIPdebugMessage("infer peak %d, relaxed peak %d, lst %d, ect %d\n", inferpeak, relaxedpeak, maxlst, minect); 2628 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(inferpeak - duration + 1)) ); 2654 /** repropagation of edge finding algorithm simplified version from Petr Vilim only a small subset is reported such that 2668 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */ 2670 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 2683 SCIPdebugMessage("repropagate edge-finding with short reasons for variable <%s>\n", SCIPvarGetName(infervar)); 2725 /* in case the earliest start time is equal to hmin we have to also consider the jobs which run in that region 2730 /* in case the latest completion time is equal to hmax we have to also consider the jobs which run in that region 2759 /** compute the minimum overlaps w.r.t. the duration of the job and the time window [begin,end) */ 2792 /** an overload was detected due to the time-time edge-finding propagate; initialized conflict analysis, add an initial 2795 * @note the conflict analysis is not performend, only the initialized SCIP_Bool pointer is set to TRUE 2809 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */ 2812 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 2829 SCIPdebugMessage("analysis energy load in [%d,%d) (capacity %d, energy %d)\n", begin, end, capacity, requiredenergy); 2831 /* collect global contribution and adjusted the required energy by the amount of energy the inference variable 2866 SCIPvarGetName(var), SCIPvarGetLbAtIndex(var, bdchgidx, FALSE), SCIPvarGetUbAtIndex(var, bdchgidx, FALSE), 2869 /* compute the amount of energy which needs to be available for enforcing the propagation and report the bound 2876 /* get the latest start time of the infer start time variable before the propagation took place */ 2879 /* the latest start time of the inference start time variable before the propagation needs to be smaller as 2880 * the end of the time interval; meaning the job needs be overlap with the time interval in case the job is 2885 /* compute the overlap of the job in case it would be scheduled w.r.t. its latest start time and the time 2890 /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */ 2895 assert(bdchgidx == NULL || SCIPconvertRealToInt(scip, SCIPvarGetUbAtIndex(var, bdchgidx, TRUE)) < begin); 2909 assert(SCIPconvertRealToInt(scip, SCIPvarGetUbAtIndex(var, bdchgidx, FALSE)) <= (end - overlap)); 2923 /* get the earliest completion time of the infer start time variable before the propagation took place */ 2926 /* the earliest start time of the inference start time variable before the propagation needs to be larger as 2927 * than the beginning of the time interval; meaning the job needs be overlap with the time interval in case 2932 /* compute the overlap of the job in case it would be scheduled w.r.t. its earliest start time and the time 2937 /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */ 2956 assert(SCIPconvertRealToInt(scip, SCIPvarGetLbAtIndex(var, bdchgidx, FALSE)) >= (begin + overlap - duration)); 2957 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(begin + overlap - duration)) ); 2965 /* subtract the amount of energy which is available due to the overlap of the inference start time */ 2980 /* check if the has any overlap w.r.t. global bound; meaning some parts of the job will run for sure within the 2999 /* check if the job has any overlap w.r.t. local bound; meaning some parts of the job will run for sure within the 3060 SCIPdebugMessage("variable <%s> glb=[%g,%g] loc=[%g,%g], conf=[%g,%g], added=[%d,%d] (demand %d, duration %d)\n", 3097 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */ 3100 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 3101 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */ 3131 /* we propagated the latest start time (upper bound) step wise with a step length of at most the duration of 3134 assert(SCIPvarGetUbAtIndex(infervar, bdchgidx, FALSE) - SCIPvarGetUbAtIndex(infervar, bdchgidx, TRUE) < inferduration + 0.5); 3142 /* the bound passed back to be resolved might be tighter as the bound propagted by the core time propagator; 3143 * this can happen if the variable is not activ and aggregated to an activ variable with a scale != 1.0 3145 assert(SCIPconvertRealToInt(scip, SCIPvarGetUbAtIndex(infervar, bdchgidx, TRUE)) + inferduration <= inferpeak); 3169 /* the bound passed back to be resolved might be tighter as the bound propagted by the core time propagator; 3170 * this can happen if the variable is not activ and aggregated to an activ variable with a scale != 1.0 3172 assert(SCIPconvertRealToInt(scip, SCIPvarGetLbAtIndex(infervar, bdchgidx, TRUE)) - 1 >= inferpeak); 3187 SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax, 3188 infervar, inferdemand, inferpeak, relaxedpeak, bdchgidx, usebdwidening, &provedpeak, explanation) ); 3208 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, bdchgidx, (SCIP_Real)(provedpeak - inferduration + 1)) ); 3293 SCIP_CALL( SCIPbranchVarHole(scip, var, SCIPvarGetLbLocal(var), (SCIP_Real)alternativelbs[v], NULL, NULL) ); 3311 SCIP_CALL( SCIPbranchVarHole(scip, var, (SCIP_Real)alternativeubs[v], SCIPvarGetUbLocal(var), NULL, NULL) ); 3394 /** computes a point in time when the capacity is exceeded returns hmax if this does not happen */ 3405 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */ 3406 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */ 3451 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars); 3479 /** checks all cumulative constraints for infeasibility and add branching candidates to storage */ 3496 SCIP_CALL( SCIPhashtableCreate(&collectedvars, SCIPblkmem(scip), SCIPcalcHashtableSize(SCIPgetNVars(scip)), 3648 if( SCIPvarGetNLocksDown(var) > (int)downlocks[v] || SCIPvarGetNLocksUp(var) > (int)uplocks[v] ) 3655 /** in case the cumulative constraint is independent of every else, solve the cumulative problem and apply the fixings 3662 SCIP_Longint maxnodes, /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */ 3688 /* if SCIP is in probing mode or repropagation we cannot perform this dual reductions since this dual reduction 3694 /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot 3702 /* if the cumulative constraint is the only constraint of the original problem or the only check constraint in the 3716 /* after 250 conflict we force a restart since then the variable statistics are reasonable initialized */ 3752 /* check if already tried to solve that constraint as independent sub problem; we do not want to try it again if we 3762 /* mark the constraint to be tried of solving it as independent sub problem; in case that is successful the 3767 SCIPdebugMessage("the cumulative constraint <%s> is independent from rest of the problem (%d variables, %d constraints)\n", 3782 /* if a variables array is given, use the variable bounds otherwise the default values stored in the ests and lsts 3800 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */ 3808 SCIP_CALL( SCIPsolveCumulative(scip, nvars, lbs, ubs, objvals, consdata->durations, consdata->demands, consdata->capacity, 3809 consdata->hmin, consdata->hmax, timelimit, memorylimit, maxnodes, &solved, cutoff, unbounded, &error) ); 3889 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 3892 SCIPdebugMessage("detected infeasibility due to adding a core to the core resource profile\n"); 3901 SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax, 3906 /* add both bound of the inference variable since these biuld the core which we could not inserted */ 3909 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, NULL, (SCIP_Real)(inferpeak - inferduration + 1)) ); 3924 /** We are using the core resource profile which contains all core except the one of the start time variable which we 3925 * want to propagate, to incease the earliest start time. This we are doing in steps of length at most the duration of 3926 * the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict 3945 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 3972 /* first we find left position of earliest start time (lower bound) in resource profile; this position gives us the 3998 /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we 4011 /* if we found no peak that means current the job could be scheduled at its earliest start time without 4017 /* the peak position gives us a time point where the start time variable is in conflict with the resource 4018 * profile. That means we have to move it to the next time point in the resource profile but at most to the 4030 SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax, 4041 /* construct the inference information which we are using with the conflict analysis to resolve that particular 4047 SCIP_CALL( SCIPinferVarLbCons(scip, var, (SCIP_Real)newlb, cons, inferInfoToInt(inferinfo), TRUE, infeasible, &tightened) ); 4051 SCIPdebugMessage("variable <%s> new lower bound <%d> -> <%d>\n", SCIPvarGetName(var), est, newlb); 4054 /* for the statistic we count the number of times a lower bound was tightened due the the time-table algorithm */ 4059 * @note We are taking the lower of the start time variable on purpose instead of newlb. This is due the fact that 4060 * the proposed lower bound might be even strength by be the core which can be the case if aggregations are 4077 /** We are using the core resource profile which contains all core except the one of the start time variable which we 4078 * want to propagate, to decrease the latest start time. This we are doing in steps of length at most the duration of 4079 * the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict 4118 /* first we find left position of latest completion time minus 1 (upper bound + duration) in resource profile; That 4119 * is the last time point where the job would run if schedule it at its latest start time (upper bound). This 4149 /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we 4161 /* if we found no peak that means the current job could be scheduled at its latest start time without conflicting 4167 /* the peak position gives us a time point where the start time variable is in conflict with the resource 4168 * profile. That means the job has be done until that point. Hence that gives us the latest completion 4169 * time. Note that that we want to move the bound by at most the duration length (the remaining move we are 4176 /* construct the inference information which we are using with the conflict analysis to resolve that particular 4182 SCIP_CALL( SCIPinferVarUbCons(scip, var, (SCIP_Real)newub, cons, inferInfoToInt(inferinfo), TRUE, &infeasible, &tightened) ); 4186 SCIPdebugMessage("variable <%s>: new upper bound <%d> -> <%d>\n", SCIPvarGetName(var), lst, newub); 4189 /* for the statistic we count the number of times a upper bound was tightened due the the time-table algorithm */ 4194 * @note We are taking the upper of the start time variable on purpose instead of newub. This is due the fact that 4195 * the proposed upper bound might be even strength by be the core which can be the case if aggregations are 4213 /** compute for the different earliest start and latest completion time the core energy of the corresponding time 4223 int* coreEnergyAfterEst, /**< array to store the core energy after the earliest start time of each job */ 4224 int* coreEnergyAfterLct /**< array to store the core energy after the latest completion time of each job */ 4243 energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1)); 4252 coreEnergyAfterEst[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - ests[v]); 4268 energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1)); 4277 coreEnergyAfterLct[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - lcts[v]); 4376 int* inferinfos, /**< pointer to store the inference information which is need for the (best) lower bound change */ 4378 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 4391 /* if the job can be processed completely before or after the time window, nothing can be tightened */ 4395 /* if flexible part runs completely within the time window (assuming it is scheduled on its earliest start time), we 4401 /* check if the available energy in the time window is to small to handle the flexible part if it is schedule on its 4407 /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is 4410 * @note the variable ect define the earliest completion time of the flexible part of the job; hence we need to 4415 /* compute a latest start time (upper bound) such that the job consums at most the available energy 4421 /* check if we detected an infeasibility which is the case if the new lower bound is larger than the current upper 4444 begin, end, var, SCIP_BOUNDTYPE_LOWER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) ); 4489 int* inferinfos, /**< pointer to store the inference information which is need for the (best) upper bound change */ 4491 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 4505 /* if flexible part of the job can be processed completely before or after the time window, nothing can be tightened */ 4509 /* if flexible part runs completely within the time window (assuming it is scheduled on its latest start time), we 4515 /* check if the available energy in the time window is to small to handle the flexible part of the job */ 4519 /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is 4522 * @note the variable lst define the latest start time of the flexible part of the job; hence we need to compute the 4528 /* compute a latest start time (upper bound) such that the job consums at most the available energy 4535 /* check if we detected an infeasibility which is the case if the new upper bound is smaller than the current lower 4558 begin, end, var, SCIP_BOUNDTYPE_UPPER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) ); 4581 /** propagate the upper bounds and "opportunistically" the lower bounds using the time-table edge-finding algorithm */ 4595 int* lbinferinfos, /**< array to store the inference information for the lower bound changes */ 4596 int* ubinferinfos, /**< array to store the inference information for the upper bound changes */ 4597 int* lsts, /**< array of latest start time of the flexible part in the same order as the variables */ 4599 int* perm, /**< permutation of the variables w.r.t. the non-decreasing order of the earliest start times */ 4605 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 4644 /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */ 4650 /* loop over all variable in non-increasing order w.r.t. the latest completion time; thereby, the latest completion 4663 /* if the latest completion time is larger then hmax an infeasibility cannot be detected, since after hmax an 4676 /* if the latest completion time equals to previous end time, we can continue since this particular interval 4684 /* In case we only want to detect an overload (meaning no bound propagation) we can skip the interval; this is 4685 * the case if the free energy (the energy which is not occupied by any core) is smaller than the previous minimum 4700 SCIPdebugMessage("skip latest completion time <%d> (minimum available energy <%d>, free energy <%d>)\n", lct, minavailable, freeenergy); 4716 /* loop over the job in non-increasing order w.r.t. the earliest start time; these earliest start time are 4717 * defining the beginning of the time interval under investigation; Thereby, the time interval gets wider and 4738 /* if the job starts after the current end, we can skip it and do not need to consider it again since the 4747 /* check if the interval has a size such that the total energy fits, if so we can skip all intervals with the 4767 /* in case the earliest start time is equal to minbegin, the job lies completely within the time window under 4776 SCIP_CALL( tightenUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax, 4777 var, duration, demand, est, lst, lct, minbegin, end, minavailable, &(newubs[idx]), &(ubinferinfos[idx]), 4784 SCIPdebugMessage("check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, lst of free part <%d>\n", 4785 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, lst); 4790 /* if the earliest start time is smaller than hmin we can stop here since the next job will not decrease the 4810 /* compute the flexible energy which is part of the time interval for sure if the job is scheduled 4822 /* compute the flexible energy of the job which is not part of flexible energy of the time interval */ 4838 freeenergy = capacity * (end - begin) - flexenergy - coreEnergyAfterEst[i] + coreEnergyAfterEnd; 4843 SCIPdebugMessage("analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity); 4860 /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */ 4861 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ ); 4866 /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */ 4877 energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, end - lsts[lbcand])) * demands[lbcand]; 4932 /** propagate the lower bounds and "opportunistically" the upper bounds using the time-table edge-finding algorithm */ 4946 int* lbinferinfos, /**< array to store the inference information for the lower bound changes */ 4947 int* ubinferinfos, /**< array to store the inference information for the upper bound changes */ 4948 int* ects, /**< array of earliest completion time of the flexible part in the same order as the variables */ 4950 int* perm, /**< permutation of the variables w.r.t. the non-decreasing order of the latest completion times */ 4956 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 4999 /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */ 5005 /* loop over all variable in non-decreasing order w.r.t. the earliest start times; thereby, the earliest start times 5019 /* if the earliest start time is smaller then hmin an infeasibility cannot be detected, since before hmin an 5029 /* if the latest earliest start time equals to previous start time, we can continue since this particular interval 5048 /* loop over the job in non-decreasing order w.r.t. the latest completion time; these latest completion times are 5049 * defining the ending of the time interval under investigation; thereby, the time interval gets wider and wider 5069 /* if the job has a latest completion time before the the current start, we can skip it and do not need to 5070 * consider it again since the earliest start times (which define the start) are scant in non-decreasing order 5078 /* check if the interval has a size such that the total energy fits, if so we can skip all intervals which 5098 /* in case the latest completion time is equal to minend, the job lies completely within the time window under 5107 SCIP_CALL( tightenLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax, 5108 var, duration, demand, est, ect, lct, begin, minend, minavailable, &(newlbs[idx]), &(lbinferinfos[idx]), 5115 SCIPdebugMessage("check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, ect of free part <%d>\n", 5116 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, ect); 5121 /* if the latest completion time is larger than hmax we can stop here since the next job will not decrease the 5141 /* compute the flexible energy which is part of the time interval for sure if the job is scheduled 5153 /* compute the flexible energy of the job which is not part of flexible energy of the time interval */ 5169 freeenergy = capacity * (end - begin) - flexenergy - coreEnergyAfterStart + coreEnergyAfterLct[i]; 5174 SCIPdebugMessage("analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity); 5191 /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */ 5192 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ ); 5197 /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */ 5211 energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, ects[ubcand] - begin)) * demands[ubcand]; 5265 /** checks whether the instance is infeasible due to a overload within a certain time frame using the idea of time-table 5269 * - Petr Vilim, "Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources", In: Tobias 5270 * Achterberg and J. Christopher Beck (Eds.), Integration of AI and OR Techniques in Constraint Programming for 5272 * - Andreas Schutt, Thibaut Feydy, and Peter J. Stuckey, "Explaining Time-Table-Edge-Finding Propagation for the 5290 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 5336 /* we need to buffer the bound changes since the propagation algorithm cannot handle new bound dynamically */ 5346 collectDataTTEF(scip, nvars, vars, durations, demands, hmin, hmax, permests, ests, permlcts, lcts, ects, lsts, flexenergies); 5352 /* compute for the different earliest start and latest completion time the core energy of the corresponding time 5355 SCIP_CALL( computeCoreEngeryAfter(scip, profile, nvars, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct) ); 5358 SCIP_CALL( propagateUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax, 5360 permests, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) ); 5363 SCIP_CALL( propagateLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax, 5365 permlcts, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) ); 5373 SCIP_CALL( SCIPinferVarLbCons(scip, vars[v], (SCIP_Real)newlbs[v], cons, lbinferinfos[v], TRUE, &infeasible, &tightened) ); 5387 SCIP_CALL( SCIPinferVarUbCons(scip, vars[v], (SCIP_Real)newubs[v], cons, ubinferinfos[v], TRUE, &infeasible, &tightened) ); 5389 /* since upper bound was compute w.r.t. the "old" bound the previous lower bound update together with this upper 5427 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ ); 5461 /** a cumulative condition is not satisfied if its capacity is exceeded at a time where jobs cannot be shifted (core) 5462 * anymore we build up a cumulative profile of all cores of jobs and try to improve bounds of all jobs; also known as 5480 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 5536 /* check if the job runs completely outside of the effective horizon [hmin, hmax); if so skip it */ 5551 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, begin, end); 5557 SCIP_CALL( coretimesUpdateLb(scip, nvars, vars, durations, demands, capacity, hmin, hmax, cons, 5591 SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax, 5592 var, duration, demand, SCIPprofileGetTime(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) ); 5600 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutofftimetable++ ); 5614 SCIP_VAR* var; /**< start time variable of the job if the node data belongs to a leaf, otherwise NULL */ 5708 nodedata->enveloptheta = MAX(leftdata->enveloptheta + rightdata->energytheta, rightdata->enveloptheta); 5720 nodedata->enveloplambda = MAX(leftdata->enveloplambda + rightdata->energytheta, rightdata->enveloplambda); 5726 nodedata->enveloplambda = MAX(nodedata->enveloplambda, leftdata->enveloptheta + rightdata->energylambda); 5734 nodedata->energylambda = MAX(leftdata->energylambda + rightdata->energytheta, leftdata->energytheta + rightdata->energylambda); 6043 if( leftdata->energylambda >= 0 && nodedata->energylambda == leftdata->energylambda + rightdata->energytheta ) 6093 if( leftdata->enveloplambda >= 0 && nodedata->enveloplambda == leftdata->enveloplambda + rightdata->energytheta ) 6130 SCIPdebugMessage("add variable <%s> as elements %d to omegaset\n", SCIPvarGetName(nodedata->var), *nelements); 6135 (*energy) += (nodedata->duration - nodedata->leftadjust - nodedata->rightadjust) * nodedata->demand; 6188 if( leftdata->enveloptheta >= 0 && nodedata->enveloptheta == leftdata->enveloptheta + rightdata->energytheta ) 6243 if( leftdata->energylambda >= 0 && nodedata->energylambda == leftdata->energylambda + rightdata->energytheta ) 6303 if( leftdata->enveloplambda >= 0 && nodedata->enveloplambda == leftdata->enveloplambda + rightdata->energytheta ) 6342 SCIPvarGetName(nodedata->var), SCIPvarGetLbLocal(nodedata->var), SCIPvarGetUbLocal(nodedata->var), 6343 SCIPvarGetLbGlobal(nodedata->var), SCIPvarGetUbGlobal(nodedata->var), duration, nodedata->demand); 6352 { 6365 { 6378 * @note the conflict analysis is not performend, only the initialized SCIP_Bool pointer is set to TRUE 6389 SCIP_Bool propest, /**< should the earliest start times be propagated, otherwise the latest completion times */ 6393 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 6403 SCIPdebugMessage("est=%d, lct=%d, propest %u, reportedenergy %d, shift %d\n", est, lct, propest, reportedenergy, shift); 6411 /* collect the energy of the responsible leaves until the cumulative energy is large enough to detect an overload; 6432 SCIPdebugMessage("time window [%d,%d) available energy %d, required energy %d\n", est, lct, energy, reportedenergy); 6455 /* report the variables and relax their bounds to final time interval [est,lct) which was been detected to be 6469 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, nodedata->var, NULL, (SCIP_Real)(est - nodedata->leftadjust)) ); 6470 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, nodedata->var, NULL, (SCIP_Real)(lct - nodedata->duration + nodedata->rightadjust)) ); 6487 /** computes a new latest starting time of the job in 'respleaf' due to the energy consumption and stores the 6511 newest = (int)SCIPfeasCeil(scip, (energy - (SCIP_Real)(capacity - demand) * (lct - est)) / (SCIP_Real)demand); 6519 /** propagates start time using an edge finding algorithm which is based on binary trees (theta lambda trees) 6521 * @note The algorithm is based on the paper: Petr Vilim, "Edge Finding Filtering Algorithm for Discrete Cumulative 6533 SCIP_Bool propest, /**< should the earliest start times be propagated, otherwise the latest completion times */ 6536 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 6549 /* iterate over all added candidate (leaves) in non-increasing order w.r.t. their latest completion time */ 6610 newest = computeEstOmegaset(scip, leafdata->duration, leafdata->demand, capacity, est, lct, energy); 6612 /* if the computed earliest start time is greater than the latest completion time of the omega set we detected an overload */ 6618 SCIP_CALL( analyzeConflictOverload(scip, omegaset, capacity, nelements, est, lct, 0, propest, shift, 6623 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffedgefinder++ ); 6633 /* constuct inference information; store used propagation rule and the the time window of the omega set */ 6642 /* for the statistic we count the number of times a lower bound was tightened due the edge-finder */ 6647 /* constuct inference information; store used propagation rule and the the time window of the omega set */ 6651 SCIPvarGetName(leafdata->var), SCIPvarGetUbLocal(leafdata->var), shift - newest - leafdata->duration); 6653 SCIP_CALL( SCIPinferVarUbCons(scip, leafdata->var, (SCIP_Real)(shift - newest - leafdata->duration), 6656 /* for the statistic we count the number of times a upper bound was tightened due the edge-finder */ 6704 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffedgefinder++ ); 6726 /** checks whether the instance is infeasible due to a overload within a certain time frame using the idea of theta trees 6728 * @note The algorithm is based on the paper: Petr Vilim, "Max Energy Filtering Algorithm for Discrete Cumulative 6729 * Resources". In: Willem Jan van Hoeve and John N. Hooker (Eds.), Integration of AI and OR Techniques in 6730 * Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2009), LNCS 5547, pp 294--308 6744 SCIP_Bool propest, /**< should the earliest start times be propagated, otherwise the latest completion times */ 6746 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 6769 SCIPdebugMessage("check overload of cumulative condition of constraint <%s> (capacity %d)\n", SCIPconsGetName(cons), capacity); 6786 /* compute the latest completion time of all jobs which define the shift we apply to run the algorithm for the 6798 /* collect earliest and latest completion times and ignore jobs which do not run completion within the effective 6824 /* adjust the duration, earliest start time, and latest completion time of jobs which do not lie completely in the 6840 /* only consider jobs which have a (adjusted) duration greater than zero (the amound which will run defenetly 6877 /* adjust earliest start time to make it unique in case several jobs have the same earliest start time */ 6887 /* the envelop is the energy of the job plus the total amount of energy which is available in the time period 6888 * before that job can start, that is [0,est). The envelop is later used to compare the energy consumption of a 6910 /* iterate over all jobs in non-decreasing order of their latest completion times and add them to the theta set until 6918 /* check if the new job opens a time window which size is so large that it offers more energy than the total 6946 SCIPdebugMessage("detects cutoff due to overload in time window [?,%d) (ncands %d)\n", nodedatas[j]->lct, j); 6950 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverload++ ); 6956 /* in case an overload was detected and the conflict analysis is applicable, create an initialize explanation */ 6967 /* scan the remaining candidates for a global contributions within the time window of the last inserted candidate 7003 SCIP_CALL( analyzeConflictOverload(scip, leaves, capacity, ninsertcands, est, lct, glbenery, propest, shift, 7009 SCIP_CALL( inferboundsEdgeFinding(scip, conshdlrdata, cons, tree, leaves, capacity, ninsertcands, 7029 /** checks whether the instance is infeasible due to a overload within a certain time frame using the idea of theta trees 7031 * @note The algorithm is based on the paper: Petr Vilim, "Max Energy Filtering Algorithm for Discrete Cumulative 7032 * Resources". In: Willem Jan van Hoeve and John N. Hooker (Eds.), Integration of AI and OR Techniques in 7033 * Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2009), LNCS 5547, pp 294--308 7048 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 7062 SCIP_CALL( checkOverloadViaThetaTree(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax, 7074 SCIP_CALL( checkOverloadViaThetaTree(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax, 7080 /** checks if the constraint is redundant; that is the case if its capacity can never be exceeded; therefore we check 7081 * with respect to the lower and upper bounds of the integer start time variables the maximum capacity usage for all 7101 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */ 7102 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */ 7155 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */ 7204 /** creates the worst case resource profile, that is, all jobs are inserted with the earliest start and latest 7213 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 7220 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 7254 /* check if the job runs completely outside of the effective horizon [hmin, hmax); if so skip it */ 7279 SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax, 7280 var, duration, demand, SCIPprofileGetTime(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) ); 7288 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutofftimetable++ ); 7314 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 7328 SCIP_CALL( consCheckRedundancy(scip, nvars, vars, durations, demands, capacity, hmin, hmax, redundant) ); 7337 SCIP_CALL( createCoreProfile(scip, conshdlrdata, profile, nvars, vars, durations, demands, capacity, hmin, hmax, 7343 SCIP_CALL( propagateTimetable(scip, conshdlrdata, profile, nvars, vars, durations, demands, capacity, hmin, hmax, cons, 7350 SCIP_CALL( propagateEdgeFinding(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax, 7357 SCIP_CALL( propagateTTEF(scip, conshdlrdata, profile, nvars, vars, durations, demands, capacity, hmin, hmax, cons, 7444 /** it is dual feasible to remove the values {leftub+1, ..., rightlb-1} since SCIP current does not feature domain holes 7445 * we use the probing mode to check if one of the two branches is infeasible. If this is the case the dual redundant can 7456 SCIP_Real* leftimpllbs, /**< lower bounds after applying implications and cliques in left branch, or NULL */ 7457 SCIP_Real* leftimplubs, /**< upper bounds after applying implications and cliques in left branch, or NULL */ 7460 SCIP_Real* rightimpllbs, /**< lower bounds after applying implications and cliques in right branch, or NULL */ 7461 SCIP_Real* rightimplubs, /**< upper bounds after applying implications and cliques in right branch, or NULL */ 7462 SCIP_Real* rightproplbs, /**< lower bounds after applying domain propagation in right branch */ 7463 SCIP_Real* rightpropubs, /**< upper bounds after applying domain propagation in right branch */ 7464 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */ 7490 SCIP_CALL( SCIPapplyProbingVar(scip, vars, nvars, probingpos, SCIP_BOUNDTYPE_UPPER, leftub, -1, 7507 /* note that probing can change the upper bound and thus the right branch may have been detected infeasible if 7525 SCIP_CALL( SCIPapplyProbingVar(scip, vars, nvars, probingpos, SCIP_BOUNDTYPE_LOWER, rightlb, -1, 7564 /* in case the variable is not active we need to check the object coefficient of the active variable */ 7583 /* rounding the integer variable down is only a valid dual reduction if the object coefficient is zero or positive 7588 if( (scalar > 0 && SCIPisNegative(scip, objval)) || (scalar < 0 && SCIPisPositive(scip, objval)) ) 7613 /* in case the variable is not active we need to check the object coefficient of the active variable */ 7632 /* rounding the integer variable up is only a valid dual reduction if the object coefficient is zero or negative 7637 if( (scalar > 0 && SCIPisPositive(scip, objval)) || (scalar < 0 && SCIPisNegative(scip, objval)) ) 7643 /** For each variable we compute an alternative lower and upper bounds. That is, if the variable is not fixed to its 7644 * lower or upper bound the next reasonable lower or upper bound would be this alternative bound (implying that certain 7645 * values are not of interest). An alternative bound for a particular is only valied if the cumulative constarints are 7692 SCIP_CALL( SCIPcreateWorstCaseProfile(scip, profile, consdata->nvars, consdata->vars, consdata->durations, consdata->demands) ); 7720 /* multi-aggregated variables should appear here since we mark the variables to be not mutlt-aggregated */ 7788 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */ 7846 /* for the statistic we count the number of jobs which are dual fixed due the information of all cumulative 7849 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nallconsdualfixs++ ); 7855 /* In the current version SCIP, variable domains are single intervals. Meaning that domain holes or not 7856 * representable. To retrieve a potential dual reduction we using probing to check both branches. If one in 7859 SCIP_CALL( applyProbingVar(scip, vars, nvars, v, (SCIP_Real) lb, (SCIP_Real) alternativelbs[v], 7860 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs, 7865 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nallconsdualfixs++ ); 7893 /* for the statistic we count the number of jobs which are dual fixed due the information of all cumulative 7896 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nallconsdualfixs++ ); 7902 /* In the current version SCIP, variable domains are single intervals. Meaning that domain holes or not 7903 * representable. To retrieve a potential dual reduction we using probing to check both branches. If one in 7906 SCIP_CALL( applyProbingVar(scip, vars, nvars, v, (SCIP_Real) alternativeubs[v], (SCIP_Real) ub, 7907 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs, 7912 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nallconsdualfixs++ ); 7940 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */ 7942 SCIP_Bool* branched /**< pointer to store if a branching was applied, or NULL to avoid branching */ 7976 SCIP_CALL( computeAlternativeBounds(scip, conss, nconss, local, alternativelbs, alternativeubs, downlocks, uplocks) ); 7979 SCIP_CALL( applyAlternativeBoundsFixing(scip, vars, nvars, alternativelbs, alternativeubs, downlocks, uplocks, 7984 SCIP_CALL( applyAlternativeBoundsBranching(scip, vars, nvars, alternativelbs, alternativeubs, downlocks, uplocks, branched) ); 8009 int* startvalues, /**< upper bounds on finishing time per job for activities from 0,..., nactivities -1 */ 8100 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), rowname, -SCIPinfinity(scip), (SCIP_Real)bigcoversize, 8157 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->bcoverrows, consdata->nbcoverrows, consdata->bcoverrowssize) ); 8188 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), rowname, -SCIPinfinity(scip), (SCIP_Real)smallcoversize, 8245 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->scoverrows, consdata->nscoverrows, consdata->scoverrowssize) ); 8272 int* startindices; /* we sort the startvalues, so we need to know wich index of a job it corresponds to */ 8273 int* endindices; /* we sort the endvalues, so we need to know wich index of a job it corresponds to */ 8313 endvalues[j] = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(consdata->vars[j])) + consdata->durations[j]; 8366 /* we can create covering constraints for each pint in time in interval [curtime; nextprofilechange[ */ 8399 /** this method creates a row for time point curtime which insures the capacity restriction of the cumulative 8431 SCIP_CALL( collectBinaryVars(scip, consdata, &binvars, &coefs, &nbinvars, startindices, curtime, nstarted, nfinished) ); 8434 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d[%d]", SCIPconsGetName(cons), nstarted-1, curtime); 8441 SCIP_CALL( SCIPcreateConsKnapsack(scip, &lincons, name, 0, NULL, NULL, (SCIP_Longint)(capacity), 8457 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real)capacity, FALSE, FALSE, SCIPconsIsRemovable(cons)) ); 8476 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->demandrows, consdata->ndemandrows, consdata->demandrowssize) ); 8489 /** this method checks how many cumulatives can run at most at one time if this is greater than the capacity it creates 8503 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */ 8504 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */ 8557 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars); 8574 /* step forward until next job is released and see whether capacity constraint is met or not */ 8583 SCIP_CALL( createCapacityRestriction(scip, cons, startindices, curtime, j+1, endindex, cutsasconss) ); 8585 /* create for all points in time between the current event point and next start event point a row if the free 8598 SCIP_CALL( createCapacityRestriction(scip, cons, startindices, t, j+1, endindex, cutsasconss) ); 8615 /** creates LP rows corresponding to cumulative constraint; therefore, check each point in time if the maximal needed 8692 assert( ! infeasible ); /* this function is only called by initlp -> the cut should be feasible */ 8761 SCIPdebugMessage("cumulative constraint <%s> separated %d cuts\n", SCIPconsGetName(cons), ncuts); 8887 /** this method creates a row for time point @p curtime which ensures the capacity restriction of the cumulative constraint */ 8919 SCIP_CALL( collectIntVars(scip, consdata, &activevars, startindices, curtime, nstarted, nfinished, lower, &lhs ) ); 8925 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, (SCIP_Real) lhs, SCIPinfinity(scip), 8931 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), (SCIP_Real) lhs, 8971 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */ 8972 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */ 9006 createSelectedSortedEventpointsSol(scip, consdata, sol, starttimes, endtimes, startindices, endindices, &nvars, lower); 9024 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars); 9039 SCIP_CALL( createCapacityRestrictionIntvars(scip, cons, sol, startindices, curtime, j+1, endindex, lower) ); 9062 /** returns TRUE if all demands are smaller than the capacity of the cumulative constraint and if the total demand is 9084 /* if no activities are associated with this cumulative then this constraint is not infeasible, return */ 9145 /** remove jobs which have a duration or demand of zero (zero energy) or lay outside the efficient horizon [hmin, hmax); 9204 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nirrelevantjobs++ ); 9238 /* jobs with a demand greater than the the capacity have to moved outside the time interval [hmin,hmax) */ 9246 /* the jobs has to have an overlap with the efficient horizon otherwise it would be already removed */ 9252 /* the job will at least run partly in the time interval [hmin,hmax) this means the problem is infeasible */ 9258 SCIP_CALL( SCIPtightenVarUb(scip, var, (SCIP_Real)(consdata->hmin - duration), TRUE, cutoff, &tightened) ); 9266 SCIP_CALL( SCIPtightenVarLb(scip, var, (SCIP_Real)(consdata->hmax), TRUE, cutoff, &tightened) ); 9273 /* this job can run before or after the time interval [hmin,hmax) thus we create a bound disjunction 9303 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, name, 2, vartuple, boundtypetuple, boundtuple, 9353 SCIPdebugMessage("cumulative constraint <%s> has %d jobs left, cutoff %u\n", SCIPconsGetName(cons), consdata->nvars, *cutoff); 9358 /** fix integer variable to upper bound if the rounding locks and the object coefficient are in favor of that */ 9371 /* if SCIP is in probing mode or repropagation we cannot perform this dual reductions since this dual reduction 9377 /* rounding the variable to the upper bound is only a feasible dual reduction if the cumulative constraint 9389 /* rounding the integer variable up is only a valid dual reduction if the object coefficient is zero or negative 9403 SCIPdebugMessage("fix variable <%s> to upper bound %g\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var)); 9410 /** fix integer variable to lower bound if the rounding locks and the object coefficient are in favor of that */ 9423 /* if SCIP is in probing mode or repropagation we cannot perform this dual reductions since this dual reduction 9429 /* rounding the variable to the lower bound is only a feasible dual reduction if the cumulative constraint 9450 SCIPdebugMessage("fix variable <%s> to lower bound %g\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var)); 9503 SCIPdebugMessage("update cumulative condition (%d + %d > %d) to unary cumulative condition\n", mindemand1, mindemand2, *capacity); 9529 /** divides demands by their greatest common divisor and divides capacity by the same value, rounding down the result; 9530 * in case the the smallest demands add up to more than the capacity we reductions all demands to one as well as the 9556 /**@todo sort items w.r.t. the demands, because we can stop earlier if the smaller weights are evaluated first */ 9558 SCIP_CALL( normalizeCumulativeCondition(scip, consdata->nvars, consdata->vars, consdata->durations, 9574 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 9609 /* If SCIP is repropagating the root node, it is not possible to decompose the constraints. This is the case since 9610 * the conflict analysis stores the constraint pointer for bound changes made by this constraint. These pointer 9611 * are used during the resolve propagation phase to explain bound changes. If we would decompose certain jobs into 9612 * a new cumulative constraint, the "old" pointer is not valid. More precise, the "old" constraint is not able to 9621 /* 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 */ 9632 /* check if the current time point does not exceed the capacity w.r.t. worst case resource profile; if so we 9655 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 9679 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 9681 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 9689 SCIP_CALL( SCIPcreateConsCumulative(scip, &cons, name, nvars, vars, durations, demands, capacity, 9690 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 9730 SCIPdebugMessage("cumulative constraint <%s> adjust hmin <%d> -> <%d>\n", SCIPconsGetName(cons), consdata->hmin, hmin); 9739 SCIPdebugMessage("cumulative constraint <%s> adjust hmax <%d> -> <%d>\n", SCIPconsGetName(cons), consdata->hmax, hmax); 9766 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), 9767 SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) ); 9783 /** presolve cumulative condition w.r.t. the earlier start times (est) and the hmin of the effective horizon 9785 * (1) If the latest completion time (lct) of a job is smaller or equal than hmin, the corresponding job can be removed 9786 * form the constraint. This is the case since it cannot effect any assignment within the effective horizon 9788 * (2) If the latest start time (lst) of a job is smaller or equal than hmin it follows that the this jobs can run 9789 * before the effective horizon or it overlaps with the effective horizon such that hmin in included. Hence, the 9792 * (3) If the earlier completion time (ect) of a job is smaller or equal than hmin, the cumulative is the only one 9793 * locking the corresponding variable down, and the objective coefficient of the start time variable is not 9796 * (4) If the earlier start time (est) of job is smaller than the hmin, the cumulative is the only one locking the 9797 * corresponding variable down, and the objective coefficient of the start time variable is not negative, than 9800 * (5) If the earlier start time (est) of job is smaller than the smallest earlier completion times of all other jobs 9801 * (lets denote this with minect), the cumulative is the only one locking the corresponding variable down, and the 9802 * objective coefficient of the start time variable is not negative, than removing the values {est+1,...,minect-1} 9805 * @note That method does not remove any variable form the arrays. It only marks the variables which are irrelevant for 9819 SCIP_Bool* irrelevants, /**< array mark those variables which are irrelevant for the cumulative condition */ 9852 SCIPdebugMessage("check for irrelevant variable for cumulative condition (hmin %d) w.r.t. earlier start time\n", hmin); 9892 /* collect earlier start time (est), earlier completion time (ect), latest start time (lst), and latest completion 9912 /* (1) check if the job runs completely before the effective horizon; if so the job can be removed form the 9922 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nirrelevantjobs++ ); 9926 /* (2) check if the jobs overlaps with the time point hmin if it overlaps at all with the effective horizon; if 9939 * We mark the job to be deletable. The removement together with the capacity reducion is done later 9948 /* for the statistic we count the number of jobs which always run during the effective horizon */ 9967 /* (3) check if the job can finish before the effective horizon starts; if so and the job can be fixed to its 9968 * earliest start time (which implies that it finishes before the effective horizon starts), the job can be 9972 /* job can be removed from the constraint only if the integer start time variable can be fixed to its lower 9983 SCIPdebugMessage(" variable <%s>[%d,%d] with duration <%d> is irrelevant due to dual fixing wrt EST\n", 9986 /* after fixing the start time variable to its lower bound, the (new) earliest completion time should be smaller or equal ti hmin */ 10002 /* check if the cumulative constraint is the only one looking this variable down and if the objective function 10024 /* for the statistic we count the number of jobs which are dual fixed due the information of all cumulative 10033 /* In the current version SCIP, variable domains are single intervals. Meaning that domain holes or not 10034 * representable. To retrieve a potential dual reduction we using probing to check both branches. If one in 10038 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs, 10067 /** presolve cumulative condition w.r.t. the latest completion times (lct) and the hmax of the effective horizon 10069 * (1) If the earliest start time (est) of a job is larger or equal than hmax, the corresponding job can be removed 10070 * form the constraint. This is the case since it cannot effect any assignment within the effective horizon 10072 * (2) If the earliest completion time (ect) of a job is larger or equal than hmax it follows that the this jobs can run 10073 * before the effective horizon or it overlaps with the effective horizon such that hmax in included. Hence, the 10076 * (3) If the latest start time (lst) of a job is larger or equal than hmax, the cumulative is the only one 10077 * locking the corresponding variable up, and the objective coefficient of the start time variable is not 10080 * (4) If the latest completion time (lct) of job is larger than the hmax, the cumulative is the only one locking the 10081 * corresponding variable up, and the objective coefficient of the start time variable is not positive, than 10082 * removing the values {hmax - p_j, ..., lst-1} form variable domain is dual feasible (p_j is the processing time 10085 * (5) If the latest completion time (lct) of job is smaller than the largerst latest start time of all other jobs 10086 * (lets denote this with maxlst), the cumulative is the only one locking the corresponding variable up, and the 10087 * objective coefficient of the start time variable is not positive, than removing the values {maxlst - p_j + 1, 10088 * ..., lst-1} form variable domain is dual feasible (p_j is the processing time of the corresponding job). 10090 * @note That method does not remove any variable form the arrays. It only marks the variables which are irrelevant for 10104 SCIP_Bool* irrelevants, /**< array mark those variables which are irrelevant for the cumulative condition */ 10105 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */ 10137 SCIPdebugMessage("check for irrelevant variable for cumulative condition (hmax %d) w.r.t. latest completion time\n", hmax); 10176 /* collect earlier start time (est), earlier completion time (ect), latest start time (lst), and latest completion 10195 /* (1) check if the job runs completely after the effective horizon; if so the job can be removed form the 10205 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nirrelevantjobs++ ); 10212 /* (2) check if the jobs overlaps with the time point hmax if it overlaps at all with the effective horizon; if 10222 SCIPdebugMessage(" variables <%s>[%d,%d] with duration <%d> is irrelevant due to no down lock\n", 10228 /* for the statistic we count the number of jobs which always run during the effective horizon */ 10247 /* (3) check if the job can start after the effective horizon finishes; if so and the job can be fixed to its 10248 * latest start time (which implies that it starts after the effective horizon finishes), the job can be 10252 /* job can be removed from the constraint only if the integer start time variable can be fixed to its upper 10263 SCIPdebugMessage(" variable <%s>[%d,%d] with duration <%d> is irrelevant due to dual fixing wrt LCT\n", 10266 /* after fixing the start time variable to its upper bound, the (new) latest start time should be greather or equal ti hmax */ 10282 /* check if the cumulative constraint is the only one looking this variable down and if the objective function 10304 /* for the statistic we count the number of jobs which are dual fixed due the information of all cumulative 10313 /* In the current version SCIP, variable domains are single intervals. Meaning that domain holes or not 10314 * representable. To retrieve a potential dual reduction we using probing to check both branches. If one 10318 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs, 10385 /* remove variables from the cumulative constraint which are marked to be deleted; we need to that in the reverse 10425 /** stores all demands which are smaller than the capacity of those jobs that are running at 'curtime' */ 10465 /* check the end time of this job is larger than the curtime; in this case the job is still running */ 10482 /** this method creates a row for time point curtime which insures the capacity restriction of the cumulative 10515 SCIP_CALL( collectDemands(scip, consdata, startindices, curtime, nstarted, nfinished, &demands, &ndemands) ); 10527 SCIP_CALL( SCIPsolveKnapsackExactly(scip, ndemands, demands, profits, (SCIP_Longint)consdata->capacity, 10557 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */ 10558 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */ 10578 /* if no activities are associated with this cumulative or the capacity is 1, then this constraint is redundant */ 10607 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars); 10610 addEndingJobDemands(consdata, curtime, endtimes, endindices, &freecapacity, &endindex, nvars); 10626 SCIP_CALL( getHighestCapacityUsage(scip, cons, startindices, curtime, j+1, endindex, &newcapacity) ); 10633 /* also those points in time, where the capacity limit is not exceeded, must be taken into account */ 10640 /* capacity cannot be decreased if the demand sum over more than one job equals the capacity */ 10730 if( mindemand + consdata->demands[j] > consdata->capacity && consdata->demands[j] < consdata->capacity ) 10732 SCIPdebugMessage("+-+-+-+-+-+change demand of var<%s> from %d to capacity %d\n", SCIPvarGetName(consdata->vars[j]), 10758 lct_j = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(consdata->vars[j])) + consdata->durations[j]; 10769 lct_i = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(consdata->vars[i])) + consdata->durations[i]; 10783 SCIPdebugMessage("+-+-+-+-+-+change demand of var<%s> from %d to capacity %d\n", SCIPvarGetName(consdata->vars[j]), 10793 SCIPdebugMessage("+-+-+-+-+-+changed %d coefficients of variables of cumulative constraint<%s>\n", 10865 SCIP_CALL( SCIPcreateVar(scip, &aggrvar, name, (SCIP_Real)(est+shift), (SCIP_Real)lst, 0.0, SCIPvarGetType(var), 10868 SCIP_CALL( SCIPaggregateVars(scip, var, aggrvar, 1.0, -1.0, (SCIP_Real)shift, &infeasible, &redundant, &aggregated) ); 10879 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, consdata->downlocks[v], consdata->uplocks[v]) ); 10942 /* add all jobs which has a demand smaller than one half of the capacity but together with the smallest collected 10963 SCIP_CALL( createConsCumulative(scip, SCIPconsGetName(cons), nvars, vars, durations, demands, 1, consdata->hmin, consdata->hmax, 10984 int* naggrvars, /**< pointer to counter which is increased by the number of deduced variable aggregations */ 11006 /* in case the cumulative constraint is independent of every else, solve the cumulative problem and apply the 11011 SCIP_CALL( solveIndependentCons(scip, cons, conshdlrdata->maxnodes, nchgbds, nfixedvars, ndelconss, cutoff, unbounded) ); 11017 SCIP_CALL( presolveConsEffectiveHorizon(scip, cons, nfixedvars, nchgcoefs, nchgsides, cutoff) ); 11083 { 11092 { 11101 { 11107 if( tcliquegraph->precedencematrix[node1][node2] || tcliquegraph->precedencematrix[node2][node1] ) 11122 { 11135 /* check if the node is adjacent to the given node (nodes and adjacent nodes are ordered by node index) */ 11178 SCIPinfoMessage(scip, NULL, "(%d/%d) ", tcliquegraph->precedencematrix[i][j], tcliquegraph->demandmatrix[i][j]); 11187 /** analyzes if the given variable lower bound condition implies a precedence condition w.r.t. given duration for the 11221 /* if vlbcoef < 1 and ub(vlbvar) <= (duration - vlbconst)/(vlbcoef - 1) -> precedence condition */ 11233 /* if vlbcoef > 1 and lb(vlbvar) >= (duration - vlbconst)/(vlbcoef - 1) -> precedence condition */ 11242 /** analyzes if the given variable upper bound condition implies a precedence condition w.r.t. given duration for the 11266 /** get the corresponding index of the given variables; this in case of an active variable the problem index and for 11308 SCIP_CALL( SCIPreallocBufferArray(scip, &tcliquegraph->precedencematrix[v], size) ); /*lint !e866*/ 11309 SCIP_CALL( SCIPreallocBufferArray(scip, &tcliquegraph->demandmatrix[v], size) ); /*lint !e866*/ 11321 SCIP_CALL( SCIPallocBufferArray(scip, &tcliquegraph->precedencematrix[pos], tcliquegraph->size) ); /*lint !e866*/ 11322 BMSclearMemoryArray(tcliquegraph->precedencematrix[pos], tcliquegraph->nnodes); /*lint !e866*/ 11324 SCIP_CALL( SCIPallocBufferArray(scip, &tcliquegraph->demandmatrix[pos], tcliquegraph->size) ); /*lint !e866*/ 11350 /** use the variables bounds of SCIP to projected variables bound graph into a precedence garph 11352 * Let d be the (assumed) duration of variable x and consider a variable bound of the form b * x + c <= y. This 11353 * variable bounds implies a precedence condition x -> y (meaning job y starts after job x is finished) if: 11408 if( impliesVlbPrecedenceCondition(scip, vbdvars[b], vbdcoefs[b], vbdconsts[b], tcliquegraph->durations[idx2]) ) 11427 if( impliesVubPrecedenceCondition(scip, var, vbdcoefs[b], vbdconsts[b], tcliquegraph->durations[idx1]) ) 11441 /* check if the latest completion time of job1 is smaller than the earliest start time of job2 */ 11442 if( SCIPisLE(scip, SCIPvarGetUbLocal(var) + tcliquegraph->durations[idx1], SCIPvarGetLbLocal(vars[b])) ) 11445 /* check if the latest completion time of job2 is smaller than the earliest start time of job1 */ 11446 if( SCIPisLE(scip, SCIPvarGetUbLocal(vars[b]) + tcliquegraph->durations[idx2], SCIPvarGetLbLocal(var)) ) 11486 /** constructs a non-overlapping graph w.r.t. given durations and available cumulative constraints */ 11527 if( tcliquegraph->durations[idx1] == 0 || tcliquegraph->durations[idx1] > consdata->durations[i] ) 11561 if( tcliquegraph->durations[idx2] == 0 || tcliquegraph->durations[idx2] > consdata->durations[j] ) 11564 SCIPdebugMessage(" *** variable <%s> and variable <%s>\n", SCIPvarGetName(vars[i]), SCIPvarGetName(vars[j])); 11580 /** constructs a conflict set graph (undirected) which contains for each job a node and edge if the corresponding pair 11594 /* use the variables bounds of SCIP to project the variables bound graph inot a precedence graph */ 11597 /* compute the transitive closure of the precedence graph and the number of in and out arcs */ 11598 transitiveClosure(tcliquegraph->precedencematrix, tcliquegraph->ninarcs, tcliquegraph->noutarcs, tcliquegraph->nnodes); 11638 SCIP_CALL( SCIPcreateConsCumulative(scip, &cons, name, ncliquenodes, vars, durations, demands, 1, 11689 /* create a hash table to store all start time variables which are already covered by at least one clique */ 11731 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique, 11736 SCIPdebugMessage("tree nodes %d clique size %d (weight %d, status %d)\n", ntreenodes, ncliquenodes, cliqueweight, tcliquestatus); 11775 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->naddeddisjunctives += nconss ); 11787 int distance /**< minimum distance between the start time of the job corresponding to var and the job corresponding to vbdvar */ 11793 SCIP_CALL( SCIPcreateConsVarbound(scip, &cons, name, var, vbdvar, -1.0, -SCIPinfinity(scip), -(SCIP_Real)distance, 11805 /** compute a minimum distance between the start times of the two given jobs and post it as variable bound constraint */ 11837 /* get latest completion time (lct) of the source and the earliest start time (est) of sink */ 11838 lct = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[source])) + tcliquegraph->durations[source]; 11857 else if( tcliquegraph->precedencematrix[source][i] && tcliquegraph->precedencematrix[i][sink] ) 11875 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique, 11888 /* the minimum distance between the start times of source job and the sink job is the clique weight plus the 11904 * for each arc of the transitive closure of the precedence graph, we are computing a minimum distance between the 11966 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->naddedvarbounds += nconss ); 12006 /**@todo For the test sets, which we are considere, the durations are independent of the cumulative 12007 * constaints. Meaning each job has a fixed duration which is the same for all cumulative constraints. In 12008 * general this is not the case. Therefore, the question would be which duration should be used? 12126 /** construct an incompatibility graph and search for precedence constraints (variables bounds) and unary cumulative 12167 /** compute the constraint signature which is used to detect constraints which contain potentially the same set of variables */ 12185 consdata->signature |= ((unsigned int)1 << ((unsigned int)SCIPvarGetIndex(vars[v]) % (sizeof(unsigned int) * 8))); 12191 /** index comparison method of linear constraints: compares two indices of the variable set in the linear constraint */ 12409 if( demands[i] + demands[j] > capacity && SCIPconvertRealToInt(scip, vbdconsts[b]) < durations[j] ) 12415 SCIPdebugMessage("<%s>[%d] + %g <= <%s>[%d]\n", SCIPvarGetName(vbdvars[b]), durations[j], vbdconsts[b], SCIPvarGetName(var), durations[i]); 12423 SCIP_CALL( SCIPaddVarVlb(scip, var, vbdvars[b], 1.0, (SCIP_Real) durations[j], &infeasible, &nlocalbdchgs) ); 12466 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */ 12482 SCIPstatisticPrintf("time-table: lb=%" SCIP_LONGINT_FORMAT ", ub=%" SCIP_LONGINT_FORMAT ", cutoff=%" SCIP_LONGINT_FORMAT "\n", 12484 SCIPstatisticPrintf("edge-finder: lb=%" SCIP_LONGINT_FORMAT ", ub=%" SCIP_LONGINT_FORMAT ", cutoff=%" SCIP_LONGINT_FORMAT "\n", 12486 SCIPstatisticPrintf("overload: time-table=%" SCIP_LONGINT_FORMAT " time-time edge-finding=%" SCIP_LONGINT_FORMAT "\n", 12499 /** presolving initialization method of constraint handler (called when presolving is about to begin) */ 12513 /* remove jobs which have a duration or demand of zero (zero energy) or lay outside the effective horizon [hmin, 12523 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */ 12545 SCIPstatisticPrintf("@11 added variables bounds constraints %d\n", conshdlrdata->naddedvarbounds); 12546 SCIPstatisticPrintf("@22 added disjunctive constraints %d\n", conshdlrdata->naddeddisjunctives); 12561 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */ 12593 /* if constraint belongs to transformed problem space, drop bound change events on variables */ 12640 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata, 12641 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons), 12644 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) ); 12655 { 12690 { 12836 SCIPdebugMessage("LP enforcing %d useful cumulative constraints of %d constraints\n", nusefulconss, nconss); 13003 &nchgbds, &naggrvars, &nchgbds, &ndelconss, &nchgbds, &nchgbds, &nchgbds, &cutoff, &cutoff) ); 13015 SCIP_CALL( propagateCons(scip, cons, conshdlrdata, SCIP_PRESOLTIMING_ALWAYS, &nchgbds, &ndelconss, &cutoff) ); 13023 SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata, SCIP_PRESOLTIMING_ALWAYS, &nchgbds, &ndelconss, &cutoff) ); 13030 SCIP_CALL( propagateAllConss(scip, conshdlrdata, conss, nconss, TRUE, &nchgbds, &cutoff, NULL) ); 13041 SCIPdebugMessage("delete (locally) %d constraints and changed %d variable bounds\n", ndelconss, nchgbds); 13094 /* remove jobs which have a duration or demand of zero (zero energy) or lay outside the effective horizon [hmin, 13103 nfixedvars, naggrvars, nchgbds, ndelconss, naddconss, nchgcoefs, nchgsides, &cutoff, &unbounded) ); 13116 /* in the first round we create a disjunctive constraint containing those jobs which cannot run in parallel */ 13129 SCIP_CALL( propagateCons(scip, cons, conshdlrdata, presoltiming, nchgbds, ndelconss, &cutoff) ); 13133 if( !cutoff && !unbounded && conshdlrdata->dualpresolve && SCIPallowDualReds(scip) && nconss > 1 && (presoltiming & SCIP_PRESOLTIMING_FAST) != 0 ) 13144 /* combine different source and detect disjunctive constraints and variable bound constraints to improve the 13151 if( !cutoff && conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 ) 13164 || *nchgcoefs > oldnchgcoefs || *nupgdconss > oldnupgdconss || *ndelconss > oldndelconss || *naddconss > oldnaddconss ) 13195 SCIPdebugMessage("resolve propagation: variable <%s>, cumulative constraint <%s> (capacity %d, propagation %d, H=[%d,%d))\n", 13196 SCIPvarGetName(infervar), SCIPconsGetName(cons), consdata->capacity, inferInfoGetProprule(intToInferInfo(inferinfo)), 13201 infervar, intToInferInfo(inferinfo), boundtype, bdchgidx, relaxedbd, conshdlrdata->usebdwidening, NULL, result) ); 13214 SCIPdebugMessage("lock cumulative constraint <%s> with nlockspos = %d, nlocksneg = %d\n", SCIPconsGetName(cons), nlockspos, nlocksneg); 13288 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &vars[v], varmap, consmap, global, valid) ); 13303 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 13374 SCIPdebugMessage("parse job <%s>, duration %d, demand %d\n", SCIPvarGetName(var), duration, demand); 13402 SCIP_CALL( SCIPcreateConsCumulative(scip, cons, name, nvars, vars, durations, demands, capacity, 13403 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 13442 /** constraint method of constraint handler which returns the number of variables (if possible) */ 13507 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecCumulative, NULL) ); 13536 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropCumulative, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, 13539 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpCumulative, consSepasolCumulative, CONSHDLR_SEPAFREQ, 13587 "constraints/" CONSHDLR_NAME "/fillbranchcands", "should branching candidates be added to storage?", 13610 "number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit)?", 13613 "constraints/" CONSHDLR_NAME "/detectdisjunctive", "search for conflict set via maximal cliques to detect disjunctive constraints", 13616 "constraints/" CONSHDLR_NAME "/detectvarbounds", "search for conflict set via maximal cliques to detect variable bound constraints", 13621 "constraints/" CONSHDLR_NAME "/usebdwidening", "should bound widening be used during the conflict analysis?", 13633 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 13655 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 13657 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 13678 SCIP_CALL( consdataCreate(scip, &consdata, vars, NULL, durations, demands, nvars, capacity, 0, INT_MAX, check) ); 13703 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the 13704 * method SCIPcreateConsCumulative(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h 13706 * @see SCIPcreateConsCumulative() for information about the basic constraint flag configuration 13708 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 13715 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 13723 SCIP_CALL( SCIPcreateConsCumulative(scip, cons, name, nvars, vars, durations, demands, capacity, 13922 /** check for the given starting time variables with their demands and durations if the cumulative conditions for the 13929 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 13943 SCIP_CALL( checkCumulativeCondition(scip, sol, nvars, vars, durations, demands, capacity, hmin, hmax, 13967 /** searches for a time point within the cumulative condition were the cumulative condition can be split */ 13971 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 13980 SCIP_CALL( computeEffectiveHorizonCumulativeCondition(scip, nvars, vars, durations, demands, capacity, 13986 /** presolve cumulative condition w.r.t. effective horizon by detecting irrelevant variables */ 13997 SCIP_Bool* irrelevants, /**< array mark those variables which are irrelevant for the cumulative condition */ 14007 SCIP_CALL( presolveConsEst(scip, nvars, vars, durations, hmin, hmax, downlocks, uplocks, cons, 14011 SCIP_CALL( presolveConsLct(scip, nvars, vars, durations, hmin, hmax, downlocks, uplocks, cons, 14022 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 14031 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 14079 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */ 14081 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */ 14082 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */ 14085 SCIP_CALL( respropCumulativeCondition(scip, nvars, vars, durations, demands, capacity, hmin, hmax, 14086 infervar, intToInferInfo(inferinfo), boundtype, bdchgidx, relaxedbd, TRUE, explanation, result) ); 14144 SCIPgmlWriteNode(file, (unsigned int)(size_t)var, SCIPvarGetName(var), "rectangle", color, NULL); 14163 SCIPgmlWriteArc(file, (unsigned int)(size_t)vbdvars[b], (unsigned int)(size_t)var, NULL, NULL); 14175 SCIPgmlWriteArc(file, (unsigned int)(size_t)var, (unsigned int)(size_t)vbdvars[b], NULL, NULL); 14195 SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)) /**< method to use an individual cumulative condition */ 14219 * @note If the problem was solved to the earliest start times (ests) and latest start times (lsts) array contain the 14220 * solution values; If the problem was not solved these two arrays contain the global bounds at the time the sub 14228 SCIP_Real* objvals, /**< array of objective coefficients for each job (linear objective function), or NULL if none */ 14236 SCIP_Longint maxnodes, /**< maximum number of branch-and-bound nodes to solve the single cumulative constraint (-1: no limit) */ 14266 /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */ 14269 SCIP_CALL( conshdlrdata->solveCumulative(njobs, ests, lsts, objvals, durations, demands, capacity, 14276 /** creates the worst case resource profile, that is, all jobs are inserted with the earliest start and latest 14283 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */ 14313 /* add each job with its earliest start and latest completion time into the resource profile */ 14338 SCIP_CALL( SCIPprofileInsertCore(profile, impliedest, impliedlct, copydemands[v], &pos, &infeasible) ); 14357 /** computes w.r.t. the given worst case resource profile the first time point where the given capacity can be violated */ 14387 /** computes w.r.t. the given worst case resource profile the first time point where the given capacity is satisfied for sure */
static SCIP_RETCODE consdataCatchEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr) Definition: cons_cumulative.c:1757 SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed) Definition: scip.c:22777 SCIP_RETCODE SCIPbtnodeCreate(SCIP_BT *tree, SCIP_BTNODE **node, void *dataptr) Definition: misc.c:6639 SCIP_RETCODE SCIPsetSolveCumulative(SCIP *scip, SCIP_DECL_SOLVECUMULATIVE((*solveCumulative))) Definition: cons_cumulative.c:14194 Definition: type_paramset.h:63 Definition: type_result.h:33 SCIP_Real SCIPgetRowSolFeasibility(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol) Definition: scip.c:28308 SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name) Definition: scip.c:5878 Definition: type_result.h:37 SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans))) Definition: scip.c:5588 static SCIP_RETCODE propagateAllConss(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, SCIP_Bool local, int *nfixedvars, SCIP_Bool *cutoff, SCIP_Bool *branched) Definition: cons_cumulative.c:7935 Definition: struct_var.h:97 static TCLIQUE_GETNNODES(tcliqueGetnnodesClique) Definition: cons_cumulative.c:11083 static int computeEnergyContribution(SCIP_BTNODE *node) Definition: cons_cumulative.c:6328 SCIP_RETCODE SCIPsolveCumulative(SCIP *scip, int njobs, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Real *objvals, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint maxnodes, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *error) Definition: cons_cumulative.c:14224 static SCIP_DECL_CONSGETVARS(consGetVarsCumulative) Definition: cons_cumulative.c:13423 static SCIP_RETCODE consdataDropAllEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr) Definition: cons_cumulative.c:1802 static PROPRULE inferInfoGetProprule(INFERINFO inferinfo) Definition: cons_cumulative.c:300 static SCIP_RETCODE checkCumulativeCondition(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *violated, SCIP_CONS *cons, SCIP_Bool printreason) Definition: cons_cumulative.c:2230 SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated) Definition: scip.c:22886 constraint handler for cumulative constraints static SCIP_RETCODE propagateEdgeFinding(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, SCIP_Bool *initialized, SCIP_Bool *explanation, int *nchgbds, SCIP_Bool *cutoff) Definition: cons_cumulative.c:7037 Definition: struct_scip.h:53 SCIP_RETCODE SCIPprofileDeleteCore(SCIP_PROFILE *profile, int left, int right, int demand) Definition: misc.c:5268 static SCIP_RETCODE computeMinDistance(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int source, int sink, int *naddconss) Definition: cons_cumulative.c:11808 SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element) Definition: misc.c:1567 static void consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file) Definition: cons_cumulative.c:2066 static SCIP_DECL_CONSENFOPS(consEnfopsCumulative) Definition: cons_cumulative.c:12908 static SCIP_RETCODE analyzeConflictOverload(SCIP *scip, SCIP_BTNODE **leaves, int capacity, int nleaves, int est, int lct, int reportedenergy, SCIP_Bool propest, int shift, SCIP_Bool usebdwidening, SCIP_Bool *initialized, SCIP_Bool *explanation) Definition: cons_cumulative.c:6382 SCIP_Bool SCIPexistsConsLinking(SCIP *scip, SCIP_VAR *intvar) Definition: cons_linking.c:3324 static SCIP_RETCODE createCoverCutsTimepoint(SCIP *scip, SCIP_CONS *cons, int *startvalues, int time) Definition: cons_cumulative.c:8007 SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata) Definition: scip.c:15737 static SCIP_RETCODE createCapacityRestrictionIntvars(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool lower) Definition: cons_cumulative.c:8890 SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value) Definition: scip.c:4154 static void addEndingJobDemands(SCIP_CONSDATA *consdata, int curtime, int *endtimes, int *endindices, int *freecapacity, int *idx, int nvars) Definition: cons_cumulative.c:3368 SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop))) Definition: scip.c:5634 SCIP_RETCODE SCIPtransformConss(SCIP *scip, int nconss, SCIP_CONS **conss, SCIP_CONS **transconss) Definition: scip.c:25401 SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa) Definition: scip.c:5246 void SCIPgmlWriteArc(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color) Definition: misc.c:437 SCIP_RETCODE SCIPpresolveCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff) Definition: cons_cumulative.c:13988 Definition: type_result.h:49 static int computeOverlap(int begin, int end, int est, int lst, int duration) Definition: cons_cumulative.c:2762 static SCIP_RETCODE constraintNonOverlappingGraph(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss) Definition: cons_cumulative.c:11489 static SCIP_RETCODE analyzeEnergyRequirement(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int begin, int end, SCIP_VAR *infervar, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool usebdwidening, SCIP_Bool *explanation) Definition: cons_cumulative.c:2799 static void initializeLocks(SCIP_CONSDATA *consdata, SCIP_Bool locked) Definition: cons_cumulative.c:1824 Definition: type_result.h:38 Definition: type_set.h:35 static SCIP_RETCODE createDisjuctiveCons(SCIP *scip, SCIP_CONS *cons, int *naddconss) Definition: cons_cumulative.c:10895 static SCIP_RETCODE solveIndependentCons(SCIP *scip, SCIP_CONS *cons, SCIP_Longint maxnodes, int *nchgbds, int *nfixedvars, int *ndelconss, SCIP_Bool *cutoff, SCIP_Bool *unbounded) Definition: cons_cumulative.c:3660 SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy))) Definition: scip.c:5334 static void updateKeyOnTrace(SCIP_BTNODE *node, SCIP_Real key) Definition: cons_cumulative.c:5761 void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor) Definition: misc.c:295 Definition: struct_var.h:196 Definition: type_stat.h:55 static SCIP_RETCODE presolveConsEst(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff) Definition: cons_cumulative.c:9810 static SCIP_RETCODE computePeak(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, int *timepoint) Definition: cons_cumulative.c:3397 int * SCIPgetDemandsCumulative(SCIP *scip, SCIP_CONS *cons) Definition: cons_cumulative.c:13903 static void transitiveClosure(SCIP_Bool **adjmatrix, int *ninarcs, int *noutarcs, int nnodes) Definition: cons_cumulative.c:11457 SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip) Definition: scip.c:24320 SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant) Definition: scip.c:17429 SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars))) Definition: scip.c:5818 void SCIPbtnodeSetRightchild(SCIP_BTNODE *node, SCIP_BTNODE *right) Definition: misc.c:6909 static SCIP_Bool isConsIndependently(SCIP *scip, SCIP_CONS *cons) Definition: cons_cumulative.c:3621 static SCIP_RETCODE applyAlternativeBoundsFixing(SCIP *scip, SCIP_VAR **vars, int nvars, int *alternativelbs, int *alternativeubs, int *downlocks, int *uplocks, int *nfixedvars, SCIP_Bool *cutoff) Definition: cons_cumulative.c:7781 SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype) Definition: scip.c:15817 static SCIP_RETCODE collectIntVars(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR ***activevars, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool lower, int *lhs) Definition: cons_cumulative.c:612 static SCIP_RETCODE fixIntegerVariableLb(SCIP *scip, SCIP_VAR *var, SCIP_Bool downlock, int *nfixedvars) Definition: cons_cumulative.c:9413 SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize) Definition: misc.c:2057 Definition: struct_misc.h:195 SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value) Definition: scip.c:4046 static SCIP_RETCODE consdataFreeRows(SCIP *scip, SCIP_CONSDATA **consdata) Definition: cons_cumulative.c:1966 SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata) Definition: scip.c:7778 static SCIP_RETCODE checkOverloadViaThetaTree(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, SCIP_Bool propest, SCIP_Bool *initialized, SCIP_Bool *explanation, int *nchgbds, SCIP_Bool *cutoff) Definition: cons_cumulative.c:6734 SCIP_RETCODE SCIPvisualizeConsCumulative(SCIP *scip, SCIP_CONS *cons) Definition: cons_cumulative.c:14093 SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval) Definition: scip.c:33396 int SCIPgetNVarsCumulative(SCIP *scip, SCIP_CONS *cons) Definition: cons_cumulative.c:13840 static SCIP_DECL_CONSEXITSOL(consExitsolCumulative) Definition: cons_cumulative.c:12564 Definition: type_var.h:53 static void subtractStartingJobDemands(SCIP_CONSDATA *consdata, int curtime, int *starttimes, int *startindices, int *freecapacity, int *idx, int nvars) Definition: cons_cumulative.c:3328 SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse))) Definition: scip.c:5795 static SCIP_RETCODE presolveConsEffectiveHorizon(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *nchgcoefs, int *nchgsides, SCIP_Bool *cutoff) Definition: cons_cumulative.c:10347 SCIP_RETCODE SCIPcreateConsCumulative(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_cumulative.c:13629 static SCIP_RETCODE removeIrrelevantJobs(SCIP *scip, SCIP_CONS *cons) Definition: cons_cumulative.c:9150 static SCIP_RETCODE applyProbingVar(SCIP *scip, SCIP_VAR **vars, int nvars, int probingpos, SCIP_Real leftub, SCIP_Real rightlb, SCIP_Real *leftimpllbs, SCIP_Real *leftimplubs, SCIP_Real *leftproplbs, SCIP_Real *leftpropubs, SCIP_Real *rightimpllbs, SCIP_Real *rightimplubs, SCIP_Real *rightproplbs, SCIP_Real *rightpropubs, int *nfixedvars, SCIP_Bool *success, SCIP_Bool *cutoff) Definition: cons_cumulative.c:7450 static SCIP_RETCODE presolveCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PRESOLTIMING presoltiming, int *nfixedvars, int *nchgbds, int *ndelconss, int *naddconss, int *nchgcoefs, int *nchgsides, SCIP_Bool *cutoff, SCIP_Bool *unbounded) Definition: cons_cumulative.c:10978 SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value) Definition: scip.c:4109 SCIP_RETCODE SCIPcheckCumulativeCondition(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *violated, SCIP_CONS *cons, SCIP_Bool printreason) Definition: cons_cumulative.c:13926 static SCIP_RETCODE strengthenVarbounds(SCIP *scip, SCIP_CONS *cons, int *nchgbds, int *naddconss) Definition: cons_cumulative.c:12347 static SCIP_RETCODE getNodeIdx(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_VAR *var, int *idx) Definition: cons_cumulative.c:11271 static void conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata) Definition: cons_cumulative.c:1736 void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len) Definition: type_stat.h:43 SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after) Definition: var.c:15737 static SCIP_RETCODE deleteLambdaLeaf(SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node) Definition: cons_cumulative.c:5793 SCIP_RETCODE SCIPprofileInsertCore(SCIP_PROFILE *profile, int left, int right, int demand, int *pos, SCIP_Bool *infeasible) Definition: misc.c:5238 SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata) Definition: scip.c:3601 SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var) Definition: scip.c:34983 Definition: type_result.h:40 static SCIP_RETCODE separateCoverCutsCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff) Definition: cons_cumulative.c:8774 tclique user interface SCIP_RETCODE SCIPcreateConsBasicKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity) Definition: cons_knapsack.c:13198 static SCIP_RETCODE createCoreProfile(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) Definition: cons_cumulative.c:7209 void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin) Definition: misc.c:2116 static SCIP_RETCODE createNodedata(SCIP *scip, SCIP_NODEDATA **nodedata) Definition: cons_cumulative.c:5634 SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) Definition: cons_setppc.c:9063 SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file) Definition: scip.c:26237 SCIP_RETCODE SCIPsplitCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *hmin, int *hmax, int *split) Definition: cons_cumulative.c:13969 SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible) Definition: scip.c:30967 int SCIPgetCapacityCumulative(SCIP *scip, SCIP_CONS *cons) Definition: cons_cumulative.c:13861 static void createSelectedSortedEventpointsSol(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, int *starttimes, int *endtimes, int *startindices, int *endindices, int *nvars, SCIP_Bool lower) Definition: cons_cumulative.c:777 static SCIP_DECL_CONSINITLP(consInitlpCumulative) Definition: cons_cumulative.c:12655 static SCIP_DECL_CONSPRESOL(consPresolCumulative) Definition: cons_cumulative.c:13053 SCIP_RETCODE SCIPcreateWorstCaseProfile(SCIP *scip, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands) Definition: cons_cumulative.c:14280 static SCIP_RETCODE deleteTrivilCons(SCIP *scip, SCIP_CONS *cons, int *ndelconss, SCIP_Bool *cutoff) Definition: cons_cumulative.c:9108 SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree))) Definition: scip.c:5359 static SCIP_RETCODE respropCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, INFERINFO inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool usebdwidening, SCIP_Bool *explanation, SCIP_RESULT *result) Definition: cons_cumulative.c:3086 static SCIP_RETCODE removeOversizedJobs(SCIP *scip, SCIP_CONS *cons, int *nchgbds, int *nchgcoefs, int *naddconss, SCIP_Bool *cutoff) Definition: cons_cumulative.c:9320 SCIP_RETCODE SCIPcreateConsVarbound(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_varbound.c:4545 static SCIP_RETCODE createConsCumulative(SCIP *scip, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_cumulative.c:9652 static SCIP_RETCODE adjustOversizedJobBounds(SCIP *scip, SCIP_CONSDATA *consdata, int pos, int *nchgbds, int *naddconss, SCIP_Bool *cutoff) Definition: cons_cumulative.c:9214 Definition: type_stat.h:34 SCIP_RETCODE SCIPinferVarUbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20572 Definition: type_stat.h:35 SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr) Definition: misc.c:1480 static SCIP_DECL_SOLVECUMULATIVE(solveCumulativeViaScipCp) Definition: cons_cumulative.c:1225 static SCIP_RETCODE coretimesUpdateUb(SCIP *scip, SCIP_VAR *var, int duration, int demand, int capacity, SCIP_CONS *cons, SCIP_PROFILE *profile, int idx, int *nchgbds) Definition: cons_cumulative.c:4084 SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success) Definition: scip.c:24720 static void freeTcliqueGraph(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph) Definition: cons_cumulative.c:12102 Definition: struct_sol.h:50 static void createSortedEventpointsSol(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *starttimes, int *endtimes, int *startindices, int *endindices) Definition: cons_cumulative.c:734 static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr) Definition: cons_cumulative.c:1691 SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata) Definition: scip.c:3547 SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin) Definition: misc.c:2159 SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr) Definition: scip.c:16156 SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name) Definition: scip.c:9077 int SCIPcomputeHmax(SCIP *scip, SCIP_PROFILE *profile, int capacity) Definition: cons_cumulative.c:14389 static SCIP_RETCODE updateEnvelop(SCIP *scip, SCIP_BTNODE *node) Definition: cons_cumulative.c:5671 SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr) Definition: cons.c:3917 static SCIP_RETCODE separateConsBinaryRepresentation(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff) Definition: cons_cumulative.c:8702 static SCIP_RETCODE findPrecedenceConss(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int *naddconss) Definition: cons_cumulative.c:11909 static SCIP_DECL_CONSCHECK(consCheckCumulative) Definition: cons_cumulative.c:12937 SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos) Definition: scip.c:36622 int SCIPcomputeHmin(SCIP *scip, SCIP_PROFILE *profile, int capacity) Definition: cons_cumulative.c:14359 static SCIP_RETCODE getHighestCapacityUsage(SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, int *bestcapacity) Definition: cons_cumulative.c:10487 Definition: struct_misc.h:101 static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR **vars, SCIP_CONS **linkingconss, int *durations, int *demands, int nvars, int capacity, int hmin, int hmax, SCIP_Bool check) Definition: cons_cumulative.c:1844 SCIP_RETCODE SCIPcreateConsKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_knapsack.c:13130 Constraint handler for knapsack constraints of the form , x binary and . SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success) Definition: scip.c:1781 int * SCIPgetValsLinking(SCIP *scip, SCIP_CONS *cons) Definition: cons_linking.c:3450 Definition: type_stat.h:36 static SCIP_RETCODE collectBranchingCands(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, int *nbranchcands) Definition: cons_cumulative.c:3482 static SCIP_RETCODE findCumulativeConss(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int *naddconss) Definition: cons_cumulative.c:11655 static SCIP_RETCODE propagateTTEF(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) Definition: cons_cumulative.c:5277 Definition: type_result.h:35 static SCIP_RETCODE tightenUbTTEF(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *var, int duration, int demand, int est, int lst, int lct, int begin, int end, int energy, int *bestub, int *inferinfos, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) Definition: cons_cumulative.c:4470 Definition: struct_cons.h:36 static SCIP_RETCODE enforceSolution(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool branch, SCIP_RESULT *result) Definition: cons_cumulative.c:3569 static SCIP_RETCODE projectVbd(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph) Definition: cons_cumulative.c:11362 static SCIP_RETCODE createTcliqueGraph(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph) Definition: cons_cumulative.c:12021 SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup) Definition: scip.c:19526 #define SCIPfreeBlockMemoryArrayNull(scip, ptr, num) Definition: scip.h:20574 void SCIPsortIntInt(int *intarray1, int *intarray2, int len) SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1) Definition: scip.c:25300 Definition: struct_cons.h:116 Definition: type_retcode.h:42 void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) void SCIPbtnodeSetLeftchild(SCIP_BTNODE *node, SCIP_BTNODE *left) Definition: misc.c:6895 static SCIP_RETCODE collectBinaryVars(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR ***vars, int **coefs, int *nvars, int *startindices, int curtime, int nstarted, int nfinished) Definition: cons_cumulative.c:514 static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyCumulative) Definition: cons_cumulative.c:12451 SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after) Definition: var.c:15859 Definition: type_lp.h:47 Definition: type_stat.h:52 SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming) Definition: scip.c:5527 SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row) Definition: scip.c:28151 Definition: type_result.h:36 static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata) Definition: cons_cumulative.c:2017 void SCIPstrCopySection(const char *str, char startchar, char endchar, char *token, int size, char **endptr) Definition: misc.c:8275 static void traceLambdaEnvelop(SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy) Definition: cons_cumulative.c:6262 static SCIP_RETCODE computeEffectiveHorizon(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss, int *nchgsides) Definition: cons_cumulative.c:9706 static int computeEstOmegaset(SCIP *scip, int duration, int demand, int capacity, int est, int lct, int energy) Definition: cons_cumulative.c:6492 SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2) Definition: scip.c:41907 SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre))) Definition: scip.c:5503 #define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum) Definition: scip.h:20562 Definition: type_var.h:44 static SCIP_RETCODE propagateCumulativeCondition(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PRESOLTIMING presoltiming, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *redundant, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) Definition: cons_cumulative.c:7300 SCIP_RETCODE SCIPsetHminCumulative(SCIP *scip, SCIP_CONS *cons, int hmin) Definition: cons_cumulative.c:13731 static SCIP_RETCODE coretimesUpdateLb(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, SCIP_PROFILE *profile, int idx, int *nchgbds, SCIP_Bool usebdwidening, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *infeasible) Definition: cons_cumulative.c:3931 static SCIP_RETCODE createCumulativeCons(SCIP *scip, const char *name, TCLIQUE_GRAPH *tcliquegraph, int *cliquenodes, int ncliquenodes) Definition: cons_cumulative.c:11609 Definition: type_retcode.h:33 void tcliqueMaxClique(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_WEIGHT maxfirstnodeweight, TCLIQUE_WEIGHT minweight, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, int *ntreenodes, TCLIQUE_STATUS *status) Definition: tclique_branch.c:1000 static SCIP_RETCODE createCoverCuts(SCIP *scip, SCIP_CONS *cons) Definition: cons_cumulative.c:8262 Definition: type_stat.h:33 static int computeTotalEnergy(int *durations, int *demands, int njobs) Definition: cons_cumulative.c:1199 void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len) SCIP_RETCODE SCIPsolveKnapsackExactly(SCIP *scip, int nitems, SCIP_Longint *weights, SCIP_Real *profits, SCIP_Longint capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval, SCIP_Bool *success) Definition: cons_knapsack.c:949 SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming) Definition: scip.c:5292 static SCIP_RETCODE propagateLbTTEF(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, int *newlbs, int *newubs, int *lbinferinfos, int *ubinferinfos, int *ects, int *flexenergies, int *perm, int *ests, int *lcts, int *coreEnergyAfterEst, int *coreEnergyAfterLct, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) Definition: cons_cumulative.c:4935 SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata) Definition: scip.c:5192 void SCIPsortDownIntIntInt(int *intarray1, int *intarray2, int *intarray3, int len) SCIP_RETCODE SCIPpropCumulativeCondition(SCIP *scip, SCIP_PRESOLTIMING presoltiming, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) Definition: cons_cumulative.c:14019 static TCLIQUE_SELECTADJNODES(tcliqueSelectadjnodesClique) Definition: cons_cumulative.c:11122 Definition: type_result.h:42 SCIP_RETCODE SCIPprofileCreate(SCIP_PROFILE **profile, int capacity) Definition: misc.c:4965 Definition: cons_cumulative.c:255 SCIP_RETCODE SCIPaddCoefKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight) Definition: cons_knapsack.c:13217 static SCIP_RETCODE consCapacityConstraintsFinder(SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss) Definition: cons_cumulative.c:8494 static void collectDataTTEF(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int hmin, int hmax, int *permests, int *ests, int *permlcts, int *lcts, int *ects, int *lsts, int *flexenergies) Definition: cons_cumulative.c:4289 SCIP_RETCODE SCIPcreateConsBounddisjunction(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_bounddisjunction.c:3036 static SCIP_RETCODE consCheckRedundancy(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *redundant) Definition: cons_cumulative.c:7086 SCIP_RETCODE SCIPapplyProbingVar(SCIP *scip, SCIP_VAR **vars, int nvars, int probingpos, SCIP_BOUNDTYPE boundtype, SCIP_Real bound, int maxproprounds, SCIP_Real *impllbs, SCIP_Real *implubs, SCIP_Real *proplbs, SCIP_Real *propubs, SCIP_Bool *cutoff) Definition: prop_probing.c:1181 SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars) Definition: scip.c:17116 SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var) Definition: scip.c:23119 constraint handler for linking binary variables to an integer variable SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20193 SCIP_BTNODE * SCIPbtnodeGetRightchild(SCIP_BTNODE *node) Definition: misc.c:6778 static SCIP_RETCODE propagateUbTTEF(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, int *newlbs, int *newubs, int *lbinferinfos, int *ubinferinfos, int *lsts, int *flexenergies, int *perm, int *ests, int *lcts, int *coreEnergyAfterEst, int *coreEnergyAfterLct, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) Definition: cons_cumulative.c:4584 static void traceThetaEnvelop(SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy) Definition: cons_cumulative.c:6144 SCIP_RETCODE SCIPgetBinvarsLinking(SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***binvars, int *nbinvars) Definition: cons_linking.c:3385 SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre))) Definition: scip.c:5479 SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: scip.c:24772 SCIP_RETCODE SCIPsetConsEnforced(SCIP *scip, SCIP_CONS *cons, SCIP_Bool enforce) Definition: scip.c:25097 static SCIP_RETCODE presolveConsLct(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff) Definition: cons_cumulative.c:10095 SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip) Definition: scipdefplugins.c:27 static SCIP_RETCODE consdataDropEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos) Definition: cons_cumulative.c:1781 SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value) Definition: scip.c:4001 int * SCIPgetDurationsCumulative(SCIP *scip, SCIP_CONS *cons) Definition: cons_cumulative.c:13882 static SCIP_RETCODE analyseInfeasibelCoreInsertion(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferduration, int inferdemand, int inferpeak, SCIP_Bool usebdwidening, SCIP_Bool *initialized, SCIP_Bool *explanation) Definition: cons_cumulative.c:3875 static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PRESOLTIMING presoltiming, int *nchgbds, int *ndelconss, SCIP_Bool *cutoff) Definition: cons_cumulative.c:7369 SCIP_VAR ** SCIPgetVarsCumulative(SCIP *scip, SCIP_CONS *cons) Definition: cons_cumulative.c:13819 static void freeNodedata(SCIP *scip, SCIP_NODEDATA **nodedata) Definition: cons_cumulative.c:5658 Definition: type_var.h:54 Definition: cons_cumulative.c:253 SCIP_Bool SCIPprofileFindLeft(SCIP_PROFILE *profile, int timepoint, int *pos) Definition: misc.c:5091 static SCIP_DECL_EVENTEXEC(eventExecCumulative) Definition: cons_cumulative.c:13468 SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet) Definition: scip.c:4382 SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row) Definition: scip.c:27811 SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr) Definition: misc.c:8245 SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx) Definition: scip.c:24369 Definition: struct_lp.h:189 static SCIP_RETCODE normalizeDemands(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides) Definition: cons_cumulative.c:9535 static SCIP_RETCODE computeCoreEngeryAfter(SCIP *scip, SCIP_PROFILE *profile, int nvars, int *ests, int *lcts, int *coreEnergyAfterEst, int *coreEnergyAfterLct) Definition: cons_cumulative.c:4218 Definition: type_set.h:38 static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss) Definition: cons_cumulative.c:8625 Definition: cons_cumulative.c:254 SCIP_RETCODE SCIPcreateConsBasicSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars) Definition: cons_setppc.c:8930 SCIP_RETCODE SCIPaddVarVlb(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vlbvar, SCIP_Real vlbcoef, SCIP_Real vlbconstant, SCIP_Bool *infeasible, int *nbdchgs) Definition: scip.c:21563 Definition: type_var.h:45 SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb) Definition: scip.c:24403 SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp))) Definition: scip.c:5611 static SCIP_RETCODE branch(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_Bool allowaddcons, SCIP_RESULT *result) Definition: branch_allfullstrong.c:63 void SCIPprofilePrint(SCIP_PROFILE *profile, SCIP_MESSAGEHDLR *messagehdlr, FILE *file) Definition: misc.c:5003 static SCIP_RETCODE inferboundsEdgeFinding(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS *cons, SCIP_BT *tree, SCIP_BTNODE **leaves, int capacity, int ncands, SCIP_Bool propest, int shift, SCIP_Bool *initialized, SCIP_Bool *explanation, int *nchgbds, SCIP_Bool *cutoff) Definition: cons_cumulative.c:6526 static SCIP_RETCODE consdataDeletePos(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_CONS *cons, int pos) Definition: cons_cumulative.c:2093 SCIP_RETCODE SCIPcreateConsBasicCumulative(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity) Definition: cons_cumulative.c:13711 int * SCIPprofileGetTimepoints(SCIP_PROFILE *profile) Definition: misc.c:5045 static SCIP_RETCODE computeImpliedEst(SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *addedvars, int *est) Definition: cons_cumulative.c:382 static SCIP_RETCODE tightenCoefs(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs) Definition: cons_cumulative.c:10692 static SCIP_DECL_SORTINDCOMP(consdataCompVar) Definition: cons_cumulative.c:12194 Definition: struct_misc.h:186 static SCIP_Bool checkDemands(SCIP *scip, SCIP_CONS *cons) Definition: cons_cumulative.c:9067 Definition: type_retcode.h:39 Definition: struct_misc.h:161 SCIP_RETCODE SCIPinferVarLbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20469 static SCIP_DECL_CONSENFOLP(consEnfolpCumulative) Definition: cons_cumulative.c:12822 SCIP_BTNODE * SCIPbtnodeGetLeftchild(SCIP_BTNODE *node) Definition: misc.c:6768 SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos) Definition: scip.c:36668 SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete))) Definition: scip.c:5565 Definition: type_set.h:34 Definition: type_stat.h:39 static SCIP_RETCODE tightenLbTTEF(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *var, int duration, int demand, int est, int ect, int lct, int begin, int end, int energy, int *bestlb, int *inferinfos, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) Definition: cons_cumulative.c:4357 static void createSortedEventpoints(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *starttimes, int *endtimes, int *startindices, int *endindices, SCIP_Bool local) Definition: cons_cumulative.c:686 SCIP_RETCODE SCIPincludeConshdlrCumulative(SCIP *scip) Definition: cons_cumulative.c:13499 Definition: struct_misc.h:80 SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin) Definition: misc.c:2177 static SCIP_RETCODE insertThetanode(SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node, SCIP_NODEDATA **nodedatas, int *nnodedatas) Definition: cons_cumulative.c:5903 int SCIPgetHmaxCumulative(SCIP *scip, SCIP_CONS *cons) Definition: cons_cumulative.c:13799 void SCIPbtnodeSetParent(SCIP_BTNODE *node, SCIP_BTNODE *parent) Definition: misc.c:6881 static SCIP_RETCODE removeRedundantConss(SCIP *scip, SCIP_CONS **conss, int nconss, int *ndelconss) Definition: cons_cumulative.c:12207 SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint))) Definition: scip.c:5772 static SCIP_RETCODE getActiveVar(SCIP *scip, SCIP_VAR **var, int *scalar, int *constant) Definition: cons_cumulative.c:1154 void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len) Definition: misc.c:3829 SCIP_RETCODE SCIPbranchVarHole(SCIP *scip, SCIP_VAR *var, SCIP_Real left, SCIP_Real right, SCIP_NODE **downchild, SCIP_NODE **upchild) Definition: scip.c:33775 SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row) Definition: scip.c:27834 static SCIP_RETCODE computeAlternativeBounds(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool local, int *alternativelbs, int *alternativeubs, int *downlocks, int *uplocks) Definition: cons_cumulative.c:7650 Definition: type_stat.h:44 Definition: type_stat.h:45 SCIP_RETCODE SCIPsetConsSeparated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool separate) Definition: scip.c:25072 static void traceLambdaEnergy(SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy) Definition: cons_cumulative.c:6205 static SCIP_DECL_CONSPRINT(consPrintCumulative) Definition: cons_cumulative.c:13249 void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...) Definition: scip.c:1281 static SCIP_RETCODE consdataCollectLinkingCons(SCIP *scip, SCIP_CONSDATA *consdata) Definition: cons_cumulative.c:2163 static SCIP_RETCODE initializeDurations(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss) Definition: cons_cumulative.c:11977 static SCIP_BTNODE * findResponsibleLambdaLeafTraceEnvelop(SCIP_BTNODE *node) Definition: cons_cumulative.c:6056 static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss) Definition: cons_cumulative.c:8668 Definition: type_lp.h:48 int SCIPgetHminCumulative(SCIP *scip, SCIP_CONS *cons) Definition: cons_cumulative.c:13755 static SCIP_RETCODE constructIncompatibilityGraph(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss) Definition: cons_cumulative.c:11585 static SCIP_RETCODE moveNodeToLambda(SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node) Definition: cons_cumulative.c:5867 static int computeCoreWithInterval(int begin, int end, int ect, int lst) Definition: cons_cumulative.c:363 static void collectThetaSubtree(SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy) Definition: cons_cumulative.c:6109 #define SCIPduplicateBufferArray(scip, ptr, source, num) Definition: scip.h:20593 SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol))) Definition: scip.c:5455 const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr) Definition: event.c:278 SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup) Definition: scip.c:19453 static SCIP_RETCODE resolvePropagationCoretimes(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferdemand, int inferpeak, int relaxedpeak, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool usebdwidening, int *provedpeak, SCIP_Bool *explanation) Definition: cons_cumulative.c:2408 static SCIP_RETCODE normalizeCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int *capacity, int *nchgcoefs, int *nchgsides) Definition: cons_cumulative.c:9460 static SCIP_DECL_CONSSEPASOL(consSepasolCumulative) Definition: cons_cumulative.c:12758 SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial) Definition: scip.c:25047 static SCIP_RETCODE applyAlternativeBoundsBranching(SCIP *scip, SCIP_VAR **vars, int nvars, int *alternativelbs, int *alternativeubs, int *downlocks, int *uplocks, SCIP_Bool *branched) Definition: cons_cumulative.c:3263 SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var) Definition: scip.c:24635 static SCIP_DECL_CONSPARSE(consParseCumulative) Definition: cons_cumulative.c:13328 SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened) Definition: scip.c:20299 static SCIP_DECL_CONSTRANS(consTransCumulative) Definition: cons_cumulative.c:12613 static SCIP_RETCODE propagateTimetable(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) Definition: cons_cumulative.c:5467 static SCIP_RETCODE fixIntegerVariableUb(SCIP *scip, SCIP_VAR *var, SCIP_Bool uplock, int *nfixedvars) Definition: cons_cumulative.c:9361 SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable) Definition: scip.c:27600 SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file) Definition: scip.c:28334 #define SCIPduplicateBlockMemoryArray(scip, ptr, source, num) Definition: scip.h:20568 void SCIPsortInt(int *intarray, int len) static SCIP_RETCODE createPrecedenceCons(SCIP *scip, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, int distance) Definition: cons_cumulative.c:11783 static INFERINFO getInferInfo(PROPRULE proprule, int data1, int data2) Definition: cons_cumulative.c:328 SCIP_RETCODE SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub) Definition: scip.c:24471 Definition: type_retcode.h:45 static SCIP_RETCODE detectRedundantConss(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, int *naddconss) Definition: cons_cumulative.c:12131 Definition: type_set.h:42 SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet) Definition: scip.c:4360 SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element) Definition: misc.c:1692 SCIP_CONS * SCIPgetConsLinking(SCIP *scip, SCIP_VAR *intvar) Definition: cons_linking.c:3342 static SCIP_RETCODE varMayRoundUp(SCIP *scip, SCIP_VAR *var, SCIP_Bool *roundable) Definition: cons_cumulative.c:7597 SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup) Definition: scip.c:19399 SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value) Definition: scip.c:3938 static SCIP_RETCODE separateConsOnIntegerVariables(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool lower, SCIP_Bool *separated) Definition: cons_cumulative.c:8959 static void consdataCalcSignature(SCIP_CONSDATA *consdata) Definition: cons_cumulative.c:12170 SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value) Definition: scip.c:3797 static SCIP_RETCODE createCapacityRestriction(SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool cutsasconss) Definition: cons_cumulative.c:8404 static SCIP_Bool impliesVlbPrecedenceCondition(SCIP *scip, SCIP_VAR *vlbvar, SCIP_Real vlbcoef, SCIP_Real vlbconst, int duration) Definition: cons_cumulative.c:11194 SCIP_RETCODE SCIPsetHmaxCumulative(SCIP *scip, SCIP_CONS *cons, int hmax) Definition: cons_cumulative.c:13775 SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx) Definition: scip.c:24436 SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image) Definition: misc.c:2094 static SCIP_RETCODE tightenCapacity(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides) Definition: cons_cumulative.c:10548 static SCIP_RETCODE collectDemands(SCIP *scip, SCIP_CONSDATA *consdata, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Longint **demands, int *ndemands) Definition: cons_cumulative.c:10428 Definition: type_retcode.h:43 SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var) Definition: scip.c:24659 static SCIP_RETCODE computeEffectiveHorizonCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *hmin, int *hmax, int *split) Definition: cons_cumulative.c:9572 static SCIP_DECL_CONSINITPRE(consInitpreCumulative) Definition: cons_cumulative.c:12502 Definition: objbranchrule.h:33 static SCIP_DECL_CONSGETNVARS(consGetNVarsCumulative) Definition: cons_cumulative.c:13445 static SCIP_RETCODE computeImpliedLct(SCIP *scip, SCIP_VAR *var, int duration, SCIP_HASHMAP *addedvars, int *lct) Definition: cons_cumulative.c:450 int SCIPprofileGetNTimepoints(SCIP_PROFILE *profile) Definition: misc.c:5035 SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars))) Definition: scip.c:5841 SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val) Definition: scip.c:27864 Definition: type_var.h:43 static SCIP_DECL_CONSDELETE(consDeleteCumulative) Definition: cons_cumulative.c:12587 SCIP_Longint SCIPcalcGreComDiv(SCIP_Longint val1, SCIP_Longint val2) Definition: misc.c:7083 SCIP_RETCODE SCIPrespropCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool *explanation, SCIP_RESULT *result) Definition: cons_cumulative.c:14068 default SCIP plugins static SCIP_BTNODE * findResponsibleLambdaLeafTraceEnergy(SCIP_BTNODE *node) Definition: cons_cumulative.c:6007 static SCIP_DECL_CONSSEPALP(consSepalpCumulative) Definition: cons_cumulative.c:12690 static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *violated, SCIP_Bool printreason) Definition: cons_cumulative.c:2372 Definition: type_stat.h:53 void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata) Definition: cons.c:3927 Definition: type_stat.h:48 Definition: type_result.h:39 Definition: struct_event.h:185 SCIP_RETCODE SCIPcreateConsLinking(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *intvar, SCIP_VAR **binvars, int *vals, int nbinvars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) Definition: cons_linking.c:3219 Definition: type_stat.h:42 static TCLIQUE_GETWEIGHTS(tcliqueGetweightsClique) Definition: cons_cumulative.c:11092 static SCIP_DECL_CONSRESPROP(consRespropCumulative) Definition: cons_cumulative.c:13175 static SCIP_RETCODE varMayRoundDown(SCIP *scip, SCIP_VAR *var, SCIP_Bool *roundable) Definition: cons_cumulative.c:7548 Definition: type_stat.h:51 static SCIP_Bool impliesVubPrecedenceCondition(SCIP *scip, SCIP_VAR *var, SCIP_Real vubcoef, SCIP_Real vubconst, int duration) Definition: cons_cumulative.c:11249 Definition: type_stat.h:54 SCIP_RETCODE SCIPnormalizeCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int *capacity, int *nchgcoefs, int *nchgsides) Definition: cons_cumulative.c:13951 |