
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 holds.
 Separation:
 can be done using binary start time model, see Pritskers, Watters and Wolfe
 or by just separating relatively weak cuts on the start time variables
 Propagation:
 time tabling, Klein & Scholl (1999)
 Edgefinding from Petr Vilim, adjusted and simplified for dynamic repropagation (2009)
 energetic reasoning, see Baptiste, Le Pape, Nuijten (2001)
Definition in file cons_cumulative.h.
Go to the source code of this file.

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 *delvars, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff) 

SCIP_RETCODE  SCIPpropCumulativeCondition (SCIP *scip, 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) 

#define SCIP_DECL_SOLVECUMULATIVE 
( 

x  ) 

Value:
int* durations, int* demands, int capacity, int hmin, int hmax, \
solves given cumulative condition as independent sub problem
 Note
 The time and memory limit should be respected.

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.
input:
 njobs : number of jobs (activities)
 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 branchandbound nodes to solve the single cumulative constraint (1: no limit)
input/output:
 ests : array of earliest start times for each job
 lsts : array of latest start times for each job
output:
 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 86 of file cons_cumulative.h.
creates the constraint handler for cumulative constraints and includes it in SCIP
 Parameters

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. 
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 an absolute power 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 SCIPsetConsFLAGNAMEmethods 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 
set the left bound of effective horizon
 Parameters

scip  SCIP data structure 
cons  constraint data 
hmin  left bound of time axis to be considered 
returns the left bound of the effective horizon
 Parameters

scip  SCIP data structure 
cons  constraint 
set the right bound of the effective horizon
 Parameters

scip  SCIP data structure 
cons  constraint data 
hmax  right bound of time axis to be considered 
returns the right bound of effective horizon
 Parameters

scip  SCIP data structure 
cons  constraint 
returns the start time variables of the cumulative constraint
 Parameters

scip  SCIP data structure 
cons  constraint data 
returns the number of start time variables of the cumulative constraint
 Parameters

scip  SCIP data structure 
cons  constraint data 
returns the capacity of the cumulative constraint
 Parameters

scip  SCIP data structure 
cons  constraint data 
int* SCIPgetDurationsCumulative 
( 
SCIP * 
scip, 


SCIP_CONS * 
cons 

) 
 
returns the durations of the cumulative constraint
 Parameters

scip  SCIP data structure 
cons  constraint data 
returns the demands of the cumulative constraint
 Parameters

scip  SCIP data structure 
cons  constraint data 
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 
hmax  right bound of time axis to be considered 
violated  pointer to store if the cumulative condition is violated 
cons  constraint which is checked 
printreason  should the reason for the violation be printed? 
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 
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 
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 * 
delvars, 


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 
delvars  array storing the variable which can be deleted from the constraint 
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 
SCIP_RETCODE SCIPpropCumulativeCondition 
( 
SCIP * 
scip, 


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 
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 
hmax  right bound of time axis to be considered 
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 
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 
this method visualizes the cumulative structure in GML format
 Parameters

scip  SCIP data structure 
cons  cumulative constraint 
sets method to solve an individual cumulative condition
 Parameters

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