Scippy

SCIP

Solving Constraint Integer Programs

cons_cumulative.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_cumulative.c
26 * @ingroup DEFPLUGINS_CONS
27 * @brief constraint handler for cumulative constraints
28 * @author Timo Berthold
29 * @author Stefan Heinz
30 * @author Jens Schulz
31 *
32 * Given:
33 * - a set of jobs, represented by their integer start time variables \f$S_j\f$, their array of processing times \f$p_j\f$ and of
34 * their demands \f$d_j\f$.
35 * - an integer resource capacity \f$C\f$
36 *
37 * The cumulative constraint ensures that for each point in time \f$t\f$ \f$\sum_{j: S_j \leq t < S_j + p_j} d_j \leq C\f$ holds.
38 *
39 * Separation:
40 * - can be done using binary start time model, see Pritskers, Watters and Wolfe
41 * - or by just separating relatively weak cuts on the integer start time variables
42 *
43 * Propagation:
44 * - time tabling, Klein & Scholl (1999)
45 * - Edge-finding from Petr Vilim, adjusted and simplified for dynamic repropagation
46 * (2009)
47 * - energetic reasoning, see Baptiste, Le Pape, Nuijten (2001)
48 *
49 */
50
51/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
52
53#include <assert.h>
54#include <string.h>
55
56#include "tclique/tclique.h"
58#include "scip/cons_linking.h"
59#include "scip/cons_knapsack.h"
60#include "scip/scipdefplugins.h"
61
62/**@name Constraint handler properties
63 *
64 * @{
65 */
66
67/* constraint handler properties */
68#define CONSHDLR_NAME "cumulative"
69#define CONSHDLR_DESC "cumulative constraint handler"
70#define CONSHDLR_SEPAPRIORITY 2100000 /**< priority of the constraint handler for separation */
71#define CONSHDLR_ENFOPRIORITY -2040000 /**< priority of the constraint handler for constraint enforcing */
72#define CONSHDLR_CHECKPRIORITY -3030000 /**< priority of the constraint handler for checking feasibility */
73#define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
74#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
75#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
76 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
77#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
78#define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
79#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
80#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
81
82#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
83#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
84
85/**@} */
86
87/**@name Default parameter values
88 *
89 * @{
90 */
91
92/* default parameter values */
93
94/* separation */
95#define DEFAULT_USEBINVARS FALSE /**< should the binary representation be used? */
96#define DEFAULT_LOCALCUTS FALSE /**< should cuts be added only locally? */
97#define DEFAULT_USECOVERCUTS TRUE /**< should covering cuts be added? */
98#define DEFAULT_CUTSASCONSS TRUE /**< should the cuts be created as knapsack constraints? */
99#define DEFAULT_SEPAOLD TRUE /**< shall old sepa algo be applied? */
100
101/* propagation */
102#define DEFAULT_TTINFER TRUE /**< should time-table (core-times) propagator be used to infer bounds? */
103#define DEFAULT_EFCHECK FALSE /**< should edge-finding be used to detect an overload? */
104#define DEFAULT_EFINFER FALSE /**< should edge-finding be used to infer bounds? */
105#define DEFAULT_USEADJUSTEDJOBS FALSE /**< should during edge-finding jobs be adusted which run on the border of the effective time horizon? */
106#define DEFAULT_TTEFCHECK TRUE /**< should time-table edge-finding be used to detect an overload? */
107#define DEFAULT_TTEFINFER TRUE /**< should time-table edge-finding be used to infer bounds? */
108
109/* presolving */
110#define DEFAULT_DUALPRESOLVE TRUE /**< should dual presolving be applied? */
111#define DEFAULT_COEFTIGHTENING FALSE /**< should coeffisient tightening be applied? */
112#define DEFAULT_NORMALIZE TRUE /**< should demands and capacity be normalized? */
113#define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
114#define DEFAULT_DISJUNCTIVE TRUE /**< extract disjunctive constraints? */
115#define DEFAULT_DETECTDISJUNCTIVE TRUE /**< search for conflict set via maximal cliques to detect disjunctive constraints */
116#define DEFAULT_DETECTVARBOUNDS TRUE /**< search for conflict set via maximal cliques to detect variable bound constraints */
117#define DEFAULT_MAXNODES 10000LL /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
118
119/* enforcement */
120#define DEFAULT_FILLBRANCHCANDS FALSE /**< should branching candidates be added to storage? */
121
122/* conflict analysis */
123#define DEFAULT_USEBDWIDENING TRUE /**< should bound widening be used during conflict analysis? */
124
125/**@} */
126
127/**@name Event handler properties
128 *
129 * @{
130 */
131
132#define EVENTHDLR_NAME "cumulative"
133#define EVENTHDLR_DESC "bound change event handler for cumulative constraints"
134
135/**@} */
136
137/*
138 * Data structures
139 */
140
141/** constraint data for cumulative constraints */
142struct SCIP_ConsData
143{
144 SCIP_VAR** vars; /**< array of variable representing the start time of each job */
145 SCIP_Bool* downlocks; /**< array to store if the variable has a down lock */
146 SCIP_Bool* uplocks; /**< array to store if the variable has an uplock */
147 SCIP_CONS** linkingconss; /**< array of linking constraints for the integer variables */
148 SCIP_ROW** demandrows; /**< array of rows of linear relaxation of this problem */
149 SCIP_ROW** scoverrows; /**< array of rows of small cover cuts of this problem */
150 SCIP_ROW** bcoverrows; /**< array of rows of big cover cuts of this problem */
151 int* demands; /**< array containing corresponding demands */
152 int* durations; /**< array containing corresponding durations */
153 SCIP_Real resstrength1; /**< stores the resource strength 1*/
154 SCIP_Real resstrength2; /**< stores the resource strength 2 */
155 SCIP_Real cumfactor1; /**< stroes the cumulativeness of the constraint */
156 SCIP_Real disjfactor1; /**< stores the disjunctiveness of the constraint */
157 SCIP_Real disjfactor2; /**< stores the disjunctiveness of the constraint */
158 SCIP_Real estimatedstrength;
159 int nvars; /**< number of variables */
160 int varssize; /**< size of the arrays */
161 int ndemandrows; /**< number of rows of cumulative constrint for linear relaxation */
162 int demandrowssize; /**< size of array rows of demand rows */
163 int nscoverrows; /**< number of rows of small cover cuts */
164 int scoverrowssize; /**< size of array of small cover cuts */
165 int nbcoverrows; /**< number of rows of big cover cuts */
166 int bcoverrowssize; /**< size of array of big cover cuts */
167 int capacity; /**< available cumulative capacity */
168
169 int hmin; /**< left bound of time axis to be considered (including hmin) */
170 int hmax; /**< right bound of time axis to be considered (not including hmax) */
171
172 unsigned int signature; /**< constraint signature which is need for pairwise comparison */
173
174 unsigned int validsignature:1; /**< is the signature valid */
175 unsigned int normalized:1; /**< is the constraint normalized */
176 unsigned int covercuts:1; /**< cover cuts are created? */
177 unsigned int propagated:1; /**< is constraint propagted */
178 unsigned int varbounds:1; /**< bool to store if variable bound strengthening was already preformed */
179 unsigned int triedsolving:1; /**< bool to store if we tried already to solve that constraint as independent subproblem */
180
181#ifdef SCIP_STATISTIC
182 int maxpeak;
183#endif
184};
185
186/** constraint handler data */
187struct SCIP_ConshdlrData
188{
189 SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */
190
191 SCIP_Bool usebinvars; /**< should the binary variables be used? */
192 SCIP_Bool cutsasconss; /**< should the cumulative constraint create cuts as knapsack constraints? */
193 SCIP_Bool ttinfer; /**< should time-table (core-times) propagator be used to infer bounds? */
194 SCIP_Bool efcheck; /**< should edge-finding be used to detect an overload? */
195 SCIP_Bool efinfer; /**< should edge-finding be used to infer bounds? */
196 SCIP_Bool useadjustedjobs; /**< should during edge-finding jobs be adusted which run on the border of the effective time horizon? */
197 SCIP_Bool ttefcheck; /**< should time-table edge-finding be used to detect an overload? */
198 SCIP_Bool ttefinfer; /**< should time-table edge-finding be used to infer bounds? */
199 SCIP_Bool localcuts; /**< should cuts be added only locally? */
200 SCIP_Bool usecovercuts; /**< should covering cuts be added? */
201 SCIP_Bool sepaold; /**< shall old sepa algo be applied? */
202
203 SCIP_Bool fillbranchcands; /**< should branching candidates be added to storage? */
204
205 SCIP_Bool dualpresolve; /**< should dual presolving be applied? */
206 SCIP_Bool coeftightening; /**< should coeffisient tightening be applied? */
207 SCIP_Bool normalize; /**< should demands and capacity be normalized? */
208 SCIP_Bool disjunctive; /**< extract disjunctive constraints? */
209 SCIP_Bool detectdisjunctive; /**< search for conflict set via maximal cliques to detect disjunctive constraints */
210 SCIP_Bool detectvarbounds; /**< search for conflict set via maximal cliques to detect variable bound constraints */
211 SCIP_Bool usebdwidening; /**< should bound widening be used during conflict analysis? */
212 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
213 SCIP_Bool detectedredundant; /**< was detection of redundant constraints already performed? */
214
215 SCIP_Longint maxnodes; /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
216
217 SCIP_DECL_SOLVECUMULATIVE((*solveCumulative)); /**< method to use a single cumulative condition */
218
219 /* statistic values which are collected if SCIP_STATISTIC is defined */
220#ifdef SCIP_STATISTIC
221 SCIP_Longint nlbtimetable; /**< number of times the lower bound was tightened by the time-table propagator */
222 SCIP_Longint nubtimetable; /**< number of times the upper bound was tightened by the time-table propagator */
223 SCIP_Longint ncutofftimetable; /**< number of times the a cutoff was detected due to time-table propagator */
224 SCIP_Longint nlbedgefinder; /**< number of times the lower bound was tightened by the edge-finder propagator */
225 SCIP_Longint nubedgefinder; /**< number of times the upper bound was tightened by the edge-finder propagator */
226 SCIP_Longint ncutoffedgefinder; /**< number of times the a cutoff was detected due to edge-finder propagator */
227 SCIP_Longint ncutoffoverload; /**< number of times the a cutoff was detected due to overload checking via edge-finding */
228 SCIP_Longint nlbTTEF; /**< number of times the lower bound was tightened by time-table edge-finding */
229 SCIP_Longint nubTTEF; /**< number of times the upper bound was tightened by time-table edge-finding */
230 SCIP_Longint ncutoffoverloadTTEF;/**< number of times the a cutoff was detected due to overload checking via time-table edge-finding */
231
232 int nirrelevantjobs; /**< number of time a irrelevant/redundant jobs was removed form a constraint */
233 int nalwaysruns; /**< number of time a job removed form a constraint which run completely during the effective horizon */
234 int nremovedlocks; /**< number of times a up or down lock was removed */
235 int ndualfixs; /**< number of times a dual fix was performed by a single constraint */
236 int ndecomps; /**< number of times a constraint was decomposed */
237 int ndualbranchs; /**< number of times a dual branch was discoverd and applicable via probing */
238 int nallconsdualfixs; /**< number of times a dual fix was performed due to knowledge of all cumulative constraints */
239 int naddedvarbounds; /**< number of added variable bounds constraints */
240 int naddeddisjunctives; /**< number of added disjunctive constraints */
241
242 SCIP_Bool iscopy; /**< Boolean to store if constraint handler is part of a copy */
243#endif
244};
245
246/**@name Inference Information Methods
247 *
248 * An inference information can be passed with each domain reduction to SCIP. This information is passed back to the
249 * constraint handler if the corresponding bound change has to be explained. It can be used to store information which
250 * help to construct a reason/explanation for a bound change. The inference information is limited to size of integer.
251 *
252 * In case of the cumulative constraint handler we store the used propagation algorithms for that particular bound
253 * change and the earliest start and latest completion time of all jobs in the conflict set.
254 *
255 * @{
256 */
257
258/** Propagation rules */
260{
261 PROPRULE_0_INVALID = 0, /**< invalid inference information */
262 PROPRULE_1_CORETIMES = 1, /**< core-time propagator */
263 PROPRULE_2_EDGEFINDING = 2, /**< edge-finder */
264 PROPRULE_3_TTEF = 3 /**< time-table edeg-finding */
266typedef enum Proprule PROPRULE;
267
268/** inference information */
269struct InferInfo
270{
271 union
272 {
273 /** struct to use the inference information */
274 struct
275 {
276 unsigned int proprule:2; /**< propagation rule that was applied */
277 unsigned int data1:15; /**< data field one */
278 unsigned int data2:15; /**< data field two */
279 } asbits;
280 int asint; /**< inference information as a single int value */
281 } val;
282};
283typedef struct InferInfo INFERINFO;
284
285/** converts an integer into an inference information */
286static
288 int i /**< integer to convert */
289 )
290{
291 INFERINFO inferinfo;
292
293 inferinfo.val.asint = i;
294
295 return inferinfo;
296}
297
298/** converts an inference information into an int */
299static
301 INFERINFO inferinfo /**< inference information to convert */
302 )
303{
304 return inferinfo.val.asint;
305}
306
307/** returns the propagation rule stored in the inference information */
308static
310 INFERINFO inferinfo /**< inference information to convert */
311 )
312{
313 return (PROPRULE) inferinfo.val.asbits.proprule;
314}
315
316/** returns data field one of the inference information */
317static
319 INFERINFO inferinfo /**< inference information to convert */
320 )
321{
322 return (int) inferinfo.val.asbits.data1;
323}
324
325/** returns data field two of the inference information */
326static
328 INFERINFO inferinfo /**< inference information to convert */
329 )
330{
331 return (int) inferinfo.val.asbits.data2;
332}
333
334/** returns whether the inference information is valid */
335static
337 INFERINFO inferinfo /**< inference information to convert */
338 )
339{
340 return (inferinfo.val.asint != 0);
341}
342
343
344/** constructs an inference information out of a propagation rule, an earliest start and a latest completion time */
345static
347 PROPRULE proprule, /**< propagation rule that deduced the value */
348 int data1, /**< data field one */
349 int data2 /**< data field two */
350 )
351{
352 INFERINFO inferinfo;
353
354 /* check that the data members are in the range of the available bits */
355 if( proprule == PROPRULE_0_INVALID || data1 < 0 || data1 >= (1<<15) || data2 < 0 || data2 >= (1<<15) )
356 {
357 inferinfo.val.asint = 0;
358 assert(inferInfoGetProprule(inferinfo) == PROPRULE_0_INVALID);
359 assert(inferInfoIsValid(inferinfo) == FALSE);
360 }
361 else
362 {
363 inferinfo.val.asbits.proprule = proprule; /*lint !e641*/
364 inferinfo.val.asbits.data1 = (unsigned int) data1; /*lint !e732*/
365 inferinfo.val.asbits.data2 = (unsigned int) data2; /*lint !e732*/
366 assert(inferInfoIsValid(inferinfo) == TRUE);
367 }
368
369 return inferinfo;
370}
371
372/**@} */
373
374/*
375 * Local methods
376 */
377
378/**@name Miscellaneous Methods
379 *
380 * @{
381 */
382
383#ifndef NDEBUG
384
385/** compute the core of a job which lies in certain interval [begin, end) */
386static
388 int begin, /**< begin of the interval */
389 int end, /**< end of the interval */
390 int ect, /**< earliest completion time */
391 int lst /**< latest start time */
392 )
393{
394 int core;
395
396 core = MAX(0, MIN(end, ect) - MAX(lst, begin));
397
398 return core;
399}
400#else
401#define computeCoreWithInterval(begin, end, ect, lst) (MAX(0, MIN((end), (ect)) - MAX((lst), (begin))))
402#endif
403
404/** returns the implied earliest start time */ /*lint -e{715}*/
405static
407 SCIP* scip, /**< SCIP data structure */
408 SCIP_VAR* var, /**< variable for which the implied est should be returned */
409 SCIP_HASHMAP* addedvars, /**< hash map containig the variable which are already added */
410 int* est /**< pointer to store the implied earliest start time */
411 )
412{ /*lint --e{715}*/
413#if 0
414 SCIP_VAR** vbdvars;
415 SCIP_VAR* vbdvar;
416 SCIP_Real* vbdcoefs;
417 SCIP_Real* vbdconsts;
418 void* image;
419 int nvbdvars;
420 int v;
421#endif
422
424
425#if 0
426 /* the code contains a bug; we need to check if an implication forces that the jobs do not run in parallel */
427
428 nvbdvars = SCIPvarGetNVlbs(var);
429 vbdvars = SCIPvarGetVlbVars(var);
430 vbdcoefs = SCIPvarGetVlbCoefs(var);
431 vbdconsts = SCIPvarGetVlbConstants(var);
432
433 for( v = 0; v < nvbdvars; ++v )
434 {
435 vbdvar = vbdvars[v];
436 assert(vbdvar != NULL);
437
438 image = SCIPhashmapGetImage(addedvars, (void*)vbdvar);
439
440 if( image != NULL && SCIPisEQ(scip, vbdcoefs[v], 1.0 ) )
441 {
442 int duration;
443 int vbdconst;
444
445 duration = (int)(size_t)image;
446 vbdconst = SCIPconvertRealToInt(scip, vbdconsts[v]);
447
448 SCIPdebugMsg(scip, "check implication <%s>[%g,%g] >= <%s>[%g,%g] + <%g>\n",
450 SCIPvarGetName(vbdvar), SCIPvarGetLbLocal(vbdvar), SCIPvarGetUbLocal(vbdvar), vbdconsts[v]);
451
452 if( duration >= vbdconst )
453 {
454 int impliedest;
455
456 impliedest = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vbdvar)) + duration;
457
458 if( (*est) < impliedest )
459 {
460 (*est) = impliedest;
461
462 SCIP_CALL( SCIPhashmapRemove(addedvars, (void*)vbdvar) );
463 }
464 }
465 }
466 }
467#endif
468
469 return SCIP_OKAY;
470}
471
472/** returns the implied latest completion time */ /*lint -e{715}*/
473static
475 SCIP* scip, /**< SCIP data structure */
476 SCIP_VAR* var, /**< variable for which the implied est should be returned */
477 int duration, /**< duration of the given job */
478 SCIP_HASHMAP* addedvars, /**< hash map containig the variable which are already added */
479 int* lct /**< pointer to store the implied latest completion time */
480 )
481{ /*lint --e{715}*/
482#if 0
483 SCIP_VAR** vbdvars;
484 SCIP_VAR* vbdvar;
485 SCIP_Real* vbdcoefs;
486 SCIP_Real* vbdconsts;
487 int nvbdvars;
488 int v;
489#endif
490
491 (*lct) = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) + duration;
492
493#if 0
494 /* the code contains a bug; we need to check if an implication forces that the jobs do not run in parallel */
495
496 nvbdvars = SCIPvarGetNVubs(var);
497 vbdvars = SCIPvarGetVubVars(var);
498 vbdcoefs = SCIPvarGetVubCoefs(var);
499 vbdconsts = SCIPvarGetVubConstants(var);
500
501 for( v = 0; v < nvbdvars; ++v )
502 {
503 vbdvar = vbdvars[v];
504 assert(vbdvar != NULL);
505
506 if( SCIPhashmapExists(addedvars, (void*)vbdvar) && SCIPisEQ(scip, vbdcoefs[v], 1.0 ) )
507 {
508 int vbdconst;
509
510 vbdconst = SCIPconvertRealToInt(scip, -vbdconsts[v]);
511
512 SCIPdebugMsg(scip, "check implication <%s>[%g,%g] <= <%s>[%g,%g] + <%g>\n",
514 SCIPvarGetName(vbdvar), SCIPvarGetLbLocal(vbdvar), SCIPvarGetUbLocal(vbdvar), vbdconsts[v]);
515
516 if( duration >= -vbdconst )
517 {
518 int impliedlct;
519
520 impliedlct = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vbdvar));
521
522 if( (*lct) > impliedlct )
523 {
524 (*lct) = impliedlct;
525
526 SCIP_CALL( SCIPhashmapRemove(addedvars, (void*)vbdvar) );
527 }
528 }
529 }
530 }
531#endif
532
533 return SCIP_OKAY;
534}
535
536/** collects all necessary binary variables to represent the jobs which can be active at time point of interest */
537static
539 SCIP* scip, /**< SCIP data structure */
540 SCIP_CONSDATA* consdata, /**< constraint data */
541 SCIP_VAR*** vars, /**< pointer to the array to store the binary variables */
542 int** coefs, /**< pointer to store the coefficients */
543 int* nvars, /**< number if collect binary variables */
544 int* startindices, /**< permutation with rspect to the start times */
545 int curtime, /**< current point in time */
546 int nstarted, /**< number of jobs that start before the curtime or at curtime */
547 int nfinished /**< number of jobs that finished before curtime or at curtime */
548 )
549{
550 int nrowvars;
551 int startindex;
552 int size;
553
554 size = 10;
555 nrowvars = 0;
556 startindex = nstarted - 1;
557
558 SCIP_CALL( SCIPallocBufferArray(scip, vars, size) );
559 SCIP_CALL( SCIPallocBufferArray(scip, coefs, size) );
560
561 /* search for the (nstarted - nfinished) jobs which are active at curtime */
562 while( nstarted - nfinished > nrowvars )
563 {
564 SCIP_VAR* var;
565 int endtime;
566 int duration;
567 int demand;
568 int varidx;
569
570 /* collect job information */
571 varidx = startindices[startindex];
572 assert(varidx >= 0 && varidx < consdata->nvars);
573
574 var = consdata->vars[varidx];
575 duration = consdata->durations[varidx];
576 demand = consdata->demands[varidx];
577 assert(var != NULL);
578
579 endtime = SCIPconvertRealToInt(scip, SCIPvarGetUbGlobal(var)) + duration;
580
581 /* check the end time of this job is larger than the curtime; in this case the job is still running */
582 if( endtime > curtime )
583 {
584 SCIP_VAR** binvars;
585 SCIP_Real* vals;
586 int nbinvars;
587 int start;
588 int end;
589 int b;
590
591 /* check if the linking constraints exists */
592 assert(SCIPexistsConsLinking(scip, var));
593 assert(SCIPgetConsLinking(scip, var) != NULL);
594 assert(SCIPgetConsLinking(scip, var) == consdata->linkingconss[varidx]);
595
596 /* collect linking constraint information */
597 SCIP_CALL( SCIPgetBinvarsLinking(scip, consdata->linkingconss[varidx], &binvars, &nbinvars) );
598 vals = SCIPgetValsLinking(scip, consdata->linkingconss[varidx]);
599
600 start = curtime - duration + 1;
601 end = MIN(curtime, endtime - duration);
602
603 for( b = 0; b < nbinvars; ++b )
604 {
605 if( vals[b] < start )
606 continue;
607
608 if( vals[b] > end )
609 break;
610
611 assert(binvars[b] != NULL);
612
613 /* ensure array proper array size */
614 if( size == *nvars )
615 {
616 size *= 2;
617 SCIP_CALL( SCIPreallocBufferArray(scip, vars, size) );
618 SCIP_CALL( SCIPreallocBufferArray(scip, coefs, size) );
619 }
620
621 (*vars)[*nvars] = binvars[b];
622 (*coefs)[*nvars] = demand;
623 (*nvars)++;
624 }
625 nrowvars++;
626 }
627
628 startindex--;
629 }
630
631 return SCIP_OKAY;
632}
633
634/** collect all integer variable which belong to jobs which can run at the point of interest */
635static
637 SCIP* scip, /**< SCIP data structure */
638 SCIP_CONSDATA* consdata, /**< constraint data */
639 SCIP_VAR*** activevars, /**< jobs that are currently running */
640 int* startindices, /**< permutation with rspect to the start times */
641 int curtime, /**< current point in time */
642 int nstarted, /**< number of jobs that start before the curtime or at curtime */
643 int nfinished, /**< number of jobs that finished before curtime or at curtime */
644 SCIP_Bool lower, /**< shall cuts be created due to lower or upper bounds? */
645 int* lhs /**< lhs for the new row sum of lbs + minoffset */
646 )
647{
648 SCIP_VAR* var;
649 int startindex;
650 int endtime;
651 int duration;
652 int starttime;
653
654 int varidx;
655 int sumofstarts;
656 int mindelta;
657 int counter;
658
659 assert(curtime >= consdata->hmin);
660 assert(curtime < consdata->hmax);
661
662 counter = 0;
663 sumofstarts = 0;
664
665 mindelta = INT_MAX;
666
667 startindex = nstarted - 1;
668
669 /* search for the (nstarted - nfinished) jobs which are active at curtime */
670 while( nstarted - nfinished > counter )
671 {
672 assert(startindex >= 0);
673
674 /* collect job information */
675 varidx = startindices[startindex];
676 assert(varidx >= 0 && varidx < consdata->nvars);
677
678 var = consdata->vars[varidx];
679 duration = consdata->durations[varidx];
680 assert(duration > 0);
681 assert(var != NULL);
682
683 if( lower )
685 else
687
688 endtime = MIN(starttime + duration, consdata->hmax);
689
690 /* check the end time of this job is larger than the curtime; in this case the job is still running */
691 if( endtime > curtime )
692 {
693 (*activevars)[counter] = var;
694 sumofstarts += starttime;
695 mindelta = MIN(mindelta, endtime - curtime); /* this amount of schifting holds for lb and ub */
696 counter++;
697 }
698
699 startindex--;
700 }
701
702 assert(mindelta > 0);
703 *lhs = lower ? sumofstarts + mindelta : sumofstarts - mindelta;
704
705 return SCIP_OKAY;
706}
707
708/** initialize the sorted event point arrays */
709static
711 SCIP* scip, /**< SCIP data structure */
712 int nvars, /**< number of start time variables (activities) */
713 SCIP_VAR** vars, /**< array of start time variables */
714 int* durations, /**< array of durations per start time variable */
715 int* starttimes, /**< array to store sorted start events */
716 int* endtimes, /**< array to store sorted end events */
717 int* startindices, /**< permutation with rspect to the start times */
718 int* endindices, /**< permutation with rspect to the end times */
719 SCIP_Bool local /**< shall local bounds be used */
720 )
721{
722 SCIP_VAR* var;
723 int j;
724
725 assert(vars != NULL || nvars == 0);
726
727 /* assign variables, start and endpoints to arrays */
728 for ( j = 0; j < nvars; ++j )
729 {
730 assert(vars != NULL);
731
732 var = vars[j];
733 assert(var != NULL);
734
735 if( local )
736 starttimes[j] = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var));
737 else
738 starttimes[j] = SCIPconvertRealToInt(scip, SCIPvarGetLbGlobal(var));
739
740 startindices[j] = j;
741
742 if( local )
743 endtimes[j] = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) + durations[j];
744 else
745 endtimes[j] = SCIPconvertRealToInt(scip, SCIPvarGetUbGlobal(var)) + durations[j];
746
747 endindices[j] = j;
748 }
749
750 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
751 SCIPsortIntInt(starttimes, startindices, j);
752 SCIPsortIntInt(endtimes, endindices, j);
753}
754
755/** initialize the sorted event point arrays w.r.t. the given primal solutions */
756static
758 SCIP* scip, /**< SCIP data structure */
759 SCIP_SOL* sol, /**< solution */
760 int nvars, /**< number of start time variables (activities) */
761 SCIP_VAR** vars, /**< array of start time variables */
762 int* durations, /**< array of durations per start time variable */
763 int* starttimes, /**< array to store sorted start events */
764 int* endtimes, /**< array to store sorted end events */
765 int* startindices, /**< permutation with rspect to the start times */
766 int* endindices /**< permutation with rspect to the end times */
767 )
768{
769 SCIP_VAR* var;
770 int j;
771
772 assert(vars != NULL || nvars == 0);
773
774 /* assign variables, start and endpoints to arrays */
775 for ( j = 0; j < nvars; ++j )
776 {
777 assert(vars != NULL);
778
779 var = vars[j];
780 assert(var != NULL);
781
782 starttimes[j] = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, var));
783 startindices[j] = j;
784
785 endtimes[j] = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, var)) + durations[j];
786 endindices[j] = j;
787 }
788
789 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
790 SCIPsortIntInt(starttimes, startindices, j);
791 SCIPsortIntInt(endtimes, endindices, j);
792}
793
794/** initialize the sorted event point arrays
795 *
796 * @todo Check the separation process!
797 */
798static
800 SCIP* scip, /**< SCIP data structure */
801 SCIP_CONSDATA* consdata, /**< constraint data */
802 SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
803 int* starttimes, /**< array to store sorted start events */
804 int* endtimes, /**< array to store sorted end events */
805 int* startindices, /**< permutation with rspect to the start times */
806 int* endindices, /**< permutation with rspect to the end times */
807 int* nvars, /**< number of variables that are integral */
808 SCIP_Bool lower /**< shall the constraints be derived for lower or upper bounds? */
809 )
810{
811 SCIP_VAR* var;
812 int tmpnvars;
813 int j;
814
815 tmpnvars = consdata->nvars;
816 *nvars = 0;
817
818 /* assign variables, start and endpoints to arrays */
819 for ( j = 0; j < tmpnvars; ++j )
820 {
821 var = consdata->vars[j];
822 assert(var != NULL);
823 assert(consdata->durations[j] > 0);
824 assert(consdata->demands[j] > 0);
825
826 if( lower )
827 {
828 /* only consider jobs that are at their lower or upper bound */
829 if( !SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, var))
830 || !SCIPisFeasEQ(scip, SCIPgetSolVal(scip, sol, var), SCIPvarGetLbLocal(var)) )
831 continue;
832
833 starttimes[*nvars] = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, var));
834 startindices[*nvars] = j;
835
836 endtimes[*nvars] = starttimes[*nvars] + consdata->durations[j];
837 endindices[*nvars] = j;
838
839 SCIPdebugMsg(scip, "%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
840 *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var),
841 consdata->durations[j],
842 starttimes[*nvars], starttimes[*nvars] + consdata->durations[startindices[*nvars]],
843 consdata->demands[startindices[*nvars]]);
844
845 (*nvars)++;
846 }
847 else
848 {
849 if( !SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, var))
850 || !SCIPisFeasEQ(scip, SCIPgetSolVal(scip, sol, var), SCIPvarGetUbLocal(var)) )
851 continue;
852
853 starttimes[*nvars] = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, var));
854 startindices[*nvars] = j;
855
856 endtimes[*nvars] = starttimes[*nvars] + consdata->durations[j];
857 endindices[*nvars] = j;
858
859 SCIPdebugMsg(scip, "%d: variable <%s>[%g,%g] (sol %g, duration %d) starttime %d, endtime = %d, demand = %d\n",
860 *nvars, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPgetSolVal(scip, sol, var),
861 consdata->durations[j],
862 starttimes[*nvars], starttimes[*nvars] + consdata->durations[startindices[*nvars]],
863 consdata->demands[startindices[*nvars]]);
864
865 (*nvars)++;
866 }
867 }
868
869 /* sort the arrays not-decreasing according to startsolvalues and endsolvalues (and sort the indices in the same way) */
870 SCIPsortIntInt(starttimes, startindices, *nvars);
871 SCIPsortIntInt(endtimes, endindices, *nvars);
872
873#ifdef SCIP_DEBUG
874 SCIPdebugMsg(scip, "sorted output %d\n", *nvars);
875
876 for ( j = 0; j < *nvars; ++j )
877 {
878 SCIPdebugMsg(scip, "%d: job[%d] starttime %d, endtime = %d, demand = %d\n", j,
879 startindices[j], starttimes[j], starttimes[j] + consdata->durations[startindices[j]],
880 consdata->demands[startindices[j]]);
881 }
882
883 for ( j = 0; j < *nvars; ++j )
884 {
885 SCIPdebugMsg(scip, "%d: job[%d] endtime %d, demand = %d\n", j, endindices[j], endtimes[j],
886 consdata->demands[endindices[j]]);
887 }
888#endif
889}
890
891#ifdef SCIP_STATISTIC
892/** this method checks for relevant intervals for energetic reasoning */
893static
894SCIP_RETCODE computeRelevantEnergyIntervals(
895 SCIP* scip, /**< SCIP data structure */
896 int nvars, /**< number of start time variables (activities) */
897 SCIP_VAR** vars, /**< array of start time variables */
898 int* durations, /**< array of durations */
899 int* demands, /**< array of demands */
900 int capacity, /**< cumulative capacity */
901 int hmin, /**< left bound of time axis to be considered (including hmin) */
902 int hmax, /**< right bound of time axis to be considered (not including hmax) */
903 int** timepoints, /**< array to store relevant points in time */
904 SCIP_Real** cumulativedemands, /**< array to store the estimated cumulative demand for each point in time */
905 int* ntimepoints, /**< pointer to store the number of timepoints */
906 int* maxdemand, /**< pointer to store maximum over all demands */
907 SCIP_Real* minfreecapacity /**< pointer to store the minimum free capacity */
908 )
909{
910 int* starttimes; /* stores when each job is starting */
911 int* endtimes; /* stores when each job ends */
912 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
913 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
914
915 SCIP_Real totaldemand;
916 int curtime; /* point in time which we are just checking */
917 int endindex; /* index of endsolvalues with: endsolvalues[endindex] > curtime */
918
919 int j;
920
921 assert( scip != NULL );
922 assert(durations != NULL);
923 assert(demands != NULL);
924 assert(capacity >= 0);
925
926 /* if no activities are associated with this cumulative then this constraint is redundant */
927 if( nvars == 0 )
928 return SCIP_OKAY;
929
930 assert(vars != NULL);
931
932 SCIP_CALL( SCIPallocBufferArray(scip, &starttimes, nvars) );
933 SCIP_CALL( SCIPallocBufferArray(scip, &endtimes, nvars) );
934 SCIP_CALL( SCIPallocBufferArray(scip, &startindices, nvars) );
935 SCIP_CALL( SCIPallocBufferArray(scip, &endindices, nvars) );
936
937 /* create event point arrays */
938 createSortedEventpoints(scip, nvars, vars, durations, starttimes, endtimes, startindices, endindices, TRUE);
939
940 endindex = 0;
941 totaldemand = 0.0;
942
943 *ntimepoints = 0;
944 (*timepoints)[0] = starttimes[0];
945 (*cumulativedemands)[0] = 0;
946 *maxdemand = 0;
947
948 /* check each startpoint of a job whether the capacity is kept or not */
949 for( j = 0; j < nvars; ++j )
950 {
951 int lct;
952 int idx;
953
954 curtime = starttimes[j];
955
956 if( curtime >= hmax )
957 break;
958
959 /* free all capacity usages of jobs the are no longer running */
960 while( endindex < nvars && endtimes[endindex] <= curtime )
961 {
962 int est;
963
964 if( (*timepoints)[*ntimepoints] < endtimes[endindex] )
965 {
966 (*ntimepoints)++;
967 (*timepoints)[*ntimepoints] = endtimes[endindex];
968 (*cumulativedemands)[*ntimepoints] = 0;
969 }
970
971 idx = endindices[endindex];
973 totaldemand -= (SCIP_Real) demands[idx] * durations[idx] / (endtimes[endindex] - est);
974 endindex++;
975
976 (*cumulativedemands)[*ntimepoints] = totaldemand;
977 }
978
979 idx = startindices[j];
980 lct = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[idx]) + durations[idx]);
981 totaldemand += (SCIP_Real) demands[idx] * durations[idx] / (lct - starttimes[j]);
982
983 if( (*timepoints)[*ntimepoints] < curtime )
984 {
985 (*ntimepoints)++;
986 (*timepoints)[*ntimepoints] = curtime;
987 (*cumulativedemands)[*ntimepoints] = 0;
988 }
989
990 (*cumulativedemands)[*ntimepoints] = totaldemand;
991
992 /* add the relative capacity requirements for all job which start at the curtime */
993 while( j+1 < nvars && starttimes[j+1] == curtime )
994 {
995 ++j;
996 idx = startindices[j];
997 lct = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[idx]) + durations[idx]);
998 totaldemand += (SCIP_Real) demands[idx] * durations[idx] / (lct - starttimes[j]);
999
1000 (*cumulativedemands)[*ntimepoints] = totaldemand;
1001 }
1002 } /*lint --e{850}*/
1003
1004 /* free all capacity usages of jobs that are no longer running */
1005 while( endindex < nvars/* && endtimes[endindex] < hmax*/)
1006 {
1007 int est;
1008 int idx;
1009
1010 if( (*timepoints)[*ntimepoints] < endtimes[endindex] )
1011 {
1012 (*ntimepoints)++;
1013 (*timepoints)[*ntimepoints] = endtimes[endindex];
1014 (*cumulativedemands)[*ntimepoints] = 0;
1015 }
1016
1017 idx = endindices[endindex];
1018 est = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[idx]));
1019 totaldemand -= (SCIP_Real) demands[idx] * durations[idx] / (endtimes[endindex] - est);
1020 (*cumulativedemands)[*ntimepoints] = totaldemand;
1021
1022 ++endindex;
1023 }
1024
1025 (*ntimepoints)++;
1026 /* compute minimum free capacity */
1027 (*minfreecapacity) = INT_MAX;
1028 for( j = 0; j < *ntimepoints; ++j )
1029 {
1030 if( (*timepoints)[j] >= hmin && (*timepoints)[j] < hmax )
1031 *minfreecapacity = MIN( *minfreecapacity, (SCIP_Real)capacity - (*cumulativedemands)[j] );
1032 }
1033
1034 /* free buffer arrays */
1035 SCIPfreeBufferArray(scip, &endindices);
1036 SCIPfreeBufferArray(scip, &startindices);
1037 SCIPfreeBufferArray(scip, &endtimes);
1038 SCIPfreeBufferArray(scip, &starttimes);
1039
1040 return SCIP_OKAY;
1041}
1042
1043/** evaluates the cumulativeness and disjointness factor of a cumulative constraint */
1044static
1045SCIP_RETCODE evaluateCumulativeness(
1046 SCIP* scip, /**< pointer to scip */
1047 SCIP_CONS* cons /**< cumulative constraint */
1048 )
1049{
1050 SCIP_CONSDATA* consdata;
1051 int nvars;
1052 int v;
1053 int capacity;
1054
1055 /* output values: */
1056 SCIP_Real disjfactor2; /* (peak-capacity)/capacity * (large demands/nvars_t) */
1057 SCIP_Real cumfactor1;
1058 SCIP_Real resstrength1; /* overall strength */
1059 SCIP_Real resstrength2; /* timepoint wise maximum */
1060
1061 /* helpful variables: */
1062 SCIP_Real globalpeak;
1063 SCIP_Real globalmaxdemand;
1064
1065 /* get constraint data structure */
1066 consdata = SCIPconsGetData(cons);
1067 assert(consdata != NULL);
1068
1069 nvars = consdata->nvars;
1070 capacity = consdata->capacity;
1071 globalpeak = 0.0;
1072 globalmaxdemand = 0.0;
1073
1074 disjfactor2 = 0.0;
1075 cumfactor1 = 0.0;
1076 resstrength2 = 0.0;
1077
1078 /* check each starting time (==each job, but inefficient) */
1079 for( v = 0; v < nvars; ++v )
1080 {
1081 SCIP_Real peak;
1082 SCIP_Real maxdemand;
1083 SCIP_Real deltademand;
1084 int ndemands;
1085 int nlarge;
1086
1087 int timepoint;
1088 int j;
1089 timepoint = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(consdata->vars[v]));
1090 peak = consdata->demands[v];
1091 ndemands = 1;
1092 maxdemand = 0;
1093 nlarge = 0;
1094
1095 if( consdata->demands[v] > capacity / 3 )
1096 nlarge++;
1097
1098 for( j = 0; j < nvars; ++j )
1099 {
1100 int lb;
1101
1102 if( j == v )
1103 continue;
1104
1105 maxdemand = 0.0;
1106 lb = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(consdata->vars[j]));
1107
1108 if( lb <= timepoint && lb + consdata->durations[j] > timepoint )
1109 {
1110 peak += consdata->demands[j];
1111 ndemands++;
1112
1113 if( consdata->demands[j] > consdata->capacity / 3 )
1114 nlarge++;
1115 }
1116 }
1117
1118 deltademand = (SCIP_Real)peak / (SCIP_Real)ndemands;
1119 globalpeak = MAX(globalpeak, peak);
1120 globalmaxdemand = MAX(globalmaxdemand, maxdemand);
1121
1122 if( peak > capacity )
1123 {
1124 disjfactor2 = MAX( disjfactor2, (peak-(SCIP_Real)capacity)/peak * (nlarge/(SCIP_Real)ndemands) );
1125 cumfactor1 = MAX( cumfactor1, (peak-capacity)/peak * (capacity-deltademand)/(SCIP_Real)capacity );
1126 resstrength2 = MAX(resstrength2, (capacity-maxdemand)/(peak-maxdemand) );
1127 }
1128 }
1129
1130 resstrength1 = (capacity-globalmaxdemand) / (globalpeak-globalmaxdemand);
1131
1132 consdata->maxpeak = SCIPconvertRealToInt(scip, globalpeak);
1133 consdata->disjfactor2 = disjfactor2;
1134 consdata->cumfactor1 = cumfactor1;
1135 consdata->resstrength2 = resstrength2;
1136 consdata->resstrength1 = resstrength1;
1137
1138 /* get estimated res strength */
1139 {
1140 int* timepoints;
1141 SCIP_Real* estimateddemands;
1142 int ntimepoints;
1143 int maxdemand;
1144 SCIP_Real minfreecapacity;
1145
1146 SCIP_CALL( SCIPallocBufferArray(scip, &timepoints, 2*nvars) );
1147 SCIP_CALL( SCIPallocBufferArray(scip, &estimateddemands, 2*nvars) );
1148
1149 ntimepoints = 0;
1150 minfreecapacity = INT_MAX;
1151
1152 SCIP_CALL( computeRelevantEnergyIntervals(scip, nvars, consdata->vars,
1153 consdata->durations, consdata->demands,
1154 capacity, consdata->hmin, consdata->hmax, &timepoints, &estimateddemands,
1155 &ntimepoints, &maxdemand, &minfreecapacity) );
1156
1157 /* free buffer arrays */
1158 SCIPfreeBufferArray(scip, &estimateddemands);
1159 SCIPfreeBufferArray(scip, &timepoints);
1160
1161 consdata->estimatedstrength = (SCIP_Real)(capacity - minfreecapacity) / (SCIP_Real) capacity;
1162 }
1163
1164 SCIPstatisticPrintf("cumulative constraint<%s>: DISJ1=%g, DISJ2=%g, CUM=%g, RS1 = %g, RS2 = %g, EST = %g\n",
1165 SCIPconsGetName(cons), consdata->disjfactor1, disjfactor2, cumfactor1, resstrength1, resstrength2,
1166 consdata->estimatedstrength);
1167
1168 return SCIP_OKAY;
1169}
1170#endif
1171
1172/** gets the active variables together with the constant */
1173static
1175 SCIP* scip, /**< SCIP data structure */
1176 SCIP_VAR** var, /**< pointer to store the active variable */
1177 int* scalar, /**< pointer to store the scalar */
1178 int* constant /**< pointer to store the constant */
1179 )
1180{
1181 if( !SCIPvarIsActive(*var) )
1182 {
1183 SCIP_Real realscalar;
1184 SCIP_Real realconstant;
1185
1186 realscalar = 1.0;
1187 realconstant = 0.0;
1188
1190
1191 /* transform variable to active variable */
1192 SCIP_CALL( SCIPgetProbvarSum(scip, var, &realscalar, &realconstant) );
1193 assert(!SCIPisZero(scip, realscalar));
1194 assert(SCIPvarIsActive(*var));
1195
1196 if( realconstant < 0.0 )
1197 (*constant) = -SCIPconvertRealToInt(scip, -realconstant);
1198 else
1199 (*constant) = SCIPconvertRealToInt(scip, realconstant);
1200
1201 if( realscalar < 0.0 )
1202 (*scalar) = -SCIPconvertRealToInt(scip, -realscalar);
1203 else
1204 (*scalar) = SCIPconvertRealToInt(scip, realscalar);
1205 }
1206 else
1207 {
1208 (*scalar) = 1;
1209 (*constant) = 0;
1210 }
1211
1212 assert(*scalar != 0);
1213
1214 return SCIP_OKAY;
1215}
1216
1217/** computes the total energy of all jobs */
1218static
1220 int* durations, /**< array of job durations */
1221 int* demands, /**< array of job demands */
1222 int njobs /**< number of jobs */
1223 )
1224{
1225 SCIP_Longint energy;
1226 int j;
1227
1228 energy = 0;
1229
1230 for( j = 0; j < njobs; ++j )
1231 energy += (SCIP_Longint) durations[j] * demands[j];
1232
1233 return energy;
1234}
1235
1236/**@} */
1237
1238/**@name Default method to solve a cumulative condition
1239 *
1240 * @{
1241 */
1242
1243/** setup and solve subscip to solve single cumulative condition */
1244static
1246 SCIP* subscip, /**< subscip data structure */
1247 SCIP_Real* objvals, /**< array of objective coefficients for each job (linear objective function), or NULL if none */
1248 int* durations, /**< array of durations */
1249 int* demands, /**< array of demands */
1250 int njobs, /**< number of jobs (activities) */
1251 int capacity, /**< cumulative capacity */
1252 int hmin, /**< left bound of time axis to be considered (including hmin) */
1253 int hmax, /**< right bound of time axis to be considered (not including hmax) */
1254 SCIP_Longint maxnodes, /**< maximum number of branch-and-bound nodes (-1: no limit) */
1255 SCIP_Real timelimit, /**< time limit for solving in seconds */
1256 SCIP_Real memorylimit, /**< memory limit for solving in mega bytes (MB) */
1257 SCIP_Real* ests, /**< array of earliest start times for each job */
1258 SCIP_Real* lsts, /**< array of latest start times for each job */
1259 SCIP_Bool* infeasible, /**< pointer to store if the subproblem was infeasible */
1260 SCIP_Bool* unbounded, /**< pointer to store if the problem is unbounded */
1261 SCIP_Bool* solved, /**< pointer to store if the problem is solved (to optimality) */
1262 SCIP_Bool* error /**< pointer to store if an error occurred */
1263 )
1264{
1265 SCIP_VAR** subvars;
1266 SCIP_CONS* cons;
1267
1268 char name[SCIP_MAXSTRLEN];
1269 int v;
1270 SCIP_RETCODE retcode;
1271
1272 assert(subscip != NULL);
1273
1274 /* copy all plugins */
1276
1277 /* create the subproblem */
1278 SCIP_CALL( SCIPcreateProbBasic(subscip, "cumulative") );
1279
1280 SCIP_CALL( SCIPallocBlockMemoryArray(subscip, &subvars, njobs) );
1281
1282 /* create for each job a start time variable */
1283 for( v = 0; v < njobs; ++v )
1284 {
1285 SCIP_Real objval;
1286
1287 /* construct variable name */
1288 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "job%d", v);
1289
1290 if( objvals == NULL )
1291 objval = 0.0;
1292 else
1293 objval = objvals[v];
1294
1295 SCIP_CALL( SCIPcreateVarBasic(subscip, &subvars[v], name, ests[v], lsts[v], objval, SCIP_VARTYPE_INTEGER) );
1296 SCIP_CALL( SCIPaddVar(subscip, subvars[v]) );
1297 }
1298
1299 /* create cumulative constraint */
1300 SCIP_CALL( SCIPcreateConsBasicCumulative(subscip, &cons, "cumulative",
1301 njobs, subvars, durations, demands, capacity) );
1302
1303 /* set effective horizon */
1304 SCIP_CALL( SCIPsetHminCumulative(subscip, cons, hmin) );
1305 SCIP_CALL( SCIPsetHmaxCumulative(subscip, cons, hmax) );
1306
1307 /* add cumulative constraint */
1308 SCIP_CALL( SCIPaddCons(subscip, cons) );
1309 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1310
1311 /* set CP solver settings
1312 *
1313 * @note This "meta" setting has to be set first since this call overwrite all parameters including for example the
1314 * time limit.
1315 */
1317
1318 /* do not abort subproblem on CTRL-C */
1319 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
1320
1321 /* disable output to console */
1322 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1323
1324 /* set limits for the subproblem */
1325 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", maxnodes) );
1326 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
1327 SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
1328
1329 /* forbid recursive call of heuristics and separators solving subMIPs */
1330 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
1331
1332 /* solve single cumulative constraint by branch and bound */
1333 retcode = SCIPsolve(subscip);
1334
1335 if( retcode != SCIP_OKAY )
1336 (*error) = TRUE;
1337 else
1338 {
1339 SCIPdebugMsg(subscip, "solved single cumulative condition with status %d\n", SCIPgetStatus(subscip));
1340
1341 /* evaluated solution status */
1342 switch( SCIPgetStatus(subscip) )
1343 {
1346 (*infeasible) = TRUE;
1347 (*solved) = TRUE;
1348 break;
1350 (*unbounded) = TRUE;
1351 (*solved) = TRUE;
1352 break;
1354 {
1355 SCIP_SOL* sol;
1356 SCIP_Real solval;
1357
1358 sol = SCIPgetBestSol(subscip);
1359 assert(sol != NULL);
1360
1361 for( v = 0; v < njobs; ++v )
1362 {
1363 solval = SCIPgetSolVal(subscip, sol, subvars[v]);
1364
1365 ests[v] = solval;
1366 lsts[v] = solval;
1367 }
1368 (*solved) = TRUE;
1369 break;
1370 }
1377 /* transfer the global bound changes */
1378 for( v = 0; v < njobs; ++v )
1379 {
1380 ests[v] = SCIPvarGetLbGlobal(subvars[v]);
1381 lsts[v] = SCIPvarGetUbGlobal(subvars[v]);
1382 }
1383 (*solved) = FALSE;
1384 break;
1385
1394 SCIPerrorMessage("invalid status code <%d>\n", SCIPgetStatus(subscip));
1395 return SCIP_INVALIDDATA;
1396 }
1397 }
1398
1399 /* release all variables */
1400 for( v = 0; v < njobs; ++v )
1401 {
1402 SCIP_CALL( SCIPreleaseVar(subscip, &subvars[v]) );
1403 }
1404
1405 SCIPfreeBlockMemoryArray(subscip, &subvars, njobs);
1406
1407 return SCIP_OKAY;
1408}
1409
1410/** solve single cumulative condition using SCIP and a single cumulative constraint */
1411static
1412SCIP_DECL_SOLVECUMULATIVE(solveCumulativeViaScipCp)
1413{
1414 SCIP* subscip;
1415
1416 SCIP_RETCODE retcode;
1417
1418 assert(njobs > 0);
1419
1420 (*solved) = FALSE;
1421 (*infeasible) = FALSE;
1422 (*unbounded) = FALSE;
1423 (*error) = FALSE;
1424
1425 SCIPdebugMessage("solve independent cumulative condition with %d variables\n", njobs);
1426
1427 /* initialize the sub-problem */
1428 SCIP_CALL( SCIPcreate(&subscip) );
1429
1430 /* create and solve the subproblem. catch possible errors */
1431 retcode = setupAndSolveCumulativeSubscip(subscip, objvals, durations, demands,
1432 njobs, capacity, hmin, hmax,
1433 maxnodes, timelimit, memorylimit,
1434 ests, lsts,
1435 infeasible, unbounded, solved, error);
1436
1437 /* free the subscip in any case */
1438 SCIP_CALL( SCIPfree(&subscip) );
1439
1440 SCIP_CALL( retcode );
1441
1442 return SCIP_OKAY;
1443}
1444
1445#if 0
1446/** solve single cumulative condition using SCIP and the time indexed formulation */
1447static
1448SCIP_DECL_SOLVECUMULATIVE(solveCumulativeViaScipMip)
1449{
1450 SCIP* subscip;
1451 SCIP_VAR*** binvars;
1452 SCIP_RETCODE retcode;
1453 char name[SCIP_MAXSTRLEN];
1454 int minest;
1455 int maxlct;
1456 int t;
1457 int v;
1458
1459 assert(njobs > 0);
1460
1461 (*solved) = FALSE;
1462 (*infeasible) = FALSE;
1463 (*unbounded) = FALSE;
1464 (*error) = FALSE;
1465
1466 SCIPdebugMsg(scip, "solve independent cumulative condition with %d variables\n", njobs);
1467
1468 /* initialize the sub-problem */
1469 SCIP_CALL( SCIPcreate(&subscip) );
1470
1471 /* copy all plugins */
1473
1474 /* create the subproblem */
1475 SCIP_CALL( SCIPcreateProbBasic(subscip, "cumulative") );
1476
1477 SCIP_CALL( SCIPallocBufferArray(subscip, &binvars, njobs) );
1478
1479 minest = INT_MAX;
1480 maxlct = INT_MIN;
1481
1482 /* create for each job and time step a binary variable which is one if this jobs starts at this time point and a set
1483 * partitioning constrain which forces that job starts
1484 */
1485 for( v = 0; v < njobs; ++v )
1486 {
1487 SCIP_CONS* cons;
1488 SCIP_Real objval;
1489 int timeinterval;
1490 int est;
1491 int lst;
1492
1493 if( objvals == NULL )
1494 objval = 0.0;
1495 else
1496 objval = objvals[v];
1497
1498 est = ests[v];
1499 lst = lsts[v];
1500
1501 /* compute number of possible start points */
1502 timeinterval = lst - est + 1;
1503 assert(timeinterval > 0);
1504
1505 /* compute the smallest earliest start time and largest latest completion time */
1506 minest = MIN(minest, est);
1507 maxlct = MAX(maxlct, lst + durations[v]);
1508
1509 /* construct constraint name */
1510 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d", v);
1511
1512 SCIP_CALL( SCIPcreateConsBasicSetpart(subscip, &cons, name, 0, NULL) );
1513
1514 SCIP_CALL( SCIPallocBufferArray(subscip, &binvars[v], timeinterval) );
1515
1516 for( t = 0; t < timeinterval; ++t )
1517 {
1518 SCIP_VAR* binvar;
1519
1520 /* construct varibale name */
1521 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "job_%d_time_%d", v, t + est);
1522
1523 SCIP_CALL( SCIPcreateVarBasic(subscip, &binvar, name, 0.0, 1.0, objval, SCIP_VARTYPE_BINARY) );
1524 SCIP_CALL( SCIPaddVar(subscip, binvar) );
1525
1526 /* add binary varibale to the set partitioning constraint which ensures that the job is started */
1527 SCIP_CALL( SCIPaddCoefSetppc(subscip, cons, binvar) );
1528
1529 binvars[v][t] = binvar;
1530 }
1531
1532 /* add and release the set partitioning constraint */
1533 SCIP_CALL( SCIPaddCons(subscip, cons) );
1534 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1535 }
1536
1537 /* adjusted the smallest earliest start time and the largest latest completion time with the effective horizon */
1538 hmin = MAX(hmin, minest);
1539 hmax = MIN(hmax, maxlct);
1540 assert(hmin > INT_MIN);
1541 assert(hmax < INT_MAX);
1542 assert(hmin < hmax);
1543
1544 /* create for each time a knapsack constraint which ensures that the resource capacity is not exceeded */
1545 for( t = hmin; t < hmax; ++t )
1546 {
1547 SCIP_CONS* cons;
1548
1549 /* construct constraint name */
1550 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "time_%d", t);
1551
1552 /* create an empty knapsack constraint */
1553 SCIP_CALL( SCIPcreateConsBasicKnapsack(subscip, &cons, name, 0, NULL, NULL, (SCIP_Longint)capacity) );
1554
1555 /* add all jobs which potentially can be processed at that time point */
1556 for( v = 0; v < njobs; ++v )
1557 {
1558 int duration;
1559 int demand;
1560 int start;
1561 int end;
1562 int est;
1563 int lst;
1564 int k;
1565
1566 est = ests[v];
1567 lst = lsts[v] ;
1568
1569 duration = durations[v];
1570 assert(duration > 0);
1571
1572 /* check if the varibale is processed potentially at time point t */
1573 if( t < est || t >= lst + duration )
1574 continue;
1575
1576 demand = demands[v];
1577 assert(demand >= 0);
1578
1579 start = MAX(t - duration + 1, est);
1580 end = MIN(t, lst);
1581
1582 assert(start <= end);
1583
1584 for( k = start; k <= end; ++k )
1585 {
1586 assert(binvars[v][k] != NULL);
1587 SCIP_CALL( SCIPaddCoefKnapsack(subscip, cons, binvars[v][k], (SCIP_Longint) demand) );
1588 }
1589 }
1590
1591 /* add and release the knapsack constraint */
1592 SCIP_CALL( SCIPaddCons(subscip, cons) );
1593 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1594 }
1595
1596 /* do not abort subproblem on CTRL-C */
1597 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
1598
1599 /* disable output to console */
1600 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1601
1602 /* set limits for the subproblem */
1603 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", maxnodes) );
1604 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
1605 SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
1606
1607 /* solve single cumulative constraint by branch and bound */
1608 retcode = SCIPsolve(subscip);
1609
1610 if( retcode != SCIP_OKAY )
1611 (*error) = TRUE;
1612 else
1613 {
1614 SCIPdebugMsg(scip, "solved single cumulative condition with status %d\n", SCIPgetStatus(subscip));
1615
1616 /* evaluated solution status */
1617 switch( SCIPgetStatus(subscip) )
1618 {
1621 (*infeasible) = TRUE;
1622 (*solved) = TRUE;
1623 break;
1625 (*unbounded) = TRUE;
1626 (*solved) = TRUE;
1627 break;
1629 {
1630 SCIP_SOL* sol;
1631
1632 sol = SCIPgetBestSol(subscip);
1633 assert(sol != NULL);
1634
1635 for( v = 0; v < njobs; ++v )
1636 {
1637 int timeinterval;
1638 int est;
1639 int lst;
1640
1641 est = ests[v];
1642 lst = lsts[v];
1643
1644 /* compute number of possible start points */
1645 timeinterval = lst - est + 1;
1646
1647 /* check which binary varibale is set to one */
1648 for( t = 0; t < timeinterval; ++t )
1649 {
1650 if( SCIPgetSolVal(subscip, sol, binvars[v][t]) > 0.5 )
1651 {
1652 ests[v] = est + t;
1653 lsts[v] = est + t;
1654 break;
1655 }
1656 }
1657 }
1658
1659 (*solved) = TRUE;
1660 break;
1661 }
1667 /* transfer the global bound changes */
1668 for( v = 0; v < njobs; ++v )
1669 {
1670 int timeinterval;
1671 int est;
1672 int lst;
1673
1674 est = ests[v];
1675 lst = lsts[v];
1676
1677 /* compute number of possible start points */
1678 timeinterval = lst - est + 1;
1679
1680 /* check which binary varibale is the first binary varibale which is not globally fixed to zero */
1681 for( t = 0; t < timeinterval; ++t )
1682 {
1683 if( SCIPvarGetUbGlobal(binvars[v][t]) > 0.5 )
1684 {
1685 ests[v] = est + t;
1686 break;
1687 }
1688 }
1689
1690 /* check which binary varibale is the last binary varibale which is not globally fixed to zero */
1691 for( t = timeinterval - 1; t >= 0; --t )
1692 {
1693 if( SCIPvarGetUbGlobal(binvars[v][t]) > 0.5 )
1694 {
1695 lsts[v] = est + t;
1696 break;
1697 }
1698 }
1699 }
1700 (*solved) = FALSE;
1701 break;
1702
1708 SCIPerrorMessage("invalid status code <%d>\n", SCIPgetStatus(subscip));
1709 return SCIP_INVALIDDATA;
1710 }
1711 }
1712
1713 /* release all variables */
1714 for( v = 0; v < njobs; ++v )
1715 {
1716 int timeinterval;
1717 int est;
1718 int lst;
1719
1720 est = ests[v];
1721 lst = lsts[v];
1722
1723 /* compute number of possible start points */
1724 timeinterval = lst - est + 1;
1725
1726 for( t = 0; t < timeinterval; ++t )
1727 {
1728 SCIP_CALL( SCIPreleaseVar(subscip, &binvars[v][t]) );
1729 }
1730 SCIPfreeBufferArray(subscip, &binvars[v]);
1731 }
1732
1733 SCIPfreeBufferArray(subscip, &binvars);
1734
1735 SCIP_CALL( SCIPfree(&subscip) );
1736
1737 return SCIP_OKAY;
1738}
1739#endif
1740
1741/**@} */
1742
1743/**@name Constraint handler data
1744 *
1745 * Method used to create and free the constraint handler data when including and removing the cumulative constraint
1746 * handler.
1747 *
1748 * @{
1749 */
1750
1751/** creates constaint handler data for cumulative constraint handler */
1752static
1754 SCIP* scip, /**< SCIP data structure */
1755 SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
1756 SCIP_EVENTHDLR* eventhdlr /**< event handler */
1757 )
1758{
1759 /* create precedence constraint handler data */
1760 assert(scip != NULL);
1761 assert(conshdlrdata != NULL);
1762 assert(eventhdlr != NULL);
1763
1764 SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
1765
1766 /* set event handler for checking if bounds of start time variables are tighten */
1767 (*conshdlrdata)->eventhdlr = eventhdlr;
1768
1769 /* set default methed for solving single cumulative conditions using SCIP and a CP model */
1770 (*conshdlrdata)->solveCumulative = solveCumulativeViaScipCp;
1771
1772#ifdef SCIP_STATISTIC
1773 (*conshdlrdata)->nlbtimetable = 0;
1774 (*conshdlrdata)->nubtimetable = 0;
1775 (*conshdlrdata)->ncutofftimetable = 0;
1776 (*conshdlrdata)->nlbedgefinder = 0;
1777 (*conshdlrdata)->nubedgefinder = 0;
1778 (*conshdlrdata)->ncutoffedgefinder = 0;
1779 (*conshdlrdata)->ncutoffoverload = 0;
1780 (*conshdlrdata)->ncutoffoverloadTTEF = 0;
1781
1782 (*conshdlrdata)->nirrelevantjobs = 0;
1783 (*conshdlrdata)->nalwaysruns = 0;
1784 (*conshdlrdata)->nremovedlocks = 0;
1785 (*conshdlrdata)->ndualfixs = 0;
1786 (*conshdlrdata)->ndecomps = 0;
1787 (*conshdlrdata)->ndualbranchs = 0;
1788 (*conshdlrdata)->nallconsdualfixs = 0;
1789 (*conshdlrdata)->naddedvarbounds = 0;
1790 (*conshdlrdata)->naddeddisjunctives = 0;
1791#endif
1792
1793 return SCIP_OKAY;
1794}
1795
1796/** frees constraint handler data for logic or constraint handler */
1797static
1799 SCIP* scip, /**< SCIP data structure */
1800 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
1801 )
1802{
1803 assert(conshdlrdata != NULL);
1804 assert(*conshdlrdata != NULL);
1805
1806 SCIPfreeBlockMemory(scip, conshdlrdata);
1807}
1808
1809/**@} */
1810
1811
1812/**@name Constraint data methods
1813 *
1814 * @{
1815 */
1816
1817/** catches bound change events for all variables in transformed cumulative constraint */
1818static
1820 SCIP* scip, /**< SCIP data structure */
1821 SCIP_CONSDATA* consdata, /**< cumulative constraint data */
1822 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
1823 )
1824{
1825 int v;
1826
1827 assert(scip != NULL);
1828 assert(consdata != NULL);
1829 assert(eventhdlr != NULL);
1830
1831 /* catch event for every single variable */
1832 for( v = 0; v < consdata->nvars; ++v )
1833 {
1834 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[v],
1835 SCIP_EVENTTYPE_BOUNDTIGHTENED, eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
1836 }
1837
1838 return SCIP_OKAY;
1839}
1840
1841/** drops events for variable at given position */
1842static
1844 SCIP* scip, /**< SCIP data structure */
1845 SCIP_CONSDATA* consdata, /**< cumulative constraint data */
1846 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1847 int pos /**< array position of variable to catch bound change events for */
1848 )
1849{
1850 assert(scip != NULL);
1851 assert(consdata != NULL);
1852 assert(eventhdlr != NULL);
1853 assert(0 <= pos && pos < consdata->nvars);
1854 assert(consdata->vars[pos] != NULL);
1855
1856 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos],
1857 SCIP_EVENTTYPE_BOUNDTIGHTENED, eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
1858
1859 return SCIP_OKAY;
1860}
1861
1862/** drops bound change events for all variables in transformed linear constraint */
1863static
1865 SCIP* scip, /**< SCIP data structure */
1866 SCIP_CONSDATA* consdata, /**< linear constraint data */
1867 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
1868 )
1869{
1870 int v;
1871
1872 assert(scip != NULL);
1873 assert(consdata != NULL);
1874
1875 /* drop event of every single variable */
1876 for( v = 0; v < consdata->nvars; ++v )
1877 {
1878 SCIP_CALL( consdataDropEvents(scip, consdata, eventhdlr, v) );
1879 }
1880
1881 return SCIP_OKAY;
1882}
1883
1884/** initialize variable lock data structure */
1885static
1887 SCIP_CONSDATA* consdata, /**< constraint data */
1888 SCIP_Bool locked /**< should the variable be locked? */
1889 )
1890{
1891 int nvars;
1892 int v;
1893
1894 nvars = consdata->nvars;
1895
1896 /* initialize locking arrays */
1897 for( v = 0; v < nvars; ++v )
1898 {
1899 consdata->downlocks[v] = locked;
1900 consdata->uplocks[v] = locked;
1901 }
1902}
1903
1904/** creates constraint data of cumulative constraint */
1905static
1907 SCIP* scip, /**< SCIP data structure */
1908 SCIP_CONSDATA** consdata, /**< pointer to consdata */
1909 SCIP_VAR** vars, /**< array of integer variables */
1910 SCIP_CONS** linkingconss, /**< array of linking constraints for the integer variables, or NULL */
1911 int* durations, /**< array containing corresponding durations */
1912 int* demands, /**< array containing corresponding demands */
1913 int nvars, /**< number of variables */
1914 int capacity, /**< available cumulative capacity */
1915 int hmin, /**< left bound of time axis to be considered (including hmin) */
1916 int hmax, /**< right bound of time axis to be considered (not including hmax) */
1917 SCIP_Bool check /**< is the corresponding constraint a check constraint */
1918 )
1919{
1920 int v;
1921
1922 assert(scip != NULL);
1923 assert(consdata != NULL);
1924 assert(vars != NULL || nvars > 0);
1925 assert(demands != NULL);
1926 assert(durations != NULL);
1927 assert(capacity >= 0);
1928 assert(hmin >= 0);
1929 assert(hmin < hmax);
1930
1931 /* create constraint data */
1932 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
1933
1934 (*consdata)->hmin = hmin;
1935 (*consdata)->hmax = hmax;
1936
1937 (*consdata)->capacity = capacity;
1938 (*consdata)->demandrows = NULL;
1939 (*consdata)->demandrowssize = 0;
1940 (*consdata)->ndemandrows = 0;
1941 (*consdata)->scoverrows = NULL;
1942 (*consdata)->nscoverrows = 0;
1943 (*consdata)->scoverrowssize = 0;
1944 (*consdata)->bcoverrows = NULL;
1945 (*consdata)->nbcoverrows = 0;
1946 (*consdata)->bcoverrowssize = 0;
1947 (*consdata)->nvars = nvars;
1948 (*consdata)->varssize = nvars;
1949 (*consdata)->signature = 0;
1950 (*consdata)->validsignature = FALSE;
1951 (*consdata)->normalized = FALSE;
1952 (*consdata)->covercuts = FALSE;
1953 (*consdata)->propagated = FALSE;
1954 (*consdata)->varbounds = FALSE;
1955 (*consdata)->triedsolving = FALSE;
1956
1957 if( nvars > 0 )
1958 {
1959 assert(vars != NULL); /* for flexelint */
1960
1961 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
1962 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->demands, demands, nvars) );
1963 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->durations, durations, nvars) );
1964 (*consdata)->linkingconss = NULL;
1965
1966 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->downlocks, nvars) );
1967 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->uplocks, nvars) );
1968
1969 /* initialize variable lock data structure; the locks are only used if the constraint is a check constraint */
1970 initializeLocks(*consdata, check);
1971
1972 if( linkingconss != NULL )
1973 {
1974 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->linkingconss, linkingconss, nvars) );
1975 }
1976
1977 /* transform variables, if they are not yet transformed */
1978 if( SCIPisTransformed(scip) )
1979 {
1980 SCIPdebugMsg(scip, "get tranformed variables and constraints\n");
1981
1982 /* get transformed variables and do NOT captures these */
1983 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
1984
1985 /* multi-aggregated variables cannot be replaced by active variable; therefore we mark all variables for not
1986 * been multi-aggregated
1987 */
1988 for( v = 0; v < nvars; ++v )
1989 {
1990 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[v]) );
1991 }
1992
1993 if( linkingconss != NULL )
1994 {
1995 /* get transformed constraints and captures these */
1996 SCIP_CALL( SCIPtransformConss(scip, (*consdata)->nvars, (*consdata)->linkingconss, (*consdata)->linkingconss) );
1997
1998 for( v = 0; v < nvars; ++v )
1999 assert(SCIPgetConsLinking(scip, (*consdata)->vars[v]) == (*consdata)->linkingconss[v]);
2000 }
2001 }
2002
2003#ifndef NDEBUG
2004 /* only binary and integer variables can be used in cumulative constraints
2005 * for fractional variable values, the constraint cannot be checked
2006 */
2007 for( v = 0; v < (*consdata)->nvars; ++v )
2008 assert(SCIPvarGetType((*consdata)->vars[v]) <= SCIP_VARTYPE_INTEGER);
2009#endif
2010 }
2011 else
2012 {
2013 (*consdata)->vars = NULL;
2014 (*consdata)->downlocks = NULL;
2015 (*consdata)->uplocks = NULL;
2016 (*consdata)->demands = NULL;
2017 (*consdata)->durations = NULL;
2018 (*consdata)->linkingconss = NULL;
2019 }
2020
2021 /* initialize values for running propagation algorithms efficiently */
2022 (*consdata)->resstrength1 = -1.0;
2023 (*consdata)->resstrength2 = -1.0;
2024 (*consdata)->cumfactor1 = -1.0;
2025 (*consdata)->disjfactor1 = -1.0;
2026 (*consdata)->disjfactor2 = -1.0;
2027 (*consdata)->estimatedstrength = -1.0;
2028
2029 SCIPstatistic( (*consdata)->maxpeak = -1 );
2030
2031 return SCIP_OKAY;
2032}
2033
2034/** releases LP rows of constraint data and frees rows array */
2035static
2037 SCIP* scip, /**< SCIP data structure */
2038 SCIP_CONSDATA** consdata /**< constraint data */
2039 )
2040{
2041 int r;
2042
2043 assert(consdata != NULL);
2044 assert(*consdata != NULL);
2045
2046 for( r = 0; r < (*consdata)->ndemandrows; ++r )
2047 {
2048 assert((*consdata)->demandrows[r] != NULL);
2049 SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->demandrows[r]) );
2050 }
2051
2052 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->demandrows, (*consdata)->demandrowssize);
2053
2054 (*consdata)->ndemandrows = 0;
2055 (*consdata)->demandrowssize = 0;
2056
2057 /* free rows of cover cuts */
2058 for( r = 0; r < (*consdata)->nscoverrows; ++r )
2059 {
2060 assert((*consdata)->scoverrows[r] != NULL);
2061 SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->scoverrows[r]) );
2062 }
2063
2064 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->scoverrows, (*consdata)->scoverrowssize);
2065
2066 (*consdata)->nscoverrows = 0;
2067 (*consdata)->scoverrowssize = 0;
2068
2069 for( r = 0; r < (*consdata)->nbcoverrows; ++r )
2070 {
2071 assert((*consdata)->bcoverrows[r] != NULL);
2072 SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->bcoverrows[r]) );
2073 }
2074
2075 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->bcoverrows, (*consdata)->bcoverrowssize);
2076
2077 (*consdata)->nbcoverrows = 0;
2078 (*consdata)->bcoverrowssize = 0;
2079
2080 (*consdata)->covercuts = FALSE;
2081
2082 return SCIP_OKAY;
2083}
2084
2085/** frees a cumulative constraint data */
2086static
2088 SCIP* scip, /**< SCIP data structure */
2089 SCIP_CONSDATA** consdata /**< pointer to linear constraint data */
2090 )
2091{
2092 int varssize;
2093 int nvars;
2094
2095 assert(consdata != NULL);
2096 assert(*consdata != NULL);
2097
2098 nvars = (*consdata)->nvars;
2099 varssize = (*consdata)->varssize;
2100
2101 if( varssize > 0 )
2102 {
2103 int v;
2104
2105 /* release and free the rows */
2106 SCIP_CALL( consdataFreeRows(scip, consdata) );
2107
2108 /* release the linking constraints if they were generated */
2109 if( (*consdata)->linkingconss != NULL )
2110 {
2111 for( v = nvars-1; v >= 0; --v )
2112 {
2113 assert((*consdata)->linkingconss[v] != NULL );
2114 SCIP_CALL( SCIPreleaseCons(scip, &(*consdata)->linkingconss[v]) );
2115 }
2116
2117 SCIPfreeBlockMemoryArray(scip, &(*consdata)->linkingconss, varssize);
2118 }
2119
2120 /* free arrays */
2121 SCIPfreeBlockMemoryArray(scip, &(*consdata)->downlocks, varssize);
2122 SCIPfreeBlockMemoryArray(scip, &(*consdata)->uplocks, varssize);
2123 SCIPfreeBlockMemoryArray(scip, &(*consdata)->durations, varssize);
2124 SCIPfreeBlockMemoryArray(scip, &(*consdata)->demands, varssize);
2125 SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, varssize);
2126 }
2127
2128 /* free memory */
2129 SCIPfreeBlockMemory(scip, consdata);
2130
2131 return SCIP_OKAY;
2132}
2133
2134/** prints cumulative constraint to file stream */
2135static
2137 SCIP* scip, /**< SCIP data structure */
2138 SCIP_CONSDATA* consdata, /**< cumulative constraint data */
2139 FILE* file /**< output file (or NULL for standard output) */
2140 )
2141{
2142 int v;
2143
2144 assert(consdata != NULL);
2145
2146 /* print coefficients */
2147 SCIPinfoMessage( scip, file, "cumulative(");
2148
2149 for( v = 0; v < consdata->nvars; ++v )
2150 {
2151 assert(consdata->vars[v] != NULL);
2152 if( v > 0 )
2153 SCIPinfoMessage(scip, file, ", ");
2154 SCIPinfoMessage(scip, file, "<%s>[%g,%g](%d)[%d]", SCIPvarGetName(consdata->vars[v]),
2155 SCIPvarGetLbGlobal(consdata->vars[v]), SCIPvarGetUbGlobal(consdata->vars[v]),
2156 consdata->durations[v], consdata->demands[v]);
2157 }
2158 SCIPinfoMessage(scip, file, ")[%d,%d) <= %d", consdata->hmin, consdata->hmax, consdata->capacity);
2159}
2160
2161/** deletes coefficient at given position from constraint data */
2162static
2164 SCIP* scip, /**< SCIP data structure */
2165 SCIP_CONSDATA* consdata, /**< cumulative constraint data */
2166 SCIP_CONS* cons, /**< knapsack constraint */
2167 int pos /**< position of coefficient to delete */
2168 )
2169{
2170 SCIP_CONSHDLR* conshdlr;
2171 SCIP_CONSHDLRDATA* conshdlrdata;
2172
2173 assert(scip != NULL);
2174 assert(consdata != NULL);
2175 assert(cons != NULL);
2176 assert(SCIPconsIsTransformed(cons));
2177 assert(!SCIPinProbing(scip));
2178
2179 SCIPdebugMsg(scip, "cumulative constraint <%s>: remove variable <%s>\n",
2180 SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[pos]));
2181
2182 /* remove the rounding locks for the deleted variable */
2183 SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, consdata->downlocks[pos], consdata->uplocks[pos]) );
2184
2185 consdata->downlocks[pos] = FALSE;
2186 consdata->uplocks[pos] = FALSE;
2187
2188 if( consdata->linkingconss != NULL )
2189 {
2190 SCIP_CALL( SCIPreleaseCons(scip, &consdata->linkingconss[pos]) );
2191 }
2192
2193 /* get event handler */
2194 conshdlr = SCIPconsGetHdlr(cons);
2195 assert(conshdlr != NULL);
2196 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2197 assert(conshdlrdata != NULL);
2198 assert(conshdlrdata->eventhdlr != NULL);
2199
2200 /* drop events */
2201 SCIP_CALL( consdataDropEvents(scip, consdata, conshdlrdata->eventhdlr, pos) );
2202
2203 SCIPdebugMsg(scip, "remove variable <%s>[%g,%g] from cumulative constraint <%s>\n",
2204 SCIPvarGetName(consdata->vars[pos]), SCIPvarGetLbGlobal(consdata->vars[pos]), SCIPvarGetUbGlobal(consdata->vars[pos]), SCIPconsGetName(cons));
2205
2206 /* in case the we did not remove the variable in the last slot of the arrays we move the current last to this
2207 * position
2208 */
2209 if( pos != consdata->nvars - 1 )
2210 {
2211 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
2212 consdata->downlocks[pos] = consdata->downlocks[consdata->nvars-1];
2213 consdata->uplocks[pos] = consdata->uplocks[consdata->nvars-1];
2214 consdata->demands[pos] = consdata->demands[consdata->nvars-1];
2215 consdata->durations[pos] = consdata->durations[consdata->nvars-1];
2216
2217 if( consdata->linkingconss != NULL )
2218 {
2219 consdata->linkingconss[pos]= consdata->linkingconss[consdata->nvars-1];
2220 }
2221 }
2222
2223 consdata->nvars--;
2224 consdata->validsignature = FALSE;
2225 consdata->normalized = FALSE;
2226
2227 return SCIP_OKAY;
2228}
2229
2230/** collect linking constraints for each integer variable */
2231static
2233 SCIP* scip, /**< SCIP data structure */
2234 SCIP_CONSDATA* consdata /**< pointer to consdata */
2235 )
2236{
2237 int nvars;
2238 int v;
2239
2240 assert(scip != NULL);
2241 assert(consdata != NULL);
2242
2243 nvars = consdata->nvars;
2244 assert(nvars > 0);
2245 assert(consdata->linkingconss == NULL);
2246
2247 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->linkingconss, consdata->varssize) );
2248
2249 for( v = 0; v < nvars; ++v )
2250 {
2251 SCIP_CONS* cons;
2252 SCIP_VAR* var;
2253
2254 var = consdata->vars[v];
2255 assert(var != NULL);
2256
2257 SCIPdebugMsg(scip, "linking constraint (%d of %d) for variable <%s>\n", v+1, nvars, SCIPvarGetName(var));
2258
2259 /* create linking constraint if it does not exist yet */
2260 if( !SCIPexistsConsLinking(scip, var) )
2261 {
2262 char name[SCIP_MAXSTRLEN];
2263
2264 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "link(%s)", SCIPvarGetName(var));
2265
2266 /* creates and captures an linking constraint */
2267 SCIP_CALL( SCIPcreateConsLinking(scip, &cons, name, var, NULL, 0, 0,
2268 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE /*TRUE*/, FALSE) );
2269 SCIP_CALL( SCIPaddCons(scip, cons) );
2270 consdata->linkingconss[v] = cons;
2271 }
2272 else
2273 {
2274 consdata->linkingconss[v] = SCIPgetConsLinking(scip, var);
2275 SCIP_CALL( SCIPcaptureCons(scip, consdata->linkingconss[v]) );
2276 }
2277
2278 assert(SCIPexistsConsLinking(scip, var));
2279 assert(consdata->linkingconss[v] != NULL);
2280 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(consdata->linkingconss[v])), "linking") == 0 );
2281 assert(SCIPgetConsLinking(scip, var) == consdata->linkingconss[v]);
2282 }
2283
2284 return SCIP_OKAY;
2285}
2286
2287/**@} */
2288
2289
2290/**@name Check methods
2291 *
2292 * @{
2293 */
2294
2295/** check for the given starting time variables with their demands and durations if the cumulative conditions for the
2296 * given solution is satisfied
2297 */
2298static
2300 SCIP* scip, /**< SCIP data structure */
2301 SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
2302 int nvars, /**< number of variables (jobs) */
2303 SCIP_VAR** vars, /**< array of integer variable which corresponds to starting times for a job */
2304 int* durations, /**< array containing corresponding durations */
2305 int* demands, /**< array containing corresponding demands */
2306 int capacity, /**< available cumulative capacity */
2307 int hmin, /**< left bound of time axis to be considered (including hmin) */
2308 int hmax, /**< right bound of time axis to be considered (not including hmax) */
2309 SCIP_Bool* violated, /**< pointer to store if the cumulative condition is violated */
2310 SCIP_CONS* cons, /**< constraint which is checked */
2311 SCIP_Bool printreason /**< should the reason for the violation be printed? */
2312 )
2313{
2314 int* startsolvalues; /* stores when each job is starting */
2315 int* endsolvalues; /* stores when each job ends */
2316 int* startindices; /* we will sort the startsolvalues, thus we need to know which index of a job it corresponds to */
2317 int* endindices; /* we will sort the endsolvalues, thus we need to know which index of a job it corresponds to */
2318
2319 int freecapacity;
2320 int curtime; /* point in time which we are just checking */
2321 int endindex; /* index of endsolvalues with: endsolvalues[endindex] > curtime */
2322 int j;
2323
2324 SCIP_Real absviol;
2325 SCIP_Real relviol;
2326
2327 assert(scip != NULL);
2328 assert(violated != NULL);
2329
2330 (*violated) = FALSE;
2331
2332 if( nvars == 0 )
2333 return SCIP_OKAY;
2334
2335 assert(vars != NULL);
2336 assert(demands != NULL);
2337 assert(durations != NULL);
2338
2339 /* compute time points where we have to check whether capacity constraint is infeasible or not */
2340 SCIP_CALL( SCIPallocBufferArray(scip, &startsolvalues, nvars) );
2341 SCIP_CALL( SCIPallocBufferArray(scip, &endsolvalues, nvars) );
2342 SCIP_CALL( SCIPallocBufferArray(scip, &startindices, nvars) );
2343 SCIP_CALL( SCIPallocBufferArray(scip, &endindices, nvars) );
2344
2345 /* assign variables, start and endpoints to arrays */
2346 for ( j = 0; j < nvars; ++j )
2347 {
2348 int solvalue;
2349
2350 /* the constraint of the cumulative constraint handler should be called after the integrality check */
2351 assert(SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars[j])));
2352
2353 solvalue = SCIPconvertRealToInt(scip, SCIPgetSolVal(scip, sol, vars[j]));
2354
2355 /* we need to ensure that we check at least one time point during the effective horizon; therefore we project all
2356 * jobs which start before hmin to hmin
2357 */
2358 startsolvalues[j] = MAX(solvalue, hmin);
2359 startindices[j] = j;
2360
2361 endsolvalues[j] = MAX(solvalue + durations[j], hmin);
2362 endindices[j] = j;
2363 }
2364
2365 /* sort the arrays not-decreasing according to start solution values and end solution values (and sort the
2366 * corresponding indices in the same way)
2367 */
2368 SCIPsortIntInt(startsolvalues, startindices, nvars);
2369 SCIPsortIntInt(endsolvalues, endindices, nvars);
2370
2371 endindex = 0;
2372 freecapacity = capacity;
2373 absviol = 0.0;
2374 relviol = 0.0;
2375
2376 /* check each start point of a job whether the capacity is kept or not */
2377 for( j = 0; j < nvars; ++j )
2378 {
2379 /* only check intervals [hmin,hmax) */
2380 curtime = startsolvalues[j];
2381
2382 if( curtime >= hmax )
2383 break;
2384
2385 /* subtract all capacity needed up to this point */
2386 freecapacity -= demands[startindices[j]];
2387 while( j+1 < nvars && startsolvalues[j+1] == curtime )
2388 {
2389 j++;
2390 freecapacity -= demands[startindices[j]];
2391 }
2392
2393 /* free all capacity usages of jobs that are no longer running */
2394 while( endindex < nvars && curtime >= endsolvalues[endindex] )
2395 {
2396 freecapacity += demands[endindices[endindex]];
2397 ++endindex;
2398 }
2399 assert(freecapacity <= capacity);
2400
2401 /* update absolute and relative violation */
2402 if( absviol < (SCIP_Real) (-freecapacity) )
2403 {
2404 absviol = -freecapacity;
2405 relviol = SCIPrelDiff((SCIP_Real)(capacity - freecapacity), (SCIP_Real)capacity);
2406 }
2407
2408 /* check freecapacity to be smaller than zero */
2409 if( freecapacity < 0 && curtime >= hmin )
2410 {
2411 SCIPdebugMsg(scip, "freecapacity = %3d\n", freecapacity);
2412 (*violated) = TRUE;
2413
2414 if( printreason )
2415 {
2416 int i;
2417
2418 /* first state the violated constraints */
2419 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2420
2421 /* second state the reason */
2423 ";\nviolation: at time point %d available capacity = %d, needed capacity = %d\n",
2424 curtime, capacity, capacity - freecapacity);
2425
2426 for( i = 0; i <= j; ++i )
2427 {
2428 if( startsolvalues[i] + durations[startindices[i]] > curtime )
2429 {
2430 SCIPinfoMessage(scip, NULL, "activity %s, start = %i, duration = %d, demand = %d \n",
2431 SCIPvarGetName(vars[startindices[i]]), startsolvalues[i], durations[startindices[i]],
2432 demands[startindices[i]]);
2433 }
2434 }
2435 }
2436 break;
2437 }
2438 } /*lint --e{850}*/
2439
2440 /* update constraint violation in solution */
2441 if( sol != NULL )
2442 SCIPupdateSolConsViolation(scip, sol, absviol, relviol);
2443
2444 /* free all buffer arrays */
2445 SCIPfreeBufferArray(scip, &endindices);
2446 SCIPfreeBufferArray(scip, &startindices);
2447 SCIPfreeBufferArray(scip, &endsolvalues);
2448 SCIPfreeBufferArray(scip, &startsolvalues);
2449
2450 return SCIP_OKAY;
2451}
2452
2453/** check if the given constrait is valid; checks each starting point of a job whether the remaining capacity is at
2454 * least zero or not. If not (*violated) is set to TRUE
2455 */
2456static
2458 SCIP* scip, /**< SCIP data structure */
2459 SCIP_CONS* cons, /**< constraint to be checked */
2460 SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
2461 SCIP_Bool* violated, /**< pointer to store if the constraint is violated */
2462 SCIP_Bool printreason /**< should the reason for the violation be printed? */
2463 )
2464{
2465 SCIP_CONSDATA* consdata;
2466
2467 assert(scip != NULL);
2468 assert(cons != NULL);
2469 assert(violated != NULL);
2470
2471 SCIPdebugMsg(scip, "check cumulative constraints <%s>\n", SCIPconsGetName(cons));
2472
2473 consdata = SCIPconsGetData(cons);
2474 assert(consdata != NULL);
2475
2476 /* check the cumulative condition */
2477 SCIP_CALL( checkCumulativeCondition(scip, sol, consdata->nvars, consdata->vars,
2478 consdata->durations, consdata->demands, consdata->capacity, consdata->hmin, consdata->hmax,
2479 violated, cons, printreason) );
2480
2481 return SCIP_OKAY;
2482}
2483
2484/**@} */
2485
2486/**@name Conflict analysis
2487 *
2488 * @{
2489 */
2490
2491/** resolves the propagation of the core time algorithm */
2492static
2494 SCIP* scip, /**< SCIP data structure */
2495 int nvars, /**< number of start time variables (activities) */
2496 SCIP_VAR** vars, /**< array of start time variables */
2497 int* durations, /**< array of durations */
2498 int* demands, /**< array of demands */
2499 int capacity, /**< cumulative capacity */
2500 int hmin, /**< left bound of time axis to be considered (including hmin) */
2501 int hmax, /**< right bound of time axis to be considered (not including hmax) */
2502 SCIP_VAR* infervar, /**< inference variable */
2503 int inferdemand, /**< demand of the inference variable */
2504 int inferpeak, /**< time point which causes the propagation */
2505 int relaxedpeak, /**< relaxed time point which would be sufficient to be proved */
2506 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2507 SCIP_Bool usebdwidening, /**< should bound widening be used during conflict analysis? */
2508 int* provedpeak, /**< pointer to store the actually proved peak, or NULL */
2509 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2510 )
2511{
2512 SCIP_VAR* var;
2513 SCIP_Bool* reported;
2514 int duration;
2515 int maxlst;
2516 int minect;
2517 int ect;
2518 int lst;
2519 int j;
2520
2522
2523 SCIPdebugMsg(scip, "variable <%s>: (demand %d) resolve propagation of core time algorithm (peak %d)\n",
2524 SCIPvarGetName(infervar), inferdemand, inferpeak);
2525 assert(nvars > 0);
2526
2527 /* adjusted capacity */
2528 capacity -= inferdemand;
2529 maxlst = INT_MIN;
2530 minect = INT_MAX;
2531
2532 SCIP_CALL( SCIPallocBufferArray(scip, &reported, nvars) );
2533 BMSclearMemoryArray(reported, nvars);
2534
2535 /* first we loop over all variables and adjust the capacity with those jobs which provide a global core at the
2536 * inference peak and those where the current conflict bounds provide a core at the inference peak
2537 */
2538 for( j = 0; j < nvars && capacity >= 0; ++j )
2539 {
2540 var = vars[j];
2541 assert(var != NULL);
2542
2543 /* skip inference variable */
2544 if( var == infervar )
2545 continue;
2546
2547 duration = durations[j];
2548 assert(duration > 0);
2549
2550 /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */
2551 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)));
2552 assert(SCIPisFeasIntegral(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE)));
2553 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)));
2554 assert(SCIPisFeasIntegral(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE)));
2555
2556 SCIPdebugMsg(scip, "variable <%s>: glb=[%g,%g] conflict=[%g,%g] (duration %d, demand %d)\n",
2558 SCIPgetConflictVarLb(scip, var), SCIPgetConflictVarUb(scip, var), duration, demands[j]);
2559
2560 ect = SCIPconvertRealToInt(scip, SCIPvarGetLbGlobal(var)) + duration;
2562
2563 /* check if the inference peak is part of the global bound core; if so we decreasing the capacity by the demand of
2564 * that job without adding it the explanation
2565 */
2566 if( inferpeak < ect && lst <= inferpeak )
2567 {
2568 capacity -= demands[j];
2569 reported[j] = TRUE;
2570
2571 maxlst = MAX(maxlst, lst);
2572 minect = MIN(minect, ect);
2573 assert(maxlst < minect);
2574
2575 if( explanation != NULL )
2576 explanation[j] = TRUE;
2577
2578 continue;
2579 }
2580
2581 /* collect the conflict bound core (the conflict bounds are those bounds which are already part of the conflict)
2582 * hence these bound are already reported by other resolve propation steps. In case a bound (lower or upper) is
2583 * not part of the conflict yet we get the global bounds back.
2584 */
2585 ect = SCIPconvertRealToInt(scip, SCIPgetConflictVarLb(scip, var)) + duration;
2587
2588 /* check if the inference peak is part of the conflict bound core; if so we decreasing the capacity by the demand
2589 * of that job without and collect the job as part of the explanation
2590 *
2591 * @note we do not need to reported that job to SCIP since the required bounds are already reported
2592 */
2593 if( inferpeak < ect && lst <= inferpeak )
2594 {
2595 capacity -= demands[j];
2596 reported[j] = TRUE;
2597
2598 maxlst = MAX(maxlst, lst);
2599 minect = MIN(minect, ect);
2600 assert(maxlst < minect);
2601
2602 if( explanation != NULL )
2603 explanation[j] = TRUE;
2604 }
2605 }
2606
2607 if( capacity >= 0 )
2608 {
2609 int* cands;
2610 int* canddemands;
2611 int ncands;
2612 int c;
2613
2614 SCIP_CALL( SCIPallocBufferArray(scip, &cands, nvars) );
2615 SCIP_CALL( SCIPallocBufferArray(scip, &canddemands, nvars) );
2616 ncands = 0;
2617
2618 /* collect all cores of the variables which lay in the considered time window except the inference variable */
2619 for( j = 0; j < nvars; ++j )
2620 {
2621 var = vars[j];
2622 assert(var != NULL);
2623
2624 /* skip inference variable */
2625 if( var == infervar || reported[j] )
2626 continue;
2627
2628 duration = durations[j];
2629 assert(duration > 0);
2630
2631 /* compute cores of jobs; if core overlaps interval of inference variable add this job to the array */
2632 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)));
2633 assert(SCIPisFeasIntegral(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE)));
2634 assert(!SCIPvarIsActive(var) || SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)));
2635 assert(SCIPisFeasIntegral(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE)));
2636
2637 /* collect local core information */
2638 ect = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) + duration;
2639 lst = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
2640
2641 SCIPdebugMsg(scip, "variable <%s>: loc=[%g,%g] glb=[%g,%g] (duration %d, demand %d)\n",
2642 SCIPvarGetName(var), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE),
2643 SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), duration, demands[j]);
2644
2645 /* check if the inference peak is part of the core */
2646 if( inferpeak < ect && lst <= inferpeak )
2647 {
2648 cands[ncands] = j;
2649 canddemands[ncands] = demands[j];
2650 ncands++;
2651
2652 capacity -= demands[j];
2653 }
2654 }
2655
2656 /* sort candidates indices w.r.t. their demands */
2657 SCIPsortDownIntInt(canddemands, cands, ncands);
2658
2659 assert(capacity < 0);
2660 assert(ncands > 0);
2661
2662 /* greedily remove candidates form the list such that the needed capacity is still exceeded */
2663 while( capacity + canddemands[ncands-1] < 0 )
2664 {
2665 ncands--;
2666 capacity += canddemands[ncands];
2667 assert(ncands > 0);
2668 }
2669
2670 /* compute the size (number of time steps) of the job cores */
2671 for( c = 0; c < ncands; ++c )
2672 {
2673 var = vars[cands[c]];
2674 assert(var != NULL);
2675
2676 duration = durations[cands[c]];
2677
2678 ect = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) + duration;
2679 lst = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
2680
2681 maxlst = MAX(maxlst, lst);
2682 minect = MIN(minect, ect);
2683 assert(maxlst < minect);
2684 }
2685
2686 SCIPdebugMsg(scip, "infer peak %d, relaxed peak %d, lst %d, ect %d\n", inferpeak, relaxedpeak, maxlst, minect);
2687 assert(inferpeak >= maxlst);
2688 assert(inferpeak < minect);
2689
2690 /* check if the collect variable are sufficient to prove the relaxed bound (relaxedpeak) */
2691 if( relaxedpeak < inferpeak )
2692 {
2693 inferpeak = MAX(maxlst, relaxedpeak);
2694 }
2695 else if( relaxedpeak > inferpeak )
2696 {
2697 inferpeak = MIN(minect-1, relaxedpeak);
2698 }
2699 assert(inferpeak >= hmin);
2700 assert(inferpeak < hmax);
2701 assert(inferpeak >= maxlst);
2702 assert(inferpeak < minect);
2703
2704 /* post all necessary bound changes */
2705 for( c = 0; c < ncands; ++c )
2706 {
2707 var = vars[cands[c]];
2708 assert(var != NULL);
2709
2710 if( usebdwidening )
2711 {
2712 duration = durations[cands[c]];
2713
2714 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(inferpeak - duration + 1)) );
2715 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, (SCIP_Real)inferpeak) );
2716 }
2717 else
2718 {
2719 SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
2720 SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
2721 }
2722
2723 if( explanation != NULL )
2724 explanation[cands[c]] = TRUE;
2725 }
2726
2727 SCIPfreeBufferArray(scip, &canddemands);
2728 SCIPfreeBufferArray(scip, &cands);
2729 }
2730
2731 SCIPfreeBufferArray(scip, &reported);
2732
2733 if( provedpeak != NULL )
2734 *provedpeak = inferpeak;
2735
2736 return SCIP_OKAY;
2737}
2738
2739#if 0
2740/** repropagation of edge finding algorithm simplified version from Petr Vilim only a small subset is reported such that
2741 * energy in total and for bound change is enough
2742 */
2743static
2744SCIP_RETCODE resolvePropagationEdgeFinding(
2745 SCIP* scip, /**< SCIP data structure */
2746 int nvars, /**< number of start time variables (activities) */
2747 SCIP_VAR** vars, /**< array of start time variables */
2748 int* durations, /**< array of durations */
2749 int hmin, /**< left bound of time axis to be considered (including hmin) */
2750 int hmax, /**< right bound of time axis to be considered (not including hmax) */
2751 SCIP_VAR* infervar, /**< variable whose bound change is to be explained */
2752 INFERINFO inferinfo, /**< inference info containing position of correct bdchgids */
2753 SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
2754 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2755 SCIP_Bool usebdwidening, /**< should bound widening be used during conflict analysis? */
2756 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2757 )
2758{
2759 int est;
2760 int lct;
2761 int j;
2762
2763 /* ???????????????????? do bound widening */
2764
2765 assert(scip != NULL);
2766 assert(nvars > 0);
2767 assert(inferInfoGetProprule(inferinfo) == PROPRULE_2_EDGEFINDING);
2768
2769 SCIPdebugMsg(scip, "repropagate edge-finding with short reasons for variable <%s>\n", SCIPvarGetName(infervar));
2770
2771 if( boundtype == SCIP_BOUNDTYPE_LOWER )
2772 {
2773 SCIP_CALL( SCIPaddConflictLb(scip, infervar, bdchgidx) );
2774 }
2775 else
2776 {
2777 SCIP_CALL( SCIPaddConflictUb(scip, infervar, bdchgidx) );
2778 }
2779
2780 est = inferInfoGetData1(inferinfo);
2781 lct = inferInfoGetData2(inferinfo);
2782 assert(est < lct);
2783
2784 /* collect the energies of all variables in [est_omega, lct_omega] */
2785 for( j = 0; j < nvars; ++j )
2786 {
2787 SCIP_VAR* var;
2788 SCIP_Bool left;
2789 SCIP_Bool right;
2790 int duration;
2791 int lb;
2792 int ub;
2793
2794 var = vars[j];
2795 assert(var != NULL);
2796
2797 if( var == infervar )
2798 {
2799 if( explanation != NULL )
2800 explanation[j] = TRUE;
2801
2802 continue;
2803 }
2804
2805 lb = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE));
2806 ub = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
2807
2808 duration = durations[j];
2809 assert(duration > 0);
2810
2811 /* in case the earliest start time is equal to hmin we have to also consider the jobs which run in that region
2812 * since we use adjusted jobs during the propagation
2813 */
2814 left = (est == hmin && lb + duration > hmin) || lb >= est;
2815
2816 /* in case the latest completion time is equal to hmax we have to also consider the jobs which run in that region
2817 * since we use adjusted jobs during the propagation
2818 */
2819 right = (lct == hmax && ub < hmax) || ub + duration <= lct;
2820
2821 /* store all jobs running in [est_omega; lct_omega] */
2822 if( left && right )
2823 {
2824 /* check if bound widening should be used */
2825 if( usebdwidening )
2826 {
2827 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(lct - duration)) );
2828 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, (SCIP_Real)(est)) );
2829 }
2830 else
2831 {
2832 SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
2833 SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
2834 }
2835
2836 if( explanation != NULL )
2837 explanation[j] = TRUE;
2838 }
2839 }
2840
2841 return SCIP_OKAY;
2842}
2843#endif
2844
2845/** compute the minimum overlaps w.r.t. the duration of the job and the time window [begin,end) */
2846static
2848 int begin, /**< begin of the times interval */
2849 int end, /**< end of time interval */
2850 int est, /**< earliest start time */
2851 int lst, /**< latest start time */
2852 int duration /**< duration of the job */
2853 )
2854{
2855 int left;
2856 int right;
2857 int ect;
2858 int lct;
2859
2860 ect = est + duration;
2861 lct = lst + duration;
2862
2863 /* check if job runs completely within [begin,end) */
2864 if( lct <= end && est >= begin )
2865 return duration;
2866
2867 assert(lst <= end && ect >= begin);
2868
2869 left = ect - begin;
2870 assert(left > 0);
2871
2872 right = end - lst;
2873 assert(right > 0);
2874
2875 return MIN3(left, right, end - begin);
2876}
2877
2878/** an overload was detected due to the time-time edge-finding propagate; initialized conflict analysis, add an initial
2879 * reason
2880 *
2881 * @note the conflict analysis is not performend, only the initialized SCIP_Bool pointer is set to TRUE
2882 */
2883static
2885 SCIP* scip, /**< SCIP data structure */
2886 int nvars, /**< number of start time variables (activities) */
2887 SCIP_VAR** vars, /**< array of start time variables */
2888 int* durations, /**< array of durations */
2889 int* demands, /**< array of demands */
2890 int capacity, /**< capacity of the cumulative condition */
2891 int begin, /**< begin of the time window */
2892 int end, /**< end of the time window */
2893 SCIP_VAR* infervar, /**< variable which was propagate, or NULL */
2894 SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
2895 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
2896 SCIP_Real relaxedbd, /**< the relaxed bound which is sufficient to be explained */
2897 SCIP_Bool usebdwidening, /**< should bound widening be used during conflict analysis? */
2898 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
2899 )
2900{
2901 int* locenergies;
2902 int* overlaps;
2903 int* idxs;
2904
2905 SCIP_Longint requiredenergy;
2906 int v;
2907
2908 SCIP_CALL( SCIPallocBufferArray(scip, &locenergies, nvars) );
2909 SCIP_CALL( SCIPallocBufferArray(scip, &overlaps, nvars) );
2910 SCIP_CALL( SCIPallocBufferArray(scip, &idxs, nvars) );
2911
2912 /* energy which needs be explained */
2913 requiredenergy = ((SCIP_Longint) end - begin) * capacity;
2914
2915 SCIPdebugMsg(scip, "analysis energy load in [%d,%d) (capacity %d, energy %" SCIP_LONGINT_FORMAT ")\n", begin, end, capacity, requiredenergy);
2916
2917 /* collect global contribution and adjusted the required energy by the amount of energy the inference variable
2918 * takes
2919 */
2920 for( v = 0; v < nvars; ++v )
2921 {
2922 SCIP_VAR* var;
2923 int glbenergy;
2924 int duration;
2925 int demand;
2926 int est;
2927 int lst;
2928
2929 var = vars[v];
2930 assert(var != NULL);
2931
2932 locenergies[v] = 0;
2933 overlaps[v] = 0;
2934 idxs[v] = v;
2935
2936 demand = demands[v];
2937 assert(demand > 0);
2938
2939 duration = durations[v];
2940 assert(duration > 0);
2941
2942 /* check if the variable equals the inference variable (the one which was propagated) */
2943 if( infervar == var )
2944 {
2945 int overlap;
2946 int right;
2947 int left;
2948
2949 assert(relaxedbd != SCIP_UNKNOWN); /*lint !e777*/
2950
2951 SCIPdebugMsg(scip, "inference variable <%s>[%g,%g] %s %g (duration %d, demand %d)\n",
2952 SCIPvarGetName(var), SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE),
2953 boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", relaxedbd, duration, demand);
2954
2955 /* compute the amount of energy which needs to be available for enforcing the propagation and report the bound
2956 * which is necessary from the inference variable
2957 */
2958 if( boundtype == SCIP_BOUNDTYPE_UPPER )
2959 {
2960 int lct;
2961
2962 /* get the latest start time of the infer start time variable before the propagation took place */
2963 lst = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
2964
2965 /* the latest start time of the inference start time variable before the propagation needs to be smaller as
2966 * the end of the time interval; meaning the job needs be overlap with the time interval in case the job is
2967 * scheduled w.r.t. its latest start time
2968 */
2969 assert(lst < end);
2970
2971 /* compute the overlap of the job in case it would be scheduled w.r.t. its latest start time and the time
2972 * interval (before the propagation)
2973 */
2974 right = MIN3(end - lst, end - begin, duration);
2975
2976 /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */
2977 assert(right > 0);
2978
2979 lct = SCIPconvertRealToInt(scip, relaxedbd) + duration;
2980 assert(begin <= lct);
2981 assert(bdchgidx == NULL || SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE)) < begin);
2982
2983 /* compute the overlap of the job after the propagation but considering the relaxed bound */
2984 left = MIN(lct - begin + 1, end - begin);
2985 assert(left > 0);
2986
2987 /* compute the minimum overlap; */
2988 overlap = MIN(left, right);
2989 assert(overlap > 0);
2990 assert(overlap <= end - begin);
2991 assert(overlap <= duration);
2992
2993 if( usebdwidening )
2994 {
2995 assert(SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)) <= (end - overlap));
2996 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, (SCIP_Real)(end - overlap)) );
2997 }
2998 else
2999 {
3000 SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
3001 }
3002 }
3003 else
3004 {
3005 int ect;
3006
3007 assert(boundtype == SCIP_BOUNDTYPE_LOWER);
3008
3009 /* get the earliest completion time of the infer start time variable before the propagation took place */
3010 ect = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) + duration;
3011
3012 /* the earliest start time of the inference start time variable before the propagation needs to be larger as
3013 * than the beginning of the time interval; meaning the job needs be overlap with the time interval in case
3014 * the job is scheduled w.r.t. its earliest start time
3015 */
3016 assert(ect > begin);
3017
3018 /* compute the overlap of the job in case it would be scheduled w.r.t. its earliest start time and the time
3019 * interval (before the propagation)
3020 */
3021 left = MIN3(ect - begin, end - begin, duration);
3022
3023 /* the job needs to overlap with the interval; otherwise the propagation w.r.t. this time window is not valid */
3024 assert(left > 0);
3025
3026 est = SCIPconvertRealToInt(scip, relaxedbd);
3027 assert(end >= est);
3028 assert(bdchgidx == NULL || end - SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE) < duration);
3029
3030 /* compute the overlap of the job after the propagation but considering the relaxed bound */
3031 right = MIN(end - est + 1, end - begin);
3032 assert(right > 0);
3033
3034 /* compute the minimum overlap */
3035 overlap = MIN(left, right);
3036 assert(overlap > 0);
3037 assert(overlap <= end - begin);
3038 assert(overlap <= duration);
3039
3040 if( usebdwidening )
3041 {
3042 assert(SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) >= (begin + overlap - duration));
3043 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)(begin + overlap - duration)) );
3044 }
3045 else
3046 {
3047 SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
3048 }
3049 }
3050
3051 /* subtract the amount of energy which is available due to the overlap of the inference start time */
3052 requiredenergy -= (SCIP_Longint) overlap * demand;
3053
3054 if( explanation != NULL )
3055 explanation[v] = TRUE;
3056
3057 continue;
3058 }
3059
3060 /* global time points */
3063
3064 glbenergy = 0;
3065
3066 /* check if the has any overlap w.r.t. global bound; meaning some parts of the job will run for sure within the
3067 * time window
3068 */
3069 if( est + duration > begin && lst < end )
3070 {
3071 /* evaluated global contribution */
3072 glbenergy = computeOverlap(begin, end, est, lst, duration) * demand;
3073
3074 /* remove the globally available energy form the required energy */
3075 requiredenergy -= glbenergy;
3076
3077 if( explanation != NULL )
3078 explanation[v] = TRUE;
3079 }
3080
3081 /* local time points */
3082 est = SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE));
3083 lst = SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE));
3084
3085 /* check if the job has any overlap w.r.t. local bound; meaning some parts of the job will run for sure within the
3086 * time window
3087 */
3088 if( est + duration > begin && lst < end )
3089 {
3090 overlaps[v] = computeOverlap(begin, end, est, lst, duration);
3091
3092 /* evaluated additionally local energy contribution */
3093 locenergies[v] = overlaps[v] * demand - glbenergy;
3094 assert(locenergies[v] >= 0);
3095 }
3096 }
3097
3098 /* sort the variable contributions w.r.t. additional local energy contributions */
3099 SCIPsortDownIntIntInt(locenergies, overlaps, idxs, nvars);
3100
3101 /* add local energy contributions until an overload is implied */
3102 for( v = 0; v < nvars && requiredenergy >= 0; ++v )
3103 {
3104 SCIP_VAR* var;
3105 int duration;
3106 int overlap;
3107 int relaxlb;
3108 int relaxub;
3109 int idx;
3110
3111 idx = idxs[v];
3112 assert(idx >= 0 && idx < nvars);
3113
3114 var = vars[idx];
3115 assert(var != NULL);
3116 assert(var != infervar);
3117
3118 duration = durations[idx];
3119 assert(duration > 0);
3120
3121 overlap = overlaps[v];
3122 assert(overlap > 0);
3123
3124 requiredenergy -= locenergies[v];
3125
3126 if( requiredenergy < -1 )
3127 {
3128 int demand;
3129
3130 demand = demands[idx];
3131 assert(demand > 0);
3132
3133 overlap += (int)((requiredenergy + 1) / demand);
3134
3135#ifndef NDEBUG
3136 requiredenergy += locenergies[v];
3137 requiredenergy -= (SCIP_Longint) overlap * demand;
3138 assert(requiredenergy < 0);
3139#endif
3140 }
3141 assert(overlap > 0);
3142
3143 relaxlb = begin - duration + overlap;
3144 relaxub = end - overlap;
3145
3146 SCIPdebugMsg(scip, "variable <%s> glb=[%g,%g] loc=[%g,%g], conf=[%g,%g], added=[%d,%d] (demand %d, duration %d)\n",
3147 SCIPvarGetName(var),
3151 relaxlb, relaxub, demands[idx], duration);
3152
3153 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, (SCIP_Real)relaxlb) );
3154 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, (SCIP_Real)relaxub) );
3155
3156 if( explanation != NULL )
3157 explanation[idx] = TRUE;
3158 }
3159
3160 assert(requiredenergy < 0);
3161
3162 SCIPfreeBufferArray(scip, &idxs);
3163 SCIPfreeBufferArray(scip, &overlaps);
3164 SCIPfreeBufferArray(scip, &locenergies);
3165
3166 return SCIP_OKAY;
3167}
3168
3169/** resolve propagation w.r.t. the cumulative condition */
3170static
3172 SCIP* scip, /**< SCIP data structure */
3173 int nvars, /**< number of start time variables (activities) */
3174 SCIP_VAR** vars, /**< array of start time variables */
3175 int* durations, /**< array of durations */
3176 int* demands, /**< array of demands */
3177 int capacity, /**< cumulative capacity */
3178 int hmin, /**< left bound of time axis to be considered (including hmin) */
3179 int hmax, /**< right bound of time axis to be considered (not including hmax) */
3180 SCIP_VAR* infervar, /**< the conflict variable whose bound change has to be resolved */
3181 INFERINFO inferinfo, /**< the user information */
3182 SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
3183 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
3184 SCIP_Real relaxedbd, /**< the relaxed bound which is sufficient to be explained */
3185 SCIP_Bool usebdwidening, /**< should bound widening be used during conflict analysis? */
3186 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
3187 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
3188 )
3189{
3190 switch( inferInfoGetProprule(inferinfo) )
3191 {
3193 {
3194 int inferdemand;
3195 int inferduration;
3196 int inferpos;
3197 int inferpeak;
3198 int relaxedpeak;
3199 int provedpeak;
3200
3201 /* get the position of the inferred variable in the vars array */
3202 inferpos = inferInfoGetData1(inferinfo);
3203 if( inferpos >= nvars || vars[inferpos] != infervar )
3204 {
3205 /* find inference variable in constraint */
3206 for( inferpos = 0; inferpos < nvars && vars[inferpos] != infervar; ++inferpos )
3207 {}
3208 }
3209 assert(inferpos < nvars);
3210 assert(vars[inferpos] == infervar);
3211
3212 inferdemand = demands[inferpos];
3213 inferduration = durations[inferpos];
3214
3215 if( boundtype == SCIP_BOUNDTYPE_UPPER )
3216 {
3217 /* we propagated the latest start time (upper bound) step wise with a step length of at most the duration of
3218 * the inference variable
3219 */
3220 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE) - SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < inferduration + 0.5);
3221
3222 SCIPdebugMsg(scip, "variable <%s>: upper bound changed from %g to %g (relaxed %g)\n",
3223 SCIPvarGetName(infervar), SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE),
3224 SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE), relaxedbd);
3225
3226 /* get the inference peak that the time point which lead to the that propagtion */
3227 inferpeak = inferInfoGetData2(inferinfo);
3228 /* the bound passed back to be resolved might be tighter as the bound propagted by the core time propagator;
3229 * this can happen if the variable is not activ and aggregated to an activ variable with a scale != 1.0
3230 */
3231 assert(SCIPconvertRealToInt(scip, SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE)) + inferduration <= inferpeak);
3232 relaxedpeak = SCIPconvertRealToInt(scip, relaxedbd) + inferduration;
3233
3234 /* make sure that the relaxed peak is part of the effective horizon */
3235 relaxedpeak = MIN(relaxedpeak, hmax-1);
3236
3237 /* make sure that relaxed peak is not larger than the infer peak
3238 *
3239 * This can happen in case the variable is not an active variable!
3240 */
3241 relaxedpeak = MAX(relaxedpeak, inferpeak);
3242 assert(relaxedpeak >= inferpeak);
3243 assert(relaxedpeak >= hmin);
3244 }
3245 else
3246 {
3247 assert(boundtype == SCIP_BOUNDTYPE_LOWER);
3248
3249 SCIPdebugMsg(scip, "variable <%s>: lower bound changed from %g to %g (relaxed %g)\n",
3250 SCIPvarGetName(infervar), SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, FALSE),
3251 SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE), relaxedbd);
3252
3253 /* get the time interval where the job could not be scheduled */
3254 inferpeak = inferInfoGetData2(inferinfo);
3255 /* the bound passed back to be resolved might be tighter as the bound propagted by the core time propagator;
3256 * this can happen if the variable is not activ and aggregated to an activ variable with a scale != 1.0
3257 */
3258 assert(SCIPconvertRealToInt(scip, SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE)) - 1 >= inferpeak);
3259 relaxedpeak = SCIPconvertRealToInt(scip, relaxedbd) - 1;
3260
3261 /* make sure that the relaxed peak is part of the effective horizon */
3262 relaxedpeak = MAX(relaxedpeak, hmin);
3263
3264 /* make sure that relaxed peak is not larger than the infer peak
3265 *
3266 * This can happen in case the variable is not an active variable!
3267 */
3268 relaxedpeak = MIN(relaxedpeak, inferpeak);
3269 assert(relaxedpeak < hmax);
3270 }
3271
3272 /* resolves the propagation of the core time algorithm */
3273 SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
3274 infervar, inferdemand, inferpeak, relaxedpeak, bdchgidx, usebdwidening, &provedpeak, explanation) );
3275
3276 if( boundtype == SCIP_BOUNDTYPE_UPPER )
3277 {
3278 if( usebdwidening )
3279 {
3280 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, infervar, NULL, (SCIP_Real)provedpeak) );
3281 }
3282 else
3283 {
3284 /* old upper bound of variable itself is part of the explanation */
3285 SCIP_CALL( SCIPaddConflictUb(scip, infervar, bdchgidx) );
3286 }
3287 }
3288 else
3289 {
3290 assert(boundtype == SCIP_BOUNDTYPE_LOWER);
3291
3292 if( usebdwidening )
3293 {
3294 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, bdchgidx, (SCIP_Real)(provedpeak - inferduration + 1)) );
3295 }
3296 else
3297 {
3298 /* old lower bound of variable itself is part of the explanation */
3299 SCIP_CALL( SCIPaddConflictLb(scip, infervar, bdchgidx) );
3300 }
3301 }
3302
3303 if( explanation != NULL )
3304 explanation[inferpos] = TRUE;
3305
3306 break;
3307 }
3309 case PROPRULE_3_TTEF:
3310 {
3311 int begin;
3312 int end;
3313
3314 begin = inferInfoGetData1(inferinfo);
3315 end = inferInfoGetData2(inferinfo);
3316 assert(begin < end);
3317
3318 begin = MAX(begin, hmin);
3319 end = MIN(end, hmax);
3320
3321 SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
3322 begin, end, infervar, boundtype, bdchgidx, relaxedbd, usebdwidening, explanation) );
3323
3324 break;
3325 }
3326
3327 case PROPRULE_0_INVALID:
3328 default:
3329 SCIPerrorMessage("invalid inference information %d\n", inferInfoGetProprule(inferinfo));
3330 SCIPABORT();
3331 return SCIP_INVALIDDATA; /*lint !e527*/
3332 }
3333
3334 (*result) = SCIP_SUCCESS;
3335
3336 return SCIP_OKAY;
3337}
3338
3339/**@} */
3340
3341
3342/**@name Enforcement methods
3343 *
3344 * @{
3345 */
3346
3347/** apply all fixings which are given by the alternative bounds */
3348static
3350 SCIP* scip, /**< SCIP data structure */
3351 SCIP_VAR** vars, /**< array of active variables */
3352 int nvars, /**< number of active variables */
3353 int* alternativelbs, /**< alternative lower bounds */
3354 int* alternativeubs, /**< alternative lower bounds */
3355 int* downlocks, /**< number of constraints with down lock participating by the computation */
3356 int* uplocks, /**< number of constraints with up lock participating by the computation */
3357 SCIP_Bool* branched /**< pointer to store if a branching was applied */
3358 )
3359{
3360 int v;
3361
3362 for( v = 0; v < nvars; ++v )
3363 {
3364 SCIP_VAR* var;
3365 SCIP_Real objval;
3366
3367 var = vars[v];
3368 assert(var != NULL);
3369
3370 objval = SCIPvarGetObj(var);
3371
3372 if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == downlocks[v] && !SCIPisNegative(scip, objval) )
3373 {
3374 int ub;
3375
3377
3378 if( alternativelbs[v] <= ub )
3379 {
3380 SCIP_CALL( SCIPbranchVarHole(scip, var, SCIPvarGetLbLocal(var), (SCIP_Real)alternativelbs[v], NULL, NULL) );
3381 (*branched) = TRUE;
3382
3383 SCIPdebugMsg(scip, "variable <%s> branched domain hole (%g,%d)\n", SCIPvarGetName(var),
3384 SCIPvarGetLbLocal(var), alternativelbs[v]);
3385
3386 return SCIP_OKAY;
3387 }
3388 }
3389
3390 if( SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == uplocks[v] && !SCIPisPositive(scip, objval) )
3391 {
3392 int lb;
3393
3395
3396 if( alternativeubs[v] >= lb )
3397 {
3398 SCIP_CALL( SCIPbranchVarHole(scip, var, (SCIP_Real)alternativeubs[v], SCIPvarGetUbLocal(var), NULL, NULL) );
3399 (*branched) = TRUE;
3400
3401 SCIPdebugMsg(scip, "variable <%s> branched domain hole (%d,%g)\n", SCIPvarGetName(var),
3402 alternativeubs[v], SCIPvarGetUbLocal(var));
3403
3404 return SCIP_OKAY;
3405 }
3406 }
3407 }
3408
3409 return SCIP_OKAY;
3410}
3411
3412/** remove the capacity requirments for all job which start at the curtime */
3413static
3415 SCIP_CONSDATA* consdata, /**< constraint data */
3416 int curtime, /**< current point in time */
3417 int* starttimes, /**< array of start times */
3418 int* startindices, /**< permutation with respect to the start times */
3419 int* freecapacity, /**< pointer to store the resulting free capacity */
3420 int* idx, /**< pointer to index in start time array */
3421 int nvars /**< number of vars in array of starttimes and startindices */
3422 )
3423{
3424#if defined SCIP_DEBUG && !defined NDEBUG
3425 int oldidx;
3426
3427 assert(idx != NULL);
3428 oldidx = *idx;
3429#else
3430 assert(idx != NULL);
3431#endif
3432
3433 assert(starttimes != NULL);
3434 assert(starttimes != NULL);
3435 assert(freecapacity != NULL);
3436 assert(starttimes[*idx] == curtime);
3437 assert(consdata->demands != NULL);
3438 assert(freecapacity != idx);
3439
3440 /* subtract all capacity needed up to this point */
3441 (*freecapacity) -= consdata->demands[startindices[*idx]];
3442
3443 while( (*idx)+1 < nvars && starttimes[(*idx)+1] == curtime )
3444 {
3445 ++(*idx);
3446 (*freecapacity) -= consdata->demands[startindices[(*idx)]];
3447 assert(freecapacity != idx);
3448 }
3449#ifdef SCIP_DEBUG
3450 assert(oldidx <= *idx);
3451#endif
3452}
3453
3454/** add the capacity requirments for all job which end at the curtime */
3455static
3457 SCIP_CONSDATA* consdata, /**< constraint data */
3458 int curtime, /**< current point in time */
3459 int* endtimes, /**< array of end times */
3460 int* endindices, /**< permutation with rspect to the end times */
3461 int* freecapacity, /**< pointer to store the resulting free capacity */
3462 int* idx, /**< pointer to index in end time array */
3463 int nvars /**< number of vars in array of starttimes and startindices */
3464 )
3465{
3466#if defined SCIP_DEBUG && !defined NDEBUG
3467 int oldidx;
3468 oldidx = *idx;
3469#endif
3470
3471 /* free all capacity usages of jobs the are no longer running */
3472 while( endtimes[*idx] <= curtime && *idx < nvars)
3473 {
3474 (*freecapacity) += consdata->demands[endindices[*idx]];
3475 ++(*idx);
3476 }
3477
3478#ifdef SCIP_DEBUG
3479 assert(oldidx <= *idx);
3480#endif
3481}
3482
3483/** computes a point in time when the capacity is exceeded returns hmax if this does not happen */
3484static
3486 SCIP* scip, /**< SCIP data structure */
3487 SCIP_CONSDATA* consdata, /**< constraint handler data */
3488 SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
3489 int* timepoint /**< pointer to store the time point of the peak */
3490 )
3491{
3492 int* starttimes; /* stores when each job is starting */
3493 int* endtimes; /* stores when each job ends */
3494 int* startindices; /* we will sort the startsolvalues, thus we need to know wich index of a job it corresponds to */
3495 int* endindices; /* we will sort the endsolvalues, thus we need to know wich index of a job it corresponds to */
3496
3497 int nvars; /* number of activities for this constraint */
3498 int freecapacity; /* remaining capacity */
3499 int curtime; /* point in time which we are just checking */
3500 int endindex; /* index of endsolvalues with: endsolvalues[endindex] > curtime */
3501
3502 int hmin;
3503 int hmax;
3504
3505 int j;
3506
3507 assert(consdata != NULL);
3508
3509 nvars = consdata->nvars;
3510 assert(nvars > 0);
3511
3512 *timepoint = consdata->hmax;
3513
3514 assert(consdata->vars != NULL);
3515
3516 SCIP_CALL( SCIPallocBufferArray(scip, &starttimes, nvars) );
3517 SCIP_CALL( SCIPallocBufferArray(scip, &endtimes, nvars) );
3518 SCIP_CALL( SCIPallocBufferArray(scip, &startindices, nvars) );
3519 SCIP_CALL( SCIPallocBufferArray(scip, &endindices, nvars) );
3520
3521 /* create event point arrays */
3522 createSortedEventpointsSol(scip, sol, consdata->nvars, consdata->vars, consdata->durations,
3523 starttimes, endtimes, startindices, endindices);
3524
3525 endindex = 0;
3526 freecapacity = consdata->capacity;
3527 hmin = consdata->hmin;
3528 hmax = consdata->hmax;
3529
3530 /* check each startpoint of a job whether the capacity is kept or not */
3531 for( j = 0; j < nvars; ++j )
3532 {
3533 curtime = starttimes[j];
3534 SCIPdebugMsg(scip, "look at %d-th job with start %d\n", j, curtime);
3535
3536 if( curtime >= hmax )
3537 break;
3538
3539 /* remove the capacity requirments for all job which start at the curtime */
3540 subtractStartingJobDemands(consdata, curtime, starttimes, startindices, &freecapacity, &j, nvars);
3541
3542 /* add the capacity requirments for all job which end at the curtime */
3543 addEndingJobDemands(consdata, curtime, endtimes, endindices, &freecapacity, &endindex, nvars);
3544
3545 assert(freecapacity <= consdata->capacity);
3546 assert(endindex <= nvars);
3547
3548 /* endindex - points to the next job which will finish */
3549 /* j - points to the last job that has been released */
3550
3551 /* if free capacity is smaller than zero, then add branching candidates */
3552 if( freecapacity < 0 && curtime >= hmin )
3553 {
3554 *timepoint = curtime;
3555 break;
3556 }
3557 } /*lint --e{850}*/
3558
3559 /* free all buffer arrays */
3560 SCIPfreeBufferArray(scip, &endindices);
3561 SCIPfreeBufferArray(scip, &startindices);
3562 SCIPfreeBufferArray(scip, &endtimes);
3563 SCIPfreeBufferArray(scip, &starttimes);
3564
3565 return SCIP_OKAY;
3566}
3567
3568/** checks all cumulative constraints for infeasibility and add branching candidates to storage */
3569static
3571 SCIP* scip, /**< SCIP data structure */
3572 SCIP_CONS** conss, /**< constraints to be processed */
3573 int nconss, /**< number of constraints */
3574 SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
3575 int* nbranchcands /**< pointer to store the number of branching variables */
3576 )
3577{
3578 SCIP_HASHTABLE* collectedvars;
3579 int c;
3580
3581 assert(scip != NULL);
3582 assert(conss != NULL);
3583
3584 /* create a hash table */
3586 SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal, NULL) );
3587
3588 assert(scip != NULL);
3589 assert(conss != NULL);
3590
3591 for( c = 0; c < nconss; ++c )
3592 {
3593 SCIP_CONS* cons;
3594 SCIP_CONSDATA* consdata;
3595
3596 int curtime;
3597 int j;
3598
3599 cons = conss[c];
3600 assert(cons != NULL);
3601
3602 if( !SCIPconsIsActive(cons) )
3603 continue;
3604
3605 consdata = SCIPconsGetData(cons);
3606 assert(consdata != NULL);
3607
3608 /* get point in time when capacity is exceeded */
3609 SCIP_CALL( computePeak(scip, consdata, sol, &curtime) );
3610
3611 if( curtime < consdata->hmin || curtime >= consdata->hmax )
3612 continue;
3613
3614 /* report all variables that are running at that point in time */
3615 for( j = 0; j < consdata->nvars; ++j )
3616 {
3617 SCIP_VAR* var;
3618 int lb;
3619 int ub;
3620
3621 var = consdata->vars[j];
3622 assert(var != NULL);
3623
3624 /* check if the variable was already added */
3625 if( SCIPhashtableExists(collectedvars, (void*)var) )
3626 continue;
3627
3630
3631 if( lb <= curtime && ub + consdata->durations[j] > curtime && lb < ub )
3632 {
3633 SCIP_Real solval;
3634 SCIP_Real score;
3635
3636 solval = SCIPgetSolVal(scip, sol, var);
3637 score = MIN(solval - lb, ub - solval) / ((SCIP_Real)ub-lb);
3638
3639 SCIPdebugMsg(scip, "add var <%s> to branch cand storage\n", SCIPvarGetName(var));
3640 SCIP_CALL( SCIPaddExternBranchCand(scip, var, score, lb + (ub - lb) / 2.0 + 0.2) );
3641 (*nbranchcands)++;
3642
3643 SCIP_CALL( SCIPhashtableInsert(collectedvars, var) );
3644 }
3645 }
3646 }
3647
3648 SCIPhashtableFree(&collectedvars);
3649
3650 SCIPdebugMsg(scip, "found %d branching candidates\n", *nbranchcands);
3651
3652 return SCIP_OKAY;
3653}
3654
3655/** enforcement of an LP, pseudo, or relaxation solution */
3656static
3658 SCIP* scip, /**< SCIP data structure */
3659 SCIP_CONS** conss, /**< constraints to be processed */
3660 int nconss, /**< number of constraints */
3661 SCIP_SOL* sol, /**< solution to enforce (NULL for LP or pseudo solution) */
3662 SCIP_Bool branch, /**< should branching candidates be collected */
3663 SCIP_RESULT* result /**< pointer to store the result */
3664 )
3665{
3666 if( branch )
3667 {
3668 int nbranchcands;
3669
3670 nbranchcands = 0;
3671 SCIP_CALL( collectBranchingCands(scip, conss, nconss, sol, &nbranchcands) );
3672
3673 if( nbranchcands > 0 )
3674 (*result) = SCIP_INFEASIBLE;
3675 }
3676 else
3677 {
3678 SCIP_Bool violated;
3679 int c;
3680
3681 violated = FALSE;
3682
3683 /* first check if a constraints is violated */
3684 for( c = 0; c < nconss && !violated; ++c )
3685 {
3686 SCIP_CONS* cons;
3687
3688 cons = conss[c];
3689 assert(cons != NULL);
3690
3691 SCIP_CALL( checkCons(scip, cons, sol, &violated, FALSE) );
3692 }
3693
3694 if( violated )
3695 (*result) = SCIP_INFEASIBLE;
3696 }
3697
3698 return SCIP_OKAY;
3699}
3700
3701/**@} */
3702
3703/**@name Propagation
3704 *
3705 * @{
3706 */
3707
3708/** check if cumulative constraint is independently of all other constraints */
3709static
3711 SCIP_CONS* cons /**< cumulative constraint */
3712 )
3713{
3714 SCIP_CONSDATA* consdata;
3715 SCIP_VAR** vars;
3716 SCIP_Bool* downlocks;
3717 SCIP_Bool* uplocks;
3718 int nvars;
3719 int v;
3720
3721 consdata = SCIPconsGetData(cons);
3722 assert(consdata != NULL);
3723
3724 nvars = consdata->nvars;
3725 vars = consdata->vars;
3726 downlocks = consdata->downlocks;
3727 uplocks = consdata->uplocks;
3728
3729 /* check if the cumulative constraint has the only locks on the involved variables */
3730 for( v = 0; v < nvars; ++v )
3731 {
3732 SCIP_VAR* var;
3733
3734 var = vars[v];
3735 assert(var != NULL);
3736
3737 if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) > (int)downlocks[v]
3738 || SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) > (int)uplocks[v] )
3739 return FALSE;
3740 }
3741
3742 return TRUE;
3743}
3744
3745/** in case the cumulative constraint is independent of every else, solve the cumulative problem and apply the fixings
3746 * (dual reductions)
3747 */
3748static
3750 SCIP* scip, /**< SCIP data structure */
3751 SCIP_CONS* cons, /**< cumulative constraint */
3752 SCIP_Longint maxnodes, /**< number of branch-and-bound nodes to solve an independent cumulative constraint (-1: no limit) */
3753 int* nchgbds, /**< pointer to store the number changed variable bounds */
3754 int* nfixedvars, /**< pointer to count number of fixings */
3755 int* ndelconss, /**< pointer to count number of deleted constraints */
3756 SCIP_Bool* cutoff, /**< pointer to store if the constraint is infeasible */
3757 SCIP_Bool* unbounded /**< pointer to store if the constraint is unbounded */
3758 )
3759{
3760 SCIP_CONSDATA* consdata;
3761 SCIP_VAR** vars;
3762 SCIP_Real* objvals;
3763 SCIP_Real* lbs;
3764 SCIP_Real* ubs;
3765 SCIP_Real timelimit;
3766 SCIP_Real memorylimit;
3767 SCIP_Bool solved;
3768 SCIP_Bool error;
3769
3770 int ncheckconss;
3771 int nvars;
3772 int v;
3773
3774 assert(scip != NULL);
3775 assert(!SCIPconsIsModifiable(cons));
3776 assert(SCIPgetNConss(scip) > 0);
3777
3778 /* if SCIP is in probing mode or repropagation we cannot perform this dual reductions since this dual reduction
3779 * would/could end in an implication which can lead to cutoff of the/all optimal solution
3780 */
3782 return SCIP_OKAY;
3783
3784 /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
3785 * use the locks to decide for a dual reduction using this constraint;
3786 */
3787 if( !SCIPconsIsChecked(cons) )
3788 return SCIP_OKAY;
3789
3790 ncheckconss = SCIPgetNCheckConss(scip);
3791
3792 /* if the cumulative constraint is the only constraint of the original problem or the only check constraint in the
3793 * presolved problem do nothing execpt to change the parameter settings
3794 */
3795 if( ncheckconss == 1 )
3796 {
3797 /* shrink the minimal maximum value for the conflict length */
3798 SCIP_CALL( SCIPsetIntParam(scip, "conflict/minmaxvars", 10) );
3799
3800 /* use only first unique implication point */
3801 SCIP_CALL( SCIPsetIntParam(scip, "conflict/fuiplevels", 1) );
3802
3803 /* do not use reconversion conflicts */
3804 SCIP_CALL( SCIPsetIntParam(scip, "conflict/reconvlevels", 0) );
3805
3806 /* after 250 conflict we force a restart since then the variable statistics are reasonable initialized */
3807 SCIP_CALL( SCIPsetIntParam(scip, "conflict/restartnum", 250) );
3808
3809 /* increase the number of conflicts which induce a restart */
3810 SCIP_CALL( SCIPsetRealParam(scip, "conflict/restartfac", 2.0) );
3811
3812 /* weight the variable which made into a conflict */
3813 SCIP_CALL( SCIPsetRealParam(scip, "conflict/conflictweight", 1.0) );
3814
3815 /* do not check pseudo solution (for performance reasons) */
3816 SCIP_CALL( SCIPsetBoolParam(scip, "constraints/disableenfops", TRUE) );
3817
3818 /* use value based history to detect a reasonable branching point */
3819 SCIP_CALL( SCIPsetBoolParam(scip, "history/valuebased", TRUE) );
3820
3821 /* turn of LP relaxation */
3822 SCIP_CALL( SCIPsetIntParam(scip, "lp/solvefreq", -1) );
3823
3824 /* prefer the down branch in case the value based history does not suggest something */
3825 SCIP_CALL( SCIPsetCharParam(scip, "nodeselection/childsel", 'd') );
3826
3827 /* accept any bound change */
3828 SCIP_CALL( SCIPsetRealParam(scip, "numerics/boundstreps", 1e-6) );
3829
3830 /* allow for at most 10 restart, after that the value based history should be reliable */
3831 SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 10) );
3832
3833 /* set priority for depth first search to highest possible value */
3834 SCIP_CALL( SCIPsetIntParam(scip, "nodeselection/dfs/stdpriority", INT_MAX/4) );
3835
3836 return SCIP_OKAY;
3837 }
3838
3839 consdata = SCIPconsGetData(cons);
3840 assert(consdata != NULL);
3841
3842 /* check if already tried to solve that constraint as independent sub problem; we do not want to try it again if we
3843 * fail on the first place
3844 */
3845 if( consdata->triedsolving )
3846 return SCIP_OKAY;
3847
3848 /* check if constraint is independently */
3849 if( !isConsIndependently(cons) )
3850 return SCIP_OKAY;
3851
3852 /* mark the constraint to be tried of solving it as independent sub problem; in case that is successful the
3853 * constraint is deleted; otherwise, we want to ensure that we do not try that again
3854 */
3855 consdata->triedsolving = TRUE;
3856
3857 SCIPdebugMsg(scip, "the cumulative constraint <%s> is independent from rest of the problem (%d variables, %d constraints)\n",
3860
3861 nvars = consdata->nvars;
3862 vars = consdata->vars;
3863
3864 SCIP_CALL( SCIPallocBufferArray(scip, &lbs, nvars) );
3865 SCIP_CALL( SCIPallocBufferArray(scip, &ubs, nvars) );
3866 SCIP_CALL( SCIPallocBufferArray(scip, &objvals, nvars) );
3867
3868 for( v = 0; v < nvars; ++v )
3869 {
3870 SCIP_VAR* var;
3871
3872 /* if a variables array is given, use the variable bounds otherwise the default values stored in the ests and lsts
3873 * array
3874 */
3875 var = vars[v];
3876 assert(var != NULL);
3877
3878 lbs[v] = SCIPvarGetLbLocal(var);
3879 ubs[v] = SCIPvarGetUbLocal(var);
3880
3881 objvals[v] = SCIPvarGetObj(var);
3882 }
3883
3884 /* check whether there is enough time and memory left */
3885 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
3886 if( !SCIPisInfinity(scip, timelimit) )
3887 timelimit -= SCIPgetSolvingTime(scip);
3888 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
3889
3890 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
3891 if( !SCIPisInfinity(scip, memorylimit) )
3892 {
3893 memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
3894 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
3895 }
3896
3897 /* solve the cumulative condition separately */
3898 SCIP_CALL( SCIPsolveCumulative(scip, nvars, lbs, ubs, objvals, consdata->durations, consdata->demands, consdata->capacity,
3899 consdata->hmin, consdata->hmax, timelimit, memorylimit, maxnodes, &solved, cutoff, unbounded, &error) );
3900
3901 if( !(*cutoff) && !(*unbounded) && !error )
3902 {
3903 SCIP_Bool infeasible;
3904 SCIP_Bool tightened;
3905 SCIP_Bool allfixed;
3906
3907 allfixed = TRUE;
3908
3909 for( v = 0; v < nvars; ++v )
3910 {
3911 /* check if variable is fixed */
3912 if( lbs[v] + 0.5 > ubs[v] )
3913 {
3914 SCIP_CALL( SCIPfixVar(scip, vars[v], lbs[v], &infeasible, &tightened) );
3915 assert(!infeasible);
3916
3917 if( tightened )
3918 {
3919 (*nfixedvars)++;
3920 consdata->triedsolving = FALSE;
3921 }
3922 }
3923 else
3924 {
3925 SCIP_CALL( SCIPtightenVarLb(scip, vars[v], lbs[v], TRUE, &infeasible, &tightened) );
3926 assert(!infeasible);
3927
3928 if( tightened )
3929 {
3930 (*nchgbds)++;
3931 consdata->triedsolving = FALSE;
3932 }
3933
3934 SCIP_CALL( SCIPtightenVarUb(scip, vars[v], ubs[v], TRUE, &infeasible, &tightened) );
3935 assert(!infeasible);
3936
3937 if( tightened )
3938 {
3939 (*nchgbds)++;
3940 consdata->triedsolving = FALSE;
3941 }
3942
3943 allfixed = FALSE;
3944 }
3945 }
3946
3947 /* if all variables are fixed, remove the cumulative constraint since it is redundant */
3948 if( allfixed )
3949 {
3951 (*ndelconss)++;
3952 }
3953 }
3954
3955 SCIPfreeBufferArray(scip, &objvals);
3958
3959 return SCIP_OKAY;
3960}
3961
3962/** start conflict analysis to analysis the core insertion which is infeasible */
3963static
3965 SCIP* scip, /**< SCIP data structure */
3966 int nvars, /**< number of start time variables (activities) */
3967 SCIP_VAR** vars, /**< array of start time variables */
3968 int* durations, /**< array of durations */
3969 int* demands, /**< array of demands */
3970 int capacity, /**< cumulative capacity */
3971 int hmin, /**< left bound of time axis to be considered (including hmin) */
3972 int hmax, /**< right bound of time axis to be considered (not including hmax) */
3973 SCIP_VAR* infervar, /**< start time variable which lead to the infeasibilty */
3974 int inferduration, /**< duration of the start time variable */
3975 int inferdemand, /**< demand of the start time variable */
3976 int inferpeak, /**< profile preak which causes the infeasibilty */
3977 SCIP_Bool usebdwidening, /**< should bound widening be used during conflict analysis? */
3978 SCIP_Bool* initialized, /**< pointer to store if the conflict analysis was initialized */
3979 SCIP_Bool* explanation /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
3980 )
3981{
3982 SCIPdebugMsg(scip, "detected infeasibility due to adding a core to the core resource profile\n");
3983 SCIPdebugMsg(scip, "variable <%s>[%g,%g] (demand %d, duration %d)\n", SCIPvarGetName(infervar),
3984 SCIPvarGetLbLocal(infervar), SCIPvarGetUbLocal(infervar), inferdemand, inferduration);
3985
3986 /* initialize conflict analysis if conflict analysis is applicable */
3988 {
3990
3991 SCIP_CALL( resolvePropagationCoretimes(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
3992 infervar, inferdemand, inferpeak, inferpeak, NULL, usebdwidening, NULL, explanation) );
3993
3994 SCIPdebugMsg(scip, "add lower and upper bounds of variable <%s>\n", SCIPvarGetName(infervar));
3995
3996 /* add both bound of the inference variable since these biuld the core which we could not inserted */
3997 if( usebdwidening )
3998 {
3999 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, NULL, (SCIP_Real)(inferpeak - inferduration + 1)) );
4000 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, infervar, NULL, (SCIP_Real)inferpeak) );
4001 }
4002 else
4003 {
4004 SCIP_CALL( SCIPaddConflictLb(scip, infervar, NULL) );
4005 SCIP_CALL( SCIPaddConflictUb(scip, infervar, NULL) );
4006 }
4007
4008 *initialized = TRUE;
4009 }
4010
4011 return SCIP_OKAY;
4012}
4013
4014/** We are using the core resource profile which contains all core except the one of the start time variable which we
4015 * want to propagate, to incease the earliest start time. This we are doing in steps of length at most the duration of
4016 * the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict
4017 * analysis
4018 */
4019static
4021 SCIP* scip, /**< SCIP data structure */
4022 int nvars, /**< number of start time variables (activities) */
4023 SCIP_VAR** vars, /**< array of start time variables */
4024 int* durations, /**< array of durations */
4025 int* demands, /**< array of demands */
4026 int capacity, /**< cumulative capacity */
4027 int hmin, /**< left bound of time axis to be considered (including hmin) */
4028 int hmax, /**< right bound of time axis to be considered (not including hmax) */
4029 SCIP_CONS* cons, /**< constraint which is propagated */
4030 SCIP_PROFILE* profile, /**< resource profile */
4031 int idx, /**< position of the variable to propagate */
4032 int* nchgbds, /**< pointer to store the number of bound changes */
4033 SCIP_Bool usebdwidening, /**< should bound widening be used during conflict analysis? */
4034 SCIP_Bool* initialized, /**< was conflict analysis initialized */
4035 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4036 SCIP_Bool* infeasible /**< pointer to store if the constraint is infeasible */
4037 )
4038{
4039 SCIP_VAR* var;
4040 int ntimepoints;
4041 int duration;
4042 int demand;
4043 int peak;
4044 int newlb;
4045 int est;
4046 int lst;
4047 int pos;
4048
4049 var = vars[idx];
4050 assert(var != NULL);
4051
4052 duration = durations[idx];
4053 assert(duration > 0);
4054
4055 demand = demands[idx];
4056 assert(demand > 0);
4057
4060 ntimepoints = SCIPprofileGetNTimepoints(profile);
4061
4062 /* first we find left position of earliest start time (lower bound) in resource profile; this position gives us the
4063 * load which we have at the earliest start time (lower bound)
4064 */
4065 (void) SCIPprofileFindLeft(profile, est, &pos);
4066
4067 SCIPdebugMsg(scip, "propagate earliest start time (lower bound) (pos %d)\n", pos);
4068
4069 /* we now trying to move the earliest start time in steps of at most "duration" length */
4070 do
4071 {
4072 INFERINFO inferinfo;
4073 SCIP_Bool tightened;
4074 int ect;
4075
4076#ifndef NDEBUG
4077 {
4078 /* in debug mode we check that we adjust the search position correctly */
4079 int tmppos;
4080
4081 (void)SCIPprofileFindLeft(profile, est, &tmppos);
4082 assert(pos == tmppos);
4083 }
4084#endif
4085 ect = est + duration;
4086 peak = -1;
4087
4088 /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we
4089 * want a peak which is closest to the earliest completion time
4090 */
4091 do
4092 {
4093 /* check if the profile load conflicts with the demand of the start time variable */
4094 if( SCIPprofileGetLoad(profile, pos) + demand > capacity )
4095 peak = pos;
4096
4097 pos++;
4098 }
4099 while( pos < ntimepoints && SCIPprofileGetTime(profile, pos) < ect );
4100
4101 /* if we found no peak that means current the job could be scheduled at its earliest start time without
4102 * conflicting to the core resource profile
4103 */
4104 /* coverity[check_after_sink] */
4105 if( peak == -1 )
4106 break;
4107
4108 /* the peak position gives us a time point where the start time variable is in conflict with the resource
4109 * profile. That means we have to move it to the next time point in the resource profile but at most to the
4110 * earliest completion time (the remaining move will done in the next loop)
4111 */
4112 newlb = SCIPprofileGetTime(profile, peak+1);
4113 newlb = MIN(newlb, ect);
4114
4115 /* if the earliest start time is greater than the lst we detected an infeasibilty */
4116 if( newlb > lst )
4117 {
4118 SCIPdebugMsg(scip, "variable <%s>: cannot be scheduled\n", SCIPvarGetName(var));
4119
4120 /* use conflict analysis to analysis the core insertion which was infeasible */
4121 SCIP_CALL( analyseInfeasibelCoreInsertion(scip, nvars, vars, durations, demands, capacity, hmin, hmax,
4122 var, duration, demand, newlb-1, usebdwidening, initialized, explanation) );
4123
4124 if( explanation != NULL )
4125 explanation[idx] = TRUE;
4126
4127 *infeasible = TRUE;
4128
4129 break;
4130 }
4131
4132 /* construct the inference information which we are using with the conflict analysis to resolve that particular
4133 * bound change
4134 */
4135 inferinfo = getInferInfo(PROPRULE_1_CORETIMES, idx, newlb-1);
4136
4137 /* perform the bound lower bound change */
4138 if( inferInfoIsValid(inferinfo) )
4139 {
4140 SCIP_CALL( SCIPinferVarLbCons(scip, var, (SCIP_Real)newlb, cons, inferInfoToInt(inferinfo), TRUE, infeasible, &tightened) );
4141 }
4142 else
4143 {
4144 SCIP_CALL( SCIPtightenVarLb(scip, var, (SCIP_Real)newlb, TRUE, infeasible, &tightened) );
4145 }
4146 assert(tightened);
4147 assert(!(*infeasible));
4148
4149 SCIPdebugMsg(scip, "variable <%s> new lower bound <%d> -> <%d>\n", SCIPvarGetName(var), est, newlb);
4150 (*nchgbds)++;
4151
4152 /* for the statistic we count the number of times a lower bound was tightened due the the time-table algorithm */
4154
4155 /* adjust the earliest start time
4156 *
4157 * @note We are taking the lower of the start time variable on purpose instead of newlb. This is due the fact that
4158 * the proposed lower bound might be even strength by be the core which can be the case if aggregations are
4159 * involved.
4160 */
4162 assert(est >= newlb);
4163
4164 /* adjust the search position for the resource profile for the next step */
4165 if( est == SCIPprofileGetTime(profile, peak+1) )
4166 pos = peak + 1;
4167 else
4168 pos = peak;
4169 }
4170 while( est < lst );
4171
4172 return SCIP_OKAY;
4173}
4174
4175/** We are using the core resource profile which contains all core except the one of the start time variable which we
4176 * want to propagate, to decrease the latest start time. This we are doing in steps of length at most the duration of
4177 * the job. The reason for that is, that this makes it later easier to resolve this propagation during the conflict
4178 * analysis
4179 */
4180static
4182 SCIP* scip, /**< SCIP data structure */
4183 SCIP_VAR* var, /**< start time variable to propagate */
4184 int duration, /**< duration of the job */
4185 int demand, /**< demand of the job */
4186 int capacity, /**< cumulative capacity */
4187 SCIP_CONS* cons, /**< constraint which is propagated */
4188 SCIP_PROFILE* profile, /**< resource profile */
4189 int idx, /**< position of the variable to propagate */
4190 int* nchgbds /**< pointer to store the number of bound changes */
4191 )
4192{
4193 int ntimepoints;
4194 int newub;
4195 int peak;
4196 int pos;
4197 int est;
4198 int lst;
4199 int lct;
4200
4201 assert(var != NULL);
4202 assert(duration > 0);
4203 assert(demand > 0);
4204
4207
4208 /* in case the start time variable is fixed do nothing */
4209 if( est == lst )
4210 return SCIP_OKAY;
4211
4212 ntimepoints = SCIPprofileGetNTimepoints(profile);
4213
4214 lct = lst + duration;
4215
4216 /* first we find left position of latest completion time minus 1 (upper bound + duration) in resource profile; That
4217 * is the last time point where the job would run if schedule it at its latest start time (upper bound). This
4218 * position gives us the load which we have at the latest completion time minus one
4219 */
4220 (void) SCIPprofileFindLeft(profile, lct - 1, &pos);
4221
4222 SCIPdebugMsg(scip, "propagate upper bound (pos %d)\n", pos);
4224
4225 if( pos == ntimepoints-1 && SCIPprofileGetTime(profile, pos) == lst )
4226 return SCIP_OKAY;
4227
4228 /* we now trying to move the latest start time in steps of at most "duration" length */
4229 do
4230 {
4231 INFERINFO inferinfo;
4232 SCIP_Bool tightened;
4233 SCIP_Bool infeasible;
4234
4235 peak = -1;
4236
4237#ifndef NDEBUG
4238 {
4239 /* in debug mode we check that we adjust the search position correctly */
4240 int tmppos;
4241
4242 (void)SCIPprofileFindLeft(profile, lct - 1, &tmppos);
4243 assert(pos == tmppos);
4244 }
4245#endif
4246
4247 /* we search for a peak within the core profile which conflicts with the demand of the start time variable; we
4248 * want a peak which is closest to the latest start time
4249 */
4250 do
4251 {
4252 if( SCIPprofileGetLoad(profile, pos) + demand > capacity )
4253 peak = pos;
4254
4255 pos--;
4256 }
4257 while( pos >= 0 && SCIPprofileGetTime(profile, pos+1) > lst);
4258
4259 /* if we found no peak that means the current job could be scheduled at its latest start time without conflicting
4260 * to the core resource profile
4261 */
4262 /* coverity[check_after_sink] */
4263 if( peak == -1 )
4264 break;
4265
4266 /* the peak position gives us a time point where the start time variable is in conflict with the resource
4267 * profile. That means the job has be done until that point. Hence that gives us the latest completion
4268 * time. Note that that we want to move the bound by at most the duration length (the remaining move we are
4269 * doing in the next loop)
4270 */
4271 newub = SCIPprofileGetTime(profile, peak);
4272 newub = MAX(newub, lst) - duration;
4273 assert(newub >= est);
4274
4275 /* construct the inference information which we are using with the conflict analysis to resolve that particular
4276 * bound change
4277 */
4278 inferinfo = getInferInfo(PROPRULE_1_CORETIMES, idx, newub+duration);
4279
4280 /* perform the bound upper bound change */
4281 if( inferInfoIsValid(inferinfo) )
4282 {
4283 SCIP_CALL( SCIPinferVarUbCons(scip, var, (SCIP_Real)newub, cons, inferInfoToInt(inferinfo), TRUE, &infeasible, &tightened) );
4284 }
4285 else
4286 {
4287 SCIP_CALL( SCIPtightenVarUb(scip, var, (SCIP_Real)newub, TRUE, &infeasible, &tightened) );
4288 }
4289 assert(tightened);
4290 assert(!infeasible);
4291
4292 SCIPdebugMsg(scip, "variable <%s>: new upper bound <%d> -> <%d>\n", SCIPvarGetName(var), lst, newub);
4293 (*nchgbds)++;
4294
4295 /* for the statistic we count the number of times a upper bound was tightened due the the time-table algorithm */
4297
4298 /* adjust the latest start and completion time
4299 *
4300 * @note We are taking the upper of the start time variable on purpose instead of newub. This is due the fact that
4301 * the proposed upper bound might be even strength by be the core which can be the case if aggregations are
4302 * involved.
4303 */
4305 assert(lst <= newub);
4306 lct = lst + duration;
4307
4308 /* adjust the search position for the resource profile for the next step */
4309 if( SCIPprofileGetTime(profile, peak) == lct )
4310 pos = peak - 1;
4311 else
4312 pos = peak;
4313 }
4314 while( est < lst );
4315
4316 return SCIP_OKAY;
4317}
4318
4319/** compute for the different earliest start and latest completion time the core energy of the corresponding time
4320 * points
4321 */
4322static
4324 SCIP_PROFILE* profile, /**< core profile */
4325 int nvars, /**< number of start time variables (activities) */
4326 int* ests, /**< array of sorted earliest start times */
4327 int* lcts, /**< array of sorted latest completion times */
4328 int* coreEnergyAfterEst, /**< array to store the core energy after the earliest start time of each job */
4329 int* coreEnergyAfterLct /**< array to store the core energy after the latest completion time of each job */
4330 )
4331{
4332 int ntimepoints;
4333 int energy;
4334 int t;
4335 int v;
4336
4337 ntimepoints = SCIPprofileGetNTimepoints(profile);
4338 t = ntimepoints - 1;
4339 energy = 0;
4340
4341 /* compute core energy after the earliest start time of each job */
4342 for( v = nvars-1; v >= 0; --v )
4343 {
4344 while( t > 0 && SCIPprofileGetTime(profile, t-1) >= ests[v] )
4345 {
4346 assert(SCIPprofileGetLoad(profile, t-1) >= 0);
4347 assert(SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1)>= 0);
4348 energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1));
4349 t--;
4350 }
4351 assert(SCIPprofileGetTime(profile, t) >= ests[v] || t == ntimepoints-1);
4352
4353 /* maybe ests[j] is in-between two timepoints */
4354 if( SCIPprofileGetTime(profile, t) - ests[v] > 0 )
4355 {
4356 assert(t > 0);
4357 coreEnergyAfterEst[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - ests[v]);
4358 }
4359 else
4360 coreEnergyAfterEst[v] = energy;
4361 }
4362
4363 t = ntimepoints - 1;
4364 energy = 0;
4365
4366 /* compute core energy after the latest completion time of each job */
4367 for( v = nvars-1; v >= 0; --v )
4368 {
4369 while( t > 0 && SCIPprofileGetTime(profile, t-1) >= lcts[v] )
4370 {
4371 assert(SCIPprofileGetLoad(profile, t-1) >= 0);
4372 assert(SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1)>= 0);
4373 energy += SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - SCIPprofileGetTime(profile, t-1));
4374 t--;
4375 }
4376 assert(SCIPprofileGetTime(profile, t) >= lcts[v] || t == ntimepoints-1);
4377
4378 /* maybe lcts[j] is in-between two timepoints */
4379 if( SCIPprofileGetTime(profile, t) - lcts[v] > 0 )
4380 {
4381 assert(t > 0);
4382 coreEnergyAfterLct[v] = energy + SCIPprofileGetLoad(profile, t-1) * (SCIPprofileGetTime(profile, t) - lcts[v]);
4383 }
4384 else
4385 coreEnergyAfterLct[v] = energy;
4386 }
4387}
4388
4389/** collect earliest start times, latest completion time, and free energy contributions */
4390static
4392 SCIP* scip, /**< SCIP data structure */
4393 int nvars, /**< number of start time variables (activities) */
4394 SCIP_VAR** vars, /**< array of start time variables */
4395 int* durations, /**< array of durations */
4396 int* demands, /**< array of demands */
4397 int hmin, /**< left bound of time axis to be considered (including hmin) */
4398 int hmax, /**< right bound of time axis to be considered (not including hmax) */
4399 int* permests, /**< array to store the variable positions */
4400 int* ests, /**< array to store earliest start times */
4401 int* permlcts, /**< array to store the variable positions */
4402 int* lcts, /**< array to store latest completion times */
4403 int* ects, /**< array to store earliest completion times of the flexible part of the job */
4404 int* lsts, /**< array to store latest start times of the flexible part of the job */
4405 int* flexenergies /**< array to store the flexible energies of each job */
4406 )
4407{
4408 int v;
4409
4410 for( v = 0; v < nvars; ++ v)
4411 {
4412 int duration;
4413 int leftadjust;
4414 int rightadjust;
4415 int core;
4416 int est;
4417 int lct;
4418 int ect;
4419 int lst;
4420
4421 duration = durations[v];
4422 assert(duration > 0);
4423
4426 ect = est + duration;
4427 lct = lst + duration;
4428
4429 ests[v] = est;
4430 lcts[v] = lct;
4431 permests[v] = v;
4432 permlcts[v] = v;
4433
4434 /* compute core time window which lies within the effective horizon */
4435 core = (int) computeCoreWithInterval(hmin, hmax, ect, lst);
4436
4437 /* compute the number of time steps the job could run before the effective horizon */
4438 leftadjust = MAX(0, hmin - est);
4439
4440 /* compute the number of time steps the job could run after the effective horizon */
4441 rightadjust = MAX(0, lct - hmax);
4442
4443 /* compute for each job the energy which is flexible; meaning not part of the core */
4444 flexenergies[v] = duration - leftadjust - rightadjust - core;
4445 flexenergies[v] = MAX(0, flexenergies[v]);
4446 flexenergies[v] *= demands[v];
4447 assert(flexenergies[v] >= 0);
4448
4449 /* the earliest completion time of the flexible energy */
4450 ects[v] = MIN(ect, lst);
4451
4452 /* the latest start time of the flexible energy */
4453 lsts[v] = MAX(ect, lst);
4454 }
4455}
4456
4457/** try to tighten the lower bound of the given variable */
4458static
4460 SCIP* scip, /**< SCIP data structure */
4461 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
4462 int nvars, /**< number of start time variables (activities) */
4463 SCIP_VAR** vars, /**< array of start time variables */
4464 int* durations, /**< array of durations */
4465 int* demands, /**< array of demands */
4466 int capacity, /**< cumulative capacity */
4467 int hmin, /**< left bound of time axis to be considered (including hmin) */
4468 int hmax, /**< right bound of time axis to be considered (not including hmax) */
4469 SCIP_VAR* var, /**< variable to be considered for upper bound tightening */
4470 int duration, /**< duration of the job */
4471 int demand, /**< demand of the job */
4472 int est, /**< earliest start time of the job */
4473 int ect, /**< earliest completion time of the flexible part of the job */
4474 int lct, /**< latest completion time of the job */
4475 int begin, /**< begin of the time window under investigation */
4476 int end, /**< end of the time window under investigation */
4477 SCIP_Longint energy, /**< available energy for the flexible part of the hob within the time window */
4478 int* bestlb, /**< pointer to strope the best lower bound change */
4479 int* inferinfos, /**< pointer to store the inference information which is need for the (best) lower bound change */
4480 SCIP_Bool* initialized, /**< was conflict analysis initialized */
4481 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4482 SCIP_Bool* cutoff /**< pointer to store if the constraint is infeasible */
4483 )
4484{
4485 int newlb;
4486
4487 assert(begin >= hmin);
4488 assert(end <= hmax);
4489
4490 /* check if the time-table edge-finding should infer bounds */
4491 if( !conshdlrdata->ttefinfer )
4492 return SCIP_OKAY;
4493
4494 /* if the job can be processed completely before or after the time window, nothing can be tightened */
4495 if( est >= end || ect <= begin )
4496 return SCIP_OKAY;
4497
4498 /* if flexible part runs completely within the time window (assuming it is scheduled on its earliest start time), we
4499 * skip since the overload check will do the job
4500 */
4501 if( est >= begin && ect <= end )
4502 return SCIP_OKAY;
4503
4504 /* check if the available energy in the time window is to small to handle the flexible part if it is schedule on its
4505 * earliest start time
4506 */
4507 if( energy >= demand * ((SCIP_Longint) MAX(begin, est) - MIN(end, ect)) )
4508 return SCIP_OKAY;
4509
4510 /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is
4511 * present; therefore, we need to add the core;
4512 *
4513 * @note the variable ect define the earliest completion time of the flexible part of the job; hence we need to
4514 * compute the earliest completion time of the (whole) job
4515 */
4516 energy += computeCoreWithInterval(begin, end, est + duration, lct - duration) * demand;
4517
4518 /* compute a latest start time (upper bound) such that the job consums at most the available energy
4519 *
4520 * @note we can round down the compute duration w.r.t. the available energy
4521 */
4522 newlb = end - (int) (energy / demand);
4523
4524 /* check if we detected an infeasibility which is the case if the new lower bound is larger than the current upper
4525 * bound (latest start time); meaning it is not possible to schedule the job
4526 */
4527 if( newlb > lct - duration )
4528 {
4529 /* initialize conflict analysis if conflict analysis is applicable */
4531 {
4532 SCIP_Real relaxedbd;
4533
4534 assert(SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) < newlb);
4535
4536 /* it is enough to overshoot the upper bound of the variable by one */
4537 relaxedbd = SCIPvarGetUbLocal(var) + 1.0;
4538
4539 /* initialize conflict analysis */
4541
4542 /* added to upper bound (which was overcut be new lower bound) of the variable */
4544
4545 /* analyze the infeasible */
4546 SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
4547 begin, end, var, SCIP_BOUNDTYPE_LOWER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) );
4548
4549 (*initialized) = TRUE;
4550 }
4551
4552 (*cutoff) = TRUE;
4553 }
4554 else if( newlb > (*bestlb) )
4555 {
4556 INFERINFO inferinfo;
4557
4558 assert(newlb > begin);
4559
4560 inferinfo = getInferInfo(PROPRULE_3_TTEF, begin, end);
4561
4562 /* construct inference information */
4563 (*inferinfos) = inferInfoToInt(inferinfo);
4564 (*bestlb) = newlb;
4565 }
4566
4567 return SCIP_OKAY;
4568}
4569
4570/** try to tighten the upper bound of the given variable */
4571static
4573 SCIP* scip, /**< SCIP data structure */
4574 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
4575 int nvars, /**< number of start time variables (activities) */
4576 SCIP_VAR** vars, /**< array of start time variables */
4577 int* durations, /**< array of durations */
4578 int* demands, /**< array of demands */
4579 int capacity, /**< cumulative capacity */
4580 int hmin, /**< left bound of time axis to be considered (including hmin) */
4581 int hmax, /**< right bound of time axis to be considered (not including hmax) */
4582 SCIP_VAR* var, /**< variable to be considered for upper bound tightening */
4583 int duration, /**< duration of the job */
4584 int demand, /**< demand of the job */
4585 int est, /**< earliest start time of the job */
4586 int lst, /**< latest start time of the flexible part of the job */
4587 int lct, /**< latest completion time of the job */
4588 int begin, /**< begin of the time window under investigation */
4589 int end, /**< end of the time window under investigation */
4590 SCIP_Longint energy, /**< available energy for the flexible part of the hob within the time window */
4591 int* bestub, /**< pointer to strope the best upper bound change */
4592 int* inferinfos, /**< pointer to store the inference information which is need for the (best) upper bound change */
4593 SCIP_Bool* initialized, /**< was conflict analysis initialized */
4594 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4595 SCIP_Bool* cutoff /**< pointer to store if the constraint is infeasible */
4596 )
4597{
4598 int newub;
4599
4600 assert(begin >= hmin);
4601 assert(end <= hmax);
4602 assert(est < begin);
4603
4604 /* check if the time-table edge-finding should infer bounds */
4605 if( !conshdlrdata->ttefinfer )
4606 return SCIP_OKAY;
4607
4608 /* if flexible part of the job can be processed completely before or after the time window, nothing can be tightened */
4609 if( lst >= end || lct <= begin )
4610 return SCIP_OKAY;
4611
4612 /* if flexible part runs completely within the time window (assuming it is scheduled on its latest start time), we
4613 * skip since the overload check will do the job
4614 */
4615 if( lst >= begin && lct <= end )
4616 return SCIP_OKAY;
4617
4618 /* check if the available energy in the time window is to small to handle the flexible part of the job */
4619 if( energy >= demand * ((SCIP_Longint) MIN(end, lct) - MAX(begin, lst)) )
4620 return SCIP_OKAY;
4621
4622 /* adjust the available energy for the job; the given available energy assumes that the core of the considered job is
4623 * present; therefore, we need to add the core;
4624 *
4625 * @note the variable lst define the latest start time of the flexible part of the job; hence we need to compute the
4626 * latest start of the (whole) job
4627 */
4628 energy += computeCoreWithInterval(begin, end, est + duration, lct - duration) * demand;
4629 assert(energy >= 0);
4630
4631 /* compute a latest start time (upper bound) such that the job consums at most the available energy
4632 *
4633 * @note we can round down the compute duration w.r.t. the available energy
4634 */
4635 assert(demand > 0);
4636 newub = begin - duration + (int) (energy / demand);
4637
4638 /* check if we detected an infeasibility which is the case if the new upper bound is smaller than the current lower
4639 * bound (earliest start time); meaning it is not possible to schedule the job
4640 */
4641 if( newub < est )
4642 {
4643 /* initialize conflict analysis if conflict analysis is applicable */
4645 {
4646 SCIP_Real relaxedbd;
4647
4648 assert(SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var)) > newub);
4649
4650 /* it is enough to undershoot the lower bound of the variable by one */
4651 relaxedbd = SCIPvarGetLbLocal(var) - 1.0;
4652
4653 /* initialize conflict analysis */
4655
4656 /* added to lower bound (which was undercut be new upper bound) of the variable */
4658
4659 /* analyze the infeasible */
4660 SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
4661 begin, end, var, SCIP_BOUNDTYPE_UPPER, NULL, relaxedbd, conshdlrdata->usebdwidening, explanation) );
4662
4663 (*initialized) = TRUE;
4664 }
4665
4666 (*cutoff) = TRUE;
4667 }
4668 else if( newub < (*bestub) )
4669 {
4670 INFERINFO inferinfo;
4671
4672 assert(newub < begin);
4673
4674 inferinfo = getInferInfo(PROPRULE_3_TTEF, begin, end);
4675
4676 /* construct inference information */
4677 (*inferinfos) = inferInfoToInt(inferinfo);
4678 (*bestub) = newub;
4679 }
4680
4681 return SCIP_OKAY;
4682}
4683
4684/** propagate the upper bounds and "opportunistically" the lower bounds using the time-table edge-finding algorithm */
4685static
4687 SCIP* scip, /**< SCIP data structure */
4688 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
4689 int nvars, /**< number of start time variables (activities) */
4690 SCIP_VAR** vars, /**< array of start time variables */
4691 int* durations, /**< array of durations */
4692 int* demands, /**< array of demands */
4693 int capacity, /**< cumulative capacity */
4694 int hmin, /**< left bound of time axis to be considered (including hmin) */
4695 int hmax, /**< right bound of time axis to be considered (not including hmax) */
4696 int* newlbs, /**< array to buffer new lower bounds */
4697 int* newubs, /**< array to buffer new upper bounds */
4698 int* lbinferinfos, /**< array to store the inference information for the lower bound changes */
4699 int* ubinferinfos, /**< array to store the inference information for the upper bound changes */
4700 int* lsts, /**< array of latest start time of the flexible part in the same order as the variables */
4701 int* flexenergies, /**< array of flexible energies in the same order as the variables */
4702 int* perm, /**< permutation of the variables w.r.t. the non-decreasing order of the earliest start times */
4703 int* ests, /**< array with earliest strart times sorted in non-decreasing order */
4704 int* lcts, /**< array with latest completion times sorted in non-decreasing order */
4705 int* coreEnergyAfterEst, /**< core energy after the earliest start times */
4706 int* coreEnergyAfterLct, /**< core energy after the latest completion times */
4707 SCIP_Bool* initialized, /**< was conflict analysis initialized */
4708 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
4709 SCIP_Bool* cutoff /**< pointer to store if the constraint is infeasible */
4710 )
4711{
4712 int coreEnergyAfterEnd;
4713 SCIP_Longint maxavailable;
4714 SCIP_Longint minavailable;
4715 SCIP_Longint totalenergy;
4716 int nests;
4717 int est;
4718 int lct;
4719 int start;
4720 int end;
4721 int v;
4722
4723 est = INT_MAX;
4724 lct = INT_MIN;
4725
4726 /* compute earliest start and latest completion time of all jobs */
4727 for( v = 0; v < nvars; ++v )
4728 {
4729 start = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[v]));
4730 end = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[v])) + durations[v];
4731
4732 est = MIN(est, start);
4733 lct = MAX(lct, end);
4734 }
4735
4736 /* adjust the effective time horizon */
4737 hmin = MAX(hmin, est);
4738 hmax = MIN(hmax, lct);
4739
4740 end = hmax + 1;
4741 coreEnergyAfterEnd = -1;
4742
4743 maxavailable = ((SCIP_Longint) hmax - hmin) * capacity;
4744 minavailable = maxavailable;
4745 totalenergy = computeTotalEnergy(durations, demands, nvars);
4746
4747 /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */
4748 if( ((SCIP_Longint) lcts[0] - ests[nvars-1]) * capacity >= totalenergy )
4749 return SCIP_OKAY;
4750
4751 nests = nvars;
4752
4753 /* loop over all variable in non-increasing order w.r.t. the latest completion time; thereby, the latest completion
4754 * times define the end of the time interval under investigation
4755 */
4756 for( v = nvars-1; v >= 0 && !(*cutoff); --v )
4757 {
4758 int flexenergy;
4759 int minbegin;
4760 int lbenergy;
4761 int lbcand;
4762 int i;
4763
4764 lct = lcts[v];
4765
4766 /* if the latest completion time is larger then hmax an infeasibility cannot be detected, since after hmax an
4767 * infinity capacity is available; hence we skip that
4768 */
4769 if( lct > hmax )
4770 continue;
4771
4772 /* if the latest completion time is smaller then hmin we have to stop */
4773 if( lct <= hmin )
4774 {
4775 assert(v == 0 || lcts[v-1] <= lcts[v]);
4776 break;
4777 }
4778
4779 /* if the latest completion time equals to previous end time, we can continue since this particular interval
4780 * induced by end was just analyzed
4781 */
4782 if( lct == end )
4783 continue;
4784
4785 assert(lct < end);
4786
4787 /* In case we only want to detect an overload (meaning no bound propagation) we can skip the interval; this is
4788 * the case if the free energy (the energy which is not occupied by any core) is smaller than the previous minimum
4789 * free energy; if so it means that in the next iterate the free-energy cannot be negative
4790 */
4791 if( !conshdlrdata->ttefinfer && end <= hmax && minavailable < maxavailable )
4792 {
4793 SCIP_Longint freeenergy;
4794
4795 assert(coreEnergyAfterLct[v] >= coreEnergyAfterEnd);
4796 assert(coreEnergyAfterEnd >= 0);
4797
4798 /* compute the energy which is not consumed by the cores with in the interval [lct, end) */
4799 freeenergy = capacity * ((SCIP_Longint) end - lct) - coreEnergyAfterLct[v] + coreEnergyAfterEnd;
4800
4801 if( freeenergy <= minavailable )
4802 {
4803 SCIPdebugMsg(scip, "skip latest completion time <%d> (minimum available energy <%" SCIP_LONGINT_FORMAT ">, free energy <%" SCIP_LONGINT_FORMAT ">)\n", lct, minavailable, freeenergy);
4804 continue;
4805 }
4806 }
4807
4808 SCIPdebugMsg(scip, "check intervals ending with <%d>\n", lct);
4809
4810 end = lct;
4811 coreEnergyAfterEnd = coreEnergyAfterLct[v];
4812
4813 flexenergy = 0;
4814 minavailable = maxavailable;
4815 minbegin = hmax;
4816 lbcand = -1;
4817 lbenergy = 0;
4818
4819 /* loop over the job in non-increasing order w.r.t. the earliest start time; these earliest start time are
4820 * defining the beginning of the time interval under investigation; Thereby, the time interval gets wider and
4821 * wider
4822 */
4823 for( i = nests-1; i >= 0; --i )
4824 {
4825 SCIP_VAR* var;
4826 SCIP_Longint freeenergy;
4827 int duration;
4828 int demand;
4829 int begin;
4830 int idx;
4831 int lst;
4832
4833 idx = perm[i];
4834 assert(idx >= 0);
4835 assert(idx < nvars);
4836 assert(!(*cutoff));
4837
4838 /* the earliest start time of the job */
4839 est = ests[i];
4840
4841 /* if the job starts after the current end, we can skip it and do not need to consider it again since the
4842 * latest completion times (which define end) are scant in non-increasing order
4843 */
4844 if( end <= est )
4845 {
4846 nests--;
4847 continue;
4848 }
4849
4850 /* check if the interval has a size such that the total energy fits, if so we can skip all intervals with the
4851 * current ending time
4852 */
4853 if( ((SCIP_Longint) end - est) * capacity >= totalenergy )
4854 break;
4855
4856 var = vars[idx];
4857 assert(var != NULL);
4858
4859 duration = durations[idx];
4860 assert(duration > 0);
4861
4862 demand = demands[idx];
4863 assert(demand > 0);
4864
4865 lct = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) + duration;
4866
4867 /* the latest start time of the free part of the job */
4868 lst = lsts[idx];
4869
4870 /* in case the earliest start time is equal to minbegin, the job lies completely within the time window under
4871 * investigation; hence the overload check will do the the job
4872 */
4873 assert(est <= minbegin);
4874 if( minavailable < maxavailable && est < minbegin )
4875 {
4876 assert(!(*cutoff));
4877
4878 /* try to tighten the upper bound */
4879 SCIP_CALL( tightenUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
4880 var, duration, demand, est, lst, lct, minbegin, end, minavailable, &(newubs[idx]), &(ubinferinfos[idx]),
4881 initialized, explanation, cutoff) );
4882
4883 if( *cutoff )
4884 break;
4885 }
4886
4887 SCIPdebugMsg(scip, "check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, lst of free part <%d>\n",
4888 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, lst);
4889
4890 begin = est;
4891 assert(SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(var)) == est);
4892
4893 /* if the earliest start time is smaller than hmin we can stop here since the next job will not decrease the
4894 * free energy
4895 */
4896 if( begin < hmin )
4897 break;
4898
4899 /* compute the contribution to the flexible energy */
4900 if( lct <= end )
4901 {
4902 /* if the jobs has to finish before the end, all the energy has to be scheduled */
4903 assert(lst >= begin);
4904 assert(flexenergies[idx] >= 0);
4905 flexenergy += flexenergies[idx];
4906 }
4907 else
4908 {
4909 /* the job partly overlaps with the end */
4910 int candenergy;
4911 int energy;
4912
4913 /* compute the flexible energy which is part of the time interval for sure if the job is scheduled
4914 * w.r.t. latest start time
4915 *
4916 * @note we need to be aware of the effective horizon
4917 */
4918 energy = MIN(flexenergies[idx], demands[idx] * MAX(0, (end - lst)));
4919 assert(end - lst < duration);
4920 assert(energy >= 0);
4921
4922 /* adjust the flexible energy of the time interval */
4923 flexenergy += energy;
4924
4925 /* compute the flexible energy of the job which is not part of flexible energy of the time interval */
4926 candenergy = MIN(flexenergies[idx], demands[idx] * (end - begin)) - energy;
4927 assert(candenergy >= 0);
4928
4929 /* check if we found a better candidate */
4930 if( candenergy > lbenergy )
4931 {
4932 lbenergy = candenergy;
4933 lbcand = idx;
4934 }
4935 }
4936
4937 SCIPdebugMsg(scip, "time window [%d,%d) flexible energy <%d>\n", begin, end, flexenergy);
4938 assert(coreEnergyAfterEst[i] >= coreEnergyAfterEnd);
4939
4940 /* compute the energy which is not used yet */
4941 freeenergy = capacity * ((SCIP_Longint) end - begin) - flexenergy - coreEnergyAfterEst[i] + coreEnergyAfterEnd;
4942
4943 /* check overload */
4944 if( freeenergy < 0 )
4945 {
4946 SCIPdebugMsg(scip, "analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
4947
4948 /* initialize conflict analysis if conflict analysis is applicable */
4950 {
4951 /* analyze infeasibilty */
4953
4954 SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
4956 conshdlrdata->usebdwidening, explanation) );
4957
4958 (*initialized) = TRUE;
4959 }
4960
4961 (*cutoff) = TRUE;
4962
4963 /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */
4965
4966 break;
4967 }
4968
4969 /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */
4970 if( lbenergy > 0 && freeenergy < lbenergy )
4971 {
4972 SCIP_Longint energy;
4973 int newlb;
4974 int ect;
4975
4976 ect = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[lbcand])) + durations[lbcand];
4977 lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[lbcand]));
4978
4979 /* remove the energy of our job from the ... */
4980 energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, (SCIP_Longint) end - lsts[lbcand])) * demands[lbcand];
4981
4982 newlb = end - (int)(energy / demands[lbcand]);
4983
4984 if( newlb > lst )
4985 {
4986 /* initialize conflict analysis if conflict analysis is applicable */
4988 {
4989 SCIP_Real relaxedbd;
4990
4991 /* analyze infeasibilty */
4993
4994 relaxedbd = lst + 1.0;
4995
4996 /* added to upper bound (which was overcut be new lower bound) of the variable */
4997 SCIP_CALL( SCIPaddConflictUb(scip, vars[lbcand], NULL) );
4998
4999 SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
5000 begin, end, vars[lbcand], SCIP_BOUNDTYPE_LOWER, NULL, relaxedbd,
5001 conshdlrdata->usebdwidening, explanation) );
5002
5003 (*initialized) = TRUE;
5004 }
5005
5006 (*cutoff) = TRUE;
5007 break;
5008 }
5009 else if( newlb > newlbs[lbcand] )
5010 {
5011 INFERINFO inferinfo;
5012
5013 /* construct inference information */
5014 inferinfo = getInferInfo(PROPRULE_3_TTEF, begin, end);
5015
5016 /* buffer upper bound change */
5017 lbinferinfos[lbcand] = inferInfoToInt(inferinfo);
5018 newlbs[lbcand] = newlb;
5019 }
5020 }
5021
5022 /* check if the current interval has a smaller free energy */
5023 if( minavailable > freeenergy )
5024 {
5025 minavailable = freeenergy;
5026 minbegin = begin;
5027 }
5028 assert(minavailable >= 0);
5029 }
5030 }
5031
5032 return SCIP_OKAY;
5033}
5034
5035/** propagate the lower bounds and "opportunistically" the upper bounds using the time-table edge-finding algorithm */
5036static
5038 SCIP* scip, /**< SCIP data structure */
5039 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
5040 int nvars, /**< number of start time variables (activities) */
5041 SCIP_VAR** vars, /**< array of start time variables */
5042 int* durations, /**< array of durations */
5043 int* demands, /**< array of demands */
5044 int capacity, /**< cumulative capacity */
5045 int hmin, /**< left bound of time axis to be considered (including hmin) */
5046 int hmax, /**< right bound of time axis to be considered (not including hmax) */
5047 int* newlbs, /**< array to buffer new lower bounds */
5048 int* newubs, /**< array to buffer new upper bounds */
5049 int* lbinferinfos, /**< array to store the inference information for the lower bound changes */
5050 int* ubinferinfos, /**< array to store the inference information for the upper bound changes */
5051 int* ects, /**< array of earliest completion time of the flexible part in the same order as the variables */
5052 int* flexenergies, /**< array of flexible energies in the same order as the variables */
5053 int* perm, /**< permutation of the variables w.r.t. the non-decreasing order of the latest completion times */
5054 int* ests, /**< array with earliest strart times sorted in non-decreasing order */
5055 int* lcts, /**< array with latest completion times sorted in non-decreasing order */
5056 int* coreEnergyAfterEst, /**< core energy after the earliest start times */
5057 int* coreEnergyAfterLct, /**< core energy after the latest completion times */
5058 SCIP_Bool* initialized, /**< was conflict analysis initialized */
5059 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
5060 SCIP_Bool* cutoff /**< pointer to store if the constraint is infeasible */
5061 )
5062{
5063 int coreEnergyAfterStart;
5064 SCIP_Longint maxavailable;
5065 SCIP_Longint minavailable;
5066 SCIP_Longint totalenergy;
5067 int nlcts;
5068 int begin;
5069 int minest;
5070 int maxlct;
5071 int start;
5072 int end;
5073 int v;
5074
5075 if( *cutoff )
5076 return SCIP_OKAY;
5077
5078 begin = hmin - 1;
5079
5080 minest = INT_MAX;
5081 maxlct = INT_MIN;
5082
5083 /* compute earliest start and latest completion time of all jobs */
5084 for( v = 0; v < nvars; ++v )
5085 {
5086 start = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[v]));
5087 end = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[v])) + durations[v];
5088
5089 minest = MIN(minest, start);
5090 maxlct = MAX(maxlct, end);
5091 }
5092
5093 /* adjust the effective time horizon */
5094 hmin = MAX(hmin, minest);
5095 hmax = MIN(hmax, maxlct);
5096
5097 maxavailable = ((SCIP_Longint) hmax - hmin) * capacity;
5098 totalenergy = computeTotalEnergy(durations, demands, nvars);
5099
5100 /* check if the smallest interval has a size such that the total energy fits, if so we can skip the propagator */
5101 if( ((SCIP_Longint) lcts[0] - ests[nvars-1]) * capacity >= totalenergy )
5102 return SCIP_OKAY;
5103
5104 nlcts = 0;
5105
5106 /* loop over all variable in non-decreasing order w.r.t. the earliest start times; thereby, the earliest start times
5107 * define the start of the time interval under investigation
5108 */
5109 for( v = 0; v < nvars; ++v )
5110 {
5111 int flexenergy;
5112 int minend;
5113 int ubenergy;
5114 int ubcand;
5115 int est;
5116 int i;
5117
5118 est = ests[v];
5119
5120 /* if the earliest start time is smaller then hmin an infeasibility cannot be detected, since before hmin an
5121 * infinity capacity is available; hence we skip that
5122 */
5123 if( est < hmin )
5124 continue;
5125
5126 /* if the earliest start time is larger or equal then hmax we have to stop */
5127 if( est >= hmax )
5128 break;
5129
5130 /* if the latest earliest start time equals to previous start time, we can continue since this particular interval
5131 * induced by start was just analyzed
5132 */
5133 if( est == begin )
5134 continue;
5135
5136 assert(est > begin);
5137
5138 SCIPdebugMsg(scip, "check intervals starting with <%d>\n", est);
5139
5140 begin = est;
5141 coreEnergyAfterStart = coreEnergyAfterEst[v];
5142
5143 flexenergy = 0;
5144 minavailable = maxavailable;
5145 minend = hmin;
5146 ubcand = -1;
5147 ubenergy = 0;
5148
5149 /* loop over the job in non-decreasing order w.r.t. the latest completion time; these latest completion times are
5150 * defining the ending of the time interval under investigation; thereby, the time interval gets wider and wider
5151 */
5152 for( i = nlcts; i < nvars; ++i )
5153 {
5154 SCIP_VAR* var;
5155 SCIP_Longint freeenergy;
5156 int duration;
5157 int demand;
5158 int idx;
5159 int lct;
5160 int ect;
5161
5162 idx = perm[i];
5163 assert(idx >= 0);
5164 assert(idx < nvars);
5165 assert(!(*cutoff));
5166
5167 /* the earliest start time of the job */
5168 lct = lcts[i];
5169
5170 /* if the job has a latest completion time before the the current start, we can skip it and do not need to
5171 * consider it again since the earliest start times (which define the start) are scant in non-decreasing order
5172 */
5173 if( lct <= begin )
5174 {
5175 nlcts++;
5176 continue;
5177 }
5178
5179 /* check if the interval has a size such that the total energy fits, if so we can skip all intervals which
5180 * start with current beginning time
5181 */
5182 if( ((SCIP_Longint) lct - begin) * capacity >= totalenergy )
5183 break;
5184
5185 var = vars[idx];
5186 assert(var != NULL);
5187
5188 duration = durations[idx];
5189 assert(duration > 0);
5190
5191 demand = demands[idx];
5192 assert(demand > 0);
5193
5195
5196 /* the earliest completion time of the flexible part of the job */
5197 ect = ects[idx];
5198
5199 /* in case the latest completion time is equal to minend, the job lies completely within the time window under
5200 * investigation; hence the overload check will do the the job
5201 */
5202 assert(lct >= minend);
5203 if( minavailable < maxavailable && lct > minend )
5204 {
5205 assert(!(*cutoff));
5206
5207 /* try to tighten the upper bound */
5208 SCIP_CALL( tightenLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5209 var, duration, demand, est, ect, lct, begin, minend, minavailable, &(newlbs[idx]), &(lbinferinfos[idx]),
5210 initialized, explanation, cutoff) );
5211
5212 if( *cutoff )
5213 return SCIP_OKAY;
5214 }
5215
5216 SCIPdebugMsg(scip, "check variable <%s>[%g,%g] (duration %d, demands %d, est <%d>, ect of free part <%d>\n",
5217 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), duration, demand, est, ect);
5218
5219 end = lct;
5220 assert(SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(var)) + duration == lct);
5221
5222 /* if the latest completion time is larger than hmax we can stop here since the next job will not decrease the
5223 * free energy
5224 */
5225 if( end > hmax )
5226 break;
5227
5228 /* compute the contribution to the flexible energy */
5229 if( est >= begin )
5230 {
5231 /* if the jobs has to finish before the end, all the energy has to be scheduled */
5232 assert(ect <= end);
5233 assert(flexenergies[idx] >= 0);
5234 flexenergy += flexenergies[idx];
5235 }
5236 else
5237 {
5238 /* the job partly overlaps with the end */
5239 int candenergy;
5240 int energy;
5241
5242 /* compute the flexible energy which is part of the time interval for sure if the job is scheduled
5243 * w.r.t. latest start time
5244 *
5245 * @note we need to be aware of the effective horizon
5246 */
5247 energy = MIN(flexenergies[idx], demands[idx] * MAX(0, (ect - begin)));
5248 assert(ect - begin < duration);
5249 assert(energy >= 0);
5250
5251 /* adjust the flexible energy of the time interval */
5252 flexenergy += energy;
5253
5254 /* compute the flexible energy of the job which is not part of flexible energy of the time interval */
5255 candenergy = MIN(flexenergies[idx], demands[idx] * (end - begin)) - energy;
5256 assert(candenergy >= 0);
5257
5258 /* check if we found a better candidate */
5259 if( candenergy > ubenergy )
5260 {
5261 ubenergy = candenergy;
5262 ubcand = idx;
5263 }
5264 }
5265
5266 SCIPdebugMsg(scip, "time window [%d,%d) flexible energy <%d>\n", begin, end, flexenergy);
5267 assert(coreEnergyAfterLct[i] <= coreEnergyAfterStart);
5268
5269 /* compute the energy which is not used yet */
5270 freeenergy = capacity * ((SCIP_Longint) end - begin) - flexenergy - coreEnergyAfterStart + coreEnergyAfterLct[i];
5271
5272 /* check overload */
5273 if( freeenergy < 0 )
5274 {
5275 SCIPdebugMsg(scip, "analyze overload within time window [%d,%d) capacity %d\n", begin, end, capacity);
5276
5277 /* initialize conflict analysis if conflict analysis is applicable */
5279 {
5280 /* analyze infeasibilty */
5282
5283 SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
5285 conshdlrdata->usebdwidening, explanation) );
5286
5287 (*initialized) = TRUE;
5288 }
5289
5290 (*cutoff) = TRUE;
5291
5292 /* for the statistic we count the number of times a cutoff was detected due the time-time-edge-finding */
5294
5295 return SCIP_OKAY;
5296 }
5297
5298 /* check if the available energy is not sufficent to schedule the flexible energy of the best candidate job */
5299 if( ubenergy > 0 && freeenergy < ubenergy )
5300 {
5301 SCIP_Longint energy;
5302 int newub;
5303 int lst;
5304
5305 duration = durations[ubcand];
5306 assert(duration > 0);
5307
5308 ect = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[ubcand])) + duration;
5309 lst = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[ubcand]));
5310
5311 /* remove the energy of our job from the ... */
5312 energy = freeenergy + (computeCoreWithInterval(begin, end, ect, lst) + MAX(0, (SCIP_Longint) ects[ubcand] - begin)) * demands[ubcand];
5313
5314 newub = begin - duration + (int)(energy / demands[ubcand]);
5315
5316 if( newub < ect - duration )
5317 {
5318 /* initialize conflict analysis if conflict analysis is applicable */
5320 {
5321 SCIP_Real relaxedbd;
5322 /* analyze infeasibilty */
5324
5325 relaxedbd = ect - duration - 1.0;
5326
5327 /* added to lower bound (which was undercut be new upper bound) of the variable */
5328 SCIP_CALL( SCIPaddConflictUb(scip, vars[ubcand], NULL) );
5329
5330 SCIP_CALL( analyzeEnergyRequirement(scip, nvars, vars, durations, demands, capacity,
5331 begin, end, vars[ubcand], SCIP_BOUNDTYPE_UPPER, NULL, relaxedbd,
5332 conshdlrdata->usebdwidening, explanation) );
5333
5334 (*initialized) = TRUE;
5335 }
5336
5337 (*cutoff) = TRUE;
5338 return SCIP_OKAY;
5339 }
5340 else if( newub < newubs[ubcand] )
5341 {
5342 INFERINFO inferinfo;
5343
5344 /* construct inference information */
5345 inferinfo = getInferInfo(PROPRULE_3_TTEF, begin, end);
5346
5347 /* buffer upper bound change */
5348 ubinferinfos[ubcand] = inferInfoToInt(inferinfo);
5349 newubs[ubcand] = newub;
5350 }
5351 }
5352
5353 /* check if the current interval has a smaller free energy */
5354 if( minavailable > freeenergy )
5355 {
5356 minavailable = freeenergy;
5357 minend = end;
5358 }
5359 assert(minavailable >= 0);
5360 }
5361 }
5362
5363 return SCIP_OKAY;
5364}
5365
5366/** checks whether the instance is infeasible due to a overload within a certain time frame using the idea of time-table
5367 * edge-finding
5368 *
5369 * @note The algorithm is based on the following two papers:
5370 * - Petr Vilim, "Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources", In: Tobias
5371 * Achterberg and J. Christopher Beck (Eds.), Integration of AI and OR Techniques in Constraint Programming for
5372 * Combinatorial Optimization Problems (CPAIOR 2011), LNCS 6697, pp 230--245
5373 * - Andreas Schutt, Thibaut Feydy, and Peter J. Stuckey, "Explaining Time-Table-Edge-Finding Propagation for the
5374 * Cumulative Resource Constraint (submitted to CPAIOR 2013)
5375 */
5376static
5378 SCIP* scip, /**< SCIP data structure */
5379 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
5380 SCIP_PROFILE* profile, /**< current core profile */
5381 int nvars, /**< number of start time variables (activities) */
5382 SCIP_VAR** vars, /**< array of start time variables */
5383 int* durations, /**< array of durations */
5384 int* demands, /**< array of demands */
5385 int capacity, /**< cumulative capacity */
5386 int hmin, /**< left bound of time axis to be considered (including hmin) */
5387 int hmax, /**< right bound of time axis to be considered (not including hmax) */
5388 SCIP_CONS* cons, /**< constraint which is propagated (needed to SCIPinferVar**Cons()) */
5389 int* nchgbds, /**< pointer to store the number of bound changes */
5390 SCIP_Bool* initialized, /**< was conflict analysis initialized */
5391 SCIP_Bool* explanation, /**< bool array which marks the variable which are part of the explanation if a cutoff was detected, or NULL */
5392 SCIP_Bool* cutoff /**< pointer to store if the constraint is infeasible */
5393 )
5394{
5395 int* coreEnergyAfterEst;
5396 int* coreEnergyAfterLct;
5397 int* flexenergies;
5398 int* permests;
5399 int* permlcts;
5400 int* lcts;
5401 int* ests;
5402 int* ects;
5403 int* lsts;
5404
5405 int* newlbs;
5406 int* newubs;
5407 int* lbinferinfos;
5408 int* ubinferinfos;
5409
5410 int v;
5411
5412 /* check if a cutoff was already detected */
5413 if( (*cutoff) )
5414 return SCIP_OKAY;
5415
5416 /* check if at least the basic overload checking should be perfomed */
5417 if( !conshdlrdata->ttefcheck )
5418 return SCIP_OKAY;
5419
5420 SCIPdebugMsg(scip, "run time-table edge-finding overload checking\n");
5421
5422 SCIP_CALL( SCIPallocBufferArray(scip, &coreEnergyAfterEst, nvars) );
5423 SCIP_CALL( SCIPallocBufferArray(scip, &coreEnergyAfterLct, nvars) );
5424 SCIP_CALL( SCIPallocBufferArray(scip, &flexenergies, nvars) );
5425 SCIP_CALL( SCIPallocBufferArray(scip, &permlcts, nvars) );
5426 SCIP_CALL( SCIPallocBufferArray(scip, &permests, nvars) );
5427 SCIP_CALL( SCIPallocBufferArray(scip, &lcts, nvars) );
5428 SCIP_CALL( SCIPallocBufferArray(scip, &ests, nvars) );
5429 SCIP_CALL( SCIPallocBufferArray(scip, &ects, nvars) );
5430 SCIP_CALL( SCIPallocBufferArray(scip, &lsts, nvars) );
5431
5432 SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, nvars) );
5433 SCIP_CALL( SCIPallocBufferArray(scip, &newubs, nvars) );
5434 SCIP_CALL( SCIPallocBufferArray(scip, &lbinferinfos, nvars) );
5435 SCIP_CALL( SCIPallocBufferArray(scip, &ubinferinfos, nvars) );
5436
5437 /* we need to buffer the bound changes since the propagation algorithm cannot handle new bound dynamically */
5438 for( v = 0; v < nvars; ++v )
5439 {
5440 newlbs[v] = SCIPconvertRealToInt(scip, SCIPvarGetLbLocal(vars[v]));
5441 newubs[v] = SCIPconvertRealToInt(scip, SCIPvarGetUbLocal(vars[v]));
5442 lbinferinfos[v] = 0;
5443 ubinferinfos[v] = 0;
5444 }
5445
5446 /* collect earliest start times, latest completion time, and free energy contributions */
5447 collectDataTTEF(scip, nvars, vars, durations, demands, hmin, hmax, permests, ests, permlcts, lcts, ects, lsts, flexenergies);
5448
5449 /* sort the earliest start times and latest completion in non-decreasing order */
5450 SCIPsortIntInt(ests, permests, nvars);
5451 SCIPsortIntInt(lcts, permlcts, nvars);
5452
5453 /* compute for the different earliest start and latest completion time the core energy of the corresponding time
5454 * points
5455 */
5456 computeCoreEnergyAfter(profile, nvars, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct);
5457
5458 /* propagate the upper bounds and "opportunistically" the lower bounds */
5459 SCIP_CALL( propagateUbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5460 newlbs, newubs, lbinferinfos, ubinferinfos, lsts, flexenergies,
5461 permests, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );
5462
5463 /* propagate the lower bounds and "opportunistically" the upper bounds */
5464 SCIP_CALL( propagateLbTTEF(scip, conshdlrdata, nvars, vars, durations, demands, capacity, hmin, hmax,
5465 newlbs, newubs, lbinferinfos, ubinferinfos, ects, flexenergies,
5466 permlcts, ests, lcts, coreEnergyAfterEst, coreEnergyAfterLct, initialized, explanation, cutoff) );
5467
5468 /* apply the buffer bound changes */
5469 for( v = 0; v < nvars && !(*cutoff); ++v )
5470 {
5471 SCIP_Bool infeasible;
5472 SCIP_Bool tightened;
5473
5474 if( inferInfoIsValid(intToInferInfo(lbinferinfos[v])) )
5475 {
5476 SCIP_CALL( SCIPinferVarLbCons(scip, vars[v], (SCIP_Real)newlbs[v], cons, lbinferinfos[v],
5477 TRUE, &infeasible, &tightened) );
5478 }
5479 else
5480 {
5481 SCIP_CALL( SCIPtightenVarLb(scip, vars[v], (SCIP_Real)newlbs[v], TRUE, &infeasible, &tightened) );
5482 }
5483
5484 /* since we change first the lower bound of the variable an infeasibilty should not be detected */
5485 assert(!infeasible);
5486
5487 if( tightened )
5488 {
5489 (*nchgbds)++;
5490
5491 /* for the statistic we count the number of times a cutoff was detected due the time-time */
5493 }
5494
5495 if( inferInfoIsValid(intToInferInfo(ubinferinfos[v])) )
5496 {
5497 SCIP_CALL( SCIPinferVarUbCons(scip, vars[v], (SCIP_Real)newubs[v], cons, ubinferinfos[v],
5498 TRUE, &infeasible, &tightened) );
5499 }
5500 else
5501 {
5502 SCIP_CALL( SCIPtightenVarUb(scip, vars[v], (SCIP_Real)newubs[v], TRUE, &infeasible, &tightened) );
5503 }
5504
5505 /* since upper bound was compute w.r.t. the "old" bound the previous lower bound update together with this upper
5506 * bound update can be infeasible
5507 */
5508 if( infeasible )
5509 {
5510 /* a small performance improvement is possible here: if the tighten...TEFF and propagate...TEFF methods would
5511 * return not only the inferinfos, but the actual begin and end values, then the infeasibility here could also
5512 * be analyzed in the case when begin and end exceed the 15 bit limit
5513 */
5515 {
5516 INFERINFO inferinfo;
5517 SCIP_VAR* var;
5518 int begin;
5519 int end;
5520
5521 var = vars[v];
5522 assert(var != NULL);
5523
5524 /* initialize conflict analysis */
5526
5527 /* convert int to inference information */
5528 inferinfo = intToInferInfo(ubinferinfos[v]);
5529
5530 /* collect time window from inference information */
5531 begin = inferInfoGetData1(inferinfo);
5532 end = inferInfoGetData2(inferinfo);
5533 assert(begin < end);
5534
5535 /* added to lower bound (which was undercut be new upper bound) of the variable */