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

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

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

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

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

set the left bound of effective horizon

Parameters

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

int SCIPgetHminCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns the left bound of the effective horizon

Parameters

scip	SCIP data structure
cons	constraint

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

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

int SCIPgetHmaxCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns the right bound of effective horizon

Parameters

scip	SCIP data structure
cons	constraint

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

returns the start time variables of the cumulative constraint

Parameters

scip	SCIP data structure
cons	constraint data

int SCIPgetNVarsCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

returns the number of start time variables of the cumulative constraint

Parameters

scip	SCIP data structure
cons	constraint data

int SCIPgetCapacityCumulative	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

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

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

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

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

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

sets method to solve an individual cumulative condition

Parameters

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

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

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

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

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

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

Function Documentation