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