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