Scippy

SCIP

Solving Constraint Integer Programs

prop_vbounds.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file prop_vbounds.c
26 * @ingroup DEFPLUGINS_PROP
27 * @brief variable upper and lower bound propagator
28 * @author Stefan Heinz
29 * @author Jens Schulz
30 * @author Gerald Gamrath
31 * @author Marc Pfetsch
32 *
33 * This propagator uses global bound information provided by SCIP to deduce global and local bound changes.
34 * It can take into account
35 * - implications (bound change following from specific value of a binary variable)
36 * - cliques (set of binary variables, each with a corresponding value, of which at most one variable can get the value)
37 * - variable lower/upper bounds (bounds of arbitrary variables that depend linearly on the value of another variable)
38 *
39 * The propagator does not look at a variable in whole, but at one point in time only handles one specific bound (lower
40 * or upper) of a variable and deduces changes for lower or upper bounds of other variables. The concept is as follows:
41 *
42 * 1) Extract variable bound data
43 *
44 * Implications and cliques are stored in a way such that given a variable and its new value, we can access all bound
45 * changes that can be deduced from setting the variable to that value. However, for variable bounds, this currently
46 * does not hold, they are only stored in the other direction, i.e. for a bound of a given variable, we have a list
47 * of all other bounds of variables that directly influence the bound of the given variable and a linear function
48 * describing how they do this.
49 * For the propagation, we need the other direction, thus we store it in the propagator data when the branch-and-bound
50 * solving process is about to begin.
51 *
52 * 2) Topological sorting of bounds of variable
53 *
54 * We compute a topological order of the bounds of variables. This is needed to define an order in which we will
55 * regard bounds of variables in the propagation process in order to avoid unneccessarily regarding the same variable
56 * bound multiple times because it was changed in the meantime when propagating another bound of a variable.
57 * Therefore, we implictly regard a directed graph, in which each node corresponds to a bound of a variable and there
58 * exists a directed edge from one node to another, if the bound corresponding to the former node influences the
59 * bound corresponding to the latter node. This is done by iteratively running a DFS until all nodes were visited.
60 * Note that there might be cycles in the graph, which are randomly broken, so the order is only almost topological.
61 *
62 * 3) Collecting bound changes
63 *
64 * For each bound of a variable, which can trigger bound changes of other variables, the propagator catches all
65 * events informing about a global change of the bound or a local tightening of the bound. The event handler
66 * then adds the bound of the variable to a priority queue, with the key in the priority queue corresponding
67 * to the position of the bound in the topological sort.
68 *
69 * 4) Propagating Bounds
70 *
71 * As long as there are bounds contained in the priority queue, the propagator pops one bound from the queue, which
72 * is the one most at the beginning of the topological sort, so it should not be influenced by propagating other
73 * bounds currently contained in the queue. Starting at this bound, all implication, clique, and variable bound
74 * information is used to deduce tigther bounds for other variables and change the bounds, if a tighter one is found.
75 * These bound changes trigger an event that will lead to adding the corresponding bound to the priority queue,
76 * if it is not contained, yet. The process is iterated until the priority queue contains no more bounds.
77 *
78 * Additionally, the propagator analyzes the conflict/clique graph during presolving. It uses Tarjan's algorithm to
79 * search for strongly connected components, for each of which all variables can be aggregated to one. Additionally,
80 * it may detect invalid assignments of binary variables and fix the variable to the only possible value left.
81 */
82
83/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
84
86#include "scip/prop_vbounds.h"
87#include "scip/pub_event.h"
88#include "scip/pub_implics.h"
89#include "scip/pub_message.h"
90#include "scip/pub_misc.h"
91#include "scip/pub_prop.h"
92#include "scip/pub_var.h"
93#include "scip/scip_conflict.h"
94#include "scip/scip_event.h"
95#include "scip/scip_general.h"
96#include "scip/scip_mem.h"
97#include "scip/scip_message.h"
98#include "scip/scip_numerics.h"
99#include "scip/scip_param.h"
100#include "scip/scip_prob.h"
101#include "scip/scip_prop.h"
102#include "scip/scip_tree.h"
103#include "scip/scip_var.h"
104#include <string.h>
105
106/**@name Propagator properties
107 *
108 * @{
109 */
110
111#define PROP_NAME "vbounds"
112#define PROP_DESC "propagates variable upper and lower bounds"
113#define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP
114#define PROP_PRIORITY 3000000 /**< propagator priority */
115#define PROP_FREQ 1 /**< propagator frequency */
116#define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
117
118#define PROP_PRESOL_PRIORITY -90000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
119#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM | SCIP_PRESOLTIMING_EXHAUSTIVE
120#define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
121 * limit) */
122/**@} */
123
124/**@name Event handler properties
125 *
126 * @{
127 */
128
129#define EVENTHDLR_NAME "vbounds"
130#define EVENTHDLR_DESC "bound change event handler for for vbounds propagator"
131
132/**@} */
133
134/**@name Default parameter values
135 *
136 * @{
137 */
138
139#define DEFAULT_USEBDWIDENING TRUE /**< should bound widening be used to initialize conflict analysis? */
140#define DEFAULT_USEIMPLICS FALSE /**< should implications be propagated? */
141#define DEFAULT_USECLIQUES FALSE /**< should cliques be propagated? */
142#define DEFAULT_USEVBOUNDS TRUE /**< should variable bounds be propagated? */
143#define DEFAULT_DOTOPOSORT TRUE /**< should the bounds be topologically sorted in advance? */
144#define DEFAULT_SORTCLIQUES FALSE /**< should cliques be regarded for the topological sort? */
145#define DEFAULT_DETECTCYCLES FALSE /**< should cycles in the variable bound graph be identified? */
146#define DEFAULT_MINNEWCLIQUES 0.1 /**< minimum number of new cliques to trigger another clique table analysis */
147#define DEFAULT_MAXCLIQUESMEDIUM 50.0 /**< maximum number of cliques per variable to run clique table analysis in
148 * medium presolving */
149#define DEFAULT_MAXCLIQUESEXHAUSTIVE 100.0 /**< maximum number of cliques per variable to run clique table analysis in
150 * exhaustive presolving */
151
152/**@} */
153
154/**@name Propagator defines
155 *
156 * @{
157 *
158 * The propagator works on indices representing a bound of a variable. This index will be called bound index in the
159 * following. For a given active variable with problem index i (note that active variables have problem indices
160 * between 0 and nactivevariable - 1), the bound index of its lower bound is 2*i, the bound index of its upper
161 * bound is 2*i + 1. The other way around, a given bound index i corresponds to the variable with problem index
162 * i/2 (rounded down), and to the lower bound, if i is even, to the upper bound if i is odd.
163 * The following macros can be used to convert bound index into variable problem index and boundtype and vice versa.
164 */
165#define getLbIndex(idx) (2*(idx))
166#define getUbIndex(idx) (2*(idx)+1)
167#define getVarIndex(idx) ((idx)/2)
168#define getBoundtype(idx) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)
169#define isIndexLowerbound(idx) ((idx) % 2 == 0)
170#define getBoundString(lower) ((lower) ? "lb" : "ub")
171#define getBoundtypeString(type) ((type) == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper")
172#define indexGetBoundString(idx) (getBoundString(isIndexLowerbound(idx)))
173#define getOtherBoundIndex(idx) ((idx) + 1 - 2 * ((idx) % 2))
174
175/**@} */
176
177/*
178 * Data structures
179 */
180
181/** propagator data */
182struct SCIP_PropData
183{
184 SCIP_EVENTHDLR* eventhdlr; /**< event handler for catching bound changes */
185 SCIP_VAR** vars; /**< array containing all variable which are considered within the propagator */
186 SCIP_HASHMAP* varhashmap; /**< hashmap mapping from variable to index in the vars array */
187 int* topoorder; /**< array mapping on the bounds of variables in topological order;
188 * or -1, if the bound that should be at that position has no outgoing
189 * implications, cliques, or vbounds;
190 * i.e., for i < j and topoorder[i] != -1 != topoorder[j], the variable
191 * and boundtype represented by index topoorder[i] are earlier in the
192 * topological order than those represented by index topoorder[j]
193 */
194 int** vboundboundedidx; /**< array storing for each bound index the bound indices of all bounds
195 * influenced by this bound through variable bounds */
196 SCIP_Real** vboundcoefs; /**< array storing for each bound index the coefficients in the variable
197 * bounds influencing the corresponding bound index stored in
198 * vboundboundedidx */
199 SCIP_Real** vboundconstants; /**< array storing for each bound index the constants in the variable
200 * bounds influencing the corresponding bound index stored in
201 * vboundboundedidx */
202 int* nvbounds; /**< array storing for each bound index the number of vbounds stored */
203 int* vboundsize; /**< array with sizes of vbound arrays for the nodes */
204 int nbounds; /**< number of bounds of variables regarded (two times number of active variables) */
205 int lastpresolncliques; /**< number of cliques created until the last call to the presolver */
206 SCIP_PQUEUE* propqueue; /**< priority queue to handle the bounds of variables that were changed and have to be propagated */
207 SCIP_Bool* inqueue; /**< boolean array to store whether a bound of a variable is already contained in propqueue */
208 SCIP_Bool initialized; /**< was the data for propagation already initialized? */
209 SCIP_Real minnewcliques; /**< minimum percentage of new cliques to trigger another clique table analysis */
210 SCIP_Real maxcliquesmedium; /**< maximum number of cliques per variable to run clique table analysis in medium presolving */
211 SCIP_Real maxcliquesexhaustive;/**< maximum number of cliques per variable to run clique table analysis in exhaustive presolving */
212 SCIP_Bool usebdwidening; /**< should bound widening be used to initialize conflict analysis? */
213 SCIP_Bool useimplics; /**< should implications be propagated? */
214 SCIP_Bool usecliques; /**< should cliques be propagated? */
215 SCIP_Bool usevbounds; /**< should variable bounds be propagated? */
216 SCIP_Bool dotoposort; /**< should the bounds be topologically sorted in advance? */
217 SCIP_Bool sortcliques; /**< should cliques be regarded for the topological sort? */
218 SCIP_Bool detectcycles; /**< should cycles in the variable bound graph be identified? */
219};
220
221/** inference information */
222struct InferInfo
223{
224 union
225 {
226 struct
227 {
228 unsigned int pos:31; /**< position of the variable which forced that propagation */
229 unsigned int boundtype:1; /**< bound type which was the reason (0: lower, 1: upper) */
230 } asbits;
231 int asint; /**< inference information as a single int value */
232 } val;
233};
234typedef struct InferInfo INFERINFO;
235
236/** converts an integer into an inference information */
237static
239 int i /**< integer to convert */
240 )
241{
242 INFERINFO inferinfo;
243
244 inferinfo.val.asint = i;
245
246 return inferinfo;
247}
248
249/** converts an inference information into an int */
250static
252 INFERINFO inferinfo /**< inference information to convert */
253 )
254{
255 return inferinfo.val.asint;
256}
257
258/** returns the propagation rule stored in the inference information */
259static
261 INFERINFO inferinfo /**< inference information to convert */
262 )
263{
264 assert((SCIP_BOUNDTYPE)inferinfo.val.asbits.boundtype == SCIP_BOUNDTYPE_LOWER
265 || (SCIP_BOUNDTYPE)inferinfo.val.asbits.boundtype == SCIP_BOUNDTYPE_UPPER);
266 return (SCIP_BOUNDTYPE)inferinfo.val.asbits.boundtype;
267}
268
269/** returns the position stored in the inference information */
270static
272 INFERINFO inferinfo /**< inference information to convert */
273 )
274{
275 return (int) inferinfo.val.asbits.pos;
276}
277
278/** constructs an inference information out of a position of a variable and a boundtype */
279static
281 int pos, /**< position of the variable which forced that propagation */
282 SCIP_BOUNDTYPE boundtype /**< propagation rule that deduced the value */
283 )
284{
285 INFERINFO inferinfo;
286
287 assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
288 assert(pos >= 0);
289
290 inferinfo.val.asbits.pos = (unsigned int) pos; /*lint !e732*/
291 inferinfo.val.asbits.boundtype = (unsigned int) boundtype; /*lint !e641*/
292
293 return inferinfo;
294}
295
296/*
297 * Local methods
298 */
299
300/* returns the lower bound index of a variable */
301static
303 SCIP_PROPDATA* propdata, /**< propagator data */
304 SCIP_VAR* var /**< variable to get the index for */
305 )
306{
307 int i;
308
309 i = SCIPhashmapGetImageInt(propdata->varhashmap, var);
310
311 assert(SCIPhashmapExists(propdata->varhashmap, var) == (i != INT_MAX));
312 assert(i >= 0);
313
314 return getLbIndex(i == INT_MAX ? -1 : i);
315}
316
317/* returns the upper bound index of a variable */
318static
320 SCIP_PROPDATA* propdata, /**< propagator data */
321 SCIP_VAR* var /**< variable to get the index for */
322 )
323{
324 int i;
325
326 i = SCIPhashmapGetImageInt(propdata->varhashmap, var);
327
328 assert(SCIPhashmapExists(propdata->varhashmap, var) == (i != INT_MAX));
329 assert(i >= 0);
330
331 return getUbIndex(i == INT_MAX ? -1 : i);
332}
333
334/** reset propagation data */
335static
337 SCIP_PROPDATA* propdata /**< propagator data */
338 )
339{
340 propdata->vars = NULL;
341 propdata->varhashmap = NULL;
342 propdata->topoorder = NULL;
343 propdata->vboundboundedidx = NULL;
344 propdata->vboundcoefs = NULL;
345 propdata->vboundconstants = NULL;
346 propdata->nvbounds = NULL;
347 propdata->vboundsize = NULL;
348 propdata->nbounds = 0;
349 propdata->initialized = FALSE;
350}
351
352/** catches events for variables */
353static
355 SCIP* scip, /**< SCIP data structure */
356 SCIP_PROPDATA* propdata /**< propagator data */
357 )
358{
359 SCIP_EVENTHDLR* eventhdlr;
360 SCIP_EVENTTYPE eventtype;
361 SCIP_VAR** vars;
362 SCIP_VAR* var;
363 SCIP_Bool lower;
364 int nbounds;
365 int v;
366 int idx;
367
368 assert(scip != NULL);
369 assert(propdata != NULL);
370 assert(propdata->vars != NULL);
371 assert(propdata->topoorder != NULL);
372
373 /* catch variable events according to computed eventtypes */
374 eventhdlr = propdata->eventhdlr;
375 assert(eventhdlr != NULL);
376
377 vars = propdata->vars;
378 nbounds = propdata->nbounds;
379
380 /* setup events */
381 for( v = 0; v < nbounds; ++v )
382 {
383 idx = propdata->topoorder[v];
384 assert(idx >= 0 && idx < nbounds);
385
386 var = vars[getVarIndex(idx)];
387 lower = isIndexLowerbound(idx);
388
389 /* if the bound does not influence another bound by implications, cliques, or vbounds,
390 * we do not create an event and do not catch changes of the bound;
391 * we mark this by setting the value in topoorder to -1
392 */
393 if( propdata->nvbounds[idx] == 0 && SCIPvarGetNImpls(var, lower) == 0 && SCIPvarGetNCliques(var, lower) == 0 )
394 {
395 propdata->topoorder[v] = -1;
396 continue;
397 }
398
399 /* determine eventtype that we want to catch depending on boundtype of variable */
400 if( lower )
402 else
404
405 SCIP_CALL( SCIPcatchVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (uintptr_t) v, NULL) ); /*lint !e571*/
406 }
407
408 return SCIP_OKAY;
409}
410
411/** drops events for variables */
412static
414 SCIP* scip, /**< SCIP data structure */
415 SCIP_PROPDATA* propdata /**< propagator data */
416 )
417{
418 SCIP_EVENTHDLR* eventhdlr;
419 SCIP_EVENTTYPE eventtype;
420 SCIP_VAR** vars;
421 SCIP_VAR* var;
422 SCIP_Bool lower;
423 int nbounds;
424 int v;
425 int idx;
426
427 assert(propdata != NULL);
428
429 eventhdlr = propdata->eventhdlr;
430 assert(eventhdlr != NULL);
431
432 vars = propdata->vars;
433 nbounds = propdata->nbounds;
434
435 for( v = 0; v < nbounds; ++v )
436 {
437 idx = propdata->topoorder[v];
438
439 if( idx == -1 )
440 continue;
441
442 assert(idx >= 0 && idx < nbounds);
443
444 var = vars[getVarIndex(idx)];
445 lower = isIndexLowerbound(idx);
446
447 /* determine eventtype that we catch and now want to drop depending on boundtype of variable */
448 if( lower )
450 else
452
453 SCIP_CALL( SCIPdropVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*) (uintptr_t) v, -1) ); /*lint !e571*/
454 }
455
456 return SCIP_OKAY;
457}
458
459#define INITMEMSIZE 5
460
461/* adds a vbound to the propagator data to store it internally and allow forward propagation */
462static
464 SCIP* scip, /**< SCIP data structure */
465 SCIP_PROPDATA* propdata, /**< propagator data */
466 int startidx, /**< index of bound of variable influencing the other variable */
467 int endidx, /**< index of bound of variable which is influenced */
468 SCIP_Real coef, /**< coefficient in the variable bound */
469 SCIP_Real constant /**< constant in the variable bound */
470 )
471{
472 int nvbounds;
473
474 assert(scip != NULL);
475 assert(propdata != NULL);
476
477 if( propdata->vboundsize[startidx] == 0 )
478 {
479 /* allocate memory for storing vbounds */
480 propdata->vboundsize[startidx] = INITMEMSIZE;
481
482 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundboundedidx[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
483 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundcoefs[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
484 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundconstants[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
485 }
486 else if( propdata->nvbounds[startidx] >= propdata->vboundsize[startidx] )
487 {
488 /* reallocate memory for storing vbounds */
489 propdata->vboundsize[startidx] = SCIPcalcMemGrowSize(scip, propdata->nvbounds[startidx] + 1);
490 assert(propdata->nvbounds[startidx] < propdata->vboundsize[startidx]);
491
492 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundboundedidx[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
493 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundcoefs[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
494 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->vboundconstants[startidx], propdata->vboundsize[startidx]) ); /*lint !e866*/
495 }
496
497 nvbounds = propdata->nvbounds[startidx];
498 propdata->vboundboundedidx[startidx][nvbounds] = endidx;
499 propdata->vboundcoefs[startidx][nvbounds] = coef;
500 propdata->vboundconstants[startidx][nvbounds] = constant;
501 (propdata->nvbounds[startidx])++;
502
503 return SCIP_OKAY;
504}
505
506/** comparison method for two indices in the topoorder array, preferring higher indices because the order is reverse
507 * topological
508 */
509static
510SCIP_DECL_SORTPTRCOMP(compVarboundIndices)
511{
512 int idx1 = (int)(size_t)elem1;
513 int idx2 = (int)(size_t)elem2;
514
515 return idx2 - idx1;
516}
517
518/* extract bound changes or infeasibility information from a cycle in the variable bound graph detected during
519 * depth-first search
520 */
521static
523 SCIP* scip, /**< SCIP data structure */
524 SCIP_PROPDATA* propdata, /**< propagator data */
525 int* dfsstack, /**< array of size number of nodes to store the stack;
526 * only needed for performance reasons */
527 int* stacknextedge, /**< array storing the next edge to be visited in dfs for all nodes on the
528 * stack/in the current path; negative numbers represent a clique,
529 * positive numbers an implication (smaller numbers) or a variable bound */
530 int stacksize, /**< current stack size */
531 SCIP_Bool samebound, /**< does the cycle contain the same bound twice or both bounds of the same variable? */
532 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
533
534 )
535{
536 SCIP_VAR** vars;
537 SCIP_VAR* currvar;
538 SCIP_Bool currlower;
539
540 SCIP_Real coef = 1.0;
541 SCIP_Real constant = 0.0;
542 SCIP_Bool islower;
543 SCIP_Real newbound;
544 int cycleidx;
545 int startidx;
546 int ntmpimpls;
547 int j;
548 int k;
549
550 assert(scip != NULL);
551 assert(propdata != NULL);
552
553 vars = propdata->vars;
554
555 /* the last element on the stack is the end-point of the cycle */
556 cycleidx = dfsstack[stacksize - 1];
557
558 /* the same bound of the variable was visited already earlier on the current path, so the start-point of the cycle
559 * has the same index
560 */
561 if( samebound )
562 startidx = cycleidx;
563 /* the other bound of the variable was visited earlier on the current path, so the start-point of the cycle
564 * has the index of the other bound
565 */
566 else
567 startidx = getOtherBoundIndex(cycleidx);
568
569 /* search for the start-point of the cycle; since the endpoint is at position stacksize - 1 we start at stacksize - 2
570 * and go backwards
571 */
572 for( j = stacksize - 2; dfsstack[j] != startidx && j >= 0; --j ){};
573 assert(j >= 0);
574
575 for( ; j < stacksize - 1; ++j )
576 {
577 currvar = vars[getVarIndex(dfsstack[j])];
578 currlower = isIndexLowerbound(dfsstack[j]);
579
580 /* if we do not use implications, we assume the number of implications to be 0 (as we did before) */
581 ntmpimpls = (propdata->useimplics ? SCIPvarGetNImpls(currvar, currlower) : 0);
582
583 /* stacknextedge[j] <= 0 --> the last outgoing edge traversed during dfs starting from node dfsstack[j] was given
584 * by a clique
585 */
586 if( stacknextedge[j] <= 0 )
587 {
588 SCIP_Bool nextlower = isIndexLowerbound(dfsstack[j+1]);
589#if defined(SCIP_DEBUG) || defined(SCIP_MORE_DEBUG)
590 SCIP_CLIQUE** tmpcliques = SCIPvarGetCliques(currvar, currlower);
591 SCIP_VAR** cliquevars;
592 SCIP_Bool* cliquevals;
593 int ntmpcliques = SCIPvarGetNCliques(currvar, currlower);
594 int ncliquevars;
595 int v;
596#endif
597 /* there are four cases:
598 * a) lb(x) -> ub(y) ==> clique(x,y,...) ==> y <= 1 - x
599 * b) lb(x) -> lb(y) ==> clique(x,~y,...) ==> y >= x
600 * c) ub(x) -> ub(y) ==> clique(~x,y,...) ==> y <= x
601 * d) ub(x) -> lb(y) ==> clique(~x,~y,...) ==> y >= 1 - x
602 *
603 * in cases b) and c), coef=1.0 and constant=0.0; these are the cases where both nodes represent
604 * the same type of bound
605 * in cases a) and d), coef=-1.0 and constant=1.0; both nodes represent different types of bounds
606 *
607 * we do not need to change the overall coef and constant in cases b) and c), but for the others
608 */
609 if( currlower != nextlower )
610 {
611 coef = -coef;
612 constant = -constant + 1.0;
613 }
614
615 /* since the coefficient and constant only depend on the type of bounds of the two nodes (see below), we do not
616 * need to search for the variable in the clique; however, if debug output is enabled, we want to print the
617 * clique, if more debugging is enabled, we explicitly check that the variable and bound we expect are in the
618 * clique
619 */
620#if defined(SCIP_DEBUG) || defined(SCIP_MORE_DEBUG)
621 if( stacknextedge[j] == 0 )
622 {
623 k = ntmpcliques - 1;
624 }
625 else
626 {
627 /* we processed at least one edge, so the next one should be -2 or smaller (we have a -1 offset) */
628 assert(stacknextedge[j] <= -2);
629
630 k = -stacknextedge[j] - 2;
631
632 assert(k < ntmpcliques);
633 }
634
635 cliquevars = SCIPcliqueGetVars(tmpcliques[k]);
636 cliquevals = SCIPcliqueGetValues(tmpcliques[k]);
637 ncliquevars = SCIPcliqueGetNVars(tmpcliques[k]);
638#ifdef SCIP_DEBUG
639 SCIPdebugMsg(scip, "clique: ");
640 for( v = 0; v < ncliquevars; ++v )
641 {
642 SCIPdebugMsg(scip, "%s%s ", cliquevals[v] ? "" : "~", SCIPvarGetName(cliquevars[v]));
643 }
644 SCIPdebugMsg(scip, "(equation:%d)\n", SCIPcliqueIsEquation(tmpcliques[k]));
645#endif
646#ifdef SCIP_MORE_DEBUG
647 for( v = 0; v < ncliquevars; ++v )
648 {
649 if( cliquevars[v] == vars[getVarIndex(dfsstack[j+1])] && cliquevals[v] == !nextlower )
650 break;
651 }
652 assert(v < ncliquevars);
653#endif
654
655 SCIPdebugMsg(scip, "%s(%s) -- (*%g + %g)[clique(<%s%s>,<%s%s>,...)] --> %s(%s)\n",
656 indexGetBoundString(dfsstack[j]), SCIPvarGetName(currvar),
657 (currlower != nextlower ? -1.0 : 1.0),
658 (currlower != nextlower ? 1.0 : 0.0),
659 (currlower ? "" : "~"), SCIPvarGetName(currvar),
660 (nextlower ? "~" : ""), SCIPvarGetName(vars[getVarIndex(dfsstack[j+1])]),
661 indexGetBoundString(dfsstack[j+1]), SCIPvarGetName(currvar));
662#endif
663 }
664 /* stacknextedge[j] > 0 --> the last outgoing edge traversed during dfs starting from node dfsstack[j] was given
665 * by an implication or vbound. Implications are looked at first, so if stacknextedge[j] <= ntmpimpls, it comes
666 * from an implication
667 */
668 else if( stacknextedge[j] <= ntmpimpls )
669 {
670#ifndef NDEBUG
671 SCIP_VAR** implvars = SCIPvarGetImplVars(currvar, currlower);
672#endif
673 SCIP_BOUNDTYPE* impltypes = SCIPvarGetImplTypes(currvar, currlower);
674 SCIP_Real* implbounds = SCIPvarGetImplBounds(currvar, currlower);
675 SCIP_VAR* nextvar = vars[getVarIndex(dfsstack[j+1])];
676 SCIP_Real newconstant;
677 SCIP_Real newcoef;
678
679 k = stacknextedge[j] - 1;
680
681 assert(dfsstack[j+1] == (impltypes[k] == SCIP_BOUNDTYPE_LOWER ?
682 varGetLbIndex(propdata, implvars[k]) : varGetUbIndex(propdata, implvars[k])));
683
684 if( impltypes[k] == SCIP_BOUNDTYPE_LOWER )
685 {
686 newcoef = implbounds[k] - SCIPvarGetLbLocal(nextvar);
687
688 if( currlower )
689 {
690 newconstant = SCIPvarGetLbLocal(nextvar);
691 }
692 else
693 {
694 newconstant = implbounds[k];
695 newcoef *= -1.0;
696 }
697 }
698 else
699 {
700 assert(impltypes[k] == SCIP_BOUNDTYPE_UPPER);
701
702 newcoef = SCIPvarGetUbLocal(nextvar) - implbounds[k];
703
704 if( currlower )
705 {
706 newconstant = SCIPvarGetUbLocal(nextvar);
707 newcoef *= -1.0;
708 }
709 else
710 {
711 newconstant = implbounds[k];
712 }
713 }
714
715 coef = coef * newcoef;
716 constant = constant * newcoef + newconstant;
717
718 SCIPdebugMsg(scip, "%s(%s) -- (*%g + %g) --> %s(%s)\n",
719 indexGetBoundString(dfsstack[j]), SCIPvarGetName(vars[getVarIndex(dfsstack[j])]),
720 newcoef, newconstant,
721 indexGetBoundString(dfsstack[j+1]), SCIPvarGetName(vars[getVarIndex(dfsstack[j+1])]));
722 }
723 /* the edge was given by a variable bound relation */
724 else
725 {
726 assert(stacknextedge[j] > ntmpimpls);
727
728 k = stacknextedge[j] - ntmpimpls - 1;
729 assert(k < propdata->nvbounds[dfsstack[j]]);
730 assert(propdata->vboundboundedidx[dfsstack[j]][k] == dfsstack[j+1]);
731
732 SCIPdebugMsg(scip, "%s(%s) -- (*%g + %g) --> %s(%s)\n",
733 indexGetBoundString(dfsstack[j]), SCIPvarGetName(vars[getVarIndex(dfsstack[j])]),
734 propdata->vboundcoefs[dfsstack[j]][k], propdata->vboundconstants[dfsstack[j]][k],
735 indexGetBoundString(dfsstack[j+1]), SCIPvarGetName(vars[getVarIndex(dfsstack[j+1])]));
736
737 coef = coef * propdata->vboundcoefs[dfsstack[j]][k];
738 constant = constant * propdata->vboundcoefs[dfsstack[j]][k] + propdata->vboundconstants[dfsstack[j]][k];
739 }
740 }
741
742 SCIPdebugMsg(scip, "==> %s(%s) -- (*%g + %g) --> %s(%s)\n",
743 indexGetBoundString(startidx), SCIPvarGetName(vars[getVarIndex(startidx)]),
744 coef, constant,
745 indexGetBoundString(cycleidx), SCIPvarGetName(vars[getVarIndex(cycleidx)]));
746
747 islower = isIndexLowerbound(cycleidx);
748
749 /* we have a relation x <=/>= coef * x + constant now
750 * (the relation depends on islower, i.e., whether the last node in the cycle is a lower or upper bound)
751 * case 1) coef is 1.0 --> x cancels out and we have a statement 0 <=/>= constant.
752 * if we have a >= relation and constant is positive, we have a contradiction 0 >= constant
753 * if we have a <= relation and constant is negative, we have a contradiction 0 <= constant
754 * case 2) coef != 1.0 --> we have a relation x - coef * x <=/>= constant
755 * <=> (1 - coef) * x <=/>= constant
756 * if coef < 1.0 this gives us x >= constant / (1 - coef) (if islower=TRUE)
757 * or x <= constant / (1 - coef) (if islower=FALSE)
758 * if coef > 1.0, the relation signs need to be switched.
759 */
760 if( SCIPisEQ(scip, coef, 1.0) )
761 {
762 if( islower && SCIPisFeasPositive(scip, constant) )
763 {
764 SCIPdebugMsg(scip, "-> infeasible aggregated variable bound relation 0 >= %g\n", constant);
765 *infeasible = TRUE;
766 }
767 else if( !islower && SCIPisFeasNegative(scip, constant) )
768 {
769 SCIPdebugMsg(scip, "-> infeasible aggregated variable bound relation 0 <= %g\n", constant);
770 *infeasible = TRUE;
771 }
772 }
773 else
774 {
775 SCIP_Bool tightened;
776
777 newbound = constant / (1.0 - coef);
778
779 if( SCIPisGT(scip, coef, 1.0) )
780 islower = !islower;
781
782 if( islower )
783 {
784 SCIPdebugMsg(scip, "-> found new lower bound: <%s>[%g,%g] >= %g\n", SCIPvarGetName(vars[getVarIndex(cycleidx)]),
785 SCIPvarGetLbLocal(vars[getVarIndex(cycleidx)]), SCIPvarGetUbLocal(vars[getVarIndex(cycleidx)]), newbound);
786 SCIP_CALL( SCIPtightenVarLb(scip, vars[getVarIndex(cycleidx)], newbound, FALSE, infeasible, &tightened) );
787 }
788 else
789 {
790 SCIPdebugMsg(scip, "-> found new upper bound: <%s>[%g,%g] <= %g\n", SCIPvarGetName(vars[getVarIndex(cycleidx)]),
791 SCIPvarGetLbLocal(vars[getVarIndex(cycleidx)]), SCIPvarGetUbLocal(vars[getVarIndex(cycleidx)]), newbound);
792 SCIP_CALL( SCIPtightenVarUb(scip, vars[getVarIndex(cycleidx)], newbound, FALSE, infeasible, &tightened) );
793 }
794
795 if( tightened )
796 SCIPdebugMsg(scip, "---> applied new bound\n");
797 }
798
799 return SCIP_OKAY;
800}
801
802#define VISITED 1
803#define ACTIVE 2
804/** performs depth-first-search in the implicitly given directed graph from the given start index */
805static
807 SCIP* scip, /**< SCIP data structure */
808 SCIP_PROPDATA* propdata, /**< propagator data */
809 int startnode, /**< node to start the depth-first-search */
810 int* visited, /**< array to store for each node, whether it was already visited */
811 int* dfsstack, /**< array of size number of nodes to store the stack;
812 * only needed for performance reasons */
813 int* stacknextedge, /**< array of size number of nodes to store the next edge to be visited in
814 * dfs for all nodes on the stack/in the current path; only needed for
815 * performance reasons */
816 int* dfsnodes, /**< array of nodes that can be reached starting at startnode, in reverse
817 * dfs order */
818 int* ndfsnodes, /**< pointer to store number of nodes that can be reached starting at
819 * startnode */
820 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
821 )
822{
823 SCIP_VAR** vars;
824 SCIP_VAR* startvar;
825 SCIP_Bool lower;
826 int stacksize;
827 int curridx;
828 int nimpls;
829 int idx;
830 /* for cycle detection, we need to mark currently active nodes, otherwise we just mark them as visited */
831 int visitedflag = (propdata->detectcycles ? ACTIVE : VISITED);
832
833 assert(startnode >= 0);
834 assert(startnode < propdata->nbounds);
835 assert(visited != NULL);
836 assert(visited[startnode] == 0);
837 assert(dfsstack != NULL);
838 assert(dfsnodes != NULL);
839 assert(ndfsnodes != NULL);
840 assert(infeasible != NULL);
841
842 *infeasible = FALSE;
843
844 vars = propdata->vars;
845
846 /* put start node on the stack */
847 dfsstack[0] = startnode;
848 stacknextedge[0] = 0;
849 stacksize = 1;
850 idx = -1;
851
852 /* we run until no more bounds indices are on the stack, i.e. all changed bounds were propagated */
853 while( stacksize > 0 )
854 {
855 /* get next node from stack */
856 curridx = dfsstack[stacksize - 1];
857
858 /* mark current node as visited */
859 assert((visited[curridx] != 0) == (stacknextedge[stacksize - 1] != 0));
860 visited[curridx] = visitedflag;
861
862 startvar = vars[getVarIndex(curridx)];
863 lower = isIndexLowerbound(curridx);
864
865 /* if the variable was fixed in the meantime, it is a loose end in the variable bound graph */
866 if( SCIPisFeasGE(scip, SCIPvarGetLbGlobal(startvar), SCIPvarGetUbGlobal(startvar)) )
867 goto REMOVE;
868
869 nimpls = 0;
870
871 if( propdata->sortcliques && propdata->usecliques && stacknextedge[stacksize - 1] == 0 )
872 stacknextedge[stacksize - 1] = -1;
873
874 /* stacknextedge is negative, if the last visited edge from the current node belongs to a clique;
875 * the index of the clique in the variable's clique list equals abs(stacknextedge) - 1
876 */
877 if( propdata->sortcliques && propdata->usecliques && stacknextedge[stacksize - 1] < 0 )
878 {
879 SCIP_CLIQUE** cliques;
880 int ncliques;
881 int j;
882 int i;
883 SCIP_Bool found;
884
885 ncliques = SCIPvarGetNCliques(startvar, lower);
886 cliques = SCIPvarGetCliques(startvar, lower);
887 found = FALSE;
888
889 assert(stacknextedge[stacksize - 1] == -1 || -stacknextedge[stacksize - 1] - 1 <= ncliques);
890
891 /* iterate over all not yet handled cliques and search for an unvisited node */
892 for( j = -stacknextedge[stacksize - 1] - 1; j < ncliques; ++j )
893 {
894 SCIP_VAR** cliquevars;
895 SCIP_Bool* cliquevals;
896 int ncliquevars;
897
898 cliquevars = SCIPcliqueGetVars(cliques[j]);
899 cliquevals = SCIPcliqueGetValues(cliques[j]);
900 ncliquevars = SCIPcliqueGetNVars(cliques[j]);
901
902 for( i = 0; i < ncliquevars; ++i )
903 {
904 if( cliquevars[i] == startvar )
905 continue;
906
907 if( cliquevals[i] )
908 idx = varGetUbIndex(propdata, cliquevars[i]);
909 else
910 idx = varGetLbIndex(propdata, cliquevars[i]);
911
912 /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
913 * bound graph and try to extract valid bound changes from it or detect infeasibility
914 */
915 if( idx >= 0 && (visited[idx] == ACTIVE || visited[getOtherBoundIndex(idx)] == ACTIVE)
916 && !SCIPisFeasGE(scip, SCIPvarGetLbGlobal(cliquevars[i]), SCIPvarGetUbGlobal(cliquevars[i])) )
917 {
918 SCIPdebugMsg(scip, "found cycle\n");
919
920 dfsstack[stacksize] = idx;
921 stacknextedge[stacksize - 1] = -j - 2;
922
923 SCIP_CALL( extractCycle(scip, propdata, dfsstack, stacknextedge, stacksize + 1,
924 visited[idx] == ACTIVE, infeasible) );
925
926 if( *infeasible )
927 break;
928 }
929
930 /* break when the first unvisited node is reached */
931 if( idx >= 0 && !visited[idx] )
932 {
933 found = TRUE;
934 break;
935 }
936 }
937 if( found )
938 break;
939 }
940
941 /* we stopped because we found an unhandled node and not because we reached the end of the list */
942 if( found )
943 {
944 assert(idx >= 0);
945 assert(!visited[idx]);
946 assert(j < ncliques);
947
948 SCIPdebugMsg(scip, "clique: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
950
951 /* put the adjacent node onto the stack */
952 dfsstack[stacksize] = idx;
953 stacknextedge[stacksize] = 0;
954 stacknextedge[stacksize - 1] = -j - 2;
955 stacksize++;
956 assert(stacksize <= propdata->nbounds);
957
958 /* restart while loop, get next index from stack */
959 continue;
960 }
961 else
962 {
963 /* we did not find an edge to an unhandled node given by a clique */
964 stacknextedge[stacksize - 1] = 0;
965 }
966 }
967 assert(stacknextedge[stacksize - 1] >= 0);
968
969 /* go over edges given by implications */
970 if( propdata->useimplics )
971 {
972 nimpls = SCIPvarGetNImpls(startvar, lower);
973
974 if( stacknextedge[stacksize - 1] < nimpls )
975 {
976 SCIP_VAR** implvars;
977 SCIP_BOUNDTYPE* impltypes;
978 int* implids;
979 int i;
980
981 implvars = SCIPvarGetImplVars(startvar, lower);
982 impltypes = SCIPvarGetImplTypes(startvar, lower);
983 implids = SCIPvarGetImplIds(startvar, lower);
984
985 for( i = stacknextedge[stacksize - 1]; i < nimpls; ++i )
986 {
987 /* it might happen that implications point to inactive variables (normally, those are removed when a
988 * variable becomes inactive, but in some cases, it cannot be done), we have to ignore these variables
989 */
990 if( !SCIPvarIsActive(implvars[i]) )
991 continue;
992
993 /* implication is just a shortcut, so we dont regard it now, because will later go the long way, anyway;
994 * however, if we do regard cliques for the topological order, we use them to get a better order
995 */
996 if( propdata->usecliques && !propdata->sortcliques && implids[i] < 0 )
997 continue;
998
999 idx = (impltypes[i] == SCIP_BOUNDTYPE_LOWER ?
1000 varGetLbIndex(propdata, implvars[i]) : varGetUbIndex(propdata, implvars[i]));
1001
1002 /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
1003 * bound graph and try to extract valid bound changes from it or detect infeasibility
1004 */
1005 if( idx >= 0 && (visited[idx] == ACTIVE || visited[getOtherBoundIndex(idx)] == ACTIVE)
1006 && !SCIPisFeasGE(scip, SCIPvarGetLbGlobal(implvars[i]), SCIPvarGetUbGlobal(implvars[i])) )
1007 {
1008 SCIPdebugMsg(scip, "found cycle\n");
1009
1010 dfsstack[stacksize] = idx;
1011 stacknextedge[stacksize - 1] = i + 1;
1012
1013 SCIP_CALL( extractCycle(scip, propdata, dfsstack, stacknextedge, stacksize + 1,
1014 visited[idx] == ACTIVE, infeasible) );
1015
1016 if( *infeasible )
1017 break;
1018 }
1019
1020 /* break when the first unvisited node is reached */
1021 if( idx >= 0 && !visited[idx] )
1022 break;
1023 }
1024
1025 /* we stopped because we found an unhandled node and not because we reached the end of the list */
1026 if( i < nimpls )
1027 {
1028 assert(!visited[idx]);
1029
1030 SCIPdebugMsg(scip, "impl: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
1032
1033 /* put the adjacent node onto the stack */
1034 dfsstack[stacksize] = idx;
1035 stacknextedge[stacksize] = 0;
1036 stacknextedge[stacksize - 1] = i + 1;
1037 stacksize++;
1038 assert(stacksize <= propdata->nbounds);
1039
1040 /* restart while loop, get next index from stack */
1041 continue;
1042 }
1043 else
1044 {
1045 stacknextedge[stacksize - 1] = nimpls;
1046 }
1047 }
1048 }
1049 assert(stacknextedge[stacksize - 1] >= nimpls);
1050
1051 /* go over edges corresponding to varbounds */
1052 if( propdata->usevbounds )
1053 {
1054 int nvbounds;
1055 int* vboundidx;
1056 int i;
1057
1058 nvbounds = propdata->nvbounds[curridx];
1059 vboundidx = propdata->vboundboundedidx[curridx];
1060
1061 /* iterate over all vbounds for the given bound */
1062 for( i = stacknextedge[stacksize - 1] - nimpls; i < nvbounds; ++i )
1063 {
1064 idx = vboundidx[i];
1065 assert(idx >= 0);
1066
1067 if( (visited[idx] == ACTIVE || visited[getOtherBoundIndex(idx)] == ACTIVE)
1069 {
1070 SCIPdebugMsg(scip, "found cycle\n");
1071
1072 dfsstack[stacksize] = idx;
1073 stacknextedge[stacksize - 1] = nimpls + i + 1;
1074
1075 /* we reached a variable that was already visited on the active path, so we have a cycle in the variable
1076 * bound graph and try to extract valid bound changes from it or detect infeasibility
1077 */
1078 SCIP_CALL( extractCycle(scip, propdata, dfsstack, stacknextedge, stacksize + 1,
1079 visited[idx] == ACTIVE, infeasible) );
1080
1081 if( *infeasible )
1082 break;
1083 }
1084
1085 /* break when the first unvisited node is reached */
1086 if( !visited[idx] )
1087 break;
1088 }
1089
1090 if( *infeasible )
1091 break;
1092
1093 /* we stopped because we found an unhandled node and not because we reached the end of the list */
1094 if( i < nvbounds )
1095 {
1096 assert(!visited[idx]);
1097
1098 SCIPdebugMsg(scip, "vbound: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
1100
1101 /* put the adjacent node onto the stack */
1102 dfsstack[stacksize] = idx;
1103 stacknextedge[stacksize] = 0;
1104 stacknextedge[stacksize - 1] = nimpls + i + 1;
1105 stacksize++;
1106 assert(stacksize <= propdata->nbounds);
1107
1108 /* restart while loop, get next index from stack */
1109 continue;
1110 }
1111 }
1112 REMOVE:
1113 /* the current node was completely handled, remove it from stack */
1114 stacksize--;
1115
1116 SCIPdebugMsg(scip, "topoorder[%d] = %s(%s)\n", *ndfsnodes, getBoundString(lower), SCIPvarGetName(startvar));
1117
1118 /* store node in the sorted nodes array */
1119 dfsnodes[(*ndfsnodes)] = curridx;
1120 assert(visited[curridx] == visitedflag);
1121 visited[curridx] = VISITED;
1122 (*ndfsnodes)++;
1123 }
1124
1125 return SCIP_OKAY;
1126}
1127
1128/** sort the bounds of variables topologically */
1129static
1131 SCIP* scip, /**< SCIP data structure */
1132 SCIP_PROPDATA* propdata, /**< propagator data */
1133 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
1134 )
1135{
1136 int* dfsstack;
1137 int* stacknextedge;
1138 int* visited;
1139 int nsortednodes;
1140 int nbounds;
1141 int i;
1142
1143 assert(scip != NULL);
1144 assert(propdata != NULL);
1145 assert(infeasible != NULL);
1146
1147 nbounds = propdata->nbounds;
1148
1149 SCIP_CALL( SCIPallocBufferArray(scip, &dfsstack, nbounds) );
1150 SCIP_CALL( SCIPallocBufferArray(scip, &stacknextedge, nbounds) );
1151 SCIP_CALL( SCIPallocClearBufferArray(scip, &visited, nbounds) );
1152
1153 nsortednodes = 0;
1154
1155 /* while there are unvisited nodes, run dfs starting from one of these nodes; the dfs orders are stored in the
1156 * topoorder array, later dfs calls are just appended after the stacks of previous dfs calls, which gives us a
1157 * reverse topological order
1158 */
1159 for( i = 0; i < nbounds && !(*infeasible); ++i )
1160 {
1161 if( !visited[i] )
1162 {
1163 SCIP_CALL( dfs(scip, propdata, i, visited, dfsstack, stacknextedge, propdata->topoorder, &nsortednodes, infeasible) );
1164 }
1165 }
1166 assert((nsortednodes == nbounds) || (*infeasible));
1167
1168 SCIPfreeBufferArray(scip, &visited);
1169 SCIPfreeBufferArray(scip, &stacknextedge);
1170 SCIPfreeBufferArray(scip, &dfsstack);
1171
1172 return SCIP_OKAY;
1173}
1174
1175/** initializes the internal data for the variable bounds propagator */
1176static
1178 SCIP* scip, /**< SCIP data structure */
1179 SCIP_PROP* prop, /**< vbounds propagator */
1180 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
1181 )
1182{
1183 SCIP_PROPDATA* propdata;
1184 SCIP_VAR** vars;
1185 int nvars;
1186 int nbounds;
1187 int startidx;
1188 int v;
1189 int n;
1190
1191 assert(scip != NULL);
1192 assert(prop != NULL);
1193 assert(infeasible != NULL);
1194
1195 /* get propagator data */
1196 propdata = SCIPpropGetData(prop);
1197 assert(propdata != NULL);
1198 assert(!propdata->initialized);
1199
1200 SCIPdebugMsg(scip, "initialize vbounds propagator for problem <%s>\n", SCIPgetProbName(scip));
1201
1202 vars = SCIPgetVars(scip);
1203 nvars = SCIPgetNVars(scip);
1204 nbounds = 2 * nvars;
1205
1206 *infeasible = FALSE;
1207
1208 /* store size of the bounds of variables array */
1209 propdata->nbounds = nbounds;
1210
1211 if( nbounds == 0 )
1212 return SCIP_OKAY;
1213
1214 propdata->initialized = TRUE;
1215
1216 /* prepare priority queue structure */
1217 SCIP_CALL( SCIPpqueueCreate(&propdata->propqueue, nvars, 2.0, compVarboundIndices, NULL) );
1218 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->inqueue, nbounds) );
1219 BMSclearMemoryArray(propdata->inqueue, nbounds);
1220
1221 /* we need to copy the variable since this array is the basis of the propagator and the corresponding variable array
1222 * within SCIP might change during the search
1223 */
1224 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &propdata->vars, vars, nvars) );
1225 SCIP_CALL( SCIPhashmapCreate(&propdata->varhashmap, SCIPblkmem(scip), nvars) );
1226
1227 for( v = 0; v < nvars; ++v )
1228 {
1229 SCIP_CALL( SCIPhashmapInsertInt(propdata->varhashmap, propdata->vars[v], v) );
1230 }
1231
1232 /* allocate memory for the arrays of the propdata */
1233 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->topoorder, nbounds) );
1234 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundboundedidx, nbounds) );
1235 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundcoefs, nbounds) );
1236 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundconstants, nbounds) );
1237 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->nvbounds, nbounds) );
1238 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->vboundsize, nbounds) );
1239 BMSclearMemoryArray(propdata->vboundboundedidx, nbounds);
1240 BMSclearMemoryArray(propdata->vboundcoefs, nbounds);
1241 BMSclearMemoryArray(propdata->vboundconstants, nbounds);
1242 BMSclearMemoryArray(propdata->nvbounds, nbounds);
1243 BMSclearMemoryArray(propdata->vboundsize, nbounds);
1244
1245 for( v = 0; v < nbounds; ++v )
1246 {
1247 propdata->topoorder[v] = v;
1248 propdata->vboundboundedidx[v] = NULL;
1249 propdata->vboundcoefs[v] = NULL;
1250 propdata->vboundconstants[v] = NULL;
1251 propdata->nvbounds[v] = 0;
1252 propdata->vboundsize[v] = 0;
1253 }
1254
1255 /* collect information about varbounds */
1256 for( v = 0; v < nbounds; ++v )
1257 {
1258 SCIP_VAR** vbvars;
1259 SCIP_VAR* var;
1260 SCIP_Real* coefs;
1261 SCIP_Real* constants;
1262 SCIP_Bool lower;
1263 int nvbvars;
1264
1265 var = vars[getVarIndex(v)];
1266 lower = isIndexLowerbound(v);
1267
1268 /* get the variable bound informations for the current variable */
1269 if( lower )
1270 {
1271 vbvars = SCIPvarGetVlbVars(var);
1272 coefs = SCIPvarGetVlbCoefs(var);
1273 constants = SCIPvarGetVlbConstants(var);
1274 nvbvars = SCIPvarGetNVlbs(var);
1275 }
1276 else
1277 {
1278 vbvars = SCIPvarGetVubVars(var);
1279 coefs = SCIPvarGetVubCoefs(var);
1280 constants = SCIPvarGetVubConstants(var);
1281 nvbvars = SCIPvarGetNVubs(var);
1282 }
1283
1284 /* loop over all variable bounds; a variable lower bound has the form: x >= b*y + d,
1285 * a variable upper bound the form x <= b*y + d */
1286 for( n = 0; n < nvbvars; ++n )
1287 {
1288 SCIP_VAR* vbvar;
1289 SCIP_Real coef;
1290 SCIP_Real constant;
1291
1292 vbvar = vbvars[n];
1293 coef = coefs[n];
1294 constant = constants[n];
1295 assert(vbvar != NULL);
1296
1297 /* transform variable bound variable to an active variable, if possible */
1298 SCIP_CALL( SCIPgetProbvarSum(scip, &vbvar, &coef, &constant) );
1299 assert(vbvar != NULL);
1300
1301 if( !SCIPvarIsActive(vbvar) )
1302 continue;
1303
1304 /* if the coefficient is positive, the type of bound is the same for the bounded and the bounding variable */
1305 if( SCIPisPositive(scip, coef) )
1306 startidx = (lower ? varGetLbIndex(propdata, vbvar) : varGetUbIndex(propdata, vbvar));
1307 else
1308 startidx = (lower ? varGetUbIndex(propdata, vbvar) : varGetLbIndex(propdata, vbvar));
1309 assert(startidx >= 0);
1310
1311 /* If the vbvar is binary, the vbound should be stored as an implication already.
1312 * However, it might happen that vbvar was integer when the variable bound was added, but was converted
1313 * to a binary variable later during presolving when its upper bound was changed to 1. In this case,
1314 * the implication might not have been created.
1315 */
1317 && SCIPvarHasImplic(vbvar, isIndexLowerbound(startidx), var, getBoundtype(v)) )
1318 {
1319 SCIPdebugMsg(scip, "varbound <%s> %s %g * <%s> + %g not added to propagator data due to reverse implication\n",
1320 SCIPvarGetName(var), (lower ? ">=" : "<="), coef,
1321 SCIPvarGetName(vbvar), constant);
1322 }
1323 else
1324 {
1325 SCIP_CALL( addVbound(scip, propdata, startidx, v, coef, constant) );
1326
1327 SCIPdebugMsg(scip, "varbound <%s> %s %g * <%s> + %g added to propagator data\n",
1328 SCIPvarGetName(var), (lower ? ">=" : "<="), coef,
1329 SCIPvarGetName(vbvar), constant);
1330 }
1331 }
1332 }
1333
1334 /* sort the bounds topologically */
1335 if( propdata->dotoposort )
1336 {
1337 SCIP_CALL( topologicalSort(scip, propdata, infeasible) );
1338 }
1339
1340 /* catch variable events */
1341 SCIP_CALL( catchEvents(scip, propdata) );
1342
1343 return SCIP_OKAY;
1344}
1345
1346/** resolves a propagation by adding the variable which implied that bound change */
1347static
1349 SCIP* scip, /**< SCIP data structure */
1350 SCIP_PROPDATA* propdata, /**< propagator data */
1351 SCIP_VAR* var, /**< variable to be reported */
1352 SCIP_BOUNDTYPE boundtype, /**< bound to be reported */
1353 SCIP_BDCHGIDX* bdchgidx /**< the index of the bound change, representing the point of time where
1354 * the change took place, or NULL for the current local bounds */
1355 )
1356{
1357 assert(propdata != NULL);
1358 assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
1359
1360 SCIPdebugMsg(scip, " -> add %s bound of variable <%s> as reason\n",
1361 getBoundtypeString(boundtype), SCIPvarGetName(var));
1362
1363 switch( boundtype )
1364 {
1366 SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
1367 break;
1369 SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
1370 break;
1371 default:
1372 SCIPerrorMessage("invalid bound type <%d>\n", boundtype);
1373 SCIPABORT();
1374 return SCIP_INVALIDDATA; /*lint !e527*/
1375 }
1376
1377 return SCIP_OKAY;
1378}
1379
1380/** relaxes bound of give variable as long as the given inference bound still leads to a cutoff and add that bound
1381 * change to the conflict set
1382 */
1383static
1385 SCIP* scip, /**< SCIP data structure */
1386 SCIP_VAR* var, /**< variable for which the upper bound should be relaxed */
1387 SCIP_BOUNDTYPE boundtype, /**< boundtype used for the variable bound variable */
1388 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where
1389 * the change took place, or NULL for the current local bounds */
1390 SCIP_Real relaxedbd /**< relaxed bound */
1391 )
1392{
1393 if( boundtype == SCIP_BOUNDTYPE_LOWER )
1394 {
1395 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, var, bdchgidx, relaxedbd) );
1396 }
1397 else
1398 {
1399 assert(boundtype == SCIP_BOUNDTYPE_UPPER);
1400 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, var, bdchgidx, relaxedbd) );
1401 }
1402
1403 return SCIP_OKAY;
1404}
1405
1406/** compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1407static
1409 SCIP* scip, /**< SCIP data structure */
1410 SCIP_VAR* var, /**< variable which was propagated */
1411 SCIP_Real inferlb, /**< inference lower bound */
1412 SCIP_Real coef, /**< inference variable bound coefficient used */
1413 SCIP_Real constant /**< inference variable bound constant used */
1414 )
1415{
1416 SCIP_Real relaxedbd;
1417
1418 if( SCIPvarIsIntegral(var) && inferlb < SCIPgetHugeValue(scip) * SCIPfeastol(scip) )
1419 relaxedbd = (inferlb - 1.0 + 2*SCIPfeastol(scip) - constant) / coef;
1420 else
1421 relaxedbd = (inferlb - constant) / coef;
1422
1423 /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1424 assert(SCIPisEQ(scip, inferlb, SCIPadjustedVarLb(scip, var, relaxedbd * coef + constant)));
1425
1426 if( coef > 0.0 )
1427 relaxedbd += SCIPfeastol(scip);
1428 else
1429 relaxedbd -= SCIPfeastol(scip);
1430
1431 return relaxedbd;
1432}
1433
1434/** analyzes an infeasibility which was reached by updating the lower bound of the inference variable above its upper
1435 * bound
1436 */
1437static
1439 SCIP* scip, /**< SCIP data structure */
1440 SCIP_PROPDATA* propdata, /**< propagator data */
1441 SCIP_VAR* infervar, /**< variable which led to a cutoff */
1442 SCIP_Real inferlb, /**< lower bound which led to infeasibility */
1443 SCIP_VAR* vbdvar, /**< variable which is the reason for the lower bound change */
1444 SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the lower bound change */
1445 SCIP_Real coef, /**< inference variable bound coefficient used */
1446 SCIP_Real constant, /**< inference variable bound constant used */
1447 SCIP_Bool canwide /**< can bound widening be used (for vbounds) or not
1448 * (for implications or cliques) */
1449 )
1450{
1451 assert(scip != NULL);
1452 assert(propdata != NULL);
1453 assert(infervar != NULL);
1454 assert(SCIPisEQ(scip, SCIPvarGetUbLocal(infervar), SCIPgetVarUbAtIndex(scip, infervar, NULL, FALSE)));
1455 assert(SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, infervar, NULL, TRUE), SCIPgetVarUbAtIndex(scip, infervar, NULL, FALSE)));
1456 assert(SCIPisGT(scip, inferlb, SCIPvarGetUbLocal(infervar)));
1458
1459 /* check if conflict analysis is applicable */
1461 return SCIP_OKAY;
1462
1463 if( canwide && propdata->usebdwidening )
1464 {
1465 SCIP_Real relaxedbd;
1466 SCIP_Real relaxedub;
1467
1468 SCIPdebugMsg(scip, "try to create conflict using bound widening order: inference variable, variable bound variable\n");
1469
1470 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1472
1473 /* adjust lower bound */
1474 inferlb = SCIPadjustedVarLb(scip, infervar, inferlb);
1475
1476 /* compute a relaxed upper bound which would be sufficient to be still infeasible */
1477 if( SCIPvarIsIntegral(infervar) )
1478 relaxedub = inferlb - 1.0;
1479 else
1480 relaxedub = inferlb - 2*SCIPfeastol(scip);
1481
1482 /* try to relax inference variable upper bound such that the infeasibility is still given */
1483 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, infervar, NULL, relaxedub) );
1484
1485 /* collect the upper bound which is reported to the conflict analysis */
1486 relaxedub = SCIPgetConflictVarUb(scip, infervar);
1487
1488 /* adjust inference bound with respect to the upper bound reported to the conflict analysis */
1489 if( SCIPvarIsIntegral(infervar) )
1490 relaxedub = relaxedub + 1.0;
1491 else
1492 relaxedub = relaxedub + 2*SCIPfeastol(scip);
1493
1494 /* compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable */
1495 relaxedbd = computeRelaxedLowerbound(scip, infervar, relaxedub, coef, constant);
1496
1497 /* try to relax variable bound variable */
1498 SCIP_CALL( relaxVbdvar(scip, vbdvar, boundtype, NULL, relaxedbd) );
1499
1500 /* analyze the conflict */
1502 }
1503 else
1504 {
1505 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1507
1508 /* add upper bound of the variable for which we tried to change the lower bound */
1509 SCIP_CALL( SCIPaddConflictUb(scip, infervar, NULL) );
1510
1511 /* add (correct) bound of the variable which let to the new lower bound */
1512 SCIP_CALL( resolvePropagation(scip, propdata, vbdvar, boundtype, NULL) );
1513
1514 /* analyze the conflict */
1516 }
1517
1518 return SCIP_OKAY;
1519}
1520
1521/** compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1522static
1524 SCIP* scip, /**< SCIP data structure */
1525 SCIP_VAR* var, /**< variable which was propagated */
1526 SCIP_Real inferub, /**< inference upper bound */
1527 SCIP_Real coef, /**< inference variable bound coefficient used */
1528 SCIP_Real constant /**< inference variable bound constant used */
1529 )
1530{
1531 SCIP_Real relaxedbd;
1532
1533 if( SCIPvarIsIntegral(var) && inferub < SCIPgetHugeValue(scip) * SCIPfeastol(scip) )
1534 relaxedbd = (inferub + 1.0 - 2*SCIPfeastol(scip) - constant) / coef;
1535 else
1536 relaxedbd = (inferub - constant) / coef;
1537
1538 /* check the computed relaxed lower/upper bound is a proper reason for the inference bound which has to be explained */
1539 assert(SCIPisEQ(scip, inferub, SCIPadjustedVarUb(scip, var, relaxedbd * coef + constant)));
1540
1541 if( coef > 0.0 )
1542 relaxedbd -= SCIPfeastol(scip);
1543 else
1544 relaxedbd += SCIPfeastol(scip);
1545
1546 return relaxedbd;
1547}
1548
1549/** analyzes an infeasibility which was reached by updating the upper bound of the inference variable below its lower
1550 * bound
1551 */
1552static
1554 SCIP* scip, /**< SCIP data structure */
1555 SCIP_PROPDATA* propdata, /**< propagator data */
1556 SCIP_VAR* infervar, /**< variable which led to a cutoff */
1557 SCIP_Real inferub, /**< upper bound which led to infeasibility */
1558 SCIP_VAR* vbdvar, /**< variable which is the reason for the upper bound change */
1559 SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the upper bound change */
1560 SCIP_Real coef, /**< inference variable bound coefficient used */
1561 SCIP_Real constant, /**< inference variable bound constant used */
1562 SCIP_Bool canwide /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1563 )
1564{
1565 assert(scip != NULL);
1566 assert(propdata != NULL);
1567 assert(infervar != NULL);
1568 assert(SCIPisEQ(scip, SCIPvarGetLbLocal(infervar), SCIPgetVarLbAtIndex(scip, infervar, NULL, FALSE)));
1569 assert(SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, infervar, NULL, TRUE), SCIPgetVarLbAtIndex(scip, infervar, NULL, FALSE)));
1570 assert(SCIPisLT(scip, inferub, SCIPvarGetLbLocal(infervar)));
1572
1573 /* check if conflict analysis is applicable */
1575 return SCIP_OKAY;
1576
1577 if( canwide && propdata->usebdwidening )
1578 {
1579 SCIP_Real relaxedbd;
1580 SCIP_Real relaxedlb;
1581
1582 SCIPdebugMsg(scip, "try to create conflict using bound widening order: inference variable, variable bound variable\n");
1583
1584 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1586
1587 /* adjust upper bound */
1588 inferub = SCIPadjustedVarUb(scip, infervar, inferub);
1589
1590 /* compute a relaxed lower bound which would be sufficient to be still infeasible */
1591 if( SCIPvarIsIntegral(infervar) )
1592 relaxedlb = inferub + 1.0;
1593 else
1594 relaxedlb = inferub + 2*SCIPfeastol(scip);
1595
1596 /* try to relax inference variable lower bound such that the infeasibility is still given */
1597 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, infervar, NULL, relaxedlb) );
1598
1599 /* collect the lower bound which is reported to the conflict analysis */
1600 relaxedlb = SCIPgetConflictVarLb(scip, infervar);
1601
1602 /* adjust inference bound with respect to the upper bound reported to the conflict analysis */
1603 if( SCIPvarIsIntegral(infervar) )
1604 relaxedlb = relaxedlb - 1.0;
1605 else
1606 relaxedlb = relaxedlb - 2*SCIPfeastol(scip);
1607
1608 /* compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable */
1609 relaxedbd = computeRelaxedUpperbound(scip, infervar, relaxedlb, coef, constant);
1610
1611 /* try to relax variable bound variable */
1612 SCIP_CALL( relaxVbdvar(scip, vbdvar, boundtype, NULL, relaxedbd) );
1613
1614 /* analyze the conflict */
1616 }
1617 else
1618 {
1619 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1621
1622 /* add lower bound of the variable for which we tried to change the upper bound */
1623 SCIP_CALL( SCIPaddConflictLb(scip, infervar, NULL) );
1624
1625 /* add (correct) bound of the variable which let to the new upper bound */
1626 SCIP_CALL( resolvePropagation(scip, propdata, vbdvar, boundtype, NULL) );
1627
1628 /* analyze the conflict */
1630 }
1631
1632 return SCIP_OKAY;
1633}
1634
1635/* tries to tighten the (global) lower bound of the given variable to the given new bound */
1636static
1638 SCIP* scip, /**< SCIP data structure */
1639 SCIP_PROP* prop, /**< vbounds propagator */
1640 SCIP_PROPDATA* propdata, /**< propagator data */
1641 SCIP_VAR* var, /**< variable whose lower bound should be tightened */
1642 SCIP_Real newlb, /**< new lower bound for the variable */
1643 SCIP_Bool global, /**< is the bound globally valid? */
1644 SCIP_VAR* vbdvar, /**< variable which is the reason for the lower bound change */
1645 SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the lower bound change */
1646 SCIP_Bool force, /**< should domain changes for continuous variables be forced */
1647 SCIP_Real coef, /**< coefficient in vbound constraint causing the propagation;
1648 * or 0.0 if propagation is caused by clique or implication */
1649 SCIP_Real constant, /**< constant in vbound constraint causing the propagation;
1650 * or 0.0 if propagation is caused by clique or implication */
1651 SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1652 int* nchgbds, /**< pointer to increase, if a bound was changed */
1653 SCIP_RESULT* result /**< pointer to store the result of the propagation */
1654 )
1655{
1656 INFERINFO inferinfo;
1657 SCIP_Real lb;
1658 SCIP_Bool tightened;
1659 SCIP_Bool infeasible;
1660
1661 assert(scip != NULL);
1662 assert(prop != NULL);
1663 assert(propdata != NULL);
1664 assert(var != NULL);
1665 assert(nchgbds != NULL);
1666 assert(result != NULL);
1667
1668 lb = SCIPvarGetLbLocal(var);
1669
1670 /* check that the new upper bound is better */
1671 if( (SCIPvarIsIntegral(var) && newlb - lb > 0.5) || (force && SCIPisGT(scip, newlb, lb)) )
1672 force = TRUE;
1673 else
1674 force = FALSE;
1675
1676 /* try to tighten the lower bound */
1677 if( global )
1678 {
1679 SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newlb, force, &infeasible, &tightened) );
1680 }
1681 else
1682 {
1683 inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1684
1685 SCIP_CALL( SCIPinferVarLbProp(scip, var, newlb, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1686 }
1687
1688 if( infeasible )
1689 {
1690 /* the infeasible results comes from the fact that the new lower bound lies above the current upper bound */
1691 assert(SCIPisGT(scip, newlb, SCIPvarGetUbLocal(var)));
1692 assert(!global || SCIPisGT(scip, newlb, SCIPvarGetUbGlobal(var)));
1693
1694 SCIPdebugMsg(scip, "tightening%s lower bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1695 (global ? " global" : ""), SCIPvarGetName(var), newlb, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1696
1697 if( global )
1698 {
1699 /* cutoff the root node */
1701 }
1702 else
1703 {
1704 /* analyzes a infeasibility via conflict analysis */
1705 SCIP_CALL( analyzeConflictLowerbound(scip, propdata, var, newlb, vbdvar, boundtype, coef, constant, canwide) );
1706 }
1707 *result = SCIP_CUTOFF;
1708 }
1709 else if( tightened )
1710 {
1711 SCIPdebugMsg(scip, "tightened%s lower bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1712 (global ? " global" : ""), SCIPvarGetName(var), newlb, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1713 (*nchgbds)++;
1714 }
1715
1716 return SCIP_OKAY;
1717}
1718
1719/* tries to tighten the (global) upper bound of the given variable to the given new bound */
1720static
1722 SCIP* scip, /**< SCIP data structure */
1723 SCIP_PROP* prop, /**< vbounds propagator */
1724 SCIP_PROPDATA* propdata, /**< propagator data */
1725 SCIP_VAR* var, /**< variable whose upper bound should be tightened */
1726 SCIP_Real newub, /**< new upper bound of the variable */
1727 SCIP_Bool global, /**< is the bound globally valid? */
1728 SCIP_VAR* vbdvar, /**< variable which is the reason for the upper bound change */
1729 SCIP_BOUNDTYPE boundtype, /**< bound which is the reason for the upper bound change */
1730 SCIP_Bool force, /**< should domain changes for continuous variables be forced */
1731 SCIP_Real coef, /**< coefficient in vbound constraint causing the propagation;
1732 * or 0.0 if propagation is caused by clique or implication */
1733 SCIP_Real constant, /**< constant in vbound constraint causing the propagation;
1734 * or 0.0 if propagation is caused by clique or implication */
1735 SCIP_Bool canwide, /**< can bound widening be used (for vbounds) or not (for inplications or cliques) */
1736 int* nchgbds, /**< pointer to increase, if a bound was changed */
1737 SCIP_RESULT* result /**< pointer to store the result of the propagation */
1738 )
1739{
1740 INFERINFO inferinfo;
1741 SCIP_Real ub;
1742 SCIP_Bool tightened;
1743 SCIP_Bool infeasible;
1744
1745 assert(scip != NULL);
1746 assert(prop != NULL);
1747 assert(propdata != NULL);
1748 assert(var != NULL);
1749 assert(nchgbds != NULL);
1750 assert(result != NULL);
1751
1752 ub = SCIPvarGetUbLocal(var);
1753
1754 /* check that the new upper bound is better */
1755 if( (SCIPvarIsIntegral(var) && ub - newub > 0.5) || (force && SCIPisLT(scip, newub, ub)) )
1756 force = TRUE;
1757 else
1758 force = FALSE;
1759
1760 /* try to tighten the upper bound */
1761 if( global )
1762 {
1763 SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newub, force, &infeasible, &tightened) );
1764 }
1765 else
1766 {
1767 inferinfo = getInferInfo(boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, vbdvar) : varGetUbIndex(propdata, vbdvar), boundtype);
1768
1769 SCIP_CALL( SCIPinferVarUbProp(scip, var, newub, prop, inferInfoToInt(inferinfo), force, &infeasible, &tightened) );
1770 }
1771
1772 if( infeasible )
1773 {
1774 /* the infeasible results comes from the fact that the new upper bound lies below the current lower bound */
1775 assert(SCIPisLT(scip, newub, SCIPvarGetLbLocal(var)));
1776 assert(!global || SCIPisLT(scip, newub, SCIPvarGetLbGlobal(var)));
1777
1778 SCIPdebugMsg(scip, "tightening%s upper bound of variable <%s> to %g due the %s bound of variable <%s> led to infeasibility\n",
1779 (global ? " global" : ""), SCIPvarGetName(var), newub, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1780
1781 if( global )
1782 {
1783 /* cutoff the root node */
1785 }
1786 else
1787 {
1788 /* analyzes a infeasibility via conflict analysis */
1789 SCIP_CALL( analyzeConflictUpperbound(scip, propdata, var, newub, vbdvar, boundtype, coef, constant, canwide) );
1790 }
1791 *result = SCIP_CUTOFF;
1792 }
1793 else if( tightened )
1794 {
1795 SCIPdebugMsg(scip, "tightened%s upper bound of variable <%s> to %g due the %s bound of variable <%s>\n",
1796 (global ? " global" : ""), SCIPvarGetName(var), newub, getBoundtypeString(boundtype), SCIPvarGetName(vbdvar));
1797 (*nchgbds)++;
1798 }
1799
1800 return SCIP_OKAY;
1801}
1802
1803/** performs propagation of variables lower and upper bounds, implications, and cliques */
1804static
1806 SCIP* scip, /**< SCIP data structure */
1807 SCIP_PROP* prop, /**< vbounds propagator */
1808 SCIP_Bool force, /**< should domain changes for continuous variables be forced */
1809 SCIP_RESULT* result /**< pointer to store the result of the propagation */
1810 )
1811{
1812 SCIP_PROPDATA* propdata;
1813 SCIP_VAR** vars;
1814 SCIP_VAR* startvar;
1815 SCIP_BOUNDTYPE starttype;
1816 SCIP_Real startbound;
1817 SCIP_Real globalbound;
1818 int* queuelist = NULL;
1819 int nqueuelist = 0;
1820 int startpos;
1821 int topopos;
1822 int v;
1823 int n;
1824 int nchgbds;
1825 int nbounds;
1826 SCIP_Bool lower;
1827 SCIP_Bool global;
1828
1829 assert(scip != NULL);
1830 assert(prop != NULL);
1831 assert(result != NULL);
1832
1833 (*result) = SCIP_DIDNOTRUN;
1834
1835 /* we do not run the propagator in presolving, because we want to avoid doing the expensive creation of the graph twice */
1837 return SCIP_OKAY;
1838
1839 propdata = SCIPpropGetData(prop);
1840 assert(propdata != NULL);
1841
1842 /* initialize propagator data needed for propagation, if not done yet */
1843 if( !propdata->initialized )
1844 {
1845 SCIP_Bool infeasible;
1846
1847 SCIP_CALL( initData(scip, prop, &infeasible) );
1848
1849 if( infeasible )
1850 {
1851 *result = SCIP_CUTOFF;
1852 return SCIP_OKAY;
1853 }
1854 }
1855 assert(propdata->nbounds == 0 || propdata->propqueue != NULL);
1856
1857 vars = propdata->vars;
1858 nbounds = propdata->nbounds;
1859
1860 if( nbounds == 0 )
1861 return SCIP_OKAY;
1862
1863 /* propagate all variables if we are in repropagation */
1865 {
1866 SCIP_VAR* var;
1867 int idx;
1868
1869 for( v = nbounds - 1; v >= 0; --v )
1870 {
1871 idx = propdata->topoorder[v];
1872 if( idx != -1 && !propdata->inqueue[v] )
1873 {
1874 var = vars[getVarIndex(idx)];
1875 lower = isIndexLowerbound(idx);
1876 if( !SCIPvarIsBinary(var) || (lower && SCIPvarGetLbLocal(var) > 0.5)
1877 || (!lower && SCIPvarGetUbLocal(var) < 0.5) )
1878 {
1879 SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(v + 1)) ); /*lint !e571 !e776*/
1880 propdata->inqueue[v] = TRUE;
1881 }
1882 }
1883 }
1884 }
1885
1886 /* return if no bound changes are in the priority queue (no changed bounds to handle since last propagation) */
1887 if( SCIPpqueueNElems(propdata->propqueue) == 0 )
1888 return SCIP_OKAY;
1889
1890 nchgbds = 0;
1891
1892 (*result) = SCIP_DIDNOTFIND;
1893
1894 /* allocate space for variables added to the queue - needed to clean up data */
1895 SCIP_CALL( SCIPallocBufferArray(scip, &queuelist, nbounds) );
1896
1897 SCIPdebugMsg(scip, "varbound propagator: %d elements in the propagation queue\n", SCIPpqueueNElems(propdata->propqueue));
1898
1899 /* get variable bound of highest priority from priority queue and try to deduce bound changes for other variables;
1900 * the priority queue is ordered w.r.t the topological sort of the varbound graph
1901 */
1902 while( SCIPpqueueNElems(propdata->propqueue) > 0 )
1903 {
1904 /* coverity[pointer_conversion_loses_bits] */
1905 topopos = ((int)(size_t)SCIPpqueueRemove(propdata->propqueue)) - 1;
1906 assert(propdata->inqueue[topopos]);
1907 startpos = propdata->topoorder[topopos];
1908 assert(startpos >= 0);
1909 queuelist[nqueuelist++] = topopos;
1910 assert( nqueuelist <= nbounds );
1911
1912 /* do not directly set propdata->inqueue[topopos] = FALSE: we allow only one propagation sweep through the
1913 * topologically ordered bounds; otherwise an infinite loop could occur */
1914
1915 startvar = vars[getVarIndex(startpos)];
1916 starttype = getBoundtype(startpos);
1917 lower = (starttype == SCIP_BOUNDTYPE_LOWER);
1918 startbound = ( lower ? SCIPvarGetLbLocal(startvar) : SCIPvarGetUbLocal(startvar) );
1919 globalbound = ( lower ? SCIPvarGetLbGlobal(startvar) : SCIPvarGetUbGlobal(startvar));
1920 global = SCIPisEQ(scip, startbound, globalbound);
1921
1922 SCIPdebugMsg(scip, "propagate new %s bound of %g of variable <%s>:\n",
1923 getBoundtypeString(starttype), startbound, SCIPvarGetName(startvar));
1924
1925 /* there should be neither implications nor cliques for non-binary variables */
1926 assert(SCIPvarIsBinary(startvar) || SCIPvarGetNImpls(startvar, lower) == 0);
1927 assert(SCIPvarIsBinary(startvar) || SCIPvarGetNCliques(startvar, lower) == 0);
1928
1929 if( SCIPvarIsBinary(startvar) )
1930 {
1931 /* we only propagate binary variables if the lower bound changed to 1.0 or the upper bound changed to 0.0 */
1932 if( lower != (startbound > 0.5) )
1933 continue;
1934
1935 /* propagate implications */
1936 if( propdata->useimplics )
1937 {
1938 int nimplvars;
1939
1940 /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
1941 * get all implications for this varfixing
1942 */
1943 nimplvars = SCIPvarGetNImpls(startvar, lower);
1944
1945 /* if there are implications for the varfixing, propagate them */
1946 if( nimplvars > 0 )
1947 {
1948 SCIP_VAR** implvars;
1949 SCIP_BOUNDTYPE* impltypes;
1950 SCIP_Real* implbounds;
1951 int* implids;
1952
1953 implvars = SCIPvarGetImplVars(startvar, lower);
1954 impltypes = SCIPvarGetImplTypes(startvar, lower);
1955 implbounds = SCIPvarGetImplBounds(startvar, lower);
1956 implids = SCIPvarGetImplIds(startvar, lower);
1957
1958 for( n = 0; n < nimplvars; ++n )
1959 {
1960 /* implication is just a shortcut, so we do not propagate it now,
1961 * because we will propagate the longer way, anyway
1962 */
1963 if( implids[n] < 0 )
1964 continue;
1965
1966 /* it might happen that implications point to inactive variables (normally, those are removed when a
1967 * variable becomes inactive, but in some cases, it cannot be done), we have to ignore these variables
1968 */
1969 if( !SCIPvarIsActive(implvars[n]) )
1970 continue;
1971
1972 if( impltypes[n] == SCIP_BOUNDTYPE_LOWER )
1973 {
1974 SCIP_CALL( tightenVarLb(scip, prop, propdata, implvars[n], implbounds[n], global, startvar,
1975 starttype, force, 0.0, 0.0, FALSE, &nchgbds, result) );
1976 }
1977 else
1978 {
1979 SCIP_CALL( tightenVarUb(scip, prop, propdata, implvars[n], implbounds[n], global, startvar,
1980 starttype, force, 0.0, 0.0, FALSE, &nchgbds, result) );
1981 }
1982
1983 if( *result == SCIP_CUTOFF )
1984 break;
1985 }
1986 if( *result == SCIP_CUTOFF )
1987 break;
1988 }
1989 }
1990
1991 /* propagate cliques */
1992 if( propdata->usecliques )
1993 {
1994 int ncliques;
1995
1996 /* if the lower bound of the startvar was changed, it was fixed to 1.0, otherwise it was fixed to 0.0;
1997 * get all cliques for this varfixing
1998 */
1999 ncliques = SCIPvarGetNCliques(startvar, lower);
2000
2001 /* if there are cliques for the varfixing, propagate them */
2002 if( ncliques > 0 )
2003 {
2004 SCIP_CLIQUE** cliques;
2005 int j;
2006
2007 cliques = SCIPvarGetCliques(startvar, lower);
2008
2009 for( j = 0; j < ncliques; ++j )
2010 {
2011 SCIP_VAR** cliquevars;
2012 SCIP_Bool* cliquevals;
2013 int ncliquevars;
2014
2015 cliquevars = SCIPcliqueGetVars(cliques[j]);
2016 cliquevals = SCIPcliqueGetValues(cliques[j]);
2017 ncliquevars = SCIPcliqueGetNVars(cliques[j]);
2018
2019 /* fix all variables except for the startvar to the value which is not in the clique */
2020 for( n = 0; n < ncliquevars; ++n )
2021 {
2022 if( cliquevars[n] == startvar )
2023 continue;
2024
2025 /* try to tighten the bound */
2026 if( cliquevals[n] )
2027 {
2028 /* unnegated variable is in clique, so it has to be fixed to 0.0 */
2029 SCIP_CALL( tightenVarUb(scip, prop, propdata, cliquevars[n], 0.0, global, startvar, starttype,
2030 force, 0.0, 0.0, FALSE, &nchgbds, result) );
2031 }
2032 else
2033 {
2034 /* negated variable is in clique, so it has to be fixed to 1.0 */
2035 SCIP_CALL( tightenVarLb(scip, prop, propdata, cliquevars[n], 1.0, global, startvar, starttype,
2036 force, 0.0, 0.0, FALSE, &nchgbds, result) );
2037 }
2038
2039 if( *result == SCIP_CUTOFF )
2040 break;
2041 }
2042 }
2043 if( *result == SCIP_CUTOFF )
2044 break;
2045 }
2046 }
2047 }
2048
2049 /* propagate vbounds */
2050 if( propdata->usevbounds && ! SCIPisInfinity(scip, REALABS(startbound)) )
2051 {
2052 SCIP_VAR* boundedvar;
2053 SCIP_Real newbound;
2054 SCIP_Real coef;
2055 SCIP_Real constant;
2056
2057 /* iterate over all vbounds for the given bound */
2058 for( n = 0; n < propdata->nvbounds[startpos]; ++n )
2059 {
2060 boundedvar = vars[getVarIndex(propdata->vboundboundedidx[startpos][n])];
2061 coef = propdata->vboundcoefs[startpos][n];
2062 constant = propdata->vboundconstants[startpos][n];
2063
2064 /* compute new bound */
2065 newbound = startbound * coef + constant;
2066
2067 /* try to tighten the bound */
2068 if( isIndexLowerbound(propdata->vboundboundedidx[startpos][n]) )
2069 {
2070 SCIP_CALL( tightenVarLb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
2071 coef, constant, TRUE, &nchgbds, result) );
2072 }
2073 else
2074 {
2075 SCIP_CALL( tightenVarUb(scip, prop, propdata, boundedvar, newbound, global, startvar, starttype, force,
2076 coef, constant, TRUE, &nchgbds, result) );
2077 }
2078
2079 if( *result == SCIP_CUTOFF )
2080 break;
2081 }
2082 if( *result == SCIP_CUTOFF )
2083 break;
2084 }
2085 }
2086
2087 /* clean up inqueue */
2088 for( v = 0; v < nqueuelist; ++v )
2089 {
2090 assert( 0 <= queuelist[v] && queuelist[v] < nbounds );
2091 propdata->inqueue[queuelist[v]] = FALSE;
2092 assert( SCIPpqueueFind(propdata->propqueue, (void*)(size_t) (queuelist[v] + 1)) == -1 ); /*lint !e571*//*lint !e776*/
2093 }
2094 SCIPfreeBufferArray(scip, &queuelist);
2095
2096#ifdef SCIP_DEBUG
2097 for( v = 0; v < nbounds; ++v)
2098 {
2099 if( propdata->inqueue[v] )
2100 assert( SCIPpqueueFind(propdata->propqueue, (void*)(size_t) (v + 1)) >= 0 );
2101 else
2102 assert( SCIPpqueueFind(propdata->propqueue, (void*)(size_t) (v + 1)) == -1 );
2103 }
2104#endif
2105
2106 SCIPdebugMsg(scip, "tightened %d variable bounds\n", nchgbds);
2107
2108 /* set the result depending on whether bound changes were found or not */
2109 if( *result != SCIP_CUTOFF && nchgbds > 0 )
2110 (*result) = SCIP_REDUCEDDOM;
2111
2112 return SCIP_OKAY;
2113}
2114
2115/**@name Callback methods of propagator
2116 *
2117 * @{
2118 */
2119
2120/** copy method for propagator plugins (called when SCIP copies plugins) */
2121static
2122SCIP_DECL_PROPCOPY(propCopyVbounds)
2123{ /*lint --e{715}*/
2124 assert(scip != NULL);
2125 assert(prop != NULL);
2126 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2127
2128 /* call inclusion method of propagator */
2130
2131 return SCIP_OKAY;
2132}
2133
2134/** destructor of propagator to free user data (called when SCIP is exiting) */
2135static
2136SCIP_DECL_PROPFREE(propFreeVbounds)
2137{ /*lint --e{715}*/
2138 SCIP_PROPDATA* propdata;
2139
2140 /* free propagator data */
2141 propdata = SCIPpropGetData(prop);
2142
2143 SCIPfreeBlockMemory(scip, &propdata);
2144 SCIPpropSetData(prop, NULL);
2145
2146 return SCIP_OKAY;
2147}
2148
2149/** presolving initialization method of propagator (called when presolving is about to begin) */
2150static
2151SCIP_DECL_PROPINITPRE(propInitpreVbounds)
2152{ /*lint --e{715}*/
2153 SCIP_PROPDATA* propdata;
2154
2155 propdata = SCIPpropGetData(prop);
2156 assert(propdata != NULL);
2157
2158 propdata->lastpresolncliques = 0;
2159
2160 return SCIP_OKAY;
2161}
2162
2163/** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
2164static
2165SCIP_DECL_PROPEXITSOL(propExitsolVbounds)
2166{ /*lint --e{715}*/
2167 SCIP_PROPDATA* propdata;
2168 int v;
2169
2170 propdata = SCIPpropGetData(prop);
2171 assert(propdata != NULL);
2172
2173 /* free data stored for propagation */
2174 if( propdata->initialized )
2175 {
2176 /* drop all variable events */
2177 SCIP_CALL( dropEvents(scip, propdata) );
2178
2179 /* release all variables */
2180 for( v = 0; v < propdata->nbounds; ++v )
2181 {
2182 /* free vbound data */
2183 if( propdata->vboundsize[v] > 0 )
2184 {
2185 SCIPfreeMemoryArray(scip, &propdata->vboundboundedidx[v]);
2186 SCIPfreeMemoryArray(scip, &propdata->vboundcoefs[v]);
2187 SCIPfreeMemoryArray(scip, &propdata->vboundconstants[v]);
2188 }
2189 }
2190
2191 /* free priority queue */
2192 SCIPpqueueFree(&propdata->propqueue);
2193
2194 /* free arrays */
2195 SCIPfreeBlockMemoryArray(scip, &propdata->vboundsize, propdata->nbounds);
2196 SCIPfreeBlockMemoryArray(scip, &propdata->nvbounds, propdata->nbounds);
2197 SCIPfreeBlockMemoryArray(scip, &propdata->vboundconstants, propdata->nbounds);
2198 SCIPfreeBlockMemoryArray(scip, &propdata->vboundcoefs, propdata->nbounds);
2199 SCIPfreeBlockMemoryArray(scip, &propdata->vboundboundedidx, propdata->nbounds);
2200 SCIPfreeBlockMemoryArray(scip, &propdata->inqueue, propdata->nbounds);
2201 SCIPfreeBlockMemoryArray(scip, &propdata->topoorder, propdata->nbounds);
2202
2203 /* free variable array and hashmap */
2204 SCIPhashmapFree(&propdata->varhashmap);
2205 SCIPfreeBlockMemoryArray(scip, &propdata->vars, propdata->nbounds / 2);
2206 }
2207
2208 /* reset propagation data */
2209 resetPropdata(propdata);
2210
2211 return SCIP_OKAY;
2212}
2213
2214/** performs Tarjan's algorithm for strongly connected components in the implicitly given directed implication graph
2215 * from the given start index; each variable x is represented by two nodes lb(x) = 2*idx(x) and ub(x) = 2*idx(x)+1
2216 * where lb(x) means that the lower bound of x should be changed, i.e., that x is fixed to 1, and vice versa.
2217 *
2218 * The algorithm is an iterative version of Tarjans algorithm
2219 * (see https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm)
2220 * with some additional tweaks.
2221 * Each clique x_1 + ... + x_k <= 1 is represented by k(k-1) arcs (lb(x_i),ub(x_j)), j != i.
2222 * This quadratic number can blow up the running time of Tarjan's algorithm, which is linear in the number of
2223 * nodes and arcs of the graph. However, it suffices to consider only k of these arcs during the course of the algorithm.
2224 * To this end, when we first come to a node lb(x_i) of the clique, traverse all arcs (lb(x_i),ub(x_j)) for this particular i,
2225 * and store that we entered the clique via lb(x_i). Next time we come to any node lb(x_i') of the clique, we know
2226 * that the only arc pointing to an unvisited node is (lb(x_i'),ub(x_i)), all other edges can be disregarded.
2227 * After that, we can disregard the clique for the further search.
2228 * Additionally, we try to identify infeasible fixings for binary variables. Those can be given by a path
2229 * from x=1 to x=0 (or vice versa) or if x=0 (or 1) implies both y=0 and y=1.
2230 */
2231static
2233 SCIP* scip, /**< SCIP data structure */
2234 int startnode, /**< node to start the depth-first-search */
2235 int* startindex, /**< next index to assign to a processed node */
2236 SCIP_Shortbool* nodeonstack, /**< array to store the whether a each node is on the stack */
2237 int* nodeindex, /**< array to store the dfs index for each node */
2238 int* nodelowlink, /**< array to store the lowlink for each node */
2239 SCIP_Shortbool* nodeinfeasible, /**< array to store whether the fixing of a node was detected to be infeasible */
2240 int* dfsstack, /**< array of size number of nodes to store the stack */
2241 int* predstackidx, /**< for each node on the stack: stack position of its predecessor in the Tarjan search */
2242 int* stacknextclique, /**< array of size number of nodes to store the next clique to be regarded in
2243 * the algorithm for all nodes on the stack */
2244 int* stacknextcliquevar, /**< array of size number of nodes to store the next variable in the next clique to be
2245 * regarded in the algorithm for all nodes on the stack */
2246 int* topoorder, /**< array with reverse (almost) topological ordering of the nodes */
2247 int* nordered, /**< number of ordered nodes (disconnected nodes are disregarded) */
2248 int* cliquefirstentry, /**< node from which a clique was entered for the first time; needed because when
2249 * entering the clique a second time, only the other bound corresponding to this node
2250 * remains to be processed */
2251 int* cliquecurrentexit, /**< for cliques which define an arc on the current path: target node of this arc */
2252 int* sccvars, /**< array with all nontrivial strongly connected components in the graph */
2253 int* sccstarts, /**< start indices of SCCs in sccvars array; one additional entry at the end
2254 * to give length of used part of sccvars array */
2255 int* nsccs, /**< pointer to store number of strongly connected components */
2256 int* infeasnodes, /**< sparse array with node indices of infeasible nodes */
2257 int* ninfeasnodes, /**< pointer to store the number of infeasible nodes */
2258 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
2259 )
2260{
2261 SCIP_VAR** vars;
2262 SCIP_VAR* startvar;
2263 SCIP_Bool lower;
2264 int label = *startindex;
2265 int stacksize;
2266 int currstackidx;
2267 int curridx;
2268 int idx;
2269
2270 assert(startnode >= 0);
2271 assert(startnode < 2 * (SCIPgetNVars(scip) - SCIPgetNContVars(scip)));
2272 assert(nodeindex != NULL);
2273 assert(nodeindex[startnode] == 0);
2274 assert(nodelowlink != NULL);
2275 assert(nodelowlink[startnode] == 0);
2276 assert(dfsstack != NULL);
2277 assert(stacknextclique != NULL);
2278 assert(infeasible != NULL);
2279
2280 *infeasible = FALSE;
2281
2282 vars = SCIPgetVars(scip);
2283
2284 /* put start node on the stack */
2285 dfsstack[0] = startnode;
2286 stacknextclique[0] = 0;
2287 stacknextcliquevar[0] = 0;
2288 predstackidx[0] = -1;
2289 stacksize = 1;
2290 idx = -1;
2291 currstackidx = 0;
2292#ifdef DEBUG_TARJAN
2293 SCIPdebugMsg(scip, "put %s(%s) on stack[%d]\n", indexGetBoundString(dfsstack[stacksize-1]),
2294 SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize-1])]), stacksize-1);
2295#endif
2296
2297 /* we run until no more bounds indices are on the stack, i.e., no further nodes are connected to the startnode */
2298 while( stacksize > 0 )
2299 {
2300 SCIP_CLIQUE** cliques;
2301 int ncliques;
2302 SCIP_Bool found;
2303 int clqidx = -1;
2304 int j;
2305 int i;
2306
2307 /* get next node from stack */
2308 curridx = dfsstack[currstackidx];
2309 assert(nodelowlink[curridx] <= nodeindex[curridx]);
2310
2311 startvar = vars[getVarIndex(curridx)];
2312 lower = isIndexLowerbound(curridx);
2313
2314 /* mark current node as on stack, assign index and lowlink */
2315 if( nodeindex[curridx] == 0 )
2316 {
2317 assert(!nodeonstack[curridx]);
2318 assert(stacknextclique[currstackidx] == 0);
2319 assert(stacknextcliquevar[currstackidx] == 0);
2320 nodeonstack[curridx] = 1;
2321 nodeindex[curridx] = label;
2322 nodelowlink[curridx] = label;
2323 ++label;
2324
2325#ifdef DEBUG_TARJAN
2326 {
2327 ncliques = SCIPvarGetNCliques(startvar, lower);
2328 cliques = SCIPvarGetCliques(startvar, lower);
2329
2330 SCIPdebugMsg(scip, "variable %s(%s) has %d cliques\n", indexGetBoundString(curridx), SCIPvarGetName(startvar),
2331 ncliques);
2332 for( j = 0; j < ncliques; ++j )
2333 {
2334 SCIP_VAR** cliquevars;
2335 SCIP_Bool* cliquevals;
2336 int ncliquevars;
2337
2338 clqidx = SCIPcliqueGetIndex(cliques[j]);
2339 cliquevars = SCIPcliqueGetVars(cliques[j]);
2340 cliquevals = SCIPcliqueGetValues(cliques[j]);
2341 ncliquevars = SCIPcliqueGetNVars(cliques[j]);
2342
2343 SCIPdebugMsg(scip, "clique %d [%d vars, stacksize: %d]...\n", clqidx, ncliquevars, stacksize);
2344 for( int v = 0; v < ncliquevars; ++v )
2345 SCIPdebugMsgPrint(scip, " %s<%s>", cliquevals[v] ? "" : "~", SCIPvarGetName(cliquevars[v]));
2346 SCIPdebugMsgPrint(scip, "\n");
2347 }
2348 }
2349#endif
2350 }
2351 /* we just did a backtrack and still need to investigate some outgoing edges of the node;
2352 * however, we should have investigated some of the outgoing edges before
2353 */
2354 else
2355 {
2356 assert(stacknextclique[currstackidx] > 0 || stacknextcliquevar[currstackidx] > 0);
2357 assert(nodeindex[curridx] < label);
2358 }
2359 assert(stacknextclique[currstackidx] >= 0);
2360
2361 ncliques = SCIPvarGetNCliques(startvar, lower);
2362 cliques = SCIPvarGetCliques(startvar, lower);
2363 found = FALSE;
2364
2365 /* iterate over all not yet handled cliques and search for an unvisited node */
2366 for( j = stacknextclique[currstackidx]; j < ncliques; ++j )
2367 {
2368 SCIP_VAR** cliquevars;
2369 SCIP_Bool* cliquevals;
2370 int ncliquevars;
2371
2372 clqidx = SCIPcliqueGetIndex(cliques[j]);
2373 cliquevars = SCIPcliqueGetVars(cliques[j]);
2374 cliquevals = SCIPcliqueGetValues(cliques[j]);
2375 ncliquevars = SCIPcliqueGetNVars(cliques[j]);
2376
2377 /* we did not look at this clique before from the current node, i.e., we did not backtrack now from another
2378 * node which was reached via this clique
2379 */
2380 if( stacknextcliquevar[currstackidx] == 0 )
2381 {
2382#ifdef DEBUG_TARJAN
2383 SCIPdebugMsg(scip, "clique %d [%d vars, stacksize: %d]...\n", clqidx, ncliquevars, stacksize);
2384 for( int v = 0; v < ncliquevars; ++v )
2385 SCIPdebugMsgPrint(scip, " %s<%s>", cliquevals[v] ? "" : "~", SCIPvarGetName(cliquevars[v]));
2386 SCIPdebugMsgPrint(scip, "\n");
2387#endif
2388 /* the clique was not entered before, remember that we first entered it from curridx
2389 * (add 1 to distinguish it from 0 initialization)
2390 */
2391 if( cliquefirstentry[clqidx] == 0 )
2392 {
2393 cliquefirstentry[clqidx] = curridx + 1;
2394 }
2395 else
2396 {
2397 int cliquefirstentryidx = (cliquefirstentry[clqidx] > 0 ? cliquefirstentry[clqidx] : -cliquefirstentry[clqidx]) - 1;
2398 int infeasnode = -1;
2399 assert(cliquefirstentryidx != curridx);
2400
2401 /* The node by which we entered the clique the first time is still on the stack, so there is a
2402 * way from that node to the node by which we are entering the clique right now.
2403 * Since these two assignments together violate the clique and the second assignment is implied by the first,
2404 * the first one is infeasible
2405 */
2406 if( nodeonstack[cliquefirstentryidx] && !nodeinfeasible[cliquefirstentryidx] )
2407 {
2408 SCIPdebugMsg(scip, "infeasible assignment (1): %s(%s)\n", indexGetBoundString(cliquefirstentryidx),
2409 SCIPvarGetName(vars[getVarIndex(cliquefirstentryidx)]));
2410 infeasnode = cliquefirstentryidx;
2411 }
2412 /* the first entry point of the clique was also implied by the current startnode, so this node implies
2413 * two variables in the clique and is therefore infeasible
2414 */
2415 else if( nodeindex[cliquefirstentryidx] >= *startindex && !nodeinfeasible[startnode] )
2416 {
2417 SCIPdebugMsg(scip, "infeasible assignment (2): %s(%s)\n", indexGetBoundString(startnode),
2418 SCIPvarGetName(vars[getVarIndex(startnode)]));
2419 infeasnode = startnode;
2420 }
2421
2422 /* we identified an infeasibility */
2423 if( infeasnode >= 0 )
2424 {
2425 /* both values are invalid for the variable, the whole problem is infeasible */
2426 if( nodeinfeasible[getOtherBoundIndex(infeasnode)] )
2427 {
2428 *infeasible = TRUE;
2429 return SCIP_OKAY;
2430 }
2431 infeasnodes[*ninfeasnodes] = infeasnode;
2432 nodeinfeasible[infeasnode] = TRUE;
2433 ++(*ninfeasnodes);
2434
2435 /* the last node by which the clique was exited is not the negation of the current node and still on
2436 * the stack: update the lowlink of the current node
2437 */
2438 if( cliquecurrentexit[clqidx] > 0
2439 && curridx != getOtherBoundIndex(cliquecurrentexit[clqidx] - 1)
2440 && nodeonstack[cliquecurrentexit[clqidx] - 1]
2441 && nodeindex[cliquecurrentexit[clqidx] - 1] < nodelowlink[curridx] )
2442 {
2443 nodelowlink[curridx] = nodeindex[cliquecurrentexit[clqidx] - 1];
2444 }
2445 }
2446 /* clique is entered for the second time; there is only one edge left to investigate, namely the edge to
2447 * the negation of the first entry point
2448 */
2449 else if( cliquefirstentry[clqidx] > 0 )
2450 {
2451#ifdef DEBUG_TARJAN
2452 SCIPdebugMsg(scip, "entering clique %d a second time\n", clqidx);
2453#endif
2454 idx = getOtherBoundIndex(cliquefirstentry[clqidx] - 1);
2455
2456 /* node was not investigated yet, we found the next node to process */
2457 if( nodeindex[idx] == 0 )
2458 found = TRUE;
2459 /* update lowlink if the node is on the stack */
2460 else if( nodeonstack[idx] && nodeindex[idx] < nodelowlink[curridx] )
2461 nodelowlink[curridx] = nodeindex[idx];
2462
2463 /* cliquefirstentry[clqidx] < 0 means that we entered the clique at least two times already */
2464 cliquefirstentry[clqidx] = -cliquefirstentry[clqidx];
2465 }
2466 else
2467 {
2468#ifdef DEBUG_TARJAN
2469 SCIPdebugMsg(scip, "skip clique %d: visited more than twice already!\n", clqidx);
2470#endif
2471 }
2472 stacknextcliquevar[currstackidx] = ncliquevars;
2473 }
2474 }
2475
2476 /* iterate over variables in the clique; start where we stopped last time */
2477 for( i = stacknextcliquevar[currstackidx]; i < ncliquevars; ++i )
2478 {
2479 if( cliquevars[i] == startvar )
2480 continue;
2481
2482 if( !SCIPvarIsActive(cliquevars[i]) )
2483 continue;
2484
2485 if( cliquevals[i] )
2486 idx = getUbIndex(SCIPvarGetProbindex(cliquevars[i]));
2487 else
2488 idx = getLbIndex(SCIPvarGetProbindex(cliquevars[i]));
2489 assert(idx >= 0);
2490
2491 /* break when the first unvisited node is reached */
2492 if( nodeindex[idx] == 0 )
2493 {
2494 assert(!nodeonstack[idx]);
2495 stacknextcliquevar[currstackidx] = i + 1;
2496 found = TRUE;
2497 break;
2498 }
2499 else if( nodeonstack[idx] && nodeindex[idx] < nodelowlink[curridx] )
2500 {
2501 nodelowlink[curridx] = nodeindex[idx];
2502 }
2503 }
2504 if( found )
2505 {
2506 if( stacknextcliquevar[currstackidx] < ncliquevars )
2507 stacknextclique[currstackidx] = j;
2508 else
2509 {
2510 stacknextclique[currstackidx] = j + 1;
2511 stacknextcliquevar[currstackidx] = 0;
2512 }
2513 break;
2514 }
2515 else
2516 {
2517 assert(i == ncliquevars);
2518 stacknextclique[currstackidx] = j + 1;
2519 stacknextcliquevar[currstackidx] = 0;
2520 }
2521 }
2522 assert(found || j == ncliques);
2523 assert(found || stacknextclique[currstackidx] == ncliques);
2524
2525 /* we stopped because we found an unhandled node and not because we reached the end of the list */
2526 if( found )
2527 {
2528 int otheridx = getOtherBoundIndex(idx);
2529 int infeasnode = -1;
2530
2531 assert(idx >= 0);
2532 assert(!nodeonstack[idx]);
2533 assert(j < ncliques);
2534 assert(clqidx >= 0);
2535
2536 /* the negated node corresponding to the next node is already on the stack -> the negated assignment is
2537 * infeasible
2538 */
2539 if( nodeonstack[otheridx] && !nodeinfeasible[otheridx] )
2540 {
2541 SCIPdebugMsg(scip, "infeasible assignment (3): %s(%s)\n", indexGetBoundString(otheridx),
2542 SCIPvarGetName(vars[getVarIndex(otheridx)]));
2543 infeasnode = otheridx;
2544 }
2545 /* the negated node corresponding to the next node was reached from the same startnode -> the startnode is
2546 * infeasible
2547 */
2548 else if( nodeindex[otheridx] >= *startindex && !nodeinfeasible[startnode] )
2549 {
2550 SCIPdebugMsg(scip, "infeasible assignment (4): %s(%s)\n", indexGetBoundString(startnode),
2551 SCIPvarGetName(vars[getVarIndex(startnode)]));
2552 infeasnode = startnode;
2553 }
2554 /* treat infeasible case */
2555 if( infeasnode >= 0 )
2556 {
2557 if( nodeinfeasible[getOtherBoundIndex(infeasnode)] )
2558 {
2559 *infeasible = TRUE;
2560 return SCIP_OKAY;
2561 }
2562 infeasnodes[*ninfeasnodes] = infeasnode;
2563 nodeinfeasible[infeasnode] = TRUE;
2564 ++(*ninfeasnodes);
2565 }
2566
2567 SCIPdebugMsg(scip, "clique: %s(%s) -> %s(%s)\n", getBoundString(lower), SCIPvarGetName(startvar),
2569
2570 /* put the adjacent node onto the stack */
2571 dfsstack[stacksize] = idx;
2572 stacknextclique[stacksize] = 0;
2573 stacknextcliquevar[stacksize] = 0;
2574 cliquecurrentexit[clqidx] = idx + 1;
2575 predstackidx[stacksize] = currstackidx;
2576 currstackidx = stacksize;
2577 stacksize++;
2578 assert(stacksize <= 2 * (SCIPgetNVars(scip) - SCIPgetNContVars(scip)));
2579
2580#ifdef DEBUG_TARJAN
2581 SCIPdebugMsg(scip, "put %s(%s) on stack[%d]\n", indexGetBoundString(dfsstack[stacksize-1]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize-1])]), stacksize-1);
2582#endif
2583 /* restart while loop, get next index from stack */
2584 continue;
2585 }
2586 assert(stacknextclique[currstackidx] == ncliques);
2587
2588 /* no node with a smaller index can be reached from this node -> it is the root of a SCC,
2589 * consisting of all nodes above it on the stack, including the node itself
2590 */
2591 if( nodelowlink[curridx] == nodeindex[curridx] )
2592 {
2593 /* we are only interested in SCCs with more than one node */
2594 if( dfsstack[stacksize-1] != curridx )
2595 {
2596 int sccvarspos = sccstarts[*nsccs];
2597
2598 SCIPdebugMsg(scip, "SCC:");
2599
2600 /* store the SCC in sccvars */
2601 do{
2602 stacksize--;
2603 idx = dfsstack[stacksize];
2604 nodeonstack[idx] = 0;
2605 sccvars[sccvarspos] = idx;
2606 ++sccvarspos;
2608#ifdef DEBUG_TARJAN
2609 SCIPdebugMsg(scip, "remove %s(%s) from stack[%d]\n", indexGetBoundString(dfsstack[stacksize]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize])]), stacksize);
2610#endif
2611 }
2612 while( idx != curridx );
2613 SCIPdebugMsgPrint(scip, "\n");
2614 ++(*nsccs);
2615 sccstarts[*nsccs] = sccvarspos;
2616 }
2617 /* trivial SCC: remove the single node from the stack, but don't store it as a SCC */
2618 else
2619 {
2620 stacksize--;
2621#ifdef DEBUG_TARJAN
2622 SCIPdebugMsg(scip, "remove %s(%s) from stack[%d]\n", indexGetBoundString(dfsstack[stacksize]), SCIPvarGetName(vars[getVarIndex(dfsstack[stacksize])]), stacksize);
2623#endif
2624 idx = dfsstack[stacksize];
2625 nodeonstack[idx] = 0;
2626 assert(nodeindex[idx] > 0);
2627 }
2628 }
2629 /* in a pure dfs, the node would now leave the stack, add it to the array of nodes in reverse topological order */
2630 if( topoorder != NULL && (stacksize > 0 || label > *startindex + 1) )
2631 {
2632 assert(nordered != NULL);
2633 topoorder[*nordered] = curridx;
2634 ++(*nordered);
2635 }
2636
2637 /* the current node was handled, backtrack */
2638 if( stacksize > 0 )
2639 {
2640 idx = dfsstack[predstackidx[currstackidx]];
2641 nodelowlink[idx] = MIN(nodelowlink[idx], nodelowlink[curridx]);
2642 currstackidx = predstackidx[currstackidx];
2643 }
2644 }
2645
2646 *startindex = label;
2647
2648 return SCIP_OKAY;
2649}
2650
2651
2652/** apply fixings and aggregations found by the clique graph analysis */
2653static
2655 SCIP* scip, /**< SCIP data structure */
2656 SCIP_VAR** vars, /**< array of active variables */
2657 int* infeasnodes, /**< sparse array with node indices of infeasible nodes */
2658 int ninfeasnodes, /**< pointer to store the number of infeasible nodes */
2659 SCIP_Shortbool* nodeinfeasible, /**< array to store whether the fixing of a node was detected to be infeasible */
2660 int* sccvars, /**< array with all nontrivial strongly connected components in the graph */
2661 int* sccstarts, /**< start indices of SCCs in sccvars array; one additional entry at the end
2662 * to give length of used part of sccvars array */
2663 int nsccs, /**< pointer to store number of strongly connected components */
2664 SCIP_Bool* infeasible, /**< pointer to store whether an infeasibility was detected */
2665 int* nfixedvars, /**< pointer to number of fixed variables, increment when fixing another one */
2666 int* naggrvars, /**< pointer to number of aggregated variables, increment when aggregating another one */
2667 SCIP_RESULT* result /**< pointer to store result of the call */
2668 )
2669{
2670 int i = 0;
2671
2672 assert(scip != NULL);
2673 assert(vars != NULL);
2674 assert(infeasible != NULL);
2675
2676 /* for all infeasible node: fix variable to the other bound */
2677 if( !(*infeasible) && ninfeasnodes > 0 )
2678 {
2679 for( i = 0; i < ninfeasnodes; ++i )
2680 {
2681 SCIP_VAR* var = vars[getVarIndex(infeasnodes[i])];
2682 SCIP_Bool lower = isIndexLowerbound(infeasnodes[i]);
2683 SCIP_Bool fixed;
2684
2685 assert(nodeinfeasible[infeasnodes[i]]);
2686 nodeinfeasible[infeasnodes[i]] = FALSE;
2687
2688 SCIP_CALL( SCIPfixVar(scip, var, lower ? 0.0 : 1.0, infeasible, &fixed) );
2689
2690 SCIPdebugMsg(scip, "fix <%s>[%d] to %g: inf=%u, fixed=%u\n",
2691 SCIPvarGetName(var), infeasnodes[i], lower ? 0.0 : 1.0, *infeasible, fixed);
2692
2693 /* fixing was infeasible */
2694 if( *infeasible )
2695 break;
2696
2697 /* increase fixing counter and update result pointer */
2698 if( fixed )
2699 {
2700 *result = SCIP_SUCCESS;
2701 ++(*nfixedvars);
2702 }
2703 }
2704 }
2705 assert((*infeasible) || i == ninfeasnodes);
2706
2707 /* clear clean buffer array (if we did not enter the block above or stopped early due to an infeasibility) */
2708 for( ; i < ninfeasnodes; ++i )
2709 {
2710 assert(nodeinfeasible[infeasnodes[i]]);
2711 nodeinfeasible[infeasnodes[i]] = FALSE;
2712 }
2713
2714 if( !(*infeasible) && nsccs > 0 )
2715 {
2716 /* for each strongly connected component: aggregate all variables to the first one */
2717 for( i = 0; i < nsccs; ++i )
2718 {
2719 SCIP_VAR* startvar;
2720 SCIP_Bool lower;
2721 SCIP_Bool aggregated;
2722 SCIP_Bool redundant;
2723 int v;
2724
2725 assert(sccstarts[i] < sccstarts[i+1] - 1);
2726
2727 /* get variable and boundtype for first node of the SCC */
2728 startvar = vars[getVarIndex(sccvars[sccstarts[i]])];
2729 lower = isIndexLowerbound(sccvars[sccstarts[i]]);
2730
2731 for( v = sccstarts[i] + 1; v < sccstarts[i+1]; ++v )
2732 {
2733 /* aggregate variables: if both nodes represent the same bound, we have x=1 <=> y=1,
2734 * and thus aggregate x - y = 0; if both represent different bounds we have
2735 * x=1 <=> y=0, so we aggregate x + y = 1
2736 */
2737 SCIP_CALL( SCIPaggregateVars(scip, startvar, vars[getVarIndex(sccvars[v])], 1.0,
2738 lower == isIndexLowerbound(sccvars[v]) ? -1.0 : 1.0,
2739 lower == isIndexLowerbound(sccvars[v]) ? 0.0 : 1.0,
2740 infeasible, &redundant, &aggregated) );
2741
2742 SCIPdebugMsg(scip, "aggregate <%s> + %g <%s> = %g: inf=%u, red=%u, aggr=%u\n",
2743 SCIPvarGetName(startvar), lower == isIndexLowerbound(sccvars[v]) ? -1.0 : 1.0,
2744 SCIPvarGetName(vars[getVarIndex(sccvars[v])]), lower == isIndexLowerbound(sccvars[v]) ? 0.0 : 1.0,
2745 *infeasible, redundant, aggregated);
2746
2747 /* aggregation was infeasible */
2748 if( *infeasible )
2749 break;
2750
2751 /* increase aggregation counter and update result pointer */
2752 if( aggregated )
2753 {
2754 ++(*naggrvars);
2755 *result = SCIP_SUCCESS;
2756 }
2757 }
2758 }
2759 }
2760
2761 return SCIP_OKAY;
2762}
2763
2764
2765
2766/** presolving method of propagator: search for strongly connected components in the implication graph and
2767 * aggregate all variables within a component; additionally, identifies infeasible variable assignments
2768 * as a side product if a path from x=1 to x=0 (or vice versa) is found or x=1 implies both y=0 and y=1
2769 * The identification of such assignments depends on the order in which variable bounds are processed;
2770 * therefore, we are doing a second run with the bounds processed in (almost) topological order.
2771 */
2772static
2773SCIP_DECL_PROPPRESOL(propPresolVbounds)
2774{ /*lint --e{715}*/
2775 SCIP_PROPDATA* propdata;
2776 SCIP_VAR** tmpvars;
2777 SCIP_VAR** vars;
2778 int* dfsstack;
2779 int* stacknextclique;
2780 int* stacknextcliquevar;
2781 int* nodeindex;
2782 int* nodelowlink;
2783 int* predstackidx;
2784 int* cliquefirstentry;
2785 int* cliquecurrentexit;
2786 int* topoorder;
2787 int* sccvars;
2788 int* sccstarts;
2789 int* infeasnodes;
2790 SCIP_Shortbool* nodeonstack;
2791 SCIP_Shortbool* nodeinfeasible;
2792 int ninfeasnodes;
2793 int nsccs;
2794 int nbounds;
2795 int nbinvars;
2796 int ncliques;
2797 int startindex = 1;
2798 int nordered = 0;
2799 int i;
2800 SCIP_Bool infeasible = FALSE;
2801
2802 assert(scip != NULL);
2803
2804 propdata = SCIPpropGetData(prop);
2805 assert(propdata != NULL);
2806
2807 ncliques = SCIPgetNCliques(scip);
2808
2809 *result = SCIP_DIDNOTRUN;
2810
2811 if( ncliques < 2 )
2812 return SCIP_OKAY;
2813
2814 /* too many cliques for medium presolving */
2815 if( presoltiming == SCIP_PRESOLTIMING_MEDIUM && ncliques > propdata->maxcliquesmedium * SCIPgetNBinVars(scip) )
2816 return SCIP_OKAY;
2817
2818 /* too many cliques for exhaustive presolving */
2819 if( ncliques > propdata->maxcliquesexhaustive * SCIPgetNBinVars(scip) )
2820 return SCIP_OKAY;
2821
2822 /* only run if enough new cliques were created since the last successful call */
2823 if( SCIPgetNCliquesCreated(scip) < (1.0 + propdata->minnewcliques) * propdata->lastpresolncliques )
2824 return SCIP_OKAY;
2825
2826 *result = SCIP_DIDNOTFIND;
2827
2828 nbinvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
2829 nbounds = 2 * nbinvars;
2830
2831 /* cleanup cliques, stop if this proved infeasibility already */
2832 SCIP_CALL( SCIPcleanupCliques(scip, &infeasible) );
2833
2834 if( infeasible )
2835 {
2836 *result = SCIP_CUTOFF;
2837 return SCIP_OKAY;
2838 }
2839
2840 tmpvars = SCIPgetVars(scip);
2841
2842 /* duplicate variable array; needed to get the fixings right later */
2843 SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, tmpvars, nbinvars) );
2844
2845 SCIP_CALL( SCIPallocBufferArray(scip, &dfsstack, nbounds) );
2846 SCIP_CALL( SCIPallocBufferArray(scip, &stacknextclique, nbounds) );
2847 SCIP_CALL( SCIPallocBufferArray(scip, &stacknextcliquevar, nbounds) );
2848 SCIP_CALL( SCIPallocBufferArray(scip, &predstackidx, nbounds) );
2849 SCIP_CALL( SCIPallocBufferArray(scip, &topoorder, nbounds) );
2850 SCIP_CALL( SCIPallocBufferArray(scip, &sccvars, nbounds) );
2851 SCIP_CALL( SCIPallocBufferArray(scip, &sccstarts, nbinvars + 1) );
2852 SCIP_CALL( SCIPallocBufferArray(scip, &infeasnodes, nbounds) );
2853 SCIP_CALL( SCIPallocClearBufferArray(scip, &nodeindex, nbounds) );
2854 SCIP_CALL( SCIPallocClearBufferArray(scip, &nodelowlink, nbounds) );
2855 SCIP_CALL( SCIPallocClearBufferArray(scip, &cliquefirstentry, ncliques) );
2856 SCIP_CALL( SCIPallocClearBufferArray(scip, &cliquecurrentexit, ncliques) );
2857 SCIP_CALL( SCIPallocClearBufferArray(scip, &nodeonstack, nbounds) );
2858 SCIP_CALL( SCIPallocCleanBufferArray(scip, &nodeinfeasible, nbounds) );
2859 sccstarts[0] = 0;
2860 nsccs = 0;
2861 ninfeasnodes = 0;
2862
2863 /* while there are unvisited nodes, run Tarjan's algorithm starting from one of these nodes */
2864 for( i = 0; i < nbounds && !infeasible; ++i )
2865 {
2866 if( nodeindex[i] == 0 )
2867 {
2868 SCIP_CALL( tarjan(scip, i, &startindex, nodeonstack, nodeindex, nodelowlink, nodeinfeasible,
2869 dfsstack, predstackidx, stacknextclique, stacknextcliquevar, topoorder, &nordered,
2870 cliquefirstentry, cliquecurrentexit, sccvars, sccstarts, &nsccs,
2871 infeasnodes, &ninfeasnodes, &infeasible) );
2872 }
2873 }
2874 assert(nordered <= nbounds);
2875
2876 /* aggregate all variables within a SCC and fix all variables for which one bounds was proven infeasible */
2877 if( ninfeasnodes > 0 || nsccs > 0 )
2878 {
2879 SCIP_CALL( applyFixingsAndAggregations(scip, vars, infeasnodes, ninfeasnodes, nodeinfeasible,
2880 sccvars, sccstarts, nsccs, &infeasible, nfixedvars, naggrvars, result) );
2881 }
2882
2883 /* second round, now with topological order! */
2884 if( !infeasible && nordered > 0 )
2885 {
2886 SCIP_VAR** vars2;
2887 int nbounds2;
2888
2889 assert(nordered > 1);
2890
2891 /* we already fixed or aggregated some variables in the first run, so we better clean up the cliques */
2892 if( *result == SCIP_SUCCESS )
2893 {
2894 SCIP_CALL( SCIPcleanupCliques(scip, &infeasible) );
2895
2896 if( infeasible )
2897 goto TERMINATE;
2898 }
2899
2900 nbounds2 = 2 * (SCIPgetNVars(scip) - SCIPgetNContVars(scip));
2901 ncliques = SCIPgetNCliques(scip);
2902
2903 SCIP_CALL( SCIPduplicateBufferArray(scip, &vars2, tmpvars, nbounds2/2) );
2904
2905 /* clear arrays that should be initialized to 0 */
2906 BMSclearMemoryArray(nodeonstack, nbounds2);
2907 BMSclearMemoryArray(nodeindex, nbounds2);
2908 BMSclearMemoryArray(nodelowlink, nbounds2);
2909 BMSclearMemoryArray(cliquefirstentry, ncliques);
2910 BMSclearMemoryArray(cliquecurrentexit, ncliques);
2911 sccstarts[0] = 0;
2912 nsccs = 0;
2913 ninfeasnodes = 0;
2914 startindex = 1;
2915
2916 /* while there are unvisited nodes, run Tarjan's algorithm starting from one of these nodes */
2917 for( i = nordered - 1; i >= 0 && !infeasible; --i )
2918 {
2919 int varindex;
2920 int startpos;
2921 assert(topoorder[i] < nbounds);
2922
2923 /* variable of next node in topological order */
2924 varindex = SCIPvarGetProbindex(vars[getVarIndex(topoorder[i])]);
2925
2926 /* variable was not fixed after the first run */
2927 if( varindex >= 0 )
2928 {
2929 startpos = isIndexLowerbound(topoorder[i]) ? getLbIndex(varindex) : getUbIndex(varindex);
2930 if( nodeindex[startpos] == 0 )
2931 {
2932 SCIP_CALL( tarjan(scip, startpos, &startindex, nodeonstack, nodeindex, nodelowlink, nodeinfeasible,
2933 dfsstack, predstackidx, stacknextclique, stacknextcliquevar, NULL, NULL,
2934 cliquefirstentry, cliquecurrentexit, sccvars, sccstarts, &nsccs,
2935 infeasnodes, &ninfeasnodes, &infeasible) );
2936 }
2937 }
2938 }
2939
2940 /* aggregate all variables within a SCC and fix all variables for which one bounds was proven infeasible */
2941 if( ninfeasnodes > 0 || nsccs > 0 )
2942 {
2943 SCIP_CALL( applyFixingsAndAggregations(scip, vars2, infeasnodes, ninfeasnodes, nodeinfeasible,
2944 sccvars, sccstarts, nsccs, &infeasible, nfixedvars, naggrvars, result) );
2945 }
2946
2947 SCIPfreeBufferArray(scip, &vars2);
2948 }
2949
2950 TERMINATE:
2951 if( infeasible )
2952 *result = SCIP_CUTOFF;
2953#ifndef NDEBUG
2954 for( i = 0; i < nbounds; ++i )
2955 {
2956 assert(nodeinfeasible[i] == FALSE);
2957 }
2958#endif
2959 SCIPfreeCleanBufferArray(scip, &nodeinfeasible);
2960 SCIPfreeBufferArray(scip, &nodeonstack);
2961 SCIPfreeBufferArray(scip, &cliquecurrentexit);
2962 SCIPfreeBufferArray(scip, &cliquefirstentry);
2963 SCIPfreeBufferArray(scip, &nodelowlink);
2964 SCIPfreeBufferArray(scip, &nodeindex);
2965 SCIPfreeBufferArray(scip, &infeasnodes);
2966 SCIPfreeBufferArray(scip, &sccstarts);
2967 SCIPfreeBufferArray(scip, &sccvars);
2968 SCIPfreeBufferArray(scip, &topoorder);
2969 SCIPfreeBufferArray(scip, &predstackidx);
2970 SCIPfreeBufferArray(scip, &stacknextcliquevar);
2971 SCIPfreeBufferArray(scip, &stacknextclique);
2972 SCIPfreeBufferArray(scip, &dfsstack);
2973 SCIPfreeBufferArray(scip, &vars);
2974
2975 propdata->lastpresolncliques = SCIPgetNCliquesCreated(scip);
2976
2977 return SCIP_OKAY;
2978}
2979
2980
2981
2982/** execution method of propagator */
2983static
2984SCIP_DECL_PROPEXEC(propExecVbounds)
2985{ /*lint --e{715}*/
2986 *result = SCIP_DIDNOTRUN;
2987
2988 /* perform variable lower and upper bound propagation */
2989 SCIP_CALL( propagateVbounds(scip, prop, FALSE, result) );
2990
2991 assert((*result) == SCIP_CUTOFF || (*result) == SCIP_DIDNOTRUN
2992 || (*result) == SCIP_DIDNOTFIND || (*result) == SCIP_REDUCEDDOM);
2993
2994 return SCIP_OKAY;
2995}
2996
2997/** propagation conflict resolving method of propagator */
2998static
2999SCIP_DECL_PROPRESPROP(propRespropVbounds)
3000{ /*lint --e{715}*/
3001 SCIP_PROPDATA* propdata;
3002 SCIP_VAR** vars;
3003 SCIP_VAR* startvar;
3004 SCIP_BOUNDTYPE starttype;
3005 int pos;
3006
3007 propdata = SCIPpropGetData(prop);
3008 assert(propdata != NULL);
3009
3010 starttype = inferInfoGetBoundtype(intToInferInfo(inferinfo));
3011 pos = inferInfoGetPos(intToInferInfo(inferinfo));
3012 assert(pos >= 0);
3013 assert(pos < propdata->nbounds);
3014
3015 vars = propdata->vars;
3016 assert(vars != NULL);
3017 startvar = vars[getVarIndex(pos)];
3018 assert(startvar != NULL);
3019 assert(startvar != infervar);
3020
3021 SCIPdebugMsg(scip, "explain %s bound change of variable <%s>\n",
3022 getBoundtypeString(boundtype), SCIPvarGetName(infervar));
3023
3024 if( !SCIPvarIsBinary(startvar) && propdata->usebdwidening )
3025 {
3026 int* vboundboundedidx;
3027 SCIP_Real constant;
3028 SCIP_Real coef;
3029 int inferidx;
3030 int nvbounds;
3031 int b;
3032
3033 nvbounds = propdata->nvbounds[pos];
3034 vboundboundedidx = propdata->vboundboundedidx[pos];
3035
3036 inferidx = boundtype == SCIP_BOUNDTYPE_LOWER ? varGetLbIndex(propdata, infervar) : varGetUbIndex(propdata, infervar);
3037 assert(inferidx >= 0);
3038
3039 for( b = 0; b < nvbounds; ++b )
3040 {
3041 if( vboundboundedidx[b] == inferidx )
3042 break;
3043 }
3044 assert(b < nvbounds);
3045
3046 coef = propdata->vboundcoefs[pos][b];
3047 constant = propdata->vboundconstants[pos][b];
3048 assert(!SCIPisZero(scip, coef));
3049
3050 /* compute the relaxed bound which is sufficient to propagate the inference bound of given variable */
3051 if( boundtype == SCIP_BOUNDTYPE_LOWER )
3052 relaxedbd = computeRelaxedLowerbound(scip, infervar, relaxedbd, coef, constant);
3053 else
3054 relaxedbd = computeRelaxedUpperbound(scip, infervar, relaxedbd, coef, constant);
3055
3056 /* try to relax variable bound variable */
3057 SCIP_CALL( relaxVbdvar(scip, startvar, starttype, bdchgidx, relaxedbd) );
3058 }
3059 else
3060 {
3061 SCIP_CALL( resolvePropagation(scip, propdata, startvar, starttype, bdchgidx) );
3062 }
3063
3064 (*result) = SCIP_SUCCESS;
3065
3066 return SCIP_OKAY;
3067}
3068
3069/**@} */
3070
3071/**@name Callback methods of event handler
3072 *
3073 * @{
3074 */
3075
3076/** execution method of bound change event handler */
3077static
3078SCIP_DECL_EVENTEXEC(eventExecVbound)
3079{ /*lint --e{715}*/
3080 SCIP_PROPDATA* propdata;
3081 int idx;
3082
3083 assert(eventhdlr != NULL);
3084
3085 propdata = (SCIP_PROPDATA*)SCIPeventhdlrGetData(eventhdlr);
3086 assert(propdata != NULL);
3087
3088 /* coverity[pointer_conversion_loses_bits] */
3089 idx = (int) (size_t) eventdata;
3090 assert(idx >= 0);
3091
3092 SCIPdebugMsg(scip, "eventexec (type=%" SCIP_EVENTTYPE_FORMAT "): try to add sort index %d: %s(%s) to priority queue\n", SCIPeventGetType(event),
3093 idx, indexGetBoundString(propdata->topoorder[idx]),
3094 SCIPvarGetName(propdata->vars[getVarIndex(propdata->topoorder[idx])]));
3095
3097 && SCIPeventGetNewbound(event) > 0.5 )
3098 return SCIP_OKAY;
3099
3101 && SCIPeventGetNewbound(event) < 0.5 )
3102 return SCIP_OKAY;
3103
3104 assert(getVarIndex(propdata->topoorder[idx]) < SCIPgetNVars(scip));
3105 assert(SCIPvarGetType(propdata->vars[getVarIndex(propdata->topoorder[idx])]) != SCIP_VARTYPE_BINARY
3106 || (isIndexLowerbound(propdata->topoorder[idx]) == (SCIPeventGetNewbound(event) > 0.5)));
3107
3108 /* add the bound change to the propagation queue, if it is not already contained */
3109 if( !propdata->inqueue[idx] )
3110 {
3111 SCIP_CALL( SCIPpqueueInsert(propdata->propqueue, (void*)(size_t)(idx + 1)) ); /*lint !e571 !e776*/
3112 propdata->inqueue[idx] = TRUE;
3113 assert(SCIPpqueueNElems(propdata->propqueue) > 0);
3114 }
3115
3116 return SCIP_OKAY;
3117}
3118
3119/**@} */
3120
3121
3122/** creates the vbounds propagator and includes it in SCIP */
3124 SCIP* scip /**< SCIP data structure */
3125 )
3126{
3127 SCIP_PROPDATA* propdata;
3128 SCIP_PROP* prop;
3129
3130 /* create vbounds propagator data */
3131 SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
3132
3133 /* reset propagation data */
3134 resetPropdata(propdata);
3135
3136 /* include propagator */
3138 propExecVbounds, propdata) );
3139 assert(prop != NULL);
3140
3141 /* set optional callbacks via setter functions */
3142 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyVbounds) );
3143 SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeVbounds) );
3144 SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreVbounds) );
3145 SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolVbounds) );
3146 SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropVbounds) );
3149
3150 /* include event handler for bound change events */
3152 eventExecVbound, (SCIP_EVENTHDLRDATA*)propdata) );
3153
3155 "propagating/" PROP_NAME "/usebdwidening", "should bound widening be used to initialize conflict analysis?",
3156 &propdata->usebdwidening, FALSE, DEFAULT_USEBDWIDENING, NULL, NULL) );
3158 "propagating/" PROP_NAME "/useimplics", "should implications be propagated?",
3159 &propdata->useimplics, TRUE, DEFAULT_USEIMPLICS, NULL, NULL) );
3161 "propagating/" PROP_NAME "/usecliques", "should cliques be propagated?",
3162 &propdata->usecliques, TRUE, DEFAULT_USECLIQUES, NULL, NULL) );
3164 "propagating/" PROP_NAME "/usevbounds", "should vbounds be propagated?",
3165 &propdata->usevbounds, TRUE, DEFAULT_USEVBOUNDS, NULL, NULL) );
3167 "propagating/" PROP_NAME "/dotoposort", "should the bounds be topologically sorted in advance?",
3168 &propdata->dotoposort, FALSE, DEFAULT_DOTOPOSORT, NULL, NULL) );
3170 "propagating/" PROP_NAME "/sortcliques", "should cliques be regarded for the topological sort?",
3171 &propdata->sortcliques, TRUE, DEFAULT_SORTCLIQUES, NULL, NULL) );
3173 "propagating/" PROP_NAME "/detectcycles", "should cycles in the variable bound graph be identified?",
3174 &propdata->detectcycles, FALSE, DEFAULT_DETECTCYCLES, NULL, NULL) );
3176 "propagating/" PROP_NAME "/minnewcliques", "minimum percentage of new cliques to trigger another clique table analysis",
3177 &propdata->minnewcliques, FALSE, DEFAULT_MINNEWCLIQUES, 0.0, 1.0, NULL, NULL) );
3178 SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/maxcliquesmedium",
3179 "maximum number of cliques per variable to run clique table analysis in medium presolving",
3180 &propdata->maxcliquesmedium, FALSE, DEFAULT_MAXCLIQUESMEDIUM, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3181 SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/maxcliquesexhaustive",
3182 "maximum number of cliques per variable to run clique table analysis in exhaustive presolving",
3183 &propdata->maxcliquesexhaustive, FALSE, DEFAULT_MAXCLIQUESEXHAUSTIVE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3184
3185 return SCIP_OKAY;
3186}
3187
3188/** returns TRUE if the propagator has the status that all variable lower and upper bounds are propgated */
3190 SCIP* scip /**< SCIP data structure */
3191 )
3192{
3193 SCIP_PROP* prop;
3194 SCIP_PROPDATA* propdata;
3195
3196 prop = SCIPfindProp(scip, PROP_NAME);
3197 assert(prop != NULL);
3198
3199 propdata = SCIPpropGetData(prop);
3200 assert(propdata != NULL);
3201
3202 return (SCIPpqueueNElems(propdata->propqueue) == 0);
3203}
3204
3205/** performs propagation of variables lower and upper bounds */
3207 SCIP* scip, /**< SCIP data structure */
3208 SCIP_Bool force, /**< should domain changes for continuous variables be forced */
3209 SCIP_RESULT* result /**< pointer to store result */
3210 )
3211{
3212 SCIP_PROP* prop;
3213
3214 prop = SCIPfindProp(scip, PROP_NAME);
3215 assert(prop != NULL);
3216
3217 /* perform variable lower and upper bound propagation */
3218 SCIP_CALL( propagateVbounds(scip, prop, force, result) );
3219
3220 assert((*result) == SCIP_CUTOFF || (*result) == SCIP_DIDNOTRUN
3221 || (*result) == SCIP_DIDNOTFIND || (*result) == SCIP_REDUCEDDOM);
3222
3223 return SCIP_OKAY;
3224}
SCIP_VAR ** b
Definition: circlepacking.c:65
struct InferInfo INFERINFO
#define NULL
Definition: def.h:267
#define SCIP_Shortbool
Definition: def.h:99
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIPABORT()
Definition: def.h:346
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2172
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
#define SCIPdebugMsgPrint
Definition: scip_message.h:79
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_Bool SCIPisPropagatedVbounds(SCIP *scip)
SCIP_RETCODE SCIPexecPropVbounds(SCIP *scip, SCIP_Bool force, SCIP_RESULT *result)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
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
int SCIPpqueueFind(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1549
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
Definition: misc.c:1322
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1394
int SCIPpqueueNElems(SCIP_PQUEUE *pqueue)
Definition: misc.c:1527
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1295
void * SCIPpqueueRemove(SCIP_PQUEUE *pqueue)
Definition: misc.c:1493
SCIP_RETCODE SCIPincludePropVbounds(SCIP *scip)
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE 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 SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:334
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1030
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:1053
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
Definition: event.c:1242
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:146
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:70
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:80
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#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_PROP * SCIPfindProp(SCIP *scip, const char *name)
Definition: scip_prop.c:329
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:799
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:312
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:789
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:279
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:941
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:247
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:167
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:151
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:231
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:114
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Real SCIPgetHugeValue(SCIP *scip)
SCIP_Bool SCIPisGT(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)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:146
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:434
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:110
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5203
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:18270
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:18292
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17748
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIP_RETCODE SCIPinferVarUbProp(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_PROP *inferprop, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6010
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6348
SCIP_Bool SCIPvarHasImplic(SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype)
Definition: var.c:11111
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18356
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip_var.c:8401
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5320
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip_var.c:1794
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18373
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2128
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17768
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
int SCIPgetNCliquesCreated(SCIP *scip)
Definition: scip_var.c:7602
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
Definition: scip_var.c:7532
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip_var.c:4645
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:18302
int * SCIPvarGetImplIds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18418
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:18312
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip_var.c:4613
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18402
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18430
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
int SCIPgetNCliques(SCIP *scip)
Definition: scip_var.c:7575
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:18282
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18441
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1992
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:18344
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:18324
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:18334
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18388
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6228
SCIP_RETCODE SCIPinferVarLbProp(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_PROP *inferprop, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5895
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3380
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3370
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3392
int SCIPcliqueGetIndex(SCIP_CLIQUE *clique)
Definition: implics.c:3416
SCIP_Bool SCIPcliqueIsEquation(SCIP_CLIQUE *clique)
Definition: implics.c:3436
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
#define PROP_PRESOL_MAXROUNDS
Definition: prop_vbounds.c:120
#define PROP_PRESOLTIMING
Definition: prop_vbounds.c:119
#define getOtherBoundIndex(idx)
Definition: prop_vbounds.c:173
#define PROP_DESC
Definition: prop_vbounds.c:112
static SCIP_RETCODE propagateVbounds(SCIP *scip, SCIP_PROP *prop, SCIP_Bool force, SCIP_RESULT *result)
#define DEFAULT_MINNEWCLIQUES
Definition: prop_vbounds.c:146
#define DEFAULT_USEBDWIDENING
Definition: prop_vbounds.c:139
static SCIP_RETCODE relaxVbdvar(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd)
static SCIP_RETCODE topologicalSort(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible)
#define isIndexLowerbound(idx)
Definition: prop_vbounds.c:169
#define getBoundString(lower)
Definition: prop_vbounds.c:170
static SCIP_RETCODE extractCycle(SCIP *scip, SCIP_PROPDATA *propdata, int *dfsstack, int *stacknextedge, int stacksize, SCIP_Bool samebound, SCIP_Bool *infeasible)
Definition: prop_vbounds.c:522
#define PROP_NAME
Definition: prop_vbounds.c:111
static SCIP_DECL_PROPFREE(propFreeVbounds)
static SCIP_RETCODE dfs(SCIP *scip, SCIP_PROPDATA *propdata, int startnode, int *visited, int *dfsstack, int *stacknextedge, int *dfsnodes, int *ndfsnodes, SCIP_Bool *infeasible)
Definition: prop_vbounds.c:806
#define VISITED
Definition: prop_vbounds.c:802
static SCIP_Real computeRelaxedLowerbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferlb, SCIP_Real coef, SCIP_Real constant)
#define getUbIndex(idx)
Definition: prop_vbounds.c:166
#define DEFAULT_MAXCLIQUESMEDIUM
Definition: prop_vbounds.c:147
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:354
#define ACTIVE
Definition: prop_vbounds.c:803
static SCIP_DECL_EVENTEXEC(eventExecVbound)
#define DEFAULT_USECLIQUES
Definition: prop_vbounds.c:141
static SCIP_DECL_SORTPTRCOMP(compVarboundIndices)
Definition: prop_vbounds.c:510
static int varGetLbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
Definition: prop_vbounds.c:302
static SCIP_RETCODE analyzeConflictUpperbound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *infervar, SCIP_Real inferub, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide)
static SCIP_RETCODE addVbound(SCIP *scip, SCIP_PROPDATA *propdata, int startidx, int endidx, SCIP_Real coef, SCIP_Real constant)
Definition: prop_vbounds.c:463
#define indexGetBoundString(idx)
Definition: prop_vbounds.c:172
static int inferInfoGetPos(INFERINFO inferinfo)
Definition: prop_vbounds.c:271
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:413
#define PROP_DELAY
Definition: prop_vbounds.c:116
static INFERINFO intToInferInfo(int i)
Definition: prop_vbounds.c:238
static SCIP_RETCODE applyFixingsAndAggregations(SCIP *scip, SCIP_VAR **vars, int *infeasnodes, int ninfeasnodes, SCIP_Shortbool *nodeinfeasible, int *sccvars, int *sccstarts, int nsccs, SCIP_Bool *infeasible, int *nfixedvars, int *naggrvars, SCIP_RESULT *result)
#define getLbIndex(idx)
Definition: prop_vbounds.c:165
#define getBoundtypeString(type)
Definition: prop_vbounds.c:171
static SCIP_DECL_PROPEXITSOL(propExitsolVbounds)
static SCIP_RETCODE tarjan(SCIP *scip, int startnode, int *startindex, SCIP_Shortbool *nodeonstack, int *nodeindex, int *nodelowlink, SCIP_Shortbool *nodeinfeasible, int *dfsstack, int *predstackidx, int *stacknextclique, int *stacknextcliquevar, int *topoorder, int *nordered, int *cliquefirstentry, int *cliquecurrentexit, int *sccvars, int *sccstarts, int *nsccs, int *infeasnodes, int *ninfeasnodes, SCIP_Bool *infeasible)
static SCIP_BOUNDTYPE inferInfoGetBoundtype(INFERINFO inferinfo)
Definition: prop_vbounds.c:260
#define INITMEMSIZE
Definition: prop_vbounds.c:459
#define PROP_TIMING
Definition: prop_vbounds.c:113
static SCIP_DECL_PROPINITPRE(propInitpreVbounds)
static void resetPropdata(SCIP_PROPDATA *propdata)
Definition: prop_vbounds.c:336
#define DEFAULT_USEIMPLICS
Definition: prop_vbounds.c:140
static int varGetUbIndex(SCIP_PROPDATA *propdata, SCIP_VAR *var)
Definition: prop_vbounds.c:319
static SCIP_DECL_PROPRESPROP(propRespropVbounds)
static SCIP_RETCODE analyzeConflictLowerbound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *infervar, SCIP_Real inferlb, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide)
#define getBoundtype(idx)
Definition: prop_vbounds.c:168
static SCIP_RETCODE tightenVarUb(SCIP *scip, SCIP_PROP *prop, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_Real newub, SCIP_Bool global, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Bool force, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide, int *nchgbds, SCIP_RESULT *result)
#define DEFAULT_MAXCLIQUESEXHAUSTIVE
Definition: prop_vbounds.c:149
#define DEFAULT_USEVBOUNDS
Definition: prop_vbounds.c:142
#define getVarIndex(idx)
Definition: prop_vbounds.c:167
#define DEFAULT_DETECTCYCLES
Definition: prop_vbounds.c:145
#define EVENTHDLR_DESC
Definition: prop_vbounds.c:130
static SCIP_DECL_PROPEXEC(propExecVbounds)
static int inferInfoToInt(INFERINFO inferinfo)
Definition: prop_vbounds.c:251
#define EVENTHDLR_NAME
Definition: prop_vbounds.c:129
static SCIP_DECL_PROPCOPY(propCopyVbounds)
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
#define PROP_FREQ
Definition: prop_vbounds.c:115
static SCIP_DECL_PROPPRESOL(propPresolVbounds)
static SCIP_RETCODE tightenVarLb(SCIP *scip, SCIP_PROP *prop, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_Real newlb, SCIP_Bool global, SCIP_VAR *vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Bool force, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide, int *nchgbds, SCIP_RESULT *result)
#define PROP_PRIORITY
Definition: prop_vbounds.c:114
#define DEFAULT_DOTOPOSORT
Definition: prop_vbounds.c:143
#define PROP_PRESOL_PRIORITY
Definition: prop_vbounds.c:118
static SCIP_RETCODE initData(SCIP *scip, SCIP_PROP *prop, SCIP_Bool *infeasible)
static INFERINFO getInferInfo(int pos, SCIP_BOUNDTYPE boundtype)
Definition: prop_vbounds.c:280
static SCIP_Real computeRelaxedUpperbound(SCIP *scip, SCIP_VAR *var, SCIP_Real inferub, SCIP_Real coef, SCIP_Real constant)
#define DEFAULT_SORTCLIQUES
Definition: prop_vbounds.c:144
variable upper and lower bound propagator
public methods for managing events
public methods for implications, variable bounds, and cliques
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public data structures and miscellaneous methods
public methods for propagators
public methods for problem variables
public methods for conflict handler plugins and conflict analysis
public methods for 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 propagator plugins
public methods for the branch-and-bound tree
public methods for SCIP variables
@ SCIP_CONFTYPE_PROPAGATION
Definition: type_conflict.h:60
#define SCIP_EVENTTYPE_GUBCHANGED
Definition: type_event.h:76
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:173
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:79
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:155
#define SCIP_EVENTTYPE_FORMAT
Definition: type_event.h:152
#define SCIP_EVENTTYPE_GLBCHANGED
Definition: type_event.h:75
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:151
#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_STAGE_SOLVING
Definition: type_set.h:53
#define SCIP_PRESOLTIMING_MEDIUM
Definition: type_timing.h:53
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62