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

Definition in file cons_cumulative.h.

#include "scip/def.h"
#include "scip/type_cons.h"
#include "scip/type_lp.h"
#include "scip/type_misc.h"
#include "scip/type_result.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"
#include "scip/type_sol.h"
#include "scip/type_timing.h"
#include "scip/type_var.h"

Go to the source code of this file.

Functions

SCIP_EXPORT SCIP_RETCODE SCIPincludeConshdlrCumulative (SCIP *scip)
 

Cumulative Constraints

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)
#define SCIP_DECL_SOLVECUMULATIVE(x)
 
SCIP_EXPORT 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_EXPORT SCIP_RETCODE SCIPcreateConsBasicCumulative (SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity)
 
SCIP_EXPORT SCIP_RETCODE SCIPsetHminCumulative (SCIP *scip, SCIP_CONS *cons, int hmin)
 
SCIP_EXPORT int SCIPgetHminCumulative (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPORT SCIP_RETCODE SCIPsetHmaxCumulative (SCIP *scip, SCIP_CONS *cons, int hmax)
 
SCIP_EXPORT int SCIPgetHmaxCumulative (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPORT SCIP_VAR ** SCIPgetVarsCumulative (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPORT int SCIPgetNVarsCumulative (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPORT int SCIPgetCapacityCumulative (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPORT int * SCIPgetDurationsCumulative (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPORT int * SCIPgetDemandsCumulative (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPORT 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_EXPORT SCIP_RETCODE SCIPnormalizeCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int *capacity, int *nchgcoefs, int *nchgsides)
 
SCIP_EXPORT SCIP_RETCODE SCIPsplitCumulativeCondition (SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *hmin, int *hmax, int *split)
 
SCIP_EXPORT 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_EXPORT 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_EXPORT 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_EXPORT SCIP_RETCODE SCIPvisualizeConsCumulative (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPORT SCIP_RETCODE SCIPsetSolveCumulative (SCIP *scip, SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)))
 
SCIP_EXPORT 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_EXPORT SCIP_RETCODE SCIPcreateWorstCaseProfile (SCIP *scip, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands)
 
SCIP_EXPORT int SCIPcomputeHmin (SCIP *scip, SCIP_PROFILE *profile, int capacity)
 
SCIP_EXPORT int SCIPcomputeHmax (SCIP *scip, SCIP_PROFILE *profile, int capacity)