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.

Referenced by applyAlternativeBoundsFixing(), checkOverloadViaThetaTree(), computeEffectiveHorizon(), coretimesUpdateLb(), coretimesUpdateUb(), createCoreProfile(), enforceConstraint(), findCumulativeConss(), findPrecedenceConss(), inferboundsEdgeFinding(), presolveConsEst(), presolveConsLct(), propagateLbTTEF(), propagateTimetable(), propagateTTEF(), propagateUbTTEF(), removeIrrelevantJobs(), SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSENFOPS(), SCIP_DECL_CONSEXITSOL(), SCIP_DECL_CONSFREE(), SCIP_DECL_CONSHDLRCOPY(), SCIP_DECL_CONSINITLP(), SCIP_DECL_CONSPRESOL(), SCIP_DECL_CONSPROP(), SCIP_DECL_CONSRESPROP(), SCIP_DECL_CONSSEPALP(), SCIP_DECL_CONSSEPASOL(), SCIPcreateConsCumulative(), SCIPgetCapacityCumulative(), SCIPgetDemandsCumulative(), SCIPgetDurationsCumulative(), SCIPgetHmaxCumulative(), SCIPgetHminCumulative(), SCIPgetNVarsCumulative(), SCIPgetVarsCumulative(), SCIPincludeConshdlrCumulative(), SCIPpropCumulativeCondition(), SCIPsetHmaxCumulative(), SCIPsetHminCumulative(), SCIPsetSolveCumulative(), and SCIPsolveCumulative().

◆ CONSHDLR_DESC

#define CONSHDLR_DESC "cumulative constraint handler"

Definition at line 69 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY 2100000

priority of the constraint handler for separation

Definition at line 70 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY -2040000

priority of the constraint handler for constraint enforcing

Definition at line 71 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY -3030000

priority of the constraint handler for checking feasibility

Definition at line 72 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ 1

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

Definition at line 73 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ 1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 74 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ 100

frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only

Definition at line 75 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS -1

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

Definition at line 78 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA FALSE

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

Definition at line 79 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP FALSE

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

Definition at line 80 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS TRUE

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

Definition at line 81 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS

Definition at line 83 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

Definition at line 84 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_USEBINVARS

#define DEFAULT_USEBINVARS FALSE

should the binary representation be used?

Definition at line 96 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_LOCALCUTS

#define DEFAULT_LOCALCUTS FALSE

should cuts be added only locally?

Definition at line 97 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_USECOVERCUTS

#define DEFAULT_USECOVERCUTS TRUE

should covering cuts be added?

Definition at line 98 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_CUTSASCONSS

#define DEFAULT_CUTSASCONSS TRUE

should the cuts be created as knapsack constraints?

Definition at line 99 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_SEPAOLD

#define DEFAULT_SEPAOLD TRUE

shall old sepa algo be applied?

Definition at line 100 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_TTINFER

#define DEFAULT_TTINFER TRUE

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

Definition at line 103 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_EFCHECK

#define DEFAULT_EFCHECK FALSE

should edge-finding be used to detect an overload?

Definition at line 104 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_EFINFER

#define DEFAULT_EFINFER FALSE

should edge-finding be used to infer bounds?

Definition at line 105 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_USEADJUSTEDJOBS

#define DEFAULT_USEADJUSTEDJOBS FALSE

should during edge-finding jobs be adusted which run on the border of the effective time horizon?

Definition at line 106 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_TTEFCHECK

#define DEFAULT_TTEFCHECK TRUE

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

Definition at line 107 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_TTEFINFER

#define DEFAULT_TTEFINFER TRUE

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

Definition at line 108 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_DUALPRESOLVE

#define DEFAULT_DUALPRESOLVE TRUE

should dual presolving be applied?

Definition at line 111 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_COEFTIGHTENING

#define DEFAULT_COEFTIGHTENING FALSE

should coeffisient tightening be applied?

Definition at line 112 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_NORMALIZE

#define DEFAULT_NORMALIZE TRUE

should demands and capacity be normalized?

Definition at line 113 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_PRESOLPAIRWISE

#define DEFAULT_PRESOLPAIRWISE TRUE

should pairwise constraint comparison be performed in presolving?

Definition at line 114 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_DISJUNCTIVE

#define DEFAULT_DISJUNCTIVE TRUE

extract disjunctive constraints?

Definition at line 115 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_DETECTDISJUNCTIVE

#define DEFAULT_DETECTDISJUNCTIVE TRUE

search for conflict set via maximal cliques to detect disjunctive constraints

Definition at line 116 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_DETECTVARBOUNDS

#define DEFAULT_DETECTVARBOUNDS TRUE

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

Definition at line 117 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_MAXNODES

#define DEFAULT_MAXNODES 10000LL

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

Definition at line 118 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_FILLBRANCHCANDS

#define DEFAULT_FILLBRANCHCANDS FALSE

should branching candidates be added to storage?

Definition at line 121 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ DEFAULT_USEBDWIDENING

#define DEFAULT_USEBDWIDENING TRUE

should bound widening be used during conflict analysis?

Definition at line 124 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME "cumulative"

Definition at line 133 of file cons_cumulative.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludeConshdlrCumulative().

◆ EVENTHDLR_DESC

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

Definition at line 134 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

Typedef Documentation

◆ PROPRULE

typedef enum Proprule PROPRULE

Definition at line 267 of file cons_cumulative.c.

◆ INFERINFO

typedef struct InferInfo INFERINFO

Definition at line 284 of file cons_cumulative.c.

◆ SCIP_NODEDATA

typedef struct SCIP_NodeData SCIP_NODEDATA

Definition at line 5748 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 260 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 288 of file cons_cumulative.c.

References inferInfoToInt().

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

◆ inferInfoToInt()

static int inferInfoToInt ( INFERINFO inferinfo )

static

converts an inference information into an int

Parameters

inferinfo inference information to convert

Definition at line 301 of file cons_cumulative.c.

References inferInfoGetProprule().

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

◆ inferInfoGetProprule()

static PROPRULE inferInfoGetProprule ( INFERINFO inferinfo )

static

returns the propagation rule stored in the inference information

Parameters

inferinfo inference information to convert

Definition at line 310 of file cons_cumulative.c.

References inferInfoGetData1().

Referenced by getInferInfo(), inferInfoToInt(), resolvePropagationCoretimes(), 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 319 of file cons_cumulative.c.

References inferInfoGetData2().

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

◆ inferInfoGetData2()

static int inferInfoGetData2 ( INFERINFO inferinfo )

static

returns data field two of the inference information

Parameters

inferinfo inference information to convert

Definition at line 328 of file cons_cumulative.c.

References inferInfoIsValid(), and SCIP_Bool.

Referenced by inferInfoGetData1(), propagateTTEF(), resolvePropagationCoretimes(), 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 337 of file cons_cumulative.c.

References getInferInfo().

Referenced by coretimesUpdateLb(), coretimesUpdateUb(), getInferInfo(), inferboundsEdgeFinding(), inferInfoGetData2(), 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 347 of file cons_cumulative.c.

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

Referenced by coretimesUpdateLb(), coretimesUpdateUb(), inferboundsEdgeFinding(), inferInfoIsValid(), 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 388 of file cons_cumulative.c.

References computeImpliedEst(), and MAX.

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

◆ computeImpliedEst()

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

static

returns the implied earliest start time

Parameters

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

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

Referenced by computeCoreWithInterval(), and SCIPcreateWorstCaseProfile().

◆ computeImpliedLct()

static SCIP_RETCODE computeImpliedLct	(	SCIP *	scip,
		SCIP_VAR *	var,
		int	duration,
		SCIP_HASHMAP *	addedvars,
		int *	lct
	)

static

returns the implied latest completion time

Parameters

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

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

Referenced by computeImpliedEst(), and SCIPcreateWorstCaseProfile().

◆ collectBinaryVars()

static SCIP_RETCODE collectBinaryVars	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		SCIP_VAR ***	vars,
		int **	coefs,
		int *	nvars,
		int *	startindices,
		int	curtime,
		int	nstarted,
		int	nfinished
	)

static

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

Parameters

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

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

Referenced by computeImpliedLct(), and createCapacityRestriction().

◆ collectIntVars()

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

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

Referenced by collectBinaryVars(), and createCapacityRestrictionIntvars().

◆ createSortedEventpoints()

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

static

initialize the sorted event point arrays

Parameters

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

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

Referenced by collectIntVars(), consCapacityConstraintsFinder(), createSelectedSortedEventpointsSol(), and tightenCapacity().

◆ createSortedEventpointsSol()

static void createSortedEventpointsSol	(	SCIP *	scip,
		SCIP_SOL *	sol,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	starttimes,
		int *	endtimes,
		int *	startindices,
		int *	endindices
	)

static

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

Parameters

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

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

Referenced by computePeak(), and createSortedEventpoints().

◆ createSelectedSortedEventpointsSol()

static void createSelectedSortedEventpointsSol	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		SCIP_SOL *	sol,
		int *	starttimes,
		int *	endtimes,
		int *	startindices,
		int *	endindices,
		int *	nvars,
		SCIP_Bool	lower
	)

static

initialize the sorted event point arrays

Parameters

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

References createSortedEventpoints(), getActiveVar(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPsortIntInt(), SCIPstatisticPrintf, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by createSortedEventpointsSol(), and separateConsOnIntegerVariables().

◆ getActiveVar()

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

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

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

◆ computeTotalEnergy()

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

References SCIP_Longint, and setupAndSolveCumulativeSubscip().

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

◆ setupAndSolveCumulativeSubscip()

static SCIP_RETCODE setupAndSolveCumulativeSubscip	(	SCIP *	subscip,
		SCIP_Real *	objvals,
		int *	durations,
		int *	demands,
		int	njobs,
		int	capacity,
		int	hmin,
		int	hmax,
		SCIP_Longint	maxnodes,
		SCIP_Real	timelimit,
		SCIP_Real	memorylimit,
		SCIP_Real *	ests,
		SCIP_Real *	lsts,
		SCIP_Bool *	infeasible,
		SCIP_Bool *	unbounded,
		SCIP_Bool *	solved,
		SCIP_Bool *	error
	)

static

setup and solve subscip to solve single cumulative condition

Parameters

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

References FALSE, NULL, SCIP_CALL, SCIP_DECL_SOLVECUMULATIVE(), SCIP_INVALIDDATA, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PARAMEMPHASIS_CPSOLVER, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_RESTARTLIMIT, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TERMINATE, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_STATUS_USERINTERRUPT, SCIP_VARTYPE_INTEGER, SCIPaddCons(), SCIPaddVar(), SCIPallocBlockMemoryArray, SCIPcreateConsBasicCumulative(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPdebugMsg, SCIPerrorMessage, SCIPfreeBlockMemoryArray, SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetStatus(), SCIPincludeDefaultPlugins(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetBoolParam(), SCIPsetEmphasis(), SCIPsetHmaxCumulative(), SCIPsetHminCumulative(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsetSubscipsOff(), SCIPsnprintf(), SCIPsolve(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by computeTotalEnergy(), and SCIP_DECL_SOLVECUMULATIVE().

◆ SCIP_DECL_SOLVECUMULATIVE()

static SCIP_DECL_SOLVECUMULATIVE ( solveCumulativeViaScipCp )

static

solve single cumulative condition using SCIP and a single cumulative constraint

Definition at line 1411 of file cons_cumulative.c.

References conshdlrdataCreate(), FALSE, MAX, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_STATUS_USERINTERRUPT, SCIP_VARTYPE_BINARY, SCIPaddCoefKnapsack(), SCIPaddCoefSetppc(), SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPcreate(), SCIPcreateConsBasicKnapsack(), SCIPcreateConsBasicSetpart(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPdebugMessage, SCIPdebugMsg, SCIPerrorMessage, SCIPfree(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetStatus(), SCIPincludeDefaultPlugins(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsnprintf(), SCIPsolve(), SCIPvarGetUbGlobal(), setupAndSolveCumulativeSubscip(), and TRUE.

Referenced by setupAndSolveCumulativeSubscip().

◆ conshdlrdataCreate()

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

References conshdlrdataFree(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.

Referenced by SCIP_DECL_SOLVECUMULATIVE(), and SCIPincludeConshdlrCumulative().

◆ conshdlrdataFree()

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

static

frees constraint handler data for logic or constraint handler

Parameters

scip	SCIP data structure
conshdlrdata	pointer to the constraint handler data

Definition at line 1797 of file cons_cumulative.c.

References consdataCatchEvents(), NULL, and SCIPfreeBlockMemory.

Referenced by conshdlrdataCreate(), and SCIP_DECL_CONSFREE().

◆ consdataCatchEvents()

static SCIP_RETCODE consdataCatchEvents	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		SCIP_EVENTHDLR *	eventhdlr
	)

static

catches bound change events for all variables in transformed cumulative constraint

Parameters

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

Definition at line 1818 of file cons_cumulative.c.

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

Referenced by conshdlrdataFree(), SCIP_DECL_CONSTRANS(), and SCIPcreateConsCumulative().

◆ consdataDropEvents()

static SCIP_RETCODE consdataDropEvents	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		SCIP_EVENTHDLR *	eventhdlr,
		int	pos
	)

static

drops events for variable at given position

Parameters

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

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

Referenced by consdataCatchEvents(), consdataDeletePos(), and consdataDropAllEvents().

◆ consdataDropAllEvents()

static SCIP_RETCODE consdataDropAllEvents	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		SCIP_EVENTHDLR *	eventhdlr
	)

static

drops bound change events for all variables in transformed linear constraint

Parameters

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

Definition at line 1863 of file cons_cumulative.c.

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

Referenced by consdataDropEvents(), and SCIP_DECL_CONSDELETE().

◆ initializeLocks()

static void initializeLocks	(	SCIP_CONSDATA *	consdata,
		SCIP_Bool	locked
	)

static

initialize variable lock data structure

Parameters

consdata	constraint data
locked	should the variable be locked?

Definition at line 1885 of file cons_cumulative.c.

References consdataCreate().

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

◆ consdataCreate()

static SCIP_RETCODE consdataCreate	(	SCIP *	scip,
		SCIP_CONSDATA **	consdata,
		SCIP_VAR **	vars,
		SCIP_CONS **	linkingconss,
		int *	durations,
		int *	demands,
		int	nvars,
		int	capacity,
		int	hmin,
		int	hmax,
		SCIP_Bool	check
	)

static

creates constraint data of cumulative constraint

Parameters

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

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

Referenced by initializeLocks(), SCIP_DECL_CONSTRANS(), and SCIPcreateConsCumulative().

◆ consdataFreeRows()

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

static

releases LP rows of constraint data and frees rows array

Parameters

scip	SCIP data structure
consdata	constraint data

Definition at line 2035 of file cons_cumulative.c.

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

Referenced by consdataCreate(), consdataFree(), and SCIP_DECL_CONSEXITSOL().

◆ consdataFree()

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

static

frees a cumulative constraint data

Parameters

scip	SCIP data structure
consdata	pointer to linear constraint data

Definition at line 2086 of file cons_cumulative.c.

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

Referenced by consdataFreeRows(), and SCIP_DECL_CONSDELETE().

◆ consdataPrint()

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

static

prints cumulative constraint to file stream

Parameters

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

Definition at line 2135 of file cons_cumulative.c.

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

Referenced by consdataFree(), and SCIP_DECL_CONSPRINT().

◆ consdataDeletePos()

static SCIP_RETCODE consdataDeletePos	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		SCIP_CONS *	cons,
		int	pos
	)

static

deletes coefficient at given position from constraint data

Parameters

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

Definition at line 2162 of file cons_cumulative.c.

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

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

◆ consdataCollectLinkingCons()

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

static

collect linking constraints for each integer variable

Parameters

scip	SCIP data structure
consdata	pointer to consdata

Definition at line 2231 of file cons_cumulative.c.

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

Referenced by consdataDeletePos(), createRelaxation(), and separateCoverCutsCons().

◆ checkCumulativeCondition()

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

References checkCons(), FALSE, MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPinfoMessage(), SCIPisFeasIntegral(), SCIPprintCons(), SCIPrelDiff(), SCIPsortIntInt(), SCIPupdateSolConsViolation(), SCIPvarGetName(), and TRUE.

Referenced by checkCons(), consdataCollectLinkingCons(), and SCIPcheckCumulativeCondition().

◆ checkCons()

static SCIP_RETCODE checkCons	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol,
		SCIP_Bool *	violated,
		SCIP_Bool	printreason
	)

static

check if the given constrait is valid; checks each starting point of a job whether the remaining capacity is at least zero or not. If not (*violated) is set to TRUE

Parameters

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

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

Referenced by checkCumulativeCondition(), enforceConstraint(), enforceSolution(), and SCIP_DECL_CONSCHECK().

◆ resolvePropagationCoretimes()

static SCIP_RETCODE resolvePropagationCoretimes	(	SCIP *	scip,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int	capacity,
		int	hmin,
		int	hmax,
		SCIP_VAR *	infervar,
		int	inferdemand,
		int	inferpeak,
		int	relaxedpeak,
		SCIP_BDCHGIDX *	bdchgidx,
		SCIP_Bool	usebdwidening,
		int *	provedpeak,
		SCIP_Bool *	explanation
	)

static

resolves the propagation of the core time algorithm

Parameters

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

References BMSclearMemoryArray, computeOverlap(), FALSE, inferInfoGetData1(), inferInfoGetData2(), inferInfoGetProprule(), MAX, NULL, PROPRULE_2_EDGEFINDING, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIPaddConflictLb(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictUb(), SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetConflictVarLb(), SCIPgetConflictVarUb(), SCIPgetStage(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPinProbing(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPsortDownIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), and TRUE.

Referenced by analyseInfeasibelCoreInsertion(), checkCons(), and respropCumulativeCondition().

◆ computeOverlap()

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

References analyzeEnergyRequirement().

Referenced by analyzeEnergyRequirement(), and resolvePropagationCoretimes().

◆ analyzeEnergyRequirement()

static SCIP_RETCODE analyzeEnergyRequirement	(	SCIP *	scip,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int	capacity,
		int	begin,
		int	end,
		SCIP_VAR *	infervar,
		SCIP_BOUNDTYPE	boundtype,
		SCIP_BDCHGIDX *	bdchgidx,
		SCIP_Real	relaxedbd,
		SCIP_Bool	usebdwidening,
		SCIP_Bool *	explanation
	)

static

an overload was detected due to the time-time edge-finding propagate; initialized conflict analysis, add an initial reason

Note: the conflict analysis is not performend, only the initialized SCIP_Bool pointer is set to TRUE

Parameters

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

References computeOverlap(), FALSE, NULL, respropCumulativeCondition(), SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_UNKNOWN, SCIPaddConflictLb(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictUb(), SCIPallocBufferArray, SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetConflictVarLb(), SCIPgetConflictVarUb(), SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPsortDownIntIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.

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

◆ respropCumulativeCondition()

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

References analyzeEnergyRequirement(), applyAlternativeBoundsBranching(), FALSE, inferInfoGetData1(), inferInfoGetData2(), inferInfoGetProprule(), MAX, 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 analyzeEnergyRequirement(), SCIP_DECL_CONSRESPROP(), and SCIPrespropCumulativeCondition().

◆ applyAlternativeBoundsBranching()

static SCIP_RETCODE applyAlternativeBoundsBranching	(	SCIP *	scip,
		SCIP_VAR **	vars,
		int	nvars,
		int *	alternativelbs,
		int *	alternativeubs,
		int *	downlocks,
		int *	uplocks,
		SCIP_Bool *	branched
	)

static

apply all fixings which are given by the alternative bounds

Parameters

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

References NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPbranchVarHole(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPisNegative(), SCIPisPositive(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarGetUbLocal(), subtractStartingJobDemands(), and TRUE.

Referenced by propagateAllConss(), and respropCumulativeCondition().

◆ subtractStartingJobDemands()

static void subtractStartingJobDemands	(	SCIP_CONSDATA *	consdata,
		int	curtime,
		int *	starttimes,
		int *	startindices,
		int *	freecapacity,
		int *	idx,
		int	nvars
	)

static

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

Parameters

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

References addEndingJobDemands(), and NULL.

Referenced by applyAlternativeBoundsBranching(), computePeak(), consCapacityConstraintsFinder(), separateConsOnIntegerVariables(), and tightenCapacity().

◆ addEndingJobDemands()

static void addEndingJobDemands	(	SCIP_CONSDATA *	consdata,
		int	curtime,
		int *	endtimes,
		int *	endindices,
		int *	freecapacity,
		int *	idx,
		int	nvars
	)

static

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

Parameters

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

References computePeak().

Referenced by computePeak(), consCapacityConstraintsFinder(), separateConsOnIntegerVariables(), subtractStartingJobDemands(), and tightenCapacity().

◆ computePeak()

static SCIP_RETCODE computePeak	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		SCIP_SOL *	sol,
		int *	timepoint
	)

static

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

Parameters

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

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

Referenced by addEndingJobDemands(), and collectBranchingCands().

◆ collectBranchingCands()

static SCIP_RETCODE collectBranchingCands	(	SCIP *	scip,
		SCIP_CONS **	conss,
		int	nconss,
		SCIP_SOL *	sol,
		int *	nbranchcands
	)

static

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

Parameters

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

References computePeak(), enforceSolution(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddExternBranchCand(), SCIPblkmem(), SCIPconsGetData(), SCIPconsIsActive(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPgetNVars(), SCIPgetSolVal(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by computePeak(), and enforceSolution().

◆ enforceSolution()

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

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

Referenced by collectBranchingCands(), enforceConstraint(), and SCIP_DECL_CONSENFOPS().

◆ isConsIndependently()

static SCIP_Bool isConsIndependently ( SCIP_CONS * cons )

static

check if cumulative constraint is independently of all other constraints

Parameters

cons	cumulative constraint

Definition at line 3709 of file cons_cumulative.c.

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

Referenced by enforceSolution(), and solveIndependentCons().

◆ solveIndependentCons()

static SCIP_RETCODE solveIndependentCons	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_Longint	maxnodes,
		int *	nchgbds,
		int *	nfixedvars,
		int *	ndelconss,
		SCIP_Bool *	cutoff,
		SCIP_Bool *	unbounded
	)

static

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

Parameters

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

References analyseInfeasibelCoreInsertion(), FALSE, isConsIndependently(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelConsLocal(), SCIPfixVar(), SCIPfreeBufferArray, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNCheckConss(), SCIPgetNConss(), SCIPgetNVars(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPinProbing(), SCIPinRepropagation(), SCIPisInfinity(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetRealParam(), SCIPsolveCumulative(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetUbLocal(), and TRUE.

Referenced by isConsIndependently(), and presolveCons().

◆ analyseInfeasibelCoreInsertion()

static SCIP_RETCODE analyseInfeasibelCoreInsertion	(	SCIP *	scip,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int	capacity,
		int	hmin,
		int	hmax,
		SCIP_VAR *	infervar,
		int	inferduration,
		int	inferdemand,
		int	inferpeak,
		SCIP_Bool	usebdwidening,
		SCIP_Bool *	initialized,
		SCIP_Bool *	explanation
	)

static

start conflict analysis to analysis the core insertion which is infeasible

Parameters

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

References coretimesUpdateLb(), FALSE, NULL, resolvePropagationCoretimes(), SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictUb(), SCIPdebugMsg, SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by coretimesUpdateLb(), createCoreProfile(), propagateTimetable(), and solveIndependentCons().

◆ coretimesUpdateLb()

static SCIP_RETCODE coretimesUpdateLb	(	SCIP *	scip,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int	capacity,
		int	hmin,
		int	hmax,
		SCIP_CONS *	cons,
		SCIP_PROFILE *	profile,
		int	idx,
		int *	nchgbds,
		SCIP_Bool	usebdwidening,
		SCIP_Bool *	initialized,
		SCIP_Bool *	explanation,
		SCIP_Bool *	infeasible
	)

static

We are using the core resource profile which contains all core except the one of the start time variable which we want to propagate, to incease the earliest start time. This we are doing in steps of length at most the duration of the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict analysis

Parameters

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

References analyseInfeasibelCoreInsertion(), CONSHDLR_NAME, coretimesUpdateUb(), getInferInfo(), inferInfoIsValid(), inferInfoToInt(), 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 analyseInfeasibelCoreInsertion(), and propagateTimetable().

◆ coretimesUpdateUb()

static SCIP_RETCODE coretimesUpdateUb	(	SCIP *	scip,
		SCIP_VAR *	var,
		int	duration,
		int	demand,
		int	capacity,
		SCIP_CONS *	cons,
		SCIP_PROFILE *	profile,
		int	idx,
		int *	nchgbds
	)

static

We are using the core resource profile which contains all core except the one of the start time variable which we want to propagate, to decrease the latest start time. This we are doing in steps of length at most the duration of the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict analysis

Parameters

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

References computeCoreEnergyAfter(), 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 coretimesUpdateLb(), and 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 4322 of file cons_cumulative.c.

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

Referenced by coretimesUpdateUb(), and propagateTTEF().

◆ collectDataTTEF()

static void collectDataTTEF	(	SCIP *	scip,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int	hmin,
		int	hmax,
		int *	permests,
		int *	ests,
		int *	permlcts,
		int *	lcts,
		int *	ects,
		int *	lsts,
		int *	flexenergies
	)

static

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

Parameters

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

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

Referenced by computeCoreEnergyAfter(), and propagateTTEF().

◆ tightenLbTTEF()

static SCIP_RETCODE tightenLbTTEF	(	SCIP *	scip,
		SCIP_CONSHDLRDATA *	conshdlrdata,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int	capacity,
		int	hmin,
		int	hmax,
		SCIP_VAR *	var,
		int	duration,
		int	demand,
		int	est,
		int	ect,
		int	lct,
		int	begin,
		int	end,
		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 4458 of file cons_cumulative.c.

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

Referenced by collectDataTTEF(), and propagateLbTTEF().

◆ tightenUbTTEF()

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

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

Referenced by propagateUbTTEF(), and tightenLbTTEF().

◆ propagateUbTTEF()

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

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

Referenced by propagateTTEF(), and tightenUbTTEF().

◆ propagateLbTTEF()

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

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

Referenced by propagateTTEF(), and propagateUbTTEF().

◆ propagateTTEF()

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

References analyzeEnergyRequirement(), collectDataTTEF(), computeCoreEnergyAfter(), CONSHDLR_NAME, FALSE, inferInfoGetData1(), inferInfoGetData2(), inferInfoIsValid(), intToInferInfo(), NULL, propagateLbTTEF(), propagateTimetable(), propagateUbTTEF(), SCIP_Bool, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIPaddConflictLb(), SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPsortIntInt(), SCIPstatistic, SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by propagateCumulativeCondition(), and propagateLbTTEF().

◆ propagateTimetable()

static SCIP_RETCODE propagateTimetable	(	SCIP *	scip,
		SCIP_CONSHDLRDATA *	conshdlrdata,
		SCIP_PROFILE *	profile,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int	capacity,
		int	hmin,
		int	hmax,
		SCIP_CONS *	cons,
		int *	nchgbds,
		SCIP_Bool *	initialized,
		SCIP_Bool *	explanation,
		SCIP_Bool *	cutoff
	)

static

a cumulative condition is not satisfied if its capacity is exceeded at a time where jobs cannot be shifted (core) anymore we build up a cumulative profile of all cores of jobs and try to improve bounds of all jobs; also known as time table propagator

Parameters

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

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

Referenced by propagateCumulativeCondition(), and propagateTTEF().

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

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

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

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

Referenced by deleteLambdaLeaf(), and updateEnvelope().

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

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

Referenced by inferboundsEdgeFinding(), and updateKeyOnTrace().

◆ moveNodeToLambda()

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

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

Referenced by deleteLambdaLeaf(), and 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 5982 of file cons_cumulative.c.

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

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

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

Referenced by findResponsibleLambdaLeafTraceEnvelop(), and insertThetanode().

◆ findResponsibleLambdaLeafTraceEnvelop()

static SCIP_BTNODE* findResponsibleLambdaLeafTraceEnvelop ( SCIP_BTNODE * node )

static

returns the leaf responsible for the lambda envelop

Parameters

node	node which defines the subtree beases on the lambda envelop

Definition at line 6148 of file cons_cumulative.c.

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

Referenced by findResponsibleLambdaLeafTraceEnergy(), and inferboundsEdgeFinding().

◆ collectThetaSubtree()

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

static

reports all elements from set theta to generate a conflicting set

Parameters

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

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

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

◆ traceThetaEnvelop()

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

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

Referenced by collectThetaSubtree(), and traceLambdaEnvelop().

◆ traceLambdaEnergy()

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

static

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

Parameters

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

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

Referenced by traceLambdaEnvelop(), and traceThetaEnvelop().

◆ traceLambdaEnvelop()

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

static

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

Parameters

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

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

Referenced by inferboundsEdgeFinding(), and traceLambdaEnergy().

◆ computeEnergyContribution()

static int computeEnergyContribution ( SCIP_BTNODE * node )

static

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

Parameters

node leaf

Definition at line 6419 of file cons_cumulative.c.

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

Referenced by analyzeConflictOverload(), and traceLambdaEnvelop().

◆ SCIP_DECL_SORTPTRCOMP()

static SCIP_DECL_SORTPTRCOMP ( compNodeEst )

static

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

Definition at line 6443 of file cons_cumulative.c.

References SCIP_DECL_SORTINDCOMP(), and SCIPbtnodeGetData().

Referenced by computeEnergyContribution().

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

References analyzeConflictOverload().

Referenced by consdataCalcSignature(), and SCIP_DECL_SORTPTRCOMP().

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

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

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

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

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

Referenced by analyzeConflictOverload(), and inferboundsEdgeFinding().

◆ inferboundsEdgeFinding()

static SCIP_RETCODE inferboundsEdgeFinding	(	SCIP *	scip,
		SCIP_CONSHDLRDATA *	conshdlrdata,
		SCIP_CONS *	cons,
		SCIP_BT *	tree,
		SCIP_BTNODE **	leaves,
		int	capacity,
		int	ncands,
		SCIP_Bool	propest,
		int	shift,
		SCIP_Bool *	initialized,
		SCIP_Bool *	explanation,
		int *	nchgbds,
		SCIP_Bool *	cutoff
	)

static

propagates start time using an edge finding algorithm which is based on binary trees (theta lambda trees)

Note: The algorithm is based on the paper: Petr Vilim, "Edge Finding Filtering Algorithm for Discrete Cumulative Resources in O(kn log n)". *I.P. Gent (Ed.): CP 2009, LNCS 5732, pp. 802-816, 2009.

Parameters

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

References analyzeConflictOverload(), checkOverloadViaThetaTree(), 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(), and computeEstOmegaset().

◆ checkOverloadViaThetaTree()

static SCIP_RETCODE checkOverloadViaThetaTree	(	SCIP *	scip,
		SCIP_CONSHDLRDATA *	conshdlrdata,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int	capacity,
		int	hmin,
		int	hmax,
		SCIP_CONS *	cons,
		SCIP_Bool	propest,
		SCIP_Bool *	initialized,
		SCIP_Bool *	explanation,
		int *	nchgbds,
		SCIP_Bool *	cutoff
	)

static

checks whether the instance is infeasible due to a overload within a certain time frame using the idea of theta trees

Note: The algorithm is based on the paper: Petr Vilim, "Max Energy Filtering Algorithm for Discrete Cumulative Resources". In: Willem Jan van Hoeve and John N. Hooker (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2009), LNCS 5547, pp 294–308

Parameters

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

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

Referenced by inferboundsEdgeFinding(), and propagateEdgeFinding().

◆ propagateEdgeFinding()

static SCIP_RETCODE propagateEdgeFinding	(	SCIP *	scip,
		SCIP_CONSHDLRDATA *	conshdlrdata,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int	capacity,
		int	hmin,
		int	hmax,
		SCIP_CONS *	cons,
		SCIP_Bool *	initialized,
		SCIP_Bool *	explanation,
		int *	nchgbds,
		SCIP_Bool *	cutoff
	)

static

checks whether the instance is infeasible due to a overload within a certain time frame using the idea of theta trees

Note: The algorithm is based on the paper: Petr Vilim, "Max Energy Filtering Algorithm for Discrete Cumulative Resources". In: Willem Jan van Hoeve and John N. Hooker (Eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2009), LNCS 5547, pp 294–308

Parameters

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

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

Referenced by checkOverloadViaThetaTree(), and propagateCumulativeCondition().

◆ consCheckRedundancy()

static SCIP_RETCODE consCheckRedundancy	(	SCIP *	scip,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int	capacity,
		int	hmin,
		int	hmax,
		SCIP_Bool *	redundant
	)

static

checks if the constraint is redundant; that is the case if its capacity can never be exceeded; therefore we check with respect to the lower and upper bounds of the integer start time variables the maximum capacity usage for all event points

Parameters

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

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

Referenced by propagateCumulativeCondition(), and propagateEdgeFinding().

◆ createCoreProfile()

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

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

Referenced by consCheckRedundancy(), and propagateCumulativeCondition().

◆ propagateCumulativeCondition()

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

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

Referenced by createCoreProfile(), propagateCons(), and SCIPpropCumulativeCondition().

◆ propagateCons()

static SCIP_RETCODE propagateCons	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_CONSHDLRDATA *	conshdlrdata,
		SCIP_PRESOLTIMING	presoltiming,
		int *	nchgbds,
		int *	ndelconss,
		SCIP_Bool *	cutoff
	)

static

propagate the cumulative constraint

Parameters

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

References applyProbingVar(), FALSE, NULL, propagateCumulativeCondition(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_PRESOLVING, SCIPanalyzeConflictCons(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsDeleted(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPgetDepth(), SCIPgetStage(), SCIPinProbing(), SCIPresetConsAge(), and TRUE.

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

◆ applyProbingVar()

static SCIP_RETCODE applyProbingVar	(	SCIP *	scip,
		SCIP_VAR **	vars,
		int	nvars,
		int	probingpos,
		SCIP_Real	leftub,
		SCIP_Real	rightlb,
		SCIP_Real *	leftimpllbs,
		SCIP_Real *	leftimplubs,
		SCIP_Real *	leftproplbs,
		SCIP_Real *	leftpropubs,
		SCIP_Real *	rightimpllbs,
		SCIP_Real *	rightimplubs,
		SCIP_Real *	rightproplbs,
		SCIP_Real *	rightpropubs,
		int *	nfixedvars,
		SCIP_Bool *	success,
		SCIP_Bool *	cutoff
	)

static

it is dual feasible to remove the values {leftub+1, ..., rightlb-1} since SCIP current does not feature domain holes we use the probing mode to check if one of the two branches is infeasible. If this is the case the dual redundant can be realize as domain reduction. Otherwise we do nothing

Parameters

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

References FALSE, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIPapplyProbingVar(), SCIPinProbing(), SCIPinRepropagation(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and varMayRoundDown().

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

◆ varMayRoundDown()

static SCIP_RETCODE varMayRoundDown	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_Bool *	roundable
	)

static

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

Parameters

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

Definition at line 7655 of file cons_cumulative.c.

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

Referenced by applyAlternativeBoundsFixing(), applyProbingVar(), fixIntegerVariableLb(), and presolveConsEst().

◆ varMayRoundUp()

static SCIP_RETCODE varMayRoundUp	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_Bool *	roundable
	)

static

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

Parameters

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

Definition at line 7704 of file cons_cumulative.c.

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

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

◆ computeAlternativeBounds()

static SCIP_RETCODE computeAlternativeBounds	(	SCIP *	scip,
		SCIP_CONS **	conss,
		int	nconss,
		SCIP_Bool	local,
		int *	alternativelbs,
		int *	alternativeubs,
		int *	downlocks,
		int *	uplocks
	)

static

For each variable we compute an alternative lower and upper bounds. That is, if the variable is not fixed to its lower or upper bound the next reasonable lower or upper bound would be this alternative bound (implying that certain values are not of interest). An alternative bound for a particular is only valied if the cumulative constarints are the only one locking this variable in the corresponding direction.

Parameters

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

References applyAlternativeBoundsFixing(), SCIP_Profile::capacity, getActiveVar(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_MULTAGGR, SCIPcomputeHmax(), SCIPcomputeHmin(), SCIPconsGetData(), SCIPconsIsChecked(), SCIPconsIsDeleted(), SCIPconvertRealToInt(), SCIPcreateWorstCaseProfile(), SCIPprofileCreate(), SCIPprofileFree(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetStatus(), and SCIPvarGetUbLocal().

Referenced by propagateAllConss(), and varMayRoundUp().

◆ applyAlternativeBoundsFixing()

static SCIP_RETCODE applyAlternativeBoundsFixing	(	SCIP *	scip,
		SCIP_VAR **	vars,
		int	nvars,
		int *	alternativelbs,
		int *	alternativeubs,
		int *	downlocks,
		int *	uplocks,
		int *	nfixedvars,
		SCIP_Bool *	cutoff
	)

static

apply all fixings which are given by the alternative bounds

Parameters

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

References applyProbingVar(), CONSHDLR_NAME, NULL, propagateAllConss(), SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPfindConshdlr(), SCIPfixVar(), SCIPfreeBufferArray, SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetUbLocal(), varMayRoundDown(), and varMayRoundUp().

Referenced by computeAlternativeBounds(), and propagateAllConss().

◆ propagateAllConss()

static SCIP_RETCODE propagateAllConss	(	SCIP *	scip,
		SCIP_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 8047 of file cons_cumulative.c.

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

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

◆ createCoverCutsTimepoint()

static SCIP_RETCODE createCoverCutsTimepoint	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	startvalues,
		int	time
	)

static

creates covering cuts for jobs violating resource constraints

Parameters

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

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

Referenced by createCoverCuts(), and propagateAllConss().

◆ createCoverCuts()

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

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

Referenced by createCoverCutsTimepoint(), and separateCoverCutsCons().

◆ createCapacityRestriction()

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

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

Referenced by consCapacityConstraintsFinder(), and createCoverCuts().

◆ consCapacityConstraintsFinder()

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

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

Referenced by createCapacityRestriction(), and createRelaxation().

◆ createRelaxation()

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

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

Referenced by addRelaxation(), consCapacityConstraintsFinder(), and separateConsBinaryRepresentation().

◆ addRelaxation()

static SCIP_RETCODE addRelaxation	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_Bool	cutsasconss,
		SCIP_Bool *	infeasible
	)

static

adds linear relaxation of cumulative constraint to the LP

Parameters

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

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

Referenced by createRelaxation(), and SCIP_DECL_CONSINITLP().

◆ separateConsBinaryRepresentation()

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

static

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

Parameters

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

References createRelaxation(), FALSE, NULL, r, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPgetRowLPFeasibility(), SCIPgetRowSolFeasibility(), SCIPisFeasNegative(), SCIPresetConsAge(), SCIProwIsInLP(), separateCoverCutsCons(), and TRUE.

Referenced by addRelaxation(), enforceConstraint(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

◆ separateCoverCutsCons()

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

static

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

Parameters

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

References consdataCollectLinkingCons(), createCapacityRestrictionIntvars(), createCoverCuts(), FALSE, NULL, r, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPgetRowLPFeasibility(), SCIPgetRowSolFeasibility(), SCIPinfinity(), SCIPisFeasNegative(), SCIPresetConsAge(), SCIProwIsInLP(), and TRUE.

Referenced by SCIP_DECL_CONSSEPALP(), SCIP_DECL_CONSSEPASOL(), and separateConsBinaryRepresentation().

◆ createCapacityRestrictionIntvars()

static SCIP_RETCODE createCapacityRestrictionIntvars	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	startindices,
		int	curtime,
		int	nstarted,
		int	nfinished,
		SCIP_Bool	lower,
		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 9007 of file cons_cumulative.c.

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

Referenced by separateConsOnIntegerVariables(), and separateCoverCutsCons().

◆ separateConsOnIntegerVariables()

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

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

Referenced by createCapacityRestrictionIntvars(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

◆ checkDemands()

static SCIP_Bool checkDemands	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

static

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

Parameters

scip	SCIP data structure
cons	constraint to be checked

Definition at line 9181 of file cons_cumulative.c.

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

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

◆ deleteTrivilCons()

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

static

delete constraint if it consists of at most one job

Parameters

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

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

Referenced by checkDemands(), and presolveCons().

◆ removeIrrelevantJobs()

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

static

remove jobs which have a duration or demand of zero (zero energy) or lay outside the efficient horizon [hmin, hmax); this is done in the SCIP_DECL_CONSINITPRE() callback

Parameters

scip	SCIP data structure
cons	constraint to propagate

Definition at line 9264 of file cons_cumulative.c.

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

Referenced by deleteTrivilCons(), SCIP_DECL_CONSINITPRE(), and SCIP_DECL_CONSPRESOL().

◆ adjustOversizedJobBounds()

static SCIP_RETCODE adjustOversizedJobBounds	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		int	pos,
		int *	nchgbds,
		int *	naddconss,
		SCIP_Bool *	cutoff
	)

static

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

Parameters

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

References FALSE, NULL, removeOversizedJobs(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPconvertRealToInt(), SCIPcreateConsBounddisjunction(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPreleaseCons(), SCIPsnprintf(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by removeIrrelevantJobs(), and removeOversizedJobs().

◆ removeOversizedJobs()

static SCIP_RETCODE removeOversizedJobs	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	nchgbds,
		int *	nchgcoefs,
		int *	naddconss,
		SCIP_Bool *	cutoff
	)

static

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

Parameters

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

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

Referenced by adjustOversizedJobBounds(), and presolveCons().

◆ fixIntegerVariableUb()

static SCIP_RETCODE fixIntegerVariableUb	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_Bool	uplock,
		int *	nfixedvars
	)

static

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

Parameters

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

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

Referenced by presolveConsLct(), and removeOversizedJobs().

◆ fixIntegerVariableLb()

static SCIP_RETCODE fixIntegerVariableLb	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_Bool	downlock,
		int *	nfixedvars
	)

static

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

Parameters

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

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

Referenced by fixIntegerVariableUb(), and presolveConsEst().

◆ normalizeCumulativeCondition()

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

References MAX, normalizeDemands(), SCIP_Longint, SCIPcalcGreComDiv(), and SCIPdebugMsg.

Referenced by fixIntegerVariableLb(), 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 9645 of file cons_cumulative.c.

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

Referenced by normalizeCumulativeCondition(), and presolveCons().

◆ computeEffectiveHorizonCumulativeCondition()

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

static

computes for the given cumulative condition the effective horizon

Parameters

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

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

Referenced by computeEffectiveHorizon(), normalizeDemands(), and SCIPsplitCumulativeCondition().

◆ createConsCumulative()

static SCIP_RETCODE createConsCumulative	(	SCIP *	scip,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int	capacity,
		int	hmin,
		int	hmax,
		SCIP_Bool	initial,
		SCIP_Bool	separate,
		SCIP_Bool	enforce,
		SCIP_Bool	check,
		SCIP_Bool	propagate,
		SCIP_Bool	local,
		SCIP_Bool	modifiable,
		SCIP_Bool	dynamic,
		SCIP_Bool	removable,
		SCIP_Bool	stickingatnode
	)

static

creates and adds a cumulative constraint

Parameters

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

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

Referenced by computeEffectiveHorizon(), computeEffectiveHorizonCumulativeCondition(), and createDisjuctiveCons().

◆ computeEffectiveHorizon()

static SCIP_RETCODE computeEffectiveHorizon	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	ndelconss,
		int *	naddconss,
		int *	nchgsides
	)

static

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

Parameters

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

References computeEffectiveHorizonCumulativeCondition(), CONSHDLR_NAME, createConsCumulative(), NULL, presolveConsEst(), SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPdebugMsg, SCIPdelCons(), SCIPfindConshdlr(), SCIPsnprintf(), and SCIPstatistic.

Referenced by createConsCumulative(), and presolveCons().

◆ presolveConsEst()

static SCIP_RETCODE presolveConsEst	(	SCIP *	scip,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int	hmin,
		int	hmax,
		SCIP_Bool *	downlocks,
		SCIP_Bool *	uplocks,
		SCIP_CONS *	cons,
		SCIP_Bool *	irrelevants,
		int *	nfixedvars,
		int *	nchgsides,
		SCIP_Bool *	cutoff
	)

static

presolve cumulative condition w.r.t. the earlier start times (est) and the hmin of the effective horizon

(1) If the latest completion time (lct) of a job is smaller or equal than hmin, the corresponding job can be removed form the constraint. This is the case since it cannot effect any assignment within the effective horizon

(2) If the latest start time (lst) of a job is smaller or equal than hmin it follows that the this jobs can run before the effective horizon or it overlaps with the effective horizon such that hmin in included. Hence, the down-lock of the corresponding start time variable can be removed.

(3) If the earlier completion time (ect) of a job is smaller or equal than hmin, the cumulative is the only one locking the corresponding variable down, and the objective coefficient of the start time variable is not negative, than the job can be dual fixed to its earlier start time (est).

(4) If the earlier start time (est) of job is smaller than the hmin, the cumulative is the only one locking the corresponding variable down, and the objective coefficient of the start time variable is not negative, than removing the values {est+1,...,hmin} form variable domain is dual feasible.

(5) If the earlier start time (est) of job is smaller than the smallest earlier completion times of all other jobs (lets denote this with minect), the cumulative is the only one locking the corresponding variable down, and the objective coefficient of the start time variable is not negative, than removing the values {est+1,...,minect-1} form variable domain is dual feasible.

Note: That method does not remove any variable form the arrays. It only marks the variables which are irrelevant for the cumulative condition; The deletion has to be done later.

Parameters

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

References applyProbingVar(), CONSHDLR_NAME, FALSE, fixIntegerVariableLb(), MAX, NULL, presolveConsLct(), SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfixVar(), SCIPfreeBufferArray, SCIPstatistic, SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDownType(), SCIPvarGetUbGlobal(), TRUE, and varMayRoundDown().

Referenced by computeEffectiveHorizon(), presolveConsEffectiveHorizon(), and SCIPpresolveCumulativeCondition().

◆ presolveConsLct()

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

References applyProbingVar(), CONSHDLR_NAME, FALSE, fixIntegerVariableUb(), MAX, NULL, presolveConsEffectiveHorizon(), SCIP_Bool, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfixVar(), SCIPfreeBufferArray, SCIPstatistic, SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNLocksUpType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and varMayRoundUp().

Referenced by presolveConsEffectiveHorizon(), presolveConsEst(), and SCIPpresolveCumulativeCondition().

◆ presolveConsEffectiveHorizon()

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

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

Referenced by presolveCons(), and presolveConsLct().

◆ collectDemands()

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

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

Referenced by getHighestCapacityUsage(), and presolveConsEffectiveHorizon().

◆ getHighestCapacityUsage()

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

static

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

Parameters

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

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

Referenced by collectDemands(), and tightenCapacity().

◆ tightenCapacity()

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

static

try to tighten the capacity – using DP for knapsack, we find the maximum possible capacity usage – neglects hmin and hmax, such that it is also able to check solutions globally

Parameters

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

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

Referenced by getHighestCapacityUsage(), and presolveCons().

◆ tightenCoefs()

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

References createDisjuctiveCons(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVar(), SCIPaggregateVars(), SCIPconsGetData(), SCIPconsGetName(), SCIPconvertRealToInt(), SCIPcreateVar(), SCIPdebugMsg, SCIPlockVarCons(), SCIPreleaseVar(), SCIPsnprintf(), SCIPunlockVarCons(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsInitial(), SCIPvarIsRemovable(), and TRUE.

Referenced by presolveCons(), and tightenCapacity().

◆ createDisjuctiveCons()

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

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

Referenced by SCIP_DECL_CONSPRESOL(), and tightenCoefs().

◆ presolveCons()

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

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

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

◆ TCLIQUE_GETNNODES()

static TCLIQUE_GETNNODES ( tcliqueGetnnodesClique )

static

gets number of nodes in the graph

Definition at line 11185 of file cons_cumulative.c.

References NULL, and TCLIQUE_GETWEIGHTS().

Referenced by presolveCons().

◆ TCLIQUE_GETWEIGHTS()

static TCLIQUE_GETWEIGHTS ( tcliqueGetweightsClique )

static

gets weight of nodes in the graph

Definition at line 11194 of file cons_cumulative.c.

References NULL, and TCLIQUE_ISEDGE().

Referenced by TCLIQUE_GETNNODES().

◆ TCLIQUE_ISEDGE()

static TCLIQUE_ISEDGE ( tcliqueIsedgeClique )

static

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

Definition at line 11203 of file cons_cumulative.c.

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

Referenced by TCLIQUE_GETWEIGHTS().

◆ TCLIQUE_SELECTADJNODES()

static TCLIQUE_SELECTADJNODES ( tcliqueSelectadjnodesClique )

static

selects all nodes from a given set of nodes which are adjacent to a given node and returns the number of selected nodes

Definition at line 11224 of file cons_cumulative.c.

References nnodes, NULL, and TCLIQUE_NEWSOL().

Referenced by TCLIQUE_ISEDGE().

◆ TCLIQUE_NEWSOL()

static TCLIQUE_NEWSOL ( tcliqueNewsolClique )

static

generates cuts using a clique found by algorithm for maximum weight clique and decides whether to stop generating cliques with the algorithm for maximum weight clique

Definition at line 11258 of file cons_cumulative.c.

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

Referenced by TCLIQUE_SELECTADJNODES().

◆ impliesVlbPrecedenceCondition()

static SCIP_Bool impliesVlbPrecedenceCondition	(	SCIP *	scip,
		SCIP_VAR *	vlbvar,
		SCIP_Real	vlbcoef,
		SCIP_Real	vlbconst,
		int	duration
	)

static

print the tclique graph analyzes if the given variable lower bound condition implies a precedence condition w.r.t. given duration for the job corresponding to variable bound variable (vlbvar)

variable lower bound is given as: var >= vlbcoef * vlbvar + vlbconst

Parameters

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

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

Referenced by impliesVubPrecedenceCondition(), projectVbd(), and TCLIQUE_NEWSOL().

◆ impliesVubPrecedenceCondition()

static SCIP_Bool impliesVubPrecedenceCondition	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_Real	vubcoef,
		SCIP_Real	vubconst,
		int	duration
	)

static

analyzes if the given variable upper bound condition implies a precedence condition w.r.t. given duration for the job corresponding to variable which is bounded (var)

variable upper bound is given as: var <= vubcoef * vubvar + vubconst

Parameters

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

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

Referenced by impliesVlbPrecedenceCondition(), and projectVbd().

◆ getNodeIdx()

static SCIP_RETCODE getNodeIdx	(	SCIP *	scip,
		TCLIQUE_GRAPH *	tcliquegraph,
		SCIP_VAR *	var,
		int *	idx
	)

static

get the corresponding index of the given variables; this in case of an active variable the problem index and for others an index larger than the number if active variables

Parameters

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

Definition at line 11373 of file cons_cumulative.c.

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

Referenced by constraintNonOverlappingGraph(), impliesVubPrecedenceCondition(), initializeDurations(), and projectVbd().

◆ projectVbd()

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

static

use the variables bounds of SCIP to projected variables bound graph into a precedence garph

Let d be the (assumed) duration of variable x and consider a variable bound of the form b * x + c <= y. This variable bounds implies a precedence condition x -> y (meaning job y starts after job x is finished) if:

(i) b = 1 and c >= d (ii) b > 1 and lb(x) >= (d - c)/(b - 1) (iii) b < 1 and ub(x) >= (d - c)/(b - 1)

Parameters

scip	SCIP data structure
tcliquegraph	incompatibility graph

Definition at line 11464 of file cons_cumulative.c.

References b, getNodeIdx(), impliesVlbPrecedenceCondition(), impliesVubPrecedenceCondition(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetNVars(), SCIPgetVars(), SCIPisLE(), SCIPvarGetLbLocal(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), transitiveClosure(), and TRUE.

Referenced by constructIncompatibilityGraph(), and getNodeIdx().

◆ transitiveClosure()

static void transitiveClosure	(	SCIP_Bool **	adjmatrix,
		int *	ninarcs,
		int *	noutarcs,
		int	nnodes
	)

static

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

Parameters

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

References constraintNonOverlappingGraph(), nnodes, and TRUE.

Referenced by constructIncompatibilityGraph(), and projectVbd().

◆ constraintNonOverlappingGraph()

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

static

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

Parameters

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

Definition at line 11591 of file cons_cumulative.c.

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

Referenced by constructIncompatibilityGraph(), and transitiveClosure().

◆ constructIncompatibilityGraph()

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

static

constructs a conflict set graph (undirected) which contains for each job a node and edge if the corresponding pair of jobs cannot run in parallel

Parameters

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

Definition at line 11686 of file cons_cumulative.c.

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

Referenced by constraintNonOverlappingGraph(), and detectRedundantConss().

◆ createCumulativeCons()

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

static

create cumulative constraint from conflict set

Parameters

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

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

Referenced by constructIncompatibilityGraph(), and findCumulativeConss().

◆ findCumulativeConss()

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

static

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

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

Referenced by createCumulativeCons(), and detectRedundantConss().

◆ createPrecedenceCons()

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

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

Referenced by computeMinDistance(), findCumulativeConss(), and strengthenVarbounds().

◆ computeMinDistance()

static SCIP_RETCODE computeMinDistance	(	SCIP *	scip,
		TCLIQUE_GRAPH *	tcliquegraph,
		int	source,
		int	sink,
		int *	naddconss
	)

static

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

Parameters

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

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

Referenced by createPrecedenceCons(), and findPrecedenceConss().

◆ findPrecedenceConss()

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

static

search for precedence constraints

for each arc of the transitive closure of the precedence graph, we are computing a minimum distance between the corresponding two jobs

Parameters

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

Definition at line 12010 of file cons_cumulative.c.

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

Referenced by computeMinDistance(), and detectRedundantConss().

◆ initializeDurations()

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

static

initialize the assumed durations for each variable

Parameters

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

Definition at line 12078 of file cons_cumulative.c.

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

Referenced by detectRedundantConss(), and findPrecedenceConss().

◆ createTcliqueGraph()

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

static

create tclique graph

Parameters

scip	SCIP data structure
tcliquegraph	reference to the incompatibility graph

Definition at line 12122 of file cons_cumulative.c.

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

Referenced by detectRedundantConss(), and initializeDurations().

◆ freeTcliqueGraph()

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

static

frees the tclique graph

Parameters

scip	SCIP data structure
tcliquegraph	reference to the incompatibility graph

Definition at line 12203 of file cons_cumulative.c.

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

Referenced by createTcliqueGraph(), and detectRedundantConss().

◆ detectRedundantConss()

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

static

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

Parameters

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

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

Referenced by freeTcliqueGraph(), and SCIP_DECL_CONSPRESOL().

◆ consdataCalcSignature()

static void consdataCalcSignature ( SCIP_CONSDATA * consdata )

static

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

Parameters

consdata cumulative constraint data

Definition at line 12271 of file cons_cumulative.c.

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

Referenced by detectRedundantConss(), and 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 12295 of file cons_cumulative.c.

References NULL, removeRedundantConss(), 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 12308 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSPRESOL(), and SCIP_DECL_SORTINDCOMP().

◆ strengthenVarbounds()

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

static

strengthen the variable bounds using the cumulative condition

Parameters

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

References b, createPrecedenceCons(), enforceConstraint(), NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarVlb(), SCIPconsGetData(), SCIPconvertRealToInt(), SCIPdebugMsg, SCIPgetNRuns(), SCIPisEQ(), SCIPisStopped(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), and TRUE.

Referenced by removeRedundantConss(), and SCIP_DECL_CONSPRESOL().

◆ enforceConstraint()

static SCIP_RETCODE enforceConstraint	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_CONS **	conss,
		int	nconss,
		int	nusefulconss,
		SCIP_SOL *	sol,
		SCIP_Bool	solinfeasible,
		SCIP_RESULT *	result
	)

static

helper function to enforce constraints

Parameters

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

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

Referenced by SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFORELAX(), and strengthenVarbounds().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyCumulative )

static

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

Definition at line 12649 of file cons_cumulative.c.

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

Referenced by enforceConstraint().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeCumulative )

static

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

Definition at line 12667 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSHDLRCOPY().

◆ SCIP_DECL_CONSINITPRE()

static SCIP_DECL_CONSINITPRE ( consInitpreCumulative )

static

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

Definition at line 12700 of file cons_cumulative.c.

References FALSE, NULL, removeIrrelevantJobs(), SCIP_CALL, SCIP_DECL_CONSEXITPRE, SCIP_DECL_CONSEXITSOL(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPstatisticPrintf, and SCIPvisualizeConsCumulative().

Referenced by SCIP_DECL_CONSFREE().

◆ SCIP_DECL_CONSEXITSOL()

static SCIP_DECL_CONSEXITSOL ( consExitsolCumulative )

static

presolving deinitialization method of constraint handler (called after presolving has been finished) solving process deinitialization method of constraint handler (called before branch and bound process data is freed)

Definition at line 12762 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSINITPRE().

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteCumulative )

static

frees specific constraint data

Definition at line 12785 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSEXITSOL().

◆ SCIP_DECL_CONSTRANS()

static SCIP_DECL_CONSTRANS ( consTransCumulative )

static

transforms constraint data into data belonging to the transformed problem

Definition at line 12811 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSDELETE().

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpCumulative )

static

LP initialization method of constraint handler

Definition at line 12853 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSTRANS().

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpCumulative )

static

separation method of constraint handler for LP solutions

Definition at line 12890 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSINITLP().

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolCumulative )

static

separation method of constraint handler for arbitrary primal solutions

Definition at line 12954 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSSEPALP().

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpCumulative )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 13014 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSSEPASOL().

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxCumulative )

static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 13023 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSENFOLP().

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsCumulative )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 13032 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSENFORELAX().

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckCumulative )

static

feasibility check method of constraint handler for integral solutions

Definition at line 13061 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSENFOPS().

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropCumulative )

static

domain propagation method of constraint handler

Definition at line 13089 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSCHECK().

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolCumulative )

static

presolving method of constraint handler

Definition at line 13176 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSPROP().

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropCumulative )

static

propagation conflict resolving method of constraint handler

Definition at line 13297 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSPRESOL().

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockCumulative )

static

variable rounding lock method of constraint handler

Definition at line 13331 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSRESPROP().

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintCumulative )

static

constraint display method of constraint handler

Definition at line 13372 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSLOCK().

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopyCumulative )

static

constraint copying method of constraint handler

Definition at line 13385 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSPRINT().

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseCumulative )

static

constraint parsing method of constraint handler

Definition at line 13451 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSCOPY().

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsCumulative )

static

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

Definition at line 13558 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSPARSE().

◆ SCIP_DECL_CONSGETNVARS()

static SCIP_DECL_CONSGETNVARS ( consGetNVarsCumulative )

static

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

Definition at line 13580 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSGETVARS().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecCumulative )

static

execution method of event handler

Definition at line 13603 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSGETNVARS().

SCIP

Detailed Description

Macros

Functions

Inference Information Methods

Propagation

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

◆ CONSHDLR_SEPAPRIORITY

◆ CONSHDLR_ENFOPRIORITY

◆ CONSHDLR_CHECKPRIORITY

◆ CONSHDLR_SEPAFREQ

◆ CONSHDLR_PROPFREQ

◆ CONSHDLR_EAGERFREQ

◆ CONSHDLR_MAXPREROUNDS

◆ CONSHDLR_DELAYSEPA

◆ CONSHDLR_DELAYPROP

◆ CONSHDLR_NEEDSCONS

◆ CONSHDLR_PRESOLTIMING

◆ CONSHDLR_PROP_TIMING

◆ DEFAULT_USEBINVARS

◆ DEFAULT_LOCALCUTS

◆ DEFAULT_USECOVERCUTS

◆ DEFAULT_CUTSASCONSS

◆ DEFAULT_SEPAOLD

◆ DEFAULT_TTINFER

◆ DEFAULT_EFCHECK

◆ DEFAULT_EFINFER

◆ DEFAULT_USEADJUSTEDJOBS

◆ DEFAULT_TTEFCHECK

◆ DEFAULT_TTEFINFER

◆ DEFAULT_DUALPRESOLVE

◆ DEFAULT_COEFTIGHTENING

◆ DEFAULT_NORMALIZE

◆ DEFAULT_PRESOLPAIRWISE

◆ DEFAULT_DISJUNCTIVE

◆ DEFAULT_DETECTDISJUNCTIVE

◆ DEFAULT_DETECTVARBOUNDS

◆ DEFAULT_MAXNODES

◆ DEFAULT_FILLBRANCHCANDS

◆ DEFAULT_USEBDWIDENING

◆ EVENTHDLR_NAME

◆ EVENTHDLR_DESC

Typedef Documentation

◆ PROPRULE

◆ INFERINFO

◆ SCIP_NODEDATA

Enumeration Type Documentation

◆ Proprule

Function Documentation

◆ intToInferInfo()

◆ inferInfoToInt()

◆ inferInfoGetProprule()

◆ inferInfoGetData1()

◆ inferInfoGetData2()

◆ inferInfoIsValid()

◆ getInferInfo()

◆ computeCoreWithInterval()

◆ computeImpliedEst()

◆ computeImpliedLct()

◆ collectBinaryVars()

◆ collectIntVars()

◆ createSortedEventpoints()

◆ createSortedEventpointsSol()

◆ createSelectedSortedEventpointsSol()

◆ getActiveVar()

◆ computeTotalEnergy()

◆ setupAndSolveCumulativeSubscip()

◆ SCIP_DECL_SOLVECUMULATIVE()

◆ conshdlrdataCreate()

◆ conshdlrdataFree()

◆ consdataCatchEvents()

◆ consdataDropEvents()

◆ consdataDropAllEvents()

◆ initializeLocks()

◆ consdataCreate()

◆ consdataFreeRows()

◆ consdataFree()

◆ consdataPrint()