Scippy

SCIP

Solving Constraint Integer Programs

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