cons_cumulative.c
Go to the documentation of this file.
33 * - 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
37 * 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.
51/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
68#define CONSHDLR_ENFOPRIORITY -2040000 /**< priority of the constraint handler for constraint enforcing */
69#define CONSHDLR_CHECKPRIORITY -3030000 /**< priority of the constraint handler for checking feasibility */
70#define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
71#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
72#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
74#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
75#define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
76#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
77#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
90#define DEFAULT_MAXTIME 2000000000 /** < maximum range for time horizon (to avoid integer overflow) */
100#define DEFAULT_TTINFER TRUE /**< should time-table (core-times) propagator be used to infer bounds? */
103#define DEFAULT_USEADJUSTEDJOBS FALSE /**< should during edge-finding jobs be adusted which run on the border of the effective time horizon? */
104#define DEFAULT_TTEFCHECK TRUE /**< should time-table edge-finding be used to detect an overload? */
111#define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
113#define DEFAULT_DETECTDISJUNCTIVE TRUE /**< search for conflict set via maximal cliques to detect disjunctive constraints */
114#define DEFAULT_DETECTVARBOUNDS TRUE /**< search for conflict set via maximal cliques to detect variable bound constraints */
115#define DEFAULT_MAXNODES 10000LL /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
121#define DEFAULT_USEBDWIDENING TRUE /**< should bound widening be used during conflict analysis? */
176 unsigned int varbounds:1; /**< bool to store if variable bound strengthening was already preformed */
177 unsigned int triedsolving:1; /**< bool to store if we tried already to solve that constraint as independent subproblem */
190 SCIP_Bool cutsasconss; /**< should the cumulative constraint create cuts as knapsack constraints? */
194 SCIP_Bool useadjustedjobs; /**< should during edge-finding jobs be adusted which run on the border of the effective time horizon? */
207 SCIP_Bool detectdisjunctive; /**< search for conflict set via maximal cliques to detect disjunctive constraints */
208 SCIP_Bool detectvarbounds; /**< search for conflict set via maximal cliques to detect variable bound constraints */
211 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
214 SCIP_Longint maxnodes; /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
216 SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)); /**< method to use a single cumulative condition */
220 SCIP_Longint nlbtimetable; /**< number of times the lower bound was tightened by the time-table propagator */
221 SCIP_Longint nubtimetable; /**< number of times the upper bound was tightened by the time-table propagator */
222 SCIP_Longint ncutofftimetable; /**< number of times the a cutoff was detected due to time-table propagator */
223 SCIP_Longint nlbedgefinder; /**< number of times the lower bound was tightened by the edge-finder propagator */
224 SCIP_Longint nubedgefinder; /**< number of times the upper bound was tightened by the edge-finder propagator */
225 SCIP_Longint ncutoffedgefinder; /**< number of times the a cutoff was detected due to edge-finder propagator */
226 SCIP_Longint ncutoffoverload; /**< number of times the a cutoff was detected due to overload checking via edge-finding */
227 SCIP_Longint nlbTTEF; /**< number of times the lower bound was tightened by time-table edge-finding */
228 SCIP_Longint nubTTEF; /**< number of times the upper bound was tightened by time-table edge-finding */
229 SCIP_Longint ncutoffoverloadTTEF;/**< number of times the a cutoff was detected due to overload checking via time-table edge-finding */
231 int nirrelevantjobs; /**< number of time a irrelevant/redundant jobs was removed form a constraint */
232 int nalwaysruns; /**< number of time a job removed form a constraint which run completely during the effective horizon */
236 int ndualbranchs; /**< number of times a dual branch was discoverd and applicable via probing */
237 int nallconsdualfixs; /**< number of times a dual fix was performed due to knowledge of all cumulative constraints */
247 * An inference information can be passed with each domain reduction to SCIP. This information is passed back to the
248 * constraint handler if the corresponding bound change has to be explained. It can be used to store information which
249 * help to construct a reason/explanation for a bound change. The inference information is limited to size of integer.
251 * In case of the cumulative constraint handler we store the used propagation algorithms for that particular bound
264};
367/** constructs an inference information out of a propagation rule, an earliest start and a latest completion time */
378 if( proprule == PROPRULE_0_INVALID || data1 < 0 || data1 >= (1<<15) || data2 < 0 || data2 >= (1<<15) )
424#define computeCoreWithInterval(begin, end, ect, lst) (MAX(0, MIN((end), (ect)) - MAX((lst), (begin))))
450 /* the code contains a bug; we need to check if an implication forces that the jobs do not run in parallel */
519 /* the code contains a bug; we need to check if an implication forces that the jobs do not run in parallel */
561/** collects all necessary binary variables to represent the jobs which can be active at time point of interest */
606 /* check the end time of this job is larger than the curtime; in this case the job is still running */
715 /* check the end time of this job is larger than the curtime; in this case the job is still running */
775 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
814 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
864 SCIPdebugMsg(scip, "%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
865 *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var),
884 SCIPdebugMsg(scip, "%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
885 *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var),
894 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
929 SCIP_Real** cumulativedemands, /**< array to store the estimated cumulative demand for each point in time */
937 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
938 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
963 createSortedEventpoints(scip, nvars, vars, durations, starttimes, endtimes, startindices, endindices, TRUE);
1149 disjfactor2 = MAX( disjfactor2, (peak-(SCIP_Real)capacity)/peak * (nlarge/(SCIP_Real)ndemands) );
1150 cumfactor1 = MAX( cumfactor1, (peak-capacity)/peak * (capacity-deltademand)/(SCIP_Real)capacity );
1189 SCIPstatisticPrintf("cumulative constraint<%s>: DISJ1=%g, DISJ2=%g, CUM=%g, RS1 = %g, RS2 = %g, EST = %g\n",
1190 SCIPconsGetName(cons), consdata->disjfactor1, disjfactor2, cumfactor1, resstrength1, resstrength2,
1272 SCIP_Real* objvals, /**< array of objective coefficients for each job (linear objective function), or NULL if none */
1320 SCIP_CALL( SCIPcreateVarBasic(subscip, &subvars[v], name, ests[v], lsts[v], objval, SCIP_VARTYPE_INTEGER) );
1338 * @note This "meta" setting has to be set first since this call overwrite all parameters including for example the
1364 SCIPdebugMsg(subscip, "solved single cumulative condition with status %d\n", SCIPgetStatus(subscip));
1509 /* create for each job and time step a binary variable which is one if this jobs starts at this time point and a set
1550 SCIP_CALL( SCIPcreateVarBasic(subscip, &binvar, name, 0.0, 1.0, objval, SCIP_VARTYPE_BINARY) );
1553 /* add binary varibale to the set partitioning constraint which ensures that the job is started */
1564 /* adjusted the smallest earliest start time and the largest latest completion time with the effective horizon */
1571 /* create for each time a knapsack constraint which ensures that the resource capacity is not exceeded */
1580 SCIP_CALL( SCIPcreateConsBasicKnapsack(subscip, &cons, name, 0, NULL, NULL, (SCIP_Longint)capacity) );
1641 SCIPdebugMsg(scip, "solved single cumulative condition with status %d\n", SCIPgetStatus(subscip));
1707 /* check which binary varibale is the first binary varibale which is not globally fixed to zero */
1717 /* check which binary varibale is the last binary varibale which is not globally fixed to zero */
1772 * Method used to create and free the constraint handler data when including and removing the cumulative constraint
1937 SCIP_CONS** linkingconss, /**< array of linking constraints for the integer variables, or NULL */
1996 /* initialize variable lock data structure; the locks are only used if the constraint is a check constraint */
2001 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->linkingconss, linkingconss, nvars) );
2010 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
2012 /* multi-aggregated variables cannot be replaced by active variable; therefore we mark all variables for not
2023 SCIP_CALL( SCIPtransformConss(scip, (*consdata)->nvars, (*consdata)->linkingconss, (*consdata)->linkingconss) );
2185 SCIPinfoMessage(scip, file, ")[%d,%d) <= %d", consdata->hmin, consdata->hmax, consdata->capacity);
2210 SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, consdata->downlocks[pos], consdata->uplocks[pos]) );
2231 SCIPvarGetName(consdata->vars[pos]), SCIPvarGetLbGlobal(consdata->vars[pos]), SCIPvarGetUbGlobal(consdata->vars[pos]), SCIPconsGetName(cons));
2233 /* in case the we did not remove the variable in the last slot of the arrays we move the current last to this
2284 SCIPdebugMsg(scip, "linking constraint (%d of %d) for variable <%s>\n", v+1, nvars, SCIPvarGetName(var));
2309 SCIP_STRINGEQ( SCIPconshdlrGetName(SCIPconsGetHdlr(consdata->linkingconss[v])), "linking", SCIP_INVALIDCALL );
2323/** check for the given starting time variables with their demands and durations if the cumulative conditions for the
2331 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
2344 int* startindices; /* we will sort the startsolvalues, thus we need to know which index of a job it corresponds to */
2345 int* endindices; /* we will sort the endsolvalues, thus we need to know which index of a job it corresponds to */
2367 /* compute time points where we have to check whether capacity constraint is infeasible or not */
2378 /* the constraint of the cumulative constraint handler should be called after the integrality check */
2383 /* we need to ensure that we check at least one time point during the effective horizon; therefore we project all
2393 /* sort the arrays not-decreasing according to start solution values and end solution values (and sort the
2481/** check if the given constrait is valid; checks each starting point of a job whether the remaining capacity is at
2534 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2537 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2551 SCIPdebugMsg(scip, "variable <%s>: (demand %d) resolve propagation of core time algorithm (peak %d)\n",
2563 /* first we loop over all variables and adjust the capacity with those jobs which provide a global core at the
2564 * inference peak and those where the current conflict bounds provide a core at the inference peak
2578 /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */
2579 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)));
2581 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)));
2591 /* check if the inference peak is part of the global bound core; if so we decreasing the capacity by the demand of
2609 /* collect the conflict bound core (the conflict bounds are those bounds which are already part of the conflict)
2610 * hence these bound are already reported by other resolve propation steps. In case a bound (lower or upper) is
2616 /* check if the inference peak is part of the conflict bound core; if so we decreasing the capacity by the demand
2619 * @note we do not need to reported that job to SCIP since the required bounds are already reported
2646 /* collect all cores of the variables which lay in the considered time window except the inference variable */
2659 /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */
2660 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)));
2662 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)));
2666 ect = boundedConvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) + duration;
2670 SCIPvarGetName(var), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE),
2706 ect = boundedConvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) + duration;
2714 SCIPdebugMsg(scip, "infer peak %d, relaxed peak %d, lst %d, ect %d\n", inferpeak, relaxedpeak, maxlst, minect);
2742 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(inferpeak - duration + 1)) );
2767/** compute the minimum overlaps w.r.t. the duration of the job and the time window [begin,end) */
2800/** an overload was detected due to the time-time edge-finding propagate; initialized conflict analysis, add an initial
2803 * @note the conflict analysis is not performend, only the initialized SCIP_Bool pointer is set to TRUE
2817 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2820 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2837 SCIPdebugMsg(scip, "analysis energy load in [%d,%d) (capacity %d, energy %" SCIP_LONGINT_FORMAT ")\n", begin, end, capacity, requiredenergy);
2839 /* collect global contribution and adjusted the required energy by the amount of energy the inference variable
2874 SCIPvarGetName(var), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE),
2877 /* compute the amount of energy which needs to be available for enforcing the propagation and report the bound
2884 /* get the latest start time of the infer start time variable before the propagation took place */
2887 /* the latest start time of the inference start time variable before the propagation needs to be smaller as
2888 * the end of the time interval; meaning the job needs be overlap with the time interval in case the job is
2893 /* compute the overlap of the job in case it would be scheduled w.r.t. its latest start time and the time
2898 /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */
2918 assert(boundedConvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)) <= (end - overlap));
2932 /* get the earliest completion time of the infer start time variable before the propagation took place */
2933 ect = boundedConvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) + duration;
2935 /* the earliest start time of the inference start time variable before the propagation needs to be larger as
2936 * than the beginning of the time interval; meaning the job needs be overlap with the time interval in case
2941 /* compute the overlap of the job in case it would be scheduled w.r.t. its earliest start time and the time
2946 /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */
2965 assert(boundedConvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) >= (begin + overlap - duration));
2966 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(begin + overlap - duration)) );
2974 /* subtract the amount of energy which is available due to the overlap of the inference start time */
2989 /* check if the has any overlap w.r.t. global bound; meaning some parts of the job will run for sure within the
3008 /* check if the job has any overlap w.r.t. local bound; meaning some parts of the job will run for sure within the
3069 SCIPdebugMsg(scip, "variable <%s> glb=[%g,%g] loc=[%g,%g], conf=[%g,%g], added=[%d,%d] (demand %d, duration %d)\n",
3106 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
3109 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
3110 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
3140 /* we propagated the latest start time (upper bound) step wise with a step length of at most the duration of
3143 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE) - SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < inferduration + 0.5);
3151 /* the bound passed back to be resolved might be tighter as the bound propagted by the core time propagator;
3152 * this can happen if the variable is not activ and aggregated to an activ variable with a scale != 1.0
3155 boundedConvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE)) + inferduration <= inferpeak);
3179 /* the bound passed back to be resolved might be tighter as the bound propagted by the core time propagator;
3180 * this can happen if the variable is not activ and aggregated to an activ variable with a scale != 1.0
3182 assert(boundedConvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE)) - 1 >= inferpeak);
3197 SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
3198 infervar, inferdemand, inferpeak, relaxedpeak, bdchgidx, usebdwidening, &provedpeak, explanation) );
3218 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, bdchgidx, (SCIP_Real)(provedpeak - inferduration + 1)) );
3296 if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == downlocks[v] && !SCIPisNegative(scip, objval) )
3304 SCIP_CALL( SCIPbranchVarHole(scip, var, SCIPvarGetLbLocal(var), (SCIP_Real)alternativelbs[v], NULL, NULL) );
3314 if( SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == uplocks[v] && !SCIPisPositive(scip, objval) )
3322 SCIP_CALL( SCIPbranchVarHole(scip, var, (SCIP_Real)alternativeubs[v], SCIPvarGetUbLocal(var), NULL, NULL) );
3407/** computes a point in time when the capacity is exceeded returns hmax if this does not happen */
3418 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
3419 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
3464 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars);
3492/** checks all cumulative constraints for infeasibility and add branching candidates to storage */
3669/** in case the cumulative constraint is independent of every else, solve the cumulative problem and apply the fixings
3676 SCIP_Longint maxnodes, /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
3702 /* if SCIP is in probing mode or repropagation we cannot perform this dual reductions since this dual reduction
3708 /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
3716 /* if the cumulative constraint is the only constraint of the original problem or the only check constraint in the
3730 /* after 250 conflict we force a restart since then the variable statistics are reasonable initialized */
3766 /* check if already tried to solve that constraint as independent sub problem; we do not want to try it again if we
3776 /* mark the constraint to be tried of solving it as independent sub problem; in case that is successful the
3781 SCIPdebugMsg(scip, "the cumulative constraint <%s> is independent from rest of the problem (%d variables, %d constraints)\n",
3796 /* if a variables array is given, use the variable bounds otherwise the default values stored in the ests and lsts
3814 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
3822 SCIP_CALL( SCIPsolveCumulative(scip, nvars, lbs, ubs, objvals, consdata->durations, consdata->demands, consdata->capacity,
3823 consdata->hmin, consdata->hmax, timelimit, memorylimit, maxnodes, &solved, cutoff, unbounded, &error) );
3903 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
3906 SCIPdebugMsg(scip, "detected infeasibility due to adding a core to the core resource profile\n");
3907 SCIPdebugMsg(scip, "variable <%s>[%g,%g] (demand %d, duration %d)\n", SCIPvarGetName(infervar),
3915 SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
3920 /* add both bound of the inference variable since these biuld the core which we could not inserted */
3923 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, NULL, (SCIP_Real)(inferpeak - inferduration + 1)) );
3938/** We are using the core resource profile which contains all core except the one of the start time variable which we
3939 * want to propagate, to incease the earliest start time. This we are doing in steps of length at most the duration of
3940 * the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict
3959 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
3986 /* first we find left position of earliest start time (lower bound) in resource profile; this position gives us the
4012 /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we
4025 /* if we found no peak that means current the job could be scheduled at its earliest start time without
4032 /* the peak position gives us a time point where the start time variable is in conflict with the resource
4033 * profile. That means we have to move it to the next time point in the resource profile but at most to the
4045 SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
4056 /* construct the inference information which we are using with the conflict analysis to resolve that particular
4064 SCIP_CALL( SCIPinferVarLbCons(scip, var, (SCIP_Real)newlb, cons, inferInfoToInt(inferinfo), TRUE, infeasible, &tightened) );
4073 SCIPdebugMsg(scip, "variable <%s> new lower bound <%d> -> <%d>\n", SCIPvarGetName(var), est, newlb);
4076 /* for the statistic we count the number of times a lower bound was tightened due the the time-table algorithm */
4081 * @note We are taking the lower of the start time variable on purpose instead of newlb. This is due the fact that
4082 * the proposed lower bound might be even strength by be the core which can be the case if aggregations are
4099/** We are using the core resource profile which contains all core except the one of the start time variable which we
4100 * want to propagate, to decrease the latest start time. This we are doing in steps of length at most the duration of
4101 * the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict
4140 /* first we find left position of latest completion time minus 1 (upper bound + duration) in resource profile; That
4141 * is the last time point where the job would run if schedule it at its latest start time (upper bound). This
4171 /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we
4183 /* if we found no peak that means the current job could be scheduled at its latest start time without conflicting
4190 /* the peak position gives us a time point where the start time variable is in conflict with the resource
4191 * profile. That means the job has be done until that point. Hence that gives us the latest completion
4192 * time. Note that that we want to move the bound by at most the duration length (the remaining move we are
4199 /* construct the inference information which we are using with the conflict analysis to resolve that particular
4207 SCIP_CALL( SCIPinferVarUbCons(scip, var, (SCIP_Real)newub, cons, inferInfoToInt(inferinfo), TRUE, &infeasible, &tightened) );
4216 SCIPdebugMsg(scip, "variable <%s>: new upper bound <%d> -> <%d>\n", SCIPvarGetName(var), lst, newub);
4219 /* for the statistic we count the number of times a upper bound was tightened due the the time-table algorithm */
4224 * @note We are taking the upper of the start time variable on purpose instead of newub. This is due the fact that
4225 * the proposed upper bound might be even strength by be the core which can be the case if aggregations are
4243/** compute for the different earliest start and latest completion time the core energy of the corresponding time
4252 int* coreEnergyAfterEst, /**< array to store the core energy after the earliest start time of each job */
4253 int* coreEnergyAfterLct /**< array to store the core energy after the latest completion time of each job */
4272 energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1));
4281 coreEnergyAfterEst[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - ests[v]);
4297 energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1));
4306 coreEnergyAfterLct[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - lcts[v]);
4401 SCIP_Longint energy, /**< available energy for the flexible part of the hob within the time window */
4403 int* inferinfos, /**< pointer to store the inference information which is need for the (best) lower bound change */
4405 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4418 /* if the job can be processed completely before or after the time window, nothing can be tightened */
4422 /* if flexible part runs completely within the time window (assuming it is scheduled on its earliest start time), we
4428 /* check if the available energy in the time window is to small to handle the flexible part if it is schedule on its
4434 /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is
4437 * @note the variable ect define the earliest completion time of the flexible part of the job; hence we need to
4442 /* compute a latest start time (upper bound) such that the job consums at most the available energy
4448 /* check if we detected an infeasibility which is the case if the new lower bound is larger than the current upper
4471 begin, end, var, SCIP_BOUNDTYPE_LOWER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) );
4514 SCIP_Longint energy, /**< available energy for the flexible part of the hob within the time window */
4516 int* inferinfos, /**< pointer to store the inference information which is need for the (best) upper bound change */
4518 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4532 /* if flexible part of the job can be processed completely before or after the time window, nothing can be tightened */
4536 /* if flexible part runs completely within the time window (assuming it is scheduled on its latest start time), we
4542 /* check if the available energy in the time window is to small to handle the flexible part of the job */
4546 /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is
4549 * @note the variable lst define the latest start time of the flexible part of the job; hence we need to compute the
4555 /* compute a latest start time (upper bound) such that the job consums at most the available energy
4562 /* check if we detected an infeasibility which is the case if the new upper bound is smaller than the current lower
4585 begin, end, var, SCIP_BOUNDTYPE_UPPER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) );
4608/** propagate the upper bounds and "opportunistically" the lower bounds using the time-table edge-finding algorithm */
4622 int* lbinferinfos, /**< array to store the inference information for the lower bound changes */
4623 int* ubinferinfos, /**< array to store the inference information for the upper bound changes */
4624 int* lsts, /**< array of latest start time of the flexible part in the same order as the variables */
4626 int* perm, /**< permutation of the variables w.r.t. the non-decreasing order of the earliest start times */
4632 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4671 /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */
4677 /* loop over all variable in non-increasing order w.r.t. the latest completion time; thereby, the latest completion
4690 /* if the latest completion time is larger then hmax an infeasibility cannot be detected, since after hmax an
4703 /* if the latest completion time equals to previous end time, we can continue since this particular interval
4711 /* In case we only want to detect an overload (meaning no bound propagation) we can skip the interval; this is
4712 * the case if the free energy (the energy which is not occupied by any core) is smaller than the previous minimum
4723 freeenergy = capacity * ((SCIP_Longint) end - lct) - coreEnergyAfterLct[v] + coreEnergyAfterEnd;
4727 SCIPdebugMsg(scip, "skip latest completion time <%d> (minimum available energy <%" SCIP_LONGINT_FORMAT ">, free energy <%" SCIP_LONGINT_FORMAT ">)\n", lct, minavailable, freeenergy);
4743 /* loop over the job in non-increasing order w.r.t. the earliest start time; these earliest start time are
4744 * defining the beginning of the time interval under investigation; Thereby, the time interval gets wider and
4765 /* if the job starts after the current end, we can skip it and do not need to consider it again since the
4774 /* check if the interval has a size such that the total energy fits, if so we can skip all intervals with the
4794 /* in case the earliest start time is equal to minbegin, the job lies completely within the time window under
4803 SCIP_CALL( tightenUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
4804 var, duration, demand, est, lst, lct, minbegin, end, minavailable, &(newubs[idx]), &(ubinferinfos[idx]),
4811 SCIPdebugMsg(scip, "check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, lst of free part <%d>\n",
4812 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, lst);
4817 /* if the earliest start time is smaller than hmin we can stop here since the next job will not decrease the
4837 /* compute the flexible energy which is part of the time interval for sure if the job is scheduled
4849 /* compute the flexible energy of the job which is not part of flexible energy of the time interval */
4865 freeenergy = capacity * ((SCIP_Longint) end - begin) - flexenergy - coreEnergyAfterEst[i] + coreEnergyAfterEnd;
4870 SCIPdebugMsg(scip, "analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
4887 /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */
4888 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
4893 /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */
4904 energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, (SCIP_Longint) end - lsts[lbcand])) * demands[lbcand];
4959/** propagate the lower bounds and "opportunistically" the upper bounds using the time-table edge-finding algorithm */
4973 int* lbinferinfos, /**< array to store the inference information for the lower bound changes */
4974 int* ubinferinfos, /**< array to store the inference information for the upper bound changes */
4975 int* ects, /**< array of earliest completion time of the flexible part in the same order as the variables */
4977 int* perm, /**< permutation of the variables w.r.t. the non-decreasing order of the latest completion times */
4983 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
5024 /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */
5030 /* loop over all variable in non-decreasing order w.r.t. the earliest start times; thereby, the earliest start times
5044 /* if the earliest start time is smaller then hmin an infeasibility cannot be detected, since before hmin an
5054 /* if the latest earliest start time equals to previous start time, we can continue since this particular interval
5073 /* loop over the job in non-decreasing order w.r.t. the latest completion time; these latest completion times are
5074 * defining the ending of the time interval under investigation; thereby, the time interval gets wider and wider
5094 /* if the job has a latest completion time before the the current start, we can skip it and do not need to
5095 * consider it again since the earliest start times (which define the start) are scant in non-decreasing order
5103 /* check if the interval has a size such that the total energy fits, if so we can skip all intervals which
5123 /* in case the latest completion time is equal to minend, the job lies completely within the time window under
5132 SCIP_CALL( tightenLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5133 var, duration, demand, est, ect, lct, begin, minend, minavailable, &(newlbs[idx]), &(lbinferinfos[idx]),
5140 SCIPdebugMsg(scip, "check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, ect of free part <%d>\n",
5141 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, ect);
5146 /* if the latest completion time is larger than hmax we can stop here since the next job will not decrease the
5166 /* compute the flexible energy which is part of the time interval for sure if the job is scheduled
5178 /* compute the flexible energy of the job which is not part of flexible energy of the time interval */
5194 freeenergy = capacity * ((SCIP_Longint) end - begin) - flexenergy - coreEnergyAfterStart + coreEnergyAfterLct[i];
5199 SCIPdebugMsg(scip, "analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
5216 /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */
5217 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
5222 /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */
5236 energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, (SCIP_Longint) ects[ubcand] - begin)) * demands[ubcand];
5290/** checks whether the instance is infeasible due to a overload within a certain time frame using the idea of time-table
5294 * - Petr Vilim, "Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources", In: Tobias
5295 * Achterberg and J. Christopher Beck (Eds.), Integration of AI and OR Techniques in Constraint Programming for
5297 * - Andreas Schutt, Thibaut Feydy, and Peter J. Stuckey, "Explaining Time-Table-Edge-Finding Propagation for the
5315 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
5361 /* we need to buffer the bound changes since the propagation algorithm cannot handle new bound dynamically */
5371 collectDataTTEF(scip, nvars, vars, durations, demands, hmin, hmax, permests, ests, permlcts, lcts, ects, lsts, flexenergies);
5377 /* compute for the different earliest start and latest completion time the core energy of the corresponding time
5383 SCIP_CALL( propagateUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5385 permests, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );
5388 SCIP_CALL( propagateLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5390 permlcts, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );
5405 SCIP_CALL( SCIPtightenVarLb(scip, vars[v], (SCIP_Real)newlbs[v], TRUE, &infeasible, &tightened) );
5408 /* since we change first the lower bound of the variable an infeasibilty should not be detected */
5426 SCIP_CALL( SCIPtightenVarUb(scip, vars[v], (SCIP_Real)newubs[v], TRUE, &infeasible, &tightened) );
5429 /* since upper bound was compute w.r.t. the "old" bound the previous lower bound update together with this upper
5434 /* a small performance improvement is possible here: if the tighten...TEFF and propagate...TEFF methods would
5435 * return not only the inferinfos, but the actual begin and end values, then the infeasibility here could also
5438 if( SCIPisConflictAnalysisApplicable(scip) && inferInfoIsValid(intToInferInfo(ubinferinfos[v])) )
5471 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
5505/** a cumulative condition is not satisfied if its capacity is exceeded at a time where jobs cannot be shifted (core)
5506 * anymore we build up a cumulative profile of all cores of jobs and try to improve bounds of all jobs; also known as
5524 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
5546 SCIPdebugMsg(scip, "propagate cores of cumulative condition of constraint <%s>[%d,%d) <= %d\n",
5580 /* check if the job runs completely outside of the effective horizon [hmin, hmax); if so skip it */
5595 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, begin, end);
5601 SCIP_CALL( coretimesUpdateLb(scip, nvars, vars, durations, demands, capacity, hmin, hmax, cons,
5635 SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
5636 var, duration, demand, SCIPprofileGetTime(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) );
5644 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutofftimetable++ );
5658 SCIP_VAR* var; /**< start time variable of the job if the node data belongs to a leaf, otherwise NULL */
5666 SCIP_Longint enveloptheta; /**< the maximal energy of a subset of jobs part of the theta set */
5716 nodedata->enveloptheta = MAX(leftdata->enveloptheta + rightdata->energytheta, rightdata->enveloptheta);
5728 nodedata->enveloplambda = MAX(leftdata->enveloplambda + rightdata->energytheta, rightdata->enveloplambda);
5734 nodedata->enveloplambda = MAX(nodedata->enveloplambda, leftdata->enveloptheta + rightdata->energylambda);
5736 SCIPdebugMsg(scip, "node <%p> lambda envelop %" SCIP_LONGINT_FORMAT "\n", (void*)node, nodedata->enveloplambda);
5742 nodedata->energylambda = MAX(leftdata->energylambda + rightdata->energytheta, leftdata->energytheta + rightdata->energylambda);
6061 if( leftdata->energylambda >= 0 && nodedata->energylambda == leftdata->energylambda + rightdata->energytheta )
6111 if( leftdata->enveloplambda >= 0 && nodedata->enveloplambda == leftdata->enveloplambda + rightdata->energytheta )
6148 SCIPdebugMessage("add variable <%s> as elements %d to omegaset\n", SCIPvarGetName(nodedata->var), *nelements);
6153 (*energy) += (nodedata->duration - nodedata->leftadjust - nodedata->rightadjust) * nodedata->demand;
6205 if( leftdata->enveloptheta >= 0 && nodedata->enveloptheta == leftdata->enveloptheta + rightdata->energytheta )
6260 if( leftdata->energylambda >= 0 && nodedata->energylambda == leftdata->energylambda + rightdata->energytheta )
6320 if( leftdata->enveloplambda >= 0 && nodedata->enveloplambda == leftdata->enveloplambda + rightdata->energytheta )
6359 SCIPvarGetName(nodedata->var), SCIPvarGetLbLocal(nodedata->var), SCIPvarGetUbLocal(nodedata->var),
6360 SCIPvarGetLbGlobal(nodedata->var), SCIPvarGetUbGlobal(nodedata->var), duration, nodedata->demand);
6392 * @note the conflict analysis is not performend, only the initialized SCIP_Bool pointer is set to TRUE
6403 SCIP_Bool propest, /**< should the earliest start times be propagated, otherwise the latest completion times */
6407 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
6417 SCIPdebugMsg(scip, "est=%d, lct=%d, propest %u, reportedenergy %d, shift %d\n", est, lct, propest, reportedenergy, shift);
6425 /* collect the energy of the responsible leaves until the cumulative energy is large enough to detect an overload;
6446 SCIPdebugMsg(scip, "time window [%d,%d) available energy %" SCIP_LONGINT_FORMAT ", required energy %d\n", est, lct, energy, reportedenergy);
6469 /* report the variables and relax their bounds to final time interval [est,lct) which was been detected to be
6483 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, nodedata->var, NULL, (SCIP_Real)(est - nodedata->leftadjust)) );
6484 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, nodedata->var, NULL, (SCIP_Real)(lct - nodedata->duration + nodedata->rightadjust)) );
6501/** computes a new latest starting time of the job in 'respleaf' due to the energy consumption and stores the
6525 newest = (int)SCIPfeasCeil(scip, (energy - (SCIP_Real)(capacity - demand) * (lct - est)) / (SCIP_Real)demand);
6533/** propagates start time using an edge finding algorithm which is based on binary trees (theta lambda trees)
6535 * @note The algorithm is based on the paper: Petr Vilim, "Edge Finding Filtering Algorithm for Discrete Cumulative
6547 SCIP_Bool propest, /**< should the earliest start times be propagated, otherwise the latest completion times */
6550 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
6563 /* iterate over all added candidate (leaves) in non-increasing order w.r.t. their latest completion time */
6624 newest = computeEstOmegaset(scip, leafdata->duration, leafdata->demand, capacity, est, lct, energy);
6626 /* if the computed earliest start time is greater than the latest completion time of the omega set we detected an overload */
6632 SCIP_CALL( analyzeConflictOverload(scip, omegaset, capacity, nelements, est, lct, 0, propest, shift,
6637 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffedgefinder++ );
6647 /* constuct inference information; store used propagation rule and the the time window of the omega set */
6664 /* for the statistic we count the number of times a lower bound was tightened due the edge-finder */
6669 /* constuct inference information; store used propagation rule and the the time window of the omega set */
6673 SCIPvarGetName(leafdata->var), SCIPvarGetUbLocal(leafdata->var), shift - newest - leafdata->duration);
6677 SCIP_CALL( SCIPinferVarUbCons(scip, leafdata->var, (SCIP_Real)(shift - newest - leafdata->duration),
6682 SCIP_CALL( SCIPtightenVarUb(scip, leafdata->var, (SCIP_Real)(shift - newest - leafdata->duration),
6686 /* for the statistic we count the number of times a upper bound was tightened due the edge-finder */
6734 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffedgefinder++ );
6756/** checks whether the instance is infeasible due to a overload within a certain time frame using the idea of theta trees
6758 * @note The algorithm is based on the paper: Petr Vilim, "Max Energy Filtering Algorithm for Discrete Cumulative
6759 * Resources". In: Willem Jan van Hoeve and John N. Hooker (Eds.), Integration of AI and OR Techniques in
6760 * Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2009), LNCS 5547, pp 294--308
6774 SCIP_Bool propest, /**< should the earliest start times be propagated, otherwise the latest completion times */
6776 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
6801 SCIPdebugMsg(scip, "check overload of cumulative condition of constraint <%s> (capacity %d)\n", SCIPconsGetName(cons), capacity);
6819 /* compute the latest completion time of all jobs which define the shift we apply to run the algorithm for the
6831 /* collect earliest and latest completion times and ignore jobs which do not run completion within the effective
6857 /* adjust the duration, earliest start time, and latest completion time of jobs which do not lie completely in the
6873 /* only consider jobs which have a (adjusted) duration greater than zero (the amound which will run defenetly
6912 /* adjust earliest start time to make it unique in case several jobs have the same earliest start time */
6922 /* the envelop is the energy of the job plus the total amount of energy which is available in the time period
6923 * before that job can start, that is [0,est). The envelop is later used to compare the energy consumption of a
6942 /* iterate over all jobs in non-decreasing order of their latest completion times and add them to the theta set until
6952 /* check if the new job opens a time window which size is so large that it offers more energy than the total
6980 SCIPdebugMsg(scip, "detects cutoff due to overload in time window [?,%d) (ncands %d)\n", nodedatas[idx].lct, j);
6984 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverload++ );
6990 /* in case an overload was detected and the conflict analysis is applicable, create an initialize explanation */
7002 /* scan the remaining candidates for a global contributions within the time window of the last inserted candidate
7039 SCIP_CALL( analyzeConflictOverload(scip, leaves, capacity, ninsertcands, est, lct, glbenery, propest, shift,
7045 SCIP_CALL( inferboundsEdgeFinding(scip, conshdlrdata, cons, tree, leaves, capacity, ninsertcands,
7060/** checks whether the instance is infeasible due to a overload within a certain time frame using the idea of theta trees
7062 * @note The algorithm is based on the paper: Petr Vilim, "Max Energy Filtering Algorithm for Discrete Cumulative
7063 * Resources". In: Willem Jan van Hoeve and John N. Hooker (Eds.), Integration of AI and OR Techniques in
7064 * Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2009), LNCS 5547, pp 294--308
7079 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
7093 SCIP_CALL( checkOverloadViaThetaTree(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
7105 SCIP_CALL( checkOverloadViaThetaTree(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
7111/** checks if the constraint is redundant; that is the case if its capacity can never be exceeded; therefore we check
7112 * with respect to the lower and upper bounds of the integer start time variables the maximum capacity usage for all
7131 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
7132 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
7185 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
7234/** creates the worst case resource profile, that is, all jobs are inserted with the earliest start and latest
7243 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
7250 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
7284 /* check if the job runs completely outside of the effective horizon [hmin, hmax); if so skip it */
7309 SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
7310 var, duration, demand, SCIPprofileGetTime(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) );
7318 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutofftimetable++ );
7344 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
7360 SCIP_CALL( consCheckRedundancy(scip, nvars, vars, durations, demands, capacity, hmin, hmax, redundant) );
7369 SCIP_CALL_TERMINATE( retcode, createCoreProfile(scip, conshdlrdata, profile, nvars, vars, durations, demands, capacity, hmin, hmax,
7375 SCIP_CALL_TERMINATE( retcode, propagateTimetable(scip, conshdlrdata, profile, nvars, vars, durations, demands, capacity, hmin, hmax, cons,
7382 SCIP_CALL_TERMINATE( retcode, propagateEdgeFinding(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
7389 SCIP_CALL_TERMINATE( retcode, propagateTTEF(scip, conshdlrdata, profile, nvars, vars, durations, demands, capacity, hmin, hmax, cons,
7477/** it is dual feasible to remove the values {leftub+1, ..., rightlb-1} since SCIP current does not feature domain holes
7478 * we use the probing mode to check if one of the two branches is infeasible. If this is the case the dual redundant can
7489 SCIP_Real* leftimpllbs, /**< lower bounds after applying implications and cliques in left branch, or NULL */
7490 SCIP_Real* leftimplubs, /**< upper bounds after applying implications and cliques in left branch, or NULL */
7493 SCIP_Real* rightimpllbs, /**< lower bounds after applying implications and cliques in right branch, or NULL */
7494 SCIP_Real* rightimplubs, /**< upper bounds after applying implications and cliques in right branch, or NULL */
7495 SCIP_Real* rightproplbs, /**< lower bounds after applying domain propagation in right branch */
7496 SCIP_Real* rightpropubs, /**< upper bounds after applying domain propagation in right branch */
7497 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */
7523 SCIP_CALL( SCIPapplyProbingVar(scip, vars, nvars, probingpos, SCIP_BOUNDTYPE_UPPER, leftub, -1,
7540 /* note that probing can change the upper bound and thus the right branch may have been detected infeasible if
7558 SCIP_CALL( SCIPapplyProbingVar(scip, vars, nvars, probingpos, SCIP_BOUNDTYPE_LOWER, rightlb, -1,
7597 /* in case the variable is not active we need to check the object coefficient of the active variable */
7616 /* rounding the integer variable down is only a valid dual reduction if the object coefficient is zero or positive
7621 if( (scalar > 0 && SCIPisNegative(scip, objval)) || (scalar < 0 && SCIPisPositive(scip, objval)) )
7646 /* in case the variable is not active we need to check the object coefficient of the active variable */
7665 /* rounding the integer variable up is only a valid dual reduction if the object coefficient is zero or negative
7670 if( (scalar > 0 && SCIPisPositive(scip, objval)) || (scalar < 0 && SCIPisNegative(scip, objval)) )
7676/** For each variable we compute an alternative lower and upper bounds. That is, if the variable is not fixed to its
7677 * lower or upper bound the next reasonable lower or upper bound would be this alternative bound (implying that certain
7678 * values are not of interest). An alternative bound for a particular is only valied if the cumulative constarints are
7726 retcode = SCIPcreateWorstCaseProfile(scip, profile, consdata->nvars, consdata->vars, consdata->durations, consdata->demands);
7757 /* multi-aggregated variables should appear here since we mark the variables to be not mutlt-aggregated */
7824 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */
7885 /* for the statistic we count the number of jobs which are dual fixed due the information of all cumulative
7888 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nallconsdualfixs++ );
7894 /* In the current version SCIP, variable domains are single intervals. Meaning that domain holes or not
7895 * representable. To retrieve a potential dual reduction we using probing to check both branches. If one in
7898 SCIP_CALL( applyProbingVar(scip, vars, nvars, v, (SCIP_Real) lb, (SCIP_Real) alternativelbs[v],
7899 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
7904 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nallconsdualfixs++ );
7931 /* for the statistic we count the number of jobs which are dual fixed due the information of all cumulative
7934 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nallconsdualfixs++ );
7940 /* In the current version SCIP, variable domains are single intervals. Meaning that domain holes or not
7941 * representable. To retrieve a potential dual reduction we using probing to check both branches. If one in
7944 SCIP_CALL( applyProbingVar(scip, vars, nvars, v, (SCIP_Real) alternativeubs[v], (SCIP_Real) ub,
7945 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
7950 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nallconsdualfixs++ );
7977 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */
7979 SCIP_Bool* branched /**< pointer to store if a branching was applied, or NULL to avoid branching */
8013 SCIP_CALL( computeAlternativeBounds(scip, conss, nconss, local, alternativelbs, alternativeubs, downlocks, uplocks) );
8016 SCIP_CALL( applyAlternativeBoundsFixing(scip, vars, nvars, alternativelbs, alternativeubs, downlocks, uplocks,
8021 SCIP_CALL( applyAlternativeBoundsBranching(scip, vars, nvars, alternativelbs, alternativeubs, downlocks, uplocks, branched) );
8046 int* startvalues, /**< upper bounds on finishing time per job for activities from 0,..., nactivities -1 */
8137 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, rowname, -SCIPinfinity(scip), (SCIP_Real)bigcoversize,
8194 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->bcoverrows, consdata->nbcoverrows, consdata->bcoverrowssize) );
8225 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, rowname, -SCIPinfinity(scip), (SCIP_Real)smallcoversize,
8282 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->scoverrows, consdata->nscoverrows, consdata->scoverrowssize) );
8309 int* startindices; /* we sort the startvalues, so we need to know wich index of a job it corresponds to */
8310 int* endindices; /* we sort the endvalues, so we need to know wich index of a job it corresponds to */
8350 endvalues[j] = boundedConvertRealToInt(scip, SCIPvarGetUbLocal(consdata->vars[j])) + consdata->durations[j];
8402 /* we can create covering constraints for each pint in time in interval [curtime; nextprofilechange[ */
8433/** this method creates a row for time point curtime which insures the capacity restriction of the cumulative
8465 SCIP_CALL( collectBinaryVars(scip, consdata, &binvars, &coefs, &nbinvars, startindices, curtime, nstarted, nfinished) );
8468 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d[%d]", SCIPconsGetName(cons), nstarted-1, curtime);
8475 SCIP_CALL( SCIPcreateConsKnapsack(scip, &lincons, name, 0, NULL, NULL, (SCIP_Longint)(capacity),
8491 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), (SCIP_Real)capacity, FALSE, FALSE, SCIPconsIsRemovable(cons)) );
8510 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->demandrows, consdata->ndemandrows, consdata->demandrowssize) );
8523/** this method checks how many cumulatives can run at most at one time if this is greater than the capacity it creates
8537 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
8538 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
8591 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars);
8608 /* step forward until next job is released and see whether capacity constraint is met or not */
8617 SCIP_CALL( createCapacityRestriction(scip, cons, startindices, curtime, j+1, endindex, cutsasconss) );
8619 /* create for all points in time between the current event point and next start event point a row if the free
8632 SCIP_CALL( createCapacityRestriction(scip, cons, startindices, t, j+1, endindex, cutsasconss) );
8649/** creates LP rows corresponding to cumulative constraint; therefore, check each point in time if the maximal needed
8704 SCIP_Bool cutsasconss, /**< should the cumulative constraint create the cuts as constraints? */
8801 SCIPdebugMsg(scip, "cumulative constraint <%s> separated %d cuts\n", SCIPconsGetName(cons), ncuts);
8930/** this method creates a row for time point @p curtime which ensures the capacity restriction of the cumulative constraint */
8960 SCIP_CALL( collectIntVars(scip, consdata, &activevars, startindices, curtime, nstarted, nfinished, lower, &lhs ) );
8972 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), (SCIP_Real) lhs,
9011 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
9012 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
9046 createSelectedSortedEventpointsSol(scip, consdata, sol, starttimes, endtimes, startindices, endindices, &nvars, lower);
9064 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars);
9079 SCIP_CALL( createCapacityRestrictionIntvars(scip, cons, startindices, curtime, j+1, endindex, lower, cutoff) );
9102/** returns TRUE if all demands are smaller than the capacity of the cumulative constraint and if the total demand is
9124 /* if no activities are associated with this cumulative then this constraint is not infeasible, return */
9185/** remove jobs which have a duration or demand of zero (zero energy) or lay outside the efficient horizon [hmin, hmax);
9244 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nirrelevantjobs++ );
9278 /* jobs with a demand greater than the the capacity have to moved outside the time interval [hmin,hmax) */
9286 /* the jobs has to have an overlap with the efficient horizon otherwise it would be already removed */
9292 /* the job will at least run partly in the time interval [hmin,hmax) this means the problem is infeasible */
9298 SCIP_CALL( SCIPtightenVarUb(scip, var, (SCIP_Real)(consdata->hmin - duration), TRUE, cutoff, &tightened) );
9306 SCIP_CALL( SCIPtightenVarLb(scip, var, (SCIP_Real)(consdata->hmax), TRUE, cutoff, &tightened) );
9313 /* this job can run before or after the time interval [hmin,hmax) thus we create a bound disjunction
9343 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, name, 2, vartuple, boundtypetuple, boundtuple,
9393 SCIPdebugMsg(scip, "cumulative constraint <%s> has %d jobs left, cutoff %u\n", SCIPconsGetName(cons), consdata->nvars, *cutoff);
9398/** fix integer variable to upper bound if the rounding locks and the object coefficient are in favor of that */
9411 /* if SCIP is in probing mode or repropagation we cannot perform this dual reductions since this dual reduction
9417 /* rounding the variable to the upper bound is only a feasible dual reduction if the cumulative constraint
9429 /* rounding the integer variable up is only a valid dual reduction if the object coefficient is zero or negative
9443 SCIPdebugMsg(scip, "fix variable <%s> to upper bound %g\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var));
9450/** fix integer variable to lower bound if the rounding locks and the object coefficient are in favor of that */
9463 /* if SCIP is in probing mode or repropagation we cannot perform this dual reductions since this dual reduction
9469 /* rounding the variable to the lower bound is only a feasible dual reduction if the cumulative constraint
9490 SCIPdebugMsg(scip, "fix variable <%s> to lower bound %g\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var));
9541 SCIPdebugMsg(scip, "update cumulative condition (%d + %d > %d) to unary cumulative condition\n", mindemand1, mindemand2, *capacity);
9553 SCIPdebugMsg(scip, "cumulative condition: dividing demands by %" SCIP_LONGINT_FORMAT "\n", gcd);
9565/** divides demands by their greatest common divisor and divides capacity by the same value, rounding down the result;
9566 * in case the the smallest demands add up to more than the capacity we reductions all demands to one as well as the
9592 /**@todo sort items w.r.t. the demands, because we can stop earlier if the smaller weights are evaluated first */
9594 normalizeCumulativeCondition(scip, consdata->nvars, consdata->demands, &consdata->capacity, nchgcoefs, nchgsides);
9607 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
9622 SCIP_CALL_FINALLY( SCIPcreateWorstCaseProfile(scip, profile, nvars, vars, durations, demands), SCIPprofileFree(&profile) );
9642 /* If SCIP is repropagating the root node, it is not possible to decompose the constraints. This is the case since
9643 * the conflict analysis stores the constraint pointer for bound changes made by this constraint. These pointer
9644 * are used during the resolve propagation phase to explain bound changes. If we would decompose certain jobs into
9645 * a new cumulative constraint, the "old" pointer is not valid. More precise, the "old" constraint is not able to
9654 /* 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 */
9665 /* check if the current time point does not exceed the capacity w.r.t. worst case resource profile; if so we
9688 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
9712 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
9714 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
9722 SCIP_CALL( SCIPcreateConsCumulative(scip, &cons, name, nvars, vars, durations, demands, capacity,
9723 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
9763 SCIPdebugMsg(scip, "cumulative constraint <%s> adjust hmin <%d> -> <%d>\n", SCIPconsGetName(cons), consdata->hmin, hmin);
9772 SCIPdebugMsg(scip, "cumulative constraint <%s> adjust hmax <%d> -> <%d>\n", SCIPconsGetName(cons), consdata->hmax, hmax);
9799 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
9800 SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
9816/** presolve cumulative condition w.r.t. the earlier start times (est) and the hmin of the effective horizon
9818 * (1) If the latest completion time (lct) of a job is smaller or equal than hmin, the corresponding job can be removed
9819 * form the constraint. This is the case since it cannot effect any assignment within the effective horizon
9821 * (2) If the latest start time (lst) of a job is smaller or equal than hmin it follows that the this jobs can run
9822 * before the effective horizon or it overlaps with the effective horizon such that hmin in included. Hence, the
9825 * (3) If the earlier completion time (ect) of a job is smaller or equal than hmin, the cumulative is the only one
9826 * locking the corresponding variable down, and the objective coefficient of the start time variable is not
9829 * (4) If the earlier start time (est) of job is smaller than the hmin, the cumulative is the only one locking the
9830 * corresponding variable down, and the objective coefficient of the start time variable is not negative, than
9833 * (5) If the earlier start time (est) of job is smaller than the smallest earlier completion times of all other jobs
9834 * (lets denote this with minect), the cumulative is the only one locking the corresponding variable down, and the
9835 * objective coefficient of the start time variable is not negative, than removing the values {est+1,...,minect-1}
9838 * @note That method does not remove any variable form the arrays. It only marks the variables which are irrelevant for
9852 SCIP_Bool* irrelevants, /**< array mark those variables which are irrelevant for the cumulative condition */
9885 SCIPdebugMsg(scip, "check for irrelevant variable for cumulative condition (hmin %d) w.r.t. earlier start time\n", hmin);
9925 /* collect earlier start time (est), earlier completion time (ect), latest start time (lst), and latest completion
9945 /* (1) check if the job runs completely before the effective horizon; if so the job can be removed form the
9955 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nirrelevantjobs++ );
9959 /* (2) check if the jobs overlaps with the time point hmin if it overlaps at all with the effective horizon; if
9972 * We mark the job to be deletable. The removement together with the capacity reducion is done later
9981 /* for the statistic we count the number of jobs which always run during the effective horizon */
10000 /* (3) check if the job can finish before the effective horizon starts; if so and the job can be fixed to its
10001 * earliest start time (which implies that it finishes before the effective horizon starts), the job can be
10005 /* job can be removed from the constraint only if the integer start time variable can be fixed to its lower
10016 SCIPdebugMsg(scip, " variable <%s>[%d,%d] with duration <%d> is irrelevant due to dual fixing wrt EST\n",
10019 /* after fixing the start time variable to its lower bound, the (new) earliest completion time should be smaller or equal ti hmin */
10035 /* check if the cumulative constraint is the only one looking this variable down and if the objective function
10057 /* for the statistic we count the number of jobs which are dual fixed due the information of all cumulative
10066 /* In the current version SCIP, variable domains are single intervals. Meaning that domain holes or not
10067 * representable. To retrieve a potential dual reduction we using probing to check both branches. If one in
10071 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
10100/** presolve cumulative condition w.r.t. the latest completion times (lct) and the hmax of the effective horizon
10102 * (1) If the earliest start time (est) of a job is larger or equal than hmax, the corresponding job can be removed
10103 * form the constraint. This is the case since it cannot effect any assignment within the effective horizon
10105 * (2) If the earliest completion time (ect) of a job is larger or equal than hmax it follows that the this jobs can run
10106 * before the effective horizon or it overlaps with the effective horizon such that hmax in included. Hence, the
10109 * (3) If the latest start time (lst) of a job is larger or equal than hmax, the cumulative is the only one
10110 * locking the corresponding variable up, and the objective coefficient of the start time variable is not
10113 * (4) If the latest completion time (lct) of job is larger than the hmax, the cumulative is the only one locking the
10114 * corresponding variable up, and the objective coefficient of the start time variable is not positive, than
10115 * removing the values {hmax - p_j, ..., lst-1} form variable domain is dual feasible (p_j is the processing time
10118 * (5) If the latest completion time (lct) of job is smaller than the largerst latest start time of all other jobs
10119 * (lets denote this with maxlst), the cumulative is the only one locking the corresponding variable up, and the
10120 * objective coefficient of the start time variable is not positive, than removing the values {maxlst - p_j + 1,
10121 * ..., lst-1} form variable domain is dual feasible (p_j is the processing time of the corresponding job).
10123 * @note That method does not remove any variable form the arrays. It only marks the variables which are irrelevant for
10137 SCIP_Bool* irrelevants, /**< array mark those variables which are irrelevant for the cumulative condition */
10138 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */
10170 SCIPdebugMsg(scip, "check for irrelevant variable for cumulative condition (hmax %d) w.r.t. latest completion time\n", hmax);
10209 /* collect earlier start time (est), earlier completion time (ect), latest start time (lst), and latest completion
10228 /* (1) check if the job runs completely after the effective horizon; if so the job can be removed form the
10238 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nirrelevantjobs++ );
10245 /* (2) check if the jobs overlaps with the time point hmax if it overlaps at all with the effective horizon; if
10255 SCIPdebugMsg(scip, " variables <%s>[%d,%d] with duration <%d> is irrelevant due to no down lock\n",
10261 /* for the statistic we count the number of jobs which always run during the effective horizon */
10280 /* (3) check if the job can start after the effective horizon finishes; if so and the job can be fixed to its
10281 * latest start time (which implies that it starts after the effective horizon finishes), the job can be
10285 /* job can be removed from the constraint only if the integer start time variable can be fixed to its upper
10296 SCIPdebugMsg(scip, " variable <%s>[%d,%d] with duration <%d> is irrelevant due to dual fixing wrt LCT\n",
10299 /* after fixing the start time variable to its upper bound, the (new) latest start time should be greather or equal ti hmax */
10315 /* check if the cumulative constraint is the only one looking this variable down and if the objective function
10337 /* for the statistic we count the number of jobs which are dual fixed due the information of all cumulative
10346 /* In the current version SCIP, variable domains are single intervals. Meaning that domain holes or not
10347 * representable. To retrieve a potential dual reduction we using probing to check both branches. If one
10351 downimpllbs, downimplubs, downproplbs, downpropubs, upimpllbs, upimplubs, upproplbs, uppropubs,
10418 /* remove variables from the cumulative constraint which are marked to be deleted; we need to that in the reverse
10458/** stores all demands which are smaller than the capacity of those jobs that are running at 'curtime' */
10496 endtime = boundedConvertRealToInt(scip, SCIPvarGetUbGlobal(var)) + consdata->durations[varidx];
10498 /* check the end time of this job is larger than the curtime; in this case the job is still running */
10513/** this method creates a row for time point curtime which insures the capacity restriction of the cumulative
10546 collectDemands(scip, consdata, startindices, curtime, nstarted, nfinished, &demands, &ndemands);
10558 SCIP_CALL( SCIPsolveKnapsackExactly(scip, ndemands, demands, profits, (SCIP_Longint)consdata->capacity,
10588 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
10589 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
10609 /* if no activities are associated with this cumulative or the capacity is 1, then this constraint is redundant */
10615 SCIPdebugMsg(scip, "try to tighten capacity for cumulative constraint <%s> with capacity %d\n",
10638 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars);
10641 addEndingJobDemands(consdata, curtime, endtimes, endindices, &freecapacity, &endindex, nvars);
10657 SCIP_CALL( getHighestCapacityUsage(scip, cons, startindices, curtime, j+1, endindex, &newcapacity) );
10664 /* also those points in time, where the capacity limit is not exceeded, must be taken into account */
10671 /* capacity cannot be decreased if the demand sum over more than one job equals the capacity */
10707 SCIPdebug( SCIPdebugMsg(scip, "; changed additionally %d coefficients\n", (*nchgcoefs) - oldnchgcoefs); )
10760 if( mindemand + consdata->demands[j] > consdata->capacity && consdata->demands[j] < consdata->capacity )
10762 SCIPdebugMsg(scip, "+-+-+-+-+-+change demand of var<%s> from %d to capacity %d\n", SCIPvarGetName(consdata->vars[j]),
10788 lct_j = boundedConvertRealToInt(scip, SCIPvarGetUbLocal(consdata->vars[j])) + consdata->durations[j];
10799 lct_i = boundedConvertRealToInt(scip, SCIPvarGetUbLocal(consdata->vars[i])) + consdata->durations[i];
10813 SCIPdebugMsg(scip, "+-+-+-+-+-+change demand of var<%s> from %d to capacity %d\n", SCIPvarGetName(consdata->vars[j]),
10822 SCIPdebugMsg(scip, "+-+-+-+-+-+changed %d coefficients of variables of cumulative constraint<%s>\n",
10896 SCIP_CALL( SCIPcreateVar(scip, &aggrvar, name, (SCIP_Real)(est+shift), (SCIP_Real)lst, 0.0, SCIPvarGetType(var),
10899 SCIP_CALL( SCIPaggregateVars(scip, var, aggrvar, 1.0, -1.0, (SCIP_Real)shift, &infeasible, &redundant, &aggregated) );
10910 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, consdata->downlocks[v], consdata->uplocks[v]) );
10973 /* add all jobs which has a demand smaller than one half of the capacity but together with the smallest collected
10994 SCIP_CALL( createConsCumulative(scip, SCIPconsGetName(cons), nvars, vars, durations, demands, 1, consdata->hmin, consdata->hmax,
11034 /* in case the cumulative constraint is independent of every else, solve the cumulative problem and apply the
11039 SCIP_CALL( solveIndependentCons(scip, cons, conshdlrdata->maxnodes, nchgbds, nfixedvars, ndelconss, cutoff, unbounded) );
11045 SCIP_CALL( presolveConsEffectiveHorizon(scip, cons, nfixedvars, nchgcoefs, nchgsides, cutoff) );
11136 if( tcliquegraph->precedencematrix[node1][node2] || tcliquegraph->precedencematrix[node2][node1] )
11164 /* check if the node is adjacent to the given node (nodes and adjacent nodes are ordered by node index) */
11192/** analyzes if the given variable lower bound condition implies a precedence condition w.r.t. given duration for the
11226 /* if vlbcoef < 1 and ub(vlbvar) <= (duration - vlbconst)/(vlbcoef - 1) -> precedence condition */
11238 /* if vlbcoef > 1 and lb(vlbvar) >= (duration - vlbconst)/(vlbcoef - 1) -> precedence condition */
11247/** analyzes if the given variable upper bound condition implies a precedence condition w.r.t. given duration for the
11271/** get the corresponding index of the given variables; this in case of an active variable the problem index and for
11313 SCIP_CALL( SCIPreallocBufferArray(scip, &tcliquegraph->precedencematrix[v], size) ); /*lint !e866*/
11314 SCIP_CALL( SCIPreallocBufferArray(scip, &tcliquegraph->demandmatrix[v], size) ); /*lint !e866*/
11326 SCIP_CALL( SCIPallocBufferArray(scip, &tcliquegraph->precedencematrix[pos], tcliquegraph->size) ); /*lint !e866*/
11327 BMSclearMemoryArray(tcliquegraph->precedencematrix[pos], tcliquegraph->nnodes); /*lint !e866*/
11329 SCIP_CALL( SCIPallocBufferArray(scip, &tcliquegraph->demandmatrix[pos], tcliquegraph->size) ); /*lint !e866*/
11355/** use the variables bounds of SCIP to projected variables bound graph into a precedence garph
11357 * Let d be the (assumed) duration of variable x and consider a variable bound of the form b * x + c <= y. This
11358 * variable bounds implies a precedence condition x -> y (meaning job y starts after job x is finished) if:
11413 if( impliesVlbPrecedenceCondition(scip, vbdvars[b], vbdcoefs[b], vbdconsts[b], tcliquegraph->durations[idx2]) )
11432 if( impliesVubPrecedenceCondition(scip, var, vbdcoefs[b], vbdconsts[b], tcliquegraph->durations[idx1]) )
11446 /* check if the latest completion time of job1 is smaller than the earliest start time of job2 */
11447 if( SCIPisLE(scip, SCIPvarGetUbLocal(var) + tcliquegraph->durations[idx1], SCIPvarGetLbLocal(vars[b])) )
11450 /* check if the latest completion time of job2 is smaller than the earliest start time of job1 */
11451 if( SCIPisLE(scip, SCIPvarGetUbLocal(vars[b]) + tcliquegraph->durations[idx2], SCIPvarGetLbLocal(var)) )
11491/** constructs a non-overlapping graph w.r.t. given durations and available cumulative constraints */
11532 if( tcliquegraph->durations[idx1] == 0 || tcliquegraph->durations[idx1] > consdata->durations[i] )
11566 if( tcliquegraph->durations[idx2] == 0 || tcliquegraph->durations[idx2] > consdata->durations[j] )
11569 SCIPdebugMsg(scip, " *** variable <%s> and variable <%s>\n", SCIPvarGetName(vars[i]), SCIPvarGetName(vars[j]));
11584/** constructs a conflict set graph (undirected) which contains for each job a node and edge if the corresponding pair
11598 /* use the variables bounds of SCIP to project the variables bound graph inot a precedence graph */
11601 /* compute the transitive closure of the precedence graph and the number of in and out arcs */
11602 transitiveClosure(tcliquegraph->precedencematrix, tcliquegraph->ninarcs, tcliquegraph->noutarcs, tcliquegraph->nnodes);
11642 SCIP_CALL( SCIPcreateConsCumulative(scip, &cons, name, ncliquenodes, vars, durations, demands, 1,
11693 /* create a hash table to store all start time variables which are already covered by at least one clique */
11727 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,
11732 SCIPdebugMsg(scip, "tree nodes %d clique size %d (weight %d, status %d)\n", ntreenodes, ncliquenodes, cliqueweight, tcliquestatus);
11771 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->naddeddisjunctives += nconss );
11783 int distance /**< minimum distance between the start time of the job corresponding to var and the job corresponding to vbdvar */
11789 SCIP_CALL( SCIPcreateConsVarbound(scip, &cons, name, var, vbdvar, -1.0, -SCIPinfinity(scip), -(SCIP_Real)distance,
11801/** compute a minimum distance between the start times of the two given jobs and post it as variable bound constraint */
11833 /* get latest completion time (lct) of the source and the earliest start time (est) of sink */
11834 lct = boundedConvertRealToInt(scip, SCIPvarGetUbLocal(vars[source])) + tcliquegraph->durations[source];
11853 else if( tcliquegraph->precedencematrix[source][i] && tcliquegraph->precedencematrix[i][sink] )
11871 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,
11884 /* the minimum distance between the start times of source job and the sink job is the clique weight plus the
11900 * for each arc of the transitive closure of the precedence graph, we are computing a minimum distance between the
11962 SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->naddedvarbounds += nconss );
12002 /**@todo For the test sets, which we are considere, the durations are independent of the cumulative
12003 * constaints. Meaning each job has a fixed duration which is the same for all cumulative constraints. In
12004 * general this is not the case. Therefore, the question would be which duration should be used?
12122/** construct an incompatibility graph and search for precedence constraints (variables bounds) and unary cumulative
12163/** compute the constraint signature which is used to detect constraints which contain potentially the same set of variables */
12181 consdata->signature |= ((unsigned int)1 << ((unsigned int)SCIPvarGetIndex(vars[v]) % (sizeof(unsigned int) * 8)));
12187/** index comparison method of linear constraints: compares two indices of the variable set in the linear constraint */
12413 SCIPdebugMsg(scip, "<%s>[%d] + %g <= <%s>[%d]\n", SCIPvarGetName(vbdvars[b]), durations[j], vbdconsts[b], SCIPvarGetName(var), durations[i]);
12421 SCIP_CALL( SCIPaddVarVlb(scip, var, vbdvars[b], 1.0, (SCIP_Real) durations[j], &infeasible, &nlocalbdchgs) );
12447 SCIP_Bool solinfeasible, /**< was the solution already declared infeasible by a constraint handler? */
12465 SCIPdebugMsg(scip, "constraint enforcing %d useful cumulative constraints of %d constraints for %s solution\n", nusefulconss, nconss,
12529 SCIP_CALL( enforceSolution(scip, conss, nconss, sol, conshdlrdata->fillbranchcands, result) );
12562/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
12579 SCIPstatisticPrintf("time-table: lb=%" SCIP_LONGINT_FORMAT ", ub=%" SCIP_LONGINT_FORMAT ", cutoff=%" SCIP_LONGINT_FORMAT "\n",
12581 SCIPstatisticPrintf("edge-finder: lb=%" SCIP_LONGINT_FORMAT ", ub=%" SCIP_LONGINT_FORMAT ", cutoff=%" SCIP_LONGINT_FORMAT "\n",
12583 SCIPstatisticPrintf("overload: time-table=%" SCIP_LONGINT_FORMAT " time-time edge-finding=%" SCIP_LONGINT_FORMAT "\n",
12596/** presolving initialization method of constraint handler (called when presolving is about to begin) */
12610 /* remove jobs which have a duration or demand of zero (zero energy) or lay outside the effective horizon [hmin,
12620/** presolving deinitialization method of constraint handler (called after presolving has been finished) */
12642 SCIPstatisticPrintf("@11 added variables bounds constraints %d\n", conshdlrdata->naddedvarbounds);
12643 SCIPstatisticPrintf("@22 added disjunctive constraints %d\n", conshdlrdata->naddeddisjunctives);
12658/** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
12692 /* if constraint belongs to transformed problem space, drop bound change events on variables */
12739 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
12740 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
12743 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
12844 SCIP_CALL( separateConsOnIntegerVariables(scip, conss[c], NULL, FALSE, &separated, &cutoff) );
12905 SCIP_CALL( separateConsOnIntegerVariables(scip, conss[c], NULL, FALSE, &separated, &cutoff) );
12921 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, NULL, solinfeasible, result) );
12930 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, sol, solinfeasible, result) );
12960 SCIP_CALL( enforceSolution(scip, conss, nconss, NULL, conshdlrdata->fillbranchcands, result) );
13004 SCIPdebugMsg(scip, "propagate %d of %d useful cumulative constraints\n", nusefulconss, nconss);
13040 SCIP_CALL( propagateCons(scip, cons, conshdlrdata, SCIP_PRESOLTIMING_ALWAYS, &nchgbds, &ndelconss, &cutoff) );
13048 SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata, SCIP_PRESOLTIMING_ALWAYS, &nchgbds, &ndelconss, &cutoff) );
13059 SCIPdebugMsg(scip, "delete (locally) %d constraints and changed %d variable bounds\n", ndelconss, nchgbds);
13113 /* remove jobs which have a duration or demand of zero (zero energy) or lay outside the effective horizon [hmin,
13130 /* in the first round we create a disjunctive constraint containing those jobs which cannot run in parallel */
13143 SCIP_CALL( propagateCons(scip, cons, conshdlrdata, presoltiming, nchgbds, ndelconss, &cutoff) );
13147 if( !cutoff && !unbounded && conshdlrdata->dualpresolve && SCIPallowStrongDualReds(scip) && nconss > 1 && (presoltiming & SCIP_PRESOLTIMING_FAST) != 0 )
13157 /* combine different source and detect disjunctive constraints and variable bound constraints to improve the
13164 if( !cutoff && conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
13177 || *nchgcoefs > oldnchgcoefs || *nupgdconss > oldnupgdconss || *ndelconss > oldndelconss || *naddconss > oldnaddconss )
13209 SCIPdebugMsg(scip, "resolve propagation: variable <%s>, cumulative constraint <%s> (capacity %d, propagation %d, H=[%d,%d))\n",
13210 SCIPvarGetName(infervar), SCIPconsGetName(cons), consdata->capacity, inferInfoGetProprule(intToInferInfo(inferinfo)),
13215 infervar, intToInferInfo(inferinfo), boundtype, bdchgidx, relaxedbd, conshdlrdata->usebdwidening, NULL, result) );
13228 SCIPdebugMsg(scip, "lock cumulative constraint <%s> with nlockspos = %d, nlocksneg = %d\n", SCIPconsGetName(cons), nlockspos, nlocksneg);
13245 SCIP_CALL( SCIPaddVarLocksType(scip, vars[v], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
13303 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &vars[v], varmap, consmap, global, valid) );
13318 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
13400 SCIPdebugMsg(scip, "parse job <%s>, duration %d, demand %d\n", SCIPvarGetName(var), duration, demand);
13429 SCIP_CALL( SCIPcreateConsCumulative(scip, cons, name, nvars, vars, durations, demands, capacity,
13430 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
13469/** constraint method of constraint handler which returns the number of variables (if possible) */
13530 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecCumulative, NULL) );
13559 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropCumulative, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
13562 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpCumulative, consSepasolCumulative, CONSHDLR_SEPAFREQ,
13614 "constraints/" CONSHDLR_NAME "/fillbranchcands", "should branching candidates be added to storage?",
13637 "number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit)?",
13640 "constraints/" CONSHDLR_NAME "/detectdisjunctive", "search for conflict set via maximal cliques to detect disjunctive constraints",
13643 "constraints/" CONSHDLR_NAME "/detectvarbounds", "search for conflict set via maximal cliques to detect variable bound constraints",
13648 "constraints/" CONSHDLR_NAME "/usebdwidening", "should bound widening be used during the conflict analysis?",
13660 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
13682 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
13684 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
13716 SCIP_CALL( consdataCreate(scip, &consdata, vars, NULL, durations, demands, nvars, capacity, 0, INT_MAX, check) );
13740 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
13741 * method SCIPcreateConsCumulative(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
13743 * @see SCIPcreateConsCumulative() for information about the basic constraint flag configuration
13745 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
13752 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
13760 SCIP_CALL( SCIPcreateConsCumulative(scip, cons, name, nvars, vars, durations, demands, capacity,
13808/** set the right bound of the time axis to be considered (not including hmax) */ /*lint -e{715}*/
13930/** check for the given starting time variables with their demands and durations if the cumulative conditions for the
13937 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
13951 SCIP_CALL( checkCumulativeCondition(scip, sol, nvars, vars, durations, demands, capacity, hmin, hmax,
13974/** searches for a time point within the cumulative condition were the cumulative condition can be split */
13978 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
13987 SCIP_CALL( computeEffectiveHorizonCumulativeCondition(scip, nvars, vars, durations, demands, capacity,
13993/** presolve cumulative condition w.r.t. effective horizon by detecting irrelevant variables */
14004 SCIP_Bool* irrelevants, /**< array mark those variables which are irrelevant for the cumulative condition */
14014 SCIP_CALL( presolveConsEst(scip, nvars, vars, durations, hmin, hmax, downlocks, uplocks, cons,
14018 SCIP_CALL( presolveConsLct(scip, nvars, vars, durations, hmin, hmax, downlocks, uplocks, cons,
14029 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
14038 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
14086 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
14088 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
14089 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
14092 SCIP_CALL( respropCumulativeCondition(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
14093 infervar, intToInferInfo(inferinfo), boundtype, bdchgidx, relaxedbd, TRUE, explanation, result) );
14153 SCIPgmlWriteNode(file, (unsigned int)(size_t)var, SCIPvarGetName(var), "rectangle", color, NULL);
14172 SCIPgmlWriteArc(file, (unsigned int)(size_t)vbdvars[b], (unsigned int)(size_t)var, NULL, NULL);
14185 SCIPgmlWriteArc(file, (unsigned int)(size_t)var, (unsigned int)(size_t)vbdvars[b], NULL, NULL);
14205 SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)) /**< method to use an individual cumulative condition */
14229 * @note If the problem was solved to the earliest start times (ests) and latest start times (lsts) array contain the
14230 * solution values; If the problem was not solved these two arrays contain the global bounds at the time the sub
14238 SCIP_Real* objvals, /**< array of objective coefficients for each job (linear objective function), or NULL if none */
14246 SCIP_Longint maxnodes, /**< maximum number of branch-and-bound nodes to solve the single cumulative constraint (-1: no limit) */
14276 /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
14279 SCIP_CALL( conshdlrdata->solveCumulative(njobs, ests, lsts, objvals, durations, demands, capacity,
14286/** creates the worst case resource profile, that is, all jobs are inserted with the earliest start and latest
14293 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
14323 /* add each job with its earliest start and latest completion time into the resource profile */
14348 SCIP_CALL( SCIPprofileInsertCore(profile, impliedest, impliedlct, copydemands[v], &pos, &infeasible) );
14367/** computes w.r.t. the given worst case resource profile the first time point where the given capacity can be violated */ /*lint -e{715}*/
14397/** computes w.r.t. the given worst case resource profile the first time point where the given capacity is satisfied for sure */ /*lint -e{715}*/
static SCIP_RETCODE branch(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_RESULT *result)
Definition: branch_allfullstrong.c:87
static SCIP_RETCODE adjustOversizedJobBounds(SCIP *scip, SCIP_CONSDATA *consdata, int pos, int *nchgbds, int *naddconss, SCIP_Bool *cutoff)
Definition: cons_cumulative.c:9253
static SCIP_RETCODE createTcliqueGraph(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
Definition: cons_cumulative.c:12016
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:782
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:735
static void consdataCalcSignature(SCIP_CONSDATA *consdata)
Definition: cons_cumulative.c:12165
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:4610
static PROPRULE inferInfoGetProprule(INFERINFO inferinfo)
Definition: cons_cumulative.c:332
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:661
static SCIP_RETCODE getActiveVar(SCIP *scip, SCIP_VAR **var, int *scalar, int *constant)
Definition: cons_cumulative.c:1199
static SCIP_DECL_CONSINITPRE(consInitpreCumulative)
Definition: cons_cumulative.c:12598
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:9684
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:9842
static void subtractStartingJobDemands(SCIP_CONSDATA *consdata, int curtime, int *starttimes, int *startindices, int *freecapacity, int *idx, int nvars)
Definition: cons_cumulative.c:3338
static SCIP_RETCODE varMayRoundUp(SCIP *scip, SCIP_VAR *var, SCIP_Bool *roundable)
Definition: cons_cumulative.c:7629
static SCIP_DECL_EVENTEXEC(eventExecCumulative)
Definition: cons_cumulative.c:13494
static SCIP_Longint computeCoreWithInterval(int begin, int end, int ect, int lst)
Definition: cons_cumulative.c:410
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:7816
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:6763
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:7401
static SCIP_RETCODE createPrecedenceCons(SCIP *scip, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, int distance)
Definition: cons_cumulative.c:11778
static SCIP_Bool isConsIndependently(SCIP_CONS *cons)
Definition: cons_cumulative.c:3634
static SCIP_DECL_CONSENFOPS(consEnfopsCumulative)
Definition: cons_cumulative.c:12937
static SCIP_RETCODE separateConsOnIntegerVariables(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool lower, SCIP_Bool *separated, SCIP_Bool *cutoff)
Definition: cons_cumulative.c:8998
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:6395
static void conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
Definition: cons_cumulative.c:1825
static void freeTcliqueGraph(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
Definition: cons_cumulative.c:12097
static SCIP_Bool checkDemands(SCIP *scip, SCIP_CONS *cons)
Definition: cons_cumulative.c:9106
static SCIP_RETCODE createCoverCuts(SCIP *scip, SCIP_CONS *cons)
Definition: cons_cumulative.c:8298
static void consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
Definition: cons_cumulative.c:2163
static SCIP_RETCODE tightenUbTTEF(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *var, int duration, int demand, int est, int lst, int lct, int begin, int end, SCIP_Longint energy, int *bestub, int *inferinfos, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
Definition: cons_cumulative.c:4496
static SCIP_DECL_CONSCHECK(consCheckCumulative)
Definition: cons_cumulative.c:12967
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:5510
static SCIP_RETCODE computeImpliedEst(SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *addedvars, int *est)
Definition: cons_cumulative.c:429
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_Bool solinfeasible, SCIP_RESULT *result)
Definition: cons_cumulative.c:12440
static SCIP_RETCODE collectBranchingCands(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, int *nbranchcands)
Definition: cons_cumulative.c:3494
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:11008
static int computeEnergyContribution(SCIP_BTNODE *node)
Definition: cons_cumulative.c:6344
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:6539
static SCIP_DECL_CONSENFORELAX(consEnforelaxCumulative)
Definition: cons_cumulative.c:12928
static SCIP_RETCODE presolveConsEffectiveHorizon(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *nchgcoefs, int *nchgsides, SCIP_Bool *cutoff)
Definition: cons_cumulative.c:10379
static int boundedConvertRealToInt(SCIP *scip, SCIP_Real real)
Definition: cons_cumulative.c:308
static SCIP_RETCODE constraintNonOverlappingGraph(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss)
Definition: cons_cumulative.c:11493
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:7238
static SCIP_DECL_SOLVECUMULATIVE(solveCumulativeViaScipCp)
Definition: cons_cumulative.c:1437
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:7116
static SCIP_RETCODE detectRedundantConss(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, int *naddconss)
Definition: cons_cumulative.c:12126
static SCIP_RETCODE getNodeIdx(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_VAR *var, int *idx)
Definition: cons_cumulative.c:11275
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:7682
static SCIP_RETCODE removeRedundantConss(SCIP *scip, SCIP_CONS **conss, int nconss, int *ndelconss)
Definition: cons_cumulative.c:12202
static SCIP_RETCODE findPrecedenceConss(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int *naddconss)
Definition: cons_cumulative.c:11904
static SCIP_RETCODE fixIntegerVariableUb(SCIP *scip, SCIP_VAR *var, SCIP_Bool uplock, int *nfixedvars)
Definition: cons_cumulative.c:9400
static SCIP_RETCODE createCapacityRestriction(SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool cutsasconss)
Definition: cons_cumulative.c:8437
static void addEndingJobDemands(SCIP_CONSDATA *consdata, int curtime, int *endtimes, int *endindices, int *freecapacity, int *idx, int nvars)
Definition: cons_cumulative.c:3380
static INFERINFO getInferInfo(PROPRULE proprule, int data1, int data2)
Definition: cons_cumulative.c:369
static SCIP_RETCODE setupAndSolveCumulativeSubscip(SCIP *subscip, SCIP_Real *objvals, int *durations, int *demands, int njobs, int capacity, int hmin, int hmax, SCIP_Longint maxnodes, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *solved, SCIP_Bool *error)
Definition: cons_cumulative.c:1270
static TCLIQUE_SELECTADJNODES(tcliqueSelectadjnodesClique)
Definition: cons_cumulative.c:11150
static SCIP_DECL_CONSSEPALP(consSepalpCumulative)
Definition: cons_cumulative.c:12792
static int computeOverlap(int begin, int end, int est, int lst, int duration)
Definition: cons_cumulative.c:2769
static SCIP_Longint computeTotalEnergy(int *durations, int *demands, int njobs)
Definition: cons_cumulative.c:1244
static SCIP_RETCODE strengthenVarbounds(SCIP *scip, SCIP_CONS *cons, int *nchgbds, int *naddconss)
Definition: cons_cumulative.c:12343
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:3094
static SCIP_DECL_CONSRESPROP(consRespropCumulative)
Definition: cons_cumulative.c:13187
static SCIP_RETCODE removeIrrelevantJobs(SCIP *scip, SCIP_CONS *cons)
Definition: cons_cumulative.c:9189
static SCIP_DECL_CONSGETVARS(consGetVarsCumulative)
Definition: cons_cumulative.c:13449
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:824
static void updateEnvelope(SCIP *scip, SCIP_BTNODE *node)
Definition: cons_cumulative.c:5678
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:7067
static SCIP_DECL_SORTINDCOMP(compNodedataLct)
Definition: cons_cumulative.c:6381
static SCIP_DECL_CONSGETNVARS(consGetNVarsCumulative)
Definition: cons_cumulative.c:13471
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:2806
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:3273
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:7482
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyCumulative)
Definition: cons_cumulative.c:12545
static void normalizeDemands(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides)
Definition: cons_cumulative.c:9570
static SCIP_Bool inferInfoIsValid(INFERINFO inferinfo)
Definition: cons_cumulative.c:359
static void computeCoreEnergyAfter(SCIP_PROFILE *profile, int nvars, int *ests, int *lcts, int *coreEnergyAfterEst, int *coreEnergyAfterLct)
Definition: cons_cumulative.c:4247
static SCIP_RETCODE consCapacityConstraintsFinder(SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss)
Definition: cons_cumulative.c:8527
static SCIP_RETCODE createCumulativeCons(SCIP *scip, const char *name, TCLIQUE_GRAPH *tcliquegraph, int *cliquenodes, int ncliquenodes)
Definition: cons_cumulative.c:11612
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:4315
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:1933
static SCIP_RETCODE createCoverCutsTimepoint(SCIP *scip, SCIP_CONS *cons, int *startvalues, int time)
Definition: cons_cumulative.c:8043
static SCIP_RETCODE tightenLbTTEF(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *var, int duration, int demand, int est, int ect, int lct, int begin, int end, SCIP_Longint energy, int *bestlb, int *inferinfos, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
Definition: cons_cumulative.c:4383
static SCIP_RETCODE consdataDeletePos(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_CONS *cons, int pos)
Definition: cons_cumulative.c:2190
static SCIP_RETCODE propagateAllConss(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool local, int *nfixedvars, SCIP_Bool *cutoff, SCIP_Bool *branched)
Definition: cons_cumulative.c:7972
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:10127
static void traceThetaEnvelop(SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy)
Definition: cons_cumulative.c:6161
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:7329
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:2521
static SCIP_RETCODE consdataDropAllEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_cumulative.c:1891
static TCLIQUE_GETWEIGHTS(tcliqueGetweightsClique)
Definition: cons_cumulative.c:11120
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:563
static SCIP_RETCODE projectVbd(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph)
Definition: cons_cumulative.c:11366
static SCIP_RETCODE createDisjuctiveCons(SCIP *scip, SCIP_CONS *cons, int *naddconss)
Definition: cons_cumulative.c:10925
static SCIP_RETCODE deleteLambdaLeaf(SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node)
Definition: cons_cumulative.c:5798
static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss)
Definition: cons_cumulative.c:8658
static SCIP_RETCODE computeEffectiveHorizon(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss, int *nchgsides)
Definition: cons_cumulative.c:9738
static SCIP_RETCODE enforceSolution(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_Bool branch, SCIP_RESULT *result)
Definition: cons_cumulative.c:3581
static SCIP_RETCODE deleteTrivilCons(SCIP *scip, SCIP_CONS *cons, int *ndelconss, SCIP_Bool *cutoff)
Definition: cons_cumulative.c:9147
static SCIP_DECL_CONSPRINT(consPrintCumulative)
Definition: cons_cumulative.c:13263
static SCIP_RETCODE computeMinDistance(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int source, int sink, int *naddconss)
Definition: cons_cumulative.c:11803
static SCIP_RETCODE varMayRoundDown(SCIP *scip, SCIP_VAR *var, SCIP_Bool *roundable)
Definition: cons_cumulative.c:7580
static void collectDemands(SCIP *scip, SCIP_CONSDATA *consdata, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Longint **demands, int *ndemands)
Definition: cons_cumulative.c:10460
static SCIP_RETCODE createCapacityRestrictionIntvars(SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool lower, SCIP_Bool *cutoff)
Definition: cons_cumulative.c:8932
static SCIP_RETCODE computeImpliedLct(SCIP *scip, SCIP_VAR *var, int duration, SCIP_HASHMAP *addedvars, int *lct)
Definition: cons_cumulative.c:498
static SCIP_RETCODE findCumulativeConss(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int *naddconss)
Definition: cons_cumulative.c:11658
static SCIP_RETCODE tightenCoefs(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs)
Definition: cons_cumulative.c:10721
static SCIP_RETCODE tightenCapacity(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides)
Definition: cons_cumulative.c:10578
static SCIP_BTNODE * findResponsibleLambdaLeafTraceEnergy(SCIP_BTNODE *node)
Definition: cons_cumulative.c:6024
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:3888
static SCIP_RETCODE consdataFreeRows(SCIP *scip, SCIP_CONSDATA **consdata)
Definition: cons_cumulative.c:2063
static SCIP_RETCODE initializeDurations(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss)
Definition: cons_cumulative.c:11972
static SCIP_Bool impliesVlbPrecedenceCondition(SCIP *scip, SCIP_VAR *vlbvar, SCIP_Real vlbcoef, SCIP_Real vlbconst, int duration)
Definition: cons_cumulative.c:11198
static SCIP_RETCODE separateCoverCutsCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff)
Definition: cons_cumulative.c:8813
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
Definition: cons_cumulative.c:2114
static TCLIQUE_GETNNODES(tcliqueGetnnodesClique)
Definition: cons_cumulative.c:11111
static SCIP_DECL_CONSENFOLP(consEnfolpCumulative)
Definition: cons_cumulative.c:12919
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:3944
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:3673
static SCIP_DECL_CONSDELETE(consDeleteCumulative)
Definition: cons_cumulative.c:12684
static void initializeLocks(SCIP_CONSDATA *consdata, SCIP_Bool locked)
Definition: cons_cumulative.c:1913
static SCIP_BTNODE * findResponsibleLambdaLeafTraceEnvelop(SCIP_BTNODE *node)
Definition: cons_cumulative.c:6073
static SCIP_RETCODE fixIntegerVariableLb(SCIP *scip, SCIP_VAR *var, SCIP_Bool downlock, int *nfixedvars)
Definition: cons_cumulative.c:9452
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_cumulative.c:1780
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:4105
static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *violated, SCIP_Bool printreason)
Definition: cons_cumulative.c:2485
static void collectThetaSubtree(SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy)
Definition: cons_cumulative.c:6126
static int computeEstOmegaset(SCIP *scip, int duration, int demand, int capacity, int est, int lct, int energy)
Definition: cons_cumulative.c:6505
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:5301
static SCIP_RETCODE insertThetanode(SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node, SCIP_NODEDATA *nodedatas, int *nodedataidx, int *nnodedatas)
Definition: cons_cumulative.c:5907
static SCIP_DECL_CONSPARSE(consParseCumulative)
Definition: cons_cumulative.c:13342
static SCIP_DECL_CONSPRESOL(consPresolCumulative)
Definition: cons_cumulative.c:13070
static void traceLambdaEnvelop(SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy)
Definition: cons_cumulative.c:6278
static SCIP_RETCODE computePeak(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, int *timepoint)
Definition: cons_cumulative.c:3409
static SCIP_RETCODE consdataCollectLinkingCons(SCIP *scip, SCIP_CONSDATA *consdata)
Definition: cons_cumulative.c:2259
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:4961
static void transitiveClosure(SCIP_Bool **adjmatrix, int *ninarcs, int *noutarcs, int nnodes)
Definition: cons_cumulative.c:11461
static SCIP_RETCODE getHighestCapacityUsage(SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, int *bestcapacity)
Definition: cons_cumulative.c:10517
static SCIP_RETCODE constructIncompatibilityGraph(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss)
Definition: cons_cumulative.c:11588
static SCIP_RETCODE removeOversizedJobs(SCIP *scip, SCIP_CONS *cons, int *nchgbds, int *nchgcoefs, int *naddconss, SCIP_Bool *cutoff)
Definition: cons_cumulative.c:9359
static SCIP_DECL_CONSINITLP(consInitlpCumulative)
Definition: cons_cumulative.c:12753
static void updateKeyOnTrace(SCIP_BTNODE *node, SCIP_Real key)
Definition: cons_cumulative.c:5766
static SCIP_DECL_CONSEXITSOL(consExitsolCumulative)
Definition: cons_cumulative.c:12660
static SCIP_DECL_CONSSEPASOL(consSepasolCumulative)
Definition: cons_cumulative.c:12858
static SCIP_RETCODE consdataDropEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
Definition: cons_cumulative.c:1870
static void traceLambdaEnergy(SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy)
Definition: cons_cumulative.c:6221
static SCIP_DECL_CONSTRANS(consTransCumulative)
Definition: cons_cumulative.c:12711
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:9604
static SCIP_RETCODE separateConsBinaryRepresentation(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff)
Definition: cons_cumulative.c:8737
static void normalizeCumulativeCondition(SCIP *scip, int nvars, int *demands, int *capacity, int *nchgcoefs, int *nchgsides)
Definition: cons_cumulative.c:9499
static SCIP_Bool impliesVubPrecedenceCondition(SCIP *scip, SCIP_VAR *var, SCIP_Real vubcoef, SCIP_Real vubconst, int duration)
Definition: cons_cumulative.c:11253
static SCIP_RETCODE moveNodeToLambda(SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node)
Definition: cons_cumulative.c:5871
static SCIP_RETCODE consdataCatchEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_cumulative.c:1846
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss, SCIP_Bool *infeasible)
Definition: cons_cumulative.c:8701
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:2327
constraint handler for cumulative constraints
Constraint handler for knapsack constraints of the form , x binary and .
constraint handler for linking binary variables to a linking (continuous or integer) variable
static SCIP_RETCODE solveCumulative(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool local, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Longint maxnodes, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *error)
Definition: cons_optcumulative.c:1265
void SCIPbtnodeSetRightchild(SCIP_BTNODE *node, SCIP_BTNODE *right)
Definition: misc.c:9023
SCIP_BTNODE * SCIPbtnodeGetRightchild(SCIP_BTNODE *node)
Definition: misc.c:8892
SCIP_RETCODE SCIPbtnodeCreate(SCIP_BT *tree, SCIP_BTNODE **node, void *dataptr)
Definition: misc.c:8753
void SCIPbtnodeSetParent(SCIP_BTNODE *node, SCIP_BTNODE *parent)
Definition: misc.c:8995
void SCIPbtnodeSetLeftchild(SCIP_BTNODE *node, SCIP_BTNODE *left)
Definition: misc.c:9009
SCIP_BTNODE * SCIPbtnodeGetLeftchild(SCIP_BTNODE *node)
Definition: misc.c:8882
int SCIPgetHminCumulative(SCIP *scip, SCIP_CONS *cons)
Definition: cons_cumulative.c:13793
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:14025
SCIP_RETCODE SCIPgetBinvarsLinking(SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***binvars, int *nbinvars)
Definition: cons_linking.c:3779
SCIP_RETCODE SCIPsetSolveCumulative(SCIP *scip, SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)))
Definition: cons_cumulative.c:14203
SCIP_RETCODE SCIPcreateConsBasicSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
Definition: cons_setppc.c:9533
int * SCIPgetDurationsCumulative(SCIP *scip, SCIP_CONS *cons)
Definition: cons_cumulative.c:13899
SCIP_Bool SCIPexistsConsLinking(SCIP *scip, SCIP_VAR *linkvar)
Definition: cons_linking.c:3722
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:13975
SCIP_RETCODE SCIPaddCoefKnapsack(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Longint weight)
Definition: cons_knapsack.c:13831
SCIP_RETCODE SCIPvisualizeConsCumulative(SCIP *scip, SCIP_CONS *cons)
Definition: cons_cumulative.c:14099
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:13747
int SCIPcomputeHmax(SCIP *scip, SCIP_PROFILE *profile, int capacity)
Definition: cons_cumulative.c:14398
SCIP_CONS * SCIPgetConsLinking(SCIP *scip, SCIP_VAR *linkvar)
Definition: cons_linking.c:3740
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:3335
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:13933
SCIP_VAR ** SCIPgetVarsCumulative(SCIP *scip, SCIP_CONS *cons)
Definition: cons_cumulative.c:13851
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:13812
int * SCIPgetDemandsCumulative(SCIP *scip, SCIP_CONS *cons)
Definition: cons_cumulative.c:13915
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:14233
SCIP_RETCODE SCIPcreateConsLinking(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *linkvar, SCIP_VAR **binvars, SCIP_Real *vals, int nbinvars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_linking.c:3589
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:1091
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9664
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:13725
int SCIPgetHmaxCumulative(SCIP *scip, SCIP_CONS *cons)
Definition: cons_cumulative.c:13835
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:14074
int SCIPgetCapacityCumulative(SCIP *scip, SCIP_CONS *cons)
Definition: cons_cumulative.c:13883
SCIP_RETCODE SCIPnormalizeCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int *capacity, int *nchgcoefs, int *nchgsides)
Definition: cons_cumulative.c:13958
SCIP_RETCODE SCIPcreateWorstCaseProfile(SCIP *scip, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands)
Definition: cons_cumulative.c:14289
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:13994
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:5839
SCIP_Real * SCIPgetValsLinking(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linking.c:3823
SCIP_RETCODE SCIPsetHminCumulative(SCIP *scip, SCIP_CONS *cons, int hmin)
Definition: cons_cumulative.c:13767
int SCIPgetNVarsCumulative(SCIP *scip, SCIP_CONS *cons)
Definition: cons_cumulative.c:13867
SCIP_RETCODE SCIPsetHmaxCumulative(SCIP *scip, SCIP_CONS *cons, int hmax)
Definition: cons_cumulative.c:13809
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:13655
int SCIPcomputeHmin(SCIP *scip, SCIP_PROFILE *profile, int capacity)
Definition: cons_cumulative.c:14368
SCIP_RETCODE SCIPincludeConshdlrCumulative(SCIP *scip)
Definition: cons_cumulative.c:13521
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_copy.c:713
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:501
void SCIPgmlWriteArc(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:643
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:182
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3304
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3284
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3061
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3466
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3179
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3482
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2647
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:2298
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2535
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:4067
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIP_Longint SCIPcalcGreComDiv(SCIP_Longint val1, SCIP_Longint val2)
Definition: misc.c:9197
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:1203
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_param.c:111
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:904
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
Definition: scip_param.c:882
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:661
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_param.c:57
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: scip_branch.c:673
SCIP_RETCODE SCIPbranchVarHole(SCIP *scip, SCIP_VAR *var, SCIP_Real left, SCIP_Real right, SCIP_NODE **downchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1099
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:365
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_conflict.c:336
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:432
SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb)
Definition: scip_conflict.c:399
SCIP_RETCODE SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub)
Definition: scip_conflict.c:467
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip_conflict.c:314
SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var)
Definition: scip_conflict.c:655
SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var)
Definition: scip_conflict.c:631
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: scip_conflict.c:728
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:808
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4350
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:540
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:831
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre)))
Definition: scip_cons.c:492
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_cons.c:235
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:281
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_cons.c:181
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre)))
Definition: scip_cons.c:516
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:940
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:468
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:624
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4340
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:601
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:647
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:854
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:785
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2536
SCIP_RETCODE SCIPtransformConss(SCIP *scip, int nconss, SCIP_CONS **conss, SCIP_CONS **transconss)
Definition: scip_cons.c:1625
SCIP_RETCODE SCIPsetConsSeparated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool separate)
Definition: scip_cons.c:1296
SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial)
Definition: scip_cons.c:1271
SCIP_RETCODE SCIPsetConsEnforced(SCIP *scip, SCIP_CONS *cons, SCIP_Bool enforce)
Definition: scip_cons.c:1321
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_cons.c:997
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1812
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
Definition: scip_cons.c:1524
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1173
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1138
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:225
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:111
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:396
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:367
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:413
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1581
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONS *cons, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1398
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1604
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1646
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2176
SCIP_Real SCIPgetRowSolFeasibility(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2131
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1974
void SCIPupdateSolConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition: scip_sol.c:451
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1763
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:488
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:771
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:462
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:860
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:872
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:475
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:436
int SCIPconvertRealToInt(SCIP *scip, SCIP_Real real)
Definition: scip_numerics.c:1279
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:449
SCIP_Bool SCIPparseReal(SCIP *scip, const char *str, SCIP_Real *value, char **endptr)
Definition: scip_numerics.c:368
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6401
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:5210
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:2119
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:4380
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_var.c:10550
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_var.c:7069
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6651
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:728
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip_var.c:2499
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:5118
SCIP_RETCODE SCIPaddVarVlb(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vlbvar, SCIP_Real vlbcoef, SCIP_Real vlbconstant, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip_var.c:8621
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:5296
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2872
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_var.c:120
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:11057
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:10318
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_var.c:6964
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2736
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_var.c:184
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:4322
SCIP_RETCODE SCIPprofileInsertCore(SCIP_PROFILE *profile, int left, int right, int demand, int *pos, SCIP_Bool *infeasible)
Definition: misc.c:7097
int * SCIPprofileGetTimepoints(SCIP_PROFILE *profile)
Definition: misc.c:6904
SCIP_Bool SCIPprofileFindLeft(SCIP_PROFILE *profile, int timepoint, int *pos)
Definition: misc.c:6950
int SCIPprofileGetNTimepoints(SCIP_PROFILE *profile)
Definition: misc.c:6894
SCIP_RETCODE SCIPprofileCreate(SCIP_PROFILE **profile, int capacity)
Definition: misc.c:6832
SCIP_RETCODE SCIPprofileDeleteCore(SCIP_PROFILE *profile, int left, int right, int demand)
Definition: misc.c:7127
void SCIPprofilePrint(SCIP_PROFILE *profile, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: misc.c:6862
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortDownIntIntInt(int *intarray1, int *intarray2, int *intarray3, int len)
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5581
void SCIPsortInt(int *intarray, int len)
void SCIPstrCopySection(const char *str, char startchar, char endchar, char *token, int size, char **endptr)
Definition: misc.c:10985
Definition: multiprecision.hpp:66
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
Definition: scipdefplugins.c:37
default SCIP plugins
static SCIP_RETCODE separate(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
Main separation function.
Definition: sepa_flower.c:1219
Definition: struct_var.h:114
Definition: struct_misc.h:240
Definition: struct_misc.h:249
Definition: struct_cons.h:47
Definition: struct_cons.h:128
Definition: struct_event.h:218
Definition: struct_misc.h:139
Definition: struct_misc.h:90
Definition: struct_misc.h:211
Definition: struct_lp.h:205
Definition: struct_sol.h:74
Definition: struct_var.h:262
Definition: struct_scip.h:72
tclique user interface
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:1010