Scippy

SCIP

Solving Constraint Integer Programs

cons_optcumulative.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file cons_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  SCIP_CONSHDLR* conshdlr;
4108 
4109  /* create event handler for bound change events */
4111  eventExecOptcumulativeBinvars, NULL) );
4112 
4113  /* create event handler for bound change events */
4115  eventExecOptcumulativeIntvars, NULL) );
4116 
4117  /* create constraint handler data */
4118  SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlrbinvars, eventhdlrintvars) );
4119 
4120  /* include constraint handler */
4123  consEnfolpOptcumulative, consEnfopsOptcumulative, consCheckOptcumulative,
4124  consLockOptcumulative, conshdlrdata) );
4125 
4126  /* set non-fundamental callbacks via specific setter functions */
4127  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOptcumulative, consCopyOptcumulative) );
4130  SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr, consInitpreOptcumulative) );
4132  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpOptcumulative) );
4134  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolOptcumulative) );
4140  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOptcumulative) );
4141  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOptcumulative) );
4142  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOptcumulative) );
4143  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolOptcumulative,
4145  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOptcumulative) );
4146  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropOptcumulative, CONSHDLR_PROPFREQ,
4148  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOptcumulative) );
4149  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOptcumulative, consSepasolOptcumulative,
4151  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOptcumulative) );
4153 
4154  /* add optcumulative constraint handler parameters */
4156  "constraints/"CONSHDLR_NAME"/rowrelax",
4157  "add linear relaxation as LP row (otherwise a knapsack constraint is created)?",
4158  &conshdlrdata->rowrelax, FALSE, DEFAULT_ROWRELAX, NULL, NULL) );
4159 
4161  "constraints/"CONSHDLR_NAME"/conflictanalysis",
4162  "participate in conflict analysis?",
4163  &conshdlrdata->conflictanalysis, FALSE, DEFAULT_CONFLICTANALYSIS, NULL, NULL) );
4164 
4166  "constraints/"CONSHDLR_NAME"/intervalrelax",
4167  "create a relaxation for each start and end time point interval",
4168  &conshdlrdata->intervalrelax, FALSE, DEFAULT_INTERVALRELAX, NULL, NULL) );
4169 
4170  return SCIP_OKAY;
4171 }
4172 
4173 /** creates and captures a optcumulative constraint */
4175  SCIP* scip, /**< SCIP data structure */
4176  SCIP_CONS** cons, /**< pointer to hold the created constraint */
4177  const char* name, /**< name of constraint */
4178  int nvars, /**< number of variables (jobs) */
4179  SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
4180  SCIP_VAR** binvars, /**< array of variable representing if the job has to be processed on this machine */
4181  int* durations, /**< array containing corresponding durations */
4182  int* demands, /**< array containing corresponding demands */
4183  int capacity, /**< available cumulative capacity */
4184  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
4185  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
4186  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
4187  * Usually set to TRUE. */
4188  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
4189  * TRUE for model constraints, FALSE for additional, redundant constraints. */
4190  SCIP_Bool check, /**< should the constraint be checked for feasibility?
4191  * TRUE for model constraints, FALSE for additional, redundant constraints. */
4192  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
4193  * Usually set to TRUE. */
4194  SCIP_Bool local, /**< is constraint only valid locally?
4195  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
4196  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
4197  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
4198  * adds coefficients to this constraint. */
4199  SCIP_Bool dynamic, /**< is constraint subject to aging?
4200  * Usually set to FALSE. Set to TRUE for own cuts which
4201  * are seperated as constraints. */
4202  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
4203  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
4204  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
4205  * if it may be moved to a more global node?
4206  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
4207  )
4208 {
4209  /* TODO: (optional) modify the definition of the SCIPcreateConsOptcumulative() call, if you don't need all the information */
4210 
4211  SCIP_CONSHDLR* conshdlr;
4212  SCIP_CONSDATA* consdata;
4213 
4214  /* find the optcumulative constraint handler */
4215  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
4216  if( conshdlr == NULL )
4217  {
4218  SCIPerrorMessage("optcumulative constraint handler not found\n");
4219  return SCIP_PLUGINNOTFOUND;
4220  }
4221 
4222  /* the optcumulative constraint handler currently does not support modifiable constraints */
4223  assert(modifiable == FALSE);
4224 
4225  /* create constraint data */
4226  SCIP_CALL( consdataCreate(scip, &consdata, nvars, vars, binvars, durations, demands, capacity, check) );
4227 
4228  /* create constraint */
4229  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
4230  local, modifiable, dynamic, removable, stickingatnode) );
4231 
4232  if( SCIPgetStage(scip) != SCIP_STAGE_PROBLEM )
4233  {
4234  SCIP_CONSHDLRDATA* conshdlrdata;
4235 
4236  /* get event handler */
4237  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4238  assert(conshdlrdata != NULL);
4239  assert(conshdlrdata->eventhdlrbinvars != NULL);
4240  assert(conshdlrdata->eventhdlrintvars != NULL);
4241 
4242  assert(consdata->nglbfixedones == 0);
4243  assert(consdata->nglbfixedzeros == 0);
4244 
4245  /* catch bound change events of variables */
4246  SCIP_CALL( catchAllEvents(scip, *cons, conshdlrdata->eventhdlrbinvars, conshdlrdata->eventhdlrintvars) );
4247  }
4248 
4249  return SCIP_OKAY;
4250 }
4251 
4252 /** set the left bound of the time axis to be considered (including hmin) */
4254  SCIP* scip, /**< SCIP data structure */
4255  SCIP_CONS* cons, /**< constraint data */
4256  int hmin /**< left bound of time axis to be considered */
4257  )
4258 {
4259  SCIP_CONSDATA* consdata;
4260  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4261  {
4262  SCIPerrorMessage("constraint is not a cumulative constraint with optional activities\n");
4263  return SCIP_INVALIDCALL;
4264  }
4265 
4266  consdata = SCIPconsGetData(cons);
4267  assert(consdata != NULL);
4268  assert(hmin >= 0);
4269  assert(hmin <= consdata->hmax);
4270 
4271  consdata->hmin = hmin;
4272 
4273  return SCIP_OKAY;
4274 }
4275 
4276 /** returns the left bound of the time axis to be considered */
4278  SCIP* scip, /**< SCIP data structure */
4279  SCIP_CONS* cons /**< constraint */
4280  )
4281 {
4282  SCIP_CONSDATA* consdata;
4283  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4284  {
4285  SCIPerrorMessage("constraint is not a cumulative constraint with optional activities\n");
4286  SCIPABORT();
4287  return 0; /*lint !e527*/
4288  }
4289 
4290  consdata = SCIPconsGetData(cons);
4291  assert(consdata != NULL);
4292 
4293  return consdata->hmin;
4294 }
4295 
4296 /** set the right bound of the time axis to be considered (not including hmax) */
4298  SCIP* scip, /**< SCIP data structure */
4299  SCIP_CONS* cons, /**< constraint data */
4300  int hmax /**< right bound of time axis to be considered */
4301  )
4302 {
4303  SCIP_CONSDATA* consdata;
4304  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4305  {
4306  SCIPerrorMessage("constraint is not a cumulative constraint with optional activities\n");
4307  return SCIP_INVALIDCALL; /*lint !e527*/
4308  }
4309 
4310  consdata = SCIPconsGetData(cons);
4311  assert(consdata != NULL);
4312  assert(hmax >= consdata->hmin);
4313 
4314  consdata->hmax = hmax;
4315 
4316  return SCIP_OKAY;
4317 }
4318 
4319 /** returns the right bound of the time axis to be considered */
4321  SCIP* scip, /**< SCIP data structure */
4322  SCIP_CONS* cons /**< constraint */
4323  )
4324 {
4325  SCIP_CONSDATA* consdata;
4326  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4327  {
4328  SCIPerrorMessage("constraint is not a cumulative constraint with optional activities\n");
4329  SCIPABORT();
4330  return 0; /*lint !e527*/
4331  }
4332 
4333  consdata = SCIPconsGetData(cons);
4334  assert(consdata != NULL);
4335 
4336  return consdata->hmax;
4337 }
#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:4229
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1785
#define consExitOptcumulative
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
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:4945
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
#define NULL
Definition: def.h:267
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:5205
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:9530
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8475
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:601
#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:7050
#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:941
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18079
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:288
static SCIP_DECL_CONSPROP(consPropOptcumulative)
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1813
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2843
static long bound
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
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:18135
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)
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre)))
Definition: scip_cons.c:492
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlrbinvars, SCIP_EVENTHDLR *eventhdlrintvars)
#define FALSE
Definition: def.h:94
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
static SCIP_RETCODE checkRedundancy(SCIP *scip, SCIP_CONS *cons, int *ndelconss, SCIP_Bool *redundant)
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:181
static SCIP_DECL_CONSFREE(consFreeOptcumulative)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:93
#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:8495
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:8525
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:5322
#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:7020
#define SCIPdebugMessage
Definition: pub_message.h:96
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:235
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:590
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)
SCIP_RETCODE SCIPsetConshdlrDelvars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELVARS((*consdelvars)))
Definition: scip_cons.c:762
static SCIP_RETCODE detectImplications(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *naddconss)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8485
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:624
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5034
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1482
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:808
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:998
#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:17523
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4261
#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:18089
static SCIP_RETCODE enfopsCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *trysol, SCIP_Bool *violated, SCIP_Bool *consadded, SCIP_Bool *solfeasible)
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
#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)
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
#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:4199
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
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:3393
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:3474
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:11007
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4439
#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:9457
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8216
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8717
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8435
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:17420
#define consDisableOptcumulative
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4219
static SCIP_RETCODE fixIntegerVariable(SCIP *scip, SCIP_VAR *var, SCIP_Bool downlock, SCIP_Bool uplock, int *nchgbds)
static SCIP_RETCODE dropAllEvents(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlrbinvars, SCIP_EVENTHDLR *eventhdlrintvars)
#define CONSHDLR_EAGERFREQ
static SCIP_RETCODE applyZeroFixings(SCIP *scip, SCIP_CONS *cons, int *nchgcoefs, int *nchgbds)
SCIP_RETCODE SCIPcreateConsKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define consExitpreOptcumulative
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS *cons, SCIP_Bool *rowadded, SCIP_Bool *consadded, SCIP_Bool *cutoff)
#define SCIP_EVENTTYPE_UBRELAXED
Definition: type_event.h: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:380
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:6755
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8455
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:647
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:1077
#define DEFAULT_CONFLICTANALYSIS
#define SCIP_Bool
Definition: def.h:91
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:16711
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2537
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3430
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
Definition: misc.c:10977
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8236
#define MIN(x, y)
Definition: def.h:243
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8345
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *binvar, SCIP_VAR *var, SCIP_Bool downlock, SCIP_Bool uplock)
SCIP_RETCODE SCIPsetConshdlrDisable(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDISABLE((*consdisable)))
Definition: scip_cons.c:739
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:841
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8415
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8385
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17927
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:8278
#define EVENTHDLR_BINVARS_NAME
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, int nvars, SCIP_VAR **vars, SCIP_VAR **binvars, int *durations, int *demands, int capacity, SCIP_Bool check)
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:785
#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
SCIP_RETCODE SCIPsetConshdlrEnable(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENABLE((*consenable)))
Definition: scip_cons.c:716
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)
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre)))
Definition: scip_cons.c:516
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)
#define MAX(x, y)
Definition: def.h:239
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:3417
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:8246
#define CONSHDLR_NEEDSCONS
SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINIT((*consinit)))
Definition: scip_cons.c:396
#define CONSHDLR_SEPAFREQ
SCIP_RETCODE SCIPrestartSolve(SCIP *scip)
Definition: scip_solve.c:3472
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)
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit)))
Definition: scip_cons.c:420
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:1174
static SCIP_DECL_CONSEXITSOL(consExitsolOptcumulative)
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:540
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:173
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8465
static SCIP_RETCODE catchAllEvents(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlrbinvars, SCIP_EVENTHDLR *eventhdlrintvars)
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:718
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8405
static SCIP_RETCODE consdataDeletePos(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_CONS *cons, int pos)
#define SCIP_INVALID
Definition: def.h:193
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8395
#define consActiveOptcumulative
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
SCIP_RETCODE SCIPcreateCurrentSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:339
#define SCIP_Longint
Definition: def.h:158
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:18145
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:165
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition: var.c:17562
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip_cons.c:670
#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
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:468
#define SCIPABORT()
Definition: def.h:352
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:1217
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:1529
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:6769
static SCIP_DECL_CONSENFOPS(consEnfopsOptcumulative)
#define CONSHDLR_PROP_TIMING
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:151
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:281
#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:1631