Scippy

SCIP

Solving Constraint Integer Programs

cons_optcumulative.c File Reference

Detailed Description

constraint handler for cumulative constraints with optional activities

Author
Chris Beck
Stefan Heinz

Given a set of jobs \(J\). Each job~ \(j\) has a binary variables \(x_j\) which is one if this job is scheduled on that machine (otherwise it is zero), an integer start time variables \(S_j\), a processing time \(p_j\), and a demands \(d_j\). Besides that an integer resource capacity \(C\).

The optcumulative enfoces the cumulative conditions for those jobs which are assigned to that machine. Let \(J'\) be the subset of jobs assigned to that optcumulative constraint, then the cumulative constraint ensures that for each point in time \(t\) \(\sum_{j\in J': S_j \leq t < S_j + p_j} d_j \leq C\) holds.

Propagation:

LP Relaxation:

  • let est(J) the earliest start time of all jobs of set \(J\) and lct(J) the latest completion time for all jobs of set \(J\), then the following linear constraint has to hold \(\sum_{j\in J} p_j \cdot d_j \leq (lct(J) - est(J)) \cdot C\)

Definition in file cons_optcumulative.c.

#include <assert.h>
#include <string.h>
#include "cons_optcumulative.h"
#include "scip/cons_cumulative.h"
#include "scip/cons_knapsack.h"
#include "scip/scipdefplugins.h"

Go to the source code of this file.

Macros

#define consInitOptcumulative   NULL
 
#define consExitOptcumulative   NULL
 
#define consExitpreOptcumulative   NULL
 
#define consInitsolOptcumulative   NULL
 
#define consEnforelaxOptcomulative   NULL
 
#define consSepasolOptcumulative   NULL
 
#define consActiveOptcumulative   NULL
 
#define consDeactiveOptcumulative   NULL
 
#define consEnableOptcumulative   NULL
 
#define consDisableOptcumulative   NULL
 
#define consDelvarsOptcumulative   NULL
 
Constraint handler properties
#define CONSHDLR_NAME   "optcumulative"
 
#define CONSHDLR_DESC   "constraint handler for cumulative constraints with optional activities"
 
#define CONSHDLR_SEPAPRIORITY   0
 
#define CONSHDLR_ENFOPRIORITY   -2060000
 
#define CONSHDLR_CHECKPRIORITY   -3100000
 
#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_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
 
#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_MEDIUM
 
Event handler properties
#define EVENTHDLR_BINVARS_NAME   "optcumulativebinvars"
 
#define EVENTHDLR_BINVARS_DESC   "bound change event handler for binary variables of optcumulative constraints"
 
#define EVENTHDLR_INTVARS_NAME   "optcumulativeintvars"
 
#define EVENTHDLR_INTVARS_DESC   "bound change event handler for integer variables of optcumulative constraints"
 
Default parameter values
#define DEFAULT_ROWRELAX   FALSE
 
#define DEFAULT_CONFLICTANALYSIS   TRUE
 
#define DEFAULT_INTERVALRELAX   TRUE
 

Functions

static SCIP_RETCODE unlockRounding (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *binvar, SCIP_VAR *var, SCIP_Bool downlock, SCIP_Bool uplock)
 
static SCIP_RETCODE catchEventBinvar (SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
 
static SCIP_RETCODE dropEventBinvar (SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
 
static SCIP_RETCODE catchEventIntvar (SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
 
static SCIP_RETCODE dropEventIntvar (SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
 
static SCIP_RETCODE catchAllEvents (SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlrbinvars, SCIP_EVENTHDLR *eventhdlrintvars)
 
static SCIP_RETCODE dropAllEvents (SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlrbinvars, SCIP_EVENTHDLR *eventhdlrintvars)
 
static void createSortedEventpoints (SCIP *scip, SCIP_CONSDATA *consdata, int *starttimes, int *endtimes, int *startindices, int *endindices, SCIP_Bool local)
 
static SCIP_Longint computeMaxEnergy (SCIP *scip, SCIP_CONSDATA *consdata, int starttime, int endtime)
 
static SCIP_RETCODE collectVars (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR **vars, SCIP_Longint *weights, int *nvars, int starttime, int endtime)
 
static int removeRedundantRows (SCIP_Longint *rowtightness, int *startidxs, int nrows, SCIP_Longint tightness)
 
static SCIP_RETCODE createRow (SCIP *scip, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_VAR **vars, SCIP_Longint *weights, int nvars, SCIP_Longint capacity, SCIP_Bool local, SCIP_Bool *rowadded, SCIP_Bool *consadded, SCIP_Bool *cutoff)
 
static SCIP_RETCODE addRelaxation (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS *cons, SCIP_Bool *rowadded, SCIP_Bool *consadded, SCIP_Bool *cutoff)
 
static void collectActivities (SCIP_CONSDATA *consdata, SCIP_VAR **binvars, SCIP_VAR **vars, int *durations, int *demands, int *nfixedones, int *nfixedzeros, SCIP_Bool *auxiliary)
 
static void collectSolActivities (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, SCIP_VAR **binvars, SCIP_VAR **vars, int *durations, int *demands, int *nvars, int *nfixedones, int *nfixedzeros, SCIP_Bool *auxiliary)
 
static SCIP_RETCODE solveCumulative (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool local, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Longint maxnodes, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *error)
 
static SCIP_RETCODE createConflictCons (SCIP *scip, const char *name, SCIP_VAR **binvars, int nvars)
 
static SCIP_RETCODE checkRedundancy (SCIP *scip, SCIP_CONS *cons, int *ndelconss, SCIP_Bool *redundant)
 
static SCIP_RETCODE solveSubproblem (SCIP *scip, SCIP_CONS *cons, SCIP_Bool conflictanalysis, SCIP_CONSDATA *consdata, SCIP_VAR **binvars, SCIP_VAR **vars, int *durations, int *demands, int nvars, int *nfixedvars, int *nchgbds, int *ndelconss, SCIP_Bool *cutoff)
 
static SCIP_RETCODE checkCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *violated, SCIP_Bool printreason)
 
static SCIP_RETCODE enfopsCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *trysol, SCIP_Bool *violated, SCIP_Bool *consadded, SCIP_Bool *solfeasible)
 
static SCIP_RETCODE upgradeCons (SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nupgdconss, SCIP_Bool *mustpropagate)
 
static SCIP_RETCODE fixIntegerVariable (SCIP *scip, SCIP_VAR *var, SCIP_Bool downlock, SCIP_Bool uplock, int *nchgbds)
 
static SCIP_RETCODE consdataDeletePos (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_CONS *cons, int pos)
 
static SCIP_RETCODE applyZeroFixings (SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgbds)
 
static SCIP_RETCODE removeIrrelevantJobs (SCIP *scip, SCIP_CONS *cons)
 
static SCIP_RETCODE presolveCumulativeCondition (SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *nchgcoefs, int *nchgsides, SCIP_Bool *cutoff)
 
static SCIP_RETCODE createSetPackingCons (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2)
 
static SCIP_RETCODE createVarboundCons (SCIP *scip, SCIP_VAR *binvar, SCIP_VAR *intvar, int bound, SCIP_Bool lower)
 
static SCIP_RETCODE createBounddisjunctionCons (SCIP *scip, SCIP_VAR *binvar, SCIP_VAR *intvar, int lb, int ub)
 
static SCIP_RETCODE detectImplications (SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *naddconss)
 
static SCIP_RETCODE propagateCons (SCIP *scip, SCIP_CONS *cons, SCIP_Bool conflictanalysis, int *nfixedvars, int *nchgbds, int *ndelconss, SCIP_Bool *cutoff)
 
static SCIP_DECL_CONSHDLRCOPY (conshdlrCopyOptcumulative)
 
static SCIP_DECL_CONSFREE (consFreeOptcumulative)
 
static SCIP_DECL_CONSINITPRE (consInitpreOptcumulative)
 
static SCIP_DECL_CONSEXITSOL (consExitsolOptcumulative)
 
static SCIP_DECL_CONSDELETE (consDeleteOptcumulative)
 
static SCIP_DECL_CONSTRANS (consTransOptcumulative)
 
static SCIP_DECL_CONSINITLP (consInitlpOptcumulative)
 
static SCIP_DECL_CONSSEPALP (consSepalpOptcumulative)
 
static SCIP_DECL_CONSENFOLP (consEnfolpOptcumulative)
 
static SCIP_DECL_CONSENFOPS (consEnfopsOptcumulative)
 
static SCIP_DECL_CONSCHECK (consCheckOptcumulative)
 
static SCIP_DECL_CONSPROP (consPropOptcumulative)
 
static SCIP_DECL_CONSPRESOL (consPresolOptcumulative)
 
static SCIP_DECL_CONSRESPROP (consRespropOptcumulative)
 
static SCIP_DECL_CONSLOCK (consLockOptcumulative)
 
static SCIP_DECL_CONSPRINT (consPrintOptcumulative)
 
static SCIP_DECL_CONSCOPY (consCopyOptcumulative)
 
static SCIP_DECL_CONSPARSE (consParseOptcumulative)
 
static SCIP_DECL_EVENTEXEC (eventExecOptcumulativeBinvars)
 
static SCIP_DECL_EVENTEXEC (eventExecOptcumulativeIntvars)
 
SCIP_RETCODE SCIPincludeConshdlrOptcumulative (SCIP *scip)
 
SCIP_RETCODE SCIPcreateConsOptcumulative (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_VAR **binvars, 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)
 
Debug Methods
static void checkCounters (SCIP_CONSDATA *consdata)
 
Miscellaneous Methods
static int convertBoundToInt (SCIP *scip, SCIP_Real bound)
 
Constraint data methods
static SCIP_RETCODE consdataCreate (SCIP *scip, SCIP_CONSDATA **consdata, int nvars, SCIP_VAR **vars, SCIP_VAR **binvars, int *durations, int *demands, int capacity, SCIP_Bool check)
 
static SCIP_RETCODE consdataFree (SCIP *scip, SCIP_CONSDATA **consdata)
 
static SCIP_RETCODE consdataPrint (SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
 
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 *eventhdlrbinvars, SCIP_EVENTHDLR *eventhdlrintvars)
 
static SCIP_RETCODE conshdlrdataFree (SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "constraint handler for cumulative constraints with optional activities"

Definition at line 70 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   0

priority of the constraint handler for separation

Definition at line 71 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   -2060000

priority of the constraint handler for constraint enforcing

Definition at line 72 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -3100000

priority of the constraint handler for checking feasibility

Definition at line 73 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ   1

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

Definition at line 74 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 75 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ   100

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

Definition at line 76 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS   -1

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

Definition at line 79 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA   FALSE

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

Definition at line 80 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   FALSE

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

Definition at line 81 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   TRUE

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

Definition at line 82 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 84 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_MEDIUM

Definition at line 85 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ EVENTHDLR_BINVARS_NAME

#define EVENTHDLR_BINVARS_NAME   "optcumulativebinvars"

Definition at line 94 of file cons_optcumulative.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludeConshdlrOptcumulative().

◆ EVENTHDLR_BINVARS_DESC

#define EVENTHDLR_BINVARS_DESC   "bound change event handler for binary variables of optcumulative constraints"

Definition at line 95 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ EVENTHDLR_INTVARS_NAME

#define EVENTHDLR_INTVARS_NAME   "optcumulativeintvars"

Definition at line 97 of file cons_optcumulative.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludeConshdlrOptcumulative().

◆ EVENTHDLR_INTVARS_DESC

#define EVENTHDLR_INTVARS_DESC   "bound change event handler for integer variables of optcumulative constraints"

Definition at line 98 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ DEFAULT_ROWRELAX

#define DEFAULT_ROWRELAX   FALSE

add linear relaxation as LP row (otherwise a knapsack constraint is created)?

Definition at line 107 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ DEFAULT_CONFLICTANALYSIS

#define DEFAULT_CONFLICTANALYSIS   TRUE

participate in conflict analysis?"

Definition at line 108 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ DEFAULT_INTERVALRELAX

#define DEFAULT_INTERVALRELAX   TRUE

create a relaxation for each start and end time point interval

Definition at line 109 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ consInitOptcumulative

#define consInitOptcumulative   NULL

initialization method of constraint handler (called after problem was transformed)

Definition at line 3011 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ consExitOptcumulative

#define consExitOptcumulative   NULL

deinitialization method of constraint handler (called before transformed problem is freed)

Definition at line 3015 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ consExitpreOptcumulative

#define consExitpreOptcumulative   NULL

presolving deinitialization method of constraint handler (called after presolving has been finished)

Definition at line 3050 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ consInitsolOptcumulative

#define consInitsolOptcumulative   NULL

solving process initialization method of constraint handler (called when branch and bound process is about to begin)

Definition at line 3054 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ consEnforelaxOptcomulative

#define consEnforelaxOptcomulative   NULL

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 3057 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ consSepasolOptcumulative

#define consSepasolOptcumulative   NULL

separation method of constraint handler for arbitrary primal solutions

Definition at line 3225 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ consActiveOptcumulative

#define consActiveOptcumulative   NULL

constraint activation notification method of constraint handler

Definition at line 3808 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ consDeactiveOptcumulative

#define consDeactiveOptcumulative   NULL

constraint deactivation notification method of constraint handler

Definition at line 3812 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ consEnableOptcumulative

#define consEnableOptcumulative   NULL

constraint enabling notification method of constraint handler

Definition at line 3816 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ consDisableOptcumulative

#define consDisableOptcumulative   NULL

constraint disabling notification method of constraint handler

Definition at line 3820 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

◆ consDelvarsOptcumulative

#define consDelvarsOptcumulative   NULL

variable deletion method of constraint handler

Definition at line 3823 of file cons_optcumulative.c.

Referenced by SCIPincludeConshdlrOptcumulative().

Function Documentation

◆ checkCounters()

static void checkCounters ( SCIP_CONSDATA consdata)
static

check constraint state (nglbfixedones and nglbfixedzeros)

Parameters
consdataoptcumulative constraint data

Definition at line 167 of file cons_optcumulative.c.

References convertBoundToInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

Referenced by applyZeroFixings(), catchAllEvents(), consdataDeletePos(), propagateCons(), and upgradeCons().

◆ convertBoundToInt()

static int convertBoundToInt ( SCIP scip,
SCIP_Real  bound 
)
static

converts the given double bound which is integral to an int; in optimized mode the function gets inlined for performance; in debug mode we check some additional conditions

Parameters
scipSCIP data structure
bounddouble bound to convert

Definition at line 218 of file cons_optcumulative.c.

References bound, consdataCreate(), SCIP_Real, SCIPisEQ(), and SCIPisIntegral().

Referenced by addRelaxation(), checkCounters(), checkRedundancy(), collectVars(), computeMaxEnergy(), createSortedEventpoints(), detectImplications(), enfopsCons(), presolveCumulativeCondition(), propagateCons(), removeIrrelevantJobs(), and solveSubproblem().

◆ consdataCreate()

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

creates constraint data of optcumulative constraint

Parameters
scipSCIP data structure
consdatapointer to consdata
nvarsnumber of variables
varsarray of integer variables
binvarsarray of variable representing if the job has to be processed on this machine
durationsarray containing corresponding durations
demandsarray containing corresponding demands
capacityavailable cumulative capacity
checkis the corresponding constraint a check constraint

Definition at line 241 of file cons_optcumulative.c.

References consdataFree(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPdebugMessage, SCIPduplicateBlockMemoryArray, SCIPgetTransformedVars(), SCIPisTransformed(), and SCIPmarkDoNotMultaggrVar().

Referenced by convertBoundToInt(), SCIP_DECL_CONSTRANS(), and SCIPcreateConsOptcumulative().

◆ consdataFree()

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

frees a optcumulative constraint data

Parameters
scipSCIP data structure
consdatapointer to linear constraint data

Definition at line 338 of file cons_optcumulative.c.

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

Referenced by consdataCreate(), and SCIP_DECL_CONSDELETE().

◆ consdataPrint()

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

prints optcumulative constraint to file stream

Parameters
scipSCIP data structure
consdataoptcumulative constraint data
fileoutput file (or NULL for standard output)

Definition at line 381 of file cons_optcumulative.c.

References conshdlrdataCreate(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPinfoMessage(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and SCIPwriteVarName().

Referenced by consdataFree(), and SCIP_DECL_CONSPRINT().

◆ conshdlrdataCreate()

static SCIP_RETCODE conshdlrdataCreate ( SCIP scip,
SCIP_CONSHDLRDATA **  conshdlrdata,
SCIP_EVENTHDLR eventhdlrbinvars,
SCIP_EVENTHDLR eventhdlrintvars 
)
static

creates constaint handler data for set partitioning / packing / covering constraint handler

Parameters
scipSCIP data structure
conshdlrdatapointer to store the constraint handler data
eventhdlrbinvarsused event handler for tracing bound changes on binary variables
eventhdlrintvarsused event handler for tracing bound changes on integer variables

Definition at line 424 of file cons_optcumulative.c.

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

Referenced by consdataPrint(), and SCIPincludeConshdlrOptcumulative().

◆ conshdlrdataFree()

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

frees constraint handler data for set partitioning / packing / covering constraint handler

Parameters
scipSCIP data structure
conshdlrdatapointer to the constraint handler data

Definition at line 447 of file cons_optcumulative.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, and unlockRounding().

Referenced by conshdlrdataCreate(), and SCIP_DECL_CONSFREE().

◆ unlockRounding()

static SCIP_RETCODE unlockRounding ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR binvar,
SCIP_VAR var,
SCIP_Bool  downlock,
SCIP_Bool  uplock 
)
static

removes rounding locks for the given variable in the given optcumulative constraint

Parameters
scipSCIP data structure
consoptcumulative constraint
binvardecision variable
varstart time variable
downlockhas the integer start time variable a down lock
uplockhas the integer start time variable an up lock

Definition at line 464 of file cons_optcumulative.c.

References catchEventBinvar(), FALSE, SCIP_CALL, SCIP_OKAY, SCIPunlockVarCons(), and TRUE.

Referenced by consdataDeletePos(), and conshdlrdataFree().

◆ catchEventBinvar()

static SCIP_RETCODE catchEventBinvar ( SCIP scip,
SCIP_CONS cons,
SCIP_EVENTHDLR eventhdlr,
int  pos 
)
static

catches events for binary variable at given position

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint
eventhdlrevent handler to call for the event processing
posarray position of variable to catch bound change events for

Definition at line 484 of file cons_optcumulative.c.

References dropEventBinvar(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDRELAXED, SCIP_EVENTTYPE_BOUNDTIGHTENED, SCIP_EVENTTYPE_GBDCHANGED, SCIP_OKAY, SCIPcatchVarEvent(), SCIPconsGetData(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

Referenced by catchAllEvents(), and unlockRounding().

◆ dropEventBinvar()

static SCIP_RETCODE dropEventBinvar ( SCIP scip,
SCIP_CONS cons,
SCIP_EVENTHDLR eventhdlr,
int  pos 
)
static

drops events for binary variable at given position

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint
eventhdlrevent handler to call for the event processing
posarray position of variable to catch bound change events for

Definition at line 537 of file cons_optcumulative.c.

References catchEventIntvar(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDRELAXED, SCIP_EVENTTYPE_BOUNDTIGHTENED, SCIP_EVENTTYPE_GBDCHANGED, SCIP_OKAY, SCIPconsGetData(), SCIPdropVarEvent(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

Referenced by catchEventBinvar(), consdataDeletePos(), and dropAllEvents().

◆ catchEventIntvar()

static SCIP_RETCODE catchEventIntvar ( SCIP scip,
SCIP_CONS cons,
SCIP_EVENTHDLR eventhdlr,
int  pos 
)
static

catches events for integer variable at given position

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint
eventhdlrevent handler to call for the event processing
posarray position of variable to catch bound change events for

Definition at line 584 of file cons_optcumulative.c.

References dropEventIntvar(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDTIGHTENED, SCIP_EVENTTYPE_GBDCHANGED, SCIP_OKAY, SCIPcatchVarEvent(), and SCIPconsGetData().

Referenced by catchAllEvents(), and dropEventBinvar().

◆ dropEventIntvar()

static SCIP_RETCODE dropEventIntvar ( SCIP scip,
SCIP_CONS cons,
SCIP_EVENTHDLR eventhdlr,
int  pos 
)
static

drops events for integer variable at given position

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint
eventhdlrevent handler to call for the event processing
posarray position of variable to catch bound change events for

Definition at line 619 of file cons_optcumulative.c.

References catchAllEvents(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDTIGHTENED, SCIP_EVENTTYPE_GBDCHANGED, SCIP_OKAY, SCIPconsGetData(), and SCIPdropVarEvent().

Referenced by catchEventIntvar(), consdataDeletePos(), and dropAllEvents().

◆ catchAllEvents()

static SCIP_RETCODE catchAllEvents ( SCIP scip,
SCIP_CONS cons,
SCIP_EVENTHDLR eventhdlrbinvars,
SCIP_EVENTHDLR eventhdlrintvars 
)
static

catches bound change events for all variables in transformed optcumulative constraint

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint
eventhdlrbinvarsevent handler to call for the event processing on binary variables
eventhdlrintvarsevent handler to call for the event processing on integer variables

Definition at line 649 of file cons_optcumulative.c.

References catchEventBinvar(), catchEventIntvar(), checkCounters(), dropAllEvents(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPconsGetData().

Referenced by dropEventIntvar(), SCIP_DECL_CONSTRANS(), and SCIPcreateConsOptcumulative().

◆ dropAllEvents()

static SCIP_RETCODE dropAllEvents ( SCIP scip,
SCIP_CONS cons,
SCIP_EVENTHDLR eventhdlrbinvars,
SCIP_EVENTHDLR eventhdlrintvars 
)
static

drops bound change events for all variables in transformed optcumulative constraint

Parameters
scipSCIP data structure
consset partitioning / packing / covering constraint
eventhdlrbinvarsevent handler to call for the event processing on binary variables
eventhdlrintvarsevent handler to call for the event processing on integer variables

Definition at line 682 of file cons_optcumulative.c.

References createSortedEventpoints(), dropEventBinvar(), dropEventIntvar(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPconsGetData().

Referenced by catchAllEvents(), and SCIP_DECL_CONSDELETE().

◆ createSortedEventpoints()

static void createSortedEventpoints ( SCIP scip,
SCIP_CONSDATA consdata,
int *  starttimes,
int *  endtimes,
int *  startindices,
int *  endindices,
SCIP_Bool  local 
)
static

initialize the sorted event point arrays

Parameters
scipSCIP data structure
consdataconstraint data
starttimesarray to store sorted start events
endtimesarray to store sorted end events
startindicespermutation with rspect to the start times
endindicespermutation with rspect to the end times
localshall local bounds be used

Definition at line 714 of file cons_optcumulative.c.

References computeMaxEnergy(), convertBoundToInt(), SCIP_Longint, SCIPsortIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

Referenced by addRelaxation(), and dropAllEvents().

◆ computeMaxEnergy()

static SCIP_Longint computeMaxEnergy ( SCIP scip,
SCIP_CONSDATA consdata,
int  starttime,
int  endtime 
)
static

computes the maximum energy for all variables which correspond to jobs which start between the given start time and end time

Returns
Maximum energy for the given time window
Parameters
scipSCIP data structure
consdataoptcumulative constraint data
starttimestart time
endtimeend time

Definition at line 760 of file cons_optcumulative.c.

References collectVars(), convertBoundToInt(), SCIP_Longint, SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by addRelaxation(), and createSortedEventpoints().

◆ collectVars()

static SCIP_RETCODE collectVars ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_VAR **  vars,
SCIP_Longint weights,
int *  nvars,
int  starttime,
int  endtime 
)
static

collects all variables which correspond to jobs which start between the given start time and end time

Parameters
scipSCIP data structure
consdataoptcumulative constraint data
varsarray to store the variables
weightsarray to store the weights
nvarspointer to store the number of collected variables
starttimestart time
endtimeend time

Definition at line 791 of file cons_optcumulative.c.

References convertBoundToInt(), removeRedundantRows(), SCIP_Longint, SCIP_OKAY, SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by addRelaxation(), and computeMaxEnergy().

◆ removeRedundantRows()

static int removeRedundantRows ( SCIP_Longint rowtightness,
int *  startidxs,
int  nrows,
SCIP_Longint  tightness 
)
static

remove row which have a tightness which is smaller or equal to the given one

Returns
The number of remaining rows
Parameters
rowtightnessarray containing the tightness for the previously selected rows
startidxsarray containing for each row the index for the start event
nrowscurrent number of rows
tightnesstightness to use to detect redundant rows

Definition at line 829 of file cons_optcumulative.c.

References createRow().

Referenced by addRelaxation(), and collectVars().

◆ createRow()

static SCIP_RETCODE createRow ( SCIP scip,
SCIP_CONSHDLR conshdlr,
const char *  name,
SCIP_VAR **  vars,
SCIP_Longint weights,
int  nvars,
SCIP_Longint  capacity,
SCIP_Bool  local,
SCIP_Bool rowadded,
SCIP_Bool consadded,
SCIP_Bool cutoff 
)
static

depending on the parameters setting a row or an knapsack constraint is created

Parameters
scipSCIP data structure
conshdlrconstraint handler
namename of the row
varsarray of variable representing if the job has to be processed on this machine
weightsstart time variables of the activities which are assigned
nvarsnumber of variables
capacityavailable cumulative capacity
localcreate local row
rowaddedpointer to store if a row was added
consaddedpointer to store if a constraint was added
cutoffpointer to store whether a cutoff occurred

Definition at line 856 of file cons_optcumulative.c.

References addRelaxation(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPconshdlrGetData(), SCIPcreateConsKnapsack(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPflushRowExtensions(), SCIPgetDepth(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPprintCons(), SCIPprintRow(), SCIPreleaseCons(), SCIPreleaseRow(), SCIProwIsInLP(), and TRUE.

Referenced by addRelaxation(), enfopsCons(), and removeRedundantRows().

◆ addRelaxation()

static SCIP_RETCODE addRelaxation ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_CONS cons,
SCIP_Bool rowadded,
SCIP_Bool consadded,
SCIP_Bool cutoff 
)
static

adds linear relaxation as cut to the LP

Parameters
scipSCIP data structure
conshdlrconstraint handler
conshdlrdataconstraint handler data structure
consoptcumulative constraint
rowaddedpointer to store if a row was added
consaddedpointer to store if a constraint was added
cutoffpointer to store whether a cutoff occurred

Definition at line 927 of file cons_optcumulative.c.

References BMSclearMemoryArray, collectActivities(), collectVars(), computeMaxEnergy(), convertBoundToInt(), createRow(), createSortedEventpoints(), FALSE, MAX, MIN, NULL, removeRedundantRows(), SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPrestartSolve(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by createRow(), SCIP_DECL_CONSINITLP(), and SCIP_DECL_CONSSEPALP().

◆ collectActivities()

static void collectActivities ( SCIP_CONSDATA consdata,
SCIP_VAR **  binvars,
SCIP_VAR **  vars,
int *  durations,
int *  demands,
int *  nfixedones,
int *  nfixedzeros,
SCIP_Bool auxiliary 
)
static

collect all activities which are locally (that means in the current branch and bound node) assigned to that machine

Parameters
consdataconstraint data
binvarsarray of variable representing if the job has to be processed on this machine
varsstart time variables of the activities which are assigned
durationsdurations of the activities
demandsdemands of the activities
nfixedonespointer to store number of activities assigned to that machine
nfixedzerospointer to store number of binary variables fixed to zeor
auxiliarypointer to store if the integer start time variables of the assigned activities are auxiliary variables; that is the case if the optcumulative choice constraints is the only one having locks on these variables

Definition at line 1154 of file cons_optcumulative.c.

References collectSolActivities(), FALSE, SCIPdebugMessage, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by addRelaxation(), propagateCons(), and upgradeCons().

◆ collectSolActivities()

static void collectSolActivities ( SCIP scip,
SCIP_CONSDATA consdata,
SCIP_SOL sol,
SCIP_VAR **  binvars,
SCIP_VAR **  vars,
int *  durations,
int *  demands,
int *  nvars,
int *  nfixedones,
int *  nfixedzeros,
SCIP_Bool auxiliary 
)
static

collect all activities which are assigned to that machine in the given solution

Parameters
scipSCIP data structure
consdataconstraint data
solprimal solution, or NULL for current LP/pseudo solution
binvarsarray of variable representing if the job has to be processed on this machine
varsstart time variables of the activities which are assigned
durationsdurations of the activities
demandsdemands of the activities
nvarspointer to store number of activities assigned to that machine
nfixedonespointer to store number of binary variables locally fixed to one
nfixedzerospointer to store number of binary variables locally fixed to zero
auxiliarypointer to store if the integer start time variables of the assigned activities are auxiliary variables; that is the case if the machine choice constraints is the only one haveing locks on these variables

Definition at line 1209 of file cons_optcumulative.c.

References FALSE, SCIPdebugMessage, SCIPgetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetUbLocal(), solveCumulative(), and TRUE.

Referenced by checkCons(), collectActivities(), and enfopsCons().

◆ solveCumulative()

static SCIP_RETCODE solveCumulative ( SCIP scip,
int  nvars,
SCIP_VAR **  vars,
int *  durations,
int *  demands,
int  capacity,
int  hmin,
int  hmax,
SCIP_Bool  local,
SCIP_Real ests,
SCIP_Real lsts,
SCIP_Longint  maxnodes,
SCIP_Bool solved,
SCIP_Bool infeasible,
SCIP_Bool unbounded,
SCIP_Bool error 
)
static

solves given cumulative condition as independent sub problem

Note
The time and memory limit of the SCIP environment in transferred to sub solver
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
nvarsnumber of start time variables (activities)
varsstart 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)
localuse local bounds, otherwise global
estsarray to store the earlier start time for each job
lstsarray to store the latest start time for each job
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

Definition at line 1267 of file cons_optcumulative.c.

References createConflictCons(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPisInfinity(), SCIPsolveCumulative(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetUbGlobal(), and SCIPvarGetUbLocal().

Referenced by checkRedundancy(), collectSolActivities(), enfopsCons(), SCIPsetSolveCumulative(), and solveSubproblem().

◆ createConflictCons()

static SCIP_RETCODE createConflictCons ( SCIP scip,
const char *  name,
SCIP_VAR **  binvars,
int  nvars 
)
static

create a logicor constraint which ensures that the jobs related to binary variables are not assigned in the same time to this optional cumulative constraint

Parameters
scipSCIP data structure
namename of conflict constraint
binvarsarray of binary variables
nvarsnumber of variables

Definition at line 1341 of file cons_optcumulative.c.

References checkRedundancy(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddCoefLogicor(), SCIPaddCons(), SCIPcreateConsLogicor(), SCIPgetNegatedVar(), SCIPreleaseCons(), SCIPvarGetLbGlobal(), and TRUE.

Referenced by checkRedundancy(), enfopsCons(), and solveCumulative().

◆ checkRedundancy()

static SCIP_RETCODE checkRedundancy ( SCIP scip,
SCIP_CONS cons,
int *  ndelconss,
SCIP_Bool redundant 
)
static

check of the given constraint is redundant

Parameters
scipSCIP data structure
consoptcumulative constraint which collapsed to a cumulative constraint locally
ndelconsspointer to store the number of deleted constraints
redundantpointer to store if the constraint is redundant

Definition at line 1375 of file cons_optcumulative.c.

References convertBoundToInt(), createConflictCons(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPconsGetData(), SCIPconsGetName(), SCIPdelConsLocal(), SCIPfreeBufferArray, SCIPinProbing(), SCIPsortRealPtrPtrIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetUbGlobal(), solveCumulative(), solveSubproblem(), and TRUE.

Referenced by createConflictCons(), and SCIP_DECL_CONSPROP().

◆ solveSubproblem()

static SCIP_RETCODE solveSubproblem ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool  conflictanalysis,
SCIP_CONSDATA consdata,
SCIP_VAR **  binvars,
SCIP_VAR **  vars,
int *  durations,
int *  demands,
int  nvars,
int *  nfixedvars,
int *  nchgbds,
int *  ndelconss,
SCIP_Bool cutoff 
)
static

solve the cumulative sub problem

Parameters
scipSCIP data structure
consoptcumulative constraint which collapsed to a cumulative constraint locally
conflictanalysisshould conflict analysis be called for infeasible subproblems
consdataconstraint data
binvarsarray of variable representing if the job has to be processed on this machine
varsstart time variables of the activities which are assigned
durationsdurations of the activities
demandsdemands of the activities
nvarsnumber of activities assigned to that machine
nfixedvarspointer to store the numbver of fixed variables
nchgbdspointer to store the number of changed bounds
ndelconsspointer to store the number of deleted constraints
cutoffpointer to store if the constraint is violated

Definition at line 1522 of file cons_optcumulative.c.

References checkCons(), convertBoundToInt(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPaddConflictBinvar(), SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPallocBufferArray, SCIPanalyzeConflictCons(), SCIPdelConsLocal(), SCIPfixVar(), SCIPfreeBufferArray, SCIPinitConflictAnalysis(), SCIPinProbing(), SCIPsortRealPtrPtrIntInt(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), solveCumulative(), and TRUE.

Referenced by checkRedundancy(), and propagateCons().

◆ checkCons()

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

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

Parameters
scipSCIP data structure
consconstraint to be checked
solprimal solution, or NULL for current LP/pseudo solution
violatedpointer to store if the constraint is violated
printreasonshould the reason for the violation be printed?

Definition at line 1683 of file cons_optcumulative.c.

References collectSolActivities(), enfopsCons(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcheckCumulativeCondition(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMessage, and SCIPfreeBufferArray.

Referenced by SCIP_DECL_CONSCHECK(), and solveSubproblem().

◆ enfopsCons()

static SCIP_RETCODE enfopsCons ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL trysol,
SCIP_Bool violated,
SCIP_Bool consadded,
SCIP_Bool solfeasible 
)
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
scipSCIP data structure
consconstraint to be checked
trysolprimal solution to construct, or NULL
violatedpointer to store if the constraint is violated/infeasible
consaddedpointer to store if a constraint was added
solfeasiblepointer to store if the constraint solution is potentially feasible

Definition at line 1738 of file cons_optcumulative.c.

References collectSolActivities(), convertBoundToInt(), createConflictCons(), createRow(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcheckCumulativeCondition(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPincConsAge(), SCIPisStopped(), SCIPresetConsAge(), SCIPsetSolVal(), SCIPsortRealPtrPtrIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), solveCumulative(), TRUE, and upgradeCons().

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

◆ upgradeCons()

static SCIP_RETCODE upgradeCons ( SCIP scip,
SCIP_CONS cons,
int *  ndelconss,
int *  nupgdconss,
SCIP_Bool mustpropagate 
)
static

◆ fixIntegerVariable()

static SCIP_RETCODE fixIntegerVariable ( SCIP scip,
SCIP_VAR var,
SCIP_Bool  downlock,
SCIP_Bool  uplock,
int *  nchgbds 
)
static

since the binary variable is fixed to zero, depending in the objective coefficient of the integer variable and the rounding locks, we might can fix the integer variable

Parameters
scipSCIP data structure
varinteger variable to fix
downlockdoes the variable has down lock given by the optcumulative constraint
uplockdoes the variable has up lock given by the optcumulative constraint
nchgbdspointer to store the number changed variable bounds

Definition at line 2066 of file cons_optcumulative.c.

References consdataDeletePos(), SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPfixVar(), SCIPinProbing(), SCIPinRepropagation(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetObj(), and SCIPvarGetUbLocal().

Referenced by applyZeroFixings(), propagateCons(), and upgradeCons().

◆ consdataDeletePos()

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

deletes coefficient at given position from constraint data

Parameters
scipSCIP data structure
consdatacumulative constraint data
consknapsack constraint
posposition of coefficient to delete

Definition at line 2139 of file cons_optcumulative.c.

References applyZeroFixings(), checkCounters(), dropEventBinvar(), dropEventIntvar(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsTransformed(), SCIPdebugMessage, SCIPvarGetName(), and unlockRounding().

Referenced by applyZeroFixings(), detectImplications(), fixIntegerVariable(), presolveCumulativeCondition(), and removeIrrelevantJobs().

◆ applyZeroFixings()

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

remove all jobs for which the binary variable is globally fixed to zero

Parameters
scipSCIP data structure
consconstraint to be checked
nchgcoefspointer to store the number changed coefficients
nchgbdspointer to store the number changed variable bounds

Definition at line 2199 of file cons_optcumulative.c.

References checkCounters(), consdataDeletePos(), fixIntegerVariable(), NULL, removeIrrelevantJobs(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsChecked(), SCIPdebugMessage, SCIPvarGetName(), SCIPvarGetUbGlobal(), and TRUE.

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

◆ removeIrrelevantJobs()

static SCIP_RETCODE removeIrrelevantJobs ( SCIP scip,
SCIP_CONS cons 
)
static

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

Parameters
scipSCIP data structure
consconstraint to propagate

Definition at line 2247 of file cons_optcumulative.c.

References consdataDeletePos(), convertBoundToInt(), NULL, presolveCumulativeCondition(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMessage, SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().

Referenced by applyZeroFixings(), and SCIP_DECL_CONSINITPRE().

◆ presolveCumulativeCondition()

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

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

Parameters
scipSCIP data structure
consconstraint to be checked
nfixedvarspointer to store the number of fixed variables
nchgcoefspointer to store the number of changed coefficients
nchgsidespointer to store the number of changed sides
cutoffbuffer to store whether a cutoff is detected

Definition at line 2308 of file cons_optcumulative.c.

References BMSclearMemoryArray, consdataDeletePos(), convertBoundToInt(), createSetPackingCons(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMessage, SCIPfixVar(), SCIPfreeBufferArray, SCIPpresolveCumulativeCondition(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by removeIrrelevantJobs(), and SCIP_DECL_CONSPRESOL().

◆ createSetPackingCons()

static SCIP_RETCODE createSetPackingCons ( SCIP scip,
SCIP_VAR var1,
SCIP_VAR var2 
)
static

create an an set partitioning constraint

Parameters
scipSCIP data structure
var1first variable
var2second variable

Definition at line 2393 of file cons_optcumulative.c.

References createVarboundCons(), NULL, SCIP_CALL, SCIP_OKAY, SCIPaddCoefSetppc(), SCIPaddCons(), SCIPcreateConsBasicSetpack(), SCIPdebugPrintCons, and SCIPreleaseCons().

Referenced by detectImplications(), and presolveCumulativeCondition().

◆ createVarboundCons()

static SCIP_RETCODE createVarboundCons ( SCIP scip,
SCIP_VAR binvar,
SCIP_VAR intvar,
int  bound,
SCIP_Bool  lower 
)
static

create variable bound constraint

Parameters
scipSCIP data structure
binvarbinary variable x
intvarinteger variable y
boundvariable bound
lowervariable lower bound? (Otherwise upper bound)

Definition at line 2414 of file cons_optcumulative.c.

References bound, createBounddisjunctionCons(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPcreateConsBasicVarbound(), SCIPdebugPrintCons, SCIPinfinity(), SCIPreleaseCons(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by createSetPackingCons(), and detectImplications().

◆ createBounddisjunctionCons()

static SCIP_RETCODE createBounddisjunctionCons ( SCIP scip,
SCIP_VAR binvar,
SCIP_VAR intvar,
int  lb,
int  ub 
)
static

create bound disjunction constraint

Parameters
scipSCIP data structure
binvarbinary variable x
intvarinteger variable y
lblower bound
ublower bound

Definition at line 2452 of file cons_optcumulative.c.

References detectImplications(), NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsBasicBounddisjunction(), SCIPdebugPrintCons, SCIPfreeBufferArray, and SCIPreleaseCons().

Referenced by createVarboundCons(), and detectImplications().

◆ detectImplications()

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

detect implication

Parameters
scipSCIP data structure
consoptcumulative constraint
nchgcoefspointer to store the number of changed coefficients
naddconsspointer to store the number of added constraints

Definition at line 2498 of file cons_optcumulative.c.

References consdataDeletePos(), convertBoundToInt(), createBounddisjunctionCons(), createSetPackingCons(), createVarboundCons(), FALSE, NULL, propagateCons(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMessage, SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by createBounddisjunctionCons(), and SCIP_DECL_CONSPRESOL().

◆ propagateCons()

static SCIP_RETCODE propagateCons ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool  conflictanalysis,
int *  nfixedvars,
int *  nchgbds,
int *  ndelconss,
SCIP_Bool cutoff 
)
static

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyOptcumulative  )
static

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

Definition at line 2979 of file cons_optcumulative.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrOptcumulative(), and TRUE.

Referenced by propagateCons().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeOptcumulative  )
static

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

Definition at line 2995 of file cons_optcumulative.c.

References conshdlrdataFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), and SCIPconshdlrSetData().

Referenced by SCIP_DECL_CONSHDLRCOPY().

◆ SCIP_DECL_CONSINITPRE()

static SCIP_DECL_CONSINITPRE ( consInitpreOptcumulative  )
static

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

Definition at line 3020 of file cons_optcumulative.c.

References CONSHDLR_NAME, NULL, removeIrrelevantJobs(), SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPfindHeur().

◆ SCIP_DECL_CONSEXITSOL()

static SCIP_DECL_CONSEXITSOL ( consExitsolOptcumulative  )
static

solving process deinitialization method of constraint handler (called before branch and bound process data is freed)

Definition at line 3061 of file cons_optcumulative.c.

References NULL, SCIP_CALL, SCIP_DECL_CONSDELETE(), SCIP_OKAY, SCIPconsGetData(), and SCIPreleaseRow().

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteOptcumulative  )
static

◆ SCIP_DECL_CONSTRANS()

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpOptcumulative  )
static

LP initialization method of constraint handler

Definition at line 3164 of file cons_optcumulative.c.

References addRelaxation(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSSEPALP(), SCIP_OKAY, SCIPconshdlrGetData(), and SCIPconsIsInitial().

Referenced by SCIP_DECL_CONSTRANS().

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpOptcumulative  )
static

separation method of constraint handler for LP solutions

Definition at line 3191 of file cons_optcumulative.c.

References addRelaxation(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SEPARATED, and SCIPconshdlrGetData().

Referenced by SCIP_DECL_CONSINITLP().

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpOptcumulative  )
static

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsOptcumulative  )
static

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckOptcumulative  )
static

feasibility check method of constraint handler for integral solutions

Definition at line 3357 of file cons_optcumulative.c.

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

Referenced by SCIP_DECL_CONSENFOPS().

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropOptcumulative  )
static

◆ SCIP_DECL_CONSPRESOL()

◆ SCIP_DECL_CONSRESPROP()

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockOptcumulative  )
static

variable rounding lock method of constraint handler

Definition at line 3766 of file cons_optcumulative.c.

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

Referenced by SCIP_DECL_CONSRESPROP().

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintOptcumulative  )
static

constraint display method of constraint handler

Definition at line 3827 of file cons_optcumulative.c.

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

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopyOptcumulative  )
static

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseOptcumulative  )
static

◆ SCIP_DECL_EVENTEXEC() [1/2]

◆ SCIP_DECL_EVENTEXEC() [2/2]

static SCIP_DECL_EVENTEXEC ( eventExecOptcumulativeIntvars  )
static

◆ SCIPincludeConshdlrOptcumulative()

◆ SCIPcreateConsOptcumulative()

SCIP_RETCODE SCIPcreateConsOptcumulative ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
int  nvars,
SCIP_VAR **  vars,
SCIP_VAR **  binvars,
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 optcumulative 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
binvarsarray of variable representing if the job has to be processed on this machine
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.

Definition at line 4145 of file cons_optcumulative.c.

References catchAllEvents(), consdataCreate(), CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_STAGE_PROBLEM, SCIPconshdlrGetData(), SCIPcreateCons(), SCIPerrorMessage, SCIPfindConshdlr(), and SCIPgetStage().

Referenced by createCipFormulation(), createMipCpFormulation(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSPRESOL(), and SCIPincludeConshdlrOptcumulative().