Scippy

SCIP

Solving Constraint Integer Programs

cons_cumulative.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_cumulative.c
17  * @brief constraint handler for cumulative constraints
18  * @author Timo Berthold
19  * @author Stefan Heinz
20  * @author Jens Schulz
21  *
22  * Given:
23  * - 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
24  * their demands \f$d_j\f$.
25  * - an integer resource capacity \f$C\f$
26  *
27  * 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.
28  *
29  * Separation:
30  * - can be done using binary start time model, see Pritskers, Watters and Wolfe
31  * - or by just separating relatively weak cuts on the integer start time variables
32  *
33  * Propagation:
34  * - time tabling, Klein & Scholl (1999)
35  * - Edge-finding from Petr Vilim, adjusted and simplified for dynamic repropagation
36  * (2009)
37  * - energetic reasoning, see Baptiste, Le Pape, Nuijten (2001)
38  *
39  */
40 
41 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
42 
43 #include <assert.h>
44 #include <string.h>
45 
46 #include "tclique/tclique.h"
47 #include "scip/cons_cumulative.h"
48 #include "scip/cons_linking.h"
49 #include "scip/cons_knapsack.h"
50 #include "scip/scipdefplugins.h"
51 
52 /**@name Constraint handler properties
53  *
54  * @{
55  */
56 
57 /* constraint handler properties */
58 #define CONSHDLR_NAME "cumulative"
59 #define CONSHDLR_DESC "cumulative constraint handler"
60 #define CONSHDLR_SEPAPRIORITY 2100000 /**< priority of the constraint handler for separation */
61 #define CONSHDLR_ENFOPRIORITY -2040000 /**< priority of the constraint handler for constraint enforcing */
62 #define CONSHDLR_CHECKPRIORITY -3030000 /**< priority of the constraint handler for checking feasibility */
63 #define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
64 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
65 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
66  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
67 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
68 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
69 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
70 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
71 
72 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
73 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
74 
75 /**@} */
76 
77 /**@name Default parameter values
78  *
79  * @{
80  */
81 
82 /* default parameter values */
83 
84 /* separation */
85 #define DEFAULT_USEBINVARS FALSE /**< should the binary representation be used? */
86 #define DEFAULT_LOCALCUTS FALSE /**< should cuts be added only locally? */
87 #define DEFAULT_USECOVERCUTS TRUE /**< should covering cuts be added? */
88 #define DEFAULT_CUTSASCONSS TRUE /**< should the cuts be created as knapsack constraints? */
89 #define DEFAULT_SEPAOLD TRUE /**< shall old sepa algo be applied? */
90 
91 /* propagation */
92 #define DEFAULT_TTINFER TRUE /**< should time-table (core-times) propagator be used to infer bounds? */
93 #define DEFAULT_EFCHECK FALSE /**< should edge-finding be used to detect an overload? */
94 #define DEFAULT_EFINFER FALSE /**< should edge-finding be used to infer bounds? */
95 #define DEFAULT_USEADJUSTEDJOBS FALSE /**< should during edge-finding jobs be adusted which run on the border of the effective time horizon? */
96 #define DEFAULT_TTEFCHECK TRUE /**< should time-table edge-finding be used to detect an overload? */
97 #define DEFAULT_TTEFINFER TRUE /**< should time-table edge-finding be used to infer bounds? */
98 
99 /* presolving */
100 #define DEFAULT_DUALPRESOLVE TRUE /**< should dual presolving be applied? */
101 #define DEFAULT_COEFTIGHTENING FALSE /**< should coeffisient tightening be applied? */
102 #define DEFAULT_NORMALIZE TRUE /**< should demands and capacity be normalized? */
103 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
104 #define DEFAULT_DISJUNCTIVE TRUE /**< extract disjunctive constraints? */
105 #define DEFAULT_DETECTDISJUNCTIVE TRUE /**< search for conflict set via maximal cliques to detect disjunctive constraints */
106 #define DEFAULT_DETECTVARBOUNDS TRUE /**< search for conflict set via maximal cliques to detect variable bound constraints */
107 #define DEFAULT_MAXNODES 10000LL /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
109 /* enforcement */
110 #define DEFAULT_FILLBRANCHCANDS FALSE /**< should branching candidates be added to storage? */
112 /* conflict analysis */
113 #define DEFAULT_USEBDWIDENING TRUE /**< should bound widening be used during conflict analysis? */
115 /**@} */
116 
117 /**@name Event handler properties
118  *
119  * @{
120  */
121 
122 #define EVENTHDLR_NAME "cumulative"
123 #define EVENTHDLR_DESC "bound change event handler for cumulative constraints"
125 /**@} */
126 
127 /*
128  * Data structures
129  */
130 
131 /** constraint data for cumulative constraints */
132 struct SCIP_ConsData
133 {
134  SCIP_VAR** vars; /**< array of variable representing the start time of each job */
135  SCIP_Bool* downlocks; /**< array to store if the variable has a down lock */
136  SCIP_Bool* uplocks; /**< array to store if the variable has an uplock */
137  SCIP_CONS** linkingconss; /**< array of linking constraints for the integer variables */
138  SCIP_ROW** demandrows; /**< array of rows of linear relaxation of this problem */
139  SCIP_ROW** scoverrows; /**< array of rows of small cover cuts of this problem */
140  SCIP_ROW** bcoverrows; /**< array of rows of big cover cuts of this problem */
141  int* demands; /**< array containing corresponding demands */
142  int* durations; /**< array containing corresponding durations */
143  SCIP_Real resstrength1; /**< stores the resource strength 1*/
144  SCIP_Real resstrength2; /**< stores the resource strength 2 */
145  SCIP_Real cumfactor1; /**< stroes the cumulativeness of the constraint */
146  SCIP_Real disjfactor1; /**< stores the disjunctiveness of the constraint */
147  SCIP_Real disjfactor2; /**< stores the disjunctiveness of the constraint */
148  SCIP_Real estimatedstrength;
149  int nvars; /**< number of variables */
150  int varssize; /**< size of the arrays */
151  int ndemandrows; /**< number of rows of cumulative constrint for linear relaxation */
152  int demandrowssize; /**< size of array rows of demand rows */
153  int nscoverrows; /**< number of rows of small cover cuts */
154  int scoverrowssize; /**< size of array of small cover cuts */
155  int nbcoverrows; /**< number of rows of big cover cuts */
156  int bcoverrowssize; /**< size of array of big cover cuts */
157  int capacity; /**< available cumulative capacity */
158 
159  int hmin; /**< left bound of time axis to be considered (including hmin) */
160  int hmax; /**< right bound of time axis to be considered (not including hmax) */
161 
162  unsigned int signature; /**< constraint signature which is need for pairwise comparison */
163 
164  unsigned int validsignature:1; /**< is the signature valid */
165  unsigned int normalized:1; /**< is the constraint normalized */
166  unsigned int covercuts:1; /**< cover cuts are created? */
167  unsigned int propagated:1; /**< is constraint propagted */
168  unsigned int varbounds:1; /**< bool to store if variable bound strengthening was already preformed */
169  unsigned int triedsolving:1; /**< bool to store if we tried already to solve that constraint as independent subproblem */
170 
171 #ifdef SCIP_STATISTIC
172  int maxpeak;
173 #endif
174 };
175 
176 /** constraint handler data */
177 struct SCIP_ConshdlrData
178 {
179  SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */
180 
181  SCIP_Bool usebinvars; /**< should the binary variables be used? */
182  SCIP_Bool cutsasconss; /**< should the cumulative constraint create cuts as knapsack constraints? */
183  SCIP_Bool ttinfer; /**< should time-table (core-times) propagator be used to infer bounds? */
184  SCIP_Bool efcheck; /**< should edge-finding be used to detect an overload? */
185  SCIP_Bool efinfer; /**< should edge-finding be used to infer bounds? */
186  SCIP_Bool useadjustedjobs; /**< should during edge-finding jobs be adusted which run on the border of the effective time horizon? */
187  SCIP_Bool ttefcheck; /**< should time-table edge-finding be used to detect an overload? */
188  SCIP_Bool ttefinfer; /**< should time-table edge-finding be used to infer bounds? */
189  SCIP_Bool localcuts; /**< should cuts be added only locally? */
190  SCIP_Bool usecovercuts; /**< should covering cuts be added? */
191  SCIP_Bool sepaold; /**< shall old sepa algo be applied? */
192 
193 
194  SCIP_Bool fillbranchcands; /**< should branching candidates be added to storage? */
195 
196  SCIP_Bool dualpresolve; /**< should dual presolving be applied? */
197  SCIP_Bool coeftightening; /**< should coeffisient tightening be applied? */
198  SCIP_Bool normalize; /**< should demands and capacity be normalized? */
199  SCIP_Bool disjunctive; /**< extract disjunctive constraints? */
200  SCIP_Bool detectdisjunctive; /**< search for conflict set via maximal cliques to detect disjunctive constraints */
201  SCIP_Bool detectvarbounds; /**< search for conflict set via maximal cliques to detect variable bound constraints */
202  SCIP_Bool usebdwidening; /**< should bound widening be used during conflict analysis? */
203  SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
204  SCIP_Bool detectedredundant; /**< was detection of redundant constraints already performed? */
205 
206  SCIP_Longint maxnodes; /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
207 
208  SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)); /**< method to use a single cumulative condition */
209 
210  /* statistic values which are collected if SCIP_STATISTIC is defined */
211 #ifdef SCIP_STATISTIC
212  SCIP_Longint nlbtimetable; /**< number of times the lower bound was tightened by the time-table propagator */
213  SCIP_Longint nubtimetable; /**< number of times the upper bound was tightened by the time-table propagator */
214  SCIP_Longint ncutofftimetable; /**< number of times the a cutoff was detected due to time-table propagator */
215  SCIP_Longint nlbedgefinder; /**< number of times the lower bound was tightened by the edge-finder propagator */
216  SCIP_Longint nubedgefinder; /**< number of times the upper bound was tightened by the edge-finder propagator */
217  SCIP_Longint ncutoffedgefinder; /**< number of times the a cutoff was detected due to edge-finder propagator */
218  SCIP_Longint ncutoffoverload; /**< number of times the a cutoff was detected due to overload checking via edge-finding */
219  SCIP_Longint nlbTTEF; /**< number of times the lower bound was tightened by time-table edge-finding */
220  SCIP_Longint nubTTEF; /**< number of times the upper bound was tightened by time-table edge-finding */
221  SCIP_Longint ncutoffoverloadTTEF;/**< number of times the a cutoff was detected due to overload checking via time-table edge-finding */
222 
223  int nirrelevantjobs; /**< number of time a irrelevant/redundant jobs was removed form a constraint */
224  int nalwaysruns; /**< number of time a job removed form a constraint which run completely during the effective horizon */
225  int nremovedlocks; /**< number of times a up or down lock was removed */
226  int ndualfixs; /**< number of times a dual fix was performed by a single constraint */
227  int ndecomps; /**< number of times a constraint was decomposed */
228  int ndualbranchs; /**< number of times a dual branch was discoverd and applicable via probing */
229  int nallconsdualfixs; /**< number of times a dual fix was performed due to knowledge of all cumulative constraints */
230  int naddedvarbounds; /**< number of added variable bounds constraints */
231  int naddeddisjunctives; /**< number of added disjunctive constraints */
232 
233  SCIP_Bool iscopy; /**< Boolean to store if constraint handler is part of a copy */
234 #endif
235 };
236 
237 /**@name Inference Information Methods
238  *
239  * An inference information can be passed with each domain reduction to SCIP. This information is passed back to the
240  * constraint handler if the corresponding bound change has to be explained. It can be used to store information which
241  * help to construct a reason/explanation for a bound change. The inference information is limited to size of integer.
242  *
243  * In case of the cumulative constraint handler we store the used propagation algorithms for that particular bound
244  * change and the earliest start and latest completion time of all jobs in the conflict set.
245  *
246  * @{
247  */
248 
249 /** Propagation rules */
250 enum Proprule
251 {
252  PROPRULE_1_CORETIMES = 1, /**< core-time propagator */
253  PROPRULE_2_EDGEFINDING = 2, /**< edge-finder */
254  PROPRULE_3_TTEF = 3 /**< time-table edeg-finding */
255 };
256 typedef enum Proprule PROPRULE;
258 /** inference information */
259 struct InferInfo
260 {
261  union
262  {
263  /** struct to use the inference information */
264  struct
265  {
266  unsigned int proprule:2; /**< propagation rule that was applied */
267  unsigned int data1:15; /**< data field one */
268  unsigned int data2:15; /**< data field two */
269  } asbits;
270  int asint; /**< inference information as a single int value */
271  } val;
272 };
273 typedef struct InferInfo INFERINFO;
275 /** converts an integer into an inference information */
276 static
277 INFERINFO intToInferInfo(
278  int i /**< integer to convert */
279  )
280 {
281  INFERINFO inferinfo;
282 
283  inferinfo.val.asint = i;
284 
285  return inferinfo;
286 }
287 
288 /** converts an inference information into an int */
289 static
290 int inferInfoToInt(
291  INFERINFO inferinfo /**< inference information to convert */
292  )
293 {
294  return inferinfo.val.asint;
295 }
296 
297 /** returns the propagation rule stored in the inference information */
298 static
300  INFERINFO inferinfo /**< inference information to convert */
301  )
302 {
303  return (PROPRULE) inferinfo.val.asbits.proprule;
304 }
305 
306 /** returns data field one of the inference information */
307 static
309  INFERINFO inferinfo /**< inference information to convert */
310  )
311 {
312  return (int) inferinfo.val.asbits.data1;
313 }
314 
315 /** returns data field two of the inference information */
316 static
318  INFERINFO inferinfo /**< inference information to convert */
319  )
320 {
321  return (int) inferinfo.val.asbits.data2;
322 }
323 
324 
325 /** constructs an inference information out of a propagation rule, an earliest start and a latest completion time */
326 static
327 INFERINFO getInferInfo(
328  PROPRULE proprule, /**< propagation rule that deduced the value */
329  int data1, /**< data field one */
330  int data2 /**< data field two */
331  )
332 {
333  INFERINFO inferinfo;
334 
335  /* check that the data menber are in the range of the available bits */
336  assert((int)proprule <= (1<<2)-1); /*lint !e685*/
337  assert(data1 >= 0 && data1 < (1<<15));
338  assert(data2 >= 0 && data2 < (1<<15));
339 
340  inferinfo.val.asbits.proprule = proprule; /*lint !e641*/
341  inferinfo.val.asbits.data1 = (unsigned int) data1; /*lint !e732*/
342  inferinfo.val.asbits.data2 = (unsigned int) data2; /*lint !e732*/
343 
344  return inferinfo;
345 }
346 
347 /**@} */
348 
349 /*
350  * Local methods
351  */
352 
353 /**@name Miscellaneous Methods
354  *
355  * @{
356  */
357 
358 #ifndef NDEBUG
359 
360 /** compute the core of a job which lies in certain interval [begin, end) */
361 static
363  int begin, /**< begin of the interval */
364  int end, /**< end of the interval */
365  int ect, /**< earliest completion time */
366  int lst /**< latest start time */
367  )
368 {
369  int core;
370 
371  core = MAX(0, MIN(end, ect) - MAX(lst, begin));
372 
373  return core;
374 }
375 #else
376 #define computeCoreWithInterval(begin, end, ect, lst) (MAX(0, MIN((end), (ect)) - MAX((lst), (begin))))
377 #endif
378 
379 /** returns the implied earliest start time */
380 static
382  SCIP* scip, /**< SCIP data structure */
383  SCIP_VAR* var, /**< variable for which the implied est should be returned */
384  SCIP_HASHMAP* addedvars, /**< hash map containig the variable which are already added */
385  int* est /**< pointer to store the implied earliest start time */
386  )
387 { /*lint --e{715}*/
388 #if 0
389  SCIP_VAR** vbdvars;
390  SCIP_VAR* vbdvar;
391  SCIP_Real* vbdcoefs;
392  SCIP_Real* vbdconsts;
393  void* image;
394  int nvbdvars;
395  int v;
396 #endif
397 
398  (*est) = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
399 
400 #if 0
401  /* the code contains a bug; we need to check if an implication forces that the jobs do not run in parallel */
402 
403  nvbdvars = SCIPvarGetNVlbs(var);
404  vbdvars = SCIPvarGetVlbVars(var);
405  vbdcoefs = SCIPvarGetVlbCoefs(var);
406  vbdconsts = SCIPvarGetVlbConstants(var);
407 
408  for( v = 0; v < nvbdvars; ++v )
409  {
410  vbdvar = vbdvars[v];
411  assert(vbdvar != NULL);
412 
413  image = SCIPhashmapGetImage(addedvars, (void*)vbdvar);
414 
415  if( image != NULL && SCIPisEQ(scip, vbdcoefs[v], 1.0 ) )
416  {
417  int duration;
418  int vbdconst;
419 
420  duration = (int)(size_t)image;
421  vbdconst = SCIPconvertRealToInt(scip, vbdconsts[v]);
422 
423  SCIPdebugMsg(scip, "check implication <%s>[%g,%g] >= <%s>[%g,%g] + <%g>\n",
425  SCIPvarGetName(vbdvar), SCIPvarGetLbLocal(vbdvar), SCIPvarGetUbLocal(vbdvar), vbdconsts[v]);
426 
427  if( duration >= vbdconst )
428  {
429  int impliedest;
430 
431  impliedest = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vbdvar)) + duration;
432 
433  if( (*est) < impliedest )
434  {
435  (*est) = impliedest;
436 
437  SCIP_CALL( SCIPhashmapRemove(addedvars, (void*)vbdvar) );
438  }
439  }
440  }
441  }
442 #endif
443 
444  return SCIP_OKAY;
445 }
446 
447 /** returns the implied latest completion time */
448 static
450  SCIP* scip, /**< SCIP data structure */
451  SCIP_VAR* var, /**< variable for which the implied est should be returned */
452  int duration, /**< duration of the given job */
453  SCIP_HASHMAP* addedvars, /**< hash map containig the variable which are already added */
454  int* lct /**< pointer to store the implied latest completion time */
455  )
456 { /*lint --e{715}*/
457 #if 0
458  SCIP_VAR** vbdvars;
459  SCIP_VAR* vbdvar;
460  SCIP_Real* vbdcoefs;
461  SCIP_Real* vbdconsts;
462  int nvbdvars;
463  int v;
464 #endif
465 
466  (*lct) = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) + duration;
467 
468 #if 0
469  /* the code contains a bug; we need to check if an implication forces that the jobs do not run in parallel */
470 
471  nvbdvars = SCIPvarGetNVubs(var);
472  vbdvars = SCIPvarGetVubVars(var);
473  vbdcoefs = SCIPvarGetVubCoefs(var);
474  vbdconsts = SCIPvarGetVubConstants(var);
475 
476  for( v = 0; v < nvbdvars; ++v )
477  {
478  vbdvar = vbdvars[v];
479  assert(vbdvar != NULL);
480 
481  if( SCIPhashmapExists(addedvars, (void*)vbdvar) && SCIPisEQ(scip, vbdcoefs[v], 1.0 ) )
482  {
483  int vbdconst;
484 
485  vbdconst = SCIPconvertRealToInt(scip, -vbdconsts[v]);
486 
487  SCIPdebugMsg(scip, "check implication <%s>[%g,%g] <= <%s>[%g,%g] + <%g>\n",
489  SCIPvarGetName(vbdvar), SCIPvarGetLbLocal(vbdvar), SCIPvarGetUbLocal(vbdvar), vbdconsts[v]);
490 
491  if( duration >= -vbdconst )
492  {
493  int impliedlct;
494 
495  impliedlct = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vbdvar));
496 
497  if( (*lct) > impliedlct )
498  {
499  (*lct) = impliedlct;
500 
501  SCIP_CALL( SCIPhashmapRemove(addedvars, (void*)vbdvar) );
502  }
503  }
504  }
505  }
506 #endif
507 
508  return SCIP_OKAY;
509 }
510 
511 /** collects all necessary binary variables to represent the jobs which can be active at time point of interest */
512 static
514  SCIP* scip, /**< SCIP data structure */
515  SCIP_CONSDATA* consdata, /**< constraint data */
516  SCIP_VAR*** vars, /**< pointer to the array to store the binary variables */
517  int** coefs, /**< pointer to store the coefficients */
518  int* nvars, /**< number if collect binary variables */
519  int* startindices, /**< permutation with rspect to the start times */
520  int curtime, /**< current point in time */
521  int nstarted, /**< number of jobs that start before the curtime or at curtime */
522  int nfinished /**< number of jobs that finished before curtime or at curtime */
523  )
524 {
525  int nrowvars;
526  int startindex;
527  int size;
528 
529  size = 10;
530  nrowvars = 0;
531  startindex = nstarted - 1;
532 
533  SCIP_CALL( SCIPallocBufferArray(scip, vars, size) );
534  SCIP_CALL( SCIPallocBufferArray(scip, coefs, size) );
535 
536  /* search for the (nstarted - nfinished) jobs which are active at curtime */
537  while( nstarted - nfinished > nrowvars )
538  {
539  SCIP_VAR* var;
540  int endtime;
541  int duration;
542  int demand;
543  int varidx;
544 
545  /* collect job information */
546  varidx = startindices[startindex];
547  assert(varidx >= 0 && varidx < consdata->nvars);
548 
549  var = consdata->vars[varidx];
550  duration = consdata->durations[varidx];
551  demand = consdata->demands[varidx];
552  assert(var != NULL);
553 
554  endtime = SCIPconvertRealToInt(scip, SCIPvarGetUbGlobal(var)) + duration;
555 
556  /* check the end time of this job is larger than the curtime; in this case the job is still running */
557  if( endtime > curtime )
558  {
559  SCIP_VAR** binvars;
560  int* vals;
561  int nbinvars;
562  int start;
563  int end;
564  int b;
565 
566  /* check if the linking constraints exists */
567  assert(SCIPexistsConsLinking(scip, var));
568  assert(SCIPgetConsLinking(scip, var) != NULL);
569  assert(SCIPgetConsLinking(scip, var) == consdata->linkingconss[varidx]);
570 
571  /* collect linking constraint information */
572  SCIP_CALL( SCIPgetBinvarsLinking(scip, consdata->linkingconss[varidx], &binvars, &nbinvars) );
573  vals = SCIPgetValsLinking(scip, consdata->linkingconss[varidx]);
574 
575  start = curtime - duration + 1;
576  end = MIN(curtime, endtime - duration);
577 
578  for( b = 0; b < nbinvars; ++b )
579  {
580  if( vals[b] < start )
581  continue;
582 
583  if( vals[b] > end )
584  break;
585 
586  assert(binvars[b] != NULL);
587 
588  /* ensure array proper array size */
589  if( size == *nvars )
590  {
591  size *= 2;
592  SCIP_CALL( SCIPreallocBufferArray(scip, vars, size) );
593  SCIP_CALL( SCIPreallocBufferArray(scip, coefs, size) );
594  }
595 
596  (*vars)[*nvars] = binvars[b];
597  (*coefs)[*nvars] = demand;
598  (*nvars)++;
599  }
600  nrowvars++;
601  }
602 
603  startindex--;
604  }
605 
606  return SCIP_OKAY;
607 }
608 
609 /** collect all integer variable which belong to jobs which can run at the point of interest */
610 static
612  SCIP* scip, /**< SCIP data structure */
613  SCIP_CONSDATA* consdata, /**< constraint data */
614  SCIP_VAR*** activevars, /**< jobs that are currently running */
615  int* startindices, /**< permutation with rspect to the start times */
616  int curtime, /**< current point in time */
617  int nstarted, /**< number of jobs that start before the curtime or at curtime */
618  int nfinished, /**< number of jobs that finished before curtime or at curtime */
619  SCIP_Bool lower, /**< shall cuts be created due to lower or upper bounds? */
620  int* lhs /**< lhs for the new row sum of lbs + minoffset */
621  )
622 {
623  SCIP_VAR* var;
624  int startindex;
625  int endtime;
626  int duration;
627  int starttime;
628 
629  int varidx;
630  int sumofstarts;
631  int mindelta;
632  int counter;
633 
634  assert(curtime >= consdata->hmin);
635  assert(curtime < consdata->hmax);
636 
637  counter = 0;
638  sumofstarts = 0;
639 
640  mindelta = INT_MAX;
641 
642  startindex = nstarted - 1;
643 
644  /* search for the (nstarted - nfinished) jobs which are active at curtime */
645  while( nstarted - nfinished > counter )
646  {
647  assert(startindex >= 0);
648 
649  /* collect job information */
650  varidx = startindices[startindex];
651  assert(varidx >= 0 && varidx < consdata->nvars);
652 
653  var = consdata->vars[varidx];
654  duration = consdata->durations[varidx];
655  assert(duration > 0);
656  assert(var != NULL);
657 
658  if( lower )
659  starttime = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
660  else
661  starttime = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
662 
663  endtime = MIN(starttime + duration, consdata->hmax);
664 
665  /* check the end time of this job is larger than the curtime; in this case the job is still running */
666  if( endtime > curtime )
667  {
668  (*activevars)[counter] = var;
669  sumofstarts += starttime;
670  mindelta = MIN(mindelta, endtime - curtime); /* this amount of schifting holds for lb and ub */
671  counter++;
672  }
673 
674  startindex--;
675  }
676 
677  assert(mindelta > 0);
678  *lhs = lower ? sumofstarts + mindelta : sumofstarts - mindelta;
679 
680  return SCIP_OKAY;
681 }
682 
683 /** initialize the sorted event point arrays */
684 static
686  SCIP* scip, /**< SCIP data structure */
687  int nvars, /**< number of start time variables (activities) */
688  SCIP_VAR** vars, /**< array of start time variables */
689  int* durations, /**< array of durations per start time variable */
690  int* starttimes, /**< array to store sorted start events */
691  int* endtimes, /**< array to store sorted end events */
692  int* startindices, /**< permutation with rspect to the start times */
693  int* endindices, /**< permutation with rspect to the end times */
694  SCIP_Bool local /**< shall local bounds be used */
695  )
696 {
697  SCIP_VAR* var;
698  int j;
699 
700  assert(vars != NULL || nvars == 0);
701 
702  /* assign variables, start and endpoints to arrays */
703  for ( j = 0; j < nvars; ++j )
704  {
705  assert(vars != NULL);
706 
707  var = vars[j];
708  assert(var != NULL);
709 
710  if( local )
711  starttimes[j] = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
712  else
713  starttimes[j] = SCIPconvertRealToInt(scip, SCIPvarGetLbGlobal(var));
714 
715  startindices[j] = j;
716 
717  if( local )
718  endtimes[j] = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) + durations[j];
719  else
720  endtimes[j] = SCIPconvertRealToInt(scip, SCIPvarGetUbGlobal(var)) + durations[j];
721 
722  endindices[j] = j;
723 
724  }
725 
726  /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
727  SCIPsortIntInt(starttimes, startindices, j);
728  SCIPsortIntInt(endtimes, endindices, j);
729 }
730 
731 /** initialize the sorted event point arrays w.r.t. the given primal solutions */
732 static
734  SCIP* scip, /**< SCIP data structure */
735  SCIP_SOL* sol, /**< solution */
736  int nvars, /**< number of start time variables (activities) */
737  SCIP_VAR** vars, /**< array of start time variables */
738  int* durations, /**< array of durations per start time variable */
739  int* starttimes, /**< array to store sorted start events */
740  int* endtimes, /**< array to store sorted end events */
741  int* startindices, /**< permutation with rspect to the start times */
742  int* endindices /**< permutation with rspect to the end times */
743  )
744 {
745  SCIP_VAR* var;
746  int j;
747 
748  assert(vars != NULL || nvars == 0);
749 
750  /* assign variables, start and endpoints to arrays */
751  for ( j = 0; j < nvars; ++j )
752  {
753  assert(vars != NULL);
754 
755  var = vars[j];
756  assert(var != NULL);
757 
758  starttimes[j] = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, var));
759  startindices[j] = j;
760 
761  endtimes[j] = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, var)) + durations[j];
762  endindices[j] = j;
763 
764  }
765 
766  /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
767  SCIPsortIntInt(starttimes, startindices, j);
768  SCIPsortIntInt(endtimes, endindices, j);
769 }
770 
771 /** initialize the sorted event point arrays
772  *
773  * @todo Check the separation process!
774  */
775 static
777  SCIP* scip, /**< SCIP data structure */
778  SCIP_CONSDATA* consdata, /**< constraint data */
779  SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
780  int* starttimes, /**< array to store sorted start events */
781  int* endtimes, /**< array to store sorted end events */
782  int* startindices, /**< permutation with rspect to the start times */
783  int* endindices, /**< permutation with rspect to the end times */
784  int* nvars, /**< number of variables that are integral */
785  SCIP_Bool lower /**< shall the constraints be derived for lower or upper bounds? */
786  )
787 {
788  SCIP_VAR* var;
789  int tmpnvars;
790  int j;
791 
792  tmpnvars = consdata->nvars;
793  *nvars = 0;
794 
795  /* assign variables, start and endpoints to arrays */
796  for ( j = 0; j < tmpnvars; ++j )
797  {
798  var = consdata->vars[j];
799  assert(var != NULL);
800  assert(consdata->durations[j] > 0);
801  assert(consdata->demands[j] > 0);
802 
803  if( lower )
804  {
805  /* only consider jobs that are at their lower or upper bound */
806  if( !SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, var))
807  || !SCIPisFeasEQ(scip, SCIPgetSolVal(scip, sol, var), SCIPvarGetLbLocal(var)) )
808  continue;
809 
810 
811  starttimes[*nvars] = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, var));
812  startindices[*nvars] = j;
813 
814  endtimes[*nvars] = starttimes[*nvars] + consdata->durations[j];
815  endindices[*nvars] = j;
816 
817  SCIPdebugMsg(scip, "%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
818  *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var),
819  consdata->durations[j],
820  starttimes[*nvars], starttimes[*nvars] + consdata->durations[startindices[*nvars]],
821  consdata->demands[startindices[*nvars]]);
822 
823  (*nvars)++;
824  }
825  else
826  {
827  if( !SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, var))
828  || !SCIPisFeasEQ(scip, SCIPgetSolVal(scip, sol, var), SCIPvarGetUbLocal(var)) )
829  continue;
830 
831  starttimes[*nvars] = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, var));
832  startindices[*nvars] = j;
833 
834  endtimes[*nvars] = starttimes[*nvars] + consdata->durations[j];
835  endindices[*nvars] = j;
836 
837  SCIPdebugMsg(scip, "%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
838  *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var),
839  consdata->durations[j],
840  starttimes[*nvars], starttimes[*nvars] + consdata->durations[startindices[*nvars]],
841  consdata->demands[startindices[*nvars]]);
842 
843  (*nvars)++;
844  }
845  }
846 
847  /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
848  SCIPsortIntInt(starttimes, startindices, *nvars);
849  SCIPsortIntInt(endtimes, endindices, *nvars);
850 
851 #ifdef SCIP_DEBUG
852  SCIPdebugMsg(scip, "sorted output %d\n", *nvars);
853 
854  for ( j = 0; j < *nvars; ++j )
855  {
856  SCIPdebugMsg(scip, "%d: job[%d] starttime %d, endtime = %d, demand = %d\n", j,
857  startindices[j], starttimes[j], starttimes[j] + consdata->durations[startindices[j]],
858  consdata->demands[startindices[j]]);
859  }
860 
861  for ( j = 0; j < *nvars; ++j )
862  {
863  SCIPdebugMsg(scip, "%d: job[%d] endtime %d, demand = %d\n", j, endindices[j], endtimes[j],
864  consdata->demands[endindices[j]]);
865  }
866 #endif
867 }
868 
869 #ifdef SCIP_STATISTIC
870 /** this method checks for relevant intervals for energetic reasoning */
871 static
872 SCIP_RETCODE computeRelevantEnergyIntervals(
873  SCIP* scip, /**< SCIP data structure */
874  int nvars, /**< number of start time variables (activities) */
875  SCIP_VAR** vars, /**< array of start time variables */
876  int* durations, /**< array of durations */
877  int* demands, /**< array of demands */
878  int capacity, /**< cumulative capacity */
879  int hmin, /**< left bound of time axis to be considered (including hmin) */
880  int hmax, /**< right bound of time axis to be considered (not including hmax) */
881  int** timepoints, /**< array to store relevant points in time */
882  SCIP_Real** cumulativedemands, /**< array to store the estimated cumulative demand for each point in time */
883  int* ntimepoints, /**< pointer to store the number of timepoints */
884  int* maxdemand, /**< pointer to store maximum over all demands */
885  SCIP_Real* minfreecapacity /**< pointer to store the minimum free capacity */
886  )
887 {
888  int* starttimes; /* stores when each job is starting */
889  int* endtimes; /* stores when each job ends */
890  int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
891  int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
892 
893  SCIP_Real totaldemand;
894  int curtime; /* point in time which we are just checking */
895  int endindex; /* index of endsolvalues with: endsolvalues[endindex] > curtime */
896 
897  int j;
898 
899  assert( scip != NULL );
900  assert(durations != NULL);
901  assert(demands != NULL);
902  assert(capacity >= 0);
903 
904  /* if no activities are associated with this cumulative then this constraint is redundant */
905  if( nvars == 0 )
906  return SCIP_OKAY;
907 
908  assert(vars != NULL);
909 
910  SCIP_CALL( SCIPallocBufferArray(scip, &starttimes, nvars) );
911  SCIP_CALL( SCIPallocBufferArray(scip, &endtimes, nvars) );
912  SCIP_CALL( SCIPallocBufferArray(scip, &startindices, nvars) );
913  SCIP_CALL( SCIPallocBufferArray(scip, &endindices, nvars) );
914 
915  /* create event point arrays */
916  createSortedEventpoints(scip, nvars, vars, durations, starttimes, endtimes, startindices, endindices, TRUE);
917 
918  endindex = 0;
919  totaldemand = 0.0;
920 
921  *ntimepoints = 0;
922  (*timepoints)[0] = starttimes[0];
923  (*cumulativedemands)[0] = 0;
924  *maxdemand = 0;
925 
926  /* check each startpoint of a job whether the capacity is kept or not */
927  for( j = 0; j < nvars; ++j )
928  {
929  int lct;
930  int idx;
931 
932  curtime = starttimes[j];
933 
934  if( curtime >= hmax )
935  break;
936 
937  /* free all capacity usages of jobs the are no longer running */
938  while( endindex < nvars && endtimes[endindex] <= curtime )
939  {
940  int est;
941 
942  if( (*timepoints)[*ntimepoints] < endtimes[endindex] )
943  {
944  (*ntimepoints)++;
945  (*timepoints)[*ntimepoints] = endtimes[endindex];
946  (*cumulativedemands)[*ntimepoints] = 0;
947  }
948 
949  idx = endindices[endindex];
950  est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[idx]));
951  totaldemand -= (SCIP_Real) demands[idx] * durations[idx] / (endtimes[endindex] - est);
952  endindex++;
953 
954  (*cumulativedemands)[*ntimepoints] = totaldemand;
955  }
956 
957  idx = startindices[j];
958  lct = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[idx]) + durations[idx]);
959  totaldemand += (SCIP_Real) demands[idx] * durations[idx] / (lct - starttimes[j]);
960 
961  if( (*timepoints)[*ntimepoints] < curtime )
962  {
963  (*ntimepoints)++;
964  (*timepoints)[*ntimepoints] = curtime;
965  (*cumulativedemands)[*ntimepoints] = 0;
966  }
967 
968  (*cumulativedemands)[*ntimepoints] = totaldemand;
969 
970  /* add the relative capacity requirements for all job which start at the curtime */
971  while( j+1 < nvars && starttimes[j+1] == curtime )
972  {
973  ++j;
974  idx = startindices[j];
975  lct = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[idx]) + durations[idx]);
976  totaldemand += (SCIP_Real) demands[idx] * durations[idx] / (lct - starttimes[j]);
977 
978  (*cumulativedemands)[*ntimepoints] = totaldemand;
979  }
980  } /*lint --e{850}*/
981 
982  /* free all capacity usages of jobs that are no longer running */
983  while( endindex < nvars/* && endtimes[endindex] < hmax*/)
984  {
985  int est;
986  int idx;
987 
988  if( (*timepoints)[*ntimepoints] < endtimes[endindex] )
989  {
990  (*ntimepoints)++;
991  (*timepoints)[*ntimepoints] = endtimes[endindex];
992  (*cumulativedemands)[*ntimepoints] = 0;
993  }
994 
995  idx = endindices[endindex];
996  est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[idx]));
997  totaldemand -= (SCIP_Real) demands[idx] * durations[idx] / (endtimes[endindex] - est);
998  (*cumulativedemands)[*ntimepoints] = totaldemand;
999 
1000  ++endindex;
1001  }
1002 
1003  (*ntimepoints)++;
1004  /* compute minimum free capacity */
1005  (*minfreecapacity) = INT_MAX;
1006  for( j = 0; j < *ntimepoints; ++j )
1007  {
1008  if( (*timepoints)[j] >= hmin && (*timepoints)[j] < hmax )
1009  *minfreecapacity = MIN( *minfreecapacity, (SCIP_Real)capacity - (*cumulativedemands)[j] );
1010  }
1011 
1012  /* free buffer arrays */
1013  SCIPfreeBufferArray(scip, &endindices);
1014  SCIPfreeBufferArray(scip, &startindices);
1015  SCIPfreeBufferArray(scip, &endtimes);
1016  SCIPfreeBufferArray(scip, &starttimes);
1017 
1018  return SCIP_OKAY;
1019 }
1020 
1021 /** evaluates the cumulativeness and disjointness factor of a cumulative constraint */
1022 static
1023 SCIP_RETCODE evaluateCumulativeness(
1024  SCIP* scip, /**< pointer to scip */
1025  SCIP_CONS* cons /**< cumulative constraint */
1026  )
1027 {
1028  SCIP_CONSDATA* consdata;
1029  int nvars;
1030  int v;
1031  int capacity;
1032 
1033  /* output values: */
1034  SCIP_Real disjfactor2; /* (peak-capacity)/capacity * (large demands/nvars_t) */
1035  SCIP_Real cumfactor1;
1036  SCIP_Real resstrength1; /* overall strength */
1037  SCIP_Real resstrength2; /* timepoint wise maximum */
1038 
1039  /* helpful variables: */
1040  SCIP_Real globalpeak;
1041  SCIP_Real globalmaxdemand;
1042 
1043  /* get constraint data structure */
1044  consdata = SCIPconsGetData(cons);
1045  assert(consdata != NULL);
1046 
1047  nvars = consdata->nvars;
1048  capacity = consdata->capacity;
1049  globalpeak = 0.0;
1050  globalmaxdemand = 0.0;
1051 
1052  disjfactor2 = 0.0;
1053  cumfactor1 = 0.0;
1054  resstrength2 = 0.0;
1055 
1056  /* check each starting time (==each job, but inefficient) */
1057  for( v = 0; v < nvars; ++v )
1058  {
1059  SCIP_Real peak;
1060  SCIP_Real maxdemand;
1061  SCIP_Real deltademand;
1062  int ndemands;
1063  int nlarge;
1064 
1065  int timepoint;
1066  int j;
1067  timepoint = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(consdata->vars[v]));
1068  peak = consdata->demands[v];
1069  ndemands = 1;
1070  maxdemand = 0;
1071  nlarge = 0;
1072 
1073  if( consdata->demands[v] > capacity / 3 )
1074  nlarge++;
1075 
1076  for( j = 0; j < nvars; ++j )
1077  {
1078  int lb;
1079 
1080  if( j == v )
1081  continue;
1082 
1083  maxdemand = 0.0;
1084  lb = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(consdata->vars[j]));
1085 
1086  if( lb <= timepoint && lb + consdata->durations[j] > timepoint )
1087  {
1088  peak += consdata->demands[j];
1089  ndemands++;
1090 
1091  if( consdata->demands[j] > consdata->capacity / 3 )
1092  nlarge++;
1093  }
1094  }
1095 
1096  deltademand = (SCIP_Real)peak / (SCIP_Real)ndemands;
1097  globalpeak = MAX(globalpeak, peak);
1098  globalmaxdemand = MAX(globalmaxdemand, maxdemand);
1099 
1100  if( peak > capacity )
1101  {
1102  disjfactor2 = MAX( disjfactor2, (peak-(SCIP_Real)capacity)/peak * (nlarge/(SCIP_Real)ndemands) );
1103  cumfactor1 = MAX( cumfactor1, (peak-capacity)/peak * (capacity-deltademand)/(SCIP_Real)capacity );
1104  resstrength2 = MAX(resstrength2, (capacity-maxdemand)/(peak-maxdemand) );
1105  }
1106  }
1107 
1108  resstrength1 = (capacity-globalmaxdemand) / (globalpeak-globalmaxdemand);
1109 
1110  consdata->maxpeak = SCIPconvertRealToInt(scip, globalpeak);
1111  consdata->disjfactor2 = disjfactor2;
1112  consdata->cumfactor1 = cumfactor1;
1113  consdata->resstrength2 = resstrength2;
1114  consdata->resstrength1 = resstrength1;
1115 
1116  /* get estimated res strength */
1117  {
1118  int* timepoints;
1119  SCIP_Real* estimateddemands;
1120  int ntimepoints;
1121  int maxdemand;
1122  SCIP_Real minfreecapacity;
1123 
1124  SCIP_CALL( SCIPallocBufferArray(scip, &timepoints, 2*nvars) );
1125  SCIP_CALL( SCIPallocBufferArray(scip, &estimateddemands, 2*nvars) );
1126 
1127  ntimepoints = 0;
1128  minfreecapacity = INT_MAX;
1129 
1130 
1131  SCIP_CALL( computeRelevantEnergyIntervals(scip, nvars, consdata->vars,
1132  consdata->durations, consdata->demands,
1133  capacity, consdata->hmin, consdata->hmax, &timepoints, &estimateddemands,
1134  &ntimepoints, &maxdemand, &minfreecapacity) );
1135 
1136  /* free buffer arrays */
1137  SCIPfreeBufferArray(scip, &estimateddemands);
1138  SCIPfreeBufferArray(scip, &timepoints);
1139 
1140  consdata->estimatedstrength = (SCIP_Real)(capacity - minfreecapacity) / (SCIP_Real) capacity;
1141  }
1142 
1143  SCIPstatisticPrintf("cumulative constraint<%s>: DISJ1=%g, DISJ2=%g, CUM=%g, RS1 = %g, RS2 = %g, EST = %g\n",
1144  SCIPconsGetName(cons), consdata->disjfactor1, disjfactor2, cumfactor1, resstrength1, resstrength2,
1145  consdata->estimatedstrength);
1146 
1147  return SCIP_OKAY;
1148 }
1149 #endif
1150 
1151 /** gets the active variables together with the constant */
1152 static
1154  SCIP* scip, /**< SCIP data structure */
1155  SCIP_VAR** var, /**< pointer to store the active variable */
1156  int* scalar, /**< pointer to store the scalar */
1157  int* constant /**< pointer to store the constant */
1158  )
1159 {
1160  if( !SCIPvarIsActive(*var) )
1161  {
1162  SCIP_Real realscalar;
1163  SCIP_Real realconstant;
1164 
1165  realscalar = 1.0;
1166  realconstant = 0.0;
1167 
1169 
1170  /* transform variable to active variable */
1171  SCIP_CALL( SCIPgetProbvarSum(scip, var, &realscalar, &realconstant) );
1172  assert(!SCIPisZero(scip, realscalar));
1173  assert(SCIPvarIsActive(*var));
1174 
1175  if( realconstant < 0.0 )
1176  (*constant) = -SCIPconvertRealToInt(scip, -realconstant);
1177  else
1178  (*constant) = SCIPconvertRealToInt(scip, realconstant);
1179 
1180  if( realscalar < 0.0 )
1181  (*scalar) = -SCIPconvertRealToInt(scip, -realscalar);
1182  else
1183  (*scalar) = SCIPconvertRealToInt(scip, realscalar);
1184  }
1185  else
1186  {
1187  (*scalar) = 1;
1188  (*constant) = 0;
1189  }
1190 
1191  assert(*scalar != 0);
1192 
1193  return SCIP_OKAY;
1194 }
1195 
1196 /** computes the total energy of all jobs */
1197 static
1198 int computeTotalEnergy(
1199  int* durations, /**< array of job durations */
1200  int* demands, /**< array of job demands */
1201  int njobs /**< number of jobs */
1202  )
1203 {
1204  int energy;
1205  int j;
1206 
1207  energy = 0;
1208 
1209  for( j = 0; j < njobs; ++j )
1210  energy += durations[j] * demands[j];
1211 
1212  return energy;
1213 }
1214 
1215 /**@} */
1216 
1217 /**@name Default method to solve a cumulative condition
1218  *
1219  * @{
1220  */
1221 
1222 /** solve single cumulative condition using SCIP and a single cumulative constraint */
1223 static
1224 SCIP_DECL_SOLVECUMULATIVE(solveCumulativeViaScipCp)
1226  SCIP* subscip;
1227  SCIP_VAR** subvars;
1228  SCIP_CONS* cons;
1229  SCIP_RETCODE retcode;
1230  char name[SCIP_MAXSTRLEN];
1231  int v;
1232 
1233  assert(njobs > 0);
1234 
1235  (*solved) = FALSE;
1236  (*infeasible) = FALSE;
1237  (*unbounded) = FALSE;
1238  (*error) = FALSE;
1239 
1240  SCIPdebugMessage("solve independent cumulative condition with %d variables\n", njobs);
1241 
1242  /* initialize the sub-problem */
1243  SCIP_CALL( SCIPcreate(&subscip) );
1244 
1245  /* copy all plugins */
1247 
1248  /* create the subproblem */
1249  SCIP_CALL( SCIPcreateProbBasic(subscip, "cumulative") );
1250 
1251  SCIP_CALL( SCIPallocBlockMemoryArray(subscip, &subvars, njobs) );
1252 
1253  /* create for each job a start time variable */
1254  for( v = 0; v < njobs; ++v )
1255  {
1256  SCIP_Real objval;
1257 
1258  /* construct varibale name */
1259  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "job%d", v);
1260 
1261  if( objvals == NULL )
1262  objval = 0.0;
1263  else
1264  objval = objvals[v];
1265 
1266  SCIP_CALL( SCIPcreateVarBasic(subscip, &subvars[v], name, ests[v], lsts[v], objval, SCIP_VARTYPE_INTEGER) );
1267  SCIP_CALL( SCIPaddVar(subscip, subvars[v]) );
1268  }
1269 
1270  /* create cumulative constraint */
1271  SCIP_CALL( SCIPcreateConsBasicCumulative(subscip, &cons, "cumulative",
1272  njobs, subvars, durations, demands, capacity) );
1273 
1274  /* set effective horizon */
1275  SCIP_CALL( SCIPsetHminCumulative(subscip, cons, hmin) );
1276  SCIP_CALL( SCIPsetHmaxCumulative(subscip, cons, hmax) );
1277 
1278  /* add cumulative constraint */
1279  SCIP_CALL( SCIPaddCons(subscip, cons) );
1280  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1281 
1282  /* set CP solver settings
1283  *
1284  * @note This "meta" setting has to be set first since this call overwrite all parameters including for example the
1285  * time limit.
1286  */
1288 
1289  /* do not abort subproblem on CTRL-C */
1290  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
1291 
1292  /* disable output to console */
1293  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1294 
1295  /* set limits for the subproblem */
1296  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", maxnodes) );
1297  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
1298  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
1299 
1300  /* forbid recursive call of heuristics and separators solving subMIPs
1301  * todo: really? This method was part of 3.0.1 but not in v31-Bugfix
1302  */
1303  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
1304 
1305  /* solve single cumulative constraint by branch and bound */
1306  retcode = SCIPsolve(subscip);
1307 
1308  if( retcode != SCIP_OKAY )
1309  (*error) = TRUE;
1310  else
1311  {
1312  SCIPdebugMsg(subscip, "solved single cumulative condition with status %d\n", SCIPgetStatus(subscip));
1313 
1314  /* evaluated solution status */
1315  switch( SCIPgetStatus(subscip) )
1316  {
1317  case SCIP_STATUS_INFORUNBD:
1319  (*infeasible) = TRUE;
1320  (*solved) = TRUE;
1321  break;
1322  case SCIP_STATUS_UNBOUNDED:
1323  (*unbounded) = TRUE;
1324  (*solved) = TRUE;
1325  break;
1326  case SCIP_STATUS_OPTIMAL:
1327  {
1328  SCIP_SOL* sol;
1329  SCIP_Real solval;
1330 
1331  sol = SCIPgetBestSol(subscip);
1332  assert(sol != NULL);
1333 
1334  for( v = 0; v < njobs; ++v )
1335  {
1336  solval = SCIPgetSolVal(subscip, sol, subvars[v]);
1337 
1338  ests[v] = solval;
1339  lsts[v] = solval;
1340  }
1341  (*solved) = TRUE;
1342  break;
1343  }
1344  case SCIP_STATUS_NODELIMIT:
1346  case SCIP_STATUS_TIMELIMIT:
1347  case SCIP_STATUS_MEMLIMIT:
1349  /* transfer the global bound changes */
1350  for( v = 0; v < njobs; ++v )
1351  {
1352  ests[v] = SCIPvarGetLbGlobal(subvars[v]);
1353  lsts[v] = SCIPvarGetUbGlobal(subvars[v]);
1354  }
1355  (*solved) = FALSE;
1356  break;
1357 
1358  case SCIP_STATUS_UNKNOWN:
1360  case SCIP_STATUS_GAPLIMIT:
1361  case SCIP_STATUS_SOLLIMIT:
1364  SCIPerrorMessage("invalid status code <%d>\n", SCIPgetStatus(subscip));
1365  return SCIP_INVALIDDATA;
1366  }
1367  }
1368 
1369  /* release all variables */
1370  for( v = 0; v < njobs; ++v )
1371  {
1372  SCIP_CALL( SCIPreleaseVar(subscip, &subvars[v]) );
1373  }
1374 
1375  SCIPfreeBlockMemoryArray(subscip, &subvars, njobs);
1376 
1377  SCIP_CALL( SCIPfree(&subscip) );
1378 
1379  return SCIP_OKAY;
1380 }
1381 
1382 #if 0
1383 /** solve single cumulative condition using SCIP and the time indexed formulation */
1384 static
1385 SCIP_DECL_SOLVECUMULATIVE(solveCumulativeViaScipMip)
1386 {
1387  SCIP* subscip;
1388  SCIP_VAR*** binvars;
1389  SCIP_RETCODE retcode;
1390  char name[SCIP_MAXSTRLEN];
1391  int minest;
1392  int maxlct;
1393  int t;
1394  int v;
1395 
1396  assert(njobs > 0);
1397 
1398  (*solved) = FALSE;
1399  (*infeasible) = FALSE;
1400  (*unbounded) = FALSE;
1401  (*error) = FALSE;
1402 
1403  SCIPdebugMsg(scip, "solve independent cumulative condition with %d variables\n", njobs);
1404 
1405  /* initialize the sub-problem */
1406  SCIP_CALL( SCIPcreate(&subscip) );
1407 
1408  /* copy all plugins */
1410 
1411  /* create the subproblem */
1412  SCIP_CALL( SCIPcreateProbBasic(subscip, "cumulative") );
1413 
1414  SCIP_CALL( SCIPallocBufferArray(subscip, &binvars, njobs) );
1415 
1416  minest = INT_MAX;
1417  maxlct = INT_MIN;
1418 
1419  /* create for each job and time step a binary variable which is one if this jobs starts at this time point and a set
1420  * partitioning constrain which forces that job starts
1421  */
1422  for( v = 0; v < njobs; ++v )
1423  {
1424  SCIP_CONS* cons;
1425  SCIP_Real objval;
1426  int timeinterval;
1427  int est;
1428  int lst;
1429 
1430  if( objvals == NULL )
1431  objval = 0.0;
1432  else
1433  objval = objvals[v];
1434 
1435  est = ests[v];
1436  lst = lsts[v];
1437 
1438  /* compute number of possible start points */
1439  timeinterval = lst - est + 1;
1440  assert(timeinterval > 0);
1441 
1442  /* compute the smallest earliest start time and largest latest completion time */
1443  minest = MIN(minest, est);
1444  maxlct = MAX(maxlct, lst + durations[v]);
1445 
1446  /* construct constraint name */
1447  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d", v);
1448 
1449  SCIP_CALL( SCIPcreateConsBasicSetpart(subscip, &cons, name, 0, NULL) );
1450 
1451  SCIP_CALL( SCIPallocBufferArray(subscip, &binvars[v], timeinterval) );
1452 
1453  for( t = 0; t < timeinterval; ++t )
1454  {
1455  SCIP_VAR* binvar;
1456 
1457  /* construct varibale name */
1458  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_time_%d", v, t + est);
1459 
1460  SCIP_CALL( SCIPcreateVarBasic(subscip, &binvar, name, 0.0, 1.0, objval, SCIP_VARTYPE_BINARY) );
1461  SCIP_CALL( SCIPaddVar(subscip, binvar) );
1462 
1463  /* add binary varibale to the set partitioning constraint which ensures that the job is started */
1464  SCIP_CALL( SCIPaddCoefSetppc(subscip, cons, binvar) );
1465 
1466  binvars[v][t] = binvar;
1467  }
1468 
1469  /* add and release the set partitioning constraint */
1470  SCIP_CALL( SCIPaddCons(subscip, cons) );
1471  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1472  }
1473 
1474  /* adjusted the smallest earliest start time and the largest latest completion time with the effective horizon */
1475  hmin = MAX(hmin, minest);
1476  hmax = MIN(hmax, maxlct);
1477  assert(hmin > INT_MIN);
1478  assert(hmax < INT_MAX);
1479  assert(hmin < hmax);
1480 
1481  /* create for each time a knapsack constraint which ensures that the resource capacity is not exceeded */
1482  for( t = hmin; t < hmax; ++t )
1483  {
1484  SCIP_CONS* cons;
1485 
1486  /* construct constraint name */
1487  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "time_%d", t);
1488 
1489  /* create an empty knapsack constraint */
1490  SCIP_CALL( SCIPcreateConsBasicKnapsack(subscip, &cons, name, 0, NULL, NULL, (SCIP_Longint)capacity) );
1491 
1492  /* add all jobs which potentially can be processed at that time point */
1493  for( v = 0; v < njobs; ++v )
1494  {
1495  int duration;
1496  int demand;
1497  int start;
1498  int end;
1499  int est;
1500  int lst;
1501  int k;
1502 
1503  est = ests[v];
1504  lst = lsts[v] ;
1505 
1506  duration = durations[v];
1507  assert(duration > 0);
1508 
1509  /* check if the varibale is processed potentially at time point t */
1510  if( t < est || t >= lst + duration )
1511  continue;
1512 
1513  demand = demands[v];
1514  assert(demand >= 0);
1515 
1516  start = MAX(t - duration + 1, est);
1517  end = MIN(t, lst);
1518 
1519  assert(start <= end);
1520 
1521  for( k = start; k <= end; ++k )
1522  {
1523  assert(binvars[v][k] != NULL);
1524  SCIP_CALL( SCIPaddCoefKnapsack(subscip, cons, binvars[v][k], (SCIP_Longint) demand) );
1525  }
1526  }
1527 
1528  /* add and release the knapsack constraint */
1529  SCIP_CALL( SCIPaddCons(subscip, cons) );
1530  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1531  }
1532 
1533  /* do not abort subproblem on CTRL-C */
1534  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
1535 
1536  /* disable output to console */
1537  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1538 
1539  /* set limits for the subproblem */
1540  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", maxnodes) );
1541  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
1542  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
1543 
1544  /* solve single cumulative constraint by branch and bound */
1545  retcode = SCIPsolve(subscip);
1546 
1547  if( retcode != SCIP_OKAY )
1548  (*error) = TRUE;
1549  else
1550  {
1551  SCIPdebugMsg(scip, "solved single cumulative condition with status %d\n", SCIPgetStatus(subscip));
1552 
1553  /* evaluated solution status */
1554  switch( SCIPgetStatus(subscip) )
1555  {
1556  case SCIP_STATUS_INFORUNBD:
1558  (*infeasible) = TRUE;
1559  (*solved) = TRUE;
1560  break;
1561  case SCIP_STATUS_UNBOUNDED:
1562  (*unbounded) = TRUE;
1563  (*solved) = TRUE;
1564  break;
1565  case SCIP_STATUS_OPTIMAL:
1566  {
1567  SCIP_SOL* sol;
1568 
1569  sol = SCIPgetBestSol(subscip);
1570  assert(sol != NULL);
1571 
1572  for( v = 0; v < njobs; ++v )
1573  {
1574  int timeinterval;
1575  int est;
1576  int lst;
1577 
1578  est = ests[v];
1579  lst = lsts[v];
1580 
1581  /* compute number of possible start points */
1582  timeinterval = lst - est + 1;
1583 
1584  /* check which binary varibale is set to one */
1585  for( t = 0; t < timeinterval; ++t )
1586  {
1587  if( SCIPgetSolVal(subscip, sol, binvars[v][t]) > 0.5 )
1588  {
1589  ests[v] = est + t;
1590  lsts[v] = est + t;
1591  break;
1592  }
1593  }
1594  }
1595 
1596  (*solved) = TRUE;
1597  break;
1598  }
1599  case SCIP_STATUS_NODELIMIT:
1601  case SCIP_STATUS_TIMELIMIT:
1602  case SCIP_STATUS_MEMLIMIT:
1604  /* transfer the global bound changes */
1605  for( v = 0; v < njobs; ++v )
1606  {
1607  int timeinterval;
1608  int est;
1609  int lst;
1610 
1611  est = ests[v];
1612  lst = lsts[v];
1613 
1614  /* compute number of possible start points */
1615  timeinterval = lst - est + 1;
1616 
1617  /* check which binary varibale is the first binary varibale which is not globally fixed to zero */
1618  for( t = 0; t < timeinterval; ++t )
1619  {
1620  if( SCIPvarGetUbGlobal(binvars[v][t]) > 0.5 )
1621  {
1622  ests[v] = est + t;
1623  break;
1624  }
1625  }
1626 
1627  /* check which binary varibale is the last binary varibale which is not globally fixed to zero */
1628  for( t = timeinterval - 1; t >= 0; --t )
1629  {
1630  if( SCIPvarGetUbGlobal(binvars[v][t]) > 0.5 )
1631  {
1632  lsts[v] = est + t;
1633  break;
1634  }
1635  }
1636  }
1637  (*solved) = FALSE;
1638  break;
1639 
1640  case SCIP_STATUS_UNKNOWN:
1642  case SCIP_STATUS_GAPLIMIT:
1643  case SCIP_STATUS_SOLLIMIT:
1645  SCIPerrorMessage("invalid status code <%d>\n", SCIPgetStatus(subscip));
1646  return SCIP_INVALIDDATA;
1647  }
1648  }
1649 
1650  /* release all variables */
1651  for( v = 0; v < njobs; ++v )
1652  {
1653  int timeinterval;
1654  int est;
1655  int lst;
1656 
1657  est = ests[v];
1658  lst = lsts[v];
1659 
1660  /* compute number of possible start points */
1661  timeinterval = lst - est + 1;
1662 
1663  for( t = 0; t < timeinterval; ++t )
1664  {
1665  SCIP_CALL( SCIPreleaseVar(subscip, &binvars[v][t]) );
1666  }
1667  SCIPfreeBufferArray(subscip, &binvars[v]);
1668  }
1669 
1670  SCIPfreeBufferArray(subscip, &binvars);
1671 
1672  SCIP_CALL( SCIPfree(&subscip) );
1673 
1674  return SCIP_OKAY;
1675 }
1676 #endif
1677 
1678 /**@} */
1679 
1680 /**@name Constraint handler data
1681  *
1682  * Method used to create and free the constraint handler data when including and removing the cumulative constraint
1683  * handler.
1684  *
1685  * @{
1686  */
1687 
1688 /** creates constaint handler data for cumulative constraint handler */
1689 static
1691  SCIP* scip, /**< SCIP data structure */
1692  SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
1693  SCIP_EVENTHDLR* eventhdlr /**< event handler */
1694  )
1695 {
1696  /* create precedence constraint handler data */
1697  assert(scip != NULL);
1698  assert(conshdlrdata != NULL);
1699  assert(eventhdlr != NULL);
1700 
1701  SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
1702 
1703  /* set event handler for checking if bounds of start time variables are tighten */
1704  (*conshdlrdata)->eventhdlr = eventhdlr;
1705 
1706  /* set default methed for solving single cumulative conditions using SCIP and a CP model */
1707  (*conshdlrdata)->solveCumulative = solveCumulativeViaScipCp;
1708 
1709 #ifdef SCIP_STATISTIC
1710  (*conshdlrdata)->nlbtimetable = 0;
1711  (*conshdlrdata)->nubtimetable = 0;
1712  (*conshdlrdata)->ncutofftimetable = 0;
1713  (*conshdlrdata)->nlbedgefinder = 0;
1714  (*conshdlrdata)->nubedgefinder = 0;
1715  (*conshdlrdata)->ncutoffedgefinder = 0;
1716  (*conshdlrdata)->ncutoffoverload = 0;
1717  (*conshdlrdata)->ncutoffoverloadTTEF = 0;
1718 
1719  (*conshdlrdata)->nirrelevantjobs = 0;
1720  (*conshdlrdata)->nalwaysruns = 0;
1721  (*conshdlrdata)->nremovedlocks = 0;
1722  (*conshdlrdata)->ndualfixs = 0;
1723  (*conshdlrdata)->ndecomps = 0;
1724  (*conshdlrdata)->ndualbranchs = 0;
1725  (*conshdlrdata)->nallconsdualfixs = 0;
1726  (*conshdlrdata)->naddedvarbounds = 0;
1727  (*conshdlrdata)->naddeddisjunctives = 0;
1728 #endif
1729 
1730  return SCIP_OKAY;
1731 }
1732 
1733 /** frees constraint handler data for logic or constraint handler */
1734 static
1735 void conshdlrdataFree(
1736  SCIP* scip, /**< SCIP data structure */
1737  SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
1738  )
1739 {
1740  assert(conshdlrdata != NULL);
1741  assert(*conshdlrdata != NULL);
1742 
1743  SCIPfreeBlockMemory(scip, conshdlrdata);
1744 }
1745 
1746 /**@} */
1747 
1748 
1749 /**@name Constraint data methods
1750  *
1751  * @{
1752  */
1753 
1754 /** catches bound change events for all variables in transformed cumulative constraint */
1755 static
1757  SCIP* scip, /**< SCIP data structure */
1758  SCIP_CONSDATA* consdata, /**< cumulative constraint data */
1759  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
1760  )
1761 {
1762  int v;
1763 
1764  assert(scip != NULL);
1765  assert(consdata != NULL);
1766  assert(eventhdlr != NULL);
1767 
1768  /* catch event for every single variable */
1769  for( v = 0; v < consdata->nvars; ++v )
1770  {
1771  SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[v],
1772  SCIP_EVENTTYPE_BOUNDTIGHTENED, eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
1773  }
1774 
1775  return SCIP_OKAY;
1776 }
1777 
1778 /** drops events for variable at given position */
1779 static
1781  SCIP* scip, /**< SCIP data structure */
1782  SCIP_CONSDATA* consdata, /**< cumulative constraint data */
1783  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1784  int pos /**< array position of variable to catch bound change events for */
1785  )
1786 {
1787  assert(scip != NULL);
1788  assert(consdata != NULL);
1789  assert(eventhdlr != NULL);
1790  assert(0 <= pos && pos < consdata->nvars);
1791  assert(consdata->vars[pos] != NULL);
1792 
1793  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos],
1794  SCIP_EVENTTYPE_BOUNDTIGHTENED, eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
1795 
1796  return SCIP_OKAY;
1797 }
1798 
1799 /** drops bound change events for all variables in transformed linear constraint */
1800 static
1802  SCIP* scip, /**< SCIP data structure */
1803  SCIP_CONSDATA* consdata, /**< linear constraint data */
1804  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
1805  )
1806 {
1807  int v;
1808 
1809  assert(scip != NULL);
1810  assert(consdata != NULL);
1811 
1812  /* drop event of every single variable */
1813  for( v = 0; v < consdata->nvars; ++v )
1814  {
1815  SCIP_CALL( consdataDropEvents(scip, consdata, eventhdlr, v) );
1816  }
1817 
1818  return SCIP_OKAY;
1819 }
1820 
1821 /** initialize variable lock data structure */
1822 static
1823 void initializeLocks(
1824  SCIP_CONSDATA* consdata, /**< constraint data */
1825  SCIP_Bool locked /**< should the variable be locked? */
1826  )
1827 {
1828  int nvars;
1829  int v;
1830 
1831  nvars = consdata->nvars;
1832 
1833  /* initialize locking arrays */
1834  for( v = 0; v < nvars; ++v )
1835  {
1836  consdata->downlocks[v] = locked;
1837  consdata->uplocks[v] = locked;
1838  }
1839 }
1840 
1841 /** creates constraint data of cumulative constraint */
1842 static
1844  SCIP* scip, /**< SCIP data structure */
1845  SCIP_CONSDATA** consdata, /**< pointer to consdata */
1846  SCIP_VAR** vars, /**< array of integer variables */
1847  SCIP_CONS** linkingconss, /**< array of linking constraints for the integer variables, or NULL */
1848  int* durations, /**< array containing corresponding durations */
1849  int* demands, /**< array containing corresponding demands */
1850  int nvars, /**< number of variables */
1851  int capacity, /**< available cumulative capacity */
1852  int hmin, /**< left bound of time axis to be considered (including hmin) */
1853  int hmax, /**< right bound of time axis to be considered (not including hmax) */
1854  SCIP_Bool check /**< is the corresponding constraint a check constraint */
1855  )
1856 {
1857  int v;
1858 
1859  assert(scip != NULL);
1860  assert(consdata != NULL);
1861  assert(vars != NULL || nvars > 0);
1862  assert(demands != NULL);
1863  assert(durations != NULL);
1864  assert(capacity >= 0);
1865  assert(hmin >= 0);
1866  assert(hmin < hmax);
1867 
1868  /* create constraint data */
1869  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
1870 
1871  (*consdata)->hmin = hmin;
1872  (*consdata)->hmax = hmax;
1873 
1874  (*consdata)->capacity = capacity;
1875  (*consdata)->demandrows = NULL;
1876  (*consdata)->demandrowssize = 0;
1877  (*consdata)->ndemandrows = 0;
1878  (*consdata)->scoverrows = NULL;
1879  (*consdata)->nscoverrows = 0;
1880  (*consdata)->scoverrowssize = 0;
1881  (*consdata)->bcoverrows = NULL;
1882  (*consdata)->nbcoverrows = 0;
1883  (*consdata)->bcoverrowssize = 0;
1884  (*consdata)->nvars = nvars;
1885  (*consdata)->varssize = nvars;
1886  (*consdata)->signature = 0;
1887  (*consdata)->validsignature = FALSE;
1888  (*consdata)->normalized = FALSE;
1889  (*consdata)->covercuts = FALSE;
1890  (*consdata)->propagated = FALSE;
1891  (*consdata)->varbounds = FALSE;
1892  (*consdata)->triedsolving = FALSE;
1893 
1894  if( nvars > 0 )
1895  {
1896  assert(vars != NULL); /* for flexelint */
1897 
1898  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
1899  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->demands, demands, nvars) );
1900  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->durations, durations, nvars) );
1901  (*consdata)->linkingconss = NULL;
1902 
1903  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->downlocks, nvars) );
1904  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->uplocks, nvars) );
1905 
1906  /* initialize variable lock data structure; the locks are only used if the contraint is a check constraint */
1907  initializeLocks(*consdata, check);
1908 
1909  if( linkingconss != NULL )
1910  {
1911  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->linkingconss, linkingconss, nvars) );
1912  }
1913 
1914  /* transform variables, if they are not yet transformed */
1915  if( SCIPisTransformed(scip) )
1916  {
1917  SCIPdebugMsg(scip, "get tranformed variables and constraints\n");
1918 
1919  /* get transformed variables and do NOT captures these */
1920  SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
1921 
1922  /* multi-aggregated variables cannot be replaced by active variable; therefore we mark all variables for not
1923  * been multi-aggregated
1924  */
1925  for( v = 0; v < nvars; ++v )
1926  {
1927  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[v]) );
1928  }
1929 
1930  if( linkingconss != NULL )
1931  {
1932  /* get transformed constraints and captures these */
1933  SCIP_CALL( SCIPtransformConss(scip, (*consdata)->nvars, (*consdata)->linkingconss, (*consdata)->linkingconss) );
1934 
1935  for( v = 0; v < nvars; ++v )
1936  assert(SCIPgetConsLinking(scip, (*consdata)->vars[v]) == (*consdata)->linkingconss[v]);
1937  }
1938  }
1939  }
1940  else
1941  {
1942  (*consdata)->vars = NULL;
1943  (*consdata)->downlocks = NULL;
1944  (*consdata)->uplocks = NULL;
1945  (*consdata)->demands = NULL;
1946  (*consdata)->durations = NULL;
1947  (*consdata)->linkingconss = NULL;
1948  }
1949 
1950  /* initialize values for running propagation algorithms efficiently */
1951  (*consdata)->resstrength1 = -1.0;
1952  (*consdata)->resstrength2 = -1.0;
1953  (*consdata)->cumfactor1 = -1.0;
1954  (*consdata)->disjfactor1 = -1.0;
1955  (*consdata)->disjfactor2 = -1.0;
1956  (*consdata)->estimatedstrength = -1.0;
1957 
1958  SCIPstatistic( (*consdata)->maxpeak = -1 );
1959 
1960  return SCIP_OKAY;
1961 }
1962 
1963 /** releases LP rows of constraint data and frees rows array */
1964 static
1966  SCIP* scip, /**< SCIP data structure */
1967  SCIP_CONSDATA** consdata /**< constraint data */
1968  )
1969 {
1970  int r;
1971 
1972  assert(consdata != NULL);
1973  assert(*consdata != NULL);
1974 
1975  for( r = 0; r < (*consdata)->ndemandrows; ++r )
1976  {
1977  assert((*consdata)->demandrows[r] != NULL);
1978  SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->demandrows[r]) );
1979  }
1980 
1981  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->demandrows, (*consdata)->demandrowssize);
1982 
1983  (*consdata)->ndemandrows = 0;
1984  (*consdata)->demandrowssize = 0;
1985 
1986  /* free rows of cover cuts */
1987  for( r = 0; r < (*consdata)->nscoverrows; ++r )
1988  {
1989  assert((*consdata)->scoverrows[r] != NULL);
1990  SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->scoverrows[r]) );
1991  }
1992 
1993  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->scoverrows, (*consdata)->scoverrowssize);
1994 
1995  (*consdata)->nscoverrows = 0;
1996  (*consdata)->scoverrowssize = 0;
1997 
1998  for( r = 0; r < (*consdata)->nbcoverrows; ++r )
1999  {
2000  assert((*consdata)->bcoverrows[r] != NULL);
2001  SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->bcoverrows[r]) );
2002  }
2003 
2004  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->bcoverrows, (*consdata)->bcoverrowssize);
2005 
2006  (*consdata)->nbcoverrows = 0;
2007  (*consdata)->bcoverrowssize = 0;
2008 
2009  (*consdata)->covercuts = FALSE;
2010 
2011  return SCIP_OKAY;
2012 }
2013 
2014 /** frees a cumulative constraint data */
2015 static
2017  SCIP* scip, /**< SCIP data structure */
2018  SCIP_CONSDATA** consdata /**< pointer to linear constraint data */
2019  )
2020 {
2021  int varssize;
2022  int nvars;
2023 
2024  assert(consdata != NULL);
2025  assert(*consdata != NULL);
2026 
2027  nvars = (*consdata)->nvars;
2028  varssize = (*consdata)->varssize;
2029 
2030  if( varssize > 0 )
2031  {
2032  int v;
2033 
2034  /* release and free the rows */
2035  SCIP_CALL( consdataFreeRows(scip, consdata) );
2036 
2037  /* release the linking constraints if they were generated */
2038  if( (*consdata)->linkingconss != NULL )
2039  {
2040  for( v = nvars-1; v >= 0; --v )
2041  {
2042  assert((*consdata)->linkingconss[v] != NULL );
2043  SCIP_CALL( SCIPreleaseCons(scip, &(*consdata)->linkingconss[v]) );
2044  }
2045 
2046  SCIPfreeBlockMemoryArray(scip, &(*consdata)->linkingconss, varssize);
2047  }
2048 
2049  /* free arrays */
2050  SCIPfreeBlockMemoryArray(scip, &(*consdata)->downlocks, varssize);
2051  SCIPfreeBlockMemoryArray(scip, &(*consdata)->uplocks, varssize);
2052  SCIPfreeBlockMemoryArray(scip, &(*consdata)->durations, varssize);
2053  SCIPfreeBlockMemoryArray(scip, &(*consdata)->demands, varssize);
2054  SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, varssize);
2055  }
2056 
2057  /* free memory */
2058  SCIPfreeBlockMemory(scip, consdata);
2059 
2060  return SCIP_OKAY;
2061 }
2062 
2063 /** prints cumulative constraint to file stream */
2064 static
2065 void consdataPrint(
2066  SCIP* scip, /**< SCIP data structure */
2067  SCIP_CONSDATA* consdata, /**< cumulative constraint data */
2068  FILE* file /**< output file (or NULL for standard output) */
2069  )
2070 {
2071  int v;
2072 
2073  assert(consdata != NULL);
2074 
2075  /* print coefficients */
2076  SCIPinfoMessage( scip, file, "cumulative(");
2077 
2078  for( v = 0; v < consdata->nvars; ++v )
2079  {
2080  assert(consdata->vars[v] != NULL);
2081  if( v > 0 )
2082  SCIPinfoMessage(scip, file, ", ");
2083  SCIPinfoMessage(scip, file, "<%s>[%g,%g](%d)[%d]", SCIPvarGetName(consdata->vars[v]),
2084  SCIPvarGetLbGlobal(consdata->vars[v]), SCIPvarGetUbGlobal(consdata->vars[v]),
2085  consdata->durations[v], consdata->demands[v]);
2086  }
2087  SCIPinfoMessage(scip, file, ")[%d,%d) <= %d", consdata->hmin, consdata->hmax, consdata->capacity);
2088 }
2089 
2090 /** deletes coefficient at given position from constraint data */
2091 static
2093  SCIP* scip, /**< SCIP data structure */
2094  SCIP_CONSDATA* consdata, /**< cumulative constraint data */
2095  SCIP_CONS* cons, /**< knapsack constraint */
2096  int pos /**< position of coefficient to delete */
2097  )
2098 {
2099  SCIP_CONSHDLR* conshdlr;
2100  SCIP_CONSHDLRDATA* conshdlrdata;
2101 
2102  assert(scip != NULL);
2103  assert(consdata != NULL);
2104  assert(cons != NULL);
2105  assert(SCIPconsIsTransformed(cons));
2106  assert(!SCIPinProbing(scip));
2107 
2108  SCIPdebugMsg(scip, "cumulative constraint <%s>: remove variable <%s>\n",
2109  SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[pos]));
2110 
2111  /* remove the rounding locks for the deleted variable */
2112  SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, consdata->downlocks[pos], consdata->uplocks[pos]) );
2113 
2114  consdata->downlocks[pos] = FALSE;
2115  consdata->uplocks[pos] = FALSE;
2116 
2117  if( consdata->linkingconss != NULL )
2118  {
2119  SCIP_CALL( SCIPreleaseCons(scip, &consdata->linkingconss[pos]) );
2120  }
2121 
2122  /* get event handler */
2123  conshdlr = SCIPconsGetHdlr(cons);
2124  assert(conshdlr != NULL);
2125  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2126  assert(conshdlrdata != NULL);
2127  assert(conshdlrdata->eventhdlr != NULL);
2128 
2129  /* drop events */
2130  SCIP_CALL( consdataDropEvents(scip, consdata, conshdlrdata->eventhdlr, pos) );
2131 
2132  SCIPdebugMsg(scip, "remove variable <%s>[%g,%g] from cumulative constraint <%s>\n",
2133  SCIPvarGetName(consdata->vars[pos]), SCIPvarGetLbGlobal(consdata->vars[pos]), SCIPvarGetUbGlobal(consdata->vars[pos]), SCIPconsGetName(cons));
2134 
2135 
2136  /* in case the we did not remove the variable in the last slot of the arrays we move the current last to this
2137  * position
2138  */
2139  if( pos != consdata->nvars - 1 )
2140  {
2141  consdata->vars[pos] = consdata->vars[consdata->nvars-1];
2142  consdata->downlocks[pos] = consdata->downlocks[consdata->nvars-1];
2143  consdata->uplocks[pos] = consdata->uplocks[consdata->nvars-1];
2144  consdata->demands[pos] = consdata->demands[consdata->nvars-1];
2145  consdata->durations[pos] = consdata->durations[consdata->nvars-1];
2146 
2147  if( consdata->linkingconss != NULL )
2148  {
2149  consdata->linkingconss[pos]= consdata->linkingconss[consdata->nvars-1];
2150  }
2151  }
2152 
2153  consdata->nvars--;
2154  consdata->validsignature = FALSE;
2155  consdata->normalized = FALSE;
2156 
2157  return SCIP_OKAY;
2158 }
2159 
2160 /** collect linking constraints for each integer variable */
2161 static
2163  SCIP* scip, /**< SCIP data structure */
2164  SCIP_CONSDATA* consdata /**< pointer to consdata */
2165  )
2166 {
2167  int nvars;
2168  int v;
2169 
2170  assert(scip != NULL);
2171  assert(consdata != NULL);
2172 
2173  nvars = consdata->nvars;
2174  assert(nvars > 0);
2175  assert(consdata->linkingconss == NULL);
2176 
2177  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->linkingconss, consdata->varssize) );
2178 
2179  for( v = 0; v < nvars; ++v )
2180  {
2181  SCIP_CONS* cons;
2182  SCIP_VAR* var;
2183 
2184  var = consdata->vars[v];
2185  assert(var != NULL);
2186 
2187  SCIPdebugMsg(scip, "linking constraint (%d of %d) for variable <%s>\n", v+1, nvars, SCIPvarGetName(var));
2188 
2189  /* create linking constraint if it does not exist yet */
2190  if( !SCIPexistsConsLinking(scip, var) )
2191  {
2192  char name[SCIP_MAXSTRLEN];
2193 
2194  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "link(%s)", SCIPvarGetName(var));
2195 
2196  /* creates and captures an linking constraint */
2197  SCIP_CALL( SCIPcreateConsLinking(scip, &cons, name, var, NULL, 0, 0,
2198  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE /*TRUE*/, FALSE) );
2199  SCIP_CALL( SCIPaddCons(scip, cons) );
2200  consdata->linkingconss[v] = cons;
2201  }
2202  else
2203  {
2204  consdata->linkingconss[v] = SCIPgetConsLinking(scip, var);
2205  SCIP_CALL( SCIPcaptureCons(scip, consdata->linkingconss[v]) );
2206  }
2207 
2208  assert(SCIPexistsConsLinking(scip, var));
2209  assert(consdata->linkingconss[v] != NULL);
2210  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(consdata->linkingconss[v])), "linking") == 0 );
2211  assert(SCIPgetConsLinking(scip, var) == consdata->linkingconss[v]);
2212  }
2213 
2214  return SCIP_OKAY;
2215 }
2216 
2217 /**@} */
2218 
2219 
2220 /**@name Check methods
2221  *
2222  * @{
2223  */
2224 
2225 /** check for the given starting time variables with their demands and durations if the cumulative conditions for the
2226  * given solution is satisfied
2227  */
2228 static
2230  SCIP* scip, /**< SCIP data structure */
2231  SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
2232  int nvars, /**< number of variables (jobs) */
2233  SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
2234  int* durations, /**< array containing corresponding durations */
2235  int* demands, /**< array containing corresponding demands */
2236  int capacity, /**< available cumulative capacity */
2237  int hmin, /**< left bound of time axis to be considered (including hmin) */
2238  int hmax, /**< right bound of time axis to be considered (not including hmax) */
2239  SCIP_Bool* violated, /**< pointer to store if the cumulative condition is violated */
2240  SCIP_CONS* cons, /**< constraint which is checked */
2241  SCIP_Bool printreason /**< should the reason for the violation be printed? */
2242  )
2243 {
2244  int* startsolvalues; /* stores when each job is starting */
2245  int* endsolvalues; /* stores when each job ends */
2246  int* startindices; /* we will sort the startsolvalues, thus we need to know which index of a job it corresponds to */
2247  int* endindices; /* we will sort the endsolvalues, thus we need to know which index of a job it corresponds to */
2248 
2249  int freecapacity;
2250  int curtime; /* point in time which we are just checking */
2251  int endindex; /* index of endsolvalues with: endsolvalues[endindex] > curtime */
2252  int j;
2253 
2254  assert(scip != NULL);
2255  assert(violated != NULL);
2256 
2257  (*violated) = FALSE;
2258 
2259  if( nvars == 0 )
2260  return SCIP_OKAY;
2261 
2262  assert(vars != NULL);
2263  assert(demands != NULL);
2264  assert(durations != NULL);
2265 
2266  /* compute time points where we have to check whether capacity constraint is infeasible or not */
2267  SCIP_CALL( SCIPallocBufferArray(scip, &startsolvalues, nvars) );
2268  SCIP_CALL( SCIPallocBufferArray(scip, &endsolvalues, nvars) );
2269  SCIP_CALL( SCIPallocBufferArray(scip, &startindices, nvars) );
2270  SCIP_CALL( SCIPallocBufferArray(scip, &endindices, nvars) );
2271 
2272  /* assign variables, start and endpoints to arrays */
2273  for ( j = 0; j < nvars; ++j )
2274  {
2275  int solvalue;
2276 
2277  /* the constraint of the cumulative constraint handler should be called after the integrality check */
2278  assert(SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars[j])));
2279 
2280  solvalue = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, vars[j]));
2281 
2282  /* we need to ensure that we check at least one time point during the effective horizon; therefore we project all
2283  * jobs which start before hmin to hmin
2284  */
2285  startsolvalues[j] = MAX(solvalue, hmin);
2286  startindices[j] = j;
2287 
2288  endsolvalues[j] = MAX(solvalue + durations[j], hmin);
2289  endindices[j] = j;
2290  }
2291 
2292  /* sort the arrays not-decreasing according to start solution values and end solution values (and sort the
2293  * corresponding indices in the same way)
2294  */
2295  SCIPsortIntInt(startsolvalues, startindices, nvars);
2296  SCIPsortIntInt(endsolvalues, endindices, nvars);
2297 
2298  endindex = 0;
2299  freecapacity = capacity;
2300 
2301  /* check each start point of a job whether the capacity is kept or not */
2302  for( j = 0; j < nvars; ++j )
2303  {
2304  /* only check intervals [hmin,hmax) */
2305  curtime = startsolvalues[j];
2306 
2307  if( curtime >= hmax )
2308  break;
2309 
2310  /* subtract all capacity needed up to this point */
2311  freecapacity -= demands[startindices[j]];
2312  while( j+1 < nvars && startsolvalues[j+1] == curtime )
2313  {
2314  j++;
2315  freecapacity -= demands[startindices[j]];
2316  }
2317 
2318  /* free all capacity usages of jobs that are no longer running */
2319  while( endindex < nvars && curtime >= endsolvalues[endindex] )
2320  {
2321  freecapacity += demands[endindices[endindex]];
2322  ++endindex;
2323  }
2324  assert(freecapacity <= capacity);
2325 
2326  /* check freecapacity to be smaller than zero */
2327  if( freecapacity < 0 && curtime >= hmin )
2328  {
2329  SCIPdebugMsg(scip, "freecapacity = %3d\n", freecapacity);
2330  (*violated) = TRUE;
2331 
2332  if( printreason )
2333  {
2334  int i;
2335 
2336  /* first state the violated constraints */
2337  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2338 
2339  /* second state the reason */
2340  SCIPinfoMessage(scip, NULL,
2341  ";\nviolation: at time point %d available capacity = %d, needed capacity = %d\n",
2342  curtime, capacity, capacity - freecapacity);
2343 
2344  for( i = 0; i <= j; ++i )
2345  {
2346  if( startsolvalues[i] + durations[startindices[i]] > curtime )
2347  {
2348  SCIPinfoMessage(scip, NULL, "activity %s, start = %i, duration = %d, demand = %d \n",
2349  SCIPvarGetName(vars[startindices[i]]), startsolvalues[i], durations[startindices[i]],
2350  demands[startindices[i]]);
2351  }
2352  }
2353  }
2354  break;
2355  }
2356  } /*lint --e{850}*/
2357 
2358  /* free all buffer arrays */
2359  SCIPfreeBufferArray(scip, &endindices);
2360  SCIPfreeBufferArray(scip, &startindices);
2361  SCIPfreeBufferArray(scip, &endsolvalues);
2362  SCIPfreeBufferArray(scip, &startsolvalues);
2363 
2364  return SCIP_OKAY;
2365 }
2366 
2367 /** check if the given constrait is valid; checks each starting point of a job whether the remaining capacity is at
2368  * least zero or not. If not (*violated) is set to TRUE
2369  */
2370 static
2372  SCIP* scip, /**< SCIP data structure */
2373  SCIP_CONS* cons, /**< constraint to be checked */
2374  SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
2375  SCIP_Bool* violated, /**< pointer to store if the constraint is violated */
2376  SCIP_Bool printreason /**< should the reason for the violation be printed? */
2377  )
2378 {
2379  SCIP_CONSDATA* consdata;
2380 
2381  assert(scip != NULL);
2382  assert(cons != NULL);
2383  assert(violated != NULL);
2384 
2385  SCIPdebugMsg(scip, "check cumulative constraints <%s>\n", SCIPconsGetName(cons));
2386 
2387  consdata = SCIPconsGetData(cons);
2388  assert(consdata != NULL);
2389 
2390  /* check the cumulative condition */
2391  SCIP_CALL( checkCumulativeCondition(scip, sol, consdata->nvars, consdata->vars,
2392  consdata->durations, consdata->demands, consdata->capacity, consdata->hmin, consdata->hmax,
2393  violated, cons, printreason) );
2394 
2395  return SCIP_OKAY;
2396 }
2397 
2398 /**@} */
2399 
2400 /**@name Conflict analysis
2401  *
2402  * @{
2403  */
2404 
2405 /** resolves the propagation of the core time algorithm */
2406 static
2408  SCIP* scip, /**< SCIP data structure */
2409  int nvars, /**< number of start time variables (activities) */
2410  SCIP_VAR** vars, /**< array of start time variables */
2411  int* durations, /**< array of durations */
2412  int* demands, /**< array of demands */
2413  int capacity, /**< cumulative capacity */
2414  int hmin, /**< left bound of time axis to be considered (including hmin) */
2415  int hmax, /**< right bound of time axis to be considered (not including hmax) */
2416  SCIP_VAR* infervar, /**< inference variable */
2417  int inferdemand, /**< demand of the inference variable */
2418  int inferpeak, /**< time point which causes the propagation */
2419  int relaxedpeak, /**< relaxed time point which would be sufficient to be proved */
2420  SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2421  SCIP_Bool usebdwidening, /**< should bound widening be used during conflict analysis? */
2422  int* provedpeak, /**< pointer to store the actually proved peak, or NULL */
2423  SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2424  )
2425 {
2426  SCIP_VAR* var;
2427  SCIP_Bool* reported;
2428  int duration;
2429  int maxlst;
2430  int minect;
2431  int ect;
2432  int lst;
2433  int j;
2434 
2435  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip));
2436 
2437  SCIPdebugMsg(scip, "variable <%s>: (demand %d) resolve propagation of core time algorithm (peak %d)\n",
2438  SCIPvarGetName(infervar), inferdemand, inferpeak);
2439  assert(nvars > 0);
2440 
2441  /* adjusted capacity */
2442  capacity -= inferdemand;
2443  maxlst = INT_MIN;
2444  minect = INT_MAX;
2445 
2446  SCIP_CALL( SCIPallocBufferArray(scip, &reported, nvars) );
2447  BMSclearMemoryArray(reported, nvars);
2448 
2449  /* first we loop over all variables and adjust the capacity with those jobs which provide a global core at the
2450  * inference peak and those where the current conflict bounds provide a core at the inference peak
2451  */
2452  for( j = 0; j < nvars && capacity >= 0; ++j )
2453  {
2454  var = vars[j];
2455  assert(var != NULL);
2456 
2457  /* skip inference variable */
2458  if( var == infervar )
2459  continue;
2460 
2461  duration = durations[j];
2462  assert(duration > 0);
2463 
2464  /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */
2465  assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)));
2466  assert(SCIPisFeasIntegral(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE)));
2467  assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)));
2468  assert(SCIPisFeasIntegral(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE)));
2469 
2470  SCIPdebugMsg(scip, "variable <%s>: glb=[%g,%g] conflict=[%g,%g] (duration %d, demand %d)\n",
2472  SCIPgetConflictVarLb(scip, var), SCIPgetConflictVarUb(scip, var), duration, demands[j]);
2473 
2474  ect = SCIPconvertRealToInt(scip, SCIPvarGetLbGlobal(var)) + duration;
2475  lst = SCIPconvertRealToInt(scip, SCIPvarGetUbGlobal(var));
2476 
2477  /* check if the inference peak is part of the global bound core; if so we decreasing the capacity by the demand of
2478  * that job without adding it the explanation
2479  */
2480  if( inferpeak < ect && lst <= inferpeak )
2481  {
2482  capacity -= demands[j];
2483  reported[j] = TRUE;
2484 
2485  maxlst = MAX(maxlst, lst);
2486  minect = MIN(minect, ect);
2487  assert(maxlst < minect);
2488 
2489  if( explanation != NULL )
2490  explanation[j] = TRUE;
2491 
2492  continue;
2493  }
2494 
2495  /* collect the conflict bound core (the conflict bounds are those bounds which are already part of the conflict)
2496  * hence these bound are already reported by other resolve propation steps. In case a bound (lower or upper) is
2497  * not part of the conflict yet we get the global bounds back.
2498  */
2499  ect = SCIPconvertRealToInt(scip, SCIPgetConflictVarLb(scip, var)) + duration;
2500  lst = SCIPconvertRealToInt(scip, SCIPgetConflictVarUb(scip, var));
2501 
2502  /* check if the inference peak is part of the conflict bound core; if so we decreasing the capacity by the demand
2503  * of that job without and collect the job as part of the explanation
2504  *
2505  * @note we do not need to reported that job to SCIP since the required bounds are already reported
2506  */
2507  if( inferpeak < ect && lst <= inferpeak )
2508  {
2509  capacity -= demands[j];
2510  reported[j] = TRUE;
2511 
2512  maxlst = MAX(maxlst, lst);
2513  minect = MIN(minect, ect);
2514  assert(maxlst < minect);
2515 
2516  if( explanation != NULL )
2517  explanation[j] = TRUE;
2518  }
2519  }
2520 
2521  if( capacity >= 0 )
2522  {
2523  int* cands;
2524  int* canddemands;
2525  int ncands;
2526  int c;
2527 
2528  SCIP_CALL( SCIPallocBufferArray(scip, &cands, nvars) );
2529  SCIP_CALL( SCIPallocBufferArray(scip, &canddemands, nvars) );
2530  ncands = 0;
2531 
2532  /* collect all cores of the variables which lay in the considered time window except the inference variable */
2533  for( j = 0; j < nvars; ++j )
2534  {
2535  var = vars[j];
2536  assert(var != NULL);
2537 
2538  /* skip inference variable */
2539  if( var == infervar || reported[j] )
2540  continue;
2541 
2542  duration = durations[j];
2543  assert(duration > 0);
2544 
2545  /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */
2546  assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)));
2547  assert(SCIPisFeasIntegral(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE)));
2548  assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)));
2549  assert(SCIPisFeasIntegral(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE)));
2550 
2551  /* collect local core information */
2552  ect = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) + duration;
2553  lst = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
2554 
2555  SCIPdebugMsg(scip, "variable <%s>: loc=[%g,%g] glb=[%g,%g] (duration %d, demand %d)\n",
2556  SCIPvarGetName(var), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE),
2557  SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), duration, demands[j]);
2558 
2559  /* check if the inference peak is part of the core */
2560  if( inferpeak < ect && lst <= inferpeak )
2561  {
2562  cands[ncands] = j;
2563  canddemands[ncands] = demands[j];
2564  ncands++;
2565 
2566  capacity -= demands[j];
2567  }
2568  }
2569 
2570  /* sort candidates indices w.r.t. their demands */
2571  SCIPsortDownIntInt(canddemands, cands, ncands);
2572 
2573  assert(capacity < 0);
2574  assert(ncands > 0);
2575 
2576  /* greedily remove candidates form the list such that the needed capacity is still exceeded */
2577  while( capacity + canddemands[ncands-1] < 0 )
2578  {
2579  ncands--;
2580  capacity += canddemands[ncands];
2581  assert(ncands > 0);
2582  }
2583 
2584  /* compute the size (number of time steps) of the job cores */
2585  for( c = 0; c < ncands; ++c )
2586  {
2587  var = vars[cands[c]];
2588  assert(var != NULL);
2589 
2590  duration = durations[cands[c]];
2591 
2592  ect = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) + duration;
2593  lst = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
2594 
2595  maxlst = MAX(maxlst, lst);
2596  minect = MIN(minect, ect);
2597  assert(maxlst < minect);
2598  }
2599 
2600  SCIPdebugMsg(scip, "infer peak %d, relaxed peak %d, lst %d, ect %d\n", inferpeak, relaxedpeak, maxlst, minect);
2601  assert(inferpeak >= maxlst);
2602  assert(inferpeak < minect);
2603 
2604  /* check if the collect variable are sufficient to prove the relaxed bound (relaxedpeak) */
2605  if( relaxedpeak < inferpeak )
2606  {
2607  inferpeak = MAX(maxlst, relaxedpeak);
2608  }
2609  else if( relaxedpeak > inferpeak )
2610  {
2611  inferpeak = MIN(minect-1, relaxedpeak);
2612  }
2613  assert(inferpeak >= hmin);
2614  assert(inferpeak < hmax);
2615  assert(inferpeak >= maxlst);
2616  assert(inferpeak < minect);
2617 
2618  /* post all necessary bound changes */
2619  for( c = 0; c < ncands; ++c )
2620  {
2621  var = vars[cands[c]];
2622  assert(var != NULL);
2623 
2624  if( usebdwidening )
2625  {
2626  duration = durations[cands[c]];
2627 
2628  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(inferpeak - duration + 1)) );
2629  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, (SCIP_Real)inferpeak) );
2630  }
2631  else
2632  {
2633  SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
2634  SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
2635  }
2636 
2637  if( explanation != NULL )
2638  explanation[cands[c]] = TRUE;
2639  }
2640 
2641  SCIPfreeBufferArray(scip, &canddemands);
2642  SCIPfreeBufferArray(scip, &cands);
2643  }
2644 
2645  SCIPfreeBufferArray(scip, &reported);
2646 
2647  if( provedpeak != NULL )
2648  *provedpeak = inferpeak;
2649 
2650  return SCIP_OKAY;
2651 }
2652 
2653 #if 0
2654 /** repropagation of edge finding algorithm simplified version from Petr Vilim only a small subset is reported such that
2655  * energy in total and for bound change is enough
2656  */
2657 static
2658 SCIP_RETCODE resolvePropagationEdgeFinding(
2659  SCIP* scip, /**< SCIP data structure */
2660  int nvars, /**< number of start time variables (activities) */
2661  SCIP_VAR** vars, /**< array of start time variables */
2662  int* durations, /**< array of durations */
2663  int hmin, /**< left bound of time axis to be considered (including hmin) */
2664  int hmax, /**< right bound of time axis to be considered (not including hmax) */
2665  SCIP_VAR* infervar, /**< variable whose bound change is to be explained */
2666  INFERINFO inferinfo, /**< inference info containing position of correct bdchgids */
2667  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
2668  SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2669  SCIP_Bool usebdwidening, /**< should bound widening be used during conflict analysis? */
2670  SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2671  )
2672 {
2673  int est;
2674  int lct;
2675  int j;
2676 
2677  /* ???????????????????? do bound widening */
2678 
2679  assert(scip != NULL);
2680  assert(nvars > 0);
2681  assert(inferInfoGetProprule(inferinfo) == PROPRULE_2_EDGEFINDING);
2682 
2683  SCIPdebugMsg(scip, "repropagate edge-finding with short reasons for variable <%s>\n", SCIPvarGetName(infervar));
2684 
2685  if( boundtype == SCIP_BOUNDTYPE_LOWER )
2686  {
2687  SCIP_CALL( SCIPaddConflictLb(scip, infervar, bdchgidx) );
2688  }
2689  else
2690  {
2691  SCIP_CALL( SCIPaddConflictUb(scip, infervar, bdchgidx) );
2692  }
2693 
2694  est = inferInfoGetData1(inferinfo);
2695  lct = inferInfoGetData2(inferinfo);
2696  assert(est < lct);
2697 
2698  /* collect the energies of all variables in [est_omega, lct_omega] */
2699  for( j = 0; j < nvars; ++j )
2700  {
2701  SCIP_VAR* var;
2702  SCIP_Bool left;
2703  SCIP_Bool right;
2704  int duration;
2705  int lb;
2706  int ub;
2707 
2708  var = vars[j];
2709  assert(var != NULL);
2710 
2711  if( var == infervar )
2712  {
2713  if( explanation != NULL )
2714  explanation[j] = TRUE;
2715 
2716  continue;
2717  }
2718 
2719  lb = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE));
2720  ub = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
2721 
2722  duration = durations[j];
2723  assert(duration > 0);
2724 
2725  /* in case the earliest start time is equal to hmin we have to also consider the jobs which run in that region
2726  * since we use adjusted jobs during the propagation
2727  */
2728  left = (est == hmin && lb + duration > hmin) || lb >= est;
2729 
2730  /* in case the latest completion time is equal to hmax we have to also consider the jobs which run in that region
2731  * since we use adjusted jobs during the propagation
2732  */
2733  right = (lct == hmax && ub < hmax) || ub + duration <= lct;
2734 
2735  /* store all jobs running in [est_omega; lct_omega] */
2736  if( left && right )
2737  {
2738  /* check if bound widening should be used */
2739  if( usebdwidening )
2740  {
2741  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(lct - duration)) );
2742  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, (SCIP_Real)(est)) );
2743  }
2744  else
2745  {
2746  SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
2747  SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
2748  }
2749 
2750  if( explanation != NULL )
2751  explanation[j] = TRUE;
2752  }
2753  }
2754 
2755  return SCIP_OKAY;
2756 }
2757 #endif
2758 
2759 /** compute the minimum overlaps w.r.t. the duration of the job and the time window [begin,end) */
2760 static
2761 int computeOverlap(
2762  int begin, /**< begin of the times interval */
2763  int end, /**< end of time interval */
2764  int est, /**< earliest start time */
2765  int lst, /**< latest start time */
2766  int duration /**< duration of the job */
2767  )
2768 {
2769  int left;
2770  int right;
2771  int ect;
2772  int lct;
2773 
2774  ect = est + duration;
2775  lct = lst + duration;
2776 
2777  /* check if job runs completely within [begin,end) */
2778  if( lct <= end && est >= begin )
2779  return duration;
2780 
2781  assert(lst <= end && ect >= begin);
2782 
2783  left = ect - begin;
2784  assert(left > 0);
2785 
2786  right = end - lst;
2787  assert(right > 0);
2788 
2789  return MIN3(left, right, end - begin);
2790 }
2791 
2792 /** an overload was detected due to the time-time edge-finding propagate; initialized conflict analysis, add an initial
2793  * reason
2794  *
2795  * @note the conflict analysis is not performend, only the initialized SCIP_Bool pointer is set to TRUE
2796  */
2797 static
2799  SCIP* scip, /**< SCIP data structure */
2800  int nvars, /**< number of start time variables (activities) */
2801  SCIP_VAR** vars, /**< array of start time variables */
2802  int* durations, /**< array of durations */
2803  int* demands, /**< array of demands */
2804  int capacity, /**< capacity of the cumulative condition */
2805  int begin, /**< begin of the time window */
2806  int end, /**< end of the time window */
2807  SCIP_VAR* infervar, /**< variable which was propagate, or NULL */
2808  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
2809  SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2810  SCIP_Real relaxedbd, /**< the relaxed bound which is sufficient to be explained */
2811  SCIP_Bool usebdwidening, /**< should bound widening be used during conflict analysis? */
2812  SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2813  )
2814 {
2815  int* locenergies;
2816  int* overlaps;
2817  int* idxs;
2818 
2819  int requiredenergy;
2820  int v;
2821 
2822  SCIP_CALL( SCIPallocBufferArray(scip, &locenergies, nvars) );
2823  SCIP_CALL( SCIPallocBufferArray(scip, &overlaps, nvars) );
2824  SCIP_CALL( SCIPallocBufferArray(scip, &idxs, nvars) );
2825 
2826  /* energy which needs be explained */
2827  requiredenergy = (end - begin) * capacity;
2828 
2829  SCIPdebugMsg(scip, "analysis energy load in [%d,%d) (capacity %d, energy %d)\n", begin, end, capacity, requiredenergy);
2830 
2831  /* collect global contribution and adjusted the required energy by the amount of energy the inference variable
2832  * takes
2833  */
2834  for( v = 0; v < nvars; ++v )
2835  {
2836  SCIP_VAR* var;
2837  int glbenergy;
2838  int duration;
2839  int demand;
2840  int est;
2841  int lst;
2842 
2843  var = vars[v];
2844  assert(var != NULL);
2845 
2846  locenergies[v] = 0;
2847  overlaps[v] = 0;
2848  idxs[v] = v;
2849 
2850  demand = demands[v];
2851  assert(demand > 0);
2852 
2853  duration = durations[v];
2854  assert(duration > 0);
2855 
2856  /* check if the variable equals the inference variable (the one which was propagated) */
2857  if( infervar == var )
2858  {
2859  int overlap;
2860  int right;
2861  int left;
2862 
2863  assert(relaxedbd != SCIP_UNKNOWN); /*lint !e777*/
2864 
2865  SCIPdebugMsg(scip, "inference variable <%s>[%g,%g] %s %g (duration %d, demand %d)\n",
2866  SCIPvarGetName(var), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE),
2867  boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", relaxedbd, duration, demand);
2868 
2869  /* compute the amount of energy which needs to be available for enforcing the propagation and report the bound
2870  * which is necessary from the inference variable
2871  */
2872  if( boundtype == SCIP_BOUNDTYPE_UPPER )
2873  {
2874  int lct;
2875 
2876  /* get the latest start time of the infer start time variable before the propagation took place */
2877  lst = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
2878 
2879  /* the latest start time of the inference start time variable before the propagation needs to be smaller as
2880  * the end of the time interval; meaning the job needs be overlap with the time interval in case the job is
2881  * scheduled w.r.t. its latest start time
2882  */
2883  assert(lst < end);
2884 
2885  /* compute the overlap of the job in case it would be scheduled w.r.t. its latest start time and the time
2886  * interval (before the propagation)
2887  */
2888  right = MIN3(end - lst, end - begin, duration);
2889 
2890  /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */
2891  assert(right > 0);
2892 
2893  lct = SCIPconvertRealToInt(scip, relaxedbd) + duration;
2894  assert(begin <= lct);
2895  assert(bdchgidx == NULL || SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE)) < begin);
2896 
2897  /* compute the overlap of the job after the propagation but considering the relaxed bound */
2898  left = MIN(lct - begin + 1, end - begin);
2899  assert(left > 0);
2900 
2901  /* compute the minimum overlap; */
2902  overlap = MIN(left, right);
2903  assert(overlap > 0);
2904  assert(overlap <= end - begin);
2905  assert(overlap <= duration);
2906 
2907  if( usebdwidening )
2908  {
2909  assert(SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)) <= (end - overlap));
2910  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, (SCIP_Real)(end - overlap)) );
2911  }
2912  else
2913  {
2914  SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
2915  }
2916  }
2917  else
2918  {
2919  int ect;
2920 
2921  assert(boundtype == SCIP_BOUNDTYPE_LOWER);
2922 
2923  /* get the earliest completion time of the infer start time variable before the propagation took place */
2924  ect = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) + duration;
2925 
2926  /* the earliest start time of the inference start time variable before the propagation needs to be larger as
2927  * than the beginning of the time interval; meaning the job needs be overlap with the time interval in case
2928  * the job is scheduled w.r.t. its earliest start time
2929  */
2930  assert(ect > begin);
2931 
2932  /* compute the overlap of the job in case it would be scheduled w.r.t. its earliest start time and the time
2933  * interval (before the propagation)
2934  */
2935  left = MIN3(ect - begin, end - begin, duration);
2936 
2937  /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */
2938  assert(left > 0);
2939 
2940  est = SCIPconvertRealToInt(scip, relaxedbd);
2941  assert(end >= est);
2942  assert(bdchgidx == NULL || end - SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE) < duration);
2943 
2944  /* compute the overlap of the job after the propagation but considering the relaxed bound */
2945  right = MIN(end - est + 1, end - begin);
2946  assert(right > 0);
2947 
2948  /* compute the minimum overlap */
2949  overlap = MIN(left, right);
2950  assert(overlap > 0);
2951  assert(overlap <= end - begin);
2952  assert(overlap <= duration);
2953 
2954  if( usebdwidening )
2955  {
2956  assert(SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) >= (begin + overlap - duration));
2957  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(begin + overlap - duration)) );
2958  }
2959  else
2960  {
2961  SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
2962  }
2963  }
2964 
2965  /* subtract the amount of energy which is available due to the overlap of the inference start time */
2966  requiredenergy -= overlap * demand;
2967 
2968  if( explanation != NULL )
2969  explanation[v] = TRUE;
2970 
2971  continue;
2972  }
2973 
2974  /* global time points */
2975  est = SCIPconvertRealToInt(scip, SCIPvarGetLbGlobal(var));
2976  lst = SCIPconvertRealToInt(scip, SCIPvarGetUbGlobal(var));
2977 
2978  glbenergy = 0;
2979 
2980  /* check if the has any overlap w.r.t. global bound; meaning some parts of the job will run for sure within the
2981  * time window
2982  */
2983  if( est + duration > begin && lst < end )
2984  {
2985  /* evaluated global contribution */
2986  glbenergy = computeOverlap(begin, end, est, lst, duration) * demand;
2987 
2988  /* remove the globally available energy form the required energy */
2989  requiredenergy -= glbenergy;
2990 
2991  if( explanation != NULL )
2992  explanation[v] = TRUE;
2993  }
2994 
2995  /* local time points */
2996  est = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE));
2997  lst = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
2998 
2999  /* check if the job has any overlap w.r.t. local bound; meaning some parts of the job will run for sure within the
3000  * time window
3001  */
3002  if( est + duration > begin && lst < end )
3003  {
3004  overlaps[v] = computeOverlap(begin, end, est, lst, duration);
3005 
3006  /* evaluated additionally local energy contribution */
3007  locenergies[v] = overlaps[v] * demand - glbenergy;
3008  assert(locenergies[v] >= 0);
3009  }
3010  }
3011 
3012  /* sort the variable contributions w.r.t. additional local energy contributions */
3013  SCIPsortDownIntIntInt(locenergies, overlaps, idxs, nvars);
3014 
3015  /* add local energy contributions until an overload is implied */
3016  for( v = 0; v < nvars && requiredenergy >= 0; ++v )
3017  {
3018  SCIP_VAR* var;
3019  int duration;
3020  int overlap;
3021  int relaxlb;
3022  int relaxub;
3023  int idx;
3024 
3025  idx = idxs[v];
3026  assert(idx >= 0 && idx < nvars);
3027 
3028  var = vars[idx];
3029  assert(var != NULL);
3030  assert(var != infervar);
3031 
3032  duration = durations[idx];
3033  assert(duration > 0);
3034 
3035  overlap = overlaps[v];
3036  assert(overlap > 0);
3037 
3038  requiredenergy -= locenergies[v];
3039 
3040  if( requiredenergy < -1 )
3041  {
3042  int demand;
3043 
3044  demand = demands[idx];
3045  assert(demand > 0);
3046 
3047  overlap += (int)((requiredenergy + 1) / demand);
3048 
3049 #ifndef NDEBUG
3050  requiredenergy += locenergies[v];
3051  requiredenergy -= overlap * demand;
3052  assert(requiredenergy < 0);
3053 #endif
3054  }
3055  assert(overlap > 0);
3056 
3057  relaxlb = begin - duration + overlap;
3058  relaxub = end - overlap;
3059 
3060  SCIPdebugMsg(scip, "variable <%s> glb=[%g,%g] loc=[%g,%g], conf=[%g,%g], added=[%d,%d] (demand %d, duration %d)\n",
3061  SCIPvarGetName(var),
3064  SCIPgetConflictVarLb(scip, var), SCIPgetConflictVarUb(scip, var),
3065  relaxlb, relaxub, demands[idx], duration);
3066 
3067  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)relaxlb) );
3068  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, (SCIP_Real)relaxub) );
3069 
3070  if( explanation != NULL )
3071  explanation[idx] = TRUE;
3072  }
3073 
3074  assert(requiredenergy < 0);
3075 
3076  SCIPfreeBufferArray(scip, &idxs);
3077  SCIPfreeBufferArray(scip, &overlaps);
3078  SCIPfreeBufferArray(scip, &locenergies);
3079 
3080  return SCIP_OKAY;
3081 }
3082 
3083 /** resolve propagation w.r.t. the cumulative condition */
3084 static
3086  SCIP* scip, /**< SCIP data structure */
3087  int nvars, /**< number of start time variables (activities) */
3088  SCIP_VAR** vars, /**< array of start time variables */
3089  int* durations, /**< array of durations */
3090  int* demands, /**< array of demands */
3091  int capacity, /**< cumulative capacity */
3092  int hmin, /**< left bound of time axis to be considered (including hmin) */
3093  int hmax, /**< right bound of time axis to be considered (not including hmax) */
3094  SCIP_VAR* infervar, /**< the conflict variable whose bound change has to be resolved */
3095  INFERINFO inferinfo, /**< the user information */
3096  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
3097  SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
3098  SCIP_Real relaxedbd, /**< the relaxed bound which is sufficient to be explained */
3099  SCIP_Bool usebdwidening, /**< should bound widening be used during conflict analysis? */
3100  SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
3101  SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
3102  )
3103 {
3104  switch( inferInfoGetProprule(inferinfo) )
3105  {
3106  case PROPRULE_1_CORETIMES:
3107  {
3108  int inferdemand;
3109  int inferduration;
3110  int inferpos;
3111  int inferpeak;
3112  int relaxedpeak;
3113  int provedpeak;
3114 
3115  /* get the position of the inferred variable in the vars array */
3116  inferpos = inferInfoGetData1(inferinfo);
3117  if( inferpos >= nvars || vars[inferpos] != infervar )
3118  {
3119  /* find inference variable in constraint */
3120  for( inferpos = 0; inferpos < nvars && vars[inferpos] != infervar; ++inferpos )
3121  {}
3122  }
3123  assert(inferpos < nvars);
3124  assert(vars[inferpos] == infervar);
3125 
3126  inferdemand = demands[inferpos];
3127  inferduration = durations[inferpos];
3128 
3129  if( boundtype == SCIP_BOUNDTYPE_UPPER )
3130  {
3131  /* we propagated the latest start time (upper bound) step wise with a step length of at most the duration of
3132  * the inference variable
3133  */
3134  assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE) - SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < inferduration + 0.5);
3135 
3136  SCIPdebugMsg(scip, "variable <%s>: upper bound changed from %g to %g (relaxed %g)\n",
3137  SCIPvarGetName(infervar), SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE),
3138  SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE), relaxedbd);
3139 
3140  /* get the inference peak that the time point which lead to the that propagtion */
3141  inferpeak = inferInfoGetData2(inferinfo);
3142  /* the bound passed back to be resolved might be tighter as the bound propagted by the core time propagator;
3143  * this can happen if the variable is not activ and aggregated to an activ variable with a scale != 1.0
3144  */
3145  assert(SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE)) + inferduration <= inferpeak);
3146  relaxedpeak = SCIPconvertRealToInt(scip, relaxedbd) + inferduration;
3147 
3148  /* make sure that the relaxed peak is part of the effective horizon */
3149  relaxedpeak = MIN(relaxedpeak, hmax-1);
3150 
3151  /* make sure that relaxed peak is not larger than the infer peak
3152  *
3153  * This can happen in case the variable is not an active variable!
3154  */
3155  relaxedpeak = MAX(relaxedpeak, inferpeak);
3156  assert(relaxedpeak >= inferpeak);
3157  assert(relaxedpeak >= hmin);
3158  }
3159  else
3160  {
3161  assert(boundtype == SCIP_BOUNDTYPE_LOWER);
3162 
3163  SCIPdebugMsg(scip, "variable <%s>: lower bound changed from %g to %g (relaxed %g)\n",
3164  SCIPvarGetName(infervar), SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, FALSE),
3165  SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE), relaxedbd);
3166 
3167  /* get the time interval where the job could not be scheduled */
3168  inferpeak = inferInfoGetData2(inferinfo);
3169  /* the bound passed back to be resolved might be tighter as the bound propagted by the core time propagator;
3170  * this can happen if the variable is not activ and aggregated to an activ variable with a scale != 1.0
3171  */
3172  assert(SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE)) - 1 >= inferpeak);
3173  relaxedpeak = SCIPconvertRealToInt(scip, relaxedbd) - 1;
3174 
3175  /* make sure that the relaxed peak is part of the effective horizon */
3176  relaxedpeak = MAX(relaxedpeak, hmin);
3177 
3178  /* make sure that relaxed peak is not larger than the infer peak
3179  *
3180  * This can happen in case the variable is not an active variable!
3181  */
3182  relaxedpeak = MIN(relaxedpeak, inferpeak);
3183  assert(relaxedpeak < hmax);
3184  }
3185 
3186  /* resolves the propagation of the core time algorithm */
3187  SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
3188  infervar, inferdemand, inferpeak, relaxedpeak, bdchgidx, usebdwidening, &provedpeak, explanation) );
3189 
3190  if( boundtype == SCIP_BOUNDTYPE_UPPER )
3191  {
3192  if( usebdwidening )
3193  {
3194  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, infervar, NULL, (SCIP_Real)provedpeak) );
3195  }
3196  else
3197  {
3198  /* old upper bound of variable itself is part of the explanation */
3199  SCIP_CALL( SCIPaddConflictUb(scip, infervar, bdchgidx) );
3200  }
3201  }
3202  else
3203  {
3204  assert(boundtype == SCIP_BOUNDTYPE_LOWER);
3205 
3206  if( usebdwidening )
3207  {
3208  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, bdchgidx, (SCIP_Real)(provedpeak - inferduration + 1)) );
3209  }
3210  else
3211  {
3212  /* old lower bound of variable itself is part of the explanation */
3213  SCIP_CALL( SCIPaddConflictLb(scip, infervar, bdchgidx) );
3214  }
3215  }
3216 
3217  if( explanation != NULL )
3218  explanation[inferpos] = TRUE;
3219 
3220  break;
3221  }
3223  case PROPRULE_3_TTEF:
3224  {
3225  int begin;
3226  int end;
3227 
3228  begin = inferInfoGetData1(inferinfo);
3229  end = inferInfoGetData2(inferinfo);
3230  assert(begin < end);
3231 
3232  begin = MAX(begin, hmin);
3233  end = MIN(end, hmax);
3234 
3235  SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
3236  begin, end, infervar, boundtype, bdchgidx, relaxedbd, usebdwidening, explanation) );
3237 
3238  break;
3239  }
3240 
3241  default:
3242  SCIPerrorMessage("invalid inference information %d\n", inferInfoGetProprule(inferinfo));
3243  SCIPABORT();
3244  return SCIP_INVALIDDATA; /*lint !e527*/
3245  }
3246 
3247  (*result) = SCIP_SUCCESS;
3248 
3249  return SCIP_OKAY;
3250 }
3251 
3252 /**@} */
3253 
3254 
3255 /**@name Enforcement methods
3256  *
3257  * @{
3258  */
3259 
3260 /** apply all fixings which are given by the alternative bounds */
3261 static
3263  SCIP* scip, /**< SCIP data structure */
3264  SCIP_VAR** vars, /**< array of active variables */
3265  int nvars, /**< number of active variables */
3266  int* alternativelbs, /**< alternative lower bounds */
3267  int* alternativeubs, /**< alternative lower bounds */
3268  int* downlocks, /**< number of constraints with down lock participating by the computation */
3269  int* uplocks, /**< number of constraints with up lock participating by the computation */
3270  SCIP_Bool* branched /**< pointer to store if a branching was applied */
3271  )
3272 {
3273  int v;
3274 
3275  for( v = 0; v < nvars; ++v )
3276  {
3277  SCIP_VAR* var;
3278  SCIP_Real objval;
3279 
3280  var = vars[v];
3281  assert(var != NULL);
3282 
3283  objval = SCIPvarGetObj(var);
3284 
3285  if( SCIPvarGetNLocksDown(var) == downlocks[v] && !SCIPisNegative(scip, objval) )
3286  {
3287  int ub;
3288 
3289  ub = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
3290 
3291  if( alternativelbs[v] <= ub )
3292  {
3293  SCIP_CALL( SCIPbranchVarHole(scip, var, SCIPvarGetLbLocal(var), (SCIP_Real)alternativelbs[v], NULL, NULL) );
3294  (*branched) = TRUE;
3295 
3296  SCIPdebugMsg(scip, "variable <%s> branched domain hole (%g,%d)\n", SCIPvarGetName(var),
3297  SCIPvarGetLbLocal(var), alternativelbs[v]);
3298 
3299  return SCIP_OKAY;
3300  }
3301  }
3302 
3303  if( SCIPvarGetNLocksUp(var) == uplocks[v] && !SCIPisPositive(scip, objval) )
3304  {
3305  int lb;
3306 
3307  lb = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
3308 
3309  if( alternativeubs[v] >= lb )
3310  {
3311  SCIP_CALL( SCIPbranchVarHole(scip, var, (SCIP_Real)alternativeubs[v], SCIPvarGetUbLocal(var), NULL, NULL) );
3312  (*branched) = TRUE;
3313 
3314  SCIPdebugMsg(scip, "variable <%s> branched domain hole (%d,%g)\n", SCIPvarGetName(var),
3315  alternativeubs[v], SCIPvarGetUbLocal(var));
3316 
3317  return SCIP_OKAY;
3318  }
3319  }
3320  }
3321 
3322  return SCIP_OKAY;
3323 }
3324 
3325 /** remove the capacity requirments for all job which start at the curtime */
3326 static
3328  SCIP_CONSDATA* consdata, /**< constraint data */
3329  int curtime, /**< current point in time */
3330  int* starttimes, /**< array of start times */
3331  int* startindices, /**< permutation with respect to the start times */
3332  int* freecapacity, /**< pointer to store the resulting free capacity */
3333  int* idx, /**< pointer to index in start time array */
3334  int nvars /**< number of vars in array of starttimes and startindices */
3335  )
3336 {
3337 
3338 #if defined SCIP_DEBUG && !defined NDEBUG
3339  int oldidx;
3340 
3341  assert(idx != NULL);
3342  oldidx = *idx;
3343 #else
3344  assert(idx != NULL);
3345 #endif
3346 
3347  assert(starttimes != NULL);
3348  assert(starttimes != NULL);
3349  assert(freecapacity != NULL);
3350  assert(starttimes[*idx] == curtime);
3351  assert(consdata->demands != NULL);
3352  assert(freecapacity != idx);
3353 
3354  /* subtract all capacity needed up to this point */
3355  (*freecapacity) -= consdata->demands[startindices[*idx]];
3356 
3357  while( (*idx)+1 < nvars && starttimes[(*idx)+1] == curtime )
3358  {
3359  ++(*idx);
3360  (*freecapacity) -= consdata->demands[startindices[(*idx)]];
3361  assert(freecapacity != idx);
3362  }
3363 #ifdef SCIP_DEBUG
3364  assert(oldidx <= *idx);
3365 #endif
3366 }
3367 
3368 /** add the capacity requirments for all job which end at the curtime */
3369 static
3370 void addEndingJobDemands(
3371  SCIP_CONSDATA* consdata, /**< constraint data */
3372  int curtime, /**< current point in time */
3373  int* endtimes, /**< array of end times */
3374  int* endindices, /**< permutation with rspect to the end times */
3375  int* freecapacity, /**< pointer to store the resulting free capacity */
3376  int* idx, /**< pointer to index in end time array */
3377  int nvars /**< number of vars in array of starttimes and startindices */
3378  )
3379 {
3380 #if defined SCIP_DEBUG && !defined NDEBUG
3381  int oldidx;
3382  oldidx = *idx;
3383 #endif
3384 
3385  /* free all capacity usages of jobs the are no longer running */
3386  while( endtimes[*idx] <= curtime && *idx < nvars)
3387  {
3388  (*freecapacity) += consdata->demands[endindices[*idx]];
3389  ++(*idx);
3390  }
3391 
3392 #ifdef SCIP_DEBUG
3393  assert(oldidx <= *idx);
3394 #endif
3395 }
3396 
3397 /** computes a point in time when the capacity is exceeded returns hmax if this does not happen */
3398 static
3400  SCIP* scip, /**< SCIP data structure */
3401  SCIP_CONSDATA* consdata, /**< constraint handler data */
3402  SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
3403  int* timepoint /**< pointer to store the time point of the peak */
3404  )
3405 {
3406  int* starttimes; /* stores when each job is starting */
3407  int* endtimes; /* stores when each job ends */
3408  int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
3409  int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
3410 
3411  int nvars; /* number of activities for this constraint */
3412  int freecapacity; /* remaining capacity */
3413  int curtime; /* point in time which we are just checking */
3414  int endindex; /* index of endsolvalues with: endsolvalues[endindex] > curtime */
3415 
3416  int hmin;
3417  int hmax;
3418 
3419  int j;
3420 
3421  assert(consdata != NULL);
3422 
3423  nvars = consdata->nvars;
3424  assert(nvars > 0);
3425 
3426  *timepoint = consdata->hmax;
3427 
3428  assert(consdata->vars != NULL);
3429 
3430  SCIP_CALL( SCIPallocBufferArray(scip, &starttimes, nvars) );
3431  SCIP_CALL( SCIPallocBufferArray(scip, &endtimes, nvars) );
3432  SCIP_CALL( SCIPallocBufferArray(scip, &startindices, nvars) );
3433  SCIP_CALL( SCIPallocBufferArray(scip, &endindices, nvars) );
3434 
3435  /* create event point arrays */
3436  createSortedEventpointsSol(scip, sol, consdata->nvars, consdata->vars, consdata->durations,
3437  starttimes, endtimes, startindices, endindices);
3438 
3439  endindex = 0;
3440  freecapacity = consdata->capacity;
3441  hmin = consdata->hmin;
3442  hmax = consdata->hmax;
3443 
3444  /* check each startpoint of a job whether the capacity is kept or not */
3445  for( j = 0; j < nvars; ++j )
3446  {
3447  curtime = starttimes[j];
3448  SCIPdebugMsg(scip, "look at %d-th job with start %d\n", j, curtime);
3449 
3450  if( curtime >= hmax )
3451  break;
3452 
3453  /* remove the capacity requirments for all job which start at the curtime */
3454  subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars);
3455 
3456  /* add the capacity requirments for all job which end at the curtime */
3457  addEndingJobDemands(consdata, curtime, endtimes, endindices, &freecapacity, &endindex, nvars);
3458 
3459  assert(freecapacity <= consdata->capacity);
3460  assert(endindex <= nvars);
3461 
3462  /* endindex - points to the next job which will finish */
3463  /* j - points to the last job that has been released */
3464 
3465  /* if free capacity is smaller than zero, then add branching candidates */
3466  if( freecapacity < 0 && curtime >= hmin )
3467  {
3468  *timepoint = curtime;
3469  break;
3470  }
3471  } /*lint --e{850}*/
3472 
3473  /* free all buffer arrays */
3474  SCIPfreeBufferArray(scip, &endindices);
3475  SCIPfreeBufferArray(scip, &startindices);
3476  SCIPfreeBufferArray(scip, &endtimes);
3477  SCIPfreeBufferArray(scip, &starttimes);
3478 
3479  return SCIP_OKAY;
3480 }
3481 
3482 /** checks all cumulative constraints for infeasibility and add branching candidates to storage */
3483 static
3485  SCIP* scip, /**< SCIP data structure */
3486  SCIP_CONS** conss, /**< constraints to be processed */
3487  int nconss, /**< number of constraints */
3488  SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
3489  int* nbranchcands /**< pointer to store the number of branching variables */
3490  )
3491 {
3492  SCIP_HASHTABLE* collectedvars;
3493  int c;
3494 
3495  assert(scip != NULL);
3496  assert(conss != NULL);
3497 
3498  /* create a hash table */
3499  SCIP_CALL( SCIPhashtableCreate(&collectedvars, SCIPblkmem(scip), SCIPgetNVars(scip),
3500  SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal, NULL) );
3501 
3502  assert(scip != NULL);
3503  assert(conss != NULL);
3504 
3505  for( c = 0; c < nconss; ++c )
3506  {
3507  SCIP_CONS* cons;
3508  SCIP_CONSDATA* consdata;
3509 
3510  int curtime;
3511  int j;
3512 
3513  cons = conss[c];
3514  assert(cons != NULL);
3515 
3516  if( !SCIPconsIsActive(cons) )
3517  continue;
3518 
3519  consdata = SCIPconsGetData(cons);
3520  assert(consdata != NULL);
3521 
3522  /* get point in time when capacity is exceeded */
3523  SCIP_CALL( computePeak(scip, consdata, sol, &curtime) );
3524 
3525  if( curtime < consdata->hmin || curtime >= consdata->hmax )
3526  continue;
3527 
3528  /* report all variables that are running at that point in time */
3529  for( j = 0; j < consdata->nvars; ++j )
3530  {
3531  SCIP_VAR* var;
3532  int lb;
3533  int ub;
3534 
3535  var = consdata->vars[j];
3536  assert(var != NULL);
3537 
3538  /* check if the variable was already added */
3539  if( SCIPhashtableExists(collectedvars, (void*)var) )
3540  continue;
3541 
3542  lb = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
3543  ub = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
3544 
3545  if( lb <= curtime && ub + consdata->durations[j] > curtime && lb < ub )
3546  {
3547  SCIP_Real solval;
3548  SCIP_Real score;
3549 
3550  solval = SCIPgetSolVal(scip, sol, var);
3551  score = MIN(solval - lb, ub - solval) / ((SCIP_Real)ub-lb);
3552 
3553  SCIPdebugMsg(scip, "add var <%s> to branch cand storage\n", SCIPvarGetName(var));
3554  SCIP_CALL( SCIPaddExternBranchCand(scip, var, score, lb + (ub - lb) / 2.0 + 0.2) );
3555  (*nbranchcands)++;
3556 
3557  SCIP_CALL( SCIPhashtableInsert(collectedvars, var) );
3558  }
3559  }
3560  }
3561 
3562  SCIPhashtableFree(&collectedvars);
3563 
3564  SCIPdebugMsg(scip, "found %d branching candidates\n", *nbranchcands);
3565 
3566  return SCIP_OKAY;
3567 }
3568 
3569 /** enforcement of an LP, pseudo, or relaxation solution */
3570 static
3572  SCIP* scip, /**< SCIP data structure */
3573  SCIP_CONS** conss, /**< constraints to be processed */
3574  int nconss, /**< number of constraints */
3575  SCIP_SOL* sol, /**< solution to enforce (NULL for LP or pseudo solution) */
3576  SCIP_Bool branch, /**< should branching candidates be collected */
3577  SCIP_RESULT* result /**< pointer to store the result */
3578  )
3579 {
3580  if( branch )
3581  {
3582  int nbranchcands;
3583 
3584  nbranchcands = 0;
3585  SCIP_CALL( collectBranchingCands(scip, conss, nconss, sol, &nbranchcands) );
3586 
3587  if( nbranchcands > 0 )
3588  (*result) = SCIP_INFEASIBLE;
3589  }
3590  else
3591  {
3592  SCIP_Bool violated;
3593  int c;
3594 
3595  violated = FALSE;
3596 
3597  /* first check if a constraints is violated */
3598  for( c = 0; c < nconss && !violated; ++c )
3599  {
3600  SCIP_CONS* cons;
3601 
3602  cons = conss[c];
3603  assert(cons != NULL);
3604 
3605  SCIP_CALL( checkCons(scip, cons, sol, &violated, FALSE) );
3606  }
3607 
3608  if( violated )
3609  (*result) = SCIP_INFEASIBLE;
3610  }
3611 
3612  return SCIP_OKAY;
3613 }
3614 
3615 /**@} */
3616 
3617 /**@name Propagation
3618  *
3619  * @{
3620  */
3621 
3622 /** check if cumulative constraint is independently of all other constraints */
3623 static
3625  SCIP* scip, /**< SCIP data structure */
3626  SCIP_CONS* cons /**< cumulative constraint */
3627  )
3628 {
3629  SCIP_CONSDATA* consdata;
3630  SCIP_VAR** vars;
3631  SCIP_Bool* downlocks;
3632  SCIP_Bool* uplocks;
3633  int nvars;
3634  int v;
3635 
3636  consdata = SCIPconsGetData(cons);
3637  assert(consdata != NULL);
3638 
3639  nvars = consdata->nvars;
3640  vars = consdata->vars;
3641  downlocks = consdata->downlocks;
3642  uplocks = consdata->uplocks;
3643 
3644  /* check if the cumulative constraint has the only locks on the involved variables */
3645  for( v = 0; v < nvars; ++v )
3646  {
3647  SCIP_VAR* var;
3648 
3649  var = vars[v];
3650  assert(var != NULL);
3651 
3652  if( SCIPvarGetNLocksDown(var) > (int)downlocks[v] || SCIPvarGetNLocksUp(var) > (int)uplocks[v] )
3653  return FALSE;
3654  }
3655 
3656  return TRUE;
3657 }
3658 
3659 /** in case the cumulative constraint is independent of every else, solve the cumulative problem and apply the fixings
3660  * (dual reductions)
3661  */
3662 static
3664  SCIP* scip, /**< SCIP data structure */
3665  SCIP_CONS* cons, /**< cumulative constraint */
3666  SCIP_Longint maxnodes, /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
3667  int* nchgbds, /**< pointer to store the number changed variable bounds */
3668  int* nfixedvars, /**< pointer to count number of fixings */
3669  int* ndelconss, /**< pointer to count number of deleted constraints */
3670  SCIP_Bool* cutoff, /**< pointer to store if the constraint is infeasible */
3671  SCIP_Bool* unbounded /**< pointer to store if the constraint is unbounded */
3672  )
3673 {
3674  SCIP_CONSDATA* consdata;
3675  SCIP_VAR** vars;
3676  SCIP_Real* objvals;
3677  SCIP_Real* lbs;
3678  SCIP_Real* ubs;
3679  SCIP_Real timelimit;
3680  SCIP_Real memorylimit;
3681  SCIP_Bool solved;
3682  SCIP_Bool error;
3683 
3684  int ncheckconss;
3685  int nvars;
3686  int v;
3687 
3688  assert(scip != NULL);
3689  assert(!SCIPconsIsModifiable(cons));
3690  assert(SCIPgetNConss(scip) > 0);
3691 
3692  /* if SCIP is in probing mode or repropagation we cannot perform this dual reductions since this dual reduction
3693  * would/could end in an implication which can lead to cutoff of the/all optimal solution
3694  */
3695  if( SCIPinProbing(scip) || SCIPinRepropagation(scip) )
3696  return SCIP_OKAY;
3697 
3698  /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
3699  * use the locks to decide for a dual reduction using this constraint;
3700  */
3701  if( !SCIPconsIsChecked(cons) )
3702  return SCIP_OKAY;
3703 
3704  ncheckconss = SCIPgetNCheckConss(scip);
3705 
3706  /* if the cumulative constraint is the only constraint of the original problem or the only check constraint in the
3707  * presolved problem do nothing execpt to change the parameter settings
3708  */
3709  if( ncheckconss == 1 )
3710  {
3711  /* shrink the minimal maximum value for the conflict length */
3712  SCIP_CALL( SCIPsetIntParam(scip, "conflict/minmaxvars", 10) );
3713 
3714  /* use only first unique implication point */
3715  SCIP_CALL( SCIPsetIntParam(scip, "conflict/fuiplevels", 1) );
3716 
3717  /* do not use reconversion conflicts */
3718  SCIP_CALL( SCIPsetIntParam(scip, "conflict/reconvlevels", 0) );
3719 
3720  /* after 250 conflict we force a restart since then the variable statistics are reasonable initialized */
3721  SCIP_CALL( SCIPsetIntParam(scip, "conflict/restartnum", 250) );
3722 
3723  /* increase the number of conflicts which induce a restart */
3724  SCIP_CALL( SCIPsetRealParam(scip, "conflict/restartfac", 2.0) );
3725 
3726  /* weight the variable which made into a conflict */
3727  SCIP_CALL( SCIPsetRealParam(scip, "conflict/conflictweight", 1.0) );
3728 
3729  /* do not check pseudo solution (for performance reasons) */
3730  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/disableenfops", TRUE) );
3731 
3732  /* use value based history to detect a reasonable branching point */
3733  SCIP_CALL( SCIPsetBoolParam(scip, "history/valuebased", TRUE) );
3734 
3735  /* turn of LP relaxation */
3736  SCIP_CALL( SCIPsetIntParam(scip, "lp/solvefreq", -1) );
3737 
3738  /* prefer the down branch in case the value based history does not suggest something */
3739  SCIP_CALL( SCIPsetCharParam(scip, "nodeselection/childsel", 'd') );
3740 
3741  /* accept any bound change */
3742  SCIP_CALL( SCIPsetRealParam(scip, "numerics/boundstreps", 1e-6) );
3743 
3744  /* allow for at most 10 restart, after that the value based history should be reliable */
3745  SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 10) );
3746 
3747  /* set priority for depth first search to highest possible value */
3748  SCIP_CALL( SCIPsetIntParam(scip, "nodeselection/dfs/stdpriority", INT_MAX/4) );
3749 
3750  return SCIP_OKAY;
3751  }
3752 
3753  consdata = SCIPconsGetData(cons);
3754  assert(consdata != NULL);
3755 
3756  /* check if already tried to solve that constraint as independent sub problem; we do not want to try it again if we
3757  * fail on the first place
3758  */
3759  if( consdata->triedsolving )
3760  return SCIP_OKAY;
3761 
3762  /* check if constraint is independently */
3763  if( !isConsIndependently(scip, cons) )
3764  return SCIP_OKAY;
3765 
3766  /* mark the constraint to be tried of solving it as independent sub problem; in case that is successful the
3767  * constraint is deleted; otherwise, we want to ensure that we do not try that again
3768  */
3769  consdata->triedsolving = TRUE;
3770 
3771  SCIPdebugMsg(scip, "the cumulative constraint <%s> is independent from rest of the problem (%d variables, %d constraints)\n",
3772  SCIPconsGetName(cons), SCIPgetNVars(scip), SCIPgetNConss(scip));
3773  SCIPdebugPrintCons(scip, cons, NULL);
3774 
3775  nvars = consdata->nvars;
3776  vars = consdata->vars;
3777 
3778  SCIP_CALL( SCIPallocBufferArray(scip, &lbs, nvars) );
3779  SCIP_CALL( SCIPallocBufferArray(scip, &ubs, nvars) );
3780  SCIP_CALL( SCIPallocBufferArray(scip, &objvals, nvars) );
3781 
3782  for( v = 0; v < nvars; ++v )
3783  {
3784  SCIP_VAR* var;
3785 
3786  /* if a variables array is given, use the variable bounds otherwise the default values stored in the ests and lsts
3787  * array
3788  */
3789  var = vars[v];
3790  assert(var != NULL);
3791 
3792  lbs[v] = SCIPvarGetLbLocal(var);
3793  ubs[v] = SCIPvarGetUbLocal(var);
3794 
3795  objvals[v] = SCIPvarGetObj(var);
3796  }
3797 
3798  /* check whether there is enough time and memory left */
3799  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
3800  if( !SCIPisInfinity(scip, timelimit) )
3801  timelimit -= SCIPgetSolvingTime(scip);
3802  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
3803 
3804  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
3805  if( !SCIPisInfinity(scip, memorylimit) )
3806  {
3807  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
3808  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
3809  }
3810 
3811  /* solve the cumulative condition separately */
3812  SCIP_CALL( SCIPsolveCumulative(scip, nvars, lbs, ubs, objvals, consdata->durations, consdata->demands, consdata->capacity,
3813  consdata->hmin, consdata->hmax, timelimit, memorylimit, maxnodes, &solved, cutoff, unbounded, &error) );
3814 
3815  if( !(*cutoff) && !(*unbounded) && !error )
3816  {
3817  SCIP_Bool infeasible;
3818  SCIP_Bool tightened;
3819  SCIP_Bool allfixed;
3820 
3821  allfixed = TRUE;
3822 
3823  for( v = 0; v < nvars; ++v )
3824  {
3825  /* check if variable is fixed */
3826  if( lbs[v] + 0.5 > ubs[v] )
3827  {
3828  SCIP_CALL( SCIPfixVar(scip, vars[v], lbs[v], &infeasible, &tightened) );
3829  assert(!infeasible);
3830 
3831  if( tightened )
3832  {
3833  (*nfixedvars)++;
3834  consdata->triedsolving = FALSE;
3835  }
3836  }
3837  else
3838  {
3839  SCIP_CALL( SCIPtightenVarLb(scip, vars[v], lbs[v], TRUE, &infeasible, &tightened) );
3840  assert(!infeasible);
3841 
3842  if( tightened )
3843  {
3844  (*nchgbds)++;
3845  consdata->triedsolving = FALSE;
3846  }
3847 
3848  SCIP_CALL( SCIPtightenVarUb(scip, vars[v], ubs[v], TRUE, &infeasible, &tightened) );
3849  assert(!infeasible);
3850 
3851  if( tightened )
3852  {
3853  (*nchgbds)++;
3854  consdata->triedsolving = FALSE;
3855  }
3856 
3857  allfixed = FALSE;
3858  }
3859  }
3860 
3861  /* if all variables are fixed, remove the cumulative constraint since it is redundant */
3862  if( allfixed )
3863  {
3864  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3865  (*ndelconss)++;
3866  }
3867  }
3868 
3869  SCIPfreeBufferArray(scip, &objvals);
3870  SCIPfreeBufferArray(scip, &ubs);
3871  SCIPfreeBufferArray(scip, &lbs);
3872 
3873  return SCIP_OKAY;
3874 }
3875 
3876 /** start conflict analysis to analysis the core insertion which is infeasible */
3877 static
3879  SCIP* scip, /**< SCIP data structure */
3880  int nvars, /**< number of start time variables (activities) */
3881  SCIP_VAR** vars, /**< array of start time variables */
3882  int* durations, /**< array of durations */
3883  int* demands, /**< array of demands */
3884  int capacity, /**< cumulative capacity */
3885  int hmin, /**< left bound of time axis to be considered (including hmin) */
3886  int hmax, /**< right bound of time axis to be considered (not including hmax) */
3887  SCIP_VAR* infervar, /**< start time variable which lead to the infeasibilty */
3888  int inferduration, /**< duration of the start time variable */
3889  int inferdemand, /**< demand of the start time variable */
3890  int inferpeak, /**< profile preak which causes the infeasibilty */
3891  SCIP_Bool usebdwidening, /**< should bound widening be used during conflict analysis? */
3892  SCIP_Bool* initialized, /**< pointer to store if the conflict analysis was initialized */
3893  SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
3894  )
3895 {
3896  SCIPdebugMsg(scip, "detected infeasibility due to adding a core to the core resource profile\n");
3897  SCIPdebugMsg(scip, "variable <%s>[%g,%g] (demand %d, duration %d)\n", SCIPvarGetName(infervar),
3898  SCIPvarGetLbLocal(infervar), SCIPvarGetUbLocal(infervar), inferdemand, inferduration);
3899 
3900  /* initialize conflict analysis if conflict analysis is applicable */
3902  {
3904 
3905  SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
3906  infervar, inferdemand, inferpeak, inferpeak, NULL, usebdwidening, NULL, explanation) );
3907 
3908  SCIPdebugMsg(scip, "add lower and upper bounds of variable <%s>\n", SCIPvarGetName(infervar));
3909 
3910  /* add both bound of the inference variable since these biuld the core which we could not inserted */
3911  if( usebdwidening )
3912  {
3913  SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, NULL, (SCIP_Real)(inferpeak - inferduration + 1)) );
3914  SCIP_CALL( SCIPaddConflictRelaxedUb(scip, infervar, NULL, (SCIP_Real)inferpeak) );
3915  }
3916  else
3917  {
3918  SCIP_CALL( SCIPaddConflictLb(scip, infervar, NULL) );
3919  SCIP_CALL( SCIPaddConflictUb(scip, infervar, NULL) );
3920  }
3921 
3922  *initialized = TRUE;
3923  }
3924 
3925  return SCIP_OKAY;
3926 }
3927 
3928 /** We are using the core resource profile which contains all core except the one of the start time variable which we
3929  * want to propagate, to incease the earliest start time. This we are doing in steps of length at most the duration of
3930  * the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict
3931  * analysis
3932  */
3933 static
3935  SCIP* scip, /**< SCIP data structure */
3936  int nvars, /**< number of start time variables (activities) */
3937  SCIP_VAR** vars, /**< array of start time variables */
3938  int* durations, /**< array of durations */
3939  int* demands, /**< array of demands */
3940  int capacity, /**< cumulative capacity */
3941  int hmin, /**< left bound of time axis to be considered (including hmin) */
3942  int hmax, /**< right bound of time axis to be considered (not including hmax) */
3943  SCIP_CONS* cons, /**< constraint which is propagated */
3944  SCIP_PROFILE* profile, /**< resource profile */
3945  int idx, /**< position of the variable to propagate */
3946  int* nchgbds, /**< pointer to store the number of bound changes */
3947  SCIP_Bool usebdwidening, /**< should bound widening be used during conflict analysis? */
3948  SCIP_Bool* initialized, /**< was conflict analysis initialized */
3949  SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
3950  SCIP_Bool* infeasible /**< pointer to store if the constraint is infeasible */
3951  )
3952 {
3953  SCIP_VAR* var;
3954  int ntimepoints;
3955  int duration;
3956  int demand;
3957  int peak;
3958  int newlb;
3959  int est;
3960  int lst;
3961  int pos;
3962 
3963  var = vars[idx];
3964  assert(var != NULL);
3965 
3966  duration = durations[idx];
3967  assert(duration > 0);
3968 
3969  demand = demands[idx];
3970  assert(demand > 0);
3971 
3972  est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
3973  lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
3974  ntimepoints = SCIPprofileGetNTimepoints(profile);
3975 
3976  /* first we find left position of earliest start time (lower bound) in resource profile; this position gives us the
3977  * load which we have at the earliest start time (lower bound)
3978  */
3979  (void) SCIPprofileFindLeft(profile, est, &pos);
3980 
3981  SCIPdebugMsg(scip, "propagate earliest start time (lower bound) (pos %d)\n", pos);
3982 
3983  /* we now trying to move the earliest start time in steps of at most "duration" length */
3984  do
3985  {
3986  INFERINFO inferinfo;
3987  SCIP_Bool tightened;
3988  int ect;
3989 
3990 #ifndef NDEBUG
3991  {
3992  /* in debug mode we check that we adjust the search position correctly */
3993  int tmppos;
3994 
3995  (void)SCIPprofileFindLeft(profile, est, &tmppos);
3996  assert(pos == tmppos);
3997  }
3998 #endif
3999  ect = est + duration;
4000  peak = -1;
4001 
4002  /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we
4003  * want a peak which is closest to the earliest completion time
4004  */
4005  do
4006  {
4007  /* check if the profile load conflicts with the demand of the start time variable */
4008  if( SCIPprofileGetLoad(profile, pos) + demand > capacity )
4009  peak = pos;
4010 
4011  pos++;
4012  }
4013  while( pos < ntimepoints && SCIPprofileGetTime(profile, pos) < ect );
4014 
4015  /* if we found no peak that means current the job could be scheduled at its earliest start time without
4016  * conflicting to the core resource profile
4017  */
4018  if( peak == -1 )
4019  break;
4020 
4021  /* the peak position gives us a time point where the start time variable is in conflict with the resource
4022  * profile. That means we have to move it to the next time point in the resource profile but at most to the
4023  * earliest completion time (the remaining move will done in the next loop)
4024  */
4025  newlb = SCIPprofileGetTime(profile, peak+1);
4026  newlb = MIN(newlb, ect);
4027 
4028  /* if the earliest start time is greater than the lst we detected an infeasibilty */
4029  if( newlb > lst )
4030  {
4031  SCIPdebugMsg(scip, "variable <%s>: cannot be scheduled\n", SCIPvarGetName(var));
4032 
4033  /* use conflict analysis to analysis the core insertion which was infeasible */
4034  SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
4035  var, duration, demand, newlb-1, usebdwidening, initialized, explanation) );
4036 
4037  if( explanation != NULL )
4038  explanation[idx] = TRUE;
4039 
4040  *infeasible = TRUE;
4041 
4042  break;
4043  }
4044 
4045  /* construct the inference information which we are using with the conflict analysis to resolve that particular
4046  * bound change
4047  */
4048  inferinfo = getInferInfo(PROPRULE_1_CORETIMES, idx, newlb-1);
4049 
4050  /* perform the bound lower bound change */
4051  SCIP_CALL( SCIPinferVarLbCons(scip, var, (SCIP_Real)newlb, cons, inferInfoToInt(inferinfo), TRUE, infeasible, &tightened) );
4052  assert(tightened);
4053  assert(!(*infeasible));
4054 
4055  SCIPdebugMsg(scip, "variable <%s> new lower bound <%d> -> <%d>\n", SCIPvarGetName(var), est, newlb);
4056  (*nchgbds)++;
4057 
4058  /* for the statistic we count the number of times a lower bound was tightened due the the time-table algorithm */
4060 
4061  /* adjust the earliest start time
4062  *
4063  * @note We are taking the lower of the start time variable on purpose instead of newlb. This is due the fact that
4064  * the proposed lower bound might be even strength by be the core which can be the case if aggregations are
4065  * involved.
4066  */
4067  est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
4068  assert(est >= newlb);
4069 
4070  /* adjust the search position for the resource profile for the next step */
4071  if( est == SCIPprofileGetTime(profile, peak+1) )
4072  pos = peak + 1;
4073  else
4074  pos = peak;
4075  }
4076  while( est < lst );
4077 
4078  return SCIP_OKAY;
4079 }
4080 
4081 /** We are using the core resource profile which contains all core except the one of the start time variable which we
4082  * want to propagate, to decrease the latest start time. This we are doing in steps of length at most the duration of
4083  * the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict
4084  * analysis
4085  */
4086 static
4088  SCIP* scip, /**< SCIP data structure */
4089  SCIP_VAR* var, /**< start time variable to propagate */
4090  int duration, /**< duration of the job */
4091  int demand, /**< demand of the job */
4092  int capacity, /**< cumulative capacity */
4093  SCIP_CONS* cons, /**< constraint which is propagated */
4094  SCIP_PROFILE* profile, /**< resource profile */
4095  int idx, /**< position of the variable to propagate */
4096  int* nchgbds /**< pointer to store the number of bound changes */
4097  )
4098 {
4099  int ntimepoints;
4100  int newub;
4101  int peak;
4102  int pos;
4103  int est;
4104  int lst;
4105  int lct;
4106 
4107  assert(var != NULL);
4108  assert(duration > 0);
4109  assert(demand > 0);
4110 
4111  est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
4112  lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
4113 
4114  /* in case the start time variable is fixed do nothing */
4115  if( est == lst )
4116  return SCIP_OKAY;
4117 
4118  ntimepoints = SCIPprofileGetNTimepoints(profile);
4119 
4120  lct = lst + duration;
4121 
4122  /* first we find left position of latest completion time minus 1 (upper bound + duration) in resource profile; That
4123  * is the last time point where the job would run if schedule it at its latest start time (upper bound). This
4124  * position gives us the load which we have at the latest completion time minus one
4125  */
4126  (void) SCIPprofileFindLeft(profile, lct - 1, &pos);
4127 
4128  SCIPdebugMsg(scip, "propagate upper bound (pos %d)\n", pos);
4129  SCIPdebug( SCIPprofilePrint(profile, SCIPgetMessagehdlr(scip), NULL) );
4130 
4131  if( pos == ntimepoints-1 && SCIPprofileGetTime(profile, pos) == lst )
4132  return SCIP_OKAY;
4133 
4134  /* we now trying to move the latest start time in steps of at most "duration" length */
4135  do
4136  {
4137  INFERINFO inferinfo;
4138  SCIP_Bool tightened;
4139  SCIP_Bool infeasible;
4140 
4141  peak = -1;
4142 
4143 #ifndef NDEBUG
4144  {
4145  /* in debug mode we check that we adjust the search position correctly */
4146  int tmppos;
4147 
4148  (void)SCIPprofileFindLeft(profile, lct - 1, &tmppos);
4149  assert(pos == tmppos);
4150  }
4151 #endif
4152 
4153  /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we
4154  * want a peak which is closest to the latest start time
4155  */
4156  do
4157  {
4158  if( SCIPprofileGetLoad(profile, pos) + demand > capacity )
4159  peak = pos;
4160 
4161  pos--;
4162  }
4163  while( pos >= 0 && SCIPprofileGetTime(profile, pos+1) > lst);
4164 
4165  /* if we found no peak that means the current job could be scheduled at its latest start time without conflicting
4166  * to the core resource profile
4167  */
4168  if( peak == -1 )
4169  break;
4170 
4171  /* the peak position gives us a time point where the start time variable is in conflict with the resource
4172  * profile. That means the job has be done until that point. Hence that gives us the latest completion
4173  * time. Note that that we want to move the bound by at most the duration length (the remaining move we are
4174  * doing in the next loop)
4175  */
4176  newub = SCIPprofileGetTime(profile, peak);
4177  newub = MAX(newub, lst) - duration;
4178  assert(newub >= est);
4179 
4180  /* construct the inference information which we are using with the conflict analysis to resolve that particular
4181  * bound change
4182  */
4183  inferinfo = getInferInfo(PROPRULE_1_CORETIMES, idx, newub+duration);
4184 
4185  /* perform the bound upper bound change */
4186  SCIP_CALL( SCIPinferVarUbCons(scip, var, (SCIP_Real)newub, cons, inferInfoToInt(inferinfo), TRUE, &infeasible, &tightened) );
4187  assert(tightened);
4188  assert(!infeasible);
4189 
4190  SCIPdebugMsg(scip, "variable <%s>: new upper bound <%d> -> <%d>\n", SCIPvarGetName(var), lst, newub);
4191  (*nchgbds)++;
4192 
4193  /* for the statistic we count the number of times a upper bound was tightened due the the time-table algorithm */
4195 
4196  /* adjust the latest start and completion time
4197  *
4198  * @note We are taking the upper of the start time variable on purpose instead of newub. This is due the fact that
4199  * the proposed upper bound might be even strength by be the core which can be the case if aggregations are
4200  * involved.
4201  */
4202  lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
4203  assert(lst <= newub);
4204  lct = lst + duration;
4205 
4206  /* adjust the search position for the resource profile for the next step */
4207  if( SCIPprofileGetTime(profile, peak) == lct )
4208  pos = peak - 1;
4209  else
4210  pos = peak;
4211  }
4212  while( est < lst );
4213 
4214  return SCIP_OKAY;
4215 }
4216 
4217 /** compute for the different earliest start and latest completion time the core energy of the corresponding time
4218  * points
4219  */
4220 static
4222  SCIP* scip, /**< SCIP data structure */
4223  SCIP_PROFILE* profile, /**< core profile */
4224  int nvars, /**< number of start time variables (activities) */
4225  int* ests, /**< array of sorted earliest start times */
4226  int* lcts, /**< array of sorted latest completion times */
4227  int* coreEnergyAfterEst, /**< array to store the core energy after the earliest start time of each job */
4228  int* coreEnergyAfterLct /**< array to store the core energy after the latest completion time of each job */
4229  )
4230 {
4231  int ntimepoints;
4232  int energy;
4233  int t;
4234  int v;
4235 
4236  ntimepoints = SCIPprofileGetNTimepoints(profile);
4237  t = ntimepoints - 1;
4238  energy = 0;
4239 
4240  /* compute core energy after the earliest start time of each job */
4241  for( v = nvars-1; v >= 0; --v )
4242  {
4243  while( t > 0 && SCIPprofileGetTime(profile, t-1) >= ests[v] )
4244  {
4245  assert(SCIPprofileGetLoad(profile, t-1) >= 0);
4246  assert(SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1)>= 0);
4247  energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1));
4248  t--;
4249  }
4250  assert(SCIPprofileGetTime(profile, t) >= ests[v] || t == ntimepoints-1);
4251 
4252  /* maybe ests[j] is in-between two timepoints */
4253  if( SCIPprofileGetTime(profile, t) - ests[v] > 0 )
4254  {
4255  assert(t > 0);
4256  coreEnergyAfterEst[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - ests[v]);
4257  }
4258  else
4259  coreEnergyAfterEst[v] = energy;
4260  }
4261 
4262  t = ntimepoints - 1;
4263  energy = 0;
4264 
4265  /* compute core energy after the latest completion time of each job */
4266  for( v = nvars-1; v >= 0; --v )
4267  {
4268  while( t > 0 && SCIPprofileGetTime(profile, t-1) >= lcts[v] )
4269  {
4270  assert(SCIPprofileGetLoad(profile, t-1) >= 0);
4271  assert(SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1)>= 0);
4272  energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1));
4273  t--;
4274  }
4275  assert(SCIPprofileGetTime(profile, t) >= lcts[v] || t == ntimepoints-1);
4276 
4277  /* maybe lcts[j] is in-between two timepoints */
4278  if( SCIPprofileGetTime(profile, t) - lcts[v] > 0 )
4279  {
4280  assert(t > 0);
4281  coreEnergyAfterLct[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - lcts[v]);
4282  }
4283  else
4284  coreEnergyAfterLct[v] = energy;
4285  }
4286 
4287  return SCIP_OKAY;
4288 }
4289 
4290 /** collect earliest start times, latest completion time, and free energy contributions */
4291 static
4292 void collectDataTTEF(
4293  SCIP* scip, /**< SCIP data structure */
4294  int nvars, /**< number of start time variables (activities) */
4295  SCIP_VAR** vars, /**< array of start time variables */
4296  int* durations, /**< array of durations */
4297  int* demands, /**< array of demands */
4298  int hmin, /**< left bound of time axis to be considered (including hmin) */
4299  int hmax, /**< right bound of time axis to be considered (not including hmax) */
4300  int* permests, /**< array to store the variable positions */
4301  int* ests, /**< array to store earliest start times */
4302  int* permlcts, /**< array to store the variable positions */
4303  int* lcts, /**< array to store latest completion times */
4304  int* ects, /**< array to store earliest completion times of the flexible part of the job */
4305  int* lsts, /**< array to store latest start times of the flexible part of the job */
4306  int* flexenergies /**< array to store the flexible energies of each job */
4307  )
4308 {
4309  int v;
4310 
4311  for( v = 0; v < nvars; ++ v)
4312  {
4313  int duration;
4314  int leftadjust;
4315  int rightadjust;
4316  int core;
4317  int est;
4318  int lct;
4319  int ect;
4320  int lst;
4321 
4322  duration = durations[v];
4323  assert(duration > 0);
4324 
4325  est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[v]));
4326  lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[v]));
4327  ect = est + duration;
4328  lct = lst + duration;
4329 
4330  ests[v] = est;
4331  lcts[v] = lct;
4332  permests[v] = v;
4333  permlcts[v] = v;
4334 
4335  /* compute core time window which lies within the effective horizon */
4336  core = computeCoreWithInterval(hmin, hmax, ect, lst);
4337 
4338  /* compute the number of time steps the job could run before the effective horizon */
4339  leftadjust = MAX(0, hmin - est);
4340 
4341  /* compute the number of time steps the job could run after the effective horizon */
4342  rightadjust = MAX(0, lct - hmax);
4343 
4344  /* compute for each job the energy which is flexible; meaning not part of the core */
4345  flexenergies[v] = duration - leftadjust - rightadjust - core;
4346  flexenergies[v] = MAX(0, flexenergies[v]);
4347  flexenergies[v] *= demands[v];
4348  assert(flexenergies[v] >= 0);
4349 
4350  /* the earliest completion time of the flexible energy */
4351  ects[v] = MIN(ect, lst);
4352 
4353  /* the latest start time of the flexible energy */
4354  lsts[v] = MAX(ect, lst);
4355  }
4356 }
4357 
4358 /** try to tighten the lower bound of the given variable */
4359 static
4361  SCIP* scip, /**< SCIP data structure */
4362  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
4363  int nvars, /**< number of start time variables (activities) */
4364  SCIP_VAR** vars, /**< array of start time variables */
4365  int* durations, /**< array of durations */
4366  int* demands, /**< array of demands */
4367  int capacity, /**< cumulative capacity */
4368  int hmin, /**< left bound of time axis to be considered (including hmin) */
4369  int hmax, /**< right bound of time axis to be considered (not including hmax) */
4370  SCIP_VAR* var, /**< variable to be considered for upper bound tightening */
4371  int duration, /**< duration of the job */
4372  int demand, /**< demand of the job */
4373  int est, /**< earliest start time of the job */
4374  int ect, /**< earliest completion time of the flexible part of the job */
4375  int lct, /**< latest completion time of the job */
4376  int begin, /**< begin of the time window under investigation */
4377  int end, /**< end of the time window under investigation */
4378  int energy, /**< available energy for the flexible part of the hob within the time window */
4379  int* bestlb, /**< pointer to strope the best lower bound change */
4380  int* inferinfos, /**< pointer to store the inference information which is need for the (best) lower bound change */
4381  SCIP_Bool* initialized, /**< was conflict analysis initialized */
4382  SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4383  SCIP_Bool* cutoff /**< pointer to store if the constraint is infeasible */
4384  )
4385 {
4386  int newlb;
4387 
4388  assert(begin >= hmin);
4389  assert(end <= hmax);
4390 
4391  /* check if the time-table edge-finding should infer bounds */
4392  if( !conshdlrdata->ttefinfer )
4393  return SCIP_OKAY;
4394 
4395  /* if the job can be processed completely before or after the time window, nothing can be tightened */
4396  if( est >= end || ect <= begin )
4397  return SCIP_OKAY;
4398 
4399  /* if flexible part runs completely within the time window (assuming it is scheduled on its earliest start time), we
4400  * skip since the overload check will do the job
4401  */
4402  if( est >= begin && ect <= end )
4403  return SCIP_OKAY;
4404 
4405  /* check if the available energy in the time window is to small to handle the flexible part if it is schedule on its
4406  * earliest start time
4407  */
4408  if( energy >= demand * (MAX(begin, est) - MIN(end, ect)) )
4409  return SCIP_OKAY;
4410 
4411  /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is
4412  * present; therefore, we need to add the core;
4413  *
4414  * @note the variable ect define the earliest completion time of the flexible part of the job; hence we need to
4415  * compute the earliest completion time of the (whole) job
4416  */
4417  energy += computeCoreWithInterval(begin, end, est + duration, lct - duration) * demand;
4418 
4419  /* compute a latest start time (upper bound) such that the job consums at most the available energy
4420  *
4421  * @note we can round down the compute duration w.r.t. the available energy
4422  */
4423  newlb = end - energy / demand;
4424 
4425  /* check if we detected an infeasibility which is the case if the new lower bound is larger than the current upper
4426  * bound (latest start time); meaning it is not possible to schedule the job
4427  */
4428  if( newlb > lct - duration )
4429  {
4430  /* initialize conflict analysis if conflict analysis is applicable */
4432  {
4433  SCIP_Real relaxedbd;
4434 
4435  assert(SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) < newlb);
4436 
4437  /* it is enough to overshoot the upper bound of the variable by one */
4438  relaxedbd = SCIPvarGetUbLocal(var) + 1.0;
4439 
4440  /* initialize conflict analysis */
4442 
4443  /* added to upper bound (which was overcut be new lower bound) of the variable */
4444  SCIP_CALL( SCIPaddConflictUb(scip, var, NULL) );
4445 
4446  /* analyze the infeasible */
4447  SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
4448  begin, end, var, SCIP_BOUNDTYPE_LOWER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) );
4449 
4450  (*initialized) = TRUE;
4451  }
4452 
4453  (*cutoff) = TRUE;
4454  }
4455  else if( newlb > (*bestlb) )
4456  {
4457  INFERINFO inferinfo;
4458 
4459  assert(newlb > begin);
4460 
4461  inferinfo = getInferInfo(PROPRULE_3_TTEF, begin, end);
4462 
4463  /* construct inference information */
4464  (*inferinfos) = inferInfoToInt(inferinfo);
4465  (*bestlb) = newlb;
4466  }
4467 
4468  return SCIP_OKAY;
4469 }
4470 
4471 /** try to tighten the upper bound of the given variable */
4472 static
4474  SCIP* scip, /**< SCIP data structure */
4475  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
4476  int nvars, /**< number of start time variables (activities) */
4477  SCIP_VAR** vars, /**< array of start time variables */
4478  int* durations, /**< array of durations */
4479  int* demands, /**< array of demands */
4480  int capacity, /**< cumulative capacity */
4481  int hmin, /**< left bound of time axis to be considered (including hmin) */
4482  int hmax, /**< right bound of time axis to be considered (not including hmax) */
4483  SCIP_VAR* var, /**< variable to be considered for upper bound tightening */
4484  int duration, /**< duration of the job */
4485  int demand, /**< demand of the job */
4486  int est, /**< earliest start time of the job */
4487  int lst, /**< latest start time of the flexible part of the job */
4488  int lct, /**< latest completion time of the job */
4489  int begin, /**< begin of the time window under investigation */
4490  int end, /**< end of the time window under investigation */
4491  int energy, /**< available energy for the flexible part of the hob within the time window */
4492  int* bestub, /**< pointer to strope the best upper bound change */
4493  int* inferinfos, /**< pointer to store the inference information which is need for the (best) upper bound change */
4494  SCIP_Bool* initialized, /**< was conflict analysis initialized */
4495  SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4496  SCIP_Bool* cutoff /**< pointer to store if the constraint is infeasible */
4497  )
4498 {
4499  int newub;
4500 
4501  assert(begin >= hmin);
4502  assert(end <= hmax);
4503  assert(est < begin);
4504 
4505  /* check if the time-table edge-finding should infer bounds */
4506  if( !conshdlrdata->ttefinfer )
4507  return SCIP_OKAY;
4508 
4509  /* if flexible part of the job can be processed completely before or after the time window, nothing can be tightened */
4510  if( lst >= end || lct <= begin )
4511  return SCIP_OKAY;
4512 
4513  /* if flexible part runs completely within the time window (assuming it is scheduled on its latest start time), we
4514  * skip since the overload check will do the job
4515  */
4516  if( lst >= begin && lct <= end )
4517  return SCIP_OKAY;
4518 
4519  /* check if the available energy in the time window is to small to handle the flexible part of the job */
4520  if( energy >= demand * (MIN(end, lct) - MAX(begin, lst)) )
4521  return SCIP_OKAY;
4522 
4523  /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is
4524  * present; therefore, we need to add the core;
4525  *
4526  * @note the variable lst define the latest start time of the flexible part of the job; hence we need to compute the
4527  * latest start of the (whole) job
4528  */
4529  energy += computeCoreWithInterval(begin, end, est + duration, lct - duration) * demand;
4530  assert(energy >= 0);
4531 
4532  /* compute a latest start time (upper bound) such that the job consums at most the available energy
4533  *
4534  * @note we can round down the compute duration w.r.t. the available energy
4535  */
4536  assert(demand > 0);
4537  newub = begin - duration + energy / demand;
4538 
4539  /* check if we detected an infeasibility which is the case if the new upper bound is smaller than the current lower
4540  * bound (earliest start time); meaning it is not possible to schedule the job
4541  */
4542  if( newub < est )
4543  {
4544  /* initialize conflict analysis if conflict analysis is applicable */
4546  {
4547  SCIP_Real relaxedbd;
4548 
4549  assert(SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var)) > newub);
4550 
4551  /* it is enough to undershoot the lower bound of the variable by one */
4552  relaxedbd = SCIPvarGetLbLocal(var) - 1.0;
4553 
4554  /* initialize conflict analysis */
4556 
4557  /* added to lower bound (which was undercut be new upper bound) of the variable */
4558  SCIP_CALL( SCIPaddConflictLb(scip, var, NULL) );
4559 
4560  /* analyze the infeasible */
4561  SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
4562  begin, end, var, SCIP_BOUNDTYPE_UPPER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) );
4563 
4564  (*initialized) = TRUE;
4565  }
4566 
4567  (*cutoff) = TRUE;
4568  }
4569  else if( newub < (*bestub) )
4570  {
4571  INFERINFO inferinfo;
4572 
4573  assert(newub < begin);
4574 
4575  inferinfo = getInferInfo(PROPRULE_3_TTEF, begin, end);
4576 
4577  /* construct inference information */
4578  (*inferinfos) = inferInfoToInt(inferinfo);
4579  (*bestub) = newub;
4580  }
4581 
4582  return SCIP_OKAY;
4583 }
4584 
4585 /** propagate the upper bounds and "opportunistically" the lower bounds using the time-table edge-finding algorithm */
4586 static
4588  SCIP* scip, /**< SCIP data structure */
4589  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
4590  int nvars, /**< number of start time variables (activities) */
4591  SCIP_VAR** vars, /**< array of start time variables */
4592  int* durations, /**< array of durations */
4593  int* demands, /**< array of demands */
4594  int capacity, /**< cumulative capacity */
4595  int hmin, /**< left bound of time axis to be considered (including hmin) */
4596  int hmax, /**< right bound of time axis to be considered (not including hmax) */
4597  int* newlbs, /**< array to buffer new lower bounds */
4598  int* newubs, /**< array to buffer new upper bounds */
4599  int* lbinferinfos, /**< array to store the inference information for the lower bound changes */
4600  int* ubinferinfos, /**< array to store the inference information for the upper bound changes */
4601  int* lsts, /**< array of latest start time of the flexible part in the same order as the variables */
4602  int* flexenergies, /**< array of flexible energies in the same order as the variables */
4603  int* perm, /**< permutation of the variables w.r.t. the non-decreasing order of the earliest start times */
4604  int* ests, /**< array with earliest strart times sorted in non-decreasing order */
4605  int* lcts, /**< array with latest completion times sorted in non-decreasing order */
4606  int* coreEnergyAfterEst, /**< core energy after the earliest start times */
4607  int* coreEnergyAfterLct, /**< core energy after the latest completion times */
4608  SCIP_Bool* initialized, /**< was conflict analysis initialized */
4609  SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4610  SCIP_Bool* cutoff /**< pointer to store if the constraint is infeasible */
4611  )
4612 {
4613  int coreEnergyAfterEnd;
4614  int maxavailable;
4615  int minavailable;
4616  int totalenergy;
4617  int nests;
4618  int est;
4619  int lct;
4620  int start;
4621  int end;
4622  int v;
4623 
4624  est = INT_MAX;
4625  lct = INT_MIN;
4626 
4627  /* compute earliest start and latest completion time of all jobs */
4628  for( v = 0; v < nvars; ++v )
4629  {
4630  start = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[v]));
4631  end = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[v])) + durations[v];
4632 
4633  est = MIN(est, start);
4634  lct = MAX(lct, end);
4635  }
4636 
4637  /* adjust the effective time horizon */
4638  hmin = MAX(hmin, est);
4639  hmax = MIN(hmax, lct);
4640 
4641  end = hmax + 1;
4642  coreEnergyAfterEnd = -1;
4643 
4644  maxavailable = (hmax - hmin) * capacity;
4645  minavailable = maxavailable;
4646  totalenergy = computeTotalEnergy(durations, demands, nvars);
4647 
4648  /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */
4649  if( (lcts[0] - ests[nvars-1]) * capacity >= totalenergy )
4650  return SCIP_OKAY;
4651 
4652  nests = nvars;
4653 
4654  /* loop over all variable in non-increasing order w.r.t. the latest completion time; thereby, the latest completion
4655  * times define the end of the time interval under investigation
4656  */
4657  for( v = nvars-1; v >= 0 && !(*cutoff); --v )
4658  {
4659  int flexenergy;
4660  int minbegin;
4661  int lbenergy;
4662  int lbcand;
4663  int i;
4664 
4665  lct = lcts[v];
4666 
4667  /* if the latest completion time is larger then hmax an infeasibility cannot be detected, since after hmax an
4668  * infinity capacity is available; hence we skip that
4669  */
4670  if( lct > hmax )
4671  continue;
4672 
4673  /* if the latest completion time is smaller then hmin we have to stop */
4674  if( lct <= hmin )
4675  {
4676  assert(v == 0 || lcts[v-1] <= lcts[v]);
4677  break;
4678  }
4679 
4680  /* if the latest completion time equals to previous end time, we can continue since this particular interval
4681  * induced by end was just analyzed
4682  */
4683  if( lct == end )
4684  continue;
4685 
4686  assert(lct < end);
4687 
4688  /* In case we only want to detect an overload (meaning no bound propagation) we can skip the interval; this is
4689  * the case if the free energy (the energy which is not occupied by any core) is smaller than the previous minimum
4690  * free energy; if so it means that in the next iterate the free-energy cannot be negative
4691  */
4692  if( !conshdlrdata->ttefinfer && end <= hmax && minavailable < maxavailable )
4693  {
4694  int freeenergy;
4695 
4696  assert(coreEnergyAfterLct[v] >= coreEnergyAfterEnd);
4697  assert(coreEnergyAfterEnd >= 0);
4698 
4699  /* compute the energy which is not consumed by the cores with in the interval [lct, end) */
4700  freeenergy = capacity * (end - lct) - coreEnergyAfterLct[v] + coreEnergyAfterEnd;
4701 
4702  if( freeenergy <= minavailable )
4703  {
4704  SCIPdebugMsg(scip, "skip latest completion time <%d> (minimum available energy <%d>, free energy <%d>)\n", lct, minavailable, freeenergy);
4705  continue;
4706  }
4707  }
4708 
4709  SCIPdebugMsg(scip, "check intervals ending with <%d>\n", lct);
4710 
4711  end = lct;
4712  coreEnergyAfterEnd = coreEnergyAfterLct[v];
4713 
4714  flexenergy = 0;
4715  minavailable = maxavailable;
4716  minbegin = hmax;
4717  lbcand = -1;
4718  lbenergy = 0;
4719 
4720  /* loop over the job in non-increasing order w.r.t. the earliest start time; these earliest start time are
4721  * defining the beginning of the time interval under investigation; Thereby, the time interval gets wider and
4722  * wider
4723  */
4724  for( i = nests-1; i >= 0; --i )
4725  {
4726  SCIP_VAR* var;
4727  int freeenergy;
4728  int duration;
4729  int demand;
4730  int begin;
4731  int idx;
4732  int lst;
4733 
4734  idx = perm[i];
4735  assert(idx >= 0);
4736  assert(idx < nvars);
4737  assert(!(*cutoff));
4738 
4739  /* the earliest start time of the job */
4740  est = ests[i];
4741 
4742  /* if the job starts after the current end, we can skip it and do not need to consider it again since the
4743  * latest completion times (which define end) are scant in non-increasing order
4744  */
4745  if( end <= est )
4746  {
4747  nests--;
4748  continue;
4749  }
4750 
4751  /* check if the interval has a size such that the total energy fits, if so we can skip all intervals with the
4752  * current ending time
4753  */
4754  if( (end - est) * capacity >= totalenergy )
4755  break;
4756 
4757  var = vars[idx];
4758  assert(var != NULL);
4759 
4760  duration = durations[idx];
4761  assert(duration > 0);
4762 
4763  demand = demands[idx];
4764  assert(demand > 0);
4765 
4766  lct = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) + duration;
4767 
4768  /* the latest start time of the free part of the job */
4769  lst = lsts[idx];
4770 
4771  /* in case the earliest start time is equal to minbegin, the job lies completely within the time window under
4772  * investigation; hence the overload check will do the the job
4773  */
4774  assert(est <= minbegin);
4775  if( minavailable < maxavailable && est < minbegin )
4776  {
4777  assert(!(*cutoff));
4778 
4779  /* try to tighten the upper bound */
4780  SCIP_CALL( tightenUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
4781  var, duration, demand, est, lst, lct, minbegin, end, minavailable, &(newubs[idx]), &(ubinferinfos[idx]),
4782  initialized, explanation, cutoff) );
4783 
4784  if( *cutoff )
4785  break;
4786  }
4787 
4788  SCIPdebugMsg(scip, "check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, lst of free part <%d>\n",
4789  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, lst);
4790 
4791  begin = est;
4792  assert(SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var)) == est);
4793 
4794  /* if the earliest start time is smaller than hmin we can stop here since the next job will not decrease the
4795  * free energy
4796  */
4797  if( begin < hmin )
4798  break;
4799 
4800  /* compute the contribution to the flexible energy */
4801  if( lct <= end )
4802  {
4803  /* if the jobs has to finish before the end, all the energy has to be scheduled */
4804  assert(lst >= begin);
4805  assert(flexenergies[idx] >= 0);
4806  flexenergy += flexenergies[idx];
4807  }
4808  else
4809  {
4810  /* the job partly overlaps with the end */
4811  int candenergy;
4812  int energy;
4813 
4814  /* compute the flexible energy which is part of the time interval for sure if the job is scheduled
4815  * w.r.t. latest start time
4816  *
4817  * @note we need to be aware of the effective horizon
4818  */
4819  energy = MIN(flexenergies[idx], demands[idx] * MAX(0, (end - lst)));
4820  assert(end - lst < duration);
4821  assert(energy >= 0);
4822 
4823  /* adjust the flexible energy of the time interval */
4824  flexenergy += energy;
4825 
4826  /* compute the flexible energy of the job which is not part of flexible energy of the time interval */
4827  candenergy = MIN(flexenergies[idx], demands[idx] * (end - begin)) - energy;
4828  assert(candenergy >= 0);
4829 
4830  /* check if we found a better candidate */
4831  if( candenergy > lbenergy )
4832  {
4833  lbenergy = candenergy;
4834  lbcand = idx;
4835  }
4836  }
4837 
4838  SCIPdebugMsg(scip, "time window [%d,%d) flexible energy <%d>\n", begin, end, flexenergy);
4839  assert(coreEnergyAfterEst[i] >= coreEnergyAfterEnd);
4840 
4841  /* compute the energy which is not used yet */
4842  freeenergy = capacity * (end - begin) - flexenergy - coreEnergyAfterEst[i] + coreEnergyAfterEnd;
4843 
4844  /* check overload */
4845  if( freeenergy < 0 )
4846  {
4847  SCIPdebugMsg(scip, "analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
4848 
4849  /* initialize conflict analysis if conflict analysis is applicable */
4851  {
4852  /* analyze infeasibilty */
4854 
4855  SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
4856  begin, end, NULL, SCIP_BOUNDTYPE_UPPER, NULL, SCIP_UNKNOWN,
4857  conshdlrdata->usebdwidening, explanation) );
4858 
4859  (*initialized) = TRUE;
4860  }
4861 
4862  (*cutoff) = TRUE;
4863 
4864  /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */
4865  SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
4866 
4867  break;
4868  }
4869 
4870  /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */
4871  if( lbenergy > 0 && freeenergy < lbenergy )
4872  {
4873  int energy;
4874  int newlb;
4875  int ect;
4876 
4877  ect = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[lbcand])) + durations[lbcand];
4878  lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[lbcand]));
4879 
4880  /* remove the energy of our job from the ... */
4881  energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, end - lsts[lbcand])) * demands[lbcand];
4882 
4883  newlb = end - (int)(energy / demands[lbcand]);
4884 
4885  if( newlb > lst )
4886  {
4887  /* initialize conflict analysis if conflict analysis is applicable */
4889  {
4890  SCIP_Real relaxedbd;
4891 
4892  /* analyze infeasibilty */
4894 
4895  relaxedbd = lst + 1.0;
4896 
4897  /* added to upper bound (which was overcut be new lower bound) of the variable */
4898  SCIP_CALL( SCIPaddConflictUb(scip, vars[lbcand], NULL) );
4899 
4900  SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
4901  begin, end, vars[lbcand], SCIP_BOUNDTYPE_LOWER, NULL, relaxedbd,
4902  conshdlrdata->usebdwidening, explanation) );
4903 
4904  (*initialized) = TRUE;
4905  }
4906 
4907  (*cutoff) = TRUE;
4908  break;
4909  }
4910  else if( newlb > newlbs[lbcand] )
4911  {
4912  INFERINFO inferinfo;
4913 
4914  /* construct inference information */
4915  inferinfo = getInferInfo(PROPRULE_3_TTEF, begin, end);
4916 
4917  /* buffer upper bound change */
4918  lbinferinfos[lbcand] = inferInfoToInt(inferinfo);
4919  newlbs[lbcand] = newlb;
4920  }
4921  }
4922 
4923  /* check if the current interval has a smaller free energy */
4924  if( minavailable > freeenergy )
4925  {
4926  minavailable = freeenergy;
4927  minbegin = begin;
4928  }
4929  assert(minavailable >= 0);
4930  }
4931  }
4932 
4933  return SCIP_OKAY;
4934 }
4935 
4936 /** propagate the lower bounds and "opportunistically" the upper bounds using the time-table edge-finding algorithm */
4937 static
4939  SCIP* scip, /**< SCIP data structure */
4940  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
4941  int nvars, /**< number of start time variables (activities) */
4942  SCIP_VAR** vars, /**< array of start time variables */
4943  int* durations, /**< array of durations */
4944  int* demands, /**< array of demands */
4945  int capacity, /**< cumulative capacity */
4946  int hmin, /**< left bound of time axis to be considered (including hmin) */
4947  int hmax, /**< right bound of time axis to be considered (not including hmax) */
4948  int* newlbs, /**< array to buffer new lower bounds */
4949  int* newubs, /**< array to buffer new upper bounds */
4950  int* lbinferinfos, /**< array to store the inference information for the lower bound changes */
4951  int* ubinferinfos, /**< array to store the inference information for the upper bound changes */
4952  int* ects, /**< array of earliest completion time of the flexible part in the same order as the variables */
4953  int* flexenergies, /**< array of flexible energies in the same order as the variables */
4954  int* perm, /**< permutation of the variables w.r.t. the non-decreasing order of the latest completion times */
4955  int* ests, /**< array with earliest strart times sorted in non-decreasing order */
4956  int* lcts, /**< array with latest completion times sorted in non-decreasing order */
4957  int* coreEnergyAfterEst, /**< core energy after the earliest start times */
4958  int* coreEnergyAfterLct, /**< core energy after the latest completion times */
4959  SCIP_Bool* initialized, /**< was conflict analysis initialized */
4960  SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4961  SCIP_Bool* cutoff /**< pointer to store if the constraint is infeasible */
4962  )
4963 {
4964  int coreEnergyAfterStart;
4965  int maxavailable;
4966  int minavailable;
4967  int totalenergy;
4968  int nlcts;
4969  int begin;
4970  int minest;
4971  int maxlct;
4972  int start;
4973  int end;
4974  int v;
4975 
4976  if( *cutoff )
4977  return SCIP_OKAY;
4978 
4979  begin = hmin - 1;
4980 
4981  minest = INT_MAX;
4982  maxlct = INT_MIN;
4983 
4984  /* compute earliest start and latest completion time of all jobs */
4985  for( v = 0; v < nvars; ++v )
4986  {
4987  start = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[v]));
4988  end = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[v])) + durations[v];
4989 
4990  minest = MIN(minest, start);
4991  maxlct = MAX(maxlct, end);
4992  }
4993 
4994  /* adjust the effective time horizon */
4995  hmin = MAX(hmin, minest);
4996  hmax = MIN(hmax, maxlct);
4997 
4998  maxavailable = (hmax - hmin) * capacity;
4999  totalenergy = computeTotalEnergy(durations, demands, nvars);
5000 
5001  /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */
5002  if( (lcts[0] - ests[nvars-1]) * capacity >= totalenergy )
5003  return SCIP_OKAY;
5004 
5005  nlcts = 0;
5006 
5007  /* loop over all variable in non-decreasing order w.r.t. the earliest start times; thereby, the earliest start times
5008  * define the start of the time interval under investigation
5009  */
5010  for( v = 0; v < nvars; ++v )
5011  {
5012  int flexenergy;
5013  int minend;
5014  int ubenergy;
5015  int ubcand;
5016  int est;
5017  int i;
5018 
5019  est = ests[v];
5020 
5021  /* if the earliest start time is smaller then hmin an infeasibility cannot be detected, since before hmin an
5022  * infinity capacity is available; hence we skip that
5023  */
5024  if( est < hmin )
5025  continue;
5026 
5027  /* if the earliest start time is larger or equal then hmax we have to stop */
5028  if( est >= hmax )
5029  break;
5030 
5031  /* if the latest earliest start time equals to previous start time, we can continue since this particular interval
5032  * induced by start was just analyzed
5033  */
5034  if( est == begin )
5035  continue;
5036 
5037  assert(est > begin);
5038 
5039  SCIPdebugMsg(scip, "check intervals starting with <%d>\n", est);
5040 
5041  begin = est;
5042  coreEnergyAfterStart = coreEnergyAfterEst[v];
5043 
5044  flexenergy = 0;
5045  minavailable = maxavailable;
5046  minend = hmin;
5047  ubcand = -1;
5048  ubenergy = 0;
5049 
5050  /* loop over the job in non-decreasing order w.r.t. the latest completion time; these latest completion times are
5051  * defining the ending of the time interval under investigation; thereby, the time interval gets wider and wider
5052  */
5053  for( i = nlcts; i < nvars; ++i )
5054  {
5055  SCIP_VAR* var;
5056  int freeenergy;
5057  int duration;
5058  int demand;
5059  int idx;
5060  int lct;
5061  int ect;
5062 
5063  idx = perm[i];
5064  assert(idx >= 0);
5065  assert(idx < nvars);
5066  assert(!(*cutoff));
5067 
5068  /* the earliest start time of the job */
5069  lct = lcts[i];
5070 
5071  /* if the job has a latest completion time before the the current start, we can skip it and do not need to
5072  * consider it again since the earliest start times (which define the start) are scant in non-decreasing order
5073  */
5074  if( lct <= begin )
5075  {
5076  nlcts++;
5077  continue;
5078  }
5079 
5080  /* check if the interval has a size such that the total energy fits, if so we can skip all intervals which
5081  * start with current beginning time
5082  */
5083  if( (lct - begin) * capacity >= totalenergy )
5084  break;
5085 
5086  var = vars[idx];
5087  assert(var != NULL);
5088 
5089  duration = durations[idx];
5090  assert(duration > 0);
5091 
5092  demand = demands[idx];
5093  assert(demand > 0);
5094 
5095  est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
5096 
5097  /* the earliest completion time of the flexible part of the job */
5098  ect = ects[idx];
5099 
5100  /* in case the latest completion time is equal to minend, the job lies completely within the time window under
5101  * investigation; hence the overload check will do the the job
5102  */
5103  assert(lct >= minend);
5104  if( minavailable < maxavailable && lct > minend )
5105  {
5106  assert(!(*cutoff));
5107 
5108  /* try to tighten the upper bound */
5109  SCIP_CALL( tightenLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5110  var, duration, demand, est, ect, lct, begin, minend, minavailable, &(newlbs[idx]), &(lbinferinfos[idx]),
5111  initialized, explanation, cutoff) );
5112 
5113  if( *cutoff )
5114  return SCIP_OKAY;
5115  }
5116 
5117  SCIPdebugMsg(scip, "check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, ect of free part <%d>\n",
5118  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, ect);
5119 
5120  end = lct;
5121  assert(SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) + duration == lct);
5122 
5123  /* if the latest completion time is larger than hmax we can stop here since the next job will not decrease the
5124  * free energy
5125  */
5126  if( end > hmax )
5127  break;
5128 
5129  /* compute the contribution to the flexible energy */
5130  if( est >= begin )
5131  {
5132  /* if the jobs has to finish before the end, all the energy has to be scheduled */
5133  assert(ect <= end);
5134  assert(flexenergies[idx] >= 0);
5135  flexenergy += flexenergies[idx];
5136  }
5137  else
5138  {
5139  /* the job partly overlaps with the end */
5140  int candenergy;
5141  int energy;
5142 
5143  /* compute the flexible energy which is part of the time interval for sure if the job is scheduled
5144  * w.r.t. latest start time
5145  *
5146  * @note we need to be aware of the effective horizon
5147  */
5148  energy = MIN(flexenergies[idx], demands[idx] * MAX(0, (ect - begin)));
5149  assert(ect - begin < duration);
5150  assert(energy >= 0);
5151 
5152  /* adjust the flexible energy of the time interval */
5153  flexenergy += energy;
5154 
5155  /* compute the flexible energy of the job which is not part of flexible energy of the time interval */
5156  candenergy = MIN(flexenergies[idx], demands[idx] * (end - begin)) - energy;
5157  assert(candenergy >= 0);
5158 
5159  /* check if we found a better candidate */
5160  if( candenergy > ubenergy )
5161  {
5162  ubenergy = candenergy;
5163  ubcand = idx;
5164  }
5165  }
5166 
5167  SCIPdebugMsg(scip, "time window [%d,%d) flexible energy <%d>\n", begin, end, flexenergy);
5168  assert(coreEnergyAfterLct[i] <= coreEnergyAfterStart);
5169 
5170  /* compute the energy which is not used yet */
5171  freeenergy = capacity * (end - begin) - flexenergy - coreEnergyAfterStart + coreEnergyAfterLct[i];
5172 
5173  /* check overload */
5174  if( freeenergy < 0 )
5175  {
5176  SCIPdebugMsg(scip, "analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
5177 
5178  /* initialize conflict analysis if conflict analysis is applicable */
5180  {
5181  /* analyze infeasibilty */
5183 
5184  SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
5185  begin, end, NULL, SCIP_BOUNDTYPE_UPPER, NULL, SCIP_UNKNOWN,
5186  conshdlrdata->usebdwidening, explanation) );
5187 
5188  (*initialized) = TRUE;
5189  }
5190 
5191  (*cutoff) = TRUE;
5192 
5193  /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */
5194  SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
5195 
5196  return SCIP_OKAY;
5197  }
5198 
5199  /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */
5200  if( ubenergy > 0 && freeenergy < ubenergy )
5201  {
5202  int energy;
5203  int newub;
5204  int lst;
5205 
5206  duration = durations[ubcand];
5207  assert(duration > 0);
5208 
5209  ect = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[ubcand])) + duration;
5210  lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[ubcand]));
5211 
5212  /* remove the energy of our job from the ... */
5213  energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, ects[ubcand] - begin)) * demands[ubcand];
5214 
5215  newub = begin - duration + (int)(energy / demands[ubcand]);
5216 
5217  if( newub < ect - duration )
5218  {
5219  /* initialize conflict analysis if conflict analysis is applicable */
5221  {
5222  SCIP_Real relaxedbd;
5223  /* analyze infeasibilty */
5225 
5226  relaxedbd = ect - duration - 1.0;
5227 
5228  /* added to lower bound (which was undercut be new upper bound) of the variable */
5229  SCIP_CALL( SCIPaddConflictUb(scip, vars[ubcand], NULL) );
5230 
5231  SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
5232  begin, end, vars[ubcand], SCIP_BOUNDTYPE_UPPER, NULL, relaxedbd,
5233  conshdlrdata->usebdwidening, explanation) );
5234 
5235  (*initialized) = TRUE;
5236  }
5237 
5238  (*cutoff) = TRUE;
5239  return SCIP_OKAY;
5240  }
5241  else if( newub < newubs[ubcand] )
5242  {
5243  INFERINFO inferinfo;
5244 
5245  /* construct inference information */
5246  inferinfo = getInferInfo(PROPRULE_3_TTEF, begin, end);
5247 
5248  /* buffer upper bound change */
5249  ubinferinfos[ubcand] = inferInfoToInt(inferinfo);
5250  newubs[ubcand] = newub;
5251  }
5252  }
5253 
5254  /* check if the current interval has a smaller free energy */
5255  if( minavailable > freeenergy )
5256  {
5257  minavailable = freeenergy;
5258  minend = end;
5259  }
5260  assert(minavailable >= 0);
5261  }
5262  }
5263 
5264  return SCIP_OKAY;
5265 }
5266 
5267 /** checks whether the instance is infeasible due to a overload within a certain time frame using the idea of time-table
5268  * edge-finding
5269  *
5270  * @note The algorithm is based on the following two papers:
5271  * - Petr Vilim, "Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources", In: Tobias
5272  * Achterberg and J. Christopher Beck (Eds.), Integration of AI and OR Techniques in Constraint Programming for
5273  * Combinatorial Optimization Problems (CPAIOR 2011), LNCS 6697, pp 230--245
5274  * - Andreas Schutt, Thibaut Feydy, and Peter J. Stuckey, "Explaining Time-Table-Edge-Finding Propagation for the
5275  * Cumulative Resource Constraint (submitted to CPAIOR 2013)
5276  */
5277 static
5279  SCIP* scip, /**< SCIP data structure */
5280  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
5281  SCIP_PROFILE* profile, /**< current core profile */
5282  int nvars, /**< number of start time variables (activities) */
5283  SCIP_VAR** vars, /**< array of start time variables */
5284  int* durations, /**< array of durations */
5285  int* demands, /**< array of demands */
5286  int capacity, /**< cumulative capacity */
5287  int hmin, /**< left bound of time axis to be considered (including hmin) */
5288  int hmax, /**< right bound of time axis to be considered (not including hmax) */
5289  SCIP_CONS* cons, /**< constraint which is propagated (needed to SCIPinferVar**Cons()) */
5290  int* nchgbds, /**< pointer to store the number of bound changes */
5291  SCIP_Bool* initialized, /**< was conflict analysis initialized */
5292  SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
5293  SCIP_Bool* cutoff /**< pointer to store if the constraint is infeasible */
5294  )
5295 {
5296  int* coreEnergyAfterEst;
5297  int* coreEnergyAfterLct;
5298  int* flexenergies;
5299  int* permests;
5300  int* permlcts;
5301  int* lcts;
5302  int* ests;
5303  int* ects;
5304  int* lsts;
5305 
5306  int* newlbs;
5307  int* newubs;
5308  int* lbinferinfos;
5309  int* ubinferinfos;
5310 
5311  int v;
5312 
5313  /* check if a cutoff was already detected */
5314  if( (*cutoff) )
5315  return SCIP_OKAY;
5316 
5317  /* check if at least the basic overload checking should be perfomed */
5318  if( !conshdlrdata->ttefcheck )
5319  return SCIP_OKAY;
5320 
5321  SCIPdebugMsg(scip, "run time-table edge-finding overload checking\n");
5322 
5323  SCIP_CALL( SCIPallocBufferArray(scip, &coreEnergyAfterEst, nvars) );
5324  SCIP_CALL( SCIPallocBufferArray(scip, &coreEnergyAfterLct, nvars) );
5325  SCIP_CALL( SCIPallocBufferArray(scip, &flexenergies, nvars) );
5326  SCIP_CALL( SCIPallocBufferArray(scip, &permlcts, nvars) );
5327  SCIP_CALL( SCIPallocBufferArray(scip, &permests, nvars) );
5328  SCIP_CALL( SCIPallocBufferArray(scip, &lcts, nvars) );
5329  SCIP_CALL( SCIPallocBufferArray(scip, &ests, nvars) );
5330  SCIP_CALL( SCIPallocBufferArray(scip, &ects, nvars) );
5331  SCIP_CALL( SCIPallocBufferArray(scip, &lsts, nvars) );
5332 
5333  SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, nvars) );
5334  SCIP_CALL( SCIPallocBufferArray(scip, &newubs, nvars) );
5335  SCIP_CALL( SCIPallocBufferArray(scip, &lbinferinfos, nvars) );
5336  SCIP_CALL( SCIPallocBufferArray(scip, &ubinferinfos, nvars) );
5337 
5338  /* we need to buffer the bound changes since the propagation algorithm cannot handle new bound dynamically */
5339  for( v = 0; v < nvars; ++v )
5340  {
5341  newlbs[v] = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[v]));
5342  newubs[v] = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[v]));
5343  lbinferinfos[v] = 0;
5344  ubinferinfos[v] = 0;
5345  }
5346 
5347  /* collect earliest start times, latest completion time, and free energy contributions */
5348  collectDataTTEF(scip, nvars, vars, durations, demands, hmin, hmax, permests, ests, permlcts, lcts, ects, lsts, flexenergies);
5349 
5350  /* sort the earliest start times and latest completion in non-decreasing order */
5351  SCIPsortIntInt(ests, permests, nvars);
5352  SCIPsortIntInt(lcts, permlcts, nvars);
5353 
5354  /* compute for the different earliest start and latest completion time the core energy of the corresponding time
5355  * points
5356  */
5357  SCIP_CALL( computeCoreEngeryAfter(scip, profile, nvars, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct) );
5358 
5359  /* propagate the upper bounds and "opportunistically" the lower bounds */
5360  SCIP_CALL( propagateUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5361  newlbs, newubs, lbinferinfos, ubinferinfos, lsts, flexenergies,
5362  permests, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );
5363 
5364  /* propagate the lower bounds and "opportunistically" the upper bounds */
5365  SCIP_CALL( propagateLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5366  newlbs, newubs, lbinferinfos, ubinferinfos, ects, flexenergies,
5367  permlcts, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );
5368 
5369  /* apply the buffer bound changes */
5370  for( v = 0; v < nvars && !(*cutoff); ++v )
5371  {
5372  SCIP_Bool infeasible;
5373  SCIP_Bool tightened;
5374 
5375  SCIP_CALL( SCIPinferVarLbCons(scip, vars[v], (SCIP_Real)newlbs[v], cons, lbinferinfos[v], TRUE, &infeasible, &tightened) );
5376 
5377  /* since we change first the lower bound of the variable an infeasibilty should be detected */
5378  assert(!infeasible);
5379 
5380  if( tightened )
5381  {
5382  (*nchgbds)++;
5383 
5384  /* for the statistic we count the number of times a cutoff was detected due the time-time */
5386  }
5387 
5388 
5389  SCIP_CALL( SCIPinferVarUbCons(scip, vars[v], (SCIP_Real)newubs[v], cons, ubinferinfos[v], TRUE, &infeasible, &tightened) );
5390 
5391  /* since upper bound was compute w.r.t. the "old" bound the previous lower bound update together with this upper
5392  * bound update can be infeasible
5393  */
5394  if( infeasible )
5395  {
5397  {
5398  INFERINFO inferinfo;
5399  SCIP_VAR* var;
5400  int begin;
5401  int end;
5402 
5403  var = vars[v];
5404  assert(var != NULL);
5405 
5406  /* initialize conflict analysis */
5408 
5409  /* convert int to inference information */
5410  inferinfo = intToInferInfo(ubinferinfos[v]);
5411 
5412  /* collect time window from inference information */
5413  begin = inferInfoGetData1(inferinfo);
5414  end = inferInfoGetData2(inferinfo);
5415  assert(begin < end);
5416 
5417  /* added to lower bound (which was undercut be new upper bound) of the variable */
5418  SCIP_CALL( SCIPaddConflictLb(scip, var, NULL) );
5419 
5420  /* analysis the upper bound change */
5421  SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
5422  begin, end, var, SCIP_BOUNDTYPE_UPPER, NULL, SCIPvarGetLbLocal(vars[v]) - 1.0,
5423  conshdlrdata->usebdwidening, explanation) );
5424 
5425  (*initialized) = TRUE;
5426  }
5427 
5428  /* for the statistic we count the number of times a cutoff was detected due the time-time */
5429  SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutoffoverloadTTEF++ );
5430 
5431  (*cutoff) = TRUE;
5432  break;
5433  }
5434 
5435  if( tightened )
5436  {
5437  (*nchgbds)++;
5438 
5439  /* for the statistic we count the number of times a cutoff was detected due the time-time */
5441  }
5442  }
5443 
5444  SCIPfreeBufferArray(scip, &ubinferinfos);
5445  SCIPfreeBufferArray(scip, &lbinferinfos);
5446  SCIPfreeBufferArray(scip, &newubs);
5447  SCIPfreeBufferArray(scip, &newlbs);
5448 
5449  /* free buffer arrays */
5450  SCIPfreeBufferArray(scip, &lsts);
5451  SCIPfreeBufferArray(scip, &ects);
5452  SCIPfreeBufferArray(scip, &ests);
5453  SCIPfreeBufferArray(scip, &lcts);
5454  SCIPfreeBufferArray(scip, &permests);
5455  SCIPfreeBufferArray(scip, &permlcts);
5456  SCIPfreeBufferArray(scip, &flexenergies);
5457  SCIPfreeBufferArray(scip, &coreEnergyAfterLct);
5458  SCIPfreeBufferArray(scip, &coreEnergyAfterEst);
5459 
5460  return SCIP_OKAY;
5461 }
5462 
5463 /** a cumulative condition is not satisfied if its capacity is exceeded at a time where jobs cannot be shifted (core)
5464  * anymore we build up a cumulative profile of all cores of jobs and try to improve bounds of all jobs; also known as
5465  * time table propagator
5466  */
5467 static
5469  SCIP* scip, /**< SCIP data structure */
5470  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
5471  SCIP_PROFILE* profile, /**< core profile */
5472  int nvars, /**< number of start time variables (activities) */
5473  SCIP_VAR** vars, /**< array of start time variables */
5474  int* durations, /**< array of durations */
5475  int* demands, /**< array of demands */
5476  int capacity, /**< cumulative capacity */
5477  int hmin, /**< left bound of time axis to be considered (including hmin) */
5478  int hmax, /**< right bound of time axis to be considered (not including hmax) */
5479  SCIP_CONS* cons, /**< constraint which is propagated (needed to SCIPinferVar**Cons()) */
5480  int* nchgbds, /**< pointer to store the number of bound changes */
5481  SCIP_Bool* initialized, /**< was conflict analysis initialized */
5482  SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
5483  SCIP_Bool* cutoff /**< pointer to store if the constraint is infeasible */
5484  )
5485 {
5486  SCIP_Bool infeasible;
5487  int v;
5488 
5489  assert(scip != NULL);
5490  assert(nvars > 0);
5491  assert(cons != NULL);
5492  assert(cutoff != NULL);
5493 
5494  /* check if already a cutoff was detected */
5495  if( (*cutoff) )
5496  return SCIP_OKAY;
5497 
5498  /* check if the time tabling should infer bounds */
5499  if( !conshdlrdata->ttinfer )
5500  return SCIP_OKAY;
5501 
5502  assert(*initialized == FALSE);
5503 
5504  SCIPdebugMsg(scip, "propagate cores of cumulative condition of constraint <%s>[%d,%d) <= %d\n",
5505  SCIPconsGetName(cons), hmin, hmax, capacity);
5506 
5507  infeasible = FALSE;
5508 
5509  /* if core profile is empty; nothing to do */
5510  if( SCIPprofileGetNTimepoints(profile) <= 1 )
5511  return SCIP_OKAY;
5512 
5513  /* start checking each job whether the bounds can be improved */
5514  for( v = 0; v < nvars; ++v )
5515  {
5516  SCIP_VAR* var;
5517  int demand;
5518  int duration;
5519  int begin;
5520  int end;
5521  int est;
5522  int lst;
5523 
5524  var = vars[v];
5525  assert(var != NULL);
5526 
5527  duration = durations[v];
5528  assert(duration > 0);
5529 
5530  /* collect earliest and latest start time */
5531  est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
5532  lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
5533 
5534  /* check if the start time variables is already fixed; in that case we can ignore the job */
5535  if( est == lst )
5536  continue;
5537 
5538  /* check if the job runs completely outside of the effective horizon [hmin, hmax); if so skip it */
5539  if( lst + duration <= hmin || est >= hmax )
5540  continue;
5541 
5542  /* compute core interval w.r.t. effective time horizon */
5543  begin = MAX(hmin, lst);
5544  end = MIN(hmax, est + duration);
5545 
5546  demand = demands[v];
5547  assert(demand > 0);
5548 
5549  /* if the job has a core, remove it first */
5550  if( begin < end )
5551  {
5552  SCIPdebugMsg(scip, "variable <%s>[%g,%g] (duration %d, demand %d): remove core [%d,%d)\n",
5553  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, begin, end);
5554 
5555  SCIP_CALL( SCIPprofileDeleteCore(profile, begin, end, demand) );
5556  }
5557 
5558  /* first try to update the earliest start time */
5559  SCIP_CALL( coretimesUpdateLb(scip, nvars, vars, durations, demands, capacity, hmin, hmax, cons,
5560  profile, v, nchgbds, conshdlrdata->usebdwidening, initialized, explanation, cutoff) );
5561 
5562  if( *cutoff )
5563  break;
5564 
5565  /* second try to update the latest start time */
5566  SCIP_CALL( coretimesUpdateUb(scip, var, duration, demand, capacity, cons,
5567  profile, v, nchgbds) );
5568 
5569  if( *cutoff )
5570  break;
5571 
5572  /* collect the potentially updated earliest and latest start time */
5573  est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
5574  lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var));
5575 
5576  /* compute core interval w.r.t. effective time horizon */
5577  begin = MAX(hmin, lst);
5578  end = MIN(hmax, est + duration);
5579 
5580  /* after updating the bound we might have a new core */
5581  if( begin < end )
5582  {
5583  int pos;
5584 
5585  SCIPdebugMsg(scip, "variable <%s>[%d,%d] (duration %d, demand %d): add core [%d,%d)\n",
5586  SCIPvarGetName(var), est, lst, duration, demand, begin, end);
5587 
5588  SCIP_CALL( SCIPprofileInsertCore(profile, begin, end, demand, &pos, &infeasible) );
5589 
5590  if( infeasible )
5591  {
5592  /* use conflict analysis to analysis the core insertion which was infeasible */
5593  SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
5594  var, duration, demand, SCIPprofileGetTime(profile, pos), conshdlrdata->usebdwidening, initialized, explanation) );
5595 
5596  if( explanation != NULL )
5597  explanation[v] = TRUE;
5598 
5599  (*cutoff) = TRUE;
5600 
5601  /* for the statistic we count the number of times a cutoff was detected due the time-time */
5602  SCIPstatistic( SCIPconshdlrGetData(SCIPfindConshdlr(scip, CONSHDLR_NAME))->ncutofftimetable++ );
5603 
5604  break;
5605  }
5606  }
5607  }
5608 
5609  return SCIP_OKAY;
5610 }
5611 
5612 
5613 /** node data structure for the binary tree used for edgefinding (with overload checking) */
5614 struct SCIP_NodeData
5615 {
5616  SCIP_VAR* var; /**< start time variable of the job if the node data belongs to a leaf, otherwise NULL */
5617  SCIP_Real key; /**< key which is to insert the corresponding search node */
5618  int est; /**< earliest start time if the node data belongs to a leaf */
5619  int lct; /**< latest completion time if the node data belongs to a leaf */
5620  int demand; /**< demand of the job if the node data belongs to a leaf */
5621  int duration; /**< duration of the job if the node data belongs to a leaf */
5622  int leftadjust; /**< left adjustments of the duration w.r.t. hmin */
5623  int rightadjust; /**< right adjustments of the duration w.r.t. hmax */
5624  int enveloptheta; /**< the maximal energy of a subset of jobs part of the theta set */
5625  int energytheta; /**< energy of the subset of the jobs which are part of theta set */
5626  int energylambda;
5627  int enveloplambda;
5628  int idx; /**< index of the start time variable in the (global) variable array */
5629  SCIP_Bool intheta; /**< belongs the node to the theta set (otherwise to the lambda set) */
5630 };
5631 typedef struct SCIP_NodeData SCIP_NODEDATA;
5633 /** creates a node data structure */
5634 static
5636  SCIP* scip, /**< SCIP data structure */
5637  SCIP_NODEDATA** nodedata /**< pointer to store the create node data */
5638  )
5639 {
5640  SCIP_CALL( SCIPallocBuffer(scip, nodedata) );
5641  (*nodedata)->var = NULL;
5642  (*nodedata)->key = SCIP_INVALID;
5643  (*nodedata)->est = INT_MIN;
5644  (*nodedata)->lct = INT_MAX;
5645  (*nodedata)->duration = 0;
5646  (*nodedata)->demand = 0;
5647  (*nodedata)->enveloptheta = -1;
5648  (*nodedata)->energytheta = 0;
5649  (*nodedata)->enveloplambda = -1;
5650  (*nodedata)->energylambda = -1;
5651  (*nodedata)->idx = -1;
5652  (*nodedata)->intheta = TRUE;
5653 
5654  return SCIP_OKAY;
5655 }
5656 
5657 /** frees a node data structure */
5658 static
5659 void freeNodedata(
5660  SCIP* scip, /**< SCIP data structure */
5661  SCIP_NODEDATA** nodedata /**< pointer to store node data which should be freed */
5662  )
5663 {
5664  if( *nodedata != NULL )
5665  {
5666  SCIPfreeBuffer(scip, nodedata);
5667  }
5668 }
5669 
5670 /** update node data structure strating form the given node along the path to the root node */
5671 static
5673  SCIP* scip, /**< SCIP data structure */
5674  SCIP_BTNODE* node /**< search node which inserted */
5675  )
5676 {
5677  SCIP_BTNODE* left;
5678  SCIP_BTNODE* right;
5679  SCIP_NODEDATA* nodedata;
5680  SCIP_NODEDATA* leftdata;
5681  SCIP_NODEDATA* rightdata;
5682 
5683  SCIPdebugMsg(scip, "update envelop starting from node <%p>\n", (void*)node);
5684 
5685  if( SCIPbtnodeIsLeaf(node) )
5686  node = SCIPbtnodeGetParent(node);
5687 
5688  while( node != NULL )
5689  {
5690  /* get node data */
5691  nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(node);
5692  assert(nodedata != NULL);
5693 
5694  /* collect node data from left node */
5695  left = SCIPbtnodeGetLeftchild(node);
5696  assert(left != NULL);
5697  leftdata = (SCIP_NODEDATA*)SCIPbtnodeGetData(left);
5698  assert(leftdata != NULL);
5699 
5700  /* collect node data from right node */
5701  right = SCIPbtnodeGetRightchild(node);
5702  assert(right != NULL);
5703  rightdata = (SCIP_NODEDATA*)SCIPbtnodeGetData(right);
5704  assert(rightdata != NULL);
5705 
5706  /* update envelop and energy */
5707  if( leftdata->enveloptheta >= 0 )
5708  {
5709  assert(rightdata->energytheta != -1);
5710  nodedata->enveloptheta = MAX(leftdata->enveloptheta + rightdata->energytheta, rightdata->enveloptheta);
5711  }
5712  else
5713  nodedata->enveloptheta = rightdata->enveloptheta;
5714 
5715  assert(leftdata->energytheta != -1);
5716  assert(rightdata->energytheta != -1);
5717  nodedata->energytheta = leftdata->energytheta + rightdata->energytheta;
5718 
5719  if( leftdata->enveloplambda >= 0 )
5720  {
5721  assert(rightdata->energytheta != -1);
5722  nodedata->enveloplambda = MAX(leftdata->enveloplambda + rightdata->energytheta, rightdata->enveloplambda);
5723  }
5724  else
5725  nodedata->enveloplambda = rightdata->enveloplambda;
5726 
5727  if( leftdata->enveloptheta >= 0 && rightdata->energylambda >= 0 )
5728  nodedata->enveloplambda = MAX(nodedata->enveloplambda, leftdata->enveloptheta + rightdata->energylambda);
5729 
5730  SCIPdebugMsg(scip, "node <%p> lambda envelop %d\n", (void*)node, nodedata->enveloplambda);
5731 
5732  if( leftdata->energylambda >= 0 && rightdata->energylambda >= 0 )
5733  {
5734  assert(rightdata->energytheta != -1);
5735  assert(leftdata->energytheta != -1);
5736  nodedata->energylambda = MAX(leftdata->energylambda + rightdata->energytheta, leftdata->energytheta + rightdata->energylambda);
5737  }
5738  else if( rightdata->energylambda >= 0 )
5739  {
5740  assert(leftdata->energytheta != -1);
5741  nodedata->energylambda = leftdata->energytheta + rightdata->energylambda;
5742  }
5743  else if( leftdata->energylambda >= 0 )
5744  {
5745  assert(rightdata->energytheta != -1);
5746  nodedata->energylambda = leftdata->energylambda + rightdata->energytheta;
5747  }
5748  else
5749  nodedata->energylambda = -1;
5750 
5751  /* go to parent */
5752  node = SCIPbtnodeGetParent(node);
5753  }
5754 
5755  SCIPdebugMsg(scip, "updating done\n");
5756 
5757  return SCIP_OKAY;
5758 }
5759 
5760 /** updates the key of the first parent on the trace which comes from left */
5761 static
5762 void updateKeyOnTrace(
5763  SCIP_BTNODE* node, /**< node to start the trace */
5764  SCIP_Real key /**< update search key */
5765  )
5766 {
5767  assert(node != NULL);
5768 
5769  while( !SCIPbtnodeIsRoot(node) )
5770  {
5771  SCIP_BTNODE* parent;
5772 
5773  parent = SCIPbtnodeGetParent(node);
5774  assert(parent != NULL);
5775 
5776  if( SCIPbtnodeIsLeftchild(node) )
5777  {
5778  SCIP_NODEDATA* nodedata;
5779 
5780  nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(parent);
5781  assert(nodedata != NULL);
5782 
5783  nodedata->key = key;
5784  return;
5785  }
5786 
5787  node = parent;
5788  }
5789 }
5790 
5791 
5792 /** deletes the given node and updates all envelops */
5793 static
5795  SCIP* scip, /**< SCIP data structure */
5796  SCIP_BT* tree, /**< binary tree */
5797  SCIP_BTNODE* node /**< node to be deleted */
5798  )
5799 {
5800  SCIP_BTNODE* parent;
5801  SCIP_BTNODE* grandparent;
5802  SCIP_BTNODE* sibling;
5803 
5804  assert(scip != NULL);
5805  assert(tree != NULL);
5806  assert(node != NULL);
5807 
5808  assert(SCIPbtnodeIsLeaf(node));
5809  assert(!SCIPbtnodeIsRoot(node));
5810 
5811  SCIPdebugMsg(scip, "delete node <%p>\n", (void*)node);
5812 
5813  parent = SCIPbtnodeGetParent(node);
5814  assert(parent != NULL);
5815  if( SCIPbtnodeIsLeftchild(node) )
5816  {
5817  sibling = SCIPbtnodeGetRightchild(parent);
5818  SCIPbtnodeSetRightchild(parent, NULL);
5819  }
5820  else
5821  {
5822  sibling = SCIPbtnodeGetLeftchild(parent);
5823  SCIPbtnodeSetLeftchild(parent, NULL);
5824  }
5825  assert(sibling != NULL);
5826 
5827  grandparent = SCIPbtnodeGetParent(parent);
5828 
5829  if( grandparent != NULL )
5830  {
5831  /* reset parent of sibling */
5832  SCIPbtnodeSetParent(sibling, grandparent);
5833 
5834  /* reset child of grandparent to sibling */
5835  if( SCIPbtnodeIsLeftchild(parent) )
5836  {
5837  SCIPbtnodeSetLeftchild(grandparent, sibling);
5838  }
5839  else
5840  {
5841  SCIP_NODEDATA* nodedata;
5842 
5843  assert(SCIPbtnodeIsRightchild(parent));
5844  SCIPbtnodeSetRightchild(grandparent, sibling);
5845 
5846  nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(sibling);
5847 
5848  updateKeyOnTrace(grandparent, nodedata->key);
5849  }
5850 
5851  SCIP_CALL( updateEnvelop(scip, grandparent) );
5852  }
5853  else
5854  {
5855  SCIPbtnodeSetParent(sibling, NULL);
5856 
5857  SCIPbtSetRoot(tree, sibling);
5858  }
5859 
5860 
5861  SCIPbtnodeFree(tree, &parent);
5862 
5863  return SCIP_OKAY;
5864 }
5865 
5866 /** moves a node form the theta set into the lambda set and updates the envelops */
5867 static
5869  SCIP* scip, /**< SCIP data structure */
5870  SCIP_BT* tree, /**< binary tree */
5871  SCIP_BTNODE* node /**< node to move into the lambda set */
5872  )
5873 {
5874  SCIP_NODEDATA* nodedata;
5875 
5876  assert(scip != NULL);
5877  assert(tree != NULL);
5878  assert(node != NULL);
5879 
5880  nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(node);
5881  assert(nodedata != NULL);
5882  assert(nodedata->intheta);
5883 
5884  /* move the contributions form the theta set into the lambda set */
5885  assert(nodedata->enveloptheta != -1);
5886  assert(nodedata->energytheta != -1);
5887  assert(nodedata->enveloplambda == -1);
5888  assert(nodedata->energylambda == -1);
5889  nodedata->enveloplambda = nodedata->enveloptheta;
5890  nodedata->energylambda = nodedata->energytheta;
5891 
5892  nodedata->enveloptheta = -1;
5893  nodedata->energytheta = 0;
5894  nodedata->intheta = FALSE;
5895 
5896  /* update the energy and envelop values on trace */
5897  SCIP_CALL( updateEnvelop(scip, node) );
5898 
5899  return SCIP_OKAY;
5900 }
5901 
5902 /** inserts a node into the theta set and update the envelops */
5903 static
5905  SCIP* scip, /**< SCIP data structure */
5906  SCIP_BT* tree, /**< binary tree */
5907  SCIP_BTNODE* node, /**< node to insert */
5908  SCIP_NODEDATA** nodedatas, /**< array of node data */
5909  int* nnodedatas /**< pointer to number of node data */
5910  )
5911 {
5912  /* if the tree is empty the node will be the root node */
5913  if( SCIPbtIsEmpty(tree) )
5914  {
5915  SCIPbtSetRoot(tree, node);
5916  }
5917  else
5918  {
5919  SCIP_NODEDATA* newnodedata;
5920  SCIP_NODEDATA* leafdata;
5921  SCIP_NODEDATA* nodedata;
5922  SCIP_BTNODE* leaf;
5923  SCIP_BTNODE* newnode;
5924  SCIP_BTNODE* parent;
5925 
5926  leaf = SCIPbtGetRoot(tree);
5927  assert(leaf != NULL);
5928 
5929  leafdata = (SCIP_NODEDATA*)SCIPbtnodeGetData(leaf);
5930  assert(leafdata != NULL);
5931 
5932  nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(node);
5933  assert(nodedata != NULL);
5934  assert(nodedata->intheta);
5935 
5936  /* find the position to insert the node */
5937  while( !SCIPbtnodeIsLeaf(leaf) )
5938  {
5939  if( nodedata->key < leafdata->key )
5940  leaf = SCIPbtnodeGetLeftchild(leaf);
5941  else
5942  leaf = SCIPbtnodeGetRightchild(leaf);
5943 
5944  leafdata = (SCIP_NODEDATA*)SCIPbtnodeGetData(leaf);
5945  assert(leafdata != NULL);
5946  }
5947 
5948  assert(leaf != NULL);
5949  assert(leaf != node);
5950 
5951  /* create node data */
5952  SCIP_CALL( createNodedata(scip, &newnodedata) );
5953 
5954  /* create a new node */
5955  SCIP_CALL( SCIPbtnodeCreate(tree, &newnode, newnodedata) );
5956  assert(newnode != NULL);
5957 
5958  /* store node data to be able to delete them latter */
5959  nodedatas[*nnodedatas] = newnodedata;
5960  (*nnodedatas)++;
5961 
5962  parent = SCIPbtnodeGetParent(leaf);
5963 
5964  if( parent != NULL )
5965  {
5966  SCIPbtnodeSetParent(newnode, parent);
5967 
5968  /* check if the node is the left child */
5969  if( SCIPbtnodeGetLeftchild(parent) == leaf )
5970  {
5971  SCIPbtnodeSetLeftchild(parent, newnode);
5972  }
5973  else
5974  {
5975  SCIPbtnodeSetRightchild(parent, newnode);
5976  }
5977  }
5978  else
5979  SCIPbtSetRoot(tree, newnode);
5980 
5981  if( nodedata->key < leafdata->key )
5982  {
5983  /* node is on the left */
5984  SCIPbtnodeSetLeftchild(newnode, node);
5985  SCIPbtnodeSetRightchild(newnode, leaf);
5986  newnodedata->key = nodedata->key;
5987  }
5988  else
5989  {
5990  /* leaf is on the left */
5991  SCIPbtnodeSetLeftchild(newnode, leaf);
5992  SCIPbtnodeSetRightchild(newnode, node);
5993  newnodedata->key = leafdata->key;
5994  }
5995 
5996  SCIPbtnodeSetParent(leaf, newnode);
5997  SCIPbtnodeSetParent(node, newnode);
5998  }
5999 
6000  /* update envelop */
6001  SCIP_CALL( updateEnvelop(scip, node) );
6002 
6003  return SCIP_OKAY;
6004 }
6005 
6006 /** returns the leaf responsible for the lambda energy */
6007 static
6009  SCIP_BTNODE* node /**< node which defines the subtree beases on the lambda energy */
6010  )
6011 {
6012  SCIP_BTNODE* left;
6013  SCIP_BTNODE* right;
6014  SCIP_NODEDATA* nodedata;
6015  SCIP_NODEDATA* leftdata;
6016  SCIP_NODEDATA* rightdata;
6017 
6018  assert(node != NULL);
6019 
6020  nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(node);
6021  assert(nodedata != NULL);
6022 
6023  /* check if the node is the (responsible) leaf */
6024  if( SCIPbtnodeIsLeaf(node) )
6025  {
6026  assert(!nodedata->intheta);
6027  return node;
6028  }
6029 
6030  left = SCIPbtnodeGetLeftchild(node);
6031  assert(left != NULL);
6032 
6033  leftdata = (SCIP_NODEDATA*)SCIPbtnodeGetData(left);
6034  assert(leftdata != NULL);
6035 
6036  right = SCIPbtnodeGetRightchild(node);
6037  assert(right != NULL);
6038 
6039  rightdata = (SCIP_NODEDATA*)SCIPbtnodeGetData(right);
6040  assert(rightdata != NULL);
6041 
6042  assert(nodedata->energylambda != -1);
6043  assert(rightdata->energytheta != -1);
6044 
6045  if( leftdata->energylambda >= 0 && nodedata->energylambda == leftdata->energylambda + rightdata->energytheta )
6047 
6048  assert(leftdata->energytheta != -1);
6049  assert(rightdata->energylambda != -1);
6050  assert(nodedata->energylambda == leftdata->energytheta + rightdata->energylambda);
6051 
6053 }
6054 
6055 /** returns the leaf responsible for the lambda envelop */
6056 static
6058  SCIP_BTNODE* node /**< node which defines the subtree beases on the lambda envelop */
6059  )
6060 {
6061  SCIP_BTNODE* left;
6062  SCIP_BTNODE* right;
6063  SCIP_NODEDATA* nodedata;
6064  SCIP_NODEDATA* leftdata;
6065  SCIP_NODEDATA* rightdata;
6066 
6067  assert(node != NULL);
6068 
6069  nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(node);
6070  assert(nodedata != NULL);
6071 
6072  /* check if the node is the (responsible) leaf */
6073  if( SCIPbtnodeIsLeaf(node) )
6074  {
6075  assert(!nodedata->intheta);
6076  return node;
6077  }
6078 
6079  left = SCIPbtnodeGetLeftchild(node);
6080  assert(left != NULL);
6081 
6082  leftdata = (SCIP_NODEDATA*)SCIPbtnodeGetData(left);
6083  assert(leftdata != NULL);
6084 
6085  right = SCIPbtnodeGetRightchild(node);
6086  assert(right != NULL);
6087 
6088  rightdata = (SCIP_NODEDATA*)SCIPbtnodeGetData(right);
6089  assert(rightdata != NULL);
6090 
6091  assert(nodedata->enveloplambda != -1);
6092  assert(rightdata->energytheta != -1);
6093 
6094  /* check if the left or right child is the one defining the envelop for the lambda set */
6095  if( leftdata->enveloplambda >= 0 && nodedata->enveloplambda == leftdata->enveloplambda + rightdata->energytheta )
6097  else if( leftdata->enveloptheta >= 0 && rightdata->energylambda >= 0
6098  && nodedata->enveloplambda == leftdata->enveloptheta + rightdata->energylambda )
6100 
6101  assert(rightdata->enveloplambda != -1);
6102  assert(nodedata->enveloplambda == rightdata->enveloplambda);
6103 
6105 }
6106 
6107 
6108 /** reports all elements from set theta to generate a conflicting set */
6109 static
6110 void collectThetaSubtree(
6111  SCIP_BTNODE* node, /**< node within a theta subtree */
6112  SCIP_BTNODE** omegaset, /**< array to store the collected jobs */
6113  int* nelements, /**< pointer to store the number of elements in omegaset */
6114  int* est, /**< pointer to store the earliest start time of the omega set */
6115  int* lct, /**< pointer to store the latest start time of the omega set */
6116  int* energy /**< pointer to store the energy of the omega set */
6117  )
6118 {
6119  SCIP_NODEDATA* nodedata;
6120 
6121  nodedata = (SCIP_NODEDATA*)SCIPbtnodeGetData(node);
6122  assert(nodedata != NULL);
6123 
6124  if( !SCIPbtnodeIsLeaf(node) )
6125  {
6126  collectThetaSubtree(SCIPbtnodeGetLeftchild(node), omegaset, nelements, est, lct, energy);
6127  collectThetaSubtree(SCIPbtnodeGetRightchild(node), omegaset, nelements, est, lct, energy);
6128  }
6129  else if( nodedata->intheta )
6130  {
6131  assert(nodedata->var != NULL);
6132  SCIPdebugMessage("add variable <%s> as elements %d to omegaset\n", SCIPvarGetName(nodedata->var), *nelements);
6133 
6134  omegaset[*nelements] = node;
6135  (*est) = MIN(*est, nodedata->est);
6136  (*lct) = MAX(*lct, nodedata->lct);
6137  (*energy) += (nodedata->duration - nodedata->leftadjust - nodedata->rightadjust) * nodedata->demand;
6138  (*nelements)++;
6139  }
6140 }
6141 
6142 
6143 /** collect the jobs (omega set) which are contribute to theta envelop from the theta set */
6144 static
6145 void traceThetaEnvelop(