Scippy

SCIP

Solving Constraint Integer Programs

cons_cumulative.h File Reference

Detailed Description

constraint handler for cumulative constraints

Author
Timo Berthold
Stefan Heinz
Jens Schulz

Given:

  • a set of jobs, represented by their integer start time variables $S_j$, their array of processing times $p_j$ and of their demands $d_j$.
  • an integer resource capacity $C$

The cumulative constraint ensures that for each point in time $t$ $\sum_{j: S_j \leq t < S_j + p_j} d_j \leq C$ holds.

Separation:
  • can be done using binary start time model, see Pritskers, Watters and Wolfe
  • or by just separating relatively weak cuts on the 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.h.

#include "scip/scip.h"

Go to the source code of this file.

Macros

#define SCIP_DECL_SOLVECUMULATIVE(x)
 

Functions

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

Macro Definition Documentation

#define SCIP_DECL_SOLVECUMULATIVE (   x)
Value:
SCIP_RETCODE x (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)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIP_Bool
Definition: def.h:53
#define SCIP_Real
Definition: def.h:127
#define SCIP_Longint
Definition: def.h:112

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 branch-and-bound 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.

Function Documentation

SCIP_RETCODE SCIPincludeConshdlrCumulative ( SCIP scip)

creates the constraint handler for cumulative constraints and includes it in SCIP

Parameters
scipSCIP data structure
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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables (jobs)
varsarray of integer variable which corresponds to starting times for a job
durationsarray containing corresponding durations
demandsarray containing corresponding demands
capacityavailable cumulative capacity
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiableis constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are seperated as constraints.
removableshould the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnodeshould the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.
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 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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables (jobs)
varsarray of integer variable which corresponds to starting times for a job
durationsarray containing corresponding durations
demandsarray containing corresponding demands
capacityavailable cumulative capacity
SCIP_RETCODE SCIPsetHminCumulative ( SCIP scip,
SCIP_CONS cons,
int  hmin 
)

set the left bound of effective horizon

Parameters
scipSCIP data structure
consconstraint data
hminleft bound of time axis to be considered
int SCIPgetHminCumulative ( SCIP scip,
SCIP_CONS cons 
)

returns the left bound of the effective horizon

Parameters
scipSCIP data structure
consconstraint
SCIP_RETCODE SCIPsetHmaxCumulative ( SCIP scip,
SCIP_CONS cons,
int  hmax 
)

set the right bound of the effective horizon

Parameters
scipSCIP data structure
consconstraint data
hmaxright bound of time axis to be considered
int SCIPgetHmaxCumulative ( SCIP scip,
SCIP_CONS cons 
)

returns the right bound of effective horizon

Parameters
scipSCIP data structure
consconstraint
SCIP_VAR** SCIPgetVarsCumulative ( SCIP scip,
SCIP_CONS cons 
)

returns the start time variables of the cumulative constraint

Parameters
scipSCIP data structure
consconstraint data
int SCIPgetNVarsCumulative ( SCIP scip,
SCIP_CONS cons 
)

returns the number of start time variables of the cumulative constraint

Parameters
scipSCIP data structure
consconstraint data
int SCIPgetCapacityCumulative ( SCIP scip,
SCIP_CONS cons 
)

returns the capacity of the cumulative constraint

Parameters
scipSCIP data structure
consconstraint data
int* SCIPgetDurationsCumulative ( SCIP scip,
SCIP_CONS cons 
)

returns the durations of the cumulative constraint

Parameters
scipSCIP data structure
consconstraint data
int* SCIPgetDemandsCumulative ( SCIP scip,
SCIP_CONS cons 
)

returns the demands of the cumulative constraint

Parameters
scipSCIP data structure
consconstraint 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
scipSCIP data structure
solprimal solution, or NULL for current LP/pseudo solution
nvarsnumber of variables (jobs)
varsarray of integer variable which corresponds to starting times for a job
durationsarray containing corresponding durations
demandsarray containing corresponding demands
capacityavailable cumulative capacity
hminleft bound of time axis to be considered
hmaxright bound of time axis to be considered
violatedpointer to store if the cumulative condition is violated
consconstraint which is checked
printreasonshould 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
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitypointer to store the changed cumulative capacity
nchgcoefspointer to count total number of changed coefficients
nchgsidespointer to count number of side changes
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
scipSCIP data structure
nvarsnumber of variables (jobs)
varsarray of integer variable which corresponds to starting times for a job
durationsarray containing corresponding durations
demandsarray containing corresponding demands
capacityavailable cumulative capacity
hminpointer to store the left bound of the effective horizon
hmaxpointer to store the right bound of the effective horizon
splitpoint were the cumulative condition can be split
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
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
hminleft bound of time axis to be considered
hmaxright bound of time axis to be considered (not including hmax)
downlocksarray storing if the variable has a down lock, or NULL
uplocksarray storing if the variable has an up lock, or NULL
consconstraint which gets propagated, or NULL
delvarsarray storing the variable which can be deleted from the constraint
nfixedvarspointer to store the number of fixed variables
nchgsidespointer to store the number of changed sides
cutoffbuffer to store whether a cutoff is detected
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
scipSCIP data structure
presoltimingcurrent presolving timing
nvarsnumber of variables (jobs)
varsarray of integer variable which corresponds to starting times for a job
durationsarray containing corresponding durations
demandsarray containing corresponding demands
capacityavailable cumulative capacity
hminleft bound of time axis to be considered
hmaxright bound of time axis to be considered
consconstraint which gets propagated
nchgbdspointer to store the number of variable bound changes
initializedwas conflict analysis initialized
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
cutoffpointer to store if the 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
scipSCIP data structure
nvarsnumber of start time variables (activities)
varsarray of start time variables
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
infervarthe conflict variable whose bound change has to be resolved
inferinfothe user information
boundtypethe type of the changed bound (lower or upper bound)
bdchgidxthe index of the bound change, representing the point of time where the change took place
relaxedbdthe relaxed bound which is sufficient to be explained
explanationbool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL
resultpointer to store the result of the propagation conflict resolving call
SCIP_RETCODE SCIPvisualizeConsCumulative ( SCIP scip,
SCIP_CONS cons 
)

this method visualizes the cumulative structure in GML format

Parameters
scipSCIP data structure
conscumulative constraint
SCIP_RETCODE SCIPsetSolveCumulative ( SCIP scip,
SCIP_DECL_SOLVECUMULATIVE((*solveCumulative))   
)

sets method to solve an individual cumulative condition

Parameters
scipSCIP data structure
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
scipSCIP data structure
njobsnumber of jobs (activities)
estsarray with the earlier start time for each job
lstsarray with the latest start time for each job
objvalsarray of objective coefficients for each job (linear objective function), or NULL if none
durationsarray of durations
demandsarray of demands
capacitycumulative capacity
hminleft bound of time axis to be considered (including hmin)
hmaxright bound of time axis to be considered (not including hmax)
timelimittime limit for solving in seconds
memorylimitmemory limit for solving in mega bytes (MB)
maxnodesmaximum number of branch-and-bound nodes to solve the single cumulative constraint (-1: no limit)
solvedpointer to store if the problem is solved (to optimality)
infeasiblepointer to store if the problem is infeasible
unboundedpointer to store if the problem is unbounded
errorpointer to store if an error occurred
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
scipSCIP data structure
profileresource profile
nvarsnumber of variables (jobs)
varsarray of integer variable which corresponds to starting times for a job
durationsarray containing corresponding durations
demandsarray containing corresponding demands
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
scipSCIP data structure
profileworst case resource profile
capacitycapacity to check
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
scipSCIP data structure
profileworst case profile
capacitycapacity to check