Scippy

SCIP

Solving Constraint Integer Programs

prop_pseudoobj.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-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop_pseudoobj.c
17  * @brief Pseudo objective propagator
18  * @author Tobias Achterberg
19  * @author Stefan Heinz
20  *
21  * This propagator propagates the objective function using the cutoff bound and the pseudo objective value. The pseudo
22  * objective value can be seen as minimum activity of the linear objective function. Using this, this propagator checks
23  * if variables with non-zero objective coefficients can exceed the cutoff bound. If this is the case the corresponding
24  * bound can be tightened.
25  *
26  * @todo use the complete implication to initialize the objective implication data structure
27  */
28 
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
30 
31 #include <assert.h>
32 #include <string.h>
33 
34 #include "scip/prop_pseudoobj.h"
35 
36 
37 #define PROP_NAME "pseudoobj"
38 #define PROP_DESC "pseudo objective function propagator"
39 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP
40 #define PROP_PRIORITY 3000000 /**< propagator priority */
41 #define PROP_FREQ 1 /**< propagator frequency */
42 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
43 #define PROP_PRESOL_PRIORITY +6000000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
44 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
45  * limit) */
46 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */
47 
48 #define EVENTHDLR_NAME "pseudoobj"
49 #define EVENTHDLR_DESC "bound change event handler for pseudo objective function propagator"
50 
51 #define DEFAULT_MINUSELESS 100 /**< minimal number of successive non-binary variable propagator whithout a
52  * bound reduction before aborted */
53 #define DEFAULT_MAXVARSFRAC 0.1 /**< maximal fraction of non-binary variables with non-zero objective
54  * without a bound reduction before aborted */
55 #define DEFAULT_PROPFULLINROOT TRUE /**< do we want to propagate all non-binary variables if we are propagating the root node? */
56 #define DEFAULT_PROPCUTOFFBOUND TRUE /**< propagate new cutoff bound directly globally */
57 #define DEFAULT_FORCE FALSE /**< should the propagator be forced even if active pricer are present? Note that
58  * can be done if it is known that the pseudo objective activity is given by
59  * the zero bound for all variables which are currently not present in the
60  * problem */
61 #define DEFAULT_MAXNEWVARS 1000 /**< number of variable added after the propagator is reinitialized? */
62 #define DEFAULT_PROPUSEIMPLICS TRUE /**< use implications to strengthen the propagation of binary variable (increasing the objective change)? */
63 #define DEFAULT_RESPROPUSEIMPLICS TRUE /**< use implications to strengthen the resolve propagation of binary variable (increasing the objective change)? */
64 #define DEFAULT_MAXIMPLVARS 50000 /**< maximum number of binary variables the implications are used if turned on (-1: unlimited)? */
65 
66 
67 /*
68  * Data structures
69  */
70 
71 /** implication data structure for objective contributions of a binary variable */
72 struct SCIP_ObjImplics
73 {
74  SCIP_VAR** objvars; /**< variables y in implications y == 0 or y == 1, first we store the
75  * implications by x == 0 and second the implications x == 1 */
76  SCIP_Real maxobjchg; /**< maximum objective contribution if variables x is fixed to zero or one */
77  int nlbimpls; /**< number of all implications result through for x == 0 */
78  int nubimpls; /**< number of all implications result through for x == 1 */
79  int size; /**< size of the objvars array */
80 };
81 typedef struct SCIP_ObjImplics SCIP_OBJIMPLICS; /**< implications in the form x == 0 or x == 1 ==> y == 0 or y == 1 for (x and y binary) */
82 
83 
84 /** propagator data */
85 struct SCIP_PropData
86 {
87  SCIP_EVENTHDLR* eventhdlr; /**< event handler for global bound change events */
88  SCIP_VAR** minactvars; /**< binary variables with non-zero objective contribution w.r.t. minimum activity of the objective function */
89  SCIP_OBJIMPLICS** minactimpls; /**< implication data structure for the binary variables w.r.t. minimum activity */
90  SCIP_VAR** maxactvars; /**< binary variables with non-zero objective contribution w.r.t. maximum activity of the objective function */
91  SCIP_Real* maxactchgs; /**< the maximal potential change of the objective if the binary variable
92  * is fixed to its best bound w.r.t. maximum activity of the objective function */
93 
94  SCIP_VAR** objintvars; /**< non-binary variable with non-zero objective coefficient */
95  SCIP_HASHTABLE* addedvars; /**< hash table used during resolving of a bound change (conflict analysis) */
96  SCIP_Real lastlowerbound; /**< last lower bound which was propagated */
97  SCIP_Real cutoffbound; /**< last cutoff bound used for propagation */
98  SCIP_Real glbpseudoobjval; /**< last global pseudo objective used in presolving */
99  SCIP_Real maxvarsfrac; /**< maximal fraction of non-binary variables with non-zero objective
100  * without a bound reduction before aborted
101  */
102  SCIP_Real maxpseudoobjact; /**< maximal global pseudo objective activity */
103  int maxpseudoobjactinf; /**< number of coefficients contributing with infinite value to maxpseudoobjact */
104  int nminactvars; /**< number of binary variables with non-zero objective contribution w.r.t. minimum activity of the objective function */
105  int nmaxactvars; /**< number of binary variables with non-zero objective contribution w.r.t. maximum activity of the objective function */
106  int nobjintvars; /**< number of non-binary variables with non-zero objective */
107  int minuseless; /**< minimal number of successive non-binary variable propagator whithout
108  * a bound reduction before aborted
109  */
110  int lastvarnum; /**< last non-binary variable number that was looked at */
111  int glbfirstnonfixed; /**< index of first globally non-fixed binary variable in minactvars array */
112  int maxactfirstnonfixed;/**< index of first globally non-fixed binary variable in maxctvars array */
113  int firstnonfixed; /**< index of first locally non-fixed binary variable in minactvars array */
114  int nnewvars; /**< counter for counting number of new variables added */
115  int maxnewvars; /**< number of variable added after the propagator is reinitialized? */
116  int maximplvars; /**< maximum number of binary variables the implications are used if turned on (-1: unlimited)? */
117  int minactsize; /**< size of minactvars and minactimpls array */
118  int maxactsize; /**< size of maxactvars and maxactchgs array */
119  int objintvarssize; /**< size of objintvars array*/
120  SCIP_Bool glbpropagated; /**< are global domains propagated */
121  SCIP_Bool propfullinroot; /**< do we want to propagate all non-binary variables if we are propagating the root node */
122  SCIP_Bool propcutoffbound; /**< propagate new cutoff bound directly globally */
123  SCIP_Bool force; /**< should the propagator be forced even if active pricer are present? */
124  SCIP_Bool catchvaradded; /**< do we catch the variable added event? */
125  SCIP_Bool propuseimplics; /**< use implications to strengthen the propagation of binary variable (increasing the objective change)? */
126  SCIP_Bool respropuseimplics; /**< use implications to strengthen the resolve propagation of binary variable (increasing the objective change)? */
127  SCIP_Bool initialized; /**< is propagator data structure initialized */
128 };
129 
130 /*
131  * Debug methods
132  */
133 
134 #ifndef NDEBUG
135 /** check that the implications are applied for a globally fixed variable */
136 static
138  SCIP* scip, /**< SCIP data structure */
139  SCIP_VAR* var /**< variable to check the implications */
140  )
141 {
142  SCIP_VAR** vars;
143  SCIP_Real* bounds;
144  SCIP_BOUNDTYPE* boundtypes;
145  SCIP_Bool varfixing;
146  int nvars;
147  int v;
148 
149  /* check that the given variable is locally or globally fixed */
150  assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5);
151 
152  /* get fixed value */
153  varfixing = SCIPvarGetLbGlobal(var) > 0.5;
154 
155  vars = SCIPvarGetImplVars(var, varfixing);
156  nvars = SCIPvarGetNImpls(var, varfixing);
157  bounds = SCIPvarGetImplBounds(var, varfixing);
158  boundtypes = SCIPvarGetImplTypes(var, varfixing);
159 
160  /* check that each implication was applied */
161  for( v = 0; v < nvars; ++v )
162  {
163  if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
164  {
165  SCIP_Real lb;
166 
167  lb = SCIPvarGetLbGlobal(vars[v]);
168  assert(SCIPisLE(scip, lb, bounds[v]));
169  }
170  else
171  {
172  SCIP_Real ub;
173 
174  assert(boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
175 
176  ub = SCIPvarGetLbGlobal(vars[v]);
177  assert(SCIPisGE(scip, ub, bounds[v]));
178  }
179  }
180 }
181 
182 /** check if the global fixed indices are correct */
183 static
185  SCIP* scip, /**< SCIP data structure */
186  SCIP_PROPDATA* propdata /**< propagator data */
187  )
188 {
189  SCIP_VAR* var;
190  int v;
191 
192  for( v = 0; v < propdata->glbfirstnonfixed; ++v )
193  {
194  var = propdata->minactvars[v];
195  assert(var != NULL);
196 
197  assert(SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5);
198  }
199 
200  for( v = 0; v < propdata->maxactfirstnonfixed; ++v )
201  {
202  var = propdata->maxactvars[v];
203  assert(var != NULL);
204 
205  assert(SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5);
206  }
207 }
208 #endif /* end of debug methods */
209 
210 /*
211  * Comparer
212  */
213 
214 /** compares objective implications w.r.t. their maximum contribution */
215 static
216 SCIP_DECL_SORTPTRCOMP(objimplicsComp)
217 {
218  SCIP_OBJIMPLICS* objimplics1;
219  SCIP_OBJIMPLICS* objimplics2;
220 
221  objimplics1 = (SCIP_OBJIMPLICS*)elem1;
222  objimplics2 = (SCIP_OBJIMPLICS*)elem2;
223 
224  if( objimplics1->maxobjchg > objimplics2->maxobjchg )
225  return +1;
226 
227  if( objimplics1->maxobjchg < objimplics2->maxobjchg )
228  return -1;
229 
230  return 0;
231 }
232 
233 /** compare variables w.r.t.
234  * (i) the absolute value the objective coefficient;
235  * (ii) the locks which indicate most effect -- for the variables with a positive (negative) objective coefficient the
236  * down (up) lock is used since this lock indicates that tightened of the upper (lower) bound will triegger
237  * further domain propagations;
238  * (iii) the other locks;
239  * (iv) variable problem index;
240  */
241 static
242 SCIP_DECL_SORTPTRCOMP(varCompObj)
243 {
244  SCIP_VAR* var1;
245  SCIP_VAR* var2;
246  int locks1;
247  int locks2;
249  var1 = (SCIP_VAR*)elem1;
250  var2 = (SCIP_VAR*)elem2;
251 
252  assert(SCIPvarGetObj(var1) != 0.0);
253  assert(SCIPvarGetObj(var2) != 0.0);
254 
255  /* first criteria is the absolute value of objective coefficient */
256  if( REALABS(SCIPvarGetObj(var1)) < REALABS(SCIPvarGetObj(var2)) )
257  return -1;
258  else if( REALABS(SCIPvarGetObj(var1)) > REALABS(SCIPvarGetObj(var2)) )
259  return +1;
260 
261  /* second criteria the locks which indicate most effect */
262  if( SCIPvarGetObj(var1) > 0.0 )
263  locks1 = SCIPvarGetNLocksDown(var1);
264  else
265  locks1 = SCIPvarGetNLocksUp(var1);
266 
267  if( SCIPvarGetObj(var2) > 0.0 )
268  locks2 = SCIPvarGetNLocksDown(var2);
269  else
270  locks2 = SCIPvarGetNLocksUp(var2);
271 
272  if( locks1 < locks2 )
273  return -1;
274  if( locks1 > locks2 )
275  return 1;
276 
277  /* third criteria the other locks */
278  if( SCIPvarGetObj(var1) > 0.0 )
279  locks1 = SCIPvarGetNLocksUp(var1);
280  else
281  locks1 = SCIPvarGetNLocksDown(var1);
282 
283  if( SCIPvarGetObj(var2) > 0.0 )
284  locks2 = SCIPvarGetNLocksUp(var2);
285  else
286  locks2 = SCIPvarGetNLocksDown(var2);
287 
288  if( locks1 < locks2 )
289  return -1;
290  if( locks1 > locks2 )
291  return 1;
292 
293  /* forth criteria use the problem index */
294  return SCIPvarCompare(var1, var2);
295 }
296 
297 /** hash key retrieval function for cliques*/
298 static
299 SCIP_DECL_HASHGETKEY(cliqueGetHashkey)
300 { /*lint --e{715}*/
301  return elem;
302 }
303 
304 /** returns TRUE iff the cliques are equal */
305 static
306 SCIP_DECL_HASHKEYEQ(cliqueIsHashkeyEq)
307 { /*lint --e{715}*/
308  if( key1 == key2 )
309  return TRUE;
310  return FALSE;
311 }
313 /** returns the hash value of the key */
314 static
315 SCIP_DECL_HASHKEYVAL(cliqueGetHashkeyVal)
316 { /*lint --e{715}*/
317  assert( SCIPcliqueGetId((SCIP_CLIQUE*) key) >= 0 );
318  return (unsigned int) SCIPcliqueGetId((SCIP_CLIQUE*) key);
319 }
320 
321 /*
322  * methods for SCIP_OBJIMPLICS data structure
323  */
324 
325 /** creates an objective implication data structure, fixes (globally) variables which are implied by lower and upper
326  * bound fixing, and clears the collected arrays for lower and upper bound
327  */
328 static
330  SCIP* scip, /**< SCIP data structure */
331  SCIP_OBJIMPLICS** objimplics, /**< pointer to objective implication data structure */
332  SCIP_VAR** objvars, /**< objective contributor variables, or NULL */
333  SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays, or NULL */
334  SCIP_Bool* collectedlbvars, /**< temporary buffer to mark collected variables for lower bound fixing, or NULL */
335  SCIP_Bool* collectedubvars, /**< temporary buffer to mark collected variables for upper bound fixing, or NULL */
336  SCIP_Real maxlbobjchg, /**< maximum objective contributor if variables id fixed to zero */
337  SCIP_Real maxubobjchg, /**< maximum objective contributor if variables id fixed to one */
338  int nlbimpls, /**< number of variables contributing to to lower bound fix */
339  int nubimpls /**< number of variables contributing to to upper bound fix */
340  )
341 
342 {
343  assert(scip != NULL);
344  assert(objimplics != NULL);
345  assert(!SCIPisNegative(scip, maxlbobjchg));
346  assert(!SCIPisNegative(scip, maxubobjchg));
347 
348  /* allocate block memory for the implication data structure */
349  SCIP_CALL( SCIPallocBlockMemory(scip, objimplics) );
350 
351  if( nlbimpls + nubimpls == 0 )
352  {
353  assert(nlbimpls == 0);
354  assert(nubimpls == 0);
355  (*objimplics)->objvars = NULL;
356  (*objimplics)->maxobjchg = 0.0;
357  (*objimplics)->nlbimpls = 0;
358  (*objimplics)->nubimpls = 0;
359  (*objimplics)->size = 0;
360  }
361  else
362  {
363  SCIP_VAR* var;
364  int nvars;
365  int pos;
366  int v;
367 
368  assert(objvars != NULL);
369  assert(binobjvarmap != NULL);
370  assert(collectedlbvars != NULL);
371  assert(collectedubvars != NULL);
372 
373  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*objimplics)->objvars, nlbimpls + nubimpls) );
374  (*objimplics)->size = nlbimpls + nubimpls;
375 
376  nvars = 0;
377 
378  for( v = 0; v < nlbimpls; ++v )
379  {
380  var = objvars[v];
381  assert(var != NULL);
382  assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
383 
384  assert(SCIPhashmapExists(binobjvarmap, var));
385  pos = (int)(size_t)SCIPhashmapGetImage(binobjvarmap, (void*)var);
386  assert(pos > 0);
387  assert(collectedlbvars[pos]);
388 
389  if( collectedubvars[pos] )
390  {
391  SCIP_Bool infeasible;
392  SCIP_Bool tightened;
393 
395  {
396  SCIPdebugMsg(scip, "fix variables <%s> to 1.0 due to implications\n", SCIPvarGetName(var));
397 
398  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, 1.0, FALSE, &infeasible, &tightened) );
399  maxlbobjchg -= SCIPvarGetObj(var);
400  }
401  else
402  {
403  SCIPdebugMsg(scip, "fix variables <%s> to 0.0 due to implications\n", SCIPvarGetName(var));
404 
405  SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, 0.0, FALSE, &infeasible, &tightened) );
406  maxlbobjchg += SCIPvarGetObj(var);
407  }
408  assert(!infeasible);
409  assert(tightened);
410  }
411  else
412  {
413  (*objimplics)->objvars[nvars] = var;
414  nvars++;
415  }
416  collectedlbvars[pos] = FALSE;
417  }
418  (*objimplics)->nlbimpls = nvars;
419 
420  for( v = 0; v < nubimpls; ++v )
421  {
422  var = objvars[nlbimpls + v];
423  assert(var != NULL);
424  assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
425 
426  assert(SCIPhashmapExists(binobjvarmap, var));
427  pos = (int)(size_t)SCIPhashmapGetImage(binobjvarmap, (void*)var);
428  assert(pos > 0);
429  assert(collectedubvars[pos]);
430 
431  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 )
432  {
434  maxubobjchg -= SCIPvarGetObj(var);
435  else
436  maxubobjchg += SCIPvarGetObj(var);
437  }
438  else
439  {
440  (*objimplics)->objvars[nvars] = var;
441  nvars++;
442  }
443  collectedubvars[pos] = FALSE;
444  }
445  (*objimplics)->nubimpls = nvars - (*objimplics)->nlbimpls;
446 
447  /* capture the variables */
448  for( v = 0; v < nvars; ++v )
449  {
450  assert(SCIPvarIsBinary((*objimplics)->objvars[v]));
451  assert(!SCIPisZero(scip, SCIPvarGetObj((*objimplics)->objvars[v])));
452  SCIP_CALL( SCIPcaptureVar(scip, (*objimplics)->objvars[v]) );
453  }
454  }
455 
456  (*objimplics)->maxobjchg = MAX(maxlbobjchg, maxubobjchg);
457 
458  return SCIP_OKAY;
459 }
460 
461 /** frees an objective implication data structure */
462 static
464  SCIP* scip, /**< SCIP data structure */
465  SCIP_OBJIMPLICS** objimplics /**< pointer to objective implication data structure */
466  )
467 {
468  int v;
470  assert(scip != NULL);
471  assert(objimplics != NULL);
472  assert(*objimplics != NULL);
473 
474  /* release all variables */
475  for( v = 0; v < (*objimplics)->nlbimpls + (*objimplics)->nubimpls; ++v )
476  {
477  SCIP_CALL( SCIPreleaseVar(scip, &(*objimplics)->objvars[v]) );
478  }
479 
480  /* free objective variable array */
481  SCIPfreeBlockMemoryArrayNull(scip, &(*objimplics)->objvars, (*objimplics)->size);
482 
483  /* frees block memory for the implication data structure */
484  SCIPfreeBlockMemory(scip, objimplics);
485 
486  return SCIP_OKAY;
487 }
488 
489 /** remove the given variable at the given pos from the objective implication data structure */
490 static
492  SCIP* scip, /**< SCIP data structure */
493  SCIP_OBJIMPLICS* objimplics, /**< objective implication data structure */
494  int pos /**< position */
495  )
496 {
497  assert(0 <= pos);
498  assert(pos < objimplics->nlbimpls + objimplics->nubimpls);
499 
500  SCIPdebugMsg(scip, "variable <%s> ", SCIPvarGetName(objimplics->objvars[pos]));
501 
502  /* release variable */
503  SCIP_CALL( SCIPreleaseVar(scip, &objimplics->objvars[pos]) );
504 
505  /* copy last lower bound variable to that position */
506  if( pos < objimplics->nlbimpls )
507  {
508  objimplics->nlbimpls--;
509  assert(objimplics->nlbimpls >= 0);
510 
511  /* copy last lower bound variable to that position */
512  objimplics->objvars[pos] = objimplics->objvars[objimplics->nlbimpls];
513 
514  /* copy last upper bound variable to open slot */
515  objimplics->objvars[objimplics->nlbimpls] = objimplics->objvars[objimplics->nlbimpls + objimplics->nubimpls];
516 
517  SCIPdebugMsgPrint(scip, "remove lower bound implication\n");
518  }
519  else
520  {
521  objimplics->nubimpls--;
522  assert(objimplics->nubimpls >= 0);
523 
524  /* copy last upper bound variable to that position */
525  objimplics->objvars[pos] = objimplics->objvars[objimplics->nlbimpls + objimplics->nubimpls];
526 
527  SCIPdebugMsgPrint(scip, "remove upper bound implication\n");
528  }
529 
530  return SCIP_OKAY;
531 }
532 
533 /*
534  * Local methods
535  */
536 
537 
538 /** catch bound change events if the variable has a non-zero objective coefficient to check if the maximum activity of
539  * the objective function changed
540  */
541 static
543  SCIP* scip, /**< SCIP data structure */
544  SCIP_PROPDATA* propdata, /**< propagator data */
545  SCIP_EVENTHDLR* eventhdlr, /**< event handler for global bound change events */
546  SCIP_VAR* var /**< variable for which the event should be dropped */
547  )
548 {
549  SCIP_Real objval;
550 
551  assert(propdata != NULL);
552  assert(eventhdlr != NULL);
553 
554  objval = SCIPvarGetObj(var);
555 
556  if( !SCIPisZero(scip, objval) )
557  {
558  if( objval > 0.0 )
559  {
560  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_GUBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) );
561  }
562  else
563  {
564  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_GLBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) );
565  }
566  }
567 
568  return SCIP_OKAY;
569 }
570 
571 /** drop variable event w.r.t. objective coefficient */
572 static
574  SCIP* scip, /**< SCIP data structure */
575  SCIP_PROPDATA* propdata, /**< propagator data */
576  SCIP_EVENTHDLR* eventhdlr, /**< event handler for global bound change events */
577  SCIP_VAR* var /**< variable for which the event should be dropped */
578  )
579 {
580  SCIP_Real objval;
581 
582  assert(propdata != NULL);
583  assert(eventhdlr != NULL);
584 
585  objval = SCIPvarGetObj(var);
586 
587  /* drop bound change event */
588  if( !SCIPisZero(scip, objval) )
589  {
590  if( objval > 0.0 )
591  {
592  SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_GUBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, -1) );
593  }
594  else
595  {
596  SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_GLBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, -1) );
597  }
598  }
599  return SCIP_OKAY;
600 }
601 
602 /** drop all variable events */
603 static
605  SCIP* scip, /**< SCIP data structure */
606  SCIP_PROPDATA* propdata /**< propagator data */
607  )
608 {
609  SCIP_EVENTHDLR* eventhdlr;
610  SCIP_VAR* var;
611  int k;
612 
613  assert(scip != NULL);
614  assert(propdata != NULL);
615 
616  eventhdlr = propdata->eventhdlr;
617  assert(eventhdlr != NULL);
618 
619  /* drop all events and release variables */
620  for( k = 0; k < propdata->nminactvars; ++k )
621  {
622  var = propdata->minactvars[k];
623  assert(var != NULL);
624  assert(SCIPvarIsBinary(var));
625 
626  /* drop bound relax event which is caught for all binary variables which are used for propagation the objective
627  * function via the minimum activity of the objective function
628  */
629  SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDRELAXED, eventhdlr, (SCIP_EVENTDATA*)propdata, -1) );
630 
631  /* release variable */
632  SCIP_CALL( SCIPreleaseVar(scip, &var) );
633  }
634 
635  /* release variables */
636  for( k = 0; k < propdata->nmaxactvars; ++k )
637  {
638  var = propdata->maxactvars[k];
639  assert(var != NULL);
640  assert(SCIPvarIsBinary(var));
641 
642  /* drop events which are needed for evaluating the maximum activity of the objective function */
643  SCIP_CALL( dropObjEvent(scip, propdata, eventhdlr, var) );
644 
645  /* release variable */
646  SCIP_CALL( SCIPreleaseVar(scip, &var) );
647  }
648 
649  /* drop all events and release variables */
650  for( k = 0; k < propdata->nobjintvars; ++k )
651  {
652  var = propdata->objintvars[k];
653  assert(var != NULL);
654 
655  /* drop events which are needed for evaluating the maximum activity of the objective function */
656  SCIP_CALL( dropObjEvent(scip, propdata, eventhdlr, var) );
657 
658  /* release variable */
659  SCIP_CALL( SCIPreleaseVar(scip, &var) );
660  }
661 
662  return SCIP_OKAY;
663 }
664 
665 /** reset propagatore data structure */
666 static
667 void propdataReset(
668  SCIP* scip, /**< SCIP data structure */
669  SCIP_PROPDATA* propdata /**< propagator data */
670  )
671 {
672  propdata->minactvars = NULL;
673  propdata->minactimpls = NULL;
674  propdata->maxactvars = NULL;
675  propdata->maxactchgs = NULL;
676  propdata->objintvars = NULL;
677  propdata->nminactvars = 0;
678  propdata->nmaxactvars = 0;
679  propdata->nobjintvars = 0;
680  propdata->maxpseudoobjact = SCIP_INVALID;
681  propdata->maxpseudoobjactinf = 0;
682  propdata->lastvarnum = -1;
683  propdata->glbpropagated = FALSE;
684  propdata->cutoffbound = SCIP_INVALID;
685  propdata->lastlowerbound = -SCIP_INVALID;
686  propdata->glbpseudoobjval = -SCIP_INVALID;
687  propdata->glbfirstnonfixed = 0;
688  propdata->maxactfirstnonfixed = 0;
689  propdata->firstnonfixed = 0;
690  propdata->nnewvars = 0;
691  propdata->minactsize = 0;
692  propdata->maxactsize = 0;
693  propdata->objintvarssize = 0;
694  propdata->catchvaradded = FALSE;
695  propdata->initialized = FALSE;
696 }
697 
698 /** free propagator data */
699 static
701  SCIP* scip, /**< SCIP data structure */
702  SCIP_PROPDATA* propdata /**< propagator data */
703  )
704 {
705  int v;
707  if( !propdata->initialized )
708  return SCIP_OKAY;
709 
710  if( propdata->addedvars != NULL )
711  SCIPhashtableFree(&propdata->addedvars);
712 
713  /* drop events for the variables */
714  SCIP_CALL( dropVarEvents(scip, propdata) );
715 
716  for( v = 0; v < propdata->nminactvars; ++v )
717  {
718  SCIP_CALL( objimplicsFree(scip, &(propdata->minactimpls[v])) );
719  }
720 
721  /* free memory for non-zero objective variables */
722  SCIPfreeBlockMemoryArrayNull(scip, &propdata->minactvars, propdata->minactsize);
723  SCIPfreeBlockMemoryArrayNull(scip, &propdata->minactimpls, propdata->minactsize);
724  SCIPfreeBlockMemoryArrayNull(scip, &propdata->maxactvars, propdata->maxactsize);
725  SCIPfreeBlockMemoryArrayNull(scip, &propdata->maxactchgs, propdata->maxactsize);
726  SCIPfreeBlockMemoryArrayNull(scip, &propdata->objintvars, propdata->objintvarssize);
727 
728  /* reset propagator data structure */
729  propdataReset(scip, propdata);
730 
731  return SCIP_OKAY;
732 }
733 
734 /** returns the objective change for the given binary variable */
735 static
737  SCIP_VAR* var, /**< variable to get objective change for */
738  SCIP_BOUNDTYPE boundtype, /**< bound type to consider */
739  SCIP_BOUNDTYPE bound /**< fixing bound */
740  )
741 {
742  assert(SCIPvarIsBinary(var));
743  assert((int)SCIP_BOUNDTYPE_LOWER == 0);
744  assert((int)SCIP_BOUNDTYPE_UPPER == 1);
745 
746  /* collect contribution of variable itself */
747  return (SCIP_Real)((int)bound - (int)(boundtype == SCIP_BOUNDTYPE_UPPER)) * SCIPvarGetObj(var);
748 }
749 
750 /** returns the objective change provided by the implication variable by fixing it to the given bound
751  * w.r.t. minimum activity of the objective function; additionally it collects all contributors for that objective
752  * change;
753  */
754 static
756  SCIP* scip, /**< SCIP data structure */
757  SCIP_VAR* var, /**< variable to computes the objective contribution */
758  SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
759  SCIP_Bool* collectedvars, /**< temporary buffer to mark collected variables */
760  int nbinobjvars, /**< number of binary variables with non-zero objective coefficient */
761  SCIP_VAR** contributors, /**< array to store the contributors */
762  int* ncontributors /**< pointer to store number of contributor to the objective contribution */
763  )
764 {
765  SCIP_Real objval;
766  int pos;
767 
768  assert(scip != NULL);
769  assert(var != NULL);
770  assert(binobjvarmap != NULL);
771  assert(collectedvars != NULL);
772  assert(contributors != NULL);
773  assert(ncontributors != NULL);
774 
775  /* ignore global fixed variables */
776  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 )
777  return 0.0;
778 
779  objval = SCIPvarGetObj(var);
780 
781  /* ignore variables with zero objective coefficient */
782  if( SCIPisZero(scip, objval) )
783  return 0.0;
784 
785  assert(SCIPhashmapExists(binobjvarmap, var));
786  pos = (int)(size_t)SCIPhashmapGetImage(binobjvarmap, var);
787  assert(pos > 0);
788 
789  /* check if the variables was already collected through other cliques */
790  if( collectedvars[pos] )
791  return 0.0;
792 
793  /* collect variable */
794  assert(*ncontributors < nbinobjvars);
795  contributors[*ncontributors] = var;
796  (*ncontributors)++;
797 
798  /* mark variable to be collected */
799  collectedvars[pos] = TRUE;
800 
801  /* return the absolute value of the objective coefficient as constriction */
802  return REALABS(objval);
803 }
804 
805 #define MAX_CLIQUELENGTH 50
806 /** returns the objective change provided by the implications of the given variable by fixing it to the given bound
807  * w.r.t. minimum activity of the objective function; additionally it collects all contributors for that objective
808  * change;
809  *
810  * Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to
811  * fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by the
812  * implications are:
813  *
814  * \f[
815  * \displaystyle
816  * sum_{x\in I(1)} (1 - \mbox{bestbound}(x)) \cdot \mbox{objval}(x) - sum_{x\in I(1)} \mbox{bestbound}(x) \cdot \mbox{objval}(x)
817  * =
818  * sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{bestbound}(x)) \cdot \mbox{objval}(x)
819  * \f]
820  */
821 static
823  SCIP* scip, /**< SCIP data structure */
824  SCIP_VAR* var, /**< variable to computes the objective contribution */
825  SCIP_BOUNDTYPE bound, /**< bound to check for */
826  SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
827  SCIP_Bool* collectedvars, /**< temporary buffer to mark collected variables */
828  int nbinobjvars, /**< number of binary variables with non-zero objective coefficient */
829  SCIP_VAR** contributors, /**< array to store the contributors */
830  SCIP_HASHTABLE* uselesscliques, /**< hash table to store useless cliques, or NULL */
831  int* ncontributors, /**< pointer to store number of contributor to the objective contribution */
832  SCIP_Real* objchg /**< pointer to store the objective change */
833  )
834 {
835  SCIP_CLIQUE** cliques;
836  SCIP_CLIQUE* clique;
837  SCIP_VAR** vars;
838  SCIP_VAR* implvar;
839  SCIP_Bool* values;
840  SCIP_Bool varfixing;
841  int nbinvars;
842  int ncliques;
843  int c;
844  int v;
845 
846  assert(SCIPvarIsBinary(var));
847  assert(SCIPvarGetLbGlobal(var) < 0.5);
848  assert(SCIPvarGetUbGlobal(var) > 0.5);
849  assert(bound == SCIP_BOUNDTYPE_LOWER || bound == SCIP_BOUNDTYPE_UPPER);
850  assert(objchg != NULL);
851  assert(contributors != NULL);
852  assert(ncontributors != NULL);
853  assert(*ncontributors == 0);
854 
856  assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);
857  varfixing = (SCIP_Bool)bound;
858 
859  cliques = SCIPvarGetCliques(var, varfixing);
860  ncliques = SCIPvarGetNCliques(var, varfixing);
861 
862 #ifndef NDEBUG
863  /* check that the marker array is reset */
864  for( c = 0; c < nbinobjvars; ++c )
865  assert(collectedvars[c] == FALSE);
866 #endif
867 
868  /* collect all implication which are given via cliques */
869  for( c = 0; c < ncliques; ++c )
870  {
871  SCIP_Bool useless;
872 
873  assert(uselesscliques != NULL);
874 
875  clique = cliques[c];
876  assert(clique != NULL);
877 
878  /* check if the clique was previously detected to be useless with respect to minimum activity */
879  if( SCIPhashtableExists(uselesscliques, (void*)clique) )
880  continue;
881 
882  nbinvars = SCIPcliqueGetNVars(clique);
883 
884  if( nbinvars > MAX_CLIQUELENGTH )
885  {
886  SCIP_CALL( SCIPhashtableInsert(uselesscliques, (void*)clique) );
887  continue;
888  }
889 
890  vars = SCIPcliqueGetVars(clique);
891  values = SCIPcliqueGetValues(clique);
892  useless = TRUE;
893 
894  for( v = 0; v < nbinvars; ++v )
895  {
896  implvar = vars[v];
897  assert(implvar != NULL);
898 
899  if( implvar == var )
900  {
901  /* check if the clique is useful at all */
902  if( useless )
903  {
904  SCIP_Real objval;
905 
906  objval = SCIPvarGetObj(var);
907 
908  if( varfixing == (SCIP_Bool)SCIPvarGetBestBoundType(var) && !SCIPisZero(scip, objval) )
909  useless = FALSE;
910  }
911  }
912  else if( values[v] == (SCIP_Bool)SCIPvarGetBestBoundType(implvar) )
913  {
914  useless = FALSE;
915  (*objchg) += collectMinactImplicVar(scip, implvar, binobjvarmap, collectedvars, nbinobjvars, contributors, ncontributors);
916  }
917  }
918 
919  /* if the clique is useless store it in the hash table to skip it later */
920  if( useless )
921  {
922  assert(!SCIPhashtableExists(uselesscliques, (void*)clique));
923  SCIP_CALL( SCIPhashtableInsert(uselesscliques, (void*)clique) );
924  }
925  }
926 
927  return SCIP_OKAY;
928 }
929 
930 /** returns the objective change provided by the implications of the given variable by fixing it to the given bound
931  * w.r.t. minimum activity of the objective function
932  *
933  * Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to
934  * fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by the
935  * implications are:
936  *
937  * \f[
938  * \displaystyle
939  * sum_{x\in I(1)} (1 - \mbox{bestbound}(x)) \cdot \mbox{objval}(x) - sum_{x\in I(1)} \mbox{bestbound}(x) \cdot \mbox{objval}(x)
940  * =
941  * sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{bestbound}(x)) \cdot \mbox{objval}(x)
942  * \f]
943  *
944  * This can be done w.r.t. global variable bounds (local == FALSE), w.r.t. local variable bounds (local == TRUE &&
945  * bdchgidx == NULL), and w.r.t. given time stamp (local == TRUE && bdchgidx != NULL)
946  */
947 static
949  SCIP* scip, /**< SCIP data structure */
950  SCIP_VAR* var, /**< variable to computes the objective contribution */
951  SCIP_OBJIMPLICS* objimplics, /**< objective implication data for the given variable */
952  SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, or NULL */
953  SCIP_BOUNDTYPE bound, /**< bound to check for */
954  SCIP_Bool local, /**< propagate local bounds, otherwise global bounds */
955  SCIP_Real* objchg /**< pointer to store the objective change */
956  )
957 {
958  SCIP_VAR* implvar;
959  SCIP_Bool lb;
960  SCIP_Bool ub;
961  int nbinvars;
962  int v;
963 
964  assert(SCIPvarIsBinary(var));
965  assert(!local || SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE) < 0.5);
966  assert(!local || SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE) > 0.5);
967  assert(SCIPvarGetLbGlobal(var) < 0.5);
968  assert(SCIPvarGetUbGlobal(var) > 0.5);
969  assert(bound == SCIP_BOUNDTYPE_LOWER || bound == SCIP_BOUNDTYPE_UPPER);
970 
971  if( bound == SCIP_BOUNDTYPE_LOWER )
972  {
973  v = 0;
974  nbinvars = objimplics->nlbimpls;
975  }
976  else
977  {
978  assert(bound == SCIP_BOUNDTYPE_UPPER);
979  v = objimplics->nlbimpls;
980  nbinvars = objimplics->nlbimpls + objimplics->nubimpls;
981  }
982 
983  /* loop over all implications */
984  while( v < nbinvars )
985  {
986  implvar = objimplics->objvars[v];
987  assert(implvar != NULL);
988  assert(!SCIPisZero(scip, SCIPvarGetObj(implvar)));
989 
990  if( local )
991  {
992  lb = SCIPgetVarLbAtIndex(scip, implvar, bdchgidx, FALSE) > 0.5;
993  ub = SCIPgetVarUbAtIndex(scip, implvar, bdchgidx, FALSE) > 0.5;
994 
995  /* check if variable is fixed */
996  if( lb == TRUE || ub == FALSE )
997  {
998  v++;
999  continue;
1000  }
1001  }
1002  else
1003  {
1004  lb = SCIPvarGetLbGlobal(implvar) > 0.5;
1005  ub = SCIPvarGetUbGlobal(implvar) > 0.5;
1006 
1007  /* check if variable is global fixed; if so remove it from the objective implication data structure and
1008  * continue with the next candidate
1009  */
1010  if( lb == TRUE || ub == FALSE )
1011  {
1012  SCIP_CALL( objimplicsDelPos(scip, objimplics, v) );
1013  nbinvars--;
1014  continue;
1015  }
1016  }
1017 
1018  assert(SCIPvarGetObj(implvar) > 0.0 || SCIPvarsHaveCommonClique(var, (SCIP_Bool) bound, implvar, TRUE, TRUE));
1019  assert(SCIPvarGetObj(implvar) < 0.0 || SCIPvarsHaveCommonClique(var, (SCIP_Bool) bound, implvar, FALSE, TRUE));
1020 
1021  /* add objective change */
1022  (*objchg) += REALABS(SCIPvarGetObj(implvar));
1023  v++;
1024  }
1025 
1026  return SCIP_OKAY;
1027 }
1028 
1029 /** computes for the given binary variable the objective contribution by fixing it to given bound w.r.t. minimum
1030  * activity of the objective function; additionally it collects all contributors for that objective change;
1031  */
1032 static
1034  SCIP* scip, /**< SCIP data structure */
1035  SCIP_VAR* var, /**< variable to computes the objective contribution */
1036  SCIP_BOUNDTYPE bound, /**< bound to check for */
1037  SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
1038  SCIP_Bool* collectedvars, /**< temporary buffer to mark collected variables */
1039  int nbinobjvars, /**< number of binary variables with non-zero objective coefficient */
1040  SCIP_VAR** contributors, /**< array to store the contriboters */
1041  SCIP_HASHTABLE* uselesscliques, /**< hash table to store useless cliques, or NULL */
1042  int* ncontributors, /**< pointer to store number of contributor to the objective contribution */
1043  SCIP_Real* objchg /**< pointer to store the objective change */
1044  )
1045 {
1046  assert(SCIPvarIsBinary(var));
1047  assert(contributors != NULL);
1048  assert(ncontributors != NULL);
1049 
1050  /* collects the contribution of the variable itself w.r.t. the best bound */
1051  (*objchg) = getVarObjchg(var, SCIPvarGetBestBoundType(var), bound);
1052 
1053  (*ncontributors) = 0;
1054 
1055  /* add the objective contribution from the implication variable */
1056  SCIP_CALL( collectMinactImplicVars(scip, var, bound, binobjvarmap, collectedvars, nbinobjvars, contributors, uselesscliques, ncontributors, objchg) );
1057 
1058  return SCIP_OKAY;
1059 }
1060 
1061 /** computes for the given binary variable the objective contribution by fixing it to given bound w.r.t. minimum
1062  * activity of the objective function; this can be done w.r.t. global variable bounds (local == FALSE), w.r.t. local
1063  * variable bounds (local == TRUE && bdchgidx == NULL), and w.r.t. given time stamp (local == TRUE && bdchgidx != NULL)
1064  */
1065 static
1067  SCIP* scip, /**< SCIP data structure */
1068  SCIP_VAR* var, /**< variable to computes the objective contribution */
1069  SCIP_OBJIMPLICS* objimplics, /**< objective implication data for the given variable */
1070  SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, or NULL */
1071  SCIP_BOUNDTYPE bound, /**< bound to check for */
1072  SCIP_Bool local, /**< propagate local bounds, otherwise global bounds */
1073  SCIP_Real* objchg /**< pointer to store the objective change */
1074  )
1075 {
1076  assert(SCIPvarIsBinary(var));
1077 
1078  /* collects the contribution of the variable itself w.r.t. the best bound */
1079  (*objchg) = getVarObjchg(var, SCIPvarGetBestBoundType(var), bound);
1080 
1081  /* add the objective contribution from the implication variable */
1082  SCIP_CALL( getMinactImplicObjchg(scip, var, objimplics, bdchgidx, bound, local, objchg) );
1083 
1084  return SCIP_OKAY;
1085 }
1086 
1087 /** returns the global (that means w.r.t. global bounds of the variables) objective change provided by all cliques of
1088  * the given variable by fixing it to the given bound w.r.t. maximum activity of the objective function
1089  *
1090  * Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to
1091  * fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by these
1092  * implications are:
1093  *
1094  * \f[
1095  * \displaystyle
1096  * sum_{x\in I(1)} (1 - \mbox{worstbound}(x)) \cdot \mbox{objval}(x) - sum_{x\in I(1)} \mbox{worst}(x) \cdot \mbox{objval}(x)
1097  * =
1098  * sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{worstbound}(x)) \cdot \mbox{objval}(x)
1099  * \f]
1100  */
1101 static
1103  SCIP* scip, /**< SCIP data structure */
1104  SCIP_VAR* var, /**< variable to computes the objective contribution */
1105  SCIP_BOUNDTYPE bound, /**< bound to check for */
1106  SCIP_Real* objchg /**< pointer to store the objective change */
1107  )
1109  SCIP_Bool varfixing;
1110  int ncliques;
1111  int nvars;
1112 
1113  assert(scip != NULL);
1114  assert(SCIPvarIsBinary(var));
1115  assert(SCIPvarGetLbGlobal(var) < 0.5);
1116  assert(SCIPvarGetUbGlobal(var) > 0.5);
1117  assert(bound == SCIP_BOUNDTYPE_LOWER || bound == SCIP_BOUNDTYPE_UPPER);
1118  assert(objchg != NULL);
1119 
1120  varfixing = (SCIP_Bool)bound;
1121  assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE);
1122  assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);
1123 
1124  *objchg = 0.0;
1125  ncliques = SCIPvarGetNCliques(var, varfixing);
1126 
1127  if( ncliques > 0 )
1128  {
1129  SCIP_CLIQUE** cliques;
1130  SCIP_CLIQUE* clique;
1131  SCIP_VAR** clqvars;
1132  SCIP_VAR** probvars;
1133  SCIP_VAR* clqvar;
1134  SCIP_Bool* clqvalues;
1135  int* entries;
1136  int* ids;
1137  SCIP_Real obj;
1138  int nclqvars;
1139  int nentries;
1140  int objmult;
1141  int nids;
1142  int id;
1143  int c;
1144  int v;
1145 
1146  assert(SCIPisTransformed(scip));
1147 
1148  nentries = SCIPgetNVars(scip) - SCIPgetNContVars(scip) + 1;
1149 
1150  SCIP_CALL( SCIPallocBufferArray(scip, &ids, 2*nentries) );
1151  nids = 0;
1152  /* @todo move this memory allocation to SCIP_SET and add a memory list there, to decrease the number of
1153  * allocations and clear ups
1154  */
1155  SCIP_CALL( SCIPallocBufferArray(scip, &entries, nentries) );
1156  BMSclearMemoryArray(entries, nentries);
1157 
1158  cliques = SCIPvarGetCliques(var, varfixing);
1159  assert(cliques != NULL);
1160 
1161  /* iterate over all cliques and determine all importantimplications */
1162  for( c = ncliques - 1; c >= 0; --c )
1163  {
1164  clique = cliques[c];
1165  clqvars = SCIPcliqueGetVars(clique);
1166  clqvalues = SCIPcliqueGetValues(clique);
1167  nclqvars = SCIPcliqueGetNVars(clique);
1168  assert(nclqvars > 0);
1169  assert(clqvars != NULL);
1170  assert(clqvalues != NULL);
1171 
1172  if( nclqvars > MAX_CLIQUELENGTH )
1173  continue;
1174 
1175  /* iterate over all clique variables */
1176  for( v = nclqvars - 1; v >= 0; --v )
1177  {
1178  clqvar = clqvars[v];
1179  assert(clqvar != NULL);
1180 
1181  objmult = (int)!clqvalues[v] - (int)SCIPvarGetWorstBoundType(clqvar);
1182  assert(-1 <= objmult && objmult <= 1);
1183 
1184  /* ignore binary variable which are either fixed and were the objective contribution will not be zero */
1185  if( clqvar != var && objmult != 0 && SCIPvarIsActive(clqvar) &&
1186  (SCIPvarGetLbGlobal(clqvar) < 0.5 && SCIPvarGetUbGlobal(clqvar) > 0.5) && !SCIPisZero(scip, SCIPvarGetObj(clqvar)) )
1187  {
1188  int probindex = SCIPvarGetProbindex(clqvar) + 1;
1189  assert(0 < probindex && probindex < nentries);
1190 
1191  /* check that the variable was not yet visited */
1192  assert(entries[probindex] == 0 || entries[probindex] == objmult);
1193  if( entries[probindex] == 0 )
1194  {
1195  /* memorize probindex */
1196  ids[nids] = probindex;
1197  ++nids;
1198 
1199  assert(ABS(objmult) == 1);
1200 
1201  /* mark variable as visited */
1202  entries[probindex] = objmult;
1203  }
1204  }
1205  }
1206  }
1207 
1208  probvars = SCIPgetVars(scip);
1209  assert(probvars != NULL);
1210 
1211  /* add all implied objective values */
1212  for( v = nids - 1; v >= 0; --v )
1213  {
1214  id = ids[v];
1215  assert(0 < id && id < nentries);
1216  assert(entries[id] != 0);
1217 
1218  clqvar = probvars[id - 1];
1219  assert(clqvar != NULL);
1220  assert(SCIPvarIsBinary(clqvar));
1221  assert(SCIPvarIsActive(clqvar));
1222  assert(SCIPvarGetLbGlobal(clqvar) < 0.5);
1223  assert(SCIPvarGetUbGlobal(clqvar) > 0.5);
1224 
1225  obj = SCIPvarGetObj(clqvar);
1226  assert(!SCIPisZero(scip, obj));
1227 
1228  *objchg += entries[id] * obj;
1229  }
1230 
1231  /* free temporary memory */
1232  SCIPfreeBufferArray(scip, &entries);
1233  SCIPfreeBufferArray(scip, &ids);
1234  }
1235 
1236 #ifdef SCIP_MORE_DEBUG
1237  SCIPdebugMsg(scip, "objective contribution when variable <%s> fixed to %u using cliques is %g\n", SCIPvarGetName(var),
1238  varfixing, *objchg);
1239 #endif
1240 
1241  /* collect non-binary implication information */
1242  nvars = SCIPvarGetNImpls(var, varfixing);
1243 
1244  if( nvars > 0 )
1245  {
1246  SCIP_VAR** vars;
1247  SCIP_VAR* implvar;
1248  SCIP_Real* bounds;
1249  SCIP_BOUNDTYPE* boundtypes;
1250  SCIP_Real obj;
1251  SCIP_Real lb;
1252  SCIP_Real ub;
1253  int v;
1254 
1255  vars = SCIPvarGetImplVars(var, varfixing);
1256  boundtypes = SCIPvarGetImplTypes(var, varfixing);
1257  bounds = SCIPvarGetImplBounds(var, varfixing);
1258 
1259  for( v = nvars - 1; v >= 0; --v )
1260  {
1261  implvar = vars[v];
1262  assert(implvar != NULL);
1263 
1264  lb = SCIPvarGetLbLocal(implvar);
1265  ub = SCIPvarGetUbLocal(implvar);
1266  obj = SCIPvarGetObj(implvar);
1267 
1268  /* ignore binary variable which are fixed or not of column status */
1269  if( SCIPisZero(scip, obj) )
1270  continue;
1271 
1272  /* add up objective change if applicable */
1273  if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER && SCIPvarGetWorstBoundType(implvar) == SCIP_BOUNDTYPE_LOWER && SCIPisFeasGT(scip, bounds[v], lb) )
1274  *objchg += (bounds[v] - lb)*obj;
1275  else if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER && SCIPvarGetWorstBoundType(implvar) == SCIP_BOUNDTYPE_UPPER && SCIPisFeasLT(scip, bounds[v], ub) )
1276  *objchg += (bounds[v] - ub)*obj;
1277  }
1278  }
1279 
1280 #ifdef SCIP_MORE_DEBUG
1281  SCIPdebugMsg(scip, "objective contribution when variable <%s> fixed to %u using cliques and implications is %g\n", SCIPvarGetName(var),
1282  varfixing, *objchg);
1283 #endif
1284 
1285  return SCIP_OKAY;
1286 }
1287 
1288 /** computes for the given binary variable the gloabl (that means w.r.t. global bounds of the variables) objective
1289  * contribution by fixing it to given bound w.r.t. maximum activity of the objective function
1290  */
1291 static
1293  SCIP* scip, /**< SCIP data structure */
1294  SCIP_VAR* var, /**< variable to computes the objective contribution */
1295  SCIP_BOUNDTYPE bound, /**< bound to check for */
1296  SCIP_Bool useimplics, /**< should implications be used */
1297  SCIP_Real* objchg /**< pointer to store the objective change */
1298  )
1299 {
1300  assert(scip != NULL);
1301  assert(SCIPvarIsBinary(var));
1302  assert(objchg != NULL);
1303 
1304  *objchg = 0;
1305 
1306  /* check if the implications should be used to increase the objective contribution for given variable */
1307  if( useimplics )
1308  {
1309  /* using cliques and @todo other implications */
1310  SCIP_CALL( getMaxactImplicObjchg(scip, var, bound, objchg) );
1311  }
1312 
1313  /* collects the contribution of the variable itself w.r.t. the worst bound */
1314  *objchg += getVarObjchg(var, SCIPvarGetWorstBoundType(var), bound);
1315 
1316  return SCIP_OKAY;
1317 }
1318 
1319 /** reset variables array which marks variables which are collected */
1320 static
1321 void resetContributors(
1322  SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
1323  SCIP_Bool* collectedvars, /**< temporary buffer to mark collected variables which should be reset */
1324  SCIP_VAR** contributors, /**< temporary buffer to use for collecting contributors */
1325  int ncontributors /**< number of contributors */
1326  )
1328  SCIP_VAR* var;
1329  int pos;
1330  int c;
1331 
1332  for( c = 0; c < ncontributors; ++c )
1333  {
1334  var = contributors[c];
1335  assert(var != NULL);
1336 
1337  assert(SCIPhashmapExists(binobjvarmap, var));
1338  pos = (int)(size_t)SCIPhashmapGetImage(binobjvarmap, var);
1339  assert(pos > 0);
1340  collectedvars[pos] = FALSE;
1341  }
1342 }
1343 
1344 /** check if the given variable should be collected for the minimum activity propagation */
1345 static
1347  SCIP* scip, /**< SCIP data structure */
1348  SCIP_VAR* var, /**< variable to check */
1349  SCIP_OBJIMPLICS** objimplics, /**< pointer to store the objective implication data structure w.r.t. minimum activity */
1350  SCIP_Bool useimplics, /**< should implications be used */
1351  SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
1352  SCIP_Bool* collectedlbvars, /**< temporary buffer to mark collected variables for lower bound fixing */
1353  SCIP_Bool* collectedubvars, /**< temporary buffer to mark collected variables for upper bound fixing */
1354  int nbinobjvars, /**< number of binary variables with non-zero objective coefficient */
1355  SCIP_VAR** contributors, /**< temporary buffer to use for collecting contributors */
1356  SCIP_HASHTABLE* uselesscliques, /**< hash table to store useless cliques, or NULL */
1357  SCIP_Bool* collect /**< pointer to store if the variable should be stored */
1358  )
1359 {
1360  SCIP_Real lbobjchg;
1361  SCIP_Real ubobjchg;
1362  SCIP_Real objval;
1363  int nlbcliques;
1364  int nubcliques;
1365 
1366  assert(objimplics != NULL);
1367 
1368  objval = SCIPvarGetObj(var);
1369  (*objimplics) = NULL;
1370 
1371  if( SCIPisZero(scip, objval) )
1372  (*collect) = FALSE;
1373  else
1374  (*collect) = TRUE;
1375 
1376  nlbcliques = SCIPvarGetNCliques(var, FALSE);
1377  nubcliques = SCIPvarGetNCliques(var, TRUE);
1378 
1379  /* check if implications should be used and if implications are existing */
1380  if( useimplics && nlbcliques + nubcliques > 0 )
1381  {
1382  int nlbcontributors;
1383  int nubcontributors;
1384 
1385  assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE);
1386  assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);
1387 
1388  /* get contribution of variable by fixing it to its lower bound w.r.t. minimum activity of the objective function */
1389  SCIP_CALL( collectMinactObjchg(scip, var, SCIP_BOUNDTYPE_LOWER, binobjvarmap, collectedlbvars, nbinobjvars,
1390  contributors, uselesscliques, &nlbcontributors, &lbobjchg) );
1391  assert(!SCIPisNegative(scip, lbobjchg));
1392 
1393  SCIPdebugMsg(scip, "variable <%s> fixed to bound=%d implies %d(%d)\n", SCIPvarGetName(var),
1394  SCIP_BOUNDTYPE_LOWER, 0, nlbcontributors);
1395 
1396  /* ignore implications if the variable has a zero objective coefficient and implications only one variable, since
1397  * this is covered by that implied variable
1398  */
1399  if( !(*collect) && nlbcontributors == 1 )
1400  {
1401  /* reset lower bound contributors */
1402  resetContributors(binobjvarmap, collectedlbvars, contributors, nlbcontributors);
1403 
1404  assert(SCIPisZero(scip, objval));
1405  nlbcontributors = 0;
1406  }
1407 
1408  /* get contribution of variable by fixing it to its upper bound w.r.t. minimum activity of the objective function */
1409  SCIP_CALL( collectMinactObjchg(scip, var, SCIP_BOUNDTYPE_UPPER, binobjvarmap, collectedubvars, nbinobjvars,
1410  &contributors[nlbcontributors], uselesscliques, &nubcontributors, &ubobjchg) );
1411  assert(!SCIPisNegative(scip, ubobjchg));
1412 
1413  SCIPdebugMsg(scip, "variable <%s> fixed to bound=%d implies %d(%d)\n", SCIPvarGetName(var),
1414  SCIP_BOUNDTYPE_UPPER, 0, nubcontributors);
1415 
1416  /* ignore implications if the variable has a zero objective coefficient and implications only one variable, since
1417  * this is covered by that implied variable
1418  */
1419  if( !(*collect) && nubcontributors == 1 )
1420  {
1421  /* reset upper bound contributors */
1422  resetContributors(binobjvarmap, collectedubvars, &contributors[nlbcontributors], nubcontributors);
1423 
1424  assert(SCIPisZero(scip, objval));
1425  nubcontributors = 0;
1426  }
1427 
1428  if( (*collect) || nlbcontributors > 1 || nubcontributors > 1 )
1429  {
1430  /* creates an objective implication data structure, fixes (globally) variables which are implied by lower and upper
1431  * bound fixing, and clears the collected arrays for lower and upper bound
1432  */
1433  SCIP_CALL( objimplicsCreate(scip, objimplics, contributors, binobjvarmap, collectedlbvars, collectedubvars, lbobjchg, ubobjchg, nlbcontributors, nubcontributors) );
1434  (*collect) = TRUE;
1435  }
1436  else
1437  {
1438  /* reset lower bound contributors */
1439  resetContributors(binobjvarmap, collectedlbvars, contributors, nlbcontributors);
1440 
1441  /* reset upper bound contributors */
1442  resetContributors(binobjvarmap, collectedubvars, &contributors[nlbcontributors], nubcontributors);
1443  }
1444  }
1445  else if( (*collect) )
1446  {
1449  assert(!SCIPisZero(scip, lbobjchg) || !SCIPisZero(scip, ubobjchg));
1450  assert(!SCIPisNegative(scip, lbobjchg));
1451  assert(!SCIPisNegative(scip, ubobjchg));
1452 
1453  /* creates an "empty" objective implication data structure */
1454  SCIP_CALL( objimplicsCreate(scip, objimplics, NULL, NULL, NULL, NULL, lbobjchg, ubobjchg, 0, 0) );
1455  }
1456 
1457  return SCIP_OKAY;
1458 }
1459 
1460 /** check if the given variable should be collected for the maximum activity propagation */
1461 static
1463  SCIP* scip, /**< SCIP data structure */
1464  SCIP_VAR* var, /**< variable to check */
1465  SCIP_Bool useimplics, /**< should implications be used */
1466  SCIP_Real* objchg, /**< pointer to store the objective change w.r.t. maximum activity */
1467  SCIP_Bool* isnotzero /**< pointer to store if the objective change is unequal to zero or not */
1468  )
1469 {
1470  SCIP_Real lbobjchg;
1471  SCIP_Real ubobjchg;
1472 
1473  assert(scip != NULL);
1474  assert(SCIPvarIsBinary(var));
1475  assert(objchg != NULL);
1476  assert(isnotzero != NULL);
1477 
1478  /* get contribution of variable by fixing it to its lower bound w.r.t. maximum activity of the objective function */
1479  SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_LOWER, useimplics, &lbobjchg) );
1480  assert(!SCIPisPositive(scip, lbobjchg));
1481 
1482  /* get contribution of variable by fixing it to its upper bound w.r.t. maximum activity of the objective function */
1483  SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_UPPER, useimplics, &ubobjchg) );
1484  assert(!SCIPisPositive(scip, ubobjchg));
1485 
1486  (*objchg) = MIN(lbobjchg, ubobjchg);
1487 
1488  /* only consider variables with non-zero objective contribution */
1489  if( SCIPisZero(scip, (*objchg)) )
1490  *isnotzero = FALSE;
1491  else
1492  *isnotzero = TRUE;
1493 
1494  return SCIP_OKAY;
1495 }
1496 
1497 /** initializate the propagator */
1498 static
1500  SCIP* scip, /**< SCIP data structure */
1501  SCIP_PROPDATA* propdata /**< propagator data */
1502  )
1503 {
1504  SCIP_VAR** vars;
1505  SCIP_VAR* var;
1506  SCIP_HASHMAP* binobjvarmap;
1507  int nvars;
1508  int nbinvars;
1509  int nintvars;
1510  int nminactvars;
1511  int nmaxactvars;
1512  int nobjintvars;
1513  int nobjcontvars;
1514  int nobjvars;
1515  int nbinobjvars;
1516  int v;
1517 
1518  assert(scip != NULL);
1519  assert(propdata != NULL);
1520 
1521  /* get problem variables */
1522  vars = SCIPgetVars(scip);
1523  nvars = SCIPgetNVars(scip);
1524  nintvars = nvars - SCIPgetNContVars(scip);
1525 
1526  nbinvars = 0;
1527  nobjvars = 0;
1528  nbinobjvars = 0;
1529 
1530  SCIP_CALL( SCIPhashmapCreate(&binobjvarmap, SCIPblkmem(scip), SCIPgetNObjVars(scip)) );
1531 
1532  /* count and collect variable problem indices of variables with non-zero objective coefficient */
1533  for( v = 0; v < nvars; ++v )
1534  {
1535  var = vars[v];
1536  assert(var != NULL);
1537 
1538  if( !SCIPisZero(scip, SCIPvarGetObj(var)) )
1539  {
1540  nobjvars++;
1541 
1542  if( SCIPvarIsBinary(var) )
1543  {
1544  SCIP_CALL( SCIPhashmapInsert(binobjvarmap, (void*)var, (void*)(size_t)(nbinobjvars + 1)) );
1545  nbinobjvars++;
1546  }
1547  }
1548 
1549  if( SCIPvarIsBinary(var) )
1550  nbinvars++;
1551  }
1552 
1553  nminactvars = 0;
1554  nmaxactvars = 0;
1555  nobjintvars = 0;
1556  nobjcontvars = 0;
1557 
1558  if( nobjvars > 0 )
1559  {
1560  SCIP_EVENTHDLR* eventhdlr;
1561  SCIP_OBJIMPLICS* objimplics;
1562  SCIP_HASHTABLE* uselesscliques;
1563  SCIP_VAR** contributors;
1564  SCIP_Bool* collectedlbvars;
1565  SCIP_Bool* collectedubvars;
1566  SCIP_Bool collect;
1567  SCIP_Bool useimplics;
1568  SCIP_Real objval;
1569  SCIP_Real objchg;
1570 
1571  eventhdlr = propdata->eventhdlr;
1572  assert(eventhdlr != NULL);
1573 
1574  useimplics = (propdata->propuseimplics && nbinobjvars < propdata->maximplvars);
1575 
1576  /* allocate memory for all arrays */
1577  propdata->minactsize = nbinvars;
1578  propdata->maxactsize = nbinvars;
1579  propdata->objintvarssize = nobjvars - nbinobjvars;
1580  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->minactvars, propdata->minactsize) );
1581  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->minactimpls, propdata->minactsize) );
1582  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->maxactvars, propdata->maxactsize) );
1583  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->maxactchgs, propdata->maxactsize) );
1584  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->objintvars, propdata->objintvarssize) );
1585 
1586  if( useimplics )
1587  {
1588  int ncliques;
1589 
1590  /* create temporary buffer */
1591  /* we store both lb and ub contributors in array contributors, and both could be nbinobjvars, we need twice that size */
1592  SCIP_CALL( SCIPallocBufferArray(scip, &contributors, 2 * nbinobjvars) );
1593  /* @todo: use SCIPallocCleanBufferArray instead? */
1594  SCIP_CALL( SCIPallocClearBufferArray(scip, &collectedlbvars, nbinobjvars+1) );
1595  /* @todo: use SCIPallocCleanBufferArray instead? */
1596  SCIP_CALL( SCIPallocClearBufferArray(scip, &collectedubvars, nbinobjvars+1) );
1597 
1598  ncliques = SCIPgetNCliques(scip);
1599 
1600  if( ncliques > 0 )
1601  {
1602  SCIP_CALL( SCIPhashtableCreate(&uselesscliques, SCIPblkmem(scip), ncliques,
1603  cliqueGetHashkey, cliqueIsHashkeyEq, cliqueGetHashkeyVal, NULL) );
1604  }
1605  else
1606  uselesscliques = NULL;
1607  }
1608  else
1609  {
1610  contributors = NULL;
1611  collectedlbvars = NULL;
1612  collectedubvars = NULL;
1613  uselesscliques = NULL;
1614  }
1615 
1616  /* collect the variables with non-zero objective contribution and catch global bound tighten events that decrease the
1617  * maximal pseudo objective activity
1618  */
1619  for( v = 0; v < nvars && (nobjintvars == 0 || nobjintvars < propdata->objintvarssize); ++v )
1620  {
1621  var = vars[v];
1622  assert(var != NULL);
1623 
1624  objval = SCIPvarGetObj(var);
1625 
1626  if( SCIPvarIsBinary(var) )
1627  {
1628  /* ignore variables which are globally fixed */
1629  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 )
1630  {
1631 #ifndef NDEBUG
1632  /* check that the binary implications are applied for binary variables which are globally fixed */
1633  checkImplicsApplied(scip, var);
1634 #endif
1635  continue;
1636  }
1637 
1638  /* check if the variable should be collected for the minimum activity propagation */
1639  SCIP_CALL( collectMinactVar(scip, var, &objimplics, useimplics, binobjvarmap, collectedlbvars, collectedubvars,
1640  nbinobjvars, contributors, uselesscliques, &collect) );
1641 
1642  if( collect )
1643  {
1644  assert(nminactvars < nbinvars);
1645  assert(objimplics != NULL);
1646  assert(objimplics->nlbimpls + objimplics->nubimpls <= nbinobjvars);
1647 
1648  /* collect the binary variable with non-zero objective contribution */
1649  propdata->minactvars[nminactvars] = var;
1650  propdata->minactimpls[nminactvars] = objimplics;
1651  nminactvars++;
1652 
1653  /* catch bound relax event for the binary variable to handel the firstnonfixed index correctly */
1654  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDRELAXED, eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) );
1655 
1656  SCIPdebugMsg(scip, "variable <%s>[obj: <%g>] implicit objective change %g\n",
1657  SCIPvarGetName(var), objval, objimplics->maxobjchg);
1658 
1659  /* captures the variable */
1660  SCIP_CALL( SCIPcaptureVar(scip, var) ) ;
1661  }
1662  /* check if the variable should be collected for the maximum activity propagation */
1663  SCIP_CALL( collectMaxactVar(scip, var, useimplics, &objchg, &collect) );
1664 
1665  if( collect )
1666  {
1667  assert(nmaxactvars < nbinvars);
1668 
1669  /* collect the binary variable with non-zero objective contribution */
1670  propdata->maxactvars[nmaxactvars] = var;
1671  propdata->maxactchgs[nmaxactvars] = -objchg;
1672  nmaxactvars++;
1673 
1674  /* catch bound change events if the variable has a non-zero objective coefficient to check if the maximum
1675  * activity of the objective function changed
1676  */
1677  SCIP_CALL( catchObjEvent(scip, propdata, eventhdlr, var) );
1678 
1679  /* captures the variable */
1680  SCIP_CALL( SCIPcaptureVar(scip, var) ) ;
1681  }
1682  }
1683  else
1684  {
1685  /* only consider non-binary variables with a non-zero objective */
1686  if( SCIPisZero(scip, objval) )
1687  continue;
1688 
1689  assert(nobjintvars < propdata->objintvarssize);
1690 
1691  propdata->objintvars[nobjintvars] = var;
1692  nobjintvars++;
1693 
1694  if( v >= nintvars )
1695  nobjcontvars++;
1696 
1697  /* catch bound change events if the variable has a non-zero objective coefficient to check if the maximum
1698  * activity of the objective function changed
1699  */
1700  SCIP_CALL( catchObjEvent(scip, propdata, eventhdlr, var) );
1701 
1702  /* captures the variable */
1703  SCIP_CALL( SCIPcaptureVar(scip, var) );
1704  }
1705  }
1706 
1707  if( useimplics )
1708  {
1709  if( uselesscliques != NULL )
1710  SCIPhashtableFree(&uselesscliques);
1711 
1712  SCIPfreeBufferArray(scip, &collectedubvars);
1713  SCIPfreeBufferArray(scip, &collectedlbvars);
1714  SCIPfreeBufferArray(scip, &contributors);
1715  }
1716 
1717  if( nminactvars == 0 )
1718  {
1719  SCIPfreeBlockMemoryArray(scip, &propdata->minactvars, propdata->minactsize);
1720  SCIPfreeBlockMemoryArray(scip, &propdata->minactimpls, propdata->minactsize);
1721  propdata->minactsize = 0;
1722  propdata->minactvars = NULL;
1723  propdata->minactimpls = NULL;
1724  }
1725  else
1726  {
1727  /* sort binary variables with respect to the absolute value of their maximal potential objective contribution for
1728  * the minimum activity of the objective function
1729  */
1730  SCIPsortDownPtrPtr((void**)propdata->minactimpls, (void**)propdata->minactvars, objimplicsComp, nminactvars);
1731 
1732  SCIPdebugMsg(scip, "%d binary variables with non-zero objective contribution w.r.t. the minimum activity of the objective function\n", nminactvars);
1733  }
1734 
1735  if( nmaxactvars == 0 )
1736  {
1737  SCIPfreeBlockMemoryArray(scip, &propdata->maxactvars, propdata->maxactsize);
1738  SCIPfreeBlockMemoryArray(scip, &propdata->maxactchgs, propdata->maxactsize);
1739  propdata->maxactsize = 0;
1740  propdata->maxactvars = NULL;
1741  propdata->maxactchgs = NULL;
1742  }
1743  else
1744  {
1745  /* sort binary variables with respect to the absolute value of their maximal potential objective contribution for
1746  * the maximum activity of the objective function
1747  */
1748  SCIPsortDownRealPtr(propdata->maxactchgs, (void**)propdata->maxactvars, nmaxactvars);
1749 
1750  SCIPdebugMsg(scip, "%d binary variables with non-zero objective contribution w.r.t. the maximum activity of the objective function\n", nmaxactvars);
1751  }
1752 
1753  if( nobjintvars == 0 )
1754  {
1755  SCIPfreeBlockMemoryArray(scip, &propdata->objintvars, propdata->objintvarssize);
1756  propdata->objintvarssize = 0;
1757  propdata->objintvars = NULL;
1758  }
1759  else
1760  {
1761  /* sort integer variables with respect to the absolute value of their objective coefficient */
1762  SCIPsortDownPtr((void**)propdata->objintvars, varCompObj, nobjintvars - nobjcontvars);
1763 
1764  /* sort continuous variables with respect to the absolute value of their objective coefficient */
1765  SCIPsortDownPtr((void**)(&propdata->objintvars[nobjintvars - nobjcontvars]), varCompObj, nobjcontvars);
1766 
1767  SCIPdebugMsg(scip, "%d integer variables and %d continuous variables with non-zero objective contribution\n",
1768  nobjintvars - nobjcontvars, nobjcontvars);
1769  }
1770  }
1771 
1772  SCIPhashmapFree(&binobjvarmap);
1773 
1774  propdata->nminactvars = nminactvars;
1775  propdata->nmaxactvars = nmaxactvars;
1776  propdata->nobjintvars = nobjintvars;
1777  propdata->maxpseudoobjact = SCIP_INVALID;
1778  propdata->maxpseudoobjactinf = 0;
1779  propdata->lastvarnum = -1;
1780  propdata->glbfirstnonfixed = 0;
1781  propdata->maxactfirstnonfixed = 0;
1782  propdata->firstnonfixed = 0;
1783  propdata->nnewvars = 0;
1784  propdata->cutoffbound = SCIPinfinity(scip);
1785  propdata->lastlowerbound = -SCIPinfinity(scip);
1786  propdata->glbpseudoobjval = -SCIPinfinity(scip);
1787 
1788  propdata->initialized = TRUE;
1789 
1790  /* due to scaling after presolving we need to update the global pseudoactivity and the cutoffbound */
1791  propdata->glbpropagated = FALSE;
1792  propdata->glbpseudoobjval = SCIPgetGlobalPseudoObjval(scip);
1793  propdata->cutoffbound = SCIPgetCutoffbound(scip);
1794  assert(SCIPgetDepth(scip) > 0 || SCIPisFeasEQ(scip, propdata->glbpseudoobjval, SCIPgetPseudoObjval(scip)));
1795 
1796  /* create hash table which is used for resolving bound changes */
1797  if( nminactvars > 0 )
1798  {
1799  SCIP_CALL( SCIPhashtableCreate(&propdata->addedvars, SCIPblkmem(scip), nvars,
1800  SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal, NULL) );
1801  }
1802  else
1803  propdata->addedvars = NULL;
1804 
1805 
1806  return SCIP_OKAY;
1807 }
1808 
1809 /** adds for the given non-binary variable a conflict bound depending on its objective contribution */
1810 static
1812  SCIP* scip, /**< SCIP data structure */
1813  SCIP_VAR* var, /**< variable to check for objective contribution */
1814  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1815  SCIP_Real* reqpseudoobjval /**< pointer to store the remaining minimum activity which has to be proven */
1816  )
1818  SCIP_Real objval;
1819 
1820  objval = SCIPvarGetObj(var);
1821  assert(!SCIPisZero(scip, objval));
1822 
1823  if( objval > 0.0 )
1824  {
1825  SCIP_Real loclb;
1826  SCIP_Real glblb;
1827 
1828  glblb = SCIPvarGetLbGlobal(var);
1829  loclb = SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE);
1830  assert(SCIPisFeasGE(scip, loclb, glblb));
1831 
1832  /* check if the local lower bound (at time stamp bdchgidx) is larger than the global lower bound */
1833  if( SCIPisGT(scip, loclb, glblb) )
1834  {
1835  SCIPdebugMsg(scip, " add bound change <%s>[%g] >= <%g>\n", SCIPvarGetName(var), objval, loclb);
1836  SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
1837 
1838  /* hard comparison is enough to make requiredpseudoobjval nonincreasing */
1839  assert((loclb - glblb) * objval > 0.0);
1840 
1841  (*reqpseudoobjval) -= (loclb - glblb) * objval;
1842  }
1843  }
1844  else
1845  {
1846  SCIP_Real locub;
1847  SCIP_Real glbub;
1848 
1849  glbub = SCIPvarGetUbGlobal(var);
1850  locub = SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE);
1851  assert(SCIPisFeasLE(scip, locub, glbub));
1852 
1853  /* check if the local upper bound (at time stamp bdchgidx) is smaller than the global upper bound */
1854  if( SCIPisLT(scip, locub, glbub) )
1855  {
1856  SCIPdebugMsg(scip, " add bound change <%s>[%g] <= <%g>\n", SCIPvarGetName(var), objval, locub);
1857  SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
1858 
1859  /* hard comparison is enough to make requiredpseudoobjval nonincreasing */
1860  assert((locub - glbub) * objval > 0.0);
1861 
1862  (*reqpseudoobjval) -= (locub - glbub) * objval;
1863  }
1864  }
1865 
1866  return SCIP_OKAY;
1867 }
1868 
1869 /** check for the given implication variables if they also contribute to the required minimum activity */
1870 static
1872  SCIP* scip, /**< SCIP data structure */
1873  SCIP_VAR** vars, /**< variable to check for objective contribution */
1874  int start, /**< start index */
1875  int end, /**< end index */
1876  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1877  SCIP_HASHTABLE* addedvars, /**< hash table containing variables which are already added directly or implicitly due to implications */
1878  SCIP_Real* reqpseudoobjval, /**< pointer to store the remaining minimum activity which has to be proven */
1879  SCIP_Bool* foundimplics /**< pointer to store if an implication is found */
1880  )
1881 {
1882  SCIP_VAR* var;
1883  SCIP_Real lb;
1884  SCIP_Real ub;
1885  int v;
1886 
1887  assert(foundimplics != NULL);
1888  assert(*foundimplics == FALSE);
1889 
1890  for( v = start; v < end; ++v )
1891  {
1892  var = vars[v];
1893  assert(var != NULL);
1894  assert(SCIPvarIsBinary(var));
1895 
1896  /* we need to take the bounds after the bdchgidx here, since the variable of the bound change may be the implied one;
1897  * we already counted its contribution before, so we want to see it as fixed here, which it is after the bound change.
1898  */
1899  lb = SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE);
1900  ub = SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE);
1901 
1902  if( lb < 0.5 && ub > 0.5 && !SCIPhashtableExists(addedvars, (void*)var) )
1903  {
1904  (*reqpseudoobjval) -= REALABS(SCIPvarGetObj(var));
1905  SCIPdebugMsg(scip, " implicated variables <%s>[%g] bdchgidx [%g,%g] -> remaining <%g>\n", SCIPvarGetName(var), SCIPvarGetObj(var), lb, ub, *reqpseudoobjval);
1906 
1907  SCIP_CALL( SCIPhashtableInsert(addedvars, (void*)var) );
1908  assert(SCIPhashtableExists(addedvars, (void*)var));
1909  (*foundimplics) = TRUE;
1910  }
1911  }
1912 
1913  return SCIP_OKAY;
1914 }
1915 
1916 /** adds for the given binary variable a conflict bound depending on its objective contribution */
1917 static
1919  SCIP* scip, /**< SCIP data structure */
1920  SCIP_VAR* var, /**< variable to check for objective contribution */
1921  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1922  SCIP_OBJIMPLICS* objimplics, /**< objective implication data for the given variable */
1923  SCIP_HASHTABLE* addedvars, /**< hash table containing variables which are already add directly or implicitly due to implications */
1924  SCIP_Bool respropuseimplics, /**< should implications be used */
1925  SCIP_Real* reqpseudoobjval /**< pointer to store the remaining minimum activity which has to be proven */
1926  )
1927 {
1928  SCIP_Real objval;
1929  SCIP_Real lb;
1930  SCIP_Real ub;
1931  SCIP_Bool foundimplics;
1932 
1933  assert(SCIPvarIsBinary(var));
1934 
1935  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 )
1936  return SCIP_OKAY;
1937 
1938  lb = SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE);
1939  ub = SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE);
1940 
1941  objval = SCIPvarGetObj(var);
1942  foundimplics = FALSE;
1943 
1944  /* only consider variables which are fixed */
1945  if( lb > 0.5 )
1946  {
1947  if( respropuseimplics )
1948  {
1949  SCIP_CALL( getConflictImplics(scip, objimplics->objvars, objimplics->nlbimpls, objimplics->nlbimpls + objimplics->nubimpls,
1950  bdchgidx, addedvars, reqpseudoobjval, &foundimplics) );
1951  }
1952 
1953  /* check if the binary variable has a positive contribution (positive objective coefficient since it is fixed to
1954  * one) or is needed due a positive contribution of an implied variable
1955  */
1956  if( foundimplics || SCIPisPositive(scip, objval) )
1957  {
1958  SCIPdebugMsg(scip, " add bound change <%s>[%g] >= <%g> bdchgidx [%g,%g]\n", SCIPvarGetName(var), objval, lb, lb, ub);
1959  SCIP_CALL( SCIPaddConflictLb(scip, var, NULL) );
1960 
1961  (*reqpseudoobjval) -= MAX(0.0, objval);
1962 
1963  if( addedvars != NULL )
1964  {
1965  assert(!SCIPhashtableExists(addedvars, (void*)var));
1966  SCIP_CALL( SCIPhashtableInsert(addedvars, (void*)var) );
1967  }
1968  }
1969  }
1970  else if( ub < 0.5 )
1971  {
1972  if( respropuseimplics )
1973  {
1974  SCIP_CALL( getConflictImplics(scip, objimplics->objvars, 0, objimplics->nlbimpls,
1975  bdchgidx, addedvars, reqpseudoobjval, &foundimplics) );
1976  }
1977 
1978  /* check if the binary variable has a positive contribution (negative objective coefficient since it is fixed to
1979  * zero) or is needed due a positive contribution of an implied variable
1980  */
1981  if( foundimplics || SCIPisNegative(scip, objval) )
1982  {
1983  SCIPdebugMsg(scip, " add bound change <%s>[%g] <= <%g> bdchgidx=[%g,%g]\n", SCIPvarGetName(var), objval, ub, lb, ub);
1984  SCIP_CALL( SCIPaddConflictUb(scip, var, NULL) );
1985 
1986  (*reqpseudoobjval) += MIN(0.0, objval);
1987 
1988  if( addedvars != NULL )
1989  {
1990  assert(!SCIPhashtableExists(addedvars, (void*)var));
1991  SCIP_CALL( SCIPhashtableInsert(addedvars, (void*)var) );
1992  }
1993  }
1994  }
1995 
1996  return SCIP_OKAY;
1997 }
1998 
1999 
2000 /** resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the
2001  * cutoff bound
2002  */
2003 static
2005  SCIP* scip, /**< SCIP data structure */
2006  SCIP_PROPDATA* propdata, /**< propagator data */
2007  SCIP_VAR* var, /**< variable that was deduced */
2008  int inferinfo, /**< inference information */
2009  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
2010  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
2011  SCIP_HASHTABLE* addedvars, /**< hash table which contains variable which are already added or implict given as reason for the resolve, or NULL */
2012  SCIP_Real* cutoffbound /**< pointer to store the adjusted cutoff bound */
2013  )
2014 {
2015  if( inferinfo != -1 )
2016  {
2017  SCIP_OBJIMPLICS* objimplics;
2018  SCIP_Bool foundimplics;
2019  int start;
2020  int end;
2021 
2022  assert(var != NULL);
2023  assert(SCIPvarIsBinary(var));
2024  assert(bdchgidx != NULL);
2025  assert(SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE)));
2026  assert(inferinfo >= 0);
2027  assert(inferinfo < propdata->nminactvars);
2028  assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE);
2029  assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);
2030 
2031  objimplics = propdata->minactimpls[inferinfo];
2032  assert(objimplics != NULL);
2033 
2034  /* get the objective contribution if we would fix the binary inference variable to its other bound */
2035  (*cutoffbound) -= getVarObjchg(var, SCIPvarGetBestBoundType(var), boundtype);
2036  foundimplics = FALSE;
2037 
2038  if( boundtype == SCIP_BOUNDTYPE_LOWER )
2039  {
2040  start = 0;
2041  end = objimplics->nlbimpls;
2042  }
2043  else
2044  {
2045  start = objimplics->nlbimpls;
2046  end = objimplics->nlbimpls + objimplics->nubimpls;
2047  }
2048 
2049  SCIP_CALL( getConflictImplics(scip, objimplics->objvars, start, end, bdchgidx, addedvars, cutoffbound, &foundimplics) );
2050  }
2051  else
2052  {
2053  SCIP_Real glbbound;
2054  SCIP_Real newbound;
2055  SCIP_Real objval;
2056 
2057  objval = SCIPvarGetObj(var);
2058 
2059  assert(!SCIPisZero(scip, objval));
2060 
2061  if( objval > 0.0 )
2062  {
2063  newbound = SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE);
2064  glbbound = SCIPvarGetLbGlobal(var);
2065  }
2066  else
2067  {
2068  newbound = SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE);
2069  glbbound = SCIPvarGetUbGlobal(var);
2070  }
2071 
2072  /* in case the variable is integral we just need to prove the newbound plus/minus (1 - epsilon) since the this bound
2073  * would be rounded to newbound due to integrability which is global information
2074  */
2075  if( SCIPvarIsIntegral(var) )
2076  {
2077  if( objval > 0.0 )
2078  newbound += 1 - 10 * SCIPfeastol(scip);
2079  else
2080  newbound -= 1 - 10 * SCIPfeastol(scip);
2081  }
2082 
2083  /* adjust the cutoff bound by the portion the inference variable contributes to the presudo objective activitiy
2084  * (minactivity)
2085  */
2086  assert(!SCIPisNegative(scip, objval * (newbound - glbbound)));
2087  (*cutoffbound) -= objval * (newbound - glbbound);
2088  }
2089 
2090  return SCIP_OKAY;
2091 }
2092 
2093 
2094 /** resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the
2095  * cutoff bound
2096  */
2097 static
2099  SCIP* scip, /**< SCIP data structure */
2100  SCIP_PROPDATA* propdata, /**< propagator data */
2101  SCIP_Real cutoffbound, /**< the global cutoff */
2102  SCIP_VAR* infervar, /**< variable that was deduced, or NULL for conflict analysis initialization */
2103  int inferinfo, /**< inference information */
2104  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
2105  SCIP_BDCHGIDX* bdchgidx /**< bound change index (time stamp of bound change), or NULL for current time */
2106  )
2107 {
2108  SCIP_HASHTABLE* addedvars;
2109  SCIP_VAR** vars;
2110  SCIP_VAR* var;
2111  SCIP_Real glbpseudoobjval;
2112  SCIP_Real reqpseudoobjval;
2114  int nvars;
2115  int v;
2116 
2117  infinity = FALSE;
2118  addedvars = NULL;
2119  nvars = propdata->nminactvars;
2120 
2121  /* the global pseudo value gives us a global valid minimal activity
2122  *
2123  * @note The global pseudo objective activity can be minus infinity. In that case all variable are part of the
2124  * reason/explanation
2125  *
2126  * @note If the global pseudo objective activity is greater than the required minactivity, the local bound change
2127  * which has to explained is actually (now) a global one. That means, the reason/explanation is empty
2128  */
2129  glbpseudoobjval = SCIPgetGlobalPseudoObjval(scip);
2130 
2131  if( SCIPisInfinity(scip, -glbpseudoobjval) )
2132  {
2133  infinity = TRUE;
2134  reqpseudoobjval = cutoffbound;
2135  }
2136  else
2137  {
2138  /* clear hash table for storing variables which are not needed to add the reason due to global implications or
2139  * already added
2140  */
2141  if( nvars > 0 )
2142  {
2143  addedvars = propdata->addedvars;
2144  SCIPhashtableRemoveAll(addedvars);
2145  }
2146 
2147  if( infervar != NULL )
2148  {
2149  SCIP_CALL( adjustCutoffbound(scip, propdata, infervar, inferinfo, boundtype, bdchgidx, addedvars, &cutoffbound) );
2150  }
2151 
2152  reqpseudoobjval = cutoffbound - glbpseudoobjval;
2153  }
2154 
2155  SCIPdebugMsg(scip, "resolve propagation global pseudo objective <%g>, cutoff bounda <%g>, required minactivity <%g>\n",
2156  glbpseudoobjval, cutoffbound, reqpseudoobjval);
2157 
2158  /* the variables responsible for the propagation are the ones with
2159  * - obj > 0 and local lb > global lb
2160  * - obj < 0 and local ub < global ub
2161  *
2162  * collect all variables which contribute positively to the pseudo objective value (minimum activity) until we
2163  * reached the (adjusted) required minimum activity for the inference bound change
2164  */
2165 
2166  /* first, consider the binary variables */
2167  if( nvars > 0 )
2168  {
2169  SCIP_OBJIMPLICS** minactimpls;
2170 
2171  vars = propdata->minactvars;
2172  assert(vars != NULL);
2173 
2174  minactimpls = propdata->minactimpls;
2175  assert(minactimpls != NULL);
2176 
2177 #ifndef NDEBUG
2178  checkGlbfirstnonfixed(scip, propdata);
2179 #endif
2180 
2181  if( infinity )
2182  {
2183  /* if the required minimum activity is minus infinity, we have to add all variables which contribute the local
2184  * pseudo objective activity
2185  */
2186 
2187  for( v = propdata->glbfirstnonfixed; v < nvars; ++v )
2188  {
2189  var = vars[v];
2190  assert(var != NULL);
2191 
2192  /* @note binary variables can have a zero objective value */
2193 
2194  if( var == infervar )
2195  continue;
2196 
2197  SCIP_CALL( addConflictBinvar(scip, var, bdchgidx, NULL, NULL, FALSE, &reqpseudoobjval) );
2198  }
2199  }
2200  else
2201  {
2202  assert(addedvars != NULL);
2203 
2204  for( v = propdata->glbfirstnonfixed; v < nvars && SCIPisPositive(scip, reqpseudoobjval); ++v )
2205  {
2206  var = vars[v];
2207  assert(var != NULL);
2208 
2209  /* @note binary variables can have a zero objective value */
2210 
2211  if( var == infervar )
2212  continue;
2213 
2214  if( SCIPhashtableExists(addedvars, (void*)var) )
2215  continue;
2216 
2217  SCIP_CALL( addConflictBinvar(scip, var, bdchgidx, minactimpls[v], addedvars, propdata->respropuseimplics, &reqpseudoobjval) );
2218  }
2219  }
2220  }
2221 
2222  vars = propdata->objintvars;
2223  nvars = propdata->nobjintvars;
2224  assert(nvars == 0 || vars != NULL);
2225 
2226  /* second, consider the non-binary variables */
2227  for( v = 0; v < nvars && (infinity || SCIPisPositive(scip, reqpseudoobjval)); ++v )
2228  {
2229  var = vars[v];
2230  assert(var != NULL);
2231  assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
2232 
2233  if( var == infervar )
2234  continue;
2235 
2236  SCIP_CALL( addConflictBounds(scip, var, bdchgidx, &reqpseudoobjval) );
2237  }
2238 
2239  return SCIP_OKAY;
2240 }
2241 
2242 /** propagates the given variable against the cutoff bound */
2243 static
2245  SCIP* scip, /**< SCIP data structure */
2246  SCIP_PROP* prop, /**< propagator, or NULL */
2247  SCIP_VAR* var, /**< variable to propagate */
2248  int inferinfo, /**< inference information to store with the bound change */
2249  SCIP_Real objchg, /**< objective change */
2250  SCIP_Real cutoffbound, /**< cutoff bound to use */
2251  SCIP_Real pseudoobjval, /**< pseudo objective value to use */
2252  SCIP_Bool local, /**< local or global propagation */
2253  SCIP_Bool* tightened /**< pointer to store if the variable domain was tightened */
2254  )
2255 {
2256  SCIP_Real lb;
2257  SCIP_Real ub;
2258  SCIP_Real newbd;
2259  SCIP_Bool infeasible;
2260 
2261  assert(!SCIPisZero(scip, objchg));
2262  assert(!SCIPisInfinity(scip, -pseudoobjval));
2263  assert(!SCIPisInfinity(scip, cutoffbound));
2264  assert(SCIPisLT(scip, pseudoobjval, cutoffbound) );
2265  assert(tightened != NULL);
2266 
2267  *tightened = FALSE;
2268 
2269  /* collect bounds of the variable */
2270  if( local )
2271  {
2272  assert(prop != NULL);
2273  lb = SCIPvarGetLbLocal(var);
2274  ub = SCIPvarGetUbLocal(var);
2275  }
2276  else
2277  {
2278  lb = SCIPvarGetLbGlobal(var);
2279  ub = SCIPvarGetUbGlobal(var);
2280  }
2281 
2282  if( SCIPisFeasEQ(scip, lb, ub) )
2283  return SCIP_OKAY;
2284 
2285  /* depending on the objective contribution we can try to tighten the lower or upper bound of the variable */
2286  if( objchg > 0.0 )
2287  {
2288  newbd = lb + (cutoffbound - pseudoobjval) / objchg;
2289 
2290  if( local )
2291  {
2292  SCIP_CALL( SCIPinferVarUbProp(scip, var, newbd, prop, inferinfo, FALSE, &infeasible, tightened) );
2293  assert(!infeasible);
2294 
2295  if( *tightened ) /* might not be tightened due to numerical reasons */
2296  {
2297  SCIPdebugMsg(scip, " -> new (local) upper bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n",
2298  SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound);
2299  }
2300  }
2301  else
2302  {
2303  SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, FALSE, &infeasible, tightened) );
2304  assert(!infeasible);
2305 
2306  if( *tightened )
2307  {
2308  SCIPdebugMsg(scip, " -> new (global) upper bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n",
2309  SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound);
2310  }
2311  }
2312  }
2313  else
2314  {
2315  newbd = ub + (cutoffbound - pseudoobjval) / objchg;
2316 
2317  if( local )
2318  {
2319  SCIP_CALL( SCIPinferVarLbProp(scip, var, newbd, prop, inferinfo, FALSE, &infeasible, tightened) );
2320  assert(!infeasible);
2321 
2322  if( *tightened ) /* might not be tightened due to numerical reasons */
2323  {
2324  SCIPdebugMsg(scip, " -> new (local) lower bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n",
2325  SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound);
2326  }
2327  }
2328  else
2329  {
2330  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, FALSE, &infeasible, tightened) );
2331  assert(!infeasible);
2332 
2333  if( *tightened )
2334  {
2335  SCIPdebugMsg(scip, " -> new (global) lower bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n",
2336  SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound);
2337  }
2338  }
2339  }
2340 
2341  return SCIP_OKAY;
2342 }
2343 
2344 /** propagates the given binary variable against the cutoff bound */
2345 static
2347  SCIP* scip, /**< SCIP data structure */
2348  SCIP_PROP* prop, /**< propagator, or NULL */
2349  SCIP_VAR* var, /**< variable to propagate */
2350  int pos, /**< position of the variable in the corresponding propdata variable array */
2351  SCIP_Real cutoffbound, /**< cutoff bound to use */
2352  SCIP_Real pseudoobjval, /**< pseudo objective value to use */
2353  SCIP_Bool* tightened, /**< pointer to store if the variable domain was tightened */
2354  SCIP_Bool* cutoff, /**< pointer to store if a cutoff was detected */
2355  SCIP_Bool local /**< propagate local bounds, otherwise global bounds */
2356  )
2357 {
2358  SCIP_PROPDATA* propdata;
2359  SCIP_OBJIMPLICS* objimplics;
2360  SCIP_Real lbobjchg;
2361  SCIP_Real ubobjchg;
2362  SCIP_Real objchg;
2363 
2364  assert(SCIPvarIsBinary(var));
2365 
2366  propdata = SCIPpropGetData(prop);
2367  assert(propdata != NULL);
2368 
2369  objimplics = propdata->minactimpls[pos];
2370  assert(objimplics != NULL);
2371 
2372  /* get objective change in case of fixing the variable to its lower bound (that is zero) */
2373  SCIP_CALL( getMinactObjchg(scip, var, objimplics, NULL, SCIP_BOUNDTYPE_LOWER, local, &lbobjchg) );
2374  assert(!SCIPisNegative(scip, lbobjchg));
2375 
2376  /* get objective change in case of fixing the variable to its upper bound (that is one) */
2377  SCIP_CALL( getMinactObjchg(scip, var, objimplics, NULL, SCIP_BOUNDTYPE_UPPER, local, &ubobjchg) );
2378  assert(!SCIPisNegative(scip, ubobjchg));
2379 
2380  (*tightened) = FALSE;
2381 
2382  /* nothing can be done if the objective contribution is zero independently of the bound */
2383  if( SCIPisZero(scip, lbobjchg) && SCIPisZero(scip, ubobjchg) )
2384  return SCIP_OKAY;
2385 
2386  /* if the lbobjchg and ubobjchg are both able to fix the variable to its upper (1.0) or lower (0.0) bound,
2387  * respectively, we detected an cutoff
2388  *
2389  * @note There is no need to use SCIPisFeasLT() in case the objective is integral since the cutoff bound in that case
2390  * is the upper bound minus 1 plus the SCIPcutoffbounddelta() (which is MIN(100.0 * feastol, 0.0001)). However,
2391  * if the objective is not integral we have to check w.r.t. an epsilon to avoid numerical problems.
2392  */
2393  if( SCIPisFeasLT(scip, cutoffbound, pseudoobjval + ubobjchg) && SCIPisFeasLT(scip, cutoffbound, pseudoobjval + lbobjchg) )
2394  {
2395  /* check if conflict analysis is applicable */
2396  if( local && SCIPisConflictAnalysisApplicable(scip) )
2397  {
2398  assert(SCIPgetDepth(scip) > 0);
2399 
2400  /* initialize conflict analysis */
2402 
2403  /* add all variable whose best bound changes increased the pseudo objective value above to cutoff bound */
2404  SCIP_CALL( resolvePropagation(scip, propdata, pseudoobjval, NULL, -1, SCIP_BOUNDTYPE_UPPER, NULL) );
2405 
2406  /* analyze the conflict */
2407  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
2408  }
2409 
2410  (*cutoff) = TRUE;
2411  }
2412  else
2413  {
2414  /* try to tighten the variable bound use the larger objective contribution */
2415  if( lbobjchg > ubobjchg )
2416  objchg = -lbobjchg;
2417  else
2418  objchg = ubobjchg;
2419 
2420  SCIP_CALL( propagateCutoffboundVar(scip, prop, var, pos, objchg, cutoffbound, pseudoobjval, local, tightened) );
2421  }
2422 
2423  return SCIP_OKAY;
2424 }
2425 
2426 /** globally propagates if a new cutoff bound or global pseudo objective value (minimum activity of the objective
2427  * function) is available
2428  */
2429 static
2431  SCIP* scip, /**< SCIP data structure */
2432  SCIP_PROP* prop, /**< propagator */
2433  int* nchgbds, /**< pointer to store the number of bound changes */
2434  SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
2435  )
2437  SCIP_PROPDATA* propdata;
2438  SCIP_VAR** minactvars;
2439  SCIP_VAR** objintvars;
2440  SCIP_VAR* var;
2441  SCIP_Bool tightened;
2442  SCIP_Real pseudoobjval;
2443  SCIP_Real cutoffbound;
2444  int nminactvars;
2445  int nobjintvars;
2446  int v;
2447 
2448  /* this method should not be called in the root node of the search tree since the standard propagation already does
2449  * the job
2450  */
2451  assert(SCIPgetDepth(scip) > 0);
2452 
2453  propdata = SCIPpropGetData(prop);
2454  assert(propdata != NULL);
2455 
2456  pseudoobjval = SCIPgetGlobalPseudoObjval(scip);
2457  cutoffbound = propdata->cutoffbound;
2458 
2459  /* nothing can be done if the global pseudo objective is minus infinity */
2460  if( SCIPisInfinity(scip, -pseudoobjval) )
2461  return SCIP_OKAY;
2462 
2463  /* check if the global pseudo objective value (minimum activity of the objective function) is greater or equal to
2464  * the cutoff bound
2465  */
2466  if( SCIPisGE(scip, pseudoobjval, cutoffbound) )
2467  {
2468  *cutoff = TRUE;
2469  return SCIP_OKAY;
2470  }
2471 
2472  minactvars = propdata->minactvars;
2473  objintvars = propdata->objintvars;
2474  nminactvars = propdata->nminactvars;
2475  nobjintvars = propdata->nobjintvars;
2476 
2477 #ifndef NDEBUG
2478  checkGlbfirstnonfixed(scip, propdata);
2479 #endif
2480 
2481  *cutoff = FALSE;
2482 
2483  /* always propagate the binary variables completely */
2484  for( v = propdata->glbfirstnonfixed; v < nminactvars; ++v )
2485  {
2486  var = minactvars[v];
2487  assert(var != NULL);
2488 
2489  /* check if the variables is already globally fixed; if so continue with the potential candidate */
2490  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
2491  continue;
2492 
2493  /* propagates the cutoff bound for the given binary variable */
2494  SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, FALSE) );
2495 
2496  /* the binary variables are sorted in non-increasing manner w.r.t. the absolute value of their objective
2497  * contribution w.r.t. minimum activity (pseudo objective value) of the objective function; these values are the
2498  * increase in the pseudo objective activity we would get if we fix the variable to its worse bound; hence, we can
2499  * stop if for a variable this potential increase is not enough too exceed the cutoff bound;
2500  */
2501  if( !tightened )
2502  {
2503  SCIPdebugMsg(scip, "interrupt global pseudo objective propagation w.r.t. cutoff bound <%.15g> for binary variables after %d from %d binary variables\n",
2504  cutoffbound, v, nminactvars);
2505  break;
2506  }
2507 
2508  if( *cutoff )
2509  return SCIP_OKAY;
2510 
2511  /* @note The variable might not be globally fixed right away since this would destroy the local internal
2512  * data structure of a search node; the bound change is in that case pending; hence we cannot assert
2513  * that the variable is globally fixed
2514  */
2515  (*nchgbds)++;
2516  }
2517  propdata->glbfirstnonfixed = v;
2518  propdata->firstnonfixed = MAX(propdata->firstnonfixed, v);
2519 
2520  /* check all binary variables which could potentially be fixed */
2521  for( ; v < nminactvars && cutoffbound - pseudoobjval < propdata->minactimpls[v]->maxobjchg; ++v )
2522  {
2523  var = minactvars[v];
2524  assert(var != NULL);
2525 
2526  /* check if the variables is already globally fixed; if so continue with the potential candidate */
2527  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
2528  continue;
2529 
2530  /* propagates the cutoff bound for the given binary variable */
2531  SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, FALSE) );
2532 
2533  /* check if the domain of the variable was reduced */
2534  if( tightened )
2535  (*nchgbds)++;
2536 
2537  if( *cutoff )
2538  return SCIP_OKAY;
2539  }
2540 
2541 #if 0 /* might fail, but is not a real error, still need to investigate */
2542 #ifndef NDEBUG
2543  /* check that the abort criteria for the binary variables works */
2544  for( ; v < nminactvars; ++v )
2545  {
2546  assert(cutoffbound - pseudoobjval >= propdata->minactimpls[v]->maxobjchg);
2547 
2548  var = minactvars[v];
2549  assert(var != NULL);
2550 
2551  /* check if the variable is already locally fixed; in that case we just continue with the next potential
2552  * candidate
2553  */
2554  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
2555  continue;
2556 
2557  /* propagates the cutoff bound for the given binary variable */
2558  SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, FALSE) );
2559  assert(!tightened);
2560  assert(!(*cutoff));
2561  }
2562 #endif
2563 #endif
2564 
2565  /* propagate the non-binary variables completely */
2566  for( v = 0; v < nobjintvars; ++v )
2567  {
2568  var = objintvars[v];
2569  assert(var != NULL);
2570  assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
2571 
2572  /* try to tighten the bound of the variable */
2573  SCIP_CALL( propagateCutoffboundVar(scip, NULL, var, -1, SCIPvarGetObj(var), cutoffbound, pseudoobjval, FALSE, &tightened) );
2574 
2575  /* check if the domain of the variable was reduced */
2576  if( tightened )
2577  (*nchgbds)++;
2578  }
2579 
2580  propdata->glbpropagated = TRUE;
2581 
2582  return SCIP_OKAY;
2583 }
2584 
2585 /** propagates the cutoff bound for binary variables (c*x <= cutoff) */
2586 static
2588  SCIP* scip, /**< SCIP data structure */
2589  SCIP_PROP* prop, /**< propagator */
2590  SCIP_Real cutoffbound, /**< cutoff bound to use */
2591  SCIP_Real pseudoobjval, /**< pseudo objective value to use */
2592  int* nfixedvars, /**< pointer to store the number of fixed variables */
2593  SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
2594  )
2595 {
2596  SCIP_PROPDATA* propdata;
2597  SCIP_VAR** minactvars;
2598  SCIP_VAR* var;
2599  SCIP_Bool tightened;
2600  int nminactvars;
2601  int v;
2602 
2603  propdata = SCIPpropGetData(prop);
2604  assert(propdata != NULL);
2605 
2606  minactvars = propdata->minactvars;
2607  nminactvars = propdata->nminactvars;
2608  assert(nminactvars == 0 || minactvars != NULL);
2609 
2610  /* always propagate the binary variables completely; note that the variables before the firstnonfixed indexed are
2611  * already locally fixed and those before glbfirstnonfixed are already globally fixed
2612  */
2613 
2614 #ifndef NDEBUG
2615  /* check that the variables before glbfirstnonfixed are globally fixed */
2616  checkGlbfirstnonfixed(scip, propdata);
2617 
2618  /* check that the variables before firstnonfixed are locally fixed */
2619  for( v = propdata->glbfirstnonfixed; v < propdata->firstnonfixed; ++v )
2620  {
2621  var = minactvars[v];
2622  assert(var != NULL);
2623 
2624  assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5);
2625  }
2626 #endif
2627 
2628  (*cutoff) = FALSE;
2629 
2630  for( v = propdata->firstnonfixed; v < nminactvars; ++v )
2631  {
2632  var = minactvars[v];
2633  assert(var != NULL);
2634 
2635  /* check if the variable is already locally fixed; in that case we just continue with the next potential
2636  * candidate
2637  */
2638  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5)
2639  continue;
2640 
2641  /* propagates the cutoff bound for the given binary variable */
2642  SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, TRUE) );
2643 
2644  /* the binary variables are sorted in non-increasing manner w.r.t. the absolute value of their objective
2645  * contribution w.r.t. minimum activity of the objective function; These values are the increase in the pseudo
2646  * objective activity (minimum activity of the objective function) we would get if we fix the variable to its
2647  * worse bound; hence, we can stop if for a variable this potential increase is not enough too exceed the cutoff
2648  * bound;
2649  */
2650  if( !tightened )
2651  {
2652  SCIPdebugMsg(scip, "interrupt local pseudo objective propagation w.r.t. cutoff bound <%.15g> for binary variables after %d from %d binary variables\n",
2653  cutoffbound, v, nminactvars);
2654  break;
2655  }
2656 
2657  if( *cutoff )
2658  return SCIP_OKAY;
2659 
2660  /* check that the binary variable is locally fixed */
2661  assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5);
2662  (*nfixedvars)++;
2663  }
2664  propdata->firstnonfixed = v;
2665 
2666  /* check all binary variables which could potentially be fixed */
2667  for( ; v < nminactvars && cutoffbound - pseudoobjval < propdata->minactimpls[v]->maxobjchg; ++v )
2668  {
2669  var = minactvars[v];
2670  assert(var != NULL);
2671 
2672  /* check if the variable is already locally fixed; in that case we just continue with the next potential
2673  * candidate
2674  */
2675  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5)
2676  continue;
2677 
2678  /* propagates the cutoff bound for the given binary variable */
2679  SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, TRUE) );
2680 
2681  if( tightened )
2682  {
2683  assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5);
2684  (*nfixedvars)++;
2685  }
2686 
2687  if( *cutoff )
2688  return SCIP_OKAY;
2689  }
2690 
2691 #if 0 /* might fail, but is not a real error, still need to investigate */
2692 #ifndef NDEBUG
2693  /* check that the abort criteria for the binary variables works */
2694  for( ; v < nminactvars; ++v )
2695  {
2696  var = minactvars[v];
2697  assert(var != NULL);
2698 
2699  assert(cutoffbound - pseudoobjval >= propdata->minactimpls[v]->maxobjchg);
2700 
2701  /* check if the variable is already locally fixed; in that case we just continue with the next potential
2702  * candidate
2703  */
2704  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5)
2705  continue;
2706 
2707  /* propagates the cutoff bound for the given binary variable */
2708  SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, TRUE) );
2709  assert(!tightened);
2710  assert(!(*cutoff));
2711  }
2712 #endif
2713 #endif
2714 
2715  return SCIP_OKAY;
2716 }
2717 
2718 /** propagates the cutoff bound c*x <= cutoff */
2719 static
2721  SCIP* scip, /**< SCIP data structure */
2722  SCIP_PROP* prop, /**< propagator */
2723  SCIP_RESULT* result /**< pointer to store the result of the callback method */
2724  )
2725 {
2726  SCIP_PROPDATA* propdata;
2727  SCIP_Real pseudoobjval;
2728  SCIP_Real cutoffbound;
2729  SCIP_Bool cutoff;
2730  SCIP_Bool tightened;
2731  int nchgbds;
2732 
2733  assert(result != NULL);
2734 
2735  (*result) = SCIP_DIDNOTRUN;
2736 
2737  propdata = SCIPpropGetData(prop);
2738  assert(propdata != NULL);
2739 
2740  /* get current pseudo objective value (minimum activity of the objective function) and cutoff bound */
2741  pseudoobjval = SCIPgetPseudoObjval(scip);
2742  if( SCIPisInfinity(scip, -pseudoobjval) )
2743  return SCIP_OKAY;
2744  cutoffbound = SCIPgetCutoffbound(scip);
2745  if( SCIPisInfinity(scip, cutoffbound) )
2746  return SCIP_OKAY;
2747 
2748  /* @note A new global pseudo objective value could be used to retrieve global fixings. There is, however, no need to
2749  * check if a new global pseudo objective value is available. This is the case since a new (better) global
2750  * pseudo activity implies that a global bound change was performed. That causes that the root node of the
2751  * search tree gets marked for repropagation. That will result in a propagation call of the pseudo objective
2752  * propagator.
2753  */
2754 
2755  /* check current cutoff bound */
2756  if( cutoffbound < propdata->cutoffbound )
2757  {
2758  propdata->glbpropagated = FALSE;
2759  propdata->cutoffbound = cutoffbound;
2760  }
2761 
2762  nchgbds = 0;
2763  cutoff = FALSE;
2764  (*result) = SCIP_DIDNOTFIND;
2765 
2766  /* check if we have a new cutoff bound; in that case we globally propagate this new bound
2767  *
2768  * @note there is no need to propagate the cutoff bound if we are in the root node since this will be done by the
2769  * standard local propagation
2770  */
2771  if( propdata->propcutoffbound && !propdata->glbpropagated && SCIPgetDepth(scip) > 0 )
2772  {
2773  /* first globally propagate new cutoff bound or pseudo objective activity */
2774  SCIP_CALL( propagateCutoffboundGlobally(scip, prop, &nchgbds, &cutoff) );
2775 
2776  if( cutoff )
2777  {
2778  /* we are done with solving since a global pseudo activity is greater or equal to the cutoff bound */
2779  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
2780 
2781  (*result) = SCIP_CUTOFF;
2782  return SCIP_OKAY;
2783  }
2784 
2785  /* check if the global propagation cut off the active/current node */
2786  if( SCIPgetCutoffdepth(scip) <= SCIPgetDepth(scip) )
2787  {
2788  (*result) = SCIP_CUTOFF;
2789  return SCIP_OKAY;
2790  }
2791  }
2792 
2793  /* check if the pseudo objective value (minimum activity of the objective function) is greater or equal to the cutoff
2794  * bound
2795  */
2796  if( SCIPisGE(scip, pseudoobjval, cutoffbound) )
2797  {
2798  SCIPdebugMsg(scip, "pseudo objective value <%g> exceeds cutoff bound <%g>\n", pseudoobjval, cutoffbound);
2799 
2800  /* check if conflict analysis is applicable */
2802  {
2803  assert(SCIPgetDepth(scip) > 0);
2804 
2805  /* initialize conflict analysis */
2807 
2808  /* add all variable whose best bound changes increased the pseudo objective value above the cutoff bound */
2809  SCIP_CALL( resolvePropagation(scip, propdata, cutoffbound, NULL, -1, SCIP_BOUNDTYPE_UPPER, NULL) );
2810 
2811  /* analyze the conflict */
2812  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
2813  }
2814  (*result) = SCIP_CUTOFF;
2815 
2816  return SCIP_OKAY;
2817  }
2818 
2819  SCIPdebugMsg(scip, "propagating pseudo objective function (pseudoobj: %g, cutoffbound: %g)\n", pseudoobjval, cutoffbound);
2820 
2821  /* propagate binary variables */
2822  SCIP_CALL( propagateCutoffboundBinvars(scip, prop, cutoffbound, pseudoobjval, &nchgbds, &cutoff) );
2823 
2824  if( cutoff )
2825  {
2826  (*result) = SCIP_CUTOFF;
2827  return SCIP_OKAY;
2828  }
2829 
2830  /* tighten domains of non-binary variables, if they would increase the pseudo objective value above the cutoff
2831  * bound
2832  */
2833  if( propdata->propfullinroot && SCIPgetDepth(scip) == 0 )
2834  {
2835  SCIP_VAR** objintvars;
2836  SCIP_VAR* var;
2837  SCIP_Real objval;
2838  int nobjintvars;
2839  int v;
2840 
2841  objintvars = propdata->objintvars;
2842  nobjintvars = propdata->nobjintvars;
2843  assert(nobjintvars == 0 || objintvars != NULL);
2844 
2845  /* propagate all non-binary variables */
2846  for( v = 0; v < nobjintvars; ++v )
2847  {
2848  var = objintvars[v];
2849  assert(var != NULL);
2850 
2851  objval = SCIPvarGetObj(var);
2852  assert(!SCIPisZero(scip, objval));
2853 
2854  /* try to tighten the bound of the variable */
2855  SCIP_CALL( propagateCutoffboundVar(scip, NULL, var, -1, objval, cutoffbound, pseudoobjval, FALSE, &tightened) );
2856 
2857  /* check if the domain of the variable was reduced */
2858  if( tightened )
2859  nchgbds++;
2860  }
2861  }
2862  else
2863  {
2864  SCIP_VAR** objintvars;
2865  SCIP_VAR* var;
2866  SCIP_Real objval;
2867  int nobjintvars;
2868  int nmaxuseless;
2869  int nuseless;
2870  int c;
2871  int v;
2872 
2873  objintvars = propdata->objintvars;
2874  nobjintvars = propdata->nobjintvars;
2875  assert(nobjintvars == 0 || objintvars != NULL);
2876 
2877  /* compute maximum number of useless propagations before aborting */
2878  nmaxuseless = MAX(propdata->minuseless, (int)propdata->maxvarsfrac*(nobjintvars));
2879 
2880  nuseless = 0;
2881  v = propdata->lastvarnum;
2882 
2883  for( c = 0; c < nobjintvars && nuseless < nmaxuseless; ++c )
2884  {
2885  v++;
2886  if( v >= nobjintvars )
2887  v = 0;
2888 
2889  var = objintvars[v];
2890  assert(var != NULL);
2891 
2892  objval = SCIPvarGetObj(var);
2893  assert(!SCIPisZero(scip, objval));
2894 
2895  /* try to tighten the bound of the variable */
2896  SCIP_CALL( propagateCutoffboundVar(scip, prop, var, -1, objval, cutoffbound, pseudoobjval, TRUE, &tightened) );
2897 
2898  /* check if the domain of the variable was reduced */
2899  if( tightened )
2900  nchgbds++;
2901  else
2902  nuseless++;
2903  }
2904  propdata->lastvarnum = v;
2905  }
2906 
2907  /* check if we chanced bounds */
2908  if( nchgbds > 0 )
2909  (*result) = SCIP_REDUCEDDOM;
2910 
2911  return SCIP_OKAY;
2912 }
2913 
2914 /** recalculates the maximum objective pseudoactivity */
2915 static
2917  SCIP* scip, /**< SCIP data structure */
2918  SCIP_PROPDATA* propdata /**< propagator data */
2919  )
2920 {
2921  SCIP_VAR** vars;
2922  SCIP_Real objval;
2923  SCIP_Real contrib;
2924  int nvars;
2925  int v;
2926 
2927  assert(propdata != NULL);
2928 
2929  /* get problem variables */
2930  vars = SCIPgetVars(scip);
2931  nvars = SCIPgetNVars(scip);
2932 
2933  /* calculate current max pseudo activity and largest contribution */
2934  propdata->maxpseudoobjact = 0.0;
2935  propdata->maxpseudoobjactinf = 0;
2936 
2937  for( v = 0; v < nvars; ++v )
2938  {
2939  objval = SCIPvarGetObj(vars[v]);
2940  if( SCIPisPositive(scip, objval) )
2941  {
2942  contrib = SCIPvarGetUbGlobal(vars[v]);
2943  if( !SCIPisInfinity(scip, contrib) )
2944  contrib *= objval;
2945  }
2946  else if( SCIPisNegative(scip, objval) )
2947  {
2948  contrib = SCIPvarGetLbGlobal(vars[v]);
2949  if( !SCIPisInfinity(scip, -contrib) )
2950  contrib *= objval;
2951  else
2952  contrib *= -1.0;
2953  }
2954  else
2955  continue;
2956 
2957  if( SCIPisInfinity(scip, contrib) )
2958  propdata->maxpseudoobjactinf++;
2959  else
2960  propdata->maxpseudoobjact += contrib;
2961  }
2962 }
2963 
2964 /** updates the pseudo objective activity if necessary */
2965 static
2967  SCIP* scip, /**< SCIP data structure */
2968  SCIP_PROPDATA* propdata /**< propagator data */
2969  )
2970 {
2971  assert(propdata != NULL);
2973  /* if necessary, calculate the maximum pseudo objective activity */
2974  if( propdata->maxpseudoobjact == SCIP_INVALID ) /*lint !e777*/
2975  calcMaxObjPseudoactivity(scip, propdata);
2976  assert(propdata->maxpseudoobjact != SCIP_INVALID); /*lint !e777*/
2977 }
2978 
2979 /** returns the residual pseudo objective activity without the given value */
2980 static
2982  SCIP* scip, /**< SCIP data structure */
2983  SCIP_PROPDATA* propdata, /**< propagator data */
2984  SCIP_Real contrib /**< value to eliminate from pseudo objective activity */
2985  )
2986 {
2987  SCIP_Real residual;
2988 
2989  assert(propdata != NULL);
2990 
2991  /* if necessary, calculate the maximum pseudo objective activity */
2992  if( propdata->maxpseudoobjact == SCIP_INVALID ) /*lint !e777*/
2993  calcMaxObjPseudoactivity(scip, propdata);
2994  assert(propdata->maxpseudoobjact != SCIP_INVALID); /*lint !e777*/
2995 
2996  if( SCIPisInfinity(scip, contrib) )
2997  {
2998  assert(propdata->maxpseudoobjactinf >= 1);
2999  /* check if this variable yields the only infinite contribution */
3000  if( propdata->maxpseudoobjactinf == 1 )
3001  residual = propdata->maxpseudoobjact;
3002  else
3003  residual = SCIPinfinity(scip);
3004  }
3005  else
3006  {
3007  /* check if there is an infinite contribution */
3008  if( propdata->maxpseudoobjactinf >= 1 )
3009  residual = SCIPinfinity(scip);
3010  else
3011  residual = propdata->maxpseudoobjact - contrib;
3012  }
3013 
3014  return residual;
3015 }
3016 
3017 /** returns the residual pseudo objective activity */
3018 static
3020  SCIP* scip, /**< SCIP data structure */
3021  SCIP_PROPDATA* propdata, /**< propagator data */
3022  SCIP_VAR* var /**< variable to get residual activity for */
3023  )
3024 {
3025  SCIP_Real objval;
3026  SCIP_Real contrib;
3027 
3028  assert(propdata != NULL);
3029 
3030  objval = SCIPvarGetObj(var);
3032  {
3033  contrib = SCIPvarGetUbGlobal(var);
3034  if( !SCIPisInfinity(scip, contrib) )
3035  contrib *= objval;
3036  }
3037  else
3038  {
3040  contrib = SCIPvarGetLbGlobal(var);
3041  if( !SCIPisInfinity(scip, -contrib) )
3042  contrib *= objval;
3043  else
3044  contrib *= -1.0;
3045  }
3046 
3047  return getMaxObjPseudoactivityResidualValue(scip, propdata, contrib);
3048 }
3049 
3050 /** returns the maximum pseudo objective activity of the objective function */
3051 static
3053  SCIP* scip, /**< SCIP data structure */
3054  SCIP_PROPDATA* propdata /**< propagator data */
3055  )
3056 {
3057  return getMaxObjPseudoactivityResidualValue(scip, propdata, 0.0);
3059 
3060 /** propagates the global domain of the given binary variable against the lower bound (c*x >= lowerbound) */
3061 static
3063  SCIP* scip, /**< SCIP data structure */
3064  SCIP_VAR* var, /**< variable to propagate */
3065  SCIP_Real lowerbound, /**< lower bound to use */
3066  SCIP_Real maxpseudoobjact, /**< maximum pseudo objective activity */
3067  SCIP_Bool useimplics, /**< should implications be used */
3068  SCIP_Bool* infeasible, /**< pointer to store if the variable domain got empty, infeasible */
3069  SCIP_Bool* tightened /**< pointer to store if the variable domain was tightened */
3070  )
3071 {
3072  SCIP_Real lbobjchg;
3073  SCIP_Real ubobjchg;
3074 
3075  assert(SCIPvarIsBinary(var));
3076  assert(SCIPisLE(scip, lowerbound, maxpseudoobjact));
3077  assert(!SCIPisInfinity(scip, maxpseudoobjact));
3078 
3079  /*@todo Instead of running always over all implications use SCIP_OBJIMPLICS in the same way as for the propagation of
3080  * the minimum activity against the cutoff bound. If so we could use the cliques as well.
3081  */
3082 
3083  /* get contribution of variable by fixing it to its lower bound w.r.t. maximum activity of the objective function */
3084  SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_LOWER, useimplics, &lbobjchg) );
3085  assert(!SCIPisPositive(scip, lbobjchg));
3086 
3087  /* get contribution of variable by fixing it to its upper bound w.r.t. maximum activity of the objective function */
3088  SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_UPPER, useimplics, &ubobjchg) );
3089  assert(!SCIPisPositive(scip, ubobjchg));
3090 
3091  (*infeasible) = FALSE;
3092  (*tightened) = FALSE;
3093 
3094  /* if the maximum activity of the objective function without the contribution of the given variable shrinks below the
3095  * global lower bound, the contribution of the variable is need; hence, we can fix it to corresponding bound globally
3096  */
3097  if( SCIPisFeasLT(scip, maxpseudoobjact + lbobjchg, lowerbound) && SCIPisFeasLT(scip, maxpseudoobjact + ubobjchg, lowerbound) )
3098  {
3099  /* fixing the variable to zero or one leads to decreases of the maximum activity below the lower bound, hence, we
3100  * detected an cutoff
3101  */
3102  (*infeasible) = TRUE;
3103  }
3104  else if( SCIPisFeasLT(scip, maxpseudoobjact + lbobjchg, lowerbound) )
3105  {
3106  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, 1.0, FALSE, infeasible, tightened) );
3107  }
3108  else if( SCIPisFeasLT(scip, maxpseudoobjact + ubobjchg, lowerbound) )
3109  {
3110  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, 0.0, FALSE, infeasible, tightened) );
3111  }
3112 
3113  return SCIP_OKAY;
3114 }
3115 
3116 /** propagates the global domains of the given variable with non-zero objective coefficient against the lower bound
3117  * (c*x >= lowerbound)
3118  */
3119 static
3121  SCIP* scip, /**< SCIP data structure */
3122  SCIP_PROPDATA* propdata, /**< propagator data */
3123  SCIP_VAR* var, /**< variable to propagate */
3124  SCIP_Real lowerbound, /**< lower bound to use */
3125  SCIP_Bool* infeasible, /**< pointer to store if the variable domain got empty, infeasible */
3126  SCIP_Bool* tightened /**< pointer to store if the variable domain was tightened */
3127  )
3128 {
3129  SCIP_Real residual;
3130  SCIP_Real newbd;
3131  SCIP_Real objval;
3132 
3133  objval = SCIPvarGetObj(var);
3134  assert(!SCIPisZero(scip, objval));
3135 
3136  (*tightened) = FALSE;
3137 
3138  /* get residual pseudo objective activity, that is the pseudo objective activity without the given variable */
3139  residual = getMaxObjPseudoactivityResidual(scip, propdata, var);
3140 
3141  if( SCIPisInfinity(scip, residual) )
3142  return SCIP_OKAY;
3143 
3144  /* compute potential mew bound */
3145  newbd = (lowerbound - residual) / objval;
3146 
3147  /**@note In case the variable is integral we force the update of the new bound */
3148 
3149  if( objval > 0.0 )
3150  {
3151  SCIP_Real lb;
3152 
3153  lb = SCIPvarGetLbGlobal(var);
3154 
3155  if( !SCIPvarIsIntegral(var) )
3156  {
3157  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, FALSE, infeasible, tightened) );
3158  }
3159  else if( SCIPisFeasGT(scip, newbd, lb) )
3160  {
3161  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, TRUE, infeasible, tightened) );
3162  }
3163  }
3164  else
3165  {
3166  SCIP_Real ub;
3167 
3168  ub = SCIPvarGetUbGlobal(var);
3169 
3170  if( !SCIPvarIsIntegral(var) )
3171  {
3172  SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, FALSE, infeasible, tightened) );
3173  }
3174  else if( SCIPisFeasLT(scip, newbd, ub) )
3175  {
3176  SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, TRUE, infeasible, tightened) );
3177  }
3178  }
3179 
3180  return SCIP_OKAY;
3181 }
3182 
3183 /** propagates the global lower (dual) bound c*x >= lowerbound */
3184 static
3186  SCIP* scip, /**< SCIP data structure */
3187  SCIP_PROP* prop, /**< propagator */
3188  SCIP_RESULT* result /**< pointer to store the result of the callback method */
3189  )
3190 { /*lint --e{715}*/
3191  SCIP_PROPDATA* propdata;
3192  SCIP_Real lowerbound;
3193  SCIP_Real maxpseudoobjact;
3194  SCIP_Bool cutoff;
3195  int nchgbds;
3196 
3197  assert(result != NULL);
3198 
3199  (*result) = SCIP_DIDNOTRUN;
3200  cutoff = FALSE;
3201  nchgbds = 0;
3202 
3203  propdata = SCIPpropGetData(prop);
3204  assert(propdata != NULL);
3205  assert(propdata->nminactvars > 0 || propdata->nobjintvars > 0);
3206 
3207  /* check if there is a chance to find a reduction */
3208  lowerbound = SCIPgetLowerbound(scip);
3209 
3210  if( SCIPisInfinity(scip, -lowerbound) )
3211  return SCIP_OKAY;
3212 
3213  /* if the lower bound did not change since the last propagation as well as the global bounds of the variables with a
3214  * non-zero objective coefficient we do nothing since there is no new information available
3215  */
3216  if( SCIPisLE(scip, lowerbound, propdata->lastlowerbound) && propdata->maxpseudoobjact < SCIP_INVALID )
3217  return SCIP_OKAY;
3218 
3219  /* updates the pseudo objective activity if necessary */
3220  updateMaxObjPseudoactivity(scip, propdata);
3221 
3222  /* if more than one variable contributes an infinity to the maximal pseudo activity we can do nothing */
3223  assert(propdata->maxpseudoobjact < SCIP_INVALID);
3224  if( propdata->maxpseudoobjactinf > 1 )
3225  return SCIP_OKAY;
3226 
3227  maxpseudoobjact = getMaxObjPseudoactivity(scip, propdata);
3228  assert(!SCIPisInfinity(scip, maxpseudoobjact) || !SCIPisInfinity(scip, lowerbound));
3229 
3230 #ifndef NDEBUG
3231  /* check that the global indices are correct */
3232  checkGlbfirstnonfixed(scip, propdata);
3233 #endif
3234 
3235  /* if the maximum pseudo objective activity is smaller than the lower bound the problem is infeasible */
3236  if( SCIPisDualfeasLT(scip, maxpseudoobjact, lowerbound) )
3237  cutoff = TRUE;
3238  else
3239  {
3240  SCIP_VAR** objintvars;
3241  SCIP_VAR* var;
3242  SCIP_Bool tightened;
3243  int nobjintvars;
3244  int v;
3245 
3246  if( propdata->maxpseudoobjactinf == 0 && !SCIPisInfinity(scip, maxpseudoobjact) )
3247  {
3248  SCIP_VAR** maxactvars;
3249  int nmaxactvars;
3250 
3251  maxactvars = propdata->maxactvars;
3252  nmaxactvars = propdata->nmaxactvars;
3253  assert(nmaxactvars == 0 || maxactvars != NULL);
3254 
3255  for( v = propdata->maxactfirstnonfixed; v < nmaxactvars; ++v )
3256  {
3257  var = maxactvars[v];
3258  assert(var != NULL);
3259  assert(SCIPvarIsBinary(var));
3260 
3261  /* check if the variables is already globally fixed; if so continue with the next potential candidate */
3262  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
3263  continue;
3264 
3265  /* try to propagate variable domain globally */
3266  SCIP_CALL( propagateLowerboundBinvar(scip, var, lowerbound, maxpseudoobjact, propdata->propuseimplics, &cutoff, &tightened) );
3267 
3268  /* the binary variables are sorted in non-increasing manner w.r.t. the absolute value of their objective
3269  * contribution w.r.t. maximum activity of the objective function; These values are the decrease we would
3270  * get with the maximum pseudo objective activity if we fix the variable to its best bound; hence, we can
3271  * stop if for a variable this potential decrease is not enough anymore to fall below the lower bound.
3272  *
3273  * @note In case a fixing was performed. The variable might not be globally fixed right away since this would
3274  * destroy the local internal data structure of a search node; the bound change is in that case pending;
3275  * hence we cannot assert that the variable is globally fixed
3276  */
3277  if( !tightened )
3278  {
3279  assert(!SCIPisInfinity(scip, propdata->maxpseudoobjact));
3280  SCIPdebugMsg(scip, "interrupt pseudo objective propagation w.r.t. lower bound <%.15g> for binary variables after %d from %d binary variables\n",
3281  lowerbound, v, nmaxactvars);
3282  break;
3283  }
3284 
3285  if( cutoff )
3286  break;
3287 
3288  /* update maximum pseudo activity since the previous global bound change might invalidated the maximum
3289  * pseudo activity
3290  */
3291  maxpseudoobjact = getMaxObjPseudoactivity(scip, propdata);
3292  nchgbds++;
3293  }
3294 
3295  /* update globally fixed index if abort criteria was applied */
3296  propdata->maxactfirstnonfixed = v;
3297 
3298  /* check all binary variables which could potentially be fixed */
3299  for( ; v < nmaxactvars && maxpseudoobjact - lowerbound < propdata->maxactchgs[v] && !cutoff; ++v )
3300  {
3301  var = maxactvars[v];
3302  assert(var != NULL);
3303  assert(SCIPvarIsBinary(var));
3304 
3305  /* check if the variables is already globally fixed; if so continue with the potential candidate */
3306  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
3307  continue;
3308 
3309  /* propagates the cutoff bound for the given binary variable */
3310  SCIP_CALL( propagateLowerboundBinvar(scip, var, lowerbound, maxpseudoobjact, propdata->propuseimplics, &cutoff, &tightened) );
3311 
3312  if( tightened )
3313  {
3314  /* update maximum pseudo activity since the previous global bound change might invalidated the maximum
3315  * pseudo activity
3316  */
3317  maxpseudoobjact = getMaxObjPseudoactivity(scip, propdata);
3318  nchgbds++;
3319  }
3320  }
3321 
3322 #if 0 /* might fail, but is not a real error, still need to investigate */
3323 #ifndef NDEBUG
3324  /* check that the abort criteria for the binary variables works */
3325  for( ; v < nmaxactvars && !cutoff; ++v )
3326  {
3327  var = maxactvars[v];
3328  assert(var != NULL);
3329  assert(SCIPvarIsBinary(var));
3330 
3331  /* check if the variables is already globally fixed; if so continue with the next potential candidate */
3332  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
3333  continue;
3334 
3335  /* try to propagate variable domain globally */
3336  SCIP_CALL( propagateLowerboundBinvar(scip, var, lowerbound, maxpseudoobjact, propdata->propuseimplics, &cutoff, &tightened) );
3337  assert(!tightened);
3338  assert(!cutoff);
3339  }
3340 #endif
3341 #endif
3342  }
3343 
3344  objintvars = propdata->objintvars;
3345  nobjintvars = propdata->nobjintvars;
3346  assert(nobjintvars == 0 || objintvars != NULL);
3347 
3348  /* propagate c*x >= lowerbound for non-binary variables */
3349  for( v = 0; v < nobjintvars && !cutoff; ++v )
3350  {
3351  var = objintvars[v];
3352  assert(var != NULL);
3353  assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
3354 
3355  /* try to propagate variable domain globally */
3356  SCIP_CALL( propagateLowerboundVar(scip, propdata, var, lowerbound, &cutoff, &tightened) );
3357 
3358  if( tightened )
3359  nchgbds++;
3360  }
3361  }
3362 
3363  /* evaluate propagation results */
3364  if( cutoff )
3365  {
3366  /* we are done with solving since a global bound change is infeasible: cutoff root node */
3367  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
3368  (*result) = SCIP_CUTOFF;
3369  }
3370  else if( nchgbds > 0 )
3371  (*result) = SCIP_REDUCEDDOM;
3372 
3373  /* remember the lower bound which we already propagated */
3374  propdata->lastlowerbound = lowerbound;
3375 
3376  return SCIP_OKAY;
3377 }
3378 
3379 
3380 /*
3381  * Callback methods of propagator
3382  */
3383 
3384 /** copy method for propagator plugins (called when SCIP copies plugins) */
3385 static
3386 SCIP_DECL_PROPCOPY(propCopyPseudoobj)
3387 { /*lint --e{715}*/
3388  assert(scip != NULL);
3389  assert(prop != NULL);
3390  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
3391 
3392  /* call inclusion method of propagator */
3394 
3395  return SCIP_OKAY;
3396 }
3397 
3398 /** destructor of propagator to free user data (called when SCIP is exiting) */
3399 static
3400 SCIP_DECL_PROPFREE(propFreePseudoobj)
3401 { /*lint --e{715}*/
3402  SCIP_PROPDATA* propdata;
3403 
3404  /* free propagator data */
3405  propdata = SCIPpropGetData(prop);
3406  SCIPfreeBlockMemory(scip, &propdata);
3407  SCIPpropSetData(prop, NULL);
3408 
3409  return SCIP_OKAY;
3410 }
3411 
3412 
3413 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
3414 static
3415 SCIP_DECL_PROPINITSOL(propInitsolPseudoobj)
3416 {
3417  SCIP_PROPDATA* propdata;
3418 
3419  propdata = SCIPpropGetData(prop);
3420  assert(propdata != NULL);
3422  /* do nothing if active pricer are present and force flag is not TRUE */
3423  if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
3424  return SCIP_OKAY;
3425 
3426  /* if active pricer are present we want to catch the variable added event */
3427  if( SCIPgetNActivePricers(scip) > 0 )
3428  {
3429  assert(!propdata->catchvaradded);
3430  SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_VARADDED, propdata->eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) );
3431  propdata->catchvaradded = TRUE;
3432  }
3433 
3434  return SCIP_OKAY;
3435 }
3436 
3437 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
3438 static
3439 SCIP_DECL_PROPEXITSOL(propExitsolPseudoobj)
3440 { /*lint --e{715}*/
3441  SCIP_PROPDATA* propdata;
3442 
3443  propdata = SCIPpropGetData(prop);
3444  assert(propdata != NULL);
3446  if( propdata->catchvaradded )
3447  {
3448  /* drop the variable added event */
3449  SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_VARADDED, propdata->eventhdlr, (SCIP_EVENTDATA*)propdata, -1) );
3450  propdata->catchvaradded = FALSE;
3451  }
3452 
3453  /* free propagator data */
3454  SCIP_CALL( propdataExit(scip, propdata) );
3455 
3456  return SCIP_OKAY;
3457 }
3458 
3459 
3460 /** presolving method of propagator */
3461 static
3462 SCIP_DECL_PROPPRESOL(propPresolPseudoobj)
3463 { /*lint --e{715}*/
3464 
3465  SCIP_PROPDATA* propdata;
3466  SCIP_VAR** vars;
3467  SCIP_Real cutoffbound;
3468  SCIP_Real pseudoobjval;
3469  int oldnchgbds;
3470  int nvars;
3471  int v;
3472 
3473  assert(result != NULL);
3474 
3475  propdata = SCIPpropGetData(prop);
3476  assert(propdata != NULL);
3477 
3478  (*result) = SCIP_DIDNOTRUN;
3479 
3480  /* do nothing if active pricer are present and force flag is not TRUE */
3481  if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
3482  return SCIP_OKAY;
3483 
3484  /* do nothing if objective propagation is not allowed */
3485  if( !SCIPallowObjProp(scip) )
3486  return SCIP_OKAY;
3487 
3488  pseudoobjval = SCIPgetGlobalPseudoObjval(scip);
3489  if( SCIPisInfinity(scip, -pseudoobjval) )
3490  return SCIP_OKAY;
3491 
3492  cutoffbound = SCIPgetCutoffbound(scip);
3493  if( SCIPisInfinity(scip, cutoffbound) )
3494  return SCIP_OKAY;
3495 
3496  if( SCIPisGE(scip, pseudoobjval, cutoffbound) )
3497  {
3498  (*result) = SCIP_CUTOFF;
3499  return SCIP_OKAY;
3500  }
3501 
3502  /* only propagate if a new cutoff bound or global pseudo objective value is available */
3503  if( cutoffbound < propdata->cutoffbound || pseudoobjval > propdata->glbpseudoobjval )
3504  {
3505  SCIP_Real objval;
3506  SCIP_Bool tightened;
3507 
3508  (*result) = SCIP_DIDNOTFIND;
3509  oldnchgbds = *nchgbds;
3510 
3511  /* get the problem variables */
3512  vars = SCIPgetVars(scip);
3513  nvars = SCIPgetNVars(scip);
3514 
3515  /* scan the variables for pseudoobj bound reductions
3516  * (loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array)
3517  */
3518  for( v = nvars - 1; v >= 0; --v )
3519  {
3520  objval = SCIPvarGetObj(vars[v]);
3521 
3522  if( SCIPisZero(scip, objval) )
3523  continue;
3524 
3525  SCIP_CALL( propagateCutoffboundVar(scip, NULL, vars[v], -1, objval, cutoffbound, pseudoobjval, FALSE, &tightened) );
3526 
3527  if( tightened )
3528  (*nchgbds)++;
3529  }
3530 
3531  /* evaluate if bound change was detected */
3532  if( *nchgbds > oldnchgbds )
3533  (*result) = SCIP_SUCCESS;
3534 
3535  /* store the old values */
3536  propdata->cutoffbound = cutoffbound;
3537  propdata->glbpseudoobjval = pseudoobjval;
3538  propdata->glbpropagated = TRUE;
3539  }
3540 
3541  return SCIP_OKAY;
3542 }
3543 
3544 /** execution method of propagator */
3545 static
3546 SCIP_DECL_PROPEXEC(propExecPseudoobj)
3547 { /*lint --e{715}*/
3548  SCIP_PROPDATA* propdata;
3549 
3550  propdata = SCIPpropGetData(prop);
3551  assert(propdata != NULL);
3553  (*result) = SCIP_DIDNOTRUN;
3554 
3555  if( SCIPinProbing(scip) )
3556  return SCIP_OKAY;
3557 
3558  if( proptiming == SCIP_PROPTIMING_DURINGLPLOOP && SCIPgetDepth(scip) != 0 )
3559  return SCIP_OKAY;
3560 
3561  /* do nothing if active pricer are present and force flag is not TRUE */
3562  if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
3563  return SCIP_OKAY;
3564 
3565  /* do not run if propagation w.r.t. objective is not allowed */
3566  if( !SCIPallowObjProp(scip) )
3567  return SCIP_OKAY;
3568 
3569  /* check if enough new variable are added (due to column generation to reinitialized the propagator data) */
3570  if( !propdata->initialized || propdata->nnewvars > propdata->maxnewvars )
3571  {
3572  /* free current propdata data */
3573  SCIP_CALL( propdataExit(scip, propdata) );
3574 
3575  /* initialize propdata data from scratch */
3576  SCIP_CALL( propdataInit(scip, propdata) );
3577  }
3578 
3579  /* nothing to do for zero objective */
3580  if( propdata->nminactvars == 0 && propdata->nmaxactvars == 0 && propdata->nobjintvars == 0 )
3581  return SCIP_OKAY;
3582 
3583  /* propagate c*x <= cutoff */
3584  SCIP_CALL( propagateCutoffbound(scip, prop, result) );
3585 
3586  if( (*result) != SCIP_CUTOFF && (propdata->nmaxactvars > 0 || propdata->nobjintvars > 0) && SCIPgetStage(scip) == SCIP_STAGE_SOLVING )
3587  {
3588  SCIP_RESULT dualresult;
3589 
3590  /* propagates the global lower (dual) bound c*x >= lowerbound */
3591  SCIP_CALL( propagateLowerbound(scip, prop, &dualresult) );
3592 
3593  if( dualresult == SCIP_REDUCEDDOM || dualresult == SCIP_CUTOFF )
3594  (*result) = dualresult;
3595  }
3596 
3597  return SCIP_OKAY;
3598 }
3599 
3600 /** propagation conflict resolving method of propagator */
3601 static
3602 SCIP_DECL_PROPRESPROP(propRespropPseudoobj)
3603 { /*lint --e{715}*/
3604  SCIP_PROPDATA* propdata;
3605  SCIP_Real cutoffbound;
3606 
3607  assert(!SCIPisEQ(scip, SCIPvarGetLbGlobal(infervar), SCIPvarGetUbGlobal(infervar)));
3609  propdata = SCIPpropGetData(prop);
3610  assert(propdata != NULL);
3611 
3612  cutoffbound = SCIPgetCutoffbound(scip);
3613  assert(!SCIPisInfinity(scip, cutoffbound));
3614  assert(infervar != NULL);
3615 
3616  SCIPdebugMsg(scip, "resolve bound change <%s> %s <%g>(%g), cutoff bound <%g>\n", SCIPvarGetName(infervar),
3617  boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE),
3618  SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, FALSE), cutoffbound);
3619 
3620  /* resolve the propagation of the inference variable w.r.t. required minactivity */
3621  SCIP_CALL( resolvePropagation(scip, propdata, cutoffbound, infervar, inferinfo, boundtype, bdchgidx) );
3622 
3623  (*result) = SCIP_SUCCESS;
3624 
3625  return SCIP_OKAY;
3626 }
3627 
3628 
3629 /*
3630  * Event handler
3631  */
3632 
3633 /** execution method of bound change event handler */
3634 static
3635 SCIP_DECL_EVENTEXEC(eventExecPseudoobj)
3636 { /*lint --e{715}*/
3637  SCIP_PROPDATA* propdata;
3638  SCIP_EVENTTYPE eventtype;
3639 
3640  propdata = (SCIP_PROPDATA*)eventdata;
3641  assert(propdata != NULL);
3642 
3643  assert(eventhdlr != NULL);
3644  assert(eventdata != NULL);
3645  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
3646  assert(event != NULL);
3647 
3648  eventtype = SCIPeventGetType(event);
3649 
3650  switch( eventtype )
3651  {
3654  /* if bound got relaxed we need to start up front for trial of bound tightening */
3655  propdata->firstnonfixed = 0;
3656  break;
3658  propdata->nnewvars++;
3659  break;
3660  default:
3661  assert(eventtype == SCIP_EVENTTYPE_GLBCHANGED || eventtype == SCIP_EVENTTYPE_GUBCHANGED);
3662 
3663  /* invalidate the maximum pseudo objective activity */
3664  propdata->maxpseudoobjact = SCIP_INVALID;
3665  propdata->maxpseudoobjactinf = 0;
3666  }
3667 
3668  return SCIP_OKAY;
3669 }
3670 
3671 
3672 /*
3673  * propagator specific interface methods
3674  */
3675 
3676 /** creates the pseudo objective function propagator and includes it in SCIP */
3678  SCIP* scip /**< SCIP data structure */
3679  )
3680 {
3681  SCIP_PROPDATA* propdata;
3682  SCIP_PROP* prop;
3684 
3685  /* create pseudoobj propagator data */
3686  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
3687 
3688  /* reset propagator data structure */
3689  propdataReset(scip, propdata);
3690 
3691  propdata->eventhdlr = NULL;
3692  /* include event handler for gloabl bound change events and variable added event (in case of pricing) */
3693  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
3694  eventExecPseudoobj, NULL) );
3695 
3696  if( propdata->eventhdlr == NULL )
3697  {
3698  SCIPerrorMessage("event handler for pseudo objective propagator not found\n");
3699  return SCIP_PLUGINNOTFOUND;
3700  }
3701 
3702  /* include propagator */
3704  propExecPseudoobj,
3705  propdata) );
3706  assert(prop != NULL);
3707 
3708  /* set optional callbacks via setter functions */
3709  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyPseudoobj) );
3710  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreePseudoobj) );
3711  SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolPseudoobj) );
3712  SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolPseudoobj) );
3714  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropPseudoobj) );
3715 
3716  /* add pseudoobj propagator parameters */
3717  SCIP_CALL( SCIPaddIntParam(scip,
3718  "propagating/" PROP_NAME "/minuseless",
3719  "minimal number of successive non-binary variable propagator whithout a bound reduction before aborted",
3720  &propdata->minuseless, TRUE, DEFAULT_MINUSELESS, 0, INT_MAX, NULL, NULL) );
3721 
3723  "propagating/" PROP_NAME "/maxvarsfrac",
3724  "maximal fraction of non-binary variables with non-zero objective without a bound reduction before aborted",
3725  &propdata->maxvarsfrac, TRUE, DEFAULT_MAXVARSFRAC, 0.0, 1.0, NULL, NULL) );
3726 
3728  "propagating/" PROP_NAME "/propfullinroot",
3729  "do we want to propagate all non-binary variables if we are propagating the root node",
3730  &propdata->propfullinroot, TRUE, DEFAULT_PROPFULLINROOT, NULL, NULL) );
3731 
3733  "propagating/" PROP_NAME "/propcutoffbound",
3734  "propagate new cutoff bound directly globally",
3735  &propdata->propcutoffbound, TRUE, DEFAULT_PROPCUTOFFBOUND, NULL, NULL) );
3736 
3738  "propagating/" PROP_NAME "/force",
3739  "should the propagator be forced even if active pricer are present?",
3740  &propdata->force, TRUE, DEFAULT_FORCE, NULL, NULL) );
3741 
3742  SCIP_CALL( SCIPaddIntParam(scip,
3743  "propagating/" PROP_NAME "/maxnewvars",
3744  "number of variable added after the propgatore is reinitialized?",
3745  &propdata->maxnewvars, TRUE, DEFAULT_MAXNEWVARS, 0, INT_MAX, NULL, NULL) );
3746 
3748  "propagating/" PROP_NAME "/propuseimplics",
3749  "use implications to strengthen the propagation of binary variable (increasing the objective change)?",
3750  &propdata->propuseimplics, TRUE, DEFAULT_PROPUSEIMPLICS, NULL, NULL) );
3751 
3753  "propagating/" PROP_NAME "/respropuseimplics",
3754  "use implications to strengthen the resolve propagation of binary variable (increasing the objective change)?",
3755  &propdata->respropuseimplics, TRUE, DEFAULT_RESPROPUSEIMPLICS, NULL, NULL) );
3756 
3757  SCIP_CALL( SCIPaddIntParam(scip,
3758  "propagating/" PROP_NAME "/maximplvars",
3759  "maximum number of binary variables the implications are used if turned on (-1: unlimited)?",
3760  &propdata->maximplvars, TRUE, DEFAULT_MAXIMPLVARS, -1, INT_MAX, NULL, NULL) );
3761 
3762  return SCIP_OKAY;
3763 }
3764 
3765 /** propagates the cutoff bound for the given variables */
3767  SCIP* scip, /**< SCIP data structure */
3768  SCIP_PROP* prop, /**< propagator, or NULL */
3769  SCIP_VAR* var, /**< variables to propagate */
3770  SCIP_Real cutoffbound, /**< cutoff bound to use */
3771  SCIP_Real pseudoobjval, /**< pseudo objective value to use */
3772  SCIP_Bool* tightened /**< pointer to if the domain was tightened */
3773  )
3774 {
3775  SCIP_Real objval;
3776 
3777  objval = SCIPvarGetObj(var);
3778 
3779  SCIP_CALL( propagateCutoffboundVar(scip, prop, var, -1, objval, cutoffbound, pseudoobjval, TRUE, tightened) );
3780 
3781  return SCIP_OKAY;
3782 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip.c:7773
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21975
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
static SCIP_RETCODE adjustCutoffbound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_HASHTABLE *addedvars, SCIP_Real *cutoffbound)
static SCIP_RETCODE getMinactImplicObjchg(SCIP *scip, SCIP_VAR *var, SCIP_OBJIMPLICS *objimplics, SCIP_BDCHGIDX *bdchgidx, SCIP_BOUNDTYPE bound, SCIP_Bool local, SCIP_Real *objchg)
SCIP_BOUNDTYPE SCIPvarGetWorstBoundType(SCIP_VAR *var)
Definition: var.c:17294
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:45508
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:10785
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3304
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21958
#define PROP_FREQ
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip.c:19346
SCIP_VAR ** objvars
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46320
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:814
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46333
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip.c:19206
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2253
#define PROP_PRIORITY
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:40502
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42726
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip.h:21993
Pseudo objective propagator.
static SCIP_RETCODE propagateLowerbound(SCIP *scip, SCIP_PROP *prop, SCIP_RESULT *result)
#define infinity
Definition: gastrans.c:71
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17169
static SCIP_RETCODE propdataExit(SCIP *scip, SCIP_PROPDATA *propdata)
static long bound
static SCIP_RETCODE collectMinactVar(SCIP *scip, SCIP_VAR *var, SCIP_OBJIMPLICS **objimplics, SCIP_Bool useimplics, SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedlbvars, SCIP_Bool *collectedubvars, int nbinobjvars, SCIP_VAR **contributors, SCIP_HASHTABLE *uselesscliques, SCIP_Bool *collect)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:46110
static SCIP_DECL_PROPINITSOL(propInitsolPseudoobj)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17225
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46037
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17532
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.c:22900
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:8561
#define DEFAULT_MAXNEWVARS
void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip.c:18461
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16735
#define DEFAULT_PROPCUTOFFBOUND
static void updateMaxObjPseudoactivity(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46372
#define SCIP_PROPTIMING_DURINGLPLOOP
Definition: type_timing.h:57
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2764
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:278
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip.c:5690
#define DEFAULT_MINUSELESS
static SCIP_DECL_SORTPTRCOMP(objimplicsComp)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:41023
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:46050
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:46122
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip.c:26907
static SCIP_RETCODE addConflictBinvar(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_OBJIMPLICS *objimplics, SCIP_HASHTABLE *addedvars, SCIP_Bool respropuseimplics, SCIP_Real *reqpseudoobjval)
static SCIP_RETCODE getMaxactObjchg(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE bound, SCIP_Bool useimplics, SCIP_Real *objchg)
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16862
#define SCIP_EVENTTYPE_GLBCHANGED
Definition: type_event.h:61
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip.c:26811
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2902
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45985
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
static SCIP_RETCODE propagateCutoffbound(SCIP *scip, SCIP_PROP *prop, SCIP_RESULT *result)
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21956
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip.c:1010
#define PROP_DELAY
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip.c:40699
static void resetContributors(SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedvars, SCIP_VAR **contributors, int ncontributors)
#define DEFAULT_FORCE
static SCIP_Real getMaxObjPseudoactivityResidual(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var)
#define SCIPdebugMsgPrint
Definition: scip.h:452
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4237
#define EVENTHDLR_DESC
SCIP_RETCODE SCIPpropagateCutoffboundVar(SCIP *scip, SCIP_PROP *prop, SCIP_VAR *var, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, SCIP_Bool *tightened)
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17521
int SCIPgetNContVars(SCIP *scip)
Definition: scip.c:11860
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip.c:26840
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2014
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2996
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:64
#define PROP_PRESOLTIMING
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip.c:26789
static SCIP_RETCODE addConflictBounds(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real *reqpseudoobjval)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17179
static SCIP_RETCODE collectMinactObjchg(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE bound, SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedvars, int nbinobjvars, SCIP_VAR **contributors, SCIP_HASHTABLE *uselesscliques, int *ncontributors, SCIP_Real *objchg)
static SCIP_RETCODE objimplicsDelPos(SCIP *scip, SCIP_OBJIMPLICS *objimplics, int pos)
#define SCIPerrorMessage
Definition: pub_message.h:45
static SCIP_RETCODE propagateCutoffboundBinvar(SCIP *scip, SCIP_PROP *prop, SCIP_VAR *var, int pos, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, SCIP_Bool *tightened, SCIP_Bool *cutoff, SCIP_Bool local)
int SCIPgetCutoffdepth(SCIP *scip)
Definition: scip.c:41063
static SCIP_RETCODE getMaxactImplicObjchg(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE bound, SCIP_Real *objchg)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45998
SCIP_Real maxobjchg
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45753
static SCIP_RETCODE collectMinactImplicVars(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE bound, SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedvars, int nbinobjvars, SCIP_VAR **contributors, SCIP_HASHTABLE *uselesscliques, int *ncontributors, SCIP_Real *objchg)
#define MAX_CLIQUELENGTH
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16555
static SCIP_DECL_PROPPRESOL(propPresolPseudoobj)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2797
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:23229
#define PROP_DESC
#define NULL
Definition: lpi_spx1.cpp:137
#define PROP_PRESOL_MAXROUNDS
void SCIPsortDownPtrPtr(void **ptrarray1, void **ptrarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define REALABS(x)
Definition: def.h:169
#define SCIP_EVENTTYPE_UBRELAXED
Definition: type_event.h:66
#define DEFAULT_PROPUSEIMPLICS
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Real cutoffbound, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
static SCIP_RETCODE dropObjEvent(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var)
#define SCIP_CALL(x)
Definition: def.h:316
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:42550
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46359
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.c:23013
static SCIP_DECL_PROPCOPY(propCopyPseudoobj)
void SCIPhashtableRemoveAll(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2461
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46346
static SCIP_RETCODE objimplicsFree(SCIP *scip, SCIP_OBJIMPLICS **objimplics)
static SCIP_DECL_PROPFREE(propFreePseudoobj)
static SCIP_RETCODE propagateCutoffboundGlobally(SCIP *scip, SCIP_PROP *prop, int *nchgbds, SCIP_Bool *cutoff)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21991
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17479
static SCIP_DECL_PROPEXITSOL(propExitsolPseudoobj)
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:40434
static SCIP_DECL_PROPRESPROP(propRespropPseudoobj)
static SCIP_RETCODE getMinactObjchg(SCIP *scip, SCIP_VAR *var, SCIP_OBJIMPLICS *objimplics, SCIP_BDCHGIDX *bdchgidx, SCIP_BOUNDTYPE bound, SCIP_Bool local, SCIP_Real *objchg)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:959
static SCIP_Real getMaxObjPseudoactivityResidualValue(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Real contrib)
#define DEFAULT_PROPFULLINROOT
static void calcMaxObjPseudoactivity(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE propdataInit(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE collectMaxactVar(SCIP *scip, SCIP_VAR *var, SCIP_Bool useimplics, SCIP_Real *objchg, SCIP_Bool *isnotzero)
static SCIP_RETCODE objimplicsCreate(SCIP *scip, SCIP_OBJIMPLICS **objimplics, SCIP_VAR **objvars, SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedlbvars, SCIP_Bool *collectedubvars, SCIP_Real maxlbobjchg, SCIP_Real maxubobjchg, int nlbimpls, int nubimpls)
static SCIP_RETCODE propagateCutoffboundBinvars(SCIP *scip, SCIP_PROP *prop, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, int *nfixedvars, SCIP_Bool *cutoff)
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42321
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17447
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3217
#define MAX(x, y)
Definition: tclique_def.h:75
static SCIP_Real getVarObjchg(SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BOUNDTYPE bound)
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11249
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3316
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:40468
static SCIP_DECL_HASHKEYEQ(cliqueIsHashkeyEq)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17017
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip.c:7645
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:40548
int SCIPgetNObjVars(SCIP *scip)
Definition: scip.c:11908
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:46061
static SCIP_RETCODE getConflictImplics(SCIP *scip, SCIP_VAR **vars, int start, int end, SCIP_BDCHGIDX *bdchgidx, SCIP_HASHTABLE *addedvars, SCIP_Real *reqpseudoobjval, SCIP_Bool *foundimplics)
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17493
static void checkImplicsApplied(SCIP *scip, SCIP_VAR *var)
static SCIP_RETCODE catchObjEvent(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var)
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip.c:7725
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35163
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:887
#define DEFAULT_RESPROPUSEIMPLICS
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2064
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11680
static SCIP_Real collectMinactImplicVar(SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedvars, int nbinobjvars, SCIP_VAR **contributors, int *ncontributors)
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17464
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip.c:7806
#define DEFAULT_MAXVARSFRAC
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46024
#define PROP_PRESOL_PRIORITY
#define EVENTHDLR_NAME
SCIP_RETCODE SCIPincludePropPseudoobj(SCIP *scip)
int SCIPgetNCliques(SCIP *scip)
Definition: scip.c:24566
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11635
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip.c:7709
static SCIP_DECL_HASHKEYVAL(cliqueGetHashkeyVal)
static void propdataReset(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:18427
#define SCIP_Real
Definition: def.h:145
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:38
#define MIN(x, y)
Definition: memory.c:75
SCIP_Real SCIPgetGlobalPseudoObjval(SCIP *scip)
Definition: scip.c:29088
static SCIP_RETCODE propagateLowerboundVar(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_Real lowerbound, SCIP_Bool *infeasible, SCIP_Bool *tightened)
static SCIP_DECL_HASHGETKEY(cliqueGetHashkey)
#define SCIP_INVALID
Definition: def.h:165
static SCIP_RETCODE propagateCutoffboundVar(SCIP *scip, SCIP_PROP *prop, SCIP_VAR *var, int inferinfo, SCIP_Real objchg, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, SCIP_Bool local, SCIP_Bool *tightened)
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip.c:7661
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:735
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:745
SCIP_BOUNDTYPE SCIPvarGetBestBoundType(SCIP_VAR *var)
Definition: var.c:17281
#define PROP_NAME
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2365
static SCIP_DECL_EVENTEXEC(eventExecPseudoobj)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46098
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46011
static void checkGlbfirstnonfixed(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17235
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:21976
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3294
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:23349
static SCIP_RETCODE dropVarEvents(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2845
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:89
SCIP_Real SCIPgetPseudoObjval(SCIP *scip)
Definition: scip.c:29113
#define SCIP_EVENTTYPE_GUBCHANGED
Definition: type_event.h:62
SCIP_Bool SCIPisDualfeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46506
static SCIP_DECL_PROPEXEC(propExecPseudoobj)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16746
#define SCIP_EVENTTYPE_VARADDED
Definition: type_event.h:56
#define DEFAULT_MAXIMPLVARS
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.c:4293
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
Definition: scip.c:27160
SCIP_Bool SCIPallowObjProp(SCIP *scip)
Definition: scip.c:25551
static SCIP_Real getMaxObjPseudoactivity(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE propagateLowerboundBinvar(SCIP *scip, SCIP_VAR *var, SCIP_Real lowerbound, SCIP_Real maxpseudoobjact, SCIP_Bool useimplics, SCIP_Bool *infeasible, SCIP_Bool *tightened)
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.c:4211
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16842
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:134
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.c:7608
int SCIPcliqueGetId(SCIP_CLIQUE *clique)
Definition: implics.c:3326
#define PROP_TIMING
#define SCIP_EVENTTYPE_BOUNDRELAXED
Definition: type_event.h:107