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