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