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)
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)
Miscellaneous Methods
static SCIP_Longint	computeCoreWithInterval (int begin, int end, int ect, int lst)
static SCIP_RETCODE	computeImpliedEst (SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *addedvars, int *est)
static SCIP_RETCODE	computeImpliedLct (SCIP *scip, SCIP_VAR *var, int duration, SCIP_HASHMAP *addedvars, int *lct)
static SCIP_RETCODE	collectBinaryVars (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR ***vars, int **coefs, int *nvars, int *startindices, int curtime, int nstarted, int nfinished)
static SCIP_RETCODE	collectIntVars (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR ***activevars, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool lower, int *lhs)
static void	createSortedEventpoints (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *starttimes, int *endtimes, int *startindices, int *endindices, SCIP_Bool local)
static void	createSortedEventpointsSol (SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *starttimes, int *endtimes, int *startindices, int *endindices)
static void	createSelectedSortedEventpointsSol (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, int *starttimes, int *endtimes, int *startindices, int *endindices, int *nvars, SCIP_Bool lower)
static SCIP_RETCODE	getActiveVar (SCIP *scip, SCIP_VAR **var, int *scalar, int *constant)
static SCIP_Longint	computeTotalEnergy (int *durations, int *demands, int njobs)
Default method to solve a cumulative condition
static SCIP_RETCODE	setupAndSolveCumulativeSubscip (SCIP *subscip, SCIP_Real *objvals, int *durations, int *demands, int njobs, int capacity, int hmin, int hmax, SCIP_Longint maxnodes, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *solved, SCIP_Bool *error)
static	SCIP_DECL_SOLVECUMULATIVE (solveCumulativeViaScipCp)
Constraint handler data
Method used to create and free the constraint handler data when including and removing the cumulative constraint handler.
static SCIP_RETCODE	conshdlrdataCreate (SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
static void	conshdlrdataFree (SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
Constraint data methods
static SCIP_RETCODE	consdataCatchEvents (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
static SCIP_RETCODE	consdataDropEvents (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
static SCIP_RETCODE	consdataDropAllEvents (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
static void	initializeLocks (SCIP_CONSDATA *consdata, SCIP_Bool locked)
static SCIP_RETCODE	consdataCreate (SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR **vars, SCIP_CONS **linkingconss, int *durations, int *demands, int nvars, int capacity, int hmin, int hmax, SCIP_Bool check)
static SCIP_RETCODE	consdataFreeRows (SCIP *scip, SCIP_CONSDATA **consdata)
static SCIP_RETCODE	consdataFree (SCIP *scip, SCIP_CONSDATA **consdata)
static void	consdataPrint (SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
static SCIP_RETCODE	consdataDeletePos (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_CONS *cons, int pos)
static SCIP_RETCODE	consdataCollectLinkingCons (SCIP *scip, SCIP_CONSDATA *consdata)
Check methods
static SCIP_RETCODE	checkCumulativeCondition (SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *violated, SCIP_CONS *cons, SCIP_Bool printreason)
static SCIP_RETCODE	checkCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *violated, SCIP_Bool printreason)
Conflict analysis
static SCIP_RETCODE	resolvePropagationCoretimes (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferdemand, int inferpeak, int relaxedpeak, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool usebdwidening, int *provedpeak, SCIP_Bool *explanation)
static int	computeOverlap (int begin, int end, int est, int lst, int duration)
static SCIP_RETCODE	analyzeEnergyRequirement (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int begin, int end, SCIP_VAR *infervar, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool usebdwidening, SCIP_Bool *explanation)
static SCIP_RETCODE	respropCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, INFERINFO inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool usebdwidening, SCIP_Bool *explanation, SCIP_RESULT *result)
Enforcement methods
static SCIP_RETCODE	applyAlternativeBoundsBranching (SCIP *scip, SCIP_VAR **vars, int nvars, int *alternativelbs, int *alternativeubs, int *downlocks, int *uplocks, SCIP_Bool *branched)
static void	subtractStartingJobDemands (SCIP_CONSDATA *consdata, int curtime, int *starttimes, int *startindices, int *freecapacity, int *idx, int nvars)
static void	addEndingJobDemands (SCIP_CONSDATA *consdata, int curtime, int *endtimes, int *endindices, int *freecapacity, int *idx, int nvars)
static SCIP_RETCODE	computePeak (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, int *timepoint)
static SCIP_RETCODE	collectBranchingCands (SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, int *nbranchcands)
static SCIP_RETCODE	enforceSolution (SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_Bool branch, SCIP_RESULT *result)
Linear relaxations
static SCIP_RETCODE	createCoverCutsTimepoint (SCIP *scip, SCIP_CONS *cons, int *startvalues, int time)
static SCIP_RETCODE	createCoverCuts (SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE	createCapacityRestriction (SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool cutsasconss)
static SCIP_RETCODE	consCapacityConstraintsFinder (SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss)
static SCIP_RETCODE	createRelaxation (SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss)
static SCIP_RETCODE	addRelaxation (SCIP *scip, SCIP_CONS *cons, SCIP_Bool cutsasconss, SCIP_Bool *infeasible)
static SCIP_RETCODE	separateConsBinaryRepresentation (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff)
static SCIP_RETCODE	separateCoverCutsCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff)
static SCIP_RETCODE	createCapacityRestrictionIntvars (SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Bool lower, SCIP_Bool *cutoff)
static SCIP_RETCODE	separateConsOnIntegerVariables (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool lower, SCIP_Bool *separated, SCIP_Bool *cutoff)
Presolving
static SCIP_Bool	checkDemands (SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE	deleteTrivilCons (SCIP *scip, SCIP_CONS *cons, int *ndelconss, SCIP_Bool *cutoff)
static SCIP_RETCODE	removeIrrelevantJobs (SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE	adjustOversizedJobBounds (SCIP *scip, SCIP_CONSDATA *consdata, int pos, int *nchgbds, int *naddconss, SCIP_Bool *cutoff)
static SCIP_RETCODE	removeOversizedJobs (SCIP *scip, SCIP_CONS *cons, int *nchgbds, int *nchgcoefs, int *naddconss, SCIP_Bool *cutoff)
static SCIP_RETCODE	fixIntegerVariableUb (SCIP *scip, SCIP_VAR *var, SCIP_Bool uplock, int *nfixedvars)
static SCIP_RETCODE	fixIntegerVariableLb (SCIP *scip, SCIP_VAR *var, SCIP_Bool downlock, int *nfixedvars)
static void	normalizeCumulativeCondition (SCIP *scip, int nvars, int *demands, int *capacity, int *nchgcoefs, int *nchgsides)
static void	normalizeDemands (SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides)
static SCIP_RETCODE	computeEffectiveHorizonCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *hmin, int *hmax, int *split)
static SCIP_RETCODE	createConsCumulative (SCIP *scip, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
static SCIP_RETCODE	computeEffectiveHorizon (SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss, int *nchgsides)
static SCIP_RETCODE	presolveConsEst (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff)
static SCIP_RETCODE	presolveConsLct (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff)
static SCIP_RETCODE	presolveConsEffectiveHorizon (SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *nchgcoefs, int *nchgsides, SCIP_Bool *cutoff)
static void	collectDemands (SCIP *scip, SCIP_CONSDATA *consdata, int *startindices, int curtime, int nstarted, int nfinished, SCIP_Longint **demands, int *ndemands)
static SCIP_RETCODE	getHighestCapacityUsage (SCIP *scip, SCIP_CONS *cons, int *startindices, int curtime, int nstarted, int nfinished, int *bestcapacity)
static SCIP_RETCODE	tightenCapacity (SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgsides)
static SCIP_RETCODE	tightenCoefs (SCIP *scip, SCIP_CONS *cons, int *nchgcoefs)
static SCIP_RETCODE	createDisjuctiveCons (SCIP *scip, SCIP_CONS *cons, int *naddconss)
static SCIP_RETCODE	presolveCons (SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_PRESOLTIMING presoltiming, int *nfixedvars, int *nchgbds, int *ndelconss, int *naddconss, int *nchgcoefs, int *nchgsides, SCIP_Bool *cutoff, SCIP_Bool *unbounded)
TClique Graph callbacks
static	TCLIQUE_GETNNODES (tcliqueGetnnodesClique)
static	TCLIQUE_GETWEIGHTS (tcliqueGetweightsClique)
static	TCLIQUE_ISEDGE (tcliqueIsedgeClique)
static	TCLIQUE_SELECTADJNODES (tcliqueSelectadjnodesClique)
static	TCLIQUE_NEWSOL (tcliqueNewsolClique)
Callback methods of constraint handler
static	SCIP_DECL_CONSHDLRCOPY (conshdlrCopyCumulative)
static	SCIP_DECL_CONSFREE (consFreeCumulative)
static	SCIP_DECL_CONSINITPRE (consInitpreCumulative)
static	SCIP_DECL_CONSEXITSOL (consExitsolCumulative)
static	SCIP_DECL_CONSDELETE (consDeleteCumulative)
static	SCIP_DECL_CONSTRANS (consTransCumulative)
static	SCIP_DECL_CONSINITLP (consInitlpCumulative)
static	SCIP_DECL_CONSSEPALP (consSepalpCumulative)
static	SCIP_DECL_CONSSEPASOL (consSepasolCumulative)
static	SCIP_DECL_CONSENFOLP (consEnfolpCumulative)
static	SCIP_DECL_CONSENFORELAX (consEnforelaxCumulative)
static	SCIP_DECL_CONSENFOPS (consEnfopsCumulative)
static	SCIP_DECL_CONSCHECK (consCheckCumulative)
static	SCIP_DECL_CONSPROP (consPropCumulative)
static	SCIP_DECL_CONSPRESOL (consPresolCumulative)
static	SCIP_DECL_CONSRESPROP (consRespropCumulative)
static	SCIP_DECL_CONSLOCK (consLockCumulative)
static	SCIP_DECL_CONSPRINT (consPrintCumulative)
static	SCIP_DECL_CONSCOPY (consCopyCumulative)
static	SCIP_DECL_CONSPARSE (consParseCumulative)
static	SCIP_DECL_CONSGETVARS (consGetVarsCumulative)
static	SCIP_DECL_CONSGETNVARS (consGetNVarsCumulative)
Callback methods of event handler
static	SCIP_DECL_EVENTEXEC (eventExecCumulative)

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_INVALID = 0 ,   PROPRULE_1 = 1 ,   PROPRULE_2 = 2 ,   PROPRULE_3 = 3 ,   PROPRULE_4 = 4 ,   PROPRULE_0_INVALID = 0 ,   PROPRULE_1_CORETIMES = 1 ,   PROPRULE_2_EDGEFINDING = 2 ,   PROPRULE_3_TTEF = 3 ,   PROPRULE_1_RHS = 1 ,   PROPRULE_1_LHS = 2 ,   PROPRULE_1_RANGEDROW = 3 ,   PROPRULE_INVALID = 0 ,   PROPRULE_1 = 0 ,   PROPRULE_2 = 1 ,   PROPRULE_3 = 2 ,   PROPRULE_4 = 3 ,   PROPRULE_INVALID = 4 ,   PROPRULE_1 ,   PROPRULE_2 ,   PROPRULE_3 ,   PROPRULE_4 ,   PROPRULE_0 ,   PROPRULE_1 ,   PROPRULE_INTLB ,   PROPRULE_INTUB ,   PROPRULE_INVALID }
typedef enum Proprule	PROPRULE
typedef struct InferInfo	INFERINFO
static INFERINFO	intToInferInfo (int i)
static int	inferInfoToInt (INFERINFO inferinfo)
static PROPRULE	inferInfoGetProprule (INFERINFO inferinfo)
static int	inferInfoGetData1 (INFERINFO inferinfo)
static int	inferInfoGetData2 (INFERINFO inferinfo)
static SCIP_Bool	inferInfoIsValid (INFERINFO inferinfo)
static INFERINFO	getInferInfo (PROPRULE proprule, int data1, int data2)

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

Macro Definition Documentation

CONSHDLR_NAME

#define CONSHDLR_NAME   "cumulative"

Definition at line 68 of file cons_cumulative.c.

CONSHDLR_DESC

#define CONSHDLR_DESC   "cumulative constraint handler"

Definition at line 69 of file cons_cumulative.c.

CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   2100000

priority of the constraint handler for separation

Definition at line 70 of file cons_cumulative.c.

CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   -2040000

priority of the constraint handler for constraint enforcing

Definition at line 71 of file cons_cumulative.c.

CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -3030000

priority of the constraint handler for checking feasibility

Definition at line 72 of file cons_cumulative.c.

CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ   1

frequency for separating cuts; zero means to separate only in the root node

Definition at line 73 of file cons_cumulative.c.

CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 74 of file cons_cumulative.c.

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 76 of file cons_cumulative.c.

CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS   -1

maximal number of presolving rounds the constraint handler participates in (-1: no limit)

Definition at line 77 of file cons_cumulative.c.

CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 78 of file cons_cumulative.c.

CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 79 of file cons_cumulative.c.

CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   TRUE

should the constraint handler be skipped, if no constraints are available?

Definition at line 80 of file cons_cumulative.c.

CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_ALWAYS

Definition at line 82 of file cons_cumulative.c.

CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 83 of file cons_cumulative.c.

DEFAULT_USEBINVARS

#define DEFAULT_USEBINVARS   FALSE

should the binary representation be used?

Definition at line 95 of file cons_cumulative.c.

DEFAULT_LOCALCUTS

#define DEFAULT_LOCALCUTS   FALSE

should cuts be added only locally?

Definition at line 96 of file cons_cumulative.c.

DEFAULT_USECOVERCUTS

#define DEFAULT_USECOVERCUTS   TRUE

should covering cuts be added?

Definition at line 97 of file cons_cumulative.c.

DEFAULT_CUTSASCONSS

#define DEFAULT_CUTSASCONSS   TRUE

should the cuts be created as knapsack constraints?

Definition at line 98 of file cons_cumulative.c.

DEFAULT_SEPAOLD

#define DEFAULT_SEPAOLD   TRUE

shall old sepa algo be applied?

Definition at line 99 of file cons_cumulative.c.

DEFAULT_TTINFER

#define DEFAULT_TTINFER   TRUE

should time-table (core-times) propagator be used to infer bounds?

Definition at line 102 of file cons_cumulative.c.

DEFAULT_EFCHECK

#define DEFAULT_EFCHECK   FALSE

should edge-finding be used to detect an overload?

Definition at line 103 of file cons_cumulative.c.

DEFAULT_EFINFER

#define DEFAULT_EFINFER   FALSE

should edge-finding be used to infer bounds?

Definition at line 104 of file cons_cumulative.c.

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 105 of file cons_cumulative.c.

DEFAULT_TTEFCHECK

#define DEFAULT_TTEFCHECK   TRUE

should time-table edge-finding be used to detect an overload?

Definition at line 106 of file cons_cumulative.c.

DEFAULT_TTEFINFER

#define DEFAULT_TTEFINFER   TRUE

should time-table edge-finding be used to infer bounds?

Definition at line 107 of file cons_cumulative.c.

DEFAULT_DUALPRESOLVE

#define DEFAULT_DUALPRESOLVE   TRUE

should dual presolving be applied?

Definition at line 110 of file cons_cumulative.c.

DEFAULT_COEFTIGHTENING

#define DEFAULT_COEFTIGHTENING   FALSE

should coeffisient tightening be applied?

Definition at line 111 of file cons_cumulative.c.

DEFAULT_NORMALIZE

#define DEFAULT_NORMALIZE   TRUE

should demands and capacity be normalized?

Definition at line 112 of file cons_cumulative.c.

DEFAULT_PRESOLPAIRWISE

#define DEFAULT_PRESOLPAIRWISE   TRUE

should pairwise constraint comparison be performed in presolving?

Definition at line 113 of file cons_cumulative.c.

DEFAULT_DISJUNCTIVE

#define DEFAULT_DISJUNCTIVE   TRUE

extract disjunctive constraints?

Definition at line 114 of file cons_cumulative.c.

DEFAULT_DETECTDISJUNCTIVE

#define DEFAULT_DETECTDISJUNCTIVE   TRUE

search for conflict set via maximal cliques to detect disjunctive constraints

Definition at line 115 of file cons_cumulative.c.

DEFAULT_DETECTVARBOUNDS

#define DEFAULT_DETECTVARBOUNDS   TRUE

search for conflict set via maximal cliques to detect variable bound constraints

Definition at line 116 of file cons_cumulative.c.

DEFAULT_MAXNODES

#define DEFAULT_MAXNODES   10000LL

number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit)

Definition at line 117 of file cons_cumulative.c.

DEFAULT_FILLBRANCHCANDS

#define DEFAULT_FILLBRANCHCANDS   FALSE

should branching candidates be added to storage?

Definition at line 120 of file cons_cumulative.c.

DEFAULT_USEBDWIDENING

#define DEFAULT_USEBDWIDENING   TRUE

should bound widening be used during conflict analysis?

Definition at line 123 of file cons_cumulative.c.

EVENTHDLR_NAME

#define EVENTHDLR_NAME   "cumulative"

Definition at line 132 of file cons_cumulative.c.

EVENTHDLR_DESC

#define EVENTHDLR_DESC   "bound change event handler for cumulative constraints"

Definition at line 133 of file cons_cumulative.c.

Typedef Documentation

PROPRULE

typedef enum Proprule PROPRULE

Definition at line 266 of file cons_cumulative.c.

INFERINFO

typedef struct InferInfo INFERINFO

Definition at line 283 of file cons_cumulative.c.

SCIP_NODEDATA

typedef struct SCIP_NodeData SCIP_NODEDATA

Definition at line 5749 of file cons_cumulative.c.

Enumeration Type Documentation

Proprule

enum Proprule

Propagation rules

Enumerator
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_0_INVALID	invalid inference information
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 259 of file cons_cumulative.c.

Function Documentation

intToInferInfo()

static INFERINFO intToInferInfo ( int  i )

static

converts an integer into an inference information

Parameters

i	integer to convert

Definition at line 287 of file cons_cumulative.c.

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

inferInfoToInt()

static int inferInfoToInt ( INFERINFO  inferinfo )

static

converts an inference information into an int

Parameters

inferinfo

inference information to convert

Definition at line 300 of file cons_cumulative.c.

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

inferInfoGetProprule()

static PROPRULE inferInfoGetProprule ( INFERINFO  inferinfo )

static

returns the propagation rule stored in the inference information

Parameters

inferinfo

inference information to convert

Definition at line 309 of file cons_cumulative.c.

Referenced by getInferInfo(), respropCumulativeCondition(), and SCIP_DECL_CONSRESPROP().

inferInfoGetData1()

static int inferInfoGetData1 ( INFERINFO  inferinfo )

static

returns data field one of the inference information

Parameters

inferinfo

inference information to convert

Definition at line 318 of file cons_cumulative.c.

Referenced by propagateTTEF(), and respropCumulativeCondition().

inferInfoGetData2()

static int inferInfoGetData2 ( INFERINFO  inferinfo )

static

returns data field two of the inference information

Parameters

inferinfo

inference information to convert

Definition at line 327 of file cons_cumulative.c.

Referenced by propagateTTEF(), and respropCumulativeCondition().

inferInfoIsValid()

static SCIP_Bool inferInfoIsValid ( INFERINFO  inferinfo )

static

returns whether the inference information is valid

Parameters

inferinfo

inference information to convert

Definition at line 336 of file cons_cumulative.c.

Referenced by coretimesUpdateLb(), coretimesUpdateUb(), getInferInfo(), inferboundsEdgeFinding(), and propagateTTEF().

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

proprule	propagation rule that deduced the value
data1	data field one
data2	data field two

Definition at line 346 of file cons_cumulative.c.

References FALSE, inferInfoGetProprule(), inferInfoIsValid(), PROPRULE_0_INVALID, and TRUE.

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

computeCoreWithInterval()

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

static

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

Parameters

begin	begin of the interval
end	end of the interval
ect	earliest completion time
lst	latest start time

Definition at line 387 of file cons_cumulative.c.

References MAX, and MIN.

Referenced by collectDataTTEF(), 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

scip	SCIP data structure
var	variable for which the implied est should be returned
addedvars	hash map containig the variable which are already added
est	pointer to store the implied earliest start time

Definition at line 406 of file cons_cumulative.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPhashmapGetImage(), SCIPhashmapRemove(), SCIPisEQ(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), and SCIPvarGetVlbVars().

Referenced by 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

scip	SCIP data structure
var	variable for which the implied est should be returned
duration	duration of the given job
addedvars	hash map containig the variable which are already added
lct	pointer to store the implied latest completion time

Definition at line 474 of file cons_cumulative.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPhashmapExists(), SCIPhashmapRemove(), SCIPisEQ(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNVubs(), SCIPvarGetUbLocal(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), and SCIPvarGetVubVars().

Referenced by 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

scip	SCIP data structure
consdata	constraint data
vars	pointer to the array to store the binary variables
coefs	pointer to store the coefficients
nvars	number if collect binary variables
startindices	permutation with rspect to the start times
curtime	current point in time
nstarted	number of jobs that start before the curtime or at curtime
nfinished	number of jobs that finished before curtime or at curtime

Definition at line 538 of file cons_cumulative.c.

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

Referenced by 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

scip	SCIP data structure
consdata	constraint data
activevars	jobs that are currently running
startindices	permutation with rspect to the start times
curtime	current point in time
nstarted	number of jobs that start before the curtime or at curtime
nfinished	number of jobs that finished before curtime or at curtime
lower	shall cuts be created due to lower or upper bounds?
lhs	lhs for the new row sum of lbs + minoffset

Definition at line 636 of file cons_cumulative.c.

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

Referenced by 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

scip	SCIP data structure
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations per start time variable
starttimes	array to store sorted start events
endtimes	array to store sorted end events
startindices	permutation with rspect to the start times
endindices	permutation with rspect to the end times
local	shall local bounds be used

Definition at line 710 of file cons_cumulative.c.

References NULL, SCIPconvertRealToInt(), SCIPsortIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

Referenced by consCapacityConstraintsFinder(), 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

scip	SCIP data structure
sol	solution
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations per start time variable
starttimes	array to store sorted start events
endtimes	array to store sorted end events
startindices	permutation with rspect to the start times
endindices	permutation with rspect to the end times

Definition at line 757 of file cons_cumulative.c.

References NULL, SCIPconvertRealToInt(), SCIPgetSolVal(), and SCIPsortIntInt().

Referenced by computePeak().

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

scip	SCIP data structure
consdata	constraint data
sol	primal CIP solution, NULL for current LP solution
starttimes	array to store sorted start events
endtimes	array to store sorted end events
startindices	permutation with rspect to the start times
endindices	permutation with rspect to the end times
nvars	number of variables that are integral
lower	shall the constraints be derived for lower or upper bounds?

Definition at line 799 of file cons_cumulative.c.

References NULL, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPsortIntInt(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by 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

scip	SCIP data structure
var	pointer to store the active variable
scalar	pointer to store the scalar
constant	pointer to store the constant

Definition at line 1174 of file cons_cumulative.c.

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

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

computeTotalEnergy()

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

static

computes the total energy of all jobs

Parameters

durations	array of job durations
demands	array of job demands
njobs	number of jobs

Definition at line 1219 of file cons_cumulative.c.

References SCIP_Longint.

Referenced by 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

subscip	subscip data structure
objvals	array of objective coefficients for each job (linear objective function), or NULL if none
durations	array of durations
demands	array of demands
njobs	number of jobs (activities)
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
maxnodes	maximum number of branch-and-bound nodes (-1: no limit)
timelimit	time limit for solving in seconds
memorylimit	memory limit for solving in mega bytes (MB)
ests	array of earliest start times for each job
lsts	array of latest start times for each job
infeasible	pointer to store if the subproblem was infeasible
unbounded	pointer to store if the problem is unbounded
solved	pointer to store if the problem is solved (to optimality)
error	pointer to store if an error occurred

Definition at line 1245 of file cons_cumulative.c.

References FALSE, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PARAMEMPHASIS_CPSOLVER, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_DUALLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_PRIMALLIMIT, 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 SCIP_DECL_SOLVECUMULATIVE().

SCIP_DECL_SOLVECUMULATIVE()

static SCIP_DECL_SOLVECUMULATIVE ( solveCumulativeViaScipCp  )

static

solve single cumulative condition using SCIP and a single cumulative constraint

Definition at line 1412 of file cons_cumulative.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPcreate(), SCIPdebugMessage, SCIPfree(), and setupAndSolveCumulativeSubscip().

conshdlrdataCreate()

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

static

creates constaint handler data for cumulative constraint handler

Parameters

scip	SCIP data structure
conshdlrdata	pointer to store the constraint handler data
eventhdlr	event handler

Definition at line 1753 of file cons_cumulative.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.

Referenced by SCIPincludeConshdlrCumulative().

conshdlrdataFree()

static void conshdlrdataFree ( SCIP *  scip, SCIP_CONSHDLRDATA **  conshdlrdata  )

static

frees constraint handler data for logic or constraint handler

Parameters

scip	SCIP data structure
conshdlrdata	pointer to the constraint handler data

Definition at line 1798 of file cons_cumulative.c.

References NULL, and SCIPfreeBlockMemory.

Referenced by 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

scip	SCIP data structure
consdata	cumulative constraint data
eventhdlr	event handler to call for the event processing

Definition at line 1819 of file cons_cumulative.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDTIGHTENED, SCIP_OKAY, and SCIPcatchVarEvent().

Referenced by 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

scip	SCIP data structure
consdata	cumulative constraint data
eventhdlr	event handler to call for the event processing
pos	array position of variable to catch bound change events for

Definition at line 1843 of file cons_cumulative.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDTIGHTENED, SCIP_OKAY, and SCIPdropVarEvent().

Referenced by 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

scip	SCIP data structure
consdata	linear constraint data
eventhdlr	event handler to call for the event processing

Definition at line 1864 of file cons_cumulative.c.

References consdataDropEvents(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by SCIP_DECL_CONSDELETE().

initializeLocks()

static void initializeLocks ( SCIP_CONSDATA *  consdata, SCIP_Bool  locked  )

static

initialize variable lock data structure

Parameters

consdata	constraint data
locked	should the variable be locked?

Definition at line 1886 of file cons_cumulative.c.

Referenced by consdataCreate(), 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

scip	SCIP data structure
consdata	pointer to consdata
vars	array of integer variables
linkingconss	array of linking constraints for the integer variables, or NULL
durations	array containing corresponding durations
demands	array containing corresponding demands
nvars	number of variables
capacity	available cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
check	is the corresponding constraint a check constraint

Definition at line 1906 of file cons_cumulative.c.

References FALSE, initializeLocks(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_INTEGER, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPgetConsLinking(), SCIPgetTransformedVars(), SCIPisTransformed(), SCIPmarkDoNotMultaggrVar(), SCIPstatistic, SCIPtransformConss(), and SCIPvarGetType().

Referenced by 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

scip	SCIP data structure
consdata	constraint data

Definition at line 2036 of file cons_cumulative.c.

References FALSE, NULL, r, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseRow().

Referenced by consdataFree(), and SCIP_DECL_CONSEXITSOL().

consdataFree()

static SCIP_RETCODE consdataFree ( SCIP *  scip, SCIP_CONSDATA **  consdata  )

static

frees a cumulative constraint data

Parameters

scip	SCIP data structure
consdata	pointer to linear constraint data

Definition at line 2087 of file cons_cumulative.c.

References consdataFreeRows(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPreleaseCons().

Referenced by SCIP_DECL_CONSDELETE().

consdataPrint()

static void consdataPrint ( SCIP *  scip, SCIP_CONSDATA *  consdata, FILE *  file  )

static

prints cumulative constraint to file stream

Parameters

scip	SCIP data structure
consdata	cumulative constraint data
file	output file (or NULL for standard output)

Definition at line 2136 of file cons_cumulative.c.

References NULL, SCIPinfoMessage(), SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().

Referenced by 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

scip	SCIP data structure
consdata	cumulative constraint data
cons	knapsack constraint
pos	position of coefficient to delete

Definition at line 2163 of file cons_cumulative.c.

References consdataDropEvents(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsTransformed(), SCIPdebugMsg, SCIPinProbing(), SCIPreleaseCons(), SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().

Referenced by presolveConsEffectiveHorizon(), removeIrrelevantJobs(), and removeOversizedJobs().

consdataCollectLinkingCons()

static SCIP_RETCODE consdataCollectLinkingCons ( SCIP *  scip, SCIP_CONSDATA *  consdata  )

static

collect linking constraints for each integer variable

Parameters

scip	SCIP data structure
consdata	pointer to consdata

Definition at line 2232 of file cons_cumulative.c.

References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPcaptureCons(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPcreateConsLinking(), SCIPdebugMsg, SCIPexistsConsLinking(), SCIPgetConsLinking(), SCIPsnprintf(), SCIPvarGetName(), and TRUE.

Referenced by createRelaxation(), and separateCoverCutsCons().

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

scip	SCIP data structure
sol	primal solution, or NULL for current LP/pseudo solution
nvars	number of variables (jobs)
vars	array of integer variable which corresponds to starting times for a job
durations	array containing corresponding durations
demands	array containing corresponding demands
capacity	available cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
violated	pointer to store if the cumulative condition is violated
cons	constraint which is checked
printreason	should the reason for the violation be printed?

Definition at line 2299 of file cons_cumulative.c.

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

scip	SCIP data structure
cons	constraint to be checked
sol	primal solution, or NULL for current LP/pseudo solution
violated	pointer to store if the constraint is violated
printreason	should the reason for the violation be printed?

Definition at line 2457 of file cons_cumulative.c.

References checkCumulativeCondition(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), and SCIPdebugMsg.

Referenced by 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

scip	SCIP data structure
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
infervar	inference variable
inferdemand	demand of the inference variable
inferpeak	time point which causes the propagation
relaxedpeak	relaxed time point which would be sufficient to be proved
bdchgidx	the index of the bound change, representing the point of time where the change took place
usebdwidening	should bound widening be used during conflict analysis?
provedpeak	pointer to store the actually proved peak, or NULL
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL

Definition at line 2493 of file cons_cumulative.c.

References BMSclearMemoryArray, FALSE, MAX, MIN, NULL, SCIP_Bool, 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(), 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

begin	begin of the times interval
end	end of time interval
est	earliest start time
lst	latest start time
duration	duration of the job

Definition at line 2847 of file cons_cumulative.c.

References MIN3.

Referenced by analyzeEnergyRequirement().

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

scip	SCIP data structure
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	capacity of the cumulative condition
begin	begin of the time window
end	end of the time window
infervar	variable which was propagate, or NULL
boundtype	the type of the changed bound (lower or upper bound)
bdchgidx	the index of the bound change, representing the point of time where the change took place
relaxedbd	the relaxed bound which is sufficient to be explained
usebdwidening	should bound widening be used during conflict analysis?
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL

Definition at line 2884 of file cons_cumulative.c.

References computeOverlap(), FALSE, MIN, MIN3, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, 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 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

scip	SCIP data structure
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
infervar	the conflict variable whose bound change has to be resolved
inferinfo	the user information
boundtype	the type of the changed bound (lower or upper bound)
bdchgidx	the index of the bound change, representing the point of time where the change took place
relaxedbd	the relaxed bound which is sufficient to be explained
usebdwidening	should bound widening be used during conflict analysis?
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
result	pointer to store the result of the propagation conflict resolving call

Definition at line 3171 of file cons_cumulative.c.

References analyzeEnergyRequirement(), FALSE, inferInfoGetData1(), inferInfoGetData2(), inferInfoGetProprule(), MAX, MIN, NULL, PROPRULE_0_INVALID, 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 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

scip	SCIP data structure
vars	array of active variables
nvars	number of active variables
alternativelbs	alternative lower bounds
alternativeubs	alternative lower bounds
downlocks	number of constraints with down lock participating by the computation
uplocks	number of constraints with up lock participating by the computation
branched	pointer to store if a branching was applied

Definition at line 3349 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(), and TRUE.

Referenced by propagateAllConss().

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

consdata	constraint data
curtime	current point in time
starttimes	array of start times
startindices	permutation with respect to the start times
freecapacity	pointer to store the resulting free capacity
idx	pointer to index in start time array
nvars	number of vars in array of starttimes and startindices

Definition at line 3414 of file cons_cumulative.c.

References NULL.

Referenced by 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

consdata	constraint data
curtime	current point in time
endtimes	array of end times
endindices	permutation with rspect to the end times
freecapacity	pointer to store the resulting free capacity
idx	pointer to index in end time array
nvars	number of vars in array of starttimes and startindices

Definition at line 3456 of file cons_cumulative.c.

Referenced by computePeak(), consCapacityConstraintsFinder(), separateConsOnIntegerVariables(), 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

scip	SCIP data structure
consdata	constraint handler data
sol	primal solution, or NULL for current LP/pseudo solution
timepoint	pointer to store the time point of the peak

Definition at line 3485 of file cons_cumulative.c.

References addEndingJobDemands(), createSortedEventpointsSol(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, and subtractStartingJobDemands().

Referenced by 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

scip	SCIP data structure
conss	constraints to be processed
nconss	number of constraints
sol	primal solution, or NULL for current LP/pseudo solution
nbranchcands	pointer to store the number of branching variables

Definition at line 3570 of file cons_cumulative.c.

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

scip	SCIP data structure
conss	constraints to be processed
nconss	number of constraints
sol	solution to enforce (NULL for LP or pseudo solution)
branch	should branching candidates be collected
result	pointer to store the result

Definition at line 3657 of file cons_cumulative.c.

References branch(), checkCons(), collectBranchingCands(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_INFEASIBLE, and SCIP_OKAY.

Referenced by enforceConstraint(), and SCIP_DECL_CONSENFOPS().

isConsIndependently()

static SCIP_Bool isConsIndependently ( SCIP_CONS *  cons )

static

check if cumulative constraint is independently of all other constraints

Parameters

cons	cumulative constraint

Definition at line 3710 of file cons_cumulative.c.

References FALSE, NULL, SCIP_Bool, SCIP_LOCKTYPE_MODEL, SCIPconsGetData(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), and TRUE.

Referenced by 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

scip	SCIP data structure
cons	cumulative constraint
maxnodes	number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit)
nchgbds	pointer to store the number changed variable bounds
nfixedvars	pointer to count number of fixings
ndelconss	pointer to count number of deleted constraints
cutoff	pointer to store if the constraint is infeasible
unbounded	pointer to store if the constraint is unbounded

Definition at line 3749 of file cons_cumulative.c.

References 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 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

scip	SCIP data structure
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
infervar	start time variable which lead to the infeasibilty
inferduration	duration of the start time variable
inferdemand	demand of the start time variable
inferpeak	profile preak which causes the infeasibilty
usebdwidening	should bound widening be used during conflict analysis?
initialized	pointer to store if the conflict analysis was initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL

Definition at line 3964 of file cons_cumulative.c.

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

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

scip	SCIP data structure
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
cons	constraint which is propagated
profile	resource profile
idx	position of the variable to propagate
nchgbds	pointer to store the number of bound changes
usebdwidening	should bound widening be used during conflict analysis?
initialized	was conflict analysis initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
infeasible	pointer to store if the constraint is infeasible

Definition at line 4020 of file cons_cumulative.c.

References analyseInfeasibelCoreInsertion(), CONSHDLR_NAME, getInferInfo(), inferInfoIsValid(), inferInfoToInt(), MIN, NULL, PROPRULE_1_CORETIMES, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPinferVarLbCons(), SCIPprofileFindLeft(), SCIPprofileGetLoad(), SCIPprofileGetNTimepoints(), SCIPprofileGetTime(), SCIPstatistic, SCIPtightenVarLb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by 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

scip	SCIP data structure
var	start time variable to propagate
duration	duration of the job
demand	demand of the job
capacity	cumulative capacity
cons	constraint which is propagated
profile	resource profile
idx	position of the variable to propagate
nchgbds	pointer to store the number of bound changes

Definition at line 4181 of file cons_cumulative.c.

References CONSHDLR_NAME, getInferInfo(), inferInfoIsValid(), 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, SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by propagateTimetable().

computeCoreEnergyAfter()

static void computeCoreEnergyAfter ( 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

profile	core profile
nvars	number of start time variables (activities)
ests	array of sorted earliest start times
lcts	array of sorted latest completion times
coreEnergyAfterEst	array to store the core energy after the earliest start time of each job
coreEnergyAfterLct	array to store the core energy after the latest completion time of each job

Definition at line 4323 of file cons_cumulative.c.

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

Referenced by 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

scip	SCIP data structure
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
permests	array to store the variable positions
ests	array to store earliest start times
permlcts	array to store the variable positions
lcts	array to store latest completion times
ects	array to store earliest completion times of the flexible part of the job
lsts	array to store latest start times of the flexible part of the job
flexenergies	array to store the flexible energies of each job

Definition at line 4391 of file cons_cumulative.c.

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

Referenced by 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, SCIP_Longint  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

scip	SCIP data structure
conshdlrdata	constraint handler data
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
var	variable to be considered for upper bound tightening
duration	duration of the job
demand	demand of the job
est	earliest start time of the job
ect	earliest completion time of the flexible part of the job
lct	latest completion time of the job
begin	begin of the time window under investigation
end	end of the time window under investigation
energy	available energy for the flexible part of the hob within the time window
bestlb	pointer to strope the best lower bound change
inferinfos	pointer to store the inference information which is need for the (best) lower bound change
initialized	was conflict analysis initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoff	pointer to store if the constraint is infeasible

Definition at line 4459 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_Longint, SCIP_OKAY, SCIP_Real, SCIPaddConflictUb(), SCIPconvertRealToInt(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPvarGetUbLocal(), and TRUE.

Referenced by 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, SCIP_Longint  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

scip	SCIP data structure
conshdlrdata	constraint handler data
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
var	variable to be considered for upper bound tightening
duration	duration of the job
demand	demand of the job
est	earliest start time of the job
lst	latest start time of the flexible part of the job
lct	latest completion time of the job
begin	begin of the time window under investigation
end	end of the time window under investigation
energy	available energy for the flexible part of the hob within the time window
bestub	pointer to strope the best upper bound change
inferinfos	pointer to store the inference information which is need for the (best) upper bound change
initialized	was conflict analysis initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoff	pointer to store if the constraint is infeasible

Definition at line 4572 of file cons_cumulative.c.

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

Referenced by propagateUbTTEF().

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

scip	SCIP data structure
conshdlrdata	constraint handler data
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
newlbs	array to buffer new lower bounds
newubs	array to buffer new upper bounds
lbinferinfos	array to store the inference information for the lower bound changes
ubinferinfos	array to store the inference information for the upper bound changes
lsts	array of latest start time of the flexible part in the same order as the variables
flexenergies	array of flexible energies in the same order as the variables
perm	permutation of the variables w.r.t. the non-decreasing order of the earliest start times
ests	array with earliest strart times sorted in non-decreasing order
lcts	array with latest completion times sorted in non-decreasing order
coreEnergyAfterEst	core energy after the earliest start times
coreEnergyAfterLct	core energy after the latest completion times
initialized	was conflict analysis initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoff	pointer to store if the constraint is infeasible

Definition at line 4686 of file cons_cumulative.c.

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

Referenced by propagateTTEF().

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

scip	SCIP data structure
conshdlrdata	constraint handler data
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
newlbs	array to buffer new lower bounds
newubs	array to buffer new upper bounds
lbinferinfos	array to store the inference information for the lower bound changes
ubinferinfos	array to store the inference information for the upper bound changes
ects	array of earliest completion time of the flexible part in the same order as the variables
flexenergies	array of flexible energies in the same order as the variables
perm	permutation of the variables w.r.t. the non-decreasing order of the latest completion times
ests	array with earliest strart times sorted in non-decreasing order
lcts	array with latest completion times sorted in non-decreasing order
coreEnergyAfterEst	core energy after the earliest start times
coreEnergyAfterLct	core energy after the latest completion times
initialized	was conflict analysis initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoff	pointer to store if the constraint is infeasible

Definition at line 5037 of file cons_cumulative.c.

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

Referenced by propagateTTEF().

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

scip	SCIP data structure
conshdlrdata	constraint handler data
profile	current core profile
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
cons	constraint which is propagated (needed to SCIPinferVar**Cons())
nchgbds	pointer to store the number of bound changes
initialized	was conflict analysis initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoff	pointer to store if the constraint is infeasible

Definition at line 5377 of file cons_cumulative.c.

References analyzeEnergyRequirement(), collectDataTTEF(), computeCoreEnergyAfter(), CONSHDLR_NAME, FALSE, inferInfoGetData1(), inferInfoGetData2(), inferInfoIsValid(), intToInferInfo(), NULL, propagateLbTTEF(), 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, SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by propagateCumulativeCondition().

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

scip	SCIP data structure
conshdlrdata	constraint handler data
profile	core profile
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
cons	constraint which is propagated (needed to SCIPinferVar**Cons())
nchgbds	pointer to store the number of bound changes
initialized	was conflict analysis initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoff	pointer to store if the constraint is infeasible

Definition at line 5586 of file cons_cumulative.c.

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

Referenced by propagateCumulativeCondition().

updateEnvelope()

static void updateEnvelope ( SCIP *  scip, SCIP_BTNODE *  node  )

static

update node data structure starting from the given node along the path to the root node

Parameters

scip	SCIP data structure
node	search node which inserted

Definition at line 5754 of file cons_cumulative.c.

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

Referenced by deleteLambdaLeaf(), 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

node	node to start the trace
key	update search key

Definition at line 5842 of file cons_cumulative.c.

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

Referenced by deleteLambdaLeaf().

deleteLambdaLeaf()

static SCIP_RETCODE deleteLambdaLeaf ( SCIP *  scip, SCIP_BT *  tree, SCIP_BTNODE *  node  )

static

deletes the given node and updates all envelops

Parameters

scip	SCIP data structure
tree	binary tree
node	node to be deleted

Definition at line 5874 of file cons_cumulative.c.

References nodedata, NULL, SCIP_OKAY, SCIPbtnodeFree(), SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPbtnodeIsLeftchild(), SCIPbtnodeIsRightchild(), SCIPbtnodeIsRoot(), SCIPbtnodeSetLeftchild(), SCIPbtnodeSetParent(), SCIPbtnodeSetRightchild(), SCIPbtSetRoot(), SCIPdebugMsg, updateEnvelope(), and updateKeyOnTrace().

Referenced by inferboundsEdgeFinding().

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

scip	SCIP data structure
tree	binary tree
node	node to move into the lambda set

Definition at line 5947 of file cons_cumulative.c.

References FALSE, nodedata, NULL, SCIP_OKAY, SCIPbtnodeGetData(), and updateEnvelope().

Referenced by inferboundsEdgeFinding().

insertThetanode()

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

static

inserts a node into the theta set and update the envelops

Parameters

scip	SCIP data structure
tree	binary tree
node	node to insert
nodedatas	array of node data
nodedataidx	array of indices for node data
nnodedatas	pointer to number of node data

Definition at line 5983 of file cons_cumulative.c.

References nodedata, NULL, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIPbtGetRoot(), SCIPbtIsEmpty(), SCIPbtnodeCreate(), SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPbtnodeSetLeftchild(), SCIPbtnodeSetParent(), SCIPbtnodeSetRightchild(), SCIPbtSetRoot(), TRUE, and updateEnvelope().

Referenced by checkOverloadViaThetaTree().

findResponsibleLambdaLeafTraceEnergy()

static SCIP_BTNODE * findResponsibleLambdaLeafTraceEnergy ( SCIP_BTNODE *  node )

static

returns the leaf responsible for the lambda energy

Parameters

node	node which defines the subtree beases on the lambda energy

Definition at line 6100 of file cons_cumulative.c.

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

Referenced by findResponsibleLambdaLeafTraceEnergy(), and findResponsibleLambdaLeafTraceEnvelop().

findResponsibleLambdaLeafTraceEnvelop()

static SCIP_BTNODE * findResponsibleLambdaLeafTraceEnvelop ( SCIP_BTNODE *  node )

static

returns the leaf responsible for the lambda envelop

Parameters

node	node which defines the subtree beases on the lambda envelop

Definition at line 6149 of file cons_cumulative.c.

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

Referenced by findResponsibleLambdaLeafTraceEnvelop(), 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

node	node within a theta subtree
omegaset	array to store the collected jobs
nelements	pointer to store the number of elements in omegaset
est	pointer to store the earliest start time of the omega set
lct	pointer to store the latest start time of the omega set
energy	pointer to store the energy of the omega set

Definition at line 6202 of file cons_cumulative.c.

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

Referenced by collectThetaSubtree(), 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

node	node whose theta envelop needs to be backtracked
omegaset	array to store the collected jobs
nelements	pointer to store the number of elements in omegaset
est	pointer to store the earliest start time of the omega set
lct	pointer to store the latest start time of the omega set
energy	pointer to store the energy of the omega set

Definition at line 6237 of file cons_cumulative.c.

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

Referenced by traceLambdaEnvelop(), and traceThetaEnvelop().

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

node	node whose lambda envelop needs to be backtracked
omegaset	array to store the collected jobs
nelements	pointer to store the number of elements in omega set
est	pointer to store the earliest start time of the omega set
lct	pointer to store the latest start time of the omega set
energy	pointer to store the energy of the omega set

Definition at line 6297 of file cons_cumulative.c.

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

Referenced by traceLambdaEnergy(), and traceLambdaEnvelop().

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

node	node whose lambda envelop needs to be backtracked
omegaset	array to store the collected jobs
nelements	pointer to store the number of elements in omega set
est	pointer to store the earliest start time of the omega set
lct	pointer to store the latest start time of the omega set
energy	pointer to store the energy of the omega set

Definition at line 6354 of file cons_cumulative.c.

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

Referenced by inferboundsEdgeFinding(), and traceLambdaEnvelop().

computeEnergyContribution()

static int computeEnergyContribution ( SCIP_BTNODE *  node )

static

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

Parameters

node

leaf

Definition at line 6420 of file cons_cumulative.c.

References nodedata, NULL, SCIPbtnodeGetData(), SCIPdebugMessage, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

Referenced by analyzeConflictOverload().

SCIP_DECL_SORTPTRCOMP()

static SCIP_DECL_SORTPTRCOMP ( compNodeEst  )

static

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

Definition at line 6444 of file cons_cumulative.c.

References SCIPbtnodeGetData().

SCIP_DECL_SORTINDCOMP() [1/2]

static SCIP_DECL_SORTINDCOMP ( compNodedataLct  )

static

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

Definition at line 6457 of file cons_cumulative.c.

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

scip	SCIP data structure
leaves	responsible leaves for the overload
capacity	cumulative capacity
nleaves	number of responsible leaves
est	earliest start time of the ......
lct	latest completly time of the ....
reportedenergy	energy which already reported
propest	should the earliest start times be propagated, otherwise the latest completion times
shift	shift applied to all jobs before adding them to the tree
usebdwidening	should bound widening be used during conflict analysis?
initialized	was conflict analysis initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL

Definition at line 6471 of file cons_cumulative.c.

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

Referenced by checkOverloadViaThetaTree(), and inferboundsEdgeFinding().

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

scip	SCIP data structure
duration	duration of the job to move
demand	demand of the job to move
capacity	cumulative capacity
est	earliest start time of the omega set
lct	latest start time of the omega set
energy	energy of the omega set

Definition at line 6581 of file cons_cumulative.c.

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

Referenced by 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

scip	SCIP data structure
conshdlrdata	constraint handler data
cons	constraint which is propagated
tree	binary tree constaining the theta and lambda sets
leaves	array of all leaves for each job one
capacity	cumulative capacity
ncands	number of candidates
propest	should the earliest start times be propagated, otherwise the latest completion times
shift	shift applied to all jobs before adding them to the tree
initialized	was conflict analysis initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
nchgbds	pointer to store the number of bound changes
cutoff	pointer to store if the constraint is infeasible

Definition at line 6615 of file cons_cumulative.c.

References analyzeConflictOverload(), computeEstOmegaset(), CONSHDLR_NAME, deleteLambdaLeaf(), FALSE, findResponsibleLambdaLeafTraceEnvelop(), getInferInfo(), inferInfoIsValid(), inferInfoToInt(), moveNodeToLambda(), nodedata, NULL, PROPRULE_2_EDGEFINDING, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPallocBufferArray, SCIPbtGetRoot(), SCIPbtIsEmpty(), SCIPbtnodeGetData(), SCIPbtnodeIsLeaf(), SCIPbtnodeIsRoot(), SCIPconshdlrGetData(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPstatistic, SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), traceLambdaEnvelop(), and TRUE.

Referenced by checkOverloadViaThetaTree().

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

scip	SCIP data structure
conshdlrdata	constraint handler data
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
cons	constraint which is propagated
propest	should the earliest start times be propagated, otherwise the latest completion times
initialized	was conflict analysis initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
nchgbds	pointer to store the number of bound changes
cutoff	pointer to store if the constraint is infeasible

Definition at line 6839 of file cons_cumulative.c.

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

Referenced by 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

scip	SCIP data structure
conshdlrdata	constraint handler data
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
cons	constraint which is propagated
initialized	was conflict analysis initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
nchgbds	pointer to store the number of bound changes
cutoff	pointer to store if the constraint is infeasible

Definition at line 7143 of file cons_cumulative.c.

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

Referenced by 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

scip	SCIP data structure
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
redundant	pointer to store whether this constraint is redundant

Definition at line 7192 of file cons_cumulative.c.

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

Referenced by propagateCumulativeCondition().

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

scip	SCIP data structure
conshdlrdata	constraint handler data
profile	resource profile
nvars	number of variables (jobs)
vars	array of integer variable which corresponds to starting times for a job
durations	array containing corresponding durations
demands	array containing corresponding demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
initialized	was conflict analysis initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoff	pointer to store if the constraint is infeasible

Definition at line 7314 of file cons_cumulative.c.

References analyseInfeasibelCoreInsertion(), CONSHDLR_NAME, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPisFeasIntegral(), SCIPprofileGetTime(), SCIPprofileInsertCore(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by 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

scip	SCIP data structure
conshdlrdata	constraint handler data
presoltiming	current presolving timing
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
demands	array of demands
capacity	cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
cons	constraint which is propagated (needed to SCIPinferVar**Cons())
nchgbds	pointer to store the number of bound changes
redundant	pointer to store if the constraint is redundant
initialized	was conflict analysis initialized
explanation	bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoff	pointer to store if the constraint is infeasible

Definition at line 7405 of file cons_cumulative.c.

References consCheckRedundancy(), createCoreProfile(), NULL, propagateEdgeFinding(), propagateTimetable(), propagateTTEF(), SCIP_CALL, SCIP_CALL_TERMINATE, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_PRESOLTIMING_FAST, SCIP_PRESOLTIMING_MEDIUM, SCIPprofileCreate(), and SCIPprofileFree().

Referenced by 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

scip	SCIP data structure
cons	constraint to propagate
conshdlrdata	constraint handler data
presoltiming	current presolving timing
nchgbds	pointer to store the number of bound changes
ndelconss	pointer to store the number of deleted constraints
cutoff	pointer to store if the constraint is infeasible

Definition at line 7477 of file cons_cumulative.c.

References 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 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

scip	SCIP data structure
vars	problem variables
nvars	number of problem variables
probingpos	variable number to apply probing on
leftub	upper bound of probing variable in left branch
rightlb	lower bound of probing variable in right branch
leftimpllbs	lower bounds after applying implications and cliques in left branch, or NULL
leftimplubs	upper bounds after applying implications and cliques in left branch, or NULL
leftproplbs	lower bounds after applying domain propagation in left branch
leftpropubs	upper bounds after applying domain propagation in left branch
rightimpllbs	lower bounds after applying implications and cliques in right branch, or NULL
rightimplubs	upper bounds after applying implications and cliques in right branch, or NULL
rightproplbs	lower bounds after applying domain propagation in right branch
rightpropubs	upper bounds after applying domain propagation in right branch
nfixedvars	pointer to counter which is increased by the number of deduced variable fixations
success	buffer to store whether a probing succeed to dual fix the variable
cutoff	buffer to store whether a cutoff is detected

Definition at line 7558 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(), and TRUE.

Referenced by applyAlternativeBoundsFixing(), presolveConsEst(), and presolveConsLct().

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

scip	SCIP data structure
var	problem variable
roundable	pointer to store if the variable can be rounded down

Definition at line 7656 of file cons_cumulative.c.

References FALSE, getActiveVar(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIPisNegative(), SCIPisPositive(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarIsActive(), and TRUE.

Referenced by applyAlternativeBoundsFixing(), 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

scip	SCIP data structure
var	problem variable
roundable	pointer to store if the variable can be rounded down

Definition at line 7705 of file cons_cumulative.c.

References FALSE, getActiveVar(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIPisNegative(), SCIPisPositive(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarIsActive(), and TRUE.

Referenced by applyAlternativeBoundsFixing(), fixIntegerVariableUb(), and presolveConsLct().

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

scip	SCIP data structure
conss	array of cumulative constraint constraints
nconss	number of cumulative constraints
local	use local bounds effective horizon?
alternativelbs	alternative lower bounds
alternativeubs	alternative lower bounds
downlocks	number of constraints with down lock participating by the computation
uplocks	number of constraints with up lock participating by the computation

Definition at line 7758 of file cons_cumulative.c.

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

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

scip	SCIP data structure
vars	array of active variables
nvars	number of active variables
alternativelbs	alternative lower bounds
alternativeubs	alternative lower bounds
downlocks	number of constraints with down lock participating by the computation
uplocks	number of constraints with up lock participating by the computation
nfixedvars	pointer to counter which is increased by the number of deduced variable fixations
cutoff	buffer to store whether a cutoff is detected

Definition at line 7892 of file cons_cumulative.c.

References applyProbingVar(), CONSHDLR_NAME, NULL, 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 propagateAllConss().

propagateAllConss()

static SCIP_RETCODE propagateAllConss ( SCIP *  scip, SCIP_CONS **  conss, int  nconss, SCIP_Bool  local, int *  nfixedvars, SCIP_Bool *  cutoff, SCIP_Bool *  branched  )

static

propagate all constraints together

Parameters

scip	SCIP data structure
conss	all cumulative constraint
nconss	number of cumulative constraints
local	use local bounds effective horizon?
nfixedvars	pointer to counter which is increased by the number of deduced variable fixations
cutoff	buffer to store whether a cutoff is detected
branched	pointer to store if a branching was applied, or NULL to avoid branching

Definition at line 8048 of file cons_cumulative.c.

References applyAlternativeBoundsBranching(), applyAlternativeBoundsFixing(), computeAlternativeBounds(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetVars(), SCIPinProbing(), and SCIPinRepropagation().

Referenced by 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

scip	SCIP data structure
cons	constraint to be checked
startvalues	upper bounds on finishing time per job for activities from 0,..., nactivities -1
time	at this point in time covering constraints are valid

Definition at line 8119 of file cons_cumulative.c.

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

Referenced by createCoverCuts().

createCoverCuts()

static SCIP_RETCODE createCoverCuts ( SCIP *  scip, SCIP_CONS *  cons  )

static

method to construct cover cuts for all points in time

Parameters

scip	SCIP data structure
cons	constraint to be separated

Definition at line 8374 of file cons_cumulative.c.

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

Referenced by 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

scip	SCIP data structure
cons	constraint to be checked
startindices	permutation with rspect to the start times
curtime	current point in time
nstarted	number of jobs that start before the curtime or at curtime
nfinished	number of jobs that finished before curtime or at curtime
cutsasconss	should the cumulative constraint create the cuts as constraints?

Definition at line 8513 of file cons_cumulative.c.

References b, collectBinaryVars(), FALSE, NULL, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCoefKnapsack(), SCIPaddCons(), SCIPaddVarToRow(), SCIPallocBlockMemoryArray, SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsRemovable(), SCIPcreateConsKnapsack(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPflushRowExtensions(), SCIPfreeBufferArrayNull, SCIPinfinity(), SCIPprintRow(), SCIPreallocBlockMemoryArray, SCIPreleaseCons(), SCIPsnprintf(), and TRUE.

Referenced by consCapacityConstraintsFinder().

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

scip	SCIP data structure
cons	constraint to be checked
cutsasconss	should the cumulative constraint create the cuts as constraints?

Definition at line 8603 of file cons_cumulative.c.

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

Referenced by 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

scip	SCIP data structure
cons	cumulative constraint
cutsasconss	should the cumulative constraint create the cuts as constraints?

Definition at line 8734 of file cons_cumulative.c.

References consCapacityConstraintsFinder(), consdataCollectLinkingCons(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsSeparated(), SCIPsetConsEnforced(), SCIPsetConsInitial(), and SCIPsetConsSeparated().

Referenced by addRelaxation(), 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

scip	SCIP data structure
cons	cumulative constraint
cutsasconss	should the cumulative constraint create the cuts as constraints?
infeasible	pointer to store whether an infeasibility was detected

Definition at line 8777 of file cons_cumulative.c.

References createRelaxation(), FALSE, NULL, r, SCIP_CALL, SCIP_OKAY, SCIPaddRow(), SCIPconsGetData(), and SCIProwIsInLP().

Referenced by 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

scip	SCIP data structure
cons	cumulative constraint to be separated
sol	primal CIP solution, NULL for current LP solution
separated	pointer to store TRUE, if a cut was found
cutoff	whether a cutoff has been detected

Definition at line 8813 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(), and TRUE.

Referenced by 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

scip	SCIP data structure
cons	logic or constraint to be separated
sol	primal CIP solution, NULL for current LP solution
separated	pointer to store TRUE, if a cut was found
cutoff	whether a cutoff has been detected

Definition at line 8889 of file cons_cumulative.c.

References consdataCollectLinkingCons(), 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(), and SCIP_DECL_CONSSEPASOL().

createCapacityRestrictionIntvars()

static SCIP_RETCODE createCapacityRestrictionIntvars ( SCIP *  scip, SCIP_CONS *  cons, int *  startindices, int  curtime, int  nstarted, int  nfinished, SCIP_Bool  lower, SCIP_Bool *  cutoff  )

static

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

Parameters

scip	SCIP data structure
cons	constraint to be checked
startindices	permutation with rspect to the start times
curtime	current point in time
nstarted	number of jobs that start before the curtime or at curtime
nfinished	number of jobs that finished before curtime or at curtime
lower	shall cuts be created due to lower or upper bounds?
cutoff	pointer to store TRUE, if a cutoff was detected

Definition at line 9008 of file cons_cumulative.c.

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

Referenced by separateConsOnIntegerVariables().

separateConsOnIntegerVariables()

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

static

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

Parameters

scip	SCIP data structure
cons	cumulative constraint to be separated
sol	primal CIP solution, NULL for current LP solution
lower	shall cuts be created according to lower bounds?
separated	pointer to store TRUE, if a cut was found
cutoff	pointer to store TRUE, if a cutoff was detected

Definition at line 9074 of file cons_cumulative.c.

References addEndingJobDemands(), createCapacityRestrictionIntvars(), createSelectedSortedEventpointsSol(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPfreeBufferArray, subtractStartingJobDemands(), and TRUE.

Referenced by 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

scip	SCIP data structure
cons	constraint to be checked

Definition at line 9182 of file cons_cumulative.c.

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

Referenced by presolveCons(), and SCIP_DECL_CONSPRESOL().

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

scip	SCIP data structure
cons	constraint to propagate
ndelconss	pointer to store the number of deleted constraints
cutoff	pointer to store if the constraint is infeasible

Definition at line 9223 of file cons_cumulative.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPdelCons(), and TRUE.

Referenced by 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

scip	SCIP data structure
cons	constraint to propagate

Definition at line 9265 of file cons_cumulative.c.

References consdataDeletePos(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPstatistic, SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().

Referenced by 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

scip	SCIP data structure
consdata	constraint data
pos	position of job in the consdata
nchgbds	pointer to store the number of changed bounds
naddconss	pointer to store the number of added constraints
cutoff	pointer to store if a cutoff was detected

Definition at line 9329 of file cons_cumulative.c.

References FALSE, NULL, 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 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

scip	SCIP data structure
cons	constraint
nchgbds	pointer to store the number of changed bounds
nchgcoefs	pointer to store the number of changed coefficient
naddconss	pointer to store the number of added constraints
cutoff	pointer to store if a cutoff was detected

Definition at line 9435 of file cons_cumulative.c.

References adjustOversizedJobBounds(), consdataDeletePos(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), and SCIPdebugMsg.

Referenced by 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

scip	SCIP data structure
var	integer variable to fix
uplock	has thet start time variable a up lock
nfixedvars	pointer to store the number fixed variables

Definition at line 9476 of file cons_cumulative.c.

References FALSE, SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPdebugMsg, SCIPfixVar(), SCIPinProbing(), SCIPinRepropagation(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNLocksUpType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and varMayRoundUp().

Referenced by presolveConsLct().

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

scip	SCIP data structure
var	integer variable to fix
downlock	has the variable a down lock
nfixedvars	pointer to store the number fixed variables

Definition at line 9528 of file cons_cumulative.c.

References FALSE, SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPdebugMsg, SCIPfixVar(), SCIPinProbing(), SCIPinRepropagation(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDownType(), TRUE, and varMayRoundDown().

Referenced by presolveConsEst().

normalizeCumulativeCondition()

static void normalizeCumulativeCondition ( SCIP *  scip, int  nvars, int *  demands, int *  capacity, int *  nchgcoefs, int *  nchgsides  )

static

normalize cumulative condition

Parameters

scip	SCIP data structure
nvars	number of start time variables (activities)
demands	array of demands
capacity	pointer to store the changed cumulative capacity
nchgcoefs	pointer to count total number of changed coefficients
nchgsides	pointer to count number of side changes

Definition at line 9575 of file cons_cumulative.c.

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

Referenced by normalizeDemands(), and SCIPnormalizeCumulativeCondition().

normalizeDemands()

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

scip	SCIP data structure
cons	cumulative constraint
nchgcoefs	pointer to count total number of changed coefficients
nchgsides	pointer to count number of side changes

Definition at line 9646 of file cons_cumulative.c.

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

Referenced by 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

scip	SCIP data structure
nvars	number of variables (jobs)
vars	array of integer variable which corresponds to starting times for a job
durations	array containing corresponding durations
demands	array containing corresponding demands
capacity	available cumulative capacity
hmin	pointer to store the left bound of the effective horizon
hmax	pointer to store the right bound of the effective horizon
split	point were the cumulative condition can be split

Definition at line 9680 of file cons_cumulative.c.

References NULL, SCIP_CALL, SCIP_CALL_FINALLY, SCIP_OKAY, SCIPcomputeHmax(), SCIPcomputeHmin(), SCIPcreateWorstCaseProfile(), SCIPdebug, SCIPgetMessagehdlr(), SCIPinRepropagation(), SCIPprofileCreate(), SCIPprofileFree(), SCIPprofileGetLoads(), SCIPprofileGetNTimepoints(), SCIPprofileGetTimepoints(), and SCIPprofilePrint().

Referenced by computeEffectiveHorizon(), 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

scip	SCIP data structure
name	name of constraint
nvars	number of variables (jobs)
vars	array of integer variable which corresponds to starting times for a job
durations	array containing corresponding durations
demands	array containing corresponding demands
capacity	available cumulative capacity
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separate	should the constraint be separated during LP processing? Usually set to TRUE.
enforce	should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
check	should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagate	should the constraint be propagated during node processing? Usually set to TRUE.
local	is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiable	is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamic	is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are seperated as constraints.
removable	should the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnode	should the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.

Definition at line 9760 of file cons_cumulative.c.

References SCIP_CALL, SCIP_OKAY, SCIPaddCons(), SCIPcreateConsCumulative(), SCIPreleaseCons(), SCIPsetHmaxCumulative(), and SCIPsetHminCumulative().

Referenced by computeEffectiveHorizon(), 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

scip	SCIP data structure
cons	cumulative constraint
ndelconss	pointer to store the number of deleted constraints
naddconss	pointer to store the number of added constraints
nchgsides	pointer to store the number of changed sides

Definition at line 9814 of file cons_cumulative.c.

References computeEffectiveHorizonCumulativeCondition(), CONSHDLR_NAME, createConsCumulative(), NULL, 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 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

scip	SCIP data structure
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
downlocks	array to store if the variable has a down lock, or NULL
uplocks	array to store if the variable has an up lock, or NULL
cons	underlying constraint, or NULL
irrelevants	array mark those variables which are irrelevant for the cumulative condition
nfixedvars	pointer to store the number of fixed variables
nchgsides	pointer to store the number of changed sides
cutoff	buffer to store whether a cutoff is detected

Definition at line 9918 of file cons_cumulative.c.

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

scip	SCIP data structure
nvars	number of start time variables (activities)
vars	array of start time variables
durations	array of durations
hmin	left bound of time axis to be considered (including hmin)
hmax	right bound of time axis to be considered (not including hmax)
downlocks	array to store if the variable has a down lock, or NULL
uplocks	array to store if the variable has an up lock, or NULL
cons	underlying constraint, or NULL
irrelevants	array mark those variables which are irrelevant for the cumulative condition
nfixedvars	pointer to counter which is increased by the number of deduced variable fixations
nchgsides	pointer to store the number of changed sides
cutoff	buffer to store whether a cutoff is detected

Definition at line 10203 of file cons_cumulative.c.

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

scip	SCIP data structure
cons	cumulative constraint
nfixedvars	pointer to store the number of fixed variables
nchgcoefs	pointer to store the number of changed coefficients
nchgsides	pointer to store the number of changed sides
cutoff	pointer to store if a cutoff was detected

Definition at line 10455 of file cons_cumulative.c.

References BMSclearMemoryArray, consdataDeletePos(), FALSE, NULL, presolveConsEst(), presolveConsLct(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconvertRealToInt(), SCIPfreeBufferArray, SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by presolveCons().

collectDemands()

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

scip	SCIP data structure
consdata	constraint data
startindices	permutation with rspect to the start times
curtime	current point in time
nstarted	number of jobs that start before the curtime or at curtime
nfinished	number of jobs that finished before curtime or at curtime
demands	pointer to array storing the demands
ndemands	pointer to store the number of different demands

Definition at line 10536 of file cons_cumulative.c.

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

Referenced by getHighestCapacityUsage().

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

scip	SCIP data structure
cons	constraint to be checked
startindices	permutation with rspect to the start times
curtime	current point in time
nstarted	number of jobs that start before the curtime or at curtime
nfinished	number of jobs that finished before curtime or at curtime
bestcapacity	pointer to store the maximum possible capacity usage

Definition at line 10593 of file cons_cumulative.c.

References collectDemands(), NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconvertRealToInt(), SCIPfreeBufferArray, SCIPisFeasIntegral(), and SCIPsolveKnapsackExactly().

Referenced by 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

scip	SCIP data structure
cons	cumulative constraint
nchgcoefs	pointer to count total number of changed coefficients
nchgsides	pointer to store the number of changed sides

Definition at line 10654 of file cons_cumulative.c.

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

Referenced by 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

scip	SCIP data structure
cons	cumulative constraint
nchgcoefs	pointer to count total number of changed coefficients

Definition at line 10796 of file cons_cumulative.c.

References FALSE, MIN, NULL, SCIP_Bool, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by presolveCons().

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

scip	SCIP data structure
cons	cumulative constraint
naddconss	pointer to store the number of added constraints

Definition at line 10998 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSPRESOL().

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

scip	SCIP data structure
cons	cumulative constraint
conshdlrdata	constraint handler data
presoltiming	timing of presolving call
nfixedvars	pointer to store the number of fixed variables
nchgbds	pointer to store the number of changed bounds
ndelconss	pointer to store the number of deleted constraints
naddconss	pointer to store the number of added constraints
nchgcoefs	pointer to store the number of changed coefficients
nchgsides	pointer to store the number of changed sides
cutoff	pointer to store if a cutoff was detected
unbounded	pointer to store if the problem is unbounded

Definition at line 11081 of file cons_cumulative.c.

References checkDemands(), computeEffectiveHorizon(), deleteTrivilCons(), normalizeDemands(), presolveConsEffectiveHorizon(), removeOversizedJobs(), SCIP_CALL, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIPallowStrongDualReds(), SCIPconsIsDeleted(), solveIndependentCons(), tightenCapacity(), and tightenCoefs().

Referenced by SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().

TCLIQUE_GETNNODES()

static TCLIQUE_GETNNODES ( tcliqueGetnnodesClique  )

static

gets number of nodes in the graph

Definition at line 11186 of file cons_cumulative.c.

References NULL.

TCLIQUE_GETWEIGHTS()

static TCLIQUE_GETWEIGHTS ( tcliqueGetweightsClique  )

static

gets weight of nodes in the graph

Definition at line 11195 of file cons_cumulative.c.

References NULL.

TCLIQUE_ISEDGE()

static TCLIQUE_ISEDGE ( tcliqueIsedgeClique  )

static

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

Definition at line 11204 of file cons_cumulative.c.

References FALSE, nnodes, NULL, and TRUE.

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 11225 of file cons_cumulative.c.

References nnodes, and NULL.

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 11259 of file cons_cumulative.c.

References SCIPdebugMessage.

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

scip	SCIP data structure
vlbvar	variable which bounds the variable from below
vlbcoef	variable bound coefficient
vlbconst	variable bound constant
duration	duration of the variable bound variable

Definition at line 11297 of file cons_cumulative.c.

References bound, FALSE, SCIP_Real, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by impliesVubPrecedenceCondition(), and projectVbd().

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

scip	SCIP data structure
var	variable which is bound from above
vubcoef	variable bound coefficient
vubconst	variable bound constant
duration	duration of the variable which is bounded from above

Definition at line 11352 of file cons_cumulative.c.

References impliesVlbPrecedenceCondition(), and SCIP_Real.

Referenced by 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

scip	SCIP data structure
tcliquegraph	incompatibility graph
var	variable for which we want the index
idx	pointer to store the index

Definition at line 11374 of file cons_cumulative.c.

References BMSclearMemoryArray, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPreallocBufferArray, and SCIPvarGetProbindex().

Referenced by constraintNonOverlappingGraph(), 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

scip	SCIP data structure
tcliquegraph	incompatibility graph

Definition at line 11465 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(), and TRUE.

Referenced by constructIncompatibilityGraph().

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

adjmatrix	adjacent matrix
ninarcs	array to store the number of in arcs
noutarcs	array to store the number of out arcs
nnodes	number if nodes

Definition at line 11560 of file cons_cumulative.c.

References nnodes, and TRUE.

Referenced by constructIncompatibilityGraph().

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

scip	SCIP data structure
tcliquegraph	incompatibility graph
conss	array of cumulative constraints
nconss	number of cumulative constraints

Definition at line 11592 of file cons_cumulative.c.

References getNodeIdx(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by constructIncompatibilityGraph().

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

scip	SCIP data structure
tcliquegraph	incompatibility graph
conss	array of cumulative constraints
nconss	number of cumulative constraints

Definition at line 11687 of file cons_cumulative.c.

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

Referenced by 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

scip	SCIP data structure
name	constraint name
tcliquegraph	conflict set graph
cliquenodes	array storing the indecies of the nodes belonging to the clique
ncliquenodes	number of nodes in the clique

Definition at line 11711 of file cons_cumulative.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsCumulative(), SCIPfreeBufferArray, SCIPreleaseCons(), SCIPsortInt(), and TRUE.

Referenced by findCumulativeConss().

findCumulativeConss()

static SCIP_RETCODE findCumulativeConss ( SCIP *  scip, TCLIQUE_GRAPH *  tcliquegraph, int *  naddconss  )

static

search for cumulative constrainst

Parameters

scip	SCIP data structure
tcliquegraph	conflict set graph
naddconss	pointer to store the number of added constraints

Definition at line 11757 of file cons_cumulative.c.

References CONSHDLR_NAME, createCumulativeCons(), FALSE, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBufferArray, SCIPblkmem(), SCIPconshdlrGetData(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetNRuns(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPisStopped(), SCIPsnprintf(), SCIPstatistic, SCIPvarGetName(), and tcliqueMaxClique().

Referenced by detectRedundantConss().

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

scip	SCIP data structure
name	constraint name
var	variable x that has variable bound
vbdvar	binary, integer or implicit integer bounding variable y
distance	minimum distance between the start time of the job corresponding to var and the job corresponding to vbdvar

Definition at line 11885 of file cons_cumulative.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPcreateConsVarbound(), SCIPdebugPrintCons, SCIPinfinity(), SCIPreleaseCons(), and TRUE.

Referenced by computeMinDistance(), 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

scip	SCIP data structure
tcliquegraph	conflict set graph
source	index of the source node
sink	index of the sink node
naddconss	pointer to store the number of added constraints

Definition at line 11910 of file cons_cumulative.c.

References BMSclearMemoryArray, createPrecedenceCons(), nnodes, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPfreeBufferArray, SCIPgetNRuns(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and tcliqueMaxClique().

Referenced by 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

scip	SCIP data structure
tcliquegraph	conflict set graph
naddconss	pointer to store the number of added constraints

Definition at line 12011 of file cons_cumulative.c.

References computeMinDistance(), CONSHDLR_NAME, nnodes, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPisStopped(), and SCIPstatistic.

Referenced by 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

scip	SCIP data structure
tcliquegraph	the incompatibility graph
conss	cumulative constraints
nconss	number of cumulative constraints

Definition at line 12079 of file cons_cumulative.c.

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

Referenced by detectRedundantConss().

createTcliqueGraph()

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

static

create tclique graph

Parameters

scip	SCIP data structure
tcliquegraph	reference to the incompatibility graph

Definition at line 12123 of file cons_cumulative.c.

References BMSclearMemoryArray, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPblkmem(), SCIPduplicateBufferArray, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapInsertInt(), and SCIPvarGetProbindex().

Referenced by detectRedundantConss().

freeTcliqueGraph()

static void freeTcliqueGraph ( SCIP *  scip, TCLIQUE_GRAPH **  tcliquegraph  )

static

frees the tclique graph

Parameters

scip	SCIP data structure
tcliquegraph	reference to the incompatibility graph

Definition at line 12204 of file cons_cumulative.c.

References SCIPfreeBuffer, SCIPfreeBufferArray, and SCIPhashmapFree().

Referenced by 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

scip	SCIP data structure
conshdlrdata	constraint handler data
conss	array of cumulative constraints
nconss	number of cumulative constraints
naddconss	pointer to store the number of added constraints

Definition at line 12233 of file cons_cumulative.c.

References constructIncompatibilityGraph(), createTcliqueGraph(), findCumulativeConss(), findPrecedenceConss(), freeTcliqueGraph(), initializeDurations(), SCIP_CALL, and SCIP_OKAY.

Referenced by 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

consdata

cumulative constraint data

Definition at line 12272 of file cons_cumulative.c.

References SCIPvarGetIndex(), and TRUE.

Referenced by removeRedundantConss().

SCIP_DECL_SORTINDCOMP() [2/2]

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 12296 of file cons_cumulative.c.

References NULL, and SCIPvarCompare().

removeRedundantConss()

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

static

run a pairwise comparison

Parameters

scip	SCIP data structure
conss	array of cumulative constraints
nconss	number of cumulative constraints
ndelconss	pointer to store the number of deletedconstraints

Definition at line 12309 of file cons_cumulative.c.

References consdataCalcSignature(), initializeLocks(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsIsChecked(), SCIPdelCons(), SCIPfreeBufferArray, SCIPsort(), SCIPswapPointers(), SCIPupdateConsFlags(), SCIPvarCompare(), and TRUE.

Referenced by SCIP_DECL_CONSPRESOL().

strengthenVarbounds()

static SCIP_RETCODE strengthenVarbounds ( SCIP *  scip, SCIP_CONS *  cons, int *  nchgbds, int *  naddconss  )

static

strengthen the variable bounds using the cumulative condition

Parameters

scip	SCIP data structure
cons	constraint to propagate
nchgbds	pointer to store the number of changed bounds
naddconss	pointer to store the number of added constraints

Definition at line 12450 of file cons_cumulative.c.

References b, createPrecedenceCons(), 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 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

scip	SCIP data structure
conshdlr	constraint handler
conss	constraints to process
nconss	number of constraints
nusefulconss	number of useful (non-obsolete) constraints to process
sol	solution to enforce (NULL for the LP solution)
solinfeasible	was the solution already declared infeasible by a constraint handler?
result	pointer to store the result of the enforcing call

Definition at line 12546 of file cons_cumulative.c.

References checkCons(), CONSHDLR_NAME, enforceSolution(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, and separateConsBinaryRepresentation().

Referenced by SCIP_DECL_CONSENFOLP(), and SCIP_DECL_CONSENFORELAX().

SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyCumulative  )

static

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

Definition at line 12650 of file cons_cumulative.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfindConshdlr(), SCIPincludeConshdlrCumulative(), SCIPstatistic, and TRUE.

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 12668 of file cons_cumulative.c.

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

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 12701 of file cons_cumulative.c.

References FALSE, NULL, removeIrrelevantJobs(), SCIP_CALL, SCIP_OKAY, and SCIPconshdlrGetData().

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 12763 of file cons_cumulative.c.

References consdataFreeRows(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), and SCIPconshdlrGetName().

SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteCumulative  )

static

frees specific constraint data

Definition at line 12786 of file cons_cumulative.c.

References consdataDropAllEvents(), consdataFree(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPvarIsTransformed().

SCIP_DECL_CONSTRANS()

static SCIP_DECL_CONSTRANS ( consTransCumulative  )

static

transforms constraint data into data belonging to the transformed problem

Definition at line 12812 of file cons_cumulative.c.

References consdataCatchEvents(), consdataCreate(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_TRANSFORMING, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateCons(), SCIPdebugMsg, and SCIPgetStage().

SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpCumulative  )

static

LP initialization method of constraint handler

Definition at line 12854 of file cons_cumulative.c.

References addRelaxation(), CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsInitial(), SCIPdebugMsg, and SCIPrestartSolve().

SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpCumulative  )

static

separation method of constraint handler for LP solutions

Definition at line 12891 of file cons_cumulative.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetDepth(), separateConsBinaryRepresentation(), separateConsOnIntegerVariables(), separateCoverCutsCons(), and TRUE.

SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolCumulative  )

static

separation method of constraint handler for arbitrary primal solutions

Definition at line 12955 of file cons_cumulative.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetDepth(), separateConsBinaryRepresentation(), separateConsOnIntegerVariables(), separateCoverCutsCons(), and TRUE.

SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpCumulative  )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 13015 of file cons_cumulative.c.

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

SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxCumulative  )

static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 13024 of file cons_cumulative.c.

References enforceConstraint(), SCIP_CALL, and SCIP_OKAY.

SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsCumulative  )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 13033 of file cons_cumulative.c.

References CONSHDLR_NAME, enforceSolution(), NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.

SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckCumulative  )

static

feasibility check method of constraint handler for integral solutions

Definition at line 13062 of file cons_cumulative.c.

References checkCons(), CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconshdlrGetName(), and SCIPdebugMsg.

SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropCumulative  )

static

domain propagation method of constraint handler

Definition at line 13090 of file cons_cumulative.c.

References CONSHDLR_NAME, FALSE, NULL, presolveCons(), propagateAllConss(), propagateCons(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PRESOLTIMING_ALWAYS, SCIP_REDUCEDDOM, SCIPallowStrongDualReds(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsDeleted(), SCIPdebugMsg, SCIPgetDepth(), and TRUE.

SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolCumulative  )

static

presolving method of constraint handler

Definition at line 13177 of file cons_cumulative.c.

References checkDemands(), CONSHDLR_NAME, createDisjuctiveCons(), detectRedundantConss(), FALSE, NULL, presolveCons(), propagateAllConss(), propagateCons(), removeIrrelevantJobs(), removeRedundantConss(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_PRESOLTIMING_FAST, SCIP_PRESOLTIMING_MEDIUM, SCIP_SUCCESS, SCIP_UNBOUNDED, SCIPallowStrongDualReds(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsDeleted(), SCIPdebugMsg, SCIPgetNRuns(), strengthenVarbounds(), and TRUE.

SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropCumulative  )

static

propagation conflict resolving method of constraint handler

Definition at line 13298 of file cons_cumulative.c.

References CONSHDLR_NAME, inferInfoGetProprule(), intToInferInfo(), NULL, respropCumulativeCondition(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetHmaxCumulative(), SCIPgetHminCumulative(), and SCIPvarGetName().

SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockCumulative  )

static

variable rounding lock method of constraint handler

Definition at line 13332 of file cons_cumulative.c.

References NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPconsGetData(), SCIPconsGetName(), and SCIPdebugMsg.

SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintCumulative  )

static

constraint display method of constraint handler

Definition at line 13373 of file cons_cumulative.c.

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

SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopyCumulative  )

static

constraint copying method of constraint handler

Definition at line 13386 of file cons_cumulative.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPcreateConsCumulative(), SCIPfreeBufferArray, SCIPgetVarCopy(), SCIPsetHmaxCumulative(), SCIPsetHminCumulative(), and TRUE.

SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseCumulative  )

static

constraint parsing method of constraint handler

Definition at line 13452 of file cons_cumulative.c.

References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateConsCumulative(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPparseReal(), SCIPparseVarName(), SCIPsetHmaxCumulative(), SCIPsetHminCumulative(), SCIPstrCopySection(), SCIPvarGetName(), and TRUE.

SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsCumulative  )

static

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

Definition at line 13559 of file cons_cumulative.c.

References BMScopyMemoryArray, FALSE, NULL, SCIP_OKAY, SCIPconsGetData(), and TRUE.

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 13581 of file cons_cumulative.c.

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

SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecCumulative  )

static

execution method of event handler

Definition at line 13604 of file cons_cumulative.c.

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