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 , their array of processing times and of their demands .
an integer resource capacity

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)

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

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

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

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

static SCIP_RETCODE	collectIntVars (SCIP scip, SCIP_CONSDATA consdata, SCIP_VAR **activevars, int startindices, int curtime, int nstarted, int nfinished, SCIP_Bool lower, int *lhs)

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

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

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

static SCIP_RETCODE	getActiveVar (SCIP scip, SCIP_VAR var, int scalar, int *constant)

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

Default method to solve a cumulative condition
static	SCIP_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_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)

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, SCIP_SOL sol, int startindices, int curtime, int nstarted, int nfinished, SCIP_Bool lower)

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

Presolving
static SCIP_Bool	checkDemands (SCIP scip, SCIP_CONS cons)

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

static SCIP_RETCODE	removeIrrelevantJobs (SCIP scip, SCIP_CONS cons)

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

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

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

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

static SCIP_RETCODE	normalizeCumulativeCondition (SCIP scip, int nvars, SCIP_VAR vars, int durations, int demands, int capacity, int nchgcoefs, int nchgsides)

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

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

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

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

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

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

static SCIP_RETCODE	presolveConsEffectiveHorizon (SCIP scip, SCIP_CONS cons, int nfixedvars, int nchgcoefs, int nchgsides, SCIP_Bool cutoff)

static SCIP_RETCODE	collectDemands (SCIP scip, SCIP_CONSDATA consdata, int startindices, int curtime, int nstarted, int nfinished, SCIP_Longint demands, int ndemands)

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

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

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

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

static SCIP_RETCODE	presolveCons (SCIP scip, SCIP_CONS cons, SCIP_CONSHDLRDATA conshdlrdata, SCIP_PRESOLTIMING presoltiming, int nfixedvars, int nchgbds, int ndelconss, int naddconss, int nchgcoefs, int nchgsides, SCIP_Bool cutoff, SCIP_Bool *unbounded)

TClique Graph callbacks
static	TCLIQUE_GETNNODES (tcliqueGetnnodesClique)

static	TCLIQUE_GETWEIGHTS (tcliqueGetweightsClique)

static	TCLIQUE_ISEDGE (tcliqueIsedgeClique)

static	TCLIQUE_SELECTADJNODES (tcliqueSelectadjnodesClique)

static	TCLIQUE_NEWSOL (tcliqueNewsolClique)

Callback methods of constraint handler
static	SCIP_DECL_CONSHDLRCOPY (conshdlrCopyCumulative)

static	SCIP_DECL_CONSFREE (consFreeCumulative)

static	SCIP_DECL_CONSINITPRE (consInitpreCumulative)

static	SCIP_DECL_CONSEXITSOL (consExitsolCumulative)

static	SCIP_DECL_CONSDELETE (consDeleteCumulative)

static	SCIP_DECL_CONSTRANS (consTransCumulative)

static	SCIP_DECL_CONSINITLP (consInitlpCumulative)

static	SCIP_DECL_CONSSEPALP (consSepalpCumulative)

static	SCIP_DECL_CONSSEPASOL (consSepasolCumulative)

static	SCIP_DECL_CONSENFOLP (consEnfolpCumulative)

static	SCIP_DECL_CONSENFOPS (consEnfopsCumulative)

static	SCIP_DECL_CONSCHECK (consCheckCumulative)

static	SCIP_DECL_CONSPROP (consPropCumulative)

static	SCIP_DECL_CONSPRESOL (consPresolCumulative)

static	SCIP_DECL_CONSRESPROP (consRespropCumulative)

static	SCIP_DECL_CONSLOCK (consLockCumulative)

static	SCIP_DECL_CONSPRINT (consPrintCumulative)

static	SCIP_DECL_CONSCOPY (consCopyCumulative)

static	SCIP_DECL_CONSPARSE (consParseCumulative)

static	SCIP_DECL_CONSGETVARS (consGetVarsCumulative)

static	SCIP_DECL_CONSGETNVARS (consGetNVarsCumulative)

Callback methods of event handler
static	SCIP_DECL_EVENTEXEC (eventExecCumulative)

Interface methods
SCIP_RETCODE	SCIPincludeConshdlrCumulative (SCIP *scip)

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

SCIP_RETCODE	SCIPcreateConsBasicCumulative (SCIP scip, SCIP_CONS cons, const char name, int nvars, SCIP_VAR *vars, int durations, int *demands, int capacity)

SCIP_RETCODE	SCIPsetHminCumulative (SCIP scip, SCIP_CONS cons, int hmin)

int	SCIPgetHminCumulative (SCIP scip, SCIP_CONS cons)

SCIP_RETCODE	SCIPsetHmaxCumulative (SCIP scip, SCIP_CONS cons, int hmax)

int	SCIPgetHmaxCumulative (SCIP scip, SCIP_CONS cons)

SCIP_VAR **	SCIPgetVarsCumulative (SCIP scip, SCIP_CONS cons)

int	SCIPgetNVarsCumulative (SCIP scip, SCIP_CONS cons)

int	SCIPgetCapacityCumulative (SCIP scip, SCIP_CONS cons)

int *	SCIPgetDurationsCumulative (SCIP scip, SCIP_CONS cons)

int *	SCIPgetDemandsCumulative (SCIP scip, SCIP_CONS cons)

SCIP_RETCODE	SCIPcheckCumulativeCondition (SCIP scip, SCIP_SOL sol, int nvars, SCIP_VAR *vars, int durations, int demands, int capacity, int hmin, int hmax, SCIP_Bool violated, SCIP_CONS *cons, SCIP_Bool printreason)

SCIP_RETCODE	SCIPnormalizeCumulativeCondition (SCIP scip, int nvars, SCIP_VAR vars, int durations, int demands, int capacity, int nchgcoefs, int nchgsides)

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

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

SCIP_RETCODE	SCIPpropCumulativeCondition (SCIP scip, SCIP_PRESOLTIMING presoltiming, int nvars, SCIP_VAR vars, int durations, int demands, int capacity, int hmin, int hmax, SCIP_CONS cons, int nchgbds, SCIP_Bool initialized, SCIP_Bool explanation, SCIP_Bool cutoff)

SCIP_RETCODE	SCIPrespropCumulativeCondition (SCIP scip, int nvars, SCIP_VAR vars, int durations, int demands, int capacity, int hmin, int hmax, SCIP_VAR infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX bdchgidx, SCIP_Real relaxedbd, SCIP_Bool explanation, SCIP_RESULT *result)

SCIP_RETCODE	SCIPvisualizeConsCumulative (SCIP scip, SCIP_CONS cons)

SCIP_RETCODE	SCIPsetSolveCumulative (SCIP scip, SCIP_DECL_SOLVECUMULATIVE((solveCumulative)))

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

SCIP_RETCODE	SCIPcreateWorstCaseProfile (SCIP scip, SCIP_PROFILE profile, int nvars, SCIP_VAR *vars, int durations, int *demands)

int	SCIPcomputeHmin (SCIP scip, SCIP_PROFILE profile, int capacity)

int	SCIPcomputeHmax (SCIP scip, SCIP_PROFILE profile, int capacity)

Inference Information Methods
An inference information can be passed with each domain reduction to SCIP. This information is passed back to the constraint handler if the corresponding bound change has to be explained. It can be used to store information which help to construct a reason/explanation for a bound change. The inference information is limited to size of integer. In case of the cumulative constraint handler we store the used propagation algorithms for that particular bound change and the earliest start and latest completion time of all jobs in the conflict set.
enum	Proprule { PROPRULE_1, PROPRULE_2, PROPRULE_3, PROPRULE_4, PROPRULE_INVALID, PROPRULE_INVALID = 0, PROPRULE_1 = 1, PROPRULE_2 = 2, PROPRULE_3 = 3, PROPRULE_4 = 4, PROPRULE_1_CORETIMES = 1, PROPRULE_2_EDGEFINDING = 2, PROPRULE_3_TTEF = 3, PROPRULE_1_RHS = 1, PROPRULE_1_LHS = 2, PROPRULE_1_RANGEDROW = 3, PROPRULE_INVALID = 0, PROPRULE_1, PROPRULE_2, PROPRULE_3, PROPRULE_4, PROPRULE_INVALID, PROPRULE_1, PROPRULE_2, PROPRULE_3, PROPRULE_4, PROPRULE_0, PROPRULE_1, PROPRULE_INTLB, PROPRULE_INTUB, PROPRULE_INVALID }

typedef enum Proprule	PROPRULE

typedef struct InferInfo	INFERINFO

static INFERINFO	intToInferInfo (int i)

static int	inferInfoToInt (INFERINFO inferinfo)

static PROPRULE	inferInfoGetProprule (INFERINFO inferinfo)

static int	inferInfoGetData1 (INFERINFO inferinfo)

static int	inferInfoGetData2 (INFERINFO inferinfo)

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

Propagation
typedef struct SCIP_NodeData	SCIP_NODEDATA

static SCIP_Bool	isConsIndependently (SCIP scip, SCIP_CONS cons)

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

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

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

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

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

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

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

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

static SCIP_RETCODE	propagateUbTTEF (SCIP scip, SCIP_CONSHDLRDATA conshdlrdata, int nvars, SCIP_VAR *vars, int durations, int demands, int capacity, int hmin, int hmax, int newlbs, int newubs, int lbinferinfos, int ubinferinfos, int lsts, int flexenergies, int perm, int ests, int lcts, int coreEnergyAfterEst, int coreEnergyAfterLct, SCIP_Bool initialized, SCIP_Bool explanation, SCIP_Bool *cutoff)

static SCIP_RETCODE	propagateLbTTEF (SCIP scip, SCIP_CONSHDLRDATA conshdlrdata, int nvars, SCIP_VAR *vars, int durations, int demands, int capacity, int hmin, int hmax, int newlbs, int newubs, int lbinferinfos, int ubinferinfos, int ects, int flexenergies, int perm, int ests, int lcts, int coreEnergyAfterEst, int coreEnergyAfterLct, SCIP_Bool initialized, SCIP_Bool explanation, SCIP_Bool *cutoff)

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

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

static SCIP_RETCODE	createNodedata (SCIP scip, SCIP_NODEDATA *nodedata)

static void	freeNodedata (SCIP scip, SCIP_NODEDATA *nodedata)

static SCIP_RETCODE	updateEnvelop (SCIP scip, SCIP_BTNODE node)

static void	updateKeyOnTrace (SCIP_BTNODE *node, SCIP_Real key)

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

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

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

static SCIP_BTNODE *	findResponsibleLambdaLeafTraceEnergy (SCIP_BTNODE *node)

static SCIP_BTNODE *	findResponsibleLambdaLeafTraceEnvelop (SCIP_BTNODE *node)

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

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

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

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

static int	computeEnergyContribution (SCIP_BTNODE *node)

static	SCIP_DECL_SORTPTRCOMP (compNodeEst)

static	SCIP_DECL_SORTPTRCOMP (compNodedataLct)

static SCIP_RETCODE	analyzeConflictOverload (SCIP scip, SCIP_BTNODE leaves, int capacity, int nleaves, int est, int lct, int reportedenergy, SCIP_Bool propest, int shift, SCIP_Bool usebdwidening, SCIP_Bool initialized, SCIP_Bool *explanation)

static int	computeEstOmegaset (SCIP *scip, int duration, int demand, int capacity, int est, int lct, int energy)

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

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

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

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

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

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

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

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

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

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

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

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

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

Macro Definition Documentation

#define CONSHDLR_NAME "cumulative"

Definition at line 58 of file cons_cumulative.c.

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

#define CONSHDLR_DESC "cumulative constraint handler"

Definition at line 59 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define CONSHDLR_SEPAPRIORITY 2100000

priority of the constraint handler for separation

Definition at line 60 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define CONSHDLR_ENFOPRIORITY -2040000

priority of the constraint handler for constraint enforcing

Definition at line 61 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define CONSHDLR_CHECKPRIORITY -3030000

priority of the constraint handler for checking feasibility

Definition at line 62 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define CONSHDLR_SEPAFREQ 1

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

Definition at line 63 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define CONSHDLR_PROPFREQ 1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 64 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define CONSHDLR_EAGERFREQ 100

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

Definition at line 65 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define CONSHDLR_MAXPREROUNDS -1

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

Definition at line 68 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define CONSHDLR_DELAYSEPA FALSE

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

Definition at line 69 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define CONSHDLR_DELAYPROP FALSE

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

Definition at line 70 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define CONSHDLR_NEEDSCONS TRUE

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

Definition at line 71 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS

Definition at line 73 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

Definition at line 74 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_USEBINVARS FALSE

should the binary representation be used?

Definition at line 86 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_LOCALCUTS FALSE

should cuts be added only locally?

Definition at line 87 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_USECOVERCUTS TRUE

should covering cuts be added?

Definition at line 88 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_CUTSASCONSS TRUE

should the cuts be created as knapsack constraints?

Definition at line 89 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_SEPAOLD TRUE

shall old sepa algo be applied?

Definition at line 90 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_TTINFER TRUE

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

Definition at line 93 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_EFCHECK FALSE

should edge-finding be used to detect an overload?

Definition at line 94 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_EFINFER FALSE

should edge-finding be used to infer bounds?

Definition at line 95 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_USEADJUSTEDJOBS FALSE

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

Definition at line 96 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_TTEFCHECK TRUE

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

Definition at line 97 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_TTEFINFER TRUE

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

Definition at line 98 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_DUALPRESOLVE TRUE

should dual presolving be applied?

Definition at line 101 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_COEFTIGHTENING FALSE

should coeffisient tightening be applied?

Definition at line 102 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_NORMALIZE TRUE

should demands and capacity be normalized?

Definition at line 103 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_PRESOLPAIRWISE TRUE

should pairwise constraint comparison be performed in presolving?

Definition at line 104 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_DISJUNCTIVE TRUE

extract disjunctive constraints?

Definition at line 105 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_DETECTDISJUNCTIVE TRUE

search for conflict set via maximal cliques to detect disjunctive constraints

Definition at line 106 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_DETECTVARBOUNDS TRUE

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

Definition at line 107 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_MAXNODES 10000LL

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

Definition at line 108 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_FILLBRANCHCANDS FALSE

should branching candidates be added to storage?

Definition at line 111 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define DEFAULT_USEBDWIDENING TRUE

should bound widening be used during conflict analysis?

Definition at line 114 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

#define EVENTHDLR_NAME "cumulative"

Definition at line 123 of file cons_cumulative.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludeConshdlrCumulative().

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

Definition at line 124 of file cons_cumulative.c.

Referenced by SCIPincludeConshdlrCumulative().

Typedef Documentation

typedef enum Proprule PROPRULE

Definition at line 257 of file cons_cumulative.c.

typedef struct InferInfo INFERINFO

Definition at line 274 of file cons_cumulative.c.

typedef struct SCIP_NodeData SCIP_NODEDATA

Definition at line 5630 of file cons_cumulative.c.

Enumeration Type Documentation

enum Proprule

Propagation rules

Enumerator
PROPRULE_1	left hand side and bounds on z -> lower bound on x
PROPRULE_2	left hand side and upper bound on x -> bound on z
PROPRULE_3	right hand side and bounds on z -> upper bound on x
PROPRULE_4	right hand side and lower bound on x -> bound on z
PROPRULE_INVALID	propagation was applied without a specific propagation rule
PROPRULE_INVALID	propagation was applied without a specific propagation rule
PROPRULE_1	v_i = FALSE => r = FALSE
PROPRULE_2	r = TRUE => v_i = TRUE for all i
PROPRULE_3	v_i = TRUE for all i => r = TRUE
PROPRULE_4	r = FALSE, v_i = TRUE for all i except j => v_j = FALSE
PROPRULE_1_CORETIMES	core-time propagator
PROPRULE_2_EDGEFINDING	edge-finder
PROPRULE_3_TTEF	time-table edeg-finding
PROPRULE_1_RHS	activity residuals of all other variables tighten bounds of single variable due to the right hand side of the inequality
PROPRULE_1_LHS	activity residuals of all other variables tighten bounds of single variable due to the left hand side of the inequality
PROPRULE_1_RANGEDROW	fixed variables and gcd of all left variables tighten bounds of a single variable in this reanged row
PROPRULE_INVALID	propagation was applied without a specific propagation rule
PROPRULE_1	v_i = TRUE => r = TRUE
PROPRULE_2	r = FALSE => v_i = FALSE for all i
PROPRULE_3	v_i = FALSE for all i => r = FALSE
PROPRULE_4	r = TRUE, v_i = FALSE for all i except j => v_j = TRUE
PROPRULE_INVALID	propagation was applied without a specific propagation rule
PROPRULE_1	left hand side and bounds on y -> lower bound on x
PROPRULE_2	left hand side and upper bound on x -> bound on y
PROPRULE_3	right hand side and bounds on y -> upper bound on x
PROPRULE_4	right hand side and lower bound on x -> bound on y
PROPRULE_0	all variables are fixed => fix integral variable
PROPRULE_1	all except one variable fixed => fix remaining variable
PROPRULE_INTLB	lower bound propagation of integral variable
PROPRULE_INTUB	upper bound propagation of integral variable
PROPRULE_INVALID	propagation was applied without a specific propagation rule

Definition at line 251 of file cons_cumulative.c.

Function Documentation

static INFERINFO intToInferInfo ( int i )

static

converts an integer into an inference information

Parameters

i	integer to convert

Definition at line 278 of file cons_cumulative.c.

References inferInfoToInt().

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

static int inferInfoToInt ( INFERINFO inferinfo )

static

converts an inference information into an int

Parameters

inferinfo inference information to convert

Definition at line 291 of file cons_cumulative.c.

References inferInfoGetProprule().

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

static PROPRULE inferInfoGetProprule ( INFERINFO inferinfo )

static

returns the propagation rule stored in the inference information

Parameters

inferinfo inference information to convert

Definition at line 300 of file cons_cumulative.c.

References inferInfoGetData1().

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

static int inferInfoGetData1 ( INFERINFO inferinfo )

static

returns data field one of the inference information

Parameters

inferinfo inference information to convert

Definition at line 309 of file cons_cumulative.c.

References inferInfoGetData2().

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

static int inferInfoGetData2 ( INFERINFO inferinfo )

static

returns data field two of the inference information

Parameters

inferinfo inference information to convert

Definition at line 318 of file cons_cumulative.c.

References getInferInfo().

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

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

References computeCoreWithInterval().

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

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

static

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

Parameters

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

Definition at line 363 of file cons_cumulative.c.

References computeImpliedEst(), MAX, and MIN.

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

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

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

Referenced by computeCoreWithInterval(), and SCIPcreateWorstCaseProfile().

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

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

Referenced by computeImpliedEst(), and SCIPcreateWorstCaseProfile().

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

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

Referenced by computeImpliedLct(), and createCapacityRestriction().

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

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

Referenced by collectBinaryVars(), and createCapacityRestrictionIntvars().

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

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

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

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

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

Referenced by computePeak(), and createSortedEventpoints().

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

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

Referenced by createSortedEventpointsSol(), and separateConsOnIntegerVariables().

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

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

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

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

References SCIP_DECL_SOLVECUMULATIVE().

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

static SCIP_DECL_SOLVECUMULATIVE ( solveCumulativeViaScipCp )

static

solve single cumulative condition using SCIP and a single cumulative constraint

Definition at line 1225 of file cons_cumulative.c.

References conshdlrdataCreate(), FALSE, MAX, MIN, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PARAMEMPHASIS_CPSOLVER, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_RESTARTLIMIT, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_STATUS_USERINTERRUPT, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPaddCoefKnapsack(), SCIPaddCoefSetppc(), SCIPaddCons(), SCIPaddVar(), SCIPallocMemoryArray, SCIPcreate(), SCIPcreateConsBasicCumulative(), SCIPcreateConsBasicKnapsack(), SCIPcreateConsBasicSetpart(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPdebugMessage, SCIPerrorMessage, SCIPfree(), SCIPfreeMemoryArray, SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetStatus(), SCIPincludeDefaultPlugins(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetBoolParam(), SCIPsetEmphasis(), SCIPsetHmaxCumulative(), SCIPsetHminCumulative(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsetSubscipsOff(), SCIPsnprintf(), SCIPsolve(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by computeTotalEnergy().

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

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

Referenced by SCIP_DECL_SOLVECUMULATIVE(), and SCIPincludeConshdlrCumulative().

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

References consdataCatchEvents(), NULL, and SCIPfreeMemory.

Referenced by conshdlrdataCreate(), and SCIP_DECL_CONSFREE().

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

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

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

Referenced by consdataCatchEvents(), consdataDeletePos(), and 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 1802 of file cons_cumulative.c.

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

Referenced by consdataDropEvents(), and SCIP_DECL_CONSDELETE().

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

References consdataCreate().

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

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

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

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

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

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

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

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

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

Referenced by consdataFreeRows(), and SCIP_DECL_CONSDELETE().

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

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

Referenced by consdataFree(), and SCIP_DECL_CONSPRINT().

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

References analyzeEnergyRequirement().

Referenced by analyzeEnergyRequirement(), and resolvePropagationCoretimes().

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

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

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

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

References analyzeEnergyRequirement(), applyAlternativeBoundsBranching(), FALSE, inferInfoGetData1(), inferInfoGetData2(), inferInfoGetProprule(), MAX, MIN, NULL, PROPRULE_1_CORETIMES, PROPRULE_2_EDGEFINDING, PROPRULE_3_TTEF, resolvePropagationCoretimes(), SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPABORT, SCIPaddConflictLb(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictUb(), SCIPconvertRealToInt(), SCIPdebugMessage, SCIPerrorMessage, SCIPvarGetLbAtIndex(), SCIPvarGetName(), SCIPvarGetUbAtIndex(), and TRUE.

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

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

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbranchVarHole(), SCIPconvertRealToInt(), SCIPdebugMessage, SCIPisNegative(), SCIPisPositive(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetObj(), SCIPvarGetUbLocal(), subtractStartingJobDemands(), and TRUE.

Referenced by propagateAllConss(), and respropCumulativeCondition().

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

References addEndingJobDemands(), and NULL.

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

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

References computePeak().

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

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

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

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

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

Referenced by computePeak(), and enforceSolution().

static SCIP_RETCODE enforceSolution	(	SCIP *	scip,
		SCIP_CONS **	conss,
		int	nconss,
		SCIP_Bool	branch,
		SCIP_RESULT *	result
	)

static

enforcement pseudo or LP solution

Parameters

scip	SCIP data structure
conss	constraints to be processed
nconss	number of constraints
branch	should branching candidates be collected
result	pointer to store the result

Definition at line 3569 of file cons_cumulative.c.

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

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

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

static

check if cumulative constraint is independently of all other constraints

Parameters

scip	SCIP data structure
cons	cumulative constraint

Definition at line 3621 of file cons_cumulative.c.

References FALSE, NULL, SCIP_Bool, SCIPconsGetData(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), solveIndependentCons(), and TRUE.

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

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

Referenced by isConsIndependently(), and presolveCons().

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

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

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

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

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

Referenced by analyseInfeasibelCoreInsertion(), and propagateTimetable().

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

References computeCoreEngeryAfter(), CONSHDLR_NAME, getInferInfo(), inferInfoToInt(), MAX, NULL, PROPRULE_1_CORETIMES, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconshdlrGetData(), SCIPconvertRealToInt(), SCIPdebug, SCIPdebugMessage, SCIPfindConshdlr(), SCIPgetMessagehdlr(), SCIPinferVarUbCons(), SCIPprofileFindLeft(), SCIPprofileGetLoad(), SCIPprofileGetNTimepoints(), SCIPprofileGetTime(), SCIPprofilePrint(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by coretimesUpdateLb(), and propagateTimetable().

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

static

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

Parameters

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

Definition at line 4218 of file cons_cumulative.c.

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

Referenced by coretimesUpdateUb(), and propagateTTEF().

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

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

Referenced by computeCoreEngeryAfter(), and propagateTTEF().

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

static

try to tighten the lower bound of the given variable

Parameters

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

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

Referenced by collectDataTTEF(), and propagateLbTTEF().

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

static

try to tighten the upper bound of the given variable

Parameters

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

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

Referenced by propagateUbTTEF(), and tightenLbTTEF().

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

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

Referenced by propagateTTEF(), and tightenUbTTEF().

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

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

Referenced by propagateTTEF(), and propagateUbTTEF().

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

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

Referenced by propagateCumulativeCondition(), and propagateLbTTEF().

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

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

Referenced by propagateCumulativeCondition(), and propagateTTEF().

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

static

creates a node data structure

Parameters

scip	SCIP data structure
nodedata	pointer to store the create node data

Definition at line 5634 of file cons_cumulative.c.

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

Referenced by checkOverloadViaThetaTree(), and insertThetanode().

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

static

frees a node data structure

Parameters

scip	SCIP data structure
nodedata	pointer to store node data which should be freed

Definition at line 5658 of file cons_cumulative.c.

References NULL, SCIPfreeBuffer, and updateEnvelop().

Referenced by checkOverloadViaThetaTree(), and createNodedata().

static SCIP_RETCODE updateEnvelop	(	SCIP *	scip,
		SCIP_BTNODE *	node
	)

static

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

Parameters

scip	SCIP data structure
node	search node which inserted

Definition at line 5671 of file cons_cumulative.c.

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

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

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

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

Referenced by deleteLambdaLeaf(), and updateEnvelop().

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

References moveNodeToLambda(), NULL, SCIP_CALL, SCIP_OKAY, SCIPbtnodeFree(), SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPbtnodeIsLeftchild(), SCIPbtnodeIsRightchild(), SCIPbtnodeIsRoot(), SCIPbtnodeSetLeftchild(), SCIPbtnodeSetParent(), SCIPbtnodeSetRightchild(), SCIPbtSetRoot(), SCIPdebugMessage, updateEnvelop(), and updateKeyOnTrace().

Referenced by inferboundsEdgeFinding(), and updateKeyOnTrace().

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

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

Referenced by deleteLambdaLeaf(), and inferboundsEdgeFinding().

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

static

inserts a node into the theta set and update the envelops

Parameters

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

Definition at line 5903 of file cons_cumulative.c.

References createNodedata(), findResponsibleLambdaLeafTraceEnergy(), NULL, SCIP_CALL, SCIP_OKAY, SCIPbtGetRoot(), SCIPbtIsEmpty(), SCIPbtnodeCreate(), SCIPbtnodeGetData(), SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsLeaf(), SCIPbtnodeSetLeftchild(), SCIPbtnodeSetParent(), SCIPbtnodeSetRightchild(), SCIPbtSetRoot(), and updateEnvelop().

Referenced by checkOverloadViaThetaTree(), and moveNodeToLambda().

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

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

Referenced by findResponsibleLambdaLeafTraceEnvelop(), and insertThetanode().

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

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

Referenced by findResponsibleLambdaLeafTraceEnergy(), and inferboundsEdgeFinding().

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

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

Referenced by findResponsibleLambdaLeafTraceEnvelop(), traceLambdaEnergy(), traceLambdaEnvelop(), and 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 6144 of file cons_cumulative.c.

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

Referenced by collectThetaSubtree(), and traceLambdaEnvelop().

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

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

Referenced by traceLambdaEnvelop(), and traceThetaEnvelop().

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

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

Referenced by inferboundsEdgeFinding(), and traceLambdaEnergy().

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

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

Referenced by analyzeConflictOverload(), and traceLambdaEnvelop().

static SCIP_DECL_SORTPTRCOMP ( compNodeEst )

static

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

Definition at line 6352 of file cons_cumulative.c.

References SCIPbtnodeGetData().

Referenced by computeEnergyContribution().

static SCIP_DECL_SORTPTRCOMP ( compNodedataLct )

static

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

Definition at line 6365 of file cons_cumulative.c.

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

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

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

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

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

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

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

Referenced by checkOverloadViaThetaTree(), and computeEstOmegaset().

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

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

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

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

Referenced by checkOverloadViaThetaTree(), and propagateCumulativeCondition().

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

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

Referenced by propagateCumulativeCondition(), and propagateEdgeFinding().

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Referenced by computeAlternativeBounds(), and propagateAllConss().

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

static

propagate all constraints together

Parameters

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

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

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

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

Referenced by createCoverCuts(), and propagateAllConss().

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

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

Referenced by createCoverCutsTimepoint(), and separateCoverCutsCons().

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

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

Referenced by consCapacityConstraintsFinder(), and createCoverCuts().

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

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

Referenced by createCapacityRestriction(), and 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 8625 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().

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

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?

Definition at line 8668 of file cons_cumulative.c.

References createRelaxation(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddCut(), SCIPconsGetData(), SCIProwIsInLP(), and separateConsBinaryRepresentation().

Referenced by createRelaxation(), and SCIP_DECL_CONSINITLP().

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

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

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

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

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

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

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

static

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

Parameters

scip	SCIP data structure
cons	constraint to be checked
sol	primal CIP solution, NULL for current LP solution
startindices	permutation with rspect to the start times
curtime	current point in time
nstarted	number of jobs that start before the curtime or at curtime
nfinished	number of jobs that finished before curtime or at curtime
lower	shall cuts be created due to lower or upper bounds?

Definition at line 8890 of file cons_cumulative.c.

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

Referenced by separateConsOnIntegerVariables(), and separateCoverCutsCons().

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

static

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

Parameters

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

Definition at line 8959 of file cons_cumulative.c.

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

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

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

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

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

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

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

Referenced by checkDemands(), and presolveCons().

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

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

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

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 9214 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(), SCIPdebugMessage, SCIPdebugPrintCons, SCIPreleaseCons(), SCIPsnprintf(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and TRUE.

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

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

Referenced by adjustOversizedJobBounds(), and presolveCons().

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

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

Referenced by presolveConsLct(), and removeOversizedJobs().

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

References FALSE, normalizeCumulativeCondition(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPfixVar(), SCIPinProbing(), SCIPinRepropagation(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), TRUE, and varMayRoundDown().

Referenced by fixIntegerVariableUb(), and presolveConsEst().

static SCIP_RETCODE normalizeCumulativeCondition	(	SCIP *	scip,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int *	capacity,
		int *	nchgcoefs,
		int *	nchgsides
	)

static

normalize cumulative condition

Parameters

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

Definition at line 9460 of file cons_cumulative.c.

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

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

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

static

divides demands by their greatest common divisor and divides capacity by the same value, rounding down the result; in case the the smallest demands add up to more than the capacity we reductions all demands to one as well as the capacity since in that case none of the jobs can run in parallel

Parameters

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

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

Referenced by normalizeCumulativeCondition(), and presolveCons().

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

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

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

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

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

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

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 9706 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(), SCIPdebugMessage, SCIPdelCons(), SCIPfindConshdlr(), SCIPsnprintf(), and SCIPstatistic.

Referenced by createConsCumulative(), and presolveCons().

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

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

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

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

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

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

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

static SCIP_RETCODE collectDemands	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		int *	startindices,
		int	curtime,
		int	nstarted,
		int	nfinished,
		SCIP_Longint **	demands,
		int *	ndemands
	)

static

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

Parameters

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

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

Referenced by getHighestCapacityUsage(), and presolveConsEffectiveHorizon().

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

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

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

Referenced by getHighestCapacityUsage(), and presolveCons().

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

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

Referenced by presolveCons(), and tightenCapacity().

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

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

Referenced by SCIP_DECL_CONSPRESOL(), and tightenCoefs().

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

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

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

static TCLIQUE_GETNNODES ( tcliqueGetnnodesClique )

static

gets number of nodes in the graph

Definition at line 11083 of file cons_cumulative.c.

References NULL, and TCLIQUE_GETWEIGHTS().

Referenced by presolveCons().

static TCLIQUE_GETWEIGHTS ( tcliqueGetweightsClique )

static

gets weight of nodes in the graph

Definition at line 11092 of file cons_cumulative.c.

References NULL, and TCLIQUE_ISEDGE().

Referenced by TCLIQUE_GETNNODES().

static TCLIQUE_ISEDGE ( tcliqueIsedgeClique )

static

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

Definition at line 11101 of file cons_cumulative.c.

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

Referenced by TCLIQUE_GETWEIGHTS().

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

References NULL, and TCLIQUE_NEWSOL().

Referenced by TCLIQUE_ISEDGE().

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

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

Referenced by TCLIQUE_SELECTADJNODES().

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

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

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

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

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

Referenced by impliesVlbPrecedenceCondition(), and projectVbd().

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

References BMSclearMemoryArray, projectVbd(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPreallocBufferArray, and SCIPvarGetProbindex().

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

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

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

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

References constraintNonOverlappingGraph(), and TRUE.

Referenced by constructIncompatibilityGraph(), and projectVbd().

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

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

Referenced by constructIncompatibilityGraph(), and transitiveClosure().

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

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

Referenced by constraintNonOverlappingGraph(), and detectRedundantConss().

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

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

Referenced by constructIncompatibilityGraph(), and findCumulativeConss().

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

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

Referenced by createCumulativeCons(), and detectRedundantConss().

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

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

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

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

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

Referenced by computeMinDistance(), and detectRedundantConss().

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

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

Referenced by detectRedundantConss(), and findPrecedenceConss().

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

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

Referenced by detectRedundantConss(), and initializeDurations().

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

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

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

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

Referenced by freeTcliqueGraph(), and SCIP_DECL_CONSPRESOL().

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

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

Referenced by detectRedundantConss(), and removeRedundantConss().

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

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

Referenced by consdataCalcSignature().

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

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

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

Referenced by removeRedundantConss(), and SCIP_DECL_CONSPRESOL().

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyCumulative )

static

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

Definition at line 12451 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 strengthenVarbounds().

static SCIP_DECL_CONSFREE ( consFreeCumulative )

static

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

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

static SCIP_DECL_CONSINITPRE ( consInitpreCumulative )

static

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

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

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

static SCIP_DECL_CONSDELETE ( consDeleteCumulative )

static

frees specific constraint data

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

static SCIP_DECL_CONSTRANS ( consTransCumulative )

static

transforms constraint data into data belonging to the transformed problem

Definition at line 12613 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(), SCIPdebugMessage, and SCIPgetStage().

Referenced by SCIP_DECL_CONSDELETE().

static SCIP_DECL_CONSINITLP ( consInitlpCumulative )

static

LP initialization method of constraint handler

Definition at line 12655 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSTRANS().

static SCIP_DECL_CONSSEPALP ( consSepalpCumulative )

static

separation method of constraint handler for LP solutions

Definition at line 12690 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_REDUCEDDOM, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMessage, SCIPgetDepth(), separateConsBinaryRepresentation(), separateConsOnIntegerVariables(), separateCoverCutsCons(), and TRUE.

Referenced by SCIP_DECL_CONSINITLP().

static SCIP_DECL_CONSSEPASOL ( consSepasolCumulative )

static

separation method of constraint handler for arbitrary primal solutions

Definition at line 12758 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSSEPALP().

static SCIP_DECL_CONSENFOLP ( consEnfolpCumulative )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 12822 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSSEPASOL().

static SCIP_DECL_CONSENFOPS ( consEnfopsCumulative )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 12908 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSENFOLP().

static SCIP_DECL_CONSCHECK ( consCheckCumulative )

static

feasibility check method of constraint handler for integral solutions

Definition at line 12937 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 SCIPdebugMessage.

Referenced by SCIP_DECL_CONSENFOPS().

static SCIP_DECL_CONSPROP ( consPropCumulative )

static

domain propagation method of constraint handler

Definition at line 12966 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, SCIPallowDualReds(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsDeleted(), SCIPdebugMessage, SCIPgetDepth(), and TRUE.

Referenced by SCIP_DECL_CONSCHECK().

static SCIP_DECL_CONSPRESOL ( consPresolCumulative )

static

presolving method of constraint handler

Definition at line 13053 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, SCIPallowDualReds(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsDeleted(), SCIPdebugMessage, SCIPgetNRuns(), strengthenVarbounds(), and TRUE.

Referenced by SCIP_DECL_CONSPROP().

static SCIP_DECL_CONSRESPROP ( consRespropCumulative )

static

propagation conflict resolving method of constraint handler

Definition at line 13175 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSPRESOL().

static SCIP_DECL_CONSLOCK ( consLockCumulative )

static

variable rounding lock method of constraint handler

Definition at line 13209 of file cons_cumulative.c.

References NULL, SCIP_CALL, SCIP_DECL_CONSPRINT(), SCIP_OKAY, SCIPaddVarLocks(), SCIPconsGetData(), SCIPconsGetName(), and SCIPdebugMessage.

Referenced by SCIP_DECL_CONSRESPROP().

static SCIP_DECL_CONSPRINT ( consPrintCumulative )

static

constraint display method of constraint handler

Definition at line 13249 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSLOCK().

static SCIP_DECL_CONSCOPY ( consCopyCumulative )

static

constraint copying method of constraint handler

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

static SCIP_DECL_CONSPARSE ( consParseCumulative )

static

constraint parsing method of constraint handler

Definition at line 13328 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSCOPY().

static SCIP_DECL_CONSGETVARS ( consGetVarsCumulative )

static

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

Definition at line 13423 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSPARSE().

static SCIP_DECL_CONSGETNVARS ( consGetNVarsCumulative )

static

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

Definition at line 13445 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSGETVARS().

static SCIP_DECL_EVENTEXEC ( eventExecCumulative )

static

execution method of event handler

Definition at line 13468 of file cons_cumulative.c.

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

Referenced by SCIP_DECL_CONSGETNVARS().

SCIP_RETCODE SCIPincludeConshdlrCumulative ( SCIP * scip )

creates the handler for cumulative constraints and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 13499 of file cons_cumulative.c.

References CONSHDLR_CHECKPRIORITY, CONSHDLR_DELAYPROP, CONSHDLR_DELAYSEPA, CONSHDLR_DESC, CONSHDLR_EAGERFREQ, CONSHDLR_ENFOPRIORITY, CONSHDLR_MAXPREROUNDS, CONSHDLR_NAME, CONSHDLR_NEEDSCONS, CONSHDLR_PRESOLTIMING, CONSHDLR_PROP_TIMING, CONSHDLR_PROPFREQ, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, conshdlrdataCreate(), DEFAULT_COEFTIGHTENING, DEFAULT_CUTSASCONSS, DEFAULT_DETECTDISJUNCTIVE, DEFAULT_DETECTVARBOUNDS, DEFAULT_DISJUNCTIVE, DEFAULT_DUALPRESOLVE, DEFAULT_EFCHECK, DEFAULT_EFINFER, DEFAULT_FILLBRANCHCANDS, DEFAULT_LOCALCUTS, DEFAULT_MAXNODES, DEFAULT_NORMALIZE, DEFAULT_PRESOLPAIRWISE, DEFAULT_SEPAOLD, DEFAULT_TTEFCHECK, DEFAULT_TTEFINFER, DEFAULT_TTINFER, DEFAULT_USEADJUSTEDJOBS, DEFAULT_USEBDWIDENING, DEFAULT_USEBINVARS, DEFAULT_USECOVERCUTS, EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_LONGINT_MAX, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddLongintParam(), SCIPcreateConsCumulative(), SCIPincludeConshdlrBasic(), SCIPincludeEventhdlrBasic(), SCIPsetConshdlrCopy(), SCIPsetConshdlrDelete(), SCIPsetConshdlrExitpre(), SCIPsetConshdlrExitsol(), SCIPsetConshdlrFree(), SCIPsetConshdlrGetNVars(), SCIPsetConshdlrGetVars(), SCIPsetConshdlrInitlp(), SCIPsetConshdlrInitpre(), SCIPsetConshdlrParse(), SCIPsetConshdlrPresol(), SCIPsetConshdlrPrint(), SCIPsetConshdlrProp(), SCIPsetConshdlrResprop(), SCIPsetConshdlrSepa(), SCIPsetConshdlrTrans(), and TRUE.

Referenced by SCIP_DECL_CONSHDLRCOPY(), SCIP_DECL_EVENTEXEC(), and SCIPincludeDefaultPlugins().

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
	)

creates and captures a cumulative constraint

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
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
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 13629 of file cons_cumulative.c.

References consdataCatchEvents(), consdataCreate(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_STAGE_PROBLEM, SCIPconshdlrGetData(), SCIPcreateCons(), SCIPcreateConsBasicCumulative(), SCIPdebugMessage, SCIPerrorMessage, SCIPfindConshdlr(), and SCIPgetStage().

Referenced by CREATE_CONSTRAINT(), createConsCumulative(), createCumulativeCons(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSPARSE(), SCIPcreateConsBasicCumulative(), and SCIPincludeConshdlrCumulative().

SCIP_RETCODE SCIPcreateConsBasicCumulative	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int	capacity
	)

creates and captures a cumulative constraint in its most basic version, i. e., all constraint flags are set to their basic value as explained for the method SCIPcreateConsCumulative(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h

See also: SCIPcreateConsCumulative() for information about the basic constraint flag configuration

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
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

Definition at line 13711 of file cons_cumulative.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateConsCumulative(), SCIPsetHminCumulative(), and TRUE.

Referenced by SCIP_DECL_SOLVECUMULATIVE(), and SCIPcreateConsCumulative().

SCIP_RETCODE SCIPsetHminCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int	hmin
	)

set the left bound of the time axis to be considered (including hmin)

Parameters

scip	SCIP data structure
cons	constraint data
hmin	left bound of time axis to be considered

Definition at line 13731 of file cons_cumulative.c.

References CONSHDLR_NAME, NULL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetHminCumulative().

Referenced by createConsCumulative(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSPARSE(), SCIP_DECL_SOLVECUMULATIVE(), and SCIPcreateConsBasicCumulative().

int SCIPgetHminCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns the left bound of the time axis to be considered

Parameters

scip	SCIP data structure
cons	constraint

Definition at line 13755 of file cons_cumulative.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPsetHmaxCumulative().

Referenced by SCIP_DECL_CONSRESPROP(), and SCIPsetHminCumulative().

SCIP_RETCODE SCIPsetHmaxCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int	hmax
	)

set the right bound of the time axis to be considered (not including hmax)

Parameters

scip	SCIP data structure
cons	constraint data
hmax	right bound of time axis to be considered

Definition at line 13775 of file cons_cumulative.c.

References CONSHDLR_NAME, NULL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetHmaxCumulative().

Referenced by createConsCumulative(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSPARSE(), SCIP_DECL_SOLVECUMULATIVE(), and SCIPgetHminCumulative().

int SCIPgetHmaxCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns the right bound of the time axis to be considered

Parameters

scip	SCIP data structure
cons	constraint

Definition at line 13799 of file cons_cumulative.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetVarsCumulative().

Referenced by SCIP_DECL_CONSRESPROP(), and SCIPsetHmaxCumulative().

SCIP_VAR** SCIPgetVarsCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns the activities of the cumulative constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 13819 of file cons_cumulative.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetNVarsCumulative().

Referenced by SCIPgetHmaxCumulative(), and writeFzn().

int SCIPgetNVarsCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns the activities of the cumulative constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 13840 of file cons_cumulative.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetCapacityCumulative().

Referenced by SCIPgetVarsCumulative(), and writeFzn().

int SCIPgetCapacityCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns the capacity of the cumulative constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 13861 of file cons_cumulative.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetDurationsCumulative().

Referenced by SCIPgetNVarsCumulative(), and writeFzn().

int* SCIPgetDurationsCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns the durations of the cumulative constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 13882 of file cons_cumulative.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPerrorMessage, and SCIPgetDemandsCumulative().

Referenced by SCIPgetCapacityCumulative(), and writeFzn().

int* SCIPgetDemandsCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns the demands of the cumulative constraint

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 13903 of file cons_cumulative.c.

References CONSHDLR_NAME, NULL, SCIPABORT, SCIPcheckCumulativeCondition(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetName(), and SCIPerrorMessage.

Referenced by SCIPgetDurationsCumulative(), and writeFzn().

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
	)

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

References checkCumulativeCondition(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPnormalizeCumulativeCondition().

Referenced by SCIPgetDemandsCumulative().

SCIP_RETCODE SCIPnormalizeCumulativeCondition	(	SCIP *	scip,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands,
		int *	capacity,
		int *	nchgcoefs,
		int *	nchgsides
	)

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

References normalizeCumulativeCondition(), SCIP_CALL, SCIP_OKAY, and SCIPsplitCumulativeCondition().

Referenced by SCIPcheckCumulativeCondition().

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

searches for a time point within the cumulative condition were the cumulative condition can be split

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

References computeEffectiveHorizonCumulativeCondition(), SCIP_CALL, SCIP_OKAY, and SCIPpresolveCumulativeCondition().

Referenced by SCIPnormalizeCumulativeCondition().

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
	)

presolve cumulative condition w.r.t. effective horizon by detecting irrelevant variables

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
hmax	right bound of time axis to be considered (not including hmax)
downlocks	array storing if the variable has a down lock, or NULL
uplocks	array storing if the variable has an up lock, or NULL
cons	constraint which gets propagated, 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 13988 of file cons_cumulative.c.

References presolveConsEst(), presolveConsLct(), SCIP_CALL, SCIP_OKAY, and SCIPpropCumulativeCondition().

Referenced by SCIPsplitCumulativeCondition().

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
	)

propagate the given cumulative condition

Parameters

scip	SCIP data structure
presoltiming	current presolving timing
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)
cons	constraint which gets propagated
nchgbds	pointer to store the number of variable 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 cumulative condition is violated

Definition at line 14019 of file cons_cumulative.c.

References CONSHDLR_NAME, FALSE, NULL, propagateCumulativeCondition(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPconshdlrGetData(), SCIPerrorMessage, SCIPfindConshdlr(), and SCIPrespropCumulativeCondition().

Referenced by SCIPpresolveCumulativeCondition().

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
	)

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

References intToInferInfo(), respropCumulativeCondition(), SCIP_CALL, SCIP_OKAY, SCIPvisualizeConsCumulative(), and TRUE.

Referenced by SCIPpropCumulativeCondition().

SCIP_RETCODE SCIPvisualizeConsCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

this method visualizes the cumulative structure in GML format

Parameters

scip	SCIP data structure
cons	cumulative constraint

Definition at line 14093 of file cons_cumulative.c.

References NULL, SCIP_CALL, SCIP_FILECREATEERROR, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPblkmem(), SCIPcalcHashtableSize(), SCIPconsGetData(), SCIPconsGetName(), SCIPerrorMessage, SCIPgmlWriteArc(), SCIPgmlWriteClosing(), SCIPgmlWriteNode(), SCIPgmlWriteOpening(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPprintSysError(), SCIPsetSolveCumulative(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetUbGlobal(), SCIPvarGetVlbVars(), SCIPvarGetVubVars(), and TRUE.

Referenced by SCIP_DECL_CONSINITPRE(), and SCIPrespropCumulativeCondition().

SCIP_RETCODE SCIPsetSolveCumulative	(	SCIP *	scip,
		SCIP_DECL_SOLVECUMULATIVE((*solveCumulative))
	)

sets method to solve an individual cumulative condition

Parameters

scip	SCIP data structure

Definition at line 14194 of file cons_cumulative.c.

References CONSHDLR_NAME, NULL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPconshdlrGetData(), SCIPerrorMessage, SCIPfindConshdlr(), and SCIPsolveCumulative().

Referenced by SCIPvisualizeConsCumulative().

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
	)

solves given cumulative condition as independent sub problem

Note: If the problem was solved to the earliest start times (ests) and latest start times (lsts) array contain the solution values; If the problem was not solved these two arrays contain the global bounds at the time the sub solver was interrupted.

Parameters

scip	SCIP data structure
njobs	number of jobs (activities)
ests	array with the earlier start time for each job
lsts	array with the latest start time for each job
objvals	array of objective coefficients for each job (linear objective function), or NULL if none
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)
timelimit	time limit for solving in seconds
memorylimit	memory limit for solving in mega bytes (MB)
maxnodes	maximum number of branch-and-bound nodes to solve the single cumulative constraint (-1: no limit)
solved	pointer to store if the problem is solved (to optimality)
infeasible	pointer to store if the problem is infeasible
unbounded	pointer to store if the problem is unbounded
error	pointer to store if an error occurred

Definition at line 14224 of file cons_cumulative.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPconshdlrGetData(), SCIPcreateWorstCaseProfile(), SCIPerrorMessage, SCIPfindConshdlr(), and TRUE.

Referenced by SCIPsetSolveCumulative(), and solveIndependentCons().

SCIP_RETCODE SCIPcreateWorstCaseProfile	(	SCIP *	scip,
		SCIP_PROFILE *	profile,
		int	nvars,
		SCIP_VAR **	vars,
		int *	durations,
		int *	demands
	)

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

Definition at line 14280 of file cons_cumulative.c.

References computeImpliedEst(), computeImpliedLct(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcHashtableSize(), SCIPcomputeHmin(), SCIPconvertRealToInt(), SCIPfreeBufferArray, SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapInsert(), SCIPprofileInsertCore(), SCIPsortDownIntInt(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by computeAlternativeBounds(), computeEffectiveHorizonCumulativeCondition(), and SCIPsolveCumulative().

int SCIPcomputeHmin	(	SCIP *	scip,
		SCIP_PROFILE *	profile,
		int	capacity
	)

computes w.r.t. the given worst case resource profile the first time point where the given capacity can be violated

Parameters

scip	SCIP data structure
profile	worst case resource profile
capacity	capacity to check

Definition at line 14359 of file cons_cumulative.c.

References SCIPcomputeHmax(), SCIPprofileGetLoads(), SCIPprofileGetNTimepoints(), and SCIPprofileGetTimepoints().

Referenced by computeAlternativeBounds(), computeEffectiveHorizonCumulativeCondition(), and SCIPcreateWorstCaseProfile().

int SCIPcomputeHmax	(	SCIP *	scip,
		SCIP_PROFILE *	profile,
		int	capacity
	)

computes w.r.t. the given worst case resource profile the first time point where the given capacity is satisfied for sure

Parameters

scip	SCIP data structure
profile	worst case profile
capacity	capacity to check

Definition at line 14389 of file cons_cumulative.c.

References SCIPprofileGetLoads(), SCIPprofileGetNTimepoints(), and SCIPprofileGetTimepoints().

Referenced by computeAlternativeBounds(), computeEffectiveHorizonCumulativeCondition(), and SCIPcomputeHmin().

SCIP

Detailed Description

Macros

Functions

Inference Information Methods

Propagation

Macro Definition Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation