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-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop_pseudoobj.c
17  * @ingroup DEFPLUGINS_PROP
18  * @brief Pseudo objective propagator
19  * @author Tobias Achterberg
20  * @author Stefan Heinz
21  *
22  * This propagator propagates the objective function using the cutoff bound and the pseudo objective value. The pseudo
23  * objective value can be seen as minimum activity of the linear objective function. Using this, this propagator checks
24  * if variables with non-zero objective coefficients can exceed the cutoff bound. If this is the case the corresponding
25  * bound can be tightened.
26  *
27  * @todo use the complete implication to initialize the objective implication data structure
28  */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 #include "blockmemshell/memory.h"
33 #include "scip/prop_pseudoobj.h"
34 #include "scip/pub_event.h"
35 #include "scip/pub_implics.h"
36 #include "scip/pub_message.h"
37 #include "scip/pub_misc.h"
38 #include "scip/pub_misc_sort.h"
39 #include "scip/pub_prop.h"
40 #include "scip/pub_var.h"
41 #include "scip/scip_conflict.h"
42 #include "scip/scip_event.h"
43 #include "scip/scip_general.h"
44 #include "scip/scip_lp.h"
45 #include "scip/scip_mem.h"
46 #include "scip/scip_message.h"
47 #include "scip/scip_numerics.h"
48 #include "scip/scip_param.h"
49 #include "scip/scip_pricer.h"
50 #include "scip/scip_prob.h"
51 #include "scip/scip_probing.h"
52 #include "scip/scip_prop.h"
53 #include "scip/scip_solvingstats.h"
54 #include "scip/scip_tree.h"
55 #include "scip/scip_var.h"
56 #include <string.h>
57 
58 #define PROP_NAME "pseudoobj"
59 #define PROP_DESC "pseudo objective function propagator"
60 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP
61 #define PROP_PRIORITY 3000000 /**< propagator priority */
62 #define PROP_FREQ 1 /**< propagator frequency */
63 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
64 #define PROP_PRESOL_PRIORITY +6000000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
65 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
66  * limit) */
67 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */
68 
69 #define EVENTHDLR_NAME "pseudoobj"
70 #define EVENTHDLR_DESC "bound change event handler for pseudo objective function propagator"
71 
72 #define DEFAULT_MINUSELESS 100 /**< minimal number of successive non-binary variable propagator whithout a
73  * bound reduction before aborted */
74 #define DEFAULT_MAXVARSFRAC 0.1 /**< maximal fraction of non-binary variables with non-zero objective
75  * without a bound reduction before aborted */
76 #define DEFAULT_PROPFULLINROOT TRUE /**< do we want to propagate all non-binary variables if we are propagating the root node? */
77 #define DEFAULT_PROPCUTOFFBOUND TRUE /**< propagate new cutoff bound directly globally */
78 #define DEFAULT_FORCE FALSE /**< should the propagator be forced even if active pricer are present? Note that
79  * can be done if it is known that the pseudo objective activity is given by
80  * the zero bound for all variables which are currently not present in the
81  * problem */
82 #define DEFAULT_MAXNEWVARS 1000 /**< number of variable added after the propagator is reinitialized? */
83 #define DEFAULT_PROPUSEIMPLICS TRUE /**< use implications to strengthen the propagation of binary variable (increasing the objective change)? */
84 #define DEFAULT_RESPROPUSEIMPLICS TRUE /**< use implications to strengthen the resolve propagation of binary variable (increasing the objective change)? */
85 #define DEFAULT_MAXIMPLVARS 50000 /**< maximum number of binary variables the implications are used if turned on (-1: unlimited)? */
86 
87 
88 /*
89  * Data structures
90  */
91 
92 /** implication data structure for objective contributions of a binary variable */
93 struct SCIP_ObjImplics
94 {
95  SCIP_VAR** objvars; /**< variables y in implications y == 0 or y == 1, first we store the
96  * implications by x == 0 and second the implications x == 1 */
97  SCIP_Real maxobjchg; /**< maximum objective contribution if variables x is fixed to zero or one */
98  int nlbimpls; /**< number of all implications result through for x == 0 */
99  int nubimpls; /**< number of all implications result through for x == 1 */
100  int size; /**< size of the objvars array */
101 };
102 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) */
105 /** propagator data */
106 struct SCIP_PropData
107 {
108  SCIP_EVENTHDLR* eventhdlr; /**< event handler for global bound change events */
109  SCIP_VAR** minactvars; /**< binary variables with non-zero objective contribution w.r.t. minimum activity of the objective function */
110  SCIP_OBJIMPLICS** minactimpls; /**< implication data structure for the binary variables w.r.t. minimum activity */
111  SCIP_VAR** maxactvars; /**< binary variables with non-zero objective contribution w.r.t. maximum activity of the objective function */
112  SCIP_Real* maxactchgs; /**< the maximal potential change of the objective if the binary variable
113  * is fixed to its best bound w.r.t. maximum activity of the objective function */
114 
115  SCIP_VAR** objintvars; /**< non-binary variable with non-zero objective coefficient */
116  SCIP_HASHTABLE* addedvars; /**< hash table used during resolving of a bound change (conflict analysis) */
117  SCIP_Real lastlowerbound; /**< last lower bound which was propagated */
118  SCIP_Real cutoffbound; /**< last cutoff bound used for propagation */
119  SCIP_Real glbpseudoobjval; /**< last global pseudo objective used in presolving */
120  SCIP_Real maxvarsfrac; /**< maximal fraction of non-binary variables with non-zero objective
121  * without a bound reduction before aborted
122  */
123  SCIP_Real maxpseudoobjact; /**< maximal global pseudo objective activity */
124  int maxpseudoobjactinf; /**< number of coefficients contributing with infinite value to maxpseudoobjact */
125  int nminactvars; /**< number of binary variables with non-zero objective contribution w.r.t. minimum activity of the objective function */
126  int nmaxactvars; /**< number of binary variables with non-zero objective contribution w.r.t. maximum activity of the objective function */
127  int nobjintvars; /**< number of non-binary variables with non-zero objective */
128  int minuseless; /**< minimal number of successive non-binary variable propagator whithout
129  * a bound reduction before aborted
130  */
131  int lastvarnum; /**< last non-binary variable number that was looked at */
132  int glbfirstnonfixed; /**< index of first globally non-fixed binary variable in minactvars array */
133  int maxactfirstnonfixed;/**< index of first globally non-fixed binary variable in maxctvars array */
134  int firstnonfixed; /**< index of first locally non-fixed binary variable in minactvars array */
135  int nnewvars; /**< counter for counting number of new variables added */
136  int maxnewvars; /**< number of variable added after the propagator is reinitialized? */
137  int maximplvars; /**< maximum number of binary variables the implications are used if turned on (-1: unlimited)? */
138  int minactsize; /**< size of minactvars and minactimpls array */
139  int maxactsize; /**< size of maxactvars and maxactchgs array */
140  int objintvarssize; /**< size of objintvars array*/
141  SCIP_Bool glbpropagated; /**< are global domains propagated */
142  SCIP_Bool propfullinroot; /**< do we want to propagate all non-binary variables if we are propagating the root node */
143  SCIP_Bool propcutoffbound; /**< propagate new cutoff bound directly globally */
144  SCIP_Bool force; /**< should the propagator be forced even if active pricer are present? */
145  SCIP_Bool catchvaradded; /**< do we catch the variable added event? */
146  SCIP_Bool propuseimplics; /**< use implications to strengthen the propagation of binary variable (increasing the objective change)? */
147  SCIP_Bool respropuseimplics; /**< use implications to strengthen the resolve propagation of binary variable (increasing the objective change)? */
148  SCIP_Bool initialized; /**< is propagator data structure initialized */
149 };
150 
151 /*
152  * Debug methods
153  */
154 
155 #ifndef NDEBUG
156 /** check that the implications are applied for a globally fixed variable */
157 static
159  SCIP* scip, /**< SCIP data structure */
160  SCIP_VAR* var /**< variable to check the implications */
161  )
162 {
163  SCIP_VAR** vars;
164  SCIP_Real* bounds;
165  SCIP_BOUNDTYPE* boundtypes;
166  SCIP_Bool varfixing;
167  int nvars;
168  int v;
169 
170  /* check that the given variable is locally or globally fixed */
171  assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5);
172 
173  /* get fixed value */
174  varfixing = SCIPvarGetLbGlobal(var) > 0.5;
175 
176  vars = SCIPvarGetImplVars(var, varfixing);
177  nvars = SCIPvarGetNImpls(var, varfixing);
178  bounds = SCIPvarGetImplBounds(var, varfixing);
179  boundtypes = SCIPvarGetImplTypes(var, varfixing);
180 
181  /* check that each implication was applied */
182  for( v = 0; v < nvars; ++v )
183  {
184  if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
185  {
186  SCIP_Real lb;
187 
188  lb = SCIPvarGetLbGlobal(vars[v]);
189  assert(SCIPisLE(scip, lb, bounds[v]));
190  }
191  else
192  {
193  SCIP_Real ub;
194 
195  assert(boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
196 
197  ub = SCIPvarGetLbGlobal(vars[v]);
198  assert(SCIPisGE(scip, ub, bounds[v]));
199  }
200  }
201 }
202 
203 /** check if the global fixed indices are correct */
204 static
206  SCIP_PROPDATA* propdata /**< propagator data */
207  )
208 {
209  SCIP_VAR* var;
210  int v;
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 = SCIPhashmapGetImageInt(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 = SCIPhashmapGetImageInt(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_PROPDATA* propdata /**< propagator data */
688  )
689 {
690  propdata->minactvars = NULL;
691  propdata->minactimpls = NULL;
692  propdata->maxactvars = NULL;
693  propdata->maxactchgs = NULL;
694  propdata->objintvars = NULL;
695  propdata->nminactvars = 0;
696  propdata->nmaxactvars = 0;
697  propdata->nobjintvars = 0;
698  propdata->maxpseudoobjact = SCIP_INVALID;
699  propdata->maxpseudoobjactinf = 0;
700  propdata->lastvarnum = -1;
701  propdata->glbpropagated = FALSE;
702  propdata->cutoffbound = SCIP_INVALID;
703  propdata->lastlowerbound = -SCIP_INVALID;
704  propdata->glbpseudoobjval = -SCIP_INVALID;
705  propdata->glbfirstnonfixed = 0;
706  propdata->maxactfirstnonfixed = 0;
707  propdata->firstnonfixed = 0;
708  propdata->nnewvars = 0;
709  propdata->minactsize = 0;
710  propdata->maxactsize = 0;
711  propdata->objintvarssize = 0;
712  propdata->catchvaradded = FALSE;
713  propdata->initialized = FALSE;
714 }
715 
716 /** free propagator data */
717 static
719  SCIP* scip, /**< SCIP data structure */
720  SCIP_PROPDATA* propdata /**< propagator data */
721  )
722 {
723  int v;
725  if( !propdata->initialized )
726  return SCIP_OKAY;
727 
728  if( propdata->addedvars != NULL )
729  SCIPhashtableFree(&propdata->addedvars);
730 
731  /* drop events for the variables */
732  SCIP_CALL( dropVarEvents(scip, propdata) );
733 
734  for( v = 0; v < propdata->nminactvars; ++v )
735  {
736  SCIP_CALL( objimplicsFree(scip, &(propdata->minactimpls[v])) );
737  }
738 
739  /* free memory for non-zero objective variables */
740  SCIPfreeBlockMemoryArrayNull(scip, &propdata->minactvars, propdata->minactsize);
741  SCIPfreeBlockMemoryArrayNull(scip, &propdata->minactimpls, propdata->minactsize);
742  SCIPfreeBlockMemoryArrayNull(scip, &propdata->maxactvars, propdata->maxactsize);
743  SCIPfreeBlockMemoryArrayNull(scip, &propdata->maxactchgs, propdata->maxactsize);
744  SCIPfreeBlockMemoryArrayNull(scip, &propdata->objintvars, propdata->objintvarssize);
745 
746  /* reset propagator data structure */
747  propdataReset(propdata);
748 
749  return SCIP_OKAY;
750 }
751 
752 /** returns the objective change for the given binary variable */
753 static
755  SCIP_VAR* var, /**< variable to get objective change for */
756  SCIP_BOUNDTYPE boundtype, /**< bound type to consider */
757  SCIP_BOUNDTYPE bound /**< fixing bound */
758  )
759 {
760  assert(SCIPvarIsBinary(var));
761  assert((int)SCIP_BOUNDTYPE_LOWER == 0);
762  assert((int)SCIP_BOUNDTYPE_UPPER == 1);
763 
764  /* collect contribution of variable itself */
765  return (SCIP_Real)((int)bound - (int)(boundtype == SCIP_BOUNDTYPE_UPPER)) * SCIPvarGetObj(var);
766 }
767 
768 /** returns the objective change provided by the implication variable by fixing it to the given bound
769  * w.r.t. minimum activity of the objective function; additionally it collects all contributors for that objective
770  * change;
771  */
772 static
774  SCIP* scip, /**< SCIP data structure */
775  SCIP_VAR* var, /**< variable to computes the objective contribution */
776  SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
777  SCIP_Bool* collectedvars, /**< temporary buffer to mark collected variables */
778  int nbinobjvars, /**< number of binary variables with non-zero objective coefficient */
779  SCIP_VAR** contributors, /**< array to store the contributors */
780  int* ncontributors /**< pointer to store number of contributor to the objective contribution */
781  )
782 {
783  SCIP_Real objval;
784  int pos;
785 
786  assert(scip != NULL);
787  assert(var != NULL);
788  assert(binobjvarmap != NULL);
789  assert(collectedvars != NULL);
790  assert(contributors != NULL);
791  assert(ncontributors != NULL);
792 
793  /* ignore global fixed variables */
794  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 )
795  return 0.0;
796 
797  objval = SCIPvarGetObj(var);
798 
799  /* ignore variables with zero objective coefficient */
800  if( SCIPisZero(scip, objval) )
801  return 0.0;
802 
803  assert(SCIPhashmapExists(binobjvarmap, var));
804  pos = SCIPhashmapGetImageInt(binobjvarmap, var);
805  assert(pos > 0);
806 
807  /* check if the variables was already collected through other cliques */
808  if( collectedvars[pos] )
809  return 0.0;
810 
811  /* collect variable */
812  assert(*ncontributors < nbinobjvars);
813  contributors[*ncontributors] = var;
814  (*ncontributors)++;
815 
816  /* mark variable to be collected */
817  collectedvars[pos] = TRUE;
818 
819  /* return the absolute value of the objective coefficient as constriction */
820  return REALABS(objval);
821 }
822 
823 #define MAX_CLIQUELENGTH 50
824 /** returns the objective change provided by the implications of the given variable by fixing it to the given bound
825  * w.r.t. minimum activity of the objective function; additionally it collects all contributors for that objective
826  * change;
827  *
828  * Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to
829  * fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by the
830  * implications are:
831  *
832  * \f[
833  * \displaystyle
834  * 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)
835  * =
836  * sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{bestbound}(x)) \cdot \mbox{objval}(x)
837  * \f]
838  */
839 static
841  SCIP* scip, /**< SCIP data structure */
842  SCIP_VAR* var, /**< variable to computes the objective contribution */
843  SCIP_BOUNDTYPE bound, /**< bound to check for */
844  SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
845  SCIP_Bool* collectedvars, /**< temporary buffer to mark collected variables */
846  int nbinobjvars, /**< number of binary variables with non-zero objective coefficient */
847  SCIP_VAR** contributors, /**< array to store the contributors */
848  SCIP_HASHTABLE* uselesscliques, /**< hash table to store useless cliques, or NULL */
849  int* ncontributors, /**< pointer to store number of contributor to the objective contribution */
850  SCIP_Real* objchg /**< pointer to store the objective change */
851  )
852 {
853  SCIP_CLIQUE** cliques;
854  SCIP_CLIQUE* clique;
855  SCIP_VAR** vars;
856  SCIP_VAR* implvar;
857  SCIP_Bool* values;
858  SCIP_Bool varfixing;
859  int nbinvars;
860  int ncliques;
861  int c;
862  int v;
863 
864  assert(SCIPvarIsBinary(var));
865  assert(SCIPvarGetLbGlobal(var) < 0.5);
866  assert(SCIPvarGetUbGlobal(var) > 0.5);
867  assert(bound == SCIP_BOUNDTYPE_LOWER || bound == SCIP_BOUNDTYPE_UPPER);
868  assert(objchg != NULL);
869  assert(contributors != NULL);
870  assert(ncontributors != NULL);
871  assert(*ncontributors == 0);
872 
874  assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);
875  varfixing = (SCIP_Bool)bound;
876 
877  cliques = SCIPvarGetCliques(var, varfixing);
878  ncliques = SCIPvarGetNCliques(var, varfixing);
879 
880  if( uselesscliques == NULL )
881  return SCIP_INVALIDDATA;
882 
883 #ifndef NDEBUG
884  /* check that the marker array is reset */
885  for( c = 0; c < nbinobjvars; ++c )
886  assert(collectedvars[c] == FALSE);
887 #endif
888 
889  /* collect all implication which are given via cliques */
890  for( c = 0; c < ncliques; ++c )
891  {
892  SCIP_Bool useless;
893 
894  clique = cliques[c];
895  assert(clique != NULL);
896 
897  /* check if the clique was previously detected to be useless with respect to minimum activity */
898  if( SCIPhashtableExists(uselesscliques, (void*)clique) )
899  continue;
900 
901  nbinvars = SCIPcliqueGetNVars(clique);
902 
903  if( nbinvars > MAX_CLIQUELENGTH )
904  {
905  SCIP_CALL( SCIPhashtableInsert(uselesscliques, (void*)clique) );
906  continue;
907  }
908 
909  vars = SCIPcliqueGetVars(clique);
910  values = SCIPcliqueGetValues(clique);
911  useless = TRUE;
912 
913  for( v = 0; v < nbinvars; ++v )
914  {
915  implvar = vars[v];
916  assert(implvar != NULL);
917 
918  if( implvar == var )
919  {
920  /* check if the clique is useful at all */
921  if( useless )
922  {
923  SCIP_Real objval;
924 
925  objval = SCIPvarGetObj(var);
926 
927  if( varfixing == (SCIP_Bool)SCIPvarGetBestBoundType(var) && !SCIPisZero(scip, objval) )
928  useless = FALSE;
929  }
930  }
931  else if( values[v] == (SCIP_Bool)SCIPvarGetBestBoundType(implvar) )
932  {
933  useless = FALSE;
934  (*objchg) += collectMinactImplicVar(scip, implvar, binobjvarmap, collectedvars, nbinobjvars, contributors, ncontributors);
935  }
936  }
937 
938  /* if the clique is useless store it in the hash table to skip it later */
939  if( useless )
940  {
941  assert(!SCIPhashtableExists(uselesscliques, (void*)clique));
942  SCIP_CALL( SCIPhashtableInsert(uselesscliques, (void*)clique) );
943  }
944  }
945 
946  return SCIP_OKAY;
947 }
948 
949 /** returns the objective change provided by the implications of the given variable by fixing it to the given bound
950  * w.r.t. minimum activity of the objective function
951  *
952  * Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to
953  * fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by the
954  * implications are:
955  *
956  * \f[
957  * \displaystyle
958  * 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)
959  * =
960  * sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{bestbound}(x)) \cdot \mbox{objval}(x)
961  * \f]
962  *
963  * This can be done w.r.t. global variable bounds (local == FALSE), w.r.t. local variable bounds (local == TRUE &&
964  * bdchgidx == NULL), and w.r.t. given time stamp (local == TRUE && bdchgidx != NULL)
965  */
966 static
968  SCIP* scip, /**< SCIP data structure */
969  SCIP_VAR* var, /**< variable to computes the objective contribution */
970  SCIP_OBJIMPLICS* objimplics, /**< objective implication data for the given variable */
971  SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, or NULL */
972  SCIP_BOUNDTYPE bound, /**< bound to check for */
973  SCIP_Bool local, /**< propagate local bounds, otherwise global bounds */
974  SCIP_Real* objchg /**< pointer to store the objective change */
975  )
976 {
977  SCIP_VAR* implvar;
978  SCIP_Bool lb;
979  SCIP_Bool ub;
980  int nbinvars;
981  int v;
982 
983  assert(SCIPvarIsBinary(var));
984  assert(!local || SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE) < 0.5);
985  assert(!local || SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE) > 0.5);
986  assert(SCIPvarGetLbGlobal(var) < 0.5);
987  assert(SCIPvarGetUbGlobal(var) > 0.5);
988  assert(bound == SCIP_BOUNDTYPE_LOWER || bound == SCIP_BOUNDTYPE_UPPER);
989 
990  if( bound == SCIP_BOUNDTYPE_LOWER )
991  {
992  v = 0;
993  nbinvars = objimplics->nlbimpls;
994  }
995  else
996  {
997  assert(bound == SCIP_BOUNDTYPE_UPPER);
998  v = objimplics->nlbimpls;
999  nbinvars = objimplics->nlbimpls + objimplics->nubimpls;
1000  }
1001 
1002  /* loop over all implications */
1003  while( v < nbinvars )
1004  {
1005  implvar = objimplics->objvars[v];
1006  assert(implvar != NULL);
1007  assert(!SCIPisZero(scip, SCIPvarGetObj(implvar)));
1008 
1009  if( local )
1010  {
1011  lb = SCIPgetVarLbAtIndex(scip, implvar, bdchgidx, FALSE) > 0.5;
1012  ub = SCIPgetVarUbAtIndex(scip, implvar, bdchgidx, FALSE) > 0.5;
1013 
1014  /* check if variable is fixed */
1015  if( lb == TRUE || ub == FALSE )
1016  {
1017  v++;
1018  continue;
1019  }
1020  }
1021  else
1022  {
1023  lb = SCIPvarGetLbGlobal(implvar) > 0.5;
1024  ub = SCIPvarGetUbGlobal(implvar) > 0.5;
1025 
1026  /* check if variable is global fixed; if so remove it from the objective implication data structure and
1027  * continue with the next candidate
1028  */
1029  if( lb == TRUE || ub == FALSE )
1030  {
1031  SCIP_CALL( objimplicsDelPos(scip, objimplics, v) );
1032  nbinvars--;
1033  continue;
1034  }
1035  }
1036 
1037  assert(SCIPvarGetObj(implvar) > 0.0 || SCIPvarsHaveCommonClique(var, (SCIP_Bool) bound, implvar, TRUE, TRUE));
1038  assert(SCIPvarGetObj(implvar) < 0.0 || SCIPvarsHaveCommonClique(var, (SCIP_Bool) bound, implvar, FALSE, TRUE));
1039 
1040  /* add objective change */
1041  (*objchg) += REALABS(SCIPvarGetObj(implvar));
1042  v++;
1043  }
1044 
1045  return SCIP_OKAY;
1046 }
1047 
1048 /** computes for the given binary variable the objective contribution by fixing it to given bound w.r.t. minimum
1049  * activity of the objective function; additionally it collects all contributors for that objective change;
1050  */
1051 static
1053  SCIP* scip, /**< SCIP data structure */
1054  SCIP_VAR* var, /**< variable to computes the objective contribution */
1055  SCIP_BOUNDTYPE bound, /**< bound to check for */
1056  SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
1057  SCIP_Bool* collectedvars, /**< temporary buffer to mark collected variables */
1058  int nbinobjvars, /**< number of binary variables with non-zero objective coefficient */
1059  SCIP_VAR** contributors, /**< array to store the contriboters */
1060  SCIP_HASHTABLE* uselesscliques, /**< hash table to store useless cliques, or NULL */
1061  int* ncontributors, /**< pointer to store number of contributor to the objective contribution */
1062  SCIP_Real* objchg /**< pointer to store the objective change */
1063  )
1064 {
1065  assert(SCIPvarIsBinary(var));
1066  assert(contributors != NULL);
1067  assert(ncontributors != NULL);
1068 
1069  /* collects the contribution of the variable itself w.r.t. the best bound */
1070  (*objchg) = getVarObjchg(var, SCIPvarGetBestBoundType(var), bound);
1071 
1072  (*ncontributors) = 0;
1073 
1074  /* add the objective contribution from the implication variable */
1075  SCIP_CALL( collectMinactImplicVars(scip, var, bound, binobjvarmap, collectedvars, nbinobjvars, contributors, uselesscliques, ncontributors, objchg) );
1076 
1077  return SCIP_OKAY;
1078 }
1079 
1080 /** computes for the given binary variable the objective contribution by fixing it to given bound w.r.t. minimum
1081  * activity of the objective function; this can be done w.r.t. global variable bounds (local == FALSE), w.r.t. local
1082  * variable bounds (local == TRUE && bdchgidx == NULL), and w.r.t. given time stamp (local == TRUE && bdchgidx != NULL)
1083  */
1084 static
1086  SCIP* scip, /**< SCIP data structure */
1087  SCIP_VAR* var, /**< variable to computes the objective contribution */
1088  SCIP_OBJIMPLICS* objimplics, /**< objective implication data for the given variable */
1089  SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, or NULL */
1090  SCIP_BOUNDTYPE bound, /**< bound to check for */
1091  SCIP_Bool local, /**< propagate local bounds, otherwise global bounds */
1092  SCIP_Real* objchg /**< pointer to store the objective change */
1093  )
1094 {
1095  assert(SCIPvarIsBinary(var));
1096 
1097  /* collects the contribution of the variable itself w.r.t. the best bound */
1098  (*objchg) = getVarObjchg(var, SCIPvarGetBestBoundType(var), bound);
1099 
1100  /* add the objective contribution from the implication variable */
1101  SCIP_CALL( getMinactImplicObjchg(scip, var, objimplics, bdchgidx, bound, local, objchg) );
1102 
1103  return SCIP_OKAY;
1104 }
1105 
1106 /** returns the global (that means w.r.t. global bounds of the variables) objective change provided by all cliques of
1107  * the given variable by fixing it to the given bound w.r.t. maximum activity of the objective function
1108  *
1109  * Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to
1110  * fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by these
1111  * implications are:
1112  *
1113  * \f[
1114  * \displaystyle
1115  * 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)
1116  * =
1117  * sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{worstbound}(x)) \cdot \mbox{objval}(x)
1118  * \f]
1119  */
1120 static
1122  SCIP* scip, /**< SCIP data structure */
1123  SCIP_VAR* var, /**< variable to computes the objective contribution */
1124  SCIP_BOUNDTYPE bound, /**< bound to check for */
1125  SCIP_Real* objchg /**< pointer to store the objective change */
1126  )
1128  SCIP_Bool varfixing;
1129  int ncliques;
1130  int nvars;
1131 
1132  assert(scip != NULL);
1133  assert(SCIPvarIsBinary(var));
1134  assert(SCIPvarGetLbGlobal(var) < 0.5);
1135  assert(SCIPvarGetUbGlobal(var) > 0.5);
1136  assert(bound == SCIP_BOUNDTYPE_LOWER || bound == SCIP_BOUNDTYPE_UPPER);
1137  assert(objchg != NULL);
1138 
1139  varfixing = (SCIP_Bool)bound;
1140  assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE);
1141  assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);
1142 
1143  *objchg = 0.0;
1144  ncliques = SCIPvarGetNCliques(var, varfixing);
1145 
1146  if( ncliques > 0 )
1147  {
1148  SCIP_CLIQUE** cliques;
1149  SCIP_CLIQUE* clique;
1150  SCIP_VAR** clqvars;
1151  SCIP_VAR** probvars;
1152  SCIP_VAR* clqvar;
1153  SCIP_Bool* clqvalues;
1154  int* entries;
1155  int* ids;
1156  SCIP_Real obj;
1157  int nclqvars;
1158  int nentries;
1159  int objmult;
1160  int nids;
1161  int id;
1162  int c;
1163  int v;
1164 
1165  assert(SCIPisTransformed(scip));
1166 
1167  nentries = SCIPgetNVars(scip) - SCIPgetNContVars(scip) + 1;
1168 
1169  SCIP_CALL( SCIPallocBufferArray(scip, &ids, 2*nentries) );
1170  nids = 0;
1171  /* @todo move this memory allocation to SCIP_SET and add a memory list there, to decrease the number of
1172  * allocations and clear ups
1173  */
1174  SCIP_CALL( SCIPallocBufferArray(scip, &entries, nentries) );
1175  BMSclearMemoryArray(entries, nentries);
1176 
1177  cliques = SCIPvarGetCliques(var, varfixing);
1178  assert(cliques != NULL);
1179 
1180  /* iterate over all cliques and determine all importantimplications */
1181  for( c = ncliques - 1; c >= 0; --c )
1182  {
1183  clique = cliques[c];
1184  clqvars = SCIPcliqueGetVars(clique);
1185  clqvalues = SCIPcliqueGetValues(clique);
1186  nclqvars = SCIPcliqueGetNVars(clique);
1187  assert(nclqvars > 0);
1188  assert(clqvars != NULL);
1189  assert(clqvalues != NULL);
1190 
1191  if( nclqvars > MAX_CLIQUELENGTH )
1192  continue;
1193 
1194  /* iterate over all clique variables */
1195  for( v = nclqvars - 1; v >= 0; --v )
1196  {
1197  clqvar = clqvars[v];
1198  assert(clqvar != NULL);
1199 
1200  objmult = (int)!clqvalues[v] - (int)SCIPvarGetWorstBoundType(clqvar);
1201  assert(-1 <= objmult && objmult <= 1);
1202 
1203  /* ignore binary variable which are either fixed and were the objective contribution will not be zero */
1204  if( clqvar != var && objmult != 0 && SCIPvarIsActive(clqvar) &&
1205  (SCIPvarGetLbGlobal(clqvar) < 0.5 && SCIPvarGetUbGlobal(clqvar) > 0.5) && !SCIPisZero(scip, SCIPvarGetObj(clqvar)) )
1206  {
1207  int probindex = SCIPvarGetProbindex(clqvar) + 1;
1208  assert(0 < probindex && probindex < nentries);
1209 
1210  /* check that the variable was not yet visited */
1211  assert(entries[probindex] == 0 || entries[probindex] == objmult);
1212  if( entries[probindex] == 0 )
1213  {
1214  /* memorize probindex */
1215  ids[nids] = probindex;
1216  ++nids;
1217 
1218  assert(ABS(objmult) == 1);
1219 
1220  /* mark variable as visited */
1221  entries[probindex] = objmult;
1222  }
1223  }
1224  }
1225  }
1226 
1227  probvars = SCIPgetVars(scip);
1228  assert(probvars != NULL);
1229 
1230  /* add all implied objective values */
1231  for( v = nids - 1; v >= 0; --v )
1232  {
1233  id = ids[v];
1234  assert(0 < id && id < nentries);
1235  assert(entries[id] != 0);
1236 
1237  clqvar = probvars[id - 1];
1238  assert(clqvar != NULL);
1239  assert(SCIPvarIsBinary(clqvar));
1240  assert(SCIPvarIsActive(clqvar));
1241  assert(SCIPvarGetLbGlobal(clqvar) < 0.5);
1242  assert(SCIPvarGetUbGlobal(clqvar) > 0.5);
1243 
1244  obj = SCIPvarGetObj(clqvar);
1245  assert(!SCIPisZero(scip, obj));
1246 
1247  *objchg += entries[id] * obj;
1248  }
1249 
1250  /* free temporary memory */
1251  SCIPfreeBufferArray(scip, &entries);
1252  SCIPfreeBufferArray(scip, &ids);
1253  }
1254 
1255 #ifdef SCIP_MORE_DEBUG
1256  SCIPdebugMsg(scip, "objective contribution when variable <%s> fixed to %u using cliques is %g\n", SCIPvarGetName(var),
1257  varfixing, *objchg);
1258 #endif
1259 
1260  /* collect non-binary implication information */
1261  nvars = SCIPvarGetNImpls(var, varfixing);
1262 
1263  if( nvars > 0 )
1264  {
1265  SCIP_VAR** vars;
1266  SCIP_VAR* implvar;
1267  SCIP_Real* bounds;
1268  SCIP_BOUNDTYPE* boundtypes;
1269  SCIP_Real obj;
1270  SCIP_Real lb;
1271  SCIP_Real ub;
1272  int v;
1273 
1274  vars = SCIPvarGetImplVars(var, varfixing);
1275  boundtypes = SCIPvarGetImplTypes(var, varfixing);
1276  bounds = SCIPvarGetImplBounds(var, varfixing);
1277 
1278  for( v = nvars - 1; v >= 0; --v )
1279  {
1280  implvar = vars[v];
1281  assert(implvar != NULL);
1282 
1283  lb = SCIPvarGetLbLocal(implvar);
1284  ub = SCIPvarGetUbLocal(implvar);
1285  obj = SCIPvarGetObj(implvar);
1286 
1287  /* ignore binary variable which are fixed or not of column status */
1288  if( SCIPisZero(scip, obj) )
1289  continue;
1290 
1291  /* add up objective change if applicable */
1292  if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER && SCIPvarGetWorstBoundType(implvar) == SCIP_BOUNDTYPE_LOWER && SCIPisFeasGT(scip, bounds[v], lb) )
1293  *objchg += (bounds[v] - lb)*obj;
1294  else if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER && SCIPvarGetWorstBoundType(implvar) == SCIP_BOUNDTYPE_UPPER && SCIPisFeasLT(scip, bounds[v], ub) )
1295  *objchg += (bounds[v] - ub)*obj;
1296  }
1297  }
1298 
1299 #ifdef SCIP_MORE_DEBUG
1300  SCIPdebugMsg(scip, "objective contribution when variable <%s> fixed to %u using cliques and implications is %g\n", SCIPvarGetName(var),
1301  varfixing, *objchg);
1302 #endif
1303 
1304  return SCIP_OKAY;
1305 }
1306 
1307 /** computes for the given binary variable the gloabl (that means w.r.t. global bounds of the variables) objective
1308  * contribution by fixing it to given bound w.r.t. maximum activity of the objective function
1309  */
1310 static
1312  SCIP* scip, /**< SCIP data structure */
1313  SCIP_VAR* var, /**< variable to computes the objective contribution */
1314  SCIP_BOUNDTYPE bound, /**< bound to check for */
1315  SCIP_Bool useimplics, /**< should implications be used */
1316  SCIP_Real* objchg /**< pointer to store the objective change */
1317  )
1318 {
1319  assert(scip != NULL);
1320  assert(SCIPvarIsBinary(var));
1321  assert(objchg != NULL);
1322 
1323  *objchg = 0;
1324 
1325  /* check if the implications should be used to increase the objective contribution for given variable */
1326  if( useimplics )
1327  {
1328  /* using cliques and @todo other implications */
1329  SCIP_CALL( getMaxactImplicObjchg(scip, var, bound, objchg) );
1330  }
1331 
1332  /* collects the contribution of the variable itself w.r.t. the worst bound */
1333  *objchg += getVarObjchg(var, SCIPvarGetWorstBoundType(var), bound);
1334 
1335  return SCIP_OKAY;
1336 }
1337 
1338 /** reset variables array which marks variables which are collected */
1339 static
1340 void resetContributors(
1341  SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
1342  SCIP_Bool* collectedvars, /**< temporary buffer to mark collected variables which should be reset */
1343  SCIP_VAR** contributors, /**< temporary buffer to use for collecting contributors */
1344  int ncontributors /**< number of contributors */
1345  )
1347  SCIP_VAR* var;
1348  int pos;
1349  int c;
1350 
1351  for( c = 0; c < ncontributors; ++c )
1352  {
1353  var = contributors[c];
1354  assert(var != NULL);
1355 
1356  assert(SCIPhashmapExists(binobjvarmap, var));
1357  pos = SCIPhashmapGetImageInt(binobjvarmap, var);
1358  assert(pos > 0);
1359  collectedvars[pos] = FALSE;
1360  }
1361 }
1362 
1363 /** check if the given variable should be collected for the minimum activity propagation */
1364 static
1366  SCIP* scip, /**< SCIP data structure */
1367  SCIP_VAR* var, /**< variable to check */
1368  SCIP_OBJIMPLICS** objimplics, /**< pointer to store the objective implication data structure w.r.t. minimum activity */
1369  SCIP_Bool useimplics, /**< should implications be used */
1370  SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */
1371  SCIP_Bool* collectedlbvars, /**< temporary buffer to mark collected variables for lower bound fixing */
1372  SCIP_Bool* collectedubvars, /**< temporary buffer to mark collected variables for upper bound fixing */
1373  int nbinobjvars, /**< number of binary variables with non-zero objective coefficient */
1374  SCIP_VAR** contributors, /**< temporary buffer to use for collecting contributors */
1375  SCIP_HASHTABLE* uselesscliques, /**< hash table to store useless cliques, or NULL */
1376  SCIP_Bool* collect /**< pointer to store if the variable should be stored */
1377  )
1378 {
1379  SCIP_Real lbobjchg;
1380  SCIP_Real ubobjchg;
1381  SCIP_Real objval;
1382  int nlbcliques;
1383  int nubcliques;
1384 
1385  assert(objimplics != NULL);
1386 
1387  objval = SCIPvarGetObj(var);
1388  (*objimplics) = NULL;
1389 
1390  if( SCIPisZero(scip, objval) )
1391  (*collect) = FALSE;
1392  else
1393  (*collect) = TRUE;
1394 
1395  nlbcliques = SCIPvarGetNCliques(var, FALSE);
1396  nubcliques = SCIPvarGetNCliques(var, TRUE);
1397 
1398  /* check if implications should be used and if implications are existing */
1399  if( useimplics && nlbcliques + nubcliques > 0 )
1400  {
1401  int nlbcontributors;
1402  int nubcontributors;
1403 
1404  assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE);
1405  assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE);
1406 
1407  /* get contribution of variable by fixing it to its lower bound w.r.t. minimum activity of the objective function */
1408  SCIP_CALL( collectMinactObjchg(scip, var, SCIP_BOUNDTYPE_LOWER, binobjvarmap, collectedlbvars, nbinobjvars,
1409  contributors, uselesscliques, &nlbcontributors, &lbobjchg) );
1410  assert(!SCIPisNegative(scip, lbobjchg));
1411 
1412  SCIPdebugMsg(scip, "variable <%s> fixed to bound=%d implies %d(%d)\n", SCIPvarGetName(var),
1413  SCIP_BOUNDTYPE_LOWER, 0, nlbcontributors);
1414 
1415  /* ignore implications if the variable has a zero objective coefficient and implications only one variable, since
1416  * this is covered by that implied variable
1417  */
1418  if( !(*collect) && nlbcontributors == 1 )
1419  {
1420  /* reset lower bound contributors */
1421  resetContributors(binobjvarmap, collectedlbvars, contributors, nlbcontributors);
1422 
1423  assert(SCIPisZero(scip, objval));
1424  nlbcontributors = 0;
1425  }
1426 
1427  /* get contribution of variable by fixing it to its upper bound w.r.t. minimum activity of the objective function */
1428  SCIP_CALL( collectMinactObjchg(scip, var, SCIP_BOUNDTYPE_UPPER, binobjvarmap, collectedubvars, nbinobjvars,
1429  &contributors[nlbcontributors], uselesscliques, &nubcontributors, &ubobjchg) );
1430  assert(!SCIPisNegative(scip, ubobjchg));
1431 
1432  SCIPdebugMsg(scip, "variable <%s> fixed to bound=%d implies %d(%d)\n", SCIPvarGetName(var),
1433  SCIP_BOUNDTYPE_UPPER, 0, nubcontributors);
1434 
1435  /* ignore implications if the variable has a zero objective coefficient and implications only one variable, since
1436  * this is covered by that implied variable
1437  */
1438  if( !(*collect) && nubcontributors == 1 )
1439  {
1440  /* reset upper bound contributors */
1441  resetContributors(binobjvarmap, collectedubvars, &contributors[nlbcontributors], nubcontributors);
1442 
1443  assert(SCIPisZero(scip, objval));
1444  nubcontributors = 0;
1445  }
1446 
1447  if( (*collect) || nlbcontributors > 1 || nubcontributors > 1 )
1448  {
1449  /* creates an objective implication data structure, fixes (globally) variables which are implied by lower and upper
1450  * bound fixing, and clears the collected arrays for lower and upper bound
1451  */
1452  SCIP_CALL( objimplicsCreate(scip, objimplics, contributors, binobjvarmap, collectedlbvars, collectedubvars, lbobjchg, ubobjchg, nlbcontributors, nubcontributors) );
1453  (*collect) = TRUE;
1454  }
1455  else
1456  {
1457  /* reset lower bound contributors */
1458  resetContributors(binobjvarmap, collectedlbvars, contributors, nlbcontributors);
1459 
1460  /* reset upper bound contributors */
1461  resetContributors(binobjvarmap, collectedubvars, &contributors[nlbcontributors], nubcontributors);
1462  }
1463  }
1464  else if( (*collect) )
1465  {
1468  assert(!SCIPisZero(scip, lbobjchg) || !SCIPisZero(scip, ubobjchg));
1469  assert(!SCIPisNegative(scip, lbobjchg));
1470  assert(!SCIPisNegative(scip, ubobjchg));
1471 
1472  /* creates an "empty" objective implication data structure */
1473  SCIP_CALL( objimplicsCreate(scip, objimplics, NULL, NULL, NULL, NULL, lbobjchg, ubobjchg, 0, 0) );
1474  }
1475 
1476  return SCIP_OKAY;
1477 }
1478 
1479 /** check if the given variable should be collected for the maximum activity propagation */
1480 static
1482  SCIP* scip, /**< SCIP data structure */
1483  SCIP_VAR* var, /**< variable to check */
1484  SCIP_Bool useimplics, /**< should implications be used */
1485  SCIP_Real* objchg, /**< pointer to store the objective change w.r.t. maximum activity */
1486  SCIP_Bool* isnotzero /**< pointer to store if the objective change is unequal to zero or not */
1487  )
1488 {
1489  SCIP_Real lbobjchg;
1490  SCIP_Real ubobjchg;
1491 
1492  assert(scip != NULL);
1493  assert(SCIPvarIsBinary(var));
1494  assert(objchg != NULL);
1495  assert(isnotzero != NULL);
1496 
1497  /* get contribution of variable by fixing it to its lower bound w.r.t. maximum activity of the objective function */
1498  SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_LOWER, useimplics, &lbobjchg) );
1499  assert(!SCIPisPositive(scip, lbobjchg));
1500 
1501  /* get contribution of variable by fixing it to its upper bound w.r.t. maximum activity of the objective function */
1502  SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_UPPER, useimplics, &ubobjchg) );
1503  assert(!SCIPisPositive(scip, ubobjchg));
1504 
1505  (*objchg) = MIN(lbobjchg, ubobjchg);
1506 
1507  /* only consider variables with non-zero objective contribution */
1508  if( SCIPisZero(scip, (*objchg)) )
1509  *isnotzero = FALSE;
1510  else
1511  *isnotzero = TRUE;
1512 
1513  return SCIP_OKAY;
1514 }
1515 
1516 /** initializate the propagator */
1517 static
1519  SCIP* scip, /**< SCIP data structure */
1520  SCIP_PROPDATA* propdata /**< propagator data */
1521  )
1522 {
1523  SCIP_VAR** vars;
1524  SCIP_VAR* var;
1525  SCIP_HASHMAP* binobjvarmap;
1526  int nvars;
1527  int nbinvars;
1528  int nintvars;
1529  int nminactvars;
1530  int nmaxactvars;
1531  int nobjintvars;
1532  int nobjcontvars;
1533  int nobjvars;
1534  int nbinobjvars;
1535  int v;
1536 
1537  assert(scip != NULL);
1538  assert(propdata != NULL);
1539 
1540  /* get problem variables */
1541  vars = SCIPgetVars(scip);
1542  nvars = SCIPgetNVars(scip);
1543  nintvars = nvars - SCIPgetNContVars(scip);
1544 
1545  nbinvars = 0;
1546  nobjvars = 0;
1547  nbinobjvars = 0;
1548 
1549  SCIP_CALL( SCIPhashmapCreate(&binobjvarmap, SCIPblkmem(scip), SCIPgetNObjVars(scip)) );
1550 
1551  /* count and collect variable problem indices of variables with non-zero objective coefficient */
1552  for( v = 0; v < nvars; ++v )
1553  {
1554  var = vars[v];
1555  assert(var != NULL);
1556 
1557  if( !SCIPisZero(scip, SCIPvarGetObj(var)) )
1558  {
1559  nobjvars++;
1560 
1561  if( SCIPvarIsBinary(var) )
1562  {
1563  SCIP_CALL( SCIPhashmapInsertInt(binobjvarmap, (void*)var, nbinobjvars + 1) );
1564  nbinobjvars++;
1565  }
1566  }
1567 
1568  if( SCIPvarIsBinary(var) )
1569  nbinvars++;
1570  }
1571 
1572  nminactvars = 0;
1573  nmaxactvars = 0;
1574  nobjintvars = 0;
1575  nobjcontvars = 0;
1576 
1577  if( nobjvars > 0 )
1578  {
1579  SCIP_EVENTHDLR* eventhdlr;
1580  SCIP_OBJIMPLICS* objimplics;
1581  SCIP_HASHTABLE* uselesscliques;
1582  SCIP_VAR** contributors;
1583  SCIP_Bool* collectedlbvars;
1584  SCIP_Bool* collectedubvars;
1585  SCIP_Bool collect;
1586  SCIP_Bool useimplics;
1587  SCIP_Real objval;
1588  SCIP_Real objchg;
1589 
1590  eventhdlr = propdata->eventhdlr;
1591  assert(eventhdlr != NULL);
1592 
1593  useimplics = (propdata->propuseimplics && nbinobjvars < propdata->maximplvars);
1594 
1595  /* allocate memory for all arrays */
1596  propdata->minactsize = nbinvars;
1597  propdata->maxactsize = nbinvars;
1598  propdata->objintvarssize = nobjvars - nbinobjvars;
1599  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->minactvars, propdata->minactsize) );
1600  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->minactimpls, propdata->minactsize) );
1601  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->maxactvars, propdata->maxactsize) );
1602  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->maxactchgs, propdata->maxactsize) );
1603  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->objintvars, propdata->objintvarssize) );
1604 
1605  if( useimplics )
1606  {
1607  int ncliques;
1608 
1609  /* create temporary buffer */
1610  /* we store both lb and ub contributors in array contributors, and both could be nbinobjvars, we need twice that size */
1611  SCIP_CALL( SCIPallocBufferArray(scip, &contributors, 2 * nbinobjvars) );
1612  /* @todo: use SCIPallocCleanBufferArray instead? */
1613  SCIP_CALL( SCIPallocClearBufferArray(scip, &collectedlbvars, nbinobjvars+1) );
1614  /* @todo: use SCIPallocCleanBufferArray instead? */
1615  SCIP_CALL( SCIPallocClearBufferArray(scip, &collectedubvars, nbinobjvars+1) );
1616 
1617  ncliques = SCIPgetNCliques(scip);
1618 
1619  if( ncliques > 0 )
1620  {
1621  SCIP_CALL( SCIPhashtableCreate(&uselesscliques, SCIPblkmem(scip), ncliques,
1622  cliqueGetHashkey, cliqueIsHashkeyEq, cliqueGetHashkeyVal, NULL) );
1623  }
1624  else
1625  uselesscliques = NULL;
1626  }
1627  else
1628  {
1629  contributors = NULL;
1630  collectedlbvars = NULL;
1631  collectedubvars = NULL;
1632  uselesscliques = NULL;
1633  }
1634 
1635  /* collect the variables with non-zero objective contribution and catch global bound tighten events that decrease the
1636  * maximal pseudo objective activity
1637  */
1638  for( v = 0; v < nvars && (nobjintvars == 0 || nobjintvars < propdata->objintvarssize); ++v )
1639  {
1640  var = vars[v];
1641  assert(var != NULL);
1642 
1643  objval = SCIPvarGetObj(var);
1644 
1645  if( SCIPvarIsBinary(var) )
1646  {
1647  /* ignore variables which are globally fixed */
1648  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 )
1649  {
1650 #ifndef NDEBUG
1651  /* check that the binary implications are applied for binary variables which are globally fixed */
1652  checkImplicsApplied(scip, var);
1653 #endif
1654  continue;
1655  }
1656 
1657  /* check if the variable should be collected for the minimum activity propagation */
1658  SCIP_CALL( collectMinactVar(scip, var, &objimplics, useimplics, binobjvarmap, collectedlbvars, collectedubvars,
1659  nbinobjvars, contributors, uselesscliques, &collect) );
1660 
1661  if( collect )
1662  {
1663  assert(nminactvars < nbinvars);
1664  assert(objimplics != NULL);
1665  assert(objimplics->nlbimpls + objimplics->nubimpls <= nbinobjvars);
1666 
1667  /* collect the binary variable with non-zero objective contribution */
1668  propdata->minactvars[nminactvars] = var;
1669  propdata->minactimpls[nminactvars] = objimplics;
1670  nminactvars++;
1671 
1672  /* catch bound relax event for the binary variable to handel the firstnonfixed index correctly */
1673  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDRELAXED, eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) );
1674 
1675  SCIPdebugMsg(scip, "variable <%s>[obj: <%g>] implicit objective change %g\n",
1676  SCIPvarGetName(var), objval, objimplics->maxobjchg);
1677 
1678  /* captures the variable */
1679  SCIP_CALL( SCIPcaptureVar(scip, var) ) ;
1680  }
1681  /* check if the variable should be collected for the maximum activity propagation */
1682  SCIP_CALL( collectMaxactVar(scip, var, useimplics, &objchg, &collect) );
1683 
1684  if( collect )
1685  {
1686  assert(nmaxactvars < nbinvars);
1687 
1688  /* collect the binary variable with non-zero objective contribution */
1689  propdata->maxactvars[nmaxactvars] = var;
1690  propdata->maxactchgs[nmaxactvars] = -objchg;
1691  nmaxactvars++;
1692 
1693  /* catch bound change events if the variable has a non-zero objective coefficient to check if the maximum
1694  * activity of the objective function changed
1695  */
1696  SCIP_CALL( catchObjEvent(scip, propdata, eventhdlr, var) );
1697 
1698  /* captures the variable */
1699  SCIP_CALL( SCIPcaptureVar(scip, var) ) ;
1700  }
1701  }
1702  else
1703  {
1704  /* only consider non-binary variables with a non-zero objective */
1705  if( SCIPisZero(scip, objval) )
1706  continue;
1707 
1708  assert(nobjintvars < propdata->objintvarssize);
1709 
1710  propdata->objintvars[nobjintvars] = var;
1711  nobjintvars++;
1712 
1713  if( v >= nintvars )
1714  nobjcontvars++;
1715 
1716  /* catch bound change events if the variable has a non-zero objective coefficient to check if the maximum
1717  * activity of the objective function changed
1718  */
1719  SCIP_CALL( catchObjEvent(scip, propdata, eventhdlr, var) );
1720 
1721  /* captures the variable */
1722  SCIP_CALL( SCIPcaptureVar(scip, var) );
1723  }
1724  }
1725 
1726  if( useimplics )
1727  {
1728  if( uselesscliques != NULL )
1729  SCIPhashtableFree(&uselesscliques);
1730 
1731  SCIPfreeBufferArray(scip, &collectedubvars);
1732  SCIPfreeBufferArray(scip, &collectedlbvars);
1733  SCIPfreeBufferArray(scip, &contributors);
1734  }
1735 
1736  if( nminactvars == 0 )
1737  {
1738  SCIPfreeBlockMemoryArray(scip, &propdata->minactvars, propdata->minactsize);
1739  SCIPfreeBlockMemoryArray(scip, &propdata->minactimpls, propdata->minactsize);
1740  propdata->minactsize = 0;
1741  propdata->minactvars = NULL;
1742  propdata->minactimpls = NULL;
1743  }
1744  else
1745  {
1746  /* sort binary variables with respect to the absolute value of their maximal potential objective contribution for
1747  * the minimum activity of the objective function
1748  */
1749  SCIPsortDownPtrPtr((void**)propdata->minactimpls, (void**)propdata->minactvars, objimplicsComp, nminactvars);
1750 
1751  SCIPdebugMsg(scip, "%d binary variables with non-zero objective contribution w.r.t. the minimum activity of the objective function\n", nminactvars);
1752  }
1753 
1754  if( nmaxactvars == 0 )
1755  {
1756  SCIPfreeBlockMemoryArray(scip, &propdata->maxactvars, propdata->maxactsize);
1757  SCIPfreeBlockMemoryArray(scip, &propdata->maxactchgs, propdata->maxactsize);
1758  propdata->maxactsize = 0;
1759  propdata->maxactvars = NULL;
1760  propdata->maxactchgs = NULL;
1761  }
1762  else
1763  {
1764  /* sort binary variables with respect to the absolute value of their maximal potential objective contribution for
1765  * the maximum activity of the objective function
1766  */
1767  SCIPsortDownRealPtr(propdata->maxactchgs, (void**)propdata->maxactvars, nmaxactvars);
1768 
1769  SCIPdebugMsg(scip, "%d binary variables with non-zero objective contribution w.r.t. the maximum activity of the objective function\n", nmaxactvars);
1770  }
1771 
1772  if( nobjintvars == 0 )
1773  {
1774  SCIPfreeBlockMemoryArray(scip, &propdata->objintvars, propdata->objintvarssize);
1775  propdata->objintvarssize = 0;
1776  propdata->objintvars = NULL;
1777  }
1778  else
1779  {
1780  /* sort integer variables with respect to the absolute value of their objective coefficient */
1781  SCIPsortDownPtr((void**)propdata->objintvars, varCompObj, nobjintvars - nobjcontvars);
1782 
1783  /* sort continuous variables with respect to the absolute value of their objective coefficient */
1784  SCIPsortDownPtr((void**)(&propdata->objintvars[nobjintvars - nobjcontvars]), varCompObj, nobjcontvars);
1785 
1786  SCIPdebugMsg(scip, "%d integer variables and %d continuous variables with non-zero objective contribution\n",
1787  nobjintvars - nobjcontvars, nobjcontvars);
1788  }
1789  }
1790 
1791  SCIPhashmapFree(&binobjvarmap);
1792 
1793  propdata->nminactvars = nminactvars;
1794  propdata->nmaxactvars = nmaxactvars;
1795  propdata->nobjintvars = nobjintvars;
1796  propdata->maxpseudoobjact = SCIP_INVALID;
1797  propdata->maxpseudoobjactinf = 0;
1798  propdata->lastvarnum = -1;
1799  propdata->glbfirstnonfixed = 0;
1800  propdata->maxactfirstnonfixed = 0;
1801  propdata->firstnonfixed = 0;
1802  propdata->nnewvars = 0;
1803  propdata->cutoffbound = SCIPinfinity(scip);
1804  propdata->lastlowerbound = -SCIPinfinity(scip);
1805  propdata->glbpseudoobjval = -SCIPinfinity(scip);
1806 
1807  propdata->initialized = TRUE;
1808 
1809  /* due to scaling after presolving we need to update the global pseudoactivity and the cutoffbound */
1810  propdata->glbpropagated = FALSE;
1811  propdata->glbpseudoobjval = SCIPgetGlobalPseudoObjval(scip);
1812  propdata->cutoffbound = SCIPgetCutoffbound(scip);
1813  assert(SCIPgetDepth(scip) > 0 || SCIPisFeasEQ(scip, propdata->glbpseudoobjval, SCIPgetPseudoObjval(scip)));
1814 
1815  /* create hash table which is used for resolving bound changes */
1816  if( nminactvars > 0 )
1817  {
1818  SCIP_CALL( SCIPhashtableCreate(&propdata->addedvars, SCIPblkmem(scip), nvars,
1819  SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal, NULL) );
1820  }
1821  else
1822  propdata->addedvars = NULL;
1823 
1824  return SCIP_OKAY;
1825 }
1826 
1827 /** adds for the given non-binary variable a conflict bound depending on its objective contribution */
1828 static
1830  SCIP* scip, /**< SCIP data structure */
1831  SCIP_VAR* var, /**< variable to check for objective contribution */
1832  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1833  SCIP_Real* reqpseudoobjval /**< pointer to store the remaining minimum activity which has to be proven */
1834  )
1836  SCIP_Real objval;
1837 
1838  objval = SCIPvarGetObj(var);
1839  assert(!SCIPisZero(scip, objval));
1840 
1841  if( objval > 0.0 )
1842  {
1843  SCIP_Real loclb;
1844  SCIP_Real glblb;
1845 
1846  glblb = SCIPvarGetLbGlobal(var);
1847  loclb = SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE);
1848  assert(SCIPisFeasGE(scip, loclb, glblb));
1849 
1850  /* check if the local lower bound (at time stamp bdchgidx) is larger than the global lower bound */
1851  if( SCIPisGT(scip, loclb, glblb) )
1852  {
1853  SCIPdebugMsg(scip, " add bound change <%s>[%g] >= <%g>\n", SCIPvarGetName(var), objval, loclb);
1854  SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) );
1855 
1856  /* hard comparison is enough to make requiredpseudoobjval nonincreasing */
1857  assert((loclb - glblb) * objval > 0.0);
1858 
1859  (*reqpseudoobjval) -= (loclb - glblb) * objval;
1860  }
1861  }
1862  else
1863  {
1864  SCIP_Real locub;
1865  SCIP_Real glbub;
1866 
1867  glbub = SCIPvarGetUbGlobal(var);
1868  locub = SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE);
1869  assert(SCIPisFeasLE(scip, locub, glbub));
1870 
1871  /* check if the local upper bound (at time stamp bdchgidx) is smaller than the global upper bound */
1872  if( SCIPisLT(scip, locub, glbub) )
1873  {
1874  SCIPdebugMsg(scip, " add bound change <%s>[%g] <= <%g>\n", SCIPvarGetName(var), objval, locub);
1875  SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) );
1876 
1877  /* hard comparison is enough to make requiredpseudoobjval nonincreasing */
1878  assert((locub - glbub) * objval > 0.0);
1879 
1880  (*reqpseudoobjval) -= (locub - glbub) * objval;
1881  }
1882  }
1883 
1884  return SCIP_OKAY;
1885 }
1886 
1887 /** check for the given implication variables if they also contribute to the required minimum activity */
1888 static
1890  SCIP* scip, /**< SCIP data structure */
1891  SCIP_VAR** vars, /**< variable to check for objective contribution */
1892  int start, /**< start index */
1893  int end, /**< end index */
1894  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1895  SCIP_HASHTABLE* addedvars, /**< hash table containing variables which are already added directly or implicitly due to implications */
1896  SCIP_Real* reqpseudoobjval, /**< pointer to store the remaining minimum activity which has to be proven */
1897  SCIP_Bool* foundimplics /**< pointer to store if an implication is found */
1898  )
1899 {
1900  SCIP_VAR* var;
1901  SCIP_Real lb;
1902  SCIP_Real ub;
1903  int v;
1904 
1905  assert(foundimplics != NULL);
1906  assert(*foundimplics == FALSE);
1907 
1908  for( v = start; v < end; ++v )
1909  {
1910  var = vars[v];
1911  assert(var != NULL);
1912  assert(SCIPvarIsBinary(var));
1913 
1914  /* we need to take the bounds after the bdchgidx here, since the variable of the bound change may be the implied one;
1915  * we already counted its contribution before, so we want to see it as fixed here, which it is after the bound change.
1916  */
1917  lb = SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE);
1918  ub = SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE);
1919 
1920  if( lb < 0.5 && ub > 0.5 && !SCIPhashtableExists(addedvars, (void*)var) )
1921  {
1922  (*reqpseudoobjval) -= REALABS(SCIPvarGetObj(var));
1923  SCIPdebugMsg(scip, " implicated variables <%s>[%g] bdchgidx [%g,%g] -> remaining <%g>\n", SCIPvarGetName(var), SCIPvarGetObj(var), lb, ub, *reqpseudoobjval);
1924 
1925  SCIP_CALL( SCIPhashtableInsert(addedvars, (void*)var) );
1926  assert(SCIPhashtableExists(addedvars, (void*)var));
1927  (*foundimplics) = TRUE;
1928  }
1929  }
1930 
1931  return SCIP_OKAY;
1932 }
1933 
1934 /** adds for the given binary variable a conflict bound depending on its objective contribution */
1935 static
1937  SCIP* scip, /**< SCIP data structure */
1938  SCIP_VAR* var, /**< variable to check for objective contribution */
1939  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1940  SCIP_OBJIMPLICS* objimplics, /**< objective implication data for the given variable */
1941  SCIP_HASHTABLE* addedvars, /**< hash table containing variables which are already add directly or implicitly due to implications */
1942  SCIP_Bool respropuseimplics, /**< should implications be used */
1943  SCIP_Real* reqpseudoobjval /**< pointer to store the remaining minimum activity which has to be proven */
1944  )
1945 {
1946  SCIP_Real objval;
1947  SCIP_Real lb;
1948  SCIP_Real ub;
1949  SCIP_Bool foundimplics;
1950 
1951  assert(SCIPvarIsBinary(var));
1952 
1953  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 )
1954  return SCIP_OKAY;
1955 
1956  lb = SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE);
1957  ub = SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE);
1958 
1959  objval = SCIPvarGetObj(var);
1960  foundimplics = FALSE;
1961 
1962  /* only consider variables which are fixed */
1963  if( lb > 0.5 )
1964  {
1965  if( respropuseimplics )
1966  {
1967  assert(objimplics != NULL);
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  assert(objimplics != NULL);
1994  SCIP_CALL( getConflictImplics(scip, objimplics->objvars, 0, objimplics->nlbimpls,
1995  bdchgidx, addedvars, reqpseudoobjval, &foundimplics) );
1996  }
1997 
1998  /* check if the binary variable has a positive contribution (negative objective coefficient since it is fixed to
1999  * zero) or is needed due a positive contribution of an implied variable
2000  */
2001  if( foundimplics || SCIPisNegative(scip, objval) )
2002  {
2003  SCIPdebugMsg(scip, " add bound change <%s>[%g] <= <%g> bdchgidx=[%g,%g]\n", SCIPvarGetName(var), objval, ub, lb, ub);
2004  SCIP_CALL( SCIPaddConflictUb(scip, var, NULL) );
2005 
2006  (*reqpseudoobjval) += MIN(0.0, objval);
2007 
2008  if( addedvars != NULL )
2009  {
2010  assert(!SCIPhashtableExists(addedvars, (void*)var));
2011  SCIP_CALL( SCIPhashtableInsert(addedvars, (void*)var) );
2012  }
2013  }
2014  }
2015 
2016  return SCIP_OKAY;
2017 }
2018 
2019 
2020 /** resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the
2021  * cutoff bound
2022  */
2023 static
2025  SCIP* scip, /**< SCIP data structure */
2026  SCIP_PROPDATA* propdata, /**< propagator data */
2027  SCIP_VAR* var, /**< variable that was deduced */
2028  int inferinfo, /**< inference information */
2029  SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */
2030  SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
2031  SCIP_HASHTABLE* addedvars, /**< hash table which contains variables which are already added or implicitly given as reason for the resolve, or NULL */
2032  SCIP_Real* cutoffbound /**< pointer to store the adjusted cutoff bound */
2033  )
2034 {
2035  if( inferinfo != -1 )
2036  {
2037  SCIP_OBJIMPLICS* objimplics;
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 
2056  if( boundtype == SCIP_BOUNDTYPE_LOWER )
2057  {
2058  start = 0;
2059  end = objimplics->nlbimpls;
2060  }
2061  else
2062  {
2063  start = objimplics->nlbimpls;
2064  end = objimplics->nlbimpls + objimplics->nubimpls;
2065  }
2066 
2067  if( addedvars != NULL )
2068  {
2069  SCIP_Bool foundimplics = FALSE;
2070  SCIP_CALL( getConflictImplics(scip, objimplics->objvars, start, end, bdchgidx, addedvars, cutoffbound, &foundimplics) );
2071  } /*lint !e438*/
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(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(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(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(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( !SCIPallowWeakDualReds(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( !SCIPallowWeakDualReds(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(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_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
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)
SCIP_Real SCIPfeastol(SCIP *scip)
static SCIP_RETCODE getMinactImplicObjchg(SCIP *scip, SCIP_VAR *var, SCIP_OBJIMPLICS *objimplics, SCIP_BDCHGIDX *bdchgidx, SCIP_BOUNDTYPE bound, SCIP_Bool local, SCIP_Real *objchg)
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2166
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3351
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2486
#define PROP_FREQ
SCIP_VAR ** objvars
public methods for SCIP parameter handling
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1996
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisDualfeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition: scip_var.c:8622
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:5876
SCIP_EXPORT int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3250
public methods for memory management
#define PROP_PRIORITY
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
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_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2598
public methods for conflict handler plugins and conflict analysis
static SCIP_RETCODE propdataExit(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPpropagateCutoffboundVar(SCIP *scip, SCIP_PROP *prop, SCIP_VAR *var, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, SCIP_Bool *tightened)
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)
static SCIP_DECL_PROPINITSOL(propInitsolPseudoobj)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1218
#define DEFAULT_MAXNEWVARS
int SCIPgetCutoffdepth(SCIP *scip)
Definition: scip_tree.c:464
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
#define DEFAULT_PROPCUTOFFBOUND
static void updateMaxObjPseudoactivity(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3131
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17192
SCIP_EXPORT SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17957
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
#define SCIP_PROPTIMING_DURINGLPLOOP
Definition: type_timing.h:57
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17510
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:5991
#define DEFAULT_MINUSELESS
static SCIP_DECL_SORTPTRCOMP(objimplicsComp)
SCIP_Real SCIPgetGlobalPseudoObjval(SCIP *scip)
Definition: scip_lp.c:299
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
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)
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:424
#define SCIP_EVENTTYPE_GLBCHANGED
Definition: type_event.h:66
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_EXPORT SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17335
public methods for problem variables
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_EXPORT SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17986
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
SCIP_Real SCIPgetPseudoObjval(SCIP *scip)
Definition: scip_lp.c:324
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
static SCIP_RETCODE propagateCutoffbound(SCIP *scip, SCIP_PROP *prop, SCIP_RESULT *result)
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:790
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
public methods for SCIP variables
#define PROP_DELAY
static void resetContributors(SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedvars, SCIP_VAR **contributors, int ncontributors)
#define DEFAULT_FORCE
static SCIP_Real getMaxObjPseudoactivityResidual(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var)
#define SCIPdebugMsgPrint
Definition: scip_message.h:70
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
#define EVENTHDLR_DESC
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:559
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_EXPORT void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:142
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:2235
public methods for querying solving statistics
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:69
#define PROP_PRESOLTIMING
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3220
public methods for the branch-and-bound tree
static SCIP_RETCODE addConflictBounds(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Real *reqpseudoobjval)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3362
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)
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17012
static SCIP_RETCODE objimplicsDelPos(SCIP *scip, SCIP_OBJIMPLICS *objimplics, int pos)
SCIP_EXPORT SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17203
#define SCIPerrorMessage
Definition: pub_message.h:55
static SCIP_RETCODE propagateCutoffboundBinvar(SCIP *scip, SCIP_PROP *prop, SCIP_VAR *var, int pos, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, SCIP_Bool *tightened, SCIP_Bool *cutoff, SCIP_Bool local)
static SCIP_RETCODE getMaxactImplicObjchg(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE bound, SCIP_Real *objchg)
SCIP_Real maxobjchg
SCIP_EXPORT int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17940
public methods for event handler plugins and event handlers
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:277
int SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2214
SCIP_EXPORT SCIP_BOUNDTYPE SCIPvarGetWorstBoundType(SCIP_VAR *var)
Definition: var.c:17787
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1941
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:100
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)
SCIP_EXPORT void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:932
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
#define MAX_CLIQUELENGTH
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:164
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
static SCIP_DECL_PROPPRESOL(propPresolPseudoobj)
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
#define PROP_DESC
int SCIPgetNCliques(SCIP *scip)
Definition: scip_var.c:7556
#define NULL
Definition: lpi_spx1.cpp:155
#define PROP_PRESOL_MAXROUNDS
#define REALABS(x)
Definition: def.h:187
#define SCIP_EVENTTYPE_UBRELAXED
Definition: type_event.h:71
#define DEFAULT_PROPUSEIMPLICS
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Real cutoffbound, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
static SCIP_RETCODE dropObjEvent(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var)
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:222
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1021
static SCIP_DECL_PROPCOPY(propCopyPseudoobj)
static SCIP_RETCODE objimplicsFree(SCIP *scip, SCIP_OBJIMPLICS **objimplics)
Definition: grphload.c:88
SCIP_Bool SCIPisDualfeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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:111
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_Real SCIPinfinity(SCIP *scip)
public data structures and miscellaneous methods
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2285
static SCIP_DECL_PROPEXITSOL(propExitsolPseudoobj)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:391
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)
static SCIP_Real getMaxObjPseudoactivityResidualValue(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Real contrib)
#define DEFAULT_PROPFULLINROOT
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3013
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)
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17672
static SCIP_RETCODE propagateCutoffboundBinvars(SCIP *scip, SCIP_PROP *prop, SCIP_Real cutoffbound, SCIP_Real pseudoobjval, int *nfixedvars, SCIP_Bool *cutoff)
SCIP_EXPORT SCIP_BOUNDTYPE SCIPvarGetBestBoundType(SCIP_VAR *var)
Definition: var.c:17774
#define MAX(x, y)
Definition: tclique_def.h:83
static SCIP_Real getVarObjchg(SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BOUNDTYPE bound)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3363
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
static SCIP_DECL_HASHKEYEQ(cliqueIsHashkeyEq)
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:339
SCIP_EXPORT SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18025
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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)
static void checkImplicsApplied(SCIP *scip, SCIP_VAR *var)
static SCIP_RETCODE catchObjEvent(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var)
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17718
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
public methods for the LP relaxation, rows and columns
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2132
public methods for variable pricer plugins
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:303
#define DEFAULT_RESPROPUSEIMPLICS
SCIP_EXPORT int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3193
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17728
methods for sorting joint arrays of various types
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:780
static SCIP_Real collectMinactImplicVar(SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *binobjvarmap, SCIP_Bool *collectedvars, int nbinobjvars, SCIP_VAR **contributors, int *ncontributors)
public methods for managing events
general public methods
#define DEFAULT_MAXVARSFRAC
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define PROP_PRESOL_PRIORITY
#define EVENTHDLR_NAME
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:311
void SCIPhashtableRemoveAll(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2694
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17662
public methods for the probing mode
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message output
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3047
static SCIP_DECL_HASHKEYVAL(cliqueGetHashkeyVal)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1252
#define SCIP_Real
Definition: def.h:163
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:43
static void propdataReset(SCIP_PROPDATA *propdata)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:270
static SCIP_DECL_HASHGETKEY(cliqueGetHashkey)
#define SCIP_INVALID
Definition: def.h:183
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 SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6329
SCIP_EXPORT SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17972
unsigned int SCIPcliqueGetId(SCIP_CLIQUE *clique)
Definition: implics.c:3373
public methods for propagator plugins
SCIP_EXPORT SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:11244
#define PROP_NAME
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:345
static SCIP_DECL_EVENTEXEC(eventExecPseudoobj)
SCIP_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17355
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:98
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3341
SCIP_RETCODE SCIPincludePropPseudoobj(SCIP *scip)
static SCIP_RETCODE dropVarEvents(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_EXPORT void SCIPsortDownPtrPtr(void **ptrarray1, void **ptrarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:122
SCIP_EXPORT int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18014
#define SCIP_EVENTTYPE_GUBCHANGED
Definition: type_event.h:67
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:105
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip_prop.c:206
public methods for global and local (sub)problems
static SCIP_DECL_PROPEXEC(propExecPseudoobj)
#define SCIP_EVENTTYPE_VARADDED
Definition: type_event.h:61
#define DEFAULT_MAXIMPLVARS
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 SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:6209
public methods for propagators
SCIP_EXPORT int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11708
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:142
#define PROP_TIMING
static void checkGlbfirstnonfixed(SCIP_PROPDATA *propdata)
#define SCIP_EVENTTYPE_BOUNDRELAXED
Definition: type_event.h:115
memory allocation routines