Scippy

SCIP

Solving Constraint Integer Programs

cons_cumulative.c File Reference

Detailed Description

constraint handler for cumulative constraints

Author
Timo Berthold
Stefan Heinz
Jens Schulz

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.

Macros

Constraint handler properties
#define CONSHDLR_NAME   "cumulative"
 
#define CONSHDLR_DESC   "cumulative constraint handler"
 
#define CONSHDLR_SEPAPRIORITY   2100000
 
#define CONSHDLR_ENFOPRIORITY   -2040000
 
#define CONSHDLR_CHECKPRIORITY   -3030000
 
#define CONSHDLR_SEPAFREQ   1
 
#define CONSHDLR_PROPFREQ   1
 
#define CONSHDLR_EAGERFREQ   100
 
#define CONSHDLR_MAXPREROUNDS   -1
 
#define CONSHDLR_DELAYSEPA   FALSE
 
#define CONSHDLR_DELAYPROP   FALSE
 
#define CONSHDLR_NEEDSCONS   TRUE
 
#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_ALWAYS
 
#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
 
Default parameter values
#define DEFAULT_USEBINVARS   FALSE
 
#define DEFAULT_LOCALCUTS   FALSE
 
#define DEFAULT_USECOVERCUTS   TRUE
 
#define DEFAULT_CUTSASCONSS   TRUE
 
#define DEFAULT_SEPAOLD   TRUE
 
#define DEFAULT_TTINFER   TRUE
 
#define DEFAULT_EFCHECK   FALSE
 
#define DEFAULT_EFINFER   FALSE
 
#define DEFAULT_USEADJUSTEDJOBS   FALSE
 
#define DEFAULT_TTEFCHECK   TRUE
 
#define DEFAULT_TTEFINFER   TRUE
 
#define DEFAULT_DUALPRESOLVE   TRUE
 
#define DEFAULT_COEFTIGHTENING   FALSE
 
#define DEFAULT_NORMALIZE   TRUE
 
#define DEFAULT_PRESOLPAIRWISE   TRUE
 
#define DEFAULT_DISJUNCTIVE   TRUE
 
#define DEFAULT_DETECTDISJUNCTIVE   TRUE
 
#define DEFAULT_DETECTVARBOUNDS   TRUE
 
#define DEFAULT_MAXNODES   10000LL
 
#define DEFAULT_FILLBRANCHCANDS   FALSE
 
#define DEFAULT_USEBDWIDENING   TRUE
 
Event handler properties
#define EVENTHDLR_NAME   "cumulative"
 
#define EVENTHDLR_DESC   "bound change event handler for cumulative constraints"
 

Functions

static SCIP_Bool impliesVlbPrecedenceCondition (SCIP *scip, SCIP_VAR *vlbvar, SCIP_Real vlbcoef, SCIP_Real vlbconst, int duration)
 
static SCIP_Bool impliesVubPrecedenceCondition (SCIP *scip, SCIP_VAR *var, SCIP_Real vubcoef, SCIP_Real vubconst, int duration)
 
static SCIP_RETCODE getNodeIdx (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_VAR *var, int *idx)
 
static SCIP_RETCODE projectVbd (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph)
 
static void transitiveClosure (SCIP_Bool **adjmatrix, int *ninarcs, int *noutarcs, int nnodes)
 
static SCIP_RETCODE constraintNonOverlappingGraph (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss)
 
static SCIP_RETCODE constructIncompatibilityGraph (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss)
 
static SCIP_RETCODE createCumulativeCons (SCIP *scip, const char *name, TCLIQUE_GRAPH *tcliquegraph, int *cliquenodes, int ncliquenodes)
 
static SCIP_RETCODE findCumulativeConss (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int *naddconss)
 
static SCIP_RETCODE createPrecedenceCons (SCIP *scip, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, int distance)
 
static SCIP_RETCODE computeMinDistance (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int source, int sink, int *naddconss)
 
static SCIP_RETCODE findPrecedenceConss (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int *naddconss)
 
static SCIP_RETCODE initializeDurations (SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_CONS **conss, int nconss)
 
static SCIP_RETCODE createTcliqueGraph (SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
 
static void freeTcliqueGraph (SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
 
static SCIP_RETCODE detectRedundantConss (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, int *naddconss)
 
static void consdataCalcSignature (SCIP_CONSDATA *consdata)
 
static SCIP_DECL_SORTINDCOMP (consdataCompVar)
 
static SCIP_RETCODE removeRedundantConss (SCIP *scip, SCIP_CONS **conss, int nconss, int *ndelconss)
 
static SCIP_RETCODE strengthenVarbounds (SCIP *scip, SCIP_CONS *cons, int *nchgbds, int *naddconss)
 
static SCIP_RETCODE enforceConstraint (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_Bool solinfeasible, SCIP_RESULT *result)
 
Miscellaneous Methods
static int computeCoreWithInterval (int begin, int end, int ect, int lst)
 
static SCIP_RETCODE computeImpliedEst (SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *addedvars, int *est)
 
static SCIP_RETCODE computeImpliedLct (SCIP *scip, SCIP_VAR *var, int duration, SCIP_HASHMAP *addedvars, int *lct)
 
static SCIP_RETCODE collectBinaryVars (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR ***vars, int **coefs, int *nvars, int *startindices, int curtime, int nstarted, int nfinished)
 
static SCIP_RETCODE collectIntVars (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR ***activevars, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool lower, int *lhs)
 
static void createSortedEventpoints (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *starttimes, int *endtimes, int *startindices, int *endindices, SCIP_Bool local)
 
static void createSortedEventpointsSol (SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *starttimes, int *endtimes, int *startindices, int *endindices)
 
static void createSelectedSortedEventpointsSol (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, int *starttimes, int *endtimes, int *startindices, int *endindices, int *nvars, SCIP_Bool lower)
 
static SCIP_RETCODE getActiveVar (SCIP *scip, SCIP_VAR **var, int *scalar, int *constant)
 
static int computeTotalEnergy (int *durations, int *demands, int njobs)
 
Default method to solve a cumulative condition
static SCIP_RETCODE setupAndSolveCumulativeSubscip (SCIP *subscip, SCIP_Real *objvals, int *durations, int *demands, int njobs, int capacity, int hmin, int hmax, SCIP_Longint maxnodes, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *solved, SCIP_Bool *error)
 
static SCIP_DECL_SOLVECUMULATIVE (solveCumulativeViaScipCp)
 
Constraint handler data

Method used to create and free the constraint handler data when including and removing the cumulative constraint handler.

static SCIP_RETCODE conshdlrdataCreate (SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
 
static void conshdlrdataFree (SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
 
Constraint data methods
static SCIP_RETCODE consdataCatchEvents (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
 
static SCIP_RETCODE consdataDropEvents (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
 
static SCIP_RETCODE consdataDropAllEvents (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
 
static void initializeLocks (SCIP_CONSDATA *consdata, SCIP_Bool locked)
 
static SCIP_RETCODE consdataCreate (SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR **vars, SCIP_CONS **linkingconss, int *durations, int *demands, int nvars, int capacity, int hmin, int hmax, SCIP_Bool check)
 
static SCIP_RETCODE consdataFreeRows (SCIP *scip, SCIP_CONSDATA **consdata)
 
static SCIP_RETCODE consdataFree (SCIP *scip, SCIP_CONSDATA **consdata)
 
static void consdataPrint (SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
 
static SCIP_RETCODE consdataDeletePos (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_CONS *cons, int pos)
 
static SCIP_RETCODE consdataCollectLinkingCons (SCIP *scip, SCIP_CONSDATA *consdata)
 
Check methods
static SCIP_RETCODE checkCumulativeCondition (SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *violated, SCIP_CONS *cons, SCIP_Bool printreason)
 
static SCIP_RETCODE checkCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *violated, SCIP_Bool printreason)
 
Conflict analysis
static SCIP_RETCODE resolvePropagationCoretimes (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferdemand, int inferpeak, int relaxedpeak, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool usebdwidening, int *provedpeak, SCIP_Bool *explanation)
 
static int computeOverlap (int begin, int end, int est, int lst, int duration)
 
static SCIP_RETCODE analyzeEnergyRequirement (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int begin, int end, SCIP_VAR *infervar, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool usebdwidening, SCIP_Bool *explanation)
 
static SCIP_RETCODE respropCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, INFERINFO inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool usebdwidening, SCIP_Bool *explanation, SCIP_RESULT *result)
 
Enforcement methods
static SCIP_RETCODE applyAlternativeBoundsBranching (SCIP *scip, SCIP_VAR **vars, int nvars, int *alternativelbs, int *alternativeubs, int *downlocks, int *uplocks, SCIP_Bool *branched)
 
static void subtractStartingJobDemands (SCIP_CONSDATA *consdata, int curtime, int *starttimes, int *startindices, int *freecapacity, int *idx, int nvars)
 
static void addEndingJobDemands (SCIP_CONSDATA *consdata, int curtime, int *endtimes, int *endindices, int *freecapacity, int *idx, int nvars)
 
static SCIP_RETCODE computePeak (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, int *timepoint)
 
static SCIP_RETCODE collectBranchingCands (SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, int *nbranchcands)
 
static SCIP_RETCODE enforceSolution (SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_Bool branch, SCIP_RESULT *result)
 
Linear relaxations
static SCIP_RETCODE createCoverCutsTimepoint (SCIP *scip, SCIP_CONS *cons, int *startvalues, int time)
 
static SCIP_RETCODE createCoverCuts (SCIP *scip, SCIP_CONS *cons)
 
static SCIP_RETCODE createCapacityRestriction (SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool cutsasconss)
 
static SCIP_RETCODE consCapacityConstraintsFinder (SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss)
 
static SCIP_RETCODE createRelaxation (SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss)
 
static SCIP_RETCODE addRelaxation (SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss, SCIP_Bool *infeasible)
 
static SCIP_RETCODE separateConsBinaryRepresentation (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff)
 
static SCIP_RETCODE separateCoverCutsCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff)
 
static SCIP_RETCODE createCapacityRestrictionIntvars (SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool lower)
 
static SCIP_RETCODE separateConsOnIntegerVariables (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool lower, SCIP_Bool *separated)
 
Presolving
static SCIP_Bool checkDemands (SCIP *scip, SCIP_CONS *cons)
 
static SCIP_RETCODE deleteTrivilCons (SCIP *scip, SCIP_CONS *cons, int *ndelconss, SCIP_Bool *cutoff)
 
static SCIP_RETCODE removeIrrelevantJobs (SCIP *scip, SCIP_CONS *cons)
 
static SCIP_RETCODE adjustOversizedJobBounds (SCIP *scip, SCIP_CONSDATA *consdata, int pos, int *nchgbds, int *naddconss, SCIP_Bool *cutoff)
 
static SCIP_RETCODE removeOversizedJobs (SCIP *scip, SCIP_CONS *cons, int *nchgbds, int *nchgcoefs, int *naddconss, SCIP_Bool *cutoff)
 
static SCIP_RETCODE fixIntegerVariableUb (SCIP *scip, SCIP_VAR *var, SCIP_Bool uplock, int *nfixedvars)
 
static SCIP_RETCODE fixIntegerVariableLb (SCIP *scip, SCIP_VAR *var, SCIP_Bool downlock, int *nfixedvars)
 
static SCIP_RETCODE normalizeCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int *capacity, int *nchgcoefs, int *nchgsides)
 
static SCIP_RETCODE normalizeDemands (SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides)
 
static SCIP_RETCODE computeEffectiveHorizonCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *hmin, int *hmax, int *split)
 
static SCIP_RETCODE createConsCumulative (SCIP *scip, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
static SCIP_RETCODE computeEffectiveHorizon (SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss, int *nchgsides)
 
static SCIP_RETCODE presolveConsEst (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff)
 
static SCIP_RETCODE presolveConsLct (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff)
 
static SCIP_RETCODE presolveConsEffectiveHorizon (SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *nchgcoefs, int *nchgsides, SCIP_Bool *cutoff)
 
static SCIP_RETCODE collectDemands (SCIP *scip, SCIP_CONSDATA *consdata, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Longint **demands, int *ndemands)
 
static SCIP_RETCODE getHighestCapacityUsage (SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, int *bestcapacity)
 
static SCIP_RETCODE tightenCapacity (SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides)
 
static SCIP_RETCODE tightenCoefs (SCIP *scip, SCIP_CONS *cons, int *nchgcoefs)
 
static SCIP_RETCODE createDisjuctiveCons (SCIP *scip, SCIP_CONS *cons, int *naddconss)
 
static SCIP_RETCODE presolveCons (SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PRESOLTIMING presoltiming, int *nfixedvars, int *nchgbds, int *ndelconss, int *naddconss, int *nchgcoefs, int *nchgsides, SCIP_Bool *cutoff, SCIP_Bool *unbounded)
 
TClique Graph callbacks
static TCLIQUE_GETNNODES (tcliqueGetnnodesClique)
 
static TCLIQUE_GETWEIGHTS (tcliqueGetweightsClique)
 
static TCLIQUE_ISEDGE (tcliqueIsedgeClique)
 
static TCLIQUE_SELECTADJNODES (tcliqueSelectadjnodesClique)
 
static TCLIQUE_NEWSOL (tcliqueNewsolClique)
 
Callback methods of constraint handler
static SCIP_DECL_CONSHDLRCOPY (conshdlrCopyCumulative)
 
static SCIP_DECL_CONSFREE (consFreeCumulative)
 
static SCIP_DECL_CONSINITPRE (consInitpreCumulative)
 
static SCIP_DECL_CONSEXITSOL (consExitsolCumulative)
 
static SCIP_DECL_CONSDELETE (consDeleteCumulative)
 
static SCIP_DECL_CONSTRANS (consTransCumulative)
 
static SCIP_DECL_CONSINITLP (consInitlpCumulative)
 
static SCIP_DECL_CONSSEPALP (consSepalpCumulative)
 
static SCIP_DECL_CONSSEPASOL (consSepasolCumulative)
 
static SCIP_DECL_CONSENFOLP (consEnfolpCumulative)
 
static SCIP_DECL_CONSENFORELAX (consEnforelaxCumulative)
 
static SCIP_DECL_CONSENFOPS (consEnfopsCumulative)
 
static SCIP_DECL_CONSCHECK (consCheckCumulative)
 
static SCIP_DECL_CONSPROP (consPropCumulative)
 
static SCIP_DECL_CONSPRESOL (consPresolCumulative)
 
static SCIP_DECL_CONSRESPROP (consRespropCumulative)
 
static SCIP_DECL_CONSLOCK (consLockCumulative)
 
static SCIP_DECL_CONSPRINT (consPrintCumulative)
 
static SCIP_DECL_CONSCOPY (consCopyCumulative)
 
static SCIP_DECL_CONSPARSE (consParseCumulative)
 
static SCIP_DECL_CONSGETVARS (consGetVarsCumulative)
 
static SCIP_DECL_CONSGETNVARS (consGetNVarsCumulative)
 
Callback methods of event handler
static SCIP_DECL_EVENTEXEC (eventExecCumulative)
 
Interface methods
SCIP_RETCODE SCIPincludeConshdlrCumulative (SCIP *scip)
 
SCIP_RETCODE SCIPcreateConsCumulative (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
SCIP_RETCODE SCIPcreateConsBasicCumulative (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity)
 
SCIP_RETCODE SCIPsetHminCumulative (SCIP *scip, SCIP_CONS *cons, int hmin)
 
int SCIPgetHminCumulative (SCIP *scip, SCIP_CONS *cons)
 
SCIP_RETCODE SCIPsetHmaxCumulative (SCIP *scip, SCIP_CONS *cons, int hmax)
 
int SCIPgetHmaxCumulative (SCIP *scip, SCIP_CONS *cons)
 
SCIP_VAR ** SCIPgetVarsCumulative (SCIP *scip, SCIP_CONS *cons)
 
int SCIPgetNVarsCumulative (SCIP *scip, SCIP_CONS *cons)
 
int SCIPgetCapacityCumulative (SCIP *scip, SCIP_CONS *cons)
 
int * SCIPgetDurationsCumulative (SCIP *scip, SCIP_CONS *cons)
 
int * SCIPgetDemandsCumulative (SCIP *scip, SCIP_CONS *cons)
 
SCIP_RETCODE SCIPcheckCumulativeCondition (SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *violated, SCIP_CONS *cons, SCIP_Bool printreason)
 
SCIP_RETCODE SCIPnormalizeCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int *capacity, int *nchgcoefs, int *nchgsides)
 
SCIP_RETCODE SCIPsplitCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *hmin, int *hmax, int *split)
 
SCIP_RETCODE SCIPpresolveCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff)
 
SCIP_RETCODE SCIPpropCumulativeCondition (SCIP *scip, SCIP_PRESOLTIMING presoltiming, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
 
SCIP_RETCODE SCIPrespropCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool *explanation, SCIP_RESULT *result)
 
SCIP_RETCODE SCIPvisualizeConsCumulative (SCIP *scip, SCIP_CONS *cons)
 
SCIP_RETCODE SCIPsetSolveCumulative (SCIP *scip, SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)))
 
SCIP_RETCODE SCIPsolveCumulative (SCIP *scip, int njobs, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Real *objvals, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint maxnodes, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *error)
 
SCIP_RETCODE SCIPcreateWorstCaseProfile (SCIP *scip, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands)
 
int SCIPcomputeHmin (SCIP *scip, SCIP_PROFILE *profile, int capacity)
 
int SCIPcomputeHmax (SCIP *scip, SCIP_PROFILE *profile, int capacity)
 

Inference Information Methods

An inference information can be passed with each domain reduction to SCIP. This information is passed back to the constraint handler if the corresponding bound change has to be explained. It can be used to store information which help to construct a reason/explanation for a bound change. The inference information is limited to size of integer.

In case of the cumulative constraint handler we store the used propagation algorithms for that particular bound change and the earliest start and latest completion time of all jobs in the conflict set.

enum  Proprule {
  PROPRULE_1,
  PROPRULE_2,
  PROPRULE_3,
  PROPRULE_4,
  PROPRULE_INVALID,
  PROPRULE_INVALID = 0,
  PROPRULE_1 = 1,
  PROPRULE_2 = 2,
  PROPRULE_3 = 3,
  PROPRULE_4 = 4,
  PROPRULE_1_CORETIMES = 1,
  PROPRULE_2_EDGEFINDING = 2,
  PROPRULE_3_TTEF = 3,
  PROPRULE_1_RHS = 1,
  PROPRULE_1_LHS = 2,
  PROPRULE_1_RANGEDROW = 3,
  PROPRULE_INVALID = 0,
  PROPRULE_1,
  PROPRULE_2,
  PROPRULE_3,
  PROPRULE_4,
  PROPRULE_INVALID,
  PROPRULE_1,
  PROPRULE_2,
  PROPRULE_3,
  PROPRULE_4,
  PROPRULE_0,
  PROPRULE_1,
  PROPRULE_INTLB,
  PROPRULE_INTUB,
  PROPRULE_INVALID
}
 
typedef enum Proprule PROPRULE
 
typedef struct InferInfo INFERINFO
 
static INFERINFO intToInferInfo (int i)
 
static int inferInfoToInt (INFERINFO inferinfo)
 
static PROPRULE inferInfoGetProprule (INFERINFO inferinfo)
 
static int inferInfoGetData1 (INFERINFO inferinfo)
 
static int inferInfoGetData2 (INFERINFO inferinfo)
 
static INFERINFO getInferInfo (PROPRULE proprule, int data1, int data2)
 

Propagation

typedef struct SCIP_NodeData SCIP_NODEDATA
 
static SCIP_Bool isConsIndependently (SCIP *scip, SCIP_CONS *cons)
 
static SCIP_RETCODE solveIndependentCons (SCIP *scip, SCIP_CONS *cons, SCIP_Longint maxnodes, int *nchgbds, int *nfixedvars, int *ndelconss, SCIP_Bool *cutoff, SCIP_Bool *unbounded)
 
static SCIP_RETCODE analyseInfeasibelCoreInsertion (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferduration, int inferdemand, int inferpeak, SCIP_Bool usebdwidening, SCIP_Bool *initialized, SCIP_Bool *explanation)
 
static SCIP_RETCODE coretimesUpdateLb (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, SCIP_PROFILE *profile, int idx, int *nchgbds, SCIP_Bool usebdwidening, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *infeasible)
 
static SCIP_RETCODE coretimesUpdateUb (SCIP *scip, SCIP_VAR *var, int duration, int demand, int capacity, SCIP_CONS *cons, SCIP_PROFILE *profile, int idx, int *nchgbds)
 
static SCIP_RETCODE computeCoreEngeryAfter (SCIP *scip, SCIP_PROFILE *profile, int nvars, int *ests, int *lcts, int *coreEnergyAfterEst, int *coreEnergyAfterLct)
 
static void collectDataTTEF (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int hmin, int hmax, int *permests, int *ests, int *permlcts, int *lcts, int *ects, int *lsts, int *flexenergies)
 
static SCIP_RETCODE tightenLbTTEF (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *var, int duration, int demand, int est, int ect, int lct, int begin, int end, int energy, int *bestlb, int *inferinfos, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
 
static SCIP_RETCODE tightenUbTTEF (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *var, int duration, int demand, int est, int lst, int lct, int begin, int end, int energy, int *bestub, int *inferinfos, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
 
static SCIP_RETCODE propagateUbTTEF (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, int *newlbs, int *newubs, int *lbinferinfos, int *ubinferinfos, int *lsts, int *flexenergies, int *perm, int *ests, int *lcts, int *coreEnergyAfterEst, int *coreEnergyAfterLct, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
 
static SCIP_RETCODE propagateLbTTEF (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, int *newlbs, int *newubs, int *lbinferinfos, int *ubinferinfos, int *ects, int *flexenergies, int *perm, int *ests, int *lcts, int *coreEnergyAfterEst, int *coreEnergyAfterLct, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
 
static SCIP_RETCODE propagateTTEF (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
 
static SCIP_RETCODE propagateTimetable (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
 
static SCIP_RETCODE createNodedata (SCIP *scip, SCIP_NODEDATA **nodedata)
 
static void freeNodedata (SCIP *scip, SCIP_NODEDATA **nodedata)
 
static SCIP_RETCODE updateEnvelop (SCIP *scip, SCIP_BTNODE *node)
 
static void updateKeyOnTrace (SCIP_BTNODE *node, SCIP_Real key)
 
static SCIP_RETCODE deleteLambdaLeaf (SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node)
 
static SCIP_RETCODE moveNodeToLambda (SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node)
 
static SCIP_RETCODE insertThetanode (SCIP *scip, SCIP_BT *tree, SCIP_BTNODE *node, SCIP_NODEDATA **nodedatas, int *nnodedatas)
 
static SCIP_BTNODEfindResponsibleLambdaLeafTraceEnergy (SCIP_BTNODE *node)
 
static SCIP_BTNODEfindResponsibleLambdaLeafTraceEnvelop (SCIP_BTNODE *node)
 
static void collectThetaSubtree (SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy)
 
static void traceThetaEnvelop (SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy)
 
static void traceLambdaEnergy (SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy)
 
static void traceLambdaEnvelop (SCIP_BTNODE *node, SCIP_BTNODE **omegaset, int *nelements, int *est, int *lct, int *energy)
 
static int computeEnergyContribution (SCIP_BTNODE *node)
 
static SCIP_DECL_SORTPTRCOMP (compNodeEst)
 
static SCIP_DECL_SORTPTRCOMP (compNodedataLct)
 
static SCIP_RETCODE analyzeConflictOverload (SCIP *scip, SCIP_BTNODE **leaves, int capacity, int nleaves, int est, int lct, int reportedenergy, SCIP_Bool propest, int shift, SCIP_Bool usebdwidening, SCIP_Bool *initialized, SCIP_Bool *explanation)
 
static int computeEstOmegaset (SCIP *scip, int duration, int demand, int capacity, int est, int lct, int energy)
 
static SCIP_RETCODE inferboundsEdgeFinding (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS *cons, SCIP_BT *tree, SCIP_BTNODE **leaves, int capacity, int ncands, SCIP_Bool propest, int shift, SCIP_Bool *initialized, SCIP_Bool *explanation, int *nchgbds, SCIP_Bool *cutoff)
 
static SCIP_RETCODE checkOverloadViaThetaTree (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, SCIP_Bool propest, SCIP_Bool *initialized, SCIP_Bool *explanation, int *nchgbds, SCIP_Bool *cutoff)
 
static SCIP_RETCODE propagateEdgeFinding (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, SCIP_Bool *initialized, SCIP_Bool *explanation, int *nchgbds, SCIP_Bool *cutoff)
 
static SCIP_RETCODE consCheckRedundancy (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *redundant)
 
static SCIP_RETCODE createCoreProfile (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
 
static SCIP_RETCODE propagateCumulativeCondition (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PRESOLTIMING presoltiming, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *redundant, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
 
static SCIP_RETCODE propagateCons (SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PRESOLTIMING presoltiming, int *nchgbds, int *ndelconss, SCIP_Bool *cutoff)
 
static SCIP_RETCODE applyProbingVar (SCIP *scip, SCIP_VAR **vars, int nvars, int probingpos, SCIP_Real leftub, SCIP_Real rightlb, SCIP_Real *leftimpllbs, SCIP_Real *leftimplubs, SCIP_Real *leftproplbs, SCIP_Real *leftpropubs, SCIP_Real *rightimpllbs, SCIP_Real *rightimplubs, SCIP_Real *rightproplbs, SCIP_Real *rightpropubs, int *nfixedvars, SCIP_Bool *success, SCIP_Bool *cutoff)
 
static SCIP_RETCODE varMayRoundDown (SCIP *scip, SCIP_VAR *var, SCIP_Bool *roundable)
 
static SCIP_RETCODE varMayRoundUp (SCIP *scip, SCIP_VAR *var, SCIP_Bool *roundable)
 
static SCIP_RETCODE computeAlternativeBounds (SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool local, int *alternativelbs, int *alternativeubs, int *downlocks, int *uplocks)
 
static SCIP_RETCODE applyAlternativeBoundsFixing (SCIP *scip, SCIP_VAR **vars, int nvars, int *alternativelbs, int *alternativeubs, int *downlocks, int *uplocks, int *nfixedvars, SCIP_Bool *cutoff)
 
static SCIP_RETCODE propagateAllConss (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, SCIP_Bool local, int *nfixedvars, SCIP_Bool *cutoff, SCIP_Bool *branched)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "cumulative constraint handler"

Definition at line 59 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   2100000

priority of the constraint handler for separation

Definition at line 60 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 61 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 62 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 63 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 64 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 65 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 68 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 69 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 70 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 71 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_ALWAYS

Definition at line 73 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 74 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_USEBINVARS

#define DEFAULT_USEBINVARS   FALSE

should the binary representation be used?

Definition at line 86 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_LOCALCUTS

#define DEFAULT_LOCALCUTS   FALSE

should cuts be added only locally?

Definition at line 87 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_USECOVERCUTS

#define DEFAULT_USECOVERCUTS   TRUE

should covering cuts be added?

Definition at line 88 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 89 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_SEPAOLD

#define DEFAULT_SEPAOLD   TRUE

shall old sepa algo be applied?

Definition at line 90 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 93 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 94 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 95 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 96 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 97 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 98 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_DUALPRESOLVE

#define DEFAULT_DUALPRESOLVE   TRUE

should dual presolving be applied?

Definition at line 101 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_COEFTIGHTENING

#define DEFAULT_COEFTIGHTENING   FALSE

should coeffisient tightening be applied?

Definition at line 102 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_NORMALIZE

#define DEFAULT_NORMALIZE   TRUE

should demands and capacity be normalized?

Definition at line 103 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 104 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_DISJUNCTIVE

#define DEFAULT_DISJUNCTIVE   TRUE

extract disjunctive constraints?

Definition at line 105 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 106 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 107 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 108 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_FILLBRANCHCANDS

#define DEFAULT_FILLBRANCHCANDS   FALSE

should branching candidates be added to storage?

Definition at line 111 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 114 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "cumulative"

Definition at line 123 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 124 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

Typedef Documentation

◆ PROPRULE

typedef enum Proprule PROPRULE

Definition at line 256 of file cons_cumulative.c.

◆ INFERINFO

typedef struct InferInfo INFERINFO

Definition at line 273 of file cons_cumulative.c.

◆ SCIP_NODEDATA

typedef struct SCIP_NodeData SCIP_NODEDATA

Definition at line 5681 of file cons_cumulative.c.

Enumeration Type Documentation

◆ Proprule

enum Proprule

Propagation rules

Enumerator
PROPRULE_1 

left hand side and bounds on z -> lower bound on x

PROPRULE_2 

left hand side and upper bound on x -> bound on z

PROPRULE_3 

right hand side and bounds on z -> upper bound on x

PROPRULE_4 

right hand side and lower bound on x -> bound on z

PROPRULE_INVALID 

propagation was applied without a specific propagation rule

PROPRULE_INVALID 

propagation was applied without a specific propagation rule

PROPRULE_1 

v_i = FALSE => r = FALSE

PROPRULE_2 

r = TRUE => v_i = TRUE for all i

PROPRULE_3 

v_i = TRUE for all i => r = TRUE

PROPRULE_4 

r = FALSE, v_i = TRUE for all i except j => v_j = FALSE

PROPRULE_1_CORETIMES 

core-time propagator

PROPRULE_2_EDGEFINDING 

edge-finder

PROPRULE_3_TTEF 

time-table edeg-finding

PROPRULE_1_RHS 

activity residuals of all other variables tighten bounds of single variable due to the right hand side of the inequality

PROPRULE_1_LHS 

activity residuals of all other variables tighten bounds of single variable due to the left hand side of the inequality

PROPRULE_1_RANGEDROW 

fixed variables and gcd of all left variables tighten bounds of a single variable in this reanged row

PROPRULE_INVALID 

propagation was applied without a specific propagation rule

PROPRULE_1 

v_i = TRUE => r = TRUE

PROPRULE_2 

r = FALSE => v_i = FALSE for all i

PROPRULE_3 

v_i = FALSE for all i => r = FALSE

PROPRULE_4 

r = TRUE, v_i = FALSE for all i except j => v_j = TRUE

PROPRULE_INVALID 

propagation was applied without a specific propagation rule

PROPRULE_1 

left hand side and bounds on y -> lower bound on x

PROPRULE_2 

left hand side and upper bound on x -> bound on y

PROPRULE_3 

right hand side and bounds on y -> upper bound on x

PROPRULE_4 

right hand side and lower bound on x -> bound on y

PROPRULE_0 

all variables are fixed => fix integral variable

PROPRULE_1 

all except one variable fixed => fix remaining variable

PROPRULE_INTLB 

lower bound propagation of integral variable

PROPRULE_INTUB 

upper bound propagation of integral variable

PROPRULE_INVALID 

propagation was applied without a specific propagation rule

Definition at line 250 of file cons_cumulative.c.

Function Documentation

◆ intToInferInfo()

static INFERINFO intToInferInfo ( int  i)
static

converts an integer into an inference information

Parameters
iinteger to convert

Definition at line 277 of file cons_cumulative.c.

References inferInfoToInt().

Referenced by propagateTTEF(), SCIP_DECL_CONSRESPROP(), and SCIPrespropCumulativeCondition().

◆ inferInfoToInt()

static int inferInfoToInt ( INFERINFO  inferinfo)
static

converts an inference information into an int

Parameters
inferinfoinference information to convert

Definition at line 290 of file cons_cumulative.c.

References inferInfoGetProprule().

Referenced by coretimesUpdateLb(), coretimesUpdateUb(), inferboundsEdgeFinding(), intToInferInfo(), propagateLbTTEF(), propagateUbTTEF(), tightenLbTTEF(), and tightenUbTTEF().

◆ inferInfoGetProprule()

static PROPRULE inferInfoGetProprule ( INFERINFO  inferinfo)
static

returns the propagation rule stored in the inference information

Parameters
inferinfoinference information to convert

Definition at line 299 of file cons_cumulative.c.

References inferInfoGetData1().

Referenced by inferInfoToInt(), resolvePropagationCoretimes(), respropCumulativeCondition(), and SCIP_DECL_CONSRESPROP().

◆ inferInfoGetData1()

static int inferInfoGetData1 ( INFERINFO  inferinfo)
static

returns data field one of the inference information

Parameters
inferinfoinference information to convert

Definition at line 308 of file cons_cumulative.c.

References inferInfoGetData2().

Referenced by inferInfoGetProprule(), propagateTTEF(), resolvePropagationCoretimes(), and respropCumulativeCondition().

◆ inferInfoGetData2()

static int inferInfoGetData2 ( INFERINFO  inferinfo)
static

returns data field two of the inference information

Parameters
inferinfoinference information to convert

Definition at line 317 of file cons_cumulative.c.

References getInferInfo().

Referenced by inferInfoGetData1(), propagateTTEF(), resolvePropagationCoretimes(), and respropCumulativeCondition().

◆ getInferInfo()

static INFERINFO getInferInfo ( PROPRULE  proprule,
int  data1,
int  data2 
)
static

constructs an inference information out of a propagation rule, an earliest start and a latest completion time

Parameters
proprulepropagation rule that deduced the value
data1data field one
data2data field two

Definition at line 327 of file cons_cumulative.c.

References computeCoreWithInterval().

Referenced by coretimesUpdateLb(), coretimesUpdateUb(), inferboundsEdgeFinding(), inferInfoGetData2(), propagateLbTTEF(), propagateUbTTEF(), tightenLbTTEF(), and tightenUbTTEF().

◆ computeCoreWithInterval()

static int computeCoreWithInterval ( int  begin,
int  end,
int  ect,
int  lst 
)
static

compute the core of a job which lies in certain interval [begin, end)

Parameters
beginbegin of the interval
endend of the interval
ectearliest completion time
lstlatest start time

Definition at line 362 of file cons_cumulative.c.

References computeImpliedEst(), MAX, and MIN.

Referenced by collectDataTTEF(), getInferInfo(), propagateLbTTEF(), propagateUbTTEF(), tightenLbTTEF(), and tightenUbTTEF().

◆ computeImpliedEst()

static SCIP_RETCODE computeImpliedEst ( SCIP scip,
SCIP_VAR var,
SCIP_HASHMAP addedvars,
int *  est 
)
static

returns the implied earliest start time

Parameters
scipSCIP data structure
varvariable for which the implied est should be returned
addedvarshash map containig the variable which are already added
estpointer 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 SCIP_RETCODE computeImpliedLct ( SCIP scip,
SCIP_VAR var,
int  duration,
SCIP_HASHMAP addedvars,
int *  lct 
)
static

returns the implied latest completion time

Parameters
scipSCIP data structure
varvariable for which the implied est should be returned
durationduration of the given job
addedvarshash map containig the variable which are already added
lctpointer 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 SCIP_RETCODE collectBinaryVars ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_VAR ***  vars,
int **  coefs,
int *  nvars,
int *  startindices,
int  curtime,
int  nstarted,
int  nfinished 
)
static

collects all necessary binary variables to represent the jobs which can be active at time point of interest

Parameters
scipSCIP data structure
consdataconstraint data
varspointer to the array to store the binary variables
coefspointer to store the coefficients
nvarsnumber if collect binary variables
startindicespermutation with rspect to the start times
curtimecurrent point in time
nstartednumber of jobs that start before the curtime or at curtime
nfinishednumber of jobs that finished before curtime or at curtime

Definition at line 513 of file cons_cumulative.c.

References b, collectIntVars(), MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPexistsConsLinking(), SCIPgetBinvarsLinking(), SCIPgetConsLinking(), SCIPgetValsLinking(), SCIPreallocBufferArray, and SCIPvarGetUbGlobal().

Referenced by computeImpliedLct(), and createCapacityRestriction().

◆ collectIntVars()

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

collect all integer variable which belong to jobs which can run at the point of interest

Parameters
scipSCIP data structure
consdataconstraint data
activevarsjobs that are currently running
startindicespermutation with rspect to the start times
curtimecurrent point in time
nstartednumber of jobs that start before the curtime or at curtime
nfinishednumber of jobs that finished before curtime or at curtime
lowershall cuts be created due to lower or upper bounds?
lhslhs for the new row sum of lbs + minoffset

Definition at line 611 of file cons_cumulative.c.

References createSortedEventpoints(), MIN, NULL, SCIP_OKAY, SCIPconvertRealToInt(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by collectBinaryVars(), and createCapacityRestrictionIntvars().

◆ createSortedEventpoints()

static void createSortedEventpoints ( SCIP scip,
int  nvars,
SCIP_VAR **  vars,
int *  durations,
int *  starttimes,
int *  endtimes,
int *  startindices,
int *  endindices,
SCIP_Bool  local 
)
static

initialize the sorted event point arrays

Parameters
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations per start time variable
starttimesarray to store sorted start events
endtimesarray to store sorted end events
startindicespermutation with rspect to the start times
endindicespermutation with rspect to the end times
localshall 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 void createSortedEventpointsSol ( SCIP scip,
SCIP_SOL sol,
int  nvars,
SCIP_VAR **  vars,
int *  durations,
int *  starttimes,
int *  endtimes,
int *  startindices,
int *  endindices 
)
static

initialize the sorted event point arrays w.r.t. the given primal solutions

Parameters
scipSCIP data structure
solsolution
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations per start time variable
starttimesarray to store sorted start events
endtimesarray to store sorted end events
startindicespermutation with rspect to the start times
endindicespermutation 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 void createSelectedSortedEventpointsSol ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_SOL sol,
int *  starttimes,
int *  endtimes,
int *  startindices,
int *  endindices,
int *  nvars,
SCIP_Bool  lower 
)
static

initialize the sorted event point arrays

Parameters
scipSCIP data structure
consdataconstraint data
solprimal CIP solution, NULL for current LP solution
starttimesarray to store sorted start events
endtimesarray to store sorted end events
startindicespermutation with rspect to the start times
endindicespermutation with rspect to the end times
nvarsnumber of variables that are integral
lowershall the constraints be derived for lower or upper bounds?

Definition at line 774 of file cons_cumulative.c.

References createSortedEventpoints(), getActiveVar(), MAX, MIN, 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 SCIP_RETCODE getActiveVar ( SCIP scip,
SCIP_VAR **  var,
int *  scalar,
int *  constant 
)
static

gets the active variables together with the constant

Parameters
scipSCIP data structure
varpointer to store the active variable
scalarpointer to store the scalar
constantpointer to store the constant

Definition at line 1149 of file cons_cumulative.c.

References computeTotalEnergy(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIPconvertRealToInt(), SCIPgetProbvarSum(), SCIPisZero(), SCIPvarGetStatus(), and SCIPvarIsActive().

Referenced by computeAlternativeBounds(), createSelectedSortedEventpointsSol(), varMayRoundDown(), and varMayRoundUp().

◆ computeTotalEnergy()

static int computeTotalEnergy ( int *  durations,
int *  demands,
int  njobs 
)
static

computes the total energy of all jobs

Parameters
durationsarray of job durations
demandsarray of job demands
njobsnumber of jobs

Definition at line 1194 of file cons_cumulative.c.

References setupAndSolveCumulativeSubscip().

Referenced by getActiveVar(), propagateLbTTEF(), and propagateUbTTEF().

◆ setupAndSolveCumulativeSubscip()

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

setup and solve subscip to solve single cumulative condition

Parameters
subscipsubscip data structure
objvalsarray of objective coefficients for each job (linear objective function), or NULL if none
durationsarray of durations
demandsarray of demands
njobsnumber of jobs (activities)
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
maxnodesmaximum number of branch-and-bound nodes (-1: no limit)
timelimittime limit for solving in seconds
memorylimitmemory limit for solving in mega bytes (MB)
estsarray of earliest start times for each job
lstsarray of latest start times for each job
infeasiblepointer to store if the subproblem was infeasible
unboundedpointer to store if the problem is unbounded
solvedpointer to store if the problem is solved (to optimality)
errorpointer 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()

◆ conshdlrdataCreate()

static SCIP_RETCODE conshdlrdataCreate ( SCIP scip,
SCIP_CONSHDLRDATA **  conshdlrdata,
SCIP_EVENTHDLR eventhdlr 
)
static

creates constaint handler data for cumulative constraint handler

Parameters
scipSCIP data structure
conshdlrdatapointer to store the constraint handler data
eventhdlrevent 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 void conshdlrdataFree ( SCIP scip,
SCIP_CONSHDLRDATA **  conshdlrdata 
)
static

frees constraint handler data for logic or constraint handler

Parameters
scipSCIP data structure
conshdlrdatapointer 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 SCIP_RETCODE consdataCatchEvents ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_EVENTHDLR eventhdlr 
)
static

catches bound change events for all variables in transformed cumulative constraint

Parameters
scipSCIP data structure
consdatacumulative constraint data
eventhdlrevent 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 SCIP_RETCODE consdataDropEvents ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_EVENTHDLR eventhdlr,
int  pos 
)
static

drops events for variable at given position

Parameters
scipSCIP data structure
consdatacumulative constraint data
eventhdlrevent handler to call for the event processing
posarray 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 SCIP_RETCODE consdataDropAllEvents ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_EVENTHDLR eventhdlr 
)
static

drops bound change events for all variables in transformed linear constraint

Parameters
scipSCIP data structure
consdatalinear constraint data
eventhdlrevent 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 void initializeLocks ( SCIP_CONSDATA consdata,
SCIP_Bool  locked 
)
static

initialize variable lock data structure

Parameters
consdataconstraint data
lockedshould the variable be locked?

Definition at line 1859 of file cons_cumulative.c.

References consdataCreate().

Referenced by consdataCreate(), consdataDropAllEvents(), and removeRedundantConss().

◆ consdataCreate()

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

creates constraint data of cumulative constraint

Parameters
scipSCIP data structure
consdatapointer to consdata
varsarray of integer variables
linkingconssarray of linking constraints for the integer variables, or NULL
durationsarray containing corresponding durations
demandsarray containing corresponding demands
nvarsnumber of variables
capacityavailable cumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
checkis 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 SCIP_RETCODE consdataFreeRows ( SCIP scip,
SCIP_CONSDATA **  consdata 
)
static

releases LP rows of constraint data and frees rows array

Parameters
scipSCIP data structure
consdataconstraint 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 SCIP_RETCODE consdataFree ( SCIP scip,
SCIP_CONSDATA **  consdata 
)
static

frees a cumulative constraint data

Parameters
scipSCIP data structure
consdatapointer 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 void consdataPrint ( SCIP scip,
SCIP_CONSDATA consdata,
FILE *  file 
)
static

prints cumulative constraint to file stream

Parameters
scipSCIP data structure
consdatacumulative constraint data
fileoutput 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 SCIP_RETCODE consdataDeletePos ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_CONS cons,
int  pos 
)
static

deletes coefficient at given position from constraint data

Parameters
scipSCIP data structure
consdatacumulative constraint data
consknapsack constraint
posposition 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 SCIP_RETCODE consdataCollectLinkingCons ( SCIP scip,
SCIP_CONSDATA consdata 
)
static

◆ checkCumulativeCondition()

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

check for the given starting time variables with their demands and durations if the cumulative conditions for the given solution is satisfied

Parameters
scipSCIP data structure
solprimal solution, or NULL for current LP/pseudo solution
nvarsnumber of variables (jobs)
varsarray of integer variable which corresponds to starting times for a job
durationsarray containing corresponding durations
demandsarray containing corresponding demands
capacityavailable cumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
violatedpointer to store if the cumulative condition is violated
consconstraint which is checked
printreasonshould 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 SCIP_RETCODE checkCons ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_Bool violated,
SCIP_Bool  printreason 
)
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
scipSCIP data structure
consconstraint to be checked
solprimal solution, or NULL for current LP/pseudo solution
violatedpointer to store if the constraint is violated
printreasonshould 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 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

resolves the propagation of the core time algorithm

Parameters
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
infervarinference variable
inferdemanddemand of the inference variable
inferpeaktime point which causes the propagation
relaxedpeakrelaxed time point which would be sufficient to be proved
bdchgidxthe index of the bound change, representing the point of time where the change took place
usebdwideningshould bound widening be used during conflict analysis?
provedpeakpointer to store the actually proved peak, or NULL
explanationbool 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, MIN, 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 int computeOverlap ( int  begin,
int  end,
int  est,
int  lst,
int  duration 
)
static

compute the minimum overlaps w.r.t. the duration of the job and the time window [begin,end)

Parameters
beginbegin of the times interval
endend of time interval
estearliest start time
lstlatest start time
durationduration of the job

Definition at line 2812 of file cons_cumulative.c.

References analyzeEnergyRequirement(), and MIN3.

Referenced by analyzeEnergyRequirement(), and resolvePropagationCoretimes().

◆ analyzeEnergyRequirement()

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

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
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycapacity of the cumulative condition
beginbegin of the time window
endend of the time window
infervarvariable which was propagate, or NULL
boundtypethe type of the changed bound (lower or upper bound)
bdchgidxthe index of the bound change, representing the point of time where the change took place
relaxedbdthe relaxed bound which is sufficient to be explained
usebdwideningshould bound widening be used during conflict analysis?
explanationbool 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, MIN, MIN3, NULL, respropCumulativeCondition(), SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_UNKNOWN, SCIPaddConflictLb(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictUb(), SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetConflictVarLb(), SCIPgetConflictVarUb(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPsortDownIntIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by computeOverlap(), propagateLbTTEF(), propagateTTEF(), propagateUbTTEF(), respropCumulativeCondition(), tightenLbTTEF(), and tightenUbTTEF().

◆ respropCumulativeCondition()

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 
)
static

resolve propagation w.r.t. the cumulative condition

Parameters
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
infervarthe conflict variable whose bound change has to be resolved
inferinfothe user information
boundtypethe type of the changed bound (lower or upper bound)
bdchgidxthe index of the bound change, representing the point of time where the change took place
relaxedbdthe relaxed bound which is sufficient to be explained
usebdwideningshould bound widening be used during conflict analysis?
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
resultpointer 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, MIN, 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 SCIP_RETCODE applyAlternativeBoundsBranching ( SCIP scip,
SCIP_VAR **  vars,
int  nvars,
int *  alternativelbs,
int *  alternativeubs,
int *  downlocks,
int *  uplocks,
SCIP_Bool branched 
)
static

apply all fixings which are given by the alternative bounds

Parameters
scipSCIP data structure
varsarray of active variables
nvarsnumber of active variables
alternativelbsalternative lower bounds
alternativeubsalternative lower bounds
downlocksnumber of constraints with down lock participating by the computation
uplocksnumber of constraints with up lock participating by the computation
branchedpointer 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 void subtractStartingJobDemands ( SCIP_CONSDATA consdata,
int  curtime,
int *  starttimes,
int *  startindices,
int *  freecapacity,
int *  idx,
int  nvars 
)
static

remove the capacity requirments for all job which start at the curtime

Parameters
consdataconstraint data
curtimecurrent point in time
starttimesarray of start times
startindicespermutation with respect to the start times
freecapacitypointer to store the resulting free capacity
idxpointer to index in start time array
nvarsnumber 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 void addEndingJobDemands ( SCIP_CONSDATA consdata,
int  curtime,
int *  endtimes,
int *  endindices,
int *  freecapacity,
int *  idx,
int  nvars 
)
static

add the capacity requirments for all job which end at the curtime

Parameters
consdataconstraint data
curtimecurrent point in time
endtimesarray of end times
endindicespermutation with rspect to the end times
freecapacitypointer to store the resulting free capacity
idxpointer to index in end time array
nvarsnumber 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 SCIP_RETCODE computePeak ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_SOL sol,
int *  timepoint 
)
static

computes a point in time when the capacity is exceeded returns hmax if this does not happen

Parameters
scipSCIP data structure
consdataconstraint handler data
solprimal solution, or NULL for current LP/pseudo solution
timepointpointer 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 SCIP_RETCODE collectBranchingCands ( SCIP scip,
SCIP_CONS **  conss,
int  nconss,
SCIP_SOL sol,
int *  nbranchcands 
)
static

checks all cumulative constraints for infeasibility and add branching candidates to storage

Parameters
scipSCIP data structure
conssconstraints to be processed
nconssnumber of constraints
solprimal solution, or NULL for current LP/pseudo solution
nbranchcandspointer to store the number of branching variables

Definition at line 3534 of file cons_cumulative.c.

References computePeak(), enforceSolution(), MIN, 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 SCIP_RETCODE enforceSolution ( SCIP scip,
SCIP_CONS **  conss,
int  nconss,
SCIP_SOL sol,
SCIP_Bool  branch,
SCIP_RESULT result 
)
static

enforcement of an LP, pseudo, or relaxation solution

Parameters
scipSCIP data structure
conssconstraints to be processed
nconssnumber of constraints
solsolution to enforce (NULL for LP or pseudo solution)
branchshould branching candidates be collected
resultpointer 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()

static SCIP_Bool isConsIndependently ( SCIP scip,
SCIP_CONS cons 
)
static

check if cumulative constraint is independently of all other constraints

Parameters
scipSCIP data structure
conscumulative 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 SCIP_RETCODE solveIndependentCons ( SCIP scip,
SCIP_CONS cons,
SCIP_Longint  maxnodes,
int *  nchgbds,
int *  nfixedvars,
int *  ndelconss,
SCIP_Bool cutoff,
SCIP_Bool unbounded 
)
static

in case the cumulative constraint is independent of every else, solve the cumulative problem and apply the fixings (dual reductions)

Parameters
scipSCIP data structure
conscumulative constraint
maxnodesnumber of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit)
nchgbdspointer to store the number changed variable bounds
nfixedvarspointer to count number of fixings
ndelconsspointer to count number of deleted constraints
cutoffpointer to store if the constraint is infeasible
unboundedpointer to store if the constraint is unbounded

Definition at line 3714 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 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

start conflict analysis to analysis the core insertion which is infeasible

Parameters
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
infervarstart time variable which lead to the infeasibilty
inferdurationduration of the start time variable
inferdemanddemand of the start time variable
inferpeakprofile preak which causes the infeasibilty
usebdwideningshould bound widening be used during conflict analysis?
initializedpointer to store if the conflict analysis was initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL

Definition at line 3929 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 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

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
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
consconstraint which is propagated
profileresource profile
idxposition of the variable to propagate
nchgbdspointer to store the number of bound changes
usebdwideningshould bound widening be used during conflict analysis?
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
infeasiblepointer to store if the constraint is infeasible

Definition at line 3985 of file cons_cumulative.c.

References analyseInfeasibelCoreInsertion(), CONSHDLR_NAME, coretimesUpdateUb(), getInferInfo(), inferInfoToInt(), MIN, 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 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

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
scipSCIP data structure
varstart time variable to propagate
durationduration of the job
demanddemand of the job
capacitycumulative capacity
consconstraint which is propagated
profileresource profile
idxposition of the variable to propagate
nchgbdspointer to store the number of bound changes

Definition at line 4138 of file cons_cumulative.c.

References computeCoreEngeryAfter(), 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().

◆ computeCoreEngeryAfter()

static SCIP_RETCODE computeCoreEngeryAfter ( SCIP scip,
SCIP_PROFILE profile,
int  nvars,
int *  ests,
int *  lcts,
int *  coreEnergyAfterEst,
int *  coreEnergyAfterLct 
)
static

compute for the different earliest start and latest completion time the core energy of the corresponding time points

Parameters
scipSCIP data structure
profilecore profile
nvarsnumber of start time variables (activities)
estsarray of sorted earliest start times
lctsarray of sorted latest completion times
coreEnergyAfterEstarray to store the core energy after the earliest start time of each job
coreEnergyAfterLctarray to store the core energy after the latest completion time of each job

Definition at line 4272 of file cons_cumulative.c.

References collectDataTTEF(), SCIP_OKAY, SCIPprofileGetLoad(), SCIPprofileGetNTimepoints(), and SCIPprofileGetTime().

Referenced by coretimesUpdateUb(), and propagateTTEF().

◆ collectDataTTEF()

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

collect earliest start times, latest completion time, and free energy contributions

Parameters
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
permestsarray to store the variable positions
estsarray to store earliest start times
permlctsarray to store the variable positions
lctsarray to store latest completion times
ectsarray to store earliest completion times of the flexible part of the job
lstsarray to store latest start times of the flexible part of the job
flexenergiesarray to store the flexible energies of each job

Definition at line 4343 of file cons_cumulative.c.

References computeCoreWithInterval(), MAX, MIN, SCIPconvertRealToInt(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and tightenLbTTEF().

Referenced by computeCoreEngeryAfter(), and propagateTTEF().

◆ tightenLbTTEF()

static SCIP_RETCODE tightenLbTTEF ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
int  nvars,
SCIP_VAR **  vars,
int *  durations,
int *  demands,
int  capacity,
int  hmin,
int  hmax,
SCIP_VAR var,
int  duration,
int  demand,
int  est,
int  ect,
int  lct,
int  begin,
int  end,
int  energy,
int *  bestlb,
int *  inferinfos,
SCIP_Bool initialized,
SCIP_Bool explanation,
SCIP_Bool cutoff 
)
static

try to tighten the lower bound of the given variable

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
varvariable to be considered for upper bound tightening
durationduration of the job
demanddemand of the job
estearliest start time of the job
ectearliest completion time of the flexible part of the job
lctlatest completion time of the job
beginbegin of the time window under investigation
endend of the time window under investigation
energyavailable energy for the flexible part of the hob within the time window
bestlbpointer to strope the best lower bound change
inferinfospointer to store the inference information which is need for the (best) lower bound change
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoffpointer to store if the constraint is infeasible

Definition at line 4411 of file cons_cumulative.c.

References analyzeEnergyRequirement(), computeCoreWithInterval(), FALSE, getInferInfo(), inferInfoToInt(), MAX, MIN, NULL, PROPRULE_3_TTEF, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPaddConflictUb(), SCIPconvertRealToInt(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPvarGetUbLocal(), tightenUbTTEF(), and TRUE.

Referenced by collectDataTTEF(), and propagateLbTTEF().

◆ tightenUbTTEF()

static SCIP_RETCODE tightenUbTTEF ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
int  nvars,
SCIP_VAR **  vars,
int *  durations,
int *  demands,
int  capacity,
int  hmin,
int  hmax,
SCIP_VAR var,
int  duration,
int  demand,
int  est,
int  lst,
int  lct,
int  begin,
int  end,
int  energy,
int *  bestub,
int *  inferinfos,
SCIP_Bool initialized,
SCIP_Bool explanation,
SCIP_Bool cutoff 
)
static

try to tighten the upper bound of the given variable

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
varvariable to be considered for upper bound tightening
durationduration of the job
demanddemand of the job
estearliest start time of the job
lstlatest start time of the flexible part of the job
lctlatest completion time of the job
beginbegin of the time window under investigation
endend of the time window under investigation
energyavailable energy for the flexible part of the hob within the time window
bestubpointer to strope the best upper bound change
inferinfospointer to store the inference information which is need for the (best) upper bound change
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoffpointer to store if the constraint is infeasible

Definition at line 4524 of file cons_cumulative.c.

References analyzeEnergyRequirement(), computeCoreWithInterval(), FALSE, getInferInfo(), inferInfoToInt(), MAX, MIN, NULL, propagateUbTTEF(), PROPRULE_3_TTEF, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPconvertRealToInt(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPvarGetLbLocal(), and TRUE.

Referenced by propagateUbTTEF(), and tightenLbTTEF().

◆ propagateUbTTEF()

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

propagate the upper bounds and "opportunistically" the lower bounds using the time-table edge-finding algorithm

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
newlbsarray to buffer new lower bounds
newubsarray to buffer new upper bounds
lbinferinfosarray to store the inference information for the lower bound changes
ubinferinfosarray to store the inference information for the upper bound changes
lstsarray of latest start time of the flexible part in the same order as the variables
flexenergiesarray of flexible energies in the same order as the variables
permpermutation of the variables w.r.t. the non-decreasing order of the earliest start times
estsarray with earliest strart times sorted in non-decreasing order
lctsarray with latest completion times sorted in non-decreasing order
coreEnergyAfterEstcore energy after the earliest start times
coreEnergyAfterLctcore energy after the latest completion times
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoffpointer to store if the constraint is infeasible

Definition at line 4638 of file cons_cumulative.c.

References analyzeEnergyRequirement(), computeCoreWithInterval(), computeTotalEnergy(), CONSHDLR_NAME, FALSE, getInferInfo(), inferInfoToInt(), MAX, MIN, NULL, propagateLbTTEF(), PROPRULE_3_TTEF, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIP_UNKNOWN, SCIPaddConflictUb(), SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), tightenUbTTEF(), and TRUE.

Referenced by propagateTTEF(), and tightenUbTTEF().

◆ propagateLbTTEF()

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

propagate the lower bounds and "opportunistically" the upper bounds using the time-table edge-finding algorithm

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
newlbsarray to buffer new lower bounds
newubsarray to buffer new upper bounds
lbinferinfosarray to store the inference information for the lower bound changes
ubinferinfosarray to store the inference information for the upper bound changes
ectsarray of earliest completion time of the flexible part in the same order as the variables
flexenergiesarray of flexible energies in the same order as the variables
permpermutation of the variables w.r.t. the non-decreasing order of the latest completion times
estsarray with earliest strart times sorted in non-decreasing order
lctsarray with latest completion times sorted in non-decreasing order
coreEnergyAfterEstcore energy after the earliest start times
coreEnergyAfterLctcore energy after the latest completion times
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoffpointer to store if the constraint is infeasible

Definition at line 4989 of file cons_cumulative.c.

References analyzeEnergyRequirement(), computeCoreWithInterval(), computeTotalEnergy(), CONSHDLR_NAME, FALSE, getInferInfo(), inferInfoToInt(), MAX, MIN, NULL, propagateTTEF(), PROPRULE_3_TTEF, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIP_UNKNOWN, SCIPaddConflictUb(), SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), tightenLbTTEF(), and TRUE.

Referenced by propagateTTEF(), and propagateUbTTEF().

◆ propagateTTEF()

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

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
scipSCIP data structure
conshdlrdataconstraint handler data
profilecurrent core profile
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
consconstraint which is propagated (needed to SCIPinferVar**Cons())
nchgbdspointer to store the number of bound changes
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoffpointer to store if the constraint is infeasible

Definition at line 5329 of file cons_cumulative.c.

References analyzeEnergyRequirement(), collectDataTTEF(), computeCoreEngeryAfter(), 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 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

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
scipSCIP data structure
conshdlrdataconstraint handler data
profilecore profile
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
consconstraint which is propagated (needed to SCIPinferVar**Cons())
nchgbdspointer to store the number of bound changes
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoffpointer to store if the constraint is infeasible

Definition at line 5518 of file cons_cumulative.c.

References analyseInfeasibelCoreInsertion(), CONSHDLR_NAME, coretimesUpdateLb(), coretimesUpdateUb(), FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPprofileDeleteCore(), SCIPprofileGetNTimepoints(), SCIPprofileGetTime(), SCIPprofileInsertCore(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by propagateCumulativeCondition(), and propagateTTEF().

◆ createNodedata()

static SCIP_RETCODE createNodedata ( SCIP scip,
SCIP_NODEDATA **  nodedata 
)
static

creates a node data structure

Parameters
scipSCIP data structure
nodedatapointer to store the create node data

Definition at line 5685 of file cons_cumulative.c.

References freeNodedata(), NULL, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIPallocBuffer, and TRUE.

Referenced by checkOverloadViaThetaTree(), and insertThetanode().

◆ freeNodedata()

static void freeNodedata ( SCIP scip,
SCIP_NODEDATA **  nodedata 
)
static

frees a node data structure

Parameters
scipSCIP data structure
nodedatapointer to store node data which should be freed

Definition at line 5709 of file cons_cumulative.c.

References nodedata, NULL, SCIPfreeBuffer, and updateEnvelop().

Referenced by checkOverloadViaThetaTree(), and createNodedata().

◆ updateEnvelop()

static SCIP_RETCODE updateEnvelop ( SCIP scip,
SCIP_BTNODE node 
)
static

update node data structure strating form the given node along the path to the root node

Parameters
scipSCIP data structure
nodesearch node which inserted

Definition at line 5722 of file cons_cumulative.c.

References MAX, nodedata, NULL, SCIP_OKAY, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPdebugMsg, and updateKeyOnTrace().

Referenced by deleteLambdaLeaf(), freeNodedata(), insertThetanode(), and moveNodeToLambda().

◆ updateKeyOnTrace()

static void updateKeyOnTrace ( SCIP_BTNODE node,
SCIP_Real  key 
)
static

updates the key of the first parent on the trace which comes from left

Parameters
nodenode to start the trace
keyupdate search key

Definition at line 5812 of file cons_cumulative.c.

References deleteLambdaLeaf(), nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetParent(), SCIPbtnodeIsLeftchild(), and SCIPbtnodeIsRoot().

Referenced by deleteLambdaLeaf(), and updateEnvelop().

◆ deleteLambdaLeaf()

◆ moveNodeToLambda()

static SCIP_RETCODE moveNodeToLambda ( SCIP scip,
SCIP_BT tree,
SCIP_BTNODE node 
)
static

moves a node form the theta set into the lambda set and updates the envelops

Parameters
scipSCIP data structure
treebinary tree
nodenode to move into the lambda set

Definition at line 5917 of file cons_cumulative.c.

References FALSE, insertThetanode(), nodedata, NULL, SCIP_CALL, SCIP_OKAY, SCIPbtnodeGetData(), and updateEnvelop().

Referenced by deleteLambdaLeaf(), and inferboundsEdgeFinding().

◆ insertThetanode()

static SCIP_RETCODE insertThetanode ( SCIP scip,
SCIP_BT tree,
SCIP_BTNODE node,
SCIP_NODEDATA **  nodedatas,
int *  nnodedatas 
)
static

inserts a node into the theta set and update the envelops

Parameters
scipSCIP data structure
treebinary tree
nodenode to insert
nodedatasarray of node data
nnodedataspointer to number of node data

Definition at line 5953 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 updateEnvelop().

Referenced by checkOverloadViaThetaTree(), and moveNodeToLambda().

◆ findResponsibleLambdaLeafTraceEnergy()

static SCIP_BTNODE* findResponsibleLambdaLeafTraceEnergy ( SCIP_BTNODE node)
static

returns the leaf responsible for the lambda energy

Parameters
nodenode which defines the subtree beases on the lambda energy

Definition at line 6057 of file cons_cumulative.c.

References findResponsibleLambdaLeafTraceEnvelop(), nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), and SCIPbtnodeIsLeaf().

Referenced by findResponsibleLambdaLeafTraceEnvelop(), and insertThetanode().

◆ findResponsibleLambdaLeafTraceEnvelop()

static SCIP_BTNODE* findResponsibleLambdaLeafTraceEnvelop ( SCIP_BTNODE node)
static

returns the leaf responsible for the lambda envelop

Parameters
nodenode which defines the subtree beases on the lambda envelop

Definition at line 6106 of file cons_cumulative.c.

References collectThetaSubtree(), findResponsibleLambdaLeafTraceEnergy(), nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), and SCIPbtnodeIsLeaf().

Referenced by findResponsibleLambdaLeafTraceEnergy(), and inferboundsEdgeFinding().

◆ collectThetaSubtree()

static void collectThetaSubtree ( SCIP_BTNODE node,
SCIP_BTNODE **  omegaset,
int *  nelements,
int *  est,
int *  lct,
int *  energy 
)
static

reports all elements from set theta to generate a conflicting set

Parameters
nodenode within a theta subtree
omegasetarray to store the collected jobs
nelementspointer to store the number of elements in omegaset
estpointer to store the earliest start time of the omega set
lctpointer to store the latest start time of the omega set
energypointer to store the energy of the omega set

Definition at line 6159 of file cons_cumulative.c.

References MAX, MIN, nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPdebugMessage, SCIPvarGetName(), and traceThetaEnvelop().

Referenced by findResponsibleLambdaLeafTraceEnvelop(), traceLambdaEnergy(), traceLambdaEnvelop(), and traceThetaEnvelop().

◆ traceThetaEnvelop()

static void traceThetaEnvelop ( SCIP_BTNODE node,
SCIP_BTNODE **  omegaset,
int *  nelements,
int *  est,
int *  lct,
int *  energy 
)
static

collect the jobs (omega set) which are contribute to theta envelop from the theta set

Parameters
nodenode whose theta envelop needs to be backtracked
omegasetarray to store the collected jobs
nelementspointer to store the number of elements in omegaset
estpointer to store the earliest start time of the omega set
lctpointer to store the latest start time of the omega set
energypointer to store the energy of the omega set

Definition at line 6194 of file cons_cumulative.c.

References collectThetaSubtree(), nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), and traceLambdaEnergy().

Referenced by collectThetaSubtree(), and traceLambdaEnvelop().

◆ traceLambdaEnergy()

static void traceLambdaEnergy ( SCIP_BTNODE node,
SCIP_BTNODE **  omegaset,
int *  nelements,
int *  est,
int *  lct,
int *  energy 
)
static

collect the jobs (omega set) which are contribute to lambda envelop from the theta set

Parameters
nodenode whose lambda envelop needs to be backtracked
omegasetarray to store the collected jobs
nelementspointer to store the number of elements in omega set
estpointer to store the earliest start time of the omega set
lctpointer to store the latest start time of the omega set
energypointer to store the energy of the omega set

Definition at line 6254 of file cons_cumulative.c.

References collectThetaSubtree(), nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), and traceLambdaEnvelop().

Referenced by traceLambdaEnvelop(), and traceThetaEnvelop().

◆ traceLambdaEnvelop()

static void traceLambdaEnvelop ( SCIP_BTNODE node,
SCIP_BTNODE **  omegaset,
int *  nelements,
int *  est,
int *  lct,
int *  energy 
)
static

collect the jobs (omega set) which are contribute to lambda envelop from the theta set

Parameters
nodenode whose lambda envelop needs to be backtracked
omegasetarray to store the collected jobs
nelementspointer to store the number of elements in omega set
estpointer to store the earliest start time of the omega set
lctpointer to store the latest start time of the omega set
energypointer to store the energy of the omega set

Definition at line 6311 of file cons_cumulative.c.

References collectThetaSubtree(), computeEnergyContribution(), nodedata, NULL, SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), traceLambdaEnergy(), and traceThetaEnvelop().

Referenced by inferboundsEdgeFinding(), and traceLambdaEnergy().

◆ computeEnergyContribution()

static int computeEnergyContribution ( SCIP_BTNODE node)
static

compute the energy contribution by job which corresponds to the given leaf

Parameters
nodeleaf

Definition at line 6377 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 SCIP_DECL_SORTPTRCOMP ( compNodeEst  )
static

comparison method for two node data w.r.t. the earliest start time

Definition at line 6401 of file cons_cumulative.c.

References SCIPbtnodeGetData().

Referenced by computeEnergyContribution().

◆ SCIP_DECL_SORTPTRCOMP() [2/2]

static SCIP_DECL_SORTPTRCOMP ( compNodedataLct  )
static

comparison method for two node data w.r.t. the latest completion time

Definition at line 6414 of file cons_cumulative.c.

References analyzeConflictOverload().

◆ analyzeConflictOverload()

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

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
scipSCIP data structure
leavesresponsible leaves for the overload
capacitycumulative capacity
nleavesnumber of responsible leaves
estearliest start time of the ......
lctlatest completly time of the ....
reportedenergyenergy which already reported
propestshould the earliest start times be propagated, otherwise the latest completion times
shiftshift applied to all jobs before adding them to the tree
usebdwideningshould bound widening be used during conflict analysis?
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL

Definition at line 6431 of file cons_cumulative.c.

References computeEnergyContribution(), computeEstOmegaset(), FALSE, nodedata, NULL, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictUb(), SCIPbtnodeGetData(), SCIPdebugMsg, SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPsortDownPtr(), SCIPswapInts(), and TRUE.

Referenced by checkOverloadViaThetaTree(), inferboundsEdgeFinding(), and SCIP_DECL_SORTPTRCOMP().

◆ computeEstOmegaset()

static int computeEstOmegaset ( SCIP scip,
int  duration,
int  demand,
int  capacity,
int  est,
int  lct,
int  energy 
)
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
scipSCIP data structure
durationduration of the job to move
demanddemand of the job to move
capacitycumulative capacity
estearliest start time of the omega set
lctlatest start time of the omega set
energyenergy of the omega set

Definition at line 6541 of file cons_cumulative.c.

References inferboundsEdgeFinding(), NULL, SCIP_Real, and SCIPfeasCeil().

Referenced by analyzeConflictOverload(), and inferboundsEdgeFinding().

◆ inferboundsEdgeFinding()

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

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
scipSCIP data structure
conshdlrdataconstraint handler data
consconstraint which is propagated
treebinary tree constaining the theta and lambda sets
leavesarray of all leaves for each job one
capacitycumulative capacity
ncandsnumber of candidates
propestshould the earliest start times be propagated, otherwise the latest completion times
shiftshift applied to all jobs before adding them to the tree
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
nchgbdspointer to store the number of bound changes
cutoffpointer to store if the constraint is infeasible

Definition at line 6575 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_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 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

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
scipSCIP data structure
conshdlrdataconstraint handler data
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
consconstraint which is propagated
propestshould the earliest start times be propagated, otherwise the latest completion times
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
nchgbdspointer to store the number of bound changes
cutoffpointer to store if the constraint is infeasible

Definition at line 6783 of file cons_cumulative.c.

References analyzeConflictOverload(), CONSHDLR_NAME, createNodedata(), FALSE, freeNodedata(), inferboundsEdgeFinding(), insertThetanode(), MAX, nodedata, NULL, propagateEdgeFinding(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPblkmem(), SCIPbtCreate(), SCIPbtFree(), SCIPbtGetRoot(), SCIPbtIsEmpty(), SCIPbtnodeCreate(), SCIPbtnodeGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPsortPtr(), SCIPstatistic, SCIPswapInts(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by inferboundsEdgeFinding(), and propagateEdgeFinding().

◆ propagateEdgeFinding()

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

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
scipSCIP data structure
conshdlrdataconstraint handler data
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
consconstraint which is propagated
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
nchgbdspointer to store the number of bound changes
cutoffpointer to store if the constraint is infeasible

Definition at line 7086 of file cons_cumulative.c.

References checkOverloadViaThetaTree(), consCheckRedundancy(), FALSE, SCIP_CALL, SCIP_OKAY, and TRUE.

Referenced by checkOverloadViaThetaTree(), and propagateCumulativeCondition().

◆ consCheckRedundancy()

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

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
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
redundantpointer to store whether this constraint is redundant

Definition at line 7135 of file cons_cumulative.c.

References createCoreProfile(), FALSE, MAX, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPfreeBufferArray, SCIPsortIntInt(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by propagateCumulativeCondition(), and propagateEdgeFinding().

◆ createCoreProfile()

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

creates the worst case resource profile, that is, all jobs are inserted with the earliest start and latest completion time

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data
profileresource profile
nvarsnumber of variables (jobs)
varsarray of integer variable which corresponds to starting times for a job
durationsarray containing corresponding durations
demandsarray containing corresponding demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoffpointer to store if the constraint is infeasible

Definition at line 7257 of file cons_cumulative.c.

References analyseInfeasibelCoreInsertion(), CONSHDLR_NAME, MAX, MIN, 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 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

propagate the cumulative condition

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data
presoltimingcurrent presolving timing
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
consconstraint which is propagated (needed to SCIPinferVar**Cons())
nchgbdspointer to store the number of bound changes
redundantpointer to store if the constraint is redundant
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoffpointer to store if the constraint is infeasible

Definition at line 7348 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 SCIP_RETCODE propagateCons ( SCIP scip,
SCIP_CONS cons,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_PRESOLTIMING  presoltiming,
int *  nchgbds,
int *  ndelconss,
SCIP_Bool cutoff 
)
static

propagate the cumulative constraint

Parameters
scipSCIP data structure
consconstraint to propagate
conshdlrdataconstraint handler data
presoltimingcurrent presolving timing
nchgbdspointer to store the number of bound changes
ndelconsspointer to store the number of deleted constraints
cutoffpointer to store if the constraint is infeasible

Definition at line 7420 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 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

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
scipSCIP data structure
varsproblem variables
nvarsnumber of problem variables
probingposvariable number to apply probing on
leftubupper bound of probing variable in left branch
rightlblower bound of probing variable in right branch
leftimpllbslower bounds after applying implications and cliques in left branch, or NULL
leftimplubsupper bounds after applying implications and cliques in left branch, or NULL
leftproplbslower bounds after applying domain propagation in left branch
leftpropubsupper bounds after applying domain propagation in left branch
rightimpllbslower bounds after applying implications and cliques in right branch, or NULL
rightimplubsupper bounds after applying implications and cliques in right branch, or NULL
rightproplbslower bounds after applying domain propagation in right branch
rightpropubsupper bounds after applying domain propagation in right branch
nfixedvarspointer to counter which is increased by the number of deduced variable fixations
successbuffer to store whether a probing succeed to dual fix the variable
cutoffbuffer to store whether a cutoff is detected

Definition at line 7501 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 SCIP_RETCODE varMayRoundDown ( SCIP scip,
SCIP_VAR var,
SCIP_Bool roundable 
)
static

is it possible, to round variable down w.r.t. objective function

Parameters
scipSCIP data structure
varproblem variable
roundablepointer to store if the variable can be rounded down

Definition at line 7599 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 SCIP_RETCODE varMayRoundUp ( SCIP scip,
SCIP_VAR var,
SCIP_Bool roundable 
)
static

is it possible, to round variable up w.r.t. objective function

Parameters
scipSCIP data structure
varproblem variable
roundablepointer to store if the variable can be rounded down

Definition at line 7648 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 SCIP_RETCODE computeAlternativeBounds ( SCIP scip,
SCIP_CONS **  conss,
int  nconss,
SCIP_Bool  local,
int *  alternativelbs,
int *  alternativeubs,
int *  downlocks,
int *  uplocks 
)
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
scipSCIP data structure
conssarray of cumulative constraint constraints
nconssnumber of cumulative constraints
localuse local bounds effective horizon?
alternativelbsalternative lower bounds
alternativeubsalternative lower bounds
downlocksnumber of constraints with down lock participating by the computation
uplocksnumber of constraints with up lock participating by the computation

Definition at line 7701 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 SCIP_RETCODE applyAlternativeBoundsFixing ( SCIP scip,
SCIP_VAR **  vars,
int  nvars,
int *  alternativelbs,
int *  alternativeubs,
int *  downlocks,
int *  uplocks,
int *  nfixedvars,
SCIP_Bool cutoff 
)
static

apply all fixings which are given by the alternative bounds

Parameters
scipSCIP data structure
varsarray of active variables
nvarsnumber of active variables
alternativelbsalternative lower bounds
alternativeubsalternative lower bounds
downlocksnumber of constraints with down lock participating by the computation
uplocksnumber of constraints with up lock participating by the computation
nfixedvarspointer to counter which is increased by the number of deduced variable fixations
cutoffbuffer to store whether a cutoff is detected

Definition at line 7835 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 SCIP_RETCODE propagateAllConss ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_CONS **  conss,
int  nconss,
SCIP_Bool  local,
int *  nfixedvars,
SCIP_Bool cutoff,
SCIP_Bool branched 
)
static

propagate all constraints together

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data
conssall cumulative constraint
nconssnumber of cumulative constraints
localuse local bounds effective horizon?
nfixedvarspointer to counter which is increased by the number of deduced variable fixations
cutoffbuffer to store whether a cutoff is detected
branchedpointer to store if a branching was applied, or NULL to avoid branching

Definition at line 7987 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 SCIP_RETCODE createCoverCutsTimepoint ( SCIP scip,
SCIP_CONS cons,
int *  startvalues,
int  time 
)
static

creates covering cuts for jobs violating resource constraints

Parameters
scipSCIP data structure
consconstraint to be checked
startvaluesupper bounds on finishing time per job for activities from 0,..., nactivities -1
timeat this point in time covering constraints are valid

Definition at line 8059 of file cons_cumulative.c.

References b, createCoverCuts(), MIN, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconvertRealToInt(), SCIPcreateEmptyRowCons(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetBinvarsLinking(), SCIPgetValsLinking(), SCIPinfinity(), SCIPreallocBlockMemoryArray, SCIPsnprintf(), SCIPsortIntInt(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by createCoverCuts(), and propagateAllConss().

◆ createCoverCuts()

static SCIP_RETCODE createCoverCuts ( SCIP scip,
SCIP_CONS cons 
)
static

method to construct cover cuts for all points in time

Parameters
scipSCIP data structure
consconstraint to be separated

Definition at line 8314 of file cons_cumulative.c.

References createCapacityRestriction(), createCoverCutsTimepoint(), MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPsortIntInt(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by createCoverCutsTimepoint(), and separateCoverCutsCons().

◆ createCapacityRestriction()

static SCIP_RETCODE createCapacityRestriction ( SCIP scip,
SCIP_CONS cons,
int *  startindices,
int  curtime,
int  nstarted,
int  nfinished,
SCIP_Bool  cutsasconss 
)
static

this method creates a row for time point curtime which insures the capacity restriction of the cumulative constraint

Parameters
scipSCIP data structure
consconstraint to be checked
startindicespermutation with rspect to the start times
curtimecurrent point in time
nstartednumber of jobs that start before the curtime or at curtime
nfinishednumber of jobs that finished before curtime or at curtime
cutsasconssshould the cumulative constraint create the cuts as constraints?

Definition at line 8453 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(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconsIsRemovable(), SCIPcreateConsKnapsack(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPflushRowExtensions(), SCIPfreeBufferArrayNull, SCIPinfinity(), SCIPprintRow(), SCIPreallocBlockMemoryArray, SCIPreleaseCons(), SCIPsnprintf(), and TRUE.

Referenced by consCapacityConstraintsFinder(), and createCoverCuts().

◆ consCapacityConstraintsFinder()

static SCIP_RETCODE consCapacityConstraintsFinder ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool  cutsasconss 
)
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
scipSCIP data structure
consconstraint to be checked
cutsasconssshould the cumulative constraint create the cuts as constraints?

Definition at line 8543 of file cons_cumulative.c.

References addEndingJobDemands(), createCapacityRestriction(), createRelaxation(), createSortedEventpoints(), FALSE, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPfreeBufferArray, and subtractStartingJobDemands().

Referenced by createCapacityRestriction(), and createRelaxation().

◆ createRelaxation()

static SCIP_RETCODE createRelaxation ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool  cutsasconss 
)
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
scipSCIP data structure
conscumulative constraint
cutsasconssshould the cumulative constraint create the cuts as constraints?

Definition at line 8674 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 SCIP_RETCODE addRelaxation ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool  cutsasconss,
SCIP_Bool infeasible 
)
static

adds linear relaxation of cumulative constraint to the LP

Parameters
scipSCIP data structure
conscumulative constraint
cutsasconssshould the cumulative constraint create the cuts as constraints?
infeasiblepointer to store whether an infeasibility was detected

Definition at line 8717 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 SCIP_RETCODE separateConsBinaryRepresentation ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_Bool separated,
SCIP_Bool cutoff 
)
static

checks constraint for violation, and adds it as a cut if possible

Parameters
scipSCIP data structure
conscumulative constraint to be separated
solprimal CIP solution, NULL for current LP solution
separatedpointer to store TRUE, if a cut was found
cutoffwhether a cutoff has been detected

Definition at line 8753 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 SCIP_RETCODE separateCoverCutsCons ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_Bool separated,
SCIP_Bool cutoff 
)
static

checks constraint for violation, and adds it as a cut if possible

Parameters
scipSCIP data structure
conslogic or constraint to be separated
solprimal CIP solution, NULL for current LP solution
separatedpointer to store TRUE, if a cut was found
cutoffwhether a cutoff has been detected

Definition at line 8829 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 SCIP_RETCODE createCapacityRestrictionIntvars ( SCIP scip,
SCIP_CONS cons,
int *  startindices,
int  curtime,
int  nstarted,
int  nfinished,
SCIP_Bool  lower 
)
static

this method creates a row for time point curtime which ensures the capacity restriction of the cumulative constraint

Parameters
scipSCIP data structure
consconstraint to be checked
startindicespermutation with rspect to the start times
curtimecurrent point in time
nstartednumber of jobs that start before the curtime or at curtime
nfinishednumber of jobs that finished before curtime or at curtime
lowershall cuts be created due to lower or upper bounds?

Definition at line 8948 of file cons_cumulative.c.

References collectIntVars(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsIsRemovable(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPflushRowExtensions(), SCIPfreeBufferArrayNull, SCIPinfinity(), SCIPprintRow(), SCIPreleaseRow(), SCIPsnprintf(), separateConsOnIntegerVariables(), and TRUE.

Referenced by separateConsOnIntegerVariables(), and separateCoverCutsCons().

◆ separateConsOnIntegerVariables()

static SCIP_RETCODE separateConsOnIntegerVariables ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_Bool  lower,
SCIP_Bool separated 
)
static

checks constraint for violation, and adds it as a cut if possible

Parameters
scipSCIP data structure
conscumulative constraint to be separated
solprimal CIP solution, NULL for current LP solution
lowershall cuts be created according to lower bounds?
separatedpointer to store TRUE, if a cut was found

Definition at line 9015 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()

static SCIP_Bool checkDemands ( SCIP scip,
SCIP_CONS cons 
)
static

returns TRUE if all demands are smaller than the capacity of the cumulative constraint and if the total demand is correct

Parameters
scipSCIP data structure
consconstraint to be checked

Definition at line 9122 of file cons_cumulative.c.

References deleteTrivilCons(), FALSE, NULL, SCIPconsGetData(), and TRUE.

Referenced by presolveCons(), SCIP_DECL_CONSPRESOL(), and separateConsOnIntegerVariables().

◆ deleteTrivilCons()

static SCIP_RETCODE deleteTrivilCons ( SCIP scip,
SCIP_CONS cons,
int *  ndelconss,
SCIP_Bool cutoff 
)
static

delete constraint if it consists of at most one job

Parameters
scipSCIP data structure
consconstraint to propagate
ndelconsspointer to store the number of deleted constraints
cutoffpointer to store if the constraint is infeasible

Definition at line 9163 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 SCIP_RETCODE removeIrrelevantJobs ( SCIP scip,
SCIP_CONS cons 
)
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
scipSCIP data structure
consconstraint to propagate

Definition at line 9205 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 SCIP_RETCODE adjustOversizedJobBounds ( SCIP scip,
SCIP_CONSDATA consdata,
int  pos,
int *  nchgbds,
int *  naddconss,
SCIP_Bool cutoff 
)
static

adjust bounds of over sizeed job (the demand is larger than the capacity)

Parameters
scipSCIP data structure
consdataconstraint data
posposition of job in the consdata
nchgbdspointer to store the number of changed bounds
naddconsspointer to store the number of added constraints
cutoffpointer to store if a cutoff was detected

Definition at line 9269 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 SCIP_RETCODE removeOversizedJobs ( SCIP scip,
SCIP_CONS cons,
int *  nchgbds,
int *  nchgcoefs,
int *  naddconss,
SCIP_Bool cutoff 
)
static

try to removed over sizeed jobs (the demand is larger than the capacity)

Parameters
scipSCIP data structure
consconstraint
nchgbdspointer to store the number of changed bounds
nchgcoefspointer to store the number of changed coefficient
naddconsspointer to store the number of added constraints
cutoffpointer to store if a cutoff was detected

Definition at line 9375 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 SCIP_RETCODE fixIntegerVariableUb ( SCIP scip,
SCIP_VAR var,
SCIP_Bool  uplock,
int *  nfixedvars 
)
static

fix integer variable to upper bound if the rounding locks and the object coefficient are in favor of that

Parameters
scipSCIP data structure
varinteger variable to fix
uplockhas thet start time variable a up lock
nfixedvarspointer to store the number fixed variables

Definition at line 9416 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 SCIP_RETCODE fixIntegerVariableLb ( SCIP scip,
SCIP_VAR var,
SCIP_Bool  downlock,
int *  nfixedvars 
)
static

fix integer variable to lower bound if the rounding locks and the object coefficient are in favor of that

Parameters
scipSCIP data structure
varinteger variable to fix
downlockhas the variable a down lock
nfixedvarspointer to store the number fixed variables

Definition at line 9468 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 SCIP_RETCODE normalizeCumulativeCondition ( SCIP scip,
int  nvars,
SCIP_VAR **  vars,
int *  durations,
int *  demands,
int *  capacity,
int *  nchgcoefs,
int *  nchgsides 
)
static

normalize cumulative condition

Parameters
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitypointer to store the changed cumulative capacity
nchgcoefspointer to count total number of changed coefficients
nchgsidespointer to count number of side changes

Definition at line 9515 of file cons_cumulative.c.

References MAX, MIN, normalizeDemands(), SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPcalcGreComDiv(), and SCIPdebugMsg.

Referenced by fixIntegerVariableLb(), normalizeDemands(), and SCIPnormalizeCumulativeCondition().

◆ normalizeDemands()

static SCIP_RETCODE normalizeDemands ( SCIP scip,
SCIP_CONS cons,
int *  nchgcoefs,
int *  nchgsides 
)
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
scipSCIP data structure
conscumulative constraint
nchgcoefspointer to count total number of changed coefficients
nchgsidespointer to count number of side changes

Definition at line 9590 of file cons_cumulative.c.

References computeEffectiveHorizonCumulativeCondition(), FALSE, normalizeCumulativeCondition(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsModifiable(), and TRUE.

Referenced by normalizeCumulativeCondition(), and presolveCons().

◆ computeEffectiveHorizonCumulativeCondition()

static SCIP_RETCODE computeEffectiveHorizonCumulativeCondition ( SCIP scip,
int  nvars,
SCIP_VAR **  vars,
int *  durations,
int *  demands,
int  capacity,
int *  hmin,
int *  hmax,
int *  split 
)
static

computes for the given cumulative condition the effective horizon

Parameters
scipSCIP data structure
nvarsnumber of variables (jobs)
varsarray of integer variable which corresponds to starting times for a job
durationsarray containing corresponding durations
demandsarray containing corresponding demands
capacityavailable cumulative capacity
hminpointer to store the left bound of the effective horizon
hmaxpointer to store the right bound of the effective horizon
splitpoint were the cumulative condition can be split

Definition at line 9627 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 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

creates and adds a cumulative constraint

Parameters
scipSCIP data structure
namename of constraint
nvarsnumber of variables (jobs)
varsarray of integer variable which corresponds to starting times for a job
durationsarray containing corresponding durations
demandsarray containing corresponding demands
capacityavailable cumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiableis constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are seperated as constraints.
removableshould 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'.
stickingatnodeshould 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 9707 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 SCIP_RETCODE computeEffectiveHorizon ( SCIP scip,
SCIP_CONS cons,
int *  ndelconss,
int *  naddconss,
int *  nchgsides 
)
static

computes the effective horizon and checks if the constraint can be decompsed

Parameters
scipSCIP data structure
conscumulative constraint
ndelconsspointer to store the number of deleted constraints
naddconsspointer to store the number of added constraints
nchgsidespointer to store the number of changed sides

Definition at line 9761 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 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

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
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
downlocksarray to store if the variable has a down lock, or NULL
uplocksarray to store if the variable has an up lock, or NULL
consunderlying constraint, or NULL
irrelevantsarray mark those variables which are irrelevant for the cumulative condition
nfixedvarspointer to store the number of fixed variables
nchgsidespointer to store the number of changed sides
cutoffbuffer to store whether a cutoff is detected

Definition at line 9865 of file cons_cumulative.c.

References applyProbingVar(), CONSHDLR_NAME, FALSE, fixIntegerVariableLb(), MAX, MIN, 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 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

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
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
downlocksarray to store if the variable has a down lock, or NULL
uplocksarray to store if the variable has an up lock, or NULL
consunderlying constraint, or NULL
irrelevantsarray mark those variables which are irrelevant for the cumulative condition
nfixedvarspointer to counter which is increased by the number of deduced variable fixations
nchgsidespointer to store the number of changed sides
cutoffbuffer to store whether a cutoff is detected

Definition at line 10150 of file cons_cumulative.c.

References applyProbingVar(), CONSHDLR_NAME, FALSE, fixIntegerVariableUb(), MAX, MIN, 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 SCIP_RETCODE presolveConsEffectiveHorizon ( SCIP scip,
SCIP_CONS cons,
int *  nfixedvars,
int *  nchgcoefs,
int *  nchgsides,
SCIP_Bool cutoff 
)
static

presolve cumulative constraint w.r.t. the boundary of the effective horizon

Parameters
scipSCIP data structure
conscumulative constraint
nfixedvarspointer to store the number of fixed variables
nchgcoefspointer to store the number of changed coefficients
nchgsidespointer to store the number of changed sides
cutoffpointer to store if a cutoff was detected

Definition at line 10402 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 SCIP_RETCODE collectDemands ( SCIP scip,
SCIP_CONSDATA consdata,
int *  startindices,
int  curtime,
int  nstarted,
int  nfinished,
SCIP_Longint **  demands,
int *  ndemands 
)
static

stores all demands which are smaller than the capacity of those jobs that are running at 'curtime'

Parameters
scipSCIP data structure
consdataconstraint data
startindicespermutation with rspect to the start times
curtimecurrent point in time
nstartednumber of jobs that start before the curtime or at curtime
nfinishednumber of jobs that finished before curtime or at curtime
demandspointer to array storing the demands
ndemandspointer to store the number of different demands

Definition at line 10483 of file cons_cumulative.c.

References getHighestCapacityUsage(), NULL, SCIP_OKAY, SCIPconvertRealToInt(), and SCIPvarGetUbGlobal().

Referenced by getHighestCapacityUsage(), and presolveConsEffectiveHorizon().

◆ getHighestCapacityUsage()

static SCIP_RETCODE getHighestCapacityUsage ( SCIP scip,
SCIP_CONS cons,
int *  startindices,
int  curtime,
int  nstarted,
int  nfinished,
int *  bestcapacity 
)
static

this method creates a row for time point curtime which insures the capacity restriction of the cumulative constraint

Parameters
scipSCIP data structure
consconstraint to be checked
startindicespermutation with rspect to the start times
curtimecurrent point in time
nstartednumber of jobs that start before the curtime or at curtime
nfinishednumber of jobs that finished before curtime or at curtime
bestcapacitypointer to store the maximum possible capacity usage

Definition at line 10542 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 SCIP_RETCODE tightenCapacity ( SCIP scip,
SCIP_CONS cons,
int *  nchgcoefs,
int *  nchgsides 
)
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
scipSCIP data structure
conscumulative constraint
nchgcoefspointer to count total number of changed coefficients
nchgsidespointer to store the number of changed sides

Definition at line 10603 of file cons_cumulative.c.

References addEndingJobDemands(), createSortedEventpoints(), FALSE, getHighestCapacityUsage(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPdebug, SCIPdebugMsg, SCIPdebugMsgPrint, SCIPfreeBufferArray, subtractStartingJobDemands(), and tightenCoefs().

Referenced by getHighestCapacityUsage(), and presolveCons().

◆ tightenCoefs()

static SCIP_RETCODE tightenCoefs ( SCIP scip,
SCIP_CONS cons,
int *  nchgcoefs 
)
static

tries to change coefficients: demand_j < cap && all other parallel jobs in conflict ==> set demand_j := cap

Parameters
scipSCIP data structure
conscumulative constraint
nchgcoefspointer to count total number of changed coefficients

Definition at line 10748 of file cons_cumulative.c.

References createDisjuctiveCons(), FALSE, MIN, 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 SCIP_RETCODE createDisjuctiveCons ( SCIP scip,
SCIP_CONS cons,
int *  naddconss 
)
static

creare a disjunctive constraint which contains all jobs which cannot run in parallel

Parameters
scipSCIP data structure
conscumulative constraint
naddconsspointer to store the number of added constraints

Definition at line 10950 of file cons_cumulative.c.

References createConsCumulative(), FALSE, MIN, NULL, presolveCons(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPfreeBufferArray, and TRUE.

Referenced by SCIP_DECL_CONSPRESOL(), and tightenCoefs().

◆ presolveCons()

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 
)
static

presolve given constraint

Parameters
scipSCIP data structure
conscumulative constraint
conshdlrdataconstraint handler data
presoltimingtiming of presolving call
nfixedvarspointer to store the number of fixed variables
nchgbdspointer to store the number of changed bounds
ndelconsspointer to store the number of deleted constraints
naddconsspointer to store the number of added constraints
nchgcoefspointer to store the number of changed coefficients
nchgsidespointer to store the number of changed sides
cutoffpointer to store if a cutoff was detected
unboundedpointer to store if the problem is unbounded

Definition at line 11033 of file cons_cumulative.c.

References checkDemands(), computeEffectiveHorizon(), deleteTrivilCons(), nnodes, normalizeDemands(), presolveConsEffectiveHorizon(), removeOversizedJobs(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIPallowDualReds(), SCIPconsIsDeleted(), solveIndependentCons(), TCLIQUE_GETNNODES(), tightenCapacity(), and tightenCoefs().

Referenced by createDisjuctiveCons(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().

◆ TCLIQUE_GETNNODES()

static TCLIQUE_GETNNODES ( tcliqueGetnnodesClique  )
static

gets number of nodes in the graph

Definition at line 11138 of file cons_cumulative.c.

References NULL, and TCLIQUE_GETWEIGHTS().

Referenced by presolveCons().

◆ TCLIQUE_GETWEIGHTS()

static TCLIQUE_GETWEIGHTS ( tcliqueGetweightsClique  )
static

gets weight of nodes in the graph

Definition at line 11147 of file cons_cumulative.c.

References NULL, and TCLIQUE_ISEDGE().

Referenced by TCLIQUE_GETNNODES().

◆ TCLIQUE_ISEDGE()

static TCLIQUE_ISEDGE ( tcliqueIsedgeClique  )
static

returns, whether the edge (node1, node2) is in the graph

Definition at line 11156 of file cons_cumulative.c.

References FALSE, nnodes, NULL, TCLIQUE_SELECTADJNODES(), and TRUE.

Referenced by TCLIQUE_GETWEIGHTS().

◆ TCLIQUE_SELECTADJNODES()

static TCLIQUE_SELECTADJNODES ( tcliqueSelectadjnodesClique  )
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 11177 of file cons_cumulative.c.

References nnodes, NULL, and TCLIQUE_NEWSOL().

Referenced by TCLIQUE_ISEDGE().

◆ TCLIQUE_NEWSOL()

static TCLIQUE_NEWSOL ( tcliqueNewsolClique  )
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 11211 of file cons_cumulative.c.

References impliesVlbPrecedenceCondition(), nnodes, NULL, SCIP_Bool, SCIPdebugMessage, and SCIPinfoMessage().

Referenced by TCLIQUE_SELECTADJNODES().

◆ impliesVlbPrecedenceCondition()

static SCIP_Bool impliesVlbPrecedenceCondition ( SCIP scip,
SCIP_VAR vlbvar,
SCIP_Real  vlbcoef,
SCIP_Real  vlbconst,
int  duration 
)
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
scipSCIP data structure
vlbvarvariable which bounds the variable from below
vlbcoefvariable bound coefficient
vlbconstvariable bound constant
durationduration of the variable bound variable

Definition at line 11249 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 SCIP_Bool impliesVubPrecedenceCondition ( SCIP scip,
SCIP_VAR var,
SCIP_Real  vubcoef,
SCIP_Real  vubconst,
int  duration 
)
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
scipSCIP data structure
varvariable which is bound from above
vubcoefvariable bound coefficient
vubconstvariable bound constant
durationduration of the variable which is bounded from above

Definition at line 11304 of file cons_cumulative.c.

References getNodeIdx(), impliesVlbPrecedenceCondition(), and SCIP_Real.

Referenced by impliesVlbPrecedenceCondition(), and projectVbd().

◆ getNodeIdx()

static SCIP_RETCODE getNodeIdx ( SCIP scip,
TCLIQUE_GRAPH tcliquegraph,
SCIP_VAR var,
int *  idx 
)
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
scipSCIP data structure
tcliquegraphincompatibility graph
varvariable for which we want the index
idxpointer to store the index

Definition at line 11326 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 SCIP_RETCODE projectVbd ( SCIP scip,
TCLIQUE_GRAPH tcliquegraph 
)
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
scipSCIP data structure
tcliquegraphincompatibility graph

Definition at line 11417 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 void transitiveClosure ( SCIP_Bool **  adjmatrix,
int *  ninarcs,
int *  noutarcs,
int  nnodes 
)
static

compute the transitive closer of the given graph and the number of in and out arcs

Parameters
adjmatrixadjacent matrix
ninarcsarray to store the number of in arcs
noutarcsarray to store the number of out arcs
nnodesnumber if nodes

Definition at line 11512 of file cons_cumulative.c.

References constraintNonOverlappingGraph(), nnodes, and TRUE.

Referenced by constructIncompatibilityGraph(), and projectVbd().

◆ constraintNonOverlappingGraph()

static SCIP_RETCODE constraintNonOverlappingGraph ( SCIP scip,
TCLIQUE_GRAPH tcliquegraph,
SCIP_CONS **  conss,
int  nconss 
)
static

constructs a non-overlapping graph w.r.t. given durations and available cumulative constraints

Parameters
scipSCIP data structure
tcliquegraphincompatibility graph
conssarray of cumulative constraints
nconssnumber of cumulative constraints

Definition at line 11544 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 SCIP_RETCODE constructIncompatibilityGraph ( SCIP scip,
TCLIQUE_GRAPH tcliquegraph,
SCIP_CONS **  conss,
int  nconss 
)
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
scipSCIP data structure
tcliquegraphincompatibility graph
conssarray of cumulative constraints
nconssnumber of cumulative constraints

Definition at line 11639 of file cons_cumulative.c.

References constraintNonOverlappingGraph(), createCumulativeCons(), NULL, projectVbd(), SCIP_CALL, SCIP_OKAY, and transitiveClosure().

Referenced by constraintNonOverlappingGraph(), and detectRedundantConss().

◆ createCumulativeCons()

static SCIP_RETCODE createCumulativeCons ( SCIP scip,
const char *  name,
TCLIQUE_GRAPH tcliquegraph,
int *  cliquenodes,
int  ncliquenodes 
)
static

create cumulative constraint from conflict set

Parameters
scipSCIP data structure
nameconstraint name
tcliquegraphconflict set graph
cliquenodesarray storing the indecies of the nodes belonging to the clique
ncliquenodesnumber of nodes in the clique

Definition at line 11663 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 SCIP_RETCODE findCumulativeConss ( SCIP scip,
TCLIQUE_GRAPH tcliquegraph,
int *  naddconss 
)
static

◆ createPrecedenceCons()

static SCIP_RETCODE createPrecedenceCons ( SCIP scip,
const char *  name,
SCIP_VAR var,
SCIP_VAR vbdvar,
int  distance 
)
static

create precedence constraint (as variable bound constraint

Parameters
scipSCIP data structure
nameconstraint name
varvariable x that has variable bound
vbdvarbinary, integer or implicit integer bounding variable y
distanceminimum distance between the start time of the job corresponding to var and the job corresponding to vbdvar

Definition at line 11837 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 SCIP_RETCODE computeMinDistance ( SCIP scip,
TCLIQUE_GRAPH tcliquegraph,
int  source,
int  sink,
int *  naddconss 
)
static

compute a minimum distance between the start times of the two given jobs and post it as variable bound constraint

Parameters
scipSCIP data structure
tcliquegraphconflict set graph
sourceindex of the source node
sinkindex of the sink node
naddconsspointer to store the number of added constraints

Definition at line 11862 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 SCIP_RETCODE findPrecedenceConss ( SCIP scip,
TCLIQUE_GRAPH tcliquegraph,
int *  naddconss 
)
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
scipSCIP data structure
tcliquegraphconflict set graph
naddconsspointer to store the number of added constraints

Definition at line 11963 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 SCIP_RETCODE initializeDurations ( SCIP scip,
TCLIQUE_GRAPH tcliquegraph,
SCIP_CONS **  conss,
int  nconss 
)
static

initialize the assumed durations for each variable

Parameters
scipSCIP data structure
tcliquegraphthe incompatibility graph
consscumulative constraints
nconssnumber of cumulative constraints

Definition at line 12031 of file cons_cumulative.c.

References createTcliqueGraph(), getNodeIdx(), MAX, NULL, SCIP_CALL, SCIP_OKAY, and SCIPconsGetData().

Referenced by detectRedundantConss(), and findPrecedenceConss().

◆ createTcliqueGraph()

static SCIP_RETCODE createTcliqueGraph ( SCIP scip,
TCLIQUE_GRAPH **  tcliquegraph 
)
static

create tclique graph

Parameters
scipSCIP data structure
tcliquegraphreference to the incompatibility graph

Definition at line 12075 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 void freeTcliqueGraph ( SCIP scip,
TCLIQUE_GRAPH **  tcliquegraph 
)
static

frees the tclique graph

Parameters
scipSCIP data structure
tcliquegraphreference to the incompatibility graph

Definition at line 12156 of file cons_cumulative.c.

References detectRedundantConss(), SCIPfreeBuffer, SCIPfreeBufferArray, and SCIPhashmapFree().

Referenced by createTcliqueGraph(), and detectRedundantConss().

◆ detectRedundantConss()

static SCIP_RETCODE detectRedundantConss ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_CONS **  conss,
int  nconss,
int *  naddconss 
)
static

construct an incompatibility graph and search for precedence constraints (variables bounds) and unary cumulative constrains (disjunctive constraint)

Parameters
scipSCIP data structure
conshdlrdataconstraint handler data
conssarray of cumulative constraints
nconssnumber of cumulative constraints
naddconsspointer to store the number of added constraints

Definition at line 12185 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 void consdataCalcSignature ( SCIP_CONSDATA consdata)
static

compute the constraint signature which is used to detect constraints which contain potentially the same set of variables

Parameters
consdatacumulative constraint data

Definition at line 12224 of file cons_cumulative.c.

References SCIP_DECL_SORTINDCOMP(), SCIPvarGetIndex(), and TRUE.

Referenced by detectRedundantConss(), and removeRedundantConss().

◆ SCIP_DECL_SORTINDCOMP()

static SCIP_DECL_SORTINDCOMP ( consdataCompVar  )
static

index comparison method of linear constraints: compares two indices of the variable set in the linear constraint

Definition at line 12248 of file cons_cumulative.c.

References NULL, removeRedundantConss(), and SCIPvarCompare().

Referenced by consdataCalcSignature().

◆ removeRedundantConss()

static SCIP_RETCODE removeRedundantConss ( SCIP scip,
SCIP_CONS **  conss,
int  nconss,
int *  ndelconss 
)
static

run a pairwise comparison

Parameters
scipSCIP data structure
conssarray of cumulative constraints
nconssnumber of cumulative constraints
ndelconsspointer to store the number of deletedconstraints

Definition at line 12261 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 SCIP_RETCODE strengthenVarbounds ( SCIP scip,
SCIP_CONS cons,
int *  nchgbds,
int *  naddconss 
)
static

strengthen the variable bounds using the cumulative condition

Parameters
scipSCIP data structure
consconstraint to propagate
nchgbdspointer to store the number of changed bounds
naddconsspointer to store the number of added constraints

Definition at line 12402 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 SCIP_RETCODE enforceConstraint ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS **  conss,
int  nconss,
int  nusefulconss,
SCIP_SOL sol,
SCIP_Bool  solinfeasible,
SCIP_RESULT result 
)
static

helper function to enforce constraints

Parameters
scipSCIP data structure
conshdlrconstraint handler
conssconstraints to process
nconssnumber of constraints
nusefulconssnumber of useful (non-obsolete) constraints to process
solsolution to enforce (NULL for the LP solution)
solinfeasiblewas the solution already declared infeasible by a constraint handler?
resultpointer to store the result of the enforcing call

Definition at line 12498 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 SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyCumulative  )
static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 12602 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 SCIP_DECL_CONSFREE ( consFreeCumulative  )
static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 12620 of file cons_cumulative.c.

References CONSHDLR_NAME, conshdlrdataFree(), NULL, SCIP_DECL_CONSINITPRE(), SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconshdlrSetData(), and SCIPstatisticPrintf.

Referenced by SCIP_DECL_CONSHDLRCOPY().

◆ SCIP_DECL_CONSINITPRE()

static SCIP_DECL_CONSINITPRE ( consInitpreCumulative  )
static

presolving initialization method of constraint handler (called when presolving is about to begin)

Definition at line 12653 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 SCIP_DECL_CONSEXITSOL ( consExitsolCumulative  )
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 12715 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 SCIP_DECL_CONSDELETE ( consDeleteCumulative  )
static

◆ SCIP_DECL_CONSTRANS()

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpCumulative  )
static

◆ SCIP_DECL_CONSSEPALP()

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolCumulative  )
static

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpCumulative  )
static

constraint enforcing method of constraint handler for LP solutions

Definition at line 12967 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 SCIP_DECL_CONSENFORELAX ( consEnforelaxCumulative  )
static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 12976 of file cons_cumulative.c.

References enforceConstraint(), SCIP_CALL, SCIP_DECL_CONSENFOPS(), and SCIP_OKAY.

Referenced by SCIP_DECL_CONSENFOLP().

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsCumulative  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 12985 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 SCIP_DECL_CONSCHECK ( consCheckCumulative  )
static

feasibility check method of constraint handler for integral solutions

Definition at line 13014 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()

◆ SCIP_DECL_CONSPRESOL()

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropCumulative  )
static

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockCumulative  )
static

variable rounding lock method of constraint handler

Definition at line 13285 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 SCIP_DECL_CONSPRINT ( consPrintCumulative  )
static

constraint display method of constraint handler

Definition at line 13326 of file cons_cumulative.c.

References consdataPrint(), NULL, SCIP_DECL_CONSCOPY(), SCIP_OKAY, and SCIPconsGetData().

Referenced by SCIP_DECL_CONSLOCK().

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopyCumulative  )
static

◆ SCIP_DECL_CONSPARSE()

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsCumulative  )
static

constraint method of constraint handler which returns the variables (if possible)

Definition at line 13500 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 SCIP_DECL_CONSGETNVARS ( consGetNVarsCumulative  )
static

constraint method of constraint handler which returns the number of variables (if possible)

Definition at line 13522 of file cons_cumulative.c.

References NULL, SCIP_DECL_EVENTEXEC(), SCIP_OKAY, SCIPconsGetData(), and TRUE.

Referenced by SCIP_DECL_CONSGETVARS().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecCumulative  )
static

execution method of event handler

Definition at line 13545 of file cons_cumulative.c.

References EVENTHDLR_NAME, FALSE, NULL, SCIP_OKAY, SCIPeventhdlrGetName(), and SCIPincludeConshdlrCumulative().

Referenced by SCIP_DECL_CONSGETNVARS().