Scippy

SCIP

Solving Constraint Integer Programs

prop_obbt.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop_obbt.c
17  * @ingroup DEFPLUGINS_PROP
18  * @brief optimization-based bound tightening propagator
19  * @author Stefan Weltge
20  * @author Benjamin Mueller
21  */
22 
23 /**@todo if bound tightenings of other propagators are the reason for lpsolstat != SCIP_LPSOLSTAT_OPTIMAL, resolve LP */
24 /**@todo only run more than once in root node if primal bound improved or many cuts were added to the LP */
25 /**@todo filter bounds of a variable already if SCIPisLbBetter()/SCIPisUbBetter() would return FALSE */
26 /**@todo improve warmstarting of LP solving */
27 /**@todo include bound value (finite/infinite) into getScore() function */
28 /**@todo use unbounded ray in filtering */
29 /**@todo do we want to run if the LP is unbounded, maybe for infinite variable bounds? */
30 /**@todo add first filter round in direction of objective function */
31 /**@todo implement conflict resolving callback by calling public method of genvbounds propagator, since the reason are
32  * exactly the variable bounds with nonnegative reduced costs stored in the right-hand side of the generated
33  * generalized variable bound (however, this only makes sense if we run locally)
34  */
35 
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 
38 #include <assert.h>
39 #include <string.h>
40 
41 #include "scip/cons_linear.h"
42 #include "scip/cons_nonlinear.h"
43 #include "scip/nlhdlr_bilinear.h"
44 #include "scip/prop_genvbounds.h"
45 #include "scip/prop_obbt.h"
46 #include "scip/pub_cons.h"
47 #include "scip/pub_lp.h"
48 #include "scip/pub_message.h"
49 #include "scip/pub_misc.h"
50 #include "scip/pub_misc_sort.h"
51 #include "scip/pub_nlp.h"
52 #include "scip/pub_prop.h"
53 #include "scip/pub_tree.h"
54 #include "scip/pub_var.h"
55 #include "scip/scip_cons.h"
56 #include "scip/scip_copy.h"
57 #include "scip/scip_cut.h"
58 #include "scip/scip_general.h"
59 #include "scip/scip_lp.h"
60 #include "scip/scip_mem.h"
61 #include "scip/scip_message.h"
62 #include "scip/scip_nlp.h"
63 #include "scip/scip_numerics.h"
64 #include "scip/scip_param.h"
65 #include "scip/scip_prob.h"
66 #include "scip/scip_probing.h"
67 #include "scip/scip_prop.h"
68 #include "scip/scip_randnumgen.h"
69 #include "scip/scip_solvingstats.h"
70 #include "scip/scip_tree.h"
71 #include "scip/scip_var.h"
72 
73 #define PROP_NAME "obbt"
74 #define PROP_DESC "optimization-based bound tightening propagator"
75 #define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP
76 #define PROP_PRIORITY -1000000 /**< propagator priority */
77 #define PROP_FREQ 0 /**< propagator frequency */
78 #define PROP_DELAY TRUE /**< should propagation method be delayed, if other propagators
79  * found reductions? */
80 
81 #define DEFAULT_CREATE_GENVBOUNDS TRUE /**< should obbt try to provide genvbounds if possible? */
82 #define DEFAULT_FILTERING_NORM TRUE /**< should coefficients in filtering be normalized w.r.t. the
83  * domains sizes? */
84 #define DEFAULT_APPLY_FILTERROUNDS FALSE /**< try to filter bounds in so-called filter rounds by solving
85  * auxiliary LPs? */
86 #define DEFAULT_APPLY_TRIVIALFITLERING TRUE /**< should obbt try to use the LP solution to filter some bounds? */
87 #define DEFAULT_GENVBDSDURINGFILTER TRUE /**< try to genrate genvbounds during trivial and aggressive filtering? */
88 #define DEFAULT_DUALFEASTOL 1e-9 /**< feasibility tolerance for reduced costs used in obbt; this value
89  * is used if SCIP's dual feastol is greater */
90 #define DEFAULT_CONDITIONLIMIT -1.0 /**< maximum condition limit used in LP solver (-1.0: no limit) */
91 #define DEFAULT_BOUNDSTREPS 0.001 /**< minimal relative improve for strengthening bounds */
92 #define DEFAULT_FILTERING_MIN 2 /**< minimal number of filtered bounds to apply another filter
93  * round */
94 #define DEFAULT_ITLIMITFACTOR 10.0 /**< multiple of root node LP iterations used as total LP iteration
95  * limit for obbt (<= 0: no limit ) */
96 #define DEFAULT_MINITLIMIT 5000L /**< minimum LP iteration limit */
97 #define DEFAULT_ONLYNONCONVEXVARS TRUE /**< only apply obbt on non-convex variables */
98 #define DEFAULT_TIGHTINTBOUNDSPROBING TRUE /**< should bounds of integral variables be tightened during
99  * the probing mode? */
100 #define DEFAULT_TIGHTCONTBOUNDSPROBING FALSE /**< should bounds of continuous variables be tightened during
101  * the probing mode? */
102 #define DEFAULT_ORDERINGALGO 1 /**< which type of ordering algorithm should we use?
103  * (0: no, 1: greedy, 2: greedy reverse) */
104 #define OBBT_SCOREBASE 5 /**< base that is used to calculate a bounds score value */
105 #define GENVBOUND_PROP_NAME "genvbounds"
106 
107 #define DEFAULT_SEPARATESOL FALSE /**< should the obbt LP solution be separated? note that that by
108  * separating solution OBBT will apply all bound tightenings
109  * immediatly */
110 #define DEFAULT_SEPAMINITER 0 /**< minimum number of iteration spend to separate an obbt LP solution */
111 #define DEFAULT_SEPAMAXITER 10 /**< maximum number of iteration spend to separate an obbt LP solution */
112 #define DEFAULT_GENVBDSDURINGSEPA TRUE /**< try to create genvbounds during separation process? */
113 #define DEFAULT_PROPAGATEFREQ 0 /**< trigger a propagation round after that many bound tightenings
114  * (0: no propagation) */
115 #define DEFAULT_CREATE_BILININEQS TRUE /**< solve auxiliary LPs in order to find valid inequalities for bilinear terms? */
116 #define DEFAULT_CREATE_LINCONS FALSE /**< create linear constraints from inequalities for bilinear terms? */
117 #define DEFAULT_ITLIMITFAC_BILININEQS 3.0 /**< multiple of OBBT LP limit used as total LP iteration limit for solving bilinear inequality LPs (< 0 for no limit) */
118 #define DEFAULT_MINNONCONVEXITY 1e-1 /**< minimum nonconvexity for choosing a bilinear term */
119 #define DEFAULT_RANDSEED 149 /**< initial random seed */
120 
121 /*
122  * Data structures
123  */
125 /** bound data */
126 struct Bound
127 {
128  SCIP_VAR* var; /**< variable */
129  SCIP_Real newval; /**< stores a probably tighter value for this bound */
130  SCIP_BOUNDTYPE boundtype; /**< type of bound */
131  unsigned int score; /**< score value that is used to group bounds */
132  unsigned int filtered:1; /**< thrown out during pre-filtering step */
133  unsigned int found:1; /**< stores whether a probably tighter value for this bound was found */
134  unsigned int done:1; /**< has this bound been processed already? */
135  unsigned int nonconvex:1; /**< is this bound affecting a nonconvex term? */
136  int index; /**< unique index */
137 };
138 typedef struct Bound BOUND;
139 
140 /* all possible corners of a rectangular domain */
141 enum Corner
142 {
145  RIGHTTOP = 4,
146  LEFTTOP = 8,
147  FILTERED = 15
148 };
149 typedef enum Corner CORNER;
151 /** bilinear bound data */
152 struct BilinBound
153 {
154  SCIP_EXPR* expr; /**< product expression */
155  int filtered; /**< corners that could be thrown out during pre-filtering step */
156  unsigned int done:1; /**< has this bilinear term been processed already? */
157  SCIP_Real score; /**< score value that is used to group bilinear term bounds */
158 };
159 typedef struct BilinBound BILINBOUND;
160 
161 /** propagator data */
162 struct SCIP_PropData
163 {
164  BOUND** bounds; /**< array of interesting bounds */
165  BILINBOUND** bilinbounds; /**< array of interesting bilinear bounds */
166  SCIP_ROW* cutoffrow; /**< pointer to current objective cutoff row */
167  SCIP_PROP* genvboundprop; /**< pointer to genvbound propagator */
168  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
169  SCIP_Longint lastnode; /**< number of last node where obbt was performed */
170  SCIP_Longint npropagatedomreds; /**< number of domain reductions found during propagation */
171  SCIP_Longint nprobingiterations; /**< number of LP iterations during the probing mode */
172  SCIP_Longint nfilterlpiters; /**< number of LP iterations spend for filtering */
173  SCIP_Longint minitlimit; /**< minimum LP iteration limit */
174  SCIP_Longint itlimitbilin; /**< total LP iterations limit for solving bilinear inequality LPs */
175  SCIP_Longint itusedbilin; /**< total LP iterations used for solving bilinear inequality LPs */
176  SCIP_Real dualfeastol; /**< feasibility tolerance for reduced costs used in obbt; this value is
177  * used if SCIP's dual feastol is greater */
178  SCIP_Real conditionlimit; /**< maximum condition limit used in LP solver (-1.0: no limit) */
179  SCIP_Real boundstreps; /**< minimal relative improve for strengthening bounds */
180  SCIP_Real itlimitfactor; /**< LP iteration limit for obbt will be this factor times total LP
181  * iterations in root node */
182  SCIP_Real itlimitfactorbilin; /**< multiple of OBBT LP limit used as total LP iteration limit for solving bilinear inequality LPs (< 0 for no limit) */
183  SCIP_Real minnonconvexity; /**< lower bound on minimum absolute value of nonconvex eigenvalues for a bilinear term */
184  SCIP_Bool applyfilterrounds; /**< apply filter rounds? */
185  SCIP_Bool applytrivialfilter; /**< should obbt try to use the LP solution to filter some bounds? */
186  SCIP_Bool genvbdsduringfilter;/**< should we try to generate genvbounds during trivial and aggressive
187  * filtering? */
188  SCIP_Bool genvbdsduringsepa; /**< try to create genvbounds during separation process? */
189  SCIP_Bool creategenvbounds; /**< should obbt try to provide genvbounds if possible? */
190  SCIP_Bool normalize; /**< should coefficients in filtering be normalized w.r.t. the domains
191  * sizes? */
192  SCIP_Bool onlynonconvexvars; /**< only apply obbt on non-convex variables */
193  SCIP_Bool tightintboundsprobing; /**< should bounds of integral variables be tightened during
194  * the probing mode? */
195  SCIP_Bool tightcontboundsprobing;/**< should bounds of continuous variables be tightened during
196  * the probing mode? */
197  SCIP_Bool separatesol; /**< should the obbt LP solution be separated? note that that by
198  * separating solution OBBT will apply all bound tightenings
199  * immediatly */
200  SCIP_Bool createbilinineqs; /**< solve auxiliary LPs in order to find valid inequalities for bilinear terms? */
201  SCIP_Bool createlincons; /**< create linear constraints from inequalities for bilinear terms? */
202  int orderingalgo; /**< which type of ordering algorithm should we use?
203  * (0: no, 1: greedy, 2: greedy reverse) */
204  int nbounds; /**< length of interesting bounds array */
205  int nbilinbounds; /**< length of interesting bilinear bounds array */
206  int bilinboundssize; /**< size of bilinear bounds array */
207  int boundssize; /**< size of bounds array */
208  int nminfilter; /**< minimal number of filtered bounds to apply another filter round */
209  int nfiltered; /**< number of filtered bounds by solving auxiliary variables */
210  int ntrivialfiltered; /**< number of filtered bounds because the LP value was equal to the bound */
211  int nsolvedbounds; /**< number of solved bounds during the loop in applyObbt() */
212  int ngenvboundsprobing; /**< number of non-trivial genvbounds generated and added during obbt */
213  int ngenvboundsaggrfil; /**< number of non-trivial genvbounds found during aggressive filtering */
214  int ngenvboundstrivfil; /**< number of non-trivial genvbounds found during trivial filtering */
215  int lastidx; /**< index to store the last undone and unfiltered bound */
216  int lastbilinidx; /**< index to store the last undone and unfiltered bilinear bound */
217  int sepaminiter; /**< minimum number of iteration spend to separate an obbt LP solution */
218  int sepamaxiter; /**< maximum number of iteration spend to separate an obbt LP solution */
219  int propagatefreq; /**< trigger a propagation round after that many bound tightenings
220  * (0: no propagation) */
221  int propagatecounter; /**< number of bound tightenings since the last propagation round */
222 };
223 
224 
225 /*
226  * Local methods
227  */
228 
229 /** solves the LP and handles errors */
230 static
232  SCIP* scip, /**< SCIP data structure */
233  int itlimit, /**< maximal number of LP iterations to perform, or -1 for no limit */
234  SCIP_Bool* error, /**< pointer to store whether an unresolved LP error occurred */
235  SCIP_Bool* optimal /**< was the LP solved to optimalilty? */
236  )
237 {
238  SCIP_LPSOLSTAT lpsolstat;
239  SCIP_RETCODE retcode;
240 
241  assert(scip != NULL);
242  assert(itlimit == -1 || itlimit >= 0);
243  assert(error != NULL);
244  assert(optimal != NULL);
245 
246  *optimal = FALSE;
247  *error = FALSE;
248 
249  retcode = SCIPsolveProbingLP(scip, itlimit, error, NULL);
250 
251  lpsolstat = SCIPgetLPSolstat(scip);
252 
253  /* an error should not kill the overall solving process */
254  if( retcode != SCIP_OKAY )
255  {
256  SCIPwarningMessage(scip, " error while solving LP in obbt propagator; LP solve terminated with code <%d>\n", retcode);
257  SCIPwarningMessage(scip, " this does not affect the remaining solution procedure --> continue\n");
258 
259  *error = TRUE;
260 
261  return SCIP_OKAY;
262  }
263 
264  if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
265  {
266  assert(!*error);
267  *optimal = TRUE;
268  }
269 #ifdef SCIP_DEBUG
270  else
271  {
272  switch( lpsolstat )
273  {
275  SCIPdebugMsg(scip, " reached lp iteration limit\n");
276  break;
278  SCIPdebugMsg(scip, " reached time limit while solving lp\n");
279  break;
281  SCIPdebugMsg(scip, " lp was unbounded\n");
282  break;
284  SCIPdebugMsg(scip, " lp was not solved\n");
285  break;
287  SCIPdebugMsg(scip, " an error occured during solving lp\n");
288  break;
291  case SCIP_LPSOLSTAT_OPTIMAL: /* should not appear because it is handled earlier */
292  default:
293  SCIPdebugMsg(scip, " received an unexpected solstat during solving lp: %d\n", lpsolstat);
294  }
295  }
296 #endif
297 
298  return SCIP_OKAY;
299 }
300 
301 /** adds the objective cutoff to the LP; must be in probing mode */
302 static
304  SCIP* scip, /**< SCIP data structure */
305  SCIP_PROPDATA* propdata /**< data of the obbt propagator */
306  )
307 {
308  SCIP_ROW* row;
309  SCIP_VAR** vars;
310  char rowname[SCIP_MAXSTRLEN];
311 
312  int nvars;
313  int i;
314 
315  assert(scip != NULL);
316  assert(SCIPinProbing(scip));
317  assert(propdata != NULL);
318  assert(propdata->cutoffrow == NULL);
319 
320  if( SCIPisInfinity(scip, SCIPgetCutoffbound(scip)) )
321  {
322  SCIPdebugMsg(scip, "no objective cutoff since there is no cutoff bound\n");
323  return SCIP_OKAY;
324  }
325 
326  SCIPdebugMsg(scip, "create objective cutoff and add it to the LP\n");
327 
328  /* get variables data */
329  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
330 
331  /* create objective cutoff row; set local flag to FALSE since primal cutoff is globally valid */
332  (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "obbt_objcutoff");
333  SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, rowname, -SCIPinfinity(scip), SCIPgetCutoffbound(scip), FALSE, FALSE, FALSE) );
334  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
335 
336  for( i = 0; i < nvars; i++ )
337  {
338  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i], SCIPvarGetObj(vars[i])) );
339  }
340  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
341 
342  /* add row to the LP */
343  SCIP_CALL( SCIPaddRowProbing(scip, row) );
344 
345  propdata->cutoffrow = row;
346  assert(SCIProwIsInLP(propdata->cutoffrow));
347 
348  return SCIP_OKAY;
349 }
350 
351 /** determines, whether a variable is already locally fixed */
352 static
354  SCIP* scip, /**< SCIP data structure */
355  SCIP_VAR* var /**< variable to check */
356  )
357 {
358  return SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
359 }
360 
361 /** sets objective to minimize or maximize a single variable */
362 static
364  SCIP* scip,
365  SCIP_PROPDATA* propdata,
366  BOUND* bound,
367  SCIP_Real coef
368  )
369 {
370 #ifdef SCIP_DEBUG
371  SCIP_VAR** vars;
372  int nvars;
373  int counter;
374  int i;
375 #endif
376 
377  assert( scip != NULL );
378  assert( propdata != NULL );
379  assert( bound != NULL );
380 
381  /* set the objective for bound->var */
382  if( bound->boundtype == SCIP_BOUNDTYPE_LOWER )
383  {
384  SCIP_CALL( SCIPchgVarObjProbing(scip, bound->var, coef) );
385  }
386  else
387  {
388  SCIP_CALL( SCIPchgVarObjProbing(scip, bound->var, -coef) );
389  }
390 
391 #ifdef SCIP_DEBUG
392  vars = SCIPgetVars(scip);
393  nvars = SCIPgetNVars(scip);
394  counter = 0;
395 
396  for( i = 0; i < nvars; ++i )
397  {
398  if( SCIPgetVarObjProbing(scip, vars[i]) != 0.0 )
399  ++counter;
400  }
401 
402  assert((counter == 0 && coef == 0.0) || (counter == 1 && coef != 0.0));
403 #endif
404 
405  return SCIP_OKAY;
406 }
407 
408 /** determines whether variable should be included in the right-hand side of the generalized variable bound */
409 static
411  SCIP* scip, /**< SCIP data structure */
412  SCIP_VAR* var /**< variable to check */
413  )
414 {
415  SCIP_Real redcost;
416 
417  assert(scip != NULL);
418  assert(var != NULL);
419 
421  return FALSE;
423  redcost = SCIPgetVarRedcost(scip, var);
424  assert(redcost != SCIP_INVALID); /*lint !e777 */
425 
426  if( redcost == SCIP_INVALID ) /*lint !e777 */
427  return FALSE;
428 
429  if( redcost < SCIPdualfeastol(scip) && redcost > -SCIPdualfeastol(scip) )
430  return FALSE;
431 
432  return TRUE;
433 }
434 
435 /** returns number of LP iterations left (-1: no limit ) */
436 static
438  SCIP* scip, /**< SCIP data structure */
439  SCIP_Longint nolditerations, /**< iterations count at the beginning of the corresponding function */
440  SCIP_Longint itlimit /**< LP iteration limit (-1: no limit) */
441  )
442 {
443  SCIP_Longint itsleft;
444 
445  assert(scip != NULL);
446  assert(nolditerations >= 0);
447  assert(itlimit == -1 || itlimit >= 0);
448 
449  if( itlimit == -1 )
450  {
451  SCIPdebugMsg(scip, "iterations left: unlimited\n");
452  return -1;
453  }
454  else
455  {
456  itsleft = itlimit - ( SCIPgetNLPIterations(scip) - nolditerations );
457  itsleft = MAX(itsleft, 0);
458  itsleft = MIN(itsleft, INT_MAX);
459 
460  SCIPdebugMsg(scip, "iterations left: %d\n", (int) itsleft);
461  return (int) itsleft;
462  }
463 }
464 
465 /** returns the objective coefficient for a variable's bound that will be chosen during filtering */
466 static
468  SCIP* scip, /**< SCIP data structure */
469  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
470  SCIP_VAR* var, /**< variable */
471  SCIP_BOUNDTYPE boundtype /**< boundtype to be filtered? */
472  )
473 {
474  SCIP_Real lb;
475  SCIP_Real ub;
476 
477  assert(scip != NULL);
478  assert(propdata != NULL);
479  assert(var != NULL);
480 
481  lb = SCIPvarGetLbLocal(var);
482  ub = SCIPvarGetUbLocal(var);
483 
484  /* this function should not be called for fixed variables */
485  assert(!varIsFixedLocal(scip, var));
486 
487  /* infinite bounds will not be reached */
488  if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisInfinity(scip, -lb) )
489  return 0.0;
490  if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisInfinity(scip, ub) )
491  return 0.0;
492 
493  if( propdata->normalize )
494  {
495  /* if the length of the domain is too large then the coefficient should be set to +/- 1.0 */
496  if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisInfinity(scip, ub) )
497  return 1.0;
498  if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisInfinity(scip, -lb) )
499  return -1.0;
500 
501  /* otherwise the coefficient is +/- 1.0 / ( ub - lb ) */
502  return boundtype == SCIP_BOUNDTYPE_LOWER ? 1.0 / (ub - lb) : -1.0 / (ub - lb);
503  }
504  else
505  {
506  return boundtype == SCIP_BOUNDTYPE_LOWER ? 1.0 : -1.0;
507  }
508 }
509 
510 /** creates a genvbound if the dual LP solution provides such information
511  *
512  * Consider the problem
513  *
514  * min { +/- x_i : obj * x <= z, lb <= Ax <= ub, l <= x <= u },
515  *
516  * where z is the current cutoff bound. Let (mu, nu, gamma, alpha, beta) >= 0 be the optimal solution of the dual of
517  * problem (P), where the variables correspond to the primal inequalities in the following way:
518  *
519  * Ax >= lb <-> mu
520  * -Ax >= -ub <-> nu
521  * -obj * x >= -z <-> gamma
522  * x >= l <-> alpha
523  * -x >= -u <-> beta
524  *
525  * Fixing these multipliers, by weak duality, we obtain the inequality
526  *
527  * +/- x_i >= lb*mu - ub*nu - z*gamma + l*alpha - u*beta
528  *
529  * that holds for all primal feasible points x with objective value at least z. Setting
530  *
531  * c = lb*mu - ub*nu, redcost_k = alpha_k - beta_k
532  *
533  * we obtain the inequality
534  *
535  * +/- x_i >= sum ( redcost_k * x_k ) + (-gamma) * cutoff_bound + c,
536  *
537  * that holds for all primal feasible points with objective value at least cutoff_bound. Therefore, the latter
538  * inequality can be added as a generalized variable bound.
539  */
540 static
542  SCIP* scip, /**< SCIP data structure */
543  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
544  BOUND* bound, /**< bound of x_i */
545  SCIP_Bool* found /**< pointer to store if we have found a non-trivial genvbound */
546  )
547 {
548  assert(scip != NULL);
549  assert(bound != NULL);
550  assert(propdata != NULL);
551  assert(propdata->genvboundprop != NULL);
552  assert(found != NULL);
554  *found = FALSE;
555 
556  /* make sure we are in probing mode having an optimal LP solution */
557  assert(SCIPinProbing(scip));
558 
559  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
560 
561  /* only genvbounds created in the root node are globally valid
562  *
563  * note: depth changes to one if we use the probing mode to solve the obbt LPs
564  */
565  assert(SCIPgetDepth(scip) == 0 || (SCIPinProbing(scip) && SCIPgetDepth(scip) == 1));
566 
567  SCIPdebugMsg(scip, " try to create a genvbound for <%s>...\n", SCIPvarGetName(bound->var));
568 
569  /* a genvbound with a multiplier for x_i would not help us */
570  if( SCIPisZero(scip, SCIPgetVarRedcost(scip, bound->var)) )
571  {
572  SCIP_VAR** vars; /* global variables array */
573  SCIP_VAR** genvboundvars; /* genvbound variables array */
574 
575  SCIP_VAR* xi; /* variable x_i */
576 
577  SCIP_Real* genvboundcoefs; /* genvbound coefficients array */
578 
579  SCIP_Real gamma_dual; /* dual multiplier of objective cutoff */
580 
581  int k; /* variable for indexing global variables array */
582  int ncoefs; /* number of nonzero coefficients in genvbound */
583  int nvars; /* number of global variables */
584 
585  /* set x_i */
586  xi = bound->var;
587 
588  /* get variable data */
589  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
590 
591  /* count nonzero coefficients in genvbound */
592  ncoefs = 0;
593  for( k = 0; k < nvars; k++ )
594  {
595  if( includeVarGenVBound(scip, vars[k]) )
596  {
597  assert(vars[k] != xi);
598  ncoefs++;
599  }
600  }
601 
602  /* get dual multiplier for the objective cutoff (set to zero if there is no) */
603  if( propdata->cutoffrow == NULL )
604  {
605  gamma_dual = 0.0;
606  }
607  else
608  {
609  assert(!SCIPisInfinity(scip, SCIPgetCutoffbound(scip)));
610 
611  /* note that the objective cutoff is of the form
612  * -inf <= obj * x <= cutoff_bound
613  * but we want the positive dual multiplier!
614  */
615  gamma_dual = -SCIProwGetDualsol(propdata->cutoffrow);
616 
617  /* we need to treat gamma to be exactly 0 if it is below the dual feasibility tolerance, see #2914 */
618  if( EPSZ(gamma_dual, SCIPdualfeastol(scip)) )
619  gamma_dual = 0.0;
620  }
621 
622  /* we need at least one nonzero coefficient or a nonzero dual multiplier for the objective cutoff */
623  if( ncoefs > 0 || gamma_dual != 0.0 )
624  {
625  SCIP_Bool addgenvbound; /* if everything is fine with the redcosts and the bounds, add the genvbound */
626  SCIP_Real c; /* helper variable to calculate constant term in genvbound */
627  int idx; /* variable for indexing genvbound's coefficients array */
628 
629  /* add the bound if the bool is still TRUE after the loop */
630  addgenvbound = TRUE;
631 
632  /* there should be no coefficient for x_i */
633  assert(SCIPisZero(scip, SCIPgetVarRedcost(scip, xi)));
634 
635  /* allocate memory for storing the genvbounds right-hand side variables and coefficients */
636  SCIP_CALL( SCIPallocBufferArray(scip, &(genvboundvars), ncoefs) );
637  SCIP_CALL( SCIPallocBufferArray(scip, &(genvboundcoefs), ncoefs) );
638 
639  /* set c = lb*mu - ub*nu - z*gamma + l*alpha - u*beta */
640  c = SCIPgetLPObjval(scip);
641 
642  /* subtract ( - z * gamma ) from c */
643  c += SCIPgetCutoffbound(scip) * gamma_dual;
644 
645  /* subtract ( l*alpha - u*beta ) from c and set the coefficients of the variables */
646  idx = 0;
647  for( k = 0; k < nvars; k++ )
648  {
649  SCIP_VAR* xk;
650 
651  xk = vars[k];
652 
653  if( includeVarGenVBound(scip, xk) )
654  {
655  SCIP_Real redcost;
656 
657  redcost = SCIPgetVarRedcost(scip, xk);
658 
659  assert(redcost != SCIP_INVALID); /*lint !e777 */
660  assert(xk != xi);
661 
662  /* in this case dont add a genvbound */
663  if( ( (redcost > SCIPdualfeastol(scip)) && SCIPisInfinity(scip, -SCIPvarGetLbLocal(xk)) ) ||
664  ( (redcost < -SCIPdualfeastol(scip)) && SCIPisInfinity(scip, SCIPvarGetUbLocal(xk)) ) )
665  {
666  addgenvbound = FALSE;
667  break;
668  }
669 
670  /* store coefficients */
671  assert(idx < ncoefs);
672  genvboundvars[idx] = xk;
673  genvboundcoefs[idx] = redcost;
674  idx++;
675 
676  /* if redcost > 0, then redcost = alpha_k, otherwise redcost = - beta_k */
677  assert(redcost <= 0 || !SCIPisInfinity(scip, -SCIPvarGetLbLocal(xk)));
678  assert(redcost >= 0 || !SCIPisInfinity(scip, SCIPvarGetUbLocal(xk)));
679  c -= redcost > 0 ? redcost * SCIPvarGetLbLocal(xk) : redcost * SCIPvarGetUbLocal(xk);
680  }
681  }
682 
683  assert(!addgenvbound || idx == ncoefs);
684 
685  /* add genvbound */
686  if( addgenvbound && !SCIPisInfinity(scip, -c) )
687  {
688 #ifndef NDEBUG
689  /* check whether the activity of the LVB in the optimal solution of the LP is equal to the LP objective value */
690  SCIP_Real activity = c - gamma_dual * SCIPgetCutoffbound(scip);
691 
692  for( k = 0; k < ncoefs; ++k )
693  activity += genvboundcoefs[k] * SCIPvarGetLPSol(genvboundvars[k]);
694 
695  SCIPdebugMsg(scip, "LVB activity = %g lpobj = %g\n", activity, SCIPgetLPObjval(scip));
696  assert(EPSZ(SCIPrelDiff(activity, SCIPgetLPObjval(scip)), 18.0 * SCIPdualfeastol(scip)));
697 #endif
698 
699  SCIPdebugMsg(scip, " adding genvbound\n");
700  SCIP_CALL( SCIPgenVBoundAdd(scip, propdata->genvboundprop, genvboundvars, xi, genvboundcoefs, ncoefs,
701  gamma_dual < SCIPdualfeastol(scip) ? 0.0 : -gamma_dual, c, bound->boundtype) );
702  *found = TRUE;
703  }
704 
705  /* free arrays */
706  SCIPfreeBufferArray(scip, &genvboundcoefs);
707  SCIPfreeBufferArray(scip, &genvboundvars);
708  }
709  else
710  {
711  SCIPdebugMsg(scip, " trivial genvbound, skipping\n");
712  }
713  }
714  else
715  {
716  SCIPdebugMsg(scip, " found multiplier for <%s>: %g, skipping\n",
717  SCIPvarGetName(bound->var), SCIPgetVarRedcost(scip, bound->var));
718  }
719 
720  return SCIP_OKAY;
721 }
722 
723 /** exchange a bound which has been processed and updates the last undone and unfiltered bound index
724  * NOTE: this method has to be called after filtering or processing a bound
725  */
726 static
727 void exchangeBounds(
728  SCIP_PROPDATA* propdata, /**< propagator data */
729  int i /**< bound that was filtered or processed */
730  )
731 {
732  assert(i >= 0 && i < propdata->nbounds);
733  assert(propdata->lastidx >= 0 && propdata->lastidx < propdata->nbounds);
734 
735  /* exchange the bounds */
736  if( propdata->lastidx != i )
737  {
738  BOUND* tmp;
740  tmp = propdata->bounds[i];
741  propdata->bounds[i] = propdata->bounds[propdata->lastidx];
742  propdata->bounds[propdata->lastidx] = tmp;
743  }
744 
745  propdata->lastidx -= 1;
746 }
747 
748 /** helper function to return a corner of the domain of two variables */
749 static
750 void getCorner(
751  SCIP_VAR* x, /**< first variable */
752  SCIP_VAR* y, /**< second variable */
753  CORNER corner, /**< corner */
754  SCIP_Real* px, /**< buffer to store point for x */
755  SCIP_Real* py /**< buffer to store point for y */
756  )
757 {
758  assert(x != NULL);
759  assert(y != NULL);
760  assert(px != NULL);
761  assert(py != NULL);
763  switch( corner )
764  {
765  case LEFTBOTTOM:
766  *px = SCIPvarGetLbGlobal(x);
767  *py = SCIPvarGetLbGlobal(y);
768  break;
769  case RIGHTBOTTOM:
770  *px = SCIPvarGetUbGlobal(x);
771  *py = SCIPvarGetLbGlobal(y);
772  break;
773  case LEFTTOP:
774  *px = SCIPvarGetLbGlobal(x);
775  *py = SCIPvarGetUbGlobal(y);
776  break;
777  case RIGHTTOP:
778  *px = SCIPvarGetUbGlobal(x);
779  *py = SCIPvarGetUbGlobal(y);
780  break;
781  case FILTERED:
782  SCIPABORT();
783  }
784 }
785 
786 /** helper function to return the two end points of a diagonal */
787 static
788 void getCorners(
789  SCIP_VAR* x, /**< first variable */
790  SCIP_VAR* y, /**< second variable */
791  CORNER corner, /**< corner */
792  SCIP_Real* xs, /**< buffer to store start point for x */
793  SCIP_Real* ys, /**< buffer to store start point for y */
794  SCIP_Real* xt, /**< buffer to store end point for x */
795  SCIP_Real* yt /**< buffer to store end point for y */
796  )
797 {
798  assert(x != NULL);
799  assert(y != NULL);
800  assert(xs != NULL);
801  assert(ys != NULL);
802  assert(xt != NULL);
803  assert(yt != NULL);
804 
805  /* get end point */
806  getCorner(x,y, corner, xt, yt);
807 
808  /* get start point */
809  switch( corner )
810  {
811  case LEFTBOTTOM:
812  getCorner(x,y, RIGHTTOP, xs, ys);
813  break;
814  case RIGHTBOTTOM:
815  getCorner(x,y, LEFTTOP, xs, ys);
816  break;
817  case LEFTTOP:
818  getCorner(x,y, RIGHTBOTTOM, xs, ys);
819  break;
820  case RIGHTTOP:
821  getCorner(x,y, LEFTBOTTOM, xs, ys);
822  break;
823  case FILTERED:
824  SCIPABORT();
825  }
826 }
827 
828 /** returns the first variable of a bilinear bound */
829 static
831  BILINBOUND* bilinbound /**< bilinear bound */
832  )
833 {
834  assert(bilinbound->expr != NULL);
835  assert(SCIPexprGetNChildren(bilinbound->expr) == 2);
836 
837  return SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(bilinbound->expr)[0]);
838 }
839 
840 /** returns the second variable of a bilinear bound */
841 static
843  BILINBOUND* bilinbound /**< bilinear bound */
844  )
845 {
846  assert(bilinbound->expr != NULL);
847  assert(SCIPexprGetNChildren(bilinbound->expr) == 2);
848 
849  return SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(bilinbound->expr)[1]);
850 }
851 
852 /** returns the negative locks of the expression in a bilinear bound */
853 static
855  BILINBOUND* bilinbound /**< bilinear bound */
856  )
857 {
858  assert(bilinbound->expr != NULL);
859 
860  return SCIPgetExprNLocksNegNonlinear(bilinbound->expr);
861 }
862 
863 /** returns the positive locks of the expression in a bilinear bound */
864 static
866  BILINBOUND* bilinbound /**< bilinear bound */
867  )
868 {
869  assert(bilinbound->expr != NULL);
870 
871  return SCIPgetExprNLocksPosNonlinear(bilinbound->expr);
872 }
873 
874 /** computes the score of a bilinear term bound */
875 static
877  SCIP* scip, /**< SCIP data structure */
878  SCIP_RANDNUMGEN* randnumgen, /**< random number generator */
879  BILINBOUND* bilinbound /**< bilinear bound */
880  )
881 {
882  SCIP_VAR* x = bilinboundGetX(bilinbound);
883  SCIP_VAR* y = bilinboundGetY(bilinbound);
884  SCIP_Real lbx = SCIPvarGetLbLocal(x);
885  SCIP_Real ubx = SCIPvarGetUbLocal(x);
886  SCIP_Real lby = SCIPvarGetLbLocal(y);
887  SCIP_Real uby = SCIPvarGetUbLocal(y);
889 
890  assert(scip != NULL);
891  assert(randnumgen != NULL);
892  assert(bilinbound != NULL);
893 
894  /* consider how often a bilinear term is present in the problem */
895  score = bilinboundGetLocksNeg(bilinbound) + bilinboundGetLocksPos(bilinbound);
896 
897  /* penalize small variable domains; TODO tune the factor in the logarithm, maybe add a parameter for it */
898  if( ubx - lbx < 0.5 )
899  score += log(2.0*(ubx-lbx) + SCIPepsilon(scip));
900  if( uby - lby < 0.5 )
901  score += log(2.0*(uby-lby) + SCIPepsilon(scip));
902 
903  /* consider interiority of variables in the LP solution */
905  {
906  SCIP_Real solx = SCIPvarGetLPSol(x);
907  SCIP_Real soly = SCIPvarGetLPSol(y);
908  SCIP_Real interiorityx = MIN(solx-lbx, ubx-solx) / MAX(ubx-lbx, SCIPepsilon(scip)); /*lint !e666*/
909  SCIP_Real interiorityy = MIN(soly-lby, uby-soly) / MAX(uby-lby, SCIPepsilon(scip)); /*lint !e666*/
910 
911  score += interiorityx + interiorityy;
912  }
913 
914  /* randomize score */
915  score *= 1.0 + SCIPrandomGetReal(randnumgen, -SCIPepsilon(scip), SCIPepsilon(scip));
916 
917  return score;
918 }
919 
920 /** trying to filter some bounds using the existing LP solution */
921 static
923  SCIP* scip, /**< original SCIP data structure */
924  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
925  int* nfiltered, /**< how many bounds were filtered this round? */
926  BOUND* currbound /**< bound for which OBBT LP was solved (Note: might be NULL) */
927  )
928 {
929  int i;
930 
931  assert(scip != NULL);
932  assert(propdata != NULL);
933  assert(nfiltered != NULL);
935  *nfiltered = 0;
936 
937  /* only apply filtering if an LP solution is at hand */
939  {
940  SCIPdebugMsg(scip, "can't filter using existing lp solution since it was not solved to optimality\n");
941  return SCIP_OKAY;
942  }
943 
944  /* check if a bound is tight */
945  for( i = propdata->nbounds - 1; i >= 0; --i )
946  {
947  BOUND* bound; /* shortcut for current bound */
948 
949  SCIP_Real solval; /* the variables value in the current solution */
950  SCIP_Real boundval; /* current local bound for the variable */
951 
952  bound = propdata->bounds[i];
953  if( bound->filtered || bound->done )
954  continue;
955 
956  boundval = bound->boundtype == SCIP_BOUNDTYPE_UPPER ?
957  SCIPvarGetUbLocal(bound->var) : SCIPvarGetLbLocal(bound->var);
958  solval = SCIPvarGetLPSol(bound->var);
959 
960  /* bound is tight; since this holds for all fixed variables, those are filtered here automatically; if the lp solution
961  * is infinity, then also the bound is tight */
962  if( (bound->boundtype == SCIP_BOUNDTYPE_UPPER &&
963  (SCIPisInfinity(scip, solval) || SCIPisFeasGE(scip, solval, boundval)))
964  || (bound->boundtype == SCIP_BOUNDTYPE_LOWER &&
965  (SCIPisInfinity(scip, -solval) || SCIPisFeasLE(scip, solval, boundval))) )
966  {
967  SCIP_BASESTAT basestat;
968 
969  /* mark bound as filtered */
970  bound->filtered = TRUE;
971  SCIPdebugMsg(scip, "trivial filtered var: %s boundval=%e solval=%e\n", SCIPvarGetName(bound->var), boundval, solval);
972 
973  /* get the basis status of the variable */
974  basestat = SCIPcolGetBasisStatus(SCIPvarGetCol(bound->var));
975 
976  /* solve corresponding OBBT LP and try to generate a nontrivial genvbound */
977  if( propdata->genvbdsduringfilter && currbound != NULL && basestat == SCIP_BASESTAT_BASIC )
978  {
979 #ifndef NDEBUG
980  int j;
981 #endif
982  SCIP_Bool optimal;
983  SCIP_Bool error;
984 
985  /* set objective coefficient of the bound */
986  SCIP_CALL( SCIPchgVarObjProbing(scip, currbound->var, 0.0) );
987  SCIP_CALL( setObjProbing(scip, propdata, bound, 1.0) );
988 
989 #ifndef NDEBUG
990  for( j = 0; j < SCIPgetNVars(scip); ++j )
991  {
992  SCIP_VAR* var;
993 
994  var = SCIPgetVars(scip)[j];
995  assert(var != NULL);
996  assert(SCIPisZero(scip, SCIPgetVarObjProbing(scip, var)) || var == bound->var);
997  }
998 #endif
999 
1000  /* solve the OBBT LP */
1001  propdata->nprobingiterations -= SCIPgetNLPIterations(scip);
1002  SCIP_CALL( solveLP(scip, -1, &error, &optimal) );
1003  propdata->nprobingiterations += SCIPgetNLPIterations(scip);
1004  assert(propdata->nprobingiterations >= 0);
1005 
1006  /* try to generate a genvbound if we have solved the OBBT LP */
1007  if( optimal && propdata->genvboundprop != NULL
1008  && (SCIPgetDepth(scip) == 0 || (SCIPinProbing(scip) && SCIPgetDepth(scip) == 1)) )
1009  {
1010  SCIP_Bool found;
1011 
1012  assert(!error);
1013  SCIP_CALL( createGenVBound(scip, propdata, bound, &found) );
1014 
1015  if( found )
1016  {
1017  propdata->ngenvboundstrivfil += 1;
1018  SCIPdebugMsg(scip, "found genvbound during trivial filtering\n");
1019  }
1020  }
1021 
1022  /* restore objective function */
1023  SCIP_CALL( setObjProbing(scip, propdata, bound, 0.0) );
1024  SCIP_CALL( setObjProbing(scip, propdata, currbound, 1.0) );
1025  }
1026 
1027  /* exchange bound i with propdata->bounds[propdata->lastidx] */
1028  if( propdata->lastidx >= 0 )
1029  exchangeBounds(propdata, i);
1030 
1031  /* increase number of filtered variables */
1032  (*nfiltered)++;
1033  }
1034  }
1035 
1036  /* try to filter bilinear bounds */
1037  for( i = propdata->lastbilinidx; i < propdata->nbilinbounds; ++i )
1038  {
1039  CORNER corners[4] = {LEFTTOP, LEFTBOTTOM, RIGHTTOP, RIGHTBOTTOM};
1040  BILINBOUND* bilinbound = propdata->bilinbounds[i];
1041  SCIP_Real solx;
1042  SCIP_Real soly;
1043  SCIPdebug(int oldfiltered;)
1044  int j;
1045 
1046  /* skip processed and filtered bounds */
1047  if( bilinbound->done || bilinbound->filtered == FILTERED ) /*lint !e641*/
1048  continue;
1049 
1050  SCIPdebug(oldfiltered = bilinbound->filtered;)
1051  solx = SCIPvarGetLPSol(bilinboundGetX(bilinbound));
1052  soly = SCIPvarGetLPSol(bilinboundGetY(bilinbound));
1053 
1054  /* check cases of unbounded solution values */
1055  if( SCIPisInfinity(scip, solx) )
1056  bilinbound->filtered = bilinbound->filtered | RIGHTTOP | RIGHTBOTTOM; /*lint !e641*/
1057  else if( SCIPisInfinity(scip, -solx) )
1058  bilinbound->filtered = bilinbound->filtered | LEFTTOP | LEFTBOTTOM; /*lint !e641*/
1059 
1060  if( SCIPisInfinity(scip, soly) )
1061  bilinbound->filtered = bilinbound->filtered | RIGHTTOP | LEFTTOP; /*lint !e641*/
1062  else if( SCIPisInfinity(scip, -soly) )
1063  bilinbound->filtered = bilinbound->filtered | RIGHTBOTTOM | LEFTBOTTOM; /*lint !e641*/
1064 
1065  /* check all corners */
1066  for( j = 0; j < 4; ++j )
1067  {
1068  SCIP_Real xt = SCIP_INVALID;
1069  SCIP_Real yt = SCIP_INVALID;
1070 
1071  getCorner(bilinboundGetX(bilinbound), bilinboundGetY(bilinbound), corners[j], &xt, &yt);
1072 
1073  if( (SCIPisInfinity(scip, REALABS(solx)) || SCIPisFeasEQ(scip, xt, solx))
1074  && (SCIPisInfinity(scip, REALABS(soly)) || SCIPisFeasEQ(scip, yt, soly)) )
1075  bilinbound->filtered = bilinbound->filtered | corners[j]; /*lint !e641*/
1076  }
1077 
1078 #ifdef SCIP_DEBUG
1079  if( oldfiltered != bilinbound->filtered )
1080  {
1081  SCIP_VAR* x = bilinboundGetX(bilinbound);
1082  SCIP_VAR* y = bilinboundGetY(bilinbound);
1083  SCIPdebugMessage("filtered corners %d for (%s,%s) = (%g,%g) in [%g,%g]x[%g,%g]\n",
1084  bilinbound->filtered - oldfiltered, SCIPvarGetName(x), SCIPvarGetName(y), solx, soly,
1086  }
1087 #endif
1088  }
1089 
1090  return SCIP_OKAY;
1091 }
1092 
1093 /** enforces one round of filtering */
1094 static
1096  SCIP* scip, /**< SCIP data structure */
1097  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
1098  int itlimit, /**< LP iteration limit (-1: no limit) */
1099  int* nfiltered, /**< how many bounds were filtered this round */
1100  SCIP_Real* objcoefs, /**< array to store the nontrivial objective coefficients */
1101  int* objcoefsinds, /**< array to store bound indices for which their corresponding variables
1102  * has a nontrivial objective coefficient */
1103  int nobjcoefs /**< number of nontrivial objective coefficients */
1104  )
1105 {
1106  SCIP_VAR** vars; /* array of the problems variables */
1107  SCIP_Bool error;
1108  SCIP_Bool optimal;
1109 
1110  int nvars; /* number of the problems variables */
1111  int i;
1112 
1113  assert(scip != NULL);
1114  assert(SCIPinProbing(scip));
1115  assert(propdata != NULL);
1116  assert(itlimit == -1 || itlimit >= 0);
1117  assert(nfiltered != NULL);
1118  assert(objcoefs != NULL);
1119  assert(objcoefsinds != NULL);
1120  assert(nobjcoefs >= 0);
1121 
1122  *nfiltered = 0;
1123 
1124  /* get variable data */
1125  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
1126 
1127  /* solve LP */
1128  propdata->nfilterlpiters -= (int) SCIPgetNLPIterations(scip);
1129  SCIP_CALL( solveLP(scip, itlimit, &error, &optimal) );
1130  propdata->nfilterlpiters += (int) SCIPgetNLPIterations(scip);
1131  assert(propdata->nfilterlpiters >= 0);
1132 
1133  if( !optimal )
1134  {
1135  SCIPdebugMsg(scip, "skipping filter round since the LP was not solved to optimality\n");
1136  return SCIP_OKAY;
1137  }
1138 
1139  assert(!error);
1140 
1141  /* check if a bound is tight */
1142  for( i = 0; i < propdata->nbounds; i++ )
1143  {
1144  BOUND* bound; /* shortcut for current bound */
1145 
1146  SCIP_Real solval; /* the variables value in the current solution */
1147  SCIP_Real boundval; /* current local bound for the variable */
1148 
1149  bound = propdata->bounds[i];
1150 
1151  /* if bound is filtered it was handled already before */
1152  if( bound->filtered )
1153  continue;
1154 
1155  boundval = bound->boundtype == SCIP_BOUNDTYPE_UPPER ?
1156  SCIPvarGetUbLocal(bound->var) : SCIPvarGetLbLocal(bound->var);
1157  solval = SCIPvarGetLPSol(bound->var);
1158 
1159  /* bound is tight */
1160  if( (bound->boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisFeasGE(scip, solval, boundval))
1161  || (bound->boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisFeasLE(scip, solval, boundval)) )
1162  {
1163  SCIP_Real objcoef;
1164  SCIP_BASESTAT basestat;
1165 
1166  /* mark bound as filtered */
1167  bound->filtered = TRUE;
1168 
1169  /* get the basis status of the variable */
1170  basestat = SCIPcolGetBasisStatus(SCIPvarGetCol(bound->var));
1171 
1172  /* increase number of filtered variables */
1173  (*nfiltered)++;
1174 
1175  /* solve corresponding OBBT LP and try to generate a nontrivial genvbound */
1176  if( propdata->genvbdsduringfilter && basestat == SCIP_BASESTAT_BASIC )
1177  {
1178  int j;
1179 
1180  /* set all objective coefficients to zero */
1181  for( j = 0; j < nobjcoefs; ++j )
1182  {
1183  BOUND* filterbound;
1184 
1185  filterbound = propdata->bounds[ objcoefsinds[j] ];
1186  assert(filterbound != NULL);
1187 
1188  SCIP_CALL( SCIPchgVarObjProbing(scip, filterbound->var, 0.0) );
1189  }
1190 
1191 #ifndef NDEBUG
1192  for( j = 0; j < nvars; ++j )
1193  assert(SCIPisZero(scip, SCIPgetVarObjProbing(scip, vars[j])));
1194 #endif
1195 
1196  /* set objective coefficient of the bound */
1197  SCIP_CALL( setObjProbing(scip, propdata, bound, 1.0) );
1198 
1199  /* solve the OBBT LP */
1200  propdata->nfilterlpiters -= (int) SCIPgetNLPIterations(scip);
1201  SCIP_CALL( solveLP(scip, -1, &error, &optimal) );
1202  propdata->nfilterlpiters += (int) SCIPgetNLPIterations(scip);
1203  assert(propdata->nfilterlpiters >= 0);
1204 
1205  /* try to generate a genvbound if we have solved the OBBT LP */
1206  if( optimal && propdata->genvboundprop != NULL
1207  && (SCIPgetDepth(scip) == 0 || (SCIPinProbing(scip) && SCIPgetDepth(scip) == 1)) )
1208  {
1209  SCIP_Bool found;
1210 
1211  assert(!error);
1212  SCIP_CALL( createGenVBound(scip, propdata, bound, &found) );
1213 
1214  if( found )
1215  {
1216  propdata->ngenvboundsaggrfil += 1;
1217  SCIPdebugMsg(scip, "found genvbound during aggressive filtering\n");
1218  }
1219  }
1220 
1221  /* restore objective function */
1222  for( j = 0; j < nobjcoefs; ++j )
1223  {
1224  BOUND* filterbound;
1225 
1226  filterbound = propdata->bounds[ objcoefsinds[j] ];
1227  assert(filterbound != NULL);
1228 
1229  /* NOTE: only restore coefficients of nonfiltered bounds */
1230  if( !filterbound->filtered )
1231  {
1232  assert(!SCIPisZero(scip, objcoefs[j]));
1233  SCIP_CALL( SCIPchgVarObjProbing(scip, propdata->bounds[ objcoefsinds[j] ]->var, objcoefs[j]) );
1234  }
1235  }
1236  }
1237 
1238  /* get the corresponding variable's objective coefficient */
1239  objcoef = SCIPgetVarObjProbing(scip, bound->var);
1240 
1241  /* change objective coefficient if it was set up for this bound */
1242  if( (bound->boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisNegative(scip, objcoef))
1243  || (bound->boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisPositive(scip, objcoef)) )
1244  {
1245  SCIP_CALL( SCIPchgVarObjProbing(scip, bound->var, 0.0) );
1246  }
1247  }
1248  }
1249 
1250  return SCIP_OKAY;
1251 }
1252 
1253 /** filter some bounds that are not improvable by solving auxiliary LPs */
1254 static
1256  SCIP* scip, /**< SCIP data structure */
1257  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
1258  SCIP_Longint itlimit /**< LP iteration limit (-1: no limit) */
1259  )
1260 {
1261  SCIP_VAR** vars;
1262  SCIP_Longint nolditerations;
1263  SCIP_Real* objcoefs; /* array to store the nontrivial objective coefficients */
1264  int* objcoefsinds; /* array to store bound indices for which the corresponding variable
1265  * has a nontrivial objective coefficient */
1266  int nobjcoefs; /* number of nontrivial objective coefficients */
1267  int nleftiterations;
1268  int i;
1269  int nfiltered;
1270  int ntotalfiltered;
1271  int nvars;
1272 
1273  assert(scip != NULL);
1274  assert(SCIPinProbing(scip));
1275  assert(propdata != NULL);
1276  assert(itlimit == -1 || itlimit >= 0);
1277 
1278  ntotalfiltered = 0;
1279  nolditerations = SCIPgetNLPIterations(scip);
1280  nleftiterations = getIterationsLeft(scip, nolditerations, itlimit);
1281 
1282  /* get variable data */
1283  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
1284 
1285  SCIPdebugMsg(scip, "start filter rounds\n");
1286 
1287  SCIP_CALL( SCIPallocBufferArray(scip, &objcoefs, propdata->nbounds) );
1288  SCIP_CALL( SCIPallocBufferArray(scip, &objcoefsinds, propdata->nbounds) );
1289  nobjcoefs = 0;
1290 
1291  /*
1292  * 1.) Try first to filter lower bounds of interesting variables, whose bounds are not already filtered
1293  */
1294 
1295  for( i = 0; i < nvars; i++ )
1296  {
1297  SCIP_CALL( SCIPchgVarObjProbing(scip, vars[i], 0.0) );
1298  }
1299 
1300  for( i = 0; i < propdata->nbounds; i++ )
1301  {
1302  if( propdata->bounds[i]->boundtype == SCIP_BOUNDTYPE_LOWER && !propdata->bounds[i]->filtered
1303  && !propdata->bounds[i]->done )
1304  {
1305  SCIP_Real objcoef;
1306 
1307  objcoef = getFilterCoef(scip, propdata, propdata->bounds[i]->var, SCIP_BOUNDTYPE_LOWER);
1308 
1309  if( !SCIPisZero(scip, objcoef) )
1310  {
1311  SCIP_CALL( SCIPchgVarObjProbing(scip, propdata->bounds[i]->var, objcoef) );
1312 
1313  /* store nontrivial objective coefficients */
1314  objcoefs[nobjcoefs] = objcoef;
1315  objcoefsinds[nobjcoefs] = i;
1316  ++nobjcoefs;
1317  }
1318  }
1319  }
1320 
1321  do
1322  {
1323  SCIPdebugMsg(scip, "doing a lower bounds round\n");
1324  SCIP_CALL( filterRound(scip, propdata, nleftiterations, &nfiltered, objcoefs, objcoefsinds, nobjcoefs) );
1325  ntotalfiltered += nfiltered;
1326  SCIPdebugMsg(scip, "filtered %d more bounds in lower bounds round\n", nfiltered);
1327 
1328  /* update iterations left */
1329  nleftiterations = getIterationsLeft(scip, nolditerations, itlimit);
1330  }
1331  while( nfiltered >= propdata->nminfilter && ( nleftiterations == -1 || nleftiterations > 0 ) );
1332 
1333  /*
1334  * 2.) Now try to filter the remaining upper bounds of interesting variables, whose bounds are not already filtered
1335  */
1336 
1337  /* set all objective coefficients to zero */
1338  for( i = 0; i < nobjcoefs; i++ )
1339  {
1340  BOUND* bound;
1341 
1342  assert(objcoefsinds[i] >= 0 && objcoefsinds[i] < propdata->nbounds);
1343  bound = propdata->bounds[ objcoefsinds[i] ];
1344  assert(bound != NULL);
1345  SCIP_CALL( SCIPchgVarObjProbing(scip, bound->var, 0.0) );
1346  }
1347 
1348  /* reset number of nontrivial objective coefficients */
1349  nobjcoefs = 0;
1350 
1351 #ifndef NDEBUG
1352  for( i = 0; i < nvars; ++i )
1353  assert(SCIPisZero(scip, SCIPgetVarObjProbing(scip, vars[i])));
1354 #endif
1355 
1356  for( i = 0; i < propdata->nbounds; i++ )
1357  {
1358  if( propdata->bounds[i]->boundtype == SCIP_BOUNDTYPE_UPPER && !propdata->bounds[i]->filtered )
1359  {
1360  SCIP_Real objcoef;
1361 
1362  objcoef = getFilterCoef(scip, propdata, propdata->bounds[i]->var, SCIP_BOUNDTYPE_UPPER);
1363 
1364  if( !SCIPisZero(scip, objcoef) )
1365  {
1366  SCIP_CALL( SCIPchgVarObjProbing(scip, propdata->bounds[i]->var, objcoef) );
1367 
1368  /* store nontrivial objective coefficients */
1369  objcoefs[nobjcoefs] = objcoef;
1370  objcoefsinds[nobjcoefs] = i;
1371  ++nobjcoefs;
1372  }
1373  }
1374  }
1375 
1376  do
1377  {
1378  SCIPdebugMsg(scip, "doing an upper bounds round\n");
1379  SCIP_CALL( filterRound(scip, propdata, nleftiterations, &nfiltered, objcoefs, objcoefsinds, nobjcoefs) );
1380  SCIPdebugMsg(scip, "filtered %d more bounds in upper bounds round\n", nfiltered);
1381  ntotalfiltered += nfiltered;
1382  /* update iterations left */
1383  nleftiterations = getIterationsLeft(scip, nolditerations, itlimit);
1384  }
1385  while( nfiltered >= propdata->nminfilter && ( nleftiterations == -1 || nleftiterations > 0 ) );
1386 
1387  SCIPdebugMsg(scip, "filtered %d this round\n", ntotalfiltered);
1388  propdata->nfiltered += ntotalfiltered;
1389 
1390  /* free array */
1391  SCIPfreeBufferArray(scip, &objcoefsinds);
1392  SCIPfreeBufferArray(scip, &objcoefs);
1393 
1394  return SCIP_OKAY;
1395 }
1396 
1397 /** applies possible bound changes that were found */
1398 static
1400  SCIP* scip, /**< SCIP data structure */
1401  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
1402  SCIP_RESULT* result /**< result pointer */
1403  )
1404 {
1405 #ifdef SCIP_DEBUG
1406  int ntightened; /* stores the number of successful bound changes */
1407 #endif
1408  int i;
1409 
1410  assert(scip != NULL);
1411  assert(!SCIPinProbing(scip));
1412  assert(propdata != NULL);
1413  assert(result != NULL);
1414  assert(*result == SCIP_DIDNOTFIND);
1415 
1416  SCIPdebug( ntightened = 0 );
1417 
1418  for( i = 0; i < propdata->nbounds; i++ )
1419  {
1420  BOUND* bound; /* shortcut to the current bound */
1421  SCIP_Bool infeas; /* stores wether a tightening approach forced an infeasibilty */
1422  SCIP_Bool tightened; /* stores wether a tightening approach was successful */
1423 
1424  bound = propdata->bounds[i];
1425 
1426  if( bound->found )
1427  {
1428  SCIPdebug( double oldbound = (bound->boundtype == SCIP_BOUNDTYPE_LOWER)
1429  ? SCIPvarGetLbLocal(bound->var)
1430  : SCIPvarGetUbLocal(bound->var) );
1431 
1432  if( bound->boundtype == SCIP_BOUNDTYPE_LOWER )
1433  {
1434  SCIP_CALL( SCIPtightenVarLb(scip, bound->var, bound->newval, FALSE, &infeas, &tightened) );
1435  }
1436  else
1437  {
1438  SCIP_CALL( SCIPtightenVarUb(scip, bound->var, bound->newval, FALSE, &infeas, &tightened) );
1439  }
1440 
1441  /* handle information about the success */
1442  if( infeas )
1443  {
1444  *result = SCIP_CUTOFF;
1445  SCIPdebugMsg(scip, "cut off\n");
1446  break;
1447  }
1448 
1449  if( tightened )
1450  {
1451  SCIPdebug( SCIPdebugMsg(scip, "tightended: %s old: %e new: %e\n" , SCIPvarGetName(bound->var), oldbound,
1452  bound->newval) );
1453  *result = SCIP_REDUCEDDOM;
1454  SCIPdebug( ntightened++ );
1455  }
1456  }
1457  }
1458 
1459  SCIPdebug( SCIPdebugMsg(scip, "tightened bounds: %d\n", ntightened) );
1460 
1461  return SCIP_OKAY;
1462 }
1463 
1464 /** tries to tighten a bound in probing mode */
1465 static
1467  SCIP* scip, /**< SCIP data structure */
1468  BOUND* bound, /**< bound that could be tightened */
1469  SCIP_Real newval, /**< new bound value */
1470  SCIP_Bool* tightened /**< was tightening successful? */
1471  )
1472 {
1473  SCIP_Real lb;
1474  SCIP_Real ub;
1475 
1476  assert(scip != NULL);
1477  assert(SCIPinProbing(scip));
1478  assert(bound != NULL);
1479  assert(tightened != NULL);
1480 
1481  *tightened = FALSE;
1482 
1483  /* get old bounds */
1484  lb = SCIPvarGetLbLocal(bound->var);
1485  ub = SCIPvarGetUbLocal(bound->var);
1486 
1487  if( bound->boundtype == SCIP_BOUNDTYPE_LOWER )
1488  {
1489  /* round bounds new value if variable is integral */
1490  if( SCIPvarIsIntegral(bound->var) )
1491  newval = SCIPceil(scip, newval);
1492 
1493  /* ensure that we give consistent bounds to the LP solver */
1494  if( newval > ub )
1495  newval = ub;
1496 
1497  /* tighten if really better */
1498  if( SCIPisLbBetter(scip, newval, lb, ub) )
1499  {
1500  SCIP_CALL( SCIPchgVarLbProbing(scip, bound->var, newval) );
1501  *tightened = TRUE;
1502  }
1503  }
1504  else
1505  {
1506  /* round bounds new value if variable is integral */
1507  if( SCIPvarIsIntegral(bound->var) )
1508  newval = SCIPfloor(scip, newval);
1509 
1510  /* ensure that we give consistent bounds to the LP solver */
1511  if( newval < lb )
1512  newval = lb;
1513 
1514  /* tighten if really better */
1515  if( SCIPisUbBetter(scip, newval, lb, ub) )
1516  {
1517  SCIP_CALL( SCIPchgVarUbProbing(scip, bound->var, newval) );
1518  *tightened = TRUE;
1519  }
1520  }
1521 
1522  return SCIP_OKAY;
1523 }
1524 
1525 /** comparison method for two bounds w.r.t. their scores */
1526 static
1527 SCIP_DECL_SORTPTRCOMP(compBoundsScore)
1528 {
1529  BOUND* bound1 = (BOUND*) elem1;
1530  BOUND* bound2 = (BOUND*) elem2;
1531 
1532  return bound1->score == bound2->score ? 0 : ( bound1->score > bound2->score ? 1 : -1 );
1533 }
1534 
1535 /** comparison method for two bilinear term bounds w.r.t. their scores */
1536 static
1537 SCIP_DECL_SORTPTRCOMP(compBilinboundsScore)
1538 {
1539  BILINBOUND* bound1 = (BILINBOUND*) elem1;
1540  BILINBOUND* bound2 = (BILINBOUND*) elem2;
1541 
1542  return bound1->score == bound2->score ? 0 : ( bound1->score > bound2->score ? 1 : -1 ); /*lint !e777*/
1543 }
1544 
1545 /** comparison method for two bounds w.r.t. their boundtype */
1546 static
1547 SCIP_DECL_SORTPTRCOMP(compBoundsBoundtype)
1548 {
1549  int diff;
1550  BOUND* bound1 = (BOUND*) elem1;
1551  BOUND* bound2 = (BOUND*) elem2;
1552 
1553  /* prioritize undone bounds */
1554  diff = (!bound1->done ? 1 : 0) - (!bound2->done ? 1 : 0);
1555  if( diff != 0 )
1556  return diff;
1557 
1558  /* prioritize unfiltered bounds */
1559  diff = (!bound1->filtered ? 1 : 0) - (!bound2->filtered ? 1 : 0);
1560  if( diff != 0 )
1561  return diff;
1562 
1563  diff = (bound1->boundtype == SCIP_BOUNDTYPE_LOWER ? 1 : 0) - (bound2->boundtype == SCIP_BOUNDTYPE_LOWER ? 1 : 0);
1564 
1565  if( diff == 0 )
1566  return (bound1->score == bound2->score) ? 0 : (bound1->score > bound2->score ? 1 : -1);
1567  else
1568  return diff;
1569 }
1570 
1571 /** sort the propdata->bounds array with their distance or their boundtype key */
1572 static
1574  SCIP* scip, /**< SCIP data structure */
1575  SCIP_PROPDATA* propdata /**< propagator data */
1576  )
1577 {
1578  assert(scip != NULL);
1579  assert(propdata != NULL);
1580 
1581  SCIPdebugMsg(scip, "sort bounds\n");
1582  SCIPsortDownPtr((void**) propdata->bounds, compBoundsBoundtype, propdata->nbounds);
1583 
1584  return SCIP_OKAY;
1586 
1587 /** evaluates a bound for the current LP solution */
1588 static
1590  SCIP* scip,
1591  BOUND* bound
1592  )
1593 {
1594  assert(scip != NULL);
1595  assert(bound != NULL);
1596 
1597  if( bound->boundtype == SCIP_BOUNDTYPE_LOWER )
1598  return REALABS( SCIPvarGetLPSol(bound->var) - SCIPvarGetLbLocal(bound->var) );
1599  else
1600  return REALABS( SCIPvarGetUbLocal(bound->var) - SCIPvarGetLPSol(bound->var) );
1602 
1603 /** returns the index of the next undone and unfiltered bound with the smallest distance */
1604 static
1605 int nextBound(
1606  SCIP* scip, /**< SCIP data structure */
1607  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
1608  SCIP_Bool convexphase /**< consider only convex variables? */
1609  )
1610 {
1611  SCIP_Real bestval;
1612  int bestidx;
1613  int k;
1614 
1615  assert(scip != NULL);
1616  assert(propdata != NULL);
1618  bestidx = -1;
1619  bestval = SCIPinfinity(scip);
1620 
1621  for( k = 0; k <= propdata->lastidx; ++k )
1622  {
1623  BOUND* tmpbound;
1624  tmpbound = propdata->bounds[k];
1625 
1626  assert(tmpbound != NULL);
1627 
1628  if( !tmpbound->filtered && !tmpbound->done && (tmpbound->nonconvex == !convexphase) )
1629  {
1630  SCIP_Real boundval;
1631 
1632  /* return the next bound which is not done or unfiltered yet */
1633  if( propdata->orderingalgo == 0 )
1634  return k;
1635 
1636  boundval = evalBound(scip, tmpbound);
1637 
1638  /* negate boundval if we use the reverse greedy algorithm */
1639  boundval = (propdata->orderingalgo == 2) ? -1.0 * boundval : boundval;
1640 
1641  if( bestidx == -1 || boundval < bestval )
1642  {
1643  bestidx = k;
1644  bestval = boundval;
1645  }
1646  }
1647  }
1648 
1649  return bestidx; /*lint !e438*/
1650 }
1651 
1652 /** try to separate the solution of the last OBBT LP in order to learn better variable bounds; we apply additional
1653  * separation rounds as long as the routine finds better bounds; because of dual degeneracy we apply a minimum number of
1654  * separation rounds
1655  */
1656 static
1658  SCIP* scip, /**< SCIP data structure */
1659  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
1660  BOUND* currbound, /**< current bound */
1661  SCIP_Longint* nleftiterations, /**< number of left iterations (-1 for no limit) */
1662  SCIP_Bool* success /**< pointer to store if we have found a better bound */
1663  )
1664 {
1665  SCIP_Bool inroot;
1666  int i;
1667 
1668  assert(nleftiterations != NULL);
1669  assert(success != NULL);
1670  assert(SCIPinProbing(scip));
1671 
1672  *success = FALSE;
1673 
1674  /* check if we are originally in the root node */
1675  inroot = SCIPgetDepth(scip) == 1;
1676 
1677  for( i = 0; i <= propdata->sepamaxiter; ++i )
1678  {
1679  SCIPdebug( SCIP_Longint nlpiter; )
1680  SCIP_Real oldval;
1681  SCIP_Bool cutoff;
1682  SCIP_Bool delayed;
1683  SCIP_Bool error;
1684  SCIP_Bool optimal;
1685  SCIP_Bool tightened;
1686 
1687  oldval = SCIPvarGetLPSol(currbound->var);
1688 
1689  /* find and store cuts to separate the current LP solution */
1690  SCIP_CALL( SCIPseparateSol(scip, NULL, inroot, TRUE, FALSE, &delayed, &cutoff) );
1691  SCIPdebugMsg(scip, "applySeparation() - ncuts = %d\n", SCIPgetNCuts(scip));
1692 
1693  /* leave if we did not found any cut */
1694  if( SCIPgetNCuts(scip) == 0 )
1695  break;
1696 
1697  /* apply cuts and resolve LP */
1698  SCIP_CALL( SCIPapplyCutsProbing(scip, &cutoff) );
1699  assert(SCIPgetNCuts(scip) == 0);
1700  SCIPdebug( nlpiter = SCIPgetNLPIterations(scip); )
1701  SCIP_CALL( solveLP(scip, (int) *nleftiterations, &error, &optimal) );
1702  SCIPdebug( nlpiter = SCIPgetNLPIterations(scip) - nlpiter; )
1703  SCIPdebug( SCIPdebugMsg(scip, "applySeparation() - optimal=%u error=%u lpiter=%" SCIP_LONGINT_FORMAT "\n", optimal, error, nlpiter); )
1704  SCIPdebugMsg(scip, "oldval = %e newval = %e\n", oldval, SCIPvarGetLPSol(currbound->var));
1705 
1706  /* leave if we did not solve the LP to optimality or an error occured */
1707  if( error || !optimal )
1708  break;
1709 
1710  /* try to generate a genvbound */
1711  if( inroot && propdata->genvboundprop != NULL && propdata->genvbdsduringsepa )
1712  {
1713  SCIP_Bool found;
1714  SCIP_CALL( createGenVBound(scip, propdata, currbound, &found) );
1715  propdata->ngenvboundsprobing += found ? 1 : 0;
1716  }
1717 
1718  /* try to tight the variable bound */
1719  tightened = FALSE;
1720  if( !SCIPisEQ(scip, oldval, SCIPvarGetLPSol(currbound->var)) )
1721  {
1722  SCIP_CALL( tightenBoundProbing(scip, currbound, SCIPvarGetLPSol(currbound->var), &tightened) );
1723  SCIPdebugMsg(scip, "apply separation - tightened=%u oldval=%e newval=%e\n", tightened, oldval,
1724  SCIPvarGetLPSol(currbound->var));
1725 
1726  *success |= tightened;
1727  }
1728 
1729  /* leave the separation if we did not tighten the bound and proceed at least propdata->sepaminiter iterations */
1730  if( !tightened && i >= propdata->sepaminiter )
1731  break;
1732  }
1733 
1734  return SCIP_OKAY;
1735 }
1736 
1737 /** finds new variable bounds until no iterations left or all bounds have been checked */
1738 static
1740  SCIP* scip, /**< SCIP data structure */
1741  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
1742  SCIP_Longint* nleftiterations, /**< pointer to store the number of left iterations */
1743  SCIP_Bool convexphase /**< consider only convex variables? */
1744  )
1745 {
1746  SCIP_Longint nolditerations;
1747  SCIP_Bool iterationsleft;
1748  BOUND* currbound;
1749  SCIP_Longint itlimit;
1750  int nextboundidx;
1752  assert(scip != NULL);
1753  assert(propdata != NULL);
1754  assert(nleftiterations != NULL);
1755 
1756  /* update the number of left iterations */
1757  nolditerations = SCIPgetNLPIterations(scip);
1758  itlimit = *nleftiterations;
1759  assert(*nleftiterations == getIterationsLeft(scip, nolditerations, itlimit));
1760  iterationsleft = (*nleftiterations == -1) || (*nleftiterations > 0);
1761 
1762  /* To improve the performance we sort the bound in such a way that the undone and
1763  * unfiltered bounds are at the end of propdata->bounds. We calculate and update
1764  * the position of the last unfiltered and undone bound in propdata->lastidx
1765  */
1766  if( !convexphase )
1767  {
1768  /* sort bounds */
1769  SCIP_CALL( sortBounds(scip, propdata) );
1770 
1771  /* if the first bound is filtered or done then there is no bound left */
1772  if( propdata->bounds[0]->done || propdata->bounds[0]->filtered )
1773  {
1774  SCIPdebugMsg(scip, "no unprocessed/unfiltered bound left\n");
1775  return SCIP_OKAY;
1776  }
1777 
1778  /* compute the last undone and unfiltered node */
1779  propdata->lastidx = 0;
1780  while( propdata->lastidx < propdata->nbounds - 1 && !propdata->bounds[propdata->lastidx]->done &&
1781  !propdata->bounds[propdata->lastidx]->filtered )
1782  ++propdata->lastidx;
1783 
1784  SCIPdebugMsg(scip, "lastidx = %d\n", propdata->lastidx);
1785  }
1786 
1787  /* find the first unprocessed bound */
1788  nextboundidx = nextBound(scip, propdata, convexphase);
1789 
1790  /* skip if there is no bound left */
1791  if( nextboundidx == -1 )
1792  {
1793  SCIPdebugMsg(scip, "no unprocessed/unfiltered bound left\n");
1794  return SCIP_OKAY;
1795  }
1796 
1797  currbound = propdata->bounds[nextboundidx];
1798  assert(!currbound->done && !currbound->filtered);
1799 
1800  /* main loop */
1801  while( iterationsleft && !SCIPisStopped(scip) )
1802  {
1803  SCIP_Bool optimal;
1804  SCIP_Bool error;
1805  int nfiltered;
1806 
1807  assert(currbound != NULL);
1808  assert(currbound->done == FALSE);
1809  assert(currbound->filtered == FALSE);
1810 
1811  /* do not visit currbound more than once */
1812  currbound->done = TRUE;
1813  exchangeBounds(propdata, nextboundidx);
1814 
1815  /* set objective for curr */
1816  SCIP_CALL( setObjProbing(scip, propdata, currbound, 1.0) );
1817 
1818  SCIPdebugMsg(scip, "before solving Boundtype: %d , LB: %e , UB: %e\n",
1819  currbound->boundtype == SCIP_BOUNDTYPE_LOWER, SCIPvarGetLbLocal(currbound->var),
1820  SCIPvarGetUbLocal(currbound->var) );
1821  SCIPdebugMsg(scip, "before solving var <%s>, LP value: %f\n",
1822  SCIPvarGetName(currbound->var), SCIPvarGetLPSol(currbound->var));
1823 
1824  SCIPdebugMsg(scip, "probing iterations before solve: %lld \n", SCIPgetNLPIterations(scip));
1825 
1826  propdata->nprobingiterations -= SCIPgetNLPIterations(scip);
1827 
1828  /* now solve the LP */
1829  SCIP_CALL( solveLP(scip, (int) *nleftiterations, &error, &optimal) );
1830 
1831  propdata->nprobingiterations += SCIPgetNLPIterations(scip);
1832  propdata->nsolvedbounds++;
1833 
1834  SCIPdebugMsg(scip, "probing iterations after solve: %lld \n", SCIPgetNLPIterations(scip));
1835  SCIPdebugMsg(scip, "OPT: %u ERROR: %u\n" , optimal, error);
1836  SCIPdebugMsg(scip, "after solving Boundtype: %d , LB: %e , UB: %e\n",
1837  currbound->boundtype == SCIP_BOUNDTYPE_LOWER, SCIPvarGetLbLocal(currbound->var),
1838  SCIPvarGetUbLocal(currbound->var) );
1839  SCIPdebugMsg(scip, "after solving var <%s>, LP value: %f\n",
1840  SCIPvarGetName(currbound->var), SCIPvarGetLPSol(currbound->var));
1841 
1842  /* update nleftiterations */
1843  *nleftiterations = getIterationsLeft(scip, nolditerations, itlimit);
1844  iterationsleft = (*nleftiterations == -1) || (*nleftiterations > 0);
1845 
1846  if( error )
1847  {
1848  SCIPdebugMsg(scip, "ERROR during LP solving\n");
1849 
1850  /* set the objective of currbound to zero to null the whole objective; otherwise the objective is wrong when
1851  * we call findNewBounds() for the convex phase
1852  */
1853  SCIP_CALL( SCIPchgVarObjProbing(scip, currbound->var, 0.0) );
1854 
1855  return SCIP_OKAY;
1856  }
1857 
1858  if( optimal )
1859  {
1860  SCIP_Bool success;
1861 
1862  currbound->newval = SCIPvarGetLPSol(currbound->var);
1863  currbound->found = TRUE;
1864 
1865  /* in root node we may want to create a genvbound (independent of tightening success) */
1866  if( (SCIPgetDepth(scip) == 0 || (SCIPinProbing(scip) && SCIPgetDepth(scip) == 1))
1867  && propdata->genvboundprop != NULL )
1868  {
1869  SCIP_Bool found;
1870 
1871  SCIP_CALL( createGenVBound(scip, propdata, currbound, &found) );
1872 
1873  if( found )
1874  propdata->ngenvboundsprobing += 1;
1875  }
1876 
1877  /* try to tighten bound in probing mode */
1878  success = FALSE;
1879  if( propdata->tightintboundsprobing && SCIPvarIsIntegral(currbound->var) )
1880  {
1881  SCIPdebugMsg(scip, "tightening bound %s = %e bounds: [%e, %e]\n", SCIPvarGetName(currbound->var),
1882  currbound->newval, SCIPvarGetLbLocal(currbound->var), SCIPvarGetUbLocal(currbound->var) );
1883  SCIP_CALL( tightenBoundProbing(scip, currbound, currbound->newval, &success) );
1884  SCIPdebugMsg(scip, "tightening bound %s\n", success ? "successful" : "not successful");
1885  }
1886  else if( propdata->tightcontboundsprobing && !SCIPvarIsIntegral(currbound->var) )
1887  {
1888  SCIPdebugMsg(scip, "tightening bound %s = %e bounds: [%e, %e]\n", SCIPvarGetName(currbound->var),
1889  currbound->newval, SCIPvarGetLbLocal(currbound->var), SCIPvarGetUbLocal(currbound->var) );
1890  SCIP_CALL( tightenBoundProbing(scip, currbound, currbound->newval, &success) );
1891  SCIPdebugMsg(scip, "tightening bound %s\n", success ? "successful" : "not successful");
1892  }
1893 
1894  /* separate current OBBT LP solution */
1895  if( iterationsleft && propdata->separatesol )
1896  {
1897  propdata->nprobingiterations -= SCIPgetNLPIterations(scip);
1898  SCIP_CALL( applySeparation(scip, propdata, currbound, nleftiterations, &success) );
1899  propdata->nprobingiterations += SCIPgetNLPIterations(scip);
1900 
1901  /* remember best solution value after solving additional separations LPs */
1902  if( success )
1903  {
1904 #ifndef NDEBUG
1905  SCIP_Real newval = SCIPvarGetLPSol(currbound->var);
1906 
1907  /* round new bound if the variable is integral */
1908  if( SCIPvarIsIntegral(currbound->var) )
1909  newval = currbound->boundtype == SCIP_BOUNDTYPE_LOWER ?
1910  SCIPceil(scip, newval) : SCIPfloor(scip, newval);
1911 
1912  assert((currbound->boundtype == SCIP_BOUNDTYPE_LOWER &&
1913  SCIPisGT(scip, newval, currbound->newval))
1914  || (currbound->boundtype == SCIP_BOUNDTYPE_UPPER &&
1915  SCIPisLT(scip, newval, currbound->newval)));
1916 #endif
1917 
1918  currbound->newval = SCIPvarGetLPSol(currbound->var);
1919  }
1920  }
1921 
1922  /* filter bound candidates by using the current LP solution */
1923  if( propdata->applytrivialfilter )
1924  {
1925  SCIP_CALL( filterExistingLP(scip, propdata, &nfiltered, currbound) );
1926  SCIPdebugMsg(scip, "filtered %d bounds via inspecting present LP solution\n", nfiltered);
1927  propdata->ntrivialfiltered += nfiltered;
1928  }
1929 
1930  propdata->propagatecounter += success ? 1 : 0;
1931 
1932  /* propagate if we have found enough bound tightenings */
1933  if( propdata->propagatefreq != 0 && propdata->propagatecounter >= propdata->propagatefreq )
1934  {
1935  SCIP_Longint ndomredsfound;
1936  SCIP_Bool cutoff;
1937 
1938  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, &ndomredsfound) );
1939  SCIPdebugMsg(scip, "propagation - cutoff %u ndomreds %" SCIP_LONGINT_FORMAT "\n", cutoff, ndomredsfound);
1940 
1941  propdata->npropagatedomreds += ndomredsfound;
1942  propdata->propagatecounter = 0;
1943  }
1944  }
1945 
1946  /* set objective to zero */
1947  SCIP_CALL( setObjProbing(scip, propdata, currbound, 0.0) );
1948 
1949  /* find the first unprocessed bound */
1950  nextboundidx = nextBound(scip, propdata, convexphase);
1951 
1952  /* check if there is no unprocessed and unfiltered node left */
1953  if( nextboundidx == -1 )
1954  {
1955  SCIPdebugMsg(scip, "NO unvisited/unfiltered bound left!\n");
1956  break;
1957  }
1958 
1959  currbound = propdata->bounds[nextboundidx];
1960  assert(!currbound->done && !currbound->filtered);
1961  }
1962 
1963  if( iterationsleft )
1964  {
1965  SCIPdebugMsg(scip, "still iterations left: %" SCIP_LONGINT_FORMAT "\n", *nleftiterations);
1966  }
1967  else
1968  {
1969  SCIPdebugMsg(scip, "no iterations left\n");
1970  }
1971 
1972  return SCIP_OKAY;
1973 }
1974 
1975 
1976 /** main function of obbt */
1977 static
1979  SCIP* scip, /**< SCIP data structure */
1980  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
1981  SCIP_Longint itlimit, /**< LP iteration limit (-1: no limit) */
1982  SCIP_RESULT* result /**< result pointer */
1983  )
1984 {
1985  SCIP_VAR** vars;
1986  SCIP_Real* oldlbs;
1987  SCIP_Real* oldubs;
1988  SCIP_Longint lastnpropagatedomreds;
1989  SCIP_Longint nleftiterations;
1990  SCIP_Real oldconditionlimit;
1991  SCIP_Real oldboundstreps;
1992  SCIP_Real olddualfeastol;
1993  SCIP_Bool hasconditionlimit;
1994  SCIP_Bool continuenode;
1995  SCIP_Bool boundleft;
1996  int oldpolishing;
1997  int nfiltered;
1998  int nvars;
1999  int i;
2000 
2001  assert(scip != NULL);
2002  assert(propdata != NULL);
2003  assert(itlimit == -1 || itlimit >= 0);
2004 
2005  SCIPdebugMsg(scip, "apply obbt\n");
2006 
2007  oldlbs = NULL;
2008  oldubs = NULL;
2009  lastnpropagatedomreds = propdata->npropagatedomreds;
2010  nleftiterations = itlimit;
2011  continuenode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) == propdata->lastnode;
2012  propdata->lastidx = -1;
2013  boundleft = FALSE;
2014  *result = SCIP_DIDNOTFIND;
2015 
2016  /* store old variable bounds if we use propagation during obbt */
2017  if( propdata->propagatefreq > 0 )
2018  {
2019  SCIP_CALL( SCIPallocBufferArray(scip, &oldlbs, propdata->nbounds) );
2020  SCIP_CALL( SCIPallocBufferArray(scip, &oldubs, propdata->nbounds) );
2021  }
2022 
2023  /* reset bound data structure flags; fixed variables are marked as filtered */
2024  for( i = 0; i < propdata->nbounds; i++ )
2025  {
2026  BOUND* bound = propdata->bounds[i];
2027  bound->found = FALSE;
2028 
2029  /* store old variable bounds */
2030  if( oldlbs != NULL && oldubs != NULL )
2031  {
2032  oldlbs[bound->index] = SCIPvarGetLbLocal(bound->var);
2033  oldubs[bound->index] = SCIPvarGetUbLocal(bound->var);
2034  }
2035 
2036  /* reset 'done' and 'filtered' flag in a new B&B node */
2037  if( !continuenode )
2038  {
2039  bound->done = FALSE;
2040  bound->filtered = FALSE;
2041  }
2042 
2043  /* mark fixed variables as filtered */
2044  bound->filtered |= varIsFixedLocal(scip, bound->var);
2045 
2046  /* check for an unprocessed bound */
2047  if( !bound->filtered && !bound->done )
2048  boundleft = TRUE;
2049  }
2050 
2051  /* no bound left to check */
2052  if( !boundleft )
2053  goto TERMINATE;
2054 
2055  /* filter variables via inspecting present LP solution */
2056  if( propdata->applytrivialfilter && !continuenode )
2057  {
2058  SCIP_CALL( filterExistingLP(scip, propdata, &nfiltered, NULL) );
2059  SCIPdebugMsg(scip, "filtered %d bounds via inspecting present LP solution\n", nfiltered);
2060  propdata->ntrivialfiltered += nfiltered;
2061  }
2062 
2063  /* store old dualfeasibletol */
2064  olddualfeastol = SCIPdualfeastol(scip);
2065 
2066  /* start probing */
2067  SCIP_CALL( SCIPstartProbing(scip) );
2068  SCIPdebugMsg(scip, "start probing\n");
2069 
2070  /* tighten dual feastol */
2071  if( propdata->dualfeastol < olddualfeastol )
2072  {
2073  SCIP_CALL( SCIPchgDualfeastol(scip, propdata->dualfeastol) );
2074  }
2075 
2076  /* tighten condition limit */
2077  hasconditionlimit = (SCIPgetRealParam(scip, "lp/conditionlimit", &oldconditionlimit) == SCIP_OKAY);
2078  if( !hasconditionlimit )
2079  {
2080  SCIPwarningMessage(scip, "obbt propagator could not set condition limit in LP solver - running without\n");
2081  }
2082  else if( propdata->conditionlimit > 0.0 && (oldconditionlimit < 0.0 || propdata->conditionlimit < oldconditionlimit) )
2083  {
2084  SCIP_CALL( SCIPsetRealParam(scip, "lp/conditionlimit", propdata->conditionlimit) );
2085  }
2086 
2087  /* tighten relative bound improvement limit */
2088  SCIP_CALL( SCIPgetRealParam(scip, "numerics/boundstreps", &oldboundstreps) );
2089  if( !SCIPisEQ(scip, oldboundstreps, propdata->boundstreps) )
2090  {
2091  SCIP_CALL( SCIPsetRealParam(scip, "numerics/boundstreps", propdata->boundstreps) );
2092  }
2093 
2094  /* add objective cutoff */
2095  SCIP_CALL( addObjCutoff(scip, propdata) );
2096 
2097  /* deactivate LP polishing */
2098  SCIP_CALL( SCIPgetIntParam(scip, "lp/solutionpolishing", &oldpolishing) );
2099  SCIP_CALL( SCIPsetIntParam(scip, "lp/solutionpolishing", 0) );
2100 
2101  /* apply filtering */
2102  if( propdata->applyfilterrounds )
2103  {
2104  SCIP_CALL( filterBounds(scip, propdata, nleftiterations) );
2105  }
2106 
2107  /* set objective coefficients to zero */
2108  vars = SCIPgetVars(scip);
2109  nvars = SCIPgetNVars(scip);
2110  for( i = 0; i < nvars; ++i )
2111  {
2112  /* note that it is not possible to change the objective of non-column variables during probing; we have to take
2113  * care of the objective contribution of loose variables in createGenVBound()
2114  */
2115  if( SCIPvarGetObj(vars[i]) != 0.0 && SCIPvarGetStatus(vars[i]) == SCIP_VARSTATUS_COLUMN )
2116  {
2117  SCIP_CALL( SCIPchgVarObjProbing(scip, vars[i], 0.0) );
2118  }
2119  }
2120 
2121  /* find new bounds for the variables */
2122  SCIP_CALL( findNewBounds(scip, propdata, &nleftiterations, FALSE) );
2123 
2124  if( nleftiterations > 0 || itlimit < 0 )
2125  {
2126  SCIP_CALL( findNewBounds(scip, propdata, &nleftiterations, TRUE) );
2127  }
2128 
2129  /* reset dual feastol and condition limit */
2130  SCIP_CALL( SCIPchgDualfeastol(scip, olddualfeastol) );
2131  if( hasconditionlimit )
2132  {
2133  SCIP_CALL( SCIPsetRealParam(scip, "lp/conditionlimit", oldconditionlimit) );
2134  }
2135 
2136  /* update bound->newval if we have learned additional bound tightenings during SCIPpropagateProbing() */
2137  if( oldlbs != NULL && oldubs != NULL && propdata->npropagatedomreds - lastnpropagatedomreds > 0 )
2138  {
2139  assert(propdata->propagatefreq > 0);
2140  for( i = 0; i < propdata->nbounds; ++i )
2141  {
2142  BOUND* bound = propdata->bounds[i];
2143 
2144  /* it might be the case that a bound found by the additional propagation is better than the bound found after solving an OBBT
2145  * LP
2146  */
2147  if( bound->found )
2148  {
2149  if( bound->boundtype == SCIP_BOUNDTYPE_LOWER )
2150  bound->newval = MAX(bound->newval, SCIPvarGetLbLocal(bound->var)); /*lint !e666*/
2151  else
2152  bound->newval = MIN(bound->newval, SCIPvarGetUbLocal(bound->var)); /*lint !e666*/
2153  }
2154  else
2155  {
2156  SCIP_Real oldlb;
2157  SCIP_Real oldub;
2158 
2159  oldlb = oldlbs[bound->index];
2160  oldub = oldubs[bound->index];
2161 
2162  if( bound->boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisLbBetter(scip, SCIPvarGetLbLocal(bound->var), oldlb, oldub) )
2163  {
2164  SCIPdebugMsg(scip, "tighter lower bound due to propagation: %d - %e -> %e\n", i, oldlb, SCIPvarGetLbLocal(bound->var));
2165  bound->newval = SCIPvarGetLbLocal(bound->var);
2166  bound->found = TRUE;
2167  }
2168 
2169  if( bound->boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisUbBetter(scip, SCIPvarGetUbLocal(bound->var), oldlb, oldub) )
2170  {
2171  SCIPdebugMsg(scip, "tighter upper bound due to propagation: %d - %e -> %e\n", i, oldub, SCIPvarGetUbLocal(bound->var));
2172  bound->newval = SCIPvarGetUbLocal(bound->var);
2173  bound->found = TRUE;
2174  }
2175  }
2176  }
2177  }
2178 
2179  /* reset relative bound improvement limit */
2180  SCIP_CALL( SCIPsetRealParam(scip, "numerics/boundstreps", oldboundstreps) );
2181 
2182  /* reset original LP polishing setting */
2183  SCIP_CALL( SCIPsetIntParam(scip, "lp/solutionpolishing", oldpolishing) );
2184 
2185  /* end probing */
2186  SCIP_CALL( SCIPendProbing(scip) );
2187  SCIPdebugMsg(scip, "end probing!\n");
2188 
2189  /* release cutoff row if there is one */
2190  if( propdata->cutoffrow != NULL )
2191  {
2192  assert(!SCIProwIsInLP(propdata->cutoffrow));
2193  SCIP_CALL( SCIPreleaseRow(scip, &(propdata->cutoffrow)) );
2194  }
2195 
2196  /* apply buffered bound changes */
2197  SCIP_CALL( applyBoundChgs(scip, propdata, result) );
2198 
2199 TERMINATE:
2200  SCIPfreeBufferArrayNull(scip, &oldubs);
2201  SCIPfreeBufferArrayNull(scip, &oldlbs);
2202 
2203  return SCIP_OKAY;
2204 }
2205 
2206 /** computes a valid inequality from the current LP relaxation for a bilinear term xy only involving x and y; the
2207  * inequality is found by optimizing along the line connecting the points (xs,ys) and (xt,yt) over the currently given
2208  * linear relaxation of the problem; this optimization problem is an LP
2209  *
2210  * max lambda
2211  * s.t. Ax <= b
2212  * (x,y) = (xs,ys) + lambda ((xt,yt) - (xs,ys))
2213  * lambda in [0,1]
2214  *
2215  * which is equivalent to
2216  *
2217  * max x
2218  * s.t. (1) Ax <= b
2219  * (2) (x - xs) / (xt - xs) = (y - ys) / (yt - ys)
2220  *
2221  * Let x* be the optimal primal and (mu,theta) be the optimal dual solution of this LP. The KKT conditions imply that
2222  * the aggregation of the linear constraints mu*Ax <= mu*b can be written as
2223  *
2224  * x * (1 - theta) / (xt - xs) + y * theta / (yt - ys) = mu * Ax <= mu * b
2225  *
2226  * <=> alpha * x + beta * y <= mu * b = alpha * (x*) + beta * (y*)
2227  *
2228  * which is a valid inequality in the (x,y)-space; in order to avoid numerical difficulties when (xs,ys) is too close
2229  * to (xt,yt), we scale constraint (1) by max{1,|xt-xs|,|yt-ys|} beforehand
2230  */
2231 static
2233  SCIP* scip, /**< SCIP data structure */
2234  SCIP_VAR* x, /**< first variable */
2235  SCIP_VAR* y, /**< second variable */
2236  SCIP_Real xs, /**< x-coordinate of the first point */
2237  SCIP_Real ys, /**< y-coordinate of the first point */
2238  SCIP_Real xt, /**< x-coordinate of the second point */
2239  SCIP_Real yt, /**< y-coordinate of the second point */
2240  SCIP_Real* xcoef, /**< pointer to store the coefficient of x */
2241  SCIP_Real* ycoef, /**< pointer to store the coefficient of y */
2242  SCIP_Real* constant, /**< pointer to store the constant */
2243  SCIP_Longint iterlim, /**< iteration limit (-1: for no limit) */
2244  int* nnonzduals /**< buffer to store the number of non-zero dual multipliers except for
2245  * the auxiliary row (NULL if not needed) */
2246  )
2247 {
2248  SCIP_ROW* row;
2249  SCIP_Real signx;
2250  SCIP_Real scale;
2251  SCIP_Real side;
2252  SCIP_Bool lperror;
2253 
2254  assert(xcoef != NULL);
2255  assert(ycoef != NULL);
2256  assert(constant != NULL);
2257  assert(SCIPinProbing(scip));
2258 
2259  *xcoef = SCIP_INVALID;
2260  *ycoef = SCIP_INVALID;
2261  *constant= SCIP_INVALID;
2262  if( nnonzduals != NULL )
2263  *nnonzduals = 0;
2264 
2265  SCIPdebugMsg(scip, " solve bilinear LP for (%s,%s) from (%g,%g) to (%g,%g)\n", SCIPvarGetName(x), SCIPvarGetName(y), xs,
2266  ys, xt, yt);
2267 
2268  /* skip computations if (xs,ys) and (xt,yt) are too close to each other or contain too large values */
2269  if( SCIPisFeasEQ(scip, xs, xt) || SCIPisFeasEQ(scip, ys, yt)
2270  || SCIPisHugeValue(scip, REALABS(xs)) || SCIPisHugeValue(scip, REALABS(xt))
2271  || SCIPisHugeValue(scip, REALABS(ys)) || SCIPisHugeValue(scip, REALABS(yt)) )
2272  {
2273  SCIPdebugMsg(scip, " -> skip: bounds are too close/large\n");
2274  return SCIP_OKAY;
2275  }
2276 
2277  /* compute scaler for the additional linear constraint */
2278  scale = MIN(MAX3(1.0, REALABS(xt-xs), REALABS(yt-ys)), 100.0); /*lint !e666*/
2279 
2280  /* set objective function */
2281  signx = (xs > xt) ? 1.0 : -1.0;
2282  SCIP_CALL( SCIPchgVarObjProbing(scip, x, signx) );
2283 
2284  /* create new probing node to remove the added LP row afterwards */
2285  SCIP_CALL( SCIPnewProbingNode(scip) );
2286 
2287  /* create row */
2288  side = scale * (xs/(xt-xs) - ys/(yt-ys));
2289  SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, "bilinrow", side, side, FALSE, FALSE, TRUE) );
2290  SCIP_CALL( SCIPaddVarToRow(scip, row, x, scale/(xt-xs)) );
2291  SCIP_CALL( SCIPaddVarToRow(scip, row, y, -scale/(yt-ys)) );
2292  SCIP_CALL( SCIPaddRowProbing(scip, row) );
2293 
2294  /* solve probing LP */
2295 #ifdef NDEBUG
2296  {
2297  SCIP_RETCODE retstat;
2298  retstat = SCIPsolveProbingLP(scip, iterlim, &lperror, NULL);
2299  if( retstat != SCIP_OKAY )
2300  {
2301  SCIPwarningMessage(scip, "Error while solving LP in quadratic constraint handler; LP solve terminated with" \
2302  "code <%d>\n", retstat);
2303  }
2304  }
2305 #else
2306  SCIP_CALL( SCIPsolveProbingLP(scip, (int)iterlim, &lperror, NULL) ); /*lint !e712*/
2307 #endif
2308 
2309  SCIPdebugMsg(scip, " solved probing LP -> lperror=%u lpstat=%d\n", lperror, SCIPgetLPSolstat(scip));
2310 
2311  /* collect dual and primal solution entries */
2312  if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
2313  {
2314  SCIP_Real xval = SCIPvarGetLPSol(x);
2315  SCIP_Real yval = SCIPvarGetLPSol(y);
2316  SCIP_Real mu = -SCIProwGetDualsol(row);
2317 
2318  SCIPdebugMsg(scip, " primal=(%g,%g) dual=%g\n", xval, yval, mu);
2319 
2320  /* xcoef x + ycoef y <= constant */
2321  *xcoef = -signx - (mu * scale) / (xt - xs);
2322  *ycoef = (mu * scale) / (yt - ys);
2323  *constant = (*xcoef) * xval + (*ycoef) * yval;
2324 
2325  /* xcoef x <= -ycoef y + constant */
2326  *ycoef = -(*ycoef);
2327 
2328  /* inequality is only useful when both coefficients are different from zero; normalize inequality if possible */
2329  if( !SCIPisFeasZero(scip, *xcoef) && !SCIPisFeasZero(scip, *ycoef) )
2330  {
2331  SCIP_Real val = REALABS(*xcoef);
2332  int r;
2333 
2334  *xcoef /= val;
2335  *ycoef /= val;
2336  *constant /= val;
2337 
2338  if( SCIPisZero(scip, *constant) )
2339  *constant = 0.0;
2340 
2341  if( nnonzduals != NULL )
2342  {
2343  /* count the number of non-zero dual multipliers except for the added row */
2344  for( r = 0; r < SCIPgetNLPRows(scip); ++r )
2345  {
2346  if( SCIPgetLPRows(scip)[r] != row && !SCIPisFeasZero(scip, SCIProwGetDualsol(SCIPgetLPRows(scip)[r])) )
2347  ++(*nnonzduals);
2348  }
2349  }
2350  }
2351  else
2352  {
2353  *xcoef = SCIP_INVALID;
2354  *ycoef = SCIP_INVALID;
2355  *constant = SCIP_INVALID;
2356  }
2357  }
2358 
2359  /* release row and backtrack probing node */
2360  SCIP_CALL( SCIPreleaseRow(scip, &row) );
2361  SCIP_CALL( SCIPbacktrackProbing(scip, 0) );
2362 
2363  /* reset objective function */
2364  SCIP_CALL( SCIPchgVarObjProbing(scip, x, 0.0) );
2365 
2366  return SCIP_OKAY;
2367 }
2368 
2369 /* applies obbt for finding valid inequalities for bilinear terms; function works as follows:
2370  *
2371  * 1. start probing mode
2372  * 2. add objective cutoff (if possible)
2373  * 3. set objective function to zero
2374  * 4. set feasibility, optimality, and relative bound improvement tolerances of SCIP
2375  * 5. main loop
2376  * 6. restore old tolerances
2377  *
2378  */
2379 static
2381  SCIP* scip, /**< SCIP data structure */
2382  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
2383  SCIP_Longint itlimit, /**< LP iteration limit (-1: no limit) */
2384  SCIP_RESULT* result /**< result pointer */
2385  )
2386 {
2387  SCIP_VAR** vars;
2388  SCIP_Real oldfeastol;
2389  SCIP_Bool lperror;
2390  SCIP_Longint nolditerations;
2391  SCIP_Longint nleftiterations;
2392  SCIP_CONSHDLR* conshdlr;
2393  SCIP_NLHDLR* bilinearnlhdlr;
2394  int nvars;
2395  int i;
2396 
2397  assert(scip != NULL);
2398  assert(propdata != NULL);
2399  assert(itlimit == -1 || itlimit >= 0);
2400  assert(result != NULL);
2401 
2402  if( propdata->nbilinbounds <= 0 || SCIPgetDepth(scip) != 0 || propdata->lastbilinidx >= propdata->nbilinbounds )
2403  return SCIP_OKAY;
2404 
2405  SCIPdebugMsg(scip, "call applyObbtBilinear starting from %d\n", propdata->lastbilinidx);
2406 
2407  /* find nonlinear handler for bilinear terms */
2408  conshdlr = SCIPfindConshdlr(scip, "nonlinear");
2409  bilinearnlhdlr = conshdlr != NULL ? SCIPfindNlhdlrNonlinear(conshdlr, "bilinear") : NULL;
2410 
2411  /* no nonlinear handler available -> skip */
2412  if( bilinearnlhdlr == NULL )
2413  return SCIP_OKAY;
2414 
2415  vars = SCIPgetVars(scip);
2416  nvars = SCIPgetNVars(scip);
2417 
2418  nolditerations = SCIPgetNLPIterations(scip);
2419  nleftiterations = getIterationsLeft(scip, nolditerations, itlimit);
2420  SCIPdebugMsg(scip, "iteration limit: %lld\n", nleftiterations);
2421 
2422  /* 1. start probing */
2423  SCIP_CALL( SCIPstartProbing(scip) );
2424 
2425  /* 2. add objective cutoff */
2426  SCIP_CALL( addObjCutoff(scip, propdata) );
2427 
2428  /* 3. set objective function to zero */
2429  for( i = 0; i < nvars; ++i )
2430  {
2431  SCIP_CALL( SCIPchgVarObjProbing(scip, vars[i], 0.0) );
2432  }
2433 
2434  /* 4. tighten LP feasibility tolerance to be at most feastol/10.0 */
2435  oldfeastol = SCIPchgRelaxfeastol(scip, SCIPfeastol(scip) / 10.0);
2436 
2437  /* we need to solve the probing LP before creating new probing nodes in solveBilinearLP() */
2438  SCIP_CALL( SCIPsolveProbingLP(scip, (int)nleftiterations, &lperror, NULL) );
2439 
2440  if( lperror )
2441  goto TERMINATE;
2442 
2443  /* 5. main loop */
2444  for( i = propdata->lastbilinidx; i < propdata->nbilinbounds
2445  && (nleftiterations > 0 || nleftiterations == -1)
2446  && (propdata->itlimitbilin < 0 || propdata->itlimitbilin > propdata->itusedbilin )
2447  && !SCIPisStopped(scip); ++i )
2448  {
2449  CORNER corners[4] = {LEFTBOTTOM, LEFTTOP, RIGHTTOP, RIGHTBOTTOM};
2450  BILINBOUND* bilinbound;
2451  int k;
2452 
2453  bilinbound = propdata->bilinbounds[i];
2454  assert(bilinbound != NULL);
2455 
2456  SCIPdebugMsg(scip, "process %d: %s %s done=%u filtered=%d nunderest=%d noverest=%d\n", i,
2457  SCIPvarGetName(bilinboundGetX(bilinbound)), SCIPvarGetName(bilinboundGetY(bilinbound)), bilinbound->done,
2458  bilinbound->filtered, bilinboundGetLocksNeg(bilinbound), bilinboundGetLocksPos(bilinbound));
2459 
2460  /* we already solved LPs for this bilinear term */
2461  if( bilinbound->done || bilinbound->filtered == (int)FILTERED )
2462  continue;
2463 
2464  /* iterate through all corners
2465  *
2466  * 0: (xs,ys)=(ubx,lby) (xt,yt)=(lbx,uby) -> underestimate
2467  * 1: (xs,ys)=(ubx,uby) (xt,yt)=(lbx,lby) -> overestimate
2468  * 2: (xs,ys)=(lbx,uby) (xt,yt)=(ubx,lby) -> underestimate
2469  * 3: (xs,ys)=(lbx,lby) (xt,yt)=(ubx,uby) -> overestimate
2470  */
2471  for( k = 0; k < 4; ++k )
2472  {
2473  CORNER corner = corners[k];
2474  SCIP_VAR* x = bilinboundGetX(bilinbound);
2475  SCIP_VAR* y = bilinboundGetY(bilinbound);
2476  SCIP_Real xcoef;
2477  SCIP_Real ycoef;
2478  SCIP_Real constant;
2479  SCIP_Real xs = SCIP_INVALID;
2480  SCIP_Real ys = SCIP_INVALID;
2481  SCIP_Real xt = SCIP_INVALID;
2482  SCIP_Real yt = SCIP_INVALID;
2483  int nnonzduals = 0;
2484 
2485  /* skip corners that lead to an under- or overestimate that is not needed */
2486  if( ((corner == LEFTTOP || corner == RIGHTBOTTOM) && bilinboundGetLocksPos(bilinbound) == 0)
2487  || ((corner == LEFTBOTTOM || corner == RIGHTTOP) && bilinboundGetLocksNeg(bilinbound) == 0) )
2488  continue;
2489 
2490  /* check whether corner has been filtered already */
2491  if( (bilinbound->filtered & corner) != 0 ) /*lint !e641*/
2492  continue;
2493 
2494  /* get corners (xs,ys) and (xt,yt) */
2495  getCorners(x, y, corner, &xs, &ys, &xt, &yt);
2496 
2497  /* skip target corner points with too large values */
2498  if( SCIPisHugeValue(scip, REALABS(xt)) || SCIPisHugeValue(scip, REALABS(yt)) )
2499  continue;
2500 
2501  /* compute inequality */
2502  propdata->itusedbilin -= SCIPgetNLPIterations(scip);
2503  SCIP_CALL( solveBilinearLP(scip, x, y, xs, ys, xt, yt, &xcoef, &ycoef, &constant, -1L,
2504  propdata->createlincons ? &nnonzduals : NULL) ); /*lint !e826*/
2505  propdata->itusedbilin += SCIPgetNLPIterations(scip);
2506 
2507  /* update number of LP iterations */
2508  nleftiterations = getIterationsLeft(scip, nolditerations, itlimit);
2509  SCIPdebugMsg(scip, "LP iterations left: %lld\n", nleftiterations);
2510 
2511  /* add inequality to quadratic constraint handler if it separates (xt,yt) */
2512  if( !SCIPisHugeValue(scip, xcoef) && !SCIPisFeasZero(scip, xcoef)
2513  && REALABS(ycoef) < 1e+3 && REALABS(ycoef) > 1e-3 /* TODO add a parameter for this */
2514  && SCIPisFeasGT(scip, (xcoef*xt - ycoef*yt - constant) / SQRT(SQR(xcoef) + SQR(ycoef) + SQR(constant)), 1e-2) )
2515  {
2516  SCIP_Bool success;
2517 
2518  /* add inequality to the associated product expression */
2519  SCIP_CALL( SCIPaddIneqBilinear(scip, bilinearnlhdlr, bilinbound->expr, xcoef, ycoef,
2520  constant, &success) );
2521 
2522  /* check whether the inequality has been accepted */
2523  if( success )
2524  {
2525  *result = SCIP_REDUCEDDOM;
2526  SCIPdebugMsg(scip, " found %g x <= %g y + %g with violation %g\n", xcoef, ycoef, constant,
2527  (xcoef*xt - ycoef*yt - constant) / SQRT(SQR(xcoef) + SQR(ycoef) + SQR(constant)));
2528 
2529  /* create a linear constraint that is only used for propagation */
2530  if( propdata->createlincons && nnonzduals > 1 )
2531  {
2532  SCIP_CONS* cons;
2533  char name[SCIP_MAXSTRLEN];
2534  SCIP_VAR* linvars[2] = {x, y};
2535  SCIP_Real linvals[2] = {xcoef, -ycoef};
2536  SCIP_Real rhs = constant;
2537 
2538  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "bilincons_%s_%s", SCIPvarGetName(x), SCIPvarGetName(y));
2539  SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, 2, linvars, linvals, -SCIPinfinity(scip), rhs,
2541 
2542  SCIP_CALL( SCIPaddCons(scip, cons) );
2543  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2544  }
2545  }
2546  }
2547  }
2548 
2549  /* mark the bound as processed */
2550  bilinbound->done = TRUE;
2551  }
2552 
2553  /* remember last unprocessed bilinear term */
2554  propdata->lastbilinidx = i;
2555 
2556  TERMINATE:
2557  /* end probing */
2558  SCIP_CALL( SCIPendProbing(scip) );
2559 
2560  /* release cutoff row if there is one */
2561  if( propdata->cutoffrow != NULL )
2562  {
2563  assert(!SCIProwIsInLP(propdata->cutoffrow));
2564  SCIP_CALL( SCIPreleaseRow(scip, &(propdata->cutoffrow)) );
2565  }
2566 
2567  /* 6. restore old tolerance */
2568  (void) SCIPchgRelaxfeastol(scip, oldfeastol);
2569 
2570  return SCIP_OKAY;
2571 }
2572 
2573 /** computes the score of a bound */
2574 static
2575 unsigned int getScore(
2576  SCIP* scip, /**< SCIP data structure */
2577  BOUND* bound, /**< pointer of bound */
2578  int nlcount, /**< number of nonlinear constraints containing the bounds variable */
2579  int maxnlcount /**< maximal number of nonlinear constraints a variable appears in */
2580  )
2581 {
2582  unsigned int score; /* score to be computed */
2583 
2584  assert(scip != NULL);
2585  assert(bound != NULL);
2586  assert(nlcount >= 0);
2587  assert(maxnlcount >= nlcount);
2588 
2589  /* score = ( nlcount * ( BASE - 1 ) / maxnlcount ) * BASE^2 + vartype * BASE + boundtype */
2590  score = (unsigned int) ( nlcount > 0 ? (OBBT_SCOREBASE * nlcount * ( OBBT_SCOREBASE - 1 )) / maxnlcount : 0 ); /*lint !e414*/
2591  switch( SCIPvarGetType(bound->var) )
2592  {
2593  case SCIP_VARTYPE_INTEGER:
2594  score += 1;
2595  break;
2596  case SCIP_VARTYPE_IMPLINT:
2597  score += 2;
2598  break;
2600  score += 3;
2601  break;
2602  case SCIP_VARTYPE_BINARY:
2603  score += 4;
2604  break;
2605  default:
2606  break;
2607  }
2608 
2609  score *= OBBT_SCOREBASE;
2610  if( bound->boundtype == SCIP_BOUNDTYPE_UPPER )
2611  score += 1;
2612 
2613  return score;
2614 }
2615 
2616 /** count how often each variable is used in a nonconvex term */
2617 static
2619  SCIP* scip, /**< SCIP data structure */
2620  unsigned int* nccounts /**< store the number each variable appears in a
2621  * non-convex term */
2622  )
2623 {
2624  SCIP_CONSHDLR* conshdlr;
2625  SCIP_HASHMAP* var2expr;
2626  int nvars;
2627  int i;
2628 
2629  assert(scip != NULL);
2630  assert(nccounts != NULL);
2631 
2632  nvars = SCIPgetNVars(scip);
2633 
2634  /* initialize nccounts to zero */
2635  BMSclearMemoryArray(nccounts, nvars);
2636 
2637  /* get nonlinear constraint handler */
2638  conshdlr = SCIPfindConshdlr(scip, "nonlinear");
2639  if( conshdlr == NULL || SCIPconshdlrGetNConss(conshdlr) == 0 )
2640  return SCIP_OKAY;
2641 
2642  var2expr = SCIPgetVarExprHashmapNonlinear(conshdlr);
2643  assert(var2expr != NULL);
2644 
2645  for( i = 0; i < SCIPgetNVars(scip); ++i )
2646  {
2647  SCIP_VAR* var;
2648 
2649  var = SCIPgetVars(scip)[i];
2650  assert(var != NULL);
2651 
2652  if( SCIPhashmapExists(var2expr, (void*) var) )
2653  {
2654  SCIP_EXPR* expr = (SCIP_EXPR*)SCIPhashmapGetImage(var2expr, (void*) var);
2655  assert(expr != NULL);
2656  assert(SCIPisExprVar(scip, expr));
2657 
2659  }
2660  }
2661 
2662 #ifdef SCIP_DEBUG
2663  for( i = 0; i < SCIPgetNVars(scip); ++i)
2664  {
2665  SCIP_VAR* var = SCIPgetVars(scip)[i];
2666  assert(var != NULL);
2667  SCIPdebugMsg(scip, "nccounts[%s] = %u\n", SCIPvarGetName(var), nccounts[SCIPvarGetProbindex(var)]);
2668  }
2669 #endif
2670 
2671  return SCIP_OKAY;
2672 }
2673 
2674 
2675 /** determines whether a variable is interesting */
2676 static
2678  SCIP* scip, /**< SCIP data structure */
2679  SCIP_VAR* var, /**< variable to check */
2680  int nlcount /**< number of nonlinear constraints containing the variable
2681  * or number of non-convex terms containing the variable
2682  * (depends on propdata->onlynonconvexvars) */
2683  )
2684 {
2685  assert(SCIPgetDepth(scip) == 0);
2686 
2687  return !SCIPvarIsBinary(var) && SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN && nlcount > 0
2688  && !varIsFixedLocal(scip, var);
2690 
2691 /** initializes interesting bounds */
2692 static
2694  SCIP* scip, /**< SCIP data structure */
2695  SCIP_PROPDATA* propdata /**< data of the obbt propagator */
2696  )
2697 {
2698  SCIP_CONSHDLR* conshdlr;
2699  SCIP_VAR** vars; /* array of the problems variables */
2700  int* nlcount; /* array that stores in how many nonlinearities each variable appears */
2701  unsigned int* nccount; /* array that stores in how many nonconvexities each variable appears */
2702 
2703  int bdidx; /* bound index inside propdata->bounds */
2704  int maxnlcount; /* maximal number of nonlinear constraints a variable appears in */
2705  int nvars; /* number of the problems variables */
2706  int i;
2707 
2708  assert(scip != NULL);
2709  assert(propdata != NULL);
2710  assert(SCIPisNLPConstructed(scip));
2711 
2712  SCIPdebugMsg(scip, "initialize bounds\n");
2713 
2714  /* get variable data */
2715  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2716 
2717  /* count nonlinearities */
2718  assert(SCIPgetNNLPVars(scip) == nvars);
2719 
2720  SCIP_CALL( SCIPallocBufferArray(scip, &nlcount, nvars) );
2721  SCIP_CALL( SCIPallocBufferArray(scip, &nccount, nvars) );
2722 
2723  SCIP_CALL( SCIPgetNLPVarsNonlinearity(scip, nlcount) );
2724  SCIP_CALL( getNLPVarsNonConvexity(scip, nccount) );
2725 
2726  maxnlcount = 0;
2727  for( i = 0; i < nvars; i++ )
2728  {
2729  if( maxnlcount < nlcount[i] )
2730  maxnlcount = nlcount[i];
2731  }
2732 
2733  /* allocate interesting bounds array */
2734  propdata->boundssize = 2 * nvars;
2735  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->bounds), 2 * nvars) );
2736 
2737  /* get all interesting variables and their bounds */
2738  bdidx = 0;
2739  for( i = 0; i < nvars; i++ )
2740  {
2741  if( varIsInteresting(scip, vars[i], (propdata->onlynonconvexvars ? (int)nccount[i] : nlcount[i])) )
2742  {
2743  BOUND** bdaddress;
2744 
2745  /* create lower bound */
2746  bdaddress = &(propdata->bounds[bdidx]);
2747  SCIP_CALL( SCIPallocBlockMemory(scip, bdaddress) );
2748  propdata->bounds[bdidx]->boundtype = SCIP_BOUNDTYPE_LOWER;
2749  propdata->bounds[bdidx]->var = vars[i];
2750  propdata->bounds[bdidx]->found = FALSE;
2751  propdata->bounds[bdidx]->filtered = FALSE;
2752  propdata->bounds[bdidx]->newval = 0.0;
2753  propdata->bounds[bdidx]->score = getScore(scip, propdata->bounds[bdidx], nlcount[i], maxnlcount);
2754  propdata->bounds[bdidx]->done = FALSE;
2755  propdata->bounds[bdidx]->nonconvex = (nccount[i] > 0);
2756  propdata->bounds[bdidx]->index = bdidx;
2757  bdidx++;
2758 
2759  /* create upper bound */
2760  bdaddress = &(propdata->bounds[bdidx]);
2761  SCIP_CALL( SCIPallocBlockMemory(scip, bdaddress) );
2762  propdata->bounds[bdidx]->boundtype = SCIP_BOUNDTYPE_UPPER;
2763  propdata->bounds[bdidx]->var = vars[i];
2764  propdata->bounds[bdidx]->found = FALSE;
2765  propdata->bounds[bdidx]->filtered = FALSE;
2766  propdata->bounds[bdidx]->newval = 0.0;
2767  propdata->bounds[bdidx]->score = getScore(scip, propdata->bounds[bdidx], nlcount[i], maxnlcount);
2768  propdata->bounds[bdidx]->done = FALSE;
2769  propdata->bounds[bdidx]->nonconvex = (nccount[i] > 0);
2770  propdata->bounds[bdidx]->index = bdidx;
2771  bdidx++;
2772  }
2773  }
2774 
2775  /* set number of interesting bounds */
2776  propdata->nbounds = bdidx;
2777 
2778  conshdlr = SCIPfindConshdlr(scip, "nonlinear");
2779 
2780  /* get all product expressions from nonlinear constraint handler */
2781  if( propdata->nbounds > 0 && conshdlr != NULL && propdata->createbilinineqs )
2782  {
2783  SCIP_NLHDLR* bilinnlhdlr;
2784  SCIP_EXPR** exprs;
2785  int nexprs;
2786 
2787  /* find nonlinear handler for bilinear terms */
2788  bilinnlhdlr = SCIPfindNlhdlrNonlinear(conshdlr, "bilinear");
2789  assert(bilinnlhdlr != NULL);
2790 
2791  /* collect all bilinear product in all nonlinear constraints */
2792  exprs = SCIPgetExprsBilinear(bilinnlhdlr);
2793  nexprs = SCIPgetNExprsBilinear(bilinnlhdlr);
2794 
2795  if( nexprs > 0 )
2796  {
2797  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->bilinbounds, nexprs) );
2798  propdata->bilinboundssize = nexprs;
2799  propdata->nbilinbounds = 0;
2800 
2801  /* store candidates as bilinear bounds */
2802  for( i = 0; i < nexprs; ++i )
2803  {
2804  BILINBOUND* bilinbound;
2805  SCIP_VAR* x;
2806  SCIP_VAR* y;
2807 
2808  assert(exprs[i] != NULL);
2809  assert(SCIPexprGetNChildren(exprs[i]) == 2);
2810 
2813  assert(x != NULL);
2814  assert(y != NULL);
2815  assert(x != y);
2816 
2817  /* skip almost fixed variables */
2818  if( !varIsInteresting(scip, x, 1) || !varIsInteresting(scip, y, 1) )
2819  continue;
2820 
2821  /* create bilinear bound */
2822  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata->bilinbounds[propdata->nbilinbounds]) ); /*lint !e866*/
2823  bilinbound = propdata->bilinbounds[propdata->nbilinbounds];
2824  BMSclearMemory(bilinbound);
2825 
2826  /* store and capture expression */
2827  bilinbound->expr = exprs[i];
2828  SCIPcaptureExpr(bilinbound->expr);
2829 
2830  /* compute a descent score */
2831  bilinbound->score = bilinboundGetScore(scip, propdata->randnumgen, bilinbound);
2832 
2833  /* increase the number of bilinear bounds */
2834  ++(propdata->nbilinbounds);
2835 
2836  SCIPdebugMsg(scip, "added bilinear bound for %s %s\n", SCIPvarGetName(x), SCIPvarGetName(y));
2837  }
2838  }
2839 
2840  /* sort bounds according to decreasing score */
2841  if( propdata->nbilinbounds > 1 )
2842  {
2843  SCIPsortDownPtr((void**) propdata->bilinbounds, compBilinboundsScore, propdata->nbilinbounds);
2844  }
2845  }
2846 
2847  /* free memory for buffering nonlinearities */
2848  assert(nlcount != NULL);
2849  assert(nccount != NULL);
2850  SCIPfreeBufferArray(scip, &nccount);
2851  SCIPfreeBufferArray(scip, &nlcount);
2852 
2853  /* propdata->bounds array if empty */
2854  if( propdata->nbounds <= 0 )
2855  {
2856  assert(propdata->nbounds == 0);
2857  assert(propdata->boundssize >= 0 );
2858  SCIPfreeBlockMemoryArray(scip, &(propdata->bounds), propdata->boundssize);
2859  }
2860 
2861  SCIPdebugMsg(scip, "problem has %d/%d interesting bounds\n", propdata->nbounds, 2 * nvars);
2862 
2863  if( propdata->nbounds > 0 )
2864  {
2865  /* sort bounds according to decreasing score; although this initial order will be overruled by the distance
2866  * criterion later, gives a more well-defined starting situation for OBBT and might help to reduce solver
2867  * variability
2868  */
2869  SCIPsortDownPtr((void**) propdata->bounds, compBoundsScore, propdata->nbounds);
2870  }
2871 
2872  return SCIP_OKAY;
2873 }
2874 
2875 /*
2876  * Callback methods of propagator
2877  */
2878 
2879 /** copy method for propagator plugins (called when SCIP copies plugins)
2880  *
2881  * @note The UG framework assumes that all default plug-ins of SCIP implement a copy callback. We check
2882  * SCIPgetSubscipDepth() in PROPEXEC to prevent the propagator to run in a sub-SCIP.
2883  */
2884 static
2885 SCIP_DECL_PROPCOPY(propCopyObbt)
2886 { /*lint --e{715}*/
2887  assert(scip != NULL);
2888  assert(prop != NULL);
2889  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2890 
2891  /* call inclusion method of constraint handler */
2892  SCIP_CALL( SCIPincludePropObbt(scip) );
2893 
2894  return SCIP_OKAY;
2895 }
2896 
2897 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
2898 static
2899 SCIP_DECL_PROPINITSOL(propInitsolObbt)
2900 { /*lint --e{715}*/
2901  SCIP_PROPDATA* propdata;
2902 
2903  assert(scip != NULL);
2904  assert(prop != NULL);
2905  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2906 
2907  /* get propagator data */
2908  propdata = SCIPpropGetData(prop);
2909  assert(propdata != NULL);
2910 
2911  propdata->bounds = NULL;
2912  propdata->nbounds = -1;
2913  propdata->boundssize = 0;
2914  propdata->cutoffrow = NULL;
2915  propdata->lastnode = -1;
2916 
2917  /* if genvbounds propagator is not available, we cannot create genvbounds */
2918  propdata->genvboundprop = propdata->creategenvbounds ? SCIPfindProp(scip, GENVBOUND_PROP_NAME) : NULL;
2919 
2920  SCIPdebugMsg(scip, "creating genvbounds: %s\n", propdata->genvboundprop != NULL ? "true" : "false");
2921 
2922  /* create random number generator */
2923  SCIP_CALL( SCIPcreateRandom(scip, &propdata->randnumgen, DEFAULT_RANDSEED, TRUE) );
2924 
2925  return SCIP_OKAY;
2926 }
2927 
2928 /** execution method of propagator */
2929 static
2930 SCIP_DECL_PROPEXEC(propExecObbt)
2931 { /*lint --e{715}*/
2932  SCIP_PROPDATA* propdata;
2933  SCIP_Longint itlimit;
2934 
2935  assert(scip != NULL);
2936  assert(prop != NULL);
2937  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2938 
2939  *result = SCIP_DIDNOTRUN;
2940 
2941  /* do not run in: presolving, repropagation, probing mode, if no objective propagation is allowed */
2943  return SCIP_OKAY;
2944 
2945  /* do not run propagator in a sub-SCIP */
2946  if( SCIPgetSubscipDepth(scip) > 0 )
2947  return SCIP_OKAY;
2948 
2949  /* only run for nonlinear problems, i.e., if NLP is constructed */
2950  if( !SCIPisNLPConstructed(scip) )
2951  {
2952  SCIPdebugMsg(scip, "NLP not constructed, skipping obbt\n");
2953  return SCIP_OKAY;
2954  }
2955 
2956  /* only run if LP all columns are in the LP, i.e., the LP is a relaxation; e.g., do not run if pricers are active
2957  * since pricing is not performed in probing mode
2958  */
2959  if( !SCIPallColsInLP(scip) )
2960  {
2961  SCIPdebugMsg(scip, "not all columns in LP, skipping obbt\n");
2962  return SCIP_OKAY;
2963  }
2964 
2965  /* get propagator data */
2966  propdata = SCIPpropGetData(prop);
2967  assert(propdata != NULL);
2968 
2969  /* ensure that bounds are initialized */
2970  if( propdata->nbounds == -1 )
2971  {
2972  /* bounds must be initialized at root node */
2973  if( SCIPgetDepth(scip) == 0 )
2974  {
2975  SCIP_CALL( initBounds(scip, propdata) );
2976  }
2977  else
2978  {
2979  assert(!SCIPinProbing(scip));
2980  return SCIP_OKAY;
2981  }
2982  }
2983  assert(propdata->nbounds >= 0);
2984 
2985  /* do not run if there are no interesting bounds */
2986  /**@todo disable */
2987  if( propdata->nbounds <= 0 )
2988  {
2989  SCIPdebugMsg(scip, "there are no interesting bounds\n");
2990  return SCIP_OKAY;
2991  }
2992 
2993  /* only run once in a node != root */
2994  if( SCIPgetDepth(scip) > 0 && SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) == propdata->lastnode )
2995  {
2996  return SCIP_OKAY;
2997  }
2998 
2999  SCIPdebugMsg(scip, "applying obbt for problem <%s> at depth %d\n", SCIPgetProbName(scip), SCIPgetDepth(scip));
3000 
3001  /* without an optimal LP solution we don't want to run; this may be because propagators with higher priority have
3002  * already found reductions or numerical troubles occured during LP solving
3003  */
3005  {
3006  SCIPdebugMsg(scip, "aborting since no optimal LP solution is at hand\n");
3007  return SCIP_OKAY;
3008  }
3009 
3010  /* compute iteration limit */
3011  if( propdata->itlimitfactor > 0.0 )
3012  itlimit = (SCIP_Longint) MAX(propdata->itlimitfactor * SCIPgetNRootLPIterations(scip),
3013  propdata->minitlimit); /*lint !e666*/
3014  else
3015  itlimit = -1;
3016 
3017  /* apply obbt */
3018  SCIP_CALL( applyObbt(scip, propdata, itlimit, result) );
3019  assert(*result != SCIP_DIDNOTRUN);
3020 
3021  /* compute globally inequalities for bilinear terms */
3022  if( propdata->createbilinineqs )
3023  {
3024  /* set LP iteration limit */
3025  if( propdata->itlimitbilin == 0L )
3026  {
3027  /* no iteration limit if itlimit < 0 or itlimitfactorbilin < 0 */
3028  propdata->itlimitbilin = (itlimit < 0 || propdata->itlimitfactorbilin < 0)
3029  ? -1L : (SCIP_Longint)(itlimit * propdata->itlimitfactorbilin);
3030  }
3031 
3032  SCIP_CALL( applyObbtBilinear(scip, propdata, itlimit, result) );
3033  }
3034 
3035  /* set current node as last node */
3036  propdata->lastnode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
3037 
3038  return SCIP_OKAY;
3039 }
3040 
3041 /** propagation conflict resolving method of propagator */
3042 static
3043 SCIP_DECL_PROPRESPROP(propRespropObbt)
3044 { /*lint --e{715}*/
3045  *result = SCIP_DIDNOTFIND;
3046 
3047  return SCIP_OKAY;
3048 }
3049 
3050 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
3051 static
3052 SCIP_DECL_PROPEXITSOL(propExitsolObbt)
3053 { /*lint --e{715}*/
3054  SCIP_PROPDATA* propdata;
3055  int i;
3056 
3057  assert(scip != NULL);
3058  assert(prop != NULL);
3059  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
3060 
3061  /* get propagator data */
3062  propdata = SCIPpropGetData(prop);
3063  assert(propdata != NULL);
3065  /* free random number generator */
3066  SCIPfreeRandom(scip, &propdata->randnumgen);
3067  propdata->randnumgen = NULL;
3068 
3069  /* note that because we reset filtered flags to false at each call to obbt, the same bound may be filtered multiple
3070  * times
3071  */
3072  SCIPstatisticMessage("DIVE-LP: %" SCIP_LONGINT_FORMAT " NFILTERED: %d NTRIVIALFILTERED: %d NSOLVED: %d "
3073  "FILTER-LP: %" SCIP_LONGINT_FORMAT " NGENVB(dive): %d NGENVB(aggr.): %d NGENVB(triv.) %d\n",
3074  propdata->nprobingiterations, propdata->nfiltered, propdata->ntrivialfiltered, propdata->nsolvedbounds,
3075  propdata->nfilterlpiters, propdata->ngenvboundsprobing, propdata->ngenvboundsaggrfil, propdata->ngenvboundstrivfil);
3076 
3077  /* free bilinear bounds */
3078  if( propdata->bilinboundssize > 0 )
3079  {
3080  for( i = propdata->nbilinbounds - 1; i >= 0; --i )
3081  {
3082  assert(propdata->bilinbounds[i] != NULL);
3083  assert(propdata->bilinbounds[i]->expr != NULL);
3084 
3085  /* release expression */
3086  SCIP_CALL( SCIPreleaseExpr(scip, &propdata->bilinbounds[i]->expr) );
3087 
3088  SCIPfreeBlockMemory(scip, &propdata->bilinbounds[i]); /*lint !e866*/
3089  }
3090  SCIPfreeBlockMemoryArray(scip, &propdata->bilinbounds, propdata->bilinboundssize);
3091  propdata->bilinboundssize = 0;
3092  propdata->nbilinbounds = 0;
3093  }
3094 
3095  /* free memory allocated for the bounds */
3096  if( propdata->nbounds > 0 )
3097  {
3098  /* free bounds */
3099  for( i = propdata->nbounds - 1; i >= 0; i-- )
3100  {
3101  SCIPfreeBlockMemory(scip, &(propdata->bounds[i])); /*lint !e866*/
3102  }
3103  SCIPfreeBlockMemoryArray(scip, &(propdata->bounds), propdata->boundssize);
3104  }
3105 
3106  propdata->nbounds = -1;
3107  propdata->itlimitbilin = 0;
3108  propdata->itusedbilin = 0;
3109 
3110  return SCIP_OKAY;
3111 }
3112 
3113 /** destructor of propagator to free user data (called when SCIP is exiting) */
3114 static
3115 SCIP_DECL_PROPFREE(propFreeObbt)
3116 { /*lint --e{715}*/
3117  SCIP_PROPDATA* propdata;
3118 
3119  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
3120 
3121  /* free propagator data */
3122  propdata = SCIPpropGetData(prop);
3123  assert(propdata != NULL);
3124 
3125  SCIPfreeBlockMemory(scip, &propdata);
3126 
3128 
3129  return SCIP_OKAY;
3130 }
3131 
3132 /*
3133  * propagator specific interface methods
3134  */
3135 
3136 /** creates the obbt propagator and includes it in SCIP */
3138  SCIP* scip /**< SCIP data structure */
3139  )
3140 {
3141  SCIP_PROPDATA* propdata;
3142  SCIP_PROP* prop;
3143 
3144  /* create obbt propagator data */
3145  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
3146  BMSclearMemory(propdata);
3147 
3148  /* initialize statistic variables */
3149  propdata->nprobingiterations = 0;
3150  propdata->nfiltered = 0;
3151  propdata->ntrivialfiltered = 0;
3152  propdata->nsolvedbounds = 0;
3153  propdata->ngenvboundsprobing = 0;
3154  propdata->ngenvboundsaggrfil = 0;
3155  propdata->ngenvboundstrivfil = 0;
3156  propdata->nfilterlpiters = 0;
3157  propdata->lastidx = -1;
3158  propdata->propagatecounter = 0;
3159  propdata->npropagatedomreds = 0;
3160 
3161  /* include propagator */
3163  propExecObbt, propdata) );
3164 
3165  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyObbt) );
3166  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeObbt) );
3167  SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolObbt) );
3168  SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolObbt) );
3169  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropObbt) );
3170 
3171  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/creategenvbounds",
3172  "should obbt try to provide genvbounds if possible?",
3173  &propdata->creategenvbounds, TRUE, DEFAULT_CREATE_GENVBOUNDS, NULL, NULL) );
3174 
3175  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/normalize",
3176  "should coefficients in filtering be normalized w.r.t. the domains sizes?",
3177  &propdata->normalize, TRUE, DEFAULT_FILTERING_NORM, NULL, NULL) );
3178 
3179  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/applyfilterrounds",
3180  "try to filter bounds in so-called filter rounds by solving auxiliary LPs?",
3181  &propdata->applyfilterrounds, TRUE, DEFAULT_APPLY_FILTERROUNDS, NULL, NULL) );
3182 
3183  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/applytrivialfilter",
3184  "try to filter bounds with the LP solution after each solve?",
3185  &propdata->applytrivialfilter, TRUE, DEFAULT_APPLY_TRIVIALFITLERING, NULL, NULL) );
3186 
3187  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/genvbdsduringfilter",
3188  "should we try to generate genvbounds during trivial and aggressive filtering?",
3189  &propdata->genvbdsduringfilter, TRUE, DEFAULT_GENVBDSDURINGFILTER, NULL, NULL) );
3190 
3191  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/genvbdsduringsepa",
3192  "try to create genvbounds during separation process?",
3193  &propdata->genvbdsduringsepa, TRUE, DEFAULT_GENVBDSDURINGSEPA, NULL, NULL) );
3194 
3195  SCIP_CALL( SCIPaddIntParam(scip, "propagating/" PROP_NAME "/minfilter",
3196  "minimal number of filtered bounds to apply another filter round",
3197  &propdata->nminfilter, TRUE, DEFAULT_FILTERING_MIN, 1, INT_MAX, NULL, NULL) );
3198 
3199  SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/itlimitfactor",
3200  "multiple of root node LP iterations used as total LP iteration limit for obbt (<= 0: no limit )",
3201  &propdata->itlimitfactor, FALSE, DEFAULT_ITLIMITFACTOR, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
3202 
3203  SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/itlimitfactorbilin",
3204  "multiple of OBBT LP limit used as total LP iteration limit for solving bilinear inequality LPs (< 0 for no limit)",
3205  &propdata->itlimitfactorbilin, FALSE, DEFAULT_ITLIMITFAC_BILININEQS, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
3206 
3207  SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/minnonconvexity",
3208  "minimum absolute value of nonconvex eigenvalues for a bilinear term",
3209  &propdata->minnonconvexity, FALSE, DEFAULT_MINNONCONVEXITY, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3210 
3211  SCIP_CALL( SCIPaddLongintParam(scip, "propagating/" PROP_NAME "/minitlimit",
3212  "minimum LP iteration limit",
3213  &propdata->minitlimit, FALSE, DEFAULT_MINITLIMIT, 0L, SCIP_LONGINT_MAX, NULL, NULL) );
3214 
3215  SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/dualfeastol",
3216  "feasibility tolerance for reduced costs used in obbt; this value is used if SCIP's dual feastol is greater",
3217  &propdata->dualfeastol, FALSE, DEFAULT_DUALFEASTOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3218 
3219  SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/conditionlimit",
3220  "maximum condition limit used in LP solver (-1.0: no limit)",
3221  &propdata->conditionlimit, FALSE, DEFAULT_CONDITIONLIMIT, -1.0, SCIP_REAL_MAX, NULL, NULL) );
3222 
3223  SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/boundstreps",
3224  "minimal relative improve for strengthening bounds",
3225  &propdata->boundstreps, FALSE, DEFAULT_BOUNDSTREPS, 0.0, 1.0, NULL, NULL) );
3226 
3227  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/onlynonconvexvars",
3228  "only apply obbt on non-convex variables",
3229  &propdata->onlynonconvexvars, TRUE, DEFAULT_ONLYNONCONVEXVARS, NULL, NULL) );
3230 
3231  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/tightintboundsprobing",
3232  "should integral bounds be tightened during the probing mode?",
3233  &propdata->tightintboundsprobing, TRUE, DEFAULT_TIGHTINTBOUNDSPROBING, NULL, NULL) );
3234 
3235  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/tightcontboundsprobing",
3236  "should continuous bounds be tightened during the probing mode?",
3237  &propdata->tightcontboundsprobing, TRUE, DEFAULT_TIGHTCONTBOUNDSPROBING, NULL, NULL) );
3238 
3239  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/createbilinineqs",
3240  "solve auxiliary LPs in order to find valid inequalities for bilinear terms?",
3241  &propdata->createbilinineqs, TRUE, DEFAULT_CREATE_BILININEQS, NULL, NULL) );
3242 
3243  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/createlincons",
3244  "create linear constraints from inequalities for bilinear terms?",
3245  &propdata->createlincons, TRUE, DEFAULT_CREATE_LINCONS, NULL, NULL) );
3246 
3247  SCIP_CALL( SCIPaddIntParam(scip, "propagating/" PROP_NAME "/orderingalgo",
3248  "select the type of ordering algorithm which should be used (0: no special ordering, 1: greedy, 2: greedy reverse)",
3249  &propdata->orderingalgo, TRUE, DEFAULT_ORDERINGALGO, 0, 2, NULL, NULL) );
3250 
3251  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/separatesol",
3252  "should the obbt LP solution be separated?",
3253  &propdata->separatesol, TRUE, DEFAULT_SEPARATESOL, NULL, NULL) );
3254 
3255  SCIP_CALL( SCIPaddIntParam(scip, "propagating/" PROP_NAME "/sepaminiter",
3256  "minimum number of iteration spend to separate an obbt LP solution",
3257  &propdata->sepaminiter, TRUE, DEFAULT_SEPAMINITER, 0, INT_MAX, NULL, NULL) );
3258 
3259  SCIP_CALL( SCIPaddIntParam(scip, "propagating/" PROP_NAME "/sepamaxiter",
3260  "maximum number of iteration spend to separate an obbt LP solution",
3261  &propdata->sepamaxiter, TRUE, DEFAULT_SEPAMAXITER, 0, INT_MAX, NULL, NULL) );
3262 
3263  SCIP_CALL( SCIPaddIntParam(scip, "propagating/" PROP_NAME "/propagatefreq",
3264  "trigger a propagation round after that many bound tightenings (0: no propagation)",
3265  &propdata->propagatefreq, TRUE, DEFAULT_PROPAGATEFREQ, 0, INT_MAX, NULL, NULL) );
3266 
3267  return SCIP_OKAY;
3268 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
#define DEFAULT_APPLY_FILTERROUNDS
Definition: prop_obbt.c:86
#define DEFAULT_GENVBDSDURINGFILTER
Definition: prop_obbt.c:90
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip_lp.c:596
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define PROP_NAME
Definition: prop_obbt.c:73
#define PROP_FREQ
Definition: prop_obbt.c:77
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:137
SCIP_Longint SCIPgetNRootLPIterations(SCIP *scip)
SCIP_Real SCIPfeastol(SCIP *scip)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:101
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5200
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1626
unsigned int done
Definition: prop_obbt.c:146
#define DEFAULT_CREATE_LINCONS
Definition: prop_obbt.c:128
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:82
static SCIP_DECL_SORTPTRCOMP(compBoundsScore)
Definition: prop_obbt.c:1539
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
static SCIP_RETCODE filterExistingLP(SCIP *scip, SCIP_PROPDATA *propdata, int *nfiltered, BOUND *currbound)
Definition: prop_obbt.c:934
public methods for branch and bound tree
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:216
#define DEFAULT_MINITLIMIT
Definition: prop_obbt.c:102
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
static SCIP_RETCODE sortBounds(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_obbt.c:1585
SCIP_RETCODE SCIPcreateEmptyRowUnspec(SCIP *scip, SCIP_ROW **row, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1473
static void exchangeBounds(SCIP_PROPDATA *propdata, int i)
Definition: prop_obbt.c:739
public methods for memory management
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3798
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1649
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
enum SCIP_BaseStat SCIP_BASESTAT
Definition: type_lpi.h:87
SCIP_RETCODE SCIPapplyCutsProbing(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_probing.c:938
#define DEFAULT_BOUNDSTREPS
Definition: prop_obbt.c:95
SCIP_PROP * SCIPfindProp(SCIP *scip, const char *name)
Definition: scip_prop.c:320
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
#define SCIP_MAXSTRLEN
Definition: def.h:293
#define DEFAULT_SEPAMAXITER
Definition: prop_obbt.c:122
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
Definition: lp.c:16997
#define DEFAULT_MINNONCONVEXITY
Definition: prop_obbt.c:130
static SCIP_DECL_PROPEXITSOL(propExitsolObbt)
Definition: prop_obbt.c:3064
static long bound
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
#define DEFAULT_ITLIMITFACTOR
Definition: prop_obbt.c:99
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1861
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
int filtered
Definition: prop_obbt.c:167
static SCIP_RETCODE filterRound(SCIP *scip, SCIP_PROPDATA *propdata, int itlimit, int *nfiltered, SCIP_Real *objcoefs, int *objcoefsinds, int nobjcoefs)
Definition: prop_obbt.c:1107
SCIP_RETCODE SCIPincludePropObbt(SCIP *scip)
Definition: prop_obbt.c:3149
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17431
SCIP_Real SCIPdualfeastol(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1865
static int nextBound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool convexphase)
Definition: prop_obbt.c:1617
#define FALSE
Definition: def.h:87
#define DEFAULT_SEPAMINITER
Definition: prop_obbt.c:121
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:102
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:11063
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2591
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define DEFAULT_APPLY_TRIVIALFITLERING
Definition: prop_obbt.c:89
#define TRUE
Definition: def.h:86
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define SCIPstatisticMessage
Definition: pub_message.h:114
SCIP_NLHDLR * SCIPfindNlhdlrNonlinear(SCIP_CONSHDLR *conshdlr, const char *name)
static SCIP_Real getFilterCoef(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype)
Definition: prop_obbt.c:479
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17600
int index
Definition: prop_obbt.c:148
public methods for problem variables
#define DEFAULT_CREATE_BILININEQS
Definition: prop_obbt.c:127
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5317
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define DEFAULT_ITLIMITFAC_BILININEQS
Definition: prop_obbt.c:129
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:292
SCIP_RETCODE SCIPgetNLPVarsNonlinearity(SCIP *scip, int *nlcount)
Definition: scip_nlp.c:214
static int bilinboundGetLocksPos(BILINBOUND *bilinbound)
Definition: prop_obbt.c:877
SCIP_EXPR * expr
Definition: prop_obbt.c:166
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define GENVBOUND_PROP_NAME
Definition: prop_obbt.c:114
#define SCIP_LONGINT_MAX
Definition: def.h:163
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition: scip_expr.c:1399
static void getCorner(SCIP_VAR *x, SCIP_VAR *y, CORNER corner, SCIP_Real *px, SCIP_Real *py)
Definition: prop_obbt.c:762
public methods for SCIP variables
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:594
Corner
Definition: prop_obbt.c:153
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:17278
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
SCIP_VAR ** x
Definition: circlepacking.c:54
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_HASHMAP * SCIPgetVarExprHashmapNonlinear(SCIP_CONSHDLR *conshdlr)
bilinear nonlinear handler
public methods for numerical tolerances
static SCIP_RETCODE tightenBoundProbing(SCIP *scip, BOUND *bound, SCIP_Real newval, SCIP_Bool *tightened)
Definition: prop_obbt.c:1478
#define DEFAULT_ORDERINGALGO
Definition: prop_obbt.c:110
public methods for querying solving statistics
static unsigned int getScore(SCIP *scip, BOUND *bound, int nlcount, int maxnlcount)
Definition: prop_obbt.c:2587
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1066
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17489
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
public methods for the branch-and-bound tree
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7434
static SCIP_RETCODE createGenVBound(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *bound, SCIP_Bool *found)
Definition: prop_obbt.c:553
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3808
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
#define DEFAULT_DUALFEASTOL
Definition: prop_obbt.c:91
public methods for managing constraints
#define DEFAULT_FILTERING_NORM
Definition: prop_obbt.c:83
int SCIPgetNNLPVars(SCIP *scip)
Definition: scip_nlp.c:192
static SCIP_RETCODE applyBoundChgs(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_RESULT *result)
Definition: prop_obbt.c:1411
static SCIP_Bool includeVarGenVBound(SCIP *scip, SCIP_VAR *var)
Definition: prop_obbt.c:422
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2769
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
static SCIP_DECL_PROPRESPROP(propRespropObbt)
Definition: prop_obbt.c:3055
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define PROP_DESC
Definition: prop_obbt.c:74
SCIP_RETCODE SCIPgenVBoundAdd(SCIP *scip, SCIP_PROP *genvboundprop, SCIP_VAR **vars, SCIP_VAR *var, SCIP_Real *coefs, int ncoefs, SCIP_Real coefcutoffbound, SCIP_Real constant, SCIP_BOUNDTYPE boundtype)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:251
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
#define NULL
Definition: lpi_spx1.cpp:155
#define DEFAULT_GENVBDSDURINGSEPA
Definition: prop_obbt.c:123
SCIP_RETCODE SCIPseparateSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool pretendroot, SCIP_Bool allowlocal, SCIP_Bool onlydelayed, SCIP_Bool *delayed, SCIP_Bool *cutoff)
Definition: scip_cut.c:726
#define REALABS(x)
Definition: def.h:201
SCIP_RETCODE SCIPchgDualfeastol(SCIP *scip, SCIP_Real dualfeastol)
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18284
static SCIP_Bool varIsInteresting(SCIP *scip, SCIP_VAR *var, int nlcount)
Definition: prop_obbt.c:2689
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:617
public methods for problem copies
SCIP_Real SCIPgetVarObjProbing(SCIP *scip, SCIP_VAR *var)
Definition: scip_probing.c:379
#define SCIP_CALL(x)
Definition: def.h:384
unsigned int done
Definition: prop_obbt.c:168
static SCIP_Real bilinboundGetScore(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, BILINBOUND *bilinbound)
Definition: prop_obbt.c:888
#define DEFAULT_PROPAGATEFREQ
Definition: prop_obbt.c:124
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:810
#define OBBT_SCOREBASE
Definition: prop_obbt.c:113
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
unsigned int score
Definition: prop_obbt.c:143
static int getIterationsLeft(SCIP *scip, SCIP_Longint nolditerations, SCIP_Longint itlimit)
Definition: prop_obbt.c:449
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4590
public methods for constraint handler plugins and constraints
public methods for NLP management
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
static SCIP_RETCODE solveBilinearLP(SCIP *scip, SCIP_VAR *x, SCIP_VAR *y, SCIP_Real xs, SCIP_Real ys, SCIP_Real xt, SCIP_Real yt, SCIP_Real *xcoef, SCIP_Real *ycoef, SCIP_Real *constant, SCIP_Longint iterlim, int *nnonzduals)
Definition: prop_obbt.c:2244
int SCIPgetExprNLocksNegNonlinear(SCIP_EXPR *expr)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_Real newval
Definition: prop_obbt.c:141
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1407
constraint handler for nonlinear constraints specified by algebraic expressions
optimization-based bound tightening propagator
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
public methods for LP management
public methods for cuts and aggregation rows
#define DEFAULT_CREATE_GENVBOUNDS
Definition: prop_obbt.c:82
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:142
static SCIP_DECL_PROPFREE(propFreeObbt)
Definition: prop_obbt.c:3127
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition: scip_var.c:8653
SCIP_BOUNDTYPE boundtype
Definition: prop_obbt.c:142
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17621
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE applySeparation(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *currbound, SCIP_Longint *nleftiterations, SCIP_Bool *success)
Definition: prop_obbt.c:1669
#define BMSclearMemory(ptr)
Definition: memory.h:122
static SCIP_RETCODE setObjProbing(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *bound, SCIP_Real coef)
Definition: prop_obbt.c:375
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:222
static SCIP_DECL_PROPCOPY(propCopyObbt)
Definition: prop_obbt.c:2897
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10025
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
public methods for the LP relaxation, rows and columns
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:932
SCIP_EXPR ** SCIPgetExprsBilinear(SCIP_NLHDLR *nlhdlr)
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1991
#define SCIP_REAL_MAX
Definition: def.h:178
unsigned int found
Definition: prop_obbt.c:145
public methods for nonlinear relaxation
SCIP_Real * r
Definition: circlepacking.c:50
#define SCIP_REAL_MIN
Definition: def.h:179
methods for sorting joint arrays of various types
SCIP_RETCODE SCIPaddIneqBilinear(SCIP *scip, SCIP_NLHDLR *nlhdlr, SCIP_EXPR *expr, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Bool *success)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
static SCIP_RETCODE solveLP(SCIP *scip, int itlimit, SCIP_Bool *error, SCIP_Bool *optimal)
Definition: prop_obbt.c:243
int SCIPgetExprNLocksPosNonlinear(SCIP_EXPR *expr)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
general public methods
#define PROP_TIMING
Definition: prop_obbt.c:75
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:303
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for random numbers
#define DEFAULT_RANDSEED
Definition: prop_obbt.c:131
public methods for the probing mode
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
#define DEFAULT_SEPARATESOL
Definition: prop_obbt.c:116
int SCIPgetNCuts(SCIP *scip)
Definition: scip_cut.c:778
SCIP_RETCODE SCIPaddRowProbing(SCIP *scip, SCIP_ROW *row)
Definition: scip_probing.c:898
public methods for message output
static SCIP_VAR * bilinboundGetX(BILINBOUND *bilinbound)
Definition: prop_obbt.c:842
static SCIP_VAR * bilinboundGetY(BILINBOUND *bilinbound)
Definition: prop_obbt.c:854
static SCIP_RETCODE findNewBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint *nleftiterations, SCIP_Bool convexphase)
Definition: prop_obbt.c:1751
#define DEFAULT_ONLYNONCONVEXVARS
Definition: prop_obbt.c:103
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1421
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1946
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip_prop.c:206
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17370
int SCIPgetNExprsBilinear(SCIP_NLHDLR *nlhdlr)
#define SCIP_Real
Definition: def.h:177
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:43
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
SCIP_VAR ** y
Definition: circlepacking.c:55
public methods for message handling
SCIP_Real score
Definition: prop_obbt.c:169
#define SCIP_INVALID
Definition: def.h:197
static SCIP_Real evalBound(SCIP *scip, BOUND *bound)
Definition: prop_obbt.c:1601
SCIP_VAR * var
Definition: prop_obbt.c:140
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:780
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:790
static int bilinboundGetLocksNeg(BILINBOUND *bilinbound)
Definition: prop_obbt.c:866
static SCIP_RETCODE filterBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit)
Definition: prop_obbt.c:1267
#define SCIP_Longint
Definition: def.h:162
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:640
public methods for propagator plugins
SCIP_Real SCIPchgRelaxfeastol(SCIP *scip, SCIP_Real relaxfeastol)
#define DEFAULT_TIGHTCONTBOUNDSPROBING
Definition: prop_obbt.c:107
static SCIP_RETCODE addObjCutoff(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_obbt.c:315
static SCIP_Bool varIsFixedLocal(SCIP *scip, SCIP_VAR *var)
Definition: prop_obbt.c:365
static SCIP_DECL_PROPINITSOL(propInitsolObbt)
Definition: prop_obbt.c:2911
static SCIP_RETCODE getNLPVarsNonConvexity(SCIP *scip, unsigned int *nccounts)
Definition: prop_obbt.c:2630
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
unsigned int filtered
Definition: prop_obbt.c:144
#define PROP_DELAY
Definition: prop_obbt.c:78
#define PROP_PRIORITY
Definition: prop_obbt.c:76
#define DEFAULT_CONDITIONLIMIT
Definition: prop_obbt.c:94
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:156
unsigned int SCIPgetExprNSepaUsesActivityNonlinear(SCIP_EXPR *expr)
unsigned int nonconvex
Definition: prop_obbt.c:147
#define DEFAULT_TIGHTINTBOUNDSPROBING
Definition: prop_obbt.c:104
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:110
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
SCIPallocBlockMemory(scip, subsol))
static SCIP_RETCODE initBounds(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_obbt.c:2705
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
static SCIP_DECL_PROPEXEC(propExecObbt)
Definition: prop_obbt.c:2942
enum Corner CORNER
Definition: prop_obbt.c:161
#define SCIPABORT()
Definition: def.h:356
public methods for global and local (sub)problems
static SCIP_RETCODE applyObbt(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit, SCIP_RESULT *result)
Definition: prop_obbt.c:1990
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17442
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:336
#define DEFAULT_FILTERING_MIN
Definition: prop_obbt.c:96
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
#define EPSZ(x, eps)
Definition: def.h:207
static SCIP_RETCODE applyObbtBilinear(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit, SCIP_RESULT *result)
Definition: prop_obbt.c:2392
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
static void getCorners(SCIP_VAR *x, SCIP_VAR *y, CORNER corner, SCIP_Real *xs, SCIP_Real *ys, SCIP_Real *xt, SCIP_Real *yt)
Definition: prop_obbt.c:800
public methods for propagators
generalized variable bounds propagator
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:105
SCIP_RETCODE SCIPchgVarObjProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_probing.c:465