SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
constraint handler for cumulative constraints
Given:
The cumulative constraint ensures that for each point in time \(t\) \(\sum_{j: S_j \leq t < S_j + p_j} d_j \leq C\) holds.
Separation:
Propagation:
Definition in file cons_cumulative.c.
#include <assert.h>#include <string.h>#include "tclique/tclique.h"#include "scip/cons_cumulative.h"#include "scip/cons_linking.h"#include "scip/cons_knapsack.h"#include "scip/scipdefplugins.h"Go to the source code of this file.
Functions | |
| static SCIP_Bool | impliesVlbPrecedenceCondition (SCIP *scip, SCIP_VAR *vlbvar, SCIP_Real vlbcoef, SCIP_Real vlbconst, int duration) |
| static SCIP_Bool | impliesVubPrecedenceCondition (SCIP *scip, SCIP_VAR *var, SCIP_Real vubcoef, SCIP_Real vubconst, int duration) |
| static SCIP_RETCODE | getNodeIdx (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_VAR *var, int *idx) |
| static SCIP_RETCODE | projectVbd (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph) |
| static void | transitiveClosure (SCIP_Bool **adjmatrix, int *ninarcs, int *noutarcs, int nnodes) |
| static SCIP_RETCODE | constraintNonOverlappingGraph (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss) |
| static SCIP_RETCODE | constructIncompatibilityGraph (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss) |
| static SCIP_RETCODE | createCumulativeCons (SCIP *scip, const char *name, TCLIQUE_GRAPH *tcliquegraph, int *cliquenodes, int ncliquenodes) |
| static SCIP_RETCODE | findCumulativeConss (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int *naddconss) |
| static SCIP_RETCODE | createPrecedenceCons (SCIP *scip, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, int distance) |
| static SCIP_RETCODE | computeMinDistance (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int source, int sink, int *naddconss) |
| static SCIP_RETCODE | findPrecedenceConss (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int *naddconss) |
| static SCIP_RETCODE | initializeDurations (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss) |
| static SCIP_RETCODE | createTcliqueGraph (SCIP *scip, TCLIQUE_GRAPH **tcliquegraph) |
| static void | freeTcliqueGraph (SCIP *scip, TCLIQUE_GRAPH **tcliquegraph) |
| static SCIP_RETCODE | detectRedundantConss (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, int *naddconss) |
| static void | consdataCalcSignature (SCIP_CONSDATA *consdata) |
| static | SCIP_DECL_SORTINDCOMP (consdataCompVar) |
| static SCIP_RETCODE | removeRedundantConss (SCIP *scip, SCIP_CONS **conss, int nconss, int *ndelconss) |
| static SCIP_RETCODE | strengthenVarbounds (SCIP *scip, SCIP_CONS *cons, int *nchgbds, int *naddconss) |
| 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) |
Miscellaneous Methods | |
| static int | computeCoreWithInterval (int begin, int end, int ect, int lst) |
| static SCIP_RETCODE | computeImpliedEst (SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *addedvars, int *est) |
| static SCIP_RETCODE | computeImpliedLct (SCIP *scip, SCIP_VAR *var, int duration, SCIP_HASHMAP *addedvars, int *lct) |
| static SCIP_RETCODE | collectBinaryVars (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR ***vars, int **coefs, int *nvars, int *startindices, int curtime, int nstarted, int nfinished) |
| static SCIP_RETCODE | collectIntVars (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR ***activevars, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool lower, int *lhs) |
| static void | createSortedEventpoints (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *starttimes, int *endtimes, int *startindices, int *endindices, SCIP_Bool local) |
| static void | createSortedEventpointsSol (SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *starttimes, int *endtimes, int *startindices, int *endindices) |
| static void | createSelectedSortedEventpointsSol (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, int *starttimes, int *endtimes, int *startindices, int *endindices, int *nvars, SCIP_Bool lower) |
| static SCIP_RETCODE | getActiveVar (SCIP *scip, SCIP_VAR **var, int *scalar, int *constant) |
| static int | computeTotalEnergy (int *durations, int *demands, int njobs) |
Default method to solve a cumulative condition | |
| static SCIP_RETCODE | setupAndSolveCumulativeSubscip (SCIP *subscip, SCIP_Real *objvals, int *durations, int *demands, int njobs, int capacity, int hmin, int hmax, SCIP_Longint maxnodes, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *solved, SCIP_Bool *error) |
| static | SCIP_DECL_SOLVECUMULATIVE (solveCumulativeViaScipCp) |
Constraint handler data | |
Method used to create and free the constraint handler data when including and removing the cumulative constraint handler. | |
| static SCIP_RETCODE | conshdlrdataCreate (SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr) |
| static void | conshdlrdataFree (SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata) |
Constraint data methods | |
| static SCIP_RETCODE | consdataCatchEvents (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr) |
| static SCIP_RETCODE | consdataDropEvents (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos) |
| static SCIP_RETCODE | consdataDropAllEvents (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr) |
| static void | initializeLocks (SCIP_CONSDATA *consdata, SCIP_Bool locked) |
| static SCIP_RETCODE | consdataCreate (SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR **vars, SCIP_CONS **linkingconss, int *durations, int *demands, int nvars, int capacity, int hmin, int hmax, SCIP_Bool check) |
| static SCIP_RETCODE | consdataFreeRows (SCIP *scip, SCIP_CONSDATA **consdata) |
| static SCIP_RETCODE | consdataFree (SCIP *scip, SCIP_CONSDATA **consdata) |
| static void | consdataPrint (SCIP *scip, SCIP_CONSDATA *consdata, FILE *file) |
| static SCIP_RETCODE | consdataDeletePos (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_CONS *cons, int pos) |
| static SCIP_RETCODE | consdataCollectLinkingCons (SCIP *scip, SCIP_CONSDATA *consdata) |
Check methods | |
| 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) |
| static SCIP_RETCODE | checkCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *violated, SCIP_Bool printreason) |
Conflict analysis | |
| static SCIP_RETCODE | resolvePropagationCoretimes (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferdemand, int inferpeak, int relaxedpeak, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool usebdwidening, int *provedpeak, SCIP_Bool *explanation) |
| static int | computeOverlap (int begin, int end, int est, int lst, int duration) |
| static SCIP_RETCODE | analyzeEnergyRequirement (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int begin, int end, SCIP_VAR *infervar, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool usebdwidening, SCIP_Bool *explanation) |
| static SCIP_RETCODE | 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) |
Enforcement methods | |
| static SCIP_RETCODE | applyAlternativeBoundsBranching (SCIP *scip, SCIP_VAR **vars, int nvars, int *alternativelbs, int *alternativeubs, int *downlocks, int *uplocks, SCIP_Bool *branched) |
| static void | subtractStartingJobDemands (SCIP_CONSDATA *consdata, int curtime, int *starttimes, int *startindices, int *freecapacity, int *idx, int nvars) |
| static void | addEndingJobDemands (SCIP_CONSDATA *consdata, int curtime, int *endtimes, int *endindices, int *freecapacity, int *idx, int nvars) |
| static SCIP_RETCODE | computePeak (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, int *timepoint) |
| static SCIP_RETCODE | collectBranchingCands (SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, int *nbranchcands) |
| static SCIP_RETCODE | enforceSolution (SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_Bool branch, SCIP_RESULT *result) |
Linear relaxations | |
| static SCIP_RETCODE | createCoverCutsTimepoint (SCIP *scip, SCIP_CONS *cons, int *startvalues, int time) |
| static SCIP_RETCODE | createCoverCuts (SCIP *scip, SCIP_CONS *cons) |
| static SCIP_RETCODE | createCapacityRestriction (SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool cutsasconss) |
| static SCIP_RETCODE | consCapacityConstraintsFinder (SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss) |
| static SCIP_RETCODE | createRelaxation (SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss) |
| static SCIP_RETCODE | addRelaxation (SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss, SCIP_Bool *infeasible) |
| static SCIP_RETCODE | separateConsBinaryRepresentation (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | separateCoverCutsCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | createCapacityRestrictionIntvars (SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool lower) |
| static SCIP_RETCODE | separateConsOnIntegerVariables (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool lower, SCIP_Bool *separated) |
Presolving | |
| static SCIP_Bool | checkDemands (SCIP *scip, SCIP_CONS *cons) |
| static SCIP_RETCODE | deleteTrivilCons (SCIP *scip, SCIP_CONS *cons, int *ndelconss, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | removeIrrelevantJobs (SCIP *scip, SCIP_CONS *cons) |
| static SCIP_RETCODE | adjustOversizedJobBounds (SCIP *scip, SCIP_CONSDATA *consdata, int pos, int *nchgbds, int *naddconss, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | removeOversizedJobs (SCIP *scip, SCIP_CONS *cons, int *nchgbds, int *nchgcoefs, int *naddconss, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | fixIntegerVariableUb (SCIP *scip, SCIP_VAR *var, SCIP_Bool uplock, int *nfixedvars) |
| static SCIP_RETCODE | fixIntegerVariableLb (SCIP *scip, SCIP_VAR *var, SCIP_Bool downlock, int *nfixedvars) |
| static SCIP_RETCODE | normalizeCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int *capacity, int *nchgcoefs, int *nchgsides) |
| static SCIP_RETCODE | normalizeDemands (SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides) |
| static SCIP_RETCODE | computeEffectiveHorizonCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *hmin, int *hmax, int *split) |
| static SCIP_RETCODE | createConsCumulative (SCIP *scip, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) |
| static SCIP_RETCODE | computeEffectiveHorizon (SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss, int *nchgsides) |
| 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) |
| static SCIP_RETCODE | presolveConsLct (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | presolveConsEffectiveHorizon (SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *nchgcoefs, int *nchgsides, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | collectDemands (SCIP *scip, SCIP_CONSDATA *consdata, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Longint **demands, int *ndemands) |
| static SCIP_RETCODE | getHighestCapacityUsage (SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, int *bestcapacity) |
| static SCIP_RETCODE | tightenCapacity (SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides) |
| static SCIP_RETCODE | tightenCoefs (SCIP *scip, SCIP_CONS *cons, int *nchgcoefs) |
| static SCIP_RETCODE | createDisjuctiveCons (SCIP *scip, SCIP_CONS *cons, int *naddconss) |
| 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) |
TClique Graph callbacks | |
| static | TCLIQUE_GETNNODES (tcliqueGetnnodesClique) |
| static | TCLIQUE_GETWEIGHTS (tcliqueGetweightsClique) |
| static | TCLIQUE_ISEDGE (tcliqueIsedgeClique) |
| static | TCLIQUE_SELECTADJNODES (tcliqueSelectadjnodesClique) |
| static | TCLIQUE_NEWSOL (tcliqueNewsolClique) |
Callback methods of constraint handler | |
| static | SCIP_DECL_CONSHDLRCOPY (conshdlrCopyCumulative) |
| static | SCIP_DECL_CONSFREE (consFreeCumulative) |
| static | SCIP_DECL_CONSINITPRE (consInitpreCumulative) |
| static | SCIP_DECL_CONSEXITSOL (consExitsolCumulative) |
| static | SCIP_DECL_CONSDELETE (consDeleteCumulative) |
| static | SCIP_DECL_CONSTRANS (consTransCumulative) |
| static | SCIP_DECL_CONSINITLP (consInitlpCumulative) |
| static | SCIP_DECL_CONSSEPALP (consSepalpCumulative) |
| static | SCIP_DECL_CONSSEPASOL (consSepasolCumulative) |
| static | SCIP_DECL_CONSENFOLP (consEnfolpCumulative) |
| static | SCIP_DECL_CONSENFORELAX (consEnforelaxCumulative) |
| static | SCIP_DECL_CONSENFOPS (consEnfopsCumulative) |
| static | SCIP_DECL_CONSCHECK (consCheckCumulative) |
| static | SCIP_DECL_CONSPROP (consPropCumulative) |
| static | SCIP_DECL_CONSPRESOL (consPresolCumulative) |
| static | SCIP_DECL_CONSRESPROP (consRespropCumulative) |
| static | SCIP_DECL_CONSLOCK (consLockCumulative) |
| static | SCIP_DECL_CONSPRINT (consPrintCumulative) |
| static | SCIP_DECL_CONSCOPY (consCopyCumulative) |
| static | SCIP_DECL_CONSPARSE (consParseCumulative) |
| static | SCIP_DECL_CONSGETVARS (consGetVarsCumulative) |
| static | SCIP_DECL_CONSGETNVARS (consGetNVarsCumulative) |
Callback methods of event handler | |
| static | SCIP_DECL_EVENTEXEC (eventExecCumulative) |
Interface methods | |
| SCIP_RETCODE | SCIPincludeConshdlrCumulative (SCIP *scip) |
| 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) |
| SCIP_RETCODE | SCIPcreateConsBasicCumulative (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity) |
| SCIP_RETCODE | SCIPsetHminCumulative (SCIP *scip, SCIP_CONS *cons, int hmin) |
| int | SCIPgetHminCumulative (SCIP *scip, SCIP_CONS *cons) |
| SCIP_RETCODE | SCIPsetHmaxCumulative (SCIP *scip, SCIP_CONS *cons, int hmax) |
| int | SCIPgetHmaxCumulative (SCIP *scip, SCIP_CONS *cons) |
| SCIP_VAR ** | SCIPgetVarsCumulative (SCIP *scip, SCIP_CONS *cons) |
| int | SCIPgetNVarsCumulative (SCIP *scip, SCIP_CONS *cons) |
| int | SCIPgetCapacityCumulative (SCIP *scip, SCIP_CONS *cons) |
| int * | SCIPgetDurationsCumulative (SCIP *scip, SCIP_CONS *cons) |
| int * | SCIPgetDemandsCumulative (SCIP *scip, SCIP_CONS *cons) |
| SCIP_RETCODE | SCIPcheckCumulativeCondition (SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *violated, SCIP_CONS *cons, SCIP_Bool printreason) |
| SCIP_RETCODE | SCIPnormalizeCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int *capacity, int *nchgcoefs, int *nchgsides) |
| SCIP_RETCODE | SCIPsplitCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *hmin, int *hmax, int *split) |
| SCIP_RETCODE | SCIPpresolveCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff) |
| SCIP_RETCODE | SCIPpropCumulativeCondition (SCIP *scip, SCIP_PRESOLTIMING presoltiming, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) |
| SCIP_RETCODE | 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) |
| SCIP_RETCODE | SCIPvisualizeConsCumulative (SCIP *scip, SCIP_CONS *cons) |
| SCIP_RETCODE | SCIPsetSolveCumulative (SCIP *scip, SCIP_DECL_SOLVECUMULATIVE((*solveCumulative))) |
| SCIP_RETCODE | SCIPsolveCumulative (SCIP *scip, int njobs, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Real *objvals, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint maxnodes, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *error) |
| SCIP_RETCODE | SCIPcreateWorstCaseProfile (SCIP *scip, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands) |
| int | SCIPcomputeHmin (SCIP *scip, SCIP_PROFILE *profile, int capacity) |
| int | SCIPcomputeHmax (SCIP *scip, SCIP_PROFILE *profile, int capacity) |
Inference Information Methods | |
An inference information can be passed with each domain reduction to SCIP. This information is passed back to the constraint handler if the corresponding bound change has to be explained. It can be used to store information which help to construct a reason/explanation for a bound change. The inference information is limited to size of integer. In case of the cumulative constraint handler we store the used propagation algorithms for that particular bound change and the earliest start and latest completion time of all jobs in the conflict set. | |
| enum | Proprule { PROPRULE_1, PROPRULE_2, PROPRULE_3, PROPRULE_4, PROPRULE_INVALID, PROPRULE_INVALID = 0, PROPRULE_1 = 1, PROPRULE_2 = 2, PROPRULE_3 = 3, PROPRULE_4 = 4, PROPRULE_1_CORETIMES = 1, PROPRULE_2_EDGEFINDING = 2, PROPRULE_3_TTEF = 3, PROPRULE_1_RHS = 1, PROPRULE_1_LHS = 2, PROPRULE_1_RANGEDROW = 3, PROPRULE_INVALID = 0, PROPRULE_1, PROPRULE_2, PROPRULE_3, PROPRULE_4, PROPRULE_INVALID, PROPRULE_1, PROPRULE_2, PROPRULE_3, PROPRULE_4, PROPRULE_0, PROPRULE_1, PROPRULE_INTLB, PROPRULE_INTUB, PROPRULE_INVALID } |
| typedef enum Proprule | PROPRULE |
| typedef struct InferInfo | INFERINFO |
| static INFERINFO | intToInferInfo (int i) |
| static int | inferInfoToInt (INFERINFO inferinfo) |
| static PROPRULE | inferInfoGetProprule (INFERINFO inferinfo) |
| static int | inferInfoGetData1 (INFERINFO inferinfo) |
| static int | inferInfoGetData2 (INFERINFO inferinfo) |
| static INFERINFO | getInferInfo (PROPRULE proprule, int data1, int data2) |
Propagation | |
| typedef struct SCIP_NodeData | SCIP_NODEDATA |
| static SCIP_Bool | isConsIndependently (SCIP *scip, SCIP_CONS *cons) |
| static SCIP_RETCODE | solveIndependentCons (SCIP *scip, SCIP_CONS *cons, SCIP_Longint maxnodes, int *nchgbds, int *nfixedvars, int *ndelconss, SCIP_Bool *cutoff, SCIP_Bool *unbounded) |
| static SCIP_RETCODE | analyseInfeasibelCoreInsertion (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferduration, int inferdemand, int inferpeak, SCIP_Bool usebdwidening, SCIP_Bool *initialized, SCIP_Bool *explanation) |
| static SCIP_RETCODE | coretimesUpdateLb (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, SCIP_PROFILE *profile, int idx, int *nchgbds, SCIP_Bool usebdwidening, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *infeasible) |
| static SCIP_RETCODE | coretimesUpdateUb (SCIP *scip, SCIP_VAR *var, int duration, int demand, int capacity, SCIP_CONS *cons, SCIP_PROFILE *profile, int idx, int *nchgbds) |
| static SCIP_RETCODE | computeCoreEngeryAfter (SCIP *scip, SCIP_PROFILE *profile, int nvars, int *ests, int *lcts, int *coreEnergyAfterEst, int *coreEnergyAfterLct) |
| static void | collectDataTTEF (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int hmin, int hmax, int *permests, int *ests, int *permlcts, int *lcts, int *ects, int *lsts, int *flexenergies) |
| static SCIP_RETCODE | tightenLbTTEF (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *var, int duration, int demand, int est, int ect, int lct, int begin, int end, int energy, int *bestlb, int *inferinfos, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | tightenUbTTEF (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *var, int duration, int demand, int est, int lst, int lct, int begin, int end, int energy, int *bestub, int *inferinfos, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) |
| 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) |
| static SCIP_RETCODE | propagateLbTTEF (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, int *newlbs, int *newubs, int *lbinferinfos, int *ubinferinfos, int *ects, int *flexenergies, int *perm, int *ests, int *lcts, int *coreEnergyAfterEst, int *coreEnergyAfterLct, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | propagateTTEF (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | propagateTimetable (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | createNodedata (SCIP *scip, SCIP_NODEDATA **nodedata) |
| static void | freeNodedata (SCIP *scip, SCIP_NODEDATA **nodedata) |
| static SCIP_RETCODE | updateEnvelop (SCIP *scip, SCIP_BTNODE *node) |
| static void | updateKeyOnTrace (SCIP_BTNODE *node, SCIP_Real key) |
| static SCIP_RETCODE | deleteLambdaLeaf (SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node) |
| static SCIP_RETCODE | moveNodeToLambda (SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node) |
| static SCIP_RETCODE | insertThetanode (SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node, SCIP_NODEDATA **nodedatas, int *nnodedatas) |
| static SCIP_BTNODE * | findResponsibleLambdaLeafTraceEnergy (SCIP_BTNODE *node) |
| static SCIP_BTNODE * | findResponsibleLambdaLeafTraceEnvelop (SCIP_BTNODE *node) |
| static void | collectThetaSubtree (SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy) |
| static void | traceThetaEnvelop (SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy) |
| static void | traceLambdaEnergy (SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy) |
| static void | traceLambdaEnvelop (SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy) |
| static int | computeEnergyContribution (SCIP_BTNODE *node) |
| static | SCIP_DECL_SORTPTRCOMP (compNodeEst) |
| static | SCIP_DECL_SORTPTRCOMP (compNodedataLct) |
| static SCIP_RETCODE | analyzeConflictOverload (SCIP *scip, SCIP_BTNODE **leaves, int capacity, int nleaves, int est, int lct, int reportedenergy, SCIP_Bool propest, int shift, SCIP_Bool usebdwidening, SCIP_Bool *initialized, SCIP_Bool *explanation) |
| static int | computeEstOmegaset (SCIP *scip, int duration, int demand, int capacity, int est, int lct, int energy) |
| static SCIP_RETCODE | inferboundsEdgeFinding (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS *cons, SCIP_BT *tree, SCIP_BTNODE **leaves, int capacity, int ncands, SCIP_Bool propest, int shift, SCIP_Bool *initialized, SCIP_Bool *explanation, int *nchgbds, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | 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) |
| 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) |
| static SCIP_RETCODE | consCheckRedundancy (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *redundant) |
| static SCIP_RETCODE | createCoreProfile (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | propagateCumulativeCondition (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PRESOLTIMING presoltiming, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *redundant, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | propagateCons (SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PRESOLTIMING presoltiming, int *nchgbds, int *ndelconss, SCIP_Bool *cutoff) |
| 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) |
| static SCIP_RETCODE | varMayRoundDown (SCIP *scip, SCIP_VAR *var, SCIP_Bool *roundable) |
| static SCIP_RETCODE | varMayRoundUp (SCIP *scip, SCIP_VAR *var, SCIP_Bool *roundable) |
| static SCIP_RETCODE | computeAlternativeBounds (SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool local, int *alternativelbs, int *alternativeubs, int *downlocks, int *uplocks) |
| static SCIP_RETCODE | applyAlternativeBoundsFixing (SCIP *scip, SCIP_VAR **vars, int nvars, int *alternativelbs, int *alternativeubs, int *downlocks, int *uplocks, int *nfixedvars, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | propagateAllConss (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, SCIP_Bool local, int *nfixedvars, SCIP_Bool *cutoff, SCIP_Bool *branched) |
| #define CONSHDLR_NAME "cumulative" |
Definition at line 58 of file cons_cumulative.c.
Referenced by applyAlternativeBoundsFixing(), checkOverloadViaThetaTree(), computeEffectiveHorizon(), coretimesUpdateLb(), coretimesUpdateUb(), createCoreProfile(), enforceConstraint(), findCumulativeConss(), findPrecedenceConss(), inferboundsEdgeFinding(), presolveConsEst(), presolveConsLct(), propagateLbTTEF(), propagateTimetable(), propagateTTEF(), propagateUbTTEF(), removeIrrelevantJobs(), SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSENFOPS(), SCIP_DECL_CONSEXITSOL(), SCIP_DECL_CONSFREE(), SCIP_DECL_CONSHDLRCOPY(), SCIP_DECL_CONSINITLP(), SCIP_DECL_CONSPRESOL(), SCIP_DECL_CONSPROP(), SCIP_DECL_CONSRESPROP(), SCIP_DECL_CONSSEPALP(), SCIP_DECL_CONSSEPASOL(), SCIPcreateConsCumulative(), SCIPgetCapacityCumulative(), SCIPgetDemandsCumulative(), SCIPgetDurationsCumulative(), SCIPgetHmaxCumulative(), SCIPgetHminCumulative(), SCIPgetNVarsCumulative(), SCIPgetVarsCumulative(), SCIPincludeConshdlrCumulative(), SCIPpropCumulativeCondition(), SCIPsetHmaxCumulative(), SCIPsetHminCumulative(), SCIPsetSolveCumulative(), and SCIPsolveCumulative().
| #define CONSHDLR_DESC "cumulative constraint handler" |
Definition at line 59 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define CONSHDLR_SEPAPRIORITY 2100000 |
priority of the constraint handler for separation
Definition at line 60 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define CONSHDLR_ENFOPRIORITY -2040000 |
priority of the constraint handler for constraint enforcing
Definition at line 61 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define CONSHDLR_CHECKPRIORITY -3030000 |
priority of the constraint handler for checking feasibility
Definition at line 62 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define CONSHDLR_SEPAFREQ 1 |
frequency for separating cuts; zero means to separate only in the root node
Definition at line 63 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define CONSHDLR_PROPFREQ 1 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 64 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define CONSHDLR_EAGERFREQ 100 |
frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only
Definition at line 65 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define CONSHDLR_MAXPREROUNDS -1 |
maximal number of presolving rounds the constraint handler participates in (-1: no limit)
Definition at line 68 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 69 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 70 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define CONSHDLR_NEEDSCONS TRUE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 71 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS |
Definition at line 73 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
Definition at line 74 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_USEBINVARS FALSE |
should the binary representation be used?
Definition at line 86 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_LOCALCUTS FALSE |
should cuts be added only locally?
Definition at line 87 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_USECOVERCUTS TRUE |
should covering cuts be added?
Definition at line 88 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_CUTSASCONSS TRUE |
should the cuts be created as knapsack constraints?
Definition at line 89 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_SEPAOLD TRUE |
shall old sepa algo be applied?
Definition at line 90 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_TTINFER TRUE |
should time-table (core-times) propagator be used to infer bounds?
Definition at line 93 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_EFCHECK FALSE |
should edge-finding be used to detect an overload?
Definition at line 94 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_EFINFER FALSE |
should edge-finding be used to infer bounds?
Definition at line 95 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_USEADJUSTEDJOBS FALSE |
should during edge-finding jobs be adusted which run on the border of the effective time horizon?
Definition at line 96 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_TTEFCHECK TRUE |
should time-table edge-finding be used to detect an overload?
Definition at line 97 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_TTEFINFER TRUE |
should time-table edge-finding be used to infer bounds?
Definition at line 98 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_DUALPRESOLVE TRUE |
should dual presolving be applied?
Definition at line 101 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_COEFTIGHTENING FALSE |
should coeffisient tightening be applied?
Definition at line 102 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_NORMALIZE TRUE |
should demands and capacity be normalized?
Definition at line 103 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_PRESOLPAIRWISE TRUE |
should pairwise constraint comparison be performed in presolving?
Definition at line 104 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_DISJUNCTIVE TRUE |
extract disjunctive constraints?
Definition at line 105 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_DETECTDISJUNCTIVE TRUE |
search for conflict set via maximal cliques to detect disjunctive constraints
Definition at line 106 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_DETECTVARBOUNDS TRUE |
search for conflict set via maximal cliques to detect variable bound constraints
Definition at line 107 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_MAXNODES 10000LL |
number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit)
Definition at line 108 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_FILLBRANCHCANDS FALSE |
should branching candidates be added to storage?
Definition at line 111 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define DEFAULT_USEBDWIDENING TRUE |
should bound widening be used during conflict analysis?
Definition at line 114 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
| #define EVENTHDLR_NAME "cumulative" |
Definition at line 123 of file cons_cumulative.c.
Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludeConshdlrCumulative().
| #define EVENTHDLR_DESC "bound change event handler for cumulative constraints" |
Definition at line 124 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
Definition at line 257 of file cons_cumulative.c.
| typedef struct InferInfo INFERINFO |
Definition at line 274 of file cons_cumulative.c.
| typedef struct SCIP_NodeData SCIP_NODEDATA |
Definition at line 5687 of file cons_cumulative.c.
| enum Proprule |
Propagation rules
Definition at line 251 of file cons_cumulative.c.
|
static |
converts an integer into an inference information
| i | integer to convert |
Definition at line 278 of file cons_cumulative.c.
References inferInfoToInt().
Referenced by propagateTTEF(), SCIP_DECL_CONSRESPROP(), and SCIPrespropCumulativeCondition().
|
static |
converts an inference information into an int
| inferinfo | inference information to convert |
Definition at line 291 of file cons_cumulative.c.
References inferInfoGetProprule().
Referenced by coretimesUpdateLb(), coretimesUpdateUb(), inferboundsEdgeFinding(), intToInferInfo(), propagateLbTTEF(), propagateUbTTEF(), tightenLbTTEF(), and tightenUbTTEF().
returns the propagation rule stored in the inference information
| inferinfo | inference information to convert |
Definition at line 300 of file cons_cumulative.c.
References inferInfoGetData1().
Referenced by inferInfoToInt(), resolvePropagationCoretimes(), respropCumulativeCondition(), and SCIP_DECL_CONSRESPROP().
|
static |
returns data field one of the inference information
| inferinfo | inference information to convert |
Definition at line 309 of file cons_cumulative.c.
References inferInfoGetData2().
Referenced by inferInfoGetProprule(), propagateTTEF(), resolvePropagationCoretimes(), and respropCumulativeCondition().
|
static |
returns data field two of the inference information
| inferinfo | inference information to convert |
Definition at line 318 of file cons_cumulative.c.
References getInferInfo().
Referenced by inferInfoGetData1(), propagateTTEF(), resolvePropagationCoretimes(), and respropCumulativeCondition().
constructs an inference information out of a propagation rule, an earliest start and a latest completion time
| proprule | propagation rule that deduced the value |
| data1 | data field one |
| data2 | data field two |
Definition at line 328 of file cons_cumulative.c.
References computeCoreWithInterval().
Referenced by coretimesUpdateLb(), coretimesUpdateUb(), inferboundsEdgeFinding(), inferInfoGetData2(), propagateLbTTEF(), propagateUbTTEF(), tightenLbTTEF(), and tightenUbTTEF().
|
static |
compute the core of a job which lies in certain interval [begin, end)
| begin | begin of the interval |
| end | end of the interval |
| ect | earliest completion time |
| lst | latest start time |
Definition at line 363 of file cons_cumulative.c.
References computeImpliedEst(), and MAX.
Referenced by collectDataTTEF(), getInferInfo(), propagateLbTTEF(), propagateUbTTEF(), tightenLbTTEF(), and tightenUbTTEF().
|
static |
returns the implied earliest start time
| scip | SCIP data structure |
| var | variable for which the implied est should be returned |
| addedvars | hash map containig the variable which are already added |
| est | pointer to store the implied earliest start time |
Definition at line 382 of file cons_cumulative.c.
References computeImpliedLct(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPhashmapGetImage(), SCIPhashmapRemove(), SCIPisEQ(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), and SCIPvarGetVlbVars().
Referenced by computeCoreWithInterval(), and SCIPcreateWorstCaseProfile().
|
static |
returns the implied latest completion time
| scip | SCIP data structure |
| var | variable for which the implied est should be returned |
| duration | duration of the given job |
| addedvars | hash map containig the variable which are already added |
| lct | pointer to store the implied latest completion time |
Definition at line 450 of file cons_cumulative.c.
References collectBinaryVars(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPhashmapExists(), SCIPhashmapRemove(), SCIPisEQ(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNVubs(), SCIPvarGetUbLocal(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), and SCIPvarGetVubVars().
Referenced by computeImpliedEst(), and SCIPcreateWorstCaseProfile().
|
static |
collects all necessary binary variables to represent the jobs which can be active at time point of interest
| scip | SCIP data structure |
| consdata | constraint data |
| vars | pointer to the array to store the binary variables |
| coefs | pointer to store the coefficients |
| nvars | number if collect binary variables |
| startindices | permutation with rspect to the start times |
| curtime | current point in time |
| nstarted | number of jobs that start before the curtime or at curtime |
| nfinished | number of jobs that finished before curtime or at curtime |
Definition at line 514 of file cons_cumulative.c.
References collectIntVars(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPexistsConsLinking(), SCIPgetBinvarsLinking(), SCIPgetConsLinking(), SCIPgetValsLinking(), SCIPreallocBufferArray, and SCIPvarGetUbGlobal().
Referenced by computeImpliedLct(), and createCapacityRestriction().
|
static |
collect all integer variable which belong to jobs which can run at the point of interest
| scip | SCIP data structure |
| consdata | constraint data |
| activevars | jobs that are currently running |
| startindices | permutation with rspect to the start times |
| curtime | current point in time |
| nstarted | number of jobs that start before the curtime or at curtime |
| nfinished | number of jobs that finished before curtime or at curtime |
| lower | shall cuts be created due to lower or upper bounds? |
| lhs | lhs for the new row sum of lbs + minoffset |
Definition at line 612 of file cons_cumulative.c.
References createSortedEventpoints(), SCIP_OKAY, SCIPconvertRealToInt(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by collectBinaryVars(), and createCapacityRestrictionIntvars().
|
static |
initialize the sorted event point arrays
| scip | SCIP data structure |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations per start time variable |
| starttimes | array to store sorted start events |
| endtimes | array to store sorted end events |
| startindices | permutation with rspect to the start times |
| endindices | permutation with rspect to the end times |
| local | shall local bounds be used |
Definition at line 686 of file cons_cumulative.c.
References createSortedEventpointsSol(), SCIPconvertRealToInt(), SCIPsortIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().
Referenced by collectIntVars(), consCapacityConstraintsFinder(), createSelectedSortedEventpointsSol(), and tightenCapacity().
|
static |
initialize the sorted event point arrays w.r.t. the given primal solutions
| scip | SCIP data structure |
| sol | solution |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations per start time variable |
| starttimes | array to store sorted start events |
| endtimes | array to store sorted end events |
| startindices | permutation with rspect to the start times |
| endindices | permutation with rspect to the end times |
Definition at line 734 of file cons_cumulative.c.
References createSelectedSortedEventpointsSol(), SCIPconvertRealToInt(), SCIPgetSolVal(), and SCIPsortIntInt().
Referenced by computePeak(), and createSortedEventpoints().
|
static |
initialize the sorted event point arrays
| scip | SCIP data structure |
| consdata | constraint data |
| sol | primal CIP solution, NULL for current LP solution |
| starttimes | array to store sorted start events |
| endtimes | array to store sorted end events |
| startindices | permutation with rspect to the start times |
| endindices | permutation with rspect to the end times |
| nvars | number of variables that are integral |
| lower | shall the constraints be derived for lower or upper bounds? |
Definition at line 777 of file cons_cumulative.c.
References createSortedEventpoints(), getActiveVar(), MAX, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPsortIntInt(), SCIPstatisticPrintf, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by createSortedEventpointsSol(), and separateConsOnIntegerVariables().
|
static |
gets the active variables together with the constant
| scip | SCIP data structure |
| var | pointer to store the active variable |
| scalar | pointer to store the scalar |
| constant | pointer to store the constant |
Definition at line 1154 of file cons_cumulative.c.
References computeTotalEnergy(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIPconvertRealToInt(), SCIPgetProbvarSum(), SCIPisZero(), SCIPvarGetStatus(), and SCIPvarIsActive().
Referenced by computeAlternativeBounds(), createSelectedSortedEventpointsSol(), varMayRoundDown(), and varMayRoundUp().
|
static |
computes the total energy of all jobs
| durations | array of job durations |
| demands | array of job demands |
| njobs | number of jobs |
Definition at line 1199 of file cons_cumulative.c.
References setupAndSolveCumulativeSubscip().
Referenced by getActiveVar(), propagateLbTTEF(), and propagateUbTTEF().
|
static |
setup and solve subscip to solve single cumulative condition
| subscip | subscip data structure |
| objvals | array of objective coefficients for each job (linear objective function), or NULL if none |
| durations | array of durations |
| demands | array of demands |
| njobs | number of jobs (activities) |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| maxnodes | maximum number of branch-and-bound nodes (-1: no limit) |
| timelimit | time limit for solving in seconds |
| memorylimit | memory limit for solving in mega bytes (MB) |
| ests | array of earliest start times for each job |
| lsts | array of latest start times for each job |
| infeasible | pointer to store if the subproblem was infeasible |
| unbounded | pointer to store if the problem is unbounded |
| solved | pointer to store if the problem is solved (to optimality) |
| error | pointer to store if an error occurred |
Definition at line 1225 of file cons_cumulative.c.
References FALSE, SCIP_CALL, SCIP_DECL_SOLVECUMULATIVE(), SCIP_INVALIDDATA, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PARAMEMPHASIS_CPSOLVER, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_RESTARTLIMIT, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_STATUS_USERINTERRUPT, SCIP_VARTYPE_INTEGER, SCIPaddCons(), SCIPaddVar(), SCIPallocBlockMemoryArray, SCIPcreateConsBasicCumulative(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPdebugMsg, SCIPerrorMessage, SCIPfreeBlockMemoryArray, SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetStatus(), SCIPincludeDefaultPlugins(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetBoolParam(), SCIPsetEmphasis(), SCIPsetHmaxCumulative(), SCIPsetHminCumulative(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsetSubscipsOff(), SCIPsnprintf(), SCIPsolve(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by computeTotalEnergy(), and SCIP_DECL_SOLVECUMULATIVE().
|
static |
solve single cumulative condition using SCIP and a single cumulative constraint
Definition at line 1389 of file cons_cumulative.c.
References conshdlrdataCreate(), FALSE, MAX, SCIP_CALL, SCIP_INVALIDDATA, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_STATUS_USERINTERRUPT, SCIP_VARTYPE_BINARY, SCIPaddCoefKnapsack(), SCIPaddCoefSetppc(), SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPcreate(), SCIPcreateConsBasicKnapsack(), SCIPcreateConsBasicSetpart(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPdebugMessage, SCIPdebugMsg, SCIPerrorMessage, SCIPfree(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetStatus(), SCIPincludeDefaultPlugins(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsnprintf(), SCIPsolve(), SCIPvarGetUbGlobal(), setupAndSolveCumulativeSubscip(), and TRUE.
Referenced by setupAndSolveCumulativeSubscip().
|
static |
creates constaint handler data for cumulative constraint handler
| scip | SCIP data structure |
| conshdlrdata | pointer to store the constraint handler data |
| eventhdlr | event handler |
Definition at line 1730 of file cons_cumulative.c.
References conshdlrdataFree(), SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
Referenced by SCIP_DECL_SOLVECUMULATIVE(), and SCIPincludeConshdlrCumulative().
|
static |
frees constraint handler data for logic or constraint handler
| scip | SCIP data structure |
| conshdlrdata | pointer to the constraint handler data |
Definition at line 1775 of file cons_cumulative.c.
References consdataCatchEvents(), and SCIPfreeBlockMemory.
Referenced by conshdlrdataCreate(), and SCIP_DECL_CONSFREE().
|
static |
catches bound change events for all variables in transformed cumulative constraint
| scip | SCIP data structure |
| consdata | cumulative constraint data |
| eventhdlr | event handler to call for the event processing |
Definition at line 1796 of file cons_cumulative.c.
References consdataDropEvents(), SCIP_CALL, SCIP_EVENTTYPE_BOUNDTIGHTENED, SCIP_OKAY, and SCIPcatchVarEvent().
Referenced by conshdlrdataFree(), SCIP_DECL_CONSTRANS(), and SCIPcreateConsCumulative().
|
static |
drops events for variable at given position
| scip | SCIP data structure |
| consdata | cumulative constraint data |
| eventhdlr | event handler to call for the event processing |
| pos | array position of variable to catch bound change events for |
Definition at line 1820 of file cons_cumulative.c.
References consdataDropAllEvents(), SCIP_CALL, SCIP_EVENTTYPE_BOUNDTIGHTENED, SCIP_OKAY, and SCIPdropVarEvent().
Referenced by consdataCatchEvents(), consdataDeletePos(), and consdataDropAllEvents().
|
static |
drops bound change events for all variables in transformed linear constraint
| scip | SCIP data structure |
| consdata | linear constraint data |
| eventhdlr | event handler to call for the event processing |
Definition at line 1841 of file cons_cumulative.c.
References consdataDropEvents(), initializeLocks(), SCIP_CALL, and SCIP_OKAY.
Referenced by consdataDropEvents(), and SCIP_DECL_CONSDELETE().
|
static |
initialize variable lock data structure
| consdata | constraint data |
| locked | should the variable be locked? |
Definition at line 1863 of file cons_cumulative.c.
References consdataCreate().
Referenced by consdataCreate(), consdataDropAllEvents(), and removeRedundantConss().
|
static |
creates constraint data of cumulative constraint
| scip | SCIP data structure |
| consdata | pointer to consdata |
| vars | array of integer variables |
| linkingconss | array of linking constraints for the integer variables, or NULL |
| durations | array containing corresponding durations |
| demands | array containing corresponding demands |
| nvars | number of variables |
| capacity | available cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| check | is the corresponding constraint a check constraint |
Definition at line 1883 of file cons_cumulative.c.
References consdataFreeRows(), FALSE, initializeLocks(), SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPgetConsLinking(), SCIPgetTransformedVars(), SCIPisTransformed(), SCIPmarkDoNotMultaggrVar(), SCIPstatistic, and SCIPtransformConss().
Referenced by initializeLocks(), SCIP_DECL_CONSTRANS(), and SCIPcreateConsCumulative().
|
static |
releases LP rows of constraint data and frees rows array
| scip | SCIP data structure |
| consdata | constraint data |
Definition at line 2005 of file cons_cumulative.c.
References consdataFree(), FALSE, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseRow().
Referenced by consdataCreate(), consdataFree(), and SCIP_DECL_CONSEXITSOL().
|
static |
frees a cumulative constraint data
| scip | SCIP data structure |
| consdata | pointer to linear constraint data |
Definition at line 2056 of file cons_cumulative.c.
References consdataFreeRows(), consdataPrint(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPreleaseCons().
Referenced by consdataFreeRows(), and SCIP_DECL_CONSDELETE().
|
static |
prints cumulative constraint to file stream
| scip | SCIP data structure |
| consdata | cumulative constraint data |
| file | output file (or NULL for standard output) |
Definition at line 2105 of file cons_cumulative.c.
References consdataDeletePos(), SCIPinfoMessage(), SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().
Referenced by consdataFree(), and SCIP_DECL_CONSPRINT().
|
static |
deletes coefficient at given position from constraint data
| scip | SCIP data structure |
| consdata | cumulative constraint data |
| cons | knapsack constraint |
| pos | position of coefficient to delete |
Definition at line 2132 of file cons_cumulative.c.
References consdataCollectLinkingCons(), consdataDropEvents(), FALSE, SCIP_CALL, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsTransformed(), SCIPdebugMsg, SCIPinProbing(), SCIPreleaseCons(), SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().
Referenced by consdataPrint(), presolveConsEffectiveHorizon(), removeIrrelevantJobs(), and removeOversizedJobs().
|
static |
collect linking constraints for each integer variable
| scip | SCIP data structure |
| consdata | pointer to consdata |
Definition at line 2202 of file cons_cumulative.c.
References checkCumulativeCondition(), FALSE, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPcaptureCons(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPcreateConsLinking(), SCIPdebugMsg, SCIPexistsConsLinking(), SCIPgetConsLinking(), SCIPsnprintf(), SCIPvarGetName(), and TRUE.
Referenced by consdataDeletePos(), createRelaxation(), and separateCoverCutsCons().
|
static |
check for the given starting time variables with their demands and durations if the cumulative conditions for the given solution is satisfied
| scip | SCIP data structure |
| sol | primal solution, or NULL for current LP/pseudo solution |
| nvars | number of variables (jobs) |
| vars | array of integer variable which corresponds to starting times for a job |
| durations | array containing corresponding durations |
| demands | array containing corresponding demands |
| capacity | available cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| violated | pointer to store if the cumulative condition is violated |
| cons | constraint which is checked |
| printreason | should the reason for the violation be printed? |
Definition at line 2269 of file cons_cumulative.c.
References checkCons(), FALSE, MAX, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPinfoMessage(), SCIPisFeasIntegral(), SCIPprintCons(), SCIPrelDiff(), SCIPsortIntInt(), SCIPupdateSolConsViolation(), SCIPvarGetName(), and TRUE.
Referenced by checkCons(), consdataCollectLinkingCons(), and SCIPcheckCumulativeCondition().
|
static |
check if the given constrait is valid; checks each starting point of a job whether the remaining capacity is at least zero or not. If not (*violated) is set to TRUE
| scip | SCIP data structure |
| cons | constraint to be checked |
| sol | primal solution, or NULL for current LP/pseudo solution |
| violated | pointer to store if the constraint is violated |
| printreason | should the reason for the violation be printed? |
Definition at line 2427 of file cons_cumulative.c.
References checkCumulativeCondition(), resolvePropagationCoretimes(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), and SCIPdebugMsg.
Referenced by checkCumulativeCondition(), enforceConstraint(), enforceSolution(), and SCIP_DECL_CONSCHECK().
|
static |
resolves the propagation of the core time algorithm
| scip | SCIP data structure |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| infervar | inference variable |
| inferdemand | demand of the inference variable |
| inferpeak | time point which causes the propagation |
| relaxedpeak | relaxed time point which would be sufficient to be proved |
| bdchgidx | the index of the bound change, representing the point of time where the change took place |
| usebdwidening | should bound widening be used during conflict analysis? |
| provedpeak | pointer to store the actually proved peak, or NULL |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
Definition at line 2463 of file cons_cumulative.c.
References BMSclearMemoryArray, computeOverlap(), FALSE, inferInfoGetData1(), inferInfoGetData2(), inferInfoGetProprule(), MAX, PROPRULE_2_EDGEFINDING, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIPaddConflictLb(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictUb(), SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetConflictVarLb(), SCIPgetConflictVarUb(), SCIPgetStage(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPinProbing(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPsortDownIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), and TRUE.
Referenced by analyseInfeasibelCoreInsertion(), checkCons(), and respropCumulativeCondition().
|
static |
compute the minimum overlaps w.r.t. the duration of the job and the time window [begin,end)
| begin | begin of the times interval |
| end | end of time interval |
| est | earliest start time |
| lst | latest start time |
| duration | duration of the job |
Definition at line 2817 of file cons_cumulative.c.
References analyzeEnergyRequirement().
Referenced by analyzeEnergyRequirement(), and resolvePropagationCoretimes().
|
static |
an overload was detected due to the time-time edge-finding propagate; initialized conflict analysis, add an initial reason
| scip | SCIP data structure |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | capacity of the cumulative condition |
| begin | begin of the time window |
| end | end of the time window |
| infervar | variable which was propagate, or NULL |
| boundtype | the type of the changed bound (lower or upper bound) |
| bdchgidx | the index of the bound change, representing the point of time where the change took place |
| relaxedbd | the relaxed bound which is sufficient to be explained |
| usebdwidening | should bound widening be used during conflict analysis? |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
Definition at line 2854 of file cons_cumulative.c.
References computeOverlap(), FALSE, respropCumulativeCondition(), SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_UNKNOWN, SCIPaddConflictLb(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictUb(), SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetConflictVarLb(), SCIPgetConflictVarUb(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPsortDownIntIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by computeOverlap(), propagateLbTTEF(), propagateTTEF(), propagateUbTTEF(), respropCumulativeCondition(), tightenLbTTEF(), and tightenUbTTEF().
|
static |
resolve propagation w.r.t. the cumulative condition
| scip | SCIP data structure |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| infervar | the conflict variable whose bound change has to be resolved |
| inferinfo | the user information |
| boundtype | the type of the changed bound (lower or upper bound) |
| bdchgidx | the index of the bound change, representing the point of time where the change took place |
| relaxedbd | the relaxed bound which is sufficient to be explained |
| usebdwidening | should bound widening be used during conflict analysis? |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
| result | pointer to store the result of the propagation conflict resolving call |
Definition at line 3141 of file cons_cumulative.c.
References analyzeEnergyRequirement(), applyAlternativeBoundsBranching(), FALSE, inferInfoGetData1(), inferInfoGetData2(), inferInfoGetProprule(), MAX, PROPRULE_1_CORETIMES, PROPRULE_2_EDGEFINDING, PROPRULE_3_TTEF, resolvePropagationCoretimes(), SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPABORT, SCIPaddConflictLb(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictUb(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPerrorMessage, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPvarGetName(), and TRUE.
Referenced by analyzeEnergyRequirement(), SCIP_DECL_CONSRESPROP(), and SCIPrespropCumulativeCondition().
|
static |
apply all fixings which are given by the alternative bounds
| scip | SCIP data structure |
| vars | array of active variables |
| nvars | number of active variables |
| alternativelbs | alternative lower bounds |
| alternativeubs | alternative lower bounds |
| downlocks | number of constraints with down lock participating by the computation |
| uplocks | number of constraints with up lock participating by the computation |
| branched | pointer to store if a branching was applied |
Definition at line 3318 of file cons_cumulative.c.
References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbranchVarHole(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPisNegative(), SCIPisPositive(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetObj(), SCIPvarGetUbLocal(), subtractStartingJobDemands(), and TRUE.
Referenced by propagateAllConss(), and respropCumulativeCondition().
|
static |
remove the capacity requirments for all job which start at the curtime
| consdata | constraint data |
| curtime | current point in time |
| starttimes | array of start times |
| startindices | permutation with respect to the start times |
| freecapacity | pointer to store the resulting free capacity |
| idx | pointer to index in start time array |
| nvars | number of vars in array of starttimes and startindices |
Definition at line 3383 of file cons_cumulative.c.
References addEndingJobDemands().
Referenced by applyAlternativeBoundsBranching(), computePeak(), consCapacityConstraintsFinder(), separateConsOnIntegerVariables(), and tightenCapacity().
|
static |
add the capacity requirments for all job which end at the curtime
| consdata | constraint data |
| curtime | current point in time |
| endtimes | array of end times |
| endindices | permutation with rspect to the end times |
| freecapacity | pointer to store the resulting free capacity |
| idx | pointer to index in end time array |
| nvars | number of vars in array of starttimes and startindices |
Definition at line 3426 of file cons_cumulative.c.
References computePeak().
Referenced by computePeak(), consCapacityConstraintsFinder(), separateConsOnIntegerVariables(), subtractStartingJobDemands(), and tightenCapacity().
|
static |
computes a point in time when the capacity is exceeded returns hmax if this does not happen
| scip | SCIP data structure |
| consdata | constraint handler data |
| sol | primal solution, or NULL for current LP/pseudo solution |
| timepoint | pointer to store the time point of the peak |
Definition at line 3455 of file cons_cumulative.c.
References addEndingJobDemands(), collectBranchingCands(), createSortedEventpointsSol(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, and subtractStartingJobDemands().
Referenced by addEndingJobDemands(), and collectBranchingCands().
|
static |
checks all cumulative constraints for infeasibility and add branching candidates to storage
| scip | SCIP data structure |
| conss | constraints to be processed |
| nconss | number of constraints |
| sol | primal solution, or NULL for current LP/pseudo solution |
| nbranchcands | pointer to store the number of branching variables |
Definition at line 3540 of file cons_cumulative.c.
References computePeak(), enforceSolution(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddExternBranchCand(), SCIPblkmem(), SCIPconsGetData(), SCIPconsIsActive(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPgetNVars(), SCIPgetSolVal(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().
Referenced by computePeak(), and enforceSolution().
|
static |
enforcement of an LP, pseudo, or relaxation solution
| scip | SCIP data structure |
| conss | constraints to be processed |
| nconss | number of constraints |
| sol | solution to enforce (NULL for LP or pseudo solution) |
| branch | should branching candidates be collected |
| result | pointer to store the result |
Definition at line 3627 of file cons_cumulative.c.
References branch(), checkCons(), collectBranchingCands(), FALSE, isConsIndependently(), SCIP_Bool, SCIP_CALL, SCIP_INFEASIBLE, and SCIP_OKAY.
Referenced by collectBranchingCands(), enforceConstraint(), and SCIP_DECL_CONSENFOPS().
check if cumulative constraint is independently of all other constraints
| scip | SCIP data structure |
| cons | cumulative constraint |
Definition at line 3680 of file cons_cumulative.c.
References FALSE, SCIP_Bool, SCIPconsGetData(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), solveIndependentCons(), and TRUE.
Referenced by enforceSolution(), and solveIndependentCons().
|
static |
in case the cumulative constraint is independent of every else, solve the cumulative problem and apply the fixings (dual reductions)
| scip | SCIP data structure |
| cons | cumulative constraint |
| maxnodes | number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) |
| nchgbds | pointer to store the number changed variable bounds |
| nfixedvars | pointer to count number of fixings |
| ndelconss | pointer to count number of deleted constraints |
| cutoff | pointer to store if the constraint is infeasible |
| unbounded | pointer to store if the constraint is unbounded |
Definition at line 3719 of file cons_cumulative.c.
References analyseInfeasibelCoreInsertion(), FALSE, isConsIndependently(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelConsLocal(), SCIPfixVar(), SCIPfreeBufferArray, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNCheckConss(), SCIPgetNConss(), SCIPgetNVars(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPinProbing(), SCIPinRepropagation(), SCIPisInfinity(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetRealParam(), SCIPsolveCumulative(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetUbLocal(), and TRUE.
Referenced by isConsIndependently(), and presolveCons().
|
static |
start conflict analysis to analysis the core insertion which is infeasible
| scip | SCIP data structure |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| infervar | start time variable which lead to the infeasibilty |
| inferduration | duration of the start time variable |
| inferdemand | demand of the start time variable |
| inferpeak | profile preak which causes the infeasibilty |
| usebdwidening | should bound widening be used during conflict analysis? |
| initialized | pointer to store if the conflict analysis was initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
Definition at line 3934 of file cons_cumulative.c.
References coretimesUpdateLb(), FALSE, resolvePropagationCoretimes(), SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictUb(), SCIPdebugMsg, SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by coretimesUpdateLb(), createCoreProfile(), propagateTimetable(), and solveIndependentCons().
|
static |
We are using the core resource profile which contains all core except the one of the start time variable which we want to propagate, to incease the earliest start time. This we are doing in steps of length at most the duration of the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict analysis
| scip | SCIP data structure |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| cons | constraint which is propagated |
| profile | resource profile |
| idx | position of the variable to propagate |
| nchgbds | pointer to store the number of bound changes |
| usebdwidening | should bound widening be used during conflict analysis? |
| initialized | was conflict analysis initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
| infeasible | pointer to store if the constraint is infeasible |
Definition at line 3990 of file cons_cumulative.c.
References analyseInfeasibelCoreInsertion(), CONSHDLR_NAME, coretimesUpdateUb(), getInferInfo(), inferInfoToInt(), PROPRULE_1_CORETIMES, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPinferVarLbCons(), SCIPprofileFindLeft(), SCIPprofileGetLoad(), SCIPprofileGetNTimepoints(), SCIPprofileGetTime(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by analyseInfeasibelCoreInsertion(), and propagateTimetable().
|
static |
We are using the core resource profile which contains all core except the one of the start time variable which we want to propagate, to decrease the latest start time. This we are doing in steps of length at most the duration of the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict analysis
| scip | SCIP data structure |
| var | start time variable to propagate |
| duration | duration of the job |
| demand | demand of the job |
| capacity | cumulative capacity |
| cons | constraint which is propagated |
| profile | resource profile |
| idx | position of the variable to propagate |
| nchgbds | pointer to store the number of bound changes |
Definition at line 4143 of file cons_cumulative.c.
References computeCoreEngeryAfter(), CONSHDLR_NAME, getInferInfo(), inferInfoToInt(), MAX, PROPRULE_1_CORETIMES, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebug, SCIPdebugMsg, SCIPfindConshdlr(), SCIPgetMessagehdlr(), SCIPinferVarUbCons(), SCIPprofileFindLeft(), SCIPprofileGetLoad(), SCIPprofileGetNTimepoints(), SCIPprofileGetTime(), SCIPprofilePrint(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by coretimesUpdateLb(), and propagateTimetable().
|
static |
compute for the different earliest start and latest completion time the core energy of the corresponding time points
| scip | SCIP data structure |
| profile | core profile |
| nvars | number of start time variables (activities) |
| ests | array of sorted earliest start times |
| lcts | array of sorted latest completion times |
| coreEnergyAfterEst | array to store the core energy after the earliest start time of each job |
| coreEnergyAfterLct | array to store the core energy after the latest completion time of each job |
Definition at line 4277 of file cons_cumulative.c.
References collectDataTTEF(), SCIP_OKAY, SCIPprofileGetLoad(), SCIPprofileGetNTimepoints(), and SCIPprofileGetTime().
Referenced by coretimesUpdateUb(), and propagateTTEF().
|
static |
collect earliest start times, latest completion time, and free energy contributions
| scip | SCIP data structure |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| permests | array to store the variable positions |
| ests | array to store earliest start times |
| permlcts | array to store the variable positions |
| lcts | array to store latest completion times |
| ects | array to store earliest completion times of the flexible part of the job |
| lsts | array to store latest start times of the flexible part of the job |
| flexenergies | array to store the flexible energies of each job |
Definition at line 4348 of file cons_cumulative.c.
References computeCoreWithInterval(), MAX, SCIPconvertRealToInt(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and tightenLbTTEF().
Referenced by computeCoreEngeryAfter(), and propagateTTEF().
|
static |
try to tighten the lower bound of the given variable
| scip | SCIP data structure |
| conshdlrdata | constraint handler data |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| var | variable to be considered for upper bound tightening |
| duration | duration of the job |
| demand | demand of the job |
| est | earliest start time of the job |
| ect | earliest completion time of the flexible part of the job |
| lct | latest completion time of the job |
| begin | begin of the time window under investigation |
| end | end of the time window under investigation |
| energy | available energy for the flexible part of the hob within the time window |
| bestlb | pointer to strope the best lower bound change |
| inferinfos | pointer to store the inference information which is need for the (best) lower bound change |
| initialized | was conflict analysis initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
| cutoff | pointer to store if the constraint is infeasible |
Definition at line 4416 of file cons_cumulative.c.
References analyzeEnergyRequirement(), computeCoreWithInterval(), FALSE, getInferInfo(), inferInfoToInt(), MAX, PROPRULE_3_TTEF, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPaddConflictUb(), SCIPconvertRealToInt(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPvarGetUbLocal(), tightenUbTTEF(), and TRUE.
Referenced by collectDataTTEF(), and propagateLbTTEF().
|
static |
try to tighten the upper bound of the given variable
| scip | SCIP data structure |
| conshdlrdata | constraint handler data |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| var | variable to be considered for upper bound tightening |
| duration | duration of the job |
| demand | demand of the job |
| est | earliest start time of the job |
| lst | latest start time of the flexible part of the job |
| lct | latest completion time of the job |
| begin | begin of the time window under investigation |
| end | end of the time window under investigation |
| energy | available energy for the flexible part of the hob within the time window |
| bestub | pointer to strope the best upper bound change |
| inferinfos | pointer to store the inference information which is need for the (best) upper bound change |
| initialized | was conflict analysis initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
| cutoff | pointer to store if the constraint is infeasible |
Definition at line 4529 of file cons_cumulative.c.
References analyzeEnergyRequirement(), computeCoreWithInterval(), FALSE, getInferInfo(), inferInfoToInt(), MAX, propagateUbTTEF(), PROPRULE_3_TTEF, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPconvertRealToInt(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPvarGetLbLocal(), and TRUE.
Referenced by propagateUbTTEF(), and tightenLbTTEF().
|
static |
propagate the upper bounds and "opportunistically" the lower bounds using the time-table edge-finding algorithm
| scip | SCIP data structure |
| conshdlrdata | constraint handler data |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| newlbs | array to buffer new lower bounds |
| newubs | array to buffer new upper bounds |
| lbinferinfos | array to store the inference information for the lower bound changes |
| ubinferinfos | array to store the inference information for the upper bound changes |
| lsts | array of latest start time of the flexible part in the same order as the variables |
| flexenergies | array of flexible energies in the same order as the variables |
| perm | permutation of the variables w.r.t. the non-decreasing order of the earliest start times |
| ests | array with earliest strart times sorted in non-decreasing order |
| lcts | array with latest completion times sorted in non-decreasing order |
| coreEnergyAfterEst | core energy after the earliest start times |
| coreEnergyAfterLct | core energy after the latest completion times |
| initialized | was conflict analysis initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
| cutoff | pointer to store if the constraint is infeasible |
Definition at line 4643 of file cons_cumulative.c.
References analyzeEnergyRequirement(), computeCoreWithInterval(), computeTotalEnergy(), CONSHDLR_NAME, FALSE, getInferInfo(), inferInfoToInt(), MAX, propagateLbTTEF(), PROPRULE_3_TTEF, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIP_UNKNOWN, SCIPaddConflictUb(), SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), tightenUbTTEF(), and TRUE.
Referenced by propagateTTEF(), and tightenUbTTEF().
|
static |
propagate the lower bounds and "opportunistically" the upper bounds using the time-table edge-finding algorithm
| scip | SCIP data structure |
| conshdlrdata | constraint handler data |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| newlbs | array to buffer new lower bounds |
| newubs | array to buffer new upper bounds |
| lbinferinfos | array to store the inference information for the lower bound changes |
| ubinferinfos | array to store the inference information for the upper bound changes |
| ects | array of earliest completion time of the flexible part in the same order as the variables |
| flexenergies | array of flexible energies in the same order as the variables |
| perm | permutation of the variables w.r.t. the non-decreasing order of the latest completion times |
| ests | array with earliest strart times sorted in non-decreasing order |
| lcts | array with latest completion times sorted in non-decreasing order |
| coreEnergyAfterEst | core energy after the earliest start times |
| coreEnergyAfterLct | core energy after the latest completion times |
| initialized | was conflict analysis initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
| cutoff | pointer to store if the constraint is infeasible |
Definition at line 4994 of file cons_cumulative.c.
References analyzeEnergyRequirement(), computeCoreWithInterval(), computeTotalEnergy(), CONSHDLR_NAME, FALSE, getInferInfo(), inferInfoToInt(), MAX, propagateTTEF(), PROPRULE_3_TTEF, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIP_UNKNOWN, SCIPaddConflictUb(), SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), tightenLbTTEF(), and TRUE.
Referenced by propagateTTEF(), and propagateUbTTEF().
|
static |
checks whether the instance is infeasible due to a overload within a certain time frame using the idea of time-table edge-finding
| scip | SCIP data structure |
| conshdlrdata | constraint handler data |
| profile | current core profile |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| cons | constraint which is propagated (needed to SCIPinferVar**Cons()) |
| nchgbds | pointer to store the number of bound changes |
| initialized | was conflict analysis initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
| cutoff | pointer to store if the constraint is infeasible |
Definition at line 5334 of file cons_cumulative.c.
References analyzeEnergyRequirement(), collectDataTTEF(), computeCoreEngeryAfter(), CONSHDLR_NAME, FALSE, inferInfoGetData1(), inferInfoGetData2(), intToInferInfo(), propagateLbTTEF(), propagateTimetable(), propagateUbTTEF(), SCIP_Bool, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPsortIntInt(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propagateCumulativeCondition(), and propagateLbTTEF().
|
static |
a cumulative condition is not satisfied if its capacity is exceeded at a time where jobs cannot be shifted (core) anymore we build up a cumulative profile of all cores of jobs and try to improve bounds of all jobs; also known as time table propagator
| scip | SCIP data structure |
| conshdlrdata | constraint handler data |
| profile | core profile |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| cons | constraint which is propagated (needed to SCIPinferVar**Cons()) |
| nchgbds | pointer to store the number of bound changes |
| initialized | was conflict analysis initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
| cutoff | pointer to store if the constraint is infeasible |
Definition at line 5524 of file cons_cumulative.c.
References analyseInfeasibelCoreInsertion(), CONSHDLR_NAME, coretimesUpdateLb(), coretimesUpdateUb(), FALSE, MAX, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPprofileDeleteCore(), SCIPprofileGetNTimepoints(), SCIPprofileGetTime(), SCIPprofileInsertCore(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propagateCumulativeCondition(), and propagateTTEF().
|
static |
creates a node data structure
| scip | SCIP data structure |
| nodedata | pointer to store the create node data |
Definition at line 5691 of file cons_cumulative.c.
References freeNodedata(), SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIPallocBuffer, and TRUE.
Referenced by checkOverloadViaThetaTree(), and insertThetanode().
|
static |
frees a node data structure
| scip | SCIP data structure |
| nodedata | pointer to store node data which should be freed |
Definition at line 5715 of file cons_cumulative.c.
References nodedata, SCIPfreeBuffer, and updateEnvelop().
Referenced by checkOverloadViaThetaTree(), and createNodedata().
|
static |
update node data structure strating form the given node along the path to the root node
| scip | SCIP data structure |
| node | search node which inserted |
Definition at line 5728 of file cons_cumulative.c.
References MAX, nodedata, SCIP_OKAY, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPdebugMsg, and updateKeyOnTrace().
Referenced by deleteLambdaLeaf(), freeNodedata(), insertThetanode(), and moveNodeToLambda().
|
static |
updates the key of the first parent on the trace which comes from left
| node | node to start the trace |
| key | update search key |
Definition at line 5818 of file cons_cumulative.c.
References deleteLambdaLeaf(), nodedata, SCIPbtnodeGetData(), SCIPbtnodeGetParent(), SCIPbtnodeIsLeftchild(), and SCIPbtnodeIsRoot().
Referenced by deleteLambdaLeaf(), and updateEnvelop().
|
static |
deletes the given node and updates all envelops
| scip | SCIP data structure |
| tree | binary tree |
| node | node to be deleted |
Definition at line 5850 of file cons_cumulative.c.
References moveNodeToLambda(), nodedata, SCIP_CALL, SCIP_OKAY, SCIPbtnodeFree(), SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPbtnodeIsLeftchild(), SCIPbtnodeIsRightchild(), SCIPbtnodeIsRoot(), SCIPbtnodeSetLeftchild(), SCIPbtnodeSetParent(), SCIPbtnodeSetRightchild(), SCIPbtSetRoot(), SCIPdebugMsg, updateEnvelop(), and updateKeyOnTrace().
Referenced by inferboundsEdgeFinding(), and updateKeyOnTrace().
|
static |
moves a node form the theta set into the lambda set and updates the envelops
| scip | SCIP data structure |
| tree | binary tree |
| node | node to move into the lambda set |
Definition at line 5924 of file cons_cumulative.c.
References FALSE, insertThetanode(), nodedata, SCIP_CALL, SCIP_OKAY, SCIPbtnodeGetData(), and updateEnvelop().
Referenced by deleteLambdaLeaf(), and inferboundsEdgeFinding().
|
static |
inserts a node into the theta set and update the envelops
| scip | SCIP data structure |
| tree | binary tree |
| node | node to insert |
| nodedatas | array of node data |
| nnodedatas | pointer to number of node data |
Definition at line 5960 of file cons_cumulative.c.
References createNodedata(), findResponsibleLambdaLeafTraceEnergy(), nodedata, SCIP_CALL, SCIP_OKAY, SCIPbtGetRoot(), SCIPbtIsEmpty(), SCIPbtnodeCreate(), SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPbtnodeSetLeftchild(), SCIPbtnodeSetParent(), SCIPbtnodeSetRightchild(), SCIPbtSetRoot(), and updateEnvelop().
Referenced by checkOverloadViaThetaTree(), and moveNodeToLambda().
|
static |
returns the leaf responsible for the lambda energy
| node | node which defines the subtree beases on the lambda energy |
Definition at line 6064 of file cons_cumulative.c.
References findResponsibleLambdaLeafTraceEnvelop(), nodedata, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), and SCIPbtnodeIsLeaf().
Referenced by findResponsibleLambdaLeafTraceEnvelop(), and insertThetanode().
|
static |
returns the leaf responsible for the lambda envelop
| node | node which defines the subtree beases on the lambda envelop |
Definition at line 6113 of file cons_cumulative.c.
References collectThetaSubtree(), findResponsibleLambdaLeafTraceEnergy(), nodedata, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), and SCIPbtnodeIsLeaf().
Referenced by findResponsibleLambdaLeafTraceEnergy(), and inferboundsEdgeFinding().
|
static |
reports all elements from set theta to generate a conflicting set
| node | node within a theta subtree |
| omegaset | array to store the collected jobs |
| nelements | pointer to store the number of elements in omegaset |
| est | pointer to store the earliest start time of the omega set |
| lct | pointer to store the latest start time of the omega set |
| energy | pointer to store the energy of the omega set |
Definition at line 6166 of file cons_cumulative.c.
References MAX, nodedata, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPdebugMessage, SCIPvarGetName(), and traceThetaEnvelop().
Referenced by findResponsibleLambdaLeafTraceEnvelop(), traceLambdaEnergy(), traceLambdaEnvelop(), and traceThetaEnvelop().
|
static |
collect the jobs (omega set) which are contribute to theta envelop from the theta set
| node | node whose theta envelop needs to be backtracked |
| omegaset | array to store the collected jobs |
| nelements | pointer to store the number of elements in omegaset |
| est | pointer to store the earliest start time of the omega set |
| lct | pointer to store the latest start time of the omega set |
| energy | pointer to store the energy of the omega set |
Definition at line 6201 of file cons_cumulative.c.
References collectThetaSubtree(), nodedata, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), and traceLambdaEnergy().
Referenced by collectThetaSubtree(), and traceLambdaEnvelop().
|
static |
collect the jobs (omega set) which are contribute to lambda envelop from the theta set
| node | node whose lambda envelop needs to be backtracked |
| omegaset | array to store the collected jobs |
| nelements | pointer to store the number of elements in omega set |
| est | pointer to store the earliest start time of the omega set |
| lct | pointer to store the latest start time of the omega set |
| energy | pointer to store the energy of the omega set |
Definition at line 6262 of file cons_cumulative.c.
References collectThetaSubtree(), nodedata, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), and traceLambdaEnvelop().
Referenced by traceLambdaEnvelop(), and traceThetaEnvelop().
|
static |
collect the jobs (omega set) which are contribute to lambda envelop from the theta set
| node | node whose lambda envelop needs to be backtracked |
| omegaset | array to store the collected jobs |
| nelements | pointer to store the number of elements in omega set |
| est | pointer to store the earliest start time of the omega set |
| lct | pointer to store the latest start time of the omega set |
| energy | pointer to store the energy of the omega set |
Definition at line 6319 of file cons_cumulative.c.
References collectThetaSubtree(), computeEnergyContribution(), nodedata, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), traceLambdaEnergy(), and traceThetaEnvelop().
Referenced by inferboundsEdgeFinding(), and traceLambdaEnergy().
|
static |
compute the energy contribution by job which corresponds to the given leaf
| node | leaf |
Definition at line 6385 of file cons_cumulative.c.
References nodedata, SCIP_DECL_SORTPTRCOMP(), SCIPbtnodeGetData(), SCIPdebugMessage, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().
Referenced by analyzeConflictOverload(), and traceLambdaEnvelop().
|
static |
comparison method for two node data w.r.t. the earliest start time
Definition at line 6409 of file cons_cumulative.c.
References SCIPbtnodeGetData().
Referenced by computeEnergyContribution().
|
static |
comparison method for two node data w.r.t. the latest completion time
Definition at line 6422 of file cons_cumulative.c.
References analyzeConflictOverload().
|
static |
an overload was detected; initialized conflict analysis, add an initial reason
| scip | SCIP data structure |
| leaves | responsible leaves for the overload |
| capacity | cumulative capacity |
| nleaves | number of responsible leaves |
| est | earliest start time of the ...... |
| lct | latest completly time of the .... |
| reportedenergy | energy which already reported |
| propest | should the earliest start times be propagated, otherwise the latest completion times |
| shift | shift applied to all jobs before adding them to the tree |
| usebdwidening | should bound widening be used during conflict analysis? |
| initialized | was conflict analysis initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
Definition at line 6439 of file cons_cumulative.c.
References computeEnergyContribution(), computeEstOmegaset(), FALSE, nodedata, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictUb(), SCIPbtnodeGetData(), SCIPdebugMsg, SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPsortDownPtr(), SCIPswapInts(), and TRUE.
Referenced by checkOverloadViaThetaTree(), inferboundsEdgeFinding(), and SCIP_DECL_SORTPTRCOMP().
|
static |
computes a new latest starting time of the job in 'respleaf' due to the energy consumption and stores the responsible interval bounds in *est_omega and *lct_omega
| scip | SCIP data structure |
| duration | duration of the job to move |
| demand | demand of the job to move |
| capacity | cumulative capacity |
| est | earliest start time of the omega set |
| lct | latest start time of the omega set |
| energy | energy of the omega set |
Definition at line 6549 of file cons_cumulative.c.
References inferboundsEdgeFinding(), SCIP_Real, and SCIPfeasCeil().
Referenced by analyzeConflictOverload(), and inferboundsEdgeFinding().
|
static |
propagates start time using an edge finding algorithm which is based on binary trees (theta lambda trees)
| scip | SCIP data structure |
| conshdlrdata | constraint handler data |
| cons | constraint which is propagated |
| tree | binary tree constaining the theta and lambda sets |
| leaves | array of all leaves for each job one |
| capacity | cumulative capacity |
| ncands | number of candidates |
| propest | should the earliest start times be propagated, otherwise the latest completion times |
| shift | shift applied to all jobs before adding them to the tree |
| initialized | was conflict analysis initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
| nchgbds | pointer to store the number of bound changes |
| cutoff | pointer to store if the constraint is infeasible |
Definition at line 6583 of file cons_cumulative.c.
References analyzeConflictOverload(), checkOverloadViaThetaTree(), computeEstOmegaset(), CONSHDLR_NAME, deleteLambdaLeaf(), FALSE, findResponsibleLambdaLeafTraceEnvelop(), getInferInfo(), inferInfoToInt(), moveNodeToLambda(), nodedata, PROPRULE_2_EDGEFINDING, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPallocBufferArray, SCIPbtGetRoot(), SCIPbtIsEmpty(), SCIPbtnodeGetData(), SCIPbtnodeIsLeaf(), SCIPbtnodeIsRoot(), SCIPconshdlrGetData(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), traceLambdaEnvelop(), and TRUE.
Referenced by checkOverloadViaThetaTree(), and computeEstOmegaset().
|
static |
checks whether the instance is infeasible due to a overload within a certain time frame using the idea of theta trees
| scip | SCIP data structure |
| conshdlrdata | constraint handler data |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| cons | constraint which is propagated |
| propest | should the earliest start times be propagated, otherwise the latest completion times |
| initialized | was conflict analysis initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
| nchgbds | pointer to store the number of bound changes |
| cutoff | pointer to store if the constraint is infeasible |
Definition at line 6791 of file cons_cumulative.c.
References analyzeConflictOverload(), CONSHDLR_NAME, createNodedata(), FALSE, freeNodedata(), inferboundsEdgeFinding(), insertThetanode(), MAX, nodedata, propagateEdgeFinding(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPblkmem(), SCIPbtCreate(), SCIPbtFree(), SCIPbtGetRoot(), SCIPbtIsEmpty(), SCIPbtnodeCreate(), SCIPbtnodeGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPsortPtr(), SCIPstatistic, SCIPswapInts(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by inferboundsEdgeFinding(), and propagateEdgeFinding().
|
static |
checks whether the instance is infeasible due to a overload within a certain time frame using the idea of theta trees
| scip | SCIP data structure |
| conshdlrdata | constraint handler data |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| cons | constraint which is propagated |
| initialized | was conflict analysis initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
| nchgbds | pointer to store the number of bound changes |
| cutoff | pointer to store if the constraint is infeasible |
Definition at line 7094 of file cons_cumulative.c.
References checkOverloadViaThetaTree(), consCheckRedundancy(), FALSE, SCIP_CALL, SCIP_OKAY, and TRUE.
Referenced by checkOverloadViaThetaTree(), and propagateCumulativeCondition().
|
static |
checks if the constraint is redundant; that is the case if its capacity can never be exceeded; therefore we check with respect to the lower and upper bounds of the integer start time variables the maximum capacity usage for all event points
| scip | SCIP data structure |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| redundant | pointer to store whether this constraint is redundant |
Definition at line 7143 of file cons_cumulative.c.
References createCoreProfile(), FALSE, MAX, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPfreeBufferArray, SCIPsortIntInt(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propagateCumulativeCondition(), and propagateEdgeFinding().
|
static |
creates the worst case resource profile, that is, all jobs are inserted with the earliest start and latest completion time
| scip | SCIP data structure |
| conshdlrdata | constraint handler data |
| profile | resource profile |
| nvars | number of variables (jobs) |
| vars | array of integer variable which corresponds to starting times for a job |
| durations | array containing corresponding durations |
| demands | array containing corresponding demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| initialized | was conflict analysis initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
| cutoff | pointer to store if the constraint is infeasible |
Definition at line 7266 of file cons_cumulative.c.
References analyseInfeasibelCoreInsertion(), CONSHDLR_NAME, MAX, propagateCumulativeCondition(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPisFeasIntegral(), SCIPprofileGetTime(), SCIPprofileInsertCore(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by consCheckRedundancy(), and propagateCumulativeCondition().
|
static |
propagate the cumulative condition
| scip | SCIP data structure |
| conshdlrdata | constraint handler data |
| presoltiming | current presolving timing |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| cons | constraint which is propagated (needed to SCIPinferVar**Cons()) |
| nchgbds | pointer to store the number of bound changes |
| redundant | pointer to store if the constraint is redundant |
| initialized | was conflict analysis initialized |
| explanation | bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL |
| cutoff | pointer to store if the constraint is infeasible |
Definition at line 7357 of file cons_cumulative.c.
References consCheckRedundancy(), createCoreProfile(), propagateCons(), propagateEdgeFinding(), propagateTimetable(), propagateTTEF(), SCIP_CALL, SCIP_CALL_TERMINATE, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_PRESOLTIMING_FAST, SCIP_PRESOLTIMING_MEDIUM, SCIPprofileCreate(), and SCIPprofileFree().
Referenced by createCoreProfile(), propagateCons(), and SCIPpropCumulativeCondition().
|
static |
propagate the cumulative constraint
| scip | SCIP data structure |
| cons | constraint to propagate |
| conshdlrdata | constraint handler data |
| presoltiming | current presolving timing |
| nchgbds | pointer to store the number of bound changes |
| ndelconss | pointer to store the number of deleted constraints |
| cutoff | pointer to store if the constraint is infeasible |
Definition at line 7429 of file cons_cumulative.c.
References applyProbingVar(), FALSE, propagateCumulativeCondition(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_PRESOLVING, SCIPanalyzeConflictCons(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsDeleted(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPgetDepth(), SCIPgetStage(), SCIPinProbing(), SCIPresetConsAge(), and TRUE.
Referenced by propagateCumulativeCondition(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().
|
static |
it is dual feasible to remove the values {leftub+1, ..., rightlb-1} since SCIP current does not feature domain holes we use the probing mode to check if one of the two branches is infeasible. If this is the case the dual redundant can be realize as domain reduction. Otherwise we do nothing
| scip | SCIP data structure |
| vars | problem variables |
| nvars | number of problem variables |
| probingpos | variable number to apply probing on |
| leftub | upper bound of probing variable in left branch |
| rightlb | lower bound of probing variable in right branch |
| leftimpllbs | lower bounds after applying implications and cliques in left branch, or NULL |
| leftimplubs | upper bounds after applying implications and cliques in left branch, or NULL |
| leftproplbs | lower bounds after applying domain propagation in left branch |
| leftpropubs | upper bounds after applying domain propagation in left branch |
| rightimpllbs | lower bounds after applying implications and cliques in right branch, or NULL |
| rightimplubs | upper bounds after applying implications and cliques in right branch, or NULL |
| rightproplbs | lower bounds after applying domain propagation in right branch |
| rightpropubs | upper bounds after applying domain propagation in right branch |
| nfixedvars | pointer to counter which is increased by the number of deduced variable fixations |
| success | buffer to store whether a probing succeed to dual fix the variable |
| cutoff | buffer to store whether a cutoff is detected |
Definition at line 7510 of file cons_cumulative.c.
References FALSE, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIPapplyProbingVar(), SCIPinProbing(), SCIPinRepropagation(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and varMayRoundDown().
Referenced by applyAlternativeBoundsFixing(), presolveConsEst(), presolveConsLct(), and propagateCons().
|
static |
is it possible, to round variable down w.r.t. objective function
| scip | SCIP data structure |
| var | problem variable |
| roundable | pointer to store if the variable can be rounded down |
Definition at line 7608 of file cons_cumulative.c.
References FALSE, getActiveVar(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIPisNegative(), SCIPisPositive(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarIsActive(), TRUE, and varMayRoundUp().
Referenced by applyAlternativeBoundsFixing(), applyProbingVar(), fixIntegerVariableLb(), and presolveConsEst().
|
static |
is it possible, to round variable up w.r.t. objective function
| scip | SCIP data structure |
| var | problem variable |
| roundable | pointer to store if the variable can be rounded down |
Definition at line 7657 of file cons_cumulative.c.
References computeAlternativeBounds(), FALSE, getActiveVar(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIPisNegative(), SCIPisPositive(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarIsActive(), and TRUE.
Referenced by applyAlternativeBoundsFixing(), fixIntegerVariableUb(), presolveConsLct(), and varMayRoundDown().
|
static |
For each variable we compute an alternative lower and upper bounds. That is, if the variable is not fixed to its lower or upper bound the next reasonable lower or upper bound would be this alternative bound (implying that certain values are not of interest). An alternative bound for a particular is only valied if the cumulative constarints are the only one locking this variable in the corresponding direction.
| scip | SCIP data structure |
| conss | array of cumulative constraint constraints |
| nconss | number of cumulative constraints |
| local | use local bounds effective horizon? |
| alternativelbs | alternative lower bounds |
| alternativeubs | alternative lower bounds |
| downlocks | number of constraints with down lock participating by the computation |
| uplocks | number of constraints with up lock participating by the computation |
Definition at line 7710 of file cons_cumulative.c.
References applyAlternativeBoundsFixing(), SCIP_Profile::capacity, getActiveVar(), SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_MULTAGGR, SCIPcomputeHmax(), SCIPcomputeHmin(), SCIPconsGetData(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconvertRealToInt(), SCIPcreateWorstCaseProfile(), SCIPprofileCreate(), SCIPprofileFree(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetStatus(), and SCIPvarGetUbLocal().
Referenced by propagateAllConss(), and varMayRoundUp().
|
static |
apply all fixings which are given by the alternative bounds
| scip | SCIP data structure |
| vars | array of active variables |
| nvars | number of active variables |
| alternativelbs | alternative lower bounds |
| alternativeubs | alternative lower bounds |
| downlocks | number of constraints with down lock participating by the computation |
| uplocks | number of constraints with up lock participating by the computation |
| nfixedvars | pointer to counter which is increased by the number of deduced variable fixations |
| cutoff | buffer to store whether a cutoff is detected |
Definition at line 7846 of file cons_cumulative.c.
References applyProbingVar(), CONSHDLR_NAME, propagateAllConss(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPfindConshdlr(), SCIPfixVar(), SCIPfreeBufferArray, SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetUbLocal(), varMayRoundDown(), and varMayRoundUp().
Referenced by computeAlternativeBounds(), and propagateAllConss().
|
static |
propagate all constraints together
| scip | SCIP data structure |
| conshdlrdata | constraint handler data |
| conss | all cumulative constraint |
| nconss | number of cumulative constraints |
| local | use local bounds effective horizon? |
| nfixedvars | pointer to counter which is increased by the number of deduced variable fixations |
| cutoff | buffer to store whether a cutoff is detected |
| branched | pointer to store if a branching was applied, or NULL to avoid branching |
Definition at line 8000 of file cons_cumulative.c.
References applyAlternativeBoundsBranching(), applyAlternativeBoundsFixing(), computeAlternativeBounds(), createCoverCutsTimepoint(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetVars(), SCIPinProbing(), and SCIPinRepropagation().
Referenced by applyAlternativeBoundsFixing(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().
|
static |
creates covering cuts for jobs violating resource constraints
| scip | SCIP data structure |
| cons | constraint to be checked |
| startvalues | upper bounds on finishing time per job for activities from 0,..., nactivities -1 |
| time | at this point in time covering constraints are valid |
Definition at line 8072 of file cons_cumulative.c.
References createCoverCuts(), SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconvertRealToInt(), SCIPcreateEmptyRowCons(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetBinvarsLinking(), SCIPgetValsLinking(), SCIPinfinity(), SCIPreallocBlockMemoryArray, SCIPsnprintf(), SCIPsortIntInt(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by createCoverCuts(), and propagateAllConss().
|
static |
method to construct cover cuts for all points in time
| scip | SCIP data structure |
| cons | constraint to be separated |
Definition at line 8327 of file cons_cumulative.c.
References createCapacityRestriction(), createCoverCutsTimepoint(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPsortIntInt(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by createCoverCutsTimepoint(), and separateCoverCutsCons().
|
static |
this method creates a row for time point curtime which insures the capacity restriction of the cumulative constraint
| scip | SCIP data structure |
| cons | constraint to be checked |
| startindices | permutation with rspect to the start times |
| curtime | current point in time |
| nstarted | number of jobs that start before the curtime or at curtime |
| nfinished | number of jobs that finished before curtime or at curtime |
| cutsasconss | should the cumulative constraint create the cuts as constraints? |
Definition at line 8469 of file cons_cumulative.c.
References collectBinaryVars(), consCapacityConstraintsFinder(), FALSE, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCoefKnapsack(), SCIPaddCons(), SCIPaddVarToRow(), SCIPallocBlockMemoryArray, SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconsIsRemovable(), SCIPcreateConsKnapsack(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPflushRowExtensions(), SCIPfreeBufferArrayNull, SCIPinfinity(), SCIPprintRow(), SCIPreallocBlockMemoryArray, SCIPreleaseCons(), SCIPsnprintf(), and TRUE.
Referenced by consCapacityConstraintsFinder(), and createCoverCuts().
|
static |
this method checks how many cumulatives can run at most at one time if this is greater than the capacity it creates row
| scip | SCIP data structure |
| cons | constraint to be checked |
| cutsasconss | should the cumulative constraint create the cuts as constraints? |
Definition at line 8559 of file cons_cumulative.c.
References addEndingJobDemands(), createCapacityRestriction(), createRelaxation(), createSortedEventpoints(), FALSE, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPfreeBufferArray, and subtractStartingJobDemands().
Referenced by createCapacityRestriction(), and createRelaxation().
|
static |
creates LP rows corresponding to cumulative constraint; therefore, check each point in time if the maximal needed capacity is larger than the capacity of the cumulative constraint
for each necessary point in time:
sum_j sum_t demand_j * x_{j,t} <= capacity
where x(j,t) is the binary variables of job j at time t
| scip | SCIP data structure |
| cons | cumulative constraint |
| cutsasconss | should the cumulative constraint create the cuts as constraints? |
Definition at line 8690 of file cons_cumulative.c.
References addRelaxation(), consCapacityConstraintsFinder(), consdataCollectLinkingCons(), FALSE, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsSeparated(), SCIPsetConsEnforced(), SCIPsetConsInitial(), and SCIPsetConsSeparated().
Referenced by addRelaxation(), consCapacityConstraintsFinder(), and separateConsBinaryRepresentation().
|
static |
adds linear relaxation of cumulative constraint to the LP
| scip | SCIP data structure |
| cons | cumulative constraint |
| cutsasconss | should the cumulative constraint create the cuts as constraints? |
| infeasible | pointer to store whether an infeasibility was detected |
Definition at line 8733 of file cons_cumulative.c.
References createRelaxation(), FALSE, SCIP_CALL, SCIP_OKAY, SCIPaddRow(), SCIPconsGetData(), SCIProwIsInLP(), and separateConsBinaryRepresentation().
Referenced by createRelaxation(), and SCIP_DECL_CONSINITLP().
|
static |
checks constraint for violation, and adds it as a cut if possible
| scip | SCIP data structure |
| cons | cumulative constraint to be separated |
| sol | primal CIP solution, NULL for current LP solution |
| separated | pointer to store TRUE, if a cut was found |
| cutoff | whether a cutoff has been detected |
Definition at line 8766 of file cons_cumulative.c.
References createRelaxation(), FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPgetRowLPFeasibility(), SCIPgetRowSolFeasibility(), SCIPisFeasNegative(), SCIPresetConsAge(), SCIProwIsInLP(), separateCoverCutsCons(), and TRUE.
Referenced by addRelaxation(), enforceConstraint(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().
|
static |
checks constraint for violation, and adds it as a cut if possible
| scip | SCIP data structure |
| cons | logic or constraint to be separated |
| sol | primal CIP solution, NULL for current LP solution |
| separated | pointer to store TRUE, if a cut was found |
| cutoff | whether a cutoff has been detected |
Definition at line 8839 of file cons_cumulative.c.
References consdataCollectLinkingCons(), createCapacityRestrictionIntvars(), createCoverCuts(), FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPgetRowLPFeasibility(), SCIPgetRowSolFeasibility(), SCIPinfinity(), SCIPisFeasNegative(), SCIPresetConsAge(), SCIProwIsInLP(), and TRUE.
Referenced by SCIP_DECL_CONSSEPALP(), SCIP_DECL_CONSSEPASOL(), and separateConsBinaryRepresentation().
|
static |
this method creates a row for time point curtime which ensures the capacity restriction of the cumulative constraint
| scip | SCIP data structure |
| cons | constraint to be checked |
| startindices | permutation with rspect to the start times |
| curtime | current point in time |
| nstarted | number of jobs that start before the curtime or at curtime |
| nfinished | number of jobs that finished before curtime or at curtime |
| lower | shall cuts be created due to lower or upper bounds? |
Definition at line 8958 of file cons_cumulative.c.
References collectIntVars(), FALSE, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsIsRemovable(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPflushRowExtensions(), SCIPfreeBufferArrayNull, SCIPinfinity(), SCIPprintRow(), SCIPreleaseRow(), SCIPsnprintf(), separateConsOnIntegerVariables(), and TRUE.
Referenced by separateConsOnIntegerVariables(), and separateCoverCutsCons().
|
static |
checks constraint for violation, and adds it as a cut if possible
| scip | SCIP data structure |
| cons | cumulative constraint to be separated |
| sol | primal CIP solution, NULL for current LP solution |
| lower | shall cuts be created according to lower bounds? |
| separated | pointer to store TRUE, if a cut was found |
Definition at line 9026 of file cons_cumulative.c.
References addEndingJobDemands(), checkDemands(), createCapacityRestrictionIntvars(), createSelectedSortedEventpointsSol(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPfreeBufferArray, subtractStartingJobDemands(), and TRUE.
Referenced by createCapacityRestrictionIntvars(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().
returns TRUE if all demands are smaller than the capacity of the cumulative constraint and if the total demand is correct
| scip | SCIP data structure |
| cons | constraint to be checked |
Definition at line 9134 of file cons_cumulative.c.
References deleteTrivilCons(), FALSE, SCIPconsGetData(), and TRUE.
Referenced by presolveCons(), SCIP_DECL_CONSPRESOL(), and separateConsOnIntegerVariables().
|
static |
delete constraint if it consists of at most one job
| scip | SCIP data structure |
| cons | constraint to propagate |
| ndelconss | pointer to store the number of deleted constraints |
| cutoff | pointer to store if the constraint is infeasible |
Definition at line 9175 of file cons_cumulative.c.
References removeIrrelevantJobs(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPdelCons(), and TRUE.
Referenced by checkDemands(), and presolveCons().
|
static |
remove jobs which have a duration or demand of zero (zero energy) or lay outside the efficient horizon [hmin, hmax); this is done in the SCIP_DECL_CONSINITPRE() callback
| scip | SCIP data structure |
| cons | constraint to propagate |
Definition at line 9217 of file cons_cumulative.c.
References adjustOversizedJobBounds(), consdataDeletePos(), CONSHDLR_NAME, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPstatistic, SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().
Referenced by deleteTrivilCons(), SCIP_DECL_CONSINITPRE(), and SCIP_DECL_CONSPRESOL().
|
static |
adjust bounds of over sizeed job (the demand is larger than the capacity)
| scip | SCIP data structure |
| consdata | constraint data |
| pos | position of job in the consdata |
| nchgbds | pointer to store the number of changed bounds |
| naddconss | pointer to store the number of added constraints |
| cutoff | pointer to store if a cutoff was detected |
Definition at line 9281 of file cons_cumulative.c.
References FALSE, removeOversizedJobs(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPconvertRealToInt(), SCIPcreateConsBounddisjunction(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPreleaseCons(), SCIPsnprintf(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by removeIrrelevantJobs(), and removeOversizedJobs().
|
static |
try to removed over sizeed jobs (the demand is larger than the capacity)
| scip | SCIP data structure |
| cons | constraint |
| nchgbds | pointer to store the number of changed bounds |
| nchgcoefs | pointer to store the number of changed coefficient |
| naddconss | pointer to store the number of added constraints |
| cutoff | pointer to store if a cutoff was detected |
Definition at line 9387 of file cons_cumulative.c.
References adjustOversizedJobBounds(), consdataDeletePos(), fixIntegerVariableUb(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), and SCIPdebugMsg.
Referenced by adjustOversizedJobBounds(), and presolveCons().
|
static |
fix integer variable to upper bound if the rounding locks and the object coefficient are in favor of that
| scip | SCIP data structure |
| var | integer variable to fix |
| uplock | has thet start time variable a up lock |
| nfixedvars | pointer to store the number fixed variables |
Definition at line 9428 of file cons_cumulative.c.
References FALSE, fixIntegerVariableLb(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfixVar(), SCIPinProbing(), SCIPinRepropagation(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNLocksUp(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and varMayRoundUp().
Referenced by presolveConsLct(), and removeOversizedJobs().
|
static |
fix integer variable to lower bound if the rounding locks and the object coefficient are in favor of that
| scip | SCIP data structure |
| var | integer variable to fix |
| downlock | has the variable a down lock |
| nfixedvars | pointer to store the number fixed variables |
Definition at line 9480 of file cons_cumulative.c.
References FALSE, normalizeCumulativeCondition(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfixVar(), SCIPinProbing(), SCIPinRepropagation(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), TRUE, and varMayRoundDown().
Referenced by fixIntegerVariableUb(), and presolveConsEst().
|
static |
normalize cumulative condition
| scip | SCIP data structure |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| demands | array of demands |
| capacity | pointer to store the changed cumulative capacity |
| nchgcoefs | pointer to count total number of changed coefficients |
| nchgsides | pointer to count number of side changes |
Definition at line 9527 of file cons_cumulative.c.
References MAX, normalizeDemands(), SCIP_Longint, SCIP_OKAY, SCIPcalcGreComDiv(), and SCIPdebugMsg.
Referenced by fixIntegerVariableLb(), normalizeDemands(), and SCIPnormalizeCumulativeCondition().
|
static |
divides demands by their greatest common divisor and divides capacity by the same value, rounding down the result; in case the the smallest demands add up to more than the capacity we reductions all demands to one as well as the capacity since in that case none of the jobs can run in parallel
| scip | SCIP data structure |
| cons | cumulative constraint |
| nchgcoefs | pointer to count total number of changed coefficients |
| nchgsides | pointer to count number of side changes |
Definition at line 9602 of file cons_cumulative.c.
References computeEffectiveHorizonCumulativeCondition(), FALSE, normalizeCumulativeCondition(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsModifiable(), and TRUE.
Referenced by normalizeCumulativeCondition(), and presolveCons().
|
static |
computes for the given cumulative condition the effective horizon
| scip | SCIP data structure |
| nvars | number of variables (jobs) |
| vars | array of integer variable which corresponds to starting times for a job |
| durations | array containing corresponding durations |
| demands | array containing corresponding demands |
| capacity | available cumulative capacity |
| hmin | pointer to store the left bound of the effective horizon |
| hmax | pointer to store the right bound of the effective horizon |
| split | point were the cumulative condition can be split |
Definition at line 9639 of file cons_cumulative.c.
References createConsCumulative(), SCIP_CALL, SCIP_CALL_FINALLY, SCIP_OKAY, SCIPcomputeHmax(), SCIPcomputeHmin(), SCIPcreateWorstCaseProfile(), SCIPdebug, SCIPgetMessagehdlr(), SCIPinRepropagation(), SCIPprofileCreate(), SCIPprofileFree(), SCIPprofileGetLoads(), SCIPprofileGetNTimepoints(), SCIPprofileGetTimepoints(), and SCIPprofilePrint().
Referenced by computeEffectiveHorizon(), normalizeDemands(), and SCIPsplitCumulativeCondition().
|
static |
creates and adds a cumulative constraint
| scip | SCIP data structure |
| name | name of constraint |
| nvars | number of variables (jobs) |
| vars | array of integer variable which corresponds to starting times for a job |
| durations | array containing corresponding durations |
| demands | array containing corresponding demands |
| capacity | available cumulative capacity |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| initial | should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'. |
| separate | should the constraint be separated during LP processing? Usually set to TRUE. |
| enforce | should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints. |
| check | should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints. |
| propagate | should the constraint be propagated during node processing? Usually set to TRUE. |
| local | is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. |
| modifiable | is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint. |
| dynamic | is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are seperated as constraints. |
| removable | should the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. |
| stickingatnode | should the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data. |
Definition at line 9719 of file cons_cumulative.c.
References computeEffectiveHorizon(), SCIP_CALL, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsCumulative(), SCIPreleaseCons(), SCIPsetHmaxCumulative(), and SCIPsetHminCumulative().
Referenced by computeEffectiveHorizon(), computeEffectiveHorizonCumulativeCondition(), and createDisjuctiveCons().
|
static |
computes the effective horizon and checks if the constraint can be decompsed
| scip | SCIP data structure |
| cons | cumulative constraint |
| ndelconss | pointer to store the number of deleted constraints |
| naddconss | pointer to store the number of added constraints |
| nchgsides | pointer to store the number of changed sides |
Definition at line 9773 of file cons_cumulative.c.
References computeEffectiveHorizonCumulativeCondition(), CONSHDLR_NAME, createConsCumulative(), presolveConsEst(), SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPdebugMsg, SCIPdelCons(), SCIPfindConshdlr(), SCIPsnprintf(), and SCIPstatistic.
Referenced by createConsCumulative(), and presolveCons().
|
static |
presolve cumulative condition w.r.t. the earlier start times (est) and the hmin of the effective horizon
(1) If the latest completion time (lct) of a job is smaller or equal than hmin, the corresponding job can be removed form the constraint. This is the case since it cannot effect any assignment within the effective horizon
(2) If the latest start time (lst) of a job is smaller or equal than hmin it follows that the this jobs can run before the effective horizon or it overlaps with the effective horizon such that hmin in included. Hence, the down-lock of the corresponding start time variable can be removed.
(3) If the earlier completion time (ect) of a job is smaller or equal than hmin, the cumulative is the only one locking the corresponding variable down, and the objective coefficient of the start time variable is not negative, than the job can be dual fixed to its earlier start time (est).
(4) If the earlier start time (est) of job is smaller than the hmin, the cumulative is the only one locking the corresponding variable down, and the objective coefficient of the start time variable is not negative, than removing the values {est+1,...,hmin} form variable domain is dual feasible.
(5) If the earlier start time (est) of job is smaller than the smallest earlier completion times of all other jobs (lets denote this with minect), the cumulative is the only one locking the corresponding variable down, and the objective coefficient of the start time variable is not negative, than removing the values {est+1,...,minect-1} form variable domain is dual feasible.
| scip | SCIP data structure |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| downlocks | array to store if the variable has a down lock, or NULL |
| uplocks | array to store if the variable has an up lock, or NULL |
| cons | underlying constraint, or NULL |
| irrelevants | array mark those variables which are irrelevant for the cumulative condition |
| nfixedvars | pointer to store the number of fixed variables |
| nchgsides | pointer to store the number of changed sides |
| cutoff | buffer to store whether a cutoff is detected |
Definition at line 9877 of file cons_cumulative.c.
References applyProbingVar(), CONSHDLR_NAME, FALSE, fixIntegerVariableLb(), MAX, presolveConsLct(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfixVar(), SCIPfreeBufferArray, SCIPstatistic, SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), SCIPvarGetUbGlobal(), TRUE, and varMayRoundDown().
Referenced by computeEffectiveHorizon(), presolveConsEffectiveHorizon(), and SCIPpresolveCumulativeCondition().
|
static |
presolve cumulative condition w.r.t. the latest completion times (lct) and the hmax of the effective horizon
(1) If the earliest start time (est) of a job is larger or equal than hmax, the corresponding job can be removed form the constraint. This is the case since it cannot effect any assignment within the effective horizon
(2) If the earliest completion time (ect) of a job is larger or equal than hmax it follows that the this jobs can run before the effective horizon or it overlaps with the effective horizon such that hmax in included. Hence, the up-lock of the corresponding start time variable can be removed.
(3) If the latest start time (lst) of a job is larger or equal than hmax, the cumulative is the only one locking the corresponding variable up, and the objective coefficient of the start time variable is not positive, than the job can be dual fixed to its latest start time (lst).
(4) If the latest completion time (lct) of job is larger than the hmax, the cumulative is the only one locking the corresponding variable up, and the objective coefficient of the start time variable is not positive, than removing the values {hmax - p_j, ..., lst-1} form variable domain is dual feasible (p_j is the processing time of the corresponding job).
(5) If the latest completion time (lct) of job is smaller than the largerst latest start time of all other jobs (lets denote this with maxlst), the cumulative is the only one locking the corresponding variable up, and the objective coefficient of the start time variable is not positive, than removing the values {maxlst - p_j + 1, ..., lst-1} form variable domain is dual feasible (p_j is the processing time of the corresponding job).
| scip | SCIP data structure |
| nvars | number of start time variables (activities) |
| vars | array of start time variables |
| durations | array of durations |
| hmin | left bound of time axis to be considered (including hmin) |
| hmax | right bound of time axis to be considered (not including hmax) |
| downlocks | array to store if the variable has a down lock, or NULL |
| uplocks | array to store if the variable has an up lock, or NULL |
| cons | underlying constraint, or NULL |
| irrelevants | array mark those variables which are irrelevant for the cumulative condition |
| nfixedvars | pointer to counter which is increased by the number of deduced variable fixations |
| nchgsides | pointer to store the number of changed sides |
| cutoff | buffer to store whether a cutoff is detected |
Definition at line 10162 of file cons_cumulative.c.
References applyProbingVar(), CONSHDLR_NAME, FALSE, fixIntegerVariableUb(), MAX, presolveConsEffectiveHorizon(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfixVar(), SCIPfreeBufferArray, SCIPstatistic, SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNLocksUp(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and varMayRoundUp().
Referenced by presolveConsEffectiveHorizon(), presolveConsEst(), and SCIPpresolveCumulativeCondition().
|
static |
presolve cumulative constraint w.r.t. the boundary of the effective horizon
| scip | SCIP data structure |
| cons | cumulative constraint |
| nfixedvars | pointer to store the number of fixed variables |
| nchgcoefs | pointer to store the number of changed coefficients |
| nchgsides | pointer to store the number of changed sides |
| cutoff | pointer to store if a cutoff was detected |
Definition at line 10414 of file cons_cumulative.c.
References BMSclearMemoryArray, collectDemands(), consdataDeletePos(), FALSE, presolveConsEst(), presolveConsLct(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconvertRealToInt(), SCIPfreeBufferArray, SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by presolveCons(), and presolveConsLct().
|
static |
stores all demands which are smaller than the capacity of those jobs that are running at 'curtime'
| scip | SCIP data structure |
| consdata | constraint data |
| startindices | permutation with rspect to the start times |
| curtime | current point in time |
| nstarted | number of jobs that start before the curtime or at curtime |
| nfinished | number of jobs that finished before curtime or at curtime |
| demands | pointer to array storing the demands |
| ndemands | pointer to store the number of different demands |
Definition at line 10495 of file cons_cumulative.c.
References getHighestCapacityUsage(), SCIP_OKAY, SCIPconvertRealToInt(), and SCIPvarGetUbGlobal().
Referenced by getHighestCapacityUsage(), and presolveConsEffectiveHorizon().
|
static |
this method creates a row for time point curtime which insures the capacity restriction of the cumulative constraint
| scip | SCIP data structure |
| cons | constraint to be checked |
| startindices | permutation with rspect to the start times |
| curtime | current point in time |
| nstarted | number of jobs that start before the curtime or at curtime |
| nfinished | number of jobs that finished before curtime or at curtime |
| bestcapacity | pointer to store the maximum possible capacity usage |
Definition at line 10554 of file cons_cumulative.c.
References collectDemands(), SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconvertRealToInt(), SCIPfreeBufferArray, SCIPisFeasIntegral(), SCIPsolveKnapsackExactly(), and tightenCapacity().
Referenced by collectDemands(), and tightenCapacity().
|
static |
try to tighten the capacity – using DP for knapsack, we find the maximum possible capacity usage – neglects hmin and hmax, such that it is also able to check solutions globally
| scip | SCIP data structure |
| cons | cumulative constraint |
| nchgcoefs | pointer to count total number of changed coefficients |
| nchgsides | pointer to store the number of changed sides |
Definition at line 10615 of file cons_cumulative.c.
References addEndingJobDemands(), createSortedEventpoints(), FALSE, getHighestCapacityUsage(), MAX, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPdebug, SCIPdebugMsg, SCIPdebugMsgPrint, SCIPfreeBufferArray, subtractStartingJobDemands(), and tightenCoefs().
Referenced by getHighestCapacityUsage(), and presolveCons().
|
static |
tries to change coefficients: demand_j < cap && all other parallel jobs in conflict ==> set demand_j := cap
| scip | SCIP data structure |
| cons | cumulative constraint |
| nchgcoefs | pointer to count total number of changed coefficients |
Definition at line 10760 of file cons_cumulative.c.
References createDisjuctiveCons(), FALSE, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVar(), SCIPaggregateVars(), SCIPconsGetData(), SCIPconsGetName(), SCIPconvertRealToInt(), SCIPcreateVar(), SCIPdebugMsg, SCIPlockVarCons(), SCIPreleaseVar(), SCIPsnprintf(), SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsInitial(), SCIPvarIsRemovable(), and TRUE.
Referenced by presolveCons(), and tightenCapacity().
|
static |
creare a disjunctive constraint which contains all jobs which cannot run in parallel
| scip | SCIP data structure |
| cons | cumulative constraint |
| naddconss | pointer to store the number of added constraints |
Definition at line 10963 of file cons_cumulative.c.
References createConsCumulative(), FALSE, presolveCons(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPfreeBufferArray, and TRUE.
Referenced by SCIP_DECL_CONSPRESOL(), and tightenCoefs().
|
static |
presolve given constraint
| scip | SCIP data structure |
| cons | cumulative constraint |
| conshdlrdata | constraint handler data |
| presoltiming | timing of presolving call |
| nfixedvars | pointer to store the number of fixed variables |
| nchgbds | pointer to store the number of changed bounds |
| ndelconss | pointer to store the number of deleted constraints |
| naddconss | pointer to store the number of added constraints |
| nchgcoefs | pointer to store the number of changed coefficients |
| nchgsides | pointer to store the number of changed sides |
| cutoff | pointer to store if a cutoff was detected |
| unbounded | pointer to store if the problem is unbounded |
Definition at line 11046 of file cons_cumulative.c.
References checkDemands(), computeEffectiveHorizon(), deleteTrivilCons(), nnodes, normalizeDemands(), presolveConsEffectiveHorizon(), removeOversizedJobs(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIPallowDualReds(), SCIPconsIsDeleted(), solveIndependentCons(), TCLIQUE_GETNNODES(), tightenCapacity(), and tightenCoefs().
Referenced by createDisjuctiveCons(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().
|
static |
gets number of nodes in the graph
Definition at line 11151 of file cons_cumulative.c.
References TCLIQUE_GETWEIGHTS().
Referenced by presolveCons().
|
static |
gets weight of nodes in the graph
Definition at line 11160 of file cons_cumulative.c.
References TCLIQUE_ISEDGE().
Referenced by TCLIQUE_GETNNODES().
|
static |
returns, whether the edge (node1, node2) is in the graph
Definition at line 11169 of file cons_cumulative.c.
References FALSE, nnodes, TCLIQUE_SELECTADJNODES(), and TRUE.
Referenced by TCLIQUE_GETWEIGHTS().
|
static |
selects all nodes from a given set of nodes which are adjacent to a given node and returns the number of selected nodes
Definition at line 11190 of file cons_cumulative.c.
References nnodes, and TCLIQUE_NEWSOL().
Referenced by TCLIQUE_ISEDGE().
|
static |
generates cuts using a clique found by algorithm for maximum weight clique and decides whether to stop generating cliques with the algorithm for maximum weight clique
Definition at line 11224 of file cons_cumulative.c.
References impliesVlbPrecedenceCondition(), nnodes, SCIP_Bool, SCIPdebugMessage, and SCIPinfoMessage().
Referenced by TCLIQUE_SELECTADJNODES().
|
static |
print the tclique graph analyzes if the given variable lower bound condition implies a precedence condition w.r.t. given duration for the job corresponding to variable bound variable (vlbvar)
variable lower bound is given as: var >= vlbcoef * vlbvar + vlbconst
| scip | SCIP data structure |
| vlbvar | variable which bounds the variable from below |
| vlbcoef | variable bound coefficient |
| vlbconst | variable bound constant |
| duration | duration of the variable bound variable |
Definition at line 11262 of file cons_cumulative.c.
References bound, FALSE, impliesVubPrecedenceCondition(), SCIP_Bool, SCIP_Real, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by impliesVubPrecedenceCondition(), projectVbd(), and TCLIQUE_NEWSOL().
|
static |
analyzes if the given variable upper bound condition implies a precedence condition w.r.t. given duration for the job corresponding to variable which is bounded (var)
variable upper bound is given as: var <= vubcoef * vubvar + vubconst
| scip | SCIP data structure |
| var | variable which is bound from above |
| vubcoef | variable bound coefficient |
| vubconst | variable bound constant |
| duration | duration of the variable which is bounded from above |
Definition at line 11317 of file cons_cumulative.c.
References getNodeIdx(), impliesVlbPrecedenceCondition(), and SCIP_Real.
Referenced by impliesVlbPrecedenceCondition(), and projectVbd().
|
static |
get the corresponding index of the given variables; this in case of an active variable the problem index and for others an index larger than the number if active variables
| scip | SCIP data structure |
| tcliquegraph | incompatibility graph |
| var | variable for which we want the index |
| idx | pointer to store the index |
Definition at line 11339 of file cons_cumulative.c.
References BMSclearMemoryArray, projectVbd(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPreallocBufferArray, and SCIPvarGetProbindex().
Referenced by constraintNonOverlappingGraph(), impliesVubPrecedenceCondition(), initializeDurations(), and projectVbd().
|
static |
use the variables bounds of SCIP to projected variables bound graph into a precedence garph
Let d be the (assumed) duration of variable x and consider a variable bound of the form b * x + c <= y. This variable bounds implies a precedence condition x -> y (meaning job y starts after job x is finished) if:
(i) b = 1 and c >= d (ii) b > 1 and lb(x) >= (d - c)/(b - 1) (iii) b < 1 and ub(x) >= (d - c)/(b - 1)
| scip | SCIP data structure |
| tcliquegraph | incompatibility graph |
Definition at line 11430 of file cons_cumulative.c.
References getNodeIdx(), impliesVlbPrecedenceCondition(), impliesVubPrecedenceCondition(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetNVars(), SCIPgetVars(), SCIPisLE(), SCIPvarGetLbLocal(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), transitiveClosure(), and TRUE.
Referenced by constructIncompatibilityGraph(), and getNodeIdx().
|
static |
compute the transitive closer of the given graph and the number of in and out arcs
| adjmatrix | adjacent matrix |
| ninarcs | array to store the number of in arcs |
| noutarcs | array to store the number of out arcs |
| nnodes | number if nodes |
Definition at line 11525 of file cons_cumulative.c.
References constraintNonOverlappingGraph(), nnodes, and TRUE.
Referenced by constructIncompatibilityGraph(), and projectVbd().
|
static |
constructs a non-overlapping graph w.r.t. given durations and available cumulative constraints
| scip | SCIP data structure |
| tcliquegraph | incompatibility graph |
| conss | array of cumulative constraints |
| nconss | number of cumulative constraints |
Definition at line 11557 of file cons_cumulative.c.
References constructIncompatibilityGraph(), getNodeIdx(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by constructIncompatibilityGraph(), and transitiveClosure().
|
static |
constructs a conflict set graph (undirected) which contains for each job a node and edge if the corresponding pair of jobs cannot run in parallel
| scip | SCIP data structure |
| tcliquegraph | incompatibility graph |
| conss | array of cumulative constraints |
| nconss | number of cumulative constraints |
Definition at line 11653 of file cons_cumulative.c.
References constraintNonOverlappingGraph(), createCumulativeCons(), projectVbd(), SCIP_CALL, SCIP_OKAY, and transitiveClosure().
Referenced by constraintNonOverlappingGraph(), and detectRedundantConss().
|
static |
create cumulative constraint from conflict set
| scip | SCIP data structure |
| name | constraint name |
| tcliquegraph | conflict set graph |
| cliquenodes | array storing the indecies of the nodes belonging to the clique |
| ncliquenodes | number of nodes in the clique |
Definition at line 11677 of file cons_cumulative.c.
References FALSE, findCumulativeConss(), SCIP_CALL, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsCumulative(), SCIPfreeBufferArray, SCIPreleaseCons(), SCIPsortInt(), and TRUE.
Referenced by constructIncompatibilityGraph(), and findCumulativeConss().
|
static |
search for cumulative constrainst
| scip | SCIP data structure |
| tcliquegraph | conflict set graph |
| naddconss | pointer to store the number of added constraints |
Definition at line 11723 of file cons_cumulative.c.
References CONSHDLR_NAME, createCumulativeCons(), createPrecedenceCons(), FALSE, nnodes, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBufferArray, SCIPblkmem(), SCIPconshdlrGetData(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetNRuns(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPisStopped(), SCIPsnprintf(), SCIPstatistic, SCIPvarGetName(), and tcliqueMaxClique().
Referenced by createCumulativeCons(), and detectRedundantConss().
|
static |
create precedence constraint (as variable bound constraint
| scip | SCIP data structure |
| name | constraint name |
| var | variable x that has variable bound |
| vbdvar | binary, integer or implicit integer bounding variable y |
| distance | minimum distance between the start time of the job corresponding to var and the job corresponding to vbdvar |
Definition at line 11851 of file cons_cumulative.c.
References computeMinDistance(), FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPcreateConsVarbound(), SCIPdebugPrintCons, SCIPinfinity(), SCIPreleaseCons(), and TRUE.
Referenced by computeMinDistance(), findCumulativeConss(), and strengthenVarbounds().
|
static |
compute a minimum distance between the start times of the two given jobs and post it as variable bound constraint
| scip | SCIP data structure |
| tcliquegraph | conflict set graph |
| source | index of the source node |
| sink | index of the sink node |
| naddconss | pointer to store the number of added constraints |
Definition at line 11876 of file cons_cumulative.c.
References BMSclearMemoryArray, createPrecedenceCons(), findPrecedenceConss(), nnodes, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPfreeBufferArray, SCIPgetNRuns(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and tcliqueMaxClique().
Referenced by createPrecedenceCons(), and findPrecedenceConss().
|
static |
search for precedence constraints
for each arc of the transitive closure of the precedence graph, we are computing a minimum distance between the corresponding two jobs
| scip | SCIP data structure |
| tcliquegraph | conflict set graph |
| naddconss | pointer to store the number of added constraints |
Definition at line 11977 of file cons_cumulative.c.
References computeMinDistance(), CONSHDLR_NAME, initializeDurations(), nnodes, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPisStopped(), and SCIPstatistic.
Referenced by computeMinDistance(), and detectRedundantConss().
|
static |
initialize the assumed durations for each variable
| scip | SCIP data structure |
| tcliquegraph | the incompatibility graph |
| conss | cumulative constraints |
| nconss | number of cumulative constraints |
Definition at line 12045 of file cons_cumulative.c.
References createTcliqueGraph(), getNodeIdx(), MAX, SCIP_CALL, SCIP_OKAY, and SCIPconsGetData().
Referenced by detectRedundantConss(), and findPrecedenceConss().
|
static |
create tclique graph
| scip | SCIP data structure |
| tcliquegraph | reference to the incompatibility graph |
Definition at line 12089 of file cons_cumulative.c.
References BMSclearMemoryArray, freeTcliqueGraph(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPblkmem(), SCIPduplicateBufferArray, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapInsert(), and SCIPvarGetProbindex().
Referenced by detectRedundantConss(), and initializeDurations().
|
static |
frees the tclique graph
| scip | SCIP data structure |
| tcliquegraph | reference to the incompatibility graph |
Definition at line 12170 of file cons_cumulative.c.
References detectRedundantConss(), SCIPfreeBuffer, SCIPfreeBufferArray, and SCIPhashmapFree().
Referenced by createTcliqueGraph(), and detectRedundantConss().
|
static |
construct an incompatibility graph and search for precedence constraints (variables bounds) and unary cumulative constrains (disjunctive constraint)
| scip | SCIP data structure |
| conshdlrdata | constraint handler data |
| conss | array of cumulative constraints |
| nconss | number of cumulative constraints |
| naddconss | pointer to store the number of added constraints |
Definition at line 12199 of file cons_cumulative.c.
References consdataCalcSignature(), constructIncompatibilityGraph(), createTcliqueGraph(), findCumulativeConss(), findPrecedenceConss(), freeTcliqueGraph(), initializeDurations(), SCIP_CALL, and SCIP_OKAY.
Referenced by freeTcliqueGraph(), and SCIP_DECL_CONSPRESOL().
|
static |
compute the constraint signature which is used to detect constraints which contain potentially the same set of variables
| consdata | cumulative constraint data |
Definition at line 12238 of file cons_cumulative.c.
References SCIP_DECL_SORTINDCOMP(), SCIPvarGetIndex(), and TRUE.
Referenced by detectRedundantConss(), and removeRedundantConss().
|
static |
index comparison method of linear constraints: compares two indices of the variable set in the linear constraint
Definition at line 12262 of file cons_cumulative.c.
References removeRedundantConss(), and SCIPvarCompare().
Referenced by consdataCalcSignature().
|
static |
run a pairwise comparison
| scip | SCIP data structure |
| conss | array of cumulative constraints |
| nconss | number of cumulative constraints |
| ndelconss | pointer to store the number of deletedconstraints |
Definition at line 12275 of file cons_cumulative.c.
References consdataCalcSignature(), initializeLocks(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsIsChecked(), SCIPdelCons(), SCIPfreeBufferArray, SCIPsort(), SCIPswapPointers(), SCIPupdateConsFlags(), SCIPvarCompare(), strengthenVarbounds(), and TRUE.
Referenced by SCIP_DECL_CONSPRESOL(), and SCIP_DECL_SORTINDCOMP().
|
static |
strengthen the variable bounds using the cumulative condition
| scip | SCIP data structure |
| cons | constraint to propagate |
| nchgbds | pointer to store the number of changed bounds |
| naddconss | pointer to store the number of added constraints |
Definition at line 12415 of file cons_cumulative.c.
References createPrecedenceCons(), enforceConstraint(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarVlb(), SCIPconsGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPgetNRuns(), SCIPisEQ(), SCIPisStopped(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), and TRUE.
Referenced by removeRedundantConss(), and SCIP_DECL_CONSPRESOL().
|
static |
helper function to enforce constraints
| scip | SCIP data structure |
| conshdlr | constraint handler |
| conss | constraints to process |
| nconss | number of constraints |
| nusefulconss | number of useful (non-obsolete) constraints to process |
| sol | solution to enforce (NULL for the LP solution) |
| solinfeasible | was the solution already declared infeasible by a constraint handler? |
| result | pointer to store the result of the enforcing call |
Definition at line 12511 of file cons_cumulative.c.
References checkCons(), CONSHDLR_NAME, enforceSolution(), FALSE, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSHDLRCOPY(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, and separateConsBinaryRepresentation().
Referenced by SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFORELAX(), and strengthenVarbounds().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 12615 of file cons_cumulative.c.
References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfindConshdlr(), SCIPincludeConshdlrCumulative(), SCIPstatistic, and TRUE.
Referenced by enforceConstraint().
|
static |
destructor of constraint handler to free constraint handler data (called when SCIP is exiting)
Definition at line 12633 of file cons_cumulative.c.
References CONSHDLR_NAME, conshdlrdataFree(), SCIP_DECL_CONSINITPRE(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconshdlrSetData(), and SCIPstatisticPrintf.
Referenced by SCIP_DECL_CONSHDLRCOPY().
|
static |
presolving initialization method of constraint handler (called when presolving is about to begin)
Definition at line 12666 of file cons_cumulative.c.
References FALSE, removeIrrelevantJobs(), SCIP_CALL, SCIP_DECL_CONSEXITPRE, SCIP_DECL_CONSEXITSOL(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPstatisticPrintf, and SCIPvisualizeConsCumulative().
Referenced by SCIP_DECL_CONSFREE().
|
static |
presolving deinitialization method of constraint handler (called after presolving has been finished) solving process deinitialization method of constraint handler (called before branch and bound process data is freed)
Definition at line 12728 of file cons_cumulative.c.
References consdataFreeRows(), CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSDELETE(), SCIP_OKAY, SCIPconsGetData(), and SCIPconshdlrGetName().
Referenced by SCIP_DECL_CONSINITPRE().
|
static |
frees specific constraint data
Definition at line 12751 of file cons_cumulative.c.
References consdataDropAllEvents(), consdataFree(), CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSTRANS(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPvarIsTransformed().
Referenced by SCIP_DECL_CONSEXITSOL().
|
static |
transforms constraint data into data belonging to the transformed problem
Definition at line 12777 of file cons_cumulative.c.
References consdataCatchEvents(), consdataCreate(), SCIP_CALL, SCIP_DECL_CONSINITLP(), SCIP_OKAY, SCIP_STAGE_TRANSFORMING, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateCons(), SCIPdebugMsg, and SCIPgetStage().
Referenced by SCIP_DECL_CONSDELETE().
|
static |
LP initialization method of constraint handler
Definition at line 12819 of file cons_cumulative.c.
References addRelaxation(), CONSHDLR_NAME, FALSE, SCIP_CALL, SCIP_DECL_CONSSEPALP(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsInitial(), SCIPdebugMsg, and SCIPrestartSolve().
Referenced by SCIP_DECL_CONSTRANS().
|
static |
separation method of constraint handler for LP solutions
Definition at line 12856 of file cons_cumulative.c.
References CONSHDLR_NAME, FALSE, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSSEPASOL(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetDepth(), separateConsBinaryRepresentation(), separateConsOnIntegerVariables(), separateCoverCutsCons(), and TRUE.
Referenced by SCIP_DECL_CONSINITLP().
|
static |
separation method of constraint handler for arbitrary primal solutions
Definition at line 12920 of file cons_cumulative.c.
References CONSHDLR_NAME, FALSE, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSENFOLP(), SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetDepth(), separateConsBinaryRepresentation(), separateConsOnIntegerVariables(), separateCoverCutsCons(), and TRUE.
Referenced by SCIP_DECL_CONSSEPALP().
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 12980 of file cons_cumulative.c.
References enforceConstraint(), SCIP_CALL, SCIP_DECL_CONSENFORELAX(), and SCIP_OKAY.
Referenced by SCIP_DECL_CONSSEPASOL().
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 12989 of file cons_cumulative.c.
References enforceConstraint(), SCIP_CALL, SCIP_DECL_CONSENFOPS(), and SCIP_OKAY.
Referenced by SCIP_DECL_CONSENFOLP().
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 12998 of file cons_cumulative.c.
References CONSHDLR_NAME, enforceSolution(), SCIP_CALL, SCIP_DECL_CONSCHECK(), SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.
Referenced by SCIP_DECL_CONSENFORELAX().
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 13027 of file cons_cumulative.c.
References checkCons(), CONSHDLR_NAME, FALSE, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSPROP(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconshdlrGetName(), and SCIPdebugMsg.
Referenced by SCIP_DECL_CONSENFOPS().
|
static |
domain propagation method of constraint handler
Definition at line 13055 of file cons_cumulative.c.
References CONSHDLR_NAME, FALSE, presolveCons(), propagateAllConss(), propagateCons(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSPRESOL(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PRESOLTIMING_ALWAYS, SCIP_REDUCEDDOM, SCIPallowDualReds(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsDeleted(), SCIPdebugMsg, SCIPgetDepth(), and TRUE.
Referenced by SCIP_DECL_CONSCHECK().
|
static |
presolving method of constraint handler
Definition at line 13142 of file cons_cumulative.c.
References checkDemands(), CONSHDLR_NAME, createDisjuctiveCons(), detectRedundantConss(), FALSE, presolveCons(), propagateAllConss(), propagateCons(), removeIrrelevantJobs(), removeRedundantConss(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSRESPROP(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_PRESOLTIMING_FAST, SCIP_PRESOLTIMING_MEDIUM, SCIP_SUCCESS, SCIP_UNBOUNDED, SCIPallowDualReds(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsDeleted(), SCIPdebugMsg, SCIPgetNRuns(), strengthenVarbounds(), and TRUE.
Referenced by SCIP_DECL_CONSPROP().
|
static |
propagation conflict resolving method of constraint handler
Definition at line 13264 of file cons_cumulative.c.
References CONSHDLR_NAME, inferInfoGetProprule(), intToInferInfo(), respropCumulativeCondition(), SCIP_CALL, SCIP_DECL_CONSLOCK(), SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetHmaxCumulative(), SCIPgetHminCumulative(), and SCIPvarGetName().
Referenced by SCIP_DECL_CONSPRESOL().
|
static |
variable rounding lock method of constraint handler
Definition at line 13298 of file cons_cumulative.c.
References SCIP_CALL, SCIP_DECL_CONSPRINT(), SCIP_OKAY, SCIPaddVarLocks(), SCIPconsGetData(), SCIPconsGetName(), and SCIPdebugMsg.
Referenced by SCIP_DECL_CONSRESPROP().
|
static |
constraint display method of constraint handler
Definition at line 13338 of file cons_cumulative.c.
References consdataPrint(), SCIP_DECL_CONSCOPY(), SCIP_OKAY, and SCIPconsGetData().
Referenced by SCIP_DECL_CONSLOCK().
|
static |
constraint copying method of constraint handler
Definition at line 13351 of file cons_cumulative.c.
References SCIP_CALL, SCIP_DECL_CONSPARSE(), SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPcreateConsCumulative(), SCIPfreeBufferArray, SCIPgetVarCopy(), SCIPsetHmaxCumulative(), SCIPsetHminCumulative(), and TRUE.
Referenced by SCIP_DECL_CONSPRINT().
|
static |
constraint parsing method of constraint handler
Definition at line 13417 of file cons_cumulative.c.
References SCIP_CALL, SCIP_DECL_CONSGETVARS(), SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateConsCumulative(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPparseVarName(), SCIPsetHmaxCumulative(), SCIPsetHminCumulative(), SCIPstrCopySection(), SCIPstrToRealValue(), SCIPvarGetName(), and TRUE.
Referenced by SCIP_DECL_CONSCOPY().
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 13512 of file cons_cumulative.c.
References BMScopyMemoryArray, FALSE, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), and TRUE.
Referenced by SCIP_DECL_CONSPARSE().
|
static |
constraint method of constraint handler which returns the number of variables (if possible)
Definition at line 13534 of file cons_cumulative.c.
References SCIP_DECL_EVENTEXEC(), SCIP_OKAY, SCIPconsGetData(), and TRUE.
Referenced by SCIP_DECL_CONSGETVARS().
|
static |
execution method of event handler
Definition at line 13557 of file cons_cumulative.c.
References EVENTHDLR_NAME, FALSE, SCIP_OKAY, SCIPeventhdlrGetName(), and SCIPincludeConshdlrCumulative().
Referenced by SCIP_DECL_CONSGETNVARS().