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-2017 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop_obbt.c
17  * @ingroup PROPAGATORS
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/prop_obbt.h"
42 #include "scip/prop_genvbounds.h"
43 #include "scip/debug.h"
44 #include "scip/cons_quadratic.h"
45 #include "scip/cons_nonlinear.h"
46 #include "scip/cons_abspower.h"
47 #include "scip/cons_bivariate.h"
48 
49 #define PROP_NAME "obbt"
50 #define PROP_DESC "optimization-based bound tightening propagator"
51 #define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP
52 #define PROP_PRIORITY -1000000 /**< propagator priority */
53 #define PROP_FREQ 0 /**< propagator frequency */
54 #define PROP_DELAY TRUE /**< should propagation method be delayed, if other propagators
55  * found reductions? */
56 
57 #define DEFAULT_CREATE_GENVBOUNDS TRUE /**< should obbt try to provide genvbounds if possible? */
58 #define DEFAULT_FILTERING_NORM TRUE /**< should coefficients in filtering be normalized w.r.t. the
59  * domains sizes? */
60 #define DEFAULT_APPLY_FILTERROUNDS FALSE /**< try to filter bounds in so-called filter rounds by solving
61  * auxiliary LPs? */
62 #define DEFAULT_APPLY_TRIVIALFITLERING TRUE /**< should obbt try to use the LP solution to filter some bounds? */
63 #define DEFAULT_GENVBDSDURINGFILTER TRUE /**< try to genrate genvbounds during trivial and aggressive filtering? */
64 #define DEFAULT_DUALFEASTOL 1e-9 /**< feasibility tolerance for reduced costs used in obbt; this value
65  * is used if SCIP's dual feastol is greater */
66 #define DEFAULT_CONDITIONLIMIT -1.0 /**< maximum condition limit used in LP solver (-1.0: no limit) */
67 #define DEFAULT_BOUNDSTREPS 0.001 /**< minimal relative improve for strengthening bounds */
68 #define DEFAULT_FILTERING_MIN 2 /**< minimal number of filtered bounds to apply another filter
69  * round */
70 #define DEFAULT_ITLIMITFACTOR 10.0 /**< multiple of root node LP iterations used as total LP iteration
71  * limit for obbt (<= 0: no limit ) */
72 #define DEFAULT_MINITLIMIT 5000L /**< minimum LP iteration limit */
73 #define DEFAULT_ONLYNONCONVEXVARS FALSE /**< only apply obbt on non-convex variables */
74 #define DEFAULT_TIGHTINTBOUNDSPROBING TRUE /**< should bounds of integral variables be tightened during
75  * the probing mode? */
76 #define DEFAULT_TIGHTCONTBOUNDSPROBING FALSE /**< should bounds of continuous variables be tightened during
77  * the probing mode? */
78 #define DEFAULT_ORDERINGALGO 1 /**< which type of ordering algorithm should we use?
79  * (0: no, 1: greedy, 2: greedy reverse) */
80 #define OBBT_SCOREBASE 5 /**< base that is used to calculate a bounds score value */
81 #define GENVBOUND_PROP_NAME "genvbounds"
82 #define INTERVALINFTY 1E+43 /**< value for infinity in interval operations */
83 
84 #define DEFAULT_SEPARATESOL FALSE /**< should the obbt LP solution be separated? note that that by
85  * separating solution OBBT will apply all bound tightenings
86  * immediatly */
87 #define DEFAULT_SEPAMINITER 0 /**< minimum number of iteration spend to separate an obbt LP solution */
88 #define DEFAULT_SEPAMAXITER 10 /**< maximum number of iteration spend to separate an obbt LP solution */
89 #define DEFAULT_GENVBDSDURINGSEPA TRUE /**< try to create genvbounds during separation process? */
90 #define DEFAULT_PROPAGATEFREQ 0 /**< trigger a propagation round after that many bound tightenings
91  * (0: no propagation) */
92 
93 /** translate from one value of infinity to another
94  *
95  * if val is >= infty1, then give infty2, else give val
96  */
97 #define infty2infty(infty1, infty2, val) ((val) >= (infty1) ? (infty2) : (val))
98 
99 /*
100  * Data structures
101  */
102 
103 /** bound data */
104 struct Bound
105 {
106  SCIP_VAR* var; /**< variable */
107  SCIP_Real newval; /**< stores a probably tighter value for this bound */
108  SCIP_BOUNDTYPE boundtype; /**< type of bound */
109  unsigned int score; /**< score value that is used to group bounds */
110  unsigned int filtered:1; /**< thrown out during pre-filtering step */
111  unsigned int found:1; /**< stores whether a probably tighter value for this bound was found */
112  unsigned int done:1; /**< has this bound been processed already? */
113  unsigned int nonconvex:1; /**< is this bound affecting a nonconvex term? */
114  int index; /**< unique index */
115 };
116 typedef struct Bound BOUND;
117 
118 
119 /** propagator data */
120 struct SCIP_PropData
121 {
122  BOUND** bounds; /**< array of interesting bounds */
123  SCIP_ROW* cutoffrow; /**< pointer to current objective cutoff row */
124  SCIP_PROP* genvboundprop; /**< pointer to genvbound propagator */
125  SCIP_Longint lastnode; /**< number of last node where obbt was performed */
126  SCIP_Longint npropagatedomreds; /**< number of domain reductions found during propagation */
127  SCIP_Longint nprobingiterations; /**< number of LP iterations during the probing mode */
128  SCIP_Longint nfilterlpiters; /**< number of LP iterations spend for filtering */
129  SCIP_Longint minitlimit; /**< minimum LP iteration limit */
130  SCIP_Real dualfeastol; /**< feasibility tolerance for reduced costs used in obbt; this value is
131  * used if SCIP's dual feastol is greater */
132  SCIP_Real conditionlimit; /**< maximum condition limit used in LP solver (-1.0: no limit) */
133  SCIP_Real boundstreps; /**< minimal relative improve for strengthening bounds */
134  SCIP_Real itlimitfactor; /**< LP iteration limit for obbt will be this factor times total LP
135  * iterations in root node */
136  SCIP_Bool applyfilterrounds; /**< apply filter rounds? */
137  SCIP_Bool applytrivialfilter; /**< should obbt try to use the LP solution to filter some bounds? */
138  SCIP_Bool genvbdsduringfilter;/**< should we try to generate genvbounds during trivial and aggressive
139  * filtering? */
140  SCIP_Bool genvbdsduringsepa; /**< try to create genvbounds during separation process? */
141  SCIP_Bool creategenvbounds; /**< should obbt try to provide genvbounds if possible? */
142  SCIP_Bool normalize; /**< should coefficients in filtering be normalized w.r.t. the domains
143  * sizes? */
144  SCIP_Bool onlynonconvexvars; /**< only apply obbt on non-convex variables */
145  SCIP_Bool tightintboundsprobing; /**< should bounds of integral variables be tightened during
146  * the probing mode? */
147  SCIP_Bool tightcontboundsprobing;/**< should bounds of continuous variables be tightened during
148  * the probing mode? */
149  SCIP_Bool separatesol; /**< should the obbt LP solution be separated? note that that by
150  * separating solution OBBT will apply all bound tightenings
151  * immediatly */
152  int orderingalgo; /**< which type of ordering algorithm should we use?
153  * (0: no, 1: greedy, 2: greedy reverse) */
154  int nbounds; /**< length of interesting bounds array */
155  int boundssize; /**< size of bounds array */
156  int nminfilter; /**< minimal number of filtered bounds to apply another filter round */
157  int nfiltered; /**< number of filtered bounds by solving auxiliary variables */
158  int ntrivialfiltered; /**< number of filtered bounds because the LP value was equal to the bound */
159  int nsolvedbounds; /**< number of solved bounds during the loop in applyObbt() */
160  int ngenvboundsprobing; /**< number of non-trivial genvbounds generated and added during obbt */
161  int ngenvboundsaggrfil; /**< number of non-trivial genvbounds found during aggressive filtering */
162  int ngenvboundstrivfil; /**< number of non-trivial genvbounds found during trivial filtering */
163  int lastidx; /**< index to store the last undone and unfiltered bound */
164  int sepaminiter; /**< minimum number of iteration spend to separate an obbt LP solution */
165  int sepamaxiter; /**< maximum number of iteration spend to separate an obbt LP solution */
166  int propagatefreq; /**< trigger a propagation round after that many bound tightenings
167  * (0: no propagation) */
168  int propagatecounter; /**< number of bound tightenings since the last propagation round */
169 };
170 
171 
172 /*
173  * Local methods
174  */
175 
176 /** solves the LP and handles errors */
177 static
178 SCIP_RETCODE solveLP(
179  SCIP* scip, /**< SCIP data structure */
180  int itlimit, /**< maximal number of LP iterations to perform, or -1 for no limit */
181  SCIP_Bool* error, /**< pointer to store whether an unresolved LP error occurred */
182  SCIP_Bool* optimal /**< was the LP solved to optimalilty? */
183  )
184 {
185  SCIP_LPSOLSTAT lpsolstat;
186  SCIP_RETCODE retcode;
187 
188  assert(scip != NULL);
189  assert(itlimit == -1 || itlimit >= 0);
190  assert(error != NULL);
191  assert(optimal != NULL);
192 
193  *optimal = FALSE;
194  *error = FALSE;
195 
196  retcode = SCIPsolveProbingLP(scip, itlimit, error, NULL);
197 
198  lpsolstat = SCIPgetLPSolstat(scip);
199 
200  /* an error should not kill the overall solving process */
201  if( retcode != SCIP_OKAY )
202  {
203  SCIPwarningMessage(scip, " error while solving LP in obbt propagator; LP solve terminated with code <%d>\n", retcode);
204  SCIPwarningMessage(scip, " this does not affect the remaining solution procedure --> continue\n");
205 
206  *error = TRUE;
207 
208  return SCIP_OKAY;
209  }
210 
211  if( lpsolstat == SCIP_LPSOLSTAT_OPTIMAL )
212  {
213  assert(!*error);
214  *optimal = TRUE;
215  }
216 #ifdef SCIP_DEBUG
217  else
218  {
219  switch( lpsolstat )
220  {
221  case SCIP_LPSOLSTAT_ITERLIMIT:
222  SCIPdebugMsg(scip, " reached lp iteration limit\n");
223  break;
224  case SCIP_LPSOLSTAT_TIMELIMIT:
225  SCIPdebugMsg(scip, " reached time limit while solving lp\n");
226  break;
227  case SCIP_LPSOLSTAT_UNBOUNDEDRAY:
228  SCIPdebugMsg(scip, " lp was unbounded\n");
229  break;
230  case SCIP_LPSOLSTAT_NOTSOLVED:
231  SCIPdebugMsg(scip, " lp was not solved\n");
232  break;
233  case SCIP_LPSOLSTAT_ERROR:
234  SCIPdebugMsg(scip, " an error occured during solving lp\n");
235  break;
236  case SCIP_LPSOLSTAT_INFEASIBLE:
237  case SCIP_LPSOLSTAT_OBJLIMIT:
238  case SCIP_LPSOLSTAT_OPTIMAL: /* should not appear because it is handled earlier */
239  default:
240  SCIPdebugMsg(scip, " received an unexpected solstat during solving lp: %d\n", lpsolstat);
241  }
242  }
243 #endif
244 
245  return SCIP_OKAY;
246 }
247 
248 /** adds the objective cutoff to the LP; must be in probing mode */
249 static
250 SCIP_RETCODE addObjCutoff(
251  SCIP* scip, /**< SCIP data structure */
252  SCIP_PROPDATA* propdata /**< data of the obbt propagator */
253  )
254 {
255  SCIP_ROW* row;
256  SCIP_VAR** vars;
257  char rowname[SCIP_MAXSTRLEN];
258 
259  int nvars;
260  int i;
261 
262  assert(scip != NULL);
263  assert(SCIPinProbing(scip));
264  assert(propdata != NULL);
265  assert(propdata->cutoffrow == NULL);
266 
267  if( SCIPisInfinity(scip, SCIPgetCutoffbound(scip)) )
268  {
269  SCIPdebugMsg(scip, "no objective cutoff since there is no cutoff bound\n");
270  return SCIP_OKAY;
271  }
272 
273  SCIPdebugMsg(scip, "create objective cutoff and add it to the LP\n");
274 
275  /* get variables data */
276  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
277 
278  /* create objective cutoff row; set local flag to FALSE since primal cutoff is globally valid */
279  (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "obbt_objcutoff");
280  SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, rowname, -SCIPinfinity(scip), SCIPgetCutoffbound(scip), FALSE, FALSE, FALSE) );
281  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
282 
283  for( i = 0; i < nvars; i++ )
284  {
285  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i], SCIPvarGetObj(vars[i])) );
286  }
287  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
288 
289  /* add row to the LP */
290  SCIP_CALL( SCIPaddRowProbing(scip, row) );
291 
292  propdata->cutoffrow = row;
293  assert(SCIProwIsInLP(propdata->cutoffrow));
294 
295  return SCIP_OKAY;
296 }
297 
298 /** determines, whether a variable is already locally fixed */
299 static
300 SCIP_Bool varIsFixedLocal(
301  SCIP* scip, /**< SCIP data structure */
302  SCIP_VAR* var /**< variable to check */
303  )
304 {
305  return SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var));
306 }
307 
308 /** sets objective to minimize or maximize a single variable */
309 static
310 SCIP_RETCODE setObjProbing(
311  SCIP* scip,
312  SCIP_PROPDATA* propdata,
313  BOUND* bound,
314  SCIP_Real coef
315  )
316 {
317 #ifdef SCIP_DEBUG
318  SCIP_VAR** vars;
319  int nvars;
320  int counter;
321  int i;
322 #endif
323 
324  assert( scip != NULL );
325  assert( propdata != NULL );
326  assert( bound != NULL );
327 
328  /* set the objective for bound->var */
329  if( bound->boundtype == SCIP_BOUNDTYPE_LOWER )
330  {
331  SCIP_CALL( SCIPchgVarObjProbing(scip, bound->var, coef) );
332  }
333  else
334  {
335  SCIP_CALL( SCIPchgVarObjProbing(scip, bound->var, -coef) );
336  }
337 
338 #ifdef SCIP_DEBUG
339  vars = SCIPgetVars(scip);
340  nvars = SCIPgetNVars(scip);
341  counter = 0;
342 
343  for( i = 0; i < nvars; ++i )
344  {
345  if( SCIPgetVarObjProbing(scip, vars[i]) != 0.0 )
346  ++counter;
347  }
348 
349  assert((counter == 0 && coef == 0.0) || (counter == 1 && coef != 0.0));
350 #endif
351 
352  return SCIP_OKAY;
353 }
354 
355 /** determines whether variable should be included in the right-hand side of the generalized variable bound */
356 static
357 SCIP_Bool includeVarGenVBound(
358  SCIP* scip, /**< SCIP data structure */
359  SCIP_VAR* var /**< variable to check */
360  )
361 {
362  SCIP_Real redcost;
363 
364  assert(scip != NULL);
365  assert(var != NULL);
366 
367  if( SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN )
368  return FALSE;
369 
370  redcost = SCIPgetVarRedcost(scip, var);
371  assert(redcost != SCIP_INVALID); /*lint !e777 */
372 
373  if( redcost == SCIP_INVALID ) /*lint !e777 */
374  return FALSE;
375 
376  if( redcost < SCIPdualfeastol(scip) && redcost > -SCIPdualfeastol(scip) )
377  return FALSE;
378 
379  return TRUE;
380 }
381 
382 /** returns number of LP iterations left (-1: no limit ) */
383 static
384 int getIterationsLeft(
385  SCIP* scip, /**< SCIP data structure */
386  SCIP_Longint nolditerations, /**< iterations count at the beginning of the corresponding function */
387  SCIP_Longint itlimit /**< LP iteration limit (-1: no limit) */
388  )
389 {
390  SCIP_Longint itsleft;
391 
392  assert(scip != NULL);
393  assert(nolditerations >= 0);
394  assert(itlimit == -1 || itlimit >= 0);
395 
396  if( itlimit == -1 )
397  {
398  SCIPdebugMsg(scip, "iterations left: unlimited\n");
399  return -1;
400  }
401  else
402  {
403  itsleft = itlimit - ( SCIPgetNLPIterations(scip) - nolditerations );
404  itsleft = MAX(itsleft, 0);
405  itsleft = MIN(itsleft, INT_MAX);
406 
407  SCIPdebugMsg(scip, "iterations left: %d\n", (int) itsleft);
408  return (int) itsleft;
409  }
410 }
411 
412 /** returns the objective coefficient for a variable's bound that will be chosen during filtering */
413 static
414 SCIP_Real getFilterCoef(
415  SCIP* scip, /**< SCIP data structure */
416  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
417  SCIP_VAR* var, /**< variable */
418  SCIP_BOUNDTYPE boundtype /**< boundtype to be filtered? */
419  )
420 {
421  SCIP_Real lb;
422  SCIP_Real ub;
423 
424  assert(scip != NULL);
425  assert(propdata != NULL);
426  assert(var != NULL);
427 
428  lb = SCIPvarGetLbLocal(var);
429  ub = SCIPvarGetUbLocal(var);
430 
431  /* this function should not be called for fixed variables */
432  assert(!varIsFixedLocal(scip, var));
433 
434  /* infinite bounds will not be reached */
435  if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisInfinity(scip, -lb) )
436  return 0.0;
437  if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisInfinity(scip, ub) )
438  return 0.0;
439 
440  if( propdata->normalize )
441  {
442  /* if the length of the domain is too large then the coefficient should be set to +/- 1.0 */
443  if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisInfinity(scip, ub) )
444  return 1.0;
445  if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisInfinity(scip, -lb) )
446  return -1.0;
447 
448  /* otherwise the coefficient is +/- 1.0 / ( ub - lb ) */
449  return boundtype == SCIP_BOUNDTYPE_LOWER ? 1.0 / (ub - lb) : -1.0 / (ub - lb);
450  }
451  else
452  {
453  return boundtype == SCIP_BOUNDTYPE_LOWER ? 1.0 : -1.0;
454  }
455 }
456 
457 /** creates a genvbound if the dual LP solution provides such information
458  *
459  * Consider the problem
460  *
461  * min { +/- x_i : obj * x <= z, lb <= Ax <= ub, l <= x <= u },
462  *
463  * where z is the current cutoff bound. Let (mu, nu, gamma, alpha, beta) >= 0 be the optimal solution of the dual of
464  * problem (P), where the variables correspond to the primal inequalities in the following way:
465  *
466  * Ax >= lb <-> mu
467  * -Ax >= -ub <-> nu
468  * -obj * x >= -z <-> gamma
469  * x >= l <-> alpha
470  * -x >= -u <-> beta
471  *
472  * Fixing these multipliers, by weak duality, we obtain the inequality
473  *
474  * +/- x_i >= lb*mu - ub*nu - z*gamma + l*alpha - u*beta
475  *
476  * that holds for all primal feasible points x with objective value at least z. Setting
477  *
478  * c = lb*mu - ub*nu, redcost_k = alpha_k - beta_k
479  *
480  * we obtain the inequality
481  *
482  * +/- x_i >= sum ( redcost_k * x_k ) + (-gamma) * cutoff_bound + c,
483  *
484  * that holds for all primal feasible points with objective value at least cutoff_bound. Therefore, the latter
485  * inequality can be added as a generalized variable bound.
486  */
487 static
488 SCIP_RETCODE createGenVBound(
489  SCIP* scip, /**< SCIP data structure */
490  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
491  BOUND* bound, /**< bound of x_i */
492  SCIP_Bool* found /**< pointer to store if we have found a non-trivial genvbound */
493  )
494 {
495  assert(scip != NULL);
496  assert(bound != NULL);
497  assert(propdata != NULL);
498  assert(propdata->genvboundprop != NULL);
499  assert(found != NULL);
500 
501  *found = FALSE;
502 
503  /* make sure we are in probing mode having an optimal LP solution */
504  assert(SCIPinProbing(scip));
505 
506  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
507 
508  /* only genvbounds created in the root node are globally valid
509  *
510  * note: depth changes to one if we use the probing mode to solve the obbt LPs
511  */
512  assert(SCIPgetDepth(scip) == 0 || (SCIPinProbing(scip) && SCIPgetDepth(scip) == 1));
513 
514  SCIPdebugMsg(scip, " try to create a genvbound for <%s>...\n", SCIPvarGetName(bound->var));
515 
516  /* a genvbound with a multiplier for x_i would not help us */
517  if( SCIPisZero(scip, SCIPgetVarRedcost(scip, bound->var)) )
518  {
519  SCIP_VAR** vars; /* global variables array */
520  SCIP_VAR** genvboundvars; /* genvbound variables array */
521 
522  SCIP_VAR* xi; /* variable x_i */
523 
524  SCIP_Real* genvboundcoefs; /* genvbound coefficients array */
525 
526  SCIP_Real gamma_dual; /* dual multiplier of objective cutoff */
527 
528  int k; /* variable for indexing global variables array */
529  int ncoefs; /* number of nonzero coefficients in genvbound */
530  int nvars; /* number of global variables */
531 
532  /* set x_i */
533  xi = bound->var;
534 
535  /* get variable data */
536  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
537 
538  /* count nonzero coefficients in genvbound */
539  ncoefs = 0;
540  for( k = 0; k < nvars; k++ )
541  {
542  if( includeVarGenVBound(scip, vars[k]) )
543  {
544  assert(vars[k] != xi);
545  ncoefs++;
546  }
547  }
548 
549  /* get dual multiplier for the objective cutoff (set to zero if there is no) */
550  if( propdata->cutoffrow == NULL )
551  {
552  gamma_dual = 0.0;
553  }
554  else
555  {
556  assert(!SCIPisInfinity(scip, SCIPgetCutoffbound(scip)));
557 
558  /* note that the objective cutoff is of the form
559  * -inf <= obj * x <= cutoff_bound
560  * but we want the positive dual multiplier!
561  */
562  gamma_dual = -SCIProwGetDualsol(propdata->cutoffrow);
563  }
564 
565  /* we need at least one nonzero coefficient or a nonzero dual multiplier for the objective cutoff */
566  if( ncoefs > 0 || !SCIPisZero(scip, gamma_dual) )
567  {
568  SCIP_Bool addgenvbound; /* if everything is fine with the redcosts and the bounds, add the genvbound */
569  SCIP_Real c; /* helper variable to calculate constant term in genvbound */
570  int idx; /* variable for indexing genvbound's coefficients array */
571 
572  /* add the bound if the bool is still TRUE after the loop */
573  addgenvbound = TRUE;
574 
575  /* there should be no coefficient for x_i */
576  assert(SCIPisZero(scip, SCIPgetVarRedcost(scip, xi)));
577 
578  /* allocate memory for storing the genvbounds right-hand side variables and coefficients */
579  SCIP_CALL( SCIPallocBufferArray(scip, &(genvboundvars), ncoefs) );
580  SCIP_CALL( SCIPallocBufferArray(scip, &(genvboundcoefs), ncoefs) );
581 
582  /* set c = lb*mu - ub*nu - z*gamma + l*alpha - u*beta */
583  c = SCIPgetLPObjval(scip);
584 
585  /* subtract ( - z * gamma ) from c */
586  c += SCIPgetCutoffbound(scip) * gamma_dual;
587 
588  /* subtract ( l*alpha - u*beta ) from c and set the coefficients of the variables */
589  idx = 0;
590  for( k = 0; k < nvars; k++ )
591  {
592  SCIP_VAR* xk;
593 
594  xk = vars[k];
595 
596  if( includeVarGenVBound(scip, xk) )
597  {
598  SCIP_Real redcost;
599 
600  redcost = SCIPgetVarRedcost(scip, xk);
601 
602  assert(redcost != SCIP_INVALID); /*lint !e777 */
603  assert(xk != xi);
604 
605  /* in this case dont add a genvbound */
606  if( ( (redcost > SCIPdualfeastol(scip)) && SCIPisInfinity(scip, -SCIPvarGetLbLocal(xk)) ) ||
607  ( (redcost < -SCIPdualfeastol(scip)) && SCIPisInfinity(scip, SCIPvarGetUbLocal(xk)) ) )
608  {
609  addgenvbound = FALSE;
610  break;
611  }
612 
613  /* store coefficients */
614  assert(idx < ncoefs);
615  genvboundvars[idx] = xk;
616  genvboundcoefs[idx] = redcost;
617  idx++;
618 
619  /* if redcost > 0, then redcost = alpha_k, otherwise redcost = - beta_k */
620  assert(redcost <= 0 || !SCIPisInfinity(scip, -SCIPvarGetLbLocal(xk)));
621  assert(redcost >= 0 || !SCIPisInfinity(scip, SCIPvarGetUbLocal(xk)));
622  c -= redcost > 0 ? redcost * SCIPvarGetLbLocal(xk) : redcost * SCIPvarGetUbLocal(xk);
623  }
624  }
625 
626  assert(!addgenvbound || idx == ncoefs);
627 
628  /* add genvbound */
629  if( addgenvbound && !SCIPisInfinity(scip, -c) )
630  {
631  SCIPdebugMsg(scip, " adding genvbound\n");
632  SCIP_CALL( SCIPgenVBoundAdd(scip, propdata->genvboundprop, genvboundvars, xi, genvboundcoefs, ncoefs,
633  !SCIPisPositive(scip, gamma_dual) ? 0.0 : -gamma_dual, c, bound->boundtype) );
634 
635  *found = TRUE;
636  }
637 
638  /* free arrays */
639  SCIPfreeBufferArray(scip, &genvboundcoefs);
640  SCIPfreeBufferArray(scip, &genvboundvars);
641  }
642  else
643  {
644  SCIPdebugMsg(scip, " trivial genvbound, skipping\n");
645  }
646  }
647  else
648  {
649  SCIPdebugMsg(scip, " found multiplier for <%s>: %g, skipping\n",
650  SCIPvarGetName(bound->var), SCIPgetVarRedcost(scip, bound->var));
651  }
652 
653  return SCIP_OKAY;
654 }
655 
656 /** exchange a bound which has been processed and updates the last undone and unfiltered bound index
657  * NOTE: this method has to be called after filtering or processing a bound
658  */
659 static
660 void exchangeBounds(
661  SCIP_PROPDATA* propdata, /**< propagator data */
662  int i /**< bound that was filtered or processed */
663  )
664 {
665  assert(i >= 0 && i < propdata->nbounds);
666  assert(propdata->lastidx >= 0 && propdata->lastidx < propdata->nbounds);
667 
668  /* exchange the bounds */
669  if( propdata->lastidx != i )
670  {
671  BOUND* tmp;
672 
673  tmp = propdata->bounds[i];
674  propdata->bounds[i] = propdata->bounds[propdata->lastidx];
675  propdata->bounds[propdata->lastidx] = tmp;
676  }
677 
678  propdata->lastidx -= 1;
679 }
680 
681 /** trying to filter some bounds using the existing LP solution */
682 static
683 SCIP_RETCODE filterExistingLP(
684  SCIP* scip, /**< original SCIP data structure */
685  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
686  int* nfiltered, /**< how many bounds were filtered this round? */
687  BOUND* currbound /**< bound for which OBBT LP was solved (Note: might be NULL) */
688  )
689 {
690  int i;
691 
692  assert(scip != NULL);
693  assert(propdata != NULL);
694  assert(nfiltered != NULL);
695 
696  *nfiltered = 0;
697 
698  /* only apply filtering if an LP solution is at hand */
699  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
700  {
701  SCIPdebugMsg(scip, "can't filter using existing lp solution since it was not solved to optimality\n");
702  return SCIP_OKAY;
703  }
704 
705  /* check if a bound is tight */
706  for( i = propdata->nbounds - 1; i >= 0; --i )
707  {
708  BOUND* bound; /* shortcut for current bound */
709 
710  SCIP_Real solval; /* the variables value in the current solution */
711  SCIP_Real boundval; /* current local bound for the variable */
712 
713  bound = propdata->bounds[i];
714  if( bound->filtered || bound->done )
715  continue;
716 
717  boundval = bound->boundtype == SCIP_BOUNDTYPE_UPPER ?
718  SCIPvarGetUbLocal(bound->var) : SCIPvarGetLbLocal(bound->var);
719  solval = SCIPvarGetLPSol(bound->var);
720 
721  /* bound is tight; since this holds for all fixed variables, those are filtered here automatically; if the lp solution
722  * is infinity, then also the bound is tight */
723  if( (bound->boundtype == SCIP_BOUNDTYPE_UPPER &&
724  (SCIPisInfinity(scip, solval) || SCIPisFeasGE(scip, solval, boundval)))
725  || (bound->boundtype == SCIP_BOUNDTYPE_LOWER &&
726  (SCIPisInfinity(scip, -solval) || SCIPisFeasLE(scip, solval, boundval))) )
727  {
728  SCIP_BASESTAT basestat;
729 
730  /* mark bound as filtered */
731  bound->filtered = TRUE;
732  SCIPdebugMsg(scip, "trivial filtered var: %s boundval=%e solval=%e\n", SCIPvarGetName(bound->var), boundval, solval);
733 
734  /* get the basis status of the variable */
735  basestat = SCIPcolGetBasisStatus(SCIPvarGetCol(bound->var));
736 
737  /* solve corresponding OBBT LP and try to generate a nontrivial genvbound */
738  if( propdata->genvbdsduringfilter && currbound != NULL && basestat == SCIP_BASESTAT_BASIC )
739  {
740 #ifndef NDEBUG
741  int j;
742 #endif
743  SCIP_Bool optimal;
744  SCIP_Bool error;
745 
746  /* set objective coefficient of the bound */
747  SCIP_CALL( SCIPchgVarObjProbing(scip, currbound->var, 0.0) );
748  SCIP_CALL( setObjProbing(scip, propdata, bound, 1.0) );
749 
750 #ifndef NDEBUG
751  for( j = 0; j < SCIPgetNVars(scip); ++j )
752  {
753  SCIP_VAR* var;
754 
755  var = SCIPgetVars(scip)[j];
756  assert(var != NULL);
757  assert(SCIPisZero(scip, SCIPgetVarObjProbing(scip, var)) || var == bound->var);
758  }
759 #endif
760 
761  /* solve the OBBT LP */
762  propdata->nprobingiterations -= SCIPgetNLPIterations(scip);
763  SCIP_CALL( solveLP(scip, -1, &error, &optimal) );
764  propdata->nprobingiterations += SCIPgetNLPIterations(scip);
765  assert(propdata->nprobingiterations >= 0);
766 
767  /* try to generate a genvbound if we have solved the OBBT LP */
768  if( optimal && propdata->genvboundprop != NULL
769  && (SCIPgetDepth(scip) == 0 || (SCIPinProbing(scip) && SCIPgetDepth(scip) == 1)) )
770  {
771  SCIP_Bool found;
772 
773  assert(!error);
774  SCIP_CALL( createGenVBound(scip, propdata, bound, &found) );
775 
776  if( found )
777  {
778  propdata->ngenvboundstrivfil += 1;
779  SCIPdebugMsg(scip, "found genvbound during trivial filtering\n");
780  }
781  }
782 
783  /* restore objective function */
784  SCIP_CALL( setObjProbing(scip, propdata, bound, 0.0) );
785  SCIP_CALL( setObjProbing(scip, propdata, currbound, 1.0) );
786  }
787 
788  /* exchange bound i with propdata->bounds[propdata->lastidx] */
789  if( propdata->lastidx >= 0 )
790  exchangeBounds(propdata, i);
791 
792  /* increase number of filtered variables */
793  (*nfiltered)++;
794  }
795  }
796 
797  return SCIP_OKAY;
798 }
799 
800 /** enforces one round of filtering */
801 static
802 SCIP_RETCODE filterRound(
803  SCIP* scip, /**< SCIP data structure */
804  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
805  int itlimit, /**< LP iteration limit (-1: no limit) */
806  int* nfiltered, /**< how many bounds were filtered this round */
807  SCIP_Real* objcoefs, /**< array to store the nontrivial objective coefficients */
808  int* objcoefsinds, /**< array to store bound indices for which their corresponding variables
809  * has a nontrivial objective coefficient */
810  int nobjcoefs /**< number of nontrivial objective coefficients */
811  )
812 {
813  SCIP_VAR** vars; /* array of the problems variables */
814  SCIP_Bool error;
815  SCIP_Bool optimal;
816 
817  int nvars; /* number of the problems variables */
818  int i;
819 
820  assert(scip != NULL);
821  assert(SCIPinProbing(scip));
822  assert(propdata != NULL);
823  assert(itlimit == -1 || itlimit >= 0);
824  assert(nfiltered != NULL);
825  assert(objcoefs != NULL);
826  assert(objcoefsinds != NULL);
827  assert(nobjcoefs >= 0);
828 
829  *nfiltered = 0;
830 
831  /* get variable data */
832  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
833 
834  /* solve LP */
835  propdata->nfilterlpiters -= (int) SCIPgetNLPIterations(scip);
836  SCIP_CALL( solveLP(scip, itlimit, &error, &optimal) );
837  propdata->nfilterlpiters += (int) SCIPgetNLPIterations(scip);
838  assert(propdata->nfilterlpiters >= 0);
839 
840  if( !optimal )
841  {
842  SCIPdebugMsg(scip, "skipping filter round since the LP was not solved to optimality\n");
843  return SCIP_OKAY;
844  }
845 
846  assert(!error);
847 
848  /* check if a bound is tight */
849  for( i = 0; i < propdata->nbounds; i++ )
850  {
851  BOUND* bound; /* shortcut for current bound */
852 
853  SCIP_Real solval; /* the variables value in the current solution */
854  SCIP_Real boundval; /* current local bound for the variable */
855 
856  bound = propdata->bounds[i];
857 
858  /* if bound is filtered it was handled already before */
859  if( bound->filtered )
860  continue;
861 
862  boundval = bound->boundtype == SCIP_BOUNDTYPE_UPPER ?
863  SCIPvarGetUbLocal(bound->var) : SCIPvarGetLbLocal(bound->var);
864  solval = SCIPvarGetLPSol(bound->var);
865 
866  /* bound is tight */
867  if( (bound->boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisFeasGE(scip, solval, boundval))
868  || (bound->boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisFeasLE(scip, solval, boundval)) )
869  {
870  SCIP_Real objcoef;
871  SCIP_BASESTAT basestat;
872 
873  /* mark bound as filtered */
874  bound->filtered = TRUE;
875 
876  /* get the basis status of the variable */
877  basestat = SCIPcolGetBasisStatus(SCIPvarGetCol(bound->var));
878 
879  /* increase number of filtered variables */
880  (*nfiltered)++;
881 
882  /* solve corresponding OBBT LP and try to generate a nontrivial genvbound */
883  if( propdata->genvbdsduringfilter && basestat == SCIP_BASESTAT_BASIC )
884  {
885  int j;
886 
887  /* set all objective coefficients to zero */
888  for( j = 0; j < nobjcoefs; ++j )
889  {
890  BOUND* filterbound;
891 
892  filterbound = propdata->bounds[ objcoefsinds[j] ];
893  assert(filterbound != NULL);
894 
895  SCIP_CALL( SCIPchgVarObjProbing(scip, filterbound->var, 0.0) );
896  }
897 
898 #ifndef NDEBUG
899  for( j = 0; j < nvars; ++j )
900  assert(SCIPisZero(scip, SCIPgetVarObjProbing(scip, vars[j])));
901 #endif
902 
903  /* set objective coefficient of the bound */
904  SCIP_CALL( setObjProbing(scip, propdata, bound, 1.0) );
905 
906  /* solve the OBBT LP */
907  propdata->nfilterlpiters -= (int) SCIPgetNLPIterations(scip);
908  SCIP_CALL( solveLP(scip, -1, &error, &optimal) );
909  propdata->nfilterlpiters += (int) SCIPgetNLPIterations(scip);
910  assert(propdata->nfilterlpiters >= 0);
911 
912  /* try to generate a genvbound if we have solved the OBBT LP */
913  if( optimal && propdata->genvboundprop != NULL
914  && (SCIPgetDepth(scip) == 0 || (SCIPinProbing(scip) && SCIPgetDepth(scip) == 1)) )
915  {
916  SCIP_Bool found;
917 
918  assert(!error);
919  SCIP_CALL( createGenVBound(scip, propdata, bound, &found) );
920 
921  if( found )
922  {
923  propdata->ngenvboundsaggrfil += 1;
924  SCIPdebugMsg(scip, "found genvbound during aggressive filtering\n");
925  }
926 
927  }
928 
929  /* restore objective function */
930  for( j = 0; j < nobjcoefs; ++j )
931  {
932  BOUND* filterbound;
933 
934  filterbound = propdata->bounds[ objcoefsinds[j] ];
935  assert(filterbound != NULL);
936 
937  /* NOTE: only restore coefficients of nonfiltered bounds */
938  if( !filterbound->filtered )
939  {
940  assert(!SCIPisZero(scip, objcoefs[j]));
941  SCIP_CALL( SCIPchgVarObjProbing(scip, propdata->bounds[ objcoefsinds[j] ]->var, objcoefs[j]) );
942  }
943  }
944  }
945 
946  /* get the corresponding variable's objective coefficient */
947  objcoef = SCIPgetVarObjProbing(scip, bound->var);
948 
949  /* change objective coefficient if it was set up for this bound */
950  if( (bound->boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisNegative(scip, objcoef))
951  || (bound->boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisPositive(scip, objcoef)) )
952  {
953  SCIP_CALL( SCIPchgVarObjProbing(scip, bound->var, 0.0) );
954  }
955  }
956  }
957 
958  return SCIP_OKAY;
959 }
960 
961 /** filter some bounds that are not improvable by solving auxiliary LPs */
962 static
963 SCIP_RETCODE filterBounds(
964  SCIP* scip, /**< SCIP data structure */
965  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
966  SCIP_Longint itlimit /**< LP iteration limit (-1: no limit) */
967  )
968 {
969  SCIP_VAR** vars;
970  SCIP_Longint nolditerations;
971  SCIP_Real* objcoefs; /* array to store the nontrivial objective coefficients */
972  int* objcoefsinds; /* array to store bound indices for which the corresponding variable
973  * has a nontrivial objective coefficient */
974  int nobjcoefs; /* number of nontrivial objective coefficients */
975  int nleftiterations;
976  int i;
977  int nfiltered;
978  int ntotalfiltered;
979  int nvars;
980 
981  assert(scip != NULL);
982  assert(SCIPinProbing(scip));
983  assert(propdata != NULL);
984  assert(itlimit == -1 || itlimit >= 0);
985 
986  ntotalfiltered = 0;
987  nolditerations = SCIPgetNLPIterations(scip);
988  nleftiterations = getIterationsLeft(scip, nolditerations, itlimit);
989 
990  /* get variable data */
991  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
992 
993  SCIPdebugMsg(scip, "start filter rounds\n");
994 
995  SCIP_CALL( SCIPallocBufferArray(scip, &objcoefs, propdata->nbounds) );
996  SCIP_CALL( SCIPallocBufferArray(scip, &objcoefsinds, propdata->nbounds) );
997  nobjcoefs = 0;
998 
999  /*
1000  * 1.) Try first to filter lower bounds of interesting variables, whose bounds are not already filtered
1001  */
1002 
1003  for( i = 0; i < nvars; i++ )
1004  {
1005  SCIP_CALL( SCIPchgVarObjProbing(scip, vars[i], 0.0) );
1006  }
1007 
1008  for( i = 0; i < propdata->nbounds; i++ )
1009  {
1010  if( propdata->bounds[i]->boundtype == SCIP_BOUNDTYPE_LOWER && !propdata->bounds[i]->filtered
1011  && !propdata->bounds[i]->done )
1012  {
1013  SCIP_Real objcoef;
1014 
1015  objcoef = getFilterCoef(scip, propdata, propdata->bounds[i]->var, SCIP_BOUNDTYPE_LOWER);
1016 
1017  if( !SCIPisZero(scip, objcoef) )
1018  {
1019  SCIP_CALL( SCIPchgVarObjProbing(scip, propdata->bounds[i]->var, objcoef) );
1020 
1021  /* store nontrivial objective coefficients */
1022  objcoefs[nobjcoefs] = objcoef;
1023  objcoefsinds[nobjcoefs] = i;
1024  ++nobjcoefs;
1025  }
1026  }
1027  }
1028 
1029  do
1030  {
1031  SCIPdebugMsg(scip, "doing a lower bounds round\n");
1032  SCIP_CALL( filterRound(scip, propdata, nleftiterations, &nfiltered, objcoefs, objcoefsinds, nobjcoefs) );
1033  ntotalfiltered += nfiltered;
1034  SCIPdebugMsg(scip, "filtered %d more bounds in lower bounds round\n", nfiltered);
1035 
1036  /* update iterations left */
1037  nleftiterations = getIterationsLeft(scip, nolditerations, itlimit);
1038  }
1039  while( nfiltered >= propdata->nminfilter && ( nleftiterations == -1 || nleftiterations > 0 ) );
1040 
1041  /*
1042  * 2.) Now try to filter the remaining upper bounds of interesting variables, whose bounds are not already filtered
1043  */
1044 
1045  /* set all objective coefficients to zero */
1046  for( i = 0; i < nobjcoefs; i++ )
1047  {
1048  BOUND* bound;
1049 
1050  assert(objcoefsinds[i] >= 0 && objcoefsinds[i] < propdata->nbounds);
1051  bound = propdata->bounds[ objcoefsinds[i] ];
1052  assert(bound != NULL);
1053  SCIP_CALL( SCIPchgVarObjProbing(scip, bound->var, 0.0) );
1054  }
1055 
1056  /* reset number of nontrivial objective coefficients */
1057  nobjcoefs = 0;
1058 
1059 #ifndef NDEBUG
1060  for( i = 0; i < nvars; ++i )
1061  assert(SCIPisZero(scip, SCIPgetVarObjProbing(scip, vars[i])));
1062 #endif
1063 
1064  for( i = 0; i < propdata->nbounds; i++ )
1065  {
1066  if( propdata->bounds[i]->boundtype == SCIP_BOUNDTYPE_UPPER && !propdata->bounds[i]->filtered )
1067  {
1068  SCIP_Real objcoef;
1069 
1070  objcoef = getFilterCoef(scip, propdata, propdata->bounds[i]->var, SCIP_BOUNDTYPE_UPPER);
1071 
1072  if( !SCIPisZero(scip, objcoef) )
1073  {
1074  SCIP_CALL( SCIPchgVarObjProbing(scip, propdata->bounds[i]->var, objcoef) );
1075 
1076  /* store nontrivial objective coefficients */
1077  objcoefs[nobjcoefs] = objcoef;
1078  objcoefsinds[nobjcoefs] = i;
1079  ++nobjcoefs;
1080  }
1081  }
1082  }
1083 
1084  do
1085  {
1086  SCIPdebugMsg(scip, "doing an upper bounds round\n");
1087  SCIP_CALL( filterRound(scip, propdata, nleftiterations, &nfiltered, objcoefs, objcoefsinds, nobjcoefs) );
1088  SCIPdebugMsg(scip, "filtered %d more bounds in upper bounds round\n", nfiltered);
1089  ntotalfiltered += nfiltered;
1090  /* update iterations left */
1091  nleftiterations = getIterationsLeft(scip, nolditerations, itlimit);
1092  }
1093  while( nfiltered >= propdata->nminfilter && ( nleftiterations == -1 || nleftiterations > 0 ) );
1094 
1095  SCIPdebugMsg(scip, "filtered %d this round\n", ntotalfiltered);
1096  propdata->nfiltered += ntotalfiltered;
1097 
1098  /* free array */
1099  SCIPfreeBufferArray(scip, &objcoefsinds);
1100  SCIPfreeBufferArray(scip, &objcoefs);
1101 
1102  return SCIP_OKAY;
1103 }
1104 
1105 /** applies possible bound changes that were found */
1106 static
1107 SCIP_RETCODE applyBoundChgs(
1108  SCIP* scip, /**< SCIP data structure */
1109  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
1110  SCIP_RESULT* result /**< result pointer */
1111  )
1112 {
1113 #ifdef SCIP_DEBUG
1114  int ntightened; /* stores the number of successful bound changes */
1115 #endif
1116  int i;
1117 
1118  assert(scip != NULL);
1119  assert(!SCIPinProbing(scip));
1120  assert(propdata != NULL);
1121  assert(result != NULL);
1122  assert(*result == SCIP_DIDNOTFIND);
1123 
1124  SCIPdebug( ntightened = 0 );
1125 
1126  for( i = 0; i < propdata->nbounds; i++ )
1127  {
1128  BOUND* bound; /* shortcut to the current bound */
1129  SCIP_Bool infeas; /* stores wether a tightening approach forced an infeasibilty */
1130  SCIP_Bool tightened; /* stores wether a tightening approach was successful */
1131 
1132  bound = propdata->bounds[i];
1133 
1134  if( bound->found )
1135  {
1136  SCIPdebug( double oldbound = (bound->boundtype == SCIP_BOUNDTYPE_LOWER)
1137  ? SCIPvarGetLbLocal(bound->var)
1138  : SCIPvarGetUbLocal(bound->var) );
1139 
1140  if( bound->boundtype == SCIP_BOUNDTYPE_LOWER )
1141  {
1142  SCIP_CALL( SCIPtightenVarLb(scip, bound->var, bound->newval, FALSE, &infeas, &tightened) );
1143  }
1144  else
1145  {
1146  SCIP_CALL( SCIPtightenVarUb(scip, bound->var, bound->newval, FALSE, &infeas, &tightened) );
1147  }
1148 
1149  /* handle information about the success */
1150  if( infeas )
1151  {
1152  *result = SCIP_CUTOFF;
1153  SCIPdebugMsg(scip, "cut off\n");
1154  break;
1155  }
1156 
1157  if( tightened )
1158  {
1159  SCIPdebug( SCIPdebugMsg(scip, "tightended: %s old: %e new: %e\n" , SCIPvarGetName(bound->var), oldbound,
1160  bound->newval) );
1161  *result = SCIP_REDUCEDDOM;
1162  SCIPdebug( ntightened++ );
1163  }
1164  }
1165  }
1166 
1167  SCIPdebug( SCIPdebugMsg(scip, "tightened bounds: %d\n", ntightened) );
1168 
1169  return SCIP_OKAY;
1170 }
1171 
1172 /** tries to tighten a bound in probing mode */
1173 static
1174 SCIP_RETCODE tightenBoundProbing(
1175  SCIP* scip, /**< SCIP data structure */
1176  BOUND* bound, /**< bound that could be tightened */
1177  SCIP_Real newval, /**< new bound value */
1178  SCIP_Bool* tightened /**< was tightening successful? */
1179  )
1180 {
1181  SCIP_Real lb;
1182  SCIP_Real ub;
1183 
1184  assert(scip != NULL);
1185  assert(SCIPinProbing(scip));
1186  assert(bound != NULL);
1187  assert(tightened != NULL);
1188 
1189  *tightened = FALSE;
1190 
1191  /* get old bounds */
1192  lb = SCIPvarGetLbLocal(bound->var);
1193  ub = SCIPvarGetUbLocal(bound->var);
1194 
1195  if( bound->boundtype == SCIP_BOUNDTYPE_LOWER )
1196  {
1197  /* round bounds new value if variable is integral */
1198  if( SCIPvarIsIntegral(bound->var) )
1199  newval = SCIPceil(scip, newval);
1200 
1201  /* ensure that we give consistent bounds to the LP solver */
1202  if( newval > ub )
1203  newval = ub;
1204 
1205  /* tighten if really better */
1206  if( SCIPisLbBetter(scip, newval, lb, ub) )
1207  {
1208  SCIP_CALL( SCIPchgVarLbProbing(scip, bound->var, newval) );
1209  *tightened = TRUE;
1210  }
1211  }
1212  else
1213  {
1214  /* round bounds new value if variable is integral */
1215  if( SCIPvarIsIntegral(bound->var) )
1216  newval = SCIPfloor(scip, newval);
1217 
1218  /* ensure that we give consistent bounds to the LP solver */
1219  if( newval < lb )
1220  newval = lb;
1221 
1222  /* tighten if really better */
1223  if( SCIPisUbBetter(scip, newval, lb, ub) )
1224  {
1225  SCIP_CALL( SCIPchgVarUbProbing(scip, bound->var, newval) );
1226  *tightened = TRUE;
1227  }
1228  }
1229 
1230  return SCIP_OKAY;
1231 }
1232 
1233 /** comparison method for two bounds w.r.t. their scores */
1234 static
1235 SCIP_DECL_SORTPTRCOMP(compBoundsScore)
1236 {
1237  BOUND* bound1 = (BOUND*) elem1;
1238  BOUND* bound2 = (BOUND*) elem2;
1239 
1240  return bound1->score == bound2->score ? 0 : ( bound1->score > bound2->score ? 1 : -1 );
1241 }
1242 
1243 /** comparison method for two bounds w.r.t. their boundtype */
1244 static
1245 SCIP_DECL_SORTPTRCOMP(compBoundsBoundtype)
1246 {
1247  int diff;
1248  BOUND* bound1 = (BOUND*) elem1;
1249  BOUND* bound2 = (BOUND*) elem2;
1250 
1251  /* prioritize undone bounds */
1252  diff = (!bound1->done ? 1 : 0) - (!bound2->done ? 1 : 0);
1253  if( diff != 0 )
1254  return diff;
1255 
1256  /* prioritize unfiltered bounds */
1257  diff = (!bound1->filtered ? 1 : 0) - (!bound2->filtered ? 1 : 0);
1258  if( diff != 0 )
1259  return diff;
1260 
1261  diff = (bound1->boundtype == SCIP_BOUNDTYPE_LOWER ? 1 : 0) - (bound2->boundtype == SCIP_BOUNDTYPE_LOWER ? 1 : 0);
1262 
1263  if( diff == 0 )
1264  return (bound1->score == bound2->score) ? 0 : (bound1->score > bound2->score ? 1 : -1);
1265  else
1266  return diff;
1267 }
1268 
1269 /** sort the propdata->bounds array with their distance or their boundtype key */
1270 static
1271 SCIP_RETCODE sortBounds(
1272  SCIP* scip, /**< SCIP data structure */
1273  SCIP_PROPDATA* propdata /**< propagator data */
1274  )
1275 {
1276  assert(scip != NULL);
1277  assert(propdata != NULL);
1278 
1279  SCIPdebugMsg(scip, "sort bounds\n");
1280  SCIPsortDownPtr((void**) propdata->bounds, compBoundsBoundtype, propdata->nbounds);
1281 
1282  return SCIP_OKAY;
1283 }
1284 
1285 /** evaluates a bound for the current LP solution */
1286 static
1287 SCIP_Real evalBound(
1288  SCIP* scip,
1289  BOUND* bound
1290  )
1291 {
1292  assert(scip != NULL);
1293  assert(bound != NULL);
1294 
1295  if( bound->boundtype == SCIP_BOUNDTYPE_LOWER )
1296  return REALABS( SCIPvarGetLPSol(bound->var) - SCIPvarGetLbLocal(bound->var) );
1297  else
1298  return REALABS( SCIPvarGetUbLocal(bound->var) - SCIPvarGetLPSol(bound->var) );
1299 }
1300 
1301 /** returns the index of the next undone and unfiltered bound with the smallest distance */
1302 static
1303 int nextBound(
1304  SCIP* scip, /**< SCIP data structure */
1305  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
1306  SCIP_Bool convexphase /**< consider only convex variables? */
1307  )
1308 {
1309  SCIP_Real bestval;
1310  int bestidx;
1311  int k;
1312 
1313  assert(scip != NULL);
1314  assert(propdata != NULL);
1315 
1316  bestidx = -1;
1317  bestval = SCIPinfinity(scip);
1318 
1319  for( k = 0; k <= propdata->lastidx; ++k )
1320  {
1321  BOUND* tmpbound;
1322  tmpbound = propdata->bounds[k];
1323 
1324  assert(tmpbound != NULL);
1325 
1326  if( !tmpbound->filtered && !tmpbound->done && (tmpbound->nonconvex == !convexphase) )
1327  {
1328  SCIP_Real boundval;
1329 
1330  /* return the next bound which is not done or unfiltered yet */
1331  if( propdata->orderingalgo == 0 )
1332  return k;
1333 
1334  boundval = evalBound(scip, tmpbound);
1335 
1336  /* negate boundval if we use the reverse greedy algorithm */
1337  boundval = (propdata->orderingalgo == 2) ? -1.0 * boundval : boundval;
1338 
1339  if( bestidx == -1 || boundval < bestval )
1340  {
1341  bestidx = k;
1342  bestval = boundval;
1343  }
1344  }
1345  }
1346 
1347  return bestidx;
1348 }
1349 
1350 /** try to separate the solution of the last OBBT LP in order to learn better variable bounds; we apply additional
1351  * separation rounds as long as the routine finds better bounds; because of dual degeneracy we apply a minimum number of
1352  * separation rounds
1353  */
1354 static
1355 SCIP_RETCODE applySeparation(
1356  SCIP* scip, /**< SCIP data structure */
1357  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
1358  BOUND* currbound, /**< current bound */
1359  SCIP_Longint* nleftiterations, /**< number of left iterations (-1 for no limit) */
1360  SCIP_Bool* success /**< pointer to store if we have found a better bound */
1361  )
1362 {
1363  SCIP_Bool inroot;
1364  int i;
1365 
1366  assert(nleftiterations != NULL);
1367  assert(success != NULL);
1368  assert(SCIPinProbing(scip));
1369 
1370  *success = FALSE;
1371 
1372  /* check if we are originally in the root node */
1373  inroot = SCIPgetDepth(scip) == 1;
1374 
1375  for( i = 0; i <= propdata->sepamaxiter; ++i )
1376  {
1377  SCIP_Longint nlpiter;
1378  SCIP_Real oldval;
1379  SCIP_Bool cutoff;
1380  SCIP_Bool delayed;
1381  SCIP_Bool error;
1382  SCIP_Bool optimal;
1383  SCIP_Bool tightened;
1384 
1385  oldval = SCIPvarGetLPSol(currbound->var);
1386 
1387  /* find and store cuts to separate the current LP solution */
1388  SCIP_CALL( SCIPseparateSol(scip, NULL, inroot, FALSE, &delayed, &cutoff) );
1389  SCIPdebugMsg(scip, "applySeparation() - ncuts = %d\n", SCIPgetNCuts(scip));
1390 
1391  /* leave if we did not found any cut */
1392  if( SCIPgetNCuts(scip) == 0 )
1393  break;
1394 
1395  /* apply cuts and resolve LP */
1396  SCIP_CALL( SCIPapplyCutsProbing(scip, &cutoff) );
1397  assert(SCIPgetNCuts(scip) == 0);
1398  SCIPdebug( nlpiter = SCIPgetNLPIterations(scip); )
1399  SCIP_CALL( solveLP(scip, (int) *nleftiterations, &error, &optimal) );
1400  SCIPdebug( nlpiter = SCIPgetNLPIterations(scip) - nlpiter; )
1401  SCIPdebugMsg(scip, "applySeparation() - optimal=%u error=%u lpiter=%" SCIP_LONGINT_FORMAT "\n", optimal, error, nlpiter);
1402  SCIPdebugMsg(scip, "oldval = %e newval = %e\n", oldval, SCIPvarGetLPSol(currbound->var));
1403 
1404  /* leave if we did not solve the LP to optimality or an error occured */
1405  if( error || !optimal )
1406  break;
1407 
1408  /* try to generate a genvbound */
1409  if( inroot && propdata->genvboundprop != NULL && propdata->genvbdsduringsepa )
1410  {
1411  SCIP_Bool found;
1412  SCIP_CALL( createGenVBound(scip, propdata, currbound, &found) );
1413  propdata->ngenvboundsprobing += found ? 1 : 0;
1414  }
1415 
1416  /* try to tight the variable bound */
1417  tightened = FALSE;
1418  if( !SCIPisEQ(scip, oldval, SCIPvarGetLPSol(currbound->var)) )
1419  {
1420  SCIP_CALL( tightenBoundProbing(scip, currbound, SCIPvarGetLPSol(currbound->var), &tightened) );
1421  SCIPdebugMsg(scip, "apply separation - tightened=%u oldval=%e newval=%e\n", tightened, oldval,
1422  SCIPvarGetLPSol(currbound->var));
1423 
1424  *success |= tightened;
1425  }
1426 
1427  /* leave the separation if we did not tighten the bound and proceed at least propdata->sepaminiter iterations */
1428  if( !tightened && i >= propdata->sepaminiter )
1429  break;
1430  }
1431 
1432  return SCIP_OKAY;
1433 }
1434 
1435 /** finds new variable bounds until no iterations left or all bounds have been checked */
1436 static
1437 SCIP_RETCODE findNewBounds(
1438  SCIP* scip, /**< SCIP data structure */
1439  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
1440  SCIP_Longint* nleftiterations, /**< pointer to store the number of left iterations */
1441  SCIP_Bool convexphase /**< consider only convex variables? */
1442  )
1443 {
1444  SCIP_Longint nolditerations;
1445  SCIP_Bool iterationsleft;
1446  BOUND* currbound;
1447  SCIP_Longint itlimit;
1448  int nextboundidx;
1449 
1450  assert(scip != NULL);
1451  assert(propdata != NULL);
1452  assert(nleftiterations != NULL);
1453 
1454  /* update the number of left iterations */
1455  nolditerations = SCIPgetNLPIterations(scip);
1456  itlimit = *nleftiterations;
1457  assert(*nleftiterations == getIterationsLeft(scip, nolditerations, itlimit));
1458  iterationsleft = (*nleftiterations == -1) || (*nleftiterations > 0);
1459 
1460  /* To improve the performance we sort the bound in such a way that the undone and
1461  * unfiltered bounds are at the end of propdata->bounds. We calculate and update
1462  * the position of the last unfiltered and undone bound in propdata->lastidx
1463  */
1464  if( !convexphase )
1465  {
1466  /* sort bounds */
1467  SCIP_CALL( sortBounds(scip, propdata) );
1468 
1469  /* if the first bound is filtered or done then there is no bound left */
1470  if( propdata->bounds[0]->done || propdata->bounds[0]->filtered )
1471  {
1472  SCIPdebugMsg(scip, "no unprocessed/unfiltered bound left\n");
1473  return SCIP_OKAY;
1474  }
1475 
1476  /* compute the last undone and unfiltered node */
1477  propdata->lastidx = 0;
1478  while( propdata->lastidx < propdata->nbounds - 1 && !propdata->bounds[propdata->lastidx]->done &&
1479  !propdata->bounds[propdata->lastidx]->filtered )
1480  ++propdata->lastidx;
1481 
1482  SCIPdebugMsg(scip, "lastidx = %d\n", propdata->lastidx);
1483  }
1484 
1485  /* find the first unprocessed bound */
1486  nextboundidx = nextBound(scip, propdata, convexphase);
1487 
1488  /* skip if there is no bound left */
1489  if( nextboundidx == -1 )
1490  {
1491  SCIPdebugMsg(scip, "no unprocessed/unfiltered bound left\n");
1492  return SCIP_OKAY;
1493  }
1494 
1495  currbound = propdata->bounds[nextboundidx];
1496  assert(!currbound->done && !currbound->filtered);
1497 
1498  /* main loop */
1499  while( iterationsleft && !SCIPisStopped(scip) )
1500  {
1501  SCIP_Bool optimal;
1502  SCIP_Bool error;
1503  int nfiltered;
1504 
1505  assert(currbound != NULL);
1506  assert(currbound->done == FALSE);
1507  assert(currbound->filtered == FALSE);
1508 
1509  /* do not visit currbound more than once */
1510  currbound->done = TRUE;
1511  exchangeBounds(propdata, nextboundidx);
1512 
1513  /* set objective for curr */
1514  SCIP_CALL( setObjProbing(scip, propdata, currbound, 1.0) );
1515 
1516  SCIPdebugMsg(scip, "before solving Boundtype: %d , LB: %e , UB: %e\n",
1517  currbound->boundtype == SCIP_BOUNDTYPE_LOWER, SCIPvarGetLbLocal(currbound->var),
1518  SCIPvarGetUbLocal(currbound->var) );
1519  SCIPdebugMsg(scip, "before solving var <%s>, LP value: %f\n",
1520  SCIPvarGetName(currbound->var), SCIPvarGetLPSol(currbound->var));
1521 
1522  SCIPdebugMsg(scip, "probing iterations before solve: %lld \n", SCIPgetNLPIterations(scip));
1523 
1524  propdata->nprobingiterations -= SCIPgetNLPIterations(scip);
1525 
1526  /* now solve the LP */
1527  SCIP_CALL( solveLP(scip, (int) *nleftiterations, &error, &optimal) );
1528 
1529  propdata->nprobingiterations += SCIPgetNLPIterations(scip);
1530  propdata->nsolvedbounds++;
1531 
1532  SCIPdebugMsg(scip, "probing iterations after solve: %lld \n", SCIPgetNLPIterations(scip));
1533  SCIPdebugMsg(scip, "OPT: %u ERROR: %u\n" , optimal, error);
1534  SCIPdebugMsg(scip, "after solving Boundtype: %d , LB: %e , UB: %e\n",
1535  currbound->boundtype == SCIP_BOUNDTYPE_LOWER, SCIPvarGetLbLocal(currbound->var),
1536  SCIPvarGetUbLocal(currbound->var) );
1537  SCIPdebugMsg(scip, "after solving var <%s>, LP value: %f\n",
1538  SCIPvarGetName(currbound->var), SCIPvarGetLPSol(currbound->var));
1539 
1540  /* update nleftiterations */
1541  *nleftiterations = getIterationsLeft(scip, nolditerations, itlimit);
1542  iterationsleft = (*nleftiterations == -1) || (*nleftiterations > 0);
1543 
1544  if( error )
1545  {
1546  SCIPdebugMsg(scip, "ERROR during LP solving\n");
1547 
1548  /* set the objective of currbound to zero to null the whole objective; otherwise the objective is wrong when
1549  * we call findNewBounds() for the convex phase
1550  */
1551  SCIP_CALL( SCIPchgVarObjProbing(scip, currbound->var, 0.0) );
1552 
1553  return SCIP_OKAY;
1554  }
1555 
1556  if( optimal )
1557  {
1558  SCIP_Bool success;
1559 
1560  currbound->newval = SCIPvarGetLPSol(currbound->var);
1561  currbound->found = TRUE;
1562 
1563  /* in root node we may want to create a genvbound (independent of tightening success) */
1564  if( (SCIPgetDepth(scip) == 0 || (SCIPinProbing(scip) && SCIPgetDepth(scip) == 1))
1565  && propdata->genvboundprop != NULL )
1566  {
1567  SCIP_Bool found;
1568 
1569  SCIP_CALL( createGenVBound(scip, propdata, currbound, &found) );
1570 
1571  if( found )
1572  propdata->ngenvboundsprobing += 1;
1573  }
1574 
1575  /* try to tighten bound in probing mode */
1576  success = FALSE;
1577  if( propdata->tightintboundsprobing && SCIPvarIsIntegral(currbound->var) )
1578  {
1579  SCIPdebugMsg(scip, "tightening bound %s = %e bounds: [%e, %e]\n", SCIPvarGetName(currbound->var),
1580  currbound->newval, SCIPvarGetLbLocal(currbound->var), SCIPvarGetUbLocal(currbound->var) );
1581  SCIP_CALL( tightenBoundProbing(scip, currbound, currbound->newval, &success) );
1582  SCIPdebugMsg(scip, "tightening bound %s\n", success ? "successful" : "not successful");
1583  }
1584  else if( propdata->tightcontboundsprobing && !SCIPvarIsIntegral(currbound->var) )
1585  {
1586  SCIPdebugMsg(scip, "tightening bound %s = %e bounds: [%e, %e]\n", SCIPvarGetName(currbound->var),
1587  currbound->newval, SCIPvarGetLbLocal(currbound->var), SCIPvarGetUbLocal(currbound->var) );
1588  SCIP_CALL( tightenBoundProbing(scip, currbound, currbound->newval, &success) );
1589  SCIPdebugMsg(scip, "tightening bound %s\n", success ? "successful" : "not successful");
1590  }
1591 
1592  /* separate current OBBT LP solution */
1593  if( iterationsleft && propdata->separatesol )
1594  {
1595  propdata->nprobingiterations -= SCIPgetNLPIterations(scip);
1596  SCIP_CALL( applySeparation(scip, propdata, currbound, nleftiterations, &success) );
1597  propdata->nprobingiterations += SCIPgetNLPIterations(scip);
1598 
1599  /* remember best solution value after solving additional separations LPs */
1600  if( success )
1601  {
1602 #ifndef NDEBUG
1603  SCIP_Real newval = SCIPvarGetLPSol(currbound->var);
1604 
1605  /* round new bound if the variable is integral */
1606  if( SCIPvarIsIntegral(currbound->var) )
1607  newval = currbound->boundtype == SCIP_BOUNDTYPE_LOWER ?
1608  SCIPceil(scip, newval) : SCIPfloor(scip, newval);
1609 
1610  assert((currbound->boundtype == SCIP_BOUNDTYPE_LOWER &&
1611  SCIPisGT(scip, newval, currbound->newval))
1612  || (currbound->boundtype == SCIP_BOUNDTYPE_UPPER &&
1613  SCIPisLT(scip, newval, currbound->newval)));
1614 #endif
1615 
1616  currbound->newval = SCIPvarGetLPSol(currbound->var);
1617  }
1618  }
1619 
1620  /* filter bound candidates by using the current LP solution */
1621  if( propdata->applytrivialfilter )
1622  {
1623  SCIP_CALL( filterExistingLP(scip, propdata, &nfiltered, currbound) );
1624  SCIPdebugMsg(scip, "filtered %d bounds via inspecting present LP solution\n", nfiltered);
1625  propdata->ntrivialfiltered += nfiltered;
1626  }
1627 
1628  propdata->propagatecounter += success ? 1 : 0;
1629 
1630  /* propagate if we have found enough bound tightenings */
1631  if( propdata->propagatefreq != 0 && propdata->propagatecounter >= propdata->propagatefreq )
1632  {
1633  SCIP_Longint ndomredsfound;
1634  SCIP_Bool cutoff;
1635 
1636  SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, &ndomredsfound) );
1637  SCIPdebugMsg(scip, "propagation - cutoff %u ndomreds %" SCIP_LONGINT_FORMAT "\n", cutoff, ndomredsfound);
1638 
1639  propdata->npropagatedomreds += ndomredsfound;
1640  propdata->propagatecounter = 0;
1641  }
1642  }
1643 
1644  /* set objective to zero */
1645  SCIP_CALL( setObjProbing(scip, propdata, currbound, 0.0) );
1646 
1647  /* find the first unprocessed bound */
1648  nextboundidx = nextBound(scip, propdata, convexphase);
1649 
1650  /* check if there is no unprocessed and unfiltered node left */
1651  if( nextboundidx == -1 )
1652  {
1653  SCIPdebugMsg(scip, "NO unvisited/unfiltered bound left!\n");
1654  break;
1655  }
1656 
1657  currbound = propdata->bounds[nextboundidx];
1658  assert(!currbound->done && !currbound->filtered);
1659  }
1660 
1661  if( iterationsleft )
1662  {
1663  SCIPdebugMsg(scip, "still iterations left: %" SCIP_LONGINT_FORMAT "\n", *nleftiterations);
1664  }
1665  else
1666  {
1667  SCIPdebugMsg(scip, "no iterations left\n");
1668  }
1669 
1670  return SCIP_OKAY;
1671 }
1672 
1673 
1674 /** main function of obbt */
1675 static
1676 SCIP_RETCODE applyObbt(
1677  SCIP* scip, /**< SCIP data structure */
1678  SCIP_PROPDATA* propdata, /**< data of the obbt propagator */
1679  SCIP_Longint itlimit, /**< LP iteration limit (-1: no limit) */
1680  SCIP_RESULT* result /**< result pointer */
1681  )
1682 {
1683  SCIP_VAR** vars;
1684  SCIP_Real* oldlbs;
1685  SCIP_Real* oldubs;
1686  SCIP_Longint lastnpropagatedomreds;
1687  SCIP_Longint nleftiterations;
1688  SCIP_Real oldconditionlimit;
1689  SCIP_Real oldboundstreps;
1690  SCIP_Real olddualfeastol;
1691  SCIP_Bool hasconditionlimit;
1692  SCIP_Bool continuenode;
1693  SCIP_Bool boundleft;
1694  int nfiltered;
1695  int nvars;
1696  int i;
1697 
1698  assert(scip != NULL);
1699  assert(propdata != NULL);
1700  assert(itlimit == -1 || itlimit >= 0);
1701 
1702  SCIPdebugMsg(scip, "apply obbt\n");
1703 
1704  oldlbs = NULL;
1705  oldubs = NULL;
1706  lastnpropagatedomreds = propdata->npropagatedomreds;
1707  nleftiterations = itlimit;
1708  continuenode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) == propdata->lastnode;
1709  propdata->lastidx = -1;
1710  boundleft = FALSE;
1711  *result = SCIP_DIDNOTFIND;
1712 
1713  /* store old variable bounds if we use propagation during obbt */
1714  if( propdata->propagatefreq > 0 )
1715  {
1716  SCIP_CALL( SCIPallocBufferArray(scip, &oldlbs, propdata->nbounds) );
1717  SCIP_CALL( SCIPallocBufferArray(scip, &oldubs, propdata->nbounds) );
1718  }
1719 
1720  /* reset bound data structure flags; fixed variables are marked as filtered */
1721  for( i = 0; i < propdata->nbounds; i++ )
1722  {
1723  BOUND* bound = propdata->bounds[i];
1724  bound->found = FALSE;
1725 
1726  /* store old variable bounds */
1727  if( oldlbs != NULL && oldubs != NULL )
1728  {
1729  oldlbs[bound->index] = SCIPvarGetLbLocal(bound->var);
1730  oldubs[bound->index] = SCIPvarGetUbLocal(bound->var);
1731  }
1732 
1733  /* reset 'done' and 'filtered' flag in a new B&B node */
1734  if( !continuenode )
1735  {
1736  bound->done = FALSE;
1737  bound->filtered = FALSE;
1738  }
1739 
1740  /* mark fixed variables as filtered */
1741  bound->filtered |= varIsFixedLocal(scip, bound->var);
1742 
1743  /* check for an unprocessed bound */
1744  if( !bound->filtered && !bound->done )
1745  boundleft = TRUE;
1746  }
1747 
1748  /* no bound left to check */
1749  if( !boundleft )
1750  goto TERMINATE;
1751 
1752  /* filter variables via inspecting present LP solution */
1753  if( propdata->applytrivialfilter && !continuenode )
1754  {
1755  SCIP_CALL( filterExistingLP(scip, propdata, &nfiltered, NULL) );
1756  SCIPdebugMsg(scip, "filtered %d bounds via inspecting present LP solution\n", nfiltered);
1757  propdata->ntrivialfiltered += nfiltered;
1758  }
1759 
1760  /* store old dualfeasibletol */
1761  olddualfeastol = SCIPdualfeastol(scip);
1762 
1763  /* start probing */
1764  SCIP_CALL( SCIPstartProbing(scip) );
1765  SCIPdebugMsg(scip, "start probing\n");
1766 
1767  /* tighten dual feastol */
1768  if( propdata->dualfeastol < olddualfeastol )
1769  {
1770  SCIP_CALL( SCIPchgDualfeastol(scip, propdata->dualfeastol) );
1771  }
1772 
1773  /* tighten condition limit */
1774  hasconditionlimit = (SCIPgetRealParam(scip, "lp/conditionlimit", &oldconditionlimit) == SCIP_OKAY);
1775  if( !hasconditionlimit )
1776  {
1777  SCIPwarningMessage(scip, "obbt propagator could not set condition limit in LP solver - running without\n");
1778  }
1779  else if( propdata->conditionlimit > 0.0 && (oldconditionlimit < 0.0 || propdata->conditionlimit < oldconditionlimit) )
1780  {
1781  SCIP_CALL( SCIPsetRealParam(scip, "lp/conditionlimit", propdata->conditionlimit) );
1782  }
1783 
1784  /* tighten relative bound improvement limit */
1785  SCIP_CALL( SCIPgetRealParam(scip, "numerics/boundstreps", &oldboundstreps) );
1786  if( !SCIPisEQ(scip, oldboundstreps, propdata->boundstreps) )
1787  {
1788  SCIP_CALL( SCIPsetRealParam(scip, "numerics/boundstreps", propdata->boundstreps) );
1789  }
1790 
1791  /* add objective cutoff */
1792  SCIP_CALL( addObjCutoff(scip, propdata) );
1793 
1794  /* apply filtering */
1795  if( propdata->applyfilterrounds )
1796  {
1797  SCIP_CALL( filterBounds(scip, propdata, nleftiterations) );
1798  }
1799 
1800  /* set objective coefficients to zero */
1801  vars = SCIPgetVars(scip);
1802  nvars = SCIPgetNVars(scip);
1803  for( i = 0; i < nvars; ++i )
1804  {
1805  /* note that it is not possible to change the objective of non-column variables during probing; we have to take
1806  * care of the objective contribution of loose variables in createGenVBound()
1807  */
1808  if( SCIPvarGetObj(vars[i]) != 0.0 && SCIPvarGetStatus(vars[i]) == SCIP_VARSTATUS_COLUMN )
1809  {
1810  SCIP_CALL( SCIPchgVarObjProbing(scip, vars[i], 0.0) );
1811  }
1812  }
1813 
1814  /* find new bounds for the variables */
1815  SCIP_CALL( findNewBounds(scip, propdata, &nleftiterations, FALSE) );
1816 
1817  if( nleftiterations > 0 || itlimit < 0 )
1818  {
1819  SCIP_CALL( findNewBounds(scip, propdata, &nleftiterations, TRUE) );
1820  }
1821 
1822  /* reset dual feastol and condition limit */
1823  SCIP_CALL( SCIPchgDualfeastol(scip, olddualfeastol) );
1824  if( hasconditionlimit )
1825  {
1826  SCIP_CALL( SCIPsetRealParam(scip, "lp/conditionlimit", oldconditionlimit) );
1827  }
1828 
1829  /* update bound->newval if we have learned additional bound tightenings during SCIPpropagateProbing() */
1830  if( oldlbs != NULL && oldubs != NULL && propdata->npropagatedomreds - lastnpropagatedomreds > 0 )
1831  {
1832  assert(propdata->propagatefreq > 0);
1833  for( i = 0; i < propdata->nbounds; ++i )
1834  {
1835  BOUND* bound = propdata->bounds[i];
1836 
1837  /* it might be the case that a bound found by the additional propagation is better than the bound found after solving an OBBT
1838  * LP
1839  */
1840  if( bound->found )
1841  {
1842  if( bound->boundtype == SCIP_BOUNDTYPE_LOWER )
1843  bound->newval = MAX(bound->newval, SCIPvarGetLbLocal(bound->var)); /*lint !e666*/
1844  else
1845  bound->newval = MIN(bound->newval, SCIPvarGetUbLocal(bound->var)); /*lint !e666*/
1846  }
1847  else
1848  {
1849  SCIP_Real oldlb;
1850  SCIP_Real oldub;
1851 
1852  oldlb = oldlbs[bound->index];
1853  oldub = oldubs[bound->index];
1854 
1855  if( bound->boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisLbBetter(scip, SCIPvarGetLbLocal(bound->var), oldlb, oldub) )
1856  {
1857  SCIPdebugMsg(scip, "tighter lower bound due to propagation: %d - %e -> %e\n", i, oldlb, SCIPvarGetLbLocal(bound->var));
1858  bound->newval = SCIPvarGetLbLocal(bound->var);
1859  bound->found = TRUE;
1860  }
1861 
1862  if( bound->boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisUbBetter(scip, SCIPvarGetUbLocal(bound->var), oldlb, oldub) )
1863  {
1864  SCIPdebugMsg(scip, "tighter upper bound due to propagation: %d - %e -> %e\n", i, oldub, SCIPvarGetUbLocal(bound->var));
1865  bound->newval = SCIPvarGetUbLocal(bound->var);
1866  bound->found = TRUE;
1867  }
1868  }
1869  }
1870  }
1871 
1872  /* reset relative bound improvement limit */
1873  SCIP_CALL( SCIPsetRealParam(scip, "numerics/boundstreps", oldboundstreps) );
1874 
1875  /* end probing */
1876  SCIP_CALL( SCIPendProbing(scip) );
1877  SCIPdebugMsg(scip, "end probing!\n");
1878 
1879  /* release cutoff row if there is one */
1880  if( propdata->cutoffrow != NULL )
1881  {
1882  assert(!SCIProwIsInLP(propdata->cutoffrow));
1883  SCIP_CALL( SCIPreleaseRow(scip, &(propdata->cutoffrow)) );
1884  }
1885 
1886  /* apply buffered bound changes */
1887  SCIP_CALL( applyBoundChgs(scip, propdata, result) );
1888 
1889 TERMINATE:
1890  SCIPfreeBufferArrayNull(scip, &oldubs);
1891  SCIPfreeBufferArrayNull(scip, &oldlbs);
1892 
1893  return SCIP_OKAY;
1894 }
1895 
1896 /** computes the score of a bound */
1897 static
1898 unsigned int getScore(
1899  SCIP* scip, /**< SCIP data structure */
1900  BOUND* bound, /**< pointer of bound */
1901  int nlcount, /**< number of nonlinear constraints containing the bounds variable */
1902  int maxnlcount /**< maximal number of nonlinear constraints a variable appears in */
1903  )
1904 {
1905  unsigned int score; /* score to be computed */
1906 
1907  assert(scip != NULL);
1908  assert(bound != NULL);
1909  assert(nlcount >= 0);
1910  assert(maxnlcount >= nlcount);
1911 
1912  /* score = ( nlcount * ( BASE - 1 ) / maxnlcount ) * BASE^2 + vartype * BASE + boundtype */
1913  score = (unsigned int) ( nlcount > 0 ? (OBBT_SCOREBASE * nlcount * ( OBBT_SCOREBASE - 1 )) / maxnlcount : 0 );
1914  switch( SCIPvarGetType(bound->var) )
1915  {
1916  case SCIP_VARTYPE_INTEGER:
1917  score += 1;
1918  break;
1919  case SCIP_VARTYPE_IMPLINT:
1920  score += 2;
1921  break;
1922  case SCIP_VARTYPE_CONTINUOUS:
1923  score += 3;
1924  break;
1925  case SCIP_VARTYPE_BINARY:
1926  score += 4;
1927  break;
1928  default:
1929  break;
1930  }
1931 
1932  score *= OBBT_SCOREBASE;
1933  if( bound->boundtype == SCIP_BOUNDTYPE_UPPER )
1934  score += 1;
1935 
1936  return score;
1937 }
1938 
1939 /** count the variables which appear in non-convex term of nlrow */
1940 static
1941 SCIP_RETCODE countNLRowVarsNonConvexity(
1942  SCIP* scip, /**< SCIP data structure */
1943  int* nlcounts, /**< store the number each variable appears in a
1944  * non-convex term */
1945  SCIP_NLROW* nlrow /**< nonlinear row */
1946  )
1947 {
1948  int t;
1949  int nexprtreevars;
1950  SCIP_VAR** exprtreevars;
1951  SCIP_EXPRTREE* exprtree;
1952 
1953  assert(scip != NULL);
1954  assert(nlcounts != NULL);
1955  assert(nlrow != NULL);
1956 
1957  /* go through all quadratic terms */
1958  for( t = SCIPnlrowGetNQuadElems(nlrow) - 1; t >= 0; --t )
1959  {
1960  SCIP_QUADELEM* quadelem;
1961  SCIP_VAR* bilinvar1;
1962  SCIP_VAR* bilinvar2;
1963 
1964  /* get quadratic term */
1965  quadelem = &SCIPnlrowGetQuadElems(nlrow)[t];
1966 
1967  /* get involved variables */
1968  bilinvar1 = SCIPnlrowGetQuadVars(nlrow)[quadelem->idx1];
1969  bilinvar2 = SCIPnlrowGetQuadVars(nlrow)[quadelem->idx2];
1970 
1971  assert(bilinvar1 != NULL);
1972  assert(bilinvar2 != NULL);
1973 
1974  /* we have a non-convex square term */
1975  if( bilinvar1 == bilinvar2 && !(quadelem->coef >= 0 ? SCIPisInfinity(scip, -SCIPnlrowGetLhs(nlrow)) : SCIPisInfinity(scip, SCIPnlrowGetRhs(nlrow))) )
1976  {
1977  ++nlcounts[SCIPvarGetProbindex(bilinvar1)];
1978  ++nlcounts[SCIPvarGetProbindex(bilinvar2)];
1979  }
1980 
1981  /* bilinear terms are in general non-convex */
1982  if( bilinvar1 != bilinvar2 )
1983  {
1984  ++nlcounts[SCIPvarGetProbindex(bilinvar1)];
1985  ++nlcounts[SCIPvarGetProbindex(bilinvar2)];
1986  }
1987  }
1988 
1989  exprtree = SCIPnlrowGetExprtree(nlrow);
1990  if( exprtree != NULL )
1991  {
1992  nexprtreevars = SCIPexprtreeGetNVars(exprtree);
1993  exprtreevars = SCIPexprtreeGetVars(exprtree);
1994 
1995  /* assume that the expression tree represents a non-convex constraint */
1996  for( t = 0; t < nexprtreevars; ++t)
1997  {
1998  SCIP_VAR* var;
1999  var = exprtreevars[t];
2000  assert(var != NULL);
2001 
2002  ++nlcounts[SCIPvarGetProbindex(var)];
2003  }
2004  }
2005 
2006  return SCIP_OKAY;
2007 }
2008 
2009 /** count how often each variable appears in a non-convex term */
2010 static
2011 SCIP_RETCODE getNLPVarsNonConvexity(
2012  SCIP* scip, /**< SCIP data structure */
2013  int* nlcounts /**< store the number each variable appears in a
2014  * non-convex term */
2015  )
2016 {
2017  SCIP_CONSHDLR* conshdlr;
2018  SCIP_CONS** conss;
2019  int nvars;
2020  int nconss;
2021  int i;
2022 
2023  assert(scip != NULL);
2024  assert(nlcounts != NULL);
2025 
2026  nvars = SCIPgetNVars(scip);
2027  BMSclearMemoryArray(nlcounts, nvars);
2028 
2029  /* quadratic constraint handler */
2030  conshdlr = SCIPfindConshdlr(scip, "quadratic");
2031  if( conshdlr != NULL )
2032  {
2033 
2034  /*SCIPdebugMsg(scip, "cons_quadratic is there!\n");*/
2035  nconss = SCIPconshdlrGetNActiveConss(conshdlr);
2036  conss = SCIPconshdlrGetConss(conshdlr);
2037 
2038  SCIPdebugMsg(scip, "nconss(quadratic) = %d\n", nconss);
2039 
2040  for( i = 0; i < nconss; ++i )
2041  {
2042  /* only check the nlrow if the constraint is not convex */
2043  if( SCIPisConvexQuadratic(scip, conss[i]) == FALSE )
2044  {
2045  SCIP_NLROW* nlrow;
2046  SCIP_CALL( SCIPgetNlRowQuadratic(scip, conss[i], &nlrow) );
2047  assert(nlrow != NULL);
2048 
2049  SCIP_CALL( countNLRowVarsNonConvexity(scip, nlcounts, nlrow) );
2050  }
2051  }
2052  }
2053 
2054  /* nonlinear constraint handler */
2055  conshdlr = SCIPfindConshdlr(scip, "nonlinear");
2056  if( conshdlr != NULL )
2057  {
2058  nconss = SCIPconshdlrGetNActiveConss(conshdlr);
2059  conss = SCIPconshdlrGetConss(conshdlr);
2060 
2061  SCIPdebugMsg(scip, "nconss(nonlinear) = %d\n", nconss);
2062 
2063  for( i = 0; i < nconss; ++i )
2064  {
2065  SCIP_EXPRCURV curvature;
2066  SCIP_CALL( SCIPgetCurvatureNonlinear(scip, conss[i], TRUE, &curvature) );
2067 
2068  /* only check the nlrow if the constraint is not convex */
2069  if( curvature != SCIP_EXPRCURV_CONVEX )
2070  {
2071  SCIP_NLROW* nlrow;
2072  SCIP_CALL( SCIPgetNlRowNonlinear(scip, conss[i], &nlrow) );
2073  assert(nlrow != NULL);
2074 
2075  SCIP_CALL( countNLRowVarsNonConvexity(scip, nlcounts, nlrow) );
2076  }
2077  }
2078  }
2079 
2080  /* bivariate constraint handler */
2081  conshdlr = SCIPfindConshdlr(scip, "bivariate");
2082  if( conshdlr != NULL )
2083  {
2084  nconss = SCIPconshdlrGetNActiveConss(conshdlr);
2085  conss = SCIPconshdlrGetConss(conshdlr);
2086 
2087  SCIPdebugMsg(scip, "nconss(bivariate) = %d\n", nconss);
2088 
2089  for( i = 0; i < nconss; ++i )
2090  {
2091  SCIP_EXPRCURV curvature;
2092  SCIP_INTERVAL* varbounds;
2093  SCIP_EXPRTREE* exprtree;
2094  int j;
2095 
2096  exprtree = SCIPgetExprtreeBivariate(scip, conss[i]);
2097  if( exprtree != NULL )
2098  {
2099  SCIP_CALL( SCIPallocBufferArray(scip, &varbounds, SCIPexprtreeGetNVars(exprtree)) );
2100  for( j = 0; j < SCIPexprtreeGetNVars(exprtree); ++j )
2101  {
2102  SCIP_VAR* var;
2103  var = SCIPexprtreeGetVars(exprtree)[j];
2104 
2105  SCIPintervalSetBounds(&varbounds[j],
2106  -infty2infty(SCIPinfinity(scip), INTERVALINFTY, -MIN(SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var))), /*lint !e666*/
2107  +infty2infty(SCIPinfinity(scip), INTERVALINFTY, MAX(SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var))) ); /*lint !e666*/
2108  }
2109 
2110  SCIP_CALL( SCIPexprtreeCheckCurvature(exprtree, SCIPinfinity(scip), varbounds, &curvature, NULL) );
2111 
2112  /* increase counter for all variables in the expression tree if the constraint is non-convex */
2113  if( curvature != SCIP_EXPRCURV_CONVEX )
2114  {
2115  for( j = 0; j < SCIPexprtreeGetNVars(exprtree); ++j )
2116  {
2117  SCIP_VAR* var;
2118  var = SCIPexprtreeGetVars(exprtree)[j];
2119 
2120  ++nlcounts[SCIPvarGetProbindex(var)];
2121  }
2122  }
2123  SCIPfreeBufferArray(scip, &varbounds);
2124  }
2125  }
2126  }
2127 
2128  /* abspower constraint handler */
2129  conshdlr = SCIPfindConshdlr(scip, "abspower");
2130  if( conshdlr != NULL )
2131  {
2132  nconss = SCIPconshdlrGetNActiveConss(conshdlr);
2133  conss = SCIPconshdlrGetConss(conshdlr);
2134 
2135  SCIPdebugMsg(scip, "nconss(abspower) = %d\n", nconss);
2136 
2137  for( i = 0; i < nconss; ++i )
2138  {
2139  /* constraint is non-convex in general */
2140  SCIP_NLROW* nlrow;
2141  SCIP_CALL( SCIPgetNlRowAbspower(scip, conss[i], &nlrow) );
2142  assert(nlrow != NULL);
2143 
2144  SCIP_CALL( countNLRowVarsNonConvexity(scip, nlcounts, nlrow) );
2145  }
2146  }
2147 
2148  return SCIP_OKAY;
2149 }
2150 
2151 
2152 /** determines whether a variable is interesting */
2153 static
2154 SCIP_Bool varIsInteresting(
2155  SCIP* scip, /**< SCIP data structure */
2156  SCIP_VAR* var, /**< variable to check */
2157  int nlcount /**< number of nonlinear constraints containing the variable
2158  * or number of non-convex terms containing the variable
2159  * (depends on propdata->onlynonconvexvars) */
2160  )
2161 {
2162  assert(SCIPgetDepth(scip) == 0);
2163 
2164  return !SCIPvarIsBinary(var) && SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN && nlcount > 0
2165  && !varIsFixedLocal(scip, var);
2166 }
2167 
2168 /** initializes interesting bounds */
2169 static
2170 SCIP_RETCODE initBounds(
2171  SCIP* scip, /**< SCIP data structure */
2172  SCIP_PROPDATA* propdata /**< data of the obbt propagator */
2173  )
2174 {
2175  SCIP_VAR** vars; /* array of the problems variables */
2176  int* nlcount; /* array that stores in how many nonlinearities each variable appears */
2177  int* nccount; /* array that stores in how many nonconvexities each variable appears */
2178 
2179  int bdidx; /* bound index inside propdata->bounds */
2180  int maxnlcount; /* maximal number of nonlinear constraints a variable appears in */
2181  int nvars; /* number of the problems variables */
2182  int i;
2183 
2184  assert(scip != NULL);
2185  assert(propdata != NULL);
2186  assert(SCIPisNLPConstructed(scip));
2187 
2188  SCIPdebugMsg(scip, "initialize bounds\n");
2189 
2190  /* get variable data */
2191  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2192 
2193  /* count nonlinearities */
2194  assert(SCIPgetNNLPVars(scip) == nvars);
2195 
2196  SCIP_CALL( SCIPallocBufferArray(scip, &nlcount, nvars) );
2197  SCIP_CALL( SCIPallocBufferArray(scip, &nccount, nvars) );
2198 
2199  SCIP_CALL( SCIPgetNLPVarsNonlinearity(scip, nlcount) );
2200  SCIP_CALL( getNLPVarsNonConvexity(scip, nccount) );
2201 
2202  maxnlcount = 0;
2203  for( i = 0; i < nvars; i++ )
2204  {
2205  if( maxnlcount < nlcount[i] )
2206  maxnlcount = nlcount[i];
2207  }
2208 
2209  /* allocate interesting bounds array */
2210  propdata->boundssize = 2 * nvars;
2211  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->bounds), 2 * nvars) );
2212 
2213  /* get all interesting variables and their bounds */
2214  bdidx = 0;
2215  for( i = 0; i < nvars; i++ )
2216  {
2217  if( varIsInteresting(scip, vars[i], (propdata->onlynonconvexvars ? nccount[i] : nlcount[i])) )
2218  {
2219  BOUND** bdaddress;
2220 
2221  /* create lower bound */
2222  bdaddress = &(propdata->bounds[bdidx]);
2223  SCIP_CALL( SCIPallocBlockMemory(scip, bdaddress) );
2224  propdata->bounds[bdidx]->boundtype = SCIP_BOUNDTYPE_LOWER;
2225  propdata->bounds[bdidx]->var = vars[i];
2226  propdata->bounds[bdidx]->found = FALSE;
2227  propdata->bounds[bdidx]->filtered = FALSE;
2228  propdata->bounds[bdidx]->newval = 0.0;
2229  propdata->bounds[bdidx]->score = getScore(scip, propdata->bounds[bdidx], nlcount[i], maxnlcount);
2230  propdata->bounds[bdidx]->done = FALSE;
2231  propdata->bounds[bdidx]->nonconvex = (nccount[i] > 0);
2232  propdata->bounds[bdidx]->index = bdidx;
2233  bdidx++;
2234 
2235  /* create upper bound */
2236  bdaddress = &(propdata->bounds[bdidx]);
2237  SCIP_CALL( SCIPallocBlockMemory(scip, bdaddress) );
2238  propdata->bounds[bdidx]->boundtype = SCIP_BOUNDTYPE_UPPER;
2239  propdata->bounds[bdidx]->var = vars[i];
2240  propdata->bounds[bdidx]->found = FALSE;
2241  propdata->bounds[bdidx]->filtered = FALSE;
2242  propdata->bounds[bdidx]->newval = 0.0;
2243  propdata->bounds[bdidx]->score = getScore(scip, propdata->bounds[bdidx], nlcount[i], maxnlcount);
2244  propdata->bounds[bdidx]->done = FALSE;
2245  propdata->bounds[bdidx]->nonconvex = (nccount[i] > 0);
2246  propdata->bounds[bdidx]->index = bdidx;
2247  bdidx++;
2248  }
2249  }
2250 
2251  /* free memory for buffering nonlinearities */
2252  assert(nlcount != NULL);
2253  assert(nccount != NULL);
2254  SCIPfreeBufferArray(scip, &nccount);
2255  SCIPfreeBufferArray(scip, &nlcount);
2256 
2257  /* set number of interesting bounds */
2258  propdata->nbounds = bdidx;
2259 
2260  /* propdata->bounds array if empty */
2261  if( propdata->nbounds <= 0 )
2262  {
2263  assert(propdata->nbounds == 0);
2264  assert(propdata->boundssize >= 0 );
2265  SCIPfreeBlockMemoryArray(scip, &(propdata->bounds), propdata->boundssize);
2266  }
2267 
2268  SCIPdebugMsg(scip, "problem has %d/%d interesting bounds\n", propdata->nbounds, 2 * nvars);
2269 
2270  if( propdata->nbounds > 0 )
2271  {
2272  /* sort bounds according to decreasing score; although this initial order will be overruled by the distance
2273  * criterion later, gives a more well-defined starting situation for OBBT and might help to reduce solver
2274  * variability
2275  */
2276  SCIPsortDownPtr((void**) propdata->bounds, compBoundsScore, propdata->nbounds);
2277  }
2278 
2279  return SCIP_OKAY;
2280 }
2281 
2282 
2283 /*
2284  * Callback methods of propagator
2285  */
2286 
2287 /** copy method for propagator plugins (called when SCIP copies plugins)
2288  *
2289  * @note The UG framework assumes that all default plug-ins of SCIP implement a copy callback. We check
2290  * SCIPgetSubscipDepth() in PROPEXEC to prevent the propagator to run in a sub-SCIP.
2291  */
2292 static
2293 SCIP_DECL_PROPCOPY(propCopyObbt)
2294 { /*lint --e{715}*/
2295  assert(scip != NULL);
2296  assert(prop != NULL);
2297  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2298 
2299  /* call inclusion method of constraint handler */
2300  SCIP_CALL( SCIPincludePropObbt(scip) );
2301 
2302  return SCIP_OKAY;
2303 }
2304 
2305 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
2306 static
2307 SCIP_DECL_PROPINITSOL(propInitsolObbt)
2308 { /*lint --e{715}*/
2309  SCIP_PROPDATA* propdata;
2310 
2311  assert(scip != NULL);
2312  assert(prop != NULL);
2313  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2314 
2315  /* get propagator data */
2316  propdata = SCIPpropGetData(prop);
2317  assert(propdata != NULL);
2318 
2319  propdata->bounds = NULL;
2320  propdata->nbounds = -1;
2321  propdata->boundssize = 0;
2322  propdata->cutoffrow = NULL;
2323  propdata->lastnode = -1;
2324 
2325  /* if genvbounds propagator is not available, we cannot create genvbounds */
2326  propdata->genvboundprop = propdata->creategenvbounds ? SCIPfindProp(scip, GENVBOUND_PROP_NAME) : NULL;
2327 
2328  SCIPdebugMsg(scip, "creating genvbounds: %s\n", propdata->genvboundprop != NULL ? "true" : "false");
2329 
2330  return SCIP_OKAY;
2331 }
2332 
2333 /** execution method of propagator */
2334 static
2335 SCIP_DECL_PROPEXEC(propExecObbt)
2336 { /*lint --e{715}*/
2337  SCIP_PROPDATA* propdata;
2338  SCIP_Longint itlimit;
2339 
2340  assert(scip != NULL);
2341  assert(prop != NULL);
2342  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2343 
2344  *result = SCIP_DIDNOTRUN;
2345 
2346  /* do not run in: presolving, repropagation, probing mode, if no objective propagation is allowed */
2347  if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPinRepropagation(scip) || SCIPinProbing(scip) || !SCIPallowObjProp(scip) )
2348  return SCIP_OKAY;
2349 
2350  /* do not run propagator in a sub-SCIP */
2351  if( SCIPgetSubscipDepth(scip) > 0 )
2352  return SCIP_OKAY;
2353 
2354  /* only run for nonlinear problems, i.e., if NLP is constructed */
2355  if( !SCIPisNLPConstructed(scip) )
2356  {
2357  SCIPdebugMsg(scip, "NLP not constructed, skipping obbt\n");
2358  return SCIP_OKAY;
2359  }
2360 
2361  /* 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
2362  * since pricing is not performed in probing mode
2363  */
2364  if( !SCIPallColsInLP(scip) )
2365  {
2366  SCIPdebugMsg(scip, "not all columns in LP, skipping obbt\n");
2367  return SCIP_OKAY;
2368  }
2369 
2370  if( !SCIPallowObjProp(scip) )
2371  return SCIP_OKAY;
2372 
2373  /* get propagator data */
2374  propdata = SCIPpropGetData(prop);
2375  assert(propdata != NULL);
2376 
2377  /* ensure that bounds are initialized */
2378  if( propdata->nbounds == -1 )
2379  {
2380  /* bounds must be initialized at root node */
2381  if( SCIPgetDepth(scip) == 0 )
2382  {
2383  SCIP_CALL( initBounds(scip, propdata) );
2384  }
2385  else
2386  {
2387  assert(!SCIPinProbing(scip));
2388  return SCIP_OKAY;
2389  }
2390  }
2391  assert(propdata->nbounds >= 0);
2392 
2393  /* do not run if there are no interesting bounds */
2394  /**@todo disable */
2395  if( propdata->nbounds <= 0 )
2396  {
2397  SCIPdebugMsg(scip, "there are no interesting bounds\n");
2398  return SCIP_OKAY;
2399  }
2400 
2401  /* only run once in a node != root */
2402  if( SCIPgetDepth(scip) > 0 && SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) == propdata->lastnode )
2403  {
2404  return SCIP_OKAY;
2405  }
2406 
2407  SCIPdebugMsg(scip, "applying obbt for problem <%s> at depth %d\n", SCIPgetProbName(scip), SCIPgetDepth(scip));
2408 
2409  /* without an optimal LP solution we don't want to run; this may be because propagators with higher priority have
2410  * already found reductions or numerical troubles occured during LP solving
2411  */
2412  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL && SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
2413  {
2414  SCIPdebugMsg(scip, "aborting since no optimal LP solution is at hand\n");
2415  return SCIP_OKAY;
2416  }
2417 
2418  /* compute iteration limit */
2419  if( propdata->itlimitfactor > 0.0 )
2420  itlimit = (SCIP_Longint) MAX(propdata->itlimitfactor * SCIPgetNRootLPIterations(scip),
2421  propdata->minitlimit); /*lint !e666*/
2422  else
2423  itlimit = -1;
2424 
2425  /* apply obbt */
2426  SCIP_CALL( applyObbt(scip, propdata, itlimit, result) );
2427  assert(*result != SCIP_DIDNOTRUN);
2428 
2429  /* set current node as last node */
2430  propdata->lastnode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
2431 
2432  return SCIP_OKAY;
2433 }
2434 
2435 /** propagation conflict resolving method of propagator */
2436 static
2437 SCIP_DECL_PROPRESPROP(propRespropObbt)
2438 { /*lint --e{715}*/
2439  *result = SCIP_DIDNOTFIND;
2440 
2441  return SCIP_OKAY;
2442 }
2443 
2444 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
2445 static
2446 SCIP_DECL_PROPEXITSOL(propExitsolObbt)
2447 { /*lint --e{715}*/
2448  SCIP_PROPDATA* propdata;
2449  int i;
2450 
2451  assert(scip != NULL);
2452  assert(prop != NULL);
2453  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2454 
2455  /* get propagator data */
2456  propdata = SCIPpropGetData(prop);
2457  assert(propdata != NULL);
2458 
2459  /* note that because we reset filtered flags to false at each call to obbt, the same bound may be filtered multiple
2460  * times
2461  */
2462  SCIPstatisticMessage("DIVE-LP: %" SCIP_LONGINT_FORMAT " NFILTERED: %d NTRIVIALFILTERED: %d NSOLVED: %d "
2463  "FILTER-LP: %" SCIP_LONGINT_FORMAT " NGENVB(dive): %d NGENVB(aggr.): %d NGENVB(triv.) %d\n",
2464  propdata->nprobingiterations, propdata->nfiltered, propdata->ntrivialfiltered, propdata->nsolvedbounds,
2465  propdata->nfilterlpiters, propdata->ngenvboundsprobing, propdata->ngenvboundsaggrfil, propdata->ngenvboundstrivfil);
2466 
2467  /* free memory allocated for the bounds */
2468  if( propdata->nbounds > 0 )
2469  {
2470  /* free bounds */
2471  for( i = propdata->nbounds - 1; i >= 0; i-- )
2472  {
2473  SCIPfreeBlockMemory(scip, &(propdata->bounds[i])); /*lint !e866*/
2474  }
2475  SCIPfreeBlockMemoryArray(scip, &(propdata->bounds), propdata->boundssize);
2476  }
2477 
2478  propdata->nbounds = -1;
2479 
2480  return SCIP_OKAY;
2481 }
2482 
2483 /** destructor of propagator to free user data (called when SCIP is exiting) */
2484 static
2485 SCIP_DECL_PROPFREE(propFreeObbt)
2486 { /*lint --e{715}*/
2487  SCIP_PROPDATA* propdata;
2488 
2489  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
2490 
2491  /* free propagator data */
2492  propdata = SCIPpropGetData(prop);
2493  assert(propdata != NULL);
2494 
2495  SCIPfreeBlockMemory(scip, &propdata);
2496 
2497  SCIPpropSetData(prop, NULL);
2498 
2499  return SCIP_OKAY;
2500 }
2501 
2502 
2503 /*
2504  * propagator specific interface methods
2505  */
2506 
2507 /** creates the obbt propagator and includes it in SCIP */
2508 SCIP_RETCODE SCIPincludePropObbt(
2509  SCIP* scip /**< SCIP data structure */
2510  )
2511 {
2512  SCIP_PROPDATA* propdata;
2513  SCIP_PROP* prop;
2514 
2515  /* create obbt propagator data */
2516  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
2517 
2518  /* initialize statistic variables */
2519  propdata->nprobingiterations = 0;
2520  propdata->nfiltered = 0;
2521  propdata->ntrivialfiltered = 0;
2522  propdata->nsolvedbounds = 0;
2523  propdata->ngenvboundsprobing = 0;
2524  propdata->ngenvboundsaggrfil = 0;
2525  propdata->ngenvboundstrivfil = 0;
2526  propdata->nfilterlpiters = 0;
2527  propdata->lastidx = -1;
2528  propdata->propagatecounter = 0;
2529  propdata->npropagatedomreds = 0;
2530 
2531  /* include propagator */
2532  SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
2533  propExecObbt, propdata) );
2534 
2535  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyObbt) );
2536  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeObbt) );
2537  SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolObbt) );
2538  SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolObbt) );
2539  SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropObbt) );
2540 
2541  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/creategenvbounds",
2542  "should obbt try to provide genvbounds if possible?",
2543  &propdata->creategenvbounds, TRUE, DEFAULT_CREATE_GENVBOUNDS, NULL, NULL) );
2544 
2545  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/normalize",
2546  "should coefficients in filtering be normalized w.r.t. the domains sizes?",
2547  &propdata->normalize, TRUE, DEFAULT_FILTERING_NORM, NULL, NULL) );
2548 
2549  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/applyfilterrounds",
2550  "try to filter bounds in so-called filter rounds by solving auxiliary LPs?",
2551  &propdata->applyfilterrounds, TRUE, DEFAULT_APPLY_FILTERROUNDS, NULL, NULL) );
2552 
2553  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/applytrivialfilter",
2554  "try to filter bounds with the LP solution after each solve?",
2555  &propdata->applytrivialfilter, TRUE, DEFAULT_APPLY_TRIVIALFITLERING, NULL, NULL) );
2556 
2557  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/genvbdsduringfilter",
2558  "should we try to generate genvbounds during trivial and aggressive filtering?",
2559  &propdata->genvbdsduringfilter, TRUE, DEFAULT_GENVBDSDURINGFILTER, NULL, NULL) );
2560 
2561  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/genvbdsduringsepa",
2562  "try to create genvbounds during separation process?",
2563  &propdata->genvbdsduringsepa, TRUE, DEFAULT_GENVBDSDURINGSEPA, NULL, NULL) );
2564 
2565  SCIP_CALL( SCIPaddIntParam(scip, "propagating/" PROP_NAME "/minfilter",
2566  "minimal number of filtered bounds to apply another filter round",
2567  &propdata->nminfilter, TRUE, DEFAULT_FILTERING_MIN, 1, INT_MAX, NULL, NULL) );
2568 
2569  SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/itlimitfactor",
2570  "multiple of root node LP iterations used as total LP iteration limit for obbt (<= 0: no limit )",
2571  &propdata->itlimitfactor, FALSE, DEFAULT_ITLIMITFACTOR, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2572 
2573  SCIP_CALL( SCIPaddLongintParam(scip, "propagating/" PROP_NAME "/minitlimit",
2574  "minimum LP iteration limit",
2575  &propdata->minitlimit, FALSE, DEFAULT_MINITLIMIT, 0L, SCIP_LONGINT_MAX, NULL, NULL) );
2576 
2577  SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/dualfeastol",
2578  "feasibility tolerance for reduced costs used in obbt; this value is used if SCIP's dual feastol is greater",
2579  &propdata->dualfeastol, FALSE, DEFAULT_DUALFEASTOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2580 
2581  SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/conditionlimit",
2582  "maximum condition limit used in LP solver (-1.0: no limit)",
2583  &propdata->conditionlimit, FALSE, DEFAULT_CONDITIONLIMIT, -1.0, SCIP_REAL_MAX, NULL, NULL) );
2584 
2585  SCIP_CALL( SCIPaddRealParam(scip, "propagating/" PROP_NAME "/boundstreps",
2586  "minimal relative improve for strengthening bounds",
2587  &propdata->boundstreps, FALSE, DEFAULT_BOUNDSTREPS, 0.0, 1.0, NULL, NULL) );
2588 
2589  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/onlynonconvexvars",
2590  "only apply obbt on non-convex variables",
2591  &propdata->onlynonconvexvars, TRUE, DEFAULT_ONLYNONCONVEXVARS, NULL, NULL) );
2592 
2593  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/tightintboundsprobing",
2594  "should integral bounds be tightened during the probing mode?",
2595  &propdata->tightintboundsprobing, TRUE, DEFAULT_TIGHTINTBOUNDSPROBING, NULL, NULL) );
2596 
2597  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/tightcontboundsprobing",
2598  "should continuous bounds be tightened during the probing mode?",
2599  &propdata->tightcontboundsprobing, TRUE, DEFAULT_TIGHTCONTBOUNDSPROBING, NULL, NULL) );
2600 
2601  SCIP_CALL( SCIPaddIntParam(scip, "propagating/" PROP_NAME "/orderingalgo",
2602  "select the type of ordering algorithm which should be used (0: no special ordering, 1: greedy, 2: greedy reverse)",
2603  &propdata->orderingalgo, TRUE, DEFAULT_ORDERINGALGO, 0, 2, NULL, NULL) );
2604 
2605  SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/separatesol",
2606  "should the obbt LP solution be separated?",
2607  &propdata->separatesol, TRUE, DEFAULT_SEPARATESOL, NULL, NULL) );
2608 
2609  SCIP_CALL( SCIPaddIntParam(scip, "propagating/" PROP_NAME "/sepaminiter",
2610  "minimum number of iteration spend to separate an obbt LP solution",
2611  &propdata->sepaminiter, TRUE, DEFAULT_SEPAMINITER, 0, INT_MAX, NULL, NULL) );
2612 
2613  SCIP_CALL( SCIPaddIntParam(scip, "propagating/" PROP_NAME "/sepamaxiter",
2614  "maximum number of iteration spend to separate an obbt LP solution",
2615  &propdata->sepamaxiter, TRUE, DEFAULT_SEPAMAXITER, 0, INT_MAX, NULL, NULL) );
2616 
2617  SCIP_CALL( SCIPaddIntParam(scip, "propagating/" PROP_NAME "/propagatefreq",
2618  "trigger a propagation round after that many bound tightenings (0: no propagation)",
2619  &propdata->propagatefreq, TRUE, DEFAULT_PROPAGATEFREQ, 0, INT_MAX, NULL, NULL) );
2620 
2621  return SCIP_OKAY;
2622 }
SCIP_RESULT
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
countNLRowVarsNonConvexity
static SCIP_RETCODE countNLRowVarsNonConvexity(SCIP *scip, int *nlcounts, SCIP_NLROW *nlrow)
Definition: prop_obbt.c:1953
SCIPfreeBlockMemoryArray
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21975
DEFAULT_APPLY_FILTERROUNDS
#define DEFAULT_APPLY_FILTERROUNDS
Definition: prop_obbt.c:62
DEFAULT_GENVBDSDURINGFILTER
#define DEFAULT_GENVBDSDURINGFILTER
Definition: prop_obbt.c:66
SCIP_BOUNDTYPE
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
PROP_NAME
#define PROP_NAME
Definition: prop_obbt.c:49
PROP_FREQ
#define PROP_FREQ
Definition: prop_obbt.c:53
SCIPinRepropagation
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip.c:40735
SCIP_DIDNOTRUN
Definition: type_result.h:33
SCIPgetNRootLPIterations
SCIP_Longint SCIPgetNRootLPIterations(SCIP *scip)
Definition: scip.c:41653
SCIPallocBlockMemoryArray
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21958
SCIPisNLPConstructed
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip.c:30965
SCIPtightenVarLb
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22212
SCIPcacheRowExtensions
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30363
Bound::done
unsigned int done
Definition: prop_obbt.c:124
SCIP_Interval
Definition: intervalarith.h:37
SCIPisFeasEQ
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46320
SCIPgetCurrentNode
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:40680
SCIP_DECL_SORTPTRCOMP
static SCIP_DECL_SORTPTRCOMP(compBoundsScore)
Definition: prop_obbt.c:1247
SCIPgetStage
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:814
filterExistingLP
static SCIP_RETCODE filterExistingLP(SCIP *scip, SCIP_PROPDATA *propdata, int *nfiltered, BOUND *currbound)
Definition: prop_obbt.c:695
SCIP_LPSOLSTAT_TIMELIMIT
Definition: type_lp.h:39
DEFAULT_MINITLIMIT
#define DEFAULT_MINITLIMIT
Definition: prop_obbt.c:78
SCIPgetNLPIterations
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:41609
sortBounds
static SCIP_RETCODE sortBounds(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_obbt.c:1283
SCIPcreateEmptyRowUnspec
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.c:30210
exchangeBounds
static void exchangeBounds(SCIP_PROPDATA *propdata, int i)
Definition: prop_obbt.c:672
SCIPfindConshdlr
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6576
SCIPgetCutoffbound
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42726
SCIPflushRowExtensions
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30386
SCIPisUbBetter
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip.c:46683
SCIP_BASESTAT
enum SCIP_BaseStat SCIP_BASESTAT
Definition: type_lpi.h:86
SCIPapplyCutsProbing
SCIP_RETCODE SCIPapplyCutsProbing(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip.c:35978
DEFAULT_BOUNDSTREPS
#define DEFAULT_BOUNDSTREPS
Definition: prop_obbt.c:71
SCIPfindProp
SCIP_PROP * SCIPfindProp(SCIP *scip, const char *name)
Definition: scip.c:7823
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17169
infty2infty
#define infty2infty(infty1, infty2, val)
Definition: prop_obbt.c:109
SCIPgetRealParam
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip.c:4461
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition: def.h:225
DEFAULT_SEPAMAXITER
#define DEFAULT_SEPAMAXITER
Definition: prop_obbt.c:99
SCIPcolGetBasisStatus
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
Definition: lp.c:16150
SCIP_DECL_PROPEXITSOL
static SCIP_DECL_PROPEXITSOL(propExitsolObbt)
Definition: prop_obbt.c:2458
bound
static long bound
Definition: GomoryHuTree.cpp:35
SCIPaddVarToRow
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:30418
DEFAULT_ITLIMITFACTOR
#define DEFAULT_ITLIMITFACTOR
Definition: prop_obbt.c:75
SCIPgetVarRedcost
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:19074
SCIPisPositive
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:46110
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17225
filterRound
static SCIP_RETCODE filterRound(SCIP *scip, SCIP_PROPDATA *propdata, int itlimit, int *nfiltered, SCIP_Real *objcoefs, int *objcoefsinds, int nobjcoefs)
Definition: prop_obbt.c:814
SCIPincludePropObbt
SCIP_RETCODE SCIPincludePropObbt(SCIP *scip)
Definition: prop_obbt.c:2520
SCIP_Var
Definition: struct_var.h:197
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16735
SCIPdualfeastol
SCIP_Real SCIPdualfeastol(SCIP *scip)
Definition: scip.c:45536
SCIPisFeasGE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46372
SCIPgetVarsData
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11554
nextBound
static int nextBound(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool convexphase)
Definition: prop_obbt.c:1315
SCIPconshdlrGetConss
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4485
FALSE
#define FALSE
Definition: def.h:64
DEFAULT_SEPAMINITER
#define DEFAULT_SEPAMINITER
Definition: prop_obbt.c:98
SCIPaddLongintParam
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.c:4265
SCIPgetSubscipDepth
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip.c:3534
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:46050
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
SCIPisNegative
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:46122
DEFAULT_APPLY_TRIVIALFITLERING
#define DEFAULT_APPLY_TRIVIALFITLERING
Definition: prop_obbt.c:65
TRUE
#define TRUE
Definition: def.h:63
SCIPdebug
#define SCIPdebug(x)
Definition: pub_message.h:74
SCIPgetNlRowNonlinear
SCIP_RETCODE SCIPgetNlRowNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
Definition: cons_nonlinear.c:9739
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIPstatisticMessage
#define SCIPstatisticMessage
Definition: pub_message.h:104
SCIP_VARTYPE_BINARY
Definition: type_var.h:53
getFilterCoef
static SCIP_Real getFilterCoef(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype)
Definition: prop_obbt.c:426
SCIPvarGetProbindex
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16862
SCIPnlrowGetRhs
SCIP_Real SCIPnlrowGetRhs(SCIP_NLROW *nlrow)
Definition: nlp.c:3383
Bound::index
int index
Definition: prop_obbt.c:126
SCIPgetCurvatureNonlinear
SCIP_RETCODE SCIPgetCurvatureNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_Bool checkcurv, SCIP_EXPRCURV *curvature)
Definition: cons_nonlinear.c:9897
SCIPintervalSetBounds
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
Definition: intervalarith.c:484
SCIP_QuadElement::idx1
int idx1
Definition: type_expr.h:100
SCIPtightenVarUb
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22328
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
SCIP_QuadElement
Definition: type_expr.h:98
SCIPchgVarLbProbing
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:35367
SCIPgetNLPVarsNonlinearity
SCIP_RETCODE SCIPgetNLPVarsNonlinearity(SCIP *scip, int *nlcount)
Definition: scip.c:31076
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45985
GENVBOUND_PROP_NAME
#define GENVBOUND_PROP_NAME
Definition: prop_obbt.c:90
SCIP_LONGINT_MAX
#define SCIP_LONGINT_MAX
Definition: def.h:131
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
SCIP_LPSOLSTAT
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21956
SCIP_LPSOLSTAT_OBJLIMIT
Definition: type_lp.h:37
SCIPsetRealParam
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip.c:4776
SCIProwGetDualsol
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition: lp.c:16411
SCIPwarningMessage
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1260
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip.h:451
SCIPaddIntParam
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.c:4237
SCIPexprtreeGetVars
SCIP_VAR ** SCIPexprtreeGetVars(SCIP_EXPRTREE *tree)
Definition: nlp.c:101
tightenBoundProbing
static SCIP_RETCODE tightenBoundProbing(SCIP *scip, BOUND *bound, SCIP_Real newval, SCIP_Bool *tightened)
Definition: prop_obbt.c:1186
SCIPnlrowGetNQuadElems
int SCIPnlrowGetNQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3322
DEFAULT_ORDERINGALGO
#define DEFAULT_ORDERINGALGO
Definition: prop_obbt.c:86
getScore
static unsigned int getScore(SCIP *scip, BOUND *bound, int nlcount, int maxnlcount)
Definition: prop_obbt.c:1910
SCIPgetProbName
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10759
SCIProwIsInLP
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:16602
SCIPgetExprtreeBivariate
SCIP_EXPRTREE * SCIPgetExprtreeBivariate(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bivariate.c:8131
SCIPexprtreeCheckCurvature
SCIP_RETCODE SCIPexprtreeCheckCurvature(SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *varbounds, SCIP_EXPRCURV *curv, SCIP_INTERVAL *bounds)
Definition: expr.c:8950
SCIPisLbBetter
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
Definition: scip.c:46668
SCIPnodeGetNumber
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7172
createGenVBound
static SCIP_RETCODE createGenVBound(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *bound, SCIP_Bool *found)
Definition: prop_obbt.c:500
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17179
DEFAULT_DUALFEASTOL
#define DEFAULT_DUALFEASTOL
Definition: prop_obbt.c:67
SCIP_QuadElement::coef
SCIP_Real coef
Definition: type_expr.h:102
DEFAULT_FILTERING_NORM
#define DEFAULT_FILTERING_NORM
Definition: prop_obbt.c:59
SCIPgetNNLPVars
int SCIPgetNNLPVars(SCIP *scip)
Definition: scip.c:31054
applyBoundChgs
static SCIP_RETCODE applyBoundChgs(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_RESULT *result)
Definition: prop_obbt.c:1119
SCIP_LPSOLSTAT_ERROR
Definition: type_lp.h:40
SCIPnlrowGetQuadVars
SCIP_VAR ** SCIPnlrowGetQuadVars(SCIP_NLROW *nlrow)
Definition: nlp.c:3285
SCIP_DIDNOTFIND
Definition: type_result.h:35
SCIP_Cons
Definition: struct_cons.h:37
includeVarGenVBound
static SCIP_Bool includeVarGenVBound(SCIP *scip, SCIP_VAR *var)
Definition: prop_obbt.c:369
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45998
SCIPpropagateProbing
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:35650
SCIP_Conshdlr
Definition: struct_cons.h:117
SCIP_DECL_PROPRESPROP
static SCIP_DECL_PROPRESPROP(propRespropObbt)
Definition: prop_obbt.c:2449
SCIPsortDownPtr
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:47
PROP_DESC
#define PROP_DESC
Definition: prop_obbt.c:50
SCIPgenVBoundAdd
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)
Definition: prop_genvbounds.c:2005
SCIPfreeBufferArrayNull
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip.h:22004
SCIPendProbing
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:35326
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16555
cons_quadratic.h
constraint handler for quadratic constraints
SCIP_VARSTATUS_COLUMN
Definition: type_var.h:42
NULL
#define NULL
Definition: lpi_spx1.cpp:137
DEFAULT_GENVBDSDURINGSEPA
#define DEFAULT_GENVBDSDURINGSEPA
Definition: prop_obbt.c:100
REALABS
#define REALABS(x)
Definition: def.h:169
SCIPchgDualfeastol
SCIP_RETCODE SCIPchgDualfeastol(SCIP *scip, SCIP_Real dualfeastol)
Definition: scip.c:45623
SCIPvarGetLPSol
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17543
SCIPexprtreeGetNVars
int SCIPexprtreeGetNVars(SCIP_EXPRTREE *tree)
Definition: expr.c:8559
SCIPgetNlRowQuadratic
SCIP_RETCODE SCIPgetNlRowQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
Definition: cons_quadratic.c:13831
SCIP_OKAY
Definition: type_retcode.h:33
varIsInteresting
static SCIP_Bool varIsInteresting(SCIP *scip, SCIP_VAR *var, int nlcount)
Definition: prop_obbt.c:2166
SCIPnlrowGetQuadElems
SCIP_QUADELEM * SCIPnlrowGetQuadElems(SCIP_NLROW *nlrow)
Definition: nlp.c:3332
SCIPgetVarObjProbing
SCIP_Real SCIPgetVarObjProbing(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:35454
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:316
DEFAULT_PROPAGATEFREQ
#define DEFAULT_PROPAGATEFREQ
Definition: prop_obbt.c:101
SCIPsolveProbingLP
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:35886
OBBT_SCOREBASE
#define OBBT_SCOREBASE
Definition: prop_obbt.c:89
getNLPVarsNonConvexity
static SCIP_RETCODE getNLPVarsNonConvexity(SCIP *scip, int *nlcounts)
Definition: prop_obbt.c:2023
SCIPisFeasLE
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46346
SCIP_REDUCEDDOM
Definition: type_result.h:42
Bound::score
unsigned int score
Definition: prop_obbt.c:121
getIterationsLeft
static int getIterationsLeft(SCIP *scip, SCIP_Longint nolditerations, SCIP_Longint itlimit)
Definition: prop_obbt.c:396
SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:34
SCIP_Prop
Definition: struct_prop.h:37
INTERVALINFTY
#define INTERVALINFTY
Definition: prop_obbt.c:91
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21991
SCIP_Bool
#define SCIP_Bool
Definition: def.h:61
SCIPgetLPSolstat
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28948
Bound::newval
SCIP_Real newval
Definition: prop_obbt.c:119
SCIP_VARTYPE_IMPLINT
Definition: type_var.h:55
SCIPseparateSol
SCIP_RETCODE SCIPseparateSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool pretendroot, SCIP_Bool onlydelayed, SCIP_Bool *delayed, SCIP_Bool *cutoff)
Definition: scip.c:34467
SCIPgetDepth
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42321
cons_nonlinear.h
constraint handler for nonlinear constraints
SCIP_VARTYPE_INTEGER
Definition: type_var.h:54
prop_obbt.h
optimization-based bound tightening propagator
SCIPgetNlRowAbspower
SCIP_RETCODE SCIPgetNlRowAbspower(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
Definition: cons_abspower.c:7302
MAX
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_Row
Definition: struct_lp.h:192
debug.h
methods for debugging
DEFAULT_CREATE_GENVBOUNDS
#define DEFAULT_CREATE_GENVBOUNDS
Definition: prop_obbt.c:58
SCIPvarGetObj
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17017
SCIPsetPropCopy
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip.c:7645
SCIP_DECL_PROPFREE
static SCIP_DECL_PROPFREE(propFreeObbt)
Definition: prop_obbt.c:2497
Bound::boundtype
SCIP_BOUNDTYPE boundtype
Definition: prop_obbt.c:120
SCIP_QuadElement::idx2
int idx2
Definition: type_expr.h:101
SCIPvarGetCol
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16883
cons_bivariate.h
constraint handler for bivariate nonlinear constraints
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:46061
applySeparation
static SCIP_RETCODE applySeparation(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *currbound, SCIP_Longint *nleftiterations, SCIP_Bool *success)
Definition: prop_obbt.c:1367
cons_abspower.h
Constraint handler for absolute power constraints .
setObjProbing
static SCIP_RETCODE setObjProbing(SCIP *scip, SCIP_PROPDATA *propdata, BOUND *bound, SCIP_Real coef)
Definition: prop_obbt.c:322
SCIPsetPropExitsol
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip.c:7725
SCIPconshdlrGetNActiveConss
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4549
SCIP_DECL_PROPCOPY
static SCIP_DECL_PROPCOPY(propCopyObbt)
Definition: prop_obbt.c:2305
SCIPinProbing
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35163
SCIPpropGetName
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:887
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11680
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition: def.h:146
Bound::found
unsigned int found
Definition: prop_obbt.c:123
SCIPnlrowGetExprtree
SCIP_EXPRTREE * SCIPnlrowGetExprtree(SCIP_NLROW *nlrow)
Definition: nlp.c:3363
SCIP_LPSOLSTAT_UNBOUNDEDRAY
Definition: type_lp.h:36
SCIP_REAL_MIN
#define SCIP_REAL_MIN
Definition: def.h:147
solveLP
static SCIP_RETCODE solveLP(SCIP *scip, int itlimit, SCIP_Bool *error, SCIP_Bool *optimal)
Definition: prop_obbt.c:190
SCIP_EXPRCURV
enum SCIP_ExprCurv SCIP_EXPRCURV
Definition: type_expr.h:93
SCIPreleaseRow
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30290
PROP_TIMING
#define PROP_TIMING
Definition: prop_obbt.c:51
SCIPsetPropResprop
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip.c:7806
SCIPgetLPObjval
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29027
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46024
SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:48
SCIP_EXPRCURV_CONVEX
Definition: type_expr.h:84
DEFAULT_SEPARATESOL
#define DEFAULT_SEPARATESOL
Definition: prop_obbt.c:93
SCIPgetNCuts
int SCIPgetNCuts(SCIP *scip)
Definition: scip.c:34517
SCIPaddRowProbing
SCIP_RETCODE SCIPaddRowProbing(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:35938
findNewBounds
static SCIP_RETCODE findNewBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint *nleftiterations, SCIP_Bool convexphase)
Definition: prop_obbt.c:1449
DEFAULT_ONLYNONCONVEXVARS
#define DEFAULT_ONLYNONCONVEXVARS
Definition: prop_obbt.c:79
SCIPgetVars
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11635
SCIPsetPropInitsol
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip.c:7709
SCIPvarGetStatus
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16674
SCIP_Real
#define SCIP_Real
Definition: def.h:145
SCIP_PROPDATA
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:38
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
MIN
#define MIN(x, y)
Definition: memory.c:75
SCIP_NlRow
Definition: struct_nlp.h:63
SCIP_INVALID
#define SCIP_INVALID
Definition: def.h:165
evalBound
static SCIP_Real evalBound(SCIP *scip, BOUND *bound)
Definition: prop_obbt.c:1299
Bound::var
SCIP_VAR * var
Definition: prop_obbt.c:118
SCIPsetPropFree
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip.c:7661
SCIPpropGetData
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:735
SCIPpropSetData
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:745
filterBounds
static SCIP_RETCODE filterBounds(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit)
Definition: prop_obbt.c:975
SCIP_Longint
#define SCIP_Longint
Definition: def.h:130
SCIPallColsInLP
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip.c:29374
DEFAULT_TIGHTCONTBOUNDSPROBING
#define DEFAULT_TIGHTCONTBOUNDSPROBING
Definition: prop_obbt.c:83
addObjCutoff
static SCIP_RETCODE addObjCutoff(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_obbt.c:262
varIsFixedLocal
static SCIP_Bool varIsFixedLocal(SCIP *scip, SCIP_VAR *var)
Definition: prop_obbt.c:312
SCIP_STAGE_SOLVING
Definition: type_set.h:44
SCIP_DECL_PROPINITSOL
static SCIP_DECL_PROPINITSOL(propInitsolObbt)
Definition: prop_obbt.c:2319
SCIP_LPSOLSTAT_INFEASIBLE
Definition: type_lp.h:35
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16720
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46098
Bound::filtered
unsigned int filtered
Definition: prop_obbt.c:122
PROP_DELAY
#define PROP_DELAY
Definition: prop_obbt.c:54
PROP_PRIORITY
#define PROP_PRIORITY
Definition: prop_obbt.c:52
DEFAULT_CONDITIONLIMIT
#define DEFAULT_CONDITIONLIMIT
Definition: prop_obbt.c:70
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17235
SCIP_LPSOLSTAT_NOTSOLVED
Definition: type_lp.h:33
SCIP_LPSOLSTAT_ITERLIMIT
Definition: type_lp.h:38
Bound::nonconvex
unsigned int nonconvex
Definition: prop_obbt.c:125
DEFAULT_TIGHTINTBOUNDSPROBING
#define DEFAULT_TIGHTINTBOUNDSPROBING
Definition: prop_obbt.c:80
SCIP_BASESTAT_BASIC
Definition: type_lpi.h:82
SCIP_ExprTree
Definition: struct_expr.h:55
SCIPstartProbing
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35185
BMSclearMemoryArray
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:89
initBounds
static SCIP_RETCODE initBounds(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_obbt.c:2182
SCIPceil
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:46183
SCIP_DECL_PROPEXEC
static SCIP_DECL_PROPEXEC(propExecObbt)
Definition: prop_obbt.c:2347
SCIPnlrowGetLhs
SCIP_Real SCIPnlrowGetLhs(SCIP_NLROW *nlrow)
Definition: nlp.c:3373
applyObbt
static SCIP_RETCODE applyObbt(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Longint itlimit, SCIP_RESULT *result)
Definition: prop_obbt.c:1688
SCIPvarIsIntegral
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16746
SCIPchgVarUbProbing
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:35411
DEFAULT_FILTERING_MIN
#define DEFAULT_FILTERING_MIN
Definition: prop_obbt.c:72
SCIPaddRealParam
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.c:4293
SCIPfloor
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:46171
SCIPisConvexQuadratic
SCIP_Bool SCIPisConvexQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14059
SCIP_CUTOFF
Definition: type_result.h:39
SCIPallowObjProp
SCIP_Bool SCIPallowObjProp(SCIP *scip)
Definition: scip.c:25551
SCIPaddBoolParam
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.c:4211
prop_genvbounds.h
generalized variable bounds propagator
SCIPincludePropBasic
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.c:7608
SCIPchgVarObjProbing
SCIP_RETCODE SCIPchgVarObjProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip.c:35540
SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:58