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