Scippy

SCIP

Solving Constraint Integer Programs

cons_optcumulative.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_optcumulative.c
17  * @ingroup CONSHDLRS
18  * @brief constraint handler for cumulative constraints with optional activities
19  * @author Chris Beck
20  * @author Stefan Heinz
21  *
22  * Given a set of jobs \f$J\f$. Each job~\f$j\f$ has a binary variables \f$x_j\f$ which is one if this job is scheduled
23  * on that machine (otherwise it is zero), an integer start time variables \f$S_j\f$, a processing time \f$p_j\f$, and a
24  * demands \f$d_j\f$. Besides that an integer resource capacity \f$C\f$.
25  *
26  * The optcumulative enfoces the cumulative conditions for those jobs which are assigned to that machine. Let \f$J'\f$
27  * be the subset of jobs assigned to that optcumulative constraint, then the cumulative constraint ensures that for
28  * each point in time \f$t\f$ \f$\sum_{j\in J': S_j \leq t < S_j + p_j} d_j \leq C\f$ holds.
29  *
30  *
31  * Propagation:
32  *
33  *
34  * LP Relaxation:
35  *
36  * - let est(J) the earliest start time of all jobs of set \f$J\f$ and lct(J) the latest completion time for all jobs of
37  * set \f$J\f$, then the following linear constraint has to hold
38  * \f$\sum_{j\in J} p_j \cdot d_j \leq (lct(J) - est(J)) \cdot C\f$
39  *
40  */
41 
42 /*
43  * @todo Find subsets \f$J'\f$ of jobs which are together not schedulable and create knapsack constraint
44  * \f$\sum_{j\in J'} p_j \cdot d_j \leq (lct(J') - est(J')) \cdot C\f$
45  * @todo Use a rectangle relaxation to determine if jobs which run in a certain interval can be packed feasible. this
46  * relaxation ignores the actual start and end time of a job.
47  * @todo Adjsut relaxation after jobs are removed during search
48  *
49  */
50 
51 
52 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
53 
54 #include <assert.h>
55 #include <string.h>
56 
57 #include "cons_optcumulative.h"
58 
59 #include "scip/cons_cumulative.h"
60 #include "scip/cons_knapsack.h"
61 #include "scip/scipdefplugins.h"
62 
63 /**@name Constraint handler properties
64  *
65  * @{
66  */
67 
68 /* constraint handler properties */
69 #define CONSHDLR_NAME "optcumulative"
70 #define CONSHDLR_DESC "constraint handler for cumulative constraints with optional activities"
71 #define CONSHDLR_SEPAPRIORITY 0 /**< priority of the constraint handler for separation */
72 #define CONSHDLR_ENFOPRIORITY -2060000 /**< priority of the constraint handler for constraint enforcing */
73 #define CONSHDLR_CHECKPRIORITY -3100000 /**< priority of the constraint handler for checking feasibility */
74 #define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
75 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
76 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
77  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
78 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
79 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
80 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
81 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
82 
83 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
84 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM
85 
86 /**@} */
87 
88 /**@name Event handler properties
89  *
90  * @{
91  */
92 
93 #define EVENTHDLR_BINVARS_NAME "optcumulativebinvars"
94 #define EVENTHDLR_BINVARS_DESC "bound change event handler for binary variables of optcumulative constraints"
95 
96 #define EVENTHDLR_INTVARS_NAME "optcumulativeintvars"
97 #define EVENTHDLR_INTVARS_DESC "bound change event handler for integer variables of optcumulative constraints"
98 
99 /**@} */
100 
101 /**@name Default parameter values
102  *
103  * @{
104  */
105 
106 #define DEFAULT_ROWRELAX FALSE /**< add linear relaxation as LP row (otherwise a knapsack constraint is created)? */
107 #define DEFAULT_CONFLICTANALYSIS TRUE /**< participate in conflict analysis?" */
108 #define DEFAULT_INTERVALRELAX TRUE /**< create a relaxation for each start and end time point interval */
110 /**@} */
111 
112 
113 /*
114  * Data structures
115  */
116 
117 /** constraint data for optcumulative constraints */
118 struct SCIP_ConsData
119 {
120  SCIP_VAR** vars; /**< array of variable representing the start time of each job */
121  SCIP_VAR** binvars; /**< array of variable representing if the job has to be processed on this machine */
122  SCIP_Bool* downlocks; /**< array to store if the start time variable has a down lock */
123  SCIP_Bool* uplocks; /**< array to store if the start time variable has an up lock */
124  SCIP_ROW* row; /**< LP row, if constraint is already stored in LP row format */
125  SCIP_CONS* cons; /**< knapsack relaxation, if created */
126  int* demands; /**< array containing corresponding demands */
127  int* durations; /**< array containing corresponding durations */
128  int nvars; /**< number of variables */
129  int varssize; /**< number of available slots in variable arrays */
130  int capacity; /**< available cumulative capacity */
131 
132  int hmin; /**< left bound of time axis to be considered (including hmin) */
133  int hmax; /**< right bound of time axis to be considered (not including hmax) */
134 
135  int nglbfixedzeros; /**< number of binary variable globally fixed to zero */
136  int nglbfixedones; /**< number of binary variable globally fixed to one */
137  int nfixedzeros; /**< number of binary variable fixed to zero */
138  int nfixedones; /**< number of binary variable fixed to one */
139  int est; /**< used earliest start time for the relaxation */
140  int lct; /**< used latest completion time for the relaxation */
141  unsigned int propagated:1; /**< is constraint already propagated? */
142  unsigned int relaxadded:1; /**< was relaxation added? */
143  unsigned int triedsolving:1; /**< bool to store if it was tried to solve the cumulative sub-problem */
144  unsigned int normalized:1; /**< is the constraint normalized */
145  unsigned int triedredundant:1; /**< bool to store if the redundancy check was applied */
146 };
147 
148 /** constraint handler data */
149 struct SCIP_ConshdlrData
150 {
151  SCIP_EVENTHDLR* eventhdlrbinvars; /**< event handler for bound change events on binary variables */
152  SCIP_EVENTHDLR* eventhdlrintvars; /**< event handler for bound change events on integer variables */
153  SCIP_HEUR* heurtrysol; /**< trysol heuristic */
154  SCIP_Bool rowrelax; /**< add linear relaxation as LP row (otherwise a knapsack constraint is created)? */
155  SCIP_Bool conflictanalysis; /**< participate in conflict analysis? */
156  SCIP_Bool intervalrelax; /**< create a relaxation for each start and end time point interval */
157 };
158 
159 /**@name Debug Methods
160  *
161  * @{
162  */
163 
164 #ifndef NDEBUG
165 /** check constraint state (nglbfixedones and nglbfixedzeros) */
166 static
167 void checkCounters(
168  SCIP_CONSDATA* consdata /**< optcumulative constraint data */
169  )
170 {
171  int nglbfixedones;
172  int nglbfixedzeors;
173  int nfixedones;
174  int nfixedzeors;
175  int v;
176 
177  nglbfixedones = 0;
178  nglbfixedzeors = 0;
179  nfixedones = 0;
180  nfixedzeors = 0;
181 
182  for( v = 0; v < consdata->nvars; ++v )
183  {
184  if( SCIPvarGetLbGlobal(consdata->binvars[v]) > 0.5 )
185  nglbfixedones++;
186 
187  if( SCIPvarGetUbGlobal(consdata->binvars[v]) < 0.5 )
188  nglbfixedzeors++;
189 
190  if( SCIPvarGetLbLocal(consdata->binvars[v]) > 0.5 )
191  nfixedones++;
192 
193  if( SCIPvarGetUbLocal(consdata->binvars[v]) < 0.5 )
194  nfixedzeors++;
195  }
196 
197  assert(nglbfixedones == consdata->nglbfixedones);
198  assert(nglbfixedzeors == consdata->nglbfixedzeros);
199  assert(nfixedones == consdata->nfixedones);
200  assert(nfixedzeors == consdata->nfixedzeros);
201 }
202 #else
203 #define checkCounters(x) /* */
204 #endif
205 
206 /**@} */
207 
208 /**@name Miscellaneous Methods
209  *
210  * @{
211  */
212 
213 #ifndef NDEBUG
214 /** converts the given double bound which is integral to an int; in optimized mode the function gets inlined for
215  * performance; in debug mode we check some additional conditions
216  */
217 static
219  SCIP* scip, /**< SCIP data structure */
220  SCIP_Real bound /**< double bound to convert */
221  )
222 {
223  assert(SCIPisIntegral(scip, bound));
224  assert(SCIPisEQ(scip, bound, (SCIP_Real)(int)(bound + 0.5)));
225 
226  return (int)(bound + 0.5);
227 }
228 #else
229 #define convertBoundToInt(x, y) ((int)((y) + 0.5))
230 #endif
231 
232 /**@} */
233 
234 /**@name Constraint data methods
235  *
236  * @{
237  */
238 
239 /** creates constraint data of optcumulative constraint */
240 static
242  SCIP* scip, /**< SCIP data structure */
243  SCIP_CONSDATA** consdata, /**< pointer to consdata */
244  int nvars, /**< number of variables */
245  SCIP_VAR** vars, /**< array of integer variables */
246  SCIP_VAR** binvars, /**< array of variable representing if the job has to be processed on this machine */
247  int* durations, /**< array containing corresponding durations */
248  int* demands, /**< array containing corresponding demands */
249  int capacity, /**< available cumulative capacity */
250  SCIP_Bool check /**< is the corresponding constraint a check constraint */
251  )
252 {
253  assert(scip != NULL);
254  assert(consdata != NULL);
255  assert(vars != NULL || nvars > 0);
256  assert(binvars != NULL || nvars > 0);
257  assert(demands != NULL);
258  assert(durations != NULL);
259  assert(capacity >= 0);
260 
261  /* create constraint data */
262  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
263 
264  (*consdata)->capacity = capacity;
265  (*consdata)->nvars = nvars;
266  (*consdata)->varssize = nvars;
267  (*consdata)->hmin = 0;
268  (*consdata)->hmax = INT_MAX;
269  (*consdata)->nglbfixedzeros = 0;
270  (*consdata)->est = -1;
271  (*consdata)->lct = INT_MAX;
272  (*consdata)->row = NULL;
273  (*consdata)->cons = NULL;
274  (*consdata)->nglbfixedzeros = 0;
275  (*consdata)->nglbfixedones = 0;
276  (*consdata)->nfixedzeros = 0;
277  (*consdata)->nfixedones = 0;
278  (*consdata)->propagated = FALSE;
279  (*consdata)->relaxadded = FALSE;
280  (*consdata)->triedsolving = FALSE;
281  (*consdata)->normalized = FALSE;
282  (*consdata)->triedredundant = FALSE;
283 
284  if( nvars > 0 )
285  {
286  int v;
287 
288  assert(vars != NULL); /* for flexelint */
289  assert(binvars != NULL); /* for flexelint */
290 
291  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
292  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->binvars, binvars, nvars) );
293  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->downlocks, demands, nvars) );
294  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->uplocks, demands, nvars) );
295  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->demands, demands, nvars) );
296  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->durations, durations, nvars) );
297 
298  /* initialize locking arrays */
299  for( v = 0; v < nvars; ++v )
300  {
301  /* the locks are only used if the contraint is a check constraint */
302  (*consdata)->downlocks[v] = check;
303  (*consdata)->uplocks[v] = check;
304  }
305 
306  /* transform variables, if they are not yet transformed */
307  if( SCIPisTransformed(scip) )
308  {
309  SCIPdebugMessage("get tranformed variables and constraints\n");
310 
311  /* get transformed variables and do NOT captures these */
312  SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
313  SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->binvars, (*consdata)->binvars) );
314 
315  for( v = 0; v < nvars; ++v )
316  {
317  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[v]) );
318  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->binvars[v]) );
319  }
320  }
321  }
322  else
323  {
324  (*consdata)->vars = NULL;
325  (*consdata)->binvars = NULL;
326  (*consdata)->downlocks = NULL;
327  (*consdata)->uplocks = NULL;
328  (*consdata)->demands = NULL;
329  (*consdata)->durations = NULL;
330  }
331 
332  return SCIP_OKAY;
333 }
334 
335 
336 /** frees a optcumulative constraint data */
337 static
339  SCIP* scip, /**< SCIP data structure */
340  SCIP_CONSDATA** consdata /**< pointer to linear constraint data */
341  )
342 {
343  int varssize;
344 
345  assert(consdata != NULL);
346  assert(*consdata != NULL);
347 
348  /* release the row */
349  if( (*consdata)->row != NULL )
350  {
351  SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row) );
352  }
353 
354  /* release the row */
355  if( (*consdata)->cons != NULL )
356  {
357  SCIP_CALL( SCIPreleaseCons(scip, &(*consdata)->cons) );
358  }
359 
360  varssize = (*consdata)->varssize;
361 
362  if( varssize > 0 )
363  {
364  /* free arrays */
365  SCIPfreeBlockMemoryArray(scip, &(*consdata)->durations, varssize);
366  SCIPfreeBlockMemoryArray(scip, &(*consdata)->demands, varssize);
367  SCIPfreeBlockMemoryArray(scip, &(*consdata)->uplocks, varssize);
368  SCIPfreeBlockMemoryArray(scip, &(*consdata)->downlocks, varssize);
369  SCIPfreeBlockMemoryArray(scip, &(*consdata)->binvars, varssize);
370  SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, varssize);
371  }
372 
373  /* free memory */
374  SCIPfreeBlockMemory(scip, consdata);
375 
376  return SCIP_OKAY;
377 }
378 
379 /** prints optcumulative constraint to file stream */
380 static
382  SCIP* scip, /**< SCIP data structure */
383  SCIP_CONSDATA* consdata, /**< optcumulative constraint data */
384  FILE* file /**< output file (or NULL for standard output) */
385  )
386 {
387  int v;
388 
389  assert(consdata != NULL);
390 
391  SCIPinfoMessage( scip, file, "optcumulative(");
392 
393  for( v = 0; v < consdata->nvars; ++v )
394  {
395  assert(consdata->vars[v] != NULL);
396  if( v > 0 )
397  SCIPinfoMessage(scip, file, ", ");
398 
399  SCIP_CALL( SCIPwriteVarName(scip, file, consdata->vars[v], FALSE) );
400 
401  SCIPinfoMessage(scip, file, "[%g,%g](%d)[%d]", SCIPvarGetLbLocal(consdata->vars[v]),
402  SCIPvarGetUbLocal(consdata->vars[v]), consdata->durations[v], consdata->demands[v]);
403 
404  SCIP_CALL( SCIPwriteVarName(scip, file, consdata->binvars[v], FALSE) );
405 
406  }
407  SCIPinfoMessage(scip, file, ")[%d,%d)<= %d", consdata->hmin, consdata->hmax, consdata->capacity);
408 
409  return SCIP_OKAY;
410 }
411 
412 /**@} */
413 
414 /**@name Constraint handler data
415  *
416  * Method used to create and free the constraint handler data when including and removing the cumulative constraint
417  * handler.
418  *
419  * @{
420  */
421 
422 /** creates constaint handler data for set partitioning / packing / covering constraint handler */
423 static
425  SCIP* scip, /**< SCIP data structure */
426  SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
427  SCIP_EVENTHDLR* eventhdlrbinvars, /**< used event handler for tracing bound changes on binary variables */
428  SCIP_EVENTHDLR* eventhdlrintvars /**< used event handler for tracing bound changes on integer variables */
429  )
430 {
431  assert(scip != NULL);
432  assert(conshdlrdata != NULL);
433  assert(eventhdlrbinvars != NULL);
434  assert(eventhdlrintvars != NULL);
435 
436  SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
437 
438  (*conshdlrdata)->eventhdlrbinvars = eventhdlrbinvars;
439  (*conshdlrdata)->eventhdlrintvars = eventhdlrintvars;
440  (*conshdlrdata)->heurtrysol = NULL;
441 
442  return SCIP_OKAY;
443 }
444 
445 /** frees constraint handler data for set partitioning / packing / covering constraint handler */
446 static
448  SCIP* scip, /**< SCIP data structure */
449  SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
450  )
451 {
452  assert(conshdlrdata != NULL);
453  assert(*conshdlrdata != NULL);
454 
455  SCIPfreeBlockMemory(scip, conshdlrdata);
456 
457  return SCIP_OKAY;
458 }
459 
460 /**@} */
461 
462 /** removes rounding locks for the given variable in the given optcumulative constraint */
463 static
465  SCIP* scip, /**< SCIP data structure */
466  SCIP_CONS* cons, /**< optcumulative constraint */
467  SCIP_VAR* binvar, /**< decision variable */
468  SCIP_VAR* var, /**< start time variable */
469  SCIP_Bool downlock, /**< has the integer start time variable a down lock */
470  SCIP_Bool uplock /**< has the integer start time variable an up lock */
471  )
472 {
473  /* rounding up may violate the constraint */
474  SCIP_CALL( SCIPunlockVarCons(scip, binvar, cons, FALSE, TRUE) );
475 
476  /* rounding in both directions may violate the constraint */
477  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, downlock, uplock) );
478 
479  return SCIP_OKAY;
480 }
481 
482 /** catches events for binary variable at given position */
483 static
485  SCIP* scip, /**< SCIP data structure */
486  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
487  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
488  int pos /**< array position of variable to catch bound change events for */
489  )
490 {
491  SCIP_CONSDATA* consdata;
492  SCIP_EVENTTYPE eventtype;
493  SCIP_VAR* binvar;
494 
495  consdata = SCIPconsGetData(cons);
496  assert(consdata != NULL);
497  assert(eventhdlr != NULL);
498  assert(0 <= pos && pos < consdata->nvars);
499  assert(consdata->binvars != NULL);
500 
501  binvar = consdata->binvars[pos];
502  assert(binvar != NULL);
503 
504  /* we are catching the following events for the binary variables:
505  *
506  * - SCIP_EVENTTYPE_BOUNDRELAXED: This allows for counting locally fixed variables to one or zero
507  * - SCIP_EVENTTYPE_GBDCHANGED: This allows to check if the optcumulative can be converted into an cumulative
508  * constraint
509  * - SCIP_EVENTTYPE_BOUNDRELAXED: This allows us to detect the moment when we can retry to solve a local cumulative
510  * constraint again
511  */
513 
514  /* catch bound change events on variable */
515  SCIP_CALL( SCIPcatchVarEvent(scip, binvar, eventtype, eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
516 
517  /* update the globally fixed variables counter for this variable */
518  if( SCIPvarGetUbGlobal(binvar) < 0.5)
519  consdata->nglbfixedzeros++;
520  else if( SCIPvarGetLbGlobal(binvar) > 0.5 )
521  consdata->nglbfixedones++;
522 
523  /* update the locally fixed variables counter for this variable */
524  if( SCIPvarGetUbLocal(binvar) < 0.5)
525  consdata->nfixedzeros++;
526  else if( SCIPvarGetLbLocal(binvar) > 0.5 )
527  consdata->nfixedones++;
528 
529  assert(consdata->nglbfixedzeros + consdata->nglbfixedones <= consdata->nvars);
530  assert(consdata->nfixedzeros + consdata->nfixedones <= consdata->nvars);
531 
532  return SCIP_OKAY;
533 }
534 
535 /** drops events for binary variable at given position */
536 static
538  SCIP* scip, /**< SCIP data structure */
539  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
540  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
541  int pos /**< array position of variable to catch bound change events for */
542  )
543 {
544  SCIP_CONSDATA* consdata;
545  SCIP_EVENTTYPE eventtype;
546  SCIP_VAR* binvar;
547 
548  consdata = SCIPconsGetData(cons);
549  assert(consdata != NULL);
550  assert(eventhdlr != NULL);
551  assert(0 <= pos && pos < consdata->nvars);
552  assert(consdata->binvars != NULL);
553 
554  binvar = consdata->binvars[pos];
555  assert(binvar != NULL);
556 
558 
559  /* drop events on variable */
560  SCIP_CALL( SCIPdropVarEvent(scip, binvar, eventtype, eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
561 
562  /* update the globally fixed variables counter for this variable */
563  if( SCIPvarGetUbGlobal(binvar) < 0.5)
564  consdata->nglbfixedzeros--;
565  else if( SCIPvarGetLbGlobal(binvar) > 0.5 )
566  consdata->nglbfixedones--;
567 
568  /* update the locally fixed variables counter for this variable */
569  if( SCIPvarGetUbLocal(binvar) < 0.5)
570  consdata->nfixedzeros--;
571  else if( SCIPvarGetLbLocal(binvar) > 0.5 )
572  consdata->nfixedones--;
573 
574  assert(consdata->nglbfixedzeros >= 0);
575  assert(consdata->nglbfixedones >= 0);
576  assert(consdata->nfixedzeros >= 0);
577  assert(consdata->nfixedones >= 0);
578 
579  return SCIP_OKAY;
580 }
581 
582 /** catches events for integer variable at given position */
583 static
585  SCIP* scip, /**< SCIP data structure */
586  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
587  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
588  int pos /**< array position of variable to catch bound change events for */
589  )
590 {
591  SCIP_CONSDATA* consdata;
592  SCIP_EVENTTYPE eventtype;
593  SCIP_VAR* var;
594 
595  consdata = SCIPconsGetData(cons);
596  assert(consdata != NULL);
597  assert(eventhdlr != NULL);
598  assert(0 <= pos && pos < consdata->nvars);
599  assert(consdata->vars != NULL);
600 
601  var = consdata->vars[pos];
602  assert(var != NULL);
603 
604  /* we are catching the following events for the integer variables:
605  *
606  * - SCIP_EVENTTYPE_GBDCHANGED: This allows to check if the optcumulative can be converted into an cumulative
607  * constraint
608  */
610 
611  /* catch bound change events on variable */
612  SCIP_CALL( SCIPcatchVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
613 
614  return SCIP_OKAY;
615 }
616 
617 /** drops events for integer variable at given position */
618 static
620  SCIP* scip, /**< SCIP data structure */
621  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
622  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
623  int pos /**< array position of variable to catch bound change events for */
624  )
625 {
626  SCIP_CONSDATA* consdata;
627  SCIP_EVENTTYPE eventtype;
628  SCIP_VAR* var;
629 
630  consdata = SCIPconsGetData(cons);
631  assert(consdata != NULL);
632  assert(eventhdlr != NULL);
633  assert(0 <= pos && pos < consdata->nvars);
634  assert(consdata->vars != NULL);
635 
636  var = consdata->vars[pos];
637  assert(var != NULL);
638 
640 
641  /* drop events on variable */
642  SCIP_CALL( SCIPdropVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
643 
644  return SCIP_OKAY;
645 }
646 
647 /** catches bound change events for all variables in transformed optcumulative constraint */
648 static
650  SCIP* scip, /**< SCIP data structure */
651  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
652  SCIP_EVENTHDLR* eventhdlrbinvars, /**< event handler to call for the event processing on binary variables */
653  SCIP_EVENTHDLR* eventhdlrintvars /**< event handler to call for the event processing on integer variables */
654  )
655 {
656  SCIP_CONSDATA* consdata;
657  int v;
658 
659  consdata = SCIPconsGetData(cons);
660  assert(consdata != NULL);
661  assert(consdata->nglbfixedones == 0);
662  assert(consdata->nglbfixedzeros == 0);
663  assert(consdata->nfixedones == 0);
664  assert(consdata->nfixedzeros == 0);
665 
666  /* catch event for every single variable */
667  for( v = 0; v < consdata->nvars; ++v )
668  {
669  SCIP_CALL( catchEventBinvar(scip, cons, eventhdlrbinvars, v) );
670 
671  SCIP_CALL( catchEventIntvar(scip, cons, eventhdlrintvars, v) );
672  }
673 
674  /* (debug) check if the counter of the constraint are correct */
675  checkCounters(consdata);
676 
677  return SCIP_OKAY;
678 }
679 
680 /** drops bound change events for all variables in transformed optcumulative constraint */
681 static
683  SCIP* scip, /**< SCIP data structure */
684  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
685  SCIP_EVENTHDLR* eventhdlrbinvars, /**< event handler to call for the event processing on binary variables */
686  SCIP_EVENTHDLR* eventhdlrintvars /**< event handler to call for the event processing on integer variables */
687  )
688 {
689  SCIP_CONSDATA* consdata;
690  int v;
691 
692  consdata = SCIPconsGetData(cons);
693  assert(consdata != NULL);
694 
695  /* drop event of every single variable */
696  for( v = 0; v < consdata->nvars; ++v )
697  {
698  SCIP_CALL( dropEventBinvar(scip, cons, eventhdlrbinvars, v) );
699 
700  SCIP_CALL( dropEventIntvar(scip, cons, eventhdlrintvars, v) );
701  }
702 
703  /* check that the internal constraint state is rested */
704  assert(consdata->nglbfixedones == 0);
705  assert(consdata->nglbfixedzeros == 0);
706  assert(consdata->nfixedones == 0);
707  assert(consdata->nfixedzeros == 0);
708 
709  return SCIP_OKAY;
710 }
711 
712 /** initialize the sorted event point arrays */
713 static
715  SCIP* scip, /**< SCIP data structure */
716  SCIP_CONSDATA* consdata, /**< constraint data */
717  int* starttimes, /**< array to store sorted start events */
718  int* endtimes, /**< array to store sorted end events */
719  int* startindices, /**< permutation with rspect to the start times */
720  int* endindices, /**< permutation with rspect to the end times */
721  SCIP_Bool local /**< shall local bounds be used */
722  )
723 {
724  SCIP_VAR* var;
725  int nvars;
726  int j;
727 
728  nvars = consdata->nvars;
729 
730  /* assign variables, start and endpoints to arrays */
731  for ( j = 0; j < nvars; ++j )
732  {
733  var = consdata->vars[j];
734  if( local )
735  starttimes[j] = convertBoundToInt(scip, SCIPvarGetLbLocal(var));
736  else
737  starttimes[j] = convertBoundToInt(scip, SCIPvarGetLbGlobal(var));
738 
739  startindices[j] = j;
740 
741  if( local )
742  endtimes[j] = convertBoundToInt(scip, SCIPvarGetUbLocal(var)) + consdata->durations[j];
743  else
744  endtimes[j] = convertBoundToInt(scip, SCIPvarGetUbGlobal(var)) + consdata->durations[j];
745 
746  endindices[j] = j;
747  }
748 
749  /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
750  SCIPsortIntInt(starttimes, startindices, nvars);
751  SCIPsortIntInt(endtimes, endindices, nvars);
752 }
753 
754 /** computes the maximum energy for all variables which correspond to jobs which start between the given start time and
755  * end time
756  *
757  * @return Maximum energy for the given time window
758  */
759 static
761  SCIP* scip, /**< SCIP data structure */
762  SCIP_CONSDATA* consdata, /**< optcumulative constraint data */
763  int starttime, /**< start time */
764  int endtime /**< end time */
765  )
766 {
767  SCIP_VAR* var;
768  SCIP_Longint maxenergy;
769  int v;
770 
771  assert(starttime < endtime);
772  maxenergy = 0LL;
773 
774  for( v = 0; v < consdata->nvars; ++v )
775  {
776  var = consdata->vars[v];
777 
778  /* collect jobs which run between the start and end time */
779  if( convertBoundToInt(scip, SCIPvarGetUbGlobal(var)) + consdata->durations[v] <= endtime
780  && convertBoundToInt(scip, SCIPvarGetLbGlobal(var)) >= starttime)
781  {
782  maxenergy += (SCIP_Longint)(consdata->durations[v] * consdata->demands[v]); /*lint !e647*/
783  }
784  }
785 
786  return maxenergy;
787 }
788 
789 /** collects all variables which correspond to jobs which start between the given start time and end time */
790 static
792  SCIP* scip, /**< SCIP data structure */
793  SCIP_CONSDATA* consdata, /**< optcumulative constraint data */
794  SCIP_VAR** vars, /**< array to store the variables */
795  SCIP_Longint* weights, /**< array to store the weights */
796  int* nvars, /**< pointer to store the number of collected variables */
797  int starttime, /**< start time */
798  int endtime /**< end time */
799  )
800 {
801  SCIP_VAR* var;
802  int v;
803 
804  assert(starttime < endtime);
805  (*nvars) = 0;
806 
807  for( v = 0; v < consdata->nvars; ++v )
808  {
809  var = consdata->vars[v];
810 
811  /* collect jobs which run between the start and end time */
812  if( convertBoundToInt(scip, SCIPvarGetUbGlobal(var)) + consdata->durations[v] <= endtime
813  && convertBoundToInt(scip, SCIPvarGetLbGlobal(var)) >= starttime)
814  {
815  vars[*nvars] = consdata->binvars[v];
816  weights[*nvars] = (SCIP_Longint)(consdata->durations[v] * consdata->demands[v]); /*lint !e647*/
817  (*nvars)++;
818  }
819  }
820 
821  return SCIP_OKAY;
822 }
823 
824 /** remove row which have a tightness which is smaller or equal to the given one
825  *
826  * @return The number of remaining rows
827  */
828 static
830  SCIP_Longint* rowtightness, /**< array containing the tightness for the previously selected rows */
831  int* startidxs, /**< array containing for each row the index for the start event */
832  int nrows, /**< current number of rows */
833  SCIP_Longint tightness /**< tightness to use to detect redundant rows */
834  )
835 {
836  int keptrows;
837  int j;
838 
839  keptrows = 0;
840 
841  for( j = 0; j < nrows; ++j )
842  {
843  rowtightness[keptrows] = rowtightness[j];
844  startidxs[keptrows] = startidxs[j];
845 
846  /* only keep this row if the tightness is better as the (current) given one */
847  if( rowtightness[j] > tightness )
848  keptrows++;
849  }
850 
851  return keptrows;
852 }
853 
854 /** depending on the parameters setting a row or an knapsack constraint is created */
855 static
857  SCIP* scip, /**< SCIP data structure */
858  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
859  const char* name, /**< name of the row */
860  SCIP_VAR** vars, /**< array of variable representing if the job has to be processed on this machine */
861  SCIP_Longint* weights, /**< start time variables of the activities which are assigned */
862  int nvars, /**< number of variables */
863  SCIP_Longint capacity, /**< available cumulative capacity */
864  SCIP_Bool local, /**< create local row */
865  SCIP_Bool* rowadded, /**< pointer to store if a row was added */
866  SCIP_Bool* consadded, /**< pointer to store if a constraint was added */
867  SCIP_Bool* cutoff /**< pointer to store whether a cutoff occurred */
868  )
869 {
870  SCIP_CONSHDLRDATA* conshdlrdata;
871 
872  conshdlrdata = SCIPconshdlrGetData(conshdlr);
873  assert(conshdlrdata != NULL);
874 
875  *cutoff = FALSE;
876  if( conshdlrdata->rowrelax || SCIPgetDepth(scip) > 0 )
877  {
878  SCIP_ROW* row;
879  int v;
880 
881  /* create empty row */
882  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, name, -SCIPinfinity(scip), (SCIP_Real)capacity, local, FALSE, FALSE) );
883 
884  /* w.r.t. performance we cache the row extension and flush them in the end */
885  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
886 
887  for( v = 0; v < nvars; ++v )
888  {
889  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[v], (SCIP_Real)weights[v]) );
890  }
891 
892  /* w.r.t. performance we flush the row extension in the end */
893  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
894 
895  assert(!SCIProwIsInLP(row));
896 
897  if( SCIPgetDepth(scip) == 0 || SCIPisCutEfficacious(scip, NULL, row) )
898  {
899  SCIPdebug( SCIPprintRow(scip, row, NULL) );
900  SCIP_CALL( SCIPaddRow(scip, row, FALSE, cutoff) );
901  (*rowadded) = TRUE;
902  }
903 
904  SCIP_CALL( SCIPreleaseRow(scip, &row) );
905  }
906  else
907  {
908  SCIP_CONS* cons;
909 
910  /* create knapsack constraint */
911  SCIP_CALL( SCIPcreateConsKnapsack(scip, &cons, name, nvars, vars, weights, capacity,
912  FALSE, TRUE, TRUE, FALSE, TRUE, local, FALSE, FALSE, TRUE, FALSE) );
913 
914  SCIPdebug( SCIP_CALL( SCIPprintCons(scip, cons, NULL) ) );
915 
916  /* add and releasse knapsack constraint */
917  SCIP_CALL( SCIPaddCons(scip, cons) );
918  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
919  (*consadded) = TRUE;
920  }
921 
922  return SCIP_OKAY;
923 }
924 
925 /** adds linear relaxation as cut to the LP */
926 static
928  SCIP* scip, /**< SCIP data structure */
929  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
930  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data structure */
931  SCIP_CONS* cons, /**< optcumulative constraint */
932  SCIP_Bool* rowadded, /**< pointer to store if a row was added */
933  SCIP_Bool* consadded, /**< pointer to store if a constraint was added */
934  SCIP_Bool* cutoff /**< pointer to store whether a cutoff occurred */
935  )
936 {
937  SCIP_CONSDATA* consdata;
938 
939  assert(scip != NULL);
940  assert(cons != NULL);
941 
942  consdata = SCIPconsGetData(cons);
943  assert(consdata != NULL);
944  assert( cutoff != NULL );
945 
946  *cutoff = FALSE;
947  if( consdata->relaxadded )
948  return SCIP_OKAY;
949 
950  SCIPdebugMessage("add relaxation for optcumulative constraint <%s>\n", SCIPconsGetName(cons));
951 
952  if( conshdlrdata->intervalrelax )
953  {
954  SCIP_Longint** rowtightness;
955  int** startidxs;
956  int* nrows;
957  int* starttimes;
958  int* endtimes;
959  int* startindices;
960  int* endindices;
961  int starttime;
962  int endtime;
963  int i;
964  int j;
965 
966  SCIP_CALL( SCIPallocBufferArray(scip, &starttimes, consdata->nvars) );
967  SCIP_CALL( SCIPallocBufferArray(scip, &startindices, consdata->nvars) );
968  SCIP_CALL( SCIPallocBufferArray(scip, &endtimes, consdata->nvars) );
969  SCIP_CALL( SCIPallocBufferArray(scip, &endindices, consdata->nvars) );
970 
971  SCIP_CALL( SCIPallocBufferArray(scip, &nrows, consdata->nvars) );
972  BMSclearMemoryArray(nrows, consdata->nvars);
973  SCIP_CALL( SCIPallocBufferArray(scip, &rowtightness, consdata->nvars) );
974  SCIP_CALL( SCIPallocBufferArray(scip, &startidxs, consdata->nvars) );
975  for( j = 0; j < consdata->nvars; ++j )
976  {
977  SCIP_CALL( SCIPallocBufferArray(scip, &rowtightness[j], consdata->nvars) ); /*lint !e866*/
978  SCIP_CALL( SCIPallocBufferArray(scip, &startidxs[j], consdata->nvars) ); /*lint !e866*/
979  }
980 
981  createSortedEventpoints(scip, consdata, starttimes, endtimes, startindices, endindices, TRUE);
982 
983  starttime = -INT_MAX;
984 
985  /* check each startpoint of a job whether the capacity is kept or not */
986  for( j = 0; j < consdata->nvars; ++j )
987  {
988  SCIP_Longint besttightness;
989 
990  assert(starttime <= starttimes[j]);
991 
992  /* if we hit the same start time again we skip the loop */
993  if( starttime == starttimes[j])
994  continue;
995 
996  starttime = starttimes[j];
997  endtime = -INT_MAX;
998  besttightness = 0LL;
999 
1000  for( i = 0; i < consdata->nvars; ++i )
1001  {
1002  SCIP_Longint energy;
1003  SCIP_Longint maxenergy;
1004  SCIP_Longint tightness;
1005 
1006  assert(endtime <= endtimes[i]);
1007 
1008  /* if we hit the same end time again we skip the loop */
1009  if( endtime == endtimes[i] )
1010  continue;
1011 
1012  endtime = endtimes[i];
1013 
1014  /* skip all end times which are smaller than the start time */
1015  if( endtime <= starttime )
1016  continue;
1017 
1018  maxenergy = computeMaxEnergy(scip, consdata, starttime, endtime);
1019 
1020  energy = (endtime - starttime) * consdata->capacity; /*lint !e647*/
1021  tightness = maxenergy - energy;
1022 
1023  /* check if the linear constraint is not trivially redundant */
1024  if( tightness > besttightness )
1025  {
1026  besttightness = tightness;
1027 
1028  nrows[i] = removeRedundantRows(rowtightness[i], startidxs[i], nrows[i], tightness);
1029 
1030  /* add row information */
1031  rowtightness[i][nrows[i]] = tightness;
1032  startidxs[i][nrows[i]] = j;
1033  nrows[i]++;
1034  }
1035  }
1036  }
1037 
1038  for( j = consdata->nvars-1; j >= 0 && ! (*cutoff); --j )
1039  {
1040  for( i = 0; i < nrows[j] && ! (*cutoff); ++i )
1041  {
1042  SCIP_VAR** vars;
1043  SCIP_Longint* weights;
1044  SCIP_Longint energy;
1045  char name[SCIP_MAXSTRLEN];
1046  int nvars;
1047 
1048  SCIP_CALL( SCIPallocBufferArray(scip, &vars, consdata->nvars) );
1049  SCIP_CALL( SCIPallocBufferArray(scip, &weights, consdata->nvars) );
1050 
1051  starttime = starttimes[startidxs[j][i]];
1052  endtime = endtimes[j];
1053 
1054  energy = (endtime - starttime) * consdata->capacity; /*lint !e647*/
1055 
1056  SCIP_CALL( collectVars(scip, consdata, vars, weights, &nvars, starttime, endtime) );
1057 
1058  SCIPdebugMessage("create linear relaxation for <%s> time interval [%d,%d] <= %"SCIP_LONGINT_FORMAT" (tightness %"SCIP_LONGINT_FORMAT")\n",
1059  SCIPconsGetName(cons), starttime, endtime, energy, rowtightness[j][i]);
1060 
1061  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s[%d,%d]", SCIPconsGetName(cons), starttime, endtime);
1062  SCIP_CALL( createRow(scip, conshdlr, name, vars, weights, nvars, energy, TRUE, rowadded, consadded, cutoff) );
1063 
1064  SCIPfreeBufferArray(scip, &weights);
1065  SCIPfreeBufferArray(scip, &vars);
1066  }
1067  }
1068 
1069  /* free buffers */
1070  for( j = consdata->nvars-1; j >= 0; --j )
1071  {
1072  SCIPfreeBufferArray(scip, &startidxs[j]);
1073  SCIPfreeBufferArray(scip, &rowtightness[j]);
1074  }
1075  SCIPfreeBufferArray(scip, &startidxs);
1076  SCIPfreeBufferArray(scip, &rowtightness);
1077  SCIPfreeBufferArray(scip, &nrows);
1078 
1079  SCIPfreeBufferArray(scip, &endindices);
1080  SCIPfreeBufferArray(scip, &endtimes);
1081  SCIPfreeBufferArray(scip, &startindices);
1082  SCIPfreeBufferArray(scip, &starttimes);
1083  }
1084  else
1085  {
1086  SCIP_VAR** vars;
1087  SCIP_Longint* weights;
1088  SCIP_Longint maxenergy;
1089  SCIP_Longint energy;
1090  int* durations;
1091  int* demands;
1092  int est;
1093  int lct;
1094  int nvars;
1095  int v;
1096 
1097  nvars = consdata->nvars;
1098  vars = consdata->vars;
1099  durations = consdata->durations;
1100  demands = consdata->demands;
1101  maxenergy = 0LL;
1102 
1103  SCIP_CALL( SCIPallocBufferArray(scip, &weights, nvars) );
1104 
1105  est = INT_MAX;
1106  lct = 0;
1107 
1108  for( v = 0; v < nvars; ++v )
1109  {
1110  weights[v] = (SCIP_Longint)(durations[v] * demands[v]); /*lint !e647*/
1111  maxenergy += weights[v];
1112 
1113  /* adjust earlier start time */
1114  est = MIN(est, convertBoundToInt(scip, SCIPvarGetLbLocal(vars[v]))); /*lint !e666*/
1115 
1116  /* adjust latest completion */
1117  lct = MAX(lct, convertBoundToInt(scip, SCIPvarGetUbLocal(vars[v]) + durations[v])); /*lint !e666*/
1118  }
1119 
1120  energy = (lct - est) * consdata->capacity; /*lint !e647*/
1121 
1122  if( maxenergy > energy )
1123  {
1124  char name[SCIP_MAXSTRLEN];
1125 
1126  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s[%d,%d]", SCIPconsGetName(cons), est, lct);
1127 
1128  SCIPdebugMessage("create linear relaxation for <%s> (nvars %d) time interval [%d,%d] <= %"SCIP_LONGINT_FORMAT"\n",
1129  SCIPconsGetName(cons), nvars, est, lct, energy);
1130 
1131  SCIP_CALL( createRow(scip, conshdlr, name, consdata->binvars, weights, nvars, energy, TRUE, rowadded, consadded, cutoff) );
1132  }
1133 
1134  /* free buffer */
1135  SCIPfreeBufferArray(scip, &weights);
1136  }
1137 
1138  consdata->relaxadded = TRUE;
1139 
1140 #if 0
1141  if( !conshdlrdata->rowrelax )
1142  {
1143  SCIP_CALL( SCIPrestartSolve(scip) );
1144  }
1145 #endif
1146 
1147  return SCIP_OKAY;
1148 }
1149 
1150 /** collect all activities which are locally (that means in the current branch and bound node) assigned to that
1151  * machine
1152  */
1153 static
1154 void collectActivities(
1155  SCIP_CONSDATA* consdata, /**< constraint data */
1156  SCIP_VAR** binvars, /**< array of variable representing if the job has to be processed on this machine */
1157  SCIP_VAR** vars, /**< start time variables of the activities which are assigned */
1158  int* durations, /**< durations of the activities */
1159  int* demands, /**< demands of the activities */
1160  int* nfixedones, /**< pointer to store number of activities assigned to that machine */
1161  int* nfixedzeros, /**< pointer to store number of binary variables fixed to zeor */
1162  SCIP_Bool* auxiliary /**< pointer to store if the integer start time variables of the assigned
1163  * activities are auxiliary variables; that is the case if the optcumulative
1164  * choice constraints is the only one having locks on these variables */
1165  )
1166 {
1167  int v;
1168 
1169  /* collect all jobs which have to be processed */
1170  (*auxiliary) = TRUE;
1171  (*nfixedones) = 0;
1172  (*nfixedzeros) = 0;
1173 
1174  for( v = 0; v < consdata->nvars; ++v )
1175  {
1176  if( SCIPvarGetLbLocal(consdata->binvars[v]) > 0.5 )
1177  {
1178  /* binary variable is fixed one */
1179 
1180  SCIPdebugMessage("collect variable <%s>[%g,%g](%d)\n",
1181  SCIPvarGetName(consdata->vars[v]), SCIPvarGetLbLocal(consdata->vars[v]), SCIPvarGetUbGlobal(consdata->vars[v]), consdata->durations[v]);
1182 
1183  binvars[*nfixedones] = consdata->binvars[v];
1184  vars[*nfixedones] = consdata->vars[v];
1185  durations[*nfixedones] = consdata->durations[v];
1186  demands[*nfixedones] = consdata->demands[v];
1187 
1188  (*nfixedones)++;
1189 
1190  /* check the locks on the integer start time variable to determine if its a auxiliary variable (only locked by
1191  * this constraint)
1192  */
1193  if( SCIPvarGetNLocksDown(consdata->vars[v]) > (int)consdata->downlocks[v]
1194  || SCIPvarGetNLocksUp(consdata->vars[v]) > (int)consdata->uplocks[v] )
1195  {
1196  (*auxiliary) = FALSE;
1197  }
1198  }
1199  else if( SCIPvarGetUbLocal(consdata->binvars[v]) < 0.5 )
1200  (*nfixedzeros)++;
1201  }
1202 
1203  assert(consdata->nfixedzeros == *nfixedzeros);
1204  assert(consdata->nfixedones == *nfixedones);
1205 }
1206 
1207 /** collect all activities which are assigned to that machine in the given solution */
1208 static
1210  SCIP* scip, /**< SCIP data structure */
1211  SCIP_CONSDATA* consdata, /**< constraint data */
1212  SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
1213  SCIP_VAR** binvars, /**< array of variable representing if the job has to be processed on this machine */
1214  SCIP_VAR** vars, /**< start time variables of the activities which are assigned */
1215  int* durations, /**< durations of the activities */
1216  int* demands, /**< demands of the activities */
1217  int* nvars, /**< pointer to store number of activities assigned to that machine */
1218  int* nfixedones, /**< pointer to store number of binary variables locally fixed to one */
1219  int* nfixedzeros, /**< pointer to store number of binary variables locally fixed to zero */
1220  SCIP_Bool* auxiliary /**< pointer to store if the integer start time variables of the assigned
1221  * activities are auxiliary variables; that is the case if the machine
1222  * choice constraints is the only one haveing locks on these variables */
1223  )
1224 {
1225  int v;
1226 
1227  (*nvars) = 0;
1228  (*nfixedones) = 0;
1229  (*nfixedzeros) = 0;
1230  (*auxiliary) = TRUE;
1231 
1232  /* collect all jobs which have to be processed */
1233  for( v = 0; v < consdata->nvars; ++v )
1234  {
1235  if( SCIPgetSolVal(scip, sol, consdata->binvars[v]) > 0.5 )
1236  {
1237  SCIPdebugMessage("collect variable <%s>\n", SCIPvarGetName(consdata->vars[v]));
1238  binvars[*nvars] = consdata->binvars[v];
1239  vars[*nvars] = consdata->vars[v];
1240  durations[*nvars] = consdata->durations[v];
1241  demands[*nvars] = consdata->demands[v];
1242  (*nvars)++;
1243 
1244  /* check the locks on the integer start time variable to determine if its a auxiliary variable */
1245  if( SCIPvarGetNLocksDown(consdata->vars[v]) > (int)consdata->downlocks[v]
1246  || SCIPvarGetNLocksUp(consdata->vars[v]) > (int)consdata->uplocks[v]
1247  )
1248  (*auxiliary) = FALSE;
1249  }
1250 
1251  if( SCIPvarGetLbLocal(consdata->binvars[v]) > 0.5 )
1252  nfixedones++;
1253  else if( SCIPvarGetUbLocal(consdata->binvars[v]) < 0.5 )
1254  nfixedzeros++;
1255  }
1256 }
1257 
1258 /** solves given cumulative condition as independent sub problem
1259  *
1260  * @note The time and memory limit of the SCIP environment in transferred to sub solver
1261  *
1262  * @note If the problem was solved to the earliest start times (ests) and latest start times (lsts) array contain the
1263  * solution values; If the problem was not solved these two arrays contain the global bounds at the time the sub
1264  * solver was interrupted.
1265  */
1266 static
1268  SCIP* scip, /**< SCIP data structure */
1269  int nvars, /**< number of start time variables (activities) */
1270  SCIP_VAR** vars, /**< start time variables */
1271  int* durations, /**< array of durations */
1272  int* demands, /**< array of demands */
1273  int capacity, /**< cumulative capacity */
1274  int hmin, /**< left bound of time axis to be considered (including hmin) */
1275  int hmax, /**< right bound of time axis to be considered (not including hmax) */
1276  SCIP_Bool local, /**< use local bounds, otherwise global */
1277  SCIP_Real* ests, /**< array to store the earlier start time for each job */
1278  SCIP_Real* lsts, /**< array to store the latest start time for each job */
1279  SCIP_Longint maxnodes, /**< maximum number of branch-and-bound nodes to solve the single cumulative constraint (-1: no limit) */
1280  SCIP_Bool* solved, /**< pointer to store if the problem is solved (to optimality) */
1281  SCIP_Bool* infeasible, /**< pointer to store if the problem is infeasible */
1282  SCIP_Bool* unbounded, /**< pointer to store if the problem is unbounded */
1283  SCIP_Bool* error /**< pointer to store if an error occurred */
1284  )
1285 {
1286  SCIP_Real* objvals;
1287  SCIP_Real timelimit;
1288  SCIP_Real memorylimit;
1289  int v;
1290 
1291  SCIP_CALL( SCIPallocBufferArray(scip, &objvals, nvars) );
1292 
1293  for( v = 0; v < nvars; ++v )
1294  {
1295  SCIP_VAR* var;
1296 
1297  var = vars[v];
1298  assert(var != NULL);
1299 
1300  if( local )
1301  {
1302  ests[v] = SCIPvarGetLbLocal(var);
1303  lsts[v] = SCIPvarGetUbLocal(var);
1304  }
1305  else
1306  {
1307  ests[v] = SCIPvarGetLbGlobal(var);
1308  lsts[v] = SCIPvarGetUbGlobal(var);
1309  }
1310 
1311  objvals[v] = SCIPvarGetObj(var);
1312  }
1313 
1314  /* check whether there is enough time and memory left */
1315  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1316  if( !SCIPisInfinity(scip, timelimit) )
1317  timelimit -= SCIPgetSolvingTime(scip);
1318  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
1319 
1320  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
1321  if( !SCIPisInfinity(scip, memorylimit) )
1322  {
1323  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1324  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
1325  }
1326 
1327  SCIP_CALL( SCIPsolveCumulative(scip, nvars, ests, lsts, objvals, durations, demands,
1328  capacity, hmin, hmax, timelimit, memorylimit, maxnodes,
1329  solved, infeasible, unbounded, error) );
1330 
1331  SCIPfreeBufferArray(scip, &objvals);
1332 
1333  return SCIP_OKAY;
1334 }
1335 
1336 
1337 /** create a logicor constraint which ensures that the jobs related to binary variables are not assigned in the same
1338  * time to this optional cumulative constraint
1339  */
1340 static
1342  SCIP* scip, /**< SCIP data structure */
1343  const char* name, /**< name of conflict constraint */
1344  SCIP_VAR** binvars, /**< array of binary variables */
1345  int nvars /**< number of variables */
1346  )
1347 {
1348  SCIP_CONS* cons;
1349  SCIP_VAR* negatedvar;
1350  int v;
1351 
1352  /* one of the jobs cannot be processed on that resource */
1353  SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, name, 0, NULL,
1355 
1356  for( v = 0; v < nvars; ++v )
1357  {
1358  if( SCIPvarGetLbGlobal(binvars[v]) > 0.5 )
1359  continue;
1360 
1361  SCIP_CALL( SCIPgetNegatedVar(scip, binvars[v], &negatedvar) );
1362 
1363  SCIP_CALL( SCIPaddCoefLogicor(scip, cons, negatedvar) );
1364  }
1365 
1366  /* add and release to constraint */
1367  SCIP_CALL( SCIPaddCons(scip, cons) );
1368  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1369 
1370  return SCIP_OKAY;
1371 }
1372 
1373 /** check of the given constraint is redundant */
1374 static
1376  SCIP* scip, /**< SCIP data structure */
1377  SCIP_CONS* cons, /**< optcumulative constraint which collapsed to a cumulative constraint locally */
1378  int* ndelconss, /**< pointer to store the number of deleted constraints */
1379  SCIP_Bool* redundant /**< pointer to store if the constraint is redundant */
1380  )
1381 {
1382  SCIP_CONSDATA* consdata;
1383  SCIP_Bool solved;
1384  SCIP_Bool infeasible;
1385  SCIP_Bool unbounded;
1386  SCIP_Bool error;
1387  SCIP_Real* lbs;
1388  SCIP_Real* ubs;
1389  int nvars;
1390  int v;
1391 
1392  assert(scip != NULL);
1393  assert(!SCIPinProbing(scip));
1394 
1395  (*redundant) = FALSE;
1396 
1397  consdata = SCIPconsGetData(cons);
1398  assert(consdata != NULL);
1399  assert(consdata->nglbfixedzeros == 0);
1400 
1401  if( consdata->triedredundant )
1402  return SCIP_OKAY;
1403 
1404  consdata->triedredundant = TRUE;
1405 
1406  nvars = consdata->nvars;
1407 
1408  /* check the locks on the integer start time variable to determine if its a auxiliary variable */
1409  for( v = 0; v < nvars; ++v )
1410  {
1411  if( SCIPvarGetNLocksDown(consdata->vars[v]) > (int)consdata->downlocks[v]
1412  || SCIPvarGetNLocksUp(consdata->vars[v]) > (int)consdata->uplocks[v]
1413  )
1414  return SCIP_OKAY;
1415  }
1416 
1417  SCIP_CALL( SCIPallocBufferArray(scip, &lbs, nvars) );
1418  SCIP_CALL( SCIPallocBufferArray(scip, &ubs, nvars) );
1419 
1420  /* solve the cumulative condition separately */
1421  SCIP_CALL( solveCumulative(scip, nvars, consdata->vars, consdata->durations, consdata->demands,
1422  consdata->capacity, consdata->hmin, consdata->hmax, FALSE,
1423  lbs, ubs, 2000LL, &solved, &infeasible, &unbounded, &error) );
1424  assert(!unbounded);
1425 
1426  if( !error )
1427  {
1428  if( infeasible )
1429  {
1430  SCIP_VAR** binvars;
1431  SCIP_VAR** vars;
1432  int* durations;
1433  int* demands;
1434  SCIP_Real* weights;
1435 
1436  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, nvars) );
1437  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
1438  SCIP_CALL( SCIPallocBufferArray(scip, &durations, nvars) );
1439  SCIP_CALL( SCIPallocBufferArray(scip, &demands, nvars) );
1440  SCIP_CALL( SCIPallocBufferArray(scip, &weights, nvars) );
1441 
1442  for( v = 0; v < nvars; ++v )
1443  {
1444  SCIP_VAR* var;
1445  int est;
1446  int lst;
1447 
1448  var = consdata->vars[v];
1449  assert(var != NULL);
1450 
1451  est = convertBoundToInt(scip, SCIPvarGetLbGlobal(var));
1452  lst = convertBoundToInt(scip, SCIPvarGetUbGlobal(var));
1453 
1454  if( consdata->demands[v] == 0.0 || consdata->durations[v] == 0.0 )
1455  return SCIP_ERROR;
1456 
1457  weights[v] = (lst - est) / (consdata->demands[v] * consdata->durations[v]); /*lint !e653*/
1458 
1459  binvars[v] = consdata->binvars[v];
1460  vars[v] = var;
1461  durations[v] = consdata->durations[v];
1462  demands[v] = consdata->demands[v];
1463  }
1464  SCIPsortRealPtrPtrIntInt(weights, (void*)binvars, (void*)vars, durations, demands, nvars);
1465 
1466  while( nvars > 1 )
1467  {
1468  SCIP_CALL( solveCumulative(scip, nvars-1, vars, consdata->durations, consdata->demands, consdata->capacity, consdata->hmin, consdata->hmax, TRUE,
1469  lbs, ubs, 2000LL, &solved, &infeasible, &unbounded, &error) );
1470 
1471  if( !infeasible )
1472  break;
1473 
1474  nvars--;
1475  }
1476 
1477  SCIP_CALL( createConflictCons(scip, SCIPconsGetName(cons), binvars, nvars) );
1478 
1479  SCIPfreeBufferArray(scip, &weights);
1480  SCIPfreeBufferArray(scip, &demands);
1481  SCIPfreeBufferArray(scip, &durations);
1482  SCIPfreeBufferArray(scip, &vars);
1483  SCIPfreeBufferArray(scip, &binvars);
1484  }
1485  else if( solved )
1486  {
1487  for( v = 0; v < nvars; ++v )
1488  {
1489  SCIP_VAR* var;
1490 
1491  /* check if variable is fixed */
1492  assert(lbs[v] + 0.5 > ubs[v]);
1493 
1494  var = consdata->vars[v];
1495  assert(var != NULL);
1496 
1497  if( SCIPvarGetLbGlobal(var) + 0.5 < lbs[v] )
1498  {
1499  SCIP_CALL( SCIPchgVarLbGlobal(scip, var, lbs[v]) );
1500  }
1501 
1502  if( SCIPvarGetUbGlobal(var) - 0.5 > lbs[v] )
1503  {
1504  SCIP_CALL( SCIPchgVarUbGlobal(scip, var, lbs[v]) );
1505  }
1506  }
1507 
1508  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1509  (*ndelconss)++;
1510  (*redundant) = TRUE;
1511  }
1512  }
1513 
1514  SCIPfreeBufferArray(scip, &ubs);
1515  SCIPfreeBufferArray(scip, &lbs);
1516 
1517  return SCIP_OKAY;
1518 }
1519 
1520 /** solve the cumulative sub problem */
1521 static
1523  SCIP* scip, /**< SCIP data structure */
1524  SCIP_CONS* cons, /**< optcumulative constraint which collapsed to a cumulative constraint locally */
1525  SCIP_Bool conflictanalysis, /**< should conflict analysis be called for infeasible subproblems */
1526  SCIP_CONSDATA* consdata, /**< constraint data */
1527  SCIP_VAR** binvars, /**< array of variable representing if the job has to be processed on this machine */
1528  SCIP_VAR** vars, /**< start time variables of the activities which are assigned */
1529  int* durations, /**< durations of the activities */
1530  int* demands, /**< demands of the activities */
1531  int nvars, /**< number of activities assigned to that machine */
1532  int* nfixedvars, /**< pointer to store the numbver of fixed variables */
1533  int* nchgbds, /**< pointer to store the number of changed bounds */
1534  int* ndelconss, /**< pointer to store the number of deleted constraints */
1535  SCIP_Bool* cutoff /**< pointer to store if the constraint is violated */
1536  )
1537 {
1538  SCIP_Bool unbounded;
1539  SCIP_Bool solved;
1540  SCIP_Bool error;
1541  SCIP_Real* lbs;
1542  SCIP_Real* ubs;
1543 
1544  assert(scip != NULL);
1545  assert(!SCIPinProbing(scip));
1546 
1547  /* if we already tried solving this subproblem we do not do it again */
1548  if( consdata->triedsolving )
1549  return SCIP_OKAY;
1550 
1551  consdata->triedsolving = TRUE;
1552 
1553  if( nvars == 0 )
1554  return SCIP_OKAY;
1555 
1556  SCIP_CALL( SCIPallocBufferArray(scip, &lbs, nvars) );
1557  SCIP_CALL( SCIPallocBufferArray(scip, &ubs, nvars) );
1558 
1559  /* solve the cumulative condition separately */
1560  SCIP_CALL( solveCumulative(scip, nvars, vars, durations, demands, consdata->capacity, consdata->hmin, consdata->hmax, TRUE,
1561  lbs, ubs, 2000LL, &solved, cutoff, &unbounded, &error) );
1562  assert(!unbounded);
1563 
1564  if( !error )
1565  {
1566  if( *cutoff && conflictanalysis )
1567  {
1568  SCIP_Real* weights;
1569  SCIP_Bool infeasible;
1570  int v;
1571 
1572  SCIP_CALL( SCIPallocBufferArray(scip, &weights, nvars) );
1573 
1574  for( v = 0; v < nvars; ++v )
1575  {
1576  int est;
1577  int lst;
1578 
1579  est = convertBoundToInt(scip, SCIPvarGetLbLocal(vars[v]));
1580  lst = convertBoundToInt(scip, SCIPvarGetUbLocal(vars[v]));
1581 
1582  if( demands[v] == 0.0 || durations[v] == 0.0 )
1583  return SCIP_ERROR;
1584 
1585  weights[v] = (lst - est) / (demands[v] * durations[v]); /*lint !e653*/
1586  }
1587  SCIPsortRealPtrPtrIntInt(weights, (void*)binvars, (void*)vars, durations, demands, nvars);
1588 
1589  SCIPfreeBufferArray(scip, &weights);
1590 
1591  while( nvars > 1 )
1592  {
1593  SCIP_CALL( solveCumulative(scip, nvars-1, vars, durations, demands, consdata->capacity, consdata->hmin, consdata->hmax, TRUE,
1594  lbs, ubs, 2000LL, &solved, &infeasible, &unbounded, &error) );
1595 
1596  if( !infeasible )
1597  break;
1598  nvars--;
1599  }
1600 
1601  /**@todo try to shrink the initial explanation */
1602 
1604 
1605  for( v = 0; v < nvars; ++v )
1606  {
1607  SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[v]) );
1608 
1609  /* we have to add the lower and upper bounds of of the start time variable to have a valid reason */
1610  SCIP_CALL( SCIPaddConflictLb(scip, vars[v], NULL) );
1611  SCIP_CALL( SCIPaddConflictUb(scip, vars[v], NULL) );
1612  }
1613 
1614  /* perform conflict analysis */
1615  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1616  }
1617  else
1618  {
1619  SCIP_Bool infeasible;
1620  SCIP_Bool tightened;
1621  SCIP_Bool allfixed;
1622  int v;
1623 
1624  allfixed = TRUE;
1625 
1626  for( v = 0; v < nvars; ++v )
1627  {
1628  /* check if variable is fixed */
1629  if( lbs[v] + 0.5 > ubs[v] )
1630  {
1631  SCIP_CALL( SCIPfixVar(scip, vars[v], lbs[v], &infeasible, &tightened) );
1632  assert(!infeasible);
1633 
1634  if( tightened )
1635  {
1636  (*nfixedvars)++;
1637  consdata->triedsolving = FALSE;
1638  }
1639  }
1640  else
1641  {
1642  SCIP_CALL( SCIPtightenVarLb(scip, vars[v], lbs[v], TRUE, &infeasible, &tightened) );
1643  assert(!infeasible);
1644 
1645  if( tightened )
1646  {
1647  (*nchgbds)++;
1648  consdata->triedsolving = FALSE;
1649  }
1650 
1651  SCIP_CALL( SCIPtightenVarUb(scip, vars[v], ubs[v], TRUE, &infeasible, &tightened) );
1652  assert(!infeasible);
1653 
1654  if( tightened )
1655  {
1656  (*nchgbds)++;
1657  consdata->triedsolving = FALSE;
1658  }
1659 
1660  allfixed = FALSE;
1661  }
1662  }
1663 
1664  /* if all variables are fixed, remove the optcumulative constraint since it is redundant */
1665  if( allfixed )
1666  {
1667  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1668  (*ndelconss)++;
1669  }
1670  }
1671  }
1672 
1673  SCIPfreeBufferArray(scip, &ubs);
1674  SCIPfreeBufferArray(scip, &lbs);
1675 
1676  return SCIP_OKAY;
1677 }
1678 
1679 /** check if the given constrait is valid; checks each starting point of a job whether the remaining capacity is at
1680  * least zero or not. If not (*violated) is set to TRUE
1681  */
1682 static
1684  SCIP* scip, /**< SCIP data structure */
1685  SCIP_CONS* cons, /**< constraint to be checked */
1686  SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
1687  SCIP_Bool* violated, /**< pointer to store if the constraint is violated */
1688  SCIP_Bool printreason /**< should the reason for the violation be printed? */
1689  )
1690 {
1691  SCIP_CONSDATA* consdata;
1692  SCIP_VAR** binvars;
1693  SCIP_VAR** vars;
1694  SCIP_Bool auxiliary;
1695  int* demands;
1696  int* durations;
1697  int nfixedones;
1698  int nfixedzeros;
1699  int nvars;
1700 
1701  assert(scip != NULL);
1702  assert(cons != NULL);
1703  assert(violated != NULL);
1704 
1705  consdata = SCIPconsGetData(cons);
1706  assert(consdata != NULL);
1707 
1708  SCIPdebugMessage("check optcumulative constraints <%s>\n", SCIPconsGetName(cons));
1709 
1710  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, consdata->nvars) );
1711  SCIP_CALL( SCIPallocBufferArray(scip, &vars, consdata->nvars) );
1712  SCIP_CALL( SCIPallocBufferArray(scip, &durations, consdata->nvars) );
1713  SCIP_CALL( SCIPallocBufferArray(scip, &demands, consdata->nvars) );
1714 
1715  /* collect information of all activities which are assigned to that machine in the given solution */
1716  collectSolActivities(scip, consdata, sol, binvars, vars, durations, demands, &nvars, &nfixedones, &nfixedzeros, &auxiliary);
1717 
1718  if( nvars > 0 )
1719  {
1720  /* check the cumulative condition */
1721  SCIP_CALL( SCIPcheckCumulativeCondition(scip, sol, nvars, vars,
1722  durations, demands, consdata->capacity, consdata->hmin, consdata->hmax, violated, cons, printreason) );
1723  }
1724 
1725  /* free all buffers */
1726  SCIPfreeBufferArray(scip, &demands);
1727  SCIPfreeBufferArray(scip, &durations);
1728  SCIPfreeBufferArray(scip, &vars);
1729  SCIPfreeBufferArray(scip, &binvars);
1730 
1731  return SCIP_OKAY;
1732 }
1733 
1734 /** check if the given constrait is valid; checks each starting point of a job whether the remaining capacity is at
1735  * least zero or not. If not (*violated) is set to TRUE
1736  */
1737 static
1739  SCIP* scip, /**< SCIP data structure */
1740  SCIP_CONS* cons, /**< constraint to be checked */
1741  SCIP_SOL* trysol, /**< primal solution to construct, or NULL */
1742  SCIP_Bool* violated, /**< pointer to store if the constraint is violated/infeasible */
1743  SCIP_Bool* consadded, /**< pointer to store if a constraint was added */
1744  SCIP_Bool* solfeasible /**< pointer to store if the constraint solution is potentially feasible */
1745  )
1746 {
1747  SCIP_CONSDATA* consdata;
1748  SCIP_VAR** binvars;
1749  SCIP_VAR** vars;
1750  SCIP_Bool auxiliary;
1751  int* demands;
1752  int* durations;
1753  int nfixedones;
1754  int nfixedzeros;
1755  int nvars;
1756 
1757  assert(scip != NULL);
1758  assert(cons != NULL);
1759  assert(violated != NULL);
1760 
1761  consdata = SCIPconsGetData(cons);
1762  assert(consdata != NULL);
1763 
1764  SCIPdebugMessage("enforce optcumulative constraints <%s>\n", SCIPconsGetName(cons));
1765 
1766  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, consdata->nvars) );
1767  SCIP_CALL( SCIPallocBufferArray(scip, &vars, consdata->nvars) );
1768  SCIP_CALL( SCIPallocBufferArray(scip, &durations, consdata->nvars) );
1769  SCIP_CALL( SCIPallocBufferArray(scip, &demands, consdata->nvars) );
1770 
1771  /* collect information of all activities which are assigned to that machine in the given solution */
1772  collectSolActivities(scip, consdata, NULL, binvars, vars, durations, demands, &nvars, &nfixedones, &nfixedzeros, &auxiliary);
1773 
1774  (*violated) = FALSE;
1775 
1776  if( nvars > 0 )
1777  {
1778  /* check the cumulative condition */
1779  SCIP_CALL( SCIPcheckCumulativeCondition(scip, NULL, nvars, vars,
1780  durations, demands, consdata->capacity, consdata->hmin, consdata->hmax, violated, cons, FALSE) );
1781 
1782  if( *violated && auxiliary && !consdata->triedsolving )
1783  {
1784  SCIP_Real* lbs;
1785  SCIP_Real* ubs;
1786  SCIP_Bool infeasible;
1787  SCIP_Bool unbounded;
1788  SCIP_Bool error;
1789  SCIP_Bool solved;
1790 
1791  if( nfixedones == nvars )
1792  consdata->triedsolving = TRUE;
1793 
1794  SCIP_CALL( SCIPallocBufferArray(scip, &lbs, nvars) );
1795  SCIP_CALL( SCIPallocBufferArray(scip, &ubs, nvars) );
1796 
1797  /* solve the cumulative condition separately */
1798  SCIP_CALL( solveCumulative(scip, nvars, vars, durations, demands, consdata->capacity, consdata->hmin, consdata->hmax,
1799  FALSE, lbs, ubs, 1000LL, &solved, &infeasible, &unbounded, &error) );
1800  assert(!unbounded);
1801 
1802  if( !error )
1803  {
1804  if( infeasible )
1805  {
1806 
1807 #ifdef SCIP_DISABLED_CODE
1808  SCIP_Real* weights;
1809  int v;
1810 
1811  SCIP_CALL( SCIPallocBufferArray(scip, &weights, nvars) );
1812 
1813  for( v = 0; v < nvars; ++v )
1814  {
1815  int est;
1816  int lst;
1817 
1818  est = convertBoundToInt(scip, SCIPvarGetLbGlobal(vars[v]));
1819  lst = convertBoundToInt(scip, SCIPvarGetUbGlobal(vars[v]));
1820  weights[v] = (lst - est) / (consdata->demands[v] * consdata->durations[v]);
1821  }
1822  SCIPsortRealPtrPtrIntInt(weights, (void*)binvars, (void*)vars, durations, demands, nvars);
1823 
1824  SCIPfreeBufferArray(scip, &weights);
1825 
1826  while( nvars > 1 && !SCIPisStopped(scip) )
1827  {
1828  SCIP_CALL( solveCumulative(scip, nvars-1, vars, durations, demands, consdata->capacity, consdata->hmin, consdata->hmax,
1829  FALSE, lbs, ubs, 1000LL, &solved, &infeasible, &unbounded, &error) );
1830 
1831  if( !infeasible )
1832  break;
1833 
1834  nvars--;
1835  }
1836 #endif
1837 
1838  /* create and adds a conflict constraint (logicor constraint) */
1839  SCIP_CALL( createConflictCons(scip, SCIPconsGetName(cons), binvars, nvars) );
1840 
1841  (*solfeasible) = FALSE;
1842  (*consadded) = TRUE;
1843  }
1844  else if( solved && *solfeasible && trysol != NULL )
1845  {
1846  int v;
1847 
1848  for(v = 0; v < nvars; ++v )
1849  {
1850  SCIP_CALL( SCIPsetSolVal(scip, trysol, vars[v], lbs[v]) );
1851  }
1852  }
1853  else
1854  (*solfeasible) = FALSE;
1855  }
1856 
1857  SCIPfreeBufferArray(scip, &ubs);
1858  SCIPfreeBufferArray(scip, &lbs);
1859  }
1860  }
1861 
1862  /* free all buffers */
1863  SCIPfreeBufferArray(scip, &demands);
1864  SCIPfreeBufferArray(scip, &durations);
1865  SCIPfreeBufferArray(scip, &vars);
1866  SCIPfreeBufferArray(scip, &binvars);
1867 
1868  return SCIP_OKAY;
1869 }
1870 
1871 #if 0
1872 /** enforce the LP or pseudo solution */
1873 static
1874 SCIP_RETCODE enfoCons(
1875  SCIP* scip, /**< SCIP data structure */
1876  SCIP_CONS* cons, /**< constraint to be checked */
1877  SCIP_Bool* violated, /**< pointer to store if the constraint is violated */
1878  SCIP_Bool* rowadded /**< pointer to store if a row was added */
1879  )
1880 {
1881  SCIP_CONSDATA* consdata;
1882  SCIP_VAR** binvars;
1883  SCIP_VAR** vars;
1884  int* demands;
1885  int* durations;
1886  SCIP_Bool auxiliary;
1887  SCIP_Bool cutoff;
1888  int nvars;
1889 
1890  assert(scip != NULL);
1891  assert(cons != NULL);
1892  assert(violated != NULL);
1893 
1894  SCIPdebugMessage("check optcumulative constraints <%s>\n", SCIPconsGetName(cons));
1895 
1896  consdata = SCIPconsGetData(cons);
1897  assert(consdata != NULL);
1898 
1899  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, consdata->nvars) );
1900  SCIP_CALL( SCIPallocBufferArray(scip, &vars, consdata->nvars) );
1901  SCIP_CALL( SCIPallocBufferArray(scip, &durations, consdata->nvars) );
1902  SCIP_CALL( SCIPallocBufferArray(scip, &demands, consdata->nvars) );
1903 
1904  /* collect information of all activities which are assigned to that machine in the given solution */
1905  collectSolActivities(scip, consdata, NULL, binvars, vars, durations, demands, &nvars, &auxiliary);
1906 
1907  if( nvars > 0 )
1908  {
1909  /* check the cumulative condition */
1910  SCIP_CALL( SCIPcheckCumulativeCondition(scip, NULL, nvars, vars,
1911  durations, demands, consdata->capacity, consdata->hmin, consdata->hmax, violated, cons, FALSE) );
1912 
1913  if( *violated )
1914  {
1915 #if 0
1916  /* create row */
1917  SCIP_CALL( createRow(scip, SCIPconsGetName(cons), binvars, vars, durations, demands, nvars,
1918  consdata->capacity, TRUE, &cutoff) );
1919 #endif
1920  /* reset constraint age since it successfully detected infeasibility */
1921  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1922  }
1923  else
1924  {
1925  /* increase constraint age since it did not detected infeasibility */
1926  SCIP_CALL( SCIPincConsAge(scip, cons) );
1927  }
1928  }
1929 
1930  /* free all buffers */
1931  SCIPfreeBufferArray(scip, &demands);
1932  SCIPfreeBufferArray(scip, &durations);
1933  SCIPfreeBufferArray(scip, &vars);
1934  SCIPfreeBufferArray(scip, &binvars);
1935 
1936  return SCIP_OKAY;
1937 }
1938 #endif
1939 
1940 /** upgrade constraints to an cumulative constraint */
1941 static
1943  SCIP* scip, /**< SCIP data structure */
1944  SCIP_CONS* cons, /**< constraint to be checked */
1945  int* ndelconss, /**< pointer to store the number of deleted constraints */
1946  int* nupgdconss, /**< pointer to store the number of upgrade constraints */
1947  SCIP_Bool* mustpropagate /**< pointer to store if the constraints has to be propagated */
1948  )
1949 {
1950  SCIP_CONSDATA* consdata;
1951  int nvars;
1952 
1953  consdata = SCIPconsGetData(cons);
1954  assert(consdata != NULL);
1955 
1956  nvars = consdata->nvars;
1957 
1958  /* (debug) check if the counter of the constraint are correct */
1959  checkCounters(consdata);
1960 
1961  if( nvars == 0 && consdata->nfixedzeros == nvars )
1962  {
1963  SCIPdebugMessage("delete optcumulative constraint <%s> since it contains no jobs\n", SCIPconsGetName(cons));
1964  SCIP_CALL( SCIPdelCons(scip, cons) );
1965  (*ndelconss)++;
1966  (*mustpropagate) = FALSE;
1967  }
1968  else if( nvars == 1 )
1969  {
1970  SCIPdebugMessage("delete optcumulative constraint <%s> since it contains only one jobs\n", SCIPconsGetName(cons));
1971 
1972  if( consdata->capacity < consdata->demands[0] )
1973  {
1974  SCIP_Bool infeasible;
1975  SCIP_Bool tightened;
1976 
1977  SCIP_CALL( SCIPfixVar(scip, consdata->binvars[0], 0.0, &infeasible, &tightened) );
1978  assert(!infeasible);
1979  assert(tightened);
1980  }
1981 
1982  SCIP_CALL( SCIPdelCons(scip, cons) );
1983  (*ndelconss)++;
1984  (*mustpropagate) = FALSE;
1985  }
1986  else if( consdata->nglbfixedones == nvars )
1987  {
1988  SCIP_CONS* cumulativecons;
1989  char name[SCIP_MAXSTRLEN];
1990 
1991  SCIPdebugMessage("upgrade optcumulative constraint <%s> to cumulative constraint\n", SCIPconsGetName(cons));
1992 
1993  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_cumulative", SCIPconsGetName(cons));
1994 
1995  SCIP_CALL( SCIPcreateConsCumulative(scip, &cumulativecons, name, consdata->nvars, consdata->vars, consdata->durations, consdata->demands, consdata->capacity,
1998  SCIP_CALL( SCIPsetHminCumulative(scip, cumulativecons, consdata->hmin) );
1999  SCIP_CALL( SCIPsetHmaxCumulative(scip, cumulativecons, consdata->hmax) );
2000  SCIP_CALL( SCIPaddCons(scip, cumulativecons) );
2001  SCIP_CALL( SCIPreleaseCons(scip, &cumulativecons) );
2002 
2003  assert(!SCIPconsIsDeleted(cons));
2004  SCIP_CALL( SCIPdelCons(scip, cons) );
2005 
2006  (*nupgdconss)++;
2007  (*mustpropagate) = FALSE;
2008  }
2009  else if( consdata->nfixedones + consdata->nfixedzeros == nvars && consdata->nfixedones > 0 )
2010  {
2011  SCIP_CONS* cumulativecons;
2012 
2013  SCIP_VAR** binvars;
2014  SCIP_VAR** vars;
2015  int* durations;
2016  int* demands;
2017  int nfixedzeros;
2018  int nfixedones;
2019 
2020  SCIP_Bool auxiliary;
2021 
2022  char name[SCIP_MAXSTRLEN];
2023 
2024  SCIPdebugMessage("upgrade optcumulative constraint <%s> to cumulative constraint (locally)\n", SCIPconsGetName(cons));
2025 
2026  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_cumulative", SCIPconsGetName(cons));
2027 
2028  SCIP_CALL( SCIPallocBufferArray(scip, &vars, consdata->nvars) );
2029  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, consdata->nvars) );
2030  SCIP_CALL( SCIPallocBufferArray(scip, &demands, consdata->nvars) );
2031  SCIP_CALL( SCIPallocBufferArray(scip, &durations, consdata->nvars) );
2032 
2033  /* collect all activities which are locally assigned to that machine */
2034  collectActivities(consdata, binvars, vars, durations, demands, &nfixedones, &nfixedzeros, &auxiliary);
2035 
2036  SCIP_CALL( SCIPcreateConsCumulative(scip, &cumulativecons, name, nfixedones, vars, durations, demands, consdata->capacity,
2039  SCIP_CALL( SCIPsetHminCumulative(scip, cumulativecons, consdata->hmin) );
2040  SCIP_CALL( SCIPsetHmaxCumulative(scip, cumulativecons, consdata->hmax) );
2041  SCIP_CALL( SCIPaddConsLocal(scip, cumulativecons, NULL) );
2042  SCIP_CALL( SCIPreleaseCons(scip, &cumulativecons) );
2043 
2044  /* free all buffers */
2045  SCIPfreeBufferArray(scip, &durations);
2046  SCIPfreeBufferArray(scip, &demands);
2047  SCIPfreeBufferArray(scip, &binvars);
2048  SCIPfreeBufferArray(scip, &vars);
2049 
2050  assert(!SCIPconsIsDeleted(cons));
2051  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
2052 
2053  (*nupgdconss)++;
2054  (*mustpropagate) = FALSE;
2055  }
2056  else
2057  assert(consdata->nvars > 1);
2058 
2059  return SCIP_OKAY;
2060 }
2061 
2062 /** since the binary variable is fixed to zero, depending in the objective coefficient of the integer variable and the
2063  * rounding locks, we might can fix the integer variable
2064  */
2065 static
2067  SCIP* scip, /**< SCIP data structure */
2068  SCIP_VAR* var, /**< integer variable to fix */
2069  SCIP_Bool downlock, /**< does the variable has down lock given by the optcumulative constraint */
2070  SCIP_Bool uplock, /**< does the variable has up lock given by the optcumulative constraint */
2071  int* nchgbds /**< pointer to store the number changed variable bounds */
2072  )
2073 {
2074  SCIP_Real objval;
2075  SCIP_Real fixvalue;
2076  SCIP_Bool infeasible;
2077  SCIP_Bool tightened;
2078 
2079  objval = SCIPvarGetObj(var);
2080  fixvalue = SCIP_INVALID;
2081 
2082  /* if SCIP is in probing mode or during repropagation we cannot perform this dual reductions since this dual
2083  * reduction would end in an implication which can lead to cutoff the optimal solution
2084  */
2085  if( SCIPinProbing(scip) || SCIPinRepropagation(scip) )
2086  return SCIP_OKAY;
2087 
2088  assert(SCIPvarGetNLocksDown(var) >= (int)downlock);
2089  assert(SCIPvarGetNLocksUp(var) >= (int)uplock);
2090 
2091  if( SCIPisZero(scip, objval) )
2092  {
2093  /* the integer start time variable has a zero objective value; if only the optcumulative constraint
2094  * handler has a problem with rounding it down or up, then this issue is obsolete since binary
2095  * variable is fixed zero; therefore, rounding the integer down or up is a feasible dual reduction
2096  */
2097  if( SCIPvarGetNLocksDown(var) == (int)downlock )
2098  fixvalue = SCIPvarGetLbLocal(var);
2099  else if( SCIPvarGetNLocksUp(var) == (int)uplock )
2100  fixvalue = SCIPvarGetUbLocal(var);
2101  else
2102  return SCIP_OKAY;
2103  }
2104  else if( SCIPisNegative(scip, objval) && SCIPvarGetNLocksUp(var) == (int)uplock )
2105  {
2106  /* the integer start time variable has a negative objective value and only the optcumulative constraint
2107  * handler has a problem with rounding it up; since the binary variable is fixed the rounding up
2108  * issue is obsolete; there rounding it to the upper bound is the best thing we can do
2109  */
2110  fixvalue = SCIPvarGetUbLocal(var);
2111  }
2112  else if( SCIPisPositive(scip, objval) && SCIPvarGetNLocksDown(var) == (int)downlock )
2113  {
2114  /* the integer start time variable has a positive objective value and only the optcumulative
2115  * constraint handler has a problem with rounding it down; since the binary variable is fixed the
2116  * rounding down issue is obsolete; there rounding it to the lower bound is the best thing we can do
2117  */
2118  fixvalue = SCIPvarGetLbLocal(var);
2119  }
2120  else
2121  return SCIP_OKAY;
2122 
2123  /* the integer start time variable has a positive objective value and only the optcumulative
2124  * constraint handler has a problem with rounding it down; since the binary variable is fixed the
2125  * rounding down issue is obsolete; there rounding it to the lower bound is the best thing we can do
2126  */
2127  assert(fixvalue < SCIP_INVALID);
2128  SCIP_CALL( SCIPfixVar(scip, var, fixvalue, &infeasible, &tightened) );
2129  assert(!infeasible);
2130 
2131  if( tightened )
2132  (*nchgbds)++;
2133 
2134  return SCIP_OKAY;
2135 }
2136 
2137 /** deletes coefficient at given position from constraint data */
2138 static
2140  SCIP* scip, /**< SCIP data structure */
2141  SCIP_CONSDATA* consdata, /**< cumulative constraint data */
2142  SCIP_CONS* cons, /**< knapsack constraint */
2143  int pos /**< position of coefficient to delete */
2144  )
2145 {
2146  assert(consdata != NULL);
2147  assert(pos < consdata->nvars);
2148 
2149  /* remove the rounding locks for the deleted variable */
2150  SCIP_CALL( unlockRounding(scip, cons, consdata->binvars[pos],
2151  consdata->vars[pos], consdata->downlocks[pos], consdata->uplocks[pos]) );
2152 
2153  consdata->downlocks[pos] = FALSE;
2154  consdata->uplocks[pos] = FALSE;
2155 
2156  if( SCIPconsIsTransformed(cons) )
2157  {
2158  SCIP_CONSHDLR* conshdlr;
2159  SCIP_CONSHDLRDATA* conshdlrdata;
2160 
2161  /* get event handler */
2162  conshdlr = SCIPconsGetHdlr(cons);
2163  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2164  assert(conshdlrdata != NULL);
2165  assert(conshdlrdata->eventhdlrbinvars != NULL);
2166  assert(conshdlrdata->eventhdlrintvars != NULL);
2167 
2168  /* drop bound change events of variable */
2169  SCIP_CALL( dropEventBinvar(scip, cons, conshdlrdata->eventhdlrbinvars, pos) );
2170  SCIP_CALL( dropEventIntvar(scip, cons, conshdlrdata->eventhdlrintvars, pos) );
2171  }
2172 
2173  SCIPdebugMessage("remove variable <%s> from optcumulative constraint <%s>\n",
2174  SCIPvarGetName(consdata->binvars[pos]), SCIPconsGetName(cons));
2175 
2176  if( pos != consdata->nvars - 1 )
2177  {
2178  consdata->binvars[pos] = consdata->binvars[consdata->nvars-1];
2179  consdata->vars[pos] = consdata->vars[consdata->nvars-1];
2180  consdata->demands[pos] = consdata->demands[consdata->nvars-1];
2181  consdata->durations[pos] = consdata->durations[consdata->nvars-1];
2182  consdata->downlocks[pos] = consdata->downlocks[consdata->nvars-1];
2183  consdata->uplocks[pos] = consdata->uplocks[consdata->nvars-1];
2184  }
2185 
2186  consdata->nvars--;
2187 
2188  /* (debug) check if the counter of the constraint are correct */
2189  checkCounters(consdata);
2190 
2191  consdata->relaxadded = FALSE;
2192  consdata->normalized = FALSE;
2193 
2194  return SCIP_OKAY;
2195 }
2196 
2197 /** remove all jobs for which the binary variable is globally fixed to zero */
2198 static
2200  SCIP* scip, /**< SCIP data structure */
2201  SCIP_CONS* cons, /**< constraint to be checked */
2202  int* nchgcoefs, /**< pointer to store the number changed coefficients */
2203  int* nchgbds /**< pointer to store the number changed variable bounds */
2204  )
2205 {
2206  SCIP_CONSDATA* consdata;
2207  int v;
2208 
2209  consdata = SCIPconsGetData(cons);
2210  assert(consdata != NULL);
2211 
2212  for( v = consdata->nvars-1; v >= 0 && consdata->nglbfixedzeros > 0; --v )
2213  {
2214  assert(consdata->binvars[v] != NULL);
2215  if( SCIPvarGetUbGlobal(consdata->binvars[v]) < 0.5 )
2216  {
2217  SCIPdebugMessage("variable <%s> is globally fixed to zero\n", SCIPvarGetName(consdata->binvars[v]));
2218 
2219  /* fix integer start time variable if possible */
2220  if( SCIPconsIsChecked(cons) )
2221  {
2222  SCIP_CALL( fixIntegerVariable(scip, consdata->vars[v], consdata->downlocks[v], consdata->uplocks[v], nchgbds) );
2223  }
2224 
2225  /* remove the job */
2226  SCIP_CALL( consdataDeletePos(scip, consdata, cons, v) );
2227  (*nchgcoefs)++;
2228 
2229  /* mark constraint to be checked for redundancy */
2230  consdata->triedredundant = TRUE;
2231  }
2232  }
2233 
2234  /* (debug) check if the counter of the constraint are correct */
2235  checkCounters(consdata);
2236 
2237  /* check that all variables fixed to zero are removed */
2238  assert(consdata->nglbfixedzeros == 0);
2239 
2240  return SCIP_OKAY;
2241 }
2242 
2243 /** remove jobs which have a duration or demand of zero (zero energy) or lay outside the efficient horizon [hmin, hmax);
2244  * this is done in the SCIP_DECL_CONSINITPRE() callback
2245  */
2246 static
2248  SCIP* scip, /**< SCIP data structure */
2249  SCIP_CONS* cons /**< constraint to propagate */
2250  )
2251 {
2252  SCIP_CONSDATA* consdata;
2253  SCIP_VAR* var;
2254  int demand;
2255  int duration;
2256  int hmin;
2257  int hmax;
2258  int est;
2259  int lct;
2260  int j;
2261 
2262  assert(scip != NULL);
2263  assert(cons != NULL);
2264 
2265  consdata = SCIPconsGetData(cons);
2266  assert(consdata != NULL);
2267 
2268  hmin = consdata->hmin;
2269  hmax = consdata->hmax;
2270 
2271  SCIPdebugMessage("check for irrelevant jobs within cumulative constraint <%s>[%d,%d)\n",
2272  SCIPconsGetName(cons), hmin, hmax);
2273 
2274  for( j = consdata->nvars-1; j >= 0; --j )
2275  {
2276  var = consdata->vars[j];
2277  demand = consdata->demands[j];
2278  duration = consdata->durations[j];
2279 
2280  /* earliest completion time (ect) and latest start time (lst) */
2281  est = convertBoundToInt(scip, SCIPvarGetLbGlobal(var));
2282  lct = convertBoundToInt(scip, SCIPvarGetUbGlobal(var)) + duration;
2283 
2284  if( demand == 0 || duration == 0 )
2285  {
2286  /* jobs with zero demand or zero duration can be removed */
2287  SCIPdebugMessage(" remove variable <%s> due to zero %s\n",
2288  SCIPvarGetName(var), demand == 0 ? "demand" : "duration");
2289 
2290  /* remove variable form constraint */
2291  SCIP_CALL( consdataDeletePos(scip, consdata, cons, j) );
2292  }
2293  else if( est >= hmax || lct <= hmin )
2294  {
2295  SCIPdebugMessage(" remove variable <%s>[%d,%d] with duration <%d>\n",
2296  SCIPvarGetName(var), est, lct - duration, duration);
2297 
2298  /* delete variable at the given position */
2299  SCIP_CALL( consdataDeletePos(scip, consdata, cons, j) );
2300  }
2301  }
2302 
2303  return SCIP_OKAY;
2304 }
2305 
2306 /** presolve cumulative condition w.r.t. effective horizon by detecting irrelevant variables */
2307 static
2309  SCIP* scip, /**< SCIP data structure */
2310  SCIP_CONS* cons, /**< constraint to be checked */
2311  int* nfixedvars, /**< pointer to store the number of fixed variables */
2312  int* nchgcoefs, /**< pointer to store the number of changed coefficients */
2313  int* nchgsides, /**< pointer to store the number of changed sides */
2314  SCIP_Bool* cutoff /**< buffer to store whether a cutoff is detected */
2315  )
2316 {
2317  SCIP_CONSDATA* consdata;
2318  SCIP_Bool* irrelevants;
2319  int nvars;
2320  int v;
2321 
2322  consdata = SCIPconsGetData(cons);
2323  assert(consdata != NULL);
2324 
2325  nvars = consdata->nvars;
2326  assert(nvars > 1);
2327 
2328  SCIP_CALL( SCIPallocBufferArray(scip, &irrelevants, nvars) );
2329  BMSclearMemoryArray(irrelevants, nvars);
2330 
2331  /* use presolving of cumulative constraint handler to process cumulative condition */
2332  SCIP_CALL( SCIPpresolveCumulativeCondition(scip, nvars, consdata->vars, consdata->durations,
2333  consdata->hmin, consdata->hmax, consdata->downlocks, consdata->uplocks, cons,
2334  irrelevants, nfixedvars, nchgsides, cutoff) );
2335 
2336  /* remove all variable which are irrelevant; note we have to iterate backwards do to the functionality of of
2337  * consdataDeletePos()
2338  */
2339  for( v = nvars-1; v >= 0; --v )
2340  {
2341  SCIP_VAR* var;
2342  int ect;
2343  int lst;
2344 
2345  if( !irrelevants[v] )
2346  continue;
2347 
2348  var = consdata->vars[v];
2349  assert(var != NULL);
2350 
2351  ect = convertBoundToInt(scip, SCIPvarGetLbGlobal(var)) + consdata->durations[v];
2352  lst = convertBoundToInt(scip, SCIPvarGetUbGlobal(var));
2353 
2354  /* check if the jobs runs completely during the effective horizon */
2355  if( lst <= consdata->hmin && ect >= consdata->hmax )
2356  {
2357  assert(!consdata->downlocks[v]);
2358  assert(!consdata->uplocks[v]);
2359 
2360  if( consdata->capacity < consdata->demands[v] )
2361  {
2362  SCIP_Bool infeasible;
2363  SCIP_Bool tightened;
2364 
2365  SCIP_CALL( SCIPfixVar(scip, consdata->binvars[0], 0.0, &infeasible, &tightened) );
2366  assert(!infeasible);
2367  assert(tightened);
2368  (*nfixedvars)++;
2369 
2370  consdata->capacity -= consdata->demands[v];
2371 
2372  SCIP_CALL( consdataDeletePos(scip, consdata, cons, v) );
2373  (*nchgcoefs)++;
2374  }
2375  }
2376  else
2377  {
2378  SCIP_CALL( consdataDeletePos(scip, consdata, cons, v) );
2379  (*nchgcoefs)++;
2380  }
2381  }
2382 
2383  SCIPdebugMessage("constraint <%s>[%d,%d) <= %d has %d variables left\n", SCIPconsGetName(cons),
2384  consdata->hmin, consdata->hmax, consdata->capacity, nvars);
2385 
2386  SCIPfreeBufferArray(scip, &irrelevants);
2387 
2388  return SCIP_OKAY;
2389 }
2390 
2391 /** create an an set partitioning constraint */
2392 static
2394  SCIP* scip, /**< SCIP data structure */
2395  SCIP_VAR* var1, /**< first variable */
2396  SCIP_VAR* var2 /**< second variable */
2397  )
2398 {
2399  SCIP_CONS* cons;
2400 
2401  SCIP_CALL( SCIPcreateConsBasicSetpack(scip, &cons, "implication", 0, NULL) );
2402  SCIP_CALL( SCIPaddCons(scip, cons) );
2403 
2404  SCIP_CALL( SCIPaddCoefSetppc(scip, cons, var1) );
2405  SCIP_CALL( SCIPaddCoefSetppc(scip, cons, var2) );
2406  SCIPdebugPrintCons(scip, cons, NULL);
2407  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2408 
2409  return SCIP_OKAY;
2410 }
2411 
2412 /** create variable bound constraint */
2413 static
2415  SCIP* scip, /**< SCIP data structure */
2416  SCIP_VAR* binvar, /**< binary variable x */
2417  SCIP_VAR* intvar, /**< integer variable y */
2418  int bound, /**< variable bound */
2419  SCIP_Bool lower /**< variable lower bound? (Otherwise upper bound) */
2420  )
2421 {
2422  SCIP_CONS* cons;
2423  SCIP_Real coef;
2424  SCIP_Real lhs;
2425  SCIP_Real rhs;
2426 
2427  assert(scip != NULL);
2428 
2429  if( lower )
2430  {
2431  lhs = SCIPvarGetLbGlobal(intvar);
2432  rhs = SCIPinfinity(scip);
2433  coef = lhs - bound;
2434  }
2435  else
2436  {
2437  lhs = -SCIPinfinity(scip);
2438  rhs = SCIPvarGetUbGlobal(intvar);
2439  coef = rhs - bound;
2440  }
2441 
2442  SCIP_CALL( SCIPcreateConsBasicVarbound(scip, &cons, "implication", intvar, binvar, coef, lhs, rhs) );
2443  SCIP_CALL( SCIPaddCons(scip, cons) );
2444  SCIPdebugPrintCons(scip, cons, NULL);
2445  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2446 
2447  return SCIP_OKAY;
2448 }
2449 
2450 /** create bound disjunction constraint */
2451 static
2453  SCIP* scip, /**< SCIP data structure */
2454  SCIP_VAR* binvar, /**< binary variable x */
2455  SCIP_VAR* intvar, /**< integer variable y */
2456  int lb, /**< lower bound */
2457  int ub /**< lower bound */
2458  )
2459 {
2460  SCIP_CONS* cons;
2461  SCIP_VAR** vars;
2462  SCIP_BOUNDTYPE* boundtypes;
2463  SCIP_Real* bounds;
2464 
2465  SCIP_CALL( SCIPallocBufferArray(scip, &vars, 3) );
2466  SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, 3) );
2467  SCIP_CALL( SCIPallocBufferArray(scip, &bounds, 3) );
2468 
2469  /* intvar >= ub */
2470  vars[0] = intvar;
2471  boundtypes[0] = SCIP_BOUNDTYPE_LOWER;
2472  bounds[0] = ub;
2473 
2474  /* intvar <= lb */
2475  vars[1] = intvar;
2476  boundtypes[1] = SCIP_BOUNDTYPE_UPPER;
2477  bounds[1] = lb;
2478 
2479  /* binvar <= 0.0 */
2480  vars[2] = binvar;
2481  boundtypes[2] = SCIP_BOUNDTYPE_LOWER;
2482  bounds[2] = 0.0;
2483 
2484  SCIP_CALL( SCIPcreateConsBasicBounddisjunction(scip, &cons, "implication", 3, vars, boundtypes, bounds) );
2485  SCIP_CALL( SCIPaddCons(scip, cons) );
2486  SCIPdebugPrintCons(scip, cons, NULL);
2487  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2488 
2489  SCIPfreeBufferArray(scip, &vars);
2490  SCIPfreeBufferArray(scip, &boundtypes);
2491  SCIPfreeBufferArray(scip, &bounds);
2492 
2493  return SCIP_OKAY;
2494 }
2495 
2496 /** detect implication */
2497 static
2499  SCIP* scip, /**< SCIP data structure */
2500  SCIP_CONS* cons, /**< optcumulative constraint */
2501  int* nchgcoefs, /**< pointer to store the number of changed coefficients */
2502  int* naddconss /**< pointer to store the number of added constraints */
2503  )
2504 {
2505  SCIP_CONSDATA* consdata;
2506  SCIP_VAR** binvars;
2507  SCIP_VAR** vars;
2508  int* durations;
2509  int hmin;
2510  int hmax;
2511  int v;
2512 
2513  consdata = SCIPconsGetData(cons);
2514  assert(consdata != NULL);
2515 
2516  vars = consdata->vars;
2517  binvars = consdata->binvars;
2518  durations = consdata->durations;
2519 
2520  hmin = consdata->hmin;
2521  hmax = consdata->hmax;
2522  assert(hmin < hmax);
2523 
2524  SCIPdebugMessage("search for implications <%s>[%d,%d) <= %d\n", SCIPconsGetName(cons), hmin, hmax, consdata->capacity);
2525 
2526  /* we loop backwards since we are deleting variable out of the constraint */
2527  for( v = consdata->nvars-1; v >= 0; --v )
2528  {
2529  SCIP_VAR* var;
2530  int start;
2531  int end;
2532 
2533  var = vars[v];
2534  assert(var != NULL);
2535 
2536  /* skip start time variables which are not globally fixed */
2537  if( SCIPvarGetLbGlobal(var) + 0.5 < SCIPvarGetUbGlobal(var) )
2538  continue;
2539 
2540  /* adjust the code for resources with capacity larger than one ??????????????? */
2541  if( consdata->demands[v] < consdata->capacity )
2542  continue;
2543 
2544  start = convertBoundToInt(scip, SCIPvarGetLbGlobal(var));
2545  assert(start < hmax);
2546 
2547  end = start + durations[v];
2548  assert(end > hmin);
2549 
2550  SCIPdebugMessage("candidate <%s> (start %d, end %d, demand %d)\n", SCIPvarGetName(var), start, end, consdata->demands[v]);
2551 
2552  if( start <= hmin && end >= hmax )
2553  {
2554  int j;
2555 
2556  /* job runs during the complete time horizon */
2557  for( j = 0; j < consdata->nvars; ++j )
2558  {
2559  SCIP_VAR* implvar;
2560  int est;
2561  int ect;
2562  int lst;
2563 
2564  if( j == v )
2565  continue;
2566 
2567  implvar = vars[j];
2568  assert(implvar != NULL);
2569 
2570  est = convertBoundToInt(scip, SCIPvarGetLbGlobal(implvar));
2571  ect = est + durations[j];
2572  lst = convertBoundToInt(scip, SCIPvarGetUbGlobal(implvar));
2573 
2574  SCIPdebugMessage("variable <%s>[%d,%d] (duration %d, demand %d)\n", SCIPvarGetName(implvar), est, lst, durations[j], consdata->demands[j]);
2575 
2576  /* check if the job will overlap with effective horizon, hence, only one of the two jobs can be scheduled on
2577  * that machine
2578  */
2579  if( ect > hmin && lst < hmax )
2580  {
2581  SCIP_CALL( createSetPackingCons(scip, binvars[v], binvars[j]) );
2582  (*naddconss)++;
2583  }
2584  else if( lst < hmax )
2585  {
2586  SCIP_CALL( createVarboundCons(scip, binvars[v], implvar, hmin - durations[j], FALSE) );
2587  (*naddconss)++;
2588  }
2589  else if( ect > hmin )
2590  {
2591  SCIP_CALL( createVarboundCons(scip, binvars[v], implvar, hmax, TRUE) );
2592  (*naddconss)++;
2593  }
2594  else
2595  {
2596  SCIP_CALL( createBounddisjunctionCons(scip, binvars[v], implvar, hmin - durations[j], hmax) );
2597  (*naddconss)++;
2598  }
2599  }
2600  }
2601  else if( start <= hmin )
2602  {
2603  int j;
2604 
2605  assert(end > hmin);
2606 
2607  /* job overlaps with hmin */
2608  for( j = 0; j < consdata->nvars; ++j )
2609  {
2610  SCIP_VAR* implvar;
2611  int est;
2612  int ect;
2613  int lst;
2614 
2615  if( j == v )
2616  continue;
2617 
2618  implvar = vars[j];
2619  assert(implvar != NULL);
2620 
2621  est = convertBoundToInt(scip, SCIPvarGetLbGlobal(implvar));
2622  ect = est + durations[j];
2623  lst = convertBoundToInt(scip, SCIPvarGetUbGlobal(implvar));
2624 
2625  SCIPdebugMessage("variable <%s>[%d,%d] (duration %d, demand %d)\n", SCIPvarGetName(implvar), est, lst, durations[j], consdata->demands[j]);
2626 
2627  if( lst < ect && hmin < ect && lst < end )
2628  {
2629  /* job j has a core which overlaps with job v within the effective horizon, hence, both jobs cannot run
2630  * at same time on that machine
2631  */
2632  SCIP_CALL( createSetPackingCons(scip, binvars[v], binvars[j]) );
2633  (*naddconss)++;
2634  }
2635  else if( end > lst )
2636  {
2637  SCIP_CALL( createSetPackingCons(scip, binvars[v], binvars[j]) );
2638  (*naddconss)++;
2639  }
2640  else if( est < end )
2641  {
2642  SCIP_CALL( createVarboundCons(scip, binvars[v], implvar, end, TRUE) );
2643  (*naddconss)++;
2644  }
2645  }
2646  }
2647  else if( end >= hmax )
2648  {
2649  int j;
2650 
2651  assert(start < hmax);
2652 
2653  /* job overlaps with hmax; that means if the job is scheduled on that machine all other jobs have to finish
2654  * before that job starts
2655  */
2656  for( j = 0; j < consdata->nvars; ++j )
2657  {
2658  SCIP_VAR* implvar;
2659  int ect;
2660  int lst;
2661  int lct;
2662 
2663  if( j == v )
2664  continue;
2665 
2666  implvar = vars[j];
2667  assert(implvar != NULL);
2668 
2669  ect = convertBoundToInt(scip, SCIPvarGetLbGlobal(implvar)) + durations[j];
2670  lst = convertBoundToInt(scip, SCIPvarGetUbGlobal(implvar));
2671  lct = lst + durations[j];
2672 
2673  SCIPdebugMessage("variable <%s>[%d,%d] (duration %d, demand %d)\n", SCIPvarGetName(implvar), ect - durations[j], lst, durations[j], consdata->demands[j]);
2674 
2675  if( lst < ect && start < ect && lst < hmax )
2676  {
2677  /* job j has a core which overlaps with job v within the effective horizon, hence, both jobs cannot run
2678  * at same time on that machine
2679  */
2680  SCIP_CALL( createSetPackingCons(scip, binvars[v], binvars[j]) );
2681  (*naddconss)++;
2682  }
2683  else if( start < ect )
2684  {
2685  SCIP_CALL( createSetPackingCons(scip, binvars[v], binvars[j]) );
2686  (*naddconss)++;
2687  }
2688  else if( lct > start )
2689  {
2690  /* job j potentially finishes to late, hence, if job v runs on that machine we can bound the start time
2691  * variable of job j form above
2692  */
2693  SCIP_CALL( createVarboundCons(scip, binvars[v], implvar, start - durations[j], FALSE) );
2694  (*naddconss)++;
2695  }
2696  }
2697  }
2698  else
2699  continue;
2700 
2701  SCIP_CALL( consdataDeletePos(scip, consdata, cons, v) );
2702  (*nchgcoefs)++;
2703  }
2704 
2705  return SCIP_OKAY;
2706 }
2707 
2708 /** propgates given constraint */
2709 static
2711  SCIP* scip, /**< SCIP data structure */
2712  SCIP_CONS* cons, /**< constraint to be checked */
2713  SCIP_Bool conflictanalysis, /**< should conflict analysis be called for infeasible subproblems */
2714  int* nfixedvars, /**< pointer to store the number of fixed variables */
2715  int* nchgbds, /**< pointer to store the number changed variable bounds */
2716  int* ndelconss, /**< pointer to store the number of deleted constraints */
2717  SCIP_Bool* cutoff /**< pointer to store if a cutoff (infeasibility) was detected */
2718  )
2719 {
2720  SCIP_CONSDATA* consdata;
2721  SCIP_VAR** binvars;
2722  SCIP_VAR** vars;
2723  SCIP_Bool auxiliary;
2724  int* durations;
2725  int* demands;
2726  int nfixedones;
2727  int nfixedzeros;
2728  int v;
2729 
2730  assert(cutoff != NULL);
2731  assert(*cutoff == FALSE);
2732 
2733  consdata = SCIPconsGetData(cons);
2734  assert(consdata != NULL);
2735  assert(consdata->nvars > 1);
2736 
2737  /* (debug) check if the counter of the constraint are correct */
2738  checkCounters(consdata);
2739 
2740  if( consdata->propagated && (consdata->nfixedones + consdata->nfixedzeros < consdata->nvars || consdata->triedsolving) )
2741  return SCIP_OKAY;
2742 
2743  SCIP_CALL( SCIPallocBufferArray(scip, &vars, consdata->nvars) );
2744  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, consdata->nvars) );
2745  SCIP_CALL( SCIPallocBufferArray(scip, &demands, consdata->nvars) );
2746  SCIP_CALL( SCIPallocBufferArray(scip, &durations, consdata->nvars) );
2747 
2748  /* collect all activities which are locally assigned to that machine */
2749  collectActivities(consdata, binvars, vars, durations, demands, &nfixedones, &nfixedzeros, &auxiliary);
2750 
2751  /* if more than one variable is assigned to that machine propagate the cumulative condition */
2752  if( !consdata->propagated && nfixedones > 1 )
2753  {
2754  SCIP_Bool* explanation;
2755  SCIP_Bool initialized;
2756 
2757  initialized = FALSE;
2758 
2759  SCIP_CALL( SCIPallocBufferArray(scip, &explanation, nfixedones) );
2760  BMSclearMemoryArray(explanation, nfixedones);
2761 
2762  /* propagate cumulative condition */
2764  durations, demands, consdata->capacity, consdata->hmin, consdata->hmax, cons, nchgbds, &initialized, explanation, cutoff) );
2765 
2766  /* in case of a conflict we have to extend the initial reason before the conflict analysis starts */
2767  if( initialized && conflictanalysis )
2768  {
2769  assert(*cutoff == TRUE);
2770 
2771  for( v = 0; v < nfixedones; ++v )
2772  {
2773  if( explanation[v] )
2774  {
2775  SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[v]) );
2776  }
2777  }
2778 
2779  /* perform conflict analysis */
2780  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
2781  }
2782 
2783  SCIPfreeBufferArray(scip, &explanation);
2784  }
2785  assert(consdata->nvars > 1);
2786 
2787  /* if we are still feasible we can try to perform dual reductions; Note that we have to avoid dual reductions during
2788  * probing since these dual reductions can lead to wrong implications; the same hold in case of repropagating
2789  */
2790  if( !(*cutoff) && !SCIPinProbing(scip) && !SCIPinRepropagation(scip) )
2791  {
2792  if( nfixedzeros + nfixedones == consdata->nvars )
2793  {
2794  /* all binary variables are fixed */
2795 
2796  if( auxiliary )
2797  {
2798  /* we have an independent subproblems since all binary variables are fixed and the integer start time
2799  * variables belonging to the binary variables which are fixed to one are only locked by this constraint
2800  */
2801  SCIP_CALL( solveSubproblem(scip, cons, conflictanalysis, consdata, binvars, vars, durations, demands,
2802  nfixedones, nfixedvars, nchgbds, ndelconss, cutoff) );
2803  }
2804  }
2805  else if( !consdata->propagated && nfixedones < consdata->nvars )
2806  {
2807  SCIP_PROFILE* profile;
2808  int hmin;
2809  int est;
2810  int lct;
2811  int pos;
2812 
2813  /* create empty resource profile with infinity resource capacity */
2814  SCIP_CALL( SCIPprofileCreate(&profile, INT_MAX) );
2815 
2816  /* create worst case resource profile */
2817  SCIP_CALL( SCIPcreateWorstCaseProfile(scip, profile, nfixedones, vars, durations, demands) );
2818 
2819  hmin = SCIPcomputeHmin(scip, profile, consdata->capacity);
2820 
2821  if( hmin < INT_MAX )
2822  {
2823  /* check if the not selected variables can be discard from the machine */
2824  for( v = 0; v < consdata->nvars && !(*cutoff) && !SCIPisStopped(scip) ; ++v )
2825  {
2826  SCIP_VAR* binvar;
2827  SCIP_VAR* var;
2828 
2829  binvar = consdata->binvars[v];
2830  assert(binvar != NULL);
2831 
2832  var = consdata->vars[v];
2833  assert(var != NULL);
2834 
2835  /* check if the binary choice variable is not fixed yet */
2836  if( SCIPvarGetLbLocal(binvar) + 0.5 < SCIPvarGetUbLocal(binvar) )
2837  {
2838  SCIP_Real lb;
2839  SCIP_Real ub;
2840  SCIP_Bool infeasible;
2841 
2842  assert(SCIPvarGetLbLocal(binvar) < 0.5);
2843  assert(SCIPvarGetUbLocal(binvar) > 0.5);
2844 
2845  est = convertBoundToInt(scip, SCIPvarGetLbLocal(var));
2846  lct = convertBoundToInt(scip, SCIPvarGetUbLocal(var)) + consdata->durations[v];
2847 
2848  SCIP_CALL( SCIPprofileInsertCore(profile, est, lct, consdata->demands[v], &pos, &infeasible) );
2849  assert(!infeasible);
2850  assert(pos == -1);
2851 
2852  hmin = SCIPcomputeHmin(scip, profile, consdata->capacity);
2853 
2854  SCIP_CALL( SCIPprofileDeleteCore(profile, est, lct, consdata->demands[v]) );
2855 
2856  if( hmin == INT_MAX )
2857  continue;
2858 
2859  /* start probing mode */
2860  SCIPdebugMessage("start probing\n");
2861  SCIP_CALL( SCIPstartProbing(scip) );
2862 
2863  SCIP_CALL( SCIPnewProbingNode(scip) );
2864 
2865  SCIPdebugMessage(" fix variables <%s>[%g,%g] to 1.0\n",
2866  SCIPvarGetName(binvar), SCIPvarGetLbLocal(binvar), SCIPvarGetUbLocal(binvar));
2867 
2868  SCIP_CALL( SCIPfixVarProbing(scip, binvar, 1.0) );
2869 
2870  SCIPdebugMessage(" run propagation\n");
2871  SCIP_CALL( SCIPpropagateProbing(scip, 0, &infeasible, NULL) );
2872 
2873  lb = SCIPvarGetLbLocal(var);
2874  ub = SCIPvarGetUbLocal(var);
2875 
2876  /* end probing mode */
2877  SCIP_CALL( SCIPendProbing(scip) );
2878  SCIPdebugMessage("end probing\n");
2879 
2880  if( infeasible )
2881  {
2882  SCIP_Bool tightened;
2883 
2884  /* propagation detected infeasibility, therefore, job cannot be processed by that machine */
2885  SCIPdebugMessage(" probing detect infeasibility\n");
2886  SCIPdebugMessage(" fix variable <%s> to 0.0\n", SCIPvarGetName(binvar));
2887 
2888  /* since this bound change is dual reduction we have to avoid that this bound change is analyzed
2889  * during the conflict analysis; otherwise all optimal solution might be removed: therefore, we
2890  * SCIPtightenVarUb instead of SCIPinferBinvarCons()
2891  */
2892  SCIP_CALL( SCIPtightenVarUb(scip, binvar, 0.0, FALSE, &infeasible, &tightened) );
2893  if( infeasible )
2894  (*cutoff) = TRUE;
2895  else if( tightened )
2896  {
2897  (*nchgbds)++;
2898 
2899  /* fix integer start time variable if possible (before calling that method we have to leave the
2900  * probing mode)
2901  */
2902  if( SCIPconsIsChecked(cons) )
2903  {
2904  SCIP_CALL( fixIntegerVariable(scip, var, consdata->downlocks[v], consdata->uplocks[v], nchgbds) );
2905  }
2906  }
2907  }
2908  else
2909  {
2910  SCIP_Bool tightened;
2911 
2912  /* probing was feasible, therefore, we can adjust the bounds of the start time variable for that job */
2913  SCIPdebugMessage(" probing stayed feasible\n");
2914 
2915  assert(SCIPvarGetNLocksUp(var) >= (int)consdata->uplocks[v]);
2916  if( SCIPvarGetNLocksUp(var) == (int)consdata->uplocks[v] )
2917  {
2918  SCIPdebugMessage(" variable <%s> change lower bound from <%g> to <%g>\n", SCIPvarGetName(var), SCIPvarGetLbLocal(var), lb);
2919 
2920  /* for this bound change there is no inference information needed since no other constraint can
2921  * use this bound change to reason something
2922  */
2923  SCIP_CALL( SCIPtightenVarLb(scip, var, lb, FALSE, &infeasible, &tightened) );
2924  assert(!infeasible);
2925 
2926  if( tightened )
2927  (*nchgbds)++;
2928  }
2929 
2930  assert(SCIPvarGetNLocksDown(var) >= (int)consdata->downlocks[v]);
2931  if( SCIPvarGetNLocksDown(var) == (int)consdata->downlocks[v] )
2932  {
2933  SCIPdebugMessage(" variable <%s> change upper bound from <%g> to <%g>\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var), ub);
2934 
2935  /* for this boound change there is no inference information needed since no other constraint can
2936  * use this bound change to reason something
2937  */
2938  SCIP_CALL( SCIPtightenVarUb(scip, var, ub, FALSE, &infeasible, &tightened) );
2939  assert(!infeasible);
2940 
2941  if( tightened )
2942  (*nchgbds)++;
2943  }
2944  }
2945  }
2946  else if( SCIPvarGetUbLocal(binvar) < 0.5 && SCIPconsIsChecked(cons) )
2947  {
2948  /* if the binary choice variable is fixed to zero we can try to perform a dual reductions */
2949  SCIP_CALL( fixIntegerVariable(scip, var, consdata->downlocks[v], consdata->uplocks[v], nchgbds) );
2950  }
2951  }
2952  }
2953 
2954  /* free worst case profile */
2955  SCIPprofileFree(&profile);
2956  }
2957  }
2958 
2959  /* mark constraint to be propagated */
2960  if( !SCIPinProbing(scip) )
2961  consdata->propagated = TRUE;
2962 
2963  /* free all buffers */
2964  SCIPfreeBufferArray(scip, &durations);
2965  SCIPfreeBufferArray(scip, &demands);
2966  SCIPfreeBufferArray(scip, &binvars);
2967  SCIPfreeBufferArray(scip, &vars);
2968 
2969  return SCIP_OKAY;
2970 }
2971 
2972 
2973 /*
2974  * Callback methods of constraint handler
2975  */
2976 
2977 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
2978 static
2979 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOptcumulative)
2980 { /*lint --e{715}*/
2981  assert(scip != NULL);
2982  assert(conshdlr != NULL);
2983  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2984 
2985  /* call inclusion method of constraint handler */
2987 
2988  *valid = TRUE;
2989 
2990  return SCIP_OKAY;
2991 }
2992 
2993 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
2994 static
2995 SCIP_DECL_CONSFREE(consFreeOptcumulative)
2996 { /*lint --e{715}*/
2997  SCIP_CONSHDLRDATA* conshdlrdata;
2998 
2999  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3000  assert(conshdlrdata != NULL);
3001 
3002  SCIP_CALL( conshdlrdataFree(scip, &conshdlrdata) );
3003 
3004  SCIPconshdlrSetData(conshdlr, NULL);
3005 
3006  return SCIP_OKAY;
3007 }
3008 
3009 
3010 /** initialization method of constraint handler (called after problem was transformed) */
3011 #define consInitOptcumulative NULL
3013 
3014 /** deinitialization method of constraint handler (called before transformed problem is freed) */
3015 #define consExitOptcumulative NULL
3017 
3018 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
3019 static
3020 SCIP_DECL_CONSINITPRE(consInitpreOptcumulative)
3021 { /*lint --e{715}*/
3022  SCIP_CONSHDLRDATA* conshdlrdata;
3023  int c;
3024 
3025  assert( scip != NULL );
3026  assert( conshdlr != NULL );
3027  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3028 
3029  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3030  assert(conshdlrdata != NULL);
3031 
3032  for( c = 0; c < nconss; ++c )
3033  {
3034  /* remove jobs which have a duration or demand of zero (zero energy) or lay outside the effective horizon [hmin,
3035  * hmax)
3036  */
3037  SCIP_CALL( removeIrrelevantJobs(scip, conss[c]) );
3038  }
3039 
3040  /* find trysol heuristic */
3041  if( conshdlrdata->heurtrysol == NULL )
3042  {
3043  conshdlrdata->heurtrysol = SCIPfindHeur(scip, "trysol");
3044  }
3045 
3046  return SCIP_OKAY;
3047 }
3048 
3049 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
3050 #define consExitpreOptcumulative NULL
3052 
3053 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
3054 #define consInitsolOptcumulative NULL
3056 /** constraint enforcing method of constraint handler for relaxation solutions */
3057 #define consEnforelaxOptcomulative NULL
3059 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
3060 static
3061 SCIP_DECL_CONSEXITSOL(consExitsolOptcumulative)
3062 { /*lint --e{715}*/
3063  int c;
3064 
3065  assert(scip != NULL);
3066 
3067  /* release the rows of all constraints */
3068  for( c = 0; c < nconss; ++c )
3069  {
3070  SCIP_CONSDATA* consdata;
3071 
3072  consdata = SCIPconsGetData(conss[c]);
3073  assert(consdata != NULL);
3074 
3075  if( consdata->row != NULL )
3076  {
3077  SCIP_CALL( SCIPreleaseRow(scip, &consdata->row) );
3078  }
3079  }
3080 
3081  return SCIP_OKAY;
3082 }
3083 
3084 
3085 /** frees specific constraint data */
3086 static
3087 SCIP_DECL_CONSDELETE(consDeleteOptcumulative)
3088 { /*lint --e{715}*/
3089  SCIP_CONSHDLRDATA* conshdlrdata;
3090 
3091  assert(conshdlr != NULL);
3092  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3093  assert(consdata != NULL );
3094  assert(*consdata != NULL );
3095 
3096  /* get event handler */
3097  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3098  assert(conshdlrdata != NULL);
3099  assert(conshdlrdata->eventhdlrbinvars != NULL);
3100  assert(conshdlrdata->eventhdlrintvars != NULL);
3101 
3102  /* if constraint belongs to transformed problem space, drop bound change events on variables */
3103  if( (*consdata)->nvars > 0 && SCIPvarIsTransformed((*consdata)->vars[0]) )
3104  {
3105  SCIP_CALL( dropAllEvents(scip, cons, conshdlrdata->eventhdlrbinvars, conshdlrdata->eventhdlrintvars) );
3106  }
3107 
3108  /* free optcumulative constraint data */
3109  SCIP_CALL( consdataFree(scip, consdata) );
3110 
3111  return SCIP_OKAY;
3112 }
3113 
3114 /** transforms constraint data into data belonging to the transformed problem */
3115 static
3116 SCIP_DECL_CONSTRANS(consTransOptcumulative)
3117 { /*lint --e{715}*/
3118  SCIP_CONSHDLRDATA* conshdlrdata;
3119  SCIP_CONSDATA* sourcedata;
3120  SCIP_CONSDATA* targetdata;
3121 
3122  assert(conshdlr != NULL);
3123  assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
3124  assert(sourcecons != NULL);
3125  assert(targetcons != NULL);
3126 
3127  /* get event handler */
3128  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3129  assert(conshdlrdata != NULL);
3130  assert(conshdlrdata->eventhdlrbinvars != NULL);
3131  assert(conshdlrdata->eventhdlrintvars != NULL);
3132 
3133  sourcedata = SCIPconsGetData(sourcecons);
3134  assert(sourcedata != NULL);
3135  assert(sourcedata->row == NULL);
3136 
3137  SCIPdebugMessage("transform optcumulative constraint <%s>\n", SCIPconsGetName(sourcecons));
3138 
3139  /* create constraint data for target constraint */
3140  SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->nvars, sourcedata->vars, sourcedata->binvars,
3141  sourcedata->durations, sourcedata->demands, sourcedata->capacity, SCIPconsIsChecked(sourcecons)) );
3142 
3143  /* create target constraint */
3144  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
3145  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
3146  SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
3147  SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
3148  SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
3149 
3150  assert(targetdata->nglbfixedones == 0);
3151  assert(targetdata->nglbfixedzeros == 0);
3152  assert(targetdata->nfixedones == 0);
3153  assert(targetdata->nfixedzeros == 0);
3154 
3155  /* catch bound change events of variables */
3156  SCIP_CALL( catchAllEvents(scip, *targetcons, conshdlrdata->eventhdlrbinvars, conshdlrdata->eventhdlrintvars) );
3157 
3158  return SCIP_OKAY;
3159 }
3160 
3161 
3162 /** LP initialization method of constraint handler */
3163 static
3164 SCIP_DECL_CONSINITLP(consInitlpOptcumulative)
3165 { /*lint --e{715}*/
3166  SCIP_CONSHDLRDATA* conshdlrdata;
3167  SCIP_Bool rowadded;
3168  SCIP_Bool consadded;
3169  SCIP_Bool cutoff;
3170  int c;
3171 
3172  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3173  assert(conshdlrdata != NULL);
3174 
3175  rowadded = FALSE;
3176  consadded = FALSE;
3177 
3178  for( c = 0; c < nconss; ++c )
3179  {
3180  assert(SCIPconsIsInitial(conss[c]));
3181  SCIP_CALL( addRelaxation(scip, conshdlr, conshdlrdata, conss[c], &rowadded, &consadded, &cutoff) );
3182  /* ignore cutoff value */
3183  }
3184 
3185  return SCIP_OKAY;
3186 }
3187 
3188 
3189 /** separation method of constraint handler for LP solutions */
3190 static
3191 SCIP_DECL_CONSSEPALP(consSepalpOptcumulative)
3193  SCIP_CONSHDLRDATA* conshdlrdata;
3194  SCIP_Bool rowadded;
3195  SCIP_Bool consadded;
3196  SCIP_Bool cutoff;
3197  int c;
3198 
3199  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3200  assert(conshdlrdata != NULL);
3201 
3202  rowadded = FALSE;
3203  consadded = FALSE;
3204  cutoff = FALSE;
3205 
3206  for( c = 0; c < nconss && ! cutoff; ++c )
3207  {
3208  SCIP_CALL( addRelaxation(scip, conshdlr, conshdlrdata, conss[c], &rowadded, &consadded, &cutoff) );
3209  }
3210 
3211  if ( cutoff )
3212  *result = SCIP_CUTOFF;
3213  else if( consadded )
3214  *result = SCIP_CONSADDED;
3215  else if( rowadded )
3216  *result = SCIP_SEPARATED;
3217  else
3218  *result = SCIP_DIDNOTFIND;
3219 
3220  return SCIP_OKAY;
3221 }/*lint !e715*/
3222 
3223 
3224 /** separation method of constraint handler for arbitrary primal solutions */
3225 #define consSepasolOptcumulative NULL
3227 
3228 /** constraint enforcing method of constraint handler for LP solutions */
3229 static
3230 SCIP_DECL_CONSENFOLP(consEnfolpOptcumulative)
3231 { /*lint --e{715}*/
3232  SCIP_CONSHDLRDATA* conshdlrdata;
3233  SCIP_SOL* trysol;
3234  SCIP_Bool violated;
3235  SCIP_Bool consviolated;
3236  SCIP_Bool consadded;
3237  SCIP_Bool solfeasible;
3238  int c;
3239 
3240  SCIPdebugMessage("method: enforce LP solution (nconss %d)\n", nconss);
3241 
3242  assert(conshdlr != NULL);
3243  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3244  assert(nconss == 0 || conss != NULL);
3245  assert(result != NULL);
3246 
3247  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3248  assert(conshdlrdata != NULL);
3249 
3250  violated = FALSE;
3251  consviolated = FALSE;
3252  consadded = FALSE;
3253  solfeasible = TRUE;
3254  trysol = NULL;
3255 
3256  /* create pseudo solution */
3257  if( conshdlrdata->heurtrysol != NULL )
3258  {
3259  SCIP_CALL( SCIPcreateCurrentSol(scip, &trysol, NULL) );
3260  }
3261 
3262  /* check all constraints even if one is dectected be violated */
3263  for( c = 0; c < nconss && (!violated || solfeasible); ++c )
3264  {
3265  SCIP_CALL( enfopsCons(scip, conss[c], trysol, &consviolated, &consadded, &solfeasible) );
3266  violated = violated || consviolated;
3267  }
3268 
3269  /* add a potentially feasible solution was constructed we pass it to the heuristic try sol */
3270  if( solfeasible && violated && trysol != NULL )
3271  {
3272 #ifdef SCIP_DEBUG
3273  FILE* file;
3274  file = fopen("build.sol", "w");
3275 
3276  if( file != NULL )
3277  {
3278  SCIP_CALL( SCIPprintSol(scip, trysol, file, FALSE) );
3279  fclose(file);
3280  }
3281 #endif
3282 
3283  SCIP_CALL( SCIPheurPassSolTrySol(scip, conshdlrdata->heurtrysol, trysol) );
3284  }
3285 
3286  SCIP_CALL( SCIPfreeSol(scip, &trysol) );
3287 
3288  if( consadded )
3289  *result = SCIP_CONSADDED;
3290  else if( violated )
3291  *result = SCIP_INFEASIBLE;
3292  else
3293  *result = SCIP_FEASIBLE;
3294 
3295  return SCIP_OKAY;
3296 }
3297 
3298 
3299 /** constraint enforcing method of constraint handler for pseudo solutions */
3300 static
3301 SCIP_DECL_CONSENFOPS(consEnfopsOptcumulative)
3302 { /*lint --e{715}*/
3303  SCIP_CONSHDLRDATA* conshdlrdata;
3304  SCIP_SOL* trysol;
3305  SCIP_Bool violated;
3306  SCIP_Bool consadded;
3307  SCIP_Bool solfeasible;
3308  int c;
3309 
3310  SCIPdebugMessage("method: enforce pseudo solution\n");
3311 
3312  assert(conshdlr != NULL);
3313  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3314  assert(nconss == 0 || conss != NULL);
3315  assert(result != NULL);
3316 
3317  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3318  assert(conshdlrdata != NULL);
3319 
3320  violated = FALSE;
3321  consadded = FALSE;
3322  solfeasible = TRUE;
3323  trysol = NULL;
3324 
3325  /* create pseudo solution */
3326  if( conshdlrdata->heurtrysol != NULL )
3327  {
3328  SCIP_CALL( SCIPcreateCurrentSol(scip, &trysol, NULL) );
3329  }
3330 
3331  for( c = 0; c < nconss && !violated; ++c )
3332  {
3333  SCIP_CALL( enfopsCons(scip, conss[c], trysol, &violated, &consadded, &solfeasible) );
3334  }
3335 
3336  /* add a potentially feasible solution was constructed we pass it to the heuristic try sol */
3337  if( solfeasible && violated && trysol != NULL )
3338  {
3339  SCIP_CALL( SCIPheurPassSolTrySol(scip, conshdlrdata->heurtrysol, trysol) );
3340  }
3341 
3342  SCIP_CALL( SCIPfreeSol(scip, &trysol) );
3343 
3344  if( consadded )
3345  *result = SCIP_CONSADDED;
3346  else if( violated )
3347  *result = SCIP_INFEASIBLE;
3348  else
3349  *result = SCIP_FEASIBLE;
3350 
3351  return SCIP_OKAY;
3352 }
3353 
3354 
3355 /** feasibility check method of constraint handler for integral solutions */
3356 static
3357 SCIP_DECL_CONSCHECK(consCheckOptcumulative)
3358 { /*lint --e{715}*/
3359  SCIP_Bool violated;
3360  int c;
3361 
3362  assert(conshdlr != NULL);
3363  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3364  assert(nconss == 0 || conss != NULL);
3365  assert(result != NULL);
3366 
3367  violated = FALSE;
3368 
3369  for( c = 0; c < nconss && !violated; ++c )
3370  {
3371  SCIP_CALL( checkCons(scip, conss[c], sol, &violated, printreason) );
3372  }
3373 
3374  if( violated )
3375  *result = SCIP_INFEASIBLE;
3376  else
3377  *result = SCIP_FEASIBLE;
3378 
3379  return SCIP_OKAY;
3380 }
3381 
3382 
3383 /** domain propagation method of constraint handler */
3384 static
3385 SCIP_DECL_CONSPROP(consPropOptcumulative)
3386 { /*lint --e{715}*/
3387  SCIP_CONSHDLRDATA* conshdlrdata;
3388  SCIP_CONS* cons;
3389  SCIP_Bool cutoff;
3390  int nfixedvars;
3391  int nupgdconss;
3392  int ndelconss;
3393  int nchgcoefs;
3394  int nchgbds;
3395  int c;
3396 
3397  assert(scip != NULL);
3398  assert(nconss > 0);
3399 
3400  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3401  assert(conshdlrdata != NULL);
3402 
3403  nfixedvars = 0;
3404  nupgdconss = 0;
3405  ndelconss = 0;
3406  nchgcoefs = 0;
3407  nchgbds = 0;
3408  cutoff = FALSE;
3409 
3410  SCIPdebugMessage("propagate %d optcumulative constraints (probing: %u)\n", nusefulconss, SCIPinProbing(scip));
3411 
3412  /* first propagate only the useful constraints */
3413  for( c = 0; c < nusefulconss && !cutoff; ++c )
3414  {
3415  SCIP_Bool mustpropagate;
3416  int oldnchgcoefs;
3417  int oldnchgbds;
3418 
3419  cons = conss[c];
3420  mustpropagate = TRUE;
3421  oldnchgcoefs = nchgcoefs;
3422  oldnchgbds = nchgbds;
3423 
3424  /* it might be that the constraint is already deleted which can be case if SCIP is in probing mode */
3425  if( SCIPconsIsDeleted(cons) )
3426  {
3427  assert(SCIPinProbing(scip));
3428  continue;
3429  }
3430 
3431  /* try to upgrade optcumulative to cumulative constraint which is possible if all remaining binary variables are
3432  * fixed to one; in case the constraint has no variable left it is removed
3433  */
3434  if( !SCIPinProbing(scip) )
3435  {
3436  SCIP_Bool redundant;
3437 
3438  /* remove all jobs for which the binary variable is globally fixed to zero */
3439  SCIP_CALL( applyZeroFixings(scip, cons, &nchgcoefs, &nchgbds) );
3440 
3441  SCIP_CALL( checkRedundancy(scip, cons, &ndelconss, &redundant) );
3442 
3443  if( redundant )
3444  continue;
3445 
3446  SCIP_CALL( upgradeCons(scip, cons, &ndelconss, &nupgdconss, &mustpropagate) );
3447  }
3448 
3449  if( mustpropagate )
3450  {
3451  SCIP_CALL( propagateCons(scip, cons, conshdlrdata->conflictanalysis, &nfixedvars, &nchgbds, &ndelconss, &cutoff) );
3452  }
3453 
3454  /* update the age of the constraint w.r.t. success of the propagation rule */
3455  if( oldnchgbds < nchgbds || oldnchgcoefs < nchgcoefs )
3456  {
3457  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3458  }
3459  else
3460  {
3461  SCIP_CALL( SCIPincConsAge(scip, cons) );
3462  }
3463  }
3464 
3465  if( cutoff )
3466  {
3467  SCIPdebugMessage("propagation detected a cutoff\n");
3468  *result = SCIP_CUTOFF;
3469  }
3470  else if( nfixedvars > 0 || nchgbds > 0 || nupgdconss > 0 )
3471  {
3472  SCIPdebugMessage("propagation detected %d bound changes\n", nchgbds);
3473  *result = SCIP_REDUCEDDOM;
3474  }
3475  else
3476  *result = SCIP_DIDNOTFIND;
3477 
3478  return SCIP_OKAY;
3479 }
3480 
3481 
3482 /** presolving method of constraint handler */
3483 static
3484 SCIP_DECL_CONSPRESOL(consPresolOptcumulative)
3485 { /*lint --e{715}*/
3486  SCIP_CONS* cons;
3487  SCIP_Bool cutoff;
3488  SCIP_Bool mustpropagate;
3489  int oldnchgbds;
3490  int oldndelconss;
3491  int oldnupgdconss;
3492  int oldnfixedvars;
3493  int c;
3494 
3495  assert(scip != NULL);
3496  assert(nconss > 0);
3497  assert(!SCIPinProbing(scip));
3498 
3499  oldnchgbds = *nchgbds;
3500  oldndelconss = *ndelconss;
3501  oldnupgdconss = *nupgdconss;
3502  oldnfixedvars = *nfixedvars;
3503  cutoff = FALSE;
3504 
3505  SCIPdebugMessage("presolve %d optcumulative constraints\n", nconss);
3506 
3507  for( c = 0; c < nconss && !cutoff; ++c )
3508  {
3509  SCIP_CONSDATA* consdata;
3510 
3511  cons = conss[c];
3512  mustpropagate = TRUE;
3513 
3514  /* remove all jobs for which the binary variable is globally fixed to zero */
3515  SCIP_CALL( applyZeroFixings(scip, cons, nchgcoefs, nchgbds) );
3516 
3517  /* try to upgrade optcumulative to cumulative constraint which is possible if all remaining binary variables are
3518  * fixed to one; in case the constraint has no or one variable left it is removed
3519  */
3520  SCIP_CALL( upgradeCons(scip, cons, ndelconss, nupgdconss, &mustpropagate) );
3521 
3522  if( mustpropagate )
3523  {
3524  int nvars;
3525  int hmin;
3526  int hmax;
3527  int split;
3528 
3529  consdata = SCIPconsGetData(cons);
3530  assert(consdata != NULL);
3531 
3532  nvars = consdata->nvars;
3533  assert(nvars > 1);
3534 
3535  if( !consdata->normalized )
3536  {
3537  /* divide demands and capacity by their greatest common divisor */
3538  SCIP_CALL( SCIPnormalizeCumulativeCondition(scip, nvars, consdata->vars, consdata->durations,
3539  consdata->demands, &consdata->capacity, nchgcoefs, nchgsides) );
3540  consdata->normalized = TRUE;
3541  }
3542 
3543  /* propagate the constaint */
3544  SCIP_CALL( propagateCons(scip, cons, FALSE, nfixedvars, nchgbds, ndelconss, &cutoff) );
3545 
3546  /* if a cutoff was detected we are done */
3547  if( cutoff )
3548  break;
3549 
3550  /* check if the optimal cumulative constraint can be decomposed */
3551  SCIP_CALL( SCIPsplitCumulativeCondition(scip, nvars, consdata->vars, consdata->durations,
3552  consdata->demands, consdata->capacity, &hmin, &hmax, &split) );
3553 
3554  /* check if this time point improves the effective horizon */
3555  if( consdata->hmin < hmin )
3556  {
3557  SCIPdebugMessage("cumulative constraint <%s> adjust hmin <%d> -> <%d>\n", SCIPconsGetName(cons), consdata->hmin, hmin);
3558 
3559  consdata->hmin = hmin;
3560  (*nchgsides)++;
3561  }
3562 
3563  /* check if this time point improves the effective horizon */
3564  if( consdata->hmax > hmax )
3565  {
3566  SCIPdebugMessage("cumulative constraint <%s> adjust hmax <%d> -> <%d>\n", SCIPconsGetName(cons), consdata->hmax, hmax);
3567  consdata->hmax = hmax;
3568  (*nchgsides)++;
3569  }
3570 
3571  /* check if the constraint is redundant */
3572  if( consdata->hmax <= consdata->hmin )
3573  {
3574  SCIPdebugMessage("constraint <%s> is redundant since hmax(%d) <= hmin(%d)\n",
3575  SCIPconsGetName(cons), consdata->hmax, consdata->hmin);
3576 
3577  SCIP_CALL( SCIPdelCons(scip, cons) );
3578  (*ndelconss)++;
3579 
3580  continue;
3581  }
3582 
3583  /* check if the cumulative constraint can be decomposed */
3584  if( consdata->hmin < split && split < consdata->hmax )
3585  {
3586  SCIP_CONS* splitcons;
3587  SCIP_CONSDATA* splitconsdata;
3588  char name[SCIP_MAXSTRLEN];
3589 
3590  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "(%s)'", SCIPconsGetName(cons));
3591 
3592  SCIPdebugMessage("split optcumulative constraint <%s>[%d,%d) with %d jobs at time point %d\n",
3593  SCIPconsGetName(cons), consdata->hmin, consdata->hmax, nvars, split);
3594 
3595  SCIP_CALL( SCIPcreateConsOptcumulative(scip, &splitcons, name, nvars, consdata->vars, consdata->binvars,
3596  consdata->durations, consdata->demands, consdata->capacity,
3599 
3600  splitconsdata = SCIPconsGetData(splitcons);
3601  assert(splitconsdata != NULL);
3602 
3603  /* adjust the effective time horizon of the new constraint */
3604  splitconsdata->hmin = split;
3605  splitconsdata->hmax = consdata->hmax;
3606 
3607  assert(split < consdata->hmax);
3608 
3609  /* add and release new cumulative constraint */
3610  SCIP_CALL( SCIPaddCons(scip, splitcons) );
3611  SCIP_CALL( SCIPreleaseCons(scip, &splitcons) );
3612 
3613  /* adjust the effective time horizon of the constraint */
3614  consdata->hmax = split;
3615 
3616  assert(consdata->hmin < consdata->hmax);
3617 
3618  (*naddconss)++;
3619  }
3620 
3621  /* presolve cumulative condition w.r.t. effective horizon by detecting irrelevant variables */
3622  SCIP_CALL( presolveCumulativeCondition(scip, cons, nfixedvars, nchgcoefs, nchgsides, &cutoff) );
3623 
3624  /* detect implications */
3625  SCIP_CALL( detectImplications(scip, cons, nchgcoefs, naddconss) );
3626 
3627  /* try to upgrade optcumulative to cumulative constraint which is possible if all remaining binary variables
3628  * are fixed to one; in case the constraint has no variable left it is removed
3629  */
3630  assert(!SCIPinProbing(scip));
3631  SCIP_CALL( upgradeCons(scip, cons, ndelconss, nupgdconss, &mustpropagate) );
3632  }
3633  }
3634 
3635  if( cutoff )
3636  {
3637  SCIPdebugMessage("presolving detected a cutoff\n");
3638  *result = SCIP_CUTOFF;
3639  }
3640  else if( oldnfixedvars < *nfixedvars || oldnchgbds < *nchgbds || oldnupgdconss < *nupgdconss || oldndelconss < *ndelconss )
3641  {
3642  SCIPdebugMessage("presolving detected %d bound changes\n", *nchgbds - oldnchgbds);
3643  *result = SCIP_SUCCESS;
3644  }
3645  else
3646  *result = SCIP_DIDNOTFIND;
3647 
3648  return SCIP_OKAY;
3649 }
3650 
3651 
3652 /** propagation conflict resolving method of constraint handler */
3653 static
3654 SCIP_DECL_CONSRESPROP(consRespropOptcumulative)
3655 { /*lint --e{715}*/
3656  SCIP_CONSHDLRDATA* conshdlrdata;
3657  SCIP_CONSDATA* consdata;
3658  SCIP_VAR** vars;
3659  SCIP_VAR** binvars;
3660  int* durations;
3661  int* demands;
3662  SCIP_Bool choicevar;
3663  int nvars;
3664  int v;
3665 
3666  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3667  assert(conshdlrdata != NULL);
3668 
3669  /* check if the constraint handler wants to participate in the conflict analysis */
3670  if( !conshdlrdata->conflictanalysis )
3671  {
3672  *result = SCIP_DIDNOTFIND;
3673  return SCIP_OKAY;
3674  }
3675 
3676  SCIPdebugMessage("resolve propagate of optcumulative constraints <%s>\n", SCIPconsGetName(cons));
3677 
3678  consdata = SCIPconsGetData(cons);
3679  assert(consdata != NULL);
3680 
3681  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, consdata->nvars) );
3682  SCIP_CALL( SCIPallocBufferArray(scip, &vars, consdata->nvars) );
3683  SCIP_CALL( SCIPallocBufferArray(scip, &durations, consdata->nvars) );
3684  SCIP_CALL( SCIPallocBufferArray(scip, &demands, consdata->nvars) );
3685 
3686  nvars = 0;
3687  choicevar = FALSE;
3688 
3689  /* collect all activities which are were locally assigned to that machine before the bound change was made */
3690  for( v = 0; v < consdata->nvars; ++v )
3691  {
3692  if( SCIPvarGetLbAtIndex(consdata->binvars[v], bdchgidx, FALSE) > 0.5 )
3693  {
3694  vars[nvars] = consdata->vars[v];
3695  binvars[nvars] = consdata->binvars[v];
3696  durations[nvars] = consdata->durations[v];
3697  demands[nvars] = consdata->demands[v];
3698  nvars++;
3699  }
3700  else if( consdata->binvars[v] == infervar )
3701  choicevar = TRUE;
3702  }
3703 
3704  assert(nvars > 0);
3705 
3706  if( choicevar )
3707  {
3708  for( v = 0; v < consdata->nvars; ++v )
3709  {
3710  if( SCIPvarGetLbAtIndex(consdata->binvars[v], bdchgidx, FALSE) > 0.5 )
3711  {
3712  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->binvars[v]) );
3713 
3714  SCIP_CALL( SCIPaddConflictLb(scip, consdata->vars[v], bdchgidx) );
3715  SCIP_CALL( SCIPaddConflictUb(scip, consdata->vars[v], bdchgidx) );
3716  }
3717  else if( consdata->binvars[v] == infervar )
3718  {
3719  SCIP_CALL( SCIPaddConflictLb(scip, consdata->vars[v], bdchgidx) );
3720  SCIP_CALL( SCIPaddConflictUb(scip, consdata->vars[v], bdchgidx) );
3721  }
3722  }
3723 
3724  *result = SCIP_SUCCESS;
3725  }
3726  else
3727  {
3728  SCIP_Bool* explanation;
3729 
3730  SCIP_CALL( SCIPallocBufferArray(scip, &explanation, nvars) );
3731  BMSclearMemoryArray(explanation, nvars);
3732 
3733  /* resolve propagate of cumulative condition */
3734  SCIP_CALL( SCIPrespropCumulativeCondition(scip, nvars, vars, durations, demands, consdata->capacity, consdata->hmin, consdata->hmax,
3735  infervar, inferinfo, boundtype, bdchgidx, relaxedbd, explanation, result) );
3736 
3737  /* if the cumulative constraint handler successfully create an explanation for the propagate we extend this
3738  * explanation with the required choice variables
3739  */
3740  if( *result == SCIP_SUCCESS )
3741  {
3742  for( v = 0; v < nvars; ++v )
3743  {
3744  if( explanation[v] )
3745  {
3746  /* add the lower bounds of the choice variables as part of the initial reason */
3747  SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[v]) );
3748  }
3749  }
3750  }
3751 
3752  SCIPfreeBufferArray(scip, &explanation);
3753  }
3754 
3755  /* free all buffers */
3756  SCIPfreeBufferArray(scip, &demands);
3757  SCIPfreeBufferArray(scip, &durations);
3758  SCIPfreeBufferArray(scip, &vars);
3759  SCIPfreeBufferArray(scip, &binvars);
3760 
3761  return SCIP_OKAY;
3762 }
3763 
3764 /** variable rounding lock method of constraint handler */
3765 static
3766 SCIP_DECL_CONSLOCK(consLockOptcumulative)
3767 { /*lint --e{715}*/
3768  SCIP_CONSDATA* consdata;
3769  SCIP_VAR** vars;
3770  int v;
3771 
3772  assert(scip != NULL);
3773  assert(cons != NULL);
3774 
3775  consdata = SCIPconsGetData(cons);
3776  assert(consdata != NULL);
3777 
3778  vars = consdata->vars;
3779  assert(vars != NULL);
3780 
3781  for( v = 0; v < consdata->nvars; ++v )
3782  {
3783  assert(consdata->vars[v] != NULL);
3784  if( consdata->downlocks[v] && consdata->uplocks[v] )
3785  {
3786  /* the integer start variable should not get rounded in both direction */
3787  SCIP_CALL( SCIPaddVarLocksType(scip, vars[v], SCIP_LOCKTYPE_MODEL, nlockspos + nlocksneg, nlockspos + nlocksneg) );
3788  }
3789  else if( consdata->downlocks[v] )
3790  {
3791  SCIP_CALL( SCIPaddVarLocksType(scip, vars[v], SCIP_LOCKTYPE_MODEL, nlockspos, nlocksneg) );
3792  }
3793  else if( consdata->uplocks[v] )
3794  {
3795  SCIP_CALL( SCIPaddVarLocksType(scip, vars[v], SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos) );
3796  }
3797 
3798  /* the binary decision variable should not get rounded up; rounding down does not influence the feasibility */
3799  assert(consdata->binvars[v] != NULL);
3800  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->binvars[v], SCIP_LOCKTYPE_MODEL, nlocksneg, nlockspos) );
3801  }
3802 
3803  return SCIP_OKAY;
3804 }
3805 
3806 
3807 /** constraint activation notification method of constraint handler */
3808 #define consActiveOptcumulative NULL
3810 
3811 /** constraint deactivation notification method of constraint handler */
3812 #define consDeactiveOptcumulative NULL
3814 
3815 /** constraint enabling notification method of constraint handler */
3816 #define consEnableOptcumulative NULL
3818 
3819 /** constraint disabling notification method of constraint handler */
3820 #define consDisableOptcumulative NULL
3822 /** variable deletion method of constraint handler */
3823 #define consDelvarsOptcumulative NULL
3825 /** constraint display method of constraint handler */
3826 static
3827 SCIP_DECL_CONSPRINT(consPrintOptcumulative)
3828 { /*lint --e{715}*/
3829  assert(scip != NULL);
3830  assert(conshdlr != NULL);
3831  assert(cons != NULL);
3832 
3833  SCIP_CALL( consdataPrint(scip, SCIPconsGetData(cons), file) );
3834 
3835  return SCIP_OKAY;
3836 }
3837 
3838 /** constraint copying method of constraint handler */
3839 static
3840 SCIP_DECL_CONSCOPY(consCopyOptcumulative)
3841 { /*lint --e{715}*/
3842  SCIP_CONSDATA* sourceconsdata;
3843  SCIP_VAR** sourcebinvars;
3844  SCIP_VAR** sourcevars;
3845  SCIP_VAR** binvars;
3846  SCIP_VAR** vars;
3847  SCIP_Bool success;
3848  const char* consname;
3849 
3850  int nvars;
3851  int v;
3852 
3853  sourceconsdata = SCIPconsGetData(sourcecons);
3854  assert(sourceconsdata != NULL);
3855 
3856  /* get variables of the source constraint */
3857  sourcebinvars = sourceconsdata->binvars;
3858  sourcevars = sourceconsdata->vars;
3859  nvars = sourceconsdata->nvars;
3860 
3861  (*valid) = TRUE;
3862 
3863  if( nvars == 0 )
3864  return SCIP_OKAY;
3865 
3866  /* allocate buffer array */
3867  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, nvars) );
3868  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
3869 
3870  success = TRUE;
3871 
3872  for( v = 0; v < nvars && success; ++v )
3873  {
3874  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcebinvars[v], &binvars[v], varmap, consmap, global, &success) );
3875  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &vars[v], varmap, consmap, global, &success) );
3876  }
3877 
3878  if( success )
3879  {
3880  if( name != NULL )
3881  consname = name;
3882  else
3883  consname = SCIPconsGetName(sourcecons);
3884 
3885  /* copy the logic using the linear constraint copy method */
3886  SCIP_CALL( SCIPcreateConsOptcumulative(scip, cons, consname, nvars, vars, binvars,
3887  sourceconsdata->durations, sourceconsdata->demands, sourceconsdata->capacity,
3888  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3889 
3890  }
3891  else
3892  (*valid) = FALSE;
3893 
3894  /* free buffer array */
3895  SCIPfreeBufferArray(scip, &vars);
3896  SCIPfreeBufferArray(scip, &binvars);
3897 
3898  return SCIP_OKAY;
3899 }
3900 
3901 /** constraint parsing method of constraint handler */
3902 static
3903 SCIP_DECL_CONSPARSE(consParseOptcumulative)
3904 { /*lint --e{715}*/
3905  SCIP_VAR** vars;
3906  SCIP_VAR** binvars;
3907  SCIP_VAR* var;
3908  SCIP_VAR* binvar;
3909  SCIP_Real value;
3910  char strvalue[SCIP_MAXSTRLEN];
3911  char* endptr;
3912  int* demands;
3913  int* durations;
3914  int capacity;
3915  int duration;
3916  int demand;
3917  int hmin;
3918  int hmax;
3919  int varssize;
3920  int nvars;
3921 
3922  SCIPdebugMsg(scip, "parse <%s> as optcumulative constraint\n", str);
3923 
3924  /* cutoff "cumulative" form the constraint string */
3925  SCIPstrCopySection(str, 'o', '(', strvalue, SCIP_MAXSTRLEN, &endptr);
3926  str = endptr;
3927 
3928  varssize = 100;
3929  nvars = 0;
3930 
3931  /* allocate buffer array for variables */
3932  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
3933  SCIP_CALL( SCIPallocBufferArray(scip, &binvars, varssize) );
3934  SCIP_CALL( SCIPallocBufferArray(scip, &demands, varssize) );
3935  SCIP_CALL( SCIPallocBufferArray(scip, &durations, varssize) );
3936 
3937  do
3938  {
3939  SCIP_CALL( SCIPparseVarName(scip, str, &var, &endptr) );
3940 
3941  if( var != NULL )
3942  {
3943  str = endptr;
3944 
3945  SCIPstrCopySection(str, '(', ')', strvalue, SCIP_MAXSTRLEN, &endptr);
3946  duration = atoi(strvalue);
3947  str = endptr;
3948 
3949  SCIPstrCopySection(str, '[', ']', strvalue, SCIP_MAXSTRLEN, &endptr);
3950  demand = atoi(strvalue);
3951  str = endptr;
3952 
3953  SCIP_CALL( SCIPparseVarName(scip, str, &binvar, &endptr) );
3954  str = endptr;
3955 
3956  SCIPdebugMsg(scip, "parse job <%s><%s>, duration %d, demand %d\n", SCIPvarGetName(var), SCIPvarGetName(binvar), duration, demand);
3957 
3958  assert(nvars < varssize);
3959  vars[nvars] = var;
3960  binvars[nvars] = binvar;
3961  demands[nvars] = demand;
3962  durations[nvars] = duration;
3963  nvars++;
3964  }
3965  }
3966  while( var != NULL );
3967 
3968  /* parse effective time window */
3969  SCIPstrCopySection(str, '[', ',', strvalue, SCIP_MAXSTRLEN, &endptr);
3970  hmin = atoi(strvalue);
3971  str = endptr;
3972 
3973  if( SCIPstrToRealValue(str, &value, &endptr) )
3974  {
3975  hmax = (int)(value);
3976  str = endptr;
3977 
3978  /* parse capacity */
3979  SCIPstrCopySection(str, ')', '=', strvalue, SCIP_MAXSTRLEN, &endptr);
3980  str = endptr;
3981  if( SCIPstrToRealValue(str, &value, &endptr) )
3982  {
3983  capacity = (int)value;
3984 
3985  /* create cumulative constraint */
3986  SCIP_CALL( SCIPcreateConsOptcumulative(scip, cons, name, nvars, vars, binvars, durations, demands, capacity,
3987  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3988 
3989  (*success) = TRUE;
3990 
3991  SCIP_CALL( SCIPsetHminOptcumulative(scip, *cons, hmin) );
3992  SCIP_CALL( SCIPsetHmaxOptcumulative(scip, *cons, hmax) );
3993  }
3994  }
3995 
3996  /* free buffer arrays */
3997  SCIPfreeBufferArray(scip, &durations);
3998  SCIPfreeBufferArray(scip, &demands);
3999  SCIPfreeBufferArray(scip, &binvars);
4000  SCIPfreeBufferArray(scip, &vars);
4001 
4002  return SCIP_OKAY;
4003 }
4004 
4005 
4006 
4007 /*
4008  * Callback methods of event handler
4009  */
4010 
4011 static
4012 SCIP_DECL_EVENTEXEC(eventExecOptcumulativeBinvars)
4013 { /*lint --e{715}*/
4014  SCIP_CONSDATA* consdata;
4015  SCIP_EVENTTYPE eventtype;
4016 
4017  assert(eventhdlr != NULL);
4018  assert(eventdata != NULL);
4019  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_BINVARS_NAME) == 0);
4020  assert(event != NULL);
4021 
4022  /* collect event information */
4023  consdata = (SCIP_CONSDATA*)eventdata;
4024  eventtype = SCIPeventGetType(event);
4025 
4026  switch( eventtype )
4027  {
4029  consdata->nglbfixedones++;
4030  break;
4032  consdata->nglbfixedzeros++;
4033  break;
4035  consdata->nfixedones++;
4036  consdata->propagated = FALSE;
4037  break;
4039  consdata->nfixedzeros++;
4040  break;
4042  consdata->nfixedones--;
4043  consdata->triedsolving = FALSE;
4044  break;
4046  consdata->nfixedzeros--;
4047  consdata->triedsolving = FALSE;
4048 
4049  if( !SCIPinProbing(scip) )
4050  consdata->propagated = FALSE;
4051  break;
4052  default:
4053  SCIPerrorMessage("invalid event type %lx\n", eventtype);
4054  return SCIP_INVALIDDATA;
4055  }
4056 
4057  return SCIP_OKAY;
4058 }
4059 
4060 static
4061 SCIP_DECL_EVENTEXEC(eventExecOptcumulativeIntvars)
4062 { /*lint --e{715}*/
4063  SCIP_CONSDATA* consdata;
4064 
4065  assert(eventhdlr != NULL);
4066  assert(eventdata != NULL);
4067  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_INTVARS_NAME) == 0);
4068  assert(event != NULL);
4069 
4070  /* collect event information */
4071  consdata = (SCIP_CONSDATA*)eventdata;
4072  assert(consdata != NULL);
4073 
4074  /* a bound of a start time variable was tightened; therefore we mark to constraint to create a new local linear
4075  * relaxation
4076  */
4077  if( consdata->nfixedzeros + consdata->nfixedones < consdata->nvars )
4078  consdata->relaxadded = FALSE;
4079 
4080  if( !SCIPinProbing(scip) )
4081  consdata->propagated = FALSE;
4082 
4083  return SCIP_OKAY;
4084 }
4085 
4086 /*
4087  * constraint specific interface methods
4088  */
4089 
4090 /** creates the handler for optcumulative constraints and includes it in SCIP */
4092  SCIP* scip /**< SCIP data structure */
4093  )
4094 {
4095  SCIP_CONSHDLRDATA* conshdlrdata;
4096  SCIP_EVENTHDLR* eventhdlrbinvars;
4097  SCIP_EVENTHDLR* eventhdlrintvars;
4098 
4099  /* create event handler for bound change events */
4101  eventExecOptcumulativeBinvars, NULL) );
4102 
4103  /* create event handler for bound change events */
4105  eventExecOptcumulativeIntvars, NULL) );
4106 
4107  /* create constraint handler data */
4108  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlrbinvars, eventhdlrintvars) );
4109 
4110  /* include constraint handler */
4116  conshdlrCopyOptcumulative,
4117  consFreeOptcumulative, consInitOptcumulative, consExitOptcumulative,
4118  consInitpreOptcumulative, consExitpreOptcumulative, consInitsolOptcumulative, consExitsolOptcumulative,
4119  consDeleteOptcumulative, consTransOptcumulative, consInitlpOptcumulative,
4120  consSepalpOptcumulative, consSepasolOptcumulative, consEnfolpOptcumulative, consEnforelaxOptcomulative, consEnfopsOptcumulative, consCheckOptcumulative,
4121  consPropOptcumulative, consPresolOptcumulative, consRespropOptcumulative, consLockOptcumulative,
4124  consDelvarsOptcumulative, consPrintOptcumulative, consCopyOptcumulative, consParseOptcumulative,
4125  NULL, NULL, NULL,
4126  conshdlrdata) );
4127 
4128  /* add optcumulative constraint handler parameters */
4130  "constraints/"CONSHDLR_NAME"/rowrelax",
4131  "add linear relaxation as LP row (otherwise a knapsack constraint is created)?",
4132  &conshdlrdata->rowrelax, FALSE, DEFAULT_ROWRELAX, NULL, NULL) );
4133 
4135  "constraints/"CONSHDLR_NAME"/conflictanalysis",
4136  "participate in conflict analysis?",
4137  &conshdlrdata->conflictanalysis, FALSE, DEFAULT_CONFLICTANALYSIS, NULL, NULL) );
4138 
4140  "constraints/"CONSHDLR_NAME"/intervalrelax",
4141  "create a relaxation for each start and end time point interval",
4142  &conshdlrdata->intervalrelax, FALSE, DEFAULT_INTERVALRELAX, NULL, NULL) );
4143 
4144  return SCIP_OKAY;
4145 }
4146 
4147 /** creates and captures a optcumulative constraint */
4149  SCIP* scip, /**< SCIP data structure */
4150  SCIP_CONS** cons, /**< pointer to hold the created constraint */
4151  const char* name, /**< name of constraint */
4152  int nvars, /**< number of variables (jobs) */
4153  SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
4154  SCIP_VAR** binvars, /**< array of variable representing if the job has to be processed on this machine */
4155  int* durations, /**< array containing corresponding durations */
4156  int* demands, /**< array containing corresponding demands */
4157  int capacity, /**< available cumulative capacity */
4158  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
4159  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
4160  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
4161  * Usually set to TRUE. */
4162  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
4163  * TRUE for model constraints, FALSE for additional, redundant constraints. */
4164  SCIP_Bool check, /**< should the constraint be checked for feasibility?
4165  * TRUE for model constraints, FALSE for additional, redundant constraints. */
4166  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
4167  * Usually set to TRUE. */
4168  SCIP_Bool local, /**< is constraint only valid locally?
4169  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
4170  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
4171  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
4172  * adds coefficients to this constraint. */
4173  SCIP_Bool dynamic, /**< is constraint subject to aging?
4174  * Usually set to FALSE. Set to TRUE for own cuts which
4175  * are seperated as constraints. */
4176  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
4177  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
4178  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
4179  * if it may be moved to a more global node?
4180  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
4181  )
4182 {
4183  /* TODO: (optional) modify the definition of the SCIPcreateConsOptcumulative() call, if you don't need all the information */
4184 
4185  SCIP_CONSHDLR* conshdlr;
4186  SCIP_CONSDATA* consdata;
4187 
4188  /* find the optcumulative constraint handler */
4189  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
4190  if( conshdlr == NULL )
4191  {
4192  SCIPerrorMessage("optcumulative constraint handler not found\n");
4193  return SCIP_PLUGINNOTFOUND;
4194  }
4195 
4196  /* the optcumulative constraint handler currently does not support modifiable constraints */
4197  assert(modifiable == FALSE);
4198 
4199  /* create constraint data */
4200  SCIP_CALL( consdataCreate(scip, &consdata, nvars, vars, binvars, durations, demands, capacity, check) );
4201 
4202  /* create constraint */
4203  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
4204  local, modifiable, dynamic, removable, stickingatnode) );
4205 
4206  if( SCIPgetStage(scip) != SCIP_STAGE_PROBLEM )
4207  {
4208  SCIP_CONSHDLRDATA* conshdlrdata;
4209 
4210  /* get event handler */
4211  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4212  assert(conshdlrdata != NULL);
4213  assert(conshdlrdata->eventhdlrbinvars != NULL);
4214  assert(conshdlrdata->eventhdlrintvars != NULL);
4215 
4216  assert(consdata->nglbfixedones == 0);
4217  assert(consdata->nglbfixedzeros == 0);
4218 
4219  /* catch bound change events of variables */
4220  SCIP_CALL( catchAllEvents(scip, *cons, conshdlrdata->eventhdlrbinvars, conshdlrdata->eventhdlrintvars) );
4221  }
4222 
4223  return SCIP_OKAY;
4224 }
4225 
4226 /** set the left bound of the time axis to be considered (including hmin) */
4228  SCIP* scip, /**< SCIP data structure */
4229  SCIP_CONS* cons, /**< constraint data */
4230  int hmin /**< left bound of time axis to be considered */
4231  )
4232 {
4233  SCIP_CONSDATA* consdata;
4234  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4235  {
4236  SCIPerrorMessage("constraint is not a cumulative constraint with optional activities\n");
4237  return SCIP_INVALIDCALL;
4238  }
4239 
4240  consdata = SCIPconsGetData(cons);
4241  assert(consdata != NULL);
4242  assert(hmin >= 0);
4243  assert(hmin <= consdata->hmax);
4244 
4245  consdata->hmin = hmin;
4246 
4247  return SCIP_OKAY;
4248 }
4249 
4250 /** returns the left bound of the time axis to be considered */
4252  SCIP* scip, /**< SCIP data structure */
4253  SCIP_CONS* cons /**< constraint */
4254  )
4255 {
4256  SCIP_CONSDATA* consdata;
4257  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4258  {
4259  SCIPerrorMessage("constraint is not a cumulative constraint with optional activities\n");
4260  SCIPABORT();
4261  return 0; /*lint !e527*/
4262  }
4263 
4264  consdata = SCIPconsGetData(cons);
4265  assert(consdata != NULL);
4266 
4267  return consdata->hmin;
4268 }
4269 
4270 /** set the right bound of the time axis to be considered (not including hmax) */
4272  SCIP* scip, /**< SCIP data structure */
4273  SCIP_CONS* cons, /**< constraint data */
4274  int hmax /**< right bound of time axis to be considered */
4275  )
4276 {
4277  SCIP_CONSDATA* consdata;
4278  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4279  {
4280  SCIPerrorMessage("constraint is not a cumulative constraint with optional activities\n");
4281  return SCIP_INVALIDCALL; /*lint !e527*/
4282  }
4283 
4284  consdata = SCIPconsGetData(cons);
4285  assert(consdata != NULL);
4286  assert(hmax >= consdata->hmin);
4287 
4288  consdata->hmax = hmax;
4289 
4290  return SCIP_OKAY;
4291 }
4292 
4293 /** returns the right bound of the time axis to be considered */
4295  SCIP* scip, /**< SCIP data structure */
4296  SCIP_CONS* cons /**< constraint */
4297  )
4298 {
4299  SCIP_CONSDATA* consdata;
4300  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4301  {
4302  SCIPerrorMessage("constraint is not a cumulative constraint with optional activities\n");
4303  SCIPABORT();
4304  return 0; /*lint !e527*/
4305  }
4306 
4307  consdata = SCIPconsGetData(cons);
4308  assert(consdata != NULL);
4309 
4310  return consdata->hmax;
4311 }
#define CONSHDLR_SEPAPRIORITY
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
static SCIP_RETCODE dropEventBinvar(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
SCIP_RETCODE SCIPaddCoefLogicor(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
static SCIP_RETCODE upgradeCons(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *nupgdconss, SCIP_Bool *mustpropagate)
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4205
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1721
#define consExitOptcumulative
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:137
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4940
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:369
static SCIP_DECL_CONSINITLP(consInitlpOptcumulative)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5200
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1626
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9372
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8344
#define CONSHDLR_DELAYPROP
constraint handler for cumulative constraints
static SCIP_DECL_CONSCHECK(consCheckOptcumulative)
void SCIPsortRealPtrPtrIntInt(SCIP_Real *realarray, void **ptrarray1, void **ptrarray2, int *intarray1, int *intarray2, int len)
SCIP_RETCODE SCIPprofileDeleteCore(SCIP_PROFILE *profile, int left, int right, int demand)
Definition: misc.c:6952
#define CONSHDLR_PRESOLTIMING
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:345
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1649
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
#define SCIP_MAXSTRLEN
Definition: def.h:293
static SCIP_DECL_CONSPROP(consPropOptcumulative)
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1749
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2842
static long bound
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
SCIP_RETCODE SCIPcreateConsBasicBounddisjunction(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
static SCIP_DECL_CONSSEPALP(consSepalpOptcumulative)
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:524
static SCIP_RETCODE catchEventBinvar(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlrbinvars, SCIP_EVENTHDLR *eventhdlrintvars)
#define FALSE
Definition: def.h:87
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
static SCIP_RETCODE checkRedundancy(SCIP *scip, SCIP_CONS *cons, int *ndelconss, SCIP_Bool *redundant)
static SCIP_DECL_CONSFREE(consFreeOptcumulative)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:86
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define CONSHDLR_ENFOPRIORITY
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8364
static SCIP_DECL_CONSPRINT(consPrintOptcumulative)
static SCIP_DECL_CONSINITPRE(consInitpreOptcumulative)
#define CONSHDLR_PROPFREQ
#define SCIP_EVENTTYPE_GLBCHANGED
Definition: type_event.h:66
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8394
static SCIP_RETCODE solveSubproblem(SCIP *scip, SCIP_CONS *cons, SCIP_Bool conflictanalysis, SCIP_CONSDATA *consdata, SCIP_VAR **binvars, SCIP_VAR **vars, int *durations, int *demands, int nvars, int *nfixedvars, int *nchgbds, int *ndelconss, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5317
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPprofileInsertCore(SCIP_PROFILE *profile, int left, int right, int demand, int *pos, SCIP_Bool *infeasible)
Definition: misc.c:6922
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE catchEventIntvar(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:93
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:566
SCIP_RETCODE SCIPcreateConsBasicVarbound(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, SCIP_Real lhs, SCIP_Real rhs)
static SCIP_RETCODE detectImplications(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *naddconss)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8354
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5029
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1477
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip_cons.c:934
#define consDeactiveOptcumulative
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPsolveCumulative(SCIP *scip, int njobs, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Real *objvals, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint maxnodes, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *error)
#define consInitsolOptcumulative
int SCIPgetHmaxOptcumulative(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17456
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4256
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:69
SCIP_RETCODE SCIPheurPassSolTrySol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
Definition: heur_trysol.c:243
#define EVENTHDLR_INTVARS_DESC
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOptcumulative)
#define CONSHDLR_CHECKPRIORITY
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
static SCIP_RETCODE enfopsCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *trysol, SCIP_Bool *violated, SCIP_Bool *consadded, SCIP_Bool *solfeasible)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:96
static SCIP_RETCODE dropEventIntvar(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
static SCIP_DECL_CONSENFOLP(consEnfolpOptcumulative)
static void checkCounters(SCIP_CONSDATA *consdata)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:108
Constraint handler for knapsack constraints of the form , x binary and .
#define consSepasolOptcumulative
SCIP_RETCODE SCIPcreateConsOptcumulative(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_VAR **binvars, int *durations, int *demands, int capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPincludeConshdlrOptcumulative(SCIP *scip)
#define EVENTHDLR_INTVARS_NAME
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:249
#define SCIPerrorMessage
Definition: pub_message.h:55
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4175
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2769
SCIP_RETCODE SCIPcheckCumulativeCondition(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool *violated, SCIP_CONS *cons, SCIP_Bool printreason)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_RETCODE SCIPaddConsLocal(SCIP *scip, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3392
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3473
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:409
int SCIPcomputeHmin(SCIP *scip, SCIP_PROFILE *profile, int capacity)
SCIP_RETCODE SCIPcreateConsCumulative(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
static SCIP_RETCODE createSetPackingCons(SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2)
static SCIP_DECL_CONSPRESOL(consPresolOptcumulative)
#define CONSHDLR_DELAYSEPA
void SCIPstrCopySection(const char *str, char startchar, char endchar, char *token, int size, char **endptr)
Definition: misc.c:10886
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4434
#define CONSHDLR_MAXPREROUNDS
#define consEnforelaxOptcomulative
SCIP_RETCODE SCIPcreateConsBasicSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
Definition: cons_setppc.c:9299
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8085
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8712
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8304
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:251
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:164
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
#define consDisableOptcumulative
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4195
static SCIP_RETCODE fixIntegerVariable(SCIP *scip, SCIP_VAR *var, SCIP_Bool downlock, SCIP_Bool uplock, int *nchgbds)
static SCIP_RETCODE dropAllEvents(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlrbinvars, SCIP_EVENTHDLR *eventhdlrintvars)
#define NULL
Definition: lpi_spx1.cpp:155
#define CONSHDLR_EAGERFREQ
static SCIP_RETCODE applyZeroFixings(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgbds)
SCIP_RETCODE SCIPcreateConsKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define consExitpreOptcumulative
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS *cons, SCIP_Bool *rowadded, SCIP_Bool *consadded, SCIP_Bool *cutoff)
#define SCIP_EVENTTYPE_UBRELAXED
Definition: type_event.h:71
static SCIP_RETCODE solveCumulative(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_Bool local, SCIP_Real *ests, SCIP_Real *lsts, SCIP_Longint maxnodes, SCIP_Bool *solved, SCIP_Bool *infeasible, SCIP_Bool *unbounded, SCIP_Bool *error)
#define SCIP_CALL(x)
Definition: def.h:384
static SCIP_RETCODE conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:68
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
SCIP_RETCODE SCIPcreateWorstCaseProfile(SCIP *scip, SCIP_PROFILE *profile, int nvars, SCIP_VAR **vars, int *durations, int *demands)
SCIP_RETCODE SCIPprofileCreate(SCIP_PROFILE **profile, int capacity)
Definition: misc.c:6657
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8324
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:241
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:56
#define SCIP_EVENTTYPE_BOUNDTIGHTENED
Definition: type_event.h:114
static SCIP_RETCODE collectVars(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_VAR **vars, SCIP_Longint *weights, int *nvars, int starttime, int endtime)
SCIP_RETCODE SCIPpropCumulativeCondition(SCIP *scip, SCIP_PRESOLTIMING presoltiming, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_CONS *cons, int *nchgbds, SCIP_Bool *initialized, SCIP_Bool *explanation, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPsetHminCumulative(SCIP *scip, SCIP_CONS *cons, int hmin)
#define DEFAULT_INTERVALRELAX
#define CONSHDLR_DESC
SCIP_RETCODE SCIPsplitCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int *hmin, int *hmax, int *split)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
#define DEFAULT_CONFLICTANALYSIS
#define SCIP_Bool
Definition: def.h:84
static SCIP_RETCODE presolveCumulativeCondition(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *nchgcoefs, int *nchgsides, SCIP_Bool *cutoff)
static SCIP_RETCODE consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1021
static SCIP_Longint computeMaxEnergy(SCIP *scip, SCIP_CONSDATA *consdata, int starttime, int endtime)
static SCIP_DECL_CONSDELETE(consDeleteOptcumulative)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16542
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2473
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3423
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
Definition: misc.c:10856
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8105
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8214
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *binvar, SCIP_VAR *var, SCIP_Bool downlock, SCIP_Bool uplock)
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool conflictanalysis, int *nfixedvars, int *nchgbds, int *ndelconss, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8284
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8254
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:391
static SCIP_DECL_CONSRESPROP(consRespropOptcumulative)
#define consEnableOptcumulative
#define SCIP_PRESOLTIMING_ALWAYS
Definition: type_timing.h:49
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8273
#define EVENTHDLR_BINVARS_NAME
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, int nvars, SCIP_VAR **vars, SCIP_VAR **binvars, int *durations, int *demands, int capacity, SCIP_Bool check)
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:70
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define SCIP_EVENTTYPE_GBDCHANGED
Definition: type_event.h:111
static SCIP_DECL_CONSPARSE(consParseOptcumulative)
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
#define CONSHDLR_NAME
static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *violated, SCIP_Bool printreason)
SCIP_RETCODE SCIPnormalizeCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int *capacity, int *nchgcoefs, int *nchgsides)
SCIP_RETCODE SCIPrespropCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int *demands, int capacity, int hmin, int hmax, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd, SCIP_Bool *explanation, SCIP_RESULT *result)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
static void collectSolActivities(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, SCIP_VAR **binvars, SCIP_VAR **vars, int *durations, int *demands, int *nvars, int *nfixedones, int *nfixedzeros, SCIP_Bool *auxiliary)
SCIP_RETCODE SCIPsetHminOptcumulative(SCIP *scip, SCIP_CONS *cons, int hmin)
static SCIP_RETCODE createVarboundCons(SCIP *scip, SCIP_VAR *binvar, SCIP_VAR *intvar, int bound, SCIP_Bool lower)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3410
static void collectActivities(SCIP_CONSDATA *consdata, SCIP_VAR **binvars, SCIP_VAR **vars, int *durations, int *demands, int *nfixedones, int *nfixedzeros, SCIP_Bool *auxiliary)
static SCIP_RETCODE removeIrrelevantJobs(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
#define consDelvarsOptcumulative
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:91
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:702
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8115
#define CONSHDLR_NEEDSCONS
#define CONSHDLR_SEPAFREQ
SCIP_RETCODE SCIPrestartSolve(SCIP *scip)
Definition: scip_solve.c:3571
static void createSortedEventpoints(SCIP *scip, SCIP_CONSDATA *consdata, int *starttimes, int *endtimes, int *startindices, int *endindices, SCIP_Bool local)
int SCIPgetHminOptcumulative(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE createRow(SCIP *scip, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_VAR **vars, SCIP_Longint *weights, int nvars, SCIP_Longint capacity, SCIP_Bool local, SCIP_Bool *rowadded, SCIP_Bool *consadded, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPsetHmaxCumulative(SCIP *scip, SCIP_CONS *cons, int hmax)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
static SCIP_DECL_CONSEXITSOL(consExitsolOptcumulative)
static int convertBoundToInt(SCIP *scip, SCIP_Real bound)
static SCIP_DECL_CONSCOPY(consCopyOptcumulative)
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:117
static SCIP_RETCODE createBounddisjunctionCons(SCIP *scip, SCIP_VAR *binvar, SCIP_VAR *intvar, int lb, int ub)
SCIP_RETCODE SCIPsetHmaxOptcumulative(SCIP *scip, SCIP_CONS *cons, int hmax)
static SCIP_DECL_CONSLOCK(consLockOptcumulative)
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8334
static SCIP_RETCODE catchAllEvents(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlrbinvars, SCIP_EVENTHDLR *eventhdlrintvars)
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8274
static SCIP_RETCODE consdataDeletePos(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_CONS *cons, int pos)
#define SCIP_INVALID
Definition: def.h:197
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8264
#define consActiveOptcumulative
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2197
SCIP_RETCODE SCIPcreateCurrentSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:474
#define SCIP_Longint
Definition: def.h:162
static SCIP_DECL_EVENTEXEC(eventExecOptcumulativeBinvars)
static SCIP_RETCODE createConflictCons(SCIP *scip, const char *name, SCIP_VAR **binvars, int nvars)
static int removeRedundantRows(SCIP_Longint *rowtightness, int *startidxs, int nrows, SCIP_Longint tightness)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:55
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:156
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition: var.c:17393
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:110
SCIP_RETCODE SCIPincludeConshdlr(SCIP *scip, const char *name, const char *desc, int sepapriority, int enfopriority, int chckpriority, int sepafreq, int propfreq, int eagerfreq, int maxprerounds, SCIP_Bool delaysepa, SCIP_Bool delayprop, SCIP_Bool needscons, SCIP_PROPTIMING proptiming, SCIP_PRESOLTIMING presoltiming, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSFREE((*consfree)), SCIP_DECL_CONSINIT((*consinit)), SCIP_DECL_CONSEXIT((*consexit)), SCIP_DECL_CONSINITPRE((*consinitpre)), SCIP_DECL_CONSEXITPRE((*consexitpre)), SCIP_DECL_CONSINITSOL((*consinitsol)), SCIP_DECL_CONSEXITSOL((*consexitsol)), SCIP_DECL_CONSDELETE((*consdelete)), SCIP_DECL_CONSTRANS((*constrans)), SCIP_DECL_CONSINITLP((*consinitlp)), SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFORELAX((*consenforelax)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSPROP((*consprop)), SCIP_DECL_CONSPRESOL((*conspresol)), SCIP_DECL_CONSRESPROP((*consresprop)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_DECL_CONSACTIVE((*consactive)), SCIP_DECL_CONSDEACTIVE((*consdeactive)), SCIP_DECL_CONSENABLE((*consenable)), SCIP_DECL_CONSDISABLE((*consdisable)), SCIP_DECL_CONSDELVARS((*consdelvars)), SCIP_DECL_CONSPRINT((*consprint)), SCIP_DECL_CONSCOPY((*conscopy)), SCIP_DECL_CONSPARSE((*consparse)), SCIP_DECL_CONSGETVARS((*consgetvars)), SCIP_DECL_CONSGETNVARS((*consgetnvars)), SCIP_DECL_CONSGETDIVEBDCHGS((*consgetdivebdchgs)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:73
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
SCIPallocBlockMemory(scip, subsol))
#define SCIP_EVENTTYPE_GUBCHANGED
Definition: type_event.h:67
#define consInitOptcumulative
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1382
#define EVENTHDLR_BINVARS_DESC
#define SCIPABORT()
Definition: def.h:356
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip_var.c:221
#define DEFAULT_ROWRELAX
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
default SCIP plugins
static SCIP_DECL_CONSTRANS(consTransOptcumulative)
constraint handler for cumulative constraints with optional activities
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1524
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
SCIP_RETCODE SCIPpresolveCumulativeCondition(SCIP *scip, int nvars, SCIP_VAR **vars, int *durations, int hmin, int hmax, SCIP_Bool *downlocks, SCIP_Bool *uplocks, SCIP_CONS *cons, SCIP_Bool *irrelevants, int *nfixedvars, int *nchgsides, SCIP_Bool *cutoff)
void SCIPprofileFree(SCIP_PROFILE **profile)
Definition: misc.c:6671
static SCIP_DECL_CONSENFOPS(consEnfopsOptcumulative)
#define CONSHDLR_PROP_TIMING
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:142
#define SCIP_EVENTTYPE_BOUNDRELAXED
Definition: type_event.h:115
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1766