cons_cumulative.c

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*                  This file is part of the program and library             */
/*         SCIP --- Solving Constraint Integer Programs                      */
/*                                                                           */
/*  Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB)                      */
/*                                                                           */
/*  Licensed under the Apache License, Version 2.0 (the "License");          */
/*  you may not use this file except in compliance with the License.         */
/*  You may obtain a copy of the License at                                  */
/*                                                                           */
/*      http://www.apache.org/licenses/LICENSE-2.0                           */
/*                                                                           */
/*  Unless required by applicable law or agreed to in writing, software      */
/*  distributed under the License is distributed on an "AS IS" BASIS,        */
/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
/*  See the License for the specific language governing permissions and      */
/*  limitations under the License.                                           */
/*                                                                           */
/*  You should have received a copy of the Apache-2.0 license                */
/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 
/**@file   cons_cumulative.c
 * @ingroup DEFPLUGINS_CONS
 * @brief  constraint handler for cumulative constraints
 * @author Timo Berthold
 * @author Stefan Heinz
 * @author Jens Schulz
 *
 * Given:
 * - a set of jobs, represented by their integer start time variables \f$S_j\f$, their array of processing times \f$p_j\f$ and of
 *   their demands \f$d_j\f$.
 * - an integer resource capacity \f$C\f$
 *
 * The cumulative constraint ensures that for each point in time \f$t\f$ \f$\sum_{j: S_j \leq t < S_j + p_j} d_j \leq C\f$ holds.
 *
 * Separation:
 * - can be done using binary start time model, see Pritskers, Watters and Wolfe
 * - or by just separating relatively weak cuts on the integer 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)
 *
 */
 
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
 
#include <assert.h>
#include <string.h>
 
#include "tclique/tclique.h"
#include "scip/cons_cumulative.h"
#include "scip/cons_linking.h"
#include "scip/cons_knapsack.h"
#include "scip/scipdefplugins.h"
 
/**@name Constraint handler properties
 *
 * @{
 */
 
/* constraint handler properties */
#define CONSHDLR_NAME          "cumulative"
#define CONSHDLR_DESC          "cumulative constraint handler"
#define CONSHDLR_SEPAPRIORITY   2100000 /**< priority of the constraint handler for separation */
#define CONSHDLR_ENFOPRIORITY  -2040000 /**< priority of the constraint handler for constraint enforcing */
#define CONSHDLR_CHECKPRIORITY -3030000 /**< priority of the constraint handler for checking feasibility */
#define CONSHDLR_SEPAFREQ             1 /**< frequency for separating cuts; zero means to separate only in the root node */
#define CONSHDLR_PROPFREQ             1 /**< frequency for propagating domains; zero means only preprocessing propagation */
#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 */
#define CONSHDLR_MAXPREROUNDS        -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
#define CONSHDLR_DELAYSEPA        FALSE /**< should separation method be delayed, if other separators found cuts? */
#define CONSHDLR_DELAYPROP        FALSE /**< should propagation method be delayed, if other propagators found reductions? */
#define CONSHDLR_NEEDSCONS         TRUE /**< should the constraint handler be skipped, if no constraints are available? */
 
#define CONSHDLR_PRESOLTIMING            SCIP_PRESOLTIMING_ALWAYS
#define CONSHDLR_PROP_TIMING             SCIP_PROPTIMING_BEFORELP
 
/**@} */
 
/**@name Default parameter values
 *
 * @{
 */
 
/* default parameter values */
 
/* separation */
#define DEFAULT_USEBINVARS             FALSE /**< should the binary representation be used? */
#define DEFAULT_LOCALCUTS              FALSE /**< should cuts be added only locally? */
#define DEFAULT_USECOVERCUTS            TRUE /**< should covering cuts be added? */
#define DEFAULT_CUTSASCONSS             TRUE /**< should the cuts be created as knapsack constraints? */
#define DEFAULT_SEPAOLD                 TRUE /**< shall old sepa algo be applied? */
 
/* propagation */
#define DEFAULT_TTINFER                 TRUE /**< should time-table (core-times) propagator be used to infer bounds? */
#define DEFAULT_EFCHECK                FALSE /**< should edge-finding be used to detect an overload? */
#define DEFAULT_EFINFER                FALSE /**< should edge-finding be used to infer bounds? */
#define DEFAULT_USEADJUSTEDJOBS        FALSE /**< should during edge-finding jobs be adusted which run on the border of the effective time horizon? */
#define DEFAULT_TTEFCHECK               TRUE /**< should time-table edge-finding be used to detect an overload? */
#define DEFAULT_TTEFINFER               TRUE /**< should time-table edge-finding be used to infer bounds? */
 
/* presolving */
#define DEFAULT_DUALPRESOLVE            TRUE /**< should dual presolving be applied? */
#define DEFAULT_COEFTIGHTENING         FALSE /**< should coeffisient tightening be applied? */
#define DEFAULT_NORMALIZE               TRUE /**< should demands and capacity be normalized? */
#define DEFAULT_PRESOLPAIRWISE          TRUE /**< should pairwise constraint comparison be performed in presolving? */
#define DEFAULT_DISJUNCTIVE             TRUE /**< extract disjunctive constraints? */
#define DEFAULT_DETECTDISJUNCTIVE       TRUE /**< search for conflict set via maximal cliques to detect disjunctive constraints */
#define DEFAULT_DETECTVARBOUNDS         TRUE /**< search for conflict set via maximal cliques to detect variable bound constraints */
#define DEFAULT_MAXNODES             10000LL /**< number of branch-and-bound nodes to solve an independent cumulative constraint  (-1: no limit) */
 
/* enforcement */
#define DEFAULT_FILLBRANCHCANDS        FALSE /**< should branching candidates be added to storage? */
 
/* conflict analysis */
#define DEFAULT_USEBDWIDENING           TRUE /**< should bound widening be used during conflict analysis? */
 
/**@} */
 
/**@name Event handler properties
 *
 * @{
 */
 
#define EVENTHDLR_NAME         "cumulative"
#define EVENTHDLR_DESC         "bound change event handler for cumulative constraints"
 
/**@} */
 
/*
 * Data structures
 */
 
/** constraint data for cumulative constraints */
struct SCIP_ConsData
{
   SCIP_VAR**            vars;               /**< array of variable representing the start time of each job */
   SCIP_Bool*            downlocks;          /**< array to store if the variable has a down lock */
   SCIP_Bool*            uplocks;            /**< array to store if the variable has an uplock */
   SCIP_CONS**           linkingconss;       /**< array of linking constraints for the integer variables */
   SCIP_ROW**            demandrows;         /**< array of rows of linear relaxation of this problem */
   SCIP_ROW**            scoverrows;         /**< array of rows of small cover cuts of this problem */
   SCIP_ROW**            bcoverrows;         /**< array of rows of big cover cuts of this problem */
   int*                  demands;            /**< array containing corresponding demands */
   int*                  durations;          /**< array containing corresponding durations */
   SCIP_Real             resstrength1;       /**< stores the resource strength 1*/
   SCIP_Real             resstrength2;       /**< stores the resource strength 2 */
   SCIP_Real             cumfactor1;         /**< stroes the cumulativeness of the constraint */
   SCIP_Real             disjfactor1;        /**< stores the disjunctiveness of the constraint */
   SCIP_Real             disjfactor2;        /**< stores the disjunctiveness of the constraint */
   SCIP_Real             estimatedstrength;
   int                   nvars;              /**< number of variables */
   int                   varssize;           /**< size of the arrays */
   int                   ndemandrows;        /**< number of rows of cumulative constrint for linear relaxation */
   int                   demandrowssize;     /**< size of array rows of demand rows */
   int                   nscoverrows;        /**< number of rows of small cover cuts */
   int                   scoverrowssize;     /**< size of array of small cover cuts */
   int                   nbcoverrows;        /**< number of rows of big cover cuts */
   int                   bcoverrowssize;     /**< size of array of big cover cuts */
   int                   capacity;           /**< available cumulative capacity */
 
   int                   hmin;               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax;               /**< right bound of time axis to be considered  (not including hmax) */
 
   unsigned int          signature;          /**< constraint signature which is need for pairwise comparison */
 
   unsigned int          validsignature:1;   /**< is the signature valid */
   unsigned int          normalized:1;       /**< is the constraint normalized */
   unsigned int          covercuts:1;        /**< cover cuts are created? */
   unsigned int          propagated:1;       /**< is constraint propagted */
   unsigned int          varbounds:1;        /**< bool to store if variable bound strengthening was already preformed */
   unsigned int          triedsolving:1;     /**< bool to store if we tried already to solve that constraint as independent subproblem */
 
#ifdef SCIP_STATISTIC
   int                   maxpeak;
#endif
};
 
/** constraint handler data */
struct SCIP_ConshdlrData
{
   SCIP_EVENTHDLR*       eventhdlr;          /**< event handler for bound change events */
 
   SCIP_Bool             usebinvars;         /**< should the binary variables be used? */
   SCIP_Bool             cutsasconss;        /**< should the cumulative constraint create cuts as knapsack constraints? */
   SCIP_Bool             ttinfer;            /**< should time-table (core-times) propagator be used to infer bounds? */
   SCIP_Bool             efcheck;            /**< should edge-finding be used to detect an overload? */
   SCIP_Bool             efinfer;            /**< should edge-finding be used to infer bounds? */
   SCIP_Bool             useadjustedjobs;    /**< should during edge-finding jobs be adusted which run on the border of the effective time horizon? */
   SCIP_Bool             ttefcheck;          /**< should time-table edge-finding be used to detect an overload? */
   SCIP_Bool             ttefinfer;          /**< should time-table edge-finding be used to infer bounds? */
   SCIP_Bool             localcuts;          /**< should cuts be added only locally? */
   SCIP_Bool             usecovercuts;       /**< should covering cuts be added? */
   SCIP_Bool             sepaold;            /**< shall old sepa algo be applied? */
 
   SCIP_Bool             fillbranchcands;    /**< should branching candidates be added to storage? */
 
   SCIP_Bool             dualpresolve;       /**< should dual presolving be applied? */
   SCIP_Bool             coeftightening;     /**< should coeffisient tightening be applied? */
   SCIP_Bool             normalize;          /**< should demands and capacity be normalized? */
   SCIP_Bool             disjunctive;        /**< extract disjunctive constraints? */
   SCIP_Bool             detectdisjunctive;  /**< search for conflict set via maximal cliques to detect disjunctive constraints */
   SCIP_Bool             detectvarbounds;    /**< search for conflict set via maximal cliques to detect variable bound constraints */
   SCIP_Bool             usebdwidening;      /**< should bound widening be used during conflict analysis? */
   SCIP_Bool             presolpairwise;     /**< should pairwise constraint comparison be performed in presolving? */
   SCIP_Bool             detectedredundant;  /**< was detection of redundant constraints already performed? */
 
   SCIP_Longint          maxnodes;           /**< number of branch-and-bound nodes to solve an independent cumulative constraint  (-1: no limit) */
 
   SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)); /**< method to use a single cumulative condition */
 
   /* statistic values which are collected if SCIP_STATISTIC is defined */
#ifdef SCIP_STATISTIC
   SCIP_Longint          nlbtimetable;       /**< number of times the lower bound was tightened by the time-table propagator */
   SCIP_Longint          nubtimetable;       /**< number of times the upper bound was tightened by the time-table propagator */
   SCIP_Longint          ncutofftimetable;   /**< number of times the a cutoff was detected due to time-table propagator */
   SCIP_Longint          nlbedgefinder;      /**< number of times the lower bound was tightened by the edge-finder propagator */
   SCIP_Longint          nubedgefinder;      /**< number of times the upper bound was tightened by the edge-finder propagator */
   SCIP_Longint          ncutoffedgefinder;  /**< number of times the a cutoff was detected due to edge-finder propagator */
   SCIP_Longint          ncutoffoverload;    /**< number of times the a cutoff was detected due to overload checking via edge-finding */
   SCIP_Longint          nlbTTEF;            /**< number of times the lower bound was tightened by time-table edge-finding */
   SCIP_Longint          nubTTEF;            /**< number of times the upper bound was tightened by time-table edge-finding */
   SCIP_Longint          ncutoffoverloadTTEF;/**< number of times the a cutoff was detected due to overload checking via time-table edge-finding */
 
   int                   nirrelevantjobs;    /**< number of time a irrelevant/redundant jobs was removed form a constraint */
   int                   nalwaysruns;        /**< number of time a job removed form a constraint which run completely during the effective horizon */
   int                   nremovedlocks;      /**< number of times a up or down lock was removed */
   int                   ndualfixs;          /**< number of times a dual fix was performed by a single constraint */
   int                   ndecomps;           /**< number of times a constraint was decomposed */
   int                   ndualbranchs;       /**< number of times a dual branch was discoverd and applicable via probing */
   int                   nallconsdualfixs;   /**< number of times a dual fix was performed due to knowledge of all cumulative constraints */
   int                   naddedvarbounds;    /**< number of added variable bounds constraints */
   int                   naddeddisjunctives; /**< number of added disjunctive constraints */
 
   SCIP_Bool             iscopy;             /**< Boolean to store if constraint handler is part of a copy */
#endif
};
 
/**@name Inference Information Methods
 *
 *  An inference information can be passed with each domain reduction to SCIP. This information is passed back to the
 *  constraint handler if the corresponding bound change has to be explained. It can be used to store information which
 *  help to construct a reason/explanation for a bound change. The inference information is limited to size of integer.
 *
 *  In case of the cumulative constraint handler we store the used propagation algorithms for that particular bound
 *  change and the earliest start and latest completion time of all jobs in the conflict set.
 *
 * @{
 */
 
/** Propagation rules */
enum Proprule
{
   PROPRULE_0_INVALID            = 0,        /**< invalid inference information */
   PROPRULE_1_CORETIMES          = 1,        /**< core-time propagator */
   PROPRULE_2_EDGEFINDING        = 2,        /**< edge-finder */
   PROPRULE_3_TTEF               = 3         /**< time-table edeg-finding */
};
typedef enum Proprule PROPRULE;
 
/** inference information */
struct InferInfo
{
   union
   {
      /** struct to use the inference information */
      struct
      {
         unsigned int    proprule:2;         /**< propagation rule that was applied */
         unsigned int    data1:15;           /**< data field one */
         unsigned int    data2:15;           /**< data field two */
      } asbits;
      int                asint;              /**< inference information as a single int value */
   } val;
};
typedef struct InferInfo INFERINFO;
 
/** converts an integer into an inference information */
static
INFERINFO intToInferInfo(
   int                   i                   /**< integer to convert */
   )
{
   INFERINFO inferinfo;
 
   inferinfo.val.asint = i;
 
   return inferinfo;
}
 
/** converts an inference information into an int */
static
int inferInfoToInt(
   INFERINFO             inferinfo           /**< inference information to convert */
   )
{
   return inferinfo.val.asint;
}
 
/** returns the propagation rule stored in the inference information */
static
PROPRULE inferInfoGetProprule(
   INFERINFO             inferinfo           /**< inference information to convert */
   )
{
   return (PROPRULE) inferinfo.val.asbits.proprule;
}
 
/** returns data field one of the inference information */
static
int inferInfoGetData1(
   INFERINFO             inferinfo           /**< inference information to convert */
   )
{
   return (int) inferinfo.val.asbits.data1;
}
 
/** returns data field two of the inference information */
static
int inferInfoGetData2(
   INFERINFO             inferinfo           /**< inference information to convert */
   )
{
   return (int) inferinfo.val.asbits.data2;
}
 
/** returns whether the inference information is valid */
static
SCIP_Bool inferInfoIsValid(
   INFERINFO             inferinfo           /**< inference information to convert */
   )
{
   return (inferinfo.val.asint != 0);
}
 
 
/** constructs an inference information out of a propagation rule, an earliest start and a latest completion time */
static
INFERINFO getInferInfo(
   PROPRULE              proprule,           /**< propagation rule that deduced the value */
   int                   data1,              /**< data field one */
   int                   data2               /**< data field two */
   )
{
   INFERINFO inferinfo;
 
   /* check that the data members are in the range of the available bits */
   if( proprule == PROPRULE_0_INVALID || data1 < 0 || data1 >= (1<<15) || data2 < 0 || data2 >= (1<<15) )
   {
      inferinfo.val.asint = 0;
      assert(inferInfoGetProprule(inferinfo) == PROPRULE_0_INVALID);
      assert(inferInfoIsValid(inferinfo) == FALSE);
   }
   else
   {
      inferinfo.val.asbits.proprule = proprule; /*lint !e641*/
      inferinfo.val.asbits.data1 = (unsigned int) data1; /*lint !e732*/
      inferinfo.val.asbits.data2 = (unsigned int) data2; /*lint !e732*/
      assert(inferInfoIsValid(inferinfo) == TRUE);
   }
 
   return inferinfo;
}
 
/**@} */
 
/*
 * Local methods
 */
 
/**@name Miscellaneous Methods
 *
 * @{
 */
 
#ifndef NDEBUG
 
/** compute the core of a job which lies in certain interval [begin, end) */
static
SCIP_Longint computeCoreWithInterval(
   int                   begin,              /**< begin of the interval */
   int                   end,                /**< end of the interval */
   int                   ect,                /**< earliest completion time */
   int                   lst                 /**< latest start time */
   )
{
   int core;
 
   core = MAX(0, MIN(end, ect) - MAX(lst, begin));
 
   return core;
}
#else
#define computeCoreWithInterval(begin, end, ect, lst) (MAX(0, MIN((end), (ect)) - MAX((lst), (begin))))
#endif
 
/** returns the implied earliest start time */   /*lint -e{715}*/
static
SCIP_RETCODE computeImpliedEst(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_VAR*             var,                /**< variable for which the implied est should be returned */
   SCIP_HASHMAP*         addedvars,          /**< hash map containig the variable which are already added */
   int*                  est                 /**< pointer to store the implied earliest start time */
   )
{  /*lint --e{715}*/
#if 0
   SCIP_VAR** vbdvars;
   SCIP_VAR* vbdvar;
   SCIP_Real* vbdcoefs;
   SCIP_Real* vbdconsts;
   void* image;
   int nvbdvars;
   int v;
#endif
 
   (*est) = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
 
#if 0
   /* the code contains a bug; we need to check if an implication forces that the jobs do not run in parallel */
 
   nvbdvars = SCIPvarGetNVlbs(var);
   vbdvars = SCIPvarGetVlbVars(var);
   vbdcoefs = SCIPvarGetVlbCoefs(var);
   vbdconsts = SCIPvarGetVlbConstants(var);
 
   for( v = 0; v < nvbdvars; ++v )
   {
      vbdvar = vbdvars[v];
      assert(vbdvar != NULL);
 
      image = SCIPhashmapGetImage(addedvars, (void*)vbdvar);
 
      if( image != NULL && SCIPisEQ(scip, vbdcoefs[v], 1.0 ) )
      {
         int duration;
         int vbdconst;
 
         duration = (int)(size_t)image;
         vbdconst = SCIPconvertRealToInt(scip, vbdconsts[v]);
 
         SCIPdebugMsg(scip, "check implication <%s>[%g,%g] >= <%s>[%g,%g] + <%g>\n",
            SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
            SCIPvarGetName(vbdvar), SCIPvarGetLbLocal(vbdvar), SCIPvarGetUbLocal(vbdvar), vbdconsts[v]);
 
         if( duration >= vbdconst )
         {
            int impliedest;
 
            impliedest =  SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vbdvar)) + duration;
 
            if( (*est) < impliedest )
            {
               (*est) = impliedest;
 
               SCIP_CALL( SCIPhashmapRemove(addedvars, (void*)vbdvar) );
            }
         }
      }
   }
#endif
 
   return SCIP_OKAY;
}
 
/** returns the implied latest completion time */    /*lint -e{715}*/
static
SCIP_RETCODE computeImpliedLct(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_VAR*             var,                /**< variable for which the implied est should be returned */
   int                   duration,           /**< duration of the given job */
   SCIP_HASHMAP*         addedvars,          /**< hash map containig the variable which are already added */
   int*                  lct                 /**< pointer to store the implied latest completion time */
   )
{  /*lint --e{715}*/
#if 0
   SCIP_VAR** vbdvars;
   SCIP_VAR* vbdvar;
   SCIP_Real* vbdcoefs;
   SCIP_Real* vbdconsts;
   int nvbdvars;
   int v;
#endif
 
   (*lct) = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) + duration;
 
#if 0
   /* the code contains a bug; we need to check if an implication forces that the jobs do not run in parallel */
 
   nvbdvars = SCIPvarGetNVubs(var);
   vbdvars = SCIPvarGetVubVars(var);
   vbdcoefs = SCIPvarGetVubCoefs(var);
   vbdconsts = SCIPvarGetVubConstants(var);
 
   for( v = 0; v < nvbdvars; ++v )
   {
      vbdvar = vbdvars[v];
      assert(vbdvar != NULL);
 
      if( SCIPhashmapExists(addedvars, (void*)vbdvar) &&  SCIPisEQ(scip, vbdcoefs[v], 1.0 ) )
      {
         int vbdconst;
 
         vbdconst = SCIPconvertRealToInt(scip, -vbdconsts[v]);
 
         SCIPdebugMsg(scip, "check implication <%s>[%g,%g] <= <%s>[%g,%g] + <%g>\n",
            SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
            SCIPvarGetName(vbdvar), SCIPvarGetLbLocal(vbdvar), SCIPvarGetUbLocal(vbdvar), vbdconsts[v]);
 
         if( duration >= -vbdconst )
         {
            int impliedlct;
 
            impliedlct = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vbdvar));
 
            if( (*lct) > impliedlct )
            {
               (*lct) = impliedlct;
 
               SCIP_CALL( SCIPhashmapRemove(addedvars, (void*)vbdvar) );
            }
         }
      }
   }
#endif
 
   return SCIP_OKAY;
}
 
/** collects all necessary binary variables to represent the jobs which can be active at time point of interest */
static
SCIP_RETCODE collectBinaryVars(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< constraint data */
   SCIP_VAR***           vars,               /**< pointer to the array to store the binary variables */
   int**                 coefs,              /**< pointer to store the coefficients */
   int*                  nvars,              /**< number if collect binary variables */
   int*                  startindices,       /**< permutation with rspect to the start times */
   int                   curtime,            /**< current point in time */
   int                   nstarted,           /**< number of jobs that start before the curtime or at curtime */
   int                   nfinished           /**< number of jobs that finished before curtime or at curtime */
   )
{
   int nrowvars;
   int startindex;
   int size;
 
   size = 10;
   nrowvars = 0;
   startindex = nstarted - 1;
 
   SCIP_CALL( SCIPallocBufferArray(scip, vars, size) );
   SCIP_CALL( SCIPallocBufferArray(scip, coefs, size) );
 
   /* search for the (nstarted - nfinished) jobs which are active at curtime */
   while( nstarted - nfinished > nrowvars )
   {
      SCIP_VAR* var;
      int endtime;
      int duration;
      int demand;
      int varidx;
 
      /* collect job information */
      varidx = startindices[startindex];
      assert(varidx >= 0 && varidx < consdata->nvars);
 
      var = consdata->vars[varidx];
      duration = consdata->durations[varidx];
      demand = consdata->demands[varidx];
      assert(var != NULL);
 
      endtime = SCIPconvertRealToInt(scip, SCIPvarGetUbGlobal(var)) + duration;
 
      /* check the end time of this job is larger than the curtime; in this case the job is still running */
      if( endtime > curtime )
      {
         SCIP_VAR** binvars;
         SCIP_Real* vals;
         int nbinvars;
         int start;
         int end;
         int b;
 
         /* check if the linking constraints exists */
         assert(SCIPexistsConsLinking(scip, var));
         assert(SCIPgetConsLinking(scip, var) != NULL);
         assert(SCIPgetConsLinking(scip, var) == consdata->linkingconss[varidx]);
 
         /* collect linking constraint information */
         SCIP_CALL( SCIPgetBinvarsLinking(scip, consdata->linkingconss[varidx], &binvars, &nbinvars) );
         vals = SCIPgetValsLinking(scip, consdata->linkingconss[varidx]);
 
         start = curtime - duration + 1;
         end = MIN(curtime, endtime - duration);
 
         for( b = 0; b < nbinvars; ++b )
         {
            if( vals[b] < start )
               continue;
 
            if( vals[b] > end )
               break;
 
            assert(binvars[b] != NULL);
 
            /* ensure array proper array size */
            if( size == *nvars )
            {
               size *= 2;
               SCIP_CALL( SCIPreallocBufferArray(scip, vars, size) );
               SCIP_CALL( SCIPreallocBufferArray(scip, coefs, size) );
            }
 
            (*vars)[*nvars] = binvars[b];
            (*coefs)[*nvars] = demand;
            (*nvars)++;
         }
         nrowvars++;
      }
 
      startindex--;
   }
 
   return SCIP_OKAY;
}
 
/** collect all integer variable which belong to jobs which can run at the point of interest */
static
SCIP_RETCODE collectIntVars(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< constraint data */
   SCIP_VAR***           activevars,         /**< jobs that are currently running */
   int*                  startindices,       /**< permutation with rspect to the start times */
   int                   curtime,            /**< current point in time */
   int                   nstarted,           /**< number of jobs that start before the curtime or at curtime */
   int                   nfinished,          /**< number of jobs that finished before curtime or at curtime */
   SCIP_Bool             lower,              /**< shall cuts be created due to lower or upper bounds? */
   int*                  lhs                 /**< lhs for the new row sum of lbs + minoffset */
   )
{
   SCIP_VAR* var;
   int startindex;
   int endtime;
   int duration;
   int starttime;
 
   int varidx;
   int sumofstarts;
   int mindelta;
   int counter;
 
   assert(curtime >= consdata->hmin);
   assert(curtime < consdata->hmax);
 
   counter = 0;
   sumofstarts = 0;
 
   mindelta = INT_MAX;
 
   startindex = nstarted - 1;
 
   /* search for the (nstarted - nfinished) jobs which are active at curtime */
   while( nstarted - nfinished > counter )
   {
      assert(startindex >= 0);
 
      /* collect job information */
      varidx = startindices[startindex];
      assert(varidx >= 0 && varidx < consdata->nvars);
 
      var = consdata->vars[varidx];
      duration = consdata->durations[varidx];
      assert(duration > 0);
      assert(var != NULL);
 
      if( lower )
         starttime = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
      else
         starttime = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
 
      endtime = MIN(starttime + duration, consdata->hmax);
 
      /* check the end time of this job is larger than the curtime; in this case the job is still running */
      if( endtime > curtime )
      {
         (*activevars)[counter] = var;
         sumofstarts += starttime;
         mindelta = MIN(mindelta, endtime - curtime); /* this amount of schifting holds for lb and ub */
         counter++;
      }
 
      startindex--;
   }
 
   assert(mindelta > 0);
   *lhs = lower ? sumofstarts + mindelta : sumofstarts - mindelta;
 
   return SCIP_OKAY;
}
 
/** initialize the sorted event point arrays */
static
void createSortedEventpoints(
   SCIP*                 scip,               /**< SCIP data structure */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations per start time variable */
   int*                  starttimes,         /**< array to store sorted start events */
   int*                  endtimes,           /**< array to store sorted end events */
   int*                  startindices,       /**< permutation with rspect to the start times */
   int*                  endindices,         /**< permutation with rspect to the end times */
   SCIP_Bool             local               /**< shall local bounds be used */
   )
{
   SCIP_VAR* var;
   int j;
 
   assert(vars != NULL || nvars == 0);
 
   /* assign variables, start and endpoints to arrays */
   for ( j = 0; j < nvars; ++j )
   {
      assert(vars != NULL);
 
      var = vars[j];
      assert(var != NULL);
 
      if( local )
         starttimes[j] = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
      else
         starttimes[j] = SCIPconvertRealToInt(scip, SCIPvarGetLbGlobal(var));
 
      startindices[j] = j;
 
      if( local )
         endtimes[j] = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) + durations[j];
      else
         endtimes[j] = SCIPconvertRealToInt(scip, SCIPvarGetUbGlobal(var)) + durations[j];
 
      endindices[j] = j;
   }
 
   /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
   SCIPsortIntInt(starttimes, startindices, j);
   SCIPsortIntInt(endtimes, endindices, j);
}
 
/** initialize the sorted event point arrays w.r.t. the given primal solutions */
static
void createSortedEventpointsSol(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_SOL*             sol,                /**< solution */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations per start time variable */
   int*                  starttimes,         /**< array to store sorted start events */
   int*                  endtimes,           /**< array to store sorted end events */
   int*                  startindices,       /**< permutation with rspect to the start times */
   int*                  endindices          /**< permutation with rspect to the end times */
   )
{
   SCIP_VAR* var;
   int j;
 
   assert(vars != NULL || nvars == 0);
 
   /* assign variables, start and endpoints to arrays */
   for ( j = 0; j < nvars; ++j )
   {
      assert(vars != NULL);
 
      var = vars[j];
      assert(var != NULL);
 
      starttimes[j] = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, var));
      startindices[j] = j;
 
      endtimes[j] = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, var)) + durations[j];
      endindices[j] = j;
   }
 
   /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
   SCIPsortIntInt(starttimes, startindices, j);
   SCIPsortIntInt(endtimes, endindices, j);
}
 
/** initialize the sorted event point arrays
 *
 * @todo Check the separation process!
 */
static
void createSelectedSortedEventpointsSol(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< constraint data */
   SCIP_SOL*             sol,                /**< primal CIP solution, NULL for current LP solution */
   int*                  starttimes,         /**< array to store sorted start events */
   int*                  endtimes,           /**< array to store sorted end events */
   int*                  startindices,       /**< permutation with rspect to the start times */
   int*                  endindices,         /**< permutation with rspect to the end times */
   int*                  nvars,              /**< number of variables that are integral */
   SCIP_Bool             lower               /**< shall the constraints be derived for lower or upper bounds? */
   )
{
   SCIP_VAR* var;
   int tmpnvars;
   int j;
 
   tmpnvars = consdata->nvars;
   *nvars = 0;
 
   /* assign variables, start and endpoints to arrays */
   for ( j = 0; j < tmpnvars; ++j )
   {
      var = consdata->vars[j];
      assert(var != NULL);
      assert(consdata->durations[j] > 0);
      assert(consdata->demands[j] > 0);
 
      if( lower )
      {
         /* only consider jobs that are at their lower or upper bound */
         if( !SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, var))
            || !SCIPisFeasEQ(scip, SCIPgetSolVal(scip, sol, var), SCIPvarGetLbLocal(var)) )
            continue;
 
         starttimes[*nvars] = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, var));
         startindices[*nvars] = j;
 
         endtimes[*nvars] =  starttimes[*nvars] + consdata->durations[j];
         endindices[*nvars] = j;
 
         SCIPdebugMsg(scip, "%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
            *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var),
            consdata->durations[j],
            starttimes[*nvars], starttimes[*nvars] + consdata->durations[startindices[*nvars]],
            consdata->demands[startindices[*nvars]]);
 
         (*nvars)++;
      }
      else
      {
         if( !SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, var))
            || !SCIPisFeasEQ(scip, SCIPgetSolVal(scip, sol, var), SCIPvarGetUbLocal(var)) )
            continue;
 
         starttimes[*nvars] = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, var));
         startindices[*nvars] = j;
 
         endtimes[*nvars] =  starttimes[*nvars] + consdata->durations[j];
         endindices[*nvars] = j;
 
         SCIPdebugMsg(scip, "%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
            *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var),
            consdata->durations[j],
            starttimes[*nvars], starttimes[*nvars] + consdata->durations[startindices[*nvars]],
            consdata->demands[startindices[*nvars]]);
 
         (*nvars)++;
      }
   }
 
   /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
   SCIPsortIntInt(starttimes, startindices, *nvars);
   SCIPsortIntInt(endtimes, endindices, *nvars);
 
#ifdef SCIP_DEBUG
   SCIPdebugMsg(scip, "sorted output %d\n", *nvars);
 
   for ( j = 0; j < *nvars; ++j )
   {
      SCIPdebugMsg(scip, "%d: job[%d] starttime %d, endtime = %d, demand = %d\n", j,
         startindices[j], starttimes[j], starttimes[j] + consdata->durations[startindices[j]],
         consdata->demands[startindices[j]]);
   }
 
   for ( j = 0; j < *nvars; ++j )
   {
      SCIPdebugMsg(scip, "%d: job[%d] endtime %d,  demand = %d\n", j, endindices[j], endtimes[j],
         consdata->demands[endindices[j]]);
   }
#endif
}
 
#ifdef SCIP_STATISTIC
/** this method checks for relevant intervals for energetic reasoning */
static
SCIP_RETCODE computeRelevantEnergyIntervals(
   SCIP*                 scip,               /**< SCIP data structure */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations */
   int*                  demands,            /**< array of demands */
   int                   capacity,           /**< cumulative capacity */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   int**                 timepoints,         /**< array to store relevant points in time */
   SCIP_Real**           cumulativedemands,  /**< array to store the estimated cumulative demand for each point in time */
   int*                  ntimepoints,        /**< pointer to store the number of timepoints */
   int*                  maxdemand,          /**< pointer to store maximum over all demands */
   SCIP_Real*            minfreecapacity     /**< pointer to store the minimum free capacity */
   )
{
   int* starttimes;         /* stores when each job is starting */
   int* endtimes;           /* stores when each job ends */
   int* startindices;       /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
   int* endindices;         /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
 
   SCIP_Real totaldemand;
   int curtime;             /* point in time which we are just checking */
   int endindex;            /* index of endsolvalues with: endsolvalues[endindex] > curtime */
 
   int j;
 
   assert( scip != NULL );
   assert(durations != NULL);
   assert(demands != NULL);
   assert(capacity >= 0);
 
   /* if no activities are associated with this cumulative then this constraint is redundant */
   if( nvars == 0 )
      return SCIP_OKAY;
 
   assert(vars != NULL);
 
   SCIP_CALL( SCIPallocBufferArray(scip, &starttimes, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &endtimes, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &startindices, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &endindices, nvars) );
 
   /* create event point arrays */
   createSortedEventpoints(scip, nvars, vars, durations, starttimes, endtimes, startindices, endindices, TRUE);
 
   endindex = 0;
   totaldemand = 0.0;
 
   *ntimepoints = 0;
   (*timepoints)[0] = starttimes[0];
   (*cumulativedemands)[0] = 0;
   *maxdemand = 0;
 
   /* check each startpoint of a job whether the capacity is kept or not */
   for( j = 0; j < nvars; ++j )
   {
      int lct;
      int idx;
 
      curtime = starttimes[j];
 
      if( curtime >= hmax )
         break;
 
      /* free all capacity usages of jobs the are no longer running */
      while( endindex < nvars && endtimes[endindex] <= curtime )
      {
         int est;
 
         if( (*timepoints)[*ntimepoints] < endtimes[endindex] )
         {
            (*ntimepoints)++;
            (*timepoints)[*ntimepoints] = endtimes[endindex];
            (*cumulativedemands)[*ntimepoints] = 0;
         }
 
         idx = endindices[endindex];
         est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[idx]));
         totaldemand -= (SCIP_Real) demands[idx] * durations[idx] / (endtimes[endindex] - est);
         endindex++;
 
         (*cumulativedemands)[*ntimepoints] = totaldemand;
      }
 
      idx = startindices[j];
      lct = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[idx]) + durations[idx]);
      totaldemand += (SCIP_Real) demands[idx] * durations[idx] / (lct - starttimes[j]);
 
      if( (*timepoints)[*ntimepoints] < curtime )
      {
         (*ntimepoints)++;
         (*timepoints)[*ntimepoints] = curtime;
         (*cumulativedemands)[*ntimepoints] = 0;
      }
 
      (*cumulativedemands)[*ntimepoints] = totaldemand;
 
      /* add the relative capacity requirements for all job which start at the curtime */
      while( j+1 < nvars && starttimes[j+1] == curtime )
      {
         ++j;
         idx = startindices[j];
         lct = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[idx]) + durations[idx]);
         totaldemand += (SCIP_Real) demands[idx] * durations[idx] / (lct - starttimes[j]);
 
         (*cumulativedemands)[*ntimepoints] = totaldemand;
      }
   } /*lint --e{850}*/
 
   /* free all capacity usages of jobs that are no longer running */
   while( endindex < nvars/* && endtimes[endindex] < hmax*/)
   {
      int est;
      int idx;
 
      if( (*timepoints)[*ntimepoints] < endtimes[endindex] )
      {
         (*ntimepoints)++;
         (*timepoints)[*ntimepoints] = endtimes[endindex];
         (*cumulativedemands)[*ntimepoints] = 0;
      }
 
      idx = endindices[endindex];
      est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[idx]));
      totaldemand -= (SCIP_Real) demands[idx] * durations[idx] / (endtimes[endindex] - est);
      (*cumulativedemands)[*ntimepoints] = totaldemand;
 
      ++endindex;
   }
 
   (*ntimepoints)++;
   /* compute minimum free capacity */
   (*minfreecapacity) = INT_MAX;
   for( j = 0; j < *ntimepoints; ++j )
   {
      if( (*timepoints)[j] >= hmin && (*timepoints)[j] < hmax )
         *minfreecapacity = MIN( *minfreecapacity, (SCIP_Real)capacity - (*cumulativedemands)[j] );
   }
 
   /* free buffer arrays */
   SCIPfreeBufferArray(scip, &endindices);
   SCIPfreeBufferArray(scip, &startindices);
   SCIPfreeBufferArray(scip, &endtimes);
   SCIPfreeBufferArray(scip, &starttimes);
 
   return SCIP_OKAY;
}
 
/** evaluates the cumulativeness and disjointness factor of a cumulative constraint */
static
SCIP_RETCODE evaluateCumulativeness(
   SCIP*                 scip,               /**< pointer to scip */
   SCIP_CONS*            cons                /**< cumulative constraint */
   )
{
   SCIP_CONSDATA* consdata;
   int nvars;
   int v;
   int capacity;
 
   /* output values: */
   SCIP_Real disjfactor2; /* (peak-capacity)/capacity * (large demands/nvars_t) */
   SCIP_Real cumfactor1;
   SCIP_Real resstrength1; /* overall strength */
   SCIP_Real resstrength2; /* timepoint wise maximum */
 
   /* helpful variables: */
   SCIP_Real globalpeak;
   SCIP_Real globalmaxdemand;
 
   /* get constraint data structure */
   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
 
   nvars = consdata->nvars;
   capacity = consdata->capacity;
   globalpeak = 0.0;
   globalmaxdemand = 0.0;
 
   disjfactor2 = 0.0;
   cumfactor1 = 0.0;
   resstrength2 = 0.0;
 
   /* check each starting time (==each job, but inefficient) */
   for( v = 0; v < nvars; ++v )
   {
      SCIP_Real peak;
      SCIP_Real maxdemand;
      SCIP_Real deltademand;
      int ndemands;
      int nlarge;
 
      int timepoint;
      int j;
      timepoint = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(consdata->vars[v]));
      peak = consdata->demands[v];
      ndemands = 1;
      maxdemand = 0;
      nlarge = 0;
 
      if( consdata->demands[v] > capacity / 3 )
         nlarge++;
 
      for( j = 0; j < nvars; ++j )
      {
         int lb;
 
         if( j == v )
            continue;
 
         maxdemand = 0.0;
         lb = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(consdata->vars[j]));
 
         if( lb <= timepoint && lb + consdata->durations[j] > timepoint )
         {
            peak += consdata->demands[j];
            ndemands++;
 
            if( consdata->demands[j] > consdata->capacity / 3 )
               nlarge++;
         }
      }
 
      deltademand = (SCIP_Real)peak / (SCIP_Real)ndemands;
      globalpeak = MAX(globalpeak, peak);
      globalmaxdemand = MAX(globalmaxdemand, maxdemand);
 
      if( peak > capacity )
      {
         disjfactor2 = MAX( disjfactor2, (peak-(SCIP_Real)capacity)/peak * (nlarge/(SCIP_Real)ndemands) );
         cumfactor1 = MAX( cumfactor1, (peak-capacity)/peak * (capacity-deltademand)/(SCIP_Real)capacity );
         resstrength2 = MAX(resstrength2, (capacity-maxdemand)/(peak-maxdemand) );
      }
   }
 
   resstrength1 = (capacity-globalmaxdemand) / (globalpeak-globalmaxdemand);
 
   consdata->maxpeak = SCIPconvertRealToInt(scip, globalpeak);
   consdata->disjfactor2 = disjfactor2;
   consdata->cumfactor1 = cumfactor1;
   consdata->resstrength2 = resstrength2;
   consdata->resstrength1 = resstrength1;
 
   /* get estimated res strength */
   {
      int* timepoints;
      SCIP_Real* estimateddemands;
      int ntimepoints;
      int maxdemand;
      SCIP_Real minfreecapacity;
 
      SCIP_CALL( SCIPallocBufferArray(scip, &timepoints, 2*nvars) );
      SCIP_CALL( SCIPallocBufferArray(scip, &estimateddemands, 2*nvars) );
 
      ntimepoints = 0;
      minfreecapacity = INT_MAX;
 
      SCIP_CALL( computeRelevantEnergyIntervals(scip, nvars, consdata->vars,
            consdata->durations, consdata->demands,
            capacity, consdata->hmin, consdata->hmax, &timepoints, &estimateddemands,
            &ntimepoints, &maxdemand, &minfreecapacity) );
 
      /* free buffer arrays */
      SCIPfreeBufferArray(scip, &estimateddemands);
      SCIPfreeBufferArray(scip, &timepoints);
 
      consdata->estimatedstrength = (SCIP_Real)(capacity - minfreecapacity) / (SCIP_Real) capacity;
   }
 
   SCIPstatisticPrintf("cumulative constraint<%s>: DISJ1=%g, DISJ2=%g, CUM=%g, RS1 = %g, RS2 = %g, EST = %g\n",
      SCIPconsGetName(cons), consdata->disjfactor1, disjfactor2, cumfactor1, resstrength1, resstrength2,
      consdata->estimatedstrength);
 
   return SCIP_OKAY;
}
#endif
 
/** gets the active variables together with the constant */
static
SCIP_RETCODE getActiveVar(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_VAR**            var,                /**< pointer to store the active variable */
   int*                  scalar,             /**< pointer to store the scalar */
   int*                  constant            /**< pointer to store the constant */
   )
{
   if( !SCIPvarIsActive(*var) )
   {
      SCIP_Real realscalar;
      SCIP_Real realconstant;
 
      realscalar = 1.0;
      realconstant = 0.0;
 
      assert(SCIPvarGetStatus(*var) == SCIP_VARSTATUS_AGGREGATED);
 
      /* transform variable to active variable */
      SCIP_CALL( SCIPgetProbvarSum(scip, var, &realscalar, &realconstant) );
      assert(!SCIPisZero(scip, realscalar));
      assert(SCIPvarIsActive(*var));
 
      if( realconstant < 0.0 )
         (*constant) = -SCIPconvertRealToInt(scip, -realconstant);
      else
         (*constant) = SCIPconvertRealToInt(scip, realconstant);
 
      if( realscalar < 0.0 )
         (*scalar) = -SCIPconvertRealToInt(scip, -realscalar);
      else
         (*scalar) = SCIPconvertRealToInt(scip, realscalar);
   }
   else
   {
      (*scalar) = 1;
      (*constant) = 0;
   }
 
   assert(*scalar != 0);
 
   return SCIP_OKAY;
}
 
/** computes the total energy of all jobs */
static
SCIP_Longint computeTotalEnergy(
   int*                  durations,          /**< array of job durations */
   int*                  demands,            /**< array of job demands */
   int                   njobs               /**< number of jobs */
   )
{
   SCIP_Longint energy;
   int j;
 
   energy = 0;
 
   for( j = 0; j < njobs; ++j )
      energy += (SCIP_Longint) durations[j] * demands[j];
 
   return energy;
}
 
/**@} */
 
/**@name Default method to solve a cumulative condition
 *
 * @{
 */
 
/** setup and solve subscip to solve single cumulative condition  */
static
SCIP_RETCODE setupAndSolveCumulativeSubscip(
   SCIP*                 subscip,            /**< subscip data structure */
   SCIP_Real*            objvals,            /**< array of objective coefficients for each job (linear objective function), or NULL if none */
   int*                  durations,          /**< array of durations */
   int*                  demands,            /**< array of demands */
   int                   njobs,              /**< number of jobs (activities) */
   int                   capacity,           /**< cumulative capacity */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   SCIP_Longint          maxnodes,           /**< maximum number of branch-and-bound nodes (-1: no limit) */
   SCIP_Real             timelimit,          /**< time limit for solving in seconds */
   SCIP_Real             memorylimit,        /**< memory limit for solving in mega bytes (MB) */
   SCIP_Real*            ests,               /**< array of earliest start times for each job */
   SCIP_Real*            lsts,               /**< array of latest start times for each job */
   SCIP_Bool*            infeasible,         /**< pointer to store if the subproblem was infeasible */
   SCIP_Bool*            unbounded,          /**< pointer to store if the problem is unbounded */
   SCIP_Bool*            solved,             /**< pointer to store if the problem is solved (to optimality) */
   SCIP_Bool*            error               /**< pointer to store if an error occurred */
   )
{
   SCIP_VAR** subvars;
   SCIP_CONS* cons;
 
   char name[SCIP_MAXSTRLEN];
   int v;
   SCIP_RETCODE retcode;
 
   assert(subscip != NULL);
 
   /* copy all plugins */
   SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
 
   /* create the subproblem */
   SCIP_CALL( SCIPcreateProbBasic(subscip, "cumulative") );
 
   SCIP_CALL( SCIPallocBlockMemoryArray(subscip, &subvars, njobs) );
 
   /* create for each job a start time variable */
   for( v = 0; v < njobs; ++v )
   {
      SCIP_Real objval;
 
      /* construct variable name */
      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "job%d", v);
 
      if( objvals == NULL )
         objval = 0.0;
      else
         objval = objvals[v];
 
      SCIP_CALL( SCIPcreateVarBasic(subscip, &subvars[v], name, ests[v], lsts[v], objval, SCIP_VARTYPE_INTEGER) );
      SCIP_CALL( SCIPaddVar(subscip, subvars[v]) );
   }
 
   /* create cumulative constraint */
   SCIP_CALL( SCIPcreateConsBasicCumulative(subscip, &cons, "cumulative",
         njobs, subvars, durations, demands, capacity) );
 
   /* set effective horizon */
   SCIP_CALL( SCIPsetHminCumulative(subscip, cons, hmin) );
   SCIP_CALL( SCIPsetHmaxCumulative(subscip, cons, hmax) );
 
   /* add cumulative constraint */
   SCIP_CALL( SCIPaddCons(subscip, cons) );
   SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
 
   /* set CP solver settings
    *
    * @note This "meta" setting has to be set first since this call overwrite all parameters including for example the
    *       time limit.
    */
   SCIP_CALL( SCIPsetEmphasis(subscip, SCIP_PARAMEMPHASIS_CPSOLVER, TRUE) );
 
   /* do not abort subproblem on CTRL-C */
   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
 
   /* disable output to console */
   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
 
   /* set limits for the subproblem */
   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", maxnodes) );
   SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
   SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
 
   /* forbid recursive call of heuristics and separators solving subMIPs */
   SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
 
   /* solve single cumulative constraint by branch and bound */
   retcode = SCIPsolve(subscip);
 
   if( retcode != SCIP_OKAY )
      (*error) = TRUE;
   else
   {
      SCIPdebugMsg(subscip, "solved single cumulative condition with status %d\n", SCIPgetStatus(subscip));
 
      /* evaluated solution status */
      switch( SCIPgetStatus(subscip) )
      {
      case SCIP_STATUS_INFORUNBD:
      case SCIP_STATUS_INFEASIBLE:
         (*infeasible) = TRUE;
         (*solved) = TRUE;
         break;
      case SCIP_STATUS_UNBOUNDED:
         (*unbounded) = TRUE;
         (*solved) = TRUE;
         break;
      case SCIP_STATUS_OPTIMAL:
      {
         SCIP_SOL* sol;
         SCIP_Real solval;
 
         sol = SCIPgetBestSol(subscip);
         assert(sol != NULL);
 
         for( v = 0; v < njobs; ++v )
         {
            solval = SCIPgetSolVal(subscip, sol, subvars[v]);
 
            ests[v] = solval;
            lsts[v] = solval;
         }
         (*solved) = TRUE;
         break;
      }
      case SCIP_STATUS_NODELIMIT:
      case SCIP_STATUS_TOTALNODELIMIT:
      case SCIP_STATUS_TIMELIMIT:
      case SCIP_STATUS_MEMLIMIT:
      case SCIP_STATUS_USERINTERRUPT:
      case SCIP_STATUS_TERMINATE:
         /* transfer the global bound changes */
         for( v = 0; v < njobs; ++v )
         {
            ests[v] = SCIPvarGetLbGlobal(subvars[v]);
            lsts[v] = SCIPvarGetUbGlobal(subvars[v]);
         }
         (*solved) = FALSE;
         break;
 
      case SCIP_STATUS_UNKNOWN:
      case SCIP_STATUS_STALLNODELIMIT:
      case SCIP_STATUS_GAPLIMIT:
      case SCIP_STATUS_PRIMALLIMIT:
      case SCIP_STATUS_DUALLIMIT:
      case SCIP_STATUS_SOLLIMIT:
      case SCIP_STATUS_BESTSOLLIMIT:
      case SCIP_STATUS_RESTARTLIMIT:
         SCIPerrorMessage("invalid status code <%d>\n", SCIPgetStatus(subscip));
         return SCIP_INVALIDDATA;
      }
   }
 
   /* release all variables */
   for( v = 0; v < njobs; ++v )
   {
      SCIP_CALL( SCIPreleaseVar(subscip, &subvars[v]) );
   }
 
   SCIPfreeBlockMemoryArray(subscip, &subvars, njobs);
 
   return SCIP_OKAY;
}
 
/** solve single cumulative condition using SCIP and a single cumulative constraint */
static
SCIP_DECL_SOLVECUMULATIVE(solveCumulativeViaScipCp)
{
   SCIP* subscip;
 
   SCIP_RETCODE retcode;
 
   assert(njobs > 0);
 
   (*solved) = FALSE;
   (*infeasible) = FALSE;
   (*unbounded) = FALSE;
   (*error) = FALSE;
 
   SCIPdebugMessage("solve independent cumulative condition with %d variables\n", njobs);
 
   /* initialize the sub-problem */
   SCIP_CALL( SCIPcreate(&subscip) );
 
   /* create and solve the subproblem. catch possible errors */
   retcode = setupAndSolveCumulativeSubscip(subscip, objvals, durations, demands,
         njobs, capacity, hmin, hmax,
         maxnodes, timelimit, memorylimit,
         ests, lsts,
         infeasible, unbounded, solved, error);
 
   /* free the subscip in any case */
   SCIP_CALL( SCIPfree(&subscip) );
 
   SCIP_CALL( retcode );
 
   return SCIP_OKAY;
}
 
#if 0
/** solve single cumulative condition using SCIP and the time indexed formulation */
static
SCIP_DECL_SOLVECUMULATIVE(solveCumulativeViaScipMip)
{
   SCIP* subscip;
   SCIP_VAR*** binvars;
   SCIP_RETCODE retcode;
   char name[SCIP_MAXSTRLEN];
   int minest;
   int maxlct;
   int t;
   int v;
 
   assert(njobs > 0);
 
   (*solved) = FALSE;
   (*infeasible) = FALSE;
   (*unbounded) = FALSE;
   (*error) = FALSE;
 
   SCIPdebugMsg(scip, "solve independent cumulative condition with %d variables\n", njobs);
 
   /* initialize the sub-problem */
   SCIP_CALL( SCIPcreate(&subscip) );
 
   /* copy all plugins */
   SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
 
   /* create the subproblem */
   SCIP_CALL( SCIPcreateProbBasic(subscip, "cumulative") );
 
   SCIP_CALL( SCIPallocBufferArray(subscip, &binvars, njobs) );
 
   minest = INT_MAX;
   maxlct = INT_MIN;
 
   /* create for each job and time step a binary variable which is one if this jobs starts at this time point and a set
    * partitioning constrain which forces that job starts
    */
   for( v = 0; v < njobs; ++v )
   {
      SCIP_CONS* cons;
      SCIP_Real objval;
      int timeinterval;
      int est;
      int lst;
 
      if( objvals == NULL )
         objval = 0.0;
      else
         objval = objvals[v];
 
      est = ests[v];
      lst = lsts[v];
 
      /* compute number of possible start points */
      timeinterval = lst - est + 1;
      assert(timeinterval > 0);
 
      /* compute the smallest earliest start time and largest latest completion time */
      minest = MIN(minest, est);
      maxlct = MAX(maxlct, lst + durations[v]);
 
      /* construct constraint name */
      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d", v);
 
      SCIP_CALL( SCIPcreateConsBasicSetpart(subscip, &cons, name, 0, NULL) );
 
      SCIP_CALL( SCIPallocBufferArray(subscip, &binvars[v], timeinterval) );
 
      for( t = 0; t < timeinterval; ++t )
      {
         SCIP_VAR* binvar;
 
         /* construct varibale name */
         (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_time_%d", v, t + est);
 
         SCIP_CALL( SCIPcreateVarBasic(subscip, &binvar, name, 0.0, 1.0, objval, SCIP_VARTYPE_BINARY) );
         SCIP_CALL( SCIPaddVar(subscip, binvar) );
 
         /* add binary varibale to the set partitioning constraint which ensures that the job is started */
         SCIP_CALL( SCIPaddCoefSetppc(subscip, cons, binvar) );
 
         binvars[v][t] = binvar;
      }
 
      /* add and release the set partitioning constraint */
      SCIP_CALL( SCIPaddCons(subscip, cons) );
      SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
   }
 
   /* adjusted the smallest earliest start time and the largest latest completion time with the effective horizon */
   hmin = MAX(hmin, minest);
   hmax = MIN(hmax, maxlct);
   assert(hmin > INT_MIN);
   assert(hmax < INT_MAX);
   assert(hmin < hmax);
 
   /* create for each time a knapsack constraint which ensures that the resource capacity is not exceeded */
   for( t = hmin; t < hmax; ++t )
   {
      SCIP_CONS* cons;
 
      /* construct constraint name */
      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "time_%d", t);
 
      /* create an empty knapsack constraint */
      SCIP_CALL( SCIPcreateConsBasicKnapsack(subscip, &cons, name, 0, NULL, NULL, (SCIP_Longint)capacity) );
 
      /* add all jobs which potentially can be processed at that time point */
      for( v = 0; v < njobs; ++v )
      {
         int duration;
         int demand;
         int start;
         int end;
         int est;
         int lst;
         int k;
 
         est = ests[v];
         lst = lsts[v] ;
 
         duration = durations[v];
         assert(duration > 0);
 
         /* check if the varibale is processed potentially at time point t */
         if( t < est || t >= lst + duration )
            continue;
 
         demand = demands[v];
         assert(demand >= 0);
 
         start = MAX(t - duration + 1, est);
         end = MIN(t, lst);
 
         assert(start <= end);
 
         for( k = start; k <= end; ++k )
         {
            assert(binvars[v][k] != NULL);
            SCIP_CALL( SCIPaddCoefKnapsack(subscip, cons, binvars[v][k], (SCIP_Longint) demand) );
         }
      }
 
      /* add and release the knapsack constraint */
      SCIP_CALL( SCIPaddCons(subscip, cons) );
      SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
   }
 
   /* do not abort subproblem on CTRL-C */
   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
 
   /* disable output to console */
   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
 
   /* set limits for the subproblem */
   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", maxnodes) );
   SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
   SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
 
   /* solve single cumulative constraint by branch and bound */
   retcode = SCIPsolve(subscip);
 
   if( retcode != SCIP_OKAY )
      (*error) = TRUE;
   else
   {
      SCIPdebugMsg(scip, "solved single cumulative condition with status %d\n", SCIPgetStatus(subscip));
 
      /* evaluated solution status */
      switch( SCIPgetStatus(subscip) )
      {
      case SCIP_STATUS_INFORUNBD:
      case SCIP_STATUS_INFEASIBLE:
         (*infeasible) = TRUE;
         (*solved) = TRUE;
         break;
      case SCIP_STATUS_UNBOUNDED:
         (*unbounded) = TRUE;
         (*solved) = TRUE;
         break;
      case SCIP_STATUS_OPTIMAL:
      {
         SCIP_SOL* sol;
 
         sol = SCIPgetBestSol(subscip);
         assert(sol != NULL);
 
         for( v = 0; v < njobs; ++v )
         {
            int timeinterval;
            int est;
            int lst;
 
            est = ests[v];
            lst = lsts[v];
 
            /* compute number of possible start points */
            timeinterval = lst - est + 1;
 
            /* check which binary varibale is set to one */
            for( t = 0; t < timeinterval; ++t )
            {
               if( SCIPgetSolVal(subscip, sol, binvars[v][t]) > 0.5 )
               {
                  ests[v] = est + t;
                  lsts[v] = est + t;
                  break;
               }
            }
         }
 
         (*solved) = TRUE;
         break;
      }
      case SCIP_STATUS_NODELIMIT:
      case SCIP_STATUS_TOTALNODELIMIT:
      case SCIP_STATUS_TIMELIMIT:
      case SCIP_STATUS_MEMLIMIT:
      case SCIP_STATUS_USERINTERRUPT:
         /* transfer the global bound changes */
         for( v = 0; v < njobs; ++v )
         {
            int timeinterval;
            int est;
            int lst;
 
            est = ests[v];
            lst = lsts[v];
 
            /* compute number of possible start points */
            timeinterval = lst - est + 1;
 
            /* check which binary varibale is the first binary varibale which is not globally fixed to zero */
            for( t = 0; t < timeinterval; ++t )
            {
               if( SCIPvarGetUbGlobal(binvars[v][t]) > 0.5 )
               {
                  ests[v] = est + t;
                  break;
               }
            }
 
            /* check which binary varibale is the last binary varibale which is not globally fixed to zero */
            for( t = timeinterval - 1; t >= 0; --t )
            {
               if( SCIPvarGetUbGlobal(binvars[v][t]) > 0.5 )
               {
                  lsts[v] = est + t;
                  break;
               }
            }
         }
         (*solved) = FALSE;
         break;
 
      case SCIP_STATUS_UNKNOWN:
      case SCIP_STATUS_STALLNODELIMIT:
      case SCIP_STATUS_GAPLIMIT:
      case SCIP_STATUS_SOLLIMIT:
      case SCIP_STATUS_BESTSOLLIMIT:
         SCIPerrorMessage("invalid status code <%d>\n", SCIPgetStatus(subscip));
         return SCIP_INVALIDDATA;
      }
   }
 
   /* release all variables */
   for( v = 0; v < njobs; ++v )
   {
      int timeinterval;
      int est;
      int lst;
 
      est = ests[v];
      lst = lsts[v];
 
      /* compute number of possible start points */
      timeinterval = lst - est + 1;
 
      for( t = 0; t < timeinterval; ++t )
      {
         SCIP_CALL( SCIPreleaseVar(subscip, &binvars[v][t]) );
      }
      SCIPfreeBufferArray(subscip, &binvars[v]);
   }
 
   SCIPfreeBufferArray(subscip, &binvars);
 
   SCIP_CALL( SCIPfree(&subscip) );
 
   return SCIP_OKAY;
}
#endif
 
/**@} */
 
/**@name Constraint handler data
 *
 * Method used to create and free the constraint handler data when including and removing the cumulative constraint
 * handler.
 *
 * @{
 */
 
/** creates constaint handler data for cumulative constraint handler */
static
SCIP_RETCODE conshdlrdataCreate(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA**   conshdlrdata,       /**< pointer to store the constraint handler data */
   SCIP_EVENTHDLR*       eventhdlr           /**< event handler */
   )
{
   /* create precedence constraint handler data */
   assert(scip != NULL);
   assert(conshdlrdata != NULL);
   assert(eventhdlr != NULL);
 
   SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
 
   /* set event handler for checking if bounds of start time variables are tighten */
   (*conshdlrdata)->eventhdlr = eventhdlr;
 
   /* set default methed for solving single cumulative conditions using SCIP and a CP model */
   (*conshdlrdata)->solveCumulative = solveCumulativeViaScipCp;
 
#ifdef SCIP_STATISTIC
   (*conshdlrdata)->nlbtimetable = 0;
   (*conshdlrdata)->nubtimetable = 0;
   (*conshdlrdata)->ncutofftimetable = 0;
   (*conshdlrdata)->nlbedgefinder = 0;
   (*conshdlrdata)->nubedgefinder = 0;
   (*conshdlrdata)->ncutoffedgefinder = 0;
   (*conshdlrdata)->ncutoffoverload = 0;
   (*conshdlrdata)->ncutoffoverloadTTEF = 0;
 
   (*conshdlrdata)->nirrelevantjobs = 0;
   (*conshdlrdata)->nalwaysruns = 0;
   (*conshdlrdata)->nremovedlocks = 0;
   (*conshdlrdata)->ndualfixs = 0;
   (*conshdlrdata)->ndecomps = 0;
   (*conshdlrdata)->ndualbranchs = 0;
   (*conshdlrdata)->nallconsdualfixs = 0;
   (*conshdlrdata)->naddedvarbounds = 0;
   (*conshdlrdata)->naddeddisjunctives = 0;
#endif
 
   return SCIP_OKAY;
}
 
/** frees constraint handler data for logic or constraint handler */
static
void conshdlrdataFree(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA**   conshdlrdata        /**< pointer to the constraint handler data */
   )
{
   assert(conshdlrdata != NULL);
   assert(*conshdlrdata != NULL);
 
   SCIPfreeBlockMemory(scip, conshdlrdata);
}
 
/**@} */
 
 
/**@name Constraint data methods
 *
 * @{
 */
 
/** catches bound change events for all variables in transformed cumulative constraint */
static
SCIP_RETCODE consdataCatchEvents(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< cumulative constraint data */
   SCIP_EVENTHDLR*       eventhdlr           /**< event handler to call for the event processing */
   )
{
   int v;
 
   assert(scip != NULL);
   assert(consdata != NULL);
   assert(eventhdlr != NULL);
 
   /* catch event for every single variable */
   for( v = 0; v < consdata->nvars; ++v )
   {
      SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[v],
            SCIP_EVENTTYPE_BOUNDTIGHTENED, eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
   }
 
   return SCIP_OKAY;
}
 
/** drops events for variable at given position */
static
SCIP_RETCODE consdataDropEvents(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< cumulative constraint data */
   SCIP_EVENTHDLR*       eventhdlr,          /**< event handler to call for the event processing */
   int                   pos                 /**< array position of variable to catch bound change events for */
   )
{
   assert(scip != NULL);
   assert(consdata != NULL);
   assert(eventhdlr != NULL);
   assert(0 <= pos && pos < consdata->nvars);
   assert(consdata->vars[pos] != NULL);
 
   SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos],
         SCIP_EVENTTYPE_BOUNDTIGHTENED, eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
 
   return SCIP_OKAY;
}
 
/** drops bound change events for all variables in transformed linear constraint */
static
SCIP_RETCODE consdataDropAllEvents(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< linear constraint data */
   SCIP_EVENTHDLR*       eventhdlr           /**< event handler to call for the event processing */
   )
{
   int v;
 
   assert(scip != NULL);
   assert(consdata != NULL);
 
   /* drop event of every single variable */
   for( v = 0; v < consdata->nvars; ++v )
   {
      SCIP_CALL( consdataDropEvents(scip, consdata, eventhdlr, v) );
   }
 
   return SCIP_OKAY;
}
 
/** initialize variable lock data structure */
static
void initializeLocks(
   SCIP_CONSDATA*        consdata,           /**< constraint data */
   SCIP_Bool             locked              /**< should the variable be locked? */
   )
{
   int nvars;
   int v;
 
   nvars = consdata->nvars;
 
   /* initialize locking arrays */
   for( v = 0; v < nvars; ++v )
   {
      consdata->downlocks[v] = locked;
      consdata->uplocks[v] = locked;
   }
}
 
/** creates constraint data of cumulative constraint */
static
SCIP_RETCODE consdataCreate(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA**       consdata,           /**< pointer to consdata */
   SCIP_VAR**            vars,               /**< array of integer variables */
   SCIP_CONS**           linkingconss,       /**< array of linking constraints for the integer variables, or NULL */
   int*                  durations,          /**< array containing corresponding durations */
   int*                  demands,            /**< array containing corresponding demands */
   int                   nvars,              /**< number of variables */
   int                   capacity,           /**< available cumulative capacity */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   SCIP_Bool             check               /**< is the corresponding constraint a check constraint */
   )
{
   int v;
 
   assert(scip != NULL);
   assert(consdata != NULL);
   assert(vars != NULL || nvars > 0);
   assert(demands != NULL);
   assert(durations != NULL);
   assert(capacity >= 0);
   assert(hmin >= 0);
   assert(hmin < hmax);
 
   /* create constraint data */
   SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
 
   (*consdata)->hmin = hmin;
   (*consdata)->hmax = hmax;
 
   (*consdata)->capacity = capacity;
   (*consdata)->demandrows = NULL;
   (*consdata)->demandrowssize = 0;
   (*consdata)->ndemandrows = 0;
   (*consdata)->scoverrows = NULL;
   (*consdata)->nscoverrows = 0;
   (*consdata)->scoverrowssize = 0;
   (*consdata)->bcoverrows = NULL;
   (*consdata)->nbcoverrows = 0;
   (*consdata)->bcoverrowssize = 0;
   (*consdata)->nvars = nvars;
   (*consdata)->varssize = nvars;
   (*consdata)->signature = 0;
   (*consdata)->validsignature = FALSE;
   (*consdata)->normalized = FALSE;
   (*consdata)->covercuts = FALSE;
   (*consdata)->propagated = FALSE;
   (*consdata)->varbounds = FALSE;
   (*consdata)->triedsolving = FALSE;
 
   if( nvars > 0 )
   {
      assert(vars != NULL); /* for flexelint */
 
      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->demands, demands, nvars) );
      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->durations, durations, nvars) );
      (*consdata)->linkingconss = NULL;
 
      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->downlocks, nvars) );
      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->uplocks, nvars) );
 
      /* initialize variable lock data structure; the locks are only used if the constraint is a check constraint */
      initializeLocks(*consdata, check);
 
      if( linkingconss != NULL )
      {
         SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->linkingconss, linkingconss, nvars) );
      }
 
      /* transform variables, if they are not yet transformed */
      if( SCIPisTransformed(scip) )
      {
         SCIPdebugMsg(scip, "get tranformed variables and constraints\n");
 
         /* get transformed variables and do NOT captures these */
         SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
 
         /* multi-aggregated variables cannot be replaced by active variable; therefore we mark all variables for not
          * been multi-aggregated
          */
         for( v = 0; v < nvars; ++v )
         {
            SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[v]) );
         }
 
         if( linkingconss != NULL )
         {
            /* get transformed constraints and captures these */
            SCIP_CALL( SCIPtransformConss(scip, (*consdata)->nvars, (*consdata)->linkingconss, (*consdata)->linkingconss) );
 
            for( v = 0; v < nvars; ++v )
               assert(SCIPgetConsLinking(scip, (*consdata)->vars[v]) == (*consdata)->linkingconss[v]);
         }
      }
 
#ifndef NDEBUG
      /* only binary and integer variables can be used in cumulative constraints
       * for fractional variable values, the constraint cannot be checked
       */
      for( v = 0; v < (*consdata)->nvars; ++v )
         assert(SCIPvarGetType((*consdata)->vars[v]) <= SCIP_VARTYPE_INTEGER);
#endif
   }
   else
   {
      (*consdata)->vars = NULL;
      (*consdata)->downlocks = NULL;
      (*consdata)->uplocks = NULL;
      (*consdata)->demands = NULL;
      (*consdata)->durations = NULL;
      (*consdata)->linkingconss = NULL;
   }
 
   /* initialize values for running propagation algorithms efficiently */
   (*consdata)->resstrength1 = -1.0;
   (*consdata)->resstrength2 = -1.0;
   (*consdata)->cumfactor1 = -1.0;
   (*consdata)->disjfactor1 = -1.0;
   (*consdata)->disjfactor2 = -1.0;
   (*consdata)->estimatedstrength = -1.0;
 
   SCIPstatistic( (*consdata)->maxpeak = -1 );
 
   return SCIP_OKAY;
}
 
/** releases LP rows of constraint data and frees rows array */
static
SCIP_RETCODE consdataFreeRows(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA**       consdata            /**< constraint data */
   )
{
   int r;
 
   assert(consdata != NULL);
   assert(*consdata != NULL);
 
   for( r = 0; r < (*consdata)->ndemandrows; ++r )
   {
      assert((*consdata)->demandrows[r] != NULL);
      SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->demandrows[r]) );
   }
 
   SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->demandrows, (*consdata)->demandrowssize);
 
   (*consdata)->ndemandrows = 0;
   (*consdata)->demandrowssize = 0;
 
   /* free rows of cover cuts */
   for( r = 0; r < (*consdata)->nscoverrows; ++r )
   {
      assert((*consdata)->scoverrows[r] != NULL);
      SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->scoverrows[r]) );
   }
 
   SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->scoverrows, (*consdata)->scoverrowssize);
 
   (*consdata)->nscoverrows = 0;
   (*consdata)->scoverrowssize = 0;
 
   for( r = 0; r < (*consdata)->nbcoverrows; ++r )
   {
      assert((*consdata)->bcoverrows[r] != NULL);
      SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->bcoverrows[r]) );
   }
 
   SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->bcoverrows, (*consdata)->bcoverrowssize);
 
   (*consdata)->nbcoverrows = 0;
   (*consdata)->bcoverrowssize = 0;
 
   (*consdata)->covercuts = FALSE;
 
   return SCIP_OKAY;
}
 
/** frees a cumulative constraint data */
static
SCIP_RETCODE consdataFree(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA**       consdata            /**< pointer to linear constraint data */
   )
{
   int varssize;
   int nvars;
 
   assert(consdata != NULL);
   assert(*consdata != NULL);
 
   nvars =  (*consdata)->nvars;
   varssize = (*consdata)->varssize;
 
   if( varssize > 0 )
   {
      int v;
 
      /* release and free the rows */
      SCIP_CALL( consdataFreeRows(scip, consdata) );
 
      /* release the linking constraints if they were generated */
      if( (*consdata)->linkingconss != NULL )
      {
         for( v = nvars-1; v >= 0; --v )
         {
            assert((*consdata)->linkingconss[v] != NULL );
            SCIP_CALL( SCIPreleaseCons(scip, &(*consdata)->linkingconss[v]) );
         }
 
         SCIPfreeBlockMemoryArray(scip, &(*consdata)->linkingconss, varssize);
      }
 
      /* free arrays */
      SCIPfreeBlockMemoryArray(scip, &(*consdata)->downlocks, varssize);
      SCIPfreeBlockMemoryArray(scip, &(*consdata)->uplocks, varssize);
      SCIPfreeBlockMemoryArray(scip, &(*consdata)->durations, varssize);
      SCIPfreeBlockMemoryArray(scip, &(*consdata)->demands, varssize);
      SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, varssize);
   }
 
   /* free memory */
   SCIPfreeBlockMemory(scip, consdata);
 
   return SCIP_OKAY;
}
 
/** prints cumulative constraint to file stream */
static
void consdataPrint(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< cumulative constraint data */
   FILE*                 file                /**< output file (or NULL for standard output) */
   )
{
   int v;
 
   assert(consdata != NULL);
 
   /* print coefficients */
   SCIPinfoMessage( scip, file, "cumulative(");
 
   for( v = 0; v < consdata->nvars; ++v )
   {
      assert(consdata->vars[v] != NULL);
      if( v > 0 )
         SCIPinfoMessage(scip, file, ", ");
      SCIPinfoMessage(scip, file, "<%s>[%g,%g](%d)[%d]", SCIPvarGetName(consdata->vars[v]),
         SCIPvarGetLbGlobal(consdata->vars[v]), SCIPvarGetUbGlobal(consdata->vars[v]),
         consdata->durations[v], consdata->demands[v]);
   }
   SCIPinfoMessage(scip, file, ")[%d,%d) <= %d", consdata->hmin, consdata->hmax, consdata->capacity);
}
 
/** deletes coefficient at given position from constraint data */
static
SCIP_RETCODE consdataDeletePos(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< cumulative constraint data */
   SCIP_CONS*            cons,               /**< knapsack constraint */
   int                   pos                 /**< position of coefficient to delete */
   )
{
   SCIP_CONSHDLR* conshdlr;
   SCIP_CONSHDLRDATA* conshdlrdata;
 
   assert(scip != NULL);
   assert(consdata != NULL);
   assert(cons != NULL);
   assert(SCIPconsIsTransformed(cons));
   assert(!SCIPinProbing(scip));
 
   SCIPdebugMsg(scip, "cumulative constraint <%s>: remove variable <%s>\n",
      SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[pos]));
 
   /* remove the rounding locks for the deleted variable */
   SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, consdata->downlocks[pos], consdata->uplocks[pos]) );
 
   consdata->downlocks[pos] = FALSE;
   consdata->uplocks[pos] = FALSE;
 
   if( consdata->linkingconss != NULL )
   {
      SCIP_CALL( SCIPreleaseCons(scip, &consdata->linkingconss[pos]) );
   }
 
   /* get event handler */
   conshdlr = SCIPconsGetHdlr(cons);
   assert(conshdlr != NULL);
   conshdlrdata = SCIPconshdlrGetData(conshdlr);
   assert(conshdlrdata != NULL);
   assert(conshdlrdata->eventhdlr != NULL);
 
   /* drop events */
   SCIP_CALL( consdataDropEvents(scip, consdata, conshdlrdata->eventhdlr, pos) );
 
   SCIPdebugMsg(scip, "remove variable <%s>[%g,%g] from cumulative constraint <%s>\n",
      SCIPvarGetName(consdata->vars[pos]), SCIPvarGetLbGlobal(consdata->vars[pos]), SCIPvarGetUbGlobal(consdata->vars[pos]), SCIPconsGetName(cons));
 
   /* in case the we did not remove the variable in the last slot of the arrays we move the current last to this
    * position
    */
   if( pos != consdata->nvars - 1 )
   {
      consdata->vars[pos] = consdata->vars[consdata->nvars-1];
      consdata->downlocks[pos] = consdata->downlocks[consdata->nvars-1];
      consdata->uplocks[pos] = consdata->uplocks[consdata->nvars-1];
      consdata->demands[pos] = consdata->demands[consdata->nvars-1];
      consdata->durations[pos] = consdata->durations[consdata->nvars-1];
 
      if( consdata->linkingconss != NULL )
      {
         consdata->linkingconss[pos]= consdata->linkingconss[consdata->nvars-1];
      }
   }
 
   consdata->nvars--;
   consdata->validsignature = FALSE;
   consdata->normalized = FALSE;
 
   return SCIP_OKAY;
}
 
/** collect linking constraints for each integer variable */
static
SCIP_RETCODE consdataCollectLinkingCons(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata            /**< pointer to consdata */
   )
{
   int nvars;
   int v;
 
   assert(scip != NULL);
   assert(consdata != NULL);
 
   nvars = consdata->nvars;
   assert(nvars > 0);
   assert(consdata->linkingconss == NULL);
 
   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->linkingconss, consdata->varssize) );
 
   for( v = 0; v < nvars; ++v )
   {
      SCIP_CONS* cons;
      SCIP_VAR* var;
 
      var = consdata->vars[v];
      assert(var != NULL);
 
      SCIPdebugMsg(scip, "linking constraint (%d of %d) for variable <%s>\n", v+1, nvars, SCIPvarGetName(var));
 
      /* create linking constraint if it does not exist yet */
      if( !SCIPexistsConsLinking(scip, var) )
      {
         char name[SCIP_MAXSTRLEN];
 
         (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "link(%s)", SCIPvarGetName(var));
 
         /* creates and captures an linking constraint */
         SCIP_CALL( SCIPcreateConsLinking(scip, &cons, name, var, NULL, 0, 0,
               TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE /*TRUE*/, FALSE) );
         SCIP_CALL( SCIPaddCons(scip, cons) );
         consdata->linkingconss[v] = cons;
      }
      else
      {
         consdata->linkingconss[v] = SCIPgetConsLinking(scip, var);
         SCIP_CALL( SCIPcaptureCons(scip, consdata->linkingconss[v]) );
      }
 
      assert(SCIPexistsConsLinking(scip, var));
      assert(consdata->linkingconss[v] != NULL);
      assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(consdata->linkingconss[v])), "linking") == 0 );
      assert(SCIPgetConsLinking(scip, var) == consdata->linkingconss[v]);
   }
 
   return SCIP_OKAY;
}
 
/**@} */
 
 
/**@name Check methods
 *
 * @{
 */
 
/** check for the given starting time variables with their demands and durations if the cumulative conditions for the
 *  given solution is satisfied
 */
static
SCIP_RETCODE checkCumulativeCondition(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_SOL*             sol,                /**< primal solution, or NULL for current LP/pseudo solution */
   int                   nvars,              /**< number of variables (jobs) */
   SCIP_VAR**            vars,               /**< array of integer variable which corresponds to starting times for a job */
   int*                  durations,          /**< array containing corresponding durations */
   int*                  demands,            /**< array containing corresponding demands */
   int                   capacity,           /**< available cumulative capacity */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   SCIP_Bool*            violated,           /**< pointer to store if the cumulative condition is violated */
   SCIP_CONS*            cons,               /**< constraint which is checked */
   SCIP_Bool             printreason         /**< should the reason for the violation be printed? */
   )
{
   int* startsolvalues;       /* stores when each job is starting */
   int* endsolvalues;         /* stores when each job ends */
   int* startindices;         /* we will sort the startsolvalues, thus we need to know which index of a job it corresponds to */
   int* endindices;           /* we will sort the endsolvalues, thus we need to know which index of a job it corresponds to */
 
   int freecapacity;
   int curtime;            /* point in time which we are just checking */
   int endindex;           /* index of endsolvalues with: endsolvalues[endindex] > curtime */
   int j;
 
   SCIP_Real absviol;
   SCIP_Real relviol;
 
   assert(scip != NULL);
   assert(violated != NULL);
 
   (*violated) = FALSE;
 
   if( nvars == 0 )
      return SCIP_OKAY;
 
   assert(vars != NULL);
   assert(demands != NULL);
   assert(durations != NULL);
 
   /* compute time points where we have to check whether capacity constraint is infeasible or not */
   SCIP_CALL( SCIPallocBufferArray(scip, &startsolvalues, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &endsolvalues, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &startindices, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &endindices, nvars) );
 
   /* assign variables, start and endpoints to arrays */
   for ( j = 0; j < nvars; ++j )
   {
      int solvalue;
 
      /* the constraint of the cumulative constraint handler should be called after the integrality check */
      assert(SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars[j])));
 
      solvalue = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, vars[j]));
 
      /* we need to ensure that we check at least one time point during the effective horizon; therefore we project all
       * jobs which start before hmin to hmin
       */
      startsolvalues[j] = MAX(solvalue, hmin);
      startindices[j] = j;
 
      endsolvalues[j] = MAX(solvalue + durations[j], hmin);
      endindices[j] = j;
   }
 
   /* sort the arrays not-decreasing according to start solution values and end solution values (and sort the
    * corresponding indices in the same way)
    */
   SCIPsortIntInt(startsolvalues, startindices, nvars);
   SCIPsortIntInt(endsolvalues, endindices, nvars);
 
   endindex = 0;
   freecapacity = capacity;
   absviol = 0.0;
   relviol = 0.0;
 
   /* check each start point of a job whether the capacity is kept or not */
   for( j = 0; j < nvars; ++j )
   {
      /* only check intervals [hmin,hmax) */
      curtime = startsolvalues[j];
 
      if( curtime >= hmax )
         break;
 
      /* subtract all capacity needed up to this point */
      freecapacity -= demands[startindices[j]];
      while( j+1 < nvars && startsolvalues[j+1] == curtime )
      {
         j++;
         freecapacity -= demands[startindices[j]];
      }
 
      /* free all capacity usages of jobs that are no longer running */
      while( endindex < nvars && curtime >= endsolvalues[endindex] )
      {
         freecapacity += demands[endindices[endindex]];
         ++endindex;
      }
      assert(freecapacity <= capacity);
 
      /* update absolute and relative violation */
      if( absviol < (SCIP_Real) (-freecapacity) )
      {
         absviol = -freecapacity;
         relviol = SCIPrelDiff((SCIP_Real)(capacity - freecapacity), (SCIP_Real)capacity);
      }
 
      /* check freecapacity to be smaller than zero */
      if( freecapacity < 0 && curtime >= hmin )
      {
         SCIPdebugMsg(scip, "freecapacity = %3d\n", freecapacity);
         (*violated) = TRUE;
 
         if( printreason )
         {
            int i;
 
            /* first state the violated constraints */
            SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
 
            /* second state the reason */
            SCIPinfoMessage(scip, NULL,
               ";\nviolation: at time point %d available capacity = %d, needed capacity = %d\n",
               curtime, capacity, capacity - freecapacity);
 
            for( i = 0; i <= j; ++i )
            {
               if( startsolvalues[i] + durations[startindices[i]] > curtime )
               {
                  SCIPinfoMessage(scip, NULL, "activity %s, start = %i, duration = %d, demand = %d \n",
                     SCIPvarGetName(vars[startindices[i]]), startsolvalues[i], durations[startindices[i]],
                     demands[startindices[i]]);
               }
            }
         }
         break;
      }
   } /*lint --e{850}*/
 
   /* update constraint violation in solution */
   if( sol != NULL )
      SCIPupdateSolConsViolation(scip, sol, absviol, relviol);
 
   /* free all buffer arrays */
   SCIPfreeBufferArray(scip, &endindices);
   SCIPfreeBufferArray(scip, &startindices);
   SCIPfreeBufferArray(scip, &endsolvalues);
   SCIPfreeBufferArray(scip, &startsolvalues);
 
   return SCIP_OKAY;
}
 
/** 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
 */
static
SCIP_RETCODE checkCons(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< constraint to be checked */
   SCIP_SOL*             sol,                /**< primal solution, or NULL for current LP/pseudo solution */
   SCIP_Bool*            violated,           /**< pointer to store if the constraint is violated */
   SCIP_Bool             printreason         /**< should the reason for the violation be printed? */
   )
{
   SCIP_CONSDATA* consdata;
 
   assert(scip != NULL);
   assert(cons != NULL);
   assert(violated != NULL);
 
   SCIPdebugMsg(scip, "check cumulative constraints <%s>\n", SCIPconsGetName(cons));
 
   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
 
   /* check the cumulative condition */
   SCIP_CALL( checkCumulativeCondition(scip, sol, consdata->nvars, consdata->vars,
         consdata->durations, consdata->demands, consdata->capacity, consdata->hmin, consdata->hmax,
         violated, cons, printreason) );
 
   return SCIP_OKAY;
}
 
/**@} */
 
/**@name Conflict analysis
 *
 * @{
 */
 
/** resolves the propagation of the core time algorithm */
static
SCIP_RETCODE resolvePropagationCoretimes(
   SCIP*                 scip,               /**< SCIP data structure */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations */
   int*                  demands,            /**< array of demands */
   int                   capacity,           /**< cumulative capacity */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   SCIP_VAR*             infervar,           /**< inference variable */
   int                   inferdemand,        /**< demand of the inference variable */
   int                   inferpeak,          /**< time point which causes the propagation */
   int                   relaxedpeak,        /**< relaxed time point which would be sufficient to be proved */
   SCIP_BDCHGIDX*        bdchgidx,           /**< the index of the bound change, representing the point of time where the change took place */
   SCIP_Bool             usebdwidening,      /**< should bound widening be used during conflict analysis? */
   int*                  provedpeak,         /**< pointer to store the actually proved peak, or NULL */
   SCIP_Bool*            explanation         /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
   )
{
   SCIP_VAR* var;
   SCIP_Bool* reported;
   int duration;
   int maxlst;
   int minect;
   int ect;
   int lst;
   int j;
 
   assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip));
 
   SCIPdebugMsg(scip, "variable <%s>: (demand %d) resolve propagation of core time algorithm (peak %d)\n",
      SCIPvarGetName(infervar), inferdemand, inferpeak);
   assert(nvars > 0);
 
   /* adjusted capacity */
   capacity -= inferdemand;
   maxlst = INT_MIN;
   minect = INT_MAX;
 
   SCIP_CALL( SCIPallocBufferArray(scip, &reported, nvars) );
   BMSclearMemoryArray(reported, nvars);
 
   /* first we loop over all variables and adjust the capacity with those jobs which provide a global core at the
    * inference peak and those where the current conflict bounds provide a core at the inference peak
    */
   for( j = 0; j < nvars && capacity >= 0; ++j )
   {
      var = vars[j];
      assert(var != NULL);
 
      /* skip inference variable */
      if( var == infervar )
         continue;
 
      duration = durations[j];
      assert(duration > 0);
 
      /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */
      assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)));
      assert(SCIPisFeasIntegral(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE)));
      assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)));
      assert(SCIPisFeasIntegral(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE)));
 
      SCIPdebugMsg(scip, "variable <%s>: glb=[%g,%g] conflict=[%g,%g] (duration %d, demand %d)\n",
         SCIPvarGetName(var),  SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var),
         SCIPgetConflictVarLb(scip, var), SCIPgetConflictVarUb(scip, var), duration, demands[j]);
 
      ect = SCIPconvertRealToInt(scip, SCIPvarGetLbGlobal(var)) + duration;
      lst = SCIPconvertRealToInt(scip, SCIPvarGetUbGlobal(var));
 
      /* check if the inference peak is part of the global bound core; if so we decreasing the capacity by the demand of
       * that job without adding it the explanation
       */
      if( inferpeak < ect && lst <= inferpeak )
      {
         capacity -= demands[j];
         reported[j] = TRUE;
 
         maxlst = MAX(maxlst, lst);
         minect = MIN(minect, ect);
         assert(maxlst < minect);
 
         if( explanation != NULL )
            explanation[j] = TRUE;
 
         continue;
      }
 
      /* collect the conflict bound core (the conflict bounds are those bounds which are already part of the conflict)
       * hence these bound are already reported by other resolve propation steps. In case a bound (lower or upper) is
       * not part of the conflict yet we get the global bounds back.
       */
      ect = SCIPconvertRealToInt(scip, SCIPgetConflictVarLb(scip, var)) + duration;
      lst = SCIPconvertRealToInt(scip, SCIPgetConflictVarUb(scip, var));
 
      /* check if the inference peak is part of the conflict bound core; if so we decreasing the capacity by the demand
       * of that job without and collect the job as part of the explanation
       *
       * @note we do not need to reported that job to SCIP since the required bounds are already reported
       */
      if( inferpeak < ect && lst <= inferpeak )
      {
         capacity -= demands[j];
         reported[j] = TRUE;
 
         maxlst = MAX(maxlst, lst);
         minect = MIN(minect, ect);
         assert(maxlst < minect);
 
         if( explanation != NULL )
            explanation[j] = TRUE;
      }
   }
 
   if( capacity >= 0 )
   {
      int* cands;
      int* canddemands;
      int ncands;
      int c;
 
      SCIP_CALL( SCIPallocBufferArray(scip, &cands, nvars) );
      SCIP_CALL( SCIPallocBufferArray(scip, &canddemands, nvars) );
      ncands = 0;
 
      /* collect all cores of the variables which lay in the considered time window except the inference variable */
      for( j = 0; j < nvars; ++j )
      {
         var = vars[j];
         assert(var != NULL);
 
         /* skip inference variable */
         if( var == infervar || reported[j] )
            continue;
 
         duration = durations[j];
         assert(duration > 0);
 
         /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */
         assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)));
         assert(SCIPisFeasIntegral(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE)));
         assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)));
         assert(SCIPisFeasIntegral(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE)));
 
         /* collect local core information */
         ect = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) + duration;
         lst = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
 
         SCIPdebugMsg(scip, "variable <%s>: loc=[%g,%g] glb=[%g,%g] (duration %d, demand %d)\n",
            SCIPvarGetName(var), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE),
            SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), duration, demands[j]);
 
         /* check if the inference peak is part of the core */
         if( inferpeak < ect && lst <= inferpeak )
         {
            cands[ncands] = j;
            canddemands[ncands] = demands[j];
            ncands++;
 
            capacity -= demands[j];
         }
      }
 
      /* sort candidates indices w.r.t. their demands */
      SCIPsortDownIntInt(canddemands, cands, ncands);
 
      assert(capacity < 0);
      assert(ncands > 0);
 
      /* greedily remove candidates form the list such that the needed capacity is still exceeded */
      while( capacity + canddemands[ncands-1] < 0 )
      {
         ncands--;
         capacity += canddemands[ncands];
         assert(ncands > 0);
      }
 
      /* compute the size (number of time steps) of the job cores */
      for( c = 0; c < ncands; ++c )
      {
         var = vars[cands[c]];
         assert(var != NULL);
 
         duration = durations[cands[c]];
 
         ect = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) + duration;
         lst = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
 
         maxlst = MAX(maxlst, lst);
         minect = MIN(minect, ect);
         assert(maxlst < minect);
      }
 
      SCIPdebugMsg(scip, "infer peak %d, relaxed peak %d, lst %d, ect %d\n", inferpeak, relaxedpeak, maxlst, minect);
      assert(inferpeak >= maxlst);
      assert(inferpeak < minect);
 
      /* check if the collect variable are sufficient to prove the relaxed bound (relaxedpeak) */
      if( relaxedpeak < inferpeak )
      {
         inferpeak = MAX(maxlst, relaxedpeak);
      }
      else if( relaxedpeak > inferpeak )
      {
         inferpeak = MIN(minect-1, relaxedpeak);
      }
      assert(inferpeak >= hmin);
      assert(inferpeak < hmax);
      assert(inferpeak >= maxlst);
      assert(inferpeak < minect);
 
      /* post all necessary bound changes */
      for( c = 0; c < ncands; ++c )
      {
         var = vars[cands[c]];
         assert(var != NULL);
 
         if( usebdwidening )
         {
            duration = durations[cands[c]];
 
            SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(inferpeak - duration + 1)) );
            SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, (SCIP_Real)inferpeak) );
         }
         else
         {
            SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
            SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
         }
 
         if( explanation != NULL )
            explanation[cands[c]] = TRUE;
      }
 
      SCIPfreeBufferArray(scip, &canddemands);
      SCIPfreeBufferArray(scip, &cands);
   }
 
   SCIPfreeBufferArray(scip, &reported);
 
   if( provedpeak != NULL )
      *provedpeak = inferpeak;
 
   return SCIP_OKAY;
}
 
#if 0
/** repropagation of edge finding algorithm simplified version from Petr Vilim only a small subset is reported such that
 *  energy in total and for bound change is enough
 */
static
SCIP_RETCODE resolvePropagationEdgeFinding(
   SCIP*                 scip,               /**< SCIP data structure */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   SCIP_VAR*             infervar,           /**< variable whose bound change is to be explained */
   INFERINFO             inferinfo,          /**< inference info containing position of correct bdchgids */
   SCIP_BOUNDTYPE        boundtype,          /**< the type of the changed bound (lower or upper bound) */
   SCIP_BDCHGIDX*        bdchgidx,           /**< the index of the bound change, representing the point of time where the change took place */
   SCIP_Bool             usebdwidening,      /**< should bound widening be used during conflict analysis? */
   SCIP_Bool*            explanation         /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
   )
{
   int est;
   int lct;
   int j;
 
   /* ???????????????????? do bound widening */
 
   assert(scip != NULL);
   assert(nvars > 0);
   assert(inferInfoGetProprule(inferinfo) == PROPRULE_2_EDGEFINDING);
 
   SCIPdebugMsg(scip, "repropagate edge-finding with short reasons for variable <%s>\n", SCIPvarGetName(infervar));
 
   if( boundtype == SCIP_BOUNDTYPE_LOWER )
   {
      SCIP_CALL( SCIPaddConflictLb(scip, infervar, bdchgidx) );
   }
   else
   {
      SCIP_CALL( SCIPaddConflictUb(scip, infervar, bdchgidx) );
   }
 
   est = inferInfoGetData1(inferinfo);
   lct = inferInfoGetData2(inferinfo);
   assert(est < lct);
 
   /* collect the energies of all variables in [est_omega, lct_omega] */
   for( j = 0; j < nvars; ++j )
   {
      SCIP_VAR* var;
      SCIP_Bool left;
      SCIP_Bool right;
      int duration;
      int lb;
      int ub;
 
      var = vars[j];
      assert(var != NULL);
 
      if( var == infervar )
      {
         if( explanation != NULL )
            explanation[j] = TRUE;
 
         continue;
      }
 
      lb = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE));
      ub = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
 
      duration = durations[j];
      assert(duration > 0);
 
      /* in case the earliest start time is equal to hmin we have to also consider the jobs which run in that region
       * since we use adjusted jobs during the propagation
       */
      left = (est == hmin && lb + duration > hmin) || lb >= est;
 
      /* in case the latest completion time is equal to hmax we have to also consider the jobs which run in that region
       * since we use adjusted jobs during the propagation
       */
      right = (lct == hmax && ub < hmax) || ub + duration <= lct;
 
      /* store all jobs running in [est_omega; lct_omega] */
      if( left && right  )
      {
         /* check if bound widening should be used */
         if( usebdwidening )
         {
            SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(lct - duration)) );
            SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, (SCIP_Real)(est)) );
         }
         else
         {
            SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
            SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
         }
 
         if( explanation != NULL )
            explanation[j] = TRUE;
      }
   }
 
   return SCIP_OKAY;
}
#endif
 
/** compute the minimum overlaps w.r.t. the duration of the job and the time window [begin,end) */
static
int computeOverlap(
   int                   begin,              /**< begin of the times interval */
   int                   end,                /**< end of time interval */
   int                   est,                /**< earliest start time */
   int                   lst,                /**< latest start time */
   int                   duration            /**< duration of the job */
   )
{
   int left;
   int right;
   int ect;
   int lct;
 
   ect = est + duration;
   lct = lst + duration;
 
   /* check if job runs completely within [begin,end) */
   if( lct <= end && est >= begin )
      return duration;
 
   assert(lst <= end && ect >= begin);
 
   left = ect - begin;
   assert(left > 0);
 
   right = end - lst;
   assert(right > 0);
 
   return MIN3(left, right, end - begin);
}
 
/** an overload was detected due to the time-time edge-finding propagate; initialized conflict analysis, add an initial
 *  reason
 *
 *  @note the conflict analysis is not performend, only the initialized SCIP_Bool pointer is set to TRUE
 */
static
SCIP_RETCODE analyzeEnergyRequirement(
   SCIP*                 scip,               /**< SCIP data structure */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations */
   int*                  demands,            /**< array of demands */
   int                   capacity,           /**< capacity of the cumulative condition */
   int                   begin,              /**< begin of the time window */
   int                   end,                /**< end of the time window */
   SCIP_VAR*             infervar,           /**< variable which was propagate, or NULL */
   SCIP_BOUNDTYPE        boundtype,          /**< the type of the changed bound (lower or upper bound) */
   SCIP_BDCHGIDX*        bdchgidx,           /**< the index of the bound change, representing the point of time where the change took place */
   SCIP_Real             relaxedbd,          /**< the relaxed bound which is sufficient to be explained */
   SCIP_Bool             usebdwidening,      /**< should bound widening be used during conflict analysis? */
   SCIP_Bool*            explanation         /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
   )
{
   int* locenergies;
   int* overlaps;
   int* idxs;
 
   SCIP_Longint requiredenergy;
   int v;
 
   SCIP_CALL( SCIPallocBufferArray(scip, &locenergies, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &overlaps, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &idxs, nvars) );
 
   /* energy which needs be explained */
   requiredenergy = ((SCIP_Longint) end - begin) * capacity;
 
   SCIPdebugMsg(scip, "analysis energy load in [%d,%d) (capacity %d, energy %" SCIP_LONGINT_FORMAT ")\n", begin, end, capacity, requiredenergy);
 
   /* collect global contribution and adjusted the required energy by the amount of energy the inference variable
    * takes
    */
   for( v = 0; v < nvars; ++v )
   {
      SCIP_VAR* var;
      int glbenergy;
      int duration;
      int demand;
      int est;
      int lst;
 
      var = vars[v];
      assert(var != NULL);
 
      locenergies[v] = 0;
      overlaps[v] = 0;
      idxs[v] = v;
 
      demand = demands[v];
      assert(demand > 0);
 
      duration = durations[v];
      assert(duration > 0);
 
      /* check if the variable equals the inference variable (the one which was propagated) */
      if( infervar == var )
      {
         int overlap;
         int right;
         int left;
 
         assert(relaxedbd != SCIP_UNKNOWN); /*lint !e777*/
 
         SCIPdebugMsg(scip, "inference variable <%s>[%g,%g] %s %g (duration %d, demand %d)\n",
            SCIPvarGetName(var), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE),
            boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", relaxedbd, duration, demand);
 
         /* compute the amount of energy which needs to be available for enforcing the propagation and report the bound
          * which is necessary from the inference variable
          */
         if( boundtype == SCIP_BOUNDTYPE_UPPER )
         {
            int lct;
 
            /* get the latest start time of the infer start time variable before the propagation took place */
            lst = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
 
            /* the latest start time of the inference start time variable before the propagation needs to be smaller as
             * the end of the time interval; meaning the job needs be overlap with the time interval in case the job is
             * scheduled w.r.t. its latest start time
             */
            assert(lst < end);
 
            /* compute the overlap of the job in case it would be scheduled w.r.t. its latest start time and the time
             * interval (before the propagation)
             */
            right = MIN3(end - lst, end - begin, duration);
 
            /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */
            assert(right > 0);
 
            lct = SCIPconvertRealToInt(scip, relaxedbd) + duration;
            assert(begin <= lct);
            assert(bdchgidx == NULL || SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE)) < begin);
 
            /* compute the overlap of the job after the propagation but considering the relaxed bound */
            left = MIN(lct - begin + 1, end - begin);
            assert(left > 0);
 
            /* compute the minimum overlap; */
            overlap = MIN(left, right);
            assert(overlap > 0);
            assert(overlap <= end - begin);
            assert(overlap <= duration);
 
            if( usebdwidening )
            {
               assert(SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)) <= (end - overlap));
               SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, (SCIP_Real)(end - overlap)) );
            }
            else
            {
               SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
            }
         }
         else
         {
            int ect;
 
            assert(boundtype == SCIP_BOUNDTYPE_LOWER);
 
            /* get the earliest completion time of the infer start time variable before the propagation took place */
            ect = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) + duration;
 
            /* the earliest start time of the inference start time variable before the propagation needs to be larger as
             * than the beginning of the time interval; meaning the job needs be overlap with the time interval in case
             * the job is scheduled w.r.t. its earliest start time
             */
            assert(ect > begin);
 
            /* compute the overlap of the job in case it would be scheduled w.r.t. its earliest start time and the time
             * interval (before the propagation)
             */
            left = MIN3(ect - begin, end - begin, duration);
 
            /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */
            assert(left > 0);
 
            est = SCIPconvertRealToInt(scip, relaxedbd);
            assert(end >= est);
            assert(bdchgidx == NULL || end - SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE) < duration);
 
            /* compute the overlap of the job after the propagation but considering the relaxed bound */
            right = MIN(end - est + 1, end - begin);
            assert(right > 0);
 
            /* compute the minimum overlap */
            overlap = MIN(left, right);
            assert(overlap > 0);
            assert(overlap <= end - begin);
            assert(overlap <= duration);
 
            if( usebdwidening )
            {
               assert(SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) >= (begin + overlap - duration));
               SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(begin + overlap - duration)) );
            }
            else
            {
               SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
            }
         }
 
         /* subtract the amount of energy which is available due to the overlap of the inference start time */
         requiredenergy -= (SCIP_Longint) overlap * demand;
 
         if( explanation != NULL )
            explanation[v] = TRUE;
 
         continue;
      }
 
      /* global time points */
      est = SCIPconvertRealToInt(scip, SCIPvarGetLbGlobal(var));
      lst = SCIPconvertRealToInt(scip, SCIPvarGetUbGlobal(var));
 
      glbenergy = 0;
 
      /* check if the has any overlap w.r.t. global bound; meaning some parts of the job will run for sure within the
       * time window
       */
      if( est + duration > begin && lst < end )
      {
         /* evaluated global contribution */
         glbenergy = computeOverlap(begin, end, est, lst, duration) * demand;
 
         /* remove the globally available energy form the required energy */
         requiredenergy -= glbenergy;
 
         if( explanation != NULL )
            explanation[v] = TRUE;
      }
 
      /* local time points */
      est = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE));
      lst = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
 
      /* check if the job has any overlap w.r.t. local bound; meaning some parts of the job will run for sure within the
       * time window
       */
      if( est + duration > begin && lst < end )
      {
         overlaps[v] = computeOverlap(begin, end, est, lst, duration);
 
         /* evaluated additionally local energy contribution */
         locenergies[v] = overlaps[v] * demand - glbenergy;
         assert(locenergies[v] >= 0);
      }
   }
 
   /* sort the variable contributions w.r.t. additional local energy contributions */
   SCIPsortDownIntIntInt(locenergies, overlaps, idxs, nvars);
 
   /* add local energy contributions until an overload is implied */
   for( v = 0; v < nvars && requiredenergy >= 0; ++v )
   {
      SCIP_VAR* var;
      int duration;
      int overlap;
      int relaxlb;
      int relaxub;
      int idx;
 
      idx = idxs[v];
      assert(idx >= 0 && idx < nvars);
 
      var = vars[idx];
      assert(var != NULL);
      assert(var != infervar);
 
      duration = durations[idx];
      assert(duration > 0);
 
      overlap = overlaps[v];
      assert(overlap > 0);
 
      requiredenergy -= locenergies[v];
 
      if( requiredenergy < -1 )
      {
         int demand;
 
         demand = demands[idx];
         assert(demand > 0);
 
         overlap += (int)((requiredenergy + 1) / demand);
 
#ifndef NDEBUG
         requiredenergy += locenergies[v];
         requiredenergy -= (SCIP_Longint) overlap * demand;
         assert(requiredenergy < 0);
#endif
      }
      assert(overlap > 0);
 
      relaxlb = begin - duration + overlap;
      relaxub = end - overlap;
 
      SCIPdebugMsg(scip, "variable <%s> glb=[%g,%g] loc=[%g,%g], conf=[%g,%g], added=[%d,%d] (demand %d, duration %d)\n",
         SCIPvarGetName(var),
         SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var),
         SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
         SCIPgetConflictVarLb(scip, var), SCIPgetConflictVarUb(scip, var),
         relaxlb, relaxub, demands[idx], duration);
 
      SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)relaxlb) );
      SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, (SCIP_Real)relaxub) );
 
      if( explanation != NULL )
         explanation[idx] = TRUE;
   }
 
   assert(requiredenergy < 0);
 
   SCIPfreeBufferArray(scip, &idxs);
   SCIPfreeBufferArray(scip, &overlaps);
   SCIPfreeBufferArray(scip, &locenergies);
 
   return SCIP_OKAY;
}
 
/** resolve propagation w.r.t. the cumulative condition */
static
SCIP_RETCODE respropCumulativeCondition(
   SCIP*                 scip,               /**< SCIP data structure */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations */
   int*                  demands,            /**< array of demands */
   int                   capacity,           /**< cumulative capacity */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   SCIP_VAR*             infervar,           /**< the conflict variable whose bound change has to be resolved */
   INFERINFO             inferinfo,          /**< the user information */
   SCIP_BOUNDTYPE        boundtype,          /**< the type of the changed bound (lower or upper bound) */
   SCIP_BDCHGIDX*        bdchgidx,           /**< the index of the bound change, representing the point of time where the change took place */
   SCIP_Real             relaxedbd,          /**< the relaxed bound which is sufficient to be explained */
   SCIP_Bool             usebdwidening,      /**< should bound widening be used during conflict analysis? */
   SCIP_Bool*            explanation,        /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
   SCIP_RESULT*          result              /**< pointer to store the result of the propagation conflict resolving call */
   )
{
   switch( inferInfoGetProprule(inferinfo) )
   {
   case PROPRULE_1_CORETIMES:
   {
      int inferdemand;
      int inferduration;
      int inferpos;
      int inferpeak;
      int relaxedpeak;
      int provedpeak;
 
      /* get the position of the inferred variable in the vars array */
      inferpos = inferInfoGetData1(inferinfo);
      if( inferpos >= nvars || vars[inferpos] != infervar )
      {
         /* find inference variable in constraint */
         for( inferpos = 0; inferpos < nvars && vars[inferpos] != infervar; ++inferpos )
         {}
      }
      assert(inferpos < nvars);
      assert(vars[inferpos] == infervar);
 
      inferdemand = demands[inferpos];
      inferduration = durations[inferpos];
 
      if( boundtype == SCIP_BOUNDTYPE_UPPER )
      {
         /* we propagated the latest start time (upper bound) step wise with a step length of at most the duration of
          * the inference variable
          */
         assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE) - SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < inferduration + 0.5);
 
         SCIPdebugMsg(scip, "variable <%s>: upper bound changed from %g to %g (relaxed %g)\n",
            SCIPvarGetName(infervar), SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE),
            SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE), relaxedbd);
 
         /* get the inference peak that the time point which lead to the that propagtion */
         inferpeak = inferInfoGetData2(inferinfo);
         /* the bound passed back to be resolved might be tighter as the bound propagted by the core time propagator;
          * this can happen if the variable is not activ and aggregated to an activ variable with a scale != 1.0
          */
         assert(SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE)) + inferduration <= inferpeak);
         relaxedpeak = SCIPconvertRealToInt(scip, relaxedbd) + inferduration;
 
         /* make sure that the relaxed peak is part of the effective horizon */
         relaxedpeak = MIN(relaxedpeak, hmax-1);
 
         /* make sure that relaxed peak is not larger than the infer peak
          *
          * This can happen in case the variable is not an active variable!
          */
         relaxedpeak = MAX(relaxedpeak, inferpeak);
         assert(relaxedpeak >= inferpeak);
         assert(relaxedpeak >= hmin);
      }
      else
      {
         assert(boundtype == SCIP_BOUNDTYPE_LOWER);
 
         SCIPdebugMsg(scip, "variable <%s>: lower bound changed from %g to %g (relaxed %g)\n",
            SCIPvarGetName(infervar), SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, FALSE),
            SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE), relaxedbd);
 
         /* get the time interval where the job could not be scheduled */
         inferpeak = inferInfoGetData2(inferinfo);
         /* the bound passed back to be resolved might be tighter as the bound propagted by the core time propagator;
          * this can happen if the variable is not activ and aggregated to an activ variable with a scale != 1.0
          */
         assert(SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE)) - 1 >= inferpeak);
         relaxedpeak = SCIPconvertRealToInt(scip, relaxedbd) - 1;
 
         /* make sure that the relaxed peak is part of the effective horizon */
         relaxedpeak = MAX(relaxedpeak, hmin);
 
         /* make sure that relaxed peak is not larger than the infer peak
          *
          * This can happen in case the variable is not an active variable!
          */
         relaxedpeak = MIN(relaxedpeak, inferpeak);
         assert(relaxedpeak < hmax);
      }
 
      /* resolves the propagation of the core time algorithm */
      SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
            infervar, inferdemand, inferpeak, relaxedpeak, bdchgidx, usebdwidening, &provedpeak, explanation) );
 
      if( boundtype == SCIP_BOUNDTYPE_UPPER )
      {
         if( usebdwidening )
         {
            SCIP_CALL( SCIPaddConflictRelaxedUb(scip, infervar, NULL,  (SCIP_Real)provedpeak) );
         }
         else
         {
            /* old upper bound of variable itself is part of the explanation */
            SCIP_CALL( SCIPaddConflictUb(scip, infervar, bdchgidx) );
         }
      }
      else
      {
         assert(boundtype == SCIP_BOUNDTYPE_LOWER);
 
         if( usebdwidening )
         {
            SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, bdchgidx, (SCIP_Real)(provedpeak - inferduration + 1)) );
         }
         else
         {
            /* old lower bound of variable itself is part of the explanation */
            SCIP_CALL( SCIPaddConflictLb(scip, infervar, bdchgidx) );
         }
      }
 
      if( explanation != NULL )
         explanation[inferpos] = TRUE;
 
      break;
   }
   case PROPRULE_2_EDGEFINDING:
   case PROPRULE_3_TTEF:
   {
      int begin;
      int end;
 
      begin = inferInfoGetData1(inferinfo);
      end = inferInfoGetData2(inferinfo);
      assert(begin < end);
 
      begin = MAX(begin, hmin);
      end = MIN(end, hmax);
 
      SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
            begin, end, infervar, boundtype, bdchgidx, relaxedbd, usebdwidening, explanation) );
 
      break;
   }
 
   case PROPRULE_0_INVALID:
   default:
      SCIPerrorMessage("invalid inference information %d\n", inferInfoGetProprule(inferinfo));
      SCIPABORT();
      return SCIP_INVALIDDATA; /*lint !e527*/
   }
 
   (*result) = SCIP_SUCCESS;
 
   return SCIP_OKAY;
}
 
/**@} */
 
 
/**@name Enforcement methods
 *
 * @{
 */
 
/** apply all fixings which are given by the alternative bounds */
static
SCIP_RETCODE applyAlternativeBoundsBranching(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_VAR**            vars,               /**< array of active variables */
   int                   nvars,              /**< number of active variables */
   int*                  alternativelbs,     /**< alternative lower bounds */
   int*                  alternativeubs,     /**< alternative lower bounds */
   int*                  downlocks,          /**< number of constraints with down lock participating by the computation */
   int*                  uplocks,            /**< number of constraints with up lock participating by the computation */
   SCIP_Bool*            branched            /**< pointer to store if a branching was applied */
   )
{
   int v;
 
   for( v = 0; v < nvars; ++v )
   {
      SCIP_VAR* var;
      SCIP_Real objval;
 
      var = vars[v];
      assert(var != NULL);
 
      objval = SCIPvarGetObj(var);
 
      if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == downlocks[v] && !SCIPisNegative(scip, objval) )
      {
         int ub;
 
         ub = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
 
         if( alternativelbs[v] <= ub )
         {
            SCIP_CALL( SCIPbranchVarHole(scip, var, SCIPvarGetLbLocal(var), (SCIP_Real)alternativelbs[v], NULL, NULL) );
            (*branched) = TRUE;
 
            SCIPdebugMsg(scip, "variable <%s> branched domain hole (%g,%d)\n", SCIPvarGetName(var),
               SCIPvarGetLbLocal(var), alternativelbs[v]);
 
            return SCIP_OKAY;
         }
      }
 
      if( SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == uplocks[v] && !SCIPisPositive(scip, objval) )
      {
         int lb;
 
         lb = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
 
         if( alternativeubs[v] >= lb )
         {
            SCIP_CALL( SCIPbranchVarHole(scip, var, (SCIP_Real)alternativeubs[v], SCIPvarGetUbLocal(var), NULL, NULL) );
            (*branched) = TRUE;
 
            SCIPdebugMsg(scip, "variable <%s> branched domain hole (%d,%g)\n", SCIPvarGetName(var),
               alternativeubs[v],  SCIPvarGetUbLocal(var));
 
            return SCIP_OKAY;
         }
      }
   }
 
   return SCIP_OKAY;
}
 
/** remove the capacity requirments for all job which start at the curtime */
static
void subtractStartingJobDemands(
   SCIP_CONSDATA*        consdata,           /**< constraint data */
   int                   curtime,            /**< current point in time */
   int*                  starttimes,         /**< array of start times */
   int*                  startindices,       /**< permutation with respect to the start times */
   int*                  freecapacity,       /**< pointer to store the resulting free capacity */
   int*                  idx,                /**< pointer to index in start time array */
   int                   nvars               /**< number of vars in array of starttimes and startindices */
   )
{
#if defined SCIP_DEBUG && !defined NDEBUG
   int oldidx;
 
   assert(idx != NULL);
   oldidx = *idx;
#else
   assert(idx != NULL);
#endif
 
   assert(starttimes != NULL);
   assert(starttimes != NULL);
   assert(freecapacity != NULL);
   assert(starttimes[*idx] == curtime);
   assert(consdata->demands != NULL);
   assert(freecapacity != idx);
 
   /* subtract all capacity needed up to this point */
   (*freecapacity) -= consdata->demands[startindices[*idx]];
 
   while( (*idx)+1 < nvars && starttimes[(*idx)+1] == curtime )
   {
      ++(*idx);
      (*freecapacity) -= consdata->demands[startindices[(*idx)]];
      assert(freecapacity != idx);
   }
#ifdef SCIP_DEBUG
   assert(oldidx <= *idx);
#endif
}
 
/** add the capacity requirments for all job which end at the curtime */
static
void addEndingJobDemands(
   SCIP_CONSDATA*        consdata,           /**< constraint data */
   int                   curtime,            /**< current point in time */
   int*                  endtimes,           /**< array of end times */
   int*                  endindices,         /**< permutation with rspect to the end times */
   int*                  freecapacity,       /**< pointer to store the resulting free capacity */
   int*                  idx,                /**< pointer to index in end time array */
   int                   nvars               /**< number of vars in array of starttimes and startindices */
   )
{
#if defined SCIP_DEBUG && !defined NDEBUG
   int oldidx;
   oldidx = *idx;
#endif
 
   /* free all capacity usages of jobs the are no longer running */
   while( endtimes[*idx] <= curtime && *idx < nvars)
   {
      (*freecapacity) += consdata->demands[endindices[*idx]];
      ++(*idx);
   }
 
#ifdef SCIP_DEBUG
   assert(oldidx <= *idx);
#endif
}
 
/** computes a point in time when the capacity is exceeded returns hmax if this does not happen */
static
SCIP_RETCODE computePeak(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSDATA*        consdata,           /**< constraint handler data */
   SCIP_SOL*             sol,                /**< primal solution, or NULL for current LP/pseudo solution */
   int*                  timepoint           /**< pointer to store the time point of the peak */
   )
{
   int* starttimes;         /* stores when each job is starting */
   int* endtimes;           /* stores when each job ends */
   int* startindices;       /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
   int* endindices;         /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
 
   int nvars;               /* number of activities for this constraint */
   int freecapacity;        /* remaining capacity */
   int curtime;             /* point in time which we are just checking */
   int endindex;            /* index of endsolvalues with: endsolvalues[endindex] > curtime */
 
   int hmin;
   int hmax;
 
   int j;
 
   assert(consdata != NULL);
 
   nvars = consdata->nvars;
   assert(nvars > 0);
 
   *timepoint = consdata->hmax;
 
   assert(consdata->vars != NULL);
 
   SCIP_CALL( SCIPallocBufferArray(scip, &starttimes, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &endtimes, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &startindices, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &endindices, nvars) );
 
   /* create event point arrays */
   createSortedEventpointsSol(scip, sol, consdata->nvars, consdata->vars, consdata->durations,
      starttimes, endtimes, startindices, endindices);
 
   endindex = 0;
   freecapacity = consdata->capacity;
   hmin = consdata->hmin;
   hmax = consdata->hmax;
 
   /* check each startpoint of a job whether the capacity is kept or not */
   for( j = 0; j < nvars; ++j )
   {
      curtime = starttimes[j];
      SCIPdebugMsg(scip, "look at %d-th job with start %d\n", j, curtime);
 
      if( curtime >= hmax )
         break;
 
      /* remove the capacity requirments for all job which start at the curtime */
      subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars);
 
      /* add the capacity requirments for all job which end at the curtime */
      addEndingJobDemands(consdata, curtime, endtimes, endindices, &freecapacity, &endindex, nvars);
 
      assert(freecapacity <= consdata->capacity);
      assert(endindex <= nvars);
 
      /* endindex - points to the next job which will finish */
      /* j - points to the last job that has been released */
 
      /* if free capacity is smaller than zero, then add branching candidates */
      if( freecapacity < 0 && curtime >= hmin )
      {
         *timepoint = curtime;
         break;
      }
   } /*lint --e{850}*/
 
   /* free all buffer arrays */
   SCIPfreeBufferArray(scip, &endindices);
   SCIPfreeBufferArray(scip, &startindices);
   SCIPfreeBufferArray(scip, &endtimes);
   SCIPfreeBufferArray(scip, &starttimes);
 
   return SCIP_OKAY;
}
 
/** checks all cumulative constraints for infeasibility and add branching candidates to storage */
static
SCIP_RETCODE collectBranchingCands(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS**           conss,              /**< constraints to be processed */
   int                   nconss,             /**< number of constraints */
   SCIP_SOL*             sol,                /**< primal solution, or NULL for current LP/pseudo solution */
   int*                  nbranchcands        /**< pointer to store the number of branching variables */
   )
{
   SCIP_HASHTABLE* collectedvars;
   int c;
 
   assert(scip != NULL);
   assert(conss != NULL);
 
   /* create a hash table */
   SCIP_CALL( SCIPhashtableCreate(&collectedvars, SCIPblkmem(scip), SCIPgetNVars(scip),
         SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal, NULL) );
 
   assert(scip != NULL);
   assert(conss != NULL);
 
   for( c = 0; c < nconss; ++c )
   {
      SCIP_CONS* cons;
      SCIP_CONSDATA* consdata;
 
      int curtime;
      int j;
 
      cons = conss[c];
      assert(cons != NULL);
 
      if( !SCIPconsIsActive(cons) )
         continue;
 
      consdata = SCIPconsGetData(cons);
      assert(consdata != NULL);
 
      /* get point in time when capacity is exceeded */
      SCIP_CALL( computePeak(scip, consdata, sol, &curtime) );
 
      if( curtime < consdata->hmin || curtime >= consdata->hmax )
         continue;
 
      /* report all variables that are running at that point in time */
      for( j = 0; j < consdata->nvars; ++j )
      {
         SCIP_VAR* var;
         int lb;
         int ub;
 
         var = consdata->vars[j];
         assert(var != NULL);
 
         /* check if the variable was already added */
         if( SCIPhashtableExists(collectedvars, (void*)var) )
            continue;
 
         lb = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
         ub = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
 
         if( lb <= curtime && ub + consdata->durations[j] > curtime && lb < ub  )
         {
            SCIP_Real solval;
            SCIP_Real score;
 
            solval = SCIPgetSolVal(scip, sol, var);
            score = MIN(solval - lb, ub - solval) / ((SCIP_Real)ub-lb);
 
            SCIPdebugMsg(scip, "add var <%s> to branch cand storage\n", SCIPvarGetName(var));
            SCIP_CALL( SCIPaddExternBranchCand(scip, var, score, lb + (ub - lb) / 2.0 + 0.2) );
            (*nbranchcands)++;
 
            SCIP_CALL( SCIPhashtableInsert(collectedvars, var) );
         }
      }
   }
 
   SCIPhashtableFree(&collectedvars);
 
   SCIPdebugMsg(scip, "found %d branching candidates\n", *nbranchcands);
 
   return SCIP_OKAY;
}
 
/** enforcement of an LP, pseudo, or relaxation solution */
static
SCIP_RETCODE enforceSolution(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS**           conss,              /**< constraints to be processed */
   int                   nconss,             /**< number of constraints */
   SCIP_SOL*             sol,                /**< solution to enforce (NULL for LP or pseudo solution) */
   SCIP_Bool             branch,             /**< should branching candidates be collected */
   SCIP_RESULT*          result              /**< pointer to store the result */
   )
{
   if( branch )
   {
      int nbranchcands;
 
      nbranchcands = 0;
      SCIP_CALL( collectBranchingCands(scip, conss, nconss, sol, &nbranchcands) );
 
      if( nbranchcands > 0 )
         (*result) = SCIP_INFEASIBLE;
   }
   else
   {
      SCIP_Bool violated;
      int c;
 
      violated = FALSE;
 
      /* first check if a constraints is violated */
      for( c = 0; c < nconss && !violated; ++c )
      {
         SCIP_CONS* cons;
 
         cons = conss[c];
         assert(cons != NULL);
 
         SCIP_CALL( checkCons(scip, cons, sol, &violated, FALSE) );
      }
 
      if( violated )
         (*result) = SCIP_INFEASIBLE;
   }
 
   return SCIP_OKAY;
}
 
/**@} */
 
/**@name Propagation
 *
 * @{
 */
 
/** check if cumulative constraint is independently of all other constraints */
static
SCIP_Bool isConsIndependently(
   SCIP_CONS*            cons                /**< cumulative constraint */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR** vars;
   SCIP_Bool* downlocks;
   SCIP_Bool* uplocks;
   int nvars;
   int v;
 
   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
 
   nvars = consdata->nvars;
   vars = consdata->vars;
   downlocks = consdata->downlocks;
   uplocks = consdata->uplocks;
 
   /* check if the cumulative constraint has the only locks on the involved variables */
   for( v = 0; v < nvars; ++v )
   {
      SCIP_VAR* var;
 
      var = vars[v];
      assert(var != NULL);
 
      if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) > (int)downlocks[v]
         || SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) > (int)uplocks[v] )
         return FALSE;
   }
 
   return TRUE;
}
 
/** in case the cumulative constraint is independent of every else, solve the cumulative problem and apply the fixings
 *  (dual reductions)
 */
static
SCIP_RETCODE solveIndependentCons(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONS*            cons,               /**< cumulative constraint */
   SCIP_Longint          maxnodes,           /**< number of branch-and-bound nodes to solve an independent cumulative constraint  (-1: no limit) */
   int*                  nchgbds,            /**< pointer to store the number changed variable bounds */
   int*                  nfixedvars,         /**< pointer to count number of fixings */
   int*                  ndelconss,          /**< pointer to count number of deleted constraints  */
   SCIP_Bool*            cutoff,             /**< pointer to store if the constraint is infeasible */
   SCIP_Bool*            unbounded           /**< pointer to store if the constraint is unbounded */
   )
{
   SCIP_CONSDATA* consdata;
   SCIP_VAR** vars;
   SCIP_Real* objvals;
   SCIP_Real* lbs;
   SCIP_Real* ubs;
   SCIP_Real timelimit;
   SCIP_Real memorylimit;
   SCIP_Bool solved;
   SCIP_Bool error;
 
   int ncheckconss;
   int nvars;
   int v;
 
   assert(scip != NULL);
   assert(!SCIPconsIsModifiable(cons));
   assert(SCIPgetNConss(scip) > 0);
 
   /* if SCIP is in probing mode or repropagation we cannot perform this dual reductions since this dual reduction
    * would/could end in an implication which can lead to cutoff of the/all optimal solution
    */
   if( SCIPinProbing(scip) || SCIPinRepropagation(scip) )
      return SCIP_OKAY;
 
   /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
    * use the locks to decide for a dual reduction using this constraint;
    */
   if( !SCIPconsIsChecked(cons) )
      return SCIP_OKAY;
 
   ncheckconss = SCIPgetNCheckConss(scip);
 
   /* if the cumulative constraint is the only constraint of the original problem or the only check constraint in the
    * presolved problem do nothing execpt to change the parameter settings
    */
   if( ncheckconss == 1 )
   {
      /* shrink the minimal maximum value for the conflict length */
      SCIP_CALL( SCIPsetIntParam(scip, "conflict/minmaxvars", 10) );
 
      /* use only first unique implication point */
      SCIP_CALL( SCIPsetIntParam(scip, "conflict/fuiplevels", 1) );
 
      /* do not use reconversion conflicts */
      SCIP_CALL( SCIPsetIntParam(scip, "conflict/reconvlevels", 0) );
 
      /* after 250 conflict we force a restart since then the variable statistics are reasonable initialized */
      SCIP_CALL( SCIPsetIntParam(scip, "conflict/restartnum", 250) );
 
      /* increase the number of conflicts which induce a restart */
      SCIP_CALL( SCIPsetRealParam(scip, "conflict/restartfac", 2.0) );
 
      /* weight the variable which made into a conflict */
      SCIP_CALL( SCIPsetRealParam(scip, "conflict/conflictweight", 1.0) );
 
      /* do not check pseudo solution (for performance reasons) */
      SCIP_CALL( SCIPsetBoolParam(scip, "constraints/disableenfops", TRUE) );
 
      /* use value based history to detect a reasonable branching point */
      SCIP_CALL( SCIPsetBoolParam(scip, "history/valuebased", TRUE) );
 
      /* turn of LP relaxation */
      SCIP_CALL( SCIPsetIntParam(scip, "lp/solvefreq", -1) );
 
      /* prefer the down branch in case the value based history does not suggest something */
      SCIP_CALL( SCIPsetCharParam(scip, "nodeselection/childsel", 'd') );
 
      /* accept any bound change */
      SCIP_CALL( SCIPsetRealParam(scip, "numerics/boundstreps", 1e-6) );
 
      /* allow for at most 10 restart, after that the value based history should be reliable */
      SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 10) );
 
      /* set priority for depth first search to highest possible value */
      SCIP_CALL( SCIPsetIntParam(scip, "nodeselection/dfs/stdpriority", INT_MAX/4) );
 
      return SCIP_OKAY;
   }
 
   consdata = SCIPconsGetData(cons);
   assert(consdata != NULL);
 
   /* check if already tried to solve that constraint as independent sub problem; we do not want to try it again if we
    * fail on the first place
    */
   if( consdata->triedsolving )
      return SCIP_OKAY;
 
   /* check if constraint is independently */
   if( !isConsIndependently(cons) )
      return SCIP_OKAY;
 
   /* mark the constraint to be tried of solving it as independent sub problem; in case that is successful the
    * constraint is deleted; otherwise, we want to ensure that we do not try that again
    */
   consdata->triedsolving = TRUE;
 
   SCIPdebugMsg(scip, "the cumulative constraint <%s> is independent from rest of the problem (%d variables, %d constraints)\n",
      SCIPconsGetName(cons), SCIPgetNVars(scip), SCIPgetNConss(scip));
   SCIPdebugPrintCons(scip, cons, NULL);
 
   nvars = consdata->nvars;
   vars = consdata->vars;
 
   SCIP_CALL( SCIPallocBufferArray(scip, &lbs, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &ubs, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &objvals, nvars) );
 
   for( v = 0; v < nvars; ++v )
   {
      SCIP_VAR* var;
 
      /* if a variables array is given, use the variable bounds otherwise the default values stored in the ests and lsts
       * array
       */
      var = vars[v];
      assert(var != NULL);
 
      lbs[v] = SCIPvarGetLbLocal(var);
      ubs[v] = SCIPvarGetUbLocal(var);
 
      objvals[v] = SCIPvarGetObj(var);
   }
 
   /* check whether there is enough time and memory left */
   SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
   if( !SCIPisInfinity(scip, timelimit) )
      timelimit -= SCIPgetSolvingTime(scip);
   SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
 
   /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
   if( !SCIPisInfinity(scip, memorylimit) )
   {
      memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
      memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
   }
 
   /* solve the cumulative condition separately */
   SCIP_CALL( SCIPsolveCumulative(scip, nvars, lbs, ubs, objvals, consdata->durations, consdata->demands, consdata->capacity,
         consdata->hmin, consdata->hmax, timelimit, memorylimit, maxnodes, &solved, cutoff, unbounded, &error) );
 
   if( !(*cutoff) && !(*unbounded) && !error )
   {
      SCIP_Bool infeasible;
      SCIP_Bool tightened;
      SCIP_Bool allfixed;
 
      allfixed = TRUE;
 
      for( v = 0; v < nvars; ++v )
      {
         /* check if variable is fixed */
         if( lbs[v] + 0.5 > ubs[v] )
         {
            SCIP_CALL( SCIPfixVar(scip, vars[v], lbs[v], &infeasible, &tightened) );
            assert(!infeasible);
 
            if( tightened )
            {
               (*nfixedvars)++;
               consdata->triedsolving = FALSE;
            }
         }
         else
         {
            SCIP_CALL( SCIPtightenVarLb(scip, vars[v], lbs[v], TRUE, &infeasible, &tightened) );
            assert(!infeasible);
 
            if( tightened )
            {
               (*nchgbds)++;
               consdata->triedsolving = FALSE;
            }
 
            SCIP_CALL( SCIPtightenVarUb(scip, vars[v], ubs[v], TRUE, &infeasible, &tightened) );
            assert(!infeasible);
 
            if( tightened )
            {
               (*nchgbds)++;
               consdata->triedsolving = FALSE;
            }
 
            allfixed = FALSE;
         }
      }
 
      /* if all variables are fixed, remove the cumulative constraint since it is redundant */
      if( allfixed )
      {
         SCIP_CALL( SCIPdelConsLocal(scip, cons) );
         (*ndelconss)++;
      }
   }
 
   SCIPfreeBufferArray(scip, &objvals);
   SCIPfreeBufferArray(scip, &ubs);
   SCIPfreeBufferArray(scip, &lbs);
 
   return SCIP_OKAY;
}
 
/** start conflict analysis to analysis the core insertion which is infeasible */
static
SCIP_RETCODE analyseInfeasibelCoreInsertion(
   SCIP*                 scip,               /**< SCIP data structure */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations */
   int*                  demands,            /**< array of demands */
   int                   capacity,           /**< cumulative capacity */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   SCIP_VAR*             infervar,           /**< start time variable which lead to the infeasibilty */
   int                   inferduration,      /**< duration of the start time variable */
   int                   inferdemand,        /**< demand of the start time variable */
   int                   inferpeak,          /**< profile preak which causes the infeasibilty */
   SCIP_Bool             usebdwidening,      /**< should bound widening be used during conflict analysis? */
   SCIP_Bool*            initialized,        /**< pointer to store if the conflict analysis was initialized */
   SCIP_Bool*            explanation         /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
   )
{
   SCIPdebugMsg(scip, "detected infeasibility due to adding a core to the core resource profile\n");
   SCIPdebugMsg(scip, "variable <%s>[%g,%g] (demand %d, duration %d)\n", SCIPvarGetName(infervar),
      SCIPvarGetLbLocal(infervar), SCIPvarGetUbLocal(infervar), inferdemand, inferduration);
 
   /* initialize conflict analysis if conflict analysis is applicable */
   if( SCIPisConflictAnalysisApplicable(scip) )
   {
      SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
 
      SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
            infervar, inferdemand, inferpeak, inferpeak, NULL, usebdwidening, NULL, explanation) );
 
      SCIPdebugMsg(scip, "add lower and upper bounds of variable <%s>\n", SCIPvarGetName(infervar));
 
      /* add both bound of the inference variable since these biuld the core which we could not inserted */
      if( usebdwidening )
      {
         SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, NULL, (SCIP_Real)(inferpeak - inferduration + 1)) );
         SCIP_CALL( SCIPaddConflictRelaxedUb(scip, infervar, NULL,  (SCIP_Real)inferpeak) );
      }
      else
      {
         SCIP_CALL( SCIPaddConflictLb(scip, infervar, NULL) );
         SCIP_CALL( SCIPaddConflictUb(scip, infervar, NULL) );
      }
 
      *initialized = TRUE;
   }
 
   return SCIP_OKAY;
}
 
/** We are using the core resource profile which contains all core except the one of the start time variable which we
 *  want to propagate, to incease the earliest start time. This we are doing in steps of length at most the duration of
 *  the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict
 *  analysis
 */
static
SCIP_RETCODE coretimesUpdateLb(
   SCIP*                 scip,               /**< SCIP data structure */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations */
   int*                  demands,            /**< array of demands */
   int                   capacity,           /**< cumulative capacity */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   SCIP_CONS*            cons,               /**< constraint which is propagated */
   SCIP_PROFILE*         profile,            /**< resource profile */
   int                   idx,                /**< position of the variable to propagate */
   int*                  nchgbds,            /**< pointer to store the number of bound changes */
   SCIP_Bool             usebdwidening,      /**< should bound widening be used during conflict analysis? */
   SCIP_Bool*            initialized,        /**< was conflict analysis initialized */
   SCIP_Bool*            explanation,        /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
   SCIP_Bool*            infeasible          /**< pointer to store if the constraint is infeasible */
   )
{
   SCIP_VAR* var;
   int ntimepoints;
   int duration;
   int demand;
   int peak;
   int newlb;
   int est;
   int lst;
   int pos;
 
   var = vars[idx];
   assert(var != NULL);
 
   duration = durations[idx];
   assert(duration > 0);
 
   demand = demands[idx];
   assert(demand > 0);
 
   est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
   lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
   ntimepoints = SCIPprofileGetNTimepoints(profile);
 
   /* first we find left position of earliest start time (lower bound) in resource profile; this position gives us the
    * load which we have at the earliest start time (lower bound)
    */
   (void) SCIPprofileFindLeft(profile, est, &pos);
 
   SCIPdebugMsg(scip, "propagate earliest start time (lower bound) (pos %d)\n", pos);
 
   /* we now trying to move the earliest start time in steps of at most "duration" length */
   do
   {
      INFERINFO inferinfo;
      SCIP_Bool tightened;
      int ect;
 
#ifndef NDEBUG
      {
         /* in debug mode we check that we adjust the search position correctly */
         int tmppos;
 
         (void)SCIPprofileFindLeft(profile, est, &tmppos);
         assert(pos == tmppos);
      }
#endif
      ect = est + duration;
      peak = -1;
 
      /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we
       * want a peak which is closest to the earliest completion time
       */
      do
      {
         /* check if the profile load conflicts with the demand of the start time variable */
         if( SCIPprofileGetLoad(profile, pos) + demand > capacity )
            peak = pos;
 
         pos++;
      }
      while( pos < ntimepoints && SCIPprofileGetTime(profile, pos) < ect );
 
      /* if we found no peak that means current the job could be scheduled at its earliest start time without
       * conflicting to the core resource profile
       */
      /* coverity[check_after_sink] */
      if( peak == -1 )
         break;
 
      /* the peak position gives us a time point where the start time variable is in conflict with the resource
       * profile. That means we have to move it to the next time point in the resource profile but at most to the
       * earliest completion time (the remaining move will done in the next loop)
       */
      newlb = SCIPprofileGetTime(profile, peak+1);
      newlb = MIN(newlb, ect);
 
      /* if the earliest start time is greater than the lst we detected an infeasibilty */
      if( newlb > lst )
      {
         SCIPdebugMsg(scip, "variable <%s>: cannot be scheduled\n", SCIPvarGetName(var));
 
         /* use conflict analysis to analysis the core insertion which was infeasible */
         SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
               var, duration, demand, newlb-1, usebdwidening, initialized, explanation) );
 
         if( explanation != NULL )
            explanation[idx] = TRUE;
 
         *infeasible = TRUE;
 
         break;
      }
 
      /* construct the inference information which we are using with the conflict analysis to resolve that particular
       * bound change
       */
      inferinfo = getInferInfo(PROPRULE_1_CORETIMES, idx, newlb-1);
 
      /* perform the bound lower bound change */
      if( inferInfoIsValid(inferinfo) )
      {
         SCIP_CALL( SCIPinferVarLbCons(scip, var, (SCIP_Real)newlb, cons, inferInfoToInt(inferinfo), TRUE, infeasible, &tightened) );
      }
      else
      {
         SCIP_CALL( SCIPtightenVarLb(scip, var, (SCIP_Real)newlb, TRUE, infeasible, &tightened) );
      }
      assert(tightened);
      assert(!(*infeasible));
 
      SCIPdebugMsg(scip, "variable <%s> new lower bound <%d> -> <%d>\n", SCIPvarGetName(var), est, newlb);
      (*nchgbds)++;
 
      /* for the statistic we count the number of times a lower bound was tightened due the the time-table algorithm */
      SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nlbtimetable++ );
 
      /* adjust the earliest start time
       *
       * @note We are taking the lower of the start time variable on purpose instead of newlb. This is due the fact that
       *       the proposed lower bound might be even strength by be the core which can be the case if aggregations are
       *       involved.
       */
      est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
      assert(est >= newlb);
 
      /* adjust the search position for the resource profile for the next step */
      if( est == SCIPprofileGetTime(profile, peak+1) )
         pos = peak + 1;
      else
         pos = peak;
   }
   while( est < lst );
 
   return SCIP_OKAY;
}
 
/** We are using the core resource profile which contains all core except the one of the start time variable which we
 *  want to propagate, to decrease the latest start time. This we are doing in steps of length at most the duration of
 *  the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict
 *  analysis
 */
static
SCIP_RETCODE coretimesUpdateUb(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_VAR*             var,                /**< start time variable to propagate */
   int                   duration,           /**< duration of the job */
   int                   demand,             /**< demand of the job */
   int                   capacity,           /**< cumulative capacity */
   SCIP_CONS*            cons,               /**< constraint which is propagated */
   SCIP_PROFILE*         profile,            /**< resource profile */
   int                   idx,                /**< position of the variable to propagate */
   int*                  nchgbds             /**< pointer to store the number of bound changes */
   )
{
   int ntimepoints;
   int newub;
   int peak;
   int pos;
   int est;
   int lst;
   int lct;
 
   assert(var != NULL);
   assert(duration > 0);
   assert(demand > 0);
 
   est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
   lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
 
   /* in case the start time variable is fixed do nothing */
   if( est == lst )
      return SCIP_OKAY;
 
   ntimepoints = SCIPprofileGetNTimepoints(profile);
 
   lct = lst + duration;
 
   /* first we find left position of latest completion time minus 1 (upper bound + duration) in resource profile; That
    * is the last time point where the job would run if schedule it at its latest start time (upper bound). This
    * position gives us the load which we have at the latest completion time minus one
    */
   (void) SCIPprofileFindLeft(profile, lct - 1, &pos);
 
   SCIPdebugMsg(scip, "propagate upper bound (pos %d)\n", pos);
   SCIPdebug( SCIPprofilePrint(profile, SCIPgetMessagehdlr(scip), NULL) );
 
   if( pos == ntimepoints-1 && SCIPprofileGetTime(profile, pos) == lst )
      return SCIP_OKAY;
 
   /* we now trying to move the latest start time in steps of at most "duration" length */
   do
   {
      INFERINFO inferinfo;
      SCIP_Bool tightened;
      SCIP_Bool infeasible;
 
      peak = -1;
 
#ifndef NDEBUG
      {
         /* in debug mode we check that we adjust the search position correctly */
         int tmppos;
 
         (void)SCIPprofileFindLeft(profile, lct - 1, &tmppos);
         assert(pos == tmppos);
      }
#endif
 
      /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we
       * want a peak which is closest to the latest start time
       */
      do
      {
         if( SCIPprofileGetLoad(profile, pos) + demand > capacity )
            peak = pos;
 
         pos--;
      }
      while( pos >= 0 && SCIPprofileGetTime(profile, pos+1) > lst);
 
      /* if we found no peak that means the current job could be scheduled at its latest start time without conflicting
       * to the core resource profile
       */
      /* coverity[check_after_sink] */
      if( peak == -1 )
         break;
 
      /* the peak position gives us a time point where the start time variable is in conflict with the resource
       * profile. That means the job has be done until that point. Hence that gives us the latest completion
       * time. Note that that we want to move the bound by at most the duration length (the remaining move we are
       * doing in the next loop)
       */
      newub = SCIPprofileGetTime(profile, peak);
      newub = MAX(newub, lst) - duration;
      assert(newub >= est);
 
      /* construct the inference information which we are using with the conflict analysis to resolve that particular
       * bound change
       */
      inferinfo = getInferInfo(PROPRULE_1_CORETIMES, idx, newub+duration);
 
      /* perform the bound upper bound change */
      if( inferInfoIsValid(inferinfo) )
      {
         SCIP_CALL( SCIPinferVarUbCons(scip, var, (SCIP_Real)newub, cons, inferInfoToInt(inferinfo), TRUE, &infeasible, &tightened) );
      }
      else
      {
         SCIP_CALL( SCIPtightenVarUb(scip, var, (SCIP_Real)newub, TRUE, &infeasible, &tightened) );
      }
      assert(tightened);
      assert(!infeasible);
 
      SCIPdebugMsg(scip, "variable <%s>: new upper bound <%d> -> <%d>\n", SCIPvarGetName(var), lst, newub);
      (*nchgbds)++;
 
      /* for the statistic we count the number of times a upper bound was tightened due the the time-table algorithm */
      SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nubtimetable++ );
 
      /* adjust the latest start and completion time
       *
       * @note We are taking the upper of the start time variable on purpose instead of newub. This is due the fact that
       *       the proposed upper bound might be even strength by be the core which can be the case if aggregations are
       *       involved.
       */
      lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
      assert(lst <= newub);
      lct = lst + duration;
 
      /* adjust the search position for the resource profile for the next step */
      if( SCIPprofileGetTime(profile, peak) == lct )
         pos = peak - 1;
      else
         pos = peak;
   }
   while( est < lst );
 
   return SCIP_OKAY;
}
 
/** compute for the different earliest start and latest completion time the core energy of the corresponding time
 *  points
 */
static
void computeCoreEnergyAfter(
   SCIP_PROFILE*         profile,            /**< core profile */
   int                   nvars,              /**< number of start time variables (activities) */
   int*                  ests,               /**< array of sorted earliest start times */
   int*                  lcts,               /**< array of sorted latest completion times */
   int*                  coreEnergyAfterEst, /**< array to store the core energy after the earliest start time of each job */
   int*                  coreEnergyAfterLct  /**< array to store the core energy after the latest completion time of each job */
   )
{
   int ntimepoints;
   int energy;
   int t;
   int v;
 
   ntimepoints = SCIPprofileGetNTimepoints(profile);
   t = ntimepoints - 1;
   energy = 0;
 
   /* compute core energy after the earliest start time of each job */
   for( v = nvars-1; v >= 0; --v )
   {
      while( t > 0 && SCIPprofileGetTime(profile, t-1) >= ests[v] )
      {
         assert(SCIPprofileGetLoad(profile, t-1) >= 0);
         assert(SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1)>= 0);
         energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1));
         t--;
      }
      assert(SCIPprofileGetTime(profile, t) >= ests[v] || t == ntimepoints-1);
 
      /* maybe ests[j] is in-between two timepoints */
      if( SCIPprofileGetTime(profile, t) - ests[v] > 0 )
      {
         assert(t > 0);
         coreEnergyAfterEst[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - ests[v]);
      }
      else
         coreEnergyAfterEst[v] = energy;
   }
 
   t = ntimepoints - 1;
   energy = 0;
 
   /* compute core energy after the latest completion time of each job */
   for( v = nvars-1; v >= 0; --v )
   {
      while( t > 0 && SCIPprofileGetTime(profile, t-1) >= lcts[v] )
      {
         assert(SCIPprofileGetLoad(profile, t-1) >= 0);
         assert(SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1)>= 0);
         energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1));
         t--;
      }
      assert(SCIPprofileGetTime(profile, t) >= lcts[v] || t == ntimepoints-1);
 
      /* maybe lcts[j] is in-between two timepoints */
      if( SCIPprofileGetTime(profile, t) - lcts[v] > 0 )
      {
         assert(t > 0);
         coreEnergyAfterLct[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - lcts[v]);
      }
      else
         coreEnergyAfterLct[v] = energy;
   }
}
 
/** collect earliest start times, latest completion time, and free energy contributions */
static
void collectDataTTEF(
   SCIP*                 scip,               /**< SCIP data structure */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations */
   int*                  demands,            /**< array of demands */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   int*                  permests,           /**< array to store the variable positions */
   int*                  ests,               /**< array to store earliest start times */
   int*                  permlcts,           /**< array to store the variable positions */
   int*                  lcts,               /**< array to store latest completion times */
   int*                  ects,               /**< array to store earliest completion times of the flexible part of the job */
   int*                  lsts,               /**< array to store latest start times of the flexible part of the job */
   int*                  flexenergies        /**< array to store the flexible energies of each job */
   )
{
   int v;
 
   for( v = 0; v < nvars; ++ v)
   {
      int duration;
      int leftadjust;
      int rightadjust;
      int core;
      int est;
      int lct;
      int ect;
      int lst;
 
      duration = durations[v];
      assert(duration > 0);
 
      est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[v]));
      lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[v]));
      ect = est + duration;
      lct = lst + duration;
 
      ests[v] = est;
      lcts[v] = lct;
      permests[v] = v;
      permlcts[v] = v;
 
      /* compute core time window which lies within the effective horizon */
      core = (int) computeCoreWithInterval(hmin, hmax, ect, lst);
 
      /* compute the number of time steps the job could run before the effective horizon */
      leftadjust = MAX(0, hmin - est);
 
      /* compute the number of time steps the job could run after the effective horizon */
      rightadjust = MAX(0, lct - hmax);
 
      /* compute for each job the energy which is flexible; meaning not part of the core */
      flexenergies[v] = duration - leftadjust - rightadjust - core;
      flexenergies[v] = MAX(0, flexenergies[v]);
      flexenergies[v] *= demands[v];
      assert(flexenergies[v] >= 0);
 
      /* the earliest completion time of the flexible energy */
      ects[v] = MIN(ect, lst);
 
      /* the latest start time of the flexible energy */
      lsts[v] = MAX(ect, lst);
   }
}
 
/** try to tighten the lower bound of the given variable */
static
SCIP_RETCODE tightenLbTTEF(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations */
   int*                  demands,            /**< array of demands */
   int                   capacity,           /**< cumulative capacity */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   SCIP_VAR*             var,                /**< variable to be considered for upper bound tightening */
   int                   duration,           /**< duration of the job */
   int                   demand,             /**< demand of the job */
   int                   est,                /**< earliest start time of the job */
   int                   ect,                /**< earliest completion time of the flexible part of the job */
   int                   lct,                /**< latest completion time of the job */
   int                   begin,              /**< begin of the time window under investigation */
   int                   end,                /**< end of the time window under investigation */
   SCIP_Longint          energy,             /**< available energy for the flexible part of the hob within the time window */
   int*                  bestlb,             /**< pointer to strope the best lower bound change */
   int*                  inferinfos,         /**< pointer to store the inference information which is need for the (best) lower bound change */
   SCIP_Bool*            initialized,        /**< was conflict analysis initialized */
   SCIP_Bool*            explanation,        /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
   SCIP_Bool*            cutoff              /**< pointer to store if the constraint is infeasible */
   )
{
   int newlb;
 
   assert(begin >= hmin);
   assert(end <= hmax);
 
   /* check if the time-table edge-finding should infer bounds */
   if( !conshdlrdata->ttefinfer )
      return SCIP_OKAY;
 
   /* if the job can be processed completely before or after the time window, nothing can be tightened */
   if( est >= end || ect <= begin )
      return SCIP_OKAY;
 
   /* if flexible part runs completely within the time window (assuming it is scheduled on its earliest start time), we
    * skip since the overload check will do the job
    */
   if( est >= begin && ect <= end )
      return SCIP_OKAY;
 
   /* check if the available energy in the time window is to small to handle the flexible part if it is schedule on its
    * earliest start time
    */
   if( energy >= demand * ((SCIP_Longint) MAX(begin, est) - MIN(end, ect)) )
      return SCIP_OKAY;
 
   /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is
    * present; therefore, we need to add the core;
    *
    * @note the variable ect define the earliest completion time of the flexible part of the job; hence we need to
    *       compute the earliest completion time of the (whole) job
    */
   energy += computeCoreWithInterval(begin, end, est + duration, lct - duration) * demand;
 
   /* compute a latest start time (upper bound) such that the job consums at most the available energy
    *
    * @note we can round down the compute duration w.r.t. the available energy
    */
   newlb = end - (int) (energy / demand);
 
   /* check if we detected an infeasibility which is the case if the new lower bound is larger than the current upper
    * bound (latest start time); meaning it is not possible to schedule the job
    */
   if( newlb > lct - duration )
   {
      /* initialize conflict analysis if conflict analysis is applicable */
      if( SCIPisConflictAnalysisApplicable(scip) )
      {
         SCIP_Real relaxedbd;
 
         assert(SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) < newlb);
 
         /* it is enough to overshoot the upper bound of the variable by one */
         relaxedbd = SCIPvarGetUbLocal(var) + 1.0;
 
         /* initialize conflict analysis */
         SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
 
         /* added to upper bound (which was overcut be new lower bound) of the variable */
         SCIP_CALL( SCIPaddConflictUb(scip, var, NULL) );
 
         /* analyze the infeasible */
         SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
               begin, end, var, SCIP_BOUNDTYPE_LOWER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) );
 
         (*initialized) = TRUE;
      }
 
      (*cutoff) = TRUE;
   }
   else if( newlb > (*bestlb) )
   {
      INFERINFO inferinfo;
 
      assert(newlb > begin);
 
      inferinfo = getInferInfo(PROPRULE_3_TTEF, begin, end);
 
      /* construct inference information */
      (*inferinfos) = inferInfoToInt(inferinfo);
      (*bestlb) = newlb;
   }
 
   return SCIP_OKAY;
}
 
/** try to tighten the upper bound of the given variable */
static
SCIP_RETCODE tightenUbTTEF(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations */
   int*                  demands,            /**< array of demands */
   int                   capacity,           /**< cumulative capacity */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   SCIP_VAR*             var,                /**< variable to be considered for upper bound tightening */
   int                   duration,           /**< duration of the job */
   int                   demand,             /**< demand of the job */
   int                   est,                /**< earliest start time of the job */
   int                   lst,                /**< latest start time of the flexible part of the job */
   int                   lct,                /**< latest completion time of the job */
   int                   begin,              /**< begin of the time window under investigation */
   int                   end,                /**< end of the time window under investigation */
   SCIP_Longint          energy,             /**< available energy for the flexible part of the hob within the time window */
   int*                  bestub,             /**< pointer to strope the best upper bound change */
   int*                  inferinfos,         /**< pointer to store the inference information which is need for the (best) upper bound change */
   SCIP_Bool*            initialized,        /**< was conflict analysis initialized */
   SCIP_Bool*            explanation,        /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
   SCIP_Bool*            cutoff              /**< pointer to store if the constraint is infeasible */
   )
{
   int newub;
 
   assert(begin >= hmin);
   assert(end <= hmax);
   assert(est < begin);
 
   /* check if the time-table edge-finding should infer bounds */
   if( !conshdlrdata->ttefinfer )
      return SCIP_OKAY;
 
   /* if flexible part of the job can be processed completely before or after the time window, nothing can be tightened */
   if( lst >= end || lct <= begin )
      return SCIP_OKAY;
 
   /* if flexible part runs completely within the time window (assuming it is scheduled on its latest start time), we
    * skip since the overload check will do the job
    */
   if( lst >= begin && lct <= end )
      return SCIP_OKAY;
 
   /* check if the available energy in the time window is to small to handle the flexible part  of the job */
   if( energy >= demand * ((SCIP_Longint) MIN(end, lct) - MAX(begin, lst)) )
      return SCIP_OKAY;
 
   /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is
    * present; therefore, we need to add the core;
    *
    * @note the variable lst define the latest start time of the flexible part of the job; hence we need to compute the
    *       latest start of the (whole) job
    */
   energy += computeCoreWithInterval(begin, end, est + duration, lct - duration) * demand;
   assert(energy >= 0);
 
   /* compute a latest start time (upper bound) such that the job consums at most the available energy
    *
    * @note we can round down the compute duration w.r.t. the available energy
    */
   assert(demand > 0);
   newub = begin - duration + (int) (energy / demand);
 
   /* check if we detected an infeasibility which is the case if the new upper bound is smaller than the current lower
    * bound (earliest start time); meaning it is not possible to schedule the job
    */
   if( newub < est )
   {
      /* initialize conflict analysis if conflict analysis is applicable */
      if( SCIPisConflictAnalysisApplicable(scip) )
      {
         SCIP_Real relaxedbd;
 
         assert(SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var)) > newub);
 
         /* it is enough to undershoot the lower bound of the variable by one */
         relaxedbd = SCIPvarGetLbLocal(var) - 1.0;
 
         /* initialize conflict analysis */
         SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
 
         /* added to lower bound (which was undercut be new upper bound) of the variable */
         SCIP_CALL( SCIPaddConflictLb(scip, var, NULL) );
 
         /* analyze the infeasible */
         SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
               begin, end, var, SCIP_BOUNDTYPE_UPPER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) );
 
         (*initialized) = TRUE;
      }
 
      (*cutoff) = TRUE;
   }
   else if( newub < (*bestub) )
   {
      INFERINFO inferinfo;
 
      assert(newub < begin);
 
      inferinfo = getInferInfo(PROPRULE_3_TTEF, begin, end);
 
      /* construct inference information */
      (*inferinfos) = inferInfoToInt(inferinfo);
      (*bestub) = newub;
   }
 
   return SCIP_OKAY;
}
 
/** propagate the upper bounds and "opportunistically" the lower bounds using the time-table edge-finding algorithm */
static
SCIP_RETCODE propagateUbTTEF(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations */
   int*                  demands,            /**< array of demands */
   int                   capacity,           /**< cumulative capacity */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   int*                  newlbs,             /**< array to buffer new lower bounds */
   int*                  newubs,             /**< array to buffer new upper bounds */
   int*                  lbinferinfos,       /**< array to store the inference information for the lower bound changes */
   int*                  ubinferinfos,       /**< array to store the inference information for the upper bound changes */
   int*                  lsts,               /**< array of latest start time of the flexible part in the same order as the variables */
   int*                  flexenergies,       /**< array of flexible energies in the same order as the variables */
   int*                  perm,               /**< permutation of the variables w.r.t. the non-decreasing order of the earliest start times */
   int*                  ests,               /**< array with earliest strart times sorted in non-decreasing order */
   int*                  lcts,               /**< array with latest completion times sorted in non-decreasing order */
   int*                  coreEnergyAfterEst, /**< core energy after the earliest start times */
   int*                  coreEnergyAfterLct, /**< core energy after the latest completion times */
   SCIP_Bool*            initialized,        /**< was conflict analysis initialized */
   SCIP_Bool*            explanation,        /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
   SCIP_Bool*            cutoff              /**< pointer to store if the constraint is infeasible */
   )
{
   int coreEnergyAfterEnd;
   SCIP_Longint maxavailable;
   SCIP_Longint minavailable;
   SCIP_Longint totalenergy;
   int nests;
   int est;
   int lct;
   int start;
   int end;
   int v;
 
   est = INT_MAX;
   lct = INT_MIN;
 
   /* compute earliest start and latest completion time of all jobs */
   for( v = 0; v < nvars; ++v )
   {
      start = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[v]));
      end = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[v])) + durations[v];
 
      est = MIN(est, start);
      lct = MAX(lct, end);
   }
 
   /* adjust the effective time horizon */
   hmin = MAX(hmin, est);
   hmax = MIN(hmax, lct);
 
   end = hmax + 1;
   coreEnergyAfterEnd = -1;
 
   maxavailable = ((SCIP_Longint) hmax - hmin) * capacity;
   minavailable = maxavailable;
   totalenergy = computeTotalEnergy(durations, demands, nvars);
 
   /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */
   if( ((SCIP_Longint) lcts[0] - ests[nvars-1]) * capacity >= totalenergy )
      return SCIP_OKAY;
 
   nests = nvars;
 
   /* loop over all variable in non-increasing order w.r.t. the latest completion time; thereby, the latest completion
    * times define the end of the time interval under investigation
    */
   for( v = nvars-1; v >= 0  && !(*cutoff); --v )
   {
      int flexenergy;
      int minbegin;
      int lbenergy;
      int lbcand;
      int i;
 
      lct = lcts[v];
 
      /* if the latest completion time is larger then hmax an infeasibility cannot be detected, since after hmax an
       * infinity capacity is available; hence we skip that
       */
      if( lct > hmax )
         continue;
 
      /* if the latest completion time is smaller then hmin we have to stop */
      if( lct <= hmin )
      {
         assert(v == 0 || lcts[v-1] <= lcts[v]);
         break;
      }
 
      /* if the latest completion time equals to previous end time, we can continue since this particular interval
       * induced by end was just analyzed
       */
      if( lct == end )
         continue;
 
      assert(lct < end);
 
      /* In case we only want to detect an overload (meaning no bound propagation) we can skip the interval; this is
       * the case if the free energy (the energy which is not occupied by any core) is smaller than the previous minimum
       * free energy; if so it means that in the next iterate the free-energy cannot be negative
       */
      if( !conshdlrdata->ttefinfer && end <= hmax && minavailable < maxavailable )
      {
         SCIP_Longint freeenergy;
 
         assert(coreEnergyAfterLct[v] >= coreEnergyAfterEnd);
         assert(coreEnergyAfterEnd >= 0);
 
         /* compute the energy which is not consumed by the cores with in the interval [lct, end) */
         freeenergy = capacity * ((SCIP_Longint) end - lct) - coreEnergyAfterLct[v] + coreEnergyAfterEnd;
 
         if( freeenergy <= minavailable )
         {
            SCIPdebugMsg(scip, "skip latest completion time  <%d> (minimum available energy <%" SCIP_LONGINT_FORMAT ">, free energy <%" SCIP_LONGINT_FORMAT ">)\n", lct, minavailable, freeenergy);
            continue;
         }
      }
 
      SCIPdebugMsg(scip, "check intervals ending with <%d>\n", lct);
 
      end = lct;
      coreEnergyAfterEnd = coreEnergyAfterLct[v];
 
      flexenergy = 0;
      minavailable = maxavailable;
      minbegin = hmax;
      lbcand = -1;
      lbenergy = 0;
 
      /* loop over the job in non-increasing order w.r.t. the earliest start time; these earliest start time are
       * defining the beginning of the time interval under investigation; Thereby, the time interval gets wider and
       * wider
       */
      for( i = nests-1; i >= 0; --i )
      {
         SCIP_VAR* var;
         SCIP_Longint freeenergy;
         int duration;
         int demand;
         int begin;
         int idx;
         int lst;
 
         idx = perm[i];
         assert(idx >= 0);
         assert(idx < nvars);
         assert(!(*cutoff));
 
         /* the earliest start time of the job */
         est = ests[i];
 
         /* if the job starts after the current end, we can skip it and do not need to consider it again since the
          * latest completion times (which define end) are scant in non-increasing order
          */
         if( end <= est )
         {
            nests--;
            continue;
         }
 
         /* check if the interval has a size such that the total energy fits, if so we can skip all intervals with the
          * current ending time
          */
         if( ((SCIP_Longint) end - est) * capacity >= totalenergy )
            break;
 
         var = vars[idx];
         assert(var != NULL);
 
         duration = durations[idx];
         assert(duration > 0);
 
         demand = demands[idx];
         assert(demand > 0);
 
         lct = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) + duration;
 
         /* the latest start time of the free part of the job */
         lst = lsts[idx];
 
         /* in case the earliest start time is equal to minbegin, the job lies completely within the time window under
          * investigation; hence the overload check will do the the job
          */
         assert(est <= minbegin);
         if( minavailable < maxavailable && est < minbegin )
         {
            assert(!(*cutoff));
 
            /* try to tighten the upper bound */
            SCIP_CALL( tightenUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
                  var, duration, demand, est, lst, lct, minbegin, end, minavailable, &(newubs[idx]), &(ubinferinfos[idx]),
                  initialized, explanation, cutoff) );
 
            if( *cutoff )
               break;
         }
 
         SCIPdebugMsg(scip, "check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, lst of free part <%d>\n",
            SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, lst);
 
         begin = est;
         assert(SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var)) == est);
 
         /* if the earliest start time is smaller than hmin we can stop here since the next job will not decrease the
          * free energy
          */
         if( begin < hmin )
            break;
 
         /* compute the contribution to the flexible energy */
         if( lct <= end )
         {
            /* if the jobs has to finish before the end, all the energy has to be scheduled */
            assert(lst >= begin);
            assert(flexenergies[idx] >= 0);
            flexenergy += flexenergies[idx];
         }
         else
         {
            /* the job partly overlaps with the end */
            int candenergy;
            int energy;
 
            /* compute the flexible energy which is part of the time interval for sure if the job is scheduled
             * w.r.t. latest start time
             *
             * @note we need to be aware of the effective horizon
             */
            energy = MIN(flexenergies[idx], demands[idx] * MAX(0, (end - lst)));
            assert(end - lst < duration);
            assert(energy >= 0);
 
            /* adjust the flexible energy of the time interval */
            flexenergy += energy;
 
            /* compute the flexible energy of the job which is not part of flexible energy of the time interval */
            candenergy = MIN(flexenergies[idx], demands[idx] * (end - begin)) - energy;
            assert(candenergy >= 0);
 
            /* check if we found a better candidate */
            if( candenergy > lbenergy )
            {
               lbenergy = candenergy;
               lbcand = idx;
            }
         }
 
         SCIPdebugMsg(scip, "time window [%d,%d) flexible energy <%d>\n", begin, end, flexenergy);
         assert(coreEnergyAfterEst[i] >= coreEnergyAfterEnd);
 
         /* compute the energy which is not used yet */
         freeenergy = capacity * ((SCIP_Longint) end - begin) - flexenergy - coreEnergyAfterEst[i] + coreEnergyAfterEnd;
 
         /* check overload */
         if( freeenergy < 0 )
         {
            SCIPdebugMsg(scip, "analyze overload  within time window [%d,%d) capacity %d\n", begin, end, capacity);
 
            /* initialize conflict analysis if conflict analysis is applicable */
            if( SCIPisConflictAnalysisApplicable(scip) )
            {
               /* analyze infeasibilty */
               SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
 
               SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
                     begin, end, NULL, SCIP_BOUNDTYPE_UPPER, NULL, SCIP_UNKNOWN,
                     conshdlrdata->usebdwidening, explanation) );
 
               (*initialized) = TRUE;
            }
 
            (*cutoff) = TRUE;
 
            /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */
            SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
 
            break;
         }
 
         /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */
         if( lbenergy > 0 && freeenergy < lbenergy )
         {
            SCIP_Longint energy;
            int newlb;
            int ect;
 
            ect = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[lbcand])) + durations[lbcand];
            lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[lbcand]));
 
            /* remove the energy of our job from the ... */
            energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, (SCIP_Longint) end - lsts[lbcand])) * demands[lbcand];
 
            newlb = end - (int)(energy / demands[lbcand]);
 
            if( newlb > lst )
            {
               /* initialize conflict analysis if conflict analysis is applicable */
               if( SCIPisConflictAnalysisApplicable(scip) )
               {
                  SCIP_Real relaxedbd;
 
                  /* analyze infeasibilty */
                  SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
 
                  relaxedbd = lst + 1.0;
 
                  /* added to upper bound (which was overcut be new lower bound) of the variable */
                  SCIP_CALL( SCIPaddConflictUb(scip, vars[lbcand], NULL) );
 
                  SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
                        begin, end, vars[lbcand], SCIP_BOUNDTYPE_LOWER, NULL, relaxedbd,
                        conshdlrdata->usebdwidening, explanation) );
 
                  (*initialized) = TRUE;
               }
 
               (*cutoff) = TRUE;
               break;
            }
            else if( newlb > newlbs[lbcand] )
            {
               INFERINFO inferinfo;
 
               /* construct inference information */
               inferinfo = getInferInfo(PROPRULE_3_TTEF, begin, end);
 
               /* buffer upper bound change */
               lbinferinfos[lbcand] = inferInfoToInt(inferinfo);
               newlbs[lbcand] = newlb;
            }
         }
 
         /* check if the current interval has a smaller free energy */
         if( minavailable > freeenergy )
         {
            minavailable = freeenergy;
            minbegin = begin;
         }
         assert(minavailable >= 0);
      }
   }
 
   return SCIP_OKAY;
}
 
/** propagate the lower bounds and "opportunistically" the upper bounds using the time-table edge-finding algorithm */
static
SCIP_RETCODE propagateLbTTEF(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations */
   int*                  demands,            /**< array of demands */
   int                   capacity,           /**< cumulative capacity */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   int*                  newlbs,             /**< array to buffer new lower bounds */
   int*                  newubs,             /**< array to buffer new upper bounds */
   int*                  lbinferinfos,       /**< array to store the inference information for the lower bound changes */
   int*                  ubinferinfos,       /**< array to store the inference information for the upper bound changes */
   int*                  ects,               /**< array of earliest completion time of the flexible part in the same order as the variables */
   int*                  flexenergies,       /**< array of flexible energies in the same order as the variables */
   int*                  perm,               /**< permutation of the variables w.r.t. the non-decreasing order of the latest completion times */
   int*                  ests,               /**< array with earliest strart times sorted in non-decreasing order */
   int*                  lcts,               /**< array with latest completion times sorted in non-decreasing order */
   int*                  coreEnergyAfterEst, /**< core energy after the earliest start times */
   int*                  coreEnergyAfterLct, /**< core energy after the latest completion times */
   SCIP_Bool*            initialized,        /**< was conflict analysis initialized */
   SCIP_Bool*            explanation,        /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
   SCIP_Bool*            cutoff              /**< pointer to store if the constraint is infeasible */
   )
{
   int coreEnergyAfterStart;
   SCIP_Longint maxavailable;
   SCIP_Longint minavailable;
   SCIP_Longint totalenergy;
   int nlcts;
   int begin;
   int minest;
   int maxlct;
   int start;
   int end;
   int v;
 
   if( *cutoff )
      return SCIP_OKAY;
 
   begin = hmin - 1;
 
   minest = INT_MAX;
   maxlct = INT_MIN;
 
   /* compute earliest start and latest completion time of all jobs */
   for( v = 0; v < nvars; ++v )
   {
      start = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[v]));
      end = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[v])) + durations[v];
 
      minest = MIN(minest, start);
      maxlct = MAX(maxlct, end);
   }
 
   /* adjust the effective time horizon */
   hmin = MAX(hmin, minest);
   hmax = MIN(hmax, maxlct);
 
   maxavailable = ((SCIP_Longint) hmax - hmin) * capacity;
   totalenergy = computeTotalEnergy(durations, demands, nvars);
 
   /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */
   if( ((SCIP_Longint) lcts[0] - ests[nvars-1]) * capacity >= totalenergy )
      return SCIP_OKAY;
 
   nlcts = 0;
 
   /* loop over all variable in non-decreasing order w.r.t. the earliest start times; thereby, the earliest start times
    * define the start of the time interval under investigation
    */
   for( v = 0; v < nvars; ++v )
   {
      int flexenergy;
      int minend;
      int ubenergy;
      int ubcand;
      int est;
      int i;
 
      est = ests[v];
 
      /* if the earliest start time is smaller then hmin an infeasibility cannot be detected, since before hmin an
       * infinity capacity is available; hence we skip that
       */
      if( est < hmin )
         continue;
 
      /* if the earliest start time is larger or equal then hmax we have to stop */
      if( est >= hmax )
         break;
 
      /* if the latest earliest start time equals to previous start time, we can continue since this particular interval
       * induced by start was just analyzed
       */
      if( est == begin )
         continue;
 
      assert(est > begin);
 
      SCIPdebugMsg(scip, "check intervals starting with <%d>\n", est);
 
      begin = est;
      coreEnergyAfterStart = coreEnergyAfterEst[v];
 
      flexenergy = 0;
      minavailable = maxavailable;
      minend = hmin;
      ubcand = -1;
      ubenergy = 0;
 
      /* loop over the job in non-decreasing order w.r.t. the latest completion time; these latest completion times are
       * defining the ending of the time interval under investigation; thereby, the time interval gets wider and wider
       */
      for( i = nlcts; i < nvars; ++i )
      {
         SCIP_VAR* var;
         SCIP_Longint freeenergy;
         int duration;
         int demand;
         int idx;
         int lct;
         int ect;
 
         idx = perm[i];
         assert(idx >= 0);
         assert(idx < nvars);
         assert(!(*cutoff));
 
         /* the earliest start time of the job */
         lct = lcts[i];
 
         /* if the job has a latest completion time before the the current start, we can skip it and do not need to
          * consider it again since the earliest start times (which define the start) are scant in non-decreasing order
          */
         if( lct <= begin )
         {
            nlcts++;
            continue;
         }
 
         /* check if the interval has a size such that the total energy fits, if so we can skip all intervals which
          * start with current beginning time
          */
         if( ((SCIP_Longint) lct - begin) * capacity >= totalenergy )
            break;
 
         var = vars[idx];
         assert(var != NULL);
 
         duration = durations[idx];
         assert(duration > 0);
 
         demand = demands[idx];
         assert(demand > 0);
 
         est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
 
         /* the earliest completion time of the flexible part of the job */
         ect = ects[idx];
 
         /* in case the latest completion time is equal to minend, the job lies completely within the time window under
          * investigation; hence the overload check will do the the job
          */
         assert(lct >= minend);
         if( minavailable < maxavailable && lct > minend )
         {
            assert(!(*cutoff));
 
            /* try to tighten the upper bound */
            SCIP_CALL( tightenLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
                  var, duration, demand, est, ect, lct, begin, minend, minavailable, &(newlbs[idx]), &(lbinferinfos[idx]),
                  initialized, explanation, cutoff) );
 
            if( *cutoff )
               return SCIP_OKAY;
         }
 
         SCIPdebugMsg(scip, "check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, ect of free part <%d>\n",
            SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, ect);
 
         end = lct;
         assert(SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) + duration == lct);
 
         /* if the latest completion time is larger than hmax we can stop here since the next job will not decrease the
          * free energy
          */
         if( end > hmax )
            break;
 
         /* compute the contribution to the flexible energy */
         if( est >= begin )
         {
            /* if the jobs has to finish before the end, all the energy has to be scheduled */
            assert(ect <= end);
            assert(flexenergies[idx] >= 0);
            flexenergy += flexenergies[idx];
         }
         else
         {
            /* the job partly overlaps with the end */
            int candenergy;
            int energy;
 
            /* compute the flexible energy which is part of the time interval for sure if the job is scheduled
             * w.r.t. latest start time
             *
             * @note we need to be aware of the effective horizon
             */
            energy = MIN(flexenergies[idx], demands[idx] * MAX(0, (ect - begin)));
            assert(ect - begin < duration);
            assert(energy >= 0);
 
            /* adjust the flexible energy of the time interval */
            flexenergy += energy;
 
            /* compute the flexible energy of the job which is not part of flexible energy of the time interval */
            candenergy = MIN(flexenergies[idx], demands[idx] * (end - begin)) - energy;
            assert(candenergy >= 0);
 
            /* check if we found a better candidate */
            if( candenergy > ubenergy )
            {
               ubenergy = candenergy;
               ubcand = idx;
            }
         }
 
         SCIPdebugMsg(scip, "time window [%d,%d) flexible energy <%d>\n", begin, end, flexenergy);
         assert(coreEnergyAfterLct[i] <= coreEnergyAfterStart);
 
         /* compute the energy which is not used yet */
         freeenergy = capacity * ((SCIP_Longint) end - begin) - flexenergy - coreEnergyAfterStart + coreEnergyAfterLct[i];
 
         /* check overload */
         if( freeenergy < 0 )
         {
            SCIPdebugMsg(scip, "analyze overload  within time window [%d,%d) capacity %d\n", begin, end, capacity);
 
            /* initialize conflict analysis if conflict analysis is applicable */
            if( SCIPisConflictAnalysisApplicable(scip) )
            {
               /* analyze infeasibilty */
               SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
 
               SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
                     begin, end, NULL, SCIP_BOUNDTYPE_UPPER, NULL, SCIP_UNKNOWN,
                     conshdlrdata->usebdwidening, explanation) );
 
               (*initialized) = TRUE;
            }
 
            (*cutoff) = TRUE;
 
            /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */
            SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
 
            return SCIP_OKAY;
         }
 
         /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */
         if( ubenergy > 0 && freeenergy < ubenergy )
         {
            SCIP_Longint energy;
            int newub;
            int lst;
 
            duration = durations[ubcand];
            assert(duration > 0);
 
            ect = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[ubcand])) + duration;
            lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[ubcand]));
 
            /* remove the energy of our job from the ... */
            energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, (SCIP_Longint) ects[ubcand] - begin)) * demands[ubcand];
 
            newub = begin - duration + (int)(energy / demands[ubcand]);
 
            if( newub < ect - duration )
            {
               /* initialize conflict analysis if conflict analysis is applicable */
               if( SCIPisConflictAnalysisApplicable(scip) )
               {
                  SCIP_Real relaxedbd;
                  /* analyze infeasibilty */
                  SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
 
                  relaxedbd = ect - duration - 1.0;
 
                  /* added to lower bound (which was undercut be new upper bound) of the variable */
                  SCIP_CALL( SCIPaddConflictUb(scip, vars[ubcand], NULL) );
 
                  SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
                        begin, end, vars[ubcand], SCIP_BOUNDTYPE_UPPER, NULL, relaxedbd,
                        conshdlrdata->usebdwidening, explanation) );
 
                  (*initialized) = TRUE;
               }
 
               (*cutoff) = TRUE;
               return SCIP_OKAY;
            }
            else if( newub < newubs[ubcand] )
            {
               INFERINFO inferinfo;
 
               /* construct inference information */
               inferinfo = getInferInfo(PROPRULE_3_TTEF, begin, end);
 
               /* buffer upper bound change */
               ubinferinfos[ubcand] = inferInfoToInt(inferinfo);
               newubs[ubcand] = newub;
            }
         }
 
         /* check if the current interval has a smaller free energy */
         if( minavailable > freeenergy )
         {
            minavailable = freeenergy;
            minend = end;
         }
         assert(minavailable >= 0);
      }
   }
 
   return SCIP_OKAY;
}
 
/** checks whether the instance is infeasible due to a overload within a certain time frame using the idea of time-table
 *  edge-finding
 *
 *  @note The algorithm is based on the following two papers:
 *        - Petr Vilim, "Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources", In: Tobias
 *          Achterberg and J. Christopher Beck (Eds.), Integration of AI and OR Techniques in Constraint Programming for
 *          Combinatorial Optimization Problems (CPAIOR 2011), LNCS 6697, pp 230--245
 *        - Andreas Schutt, Thibaut Feydy, and Peter J. Stuckey, "Explaining Time-Table-Edge-Finding Propagation for the
 *          Cumulative Resource Constraint (submitted to CPAIOR 2013)
 */
static
SCIP_RETCODE propagateTTEF(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   SCIP_PROFILE*         profile,            /**< current core profile */
   int                   nvars,              /**< number of start time variables (activities) */
   SCIP_VAR**            vars,               /**< array of start time variables */
   int*                  durations,          /**< array of durations */
   int*                  demands,            /**< array of demands */
   int                   capacity,           /**< cumulative capacity */
   int                   hmin,               /**< left bound of time axis to be considered (including hmin) */
   int                   hmax,               /**< right bound of time axis to be considered (not including hmax) */
   SCIP_CONS*            cons,               /**< constraint which is propagated (needed to SCIPinferVar**Cons()) */
   int*                  nchgbds,            /**< pointer to store the number of bound changes */
   SCIP_Bool*            initialized,        /**< was conflict analysis initialized */
   SCIP_Bool*            explanation,        /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
   SCIP_Bool*            cutoff              /**< pointer to store if the constraint is infeasible */
   )
{
   int* coreEnergyAfterEst;
   int* coreEnergyAfterLct;
   int* flexenergies;
   int* permests;
   int* permlcts;
   int* lcts;
   int* ests;
   int* ects;
   int* lsts;
 
   int* newlbs;
   int* newubs;
   int* lbinferinfos;
   int* ubinferinfos;
 
   int v;
 
   /* check if a cutoff was already detected */
   if( (*cutoff) )
      return SCIP_OKAY;
 
   /* check if at least the basic overload checking should be perfomed */
   if( !conshdlrdata->ttefcheck )
      return SCIP_OKAY;
 
   SCIPdebugMsg(scip, "run time-table edge-finding overload checking\n");
 
   SCIP_CALL( SCIPallocBufferArray(scip, &coreEnergyAfterEst, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &coreEnergyAfterLct, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &flexenergies, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &permlcts, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &permests, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &lcts, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &ests, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &ects, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &lsts, nvars) );
 
   SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &newubs, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &lbinferinfos, nvars) );
   SCIP_CALL( SCIPallocBufferArray(scip, &ubinferinfos, nvars) );
 
   /* we need to buffer the bound changes since the propagation algorithm cannot handle new bound dynamically */
   for( v = 0; v < nvars; ++v )
   {
      newlbs[v] = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[v]));
      newubs[v] = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[v]));
      lbinferinfos[v] = 0;
      ubinferinfos[v] = 0;
   }
 
   /* collect earliest start times, latest completion time, and free energy contributions */
   collectDataTTEF(scip, nvars, vars, durations, demands, hmin, hmax, permests, ests, permlcts, lcts, ects, lsts, flexenergies);
 
   /* sort the earliest start times and latest completion in non-decreasing order */
   SCIPsortIntInt(ests, permests, nvars);
   SCIPsortIntInt(lcts, permlcts, nvars);
 
   /* compute for the different earliest start and latest completion time the core energy of the corresponding time
    * points
    */
   computeCoreEnergyAfter(profile, nvars, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct);
 
   /* propagate the upper bounds and "opportunistically" the lower bounds */
   SCIP_CALL( propagateUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
         newlbs, newubs, lbinferinfos, ubinferinfos, lsts, flexenergies,
         permests, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );
 
   /* propagate the lower bounds and "opportunistically" the upper bounds */
   SCIP_CALL( propagateLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
         newlbs, newubs, lbinferinfos, ubinferinfos, ects, flexenergies,
         permlcts, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );
 
   /* apply the buffer bound changes */
   for( v = 0; v < nvars && !(*cutoff); ++v )
   {
      SCIP_Bool infeasible;
      SCIP_Bool tightened;
 
      if( inferInfoIsValid(intToInferInfo(lbinferinfos[v])) )
      {
         SCIP_CALL( SCIPinferVarLbCons(scip, vars[v], (SCIP_Real)newlbs[v], cons, lbinferinfos[v],
               TRUE, &infeasible, &tightened) );
      }
      else
      {
         SCIP_CALL( SCIPtightenVarLb(scip, vars[v], (SCIP_Real)newlbs[v], TRUE, &infeasible, &tightened) );
      }
 
      /* since we change first the lower bound of the variable an infeasibilty should not be detected */
      assert(!infeasible);
 
      if( tightened )
      {
         (*nchgbds)++;
 
         /* for the statistic we count the number of times a cutoff was detected due the time-time */
         SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->nlbTTEF++ );
      }
 
      if( inferInfoIsValid(intToInferInfo(ubinferinfos[v])) )
      {
         SCIP_CALL( SCIPinferVarUbCons(scip, vars[v], (SCIP_Real)newubs[v], cons, ubinferinfos[v],
               TRUE, &infeasible, &tightened) );
      }
      else
      {
         SCIP_CALL( SCIPtightenVarUb(scip, vars[v], (SCIP_Real)newubs[v], TRUE, &infeasible, &tightened) );
      }
 
      /* since upper bound was compute w.r.t. the "old" bound the previous lower bound update together with this upper
       * bound update can be infeasible
       */
      if( infeasible )
      {
         /* a small performance improvement is possible here: if the tighten...TEFF and propagate...TEFF methods would
          * return not only the inferinfos, but the actual begin and end values, then the infeasibility here could also
          * be analyzed in the case when begin and end exceed the 15 bit limit
          */
         if( SCIPisConflictAnalysisApplicable(scip) && inferInfoIsValid(intToInferInfo(ubinferinfos[v])) )
         {
            INFERINFO inferinfo;
            SCIP_VAR* var;
            int begin;
            int end;
 
            var = vars[v];
            assert(var != NULL);
 
            /* initialize conflict analysis */
            SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
 
            /* convert int to inference information */
            inferinfo = intToInferInfo(ubinferinfos[v]);
 
            /* collect time window from inference information */
            begin = inferInfoGetData1(inferinfo);
            end = inferInfoGetData2(inferinfo);
            assert(begin < end);
 
            /* added to lower bound (which was undercut be new upper bound) of the variable */