SCIP
Solving Constraint Integer Programs
cons_cumulative.c File Reference
Detailed Description
constraint handler for cumulative constraints
Given:
- a set of jobs, represented by their integer start time variables \(S_j\), their array of processing times \(p_j\) and of their demands \(d_j\).
- an integer resource capacity \(C\)
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:
- can be done using binary start time model, see Pritskers, Watters and Wolfe
- or by just separating relatively weak cuts on the integer start time variables
Propagation:
- time tabling, Klein & Scholl (1999)
- Edge-finding from Petr Vilim, adjusted and simplified for dynamic repropagation (2009)
- energetic reasoning, see Baptiste, Le Pape, Nuijten (2001)
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 SCIP_Longint | 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 SCIP_Longint | 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, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | separateConsOnIntegerVariables (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool lower, SCIP_Bool *separated, SCIP_Bool *cutoff) |
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 void | normalizeCumulativeCondition (SCIP *scip, int nvars, int *demands, int *capacity, int *nchgcoefs, int *nchgsides) |
| static void | 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 void | 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 = 0, PROPRULE_2 = 1, PROPRULE_3 = 2, PROPRULE_4 = 3, PROPRULE_INVALID = 4, 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_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 void | computeCoreEnergyAfter (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, SCIP_Longint 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, SCIP_Longint 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 void | updateEnvelope (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_CONS **conss, int nconss, SCIP_Bool local, int *nfixedvars, SCIP_Bool *cutoff, SCIP_Bool *branched) |
Macro Definition Documentation
◆ CONSHDLR_NAME
| #define CONSHDLR_NAME "cumulative" |
Definition at line 59 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().
◆ CONSHDLR_DESC
| #define CONSHDLR_DESC "cumulative constraint handler" |
Definition at line 60 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ CONSHDLR_SEPAPRIORITY
| #define CONSHDLR_SEPAPRIORITY 2100000 |
priority of the constraint handler for separation
Definition at line 61 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ CONSHDLR_ENFOPRIORITY
| #define CONSHDLR_ENFOPRIORITY -2040000 |
priority of the constraint handler for constraint enforcing
Definition at line 62 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ CONSHDLR_CHECKPRIORITY
| #define CONSHDLR_CHECKPRIORITY -3030000 |
priority of the constraint handler for checking feasibility
Definition at line 63 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ CONSHDLR_SEPAFREQ
| #define CONSHDLR_SEPAFREQ 1 |
frequency for separating cuts; zero means to separate only in the root node
Definition at line 64 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ CONSHDLR_PROPFREQ
| #define CONSHDLR_PROPFREQ 1 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 65 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ CONSHDLR_EAGERFREQ
| #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 66 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ CONSHDLR_MAXPREROUNDS
| #define CONSHDLR_MAXPREROUNDS -1 |
maximal number of presolving rounds the constraint handler participates in (-1: no limit)
Definition at line 69 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ CONSHDLR_DELAYSEPA
| #define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 70 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ CONSHDLR_DELAYPROP
| #define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 71 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ CONSHDLR_NEEDSCONS
| #define CONSHDLR_NEEDSCONS TRUE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 72 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ CONSHDLR_PRESOLTIMING
| #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS |
Definition at line 74 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ CONSHDLR_PROP_TIMING
| #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
Definition at line 75 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_USEBINVARS
| #define DEFAULT_USEBINVARS FALSE |
should the binary representation be used?
Definition at line 87 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_LOCALCUTS
| #define DEFAULT_LOCALCUTS FALSE |
should cuts be added only locally?
Definition at line 88 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_USECOVERCUTS
| #define DEFAULT_USECOVERCUTS TRUE |
should covering cuts be added?
Definition at line 89 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_CUTSASCONSS
| #define DEFAULT_CUTSASCONSS TRUE |
should the cuts be created as knapsack constraints?
Definition at line 90 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_SEPAOLD
| #define DEFAULT_SEPAOLD TRUE |
shall old sepa algo be applied?
Definition at line 91 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_TTINFER
| #define DEFAULT_TTINFER TRUE |
should time-table (core-times) propagator be used to infer bounds?
Definition at line 94 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_EFCHECK
| #define DEFAULT_EFCHECK FALSE |
should edge-finding be used to detect an overload?
Definition at line 95 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_EFINFER
| #define DEFAULT_EFINFER FALSE |
should edge-finding be used to infer bounds?
Definition at line 96 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_USEADJUSTEDJOBS
| #define DEFAULT_USEADJUSTEDJOBS FALSE |
should during edge-finding jobs be adusted which run on the border of the effective time horizon?
Definition at line 97 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_TTEFCHECK
| #define DEFAULT_TTEFCHECK TRUE |
should time-table edge-finding be used to detect an overload?
Definition at line 98 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_TTEFINFER
| #define DEFAULT_TTEFINFER TRUE |
should time-table edge-finding be used to infer bounds?
Definition at line 99 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_DUALPRESOLVE
| #define DEFAULT_DUALPRESOLVE TRUE |
should dual presolving be applied?
Definition at line 102 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_COEFTIGHTENING
| #define DEFAULT_COEFTIGHTENING FALSE |
should coeffisient tightening be applied?
Definition at line 103 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_NORMALIZE
| #define DEFAULT_NORMALIZE TRUE |
should demands and capacity be normalized?
Definition at line 104 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_PRESOLPAIRWISE
| #define DEFAULT_PRESOLPAIRWISE TRUE |
should pairwise constraint comparison be performed in presolving?
Definition at line 105 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_DISJUNCTIVE
| #define DEFAULT_DISJUNCTIVE TRUE |
extract disjunctive constraints?
Definition at line 106 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_DETECTDISJUNCTIVE
| #define DEFAULT_DETECTDISJUNCTIVE TRUE |
search for conflict set via maximal cliques to detect disjunctive constraints
Definition at line 107 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_DETECTVARBOUNDS
| #define DEFAULT_DETECTVARBOUNDS TRUE |
search for conflict set via maximal cliques to detect variable bound constraints
Definition at line 108 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_MAXNODES
| #define DEFAULT_MAXNODES 10000LL |
number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit)
Definition at line 109 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_FILLBRANCHCANDS
| #define DEFAULT_FILLBRANCHCANDS FALSE |
should branching candidates be added to storage?
Definition at line 112 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ DEFAULT_USEBDWIDENING
| #define DEFAULT_USEBDWIDENING TRUE |
should bound widening be used during conflict analysis?
Definition at line 115 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
◆ EVENTHDLR_NAME
| #define EVENTHDLR_NAME "cumulative" |
Definition at line 124 of file cons_cumulative.c.
Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludeConshdlrCumulative().
◆ EVENTHDLR_DESC
| #define EVENTHDLR_DESC "bound change event handler for cumulative constraints" |
Definition at line 125 of file cons_cumulative.c.
Referenced by SCIPincludeConshdlrCumulative().
Typedef Documentation
◆ PROPRULE
Definition at line 257 of file cons_cumulative.c.
◆ INFERINFO
| typedef struct InferInfo INFERINFO |
Definition at line 274 of file cons_cumulative.c.
◆ SCIP_NODEDATA
| typedef struct SCIP_NodeData SCIP_NODEDATA |
Definition at line 5677 of file cons_cumulative.c.
Enumeration Type Documentation
◆ Proprule
| enum Proprule |
Propagation rules
Definition at line 251 of file cons_cumulative.c.
Function Documentation
◆ intToInferInfo()
|
static |
converts an integer into an inference information
- Parameters
-
i integer to convert
Definition at line 278 of file cons_cumulative.c.
References inferInfoToInt().
Referenced by propagateTTEF(), SCIP_DECL_CONSRESPROP(), and SCIPrespropCumulativeCondition().
◆ inferInfoToInt()
|
static |
converts an inference information into an int
- Parameters
-
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().
◆ inferInfoGetProprule()
returns the propagation rule stored in the inference information
- Parameters
-
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().
◆ inferInfoGetData1()
|
static |
returns data field one of the inference information
- Parameters
-
inferinfo inference information to convert
Definition at line 309 of file cons_cumulative.c.
References inferInfoGetData2().
Referenced by inferInfoGetProprule(), propagateTTEF(), resolvePropagationCoretimes(), and respropCumulativeCondition().
◆ inferInfoGetData2()
|
static |
returns data field two of the inference information
- Parameters
-
inferinfo inference information to convert
Definition at line 318 of file cons_cumulative.c.
References getInferInfo().
Referenced by inferInfoGetData1(), propagateTTEF(), resolvePropagationCoretimes(), and respropCumulativeCondition().
◆ getInferInfo()
constructs an inference information out of a propagation rule, an earliest start and a latest completion time
- Parameters
-
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(), and SCIP_Longint.
Referenced by coretimesUpdateLb(), coretimesUpdateUb(), inferboundsEdgeFinding(), inferInfoGetData2(), propagateLbTTEF(), propagateUbTTEF(), tightenLbTTEF(), and tightenUbTTEF().
◆ computeCoreWithInterval()
|
static |
compute the core of a job which lies in certain interval [begin, end)
- Parameters
-
begin begin of the interval end end of the interval ect earliest completion time lst latest start time
Definition at line 362 of file cons_cumulative.c.
References computeImpliedEst(), and MAX.
Referenced by collectDataTTEF(), getInferInfo(), propagateLbTTEF(), propagateUbTTEF(), tightenLbTTEF(), and tightenUbTTEF().
◆ computeImpliedEst()
|
static |
returns the implied earliest start time
- Parameters
-
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 381 of file cons_cumulative.c.
References computeImpliedLct(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPhashmapGetImage(), SCIPhashmapRemove(), SCIPisEQ(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), and SCIPvarGetVlbVars().
Referenced by computeCoreWithInterval(), and SCIPcreateWorstCaseProfile().
◆ computeImpliedLct()
|
static |
returns the implied latest completion time
- Parameters
-
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 449 of file cons_cumulative.c.
References collectBinaryVars(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPhashmapExists(), SCIPhashmapRemove(), SCIPisEQ(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNVubs(), SCIPvarGetUbLocal(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), and SCIPvarGetVubVars().
Referenced by computeImpliedEst(), and SCIPcreateWorstCaseProfile().
◆ collectBinaryVars()
|
static |
collects all necessary binary variables to represent the jobs which can be active at time point of interest
- Parameters
-
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 513 of file cons_cumulative.c.
References b, collectIntVars(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPexistsConsLinking(), SCIPgetBinvarsLinking(), SCIPgetConsLinking(), SCIPgetValsLinking(), SCIPreallocBufferArray, and SCIPvarGetUbGlobal().
Referenced by computeImpliedLct(), and createCapacityRestriction().
◆ collectIntVars()
|
static |
collect all integer variable which belong to jobs which can run at the point of interest
- Parameters
-
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 611 of file cons_cumulative.c.
References createSortedEventpoints(), NULL, SCIP_OKAY, SCIPconvertRealToInt(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by collectBinaryVars(), and createCapacityRestrictionIntvars().
◆ createSortedEventpoints()
|
static |
initialize the sorted event point arrays
- Parameters
-
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 685 of file cons_cumulative.c.
References createSortedEventpointsSol(), NULL, SCIPconvertRealToInt(), SCIPsortIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().
Referenced by collectIntVars(), consCapacityConstraintsFinder(), createSelectedSortedEventpointsSol(), and tightenCapacity().
◆ createSortedEventpointsSol()
|
static |
initialize the sorted event point arrays w.r.t. the given primal solutions
- Parameters
-
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 732 of file cons_cumulative.c.
References createSelectedSortedEventpointsSol(), NULL, SCIPconvertRealToInt(), SCIPgetSolVal(), and SCIPsortIntInt().
Referenced by computePeak(), and createSortedEventpoints().
◆ createSelectedSortedEventpointsSol()
|
static |
initialize the sorted event point arrays
- Parameters
-
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 774 of file cons_cumulative.c.
References createSortedEventpoints(), getActiveVar(), MAX, NULL, 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().
◆ getActiveVar()
|
static |
gets the active variables together with the constant
- Parameters
-
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 1149 of file cons_cumulative.c.
References computeTotalEnergy(), SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIPconvertRealToInt(), SCIPgetProbvarSum(), SCIPisZero(), SCIPvarGetStatus(), and SCIPvarIsActive().
Referenced by computeAlternativeBounds(), createSelectedSortedEventpointsSol(), varMayRoundDown(), and varMayRoundUp().
◆ computeTotalEnergy()
|
static |
computes the total energy of all jobs
- Parameters
-
durations array of job durations demands array of job demands njobs number of jobs
Definition at line 1194 of file cons_cumulative.c.
References SCIP_Longint, and setupAndSolveCumulativeSubscip().
Referenced by getActiveVar(), propagateLbTTEF(), and propagateUbTTEF().
◆ setupAndSolveCumulativeSubscip()
|
static |
setup and solve subscip to solve single cumulative condition
- Parameters
-
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 1220 of file cons_cumulative.c.
References FALSE, NULL, 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_TERMINATE, 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().
◆ SCIP_DECL_SOLVECUMULATIVE()
|
static |
solve single cumulative condition using SCIP and a single cumulative constraint
Definition at line 1385 of file cons_cumulative.c.
References conshdlrdataCreate(), FALSE, MAX, NULL, 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().
◆ conshdlrdataCreate()
|
static |
creates constaint handler data for cumulative constraint handler
- Parameters
-
scip SCIP data structure conshdlrdata pointer to store the constraint handler data eventhdlr event handler
Definition at line 1726 of file cons_cumulative.c.
References conshdlrdataFree(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
Referenced by SCIP_DECL_SOLVECUMULATIVE(), and SCIPincludeConshdlrCumulative().
◆ conshdlrdataFree()
|
static |
frees constraint handler data for logic or constraint handler
- Parameters
-
scip SCIP data structure conshdlrdata pointer to the constraint handler data
Definition at line 1771 of file cons_cumulative.c.
References consdataCatchEvents(), NULL, and SCIPfreeBlockMemory.
Referenced by conshdlrdataCreate(), and SCIP_DECL_CONSFREE().
◆ consdataCatchEvents()
|
static |
catches bound change events for all variables in transformed cumulative constraint
- Parameters
-
scip SCIP data structure consdata cumulative constraint data eventhdlr event handler to call for the event processing
Definition at line 1792 of file cons_cumulative.c.
References consdataDropEvents(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDTIGHTENED, SCIP_OKAY, and SCIPcatchVarEvent().
Referenced by conshdlrdataFree(), SCIP_DECL_CONSTRANS(), and SCIPcreateConsCumulative().
◆ consdataDropEvents()
|
static |
drops events for variable at given position
- Parameters
-
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 1816 of file cons_cumulative.c.
References consdataDropAllEvents(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDTIGHTENED, SCIP_OKAY, and SCIPdropVarEvent().
Referenced by consdataCatchEvents(), consdataDeletePos(), and consdataDropAllEvents().
◆ consdataDropAllEvents()
|
static |
drops bound change events for all variables in transformed linear constraint
- Parameters
-
scip SCIP data structure consdata linear constraint data eventhdlr event handler to call for the event processing
Definition at line 1837 of file cons_cumulative.c.
References consdataDropEvents(), initializeLocks(), NULL, SCIP_CALL, and SCIP_OKAY.
Referenced by consdataDropEvents(), and SCIP_DECL_CONSDELETE().
◆ initializeLocks()
|
static |
initialize variable lock data structure
- Parameters
-
consdata constraint data locked should the variable be locked?
Definition at line 1859 of file cons_cumulative.c.
References consdataCreate().
Referenced by consdataCreate(), consdataDropAllEvents(), and removeRedundantConss().
◆ consdataCreate()
|
static |
creates constraint data of cumulative constraint
- Parameters
-
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 1879 of file cons_cumulative.c.
References consdataFreeRows(), FALSE, initializeLocks(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPgetConsLinking(), SCIPgetTransformedVars(), SCIPisTransformed(), SCIPmarkDoNotMultaggrVar(), SCIPstatistic, and SCIPtransformConss().
Referenced by initializeLocks(), SCIP_DECL_CONSTRANS(), and SCIPcreateConsCumulative().
◆ consdataFreeRows()
|
static |
releases LP rows of constraint data and frees rows array
- Parameters
-
scip SCIP data structure consdata constraint data
Definition at line 2001 of file cons_cumulative.c.
References consdataFree(), FALSE, NULL, r, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseRow().
Referenced by consdataCreate(), consdataFree(), and SCIP_DECL_CONSEXITSOL().
◆ consdataFree()
|
static |
frees a cumulative constraint data
- Parameters
-
scip SCIP data structure consdata pointer to linear constraint data
Definition at line 2052 of file cons_cumulative.c.
References consdataFreeRows(), consdataPrint(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPreleaseCons().
Referenced by consdataFreeRows(), and SCIP_DECL_CONSDELETE().
◆ consdataPrint()
|
static |
prints cumulative constraint to file stream
- Parameters
-
scip SCIP data structure consdata cumulative constraint data file output file (or NULL for standard output)
Definition at line 2101 of file cons_cumulative.c.
References consdataDeletePos(), NULL, SCIPinfoMessage(), SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().
Referenced by consdataFree(), and SCIP_DECL_CONSPRINT().
◆ consdataDeletePos()
|
static |
deletes coefficient at given position from constraint data
- Parameters
-
scip SCIP data structure consdata cumulative constraint data cons knapsack constraint pos position of coefficient to delete
Definition at line 2128 of file cons_cumulative.c.
References consdataCollectLinkingCons(), consdataDropEvents(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsTransformed(), SCIPdebugMsg, SCIPinProbing(), SCIPreleaseCons(), SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().
Referenced by consdataPrint(), presolveConsEffectiveHorizon(), removeIrrelevantJobs(), and removeOversizedJobs().
◆ consdataCollectLinkingCons()
|
static |
collect linking constraints for each integer variable
- Parameters
-
scip SCIP data structure consdata pointer to consdata
Definition at line 2197 of file cons_cumulative.c.
References checkCumulativeCondition(), FALSE, NULL, 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().
◆ checkCumulativeCondition()
|
static |
check for the given starting time variables with their demands and durations if the cumulative conditions for the given solution is satisfied
- Parameters
-
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 2264 of file cons_cumulative.c.
References checkCons(), FALSE, MAX, NULL, 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().
◆ checkCons()
|
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
- Parameters
-
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 2422 of file cons_cumulative.c.
References checkCumulativeCondition(), NULL, resolvePropagationCoretimes(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), and SCIPdebugMsg.
Referenced by checkCumulativeCondition(), enforceConstraint(), enforceSolution(), and SCIP_DECL_CONSCHECK().
◆ resolvePropagationCoretimes()
|
static |
resolves the propagation of the core time algorithm
- Parameters
-
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 2458 of file cons_cumulative.c.
References BMSclearMemoryArray, computeOverlap(), FALSE, inferInfoGetData1(), inferInfoGetData2(), inferInfoGetProprule(), MAX, NULL, 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().
◆ computeOverlap()
|
static |
compute the minimum overlaps w.r.t. the duration of the job and the time window [begin,end)
- Parameters
-
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 2812 of file cons_cumulative.c.
References analyzeEnergyRequirement().
Referenced by analyzeEnergyRequirement(), and resolvePropagationCoretimes().
◆ analyzeEnergyRequirement()
|
static |
an overload was detected due to the time-time edge-finding propagate; initialized conflict analysis, add an initial reason
- Note
- the conflict analysis is not performend, only the initialized SCIP_Bool pointer is set to TRUE
- Parameters
-
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 2849 of file cons_cumulative.c.
References computeOverlap(), FALSE, NULL, respropCumulativeCondition(), SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, 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().
◆ respropCumulativeCondition()
|
static |
resolve propagation w.r.t. the cumulative condition
- Parameters
-
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 3136 of file cons_cumulative.c.
References analyzeEnergyRequirement(), applyAlternativeBoundsBranching(), FALSE, inferInfoGetData1(), inferInfoGetData2(), inferInfoGetProprule(), MAX, NULL, 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().
◆ applyAlternativeBoundsBranching()
|
static |
apply all fixings which are given by the alternative bounds
- Parameters
-
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 3313 of file cons_cumulative.c.
References NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPbranchVarHole(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPisNegative(), SCIPisPositive(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarGetUbLocal(), subtractStartingJobDemands(), and TRUE.
Referenced by propagateAllConss(), and respropCumulativeCondition().
◆ subtractStartingJobDemands()
|
static |
remove the capacity requirments for all job which start at the curtime
- Parameters
-
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 3378 of file cons_cumulative.c.
References addEndingJobDemands(), and NULL.
Referenced by applyAlternativeBoundsBranching(), computePeak(), consCapacityConstraintsFinder(), separateConsOnIntegerVariables(), and tightenCapacity().
◆ addEndingJobDemands()
|
static |
add the capacity requirments for all job which end at the curtime
- Parameters
-
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 3420 of file cons_cumulative.c.
References computePeak().
Referenced by computePeak(), consCapacityConstraintsFinder(), separateConsOnIntegerVariables(), subtractStartingJobDemands(), and tightenCapacity().
◆ computePeak()
|
static |
computes a point in time when the capacity is exceeded returns hmax if this does not happen
- Parameters
-
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 3449 of file cons_cumulative.c.
References addEndingJobDemands(), collectBranchingCands(), createSortedEventpointsSol(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, and subtractStartingJobDemands().
Referenced by addEndingJobDemands(), and collectBranchingCands().
◆ collectBranchingCands()
|
static |
checks all cumulative constraints for infeasibility and add branching candidates to storage
- Parameters
-
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 3534 of file cons_cumulative.c.
References computePeak(), enforceSolution(), NULL, 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().
◆ enforceSolution()
|
static |
enforcement of an LP, pseudo, or relaxation solution
- Parameters
-
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 3621 of file cons_cumulative.c.
References branch(), checkCons(), collectBranchingCands(), FALSE, isConsIndependently(), NULL, SCIP_Bool, SCIP_CALL, SCIP_INFEASIBLE, and SCIP_OKAY.
Referenced by collectBranchingCands(), enforceConstraint(), and SCIP_DECL_CONSENFOPS().
◆ isConsIndependently()
check if cumulative constraint is independently of all other constraints
- Parameters
-
cons cumulative constraint
Definition at line 3674 of file cons_cumulative.c.
References FALSE, NULL, SCIP_Bool, SCIP_LOCKTYPE_MODEL, SCIPconsGetData(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), solveIndependentCons(), and TRUE.
Referenced by enforceSolution(), and solveIndependentCons().
◆ solveIndependentCons()
|
static |
in case the cumulative constraint is independent of every else, solve the cumulative problem and apply the fixings (dual reductions)
- Parameters
-
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 3713 of file cons_cumulative.c.
References analyseInfeasibelCoreInsertion(), FALSE, isConsIndependently(), NULL, 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().
◆ analyseInfeasibelCoreInsertion()
|
static |
start conflict analysis to analysis the core insertion which is infeasible
- Parameters
-
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 3928 of file cons_cumulative.c.
References coretimesUpdateLb(), FALSE, NULL, 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().
◆ coretimesUpdateLb()
|
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
- Parameters
-
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 3984 of file cons_cumulative.c.
References analyseInfeasibelCoreInsertion(), CONSHDLR_NAME, coretimesUpdateUb(), getInferInfo(), inferInfoToInt(), NULL, 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().
◆ coretimesUpdateUb()
|
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
- Parameters
-
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 4137 of file cons_cumulative.c.
References computeCoreEnergyAfter(), CONSHDLR_NAME, getInferInfo(), inferInfoToInt(), MAX, NULL, 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().
◆ computeCoreEnergyAfter()
|
static |
compute for the different earliest start and latest completion time the core energy of the corresponding time points
- Parameters
-
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 4271 of file cons_cumulative.c.
References collectDataTTEF(), SCIPprofileGetLoad(), SCIPprofileGetNTimepoints(), and SCIPprofileGetTime().
Referenced by coretimesUpdateUb(), and propagateTTEF().
◆ collectDataTTEF()
|
static |
collect earliest start times, latest completion time, and free energy contributions
- Parameters
-
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 4339 of file cons_cumulative.c.
References computeCoreWithInterval(), MAX, SCIPconvertRealToInt(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and tightenLbTTEF().
Referenced by computeCoreEnergyAfter(), and propagateTTEF().
◆ tightenLbTTEF()
|
static |
try to tighten the lower bound of the given variable
- Parameters
-
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 4407 of file cons_cumulative.c.
References analyzeEnergyRequirement(), computeCoreWithInterval(), FALSE, getInferInfo(), inferInfoToInt(), MAX, NULL, PROPRULE_3_TTEF, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPaddConflictUb(), SCIPconvertRealToInt(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPvarGetUbLocal(), tightenUbTTEF(), and TRUE.
Referenced by collectDataTTEF(), and propagateLbTTEF().
◆ tightenUbTTEF()
|
static |
try to tighten the upper bound of the given variable
- Parameters
-
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 4520 of file cons_cumulative.c.
References analyzeEnergyRequirement(), computeCoreWithInterval(), FALSE, getInferInfo(), inferInfoToInt(), MAX, NULL, propagateUbTTEF(), PROPRULE_3_TTEF, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPconvertRealToInt(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPvarGetLbLocal(), and TRUE.
Referenced by propagateUbTTEF(), and tightenLbTTEF().
◆ propagateUbTTEF()
|
static |
propagate the upper bounds and "opportunistically" the lower bounds using the time-table edge-finding algorithm
- Parameters
-
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 4634 of file cons_cumulative.c.
References analyzeEnergyRequirement(), computeCoreWithInterval(), computeTotalEnergy(), CONSHDLR_NAME, FALSE, getInferInfo(), inferInfoToInt(), MAX, NULL, propagateLbTTEF(), PROPRULE_3_TTEF, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_Longint, 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().
◆ propagateLbTTEF()
|
static |
propagate the lower bounds and "opportunistically" the upper bounds using the time-table edge-finding algorithm
- Parameters
-
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 4985 of file cons_cumulative.c.
References analyzeEnergyRequirement(), computeCoreWithInterval(), computeTotalEnergy(), CONSHDLR_NAME, FALSE, getInferInfo(), inferInfoToInt(), MAX, NULL, propagateTTEF(), PROPRULE_3_TTEF, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_Longint, 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().
◆ propagateTTEF()
|
static |
checks whether the instance is infeasible due to a overload within a certain time frame using the idea of time-table edge-finding
- Note
- The algorithm is based on the following two papers:
- Petr Vilim, "Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources", In: Tobias Achterberg and J. Christopher Beck (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2011), LNCS 6697, pp 230–245
- Andreas Schutt, Thibaut Feydy, and Peter J. Stuckey, "Explaining Time-Table-Edge-Finding Propagation for the Cumulative Resource Constraint (submitted to CPAIOR 2013)
- Parameters
-
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 5325 of file cons_cumulative.c.
References analyzeEnergyRequirement(), collectDataTTEF(), computeCoreEnergyAfter(), CONSHDLR_NAME, FALSE, inferInfoGetData1(), inferInfoGetData2(), intToInferInfo(), NULL, 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().
◆ propagateTimetable()
|
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
- Parameters
-
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 5514 of file cons_cumulative.c.
References analyseInfeasibelCoreInsertion(), CONSHDLR_NAME, coretimesUpdateLb(), coretimesUpdateUb(), FALSE, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPprofileDeleteCore(), SCIPprofileGetNTimepoints(), SCIPprofileGetTime(), SCIPprofileInsertCore(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propagateCumulativeCondition(), and propagateTTEF().
◆ createNodedata()
|
static |
creates a node data structure
- Parameters
-
scip SCIP data structure nodedata pointer to store the create node data
Definition at line 5681 of file cons_cumulative.c.
References freeNodedata(), NULL, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIPallocBuffer, and TRUE.
Referenced by checkOverloadViaThetaTree(), and insertThetanode().
◆ freeNodedata()
|
static |
frees a node data structure
- Parameters
-
scip SCIP data structure nodedata pointer to store node data which should be freed
Definition at line 5705 of file cons_cumulative.c.
References nodedata, NULL, SCIPfreeBuffer, and updateEnvelope().
Referenced by checkOverloadViaThetaTree(), and createNodedata().
◆ updateEnvelope()
|
static |
update node data structure starting from the given node along the path to the root node
- Parameters
-
scip SCIP data structure node search node which inserted
Definition at line 5718 of file cons_cumulative.c.
References MAX, nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPdebugMsg, and updateKeyOnTrace().
Referenced by deleteLambdaLeaf(), freeNodedata(), insertThetanode(), and moveNodeToLambda().
◆ updateKeyOnTrace()
|
static |
updates the key of the first parent on the trace which comes from left
- Parameters
-
node node to start the trace key update search key
Definition at line 5806 of file cons_cumulative.c.
References deleteLambdaLeaf(), nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetParent(), SCIPbtnodeIsLeftchild(), and SCIPbtnodeIsRoot().
Referenced by deleteLambdaLeaf(), and updateEnvelope().
◆ deleteLambdaLeaf()
|
static |
deletes the given node and updates all envelops
- Parameters
-
scip SCIP data structure tree binary tree node node to be deleted
Definition at line 5838 of file cons_cumulative.c.
References moveNodeToLambda(), nodedata, NULL, SCIP_OKAY, SCIPbtnodeFree(), SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPbtnodeIsLeftchild(), SCIPbtnodeIsRightchild(), SCIPbtnodeIsRoot(), SCIPbtnodeSetLeftchild(), SCIPbtnodeSetParent(), SCIPbtnodeSetRightchild(), SCIPbtSetRoot(), SCIPdebugMsg, updateEnvelope(), and updateKeyOnTrace().
Referenced by inferboundsEdgeFinding(), and updateKeyOnTrace().
◆ moveNodeToLambda()
|
static |
moves a node form the theta set into the lambda set and updates the envelops
- Parameters
-
scip SCIP data structure tree binary tree node node to move into the lambda set
Definition at line 5911 of file cons_cumulative.c.
References FALSE, insertThetanode(), nodedata, NULL, SCIP_OKAY, SCIPbtnodeGetData(), and updateEnvelope().
Referenced by deleteLambdaLeaf(), and inferboundsEdgeFinding().
◆ insertThetanode()
|
static |
inserts a node into the theta set and update the envelops
- Parameters
-
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 5947 of file cons_cumulative.c.
References createNodedata(), findResponsibleLambdaLeafTraceEnergy(), nodedata, NULL, SCIP_CALL, SCIP_OKAY, SCIPbtGetRoot(), SCIPbtIsEmpty(), SCIPbtnodeCreate(), SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPbtnodeSetLeftchild(), SCIPbtnodeSetParent(), SCIPbtnodeSetRightchild(), SCIPbtSetRoot(), and updateEnvelope().
Referenced by checkOverloadViaThetaTree(), and moveNodeToLambda().
◆ findResponsibleLambdaLeafTraceEnergy()
|
static |
returns the leaf responsible for the lambda energy
- Parameters
-
node node which defines the subtree beases on the lambda energy
Definition at line 6051 of file cons_cumulative.c.
References findResponsibleLambdaLeafTraceEnvelop(), nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), and SCIPbtnodeIsLeaf().
Referenced by findResponsibleLambdaLeafTraceEnvelop(), and insertThetanode().
◆ findResponsibleLambdaLeafTraceEnvelop()
|
static |
returns the leaf responsible for the lambda envelop
- Parameters
-
node node which defines the subtree beases on the lambda envelop
Definition at line 6100 of file cons_cumulative.c.
References collectThetaSubtree(), findResponsibleLambdaLeafTraceEnergy(), nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), and SCIPbtnodeIsLeaf().
Referenced by findResponsibleLambdaLeafTraceEnergy(), and inferboundsEdgeFinding().
◆ collectThetaSubtree()
|
static |
reports all elements from set theta to generate a conflicting set
- Parameters
-
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 6153 of file cons_cumulative.c.
References MAX, nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPdebugMessage, SCIPvarGetName(), and traceThetaEnvelop().
Referenced by findResponsibleLambdaLeafTraceEnvelop(), traceLambdaEnergy(), traceLambdaEnvelop(), and traceThetaEnvelop().
◆ traceThetaEnvelop()
|
static |
collect the jobs (omega set) which are contribute to theta envelop from the theta set
- Parameters
-
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 6188 of file cons_cumulative.c.
References collectThetaSubtree(), nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), and traceLambdaEnergy().
Referenced by collectThetaSubtree(), and traceLambdaEnvelop().
◆ traceLambdaEnergy()
|
static |
collect the jobs (omega set) which are contribute to lambda envelop from the theta set
- Parameters
-
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 6248 of file cons_cumulative.c.
References collectThetaSubtree(), nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), and traceLambdaEnvelop().
Referenced by traceLambdaEnvelop(), and traceThetaEnvelop().
◆ traceLambdaEnvelop()
|
static |
collect the jobs (omega set) which are contribute to lambda envelop from the theta set
- Parameters
-
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 6305 of file cons_cumulative.c.
References collectThetaSubtree(), computeEnergyContribution(), nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), traceLambdaEnergy(), and traceThetaEnvelop().
Referenced by inferboundsEdgeFinding(), and traceLambdaEnergy().
◆ computeEnergyContribution()
|
static |
compute the energy contribution by job which corresponds to the given leaf
- Parameters
-
node leaf
Definition at line 6371 of file cons_cumulative.c.
References nodedata, NULL, SCIP_DECL_SORTPTRCOMP(), SCIPbtnodeGetData(), SCIPdebugMessage, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().
Referenced by analyzeConflictOverload(), and traceLambdaEnvelop().
◆ SCIP_DECL_SORTPTRCOMP() [1/2]
|
static |
comparison method for two node data w.r.t. the earliest start time
Definition at line 6395 of file cons_cumulative.c.
References SCIPbtnodeGetData().
Referenced by computeEnergyContribution().
◆ SCIP_DECL_SORTPTRCOMP() [2/2]
|
static |
comparison method for two node data w.r.t. the latest completion time
Definition at line 6408 of file cons_cumulative.c.
References analyzeConflictOverload().
◆ analyzeConflictOverload()
|
static |
an overload was detected; initialized conflict analysis, add an initial reason
- Note
- the conflict analysis is not performend, only the initialized SCIP_Bool pointer is set to TRUE
- Parameters
-
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 6425 of file cons_cumulative.c.
References computeEnergyContribution(), computeEstOmegaset(), FALSE, nodedata, NULL, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictUb(), SCIPbtnodeGetData(), SCIPdebugMsg, SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPsortDownPtr(), SCIPswapInts(), and TRUE.
Referenced by checkOverloadViaThetaTree(), inferboundsEdgeFinding(), and SCIP_DECL_SORTPTRCOMP().
◆ computeEstOmegaset()
|
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
- Parameters
-
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 6535 of file cons_cumulative.c.
References inferboundsEdgeFinding(), NULL, SCIP_Longint, SCIP_Real, and SCIPfeasCeil().
Referenced by analyzeConflictOverload(), and inferboundsEdgeFinding().
◆ inferboundsEdgeFinding()
|
static |
propagates start time using an edge finding algorithm which is based on binary trees (theta lambda trees)
- Note
- The algorithm is based on the paper: Petr Vilim, "Edge Finding Filtering Algorithm for Discrete Cumulative Resources in O(kn log n)". *I.P. Gent (Ed.): CP 2009, LNCS 5732, pp. 802-816, 2009.
- Parameters
-
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 6569 of file cons_cumulative.c.
References analyzeConflictOverload(), checkOverloadViaThetaTree(), computeEstOmegaset(), CONSHDLR_NAME, deleteLambdaLeaf(), FALSE, findResponsibleLambdaLeafTraceEnvelop(), getInferInfo(), inferInfoToInt(), moveNodeToLambda(), nodedata, NULL, PROPRULE_2_EDGEFINDING, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_Longint, 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().
◆ checkOverloadViaThetaTree()
|
static |
checks whether the instance is infeasible due to a overload within a certain time frame using the idea of theta trees
- Note
- The algorithm is based on the paper: Petr Vilim, "Max Energy Filtering Algorithm for Discrete Cumulative Resources". In: Willem Jan van Hoeve and John N. Hooker (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2009), LNCS 5547, pp 294–308
- Parameters
-
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 6777 of file cons_cumulative.c.
References analyzeConflictOverload(), CONSHDLR_NAME, createNodedata(), FALSE, freeNodedata(), inferboundsEdgeFinding(), insertThetanode(), MAX, nodedata, NULL, propagateEdgeFinding(), SCIP_CALL, SCIP_Longint, 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().
◆ propagateEdgeFinding()
|
static |
checks whether the instance is infeasible due to a overload within a certain time frame using the idea of theta trees
- Note
- The algorithm is based on the paper: Petr Vilim, "Max Energy Filtering Algorithm for Discrete Cumulative Resources". In: Willem Jan van Hoeve and John N. Hooker (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2009), LNCS 5547, pp 294–308
- Parameters
-
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 7080 of file cons_cumulative.c.
References checkOverloadViaThetaTree(), consCheckRedundancy(), FALSE, SCIP_CALL, SCIP_OKAY, and TRUE.
Referenced by checkOverloadViaThetaTree(), and propagateCumulativeCondition().
◆ consCheckRedundancy()
|
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
- Parameters
-
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 7129 of file cons_cumulative.c.
References createCoreProfile(), FALSE, MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPfreeBufferArray, SCIPsortIntInt(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propagateCumulativeCondition(), and propagateEdgeFinding().
◆ createCoreProfile()
|
static |
creates the worst case resource profile, that is, all jobs are inserted with the earliest start and latest completion time
- Parameters
-
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 7251 of file cons_cumulative.c.
References analyseInfeasibelCoreInsertion(), CONSHDLR_NAME, MAX, NULL, 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().
◆ propagateCumulativeCondition()
|
static |
propagate the cumulative condition
- Parameters
-
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 7342 of file cons_cumulative.c.
References consCheckRedundancy(), createCoreProfile(), NULL, 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().
◆ propagateCons()
|
static |
propagate the cumulative constraint
- Parameters
-
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 7414 of file cons_cumulative.c.
References applyProbingVar(), FALSE, NULL, 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().
◆ applyProbingVar()
|
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
- Parameters
-
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 7495 of file cons_cumulative.c.
References FALSE, NULL, 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().
◆ varMayRoundDown()
|
static |
is it possible, to round variable down w.r.t. objective function
- Parameters
-
scip SCIP data structure var problem variable roundable pointer to store if the variable can be rounded down
Definition at line 7593 of file cons_cumulative.c.
References FALSE, getActiveVar(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIPisNegative(), SCIPisPositive(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarIsActive(), TRUE, and varMayRoundUp().
Referenced by applyAlternativeBoundsFixing(), applyProbingVar(), fixIntegerVariableLb(), and presolveConsEst().
◆ varMayRoundUp()
|
static |
is it possible, to round variable up w.r.t. objective function
- Parameters
-
scip SCIP data structure var problem variable roundable pointer to store if the variable can be rounded down
Definition at line 7642 of file cons_cumulative.c.
References computeAlternativeBounds(), FALSE, getActiveVar(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIPisNegative(), SCIPisPositive(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarIsActive(), and TRUE.
Referenced by applyAlternativeBoundsFixing(), fixIntegerVariableUb(), presolveConsLct(), and varMayRoundDown().
◆ computeAlternativeBounds()
|
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.
- Parameters
-
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 7695 of file cons_cumulative.c.
References applyAlternativeBoundsFixing(), SCIP_Profile::capacity, getActiveVar(), NULL, 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().
◆ applyAlternativeBoundsFixing()
|
static |
apply all fixings which are given by the alternative bounds
- Parameters
-
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 7829 of file cons_cumulative.c.
References applyProbingVar(), CONSHDLR_NAME, NULL, propagateAllConss(), SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPfindConshdlr(), SCIPfixVar(), SCIPfreeBufferArray, SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetUbLocal(), varMayRoundDown(), and varMayRoundUp().
Referenced by computeAlternativeBounds(), and propagateAllConss().
◆ propagateAllConss()
|
static |
propagate all constraints together
- Parameters
-
scip SCIP data structure 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 7985 of file cons_cumulative.c.
References applyAlternativeBoundsBranching(), applyAlternativeBoundsFixing(), computeAlternativeBounds(), createCoverCutsTimepoint(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetVars(), SCIPinProbing(), and SCIPinRepropagation().
Referenced by applyAlternativeBoundsFixing(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().
◆ createCoverCutsTimepoint()
|
static |
creates covering cuts for jobs violating resource constraints
- Parameters
-
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 8056 of file cons_cumulative.c.
References b, createCoverCuts(), NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconvertRealToInt(), SCIPcreateEmptyRowCons(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetBinvarsLinking(), SCIPgetValsLinking(), SCIPinfinity(), SCIPreallocBlockMemoryArray, SCIPsnprintf(), SCIPsortIntInt(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by createCoverCuts(), and propagateAllConss().
◆ createCoverCuts()
|
static |
method to construct cover cuts for all points in time
- Parameters
-
scip SCIP data structure cons constraint to be separated
Definition at line 8311 of file cons_cumulative.c.
References createCapacityRestriction(), createCoverCutsTimepoint(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPsortIntInt(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by createCoverCutsTimepoint(), and separateCoverCutsCons().
◆ createCapacityRestriction()
|
static |
this method creates a row for time point curtime which insures the capacity restriction of the cumulative constraint
- Parameters
-
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 8450 of file cons_cumulative.c.
References b, collectBinaryVars(), consCapacityConstraintsFinder(), FALSE, NULL, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCoefKnapsack(), SCIPaddCons(), SCIPaddVarToRow(), SCIPallocBlockMemoryArray, SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsRemovable(), SCIPcreateConsKnapsack(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPflushRowExtensions(), SCIPfreeBufferArrayNull, SCIPinfinity(), SCIPprintRow(), SCIPreallocBlockMemoryArray, SCIPreleaseCons(), SCIPsnprintf(), and TRUE.
Referenced by consCapacityConstraintsFinder(), and createCoverCuts().
◆ consCapacityConstraintsFinder()
|
static |
this method checks how many cumulatives can run at most at one time if this is greater than the capacity it creates row
- Parameters
-
scip SCIP data structure cons constraint to be checked cutsasconss should the cumulative constraint create the cuts as constraints?
Definition at line 8540 of file cons_cumulative.c.
References addEndingJobDemands(), createCapacityRestriction(), createRelaxation(), createSortedEventpoints(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPfreeBufferArray, and subtractStartingJobDemands().
Referenced by createCapacityRestriction(), and createRelaxation().
◆ 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
- Parameters
-
scip SCIP data structure cons cumulative constraint cutsasconss should the cumulative constraint create the cuts as constraints?
Definition at line 8671 of file cons_cumulative.c.
References addRelaxation(), consCapacityConstraintsFinder(), consdataCollectLinkingCons(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsSeparated(), SCIPsetConsEnforced(), SCIPsetConsInitial(), and SCIPsetConsSeparated().
Referenced by addRelaxation(), consCapacityConstraintsFinder(), and separateConsBinaryRepresentation().
◆ addRelaxation()
|
static |
adds linear relaxation of cumulative constraint to the LP
- Parameters
-
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 8714 of file cons_cumulative.c.
References createRelaxation(), FALSE, NULL, r, SCIP_CALL, SCIP_OKAY, SCIPaddRow(), SCIPconsGetData(), SCIProwIsInLP(), and separateConsBinaryRepresentation().
Referenced by createRelaxation(), and SCIP_DECL_CONSINITLP().
◆ separateConsBinaryRepresentation()
|
static |
checks constraint for violation, and adds it as a cut if possible
- Parameters
-
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 8750 of file cons_cumulative.c.
References createRelaxation(), FALSE, NULL, r, 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().
◆ separateCoverCutsCons()
|
static |
checks constraint for violation, and adds it as a cut if possible
- Parameters
-
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 8826 of file cons_cumulative.c.
References consdataCollectLinkingCons(), createCapacityRestrictionIntvars(), createCoverCuts(), FALSE, NULL, r, 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().
◆ createCapacityRestrictionIntvars()
|
static |
this method creates a row for time point curtime which ensures the capacity restriction of the cumulative constraint
- Parameters
-
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? cutoff pointer to store TRUE, if a cutoff was detected
Definition at line 8945 of file cons_cumulative.c.
References collectIntVars(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsIsRemovable(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPflushRowExtensions(), SCIPfreeBufferArrayNull, SCIPinfinity(), SCIPprintRow(), SCIPreleaseRow(), SCIPsnprintf(), separateConsOnIntegerVariables(), and TRUE.
Referenced by separateConsOnIntegerVariables(), and separateCoverCutsCons().
◆ separateConsOnIntegerVariables()
|
static |
checks constraint for violation, and adds it as a cut if possible
- Parameters
-
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 cutoff pointer to store TRUE, if a cutoff was detected
Definition at line 9011 of file cons_cumulative.c.
References addEndingJobDemands(), checkDemands(), createCapacityRestrictionIntvars(), createSelectedSortedEventpointsSol(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPfreeBufferArray, subtractStartingJobDemands(), and TRUE.
Referenced by createCapacityRestrictionIntvars(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().
◆ checkDemands()
returns TRUE if all demands are smaller than the capacity of the cumulative constraint and if the total demand is correct
- Parameters
-
scip SCIP data structure cons constraint to be checked
Definition at line 9119 of file cons_cumulative.c.
References deleteTrivilCons(), FALSE, NULL, SCIPconsGetData(), and TRUE.
Referenced by presolveCons(), SCIP_DECL_CONSPRESOL(), and separateConsOnIntegerVariables().
◆ deleteTrivilCons()
|
static |
delete constraint if it consists of at most one job
- Parameters
-
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 9160 of file cons_cumulative.c.
References NULL, removeIrrelevantJobs(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPdelCons(), and TRUE.
Referenced by checkDemands(), and presolveCons().
◆ removeIrrelevantJobs()
|
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
- Parameters
-
scip SCIP data structure cons constraint to propagate
Definition at line 9202 of file cons_cumulative.c.
References adjustOversizedJobBounds(), consdataDeletePos(), CONSHDLR_NAME, NULL, 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().
◆ adjustOversizedJobBounds()
|
static |
adjust bounds of over sizeed job (the demand is larger than the capacity)
- Parameters
-
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 9266 of file cons_cumulative.c.
References FALSE, NULL, 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().
◆ removeOversizedJobs()
|
static |
try to removed over sizeed jobs (the demand is larger than the capacity)
- Parameters
-
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 9372 of file cons_cumulative.c.
References adjustOversizedJobBounds(), consdataDeletePos(), fixIntegerVariableUb(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), and SCIPdebugMsg.
Referenced by adjustOversizedJobBounds(), and presolveCons().
◆ fixIntegerVariableUb()
|
static |
fix integer variable to upper bound if the rounding locks and the object coefficient are in favor of that
- Parameters
-
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 9413 of file cons_cumulative.c.
References FALSE, fixIntegerVariableLb(), SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPdebugMsg, SCIPfixVar(), SCIPinProbing(), SCIPinRepropagation(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNLocksUpType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and varMayRoundUp().
Referenced by presolveConsLct(), and removeOversizedJobs().
◆ fixIntegerVariableLb()
|
static |
fix integer variable to lower bound if the rounding locks and the object coefficient are in favor of that
- Parameters
-
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 9465 of file cons_cumulative.c.
References FALSE, normalizeCumulativeCondition(), SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPdebugMsg, SCIPfixVar(), SCIPinProbing(), SCIPinRepropagation(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDownType(), TRUE, and varMayRoundDown().
Referenced by fixIntegerVariableUb(), and presolveConsEst().
◆ normalizeCumulativeCondition()
|
static |
normalize cumulative condition
- Parameters
-
scip SCIP data structure nvars number of start time variables (activities) 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 9512 of file cons_cumulative.c.
References MAX, normalizeDemands(), SCIP_Longint, SCIPcalcGreComDiv(), and SCIPdebugMsg.
Referenced by fixIntegerVariableLb(), normalizeDemands(), and SCIPnormalizeCumulativeCondition().
◆ normalizeDemands()
|
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
- Parameters
-
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 9583 of file cons_cumulative.c.
References computeEffectiveHorizonCumulativeCondition(), FALSE, normalizeCumulativeCondition(), NULL, SCIPconsGetData(), SCIPconsIsModifiable(), and TRUE.
Referenced by normalizeCumulativeCondition(), and presolveCons().
◆ computeEffectiveHorizonCumulativeCondition()
|
static |
computes for the given cumulative condition the effective horizon
- Parameters
-
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 9617 of file cons_cumulative.c.
References createConsCumulative(), NULL, 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().
◆ createConsCumulative()
|
static |
creates and adds a cumulative constraint
- Parameters
-
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 9697 of file cons_cumulative.c.
References computeEffectiveHorizon(), SCIP_CALL, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsCumulative(), SCIPreleaseCons(), SCIPsetHmaxCumulative(), and SCIPsetHminCumulative().
Referenced by computeEffectiveHorizon(), computeEffectiveHorizonCumulativeCondition(), and createDisjuctiveCons().
◆ computeEffectiveHorizon()
|
static |
computes the effective horizon and checks if the constraint can be decompsed
- Parameters
-
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 9751 of file cons_cumulative.c.
References computeEffectiveHorizonCumulativeCondition(), CONSHDLR_NAME, createConsCumulative(), NULL, 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().
◆ presolveConsEst()
|
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.
- Note
- That method does not remove any variable form the arrays. It only marks the variables which are irrelevant for the cumulative condition; The deletion has to be done later.
- Parameters
-
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 9855 of file cons_cumulative.c.
References applyProbingVar(), CONSHDLR_NAME, FALSE, fixIntegerVariableLb(), MAX, NULL, presolveConsLct(), SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfixVar(), SCIPfreeBufferArray, SCIPstatistic, SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDownType(), SCIPvarGetUbGlobal(), TRUE, and varMayRoundDown().
Referenced by computeEffectiveHorizon(), presolveConsEffectiveHorizon(), and SCIPpresolveCumulativeCondition().
◆ presolveConsLct()
|
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).
- Note
- That method does not remove any variable form the arrays. It only marks the variables which are irrelevant for the cumulative condition; The deletion has to be done later.
- Parameters
-
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 10140 of file cons_cumulative.c.
References applyProbingVar(), CONSHDLR_NAME, FALSE, fixIntegerVariableUb(), MAX, NULL, presolveConsEffectiveHorizon(), SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfixVar(), SCIPfreeBufferArray, SCIPstatistic, SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNLocksUpType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and varMayRoundUp().
Referenced by presolveConsEffectiveHorizon(), presolveConsEst(), and SCIPpresolveCumulativeCondition().
◆ presolveConsEffectiveHorizon()
|
static |
presolve cumulative constraint w.r.t. the boundary of the effective horizon
- Parameters
-
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 10392 of file cons_cumulative.c.
References BMSclearMemoryArray, collectDemands(), consdataDeletePos(), FALSE, NULL, presolveConsEst(), presolveConsLct(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconvertRealToInt(), SCIPfreeBufferArray, SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by presolveCons(), and presolveConsLct().
◆ collectDemands()
|
static |
stores all demands which are smaller than the capacity of those jobs that are running at 'curtime'
- Parameters
-
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 10473 of file cons_cumulative.c.
References getHighestCapacityUsage(), NULL, SCIPconvertRealToInt(), and SCIPvarGetUbGlobal().
Referenced by getHighestCapacityUsage(), and presolveConsEffectiveHorizon().
◆ getHighestCapacityUsage()
|
static |
this method creates a row for time point curtime which insures the capacity restriction of the cumulative constraint
- Parameters
-
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 10530 of file cons_cumulative.c.
References collectDemands(), NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconvertRealToInt(), SCIPfreeBufferArray, SCIPisFeasIntegral(), SCIPsolveKnapsackExactly(), and tightenCapacity().
Referenced by collectDemands(), and tightenCapacity().
◆ 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
- Parameters
-
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 10591 of file cons_cumulative.c.
References addEndingJobDemands(), createSortedEventpoints(), FALSE, getHighestCapacityUsage(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPdebug, SCIPdebugMsg, SCIPfreeBufferArray, subtractStartingJobDemands(), and tightenCoefs().
Referenced by getHighestCapacityUsage(), and presolveCons().
◆ tightenCoefs()
|
static |
tries to change coefficients: demand_j < cap && all other parallel jobs in conflict ==> set demand_j := cap
- Parameters
-
scip SCIP data structure cons cumulative constraint nchgcoefs pointer to count total number of changed coefficients
Definition at line 10733 of file cons_cumulative.c.
References createDisjuctiveCons(), FALSE, NULL, 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().
◆ createDisjuctiveCons()
|
static |
creare a disjunctive constraint which contains all jobs which cannot run in parallel
- Parameters
-
scip SCIP data structure cons cumulative constraint naddconss pointer to store the number of added constraints
Definition at line 10935 of file cons_cumulative.c.
References createConsCumulative(), FALSE, NULL, presolveCons(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPfreeBufferArray, and TRUE.
Referenced by SCIP_DECL_CONSPRESOL(), and tightenCoefs().
◆ presolveCons()
|
static |
presolve given constraint
- Parameters
-
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 11018 of file cons_cumulative.c.
References checkDemands(), computeEffectiveHorizon(), deleteTrivilCons(), nnodes, normalizeDemands(), presolveConsEffectiveHorizon(), removeOversizedJobs(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIPallowStrongDualReds(), SCIPconsIsDeleted(), solveIndependentCons(), TCLIQUE_GETNNODES(), tightenCapacity(), and tightenCoefs().
Referenced by createDisjuctiveCons(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().
◆ TCLIQUE_GETNNODES()
|
static |
gets number of nodes in the graph
Definition at line 11123 of file cons_cumulative.c.
References NULL, and TCLIQUE_GETWEIGHTS().
Referenced by presolveCons().
◆ TCLIQUE_GETWEIGHTS()
|
static |
gets weight of nodes in the graph
Definition at line 11132 of file cons_cumulative.c.
References NULL, and TCLIQUE_ISEDGE().
Referenced by TCLIQUE_GETNNODES().
◆ TCLIQUE_ISEDGE()
|
static |
returns, whether the edge (node1, node2) is in the graph
Definition at line 11141 of file cons_cumulative.c.
References FALSE, nnodes, NULL, TCLIQUE_SELECTADJNODES(), and TRUE.
Referenced by TCLIQUE_GETWEIGHTS().
◆ TCLIQUE_SELECTADJNODES()
|
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 11162 of file cons_cumulative.c.
References nnodes, NULL, and TCLIQUE_NEWSOL().
Referenced by TCLIQUE_ISEDGE().
◆ TCLIQUE_NEWSOL()
|
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 11196 of file cons_cumulative.c.
References impliesVlbPrecedenceCondition(), nnodes, NULL, SCIP_Bool, SCIPdebugMessage, and SCIPinfoMessage().
Referenced by TCLIQUE_SELECTADJNODES().
◆ impliesVlbPrecedenceCondition()
|
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
- Parameters
-
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 11234 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().
◆ impliesVubPrecedenceCondition()
|
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
- Parameters
-
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 11289 of file cons_cumulative.c.
References getNodeIdx(), impliesVlbPrecedenceCondition(), and SCIP_Real.
Referenced by impliesVlbPrecedenceCondition(), and projectVbd().
◆ getNodeIdx()
|
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
- Parameters
-
scip SCIP data structure tcliquegraph incompatibility graph var variable for which we want the index idx pointer to store the index
Definition at line 11311 of file cons_cumulative.c.
References BMSclearMemoryArray, projectVbd(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPreallocBufferArray, and SCIPvarGetProbindex().
Referenced by constraintNonOverlappingGraph(), impliesVubPrecedenceCondition(), initializeDurations(), and projectVbd().
◆ 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)
- Parameters
-
scip SCIP data structure tcliquegraph incompatibility graph
Definition at line 11402 of file cons_cumulative.c.
References b, getNodeIdx(), impliesVlbPrecedenceCondition(), impliesVubPrecedenceCondition(), NULL, 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().
◆ transitiveClosure()
|
static |
compute the transitive closer of the given graph and the number of in and out arcs
- Parameters
-
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 11497 of file cons_cumulative.c.
References constraintNonOverlappingGraph(), nnodes, and TRUE.
Referenced by constructIncompatibilityGraph(), and projectVbd().
◆ constraintNonOverlappingGraph()
|
static |
constructs a non-overlapping graph w.r.t. given durations and available cumulative constraints
- Parameters
-
scip SCIP data structure tcliquegraph incompatibility graph conss array of cumulative constraints nconss number of cumulative constraints
Definition at line 11529 of file cons_cumulative.c.
References constructIncompatibilityGraph(), getNodeIdx(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by constructIncompatibilityGraph(), and transitiveClosure().
◆ constructIncompatibilityGraph()
|
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
- Parameters
-
scip SCIP data structure tcliquegraph incompatibility graph conss array of cumulative constraints nconss number of cumulative constraints
Definition at line 11624 of file cons_cumulative.c.
References constraintNonOverlappingGraph(), createCumulativeCons(), NULL, projectVbd(), SCIP_CALL, SCIP_OKAY, and transitiveClosure().
Referenced by constraintNonOverlappingGraph(), and detectRedundantConss().
◆ createCumulativeCons()
|
static |
create cumulative constraint from conflict set
- Parameters
-
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 11648 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().
◆ findCumulativeConss()
|
static |
search for cumulative constrainst
- Parameters
-
scip SCIP data structure tcliquegraph conflict set graph naddconss pointer to store the number of added constraints
Definition at line 11694 of file cons_cumulative.c.
References CONSHDLR_NAME, createCumulativeCons(), createPrecedenceCons(), FALSE, nnodes, NULL, 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().
◆ createPrecedenceCons()
|
static |
create precedence constraint (as variable bound constraint
- Parameters
-
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 11822 of file cons_cumulative.c.
References computeMinDistance(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPcreateConsVarbound(), SCIPdebugPrintCons, SCIPinfinity(), SCIPreleaseCons(), and TRUE.
Referenced by computeMinDistance(), findCumulativeConss(), and strengthenVarbounds().
◆ computeMinDistance()
|
static |
compute a minimum distance between the start times of the two given jobs and post it as variable bound constraint
- Parameters
-
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 11847 of file cons_cumulative.c.
References BMSclearMemoryArray, createPrecedenceCons(), findPrecedenceConss(), nnodes, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPfreeBufferArray, SCIPgetNRuns(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and tcliqueMaxClique().
Referenced by createPrecedenceCons(), and findPrecedenceConss().
◆ 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
- Parameters
-
scip SCIP data structure tcliquegraph conflict set graph naddconss pointer to store the number of added constraints
Definition at line 11948 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().
◆ initializeDurations()
|
static |
initialize the assumed durations for each variable
- Parameters
-
scip SCIP data structure tcliquegraph the incompatibility graph conss cumulative constraints nconss number of cumulative constraints
Definition at line 12016 of file cons_cumulative.c.
References createTcliqueGraph(), getNodeIdx(), MAX, NULL, SCIP_CALL, SCIP_OKAY, and SCIPconsGetData().
Referenced by detectRedundantConss(), and findPrecedenceConss().
◆ createTcliqueGraph()
|
static |
create tclique graph
- Parameters
-
scip SCIP data structure tcliquegraph reference to the incompatibility graph
Definition at line 12060 of file cons_cumulative.c.
References BMSclearMemoryArray, freeTcliqueGraph(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPblkmem(), SCIPduplicateBufferArray, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapInsertInt(), and SCIPvarGetProbindex().
Referenced by detectRedundantConss(), and initializeDurations().
◆ freeTcliqueGraph()
|
static |
frees the tclique graph
- Parameters
-
scip SCIP data structure tcliquegraph reference to the incompatibility graph
Definition at line 12141 of file cons_cumulative.c.
References detectRedundantConss(), SCIPfreeBuffer, SCIPfreeBufferArray, and SCIPhashmapFree().
Referenced by createTcliqueGraph(), and detectRedundantConss().
◆ detectRedundantConss()
|
static |
construct an incompatibility graph and search for precedence constraints (variables bounds) and unary cumulative constrains (disjunctive constraint)
- Parameters
-
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 12170 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().
◆ consdataCalcSignature()
|
static |
compute the constraint signature which is used to detect constraints which contain potentially the same set of variables
- Parameters
-
consdata cumulative constraint data
Definition at line 12209 of file cons_cumulative.c.
References SCIP_DECL_SORTINDCOMP(), SCIPvarGetIndex(), and TRUE.
Referenced by detectRedundantConss(), and removeRedundantConss().
◆ SCIP_DECL_SORTINDCOMP()
|
static |
index comparison method of linear constraints: compares two indices of the variable set in the linear constraint
Definition at line 12233 of file cons_cumulative.c.
References NULL, removeRedundantConss(), and SCIPvarCompare().
Referenced by consdataCalcSignature().
◆ removeRedundantConss()
|
static |
run a pairwise comparison
- Parameters
-
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 12246 of file cons_cumulative.c.
References consdataCalcSignature(), initializeLocks(), NULL, 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().
◆ strengthenVarbounds()
|
static |
strengthen the variable bounds using the cumulative condition
- Parameters
-
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 12387 of file cons_cumulative.c.
References b, createPrecedenceCons(), enforceConstraint(), NULL, 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().
◆ enforceConstraint()
|
static |
helper function to enforce constraints
- Parameters
-
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 12483 of file cons_cumulative.c.
References checkCons(), CONSHDLR_NAME, enforceSolution(), FALSE, NULL, 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().
◆ SCIP_DECL_CONSHDLRCOPY()
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 12587 of file cons_cumulative.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfindConshdlr(), SCIPincludeConshdlrCumulative(), SCIPstatistic, and TRUE.
Referenced by enforceConstraint().
◆ SCIP_DECL_CONSFREE()
|
static |
destructor of constraint handler to free constraint handler data (called when SCIP is exiting)
Definition at line 12605 of file cons_cumulative.c.
References CONSHDLR_NAME, conshdlrdataFree(), NULL, SCIP_DECL_CONSINITPRE(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconshdlrSetData(), and SCIPstatisticPrintf.
Referenced by SCIP_DECL_CONSHDLRCOPY().
◆ SCIP_DECL_CONSINITPRE()
|
static |
presolving initialization method of constraint handler (called when presolving is about to begin)
Definition at line 12638 of file cons_cumulative.c.
References FALSE, NULL, removeIrrelevantJobs(), SCIP_CALL, SCIP_DECL_CONSEXITPRE, SCIP_DECL_CONSEXITSOL(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPstatisticPrintf, and SCIPvisualizeConsCumulative().
Referenced by SCIP_DECL_CONSFREE().
◆ SCIP_DECL_CONSEXITSOL()
|
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 12700 of file cons_cumulative.c.
References consdataFreeRows(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSDELETE(), SCIP_OKAY, SCIPconsGetData(), and SCIPconshdlrGetName().
Referenced by SCIP_DECL_CONSINITPRE().
◆ SCIP_DECL_CONSDELETE()
|
static |
frees specific constraint data
Definition at line 12723 of file cons_cumulative.c.
References consdataDropAllEvents(), consdataFree(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSTRANS(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPvarIsTransformed().
Referenced by SCIP_DECL_CONSEXITSOL().
◆ SCIP_DECL_CONSTRANS()
|
static |
transforms constraint data into data belonging to the transformed problem
Definition at line 12749 of file cons_cumulative.c.
References consdataCatchEvents(), consdataCreate(), NULL, 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().
◆ SCIP_DECL_CONSINITLP()
|
static |
LP initialization method of constraint handler
Definition at line 12791 of file cons_cumulative.c.
References addRelaxation(), CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSSEPALP(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsInitial(), SCIPdebugMsg, and SCIPrestartSolve().
Referenced by SCIP_DECL_CONSTRANS().
◆ SCIP_DECL_CONSSEPALP()
|
static |
separation method of constraint handler for LP solutions
Definition at line 12828 of file cons_cumulative.c.
References CONSHDLR_NAME, FALSE, NULL, 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().
◆ SCIP_DECL_CONSSEPASOL()
|
static |
separation method of constraint handler for arbitrary primal solutions
Definition at line 12892 of file cons_cumulative.c.
References CONSHDLR_NAME, FALSE, NULL, 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().
◆ SCIP_DECL_CONSENFOLP()
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 12952 of file cons_cumulative.c.
References enforceConstraint(), NULL, SCIP_CALL, SCIP_DECL_CONSENFORELAX(), and SCIP_OKAY.
Referenced by SCIP_DECL_CONSSEPASOL().
◆ SCIP_DECL_CONSENFORELAX()
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 12961 of file cons_cumulative.c.
References enforceConstraint(), SCIP_CALL, SCIP_DECL_CONSENFOPS(), and SCIP_OKAY.
Referenced by SCIP_DECL_CONSENFOLP().
◆ SCIP_DECL_CONSENFOPS()
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 12970 of file cons_cumulative.c.
References CONSHDLR_NAME, enforceSolution(), NULL, SCIP_CALL, SCIP_DECL_CONSCHECK(), SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.
Referenced by SCIP_DECL_CONSENFORELAX().
◆ SCIP_DECL_CONSCHECK()
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 12999 of file cons_cumulative.c.
References checkCons(), CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSPROP(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconshdlrGetName(), and SCIPdebugMsg.
Referenced by SCIP_DECL_CONSENFOPS().
◆ SCIP_DECL_CONSPROP()
|
static |
domain propagation method of constraint handler
Definition at line 13027 of file cons_cumulative.c.
References CONSHDLR_NAME, FALSE, NULL, presolveCons(), propagateAllConss(), propagateCons(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSPRESOL(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PRESOLTIMING_ALWAYS, SCIP_REDUCEDDOM, SCIPallowStrongDualReds(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsDeleted(), SCIPdebugMsg, SCIPgetDepth(), and TRUE.
Referenced by SCIP_DECL_CONSCHECK().
◆ SCIP_DECL_CONSPRESOL()
|
static |
presolving method of constraint handler
Definition at line 13114 of file cons_cumulative.c.
References checkDemands(), CONSHDLR_NAME, createDisjuctiveCons(), detectRedundantConss(), FALSE, NULL, 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, SCIPallowStrongDualReds(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsDeleted(), SCIPdebugMsg, SCIPgetNRuns(), strengthenVarbounds(), and TRUE.
Referenced by SCIP_DECL_CONSPROP().
◆ SCIP_DECL_CONSRESPROP()
|
static |
propagation conflict resolving method of constraint handler
Definition at line 13235 of file cons_cumulative.c.
References CONSHDLR_NAME, inferInfoGetProprule(), intToInferInfo(), NULL, respropCumulativeCondition(), SCIP_CALL, SCIP_DECL_CONSLOCK(), SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetHmaxCumulative(), SCIPgetHminCumulative(), and SCIPvarGetName().
Referenced by SCIP_DECL_CONSPRESOL().
◆ SCIP_DECL_CONSLOCK()
|
static |
variable rounding lock method of constraint handler
Definition at line 13269 of file cons_cumulative.c.
References NULL, SCIP_CALL, SCIP_DECL_CONSPRINT(), SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPconsGetData(), SCIPconsGetName(), and SCIPdebugMsg.
Referenced by SCIP_DECL_CONSRESPROP().
◆ SCIP_DECL_CONSPRINT()
|
static |
constraint display method of constraint handler
Definition at line 13310 of file cons_cumulative.c.
References consdataPrint(), NULL, SCIP_DECL_CONSCOPY(), SCIP_OKAY, and SCIPconsGetData().
Referenced by SCIP_DECL_CONSLOCK().
◆ SCIP_DECL_CONSCOPY()
|
static |
constraint copying method of constraint handler
Definition at line 13323 of file cons_cumulative.c.
References NULL, SCIP_CALL, SCIP_DECL_CONSPARSE(), SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPcreateConsCumulative(), SCIPfreeBufferArray, SCIPgetVarCopy(), SCIPsetHmaxCumulative(), SCIPsetHminCumulative(), and TRUE.
Referenced by SCIP_DECL_CONSPRINT().
◆ SCIP_DECL_CONSPARSE()
|
static |
constraint parsing method of constraint handler
Definition at line 13389 of file cons_cumulative.c.
References NULL, 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().
◆ SCIP_DECL_CONSGETVARS()
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 13484 of file cons_cumulative.c.
References BMScopyMemoryArray, FALSE, NULL, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), and TRUE.
Referenced by SCIP_DECL_CONSPARSE().
◆ SCIP_DECL_CONSGETNVARS()
|
static |
constraint method of constraint handler which returns the number of variables (if possible)
Definition at line 13506 of file cons_cumulative.c.
References NULL, SCIP_DECL_EVENTEXEC(), SCIP_OKAY, SCIPconsGetData(), and TRUE.
Referenced by SCIP_DECL_CONSGETVARS().
◆ SCIP_DECL_EVENTEXEC()
|
static |
execution method of event handler
Definition at line 13529 of file cons_cumulative.c.
References EVENTHDLR_NAME, FALSE, NULL, SCIP_OKAY, SCIPeventhdlrGetName(), and SCIPincludeConshdlrCumulative().
Referenced by SCIP_DECL_CONSGETNVARS().