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