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