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-2018 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop_pseudoobj.c
17  * @brief Pseudo objective propagator
18  * @author Tobias Achterberg
19  * @author Stefan Heinz
20  *
21  * This propagator propagates the objective function using the cutoff bound and the pseudo objective value. The pseudo
22  * objective value can be seen as minimum activity of the linear objective function. Using this, this propagator checks
23  * if variables with non-zero objective coefficients can exceed the cutoff bound. If this is the case the corresponding
24  * bound can be tightened.
25  *
26  * @todo use the complete implication to initialize the objective implication data structure
27  */
28 
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
30 
31 #include "blockmemshell/memory.h"
32 #include "scip/prop_pseudoobj.h"
33 #include "scip/pub_event.h"
34 #include "scip/pub_implics.h"
35 #include "scip/pub_message.h"
36 #include "scip/pub_misc.h"
37 #include "scip/pub_misc_sort.h"
38 #include "scip/pub_prop.h"
39 #include "scip/pub_var.h"
40 #include "scip/scip_conflict.h"
41 #include "scip/scip_event.h"
42 #include "scip/scip_general.h"
43 #include "scip/scip_lp.h"
44 #include "scip/scip_mem.h"
45 #include "scip/scip_message.h"
46 #include "scip/scip_numerics.h"
47 #include "scip/scip_param.h"
48 #include "scip/scip_pricer.h"
49 #include "scip/scip_prob.h"
50 #include "scip/scip_probing.h"
51 #include "scip/scip_prop.h"
52 #include "scip/scip_solvingstats.h"
53 #include "scip/scip_tree.h"
54 #include "scip/scip_var.h"
55 #include <string.h>
56 
57 #define PROP_NAME "pseudoobj"
58 #define PROP_DESC "pseudo objective function propagator"
59 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP
60 #define PROP_PRIORITY 3000000 /**< propagator priority */
61 #define PROP_FREQ 1 /**< propagator frequency */
62 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
63 #define PROP_PRESOL_PRIORITY +6000000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
64 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
65  * limit) */
66 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */
67 
68 #define EVENTHDLR_NAME "pseudoobj"
69 #define EVENTHDLR_DESC "bound change event handler for pseudo objective function propagator"
70 
71 #define DEFAULT_MINUSELESS 100 /**< minimal number of successive non-binary variable propagator whithout a
72  * bound reduction before aborted */
73 #define DEFAULT_MAXVARSFRAC 0.1 /**< maximal fraction of non-binary variables with non-zero objective
74  * without a bound reduction before aborted */
75 #define DEFAULT_PROPFULLINROOT TRUE /**< do we want to propagate all non-binary variables if we are propagating the root node? */
76 #define DEFAULT_PROPCUTOFFBOUND TRUE /**< propagate new cutoff bound directly globally */
77 #define DEFAULT_FORCE FALSE /**< should the propagator be forced even if active pricer are present? Note that
78  * can be done if it is known that the pseudo objective activity is given by
79  * the zero bound for all variables which are currently not present in the
80  * problem */
81 #define DEFAULT_MAXNEWVARS 1000 /**< number of variable added after the propagator is reinitialized? */
82 #define DEFAULT_PROPUSEIMPLICS TRUE /**< use implications to strengthen the propagation of binary variable (increasing the objective change)? */
83 #define DEFAULT_RESPROPUSEIMPLICS TRUE /**< use implications to strengthen the resolve propagation of binary variable (increasing the objective change)? */
84 #define DEFAULT_MAXIMPLVARS 50000 /**< maximum number of binary variables the implications are used if turned on (-1: unlimited)? */
85 
86 
87 /*
88  * Data structures
89  */
90 
91 /** implication data structure for objective contributions of a binary variable */
92 struct SCIP_ObjImplics
93 {
94  SCIP_VAR** objvars; /**< variables y in implications y == 0 or y == 1, first we store the
95  * implications by x == 0 and second the implications x == 1 */
96  SCIP_Real maxobjchg; /**< maximum objective contribution if variables x is fixed to zero or one */
97  int nlbimpls; /**< number of all implications result through for x == 0 */
98  int nubimpls; /**< number of all implications result through for x == 1 */
99  int size; /**< size of the objvars array */
100 };
101 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) */
104 /** propagator data */
105 struct SCIP_PropData
106 {
107  SCIP_EVENTHDLR* eventhdlr; /**< event handler for global bound change events */
108  SCIP_VAR** minactvars; /**< binary variables with non-zero objective contribution w.r.t. minimum activity of the objective function */
109  SCIP_OBJIMPLICS** minactimpls; /**< implication data structure for the binary variables w.r.t. minimum activity */
110  SCIP_VAR** maxactvars; /**< binary variables with non-zero objective contribution w.r.t. maximum activity of the objective function */
111  SCIP_Real* maxactchgs; /**< the maximal potential change of the objective if the binary variable
112  * is fixed to its best bound w.r.t. maximum activity of the objective function */
113 
114  SCIP_VAR** objintvars; /**< non-binary variable with non-zero objective coefficient */
115  SCIP_HASHTABLE* addedvars; /**< hash table used during resolving of a bound change (conflict analysis) */
116  SCIP_Real lastlowerbound; /**< last lower bound which was propagated */
117  SCIP_Real cutoffbound; /**< last cutoff bound used for propagation */
118  SCIP_Real glbpseudoobjval; /**< last global pseudo objective used in presolving */
119  SCIP_Real maxvarsfrac; /**< maximal fraction of non-binary variables with non-zero objective
120  * without a bound reduction before aborted
121  */
122  SCIP_Real maxpseudoobjact; /**< maximal global pseudo objective activity */
123  int maxpseudoobjactinf; /**< number of coefficients contributing with infinite value to maxpseudoobjact */
124  int nminactvars; /**< number of binary variables with non-zero objective contribution w.r.t. minimum activity of the objective function */
125  int nmaxactvars; /**< number of binary variables with non-zero objective contribution w.r.t. maximum activity of the objective function */
126  int nobjintvars; /**< number of non-binary variables with non-zero objective */
127  int minuseless; /**< minimal number of successive non-binary variable propagator whithout
128  * a bound reduction before aborted
129  */
130  int lastvarnum; /**< last non-binary variable number that was looked at */
131  int glbfirstnonfixed; /**< index of first globally non-fixed binary variable in minactvars array */
132  int maxactfirstnonfixed;/**< index of first globally non-fixed binary variable in maxctvars array */
133  int firstnonfixed; /**< index of first locally non-fixed binary variable in minactvars array */
134  int nnewvars; /**< counter for counting number of new variables added */
135  int maxnewvars; /**< number of variable added after the propagator is reinitialized? */
136  int maximplvars; /**< maximum number of binary variables the implications are used if turned on (-1: unlimited)? */
137  int minactsize; /**< size of minactvars and minactimpls array */
138  int maxactsize; /**< size of maxactvars and maxactchgs array */
139  int objintvarssize; /**< size of objintvars array*/
140  SCIP_Bool glbpropagated; /**< are global domains propagated */
141  SCIP_Bool propfullinroot; /**< do we want to propagate all non-binary variables if we are propagating the root node */
142  SCIP_Bool propcutoffbound; /**< propagate new cutoff bound directly globally */
143  SCIP_Bool force; /**< should the propagator be forced even if active pricer are present? */
144  SCIP_Bool catchvaradded; /**< do we catch the variable added event? */
145  SCIP_Bool propuseimplics; /**< use implications to strengthen the propagation of binary variable (increasing the objective change)? */
146  SCIP_Bool respropuseimplics; /**< use implications to strengthen the resolve propagation of binary variable (increasing the objective change)? */
147  SCIP_Bool initialized; /**< is propagator data structure initialized */
148 };
149 
150 /*
151  * Debug methods
152  */
153 
154 #ifndef NDEBUG
155 /** check that the implications are applied for a globally fixed variable */
156 static
158  SCIP* scip, /**< SCIP data structure */
159  SCIP_VAR* var /**< variable to check the implications */
160  )
161 {
162  SCIP_VAR** vars;
163  SCIP_Real* bounds;
164  SCIP_BOUNDTYPE* boundtypes;
165  SCIP_Bool varfixing;
166  int nvars;
167  int v;
168 
169  /* check that the given variable is locally or globally fixed */
170  assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5);
171 
172  /* get fixed value */
173  varfixing = SCIPvarGetLbGlobal(var) > 0.5;
174 
175  vars = SCIPvarGetImplVars(var, varfixing);
176  nvars = SCIPvarGetNImpls(var, varfixing);
177  bounds = SCIPvarGetImplBounds(var, varfixing);
178  boundtypes = SCIPvarGetImplTypes(var, varfixing);
179 
180  /* check that each implication was applied */
181  for( v = 0; v < nvars; ++v )
182  {
183  if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
184  {
185  SCIP_Real lb;
186 
187  lb = SCIPvarGetLbGlobal(vars[v]);
188  assert(SCIPisLE(scip, lb, bounds[v]));
189  }
190  else
191  {
192  SCIP_Real ub;
193 
194  assert(boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
195 
196  ub = SCIPvarGetLbGlobal(vars[v]);
197  assert(SCIPisGE(scip, ub, bounds[v]));
198  }
199  }
200 }
201 
202 /** check if the global fixed indices are correct */
203 static
205  SCIP* scip, /**< SCIP data structure */
206  SCIP_PROPDATA* propdata /**< propagator data */
207  )
208 {
209  SCIP_VAR* var;
210  int v;
211 
212  for( v = 0; v < propdata->glbfirstnonfixed; ++v )
213  {
214  var = propdata->minactvars[v];
215  assert(var != NULL);
216 
217  assert(SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5);
218  }
219 
220  for( v = 0; v < propdata->maxactfirstnonfixed; ++v )
221  {
222  var = propdata->maxactvars[v];
223  assert(var != NULL);
224 
225  assert(SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5);
226  }
227 }
228 #endif /* end of debug methods */
229 
230 /*
231  * Comparer
232  */
233 
234 /** compares objective implications w.r.t. their maximum contribution */
235 static
236 SCIP_DECL_SORTPTRCOMP(objimplicsComp)
237 {
238  SCIP_OBJIMPLICS* objimplics1;
239  SCIP_OBJIMPLICS* objimplics2;
240 
241  objimplics1 = (SCIP_OBJIMPLICS*)elem1;
242  objimplics2 = (SCIP_OBJIMPLICS*)elem2;
243 
244  if( objimplics1->maxobjchg > objimplics2->maxobjchg )
245  return +1;
246 
247  if( objimplics1->maxobjchg < objimplics2->maxobjchg )
248  return -1;
249 
250  return 0;
251 }
252 
253 /** compare variables w.r.t.
254  * (i) the absolute value the objective coefficient;
255  * (ii) the locks which indicate most effect -- for the variables with a positive (negative) objective coefficient the
256  * down (up) lock is used since this lock indicates that tightened of the upper (lower) bound will triegger
257  * further domain propagations;
258  * (iii) the other locks;
259  * (iv) variable problem index;
260  */
261 static
262 SCIP_DECL_SORTPTRCOMP(varCompObj)
263 {
264  SCIP_VAR* var1;
265  SCIP_VAR* var2;
266  int locks1;
267  int locks2;
269  var1 = (SCIP_VAR*)elem1;
270  var2 = (SCIP_VAR*)elem2;
271 
272  assert(SCIPvarGetObj(var1) != 0.0);
273  assert(SCIPvarGetObj(var2) != 0.0);
274 
275  /* first criteria is the absolute value of objective coefficient */
276  if( REALABS(SCIPvarGetObj(var1)) < REALABS(SCIPvarGetObj(var2)) )
277  return -1;
278  else if( REALABS(SCIPvarGetObj(var1)) > REALABS(SCIPvarGetObj(var2)) )
279  return +1;
280 
281  /* second criteria the locks which indicate most effect */
282  if( SCIPvarGetObj(var1) > 0.0 )
284  else
286 
287  if( SCIPvarGetObj(var2) > 0.0 )
289  else
291 
292  if( locks1 < locks2 )
293  return -1;
294  if( locks1 > locks2 )
295  return 1;
296 
297  /* third criteria the other locks */
298  if( SCIPvarGetObj(var1) > 0.0 )
300  else
302 
303  if( SCIPvarGetObj(var2) > 0.0 )
305  else
307 
308  if( locks1 < locks2 )
309  return -1;
310  if( locks1 > locks2 )
311  return 1;
312 
313  /* forth criteria use the problem index */
314  return SCIPvarCompare(var1, var2);
315 }
316 
317 /** hash key retrieval function for cliques*/
318 static
319 SCIP_DECL_HASHGETKEY(cliqueGetHashkey)
320 { /*lint --e{715}*/
321  return elem;
322 }
323 
324 /** returns TRUE iff the cliques are equal */
325 static
326 SCIP_DECL_HASHKEYEQ(cliqueIsHashkeyEq)
327 { /*lint --e{715}*/
328  if( key1 == key2 )
329  return TRUE;
330  return FALSE;
331 }
333 /** returns the hash value of the key */
334 static
335 SCIP_DECL_HASHKEYVAL(cliqueGetHashkeyVal)
336 { /*lint --e{715}*/
337  return SCIPcliqueGetId((SCIP_CLIQUE*) key);
338 }
339 
340 /*
341  * methods for SCIP_OBJIMPLICS data structure
342  */
343 
344 /** creates an objective implication data structure, fixes (globally) variables which are implied by lower and upper
345  * bound fixing, and clears the collected arrays for lower and upper bound
346  */
347 static
349  SCIP* scip, /**< SCIP data structure */
350  SCIP_OBJIMPLICS** objimplics, /**< pointer to objective implication data structure */
351  SCIP_VAR** objvars, /**< objective contributor variables, or NULL */
352  SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays, or NULL */
353  SCIP_Bool* collectedlbvars, /**< temporary buffer to mark collected variables for lower bound fixing, or NULL */
354  SCIP_Bool* collectedubvars, /**< temporary buffer to mark collected variables for upper bound fixing, or NULL */
355  SCIP_Real maxlbobjchg, /**< maximum objective contributor if variables id fixed to zero */
356  SCIP_Real maxubobjchg, /**< maximum objective contributor if variables id fixed to one */
357  int nlbimpls, /**< number of variables contributing to to lower bound fix */
358  int nubimpls /**< number of variables contributing to to upper bound fix */
359  )
360 
361 {
362  assert(scip != NULL);
363  assert(objimplics != NULL);
364  assert(!SCIPisNegative(scip, maxlbobjchg));
365  assert(!SCIPisNegative(scip, maxubobjchg));
366 
367  /* allocate block memory for the implication data structure */
368  SCIP_CALL( SCIPallocBlockMemory(scip, objimplics) );
369 
370  if( nlbimpls + nubimpls == 0 )
371  {
372  assert(nlbimpls == 0);
373  assert(nubimpls == 0);
374  (*objimplics)->objvars = NULL;
375  (*objimplics)->maxobjchg = 0.0;
376  (*objimplics)->nlbimpls = 0;
377  (*objimplics)->nubimpls = 0;
378  (*objimplics)->size = 0;
379  }
380  else
381  {
382  SCIP_VAR* var;
383  int nvars;
384  int pos;
385  int v;
386 
387  assert(objvars != NULL);
388  assert(binobjvarmap != NULL);
389  assert(collectedlbvars != NULL);
390  assert(collectedubvars != NULL);
391 
392  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*objimplics)->objvars, nlbimpls + nubimpls) );
393  (*objimplics)->size = nlbimpls + nubimpls;
394 
395  nvars = 0;
396 
397  for( v = 0; v < nlbimpls; ++v )
398  {
399  var = objvars[v];
400  assert(var != NULL);
401  assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
402 
403  assert(SCIPhashmapExists(binobjvarmap, var));
404  pos = (int)(size_t)SCIPhashmapGetImage(binobjvarmap, (void*)var);
405  assert(pos > 0);
406  assert(collectedlbvars[pos]);
407 
408  if( collectedubvars[pos] )
409  {
410  SCIP_Bool infeasible;
411  SCIP_Bool tightened;
412 
414  {
415  SCIPdebugMsg(scip, "fix variables <%s> to 1.0 due to implications\n", SCIPvarGetName(var));
416 
417  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, 1.0, FALSE, &infeasible, &tightened) );
418  maxlbobjchg -= SCIPvarGetObj(var);
419  }
420  else
421  {
422  SCIPdebugMsg(scip, "fix variables <%s> to 0.0 due to implications\n", SCIPvarGetName(var));
423 
424  SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, 0.0, FALSE, &infeasible, &tightened) );
425  maxlbobjchg += SCIPvarGetObj(var);
426  }
427  assert(!infeasible);
428  assert(tightened);
429  }
430  else
431  {
432  (*objimplics)->objvars[nvars] = var;
433  nvars++;
434  }
435  collectedlbvars[pos] = FALSE;
436  }
437  (*objimplics)->nlbimpls = nvars;
438 
439  for( v = 0; v < nubimpls; ++v )
440  {
441  var = objvars[nlbimpls + v];
442  assert(var != NULL);
443  assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
444 
445  assert(SCIPhashmapExists(binobjvarmap, var));
446  pos = (int)(size_t)SCIPhashmapGetImage(binobjvarmap, (void*)var);
447  assert(pos > 0);
448  assert(collectedubvars[pos]);
449 
450  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 )
451  {
453  maxubobjchg -= SCIPvarGetObj(var);
454  else
455  maxubobjchg += SCIPvarGetObj(var);
456  }
457  else
458  {
459  (*objimplics)->objvars[nvars] = var;
460  nvars++;
461  }
462  collectedubvars[pos] = FALSE;
463  }
464  (*objimplics)->nubimpls = nvars - (*objimplics)->nlbimpls;
465 
466  /* capture the variables */
467  for( v = 0; v < nvars; ++v )
468  {
469  assert(SCIPvarIsBinary((*objimplics)->objvars[v]));
470  assert(!SCIPisZero(scip, SCIPvarGetObj((*objimplics)->objvars[v])));
471  SCIP_CALL( SCIPcaptureVar(scip, (*objimplics)->objvars[v]) );
472  }
473  }
474 
475  (*objimplics)->maxobjchg = MAX(maxlbobjchg, maxubobjchg);
476 
477  return SCIP_OKAY;
478 }
479 
480 /** frees an objective implication data structure */
481 static
483  SCIP* scip, /**< SCIP data structure */
484  SCIP_OBJIMPLICS** objimplics /**< pointer to objective implication data structure */
485  )
486 {
487  int v;
489  assert(scip != NULL);
490  assert(objimplics != NULL);
491  assert(*objimplics != NULL);
492 
493  /* release all variables */
494  for( v = 0; v < (*objimplics)->nlbimpls + (*objimplics)->nubimpls; ++v )
495  {
496  SCIP_CALL( SCIPreleaseVar(scip, &(*objimplics)->objvars[v]) );
497  }
498 
499  /* free objective variable array */
500  SCIPfreeBlockMemoryArrayNull(scip, &(*objimplics)->objvars, (*objimplics)->size);
501 
502  /* frees block memory for the implication data structure */
503  SCIPfreeBlockMemory(scip, objimplics);
504 
505  return SCIP_OKAY;
506 }
507 
508 /** remove the given variable at the given pos from the objective implication data structure */
509 static
511  SCIP* scip, /**< SCIP data structure */
512  SCIP_OBJIMPLICS* objimplics, /**< objective implication data structure */
513  int pos /**< position */
514  )
515 {
516  assert(0 <= pos);
517  assert(pos < objimplics->nlbimpls + objimplics->nubimpls);
518 
519  SCIPdebugMsg(scip, "variable <%s> ", SCIPvarGetName(objimplics->objvars[pos]));
520 
521  /* release variable */
522  SCIP_CALL( SCIPreleaseVar(scip, &objimplics->objvars[pos]) );
523 
524  /* copy last lower bound variable to that position */
525  if( pos < objimplics->nlbimpls )
526  {
527  objimplics->nlbimpls--;
528  assert(objimplics->nlbimpls >= 0);
529 
530  /* copy last lower bound variable to that position */
531  objimplics->objvars[pos] = objimplics->objvars[objimplics->nlbimpls];
532 
533  /* copy last upper bound variable to open slot */
534  objimplics->objvars[objimplics->nlbimpls] = objimplics->objvars[objimplics->nlbimpls + objimplics->nubimpls];
535 
536  SCIPdebugMsgPrint(scip, "remove lower bound implication\n");
537  }
538  else
539  {
540  objimplics->nubimpls--;
541  assert(objimplics->nubimpls >= 0);
542 
543  /* copy last upper bound variable to that position */
544  objimplics->objvars[pos] = objimplics->objvars[objimplics->nlbimpls + objimplics->nubimpls];
545 
546  SCIPdebugMsgPrint(scip, "remove upper bound implication\n");
547  }
548 
549  return SCIP_OKAY;
550 }
551 
552 /*
553  * Local methods
554  */
555 
556 
557 /** catch bound change events if the variable has a non-zero objective coefficient to check if the maximum activity of
558  * the objective function changed
559  */
560 static
562  SCIP* scip, /**< SCIP data structure */
563  SCIP_PROPDATA* propdata, /**< propagator data */
564  SCIP_EVENTHDLR* eventhdlr, /**< event handler for global bound change events */
565  SCIP_VAR* var /**< variable for which the event should be dropped */
566  )
567 {
568  SCIP_Real objval;
569 
570  assert(propdata != NULL);
571  assert(eventhdlr != NULL);
572 
573  objval = SCIPvarGetObj(var);
574 
575  if( !SCIPisZero(scip, objval) )
576  {
577  if( objval > 0.0 )
578  {
579  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_GUBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) );
580  }
581  else
582  {
583  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_GLBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) );
584  }
585  }
586 
587  return SCIP_OKAY;
588 }
589 
590 /** drop variable event w.r.t. objective coefficient */
591 static
593  SCIP* scip, /**< SCIP data structure */
594  SCIP_PROPDATA* propdata, /**< propagator data */
595  SCIP_EVENTHDLR* eventhdlr, /**< event handler for global bound change events */
596  SCIP_VAR* var /**< variable for which the event should be dropped */
597  )
598 {
599  SCIP_Real objval;
600 
601  assert(propdata != NULL);
602  assert(eventhdlr != NULL);
603 
604  objval = SCIPvarGetObj(var);
605 
606  /* drop bound change event */
607  if( !SCIPisZero(scip, objval) )
608  {
609  if( objval > 0.0 )
610  {
611  SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_GUBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, -1) );
612  }
613  else
614  {
615  SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_GLBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, -1) );
616  }
617  }
618  return SCIP_OKAY;
619 }
620 
621 /** drop all variable events */
622 static
624  SCIP* scip, /**< SCIP data structure */
625  SCIP_PROPDATA* propdata /**< propagator data */
626  )
627 {
628  SCIP_EVENTHDLR* eventhdlr;
629  SCIP_VAR* var;
630  int k;
631 
632  assert(scip != NULL);
633  assert(propdata != NULL);
634 
635  eventhdlr = propdata->eventhdlr;
636  assert(eventhdlr != NULL);
637 
638  /* drop all events and release variables */
639  for( k = 0; k < propdata->nminactvars; ++k )
640  {
641  var = propdata->minactvars[k];
642  assert(var != NULL);
643  assert(SCIPvarIsBinary(var));
644 
645  /* drop bound relax event which is caught for all binary variables which are used for propagation the objective
646  * function via the minimum activity of the objective function
647  */
648  SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDRELAXED, eventhdlr, (SCIP_EVENTDATA*)propdata, -1) );
649 
650  /* release variable */
651  SCIP_CALL( SCIPreleaseVar(scip, &var) );
652  }
653 
654  /* release variables */
655  for( k = 0; k < propdata->nmaxactvars; ++k )
656  {
657  var = propdata->maxactvars[k];
658  assert(var != NULL);
659  assert(SCIPvarIsBinary(var));
660 
661  /* drop events which are needed for evaluating the maximum activity of the objective function */
662  SCIP_CALL( dropObjEvent(scip, propdata, eventhdlr, var) );
663 
664  /* release variable */
665  SCIP_CALL( SCIPreleaseVar(scip, &var) );
666  }
667 
668  /* drop all events and release variables */
669  for( k = 0; k < propdata->nobjintvars; ++k )
670  {
671  var = propdata->objintvars[k];
672  assert(var != NULL);
673 
674  /* drop events which are needed for evaluating the maximum activity of the objective function */
675  SCIP_CALL( dropObjEvent(scip, propdata, eventhdlr, var) );
676 
677  /* release variable */
678  SCIP_CALL( SCIPreleaseVar(scip, &var) );
679  }
680 
681  return SCIP_OKAY;
682 }
683 
684 /** reset propagatore data structure */
685 static
686 void propdataReset(
687  SCIP* scip, /**< SCIP data structure */
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(scip, 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);
763  assert((int)SCIP_BOUNDTYPE_UPPER == 1);
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 = (int)(size_t)SCIPhashmapGetImage(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 
875  assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);
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);
1142  assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);
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 = (int)(size_t)SCIPhashmapGetImage(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);
1406  assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);
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( SCIPhashmapInsert(binobjvarmap, (void*)var, (void*)(size_t)(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  SCIP_CALL( getConflictImplics(scip, objimplics->objvars, objimplics->nlbimpls, objimplics->nlbimpls + objimplics->nubimpls,
1969  bdchgidx, addedvars, reqpseudoobjval, &foundimplics) );
1970  }
1971 
1972  /* check if the binary variable has a positive contribution (positive objective coefficient since it is fixed to
1973  * one) or is needed due a positive contribution of an implied variable
1974  */
1975  if( foundimplics || SCIPisPositive(scip, objval) )
1976  {
1977  SCIPdebugMsg(scip, " add bound change <%s>[%g] >= <%g> bdchgidx [%g,%g]\n", SCIPvarGetName(var), objval, lb, lb, ub);
1978  SCIP_CALL( SCIPaddConflictLb(scip, var, NULL) );
1979 
1980  (*reqpseudoobjval) -= MAX(0.0, objval);
1981 
1982  if( addedvars != NULL )
1983  {
1984  assert(!SCIPhashtableExists(addedvars, (void*)var));
1985  SCIP_CALL( SCIPhashtableInsert(addedvars, (void*)var) );
1986  }
1987  }
1988  }
1989  else if( ub < 0.5 )
1990  {
1991  if( respropuseimplics )
1992  {
1993  SCIP_CALL( getConflictImplics(scip, objimplics->objvars, 0, objimplics->nlbimpls,
1994  bdchgidx, addedvars, reqpseudoobjval, &foundimplics) );
1995  }
1996 
1997  /* check if the binary variable has a positive contribution (negative objective coefficient since it is fixed to
1998  * zero) or is needed due a positive contribution of an implied variable
1999  */
2000  if( foundimplics || SCIPisNegative(scip, objval) )
2001  {
2002  SCIPdebugMsg(scip, " add bound change <%s>[%g] <= <%g> bdchgidx=[%g,%g]\n", SCIPvarGetName(var), objval, ub, lb, ub);
2003  SCIP_CALL( SCIPaddConflictUb(scip, var, NULL) );
2004 
2005  (*reqpseudoobjval) += MIN(0.0, objval);
2006 
2007  if( addedvars != NULL )
2008  {
2009  assert(!SCIPhashtableExists(addedvars, (void*)var));
2010  SCIP_CALL( SCIPhashtableInsert(addedvars, (void*)var) );
2011  }
2012  }
2013  }
2014 
2015  return SCIP_OKAY;
2016 }
2017 
2018 
2019 /** resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the
2020  * cutoff bound
2021  */
2022 static
2024  SCIP* scip, /**< SCIP data structure */
2025  SCIP_PROPDATA* propdata, /**< propagator data */
2026  SCIP_VAR* var, /**< variable that was deduced */
2027  int inferinfo, /**< inference information */
2028  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
2029  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
2030  SCIP_HASHTABLE* addedvars, /**< hash table which contains variables which are already added or implicitly given as reason for the resolve, or NULL */
2031  SCIP_Real* cutoffbound /**< pointer to store the adjusted cutoff bound */
2032  )
2033 {
2034  if( inferinfo != -1 )
2035  {
2036  SCIP_OBJIMPLICS* objimplics;
2037  SCIP_Bool foundimplics;
2038  int start;
2039  int end;
2040 
2041  assert(var != NULL);
2042  assert(SCIPvarIsBinary(var));
2043  assert(bdchgidx != NULL);
2044  assert(SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE)));
2045  assert(inferinfo >= 0);
2046  assert(inferinfo < propdata->nminactvars);
2047  assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE);
2048  assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);
2049 
2050  objimplics = propdata->minactimpls[inferinfo];
2051  assert(objimplics != NULL);
2052 
2053  /* get the objective contribution if we would fix the binary inference variable to its other bound */
2054  (*cutoffbound) -= getVarObjchg(var, SCIPvarGetBestBoundType(var), boundtype);
2055  foundimplics = FALSE;
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_CALL( getConflictImplics(scip, objimplics->objvars, start, end, bdchgidx, addedvars, cutoffbound, &foundimplics) );
2071  }
2072  }
2073  else
2074  {
2075  SCIP_Real glbbound;
2076  SCIP_Real newbound;
2077  SCIP_Real objval;
2078 
2079  objval = SCIPvarGetObj(var);
2080 
2081  assert(!SCIPisZero(scip, objval));
2082 
2083  if( objval > 0.0 )
2084  {
2085  newbound = SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE);
2086  glbbound = SCIPvarGetLbGlobal(var);
2087  }
2088  else
2089  {
2090  newbound = SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE);
2091  glbbound = SCIPvarGetUbGlobal(var);
2092  }
2093 
2094  /* in case the variable is integral we just need to prove the newbound plus/minus (1 - epsilon) since the this bound
2095  * would be rounded to newbound due to integrability which is global information
2096  */
2097  if( SCIPvarIsIntegral(var) )
2098  {
2099  if( objval > 0.0 )
2100  newbound += 1 - 10 * SCIPfeastol(scip);
2101  else
2102  newbound -= 1 - 10 * SCIPfeastol(scip);
2103  }
2104 
2105  /* adjust the cutoff bound by the portion the inference variable contributes to the presudo objective activity
2106  * (minactivity)
2107  */
2108  assert(!SCIPisNegative(scip, objval * (newbound - glbbound)));
2109  (*cutoffbound) -= objval * (newbound - glbbound);
2110  }
2111 
2112  return SCIP_OKAY;
2113 }
2114 
2115 
2116 /** resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the
2117  * cutoff bound
2118  */
2119 static
2121  SCIP* scip, /**< SCIP data structure */
2122  SCIP_PROPDATA* propdata, /**< propagator data */
2123  SCIP_Real cutoffbound, /**< the global cutoff */
2124  SCIP_VAR* infervar, /**< variable that was deduced, or NULL for conflict analysis initialization */
2125  int inferinfo, /**< inference information */
2126  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
2127  SCIP_BDCHGIDX* bdchgidx /**< bound change index (time stamp of bound change), or NULL for current time */
2128  )
2129 {
2130  SCIP_HASHTABLE* addedvars;
2131  SCIP_VAR** vars;
2132  SCIP_VAR* var;
2133  SCIP_Real glbpseudoobjval;
2134  SCIP_Real reqpseudoobjval;
2136  int nvars;
2137  int v;
2138 
2139  infinity = FALSE;
2140  addedvars = NULL;
2141  nvars = propdata->nminactvars;
2142 
2143  /* the global pseudo value gives us a global valid minimal activity
2144  *
2145  * @note The global pseudo objective activity can be minus infinity. In that case all variable are part of the
2146  * reason/explanation
2147  *
2148  * @note If the global pseudo objective activity is greater than the required minactivity, the local bound change
2149  * which has to explained is actually (now) a global one. That means, the reason/explanation is empty
2150  */
2151  glbpseudoobjval = SCIPgetGlobalPseudoObjval(scip);
2152 
2153  if( SCIPisInfinity(scip, -glbpseudoobjval) )
2154  {
2155  infinity = TRUE;
2156  reqpseudoobjval = cutoffbound;
2157  }
2158  else
2159  {
2160  /* clear hash table for storing variables which are not needed to add the reason due to global implications or
2161  * already added
2162  */
2163  if( nvars > 0 )
2164  {
2165  addedvars = propdata->addedvars;
2166  SCIPhashtableRemoveAll(addedvars);
2167  }
2168 
2169  if( infervar != NULL )
2170  {
2171  SCIP_CALL( adjustCutoffbound(scip, propdata, infervar, inferinfo, boundtype, bdchgidx, addedvars, &cutoffbound) );
2172  }
2173 
2174  reqpseudoobjval = cutoffbound - glbpseudoobjval;
2175  }
2176 
2177  SCIPdebugMsg(scip, "resolve propagation global pseudo objective <%g>, cutoff bounda <%g>, required minactivity <%g>\n",
2178  glbpseudoobjval, cutoffbound, reqpseudoobjval);
2179 
2180  /* the variables responsible for the propagation are the ones with
2181  * - obj > 0 and local lb > global lb
2182  * - obj < 0 and local ub < global ub
2183  *
2184  * collect all variables which contribute positively to the pseudo objective value (minimum activity) until we
2185  * reached the (adjusted) required minimum activity for the inference bound change
2186  */
2187 
2188  /* first, consider the binary variables */
2189  if( nvars > 0 )
2190  {
2191  SCIP_OBJIMPLICS** minactimpls;
2192 
2193  vars = propdata->minactvars;
2194  assert(vars != NULL);
2195 
2196  minactimpls = propdata->minactimpls;
2197  assert(minactimpls != NULL);
2198 
2199 #ifndef NDEBUG
2200  checkGlbfirstnonfixed(scip, propdata);
2201 #endif
2202 
2203  if( infinity )
2204  {
2205  /* if the required minimum activity is minus infinity, we have to add all variables which contribute the local
2206  * pseudo objective activity
2207  */
2208 
2209  for( v = propdata->glbfirstnonfixed; v < nvars; ++v )
2210  {
2211  var = vars[v];
2212  assert(var != NULL);
2213 
2214  /* @note binary variables can have a zero objective value */
2215 
2216  if( var == infervar )
2217  continue;
2218 
2219  SCIP_CALL( addConflictBinvar(scip, var, bdchgidx, NULL, NULL, FALSE, &reqpseudoobjval) );
2220  }
2221  }
2222  else
2223  {
2224  assert(addedvars != NULL);
2225 
2226  for( v = propdata->glbfirstnonfixed; v < nvars && SCIPisPositive(scip, reqpseudoobjval); ++v )
2227  {
2228  var = vars[v];
2229  assert(var != NULL);
2230 
2231  /* @note binary variables can have a zero objective value */
2232 
2233  if( var == infervar )
2234  continue;
2235 
2236  if( SCIPhashtableExists(addedvars, (void*)var) )
2237  continue;
2238 
2239  SCIP_CALL( addConflictBinvar(scip, var, bdchgidx, minactimpls[v], addedvars, propdata->respropuseimplics, &reqpseudoobjval) );
2240  }
2241  }
2242  }
2243 
2244  vars = propdata->objintvars;
2245  nvars = propdata->nobjintvars;
2246  assert(nvars == 0 || vars != NULL);
2247 
2248  /* second, consider the non-binary variables */
2249  for( v = 0; v < nvars && (infinity || SCIPisPositive(scip, reqpseudoobjval)); ++v )
2250  {
2251  var = vars[v];
2252  assert(var != NULL);
2253  assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
2254 
2255  if( var == infervar )
2256  continue;
2257 
2258  SCIP_CALL( addConflictBounds(scip, var, bdchgidx, &reqpseudoobjval) );
2259  }
2260 
2261  return SCIP_OKAY;
2262 }
2263 
2264 /** propagates the given variable against the cutoff bound */
2265 static
2267  SCIP* scip, /**< SCIP data structure */
2268  SCIP_PROP* prop, /**< propagator, or NULL */
2269  SCIP_VAR* var, /**< variable to propagate */
2270  int inferinfo, /**< inference information to store with the bound change */
2271  SCIP_Real objchg, /**< objective change */
2272  SCIP_Real cutoffbound, /**< cutoff bound to use */
2273  SCIP_Real pseudoobjval, /**< pseudo objective value to use */
2274  SCIP_Bool local, /**< local or global propagation */
2275  SCIP_Bool* tightened /**< pointer to store if the variable domain was tightened */
2276  )
2277 {
2278  SCIP_Real lb;
2279  SCIP_Real ub;
2280  SCIP_Real newbd;
2281  SCIP_Bool infeasible;
2282 
2283  assert(!SCIPisZero(scip, objchg));
2284  assert(!SCIPisInfinity(scip, -pseudoobjval));
2285  assert(!SCIPisInfinity(scip, cutoffbound));
2286  assert(SCIPisLT(scip, pseudoobjval, cutoffbound) );
2287  assert(tightened != NULL);
2288 
2289  *tightened = FALSE;
2290 
2291  /* collect bounds of the variable */
2292  if( local )
2293  {
2294  assert(prop != NULL);
2295  lb = SCIPvarGetLbLocal(var);
2296  ub = SCIPvarGetUbLocal(var);
2297  }
2298  else
2299  {
2300  lb = SCIPvarGetLbGlobal(var);
2301  ub = SCIPvarGetUbGlobal(var);
2302  }
2303 
2304  if( SCIPisFeasEQ(scip, lb, ub) )
2305  return SCIP_OKAY;
2306 
2307  /* depending on the objective contribution we can try to tighten the lower or upper bound of the variable */
2308  if( objchg > 0.0 )
2309  {
2310  newbd = lb + (cutoffbound - pseudoobjval) / objchg;
2311 
2312  if( local )
2313  {
2314  SCIP_CALL( SCIPinferVarUbProp(scip, var, newbd, prop, inferinfo, FALSE, &infeasible, tightened) );
2315  assert(!infeasible);
2316 
2317  if( *tightened ) /* might not be tightened due to numerical reasons */
2318  {
2319  SCIPdebugMsg(scip, " -> new (local) upper bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n",
2320  SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound);
2321  }
2322  }
2323  else
2324  {
2325  SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, FALSE, &infeasible, tightened) );
2326  assert(!infeasible);
2327 
2328  if( *tightened )
2329  {
2330  SCIPdebugMsg(scip, " -> new (global) upper bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n",
2331  SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound);
2332  }
2333  }
2334  }
2335  else
2336  {
2337  newbd = ub + (cutoffbound - pseudoobjval) / objchg;
2338 
2339  if( local )
2340  {
2341  SCIP_CALL( SCIPinferVarLbProp(scip, var, newbd, prop, inferinfo, FALSE, &infeasible, tightened) );
2342  assert(!infeasible);
2343 
2344  if( *tightened ) /* might not be tightened due to numerical reasons */
2345  {
2346  SCIPdebugMsg(scip, " -> new (local) lower bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n",
2347  SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound);
2348  }
2349  }
2350  else
2351  {
2352  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, FALSE, &infeasible, tightened) );
2353  assert(!infeasible);
2354 
2355  if( *tightened )
2356  {
2357  SCIPdebugMsg(scip, " -> new (global) lower bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n",
2358  SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound);
2359  }
2360  }
2361  }
2362 
2363  return SCIP_OKAY;
2364 }
2365 
2366 /** propagates the given binary variable against the cutoff bound */
2367 static
2369  SCIP* scip, /**< SCIP data structure */
2370  SCIP_PROP* prop, /**< propagator, or NULL */
2371  SCIP_VAR* var, /**< variable to propagate */
2372  int pos, /**< position of the variable in the corresponding propdata variable array */
2373  SCIP_Real cutoffbound, /**< cutoff bound to use */
2374  SCIP_Real pseudoobjval, /**< pseudo objective value to use */
2375  SCIP_Bool* tightened, /**< pointer to store if the variable domain was tightened */
2376  SCIP_Bool* cutoff, /**< pointer to store if a cutoff was detected */
2377  SCIP_Bool local /**< propagate local bounds, otherwise global bounds */
2378  )
2379 {
2380  SCIP_PROPDATA* propdata;
2381  SCIP_OBJIMPLICS* objimplics;
2382  SCIP_Real lbobjchg;
2383  SCIP_Real ubobjchg;
2384  SCIP_Real objchg;
2385 
2386  assert(SCIPvarIsBinary(var));
2387 
2388  propdata = SCIPpropGetData(prop);
2389  assert(propdata != NULL);
2390 
2391  objimplics = propdata->minactimpls[pos];
2392  assert(objimplics != NULL);
2393 
2394  /* get objective change in case of fixing the variable to its lower bound (that is zero) */
2395  SCIP_CALL( getMinactObjchg(scip, var, objimplics, NULL, SCIP_BOUNDTYPE_LOWER, local, &lbobjchg) );
2396  assert(!SCIPisNegative(scip, lbobjchg));
2397 
2398  /* get objective change in case of fixing the variable to its upper bound (that is one) */
2399  SCIP_CALL( getMinactObjchg(scip, var, objimplics, NULL, SCIP_BOUNDTYPE_UPPER, local, &ubobjchg) );
2400  assert(!SCIPisNegative(scip, ubobjchg));
2401 
2402  (*tightened) = FALSE;
2403 
2404  /* nothing can be done if the objective contribution is zero independently of the bound */
2405  if( SCIPisZero(scip, lbobjchg) && SCIPisZero(scip, ubobjchg) )
2406  return SCIP_OKAY;
2407 
2408  /* if the lbobjchg and ubobjchg are both able to fix the variable to its upper (1.0) or lower (0.0) bound,
2409  * respectively, we detected an cutoff
2410  *
2411  * @note There is no need to use SCIPisFeasLT() in case the objective is integral since the cutoff bound in that case
2412  * is the upper bound minus 1 plus the SCIPcutoffbounddelta() (which is MIN(100.0 * feastol, 0.0001)). However,
2413  * if the objective is not integral we have to check w.r.t. an epsilon to avoid numerical problems.
2414  */
2415  if( SCIPisFeasLT(scip, cutoffbound, pseudoobjval + ubobjchg) && SCIPisFeasLT(scip, cutoffbound, pseudoobjval + lbobjchg) )
2416  {
2417  /* check if conflict analysis is applicable */
2418  if( local && SCIPisConflictAnalysisApplicable(scip) )
2419  {
2420  assert(SCIPgetDepth(scip) > 0);
2421 
2422  /* initialize conflict analysis */
2424 
2425  /* add all variable whose best bound changes increased the pseudo objective value above to cutoff bound */
2426  SCIP_CALL( resolvePropagation(scip, propdata, pseudoobjval, NULL, -1, SCIP_BOUNDTYPE_UPPER, NULL) );
2427 
2428  /* analyze the conflict */
2429  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
2430  }
2431 
2432  (*cutoff) = TRUE;
2433  }
2434  else
2435  {
2436  /* try to tighten the variable bound use the larger objective contribution */
2437  if( lbobjchg > ubobjchg )
2438  objchg = -lbobjchg;
2439  else
2440  objchg = ubobjchg;
2441 
2442  SCIP_CALL( propagateCutoffboundVar(scip, prop, var, pos, objchg, cutoffbound, pseudoobjval, local, tightened) );
2443  }
2444 
2445  return SCIP_OKAY;
2446 }
2447 
2448 /** globally propagates if a new cutoff bound or global pseudo objective value (minimum activity of the objective
2449  * function) is available
2450  */
2451 static
2453  SCIP* scip, /**< SCIP data structure */
2454  SCIP_PROP* prop, /**< propagator */
2455  int* nchgbds, /**< pointer to store the number of bound changes */
2456  SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
2457  )
2459  SCIP_PROPDATA* propdata;
2460  SCIP_VAR** minactvars;
2461  SCIP_VAR** objintvars;
2462  SCIP_VAR* var;
2463  SCIP_Bool tightened;
2464  SCIP_Real pseudoobjval;
2465  SCIP_Real cutoffbound;
2466  int nminactvars;
2467  int nobjintvars;
2468  int v;
2469 
2470  /* this method should not be called in the root node of the search tree since the standard propagation already does
2471  * the job
2472  */
2473  assert(SCIPgetDepth(scip) > 0);
2474 
2475  propdata = SCIPpropGetData(prop);
2476  assert(propdata != NULL);
2477 
2478  pseudoobjval = SCIPgetGlobalPseudoObjval(scip);
2479  cutoffbound = propdata->cutoffbound;
2480 
2481  /* nothing can be done if the global pseudo objective is minus infinity */
2482  if( SCIPisInfinity(scip, -pseudoobjval) )
2483  return SCIP_OKAY;
2484 
2485  /* check if the global pseudo objective value (minimum activity of the objective function) is greater or equal to
2486  * the cutoff bound
2487  */
2488  if( SCIPisGE(scip, pseudoobjval, cutoffbound) )
2489  {
2490  *cutoff = TRUE;
2491  return SCIP_OKAY;
2492  }
2493 
2494  minactvars = propdata->minactvars;
2495  objintvars = propdata->objintvars;
2496  nminactvars = propdata->nminactvars;
2497  nobjintvars = propdata->nobjintvars;
2498 
2499 #ifndef NDEBUG
2500  checkGlbfirstnonfixed(scip, propdata);
2501 #endif
2502 
2503  *cutoff = FALSE;
2504 
2505  /* always propagate the binary variables completely */
2506  for( v = propdata->glbfirstnonfixed; v < nminactvars; ++v )
2507  {
2508  var = minactvars[v];
2509  assert(var != NULL);
2510 
2511  /* check if the variables is already globally fixed; if so continue with the potential candidate */
2512  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
2513  continue;
2514 
2515  /* propagates the cutoff bound for the given binary variable */
2516  SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, FALSE) );
2517 
2518  /* the binary variables are sorted in non-increasing manner w.r.t. the absolute value of their objective
2519  * contribution w.r.t. minimum activity (pseudo objective value) of the objective function; these values are the
2520  * increase in the pseudo objective activity we would get if we fix the variable to its worse bound; hence, we can
2521  * stop if for a variable this potential increase is not enough too exceed the cutoff bound;
2522  */
2523  if( !tightened )
2524  {
2525  SCIPdebugMsg(scip, "interrupt global pseudo objective propagation w.r.t. cutoff bound <%.15g> for binary variables after %d from %d binary variables\n",
2526  cutoffbound, v, nminactvars);
2527  break;
2528  }
2529 
2530  if( *cutoff )
2531  return SCIP_OKAY;
2532 
2533  /* @note The variable might not be globally fixed right away since this would destroy the local internal
2534  * data structure of a search node; the bound change is in that case pending; hence we cannot assert
2535  * that the variable is globally fixed
2536  */
2537  (*nchgbds)++;
2538  }
2539  propdata->glbfirstnonfixed = v;
2540  propdata->firstnonfixed = MAX(propdata->firstnonfixed, v);
2541 
2542  /* check all binary variables which could potentially be fixed */
2543  for( ; v < nminactvars && cutoffbound - pseudoobjval < propdata->minactimpls[v]->maxobjchg; ++v )
2544  {
2545  var = minactvars[v];
2546  assert(var != NULL);
2547 
2548  /* check if the variables is already globally fixed; if so continue with the potential candidate */
2549  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
2550  continue;
2551 
2552  /* propagates the cutoff bound for the given binary variable */
2553  SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, FALSE) );
2554 
2555  /* check if the domain of the variable was reduced */
2556  if( tightened )
2557  (*nchgbds)++;
2558 
2559  if( *cutoff )
2560  return SCIP_OKAY;
2561  }
2562 
2563 #if 0 /* might fail, but is not a real error, still need to investigate */
2564 #ifndef NDEBUG
2565  /* check that the abort criteria for the binary variables works */
2566  for( ; v < nminactvars; ++v )
2567  {
2568  assert(cutoffbound - pseudoobjval >= propdata->minactimpls[v]->maxobjchg);
2569 
2570  var = minactvars[v];
2571  assert(var != NULL);
2572 
2573  /* check if the variable is already locally fixed; in that case we just continue with the next potential
2574  * candidate
2575  */
2576  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
2577  continue;
2578 
2579  /* propagates the cutoff bound for the given binary variable */
2580  SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, FALSE) );
2581  assert(!tightened);
2582  assert(!(*cutoff));
2583  }
2584 #endif
2585 #endif
2586 
2587  /* propagate the non-binary variables completely */
2588  for( v = 0; v < nobjintvars; ++v )
2589  {
2590  var = objintvars[v];
2591  assert(var != NULL);
2592  assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
2593 
2594  /* try to tighten the bound of the variable */
2595  SCIP_CALL( propagateCutoffboundVar(scip, NULL, var, -1, SCIPvarGetObj(var), cutoffbound, pseudoobjval, FALSE, &tightened) );
2596 
2597  /* check if the domain of the variable was reduced */
2598  if( tightened )
2599  (*nchgbds)++;
2600  }
2601 
2602  propdata->glbpropagated = TRUE;
2603 
2604  return SCIP_OKAY;
2605 }
2606 
2607 /** propagates the cutoff bound for binary variables (c*x <= cutoff) */
2608 static
2610  SCIP* scip, /**< SCIP data structure */
2611  SCIP_PROP* prop, /**< propagator */
2612  SCIP_Real cutoffbound, /**< cutoff bound to use */
2613  SCIP_Real pseudoobjval, /**< pseudo objective value to use */
2614  int* nfixedvars, /**< pointer to store the number of fixed variables */
2615  SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
2616  )
2617 {
2618  SCIP_PROPDATA* propdata;
2619  SCIP_VAR** minactvars;
2620  SCIP_VAR* var;
2621  SCIP_Bool tightened;
2622  int nminactvars;
2623  int v;
2624 
2625  propdata = SCIPpropGetData(prop);
2626  assert(propdata != NULL);
2627 
2628  minactvars = propdata->minactvars;
2629  nminactvars = propdata->nminactvars;
2630  assert(nminactvars == 0 || minactvars != NULL);
2631 
2632  /* always propagate the binary variables completely; note that the variables before the firstnonfixed indexed are
2633  * already locally fixed and those before glbfirstnonfixed are already globally fixed
2634  */
2635 
2636 #ifndef NDEBUG
2637  /* check that the variables before glbfirstnonfixed are globally fixed */
2638  checkGlbfirstnonfixed(scip, propdata);
2639 
2640  /* check that the variables before firstnonfixed are locally fixed */
2641  for( v = propdata->glbfirstnonfixed; v < propdata->firstnonfixed; ++v )
2642  {
2643  var = minactvars[v];
2644  assert(var != NULL);
2645 
2646  assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5);
2647  }
2648 #endif
2649 
2650  (*cutoff) = FALSE;
2651 
2652  for( v = propdata->firstnonfixed; v < nminactvars; ++v )
2653  {
2654  var = minactvars[v];
2655  assert(var != NULL);
2656 
2657  /* check if the variable is already locally fixed; in that case we just continue with the next potential
2658  * candidate
2659  */
2660  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5)
2661  continue;
2662 
2663  /* propagates the cutoff bound for the given binary variable */
2664  SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, TRUE) );
2665 
2666  /* the binary variables are sorted in non-increasing manner w.r.t. the absolute value of their objective
2667  * contribution w.r.t. minimum activity of the objective function; These values are the increase in the pseudo
2668  * objective activity (minimum activity of the objective function) we would get if we fix the variable to its
2669  * worse bound; hence, we can stop if for a variable this potential increase is not enough too exceed the cutoff
2670  * bound;
2671  */
2672  if( !tightened )
2673  {
2674  SCIPdebugMsg(scip, "interrupt local pseudo objective propagation w.r.t. cutoff bound <%.15g> for binary variables after %d from %d binary variables\n",
2675  cutoffbound, v, nminactvars);
2676  break;
2677  }
2678 
2679  if( *cutoff )
2680  return SCIP_OKAY;
2681 
2682  /* check that the binary variable is locally fixed */
2683  assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5);
2684  (*nfixedvars)++;
2685  }
2686  propdata->firstnonfixed = v;
2687 
2688  /* check all binary variables which could potentially be fixed */
2689  for( ; v < nminactvars && cutoffbound - pseudoobjval < propdata->minactimpls[v]->maxobjchg; ++v )
2690  {
2691  var = minactvars[v];
2692  assert(var != NULL);
2693 
2694  /* check if the variable is already locally fixed; in that case we just continue with the next potential
2695  * candidate
2696  */
2697  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5)
2698  continue;
2699 
2700  /* propagates the cutoff bound for the given binary variable */
2701  SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, TRUE) );
2702 
2703  if( tightened )
2704  {
2705  assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5);
2706  (*nfixedvars)++;
2707  }
2708 
2709  if( *cutoff )
2710  return SCIP_OKAY;
2711  }
2712 
2713 #if 0 /* might fail, but is not a real error, still need to investigate */
2714 #ifndef NDEBUG
2715  /* check that the abort criteria for the binary variables works */
2716  for( ; v < nminactvars; ++v )
2717  {
2718  var = minactvars[v];
2719  assert(var != NULL);
2720 
2721  assert(cutoffbound - pseudoobjval >= propdata->minactimpls[v]->maxobjchg);
2722 
2723  /* check if the variable is already locally fixed; in that case we just continue with the next potential
2724  * candidate
2725  */
2726  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5)
2727  continue;
2728 
2729  /* propagates the cutoff bound for the given binary variable */
2730  SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, TRUE) );
2731  assert(!tightened);
2732  assert(!(*cutoff));
2733  }
2734 #endif
2735 #endif
2736 
2737  return SCIP_OKAY;
2738 }
2739 
2740 /** propagates the cutoff bound c*x <= cutoff */
2741 static
2743  SCIP* scip, /**< SCIP data structure */
2744  SCIP_PROP* prop, /**< propagator */
2745  SCIP_RESULT* result /**< pointer to store the result of the callback method */
2746  )
2747 {
2748  SCIP_PROPDATA* propdata;
2749  SCIP_Real pseudoobjval;
2750  SCIP_Real cutoffbound;
2751  SCIP_Bool cutoff;
2752  SCIP_Bool tightened;
2753  int nchgbds;
2754 
2755  assert(result != NULL);
2756 
2757  (*result) = SCIP_DIDNOTRUN;
2758 
2759  propdata = SCIPpropGetData(prop);
2760  assert(propdata != NULL);
2761 
2762  /* get current pseudo objective value (minimum activity of the objective function) and cutoff bound */
2763  pseudoobjval = SCIPgetPseudoObjval(scip);
2764  if( SCIPisInfinity(scip, -pseudoobjval) )
2765  return SCIP_OKAY;
2766  cutoffbound = SCIPgetCutoffbound(scip);
2767  if( SCIPisInfinity(scip, cutoffbound) )
2768  return SCIP_OKAY;
2769 
2770  /* @note A new global pseudo objective value could be used to retrieve global fixings. There is, however, no need to
2771  * check if a new global pseudo objective value is available. This is the case since a new (better) global
2772  * pseudo activity implies that a global bound change was performed. That causes that the root node of the
2773  * search tree gets marked for repropagation. That will result in a propagation call of the pseudo objective
2774  * propagator.
2775  */
2776 
2777  /* check current cutoff bound */
2778  if( cutoffbound < propdata->cutoffbound )
2779  {
2780  propdata->glbpropagated = FALSE;
2781  propdata->cutoffbound = cutoffbound;
2782  }
2783 
2784  nchgbds = 0;
2785  cutoff = FALSE;
2786  (*result) = SCIP_DIDNOTFIND;
2787 
2788  /* check if we have a new cutoff bound; in that case we globally propagate this new bound
2789  *
2790  * @note there is no need to propagate the cutoff bound if we are in the root node since this will be done by the
2791  * standard local propagation
2792  */
2793  if( propdata->propcutoffbound && !propdata->glbpropagated && SCIPgetDepth(scip) > 0 )
2794  {
2795  /* first globally propagate new cutoff bound or pseudo objective activity */
2796  SCIP_CALL( propagateCutoffboundGlobally(scip, prop, &nchgbds, &cutoff) );
2797 
2798  if( cutoff )
2799  {
2800  /* we are done with solving since a global pseudo activity is greater or equal to the cutoff bound */
2801  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
2802 
2803  (*result) = SCIP_CUTOFF;
2804  return SCIP_OKAY;
2805  }
2806 
2807  /* check if the global propagation cut off the active/current node */
2808  if( SCIPgetCutoffdepth(scip) <= SCIPgetDepth(scip) )
2809  {
2810  (*result) = SCIP_CUTOFF;
2811  return SCIP_OKAY;
2812  }
2813  }
2814 
2815  /* check if the pseudo objective value (minimum activity of the objective function) is greater or equal to the cutoff
2816  * bound
2817  */
2818  if( SCIPisGE(scip, pseudoobjval, cutoffbound) )
2819  {
2820  SCIPdebugMsg(scip, "pseudo objective value <%g> exceeds cutoff bound <%g>\n", pseudoobjval, cutoffbound);
2821 
2822  /* check if conflict analysis is applicable */
2824  {
2825  assert(SCIPgetDepth(scip) > 0);
2826 
2827  /* initialize conflict analysis */
2829 
2830  /* add all variable whose best bound changes increased the pseudo objective value above the cutoff bound */
2831  SCIP_CALL( resolvePropagation(scip, propdata, cutoffbound, NULL, -1, SCIP_BOUNDTYPE_UPPER, NULL) );
2832 
2833  /* analyze the conflict */
2834  SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) );
2835  }
2836  (*result) = SCIP_CUTOFF;
2837 
2838  return SCIP_OKAY;
2839  }
2840 
2841  SCIPdebugMsg(scip, "propagating pseudo objective function (pseudoobj: %g, cutoffbound: %g)\n", pseudoobjval, cutoffbound);
2842 
2843  /* propagate binary variables */
2844  SCIP_CALL( propagateCutoffboundBinvars(scip, prop, cutoffbound, pseudoobjval, &nchgbds, &cutoff) );
2845 
2846  if( cutoff )
2847  {
2848  (*result) = SCIP_CUTOFF;
2849  return SCIP_OKAY;
2850  }
2851 
2852  /* tighten domains of non-binary variables, if they would increase the pseudo objective value above the cutoff
2853  * bound
2854  */
2855  if( propdata->propfullinroot && SCIPgetDepth(scip) == 0 )
2856  {
2857  SCIP_VAR** objintvars;
2858  SCIP_VAR* var;
2859  SCIP_Real objval;
2860  int nobjintvars;
2861  int v;
2862 
2863  objintvars = propdata->objintvars;
2864  nobjintvars = propdata->nobjintvars;
2865  assert(nobjintvars == 0 || objintvars != NULL);
2866 
2867  /* propagate all non-binary variables */
2868  for( v = 0; v < nobjintvars; ++v )
2869  {
2870  var = objintvars[v];
2871  assert(var != NULL);
2872 
2873  objval = SCIPvarGetObj(var);
2874  assert(!SCIPisZero(scip, objval));
2875 
2876  /* try to tighten the bound of the variable */
2877  SCIP_CALL( propagateCutoffboundVar(scip, NULL, var, -1, objval, cutoffbound, pseudoobjval, FALSE, &tightened) );
2878 
2879  /* check if the domain of the variable was reduced */
2880  if( tightened )
2881  nchgbds++;
2882  }
2883  }
2884  else
2885  {
2886  SCIP_VAR** objintvars;
2887  SCIP_VAR* var;
2888  SCIP_Real objval;
2889  int nobjintvars;
2890  int nmaxuseless;
2891  int nuseless;
2892  int c;
2893  int v;
2894 
2895  objintvars = propdata->objintvars;
2896  nobjintvars = propdata->nobjintvars;
2897  assert(nobjintvars == 0 || objintvars != NULL);
2898 
2899  /* compute maximum number of useless propagations before aborting */
2900  nmaxuseless = MAX(propdata->minuseless, (int)propdata->maxvarsfrac*(nobjintvars));
2901 
2902  nuseless = 0;
2903  v = propdata->lastvarnum;
2904 
2905  for( c = 0; c < nobjintvars && nuseless < nmaxuseless; ++c )
2906  {
2907  v++;
2908  if( v >= nobjintvars )
2909  v = 0;
2910 
2911  var = objintvars[v];
2912  assert(var != NULL);
2913 
2914  objval = SCIPvarGetObj(var);
2915  assert(!SCIPisZero(scip, objval));
2916 
2917  /* try to tighten the bound of the variable */
2918  SCIP_CALL( propagateCutoffboundVar(scip, prop, var, -1, objval, cutoffbound, pseudoobjval, TRUE, &tightened) );
2919 
2920  /* check if the domain of the variable was reduced */
2921  if( tightened )
2922  nchgbds++;
2923  else
2924  nuseless++;
2925  }
2926  propdata->lastvarnum = v;
2927  }
2928 
2929  /* check if we chanced bounds */
2930  if( nchgbds > 0 )
2931  (*result) = SCIP_REDUCEDDOM;
2932 
2933  return SCIP_OKAY;
2934 }
2935 
2936 /** recalculates the maximum objective pseudoactivity */
2937 static
2939  SCIP* scip, /**< SCIP data structure */
2940  SCIP_PROPDATA* propdata /**< propagator data */
2941  )
2942 {
2943  SCIP_VAR** vars;
2944  SCIP_Real objval;
2945  SCIP_Real contrib;
2946  int nvars;
2947  int v;
2948 
2949  assert(propdata != NULL);
2950 
2951  /* get problem variables */
2952  vars = SCIPgetVars(scip);
2953  nvars = SCIPgetNVars(scip);
2954 
2955  /* calculate current max pseudo activity and largest contribution */
2956  propdata->maxpseudoobjact = 0.0;
2957  propdata->maxpseudoobjactinf = 0;
2958 
2959  for( v = 0; v < nvars; ++v )
2960  {
2961  objval = SCIPvarGetObj(vars[v]);
2962  if( SCIPisPositive(scip, objval) )
2963  {
2964  contrib = SCIPvarGetUbGlobal(vars[v]);
2965  if( !SCIPisInfinity(scip, contrib) )
2966  contrib *= objval;
2967  }
2968  else if( SCIPisNegative(scip, objval) )
2969  {
2970  contrib = SCIPvarGetLbGlobal(vars[v]);
2971  if( !SCIPisInfinity(scip, -contrib) )
2972  contrib *= objval;
2973  else
2974  contrib *= -1.0;
2975  }
2976  else
2977  continue;
2978 
2979  if( SCIPisInfinity(scip, contrib) )
2980  propdata->maxpseudoobjactinf++;
2981  else
2982  propdata->maxpseudoobjact += contrib;
2983  }
2984 }
2985 
2986 /** updates the pseudo objective activity if necessary */
2987 static
2989  SCIP* scip, /**< SCIP data structure */
2990  SCIP_PROPDATA* propdata /**< propagator data */
2991  )
2992 {
2993  assert(propdata != NULL);
2995  /* if necessary, calculate the maximum pseudo objective activity */
2996  if( propdata->maxpseudoobjact == SCIP_INVALID ) /*lint !e777*/
2997  calcMaxObjPseudoactivity(scip, propdata);
2998  assert(propdata->maxpseudoobjact != SCIP_INVALID); /*lint !e777*/
2999 }
3000 
3001 /** returns the residual pseudo objective activity without the given value */
3002 static
3004  SCIP* scip, /**< SCIP data structure */
3005  SCIP_PROPDATA* propdata, /**< propagator data */
3006  SCIP_Real contrib /**< value to eliminate from pseudo objective activity */
3007  )
3008 {
3009  SCIP_Real residual;
3010 
3011  assert(propdata != NULL);
3012 
3013  /* if necessary, calculate the maximum pseudo objective activity */
3014  if( propdata->maxpseudoobjact == SCIP_INVALID ) /*lint !e777*/
3015  calcMaxObjPseudoactivity(scip, propdata);
3016  assert(propdata->maxpseudoobjact != SCIP_INVALID); /*lint !e777*/
3017 
3018  if( SCIPisInfinity(scip, contrib) )
3019  {
3020  assert(propdata->maxpseudoobjactinf >= 1);
3021  /* check if this variable yields the only infinite contribution */
3022  if( propdata->maxpseudoobjactinf == 1 )
3023  residual = propdata->maxpseudoobjact;
3024  else
3025  residual = SCIPinfinity(scip);
3026  }
3027  else
3028  {
3029  /* check if there is an infinite contribution */
3030  if( propdata->maxpseudoobjactinf >= 1 )
3031  residual = SCIPinfinity(scip);
3032  else
3033  residual = propdata->maxpseudoobjact - contrib;
3034  }
3035 
3036  return residual;
3037 }
3038 
3039 /** returns the residual pseudo objective activity */
3040 static
3042  SCIP* scip, /**< SCIP data structure */
3043  SCIP_PROPDATA* propdata, /**< propagator data */
3044  SCIP_VAR* var /**< variable to get residual activity for */
3045  )
3046 {
3047  SCIP_Real objval;
3048  SCIP_Real contrib;
3049 
3050  assert(propdata != NULL);
3051 
3052  objval = SCIPvarGetObj(var);
3054  {
3055  contrib = SCIPvarGetUbGlobal(var);
3056  if( !SCIPisInfinity(scip, contrib) )
3057  contrib *= objval;
3058  }
3059  else
3060  {
3062  contrib = SCIPvarGetLbGlobal(var);
3063  if( !SCIPisInfinity(scip, -contrib) )
3064  contrib *= objval;
3065  else
3066  contrib *= -1.0;
3067  }
3068 
3069  return getMaxObjPseudoactivityResidualValue(scip, propdata, contrib);
3070 }
3071 
3072 /** returns the maximum pseudo objective activity of the objective function */
3073 static
3075  SCIP* scip, /**< SCIP data structure */
3076  SCIP_PROPDATA* propdata /**< propagator data */
3077  )
3078 {
3079  return getMaxObjPseudoactivityResidualValue(scip, propdata, 0.0);
3081 
3082 /** propagates the global domain of the given binary variable against the lower bound (c*x >= lowerbound) */
3083 static
3085  SCIP* scip, /**< SCIP data structure */
3086  SCIP_VAR* var, /**< variable to propagate */
3087  SCIP_Real lowerbound, /**< lower bound to use */
3088  SCIP_Real maxpseudoobjact, /**< maximum pseudo objective activity */
3089  SCIP_Bool useimplics, /**< should implications be used */
3090  SCIP_Bool* infeasible, /**< pointer to store if the variable domain got empty, infeasible */
3091  SCIP_Bool* tightened /**< pointer to store if the variable domain was tightened */
3092  )
3093 {
3094  SCIP_Real lbobjchg;
3095  SCIP_Real ubobjchg;
3096 
3097  assert(SCIPvarIsBinary(var));
3098  assert(SCIPisDualfeasLE(scip, lowerbound, maxpseudoobjact));
3099  assert(!SCIPisInfinity(scip, maxpseudoobjact));
3100 
3101  /*@todo Instead of running always over all implications use SCIP_OBJIMPLICS in the same way as for the propagation of
3102  * the minimum activity against the cutoff bound. If so we could use the cliques as well.
3103  */
3104 
3105  /* get contribution of variable by fixing it to its lower bound w.r.t. maximum activity of the objective function */
3106  SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_LOWER, useimplics, &lbobjchg) );
3107  assert(!SCIPisPositive(scip, lbobjchg));
3108 
3109  /* get contribution of variable by fixing it to its upper bound w.r.t. maximum activity of the objective function */
3110  SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_UPPER, useimplics, &ubobjchg) );
3111  assert(!SCIPisPositive(scip, ubobjchg));
3112 
3113  (*infeasible) = FALSE;
3114  (*tightened) = FALSE;
3115 
3116  /* if the maximum activity of the objective function without the contribution of the given variable shrinks below the
3117  * global lower bound, the contribution of the variable is need; hence, we can fix it to corresponding bound globally
3118  */
3119  if( SCIPisFeasLT(scip, maxpseudoobjact + lbobjchg, lowerbound) && SCIPisFeasLT(scip, maxpseudoobjact + ubobjchg, lowerbound) )
3120  {
3121  /* fixing the variable to zero or one leads to decreases of the maximum activity below the lower bound, hence, we
3122  * detected an cutoff
3123  */
3124  (*infeasible) = TRUE;
3125  }
3126  else if( SCIPisFeasLT(scip, maxpseudoobjact + lbobjchg, lowerbound) )
3127  {
3128  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, 1.0, FALSE, infeasible, tightened) );
3129  }
3130  else if( SCIPisFeasLT(scip, maxpseudoobjact + ubobjchg, lowerbound) )
3131  {
3132  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, 0.0, FALSE, infeasible, tightened) );
3133  }
3134 
3135  return SCIP_OKAY;
3136 }
3137 
3138 /** propagates the global domains of the given variable with non-zero objective coefficient against the lower bound
3139  * (c*x >= lowerbound)
3140  */
3141 static
3143  SCIP* scip, /**< SCIP data structure */
3144  SCIP_PROPDATA* propdata, /**< propagator data */
3145  SCIP_VAR* var, /**< variable to propagate */
3146  SCIP_Real lowerbound, /**< lower bound to use */
3147  SCIP_Bool* infeasible, /**< pointer to store if the variable domain got empty, infeasible */
3148  SCIP_Bool* tightened /**< pointer to store if the variable domain was tightened */
3149  )
3150 {
3151  SCIP_Real residual;
3152  SCIP_Real newbd;
3153  SCIP_Real objval;
3154 
3155  objval = SCIPvarGetObj(var);
3156  assert(!SCIPisZero(scip, objval));
3157 
3158  (*tightened) = FALSE;
3159 
3160  /* get residual pseudo objective activity, that is the pseudo objective activity without the given variable */
3161  residual = getMaxObjPseudoactivityResidual(scip, propdata, var);
3162 
3163  if( SCIPisInfinity(scip, residual) )
3164  return SCIP_OKAY;
3165 
3166  /* compute potential mew bound */
3167  newbd = (lowerbound - residual) / objval;
3168 
3169  /**@note In case the variable is integral we force the update of the new bound */
3170 
3171  if( objval > 0.0 )
3172  {
3173  SCIP_Real lb;
3174 
3175  lb = SCIPvarGetLbGlobal(var);
3176 
3177  if( !SCIPvarIsIntegral(var) )
3178  {
3179  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, FALSE, infeasible, tightened) );
3180  }
3181  else if( SCIPisFeasGT(scip, newbd, lb) )
3182  {
3183  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, TRUE, infeasible, tightened) );
3184  }
3185  }
3186  else
3187  {
3188  SCIP_Real ub;
3189 
3190  ub = SCIPvarGetUbGlobal(var);
3191 
3192  if( !SCIPvarIsIntegral(var) )
3193  {
3194  SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, FALSE, infeasible, tightened) );
3195  }
3196  else if( SCIPisFeasLT(scip, newbd, ub) )
3197  {
3198  SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, TRUE, infeasible, tightened) );
3199  }
3200  }
3201 
3202  return SCIP_OKAY;
3203 }
3204 
3205 /** propagates the global lower (dual) bound c*x >= lowerbound */
3206 static
3208  SCIP* scip, /**< SCIP data structure */
3209  SCIP_PROP* prop, /**< propagator */
3210  SCIP_RESULT* result /**< pointer to store the result of the callback method */
3211  )
3212 { /*lint --e{715}*/
3213  SCIP_PROPDATA* propdata;
3214  SCIP_Real lowerbound;
3215  SCIP_Real maxpseudoobjact;
3216  SCIP_Bool cutoff;
3217  int nchgbds;
3218 
3219  assert(result != NULL);
3220 
3221  (*result) = SCIP_DIDNOTRUN;
3222  cutoff = FALSE;
3223  nchgbds = 0;
3224 
3225  propdata = SCIPpropGetData(prop);
3226  assert(propdata != NULL);
3227  assert(propdata->nminactvars > 0 || propdata->nobjintvars > 0);
3228 
3229  /* check if there is a chance to find a reduction */
3230  lowerbound = SCIPgetLowerbound(scip);
3231 
3232  if( SCIPisInfinity(scip, -lowerbound) )
3233  return SCIP_OKAY;
3234 
3235  /* if the lower bound did not change since the last propagation as well as the global bounds of the variables with a
3236  * non-zero objective coefficient we do nothing since there is no new information available
3237  */
3238  if( SCIPisLE(scip, lowerbound, propdata->lastlowerbound) && propdata->maxpseudoobjact < SCIP_INVALID )
3239  return SCIP_OKAY;
3240 
3241  /* updates the pseudo objective activity if necessary */
3242  updateMaxObjPseudoactivity(scip, propdata);
3243 
3244  /* if more than one variable contributes an infinity to the maximal pseudo activity we can do nothing */
3245  assert(propdata->maxpseudoobjact < SCIP_INVALID);
3246  if( propdata->maxpseudoobjactinf > 1 )
3247  return SCIP_OKAY;
3248 
3249  maxpseudoobjact = getMaxObjPseudoactivity(scip, propdata);
3250  assert(!SCIPisInfinity(scip, maxpseudoobjact) || !SCIPisInfinity(scip, lowerbound));
3251 
3252 #ifndef NDEBUG
3253  /* check that the global indices are correct */
3254  checkGlbfirstnonfixed(scip, propdata);
3255 #endif
3256 
3257  /* if the maximum pseudo objective activity is smaller than the lower bound the problem is infeasible */
3258  if( SCIPisDualfeasLT(scip, maxpseudoobjact, lowerbound) )
3259  cutoff = TRUE;
3260  else
3261  {
3262  SCIP_VAR** objintvars;
3263  SCIP_VAR* var;
3264  SCIP_Bool tightened;
3265  int nobjintvars;
3266  int v;
3267 
3268  if( propdata->maxpseudoobjactinf == 0 && !SCIPisInfinity(scip, maxpseudoobjact) )
3269  {
3270  SCIP_VAR** maxactvars;
3271  int nmaxactvars;
3272 
3273  maxactvars = propdata->maxactvars;
3274  nmaxactvars = propdata->nmaxactvars;
3275  assert(nmaxactvars == 0 || maxactvars != NULL);
3276 
3277  for( v = propdata->maxactfirstnonfixed; v < nmaxactvars; ++v )
3278  {
3279  var = maxactvars[v];
3280  assert(var != NULL);
3281  assert(SCIPvarIsBinary(var));
3282 
3283  /* check if the variables is already globally fixed; if so continue with the next potential candidate */
3284  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
3285  continue;
3286 
3287  /* try to propagate variable domain globally */
3288  SCIP_CALL( propagateLowerboundBinvar(scip, var, lowerbound, maxpseudoobjact, propdata->propuseimplics, &cutoff, &tightened) );
3289 
3290  /* the binary variables are sorted in non-increasing manner w.r.t. the absolute value of their objective
3291  * contribution w.r.t. maximum activity of the objective function; These values are the decrease we would
3292  * get with the maximum pseudo objective activity if we fix the variable to its best bound; hence, we can
3293  * stop if for a variable this potential decrease is not enough anymore to fall below the lower bound.
3294  *
3295  * @note In case a fixing was performed. The variable might not be globally fixed right away since this would
3296  * destroy the local internal data structure of a search node; the bound change is in that case pending;
3297  * hence we cannot assert that the variable is globally fixed
3298  */
3299  if( !tightened )
3300  {
3301  assert(!SCIPisInfinity(scip, propdata->maxpseudoobjact));
3302  SCIPdebugMsg(scip, "interrupt pseudo objective propagation w.r.t. lower bound <%.15g> for binary variables after %d from %d binary variables\n",
3303  lowerbound, v, nmaxactvars);
3304  break;
3305  }
3306 
3307  if( cutoff )
3308  break;
3309 
3310  /* update maximum pseudo activity since the previous global bound change might invalidated the maximum
3311  * pseudo activity
3312  */
3313  maxpseudoobjact = getMaxObjPseudoactivity(scip, propdata);
3314  nchgbds++;
3315  }
3316 
3317  /* update globally fixed index if abort criteria was applied */
3318  propdata->maxactfirstnonfixed = v;
3319 
3320  /* check all binary variables which could potentially be fixed */
3321  for( ; v < nmaxactvars && maxpseudoobjact - lowerbound < propdata->maxactchgs[v] && !cutoff; ++v )
3322  {
3323  var = maxactvars[v];
3324  assert(var != NULL);
3325  assert(SCIPvarIsBinary(var));
3326 
3327  /* check if the variables is already globally fixed; if so continue with the potential candidate */
3328  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
3329  continue;
3330 
3331  /* propagates the cutoff bound for the given binary variable */
3332  SCIP_CALL( propagateLowerboundBinvar(scip, var, lowerbound, maxpseudoobjact, propdata->propuseimplics, &cutoff, &tightened) );
3333 
3334  if( tightened )
3335  {
3336  /* update maximum pseudo activity since the previous global bound change might invalidated the maximum
3337  * pseudo activity
3338  */
3339  maxpseudoobjact = getMaxObjPseudoactivity(scip, propdata);
3340  nchgbds++;
3341  }
3342  }
3343 
3344 #if 0 /* might fail, but is not a real error, still need to investigate */
3345 #ifndef NDEBUG
3346  /* check that the abort criteria for the binary variables works */
3347  for( ; v < nmaxactvars && !cutoff; ++v )
3348  {
3349  var = maxactvars[v];
3350  assert(var != NULL);
3351  assert(SCIPvarIsBinary(var));
3352 
3353  /* check if the variables is already globally fixed; if so continue with the next potential candidate */
3354  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
3355  continue;
3356 
3357  /* try to propagate variable domain globally */
3358  SCIP_CALL( propagateLowerboundBinvar(scip, var, lowerbound, maxpseudoobjact, propdata->propuseimplics, &cutoff, &tightened) );
3359  assert(!tightened);
3360  assert(!cutoff);
3361  }
3362 #endif
3363 #endif
3364  }
3365 
3366  objintvars = propdata->objintvars;
3367  nobjintvars = propdata->nobjintvars;
3368  assert(nobjintvars == 0 || objintvars != NULL);
3369 
3370  /* propagate c*x >= lowerbound for non-binary variables */
3371  for( v = 0; v < nobjintvars && !cutoff; ++v )
3372  {
3373  var = objintvars[v];
3374  assert(var != NULL);
3375  assert(!SCIPisZero(scip, SCIPvarGetObj(var)));
3376 
3377  /* try to propagate variable domain globally */
3378  SCIP_CALL( propagateLowerboundVar(scip, propdata, var, lowerbound, &cutoff, &tightened) );
3379 
3380  if( tightened )
3381  nchgbds++;
3382  }
3383  }
3384 
3385  /* evaluate propagation results */
3386  if( cutoff )
3387  {
3388  /* we are done with solving since a global bound change is infeasible: cutoff root node */
3389  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
3390  (*result) = SCIP_CUTOFF;
3391  }
3392  else if( nchgbds > 0 )
3393  (*result) = SCIP_REDUCEDDOM;
3394 
3395  /* remember the lower bound which we already propagated */
3396  propdata->lastlowerbound = lowerbound;
3397 
3398  return SCIP_OKAY;
3399 }
3400 
3401 
3402 /*
3403  * Callback methods of propagator
3404  */
3405 
3406 /** copy method for propagator plugins (called when SCIP copies plugins) */
3407 static
3408 SCIP_DECL_PROPCOPY(propCopyPseudoobj)
3409 { /*lint --e{715}*/
3410  assert(scip != NULL);
3411  assert(prop != NULL);
3412  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
3413 
3414  /* call inclusion method of propagator */
3416 
3417  return SCIP_OKAY;
3418 }
3419 
3420 /** destructor of propagator to free user data (called when SCIP is exiting) */
3421 static
3422 SCIP_DECL_PROPFREE(propFreePseudoobj)
3423 { /*lint --e{715}*/
3424  SCIP_PROPDATA* propdata;
3425 
3426  /* free propagator data */
3427  propdata = SCIPpropGetData(prop);
3428  SCIPfreeBlockMemory(scip, &propdata);
3429  SCIPpropSetData(prop, NULL);
3430 
3431  return SCIP_OKAY;
3432 }
3433 
3434 
3435 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
3436 static
3437 SCIP_DECL_PROPINITSOL(propInitsolPseudoobj)
3438 {
3439  SCIP_PROPDATA* propdata;
3440 
3441  propdata = SCIPpropGetData(prop);
3442  assert(propdata != NULL);
3444  /* do nothing if active pricer are present and force flag is not TRUE */
3445  if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
3446  return SCIP_OKAY;
3447 
3448  /* if active pricer are present we want to catch the variable added event */
3449  if( SCIPgetNActivePricers(scip) > 0 )
3450  {
3451  assert(!propdata->catchvaradded);
3452  SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_VARADDED, propdata->eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) );
3453  propdata->catchvaradded = TRUE;
3454  }
3455 
3456  return SCIP_OKAY;
3457 }
3458 
3459 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
3460 static
3461 SCIP_DECL_PROPEXITSOL(propExitsolPseudoobj)
3462 { /*lint --e{715}*/
3463  SCIP_PROPDATA* propdata;
3464 
3465  propdata = SCIPpropGetData(prop);
3466  assert(propdata != NULL);
3468  if( propdata->catchvaradded )
3469  {
3470  /* drop the variable added event */
3471  SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_VARADDED, propdata->eventhdlr, (SCIP_EVENTDATA*)propdata, -1) );
3472  propdata->catchvaradded = FALSE;
3473  }
3474 
3475  /* free propagator data */
3476  SCIP_CALL( propdataExit(scip, propdata) );
3477 
3478  return SCIP_OKAY;
3479 }
3480 
3481 
3482 /** presolving method of propagator */
3483 static
3484 SCIP_DECL_PROPPRESOL(propPresolPseudoobj)
3485 { /*lint --e{715}*/
3486  SCIP_PROPDATA* propdata;
3487  SCIP_VAR** vars;
3488  SCIP_Real cutoffbound;
3489  SCIP_Real pseudoobjval;
3490  int oldnchgbds;
3491  int nvars;
3492  int v;
3493 
3494  assert(result != NULL);
3495 
3496  propdata = SCIPpropGetData(prop);
3497  assert(propdata != NULL);
3498 
3499  (*result) = SCIP_DIDNOTRUN;
3500 
3501  /* do nothing if active pricer are present and force flag is not TRUE */
3502  if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
3503  return SCIP_OKAY;
3504 
3505  /* do nothing if objective propagation is not allowed */
3506  if( !SCIPallowObjProp(scip) )
3507  return SCIP_OKAY;
3508 
3509  pseudoobjval = SCIPgetGlobalPseudoObjval(scip);
3510  if( SCIPisInfinity(scip, -pseudoobjval) )
3511  return SCIP_OKAY;
3512 
3513  cutoffbound = SCIPgetCutoffbound(scip);
3514  if( SCIPisInfinity(scip, cutoffbound) )
3515  return SCIP_OKAY;
3516 
3517  if( SCIPisGE(scip, pseudoobjval, cutoffbound) )
3518  {
3519  (*result) = SCIP_CUTOFF;
3520  return SCIP_OKAY;
3521  }
3522 
3523  /* only propagate if a new cutoff bound or global pseudo objective value is available */
3524  if( cutoffbound < propdata->cutoffbound || pseudoobjval > propdata->glbpseudoobjval )
3525  {
3526  SCIP_Real objval;
3527  SCIP_Bool tightened;
3528 
3529  (*result) = SCIP_DIDNOTFIND;
3530  oldnchgbds = *nchgbds;
3531 
3532  /* get the problem variables */
3533  vars = SCIPgetVars(scip);
3534  nvars = SCIPgetNVars(scip);
3535 
3536  /* scan the variables for pseudoobj bound reductions
3537  * (loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array)
3538  */
3539  for( v = nvars - 1; v >= 0; --v )
3540  {
3541  objval = SCIPvarGetObj(vars[v]);
3542 
3543  if( SCIPisZero(scip, objval) )
3544  continue;
3545 
3546  SCIP_CALL( propagateCutoffboundVar(scip, NULL, vars[v], -1, objval, cutoffbound, pseudoobjval, FALSE, &tightened) );
3547 
3548  if( tightened )
3549  (*nchgbds)++;
3550  }
3551 
3552  /* evaluate if bound change was detected */
3553  if( *nchgbds > oldnchgbds )
3554  (*result) = SCIP_SUCCESS;
3555 
3556  /* store the old values */
3557  propdata->cutoffbound = cutoffbound;
3558  propdata->glbpseudoobjval = pseudoobjval;
3559  propdata->glbpropagated = TRUE;
3560  }
3561 
3562  return SCIP_OKAY;
3563 }
3564 
3565 /** execution method of propagator */
3566 static
3567 SCIP_DECL_PROPEXEC(propExecPseudoobj)
3568 { /*lint --e{715}*/
3569  SCIP_PROPDATA* propdata;
3570 
3571  propdata = SCIPpropGetData(prop);
3572  assert(propdata != NULL);
3574  (*result) = SCIP_DIDNOTRUN;
3575 
3576  if( SCIPinProbing(scip) )
3577  return SCIP_OKAY;
3578 
3579  if( proptiming == SCIP_PROPTIMING_DURINGLPLOOP && SCIPgetDepth(scip) != 0 )
3580  return SCIP_OKAY;
3581 
3582  /* do nothing if active pricer are present and force flag is not TRUE */
3583  if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
3584  return SCIP_OKAY;
3585 
3586  /* do not run if propagation w.r.t. objective is not allowed */
3587  if( !SCIPallowObjProp(scip) )
3588  return SCIP_OKAY;
3589 
3590  /* check if enough new variable are added (due to column generation to reinitialized the propagator data) */
3591  if( !propdata->initialized || propdata->nnewvars > propdata->maxnewvars )
3592  {
3593  /* free current propdata data */
3594  SCIP_CALL( propdataExit(scip, propdata) );
3595 
3596  /* initialize propdata data from scratch */
3597  SCIP_CALL( propdataInit(scip, propdata) );
3598  }
3599 
3600  /* nothing to do for zero objective */
3601  if( propdata->nminactvars == 0 && propdata->nmaxactvars == 0 && propdata->nobjintvars == 0 )
3602  return SCIP_OKAY;
3603 
3604  /* propagate c*x <= cutoff */
3605  SCIP_CALL( propagateCutoffbound(scip, prop, result) );
3606 
3607  if( (*result) != SCIP_CUTOFF && (propdata->nmaxactvars > 0 || propdata->nobjintvars > 0) && SCIPgetStage(scip) == SCIP_STAGE_SOLVING )
3608  {
3609  SCIP_RESULT dualresult;
3610 
3611  /* propagates the global lower (dual) bound c*x >= lowerbound */
3612  SCIP_CALL( propagateLowerbound(scip, prop, &dualresult) );
3613 
3614  if( dualresult == SCIP_REDUCEDDOM || dualresult == SCIP_CUTOFF )
3615  (*result) = dualresult;
3616  }
3617 
3618  return SCIP_OKAY;
3619 }
3620 
3621 /** propagation conflict resolving method of propagator */
3622 static
3623 SCIP_DECL_PROPRESPROP(propRespropPseudoobj)
3624 { /*lint --e{715}*/
3625  SCIP_PROPDATA* propdata;
3626  SCIP_Real cutoffbound;
3627 
3628  assert(!SCIPisEQ(scip, SCIPvarGetLbGlobal(infervar), SCIPvarGetUbGlobal(infervar)));
3630  propdata = SCIPpropGetData(prop);
3631  assert(propdata != NULL);
3632 
3633  cutoffbound = SCIPgetCutoffbound(scip);
3634  assert(!SCIPisInfinity(scip, cutoffbound));
3635  assert(infervar != NULL);
3636 
3637  SCIPdebugMsg(scip, "resolve bound change <%s> %s <%g>(%g), cutoff bound <%g>\n", SCIPvarGetName(infervar),
3638  boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE),
3639  SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, FALSE), cutoffbound);
3640 
3641  /* resolve the propagation of the inference variable w.r.t. required minactivity */
3642  SCIP_CALL( resolvePropagation(scip, propdata, cutoffbound, infervar, inferinfo, boundtype, bdchgidx) );
3643 
3644  (*result) = SCIP_SUCCESS;
3645 
3646  return SCIP_OKAY;
3647 }
3648 
3649 
3650 /*
3651  * Event handler
3652  */
3653 
3654 /** execution method of bound change event handler */
3655 static
3656 SCIP_DECL_EVENTEXEC(eventExecPseudoobj)
3657 { /*lint --e{715}*/
3658  SCIP_PROPDATA* propdata;
3659  SCIP_EVENTTYPE eventtype;
3660 
3661  propdata = (SCIP_PROPDATA*)eventdata;
3662  assert(propdata != NULL);
3663 
3664  assert(eventhdlr != NULL);
3665  assert(eventdata != NULL);
3666  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
3667  assert(event != NULL);
3668 
3669  eventtype = SCIPeventGetType(event);
3670 
3671  switch( eventtype )
3672  {
3675  /* if bound got relaxed we need to start up front for trial of bound tightening */
3676  propdata->firstnonfixed = 0;
3677  break;
3679  propdata->nnewvars++;
3680  break;
3681  default:
3682  assert(eventtype == SCIP_EVENTTYPE_GLBCHANGED || eventtype == SCIP_EVENTTYPE_GUBCHANGED);
3683 
3684  /* invalidate the maximum pseudo objective activity */
3685  propdata->maxpseudoobjact = SCIP_INVALID;
3686  propdata->maxpseudoobjactinf = 0;
3687  }
3688 
3689  return SCIP_OKAY;
3690 }
3691 
3692 
3693 /*
3694  * propagator specific interface methods
3695  */
3696 
3697 /** creates the pseudo objective function propagator and includes it in SCIP */
3699  SCIP* scip /**< SCIP data structure */
3700  )
3701 {
3702  SCIP_PROPDATA* propdata;
3703  SCIP_PROP* prop;
3705  /* create pseudoobj propagator data */
3706  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
3707 
3708  /* reset propagator data structure */
3709  propdataReset(scip, propdata);
3710 
3711  propdata->eventhdlr = NULL;
3712  /* include event handler for gloabl bound change events and variable added event (in case of pricing) */
3713  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
3714  eventExecPseudoobj, NULL) );
3715 
3716  if( propdata->eventhdlr == NULL )
3717  {
3718  SCIPerrorMessage("event handler for pseudo objective propagator not found\n");
3719  return SCIP_PLUGINNOTFOUND;
3720  }
3721 
3722  /* include propagator */
3724  propExecPseudoobj,
3725  propdata) );
3726  assert(prop != NULL);
3727 
3728  /* set optional callbacks via setter functions */
3729  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyPseudoobj) );
3730  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreePseudoobj) );
3731  SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolPseudoobj) );
3732  SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolPseudoobj) );
3734  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropPseudoobj) );
3735 
3736  /* add pseudoobj propagator parameters */
3737  SCIP_CALL( SCIPaddIntParam(scip,
3738  "propagating/" PROP_NAME "/minuseless",
3739  "minimal number of successive non-binary variable propagator whithout a bound reduction before aborted",
3740  &propdata->minuseless, TRUE, DEFAULT_MINUSELESS, 0, INT_MAX, NULL, NULL) );
3741 
3743  "propagating/" PROP_NAME "/maxvarsfrac",
3744  "maximal fraction of non-binary variables with non-zero objective without a bound reduction before aborted",
3745  &propdata->maxvarsfrac, TRUE, DEFAULT_MAXVARSFRAC, 0.0, 1.0, NULL, NULL) );
3746 
3748  "propagating/" PROP_NAME "/propfullinroot",
3749  "do we want to propagate all non-binary variables if we are propagating the root node",
3750  &propdata->propfullinroot, TRUE, DEFAULT_PROPFULLINROOT, NULL, NULL) );
3751 
3753  "propagating/" PROP_NAME "/propcutoffbound",
3754  "propagate new cutoff bound directly globally",
3755  &propdata->propcutoffbound, TRUE, DEFAULT_PROPCUTOFFBOUND, NULL, NULL) );
3756 
3758  "propagating/" PROP_NAME "/force",
3759  "should the propagator be forced even if active pricer are present?",
3760  &propdata->force, TRUE, DEFAULT_FORCE, NULL, NULL) );
3761 
3762  SCIP_CALL( SCIPaddIntParam(scip,
3763  "propagating/" PROP_NAME "/maxnewvars",
3764  "number of variable added after the propgatore is reinitialized?",
3765  &propdata->maxnewvars, TRUE, DEFAULT_MAXNEWVARS, 0, INT_MAX, NULL, NULL) );
3766 
3768  "propagating/" PROP_NAME "/propuseimplics",
3769  "use implications to strengthen the propagation of binary variable (increasing the objective change)?",
3770  &propdata->propuseimplics, TRUE, DEFAULT_PROPUSEIMPLICS, NULL, NULL) );
3771 
3773  "propagating/" PROP_NAME "/respropuseimplics",
3774  "use implications to strengthen the resolve propagation of binary variable (increasing the objective change)?",
3775  &propdata->respropuseimplics, TRUE, DEFAULT_RESPROPUSEIMPLICS, NULL, NULL) );
3776 
3777  SCIP_CALL( SCIPaddIntParam(scip,
3778  "propagating/" PROP_NAME "/maximplvars",
3779  "maximum number of binary variables the implications are used if turned on (-1: unlimited)?",
3780  &propdata->maximplvars, TRUE, DEFAULT_MAXIMPLVARS, -1, INT_MAX, NULL, NULL) );
3781 
3782  return SCIP_OKAY;
3783 }
3784 
3785 /** propagates the cutoff bound for the given variables */
3787  SCIP* scip, /**< SCIP data structure */
3788  SCIP_PROP* prop, /**< propagator, or NULL */
3789  SCIP_VAR* var, /**< variables to propagate */
3790  SCIP_Real cutoffbound, /**< cutoff bound to use */
3791  SCIP_Real pseudoobjval, /**< pseudo objective value to use */
3792  SCIP_Bool* tightened /**< pointer to if the domain was tightened */
3793  )
3794 {
3795  SCIP_Real objval;
3796 
3797  objval = SCIPvarGetObj(var);
3798 
3799  SCIP_CALL( propagateCutoffboundVar(scip, prop, var, -1, objval, cutoffbound, pseudoobjval, TRUE, tightened) );
3800 
3801  return SCIP_OKAY;
3802 }
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:349
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:116
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)
#define NULL
Definition: def.h:239
SCIP_BOUNDTYPE SCIPvarGetWorstBoundType(SCIP_VAR *var)
Definition: var.c:17468
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:10958
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3343
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:99
#define PROP_FREQ
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2130
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:3176
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:412
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1994
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2265
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:422
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:132
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:17343
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3233
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:17399
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17706
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:5808
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:172
#define DEFAULT_MAXNEWVARS
void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16909
#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:65
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:314
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:418
#define DEFAULT_MINUSELESS
static SCIP_DECL_SORTPTRCOMP(objimplicsComp)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:501
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
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)
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:17036
#define SCIP_EVENTTYPE_GLBCHANGED
Definition: type_event.h:61
public methods for problem variables
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
static SCIP_RETCODE propagateCutoffbound(SCIP *scip, SCIP_PROP *prop, SCIP_RESULT *result)
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:611
public methods for SCIP variables
#define PROP_DELAY
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:177
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:89
#define SCIPdebugMsg
Definition: scip_message.h:88
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:155
#define EVENTHDLR_DESC
SCIP_RETCODE SCIPpropagateCutoffboundVar(SCIP *scip, SCIP_PROP *prop, SCIP_VAR *var, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, SCIP_Bool *tightened)
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17695
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2224
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
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:2014
public methods for querying solving statistics
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3025
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:64
#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:17353
static SCIP_RETCODE collectMinactObjchg(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE bound, SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedvars, int nbinobjvars, SCIP_VAR **contributors, SCIP_HASHTABLE *uselesscliques, int *ncontributors, SCIP_Real *objchg)
static SCIP_RETCODE objimplicsDelPos(SCIP *scip, SCIP_OBJIMPLICS *objimplics, int pos)
#define SCIPerrorMessage
Definition: pub_message.h:45
static SCIP_RETCODE propagateCutoffboundBinvar(SCIP *scip, SCIP_PROP *prop, SCIP_VAR *var, int pos, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, SCIP_Bool *tightened, SCIP_Bool *cutoff, SCIP_Bool local)
int SCIPgetCutoffdepth(SCIP *scip)
Definition: scip_tree.c:541
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:128
static SCIP_RETCODE collectMinactImplicVars(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE bound, SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedvars, int nbinobjvars, SCIP_VAR **contributors, SCIP_HASHTABLE *uselesscliques, int *ncontributors, SCIP_Real *objchg)
#define MAX_CLIQUELENGTH
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
static SCIP_DECL_PROPPRESOL(propPresolPseudoobj)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6139
#define PROP_DESC
#define PROP_PRESOL_MAXROUNDS
void SCIPsortDownPtrPtr(void **ptrarray1, void **ptrarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define REALABS(x)
Definition: def.h:174
#define SCIP_EVENTTYPE_UBRELAXED
Definition: type_event.h:66
#define DEFAULT_PROPUSEIMPLICS
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Real cutoffbound, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
static SCIP_RETCODE dropObjEvent(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var)
#define SCIP_CALL(x)
Definition: def.h:351
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:5922
static SCIP_DECL_PROPCOPY(propCopyPseudoobj)
void SCIPhashtableRemoveAll(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2473
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE objimplicsFree(SCIP *scip, SCIP_OBJIMPLICS **objimplics)
Definition: grphload.c:88
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:130
public data structures and miscellaneous methods
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17653
static SCIP_DECL_PROPEXITSOL(propExitsolPseudoobj)
#define SCIP_Bool
Definition: def.h:62
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
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:995
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:715
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17621
static SCIP_Real getVarObjchg(SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BOUNDTYPE bound)
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11422
#define MIN(x, y)
Definition: def.h:209
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3355
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:388
static SCIP_DECL_HASHKEYEQ(cliqueIsHashkeyEq)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17191
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:221
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:468
int SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2272
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:17667
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:301
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:152
public methods for the LP relaxation, rows and columns
public methods for variable pricer plugins
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:931
#define DEFAULT_RESPROPUSEIMPLICS
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2064
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2044
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:17638
public methods for managing events
general public methods
#define MAX(x, y)
Definition: def.h:208
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:382
#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:7473
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1999
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip_prop.c:285
static SCIP_DECL_HASHKEYVAL(cliqueGetHashkeyVal)
static void propdataReset(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1217
#define SCIP_Real
Definition: def.h:150
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:38
SCIP_Real SCIPgetGlobalPseudoObjval(SCIP *scip)
Definition: scip_lp.c:366
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:170
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:237
SCIP_Bool SCIPisDualfeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:779
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:789
unsigned int SCIPcliqueGetId(SCIP_CLIQUE *clique)
Definition: implics.c:3365
SCIP_BOUNDTYPE SCIPvarGetBestBoundType(SCIP_VAR *var)
Definition: var.c:17455
public methods for propagator plugins
#define PROP_NAME
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2377
static SCIP_DECL_EVENTEXEC(eventExecPseudoobj)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void checkGlbfirstnonfixed(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17409
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:117
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3333
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6259
static SCIP_RETCODE dropVarEvents(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2874
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
SCIP_Real SCIPgetPseudoObjval(SCIP *scip)
Definition: scip_lp.c:391
#define SCIP_EVENTTYPE_GUBCHANGED
Definition: type_event.h:62
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:16920
#define SCIP_EVENTTYPE_VARADDED
Definition: type_event.h:56
#define DEFAULT_MAXIMPLVARS
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:211
#define ABS(x)
Definition: def.h:204
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
SCIP_Bool SCIPallowObjProp(SCIP *scip)
Definition: scip_var.c:8488
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:129
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17016
public methods for propagators
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:134
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:184
#define PROP_TIMING
#define SCIP_EVENTTYPE_BOUNDRELAXED
Definition: type_event.h:107
memory allocation routines