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