Scippy

SCIP

Solving Constraint Integer Programs

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