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