Scippy

SCIP

Solving Constraint Integer Programs

prop_genvbounds.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file prop_genvbounds.c
26 * @ingroup DEFPLUGINS_PROP
27 * @brief generalized variable bounds propagator
28 * @author Stefan Weltge
29 * @author Ambros Gleixner
30 * @author Benjamin Mueller
31 */
32
33/**@todo should we only discard events catched from nodes that are not the current node's ancestors? */
34/**@todo improve computation of minactivity */
35/**@todo for multaggr vars on left-hand side, create a linear constraint, probably in exitpre */
36
37/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38
40#include "scip/cons_linear.h"
41#include "scip/debug.h"
43#include "scip/pub_event.h"
44#include "scip/pub_message.h"
45#include "scip/pub_misc.h"
46#include "scip/pub_prop.h"
47#include "scip/pub_var.h"
48#include "scip/scip_conflict.h"
49#include "scip/scip_cons.h"
51#include "scip/scip_event.h"
52#include "scip/scip_general.h"
53#include "scip/scip_mem.h"
54#include "scip/scip_message.h"
55#include "scip/scip_numerics.h"
56#include "scip/scip_param.h"
57#include "scip/scip_prob.h"
58#include "scip/scip_probing.h"
59#include "scip/scip_prop.h"
60#include "scip/scip_sol.h"
61#include "scip/scip_solve.h"
63#include "scip/scip_tree.h"
64#include "scip/scip_var.h"
65#include <string.h>
66
67#define PROP_NAME "genvbounds"
68#define PROP_DESC "generalized variable bounds propagator"
69#define PROP_TIMING SCIP_PROPTIMING_ALWAYS
70#define PROP_PRIORITY 3000000 /**< propagator priority */
71#define PROP_FREQ 1 /**< propagator frequency */
72#define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators
73 * found reductions? */
74#define PROP_PRESOL_PRIORITY -2000000 /**< priority of the presolving method (>= 0: before, < 0: after
75 * constraint handlers); combined with presolvers */
76#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */
77#define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates
78 * in (-1: no limit) */
79#define DEFAULT_GLOBAL_PROPAGATION TRUE /**< apply global propagation? */
80#define DEFAULT_PROPAGATE_IN_ROOT_NODE TRUE /**< apply genvbounds in root node if no new incumbent was found? */
81#define DEFAULT_SORT TRUE /**< sort genvbounds and wait for bound change events? (otherwise all
82 * genvbounds are applied in each node) */
83#define DEFAULT_PROPASCONSS FALSE /**< should genvbounds be transformed to (linear) constraints? */
84
85#define EVENTHDLR_NAME "genvbounds"
86#define EVENTHDLR_DESC "event handler for generalized variable bounds propagator"
87
88
89/*
90 * Data structures
91 */
92
93/** GenVBound data */
95{
96 SCIP_VAR** vars; /**< pointers to variables x_j occurring in this generalized variable
97 * bound */
98 SCIP_VAR* var; /**< pointer to variable x_i */
99 SCIP_Real* coefs; /**< coefficients a_j of the variables listed in vars */
100 SCIP_Real constant; /**< constant term in generalized variable bound */
101 SCIP_Real cutoffcoef; /**< cutoff bound's coefficient */
102 int coefssize; /**< size of coefs array */
103 int index; /**< index of this genvbound in genvboundstore array */
104 int ncoefs; /**< number of nonzero coefficients a_j */
105 SCIP_BOUNDTYPE boundtype; /**< type of bound provided by the genvbound, SCIP_BOUNDTYPE_LOWER/UPPER
106 * if +/- x_i on left-hand side */
107 SCIP_Bool relaxonly; /**< contains a relaxation-only variable */
108};
109typedef struct GenVBound GENVBOUND;
110
111/** starting indices data structure */
112struct SCIP_EventData
113{
114 SCIP_PROP* prop; /**< pointer to genvbounds propagator */
115 SCIP_VAR* var; /**< variable */
116 int* startindices; /**< array to store the first indices of genvbounds in components that are
117 * impacted by a change of this bound */
118 int* startcomponents; /**< array to store the components corresponding to startindices array */
119 int nstarts; /**< number of indices stored in startindices array */
120 int startindicessize; /**< size of the startindices and startcomponents arrays */
121};
122
123/** propagator data */
124struct SCIP_PropData
125{
126 GENVBOUND** genvboundstore; /**< array to store genvbounds; fast access is provided by hashmaps
127 * lbgenvbounds and ubgenvbounds */
128 SCIP_EVENTDATA** lbevents; /**< array of lower bound event data */
129 SCIP_EVENTDATA** ubevents; /**< array of upper bound event data */
130 SCIP_EVENTHDLR* eventhdlr; /**< genvbounds propagator event handler */
131 SCIP_HASHMAP* lbgenvbounds; /**< hashmap to provide fast access to lower bound genvbounds in
132 * genvboundstore array */
133 SCIP_HASHMAP* ubgenvbounds; /**< hashmap to provide fast access to upper bound genvbounds in
134 * genvboundstore array */
135 SCIP_HASHMAP* lbeventsmap; /**< hashmap to provide fast access to lbevents array */
136 SCIP_HASHMAP* ubeventsmap; /**< hashmap to provide fast access to ubevents array */
137 SCIP_HASHMAP* startmap; /**< hashmap to provide fast access to startindices array */
138 SCIP_PROP* prop; /**< pointer to genvbounds propagator */
139 SCIP_NODE* lastnodecaught; /**< last node where events for starting indices were caught */
140 SCIP_VAR* cutoffboundvar; /**< artificial variable representing primal cutoff bound */
141 int* componentsstart; /**< stores the components starting indices in genvboundstore array; the
142 * entry componentsstart[ncomponents] is equal to ngenvbounds, which
143 * makes it easier to iterate over all components */
144 int componentsstartsize;/**< size of componentsstart array */
145 int* startindices; /**< storing indices of components where local propagation should start */
146 int* startcomponents; /**< components corresponding to indices stored in startindices array */
147 int startindicessize; /**< size of startindices and startcomponents arrays */
148 int* gstartindices; /**< storing indices of components where global propagation, i.e.,
149 * propagation of an improved primal bound, should start */
150 int* gstartcomponents; /**< components corresponding to indices stored in gstartindices array */
151 int gstartindicessize; /**< size of gstartindices and gstartcomponents arrays */
152 SCIP_Real lastcutoff; /**< cutoff bound's value last time genvbounds propagator was called */
153 int genvboundstoresize; /**< size of genvboundstore array */
154 int ngenvbounds; /**< number of genvbounds stored in genvboundstore array */
155 int ncomponents; /**< number of components in genvboundstore array */
156 int nindices; /**< number of indices stored in startindices array */
157 int ngindices; /**< number of indices stored in gstartindices array */
158 int nlbevents; /**< number of data entries in lbevents array */
159 int nubevents; /**< number of data entries in ubevents array */
160 SCIP_Bool issorted; /**< stores wether array genvboundstore is topologically sorted */
161 SCIP_Bool global; /**< apply global propagation? */
162 SCIP_Bool propinrootnode; /**< apply genvbounds in root node if no new incumbent was found? */
163 SCIP_Bool sort; /**< sort genvbounds and wait for bound change events? (otherwise all
164 * genvbounds are applied in each node) */
165 SCIP_Bool propasconss; /**< should genvbounds be transformed to (linear) constraints? */
166};
167
168
169/*
170 * Local methods
171 */
172
173/** returns correct cutoff bound value */
174static
176 SCIP* scip /**< SCIP data structure */
177 )
178{
179 assert(scip != NULL);
180
181 SCIPdebugMsg(scip, "cutoff = %.9g (%.9g + %.9g * %.9g)\n",
184
185 /* the cutoff bound is valid w.r.t. the current objective function in the transformed problem; during presolving,
186 * however, the objective function can change (e.g., when a variable is fixed, its contribution in the objective is
187 * subtracted from the cutoff bound and added to the objective offset); we solve this by transforming the
188 * contribution of the cutoff bound in the generalized variable bound to the original problem as described in
189 * function SCIPgenVBoundAdd()
190 */
192}
193
194/** returns corresponding genvbound in genvboundstore if there is one, NULL otherwise */
195static
197 SCIP* scip, /**< SCIP data structure */
198 SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */
199 SCIP_VAR* var, /**< bounds variable */
200 SCIP_BOUNDTYPE boundtype /**< bounds type */
201 )
202{
203 SCIP_HASHMAP* hashmap;
204
205 assert(scip != NULL);
206 assert(propdata != NULL);
207 assert(var != NULL);
208
209 hashmap = boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds;
210
211 return (GENVBOUND*) SCIPhashmapGetImage(hashmap, var);
212}
213
214#ifdef SCIP_DEBUG
215/** prints a genvbound as debug message */
216static
217void printGenVBound(
218 SCIP* scip, /**< SCIP data structure */
219 GENVBOUND* genvbound /**< genvbound to be printed */
220 )
221{
222 SCIP_Bool first;
223 int i;
224
225 assert(genvbound != NULL);
226
227 if( genvbound->boundtype == SCIP_BOUNDTYPE_UPPER )
228 {
229 SCIPdebugMsgPrint(scip, "- ");
230 }
231
232 SCIPdebugMsgPrint(scip, "<%s> >= ", SCIPvarGetName(genvbound->var));
233
234 first = TRUE;
235 for( i = 0; i < genvbound->ncoefs; i++ )
236 {
237 if( !first )
238 {
239 SCIPdebugMsgPrint(scip, " + ");
240 }
241
242 SCIPdebugMsgPrint(scip, "%g * <%s>", genvbound->coefs[i], SCIPvarGetName(genvbound->vars[i]));
243
244 first = FALSE;
245 }
246
247 if( !SCIPisZero(scip, genvbound->cutoffcoef) )
248 {
249 SCIPdebugMsgPrint(scip, " + %g * cutoff_bound", genvbound->cutoffcoef);
250 }
251
252 if( !SCIPisZero(scip, genvbound->constant) )
253 {
254 SCIPdebugMsgPrint(scip, " + %g", genvbound->constant);
255 }
256
257 SCIPdebugMsgPrint(scip, "\n");
258}
259#endif
260
261/** calculates the minactivity of a linear combination of variables stored in an array */
262static
264 SCIP* scip, /**< SCIP data structure */
265 SCIP_VAR** vars, /**< array of variables */
266 SCIP_Real* coefs, /**< array of coefficients */
267 int nvars, /**< number of variables */
268 SCIP_Bool global /**< use global variable bounds? */
269 )
270{
271 SCIP_Real minval;
272 int i;
273
274 assert(scip != NULL);
275 assert(vars != NULL);
276 assert(coefs != NULL);
277 assert(nvars >= 0);
278
279 minval = 0.0;
280
281 for( i = 0; i < nvars; i++ )
282 {
284
285 /* get global or local bound */
286 if( global )
287 bound = coefs[i] > 0.0 ? SCIPvarGetLbGlobal(vars[i]) : SCIPvarGetUbGlobal(vars[i]);
288 else
289 bound = coefs[i] > 0.0 ? SCIPvarGetLbLocal(vars[i]) : SCIPvarGetUbLocal(vars[i]);
290
291 /* with infinite bounds we cannot compute a valid minactivity and return minus infinity */
293 return -SCIPinfinity(scip);
294
295 /* add contribution to minactivity */
296 minval += coefs[i] * bound;
297 }
298
299 return minval;
300}
301
302/** calculates the minactivity of a linear combination of variables stored in the current conflict set */
303static
305 SCIP* scip, /**< SCIP data structure */
306 SCIP_VAR** vars, /**< array of variables */
307 SCIP_Real* coefs, /**< array of coefficients */
308 int nvars, /**< number of variables */
309 SCIP_BDCHGIDX* bdchgidx /**< bound change at which minactivity should be computed; if NULL use local bounds */
310 )
311{
312 SCIP_Real minval;
313 int i;
314
315 assert(scip != NULL);
316 assert(vars != NULL);
317 assert(coefs != NULL);
318 assert(nvars >= 0);
319
320 minval = 0.0;
321
322 for( i = 0; i < nvars; i++ )
323 {
325
326 if( coefs[i] > 0.0 )
327 {
328 /* get bound at current bound change */
329 bound = SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE);
330
331 /* if bdchgidx is NULL, assert that we use local bounds */
332 assert(bdchgidx != NULL || SCIPisEQ(scip, bound, SCIPvarGetLbLocal(vars[i])));
333
334 /* if bdchgidx is not NULL, use the possibly tighter bound already in the current conflict set */
335 if( bdchgidx != NULL && SCIPgetConflictVarLb(scip, vars[i]) > bound )
336 bound = SCIPgetConflictVarLb(scip, vars[i]);
337 }
338 else
339 {
340 /* get bound at current bound change */
341 bound = SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE);
342
343 /* if bdchgidx is NULL, assert that we use local bounds */
344 assert(bdchgidx != NULL || SCIPisEQ(scip, bound, SCIPvarGetUbLocal(vars[i])));
345
346 /* if bdchgidx is not NULL, use the possibly tighter bound already in the current conflict set */
347 if( bdchgidx != NULL && SCIPgetConflictVarUb(scip, vars[i]) < bound )
348 bound = SCIPgetConflictVarUb(scip, vars[i]);
349 }
350
351 /* with infinite bounds we cannot compute a valid minactivity and return minus infinity */
353 return -SCIPinfinity(scip);
354
355 /* add contribution to minactivity */
356 minval += coefs[i] * bound;
357 }
358
359 return minval;
360}
361
362/** returns a valid bound given by a generalized variable bound */
363static
365 SCIP* scip, /**< SCIP data structure */
366 GENVBOUND* genvbound, /**< generalized variable bound */
367 SCIP_Bool global /**< use global variable bounds? */
368 )
369{
370 SCIP_Real boundval;
371
372 assert(scip != NULL);
373 assert(genvbound != NULL);
374
375 boundval = getGenVBoundsMinActivity(scip, genvbound->vars, genvbound->coefs, genvbound->ncoefs, global);
376
377 if( SCIPisInfinity(scip, -boundval) )
378 return (genvbound->boundtype == SCIP_BOUNDTYPE_LOWER) ? -SCIPinfinity(scip) : SCIPinfinity(scip);
379
380 if( genvbound->cutoffcoef != 0.0 )
381 boundval += genvbound->cutoffcoef * getCutoffboundGenVBound(scip);
382
383 boundval += genvbound->constant;
384
385 if( genvbound->boundtype == SCIP_BOUNDTYPE_UPPER )
386 boundval *= -1.0;
387
388 return boundval;
389}
390
391#ifdef WITH_DEBUG_SOLUTION
392/** checks whether a generalized variable bound violates the debug solution */
393static
394SCIP_RETCODE checkDebugSolutionGenVBound(
395 SCIP* scip, /**< SCIP data structure */
396 GENVBOUND* genvbound /**< generalized variable bound */
397 )
398{
399 SCIP_SOL* debugsol;
400 SCIP_Real activity;
401 SCIP_Real solval;
402 int i;
403
404 assert(scip != NULL);
405 assert(genvbound != NULL);
406
407 if( !SCIPdebugIsMainscip(scip) )
408 return SCIP_OKAY;
409
410 /* the genvbound must be valid for all cutoff bounds greater equal the objective value of the debug solution */
411 SCIP_CALL( SCIPdebugGetSol(scip, &debugsol) );
412
413 /* check whether a debug solution is available */
414 if( debugsol == NULL )
415 return SCIP_OKAY;
416
417 activity = 0.0;
418 for( i = 0; i < genvbound->ncoefs; i++ )
419 {
420 SCIP_CALL( SCIPdebugGetSolVal(scip, genvbound->vars[i], &solval) );
421 if( solval != SCIP_UNKNOWN || solval != SCIP_INVALID )
422 activity += genvbound->coefs[i] * solval;
423 else
424 printf("***** debug: ignoring variable with %s value in debug solution\n",
425 solval == SCIP_UNKNOWN ? "unknown" : "invalid");
426 }
427
428 activity += genvbound->cutoffcoef *
430 activity += genvbound->constant;
431
432 SCIP_CALL( SCIPdebugGetSolVal(scip, genvbound->var, &solval) );
433 if( solval != SCIP_UNKNOWN || solval != SCIP_INVALID )
434 {
435 if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER )
436 {
437 SCIP_CALL( SCIPdebugCheckLbGlobal(scip, genvbound->var, activity) );
438 }
439 else if( genvbound->boundtype == SCIP_BOUNDTYPE_UPPER )
440 {
441 SCIP_CALL( SCIPdebugCheckUbGlobal(scip, genvbound->var, -activity) );
442 }
443 }
444
445 return SCIP_OKAY;
446}
447#endif
448
449/** allocate local and global startindices, startcomponents and startmap */
450static
452 SCIP* scip, /**< SCIP data structure */
453 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
454 )
455{
456 assert(scip != NULL);
457 assert(propdata != NULL);
458
459 assert(propdata->startcomponents == NULL);
460 assert(propdata->startindices == NULL);
461 assert(propdata->startmap == NULL);
462 assert(propdata->nindices == -1);
463
464 assert(propdata->gstartindices == NULL);
465 assert(propdata->gstartcomponents == NULL);
466 assert(propdata->ngindices == -1);
467
468 assert(propdata->ngenvbounds >= 1);
469 assert(propdata->ncomponents >= 1);
470
471 SCIPdebugMsg(scip, "create starting data\n");
472
473 /* allocate memory for arrays */
474 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->startindices), propdata->ncomponents) );
475 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->startcomponents), propdata->ncomponents) );
476 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->gstartindices), propdata->ncomponents) );
477 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->gstartcomponents), propdata->ncomponents) );
478 propdata->startindicessize = propdata->ncomponents;
479 propdata->gstartindicessize = propdata->ncomponents;
480
481 /* create hashmap */
482 SCIP_CALL( SCIPhashmapCreate(&(propdata->startmap), SCIPblkmem(scip), propdata->ncomponents) );
483
484 propdata->nindices = 0;
485 propdata->ngindices = 0;
486
487 return SCIP_OKAY;
488}
489
490/** free local and global startindices, startcomponents and startmap */
491static
493 SCIP* scip, /**< SCIP data structure */
494 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
495 )
496{
497 assert(scip != NULL);
498 assert(propdata != NULL);
499
500 SCIPdebugMsg(scip, "free starting data\n");
501
502 if( propdata->startcomponents != NULL )
503 {
504 assert(propdata->startindices != NULL);
505 assert(propdata->startmap != NULL);
506 assert(propdata->nindices >= 0);
507
508 SCIPfreeBlockMemoryArray(scip, &(propdata->startindices), propdata->startindicessize);
509 SCIPfreeBlockMemoryArray(scip, &(propdata->startcomponents), propdata->startindicessize);
510 propdata->startindicessize = 0;
511 SCIPhashmapFree(&(propdata->startmap));
512 propdata->nindices = -1;
513
514 assert(propdata->gstartindices != NULL);
515 assert(propdata->gstartcomponents != NULL);
516 assert(propdata->ngindices >= 0);
517
518 SCIPfreeBlockMemoryArray(scip, &(propdata->gstartindices), propdata->gstartindicessize);
519 SCIPfreeBlockMemoryArray(scip, &(propdata->gstartcomponents), propdata->gstartindicessize);
520 propdata->gstartindicessize = 0;
521 propdata->ngindices = -1;
522 }
523
524 assert(propdata->startcomponents == NULL);
525 assert(propdata->startindices == NULL);
526 assert(propdata->startmap == NULL);
527 assert(propdata->nindices == -1);
528
529 assert(propdata->gstartindices == NULL);
530 assert(propdata->gstartcomponents == NULL);
531 assert(propdata->ngindices == -1);
532
533 return SCIP_OKAY;
534}
535
536static
538 SCIP* scip, /**< SCIP data structure */
539 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
540 )
541{
542 int i;
543
544 assert(scip != NULL);
545 assert(propdata != NULL);
546
547 assert(propdata->gstartindices != NULL);
548 assert(propdata->gstartcomponents != NULL);
549 assert(propdata->ngindices == 0);
550
551 SCIPdebugMsg(scip, "fill global starting data\n");
552
553 for( i = 0; i < propdata->ncomponents; i++ )
554 {
555 int j;
556
557 for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ ) /*lint !e679*/
558 {
559 assert(j < propdata->ngenvbounds);
560
561 if( !SCIPisZero(scip, propdata->genvboundstore[j]->cutoffcoef) )
562 {
563 assert(SCIPisNegative(scip, propdata->genvboundstore[j]->cutoffcoef));
564
565 propdata->gstartcomponents[propdata->ngindices] = i;
566 propdata->gstartindices[propdata->ngindices] = j;
567
568 /* go to next component */
569 propdata->ngindices++;
570 break;
571 }
572 }
573 }
574
575 /* resize arrays */
576 if( propdata->gstartindicessize != propdata->ngindices )
577 {
578 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->gstartindices), propdata->gstartindicessize, \
579 propdata->ngindices) );
580 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->gstartcomponents), propdata->gstartindicessize, \
581 propdata->ngindices) );
582 propdata->gstartindicessize = propdata->ngindices;
583 }
584
585 return SCIP_OKAY;
586}
587
588
589/** resets local starting data */
590static
592 SCIP* scip, /**< SCIP data structure */
593 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
594 )
595{
596 assert(scip != NULL);
597 assert(propdata != NULL);
598 assert(propdata->startcomponents != NULL);
599 assert(propdata->startindices != NULL);
600 assert(propdata->startmap != NULL);
601 assert(propdata->nindices >= 0);
602
603 SCIP_CALL( SCIPhashmapRemoveAll(propdata->startmap) );
604 propdata->nindices = 0;
605
606 return SCIP_OKAY;
607}
608
609/** frees sorted components data */
610static
612 SCIP* scip, /**< SCIP data structure */
613 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
614 )
615{
616 assert(scip != NULL);
617 assert(propdata != NULL);
618
619 SCIPdebugMsg(scip, "free components data\n");
620
621 if( propdata->componentsstart != NULL )
622 {
623 assert(propdata->ncomponents > 0);
624
625 SCIPfreeBlockMemoryArray(scip, &(propdata->componentsstart), propdata->componentsstartsize);
626 propdata->componentsstartsize = 0;
627 propdata->ncomponents = -1;
628 }
629
630 assert(propdata->componentsstart == NULL);
631 assert(propdata->ncomponents == -1);
632
633 return SCIP_OKAY;
634}
635
636/** frees memory allocated for a generalized variable bound */
637static
639 SCIP* scip,
640 GENVBOUND* genvbound
641 )
642{
643 int i;
644
645 assert(scip != NULL);
646 assert(genvbound != NULL);
647 assert(genvbound->coefs != NULL);
648 assert(genvbound->vars != NULL);
649 assert(genvbound->var != NULL);
650
651 /* release variables */
652 for( i = 0; i < genvbound->ncoefs; ++i )
653 {
654 assert(genvbound->vars[i] != NULL);
655 SCIP_CALL( SCIPreleaseVar(scip, &(genvbound->vars[i])) );
656 }
657 SCIP_CALL( SCIPreleaseVar(scip, &genvbound->var) );
658
659 /* free memory */
660 SCIPfreeBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize);
661 SCIPfreeBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize);
662 SCIPfreeBlockMemory(scip, &genvbound);
663
664 return SCIP_OKAY;
665}
666
667/** helper function to release all genvbounds */
668static
670 SCIP* scip,
671 SCIP_PROPDATA* propdata
672 )
673{
674 int i;
675
676 assert(scip != NULL);
677 assert(propdata != NULL);
678
679 if( propdata->genvboundstore != NULL )
680 {
681 /* free genvbounds */
682 for( i = propdata->ngenvbounds - 1; i >= 0; i-- )
683 {
684 SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) );
685 }
686
687 /* free genvboundstore hashmaps */
688 SCIPhashmapFree(&(propdata->lbgenvbounds));
689 SCIPhashmapFree(&(propdata->ubgenvbounds));
690
691 /* free genvboundstore array */
692 SCIPfreeBlockMemoryArray(scip, &(propdata->genvboundstore), propdata->genvboundstoresize);
693
694 /* set the number of genvbounds to zero */
695 propdata->ngenvbounds = 0;
696
697 /* free componentsstart array */
698 SCIP_CALL( freeComponentsData(scip, propdata) );
699
700 /* free starting indices data */
701 SCIP_CALL( freeStartingData(scip, propdata) );
702
703 /* release the cutoffboundvar and undo the locks */
704 if( propdata->cutoffboundvar != NULL )
705 {
706 SCIP_CALL( SCIPaddVarLocksType(scip, propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL, -1, -1) );
707 SCIP_CALL( SCIPreleaseVar(scip, &(propdata->cutoffboundvar)) );
708 propdata->cutoffboundvar = NULL;
709 SCIPdebugMsg(scip, "release cutoffboundvar!\n");
710 }
711 }
712
713 return SCIP_OKAY;
714}
715
716/** helper function to release relax-only genvbounds */
717static
719 SCIP* scip,
720 SCIP_PROPDATA* propdata
721 )
722{
723 SCIP_Bool freedgenvbound;
724 int i;
725
726 assert(scip != NULL);
727 assert(propdata != NULL);
728
729 if( propdata->genvboundstore == NULL )
730 return SCIP_OKAY;
731
732 /* free genvbounds */
733 freedgenvbound = FALSE;
734 for( i = 0 ; i < propdata->ngenvbounds; )
735 {
736 if( propdata->genvboundstore[i]->relaxonly )
737 {
738 SCIP_CALL( SCIPhashmapRemove(propdata->genvboundstore[i]->boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds,
739 propdata->genvboundstore[i]->var) );
740
741 SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) );
742 if( i != propdata->ngenvbounds-1 )
743 {
744 propdata->genvboundstore[i] = propdata->genvboundstore[propdata->ngenvbounds-1];
745 propdata->genvboundstore[i]->index = i;
746 }
747 --propdata->ngenvbounds;
748
749 propdata->issorted = FALSE;
750 freedgenvbound = TRUE;
751 }
752 else
753 ++i;
754 }
755
756 if( freedgenvbound )
757 {
758 /* free componentsstart array */
759 SCIP_CALL( freeComponentsData(scip, propdata) );
760
761 /* free starting indices data */
762 SCIP_CALL( freeStartingData(scip, propdata) );
763 }
764
765 return SCIP_OKAY;
766}
767
768/** resolves propagation of lower bound on +/- left-hand side variable of a generalized variable bound */
769static
771 SCIP* scip, /**< SCIP data structure */
772 GENVBOUND* genvbound, /**< genvbound data structure */
773 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */
774 SCIP_Real* boundval, /**< pointer to lower bound value on +/- left-hand side variable */
775 SCIP_Bool* success /**< was the explanation succesful? */
776 )
777{
778 SCIP_VAR* lhsvar;
779 SCIP_VAR** vars;
780 SCIP_Real minactivity;
781 SCIP_Real tmpboundval;
782 SCIP_Real slack;
783 int nvars;
784 int i;
785
786 assert(scip != NULL);
787 assert(genvbound != NULL);
788 assert(boundval != NULL);
789 assert(success != NULL);
790
791 *success = FALSE;
792
793 /* get left-hand side variable */
794 lhsvar = genvbound->var;
795 assert(lhsvar != NULL);
796
797 /* get right-hand side variables */
798 vars = genvbound->vars;
799 nvars = genvbound->ncoefs;
800 assert(vars != NULL);
801
802 /* if only the primal bound participates in the propagation, it is globally valid and should not be analyzed */
803 assert(nvars > 0);
804
805 /* when resolving a propagation, bdchgidx is not NULL and boundval should be the bound change performed for the
806 * left-hand side variable
807 */
808 assert(bdchgidx == NULL || genvbound->boundtype != SCIP_BOUNDTYPE_LOWER || SCIPisEQ(scip,
809 SCIPvarIsIntegral(genvbound->var) ? SCIPfeasCeil(scip, *boundval) : *boundval, SCIPgetVarLbAtIndex(scip, lhsvar, bdchgidx, TRUE)));
810 assert(bdchgidx == NULL || genvbound->boundtype != SCIP_BOUNDTYPE_UPPER || SCIPisEQ(scip,
811 SCIPvarIsIntegral(genvbound->var) ? SCIPfeasCeil(scip, *boundval) : *boundval, -SCIPgetVarUbAtIndex(scip, lhsvar, bdchgidx, TRUE)));
812
813 /* when creating an initial conflict, bdchgidx is NULL and +/-boundval must exceed the upper/lower bound of the
814 * left-hand side variable
815 */
816 assert(bdchgidx != NULL || genvbound->boundtype != SCIP_BOUNDTYPE_LOWER
817 || SCIPisGT(scip, *boundval, SCIPvarGetUbLocal(lhsvar)));
818 assert(bdchgidx != NULL || genvbound->boundtype != SCIP_BOUNDTYPE_UPPER
819 || SCIPisGT(scip, *boundval, -SCIPvarGetLbLocal(lhsvar)));
820
821 SCIPdebugMsg(scip, "resolving genvbound propagation: lhs=%s<%s> >= boundval=%.15g\n",
822 genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? "+" : "-", SCIPvarGetName(lhsvar), *boundval);
823
824 /* subtract constant terms from bound value */
825 tmpboundval = *boundval;
826 tmpboundval -= genvbound->cutoffcoef * getCutoffboundGenVBound(scip);
827 tmpboundval -= genvbound->constant;
828
829 SCIPdebugMsg(scip, "subtracting constant terms gives boundval=%.15g\n", tmpboundval);
830
831 /* compute minimal activity; if bdchgidx is NULL, we create the initial conflict and use local bounds */
832 minactivity = getGenVBoundsMinActivityConflict(scip, genvbound->vars, genvbound->coefs, genvbound->ncoefs, bdchgidx);
833
834 SCIPdebugMsg(scip, "minactivity of right-hand side is minactivity=%.15g\n", minactivity);
835
836 /* a genvbound might have been replaced since the propagation took place, hence we have to check that the current
837 * genvbound can explain the propagation at the given bound change index; note that by now, with smaller cutoff
838 * bound, we might even perform a stronger propagation
839 */
840 if( SCIPisLT(scip, minactivity, tmpboundval) )
841 {
842 SCIPdebugMsg(scip, "minactivity is too small to explain propagation; was genvbound replaced?\n");
843 return SCIP_OKAY;
844 }
845
846 /* if bdchgidx is NULL, i.e., we create the initial conflict, we should be able to explain the bound change */
847 assert(SCIPisGE(scip, minactivity, tmpboundval));
848
849 slack = MAX(minactivity - tmpboundval, 0.0);
850
851 SCIPdebugMsg(scip, "slack=%.15g\n", slack);
852
853 /* add variables on the right-hand side as reasons for propagation */
854 for( i = 0; i < nvars; i++ )
855 {
856 assert(vars[i] != NULL);
857 assert(SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE)));
858 assert(SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE)));
859
860 /* coefficient is positive */
861 if( genvbound->coefs[i] > 0.0 )
862 {
863 SCIP_Real lbatindex;
864 SCIP_Real conflictlb;
865
866 /* get bound at current bound change */
867 lbatindex = SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE);
868
869 /* get bound already enforced by conflict set */
870 conflictlb = SCIPgetConflictVarLb(scip, genvbound->vars[i]);
871 assert(SCIPisGE(scip, conflictlb, SCIPvarGetLbGlobal(genvbound->vars[i])));
872
873 SCIPdebugMsg(scip, "lower bound of variable <%s> (genvbound->vars[%d]) in conflict set / at index is %.15g / %.15g\n",
874 SCIPvarGetName(genvbound->vars[i]), i, conflictlb, lbatindex);
875
876 /* if bound is already enforced by conflict set we do not need to add the bound change; since we used the
877 * tighest bound already when computing the initial minactivity, the slack is already correct
878 */
879 if( SCIPisLE(scip, lbatindex, conflictlb) )
880 {
881 SCIPdebugMsg(scip, "skipping lower bound of variable <%s> (genvbound->vars[%d]) already enforced in conflict set\n",
882 SCIPvarGetName(genvbound->vars[i]), i);
883 }
884 else
885 {
886 SCIP_Real relaxedlb;
887
888 /* compute relaxed bound that would suffice to explain the bound change */
889 relaxedlb = lbatindex - (slack / genvbound->coefs[i]);
890 assert(relaxedlb <= lbatindex);
891
892 /* add variable to conflict set */
893 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, genvbound->vars[i], bdchgidx, relaxedlb ) );
894
895 /* get new bound of variable in conflict set; after possible bound widening in SCIPaddConflictLbRelaxed(),
896 * it should be between conflictlb and lbatindex
897 */
898 relaxedlb = SCIPgetConflictVarLb(scip, genvbound->vars[i]);
899 assert(SCIPisGE(scip, relaxedlb, conflictlb));
900 assert(SCIPisLE(scip, relaxedlb, lbatindex));
901
902 /* update slack and ensure that its nonegative */
903 slack -= genvbound->coefs[i] * (lbatindex - relaxedlb);
904 slack = MAX(slack, 0.0);
905
906 SCIPdebugMsg(scip, "added lower bound of variable <%s> (genvbound->vars[%d]); new slack=%.15g\n",
907 SCIPvarGetName(genvbound->vars[i]), i, slack);
908 }
909 }
910 /* coefficient is negative */
911 else
912 {
913 SCIP_Real ubatindex;
914 SCIP_Real conflictub;
915
916 /* get bound at current bound change */
917 ubatindex = SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE);
918
919 /* get bound already enforced by conflict set */
920 conflictub = SCIPgetConflictVarUb(scip, genvbound->vars[i]);
921 assert(SCIPisLE(scip, conflictub, SCIPvarGetUbGlobal(genvbound->vars[i])));
922
923 SCIPdebugMsg(scip, "upper bound of variable <%s> (genvbound->vars[%d]) in conflict set / at index is %.15g / %.15g\n",
924 SCIPvarGetName(genvbound->vars[i]), i, conflictub, ubatindex);
925
926 /* if bound is already enforced by conflict set we do not need to add the bound change; since we used the
927 * tighest bound already when computing the initial minactivity, the slack is already correct
928 */
929 if( SCIPisGE(scip, ubatindex, conflictub) )
930 {
931 SCIPdebugMsg(scip, "skipping upper bound of variable <%s> (genvbound->vars[%d]) already enforced in conflict set\n",
932 SCIPvarGetName(genvbound->vars[i]), i);
933 }
934 else
935 {
936 SCIP_Real relaxedub;
937
938 /* compute relaxed bound that would suffice to explain the bound change */
939 relaxedub = ubatindex - (slack / genvbound->coefs[i]);
940 assert(relaxedub >= ubatindex);
941
942 /* add variable to conflict set */
943 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, genvbound->vars[i], bdchgidx, relaxedub ) );
944
945 /* get new bound of variable in conflict set; after possible bound widening in SCIPaddConflictUbRelaxed(),
946 * it should be between conflictub and ubatindex
947 */
948 relaxedub = SCIPgetConflictVarUb(scip, genvbound->vars[i]);
949 assert(SCIPisLE(scip, relaxedub, conflictub));
950 assert(SCIPisGE(scip, relaxedub, ubatindex));
951
952 /* update slack and ensure that its nonegative */
953 slack -= genvbound->coefs[i] * (ubatindex - relaxedub);
954 slack = MAX(slack, 0.0);
955
956 SCIPdebugMsg(scip, "added upper bound of variable <%s> (genvbound->vars[%d]); new slack=%.15g\n",
957 SCIPvarGetName(genvbound->vars[i]), i, slack);
958 }
959 }
960 }
961
962 /* if slack is positive, return increased boundval */
963 if( SCIPisPositive(scip, slack) )
964 tmpboundval += slack;
965
966 /* add constant terms again */
967 tmpboundval += genvbound->cutoffcoef * getCutoffboundGenVBound(scip);
968 tmpboundval += genvbound->constant;
969
970 /* boundval should not have been decreased; if this happened nevertheless, maybe due to numerical errors, we quit
971 * without success
972 */
973 if( SCIPisLT(scip, tmpboundval, *boundval) )
974 {
975 SCIPdebugMsg(scip, "boundval was reduced from %.15g to %.15g; propagation not resolved\n", *boundval, tmpboundval);
976 return SCIP_OKAY;
977 }
978
979 /* return widened boundval */
980 *boundval = tmpboundval;
981 *success = TRUE;
982
983 return SCIP_OKAY;
984}
985
986/** create initial conflict */
987static
989 SCIP* scip, /**< SCIP data structure */
990 GENVBOUND* genvbound /**< genvbound data structure */
991 )
992{
993 SCIP_Bool success;
994
995 assert(scip != NULL);
996 assert(genvbound != NULL);
997
998 /* check if conflict analysis is applicable */
1000 return SCIP_OKAY;
1001
1002 /* initialize conflict analysis */
1004
1005 /* left-hand side variable >= ... */
1006 if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER )
1007 {
1008 SCIP_Real infeasthreshold;
1010
1011 /* get minimal right-hand side bound that leads to infeasibility; first try with a factor of 2 for robustness */
1012 bound = REALABS(SCIPvarGetUbLocal(genvbound->var));
1013 infeasthreshold = MAX(bound, 1.0) * 2 * SCIPfeastol(scip);
1014 bound = SCIPvarGetUbLocal(genvbound->var) + infeasthreshold;
1015
1016 /* add right-hand side variables that force the lower bound of the left-hand side variable above its upper bound
1017 * to conflict set
1018 */
1019 SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) );
1020 assert(!success || SCIPisFeasGT(scip, bound, SCIPvarGetUbLocal(genvbound->var)));
1021
1022 /* if infeasibility cannot be proven with the tighter bound, try with actual bound */
1023 if( !success )
1024 {
1025 bound = REALABS(SCIPvarGetUbLocal(genvbound->var));
1026 infeasthreshold = MAX(bound, 1.0) * SCIPfeastol(scip);
1027 bound = SCIPvarGetUbLocal(genvbound->var) + infeasthreshold;
1028
1029 SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) );
1030 success = success && SCIPisFeasGT(scip, bound, SCIPvarGetUbLocal(genvbound->var));
1031 }
1032
1033 /* compute upper bound on left-hand side variable that leads to infeasibility */
1034 bound -= infeasthreshold;
1035 success = success && SCIPisGE(scip, bound, SCIPvarGetUbLocal(genvbound->var));
1036
1037 /* initial reason could not be constructed, maybe due to numerics; do not apply conflict analysis */
1038 if( !success )
1039 {
1040 SCIPdebugMsg(scip, "strange: could not create initial reason to start conflict analysis\n");
1041 return SCIP_OKAY;
1042 }
1043
1044 /* if bound is already enforced by conflict set we do not have to add it */
1045 if( SCIPisGE(scip, bound, SCIPgetConflictVarUb(scip, genvbound->var)) )
1046 {
1047 SCIPdebugMsg(scip, "skipping upper bound of left-hand side variable <%s> already enforced in conflict set\n",
1048 SCIPvarGetName(genvbound->var));
1049 }
1050 else
1051 {
1052 SCIPdebugMsg(scip, "adding upper bound of left-hand side variable <%s>\n", SCIPvarGetName(genvbound->var));
1053
1055 }
1056 }
1057 /* left-hand side variable <= ..., i.e., - left-hand side variable >= ... */
1058 else
1059 {
1060 SCIP_Real infeasthreshold;
1062
1063 /* get minimal right-hand side bound that leads to infeasibility; try with a factor of 2 first for robustness */
1064 bound = REALABS(SCIPvarGetLbLocal(genvbound->var));
1065 infeasthreshold = MAX(bound, 1.0) * 2 * SCIPfeastol(scip);
1066 bound = -SCIPvarGetLbLocal(genvbound->var) + infeasthreshold;
1067
1068 /* add right-hand side variables that force the upper bound of the left-hand side variable below its lower bound
1069 * to conflict set
1070 */
1071 SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) );
1072 assert(!success || SCIPisFeasLT(scip, -bound, SCIPvarGetLbLocal(genvbound->var)));
1073
1074 /* if infeasibility cannot be proven with the tighter bound, try with actual bound */
1075 if( !success )
1076 {
1077 bound = REALABS(SCIPvarGetLbLocal(genvbound->var));
1078 infeasthreshold = MAX(bound, 1.0) * SCIPfeastol(scip);
1079 bound = -SCIPvarGetLbLocal(genvbound->var) + infeasthreshold;
1080
1081 SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) );
1082 success = success && SCIPisFeasLT(scip, -bound, SCIPvarGetLbLocal(genvbound->var));
1083 }
1084
1085 /* compute lower bound on left-hand side variable that leads to infeasibility */
1086 bound = -bound + infeasthreshold;
1087 success = success && SCIPisLE(scip, bound, SCIPvarGetLbLocal(genvbound->var));
1088
1089 /* initial reason could not be constructed, maybe due to numerics; do not apply conflict analysis */
1090 if( !success )
1091 {
1092 SCIPdebugMsg(scip, "strange: could not create initial reason to start conflict analysis\n");
1093 return SCIP_OKAY;
1094 }
1095
1096 /* if bound is already enforced by conflict set we do not have to add it */
1097 if( SCIPisLE(scip, bound, SCIPgetConflictVarLb(scip, genvbound->var)) )
1098 {
1099 SCIPdebugMsg(scip, "skipping lower bound of left-hand side variable <%s> already enforced in conflict set\n",
1100 SCIPvarGetName(genvbound->var));
1101 }
1102 else
1103 {
1104 SCIPdebugMsg(scip, "adding lower bound of left-hand side variable <%s>\n", SCIPvarGetName(genvbound->var));
1105
1107 }
1108 }
1109
1110 /* analyze the conflict */
1112
1113 return SCIP_OKAY;
1114}
1115
1116/** apply propagation for one generalized variable bound; also if the left-hand side variable is locally fixed, we
1117 * compute the right-hand side minactivity to possibly detect infeasibility
1118 */
1119static
1121 SCIP* scip, /**< SCIP data structure */
1122 SCIP_PROP* prop, /**< genvbounds propagator */
1123 GENVBOUND* genvbound, /**< genvbound data structure */
1124 SCIP_Bool global, /**< apply global bound changes? (global: true, local: false)*/
1125 SCIP_RESULT* result, /**< result pointer */
1126 int* nchgbds /**< counter to increment if bound was tightened */
1127 )
1128{
1129 SCIP_Real boundval;
1130 SCIP_Bool infeas;
1131 SCIP_Bool tightened;
1132
1133 assert(scip != NULL);
1134 assert(genvbound != NULL);
1135 assert(genvbound->var != NULL);
1136 assert(SCIPvarGetStatus(genvbound->var) != SCIP_VARSTATUS_MULTAGGR);
1137 assert(result != NULL);
1138 assert(*result != SCIP_DIDNOTRUN);
1139
1140 /* get bound value provided by genvbound */
1141 boundval = getGenVBoundsBound(scip, genvbound, global);
1142
1143 if( SCIPisInfinity(scip, REALABS(boundval)) )
1144 return SCIP_OKAY;
1145
1146#ifdef SCIP_DEBUG
1147 {
1148 SCIP_Real lb;
1149 SCIP_Real ub;
1150 SCIP_Real new_lb;
1151 SCIP_Real new_ub;
1152
1153 lb = global ? SCIPvarGetLbGlobal(genvbound->var) : SCIPvarGetLbLocal(genvbound->var);
1154 ub = global ? SCIPvarGetUbGlobal(genvbound->var) : SCIPvarGetUbLocal(genvbound->var);
1155 new_lb = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? boundval : lb;
1156 new_ub = genvbound->boundtype == SCIP_BOUNDTYPE_UPPER ? boundval : ub;
1157
1158 SCIPdebugMsg(scip, " %s genvbound propagation for <%s>\n", global ?
1159 "global" : "local", SCIPvarGetName(genvbound->var));
1160 SCIPdebugMsg(scip, " genvbound: ");
1161 printGenVBound(scip, genvbound);
1162 SCIPdebugMsg(scip, " [%.15g,%.15g] -> [%.15g,%.15g]\n", lb, ub, new_lb, new_ub);
1163 }
1164#endif
1165
1166 /* tighten bound globally */
1167 if( global || genvbound->ncoefs <= 0 )
1168 {
1169 if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER )
1170 {
1171 SCIP_CALL( SCIPtightenVarLbGlobal(scip, genvbound->var, boundval, FALSE, &infeas, &tightened) );
1172 }
1173 else
1174 {
1175 SCIP_CALL( SCIPtightenVarUbGlobal(scip, genvbound->var, boundval, FALSE, &infeas, &tightened) );
1176 }
1177 }
1178 /* tighten bound locally and start conflict analysis in case of infeasibility; as inferinfo we pass the index of the
1179 * genvbound that was used for propagation
1180 */
1181 else
1182 {
1183 if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER )
1184 {
1185 SCIP_CALL( SCIPinferVarLbProp(scip, genvbound->var, boundval, prop, genvbound->index, FALSE, &infeas, &tightened) );
1186
1187 /* initialize conflict analysis if infeasible */
1188 if( infeas )
1189 {
1190 SCIPdebugMsg(scip, " -> lower bound tightening on variable <%s> led to infeasibility\n",
1191 SCIPvarGetName(genvbound->var));
1192
1194 }
1195 }
1196 else
1197 {
1198 SCIP_CALL( SCIPinferVarUbProp(scip, genvbound->var, boundval, prop, genvbound->index, FALSE, &infeas, &tightened) );
1199
1200 /* initialize conflict analysis if infeasible */
1201 if( infeas )
1202 {
1203 SCIPdebugMsg(scip, " -> upper bound tightening on variable <%s> led to infeasibility\n",
1204 SCIPvarGetName(genvbound->var));
1205
1207 }
1208 }
1209 }
1210
1211 /* handle result */
1212 if( infeas )
1213 {
1214 *result = SCIP_CUTOFF;
1215 SCIPdebugMsg(scip, " cutoff!\n");
1216 }
1217 else if( tightened )
1218 {
1220 if( nchgbds != NULL )
1221 ++(*nchgbds);
1222 SCIPdebugMsg(scip, " tightened!\n");
1223 }
1224
1225 return SCIP_OKAY;
1226}
1227
1228#ifdef SCIP_DEBUG
1229/** prints event data as debug message */
1230static
1231void printEventData(
1232 SCIP_EVENTDATA* eventdata,
1233 SCIP_BOUNDTYPE boundtype
1234 )
1235{
1236 int i;
1237
1238 SCIPdebugMessage("event data: %s bound of <%s> tightened ==> start propagating at ",
1239 boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", SCIPvarGetName(eventdata->var));
1240
1241 /* if there is eventdata it should contain at least one starting index */
1242 assert(eventdata->nstarts > 0);
1243
1244 for( i = 0; i < eventdata->nstarts; i++ )
1245 {
1246 SCIPdebugPrintf("(component %d, index %d) ", eventdata->startcomponents[i], eventdata->startindices[i]);
1247 }
1248 SCIPdebugPrintf("\n");
1249}
1250#endif
1251
1252/** frees event data */
1253static
1255 SCIP* scip, /**< SCIP data structure */
1256 SCIP_EVENTDATA** eventdata /**< event data to be freed */
1257 )
1258{
1259 assert(scip != NULL);
1260 assert(eventdata != NULL);
1261 assert(*eventdata != NULL);
1262
1263 SCIPfreeBlockMemoryArray(scip, &((*eventdata)->startcomponents), (*eventdata)->startindicessize);
1264 SCIPfreeBlockMemoryArray(scip, &((*eventdata)->startindices), (*eventdata)->startindicessize);
1265
1266 (*eventdata)->startindicessize = 0;
1267 (*eventdata)->nstarts = -1;
1268 (*eventdata)->var = NULL;
1269 (*eventdata)->prop = NULL;
1270
1271 SCIPfreeBlockMemory(scip, eventdata);
1272
1273 return SCIP_OKAY;
1274}
1275
1276/** frees all eventdata stored */
1277static
1279 SCIP* scip, /**< SCIP data structure */
1280 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
1281 )
1282{
1283 int i;
1284
1285 assert(scip != NULL);
1286 assert(propdata != NULL);
1287
1288 if( propdata->lbevents != NULL )
1289 {
1290 assert(propdata->ubevents != NULL);
1291 assert(propdata->lbeventsmap != NULL);
1292 assert(propdata->ubeventsmap != NULL);
1293
1294 SCIPhashmapFree(&(propdata->lbeventsmap));
1295 SCIPhashmapFree(&(propdata->ubeventsmap));
1296
1297 for( i = propdata->nlbevents - 1; i >= 0; i-- )
1298 {
1299 SCIP_CALL( freeEventData(scip, &(propdata->lbevents[i])) );
1300 }
1301
1302 for( i = propdata->nubevents - 1; i >= 0; i-- )
1303 {
1304 SCIP_CALL( freeEventData(scip, &(propdata->ubevents[i])) );
1305 }
1306
1307 SCIPfreeBlockMemoryArray(scip, &(propdata->ubevents), propdata->nubevents);
1308 SCIPfreeBlockMemoryArray(scip, &(propdata->lbevents), propdata->nlbevents);
1309 propdata->nlbevents = -1;
1310 propdata->nubevents = -1;
1311 }
1312
1313 assert(propdata->lbevents == NULL);
1314 assert(propdata->ubevents == NULL);
1315 assert(propdata->lbeventsmap == NULL);
1316 assert(propdata->ubeventsmap == NULL);
1317 assert(propdata->nlbevents == -1);
1318 assert(propdata->nubevents == -1);
1319
1320 return SCIP_OKAY;
1321}
1322
1323/** drops all events caught by genvbounds propagator and frees their data */
1324static
1326 SCIP* scip, /**< SCIP data structure */
1327 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
1328 )
1329{
1330 int i;
1331
1332 SCIPdebugMsg(scip, "drop and free events\n");
1333
1334 assert(scip != NULL);
1335 assert(propdata != NULL);
1336 assert(propdata->eventhdlr != NULL);
1337
1338 if( propdata->lbevents != NULL )
1339 {
1340 assert(propdata->ubevents != NULL);
1341 assert(propdata->nlbevents >= 0);
1342 assert(propdata->nubevents >= 0);
1343
1344 for( i = propdata->nlbevents - 1; i >= 0; i-- )
1345 {
1346 /* drop event */
1347 SCIP_CALL( SCIPdropVarEvent(scip, propdata->lbevents[i]->var, SCIP_EVENTTYPE_LBTIGHTENED, propdata->eventhdlr,
1348 propdata->lbevents[i], -1) );
1349 }
1350
1351 for( i = propdata->nubevents - 1; i >= 0; i-- )
1352 {
1353 /* drop event */
1354 SCIP_CALL( SCIPdropVarEvent(scip, propdata->ubevents[i]->var, SCIP_EVENTTYPE_UBTIGHTENED, propdata->eventhdlr,
1355 propdata->ubevents[i], -1) );
1356 }
1357
1358 /* free event data */
1359 SCIP_CALL( freeAllEventData(scip, propdata) );
1360 }
1361
1362 assert(propdata->lbevents == NULL);
1363 assert(propdata->ubevents == NULL);
1364 assert(propdata->nlbevents == -1);
1365 assert(propdata->nubevents == -1);
1366
1367 return SCIP_OKAY;
1368}
1369
1370/** returns the corresponding event data entry in the corresponding array, if there is one; if not: allocates a new
1371 * event data entry, stores it in the array and returns its adress
1372 */
1373static
1375 SCIP* scip, /**< SCIP data structure */
1376 SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */
1377 SCIP_VAR* var, /**< variable */
1378 SCIP_BOUNDTYPE boundtype, /**< type of bound */
1379 SCIP_EVENTDATA** eventdata /**< event data to return */
1380 )
1381{
1382 SCIP_HASHMAP* hashmap;
1383
1384 assert(scip != NULL);
1385 assert(propdata != NULL);
1386 assert(var != NULL);
1387
1388 hashmap = boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbeventsmap : propdata->ubeventsmap;
1389
1390 if( SCIPhashmapExists(hashmap, var) )
1391 *eventdata = (SCIP_EVENTDATA*) SCIPhashmapGetImage(hashmap, var);
1392 else
1393 {
1394 /* set up new eventdata entry */
1395 SCIP_CALL( SCIPallocBlockMemory(scip, eventdata) );
1396 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*eventdata)->startcomponents), propdata->ncomponents) );
1397 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*eventdata)->startindices), propdata->ncomponents) );
1398 (*eventdata)->startindicessize = propdata->ncomponents;
1399 (*eventdata)->nstarts = 0;
1400 (*eventdata)->var = var;
1401 (*eventdata)->prop = propdata->prop;
1402
1403 /* store event data in eventarray */
1404 if( boundtype == SCIP_BOUNDTYPE_LOWER )
1405 {
1406 propdata->lbevents[propdata->nlbevents] = *eventdata;
1407 propdata->nlbevents++;
1408 }
1409 else
1410 {
1411 propdata->ubevents[propdata->nubevents] = *eventdata;
1412 propdata->nubevents++;
1413 }
1414
1415 /* store hashmap entry */
1416 SCIP_CALL( SCIPhashmapInsert(hashmap, var, (*eventdata)) );
1417 }
1418
1419 return SCIP_OKAY;
1420}
1421
1422/** adds an event to the event array lbevents (if boundtype == SCIP_BOUNDTYPE_LOWER) or ubevents (if boundtype ==
1423 * SCIP_BOUNDTYPE_UPPER)
1424 */
1425static
1427 SCIP* scip, /**< SCIP data structure */
1428 SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */
1429 SCIP_VAR* var, /**< variable thats event to be added */
1430 int startindex, /**< starting index */
1431 int startcomponent, /**< starting components index */
1432 SCIP_BOUNDTYPE boundtype /**< type of bound */
1433 )
1434{
1435 SCIP_EVENTDATA* eventdata;
1436
1437 assert(scip != NULL);
1438 assert(propdata != NULL);
1439 assert(var != NULL);
1440 assert(startindex >= 0);
1441 assert(startcomponent >= 0);
1442
1443 /* get eventdata entry */
1444 SCIP_CALL( getEventData(scip, propdata, var, boundtype, &eventdata) );
1445 assert(eventdata != NULL);
1446
1447 if( eventdata->nstarts > 0 && eventdata->startcomponents[eventdata->nstarts - 1] == startcomponent )
1448 {
1449 /* if there is already a starting index for startcomponent stored at the last entry of eventdata->startindices,
1450 * it should be smaller; this relies on the implementation of setUpEvents(), calling addEventData() in
1451 * topological order
1452 */
1453 assert(eventdata->startindices[eventdata->nstarts - 1] < startindex);
1454 }
1455 else
1456 {
1457 /* append starting information */
1458 eventdata->startcomponents[eventdata->nstarts] = startcomponent;
1459 eventdata->startindices[eventdata->nstarts] = startindex;
1460
1461 /* increase counter */
1462 eventdata->nstarts++;
1463 }
1464
1465 return SCIP_OKAY;
1466}
1467
1468static
1470 SCIP* scip, /**< SCIP data structure */
1471 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
1472 )
1473{
1474 int nprobvars;
1475 int i;
1476
1477 assert(scip != NULL);
1478 assert(propdata != NULL);
1479 assert(propdata->eventhdlr != NULL);
1480 assert(propdata->lbevents == NULL);
1481 assert(propdata->ubevents == NULL);
1482 assert(propdata->issorted);
1483 assert(propdata->nlbevents == -1);
1484 assert(propdata->nubevents == -1);
1485
1486 SCIPdebugMsg(scip, "set up events\n");
1487
1488 /* allocate lbevents, ubevents, and their hashmaps */
1489 nprobvars = SCIPgetNVars(scip) + SCIPgetNFixedVars(scip);
1490 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->lbevents), nprobvars) );
1491 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->ubevents), nprobvars) );
1492 SCIP_CALL( SCIPhashmapCreate(&(propdata->lbeventsmap), SCIPblkmem(scip), nprobvars) );
1493 SCIP_CALL( SCIPhashmapCreate(&(propdata->ubeventsmap), SCIPblkmem(scip), nprobvars) );
1494 propdata->nlbevents = 0;
1495 propdata->nubevents = 0;
1496
1497 /* loop over all components of genvboundstore */
1498 for( i = 0; i < propdata->ncomponents; i++ )
1499 {
1500 int j;
1501
1502 /* loop over all genvbounds in this component */
1503 for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ ) /*lint !e679*/
1504 {
1505 GENVBOUND* genvbound;
1506 int k;
1507
1508 assert(j < propdata->ngenvbounds);
1509
1510 genvbound = propdata->genvboundstore[j];
1511 assert(genvbound != NULL);
1512
1513 /* loop over all coefficients in this genvbound */
1514 for( k = 0; k < genvbound->ncoefs; k++ )
1515 {
1516 if( SCIPisPositive(scip, genvbound->coefs[k]) )
1517 {
1518 SCIP_CALL( addEventData(scip, propdata, genvbound->vars[k], j, i, SCIP_BOUNDTYPE_LOWER) );
1519 }
1520 else
1521 {
1522 SCIP_CALL( addEventData(scip, propdata, genvbound->vars[k], j, i, SCIP_BOUNDTYPE_UPPER) );
1523 }
1524 }
1525 }
1526 }
1527
1528 /* resize lbevents and ubevents array */
1529 assert(propdata->nlbevents <= nprobvars);
1530 assert(propdata->nubevents <= nprobvars);
1531 if( propdata->nlbevents < nprobvars )
1532 {
1533 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->lbevents), nprobvars, propdata->nlbevents) );
1534 }
1535 if( propdata->nubevents < nprobvars )
1536 {
1537 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->ubevents), nprobvars, propdata->nubevents) );
1538 }
1539
1540 /* resize and register lower bound events */
1541 for( i = 0; i < propdata->nlbevents; i++ )
1542 {
1543 SCIP_EVENTDATA* eventdata = propdata->lbevents[i];
1544
1545 assert(eventdata != NULL);
1546 assert(eventdata->nstarts > 0);
1547 assert(eventdata->startcomponents != NULL);
1548 assert(eventdata->startindices != NULL);
1549
1550 /* resize arrays stored in eventdata */
1551 if( eventdata->startindicessize != eventdata->nstarts )
1552 {
1553 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startcomponents), eventdata->startindicessize, \
1554 eventdata->nstarts) );
1555 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startindices), eventdata->startindicessize, \
1556 eventdata->nstarts) );
1557 eventdata->startindicessize = eventdata->nstarts;
1558 }
1559
1560 /* register event */
1561 SCIP_CALL( SCIPcatchVarEvent(scip, eventdata->var, SCIP_EVENTTYPE_LBTIGHTENED, propdata->eventhdlr, eventdata, \
1562 NULL) );
1563 }
1564
1565 /* resize and register upper bound events */
1566 for( i = 0; i < propdata->nubevents; i++ )
1567 {
1568 SCIP_EVENTDATA* eventdata = propdata->ubevents[i];
1569
1570 assert(eventdata != NULL);
1571 assert(eventdata->nstarts > 0);
1572 assert(eventdata->startcomponents != NULL);
1573 assert(eventdata->startindices != NULL);
1574
1575 /* resize arrays stored in eventdata */
1576 if( eventdata->startindicessize != eventdata->nstarts )
1577 {
1578 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startcomponents), eventdata->startindicessize, \
1579 eventdata->nstarts) );
1580 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startindices), eventdata->startindicessize, \
1581 eventdata->nstarts) );
1582 eventdata->startindicessize = eventdata->nstarts;
1583 }
1584 /* register event */
1585 SCIP_CALL( SCIPcatchVarEvent(scip, eventdata->var, SCIP_EVENTTYPE_UBTIGHTENED, propdata->eventhdlr, eventdata,
1586 NULL) );
1587 }
1588
1589 return SCIP_OKAY;
1590}
1591
1592/** performs a topological sort on genvboundstore array
1593 *
1594 * The genvbounds graph is defined as follows: Given two genvbounds
1595 *
1596 * (genvbound1) c1 * x_i1 >= RHS1
1597 *
1598 * and
1599 *
1600 * (genvbound2) c2 * x_i2 >= RHS2,
1601 *
1602 * there is an arc from genvbound1 to genvbound2 iff c1 = +1 and x_i1 appears with positive coefficient in RHS2 or
1603 * c1 = -1 and x_i1 appears with negative coefficient in RHS2; in this case, a bound change of x_i1 deduced from
1604 * genvbound1 improves genvbound2's minactivity in RHS2.
1605 *
1606 * The method computes the strongly connected components and sorts them topologically. The order of the nodes in an
1607 * strongly connected component is arbitrary.
1608 */
1609static
1611 SCIP* scip, /**< SCIP data structure */
1612 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
1613 )
1614{
1615 GENVBOUND** genvboundssorted; /* array to store the sorted genvbounds */
1616 SCIP_DIGRAPH* graph;
1617 int* strongcomponents;
1618 int* strongcompstartidx;
1619 int sortedindex;
1620 int i;
1621
1622 assert(scip != NULL);
1623 assert(propdata != NULL);
1624 assert(propdata->componentsstart == NULL);
1625
1626 SCIPdebugMsg(scip, "(re-)sort genvbounds topologically\n");
1627
1628 /* create digraph */
1629 SCIP_CALL( SCIPcreateDigraph(scip, &graph, propdata->ngenvbounds) );
1630
1631 /* add outgoing arcs for each genvbound */
1632 for( i = 0; i < propdata->ngenvbounds; i++ )
1633 {
1634 GENVBOUND* genvbound;
1635 int j;
1636
1637 assert(i < propdata->ngenvbounds);
1638
1639 genvbound = propdata->genvboundstore[i];
1640
1641 for( j = 0; j < genvbound->ncoefs; j++ )
1642 {
1643 if( SCIPisPositive(scip, genvbound->coefs[j]) &&
1644 SCIPhashmapExists(propdata->lbgenvbounds, genvbound->vars[j]) )
1645 {
1646 int from = ((GENVBOUND*) SCIPhashmapGetImage(propdata->lbgenvbounds, genvbound->vars[j]))->index;
1647 SCIP_CALL( SCIPdigraphAddArc(graph, from, i, NULL) );
1648 }
1649 else if( SCIPisNegative(scip, genvbound->coefs[j]) &&
1650 SCIPhashmapExists(propdata->ubgenvbounds, genvbound->vars[j]) )
1651 {
1652 int from = ((GENVBOUND*) SCIPhashmapGetImage(propdata->ubgenvbounds, genvbound->vars[j]))->index;
1653 SCIP_CALL( SCIPdigraphAddArc(graph, from, i, NULL) );
1654 }
1655 }
1656 }
1657
1658 /* perform the topological sort */
1659 SCIP_CALL( SCIPdigraphComputeUndirectedComponents(graph, 1, NULL, &(propdata->ncomponents)) );
1661 assert(SCIPdigraphGetNComponents(graph) == propdata->ncomponents);
1662
1663 /* allocate memory for genvboundssorted and componentsstart array */
1664 SCIP_CALL( SCIPallocBufferArray(scip, &genvboundssorted, propdata->ngenvbounds) );
1665 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->componentsstart), propdata->ncomponents + 1) );
1666 propdata->componentsstartsize = propdata->ncomponents + 1;
1667
1668 /* allocate memory for strong component arrays */
1669 SCIP_CALL( SCIPallocBufferArray(scip, &strongcomponents, SCIPdigraphGetNNodes(graph)) ); /*lint !e666*/
1670 SCIP_CALL( SCIPallocBufferArray(scip, &strongcompstartidx, SCIPdigraphGetNNodes(graph) + 1) ); /*lint !e666*/
1671
1672 /* compute sorted genvbounds array, fill componentsstart array */
1673 sortedindex = 0;
1674 propdata->componentsstart[propdata->ncomponents] = propdata->ngenvbounds;
1675 for( i = 0; i < propdata->ncomponents; i++ )
1676 {
1677 int j;
1678 int *nodes;
1679 int nnodes;
1680 int nstrongcomponents;
1681
1682 SCIPdigraphGetComponent(graph, i, &nodes, &nnodes);
1683 propdata->componentsstart[i] = sortedindex;
1684
1685 /* compute the strong components of the i-th undirected component */
1686 if( nnodes > 2 )
1687 {
1688 SCIP_CALL( SCIPdigraphComputeDirectedComponents(graph, i, strongcomponents, strongcompstartidx,
1689 &nstrongcomponents) );
1690
1691 for( j = 0; j < nnodes; ++j )
1692 {
1693 int node;
1694
1695 /* take the nodes at the end of the strong components array first to respect the topological
1696 * order of the different strong components
1697 */
1698 node = strongcomponents[nnodes - j - 1];
1699
1700 assert(node < propdata->ngenvbounds);
1701 genvboundssorted[sortedindex] = propdata->genvboundstore[node];
1702 sortedindex++;
1703 }
1704 }
1705 else
1706 {
1707 for( j = 0; j < nnodes; j++ )
1708 {
1709 assert(nodes[j] < propdata->ngenvbounds);
1710 genvboundssorted[sortedindex] = propdata->genvboundstore[nodes[j]];
1711 sortedindex++;
1712 }
1713 }
1714 }
1715 assert(sortedindex == propdata->ngenvbounds);
1716
1717 /* copy sorted genvbounds into genvboundstore */
1718 for( i = 0; i < propdata->ngenvbounds; i++ )
1719 {
1720 assert(genvboundssorted[i] != NULL);
1721
1722 propdata->genvboundstore[i] = genvboundssorted[i];
1723 propdata->genvboundstore[i]->index = i;
1724 }
1725
1726 /* free strong component arrays */
1727 SCIPfreeBufferArray(scip, &strongcompstartidx);
1728 SCIPfreeBufferArray(scip, &strongcomponents);
1729
1730 SCIPfreeBufferArray(scip, &(genvboundssorted));
1731
1732 /* free digraph */
1733 SCIPdigraphFree(&graph);
1734
1735 /* remember genvboundstore as sorted */
1736 propdata->issorted = TRUE;
1737
1738#ifdef SCIP_DEBUG
1739 SCIPdebugMsg(scip, "genvbounds got: %d\n", propdata->ngenvbounds);
1740 for( i = 0; i < propdata->ncomponents; i++ )
1741 {
1742 int j;
1743
1744 SCIPdebugMsg(scip, "{\n");
1745
1746 for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ )
1747 {
1748 SCIPdebugMsg(scip, " [%d] ", j);
1749 printGenVBound(scip, propdata->genvboundstore[j]);
1750 }
1751
1752 SCIPdebugMsg(scip, "}\n");
1753 }
1754#endif
1755
1756 return SCIP_OKAY;
1757}
1758
1759/** apply propagation of generalized variable bounds */
1760static
1762 SCIP* scip, /**< SCIP data structure */
1763 SCIP_PROP* prop, /**< genvbounds propagator */
1764 SCIP_Bool global, /**< use global variable bounds for propagation? */
1765 SCIP_RESULT* result, /**< result pointer */
1766 int* nchgbds /**< counter to increase by the number of changed bounds */
1767 )
1768{
1769 SCIP_PROPDATA* propdata;
1770 int* startingcomponents;
1771 int* startingindices;
1772 int nindices;
1773 int i;
1774
1775 SCIPdebugMsg(scip, "applying %s genvbound propagation in depth %d\n", global ?
1776 "global" : "local", SCIPgetDepth(scip));
1777
1778 assert(scip != NULL);
1779 assert(prop != NULL);
1780 assert(result != NULL);
1781
1782 propdata = SCIPpropGetData(prop);
1783 assert(propdata != NULL);
1784 assert(propdata->genvboundstore != NULL);
1785
1786 if( *result == SCIP_DIDNOTRUN )
1787 *result = SCIP_DIDNOTFIND;
1788
1789 /* if the genvbounds are not sorted, i.e. if root node processing has not been finished, yet, we just propagate in
1790 * the order in which they have been added to genvboundstore
1791 */
1792 if( !propdata->issorted )
1793 {
1794 int j;
1795
1796 assert(!propdata->sort || SCIPinProbing(scip) || SCIPgetDepth(scip) == 0);
1797
1798 for( j = 0; j < propdata->ngenvbounds && *result != SCIP_CUTOFF; j++ )
1799 {
1800 if( ! SCIPvarIsActive(propdata->genvboundstore[j]->var) )
1801 {
1802 /**@todo resolve multiaggregation in exitpre */
1803 }
1804 else
1805 {
1806 SCIPdebugMsg(scip, "applying genvbound with index %d (unsorted mode)\n", j);
1807 SCIP_CALL( applyGenVBound(scip, prop, propdata->genvboundstore[j], global, result, nchgbds) );
1808 }
1809 }
1810
1811 return SCIP_OKAY;
1812 }
1813
1814 /* otherwise, we propagate only components affected by the latest bound changes */
1815 startingcomponents = global ? propdata->gstartcomponents : propdata->startcomponents;
1816 startingindices = global ? propdata->gstartindices : propdata->startindices;
1817 nindices = global ? propdata->ngindices : propdata->nindices;
1818
1819 for( i = 0; i < nindices && *result != SCIP_CUTOFF; i++ )
1820 {
1821 int j;
1822
1823 SCIPdebugMsg(scip, "starting in component %d at index %d\n", startingcomponents[i], startingindices[i]);
1824 for( j = startingindices[i]; j < propdata->componentsstart[startingcomponents[i] + 1] &&
1825 *result != SCIP_CUTOFF; j++ ) /*lint !e679*/
1826 {
1827 assert(j < propdata->ngenvbounds);
1828
1829 if( ! SCIPvarIsActive(propdata->genvboundstore[j]->var) )
1830 {
1831 /**@todo resolve multiaggregation in exitpre */
1832 }
1833 else
1834 {
1835 SCIPdebugMsg(scip, "applying genvbound with index %d, component %d\n", j, startingcomponents[i]);
1836 SCIP_CALL( applyGenVBound(scip, prop, propdata->genvboundstore[j], global, result, nchgbds) );
1837 }
1838 }
1839 }
1840
1841 /* we dont want to run again caused by this starting data */
1842 if( !global )
1843 {
1845 }
1846
1847 return SCIP_OKAY;
1848}
1849
1850/** initialize propagator data */
1851static
1853 SCIP* scip, /**< SCIP data structure */
1854 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
1855 )
1856{
1857 int nprobvars;
1858
1859 assert(scip != NULL);
1860 assert(propdata != NULL);
1861 assert(propdata->eventhdlr != NULL);
1862
1863 SCIPdebugMsg(scip, "init propdata\n");
1864
1865 nprobvars = SCIPgetNVars(scip);
1866
1867 /* init genvboundstore */
1868 propdata->genvboundstoresize = 2 * nprobvars;
1869 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->genvboundstore), propdata->genvboundstoresize) );
1870 BMSclearMemoryArray(propdata->genvboundstore, propdata->genvboundstoresize);
1871 propdata->ngenvbounds = 0;
1872
1873 /* init genvboundstore hashmaps */
1874 SCIP_CALL( SCIPhashmapCreate(&(propdata->lbgenvbounds), SCIPblkmem(scip), nprobvars) );
1875 SCIP_CALL( SCIPhashmapCreate(&(propdata->ubgenvbounds), SCIPblkmem(scip), nprobvars) );
1876
1877 return SCIP_OKAY;
1878}
1879
1880/** adds a new genvbound to genvboundstore array and sets a hashmap entry */
1881static
1883 SCIP* scip, /**< SCIP data structure */
1884 SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */
1885 GENVBOUND* genvbound /**< genvbound to be added */
1886 )
1887{
1888 SCIP_HASHMAP* hashmap;
1889
1890 assert(scip != NULL);
1891 assert(propdata != NULL);
1892 assert(genvbound != NULL);
1893 assert(getGenVBound(scip, propdata, genvbound->var, genvbound->boundtype) == NULL);
1894
1895 hashmap = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds;
1896
1897 /* e.g., during presolving after a restart, new variables might have been created; in this case, we need to extend
1898 * the genvboundstore; the new size may even exceed 2*SCIPgetNVars() if we have genvbounds with nonactive left-hand
1899 * side variables
1900 */
1901 assert(propdata->ngenvbounds <= propdata->genvboundstoresize);
1902 if( propdata->ngenvbounds == propdata->genvboundstoresize )
1903 {
1904 int oldsize = propdata->genvboundstoresize;
1905 propdata->genvboundstoresize = 2*propdata->genvboundstoresize + 1;
1906 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->genvboundstore), oldsize, propdata->genvboundstoresize) );
1907 }
1908
1909 /* new index is propdata->ngenvbounds */
1910 SCIP_CALL( SCIPhashmapInsert(hashmap, genvbound->var, genvbound) );
1911 propdata->genvboundstore[propdata->ngenvbounds] = genvbound;
1912 genvbound->index = propdata->ngenvbounds;
1913 propdata->ngenvbounds++;
1914
1915 assert(propdata->ngenvbounds <= propdata->genvboundstoresize);
1916
1917 return SCIP_OKAY;
1918}
1919
1920/** runs propagation routine */
1921static
1923 SCIP* scip, /**< SCIP data structure */
1924 SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */
1925 SCIP_RESULT* result, /**< result pointer */
1926 SCIP_Bool local, /**< should local propagation be applied? */
1927 int* nchgbds /**< counter to increase by the number of changed bounds */
1928 )
1929{
1930 assert(scip != NULL);
1931 assert(propdata != NULL);
1932 assert(propdata->prop != NULL);
1933 assert(result != NULL);
1934
1935 /* we only sort after the root node is finished; this avoids having to sort again after adding more genvbounds; if
1936 * the genvbounds are not sorted, we will simply propagate all of them in the order given
1937 */
1938 if( propdata->sort && !SCIPinProbing(scip) && SCIPgetDepth(scip) > 0 )
1939 {
1940 if( !propdata->issorted )
1941 {
1942 *result = SCIP_DIDNOTFIND;
1943
1944 SCIPdebugMsg(scip, "genvbounds are not sorted\n");
1945
1946 /* drop and free old events */
1947 SCIP_CALL( dropAndFreeEvents(scip, propdata) );
1948
1949 /* free old starting data */
1950 SCIP_CALL( freeStartingData(scip, propdata) );
1951
1952 /* free sorted components data */
1953 SCIP_CALL( freeComponentsData(scip, propdata) );
1954
1955 /* sort genvbounds */
1956 SCIP_CALL( sortGenVBounds(scip, propdata) );
1957
1958 /* create starting data */
1959 SCIP_CALL( createStartingData(scip, propdata) );
1960
1961 /* fill global starting data */
1963 }
1964
1965 /* set up new events to catch (if not done so far) */
1966 if( propdata->lbevents == NULL )
1967 {
1968 SCIP_CALL( setUpEvents(scip, propdata) );
1969 }
1970 }
1971
1972 /* apply global propagation if primal bound has improved */
1973 if( propdata->global && SCIPgetDepth(scip) > 0 && SCIPisFeasLT(scip, SCIPgetCutoffbound(scip), propdata->lastcutoff) )
1974 {
1975 if( propdata->ngindices > 0 )
1976 {
1977 SCIP_CALL( applyGenVBounds(scip, propdata->prop, TRUE, result, nchgbds) );
1978 assert(*result != SCIP_DIDNOTRUN);
1979 }
1980
1981 /* within the tree, the objective function should not change anymore, hence the cutoff bound should be a stable
1982 * point of reference
1983 */
1984 propdata->lastcutoff = SCIPgetCutoffbound(scip);
1985 }
1986
1987 /* apply local propagation if allowed */
1988 if( local && *result != SCIP_CUTOFF )
1989 {
1990 /* check if local propagation in root node is allowed */
1991 if( SCIPgetDepth(scip) > 0 || propdata->propinrootnode )
1992 {
1993 /* if genvbounds are already sorted, check if bound change events were caught; otherwise apply all genvbounds */
1994 if( !propdata->issorted || ( SCIPgetCurrentNode(scip) == propdata->lastnodecaught && propdata->nindices > 0 ) )
1995 {
1996 SCIP_CALL( applyGenVBounds(scip, propdata->prop, FALSE, result, nchgbds) );
1997 assert(*result != SCIP_DIDNOTRUN);
1998 }
1999 }
2000 }
2001
2002 return SCIP_OKAY;
2003}
2004
2005/* adds all genvbounds in the genvboundstore as constraints to the problem; afterwards clears the genvboundstore */
2006static
2008 SCIP* scip, /**< SCIP data structure */
2009 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */
2010 )
2011{
2012 int i;
2013
2014 assert(scip != NULL);
2015 assert(propdata != NULL);
2016 assert(propdata->propasconss);
2017
2018 /* ensure that the cutoffboundvar is available */
2019 if( propdata->cutoffboundvar == NULL )
2020 {
2021 SCIP_Real ub;
2022 char name[16];
2023
2024 /* set the upper bound to the best primal value in the original problem */
2026
2027 SCIPdebugMsg(scip, "initialize cutoffboundvar with UB = %e\n", ub);
2028
2029 (void) SCIPsnprintf(name, 16, "cutoffboundvar");
2030 SCIP_CALL( SCIPcreateVarBasic(scip, &propdata->cutoffboundvar, name, -SCIPinfinity(scip), ub, 0.0, SCIP_VARTYPE_CONTINUOUS) );
2031 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, propdata->cutoffboundvar) );
2032
2033 SCIP_CALL( SCIPaddVar(scip, propdata->cutoffboundvar) );
2034
2035 /* lock the variable because it should not be subject to dual presolving reductions; because we create the
2036 * linear constraints as non-check constraints, the cutoffboundvar will not be locked by the linear constraint
2037 * handler
2038 */
2039 SCIP_CALL( SCIPaddVarLocksType(scip, propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL, 1, 1) );
2040 }
2041
2042 assert(propdata->cutoffboundvar != NULL);
2043
2044 /* now iterate over all genvbounds in the store and construct a linear constraint for each of them */
2045 for( i = 0; i < propdata->ngenvbounds; ++i )
2046 {
2047 GENVBOUND* genvbound;
2048 SCIP_CONS* cons;
2049 SCIP_VAR** vars;
2050 SCIP_Real* vals;
2051 char name[SCIP_MAXSTRLEN];
2052 int nvars;
2053 int j;
2054
2055 genvbound = propdata->genvboundstore[i];
2056 assert(genvbound != NULL);
2057
2058 nvars = genvbound->ncoefs + 2;
2059 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
2060 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
2061
2062 SCIPdebugMsgPrint(scip, "add cons: ");
2063
2064 /* copy the coefs/vars array */
2065 for( j = 0; j < genvbound->ncoefs; j++ )
2066 {
2067 vars[j] = genvbound->vars[j];
2068 vals[j] = genvbound->coefs[j];
2069 SCIPdebugMsgPrint(scip, "%e%s + ", vals[j], SCIPvarGetName(vars[j]));
2070 }
2071
2072 /* add the variable and the coefficient of the genvbound */
2073 vars[genvbound->ncoefs] = genvbound->var;
2074 vals[genvbound->ncoefs] = (genvbound->boundtype == SCIP_BOUNDTYPE_LOWER) ? -1.0 : 1.0;
2075
2076 SCIPdebugMsgPrint(scip, "%e%s + ", vals[genvbound->ncoefs], SCIPvarGetName(vars[genvbound->ncoefs]));
2077
2078 /* add cutoffcoef * cutoffboundvar */
2079 vars[genvbound->ncoefs + 1] = propdata->cutoffboundvar;
2080 vals[genvbound->ncoefs + 1] = genvbound->cutoffcoef;
2081
2082 SCIPdebugMsgPrint(scip, "%e%s <= %e\n", vals[genvbound->ncoefs + 1], SCIPvarGetName(vars[genvbound->ncoefs + 1]), -1.0*genvbound->constant);
2083
2084 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "genvbound_cons%d", genvbound->index);
2085
2086 /* create linear constraint with only propagate flag as TRUE */
2087 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, nvars, vars, vals, -SCIPinfinity(scip), -genvbound->constant,
2089
2090 SCIP_CALL( SCIPaddCons(scip, cons) );
2091 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2092
2093 /* free memory */
2094 SCIPfreeBufferArray(scip, &vars);
2095 SCIPfreeBufferArray(scip, &vals);
2096 }
2097
2098 /* now delete all genvbounds in the genvboundstore */
2099 if( propdata->ngenvbounds > 0 )
2100 {
2101 assert(propdata->genvboundstore != NULL);
2102
2103 for( i = propdata->ngenvbounds - 1; i >= 0; i-- )
2104 {
2105 SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) );
2106 }
2107
2108 /* free genvboundstore hashmaps */
2109 SCIPhashmapFree(&(propdata->lbgenvbounds));
2110 SCIPhashmapFree(&(propdata->ubgenvbounds));
2111
2112 /* drop and free all events */
2113 SCIP_CALL( dropAndFreeEvents(scip, propdata) );
2114
2115 /* free componentsstart array */
2116 SCIP_CALL( freeComponentsData(scip, propdata) );
2117
2118 /* free starting indices data */
2119 SCIP_CALL( freeStartingData(scip, propdata) );
2120
2121 SCIPfreeBlockMemoryArray(scip, &(propdata->genvboundstore), propdata->genvboundstoresize);
2122 propdata->genvboundstore = NULL;
2123 propdata->genvboundstoresize = 0;
2124 propdata->ngenvbounds = 0;
2125 }
2126
2127 return SCIP_OKAY;
2128}
2129
2130
2131
2132/*
2133 * Public methods
2134 */
2135
2136/** adds a generalized variable bound to the genvbounds propagator; if there is already a genvbound for the bound
2137 * "boundtype" of variable "var", it will be replaced
2138 */
2140 SCIP* scip, /**< SCIP data structure */
2141 SCIP_PROP* genvboundprop, /**< genvbound propagator */
2142 SCIP_VAR** vars, /**< array of RHSs variables */
2143 SCIP_VAR* var, /**< LHSs variable */
2144 SCIP_Real* coefs, /**< array of coefficients for the RHSs variables */
2145 int ncoefs, /**< size of coefs array */
2146 SCIP_Real coefcutoffbound, /**< nonpositive value of the cutoff bounds multiplier */
2147 SCIP_Real constant, /**< constant term */
2148 SCIP_BOUNDTYPE boundtype /**< type of bound provided by the genvbound */
2149 )
2150{
2151 /**@todo in debug mode: check if genvbound is nontrivial */
2152
2153 SCIP_PROPDATA* propdata;
2154 GENVBOUND* genvbound;
2155 SCIP_Bool newgenvbound;
2156 int i;
2157
2158 assert(scip != NULL);
2159 assert(genvboundprop != NULL);
2160 assert(strcmp(SCIPpropGetName(genvboundprop), PROP_NAME) == 0);
2161 assert(vars != NULL);
2162 assert(var != NULL);
2163 assert(coefs != NULL);
2164 assert(ncoefs >= 0);
2165 assert(coefcutoffbound <= 0.0);
2166 assert(!SCIPisInfinity(scip, -constant));
2167
2168 if( ncoefs < 0 || coefcutoffbound > 0.0 || SCIPisInfinity(scip, -constant) )
2169 {
2170 SCIPerrorMessage("cannot create generalized variable bound from invalid data\n");
2171 return SCIP_INVALIDDATA;
2172 }
2173
2174 propdata = SCIPpropGetData(genvboundprop);
2175 assert(propdata != NULL);
2176
2177 /* initialize propdata if not done yet */
2178 if( propdata->genvboundstore == NULL )
2179 {
2180 SCIP_CALL( initPropdata(scip, propdata) );
2181 }
2182
2183 genvbound = getGenVBound(scip, propdata, var, boundtype);
2184 newgenvbound = (genvbound == NULL);
2185
2186 /* release previous variables */
2187 if( !newgenvbound )
2188 {
2189 for( i = 0; i < genvbound->ncoefs; ++i )
2190 {
2191 assert(genvbound->vars[i] != NULL);
2192 SCIP_CALL( SCIPreleaseVar(scip, &(genvbound->vars[i])) );
2193 }
2194 }
2195
2196 /* check if there already is a genvbound corresponding to this bound, freeing its data and overwriting it */
2197 if( !newgenvbound && genvbound->ncoefs < ncoefs )
2198 {
2199 /* do not realloc since we do not want to keep and possibly copy the old entries */
2200 SCIPfreeBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize);
2201 SCIPfreeBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize);
2202
2203 /* allocate and copy arrays in genvbound */
2204 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->coefs), coefs, ncoefs) );
2205 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->vars), vars, ncoefs) );
2206 genvbound->coefssize = ncoefs;
2207 }
2208 else if( !newgenvbound && genvbound->ncoefs == ncoefs )
2209 {
2210 /* just update entries */
2211 for( i = 0; i < ncoefs; i++ )
2212 {
2213 genvbound->coefs[i] = coefs[i];
2214 genvbound->vars[i] = vars[i];
2215 }
2216 }
2217 else if( !newgenvbound && genvbound->ncoefs > ncoefs )
2218 {
2219 /* reallocate memory for arrays in genvbound to free unused memory */
2220 if( genvbound->coefssize < ncoefs )
2221 {
2222 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize, ncoefs) );
2223 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize, ncoefs) );
2224 genvbound->coefssize = ncoefs;
2225 }
2226
2227 /* update entries */
2228 for( i = 0; i < ncoefs; i++ )
2229 {
2230 genvbound->coefs[i] = coefs[i];
2231 genvbound->vars[i] = vars[i];
2232 }
2233 }
2234 else if( newgenvbound )
2235 {
2236 /* allocate memory for genvbound data */
2237 SCIP_CALL( SCIPallocBlockMemory(scip, &genvbound) );
2238
2239 /* allocate and copy arrays in genvbound */
2240 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->coefs), coefs, ncoefs) );
2241 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->vars), vars, ncoefs) );
2242 genvbound->coefssize = ncoefs;
2243 }
2244
2245 /* set up data for genvbound */
2246 genvbound->boundtype = boundtype;
2247 genvbound->var = var;
2248 genvbound->ncoefs = ncoefs;
2249 genvbound->constant = constant;
2250 genvbound->relaxonly = SCIPvarIsRelaxationOnly(genvbound->var);
2251
2252 /* capture variables and check for relax-only vars */
2253 for( i = 0; i < genvbound->ncoefs; ++i )
2254 {
2255 assert(genvbound->vars[i] != NULL);
2256 SCIP_CALL( SCIPcaptureVar(scip, genvbound->vars[i]) );
2257 if( SCIPvarIsRelaxationOnly(genvbound->vars[i]) )
2258 genvbound->relaxonly = TRUE;
2259 }
2260 if( newgenvbound )
2261 {
2262 assert(genvbound->var != NULL);
2263 SCIP_CALL( SCIPcaptureVar(scip, genvbound->var) );
2264 }
2265
2266 /* the cutoff bound is valid w.r.t. the current objective function in the transformed problem; during presolving,
2267 * however, the objective function can change (e.g., when a variable is fixed, its contribution in the objective
2268 * is subtracted from the cutoff bound and added to the objective offset); we solve this by transforming the
2269 * contribution of the cutoff bound in the generalized variable bound to the original problem as follows:
2270 *
2271 * +/- var >= ... + z * SCIPgetCutoffbound() + constant
2272 *
2273 * becomes
2274 *
2275 * +/- var >= ... + (z / SCIPgetTransObjscale()) * origcutoffbound + (constant - z * SCIPgetTransObjoffset())
2276 *
2277 * with SCIPgetCutoffbound() = origcutoffbound / SCIPgetTransObjscale() - SCIPgetTransObjoffset(); in the
2278 * propagation later, we will use (SCIPgetCutoffbound() + SCIPgetTransObjoffset()) * SCIPgetTransObjscale(), see
2279 * function getCutoffboundGenVBound()
2280 */
2281 if( SCIPisNegative(scip, coefcutoffbound) )
2282 {
2284 genvbound->cutoffcoef = coefcutoffbound / SCIPgetTransObjscale(scip);
2285 genvbound->constant -= (coefcutoffbound * SCIPgetTransObjoffset(scip));
2286 }
2287 else
2288 genvbound->cutoffcoef = 0.0;
2289
2290 /* if genvbound is not overwritten, create a new entry in genvboundstore */
2291 if( newgenvbound )
2292 {
2293 SCIP_CALL( addNewGenVBound(scip, propdata, genvbound) );
2294 }
2295
2296 /* mark genvbounds array to be resorted */
2297 propdata->issorted = FALSE;
2298
2299 /* debug message */
2300 SCIPdebugMsg(scip, "added genvbound ");
2301 SCIPdebug( printGenVBound(scip, genvbound) );
2302#ifdef WITH_DEBUG_SOLUTION
2303 SCIP_CALL( checkDebugSolutionGenVBound(scip, genvbound) );
2304#endif
2305
2306 return SCIP_OKAY;
2307}
2308
2309
2310/*
2311 * Callback methods of propagator
2312 */
2313
2314/** copy method for propagator plugins (called when SCIP copies plugins)
2315 *
2316 * @note The UG framework assumes that all default plug-ins of SCIP implement a copy callback.
2317 */
2318static
2319SCIP_DECL_PROPCOPY(propCopyGenvbounds)
2320{ /*lint --e{715}*/
2321 assert(scip != NULL);
2322 assert(prop != NULL);
2323 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2324
2325 /* call inclusion method of constraint handler */
2327
2328 return SCIP_OKAY;
2329}
2330
2331/** initialization method of propagator (called after problem was transformed) */
2332static
2333SCIP_DECL_PROPINIT(propInitGenvbounds)
2334{ /*lint --e{715}*/
2335 SCIP_PROPDATA* propdata;
2336
2337 assert(scip != NULL);
2338 assert(prop != NULL);
2339 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2340
2341 /* get propagator data */
2342 propdata = SCIPpropGetData(prop);
2343 assert(propdata != NULL);
2344
2345 propdata->genvboundstore = NULL;
2346 propdata->genvboundstoresize = 0;
2347 propdata->lbevents = NULL;
2348 propdata->ubevents = NULL;
2349 propdata->lbgenvbounds = NULL;
2350 propdata->ubgenvbounds = NULL;
2351 propdata->lbeventsmap = NULL;
2352 propdata->ubeventsmap = NULL;
2353 propdata->startmap = NULL;
2354 propdata->componentsstart = NULL;
2355 propdata->startindices = NULL;
2356 propdata->startcomponents = NULL;
2357 propdata->gstartindices = NULL;
2358 propdata->gstartcomponents = NULL;
2359 propdata->lastcutoff = SCIPinfinity(scip);
2360 propdata->lastnodecaught = NULL;
2361 propdata->cutoffboundvar = NULL;
2362 propdata->ngenvbounds = -1;
2363 propdata->ncomponents = -1;
2364 propdata->nindices = -1;
2365 propdata->ngindices = -1;
2366 propdata->nlbevents = -1;
2367 propdata->nubevents = -1;
2368 propdata->issorted = FALSE;
2369
2370 propdata->prop = prop;
2371
2372 return SCIP_OKAY;
2373}
2374
2375
2376/** presolving method of propagator */
2377static
2378SCIP_DECL_PROPPRESOL(propPresolGenvbounds)
2379{ /*lint --e{715}*/
2380 SCIP_PROPDATA* propdata;
2381
2382 assert(scip != NULL);
2383 assert(prop != NULL);
2384 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2385
2386 *result = SCIP_DIDNOTRUN;
2387
2389 return SCIP_OKAY;
2390
2391 /* get propagator data */
2392 propdata = SCIPpropGetData(prop);
2393 assert(propdata != NULL);
2394
2395 SCIPdebugMsg(scip, "proppresol in problem <%s>\n", SCIPgetProbName(scip));
2396
2397 /* do not run if no genvbounds were added yet */
2398 if( propdata->ngenvbounds < 1 )
2399 {
2400 SCIPdebugMsg(scip, "no bounds were added yet\n");
2401 return SCIP_OKAY;
2402 }
2403
2404 /* propagate */
2405 SCIP_CALL( execGenVBounds(scip, propdata, result, TRUE, nchgbds) );
2406
2407 return SCIP_OKAY;
2408}
2409
2410
2411/** presolving initialization method of propagator (called when presolving is about to begin) */
2412static
2413SCIP_DECL_PROPINITPRE(propInitpreGenvbounds)
2414{ /*lint --e{715}*/
2415 SCIP_PROPDATA* propdata;
2416
2417 assert(scip != NULL);
2418 assert(prop != NULL);
2419 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2420
2421 /* get propagator data */
2422 propdata = SCIPpropGetData(prop);
2423 assert(propdata != NULL);
2424
2425 /* lock the variable because it should not be deleted after a restart */
2426 if( propdata->cutoffboundvar != NULL )
2427 {
2428 SCIPdebugMsg(scip, "propinitpre in problem <%s>: locking cutoffboundvar (current downlocks=%d, uplocks=%d)\n",
2430 SCIPvarGetNLocksUpType(propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL));
2431
2432 SCIP_CALL( SCIPaddVarLocksType(scip, propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL, 1, 1) );
2433 }
2434
2435 return SCIP_OKAY;
2436}
2437
2438
2439/** presolving deinitialization method of propagator (called after presolving has been finished) */
2440static
2441SCIP_DECL_PROPEXITPRE(propExitpreGenvbounds)
2442{ /*lint --e{715}*/
2443 SCIP_VAR** vars;
2444 SCIP_PROPDATA* propdata;
2445 int i;
2446
2447 assert(scip != NULL);
2448 assert(prop != NULL);
2449 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2450
2451 SCIPdebugMsg(scip, "propexitpre in problem <%s>: removing fixed, aggregated, negated, and multi-aggregated variables from right-hand side\n",
2453
2454 /* get propagator data */
2455 propdata = SCIPpropGetData(prop);
2456 assert(propdata != NULL);
2457
2458 /* there should be no events on the right-hand side variables */
2459 assert(propdata->lbevents == NULL);
2460 assert(propdata->ubevents == NULL);
2461
2462 /* allocate memory to store new variables */
2464
2465 for( i = 0; i < propdata->ngenvbounds; )
2466 {
2467 GENVBOUND* genvbound;
2468 int requiredsize;
2469 int nvars;
2470 int j;
2471
2472 genvbound = propdata->genvboundstore[i];
2473 assert(genvbound != NULL);
2474
2475 /* store variables of the genvbound to release them properly */
2476 assert(genvbound->ncoefs <= SCIPgetNTotalVars(scip));
2477 BMScopyMemoryArray(vars, genvbound->vars, genvbound->ncoefs);
2478 nvars = genvbound->ncoefs;
2479
2480 /* replace non-active by active variables and update constant; note that this may result in coefficients where
2481 * SCIPisZero() is true; this should not create any problems
2482 */
2483 SCIP_CALL( SCIPgetProbvarLinearSum(scip, genvbound->vars, genvbound->coefs, &genvbound->ncoefs, genvbound->ncoefs, &genvbound->constant, &requiredsize, TRUE) );
2484
2485 /* if space was not enough we need to resize the buffers */
2486 if( requiredsize > genvbound->ncoefs )
2487 {
2488 /* reallocate memory for arrays in genvbound to free unused memory */
2489 if( genvbound->coefssize < requiredsize )
2490 {
2491 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize, requiredsize) );
2492 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize, requiredsize) );
2493 genvbound->coefssize = requiredsize;
2494 }
2495
2496 SCIP_CALL( SCIPgetProbvarLinearSum(scip, genvbound->vars, genvbound->coefs, &genvbound->ncoefs, requiredsize, &genvbound->constant, &requiredsize, TRUE) );
2497 assert(requiredsize <= genvbound->ncoefs);
2498 }
2499
2500 /* capture new and release old variables */
2501 for( j = 0; j < genvbound->ncoefs; ++j )
2502 {
2503 assert(genvbound->vars[j] != NULL);
2504 SCIP_CALL( SCIPcaptureVar(scip, genvbound->vars[j]) );
2505 }
2506 for( j = 0; j < nvars; ++j )
2507 {
2508 assert(vars[j] != NULL);
2509 SCIP_CALL( SCIPreleaseVar(scip, &vars[j]) );
2510 }
2511
2512 /* if the resulting genvbound is trivial, remove it */
2513 /* we remove all genvbounds with an aggregated or multi-aggregated genvbound->var; tightening aggregated variables
2514 * might lead to some asserts in tree.c if the active variable has been already tightened (see !398);
2515 *
2516 * @todo replace aggregated variable by their active part
2517 */
2518 if( (genvbound->ncoefs == 0 && SCIPisZero(scip, genvbound->cutoffcoef))
2521 {
2522 SCIP_HASHMAP* hashmap;
2523
2524 hashmap = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds;
2525
2526 /* remove genvbound from hashmap */
2527 assert(SCIPhashmapExists(hashmap, genvbound->var));
2528 SCIP_CALL( SCIPhashmapRemove(hashmap, genvbound->var) );
2529
2530 /* free genvbound and fill gap */
2531 SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) );
2532 --(propdata->ngenvbounds);
2533
2534 /* move the last genvbound to the i-th position */
2535 if( i < propdata->ngenvbounds )
2536 {
2537 propdata->genvboundstore[i] = propdata->genvboundstore[propdata->ngenvbounds];
2538 propdata->genvboundstore[i]->index = i;
2539
2540 /* mark genvbounds array to be resorted */
2541 propdata->issorted = FALSE;
2542 }
2543 }
2544 else
2545 ++i;
2546 }
2547
2548 SCIPfreeBufferArray(scip, &vars);
2549
2550 return SCIP_OKAY;
2551}
2552
2553/** deinitialization method of propagator (called before transformed problem is freed) */
2554static
2555SCIP_DECL_PROPEXIT(propExitGenvbounds)
2556{
2557 SCIP_PROPDATA* propdata;
2558
2559 assert(scip != NULL);
2560 assert(prop != NULL);
2561 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2562
2563 /* get propagator data */
2564 propdata = SCIPpropGetData(prop);
2565 assert(propdata != NULL);
2566
2567 /* free remaining genvbounds */
2568 SCIP_CALL( freeGenVBounds(scip, propdata) );
2569
2570 return SCIP_OKAY;
2571}
2572
2573/** execution method of propagator */
2574static
2575SCIP_DECL_PROPEXEC(propExecGenvbounds)
2576{ /*lint --e{715}*/
2577 SCIP_PROPDATA* propdata;
2578
2579 assert(scip != NULL);
2580 assert(prop != NULL);
2581 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2582
2583 *result = SCIP_DIDNOTRUN;
2584
2585 /* do not run if propagation w.r.t. current objective is not allowed */
2587 return SCIP_OKAY;
2588
2589 /* get propagator data */
2590 propdata = SCIPpropGetData(prop);
2591 assert(propdata != NULL);
2592
2593 /* update upper bound of the cutoffboundvar */
2594 if( propdata->cutoffboundvar != NULL )
2595 {
2596 SCIP_Real newub;
2597 SCIP_Real oldub;
2598 SCIP_Bool infeasible;
2599 SCIP_Bool tightened;
2600
2601 assert(propdata->propasconss);
2602
2603 /* compute the primal bound in the original problem */
2605 oldub = SCIPvarGetUbLocal(propdata->cutoffboundvar);
2606
2607 if( SCIPisInfinity(scip, newub) == FALSE && SCIPisFeasLT(scip, newub, oldub) )
2608 {
2609 SCIP_CALL( SCIPtightenVarUbGlobal(scip, propdata->cutoffboundvar, newub, FALSE, &infeasible, &tightened) );
2610
2611 if( tightened )
2612 {
2613 SCIPdebugMsg(scip, "tightened UB of cutoffboundvar to %e (old: %e, infeas: %u, tightened: %u)\n",
2614 newub, oldub, infeasible, tightened);
2615 }
2616
2617 assert(infeasible == FALSE);
2618 }
2619 }
2620
2621 SCIPdebugMsg(scip, "propexec in problem <%s> at depth %d%s\n", SCIPgetProbName(scip), SCIPgetDepth(scip),
2622 SCIPinProbing(scip) ? " in probing" : "");
2623
2624 /* do not run if no genvbounds were added yet */
2625 if( propdata->ngenvbounds < 1 )
2626 {
2627 /**@todo is it really no performance issue to be called each time when there are no genvbounds, e.g., for MIPs? */
2628 SCIPdebugMsg(scip, "no bounds were added yet\n");
2629 return SCIP_OKAY;
2630 }
2631
2632 /* add the genvbounds in the genvboundstore as constraints to the problem; afterwards clear the genvboundstore */
2633 if( propdata->propasconss )
2634 {
2635 SCIP_CALL( createConstraints(scip, propdata) );
2636 return SCIP_OKAY;
2637 }
2638
2639 /* propagate locally and globally */
2640 SCIP_CALL( execGenVBounds(scip, propdata, result, !SCIPinProbing(scip), NULL) );
2641
2642 /* when called in presolving stage the result is set to SCIP_SUCCESS instead of SCIP_REDUCEDDOM, this is corrected
2643 * here
2644 */
2645 if( *result == SCIP_SUCCESS )
2646 *result = SCIP_REDUCEDDOM;
2647
2648 SCIPdebugMsg(scip, "end of exec\n");
2649
2650 return SCIP_OKAY;
2651}
2652
2653/** propagation conflict resolving method of propagator */
2654static
2655SCIP_DECL_PROPRESPROP(propRespropGenvbounds)
2656{ /*lint --e{715}*/
2657 SCIP_PROPDATA* propdata;
2658 GENVBOUND* genvbound;
2659 SCIP_Real boundval;
2660 SCIP_Bool success;
2661
2662 SCIPdebugMsg(scip, "explain %s bound change of variable <%s>\n",
2663 boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", SCIPvarGetName(infervar));
2664
2665 /* get propagator data */
2666 propdata = SCIPpropGetData(prop);
2667 assert(propdata != NULL);
2668 assert(propdata->genvboundstore != NULL);
2669
2670 /* as inferinfo we passed the index of the genvbound that was used for propagation; the genvbound might have been
2671 * replaced, but also the new genvbound at this position has the same variable on the left-hand side
2672 */
2673 assert(inferinfo >= 0);
2674 assert(inferinfo < propdata->ngenvbounds);
2675
2676 *result = SCIP_DIDNOTFIND;
2677
2678 /* check also in optimized mode that inferinfo is correct */
2679 if( inferinfo >= propdata->ngenvbounds)
2680 {
2681 SCIPerrorMessage("generalized variable bounds propagator received inferinfo out of range; propagation not resolved, safe to continue\n");
2682 return SCIP_OKAY;
2683 }
2684
2685 /* get genvbound responsible for the bound change */
2686 genvbound = propdata->genvboundstore[inferinfo];
2687 assert(genvbound != NULL);
2688 assert(genvbound->var == infervar);
2689
2690 /* check also in optimized mode that inferinfo is correct */
2691 if( genvbound->var != infervar )
2692 {
2693 SCIPerrorMessage("generalized variable bounds propagator received incorrect inferinfo; propagation not resolved, but it's safe to continue\n");
2694 return SCIP_OKAY;
2695 }
2696
2697 /* get value of bound change on left-hand side */
2698 boundval = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER
2699 ? SCIPgetVarLbAtIndex(scip, genvbound->var, bdchgidx, TRUE)
2700 : -SCIPgetVarUbAtIndex(scip, genvbound->var, bdchgidx, TRUE);
2701
2702 /* if left-hand side variable is integral, it suffices to explain a bound change greater than boundval - 1 */
2703 if( SCIPvarIsIntegral(genvbound->var) )
2704 {
2705 SCIP_Real roundedboundval;
2706
2707 assert(SCIPisIntegral(scip, boundval));
2708
2709 roundedboundval = SCIPfeasCeil(scip, boundval - 1.0) + 2 * SCIPfeastol(scip);
2710 boundval = MIN(boundval, roundedboundval);
2711 }
2712
2713 /* resolve propagation */
2714 SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, bdchgidx, &boundval, &success) );
2715
2716 if( success )
2717 *result = SCIP_SUCCESS;
2718
2719 return SCIP_OKAY;
2720}
2721
2722/** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
2723static
2724SCIP_DECL_PROPEXITSOL(propExitsolGenvbounds)
2725{ /*lint --e{715}*/
2726 SCIP_PROPDATA* propdata;
2727
2728 assert(scip != NULL);
2729 assert(prop != NULL);
2730 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2731
2732 SCIPdebugMsg(scip, "propexitsol in problem <%s>\n", SCIPgetProbName(scip));
2733
2734 /* get propagator data */
2735 propdata = SCIPpropGetData(prop);
2736 assert(propdata != NULL);
2737
2738 if( !SCIPisInRestart(scip) )
2739 {
2740 /* free all genvbounds if we are not in a restart */
2741 SCIP_CALL( freeGenVBounds(scip, propdata) );
2742 }
2743 else
2744 {
2745 /* free all genvbounds that use relax-only variables if we are in a restart */
2747 }
2748
2749 /* drop and free all events */
2750 SCIP_CALL( dropAndFreeEvents(scip, propdata) );
2751
2752 return SCIP_OKAY;
2753}
2754
2755/** destructor of propagator to free user data (called when SCIP is exiting) */
2756static
2757SCIP_DECL_PROPFREE(propFreeGenvbounds)
2758{ /*lint --e{715}*/
2759 SCIP_PROPDATA* propdata;
2760
2761 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2762
2763 /* free propagator data */
2764 propdata = SCIPpropGetData(prop);
2765 assert(propdata != NULL);
2766
2767 SCIPfreeBlockMemory(scip, &propdata);
2768
2769 SCIPpropSetData(prop, NULL);
2770
2771 return SCIP_OKAY;
2772}
2773
2774
2775/*
2776 * Callback methods of event handler
2777 */
2778
2779static
2780SCIP_DECL_EVENTEXEC(eventExecGenvbounds)
2781{ /*lint --e{715}*/
2782 SCIP_PROPDATA* propdata;
2783 int i;
2784
2785 assert(scip != NULL);
2786 assert(eventdata != NULL);
2787
2790
2791 assert(eventdata->startcomponents != NULL);
2792 assert(eventdata->startindices != NULL);
2793 assert(eventdata->nstarts > 0);
2794 assert(eventdata->prop != NULL);
2795
2796 propdata = SCIPpropGetData(eventdata->prop);
2797 assert(propdata != NULL);
2798
2799 assert(propdata->startcomponents != NULL);
2800 assert(propdata->startmap != NULL);
2801 assert(propdata->startindices != NULL);
2802
2803 SCIPdebugMsg(scip, "catching eventdata:\n");
2804 SCIPdebug( printEventData(eventdata, SCIPeventGetType(event) == SCIP_EVENTTYPE_LBTIGHTENED ?
2806
2807 /* check if we need to reset old local starting indices data */
2808 if( SCIPgetCurrentNode(scip) != propdata->lastnodecaught )
2809 {
2811 propdata->lastnodecaught = SCIPgetCurrentNode(scip);
2812 }
2813
2814 for( i = 0; i < eventdata->nstarts; i++ )
2815 {
2816 int component;
2817 int startidx;
2818
2819 component = eventdata->startcomponents[i];
2820 assert(component >= 0);
2821 startidx = eventdata->startindices[i];
2822
2823 /* there is already an entry for this component */
2824 if( SCIPhashmapExists(propdata->startmap, (void*)(size_t) (component + 1)) )
2825 {
2826 int componentidx;
2827
2828 /* get its index */
2829 componentidx = (SCIPhashmapGetImageInt(propdata->startmap, (void*)(size_t) (component + 1))) - 1; /*lint !e571 !e776*/
2830 assert(componentidx >= 0);
2831 assert(propdata->startcomponents[componentidx] == component);
2832
2833 if( propdata->startindices[componentidx] > startidx )
2834 propdata->startindices[componentidx] = startidx;
2835 }
2836 else
2837 {
2838 /* get a new entry */
2839 int componentidx;
2840 componentidx = propdata->nindices;
2841
2842 /* store index */
2843 propdata->startcomponents[componentidx] = component;
2844 propdata->startindices[componentidx] = startidx;
2845
2846 /* store component in hashmap */
2847 SCIP_CALL( SCIPhashmapInsertInt(propdata->startmap, (void*)(size_t) (component + 1), componentidx + 1) ); /*lint !e571 !e776*/
2848
2849 /* increase number of starting indices */
2850 propdata->nindices++;
2851 }
2852 }
2853
2854 return SCIP_OKAY;
2855}
2856
2857/*
2858 * propagator specific interface methods
2859 */
2860
2861/** creates the genvbounds propagator and includes it in SCIP */
2863 SCIP* scip /**< SCIP data structure */
2864 )
2865{
2866 SCIP_PROPDATA* propdata;
2867 SCIP_PROP* prop;
2868
2869 /* create genvbounds propagator data */
2870 SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
2871
2872 /* include propagator */
2874 propExecGenvbounds, propdata) );
2875
2876 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyGenvbounds) );
2877 SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeGenvbounds) );
2878 SCIP_CALL( SCIPsetPropInit(scip, prop, propInitGenvbounds) );
2879 SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreGenvbounds) );
2880 SCIP_CALL( SCIPsetPropExitpre(scip, prop, propExitpreGenvbounds) );
2881 SCIP_CALL( SCIPsetPropExit(scip, prop, propExitGenvbounds) );
2882 SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolGenvbounds) );
2883 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolGenvbounds, PROP_PRESOL_PRIORITY,
2885 SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropGenvbounds) );
2886
2887 SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/global",
2888 "apply global propagation?",
2889 &propdata->global, TRUE, DEFAULT_GLOBAL_PROPAGATION, NULL, NULL) );
2890
2891 SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/propinrootnode",
2892 "apply genvbounds in root node if no new incumbent was found?",
2893 &propdata->propinrootnode, TRUE, DEFAULT_PROPAGATE_IN_ROOT_NODE, NULL, NULL) );
2894
2895 SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/sort",
2896 "sort genvbounds and wait for bound change events?",
2897 &propdata->sort, TRUE, DEFAULT_SORT, NULL, NULL) );
2898
2899 SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/propasconss",
2900 "should genvbounds be transformed to (linear) constraints?",
2901 &propdata->propasconss, TRUE, DEFAULT_PROPASCONSS, NULL, NULL) );
2902
2903 /* include event handler */
2904 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecGenvbounds, NULL) );
2905
2906 return SCIP_OKAY;
2907}
static long bound
Constraint handler for linear constraints in their most general form, .
methods for debugging
#define SCIPdebugCheckLbGlobal(scip, var, lb)
Definition: debug.h:285
#define SCIPdebugGetSolVal(scip, var, val)
Definition: debug.h:299
#define SCIPdebugCheckUbGlobal(scip, var, ub)
Definition: debug.h:286
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define SCIP_UNKNOWN
Definition: def.h:194
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
#define nnodes
Definition: gastrans.c:74
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, 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 SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition: misc.c:8089
int SCIPdigraphGetNNodes(SCIP_DIGRAPH *digraph)
Definition: misc.c:7746
void SCIPdigraphGetComponent(SCIP_DIGRAPH *digraph, int compidx, int **nodes, int *nnodes)
Definition: misc.c:8298
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7662
SCIP_RETCODE SCIPdigraphTopoSortComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8219
SCIP_RETCODE SCIPdigraphComputeDirectedComponents(SCIP_DIGRAPH *digraph, int compidx, int *strongcomponents, int *strongcompstartidx, int *nstrongcomponents)
Definition: misc.c:8430
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
Definition: misc.c:7568
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8285
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
SCIP_Real SCIPgetTransObjoffset(SCIP *scip)
Definition: scip_prob.c:1367
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
int SCIPgetNFixedVars(SCIP *scip)
Definition: scip_prob.c:2309
int SCIPgetNTotalVars(SCIP *scip)
Definition: scip_prob.c:2569
SCIP_Real SCIPgetTransObjscale(SCIP *scip)
Definition: scip_prob.c:1390
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
SCIP_RETCODE SCIPhashmapRemoveAll(SCIP_HASHMAP *hashmap)
Definition: misc.c:3633
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3439
#define SCIPdebugMsgPrint
Definition: scip_message.h:79
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPgenVBoundAdd(SCIP *scip, SCIP_PROP *genvboundprop, SCIP_VAR **vars, SCIP_VAR *var, SCIP_Real *coefs, int ncoefs, SCIP_Real coefcutoffbound, SCIP_Real constant, SCIP_BOUNDTYPE boundtype)
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 SCIPincludePropGenvbounds(SCIP *scip)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPaddConflictRelaxedLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedlb)
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
SCIP_RETCODE SCIPaddConflictRelaxedUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedub)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
SCIP_Real SCIPgetConflictVarUb(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPgetConflictVarLb(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
SCIP_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:354
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#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_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:799
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:312
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:789
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:279
SCIP_RETCODE SCIPsetPropExitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITPRE((*propexitpre)))
Definition: scip_prop.c:263
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:941
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip_prop.c:199
SCIP_RETCODE SCIPsetPropInit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINIT((*propinit)))
Definition: scip_prop.c:183
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:247
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:167
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:151
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:231
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:114
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1347
SCIP_Bool SCIPisInRestart(SCIP *scip)
Definition: scip_solve.c:3591
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
Definition: scip_var.c:1738
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17748
SCIP_RETCODE SCIPinferVarUbProp(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_PROP *inferprop, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6010
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6348
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4259
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2128
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_Bool SCIPvarIsRelaxationOnly(SCIP_VAR *var)
Definition: var.c:17706
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8715
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1992
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:194
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition: scip_var.c:8656
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition: scip_var.c:8629
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6228
SCIP_RETCODE SCIPinferVarLbProp(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_PROP *inferprop, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5895
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:134
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
#define PROP_PRESOL_MAXROUNDS
#define PROP_PRESOLTIMING
#define PROP_DESC
static SCIP_RETCODE addEventData(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, int startindex, int startcomponent, SCIP_BOUNDTYPE boundtype)
static SCIP_RETCODE freeComponentsData(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_DECL_PROPRESPROP(propRespropGenvbounds)
#define DEFAULT_PROPAGATE_IN_ROOT_NODE
static SCIP_RETCODE analyzeGenVBoundConflict(SCIP *scip, GENVBOUND *genvbound)
static SCIP_DECL_PROPCOPY(propCopyGenvbounds)
static SCIP_RETCODE execGenVBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_RESULT *result, SCIP_Bool local, int *nchgbds)
#define PROP_NAME
static SCIP_Real getGenVBoundsMinActivityConflict(SCIP *scip, SCIP_VAR **vars, SCIP_Real *coefs, int nvars, SCIP_BDCHGIDX *bdchgidx)
static SCIP_DECL_PROPINITPRE(propInitpreGenvbounds)
static SCIP_Real getGenVBoundsMinActivity(SCIP *scip, SCIP_VAR **vars, SCIP_Real *coefs, int nvars, SCIP_Bool global)
static SCIP_Real getGenVBoundsBound(SCIP *scip, GENVBOUND *genvbound, SCIP_Bool global)
static SCIP_RETCODE freeEventData(SCIP *scip, SCIP_EVENTDATA **eventdata)
static SCIP_RETCODE dropAndFreeEvents(SCIP *scip, SCIP_PROPDATA *propdata)
#define DEFAULT_PROPASCONSS
static SCIP_RETCODE setUpEvents(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE sortGenVBounds(SCIP *scip, SCIP_PROPDATA *propdata)
#define DEFAULT_SORT
static SCIP_DECL_PROPEXEC(propExecGenvbounds)
static SCIP_DECL_PROPFREE(propFreeGenvbounds)
static SCIP_RETCODE fillGlobalStartingData(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE resetLocalStartingData(SCIP *scip, SCIP_PROPDATA *propdata)
#define PROP_DELAY
static GENVBOUND * getGenVBound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype)
static SCIP_RETCODE freeGenVBoundsRelaxOnly(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE freeGenVBound(SCIP *scip, GENVBOUND *genvbound)
static SCIP_Real getCutoffboundGenVBound(SCIP *scip)
static SCIP_RETCODE applyGenVBounds(SCIP *scip, SCIP_PROP *prop, SCIP_Bool global, SCIP_RESULT *result, int *nchgbds)
#define DEFAULT_GLOBAL_PROPAGATION
static SCIP_RETCODE freeStartingData(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_DECL_PROPEXITSOL(propExitsolGenvbounds)
static SCIP_RETCODE addNewGenVBound(SCIP *scip, SCIP_PROPDATA *propdata, GENVBOUND *genvbound)
#define PROP_TIMING
static SCIP_RETCODE getEventData(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_EVENTDATA **eventdata)
static SCIP_DECL_EVENTEXEC(eventExecGenvbounds)
static SCIP_DECL_PROPPRESOL(propPresolGenvbounds)
static SCIP_RETCODE createStartingData(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_DECL_PROPEXITPRE(propExitpreGenvbounds)
static SCIP_DECL_PROPEXIT(propExitGenvbounds)
static SCIP_RETCODE applyGenVBound(SCIP *scip, SCIP_PROP *prop, GENVBOUND *genvbound, SCIP_Bool global, SCIP_RESULT *result, int *nchgbds)
static SCIP_RETCODE freeAllEventData(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_DECL_PROPINIT(propInitGenvbounds)
#define EVENTHDLR_DESC
static SCIP_RETCODE createConstraints(SCIP *scip, SCIP_PROPDATA *propdata)
#define EVENTHDLR_NAME
static SCIP_RETCODE resolveGenVBoundPropagation(SCIP *scip, GENVBOUND *genvbound, SCIP_BDCHGIDX *bdchgidx, SCIP_Real *boundval, SCIP_Bool *success)
#define PROP_FREQ
static SCIP_RETCODE freeGenVBounds(SCIP *scip, SCIP_PROPDATA *propdata)
#define PROP_PRIORITY
static SCIP_RETCODE initPropdata(SCIP *scip, SCIP_PROPDATA *propdata)
#define PROP_PRESOL_PRIORITY
generalized variable bounds propagator
public methods for managing events
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
#define SCIPdebug(x)
Definition: pub_message.h:93
#define SCIPdebugMessage
Definition: pub_message.h:96
#define SCIPdebugPrintf
Definition: pub_message.h:99
public data structures and miscellaneous methods
public methods for propagators
public methods for problem variables
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for data structures
public methods for event handler plugins and event handlers
general public methods
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for propagator plugins
public methods for solutions
public solving methods
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
SCIP_BOUNDTYPE boundtype
SCIP_Real constant
SCIP_Real * coefs
SCIP_VAR * var
SCIP_VAR ** vars
SCIP_Real cutoffcoef
SCIP_Bool relaxonly
@ SCIP_CONFTYPE_PROPAGATION
Definition: type_conflict.h:60
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:173
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:79
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:77
@ 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
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:52
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SUCCESS
Definition: type_result.h:58
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_PRESOLVING
Definition: type_set.h:49
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:54
@ SCIP_VARSTATUS_AGGREGATED
Definition: type_var.h:53
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97