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 2002-2022 Zuse Institute Berlin                                */
/*                                                                           */
/*  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_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 contraint 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]);
         }
      }
   }
   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 */
            SCIP_CALL( SCIPaddConflictLb(scip, var, NULL) );

            /* analysis the upper bound change */
            SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
                  begin, end, var, SCIP_BOUNDTYPE_UPPER, NULL, SCIPvarGetLbLocal(vars[v]) - 1.0,
                  conshdlrdata->usebdwidening, explanation) );

            (*initialized) = TRUE;
         }

         /* for the statistic we count the number of times a cutoff was detected due the time-time */
         SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );

         (*cutoff) = TRUE;
         break;
      }

      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))->nubTTEF++ );
      }
   }

   SCIPfreeBufferArray(scip, &ubinferinfos);
   SCIPfreeBufferArray(scip, &lbinferinfos);
   SCIPfreeBufferArray(scip, &newubs);
   SCIPfreeBufferArray(scip, &newlbs);

   /* free buffer arrays */
   SCIPfreeBufferArray(scip, &lsts);
   SCIPfreeBufferArray(scip, &ects);
   SCIPfreeBufferArray(scip, &ests);
   SCIPfreeBufferArray(scip, &lcts);
   SCIPfreeBufferArray(scip, &permests);
   SCIPfreeBufferArray(scip, &permlcts);
   SCIPfreeBufferArray(scip, &flexenergies);
   SCIPfreeBufferArray(scip, &coreEnergyAfterLct);
   SCIPfreeBufferArray(scip, &coreEnergyAfterEst);

   return SCIP_OKAY;
}

/** a cumulative condition is not satisfied if its capacity is exceeded at a time where jobs cannot be shifted (core)
 *  anymore we build up a cumulative profile of all cores of jobs and try to improve bounds of all jobs; also known as
 *  time table propagator
 */
static
SCIP_RETCODE propagateTimetable(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_CONSHDLRDATA*    conshdlrdata,       /**< constraint handler data */
   SCIP_PROFILE*         profile,            /**< 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 */
   )
{
   SCIP_Bool infeasible;
   int v;

   assert(scip != NULL);
   assert(nvars > 0);
   assert(cons != NULL);
   assert(cutoff !=  NULL);

   /* check if already a cutoff was detected */
   if( (*cutoff) )
      return SCIP_OKAY;

   /* check if the time tabling should infer bounds */
   if( !conshdlrdata->ttinfer )
      return SCIP_OKAY;

   assert(*initialized ==  FALSE);

   SCIPdebugMsg(scip, "propagate cores of cumulative condition of constraint <%s>[%d,%d) <= %d\n",
      SCIPconsGetName(cons), hmin, hmax, capacity);

   infeasible = FALSE;

   /* if core profile is empty; nothing to do */
   if( SCIPprofileGetNTimepoints(profile) <= 1 )
      return SCIP_OKAY;

   /* start checking each job whether the bounds can be improved */
   for( v = 0; v < nvars; ++v )
   {
      SCIP_VAR* var;
      int demand;
      int duration;
      int begin;
      int end;
      int est;
      int lst;

      var = vars[v];
      assert(var != NULL);

      duration = durations[v];
      assert(duration > 0);

      /* collect earliest and latest start time */
      est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
      lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));

      /* check if the start time variables is already fixed; in that case we can ignore the job */
      if( est == lst )
         continue;

      /* check if the job runs completely outside of the effective horizon [hmin, hmax); if so skip it */
      if( lst + duration <= hmin || est >= hmax )
         continue;

      /* compute core interval w.r.t. effective time horizon */
      begin = MAX(hmin, lst);
      end = MIN(hmax, est + duration);

      demand = demands[v];
      assert(demand > 0);

      /* if the job has a core, remove it first */
      if( begin < end  )
      {
         SCIPdebugMsg(scip, "variable <%s>[%g,%g] (duration %d, demand %d): remove core [%d,%d)\n",
            SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, begin, end);

         SCIP_CALL( SCIPprofileDeleteCore(profile, begin, end, demand) );
      }

      /* first try to update the earliest start time */
      SCIP_CALL( coretimesUpdateLb(scip, nvars, vars, durations, demands, capacity, hmin, hmax, cons,
            profile, v, nchgbds, conshdlrdata->usebdwidening, initialized, explanation, cutoff) );

      if( *cutoff )
         break;

      /* second try to update the latest start time */
      SCIP_CALL( coretimesUpdateUb(scip, var, duration, demand, capacity, cons,
            profile, v, nchgbds) );

      if( *cutoff )
         break;

      /* collect the potentially updated earliest and latest start time */
      est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
      lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));

      /* compute core interval w.r.t. effective time horizon */
      begin = MAX(hmin, lst);
      end = MIN(hmax, est + duration);

      /* after updating the bound we might have a new core */
      if( begin < end )
      {
         int pos;

         SCIPdebugMsg(scip, "variable <%s>[%d,%d] (duration %d, demand %d): add core [%d,%d)\n",
            SCIPvarGetName(var), est, lst, duration, demand, begin, end);

         SCIP_CALL( SCIPprofileInsertCore(profile, begin, end, demand, &pos, &infeasible) );

         if( infeasible )
         {
            /* 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, SCIPprofileGetTime(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) );

            if( explanation != NULL )
               explanation[v] = TRUE;

            (*cutoff) = TRUE;

            /* for the statistic we count the number of times a cutoff was detected due the time-time */
            SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutofftimetable++ );

            break;
         }
      }
   }

   return SCIP_OKAY;
}


/** node data structure for the binary tree used for edgefinding (with overload checking) */
struct SCIP_NodeData
{
   SCIP_VAR*             var;                /**< start time variable of the job if the node data belongs to a leaf, otherwise NULL */
   SCIP_Real             key;                /**< key which is to insert the corresponding search node */
   int                   est;                /**< earliest start time if the node data belongs to a leaf */
   int                   lct;                /**< latest completion time if the node data belongs to a leaf */
   int                   demand;             /**< demand of the job if the node data belongs to a leaf */
   int                   duration;           /**< duration of the job if the node data belongs to a leaf */
   int                   leftadjust;         /**< left adjustments of the duration w.r.t. hmin */
   int                   rightadjust;        /**< right adjustments of the duration w.r.t. hmax */
   SCIP_Longint          enveloptheta;       /**< the maximal energy of a subset of jobs part of the theta set */
   int                   energytheta;        /**< energy of the subset of the jobs which are part of theta set */
   int                   energylambda;
   SCIP_Longint          enveloplambda;
   int                   idx;                /**< index of the start time variable in the (global) variable array */
   SCIP_Bool             intheta;            /**< belongs the node to the theta set (otherwise to the lambda set) */
};
typedef struct SCIP_NodeData SCIP_NODEDATA;


/** update node data structure starting from the given node along the path to the root node */
static
void updateEnvelope(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_BTNODE*          node                /**< search node which inserted */
   )
{
   SCIP_BTNODE* left;
   SCIP_BTNODE* right;
   SCIP_NODEDATA* nodedata;
   SCIP_NODEDATA* leftdata;
   SCIP_NODEDATA* rightdata;

   SCIPdebugMsg(scip, "update envelop starting from node <%p>\n", (void*)node);

   if( SCIPbtnodeIsLeaf(node) )
      node = SCIPbtnodeGetParent(node);

   while( node != NULL )
   {
      /* get node data */
      nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(node);
      assert(nodedata != NULL);

      /* collect node data from left node */
      left = SCIPbtnodeGetLeftchild(node);
      assert(left != NULL);
      leftdata = (SCIP_NODEDATA*)SCIPbtnodeGetData(left);
      assert(leftdata != NULL);

      /* collect node data from right node */
      right = SCIPbtnodeGetRightchild(node);
      assert(right != NULL);
      rightdata = (SCIP_NODEDATA*)SCIPbtnodeGetData(right);
      assert(rightdata != NULL);

      /* update envelop and energy */
      if( leftdata->enveloptheta >= 0 )
      {
         assert(rightdata->energytheta != -1);
         nodedata->enveloptheta = MAX(leftdata->enveloptheta + rightdata->energytheta, rightdata->enveloptheta);
      }
      else
         nodedata->enveloptheta = rightdata->enveloptheta;

      assert(leftdata->energytheta != -1);
      assert(rightdata->energytheta != -1);
      nodedata->energytheta = leftdata->energytheta + rightdata->energytheta;

      if( leftdata->enveloplambda >= 0 )
      {
         assert(rightdata->energytheta != -1);
         nodedata->enveloplambda = MAX(leftdata->enveloplambda + rightdata->energytheta, rightdata->enveloplambda);
      }
      else
         nodedata->enveloplambda = rightdata->enveloplambda;

      if( leftdata->enveloptheta >= 0 && rightdata->energylambda >= 0 )
         nodedata->enveloplambda = MAX(nodedata->enveloplambda, leftdata->enveloptheta + rightdata->energylambda);

      SCIPdebugMsg(scip, "node <%p> lambda envelop %" SCIP_LONGINT_FORMAT "\n", (void*)node, nodedata->enveloplambda);

      if( leftdata->energylambda >= 0 && rightdata->energylambda >= 0 )
      {
         assert(rightdata->energytheta != -1);
         assert(leftdata->energytheta != -1);
         nodedata->energylambda = MAX(leftdata->energylambda + rightdata->energytheta, leftdata->energytheta + rightdata->energylambda);
      }
      else if( rightdata->energylambda >= 0 )
      {
         assert(leftdata->energytheta != -1);
         nodedata->energylambda = leftdata->energytheta + rightdata->energylambda;
      }
      else if( leftdata->energylambda >= 0 )
      {
         assert(rightdata->energytheta != -1);
         nodedata->energylambda = leftdata->energylambda + rightdata->energytheta;
      }
      else
         nodedata->energylambda = -1;

      /* go to parent */
      node = SCIPbtnodeGetParent(node);
   }

   SCIPdebugMsg(scip, "updating done\n");
}

/** updates the key of the first parent on the trace which comes from left */
static
void updateKeyOnTrace(
   SCIP_BTNODE*          node,               /**< node to start the trace */
   SCIP_Real             key                 /**< update search key */
   )
{
   assert(node != NULL);

   while( !SCIPbtnodeIsRoot(node) )
   {
      SCIP_BTNODE* parent;

      parent = SCIPbtnodeGetParent(node);
      assert(parent != NULL);

      if( SCIPbtnodeIsLeftchild(node) )
      {
         SCIP_NODEDATA* nodedata;

         nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(parent);
         assert(nodedata != NULL);

         nodedata->key = key;
         return;
      }

      node = parent;
   }
}


/** deletes the given node and updates all envelops */
static
SCIP_RETCODE deleteLambdaLeaf(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_BT*              tree,               /**< binary tree */
   SCIP_BTNODE*          node                /**< node to be deleted */
   )
{
   SCIP_BTNODE* parent;
   SCIP_BTNODE* grandparent;
   SCIP_BTNODE* sibling;

   assert(scip != NULL);
   assert(tree != NULL);
   assert(node != NULL);

   assert(SCIPbtnodeIsLeaf(node));
   assert(!SCIPbtnodeIsRoot(node));

   SCIPdebugMsg(scip, "delete node <%p>\n", (void*)node);

   parent = SCIPbtnodeGetParent(node);
   assert(parent != NULL);
   if( SCIPbtnodeIsLeftchild(node) )
   {
      sibling = SCIPbtnodeGetRightchild(parent);
      SCIPbtnodeSetRightchild(parent, NULL);
   }
   else
   {
      sibling = SCIPbtnodeGetLeftchild(parent);
      SCIPbtnodeSetLeftchild(parent, NULL);
   }
   assert(sibling != NULL);

   grandparent = SCIPbtnodeGetParent(parent);

   if( grandparent != NULL )
   {
      /* reset parent of sibling */
      SCIPbtnodeSetParent(sibling, grandparent);

      /* reset child of grandparent to sibling */
      if( SCIPbtnodeIsLeftchild(parent) )
      {
         SCIPbtnodeSetLeftchild(grandparent, sibling);
      }
      else
      {
         SCIP_NODEDATA* nodedata;

         assert(SCIPbtnodeIsRightchild(parent));
         SCIPbtnodeSetRightchild(grandparent, sibling);

         nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(sibling);

         updateKeyOnTrace(grandparent, nodedata->key);
      }

      updateEnvelope(scip, grandparent);
   }
   else
   {
      SCIPbtnodeSetParent(sibling, NULL);

      SCIPbtSetRoot(tree, sibling);
   }

   SCIPbtnodeFree(tree, &parent);

   return SCIP_OKAY;
}

/** moves a node form the theta set into the lambda set and updates the envelops */
static
SCIP_RETCODE moveNodeToLambda(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_BT*              tree,               /**< binary tree */
   SCIP_BTNODE*          node                /**< node to move into the lambda set */
   )
{
   SCIP_NODEDATA* nodedata;

   assert(scip != NULL);
   assert(tree != NULL);
   assert(node != NULL);

   nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(node);
   assert(nodedata != NULL);
   assert(nodedata->intheta);

   /* move the contributions form the theta set into the lambda set */
   assert(nodedata->enveloptheta != -1);
   assert(nodedata->energytheta != -1);
   assert(nodedata->enveloplambda == -1);
   assert(nodedata->energylambda == -1);
   nodedata->enveloplambda = nodedata->enveloptheta;
   nodedata->energylambda = nodedata->energytheta;

   nodedata->enveloptheta = -1;
   nodedata->energytheta = 0;
   nodedata->intheta = FALSE;

   /* update the energy and envelop values on trace */
   updateEnvelope(scip, node);

   return SCIP_OKAY;
}

/** inserts a node into the theta set and update the envelops */
static
SCIP_RETCODE insertThetanode(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_BT*              tree,               /**< binary tree */
   SCIP_BTNODE*          node,               /**< node to insert */
   SCIP_NODEDATA*        nodedatas,          /**< array of node data */
   int*                  nodedataidx,        /**< array of indices for node data */
   int*                  nnodedatas          /**< pointer to number of node data */
   )
{
   /* if the tree is empty the node will be the root node */
   if( SCIPbtIsEmpty(tree) )
   {
      SCIPbtSetRoot(tree, node);
   }
   else
   {
      SCIP_NODEDATA* newnodedata;
      SCIP_NODEDATA* leafdata;
      SCIP_NODEDATA* nodedata;
      SCIP_BTNODE* leaf;
      SCIP_BTNODE* newnode;
      SCIP_BTNODE* parent;

      leaf = SCIPbtGetRoot(tree);
      assert(leaf != NULL);

      leafdata = (SCIP_NODEDATA*)SCIPbtnodeGetData(leaf);
      assert(leafdata != NULL);

      nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(node);
      assert(nodedata != NULL);
      assert(nodedata->intheta);

      /* find the position to insert the node */
      while( !SCIPbtnodeIsLeaf(leaf) )
      {
         if( nodedata->key < leafdata->key )
            leaf = SCIPbtnodeGetLeftchild(leaf);
         else
            leaf = SCIPbtnodeGetRightchild(leaf);

         leafdata = (SCIP_NODEDATA*)SCIPbtnodeGetData(leaf);
         assert(leafdata != NULL);
      }

      assert(leaf != NULL);
      assert(leaf != node);

      /* store node data to be able to delete them latter */
      newnodedata = &nodedatas[*nnodedatas];
      nodedataidx[*nnodedatas] = *nnodedatas;
      ++(*nnodedatas);

      /* init node data */
      newnodedata->var = NULL;
      newnodedata->key = SCIP_INVALID;
      newnodedata->est = INT_MIN;
      newnodedata->lct = INT_MAX;
      newnodedata->duration = 0;
      newnodedata->demand = 0;
      newnodedata->enveloptheta = -1;
      newnodedata->energytheta = 0;
      newnodedata->enveloplambda = -1;
      newnodedata->energylambda = -1;
      newnodedata->idx = -1;
      newnodedata->intheta = TRUE;

      /* create a new node */
      SCIP_CALL( SCIPbtnodeCreate(tree, &newnode, newnodedata) );
      assert(newnode != NULL);

      parent = SCIPbtnodeGetParent(leaf);

      if( parent != NULL )
      {
         SCIPbtnodeSetParent(newnode, parent);

         /* check if the node is the left child */
         if( SCIPbtnodeGetLeftchild(parent) == leaf )
         {
            SCIPbtnodeSetLeftchild(parent, newnode);
         }
         else
         {
            SCIPbtnodeSetRightchild(parent, newnode);
         }
      }
      else
         SCIPbtSetRoot(tree, newnode);

      if( nodedata->key < leafdata->key )
      {
         /* node is on the left */
         SCIPbtnodeSetLeftchild(newnode, node);
         SCIPbtnodeSetRightchild(newnode, leaf);
         newnodedata->key = nodedata->key;
      }
      else
      {
         /* leaf is on the left */
         SCIPbtnodeSetLeftchild(newnode, leaf);
         SCIPbtnodeSetRightchild(newnode, node);
         newnodedata->key = leafdata->key;
      }

      SCIPbtnodeSetParent(leaf, newnode);
      SCIPbtnodeSetParent(node, newnode);
   }

   /* update envelop */
   updateEnvelope(scip, node);

   return SCIP_OKAY;
}

/** returns the leaf responsible for the lambda energy */
static
SCIP_BTNODE* findResponsibleLambdaLeafTraceEnergy(
   SCIP_BTNODE*          node                /**< node which defines the subtree beases on the lambda energy */
   )
{
   SCIP_BTNODE* left;
   SCIP_BTNODE* right;
   SCIP_NODEDATA* nodedata;
   SCIP_NODEDATA* leftdata;
   SCIP_NODEDATA* rightdata;

   assert(node != NULL);

   nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(node);
   assert(nodedata != NULL);

   /* check if the node is the (responsible) leaf */
   if( SCIPbtnodeIsLeaf(node) )
   {
      assert(!nodedata->intheta);
      return node;
   }

   left = SCIPbtnodeGetLeftchild(node);
   assert(left != NULL);

   leftdata = (SCIP_NODEDATA*)