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